Mercurial > hg > Applications > Grep

annotate regexParser/threadedSearch.cc @ 247:96c2507fd22d

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 Fri, 22 Jan 2016 18:37:04 +0900
parents 58de1744d7a9
children 2b1fbfb92d54
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"
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 245
diff changeset
5 #include "subsetConstruction.h"
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 245
diff changeset
6
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
7 struct tsValue;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
8
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
9 typedef struct ccv {
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
10 unsigned long begin;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
11 unsigned long end;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
12 BitVector state;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
13 struct tState *tState;
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
14 } *CCV;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
15
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
16 void stateSkip(TSValue tsv);
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
17
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
18 typedef struct tState {
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
19 State *state;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
20 void stateSkip(tsValue);
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
21 int ccvSize;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
22 CCV ccv;
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 } TState, *TStatePtr;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
24
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 typedef struct result {
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
26 unsigned char begin;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
27 unsigned char end;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
28 struct result *next;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
29 } Result, *ResultPtr;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
30
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
31 typedef struct tsValue {
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
32 Buffer buff;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
33 ResultPtr result;
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
34 State *stateArray;
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
35 TState *current;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
36 TState *blockBegin;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
37 TState *blockEnd;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
38 } TSValue, *TSValuePtr;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
39
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
40 void stateSkip(TSValue tsv) {
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
41 tsv.buff.matchBegin = tsv.buff.buffptr;
246
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 245
diff changeset
42 tsv.current->stateSkip(tsv);
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
43 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
44
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
45 TStatePtr generateTState(State state) {
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
46 TStatePtr tState = NEW(TState);
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
47 int ccvSize = 0;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
48 CharClassWalkerPtr ccw = createCharClassWalker(state.cc);
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
49 while (hasNext(ccw)) {
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
50 CharClassPtr cc = getNext(ccw);
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
51 ccvSize++;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
52 }
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
53 if (ccvSize == 0) return tState;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
54 else tState->ccv = (ccv*)malloc(sizeof(ccv)*ccvSize);
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
55 ccw = createCharClassWalker(state.cc);
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
56 int i = 0;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
57 while (hasNext(ccw)) {
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
58 CharClassPtr cc = getNext(ccw);
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
59 unsigned long begin = cc->cond.range.begin;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
60 unsigned long end = cc->cond.range.end;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
61 struct ccv *ccv = &tState->ccv[i++];
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
62 ccv->begin = begin;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
63 ccv->end = end;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
64 ccv->tState = NULL;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
65 ccv->state = cc->nextState;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
66 }
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
67 free(ccw);
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
68 return tState;
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
69 }
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
70
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 void tSearch(TSValue tsv) {
247
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
72 next: while (tsv.buff.buffptr < tsv.buff.buffend) {
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents: 246
diff changeset
73 unsigned char c = *tsv.buff.buffptr++;
245
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
74 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
75 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
76 else if (c<=tsv.current->ccv[i].end) {
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
77 TStatePtr current = tsv.current->ccv[i].tState;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 if (current == NULL) {
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
79 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
80 tsv.current->ccv[i].tState = current;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
81 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
82 tsv.current = tsv.current->ccv[i].tState;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
83 goto next;
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
84 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
85 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
86 tsv.current->stateSkip(tsv);
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
87 }
d34de5edaa96 add threadedSearch.cc
Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
parents:
diff changeset
88 }