Mercurial > hg > GearsTemplate

changeset 117:a574ba0da60f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
add comment rb_tree
author ikkun
date Wed, 14 Sep 2016 20:43:37 +0900
parents f57e9ffa7960 (current diff) c53f105a48c1 (diff)
children 32773f506410
files src/parallel_execution/CMakeLists.txt src/parallel_execution/main.c src/parallel_execution/rb_tree.c
diffstat 8 files changed, 41 insertions(+), 36 deletions(-) [+]
line wrap: on
line diff
--- a/Dockerfile	Wed Sep 14 20:35:21 2016 +0900
+++ b/Dockerfile	Wed Sep 14 20:43:37 2016 +0900
@@ -1,7 +1,7 @@
 # docker build -t gears .  # build container
 # docker run gears         # launch container and attach
 
-FROM fedora
+FROM fedora:23
 
 WORKDIR /root
 RUN dnf update -y
--- a/src/CMakeLists.txt	Wed Sep 14 20:35:21 2016 +0900
+++ b/src/CMakeLists.txt	Wed Sep 14 20:43:37 2016 +0900
@@ -4,7 +4,7 @@
 set(CMAKE_VERBOSE_MAKEFILE 1)
 
 # set compiler
-set(CMAKE_C_COMPILER cbclang)
+set(CMAKE_C_COMPILER $ENV{CBC_COMPILER})
 
 # compile option
 add_definitions("-Wall -g -O0")
--- a/src/parallel_execution/context.c	Wed Sep 14 20:35:21 2016 +0900
+++ b/src/parallel_execution/context.c	Wed Sep 14 20:43:37 2016 +0900
@@ -149,7 +149,7 @@
     counter->i = 0;
 
     struct Element* element = ALLOC_DATA(context, Element);
-    element->task = 0;
+    element->data = 0;
     element->next = 0;
 
     ALLOC_DATA(context, Time);
--- a/src/parallel_execution/context.h	Wed Sep 14 20:35:21 2016 +0900
+++ b/src/parallel_execution/context.h	Wed Sep 14 20:43:37 2016 +0900
@@ -134,7 +134,7 @@
         enum Code code;
         int key;
         struct Queue* waitMe;
-        struct OdsQueue* waitI;
+        struct Queue* waitI;
         int idsCount;
     } task;
     struct Queue {
@@ -143,7 +143,7 @@
         int count;
     } queue;
     struct Element {
-        struct Task* task;
+        union Data* data;
         struct Element* next;
     } element;
     struct Array {
@@ -179,13 +179,10 @@
     struct OutPutDataSegments {
         union Data **data;
     } ods;
-    struct OdsQueue {
-        struct OdsElement* first;
-        struct OdsElement* last;
-        int count;
-    } odsQueue;
-    struct OdsElement {
-        struct OutPutDataSegments* ods;
-        struct OdsElement* next;
-    } odsElement;
 };
+
+union MetaData {
+    struct Queue waitMeTasks;
+    struct Queue waitI;
+};
+
--- a/src/parallel_execution/dependency.c	Wed Sep 14 20:35:21 2016 +0900
+++ b/src/parallel_execution/dependency.c	Wed Sep 14 20:43:37 2016 +0900
@@ -8,7 +8,7 @@
 }
 
 __code waitFor1(struct Context* context, struct Task* master, struct Task* slave, struct Element* element) {
-    element->task = slave;
+    element->data = (union Data *)slave;
     // enqueue waitMe
     goto meta_waitFor(context, master->waitMe, PutQueue1);
 }
@@ -35,15 +35,13 @@
 
 __code spawnTask(struct Context* context, struct Task* task, struct Element* element, struct Queue* activeQueue, struct Queue* waitQueue) {
     //printf("spawn Task\n");
+    element->data = (union Data *)task;
     if (task->waitI->count == task->idsCount) {
         //printf("put ActiveQueue\n");
-        element->task = task;
         // enqueue activeQueue
         goto meta_spawnTask(context, activeQueue, PutQueue1);
-    }
-    else {
+    } else {
         //printf("put WaitQueue\n");
-        element->task = task;
         // enqueue waitQueue
         goto meta_spawnTask(context, waitQueue, PutQueue1);
     }
--- a/src/parallel_execution/main.c	Wed Sep 14 20:35:21 2016 +0900
+++ b/src/parallel_execution/main.c	Wed Sep 14 20:43:37 2016 +0900
@@ -14,7 +14,7 @@
 
 void print_queue(struct Element* element) {
     while (element) {
-        printf("%d\n", element->task->key);
+        printf("%d\n", ((struct Task *)(element->data))->key);
         element = element->next;
     }
 }
@@ -52,7 +52,7 @@
     int i = loopCounter->i;
 
     if (i < length) {
-        //        printf("%d\n", array->array[i]);
+           //printf("%d\n", array->array[i]);
         if (array->array[i] == (i*2)) {
             loopCounter->i++;
             goto meta(context, Code2);
@@ -129,7 +129,7 @@
 }
 
 __code createTask3(struct Context* context, struct Allocate* allocate) {
-    allocate->size = sizeof(struct OdsQueue);
+    allocate->size = sizeof(struct Queue);
     allocator(context);
     goto meta(context, CreateTask4);
 }
@@ -143,7 +143,7 @@
     goto (context->code[next])(context);
 }
 
-__code createTask4(struct Context* context, struct LoopCounter* loopCounter, struct Task* task, struct Queue* waitMe, struct OdsQueue* waitI, struct Element* element, struct Queue* activeQueue) {
+__code createTask4(struct Context* context, struct LoopCounter* loopCounter, struct Task* task, struct Queue* waitMe, struct Queue* waitI, struct Element* element, struct Queue* activeQueue) {
     int i = loopCounter->i;
 
     waitMe->first = 0;
@@ -160,7 +160,7 @@
     task->waitI = waitI;
     task->idsCount = 0;
 
-    element->task = task;
+    element->data = (union Data *)task;
 
     context->next = CreateData1;
     loopCounter->i++;
@@ -173,7 +173,7 @@
             &context->data[LoopCounter]->loopCounter,
             &context->data[context->dataNum-2]->task,
             &context->data[context->dataNum-1]->queue,
-            &context->data[context->dataNum]->odsQueue,
+            &context->data[context->dataNum]->queue,
             &context->data[Element]->element,
             &context->data[ActiveQueue]->queue);
 }
@@ -188,7 +188,7 @@
 //    task->waitI = waitI;
 //    task->idsCount = 1;
 //
-//    element->task = task;
+//    element->data = (union Data *)task;
 //
 //    context->next = CreateData1;
 //    loopCounter->i++;
@@ -211,7 +211,7 @@
 //
 //    task->code = TaskB;
 //    task->key = i;
-//    element->task = task;
+//    element->data = (union Data *)task;
 //
 //    context->next = CreateData1;
 //    loopCounter->i++;
@@ -237,7 +237,7 @@
 }
 
 __code putQueue2(struct Context* context, struct Element* new_element, struct Element* element, struct Queue* queue) {
-    new_element->task = element->task;
+    new_element->data = element->data;
 
     if (queue->first)
         goto meta(context, PutQueue3);
--- a/src/parallel_execution/rb_tree.c	Wed Sep 14 20:35:21 2016 +0900
+++ b/src/parallel_execution/rb_tree.c	Wed Sep 14 20:43:37 2016 +0900
@@ -9,11 +9,14 @@
 extern int num;
 
 __code put(struct Context* context, struct Tree* tree, struct Traverse* traverse, struct Node* root, struct Allocate* allocate) {
+    // tree->root=allocator(context,struct Node);
     allocate->size = sizeof(struct Node);
     allocator(context);
-    
+
+    // we don't need this push
     stack_push(context->code_stack, &context->next);
 
+    // after insert or replace, go to stack clear direct, we don't need this push 
     context->next = StackClear;
     stack_push(context->code_stack, &context->next);
     
@@ -21,6 +24,7 @@
     
     if (root) {
         traverse->current = root;
+        // traverse->result=compare(...)
         compare(context, traverse, traverse->current->key, context->data[Node]->node.key);
 
         goto meta(context, Replace);
@@ -43,12 +47,13 @@
 
     if (result == EQ) {
         newNode->value = context->data[Node]->node.value;
-
+   
+        // go to stack clear
         stack_pop(context->code_stack, &context->next);
         goto meta(context, context->next);
     } else if (result == GT) {
         traverse->current = oldNode->right;
-        newNode->right = context->heap;
+        newNode->right = context->heap; // allocator(context,struct Node)
     } else {
         traverse->current = oldNode->left;
         newNode->left = context->heap;
@@ -68,7 +73,7 @@
     goto replaceNode(context,
                      &context->data[Traverse]->traverse,
                      context->data[Traverse]->traverse.current,
-                     &context->data[context->dataNum]->node,
+                     &context->data[context->dataNum]->node, // new Node
                      context->data[Traverse]->traverse.result);
 }
 
@@ -88,12 +93,14 @@
                     &context->data[context->dataNum]->node);
 }
 
+// parent, grandparent and Node stack are input data segments
 __code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) {
-    if (!isEmpty(context->node_stack))
+    if (!isEmpty(context->node_stack)) // parent!=null
         goto meta(context, InsertCase2);
 
     tree->root->color = Black;
 
+    //go to stack clear
     stack_pop(context->code_stack, &context->next);
     goto meta(context, context->next);
 }
@@ -133,6 +140,7 @@
         uncle = grandparent->left;
 
     if (uncle && (uncle->color == Red)) {
+        // do insertcase1 on grandparent, stack must be pop by two
         parent->color = Black;
         uncle->color = Black;
         grandparent->color = Red;
@@ -224,10 +232,12 @@
     goto insertCase5(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current);
 }
 
+// put rotateLeft's continuation as argument
 __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) {
     struct Node* tmp = node->right;
     struct Node* parent = 0;
-    
+
+    // if you have a pararent as an argument , we don't need stack operation   
     stack_pop(context->node_stack, &parent);
 
     if (parent) {
--- a/src/parallel_execution/worker.c	Wed Sep 14 20:35:21 2016 +0900
+++ b/src/parallel_execution/worker.c	Wed Sep 14 20:43:37 2016 +0900
@@ -14,8 +14,8 @@
         context->next = GetQueue;
         stack_push(context->code_stack, &context->next);
 
-        context->next = first->task->code;
-        node->key = first->task->key;
+        context->next = ((struct Task *)(first->data))->code;
+        node->key = ((struct Task *)(first->data))->key;
 
         struct Traverse *t = &context->data[Traverse]->traverse;
         t->next = GetQueue;