Mercurial > hg > Members > Moririn
changeset 454:77de0283ac92
Debug RedBlackTree.cbc.
author | ryokka |
---|---|
date | Mon, 11 Dec 2017 20:01:05 +0900 |
parents | 40ea6277b91c |
children | a44dbeb08895 |
files | src/parallel_execution/RedBlackTree.cbc src/parallel_execution/SingleLinkedStack.cbc src/parallel_execution/Tree.cbc src/parallel_execution/context.h src/parallel_execution/generate_stub.pl src/parallel_execution/test/rbTree_test.cbc |
diffstat | 6 files changed, 91 insertions(+), 98 deletions(-) [+] |
line wrap: on
line diff
--- a/src/parallel_execution/RedBlackTree.cbc Fri Dec 08 15:32:14 2017 +0900 +++ b/src/parallel_execution/RedBlackTree.cbc Mon Dec 11 20:01:05 2017 +0900 @@ -5,25 +5,11 @@ 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* 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); @@ -34,45 +20,38 @@ return tree; } -// printTree use printNode -void printNode(struct RedBlackTree* tree) { - struct Node* node = tree->current; +void printNode(struct Node* node) { if (node == NULL) { - printf("Leaf"); + printf("leaf"); } else { - printf("key = %d (", node->key); + printf("((%d,%d (",node->color, node->key); printNode(node->right); - printf("), ("); + printf(") ("); printNode(node->left); printf(")"); } } void printTree(struct RedBlackTree* tree) { - printNode(tree); printf("\n"); -} - -__code printRBTree(struct RedBlackTree* tree){ - printTree(tree); - goto meta(context, C_exit_code); + tree->current = tree->root; + printNode(tree->current); + printf(")\n"); } __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; + printf("C_putRedBlackTree\n"); + //struct Node* newNode = &ALLOCATE(context, Node)->Node; + printf("value->%d,key->%d \n",node->value,node->key); + tree->previous = tree->newNode; + tree->newNode = node; tree->newNode->color = Red; // tree->root = newNode; // this should done at stackClear // tree->parent = NULL; // if (root) { tree->current = tree->root; // tree->result = compare(tree->current, node); - goto insertRBTree(insertNode, tree); + goto insertRBTree(node, tree); // } // printf("error : __code putRedBlackTree \n"); // goto meta(context, C_exit_code); @@ -95,44 +74,49 @@ // goto next(...); // } -__code insertRBTree(struct Node* node, struct RedBlackTree* tree) { - printf("insertRBTree\n"); +__code insertRBTree(struct Node* node, struct RedBlackTree* tree, struct Stack* stack, __code next(...)) { + // first case tree->current = root; + printf("C_insertRBTree\n"); + stack = tree->nodeStack; printf("value->%d,key->%d\n",node->value,node->key); - // tree->current = node; - // struct Stack* stack = tree->nodeStack; + printf("newNode value->%d,newNode key->%d\n",tree->newNode->value,tree->newNode->key); - if (tree->root == NULL){ - tree->root = tree->current; + if (tree->root == NULL) { + printf("insertRBTree_root eq NULL\n"); + tree->root = tree->newNode; tree->root->color = Black; - goto meta(context, C_printRBTree); + printf("tree->root->key = %d, tree->root->color = %d \n",tree->root->key,tree->root->color); + printTree(tree); + goto next(tree,...); } else { - goto searchInsertLocation(newNode, nodeStack, tree); + goto searchInsertLocation(node, tree, stack); } } -__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" - +__code searchInsertLocation(struct Node* node, struct RedBlackTree* tree, struct Stack* stack) { + // first case tree->current = root; PreCase remove root=NULL case.don't exist firstCase tree->current=NULL + printf("C_searchInsertLocation\n"); + printf("nownode->key %d , previous->key %d \n",tree->newNode->key,tree->previous->key); - if (tree->current == NULL){ - // before CS(insertRBTree) remeve "root eq NULL Case" + tree->result = compare(tree->current, node); + printf("tree->current->key = %d, node->key %d\n",tree->current->key,node->key); + printf("compare (%d,%d)\n",tree->current,node); + if (tree->current == NULL) { + printf("goto insertLocationBackInsert stack->pop"); goto stack->pop(insertLocationBackInsert); - } else if (tree->result == GT) { + } + + if (tree->result == GT) { + printf("GT searchInsertLocation"); tree->current = tree->current->right; - goto stack->push(trace, searchInsertLocation); - } else if (tree->result == LT){ + goto stack->push(tree->newNode,insertLocationBackInsert); + } else if (tree->result == LT) { + printf("LT searchInsertLocation"); tree->current = tree->current->left; - goto stack->push(trace, searchInsertLocation); + goto stack->push(tree->newNode, searchInsertLocation); } else if (tree->result == EQ) { - printf("alady member this node : __code searchInsertLocation()\n"); + printf("already member this node : __code searchInsertLocation()\n"); goto meta(context, C_exit_code); } else { printf("$insert value tree : __code searchInsertLocation() \n"); @@ -140,18 +124,22 @@ } } -__code insertLocationBackInsert(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node) { - printf("insertLocationBackInsert\n"); - struct Node* traceNode = tree->nodeStack->data; - tree->current = traceNode; +__code insertLocationBackInsert(struct RedBlackTree* tree, struct Node* node, struct Stack* stack) { + printf("C_insertLocationBackInsert\n"); + struct Node* hoge = stack->data; + printf("stackpopdata%d\n",stack->data); + tree->current = tree->previous; // tree->current = nodeStack->data; // this CS is ones only backTrace, and insert node - tree->result = compare(tree->current, tree->newNode); - + tree->result = compare(tree->previous,tree->newNode); + printf("back,compare\n"); if (tree->result == GT) { + printf("ok\n"); tree->current->right = tree->newNode; + printTree(tree); goto insertBalance(); } else if (tree->result == LT) { + printf("LT\n"); tree->current->left = tree->newNode; goto insertBalance(); } else { @@ -160,8 +148,8 @@ } } -__code insertBalance(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node){ - printf("insertBalance\n"); +__code insertBalance(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node, __code next(...)) { + printf("C_insertBalance\n"); struct Node* traceNode = tree->nodeStack->data; tree->current = traceNode; struct Stack* stack = tree->nodeStack; @@ -169,9 +157,9 @@ // exit insertion code if (tree->current == tree->root) { tree->current->color = Black; - printTree((union Data*)(tree->root)); + printTree(tree); //printTree - goto meta(context, C_exit_code); + goto next(tree,...); } @@ -180,20 +168,20 @@ goto stack->pop(insertBalance); // current color eq Black - if (tree->current->left->left || tree->current->left->right){ + if (tree->current->left->left || tree->current->left->right) { goto insertBalanceLeft(tree,nodeStack); - } else if (tree->current->right->left || tree->current->right->right){ + } else if (tree->current->right->left || tree->current->right->right) { goto insertBalanceRight(tree,nodeStack); } else { goto stack->pop(insertBalance); } } -__code insertBalanceLeft(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node){ - printf("insertBalanceLeft\n"); +__code insertBalanceLeft(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node) { + printf("C_insertBalanceLeft\n"); struct Stack* stack = tree->nodeStack; - if (tree->current->color == Black && tree->current->left->color == Red && tree->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; @@ -207,7 +195,7 @@ tree->current->right->color = Black; goto stack->pop(insertBalance); - } else if(tree->current->color == Black && tree->current->left->color == Red && tree->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; @@ -224,11 +212,11 @@ } } -__code insertBalanceRight(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node){ - printf("insertBalanceLeft\n"); +__code insertBalanceRight(struct RedBlackTree* tree, struct Node* nodeStack, struct Node* node) { + printf("C_insertBalanceLeft\n"); struct Stack* stack = tree->nodeStack; - if (tree->current->color == Black && tree->current->right->color == Red && tree->current->right->right->color == Red){ + 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; @@ -242,7 +230,7 @@ tree->current->right->color = Black; goto stack->pop(insertBalance); - } else if (tree->current->color == Black && tree->current->right->color == Red && tree->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;
--- a/src/parallel_execution/SingleLinkedStack.cbc Fri Dec 08 15:32:14 2017 +0900 +++ b/src/parallel_execution/SingleLinkedStack.cbc Mon Dec 11 20:01:05 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/Tree.cbc Fri Dec 08 15:32:14 2017 +0900 +++ b/src/parallel_execution/Tree.cbc Mon Dec 11 20:01:05 2017 +0900 @@ -1,6 +1,9 @@ typedef struct Tree<Type, Impl>{ - Type* tree; - Type* node; + /* future Code */ + /* Type* tree; */ + /* Type* node; */ + union Data* tree; + struct Node* node; __code put(Impl* tree,Type* node, __code next(...)); // __code get(Impl* tree, __code next(...)); // __code removeRedBlackTree();
--- a/src/parallel_execution/context.h Fri Dec 08 15:32:14 2017 +0900 +++ b/src/parallel_execution/context.h Mon Dec 11 20:01:05 2017 +0900 @@ -281,7 +281,6 @@ struct Node* parent; struct Node* grandparent; struct Stack* nodeStack; - enum Code* put; int result; } RedBlackTree; struct RotateTree { @@ -298,6 +297,7 @@ enum Color { Red, Black, + // Red eq 0,Black eq 1. enum name convert intager. } color; } Node; struct Atomic {
--- a/src/parallel_execution/generate_stub.pl Fri Dec 08 15:32:14 2017 +0900 +++ b/src/parallel_execution/generate_stub.pl Mon Dec 11 20:01:05 2017 +0900 @@ -285,9 +285,9 @@ while (<$in>) { if (! $inTypedef && ! $inStub && ! $inMain) { - if (/^typedef struct (\w+) {/) { + if (/^typedef struct (\w+) \{/) { $inTypedef = 1; - } elsif (/^int main\((.*)\) {/) { + } elsif (/^int main\((.*)\) \{/) { $inMain = 1; } elsif (/^\_\_code (\w+)\((.*)\)(.*)/) { %localVarType = {};
--- a/src/parallel_execution/test/rbTree_test.cbc Fri Dec 08 15:32:14 2017 +0900 +++ b/src/parallel_execution/test/rbTree_test.cbc Mon Dec 11 20:01:05 2017 +0900 @@ -1,8 +1,8 @@ #include "../../context.h" -#include <assert.h> +/* #include <assert.h> */ __code rbTreeTest1(struct Tree* tree) { - printf("insert1\n"); + printf("Test1\n"); Node* node = new Node(); node->value = 3; node->key = 3; @@ -11,24 +11,29 @@ } __code rbTreeTest1_stub(struct Context* context) { - printf("insert1_stub\n"); + printf("test1_stub\n"); Tree* tree = createRedBlackTree(context); goto rbTreeTest1(context,tree); } __code rbTreeTest2(struct Tree* tree) { - printf("insert2\n"); + printf("Test2\n"); Node* node = new Node(); node->value = 4; node->key = 4; goto tree->put(node, rbTreeTest3); } +__code rbTreeTest2_stub(struct Context* context) { + printf("test2_stub\n"); + Tree* tree = (struct Tree*)Gearef(context, Tree)->tree; + goto rbTreeTest2(context,tree); +} __code rbTreeTest3(struct Tree* tree) { - printf("insert3\n"); + printf("test3\n"); Node* node = new Node(); node->value = 2; node->key = 2; @@ -37,7 +42,7 @@ __code rbTreeTest4(struct Tree* tree) { - printf("insert4\n"); + printf("test4\n"); Node* node = new Node(); node->value = 8; node->key = 8; @@ -46,20 +51,17 @@ __code rbTreeTest5(struct Tree* tree) { - printf("insert5\n"); + printf("test5\n"); Node* node = new Node(); node->value = 7; node->key = 7; - goto tree->put(node, assert1); + goto exit_code(context); } -__code assert1(struct RedBlackTree* tree) { - printf("assert\n"); - assert(tree->root->color == Black); - goto exit_code(0); -} + int main(int argc, char const* argv[]) { + printf("test_main\n"); goto rbTreeTest1(); }