programs/notepad/search.c

   1 /*
   2  *  Notepad (search.c)
   3  *  Copyright (C) 1999 by Marcel Baur
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2.1 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Lesser General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser General Public
  16  * License along with this library; if not, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  18  *
  19  *  This file features Heuristic Boyer-Moore Text Search
  20  *
  21  *  Always:   - Buf is the Buffer containing the whole text
  22  *  =======   - SP is the Search Pattern, which has to be found in Buf.
  23  *
  24  */
  25
  26 #include <windows.h>
  27
  28  #define CHARSETSIZE 255
  29
  30  int delta[CHARSETSIZE];
  31
  32  /* rightmostpos: return rightmost position of ch in szSP (or -1) */
  33  int rightmostpos(char ch, LPSTR szSP, int nSPLen) {
  34     int i = nSPLen;
  35     while ((i>0) & (szSP[i]!=ch)) i--;
  36     return(i);
  37  }
  38
  39  /* setup_delta: setup delta1 cache */
  40  void setup_delta(LPSTR szSP, int nSPLen) {
  41     int i;
  42
  43     for (i=0; i<CHARSETSIZE; i++) {
  44        delta[i] = nSPLen;
  45     }
  46
  47     for (i=0; i<nSPLen; i++) {
  48        delta[(int)szSP[i]] = (nSPLen - rightmostpos(szSP[i], szSP, nSPLen));
  49     }
  50  }
  51
  52  int bm_search(LPSTR szBuf, int nBufLen, LPSTR szSP, int nSPLen) {
  53     int i = nSPLen;
  54     int j = nSPLen;
  55
  56     do {
  57        if ((szBuf[i] = szSP[j])) {
  58          i--; j--;
  59        } else {
  60          if ((nSPLen-j+1) > delta[(int)szBuf[i]]) {
  61            i+= (nSPLen-j+1);
  62          } else {
  63            i+= delta[(int)szBuf[i]];
  64          }
  65        }
  66     } while (j>0 && i<=nBufLen);
  67     return(i+1);
  68  }
  69