Mercurial > hg > Applications > Grep

annotate regexParser/threadedSearch.cc @ 246:58de1744d7a9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Thu, 21 Jan 2016 19:57:48 +0900
parents d34de5edaa96
children 96c2507fd22d
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
246
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 245
diff changeset
1 #include "regexParser.h"
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 245
diff changeset
2 #include "subsetConstruction.h"
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 245
diff changeset
3
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
4 struct tsValue;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
5
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
6 typedef struct tState {
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 State *state;
246
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 245
diff changeset
8 void stateSkip(struct tsValue);
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 int ccvSize;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 struct ccv{
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 unsigned long begin;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 unsigned long end;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 BitVector state;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 struct tState *tState;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
15 } *ccv;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
16 } TState, *TStatePtr;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
17
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
18 typedef struct result {
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 unsigned char begin;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 unsigned char end;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
21 struct result *next;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 } Result, *ResultPtr;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
23
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
24 typedef struct tsValue {
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 Buffer buff;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 ResultPtr result;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 TState *current;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 TState *blockBegin;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 TState *blockEnd;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
30 } TSValue, *TSValuePtr;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
31
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 void stateSkip(TSValue tsv) {
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 tsv.buff.matchBegin = tsv.buff.buffptr;
246
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 245
diff changeset
34 tsv.current->stateSkip(tsv);
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
36
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 void tSearch(TSValue tsv) {
246
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 245
diff changeset
38 next: while (buff.buffptr < buff.buffend) {
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
39 unsigned char c = *buff.buffptr++;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 for (int i = 0; i < tsv.current->ccvSize; i++) {
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 if (c<tsv.current->ccv[i].begin) tsv.current->stateSkip(tsv);
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
42 else if (c<=tsv.current->ccv[i].end) {
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 TStatePtr current = tsv.current->ccv[i].tState;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
44 if (current == NULL) {
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
45 current = generateTState(tsv.stateArray[tsv.current->ccv[i].state.bitContainer]);
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 tsv.current->ccv[i].tState = current;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
47 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
48 tsv.current = tsv.current->ccv[i].tState;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
49 goto next;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
50 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
51 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
52 tsv.current->stateSkip(tsv);
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
53 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
54 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
55
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
56 TStatePtr generateTState(StatePtr state) {
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
57 TState tState = NEW(TState);
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
58 int ccvSize = 0;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
59 CharClassWalkerPtr ccw = createCharClassWalker(state->cc);
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
60 while (hasNext(ccw)) {
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
61 CharClassPtr cc = getNext(ccw);
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
62 ccvSize++;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
63 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 if (ccvSize == 0) return tState;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 else tState->ccv = (struct ccv*)malloc(sizeof(struct ccv)*ccvSize);
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
66 CharClassWalkerPtr ccw = createCharClassWalker(state->cc);
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
67 while (hasNext(ccw)) {
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 CharClassPtr cc = getNext(ccw);
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
69 unsigned long begin = cc->cond.range.begin;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
70 unsigned long end = cc->cond.range.end;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 struct ccv *ccv = &tState->ccv[i++];
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
72 ccv->begin = begin;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
73 ccv->end = end;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 ccv->tState = NULL;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 ccv->state = cc->nextState;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 free(ccw);
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 return tState;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 }