Mercurial > hg > Applications > Grep

annotate regexParser/grepWalk.cc @ 293:948428caf616

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
NFA maximum match worked
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Tue, 02 Feb 2016 10:38:45 +0900
parents e51cac73e42a
children bdfe0a32c48f
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
231
d67649929e96 add grepWalk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
1 #include <stdio.h>
d67649929e96 add grepWalk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
2
d67649929e96 add grepWalk
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
3 #include "grepWalk.h"
234
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
4 #include "subsetConstruction.h"
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
5
293
948428caf616 NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 266
diff changeset
6 void grep(TransitionGeneratorPtr tg,unsigned char *matchBegin,Buffer buff,unsigned long d) ;
234
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
7
293
948428caf616 NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 266
diff changeset
8 void grepSkip(TransitionGeneratorPtr tg,unsigned char *matchBegin, Buffer buff) {
948428caf616 NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 266
diff changeset
9 matchBegin = buff.buffptr;
948428caf616 NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 266
diff changeset
10 grep(tg,matchBegin,buff,1); // 1 is initState
234
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
11 }
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
12
293
948428caf616 NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 266
diff changeset
13 void grepWalk(TransitionGeneratorPtr tg, unsigned char *matchBegin, Buffer buff) {
948428caf616 NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 266
diff changeset
14 grepSkip(tg,matchBegin,buff);
948428caf616 NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 266
diff changeset
15 }
948428caf616 NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 266
diff changeset
16
948428caf616 NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 266
diff changeset
17 void grepMatch(TransitionGeneratorPtr tg,unsigned char *matchBegin, Buffer buff) {
948428caf616 NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 266
diff changeset
18 fwrite(matchBegin,buff.buffptr-matchBegin,1,stdout);
948428caf616 NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 266
diff changeset
19 puts("\n");
948428caf616 NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 266
diff changeset
20 grepSkip(tg,matchBegin,buff);
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
948428caf616 NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 266
diff changeset
23 void grep(TransitionGeneratorPtr tg,unsigned char *matchBegin,Buffer buff,unsigned long d) {
234
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
24 unsigned char c = *buff.buffptr++;
235
4aab1e93a971 fix condition grepWalk.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 234
diff changeset
25 if (c=='\0') return;
234
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
26 StatePtr state = tg->stateList;
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
27
237
b809e7b62986 add memo
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 235
diff changeset
28 while (state->bitState.bitContainer != d) state = state->next; // 配列へのアクセスへ変更
234
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
29 CharClassWalkerPtr ccw = createCharClassWalker(state->cc);
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
30 CharClassPtr cc = NULL;
237
b809e7b62986 add memo
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 235
diff changeset
31 bool found = false;
234
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
32 while (hasNext(ccw)) {
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
33 cc = getNext(ccw);
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
34 unsigned long begin = cc->cond.range.begin;
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
35 unsigned long end = cc->cond.range.end;
235
4aab1e93a971 fix condition grepWalk.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 234
diff changeset
36 if (begin == end) {
4aab1e93a971 fix condition grepWalk.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 234
diff changeset
37 if (c == begin) found = true;
4aab1e93a971 fix condition grepWalk.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 234
diff changeset
38 else found = false;
4aab1e93a971 fix condition grepWalk.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 234
diff changeset
39 } else {
4aab1e93a971 fix condition grepWalk.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 234
diff changeset
40 if (c < begin) found = false;
4aab1e93a971 fix condition grepWalk.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 234
diff changeset
41 else if (c < end) found = true;
4aab1e93a971 fix condition grepWalk.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 234
diff changeset
42 }
234
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
43 if (found == true) break;
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
44 }
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
45
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
46 if (found == false) {
293
948428caf616 NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 266
diff changeset
47 grepSkip(tg,matchBegin,buff);
242
6aebc4d7dd75 fix condition generateSequentialSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 237
diff changeset
48 } else if (found == true && (cc->nextState.bitContainer | 2)) { // Accept
293
948428caf616 NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 266
diff changeset
49 grepMatch(tg,matchBegin,buff);
234
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
50 } else {
293
948428caf616 NFA maximum match worked
Shinji KONO <kono@ie.u-ryukyu.ac.jp>
parents: 266
diff changeset
51 grep(tg,matchBegin,buff,cc->nextState.bitContainer);
234
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
52 }
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
53 }
df4d04b3c34a implement grepWalk (not confirm correct working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 232
diff changeset
54