Mercurial > hg > Members > innparusu > Gears
changeset 87:9e139a340bd1 parallel_execution
rename directory
| author | Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Tue, 19 Jan 2016 16:16:26 +0900 |
| parents | e06e1a9e569e |
| children | ac04428e6739 |
| files | src/parallel_execution/CMakeLists.txt src/parallel_execution/allocate.c src/parallel_execution/compare.c src/parallel_execution/context.c src/parallel_execution/context.h src/parallel_execution/main.c src/parallel_execution/origin_cs.c src/parallel_execution/origin_cs.h src/parallel_execution/rb_tree.c src/parallel_execution/stack.c src/parallel_execution/stack.h src/parallel_execution/swap.c src/tmp/CMakeLists.txt src/tmp/allocate.c src/tmp/compare.c src/tmp/context.c src/tmp/context.h src/tmp/main.c src/tmp/origin_cs.c src/tmp/origin_cs.h src/tmp/rb_tree.c src/tmp/stack.c src/tmp/stack.h src/tmp/swap.c |
| diffstat | 24 files changed, 1167 insertions(+), 1140 deletions(-) [+] |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/parallel_execution/CMakeLists.txt Tue Jan 19 16:16:26 2016 +0900 @@ -0,0 +1,16 @@ +cmake_minimum_required(VERSION 2.8) + +add_definitions("-Wall -g -O0") + +set(CMAKE_C_COMPILER $ENV{CbC_Clang}/clang) + +add_executable(bitonic_sort + main.c + context.c + rb_tree.c + stack.c + origin_cs.c + allocate.c + compare.c +) +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/parallel_execution/allocate.c Tue Jan 19 16:16:26 2016 +0900 @@ -0,0 +1,6 @@ +#include "context.h" + +void allocator(struct Context* context) { + context->data[++context->dataNum] = context->heap; + context->heap += context->data[Allocate]->allocate.size; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/parallel_execution/compare.c Tue Jan 19 16:16:26 2016 +0900 @@ -0,0 +1,11 @@ +#include "context.h" + +void compare(struct Context* context, struct Tree* tree, int key1, int key2) { + if (key1 == key2) { + tree->result = EQ; + } else if (key1 < key2) { + tree->result = GT; + } else { + tree->result = LT; + } +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/parallel_execution/context.c Tue Jan 19 16:16:26 2016 +0900 @@ -0,0 +1,151 @@ +#include <stdlib.h> + +#include "context.h" + +extern __code code1_stub(struct Context*); +extern __code code2_stub(struct Context*); +extern __code code3_stub(struct Context*); +extern __code code4(struct Context*); +extern __code code5(struct Context*); +extern __code find(struct Context*); +extern __code not_find(struct Context*); +extern __code code6(struct Context*); +extern __code meta(struct Context*); +extern __code put_stub(struct Context*); +extern __code replaceNode_stub(struct Context*); +extern __code insertNode_stub(struct Context*); +extern __code rotateLeft_stub(struct Context*); +extern __code rotateRight_stub(struct Context*); +extern __code colorFlip_stub(struct Context*); +extern __code fixUp_stub(struct Context*); +extern __code changeReference_stub(struct Context*); +extern __code insert1_stub(struct Context*); +extern __code insert2_stub(struct Context*); +extern __code insert3_stub(struct Context*); +extern __code insert4_stub(struct Context*); +extern __code insert4_1_stub(struct Context*); +extern __code insert4_2_stub(struct Context*); +extern __code insert5_stub(struct Context*); +extern __code stackClear_stub(struct Context*); +extern __code get_stub(struct Context*); +extern __code search_stub(struct Context*); +extern __code delete_stub(struct Context*); +extern __code delete1_stub(struct Context*); +extern __code delete2_stub(struct Context*); +extern __code delete3_stub(struct Context*); +extern __code replaceNodeForDelete1_stub(struct Context*); +extern __code replaceNodeForDelete2_stub(struct Context*); +extern __code findMax1_stub(struct Context*); +extern __code findMax2_stub(struct Context*); +extern __code deleteCase1_stub(struct Context*); +extern __code deleteCase2_stub(struct Context*); +extern __code deleteCase3_stub(struct Context*); +extern __code deleteCase4_stub(struct Context*); +extern __code deleteCase5_stub(struct Context*); +extern __code deleteCase6_stub(struct Context*); +extern __code createWorker_stub(struct Context*); +extern __code taskManager_stub(struct Context*); +extern __code exit_code(struct Context*); + +__code initContext(struct Context* context) { + context->heapLimit = sizeof(union Data)*ALLOCATE_SIZE; + context->code = malloc(sizeof(__code*)*ALLOCATE_SIZE); + context->data = malloc(sizeof(union Data*)*ALLOCATE_SIZE); + context->heapStart = malloc(context->heapLimit); + + context->codeNum = Exit; + + context->code[Code1] = code1_stub; + //context->code[Code2] = code2_stub; + /* context->code[Code3] = code3_stub; */ + /* context->code[Code4] = code4; */ + /* context->code[Code5] = code5; */ + /* context->code[Find] = find; */ + /* context->code[Not_find] = not_find; */ + /* context->code[Code6] = code6; */ + context->code[Put] = put_stub; + context->code[Replace] = replaceNode_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[InsertCase4] = insert4_stub; + context->code[InsertCase4_1] = insert4_1_stub; + context->code[InsertCase4_2] = insert4_2_stub; + context->code[InsertCase5] = insert5_stub; + context->code[StackClear] = stackClear_stub; + /* context->code[Get] = get_stub; */ + /* context->code[Search] = search_stub; */ + /* context->code[Delete] = delete_stub; */ + /* context->code[Delete1] = delete1_stub; */ + /* context->code[Delete2] = delete2_stub; */ + /* context->code[Delete3] = delete3_stub; */ + /* context->code[Replace_d1] = replaceNodeForDelete1_stub; */ + /* context->code[Replace_d2] = replaceNodeForDelete2_stub; */ + /* context->code[FindMax1] = findMax1_stub; */ + /* context->code[FindMax2] = findMax2_stub; */ + /* context->code[DeleteCase1] = deleteCase1_stub; */ + /* context->code[DeleteCase2] = deleteCase2_stub; */ + /* context->code[DeleteCase3] = deleteCase3_stub; */ + /* context->code[DeleteCase4] = deleteCase4_stub; */ + /* context->code[DeleteCase5] = deleteCase5_stub; */ + /* context->code[DeleteCase6] = deleteCase6_stub; */ + context->code[CreateWorker] = createWorker_stub; + context->code[TaskManager] = taskManager_stub; + context->code[Exit] = exit_code; + + context->heap = context->heapStart; + + context->data[Worker] = context->heap; + context->heap += sizeof(struct Worker); + + context->data[Allocate] = context->heap; + context->heap += sizeof(struct Allocate); + + context->data[Tree] = context->heap; + context->heap += sizeof(struct Tree); + + context->data[Node] = context->heap; + context->heap += sizeof(struct Node); + + context->data[LoopCounter] = context->heap; + context->heap += sizeof(struct LoopCounter); + + context->data[WaitQueue] = context->heap; + context->heap += sizeof(struct Queue); + + context->data[ActiveQueue] = context->heap; + context->heap += sizeof(struct Queue); + + context->dataNum = ActiveQueue; + + struct Worker* worker = &context->data[Worker]->worker; + worker->num = 0; + worker->contexts = 0; + + struct Allocate* allocate = &contexts->data[Allocate]->allocate; + allocate->size = 0; + + struct Tree* tree = &context->data[Tree]->tree; + tree->root = 0; + tree->current = 0; + + struct Node* node = &context->data[Node]->node; + node->key = 0; + node->value = 0; + node->left = 0; + node->right = 0; + + struct LoopCounter* counter = &context->data[LoopCounter]->loopCounter; + counter->i = 0; + + struct Queue* waitQueue = &context->data[WaitQueue]->queue; + waitQueue->first = 0; + waitQueue->last = 0; + waitQueue->count = 0; + + context->node_stack = stack_init(sizeof(struct Node*), 100); + context->code_stack = stack_init(sizeof(enum Code), 100); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/parallel_execution/context.h Tue Jan 19 16:16:26 2016 +0900 @@ -0,0 +1,128 @@ +/* Context definition for llrb example */ +#include <pthread.h> +#include "stack.h" + +#define ALLOCATE_SIZE 1000 + +enum Code { + Code1, + Code2, + Code3, + Code4, + Code5, + Find, + Not_find, + Code6, + Allocator, + Put, + Replace, + Insert, + Compare, + RotateL, + RotateR, + SetTree, + InsertCase1, + InsertCase2, + InsertCase3, + InsertCase4, + InsertCase4_1, + InsertCase4_2, + InsertCase5, + StackClear, + Get, + Search, + Delete, + Delete1, + Delete2, + Delete3, + Replace_d1, + Replace_d2, + FindMax1, + FindMax2, + DeleteCase1, + DeleteCase2, + DeleteCase3, + DeleteCase4, + DeleteCase5, + DeleteCase6, + CreateWorker, + TaskManager, + Exit, +}; + +enum Relational { + EQ, + GT, + LT, +}; + +enum UniqueData { + Worker, + Allocate, + Tree, + Node, + LoopCounter, + WaitQueue, + ActiveQueue, +}; + +struct Context { + enum Code next; + int codeNum; + __code (**code) (struct Context*); + void* heapStart; + void* heap; + long heapLimit; + pthread_t thread; + stack_ptr code_stack; + stack_ptr node_stack; + int dataNum; + union Data **data; + struct Queue* waitQueue; + struct Queue* activeQueue; + struct Tree* Tree; +}; + +union Data { + struct LoopCounter { + int i; + } loopCounter; + struct Worker { + //enum DataType type; + int num; + struct Context* contexts; + } worker; + struct Array { + //enum DataType type; + int size; + int* array; + } array; + struct Spots { + //enum DataType type; + int x; + int y; + } spot; + struct Tree { + enum Code next; + struct Node* root; + struct Node* current; + int result; + } tree; + struct Node { + // need to tree + enum Code next; + int key; // comparable data segment + int value; + struct Node* left; + struct Node* right; + // need to balancing + enum Color { + Red, + Black, + } color; + } node; + struct Allocate { + enum Code next; + long size; + } allocate; +};
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/parallel_execution/main.c Tue Jan 19 16:16:26 2016 +0900 @@ -0,0 +1,81 @@ +#include <stdio.h> +#include <unistd.h> + +#include "context.h" +#include "origin_cs.h" + +extern __code initContext(struct Context* context); + +int a; + +__code code1(struct Context* context) { + if(__sync_bool_compare_and_swap(&a, 10, 0)) { + puts("success"); + a = 10; + } else { + puts("failure"); + goto meta(context, Code1); + } +} + +__code code1_stub(struct Context* context) { + goto code1(context); +} + +__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; + pthread_create(&worker_context->thread, NULL, (void*)&start_code, worker_context); + loopCounter->i++; + + goto meta(context, CreateWorker); + } + + loopCounter->i = 0; + goto meta(context, TaskManager); +} + +__code createWorker_stub(struct Context* context) { + goto createWorker(context, &context->data[LoopCounter]->loopCounter, &context->data[Worker]->worker); +} + +__code taskManager(struct Context* context, struct LoopCounter* loopCounter, struct Worker* worker) { + int i = loopCounter->i; + + if (i < worker->num) { + pthread_join(worker->contexts[i].thread, NULL); + loopCounter->i++; + + goto meta(context, TaskManager); + } + + loopCounter->i = 0; + goto meta(context, Exit); +} + +__code taskManager_stub(struct Context* context) { + goto taskManager(context, &context->data[LoopCounter]->loopCounter, &context->data[Worker]->worker); +} + +int main(int argc, char** argv) { + a = 10; + int cpu_num = (int)atoi(argv[1]); + + struct Context* main_context = (struct Context*)malloc(sizeof(struct Context)); + initContext(main_context); + main_context->next = CreateWorker; + + struct Context* worker_contexts = (struct Context*)malloc(sizeof(struct Context)*cpu_num); + + struct Worker* worker = &main_context->data[Worker]->worker; + worker->num = cpu_num; + worker->contexts = worker_contexts; + + for (int i = 0;i<cpu_num;i++) + initContext(&worker_contexts[i]); + + goto start_code(main_context); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/parallel_execution/origin_cs.c Tue Jan 19 16:16:26 2016 +0900 @@ -0,0 +1,17 @@ +#include <stdlib.h> +#include "context.h" + +__code meta(struct Context* context, enum Code next) { + goto (context->code[next])(context); +} + +__code start_code(struct Context* context) { + goto meta(context, context->next); +} + +__code exit_code(struct Context* context) { + free(context->code); + free(context->data); + free(context->heapStart); + goto exit(0); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/parallel_execution/origin_cs.h Tue Jan 19 16:16:26 2016 +0900 @@ -0,0 +1,3 @@ +extern __code start_code(struct Context* context); +extern __code exit_code(struct Context* context); +extern __code meta(struct Context* context, enum Code next);
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/parallel_execution/rb_tree.c Tue Jan 19 16:16:26 2016 +0900 @@ -0,0 +1,668 @@ +#include <stdio.h> + +#include "context.h" +#include "origin_cs.h" + +extern void allocator(struct Context* context); +extern void compare(struct Context* context, struct Tree* tree, int key1, int key2); + +extern int num; + +__code put(struct Context* context, struct Tree* tree, struct Node* root, struct Allocate* allocate) { + allocate->size = sizeof(struct Node); + allocator(context); + + stack_push(context->code_stack, &context->next); + + context->next = StackClear; + stack_push(context->code_stack, &context->next); + + tree->root = &context->data[context->dataNum]->node; + + if (root) { + tree->current = root; + compare(context, tree, tree->current->key, context->data[Node]->node.key); + + goto meta(context, Replace); + } + + goto meta(context, Insert); +} + +__code put_stub(struct Context* context) { + goto put(context, &context->data[Tree]->tree, 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) { + *newNode = *oldNode; + stack_push(context->node_stack, &newNode); + + if (result == EQ) { + newNode->value = context->data[Node]->node.value; + + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); + } else if (result == GT) { + tree->current = oldNode->right; + newNode->right = context->heap; + } else { + tree->current = oldNode->left; + newNode->left = context->heap; + } + + allocator(context); + + if (tree->current) { + compare(context, tree, tree->current->key, context->data[Node]->node.key); + goto meta(context, Replace); + } + + goto meta(context, Insert); +} + +__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); +} + +__code insertNode(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) { + node->color = Red; + *newNode = *node; + + tree->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); +} + +__code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) { + if (!isEmpty(context->node_stack)) + goto meta(context, InsertCase2); + + tree->root->color = Black; + + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); +} + +__code insert1_stub(struct Context* context) { + goto insertCase1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); +} + +__code insertCase2(struct Context* context, struct Node* current) { + struct Node* parent; + stack_pop(context->node_stack, &parent); + + if (parent->color == Black) { + stack_pop(context->code_stack, &context->next); + goto meta(context, context->next); + } + + stack_push(context->node_stack, &parent); + goto meta(context, InsertCase3); +} + +__code insert2_stub(struct Context* context) { + goto insertCase2(context, context->data[Tree]->tree.current); +} + +__code insertCase3(struct Context* context, struct Tree* tree, struct Node* current) { + struct Node* parent; + 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; + else + uncle = grandparent->left; + + if (uncle && (uncle->color == Red)) { + parent->color = Black; + uncle->color = Black; + grandparent->color = Red; + tree->current = grandparent; + goto meta(context, InsertCase1); + } + + 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[Tree]->tree, context->data[Tree]->tree.current); +} + +__code insertCase4(struct Context* context, struct Tree* tree, 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); + + tree->current = parent; + + if ((current == parent->right) && (parent == grandparent->left)) { + context->next = InsertCase4_1; + + stack_push(context->code_stack, &context->next); + goto meta(context, RotateL); + } else if ((current == parent->left) && (parent == grandparent->right)) { + context->next = InsertCase4_2; + + stack_push(context->code_stack, &context->next); + goto meta(context, RotateR); + } + + stack_push(context->node_stack, &parent); + tree->current = current; + goto meta(context, InsertCase5); +} + +__code insert4_stub(struct Context* context) { + goto insertCase4(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); +} + +__code insertCase4_1(struct Context* context, struct Tree* tree) { + stack_push(context->node_stack, &tree->current); + tree->current = tree->current->left; + goto meta(context, InsertCase5); +} + +__code insert4_1_stub(struct Context* context) { + goto insertCase4_1(context, &context->data[Tree]->tree); +} + +__code insertCase4_2(struct Context* context, struct Tree* tree) { + stack_push(context->node_stack, &tree->current); + tree->current = tree->current->right; + goto meta(context, InsertCase5); +} + +__code insert4_2_stub(struct Context* context) { + goto insertCase4_2(context, &context->data[Tree]->tree); +} + +__code insertCase5(struct Context* context, struct Tree* tree, struct Node* current) { + struct Node* parent; + struct Node* grandparent; + + stack_pop(context->node_stack, &parent); + stack_pop(context->node_stack, &grandparent); + + parent->color = Black; + grandparent->color = Red; + + tree->current = grandparent; + + if ((current == parent->left) && (parent == grandparent->left)) + goto meta(context, RotateR); + else + goto meta(context, RotateL); +} + +__code insert5_stub(struct Context* context) { + goto insertCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); +} + +__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree) { + struct Node* tmp = node->right; + struct Node* parent = 0; + + stack_pop(context->node_stack, &parent); + + if (parent) { + if (node == parent->left) + parent->left = tmp; + else + parent->right = tmp; + } else { + tree->root = tmp; + } + + stack_push(context->node_stack, &parent); + + node->right = tmp->left; + tmp->left = node; + tree->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); +} + +__code rotateRight(struct Context* context, struct Node* node, struct Tree* tree) { + struct Node* tmp = node->left; + struct Node* parent = 0; + + stack_pop(context->node_stack, &parent); + + if (parent) { + if (node == parent->left) + parent->left = tmp; + else + parent->right = tmp; + } else { + tree->root = tmp; + } + + stack_push(context->node_stack, &parent); + + node->left = tmp->right; + tmp->right = node; + tree->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); +} + +__code stackClear(struct Context* context, stack_ptr node_stack, struct Tree* tree) { + if (stack_pop(node_stack, &tree->current) == 0) + goto meta(context, StackClear); + + tree->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); +} + + +/* /\* __code get(struct Context* context, struct Tree* tree) { *\/ */ +/* /\* if (tree->root) { *\/ */ +/* /\* tree->current = tree->root; *\/ */ + +/* /\* goto meta(context, Search); *\/ */ +/* /\* } *\/ */ + +/* /\* stack_pop(context->code_stack, &context->next); *\/ */ +/* /\* goto meta(context, context->next); *\/ */ +/* /\* } *\/ */ + +/* /\* __code get_stub(struct Context* context) { *\/ */ +/* /\* 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); *\/ */ + +/* /\* if (tree->result == EQ) { *\/ */ +/* /\* *node = *tree->current; *\/ */ + +/* /\* goto meta(context, context->next); *\/ */ +/* /\* } else if (tree->result == GT) { *\/ */ +/* /\* tree->current = tree->current->right; *\/ */ +/* /\* } else { *\/ */ +/* /\* tree->current = tree->current->left; *\/ */ +/* /\* } *\/ */ + +/* /\* if (tree->current) *\/ */ +/* /\* goto meta(context, Search); *\/ */ + +/* /\* 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 delete(struct Context* context, struct Tree* tree) { *\/ */ +/* /\* if (tree->root) { *\/ */ +/* /\* stack_push(context->code_stack, &context->next); *\/ */ +/* /\* context->next = Delete1; *\/ */ +/* /\* goto meta(context, Get); *\/ */ +/* /\* } *\/ */ + +/* /\* goto meta(context, context->next); *\/ */ +/* /\* } *\/ */ + +/* /\* __code delete_stub(struct Context* context) { *\/ */ +/* /\* goto delete(context, &context->data[Tree]->tree); *\/ */ +/* /\* } *\/ */ + +/* /\* __code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) { *\/ */ +/* /\* allocate->size = sizeof(struct Node); *\/ */ +/* /\* allocator(context); *\/ */ + +/* /\* struct Node* root = tree->root; *\/ */ + +/* /\* tree->root = &context->data[context->dataNum]->node; *\/ */ +/* /\* tree->current = root; *\/ */ + +/* /\* compare(context, tree, tree->current->key, context->data[Node]->node.key); *\/ */ + +/* /\* goto meta(context, Replace_d1); *\/ */ +/* /\* } *\/ */ + +/* /\* __code delete1_stub(struct Context* context) { *\/ */ +/* /\* goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate); *\/ */ +/* /\* } *\/ */ + +/* /\* __code delete2(struct Context* context, struct Node* current) { *\/ */ +/* /\* if (current->color == Black) { *\/ */ +/* /\* struct Node* child = current->right == NULL ? current->left : current->right; *\/ */ +/* /\* current->color = child == NULL ? Black : child->color; *\/ */ + +/* /\* goto meta(context, DeleteCase1); *\/ */ +/* /\* } *\/ */ + +/* /\* goto meta(context, Delete3); *\/ */ +/* /\* } *\/ */ + +/* /\* __code delete2_stub(struct Context* context) { *\/ */ +/* /\* goto delete2(context, context->data[Tree]->tree.current); *\/ */ +/* /\* } *\/ */ + +/* /\* __code delete3(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ +/* /\* struct Node* tmp = current->right == NULL ? current->left : current->right; *\/ */ + +/* /\* if (current->parent) { *\/ */ +/* /\* if (current == current->parent->left) *\/ */ +/* /\* current->parent->left = tmp; *\/ */ +/* /\* else *\/ */ +/* /\* current->parent->right = tmp; *\/ */ +/* /\* } else { *\/ */ +/* /\* tree->root = tmp; *\/ */ +/* /\* } *\/ */ + +/* /\* if (tmp) *\/ */ +/* /\* tmp->parent = current->parent; *\/ */ + +/* /\* if (current->parent == NULL && tmp) *\/ */ +/* /\* tmp->color = Black; *\/ */ + +/* /\* current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL); *\/ */ + +/* /\* stack_pop(context->code_stack, &context->next); *\/ */ +/* /\* goto meta(context, context->next); *\/ */ +/* /\* } *\/ */ + +/* /\* __code delete3_stub(struct Context* context) { *\/ */ +/* /\* goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ +/* /\* } *\/ */ + +/* /\* __code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) { *\/ */ +/* /\* *newNode = *oldNode; *\/ */ + +/* /\* if (result == EQ) *\/ */ +/* /\* goto meta(context, Replace_d2); *\/ */ +/* /\* else if (result == GT) *\/ */ +/* /\* tree->current = newNode->right; *\/ */ +/* /\* else *\/ */ +/* /\* tree->current = newNode->left; *\/ */ + +/* /\* tree->current->parent = newNode; *\/ */ + +/* /\* if (tree->current->left == NULL && tree->current->right == NULL) *\/ */ +/* /\* goto meta(context, Delete2); *\/ */ + +/* /\* if (result == GT) *\/ */ +/* /\* newNode->right = context->heap; *\/ */ +/* /\* else if (result == LT) *\/ */ +/* /\* newNode->left = context->heap; *\/ */ + +/* /\* allocator(context); *\/ */ + +/* /\* compare(context, tree, tree->current->key, context->data[Node]->node.key); *\/ */ + +/* /\* goto meta(context, Replace_d1); *\/ */ +/* /\* } *\/ */ + +/* /\* __code replaceNodeForDelete1_stub(struct Context* context) { *\/ */ +/* /\* goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result); *\/ */ +/* /\* } *\/ */ + +/* /\* __code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) { *\/ */ +/* /\* if (tree->current->left && tree->current->right) { *\/ */ +/* /\* newNode->left->parent = newNode; *\/ */ +/* /\* tree->current = newNode->left; *\/ */ +/* /\* newNode->left = context->heap; *\/ */ +/* /\* tree->deleted = newNode; *\/ */ + +/* /\* allocator(context); *\/ */ +/* /\* tree->current->parent = newNode; *\/ */ + +/* /\* goto meta(context, FindMax1); *\/ */ +/* /\* } *\/ */ + +/* /\* goto meta(context, Delete2); *\/ */ +/* /\* } *\/ */ + +/* /\* __code replaceNodeForDelete2_stub(struct Context* context) { *\/ */ +/* /\* goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node); *\/ */ +/* /\* } *\/ */ + +/* /\* __code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { *\/ */ +/* /\* *newNode = *oldNode; *\/ */ + +/* /\* if (newNode->right) *\/ */ +/* /\* goto meta(context, FindMax2); *\/ */ + +/* /\* tree->deleted->key = newNode->key; *\/ */ +/* /\* tree->deleted->value = newNode->value; *\/ */ + +/* /\* tree->current = newNode; *\/ */ + +/* /\* goto meta(context, Delete2); *\/ */ +/* /\* } *\/ */ + +/* /\* __code findMax1_stub(struct Context* context) { *\/ */ +/* /\* goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); *\/ */ +/* /\* } *\/ */ + + +/* /\* __code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { *\/ */ +/* /\* *newNode = *oldNode; *\/ */ + +/* /\* if (newNode->right->right) { *\/ */ +/* /\* tree->current = newNode->right; *\/ */ +/* /\* newNode->right = context->heap; *\/ */ + +/* /\* allocator(context); *\/ */ +/* /\* tree->current->parent = newNode; *\/ */ + +/* /\* goto meta(context, FindMax2); *\/ */ +/* /\* } *\/ */ + +/* /\* tree->deleted->key = newNode->right->key; *\/ */ +/* /\* tree->deleted->value = newNode->right->value; *\/ */ + +/* /\* tree->current = newNode; *\/ */ + +/* /\* goto meta(context, Delete2); *\/ */ +/* /\* } *\/ */ + +/* /\* __code findMax2_stub(struct Context* context) { *\/ */ +/* /\* goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase1(struct Context* context, struct Node* current) { *\/ */ +/* /\* if (current->parent) *\/ */ +/* /\* goto meta(context, DeleteCase2); *\/ */ + +/* /\* goto meta(context, Delete3); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase1_stub(struct Context* context) { *\/ */ +/* /\* goto deleteCase1(context, context->data[Tree]->tree.current); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ +/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ + +/* /\* if ((sibling == NULL ? Black : sibling->color) == Red) { *\/ */ +/* /\* current->parent->color = Red; *\/ */ +/* /\* sibling->color = Black; *\/ */ + +/* /\* current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap); *\/ */ +/* /\* allocator(context); *\/ */ +/* /\* context->data[context->dataNum]->node = *sibling; *\/ */ + +/* /\* tree->current = current->parent; *\/ */ + +/* /\* context->next = DeleteCase3; *\/ */ +/* /\* stack_push(context->code_stack, &context->next); *\/ */ + +/* /\* if (current == current->parent->left) *\/ */ +/* /\* goto meta(context, RotateL); *\/ */ +/* /\* else *\/ */ +/* /\* goto meta(context, RotateR); *\/ */ +/* /\* } *\/ */ + +/* /\* goto meta(context, DeleteCase3); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase2_stub(struct Context* context) { *\/ */ +/* /\* goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ +/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ + +/* /\* if (current->parent->color == Black && *\/ */ +/* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */ +/* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */ +/* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */ +/* /\* sibling->color = Red; *\/ */ + +/* /\* tree->current = current->parent; *\/ */ +/* /\* goto meta(context, DeleteCase1); *\/ */ +/* /\* } *\/ */ + +/* /\* goto meta(context, DeleteCase4); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase3_stub(struct Context* context) { *\/ */ +/* /\* goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase4(struct Context* context, struct Node* current) { *\/ */ +/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ + +/* /\* if (current->parent->color == Red && *\/ */ +/* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */ +/* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */ +/* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */ +/* /\* sibling->color = Red; *\/ */ +/* /\* current->parent->color = Black; *\/ */ + +/* /\* goto meta(context, Delete3); *\/ */ +/* /\* } *\/ */ + +/* /\* goto meta(context, DeleteCase5); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase4_stub(struct Context* context) { *\/ */ +/* /\* goto deleteCase4(context, context->data[Tree]->tree.current); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ +/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ +/* /\* sibling->parent = current->parent; *\/ */ + +/* /\* if (current == current->parent->left && *\/ */ +/* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */ +/* /\* (sibling->left == NULL ? Black : sibling->left->color) == Red && *\/ */ +/* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */ +/* /\* sibling->color = Red; *\/ */ +/* /\* sibling->left->color = Black; *\/ */ + +/* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */ +/* /\* allocator(context); *\/ */ +/* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */ +/* /\* *tmp = *sibling; *\/ */ +/* /\* tmp->parent = current; *\/ */ + +/* /\* tmp->left = context->heap; *\/ */ +/* /\* allocator(context); *\/ */ +/* /\* context->data[context->dataNum]->node = *sibling->left; *\/ */ +/* /\* context->data[context->dataNum]->node.parent = tmp; *\/ */ + +/* /\* tree->current = tmp; *\/ */ + +/* /\* context->next = DeleteCase6; *\/ */ +/* /\* stack_push(context->code_stack, &context->next); *\/ */ + +/* /\* goto meta(context, RotateR); *\/ */ +/* /\* } else if (current == current->parent->right && *\/ */ +/* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */ +/* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */ +/* /\* (sibling->right == NULL ? Black : sibling->right->color) == Red) { *\/ */ +/* /\* sibling->color = Red; *\/ */ +/* /\* sibling->right->color = Black; *\/ */ + +/* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */ +/* /\* allocator(context); *\/ */ +/* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */ +/* /\* *tmp = *sibling; *\/ */ +/* /\* tmp->parent = current; *\/ */ + +/* /\* tmp->right = context->heap; *\/ */ +/* /\* allocator(context); *\/ */ +/* /\* context->data[context->dataNum]->node = *sibling->right; *\/ */ +/* /\* context->data[context->dataNum]->node.parent = tmp; *\/ */ + +/* /\* tree->current = tmp; *\/ */ + +/* /\* context->next = DeleteCase6; *\/ */ +/* /\* stack_push(context->code_stack, &context->next); *\/ */ +/* /\* goto meta(context, RotateL); *\/ */ +/* /\* } *\/ */ + +/* /\* goto meta(context, DeleteCase6); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase5_stub(struct Context* context) { *\/ */ +/* /\* goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ +/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ + +/* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */ +/* /\* allocator(context); *\/ */ +/* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */ +/* /\* *tmp = *sibling; *\/ */ +/* /\* tmp->parent = current; *\/ */ + +/* /\* tmp->color = current->parent->color; *\/ */ +/* /\* current->parent->color = Black; *\/ */ + +/* /\* context->next = Delete3; *\/ */ +/* /\* stack_push(context->code_stack, &context->next); *\/ */ + +/* /\* if (current == current->parent->left) { *\/ */ +/* /\* tmp->right->color = Black; *\/ */ +/* /\* tree->current = current->parent; *\/ */ + +/* /\* goto meta(context, RotateL); *\/ */ +/* /\* } else { *\/ */ +/* /\* tmp->left->color = Black; *\/ */ +/* /\* tree->current = current->parent; *\/ */ + +/* /\* goto meta(context, RotateR); *\/ */ +/* /\* } *\/ */ +/* /\* } *\/ */ + +/* /\* __code deleteCase6_stub(struct Context* context) { *\/ */ +/* /\* goto deleteCase6(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ +/* /\* } *\/ */
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/parallel_execution/stack.c Tue Jan 19 16:16:26 2016 +0900 @@ -0,0 +1,68 @@ +#include <string.h> +#include "stack.h" + +stack_ptr stack_init(size_t size, int max) { + stack_ptr stack_ptr; + + if ((stack_ptr = calloc(1, sizeof(stack))) == NULL) + return NULL; + + if ((stack_ptr->data = calloc(max, size)) == NULL) { + free(stack_ptr); + return NULL; + } + + stack_ptr->size = size; + stack_ptr->max = max; + stack_ptr->num = 0; + + return stack_ptr; +} + +stack_ptr stack_realloc(stack_ptr stack_ptr, int max) { + if (stack_ptr == NULL) + return NULL; + + if ((stack_ptr->data = realloc(stack_ptr->data, stack_ptr->size*max)) == NULL) + return NULL; + + stack_ptr->max = max; + + return stack_ptr; +} + +void stack_free(stack_ptr stack_ptr) { + if (stack_ptr != NULL && stack_ptr->data != NULL) { + free(stack_ptr->data); + free(stack_ptr); + } +} + +int stack_push(stack_ptr stack_ptr, void* data) { + if (stack_ptr->max <= stack_ptr->num) + return -1; + + memcpy((char*)stack_ptr->data+stack_ptr->num*stack_ptr->size, data, stack_ptr->size); + stack_ptr->num++; + + return 0; +} + +int stack_pop(stack_ptr stack_ptr, void* data) { + if (stack_ptr->num == 0) + return -1; + + stack_ptr->num--; + + memcpy(data, (char*)stack_ptr->data+stack_ptr->num*stack_ptr->size, stack_ptr->size); + + return 0; +} + +int isMax(const stack_ptr stack_ptr) { + return stack_ptr->max<=stack_ptr->num; +} + +int isEmpty(const stack_ptr stack_ptr) { + return stack_ptr->num<=0; +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/parallel_execution/stack.h Tue Jan 19 16:16:26 2016 +0900 @@ -0,0 +1,16 @@ +#include <stdlib.h> + +typedef struct { + size_t size; + int max; + int num; + void* data; +} stack, *stack_ptr; + +extern stack_ptr stack_init(); +extern stack_ptr stack_realloc(); +extern void stack_free(); +extern int stack_push(); +extern int stack_pop(); +extern int isMax(); +extern int isEmpty();
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/parallel_execution/swap.c Tue Jan 19 16:16:26 2016 +0900 @@ -0,0 +1,2 @@ +__code swap(struct Context* context, struct ) { +
--- a/src/tmp/CMakeLists.txt Mon Jan 18 17:50:52 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,16 +0,0 @@ -cmake_minimum_required(VERSION 2.8) - -add_definitions("-Wall -g -O0") - -set(CMAKE_C_COMPILER $ENV{CbC_Clang}/clang) - -add_executable(bitonic_sort - main.c - context.c - rb_tree.c - stack.c - origin_cs.c - allocate.c - compare.c -) -
--- a/src/tmp/allocate.c Mon Jan 18 17:50:52 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,6 +0,0 @@ -#include "context.h" - -void allocator(struct Context* context) { - context->data[++context->dataNum] = context->heap; - context->heap += context->data[Allocate]->allocate.size; -}
--- a/src/tmp/compare.c Mon Jan 18 17:50:52 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,11 +0,0 @@ -#include "context.h" - -void compare(struct Context* context, struct Tree* tree, int key1, int key2) { - if (key1 == key2) { - tree->result = EQ; - } else if (key1 < key2) { - tree->result = GT; - } else { - tree->result = LT; - } -}
--- a/src/tmp/context.c Mon Jan 18 17:50:52 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,128 +0,0 @@ -#include <stdlib.h> - -#include "context.h" - -extern __code code1_stub(struct Context*); -extern __code code2_stub(struct Context*); -extern __code code3_stub(struct Context*); -extern __code code4(struct Context*); -extern __code code5(struct Context*); -extern __code find(struct Context*); -extern __code not_find(struct Context*); -extern __code code6(struct Context*); -extern __code meta(struct Context*); -extern __code put_stub(struct Context*); -extern __code replaceNode_stub(struct Context*); -extern __code insertNode_stub(struct Context*); -extern __code rotateLeft_stub(struct Context*); -extern __code rotateRight_stub(struct Context*); -extern __code colorFlip_stub(struct Context*); -extern __code fixUp_stub(struct Context*); -extern __code changeReference_stub(struct Context*); -extern __code insert1_stub(struct Context*); -extern __code insert2_stub(struct Context*); -extern __code insert3_stub(struct Context*); -extern __code insert4_stub(struct Context*); -extern __code insert4_1_stub(struct Context*); -extern __code insert4_2_stub(struct Context*); -extern __code insert5_stub(struct Context*); -extern __code stackClear_stub(struct Context*); -extern __code get_stub(struct Context*); -extern __code search_stub(struct Context*); -extern __code delete_stub(struct Context*); -extern __code delete1_stub(struct Context*); -extern __code delete2_stub(struct Context*); -extern __code delete3_stub(struct Context*); -extern __code replaceNodeForDelete1_stub(struct Context*); -extern __code replaceNodeForDelete2_stub(struct Context*); -extern __code findMax1_stub(struct Context*); -extern __code findMax2_stub(struct Context*); -extern __code deleteCase1_stub(struct Context*); -extern __code deleteCase2_stub(struct Context*); -extern __code deleteCase3_stub(struct Context*); -extern __code deleteCase4_stub(struct Context*); -extern __code deleteCase5_stub(struct Context*); -extern __code deleteCase6_stub(struct Context*); -extern __code createWorker_stub(struct Context*); -extern __code taskManager_stub(struct Context*); -extern __code exit_code(struct Context*); - -__code initContext(struct Context* context) { - context->heapLimit = sizeof(union Data)*ALLOCATE_SIZE; - context->code = malloc(sizeof(__code*)*ALLOCATE_SIZE); - context->data = malloc(sizeof(union Data*)*ALLOCATE_SIZE); - context->heapStart = malloc(context->heapLimit); - - context->codeNum = Exit; - - context->code[Code1] = code1_stub; - //context->code[Code2] = code2_stub; - /* context->code[Code3] = code3_stub; */ - /* context->code[Code4] = code4; */ - /* context->code[Code5] = code5; */ - /* context->code[Find] = find; */ - /* context->code[Not_find] = not_find; */ - /* context->code[Code6] = code6; */ - context->code[Put] = put_stub; - context->code[Replace] = replaceNode_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[InsertCase4] = insert4_stub; - context->code[InsertCase4_1] = insert4_1_stub; - context->code[InsertCase4_2] = insert4_2_stub; - context->code[InsertCase5] = insert5_stub; - context->code[StackClear] = stackClear_stub; - /* context->code[Get] = get_stub; */ - /* context->code[Search] = search_stub; */ - /* context->code[Delete] = delete_stub; */ - /* context->code[Delete1] = delete1_stub; */ - /* context->code[Delete2] = delete2_stub; */ - /* context->code[Delete3] = delete3_stub; */ - /* context->code[Replace_d1] = replaceNodeForDelete1_stub; */ - /* context->code[Replace_d2] = replaceNodeForDelete2_stub; */ - /* context->code[FindMax1] = findMax1_stub; */ - /* context->code[FindMax2] = findMax2_stub; */ - /* context->code[DeleteCase1] = deleteCase1_stub; */ - /* context->code[DeleteCase2] = deleteCase2_stub; */ - /* context->code[DeleteCase3] = deleteCase3_stub; */ - /* context->code[DeleteCase4] = deleteCase4_stub; */ - /* context->code[DeleteCase5] = deleteCase5_stub; */ - /* context->code[DeleteCase6] = deleteCase6_stub; */ - context->code[CreateWorker] = createWorker_stub; - context->code[TaskManager] = taskManager_stub; - context->code[Exit] = exit_code; - - context->heap = context->heapStart; - - context->data[Worker] = context->heap; - context->heap += sizeof(struct Worker); - - context->data[Allocate] = context->heap; - context->heap += sizeof(struct Allocate); - - context->data[Tree] = context->heap; - context->heap += sizeof(struct Tree); - - context->data[Node] = context->heap; - context->heap += sizeof(struct Node); - - context->data[LoopCounter] = context->heap; - context->heap += sizeof(struct LoopCounter); - - context->dataNum = Node; - - struct Tree* tree = &context->data[Tree]->tree; - tree->root = 0; - tree->current = 0; - tree->deleted = 0; - - struct LoopCounter* counter = &context->data[LoopCounter]->loopCounter; - counter->i = 0; - - context->node_stack = stack_init(sizeof(struct Node*), 100); - context->code_stack = stack_init(sizeof(enum Code), 100); -}
--- a/src/tmp/context.h Mon Jan 18 17:50:52 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,124 +0,0 @@ -/* Context definition for llrb example */ -#include <pthread.h> -#include "stack.h" - -#define ALLOCATE_SIZE 1000 - -enum Code { - Code1, - Code2, - Code3, - Code4, - Code5, - Find, - Not_find, - Code6, - Allocator, - Put, - Replace, - Insert, - Compare, - RotateL, - RotateR, - SetTree, - InsertCase1, - InsertCase2, - InsertCase3, - InsertCase4, - InsertCase4_1, - InsertCase4_2, - InsertCase5, - StackClear, - Get, - Search, - Delete, - Delete1, - Delete2, - Delete3, - Replace_d1, - Replace_d2, - FindMax1, - FindMax2, - DeleteCase1, - DeleteCase2, - DeleteCase3, - DeleteCase4, - DeleteCase5, - DeleteCase6, - CreateWorker, - TaskManager, - Exit, -}; - -enum Relational { - EQ, - GT, - LT, -}; - -enum UniqueData { - Worker, - Allocate, - Tree, - Node, - LoopCounter, -}; - -struct Context { - enum Code next; - int codeNum; - __code (**code) (struct Context*); - void* heapStart; - void* heap; - long heapLimit; - pthread_t thread; - int dataNum; - stack_ptr code_stack; - stack_ptr node_stack; - union Data **data; -}; - -union Data { - struct LoopCounter { - int i; - } loopCounter; - struct Worker { - //enum DataType type; - int num; - struct Context* contexts; - } worker; - struct Array { - //enum DataType type; - int size; - int* array; - } array; - struct Spots { - //enum DataType type; - int x; - int y; - } spot; - struct Tree { - enum Code next; - struct Node* root; - struct Node* current; - struct Node* deleted; - int result; - } tree; - struct Node { - // need to tree - enum Code next; - int key; // comparable data segment - int value; - struct Node* left; - struct Node* right; - // need to balancing - enum Color { - Red, - Black, - } color; - } node; - struct Allocate { - enum Code next; - long size; - } allocate; -};
--- a/src/tmp/main.c Mon Jan 18 17:50:52 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,81 +0,0 @@ -#include <stdio.h> -#include <unistd.h> - -#include "context.h" -#include "origin_cs.h" - -extern __code initContext(struct Context* context); - -int a; - -__code code1(struct Context* context) { - if(__sync_bool_compare_and_swap(&a, 10, 0)) { - puts("success"); - a = 10; - } else { - puts("failure"); - goto meta(context, Code1); - } -} - -__code code1_stub(struct Context* context) { - goto code1(context); -} - -__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; - pthread_create(&worker_context->thread, NULL, (void*)&start_code, worker_context); - loopCounter->i++; - - goto meta(context, CreateWorker); - } - - loopCounter->i = 0; - goto meta(context, TaskManager); -} - -__code createWorker_stub(struct Context* context) { - goto createWorker(context, &context->data[LoopCounter]->loopCounter, &context->data[Worker]->worker); -} - -__code taskManager(struct Context* context, struct LoopCounter* loopCounter, struct Worker* worker) { - int i = loopCounter->i; - - if (i < worker->num) { - pthread_join(worker->contexts[i].thread, NULL); - loopCounter->i++; - - goto meta(context, TaskManager); - } - - loopCounter->i = 0; - goto meta(context, Exit); -} - -__code taskManager_stub(struct Context* context) { - goto taskManager(context, &context->data[LoopCounter]->loopCounter, &context->data[Worker]->worker); -} - -int main(int argc, char** argv) { - a = 10; - int cpu_num = (int)atoi(argv[1]); - - struct Context* main_context = (struct Context*)malloc(sizeof(struct Context)); - initContext(main_context); - main_context->next = CreateWorker; - - struct Context* worker_contexts = (struct Context*)malloc(sizeof(struct Context)*cpu_num); - - struct Worker* worker = &main_context->data[Worker]->worker; - worker->num = cpu_num; - worker->contexts = worker_contexts; - - for (int i = 0;i<cpu_num;i++) - initContext(&worker_contexts[i]); - - goto start_code(main_context); -}
--- a/src/tmp/origin_cs.c Mon Jan 18 17:50:52 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,17 +0,0 @@ -#include <stdlib.h> -#include "context.h" - -__code meta(struct Context* context, enum Code next) { - goto (context->code[next])(context); -} - -__code start_code(struct Context* context) { - goto meta(context, context->next); -} - -__code exit_code(struct Context* context) { - free(context->code); - free(context->data); - free(context->heapStart); - goto exit(0); -}
--- a/src/tmp/origin_cs.h Mon Jan 18 17:50:52 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,3 +0,0 @@ -extern __code start_code(struct Context* context); -extern __code exit_code(struct Context* context); -extern __code meta(struct Context* context, enum Code next);
--- a/src/tmp/rb_tree.c Mon Jan 18 17:50:52 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,668 +0,0 @@ -#include <stdio.h> - -#include "context.h" -#include "origin_cs.h" - -extern void allocator(struct Context* context); -extern void compare(struct Context* context, struct Tree* tree, int key1, int key2); - -extern int num; - -__code put(struct Context* context, struct Tree* tree, struct Node* root, struct Allocate* allocate) { - allocate->size = sizeof(struct Node); - allocator(context); - - stack_push(context->code_stack, &context->next); - - context->next = StackClear; - stack_push(context->code_stack, &context->next); - - tree->root = &context->data[context->dataNum]->node; - - if (root) { - tree->current = root; - compare(context, tree, tree->current->key, context->data[Node]->node.key); - - goto meta(context, Replace); - } - - goto meta(context, Insert); -} - -__code put_stub(struct Context* context) { - goto put(context, &context->data[Tree]->tree, 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) { - *newNode = *oldNode; - stack_push(context->node_stack, &newNode); - - if (result == EQ) { - newNode->value = context->data[Node]->node.value; - - stack_pop(context->code_stack, &context->next); - goto meta(context, context->next); - } else if (result == GT) { - tree->current = oldNode->right; - newNode->right = context->heap; - } else { - tree->current = oldNode->left; - newNode->left = context->heap; - } - - allocator(context); - - if (tree->current) { - compare(context, tree, tree->current->key, context->data[Node]->node.key); - goto meta(context, Replace); - } - - goto meta(context, Insert); -} - -__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); -} - -__code insertNode(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) { - node->color = Red; - *newNode = *node; - - tree->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); -} - -__code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) { - if (!isEmpty(context->node_stack)) - goto meta(context, InsertCase2); - - tree->root->color = Black; - - stack_pop(context->code_stack, &context->next); - goto meta(context, context->next); -} - -__code insert1_stub(struct Context* context) { - goto insertCase1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); -} - -__code insertCase2(struct Context* context, struct Node* current) { - struct Node* parent; - stack_pop(context->node_stack, &parent); - - if (parent->color == Black) { - stack_pop(context->code_stack, &context->next); - goto meta(context, context->next); - } - - stack_push(context->node_stack, &parent); - goto meta(context, InsertCase3); -} - -__code insert2_stub(struct Context* context) { - goto insertCase2(context, context->data[Tree]->tree.current); -} - -__code insertCase3(struct Context* context, struct Tree* tree, struct Node* current) { - struct Node* parent; - 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; - else - uncle = grandparent->left; - - if (uncle && (uncle->color == Red)) { - parent->color = Black; - uncle->color = Black; - grandparent->color = Red; - tree->current = grandparent; - goto meta(context, InsertCase1); - } - - 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[Tree]->tree, context->data[Tree]->tree.current); -} - -__code insertCase4(struct Context* context, struct Tree* tree, 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); - - tree->current = parent; - - if ((current == parent->right) && (parent == grandparent->left)) { - context->next = InsertCase4_1; - - stack_push(context->code_stack, &context->next); - goto meta(context, RotateL); - } else if ((current == parent->left) && (parent == grandparent->right)) { - context->next = InsertCase4_2; - - stack_push(context->code_stack, &context->next); - goto meta(context, RotateR); - } - - stack_push(context->node_stack, &parent); - tree->current = current; - goto meta(context, InsertCase5); -} - -__code insert4_stub(struct Context* context) { - goto insertCase4(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); -} - -__code insertCase4_1(struct Context* context, struct Tree* tree) { - stack_push(context->node_stack, &tree->current); - tree->current = tree->current->left; - goto meta(context, InsertCase5); -} - -__code insert4_1_stub(struct Context* context) { - goto insertCase4_1(context, &context->data[Tree]->tree); -} - -__code insertCase4_2(struct Context* context, struct Tree* tree) { - stack_push(context->node_stack, &tree->current); - tree->current = tree->current->right; - goto meta(context, InsertCase5); -} - -__code insert4_2_stub(struct Context* context) { - goto insertCase4_2(context, &context->data[Tree]->tree); -} - -__code insertCase5(struct Context* context, struct Tree* tree, struct Node* current) { - struct Node* parent; - struct Node* grandparent; - - stack_pop(context->node_stack, &parent); - stack_pop(context->node_stack, &grandparent); - - parent->color = Black; - grandparent->color = Red; - - tree->current = grandparent; - - if ((current == parent->left) && (parent == grandparent->left)) - goto meta(context, RotateR); - else - goto meta(context, RotateL); -} - -__code insert5_stub(struct Context* context) { - goto insertCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); -} - -__code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree) { - struct Node* tmp = node->right; - struct Node* parent = 0; - - stack_pop(context->node_stack, &parent); - - if (parent) { - if (node == parent->left) - parent->left = tmp; - else - parent->right = tmp; - } else { - tree->root = tmp; - } - - stack_push(context->node_stack, &parent); - - node->right = tmp->left; - tmp->left = node; - tree->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); -} - -__code rotateRight(struct Context* context, struct Node* node, struct Tree* tree) { - struct Node* tmp = node->left; - struct Node* parent = 0; - - stack_pop(context->node_stack, &parent); - - if (parent) { - if (node == parent->left) - parent->left = tmp; - else - parent->right = tmp; - } else { - tree->root = tmp; - } - - stack_push(context->node_stack, &parent); - - node->left = tmp->right; - tmp->right = node; - tree->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); -} - -__code stackClear(struct Context* context, stack_ptr node_stack, struct Tree* tree) { - if (stack_pop(node_stack, &tree->current) == 0) - goto meta(context, StackClear); - - tree->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); -} - - -/* /\* __code get(struct Context* context, struct Tree* tree) { *\/ */ -/* /\* if (tree->root) { *\/ */ -/* /\* tree->current = tree->root; *\/ */ - -/* /\* goto meta(context, Search); *\/ */ -/* /\* } *\/ */ - -/* /\* stack_pop(context->code_stack, &context->next); *\/ */ -/* /\* goto meta(context, context->next); *\/ */ -/* /\* } *\/ */ - -/* /\* __code get_stub(struct Context* context) { *\/ */ -/* /\* 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); *\/ */ - -/* /\* if (tree->result == EQ) { *\/ */ -/* /\* *node = *tree->current; *\/ */ - -/* /\* goto meta(context, context->next); *\/ */ -/* /\* } else if (tree->result == GT) { *\/ */ -/* /\* tree->current = tree->current->right; *\/ */ -/* /\* } else { *\/ */ -/* /\* tree->current = tree->current->left; *\/ */ -/* /\* } *\/ */ - -/* /\* if (tree->current) *\/ */ -/* /\* goto meta(context, Search); *\/ */ - -/* /\* 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 delete(struct Context* context, struct Tree* tree) { *\/ */ -/* /\* if (tree->root) { *\/ */ -/* /\* stack_push(context->code_stack, &context->next); *\/ */ -/* /\* context->next = Delete1; *\/ */ -/* /\* goto meta(context, Get); *\/ */ -/* /\* } *\/ */ - -/* /\* goto meta(context, context->next); *\/ */ -/* /\* } *\/ */ - -/* /\* __code delete_stub(struct Context* context) { *\/ */ -/* /\* goto delete(context, &context->data[Tree]->tree); *\/ */ -/* /\* } *\/ */ - -/* /\* __code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) { *\/ */ -/* /\* allocate->size = sizeof(struct Node); *\/ */ -/* /\* allocator(context); *\/ */ - -/* /\* struct Node* root = tree->root; *\/ */ - -/* /\* tree->root = &context->data[context->dataNum]->node; *\/ */ -/* /\* tree->current = root; *\/ */ - -/* /\* compare(context, tree, tree->current->key, context->data[Node]->node.key); *\/ */ - -/* /\* goto meta(context, Replace_d1); *\/ */ -/* /\* } *\/ */ - -/* /\* __code delete1_stub(struct Context* context) { *\/ */ -/* /\* goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate); *\/ */ -/* /\* } *\/ */ - -/* /\* __code delete2(struct Context* context, struct Node* current) { *\/ */ -/* /\* if (current->color == Black) { *\/ */ -/* /\* struct Node* child = current->right == NULL ? current->left : current->right; *\/ */ -/* /\* current->color = child == NULL ? Black : child->color; *\/ */ - -/* /\* goto meta(context, DeleteCase1); *\/ */ -/* /\* } *\/ */ - -/* /\* goto meta(context, Delete3); *\/ */ -/* /\* } *\/ */ - -/* /\* __code delete2_stub(struct Context* context) { *\/ */ -/* /\* goto delete2(context, context->data[Tree]->tree.current); *\/ */ -/* /\* } *\/ */ - -/* /\* __code delete3(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ -/* /\* struct Node* tmp = current->right == NULL ? current->left : current->right; *\/ */ - -/* /\* if (current->parent) { *\/ */ -/* /\* if (current == current->parent->left) *\/ */ -/* /\* current->parent->left = tmp; *\/ */ -/* /\* else *\/ */ -/* /\* current->parent->right = tmp; *\/ */ -/* /\* } else { *\/ */ -/* /\* tree->root = tmp; *\/ */ -/* /\* } *\/ */ - -/* /\* if (tmp) *\/ */ -/* /\* tmp->parent = current->parent; *\/ */ - -/* /\* if (current->parent == NULL && tmp) *\/ */ -/* /\* tmp->color = Black; *\/ */ - -/* /\* current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL); *\/ */ - -/* /\* stack_pop(context->code_stack, &context->next); *\/ */ -/* /\* goto meta(context, context->next); *\/ */ -/* /\* } *\/ */ - -/* /\* __code delete3_stub(struct Context* context) { *\/ */ -/* /\* goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ -/* /\* } *\/ */ - -/* /\* __code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) { *\/ */ -/* /\* *newNode = *oldNode; *\/ */ - -/* /\* if (result == EQ) *\/ */ -/* /\* goto meta(context, Replace_d2); *\/ */ -/* /\* else if (result == GT) *\/ */ -/* /\* tree->current = newNode->right; *\/ */ -/* /\* else *\/ */ -/* /\* tree->current = newNode->left; *\/ */ - -/* /\* tree->current->parent = newNode; *\/ */ - -/* /\* if (tree->current->left == NULL && tree->current->right == NULL) *\/ */ -/* /\* goto meta(context, Delete2); *\/ */ - -/* /\* if (result == GT) *\/ */ -/* /\* newNode->right = context->heap; *\/ */ -/* /\* else if (result == LT) *\/ */ -/* /\* newNode->left = context->heap; *\/ */ - -/* /\* allocator(context); *\/ */ - -/* /\* compare(context, tree, tree->current->key, context->data[Node]->node.key); *\/ */ - -/* /\* goto meta(context, Replace_d1); *\/ */ -/* /\* } *\/ */ - -/* /\* __code replaceNodeForDelete1_stub(struct Context* context) { *\/ */ -/* /\* goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result); *\/ */ -/* /\* } *\/ */ - -/* /\* __code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) { *\/ */ -/* /\* if (tree->current->left && tree->current->right) { *\/ */ -/* /\* newNode->left->parent = newNode; *\/ */ -/* /\* tree->current = newNode->left; *\/ */ -/* /\* newNode->left = context->heap; *\/ */ -/* /\* tree->deleted = newNode; *\/ */ - -/* /\* allocator(context); *\/ */ -/* /\* tree->current->parent = newNode; *\/ */ - -/* /\* goto meta(context, FindMax1); *\/ */ -/* /\* } *\/ */ - -/* /\* goto meta(context, Delete2); *\/ */ -/* /\* } *\/ */ - -/* /\* __code replaceNodeForDelete2_stub(struct Context* context) { *\/ */ -/* /\* goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node); *\/ */ -/* /\* } *\/ */ - -/* /\* __code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { *\/ */ -/* /\* *newNode = *oldNode; *\/ */ - -/* /\* if (newNode->right) *\/ */ -/* /\* goto meta(context, FindMax2); *\/ */ - -/* /\* tree->deleted->key = newNode->key; *\/ */ -/* /\* tree->deleted->value = newNode->value; *\/ */ - -/* /\* tree->current = newNode; *\/ */ - -/* /\* goto meta(context, Delete2); *\/ */ -/* /\* } *\/ */ - -/* /\* __code findMax1_stub(struct Context* context) { *\/ */ -/* /\* goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); *\/ */ -/* /\* } *\/ */ - - -/* /\* __code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { *\/ */ -/* /\* *newNode = *oldNode; *\/ */ - -/* /\* if (newNode->right->right) { *\/ */ -/* /\* tree->current = newNode->right; *\/ */ -/* /\* newNode->right = context->heap; *\/ */ - -/* /\* allocator(context); *\/ */ -/* /\* tree->current->parent = newNode; *\/ */ - -/* /\* goto meta(context, FindMax2); *\/ */ -/* /\* } *\/ */ - -/* /\* tree->deleted->key = newNode->right->key; *\/ */ -/* /\* tree->deleted->value = newNode->right->value; *\/ */ - -/* /\* tree->current = newNode; *\/ */ - -/* /\* goto meta(context, Delete2); *\/ */ -/* /\* } *\/ */ - -/* /\* __code findMax2_stub(struct Context* context) { *\/ */ -/* /\* goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase1(struct Context* context, struct Node* current) { *\/ */ -/* /\* if (current->parent) *\/ */ -/* /\* goto meta(context, DeleteCase2); *\/ */ - -/* /\* goto meta(context, Delete3); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase1_stub(struct Context* context) { *\/ */ -/* /\* goto deleteCase1(context, context->data[Tree]->tree.current); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ -/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ - -/* /\* if ((sibling == NULL ? Black : sibling->color) == Red) { *\/ */ -/* /\* current->parent->color = Red; *\/ */ -/* /\* sibling->color = Black; *\/ */ - -/* /\* current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap); *\/ */ -/* /\* allocator(context); *\/ */ -/* /\* context->data[context->dataNum]->node = *sibling; *\/ */ - -/* /\* tree->current = current->parent; *\/ */ - -/* /\* context->next = DeleteCase3; *\/ */ -/* /\* stack_push(context->code_stack, &context->next); *\/ */ - -/* /\* if (current == current->parent->left) *\/ */ -/* /\* goto meta(context, RotateL); *\/ */ -/* /\* else *\/ */ -/* /\* goto meta(context, RotateR); *\/ */ -/* /\* } *\/ */ - -/* /\* goto meta(context, DeleteCase3); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase2_stub(struct Context* context) { *\/ */ -/* /\* goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ -/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ - -/* /\* if (current->parent->color == Black && *\/ */ -/* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */ -/* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */ -/* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */ -/* /\* sibling->color = Red; *\/ */ - -/* /\* tree->current = current->parent; *\/ */ -/* /\* goto meta(context, DeleteCase1); *\/ */ -/* /\* } *\/ */ - -/* /\* goto meta(context, DeleteCase4); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase3_stub(struct Context* context) { *\/ */ -/* /\* goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase4(struct Context* context, struct Node* current) { *\/ */ -/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ - -/* /\* if (current->parent->color == Red && *\/ */ -/* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */ -/* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */ -/* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */ -/* /\* sibling->color = Red; *\/ */ -/* /\* current->parent->color = Black; *\/ */ - -/* /\* goto meta(context, Delete3); *\/ */ -/* /\* } *\/ */ - -/* /\* goto meta(context, DeleteCase5); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase4_stub(struct Context* context) { *\/ */ -/* /\* goto deleteCase4(context, context->data[Tree]->tree.current); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ -/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ -/* /\* sibling->parent = current->parent; *\/ */ - -/* /\* if (current == current->parent->left && *\/ */ -/* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */ -/* /\* (sibling->left == NULL ? Black : sibling->left->color) == Red && *\/ */ -/* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */ -/* /\* sibling->color = Red; *\/ */ -/* /\* sibling->left->color = Black; *\/ */ - -/* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */ -/* /\* allocator(context); *\/ */ -/* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */ -/* /\* *tmp = *sibling; *\/ */ -/* /\* tmp->parent = current; *\/ */ - -/* /\* tmp->left = context->heap; *\/ */ -/* /\* allocator(context); *\/ */ -/* /\* context->data[context->dataNum]->node = *sibling->left; *\/ */ -/* /\* context->data[context->dataNum]->node.parent = tmp; *\/ */ - -/* /\* tree->current = tmp; *\/ */ - -/* /\* context->next = DeleteCase6; *\/ */ -/* /\* stack_push(context->code_stack, &context->next); *\/ */ - -/* /\* goto meta(context, RotateR); *\/ */ -/* /\* } else if (current == current->parent->right && *\/ */ -/* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */ -/* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */ -/* /\* (sibling->right == NULL ? Black : sibling->right->color) == Red) { *\/ */ -/* /\* sibling->color = Red; *\/ */ -/* /\* sibling->right->color = Black; *\/ */ - -/* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */ -/* /\* allocator(context); *\/ */ -/* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */ -/* /\* *tmp = *sibling; *\/ */ -/* /\* tmp->parent = current; *\/ */ - -/* /\* tmp->right = context->heap; *\/ */ -/* /\* allocator(context); *\/ */ -/* /\* context->data[context->dataNum]->node = *sibling->right; *\/ */ -/* /\* context->data[context->dataNum]->node.parent = tmp; *\/ */ - -/* /\* tree->current = tmp; *\/ */ - -/* /\* context->next = DeleteCase6; *\/ */ -/* /\* stack_push(context->code_stack, &context->next); *\/ */ -/* /\* goto meta(context, RotateL); *\/ */ -/* /\* } *\/ */ - -/* /\* goto meta(context, DeleteCase6); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase5_stub(struct Context* context) { *\/ */ -/* /\* goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */ -/* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */ - -/* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */ -/* /\* allocator(context); *\/ */ -/* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */ -/* /\* *tmp = *sibling; *\/ */ -/* /\* tmp->parent = current; *\/ */ - -/* /\* tmp->color = current->parent->color; *\/ */ -/* /\* current->parent->color = Black; *\/ */ - -/* /\* context->next = Delete3; *\/ */ -/* /\* stack_push(context->code_stack, &context->next); *\/ */ - -/* /\* if (current == current->parent->left) { *\/ */ -/* /\* tmp->right->color = Black; *\/ */ -/* /\* tree->current = current->parent; *\/ */ - -/* /\* goto meta(context, RotateL); *\/ */ -/* /\* } else { *\/ */ -/* /\* tmp->left->color = Black; *\/ */ -/* /\* tree->current = current->parent; *\/ */ - -/* /\* goto meta(context, RotateR); *\/ */ -/* /\* } *\/ */ -/* /\* } *\/ */ - -/* /\* __code deleteCase6_stub(struct Context* context) { *\/ */ -/* /\* goto deleteCase6(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */ -/* /\* } *\/ */
--- a/src/tmp/stack.c Mon Jan 18 17:50:52 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,68 +0,0 @@ -#include <string.h> -#include "stack.h" - -stack_ptr stack_init(size_t size, int max) { - stack_ptr stack_ptr; - - if ((stack_ptr = calloc(1, sizeof(stack))) == NULL) - return NULL; - - if ((stack_ptr->data = calloc(max, size)) == NULL) { - free(stack_ptr); - return NULL; - } - - stack_ptr->size = size; - stack_ptr->max = max; - stack_ptr->num = 0; - - return stack_ptr; -} - -stack_ptr stack_realloc(stack_ptr stack_ptr, int max) { - if (stack_ptr == NULL) - return NULL; - - if ((stack_ptr->data = realloc(stack_ptr->data, stack_ptr->size*max)) == NULL) - return NULL; - - stack_ptr->max = max; - - return stack_ptr; -} - -void stack_free(stack_ptr stack_ptr) { - if (stack_ptr != NULL && stack_ptr->data != NULL) { - free(stack_ptr->data); - free(stack_ptr); - } -} - -int stack_push(stack_ptr stack_ptr, void* data) { - if (stack_ptr->max <= stack_ptr->num) - return -1; - - memcpy((char*)stack_ptr->data+stack_ptr->num*stack_ptr->size, data, stack_ptr->size); - stack_ptr->num++; - - return 0; -} - -int stack_pop(stack_ptr stack_ptr, void* data) { - if (stack_ptr->num == 0) - return -1; - - stack_ptr->num--; - - memcpy(data, (char*)stack_ptr->data+stack_ptr->num*stack_ptr->size, stack_ptr->size); - - return 0; -} - -int isMax(const stack_ptr stack_ptr) { - return stack_ptr->max<=stack_ptr->num; -} - -int isEmpty(const stack_ptr stack_ptr) { - return stack_ptr->num<=0; -}
--- a/src/tmp/stack.h Mon Jan 18 17:50:52 2016 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,16 +0,0 @@ -#include <stdlib.h> - -typedef struct { - size_t size; - int max; - int num; - void* data; -} stack, *stack_ptr; - -extern stack_ptr stack_init(); -extern stack_ptr stack_realloc(); -extern void stack_free(); -extern int stack_push(); -extern int stack_pop(); -extern int isMax(); -extern int isEmpty();