# HG changeset patch
# User Masataka Kohagura <kohagura@cr.ie.u-ryukyu.ac.jp>
# Date 1455852054 -32400
# Node ID 7e40d0e6fba04e6a277a06a43dd70df56a443a19
# Parent  8223a72a80e5ff0a6e53ebb2b1ff3193070b2a5f
add tSearch generateTState source

diff -r 8223a72a80e5 -r 7e40d0e6fba0 slide/s6/index.html
--- a/slide/s6/index.html	Fri Feb 19 11:49:29 2016 +0900
+++ b/slide/s6/index.html	Fri Feb 19 12:20:54 2016 +0900
@@ -434,6 +434,43 @@
       </div>
 
       <div class='slide'>
+    <h2>文字クラスの構造体</h2>
+<pre>
+typedef struct utf8Range {
+    unsigned long begin;
+    unsigned long end;
+} RangeList , *RangeListPtr;
+
+typedef struct condition {
+    RangeList range;
+    Word w;
+} Condition, *ConditionList;
+
+typedef struct charClass {
+    struct charClass *left;
+    struct charClass *right;
+    Condition cond;
+    int stateNum;
+    BitVector nextState;
+} CharClass, *CharClassPtr;
+</pre>
+    <ul>
+    <li>
+    正規表現木の文字ノードもしくは文字クラスノードこの構造体を持っている。
+    </li>
+    <li>
+    文字クラスは二分木で構築されている。
+    </li>
+    <li>
+    文字クラスの範囲は Condition 内の RangeList の begin と end に設定される。
+    </li>
+    <li>
+    その Condition の範囲内の文字の入力があれば、次の状態 nextState に遷移する。
+    </li>
+    </ul>
+      </div>
+
+      <div class='slide'>
     <h2>正規表現木をオートマトンの状態遷移に沿って状態割当</h2>
     <object data="images/regex/allostate.svg" width="50%"  type="image/svg+xml"></object><br>
 
@@ -498,13 +535,25 @@
 
     <ul>
     <li>
-    tgv は
+    TGValue は asterisk、startState、endState それぞれの状態を持っている。
+    </li>
+    <li>
+    正規表現木を二度 generateTransition に通す。
+    </li>
+    <li>
+    それらの状態を正規表現木に対して Tree walk しながら状態を割り振っていく。
     </li>
     <li>
+    '+' のとき、
     </li>
     <li>
+    '|' のとき、
     </li>
     <li>
+    '*' のとき、
+    </li>
+    <li>
+    文字または文字クラスのとき、
     </li>
     </ul>
       </div>
@@ -555,43 +604,6 @@
       </div>
 
       <div class='slide'>
-    <h2>文字クラスの構造体</h2>
-<pre>
-typedef struct utf8Range {
-    unsigned long begin;
-    unsigned long end;
-} RangeList , *RangeListPtr;
-
-typedef struct condition {
-    RangeList range;
-    Word w;
-} Condition, *ConditionList;
-
-typedef struct charClass {
-    struct charClass *left;
-    struct charClass *right;
-    Condition cond;
-    int stateNum;
-    BitVector nextState;
-} CharClass, *CharClassPtr;
-</pre>
-    <ul>
-    <li>
-    正規表現木の文字ノードもしくは文字クラスノードこの構造体を持っている。
-    </li>
-    <li>
-    文字クラスは二分木で構築されている。
-    </li>
-    <li>
-    文字クラスの範囲は Condition 内の RangeList の begin と end に設定される。
-    </li>
-    <li>
-    その Condition の範囲内の文字の入力があれば、次の状態 nextState に遷移する。
-    </li>
-    </ul>
-      </div>
-
-      <div class='slide'>
     <h2>Subset Construction</h2>
     <object data="images/regex/sc.svg" width="50%"  type="image/svg+xml"></object><br>
     <ul>
@@ -604,12 +616,110 @@
     </ul>
       </div>
 
-<!--
       <div class='slide'>
-    <h2>cc tree merge pattern</h2>
-    <object data="images/regex/CharClassMergePattern.svg" width="50%"  type="image/svg+xml"></object><br>
+    <h2>並列処理時の正規表現のマッチング</h2>
+<pre>
+typedef struct tState {
+    State *state;
+    tsValue (*stateSkip)(tsValue);
+    tsValue (*stateMatch)(tsValue);
+    int ccvSize;
+    CCVPtr ccv;
+} TState, *TStatePtr;
+
+TStatePtr generateTState(StatePtr state, TransitionGeneratorPtr tg) {
+    TStatePtr tState = NEW(TState);
+    tState->state = state;
+    int ccvSize = 0;
+    CharClassWalkerPtr ccw = createCharClassWalker(state->cc);
+    while (hasNext(ccw)) {
+        getNext(ccw);
+        ccvSize++;
+    }
+    tState->ccvSize = ccvSize;
+    if (state->accept) {
+        tState->stateMatch  = tg->stateMatch;
+        tState->stateSkip  = tg->stateSkip;
+    } else {
+        tState->stateMatch  = tg->stateNothing;
+        tState->stateSkip  = tg->stateSkip;
+    }
+    if (ccvSize == 0) {
+        tState->ccv = NULL;
+        state->tState = tState;
+        return tState;
+    } else tState->ccv = (ccv*)malloc(sizeof(ccv)*ccvSize);
+    ccw = createCharClassWalker(state->cc);
+    int i = 0;
+    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;
+        ccv->w = cc->cond.w;
+    }
+    free(ccw);
+    state->tState = tState;
+    return tState;
+}
+</pre>
+
+<ul>
+<li>
+tState
+</li>
+<li>
+</li>
+<li>
+</li>
+</ul>
       </div>
--->
+
+
+      <div class='slide'>
+    <h2>並列処理時の正規表現のマッチング</h2>
+<pre>
+TSValue tSearch(TSValue tsv) {
+    next: while (tsv.buff.buffptr < tsv.buff.buffend) {
+        tsv = tsv.current->stateMatch(tsv);
+        if (tsv.current->ccvSize==0) {
+            tsv.current = tsv.tg->stateStart->tState;
+        }
+        unsigned char c = *tsv.buff.buffptr++;
+        for (int i = 0; i < tsv.current->ccvSize; i++) {
+            CCVPtr ccv = &tsv.current->ccv[i];
+            if (c<ccv->begin) {
+                tsv.current = tsv.tg->stateStart->tState;
+                tsv = tsv.current->stateSkip(tsv);
+                goto next;
+            } else if (c<=ccv->end) {
+                // range matched.
+                if (ccv->w.word) {
+                    // match the word.
+                    // if (not match) continue;
+                }
+                if (ccv->tState) {
+                    tsv.current = ccv->tState;
+                } else {
+                    tsv.current = nextTState(ccv->state,tsv.tg);
+                    ccv->tState = tsv.current;
+                }
+                goto next;
+            }
+        }
+        tsv.current = tsv.tg->stateStart->tState;
+        tsv = tsv.current->stateSkip(tsv);
+    }
+    return tsv;
+}
+</pre>
+      </div>
+
+
   <div class='slide'>
 <h2>正規表現の整合性</h2>
 <object data="images/regex/regexdivide.svg" width="50%"  type="image/svg+xml"></object><br>