--- a/paper/cbc.tex	Mon Jan 23 10:39:15 2017 +0900
+++ b/paper/cbc.tex	Mon Jan 23 15:42:08 2017 +0900
@@ -224,3 +224,39 @@
         \label{fig:non-destructive-rbtree}
     \end{center}
 \end{figure}
+
+CbC を用いて赤黒木を実装する際の問題として、関数の呼び出しスタックが存在しないため、関数の再帰呼び出しによって木が辿れないことがある。
+経路を辿るためにはノードに親への参照を持たせるか、挿入・削除時に辿った経路を記憶する必要がある。
+ノードが親への参照を持つ非破壊木構造は共通部分の共有が行なえないため、辿った経路を記憶する方法を使う。
+経路の記憶にはスタックを用い、スタックは Meta DataSegment に保持させる。
+
+赤黒木を格納する DataSegment と Meta DataSegment の定義をリスト\ref{src:rbtree-context}に示す。
+経路の記憶に用いるスタックは Meta DataSegment である Context 内部の \verb/node_stack/ である。
+DataSegment は各ノード情報を持つ \verb/Node/構造体と、赤黒木を格納する \verb/Tree/構造体、挿入などで操作中の一時的な木を格納する \verb/Traverse/共用体などがある。
+
+\lstinputlisting[label=src:rbtree-context, caption=赤黒木の DataSegment と Meta DataSegment] {src/rbtreeContext.h}
+
+Meta DataSegment を初期化する Meta CodeSegment initLLRBContext をリスト\ref{src:init-rbtree-context}に示す。
+この Meta CodeSegment ではメモリ領域の確保、CodeSegment 名と CodeSegment の実体の対応表の作成などを行なう。
+メモリ領域はプログラムの起動時に一定数のメモリを確保し、ヒープとして \verb/heap/ フィールドに保持させる。
+CodeSegment 名と CodeSegment の実体との対応は、enum で定義された CodeSegment 名の添字へと CodeSegment の関数ポインタを代入することにより持つ。
+例えば \verb/Put/ の実体は \verb/put_stub/ である。
+他にも DataSegment の初期化(リスト\ref{src:init-rbtree-context} 34-48)とスタックの初期化(リスト\ref{src:init-rbtree-context} 50-51)を行なう。
+
+\lstinputlisting[label=src:init-rbtree-context, caption=赤黒木の Meta DataSegment の初期化を行なう Meta CodeSegment ] {src/initLLRBContext.c}
+
+実際の赤黒木の実装に用いられている Meta CodeSegment の一例をリスト\ref{src:rbtree-insert-case-2}に示す。
+Meta CodeSegment \verb/insertCase2/ は要素を挿入した場合に呼ばれる Meta CodeSegment の一つであり、親ノードの色によって処理を変える。
+まず、色を確認するために経路を記憶しているスタックから親の情報を取り出す。
+親の色が黒ならば処理を終了し、次の CodeSegment へと軽量継続する(リスト\ref{src:rbtree-insert-case-2} 5-8)。
+親の色が赤であるならばさらに処理を続行して \verb/InsertCase3/ へと軽量継続する。
+ここで、経路情報を再現するためにスタックへと親を再代入してから軽量継続を行なっている。
+なお、Meta CodeSegment でも Context から DataSegment を展開する処理は stub によって行なわれる(リスト\ref{src:rbtree-insert-case-2} 14-16)。
+
+\lstinputlisting[label=src:rbtree-insert-case-2, caption=赤黒木の実装に用いられている Meta CodeSegment例] {src/insertCase2.c}
+
+
+% TODO: akasha context case x の解説くらい
+% TODO: akasha context の初期化
+% TODO: verification の assert
+% TODO: akasha の結果

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/src/initLLRBContext.c	Mon Jan 23 15:42:08 2017 +0900
@@ -0,0 +1,53 @@
+__code initLLRBContext(struct Context* context, int num) {
+    context->heapLimit = sizeof(union Data)*ALLOCATE_SIZE;
+    context->code = malloc(sizeof(__code*)*ALLOCATE_SIZE);
+    context->data = malloc(sizeof(union Data*)*ALLOCATE_SIZE);
+    context->heapStart = malloc(context->heapLimit);
+
+    context->codeNum = Exit;
+
+    context->code[Code1]      = code1_stub;
+    context->code[Code2]      = code2_stub;
+    context->code[Code3]      = code3_stub;
+    context->code[Code4]      = code4;
+    context->code[Code5]      = code5;
+    context->code[Find]       = find;
+    context->code[Not_find]   = not_find;
+    context->code[Code6]      = code6;
+    context->code[Put]        = put_stub;
+    context->code[Replace]    = replaceNode_stub;
+    context->code[Insert]     = insertNode_stub;
+    context->code[RotateL]    = rotateLeft_stub;
+    context->code[RotateR]    = rotateRight_stub;
+    context->code[InsertCase1]   = insert1_stub;
+    context->code[InsertCase2]   = insert2_stub;
+    context->code[InsertCase3]   = insert3_stub;
+    context->code[InsertCase4]   = insert4_stub;
+    context->code[InsertCase4_1] = insert4_1_stub;
+    context->code[InsertCase4_2] = insert4_2_stub;
+    context->code[InsertCase5]   = insert5_stub;
+    context->code[StackClear]    = stackClear_stub;
+    context->code[Exit]       = exit_code;
+
+    context->heap = context->heapStart;
+
+    context->data[Allocate] = context->heap;
+    context->heap += sizeof(struct Allocate);
+
+    context->data[Tree] = context->heap;
+    context->heap += sizeof(struct Tree);
+
+    context->data[Node] = context->heap;
+    context->heap += sizeof(struct Node);
+
+    context->dataNum = Node;
+
+    struct Tree* tree = &context->data[Tree]->tree;
+    tree->root = 0;
+    tree->current = 0;
+    tree->deleted = 0;
+
+    context->node_stack = stack_init(sizeof(struct Node*), 100);
+    context->code_stack = stack_init(sizeof(enum Code), 100);
+}
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/src/insertCase2.c	Mon Jan 23 15:42:08 2017 +0900
@@ -0,0 +1,17 @@
+__code insertCase2(struct Context* context, struct Node* current) {
+    struct Node* parent;
+    stack_pop(context->node_stack, &parent);
+
+    if (parent->color == Black) {
+        stack_pop(context->code_stack, &context->next);
+        goto meta(context, context->next);
+    }
+
+    stack_push(context->node_stack, &parent);
+    goto meta(context, InsertCase3);
+}
+
+__code insert2_stub(struct Context* context) {
+    goto insertCase2(context, context->data[Tree]->tree.current);
+}
+

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/paper/src/rbtreeContext.h	Mon Jan 23 15:42:08 2017 +0900
@@ -0,0 +1,50 @@
+// DataSegments for Red-Black Tree
+union Data {
+    struct Comparable { // interface
+        enum Code compare;
+        union Data* data;
+    } compare;
+    struct Count {
+        enum Code next;
+        long i;
+    } count;
+    struct Tree {
+        enum Code next;
+        struct Node* root;
+        struct Node* current;
+        struct Node* deleted;
+        int result;
+    } tree;
+    struct Node {
+        // need to tree
+        enum Code next;
+        int key; // comparable data segment
+        int value;
+        struct Node* left;
+        struct Node* right;
+        // need to balancing
+        enum Color {
+            Red,
+            Black,
+        } color;
+    } node;
+    struct Allocate {
+        enum Code next;
+        long size;
+    } allocate;
+};
+
+
+// Meta DataSegment
+struct Context {
+    enum Code next;
+    int codeNum;
+    __code (**code) (struct Context*);
+    void* heapStart;
+    void* heap;
+    long heapLimit;
+    int dataNum;
+    stack_ptr code_stack;
+    stack_ptr node_stack;
+    union Data **data;
+};