home *** CD-ROM | disk | FTP | other *** search
/ TopWare Tools / TOOLS.iso / tools / top1498 / findrep.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-11-13  |  51.0 KB  |  1,702 lines
  1. /*******************  start of original comments  ********************/
  2. /*
  3.  * Written by Douglas Thomson (1989/1990)
  4.  *
  5.  * This source code is released into the public domain.
  6.  */
  7.  
  8. /*
  9.  * Name:    dte - Doug's Text Editor program - find/replace module
  10.  * Purpose: This file contains the functions relating to finding text
  11.  *           and replacing text.
  12.  *          It also contains the code for moving the cursor to various
  13.  *           other positions in the file.
  14.  * File:    findrep.c
  15.  * Author:  Douglas Thomson
  16.  * System:  this file is intended to be system-independent
  17.  * Date:    October 1, 1989
  18.  */
  19. /*********************  end of original comments   ********************/
  20.  
  21. /*
  22.  * The search and replace routines have been EXTENSIVELY rewritten.  The
  23.  * "brute force" search algorithm has been replaced by the Boyer-Moore
  24.  * string search algorithm.  This search algorithm really speeds up search
  25.  * and replace operations.
  26.  *
  27.  *                  Sketch of the BM pattern matching algorithm:
  28.  *
  29.  *    while (not found) {
  30.  *       fast skip loop;    <===  does most of the work and should be FAST
  31.  *       slow match loop;   <===  standard "brute force" string compare
  32.  *       if (found) then
  33.  *          break;
  34.  *       shift function;    <===  mismatch, shift and go to fast skip loop
  35.  *    }
  36.  *
  37.  * See:
  38.  *
  39.  *   Robert S. Boyer and J Strother Moore, "A fast string searching
  40.  *     algorithm."  _Communications of the ACM_ 20 (No. 10): 762-772, 1977.
  41.  *
  42.  * See also:
  43.  *
  44.  *   Zvi Galil, "On Improving the Worst Case Running Time of the Boyer-
  45.  *    Moore String Matching Algorithm."  _Communications of the ACM_
  46.  *    22 (No. 9): 505-508, 1979.
  47.  *
  48.  *   R. Nigel Horspool, "Practical fast searching in strings." _Software-
  49.  *    Practice and Experience_  10 (No. 3): 501-506, 1980.
  50.  *
  51.  *   Alberto Apostolico and Raffaele Giancarlo, "The Boyer-Moore-Galil
  52.  *    String Searching Strategies Revisited."  _SIAM Journal on Computing_
  53.  *    15 (No. 1): 98-105, 1986.
  54.  *
  55.  *   Andrew Hume and Daniel Sunday, "Fast String Searching."  _Software-
  56.  *    Practice and Experience_ 21 (No. 11): 1221-1248, November 1991.
  57.  *
  58.  *   Timo Raita, "Tuning the Boyer-Moore-Horspool String Searching Algorithm."
  59.  *    _Software-Practice and Experience_ 22 (No. 10): 879-884, October 1992.
  60.  *
  61.  *
  62.  *                            Boyer-Moore in TDE
  63.  *
  64.  * Hume and Sunday demonstrated in their paper that using a simple shift
  65.  * function after a mismatch gives one of the fastest search times with the
  66.  * Boyer-Moore algorithm.  When searching normal text for small patterns
  67.  * (patterns less than 30 characters or so), Hume and Sunday found that the
  68.  * faster the algorithm can get back into the fast skip loop with the
  69.  * largest shift value then the faster the search.  Some algorithms can
  70.  * generate a large shift value, but they can't get back into the skip loop
  71.  * very fast.  Hume and Sunday give a simple method for computing a shift
  72.  * constant that, more often than not, is equal to the length of the search
  73.  * pattern.  They refer to the constant as mini-Sunday delta2 or md2.  From
  74.  * the end of the string, md2 is the first leftmost occurrence of the
  75.  * rightmost character.  Hume and Sunday also found that using a simple string
  76.  * compare as the match function gave better performance than using the C
  77.  * library memcmp( ) function.  The average number of compares in the slow
  78.  * loop was slightly above 1.  Calling the memcmp( ) function to compare 1
  79.  * character slows down the algorithm.  See the Hume and Sunday paper for an
  80.  * excellent discussion on fast string searching.  Incidentally, Hume and
  81.  * Sunday describe an even faster, tuned Boyer-Moore search function.
  82.  *
  83.  * The Boyer-Moore search algorithm in TDE was rearranged so that it is now
  84.  * almost identical to the original version Boyer-Moore described in CACM.
  85.  * The simple shift function in TDE was replaced by the mini-delta2 shift
  86.  * function in the Hume and Sunday paper.
  87.  *
  88.  * I am not very fond of WordStar/TURBO x style search and replace prompting,
  89.  * which is used in the DTE 5.1 editor.  Once the search pattern has been
  90.  * defined, one only needs to press a key to search forwards or backwards.
  91.  * The forward or backward search key may be pressed at any time in any file
  92.  * once the pattern has been entered.  Also, the search case may be toggled
  93.  * at any time in any file once the pattern has been entered.
  94.  *
  95.  * Thanks to Tom Waters, twaters@relay.nswc.navy.mil, for finding a bug when
  96.  * building the ignore skip index array in TDE 1.3 and previous versions.
  97.  * BTW, I added assertions to those functions that build the skip index
  98.  * array to make certain that everything is everything.
  99.  *
  100.  * Thanks also to David Merrill, u09606@uicvm.uic.edu, for recommending a
  101.  * change and the source code for the solution to what can be an annoying
  102.  * feature in the find function.  Pressing <FindForward> before defining
  103.  * the pattern would cause TDE to display an error message.  Since we already
  104.  * know that the search pattern is undefined, we can easily prompt for
  105.  * the search pattern.  I usually tolerate such features until I get tired
  106.  * of being annoyed with error messages and finally write a solution.
  107.  * Dave, thanks for the solution and the easy-to-implement code.  Although
  108.  * such changes are small, they really make for a more comfortable editor.
  109.  *
  110.  * New editor name:  TDE, the Thomson-Davis Editor.
  111.  * Author:           Frank Davis
  112.  * Date:             June 5, 1991, version 1.0
  113.  * Date:             July 29, 1991, version 1.1
  114.  * Date:             October 5, 1991, version 1.2
  115.  * Date:             January 20, 1992, version 1.3
  116.  * Date:             February 17, 1992, version 1.4
  117.  * Date:             April 1, 1992, version 1.5
  118.  * Date:             June 5, 1992, version 2.0
  119.  * Date:             October 31, 1992, version 2.1
  120.  * Date:             April 1, 1993, version 2.2
  121.  * Date:             June 5, 1993, version 3.0
  122.  * Date:             August 29, 1993, version 3.1
  123.  * Date:             November 13, 1993, version 3.2
  124.  *
  125.  * This modification of Douglas Thomson's code is released into the
  126.  * public domain, Frank Davis.   You may distribute it freely.
  127.  */
  128.  
  129. #include "tdestr.h"
  130. #include "common.h"
  131. #include "tdefunc.h"
  132. #include "define.h"
  133.  
  134.  
  135. /*
  136.  * Name:     get_replacement_flags
  137.  * Purpose:  To input find and replace flags.
  138.  * Date:     June 5, 1991
  139.  * Modified: November 13, 1993, Frank Davis per Byrial Jensen
  140.  * Passed:   line:  prompt line
  141.  * Returns:  OK if flags were entered, ERROR if user wanted to abort
  142.  */
  143. int  get_replacement_flags( int line )
  144. {
  145. register int c;
  146. int  func;
  147. int  rc;
  148. #if defined( __UNIX__ )
  149.  chtype display_buff[MAX_COLS+2];       /* chtype is defined in curses.h */
  150. #else
  151.  char display_buff[(MAX_COLS+2)*2];
  152. #endif
  153.  
  154.    save_screen_line( 0, line, display_buff );
  155.    eol_clear( 0, line, g_display.text_color );
  156.    /*
  157.     * options: prompt or no prompt (p/n)?
  158.     */
  159.    s_output( find1, line, 0, g_display.message_color );
  160.    xygoto( strlen( find1 ) + 2, line );
  161.    do {
  162.       c = getanswerkey( );
  163.       func = getfunc( c );
  164.    } while (c != L_PROMPT  &&  c != L_NO_PROMPT  &&
  165.             c != RTURN  &&  c != ESC  &&  func != AbortCommand);
  166.    restore_screen_line( 0, line, display_buff );
  167.    switch (c) {
  168.       case L_PROMPT :
  169.       case RTURN :
  170.          g_status.replace_flag = PROMPT;
  171.          rc = OK;
  172.          break;
  173.       case L_NO_PROMPT :
  174.          g_status.replace_flag = NOPROMPT;
  175.          rc = OK;
  176.          break;
  177.       default :
  178.          rc = ERROR;
  179.    }
  180.    bm.search_defined = rc;
  181.    return( rc );
  182. }
  183.  
  184.  
  185. /*
  186.  * Name:     ask_replace
  187.  * Purpose:  Ask user if he wants to (r)place, (s)kip, or (e)xit.
  188.  * Date:     June 5, 1991
  189.  * Modified: November 13, 1993, Frank Davis per Byrial Jensen
  190.  * Returns:  TRUE if user wants to replace, ERROR otherwise.
  191.  * Passed:   window:   pointer to current window
  192.  *           finished: TRUE if user pressed ESC or (e)xit.
  193.  */
  194. int  ask_replace( TDE_WIN *window, int *finished )
  195. {
  196. register int c;
  197. int  func;
  198. int  prompt_line;
  199. int  rc;
  200. #if defined( __UNIX__ )
  201.  chtype display_buff[MAX_COLS+2];       /* chtype is defined in curses.h */
  202. #else
  203.  char display_buff[(MAX_COLS+2)*2];
  204. #endif
  205.  
  206.    prompt_line = window->cline - 1;
  207.    c = 39 - (strlen( find2 ) >> 1);
  208.    save_screen_line( 0, prompt_line, display_buff );
  209.    /*
  210.     * replace skip exit (r/s/e)?
  211.     */
  212.    s_output( find2, prompt_line, c, g_display.message_color );
  213.    do {
  214.       c = getanswerkey( );
  215.       func = getfunc( c );
  216.    } while (c != L_REPLACE  && c != L_SKIP  &&  c != L_EXIT
  217.           && c != ESC  &&  func != AbortCommand);
  218.    restore_screen_line( 0, prompt_line, display_buff );
  219.    switch (c) {
  220.       case L_REPLACE :
  221.          rc = OK;
  222.          break;
  223.       case L_EXIT :
  224.          *finished = TRUE;
  225.       case L_SKIP :
  226.       case 's' :
  227.          rc = ERROR;
  228.          break;
  229.       default :
  230.          *finished = TRUE;
  231.          rc = ERROR;
  232.          break;
  233.    }
  234.    return( rc );
  235. }
  236.  
  237.  
  238. /*
  239.  * Name:     ask_wrap_replace
  240.  * Purpose:  After a wrap, ask user if he wants to (q)uit or (c)ontine.
  241.  * Date:     June 5, 1991
  242.  * Modified: November 13, 1993, Frank Davis per Byrial Jensen
  243.  * Returns:  TRUE if user wants to continue, ERROR otherwise.
  244.  * Passed:   window:   pointer to current window
  245.  *           finished: TRUE if user pressed ESC or (q)uit.
  246.  */
  247. int  ask_wrap_replace( TDE_WIN *window, int *finished )
  248. {
  249. register int c;
  250. int  func;
  251. int  prompt_line;
  252. int  rc;
  253. #if defined( __UNIX__ )
  254.  chtype display_buff[MAX_COLS+2];       /* chtype is defined in curses.h */
  255. #else
  256.  char display_buff[(MAX_COLS+2)*2];
  257. #endif
  258.  
  259.    prompt_line = window->bottom_line;
  260.    save_screen_line( 0, prompt_line, display_buff );
  261.    /*
  262.     * search has wrapped. continue or quit (c/q)?
  263.     */
  264.    set_prompt( find3, prompt_line );
  265.    do {
  266.       c = getanswerkey( );
  267.       func = getfunc( c );
  268.    } while (c != L_QUIT  &&  c != L_CONTINUE  &&
  269.           c != ESC  &&  func != AbortCommand);
  270.    restore_screen_line( 0, prompt_line, display_buff );
  271.    switch (c) {
  272.       case L_CONTINUE :
  273.          rc = OK;
  274.          break;
  275.       case L_QUIT :
  276.       default :
  277.          *finished = TRUE;
  278.          rc = ERROR;
  279.          break;
  280.    }
  281.    return( rc );
  282. }
  283.  
  284.  
  285. /*
  286.  * Name:    do_replace
  287.  * Purpose: To replace text once match has been found.
  288.  * Date:    June 5, 1991
  289.  * Passed:  window:     pointer to current window
  290.  *          direction:  direction of search
  291.  */
  292. void do_replace( TDE_WIN *window, int direction )
  293. {
  294. int  old_len;           /* length of original text */
  295. int  new_len;           /* length of replacement text */
  296. int  rcol;
  297. register int net_change;
  298. char *source;           /* source of block move */
  299. char *dest;             /* destination of block move */
  300.  
  301.    old_len = strlen( g_status.pattern );
  302.    new_len = strlen( g_status.subst );
  303.    net_change = new_len - old_len;
  304.    rcol = window->rcol;
  305.  
  306.    /*
  307.     * move the text to either make room for the extra replacement text
  308.     *  or to close up the gap left
  309.     */
  310.  
  311.    g_status.copied = FALSE;
  312.    copy_line( window->ll );
  313.    detab_linebuff( );
  314.  
  315.    if (net_change != 0) {
  316.       assert( rcol + old_len >= 0);
  317.       assert( net_change <= rcol + old_len );
  318.  
  319.       source = g_status.line_buff + rcol + old_len;
  320.       dest  = source + net_change;
  321.  
  322.       assert( g_status.line_buff_len - rcol - old_len >= 0 );
  323.       assert( g_status.line_buff_len - rcol - old_len < MAX_LINE_LENGTH );
  324.  
  325.       memmove( dest, source, g_status.line_buff_len - rcol - old_len );
  326.       g_status.line_buff_len += net_change;
  327.    }
  328.  
  329.    /*
  330.     * insert the replacement text
  331.     */
  332.  
  333.    assert( rcol >= 0 );
  334.    assert( rcol < MAX_LINE_LENGTH );
  335.    assert( g_status.line_buff_len >= 0 );
  336.    assert( g_status.line_buff_len >= rcol );
  337.  
  338.    for (dest=g_status.line_buff+rcol, source=g_status.subst; *source;)
  339.       *dest++ = *source++;
  340.  
  341.    entab_linebuff( );
  342.    window->file_info->modified = TRUE;
  343.    un_copy_line( window->ll, window, TRUE );
  344.    window->ll->dirty = TRUE;
  345.  
  346.    if (direction == FORWARD)
  347.       window->rcol += (new_len - 1);
  348.  
  349.    assert( window->rcol >= 0 );
  350.    show_avail_mem( );
  351. }
  352.  
  353.  
  354. /*
  355.  * Name:    find_string
  356.  * Purpose: To set up and perform a find operation.
  357.  * Date:    June 5, 1991
  358.  * Passed:  window:  pointer to current window
  359.  * Notes:   Keep the search string and boyer-moore stuff until changed.
  360.  */
  361. int  find_string( TDE_WIN *window )
  362. {
  363. int  direction;
  364. int  new_string;
  365. long found_line;
  366. long bin_offset;
  367. line_list_ptr ll;
  368. register TDE_WIN *win;  /* put window pointer in a register */
  369. int  rc;
  370. int  old_rcol;
  371. int  rcol;
  372. char answer[MAX_COLS+2];
  373.  
  374.    switch (g_status.command) {
  375.       case FindForward :
  376.          direction = FORWARD;
  377.          new_string = TRUE;
  378.          break;
  379.       case FindBackward :
  380.          direction = BACKWARD;
  381.          new_string = TRUE;
  382.          break;
  383.       case RepeatFindForward1 :
  384.       case RepeatFindForward2 :
  385.          direction = FORWARD;
  386.          new_string =  bm.search_defined != OK ? TRUE : FALSE;
  387.          break;
  388.       case RepeatFindBackward1 :
  389.       case RepeatFindBackward2 :
  390.          direction = BACKWARD;
  391.          new_string =  bm.search_defined != OK ? TRUE : FALSE;
  392.          break;
  393.       default :
  394.          direction = 0;
  395.          new_string = 0;
  396.          assert( FALSE );
  397.          break;
  398.    }
  399.    win = window;
  400.    entab_linebuff( );
  401.    if (un_copy_line( win->ll, win, TRUE ) == ERROR)
  402.       return( ERROR );
  403.  
  404.    /*
  405.     * get search text, using previous as default
  406.     */
  407.    if (new_string == TRUE) {
  408.       *answer = '\0';
  409.       if (bm.search_defined == OK) {
  410.  
  411.          assert( strlen( (char *)bm.pattern ) < (size_t)g_display.ncols );
  412.  
  413.          strcpy( answer, (char *)bm.pattern );
  414.       }
  415.  
  416.       /*
  417.        * string to find:
  418.        */
  419.       if (get_name( find4, win->bottom_line, answer,
  420.                  g_display.message_color ) != OK  ||  *answer == '\0')
  421.          return( ERROR );
  422.       bm.search_defined = OK;
  423.  
  424.       assert( strlen( answer ) < (size_t)g_display.ncols );
  425.  
  426.       strcpy( (char *)bm.pattern, answer );
  427.       build_boyer_array( );
  428.    }
  429.  
  430.    rc = OK;
  431.    if (bm.search_defined == OK) {
  432.       old_rcol = win->rcol;
  433.       if (mode.inflate_tabs)
  434.          win->rcol = entab_adjust_rcol( win->ll->line, win->ll->len, win->rcol);
  435.       update_line( win );
  436.       show_search_message( SEARCHING, g_display.diag_color );
  437.  
  438. #if defined( __UNIX__ )
  439.       refresh( );
  440. #endif
  441.  
  442.       bin_offset = win->bin_offset;
  443.       if (direction == FORWARD) {
  444.          if ((ll = forward_boyer_moore_search( win, &found_line, &rcol )) != NULL) {
  445.             if (g_status.wrapped && g_status.macro_executing)
  446.                rc = ask_wrap_replace( win, &new_string );
  447.             if (rc == OK)
  448.                find_adjust( win, ll, found_line, rcol );
  449.             else
  450.                win->bin_offset = bin_offset;
  451.          }
  452.       } else {
  453.          if ((ll = backward_boyer_moore_search( win, &found_line, &rcol )) != NULL) {
  454.             if (g_status.wrapped && g_status.macro_executing)
  455.                rc = ask_wrap_replace( win, &new_string );
  456.             if (rc == OK)
  457.                find_adjust( win, ll, found_line, rcol );
  458.             else
  459.                win->bin_offset = bin_offset;
  460.          }
  461.       }
  462.       if (g_status.wrapped)
  463.          show_search_message( WRAPPED, g_display.diag_color );
  464.       else
  465.          show_search_message( CLR_SEARCH, g_display.mode_color );
  466.  
  467. #if defined( __UNIX__ )
  468.       refresh( );
  469. #endif
  470.  
  471.       if (ll == NULL) {
  472.          /*
  473.           * string not found
  474.           */
  475.          if (mode.inflate_tabs)
  476.             win->rcol = old_rcol;
  477.          combine_strings( answer, find5a, (char *)bm.pattern, find5b );
  478.          error( WARNING, win->bottom_line, answer );
  479.          rc = ERROR;
  480.       }
  481.       show_curl_line( win );
  482.       make_ruler( win );
  483.       show_ruler( win );
  484.    } else {
  485.       /*
  486.        * find pattern not defined
  487.        */
  488.       error( WARNING, win->bottom_line, find6 );
  489.       rc = ERROR;
  490.    }
  491.    return( rc );
  492. }
  493.  
  494.  
  495. /*
  496.  * Name:    build_boyer_array
  497.  * Purpose: To set up the boyer array for forward and backward searches.
  498.  * Date:    June 5, 1991
  499.  * Notes:   Set up one array for forward searches and another for backward
  500.  *          searches.  If user decides to ignore case then fill in array
  501.  *          with reverse case characters so both upper and lower case
  502.  *          characters are defined.
  503.  */
  504. void build_boyer_array( void )
  505. {
  506.  
  507.    /*
  508.     * set up for forward search
  509.     */
  510.    if (g_status.command == DefineGrep  ||  g_status.command == RepeatGrep) {
  511.  
  512.       assert( strlen( (char *)sas_bm.pattern ) + 1 < (size_t)g_display.ncols );
  513.  
  514.       memcpy( bm.pattern, sas_bm.pattern, strlen( (char *)sas_bm.pattern ) +1 );
  515.       bm.search_defined = OK;
  516.    }
  517.  
  518.    if (bm.search_defined == OK) {
  519.       build_forward_skip( &bm );
  520.       bm.forward_md2 = calculate_forward_md2( (char *)bm.pattern,
  521.                                                 bm.pattern_length );
  522.  
  523.       /*
  524.        * set up for backward search
  525.        */
  526.       build_backward_skip( &bm );
  527.       bm.backward_md2 = calculate_backward_md2( (char *)bm.pattern,
  528.                                                   bm.pattern_length );
  529.    }
  530.  
  531.  
  532.    /*
  533.     * build an array for search and seize.
  534.     */
  535.    if (sas_bm.search_defined == OK) {
  536.       build_forward_skip( &sas_bm );
  537.       sas_bm.forward_md2 = calculate_forward_md2( (char *)sas_bm.pattern,
  538.                                                     sas_bm.pattern_length );
  539.  
  540.       /*
  541.        * set up for backward search
  542.        */
  543.       build_backward_skip( &sas_bm );
  544.       sas_bm.backward_md2 = calculate_backward_md2( (char *)sas_bm.pattern,
  545.                                                       sas_bm.pattern_length );
  546.    }
  547. }
  548.  
  549.  
  550. /*
  551.  * Name:    build_forward_skip
  552.  * Purpose: build Boyer-Moore forward skip array
  553.  * Date:    October 31, 1992
  554.  * Passed:  bmp:  pointer to Boyer-Moore structure
  555.  * Notes:   build standard Boyer-Moore forward skip array.
  556.  *          Thanks to Tom Waters, twaters@relay.nswc.navy.mil, for finding a
  557.  *           bug in TDE 1.3 when building the ignore skip index array.
  558.  */
  559. void build_forward_skip( boyer_moore_type *bmp )
  560. {
  561. register unsigned char *p;
  562. register int i;
  563.  
  564.    assert( strlen( (char *)bmp->pattern ) < (size_t)g_display.ncols );
  565.  
  566.    i = bmp->pattern_length = (int)strlen( (char *)bmp->pattern );
  567.  
  568.    /*
  569.     * set skip index of all characters to length of string
  570.     */
  571.    memset( bmp->skip_forward, i, 256 );
  572.    i--;
  573.  
  574.    /*
  575.     * for each character in string, set the skip index
  576.     */
  577.    for (p=bmp->pattern; i>=0; i--, p++) {
  578.  
  579.       assert( (char)i < bmp->skip_forward[*p] );
  580.  
  581.       bmp->skip_forward[*p] = (char)i;
  582.       if (mode.search_case == IGNORE) {
  583.          if (*p >= 'A' && *p <= 'Z') {
  584.  
  585.             assert( (char)i < bmp->skip_forward[*p+32] );
  586.  
  587.             bmp->skip_forward[*p+32] = (char)i;
  588.          } else if (*p >= 'a' && *p <= 'z') {
  589.  
  590.             assert( (char)i < bmp->skip_forward[*p-32] );
  591.  
  592.             bmp->skip_forward[*p-32] = (char)i;
  593.          }
  594.       }
  595.    }
  596. }
  597.  
  598.  
  599. /*
  600.  * Name:    build_backward_skip
  601.  * Purpose: build Boyer-Moore backward skip array
  602.  * Date:    October 31, 1992
  603.  * Passed:  bmp:  pointer to Boyer-Moore structure
  604.  * Notes:   build standard Boyer-Moore backward skip array.
  605.  *          Thanks to Tom Waters, twaters@relay.nswc.navy.mil, for finding a
  606.  *           bug in TDE 1.3 when building the ignore skip index array.
  607.  */
  608. void build_backward_skip( boyer_moore_type *bmp )
  609. {
  610. register unsigned char *p;
  611. register int i;
  612.  
  613.    i = -bmp->pattern_length;
  614.    memset( bmp->skip_backward, i, 256 );
  615.    i++;
  616.    for (p=bmp->pattern + bmp->pattern_length - 1; i<=0; i++, p--) {
  617.  
  618.       assert( (char)i > bmp->skip_backward[*p] );
  619.  
  620.       bmp->skip_backward[*p] = (char)i;
  621.       if (mode.search_case == IGNORE) {
  622.          if (*p >= 'A' && *p <= 'Z') {
  623.  
  624.             assert( (char)i > bmp->skip_backward[*p+32] );
  625.  
  626.             bmp->skip_backward[*p+32] = (char)i;
  627.          } else if (*p >= 'a' && *p <= 'z') {
  628.  
  629.             assert( (char)i > bmp->skip_backward[*p-32] );
  630.  
  631.             bmp->skip_backward[*p-32] = (char)i;
  632.          }
  633.       }
  634.    }
  635. }
  636.  
  637.  
  638. /*
  639.  * Name:    calculate_forward_md2
  640.  * Purpose: Calculate mini delta2 for forward searches
  641.  * Date:    October 31, 1992
  642.  * Passed:  p:  pointer to pattern
  643.  *          len: length of pattern
  644.  * Notes:   Hume and Sunday (see above) demonstrate in their paper that
  645.  *            using a simple shift function on mismatches with BM
  646.  *            gives one of the fastest run times for general text searching.
  647.  *          mini delta2 is, from the end of the string, the first leftmost
  648.  *            occurrence of the rightmost character.  mini delta2 is 1 in
  649.  *            the worst case.  in previous versions of TDE, the shift function
  650.  *            was hard-coded as 1 -- the worst case.  typically, mini delta2
  651.  *            will be the length of the search pattern.
  652.  */
  653. int  calculate_forward_md2( char *p, int len )
  654. {
  655. int  last_c;
  656. register int i;
  657. register int md2;
  658.  
  659.    md2 = 1;
  660.    i = len - 1;
  661.    last_c = p[i];
  662.    if (mode.search_case == IGNORE) {
  663.       last_c = tolower( last_c );
  664.       for (i--; i >= 0  &&  last_c != tolower( p[i] ); i--)
  665.          ++md2;
  666.    } else
  667.       for (i--; i >= 0  &&  last_c != p[i]; i--)
  668.          ++md2;
  669.  
  670.    assert( md2 >= 1  &&  md2 <= len );
  671.  
  672.    return( md2 );
  673. }
  674.  
  675.  
  676. /*
  677.  * Name:    calculate_backward_md2
  678.  * Purpose: Calculate mini delta2 for backward searches
  679.  * Date:    October 31, 1992
  680.  * Passed:  p:  pointer to pattern
  681.  *          len: length of pattern
  682.  * Notes:   the backward mini delta2 is, from the start of the string, the
  683.  *            first rightmost occurrence of the leftmost character.  in the
  684.  *            worst case, mini delta2 is -1.  typically, mini delta2 is the
  685.  *            negative length of the search pattern.
  686.  */
  687. int  calculate_backward_md2( char *p, int len )
  688. {
  689. int  first_c;
  690. register int i;
  691. register int md2;
  692.  
  693.    md2 = -1;
  694.    i = 1;
  695.    first_c = *p;
  696.    if (mode.search_case == IGNORE) {
  697.       first_c = tolower( first_c );
  698.       for (; i < len  &&  first_c != tolower( p[i] ); i++)
  699.          --md2;
  700.    } else
  701.       for (; i < len  &&  first_c != p[i]; i++)
  702.          --md2;
  703.  
  704.    assert( md2 <= -1  &&  md2 >= -len );
  705.  
  706.    return( md2 );
  707. }
  708.  
  709.  
  710. /*
  711.  * Name:    forward_boyer_moore_search
  712.  * Purpose: search forward for pattern using boyer array
  713.  * Passed:  window:  pointer to current window
  714.  *          rline:   pointer to real line counter
  715.  *          rcol:    pointer to real column variable
  716.  * Returns: position in file if found or NULL if not found
  717.  * Date:    June 5, 1991
  718.  * Notes:   Start searching from cursor position to end of file.  If we hit
  719.  *          end of file without a match, start searching from the beginning
  720.  *          of file to cursor position.  (do wrapped searches)
  721.  */
  722. line_list_ptr forward_boyer_moore_search( TDE_WIN *window, long *rline,
  723.      int *rcol )
  724. {
  725. register int len;
  726. int  i;
  727. int  end;
  728. register TDE_WIN *win;  /* put window pointer in a register */
  729. line_list_ptr ll;
  730.  
  731.    /*
  732.     * if cursor is beyond end of line then start at end of line
  733.     */
  734.    win  = window;
  735.    i = win->rcol + 1;
  736.    len = win->ll->len;
  737.    if (i > len)
  738.       i = len;
  739.    if (i < 0)
  740.       i = 0;
  741.  
  742.  
  743.    *rcol = i;
  744.  
  745.    assert( *rcol >= 0 );
  746.  
  747.    *rline = win->rline;
  748.    ll = search_forward( win->ll, rline, (size_t *)rcol );
  749.  
  750.    if (ll == NULL) {
  751.  
  752.       end = 0;
  753.       if (win->ll->next != NULL) {
  754.          end = win->ll->next->len;
  755.          win->ll->next->len = EOF;
  756.       }
  757.  
  758.       /*
  759.        * haven't found pattern yet - now search from beginning of file
  760.        */
  761.       g_status.wrapped = TRUE;
  762.  
  763.       *rcol = 0;
  764.       *rline = 1L;
  765.       ll = search_forward( win->file_info->line_list, rline, (size_t *)rcol );
  766.  
  767.       if (ll == win->ll  &&  *rcol >= win->rcol)
  768.          ll = NULL;
  769.  
  770.       if (win->ll->next != NULL)
  771.          win->ll->next->len = end;
  772.    }
  773.  
  774.    if (ll != NULL)
  775.       bin_offset_adjust( win, *rline );
  776.    return( ll );
  777. }
  778.  
  779.  
  780. /*
  781.  * Name:    search_forward
  782.  * Purpose: search forward for pattern using boyer array
  783.  * Passed:  ll:     pointer to current node in linked list
  784.  *          rline:  pointer to real line counter
  785.  *          offset: offset into ll->line to begin search
  786.  * Returns: position in file if found or NULL if not found
  787.  * Date:    January 8, 1992
  788.  * Notes:   mini delta2 is the first leftmost occurrence of the rightmost
  789.  *            character.
  790.  */
  791. line_list_ptr search_forward( line_list_ptr ll, long *rline, size_t *offset )
  792. {
  793. register int i;
  794. text_ptr p;
  795. text_ptr q;
  796. int  mini_delta2;
  797. unsigned int  mini_guard;
  798. int  guard;
  799. int  pat_len;
  800. int  len_s;
  801. text_ptr s;
  802. char *skip;
  803. boyer_moore_type *bmp;
  804.  
  805.    if (ll->len == EOF)
  806.       return( NULL );
  807.    else {
  808.       if (g_status.command == DefineGrep  ||  g_status.command == RepeatGrep)
  809.          bmp = &sas_bm;
  810.       else
  811.          bmp = &bm;
  812.  
  813.       pat_len  = bmp->pattern_length;
  814.       mini_delta2 = bmp->forward_md2;
  815.       skip = bmp->skip_forward;
  816.       p    = bmp->pattern;
  817.  
  818.       i = pat_len - 1;
  819.       guard = -i;
  820.       mini_guard = *p;
  821.       if (mode.search_case != MATCH)
  822.          mini_guard = tolower( mini_guard );
  823.  
  824.       s = ll->line;
  825.       s += *offset;
  826.       len_s = ll->len - *offset;
  827.       for (;;) {
  828.          /*
  829.           * Boyer-Moore fast skip loop.  check character count as we move
  830.           *   down the line.
  831.           */
  832.          for (s+=i, len_s-=i; len_s > 0 && (i = skip[(unsigned char)*s]);
  833.                               s+=i, len_s-=i);
  834.          if (len_s > 0) {
  835.             /*
  836.              * i == 0, possible match.  Boyer-Moore slow match loop.
  837.              */
  838.  
  839.             if (mode.search_case == MATCH) {
  840.                if (s[guard] != mini_guard)
  841.                   goto shift_func;
  842.  
  843.                q = s + 1 - pat_len;
  844.                for (i=0; i < pat_len; i++)
  845.                   if (q[i] != p[i])
  846.                      goto shift_func;
  847.             } else {
  848.                if ((unsigned int)tolower( s[guard] ) != mini_guard)
  849.                   goto shift_func;
  850.  
  851.                q = s + 1 - pat_len;
  852.                for (i=0; i < pat_len; i++)
  853.                   if (tolower( q[i] ) != tolower( p[i] ))
  854.                      goto shift_func;
  855.             }
  856.             *offset = (size_t)(q - ll->line);
  857.  
  858.             assert( *offset <= (unsigned)(ll->len - pat_len) );
  859.  
  860.             return( ll );
  861.          }
  862. shift_func:
  863.          if (len_s <= 0) {
  864.             ++*rline;
  865.             ll = ll->next;
  866.             s = ll->line;
  867.             if (ll->len == EOF)
  868.                return( NULL );
  869.             len_s = ll->len;
  870.             i = pat_len - 1;
  871.          } else
  872.             i = mini_delta2;
  873.       }
  874.    }
  875. }
  876.  
  877.  
  878. /*
  879.  * Name:    backward_boyer_moore_search
  880.  * Purpose: search backward for pattern using boyer array
  881.  * Passed:  window:  pointer to current window
  882.  *          rline:   pointer current real line counter
  883.  *          rcol:    pointer to real column
  884.  * Returns: position in file if found or NULL if not found
  885.  * Date:    June 5, 1991
  886.  * Notes:   Start searching from cursor position to beginning of file. If we
  887.  *          hit beginning end of file without a match, start searching from the
  888.  *          end of file to cursor position.  (do wrapped searches)
  889.  */
  890. line_list_ptr backward_boyer_moore_search( TDE_WIN *window, long *rline, int *rcol )
  891. {
  892. int  i;
  893. int  len;
  894. int  end;
  895. register TDE_WIN *win;  /* put window pointer in a register */
  896. line_list_ptr ll;
  897.  
  898.    win  = window;
  899.    *rline = win->rline;
  900.  
  901.    /*
  902.     * see if cursor is on EOF line.  if so, move search start to previous node.
  903.     */
  904.    if (win->ll->len != EOF) {
  905.       ll = win->ll;
  906.       i  = win->rcol - 1;
  907.       i += bm.pattern_length - 1;
  908.       len = ll->len;
  909.       if (i >= len)
  910.          i = len - 1;
  911.    } else {
  912.       ll = win->ll->prev;
  913.       --*rline;
  914.       i = 0;
  915.       if (ll != NULL)
  916.          i = ll->len - 1;
  917.    }
  918.    *rcol = i;
  919.    ll = search_backward( ll, rline, (size_t *)rcol );
  920.  
  921.    if (ll == NULL  &&  win->rline <= win->file_info->length) {
  922.  
  923.       end = 0;
  924.       if (win->ll->prev != NULL) {
  925.          end = win->ll->prev->len;
  926.          win->ll->prev->len = EOF;
  927.       }
  928.  
  929.       /*
  930.        * haven't found pattern yet - now search from end of file
  931.        */
  932.       g_status.wrapped = TRUE;
  933.       ll = win->file_info->line_list_end;
  934.       if (ll->prev != NULL)
  935.          *rcol = ll->prev->len;
  936.       else
  937.         *rcol = 0;
  938.       *rline = win->file_info->length;
  939.       ll = search_backward( ll->prev, rline, (size_t *)rcol );
  940.  
  941.       if (ll == win->ll  &&  *rcol <= win->rcol)
  942.          ll = NULL;
  943.  
  944.       if (win->ll->prev != NULL)
  945.          win->ll->prev->len = end;
  946.    }
  947.    if (ll != NULL)
  948.       bin_offset_adjust( win, *rline );
  949.    return( ll );
  950. }
  951.  
  952.  
  953. /*
  954.  * Name:    search_backward
  955.  * Purpose: search backward for pattern using boyer array
  956.  * Passed:  ll:  pointer to node in linked list to start search
  957.  *          rline:  pointer to real line counter
  958.  *          offset:  offset into ll->line to start search
  959.  * Returns: position in file if found else return NULL
  960.  * Date:    January 8, 1992
  961.  * Notes:   Start searching from cursor position to beginning of file.
  962.  *          mini delta2 is the first rightmost occurrence of the leftmost character.
  963.  */
  964. line_list_ptr search_backward( line_list_ptr ll, long *rline, size_t *offset )
  965. {
  966. register int i;
  967. text_ptr p;
  968. int  mini_delta2;
  969. int  pat_len;
  970. int  len_s;
  971. text_ptr s;
  972.  
  973.    if (ll == NULL)
  974.       return( NULL );
  975.    if (ll->len == EOF)
  976.       return( NULL );
  977.    else {
  978.       mini_delta2 = bm.backward_md2;
  979.       pat_len  = bm.pattern_length;
  980.       p = bm.pattern;
  981.  
  982.       i = -bm.pattern_length + 1;
  983.  
  984.       s = ll->line;
  985.       s += *offset;
  986.       len_s = *offset + 1;
  987.       for (;;) {
  988.  
  989.          /*
  990.           * Boyer-Moore fast skip loop.  check character count as we move
  991.           *   up the line.
  992.           */
  993.          for (s+=i, len_s+=i; len_s > 0 &&
  994.                  (i = bm.skip_backward[(unsigned char)*s]); s+=i, len_s+=i);
  995.          if (len_s > 0) {
  996.             /*
  997.              * i == 0, possible match.  Boyer-Moore slow match loop.
  998.              */
  999.             if (mode.search_case == MATCH) {
  1000.                for (i=0; i < pat_len; i++)
  1001.                   if (s[i] != p[i])
  1002.                     goto shift_func;
  1003.             } else {
  1004.                for (i=0; i < pat_len; i++)
  1005.                   if (tolower( s[i] ) != tolower( p[i] ))
  1006.                      goto shift_func;
  1007.             }
  1008.             *offset =(size_t)(s - ll->line);
  1009.  
  1010.             assert( *offset <= (unsigned)(ll->len - pat_len) );
  1011.  
  1012.             return( ll );
  1013.          }
  1014. shift_func:
  1015.          if (len_s <= 0) {
  1016.             --*rline;
  1017.             ll = ll->prev;
  1018.             if (ll == NULL)
  1019.                return( NULL );
  1020.             if (ll->len == EOF)
  1021.                return( NULL );
  1022.             len_s = ll->len;
  1023.             s = ll->line + len_s - 1;
  1024.             i = 1 - pat_len;
  1025.          } else
  1026.             i = mini_delta2;
  1027.       }
  1028.    }
  1029. }
  1030.  
  1031.  
  1032. /*
  1033.  * Name:    show_search_message
  1034.  * Purpose: display search status
  1035.  * Date:    January 8, 1992
  1036.  * Passed:  i:     index into message array
  1037.  *          color: color to display message
  1038.  */
  1039. void show_search_message( int i, int color )
  1040. {
  1041.    /*
  1042.     *  0 = blank
  1043.     *  1 = wrapped...
  1044.     *  2 = searching
  1045.     *  3 = replacing
  1046.     *  4 = nfa choked
  1047.     */
  1048.    assert( i >= 0  &&  i <= 4);
  1049.    s_output( find7[i], g_display.mode_line, 67, color );
  1050. }
  1051.  
  1052.  
  1053. /*
  1054.  * Name:    bin_offset_adjust
  1055.  * Purpose: place cursor on screen given a position in file - default cline
  1056.  * Date:    June 5, 1991
  1057.  * Passed:  window:  pointer to current window
  1058.  *          rline:   real line position some where in the file
  1059.  * Notes:   in binary mode, we keep an accurate count of the offset of the
  1060.  *          cursor from the beginning of the file.
  1061.  */
  1062. void bin_offset_adjust( TDE_WIN *window, long rline )
  1063. {
  1064. line_list_ptr   node;
  1065. long            found_distance;
  1066.  
  1067.    assert( rline >= 1L  &&  rline <= window->file_info->length );
  1068.  
  1069.    found_distance = window->rline - rline;
  1070.    node = window->ll;
  1071.    if (found_distance < 0) {
  1072.       while (found_distance++ < 0) {
  1073.          window->bin_offset += node->len;
  1074.          node = node->next;
  1075.       }
  1076.    } else if (found_distance > 0) {
  1077.       while (found_distance-- > 0) {
  1078.          node = node->prev;
  1079.          window->bin_offset -= node->len;
  1080.       }
  1081.    }
  1082.    assert( window->bin_offset >= 0 );
  1083. }
  1084.  
  1085.  
  1086. /*
  1087.  * Name:    find_adjust
  1088.  * Purpose: place cursor on screen given a position in file - default cline
  1089.  * Date:    June 5, 1991
  1090.  * Passed:  window:  pointer to current window
  1091.  *          ll:   position anywhere in file
  1092.  *          rline:  real line number of ll in the file
  1093.  *          rcol:   real column of ll in the file
  1094.  * Notes:   ll could be anywhere in file.  Find the start of line that
  1095.  *          ll is on.  Determine if start of line is behind or ahead of
  1096.  *          current line.  Once that is done, it is easy to determine if ll
  1097.  *          is on screen.  Lastly, current cursor position becomes start of
  1098.  *          ll line - reposition and display.
  1099.  */
  1100. void find_adjust( TDE_WIN *window, line_list_ptr ll, long rline, int rcol )
  1101. {
  1102. int  cmd;
  1103. long test_line;
  1104. file_infos *file;
  1105. register TDE_WIN *win;  /* put window pointer in a register */
  1106.  
  1107.    win = window;
  1108.    file = win->file_info;
  1109.  
  1110.    /*
  1111.     * given a real column, adjust for inflated tabs.
  1112.     */
  1113.    if (mode.inflate_tabs)
  1114.       rcol = detab_adjust_rcol( ll->line, rcol );
  1115.  
  1116.    /*
  1117.     * if p, start of found line, is greater than current line, see if
  1118.     * p is between current line and bottom line on screen.
  1119.     */
  1120.    if (win->rline < rline) {
  1121.       /*
  1122.        * test_line is the number of lines between rline and found line.
  1123.        */
  1124.       test_line = rline - win->rline;
  1125.       if ((long)win->cline + test_line <= (long)win->bottom_line)
  1126.          win->cline += (int)test_line;
  1127.       else
  1128.          file->dirty = LOCAL;
  1129.  
  1130.    /*
  1131.     * if p, start of found line, is less than current line, see if
  1132.     * p is between current line and top line on screen.
  1133.     */
  1134.    } else if (win->rline > rline) {
  1135.       test_line = win->rline - rline;
  1136.       if ((long)win->cline - test_line > (long)(win->top_line+win->ruler-1))
  1137.          win->cline -= (int)test_line;
  1138.       else
  1139.          file->dirty = LOCAL;
  1140.       if (rline < (long)(win->cline - (win->top_line+win->ruler-1)))
  1141.          win->cline = (int)rline + win->top_line+win->ruler - 1;
  1142.    }
  1143.  
  1144.    /*
  1145.     * cursor line becomes found line.  check if column is on screen.
  1146.     */
  1147.    win->rline = rline;
  1148.    win->ll    = ll;
  1149.    if (file->dirty == LOCAL && (win->cline == win->bottom_line ||
  1150.                                 win->cline == win->top_line + win->ruler)) {
  1151.       cmd = g_status.command;
  1152.       if (cmd == RepeatFindForward1    ||  cmd == RepeatFindBackward1 ||
  1153.           cmd == DefineDiff            ||  cmd == RepeatDiff          ||
  1154.           cmd == FindRegX              ||  cmd == RepeatFindRegX      ||
  1155.           cmd == DefineGrep            ||  cmd == RepeatGrep) {
  1156.          center_window( win );
  1157.       } else if (cmd == ReplaceString) {
  1158.          if (win->visible)
  1159.             center_window( win );
  1160.       }
  1161.    }
  1162.    check_virtual_col( win, rcol, rcol );
  1163. }
  1164.  
  1165.  
  1166. /*
  1167.  * Name:    replace_string
  1168.  * Purpose: To set up and perform a replace operation.
  1169.  * Date:    June 5, 1991
  1170.  * Passed:  window:  pointer to current window
  1171.  */
  1172. int  replace_string( TDE_WIN *window )
  1173. {
  1174. int  direction;
  1175. int  net_change;
  1176. int  sub_len;
  1177. int  file_changed;
  1178. int  finished;
  1179. int  use_prev_find;
  1180. int  rc;
  1181. int  rcol;
  1182. int  rcol_limit;
  1183. int  wrapped;
  1184. int  wrapped_state;
  1185. int  visible;
  1186. char answer[MAX_COLS+2];
  1187. long found_line;
  1188. long line_limit;
  1189. line_list_ptr  ll;
  1190. TDE_WIN  wp;
  1191. TDE_WIN  old_wp;
  1192. register TDE_WIN *win;    /* put window pointer in a register */
  1193.  
  1194.    win = window;
  1195.    direction = get_replace_direction( win );
  1196.    if (direction == ERROR)
  1197.       return( ERROR );
  1198.  
  1199.    entab_linebuff( );
  1200.    if (un_copy_line( win->ll, win, TRUE ) == ERROR)
  1201.       return( ERROR );
  1202.  
  1203.    /*
  1204.     * get the search pattern, using the previous as the default
  1205.     */
  1206.    *answer = '\0';
  1207.    if (g_status.replace_defined == OK) {
  1208.  
  1209.       assert( strlen( g_status.pattern ) < (size_t)g_display.ncols );
  1210.  
  1211.       strcpy( answer, g_status.pattern );
  1212.    }
  1213.  
  1214.    /*
  1215.     * string to find
  1216.     */
  1217.    if (get_name( find9, win->bottom_line, answer,
  1218.                  g_display.message_color ) != OK  ||  *answer == '\0')
  1219.       return( ERROR );
  1220.  
  1221.    assert( strlen( answer ) < (size_t)g_display.ncols );
  1222.  
  1223.    strcpy( g_status.pattern, answer );
  1224.  
  1225.    /*
  1226.     * get the replacement text, using the previous as the default
  1227.     */
  1228.    *answer = '\0';
  1229.    if (g_status.replace_defined == OK) {
  1230.  
  1231.       assert( strlen( g_status.subst ) < (size_t)g_display.ncols );
  1232.  
  1233.       strcpy( answer, g_status.subst );
  1234.    }
  1235.    if (get_name( find10, win->bottom_line, answer,
  1236.                  g_display.message_color ) != OK)
  1237.       return( ERROR );
  1238.  
  1239.    assert( strlen( answer ) < (size_t)g_display.ncols );
  1240.  
  1241.    strcpy( g_status.subst, answer );
  1242.    sub_len = strlen( answer );
  1243.    strcpy( (char *)bm.pattern, g_status.pattern );
  1244.    net_change = sub_len - strlen( g_status.pattern );
  1245.  
  1246.    /*
  1247.     * get the replace flags, Prompt or NoPrompt
  1248.     */
  1249.    if (get_replacement_flags( win->bottom_line ) != OK)
  1250.       return( ERROR );
  1251.  
  1252.    build_boyer_array( );
  1253.    dup_window_info( &wp, win );
  1254.    update_line( win );
  1255.    g_status.replace_defined = OK;
  1256.  
  1257.    if (mode.inflate_tabs)
  1258.       win->rcol = entab_adjust_rcol( win->ll->line, win->ll->len, win->rcol );
  1259.  
  1260.    rc = OK;
  1261.    visible = win->visible;
  1262.    if (g_status.replace_flag == NOPROMPT) {
  1263.       wp.visible = FALSE;
  1264.       xygoto( win->ccol, win->cline );
  1265.       show_search_message( REPLACING, g_display.diag_color );
  1266.    }
  1267.    wrapped_state = wrapped = FALSE;
  1268.    finished = FALSE;
  1269.    file_changed = FALSE;
  1270.    use_prev_find = FALSE;
  1271.    line_limit = 0;
  1272.    rcol_limit = 0;
  1273.    dup_window_info( &old_wp, &wp );
  1274.    if (direction == FORWARD) {
  1275.       if ((ll = forward_boyer_moore_search( &wp, &found_line, &rcol )) != NULL &&
  1276.                 !g_status.control_break) {
  1277.          line_limit = found_line;
  1278.          rcol_limit = rcol;
  1279.          if (g_status.wrapped)
  1280.             wrapped_state = wrapped = TRUE;
  1281.          rc = replace_and_display( &wp, ll, found_line, rcol, &finished,
  1282.                                    &file_changed, direction );
  1283.          if (rc == ERROR &&  g_status.replace_flag == PROMPT  && wrapped_state)
  1284.             use_prev_find = TRUE;
  1285.       } else {
  1286.          /*
  1287.           * string not found
  1288.           */
  1289.          error( WARNING, win->bottom_line, find8 );
  1290.          finished = TRUE;
  1291.          rc = ERROR;
  1292.       }
  1293.       while (finished == FALSE) {
  1294.          use_prev_find = wrapped_state = FALSE;
  1295.          dup_window_info( &old_wp, &wp );
  1296.          if (wp.visible == TRUE)
  1297.             update_line( &wp );
  1298.          if ((ll = forward_boyer_moore_search( &wp, &found_line, &rcol )) != NULL &&
  1299.              !g_status.control_break) {
  1300.             if (g_status.wrapped)
  1301.                wrapped_state = wrapped = TRUE;
  1302.             if (wrapped) {
  1303.                if (found_line > line_limit) {
  1304.                   finished = TRUE;
  1305.                   use_prev_find = TRUE;
  1306.                } else if (found_line == line_limit  &&  rcol == rcol_limit) {
  1307.                   finished = TRUE;
  1308.                   use_prev_find = TRUE;
  1309.                }
  1310.             }
  1311.             if (finished == FALSE) {
  1312.                rc = replace_and_display( &wp, ll, found_line, rcol, &finished,
  1313.                                          &file_changed, direction );
  1314.                if (rc == OK && ll == win->ll && rcol < rcol_limit)
  1315.                   rcol_limit += net_change;
  1316.                if (rc == ERROR &&  g_status.replace_flag == PROMPT  &&
  1317.                                         wrapped_state)
  1318.                   use_prev_find = TRUE;
  1319.             }
  1320.          } else {
  1321.             if (g_status.control_break)
  1322.                rc = getkey( );
  1323.             /*
  1324.              * string not found     or   control break
  1325.              */
  1326.             if (g_status.control_break)
  1327.                error( WARNING, win->bottom_line, cb );
  1328.             else if (wp.visible)
  1329.                error( WARNING, win->bottom_line, find8 );
  1330.             finished = TRUE;
  1331.             rc = ERROR;
  1332.          }
  1333.       }
  1334.    } else {
  1335.       if ((ll = backward_boyer_moore_search( &wp, &found_line, &rcol )) != NULL &&
  1336.           !g_status.control_break) {
  1337.          line_limit = found_line;
  1338.          rcol_limit = rcol;
  1339.          if (g_status.wrapped)
  1340.             wrapped_state = wrapped = TRUE;
  1341.          replace_and_display( &wp, ll, found_line, rcol, &finished, &file_changed,
  1342.                               direction );
  1343.          if (rc == ERROR &&  g_status.replace_flag == PROMPT  && wrapped_state)
  1344.             use_prev_find = TRUE;
  1345.       } else {
  1346.          /*
  1347.           * string not found
  1348.           */
  1349.          error( WARNING, win->bottom_line, find8 );
  1350.          finished = TRUE;
  1351.          rc = ERROR;
  1352.       }
  1353.       while (finished == FALSE) {
  1354.          use_prev_find = wrapped_state = FALSE;
  1355.          dup_window_info( &old_wp, &wp );
  1356.          if (wp.visible == TRUE)
  1357.             update_line( &wp );
  1358.          if ((ll = backward_boyer_moore_search( &wp, &found_line, &rcol )) != NULL &&
  1359.              !g_status.control_break) {
  1360.             if (g_status.wrapped)
  1361.                wrapped_state = wrapped = TRUE;
  1362.             if (wrapped) {
  1363.                if (found_line < line_limit) {
  1364.                   finished = TRUE;
  1365.                   use_prev_find = TRUE;
  1366.                } else if (found_line == line_limit  &&  rcol == rcol_limit) {
  1367.                   finished = TRUE;
  1368.                   use_prev_find = TRUE;
  1369.                }
  1370.             }
  1371.             if (finished == FALSE) {
  1372.                rc = replace_and_display( &wp, ll, found_line, rcol, &finished,
  1373.                                          &file_changed, direction );
  1374.                if (rc == OK && found_line == line_limit && rcol < rcol_limit)
  1375.                   rcol_limit += net_change;
  1376.                if (rc == ERROR  && g_status.replace_flag == PROMPT  &&
  1377.                                         wrapped_state)
  1378.                   use_prev_find = TRUE;
  1379.             }
  1380.          } else {
  1381.             if (g_status.control_break)
  1382.                rc = getkey( );
  1383.             /*
  1384.              * string not found    or   control break
  1385.              */
  1386.             if (g_status.control_break)
  1387.                error( WARNING, win->bottom_line, cb );
  1388.             else if (wp.visible)
  1389.                error( WARNING, win->bottom_line, find8 );
  1390.             finished = TRUE;
  1391.             rc = ERROR;
  1392.          }
  1393.       }
  1394.    }
  1395.  
  1396.    if (g_status.replace_flag == PROMPT) {
  1397.       if (use_prev_find)
  1398.          dup_window_info( &wp, &old_wp );
  1399.       dup_window_info( win, &wp );
  1400.    } else {
  1401.       show_search_message( CLR_SEARCH, g_display.mode_color );
  1402.       g_status.wrapped = FALSE;
  1403.    }
  1404.  
  1405.    if (mode.inflate_tabs)
  1406.       win->rcol = detab_adjust_rcol( win->ll->line, win->rcol );
  1407.  
  1408.    win->visible = visible;
  1409.    check_virtual_col( win, win->rcol, win->ccol );
  1410.    if (win->file_info->dirty != LOCAL && win->file_info->dirty != GLOBAL)
  1411.       show_curl_line( win );
  1412.    if (file_changed)
  1413.       win->file_info->modified = TRUE;
  1414.    make_ruler( win );
  1415.    show_ruler( win );
  1416.    show_ruler_pointer( win );
  1417.    return( rc );
  1418. }
  1419.  
  1420.  
  1421. /*
  1422.  * Name:    replace_and_display
  1423.  * Purpose: To make room for replacement string
  1424.  * Date:    June 5, 1991
  1425.  * Passed:  window:            pointer to current window
  1426.  *          ll:                pointer to position of pattern in file
  1427.  *          rline:             pointer to real line counter
  1428.  *          rcol:              pointer to real column
  1429.  *          finished:          stop replacing on this occurrence?
  1430.  *          modified:          skip this replacement?
  1431.  *          direction:         direction of search
  1432.  * Notes:   Show user where pattern_location is on screen if needed.
  1433.  *          Replace and display if needed.   Always ask the user if he
  1434.  *          wants to do wrapped replacing.
  1435.  */
  1436. int  replace_and_display( TDE_WIN *window, line_list_ptr ll, long rline,
  1437.                      int rcol, int *finished, int *modified, int direction )
  1438. {
  1439. register int rc;
  1440. file_infos *file;
  1441. register TDE_WIN *win;  /* put window pointer in a register */
  1442.  
  1443.    win = window;
  1444.    file = win->file_info;
  1445.    rc = OK;
  1446.    if (g_status.wrapped) {
  1447.       rc = ask_wrap_replace( win, finished );
  1448.       g_status.wrapped = FALSE;
  1449.       show_search_message( CLR_SEARCH, g_display.mode_color );
  1450.    }
  1451.    if (rc == OK) {
  1452.       find_adjust( win, ll, rline, rcol );
  1453.       if (win->visible == TRUE) {
  1454.          make_ruler( win );
  1455.          show_ruler( win );
  1456.          show_ruler_pointer( win );
  1457.          xygoto( win->ccol, win->cline );
  1458.          if (file->dirty) {
  1459.             display_current_window( win );
  1460.             file->dirty = FALSE;
  1461.          } else
  1462.             show_curl_line( win );
  1463.       }
  1464.  
  1465.       if (g_status.replace_flag == PROMPT && rc == OK) {
  1466.          show_line_col( win );
  1467.          rc = ask_replace( win, finished );
  1468.       }
  1469.       if (rc == OK) {
  1470.          do_replace( win, direction );
  1471.          *modified = TRUE;
  1472.          file->dirty = GLOBAL;
  1473.          if (win->visible == TRUE) {
  1474.             show_changed_line( win );
  1475.             file->dirty = FALSE;
  1476.          }
  1477.       }
  1478.       if (mode.inflate_tabs) {
  1479.          if (win->rcol >= 0)
  1480.             win->rcol = entab_adjust_rcol( ll->line, ll->len, win->rcol );
  1481.       }
  1482.    }
  1483.    return( rc );
  1484. }
  1485.  
  1486.  
  1487. /*
  1488.  * Name:    scan_forward
  1489.  * Purpose: To find the corresponding occurrence of target, ignoring
  1490.  *           embedded pairs of opp and target, searching forwards.
  1491.  * Date:    June 5, 1991
  1492.  * Passed:  rline:  pointer to real line position
  1493.  *          rcol:   pointer to real column position
  1494.  *          ll:     pointer to current node in linked list
  1495.  *          opp:    the opposite to target
  1496.  *          target: the string to be found
  1497.  *          rc:     OK if found, ERROR otherwise
  1498.  * Returns: the location of the corresponding target in the text buffer
  1499.  * Notes:   Every 8,000 characters, check pointer forward.
  1500.  */
  1501. line_list_ptr scan_forward( long *rline, int *rcol, line_list_ptr ll,
  1502.                             char opp, char target, int *rc )
  1503. {
  1504. text_ptr s;
  1505. int  count = 0;          /* number of unmatched opposites found */
  1506. int  len;
  1507. register char c;
  1508.  
  1509.    *rc = OK;
  1510.    if (ll != NULL  &&  ll->len != EOF) {
  1511.       len = ll->len - *rcol - 1;
  1512.       s = ll->line + *rcol + 1;
  1513.       while (ll->len != EOF) {
  1514.          while (len > 0) {
  1515.  
  1516.             assert( s != NULL);
  1517.  
  1518.             c = *s++;
  1519.             --len;
  1520.             if (opp == c)
  1521.                count++;
  1522.             else if (target == c) {
  1523.                if (count == 0)
  1524.                  goto match;
  1525.                --count;
  1526.             }
  1527.          }
  1528.          ++*rline;
  1529.          ll  = ll->next;
  1530.          s   = ll->line;
  1531.          len = ll->len;
  1532.       }
  1533. match:
  1534.       if (ll->len != EOF) {
  1535.  
  1536.          assert( s != NULL );
  1537.  
  1538.          *rcol = (int)(s - ll->line - 1);
  1539.       } else
  1540.          *rc = ERROR;
  1541.    } else
  1542.       *rc = ERROR;
  1543.  
  1544.    if (*rc == OK) {
  1545.       assert( *rcol >= 0 );
  1546.       assert( *rcol < ll->len );
  1547.    }
  1548.  
  1549.    return( ll );
  1550. }
  1551.  
  1552.  
  1553. /*
  1554.  * Name:    scan_backward
  1555.  * Purpose: To find the corresponding occurrence of target, ignoring
  1556.  *           embedded pairs of opp and target, searching backwards.
  1557.  * Date:    June 5, 1991
  1558.  * Passed:  rline:  pointer to real line position
  1559.  *          rcol:   pointer to real column position
  1560.  *          ll:     pointer to current node in linked list
  1561.  *          opp:    the opposite to target
  1562.  *          target: the string to be found
  1563.  *          rc:     OK if found, ERROR otherwise
  1564.  * Returns: the location of the corresponding target in the text buffer
  1565.  */
  1566. line_list_ptr scan_backward( long *rline, int *rcol, line_list_ptr ll,
  1567.                              char opp, char target, int *rc )
  1568. {
  1569. text_ptr s;
  1570. int  count = 0;         /* number of unmatched opposites found */
  1571. register int len;
  1572. register char c;
  1573.  
  1574.    *rc = OK;
  1575.    if (ll != NULL  &&  ll->len != EOF) {
  1576.       s = ll->line + *rcol - 1;
  1577.       len = *rcol;
  1578.       while (ll != NULL) {
  1579.          while (len > 0) {
  1580.  
  1581.             assert( s != NULL );
  1582.  
  1583.             c = *s--;
  1584.             if (opp == c)
  1585.                count++;
  1586.             else if (target == c) {
  1587.                if (count == 0)
  1588.                  goto match;
  1589.                --count;
  1590.             }
  1591.             --len;
  1592.          }
  1593.          --*rline;
  1594.          ll = ll->prev;
  1595.          if (ll != NULL) {
  1596.             len = ll->len;
  1597.             s = ll->line + len - 1;
  1598.          }
  1599.       }
  1600. match:
  1601.       if (ll != NULL) {
  1602.  
  1603.          assert( s != NULL );
  1604.  
  1605.          *rcol = (int)(s - ll->line + 1);
  1606.       } else
  1607.          *rc = ERROR;
  1608.    } else
  1609.       *rc = ERROR;
  1610.  
  1611.    if (*rc == OK) {
  1612.       assert( *rcol >= 0 );
  1613.       assert( *rcol < ll->len );
  1614.    }
  1615.  
  1616.    return( ll );
  1617. }
  1618.  
  1619.  
  1620. /*
  1621.  * Name:    match_pair
  1622.  * Purpose: To find the corresponding pair to the character under the
  1623.  *           cursor.
  1624.  * Date:    June 5, 1991
  1625.  * Passed:  window:  pointer to current window
  1626.  * Notes:   Searching is very simple-minded, and does not cope with things
  1627.  *          like brackets embedded within quoted strings.
  1628.  */
  1629. int  match_pair( TDE_WIN *window )
  1630. {
  1631. register TDE_WIN *win;  /* put window pointer in a register */
  1632. long rline;
  1633. int  rc;
  1634. int  rcol;
  1635. int  old_rcol;
  1636. line_list_ptr ll;
  1637.  
  1638.    win = window;
  1639.    entab_linebuff( );
  1640.    rline = win->rline;
  1641.    ll = win->ll;
  1642.    if (un_copy_line( ll, win, TRUE ) == ERROR)
  1643.       return( ERROR );
  1644.    /*
  1645.     * make sure the character under the cursor is one that has a
  1646.     *  matched pair.
  1647.     */
  1648.    rc = OK;
  1649.    old_rcol = win->rcol;
  1650.    if (mode.inflate_tabs)
  1651.       win->rcol = entab_adjust_rcol( win->ll->line, win->ll->len, win->rcol);
  1652.  
  1653.    rcol = win->rcol;
  1654.    if (ll->len == EOF || rcol >= ll->len)
  1655.       rc = ERROR;
  1656.  
  1657.    if (rc != ERROR) {
  1658.       /*
  1659.        * find the matching pair
  1660.        */
  1661.       switch (*(ll->line + rcol)) {
  1662.          case '[':
  1663.             ll = scan_forward( &rline, &rcol, ll, '[', ']', &rc );
  1664.             break;
  1665.          case '(':
  1666.             ll = scan_forward( &rline, &rcol, ll, '(', ')', &rc );
  1667.             break;
  1668.          case '{':
  1669.             ll = scan_forward( &rline, &rcol, ll, '{', '}', &rc );
  1670.             break;
  1671.          case ']':
  1672.             ll = scan_backward( &rline, &rcol, ll, ']', '[', &rc );
  1673.             break;
  1674.          case ')':
  1675.             ll = scan_backward( &rline, &rcol, ll, ')', '(', &rc );
  1676.             break;
  1677.          case '}':
  1678.             ll = scan_backward( &rline, &rcol, ll, '}', '{', &rc );
  1679.             break;
  1680.          default :
  1681.             rc = ERROR;
  1682.       }
  1683.    }
  1684.  
  1685.    /*
  1686.     * now show the user what we have found
  1687.     */
  1688.    if (rc == OK) {
  1689.       update_line( win );
  1690.       bin_offset_adjust( win, rline );
  1691.       find_adjust( win, ll, rline, rcol );
  1692.       if (!win->file_info->dirty)
  1693.          show_curl_line( win );
  1694.       make_ruler( win );
  1695.       show_ruler( win );
  1696.    } else {
  1697.       if (mode.inflate_tabs)
  1698.          win->rcol = old_rcol;
  1699.    }
  1700.    return( rc );
  1701. }
  1702.