/* | |
* Notepad (search.c) | |
* Copyright (C) 1999 by Marcel Baur | |
* To be distributed under the Wine license | |
* | |
* This file features Heuristic Boyer-Moore Text Search | |
* | |
* Always: - Buf is the Buffer containing the whole text | |
* ======= - SP is the Search Pattern, which has to be found in Buf. | |
* | |
*/ | |
#include <win.h> | |
#define CHARSETSIZE 255 | |
int delta[CHARSETSIZE]; | |
/* rightmostpos: return rightmost position of ch in szSP (or -1) */ | |
int rightmostpos(char ch, LPSTR szSP, int nSPLen) { | |
int i = nSPLen; | |
while ((i>0) & (szSP[i]!=ch)) i--; | |
return(i); | |
} | |
/* setup_delta: setup delta1 cache */ | |
void setup_delta(LPSTR szSP, int nSPLen) { | |
int i; | |
for (i=0; i<CHARSETSIZE; i++) { | |
delta[i] = nSPLen; | |
} | |
for (i=0; i<nSPLen; i++) { | |
delta[(int)szSP[i]] = (nSPLen - rightmostpos(szSP[i], szSP, nSPLen)); | |
} | |
} | |
int bm_search(LPSTR szBuf, int nBufLen, LPSTR szSP, int nSPLen) { | |
int i = nSPLen; | |
int j = nSPLen; | |
do { | |
if ((szBuf[i] = szSP[j])) { | |
i--; j--; | |
} else { | |
if ((nSPLen-j+1) > delta[(int)szBuf[i]]) { | |
i+= (nSPLen-j+1); | |
} else { | |
i+= delta[(int)szBuf[i]]; | |
} | |
} | |
} while (j>0 && i<=nBufLen); | |
return(i+1); | |
} | |