Mercurial > hg > GearsTemplate

changeset 42:44914699ee9b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
refactoring llrb
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Tue, 19 May 2015 05:06:25 +0900
parents 46917f503bce
children ec46ac3b0401
files doc/List.graffle src/llrb/llrb.c src/llrb/llrbContext.c src/llrb/llrbContext.h
diffstat 4 files changed, 83 insertions(+), 70 deletions(-) [+]
line wrap: on
line diff
Binary file doc/List.graffle has changed
--- a/src/llrb/llrb.c	Mon May 18 15:24:46 2015 +0900
+++ b/src/llrb/llrb.c	Tue May 19 05:06:25 2015 +0900
@@ -9,11 +9,6 @@
 
 #include "stack.h"
 
-#ifdef CLANG
-#define _CbC_retrun __return
-#define _CbC_environment __environment
-#endif
-
 #define NUM 100
 
 extern __code initLLRBContext(struct Context* context);
@@ -31,7 +26,7 @@
 static clock_t c1,c2;
 
 static stack_ptr pstack;
-static union Data* pre;
+static struct Node* pre;
 
 static double getTime() {
     struct timeval tv;
@@ -39,13 +34,13 @@
     return tv.tv_sec + (double)tv.tv_usec*1e-6;
 }
 
-void print_tree(union Data* data, int n) {
-    if (data != 0) {
-        print_tree(data->node.left, n+1);
+void print_tree(struct Node* node, int n) {
+    if (node != 0) {
+        print_tree(node->left, n+1);
         for (int i=0;i<n;i++)
             printf("  ");
-        printf("key=%d depth=%d\t%p\n", data->node.key, n, data);
-        print_tree(data->node.right, n+1);
+        printf("key=%d depth=%d\t%p\n", node->key, n, node);
+        print_tree(node->right, n+1);
     }
 }
 
@@ -61,13 +56,13 @@
 
 __code put(struct Context* context) {
     struct Tree* tree = &context->data[Tree]->tree;
+    context->data[Next]->next = context->data[Allocate]->allocate.next;
     
     if (tree->root == 0) {
-        struct Node* node = &context->data[Allocate]->allocate.node;
+        struct Node* node = &context->data[Node]->node;
         node->color = Black;
         node->left = 0;
         node->right = 0;
-
         context->data[Allocate]->allocate.next = InitNode;
         goto meta(context, Allocator);
     }
@@ -80,8 +75,8 @@
 
 __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;
+    struct Node* persistentNode = tree->current;
 
     int result = context->data[Tree]->tree.result;
 
@@ -98,8 +93,8 @@
         node->left = context->heap;
     }
 
-    if (context->data[Tree]->tree.current == 0) {
-        stack_pop(pstack, &context->data[Tree]->tree.current);
+    if (tree->current == 0) {
+        stack_pop(pstack, &tree->current);
         context->data[Allocate]->allocate.next = InitNode;
         goto meta(context, Allocator);
     }
@@ -110,24 +105,24 @@
 
 __code initNode(struct Context* context) {
     struct Node* node = &context->data[context->dataNum]->node;
-    struct Node* temporalNode = &context->data[Allocate]->allocate.node;
+    struct Node* temporalNode = &context->data[Node]->node;
     struct Tree* tree = &context->data[Tree]->tree;
 
     temporalNode->color = Red;
     *node = *temporalNode;
 
     if (tree->root == 0) {
-        tree->root = context->data[context->dataNum];
-        goto meta(context, context->data[Allocate]->allocate.after_put);
+        node->color = Black;
+        tree->root = node;
+        goto meta(context, context->data[Next]->next);
     }
 
-    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;
+    int persistentKey = context->data[Tree]->tree.current->key;
+    int temporalKey = context->data[Node]->node.key;
     
     struct Tree* tree = &context->data[Tree]->tree;
 
@@ -150,15 +145,15 @@
 }
 
 __code rotateLeft(struct Context* context) {
-    struct Node* node = &context->data[Tree]->tree.current->node;
-
+    struct Node* node = context->data[Tree]->tree.current;
+    
     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;
+        if (node->right->color == Red) {
+            struct Node* tmp = node->right;
+            node->right = tmp->left;
+            tmp->left = node;
+            tmp->color = tmp->left->color;
+            tmp->left->color = Red;
             context->data[Tree]->tree.current = tmp;
         }
     }
@@ -167,16 +162,16 @@
 }
     
 __code rotateRight(struct Context* context) {
-    struct Node* node = &context->data[Tree]->tree.current->node;
+    struct Node* node = context->data[Tree]->tree.current;
 
     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;
+        if (node->left->left != 0) {
+            if (node->left->color == Red && node->left->left->color == Red) {
+                struct Node* tmp = node->left;
+                node->left = tmp->right;
+                tmp->right = node;
+                tmp->color = tmp->right->color;
+                tmp->right->color = Red;
                 context->data[Tree]->tree.current = tmp;
             }
         }
@@ -186,13 +181,13 @@
 }
 
 __code colorFlip(struct Context* context) {
-    struct Node* node = &context->data[Tree]->tree.current->node;
+    struct Node* node = context->data[Tree]->tree.current;
     
     if (node->right != 0 && node->left != 0) {
-        if (node->right->node.color == Red && node->left->node.color == Red) {
+        if (node->right->color == Red && node->left->color == Red) {
             node->color ^= 1;
-            node->left->node.color ^= 1;
-            node->right->node.color ^= 1;
+            node->left->color ^= 1;
+            node->right->color ^= 1;
         }
     }
     
@@ -201,23 +196,24 @@
 
 __code fixUp(struct Context* context) {
     struct Allocate* allocate = &context->data[Allocate]->allocate;
-    struct Node* node = &context->data[Tree]->tree.current->node;
+    struct Node* node = context->data[Tree]->tree.current;
 
     allocate->next = ChangeRef;
-    allocate->node.key = node->key;
-    context->data[Tree]->tree.prev = context->data[Tree]->tree.current;
+
+    context->data[Node]->node.key = node->key;
+    context->data[Tree]->tree.prev = node;
     
     if (stack_pop(pstack, &context->data[Tree]->tree.current) == 0) {
         goto meta(context, Compare);
     }
     
-    context->data[Tree]->tree.root = context->data[Tree]->tree.current;
+    context->data[Tree]->tree.root = node;
     
-    goto meta(context, context->data[Allocate]->allocate.after_put);
+    goto meta(context, context->data[Next]->next);
 }    
 
 __code changeReference(struct Context* context) {
-    struct Node* node = &context->data[Tree]->tree.current->node;
+    struct Node* node = context->data[Tree]->tree.current;
     int result = context->data[Tree]->tree.result;
     
     if (result == 1) {
@@ -239,39 +235,47 @@
 */
 
 __code code2(struct Context* context) {
-    context->data[2]->count = 1;
+    context->data[4]->count = 1;
     goto meta(context, Code3);
 }
 
 __code code3(struct Context* context) {
     struct Allocate* allocate = &context->data[Allocate]->allocate;
-    long loop = context->data[2]->count;
+    struct Node* node = &context->data[Node]->node;
+    long loop = context->data[4]->count;
+
     if (loop == num) {
         goto meta(context, Code4);
     }
+
     allocate->size = sizeof(struct Node);
-    allocate->after_put = Code3;
-    allocate->node.key = loop;
-    allocate->node.value = loop;
+    allocate->next = Code3;
+
+    node->key = loop;
+    node->value = loop;
     
-    context->data[2]->count++;
+    context->data[4]->count++;
     goto meta(context, Put);
 }
 
 __code code4(struct Context* context) {
     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 = 0;
-    context->data[Allocate]->allocate.node.value = 0;
+    
+    struct Allocate* allocate = &context->data[Allocate]->allocate;
+    allocate->size = sizeof(struct Node);
+    allocate->next = Code5;
+
+    struct Node* node = &context->data[Node]->node;
+    node->key = 0;
+    node->value = 0;
     
     goto meta(context, Put);
 }
 
 __code code5(struct Context* context) {
-    puts("---prev---");
+    puts("---before---");
     print_tree(pre, 0);
-    puts("---follow---");
+    puts("---after---");
     print_tree(context->data[Tree]->tree.root, 0);
     puts("--Number of Data--");
     printf("%d\n", context->dataNum);
--- a/src/llrb/llrbContext.c	Mon May 18 15:24:46 2015 +0900
+++ b/src/llrb/llrbContext.c	Tue May 19 05:06:25 2015 +0900
@@ -54,8 +54,16 @@
     context->data[Tree] = context->heap;
     context->heap += sizeof(struct Tree);
 
-    context->dataNum = Tree;
+    context->data[Node] = context->heap;
+    context->heap += sizeof(struct Node);
+
+    context->data[Next] = context->heap;
+    context->heap += sizeof(enum Code);
 
-    context->root = 0;
-    context->current = 0;
+    context->dataNum = Next;
+    
+    struct Tree* tree = &context->data[Tree]->tree;
+    tree->root = 0;
+    tree->current = 0;
+    tree->prev = 0;
 }
--- a/src/llrb/llrbContext.h	Mon May 18 15:24:46 2015 +0900
+++ b/src/llrb/llrbContext.h	Tue May 19 05:06:25 2015 +0900
@@ -25,6 +25,8 @@
 enum UniqueData {
     Allocate,
     Tree,
+    Node,
+    Next,
 };
 
 struct Context {
@@ -41,10 +43,11 @@
 
 union Data {
     long count;
+    enum Code next;
     struct Tree {
-        union Data* root;
-        union Data* current;
-        union Data* prev;
+        struct Node* root;
+        struct Node* current;
+        struct Node* prev;
         int result;
     } tree;
     struct Node {
@@ -54,13 +57,11 @@
             Red,
             Black,
         } color;
-        union Data* left;
-        union Data* right;
+        struct Node* left;
+        struct Node* right;
     } node;
     struct Allocate {
         long size;
         enum Code next;
-        enum Code after_put;
-        struct Node node;
     } allocate;
 };