Mercurial > hg > Members > Moririn
changeset 469:ed494f4004c9
add RedBlackTree.cbc insert Test
| author | ryokka |
|---|---|
| date | Wed, 27 Dec 2017 18:26:37 +0900 |
| parents | ac244346c85d |
| children | 355f7f78e3cf |
| files | src/parallel_execution/RedBlackTree.cbc src/parallel_execution/test/rbTree_test.cbc |
| diffstat | 2 files changed, 369 insertions(+), 349 deletions(-) [+] |
line wrap: on
line diff
--- a/src/parallel_execution/RedBlackTree.cbc Mon Dec 25 18:10:56 2017 +0900 +++ b/src/parallel_execution/RedBlackTree.cbc Wed Dec 27 18:26:37 2017 +0900 @@ -3,6 +3,7 @@ #include "../context.h" #interface "Tree.h" #interface "Stack.h" +#include "compare.c" extern enum Relational compare(struct Node* node1, struct Node* node2); @@ -11,7 +12,7 @@ struct RedBlackTree* redBlackTree = new RedBlackTree(); tree->tree = (union Data*)redBlackTree; redBlackTree->root = NULL; - redBlackTree->nodeStack = (union Data*)createSingleLinkedStack(context); + redBlackTree->nodeStack = createSingleLinkedStack(context); tree->put = C_putRedBlackTree; tree->get = C_getRedBlackTree; // tree->remove = C_removeRedBlackTree; @@ -58,7 +59,7 @@ struct Node* newNode = tree->newNode; tree->previous = newNode; *newNode = *oldNode; - goto nodeStack->push(newNode, replaceNode1); + goto nodeStack->push((union Data*)newNode, findNode1); } __code findNode1(struct RedBlackTree* tree, struct Node* node, __code next(...)) { @@ -311,344 +312,344 @@ goto next(...); } -/* /\* __code delete(struct Context* context, struct Tree* tree) { *\/ */ -/* /\* if (tree->root) { *\/ */ -/* /\* stack_push(context->code_stack, &context->next); *\/ */ -/* /\* context->next = Delete1; *\/ */ -/* /\* goto meta(context, Get); *\/ */ -/* /\* } *\/ */ - -/* /\* goto meta(context, context->next); *\/ */ -/* /\* } *\/ */ - -/* /\* __code delete_stub(struct Context* context) { *\/ */ -/* /\* goto delete(context, &context->data[Tree]->tree); *\/ */ -/* /\* } *\/ */ - -/* /\* __code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) { *\/ */ -/* /\* allocate->size = sizeof(struct Node); *\/ */ -/* /\* allocator(context); *\/ */ - -/* /\* struct Node* root = tree->root; *\/ */ - -/* /\* tree->root = &context->data[context->dataNum]->node; *\/ */ -/* /\* tree->current = root; *\/ */ - -/* /\* compare(context, tree, tree->current->key, context->data[Node]->node.key); *\/ */ - -/* /\* goto meta(context, Replace_d1); *\/ */ -/* /\* } *\/ */ - -/* /\* __code delete1_stub(struct Context* context) { *\/ */ -/* /\* goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate); *\/ */ -/* /\* } *\/ */ - -/* /\* __code delete2(struct Context* context, struct Node* current) { *\/ */ -/* /\* if (current->color == Black) { *\/ */ -/* /\* struct Node* child = current->right == NULL ? current->left : current->right; *\/ */ -/* /\* current->color = child == NULL ? Black : child->color; *\/ */ - -/* /\* goto meta(context, DeleteCase1); *\/ */ -/* /\* } *\/ */ - -/* /\* goto meta(context, Delete3); *\/ */ -/* /\* } *\/ */ - -/* /\* __code delete2_stub(struct Context* context) { *\/ */ -/* /\* goto delete2(context, context->data[Tree]->tree.current); *\/ */ -/* /\* } *\/ */ - -/* /\* __code delete3(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ -/* /\* struct Node* tmp = current->right == NULL ? current->left : current->right; *\/ */ - -/* /\* if (current->parent) { *\/ */ -/* /\* if (current == current->parent->left) *\/ */ -/* /\* current->parent->left = tmp; *\/ */ -/* /\* else *\/ */ -/* /\* current->parent->right = tmp; *\/ */ -/* /\* } else { *\/ */ -/* /\* tree->root = tmp; *\/ */ -/* /\* } *\/ */ - -/* /\* if (tmp) *\/ */ -/* /\* tmp->parent = current->parent; *\/ */ - -/* /\* if (current->parent == NULL && tmp) *\/ */ -/* /\* tmp->color = Black; *\/ */ - -/* /\* current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL); *\/ */ - -/* /\* stack_pop(context->code_stack, &context->next); *\/ */ -/* /\* goto meta(context, context->next); *\/ */ -/* /\* } *\/ */ - -/* /\* __code delete3_stub(struct Context* context) { *\/ */ -/* /\* goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ -/* /\* } *\/ */ - -/* /\* __code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) { *\/ */ -/* /\* *newNode = *oldNode; *\/ */ - -/* /\* if (result == EQ) *\/ */ -/* /\* goto meta(context, Replace_d2); *\/ */ -/* /\* else if (result == GT) *\/ */ -/* /\* tree->current = newNode->right; *\/ */ -/* /\* else *\/ */ -/* /\* tree->current = newNode->left; *\/ */ - -/* /\* tree->current->parent = newNode; *\/ */ - -/* /\* if (tree->current->left == NULL && tree->current->right == NULL) *\/ */ -/* /\* goto meta(context, Delete2); *\/ */ - -/* /\* if (result == GT) *\/ */ -/* /\* newNode->right = context->heap; *\/ */ -/* /\* else if (result == LT) *\/ */ -/* /\* newNode->left = context->heap; *\/ */ - -/* /\* allocator(context); *\/ */ - -/* /\* compare(context, tree, tree->current->key, context->data[Node]->node.key); *\/ */ - -/* /\* goto meta(context, Replace_d1); *\/ */ -/* /\* } *\/ */ - -/* /\* __code replaceNodeForDelete1_stub(struct Context* context) { *\/ */ -/* /\* goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result); *\/ */ -/* /\* } *\/ */ - -/* /\* __code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) { *\/ */ -/* /\* if (tree->current->left && tree->current->right) { *\/ */ -/* /\* newNode->left->parent = newNode; *\/ */ -/* /\* tree->current = newNode->left; *\/ */ -/* /\* newNode->left = context->heap; *\/ */ -/* /\* tree->deleted = newNode; *\/ */ - -/* /\* allocator(context); *\/ */ -/* /\* tree->current->parent = newNode; *\/ */ - -/* /\* goto meta(context, FindMax1); *\/ */ -/* /\* } *\/ */ - -/* /\* goto meta(context, Delete2); *\/ */ -/* /\* } *\/ */ - -/* /\* __code replaceNodeForDelete2_stub(struct Context* context) { *\/ */ -/* /\* goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node); *\/ */ -/* /\* } *\/ */ - -/* /\* __code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { *\/ */ -/* /\* *newNode = *oldNode; *\/ */ - -/* /\* if (newNode->right) *\/ */ -/* /\* goto meta(context, FindMax2); *\/ */ - -/* /\* tree->deleted->key = newNode->key; *\/ */ -/* /\* tree->deleted->value = newNode->value; *\/ */ - -/* /\* tree->current = newNode; *\/ */ - -/* /\* goto meta(context, Delete2); *\/ */ -/* /\* } *\/ */ - -/* /\* __code findMax1_stub(struct Context* context) { *\/ */ -/* /\* goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); *\/ */ -/* /\* } *\/ */ - - -/* /\* __code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { *\/ */ -/* /\* *newNode = *oldNode; *\/ */ - -/* /\* if (newNode->right->right) { *\/ */ -/* /\* tree->current = newNode->right; *\/ */ -/* /\* newNode->right = context->heap; *\/ */ - -/* /\* allocator(context); *\/ */ -/* /\* tree->current->parent = newNode; *\/ */ - -/* /\* goto meta(context, FindMax2); *\/ */ -/* /\* } *\/ */ - -/* /\* tree->deleted->key = newNode->right->key; *\/ */ -/* /\* tree->deleted->value = newNode->right->value; *\/ */ - -/* /\* tree->current = newNode; *\/ */ - -/* /\* goto meta(context, Delete2); *\/ */ -/* /\* } *\/ */ - -/* /\* __code findMax2_stub(struct Context* context) { *\/ */ -/* /\* goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase1(struct Context* context, struct Node* current) { *\/ */ -/* /\* if (current->parent) *\/ */ -/* /\* goto meta(context, DeleteCase2); *\/ */ - -/* /\* goto meta(context, Delete3); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase1_stub(struct Context* context) { *\/ */ -/* /\* goto deleteCase1(context, context->data[Tree]->tree.current); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ -/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ - -/* /\* if ((sibling == NULL ? Black : sibling->color) == Red) { *\/ */ -/* /\* current->parent->color = Red; *\/ */ -/* /\* sibling->color = Black; *\/ */ - -/* /\* current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap); *\/ */ -/* /\* allocator(context); *\/ */ -/* /\* context->data[context->dataNum]->node = *sibling; *\/ */ - -/* /\* tree->current = current->parent; *\/ */ - -/* /\* context->next = DeleteCase3; *\/ */ -/* /\* stack_push(context->code_stack, &context->next); *\/ */ - -/* /\* if (current == current->parent->left) *\/ */ -/* /\* goto meta(context, RotateL); *\/ */ -/* /\* else *\/ */ -/* /\* goto meta(context, RotateR); *\/ */ -/* /\* } *\/ */ - -/* /\* goto meta(context, DeleteCase3); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase2_stub(struct Context* context) { *\/ */ -/* /\* goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ -/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ - -/* /\* if (current->parent->color == Black && *\/ */ -/* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */ -/* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */ -/* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */ -/* /\* sibling->color = Red; *\/ */ - -/* /\* tree->current = current->parent; *\/ */ -/* /\* goto meta(context, DeleteCase1); *\/ */ -/* /\* } *\/ */ - -/* /\* goto meta(context, DeleteCase4); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase3_stub(struct Context* context) { *\/ */ -/* /\* goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase4(struct Context* context, struct Node* current) { *\/ */ -/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ - -/* /\* if (current->parent->color == Red && *\/ */ -/* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */ -/* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */ -/* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */ -/* /\* sibling->color = Red; *\/ */ -/* /\* current->parent->color = Black; *\/ */ - -/* /\* goto meta(context, Delete3); *\/ */ -/* /\* } *\/ */ - -/* /\* goto meta(context, DeleteCase5); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase4_stub(struct Context* context) { *\/ */ -/* /\* goto deleteCase4(context, context->data[Tree]->tree.current); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ -/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ -/* /\* sibling->parent = current->parent; *\/ */ - -/* /\* if (current == current->parent->left && *\/ */ -/* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */ -/* /\* (sibling->left == NULL ? Black : sibling->left->color) == Red && *\/ */ -/* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */ -/* /\* sibling->color = Red; *\/ */ -/* /\* sibling->left->color = Black; *\/ */ - -/* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */ -/* /\* allocator(context); *\/ */ -/* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */ -/* /\* *tmp = *sibling; *\/ */ -/* /\* tmp->parent = current; *\/ */ - -/* /\* tmp->left = context->heap; *\/ */ -/* /\* allocator(context); *\/ */ -/* /\* context->data[context->dataNum]->node = *sibling->left; *\/ */ -/* /\* context->data[context->dataNum]->node.parent = tmp; *\/ */ - -/* /\* tree->current = tmp; *\/ */ - -/* /\* context->next = DeleteCase6; *\/ */ -/* /\* stack_push(context->code_stack, &context->next); *\/ */ - -/* /\* goto meta(context, RotateR); *\/ */ -/* /\* } else if (current == current->parent->right && *\/ */ -/* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */ -/* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */ -/* /\* (sibling->right == NULL ? Black : sibling->right->color) == Red) { *\/ */ -/* /\* sibling->color = Red; *\/ */ -/* /\* sibling->right->color = Black; *\/ */ - -/* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */ -/* /\* allocator(context); *\/ */ -/* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */ -/* /\* *tmp = *sibling; *\/ */ -/* /\* tmp->parent = current; *\/ */ - -/* /\* tmp->right = context->heap; *\/ */ -/* /\* allocator(context); *\/ */ -/* /\* context->data[context->dataNum]->node = *sibling->right; *\/ */ -/* /\* context->data[context->dataNum]->node.parent = tmp; *\/ */ - -/* /\* tree->current = tmp; *\/ */ - -/* /\* context->next = DeleteCase6; *\/ */ -/* /\* stack_push(context->code_stack, &context->next); *\/ */ -/* /\* goto meta(context, RotateL); *\/ */ -/* /\* } *\/ */ - -/* /\* goto meta(context, DeleteCase6); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase5_stub(struct Context* context) { *\/ */ -/* /\* goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ -/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ - -/* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */ -/* /\* allocator(context); *\/ */ -/* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */ -/* /\* *tmp = *sibling; *\/ */ -/* /\* tmp->parent = current; *\/ */ - -/* /\* tmp->color = current->parent->color; *\/ */ -/* /\* current->parent->color = Black; *\/ */ - -/* /\* context->next = Delete3; *\/ */ -/* /\* stack_push(context->code_stack, &context->next); *\/ */ - -/* /\* if (current == current->parent->left) { *\/ */ -/* /\* tmp->right->color = Black; *\/ */ -/* /\* tree->current = current->parent; *\/ */ - -/* /\* goto meta(context, RotateL); *\/ */ -/* /\* } else { *\/ */ -/* /\* tmp->left->color = Black; *\/ */ -/* /\* tree->current = current->parent; *\/ */ - -/* /\* goto meta(context, RotateR); *\/ */ -/* /\* } *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase6_stub(struct Context* context) { *\/ */ -/* /\* goto deleteCase6(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ -/* /\* } *\/ */ +// __code delete(struct Context* context, struct Tree* tree) { +// if (tree->root) { +// stack_push(context->code_stack, &context->next); +// context->next = Delete1; +// goto meta(context, Get); +// } +// +// goto meta(context, context->next); +// } +// +// __code delete_stub(struct Context* context) { +// goto delete(context, &context->data[Tree]->tree); +// } +// +// __code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) { +// allocate->size = sizeof(struct Node); +// allocator(context); +// +// struct Node* root = tree->root; +// +// tree->root = &context->data[context->dataNum]->node; +// tree->current = root; +// +// compare(context, tree, tree->current->key, context->data[Node]->node.key); +// +// goto meta(context, Replace_d1); +// } +// +// __code delete1_stub(struct Context* context) { +// goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate); +// } +// +// __code delete2(struct Context* context, struct Node* current) { +// if (current->color == Black) { +// struct Node* child = current->right == NULL ? current->left : current->right; +// current->color = child == NULL ? Black : child->color; +// +// goto meta(context, DeleteCase1); +// } +// +// goto meta(context, Delete3); +// } +// +// __code delete2_stub(struct Context* context) { +// goto delete2(context, context->data[Tree]->tree.current); +// } +// +// __code delete3(struct Context* context, struct Tree* tree, struct Node* current) { +// struct Node* tmp = current->right == NULL ? current->left : current->right; +// +// if (current->parent) { +// if (current == current->parent->left) +// current->parent->left = tmp; +// else +// current->parent->right = tmp; +// } else { +// tree->root = tmp; +// } +// +// if (tmp) +// tmp->parent = current->parent; +// +// if (current->parent == NULL && tmp) +// tmp->color = Black; +// +// current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL); +// +// stack_pop(context->code_stack, &context->next); +// goto meta(context, context->next); +// } +// +// __code delete3_stub(struct Context* context) { +// goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); +// } +// +// __code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) { +// *newNode = *oldNode; +// +// if (result == EQ) +// goto meta(context, Replace_d2); +// else if (result == GT) +// tree->current = newNode->right; +// else +// tree->current = newNode->left; +// +// tree->current->parent = newNode; +// +// if (tree->current->left == NULL && tree->current->right == NULL) +// goto meta(context, Delete2); +// +// if (result == GT) +// newNode->right = context->heap; +// else if (result == LT) +// newNode->left = context->heap; +// +// allocator(context); +// +// compare(context, tree, tree->current->key, context->data[Node]->node.key); +// +// goto meta(context, Replace_d1); +// } +// +// __code replaceNodeForDelete1_stub(struct Context* context) { +// goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result); +// } +// +// __code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) { +// if (tree->current->left && tree->current->right) { +// newNode->left->parent = newNode; +// tree->current = newNode->left; +// newNode->left = context->heap; +// tree->deleted = newNode; +// +// allocator(context); +// tree->current->parent = newNode; +// +// goto meta(context, FindMax1); +// } +// +// goto meta(context, Delete2); +// } +// +// __code replaceNodeForDelete2_stub(struct Context* context) { +// goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node); +// } +// +// __code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { +// *newNode = *oldNode; +// +// if (newNode->right) +// goto meta(context, FindMax2); +// +// tree->deleted->key = newNode->key; +// tree->deleted->value = newNode->value; +// +// tree->current = newNode; +// +// goto meta(context, Delete2); +// } +// +// __code findMax1_stub(struct Context* context) { +// goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); +// } +// +// +// __code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { +// *newNode = *oldNode; +// +// if (newNode->right->right) { +// tree->current = newNode->right; +// newNode->right = context->heap; +// +// allocator(context); +// tree->current->parent = newNode; +// +// goto meta(context, FindMax2); +// } +// +// tree->deleted->key = newNode->right->key; +// tree->deleted->value = newNode->right->value; +// +// tree->current = newNode; +// +// goto meta(context, Delete2); +// } +// +// __code findMax2_stub(struct Context* context) { +// goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); +// } +// +// __code deleteCase1(struct Context* context, struct Node* current) { +// if (current->parent) +// goto meta(context, DeleteCase2); +// +// goto meta(context, Delete3); +// } +// +// __code deleteCase1_stub(struct Context* context) { +// goto deleteCase1(context, context->data[Tree]->tree.current); +// } +// +// __code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) { +// struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; +// +// if ((sibling == NULL ? Black : sibling->color) == Red) { +// current->parent->color = Red; +// sibling->color = Black; +// +// current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap); +// allocator(context); +// context->data[context->dataNum]->node = *sibling; +// +// tree->current = current->parent; +// +// context->next = DeleteCase3; +// stack_push(context->code_stack, &context->next); +// +// if (current == current->parent->left) +// goto meta(context, RotateL); +// else +// goto meta(context, RotateR); +// } +// +// goto meta(context, DeleteCase3); +// } +// +// __code deleteCase2_stub(struct Context* context) { +// goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); +// } +// +// __code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) { +// struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; +// +// if (current->parent->color == Black && +// (sibling == NULL ? Black : sibling->color) == Black && +// (sibling->left == NULL ? Black : sibling->left->color) == Black && +// (sibling->right == NULL ? Black : sibling->right->color) == Black) { +// sibling->color = Red; +// +// tree->current = current->parent; +// goto meta(context, DeleteCase1); +// } +// +// goto meta(context, DeleteCase4); +// } +// +// __code deleteCase3_stub(struct Context* context) { +// goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); +// } +// +// __code deleteCase4(struct Context* context, struct Node* current) { +// struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; +// +// if (current->parent->color == Red && +// (sibling == NULL ? Black : sibling->color) == Black && +// (sibling->left == NULL ? Black : sibling->left->color) == Black && +// (sibling->right == NULL ? Black : sibling->right->color) == Black) { +// sibling->color = Red; +// current->parent->color = Black; +// +// goto meta(context, Delete3); +// } +// +// goto meta(context, DeleteCase5); +// } +// +// __code deleteCase4_stub(struct Context* context) { +// goto deleteCase4(context, context->data[Tree]->tree.current); +// } +// +// __code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) { +// struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; +// sibling->parent = current->parent; +// +// if (current == current->parent->left && +// (sibling == NULL ? Black : sibling->color) == Black && +// (sibling->left == NULL ? Black : sibling->left->color) == Red && +// (sibling->right == NULL ? Black : sibling->right->color) == Black) { +// sibling->color = Red; +// sibling->left->color = Black; +// +// sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); +// allocator(context); +// struct Node* tmp = &context->data[context->dataNum]->node; +// *tmp = *sibling; +// tmp->parent = current; +// +// tmp->left = context->heap; +// allocator(context); +// context->data[context->dataNum]->node = *sibling->left; +// context->data[context->dataNum]->node.parent = tmp; +// +// tree->current = tmp; +// +// context->next = DeleteCase6; +// stack_push(context->code_stack, &context->next); +// +// goto meta(context, RotateR); +// } else if (current == current->parent->right && +// (sibling == NULL ? Black : sibling->color) == Black && +// (sibling->left == NULL ? Black : sibling->left->color) == Black && +// (sibling->right == NULL ? Black : sibling->right->color) == Red) { +// sibling->color = Red; +// sibling->right->color = Black; +// +// sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); +// allocator(context); +// struct Node* tmp = &context->data[context->dataNum]->node; +// *tmp = *sibling; +// tmp->parent = current; +// +// tmp->right = context->heap; +// allocator(context); +// context->data[context->dataNum]->node = *sibling->right; +// context->data[context->dataNum]->node.parent = tmp; +// +// tree->current = tmp; +// +// context->next = DeleteCase6; +// stack_push(context->code_stack, &context->next); +// goto meta(context, RotateL); +// } +// +// goto meta(context, DeleteCase6); +// } +// +// __code deleteCase5_stub(struct Context* context) { +// goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); +// } +// +// __code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) { +// struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; +// +// sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); +// allocator(context); +// struct Node* tmp = &context->data[context->dataNum]->node; +// *tmp = *sibling; +// tmp->parent = current; +// +// tmp->color = current->parent->color; +// current->parent->color = Black; +// +// context->next = Delete3; +// stack_push(context->code_stack, &context->next); +// +// if (current == current->parent->left) { +// tmp->right->color = Black; +// tree->current = current->parent; +// +// goto meta(context, RotateL); +// } else { +// tmp->left->color = Black; +// tree->current = current->parent; +// +// goto meta(context, RotateR); +// } +// } +// +// __code deleteCase6_stub(struct Context* context) { +// goto deleteCase6(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); +// }
--- a/src/parallel_execution/test/rbTree_test.cbc Mon Dec 25 18:10:56 2017 +0900 +++ b/src/parallel_execution/test/rbTree_test.cbc Wed Dec 27 18:26:37 2017 +0900 @@ -1,13 +1,16 @@ +#include <stdio.h> #include "../../context.h" #interface "Tree.h" + /* #include <assert.h> */ __code rbTreeTest1(struct Tree* tree) { printf("Test1\n"); Node* node = new Node(); - node->value = 3; + node->value = (union Data*)new Int(); + node->value->Int = 3; node->key = 3; - printf("value->%d,key->%d\n",node->value,node->key); + printf("value->%d,key->%d\n",node->value->Int,node->key); goto tree->put(node, rbTreeTest2); } @@ -21,7 +24,8 @@ __code rbTreeTest2(struct Tree* tree) { printf("Test2\n"); Node* node = new Node(); - node->value = 4; + node->value = (union Data*)new Int(); + node->value->Int = 4; node->key = 4; goto tree->put(node, rbTreeTest3); } @@ -36,29 +40,44 @@ __code rbTreeTest3(struct Tree* tree) { printf("test3\n"); Node* node = new Node(); - node->value = 2; + node->value = (union Data*)new Int(); + node->value->Int = 2; node->key = 2; goto tree->put(node, rbTreeTest4); } +__code rbTreeTest3_stub(struct Context* context) { + Tree* tree = (struct Tree*)Gearef(context, Tree)->tree; + goto rbTreeTest3(context,tree); +} __code rbTreeTest4(struct Tree* tree) { printf("test4\n"); Node* node = new Node(); - node->value = 8; + node->value = (union Data*)new Int(); + node->value->Int = 8; node->key = 8; goto tree->put(node, rbTreeTest5); } +__code rbTreeTest4_stub(struct Context* context) { + Tree* tree = (struct Tree*)Gearef(context, Tree)->tree; + goto rbTreeTest4(context,tree); +} __code rbTreeTest5(struct Tree* tree) { printf("test5\n"); Node* node = new Node(); - node->value = 7; + node->value = (union Data*)new Int(); + node->value->Int = 7; node->key = 7; goto exit_code(context); } +__code rbTreeTest5_stub(struct Context* context) { + Tree* tree = (struct Tree*)Gearef(context, Tree)->tree; + goto rbTreeTest5(context,tree); +}