# HG changeset patch
# User Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
# Date 1453194315 -32400
# Node ID 00d4c6fa49696cf21c1de6050af01918369f8b21
# Parent  ac04428e673974a7fc1639c8f13598d2ce392d99# Parent  547c23f3a898f5cc4847ba34e09078d6184a6060
merge

diff -r 547c23f3a898 -r 00d4c6fa4969 src/CMakeLists.txt
--- a/src/CMakeLists.txt	Tue Jan 19 16:22:04 2016 +0900
+++ b/src/CMakeLists.txt	Tue Jan 19 18:05:15 2016 +0900
@@ -14,4 +14,5 @@
 add_subdirectory(allocate)
 add_subdirectory(list)
 add_subdirectory(llrb)
+add_subdirectory(tmp)
 add_subdirectory(synchronizedQueue)
diff -r 547c23f3a898 -r 00d4c6fa4969 src/parallel_execution/CMakeLists.txt
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/CMakeLists.txt	Tue Jan 19 18:05:15 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
+)
+
diff -r 547c23f3a898 -r 00d4c6fa4969 src/parallel_execution/allocate.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/allocate.c	Tue Jan 19 18:05:15 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;
+}
diff -r 547c23f3a898 -r 00d4c6fa4969 src/parallel_execution/compare.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/compare.c	Tue Jan 19 18:05:15 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;
+    }
+}
diff -r 547c23f3a898 -r 00d4c6fa4969 src/parallel_execution/context.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/context.c	Tue Jan 19 18:05:15 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);
+}
diff -r 547c23f3a898 -r 00d4c6fa4969 src/parallel_execution/context.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/context.h	Tue Jan 19 18:05:15 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;
+};
diff -r 547c23f3a898 -r 00d4c6fa4969 src/parallel_execution/main.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/main.c	Tue Jan 19 18:05:15 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);
+}
diff -r 547c23f3a898 -r 00d4c6fa4969 src/parallel_execution/origin_cs.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/origin_cs.c	Tue Jan 19 18:05:15 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);
+}
diff -r 547c23f3a898 -r 00d4c6fa4969 src/parallel_execution/origin_cs.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/origin_cs.h	Tue Jan 19 18:05:15 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);
diff -r 547c23f3a898 -r 00d4c6fa4969 src/parallel_execution/rb_tree.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/rb_tree.c	Tue Jan 19 18:05:15 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); *\/ */
+/* /\* } *\/ */
diff -r 547c23f3a898 -r 00d4c6fa4969 src/parallel_execution/stack.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/stack.c	Tue Jan 19 18:05:15 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;
+}
diff -r 547c23f3a898 -r 00d4c6fa4969 src/parallel_execution/stack.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/stack.h	Tue Jan 19 18:05:15 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();
diff -r 547c23f3a898 -r 00d4c6fa4969 src/parallel_execution/swap.c
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/swap.c	Tue Jan 19 18:05:15 2016 +0900
@@ -0,0 +1,2 @@
+__code swap(struct Context* context, struct ) {
+