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) {