Mercurial > hg > Gears > GearsAgda

changeset 138:04a2f486a30d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
insert works but is not balanced
author kono
date Tue, 08 Nov 2016 19:39:40 +0900
parents 909d0548284f
children c13b07d15d86
files src/parallel_execution/CMakeLists.txt src/parallel_execution/context.h src/parallel_execution/rb_tree.c src/parallel_execution/stack.c
diffstat 4 files changed, 39 insertions(+), 16 deletions(-) [+]
line wrap: on
line diff
--- a/src/parallel_execution/CMakeLists.txt	Tue Nov 08 17:35:03 2016 +0900
+++ b/src/parallel_execution/CMakeLists.txt	Tue Nov 08 19:39:40 2016 +0900
@@ -1,7 +1,7 @@
 cmake_minimum_required(VERSION 2.8)
 
 # -DUSE_CUDA
-# add_definitions("-Wall -g -O")
+#  add_definitions("-Wall -g -O")
 add_definitions("-Wall -g")
 
 set(CMAKE_C_COMPILER $ENV{CBC_COMPILER})
--- a/src/parallel_execution/context.h	Tue Nov 08 17:35:03 2016 +0900
+++ b/src/parallel_execution/context.h	Tue Nov 08 19:39:40 2016 +0900
@@ -216,6 +216,7 @@
         enum Code next;
         enum Code rotateNext;
         struct Node* current; // reading node of original tree
+        struct Node* previous; // parent of reading node of original tree
         struct Node* newNode; // writing node of new tree
         struct Stack* nodeStack;
         int result;
--- a/src/parallel_execution/rb_tree.c	Tue Nov 08 17:35:03 2016 +0900
+++ b/src/parallel_execution/rb_tree.c	Tue Nov 08 19:39:40 2016 +0900
@@ -3,7 +3,6 @@
 #include "context.h"
 #include "origin_cs.h"
 
-extern union Data* allocator(struct Context* context);
 extern enum Relational compare(struct Node* node1, struct Node* node2);
 
 void printTree1(union Data* data) {
@@ -31,9 +30,7 @@
     if (root) {
         traverse->current = root;
         traverse->result = compare(traverse->current, node);
-        nodeStack->data = (union Data*)(newNode);
-        nodeStack->next = Replace1;
-        goto meta(context, nodeStack->push);
+        goto meta(context, Replace);
     }
 
     goto meta(context, Insert);
@@ -42,7 +39,7 @@
 __code put_stub(struct Context* context) {
     struct Node* newNode = &ALLOCATE(context, Node)->node;
     goto put(context,
-             context->data[Traverse]->traverse.nodeStack,
+             &context->data[Stack]->stack,
              &context->data[Tree]->tree,
              &context->data[Node]->node,
              &context->data[Traverse]->traverse,
@@ -52,10 +49,12 @@
 }
 
 __code replaceNode(struct Context* context, struct Traverse* traverse, struct Node* oldNode, struct Node* newNode, struct Stack* nodeStack) {
+    traverse->previous = newNode;
     *newNode = *oldNode;
+    nodeStack->stack = (union Data*)traverse->nodeStack;
     nodeStack->data = (union Data*)(newNode);
     nodeStack->next = Replace1;
-    goto meta(context, nodeStack->push);
+    goto meta(context, traverse->nodeStack->push);
 }
 
 __code replaceNode_stub(struct Context* context) {
@@ -63,7 +62,7 @@
                   &context->data[Traverse]->traverse,
                   context->data[Traverse]->traverse.current,
                   context->data[Traverse]->traverse.newNode,
-                  context->data[Traverse]->traverse.nodeStack);
+                  &context->data[Stack]->stack);
 }
 
 __code replaceNode1(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, struct Node* newnewNode, int result) {
@@ -94,7 +93,7 @@
                      &context->data[Traverse]->traverse,
                      &context->data[Node]->node,
                      context->data[Traverse]->traverse.current,
-                     &context->data[Traverse]->traverse.nodeStack->data->node,
+                     context->data[Traverse]->traverse.previous,
                      newnewNode,
                      context->data[Traverse]->traverse.result);
 }
@@ -127,21 +126,21 @@
         &context->data[Traverse]->traverse.nodeStack->stack->singleLinkedStack);
 }
 
-__code insertCase2(struct Context* context, struct Stack* nodeStack, struct Node* parent) {
+__code insertCase2(struct Context* context, struct Traverse* traverse, struct Stack* nodeStack, struct Node* parent) {
     if (parent->color == Black) {
         goto meta(context, StackClear);
     }
+    nodeStack->stack = (union Data*)traverse->nodeStack;
     nodeStack->next = InsertCase3;
-    goto meta(context, nodeStack->get2);
+    goto meta(context, traverse->nodeStack->get2);
 }
 
 __code insert2_stub(struct Context* context) {
     struct SingleLinkedStack *nodeStack = (struct SingleLinkedStack*)context->data[Traverse]->traverse.nodeStack->stack;
-    goto insertCase2(context, context->data[Traverse]->traverse.nodeStack, &nodeStack->top->data->node);
+    goto insertCase2(context, &context->data[Traverse]->traverse, &context->data[Stack]->stack, &nodeStack->top->data->node);
 }
 
-__code insertCase3(struct Context* context, struct Traverse* traverse, struct Node* parent, struct Node* grandparent) {
-    struct Stack* nodeStack = traverse->nodeStack;
+__code insertCase3(struct Context* context, struct Traverse* traverse, struct Stack* nodeStack, struct Node* parent, struct Node* grandparent) {
     struct Node* uncle;
 
     if (grandparent->left == parent)
@@ -155,15 +154,18 @@
         uncle->color = Black;
         grandparent->color = Red;
         traverse->current = grandparent;
+        nodeStack->stack = (union Data*)traverse->nodeStack;
         nodeStack->next = InsertCase1;
-        goto meta(context, nodeStack->pop2);
+        goto meta(context, traverse->nodeStack->pop2);
     }
+    nodeStack->stack = (union Data*)traverse->nodeStack;
     nodeStack->next = InsertCase4;
-    goto meta(context, nodeStack->get2);
+    goto meta(context, traverse->nodeStack->get2);
 }
 
 __code insert3_stub(struct Context* context) {
     goto insertCase3(context, &context->data[Traverse]->traverse,
+                     &context->data[Stack]->stack,
                      &context->data[Traverse]->traverse.nodeStack->data->node,
                      &context->data[Traverse]->traverse.nodeStack->data1->node
         );
@@ -176,11 +178,13 @@
     if ((current == parent->right) && (parent == grandparent->left)) {
         traverse->current = traverse->current->left;
         traverse->rotateNext = InsertCase5;
+        nodeStack->stack = (union Data*)traverse->nodeStack;
         nodeStack->next = RotateL;
         goto meta(context, nodeStack->get);
     } else if ((current == parent->left) && (parent == grandparent->right)) {
         traverse->current = traverse->current->right;
         traverse->rotateNext = InsertCase5;
+        nodeStack->stack = (union Data*)traverse->nodeStack;
         nodeStack->next = RotateR;
         goto meta(context, nodeStack->get);
     }
@@ -197,6 +201,7 @@
 
 __code insertCase5(struct Context* context, struct Traverse* traverse) {
     struct Stack* nodeStack = traverse->nodeStack;
+    nodeStack->stack = (union Data*)traverse->nodeStack;
     nodeStack->next = InsertCase51;
     goto meta(context, nodeStack->pop2);
 }
@@ -227,6 +232,7 @@
 // put rotateLeft's continuation as argument
 __code rotateLeft(struct Context* context, struct Traverse* traverse) {
     struct Stack* nodeStack = traverse->nodeStack;
+    nodeStack->stack = (union Data*)traverse->nodeStack;
     nodeStack->next = RotateL1;
     goto meta(context, nodeStack->get);
 }
--- a/src/parallel_execution/stack.c	Tue Nov 08 17:35:03 2016 +0900
+++ b/src/parallel_execution/stack.c	Tue Nov 08 19:39:40 2016 +0900
@@ -1,6 +1,7 @@
 #include "context.h"
 #include "stack.h"
 #include "origin_cs.h"
+#include <stdio.h>
 
 union Data* createSingleLinkedStack(struct Context* context) {
     struct Stack* stack = &ALLOCATE(context, Stack)->stack;
@@ -16,6 +17,21 @@
     return (union Data*)(stack);
 }
 
+void printStack1(union Data* data) {
+    struct Node* node = &data->element.data->node;
+    if (node == NULL) {
+        printf("NULL");
+    } else {
+        printf("key = %d ,", node->key);
+        printStack1((union Data*)data->element.next);
+    }
+}
+
+void printStack(union Data* data) {
+    printStack1(data);
+    printf("\n");
+}
+
 __code pushSingleLinkedStack(struct Context* context, struct SingleLinkedStack* stack, struct Element* element, union Data* data, enum Code next) {
     element->next = stack->top;
     element->data = data;