findrep.c

一个开源著名的TDE编辑器源代码

 *              search_file != window->file_info).
 */
line_list_ptr backward_search( TDE_WIN *window, long *rline, int *rcol )
{
int  i;
int  len;
int  end;
register TDE_WIN *win;  /* put window pointer in a register */
file_infos *file;
line_list_ptr ll;
line_list_ptr (*search_func)( line_list_ptr, long *, int * );

   win  = window;
   file = win->file_info;
   ll   = NULL;
   end  = 0;
   if (g_status.search & SEARCH_BLOCK) {
      if ((g_status.search & SEARCH_BEGIN) ||
          win->rline < file->block_br  ||  win->rline > file->block_er) {
         *rline = file->block_er;
         ll = file->block_end;
         *rcol = ll->len - 1;
         g_status.search |= SEARCH_BEGIN;
      }
      end = file->block_start->prev->len;
      file->block_start->prev->len = EOF;
   } else {
      if (g_status.search & SEARCH_BEGIN) {
         ll = file->line_list_end->prev;
         *rcol = ll->len - 1;
         *rline = file->length;
      }
   }
   if (ll == NULL) {
      *rline = win->rline;
      ll = win->ll;

      /*
       * see if cursor is on EOF line.  if so, move search start to
       * previous node.
       */
      if (ll->next != NULL) {
         i  = win->rcol - 1;
         if (!(g_status.search & SEARCH_REGX))
            i += bm.pattern_length - 1;
         len = ll->len;
         if (i >= len)
            i = len - 1;
      } else {
         ll = ll->prev;
         --*rline;
         i = ll->len - 1;
      }
      *rcol = i;
   }
   search_func = (g_status.search & SEARCH_REGX) ? regx_search_backward :
                                                   search_backward;
   ll = search_func( ll, rline, rcol );

   if (g_status.search & SEARCH_BLOCK)
      file->block_start->prev->len = end;

   if (ll == NULL) {
      if (g_status.search & SEARCH_ALL) {
         do {
            search_file = search_file->prev;
            if (search_file == NULL) {
               search_file = g_status.file_list;
               while (search_file->next != NULL)
                  search_file = search_file->next;
            }
            if (search_file == first_file)
               break;
            if (search_file->file_name[0] == '\0')
               continue;
            ll = search_file->line_list_end->prev;
            *rline = search_file->length;
            *rcol  = ll->len - 1;
            ll = search_func( ll, rline, rcol );
         } while (ll == NULL);
      }

      if (ll == NULL  &&  first_win->rline <= first_file->length  &&
          !(g_status.search & SEARCH_BEGIN)) {

         if (g_status.search & SEARCH_ALL) {
            win = first_win;
            file = first_file;
         }

         if (g_status.search & SEARCH_RESULTS) {
            end = win->ll->len;
            win->ll->len = EOF;

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

         /*
          * haven't found pattern yet - now search from end of file
          */
         g_status.wrapped = TRUE;
         if (g_status.search & SEARCH_BLOCK) {
            ll = file->block_end;
            *rline = file->block_er;
         } else {
            ll = file->line_list_end->prev;
            *rline = file->length;
         }
         *rcol = ll->len - 1;
         ll = search_func( ll, rline, rcol );

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

         if (g_status.search & SEARCH_RESULTS)
            win->ll->len = end;
         else if (win->ll->prev != NULL)
            win->ll->prev->len = end;
      }
   }
   flush_keyboard( );
   g_status.search &= ~SEARCH_BEGIN;

   return( ll );
}


/*
 * 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) {
      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( bm.pattern, bm.pattern_length );

      /*
       * set up for backward search
       */
      build_backward_skip( &bm );
      bm.backward_md2 = calculate_backward_md2( 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( sas_bm.pattern,
                                                  sas_bm.pattern_length );

      /*
       * set up for backward search
       */
      build_backward_skip( &sas_bm );
      sas_bm.backward_md2 = calculate_backward_md2( 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.
 *
 * jmh 030326: use bj_isalpha() and upper_lower[] instead of 'Aa'..'Zz'.
 */
void build_forward_skip( boyer_moore_type *bmp )
{
register text_ptr p;
register int i;
int  c;

   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  &&  bj_isalpha( *p )) {
         c = upper_lower[*p];

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

         bmp->skip_forward[c] = (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.
 *
 * jmh 030326: use bj_isalpha() and upper_lower[] instead of 'Aa'..'Zz'.
 */
void build_backward_skip( boyer_moore_type *bmp )
{
register text_ptr p;
register int i;
int  c;

   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  &&  bj_isalpha( *p )) {
         c = upper_lower[*p];

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

         bmp->skip_backward[c] = (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( text_ptr p, int len )
{
int  last_c;
register int i;
register int md2;

   md2 = 1;
   if (len > 1) {
      i = len - 1;
      last_c = p[i];
      if (mode.search_case == IGNORE) {
         last_c = bj_tolower( last_c );
         while (--i >= 0  &&  last_c != bj_tolower( p[i] ))
            ++md2;
      } else
         while (--i >= 0  &&  last_c != p[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( text_ptr p, int len )
{
int  first_c;
register int i;
register int md2;

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

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

   return( md2 );
}


/*
 * 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.
 *
 * jmh 991007: added block searching.
 */
line_list_ptr search_forward( line_list_ptr ll, long *rline, int *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;
file_infos *file;
int  bc, ec;

   if (ll->next == NULL)
      return( NULL );

   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 = bj_tolower( mini_guard );

   file = g_status.current_file;
   s = ll->line;
   len_s = ll->len;
   if ((g_status.search & SEARCH_BLOCK)  &&
       (file->block_type == BOX  ||
        (file->block_type == STREAM  &&
         (*rline == file->block_br ||
          (*rline == file->block_er && file->block_ec != -1))))) {
      bc = file->block_bc;
      ec = (file->block_ec == -1) ? len_s : file->block_ec;
      if (last_replace_line == *rline) {
         ec += block_replace_offset;
         block_replace_offset = 0;
         last_replace_line = 0;
      }
      if (file->inflate_tabs) {
         bc = entab_adjust_rcol( s, len_s, bc, file->ptab_size );
         if (file->block_ec != -1)
            ec = entab_adjust_rcol( s, len_s, ec, file->ptab_size );
      }
      if (bc > len_s)
         bc = len_s;
      if (ec >= len_s)
         ec = len_s - 1;

      if (file->block_type == STREAM) {
         if (*rline == file->block_br) {
            if (*offset < bc)
               *offset = bc;
         }
         if (*rline == file->block_er) {
            if (*offset > ec)
               return( NULL );
            len_s = ec + 1;
         }
      } else {
         if (*offset < bc)
            *offset = bc;
         len_s = ec + 1;
      }
   }
   s += *offset;