Mercurial > hg > Applications > Grep
annotate regexParser/grepWalk.cc @ 319:7b8234c090f7
bmSearch
author | mir3636 |
---|---|
date | Sun, 08 May 2016 22:53:20 +0900 |
parents | fa590a7272ae |
children |
rev | line source |
---|---|
231 | 1 #include <stdio.h> |
299 | 2 #include <stdlib.h> |
316 | 3 #include <string.h> |
231 | 4 |
5 #include "grepWalk.h" | |
234
df4d04b3c34a
implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
232
diff
changeset
|
6 #include "subsetConstruction.h" |
308 | 7 #include "CharClass.h" |
299 | 8 #include "threadedSearch.h" |
319 | 9 #include "bmSearch.h" |
234
df4d04b3c34a
implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
232
diff
changeset
|
10 |
299 | 11 StatePtr nextState(BitVector bi,TransitionGeneratorPtr tg) { |
12 // create tSearch in next state. | |
13 StatePtr state = tg->stateArray[bi.bitContainer]; | |
14 if (state == NULL) { | |
15 // on the fly subset construction. | |
16 state = createState(tg,bi); | |
17 determinize(state,tg); | |
18 tg->stateArray[bi.bitContainer] = state; | |
19 } | |
20 return state; | |
293
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
266
diff
changeset
|
21 } |
948428caf616
NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents:
266
diff
changeset
|
22 |
299 | 23 void grepWalk(TransitionGeneratorPtr tg,Buffer buff) { |
24 TSValue tsv = createTSValue(tg,buff); | |
25 tg->stateStart = NEW(State); | |
26 *tg->stateStart = *tg->stateList; | |
27 tg->stateStart->accept = false; // Start state never accept | |
28 StatePtr state = tg->stateStart; | |
319 | 29 checkBMSearch(state->cc); |
234
df4d04b3c34a
implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
232
diff
changeset
|
30 |
299 | 31 #if DEBUG |
32 TSValuePtr tsvp = &tsv; // make tsv visible in lldb | |
33 #endif | |
34 next: while (tsv.buff.buffptr < tsv.buff.buffend) { | |
35 if (state->accept) { | |
36 tsv = tg->stateMatch(tsv); | |
37 } | |
38 CharClassWalkerPtr ccw = createCharClassWalker(state->cc); | |
39 if (!hasNext(ccw)) { | |
40 // matched start again | |
41 state = tg->stateStart; | |
42 ccw = createCharClassWalker(state->cc); | |
235
4aab1e93a971
fix condition grepWalk.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
234
diff
changeset
|
43 } |
299 | 44 unsigned char c = *tsv.buff.buffptr++; |
45 // printState(tsv.current->state); | |
46 while (hasNext(ccw)) { | |
47 CharClassPtr cc = getNext(ccw); | |
48 if (c<cc->cond.range.begin) { | |
49 state = tg->stateStart; | |
50 tsv = tg->stateSkip(tsv); | |
51 goto next; | |
52 } else if (c<=cc->cond.range.end) { | |
53 // range matched. | |
54 if (cc->cond.w.word) { | |
315 | 55 WordPtr w; |
316 | 56 for (w = &cc->cond.w;w;w = w->next) { |
315 | 57 // match the word. |
317 | 58 if (strncmp((const char *)w->word,(const char *)tsv.buff.buffptr-1,w->length)==0) break; |
315 | 59 } |
317 | 60 if (!w) continue; // if (not match) continue; |
316 | 61 tsv.buff.buffptr += w->length - 1; |
299 | 62 } |
63 state = nextState(cc->nextState,tg); | |
64 goto next; | |
65 } | |
66 } | |
67 state = tg->stateStart; | |
68 tsv = tg->stateSkip(tsv); | |
234
df4d04b3c34a
implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
232
diff
changeset
|
69 } |
299 | 70 #if DEBUG |
71 *tsvp = tsv; | |
72 #endif | |
234
df4d04b3c34a
implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
232
diff
changeset
|
73 } |
df4d04b3c34a
implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
232
diff
changeset
|
74 |