Mercurial > hg > Members > Moririn

changeset 143:34a7a21edc36

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
recude stack get using traverse field
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Wed, 09 Nov 2016 22:33:16 +0900
parents 92eef2161a87
children d529c024e5a5
files src/parallel_execution/context.h src/parallel_execution/rb_tree.c
diffstat 2 files changed, 41 insertions(+), 41 deletions(-) [+]
line wrap: on
line diff
--- a/src/parallel_execution/context.h	Wed Nov 09 15:43:38 2016 +0900
+++ b/src/parallel_execution/context.h	Wed Nov 09 22:33:16 2016 +0900
@@ -218,6 +218,8 @@
         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 Node* parent;
+        struct Node* grandparent; 
         struct Stack* nodeStack;
         int result;
     } traverse;
--- a/src/parallel_execution/rb_tree.c	Wed Nov 09 15:43:38 2016 +0900
+++ b/src/parallel_execution/rb_tree.c	Wed Nov 09 22:33:16 2016 +0900
@@ -27,6 +27,7 @@
     printTree((union Data*)(tree->root));
     traverse->newNode = newNode;
     tree->root = newNode; // this should done at stackClear
+    traverse->parent = NULL;
     if (root) {
         traverse->current = root;
         traverse->result = compare(traverse->current, node);
@@ -82,7 +83,6 @@
         traverse->result = compare(traverse->current, node);
         goto meta(context, Replace);
     }
-    
     goto meta(context, Insert);
 
 }
@@ -98,26 +98,28 @@
                      context->data[Traverse]->traverse.result);
 }
 
-__code insertNode(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* newNode) {
+__code insertNode(struct Context* context, struct Traverse* traverse, struct Stack *nodeStack, struct Node* node, struct Node* newNode) {
     *newNode = *node;
     newNode->color = Red;
     traverse->current = newNode;
-    goto meta(context, InsertCase1);
+    nodeStack->stack = (union Data*)traverse->nodeStack;
+    nodeStack->next = InsertCase1;
+    goto meta(context, traverse->nodeStack->get2);
 }
 
 __code insertNode_stub(struct Context* context) {
     goto insertNode(context,
                     &context->data[Traverse]->traverse,
+                    &context->data[Stack]->stack,
                     &context->data[Node]->node,
                     context->data[Traverse]->traverse.newNode);
 }
 
-__code insertCase1(struct Context* context,struct Traverse* traverse, struct Tree* tree, struct Stack* nodeStack) {
-    struct SingleLinkedStack* stack = (struct SingleLinkedStack*)traverse->nodeStack->stack;
-    if (stack->top != NULL) {
-        nodeStack->stack = (union Data*)traverse->nodeStack;
-        nodeStack->next = InsertCase2;
-        goto meta(context, traverse->nodeStack->get);
+__code insertCase1(struct Context* context,struct Traverse* traverse, struct Tree* tree,struct Node *parent, struct Node *grandparent) {
+    if (parent != NULL) {
+        traverse->parent = parent;
+        traverse->grandparent = grandparent;
+        goto meta(context,InsertCase2); 
     }
     tree->root->color = Black;
     goto meta(context, StackClear);
@@ -127,79 +129,72 @@
     goto insertCase1(context, 
         &context->data[Traverse]->traverse,
         &context->data[Tree]->tree,
-        &context->data[Stack]->stack);
+        &context->data[Stack]->stack.data->node,
+        &context->data[Stack]->stack.data1->node);
 }
 
-__code insertCase2(struct Context* context, struct Traverse* traverse, struct Stack* nodeStack, struct Node* parent) {
-    if (parent->color == Black) {
+__code insertCase2(struct Context* context, struct Traverse* traverse) {
+    if (traverse->parent->color == Black) {
         goto meta(context, StackClear);
     }
-    nodeStack->stack = (union Data*)traverse->nodeStack;
-    nodeStack->next = InsertCase3;
-    goto meta(context, traverse->nodeStack->get2);
+    goto meta(context,InsertCase3); 
 }
 
 __code insert2_stub(struct Context* context) {
-    goto insertCase2(context, &context->data[Traverse]->traverse, &context->data[Stack]->stack, &context->data[Stack]->stack.data->node); 
+    goto insertCase2(context, &context->data[Traverse]->traverse); 
 }
 
-__code insertCase3(struct Context* context, struct Traverse* traverse, struct Stack* nodeStack, struct Node* parent, struct Node* grandparent) {
+__code insertCase3(struct Context* context, struct Traverse* traverse, struct Stack* nodeStack) {
     struct Node* uncle;
 
-    if (grandparent->left == parent)
-        uncle = grandparent->right;
+    if (traverse->grandparent->left == traverse->parent)
+        uncle = traverse->grandparent->right;
     else
-        uncle = grandparent->left;
+        uncle = traverse->grandparent->left;
 
     if (uncle && (uncle->color == Red)) {
         // do insertcase1 on grandparent, stack must be pop by two
-        parent->color = Black;
+        traverse->parent->color = Black;
         uncle->color = Black;
-        grandparent->color = Red;
-        traverse->current = grandparent;
+        traverse->grandparent->color = Red;
+        traverse->current = traverse->grandparent;
         nodeStack->stack = (union Data*)traverse->nodeStack;
         nodeStack->next = InsertCase1;
         goto meta(context, traverse->nodeStack->pop2);
     }
-    nodeStack->stack = (union Data*)traverse->nodeStack;
-    nodeStack->next = InsertCase4;
-    goto meta(context, traverse->nodeStack->get2);
+    goto meta(context, InsertCase4);
 }
 
 __code insert3_stub(struct Context* context) {
     goto insertCase3(context, &context->data[Traverse]->traverse,
-                     &context->data[Stack]->stack,
-                     &context->data[Stack]->stack.data->node,
-                     &context->data[Stack]->stack.data1->node
+                     &context->data[Stack]->stack
         );
 }
 
-__code insertCase4(struct Context* context, struct Traverse* traverse, struct Node* current,struct Node* parent, struct Node* grandparent) {
+__code insertCase4(struct Context* context, struct Traverse* traverse) {
     struct Stack* nodeStack = traverse->nodeStack;
-    traverse->current = parent;
 
-    if ((current == parent->right) && (parent == grandparent->left)) {
+    if ((traverse->current == traverse->parent->right) && (traverse->parent == traverse->grandparent->left)) {
         traverse->current = traverse->current->left;
         traverse->rotateNext = InsertCase5;
+        traverse->parent = traverse->grandparent;
         nodeStack->stack = (union Data*)traverse->nodeStack;
         nodeStack->next = RotateL;
         goto meta(context, nodeStack->pop);
-    } else if ((current == parent->left) && (parent == grandparent->right)) {
+    } else if ((traverse->current == traverse->parent->left) && (traverse->parent == traverse->grandparent->right)) {
         traverse->current = traverse->current->right;
         traverse->rotateNext = InsertCase5;
+        traverse->parent = traverse->grandparent;
         nodeStack->stack = (union Data*)traverse->nodeStack;
         nodeStack->next = RotateR;
         goto meta(context, nodeStack->pop);
     }
 
-    traverse->current = current;
     goto meta(context, InsertCase5);
 }
 
 __code insert4_stub(struct Context* context) {
-    goto insertCase4(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current,
-                    &context->data[Stack]->stack.data->node,
-                    &context->data[Stack]->stack.data1->node);
+    goto insertCase4(context, &context->data[Traverse]->traverse);
 }
 
 __code insertCase5(struct Context* context, struct Traverse* traverse,struct Stack *nodeStack) {
@@ -213,6 +208,9 @@
 }
 
 __code insertCase51(struct Context* context, struct Traverse* traverse, struct Node* current, struct Node* parent, struct Node* grandparent) {
+    traverse->parent = parent;
+    traverse->grandparent = grandparent;
+
     parent->color = Black;
     grandparent->color = Red;
 
@@ -241,11 +239,11 @@
     goto rotateLeft(context, &context->data[Traverse]->traverse, &context->data[Stack]->stack);
 }
 
-__code rotateLeft1(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) {
+__code rotateLeft1(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node *parent) {
     struct Node* tmp = node->right;
 
     if (parent) {
-        if (node == parent->left)
+        if (node == traverse->parent->left)
             parent->left = tmp;
         else
             parent->right = tmp;
@@ -279,11 +277,11 @@
     goto rotateLeft(context, &context->data[Traverse]->traverse, &context->data[Stack]->stack);
 }
 
-__code rotateRight1(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) {
+__code rotateRight1(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse,struct Node *parent) {
     struct Node* tmp = node->left;
     
     if (parent) {
-        if (node == parent->left)
+        if (node == traverse->parent->left)
             parent->left = tmp;
         else
             parent->right = tmp;