Mercurial > hg > GearsTemplate
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) { *\/ */