diff src/parallel_execution/rb_tree.c @ 91:1e074c3878c7

modify tree
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Tue, 26 Jan 2016 07:46:26 +0900
parents 9e139a340bd1
children 851da1107223
line wrap: on
line diff
--- a/src/parallel_execution/rb_tree.c	Tue Jan 26 06:47:35 2016 +0900
+++ b/src/parallel_execution/rb_tree.c	Tue Jan 26 07:46:26 2016 +0900
@@ -4,11 +4,11 @@
 #include "origin_cs.h"
 
 extern void allocator(struct Context* context);
-extern void compare(struct Context* context, struct Tree* tree, int key1, int key2);
+extern void compare(struct Context* context, struct Traverse* traverse, int key1, int key2);
 
 extern int num;
 
-__code put(struct Context* context, struct Tree* tree, struct Node* root, struct Allocate* allocate) {
+__code put(struct Context* context, struct Tree* tree, struct Traverse* traverse, struct Node* root, struct Allocate* allocate) {
     allocate->size = sizeof(struct Node);
     allocator(context);
     
@@ -20,8 +20,8 @@
     tree->root = &context->data[context->dataNum]->node;
     
     if (root) {
-        tree->current = root;
-        compare(context, tree, tree->current->key, context->data[Node]->node.key);
+        traverse->current = root;
+        compare(context, traverse, traverse->current->key, context->data[Node]->node.key);
 
         goto meta(context, Replace);
     }
@@ -30,10 +30,14 @@
 }
 
 __code put_stub(struct Context* context) {
-    goto put(context, &context->data[Tree]->tree, context->data[Tree]->tree.root, &context->data[Allocate]->allocate);
+    goto put(context,
+             &context->data[Tree]->tree,
+             &context->data[Traverse]->traverse,
+             context->data[Tree]->tree.root,
+             &context->data[Allocate]->allocate);
 }
 
-__code replaceNode(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) {
+__code replaceNode(struct Context* context, struct Traverse* traverse, struct Node* oldNode, struct Node* newNode, int result) {
     *newNode = *oldNode;
     stack_push(context->node_stack, &newNode);
 
@@ -43,17 +47,17 @@
         stack_pop(context->code_stack, &context->next);
         goto meta(context, context->next);
     } else if (result == GT) {
-        tree->current = oldNode->right;
+        traverse->current = oldNode->right;
         newNode->right = context->heap;
     } else {
-        tree->current = oldNode->left;
+        traverse->current = oldNode->left;
         newNode->left = context->heap;
     }
 
     allocator(context);
 
-    if (tree->current) {
-        compare(context, tree, tree->current->key, context->data[Node]->node.key);
+    if (traverse->current) {
+        compare(context, traverse, traverse->current->key, context->data[Node]->node.key);
         goto meta(context, Replace);
     }
     
@@ -61,20 +65,27 @@
 }
 
 __code replaceNode_stub(struct Context* context) {
-    goto replaceNode(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result);
+    goto replaceNode(context,
+                     &context->data[Traverse]->traverse,
+                     context->data[Traverse]->traverse.current,
+                     &context->data[context->dataNum]->node,
+                     context->data[Traverse]->traverse.result);
 }
 
-__code insertNode(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) {
+__code insertNode(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* newNode) {
     node->color = Red;
     *newNode = *node;
     
-    tree->current = newNode;
+    traverse->current = newNode;
 
     goto meta(context, InsertCase1);
 }
 
 __code insertNode_stub(struct Context* context) {
-    goto insertNode(context, &context->data[Tree]->tree, &context->data[Node]->node, &context->data[context->dataNum]->node);
+    goto insertNode(context,
+                    &context->data[Traverse]->traverse,
+                    &context->data[Node]->node,
+                    &context->data[context->dataNum]->node);
 }
 
 __code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) {
@@ -88,7 +99,7 @@
 }
 
 __code insert1_stub(struct Context* context) {
-    goto insertCase1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+    goto insertCase1(context, &context->data[Tree]->tree, context->data[Traverse]->traverse.current);
 }
 
 __code insertCase2(struct Context* context, struct Node* current) {
@@ -105,10 +116,10 @@
 }
 
 __code insert2_stub(struct Context* context) {
-    goto insertCase2(context, context->data[Tree]->tree.current);
+    goto insertCase2(context, context->data[Traverse]->traverse.current);
 }
 
-__code insertCase3(struct Context* context, struct Tree* tree, struct Node* current) {
+__code insertCase3(struct Context* context, struct Traverse* traverse, struct Node* current) {
     struct Node* parent;
     struct Node* uncle;
     struct Node* grandparent;
@@ -125,7 +136,7 @@
         parent->color = Black;
         uncle->color = Black;
         grandparent->color = Red;
-        tree->current = grandparent;
+        traverse->current = grandparent;
         goto meta(context, InsertCase1);
     }
 
@@ -136,10 +147,10 @@
 }
 
 __code insert3_stub(struct Context* context) {
-    goto insertCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+    goto insertCase3(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current);
 }
 
-__code insertCase4(struct Context* context, struct Tree* tree, struct Node* current) {
+__code insertCase4(struct Context* context, struct Traverse* traverse, struct Node* current) {
     struct Node* parent;
     struct Node* grandparent;
 
@@ -148,7 +159,7 @@
 
     stack_push(context->node_stack, &grandparent);
 
-    tree->current = parent;
+    traverse->current = parent;
 
     if ((current == parent->right) && (parent == grandparent->left)) {
         context->next = InsertCase4_1;
@@ -163,35 +174,35 @@
     }
 
     stack_push(context->node_stack, &parent);
-    tree->current = current;
+    traverse->current = current;
     goto meta(context, InsertCase5);
 }
 
 __code insert4_stub(struct Context* context) {
-    goto insertCase4(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+    goto insertCase4(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current);
 }
 
-__code insertCase4_1(struct Context* context, struct Tree* tree) {
-    stack_push(context->node_stack, &tree->current);
-    tree->current = tree->current->left;
+__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) {
-    goto insertCase4_1(context, &context->data[Tree]->tree);
+    goto insertCase4_1(context, &context->data[Traverse]->traverse);
 }   
 
-__code insertCase4_2(struct Context* context, struct Tree* tree) {
-    stack_push(context->node_stack, &tree->current);
-    tree->current = tree->current->right;
+__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) {
-    goto insertCase4_2(context, &context->data[Tree]->tree);
+    goto insertCase4_2(context, &context->data[Traverse]->traverse);
 }   
 
-__code insertCase5(struct Context* context, struct Tree* tree, struct Node* current) {
+__code insertCase5(struct Context* context, struct Traverse* traverse, struct Node* current) {
     struct Node* parent;
     struct Node* grandparent;
 
@@ -201,7 +212,7 @@
     parent->color = Black;
     grandparent->color = Red;
 
-    tree->current = grandparent;
+    traverse->current = grandparent;
 
     if ((current == parent->left) && (parent == grandparent->left))
         goto meta(context, RotateR);
@@ -210,10 +221,10 @@
 }
 
 __code insert5_stub(struct Context* context) {
-    goto insertCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+    goto insertCase5(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current);
 }
 
-__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree) {
+__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) {
     struct Node* tmp = node->right;
     struct Node* parent = 0;
     
@@ -232,17 +243,20 @@
     
     node->right = tmp->left;
     tmp->left = node;
-    tree->current = tmp;
+    traverse->current = tmp;
     
     stack_pop(context->code_stack, &context->next);
     goto meta(context, context->next);
 }
     
 __code rotateLeft_stub(struct Context* context) {
-    goto rotateLeft(context, context->data[Tree]->tree.current, &context->data[Tree]->tree);
+    goto rotateLeft(context,
+                    context->data[Traverse]->traverse.current,
+                    &context->data[Tree]->tree,
+                    &context->data[Traverse]->traverse);
 }
 
-__code rotateRight(struct Context* context, struct Node* node, struct Tree* tree) {
+__code rotateRight(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) {
     struct Node* tmp = node->left;
     struct Node* parent = 0;
     
@@ -261,28 +275,31 @@
     
     node->left = tmp->right;
     tmp->right = node;
-    tree->current = tmp;
+    traverse->current = tmp;
     
     stack_pop(context->code_stack, &context->next);
     goto meta(context, context->next);
 }
 
 __code rotateRight_stub(struct Context* context) {
-    goto rotateRight(context, context->data[Tree]->tree.current, &context->data[Tree]->tree);
+    goto rotateRight(context,
+                     context->data[Traverse]->traverse.current,
+                     &context->data[Tree]->tree,
+                     &context->data[Traverse]->traverse);
 }
 
-__code stackClear(struct Context* context, stack_ptr node_stack, struct Tree* tree) {
-    if (stack_pop(node_stack, &tree->current) == 0)
+__code stackClear(struct Context* context, stack_ptr node_stack, struct Traverse* traverse) {
+    if (stack_pop(node_stack, &traverse->current) == 0)
         goto meta(context, StackClear);
 
-    tree->current = 0;
+    traverse->current = 0;
 
     stack_pop(context->code_stack, &context->next);
     goto meta(context, context->next);
 }
 
 __code stackClear_stub(struct Context* context) {
-    goto stackClear(context, context->node_stack, &context->data[Tree]->tree);
+    goto stackClear(context, context->node_stack, &context->data[Traverse]->traverse);
 }
     
 
@@ -301,29 +318,29 @@
 /* /\*     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); *\/ */
+__code search(struct Context* context, struct Traverse* traverse, struct Node* node) {
+    compare(context, traverse, traverse->current->key, node->key);
     
-/* /\*     if (tree->result == EQ) { *\/ */
-/* /\*         *node = *tree->current; *\/ */
+    if (traverse->result == EQ) {
+        *node = *traverse->current;
         
-/* /\*         goto meta(context, context->next); *\/ */
-/* /\*     } else if (tree->result == GT) { *\/ */
-/* /\*         tree->current = tree->current->right; *\/ */
-/* /\*     } else { *\/ */
-/* /\*         tree->current = tree->current->left; *\/ */
-/* /\*     } *\/ */
+        goto meta(context, context->next);
+    } else if (traverse->result == GT) {
+        traverse->current = traverse->current->right;
+    } else {
+        traverse->current = traverse->current->left;
+    }
         
-/* /\*     if (tree->current) *\/ */
-/* /\*         goto meta(context, Search); *\/ */
+    if (traverse->current)
+        goto meta(context, Search);
 
-/* /\*     stack_pop(context->code_stack, &context->next); *\/ */
-/* /\*     goto meta(context, context->next); *\/ */
-/* /\* } *\/ */
+    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 search_stub(struct Context* context) {
+    goto search(context, &context->data[Traverse]->traverse, &context->data[Node]->node);
+}
 
 /* /\* __code delete(struct Context* context, struct Tree* tree) { *\/ */
 /* /\*     if (tree->root) { *\/ */