Mercurial > hg > Applications > Grep

comparison 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
comparison
equal deleted inserted replaced
246:58de1744d7a9 247:96c2507fd22d
1 #include <stdio.h>
2 #include <stdlib.h>
3
1 #include "regexParser.h" 4 #include "regexParser.h"
2 #include "subsetConstruction.h" 5 #include "subsetConstruction.h"
3 6
4 struct tsValue; 7 struct tsValue;
5 8
6 typedef struct tState { 9 typedef struct ccv {
7 State *state;
8 void stateSkip(struct tsValue);
9 int ccvSize;
10 struct ccv{
11 unsigned long begin; 10 unsigned long begin;
12 unsigned long end; 11 unsigned long end;
13 BitVector state; 12 BitVector state;
14 struct tState *tState; 13 struct tState *tState;
15 } *ccv; 14 } *CCV;
15
16 void stateSkip(TSValue tsv);
17
18 typedef struct tState {
19 State *state;
20 void stateSkip(tsValue);
21 int ccvSize;
22 CCV ccv;
16 } TState, *TStatePtr; 23 } TState, *TStatePtr;
17 24
18 typedef struct result { 25 typedef struct result {
19 unsigned char begin; 26 unsigned char begin;
20 unsigned char end; 27 unsigned char end;
22 } Result, *ResultPtr; 29 } Result, *ResultPtr;
23 30
24 typedef struct tsValue { 31 typedef struct tsValue {
25 Buffer buff; 32 Buffer buff;
26 ResultPtr result; 33 ResultPtr result;
34 State *stateArray;
27 TState *current; 35 TState *current;
28 TState *blockBegin; 36 TState *blockBegin;
29 TState *blockEnd; 37 TState *blockEnd;
30 } TSValue, *TSValuePtr; 38 } TSValue, *TSValuePtr;
31 39
32 void stateSkip(TSValue tsv) { 40 void stateSkip(TSValue tsv) {
33 tsv.buff.matchBegin = tsv.buff.buffptr; 41 tsv.buff.matchBegin = tsv.buff.buffptr;
34 tsv.current->stateSkip(tsv); 42 tsv.current->stateSkip(tsv);
35 } 43 }
36 44
45 TStatePtr generateTState(State state) {
46 TStatePtr tState = NEW(TState);
47 int ccvSize = 0;
48 CharClassWalkerPtr ccw = createCharClassWalker(state.cc);
49 while (hasNext(ccw)) {
50 CharClassPtr cc = getNext(ccw);
51 ccvSize++;
52 }
53 if (ccvSize == 0) return tState;
54 else tState->ccv = (ccv*)malloc(sizeof(ccv)*ccvSize);
55 ccw = createCharClassWalker(state.cc);
56 int i = 0;
57 while (hasNext(ccw)) {
58 CharClassPtr cc = getNext(ccw);
59 unsigned long begin = cc->cond.range.begin;
60 unsigned long end = cc->cond.range.end;
61 struct ccv *ccv = &tState->ccv[i++];
62 ccv->begin = begin;
63 ccv->end = end;
64 ccv->tState = NULL;
65 ccv->state = cc->nextState;
66 }
67 free(ccw);
68 return tState;
69 }
70
37 void tSearch(TSValue tsv) { 71 void tSearch(TSValue tsv) {
38 next: while (buff.buffptr < buff.buffend) { 72 next: while (tsv.buff.buffptr < tsv.buff.buffend) {
39 unsigned char c = *buff.buffptr++; 73 unsigned char c = *tsv.buff.buffptr++;
40 for (int i = 0; i < tsv.current->ccvSize; i++) { 74 for (int i = 0; i < tsv.current->ccvSize; i++) {
41 if (c<tsv.current->ccv[i].begin) tsv.current->stateSkip(tsv); 75 if (c<tsv.current->ccv[i].begin) tsv.current->stateSkip(tsv);
42 else if (c<=tsv.current->ccv[i].end) { 76 else if (c<=tsv.current->ccv[i].end) {
43 TStatePtr current = tsv.current->ccv[i].tState; 77 TStatePtr current = tsv.current->ccv[i].tState;
44 if (current == NULL) { 78 if (current == NULL) {
50 } 84 }
51 } 85 }
52 tsv.current->stateSkip(tsv); 86 tsv.current->stateSkip(tsv);
53 } 87 }
54 } 88 }
55
56 TStatePtr generateTState(StatePtr state) {
57 TState tState = NEW(TState);
58 int ccvSize = 0;
59 CharClassWalkerPtr ccw = createCharClassWalker(state->cc);
60 while (hasNext(ccw)) {
61 CharClassPtr cc = getNext(ccw);
62 ccvSize++;
63 }
64 if (ccvSize == 0) return tState;
65 else tState->ccv = (struct ccv*)malloc(sizeof(struct ccv)*ccvSize);
66 CharClassWalkerPtr ccw = createCharClassWalker(state->cc);
67 while (hasNext(ccw)) {
68 CharClassPtr cc = getNext(ccw);
69 unsigned long begin = cc->cond.range.begin;
70 unsigned long end = cc->cond.range.end;
71 struct ccv *ccv = &tState->ccv[i++];
72 ccv->begin = begin;
73 ccv->end = end;
74 ccv->tState = NULL;
75 ccv->state = cc->nextState;
76 }
77 free(ccw);
78 return tState;
79 }