programs/notepad/search.c

   1 /*
   2  *  Notepad (search.c)
   3  *  Copyright (C) 1999 by Marcel Baur
   4  *  To be distributed under the Wine license
   5  *
   6  *  This file features Heuristic Boyer-Moore Text Search
   7  *
   8  *  Always:   - Buf is the Buffer containing the whole text
   9  *  =======   - SP is the Search Pattern, which has to be found in Buf.
  10  *
  11  */
  12
  13  #include <win.h>
  14
  15  #define CHARSETSIZE 255
  16
  17  int delta[CHARSETSIZE];
  18
  19  /* rightmostpos: return rightmost position of ch in szSP (or -1) */
  20  int rightmostpos(char ch, LPSTR szSP, int nSPLen) {
  21     int i = nSPLen;
  22     while ((i>0) & (szSP[i]!=ch)) i--;
  23     return(i);
  24  }
  25
  26  /* setup_delta: setup delta1 cache */
  27  void setup_delta(LPSTR szSP, int nSPLen) {
  28     int i;
  29
  30     for (i=0; i<CHARSETSIZE; i++) {
  31        delta[i] = nSPLen;
  32     }
  33
  34     for (i=0; i<nSPLen; i++) {
  35        delta[(int)szSP[i]] = (nSPLen - rightmostpos(szSP[i], szSP, nSPLen));
  36     }
  37  }
  38
  39  int bm_search(LPSTR szBuf, int nBufLen, LPSTR szSP, int nSPLen) {
  40     int i = nSPLen;
  41     int j = nSPLen;
  42
  43     do {
  44        if ((szBuf[i] = szSP[j])) {
  45          i--; j--;
  46        } else {
  47          if ((nSPLen-j+1) > delta[(int)szBuf[i]]) {
  48            i+= (nSPLen-j+1);
  49          } else {
  50            i+= delta[(int)szBuf[i]];
  51          }
  52        }
  53     } while (j>0 && i<=nBufLen);
  54     return(i+1);
  55  }
  56