Mercurial > hg > Gears > GearsAgda
changeset 277:9d671e63df74
generate extern
author | mir3636 |
---|---|
date | Thu, 02 Feb 2017 18:29:50 +0900 |
parents | 27bc962020de |
children | 23767f714f4a |
files | src/parallel_execution/CPUWorke.cbc src/parallel_execution/CPUWorker.cbc src/parallel_execution/TaskManagerImpl.cbc src/parallel_execution/allocate.c src/parallel_execution/context.c src/parallel_execution/dependency.c src/parallel_execution/generate_context.pl src/parallel_execution/main.c src/parallel_execution/main.cbc src/parallel_execution/queue.c src/parallel_execution/queue.h src/parallel_execution/rb_tree.c src/parallel_execution/rb_tree.cbc src/parallel_execution/stack.c src/parallel_execution/stack.h src/parallel_execution/taskManager.c src/parallel_execution/time.c src/parallel_execution/time.cbc src/parallel_execution/twice.c src/parallel_execution/twice.cbc src/parallel_execution/worker.c src/parallel_execution/worker.h |
diffstat | 22 files changed, 358 insertions(+), 1996 deletions(-) [+] |
line wrap: on
line diff
--- a/src/parallel_execution/CPUWorke.cbc Wed Feb 01 21:29:21 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,64 +0,0 @@ -#include <libkern/OSAtomic.h> - -#include "context.h" -#include "origin_cs.h" - -static void start_worker(Worker* worker); - -Worker* createCPUWorker(struct Context* context, int id, Queue* queue) { - struct Worker* worker = new Worker(); - struct CPUWorker* cpuWorker = new CPUWorker(); - worker->worker = (union Data*)cpuWorker; - worker->tasks = queue; - cpuWorker->id = id; - worker->taskReceive = C_taskReceiveWorker; - worker->shutdown = C_shutdownWorker; - pthread_create(&worker->worker->CPUWorker.thread, NULL, (void*)&start_worker, worker); - return worker; -} - -static void start_worker(Worker* worker) { - CPUWorker* cpuWorker = (CPUWorker*)worker->worker; - cpuWorker->context = NEW(struct Context); - initContext(cpuWorker->context); - Gearef(cpuWorker->context, Worker)->worker = (union Data*)worker; - goto meta(cpuWorker->context, C_taskReceiveWorker); -} - -__code taskReceiveWorker(struct Worker* worker,struct Queue* queue) { - queue->queue = (union Data*)worker->tasks; - queue->next = C_getTask; - goto meta(context, worker->tasks->take); -} - -__code taskReceiveWorker_stub(struct Context* context) { - CPUWorker* cpuWorker = (CPUWorker *)GearImpl(context, Worker, worker); - pthread_cond_wait(&cpuWorker->cond, &cpuWorker->mutex); - goto taskReceiveWorker(context, &Gearef(context, Worker)->worker->Worker, Gearef(context, Queue)); -} - -__code getTask(struct Worker* worker, struct Context* task) { - if (!task) - return; // end thread - task->worker = worker; - context->next = C_taskReceiveWorker; // set CG after task exec - goto meta(task, task->next); -} - -__code getTask_stub(struct Context* context) { - Worker* worker = &Gearef(context,Worker)->worker->Worker; - struct Context* task = &Gearef(context, Queue)->data->Context; - goto getTask(context, worker, task); -} - -#ifdef USE_CUDA -__code twiceGpu() { - cuMemcpyHtoDAsync(context,context,context,context->stream); - cuLaunchkanel(); - cuMemcpyDtoHAsync(); -} -#endif - -__code shutdownWorker(struct CPUWorker* worker) { -} -
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/parallel_execution/CPUWorker.cbc Thu Feb 02 18:29:50 2017 +0900 @@ -0,0 +1,64 @@ +#include <libkern/OSAtomic.h> + +#include "context.h" +#include "origin_cs.h" + +static void start_worker(Worker* worker); + +Worker* createCPUWorker(struct Context* context, int id, Queue* queue, enum Code next) { + struct Worker* worker = new Worker(); + struct CPUWorker* cpuWorker = new CPUWorker(); + worker->worker = (union Data*)cpuWorker; + worker->tasks = queue; + cpuWorker->id = id; + worker->taskReceive = C_taskReceiveWorker; + worker->shutdown = C_shutdownWorker; + pthread_create(&worker->worker->CPUWorker.thread, NULL, (void*)&start_worker, worker); + return worker; +} + +static void start_worker(Worker* worker) { + CPUWorker* cpuWorker = (CPUWorker*)worker->worker; + cpuWorker->context = NEW(struct Context); + initContext(cpuWorker->context); + Gearef(cpuWorker->context, Worker)->worker = (union Data*)worker; + goto meta(cpuWorker->context, C_taskReceiveWorker); +} + +__code taskReceiveWorker(struct Worker* worker,struct Queue* queue) { + queue->queue = (union Data*)worker->tasks; + queue->next = C_getTask; + goto meta(context, worker->tasks->take); +} + +__code taskReceiveWorker_stub(struct Context* context) { + CPUWorker* cpuWorker = (CPUWorker *)GearImpl(context, Worker, worker); + pthread_cond_wait(&cpuWorker->cond, &cpuWorker->mutex); + goto taskReceiveWorker(context, &Gearef(context, Worker)->worker->Worker, Gearef(context, Queue)); +} + +__code getTask(struct Worker* worker, struct Context* task) { + if (!task) + return; // end thread + task->worker = worker; + context->next = C_taskReceiveWorker; // set CG after task exec + goto meta(task, task->next); +} + +__code getTask_stub(struct Context* context) { + Worker* worker = &Gearef(context,Worker)->worker->Worker; + struct Context* task = &Gearef(context, Queue)->data->Context; + goto getTask(context, worker, task); +} + +#ifdef USE_CUDA +__code twiceGpu() { + cuMemcpyHtoDAsync(context,context,context,context->stream); + cuLaunchkanel(); + cuMemcpyDtoHAsync(); +} +#endif + +__code shutdownWorker(struct CPUWorker* worker) { +} +
--- a/src/parallel_execution/TaskManagerImpl.cbc Wed Feb 01 21:29:21 2017 +0900 +++ b/src/parallel_execution/TaskManagerImpl.cbc Thu Feb 02 18:29:50 2017 +0900 @@ -1,7 +1,4 @@ #include "../context.h" -#include "../stack.h" -#include "../queue.h" -#include "../worker.h" #include "../origin_cs.h" #include <stdio.h>
--- a/src/parallel_execution/allocate.c Wed Feb 01 21:29:21 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,18 +0,0 @@ -#include "context.h" -#include "origin_cs.h" - -union Data* allocator(struct Context* context) { - context->data[++context->dataNum] = context->heap; - context->heap += context->data[D_Allocate]->Allocate.size; - return context->data[context->dataNum]; -} - -__code allocatorCS(struct Context* context, struct Allocate* allocate) { - context->data[++context->dataNum] = context->heap; - context->heap += allocate->size; - goto meta(context, allocate->next); -} - -__code allocator_stub(struct Context* context) { - goto allocatorCS(context, &context->data[D_Allocate]->Allocate); -}
--- a/src/parallel_execution/context.c Wed Feb 01 21:29:21 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,26 +0,0 @@ -#include <stdlib.h> - -#include "context.h" -#include "stack.h" -#include "queue.h" - -#include "c/extern.h" - -__code initContext(struct Context* context) { - context->heapLimit = sizeof(union Data)*ALLOCATE_SIZE; - context->code = (__code(**) (struct Context*)) NEWN(ALLOCATE_SIZE, void*); - context->data = NEWN(ALLOCATE_SIZE, union Data*); - context->heapStart = NEWN(context->heapLimit, char); - context->heap = context->heapStart; - - // context->codeNum = Exit; - context->idgCount = 0; -#include "c/codeGearInit.c" - -#include "c/dataGearInit.c" - - // context->data[D_ActiveQueue] = createSynchronizedQueue(context); - // context->data[D_WaitQueue] = createSynchronizedQueue(context); - - context->dataNum = D_Queue; -}
--- a/src/parallel_execution/dependency.c Wed Feb 01 21:29:21 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,31 +0,0 @@ -#include <stdio.h> -#include "context.h" -#include "origin_cs.h" - -__code meta_waitFor(struct Context* context, struct Queue* queue, enum Code next) { - context->data[D_Queue] = (union Data *)queue; - goto (context->code[next])(context); -} - -__code waitFor1(struct Context* context, struct Task* master, struct Task* slave, struct Element* element) { - element->data = (union Data *)slave; - // enqueue waitMe - goto meta_waitFor(context, /*master->waitMe*/ NULL , /*PutQueue1*/ C_waitFor1); -} - -__code waitFor1_stub(struct Context* context) { - // next think -} - -//__code waitFor2(struct Context* context, struct Task* master, struct Task* slave, struct Element* element) { -// element->task = master; -// task->next = context->next; -// // enqueue waitI -// goto meta_waitFor(context, task->waitI, PutQueue1); -//} -// -//__code waitFor2_stub(struct Context* context) { -// // next think -//} - -
--- a/src/parallel_execution/generate_context.pl Wed Feb 01 21:29:21 2017 +0900 +++ b/src/parallel_execution/generate_context.pl Thu Feb 02 18:29:50 2017 +0900 @@ -63,6 +63,7 @@ my %codeGear; my %dataGear; +my %constructor; # gather module Information for code table initialization for (@ARGV) { @@ -86,6 +87,11 @@ while (<$fd>) { if (/^__code (\w+)_stub\(struct Context\* context\)/ or /^\s__code (\w+)_stub\(struct Context\* context\)/) { $codeGear{$1} = $filename; + } elsif (/^(\w+)(\*)+ create(\w+)\(([^]]*)\)/) { + my $interface = $1; + my $implementation = $3; + my $constructorArgs = $4; + $constructor{$implementation} = [$interface, $constructorArgs]; } } @@ -110,6 +116,10 @@ for my $code ( sort keys %codeGear ) { print $fd "extern __code ${code}_stub(struct Context*);\n"; } + for my $impl ( sort keys %constructor ) { + my ($interface, $constructorArgs) = @{$constructor{$impl}}; + print $fd "extern $interface create${impl}($constructorArgs);\n"; + } print $fd "\n"; open my $fd,">","$ddir/enumCode.h" or die("can't open $ddir/enumCode.h $!"); @@ -130,6 +140,11 @@ #include "../context.h" #include "extern.h" +extern __code start_code(struct Context* context); +extern __code exit_code(struct Context* context); +extern __code meta(struct Context* context, enum Code next); +extern void initContext(struct Context* context); + void initContext(struct Context* context) { context->heapLimit = sizeof(union Data)*ALLOCATE_SIZE; context->code = (__code(**) (struct Context*)) NEWN(ALLOCATE_SIZE, void*); @@ -152,7 +167,35 @@ open my $fd,">","$ddir/$name-context.c" or die("can't open $ddir/$name-context.c $!"); print $fd $context_c; - + +my $meta_call = <<"EOFEOF"; + +__code meta(struct Context* context, enum Code next) { + // printf("meta %d\n",next); + goto (context->code[next])(context); +} + +__code start_code(struct Context* context) { + goto meta(context, context->next); +} + +__code start_code_stub(struct Context* context) { + goto start_code(context); +} + +__code exit_code(struct Context* context) { + free(context->code); + free(context->data); + free(context->heapStart); + goto exit(0); +} + +__code exit_code_stub(struct Context* context) { + goto exit_code(context); +} + +// end $context_c +EOFEOF open my $fd,">","$ddir/enumData.h" or die("can't open $ddir/enumData.h $!"); print $fd "enum DataType {\n";
--- a/src/parallel_execution/main.c Wed Feb 01 21:29:21 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,197 +0,0 @@ -#include <stdio.h> -#include <string.h> -#include <stdlib.h> - -#include "context.h" -#include "origin_cs.h" - -extern union Data* createRedBlackTree(struct Context* context); -extern union Data* createTaskManager(struct Context* context, int numCPU, int numGPU, int numIO); -extern void allocator(struct Context* context); - -int cpu_num = 1; -int length = 102400; -int split = 8; -int* array_ptr; - -void print_queue(struct Element* element) { - while (element) { - printf("%p\n", ((struct Task *)(element->data))); - element = element->next; - } -} - -void print_tree(struct Node* node) { - if (node != 0) { - printf("%d\n", node->value->Array.index); - print_tree(node->left); - print_tree(node->right); - } -} - -__code initDataGears(struct Context* context, struct LoopCounter* loopCounter, struct TaskManager* taskManager) { - loopCounter->tree = &createRedBlackTree(context)->Tree; - loopCounter->i = 0; - taskManager->taskManager = (union Data*)&createTaskManager(context, cpu_num, 0, 0)->TaskManager; - goto meta(context, C_createTask1); -} - -__code initDataGears_stub(struct Context* context) { - goto initDataGears(context, Gearef(context, LoopCounter), Gearef(context, TaskManager)); -} - -__code code1(struct Context* context, struct Time* time) { - printf("cpus:\t\t%d\n", cpu_num); - printf("length:\t\t%d\n", length); - printf("length/task:\t%d\n", length/split); - /* puts("queue"); */ - /* print_queue(context->data[ActiveQueue]->queue.first); */ - /* puts("tree"); */ - /* print_tree(context->data[Tree]->tree.root); */ - /* puts("result"); */ - - time->next = C_code2; - goto meta(context, C_exit_code); - //goto meta(context, C_start_time); -} - -__code code1_stub(struct Context* context) { - goto code1(context, Gearef(context, Time)); -} - -__code code2(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) { - int i = loopCounter->i; - - if (i < length) { - //printf("%d\n", array->array[i]); - if (array->array[i] == (i*2)) { - loopCounter->i++; - goto meta(context, C_code2); - } else - puts("wrong result"); - - } - - goto meta(context, C_code2); -} - -__code code2_stub(struct Context* context) { - goto code2(context, &context->data[D_Node]->Node.value->Array, &context->data[D_LoopCounter]->LoopCounter); -} - -__code createData1(struct Context* context, struct Allocate* allocate, struct LoopCounter* loopCounter) { - int i = loopCounter->i; - - if ((length/split*i) < length) { - goto meta(context, C_createData2); - } - - loopCounter->i = 0; - goto meta(context, C_code1); -} - -__code createData1_stub(struct Context* context) { - goto createData1(context, Gearef(context, Allocate), Gearef(context, LoopCounter)); -} - -__code createData2(struct Context* context, struct LoopCounter* loopCounter, struct Array* array, struct Node* node, Tree* tree) { - int i = loopCounter->i; - - array->index = i; - array->prefix = length/split; - array->array = array_ptr; - - node->key = i; - node->value = (union Data*)array; - - tree->tree = (union Data*)loopCounter->tree; - - tree->next = C_createTask1; - tree->node = node; - - goto meta(context, loopCounter->tree->put); -} - -__code createData2_stub(struct Context* context) { - Array* array = &ALLOCATE(context, Array)->Array; - goto createData2(context, - Gearef(context, LoopCounter), - array, - Gearef(context, Node), - Gearef(context, Tree)); -} - -__code createTask1(struct Context* context, struct LoopCounter* loopCounter, struct TaskManager* taskManager) { - int i = loopCounter->i; - - if ((length/split*i) < length) { - taskManager->next = C_createTask2; - goto meta(context, taskManager->taskManager->TaskManager.createTask); - } - - loopCounter->i = 0; - goto meta(context, C_code1); -} - -__code createTask1_stub(struct Context* context) { - goto createTask1(context, - Gearef(context, LoopCounter), - Gearef(context, TaskManager)); -} - -__code createTask2(struct Context* context, LoopCounter* loopCounter, TaskManager* taskManager,struct Context* task, Array* array) { - int i = loopCounter->i; - - if ((length/split*i) < length) { - array->index = i; - array->prefix = length/split; - array->array = array_ptr; - task->idgCount = 0; - task->next = C_twice; - // task->data[task->idg] = (union Data*)array; - taskManager->next = C_createTask1; - loopCounter->i++; - - goto meta(context, taskManager->taskManager->TaskManager.spawn); - } - loopCounter->i = 0; - taskManager->next = C_code1; - goto meta(context, taskManager->taskManager->TaskManager.shutdown); -} - -__code createTask2_stub(struct Context* context) { - Array* array = &ALLOCATE(context, Array)->Array; - goto createTask2(context, - Gearef(context, LoopCounter), - Gearef(context, TaskManager), - Gearef(context, TaskManager)->context, - array); -} - -void init(int argc, char** argv) { - for (int i = 1; argv[i]; ++i) { - if (strcmp(argv[i], "-cpu") == 0) - cpu_num = (int)atoi(argv[i+1]); - else if (strcmp(argv[i], "-l") == 0) - length = (int)atoi(argv[i+1]); - else if (strcmp(argv[i], "-s") == 0) - split = (int)atoi(argv[i+1]); - } -} - - -int main(int argc, char** argv) { - init(argc, argv); - - array_ptr = NEWN(length, int); - - for(int i=0; i<length; i++) - array_ptr[i]=i; - - struct Context* main_context = NEW(struct Context); - initContext(main_context); - main_context->next = C_initDataGears; - - goto start_code(main_context); -} -
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/parallel_execution/main.cbc Thu Feb 02 18:29:50 2017 +0900 @@ -0,0 +1,197 @@ +#include <stdio.h> +#include <string.h> +#include <stdlib.h> + +#include "context.h" +#include "origin_cs.h" + +extern union Data* createRedBlackTree(struct Context* context); +extern union Data* createTaskManager(struct Context* context, int numCPU, int numGPU, int numIO); +extern void allocator(struct Context* context); + +int cpu_num = 1; +int length = 102400; +int split = 8; +int* array_ptr; + +void print_queue(struct Element* element) { + while (element) { + printf("%p\n", ((struct Task *)(element->data))); + element = element->next; + } +} + +void print_tree(struct Node* node) { + if (node != 0) { + printf("%d\n", node->value->Array.index); + print_tree(node->left); + print_tree(node->right); + } +} + +__code initDataGears(struct Context* context, struct LoopCounter* loopCounter, struct TaskManager* taskManager) { + loopCounter->tree = &createRedBlackTree(context)->Tree; + loopCounter->i = 0; + taskManager->taskManager = (union Data*)&createTaskManager(context, cpu_num, 0, 0)->TaskManager; + goto meta(context, C_createTask1); +} + +__code initDataGears_stub(struct Context* context) { + goto initDataGears(context, Gearef(context, LoopCounter), Gearef(context, TaskManager)); +} + +__code code1(struct Context* context, struct Time* time) { + printf("cpus:\t\t%d\n", cpu_num); + printf("length:\t\t%d\n", length); + printf("length/task:\t%d\n", length/split); + /* puts("queue"); */ + /* print_queue(context->data[ActiveQueue]->queue.first); */ + /* puts("tree"); */ + /* print_tree(context->data[Tree]->tree.root); */ + /* puts("result"); */ + + time->next = C_code2; + goto meta(context, C_exit_code); + //goto meta(context, C_start_time); +} + +__code code1_stub(struct Context* context) { + goto code1(context, Gearef(context, Time)); +} + +__code code2(struct Context* context, struct Array* array, struct LoopCounter* loopCounter) { + int i = loopCounter->i; + + if (i < length) { + //printf("%d\n", array->array[i]); + if (array->array[i] == (i*2)) { + loopCounter->i++; + goto meta(context, C_code2); + } else + puts("wrong result"); + + } + + goto meta(context, C_code2); +} + +__code code2_stub(struct Context* context) { + goto code2(context, &context->data[D_Node]->Node.value->Array, &context->data[D_LoopCounter]->LoopCounter); +} + +__code createData1(struct Context* context, struct Allocate* allocate, struct LoopCounter* loopCounter) { + int i = loopCounter->i; + + if ((length/split*i) < length) { + goto meta(context, C_createData2); + } + + loopCounter->i = 0; + goto meta(context, C_code1); +} + +__code createData1_stub(struct Context* context) { + goto createData1(context, Gearef(context, Allocate), Gearef(context, LoopCounter)); +} + +__code createData2(struct Context* context, struct LoopCounter* loopCounter, struct Array* array, struct Node* node, Tree* tree) { + int i = loopCounter->i; + + array->index = i; + array->prefix = length/split; + array->array = array_ptr; + + node->key = i; + node->value = (union Data*)array; + + tree->tree = (union Data*)loopCounter->tree; + + tree->next = C_createTask1; + tree->node = node; + + goto meta(context, loopCounter->tree->put); +} + +__code createData2_stub(struct Context* context) { + Array* array = &ALLOCATE(context, Array)->Array; + goto createData2(context, + Gearef(context, LoopCounter), + array, + Gearef(context, Node), + Gearef(context, Tree)); +} + +__code createTask1(struct Context* context, struct LoopCounter* loopCounter, struct TaskManager* taskManager) { + int i = loopCounter->i; + + if ((length/split*i) < length) { + taskManager->next = C_createTask2; + goto meta(context, taskManager->taskManager->TaskManager.createTask); + } + + loopCounter->i = 0; + goto meta(context, C_code1); +} + +__code createTask1_stub(struct Context* context) { + goto createTask1(context, + Gearef(context, LoopCounter), + Gearef(context, TaskManager)); +} + +__code createTask2(struct Context* context, LoopCounter* loopCounter, TaskManager* taskManager,struct Context* task, Array* array) { + int i = loopCounter->i; + + if ((length/split*i) < length) { + array->index = i; + array->prefix = length/split; + array->array = array_ptr; + task->idgCount = 0; + task->next = C_twice; + // task->data[task->idg] = (union Data*)array; + taskManager->next = C_createTask1; + loopCounter->i++; + + goto meta(context, taskManager->taskManager->TaskManager.spawn); + } + loopCounter->i = 0; + taskManager->next = C_code1; + goto meta(context, taskManager->taskManager->TaskManager.shutdown); +} + +__code createTask2_stub(struct Context* context) { + Array* array = &ALLOCATE(context, Array)->Array; + goto createTask2(context, + Gearef(context, LoopCounter), + Gearef(context, TaskManager), + Gearef(context, TaskManager)->context, + array); +} + +void init(int argc, char** argv) { + for (int i = 1; argv[i]; ++i) { + if (strcmp(argv[i], "-cpu") == 0) + cpu_num = (int)atoi(argv[i+1]); + else if (strcmp(argv[i], "-l") == 0) + length = (int)atoi(argv[i+1]); + else if (strcmp(argv[i], "-s") == 0) + split = (int)atoi(argv[i+1]); + } +} + + +int main(int argc, char** argv) { + init(argc, argv); + + array_ptr = NEWN(length, int); + + for(int i=0; i<length; i++) + array_ptr[i]=i; + + struct Context* main_context = NEW(struct Context); + initContext(main_context); + main_context->next = C_initDataGears; + + goto start_code(main_context); +} +
--- a/src/parallel_execution/queue.c Wed Feb 01 21:29:21 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,184 +0,0 @@ -#include "queue.h" -#include "origin_cs.h" -#include <stdio.h> - -union Data* createSingleLinkedQueue(struct Context* context) { - struct Queue* queue = &ALLOCATE(context, Queue)->Queue; - struct SingleLinkedQueue* singleLinkedQueue = &ALLOCATE(context, SingleLinkedQueue)->SingleLinkedQueue; - queue->queue = (union Data*)singleLinkedQueue; - singleLinkedQueue->top = NULL; - singleLinkedQueue->last = NULL; - queue->take = C_takeSingleLinkedQueue; - queue->put = C_putSingleLinkedQueue; - queue->isEmpty = C_isEmptySingleLinkedQueue; - queue->clear = C_clearSingleLinkedQueue; - return (union Data*)(queue); -} - -void printQueue1(union Data* data) { - struct Node* node = &data->Element.data->Node; - if (node == NULL) { - printf("NULL"); - } else { - printf("key = %d ,", node->key); - printQueue1((union Data*)data->Element.next); - } -} - -void printQueue(union Data* data) { - printQueue1(data); - printf("\n"); -} - -__code clearSingleLinkedQueue(struct Context* context, struct SingleLinkedQueue* queue,enum Code next) { - queue->top = NULL; - goto meta(context, next); -} - -__code clearSingleLinkedQueue_stub(struct Context* context) { - goto clearSingleLinkedQueue(context, (struct SingleLinkedQueue *)context->data[D_Queue]->Queue.queue->Queue.queue, context->data[D_Queue]->Queue.next); -} - -__code putSingleLinkedQueue(struct Context* context, struct SingleLinkedQueue* queue, struct Element* element, union Data* data, enum Code next) { - element->next = NULL; - element->data = data; - if (queue->last) { - Element* last = queue->last; - last->next = element; - queue->last = element; - } else { - queue->top = element; - queue->last = element; - } - goto meta(context, next); -} - -__code putSingleLinkedQueue_stub(struct Context* context) { - struct Element* element = &ALLOCATE(context, Element)->Element; - goto putSingleLinkedQueue(context, - (struct SingleLinkedQueue *)context->data[D_Queue]->Queue.queue->Queue.queue, - element, - context->data[D_Queue]->Queue.data, - context->data[D_Queue]->Queue.next); -} - -__code takeSingleLinkedQueue(struct Context* context, struct SingleLinkedQueue* queue, union Data** data, enum Code next) { - if (queue->top) { - *data = queue->top->data; - queue->top = queue->top->next; - } else { - *data = NULL; - } - goto meta(context, next); -} - -__code takeSingleLinkedQueue_stub(struct Context* context) { - goto takeSingleLinkedQueue(context, - (struct SingleLinkedQueue *)context->data[D_Queue]->Queue.queue->Queue.queue, - &context->data[D_Queue]->Queue.data, - context->data[D_Queue]->Queue.next); -} - -__code isEmptySingleLinkedQueue(struct Context* context, struct SingleLinkedQueue* queue, enum Code next,enum Code whenEmpty) { - if (queue->top) - goto meta(context, next); - else - goto meta(context, whenEmpty); -} - -__code isEmptySingleLinkedQueue_stub(struct Context* context) { - goto isEmptySingleLinkedQueue(context, - (struct SingleLinkedQueue *)context->data[D_Queue]->Queue.queue->Queue.queue, - context->data[D_Queue]->Queue.next, - context->data[D_Queue]->Queue.whenEmpty); -} - -union Data* createSynchronizedQueue(struct Context* context) { - struct Queue* queue = &ALLOCATE(context, Queue)->Queue; - struct SingleLinkedQueue* singleLinkedQueue = &ALLOCATE(context, SingleLinkedQueue)->SingleLinkedQueue; - queue->queue = (union Data*)singleLinkedQueue; - singleLinkedQueue->top = NULL; - singleLinkedQueue->last = NULL; - queue->take = C_takeSynchronizedQueue; - queue->put = C_putSynchronizedQueue; - queue->isEmpty = C_isEmptySynchronizedQueue; - queue->clear = C_clearSynchronizedQueue; - return (union Data*)(queue); -} - -__code clearSynchronizedQueue(struct Context* context, struct SingleLinkedQueue* queue,enum Code next) { - struct Element* top = queue->top; - if (__sync_bool_compare_and_swap(&queue->top, top, NULL)) { - goto meta(context, next); - } else { - goto meta(context, C_clearSynchronizedQueue); - } -} - -__code clearSynchronizedQueue_stub(struct Context* context) { - goto clearSingleLinkedQueue(context, (struct SingleLinkedQueue *)context->data[D_Queue]->Queue.queue->Queue.queue, context->data[D_Queue]->Queue.next); -} - -__code putSynchronizedQueue(struct Context* context, struct SingleLinkedQueue* queue, struct Element* element, union Data* data, enum Code next) { - element->next = NULL; - element->data = data; - if (queue->last) { - Element* last = queue->last; - if (__sync_bool_compare_and_swap(&queue->last, last, element)) { - last->next = element; - } else { - goto meta(context, C_putSynchronizedQueue); - } - } else { - if (__sync_bool_compare_and_swap(&queue->top, NULL, element)) { - queue->last = element; - } else { - goto meta(context, C_putSynchronizedQueue); - } - } - goto meta(context, next); -} - -__code putSynchronizedQueue_stub(struct Context* context) { - struct Element* element = &ALLOCATE(context, Element)->Element; - goto putSynchronizedQueue(context, - (struct SingleLinkedQueue *)context->data[D_Queue]->Queue.queue->Queue.queue, - element, - context->data[D_Queue]->Queue.data, - context->data[D_Queue]->Queue.next); -} - -__code takeSynchronizedQueue(struct Context* context, struct SingleLinkedQueue* queue, union Data** data, enum Code next) { - if (queue->top) { - struct Element* top = queue->top; - if (__sync_bool_compare_and_swap(&queue->top, top, top->next)) { - *data = top->data; - } else { - goto meta(context, C_takeSynchronizedQueue); - } - } else { - *data = NULL; - } - goto meta(context, next); -} - -__code takeSynchronizedQueue_stub(struct Context* context) { - goto takeSynchronizedQueue(context, - (struct SingleLinkedQueue *)context->data[D_Queue]->Queue.queue->Queue.queue, - &context->data[D_Queue]->Queue.data, - context->data[D_Queue]->Queue.next); -} - -__code isEmptySynchronizedQueue(struct Context* context, struct SingleLinkedQueue* queue, enum Code next,enum Code whenEmpty) { - if (queue->top) - goto meta(context, next); - else - goto meta(context, whenEmpty); -} - -__code isEmptySynchronizedQueue_stub(struct Context* context) { - goto isEmptySynchronizedQueue(context, - (struct SingleLinkedQueue *)context->data[D_Queue]->Queue.queue->Queue.queue, - context->data[D_Queue]->Queue.next, - context->data[D_Queue]->Queue.whenEmpty); -}
--- a/src/parallel_execution/queue.h Wed Feb 01 21:29:21 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,14 +0,0 @@ -#include "context.h" -extern union Data* createSingleLinkedQueue(struct Context* context); - -extern __code putSingleLinkedQueue_stub(struct Context* context); -extern __code takeSingleLinkedQueue_stub(struct Context* context); -extern __code isEmptySingleLinkedQueue_stub(struct Context* context); -extern __code clearSingleLinkedQueue_stub(struct Context* context); - -extern union Data* createSynchronizedQueue(struct Context* context); - -extern __code putSynchronizedQueue_stub(struct Context* context); -extern __code takeSynchronizedQueue_stub(struct Context* context); -extern __code isEmptySynchronizedQueue_stub(struct Context* context); -extern __code clearSynchronizedQueue_stub(struct Context* context);
--- a/src/parallel_execution/rb_tree.c Wed Feb 01 21:29:21 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,727 +0,0 @@ -#include <stdio.h> - -#include "context.h" -#include "origin_cs.h" -#include "stack.h" - -extern enum Relational compare(struct Node* node1, struct Node* node2); - -union Data* createRedBlackTree(struct Context* context) { - struct Tree* tree = &ALLOCATE(context, Tree)->Tree; - struct RedBlackTree* redBlackTree = &ALLOCATE(context, RedBlackTree)->RedBlackTree; - tree->tree = (union Data*)redBlackTree; - redBlackTree->root = NULL; - redBlackTree->nodeStack = &createSingleLinkedStack(context)->Stack; - tree->put = C_putRedBlackTree; - tree->get = C_getRedBlackTree; - // tree->remove = C_removeRedBlackTree; - // tree->clear = C_clearRedBlackTree; - return (union Data*)(tree); -} - -void printTree1(union Data* data) { - struct Node* node = &data->Node; - if (node == NULL) { - printf("NULL"); - } else { - printf("key = %d (", node->key); - printTree1((union Data*)(node->right)); - printf("), ("); - printTree1((union Data*)(node->left)); - printf(")"); - } -} - -void printTree(union Data* data) { - printTree1(data); - printf("\n"); -} - -__code putRedBlackTree(struct Context* context, struct RedBlackTree* traverse, struct Node* node, struct Node* root, struct Node* newNode) { - printTree((union Data*)(traverse->root)); - traverse->newNode = newNode; - traverse->root = newNode; // this should done at stackClear - traverse->parent = NULL; - if (root) { - traverse->current = root; - traverse->result = compare(traverse->current, node); - goto meta(context, C_replaceNode); - } - - goto meta(context, C_insertNode); -} - -__code putRedBlackTree_stub(struct Context* context) { - struct Node* newNode = &ALLOCATE(context, Node)->Node; - goto putRedBlackTree(context, - &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, - Gearef(context, Tree)->node, - Gearef(context, Tree)->tree->Tree.tree->RedBlackTree.root, - newNode - ); -} - -__code replaceNode(struct Context* context, struct RedBlackTree* traverse, struct Node* oldNode, struct Node* newNode, struct Stack* nodeStack) { - traverse->previous = newNode; - *newNode = *oldNode; - nodeStack->stack = (union Data*)traverse->nodeStack; - nodeStack->data = (union Data*)(newNode); - nodeStack->next = C_replaceNode1; - goto meta(context, traverse->nodeStack->push); -} - -__code replaceNode_stub(struct Context* context) { - goto replaceNode(context, - &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, - Gearef(context, Tree)->tree->Tree.tree->RedBlackTree.current, - //context->data[D_RedBlackTree]->RedBlackTree.newNode, - Gearef(context, Tree)->tree->Tree.tree->RedBlackTree.newNode, - Gearef(context, Stack)); -} - -__code replaceNode1(struct Context* context, struct RedBlackTree* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, struct Node* newnewNode, int result, enum Code next) { - if (result == EQ) { - newNode->value = node->value; - // go to stack clear - goto meta(context, next); - } else if (result == GT) { - traverse->current = oldNode->right; - newNode->right = newnewNode; - } else { - traverse->current = oldNode->left; - newNode->left = newnewNode; - } - traverse->newNode = newnewNode; - if (traverse->current) { - traverse->result = compare(traverse->current, node); - goto meta(context, C_replaceNode); - } - goto meta(context, C_insertNode); - -} - -__code replaceNode1_stub(struct Context* context) { - struct Node* newnewNode = &ALLOCATE(context, Node)->Node; - goto replaceNode1(context, - &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, - Gearef(context, Tree)->node, - Gearef(context, Tree)->tree->Tree.tree->RedBlackTree.current, - Gearef(context, Tree)->tree->Tree.tree->RedBlackTree.previous, - newnewNode, - Gearef(context, Tree)->tree->Tree.tree->RedBlackTree.result, - Gearef(context, Tree)->next); -} - -__code insertNode(struct Context* context, struct RedBlackTree* traverse, struct Stack *nodeStack, struct Node* node, struct Node* newNode) { - *newNode = *node; - newNode->color = Red; - traverse->current = newNode; - nodeStack->stack = (union Data*)traverse->nodeStack; - nodeStack->next = C_insertCase1; - goto meta(context, traverse->nodeStack->get2); -} - -__code insertNode_stub(struct Context* context) { - goto insertNode(context, - &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, - Gearef(context, Stack), - Gearef(context, Tree)->node, - Gearef(context, Tree)->tree->Tree.tree->RedBlackTree.newNode); -} - -__code insertCase1(struct Context* context, struct RedBlackTree* traverse, struct Node *parent, struct Node *grandparent) { - if (parent != NULL) { - traverse->parent = parent; - traverse->grandparent = grandparent; - goto meta(context,C_insertCase2); - } - traverse->root->color = Black; - goto meta(context, C_stackClear); -} - -__code insertCase1_stub(struct Context* context) { - goto insertCase1(context, - &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, - &context->data[D_Stack]->Stack.data->Node, - &context->data[D_Stack]->Stack.data1->Node); -} - -__code insertCase2(struct Context* context, struct RedBlackTree* traverse) { - if (traverse->parent->color == Black) { - goto meta(context, C_stackClear); - } - goto meta(context,C_insertCase3); -} - -__code insertCase2_stub(struct Context* context) { - goto insertCase2(context, &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree); -} - -__code insertCase3(struct Context* context, struct RedBlackTree* traverse, struct Stack* nodeStack) { - struct Node* uncle; - - if (traverse->grandparent->left == traverse->parent) - uncle = traverse->grandparent->right; - else - uncle = traverse->grandparent->left; - - if (uncle && (uncle->color == Red)) { - // do insertcase1 on grandparent, stack must be pop by two - traverse->parent->color = Black; - uncle->color = Black; - traverse->grandparent->color = Red; - traverse->current = traverse->grandparent; - nodeStack->stack = (union Data*)traverse->nodeStack; - nodeStack->next = C_insertCase1; - goto meta(context, traverse->nodeStack->pop2); - } - goto meta(context, C_insertCase4); -} - -__code insertCase3_stub(struct Context* context) { - goto insertCase3(context, &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, - Gearef(context, Stack)); -} - -__code insertCase4(struct Context* context, struct RedBlackTree* traverse, struct RotateTree* rotateTree) { - struct Stack* nodeStack = traverse->nodeStack; - - if ((traverse->current == traverse->parent->right) && (traverse->parent == traverse->grandparent->left)) { - traverse->current = traverse->current->left; - traverse->parent = traverse->grandparent; - - rotateTree->traverse = traverse; - rotateTree->next = C_insertCase5; - - nodeStack->stack = (union Data*)traverse->nodeStack; - nodeStack->next = C_rotateLeft; - goto meta(context, nodeStack->pop); - } else if ((traverse->current == traverse->parent->left) && (traverse->parent == traverse->grandparent->right)) { - traverse->parent = traverse->grandparent; - traverse->current = traverse->current->right; - - rotateTree->traverse = traverse; - rotateTree->next = C_insertCase5; - - nodeStack->stack = (union Data*)traverse->nodeStack; - nodeStack->next = C_rotateRight; - goto meta(context, nodeStack->pop); - } - - goto meta(context, C_insertCase5); -} - -__code insertCase4_stub(struct Context* context) { - goto insertCase4(context, &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, Gearef(context, RotateTree)); -} - -__code insertCase5(struct Context* context, struct RedBlackTree* traverse,struct Stack *nodeStack) { - nodeStack->stack = (union Data*)traverse->nodeStack; - nodeStack->next = C_insertCase51; - goto meta(context, traverse->nodeStack->pop2); -} - -__code insertCase5_stub(struct Context* context) { - goto insertCase5(context, &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, Gearef(context, Stack)); -} - -__code insertCase51(struct Context* context, struct RedBlackTree* traverse, struct RotateTree *rotateTree, struct Node* current, struct Node* parent, struct Node* grandparent) { - traverse->parent = parent; - traverse->grandparent = grandparent; - - parent->color = Black; - grandparent->color = Red; - - traverse->current = grandparent; - - rotateTree->traverse = traverse; - rotateTree->next = C_stackClear; - - if ((current == parent->left) && (parent == grandparent->left)) - goto meta(context, C_rotateRight); - else - goto meta(context, C_rotateLeft); -} - -__code insertCase51_stub(struct Context* context) { - struct Node* parent = &context->data[D_Stack]->Stack.data->Node; - struct Node* grandparent = &context->data[D_Stack]->Stack.data1->Node; - goto insertCase51(context, - &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, - Gearef(context, RotateTree), - Gearef(context, Tree)->tree->Tree.tree->RedBlackTree.current, - parent, - grandparent); -} - -__code rotateLeft(struct Context* context, struct RedBlackTree* traverse,struct Stack* nodeStack) { - nodeStack->stack = (union Data*)traverse->nodeStack; - nodeStack->next = C_rotateLeft1; - goto meta(context, traverse->nodeStack->get); -} - -__code rotateLeft_stub(struct Context* context) { - struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse; - goto rotateLeft(context, traverse, Gearef(context, Stack)); -} - -__code rotateLeft1(struct Context* context, struct Node* node, struct RedBlackTree* traverse, struct Node *parent,struct RotateTree *rotateTree) { - struct Node* tmp = node->right; - - if (parent) { - if (node == parent->left) - parent->left = tmp; - else - parent->right = tmp; - } else { - traverse->root = tmp; - } - - node->right = tmp->left; - tmp->left = node; - traverse->current = tmp; - - goto meta(context, rotateTree->next); -} - -__code rotateLeft1_stub(struct Context* context) { - struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse; - struct Node* parent = &context->data[D_Stack]->Stack.data->Node; - goto rotateLeft1(context, - traverse->current, - traverse, - parent, - Gearef(context, RotateTree)); -} - -__code rotateRight(struct Context* context, struct RedBlackTree* traverse,struct Stack *nodeStack) { - nodeStack->stack = (union Data*)traverse->nodeStack; - nodeStack->next = C_rotateRight1; - goto meta(context, traverse->nodeStack->get); -} - -__code rotateRight_stub(struct Context* context) { - struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse; - goto rotateLeft(context, traverse, Gearef(context, Stack)); -} - -__code rotateRight1(struct Context* context, struct Node* node, struct RedBlackTree* traverse,struct Node *parent,struct RotateTree *rotateTree) { - struct Node* tmp = node->left; - - if (parent) { - if (node == parent->left) - parent->left = tmp; - else - parent->right = tmp; - } else { - traverse->root = tmp; - } - - node->left = tmp->right; - tmp->right = node; - traverse->current = tmp; - - goto meta(context, rotateTree->next); -} - -__code rotateRight1_stub(struct Context* context) { - struct RedBlackTree* traverse = context->data[D_RotateTree]->RotateTree.traverse; - struct Node* parent = &context->data[D_Stack]->Stack.data->Node; - goto rotateRight1(context, - traverse->current, - traverse, - parent, - Gearef(context, RotateTree)); -} - -__code stackClear(struct Context* context, struct RedBlackTree* traverse,struct Stack *nodeStack, enum Code next) { - traverse->current = 0; - nodeStack->stack = (union Data*)traverse->nodeStack; - nodeStack->next = next; - goto meta(context, traverse->nodeStack->clear); -} - -__code stackClear_stub(struct Context* context) { - goto stackClear(context, &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, Gearef(context, Stack), - Gearef(context, Tree)->next); -} - - -__code getRedBlackTree(struct Context* context, struct RedBlackTree* traverse, enum Code next) { - if (traverse->root) { - traverse->current = traverse->root; - - goto meta(context, C_search); - } - - goto meta(context, next); -} - -__code getRedBlackTree_stub(struct Context* context) { - goto getRedBlackTree(context, &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, Gearef(context, Tree)->next); -} - -__code search(struct Context* context, struct RedBlackTree* traverse, struct Node* node, enum Code next) { - // compare(context, traverse, traverse->current->key, node->key); - traverse->result = compare(traverse->current, node); - if (traverse->result == EQ) { - *node = *traverse->current; - - goto meta(context, next); - } else if (traverse->result == GT) { - traverse->current = traverse->current->right; - } else { - traverse->current = traverse->current->left; - } - - if (traverse->current) - goto meta(context, C_search); - - goto meta(context, next); -} - -__code search_stub(struct Context* context) { - goto search(context, &Gearef(context, Tree)->tree->Tree.tree->RedBlackTree, Gearef(context, Node), Gearef(context, Tree)->next); -} - -/* /\* __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/parallel_execution/rb_tree.cbc Wed Feb 01 21:29:21 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,295 +0,0 @@ -#include <stdio.h> - -#include "context.h" -#include "origin_cs.h" - -extern enum Relational compare(struct Node* node1, struct Node* node2); - -typedef struct Tree { - union Data* tree; - struct Node* node; - enum Code put; - enum Code get; - enum Code remove; - enum Code clear; - enum Code next; -} Tree; - -typedef struct RedBlackTree { - struct Node* root; - struct Node* current; // reading node of original tree - struct Node* previous; // parent of reading node of original tree - struct Node* newNode; // writing node of new tree - struct Node* parent; - struct Node* grandparent; - struct Stack* nodeStack; - int result; -} RedBlackTree; - -typedef struct RotateTree { - enum Code next; - struct RedBlackTree* traverse; - struct Tree* tree; -} rotateTree; - -typedef struct Node { - int key; // comparable data segment - union Data* value; - struct Node* left; - struct Node* right; - // need to balancing - enum Color { Red, Black, } color; -} node; - -void printTree1(union Data* data) { - struct Node* node = &data->node; - if (node == NULL) { - printf("NULL"); - } else { - printf("key = %d (", node->key); - printTree1((union Data*)(node->right)); - printf("), ("); - printTree1((union Data*)(node->left)); - printf(")"); - } -} - -void printTree(union Data* data) { - printTree1(data); - printf("\n"); -} - -__code put(struct Stack* nodeStack, struct Tree* tree, struct Node* node, struct Traverse* traverse, struct Node* root, __code next(...)) { - printTree((union Data*)(tree->root)); - Node* newNode = new Node(); - traverse->newNode = newNode; - tree->root = newNode; // this should done at stackClear - traverse->parent = NULL; - if (root) { - traverse->current = root; - traverse->result = compare(traverse->current, node); - goto replaceNode(traverse, traverse->current, newNode); - } - - goto insertNode(traverse, traverse->node, newNode); -} - -__code replaceNode(struct Traverse* traverse, struct Node* oldNode, struct Node* newNode) { - Stack* nodeStack = new Stack(); - traverse->previous = newNode; - *newNode = *oldNode; - nodeStack->stack = traverse->nodeStack; - nodeStack->data = newNode; - nodeStack->next = replaceNode1; - goto traverse->nodeStack->push(nodeStack); - // goto traverse->nodeStack->push(newNode, replaceNode1); -} - -__code replaceNode1(struct Traverse* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, int result, __code next(...)) { - Node* newnewNode = new Node(); - if (result == EQ) { - newNode->value = node->value; - // go to stack clear - goto next(...); - } else if (result == GT) { - traverse->current = oldNode->right; - newNode->right = newnewNode; - } else { - traverse->current = oldNode->left; - newNode->left = newnewNode; - } - traverse->newNode = newnewNode; - if (traverse->current) { - traverse->result = compare(traverse->current, node); - goto replaceNode(traverse, traverse->current, newNode); - } - goto insertNode(traverse, traverse->node, newNode); -} - -__code insertNode(struct Traverse* traverse, struct Node* node, struct Node* newNode) { - *newNode = *node; - newNode->color = Red; - traverse->current = newNode; - goto traverse->nodeStack->get2(traverse, tree, insertCase1); -} - -__code insertCase1(struct Node *parent, struct Node *grandparent, struct Traverse* traverse, struct Tree* tree) { - if (parent != NULL) { - traverse->parent = parent; - traverse->grandparent = grandparent; - goto insertCase2(traverse); - } - tree->root->color = Black; - goto stackClear(traverse); -} - -__code insertCase2(struct Traverse* traverse) { - if (traverse->parent->color == Black) { - goto stackClear(traverse); - } - goto insertCase3(traverse); -} - -__code insertCase3(struct Traverse* traverse) { - Stack* nodeStack = new Stack(); - struct Node* uncle; - - if (traverse->grandparent->left == traverse->parent) - uncle = traverse->grandparent->right; - else - uncle = traverse->grandparent->left; - - if (uncle && (uncle->color == Red)) { - // do insertcase1 on grandparent, stack must be pop by two - traverse->parent->color = Black; - uncle->color = Black; - traverse->grandparent->color = Red; - traverse->current = traverse->grandparent; - nodeStack->stack = (union Data*)traverse->nodeStack; - nodeStack->next = insertCase1; - goto traverse->nodeStack->pop2(nodeStack); - } - goto insertCase4(traverse, traverse->rotateTree); -} - -__code insertCase4(struct Traverse* traverse, struct RotateTree* rotateTree) { - struct Stack* nodeStack = traverse->nodeStack; - - if ((traverse->current == traverse->parent->right) && (traverse->parent == traverse->grandparent->left)) { - traverse->current = traverse->current->left; - traverse->parent = traverse->grandparent; - - rotateTree->traverse = traverse; - rotateTree->next = insertCase5; - - nodeStack->stack = (union Data*)traverse->nodeStack; - nodeStack->next = rotateLeft; - goto nodeStack->pop(nodeStack); - } else if ((traverse->current == traverse->parent->left) && (traverse->parent == traverse->grandparent->right)) { - traverse->parent = traverse->grandparent; - traverse->current = traverse->current->right; - - rotateTree->traverse = traverse; - rotateTree->next = insertCase5; - - nodeStack->stack = (union Data*)traverse->nodeStack; - nodeStack->next = rotateRight; - goto nodeStack->pop(nodeStack); - } - - goto insertCase5(traverse); -} - -__code insertCase5(struct Traverse* traverse) { - Stack* stack = new Stack; - nodeStack->stack = (union Data*)traverse->nodeStack; - nodeStack->next = insertCase51; - goto traverse->nodeStack->pop2(nodeStack); -} - -__code insertCase51(struct Traverse* traverse, struct RotateTree *rotateTree, struct Node* current, struct Node* parent, struct Node* grandparent) { - traverse->parent = parent; - traverse->grandparent = grandparent; - - parent->color = Black; - grandparent->color = Red; - - traverse->current = grandparent; - - rotateTree->traverse = traverse; - rotateTree->next = stackClear; - - if ((current == parent->left) && (parent == grandparent->left)) - goto rotateRight(traverse); - else - goto rotateLeft(traverse); -} - -__code rotateLeft(struct Traverse* traverse) { - Stack* nodeStack = new Stack(); - nodeStack->stack = (union Data*)traverse->nodeStack; - nodeStack->next = rotateLeft1; - goto traverse->nodeStack->get(nodeStack); -} - -__code rotateLeft1(struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node *parent,struct RotateTree *rotateTree) { - struct Node* tmp = node->right; - - if (parent) { - if (node == parent->left) - parent->left = tmp; - else - parent->right = tmp; - } else { - tree->root = tmp; - } - - node->right = tmp->left; - tmp->left = node; - traverse->current = tmp; - - goto rotateTree->next(...); -} - -__code rotateRight(struct Traverse* traverse) { - Stack* nodeStack = new Stack(); - nodeStack->stack = (union Data*)traverse->nodeStack; - nodeStack->next = rotateRight1; - goto traverse->nodeStack->get(nodeStack); -} - -__code rotateRight1(struct Node* node, struct Tree* tree, struct Traverse* traverse,struct Node *parent,struct RotateTree *rotateTree) { - struct Node* tmp = node->left; - - if (parent) { - if (node == parent->left) - parent->left = tmp; - else - parent->right = tmp; - } else { - tree->root = tmp; - } - - node->left = tmp->right; - tmp->right = node; - traverse->current = tmp; - - goto rotateTree->next(...); -} - -__code stackClear(struct Traverse* traverse) { - Stack* nodeStack = new Stack(); - traverse->current = 0; - nodeStack->stack = (union Data*)traverse->nodeStack; - nodeStack->next = context->next; - goto traverse->nodeStack->clear(nodeStack); -} - -__code get(struct Tree* tree, struct Traverse* traverse) { - if (tree->root) { - traverse->current = tree->root; - - goto search(traverse, traverse->node); - } - - goto traverse->next(...); -} - -__code search(struct Traverse* traverse, struct Node* node) { - // compare(context, traverse, traverse->current->key, node->key); - traverse->result = compare(traverse->current, node); - if (traverse->result == EQ) { - *node = *traverse->current; - - goto traverse->next(...); - } else if (traverse->result == GT) { - traverse->current = traverse->current->right; - } else { - traverse->current = traverse->current->left; - } - - if (traverse->current) - goto search(traverse, traverse->node); - - goto traverse->next(...); -}
--- a/src/parallel_execution/stack.c Wed Feb 01 21:29:21 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,157 +0,0 @@ -#include "context.h" -#include "stack.h" -#include "origin_cs.h" -#include <stdio.h> - -union Data* createSingleLinkedStack(struct Context* context) { - struct Stack* stack = &ALLOCATE(context, Stack)->Stack; - struct SingleLinkedStack* singleLinkedStack = &ALLOCATE(context, SingleLinkedStack)->SingleLinkedStack; - stack->stack = (union Data*)singleLinkedStack; - singleLinkedStack->top = NULL; - stack->push = C_pushSingleLinkedStack; - stack->pop = C_popSingleLinkedStack; - stack->pop2 = C_pop2SingleLinkedStack; - stack->get = C_getSingleLinkedStack; - stack->get2 = C_get2SingleLinkedStack; - stack->isEmpty = C_isEmptySingleLinkedStack; - stack->clear = C_clearSingleLinkedStack; - return (union Data*)(stack); -} - -void printStack1(union Data* data) { - struct Node* node = &data->Element.data->Node; - if (node == NULL) { - printf("NULL"); - } else { - printf("key = %d ,", node->key); - printStack1((union Data*)data->Element.next); - } -} - -void printStack(union Data* data) { - printStack1(data); - printf("\n"); -} - -__code clearSingleLinkedStack(struct Context* context, struct SingleLinkedStack* stack,enum Code next) { - stack->top = NULL; - goto meta(context, next); -} - -__code clearSingleLinkedStack_stub(struct Context* context) { - goto clearSingleLinkedStack(context, (struct SingleLinkedStack *)context->data[D_Stack]->Stack.stack->Stack.stack, context->data[D_Stack]->Stack.next); -} - -__code pushSingleLinkedStack(struct Context* context, struct SingleLinkedStack* stack, struct Element* element, union Data* data, enum Code next) { - element->next = stack->top; - element->data = data; - stack->top = element; - goto meta(context, next); -} - -__code pushSingleLinkedStack_stub(struct Context* context) { - struct Element* element = &ALLOCATE(context, Element)->Element; - goto pushSingleLinkedStack(context, - (struct SingleLinkedStack *)context->data[D_Stack]->Stack.stack->Stack.stack, - element, - context->data[D_Stack]->Stack.data, - context->data[D_Stack]->Stack.next); -} - -__code popSingleLinkedStack(struct Context* context, struct SingleLinkedStack* stack, union Data** data, enum Code next) { - if (stack->top) { - *data = stack->top->data; - stack->top = stack->top->next; - } else { - *data = NULL; - } - goto meta(context, next); -} - -__code popSingleLinkedStack_stub(struct Context* context) { - goto popSingleLinkedStack(context, - (struct SingleLinkedStack *)context->data[D_Stack]->Stack.stack->Stack.stack, - &context->data[D_Stack]->Stack.data, - context->data[D_Stack]->Stack.next); -} - -__code pop2SingleLinkedStack(struct Context* context, struct SingleLinkedStack* stack, union Data** _data, union Data** _data1, enum Code next) { - union Data* data; - union Data* data1; - if (stack->top) { - data = stack->top->data; - stack->top = stack->top->next; - } else { - data = NULL; - } - if (stack->top) { - data1 = stack->top->data; - stack->top = stack->top->next; - } else { - data1 = NULL; - } - *_data = data; - *_data1 = data1; - goto meta(context, next); -} - -__code pop2SingleLinkedStack_stub(struct Context* context) { - goto pop2SingleLinkedStack(context, - (struct SingleLinkedStack *)context->data[D_Stack]->Stack.stack->Stack.stack, - &context->data[D_Stack]->Stack.data, - &context->data[D_Stack]->Stack.data1, - context->data[D_Stack]->Stack.next); -} - -__code getSingleLinkedStack(struct Context* context, struct SingleLinkedStack* stack, union Data** data, enum Code next) { - if (stack->top) - *data = stack->top->data; - else - *data = NULL; - goto meta(context, next); -} - -__code getSingleLinkedStack_stub(struct Context* context) { - goto getSingleLinkedStack(context, - (struct SingleLinkedStack *)context->data[D_Stack]->Stack.stack->Stack.stack, - &context->data[D_Stack]->Stack.data, - context->data[D_Stack]->Stack.next); -} - -__code get2SingleLinkedStack(struct Context* context, struct SingleLinkedStack* stack, union Data** data, union Data** data1, enum Code next) { - if (stack->top) { - *data = stack->top->data; - if (stack->top->next) { - *data1 = stack->top->next->data; - } else { - *data1 = NULL; - } - } else { - *data = NULL; - *data1 = NULL; - } - goto meta(context, next); -} - -__code get2SingleLinkedStack_stub(struct Context* context) { - goto get2SingleLinkedStack(context, - (struct SingleLinkedStack *)context->data[D_Stack]->Stack.stack->Stack.stack, - &context->data[D_Stack]->Stack.data, - &context->data[D_Stack]->Stack.data1, - context->data[D_Stack]->Stack.next); -} - -__code isEmptySingleLinkedStack(struct Context* context, struct SingleLinkedStack* stack, enum Code next,enum Code whenEmpty) { - if (stack->top) - goto meta(context, next); - else - goto meta(context, whenEmpty); -} - -__code isEmptySingleLinkedStack_stub(struct Context* context) { - goto isEmptySingleLinkedStack(context, - (struct SingleLinkedStack *)context->data[D_Stack]->Stack.stack->Stack.stack, - context->data[D_Stack]->Stack.next, - context->data[D_Stack]->Stack.whenEmpty); -} -
--- a/src/parallel_execution/stack.h Wed Feb 01 21:29:21 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,2 +0,0 @@ -#include "context.h" -extern union Data* createSingleLinkedStack(struct Context* context);
--- a/src/parallel_execution/taskManager.c Wed Feb 01 21:29:21 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,154 +0,0 @@ -#include "context.h" -#include "stack.h" -#include "queue.h" -#include "worker.h" -#include "origin_cs.h" -#include <stdio.h> - -void createWorkers(struct Context* context, TaskManager* taskManeger, TaskManagerImpl* taskManagerImpl); - -union Data* createTaskManager(struct Context* context, int numCPU, int numGPU, int numIO) { - struct TaskManager* taskManager = &ALLOCATE(context, TaskManager)->TaskManager; - // 0...numIO-1 IOProcessor - // numIO...numIO+numGPU-1 GPUProcessor - // numIO+numGPU...numIO+numGPU+numCPU-1 CPUProcessor - taskManager->io = 0; - taskManager->gpu = numIO; - taskManager->cpu = numIO+numGPU; - taskManager->maxCPU = numIO+numGPU+numCPU; - taskManager->createTask = C_createTask; - taskManager->spawn = C_spawnTaskManager; - taskManager->shutdown = C_shutdownTaskManager; - struct TaskManagerImpl* taskManagerImpl = &ALLOCATE(context, TaskManagerImpl)->TaskManagerImpl; - taskManager->taskManager = (union Data*)taskManagerImpl; - taskManagerImpl -> activeQueue = &createSingleLinkedQueue(context)->Queue; - taskManagerImpl -> taskQueue = &createSingleLinkedQueue(context)->Queue; - taskManagerImpl -> numWorker = taskManager->maxCPU; - createWorkers(context, taskManager, taskManagerImpl); - return (union Data*)(taskManager); -} - -void createWorkers(struct Context* context, TaskManager* taskManager, TaskManagerImpl* taskManagerImpl) { - int i = 0; - taskManagerImpl->workers = (Worker**)ALLOC_ARRAY(context, Worker, taskManager->maxCPU); - for (;i<taskManager->gpu;i++) { - Queue* queue = &createSynchronizedQueue(context)->Queue; - taskManagerImpl->workers[i] = (Worker*)createCPUWorker(context, i, queue); - } - for (;i<taskManager->cpu;i++) { -#ifdef USE_CUDA -#else - Queue* queue = &createSynchronizedQueue(context)->Queue; - taskManagerImpl->workers[i] = (Worker*)createCPUWorker(context, i, queue); -#endif - } - for (;i<taskManager->maxCPU;i++) { - Queue* queue = &createSynchronizedQueue(context)->Queue; - taskManagerImpl->workers[i] = (Worker*)createCPUWorker(context, i, queue); - } -} - -__code createTask(struct Context* context, TaskManager* taskManager) { - taskManager->context = NEW(struct Context); - initContext(taskManager->context); - goto meta(context, C_setWorker); -} - -__code createTask_stub(struct Context* context) { - goto createTask(context, Gearef(context,TaskManager)); -} - -__code setWorker(struct Context* context, TaskManagerImpl* taskManager, struct Context* task, enum Code next) { - task->workerId = taskManager->sendWorkerIndex; - if(++taskManager->sendWorkerIndex >= taskManager->numWorker) { - taskManager->sendWorkerIndex = 0; - } - goto meta(context, next); -} - -__code setWorker_stub(struct Context* context) { - TaskManagerImpl* taskManager = (TaskManagerImpl*)GearImpl(context, TaskManager, taskManager); - goto setWorker(context, taskManager, Gearef(context, TaskManager)->context, Gearef(context, TaskManager)->next); -} - -__code spawnTaskManager(struct Context* context, struct TaskManagerImpl* taskManager, struct Queue* queue, struct Context* task, enum Code next) { - if (task->idgCount == 0) { - // enqueue activeQueue - queue->queue = (union Data*)taskManager->activeQueue; - } else { - // enqueue waitQueue - queue->queue = (union Data*)taskManager->taskQueue; - } - queue->data = (union Data*)task; - queue->next = C_spawnTaskManager1; - goto meta(context, queue->queue->Queue.put); -} - -__code spawnTaskManager_stub(struct Context* context) { - TaskManagerImpl* taskManager = (TaskManagerImpl*)GearImpl(context, TaskManager, taskManager); - pthread_mutex_lock(&taskManager->mutex); - goto spawnTaskManager(context, - taskManager, - Gearef(context, Queue), - Gearef(context, TaskManager)->context, - Gearef(context, TaskManager)->next); -} - - -__code spawnTaskManager1(struct Context* context, struct TaskManagerImpl* taskManager) { - pthread_mutex_unlock(&taskManager->mutex); - goto meta(context, C_taskSend); -} - -__code spawnTaskManager1_stub(struct Context* context) { - TaskManagerImpl* taskManager = (TaskManagerImpl*)GearImpl(context, TaskManager, taskManager); - goto spawnTaskManager1(context, - taskManager); -} - -__code taskSend(struct Context* context, TaskManagerImpl* taskManager, Queue* queue) { - queue->queue = (union Data*)taskManager->activeQueue; - queue->next = C_taskSend1; - goto meta(context, taskManager->activeQueue->take); -} - -__code taskSend_stub(struct Context* context) { - TaskManagerImpl* taskManager = (TaskManagerImpl*)GearImpl(context, TaskManager, taskManager); - goto taskSend(context, taskManager, Gearef(context, Queue)); -} - -__code taskSend1(struct Context* context, TaskManagerImpl* taskManager, Queue* queue, struct Context* task, enum Code next) { - struct Queue* tasks = taskManager->workers[task->workerId]->tasks; - queue->queue = (union Data*)tasks; - queue->data = (union Data*)task; - queue->next = next; - pthread_cond_signal(&taskManager->workers[task->workerId]->worker->CPUWorker.cond); - goto meta(context, tasks->put); -} - -__code taskSend1_stub(struct Context* context) { - TaskManagerImpl* taskManager = (TaskManagerImpl*)GearImpl(context, TaskManager, taskManager); - goto taskSend1(context, taskManager, Gearef(context, Queue), Gearef(context, TaskManager)->context, Gearef(context, TaskManager)->next); -} - -__code shutdownTaskManager(struct Context* context, struct LoopCounter* loopCounter, TaskManager* taskManager, TaskManagerImpl* taskManagerImpl, Queue* queue, enum Code next) { - int i = loopCounter->i; - if (taskManager->cpu <= i && i < taskManager->maxCPU) { - struct Queue* tasks = taskManagerImpl->workers[i]->tasks; - queue->queue = (union Data*)tasks; - queue->data = NULL; - queue->next = next; - goto meta(context, tasks->put); - pthread_join(taskManagerImpl->workers[i]->worker->CPUWorker.thread, NULL); - loopCounter->i++; - goto meta(context, C_shutdownTaskManager); - } - - loopCounter->i = 0; - goto meta(context, taskManager->next); -} - -__code shutdownTaskManager_stub(struct Context* context) { - TaskManagerImpl* taskManagerImpl = (TaskManagerImpl*)GearImpl(context, TaskManager, taskManager); - goto shutdownTaskManager(context, Gearef(context, LoopCounter), Gearef(context, TaskManager), taskManagerImpl, Gearef(context, Queue), Gearef(context, TaskManager)->next); -}
--- a/src/parallel_execution/time.c Wed Feb 01 21:29:21 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,31 +0,0 @@ -#include <stdio.h> -#include <sys/time.h> - -#include "context.h" -#include "origin_cs.h" - -__code start_time(struct Context* context, struct Time* time) { - struct timeval tv; - gettimeofday(&tv, NULL); - - time->time = tv.tv_sec + (double)tv.tv_usec*1e-6; - - goto meta(context, time->next); -} - -__code start_time_stub(struct Context* context) { - goto start_time(context, &context->data[D_Time]->Time); -} - -__code end_time(struct Context* context, struct Time* time) { - struct timeval tv; - gettimeofday(&tv, NULL); - - printf("%0.6f\n", (tv.tv_sec+(double)tv.tv_usec*1e-6) - time->time); - - goto meta(context, time->next); -} - -__code end_time_stub(struct Context* context) { - goto end_time(context, Gearef(context, Time)); -}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/parallel_execution/time.cbc Thu Feb 02 18:29:50 2017 +0900 @@ -0,0 +1,31 @@ +#include <stdio.h> +#include <sys/time.h> + +#include "context.h" +#include "origin_cs.h" + +__code start_time(struct Context* context, struct Time* time) { + struct timeval tv; + gettimeofday(&tv, NULL); + + time->time = tv.tv_sec + (double)tv.tv_usec*1e-6; + + goto meta(context, time->next); +} + +__code start_time_stub(struct Context* context) { + goto start_time(context, &context->data[D_Time]->Time); +} + +__code end_time(struct Context* context, struct Time* time) { + struct timeval tv; + gettimeofday(&tv, NULL); + + printf("%0.6f\n", (tv.tv_sec+(double)tv.tv_usec*1e-6) - time->time); + + goto meta(context, time->next); +} + +__code end_time_stub(struct Context* context) { + goto end_time(context, Gearef(context, Time)); +}
--- a/src/parallel_execution/twice.c Wed Feb 01 21:29:21 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,22 +0,0 @@ -#include <stdio.h> - -#include "context.h" -#include "origin_cs.h" - -__code twice(struct Context* context, struct LoopCounter* loopCounter, int index, int prefix, int* array, struct Context* workerContext) { - int i = loopCounter->i; - if (i < prefix) { - array[i+index*prefix] = array[i+index*prefix]*2; - loopCounter->i++; - - goto meta(context, C_twice); - } - - loopCounter->i = 0; - goto meta(workerContext, workerContext->next); -} - -__code twice_stub(struct Context* context) { - struct Context* workerContext = context->worker->worker->CPUWorker.context; - goto twice(context, Gearef(context, LoopCounter), 0, 0, NULL, workerContext); -}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/parallel_execution/twice.cbc Thu Feb 02 18:29:50 2017 +0900 @@ -0,0 +1,22 @@ +#include <stdio.h> + +#include "context.h" +#include "origin_cs.h" + +__code twice(struct Context* context, struct LoopCounter* loopCounter, int index, int prefix, int* array, struct Context* workerContext) { + int i = loopCounter->i; + if (i < prefix) { + array[i+index*prefix] = array[i+index*prefix]*2; + loopCounter->i++; + + goto meta(context, C_twice); + } + + loopCounter->i = 0; + goto meta(workerContext, workerContext->next); +} + +__code twice_stub(struct Context* context) { + struct Context* workerContext = context->worker->worker->CPUWorker.context; + goto twice(context, Gearef(context, LoopCounter), 0, 0, NULL, workerContext); +}
--- a/src/parallel_execution/worker.c Wed Feb 01 21:29:21 2017 +0900 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000 @@ -1,68 +0,0 @@ -#include <libkern/OSAtomic.h> - -#include "context.h" -#include "origin_cs.h" - -static void start_worker(Worker* worker); - -union Data* createCPUWorker(struct Context* context, int id, Queue* queue) { - struct Worker* worker = ALLOC(context, Worker); - struct CPUWorker* cpuWorker = ALLOC(context, CPUWorker); - worker->worker = (union Data*)cpuWorker; - worker->tasks = queue; - cpuWorker->id = id; - worker->taskReceive = C_taskReceiveWorker; - worker->shutdown = C_shutdownWorker; - pthread_create(&worker->worker->CPUWorker.thread, NULL, (void*)&start_worker, worker); - return (union Data*)(worker); -} - -static void start_worker(Worker* worker) { - CPUWorker* cpuWorker = (CPUWorker*)worker->worker; - cpuWorker->context = NEW(struct Context); - initContext(cpuWorker->context); - Gearef(cpuWorker->context, Worker)->worker = (union Data*)worker; - goto meta(cpuWorker->context, C_taskReceiveWorker); -} - -__code taskReceiveWorker(struct Context* context, Worker* worker, Queue* queue) { - queue->queue = (union Data*)worker->tasks; - queue->next = C_getTask; - goto meta(context, worker->tasks->take); -} - -__code taskReceiveWorker_stub(struct Context* context) { - CPUWorker* cpuWorker = (CPUWorker *)GearImpl(context, Worker, worker); - pthread_cond_wait(&cpuWorker->cond, &cpuWorker->mutex); - goto taskReceiveWorker(context, &Gearef(context, Worker)->worker->Worker, Gearef(context, Queue)); -} - -__code getTask(struct Context* context, Worker* worker, struct Context* task) { - if (!task) - return; // end thread - task->worker = worker; - context->next = C_taskReceiveWorker; // set CG after task exec - goto meta(task, task->next); -} - -__code getTask_stub(struct Context* context) { - Worker* worker = &Gearef(context,Worker)->worker->Worker; - struct Context* task = &Gearef(context, Queue)->data->Context; - goto getTask(context, worker, task); -} - -#ifdef USE_CUDA -__code twiceGpu(struct Context* context) { - cuMemcpyHtoDAsync(context,context,context,context->stream); - cuLaunchkanel(); - cuMemcpyDtoHAsync(); -} -#endif - -__code shutdownWorker(struct Context* context, CPUWorker* worker) { -} - -__code shutdownWorker_stub(struct Context* context) { - CPUWorker* worker = (CPUWorker *)GearImpl(context, Worker, worker); - goto shutdownWorker(context,worker); -}