Mercurial > hg > Gears > GearsAgda
changeset 117: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; }