Mercurial > hg > GearsTemplate

changeset 147:f2275f5777f4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add treeRotate data
author Shinji KONO <kono@ie.u-ryukyu.ac.jp>
date Thu, 10 Nov 2016 10:35:48 +0900
parents 423141c31664
children 473b7d990a1f
files src/parallel_execution/context.c src/parallel_execution/context.h src/parallel_execution/rb_tree.c
diffstat 3 files changed, 45 insertions(+), 21 deletions(-) [+]
line wrap: on
line diff
--- a/src/parallel_execution/context.c	Thu Nov 10 09:27:01 2016 +0900
+++ b/src/parallel_execution/context.c	Thu Nov 10 10:35:48 2016 +0900
@@ -151,6 +151,8 @@
     struct Traverse* traverse = ALLOC_DATA(context, Traverse);
     traverse->nodeStack = &createSingleLinkedStack(context)->stack;
 
+    ALLOC_DATA(context, RotateTree);
+
     struct Node* node = ALLOC_DATA(context, Node);
     node->key = 0;
     node->value = 0;
--- a/src/parallel_execution/context.h	Thu Nov 10 09:27:01 2016 +0900
+++ b/src/parallel_execution/context.h	Thu Nov 10 10:35:48 2016 +0900
@@ -117,6 +117,7 @@
     Stack,
     Tree,
     Traverse,
+    RotateTree,
     Node,
     LoopCounter,
     Time,
@@ -217,7 +218,6 @@
     } tree;
     struct Traverse {
         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
@@ -226,6 +226,11 @@
         struct Stack* nodeStack;
         int result;
     } traverse;
+    struct RotateTree {
+        enum Code next;
+        struct Traverse* traverse;
+        struct Tree* tree;
+    } rotateTree;
     struct Node {
         int key; // comparable data segment
         union Data* value;
@@ -246,6 +251,8 @@
     } ods;
 };
 
+// typedef struct RotateTree D_RotateTree;
+
 union MetaData {
     struct Queue waitMeTasks;
     struct Queue waitI;
--- a/src/parallel_execution/rb_tree.c	Thu Nov 10 09:27:01 2016 +0900
+++ b/src/parallel_execution/rb_tree.c	Thu Nov 10 10:35:48 2016 +0900
@@ -171,20 +171,26 @@
         );
 }
 
-__code insertCase4(struct Context* context, struct Traverse* traverse) {
+__code insertCase4(struct Context* context, struct Traverse* traverse, struct RotateTree* rotateTree) {
     struct Stack* nodeStack = traverse->nodeStack;
 
     if ((traverse->current == traverse->parent->right) && (traverse->parent == traverse->grandparent->left)) {
         traverse->current = traverse->current->left;
-        traverse->rotateNext = C_insertCase5;
         traverse->parent = traverse->grandparent;
+
+        rotateTree->traverse = traverse;
+        rotateTree->next = C_insertCase5;
+
         nodeStack->stack = (union Data*)traverse->nodeStack;
         nodeStack->next = C_rotateLeft;
         goto meta(context, nodeStack->pop);
     } else if ((traverse->current == traverse->parent->left) && (traverse->parent == traverse->grandparent->right)) {
+        traverse->parent = traverse->grandparent;
         traverse->current = traverse->current->right;
-        traverse->rotateNext = C_insertCase5;
-        traverse->parent = traverse->grandparent;
+
+        rotateTree->traverse = traverse;
+        rotateTree->next = C_insertCase5;
+
         nodeStack->stack = (union Data*)traverse->nodeStack;
         nodeStack->next = C_rotateRight;
         goto meta(context, nodeStack->pop);
@@ -194,7 +200,7 @@
 }
 
 __code insertCase4_stub(struct Context* context) {
-    goto insertCase4(context, &context->data[Traverse]->traverse);
+    goto insertCase4(context, &context->data[Traverse]->traverse, &context->data[RotateTree]->rotateTree);
 }
 
 __code insertCase5(struct Context* context, struct Traverse* traverse,struct Stack *nodeStack) {
@@ -207,7 +213,7 @@
     goto insertCase5(context, &context->data[Traverse]->traverse, &context->data[Stack]->stack);
 }
 
-__code insertCase51(struct Context* context, struct Traverse* traverse, struct Node* current, struct Node* parent, struct Node* grandparent) {
+__code insertCase51(struct Context* context, struct Traverse* traverse, struct RotateTree *rotateTree, struct Node* current, struct Node* parent, struct Node* grandparent) {
     traverse->parent = parent;
     traverse->grandparent = grandparent;
 
@@ -215,7 +221,10 @@
     grandparent->color = Red;
 
     traverse->current = grandparent;
-    traverse->rotateNext = C_stackClear;
+
+    rotateTree->traverse = traverse;
+    rotateTree->next = C_stackClear;
+
     if ((current == parent->left) && (parent == grandparent->left))
         goto meta(context, C_rotateRight);
     else
@@ -225,7 +234,7 @@
 __code insertCase51_stub(struct Context* context) {
     struct Node* parent = &context->data[Stack]->stack.data->node;
     struct Node* grandparent = &context->data[Stack]->stack.data1->node;
-    goto insertCase51(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current, parent, grandparent);
+    goto insertCase51(context, &context->data[Traverse]->traverse,&context->data[RotateTree]->rotateTree, context->data[Traverse]->traverse.current, parent, grandparent);
 }
 
 __code rotateLeft(struct Context* context, struct Traverse* traverse,struct Stack* nodeStack) {
@@ -235,10 +244,11 @@
 }
 
 __code rotateLeft_stub(struct Context* context) {
-    goto rotateLeft(context, &context->data[Traverse]->traverse, &context->data[Stack]->stack);
+    struct Traverse* traverse = context->data[RotateTree]->rotateTree.traverse;
+    goto rotateLeft(context, 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 RotateTree *rotateTree) {
     struct Node* tmp = node->right;
 
     if (parent) {
@@ -254,16 +264,18 @@
     tmp->left = node;
     traverse->current = tmp;
     
-    goto meta(context, traverse->rotateNext);
+    goto meta(context, rotateTree->next);
 }
     
 __code rotateLeft1_stub(struct Context* context) {
+    struct Traverse* traverse = context->data[RotateTree]->rotateTree.traverse;
     struct Node* parent = &context->data[Stack]->stack.data->node;
     goto rotateLeft1(context,
-                    context->data[Traverse]->traverse.current,
+                    traverse->current,
                     &context->data[Tree]->tree,
-                    &context->data[Traverse]->traverse,
-                    parent);
+                    traverse,
+                    parent,
+                    &context->data[RotateTree]->rotateTree);
 }
 
 __code rotateRight(struct Context* context, struct Traverse* traverse,struct Stack *nodeStack) {
@@ -273,10 +285,11 @@
 }
 
 __code rotateRight_stub(struct Context* context) {
-    goto rotateLeft(context, &context->data[Traverse]->traverse, &context->data[Stack]->stack);
+    struct Traverse* traverse = context->data[RotateTree]->rotateTree.traverse;
+    goto rotateLeft(context, 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 RotateTree *rotateTree) {
     struct Node* tmp = node->left;
     
     if (parent) {
@@ -292,16 +305,18 @@
     tmp->right = node;
     traverse->current = tmp;
     
-    goto meta(context, traverse->rotateNext);
+    goto meta(context, rotateTree->next);
 }
 
 __code rotateRight1_stub(struct Context* context) {
+    struct Traverse* traverse = context->data[RotateTree]->rotateTree.traverse;
     struct Node* parent = &context->data[Stack]->stack.data->node;
     goto rotateRight1(context,
-                     context->data[Traverse]->traverse.current,
+                     traverse->current,
                      &context->data[Tree]->tree,
-                     &context->data[Traverse]->traverse,
-                     parent);
+                     traverse,
+                     parent,
+                     &context->data[RotateTree]->rotateTree);
 }
 
 __code stackClear(struct Context* context, struct Traverse* traverse,struct Stack *nodeStack) {