Mercurial > hg > GearsTemplate

changeset 24:7494c0b87ec4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
implement insert of Non Destructive llrb
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Fri, 01 May 2015 05:20:47 +0900
parents 868c2918b634
children 390cf0523ea7
files src/llrb/llrb.c src/llrb/llrbContext.c src/llrb/llrbContext.h
diffstat 3 files changed, 152 insertions(+), 151 deletions(-) [+]
line wrap: on
line diff
--- a/src/llrb/llrb.c	Thu Apr 30 19:07:23 2015 +0900
+++ b/src/llrb/llrb.c	Fri May 01 05:20:47 2015 +0900
@@ -7,6 +7,8 @@
 #include "allocate.h"
 #include "origin_cs.h"
 
+#include "stack.h"
+
 #ifdef CLANG
 #define _CbC_retrun __return
 #define _CbC_environment __environment
@@ -15,9 +17,7 @@
 #define NUM 100
 
 extern __code initLLRBContext(struct Context* context);
-void colorFlip(struct Context*);
-void rotateLeft(struct Context*);
-void rotateRight(struct Context*);
+
 /* 
 __code code1(Allocate allocate) {
     allocate.size = sizeof(long);
@@ -30,6 +30,9 @@
 static int num;
 static clock_t c1,c2;
 
+static stack_ptr pstack;
+static union Data* pre;
+
 static double getTime() {
     struct timeval tv;
     gettimeofday(&tv, NULL);
@@ -41,7 +44,7 @@
         print_tree(data->node.left, n+1);
         for (int i=0;i<n;i++)
             printf("  ");
-        printf("key=%d depth=%d\n", data->node.key, n);
+        printf("key=%d depth=%d\t%p\n", data->node.key, n, data);
         print_tree(data->node.right, n+1);
     }
 }
@@ -69,29 +72,64 @@
         goto meta(context, Allocator);
     }
 
+    context->data[Allocate]->allocate.next = Insert;
     tree->current = tree->root;
+
+    goto meta(context, Compare);
+}
+
+__code clone(struct Context* context) {
+    struct Node* node = &context->data[context->dataNum]->node;
+    struct Node* persistentNode = &context->data[Tree]->tree.current->node;
+    struct Tree* tree = &context->data[Tree]->tree;
+
+    *node = *persistentNode;
+
+    switch (context->data[Tree]->tree.result) {
+    case 0:
+        stack_pop(pstack, &tree->current);
+        goto meta(context, RotateL);
+    case 1:
+        tree->current = persistentNode->right;
+        node->right = context->heap;
+        break;
+    default:
+        tree->current = persistentNode->left;
+        node->left = context->heap;
+        break;
+    }
+
+    if (context->data[Tree]->tree.current == 0) {
+        stack_pop(pstack, &context->data[Tree]->tree.current);
+        context->data[Allocate]->allocate.next = InitNode;
+        goto meta(context, Allocator);
+    }
+    
+    context->data[Allocate]->allocate.next = Insert;
     goto meta(context, Compare);
 }
 
 __code initNode(struct Context* context) {
-    struct Node* persistentNode = &context->data[context->dataNum]->node;
+    struct Node* node = &context->data[context->dataNum]->node;
     struct Node* temporalNode = &context->data[Allocate]->allocate.node;
-
     struct Tree* tree = &context->data[Tree]->tree;
 
-    *persistentNode = *temporalNode;
+    temporalNode->color = Red;
+    *node = *temporalNode;
 
-    if (tree->root == 0 || tree->result == 0) {
+    if (tree->root == 0) {
         tree->root = context->data[context->dataNum];
         goto meta(context, context->data[Allocate]->allocate.after_put);
     }
 
+    context->data[Allocate]->allocate.next = Insert;
+    goto meta(context, RotateL);
 }
 
 __code compare(struct Context* context) {
     int persistentKey = context->data[Tree]->tree.current->node.key;
     int temporalKey = context->data[Allocate]->allocate.node.key;
-
+    
     struct Tree* tree = &context->data[Tree]->tree;
 
     if (persistentKey == temporalKey) {
@@ -102,145 +140,93 @@
         tree->result = -1;
     }
 
-    goto meta(context, Insert);
+    goto meta(context, context->data[Allocate]->allocate.next);
 }
         
 __code insert(struct Context* context) {
-    struct Node* persistentNode = &context->data[Tree]->tree.current->node;
-    struct Node* temporalNode = &context->data[Allocate]->allocate.node;
-
-    struct Tree* tree = &context->data[Tree]->tree;
+    stack_push(pstack, &context->heap);
 
-    switch (context->data[Tree]->tree.result) {
-    case 0:
-        temporalNode->right = persistentNode->right;
-        temporalNode->left = persistentNode->left;
-        temporalNode->color = persistentNode->color;
-
-        context->data[Allocate]->allocate.next = InitNode;
-        goto meta(context, Allocator);
-    case 1:
-        tree->current = persistentNode->right;
-        goto meta(context, Compare);
-    case -1:
-        tree->current = persistentNode->left;
-        goto meta(context, Compare);
-    }
+    context->data[Allocate]->allocate.next = Clone;
+    goto meta(context, Allocator);
 }
-/* __code put(struct Context* context) { */
-/*     context->data[context->dataNum]->node.key = context->data[0]->allocate.key; */
-/*     context->data[context->dataNum]->node.value = context->data[0]->allocate.value; */
-/*     if (context->root == 0) { */
-/*         context->root = context->data[context->dataNum]; */
-/*         context->root->node.color = Black; */
-/*         context->root->node.parent = 0; */
-/*         goto meta(context, context->data[0]->allocate.after_put); */
-/*     } */
-/*     context->data[context->dataNum]->node.color = Red; */
-/*     context->current = context->root; */
-/*     goto meta(context, InsertD); */
-/* } */
 
-/* __code insertDown(struct Context* context) { */
-/*     int persistentKey = context->current->node.key; */
-/*     int temporalKey = context->data[context->dataNum]->node.key; */
+__code rotateLeft(struct Context* context) {
+    struct Node* node = &context->data[Tree]->tree.current->node;
+    struct Allocate* allocate = &context->data[Allocate]->allocate;
     
-/*     if (context->current->node.right != 0 && context->current->node.left != 0) { */
-/*         if (context->current->node.right->node.color == Red && context->current->node.left->node.color == Red) { */
-/*             colorFlip(context); */
-/*         } */
-/*     } */
+    allocate->next = ChangeRef;
+    allocate->node.key = node->key;
+    allocate->node.key = node->key;
+
+    if (node->right != 0) {
+        if (node->right->node.color == Red) {
+            union Data* tmp = context->data[Tree]->tree.current->node.right;
+            context->data[Tree]->tree.current->node.right = tmp->node.left;
+            tmp->node.left = context->data[Tree]->tree.current;
+            tmp->node.color = tmp->node.left->node.color;
+            tmp->node.left->node.color = Red;
+            context->data[Tree]->tree.current = tmp;
+        }
+    }
     
-/*     if (persistentKey == temporalKey) { */
-/*         context->current->node.value = context->data[context->dataNum]->node.value; */
-/*         goto meta(context, context->data[0]->allocate.after_put); */
-/*     } else if (temporalKey < persistentKey) { */
-/*         if (context->current->node.left == 0) { */
-/*             context->current->node.left = context->data[context->dataNum]; */
-/*         } else { */
-/*             context->current = context->current->node.left; */
-/*             goto meta(context, InsertD); */
-/*         } */
-/*     } else { */
-/*         if (context->current->node.right == 0) { */
-/*             context->current->node.right = context->data[context->dataNum]; */
-/*         } else { */
-/*             context->current = context->current->node.right; */
-/*             goto meta(context, InsertD); */
-/*         } */
-/*     } */
-
-/*     context->data[context->dataNum]->node.parent = context->current; */
+    goto meta(context, RotateR);
+}
     
-/*     goto meta(context, InsertU); */
-/* } */
-
-/* __code insertUp(struct Context* context) { */
-/*     if (context->current->node.right != 0) { */
-/*         if (context->current->node.right->node.color == Red) { */
-/*             rotateLeft(context); */
-/*         } */
-/*     } */
+__code rotateRight(struct Context* context) {
+    struct Node* node = &context->data[Tree]->tree.current->node;
 
-/*     if (context->current->node.left != 0) { */
-/*         if (context->current->node.left->node.left != 0) { */
-/*             if (context->current->node.left->node.color == Red && context->current->node.left->node.left->node.color == Red) { */
-/*                 rotateRight(context); */
-/*             } */
-/*         } */
-/*     } */
+    if (node->left != 0) {
+        if (node->left->node.left != 0) {
+            if (node->left->node.color == Red && node->left->node.left->node.color == Red) {
+                union Data* tmp = context->data[Tree]->tree.current->node.left;
+                context->data[Tree]->tree.current->node.left = tmp->node.right;
+                tmp->node.right = context->data[Tree]->tree.current;
+                tmp->node.color = tmp->node.right->node.color;
+                tmp->node.right->node.color = Red;
+                context->data[Tree]->tree.current = tmp;
+            }
+        }
+    }
 
-/*     if (context->current->node.right != 0 && context->current->node.left != 0) { */
-/*         if (context->current->node.right->node.color == Red && context->current->node.left->node.color == Red) { */
-/*             colorFlip(context); */
-/*         } */
-/*     }     */
-    
-/*     if (context->current->node.parent == 0) { */
-/*         context->root = context->current; */
-/*         context->root->node.color = Black; */
-/*         goto meta(context, context->data[0]->allocate.after_put); */
-/*     } */
+    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;
+            node->left->node.color ^= 1;
+            node->right->node.color ^= 1;
+        }
+    }
     
-/*     if (context->current->node.parent != 0) { */
-/*         if (context->current->node.parent->node.key < context->current->node.key) { */
-/*             context->current->node.parent->node.right = context->current; */
-/*         } else { */
-/*             context->current->node.parent->node.left = context->current; */
-/*         } */
-/*     } */
-    
-/*     context->current = context->current->node.parent; */
-/*     goto meta(context, InsertU); */
-/* } */
+    goto meta(context, Compare);
+}
 
-/* void rotateLeft(struct Context* context) { */
-/*     union Data* tmp = context->current->node.right; */
-/*     context->current->node.right = tmp->node.left; */
-/*     tmp->node.left = context->current; */
-/*     tmp->node.color = tmp->node.left->node.color; */
-/*     tmp->node.parent = tmp->node.left->node.parent; */
-/*     tmp->node.left->node.color = Red; */
-/*     tmp->node.left->node.parent = tmp; */
-/*     context->current = tmp; */
-/* } */
+__code changeReference(struct Context* context) {
+    union Data* data = 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;
+        }
 
-/* void rotateRight(struct Context* context) { */
-/*     union Data* tmp = context->current->node.left; */
-/*     context->current->node.left = tmp->node.right; */
-/*     tmp->node.right = context->current; */
-/*     tmp->node.color = tmp->node.right->node.color; */
-/*     tmp->node.parent = tmp->node.right->node.parent; */
-/*     tmp->node.right->node.color = Red; */
-/*     tmp->node.right->node.parent = tmp; */
-/*     context->current = tmp; */
-/* } */
+        goto meta(context, RotateL);
+    }
 
-/* void colorFlip(struct Context* context) { */
-/*     context->current->node.color ^= 1; */
-/*     context->current->node.left->node.color ^= 1; */
-/*     context->current->node.right->node.color ^= 1; */
-/* } */
+    context->data[Tree]->tree.root = context->data[Tree]->tree.current;
+    
+    goto meta(context, context->data[Allocate]->allocate.after_put);
+}
+
 
 /*
 __code code2(Allocate allocate, Count count) {
@@ -255,37 +241,43 @@
 }
 
 __code code3(struct Context* context) {
-    if (context->data[2]->count == num) {
+    struct Allocate* allocate = &context->data[Allocate]->allocate;
+    long loop = context->data[2]->count;
+    if (loop == num) {
         goto meta(context, Code4);
     }
-    context->data[Allocate]->allocate.size = sizeof(struct Node);
-    context->data[Allocate]->allocate.after_put = Code3;
-    context->data[Allocate]->allocate.node.key = context->data[2]->count;
-    context->data[Allocate]->allocate.node.value = context->data[2]->count;
+    allocate->size = sizeof(struct Node);
+    allocate->after_put = Code3;
+    allocate->node.key = loop;
+    allocate->node.value = loop;
+    
     context->data[2]->count++;
     goto meta(context, Put);
 }
 
 __code code4(struct Context* context) {
-    c1 = clock();
+    pre = context->data[Tree]->tree.root;
     context->data[Allocate]->allocate.size = sizeof(struct Node);
-    context->data[Allocate]->allocate.next = Put;
     context->data[Allocate]->allocate.after_put = Code5;
-    context->data[Allocate]->allocate.node.key = num+1;
-    context->data[Allocate]->allocate.node.value = num+1;
-
-    goto meta(context, Allocator);
+    context->data[Allocate]->allocate.node.key = num;
+    context->data[Allocate]->allocate.node.value = num;
+    
+    goto meta(context, Put);
 }
 
 __code code5(struct Context* context) {
     c2 = clock();
     //printf("%ld %ld\n", context->data[1]->count-1, (long)c2-c1);
-    print_tree(context->root, 0);
+    puts("---prev---");
+    print_tree(pre, 0);
+    puts("---follow---");
+    print_tree(context->data[Tree]->tree.root, 0);
     goto meta(context, Exit);
 }
 
 int main(int argc, char** argv) {
     num = (int)atoi(argv[1]);
+    pstack = stack_init(sizeof(union Data*), num/2);
     struct Context* context = (struct Context*)malloc(sizeof(struct Context));
     initLLRBContext(context);
     goto start_code(context, Code1);
--- a/src/llrb/llrbContext.c	Thu Apr 30 19:07:23 2015 +0900
+++ b/src/llrb/llrbContext.c	Fri May 01 05:20:47 2015 +0900
@@ -10,11 +10,14 @@
 extern __code meta(struct Context*);
 extern __code allocate(struct Context*);
 extern __code put(struct Context*);
+extern __code clone(struct Context*);
 extern __code initNode(struct Context*);
 extern __code compare(struct Context*);
 extern __code insert(struct Context*);
-extern __code insertDown(struct Context*);
-extern __code insertUp(struct Context*);
+extern __code rotateLeft(struct Context*);
+extern __code rotateRight(struct Context*);
+extern __code colorFlip(struct Context*);
+extern __code changeReference(struct Context*);
 extern __code exit_code(struct Context*);
 
 __code initLLRBContext(struct Context* context) {
@@ -31,11 +34,14 @@
     context->code[Code5]     = code5;
     context->code[Allocator] = allocate;
     context->code[Put]       = put;
+    context->code[Clone]     = clone;
     context->code[InitNode]  = initNode;
     context->code[Compare]   = compare;
     context->code[Insert]    = insert;
-    /* context->code[InsertD]  = insertDown; */
-    /* context->code[InsertU]  = insertUp; */
+    context->code[RotateL]   = rotateLeft;
+    context->code[RotateR]   = rotateRight;
+    context->code[ColorFlip] = colorFlip;
+    context->code[ChangeRef] = changeReference;
     context->code[Exit]      = exit_code;
     
     context->heap = context->heap_start;
--- a/src/llrb/llrbContext.h	Thu Apr 30 19:07:23 2015 +0900
+++ b/src/llrb/llrbContext.h	Fri May 01 05:20:47 2015 +0900
@@ -10,11 +10,14 @@
     Code5,
     Allocator,
     Put,
+    Clone,
     InitNode,
     Compare,
     Insert,
-    InsertD,
-    InsertU,
+    RotateL,
+    RotateR,
+    ColorFlip,
+    ChangeRef,
     Exit,
 };