# HG changeset patch
# User Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
# Date 1447088344 -32400
# Node ID 5c4b9d116eda09b881f4fb4f43b94732cba3f0fc
# Parent  6e5b0e4245ccce3f141c3e6619cf2625ff15345a
use stack for code segment

diff -r 6e5b0e4245cc -r 5c4b9d116eda src/llrb/CMakeLists.txt
--- a/src/llrb/CMakeLists.txt	Tue Oct 27 01:15:29 2015 +0900
+++ b/src/llrb/CMakeLists.txt	Tue Nov 10 01:59:04 2015 +0900
@@ -1,5 +1,7 @@
 cmake_minimum_required(VERSION 2.8)
 
+set(CMAKE_C_COMPILER $ENV{CbC_Clang}/clang)
+
 add_executable(llrb
                main.c
                llrb.c
diff -r 6e5b0e4245cc -r 5c4b9d116eda src/llrb/llrb.c
--- a/src/llrb/llrb.c	Tue Oct 27 01:15:29 2015 +0900
+++ b/src/llrb/llrb.c	Tue Nov 10 01:59:04 2015 +0900
@@ -2,18 +2,18 @@
 
 #include "llrbContext.h"
 #include "origin_cs.h"
-#include "stack.h"
 
 extern void allocator(struct Context* context);
 extern void compare(struct Context* context, struct Tree* tree, int key1, int key2);
 
 extern int num;
-extern stack_ptr node_stack;
 
 __code put(struct Context* context, struct Tree* tree, struct Allocate* allocate) {
     allocate->size = sizeof(struct Node);
     allocator(context);
 
+    stack_push(context->code_stack, &context->next);
+
     if (tree->root == 0) {
         goto meta(context, Insert);
     } else {
@@ -29,28 +29,15 @@
 }
 
 __code replaceNode(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) {
-    stack_push(node_stack, &newNode);
+    stack_push(context->node_stack, &newNode);
 
     *newNode = *oldNode;
 
     if (result == 0) {
-        stack_pop(node_stack, &tree->current);
+        stack_pop(context->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);
+        goto meta(context, Balance1);
     } else if (result == 1) {
         tree->current = oldNode->right;
         newNode->right = context->heap;
@@ -62,7 +49,7 @@
     allocator(context);
 
     if (tree->current == 0) {
-        stack_pop(node_stack, &tree->current);
+        stack_pop(context->node_stack, &tree->current);
         goto meta(context, Insert);
     } else {
         compare(context, tree, tree->current->key, context->data[Node]->node.key);
@@ -75,6 +62,55 @@
     goto replaceNode(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result);
 }
 
+__code balance1(struct Context* context, struct Node* current) {
+    if (current->right != 0)
+        if (current->right->color == Red) {
+            context->next = Balance2;
+
+            stack_push(context->code_stack, &context->next);
+            goto meta(context, RotateL);
+        }
+
+    goto meta(context, Balance2);
+}
+
+__code balance1_stub(struct Context* context) {
+    goto balance1(context, context->data[Tree]->tree.current);
+}
+
+__code balance2(struct Context* context, struct Node* current) {
+    if (current->left != 0)
+        if (current->left->left != 0)
+            if (current->left->color == Red && current->left->left->color == Red) {
+                context->next = Balance3;
+
+                stack_push(context->code_stack, &context->next);
+                goto meta(context, RotateR);
+            }
+                
+    goto meta(context, Balance3);
+}
+
+__code balance2_stub(struct Context* context) {
+    goto balance2(context, context->data[Tree]->tree.current);
+}
+
+__code balance3(struct Context* context, struct Node* current){
+    if (current->right != 0 && current->left != 0)
+        if (current->right->color == Red && current->left->color == Red) {
+            context->next = FixUp;
+
+            stack_push(context->code_stack, &context->next);
+            goto meta(context, ColorFlip);
+        }
+    
+    goto meta(context, FixUp);    
+}
+
+__code balance3_stub(struct Context* context) {
+    goto balance3(context, context->data[Tree]->tree.current);
+}
+
 __code insertNode(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) {
     node->color = Red;
     *newNode = *node;
@@ -83,24 +119,12 @@
         newNode->color = Black;
         tree->root = newNode;
         tree->current = 0;
+
+        stack_pop(context->code_stack, &context->next);
         goto meta(context, context->next);
     }
 
-    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);
+    goto meta(context, Balance1);
 }
 
 __code insertNode_stub(struct Context* context) {
@@ -115,16 +139,8 @@
     node->color = Red;
     tree->current = tmp;
     
-    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);
+    stack_pop(context->code_stack, &context->next);
+    goto meta(context, context->next);
 }
     
 __code rotateLeft_stub(struct Context* context) {
@@ -138,12 +154,9 @@
     tmp->color = node->color;
     node->color = Red;
     context->data[Tree]->tree.current = tmp;
-
-    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);
+    stack_pop(context->code_stack, &context->next);
+    goto meta(context, context->next);
 }
 
 __code rotateRight_stub(struct Context* context) {
@@ -154,8 +167,9 @@
     node->color ^= 1;
     node->left->color ^= 1;
     node->right->color ^= 1;
-    
-    goto meta(context, FixUp);
+
+    stack_pop(context->code_stack, &context->next);
+    goto meta(context, context->next);
 }
 
 __code colorFlip_stub(struct Context* context) {
@@ -166,7 +180,7 @@
     node->key = newNode->key;
     tree->prev = newNode;
     
-    if (stack_pop(node_stack, &tree->current) == 0) {
+    if (stack_pop(context->node_stack, &tree->current) == 0) {
         compare(context, tree, tree->current->key, node->key);
         goto meta(context, ChangeRef);
     }
@@ -175,6 +189,7 @@
     tree->root = newNode;
     tree->current = 0;
     
+    stack_pop(context->code_stack, &context->next);
     goto meta(context, context->next);
 }    
 
@@ -191,20 +206,7 @@
         perror("bad status");
     }
     
-    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);
+    goto meta(context, Balance1);
 }
 
 __code changeReference_stub(struct Context* context) {
@@ -238,6 +240,8 @@
     allocate->size = sizeof(struct Node);
     allocator(context);
 
+    stack_push(context->code_stack, &context->next);
+
     tree->current = tree->root;
     compare(context, tree, tree->current->key, context->data[Node]->node.key);
     goto meta(context, Replace_d);
diff -r 6e5b0e4245cc -r 5c4b9d116eda src/llrb/llrbContext.c
--- a/src/llrb/llrbContext.c	Tue Oct 27 01:15:29 2015 +0900
+++ b/src/llrb/llrbContext.c	Tue Nov 10 01:59:04 2015 +0900
@@ -19,6 +19,9 @@
 extern __code colorFlip_stub(struct Context*);
 extern __code fixUp_stub(struct Context*);
 extern __code changeReference_stub(struct Context*);
+extern __code balance1_stub(struct Context*);
+extern __code balance2_stub(struct Context*);
+extern __code balance3_stub(struct Context*);
 extern __code get_stub(struct Context*);
 extern __code delete_stub(struct Context*);
 extern __code deleteMax_stub(struct Context*);
@@ -27,7 +30,7 @@
 extern __code max_stub(struct Context*);
 extern __code exit_code(struct Context*);
 
-__code initLLRBContext(struct Context* context) {
+__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);
@@ -50,12 +53,15 @@
     context->code[ColorFlip] = colorFlip_stub;
     context->code[FixUp]     = fixUp_stub;
     context->code[ChangeRef] = changeReference_stub;
+    context->code[Balance1]  = balance1_stub;
+    context->code[Balance2]  = balance2_stub;
+    context->code[Balance3]  = balance3_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[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;
@@ -76,4 +82,6 @@
     tree->current = 0;
     tree->prev = 0;
     
+    context->node_stack = stack_init(sizeof(union Data*), num);
+    context->code_stack = stack_init(sizeof(enum Code), 100);
 }
diff -r 6e5b0e4245cc -r 5c4b9d116eda src/llrb/llrbContext.h
--- a/src/llrb/llrbContext.h	Tue Oct 27 01:15:29 2015 +0900
+++ b/src/llrb/llrbContext.h	Tue Nov 10 01:59:04 2015 +0900
@@ -1,4 +1,6 @@
 /* Context definition for llrb example */
+#include "stack.h"
+
 #define ALLOCATE_SIZE 100
 
 enum Code {
@@ -21,6 +23,9 @@
     ColorFlip,
     FixUp,
     ChangeRef,
+    Balance1,
+    Balance2,
+    Balance3,
     Get,
     Delete,
     DeleteMax,
@@ -44,6 +49,8 @@
     void* heap;
     long heapLimit;
     int dataNum;
+    stack_ptr code_stack;
+    stack_ptr node_stack;
     union Data **data;
 };
 
diff -r 6e5b0e4245cc -r 5c4b9d116eda src/llrb/main.c
--- a/src/llrb/main.c	Tue Oct 27 01:15:29 2015 +0900
+++ b/src/llrb/main.c	Tue Nov 10 01:59:04 2015 +0900
@@ -4,16 +4,14 @@
 
 #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 __code initLLRBContext(struct Context* context, int);
 extern void allocator(struct Context* context);
 
 static double getTime() {
@@ -126,15 +124,14 @@
 __code code6(struct Context* context) {
     printf("%p\n", context->data[Tree]->tree.current);
 
-    stack_free(node_stack);
+    stack_free(context->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);
+    initLLRBContext(context, num);
     goto start_code(context, Code1);
 }
diff -r 6e5b0e4245cc -r 5c4b9d116eda src/llrb/stack.h
--- a/src/llrb/stack.h	Tue Oct 27 01:15:29 2015 +0900
+++ b/src/llrb/stack.h	Tue Nov 10 01:59:04 2015 +0900
@@ -14,4 +14,3 @@
 extern int stack_pop();
 extern int isMax();
 extern int isEmpty();
-