Mercurial > hg > GearsTemplate

changeset 77:618c03f25108

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
implement insert(tail recursion)
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Fri, 27 Nov 2015 02:14:25 +0900
parents 7ad6d1502a03
children 765ee56d68f1 099d85f9d371
files src/llrb/llrb.c src/llrb/llrbContext.c src/llrb/llrbContext.h src/llrb/main.c
diffstat 4 files changed, 155 insertions(+), 47 deletions(-) [+]
line wrap: on
line diff
--- a/src/llrb/llrb.c	Tue Nov 17 16:59:48 2015 +0900
+++ b/src/llrb/llrb.c	Fri Nov 27 02:14:25 2015 +0900
@@ -29,15 +29,12 @@
 }
 
 __code replaceNode(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) {
-    stack_push(context->node_stack, &newNode);
-
     *newNode = *oldNode;
 
     if (result == 0) {
-        stack_pop(context->node_stack, &tree->current);
         newNode->value = context->data[Node]->node.value;
 
-        goto meta(context, Balance1);
+        goto meta(context, SetRoot);
     } else if (result == 1) {
         tree->current = oldNode->right;
         newNode->right = context->heap;
@@ -49,11 +46,12 @@
     allocator(context);
 
     if (tree->current) {
+        tree->current->parent = newNode;
         compare(context, tree, tree->current->key, context->data[Node]->node.key);
         goto meta(context, Replace);
     }
-
-    stack_pop(context->node_stack, &tree->current);
+    
+    tree->current = newNode;
     goto meta(context, Insert);
 }
 
@@ -62,15 +60,10 @@
 }
 
 __code balance1(struct Context* context, struct Node* current) {
-    if (current->right)
-        if (current->right->color == Red) {
-            context->next = Balance2;
-
-            stack_push(context->code_stack, &context->next);
-            goto meta(context, RotateL);
-        }
-
-    goto meta(context, Balance2);
+    if (current->parent == 0)
+        goto meta(context, SetRoot);
+    else
+        goto meta(context, Balance2);
 }
 
 __code balance1_stub(struct Context* context) {
@@ -78,47 +71,110 @@
 }
 
 __code balance2(struct Context* context, struct Node* current) {
-    if (current->left)
-        if (current->left->left)
-            if (current->left->color == Red && current->left->left->color == Red) {
-                context->next = Balance3;
-
-                stack_push(context->code_stack, &context->next);
-                goto meta(context, RotateR);
-            }
-                
-    goto meta(context, Balance3);
+    if (current->parent->color == Black)
+        goto meta(context, SetRoot);
+    else
+        goto meta(context, Balance3);
 }
 
 __code balance2_stub(struct Context* context) {
     goto balance2(context, context->data[Tree]->tree.current);
 }
 
-__code balance3(struct Context* context, struct Node* current){
-    if (current->right && current->left)
-        if (current->right->color == Red && current->left->color == Red) {
-            context->next = FixUp;
+__code balance3(struct Context* context, struct Tree* tree, struct Node* current) {
+    struct Node* uncle;
+    struct Node* grandparent = current->parent->parent;
 
-            stack_push(context->code_stack, &context->next);
-            goto meta(context, ColorFlip);
-        }
+    if (grandparent == 0)
+        uncle = 0;
+    
+    if (grandparent->left == current->parent)
+        uncle = grandparent->right;
+    else
+        uncle = grandparent->left;
     
-    goto meta(context, FixUp);    
+    if ((uncle != 0) && (uncle->color == Red)) {
+        current->parent->color = Black;
+        uncle->color = Black;
+        grandparent->color = Red;
+        tree->current = grandparent;
+        goto meta(context, Balance1);
+    } else {
+        goto meta(context, Balance4);
+    }
 }
 
 __code balance3_stub(struct Context* context) {
-    goto balance3(context, context->data[Tree]->tree.current);
+    goto balance3(context, context->data[Tree], context->data[Tree]->tree.current);
+}
+
+__code balance4(struct Context* context, struct Node* current) {
+    struct Node* grandparent = current->parent->parent;
+
+    if ((current == current->parent->right) && (current->parent == grandparent->left)) {
+        context->next = Balance4_1;
+
+        stack_push(context->code_stack, &context->next);
+        goto meta(context, RotateL);
+    } else if ((current == current->parent->left) && (current->parent == grandparent->right)) {
+        context->next = Balance4_2;
+        
+        stack_push(context->code_stack, &context->next);
+        goto meta(context, RotateR);
+    }
+
+    goto meta(context, Balance5);
+}
+
+__code balance4_stub(struct Context* context) {
+    goto balance4(context, context->data[Tree]->tree.current);
+}
+
+__code balance4_1(struct Context* context, struct Tree* tree) {
+    tree->current = tree->current->left;
+    goto meta(context, Balance5);
+}
+
+__code balance4_1_stub(struct Context* context) {
+    goto balance4_1(context, context->data[Tree]);
+}   
+
+__code balance4_2(struct Context* context, struct Tree* tree) {
+    tree->current = tree->current->right;
+    goto meta(context, Balance5);
+}
+
+__code balance4_2_stub(struct Context* context) {
+    goto balance4_2(context, context->data[Tree]);
+}   
+
+__code balance5(struct Context* context, struct Tree* tree, struct Node* current) {
+    current->parent->color = Black;
+    current->parent->parent->color = Red;
+
+    context->next = SetRoot;
+
+    stack_push(context->code_stack, &context->next);
+    tree->current = current->parent->parent;
+
+    if ((current == current->parent->left) && (current->parent == current->parent->parent->left))
+        goto meta(context, RotateR);
+    else
+        goto meta(context, RotateL);
+}
+
+__code balance5_stub(struct Context* context) {
+    goto balance5(context, context->data[Tree], context->data[Tree]->tree.current);
 }
 
 __code insertNode(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) {
     node->color = Red;
     *newNode = *node;
+    newNode->parent = tree->current;
+    
+    tree->current = newNode;
 
-    if (tree->root)
-        goto meta(context, Balance1);
-
-    tree->current = newNode;
-    goto meta(context, SetRoot);
+    goto meta(context, Balance1);
 }
 
 __code insertNode_stub(struct Context* context) {
@@ -127,10 +183,26 @@
 
 __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree) {
     struct Node* tmp = node->right;
+
+    if (node->parent == 0) {
+        tree->root = tmp;
+    } else {
+        if (node == node->parent->left)
+            node->parent->left = tmp;
+        else
+            node->parent->right = tmp;
+    }
+
+    if (tmp != 0)
+        tmp->parent = node->parent;
+    
     node->right = tmp->left;
+
+    if (tmp->left != 0)
+        tmp->left->parent = node;
+
     tmp->left = node;
-    tmp->color = node->color;
-    node->color = Red;
+    node->parent = tmp;
     tree->current = tmp;
     
     stack_pop(context->code_stack, &context->next);
@@ -143,11 +215,27 @@
 
 __code rotateRight(struct Context* context, struct Node* node, struct Tree* tree) {
     struct Node* tmp = node->left;
+
+    if (node->parent == 0) {
+        tree->root = tmp;
+    } else {
+        if (node == node->parent->left)
+            node->parent->left = tmp;
+        else
+            node->parent->right = tmp;
+    }
+
+    if (tmp != 0)
+        tmp->parent = node->parent;
+
     node->left = tmp->right;
+
+    if (tmp->right != 0)
+        tmp->right->parent = node;
+    
     tmp->right = node;
-    tmp->color = node->color;
-    node->color = Red;
-    context->data[Tree]->tree.current = tmp;
+    node->parent = tmp;
+    tree->current = tmp;
     
     stack_pop(context->code_stack, &context->next);
     goto meta(context, context->next);
@@ -191,6 +279,11 @@
 }
 
 __code setRoot(struct Context* context, struct Tree* tree, struct Node* node) {
+    if(node->parent) {
+        tree->current = tree->current->parent;
+        goto meta(context, SetRoot);
+    }
+
     tree->root = node;
     tree->root->color = Black;
     tree->current = 0;
--- a/src/llrb/llrbContext.c	Tue Nov 17 16:59:48 2015 +0900
+++ b/src/llrb/llrbContext.c	Fri Nov 27 02:14:25 2015 +0900
@@ -22,6 +22,10 @@
 extern __code balance1_stub(struct Context*);
 extern __code balance2_stub(struct Context*);
 extern __code balance3_stub(struct Context*);
+extern __code balance4_stub(struct Context*);
+extern __code balance4_1_stub(struct Context*);
+extern __code balance4_2_stub(struct Context*);
+extern __code balance5_stub(struct Context*);
 extern __code setRoot_stub(struct Context*);
 extern __code get_stub(struct Context*);
 extern __code findMin_stub(struct Context*);
@@ -66,6 +70,10 @@
     context->code[Balance1]   = balance1_stub;
     context->code[Balance2]   = balance2_stub;
     context->code[Balance3]   = balance3_stub;
+    context->code[Balance4]   = balance4_stub;
+    context->code[Balance4_1] = balance4_1_stub;
+    context->code[Balance4_2] = balance4_2_stub;
+    context->code[Balance5]   = balance5_stub;
     context->code[SetRoot]    = setRoot_stub;
     context->code[Get]        = get_stub;
     context->code[Delete]     = delete_stub;
--- a/src/llrb/llrbContext.h	Tue Nov 17 16:59:48 2015 +0900
+++ b/src/llrb/llrbContext.h	Fri Nov 27 02:14:25 2015 +0900
@@ -27,6 +27,10 @@
     Balance1,
     Balance2,
     Balance3,
+    Balance4,
+    Balance4_1,
+    Balance4_2,
+    Balance5,
     Get,
     FindMin,
     Delete,
@@ -80,15 +84,18 @@
         int result;
     } tree;
     struct Node {
+        // need to tree
         enum Code next;
         int key; // comparable data segment
         int value;
+        struct Node* left;
+        struct Node* right;
+        // need to balancing
         enum Color {
             Red,
             Black,
         } color;
-        struct Node* left;
-        struct Node* right;
+        struct Node* parent;
     } node;
     struct Allocate {
         enum Code next;
--- a/src/llrb/main.c	Tue Nov 17 16:59:48 2015 +0900
+++ b/src/llrb/main.c	Fri Nov 27 02:14:25 2015 +0900
@@ -92,7 +92,7 @@
     
     context->next = Code5;
 
-    goto meta(context, Delete);
+    goto meta(context, Exit);
 }
 
 __code code5(struct Context* context) {