Mercurial > hg > Applications > Grep

annotate regexParser/threadedSearch.cc @ 264:ef95a7f1bc03

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
implement tSearch
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Wed, 27 Jan 2016 17:41:01 +0900
parents 292753bb31e4
children e51cac73e42a
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
264
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
10 TSValue stateNothing(TSValue tsv) {
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
11 return tsv;
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13
264
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
14 TSValue stateSkip(TSValue tsv) {
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
15 tsv.buff.matchBegin = tsv.buff.buffptr;
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
16 return tsv;
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
17 }
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
18
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
19 TSValue stateMatch(TSValue tsv) {
263
292753bb31e4 fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 262
diff changeset
20 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
21 puts("");
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
22 tsv.current = tsv.tg->stateList->tState;
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
23 tsv.buff.buffptr--;
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
24 tsv = stateSkip(tsv);
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
25 return tsv;
257
ebb429c2b6a7 fix allocate state in generateTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 254
diff changeset
26 }
ebb429c2b6a7 fix allocate state in generateTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 254
diff changeset
27
251
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
28 TStatePtr generateTState(StatePtr state) {
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
29 TStatePtr tState = NEW(TState);
264
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
30 tState->state = state;
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
31 state->tState = tState;
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
32 int ccvSize = 0;
251
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
33 CharClassWalkerPtr ccw = createCharClassWalker(state->cc);
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
34 while (hasNext(ccw)) {
263
292753bb31e4 fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 262
diff changeset
35 getNext(ccw);
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
36 ccvSize++;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
37 }
263
292753bb31e4 fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 262
diff changeset
38 tState->ccvSize = ccvSize;
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
39 if (ccvSize == 0) return tState;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
40 else tState->ccv = (ccv*)malloc(sizeof(ccv)*ccvSize);
251
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
41 ccw = createCharClassWalker(state->cc);
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
42 int i = 0;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
43 while (hasNext(ccw)) {
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
44 CharClassPtr cc = getNext(ccw);
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
45 unsigned long begin = cc->cond.range.begin;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
46 unsigned long end = cc->cond.range.end;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
47 struct ccv *ccv = &tState->ccv[i++];
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
48 ccv->begin = begin;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
49 ccv->end = end;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
50 ccv->tState = NULL;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
51 ccv->state = cc->nextState;
248
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
52 ccv->w = cc->cond.w;
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
53 }
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
54 free(ccw);
263
292753bb31e4 fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 262
diff changeset
55 if (state->accept) {
292753bb31e4 fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 262
diff changeset
56 tState->stateSkip = stateMatch;
264
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
57 tState->stateContinue = stateNothing;
263
292753bb31e4 fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 262
diff changeset
58 } else {
292753bb31e4 fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 262
diff changeset
59 tState->stateSkip = stateSkip;
264
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
60 tState->stateContinue = stateNothing;
263
292753bb31e4 fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 262
diff changeset
61 }
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
62 return tState;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
63 }
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
64
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 void tSearch(TSValue tsv) {
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
66 next: while (tsv.buff.buffptr < tsv.buff.buffend) {
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
67 unsigned char c = *tsv.buff.buffptr++;
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 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
69 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
70 if (c<ccv->begin) {
264
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
71 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
72 goto next;
ebb429c2b6a7 fix allocate state in generateTransition
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 254
diff changeset
73 } else if (c<=ccv->end) {
248
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
74 // range matched.
251
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
75 if (ccv->w.word) {
248
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
76 // match the word.
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
77 // if (not match) continue;
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
78 }
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
79 TStatePtr current = ccv->tState;
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 if (current == NULL) {
248
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
81 // create tSearch in next state.
251
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 248
diff changeset
82 StatePtr state = tsv.tg->stateArray[ccv->state.bitContainer];
248
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
83 if (state == NULL) {
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
84 // on the fly subset construction.
252
2b276fdd99bd remove error (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 251
diff changeset
85 state = createState(tsv.tg,state->bitState);
2b276fdd99bd remove error (not working)
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 251
diff changeset
86 tsv.tg->stateArray[state->bitState.bitContainer] = state;
248
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
87 determinize(state,tsv.tg);
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
88 }
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
89 if (state->tState == NULL) {
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
90 current = generateTState(state);
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
91 ccv->tState = current;
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
92 } else {
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
93 ccv->tState = state->tState;
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
94 }
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
95 }
248
2b1fbfb92d54 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 247
diff changeset
96 tsv.current = ccv->tState;
264
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
97 // tsv = tsv.current->stateContinue(tsv);
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
98 goto next;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
99 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
100 }
264
ef95a7f1bc03 implement tSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 263
diff changeset
101 tsv = tsv.current->stateSkip(tsv);
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
102 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
103 }
262
157f6886ba55 write driver of threadedSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 260
diff changeset
104
157f6886ba55 write driver of threadedSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 260
diff changeset
105 void threadedSearch(TransitionGeneratorPtr tg, Buffer buff) {
157f6886ba55 write driver of threadedSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 260
diff changeset
106 TSValue tsv;
157f6886ba55 write driver of threadedSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 260
diff changeset
107 tsv.buff = buff;
157f6886ba55 write driver of threadedSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 260
diff changeset
108 tsv.tg = tg;
157f6886ba55 write driver of threadedSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 260
diff changeset
109 tsv.current = generateTState(tg->stateList);
263
292753bb31e4 fix Makefile
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 262
diff changeset
110 tSearch(tsv);
262
157f6886ba55 write driver of threadedSearch
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 260
diff changeset
111 }