3 * Copyright (C) 1999 by Marcel Baur
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.
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.
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
19 * This file features Heuristic Boyer-Moore Text Search
21 * Always: - Buf is the Buffer containing the whole text
22 * ======= - SP is the Search Pattern, which has to be found in Buf.
28 #define CHARSETSIZE 255
30 int delta
[CHARSETSIZE
];
32 /* rightmostpos: return rightmost position of ch in szSP (or -1) */
33 int rightmostpos(char ch
, LPSTR szSP
, int nSPLen
) {
35 while ((i
>0) & (szSP
[i
]!=ch
)) i
--;
39 /* setup_delta: setup delta1 cache */
40 void setup_delta(LPSTR szSP
, int nSPLen
) {
43 for (i
=0; i
<CHARSETSIZE
; i
++) {
47 for (i
=0; i
<nSPLen
; i
++) {
48 delta
[(int)szSP
[i
]] = (nSPLen
- rightmostpos(szSP
[i
], szSP
, nSPLen
));
52 int bm_search(LPSTR szBuf
, int nBufLen
, LPSTR szSP
, int nSPLen
) {
57 if ((szBuf
[i
] = szSP
[j
])) {
60 if ((nSPLen
-j
+1) > delta
[(int)szBuf
[i
]]) {
63 i
+= delta
[(int)szBuf
[i
]];
66 } while (j
>0 && i
<=nBufLen
);