Mercurial > hg > Gears > GearsAgda

changeset 134:2eccf4564efe

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
fix stack call in rb_tree
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Tue, 08 Nov 2016 10:44:39 +0900
parents 568730b1239e
children 77a7ccb0d84d
files src/parallel_execution/context.h src/parallel_execution/rb_tree.c src/parallel_execution/stack.c
diffstat 3 files changed, 79 insertions(+), 81 deletions(-) [+]
line wrap: on
line diff
--- a/src/parallel_execution/context.h	Mon Nov 07 21:12:19 2016 +0900
+++ b/src/parallel_execution/context.h	Tue Nov 08 10:44:39 2016 +0900
@@ -50,7 +50,9 @@
     Insert,
     Compare,
     RotateL,
+    RotateL1,
     RotateR,
+    RotateR1,
     SetTree,
     InsertCase1,
     InsertCase2,
@@ -62,6 +64,7 @@
     InsertCase4_1,
     InsertCase4_2,
     InsertCase5,
+    InsertCase51,
     StackClear,
     Get,
     Search,
@@ -196,6 +199,7 @@
         enum Code pop2;
         enum Code isEmpty;
         enum Code whenEmpty;
+        enum Code get;
         enum Code get2;
         enum Code next;
     } stack;
--- a/src/parallel_execution/rb_tree.c	Mon Nov 07 21:12:19 2016 +0900
+++ b/src/parallel_execution/rb_tree.c	Tue Nov 08 10:44:39 2016 +0900
@@ -40,16 +40,14 @@
 }
 
 __code put_stub(struct Context* context) {
-    struct Allocate* allocate = &context->data[Allocate]->allocate;
-    allocate->size = sizeof(struct Node);
-    allocator(context);
+    struct Node* newNode = &ALLOCATE(context, Node)->node;
     goto put(context,
              context->data[Traverse]->traverse.nodeStack,
              &context->data[Tree]->tree,
              &context->data[Node]->node,
              &context->data[Traverse]->traverse,
              context->data[Tree]->tree.root,
-             &context->data[context->dataNum]->node
+             newNode
              );
 }
 
@@ -129,18 +127,20 @@
         context->data[Traverse]->traverse.nodeStack);
 }
 
-__code insertCase2(struct Context* context, struct Node* parent) {
+__code insertCase2(struct Context* context, struct Stack* nodeStack, struct Node* parent) {
     if (parent->color == Black) {
         goto meta(context, StackClear);
     }
-    goto meta(context, InsertCase3);
+    nodeStack->next = InsertCase3;
+    goto meta(context, nodeStack->get2);
 }
 
 __code insert2_stub(struct Context* context) {
-    goto insertCase2(context, (struct Node*)context->data[Traverse]->traverse.nodeStack->data);
+    goto insertCase2(context, context->data[Traverse]->traverse.nodeStack, (struct Node*)context->data[Traverse]->traverse.nodeStack->data);
 }
 
 __code insertCase3(struct Context* context, struct Traverse* traverse, struct Node* parent, struct Node* grandparent) {
+    struct Stack* nodeStack = traverse->nodeStack;
     struct Node* uncle;
 
     if (grandparent->left == parent)
@@ -154,34 +154,34 @@
         uncle->color = Black;
         grandparent->color = Red;
         traverse->current = grandparent;
-        goto meta(context, InsertCase31);
+        nodeStack->next = InsertCase1;
+        goto meta(context, nodeStack->pop2);
     }
-    goto meta(context, InsertCase4);
+    nodeStack->next = InsertCase4;
+    goto meta(context, nodeStack->get2);
 }
 
 __code insert3_stub(struct Context* context) {
     goto insertCase3(context, &context->data[Traverse]->traverse,
-                     (struct Node*)context->data[Traverse]->traverse.nodeStack->data,
-                     (struct Node*)context->data[Traverse]->traverse.nodeStack->next->data
+                     &context->data[Traverse]->traverse.nodeStack->data->node,
+                     &context->data[Traverse]->traverse.nodeStack->data1->node
         );
 }
-__code insertCase31(struct Context* context, struct Traverse* traverse) {
-    traverse->nodeStack = traverse->nodeStack->next->next;
-    goto meta(context, InsertCase1);
-}
-__code insert31_stub(struct Context* context) {
-    goto insertCase31(context, &context->data[Traverse]->traverse);
-}
 
 __code insertCase4(struct Context* context, struct Traverse* traverse, struct Node* current,struct Node* parent, struct Node* grandparent) {
+    struct Stack* nodeStack = traverse->nodeStack;
     traverse->current = parent;
 
     if ((current == parent->right) && (parent == grandparent->left)) {
-        traverse->rotateNext = InsertCase4_1;
-        goto meta(context, InsertCase4_01);
+        traverse->current = traverse->current->left;
+        traverse->rotateNext = InsertCase5;
+        nodeStack->next = RotateL;
+        goto meta(context, nodeStack->get);
     } else if ((current == parent->left) && (parent == grandparent->right)) {
-        traverse->rotateNext = InsertCase4_2;
-        goto meta(context, InsertCase4_02);
+        traverse->current = traverse->current->right;
+        traverse->rotateNext = InsertCase5;
+        nodeStack->next = RotateR;
+        goto meta(context, nodeStack->get);
     }
 
     traverse->current = current;
@@ -191,58 +191,20 @@
 __code insert4_stub(struct Context* context) {
     goto insertCase4(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current,
                     &context->data[Traverse]->traverse.nodeStack->data->node,
-                    &context->data[Traverse]->traverse.nodeStack->next->data->node);
-}
-
-__code insertCase4_01(struct Context* context, struct Traverse* traverse) {
-    traverse->nodeStack = traverse->nodeStack -> next; 
-    traverse->rotateNext = InsertCase5;
-    goto meta(context, RotateL);
-}
-
-__code insert4_01_stub(struct Context* context) {
-    goto insertCase4_01(context, &context->data[Traverse]->traverse);
-}   
-__code insertCase4_1(struct Context* context, struct Traverse* traverse) {
-    traverse->current = traverse->current->left;
-    goto meta(context, InsertCase5);
+                    &context->data[Traverse]->traverse.nodeStack->data1->node);
 }
 
-__code insert4_1_stub(struct Context* context) {
-    struct Allocate* allocate = &context->data[Allocate]->allocate;
-    allocate->size = sizeof(struct Element);
-    allocator(context);
-    struct Element* element = &context->data[context->dataNum]->element;
-    struct Traverse* traverse = &context->data[Traverse]->traverse;
-    element->data = (union Data*)traverse->current;
-    goto insertCase4_1(context, &context->data[Traverse]->traverse);
-}   
-__code insertCase4_02(struct Context* context, struct Traverse* traverse) {
-    traverse->nodeStack = traverse->nodeStack -> next; 
-    traverse->rotateNext = InsertCase5;
-    goto meta(context, RotateR);
+__code insertCase5(struct Context* context, struct Traverse* traverse) {
+    struct Stack* nodeStack = traverse->nodeStack;
+    nodeStack->next = InsertCase51;
+    goto meta(context, nodeStack->pop2);
 }
 
-__code insert4_02_stub(struct Context* context) {
-    goto insertCase4_02(context, &context->data[Traverse]->traverse);
-}   
-
-__code insertCase4_2(struct Context* context, struct Traverse* traverse) {
-    traverse->current = traverse->current->right;
-    goto meta(context, InsertCase5);
+__code insert5_stub(struct Context* context) {
+    goto insertCase5(context, &context->data[Traverse]->traverse);
 }
 
-__code insert4_2_stub(struct Context* context) {    
-    struct Allocate* allocate = &context->data[Allocate]->allocate;
-    allocate->size = sizeof(struct Element);
-    allocator(context);
-    struct Element* element = &context->data[context->dataNum]->element;
-    struct Traverse* traverse = &context->data[Traverse]->traverse;
-    element->data = (union Data*)traverse->current;
-    goto insertCase4_2(context, &context->data[Traverse]->traverse);
-}   
-
-__code insertCase5(struct Context* context, struct Traverse* traverse, struct Node* current, struct Node* parent, struct Node* grandparent) {
+__code insertCase51(struct Context* context, struct Traverse* traverse, struct Node* current, struct Node* parent, struct Node* grandparent) {
     parent->color = Black;
     grandparent->color = Red;
 
@@ -254,16 +216,25 @@
         goto meta(context, RotateL);
 }
 
-__code insert5_stub(struct Context* context) {
+__code insert51_stub(struct Context* context) {
     struct Traverse* traverse = &context->data[Traverse]->traverse;
-    struct Node* parent = (struct Node*)traverse->nodeStack->data;
-    struct Node* grandparent = (struct Node*)traverse->nodeStack->next->data;
-    traverse->nodeStack = traverse->nodeStack->next->next;
-    goto insertCase5(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current, parent, grandparent);
+    struct Node* parent = &traverse->nodeStack->data->node;
+    struct Node* grandparent = &traverse->nodeStack->data1->node;
+    goto insertCase51(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current, parent, grandparent);
 }
 
 // put rotateLeft's continuation as argument
-__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) {
+__code rotateLeft(struct Context* context, struct Traverse* traverse) {
+    struct Stack* nodeStack = traverse->nodeStack;
+    nodeStack->next = RotateL1;
+    goto meta(context, nodeStack->get);
+}
+
+__code rotateLeft_stub(struct Context* context) {
+    goto rotateLeft(context, &context->data[Traverse]->traverse);
+}
+
+__code rotateLeft1(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) {
     struct Node* tmp = node->right;
 
     if (parent) {
@@ -282,17 +253,27 @@
     goto meta(context, traverse->rotateNext);
 }
     
-__code rotateLeft_stub(struct Context* context) {
+__code rotateLeft1_stub(struct Context* context) {
     struct Traverse* traverse = &context->data[Traverse]->traverse;
-    struct Node* parent = (traverse->nodeStack)?(struct Node*)traverse->nodeStack->data:NULL;
-    goto rotateLeft(context,
+    struct Node* parent = &traverse->nodeStack->data->node;
+    goto rotateLeft1(context,
                     context->data[Traverse]->traverse.current,
                     &context->data[Tree]->tree,
                     &context->data[Traverse]->traverse,
                     parent);
 }
 
-__code rotateRight(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) {
+__code rotateRight(struct Context* context, struct Traverse* traverse) {
+    struct Stack* nodeStack = traverse->nodeStack;
+    nodeStack->next = RotateR1;
+    goto meta(context, nodeStack->get);
+}
+
+__code rotateRight_stub(struct Context* context) {
+    goto rotateRight(context, &context->data[Traverse]->traverse);
+}
+
+__code rotateRight1(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) {
     struct Node* tmp = node->left;
     
     if (parent) {
@@ -311,10 +292,10 @@
     goto meta(context, traverse->rotateNext);
 }
 
-__code rotateRight_stub(struct Context* context) {
+__code rotateRight1_stub(struct Context* context) {
     struct Traverse* traverse = &context->data[Traverse]->traverse;
-    struct Node* parent = (traverse->nodeStack)?(struct Node*)traverse->nodeStack->data:NULL;
-    goto rotateRight(context,
+    struct Node* parent = &traverse->nodeStack->data->node;
+    goto rotateRight1(context,
                      context->data[Traverse]->traverse.current,
                      &context->data[Tree]->tree,
                      &context->data[Traverse]->traverse,
--- a/src/parallel_execution/stack.c	Mon Nov 07 21:12:19 2016 +0900
+++ b/src/parallel_execution/stack.c	Tue Nov 08 10:44:39 2016 +0900
@@ -10,6 +10,7 @@
     stack->push = PushSingleLinkedStack;
     stack->pop  = PopSingleLinkedStack;
     stack->pop2  = Pop2SingleLinkedStack;
+    stack->get  = GetSingleLinkedStack;
     stack->get2  = Get2SingleLinkedStack;
     stack->isEmpty = IsEmptySingleLinkedStack;
     return GET_DATA(stack);
@@ -59,6 +60,18 @@
                                context->data[Stack]->stack.next);
 }
 
+__code getSingleLinkedStack(struct Context* context, struct SingleLinkedStack* stack, union Data** data, union Data** data1, enum Code next) {
+    *data = stack->top;
+    goto meta(context, next);
+}
+
+__code getSingleLinkedStack_stub(struct Context* context) {
+    goto popSingleLinkedStack(context,
+                               (struct SignleLinkedStack *)context->data[Stack]->stack.stack,
+                               &context->data[Stack]->stack.data,
+                               context->data[Stack]->stack.next);
+}
+
 __code get2SingleLinkedStack(struct Context* context, struct SingleLinkedStack* stack, union Data** data, union Data** data1, enum Code next) {
     *data = stack->top;
     *data1 = stack->top->next;