Mercurial > hg > Members > Moririn

changeset 470:355f7f78e3cf

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
remove error, RedBlackTree.cbc Deletion Code
author ryokka
date Wed, 27 Dec 2017 20:21:30 +0900
parents ed494f4004c9
children e5f0cced7d43
files src/parallel_execution/RedBlackTree.cbc src/parallel_execution/context.h
diffstat 2 files changed, 274 insertions(+), 344 deletions(-) [+]
line wrap: on
line diff
--- a/src/parallel_execution/RedBlackTree.cbc	Wed Dec 27 18:26:37 2017 +0900
+++ b/src/parallel_execution/RedBlackTree.cbc	Wed Dec 27 20:21:30 2017 +0900
@@ -15,7 +15,7 @@
     redBlackTree->nodeStack = createSingleLinkedStack(context);
     tree->put = C_putRedBlackTree;
     tree->get = C_getRedBlackTree;
-    // tree->remove = C_removeRedBlackTree;
+    tree->remove = C_removeRedBlackTree;
     // tree->clear = C_clearRedBlackTree;
     return tree;
 }
@@ -48,6 +48,7 @@
     if (root) {
         tree->current = root;
         tree->result = compare(tree->current, node);
+        tree->findNodeNext = C_insertNode;
         goto findNode(tree);
     }
     goto insertNode(tree, node);
@@ -83,8 +84,9 @@
         tree->result = compare(tree->current, node);
         goto findNode(tree);
     }
-    goto insertNode(tree, node);
-
+    goto meta(context, tree->findNodeNext);
+    //   gato tree->findNodeNext(tree, node);
+    
 }
 
 __code insertNode(struct RedBlackTree* tree, struct Node* node) {
@@ -312,344 +314,271 @@
     goto next(...);
 }
 
-// __code delete(struct Context* context, struct Tree* tree) {
-//     if (tree->root) {
-//         stack_push(context->code_stack, &context->next);
-//         context->next = Delete1;
-//         goto meta(context, Get);
-//     }
-// 
-//     goto meta(context, context->next);
-// }
-// 
-// __code delete_stub(struct Context* context) {
-//     goto delete(context, &context->data[Tree]->tree);
-// }
-// 
-// __code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) {
-//     allocate->size = sizeof(struct Node);
-//     allocator(context);
-//     
-//     struct Node* root = tree->root;
-// 
-//     tree->root = &context->data[context->dataNum]->node;
-//     tree->current = root;
-// 
-//     compare(context, tree, tree->current->key, context->data[Node]->node.key);
-//     
-//     goto meta(context, Replace_d1);
-// }
-// 
-// __code delete1_stub(struct Context* context) {
-//     goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate);
-// }
-// 
-// __code delete2(struct Context* context, struct Node* current) {
-//     if (current->color == Black) {
-//         struct Node* child = current->right == NULL ? current->left : current->right;
-//         current->color = child == NULL ? Black : child->color;
-// 
-//         goto meta(context, DeleteCase1);
-//     }
-// 
-//     goto meta(context, Delete3);
-// }
-// 
-// __code delete2_stub(struct Context* context) {
-//     goto delete2(context, context->data[Tree]->tree.current);
-// }
-// 
-// __code delete3(struct Context* context, struct Tree* tree, struct Node* current) {
-//     struct Node* tmp = current->right == NULL ? current->left : current->right;
-// 
-//     if (current->parent) {
-//         if (current == current->parent->left)
-//             current->parent->left = tmp;
-//         else
-//             current->parent->right = tmp;
-//     } else {
-//         tree->root = tmp;
-//     }
-// 
-//     if (tmp)
-//         tmp->parent = current->parent;
-// 
-//     if (current->parent == NULL && tmp)
-//         tmp->color = Black;
-// 
-//     current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL);
-// 
-//     stack_pop(context->code_stack, &context->next);
-//     goto meta(context, context->next);
-// }
-// 
-// __code delete3_stub(struct Context* context) {
-//     goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
-// }
-// 
-// __code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) {
-//     *newNode = *oldNode;
-// 
-//     if (result == EQ)
-//         goto meta(context, Replace_d2);
-//     else if (result == GT)
-//         tree->current = newNode->right;
-//     else
-//         tree->current = newNode->left;
-// 
-//     tree->current->parent = newNode;
-//     
-//     if (tree->current->left == NULL && tree->current->right == NULL)
-//         goto meta(context, Delete2);
-//     
-//     if (result == GT)
-//         newNode->right = context->heap;
-//     else if (result == LT)
-//         newNode->left = context->heap;
-//     
-//     allocator(context);
-//     
-//     compare(context, tree, tree->current->key, context->data[Node]->node.key);
-//     
-//     goto meta(context, Replace_d1);
-// }
-// 
-// __code replaceNodeForDelete1_stub(struct Context* context) {
-//     goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result);
-// }
-// 
-// __code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) {
-//     if (tree->current->left && tree->current->right) {
-//         newNode->left->parent = newNode;
-//         tree->current = newNode->left;
-//         newNode->left = context->heap;
-//         tree->deleted = newNode;
-// 
-//         allocator(context);
-//         tree->current->parent = newNode;
-//         
-//         goto meta(context, FindMax1);
-//     }
-// 
-//     goto meta(context, Delete2);
-// }
-// 
-// __code replaceNodeForDelete2_stub(struct Context* context) {
-//     goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node);
-// }
-// 
-// __code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
-//     *newNode = *oldNode;
-// 
-//     if (newNode->right)
-//         goto meta(context, FindMax2);
-//     
-//     tree->deleted->key = newNode->key;
-//     tree->deleted->value = newNode->value;
-// 
-//     tree->current = newNode;
-// 
-//     goto meta(context, Delete2);
-// }
-// 
-// __code findMax1_stub(struct Context* context) {
-//     goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node);
-// }
-//     
-// 
-// __code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
-//     *newNode = *oldNode;
-// 
-//     if (newNode->right->right) {
-//         tree->current = newNode->right;
-//         newNode->right = context->heap;
-// 
-//         allocator(context);
-//         tree->current->parent = newNode;
-//         
-//         goto meta(context, FindMax2);
-//     }
-// 
-//     tree->deleted->key = newNode->right->key;
-//     tree->deleted->value = newNode->right->value;
-// 
-//     tree->current = newNode;
-//     
-//     goto meta(context, Delete2);
-// }
-//     
-// __code findMax2_stub(struct Context* context) {
-//     goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node);
-// }
-// 
-// __code deleteCase1(struct Context* context, struct Node* current) {
-//     if (current->parent)
-//         goto meta(context, DeleteCase2);
-// 
-//     goto meta(context, Delete3);
-// }
-// 
-// __code deleteCase1_stub(struct Context* context) {
-//     goto deleteCase1(context, context->data[Tree]->tree.current);
-// }
-// 
-// __code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) {
-//     struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
-//     
-//     if ((sibling == NULL ? Black : sibling->color) == Red) {
-//         current->parent->color = Red;
-//         sibling->color = Black;
-// 
-//         current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap);
-//         allocator(context);
-//         context->data[context->dataNum]->node = *sibling;
-//         
-//         tree->current = current->parent;
-//         
-//         context->next = DeleteCase3;
-//         stack_push(context->code_stack, &context->next);
-// 
-//         if (current == current->parent->left)
-//             goto meta(context, RotateL);
-//         else
-//             goto meta(context, RotateR);
-//     }
-// 
-//     goto meta(context, DeleteCase3);
-// }
-// 
-// __code deleteCase2_stub(struct Context* context) {
-//     goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
-// }
-// 
-// __code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) {
-//     struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
-//     
-//     if (current->parent->color == Black &&
-//         (sibling == NULL ? Black : sibling->color) == Black &&
-//         (sibling->left == NULL ? Black : sibling->left->color) == Black &&
-//         (sibling->right == NULL ? Black : sibling->right->color) == Black) {
-//         sibling->color = Red;
-// 
-//         tree->current = current->parent;
-//         goto meta(context, DeleteCase1);
-//     }
-// 
-//     goto meta(context, DeleteCase4);
-// }
-// 
-// __code deleteCase3_stub(struct Context* context) {
-//     goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
-// }
-// 
-// __code deleteCase4(struct Context* context, struct Node* current) {
-//     struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
-//     
-//     if (current->parent->color == Red &&
-//         (sibling == NULL ? Black : sibling->color) == Black &&
-//         (sibling->left == NULL ? Black : sibling->left->color) == Black &&
-//         (sibling->right == NULL ? Black : sibling->right->color) == Black) {
-//         sibling->color = Red;
-//         current->parent->color = Black;
-// 
-//         goto meta(context, Delete3);
-//     }
-// 
-//     goto meta(context, DeleteCase5);
-// }
-// 
-// __code deleteCase4_stub(struct Context* context) {
-//     goto deleteCase4(context, context->data[Tree]->tree.current);
-// }
-// 
-// __code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) {
-//     struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
-//     sibling->parent = current->parent;
-//     
-//     if (current == current->parent->left &&
-//         (sibling == NULL ? Black : sibling->color) == Black &&
-//         (sibling->left == NULL ? Black : sibling->left->color) == Red &&
-//         (sibling->right == NULL ? Black : sibling->right->color) == Black) {
-//         sibling->color = Red;
-//         sibling->left->color = Black;
-//         
-//         sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap);
-//         allocator(context);
-//         struct Node* tmp = &context->data[context->dataNum]->node;
-//         *tmp = *sibling;
-//         tmp->parent = current;
-//         
-//         tmp->left = context->heap;
-//         allocator(context);
-//         context->data[context->dataNum]->node = *sibling->left;
-//         context->data[context->dataNum]->node.parent = tmp;
-// 
-//         tree->current = tmp;
-//         
-//         context->next = DeleteCase6;
-//         stack_push(context->code_stack, &context->next);
-// 
-//         goto meta(context, RotateR);
-//     } else if (current == current->parent->right &&
-//                (sibling == NULL ? Black : sibling->color) == Black &&
-//                (sibling->left == NULL ? Black : sibling->left->color) == Black &&
-//                (sibling->right == NULL ? Black : sibling->right->color) == Red) {
-//         sibling->color = Red;
-//         sibling->right->color = Black;
-// 
-//         sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap);
-//         allocator(context);
-//         struct Node* tmp = &context->data[context->dataNum]->node;
-//         *tmp = *sibling;
-//         tmp->parent = current;
-// 
-//         tmp->right = context->heap;
-//         allocator(context);
-//         context->data[context->dataNum]->node = *sibling->right;
-//         context->data[context->dataNum]->node.parent = tmp;
-// 
-//         tree->current = tmp;
-// 
-//         context->next = DeleteCase6;
-//         stack_push(context->code_stack, &context->next);
-//         goto meta(context, RotateL);
-//     }
-// 
-//     goto meta(context, DeleteCase6);
-// }
-// 
-// __code deleteCase5_stub(struct Context* context) {
-//     goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
-// }
-// 
-// __code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) {
-//     struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left;
-// 
-//     sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap);
-//     allocator(context);
-//     struct Node* tmp = &context->data[context->dataNum]->node;
-//     *tmp = *sibling;
-//     tmp->parent = current;
-// 
-//     tmp->color = current->parent->color;
-//     current->parent->color = Black;
-//     
-//     context->next = Delete3;
-//     stack_push(context->code_stack, &context->next);
-//     
-//     if (current == current->parent->left) {
-//         tmp->right->color = Black;
-//         tree->current = current->parent;
-// 
-//         goto meta(context, RotateL);
-//     } else {
-//         tmp->left->color = Black;
-//         tree->current = current->parent;
-// 
-//         goto meta(context, RotateR);
-//     }
-// }
-// 
-// __code deleteCase6_stub(struct Context* context) {
-//     goto deleteCase6(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
-// }
+__code removeRedBlackTree(struct RedBlackTree* tree, struct Node* node, __code next(...)) {
+    struct Node* newNode = &ALLOCATE(context, Node)->Node;
+    struct Node* root = tree->root;
+    printTree((union Data*)(tree->root));
+    tree->newNode = newNode;
+    tree->root = newNode; // this should done at stackClear
+    tree->parent = NULL;
+    if (root) {
+        tree->current = root;
+        tree->result = compare(tree->current, node);
+        tree->findNodeNext = C_replaceNodeForDelete2;
+        goto findNode(tree);
+    }
+    goto next(...);
+}
+
+
+
+__code delete2(struct Node* current) {
+    if (current->color == Black) {
+        struct Node* child = current->right == NULL ? current->left : current->right;
+        current->color = child == NULL ? Black : child->color;
+
+        goto deleteCase1(current);
+    }
+
+    goto delete3(tree, current);
+}
+
+
+
+__code delete3(struct RedBlackTree* tree, struct Node* current, __code next(...)) {
+    struct Node* tmp = current->right == NULL ? current->left : current->right;
+    struct Stack* nodeStack = tree->nodeStack;
+
+    if (tree->parent) {
+        if (current == tree->parent->left)
+            tree->parent->left = tmp;
+        else
+            tree->parent->right = tmp;
+    } else {
+        tree->root = tmp;
+    }
+
+
+    if (tree->parent == NULL && tmp)
+        tmp->color = Black;
+
+    current == tree->parent->left ? (tree->parent->left = NULL) : (tree->parent->right = NULL);
+
+    Gearef(context, Stack)->stack = (union Data*) nodeStack;
+    Gearef(context, Stack)->next = next;
+    goto meta(context, nodeStack->pop);
+
+//    gato nodeStack->pop(next);
+}
+
+
+
+__code replaceNodeForDelete2(struct RedBlackTree* tree, struct Node* newNode) {
+    if (tree->current->left && tree->current->right) {
+        tree->parent = newNode;
+        tree->current = newNode->left;
+        newNode->left = context->heap;
+
+
+        tree->parent = newNode;
+        
+        goto findMax1(tree,oldNode, newNode);
+    }
+
+    goto delete2(current);
+}
+
+
+__code findMax1(struct RedBlackTree* tree, struct Node* oldNode, struct Node* newNode) {
+    *newNode = *oldNode;
+
+    if (newNode->right)
+        goto findMax2(tree, oldNode, newNode);
+    
+    tree->current = newNode;
+
+    goto delete2(current);
+}
+
+
+    
+
+__code findMax2(struct RedBlackTree* tree, struct Node* oldNode, struct Node* newNode) {
+    *newNode = *oldNode;
+
+    if (newNode->right->right) {
+        tree->current = newNode->right;
+        newNode->right = context->heap;
+
+        tree->parent = newNode;
+        
+        goto findMax2(tree, oldNode, newNode);
+    }
+
+    tree->current = newNode;
+    
+    goto delete2(tree,current);
+}
+    
+
+__code deleteCase1(struct RedBlackTree* tree, struct Node* current) {
+    if (tree->parent)
+        goto deleteCase2(tree,current);
+
+    goto delete3(tree, current);
+}
+
+
+
+__code deleteCase2(struct RedBlackTree* tree, struct Node* current, struct RotateTree* rotateTree) {
+    struct Node* sibling = current == tree->parent->left ? tree->parent->right : tree->parent->left;
+    
+    if ((sibling == NULL ? Black : sibling->color) == Red) {
+        tree->parent->color = Red;
+        sibling->color = Black;
+
+        current == tree->parent->left ? (tree->parent->left = context->heap) : (tree->parent->right = context->heap);
+
+        struct Node* node = sibling;
+        
+        tree->current = tree->parent;
+
+        rotateTree->traverse = tree;
+        rotateTree->next = C_deleteCase3;
+
+        if (current == tree->parent->left)
+            goto nodeStack->push(node,rotateLeft);
+        else
+            goto nodeStack->push(node,rotateRight);
+    }
+
+    goto deleteCase3(tree,current);
+}
+
+
+
+__code deleteCase3(struct RedBlackTree* tree, struct Node* current) {
+    struct Node* sibling = current == tree->parent->left ? tree->parent->right : tree->parent->left;
+    
+    if (tree->parent->color == Black &&
+        (sibling == NULL ? Black : sibling->color) == Black &&
+        (sibling->left == NULL ? Black : sibling->left->color) == Black &&
+        (sibling->right == NULL ? Black : sibling->right->color) == Black) {
+        sibling->color = Red;
+
+        tree->current = tree->parent;
+        goto deleteCase1(current);
+    }
+
+    goto deleteCase4(current);
+}
+
+
+
+__code deleteCase4(struct RedBlackTree* tree,struct Node* current) {
+    struct Node* sibling = current == tree->parent->left ? tree->parent->right : tree->parent->left;
+    
+    if (tree->parent->color == Red &&
+        (sibling == NULL ? Black : sibling->color) == Black &&
+        (sibling->left == NULL ? Black : sibling->left->color) == Black &&
+        (sibling->right == NULL ? Black : sibling->right->color) == Black) {
+        sibling->color = Red;
+        tree->parent->color = Black;
+
+        goto delete3(tree,current);
+    }
+
+    goto deleteCase5(tree,current);
+}
+
+
+
+__code deleteCase5(struct RedBlackTree* tree, struct Node* current, struct RotateTree* rotateTree) {
+    struct Node* sibling = current == tree->parent->left ? tree->parent->right : tree->parent->left;
+    sibling->parent = tree->parent;
+    
+    if (current == tree->parent->left &&
+        (sibling == NULL ? Black : sibling->color) == Black &&
+        (sibling->left == NULL ? Black : sibling->left->color) == Red &&
+        (sibling->right == NULL ? Black : sibling->right->color) == Black) {
+        sibling->color = Red;
+        sibling->left->color = Black;
+        
+        sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap);
+        allocator(context);
+        struct Node* tmp = &context->data[context->dataNum]->node;
+        *tmp = *sibling;
+        tmp->parent = current;
+        
+        tmp->left = context->heap;
+        struct Node* node = new Node();
+        node = *sibling->left;
+        node->parent = tmp;
+
+        tree->current = tmp;
+        
+        rotateTree->traverse = tree;
+        rotateTree->next = C_deleteCase6;
+
+        goto nodeStack->push(node,rotateRight);
+    } else if (current == tree->parent->right &&
+               (sibling == NULL ? Black : sibling->color) == Black &&
+               (sibling->left == NULL ? Black : sibling->left->color) == Black &&
+               (sibling->right == NULL ? Black : sibling->right->color) == Red) {
+        sibling->color = Red;
+        sibling->right->color = Black;
+
+        sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap);
+        allocator(context);
+        struct Node* tmp = &context->data[context->dataNum]->node;
+        *tmp = *sibling;
+        tmp->parent = current;
+
+        tmp->right = context->heap;
+        struct Node* node = new Node();
+        node = *sibling->right;
+        node->parent = tmp;
+
+        tree->current = tmp;
+        
+        rotateTree->traverse = tree;
+        rotateTree->next = C_deleteCase6;
+
+        goto nodeStack->push(node,rotateLeft);
+    }
+
+    goto deleteCase6(tree,current);
+}
+
+
+__code deleteCase6(struct RedBlackTree* tree, struct Node* current, struct RotateTree* rotateTree) {
+    struct Node* sibling = current == tree->parent->left ? tree->parent->right : tree->parent->left;
+
+    sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap);
+    allocator(context);
+    struct Node* tmp = &context->data[context->dataNum]->node;
+    *tmp = *sibling;
+    tmp->parent = current;
+
+    tmp->color = tree->parent->color;
+    tree->parent->color = Black;
+    
+    
+    if (current == tree->parent->left) {
+        tmp->right->color = Black;
+        tree->current = tree->parent;
+
+        rotateTree->traverse = tree;
+        rotateTree->next = C_delete3;
+
+        goto nodeStack->push(node,rotateLeft);
+    } else {
+        tmp->left->color = Black;
+        tree->current = tree->parent;
+
+        rotateTree->traverse = tree;
+        rotateTree->next = C_delete3;
+
+        goto nodeStack->push(node,rotateLeft);
+    }
+}
--- a/src/parallel_execution/context.h	Wed Dec 27 18:26:37 2017 +0900
+++ b/src/parallel_execution/context.h	Wed Dec 27 20:21:30 2017 +0900
@@ -283,6 +283,7 @@
         struct Node* parent;
         struct Node* grandparent;
         struct Stack* nodeStack;
+        enum Code findNodeNext;
         int result;
     } RedBlackTree;
     struct RotateTree {