# HG changeset patch
# User Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
# Date 1445325762 -32400
# Node ID 368306e1bfedabdfdea2fbb368461ad33363022f
# Parent  a870c84acd0ec162d219d7655b7b21fb8c2a2162
llrb deletion(not work).

diff -r a870c84acd0e -r 368306e1bfed src/CMakeLists.txt
--- a/src/CMakeLists.txt	Tue Sep 15 15:21:50 2015 +0900
+++ b/src/CMakeLists.txt	Tue Oct 20 16:22:42 2015 +0900
@@ -1,4 +1,4 @@
-cmake_minimum_required(VERSION 2.8)
+cmake_minimum_required(VERSION 3.3)
 
 # output compile log
 set(CMAKE_VERBOSE_MAKEFILE 1)
diff -r a870c84acd0e -r 368306e1bfed src/include/allocate.h
--- a/src/include/allocate.h	Tue Sep 15 15:21:50 2015 +0900
+++ b/src/include/allocate.h	Tue Oct 20 16:22:42 2015 +0900
@@ -1,6 +1,5 @@
 __code allocate();
 __code meta_allocate();
-extern __code meta();
 
 __code allocate(struct Context* context) {
     goto meta_allocate(context);
diff -r a870c84acd0e -r 368306e1bfed src/include/origin_cs.h
--- a/src/include/origin_cs.h	Tue Sep 15 15:21:50 2015 +0900
+++ b/src/include/origin_cs.h	Tue Oct 20 16:22:42 2015 +0900
@@ -1,14 +1,3 @@
-__code start_code();
-__code exit_code();
-extern __code meta();
-
-__code start_code(struct Context* context, enum Code next) {
-    goto meta(context, next);
-}
-
-__code exit_code(struct Context* context) {
-    free(context->code);
-    free(context->data);
-    free(context->heapStart);
-    goto exit(0);
-}
+extern __code start_code(struct Context* context, enum Code next);
+extern __code exit_code(struct Context* context);
+extern __code meta(struct Context* context, enum Code next);
diff -r a870c84acd0e -r 368306e1bfed src/llrb/CMakeLists.txt
--- a/src/llrb/CMakeLists.txt	Tue Sep 15 15:21:50 2015 +0900
+++ b/src/llrb/CMakeLists.txt	Tue Oct 20 16:22:42 2015 +0900
@@ -1,8 +1,12 @@
 cmake_minimum_required(VERSION 2.8)
 
 add_executable(llrb
+               main.c
                llrb.c
                llrbContext.c
                allocate.c
                compare.c
+               stack.c
+               origin_cs.c
 )
+
diff -r a870c84acd0e -r 368306e1bfed src/llrb/allocate.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/llrb/allocate.c	Tue Oct 20 16:22:42 2015 +0900
@@ -0,0 +1,6 @@
+#include "llrbContext.h"
+
+void allocator(struct Context* context) {
+    context->data[++context->dataNum] = context->heap;
+    context->heap += context->data[Allocate]->allocate.size;
+}
diff -r a870c84acd0e -r 368306e1bfed src/llrb/compare.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/llrb/compare.c	Tue Oct 20 16:22:42 2015 +0900
@@ -0,0 +1,11 @@
+#include "llrbContext.h"
+
+void compare(struct Context* context, struct Tree* tree, int key1, int key2) {
+    if (key1 == key2) {
+        tree->result = 0;
+    } else if (key1 < key2) {
+        tree->result = 1;
+    } else {
+        tree->result = -1;
+    }
+}
diff -r a870c84acd0e -r 368306e1bfed src/llrb/llrb.c
--- a/src/llrb/llrb.c	Tue Sep 15 15:21:50 2015 +0900
+++ b/src/llrb/llrb.c	Tue Oct 20 16:22:42 2015 +0900
@@ -1,97 +1,14 @@
 #include <stdio.h>
-#include <stdlib.h>
-#include <sys/time.h>
 
 #include "llrbContext.h"
-
 #include "origin_cs.h"
-
 #include "stack.h"
 
-#define NUM 100
-
-extern __code initLLRBContext(struct Context* context);
 extern void allocator(struct Context* context);
 extern void compare(struct Context* context, struct Tree* tree, int key1, int key2);
 
-/* 
-__code code1(Allocate allocate) {
-    allocate.size = sizeof(long);
-    allocate.next = Code2;
-    goto Allocate(allocate);
-}
-*/
-static double st_time;
-static double ed_time;
-static int num;
-static clock_t c1,c2;
-
-static stack_ptr pstack;
-static struct Node* pre;
-
-static double getTime() {
-    struct timeval tv;
-    gettimeofday(&tv, NULL);
-    return tv.tv_sec + (double)tv.tv_usec*1e-6;
-}
-
-void print_tree(struct Node* node, int n) {
-    if (node != 0) {
-        print_tree(node->left, n+1);
-        for (int i=0;i<n;i++)
-            printf("  ");
-        printf("key=%d depth=%d\t%p\n", node->key, n, node);
-        print_tree(node->right, n+1);
-    }
-}
-
-__code code1(struct Context* context, struct Allocate *allocate) {
-    allocate->size = sizeof(struct Count);
-    allocator(context);
-    goto meta(context, Code2);
-}
-
-__code code1_stub(struct Context* context) {
-    goto code1(context, &context->data[Allocate]->allocate);
-}
-
-
-/*
-__code code2(Allocate allocate, Count count) {
-    count.count = 0;
-    goto code3(count);
-}
-*/
-
-__code code2(struct Context* context, struct Count* count) {
-    count->i = 1;
-    goto meta(context, Code3);
-}
-
-__code code2_stub(struct Context* context) {
-    goto code2(context, &context->data[context->dataNum]->count);
-}
-
-__code code3(struct Context* context, struct Node* node, struct Count* count) {
-    if (count->i == num) {
-        goto meta(context, Code4);
-    }
-
-    context->next = Code3;
-    node->key = count->i;
-    node->value = count->i;
-    
-    count->i++;
-    goto meta(context, Put);
-}
-
-__code code3_stub(struct Context* context) {
-    goto code3(context, &context->data[Node]->node, &context->data[3]->count);
-}
-
-__code meta(struct Context* context, enum Code next) {
-    goto (context->code[next])(context);
-}
+extern int num;
+extern stack_ptr node_stack;
 
 __code put(struct Context* context, struct Tree* tree, struct Allocate* allocate) {
     allocate->size = sizeof(struct Node);
@@ -102,6 +19,7 @@
     } else {
         tree->current = tree->root;
         compare(context, tree, tree->current->key, context->data[Node]->node.key);
+
         goto meta(context, Replace);
     }
 }
@@ -111,13 +29,28 @@
 }
 
 __code replaceNode(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) {
-    stack_push(pstack, &newNode);
+    stack_push(node_stack, &newNode);
 
     *newNode = *oldNode;
 
     if (result == 0) {
-        stack_pop(pstack, &tree->current);
-        goto meta(context, RotateL);
+        stack_pop(node_stack, &tree->current);
+        newNode->value = context->data[Node]->node.value;
+
+        if (tree->current->right != 0)
+            if (tree->current->right->color == Red)
+                goto meta(context, RotateL);
+
+        if (tree->current->left != 0)
+            if (tree->current->left->left != 0)
+                if (tree->current->left->color == Red && tree->current->left->left->color == Red)
+                    goto meta(context, RotateR);
+        
+        if (tree->current->right != 0 && tree->current->left != 0)
+            if (tree->current->right->color == Red && tree->current->left->color == Red)
+                goto meta(context, ColorFlip);
+        
+        goto meta(context, FixUp);
     } else if (result == 1) {
         tree->current = oldNode->right;
         newNode->right = context->heap;
@@ -129,10 +62,11 @@
     allocator(context);
 
     if (tree->current == 0) {
-        stack_pop(pstack, &tree->current);
+        stack_pop(node_stack, &tree->current);
         goto meta(context, Insert);
     } else {
         compare(context, tree, tree->current->key, context->data[Node]->node.key);
+        
         goto meta(context, Replace);
     }
 }
@@ -148,64 +82,78 @@
     if (tree->root == 0) {
         newNode->color = Black;
         tree->root = newNode;
+        tree->current = 0;
         goto meta(context, context->next);
     }
 
-    goto meta(context, RotateL);
+    if (tree->current->right != 0)
+        if (tree->current->right->color == Red)
+            goto meta(context, RotateL);
+
+    
+    if (tree->current->left != 0)
+        if (tree->current->left->left != 0)
+            if (tree->current->left->color == Red && tree->current->left->left->color == Red)
+                goto meta(context, RotateR);
+            
+    if (tree->current->right != 0 && tree->current->left != 0)
+        if (tree->current->right->color == Red && tree->current->left->color == Red)
+            goto meta(context, ColorFlip);
+    
+    goto meta(context, FixUp);
 }
 
 __code insertNode_stub(struct Context* context) {
     goto insertNode(context, &context->data[Tree]->tree, &context->data[Node]->node, &context->data[context->dataNum]->node);
 }
 
-__code rotateLeft(struct Context* context, struct Node* node) {
-    if (node->right != 0) {
-        if (node->right->color == Red) {
-            struct Node* tmp = node->right;
-            node->right = tmp->left;
-            tmp->left = node;
-            tmp->color = tmp->left->color;
-            tmp->left->color = Red;
-            context->data[Tree]->tree.current = tmp;
-        }
-    }
+__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree) {
+    struct Node* tmp = node->right;
+    node->right = tmp->left;
+    tmp->left = node;
+    tmp->color = node->color;
+    node->color = Red;
+    tree->current = tmp;
     
-    goto meta(context, RotateR);
+    if (tree->current->left != 0)
+        if (tree->current->left->left != 0)
+            if (tree->current->left->color == Red && tree->current->left->left->color == Red)
+                goto meta(context, RotateR);
+
+    if (tree->current->right != 0 && tree->current->left != 0)
+        if (tree->current->right->color == Red && tree->current->left->color == Red)
+            goto meta(context, ColorFlip);
+    
+    goto meta(context, FixUp);
 }
     
 __code rotateLeft_stub(struct Context* context) {
-    goto rotateLeft(context, context->data[Tree]->tree.current);
+    goto rotateLeft(context, context->data[Tree]->tree.current, &context->data[Tree]->tree);
 }
 
-__code rotateRight(struct Context* context, struct Node* node) {
-    if (node->left != 0) {
-        if (node->left->left != 0) {
-            if (node->left->color == Red && node->left->left->color == Red) {
-                struct Node* tmp = node->left;
-                node->left = tmp->right;
-                tmp->right = node;
-                tmp->color = tmp->right->color;
-                tmp->right->color = Red;
-                context->data[Tree]->tree.current = tmp;
-            }
-        }
-    }
+__code rotateRight(struct Context* context, struct Node* node, struct Tree* tree) {
+    struct Node* tmp = node->left;
+    node->left = tmp->right;
+    tmp->right = node;
+    tmp->color = node->color;
+    node->color = Red;
+    context->data[Tree]->tree.current = tmp;
 
-    goto meta(context, ColorFlip);
+    if (tree->current->right != 0 && tree->current->left != 0)
+        if (tree->current->right->color == Red && tree->current->left->color == Red)
+            goto meta(context, ColorFlip);
+    
+    goto meta(context, FixUp);
 }
 
 __code rotateRight_stub(struct Context* context) {
-    goto rotateRight(context, context->data[Tree]->tree.current);
+    goto rotateRight(context, context->data[Tree]->tree.current, &context->data[Tree]->tree);
 }
 
 __code colorFlip(struct Context* context, struct Node* node) {
-    if (node->right != 0 && node->left != 0) {
-        if (node->right->color == Red && node->left->color == Red) {
-            node->color ^= 1;
-            node->left->color ^= 1;
-            node->right->color ^= 1;
-        }
-    }
+    node->color ^= 1;
+    node->left->color ^= 1;
+    node->right->color ^= 1;
     
     goto meta(context, FixUp);
 }
@@ -218,12 +166,14 @@
     node->key = newNode->key;
     tree->prev = newNode;
     
-    if (stack_pop(pstack, &tree->current) == 0) {
+    if (stack_pop(node_stack, &tree->current) == 0) {
         compare(context, tree, tree->current->key, node->key);
         goto meta(context, ChangeRef);
     }
     
+    newNode->color = Black;
     tree->root = newNode;
+    tree->current = 0;
     
     goto meta(context, context->next);
 }    
@@ -241,77 +191,276 @@
         perror("bad status");
     }
     
-    goto meta(context, RotateL);
+    if (tree->current->right != 0)
+        if (tree->current->right->color == Red)
+            goto meta(context, RotateL);
+
+    if (tree->current->left != 0)
+        if (tree->current->left->left != 0)
+            if (tree->current->left->color == Red && tree->current->left->left->color == Red)
+                goto meta(context, RotateR);
+            
+    if (tree->current->right != 0 && tree->current->left != 0)
+        if (tree->current->right->color == Red && tree->current->left->color == Red)
+            goto meta(context, ColorFlip);
+
+    goto meta(context, FixUp);
 }
 
 __code changeReference_stub(struct Context* context) {
     goto changeReference(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, context->data[Tree]->tree.result);
 }
 
-/* __code get(struct Context* context) { */
-/*     context->data[Tree]->tree.current = context->data[Tree]->tree.root; */
-/*     context->data[Next]->next = context->data[Allocate]->allocate.next; */
-/*     context->data[Allocate]->allocate.next = Traverse; */
+__code get(struct Context* context, struct Tree* tree, struct Node* node) {
+    tree->current = (tree->current == 0)? tree->root : tree->current;
 
-/*     goto meta(context, Compare); */
-/* } */
+    compare(context, tree, tree->current->key, node->key);
+    
+    if (tree->result == 0) {
+        goto meta(context, context->next);
+    } else if (tree->result == 1) {
+        tree->current = tree->current->right;
+    } else {
+        tree->current = tree->current->left;
+    }
+        
+    if (tree->current == 0)
+        goto meta(context, context->next);
+        
+    goto meta(context, Get);
+}
+
+__code get_stub(struct Context* context) {
+    goto get(context, &context->data[Tree]->tree, &context->data[Node]->node);
+}
 
-/* __code traverse(struct Context* context) { */
-/*     int result = context->data[Tree]->tree.result; */
-/*     struct Tree* tree = &context->data[Tree]->tree; */
+__code delete(struct Context* context, struct Tree* tree, struct Allocate* allocate) {
+    allocate->size = sizeof(struct Node);
+    allocator(context);
+
+    tree->current = tree->root;
+    compare(context, tree, tree->current->key, context->data[Node]->node.key);
+    goto meta(context, Replace_d);
+}
+
+__code delete_stub(struct Context* context) {
+    goto delete(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate);
+}
+
+__code replaceNode_d(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, struct Node* node) {
+    *newNode = *oldNode;
+    tree->current = newNode;
     
-/*     if (result == 0) { */
-/*         goto meta(context, context->data[Next]->next); */
-/*     } else if (result == 1) { */
-/*         tree->current = tree->current->right; */
-/*     } else { */
-/*         tree->current = tree->current->left; */
-/*     } */
+    if (tree->result == -1) {
+        
+        if (tree->current->left != 0)
+            if (tree->current->left->left != 0)
+                if (tree->current->left->color != Red && tree->current->left->left->color != Red)
+                    goto meta(context, MoveRedL);
+        
+        stack_push(node_stack, &tree->current);
+
+        tree->current->left = context->heap;
+        tree->current = oldNode->left;
 
-/*     if(tree->current == 0) { */
-/*         goto meta(context, context->data[Next]->next); */
-/*     } */
+        allocator(context);
+        compare(context, tree, tree->current->key, context->data[Node]->node.key);
+        
+        goto meta(context, Replace_d);
+    } else {
+        if (tree->current->left != 0)
+            if (tree->current->left->color = Red) {
+                allocator(context);
+                *context->data[context->dataNum]->node = *tree->current->left;
+                tree->current->left = context->data[context->dataNum]->node;
+                
+                // roatate right
+                struct Node* tmp = tree->current->left;
+                tree->current->left = tmp->right;
+                tmp->right = tree->current;
+                tmp->color = tree->current->color;
+                tree->current->color = Red;
+                tree->current = tmp;
+            }
 
-/*     goto meta(context, Compare); */
-/* } */
+        if (tree->result == 0 && tree->current->right == 0) {
+            stack_pop(node_stack, &tree->current);
+
+            compare(context, tree, tree->current->key, context->data[Node]->node.key);
 
-/* __code delete(struct Context* context) { */
-/*     goto meta(context, Get); */
-/* } */
+            if (tree->result == 1) {
+                tree->current->right = 0;
+            } else {
+                tree->current->left = 0;
+            }
 
-__code code4(struct Context* context) {
-    puts("---before---");
-    print_tree(context->data[Tree]->tree.root, 0);
-    
-    struct Node* node = &context->data[Node]->node;
-    node->key = 0;
-    node->value = 0;
-    
-    context->next = Code5;
+            if (tree->current->right != 0)
+                if (tree->current->right->color == Red)
+                    goto meta(context, RotateL);
+            
+            if (tree->current->left != 0)
+                if (tree->current->left->left != 0)
+                    if (tree->current->left->color == Red && tree->current->left->left->color == Red)
+                        goto meta(context, RotateR);
+            
+            goto meta(context, FixUp);
+        }
+            
 
-    goto meta(context, Put);
+        if (tree->current->right != 0) {
+            if (tree->right->left != 0) {
+                if (tree->current->right->color != Red && tree->current->right->left->color != Red) {
+                    goto meta(context, MoveRedR);
+                }
+            }
+
+            stack_push(node_stack, &tree->current);
+        
+            tree->current->right = context->heap;
+            tree->current = oldNode->right;
+            
+            allocator(context);
+
+            goto(context, Replace_d);
+
+        }
+        
+    allocator(context);
+    compare(context, tree, tree->current->key, context->data[Node]->node.key);
+    goto meta(context, Replace_d);
+}
+
+__code replaceNode_d_stub(struct Context* context) {
+    goto replaceNode_d(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, &context->data[Node]->node);
 }
 
-__code code5(struct Context* context) {
-    puts("---after---");
-    print_tree(context->data[Tree]->tree.root, 0);
-    puts("--Number of Data--");
-    printf("%d\n", context->dataNum);
-    stack_free(pstack);
+__code moveRedLeft(struct Context* context, struct Node* node) {
+    // color flip
+    node->color ^= 1;
+    node->left->color ^= 1;
+    node->right->color ^= 1;
+
+    if (tree->current->right != 0)
+        if (tree->current->right->left != 0)
+            if (tree->current->right->left == Red) {
+                allocator(context);
+                *context->data[context->dataNum]->node = *node->right;
+                node->right = context->data[context->dataNum]->node;
+                
+                allocator(context);
+                *context->data[context->dataNum]->node = *node->right->left;
+                node->right->left = context->data[context->dataNum]->node;
+
+                // rotate right
+                struct Node* tmp = node->right->left;
+                node->right->left = tmp->right;
+                tmp->right = node->right;
+                tmp->color = node->right->color;
+                node->right->color = Red;
+                node->right = tmp;
 
-    goto meta(context, Exit);
+                // rotate left
+                tmp = node->right;
+                node->right = tmp->left;
+                tmp->left = node;
+                tmp->color = node->color;
+                node->color = Red;
+
+                // color flip
+                node->color ^= 1;
+                node->left->color ^= 1;
+                node->right->color ^= 1;
+
+                tree->current = tmp;
+            }
+
+    stack_push(node_stack, &tree->current);
+
+    tree->current->left = context->heap;
+    tree->current = oldNode->left;
+
+    allocator(context);
+    compare(context, tree, tree->current->key, context->data[Node]->node.key);
+    
+    goto meta(context, Replace_d);
 }
 
-/* __code code6(struct Context* context) { */
-/*     puts("---get---"); */
-/*     print_tree(context->data[Tree]->tree.current, 0); */
-/*     goto meta(context, Exit); */
-/* } */
+__code moveRedRight(struct Context* context, struct Node* node) {
+    // color flip
+    node->color ^= 1;
+    node->left->color ^= 1;
+    node->right->color ^= 1;
+
+    if (tree->current->left != 0)
+        if (tree->current->left->left != 0)
+            if (tree->current->left->left == Red) {
+                allocator(context);
+                *context->data[context->dataNum]->node = *node->left;
+                node->left = context->data[context->dataNum]->node;
+                
+                // rotate right
+                struct Node* tmp = node->left;
+                node->left = tmp->right;
+                tmp->right = node;
+                tmp->color = node->color;
+                node->color = Red;
+
+                // color flip
+                node->color ^= 1;
+                node->left->color ^= 1;
+                node->right->color ^= 1;
 
-int main(int argc, char** argv) {
-    num = (int)atoi(argv[1]);
-    pstack = stack_init(sizeof(union Data*), num);
-    struct Context* context = (struct Context*)malloc(sizeof(struct Context));
-    initLLRBContext(context);
-    goto start_code(context, Code1);
+                tree->current = tmp;
+            }
+    
+    stack_push(node_stack, &tree->current);
+    
+    tree->current->right = context->heap;
+    tree->prev = tree->current;
+    tree->current = oldNode->right;
+    
+    allocator(context);
+    if (tree->result = 0) {
+        goto meta(context, DeleteMin);
+    } else {
+        compare(context, tree, tree->current->key, context->data[Node]->node.key);
+        
+        goto meta(context, Replace_d);
+    }
+}
+
+__code colorFlip_stub(struct Context* context) {
+    goto colorFlip(context, context->data[Tree]->tree.current);
 }
+
+__code deleteMin(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
+    stack_push(node_stack, &newNode);
+    
+    *newNode = *oldNode;
+    tree->current = newNode;
+
+    if (tree->current->left == 0) {
+        newNode->left = 0;
+
+        if (tree->current->right != 0)
+            if (tree->current->right->color == Red)
+                goto meta(context, RotateL);
+        
+        goto meta(context, FixUp);
+    }
+
+    if (tree->current->left != 0)
+        if (tree->current->left->left != 0)
+            if (tree->current->left->color != Red && tree->current->left->left->color != Red)
+                goto meta(context, MoveRedL);
+
+    tree->current = oldNode->left;
+    newNode->left = context->heap;
+
+    allocator(context);
+    goto meta(context, DeleteMin);
+}
+
+__code max_stub(struct Context* context) {
+    goto max(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node);
+}
diff -r a870c84acd0e -r 368306e1bfed src/llrb/llrbContext.c
--- a/src/llrb/llrbContext.c	Tue Sep 15 15:21:50 2015 +0900
+++ b/src/llrb/llrbContext.c	Tue Oct 20 16:22:42 2015 +0900
@@ -7,7 +7,9 @@
 extern __code code3_stub(struct Context*);
 extern __code code4(struct Context*);
 extern __code code5(struct Context*);
-extern __code code6_stub(struct Context*);
+extern __code find(struct Context*);
+extern __code not_find(struct Context*);
+extern __code code6(struct Context*);
 extern __code meta(struct Context*);
 extern __code put_stub(struct Context*);
 extern __code replaceNode_stub(struct Context*);
@@ -18,7 +20,11 @@
 extern __code fixUp_stub(struct Context*);
 extern __code changeReference_stub(struct Context*);
 extern __code get_stub(struct Context*);
-extern __code traverse_stub(struct Context*);
+extern __code delete_stub(struct Context*);
+extern __code deleteMax_stub(struct Context*);
+extern __code deleteMin_stub(struct Context*);
+extern __code replaceNode_d_stub(struct Context*);
+extern __code max_stub(struct Context*);
 extern __code exit_code(struct Context*);
 
 __code initLLRBContext(struct Context* context) {
@@ -33,6 +39,9 @@
     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;
@@ -41,6 +50,12 @@
     context->code[ColorFlip] = colorFlip_stub;
     context->code[FixUp]     = fixUp_stub;
     context->code[ChangeRef] = changeReference_stub;
+    context->code[Get]       = get_stub;
+    context->code[Delete]    = delete_stub;
+    context->code[DeleteMax] = deleteMax_stub;
+    //    context->code[DeleteMin] = deleteMin_stub;
+    context->code[Replace_d] = replaceNode_d_stub;
+    context->code[Max]       = max_stub;
     context->code[Exit]      = exit_code;
     
     context->heap = context->heapStart;
diff -r a870c84acd0e -r 368306e1bfed src/llrb/llrbContext.h
--- a/src/llrb/llrbContext.h	Tue Sep 15 15:21:50 2015 +0900
+++ b/src/llrb/llrbContext.h	Tue Oct 20 16:22:42 2015 +0900
@@ -1,5 +1,4 @@
 /* Context definition for llrb example */
-
 #define ALLOCATE_SIZE 100
 
 enum Code {
@@ -8,6 +7,8 @@
     Code3,
     Code4,
     Code5,
+    Find,
+    Not_find,
     Code6,
     Allocator,
     Put,
@@ -21,7 +22,11 @@
     FixUp,
     ChangeRef,
     Get,
-    Traverse,
+    Delete,
+    DeleteMax,
+    DeleteMin,
+    Replace_d,
+    Max,
     Exit,
 };
 
diff -r a870c84acd0e -r 368306e1bfed src/llrb/main.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/llrb/main.c	Tue Oct 20 16:22:42 2015 +0900
@@ -0,0 +1,140 @@
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/time.h>
+
+#include "llrbContext.h"
+#include "origin_cs.h"
+#include "stack.h"
+
+static double st_time;
+static double ed_time;
+static clock_t c1,c2;
+
+int num;
+stack_ptr node_stack;
+
+extern __code initLLRBContext(struct Context* context);
+extern void allocator(struct Context* context);
+
+static double getTime() {
+    struct timeval tv;
+    gettimeofday(&tv, NULL);
+    return tv.tv_sec + (double)tv.tv_usec*1e-6;
+}
+
+void print_tree(struct Node* node, int n) {
+    if (node != 0) {
+        print_tree(node->left, n+1);
+        for (int i=0;i<n;i++)
+            printf("  ");
+        printf(/*"key=%d value=%d depth=%d */"color=%s\t%p\n", /*node->key, node->value, n, */node->color==0? "R":"B", node);
+        print_tree(node->right, n+1);
+    }
+}
+
+/* 
+__code code1(Allocate allocate) {
+    allocate.size = sizeof(long);
+    allocate.next = Code2;
+    goto Allocate(allocate);
+}
+*/
+
+__code code1(struct Context* context, struct Allocate *allocate) {
+    allocate->size = sizeof(struct Count);
+    allocator(context);
+    goto meta(context, Code2);
+}
+
+__code code1_stub(struct Context* context) {
+    goto code1(context, &context->data[Allocate]->allocate);
+}
+
+/*
+__code code2(Allocate allocate, Count count) {
+    count.count = 0;
+    goto code3(count);
+}
+*/
+
+__code code2(struct Context* context, struct Count* count) {
+    count->i = num;
+    goto meta(context, Code3);
+}
+
+__code code2_stub(struct Context* context) {
+    goto code2(context, &context->data[context->dataNum]->count);
+}
+
+__code code3(struct Context* context, struct Node* node, struct Count* count) {
+    if (count->i == 0) {
+        goto meta(context, Code4);
+    }
+
+    print_tree(context->data[Tree]->tree.root, 0);
+    puts("");
+    context->next = Code3;
+    node->key = count->i;
+    node->value = count->i;
+    
+    count->i--;
+    goto meta(context, Put);
+}
+
+__code code3_stub(struct Context* context) {
+    goto code3(context, &context->data[Node]->node, &context->data[3]->count);
+}
+
+__code code4(struct Context* context) {
+    puts("---before---");
+    print_tree(context->data[Tree]->tree.root, 0);
+    
+    struct Node* node = &context->data[Node]->node;
+    node->key = 0;
+    node->value = 0;
+    
+    context->next = Code5;
+
+    goto meta(context, DeleteMax);
+}
+
+__code code5(struct Context* context) {
+    puts("---after---");
+    print_tree(context->data[Tree]->tree.root, 0);
+    puts("--Number of Data--");
+    printf("%d\n", context->dataNum);
+
+    goto meta(context, Find);
+}
+
+__code find(struct Context* context) {
+    context->data[Node]->node.key = 2;
+    context->next = Not_find;
+
+    goto meta(context, Get);
+}
+
+__code not_find(struct Context* context) {
+    context->data[Node]->node.key = 10;
+    context->next = Code6;
+
+    printf("%p\n", context->data[Tree]->tree.current);
+    context->data[Tree]->tree.current = 0;
+    goto meta(context, Get);
+}
+
+__code code6(struct Context* context) {
+    printf("%p\n", context->data[Tree]->tree.current);
+
+    stack_free(node_stack);
+
+    goto meta(context, Exit);
+}    
+
+int main(int argc, char** argv) {
+    num = (int)atoi(argv[1]);
+    node_stack = stack_init(sizeof(union Data*), num);
+    struct Context* context = (struct Context*)malloc(sizeof(struct Context));
+    initLLRBContext(context);
+    goto start_code(context, Code1);
+}
diff -r a870c84acd0e -r 368306e1bfed src/llrb/origin_cs.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/llrb/origin_cs.c	Tue Oct 20 16:22:42 2015 +0900
@@ -0,0 +1,17 @@
+#include <stdlib.h>
+#include "llrbContext.h"
+
+__code meta(struct Context* context, enum Code next) {
+    goto (context->code[next])(context);
+}
+
+__code start_code(struct Context* context, enum Code next) {
+    goto meta(context, next);
+}
+
+__code exit_code(struct Context* context) {
+    free(context->code);
+    free(context->data);
+    free(context->heapStart);
+    goto exit(0);
+}
diff -r a870c84acd0e -r 368306e1bfed src/llrb/stack.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/llrb/stack.c	Tue Oct 20 16:22:42 2015 +0900
@@ -0,0 +1,68 @@
+#include <string.h>
+#include "stack.h"
+
+stack_ptr stack_init(size_t size, int max) {
+    stack_ptr stack_ptr;
+    
+    if ((stack_ptr = calloc(1, sizeof(stack))) == NULL)
+        return NULL;
+    
+    if ((stack_ptr->data = calloc(max, size)) == NULL) {
+        free(stack_ptr);
+        return NULL;
+    }
+
+    stack_ptr->size = size;
+    stack_ptr->max = max;
+    stack_ptr->num = 0;
+
+    return stack_ptr;
+}
+
+stack_ptr stack_realloc(stack_ptr stack_ptr, int max) {
+    if (stack_ptr == NULL)
+        return NULL;
+
+    if ((stack_ptr->data = realloc(stack_ptr->data, stack_ptr->size*max)) == NULL)
+        return NULL;
+
+    stack_ptr->max = max;
+
+    return stack_ptr;
+}
+
+void stack_free(stack_ptr stack_ptr) {
+    if (stack_ptr != NULL && stack_ptr->data != NULL) {
+        free(stack_ptr->data);
+        free(stack_ptr);
+    }
+}
+    
+int stack_push(stack_ptr stack_ptr, void* data) {
+    if (stack_ptr->max <= stack_ptr->num)
+        return -1;
+
+    memcpy((char*)stack_ptr->data+stack_ptr->num*stack_ptr->size,  data, stack_ptr->size);
+    stack_ptr->num++;
+
+    return 0;
+}
+
+int stack_pop(stack_ptr stack_ptr, void* data) {
+    if (stack_ptr->num == 0)
+        return -1;
+
+    stack_ptr->num--;
+
+    memcpy(data, (char*)stack_ptr->data+stack_ptr->num*stack_ptr->size, stack_ptr->size);
+
+    return 0;
+}
+
+int isMax(const stack_ptr stack_ptr) {
+    return stack_ptr->max<=stack_ptr->num;
+}
+
+int isEmpty(const stack_ptr stack_ptr) {
+    return stack_ptr->num<=0;
+}
diff -r a870c84acd0e -r 368306e1bfed src/llrb/stack.h
--- a/src/llrb/stack.h	Tue Sep 15 15:21:50 2015 +0900
+++ b/src/llrb/stack.h	Tue Oct 20 16:22:42 2015 +0900
@@ -1,4 +1,4 @@
-#include <string.h>
+#include <stdlib.h>
 
 typedef struct {
     size_t size;
@@ -7,68 +7,11 @@
     void* data;
 } stack, *stack_ptr;
 
-stack_ptr stack_init(size_t size, int max) {
-    stack_ptr stack_ptr;
-    
-    if ((stack_ptr = calloc(1, sizeof(stack))) == NULL)
-        return NULL;
-    
-    if ((stack_ptr->data = calloc(max, size)) == NULL) {
-        free(stack_ptr);
-        return NULL;
-    }
-
-    stack_ptr->size = size;
-    stack_ptr->max = max;
-    stack_ptr->num = 0;
-
-    return stack_ptr;
-}
-
-stack_ptr stack_realloc(stack_ptr stack_ptr, int max) {
-    if (stack_ptr == NULL)
-        return NULL;
-
-    if ((stack_ptr->data = realloc(stack_ptr->data, stack_ptr->size*max)) == NULL)
-        return NULL;
-
-    stack_ptr->max = max;
-
-    return stack_ptr;
-}
+extern stack_ptr stack_init();
+extern stack_ptr stack_realloc();
+extern void stack_free();
+extern int stack_push();
+extern int stack_pop();
+extern int isMax();
+extern int isEmpty();
 
-void stack_free(stack_ptr stack_ptr) {
-    if (stack_ptr != NULL && stack_ptr->data != NULL) {
-        free(stack_ptr->data);
-        free(stack_ptr);
-    }
-}
-    
-int stack_push(stack_ptr stack_ptr, void* data) {
-    if (stack_ptr->max <= stack_ptr->num)
-        return -1;
-
-    memcpy((char*)stack_ptr->data+stack_ptr->num*stack_ptr->size,  data, stack_ptr->size);
-    stack_ptr->num++;
-
-    return 0;
-}
-
-int stack_pop(stack_ptr stack_ptr, void* data) {
-    if (stack_ptr->num == 0)
-        return -1;
-
-    stack_ptr->num--;
-
-    memcpy(data, (char*)stack_ptr->data+stack_ptr->num*stack_ptr->size, stack_ptr->size);
-
-    return 0;
-}
-
-int isMax(const stack_ptr stack_ptr) {
-    return stack_ptr->max<=stack_ptr->num;
-}
-
-int isEmpty(const stack_ptr stack_ptr) {
-    return stack_ptr->num<=0;
-}