Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker)

*** varlena.c	2008-09-02 23:45:48.000000000 +0100
--- varlena.c	2008-09-02 23:38:15.000000000 +0100
***************
*** 840,901 ****
  	}
  }
  
! static int
  text_position_next(int start_pos, TextPositionState *state)
  {
! 	int			pos = 0,
! 				p,
! 				px;
  
  	Assert(start_pos > 0);		/* else caller error */
  
! 	if (state->len2 <= 0)
! 		return start_pos;		/* result for empty pattern */
  
- 	if (!state->use_wchar)
- 	{
- 		/* simple case - single byte encoding */
- 		char	   *p1 = state->str1;
- 		char	   *p2 = state->str2;
  
! 		/* no use in searching str past point where search_str will fit */
! 		px = (state->len1 - state->len2);
  
- 		p1 += start_pos - 1;
  
! 		for (p = start_pos - 1; p <= px; p++)
! 		{
! 			if ((*p1 == *p2) && (strncmp(p1, p2, state->len2) == 0))
! 			{
! 				pos = p + 1;
! 				break;
! 			}
! 			p1++;
! 		}
! 	}
! 	else
! 	{
! 		/* not as simple - multibyte encoding */
! 		pg_wchar   *p1 = state->wstr1;
! 		pg_wchar   *p2 = state->wstr2;
  
- 		/* no use in searching str past point where search_str will fit */
- 		px = (state->len1 - state->len2);
  
! 		p1 += start_pos - 1;
  
! 		for (p = start_pos - 1; p <= px; p++)
! 		{
! 			if ((*p1 == *p2) && (pg_wchar_strncmp(p1, p2, state->len2) == 0))
! 			{
! 				pos = p + 1;
! 				break;
! 			}
! 			p1++;
! 		}
! 	}
  
! 	return pos;
  }
  
  static void
--- 840,1027 ----
  	}
  }
  
! /* text_position_next
!  * David Rowley 2008-09-01
!  * Uses Boyer-Moore searching
!  */
! int
  text_position_next(int start_pos, TextPositionState *state)
  {
!   
!   int skiptable[256];
!   int ai;
!   int hashsize;
! 
!   /*
!    * state->len2 = needle length in chars 
!    * state->len1 = haystack length in chars 
!    */
  
  	Assert(start_pos > 0);		/* else caller error */
  
!   if (state->len2 <= 0)
! 		return start_pos;		/* Empty needle, found it! */
  
  
!   /* Changed for zero based arrays */
!   start_pos--;
  
  
!   /* Eliminate the impossible first, the needle is
!    * too big for the haystack.
!    */
!   if (state->len1 + start_pos < state->len2)
!     return 0;
! 
!   /* Here we must determine how much of the skip table we should use.
!    * With haystack lengths of only a few characters we don't really want
!    * to have to initalize the full 256 elements of the table. Such an
!    * initialization would take too long in comparison to the rest of the
!    * search time.
!    * To get around this problem when searching for smaller strings we only
!    * use part of the skiptable, the larger the search (or at least the longer
!    * we estimate that it will take) the more we use of the skip table.
!    *
!    * After quite a few benchmarks a rule of thumb seems to show that the
!    * best skip table size is around 10 times less than the length of the
!    * haystack. Of course this is not an exact science. The needle length
!    * counts and also the mix of characters in both the needle and the haystack.
!    * It might look like a good idea to make the skip table around the same size
!    * as the needle, however that likely means more collisions or possibly no 
!    * empty positions in the table. That would mean we'd never be able to
!    * skip the length of the needle.
!    * 
!    * We skiptable[<char value> & hashsize] to tell us how many characters
!    * we should skip ahead in the haystack when we don't find a match.
!    * It does not matter that it's a lossy hash check as we're re-checking the
!    * actual character value again once the loop reiterates.
!    *
!    * The above method works both for char and pg_wchar. Perhaps with UTF8
!    * the character mix will be greater.
!    *
!    * The following code calculates the hashsize. Notice that for small 
!    * searches we're bearly using any of the skiptable. We also allocate
!    * the hash size to smaller searches first to allow them to get on 
!    * searching...
!    *
!    */
! 
!   if ((state->len2 - start_pos) < 16)
!     hashsize = 3;
!   else if ((state->len2 - start_pos) < 64)
!     hashsize = 7;
!   else if ((state->len2 - start_pos) < 128)
!     hashsize = 15;
!   else if ((state->len2 - start_pos) < 512)
!     hashsize = 31;
!   else if ((state->len2 - start_pos) < 2048)
!     hashsize = 63;
!   else if ((state->len2 - start_pos) < 4096)
!     hashsize = 127;
!   else
!     hashsize = 255;
! 
!  
!   /* Initalize the skip table. We set all elements to the needle length */
!   for (ai = 0; ai <= hashsize; ai++)
!     skiptable[ai] = state->len2;
  
  
! 	if (!state->use_wchar)
!   {
!     char *nptr;
!     char *hptr;
!     char *p;
!     char *needle = state->str2;
!     char *haystack = state->str1;
! 
!     /* Here we process the needle marking the last occurence
!      * of each character (ignoring the very last character)
!      */
!     for (ai = 0; ai < state->len2 - 1; ai++)
!       skiptable[(unsigned char) needle[ai] & hashsize] = state->len2 - ai - 1;
! 
!   
!     /* Start at startpos plus the length of the needle */
!     hptr = &haystack[state->len2 - 1 + start_pos];
! 
!     while (hptr < &haystack[state->len1]) 
!     {
!       nptr = &needle[state->len2 - 1]; /* Point to the end of the needle */
!       p = hptr;
! 
!       while (*nptr == *p) 
!       {
!         /* Do we have it? Return 1 based array pos */
!         if (nptr-- == needle) 
!           return p - haystack + 1; 
! 
!         p--;
!       }
! 
!       /* Ask the skiptable where to look next. If it
!        * finds a match then we align the two ~matching~
!        * characters and start another search there.
!        * Else we skip a whole needle length.
!        * Of course the ~matching~ characters only have the
!        * same hash value, the character value may be different.
!        */
! 
!       hptr += skiptable[(unsigned char) *hptr & hashsize];
!     }
! 
!     return 0; /* Not found */
! 
!   } 
!   
!   else
!   { 
!     /* The multibyte char version. This works exactly the same way.
!      */
!     pg_wchar *nptr;
!     pg_wchar *hptr;
!     pg_wchar *p;
!     pg_wchar *needle = state->wstr2;
!     pg_wchar *haystack = state->wstr1;
! 
!     /* Here we process the needle marking the last occurence
!      * of each character (ignoring the very last character)
!      */
!     for (ai = 0; ai < state->len2 - 1; ai++)
!       skiptable[needle[ai] & hashsize] = state->len2 - ai - 1;
! 
! 
!     /* Start at start_pos plus the length of the needle */
!     hptr = &haystack[state->len2 - 1 + start_pos];
! 
!     while (hptr < &haystack[state->len1]) 
!     {
!       nptr = &needle[state->len2 - 1]; /* Point to the end of the needle */
!       p = hptr;
! 
!       while (*nptr == *p) 
!       {
!   
!         /* Do we have it? Return 1 based array pos */
!         if (nptr-- == needle) 
!           return p - haystack + 1; 
! 
!         p--;
!       }
!  
!       /* Ask the skiptable where to look next. If it
!        * finds a match then we align the two ~matching~
!        * characters and start another search there.
!        * Else we skip a whole needle length.
!        * Of course the ~matching~ characters only have the
!        * same hash value, the character value may be different.
!        */
  
!        hptr += skiptable[*hptr & hashsize];
!     }
  
!     return 0; /* Not found */
!   }
  }
  
  static void