Binary file paper/vmpcbc.pdf has changed

--- a/paper/vmpcbc.tex	Thu Jul 07 19:32:23 2016 +0900
+++ b/paper/vmpcbc.tex	Fri Jul 08 11:17:21 2016 +0900
@@ -5,6 +5,8 @@
 \usepackage[dvipdfmx]{graphicx}
 \usepackage{latexsym}
 \usepackage{listings}
+\usepackage[font=bf,skip=\baselineskip]{caption}
+\captionsetup[lstlisting]{font={small,tt}}
 \lstset{
   language={C},
   basicstyle={\scriptsize},
@@ -617,7 +619,356 @@
 
 \end{thebibliography}
 
-\appendix % TODO: red-black tree のコード
+\appendix
+
+% {{{ CbCで記述された赤黒木のコード
+
+\section{CbCで記述された赤黒木のコード}
+CbCで記述された赤黒木のソースコードをCode\ref{src:rbtree-full} に示す。
+
+
+\begin{lstlisting}[ caption={CbCで記述された赤黒木}, label=src:rbtree-full  ]
+enum Relational {
+    EQ,
+    GT,
+    LT,
+};
+
+enum UniqueData {
+    Allocate,
+    Tree,
+    Node,
+};
+
+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;
+};
+
+union Data {
+    struct Comparable { // inteface
+        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;
+};
+
+
+__code put(struct Context* context, struct Tree* tree, struct Node* root, struct Allocate* allocate) {
+    allocate->size = sizeof(struct Node);
+    allocator(context);
+
+    stack_push(context->code_stack, &context->next);
+
+    context->next = StackClear;
+    stack_push(context->code_stack, &context->next);
+
+    tree->root = &context->data[context->dataNum]->node;
+
+    if (root) {
+        tree->current = root;
+        compare(context, tree, tree->current->key, context->data[Node]->node.key);
+
+        goto meta(context, Replace);
+    }
+
+    goto meta(context, Insert);
+}
+
+__code put_stub(struct Context* context) {
+    goto put(context, &context->data[Tree]->tree, context->data[Tree]->tree.root, &context->data[Allocate]->allocate);
+}
+
+__code replaceNode(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) {
+    *newNode = *oldNode;
+    stack_push(context->node_stack, &newNode);
+
+    if (result == EQ) {
+        newNode->value = context->data[Node]->node.value;
+
+        stack_pop(context->code_stack, &context->next);
+        goto meta(context, context->next);
+    } else if (result == GT) {
+        tree->current = oldNode->right;
+        newNode->right = context->heap;
+    } else {
+        tree->current = oldNode->left;
+        newNode->left = context->heap;
+    }
+
+    context->data[Allocate]->allocate.size = sizeof(struct Node);
+    allocator(context);
+
+    if (tree->current) {
+        compare(context, tree, tree->current->key, context->data[Node]->node.key);
+        goto meta(context, Replace);
+    }
+
+    goto meta(context, Insert);
+}
+
+__code replaceNode_stub(struct Context* context) {
+    goto replaceNode(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result);
+}
+
+__code insertNode(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) {
+    node->color = Red;
+    *newNode = *node;
+
+    tree->current = newNode;
+
+    goto meta(context, InsertCase1);
+}
+
+__code insertNode_stub(struct Context* context) {
+    goto insertNode(context, &context->data[Tree]->tree, &context->data[Node]->node, &context->data[context->dataNum]->node);
+}
+
+__code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) {
+    if (!isEmpty(context->node_stack))
+        goto meta(context, InsertCase2);
+
+    tree->root->color = Black;
+
+    stack_pop(context->code_stack, &context->next);
+    goto meta(context, context->next);
+}
+
+__code insert1_stub(struct Context* context) {
+    goto insertCase1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+}
+
+__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);
+}
+
+__code insertCase3(struct Context* context, struct Tree* tree, struct Node* current) {
+    struct Node* parent;
+    struct Node* uncle;
+    struct Node* grandparent;
+
+    stack_pop(context->node_stack, &parent);
+    stack_pop(context->node_stack, &grandparent);
+
+    if (grandparent->left == parent)
+        uncle = grandparent->right;
+    else
+        uncle = grandparent->left;
+
+    if (uncle && (uncle->color == Red)) {
+        parent->color = Black;
+        uncle->color = Black;
+        grandparent->color = Red;
+        tree->current = grandparent;
+        goto meta(context, InsertCase1);
+    }
+
+    stack_push(context->node_stack, &grandparent);
+    stack_push(context->node_stack, &parent);
+
+    goto meta(context, InsertCase4);
+}
+
+__code insert3_stub(struct Context* context) {
+    goto insertCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+}
+
+__code insertCase4(struct Context* context, struct Tree* tree, struct Node* current) {
+    struct Node* parent;
+    struct Node* grandparent;
+
+    stack_pop(context->node_stack, &parent);
+    stack_pop(context->node_stack, &grandparent);
+
+    stack_push(context->node_stack, &grandparent);
+
+    tree->current = parent;
+
+    if ((current == parent->right) && (parent == grandparent->left)) {
+        context->next = InsertCase4_1;
+
+        stack_push(context->code_stack, &context->next);
+        goto meta(context, RotateL);
+    } else if ((current == parent->left) && (parent == grandparent->right)) {
+        context->next = InsertCase4_2;
+
+        stack_push(context->code_stack, &context->next);
+        goto meta(context, RotateR);
+    }
+
+    stack_push(context->node_stack, &parent);
+    tree->current = current;
+    goto meta(context, InsertCase5);
+}
+
+__code insert4_stub(struct Context* context) {
+    goto insertCase4(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+}
+
+__code insertCase4_1(struct Context* context, struct Tree* tree) {
+    stack_push(context->node_stack, &tree->current);
+    tree->current = tree->current->left;
+    goto meta(context, InsertCase5);
+}
+
+__code insert4_1_stub(struct Context* context) {
+    goto insertCase4_1(context, &context->data[Tree]->tree);
+}
+
+__code insertCase4_2(struct Context* context, struct Tree* tree) {
+    stack_push(context->node_stack, &tree->current);
+    tree->current = tree->current->right;
+    goto meta(context, InsertCase5);
+}
+
+__code insert4_2_stub(struct Context* context) {
+    goto insertCase4_2(context, &context->data[Tree]->tree);
+}
+
+__code insertCase5(struct Context* context, struct Tree* tree, struct Node* current) {
+    struct Node* parent;
+    struct Node* grandparent;
+
+    stack_pop(context->node_stack, &parent);
+    stack_pop(context->node_stack, &grandparent);
+
+    parent->color = Black;
+    grandparent->color = Red;
+
+    tree->current = grandparent;
+
+    if ((current == parent->left) && (parent == grandparent->left))
+        goto meta(context, RotateR);
+    else
+        goto meta(context, RotateL);
+}
+
+__code insert5_stub(struct Context* context) {
+    goto insertCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+}
+
+__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree) {
+    struct Node* tmp = node->right;
+    struct Node* parent = 0;
+
+    stack_pop(context->node_stack, &parent);
+
+    if (parent) {
+        if (node == parent->left)
+            parent->left = tmp;
+        else
+            parent->right = tmp;
+    } else {
+        tree->root = tmp;
+    }
+
+    stack_push(context->node_stack, &parent);
+
+    node->right = tmp->left;
+    tmp->left = node;
+    tree->current = tmp;
+
+    stack_pop(context->code_stack, &context->next);
+    goto meta(context, context->next);
+}
+
+__code rotateLeft_stub(struct Context* context) {
+    goto rotateLeft(context, context->data[Tree]->tree.current, &context->data[Tree]->tree);
+}
+
+__code rotateRight(struct Context* context, struct Node* node, struct Tree* tree) {
+    struct Node* tmp = node->left;
+    struct Node* parent = 0;
+
+    stack_pop(context->node_stack, &parent);
+
+    if (parent) {
+        if (node == parent->left)
+            parent->left = tmp;
+        else
+            parent->right = tmp;
+    } else {
+        tree->root = tmp;
+    }
+
+    stack_push(context->node_stack, &parent);
+
+    node->left = tmp->right;
+    tmp->right = node;
+    tree->current = tmp;
+
+    stack_pop(context->code_stack, &context->next);
+    goto meta(context, context->next);
+}
+
+__code rotateRight_stub(struct Context* context) {
+    goto rotateRight(context, context->data[Tree]->tree.current, &context->data[Tree]->tree);
+}
+
+__code stackClear(struct Context* context, stack_ptr node_stack, struct Tree* tree) {
+    if (stack_pop(node_stack, &tree->current) == 0)
+        goto meta(context, StackClear);
+
+    tree->current = 0;
+
+    stack_pop(context->code_stack, &context->next);
+    goto meta(context, context->next);
+}
+
+__code stackClear_stub(struct Context* context) {
+    goto stackClear(context, context->node_stack, &context->data[Tree]->tree);
+}
+\end{lstlisting}
+
+% }}}
 
 \begin{biography}
 \profile{n}{比嘉健太}{1992年生。2015年琉球大学工学部情報工学科卒業。2015年琉球大学大学院理工学研究科情報工学専攻入学。}