Mercurial > hg > Members > innparusu > Gears

changeset 57:c469c5ed5b4d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify syntax
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Tue, 16 Jun 2015 13:40:08 +0900
parents 0299b90256e5
children 8c709b714fb0
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, 168 insertions(+), 181 deletions(-) [+]
line wrap: on
line diff
--- a/src/include/allocate.h	Thu Jun 11 17:23:50 2015 +0900
+++ b/src/include/allocate.h	Tue Jun 16 13:40:08 2015 +0900
@@ -9,5 +9,6 @@
 __code meta_allocate(struct Context* context) {
     context->data[++context->dataNum] = context->heap;
     context->heap += context->data[0]->allocate.size;
-    goto (context->code[context->data[0]->allocate.next])(context);
+
+    goto meta(context, context->next[--context->current]);
 }
--- a/src/include/origin_cs.h	Thu Jun 11 17:23:50 2015 +0900
+++ b/src/include/origin_cs.h	Tue Jun 16 13:40:08 2015 +0900
@@ -8,6 +8,6 @@
 __code exit_code(struct Context* context) {
     free(context->code);
     free(context->data);
-    free(context->heap_start);
+    free(context->heapStart);
     goto exit(0);
 }
--- a/src/llrb/llrb.c	Thu Jun 11 17:23:50 2015 +0900
+++ b/src/llrb/llrb.c	Tue Jun 16 13:40:08 2015 +0900
@@ -44,21 +44,16 @@
     }
 }
 
-__code meta_code1_before(struct Context* context) {
+__code code1(struct Context* context, struct Allocate *allocate) {
+    allocate->size = sizeof(struct Count);
+    context->next[context->current++] = Code2;
+    goto meta(context, Allocator);
+}
+
+__code code1_stub(struct Context* context) {
     goto code1(context, &context->data[Allocate]->allocate);
 }
 
-__code code1(struct Context* context, struct Allocate *allocate) {
-    allocate->size = sizeof(struct Count);
-    allocate->next = Code2;
-    goto meta(context, Allocater);
-}
-
-/* __code code1(struct Context* context) { */
-/*     context->data[Allocate]->allocate.size = sizeof(long); */
-/*     context->data[Allocate]->allocate.next = Code2; */
-/*     goto meta(context, Allocator); */
-/* } */
 
 /*
 __code code2(Allocate allocate, Count count) {
@@ -67,110 +62,118 @@
 }
 */
 
-__code code2_stub(struct Context* context) {
-    goto code2(context, &context->data[context->dataNum]->count);
-}
-
 __code code2(struct Context* context, struct Count* count) {
     count->i = 1;
     goto meta(context, Code3);
 }
 
+__code code2_stub(struct Context* context) {
+    goto code2(context, &context->data[context->dataNum]->count);
+}
+
+__code code3(struct Context* context, struct Node* node, struct Count* count) {
+    if (count->i == num) {
+        goto meta(context, Code4);
+    }
+
+    context->next[context->current++] = Code3;
+    node->key = count->i;
+    node->value = count->i;
+    
+    count->i++;
+    goto meta(context, Put);
+}
+
+__code code3_stub(struct Context* context) {
+    goto code3(context, &context->data[Node]->node, &context->data[3]->count);
+}
+
 __code meta(struct Context* context, enum Code next) {
     goto (context->code[next])(context);
 }
 
+__code put(struct Context* context, struct Tree* tree, struct Allocate* allocate) {
+    allocate->size = sizeof(struct Node);
+
+    if (tree->root == 0) {
+        context->next[context->current++] = Insert;
+    } else {
+        context->next[context->current++] = Compare;
+        context->next[context->current++] = Replace;
+        tree->current = tree->root;
+    }
+    goto meta(context, Allocator);
+}
+
 __code put_stub(struct Context* context) {
     goto put(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate);
 }
 
-__code put(struct Context* context, struct Tree* tree, struct Allocate* allocate) {
-    allocate->size = sizeof(struct Node);
-    if (tree->root == 0) {
-        allocate->next = Insert;
-        goto meta(context, Allocator);
-    }
-
-    allocate->next = Create;
-    tree->current = tree->root;
+__code replaceNode(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) {
+    stack_push(pstack, &newNode);
 
-    goto meta(context, Compare);
-}
-
-__code replaceNode(struct Context* context) {
-    struct Node* newNode = &context->data[context->dataNum]->node;
-    struct Tree* tree = &context->data[Tree]->tree;
-    struct Node* persistentNode = tree->current;
-
-    int result = context->data[Tree]->tree.result;
-
-    *newNode = *persistentNode;
+    *newNode = *oldNode;
 
     if (result == 0) {
         stack_pop(pstack, &tree->current);
         goto meta(context, RotateL);
     } else if (result == 1) {
-        tree->current = persistentNode->right;
+        tree->current = oldNode->right;
         newNode->right = context->heap;
     } else {
-        tree->current = persistentNode->left;
+        tree->current = oldNode->left;
         newNode->left = context->heap;
     }
 
     if (tree->current == 0) {
         stack_pop(pstack, &tree->current);
-        context->data[Allocate]->allocate.next = Insert;
-        goto meta(context, Allocator);
+        context->next[context->current++] = Insert;
+    } else {
+        context->next[context->current++] = Compare;
+        context->next[context->current++] = Replace;
     }
-    
-    context->data[Allocate]->allocate.next = Create;
-    goto meta(context, Compare);
+
+    goto meta(context, Allocator);
 }
 
-__code insertNode(struct Context* context) {
-    struct Node* newNode = &context->data[context->dataNum]->node;
-    struct Node* temporalNode = &context->data[Node]->node;
-    struct Tree* tree = &context->data[Tree]->tree;
+__code replaceNode_stub(struct Context* context) {
+    goto replaceNode(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result);
+}
 
-    temporalNode->color = Red;
-    *newNode = *temporalNode;
+__code insertNode(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) {
+    node->color = Red;
+    *newNode = *node;
 
     if (tree->root == 0) {
         newNode->color = Black;
         tree->root = newNode;
-        goto meta(context, context->data[Next]->next);
+        goto meta(context, context->next[--context->current]);
     }
 
     goto meta(context, RotateL);
 }
 
-__code compare(struct Context* context) {
-    int persistentKey = context->data[Tree]->tree.current->key;
-    int temporalKey = context->data[Node]->node.key;
-    
-    struct Tree* tree = &context->data[Tree]->tree;
+__code insertNode_stub(struct Context* context) {
+    goto insertNode(context, &context->data[Tree]->tree, &context->data[Node]->node, &context->data[context->dataNum]->node);
+}
 
-    if (persistentKey == temporalKey) {
+__code compare(struct Context* context, struct Tree* tree, int key1, int key2) {
+    if (key1 == key2) {
         tree->result = 0;
-    } else if (persistentKey < temporalKey) {
+    } else if (key1 < key2) {
         tree->result = 1;
     } else {
         tree->result = -1;
     }
 
-    goto meta(context, context->data[Allocate]->allocate.next);
+    goto meta(context, context->next[--context->current]);
 }
         
-__code createNode(struct Context* context) {
-    stack_push(pstack, &context->heap);
-
-    context->data[Allocate]->allocate.next = Replace;
-    goto meta(context, Allocator);
+__code compare_stub(struct Context* context) {
+    goto compare(context, &context->data[Tree]->tree, context->data[Tree]->tree.current->key, context->data[Node]->node.key);
 }
 
-__code rotateLeft(struct Context* context) {
-    struct Node* node = context->data[Tree]->tree.current;
-    
+__code rotateLeft(struct Context* context, struct Node* node) {
     if (node->right != 0) {
         if (node->right->color == Red) {
             struct Node* tmp = node->right;
@@ -185,9 +188,11 @@
     goto meta(context, RotateR);
 }
     
-__code rotateRight(struct Context* context) {
-    struct Node* node = context->data[Tree]->tree.current;
+__code rotateLeft_stub(struct Context* context) {
+    goto rotateLeft(context, context->data[Tree]->tree.current);
+}
 
+__code rotateRight(struct Context* context, struct Node* node) {
     if (node->left != 0) {
         if (node->left->left != 0) {
             if (node->left->color == Red && node->left->left->color == Red) {
@@ -204,9 +209,11 @@
     goto meta(context, ColorFlip);
 }
 
-__code colorFlip(struct Context* context) {
-    struct Node* node = context->data[Tree]->tree.current;
-    
+__code rotateRight_stub(struct Context* context) {
+    goto rotateRight(context, context->data[Tree]->tree.current);
+}
+
+__code colorFlip(struct Context* context, struct Node* node) {
     if (node->right != 0 && node->left != 0) {
         if (node->right->color == Red && node->left->color == Red) {
             node->color ^= 1;
@@ -218,32 +225,33 @@
     goto meta(context, FixUp);
 }
 
-__code fixUp(struct Context* context) {
-    struct Allocate* allocate = &context->data[Allocate]->allocate;
-    struct Node* node = context->data[Tree]->tree.current;
+__code colorFlip_stub(struct Context* context) {
+    goto colorFlip(context, context->data[Tree]->tree.current);
+}
 
-    allocate->next = ChangeRef;
-
-    context->data[Node]->node.key = node->key;
-    context->data[Tree]->tree.prev = node;
+__code fixUp(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) {
+    node->key = newNode->key;
+    tree->prev = newNode;
     
-    if (stack_pop(pstack, &context->data[Tree]->tree.current) == 0) {
+    if (stack_pop(pstack, &tree->current) == 0) {
+        context->next[context->current++] = ChangeRef;
         goto meta(context, Compare);
     }
     
-    context->data[Tree]->tree.root = node;
+    tree->root = newNode;
     
-    goto meta(context, context->data[Next]->next);
+    goto meta(context, context->next[--context->current]);
 }    
 
-__code changeReference(struct Context* context) {
-    struct Node* node = context->data[Tree]->tree.current;
-    int result = context->data[Tree]->tree.result;
-    
+__code fixUp_stub(struct Context* context) {
+    goto fixUp(context, &context->data[Tree]->tree, &context->data[Node]->node, context->data[Tree]->tree.current);
+}
+
+__code changeReference(struct Context* context, struct Tree* tree, struct Node* node, int result) {
     if (result == 1) {
-        node->right = context->data[Tree]->tree.prev;
+        node->right = tree->prev;
     } else if (result == -1) {
-        node->left = context->data[Tree]->tree.prev;
+        node->left = tree->prev;
     } else {
         perror("bad status");
     }
@@ -251,53 +259,41 @@
     goto meta(context, RotateL);
 }
 
-__code get(struct Context* context) {
-    context->data[Tree]->tree.current = context->data[Tree]->tree.root;
-    context->data[Next]->next = context->data[Allocate]->allocate.next;
-    context->data[Allocate]->allocate.next = Traverse;
-
-    goto meta(context, Compare);
+__code changeReference_stub(struct Context* context) {
+    goto changeReference(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, context->data[Tree]->tree.result);
 }
 
-__code traverse(struct Context* context) {
-    int result = context->data[Tree]->tree.result;
-    struct Tree* tree = &context->data[Tree]->tree;
-    
-    if (result == 0) {
-        goto meta(context, context->data[Next]->next);
-    } else if (result == 1) {
-        tree->current = tree->current->right;
-    } else {
-        tree->current = tree->current->left;
-    }
+/* __code get(struct Context* context) { */
+/*     context->data[Tree]->tree.current = context->data[Tree]->tree.root; */
+/*     context->data[Next]->next = context->data[Allocate]->allocate.next; */
+/*     context->data[Allocate]->allocate.next = Traverse; */
 
-    if(tree->current == 0) {
-        goto meta(context, context->data[Next]->next);
-    }
-
-    goto meta(context, Compare);
-}
+/*     goto meta(context, Compare); */
+/* } */
 
-__code delete(struct Context* context) {
-    goto meta(context, Get);
-}
-
-__code meta_code3_before(struct Context* context) {
-    goto code3(context, &context->data[Node]->node, &context->data[4]->count);
-}
+/* __code traverse(struct Context* context) { */
+/*     int result = context->data[Tree]->tree.result; */
+/*     struct Tree* tree = &context->data[Tree]->tree; */
+    
+/*     if (result == 0) { */
+/*         goto meta(context, context->data[Next]->next); */
+/*     } else if (result == 1) { */
+/*         tree->current = tree->current->right; */
+/*     } else { */
+/*         tree->current = tree->current->left; */
+/*     } */
 
-__code code3(struct Context* context, struct Node* node, struct Count* count) {
-    if (count->i == num) {
-        goto meta(context, Code4);
-    }
+/*     if(tree->current == 0) { */
+/*         goto meta(context, context->data[Next]->next); */
+/*     } */
 
-    node->next = Code3;
-    node->key = loop;
-    node->value = loop;
-    
-    count->i++;
-    goto meta(context, Put);
-}
+/*     goto meta(context, Compare); */
+/* } */
+
+/* __code delete(struct Context* context) { */
+/*     goto meta(context, Get); */
+/* } */
+
 __code code4(struct Context* context) {
     puts("---before---");
     print_tree(context->data[Tree]->tree.root, 0);
@@ -320,17 +316,14 @@
     printf("%d\n", context->dataNum);
     stack_free(pstack);
 
-    context->data[Allocate]->allocate.next = Code6;
-    context->data[Node]->node.key = 2;
-
-    goto meta(context, Get);
+    goto meta(context, Exit);
 }
 
-__code code6(struct Context* context) {
-    puts("---get---");
-    print_tree(context->data[Tree]->tree.current, 0);
-    goto meta(context, Exit);
-}
+/* __code code6(struct Context* context) { */
+/*     puts("---get---"); */
+/*     print_tree(context->data[Tree]->tree.current, 0); */
+/*     goto meta(context, Exit); */
+/* } */
 
 int main(int argc, char** argv) {
     num = (int)atoi(argv[1]);
--- a/src/llrb/llrbContext.c	Thu Jun 11 17:23:50 2015 +0900
+++ b/src/llrb/llrbContext.c	Tue Jun 16 13:40:08 2015 +0900
@@ -2,57 +2,53 @@
 
 #include "llrbContext.h"
 
-extern __code code1(struct Context*);
-extern __code code2(struct Context*);
-extern __code code3(struct Context*);
+extern __code code1_stub(struct Context*);
+extern __code code2_stub(struct Context*);
+extern __code code3_stub(struct Context*);
 extern __code code4(struct Context*);
 extern __code code5(struct Context*);
-extern __code code6(struct Context*);
+extern __code code6_stub(struct Context*);
 extern __code meta(struct Context*);
 extern __code allocate(struct Context*);
-extern __code put(struct Context*);
-extern __code replaceNode(struct Context*);
-extern __code insertNode(struct Context*);
-extern __code compare(struct Context*);
-extern __code createNode(struct Context*);
-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 get(struct Context*);
-extern __code traverse(struct Context*);
+extern __code put_stub(struct Context*);
+extern __code replaceNode_stub(struct Context*);
+extern __code insertNode_stub(struct Context*);
+extern __code compare_stub(struct Context*);
+extern __code rotateLeft_stub(struct Context*);
+extern __code rotateRight_stub(struct Context*);
+extern __code colorFlip_stub(struct Context*);
+extern __code fixUp_stub(struct Context*);
+extern __code changeReference_stub(struct Context*);
+extern __code get_stub(struct Context*);
+extern __code traverse_stub(struct Context*);
 extern __code exit_code(struct Context*);
 
 __code initLLRBContext(struct Context* context) {
-    context->dataSize = sizeof(union Data)*ALLOCATE_SIZE;
+    context->heapLimit = sizeof(union Data)*ALLOCATE_SIZE;
+    context->next = malloc(sizeof(enum Code)*ALLOCATE_SIZE);
     context->code = malloc(sizeof(__code*)*ALLOCATE_SIZE);
     context->data = malloc(sizeof(union Data*)*ALLOCATE_SIZE);
-    context->heap_start = malloc(context->dataSize);
+    context->heapStart = malloc(context->heapLimit);
 
     context->codeNum = Exit;
-    context->code[Code1]     = code1;
-    context->code[Code2]     = code2;
-    context->code[Code3]     = code3;
+    context->code[Code1]     = code1_stub;
+    context->code[Code2]     = code2_stub;
+    context->code[Code3]     = code3_stub;
     context->code[Code4]     = code4;
     context->code[Code5]     = code5;
-    context->code[Code6]     = code6;
     context->code[Allocator] = allocate;
-    context->code[Put]       = put;
-    context->code[Replace]   = replaceNode;
-    context->code[Insert]    = insertNode;
-    context->code[Compare]   = compare;
-    context->code[Create]    = createNode;
-    context->code[RotateL]   = rotateLeft;
-    context->code[RotateR]   = rotateRight;
-    context->code[ColorFlip] = colorFlip;
-    context->code[FixUp]     = fixUp;
-    context->code[ChangeRef] = changeReference;
-    context->code[Get]       = get;
-    context->code[Traverse]  = traverse;
+    context->code[Put]       = put_stub;
+    context->code[Replace]   = replaceNode_stub;
+    context->code[Insert]    = insertNode_stub;
+    context->code[Compare]   = compare_stub;
+    context->code[RotateL]   = rotateLeft_stub;
+    context->code[RotateR]   = rotateRight_stub;
+    context->code[ColorFlip] = colorFlip_stub;
+    context->code[FixUp]     = fixUp_stub;
+    context->code[ChangeRef] = changeReference_stub;
     context->code[Exit]      = exit_code;
     
-    context->heap = context->heap_start;
+    context->heap = context->heapStart;
 
     context->data[Allocate] = context->heap;
     context->heap += sizeof(struct Allocate);
@@ -63,13 +59,11 @@
     context->data[Node] = context->heap;
     context->heap += sizeof(struct Node);
 
-    context->data[Next] = context->heap;
-    context->heap += sizeof(enum Code);
-
-    context->dataNum = Next;
+    context->dataNum = Node;
     
     struct Tree* tree = &context->data[Tree]->tree;
     tree->root = 0;
     tree->current = 0;
     tree->prev = 0;
+    
 }
--- a/src/llrb/llrbContext.h	Thu Jun 11 17:23:50 2015 +0900
+++ b/src/llrb/llrbContext.h	Tue Jun 16 13:40:08 2015 +0900
@@ -29,7 +29,6 @@
     Allocate,
     Tree,
     Node,
-    Next,
 };
 
 struct Context {
@@ -48,10 +47,10 @@
     struct Comparable { // inteface
         enum Code compare;
         union Data* data;
-    }
+    } compare;
     struct Count {
         enum Code next;
-        long count;
+        long i;
     } count;
     struct Tree {
         enum Code next;