Mercurial > hg > Applications > Grep
comparison regexParser/bmSearch.cc @ 319:7b8234c090f7
bmSearch
author | mir3636 |
---|---|
date | Sun, 08 May 2016 22:53:20 +0900 |
parents | |
children | da02a7258d54 |
comparison
equal
deleted
inserted
replaced
318:c9458ffecb87 | 319:7b8234c090f7 |
---|---|
1 #include "regexPaser.h" | |
2 #include "CharClass.h" | |
3 | |
4 /** | |
5 * if start node contains only words, Boyer-Moore Search can be used. | |
6 * if so skip table is created for each word. | |
7 */ | |
8 | |
9 static void | |
10 create_BMskiptable(BMPtr bm,unsigned char *word,int len) | |
11 { | |
12 bm->skip_table = (int*)malloc(sizeof(int)*256); | |
13 for (int i = 0; i < 256; ++i) { | |
14 bm->skip_table[i] = len; | |
15 } | |
16 | |
17 for (int j = 0; j < len - 1; ++j) { | |
18 bm->skip_table[word[j]] = len - j - 1; | |
19 } | |
20 } | |
21 | |
22 void checkBMSearch(CharaClassPtr cc) { | |
23 | |
24 // first check there is no Chareclass range | |
25 CharClassWalkerPtr cw = createCharClassWalker(st->cc); | |
26 while (hasNext(cw)) { | |
27 CharClassPtr cc = getNext(cw); | |
28 if (cc->cond.w.word == NULL) { | |
29 free(cw); | |
30 return; | |
31 } | |
32 } | |
33 free(cw); | |
34 | |
35 // make skip table for each word | |
36 cw = createCharClassWalker(st->cc); | |
37 while (hasNext(cw)) { | |
38 CharClassPtr cc = getNext(cw); | |
39 if (cc->cond.w.word) { | |
40 WordPtr w = &cc->cond.w; | |
41 while (w) { | |
42 BMPtr bm = NEW(BM); | |
43 cc->cond.w.bm = bm; | |
44 create_BMskiptable(bm,cc->cond.w.word,cc->cond.length); | |
45 w = w->next; | |
46 } | |
47 } | |
48 } | |
49 free(cw); | |
50 } |