changeset 127:a574ba0da60f

add comment rb_tree
author ikkun
date Wed, 14 Sep 2016 20:43:37 +0900
parents f57e9ffa7960 (diff) c53f105a48c1 (current diff)
children 32773f506410
files src/parallel_execution/CMakeLists.txt src/parallel_execution/main.c src/parallel_execution/rb_tree.c
diffstat 4 files changed, 50 insertions(+), 38 deletions(-) [+]
line wrap: on
line diff
--- a/src/parallel_execution/CMakeLists.txt	Thu Jul 14 20:29:06 2016 +0900
+++ b/src/parallel_execution/CMakeLists.txt	Wed Sep 14 20:43:37 2016 +0900
@@ -1,7 +1,9 @@
 cmake_minimum_required(VERSION 2.8)
 
 # -DUSE_CUDA
-add_definitions("-Wall -g -O0")
+add_definitions("-Wall -g -O")
+
+set(CMAKE_C_COMPILER /Users/one/src/cbclang/Debug+Asserts/bin/clang)
 
 add_executable(twice
                main.c
--- a/src/parallel_execution/main.c	Thu Jul 14 20:29:06 2016 +0900
+++ b/src/parallel_execution/main.c	Wed Sep 14 20:43:37 2016 +0900
@@ -8,8 +8,8 @@
 extern void allocator(struct Context* context);
 
 int cpu_num = 1;
-int length = 1024;
-int split;
+int length = 102400;
+int split = 8;
 int* array_ptr;
 
 void print_queue(struct Element* element) {
--- a/src/parallel_execution/rb_tree.c	Thu Jul 14 20:29:06 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/stack.c	Thu Jul 14 20:29:06 2016 +0900
+++ b/src/parallel_execution/stack.c	Wed Sep 14 20:43:37 2016 +0900
@@ -2,67 +2,67 @@
 #include "stack.h"
 
 stack_ptr stack_init(size_t size, int max) {
-    stack_ptr stack_ptr;
+    stack_ptr p;
     
-    if ((stack_ptr = calloc(1, sizeof(stack))) == NULL)
+    if ((p = calloc(1, sizeof(stack))) == NULL)
         return NULL;
     
-    if ((stack_ptr->data = calloc(max, size)) == NULL) {
-        free(stack_ptr);
+    if ((p->data = calloc(max, size)) == NULL) {
+        free(p);
         return NULL;
     }
 
-    stack_ptr->size = size;
-    stack_ptr->max = max;
-    stack_ptr->num = 0;
+    p->size = size;
+    p->max = max;
+    p->num = 0;
 
-    return stack_ptr;
+    return p;
 }
 
-stack_ptr stack_realloc(stack_ptr stack_ptr, int max) {
-    if (stack_ptr == NULL)
+stack_ptr stack_realloc(stack_ptr p, int max) {
+    if (p == NULL)
         return NULL;
 
-    if ((stack_ptr->data = realloc(stack_ptr->data, stack_ptr->size*max)) == NULL)
+    if ((p->data = realloc(p->data, p->size*max)) == NULL)
         return NULL;
 
-    stack_ptr->max = max;
+    p->max = max;
 
-    return stack_ptr;
+    return p;
 }
 
-void stack_free(stack_ptr stack_ptr) {
-    if (stack_ptr != NULL && stack_ptr->data != NULL) {
-        free(stack_ptr->data);
-        free(stack_ptr);
+void stack_free(stack_ptr p) {
+    if (p != NULL && p->data != NULL) {
+        free(p->data);
+        free(p);
     }
 }
     
-int stack_push(stack_ptr stack_ptr, void* data) {
-    if (stack_ptr->max <= stack_ptr->num)
+int stack_push(stack_ptr p, void* data) {
+    if (p->max <= p->num)
         return -1;
 
-    memcpy((char*)stack_ptr->data+stack_ptr->num*stack_ptr->size,  data, stack_ptr->size);
-    stack_ptr->num++;
+    memcpy((char*)p->data+p->num*p->size,  data, p->size);
+    p->num++;
 
     return 0;
 }
 
-int stack_pop(stack_ptr stack_ptr, void* data) {
-    if (stack_ptr->num == 0)
+int stack_pop(stack_ptr p, void* data) {
+    if (p->num == 0)
         return -1;
 
-    stack_ptr->num--;
+    p->num--;
 
-    memcpy(data, (char*)stack_ptr->data+stack_ptr->num*stack_ptr->size, stack_ptr->size);
+    memcpy(data, (char*)p->data+p->num*p->size, p->size);
     
     return 0;
 }
 
-int isMax(const stack_ptr stack_ptr) {
-    return stack_ptr->max<=stack_ptr->num;
+int isMax(const stack_ptr p) {
+    return p->max<=p->num;
 }
 
-int isEmpty(const stack_ptr stack_ptr) {
-    return stack_ptr->num<=0;
+int isEmpty(const stack_ptr p) {
+    return p->num<=0;
 }