Mercurial > hg > GearsTemplate

changeset 172:661b0b0d0399

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
replace Tree to RedBlackTree
author ikkun
date Thu, 24 Nov 2016 20:22:17 +0900
parents 747067fe46bd
children 8260b230dc2f
files src/parallel_execution/context.c src/parallel_execution/context.h src/parallel_execution/rb_tree.c
diffstat 3 files changed, 55 insertions(+), 60 deletions(-) [+]
line wrap: on
line diff
--- a/src/parallel_execution/context.c	Thu Nov 24 16:29:46 2016 +0900
+++ b/src/parallel_execution/context.c	Thu Nov 24 20:22:17 2016 +0900
@@ -99,7 +99,6 @@
     context->code[C_insertCase4]  = insertCase4_stub;
     context->code[C_insertCase5]  = insertCase5_stub;
     context->code[C_insertCase51] = insertCase51_stub;
-    context->code[C_stackClear]   = stackClear_stub;
     context->code[C_get]          = get_stub;
     context->code[C_search]       = search_stub;
 
@@ -165,11 +164,9 @@
     
     ALLOC_DATA(context, Stack);
 
-    struct Tree* tree = ALLOC_DATA(context, Tree);
-    tree->root = 0;
+    ALLOC_DATA(context, Tree);
 
-    struct Traverse* traverse = ALLOC_DATA(context, Traverse);
-    traverse->nodeStack = &createSingleLinkedStack(context)->stack;
+    ALLOC_DATA(context, RedBlackTree);
 
     ALLOC_DATA(context, RotateTree);
 
--- a/src/parallel_execution/context.h	Thu Nov 24 16:29:46 2016 +0900
+++ b/src/parallel_execution/context.h	Thu Nov 24 20:22:17 2016 +0900
@@ -249,7 +249,7 @@
         enum Code clear;
         enum Code next;
     } Tree;
-    struct Traverse {
+    struct RedBlackTree {
         struct Node* root;
         struct Node* current; // reading node of original tree
         struct Node* previous; // parent of reading node of original tree
@@ -258,10 +258,10 @@
         struct Node* grandparent; 
         struct Stack* nodeStack;
         int result;
-    } Traverse;
+    } RedBlackTree;
     struct RotateTree {
         enum Code next;
-        struct Traverse* traverse;
+        struct RedBlackTree* traverse;
         struct Tree* tree;
     } rotateTree;
     struct Node {
@@ -300,7 +300,6 @@
 typedef struct Array Array;
 typedef struct RedBlackTree RedBlackTree;
 typedef struct Tree Tree;
-typedef struct Traverse Traverse;
 typedef struct RotateTree RotateTree;
 typedef struct Node Node;
 typedef struct Allocate Allocate;
--- a/src/parallel_execution/rb_tree.c	Thu Nov 24 16:29:46 2016 +0900
+++ b/src/parallel_execution/rb_tree.c	Thu Nov 24 20:22:17 2016 +0900
@@ -35,10 +35,10 @@
     printf("\n");
 }
 
-__code putRedBlackTree(struct Context* context, struct Stack* nodeStack,  struct Tree* tree, struct Node* node, struct Traverse* traverse, struct Node* root, struct Node* newNode) {
-    printTree((union Data*)(tree->root));
+__code putRedBlackTree(struct Context* context, struct Stack* nodeStack,  struct RedBlackTree* traverse, struct Node* node, struct Node* root, struct Node* newNode) {
+    printTree((union Data*)(traverse->root));
     traverse->newNode = newNode;
-    tree->root = newNode; // this should done at stackClear
+    traverse->root = newNode; // this should done at stackClear
     traverse->parent = NULL;
     if (root) {
         traverse->current = root;
@@ -51,17 +51,16 @@
 
 __code putRedBlackTree_stub(struct Context* context) {
     struct Node* newNode = &ALLOCATE(context, Node)->node;
-    goto put(context,
+    goto putRedBlackTree(context,
              &context->data[D_Stack]->stack,
-             &context->data[D_Tree]->tree,
+             &context->data[D_RedBlackTree]->RedBlackTree,
              &context->data[D_Node]->node,
-             &context->data[D_Traverse]->Traverse,
-             context->data[D_Tree]->tree.root,
+             context->data[D_RedBlackTree]->RedBlackTree.root,
              newNode
              );
 }
 
-__code replaceNode(struct Context* context, struct Traverse* traverse, struct Node* oldNode, struct Node* newNode, struct Stack* nodeStack) {
+__code replaceNode(struct Context* context, struct RedBlackTree* traverse, struct Node* oldNode, struct Node* newNode, struct Stack* nodeStack) {
     traverse->previous = newNode;
     *newNode = *oldNode;
     nodeStack->stack = (union Data*)traverse->nodeStack;
@@ -72,14 +71,14 @@
 
 __code replaceNode_stub(struct Context* context) {
     goto replaceNode(context,
-                  &context->data[D_Traverse]->Traverse,
-                  context->data[D_Traverse]->Traverse.current,
-                  //context->data[D_Traverse]->Traverse.newNode,
-                  Gearef(context, Traverse)->newNode,
+                  &context->data[D_RedBlackTree]->RedBlackTree,
+                  context->data[D_RedBlackTree]->RedBlackTree.current,
+                  //context->data[D_RedBlackTree]->RedBlackTree.newNode,
+                  Gearef(context, RedBlackTree)->newNode,
                   &context->data[D_Stack]->stack);
 }
 
-__code replaceNode1(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, struct Node* newnewNode, int result) {
+__code replaceNode1(struct Context* context, struct RedBlackTree* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, struct Node* newnewNode, int result) {
     if (result == EQ) {
         newNode->value = node->value;
         // go to stack clear
@@ -103,15 +102,15 @@
 __code replaceNode1_stub(struct Context* context) {
     struct Node* newnewNode = &ALLOCATE(context, Node)->node;
     goto replaceNode1(context,
-                     &context->data[D_Traverse]->Traverse,
+                     &context->data[D_RedBlackTree]->RedBlackTree,
                      &context->data[D_Node]->node,
-                     context->data[D_Traverse]->Traverse.current,
-                     context->data[D_Traverse]->Traverse.previous,
+                     context->data[D_RedBlackTree]->RedBlackTree.current,
+                     context->data[D_RedBlackTree]->RedBlackTree.previous,
                      newnewNode,
-                     context->data[D_Traverse]->Traverse.result);
+                     context->data[D_RedBlackTree]->RedBlackTree.result);
 }
 
-__code insertNode(struct Context* context, struct Traverse* traverse, struct Stack *nodeStack, struct Node* node, struct Node* newNode) {
+__code insertNode(struct Context* context, struct RedBlackTree* traverse, struct Stack *nodeStack, struct Node* node, struct Node* newNode) {
     *newNode = *node;
     newNode->color = Red;
     traverse->current = newNode;
@@ -122,13 +121,13 @@
 
 __code insertNode_stub(struct Context* context) {
     goto insertNode(context,
-                    &context->data[D_Traverse]->Traverse,
+                    &context->data[D_RedBlackTree]->RedBlackTree,
                     &context->data[D_Stack]->stack,
                     &context->data[D_Node]->node,
-                    context->data[D_Traverse]->Traverse.newNode);
+                    context->data[D_RedBlackTree]->RedBlackTree.newNode);
 }
 
-__code insertCase1(struct Context* context,struct Traverse* traverse, struct Tree* tree,struct Node *parent, struct Node *grandparent) {
+__code insertCase1(struct Context* context,struct RedBlackTree* traverse, struct RedBlackTree* tree,struct Node *parent, struct Node *grandparent) {
     if (parent != NULL) {
         traverse->parent = parent;
         traverse->grandparent = grandparent;
@@ -140,13 +139,13 @@
 
 __code insertCase1_stub(struct Context* context) {
     goto insertCase1(context, 
-        &context->data[D_Traverse]->Traverse,
-        &context->data[D_Tree]->tree,
+        &context->data[D_RedBlackTree]->RedBlackTree,
+        &context->data[D_Tree]->Tree,
         &context->data[D_Stack]->stack.data->node,
         &context->data[D_Stack]->stack.data1->node);
 }
 
-__code insertCase2(struct Context* context, struct Traverse* traverse) {
+__code insertCase2(struct Context* context, struct RedBlackTree* traverse) {
     if (traverse->parent->color == Black) {
         goto meta(context, C_stackClear);
     }
@@ -154,10 +153,10 @@
 }
 
 __code insertCase2_stub(struct Context* context) {
-    goto insertCase2(context, &context->data[D_Traverse]->Traverse); 
+    goto insertCase2(context, &context->data[D_RedBlackTree]->RedBlackTree); 
 }
 
-__code insertCase3(struct Context* context, struct Traverse* traverse, struct Stack* nodeStack) {
+__code insertCase3(struct Context* context, struct RedBlackTree* traverse, struct Stack* nodeStack) {
     struct Node* uncle;
 
     if (traverse->grandparent->left == traverse->parent)
@@ -179,12 +178,12 @@
 }
 
 __code insertCase3_stub(struct Context* context) {
-    goto insertCase3(context, &context->data[D_Traverse]->Traverse,
+    goto insertCase3(context, &context->data[D_RedBlackTree]->RedBlackTree,
                      &context->data[D_Stack]->stack
         );
 }
 
-__code insertCase4(struct Context* context, struct Traverse* traverse, struct RotateTree* rotateTree) {
+__code insertCase4(struct Context* context, struct RedBlackTree* traverse, struct RotateTree* rotateTree) {
     struct Stack* nodeStack = traverse->nodeStack;
 
     if ((traverse->current == traverse->parent->right) && (traverse->parent == traverse->grandparent->left)) {
@@ -213,20 +212,20 @@
 }
 
 __code insertCase4_stub(struct Context* context) {
-    goto insertCase4(context, &context->data[D_Traverse]->Traverse, &context->data[D_RotateTree]->rotateTree);
+    goto insertCase4(context, &context->data[D_RedBlackTree]->RedBlackTree, &context->data[D_RotateTree]->rotateTree);
 }
 
-__code insertCase5(struct Context* context, struct Traverse* traverse,struct Stack *nodeStack) {
+__code insertCase5(struct Context* context, struct RedBlackTree* traverse,struct Stack *nodeStack) {
     nodeStack->stack = (union Data*)traverse->nodeStack;
     nodeStack->next = C_insertCase51;
     goto meta(context, traverse->nodeStack->pop2);
 }
 
 __code insertCase5_stub(struct Context* context) {
-    goto insertCase5(context, &context->data[D_Traverse]->Traverse, &context->data[D_Stack]->stack);
+    goto insertCase5(context, &context->data[D_RedBlackTree]->RedBlackTree, &context->data[D_Stack]->stack);
 }
 
-__code insertCase51(struct Context* context, struct Traverse* traverse, struct RotateTree *rotateTree, struct Node* current, struct Node* parent, struct Node* grandparent) {
+__code insertCase51(struct Context* context, struct RedBlackTree* traverse, struct RotateTree *rotateTree, struct Node* current, struct Node* parent, struct Node* grandparent) {
     traverse->parent = parent;
     traverse->grandparent = grandparent;
 
@@ -247,21 +246,21 @@
 __code insertCase51_stub(struct Context* context) {
     struct Node* parent = &context->data[D_Stack]->stack.data->node;
     struct Node* grandparent = &context->data[D_Stack]->stack.data1->node;
-    goto insertCase51(context, &context->data[D_Traverse]->Traverse,&context->data[D_RotateTree]->rotateTree, context->data[D_Traverse]->Traverse.current, parent, grandparent);
+    goto insertCase51(context, &context->data[D_RedBlackTree]->RedBlackTree,&context->data[D_RotateTree]->rotateTree, context->data[D_RedBlackTree]->RedBlackTree.current, parent, grandparent);
 }
 
-__code rotateLeft(struct Context* context, struct Traverse* traverse,struct Stack* nodeStack) {
+__code rotateLeft(struct Context* context, struct RedBlackTree* traverse,struct Stack* nodeStack) {
     nodeStack->stack = (union Data*)traverse->nodeStack;
     nodeStack->next = C_rotateLeft1;
     goto meta(context, traverse->nodeStack->get);
 }
 
 __code rotateLeft_stub(struct Context* context) {
-    struct Traverse* traverse = context->data[D_RotateTree]->rotateTree.traverse;
+    struct RedBlackTree* traverse = context->data[D_RotateTree]->rotateTree.traverse;
     goto rotateLeft(context, traverse, &context->data[D_Stack]->stack);
 }
 
-__code rotateLeft1(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node *parent,struct RotateTree *rotateTree) {
+__code rotateLeft1(struct Context* context, struct Node* node, struct RedBlackTree* traverse, struct Node *parent,struct RotateTree *rotateTree) {
     struct Node* tmp = node->right;
 
     if (parent) {
@@ -270,7 +269,7 @@
         else
             parent->right = tmp;
     } else {
-        tree->root = tmp;
+        traverse->root = tmp;
     }
 
     node->right = tmp->left;
@@ -281,28 +280,28 @@
 }
     
 __code rotateLeft1_stub(struct Context* context) {
-    struct Traverse* traverse = context->data[D_RotateTree]->rotateTree.traverse;
+    struct RedBlackTree* traverse = context->data[D_RotateTree]->rotateTree.traverse;
     struct Node* parent = &context->data[D_Stack]->stack.data->node;
     goto rotateLeft1(context,
                     traverse->current,
-                    &context->data[D_Tree]->tree,
+                    &context->data[D_Tree]->Tree,
                     traverse,
                     parent,
                     &context->data[D_RotateTree]->rotateTree);
 }
 
-__code rotateRight(struct Context* context, struct Traverse* traverse,struct Stack *nodeStack) {
+__code rotateRight(struct Context* context, struct RedBlackTree* traverse,struct Stack *nodeStack) {
     nodeStack->stack = (union Data*)traverse->nodeStack;
     nodeStack->next = C_rotateRight1;
     goto meta(context, traverse->nodeStack->get);
 }
 
 __code rotateRight_stub(struct Context* context) {
-    struct Traverse* traverse = context->data[D_RotateTree]->rotateTree.traverse;
+    struct RedBlackTree* traverse = context->data[D_RotateTree]->rotateTree.traverse;
     goto rotateLeft(context, traverse, &context->data[D_Stack]->stack);
 }
 
-__code rotateRight1(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse,struct Node *parent,struct RotateTree *rotateTree) {
+__code rotateRight1(struct Context* context, struct Node* node, struct RedBlackTree* traverse,struct Node *parent,struct RotateTree *rotateTree) {
     struct Node* tmp = node->left;
     
     if (parent) {
@@ -311,7 +310,7 @@
         else
             parent->right = tmp;
     } else {
-        tree->root = tmp;
+        traverse->root = tmp;
     }
 
     node->left = tmp->right;
@@ -322,17 +321,17 @@
 }
 
 __code rotateRight1_stub(struct Context* context) {
-    struct Traverse* traverse = context->data[D_RotateTree]->rotateTree.traverse;
+    struct RedBlackTree* traverse = context->data[D_RotateTree]->rotateTree.traverse;
     struct Node* parent = &context->data[D_Stack]->stack.data->node;
     goto rotateRight1(context,
                      traverse->current,
-                     &context->data[D_Tree]->tree,
+                     &context->data[D_Tree]->Tree,
                      traverse,
                      parent,
                      &context->data[D_RotateTree]->rotateTree);
 }
 
-__code stackClear(struct Context* context, struct Traverse* traverse,struct Stack *nodeStack) {
+__code stackClear(struct Context* context, struct RedBlackTree* traverse,struct Stack *nodeStack) {
     traverse->current = 0;
     nodeStack->stack = (union Data*)traverse->nodeStack;
     nodeStack->next = context->next;
@@ -340,11 +339,11 @@
 }
 
 __code stackClear_stub(struct Context* context) {
-    goto stackClear(context, &context->data[D_Traverse]->Traverse,&context->data[D_Stack]->stack);
+    goto stackClear(context, &context->data[D_RedBlackTree]->RedBlackTree,&context->data[D_Stack]->stack);
 }
     
 
-__code getRedBlackTree(struct Context* context, struct Tree* tree, struct Traverse* traverse) {
+__code getRedBlackTree(struct Context* context, struct RedBlackTree* traverse) {
     if (tree->root) {
         traverse->current = tree->root;
 
@@ -355,10 +354,10 @@
 }
 
 __code getRedBlackTree_stub(struct Context* context) {
-    goto get(context, &context->data[D_Tree]->tree, &context->data[D_Traverse]->Traverse);
+    goto get(context, &context->data[D_Tree]->tree, &context->data[D_RedBlackTree]->RedBlackTree);
 }
 
-__code search(struct Context* context, struct Traverse* traverse, struct Node* node) {
+__code search(struct Context* context, struct RedBlackTree* traverse, struct Node* node) {
     // compare(context, traverse, traverse->current->key, node->key);
     traverse->result = compare(traverse->current, node);
     if (traverse->result == EQ) {
@@ -378,7 +377,7 @@
 }
 
 __code search_stub(struct Context* context) {
-    goto search(context, &context->data[D_Traverse]->Traverse, &context->data[D_Node]->node);
+    goto search(context, &context->data[D_RedBlackTree]->RedBlackTree, &context->data[D_Node]->node);
 }
 
 /* /\* __code delete(struct Context* context, struct Tree* tree) { *\/ */