changeset 27:44879c87c2dc

modify
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Fri, 01 May 2015 18:18:36 +0900
parents 06fcbe45e85c
children fa3038ae40ad
files src/llrb/llrb.c src/llrb/llrbContext.c src/llrb/llrbContext.h
diffstat 3 files changed, 35 insertions(+), 37 deletions(-) [+]
line wrap: on
line diff
--- a/src/llrb/llrb.c	Fri May 01 13:40:11 2015 +0900
+++ b/src/llrb/llrb.c	Fri May 01 18:18:36 2015 +0900
@@ -152,11 +152,6 @@
 
 __code rotateLeft(struct Context* context) {
     struct Node* node = &context->data[Tree]->tree.current->node;
-    struct Allocate* allocate = &context->data[Allocate]->allocate;
-    
-    allocate->next = ChangeRef;
-    allocate->node.key = node->key;
-    allocate->node.key = node->key;
 
     if (node->right != 0) {
         if (node->right->node.color == Red) {
@@ -190,9 +185,10 @@
 
     goto meta(context, ColorFlip);
 }
+
 __code colorFlip(struct Context* context) {
     struct Node* node = &context->data[Tree]->tree.current->node;
-
+    
     if (node->right != 0 && node->left != 0) {
         if (node->right->node.color == Red && node->left->node.color == Red) {
             node->color ^= 1;
@@ -201,33 +197,42 @@
         }
     }
     
-    goto meta(context, Compare);
+    goto meta(context, FixUp);
 }
 
-__code changeReference(struct Context* context) {
-    union Data* data = context->data[Tree]->tree.current;
+__code fixUp(struct Context* context) {
+    struct Allocate* allocate = &context->data[Allocate]->allocate;
+    struct Node* node = &context->data[Tree]->tree.current->node;
+
+    allocate->next = ChangeRef;
+    allocate->node.key = node->key;
+    allocate->node.key = node->key;
+    context->data[Tree]->tree.prev = context->data[Tree]->tree.current;
     
     if (stack_pop(pstack, &context->data[Tree]->tree.current) == 0) {
-        struct Node* node = &context->data[Tree]->tree.current->node;
-        
-        switch (context->data[Tree]->tree.result) {
-        case 1:
-            node->left = data;
-            break;
-        default:
-            node->right = data;
-            break;
-        }
-
-        goto meta(context, RotateL);
+        goto meta(context, Compare);
     }
-
+    
     context->data[Tree]->tree.root = context->data[Tree]->tree.current;
     
     goto meta(context, context->data[Allocate]->allocate.after_put);
+}    
+
+__code changeReference(struct Context* context) {
+    struct Node* node = &context->data[Tree]->tree.current->node;
+    
+    switch (context->data[Tree]->tree.result) {
+    case 1:
+        node->left = context->data[Tree]->tree.prev;
+        break;
+    default:
+        node->right = context->data[Tree]->tree.prev;
+        break;
+    }
+    
+    goto meta(context, RotateL);
 }
 
-
 /*
 __code code2(Allocate allocate, Count count) {
     count.count = 0;
@@ -236,7 +241,7 @@
 */
 
 __code code2(struct Context* context) {
-    context->data[2]->count = 0;
+    context->data[2]->count = 1;
     goto meta(context, Code3);
 }
 
@@ -259,8 +264,8 @@
     pre = context->data[Tree]->tree.root;
     context->data[Allocate]->allocate.size = sizeof(struct Node);
     context->data[Allocate]->allocate.after_put = Code5;
-    context->data[Allocate]->allocate.node.key = num;
-    context->data[Allocate]->allocate.node.value = num;
+    context->data[Allocate]->allocate.node.key = 0;
+    context->data[Allocate]->allocate.node.value = 0;
     
     goto meta(context, Put);
 }
--- a/src/llrb/llrbContext.c	Fri May 01 13:40:11 2015 +0900
+++ b/src/llrb/llrbContext.c	Fri May 01 18:18:36 2015 +0900
@@ -17,6 +17,7 @@
 extern __code rotateLeft(struct Context*);
 extern __code rotateRight(struct Context*);
 extern __code colorFlip(struct Context*);
+extern __code fixUp(struct Context*);
 extern __code changeReference(struct Context*);
 extern __code exit_code(struct Context*);
 
@@ -41,6 +42,7 @@
     context->code[RotateL]   = rotateLeft;
     context->code[RotateR]   = rotateRight;
     context->code[ColorFlip] = colorFlip;
+    context->code[FixUp]     = fixUp;
     context->code[ChangeRef] = changeReference;
     context->code[Exit]      = exit_code;
     
--- a/src/llrb/llrbContext.h	Fri May 01 13:40:11 2015 +0900
+++ b/src/llrb/llrbContext.h	Fri May 01 18:18:36 2015 +0900
@@ -17,6 +17,7 @@
     RotateL,
     RotateR,
     ColorFlip,
+    FixUp,
     ChangeRef,
     Exit,
 };
@@ -43,19 +44,9 @@
     struct Tree {
         union Data* root;
         union Data* current;
+        union Data* prev;
         int result;
     } tree;
-    /* struct _Node { */
-    /*     int key; */
-    /*     int value; */
-    /*     enum Color { */
-    /*         Red, */
-    /*         Black, */
-    /*     } color; */
-    /*     union Data* parent; */
-    /*     union Data* left; */
-    /*     union Data* right; */
-    /* } _node; */
     struct Node {
         int key;
         int value;