Mercurial > hg > Members > innparusu > Gears
changeset 138:337fdbffa693 default tip
Merge
| author | Tatsuki IHA <e125716@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Sat, 01 Oct 2016 00:23:35 +0900 |
| parents | fe1fbfec7d01 (diff) 77e60b6cdace (current diff) |
| children | |
| files | src/parallel_execution/context.c src/parallel_execution/context.h src/parallel_execution/main.c src/parallel_execution/rb_tree.c |
| diffstat | 6 files changed, 207 insertions(+), 150 deletions(-) [+] |
line wrap: on
line diff
--- a/src/parallel_execution/CMakeLists.txt Tue Sep 27 17:22:00 2016 +0900 +++ b/src/parallel_execution/CMakeLists.txt Sat Oct 01 00:23:35 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/context.c Tue Sep 27 17:22:00 2016 +0900 +++ b/src/parallel_execution/context.c Sat Oct 01 00:23:35 2016 +0900 @@ -13,6 +13,7 @@ extern __code meta(struct Context*); extern __code put_stub(struct Context*); extern __code replaceNode_stub(struct Context*); +extern __code replaceNode1_stub(struct Context*); extern __code insertNode_stub(struct Context*); extern __code rotateLeft_stub(struct Context*); extern __code rotateRight_stub(struct Context*); @@ -22,7 +23,10 @@ extern __code insert1_stub(struct Context*); extern __code insert2_stub(struct Context*); extern __code insert3_stub(struct Context*); +extern __code insert31_stub(struct Context*); extern __code insert4_stub(struct Context*); +extern __code insert4_01_stub(struct Context*); +extern __code insert4_02_stub(struct Context*); extern __code insert4_1_stub(struct Context*); extern __code insert4_2_stub(struct Context*); extern __code insert5_stub(struct Context*); @@ -98,13 +102,17 @@ /* context->code[Code6] = code6; */ context->code[PutTree] = put_stub; context->code[Replace] = replaceNode_stub; + context->code[Replace1] = replaceNode1_stub; context->code[Insert] = insertNode_stub; context->code[RotateL] = rotateLeft_stub; context->code[RotateR] = rotateRight_stub; context->code[InsertCase1] = insert1_stub; context->code[InsertCase2] = insert2_stub; context->code[InsertCase3] = insert3_stub; + context->code[InsertCase31] = insert31_stub; context->code[InsertCase4] = insert4_stub; + context->code[InsertCase4_01]= insert4_01_stub; + context->code[InsertCase4_02]= insert4_02_stub; context->code[InsertCase4_1] = insert4_1_stub; context->code[InsertCase4_2] = insert4_2_stub; context->code[InsertCase5] = insert5_stub; @@ -168,7 +176,8 @@ struct Tree* tree = ALLOC_DATA(context, Tree); tree->root = 0; - ALLOC_DATA(context, Traverse); + struct Traverse* traverse = ALLOC_DATA(context, Traverse); + traverse->nodeStack = NULL; struct Node* node = ALLOC_DATA(context, Node); node->key = 0;
--- a/src/parallel_execution/context.h Tue Sep 27 17:22:00 2016 +0900 +++ b/src/parallel_execution/context.h Sat Oct 01 00:23:35 2016 +0900 @@ -25,6 +25,7 @@ Allocator, PutTree, Replace, + Replace1, Insert, Compare, RotateL, @@ -33,7 +34,10 @@ InsertCase1, InsertCase2, InsertCase3, + InsertCase31, InsertCase4, + InsertCase4_01, + InsertCase4_02, InsertCase4_1, InsertCase4_2, InsertCase5, @@ -175,7 +179,10 @@ } tree; struct Traverse { enum Code next; - struct Node* current; + enum Code rotateNext; + struct Node* current; // reading node of original tree + struct Node* newNode; // writing node of new tree + struct Element* nodeStack; int result; } traverse; struct Node {
--- a/src/parallel_execution/main.c Tue Sep 27 17:22:00 2016 +0900 +++ b/src/parallel_execution/main.c Sat Oct 01 00:23:35 2016 +0900 @@ -9,8 +9,8 @@ extern void metaAllocator(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 Tue Sep 27 17:22:00 2016 +0900 +++ b/src/parallel_execution/rb_tree.c Sat Oct 01 00:23:35 2016 +0900 @@ -6,23 +6,33 @@ extern void allocator(struct Context* context); extern void compare(struct Context* context, struct Traverse* traverse, int key1, int key2); -extern int num; +void printTree1(union Data* data) { + struct Node* node = (struct Node*)data; + if (node == NULL) { + printf("NULL"); + } else { + printf("key = %d (", node->key); + printTree1((union Data*)node->right); + printf("), ("); + printTree1((union Data*)node->left); + printf(")"); + } +} -__code put(struct Context* context, struct Tree* tree, struct Traverse* traverse, struct Node* root, struct Allocate* allocate) { - allocate->size = sizeof(struct Node); - allocator(context); - - stack_push(context->code_stack, &context->next); +void printTree(union Data* data) { + printTree1(data); + printf("\n"); +} - context->next = StackClear; - stack_push(context->code_stack, &context->next); - - tree->root = &context->data[context->dataNum]->node; - +__code put(struct Context* context, struct Tree* tree, struct Node* node, struct Traverse* traverse, struct Node* root, struct Node* newNode) { + printTree((union Data*)tree->root); + traverse->newNode = newNode; + tree->root = newNode; // this should done at stackClear if (root) { traverse->current = root; - compare(context, traverse, traverse->current->key, context->data[Node]->node.key); - + // traverse->result=compare(...) + compare(context, traverse, traverse->current->key, node->key); + // goto replaceNode(traverse->current, newNode, traverse->result); goto meta(context, Replace); } @@ -30,54 +40,80 @@ } __code put_stub(struct Context* context) { + struct Allocate* allocate = &context->data[Allocate]->allocate; + allocate->size = sizeof(struct Node); + allocator(context); + goto put(context, &context->data[Tree]->tree, + &context->data[Node]->node, &context->data[Traverse]->traverse, context->data[Tree]->tree.root, - &context->data[Allocate]->allocate); + &context->data[context->dataNum]->node + ); } -__code replaceNode(struct Context* context, struct Traverse* traverse, struct Node* oldNode, struct Node* newNode, int result) { +__code replaceNode(struct Context* context, struct Traverse* traverse, struct Node* oldNode, struct Node* newNode, struct Element* element) { *newNode = *oldNode; - stack_push(context->node_stack, &newNode); + element->next = traverse->nodeStack; + element->data = (union Data* )newNode; + traverse->nodeStack = element; + // goto replaceNode1(struct Traverse* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, +struct Node* newnewNode, int result) + goto meta(context, Replace1); +} +__code replaceNode_stub(struct Context* context) { + struct Allocate* allocate = &context->data[Allocate]->allocate; + allocate->size = sizeof(struct Element); + allocator(context); + struct Element* element = &context->data[context->dataNum]->element; + goto replaceNode(context, + &context->data[Traverse]->traverse, + context->data[Traverse]->traverse.current, + context->data[Traverse]->traverse.newNode, + element); +} + +__code replaceNode1(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, struct Node* newnewNode, int result) { if (result == EQ) { - newNode->value = context->data[Node]->node.value; - - stack_pop(context->code_stack, &context->next); + newNode->value = node->value; + // go to stack clear goto meta(context, context->next); } else if (result == GT) { traverse->current = oldNode->right; - newNode->right = context->heap; + newNode->right = newnewNode; } else { traverse->current = oldNode->left; - newNode->left = context->heap; + newNode->left = newnewNode; } - - allocator(context); - + traverse->newNode = newnewNode; if (traverse->current) { - compare(context, traverse, traverse->current->key, context->data[Node]->node.key); + compare(context, traverse, traverse->current->key, node->key); goto meta(context, Replace); } goto meta(context, Insert); + } -__code replaceNode_stub(struct Context* context) { - goto replaceNode(context, +__code replaceNode1_stub(struct Context* context) { + struct Allocate* allocate = &context->data[Allocate]->allocate; + allocate->size = sizeof(struct Node); + allocator(context); + struct Node* newnewNode = &context->data[context->dataNum]->node; + goto replaceNode1(context, &context->data[Traverse]->traverse, + &context->data[Node]->node, context->data[Traverse]->traverse.current, - &context->data[context->dataNum]->node, + &context->data[Traverse]->traverse.nodeStack->data->node, + newnewNode, context->data[Traverse]->traverse.result); } __code insertNode(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* newNode) { - node->color = Red; *newNode = *node; - + newNode->color = Red; traverse->current = newNode; - goto meta(context, InsertCase1); } @@ -85,47 +121,36 @@ goto insertNode(context, &context->data[Traverse]->traverse, &context->data[Node]->node, - &context->data[context->dataNum]->node); + context->data[Traverse]->traverse.newNode); } -__code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) { - if (!isEmpty(context->node_stack)) +__code insertCase1(struct Context* context, struct Tree* tree,struct Element* nodeStack) { + if (nodeStack!=NULL) { goto meta(context, InsertCase2); - + } tree->root->color = Black; - - stack_pop(context->code_stack, &context->next); - goto meta(context, context->next); + goto meta(context, StackClear); } __code insert1_stub(struct Context* context) { - goto insertCase1(context, &context->data[Tree]->tree, context->data[Traverse]->traverse.current); + goto insertCase1(context, + &context->data[Tree]->tree, + context->data[Traverse]->traverse.nodeStack); } -__code insertCase2(struct Context* context, struct Node* current) { - struct Node* parent; - stack_pop(context->node_stack, &parent); - +__code insertCase2(struct Context* context, struct Node* parent) { if (parent->color == Black) { - stack_pop(context->code_stack, &context->next); - goto meta(context, context->next); + goto meta(context, StackClear); } - - stack_push(context->node_stack, &parent); goto meta(context, InsertCase3); } __code insert2_stub(struct Context* context) { - goto insertCase2(context, context->data[Traverse]->traverse.current); + goto insertCase2(context, (struct Node*)context->data[Traverse]->traverse.nodeStack->data); } -__code insertCase3(struct Context* context, struct Traverse* traverse, struct Node* current) { - struct Node* parent; +__code insertCase3(struct Context* context, struct Traverse* traverse, struct Node* parent, struct Node* grandparent) { struct Node* uncle; - struct Node* grandparent; - - stack_pop(context->node_stack, &parent); - stack_pop(context->node_stack, &grandparent); if (grandparent->left == parent) uncle = grandparent->right; @@ -133,87 +158,105 @@ 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; traverse->current = grandparent; - goto meta(context, InsertCase1); + goto meta(context, InsertCase31); } - - stack_push(context->node_stack, &grandparent); - stack_push(context->node_stack, &parent); - goto meta(context, InsertCase4); } __code insert3_stub(struct Context* context) { - goto insertCase3(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current); + goto insertCase3(context, &context->data[Traverse]->traverse, + (struct Node*)context->data[Traverse]->traverse.nodeStack->data, + (struct Node*)context->data[Traverse]->traverse.nodeStack->next->data + ); +} +__code insertCase31(struct Context* context, struct Traverse* traverse) { + traverse->nodeStack = traverse->nodeStack->next->next; + goto meta(context, InsertCase1); +} +__code insert31_stub(struct Context* context) { + goto insertCase31(context, &context->data[Traverse]->traverse); } -__code insertCase4(struct Context* context, struct Traverse* traverse, struct Node* current) { - struct Node* parent; - struct Node* grandparent; - - stack_pop(context->node_stack, &parent); - stack_pop(context->node_stack, &grandparent); - - stack_push(context->node_stack, &grandparent); - +__code insertCase4(struct Context* context, struct Traverse* traverse, struct Node* current,struct Node* parent, struct Node* grandparent) { traverse->current = parent; if ((current == parent->right) && (parent == grandparent->left)) { - context->next = InsertCase4_1; - - stack_push(context->code_stack, &context->next); - goto meta(context, RotateL); + traverse->rotateNext = InsertCase4_1; + goto meta(context, InsertCase4_01); } else if ((current == parent->left) && (parent == grandparent->right)) { - context->next = InsertCase4_2; - - stack_push(context->code_stack, &context->next); - goto meta(context, RotateR); + traverse->rotateNext = InsertCase4_2; + goto meta(context, InsertCase4_02); } - stack_push(context->node_stack, &parent); traverse->current = current; goto meta(context, InsertCase5); } __code insert4_stub(struct Context* context) { - goto insertCase4(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current); + goto insertCase4(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current, + &context->data[Traverse]->traverse.nodeStack->data->node, + &context->data[Traverse]->traverse.nodeStack->next->data->node); } +__code insertCase4_01(struct Context* context, struct Traverse* traverse) { + traverse->nodeStack = traverse->nodeStack -> next; + traverse->rotateNext = InsertCase5; + goto meta(context, RotateL); +} + +__code insert4_01_stub(struct Context* context) { + goto insertCase4_01(context, &context->data[Traverse]->traverse); +} __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) { + struct Allocate* allocate = &context->data[Allocate]->allocate; + allocate->size = sizeof(struct Element); + allocator(context); + struct Element* element = &context->data[context->dataNum]->element; + struct Traverse* traverse = &context->data[Traverse]->traverse; + element->data = (union Data*)traverse->current; goto insertCase4_1(context, &context->data[Traverse]->traverse); } +__code insertCase4_02(struct Context* context, struct Traverse* traverse) { + traverse->nodeStack = traverse->nodeStack -> next; + traverse->rotateNext = InsertCase5; + goto meta(context, RotateR); +} + +__code insert4_02_stub(struct Context* context) { + goto insertCase4_02(context, &context->data[Traverse]->traverse); +} __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) { +__code insert4_2_stub(struct Context* context) { + struct Allocate* allocate = &context->data[Allocate]->allocate; + allocate->size = sizeof(struct Element); + allocator(context); + struct Element* element = &context->data[context->dataNum]->element; + struct Traverse* traverse = &context->data[Traverse]->traverse; + element->data = (union Data*)traverse->current; goto insertCase4_2(context, &context->data[Traverse]->traverse); } -__code insertCase5(struct Context* context, struct Traverse* traverse, struct Node* current) { - struct Node* parent; - struct Node* grandparent; - - stack_pop(context->node_stack, &parent); - stack_pop(context->node_stack, &grandparent); - +__code insertCase5(struct Context* context, struct Traverse* traverse, struct Node* current, struct Node* parent, struct Node* grandparent) { parent->color = Black; grandparent->color = Red; traverse->current = grandparent; - + traverse->rotateNext = StackClear; if ((current == parent->left) && (parent == grandparent->left)) goto meta(context, RotateR); else @@ -221,14 +264,16 @@ } __code insert5_stub(struct Context* context) { - goto insertCase5(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current); + struct Traverse* traverse = &context->data[Traverse]->traverse; + struct Node* parent = (struct Node*)traverse->nodeStack->data; + struct Node* grandparent = (struct Node*)traverse->nodeStack->next->data; + traverse->nodeStack = traverse->nodeStack->next->next; + goto insertCase5(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current, parent, grandparent); } -__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) { +// put rotateLeft's continuation as argument +__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) { struct Node* tmp = node->right; - struct Node* parent = 0; - - stack_pop(context->node_stack, &parent); if (parent) { if (node == parent->left) @@ -239,29 +284,26 @@ tree->root = tmp; } - stack_push(context->node_stack, &parent); - node->right = tmp->left; tmp->left = node; traverse->current = tmp; - stack_pop(context->code_stack, &context->next); - goto meta(context, context->next); + goto meta(context, traverse->rotateNext); } __code rotateLeft_stub(struct Context* context) { + struct Traverse* traverse = &context->data[Traverse]->traverse; + struct Node* parent = (traverse->nodeStack)?(struct Node*)traverse->nodeStack->data:NULL; goto rotateLeft(context, context->data[Traverse]->traverse.current, &context->data[Tree]->tree, - &context->data[Traverse]->traverse); + &context->data[Traverse]->traverse, + parent); } -__code rotateRight(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse) { +__code rotateRight(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) { struct Node* tmp = node->left; - struct Node* parent = 0; - stack_pop(context->node_stack, &parent); - if (parent) { if (node == parent->left) parent->left = tmp; @@ -271,30 +313,27 @@ tree->root = tmp; } - stack_push(context->node_stack, &parent); - node->left = tmp->right; tmp->right = node; traverse->current = tmp; - stack_pop(context->code_stack, &context->next); - goto meta(context, context->next); + goto meta(context, traverse->rotateNext); } __code rotateRight_stub(struct Context* context) { + struct Traverse* traverse = &context->data[Traverse]->traverse; + struct Node* parent = (traverse->nodeStack)?(struct Node*)traverse->nodeStack->data:NULL; goto rotateRight(context, context->data[Traverse]->traverse.current, &context->data[Tree]->tree, - &context->data[Traverse]->traverse); + &context->data[Traverse]->traverse, + parent); } __code stackClear(struct Context* context, stack_ptr node_stack, struct Traverse* traverse) { - if (stack_pop(node_stack, &traverse->current) == 0) - goto meta(context, StackClear); + traverse->current = 0; + traverse->nodeStack = NULL; - traverse->current = 0; - - stack_pop(context->code_stack, &context->next); goto meta(context, context->next); } @@ -310,7 +349,7 @@ goto meta(context, Search); } - goto meta(context, traverse->next); + goto meta(context, context->next); } __code get_stub(struct Context* context) { @@ -333,7 +372,7 @@ if (traverse->current) goto meta(context, Search); - goto meta(context, traverse->next); + goto meta(context, context->next); } __code search_stub(struct Context* context) {
--- a/src/parallel_execution/stack.c Tue Sep 27 17:22:00 2016 +0900 +++ b/src/parallel_execution/stack.c Sat Oct 01 00:23:35 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; }