Mercurial > hg > Gears > Gears
changeset 1040:cf2aa790afe7
...
author | matac42 <matac@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Sun, 12 Nov 2023 12:01:57 +0900 |
parents | 23528e058b25 |
children | 9b2f5dc02b2a |
files | src/parallel_execution/RedBlackTree.cbc |
diffstat | 1 files changed, 25 insertions(+), 45 deletions(-) [+] |
line wrap: on
line diff
--- a/src/parallel_execution/RedBlackTree.cbc Tue Nov 07 11:58:03 2023 +0900 +++ b/src/parallel_execution/RedBlackTree.cbc Sun Nov 12 12:01:57 2023 +0900 @@ -99,7 +99,6 @@ } __code leftDown(struct RedBlackTree* tree, struct Stack* inputStack, struct Stack* outputStack) { - // ノードをアロケートしてinputStackに入れる struct Node* newNode = &ALLOCATE(context, Node)->Node; newNode->key = tree->current->key; newNode->value = tree->current->value; @@ -110,77 +109,58 @@ } __code leftDown1(struct RedBlackTree* tree, struct Stack* inputStack, struct Stack* outputStack) { - // if tree->left goto leftDown(tree->left, inputStack, outputStack) - // else if tree->right goto rightDown(tree->right, inputStack, outputStack) - // else goto up(tree, inputStack, outputStack) + struct Stack* nodeStack = tree->nodeStack; if (tree->left) { goto leftDown(tree->left, inputStack, outputStack); } else if (tree->right) { goto rightDown(tree->right, inputStack, outputStack); } else { - goto up(tree, inputStack, outputStack); + goto nodeStack->pop(up); } } __code rightDown(struct RedBlackTree* tree, struct Stack* inputStack, struct Stack* outputStack) { - // ノードをアロケートしてinputStackに入れる struct Node* newNode = &ALLOCATE(context, Node)->Node; newNode->key = tree->current->key; newNode->value = tree->current->value; newNode->color = tree->current->color; + newNode->right = tree->current->right; tree->current = tree->current->right; struct Stack* nodeStack = tree->nodeStack; goto nodeStack->push(newNode, leftDown); } -__code up(struct RedBlackTree* tree, struct Stack* inputStack, struct Stack* outputStack) { - // if 左からきたら inputStack->top->leftを埋める - // goto rightDown() - // if 右からきたら - // pop inputStack - // pop outputStack - // inputStack->top->rightを埋めてgoto up(tree, inputStack, outputStack) +__code up(struct Node* node, struct RedBlackTree* tree, struct Stack* inputStack, struct Stack* outputStack) { struct Stack* nodeStack = tree->nodeStack; struct Node* newNode = tree->newNode; - if (nodeStack->top->left) { - nodeStack->top->left = newNode; - goto rightDown(tree, inputStack, outputStack); + if (node->left) { + tree->current = node->right; + node->left = newNode; + goto push((union Data*)node, rightDown); } else { - goto nodeStack->pop(up1); + node->right = newNode; + newNode = node; + goto nodeStack->isEmpty(popWhenNoEmpty, next(...)); } } -__code up1(struct RedBlackTree* tree, struct Stack* inputStack, struct Stack* outputStack) { - // inputStack->top->rightを埋めてgoto up(tree, inputStack, outputStack) +__code popWhenNoEmpty(struct Node* node, struct RedBlackTree* tree, struct Stack* inputStack, struct Stack* outputStack) { struct Stack* nodeStack = tree->nodeStack; - tree->current->right = nodeStack->top->right; - goto up(tree, inputStack, outputStack); + goto nodeStack->pop(up1); +} + +__code popWhenEmpty(struct Node* node, struct RedBlackTree* tree, struct Stack* inputStack, struct Stack* outputStack) { + } -__code copyRedBlackTree1(struct RedBlackTree* tree, struct Node* node, __code next(...)) { - struct Node* oldNode = tree->current; - struct Node* newNode = tree->previous; - struct Node* newnewNode = &ALLOCATE(context, Node)->Node; - newnewNode->key = oldNode->key; - newnewNode->value = oldNode->value; - newnewNode->left = newNode->left; - if (newnewNode->left != Null) { - goto copyRedBlackTree(newnewNode->left); - } - newnewNode->right = newNode->right; - if (newnewNode->right != Null) { - goto copyRedBlackTree(newnewNode->right); - } - goto copyRedBlackTreePop(tree); - tree->newNode = newnewNode; - - if (tree->current) { - tree->result = compare(tree->current, node); - goto findNode(tree); - } - goto meta(context, tree->findNodeNext); - // gato tree->findNodeNext(tree, node); - +__code up1(struct Node* node, struct RedBlackTree* tree, struct Stack* inputStack, struct Stack* outputStack) { + struct Stack* nodeStack = tree->nodeStack; + goto nodeStack->pop(up2); +} + +__code up2(struct Node* node, struct RedBlackTree* tree, struct Stack* inputStack, struct Stack* outputStack) { + tree->current->right = node->right; + goto up(tree, inputStack, outputStack); } __code insertNode(struct RedBlackTree* tree, struct Node* node) {