changeset 245:d34de5edaa96

add threadedSearch.cc
author Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
date Thu, 21 Jan 2016 19:35:33 +0900
parents a3cddb32b87f
children 58de1744d7a9
files regexParser/Makefile regexParser/threadedSearch.cc
diffstat 2 files changed, 77 insertions(+), 0 deletions(-) [+]
line wrap: on
line diff
--- a/regexParser/Makefile	Thu Jan 21 18:11:59 2016 +0900
+++ b/regexParser/Makefile	Thu Jan 21 19:35:33 2016 +0900
@@ -85,6 +85,7 @@
 	./regexParser -regex '[d-ga-db-e]'
 	./regexParser -regex '[d-gh-ja-e]'
 	./regexParser -regex 'abcd'
+	./regexParser -regex '([a-c]x]|[d-f]y)'
 
 test2: regexParser
 	./regexParser -subset -regex '(a|b)*a(a|b)(a|b)'
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/regexParser/threadedSearch.cc	Thu Jan 21 19:35:33 2016 +0900
@@ -0,0 +1,76 @@
+struct tsValue;
+
+typedef struct tState {
+    State *state;
+    void stateSkip(struct TSValue);
+    int ccvSize;
+    struct ccv{
+        unsigned long begin;
+        unsigned long end;
+        BitVector state;
+        struct tState *tState;
+    } *ccv;
+} TState, *TStatePtr;
+
+typedef struct result {
+    unsigned char begin;
+    unsigned char end;
+    struct result *next;
+} Result, *ResultPtr;
+
+typedef struct tsValue {
+    Buffer buff;
+    ResultPtr result;
+    TState *current;
+    TState *blockBegin;
+    TState *blockEnd;
+} TSValue, *TSValuePtr;
+
+void stateSkip(TSValue tsv) {
+    tsv.buff.matchBegin = tsv.buff.buffptr;
+    tsv.(tsv);
+}
+
+void tSearch(TSValue tsv) {
+    next; while (buff.buffptr < buff.buffend) {
+        unsigned char c = *buff.buffptr++;
+        for (int i = 0; i < tsv.current->ccvSize; i++) {
+            if (c<tsv.current->ccv[i].begin) tsv.current->stateSkip(tsv);
+            else if (c<=tsv.current->ccv[i].end) {
+                TStatePtr current = tsv.current->ccv[i].tState;
+                if (current == NULL) {
+                    current = generateTState(tsv.stateArray[tsv.current->ccv[i].state.bitContainer]);
+                    tsv.current->ccv[i].tState = current;
+                }
+                tsv.current = tsv.current->ccv[i].tState;
+                goto next;
+            }
+        }
+        tsv.current->stateSkip(tsv);
+    }
+}
+
+TStatePtr generateTState(StatePtr state) {
+    TState tState = NEW(TState);
+    int ccvSize = 0;
+    CharClassWalkerPtr ccw = createCharClassWalker(state->cc);
+    while (hasNext(ccw)) {
+        CharClassPtr cc = getNext(ccw);
+        ccvSize++;
+    }    
+    if (ccvSize == 0) return tState;
+    else tState->ccv = (struct ccv*)malloc(sizeof(struct ccv)*ccvSize);
+    CharClassWalkerPtr ccw = createCharClassWalker(state->cc);
+    while (hasNext(ccw)) {
+        CharClassPtr cc = getNext(ccw);
+        unsigned long begin = cc->cond.range.begin;
+        unsigned long end = cc->cond.range.end;
+        struct ccv *ccv = &tState->ccv[i++];
+        ccv->begin = begin;
+        ccv->end = end;
+        ccv->tState = NULL;
+        ccv->state = cc->nextState;
+    }
+    free(ccw);
+    return tState;
+}