# HG changeset patch
# User ikkun
# Date 1475056036 -32400
# Node ID 73a679a85c04b4ee9055ce6c4f50de8fd161cdf9
# Parent  f708b271a7b8560c9ba6bee3df8f693575e4ed36
node stack rewrite

diff -r f708b271a7b8 -r 73a679a85c04 src/parallel_execution/context.h
--- a/src/parallel_execution/context.h	Tue Sep 27 17:48:17 2016 +0900
+++ b/src/parallel_execution/context.h	Wed Sep 28 18:47:16 2016 +0900
@@ -157,7 +157,8 @@
     struct Traverse {
         enum Code next;
         enum Code rotateNext;
-        struct Node* current;
+        struct Node* current; // reading node of original tree
+        struct Node* newNode; // wrting node of new tree
         int result;
     } traverse;
     struct Node {
diff -r f708b271a7b8 -r 73a679a85c04 src/parallel_execution/rb_tree.c
--- a/src/parallel_execution/rb_tree.c	Tue Sep 27 17:48:17 2016 +0900
+++ b/src/parallel_execution/rb_tree.c	Wed Sep 28 18:47:16 2016 +0900
@@ -8,7 +8,9 @@
 
 extern int num;
 
-__code put(struct Context* context, struct Tree* tree, struct Traverse* traverse, struct Node* root, struct Node* node) {
+__code put(struct Context* context, struct Tree* tree, struct Traverse* traverse, struct Node* root, struct Node* newNode) {
+    traverse->newNode = newNode;
+    tree->root = newNode; // this should done at stackClear
     if (root) {
         traverse->current = root;
         // traverse->result=compare(...)
@@ -25,7 +27,7 @@
     allocate->size = sizeof(struct Node);
     allocator(context);
     
-    context->data[Tree]->tree->root = &context->data[context->dataNum]->node;
+    context->data[Tree]->tree.root = &context->data[context->dataNum]->node;
     
     goto put(context,
              &context->data[Tree]->tree,
@@ -39,22 +41,19 @@
     element->next = traverse->stack;
     element->data = (struct Data* )newNode;
     traverse->stack = element;
+    // goto replaceNode1(struct Traverse* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, +struct Node* newnewNode, int result)
     goto meta(context, Replace1);
 }
 
 __code replaceNode_stub(struct Context* context) {
     struct Allocate* allocate = &context->data[Allocate]->allocate;
-    allocate->size = sizeof(struct Node);
-    allocator(context);
-    struct Node* newNode = &context->data[context->dataNum]->node;
-
     allocate->size = sizeof(struct Element);
     allocator(context);
     struct Element* element = &context->data[context->dataNum]->node;
     goto replaceNode(context,
                   &context->data[Traverse]->traverse,
                   context->data[Traverse]->traverse.current,
-                  newNode,
+                  context->data[Traverse]->traverse.newNode,
                   element);
 }
 
@@ -70,7 +69,7 @@
         traverse->current = oldNode->left;
         newNode->left = newnewNode;
     }
-
+    traverse->newNode = newnewNode;
     if (traverse->current) {
         compare(context, traverse, traverse->current->key, node->key);
         goto meta(context, Replace);
@@ -93,34 +92,34 @@
                      context->data[Traverse]->traverse.result);
 }
 
-__code insertNode(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* newNode) {
-    node->color = Red;
+__code insertNode(struct Context* context, struct Traverse* traverse, struct Tree* tree, struct Node* node, struct Node* newNode) {
     *newNode = *node;
-    
+    newNode->color = Red;
     traverse->current = newNode;
-
+    tree->root->color = Black;
     goto meta(context, InsertCase1);
 }
 
 __code insertNode_stub(struct Context* context) {
     goto insertNode(context,
                     &context->data[Traverse]->traverse,
+                    &context->data[Tree]->tree,
                     &context->data[Node]->node,
-                    &context->data[context->dataNum]->node);
+                    &context->data[Traverse]->traverse.newNode);
 }
 
-__code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) {
-    if (!isEmpty(context->node_stack)) // parent!=null
+__code insertCase1(struct Context* context, struct Node* parent) {
+    if (parent!=NULL) {
         goto meta(context, InsertCase2);
-    tree->root->color = Black;
+    }
     goto meta(context, StackClear);
 }
 
 __code insert1_stub(struct Context* context) {
-    goto insertCase1(context, &context->data[Tree]->tree, context->data[Traverse]->traverse.current);
+    goto insertCase1(context, (struct Node*)context->data[Traverse]->traverse.nodeStack->element);
 }
 
-__code insertCase2(struct Context* context, struct Node* current) {
+__code insertCase2(struct Context* context, struct Node* parent) {
     if (parent->color == Black) {
         goto meta(context, StackClear);
     }
@@ -128,10 +127,10 @@
 }
 
 __code insert2_stub(struct Context* context) {
-    goto insertCase2(context, context->data[Traverse]->traverse.current);
+    goto insertCase2(context, (struct Node*)context->data[Traverse]->traverse.nodeStack->element);
 }
 
-__code insertCase3(struct Context* context, struct Traverse* traverse, struct Node* current, struct Node* pararent, struct Node* grandparent) {
+__code insertCase3(struct Context* context, struct Traverse* traverse, struct Node* pararent, struct Node* grandparent) {
     struct Node* uncle;
 
     if (grandparent->left == parent)
@@ -145,48 +144,36 @@
         uncle->color = Black;
         grandparent->color = Red;
         traverse->current = grandparent;
-        goto meta(context, StackPop2);
+        goto meta(context, insertCase31);
     }
-
-    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[Traverse]->traverse, context->data[Traverse]->traverse.current);
+    goto insertCase3(context, &context->data[Traverse]->traverse,
+                     (struct Node*)context->data[Traverse]->traverse.nodeStack->element,
+                     (struct Node*)context->data[Traverse]->traverse.nodeStack->next->element
+        );
 }
-__code stackPop2(struct Context* context, struct Traverse* traverse, struct Node* current) {
-    stack_pop(context->node_stack, &parent);
-    stack_pop(context->node_stack, &grandparent);
+__code insertCase31(struct Context* context, struct Traverse* traverse) {
+    traverse->nodeStack = traverse->nodeStack->next->next;
     goto meta(context, InsertCase1);
 }
-__code stackPop2_stub(struct Context* context) {
-    goto stackPop2(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current);
+__code insert31_stub(struct Context* context) {
+    goto insertCase31(context, &context->data[Traverse]->traverse);
 }
 
-__code insertCase4(struct Context* context, struct Traverse* traverse, 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);
-
+__code insertCase4(struct Context* context, struct Traverse* traverse, struct Node* current,struct Node* parent, struct Node* grandparent) {
     traverse->current = parent;
 
     if ((current == parent->right) && (parent == grandparent->left)) {
         traverse->rotateNext = InsertCase4_1;
-        goto meta(context, RotateL);
+        goto meta(context, InsertCase4_01);
     } else if ((current == parent->left) && (parent == grandparent->right)) {
         traverse->rotateNext = InsertCase4_2;
-        goto meta(context, RotateR);
+        goto meta(context, InsertCase4_02);
     }
 
-    stack_push(context->node_stack, &parent);
     traverse->current = current;
     goto meta(context, InsertCase5);
 }
@@ -195,33 +182,51 @@
     goto insertCase4(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current);
 }
 
+__code insertCase4_01(struct Context* context, struct Traverse* traverse) {
+    context->data[Traverse]->traverse.nodeStack = context->data[Traverse]->traverse.nodeStack -> next; 
+    goto meta(context, RotateL);
+}
+
+__code insert4_01_stub(struct Context* context) {
+    goto insertCase4_01(context, &context->data[Traverse]->traverse);
+}   
 __code insertCase4_1(struct Context* context, struct Traverse* traverse) {
-    stack_push(context->node_stack, &traverse->current);
     traverse->current = traverse->current->left;
     goto meta(context, InsertCase5);
 }
 
 __code insert4_1_stub(struct Context* context) {
+    struct Allocate* allocate = &context->data[Allocate]->allocate;
+    allocate->size = sizeof(struct Element);
+    allocator(context);
+    struct Element* element = &context->data[context->dataNum]->node;
+    element->data = (struct Data*)traverse->current;
     goto insertCase4_1(context, &context->data[Traverse]->traverse);
 }   
+__code insertCase4_02(struct Context* context, struct Traverse* traverse) {
+    context->data[Traverse]->traverse.nodeStack = context->data[Traverse]->traverse.nodeStack -> next; 
+    goto meta(context, RotateR);
+}
+
+__code insert4_02_stub(struct Context* context) {
+    goto insertCase4_02(context, &context->data[Traverse]->traverse);
+}   
 
 __code insertCase4_2(struct Context* context, struct Traverse* traverse) {
-    stack_push(context->node_stack, &traverse->current);
     traverse->current = traverse->current->right;
     goto meta(context, InsertCase5);
 }
 
 __code insert4_2_stub(struct Context* context) {
+    struct Allocate* allocate = &context->data[Allocate]->allocate;
+    allocate->size = sizeof(struct Element);
+    allocator(context);
+    struct Element* element = &context->data[context->dataNum]->node;
+    element->data = (struct Data*)traverse->current;
     goto insertCase4_2(context, &context->data[Traverse]->traverse);
 }   
 
-__code insertCase5(struct Context* context, struct Traverse* traverse, struct Node* current) {
-    struct Node* parent;
-    struct Node* grandparent;
-
-    stack_pop(context->node_stack, &parent);
-    stack_pop(context->node_stack, &grandparent);
-    
+__code insertCase5(struct Context* context, struct Traverse* traverse, struct Node* current, struct Node* parent, struct Node* grandparant) {
     parent->color = Black;
     grandparent->color = Red;
 
@@ -234,11 +239,15 @@
 }
 
 __code insert5_stub(struct Context* context) {
+    struct Traverse* traverse = context->data[Traverse]->traverse;
+    struct Node* parent = (struct Node*)traverse->nodeStack->data;
+    struct Node* grandparent = (struct Node*)traverse->nodeStack->next->data;
+    traverse->nodeStack = traverse->nodeStack->next->next;
     goto insertCase5(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current);
 }
 
 // put rotateLeft's continuation as argument
-__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) {
+__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) {
     struct Node* tmp = node->right;
     struct Node* parent = 0;