changeset 136:c7ac153f86dd

Fix rotate cs stack
author one
date Thu, 29 Sep 2016 19:02:49 +0900
parents 9ae7ce6c83f5
children fe1fbfec7d01
files src/parallel_execution/rb_tree.c
diffstat 1 files changed, 26 insertions(+), 22 deletions(-) [+]
line wrap: on
line diff
--- a/src/parallel_execution/rb_tree.c	Thu Sep 29 17:18:15 2016 +0900
+++ b/src/parallel_execution/rb_tree.c	Thu Sep 29 19:02:49 2016 +0900
@@ -6,9 +6,26 @@
 extern void allocator(struct Context* context);
 extern void compare(struct Context* context, struct Traverse* traverse, int key1, int key2);
 
-extern int num;
+void printTree1(union Data* data) {
+    struct Node* node = (struct Node*)data;
+    if (node == NULL) {
+        printf("NULL");
+    } else {
+        printf("key = %d (", node->key);
+        printTree1((union Data*)node->right);
+        printf("), (");
+        printTree1((union Data*)node->left);
+        printf(")");
+    }
+}
+
+void printTree(union Data* data) {
+    printTree1(data);
+    printf("\n");
+}
 
 __code put(struct Context* context, struct Tree* tree, struct Node* node, struct Traverse* traverse, struct Node* root, struct Node* newNode) {
+    printTree((union Data*)tree->root);
     traverse->newNode = newNode;
     tree->root = newNode; // this should done at stackClear
     if (root) {
@@ -186,7 +203,8 @@
 }
 
 __code insertCase4_01(struct Context* context, struct Traverse* traverse) {
-    context->data[Traverse]->traverse.nodeStack = context->data[Traverse]->traverse.nodeStack -> next; 
+    traverse->nodeStack = traverse->nodeStack -> next; 
+    traverse->rotateNext = InsertCase5;
     goto meta(context, RotateL);
 }
 
@@ -208,7 +226,8 @@
     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; 
+    traverse->nodeStack = traverse->nodeStack -> next; 
+    traverse->rotateNext = InsertCase5;
     goto meta(context, RotateR);
 }
 
@@ -252,7 +271,7 @@
 }
 
 // put rotateLeft's continuation as argument
-__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent, struct Element* element) {
+__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) {
     struct Node* tmp = node->right;
 
     if (parent) {
@@ -263,7 +282,6 @@
     } else {
         tree->root = tmp;
     }
-    element->data = (union Data*)parent;
 
     node->right = tmp->left;
     tmp->left = node;
@@ -275,20 +293,14 @@
 __code rotateLeft_stub(struct Context* context) {
     struct Traverse* traverse = &context->data[Traverse]->traverse;
     struct Node* parent = (traverse->nodeStack)?(struct Node*)traverse->nodeStack->data:NULL;
-    traverse->nodeStack = traverse->nodeStack->next;
-    struct Allocate* allocate = &context->data[Allocate]->allocate;
-    allocate->size = sizeof(struct Element);
-    allocator(context);
-    struct Element* element = &context->data[context->dataNum]->element;
     goto rotateLeft(context,
                     context->data[Traverse]->traverse.current,
                     &context->data[Tree]->tree,
                     &context->data[Traverse]->traverse,
-                    parent,
-                    element);
+                    parent);
 }
 
-__code rotateRight(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent, struct Element* element) {
+__code rotateRight(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) {
     struct Node* tmp = node->left;
     
     if (parent) {
@@ -300,8 +312,6 @@
         tree->root = tmp;
     }
 
-    element->data = (union Data*)parent;    
-
     node->left = tmp->right;
     tmp->right = node;
     traverse->current = tmp;
@@ -312,17 +322,11 @@
 __code rotateRight_stub(struct Context* context) {
     struct Traverse* traverse = &context->data[Traverse]->traverse;
     struct Node* parent = (traverse->nodeStack)?(struct Node*)traverse->nodeStack->data:NULL;
-    traverse->nodeStack = traverse->nodeStack->next;
-    struct Allocate* allocate = &context->data[Allocate]->allocate;
-    allocate->size = sizeof(struct Element);
-    allocator(context);
-    struct Element* element = &context->data[context->dataNum]->element;
     goto rotateRight(context,
                      context->data[Traverse]->traverse.current,
                      &context->data[Tree]->tree,
                      &context->data[Traverse]->traverse,
-                     parent,
-                     element);
+                     parent);
 }
 
 __code stackClear(struct Context* context, stack_ptr node_stack, struct Traverse* traverse) {