Mercurial > hg > GearsTemplate
changeset 452:1432d924c472
fix RedBlackTree.cbc Insert, debug now
author | ryokka |
---|---|
date | Fri, 08 Dec 2017 15:28:06 +0900 |
parents | dcc42f3e7e97 |
children | 40ea6277b91c |
files | src/parallel_execution/CMakeLists.txt src/parallel_execution/RedBlackTree.cbc src/parallel_execution/SingleLinkedStack.cbc src/parallel_execution/Stack.cbc src/parallel_execution/Tree.cbc src/parallel_execution/context.h |
diffstat | 6 files changed, 140 insertions(+), 145 deletions(-) [+] |
line wrap: on
line diff
--- a/src/parallel_execution/CMakeLists.txt Tue Dec 05 06:33:40 2017 +0900 +++ b/src/parallel_execution/CMakeLists.txt Fri Dec 08 15:28:06 2017 +0900 @@ -128,5 +128,5 @@ TARGET rbtree SOURCES - RedBlackTree.cbc + SingleLinkedQueue.cbc test/rbTree_test.cbc RedBlackTree.cbc SingleLinkedStack.cbc )
--- a/src/parallel_execution/RedBlackTree.cbc Tue Dec 05 06:33:40 2017 +0900 +++ b/src/parallel_execution/RedBlackTree.cbc Fri Dec 08 15:28:06 2017 +0900 @@ -1,58 +1,81 @@ #include <stdio.h> #include "../context.h" - -// extern enum Relational compare(struct Node* node1, struct Node* node2); +#include "../compare.c" extern enum Relational compare(struct Node* node1, struct Node* node2); +/* Tree* createRedBlackTree(struct Context* context) */ +/* struct Tree* tree = new Tree(); */ +/* struct RedBlackTree* redBlackTree = new RedBlackTree(); */ +/* tree->tree = (union Data*)redBlackTree; */ +/* redBlackTree->root = NULL; */ +/* redBlackTree->nodeStack = (union Data*)createSingleLinkedStack(context); */ + +/* tree->put = C_putRedBlackTree; */ +/* // tree->get = C_getRedBlackTree; */ +/* // tree->remove = C_removeRedBlackTree; */ +/* // tree->clear = C_clearRedBlackTree; */ +/* return tree; */ Tree* createRedBlackTree(struct Context* context) { struct Tree* tree = new Tree(); - struct RedBlackTree* redBlackTree = new RedBlackTree(); - tree->tree = (union Data*)redBlackTree; - redBlackTree->root = NULL; - redBlackTree->nodeStack = (union Data*)createSingleLinkedStack(context); + struct RedBlackTree* rbtree = new RedBlackTree(); + // struct RedBlackTree* tree = new RedBlackTree(); + // struct RedBlackTree* tree = RedBlackTree(context); + tree->tree = (union Data*)rbtree; + rbtree->root = NULL; + rbtree->nodeStack = (union Data*)createSingleLinkedStack(context); tree->put = C_putRedBlackTree; // tree->get = C_getRedBlackTree; // tree->remove = C_removeRedBlackTree; // tree->clear = C_clearRedBlackTree; - return tree; + return tree; } -__code printTree(struct RedBlackTree* tree) { - printTree1(tree); - printf("\n"); -} - -__code printTree1(struct RedBlackTree* tree) { +// printTree use printNode +void printNode(struct RedBlackTree* tree) { struct Node* node = tree->current; if (node == NULL) { printf("Leaf"); } else { printf("key = %d (", node->key); - printTree1(node->right); + printNode(node->right); printf("), ("); - printTree1(node->left); + printNode(node->left); printf(")"); } } -__code putRedBlackTree(struct Node* node, struct RedBlackTree* tree) { - struct Node* newNode = &ALLOCATE(context, Node)->Node; - struct Node* root = tree->root; - printTree((tree->root)); - tree->newNode = newNode; +void printTree(struct RedBlackTree* tree) { + printNode(tree); + printf("\n"); +} + +__code printRBTree(struct RedBlackTree* tree){ + printTree(tree); + goto meta(context, C_exit_code); +} + +__code putRedBlackTree(struct RedBlackTree* tree, struct Node* node, __code next(...)) { + printf("putRedBlackTree\n"); + //struct Node* newNode = &ALLOCATE(context, Node)->Node; + struct Node* insertNode = node; + printf("value->%d,key->%d \n",node->value,node->key); + // struct Node* root = tree->root; + // printTree(tree); + tree->newNode = insertNode; + tree->newNode->color = Red; // tree->root = newNode; // this should done at stackClear - tree->parent = NULL; - if (root) { - tree->current = root; + // tree->parent = NULL; + // if (root) { + tree->current = tree->root; // tree->result = compare(tree->current, node); - goto insertRBTree(newNode, tree); - } - print("error : __code putRedBlackTree"); - goto next(...); + goto insertRBTree(insertNode, tree); + // } + // printf("error : __code putRedBlackTree \n"); + // goto meta(context, C_exit_code); } //__code stackClear(struct RedBlackTree* tree, struct Stack* nodeStack, __code next(...)) { @@ -73,69 +96,104 @@ // } __code insertRBTree(struct Node* node, struct RedBlackTree* tree) { - tree->current = node; - struct Stack* nodeStack = tree->nodeStack; + printf("insertRBTree\n"); + printf("value->%d,key->%d\n",node->value,node->key); + // tree->current = node; + // struct Stack* stack = tree->nodeStack; - if (tree->root == null){ + if (tree->root == NULL){ tree->root = tree->current; tree->root->color = Black; - goto next(...); - }else{ - goto searchInsertLocatetion(newNode, nodeStack, tree); + goto meta(context, C_printRBTree); + } else { + goto searchInsertLocation(newNode, nodeStack, tree); } - } -__code searchInsertLocation(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* tree) { - struct Stack* nodeStack = tree->nodeStack; +__code searchInsertLocation(struct Node* node, struct RedBlackTree* tree) { + printf("searchInsertLocation\n"); struct Node* trace = tree->current; + struct Stack* stack = tree->nodeStack; + tree->result = compare(tree->current, tree->newNode); // i think faster "compare tree->current, node" than "switch case EQ, LT, RT" - if (tree->current > node || tree->current < node) { - goto nodestack->push(nodeStack,trace, searchInsertLocation); - } else if (tree->current == node) { - printf("alady member this node : __code searchInsertLocation()"); - goto next(...); - } else if (tree->current == null){ - tree->current = node; - goto nodeStack->pop(nodeStack,insertBalance); - }else{ - printf("$insert value tree : __code searchInsertLocation()"); - goto next(...); + + + if (tree->current == NULL){ + // before CS(insertRBTree) remeve "root eq NULL Case" + goto stack->pop(insertLocationBackInsert); + } else if (tree->result == GT) { + tree->current = tree->current->right; + goto stack->push(trace, searchInsertLocation); + } else if (tree->result == LT){ + tree->current = tree->current->left; + goto stack->push(trace, searchInsertLocation); + } else if (tree->result == EQ) { + printf("alady member this node : __code searchInsertLocation()\n"); + goto meta(context, C_exit_code); + } else { + printf("$insert value tree : __code searchInsertLocation() \n"); + goto meta(context, C_exit_code); + } +} + +__code insertLocationBackInsert(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node) { + printf("insertLocationBackInsert\n"); + struct Node* traceNode = tree->nodeStack->data; + tree->current = traceNode; + // tree->current = nodeStack->data; + // this CS is ones only backTrace, and insert node + tree->result = compare(tree->current, tree->newNode); + + if (tree->result == GT) { + tree->current->right = tree->newNode; + goto insertBalance(); + } else if (tree->result == LT) { + tree->current->left = tree->newNode; + goto insertBalance(); + } else { + printf("error : __code insertLocationBackTrace() \n"); + goto meta(context, C_exit_code); } } __code insertBalance(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node){ - tree->current = nodeStack->data; + printf("insertBalance\n"); + struct Node* traceNode = tree->nodeStack->data; + tree->current = traceNode; + struct Stack* stack = tree->nodeStack; // exit insertion code if (tree->current == tree->root) { tree->current->color = Black; - printTree(((union Data* ) (tree->root))); + printTree((union Data*)(tree->root)); //printTree - goto next(...); + goto meta(context, C_exit_code); } + //current color eq Red - if (current->color == Red) - goto nodeStack->pop(nodeStack, trace, insertBalance); + if (tree->current->color == Red) + goto stack->pop(insertBalance); // current color eq Black - if (current->left->left || current->left->right){ + if (tree->current->left->left || tree->current->left->right){ goto insertBalanceLeft(tree,nodeStack); - }else if (current->right->left || current->right->right){ + } else if (tree->current->right->left || tree->current->right->right){ goto insertBalanceRight(tree,nodeStack); - }else{ - goto nodeStack->pop(nodeStack,insertBalance); + } else { + goto stack->pop(insertBalance); } } __code insertBalanceLeft(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node){ + printf("insertBalanceLeft\n"); + struct Stack* stack = tree->nodeStack; - if (current->color == Black && current->left->color == Red && current->left->left->color == Red){ + if (tree->current->color == Black && tree->current->left->color == Red && tree->current->left->left->color == Red){ struct Node* tmpCurrent = tree->current; struct Node* tmpLeft = tree->current->left; struct Node* tmpLeftLeft = tree->current->left->left; @@ -147,9 +205,9 @@ tree->current->color = Red; tree->current->left->color = Black; tree->current->right->color = Black; - goto nodeStack->pop(nodeStack,insertBalance); + goto stack->pop(insertBalance); - } else if(current->color == Black && current->left->color == Red && current->left->right->color == Red){ + } else if(tree->current->color == Black && tree->current->left->color == Red && tree->current->left->right->color == Red){ struct Node* tmpCurrent = tree->current; struct Node* tmpLeft = tree->current->left; struct Node* tmpLeftRight = tree->current->left->right; @@ -161,27 +219,30 @@ tree->current->color = Red; tree->current->left->color = Black; tree->current->right->color = Black; - goto nodeStack->pop(nodeStack,insertBalance); + goto stack->pop(insertBalance); } } __code insertBalanceRight(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node){ - if (current->color == Black && current->right->color == Red && current->right->right->color == Red){ + printf("insertBalanceLeft\n"); + struct Stack* stack = tree->nodeStack; + + if (tree->current->color == Black && tree->current->right->color == Red && tree->current->right->right->color == Red){ struct Node* tmpCurrent = tree->current; struct Node* tmpRight = tree->current->right; struct Node* tmpRightRight = tree->current->right->right; tree->current = tmpRight; tree->current->left = tmpCurrent; - tree->current->Right = tmpRightRight; + tree->current->right = tmpRightRight; tree->current->left->right = tmpRight->left; tree->current->color = Red; tree->current->left->color = Black; tree->current->right->color = Black; - goto nodeStack->pop(nodeStack,insertBalance); + goto stack->pop(insertBalance); - } else if (current->color == Black && current->right->color == Red && current->right->left->color == Red){ + } else if (tree->current->color == Black && tree->current->right->color == Red && tree->current->right->left->color == Red){ struct Node* tmpCurrent = tree->current; struct Node* tmpRight = tree->current->right; @@ -194,81 +255,11 @@ tree->current->color = Red; tree->current->left->color = Black; tree->current->right->color = Black; - goto nodeStack->pop(nodeStack,insertBalance); + goto stack->pop(insertBalance); } else { - printf("unkwon error : __code insertBalanceRight()"); - goto next(...); + printf("unkwon error : __code insertBalanceRight() \n"); + goto meta(context, C_exit_code); } } - -// insertion code end - - - - -/* __code deleteRBTree(struct RedBlackTree newNode, struct RedBlackTree* tree) { */ -/* tree->current = tree->root; */ -/* goto deleteLocate; */ -/* } */ - -/* __code deleteLocate(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* tree) { */ -/* /\* check delete node locate and push route node *\/ */ -/* struct Stack* nodeStack = tree->nodeStack; */ -/* struct Node* trace = tree->current; */ - -/* if (tree->current > node) { */ -/* goto nodeStack->push(nodeStack,trace,deleteLocate); */ -/* } else if (tree->current < node) { */ -/* goto nodeStack->push(trace,deleteLocate); */ -/* } else if (tree->current == node) { */ -/* // trace = tree->current; */ -/* goto deleteNode(struct Stack* nodeStack, struct RedBlackTree* tree,struct Node* trace); */ -/* // goto nodeStack->push(trace,deleteNode); */ -/* } else if (tree->current == null){ */ -/* printf("No member Delete node (__code deleteLocate)"); */ -/* goto next(...); */ -/* } else { */ -/* printf("Error,__code deleteLocate"); */ -/* goto next(...); */ -/* } */ -/* } */ - -/* __code deleteNode(struct Node* node, struct Stack* nodeStack, struct RedBlackTree* tree) { */ -/* struct Stack* nodeStack = tree->nodeStack; */ -/* struct Node* replaceNode = nodeStack->data; */ - -/* if(replaceNode->right == null){ */ -/* tree->current = replaceNode; */ -/* tree->current = tree->current->left; */ -/* goto deleteUnbalance(nodeStack,replaceNode); */ -/* }else if(replaceNode->left == null){ */ -/* tree->current = replaceNode; */ -/* tree->current = tree->current->right; */ -/* goto deleteUnbalance(nodeStack,replaceNode); */ -/* //goto deleteNodeReplaceNull(); */ -/* }else{ */ -/* // goto nodeStack->push(nodeStack,replaceNode,deleteNodeReplace); */ -/* goto deleteNodeReplace(nodeStack,replaceNode); */ -/* } */ -/* } */ - - -/* __code deleteNodeReplace(){ */ - -/* if (replaceNode->left != null){ */ -/* replaceNode = replaceNode->left; */ -/* goto deleteNodeReplace(); */ -/* }else if(){ */ - - -/* } */ - -/* } */ - - -/* __code deleteUnbalance() { */ -/* if () { */ -/* } */ -/* } */ - +// insertCode end
--- a/src/parallel_execution/SingleLinkedStack.cbc Tue Dec 05 06:33:40 2017 +0900 +++ b/src/parallel_execution/SingleLinkedStack.cbc Fri Dec 08 15:28:06 2017 +0900 @@ -97,7 +97,7 @@ } goto next(data, data1, ...); } - + __code isEmptySingleLinkedStack(struct SingleLinkedStack* stack, __code next(...), __code whenEmpty(...)) { if (stack->top) goto next(...);
--- a/src/parallel_execution/Stack.cbc Tue Dec 05 06:33:40 2017 +0900 +++ b/src/parallel_execution/Stack.cbc Fri Dec 08 15:28:06 2017 +0900 @@ -1,7 +1,10 @@ typedef struct Stack<Type, Impl>{ - Type* stack; - Type* data; - Type* data1; + union Data* stack; + union Data* data; + union Data* data1; + /* Type* stack; */ + /* Type* data; */ + /* Type* data1; */ __code whenEmpty(...); __code clear(Impl* stack,__code next(...)); __code push(Impl* stack,Type* data, __code next(...));
--- a/src/parallel_execution/Tree.cbc Tue Dec 05 06:33:40 2017 +0900 +++ b/src/parallel_execution/Tree.cbc Fri Dec 08 15:28:06 2017 +0900 @@ -1,8 +1,8 @@ typedef struct Tree<Type, Impl>{ Type* tree; Type* node; - __code put(Impl* tree, Type* node, Type* root, Type* newNode); - __code get(Impl* tree, __code next(...)); + __code put(Impl* tree,Type* node, __code next(...)); + // __code get(Impl* tree, __code next(...)); // __code removeRedBlackTree(); // __code clearRedBlackTree(); __code next(...);