findrep.c

THOMSON-DAVIS用C语言开发的编缉器,简单,易懂.

   rc = OK;
   if (bm.search_defined == OK) {
      old_rcol = win->rcol;
      if (mode.inflate_tabs)
         win->rcol = entab_adjust_rcol( win->ll->line, win->ll->len, win->rcol);
      update_line( win );
      show_search_message( SEARCHING, g_display.diag_color );
      bin_offset = win->bin_offset;
      if (direction == FORWARD) {
         if ((ll = forward_boyer_moore_search( win, &found_line, &rcol )) != NULL) {
            if (g_status.wrapped && g_status.macro_executing)
               rc = ask_wrap_replace( win, &new_string );
            if (rc == OK)
               find_adjust( win, ll, found_line, rcol );
            else
               win->bin_offset = bin_offset;
         }
      } else {
         if ((ll = backward_boyer_moore_search( win, &found_line, &rcol )) != NULL) {
            if (g_status.wrapped && g_status.macro_executing)
               rc = ask_wrap_replace( win, &new_string );
            if (rc == OK)
               find_adjust( win, ll, found_line, rcol );
            else
               win->bin_offset = bin_offset;
         }
      }
      if (g_status.wrapped)
         show_search_message( WRAPPED, g_display.diag_color );
      else
         show_search_message( CLR_SEARCH, g_display.mode_color );
      if (ll == NULL) {
         /*
          * string not found
          */
         if (mode.inflate_tabs)
            win->rcol = old_rcol;
         combine_strings( pattern, find5a, (char *)bm.pattern, find5b );
         error( WARNING, win->bottom_line, pattern );
         rc = ERROR;
      }
      show_curl_line( win );
      make_ruler( win );
      show_ruler( win );
   } else {
      /*
       * find pattern not defined
       */
      error( WARNING, win->bottom_line, find6 );
      rc = ERROR;
   }
   return( rc );
}


/*
 * Name:    build_boyer_array
 * Purpose: To set up the boyer array for forward and backward searches.
 * Date:    June 5, 1991
 * Notes:   Set up one array for forward searches and another for backward
 *          searches.  If user decides to ignore case then fill in array
 *          with reverse case characters so both upper and lower case
 *          characters are defined.
 */
void build_boyer_array( void )
{

   /*
    * set up for forward search
    */
   if (g_status.command == DefineGrep  ||  g_status.command == RepeatGrep) {

      assert( strlen( (char *)sas_bm.pattern ) + 1 < MAX_COLS );

      memcpy( bm.pattern, sas_bm.pattern, strlen( (char *)sas_bm.pattern ) +1 );
      bm.search_defined = OK;
   }

   if (bm.search_defined == OK) {
      build_forward_skip( &bm );
      bm.forward_md2 = calculate_forward_md2( (char *)bm.pattern,
                                                bm.pattern_length );

      /*
       * set up for backward search
       */
      build_backward_skip( &bm );
      bm.backward_md2 = calculate_backward_md2( (char *)bm.pattern,
                                                  bm.pattern_length );
   }


   /*
    * build an array for search and seize.
    */
   if (sas_bm.search_defined == OK) {
      build_forward_skip( &sas_bm );
      sas_bm.forward_md2 = calculate_forward_md2( (char *)sas_bm.pattern,
                                                    sas_bm.pattern_length );

      /*
       * set up for backward search
       */
      build_backward_skip( &sas_bm );
      sas_bm.backward_md2 = calculate_backward_md2( (char *)sas_bm.pattern,
                                                      sas_bm.pattern_length );
   }
}


/*
 * Name:    build_forward_skip
 * Purpose: build Boyer-Moore forward skip array
 * Date:    October 31, 1992
 * Passed:  bmp:  pointer to Boyer-Moore structure
 * Notes:   build standard Boyer-Moore forward skip array.
 *          Thanks to Tom Waters, [e-mail], for finding a
 *           bug in TDE 1.3 when building the ignore skip index array.
 */
void build_forward_skip( boyer_moore_type *bmp )
{
register unsigned char *p;
register int i;

   assert( strlen( (char *)bmp->pattern ) < MAX_COLS );

   i = bmp->pattern_length = (int)strlen( (char *)bmp->pattern );

   /*
    * set skip index of all characters to length of string
    */
   memset( bmp->skip_forward, i, 256 );
   i--;

   /*
    * for each character in string, set the skip index
    */
   for (p=bmp->pattern; i>=0; i--, p++) {

      assert( (char)i < bmp->skip_forward[*p] );

      bmp->skip_forward[*p] = (char)i;
      if (mode.search_case == IGNORE) {
         if (*p >= 'A' && *p <= 'Z') {

            assert( (char)i < bmp->skip_forward[*p+32] );

            bmp->skip_forward[*p+32] = (char)i;
         } else if (*p >= 'a' && *p <= 'z') {

            assert( (char)i < bmp->skip_forward[*p-32] );

            bmp->skip_forward[*p-32] = (char)i;
         }
      }
   }
}


/*
 * Name:    build_backward_skip
 * Purpose: build Boyer-Moore backward skip array
 * Date:    October 31, 1992
 * Passed:  bmp:  pointer to Boyer-Moore structure
 * Notes:   build standard Boyer-Moore backward skip array.
 *          Thanks to Tom Waters, [e-mail], for finding a
 *           bug in TDE 1.3 when building the ignore skip index array.
 */
void build_backward_skip( boyer_moore_type *bmp )
{
register unsigned char *p;
register int i;

   i = -bmp->pattern_length;
   memset( bmp->skip_backward, i, 256 );
   i++;
   for (p=bmp->pattern + bmp->pattern_length - 1; i<=0; i++, p--) {

      assert( (char)i > bmp->skip_backward[*p] );

      bmp->skip_backward[*p] = (char)i;
      if (mode.search_case == IGNORE) {
         if (*p >= 'A' && *p <= 'Z') {

            assert( (char)i > bmp->skip_backward[*p+32] );

            bmp->skip_backward[*p+32] = (char)i;
         } else if (*p >= 'a' && *p <= 'z') {

            assert( (char)i > bmp->skip_backward[*p-32] );

            bmp->skip_backward[*p-32] = (char)i;
         }
      }
   }
}


/*
 * Name:    calculate_forward_md2
 * Purpose: Calculate mini delta2 for forward searches
 * Date:    October 31, 1992
 * Passed:  p:  pointer to pattern
 *          len: length of pattern
 * Notes:   Hume and Sunday (see above) demonstrate in their paper that
 *            using a simple shift function on mismatches with BM
 *            gives one of the fastest run times for general text searching.
 *          mini delta2 is, from the end of the string, the first leftmost
 *            occurrence of the rightmost character.  mini delta2 is 1 in
 *            the worst case.  in previous versions of TDE, the shift function
 *            was hard-coded as 1 -- the worst case.  typically, mini delta2
 *            will be the length of the search pattern.
 */
int  calculate_forward_md2( char *p, int len )
{
int  last_c;
register int i;
register int md2;

   md2 = 1;
   i = len - 1;
   last_c = p[i];
   if (mode.search_case == IGNORE) {
      last_c = tolower( last_c );
      for (i--; i >= 0  &&  last_c != tolower( p[i] ); i--)
         ++md2;
   } else
      for (i--; i >= 0  &&  last_c != p[i]; i--)
         ++md2;

   assert( md2 >= 1  &&  md2 <= len );

   return( md2 );
}


/*
 * Name:    calculate_backward_md2
 * Purpose: Calculate mini delta2 for backward searches
 * Date:    October 31, 1992
 * Passed:  p:  pointer to pattern
 *          len: length of pattern
 * Notes:   the backward mini delta2 is, from the start of the string, the
 *            first rightmost occurrence of the leftmost character.  in the
 *            worst case, mini delta2 is -1.  typically, mini delta2 is the
 *            negative length of the search pattern.
 */
int  calculate_backward_md2( char *p, int len )
{
int  first_c;
register int i;
register int md2;

   md2 = -1;
   i = 1;
   first_c = *p;
   if (mode.search_case == IGNORE) {
      first_c = tolower( first_c );
      for (; i < len  &&  first_c != tolower( p[i] ); i++)
         --md2;
   } else
      for (; i < len  &&  first_c != p[i]; i++)
         --md2;

   assert( md2 <= -1  &&  md2 >= -len );

   return( md2 );
}


/*
 * Name:    forward_boyer_moore_search
 * Purpose: search forward for pattern using boyer array
 * Passed:  window:  pointer to current window
 *          rline:   pointer to real line counter
 *          rcol:    pointer to real column variable
 * Returns: position in file if found or NULL if not found
 * Date:    June 5, 1991
 * Notes:   Start searching from cursor position to end of file.  If we hit
 *          end of file without a match, start searching from the beginning
 *          of file to cursor position.  (do wrapped searches)
 */
line_list_ptr forward_boyer_moore_search( WINDOW *window, long *rline,
     int *rcol )
{
register int len;
int  i;
int  end;
register WINDOW *win;  /* put window pointer in a register */
line_list_ptr ll;

   /*
    * if cursor is beyond end of line then start at end of line
    */
   win  = window;
   i = win->rcol + 1;
   len = win->ll->len;
   if (i > len)
      i = len;
   if (i < 0)
      i = 0;


   *rcol = i;

   assert( *rcol >= 0 );

   *rline = win->rline;
   ll = search_forward( win->ll, rline, (size_t *)rcol );

   if (ll == NULL) {

      end = 0;
      if (win->ll->next != NULL) {
         end = win->ll->next->len;
         win->ll->next->len = EOF;
      }

      /*
       * haven't found pattern yet - now search from beginning of file
       */
      g_status.wrapped = TRUE;

      *rcol = 0;
      *rline = 1L;
      ll = search_forward( win->file_info->line_list, rline, (size_t *)rcol );

      if (ll == win->ll  &&  *rcol >= win->rcol)
         ll = NULL;

      if (win->ll->next != NULL)
         win->ll->next->len = end;
   }

   if (ll != NULL)
      bin_offset_adjust( win, *rline );
   return( ll );
}


/*
 * Name:    search_forward
 * Purpose: search forward for pattern using boyer array
 * Passed:  ll:     pointer to current node in linked list
 *          rline:  pointer to real line counter
 *          offset: offset into ll->line to begin search
 * Returns: position in file if found or NULL if not found
 * Date:    January 8, 1992
 * Notes:   mini delta2 is the first leftmost occurrence of the rightmost
 *            character.
 */
line_list_ptr search_forward( line_list_ptr ll, long *rline, size_t *offset )
{
register int i;
text_ptr p;
text_ptr q;
int  mini_delta2;
unsigned int  mini_guard;
int  guard;
int  pat_len;
int  len_s;
text_ptr s;
char *skip;
boyer_moore_type *bmp;

   if (ll->len == EOF)
      return( NULL );
   else {
      if (g_status.command == DefineGrep  ||  g_status.command == RepeatGrep)
         bmp = &sas_bm;
      else
         bmp = &bm;

      pat_len  = bmp->pattern_length;
      mini_delta2 = bmp->forward_md2;
      skip = bmp->skip_forward;
      p    = bmp->pattern;

      i = pat_len - 1;
      guard = -i;
      mini_guard = *p;
      if (mode.search_case != MATCH)
         mini_guard = tolower( mini_guard );

      s = ll->line;
      s += *offset;
      len_s = ll->len - *offset;
      for (;;) {
         /*
          * Boyer-Moore fast skip loop.  check character count as we move
          *   down the line.
          */
         for (s+=i, len_s-=i; len_s > 0 && (i = skip[(unsigned char)*s]);
                              s+=i, len_s-=i);
         if (len_s > 0) {
            /*
             * i == 0, possible match.  Boyer-Moore slow match loop.
             */

            if (mode.search_case == MATCH) {
               if (s[guard] != mini_guard)
                  goto shift_func;

               q = s + 1 - pat_len;
               for (i=0; i < pat_len; i++)
                  if (q[i] != p[i])
                     goto shift_func;
            } else {