Mercurial > hg > GearsTemplate

changeset 73:2667c3251a00

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
implement llrb deletion
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Tue, 10 Nov 2015 10:21:37 +0900
parents 5c4b9d116eda
children 724b65b1cfaf
files src/llrb/llrb.c src/llrb/llrbContext.c src/llrb/llrbContext.h src/llrb/main.c
diffstat 4 files changed, 306 insertions(+), 190 deletions(-) [+]
line wrap: on
line diff
--- a/src/llrb/llrb.c	Tue Nov 10 01:59:04 2015 +0900
+++ b/src/llrb/llrb.c	Tue Nov 10 10:21:37 2015 +0900
@@ -165,8 +165,12 @@
 
 __code colorFlip(struct Context* context, struct Node* node) {
     node->color ^= 1;
-    node->left->color ^= 1;
-    node->right->color ^= 1;
+
+    if (node->left != 0)
+        node->left->color ^= 1;
+
+    if (node->right != 0)
+        node->right->color ^= 1;
 
     stack_pop(context->code_stack, &context->next);
     goto meta(context, context->next);
@@ -244,227 +248,315 @@
 
     tree->current = tree->root;
     compare(context, tree, tree->current->key, context->data[Node]->node.key);
-    goto meta(context, Replace_d);
+    goto meta(context, Replace_d1);
 }
 
 __code delete_stub(struct Context* context) {
     goto delete(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate);
 }
 
-__code replaceNode_d(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, struct Node* node) {
+__code replaceNode_d1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, struct Node* node) {
     *newNode = *oldNode;
     tree->current = newNode;
     
     if (tree->result == -1) {
-        
-        if (tree->current->left != 0)
-            if (tree->current->left->left != 0)
-                if (tree->current->left->color != Red && tree->current->left->left->color != Red)
-                    goto meta(context, MoveRedL);
-        
-        stack_push(node_stack, &tree->current);
+        if (tree->current->left != 0) {
 
-        tree->current->left = context->heap;
-        tree->current = oldNode->left;
+            if (tree->current->left->left != 0)
+                if (tree->current->left->color != Red && tree->current->left->left->color != Red) {
+                    context->next = MoveRedL1;
+                    
+                    stack_push(context->code_stack, &context->next);
+                    goto meta(context, ColorFlip);
+                }
+            
+            stack_push(context->node_stack, &tree->current);
 
-        allocator(context);
-        compare(context, tree, tree->current->key, context->data[Node]->node.key);
-        
-        goto meta(context, Replace_d);
+            tree->current->left = context->heap;
+            tree->current = oldNode->left;
+
+            allocator(context);
+            compare(context, tree, tree->current->key, context->data[Node]->node.key);
+
+            goto meta(context, Replace_d1);
+        }
     } else {
         if (tree->current->left != 0)
-            if (tree->current->left->color = Red) {
+            if (tree->current->left->color == Red) {
                 allocator(context);
-                *context->data[context->dataNum]->node = *tree->current->left;
-                tree->current->left = context->data[context->dataNum]->node;
-                
-                // roatate right
-                struct Node* tmp = tree->current->left;
-                tree->current->left = tmp->right;
-                tmp->right = tree->current;
-                tmp->color = tree->current->color;
-                tree->current->color = Red;
-                tree->current = tmp;
-            }
+                context->data[context->dataNum]->node = *tree->current->left;
+                tree->current->left = &context->data[context->dataNum]->node;
 
-        if (tree->result == 0 && tree->current->right == 0) {
-            stack_pop(node_stack, &tree->current);
-
-            compare(context, tree, tree->current->key, context->data[Node]->node.key);
+                context->next = Replace_d2;
+                stack_push(context->code_stack, &context->next);
 
-            if (tree->result == 1) {
-                tree->current->right = 0;
-            } else {
-                tree->current->left = 0;
+                goto meta(context, RotateR);
             }
 
-            if (tree->current->right != 0)
-                if (tree->current->right->color == Red)
-                    goto meta(context, RotateL);
-            
-            if (tree->current->left != 0)
-                if (tree->current->left->left != 0)
-                    if (tree->current->left->color == Red && tree->current->left->left->color == Red)
-                        goto meta(context, RotateR);
-            
-            goto meta(context, FixUp);
+        goto meta(context, Replace_d2);
+    }
+}
+
+__code replaceNode_d1_stub(struct Context* context) {
+    goto replaceNode_d1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, &context->data[Node]->node);
+}
+
+__code replaceNode_d2(struct Context* context, struct Tree* tree) {
+    if (tree->result == 0 && tree->current->right == 0) {
+        stack_pop(context->node_stack, &tree->current);
+
+        compare(context, tree, tree->current->key, context->data[Node]->node.key);
+        
+        if (tree->result == 1) {
+            tree->current->right = 0;
+        } else {
+            tree->current->left = 0;
         }
-            
+
+        goto meta(context, Balance1);
+    }
+
+    goto meta(context, Replace_d3);
+}
 
-        if (tree->current->right != 0) {
-            if (tree->right->left != 0) {
-                if (tree->current->right->color != Red && tree->current->right->left->color != Red) {
-                    goto meta(context, MoveRedR);
-                }
+__code replaceNode_d2_stub(struct Context* context) {
+    goto replaceNode_d2(context, &context->data[Tree]->tree);
+}
+
+__code replaceNode_d3(struct Context* context, struct Tree* tree) {
+    if (tree->current->right != 0) {
+        if (tree->current->right->left != 0)
+            if (tree->current->right->color != Red && tree->current->right->left->color != Red) {
+                context->next = MoveRedR1;
+                stack_push(context->code_stack, &context->next);
+
+                goto meta(context, ColorFlip);
             }
 
-            stack_push(node_stack, &tree->current);
-        
-            tree->current->right = context->heap;
-            tree->current = oldNode->right;
-            
-            allocator(context);
+        goto meta(context, Replace_d4);
+    }
+}
 
-            goto(context, Replace_d);
-
-        }
-        
-    allocator(context);
-    compare(context, tree, tree->current->key, context->data[Node]->node.key);
-    goto meta(context, Replace_d);
+__code replaceNode_d3_stub(struct Context* context) {
+    goto replaceNode_d3(context, &context->data[Tree]->tree);
 }
 
-__code replaceNode_d_stub(struct Context* context) {
-    goto replaceNode_d(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, &context->data[Node]->node);
+__code replaceNode_d4(struct Context* context, struct Tree* tree, struct Node* node) {
+    stack_push(context->node_stack, &tree->current);
+
+    if (tree->result == 0) {
+        tree->current = node->right;
+        goto meta(context, FindMin);
+    } else {
+        struct Node* next = node->right;
+        tree->current->right = context->heap;
+        tree->current = next;
+        
+        allocator(context);
+
+        compare(context, tree, tree->current->key, context->data[Node]->node.key);
+
+        goto meta(context, Replace_d1);
+    }
 }
 
-__code moveRedLeft(struct Context* context, struct Node* node) {
-    // color flip
-    node->color ^= 1;
-    node->left->color ^= 1;
-    node->right->color ^= 1;
+__code replaceNode_d4_stub(struct Context* context) {
+    goto replaceNode_d4(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+}
 
+__code moveRedLeft1(struct Context* context, struct Tree* tree, struct Node* node) {
     if (tree->current->right != 0)
         if (tree->current->right->left != 0)
             if (tree->current->right->left == Red) {
                 allocator(context);
-                *context->data[context->dataNum]->node = *node->right;
-                node->right = context->data[context->dataNum]->node;
+                context->data[context->dataNum]->node = *node->right;
+                node->right = &context->data[context->dataNum]->node;
                 
                 allocator(context);
-                *context->data[context->dataNum]->node = *node->right->left;
-                node->right->left = context->data[context->dataNum]->node;
-
-                // rotate right
-                struct Node* tmp = node->right->left;
-                node->right->left = tmp->right;
-                tmp->right = node->right;
-                tmp->color = node->right->color;
-                node->right->color = Red;
-                node->right = tmp;
-
-                // rotate left
-                tmp = node->right;
-                node->right = tmp->left;
-                tmp->left = node;
-                tmp->color = node->color;
-                node->color = Red;
-
-                // color flip
-                node->color ^= 1;
-                node->left->color ^= 1;
-                node->right->color ^= 1;
-
-                tree->current = tmp;
+                context->data[context->dataNum]->node = *node->right->left;
+                node->right->left = &context->data[context->dataNum]->node;
+                
+                stack_push(context->node_stack, &tree->current);
+                tree->current = node->right;
+                
+                context->next = MoveRedL2;
+                stack_push(context->code_stack, &context->next);
+                
+                goto meta(context, RotateR);
             }
 
-    stack_push(node_stack, &tree->current);
+    stack_pop(context->code_stack, &context->next);
+    if (context->next == DeleteMin2)
+        goto meta(context, context->next);
 
+    stack_push(context->code_stack, &context->next);
+    stack_push(context->node_stack, &tree->current);
+    
+    struct Node* next = node->left;
     tree->current->left = context->heap;
-    tree->current = oldNode->left;
-
+    tree->current = next;
+    
     allocator(context);
     compare(context, tree, tree->current->key, context->data[Node]->node.key);
     
-    goto meta(context, Replace_d);
+    goto meta(context, Replace_d1);
+}
+
+__code moveRedLeft1_stub(struct Context* context) {
+    goto moveRedLeft1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+}
+ 
+__code moveRedLeft2(struct Context* context, struct Tree* tree) {
+    stack_pop(context->node_stack, &tree->current);
+
+    context->next = MoveRedL3;
+    stack_push(context->code_stack, &context->next);
+
+    context->next = ColorFlip;
+    stack_push(context->code_stack, &context->next);
+
+    goto meta(context, RotateL);
 }
 
-__code moveRedRight(struct Context* context, struct Node* node) {
-    // color flip
-    node->color ^= 1;
-    node->left->color ^= 1;
-    node->right->color ^= 1;
+__code moveRedLeft2_stub(struct Context* context) {
+    goto moveRedLeft2(context, &context->data[Tree]->tree);
+}
+
+__code moveRedLeft3(struct Context* context, struct Tree* tree) {
+    stack_pop(context->code_stack, &context->next);
+    if (context->next == DeleteMin2)
+        goto meta(context, context->next);
+
+    stack_push(context->code_stack, &context->next);
+    stack_push(context->node_stack, &tree->current);
 
+    tree->current = tree->current->left;
+    
+    compare(context, tree, tree->current->key, context->data[Node]->node.key);
+    
+    goto meta(context, Replace_d1);
+}
+
+__code moveRedLeft3_stub(struct Context* context) {
+    goto moveRedLeft3(context, &context->data[Tree]->tree);
+}
+
+__code moveRedRight1(struct Context* context, struct Tree* tree, struct Node* node) {
     if (tree->current->left != 0)
         if (tree->current->left->left != 0)
             if (tree->current->left->left == Red) {
                 allocator(context);
-                *context->data[context->dataNum]->node = *node->left;
-                node->left = context->data[context->dataNum]->node;
+                context->data[context->dataNum]->node = *node->left;
+                node->left = &context->data[context->dataNum]->node;
                 
-                // rotate right
-                struct Node* tmp = node->left;
-                node->left = tmp->right;
-                tmp->right = node;
-                tmp->color = node->color;
-                node->color = Red;
+                context->next = MoveRedR2;
+                stack_push(context->code_stack, &context->next);
+
+                context->next = ColorFlip;
+                stack_push(context->code_stack, &context->next);
+
+                goto meta(context, RotateR);
+            }
+
+    goto meta(context, Replace_d4);
+}
 
-                // color flip
-                node->color ^= 1;
-                node->left->color ^= 1;
-                node->right->color ^= 1;
+__code moveRedRight1_stub(struct Context* context) {
+    goto moveRedRight1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+}
+
+__code moveRedRight2(struct Context* context, struct Tree* tree) {
+    stack_push(context->node_stack, &tree->current);
+    tree->current = tree->current->right;
+    
+    compare(context, tree, tree->current->key, context->data[Node]->node.key);
+    
+    goto meta(context, Replace_d1);
+}
 
-                tree->current = tmp;
-            }
-    
-    stack_push(node_stack, &tree->current);
-    
-    tree->current->right = context->heap;
-    tree->prev = tree->current;
-    tree->current = oldNode->right;
-    
-    allocator(context);
-    if (tree->result = 0) {
-        goto meta(context, DeleteMin);
+__code moveRedRight2_stub(struct Context* context) {
+    goto moveRedRight2(context, &context->data[Tree]->tree);
+}
+
+__code findMin(struct Context* context, struct Tree* tree, struct Node* tmp) {
+    if (tree->current->left == 0) {
+        tmp->key = tree->current->key;
+        tmp->value = tree->current->value;
+            
+        stack_pop(context->node_stack, &tree->current);
+
+        tree->current->key = tmp->key;
+        tree->current->value = tmp->value;
+
+        stack_push(context->node_stack, &tree->current);
+
+        struct Node* next = tree->current->right;
+
+        tree->current->right = context->heap;
+        tree->current = next;
+
+        allocator(context);
+
+        goto meta(context, DeleteMin1);
     } else {
-        compare(context, tree, tree->current->key, context->data[Node]->node.key);
-        
-        goto meta(context, Replace_d);
+        tree->current = tree->current->left;
+
+        goto meta(context, FindMin);
     }
 }
 
-__code colorFlip_stub(struct Context* context) {
-    goto colorFlip(context, context->data[Tree]->tree.current);
+__code findMin_stub(struct Context* context) {
+    goto findMin(context, &context->data[Tree]->tree, &context->data[Node]->node);
 }
 
-__code deleteMin(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
-    stack_push(node_stack, &newNode);
-    
+__code deleteMin1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) {
     *newNode = *oldNode;
     tree->current = newNode;
 
     if (tree->current->left == 0) {
-        newNode->left = 0;
+        struct Node* node = tree->current;
+
+        stack_pop(context->node_stack, &tree->current);
+        
+        compare(context, tree, tree->current->key, node->key);
 
-        if (tree->current->right != 0)
-            if (tree->current->right->color == Red)
-                goto meta(context, RotateL);
+        if (tree->result == -1) {
+            tree->current->left = 0;
+        } else {
+            tree->current->right = 0;
+        }
         
-        goto meta(context, FixUp);
+        goto meta(context, Balance1);
     }
 
     if (tree->current->left != 0)
         if (tree->current->left->left != 0)
-            if (tree->current->left->color != Red && tree->current->left->left->color != Red)
-                goto meta(context, MoveRedL);
+            if (tree->current->left->color != Red && tree->current->left->left->color != Red) {
+                context->next = DeleteMin2;
+                stack_push(context->code_stack, &context->next);
+
+                context->next = MoveRedL1;
+                stack_push(context->code_stack, &context->next);
+                
+                goto meta(context, ColorFlip);
+            }
 
-    tree->current = oldNode->left;
-    newNode->left = context->heap;
+    goto meta(context, DeleteMin2);
+}
+
+__code deleteMin1_stub(struct Context* context) {
+    goto deleteMin1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node);
+}
+
+__code deleteMin2(struct Context* context, struct Tree* tree, struct Node* node) {
+    stack_push(context->node_stack, &tree->current);
+    tree->current->left = context->heap;
+    tree->current = node->left;
 
     allocator(context);
-    goto meta(context, DeleteMin);
+    goto meta(context, DeleteMin1);
 }
 
-__code max_stub(struct Context* context) {
-    goto max(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node);
+__code deleteMin2_stub(struct Context* context) {
+    goto deleteMin2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
 }
--- a/src/llrb/llrbContext.c	Tue Nov 10 01:59:04 2015 +0900
+++ b/src/llrb/llrbContext.c	Tue Nov 10 10:21:37 2015 +0900
@@ -23,11 +23,19 @@
 extern __code balance2_stub(struct Context*);
 extern __code balance3_stub(struct Context*);
 extern __code get_stub(struct Context*);
+extern __code findMin_stub(struct Context*);
 extern __code delete_stub(struct Context*);
-extern __code deleteMax_stub(struct Context*);
-extern __code deleteMin_stub(struct Context*);
-extern __code replaceNode_d_stub(struct Context*);
-extern __code max_stub(struct Context*);
+extern __code replaceNode_d1_stub(struct Context*);
+extern __code replaceNode_d2_stub(struct Context*);
+extern __code replaceNode_d3_stub(struct Context*);
+extern __code replaceNode_d4_stub(struct Context*);
+extern __code moveRedLeft1_stub(struct Context*);
+extern __code moveRedLeft2_stub(struct Context*);
+extern __code moveRedLeft3_stub(struct Context*);
+extern __code moveRedRight1_stub(struct Context*);
+extern __code moveRedRight2_stub(struct Context*);
+extern __code deleteMin1_stub(struct Context*);
+extern __code deleteMin2_stub(struct Context*);
 extern __code exit_code(struct Context*);
 
 __code initLLRBContext(struct Context* context, int num) {
@@ -37,32 +45,41 @@
     context->heapStart = malloc(context->heapLimit);
 
     context->codeNum = Exit;
-    context->code[Code1]     = code1_stub;
-    context->code[Code2]     = code2_stub;
-    context->code[Code3]     = code3_stub;
-    context->code[Code4]     = code4;
-    context->code[Code5]     = code5;
-    context->code[Find]      = find;
-    context->code[Not_find]  = not_find;
-    context->code[Code6]     = code6;
-    context->code[Put]       = put_stub;
-    context->code[Replace]   = replaceNode_stub;
-    context->code[Insert]    = insertNode_stub;
-    context->code[RotateL]   = rotateLeft_stub;
-    context->code[RotateR]   = rotateRight_stub;
-    context->code[ColorFlip] = colorFlip_stub;
-    context->code[FixUp]     = fixUp_stub;
-    context->code[ChangeRef] = changeReference_stub;
-    context->code[Balance1]  = balance1_stub;
-    context->code[Balance2]  = balance2_stub;
-    context->code[Balance3]  = balance3_stub;
-    context->code[Get]       = get_stub;
-    /* context->code[Delete]    = delete_stub; */
-    /* context->code[DeleteMax] = deleteMax_stub; */
-    /* //    context->code[DeleteMin] = deleteMin_stub; */
-    /* context->code[Replace_d] = replaceNode_d_stub; */
-    /* context->code[Max]       = max_stub; */
-    context->code[Exit]      = exit_code;
+
+    context->code[Code1]      = code1_stub;
+    context->code[Code2]      = code2_stub;
+    context->code[Code3]      = code3_stub;
+    context->code[Code4]      = code4;
+    context->code[Code5]      = code5;
+    context->code[Find]       = find;
+    context->code[Not_find]   = not_find;
+    context->code[Code6]      = code6;
+    context->code[Put]        = put_stub;
+    context->code[Replace]    = replaceNode_stub;
+    context->code[Insert]     = insertNode_stub;
+    context->code[RotateL]    = rotateLeft_stub;
+    context->code[RotateR]    = rotateRight_stub;
+    context->code[ColorFlip]  = colorFlip_stub;
+    context->code[FixUp]      = fixUp_stub;
+    context->code[ChangeRef]  = changeReference_stub;
+    context->code[Balance1]   = balance1_stub;
+    context->code[Balance2]   = balance2_stub;
+    context->code[Balance3]   = balance3_stub;
+    context->code[Get]        = get_stub;
+    context->code[Delete]     = delete_stub;
+    context->code[FindMin]    = findMin_stub;
+    context->code[Replace_d1] = replaceNode_d1_stub;
+    context->code[Replace_d2] = replaceNode_d2_stub;
+    context->code[Replace_d3] = replaceNode_d3_stub;
+    context->code[Replace_d4] = replaceNode_d4_stub;
+    context->code[MoveRedL1]  = moveRedLeft1_stub;
+    context->code[MoveRedL2]  = moveRedLeft2_stub;
+    context->code[MoveRedL3]  = moveRedLeft3_stub;
+    context->code[MoveRedR1]  = moveRedRight1_stub;
+    context->code[MoveRedR2]  = moveRedRight2_stub;
+    context->code[DeleteMin1] = deleteMin1_stub;
+    context->code[DeleteMin2] = deleteMin2_stub;
+    context->code[Exit]       = exit_code;
     
     context->heap = context->heapStart;
 
--- a/src/llrb/llrbContext.h	Tue Nov 10 01:59:04 2015 +0900
+++ b/src/llrb/llrbContext.h	Tue Nov 10 10:21:37 2015 +0900
@@ -27,11 +27,19 @@
     Balance2,
     Balance3,
     Get,
+    FindMin,
     Delete,
-    DeleteMax,
-    DeleteMin,
-    Replace_d,
-    Max,
+    Replace_d1,
+    Replace_d2,
+    Replace_d3,
+    Replace_d4,
+    MoveRedL1,
+    MoveRedL2,
+    MoveRedL3,
+    MoveRedR1,
+    MoveRedR2,
+    DeleteMin1,
+    DeleteMin2,
     Exit,
 };
 
--- a/src/llrb/main.c	Tue Nov 10 01:59:04 2015 +0900
+++ b/src/llrb/main.c	Tue Nov 10 10:21:37 2015 +0900
@@ -25,7 +25,7 @@
         print_tree(node->left, n+1);
         for (int i=0;i<n;i++)
             printf("  ");
-        printf(/*"key=%d value=%d depth=%d */"color=%s\t%p\n", /*node->key, node->value, n, */node->color==0? "R":"B", node);
+        printf("key=%d value=%d color=%s\t%p\n", node->key, node->value,/* n, */node->color==0? "R":"B", node);
         print_tree(node->right, n+1);
     }
 }
@@ -88,12 +88,11 @@
     print_tree(context->data[Tree]->tree.root, 0);
     
     struct Node* node = &context->data[Node]->node;
-    node->key = 0;
-    node->value = 0;
+    node->key = 5;
     
     context->next = Code5;
 
-    goto meta(context, DeleteMax);
+    goto meta(context, Delete);
 }
 
 __code code5(struct Context* context) {