Mercurial > hg > Members > innparusu > Gears

changeset 23:868c2918b634

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Non Destructive llrb
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Thu, 30 Apr 2015 19:07:23 +0900
parents 4c3c0ad4a75d
children 7494c0b87ec4
files src/include/allocate.h src/include/origin_cs.h src/llrb/llrb.c src/llrb/llrbContext.c src/llrb/llrbContext.h
diffstat 5 files changed, 260 insertions(+), 146 deletions(-) [+]
line wrap: on
line diff
--- a/src/include/allocate.h	Tue Apr 28 17:39:44 2015 +0900
+++ b/src/include/allocate.h	Thu Apr 30 19:07:23 2015 +0900
@@ -7,7 +7,7 @@
 }
 
 __code meta_allocate(struct Context* context) {
-    context->data[++context->dataSize] = context->heap;
+    context->data[++context->dataNum] = context->heap;
     context->heap += context->data[0]->allocate.size;
     goto (context->code[context->data[0]->allocate.next])(context);
 }
--- a/src/include/origin_cs.h	Tue Apr 28 17:39:44 2015 +0900
+++ b/src/include/origin_cs.h	Thu Apr 30 19:07:23 2015 +0900
@@ -6,5 +6,8 @@
 }
 
 __code exit_code(struct Context* context) {
+    free(context->code);
+    free(context->data);
+    free(context->heap_start);
     goto exit(0);
 }
--- a/src/llrb/llrb.c	Tue Apr 28 17:39:44 2015 +0900
+++ b/src/llrb/llrb.c	Thu Apr 30 19:07:23 2015 +0900
@@ -13,7 +13,6 @@
 #endif
 
 #define NUM 100
-#define ALLOCATE_SIZE 1000000000
 
 extern __code initLLRBContext(struct Context* context);
 void colorFlip(struct Context*);
@@ -29,6 +28,7 @@
 static double st_time;
 static double ed_time;
 static int num;
+static clock_t c1,c2;
 
 static double getTime() {
     struct timeval tv;
@@ -41,15 +41,15 @@
         print_tree(data->node.left, n+1);
         for (int i=0;i<n;i++)
             printf("  ");
-        printf("key=%d\n", data->node.key);
+        printf("key=%d depth=%d\n", data->node.key, n);
         print_tree(data->node.right, n+1);
     }
 }
 
 __code code1(struct Context* context) {
-    context->data[0]->allocate.size = sizeof(long);
-    context->data[0]->allocate.next = Code2;
-    goto meta(context, Allocate);
+    context->data[Allocate]->allocate.size = sizeof(long);
+    context->data[Allocate]->allocate.next = Code2;
+    goto meta(context, Allocator);
 }
 
 __code meta(struct Context* context, enum Code next) {
@@ -57,119 +57,190 @@
 }
 
 __code put(struct Context* context) {
-    context->data[context->dataSize]->node.key = context->data[0]->allocate.key;
-    context->data[context->dataSize]->node.value = context->data[0]->allocate.value;
-    if (context->root == 0) {
-        context->root = context->data[context->dataSize];
-        context->root->node.color = Black;
-        context->root->node.parent = 0;
-        goto meta(context, context->data[0]->allocate.after_put);
+    struct Tree* tree = &context->data[Tree]->tree;
+    
+    if (tree->root == 0) {
+        struct Node* node = &context->data[Allocate]->allocate.node;
+        node->color = Black;
+        node->left = 0;
+        node->right = 0;
+
+        context->data[Allocate]->allocate.next = InitNode;
+        goto meta(context, Allocator);
     }
-    context->data[context->dataSize]->node.color = Red;
-    context->current = context->root;
-    goto meta(context, InsertD);
+
+    tree->current = tree->root;
+    goto meta(context, Compare);
 }
 
-__code insertDown(struct Context* context) {
-    int persistentKey = context->current->node.key;
-    int temporalKey = context->data[context->dataSize]->node.key;
-    
-    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 (persistentKey == temporalKey) {
-        context->current->node.value = context->data[context->dataSize]->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->dataSize];
-        } 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->dataSize];
-        } else {
-            context->current = context->current->node.right;
-            goto meta(context, InsertD);
-        }
+__code initNode(struct Context* context) {
+    struct Node* persistentNode = &context->data[context->dataNum]->node;
+    struct Node* temporalNode = &context->data[Allocate]->allocate.node;
+
+    struct Tree* tree = &context->data[Tree]->tree;
+
+    *persistentNode = *temporalNode;
+
+    if (tree->root == 0 || tree->result == 0) {
+        tree->root = context->data[context->dataNum];
+        goto meta(context, context->data[Allocate]->allocate.after_put);
     }
 
-    context->data[context->dataSize]->node.parent = context->current;
-    
-    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 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) {
+        tree->result = 0;
+    } else if (persistentKey < temporalKey) {
+        tree->result = 1;
+    } else {
+        tree->result = -1;
     }
 
-    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);
-            }
-        }
+    goto meta(context, Insert);
+}
+        
+__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;
+
+    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);
     }
+}
+/* __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); */
+/* } */
 
-    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);
-        }
-    }    
+/* __code insertDown(struct Context* context) { */
+/*     int persistentKey = context->current->node.key; */
+/*     int temporalKey = context->data[context->dataNum]->node.key; */
     
-    if (context->current->node.parent == 0) {
-        context->root = context->current;
-        context->root->node.color = Black;
-        goto meta(context, context->data[0]->allocate.after_put);
-    }
+/*     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) {
-        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;
-        }
-    }
+/*     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; */
     
-    context->current = context->current->node.parent;
-    goto meta(context, InsertU);
-}
+/*     goto meta(context, InsertU); */
+/* } */
 
-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 insertUp(struct Context* context) { */
+/*     if (context->current->node.right != 0) { */
+/*         if (context->current->node.right->node.color == Red) { */
+/*             rotateLeft(context); */
+/*         } */
+/*     } */
+
+/*     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); */
+/*             } */
+/*         } */
+/*     } */
 
-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;
-}
+/*     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); */
+/*     } */
+    
+/*     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); */
+/* } */
 
-void colorFlip(struct Context* context) {
-    context->current->node.color ^= 1;
-    context->current->node.left->node.color ^= 1;
-    context->current->node.right->node.color ^= 1;
-}
+/* 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; */
+/* } */
+
+/* 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; */
+/* } */
+
+/* void colorFlip(struct Context* context) { */
+/*     context->current->node.color ^= 1; */
+/*     context->current->node.left->node.color ^= 1; */
+/*     context->current->node.right->node.color ^= 1; */
+/* } */
 
 /*
 __code code2(Allocate allocate, Count count) {
@@ -179,37 +250,36 @@
 */
 
 __code code2(struct Context* context) {
-    context->data[1]->count = 0;
+    context->data[2]->count = 0;
     goto meta(context, Code3);
 }
 
 __code code3(struct Context* context) {
-    if (context->data[1]->count == num) {
+    if (context->data[2]->count == num) {
         goto meta(context, Code4);
     }
-    context->data[0]->allocate.size = sizeof(struct Node);
-    context->data[0]->allocate.next = Put;
-    context->data[0]->allocate.after_put = Code3;
-    context->data[0]->allocate.key = context->data[1]->count;
-    context->data[0]->allocate.value = context->data[1]->count;
-    context->data[1]->count++;
-    goto meta(context, Allocate);
+    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;
+    context->data[2]->count++;
+    goto meta(context, Put);
 }
 
 __code code4(struct Context* context) {
-    st_time = getTime();
-    context->data[0]->allocate.size = sizeof(struct Node);
-    context->data[0]->allocate.next = Put;
-    context->data[0]->allocate.after_put = Code5;
-    context->data[0]->allocate.key = num+1;
-    context->data[0]->allocate.value = num+1;
+    c1 = clock();
+    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, Allocate);
+    goto meta(context, Allocator);
 }
 
 __code code5(struct Context* context) {
-    ed_time = getTime();
-    //    printf("%ld %0.12f\n", context->data[1]->count-1, ed_time-st_time);
+    c2 = clock();
+    //printf("%ld %ld\n", context->data[1]->count-1, (long)c2-c1);
     print_tree(context->root, 0);
     goto meta(context, Exit);
 }
@@ -217,9 +287,6 @@
 int main(int argc, char** argv) {
     num = (int)atoi(argv[1]);
     struct Context* context = (struct Context*)malloc(sizeof(struct Context));
-    context->code = malloc(sizeof(__code*)*ALLOCATE_SIZE);
-    context->data = malloc(sizeof(union Data**)*ALLOCATE_SIZE);
-    context->heap = malloc(sizeof(union Data*)*ALLOCATE_SIZE);
     initLLRBContext(context);
     goto start_code(context, Code1);
 }
--- a/src/llrb/llrbContext.c	Tue Apr 28 17:39:44 2015 +0900
+++ b/src/llrb/llrbContext.c	Thu Apr 30 19:07:23 2015 +0900
@@ -1,4 +1,7 @@
+#include <stdlib.h>
+
 #include "llrbContext.h"
+
 extern __code code1(struct Context*);
 extern __code code2(struct Context*);
 extern __code code3(struct Context*);
@@ -7,27 +10,44 @@
 extern __code meta(struct Context*);
 extern __code allocate(struct Context*);
 extern __code put(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 exit_code(struct Context*);
 
 __code initLLRBContext(struct Context* context) {
-    context->codeSize = 3;
-    context->code[Code1]    = code1;
-    context->code[Code2]    = code2;
-    context->code[Code3]    = code3;
-    context->code[Code4]    = code4;
-    context->code[Code5]    = code5;
-    context->code[Allocate] = allocate;
-    context->code[Put]      = put;
-    context->code[InsertD]  = insertDown;
-    context->code[InsertU]  = insertUp;
-    context->code[Exit]     = exit_code;
+    context->dataSize = sizeof(union Data)*ALLOCATE_SIZE;
+    context->code = malloc(sizeof(__code*)*ALLOCATE_SIZE);
+    context->data = malloc(sizeof(union Data*)*ALLOCATE_SIZE);
+    context->heap_start = malloc(context->dataSize);
+
+    context->codeNum = Exit;
+    context->code[Code1]     = code1;
+    context->code[Code2]     = code2;
+    context->code[Code3]     = code3;
+    context->code[Code4]     = code4;
+    context->code[Code5]     = code5;
+    context->code[Allocator] = allocate;
+    context->code[Put]       = put;
+    context->code[InitNode]  = initNode;
+    context->code[Compare]   = compare;
+    context->code[Insert]    = insert;
+    /* context->code[InsertD]  = insertDown; */
+    /* context->code[InsertU]  = insertUp; */
+    context->code[Exit]      = exit_code;
     
-    context->dataSize = 0;
-    context->data[context->dataSize] = context->heap;
+    context->heap = context->heap_start;
+
+    context->data[Allocate] = context->heap;
     context->heap += sizeof(struct Allocate);
 
+    context->data[Tree] = context->heap;
+    context->heap += sizeof(struct Tree);
+
+    context->dataNum = Tree;
+
     context->root = 0;
     context->current = 0;
 }
--- a/src/llrb/llrbContext.h	Tue Apr 28 17:39:44 2015 +0900
+++ b/src/llrb/llrbContext.h	Thu Apr 30 19:07:23 2015 +0900
@@ -1,40 +1,65 @@
 /* Context definition for llrb example */
 
+#define ALLOCATE_SIZE 100
+
 enum Code {
     Code1,
     Code2,
     Code3,
     Code4,
     Code5,
-    Allocate,
+    Allocator,
     Put,
+    InitNode,
+    Compare,
+    Insert,
     InsertD,
     InsertU,
     Exit,
 };
 
-enum Color {
-    Red,
-    Black,
+enum UniqueData {
+    Allocate,
+    Tree,
 };
 
 struct Context {
-    int codeSize;
+    int codeNum;
     __code (**code) (struct Context *);
+    void* heap_start;
     void* heap;
     union Data* root;
     union Data* current;
-    int dataSize;
+    long dataSize;
+    int dataNum;
     union Data **data;
 };
 
 union Data {
     long count;
+    struct Tree {
+        union Data* root;
+        union Data* current;
+        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;
-        enum Color color;
-        union Data* parent;
+        enum Color {
+            Red,
+            Black,
+        } color;
         union Data* left;
         union Data* right;
     } node;
@@ -42,7 +67,6 @@
         long size;
         enum Code next;
         enum Code after_put;
-        int key;
-        int value;
+        struct Node node;
     } allocate;
 };