Mercurial > hg > Gears > Gears
changeset 1056:b76db8c133b8
refactor
author | matac42 <matac@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Fri, 26 Jan 2024 17:03:15 +0900 |
parents | 81439e83c4d2 |
children | 71d4c7326f26 |
files | src/parallel_execution/RedBlackTree.cbc |
diffstat | 1 files changed, 41 insertions(+), 59 deletions(-) [+] |
line wrap: on
line diff
--- a/src/parallel_execution/RedBlackTree.cbc Fri Jan 26 15:45:56 2024 +0900 +++ b/src/parallel_execution/RedBlackTree.cbc Fri Jan 26 17:03:15 2024 +0900 @@ -93,6 +93,8 @@ } __code copyRedBlackTree(struct RedBlackTree* tree) { + printf("copyRedBlackTree\n"); + tree->current = tree->root; tree->copied = 0; @@ -113,14 +115,15 @@ // __code leftDown(struct RedBlackTree* tree) { + printf("leftDown\n"); struct Stack* inputStack = tree->inputStack; - printf("leftDown\n"); - goto inputStack->get(leftDown1); } __code leftDown1(struct RedBlackTree* tree, struct Stack* stack) { + printf("leftDown1\n"); + if (tree->current->left == NULL) { goto rightDown(); } @@ -137,72 +140,71 @@ data->left = newNode; } - printf("leftDown1\n"); - // 新規leftノードをpushしている goto inputStack->push(newNode, leftDown2); } // 実際にDownする __code leftDown2(struct RedBlackTree* tree) { + printf("leftDown2\n"); struct Stack* nodeStack = tree->nodeStack; struct Node* oldNode = tree->current; + tree->current = tree->current->left; - printf("leftDown2\n"); goto nodeStack->push((union Data*)oldNode, leftDown3); } __code leftDown3(struct RedBlackTree* tree) { + printf("leftDown3\n"); struct Stack* nodeStack = tree->nodeStack; - printf("leftDown3\n"); + if (tree->current) { goto leftDown(tree); } else if (tree->current == NULL) { - // ここでinputStackをpopする必要はない - // currentの付け替えをして goto nodeStack->pop(leftDown4); - } else if (tree->current->left) { - // 謎の処理 - printf("nazo\n"); - goto rightDown(tree, inputStack); } } __code leftDown4(struct RedBlackTree* tree, struct Stack* stack) { + printf("leftDown4\n"); struct Node* data = (Node*)(stack->data); + tree->current = data; - printf("leftDown4\n"); goto up(); } __code rightDown(struct RedBlackTree* tree) { + printf("rightDown\n"); struct Stack* nodeStack = tree->nodeStack; - printf("rightDown\n"); + goto nodeStack->isEmpty(rightDownWhenNoEmpty, rightDownWhenEmpty); } __code rightDownWhenNoEmpty(struct RedBlackTree* tree) { + printf("rightDownWhenNoEmpty\n"); struct Stack* inputStack = tree->inputStack; - printf("rightDownWhenNoEmpty\n"); - goto inputStack->get(rightDown1); -} -__code rightDownWhenEmpty(struct RedBlackTree* tree) { - struct Stack* inputStack = tree->inputStack; - printf("rightDownWhenEmpty\n"); - tree->copied = 1; + goto inputStack->get(rightDown1); } -// inputStackに2をpushしてなくない? +__code rightDownWhenEmpty(struct RedBlackTree* tree) { + printf("rightDownWhenEmpty\n"); + struct Stack* inputStack = tree->inputStack; + + tree->copied = 1; + + goto inputStack->get(rightDown1); +} + __code rightDown1(struct RedBlackTree* tree, struct Stack* stack) { printf("rightDown1\n"); + if (tree->current->right == NULL) { - // ここでupする時にrightから来たかleftから来たかを知る必要がある - // rightから来た場合でnodeStackが空ならば木の入れ替えへ goto up(); } + struct Stack* inputStack = tree->inputStack; struct Node* newNode = &ALLOCATE(context, Node)->Node; struct Node* data = (Node*)(stack->data); @@ -215,32 +217,27 @@ data->right = newNode; } - // 新規ノードをpushしている goto inputStack->push(newNode, rightDown2); } // 実際にDownする __code rightDown2(struct RedBlackTree* tree) { + printf("rightDown2\n"); struct Stack* nodeStack = tree->nodeStack; struct Node* oldNode = tree->current; + tree->current = tree->current->right; - printf("rightDown2\n"); goto nodeStack->push((union Data*)oldNode, rightDown3); } __code rightDown3(struct RedBlackTree* tree) { + printf("rightDown3\n"); struct Stack* inputStack = tree->inputStack; - printf("rightDown3\n"); if (tree->current) { goto leftDown(tree, inputStack); - } else if (tree->current == NULL) { - // currentの付け替えは? + } else { goto inputStack->pop2(rightDown); - } else if (tree->current->left) { - // 謎の処理 - printf("nazo\n"); - goto rightDown(tree, inputStack); } } @@ -250,26 +247,19 @@ // nodeStackが空だったらtreeの入れ替えへ // __code up(struct RedBlackTree* tree) { + printf("up\n"); struct Stack* nodeStack = tree->nodeStack; - printf("up\n"); - goto nodeStack->pop(up1); } __code up1(struct RedBlackTree* tree, struct Stack* stack) { + printf("up1\n"); struct Stack* inputStack = tree->inputStack; struct Node* data = (Node*)(stack->data); + tree->current = data; - // if (tree->current == NULL) { - // 木の入れ替え - // copyの終了 - // printf("copy finished!\n"); - // } - - printf("up1\n"); - goto inputStack->pop(up2); } @@ -279,15 +269,14 @@ struct Stack* inputStack = tree->inputStack; if (tree->current->right) { - // ここでrootからDownする場合を考える goto up0(tree); } else { goto inputStack->pop(up); } } -// Gearefがうまく挿入されないため、一度別CGに遷移している __code up0(struct RedBlackTree* tree) { + printf("up0\n"); struct Stack* nodeStack = tree->nodeStack; goto nodeStack->isEmpty(rightDown, swap); @@ -296,44 +285,37 @@ __code up3(struct Node* node, struct RedBlackTree* tree, struct Stack* inputStack) { printf("up3\n"); tree->current->right = node->right; + goto up(tree, inputStack); } -// copiedであればtreeの入れ替え __code swap(struct RedBlackTree* tree) { printf("swap\n"); if (tree->copied) { - goto swap0(tree); + goto swap1(tree); } goto rightDown(tree); } -__code swap0(struct RedBlackTree* tree) { +__code swap1(struct RedBlackTree* tree) { + printf("swap1\n"); struct Stack* inputStack = tree->inputStack; - goto inputStack->pop(swap1); + goto inputStack->pop(swap2); } -__code swap1(struct RedBlackTree* tree, struct Stack* stack, __code next(...)) { - // このキャストがうまくいってない +__code swap2(struct RedBlackTree* tree, struct Stack* stack, __code next(...)) { + printf("swap2\n"); struct Node* toTree = (Node*)(stack->data); - struct RedBlackTree* newRedBlackTree = new RedBlackTree(); newRedBlackTree->root = toTree; newRedBlackTree->current = toTree; tree = newRedBlackTree; - printf("swap1\n"); printf("copied\n"); goto next(...); } -__code popWhenNoEmpty(struct Node* node, struct RedBlackTree* tree, struct Stack* inputStack) { - struct Stack* nodeStack = tree->nodeStack; - printf("popWhenNoEmpty\n"); - goto nodeStack->pop(up2); -} - __code insertNode(struct RedBlackTree* tree, struct Node* node) { struct Stack* nodeStack = tree->nodeStack; struct Node* newNode = tree->newNode;