Mercurial > hg > Members > innparusu > Gears

changeset 91:1e074c3878c7

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
modify tree
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Tue, 26 Jan 2016 07:46:26 +0900
parents 4b5bf5b40970
children 851da1107223
files src/parallel_execution/compare.c src/parallel_execution/context.c src/parallel_execution/context.h src/parallel_execution/main.c src/parallel_execution/rb_tree.c
diffstat 5 files changed, 124 insertions(+), 77 deletions(-) [+]
line wrap: on
line diff
--- a/src/parallel_execution/compare.c	Tue Jan 26 06:47:35 2016 +0900
+++ b/src/parallel_execution/compare.c	Tue Jan 26 07:46:26 2016 +0900
@@ -1,11 +1,11 @@
 #include "context.h"
 
-void compare(struct Context* context, struct Tree* tree, int key1, int key2) {
+void compare(struct Context* context, struct Traverse* traverse, int key1, int key2) {
     if (key1 == key2) {
-        tree->result = EQ;
+        traverse->result = EQ;
     } else if (key1 < key2) {
-        tree->result = GT;
+        traverse->result = GT;
     } else {
-        tree->result = LT;
+        traverse->result = LT;
     }
 }
--- a/src/parallel_execution/context.c	Tue Jan 26 06:47:35 2016 +0900
+++ b/src/parallel_execution/context.c	Tue Jan 26 07:46:26 2016 +0900
@@ -53,6 +53,7 @@
 extern __code putQueue2_stub(struct Context*);
 extern __code putQueue3_stub(struct Context*);
 extern __code putQueue4_stub(struct Context*);
+extern __code getQueue_stub(struct Context*);
 extern __code exit_code(struct Context*);
 
 __code initContext(struct Context* context) {
@@ -110,6 +111,7 @@
     context->code[PutQueue2]     = putQueue2_stub;
     context->code[PutQueue3]     = putQueue3_stub;
     context->code[PutQueue4]     = putQueue4_stub;
+    context->code[GetQueue]      = getQueue_stub;
     context->code[Exit]       = exit_code;
     
     context->heap = context->heapStart;
@@ -123,6 +125,9 @@
     context->data[Tree] = context->heap;
     context->heap += sizeof(struct Tree);
 
+    context->data[Traverse] = context->heap;
+    context->heap += sizeof(struct Traverse);
+
     context->data[Node] = context->heap;
     context->heap += sizeof(struct Node);
     
@@ -145,9 +150,7 @@
     allocate->size = 0;
 
     struct Tree* tree = &context->data[Tree]->tree;
-    context->tree = tree;
     tree->root = 0;
-    tree->current = 0;
 
     struct Node* node = &context->data[Node]->node;
     node->key = 0;
@@ -163,7 +166,6 @@
     element->next = 0;
 
     struct Queue* activeQueue = &context->data[ActiveQueue]->queue;
-    context->activeQueue = activeQueue;
     activeQueue->first = 0;
     activeQueue->last = 0;
     activeQueue->count = 0;
--- a/src/parallel_execution/context.h	Tue Jan 26 06:47:35 2016 +0900
+++ b/src/parallel_execution/context.h	Tue Jan 26 07:46:26 2016 +0900
@@ -55,6 +55,7 @@
     PutQueue2,
     PutQueue3,
     PutQueue4,
+    GetQueue,
     Exit,
 };
 
@@ -68,6 +69,7 @@
     Worker,
     Allocate,
     Tree,
+    Traverse,
     Node,
     LoopCounter,
     Element,
@@ -86,8 +88,6 @@
     stack_ptr node_stack;
     int dataNum;
     union Data **data;
-    struct Queue* activeQueue;
-    struct Tree* tree;
 };
 
 union Data {
@@ -116,11 +116,12 @@
         int* array;
     } array;
     struct Tree {
-        enum Code next;
         struct Node* root;
+    } tree;
+    struct Traverse {
         struct Node* current;
         int result;
-    } tree;
+    } traverse;
     struct Node {
         // need to tree
         enum Code next;
--- a/src/parallel_execution/main.c	Tue Jan 26 06:47:35 2016 +0900
+++ b/src/parallel_execution/main.c	Tue Jan 26 07:46:26 2016 +0900
@@ -26,9 +26,10 @@
 }
 
 __code code1(struct Context* context) {
-    print_queue(context->activeQueue->first);
-    puts("");
-    print_tree(context->tree->root);
+    puts("queue");
+    print_queue(context->data[ActiveQueue]->queue.first);
+    puts("tree");
+    print_tree(context->data[Tree]->tree.root);
 
     goto meta(context, Exit);
 }
@@ -166,12 +167,38 @@
     goto putQueue4(context, &context->data[ActiveQueue]->queue, &context->data[context->dataNum]->element);
 }
 
+__code getQueue(struct Context* context, struct Queue* queue) {
+    if (queue->count == 0)
+        return;
+
+    struct Element* first = queue->first;
+    if (__sync_bool_compare_and_swap(&queue->first, first, first->next)) {
+        queue->count--;
+        
+        context->next = GetQueue;
+        stack_push(context->code_stack, &context->next);
+
+        context->next = first->task->code;
+        stack_push(context->code_stack, &context->next);
+
+        goto meta(context, Search);
+    } else {
+        goto meta(context, GetQueue);
+    }
+}
+
+__code getQueue_stub(struct Context* context) {
+    goto getQueue(context, &context->data[ActiveQueue]->queue);
+}
+
 __code createWorker(struct Context* context, struct LoopCounter* loopCounter, struct Worker* worker) {
     int i = loopCounter->i;
 
     if (i < worker->num) {
         struct Context* worker_context = &worker->contexts[i];
-        worker_context->next = Code1;
+        worker_context->next = GetQueue;
+        worker_context->data[Tree] = context->data[Tree];
+        worker_context->data[ActiveQueue] = context->data[ActiveQueue];
         pthread_create(&worker_context->thread, NULL, (void*)&start_code, worker_context);
         loopCounter->i++;
 
--- a/src/parallel_execution/rb_tree.c	Tue Jan 26 06:47:35 2016 +0900
+++ b/src/parallel_execution/rb_tree.c	Tue Jan 26 07:46:26 2016 +0900
@@ -4,11 +4,11 @@
 #include "origin_cs.h"
 
 extern void allocator(struct Context* context);
-extern void compare(struct Context* context, struct Tree* tree, int key1, int key2);
+extern void compare(struct Context* context, struct Traverse* traverse, int key1, int key2);
 
 extern int num;
 
-__code put(struct Context* context, struct Tree* tree, struct Node* root, struct Allocate* allocate) {
+__code put(struct Context* context, struct Tree* tree, struct Traverse* traverse, struct Node* root, struct Allocate* allocate) {
     allocate->size = sizeof(struct Node);
     allocator(context);
     
@@ -20,8 +20,8 @@
     tree->root = &context->data[context->dataNum]->node;
     
     if (root) {
-        tree->current = root;
-        compare(context, tree, tree->current->key, context->data[Node]->node.key);
+        traverse->current = root;
+        compare(context, traverse, traverse->current->key, context->data[Node]->node.key);
 
         goto meta(context, Replace);
     }
@@ -30,10 +30,14 @@
 }
 
 __code put_stub(struct Context* context) {
-    goto put(context, &context->data[Tree]->tree, context->data[Tree]->tree.root, &context->data[Allocate]->allocate);
+    goto put(context,
+             &context->data[Tree]->tree,
+             &context->data[Traverse]->traverse,
+             context->data[Tree]->tree.root,
+             &context->data[Allocate]->allocate);
 }
 
-__code replaceNode(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) {
+__code replaceNode(struct Context* context, struct Traverse* traverse, struct Node* oldNode, struct Node* newNode, int result) {
     *newNode = *oldNode;
     stack_push(context->node_stack, &newNode);
 
@@ -43,17 +47,17 @@
         stack_pop(context->code_stack, &context->next);
         goto meta(context, context->next);
     } else if (result == GT) {
-        tree->current = oldNode->right;
+        traverse->current = oldNode->right;
         newNode->right = context->heap;
     } else {
-        tree->current = oldNode->left;
+        traverse->current = oldNode->left;
         newNode->left = context->heap;
     }
 
     allocator(context);
 
-    if (tree->current) {
-        compare(context, tree, tree->current->key, context->data[Node]->node.key);
+    if (traverse->current) {
+        compare(context, traverse, traverse->current->key, context->data[Node]->node.key);
         goto meta(context, Replace);
     }
     
@@ -61,20 +65,27 @@
 }
 
 __code replaceNode_stub(struct Context* context) {
-    goto replaceNode(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result);
+    goto replaceNode(context,
+                     &context->data[Traverse]->traverse,
+                     context->data[Traverse]->traverse.current,
+                     &context->data[context->dataNum]->node,
+                     context->data[Traverse]->traverse.result);
 }
 
-__code insertNode(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) {
+__code insertNode(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* newNode) {
     node->color = Red;
     *newNode = *node;
     
-    tree->current = newNode;
+    traverse->current = newNode;
 
     goto meta(context, InsertCase1);
 }
 
 __code insertNode_stub(struct Context* context) {
-    goto insertNode(context, &context->data[Tree]->tree, &context->data[Node]->node, &context->data[context->dataNum]->node);
+    goto insertNode(context,
+                    &context->data[Traverse]->traverse,
+                    &context->data[Node]->node,
+                    &context->data[context->dataNum]->node);
 }
 
 __code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) {
@@ -88,7 +99,7 @@
 }
 
 __code insert1_stub(struct Context* context) {
-    goto insertCase1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+    goto insertCase1(context, &context->data[Tree]->tree, context->data[Traverse]->traverse.current);
 }
 
 __code insertCase2(struct Context* context, struct Node* current) {
@@ -105,10 +116,10 @@
 }
 
 __code insert2_stub(struct Context* context) {
-    goto insertCase2(context, context->data[Tree]->tree.current);
+    goto insertCase2(context, context->data[Traverse]->traverse.current);
 }
 
-__code insertCase3(struct Context* context, struct Tree* tree, struct Node* current) {
+__code insertCase3(struct Context* context, struct Traverse* traverse, struct Node* current) {
     struct Node* parent;
     struct Node* uncle;
     struct Node* grandparent;
@@ -125,7 +136,7 @@
         parent->color = Black;
         uncle->color = Black;
         grandparent->color = Red;
-        tree->current = grandparent;
+        traverse->current = grandparent;
         goto meta(context, InsertCase1);
     }
 
@@ -136,10 +147,10 @@
 }
 
 __code insert3_stub(struct Context* context) {
-    goto insertCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+    goto insertCase3(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current);
 }
 
-__code insertCase4(struct Context* context, struct Tree* tree, struct Node* current) {
+__code insertCase4(struct Context* context, struct Traverse* traverse, struct Node* current) {
     struct Node* parent;
     struct Node* grandparent;
 
@@ -148,7 +159,7 @@
 
     stack_push(context->node_stack, &grandparent);
 
-    tree->current = parent;
+    traverse->current = parent;
 
     if ((current == parent->right) && (parent == grandparent->left)) {
         context->next = InsertCase4_1;
@@ -163,35 +174,35 @@
     }
 
     stack_push(context->node_stack, &parent);
-    tree->current = current;
+    traverse->current = current;
     goto meta(context, InsertCase5);
 }
 
 __code insert4_stub(struct Context* context) {
-    goto insertCase4(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+    goto insertCase4(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current);
 }
 
-__code insertCase4_1(struct Context* context, struct Tree* tree) {
-    stack_push(context->node_stack, &tree->current);
-    tree->current = tree->current->left;
+__code insertCase4_1(struct Context* context, struct Traverse* traverse) {
+    stack_push(context->node_stack, &traverse->current);
+    traverse->current = traverse->current->left;
     goto meta(context, InsertCase5);
 }
 
 __code insert4_1_stub(struct Context* context) {
-    goto insertCase4_1(context, &context->data[Tree]->tree);
+    goto insertCase4_1(context, &context->data[Traverse]->traverse);
 }   
 
-__code insertCase4_2(struct Context* context, struct Tree* tree) {
-    stack_push(context->node_stack, &tree->current);
-    tree->current = tree->current->right;
+__code insertCase4_2(struct Context* context, struct Traverse* traverse) {
+    stack_push(context->node_stack, &traverse->current);
+    traverse->current = traverse->current->right;
     goto meta(context, InsertCase5);
 }
 
 __code insert4_2_stub(struct Context* context) {
-    goto insertCase4_2(context, &context->data[Tree]->tree);
+    goto insertCase4_2(context, &context->data[Traverse]->traverse);
 }   
 
-__code insertCase5(struct Context* context, struct Tree* tree, struct Node* current) {
+__code insertCase5(struct Context* context, struct Traverse* traverse, struct Node* current) {
     struct Node* parent;
     struct Node* grandparent;
 
@@ -201,7 +212,7 @@
     parent->color = Black;
     grandparent->color = Red;
 
-    tree->current = grandparent;
+    traverse->current = grandparent;
 
     if ((current == parent->left) && (parent == grandparent->left))
         goto meta(context, RotateR);
@@ -210,10 +221,10 @@
 }
 
 __code insert5_stub(struct Context* context) {
-    goto insertCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
+    goto insertCase5(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current);
 }
 
-__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree) {
+__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) {
     struct Node* tmp = node->right;
     struct Node* parent = 0;
     
@@ -232,17 +243,20 @@
     
     node->right = tmp->left;
     tmp->left = node;
-    tree->current = tmp;
+    traverse->current = tmp;
     
     stack_pop(context->code_stack, &context->next);
     goto meta(context, context->next);
 }
     
 __code rotateLeft_stub(struct Context* context) {
-    goto rotateLeft(context, context->data[Tree]->tree.current, &context->data[Tree]->tree);
+    goto rotateLeft(context,
+                    context->data[Traverse]->traverse.current,
+                    &context->data[Tree]->tree,
+                    &context->data[Traverse]->traverse);
 }
 
-__code rotateRight(struct Context* context, struct Node* node, struct Tree* tree) {
+__code rotateRight(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) {
     struct Node* tmp = node->left;
     struct Node* parent = 0;
     
@@ -261,28 +275,31 @@
     
     node->left = tmp->right;
     tmp->right = node;
-    tree->current = tmp;
+    traverse->current = tmp;
     
     stack_pop(context->code_stack, &context->next);
     goto meta(context, context->next);
 }
 
 __code rotateRight_stub(struct Context* context) {
-    goto rotateRight(context, context->data[Tree]->tree.current, &context->data[Tree]->tree);
+    goto rotateRight(context,
+                     context->data[Traverse]->traverse.current,
+                     &context->data[Tree]->tree,
+                     &context->data[Traverse]->traverse);
 }
 
-__code stackClear(struct Context* context, stack_ptr node_stack, struct Tree* tree) {
-    if (stack_pop(node_stack, &tree->current) == 0)
+__code stackClear(struct Context* context, stack_ptr node_stack, struct Traverse* traverse) {
+    if (stack_pop(node_stack, &traverse->current) == 0)
         goto meta(context, StackClear);
 
-    tree->current = 0;
+    traverse->current = 0;
 
     stack_pop(context->code_stack, &context->next);
     goto meta(context, context->next);
 }
 
 __code stackClear_stub(struct Context* context) {
-    goto stackClear(context, context->node_stack, &context->data[Tree]->tree);
+    goto stackClear(context, context->node_stack, &context->data[Traverse]->traverse);
 }
     
 
@@ -301,29 +318,29 @@
 /* /\*     goto get(context, &context->data[Tree]->tree); *\/ */
 /* /\* } *\/ */
 
-/* /\* __code search(struct Context* context, struct Tree* tree, struct Node* node) { *\/ */
-/* /\*     compare(context, tree, tree->current->key, node->key); *\/ */
+__code search(struct Context* context, struct Traverse* traverse, struct Node* node) {
+    compare(context, traverse, traverse->current->key, node->key);
     
-/* /\*     if (tree->result == EQ) { *\/ */
-/* /\*         *node = *tree->current; *\/ */
+    if (traverse->result == EQ) {
+        *node = *traverse->current;
         
-/* /\*         goto meta(context, context->next); *\/ */
-/* /\*     } else if (tree->result == GT) { *\/ */
-/* /\*         tree->current = tree->current->right; *\/ */
-/* /\*     } else { *\/ */
-/* /\*         tree->current = tree->current->left; *\/ */
-/* /\*     } *\/ */
+        goto meta(context, context->next);
+    } else if (traverse->result == GT) {
+        traverse->current = traverse->current->right;
+    } else {
+        traverse->current = traverse->current->left;
+    }
         
-/* /\*     if (tree->current) *\/ */
-/* /\*         goto meta(context, Search); *\/ */
+    if (traverse->current)
+        goto meta(context, Search);
 
-/* /\*     stack_pop(context->code_stack, &context->next); *\/ */
-/* /\*     goto meta(context, context->next); *\/ */
-/* /\* } *\/ */
+    stack_pop(context->code_stack, &context->next);
+    goto meta(context, context->next);
+}
 
-/* /\* __code search_stub(struct Context* context) { *\/ */
-/* /\*     goto search(context, &context->data[Tree]->tree, &context->data[Node]->node); *\/ */
-/* /\* } *\/ */
+__code search_stub(struct Context* context) {
+    goto search(context, &context->data[Traverse]->traverse, &context->data[Node]->node);
+}
 
 /* /\* __code delete(struct Context* context, struct Tree* tree) { *\/ */
 /* /\*     if (tree->root) { *\/ */