Mercurial > hg > Members > innparusu > Gears

changeset 83:c13575c3dbe9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
use stack
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Thu, 07 Jan 2016 08:20:03 +0900
parents 69d0637e52fd
children f9487d7ea533 e06e1a9e569e
files src/llrb/llrb.c src/llrb/llrbContext.c src/llrb/llrbContext.h src/llrb/main.c
diffstat 4 files changed, 435 insertions(+), 412 deletions(-) [+]
line wrap: on
line diff
--- a/src/llrb/llrb.c	Fri Dec 11 15:07:10 2015 +0900
+++ b/src/llrb/llrb.c	Thu Jan 07 08:20:03 2016 +0900
@@ -14,6 +14,9 @@
     
     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) {
@@ -32,6 +35,7 @@
 
 __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;
@@ -49,12 +53,10 @@
     allocator(context);
 
     if (tree->current) {
-        tree->current->parent = newNode;
         compare(context, tree, tree->current->key, context->data[Node]->node.key);
         goto meta(context, Replace);
     }
     
-    tree->current = newNode;
     goto meta(context, Insert);
 }
 
@@ -65,7 +67,6 @@
 __code insertNode(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) {
     node->color = Red;
     *newNode = *node;
-    newNode->parent = tree->current;
     
     tree->current = newNode;
 
@@ -77,11 +78,10 @@
 }
 
 __code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) {
-    if (current->parent)
+    if (!isEmpty(context->node_stack))
         goto meta(context, InsertCase2);
 
     tree->root->color = Black;
-    tree->current = 0;
 
     stack_pop(context->code_stack, &context->next);
     goto meta(context, context->next);
@@ -92,11 +92,15 @@
 }
 
 __code insertCase2(struct Context* context, struct Node* current) {
-    if (current->parent->color == Black) {
+    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);
 }
 
@@ -105,22 +109,29 @@
 }
 
 __code insertCase3(struct Context* context, struct Tree* tree, struct Node* current) {
+    struct Node* parent;
     struct Node* uncle;
-    struct Node* grandparent = current->parent->parent;
+    struct Node* grandparent;
 
-    if (grandparent->left == current->parent)
+    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)) {
-        current->parent->color = Black;
+        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);
 }
 
@@ -128,29 +139,40 @@
     goto insertCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
 }
 
-__code insertCase4(struct Context* context, struct Node* current) {
-    struct Node* grandparent = current->parent->parent;
+__code insertCase4(struct Context* context, struct Tree* tree, struct Node* current) {
+    struct Node* parent;
+    struct Node* grandparent;
 
-    if ((current == current->parent->right) && (current->parent == grandparent->left)) {
+    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 == current->parent->left) && (current->parent == grandparent->right)) {
+    } 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.current);
+    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);
 }
@@ -160,6 +182,7 @@
 }   
 
 __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);
 }
@@ -169,15 +192,18 @@
 }   
 
 __code insertCase5(struct Context* context, struct Tree* tree, struct Node* current) {
-    current->parent->color = Black;
-    current->parent->parent->color = Red;
-
-    tree->current = current->parent->parent;
+    struct Node* parent;
+    struct Node* grandparent;
 
-    context->next = InsertCase5_1;
-    stack_push(context->code_stack, &context->next);
+    stack_pop(context->node_stack, &parent);
+    stack_pop(context->node_stack, &grandparent);
     
-    if ((current == current->parent->left) && (current->parent == current->parent->parent->left))
+    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);
@@ -187,39 +213,25 @@
     goto insertCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
 }
 
-__code insertCase5_1(struct Context* context, struct Tree* tree) {
-    tree->current = NULL;
-
-    stack_pop(context->code_stack, &context->next);
-    goto meta(context, context->next);
-}
-
-__code insert5_1_stub(struct Context* context) {
-    goto insertCase5_1(context, &context->data[context->dataNum]->tree);
-}
-
 __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 (node->parent) {
-        if (node == node->parent->left)
-            node->parent->left = tmp;
+    if (parent) {
+        if (node == parent->left)
+            parent->left = tmp;
         else
-            node->parent->right = tmp;
+            parent->right = tmp;
     } else {
         tree->root = tmp;
     }
 
-    if (tmp)
-        tmp->parent = node->parent;
+    stack_push(context->node_stack, &parent);
     
     node->right = tmp->left;
-
-    if (tmp->left)
-        tmp->left->parent = node;
-
     tmp->left = node;
-    node->parent = tmp;
     tree->current = tmp;
     
     stack_pop(context->code_stack, &context->next);
@@ -232,26 +244,23 @@
 
 __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 (node->parent) {
-        if (node == node->parent->left)
-            node->parent->left = tmp;
+    if (parent) {
+        if (node == parent->left)
+            parent->left = tmp;
         else
-            node->parent->right = tmp;
+            parent->right = tmp;
     } else {
         tree->root = tmp;
     }
 
-    if (tmp)
-        tmp->parent = node->parent;
-
+    stack_push(context->node_stack, &parent);
+    
     node->left = tmp->right;
-
-    if (tmp->right)
-        tmp->right->parent = node;
-    
     tmp->right = node;
-    node->parent = tmp;
     tree->current = tmp;
     
     stack_pop(context->code_stack, &context->next);
@@ -262,383 +271,398 @@
     goto rotateRight(context, context->data[Tree]->tree.current, &context->data[Tree]->tree);
 }
 
-__code get(struct Context* context, struct Tree* tree) {
-    if (tree->root) {
-        tree->current = tree->root;
-
-        goto meta(context, Search);
-    }
-
-    stack_pop(context->code_stack, &context->next);
-    goto meta(context, context->next);
-}
-
-__code get_stub(struct Context* context) {
-    goto get(context, &context->data[Tree]->tree);
-}
-
-__code search(struct Context* context, struct Tree* tree, struct Node* node) {
-    compare(context, tree, tree->current->key, node->key);
-    
-    if (tree->result == EQ) {
-        *node = *tree->current;
-        
-        goto meta(context, context->next);
-    } else if (tree->result == GT) {
-        tree->current = tree->current->right;
-    } else {
-        tree->current = tree->current->left;
-    }
-        
-    if (tree->current)
-        goto meta(context, Search);
-
-    stack_pop(context->code_stack, &context->next);
-    goto meta(context, context->next);
-}
-
-__code search_stub(struct Context* context) {
-    goto search(context, &context->data[Tree]->tree, &context->data[Node]->node);
-}
-
-__code delete(struct Context* context, struct Tree* tree) {
-    if (tree->root) {
-        stack_push(context->code_stack, &context->next);
-        context->next = Delete1;
-        goto meta(context, Get);
-    }
-
-    goto meta(context, context->next);
-}
-
-__code delete_stub(struct Context* context) {
-    goto delete(context, &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);
 
-__code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) {
-    allocate->size = sizeof(struct Node);
-    allocator(context);
-    
-    struct Node* root = tree->root;
-
-    tree->root = &context->data[context->dataNum]->node;
-    tree->current = root;
-
-    compare(context, tree, tree->current->key, context->data[Node]->node.key);
-    
-    goto meta(context, Replace_d1);
-}
-
-__code delete1_stub(struct Context* context) {
-    goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate);
-}
-
-__code delete2(struct Context* context, struct Node* current) {
-    if (current->color == Black) {
-        struct Node* child = current->right == NULL ? current->left : current->right;
-        current->color = child == NULL ? Black : child->color;
-
-        goto meta(context, DeleteCase1);
-    }
-
-    goto meta(context, Delete3);
-}
-
-__code delete2_stub(struct Context* context) {
-    goto delete2(context, context->data[Tree]->tree.current);
-}
-
-__code delete3(struct Context* context, struct Tree* tree, struct Node* current) {
-    struct Node* tmp = current->right == NULL ? current->left : current->right;
-
-    if (current->parent) {
-        if (current == current->parent->left)
-            current->parent->left = tmp;
-        else
-            current->parent->right = tmp;
-    } else {
-        tree->root = tmp;
-    }
-
-    if (tmp)
-        tmp->parent = current->parent;
-
-    if (current->parent == NULL && tmp)
-        tmp->color = Black;
-
-    current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL);
+    tree->current = 0;
 
     stack_pop(context->code_stack, &context->next);
     goto meta(context, context->next);
 }
 
-__code delete3_stub(struct Context* context) {
-    goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
-}
-
-__code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) {
-    *newNode = *oldNode;
-
-    if (result == EQ)
-        goto meta(context, Replace_d2);
-    else if (result == GT)
-        tree->current = newNode->right;
-    else
-        tree->current = newNode->left;
-
-    tree->current->parent = newNode;
-    
-    if (tree->current->left == NULL && tree->current->right == NULL)
-        goto meta(context, Delete2);
-    
-    if (result == GT)
-        newNode->right = context->heap;
-    else if (result == LT)
-        newNode->left = context->heap;
-    
-    allocator(context);
-    
-    compare(context, tree, tree->current->key, context->data[Node]->node.key);
-    
-    goto meta(context, Replace_d1);
-}
-
-__code replaceNodeForDelete1_stub(struct Context* context) {
-    goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result);
-}
-
-__code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) {
-    if (tree->current->left && tree->current->right) {
-        newNode->left->parent = newNode;
-        tree->current = newNode->left;
-        newNode->left = context->heap;
-        tree->deleted = newNode;
-
-        allocator(context);
-        tree->current->parent = newNode;
-        
-        goto meta(context, FindMax1);
-    }
-
-    goto meta(context, Delete2);
-}
-
-__code replaceNodeForDelete2_stub(struct Context* context) {
-    goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node);
-}
-
-__code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
-    *newNode = *oldNode;
-
-    if (newNode->right)
-        goto meta(context, FindMax2);
-    
-    tree->deleted->key = newNode->key;
-    tree->deleted->value = newNode->value;
-
-    tree->current = newNode;
-
-    goto meta(context, Delete2);
-}
-
-__code findMax1_stub(struct Context* context) {
-    goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node);
+__code stackClear_stub(struct Context* context) {
+    goto stackClear(context, context->node_stack, &context->data[Tree]->tree);
 }
     
 
-__code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
-    *newNode = *oldNode;
+/* /\* __code get(struct Context* context, struct Tree* tree) { *\/ */
+/* /\*     if (tree->root) { *\/ */
+/* /\*         tree->current = tree->root; *\/ */
 
-    if (newNode->right->right) {
-        tree->current = newNode->right;
-        newNode->right = context->heap;
+/* /\*         goto meta(context, Search); *\/ */
+/* /\*     } *\/ */
 
-        allocator(context);
-        tree->current->parent = newNode;
-        
-        goto meta(context, FindMax2);
-    }
+/* /\*     stack_pop(context->code_stack, &context->next); *\/ */
+/* /\*     goto meta(context, context->next); *\/ */
+/* /\* } *\/ */
 
-    tree->deleted->key = newNode->right->key;
-    tree->deleted->value = newNode->right->value;
+/* /\* __code get_stub(struct Context* context) { *\/ */
+/* /\*     goto get(context, &context->data[Tree]->tree); *\/ */
+/* /\* } *\/ */
 
-    tree->current = newNode;
-    
-    goto meta(context, Delete2);
-}
+/* /\* __code search(struct Context* context, struct Tree* tree, struct Node* node) { *\/ */
+/* /\*     compare(context, tree, tree->current->key, node->key); *\/ */
     
-__code findMax2_stub(struct Context* context) {
-    goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node);
-}
-
-__code deleteCase1(struct Context* context, struct Node* current) {
-    if (current->parent)
-        goto meta(context, DeleteCase2);
-
-    goto meta(context, Delete3);
-}
-
-__code deleteCase1_stub(struct Context* context) {
-    goto deleteCase1(context, context->data[Tree]->tree.current);
-}
-
-__code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) {
-    struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
-    
-    if ((sibling == NULL ? Black : sibling->color) == Red) {
-        current->parent->color = Red;
-        sibling->color = Black;
-
-        current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap);
-        allocator(context);
-        context->data[context->dataNum]->node = *sibling;
+/* /\*     if (tree->result == EQ) { *\/ */
+/* /\*         *node = *tree->current; *\/ */
         
-        tree->current = current->parent;
+/* /\*         goto meta(context, context->next); *\/ */
+/* /\*     } else if (tree->result == GT) { *\/ */
+/* /\*         tree->current = tree->current->right; *\/ */
+/* /\*     } else { *\/ */
+/* /\*         tree->current = tree->current->left; *\/ */
+/* /\*     } *\/ */
         
-        context->next = DeleteCase3;
-        stack_push(context->code_stack, &context->next);
+/* /\*     if (tree->current) *\/ */
+/* /\*         goto meta(context, Search); *\/ */
+
+/* /\*     stack_pop(context->code_stack, &context->next); *\/ */
+/* /\*     goto meta(context, context->next); *\/ */
+/* /\* } *\/ */
 
-        if (current == current->parent->left)
-            goto meta(context, RotateL);
-        else
-            goto meta(context, RotateR);
-    }
+/* /\* __code search_stub(struct Context* context) { *\/ */
+/* /\*     goto search(context, &context->data[Tree]->tree, &context->data[Node]->node); *\/ */
+/* /\* } *\/ */
+
+/* /\* __code delete(struct Context* context, struct Tree* tree) { *\/ */
+/* /\*     if (tree->root) { *\/ */
+/* /\*         stack_push(context->code_stack, &context->next); *\/ */
+/* /\*         context->next = Delete1; *\/ */
+/* /\*         goto meta(context, Get); *\/ */
+/* /\*     } *\/ */
 
-    goto meta(context, DeleteCase3);
-}
+/* /\*     goto meta(context, context->next); *\/ */
+/* /\* } *\/ */
+
+/* /\* __code delete_stub(struct Context* context) { *\/ */
+/* /\*     goto delete(context, &context->data[Tree]->tree); *\/ */
+/* /\* } *\/ */
 
-__code deleteCase2_stub(struct Context* context) {
-    goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
-}
+/* /\* __code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) { *\/ */
+/* /\*     allocate->size = sizeof(struct Node); *\/ */
+/* /\*     allocator(context); *\/ */
+    
+/* /\*     struct Node* root = tree->root; *\/ */
 
-__code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) {
-    struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
+/* /\*     tree->root = &context->data[context->dataNum]->node; *\/ */
+/* /\*     tree->current = root; *\/ */
+
+/* /\*     compare(context, tree, tree->current->key, context->data[Node]->node.key); *\/ */
     
-    if (current->parent->color == Black &&
-        (sibling == NULL ? Black : sibling->color) == Black &&
-        (sibling->left == NULL ? Black : sibling->left->color) == Black &&
-        (sibling->right == NULL ? Black : sibling->right->color) == Black) {
-        sibling->color = Red;
+/* /\*     goto meta(context, Replace_d1); *\/ */
+/* /\* } *\/ */
+
+/* /\* __code delete1_stub(struct Context* context) { *\/ */
+/* /\*     goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate); *\/ */
+/* /\* } *\/ */
+
+/* /\* __code delete2(struct Context* context, struct Node* current) { *\/ */
+/* /\*     if (current->color == Black) { *\/ */
+/* /\*         struct Node* child = current->right == NULL ? current->left : current->right; *\/ */
+/* /\*         current->color = child == NULL ? Black : child->color; *\/ */
+
+/* /\*         goto meta(context, DeleteCase1); *\/ */
+/* /\*     } *\/ */
+
+/* /\*     goto meta(context, Delete3); *\/ */
+/* /\* } *\/ */
+
+/* /\* __code delete2_stub(struct Context* context) { *\/ */
+/* /\*     goto delete2(context, context->data[Tree]->tree.current); *\/ */
+/* /\* } *\/ */
+
+/* /\* __code delete3(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
+/* /\*     struct Node* tmp = current->right == NULL ? current->left : current->right; *\/ */
 
-        tree->current = current->parent;
-        goto meta(context, DeleteCase1);
-    }
+/* /\*     if (current->parent) { *\/ */
+/* /\*         if (current == current->parent->left) *\/ */
+/* /\*             current->parent->left = tmp; *\/ */
+/* /\*         else *\/ */
+/* /\*             current->parent->right = tmp; *\/ */
+/* /\*     } else { *\/ */
+/* /\*         tree->root = tmp; *\/ */
+/* /\*     } *\/ */
+
+/* /\*     if (tmp) *\/ */
+/* /\*         tmp->parent = current->parent; *\/ */
+
+/* /\*     if (current->parent == NULL && tmp) *\/ */
+/* /\*         tmp->color = Black; *\/ */
+
+/* /\*     current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL); *\/ */
 
-    goto meta(context, DeleteCase4);
-}
+/* /\*     stack_pop(context->code_stack, &context->next); *\/ */
+/* /\*     goto meta(context, context->next); *\/ */
+/* /\* } *\/ */
+
+/* /\* __code delete3_stub(struct Context* context) { *\/ */
+/* /\*     goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
+/* /\* } *\/ */
+
+/* /\* __code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) { *\/ */
+/* /\*     *newNode = *oldNode; *\/ */
+
+/* /\*     if (result == EQ) *\/ */
+/* /\*         goto meta(context, Replace_d2); *\/ */
+/* /\*     else if (result == GT) *\/ */
+/* /\*         tree->current = newNode->right; *\/ */
+/* /\*     else *\/ */
+/* /\*         tree->current = newNode->left; *\/ */
 
-__code deleteCase3_stub(struct Context* context) {
-    goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
-}
-
-__code deleteCase4(struct Context* context, struct Node* current) {
-    struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
+/* /\*     tree->current->parent = newNode; *\/ */
+    
+/* /\*     if (tree->current->left == NULL && tree->current->right == NULL) *\/ */
+/* /\*         goto meta(context, Delete2); *\/ */
+    
+/* /\*     if (result == GT) *\/ */
+/* /\*         newNode->right = context->heap; *\/ */
+/* /\*     else if (result == LT) *\/ */
+/* /\*         newNode->left = context->heap; *\/ */
+    
+/* /\*     allocator(context); *\/ */
+    
+/* /\*     compare(context, tree, tree->current->key, context->data[Node]->node.key); *\/ */
     
-    if (current->parent->color == Red &&
-        (sibling == NULL ? Black : sibling->color) == Black &&
-        (sibling->left == NULL ? Black : sibling->left->color) == Black &&
-        (sibling->right == NULL ? Black : sibling->right->color) == Black) {
-        sibling->color = Red;
-        current->parent->color = Black;
+/* /\*     goto meta(context, Replace_d1); *\/ */
+/* /\* } *\/ */
+
+/* /\* __code replaceNodeForDelete1_stub(struct Context* context) { *\/ */
+/* /\*     goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result); *\/ */
+/* /\* } *\/ */
+
+/* /\* __code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) { *\/ */
+/* /\*     if (tree->current->left && tree->current->right) { *\/ */
+/* /\*         newNode->left->parent = newNode; *\/ */
+/* /\*         tree->current = newNode->left; *\/ */
+/* /\*         newNode->left = context->heap; *\/ */
+/* /\*         tree->deleted = newNode; *\/ */
+
+/* /\*         allocator(context); *\/ */
+/* /\*         tree->current->parent = newNode; *\/ */
+        
+/* /\*         goto meta(context, FindMax1); *\/ */
+/* /\*     } *\/ */
+
+/* /\*     goto meta(context, Delete2); *\/ */
+/* /\* } *\/ */
 
-        goto meta(context, Delete3);
-    }
+/* /\* __code replaceNodeForDelete2_stub(struct Context* context) { *\/ */
+/* /\*     goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node); *\/ */
+/* /\* } *\/ */
+
+/* /\* __code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { *\/ */
+/* /\*     *newNode = *oldNode; *\/ */
+
+/* /\*     if (newNode->right) *\/ */
+/* /\*         goto meta(context, FindMax2); *\/ */
+    
+/* /\*     tree->deleted->key = newNode->key; *\/ */
+/* /\*     tree->deleted->value = newNode->value; *\/ */
+
+/* /\*     tree->current = newNode; *\/ */
+
+/* /\*     goto meta(context, Delete2); *\/ */
+/* /\* } *\/ */
+
+/* /\* __code findMax1_stub(struct Context* context) { *\/ */
+/* /\*     goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); *\/ */
+/* /\* } *\/ */
+    
+
+/* /\* __code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { *\/ */
+/* /\*     *newNode = *oldNode; *\/ */
 
-    goto meta(context, DeleteCase5);
-}
+/* /\*     if (newNode->right->right) { *\/ */
+/* /\*         tree->current = newNode->right; *\/ */
+/* /\*         newNode->right = context->heap; *\/ */
 
-__code deleteCase4_stub(struct Context* context) {
-    goto deleteCase4(context, context->data[Tree]->tree.current);
-}
+/* /\*         allocator(context); *\/ */
+/* /\*         tree->current->parent = newNode; *\/ */
+        
+/* /\*         goto meta(context, FindMax2); *\/ */
+/* /\*     } *\/ */
 
-__code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) {
-    struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
-    sibling->parent = current->parent;
+/* /\*     tree->deleted->key = newNode->right->key; *\/ */
+/* /\*     tree->deleted->value = newNode->right->value; *\/ */
+
+/* /\*     tree->current = newNode; *\/ */
+    
+/* /\*     goto meta(context, Delete2); *\/ */
+/* /\* } *\/ */
     
-    if (current == current->parent->left &&
-        (sibling == NULL ? Black : sibling->color) == Black &&
-        (sibling->left == NULL ? Black : sibling->left->color) == Red &&
-        (sibling->right == NULL ? Black : sibling->right->color) == Black) {
-        sibling->color = Red;
-        sibling->left->color = Black;
+/* /\* __code findMax2_stub(struct Context* context) { *\/ */
+/* /\*     goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); *\/ */
+/* /\* } *\/ */
+
+/* /\* __code deleteCase1(struct Context* context, struct Node* current) { *\/ */
+/* /\*     if (current->parent) *\/ */
+/* /\*         goto meta(context, DeleteCase2); *\/ */
+
+/* /\*     goto meta(context, Delete3); *\/ */
+/* /\* } *\/ */
+
+/* /\* __code deleteCase1_stub(struct Context* context) { *\/ */
+/* /\*     goto deleteCase1(context, context->data[Tree]->tree.current); *\/ */
+/* /\* } *\/ */
+
+/* /\* __code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
+/* /\*     struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
+    
+/* /\*     if ((sibling == NULL ? Black : sibling->color) == Red) { *\/ */
+/* /\*         current->parent->color = Red; *\/ */
+/* /\*         sibling->color = Black; *\/ */
+
+/* /\*         current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap); *\/ */
+/* /\*         allocator(context); *\/ */
+/* /\*         context->data[context->dataNum]->node = *sibling; *\/ */
         
-        sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap);
-        allocator(context);
-        struct Node* tmp = &context->data[context->dataNum]->node;
-        *tmp = *sibling;
-        tmp->parent = current;
+/* /\*         tree->current = current->parent; *\/ */
         
-        tmp->left = context->heap;
-        allocator(context);
-        context->data[context->dataNum]->node = *sibling->left;
-        context->data[context->dataNum]->node.parent = tmp;
+/* /\*         context->next = DeleteCase3; *\/ */
+/* /\*         stack_push(context->code_stack, &context->next); *\/ */
 
-        tree->current = tmp;
-        
-        context->next = DeleteCase6;
-        stack_push(context->code_stack, &context->next);
+/* /\*         if (current == current->parent->left) *\/ */
+/* /\*             goto meta(context, RotateL); *\/ */
+/* /\*         else *\/ */
+/* /\*             goto meta(context, RotateR); *\/ */
+/* /\*     } *\/ */
+
+/* /\*     goto meta(context, DeleteCase3); *\/ */
+/* /\* } *\/ */
+
+/* /\* __code deleteCase2_stub(struct Context* context) { *\/ */
+/* /\*     goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
+/* /\* } *\/ */
 
-        goto meta(context, RotateR);
-    } else if (current == current->parent->right &&
-               (sibling == NULL ? Black : sibling->color) == Black &&
-               (sibling->left == NULL ? Black : sibling->left->color) == Black &&
-               (sibling->right == NULL ? Black : sibling->right->color) == Red) {
-        sibling->color = Red;
-        sibling->right->color = Black;
+/* /\* __code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
+/* /\*     struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
+    
+/* /\*     if (current->parent->color == Black && *\/ */
+/* /\*         (sibling == NULL ? Black : sibling->color) == Black && *\/ */
+/* /\*         (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */
+/* /\*         (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */
+/* /\*         sibling->color = Red; *\/ */
+
+/* /\*         tree->current = current->parent; *\/ */
+/* /\*         goto meta(context, DeleteCase1); *\/ */
+/* /\*     } *\/ */
+
+/* /\*     goto meta(context, DeleteCase4); *\/ */
+/* /\* } *\/ */
 
-        sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap);
-        allocator(context);
-        struct Node* tmp = &context->data[context->dataNum]->node;
-        *tmp = *sibling;
-        tmp->parent = current;
+/* /\* __code deleteCase3_stub(struct Context* context) { *\/ */
+/* /\*     goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
+/* /\* } *\/ */
+
+/* /\* __code deleteCase4(struct Context* context, struct Node* current) { *\/ */
+/* /\*     struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
+    
+/* /\*     if (current->parent->color == Red && *\/ */
+/* /\*         (sibling == NULL ? Black : sibling->color) == Black && *\/ */
+/* /\*         (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */
+/* /\*         (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */
+/* /\*         sibling->color = Red; *\/ */
+/* /\*         current->parent->color = Black; *\/ */
+
+/* /\*         goto meta(context, Delete3); *\/ */
+/* /\*     } *\/ */
 
-        tmp->right = context->heap;
-        allocator(context);
-        context->data[context->dataNum]->node = *sibling->right;
-        context->data[context->dataNum]->node.parent = tmp;
+/* /\*     goto meta(context, DeleteCase5); *\/ */
+/* /\* } *\/ */
 
-        tree->current = tmp;
+/* /\* __code deleteCase4_stub(struct Context* context) { *\/ */
+/* /\*     goto deleteCase4(context, context->data[Tree]->tree.current); *\/ */
+/* /\* } *\/ */
 
-        context->next = DeleteCase6;
-        stack_push(context->code_stack, &context->next);
-        goto meta(context, RotateL);
-    }
+/* /\* __code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
+/* /\*     struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
+/* /\*     sibling->parent = current->parent; *\/ */
+    
+/* /\*     if (current == current->parent->left && *\/ */
+/* /\*         (sibling == NULL ? Black : sibling->color) == Black && *\/ */
+/* /\*         (sibling->left == NULL ? Black : sibling->left->color) == Red && *\/ */
+/* /\*         (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */
+/* /\*         sibling->color = Red; *\/ */
+/* /\*         sibling->left->color = Black; *\/ */
+        
+/* /\*         sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */
+/* /\*         allocator(context); *\/ */
+/* /\*         struct Node* tmp = &context->data[context->dataNum]->node; *\/ */
+/* /\*         *tmp = *sibling; *\/ */
+/* /\*         tmp->parent = current; *\/ */
+        
+/* /\*         tmp->left = context->heap; *\/ */
+/* /\*         allocator(context); *\/ */
+/* /\*         context->data[context->dataNum]->node = *sibling->left; *\/ */
+/* /\*         context->data[context->dataNum]->node.parent = tmp; *\/ */
 
-    goto meta(context, DeleteCase6);
-}
+/* /\*         tree->current = tmp; *\/ */
+        
+/* /\*         context->next = DeleteCase6; *\/ */
+/* /\*         stack_push(context->code_stack, &context->next); *\/ */
 
-__code deleteCase5_stub(struct Context* context) {
-    goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
-}
+/* /\*         goto meta(context, RotateR); *\/ */
+/* /\*     } else if (current == current->parent->right && *\/ */
+/* /\*                (sibling == NULL ? Black : sibling->color) == Black && *\/ */
+/* /\*                (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */
+/* /\*                (sibling->right == NULL ? Black : sibling->right->color) == Red) { *\/ */
+/* /\*         sibling->color = Red; *\/ */
+/* /\*         sibling->right->color = Black; *\/ */
 
-__code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) {
-    struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
+/* /\*         sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */
+/* /\*         allocator(context); *\/ */
+/* /\*         struct Node* tmp = &context->data[context->dataNum]->node; *\/ */
+/* /\*         *tmp = *sibling; *\/ */
+/* /\*         tmp->parent = current; *\/ */
 
-    sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap);
-    allocator(context);
-    struct Node* tmp = &context->data[context->dataNum]->node;
-    *tmp = *sibling;
-    tmp->parent = current;
+/* /\*         tmp->right = context->heap; *\/ */
+/* /\*         allocator(context); *\/ */
+/* /\*         context->data[context->dataNum]->node = *sibling->right; *\/ */
+/* /\*         context->data[context->dataNum]->node.parent = tmp; *\/ */
+
+/* /\*         tree->current = tmp; *\/ */
+
+/* /\*         context->next = DeleteCase6; *\/ */
+/* /\*         stack_push(context->code_stack, &context->next); *\/ */
+/* /\*         goto meta(context, RotateL); *\/ */
+/* /\*     } *\/ */
+
+/* /\*     goto meta(context, DeleteCase6); *\/ */
+/* /\* } *\/ */
 
-    tmp->color = current->parent->color;
-    current->parent->color = Black;
-    
-    context->next = Delete3;
-    stack_push(context->code_stack, &context->next);
+/* /\* __code deleteCase5_stub(struct Context* context) { *\/ */
+/* /\*     goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
+/* /\* } *\/ */
+
+/* /\* __code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
+/* /\*     struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
+
+/* /\*     sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */
+/* /\*     allocator(context); *\/ */
+/* /\*     struct Node* tmp = &context->data[context->dataNum]->node; *\/ */
+/* /\*     *tmp = *sibling; *\/ */
+/* /\*     tmp->parent = current; *\/ */
+
+/* /\*     tmp->color = current->parent->color; *\/ */
+/* /\*     current->parent->color = Black; *\/ */
     
-    if (current == current->parent->left) {
-        tmp->right->color = Black;
-        tree->current = current->parent;
+/* /\*     context->next = Delete3; *\/ */
+/* /\*     stack_push(context->code_stack, &context->next); *\/ */
+    
+/* /\*     if (current == current->parent->left) { *\/ */
+/* /\*         tmp->right->color = Black; *\/ */
+/* /\*         tree->current = current->parent; *\/ */
 
-        goto meta(context, RotateL);
-    } else {
-        tmp->left->color = Black;
-        tree->current = current->parent;
+/* /\*         goto meta(context, RotateL); *\/ */
+/* /\*     } else { *\/ */
+/* /\*         tmp->left->color = Black; *\/ */
+/* /\*         tree->current = current->parent; *\/ */
 
-        goto meta(context, RotateR);
-    }
-}
+/* /\*         goto meta(context, RotateR); *\/ */
+/* /\*     } *\/ */
+/* /\* } *\/ */
 
-__code deleteCase6_stub(struct Context* context) {
-    goto deleteCase6(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
-}
+/* /\* __code deleteCase6_stub(struct Context* context) { *\/ */
+/* /\*     goto deleteCase6(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
+/* /\* } *\/ */
--- a/src/llrb/llrbContext.c	Fri Dec 11 15:07:10 2015 +0900
+++ b/src/llrb/llrbContext.c	Thu Jan 07 08:20:03 2016 +0900
@@ -26,7 +26,7 @@
 extern __code insert4_1_stub(struct Context*);
 extern __code insert4_2_stub(struct Context*);
 extern __code insert5_stub(struct Context*);
-extern __code insert5_1_stub(struct Context*);
+extern __code stackClear_stub(struct Context*);
 extern __code get_stub(struct Context*);
 extern __code search_stub(struct Context*);
 extern __code delete_stub(struct Context*);
@@ -73,23 +73,23 @@
     context->code[InsertCase4_1] = insert4_1_stub;
     context->code[InsertCase4_2] = insert4_2_stub;
     context->code[InsertCase5]   = insert5_stub;
-    context->code[InsertCase5_1] = insert5_1_stub;
-    context->code[Get]        = get_stub;
-    context->code[Search]        = search_stub;
-    context->code[Delete]        = delete_stub;
-    context->code[Delete1]       = delete1_stub;
-    context->code[Delete2]       = delete2_stub;
-    context->code[Delete3]       = delete3_stub;
-    context->code[Replace_d1] = replaceNodeForDelete1_stub;
-    context->code[Replace_d2] = replaceNodeForDelete2_stub;
-    context->code[FindMax1]    = findMax1_stub;
-    context->code[FindMax2]    = findMax2_stub;
-    context->code[DeleteCase1]   = deleteCase1_stub;
-    context->code[DeleteCase2]   = deleteCase2_stub;
-    context->code[DeleteCase3]   = deleteCase3_stub;
-    context->code[DeleteCase4]   = deleteCase4_stub;
-    context->code[DeleteCase5]   = deleteCase5_stub;
-    context->code[DeleteCase6]   = deleteCase6_stub;
+    context->code[StackClear]    = stackClear_stub;
+    /* context->code[Get]        = get_stub; */
+    /* context->code[Search]        = search_stub; */
+    /* context->code[Delete]        = delete_stub; */
+    /* context->code[Delete1]       = delete1_stub; */
+    /* context->code[Delete2]       = delete2_stub; */
+    /* context->code[Delete3]       = delete3_stub; */
+    /* context->code[Replace_d1] = replaceNodeForDelete1_stub; */
+    /* context->code[Replace_d2] = replaceNodeForDelete2_stub; */
+    /* context->code[FindMax1]    = findMax1_stub; */
+    /* context->code[FindMax2]    = findMax2_stub; */
+    /* context->code[DeleteCase1]   = deleteCase1_stub; */
+    /* context->code[DeleteCase2]   = deleteCase2_stub; */
+    /* context->code[DeleteCase3]   = deleteCase3_stub; */
+    /* context->code[DeleteCase4]   = deleteCase4_stub; */
+    /* context->code[DeleteCase5]   = deleteCase5_stub; */
+    /* context->code[DeleteCase6]   = deleteCase6_stub; */
     context->code[Exit]       = exit_code;
     
     context->heap = context->heapStart;
@@ -110,6 +110,6 @@
     tree->current = 0;
     tree->deleted = 0;
     
-    context->node_stack = stack_init(sizeof(union Data*), num);
+    context->node_stack = stack_init(sizeof(struct Node*), 100);
     context->code_stack = stack_init(sizeof(enum Code), 100);
 }
--- a/src/llrb/llrbContext.h	Fri Dec 11 15:07:10 2015 +0900
+++ b/src/llrb/llrbContext.h	Thu Jan 07 08:20:03 2016 +0900
@@ -27,7 +27,7 @@
     InsertCase4_1,
     InsertCase4_2,
     InsertCase5,
-    InsertCase5_1,
+    StackClear,
     Get,
     Search,
     Delete,
@@ -85,7 +85,7 @@
         enum Code next;
         struct Node* root;
         struct Node* current;
-        struct Node* deleted;;
+        struct Node* deleted;
         int result;
     } tree;
     struct Node {
@@ -100,7 +100,6 @@
             Red,
             Black,
         } color;
-        struct Node* parent;
     } node;
     struct Allocate {
         enum Code next;
--- a/src/llrb/main.c	Fri Dec 11 15:07:10 2015 +0900
+++ b/src/llrb/main.c	Thu Jan 07 08:20:03 2016 +0900
@@ -72,7 +72,7 @@
     print_tree(context->data[Tree]->tree.root, 0);
     puts("");
     context->next = Code3;
-    node->key = count->i;
+    node->key = rand()%100+1;
     node->value = count->i;
     
     count->i--;
@@ -92,7 +92,7 @@
     
     context->next = Code5;
 
-    goto meta(context, Delete);
+    goto meta(context, Exit);
 }
 
 __code code5(struct Context* context) {