Mercurial > hg > Applications > Grep

annotate regexParser/threadedSearch.cc @ 278:99d635926ef3

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
ceriumCreateAnyState implemented
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Sat, 30 Jan 2016 21:19:05 +0900
parents 7b4bcc7b5ae6
children b74e3b4b11d7
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
1 #include <stdio.h>
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
2 #include <stdlib.h>
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
3
246
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 245
diff changeset
4 #include "regexParser.h"
258
29e467a491ba remove error and add threadedSearch.h
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 257
diff changeset
5 #include "threadedSearch.h"
246
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 245
diff changeset
6 #include "subsetConstruction.h"
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 245
diff changeset
7
259
6a6546a753cf tSearch of driver in main.cc (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 258
diff changeset
8 void tSearch(TSValue tsv);
6a6546a753cf tSearch of driver in main.cc (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 258
diff changeset
9
272
5aa9d01926f1 Cerium version no compile errors
kono
parents: 270
diff changeset
10 static
264
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
11 TSValue stateNothing(TSValue tsv) {
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
12 return tsv;
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14
272
5aa9d01926f1 Cerium version no compile errors
kono
parents: 270
diff changeset
15 static
264
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
16 TSValue stateSkip(TSValue tsv) {
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
17 tsv.buff.matchBegin = tsv.buff.buffptr;
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
18 return tsv;
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
19 }
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
20
272
5aa9d01926f1 Cerium version no compile errors
kono
parents: 270
diff changeset
21 static
264
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
22 TSValue stateMatch(TSValue tsv) {
263
292753bb31e4 fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 262
diff changeset
23 fwrite(tsv.buff.matchBegin,tsv.buff.buffptr-tsv.buff.matchBegin-1,1,stdout);
264
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
24 puts("");
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
25 tsv.current = tsv.tg->stateList->tState;
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
26 tsv.buff.buffptr--;
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
27 tsv = stateSkip(tsv);
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
28 return tsv;
257
ebb429c2b6a7 fix allocate state in generateTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 254
diff changeset
29 }
ebb429c2b6a7 fix allocate state in generateTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 254
diff changeset
30
266
e51cac73e42a CeriumGrep start
masa
parents: 264
diff changeset
31 TStatePtr generateTState(StatePtr state, TransitionGeneratorPtr tg) {
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
32 TStatePtr tState = NEW(TState);
264
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
33 tState->state = state;
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
34 state->tState = tState;
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
35 int ccvSize = 0;
251
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
36 CharClassWalkerPtr ccw = createCharClassWalker(state->cc);
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
37 while (hasNext(ccw)) {
263
292753bb31e4 fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 262
diff changeset
38 getNext(ccw);
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
39 ccvSize++;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
40 }
263
292753bb31e4 fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 262
diff changeset
41 tState->ccvSize = ccvSize;
275
8879eb8c64a8 remove segmentation fault
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 272
diff changeset
42 if (state->accept) {
8879eb8c64a8 remove segmentation fault
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 272
diff changeset
43 tState->stateSkip = tg->stateMatch;
8879eb8c64a8 remove segmentation fault
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 272
diff changeset
44 tState->stateContinue = tg->stateNothing;
8879eb8c64a8 remove segmentation fault
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 272
diff changeset
45 } else {
8879eb8c64a8 remove segmentation fault
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 272
diff changeset
46 tState->stateSkip = tg->stateSkip;
8879eb8c64a8 remove segmentation fault
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 272
diff changeset
47 tState->stateContinue = tg->stateNothing;
8879eb8c64a8 remove segmentation fault
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 272
diff changeset
48 }
277
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
49 if (ccvSize == 0) {
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
50 tState->ccv = NULL;
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
51 return tState;
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
52 } else tState->ccv = (ccv*)malloc(sizeof(ccv)*ccvSize);
251
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
53 ccw = createCharClassWalker(state->cc);
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
54 int i = 0;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
55 while (hasNext(ccw)) {
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
56 CharClassPtr cc = getNext(ccw);
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
57 unsigned long begin = cc->cond.range.begin;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
58 unsigned long end = cc->cond.range.end;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
59 struct ccv *ccv = &tState->ccv[i++];
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
60 ccv->begin = begin;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
61 ccv->end = end;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
62 ccv->tState = NULL;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
63 ccv->state = cc->nextState;
248
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
64 ccv->w = cc->cond.w;
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
65 }
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
66 free(ccw);
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
67 return tState;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
68 }
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
69
277
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
70 TStatePtr nextTState(BitVector bi,TransitionGeneratorPtr tg) {
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
71 // create tSearch in next state.
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
72 StatePtr state = tg->stateArray[bi.bitContainer];
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
73 if (state == NULL) {
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
74 // on the fly subset construction.
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
75 state = createState(tg,bi);
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
76 determinize(state,tg);
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
77 tg->stateArray[bi.bitContainer] = state;
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
78 }
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
79 if (state->tState == NULL) {
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
80 generateTState(state,tg);
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
81 }
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
82 return state->tState;
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
83 }
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
84
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 void tSearch(TSValue tsv) {
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
86 next: while (tsv.buff.buffptr < tsv.buff.buffend) {
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
87 unsigned char c = *tsv.buff.buffptr++;
278
99d635926ef3 ceriumCreateAnyState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 277
diff changeset
88 // printState(tsv.current->state);
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
89 for (int i = 0; i < tsv.current->ccvSize; i++) {
248
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
90 CCVPtr ccv = &tsv.current->ccv[i];
257
ebb429c2b6a7 fix allocate state in generateTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 254
diff changeset
91 if (c<ccv->begin) {
264
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
92 tsv = tsv.current->stateSkip(tsv);
257
ebb429c2b6a7 fix allocate state in generateTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 254
diff changeset
93 goto next;
ebb429c2b6a7 fix allocate state in generateTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 254
diff changeset
94 } else if (c<=ccv->end) {
248
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
95 // range matched.
251
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
96 if (ccv->w.word) {
248
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
97 // match the word.
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
98 // if (not match) continue;
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
99 }
277
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
100 if (ccv->tState) {
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
101 tsv.current = ccv->tState;
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
102 } else {
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
103 tsv.current = nextTState(ccv->state,tsv.tg);
7b4bcc7b5ae6 nextTState implemented
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 275
diff changeset
104 ccv->tState = tsv.current;
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
105 }
264
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
106 // tsv = tsv.current->stateContinue(tsv);
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
107 goto next;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
108 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
109 }
264
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
110 tsv = tsv.current->stateSkip(tsv);
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
111 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
112 }
262
157f6886ba55 write driver of threadedSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 260
diff changeset
113
157f6886ba55 write driver of threadedSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 260
diff changeset
114 void threadedSearch(TransitionGeneratorPtr tg, Buffer buff) {
157f6886ba55 write driver of threadedSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 260
diff changeset
115 TSValue tsv;
157f6886ba55 write driver of threadedSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 260
diff changeset
116 tsv.buff = buff;
157f6886ba55 write driver of threadedSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 260
diff changeset
117 tsv.tg = tg;
266
e51cac73e42a CeriumGrep start
masa
parents: 264
diff changeset
118 tsv.result = NULL;
e51cac73e42a CeriumGrep start
masa
parents: 264
diff changeset
119 tsv.tg->stateSkip = stateSkip;
e51cac73e42a CeriumGrep start
masa
parents: 264
diff changeset
120 tsv.tg->stateMatch = stateMatch;
e51cac73e42a CeriumGrep start
masa
parents: 264
diff changeset
121 tsv.tg->stateNothing = stateNothing;
270
c82f7e7f66f7 running ts
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 268
diff changeset
122 tsv.current = generateTState(tg->stateList,tg);
263
292753bb31e4 fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 262
diff changeset
123 tSearch(tsv);
262
157f6886ba55 write driver of threadedSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 260
diff changeset
124 }