changeset 1001:40817b3f91e2

merge
author ichikitakahiro <e165713@ie.u-ryukyu.ac.jp>
date Thu, 23 Dec 2021 16:59:31 +0900
parents d8142d91bc71 (current diff) 088a7d2b203d (diff)
children dad078c90f29 d3355697c87c
files src/parallel_execution/CMakeLists.txt
diffstat 10 files changed, 648 insertions(+), 29 deletions(-) [+]
line wrap: on
line diff
--- a/src/parallel_execution/CMakeLists.txt	Thu Dec 23 16:59:01 2021 +0900
+++ b/src/parallel_execution/CMakeLists.txt	Thu Dec 23 16:59:31 2021 +0900
@@ -240,7 +240,7 @@
   TARGET
     gearsDirectory
   SOURCES
-    TaskManagerImpl.cbc CPUWorker.cbc SingleLinkedQueue.cbc SingleLinkedStack.cbc AtomicReference.cbc SynchronizedQueue.cbc FileSystemTree.cbc examples/gearsDirectory/GearsDirectoryImpl.cbc examples/gearsDirectory/GearsDirectory_test.cbc compare.c
+    TaskManagerImpl.cbc CPUWorker.cbc SingleLinkedQueue.cbc SingleLinkedStack.cbc AtomicReference.cbc SynchronizedQueue.cbc FileSystemTree.cbc EntryTree.cbc examples/gearsDirectory/GearsDirectoryImpl.cbc examples/gearsDirectory/GearsDirectory_test.cbc compare.c
 )
 
 GearsCommand(
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/ETree.h	Thu Dec 23 16:59:31 2021 +0900
@@ -0,0 +1,13 @@
+typedef struct ETree<>{
+    /* future Code */
+    /* Type* tree; */
+    /* Type* node; */
+    union Data* eTree;
+    struct Node* node;
+    struct ETree* treeParent;
+    __code put(Impl* eTree,Type* node, __code next(...));
+    __code get(Impl* eTree, Type* node, __code next(...));
+    __code remove(Impl* eTree,Type* node, __code next(...));
+    // __code clearRedBlackTree();
+    __code next(...);
+} ETree;
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/EntryTree.cbc	Thu Dec 23 16:59:31 2021 +0900
@@ -0,0 +1,604 @@
+#include <stdio.h>
+
+#include "../context.h"
+#interface "ETree.h"
+#interface "Stack.h"
+
+extern enum Relational compare(struct Node* node1, struct Node* node2);
+
+ETree* createEntryTree(struct Context* context, struct ETree* cDirectory) {
+    struct ETree* eTree = new ETree();
+    struct EntryTree* entryTree = new EntryTree();
+    eTree->eTree = (union Data*)entryTree;
+    entryTree->root = NULL;
+    entryTree->nodeStack = createSingleLinkedStack(context);
+    eTree->treeParent = cDirectory;
+    eTree->put = C_putEntryTree;
+    eTree->get = C_getEntryTree;
+    eTree->remove = C_removeEntryTree;
+    // eTree->clear = C_clearEntryTree;
+    return eTree;
+}
+
+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 putEntryTree(struct EntryTree* eTree, struct Node* node) {
+    struct Node* newNode = &ALLOCATE(context, Node)->Node;
+    struct Node* root = eTree->root;
+    //printTree((union Data*)(eTree->root));
+    eTree->newNode = newNode;
+    eTree->root = newNode; // this should done at stackClear
+    eTree->parent = NULL;
+    if (root) {
+        eTree->current = root;
+        eTree->result = compare(eTree->current, node);
+        eTree->findNodeNext = C_insertNode;
+        goto findNode(eTree);
+    }
+    goto insertNode(eTree, node);
+}
+
+__code findNode(struct EntryTree* eTree) {
+    struct Stack* nodeStack = eTree->nodeStack;
+    struct Node* oldNode = eTree->current;
+    struct Node* newNode = eTree->newNode;
+    eTree->previous = newNode;
+    *newNode = *oldNode;
+    goto nodeStack->push((union Data*)newNode, findNode1);
+}
+
+__code findNode1(struct EntryTree* eTree, struct Node* node, __code next(...)) {
+    struct Node* oldNode = eTree->current;
+    struct Node* newNode = eTree->previous;
+    struct Node* newnewNode = &ALLOCATE(context, Node)->Node;
+    int result = eTree->result;
+    if (result == EQ) {
+        newNode->value = node->value;
+        // go to stack clear
+        goto next(...);
+    } else if (result == GT) {
+        eTree->current = oldNode->right;
+        newNode->right = newnewNode;
+    } else {
+        eTree->current = oldNode->left;
+        newNode->left = newnewNode;
+    }
+    eTree->newNode = newnewNode;
+    if (eTree->current) {
+        eTree->result = compare(eTree->current, node);
+        goto findNode(eTree);
+    }
+    goto meta(context, eTree->findNodeNext);
+    //   gato eTree->findNodeNext(eTree, node);
+    
+}
+
+__code insertNode(struct EntryTree* eTree, struct Node* node) {
+    struct Stack* nodeStack = eTree->nodeStack;
+    struct Node* newNode = eTree->newNode;
+    *newNode = *node;
+    newNode->color = Red;
+    eTree->current = newNode;
+    goto nodeStack->get2(insertCase1);
+}
+
+__code insertCase1(struct EntryTree* eTree, struct Node *parent, struct Node *grandparent) {
+    if (parent != NULL) {
+        eTree->parent = parent;
+        eTree->grandparent = grandparent;
+        goto insertCase2(eTree);
+    }
+    eTree->root->color = Black;
+    goto stackClear();
+}
+
+__code insertCase1_stub(struct Context* context) {
+    goto insertCase1(context, 
+        &Gearef(context, ETree)->eTree->ETree.eTree->EntryTree,
+        &context->data[D_Stack]->Stack.data->Node,
+        &context->data[D_Stack]->Stack.data1->Node);
+}
+
+__code insertCase2(struct EntryTree* eTree) {
+    if (eTree->parent->color == Black) {
+        goto stackClear();
+    }
+    goto insertCase3(eTree);
+}
+
+__code insertCase3(struct EntryTree* eTree) {
+    struct Stack* nodeStack = eTree->nodeStack;
+    struct Node* uncle;
+
+    if (eTree->grandparent->left == eTree->parent) {
+        uncle = eTree->grandparent->right;
+    } else {
+        uncle = eTree->grandparent->left;
+    }
+
+    if (uncle && (uncle->color == Red)) {
+        // do insertcase1 on grandparent, stack must be pop by two
+        eTree->parent->color = Black;
+        uncle->color = Black;
+        eTree->grandparent->color = Red;
+        eTree->current = eTree->grandparent;
+        goto nodeStack->pop2(insertCase1);
+    }
+    goto insertCase4();
+}
+
+__code insertCase4(struct EntryTree* eTree, struct RotateTree* rotateTree) {
+    struct Stack* nodeStack = eTree->nodeStack;
+
+    if ((eTree->current == eTree->parent->right) && (eTree->parent == eTree->grandparent->left)) {
+        eTree->current = eTree->current->left;
+        eTree->parent = eTree->grandparent;
+
+        rotateTree->traverse = eTree;
+        rotateTree->next = C_insertCase5;
+
+        goto nodeStack->pop(rotateLeft);
+    } else if ((eTree->current == eTree->parent->left) && (eTree->parent == eTree->grandparent->right)) {
+        eTree->parent = eTree->grandparent;
+        eTree->current = eTree->current->right;
+
+        rotateTree->traverse = eTree;
+        rotateTree->next = C_insertCase5;
+
+        goto nodeStack->pop(rotateRight);
+    }
+
+    goto insertCase5();
+}
+
+__code insertCase5(struct EntryTree* eTree) {
+    struct Stack* nodeStack = eTree->nodeStack;
+    goto nodeStack->pop2(insertCase51);
+}
+
+__code insertCase51(struct EntryTree* eTree, struct RotateTree* rotateTree, struct Node* parent, struct Node* grandparent) {
+    struct Node* current = eTree->current;
+    eTree->parent = parent;
+    eTree->grandparent = grandparent;
+
+    parent->color = Black;
+    grandparent->color = Red;
+
+    eTree->current = grandparent;
+
+    rotateTree->traverse = eTree;
+    rotateTree->next = C_stackClear;
+
+    if ((current == parent->left) && (parent == grandparent->left)){
+        goto rotateRight();
+    } else {
+        goto 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, ETree)->eTree->ETree.eTree->EntryTree,
+                      Gearef(context, RotateTree),
+                      parent,
+                      grandparent);
+}
+
+__code rotateLeft(struct EntryTree* eTree) {
+    struct Stack* nodeStack = eTree->nodeStack;
+    goto nodeStack->get(rotateLeft1);
+}
+
+__code rotateLeft_stub(struct Context* context) {
+    struct EntryTree* traverse = context->data[D_RotateTree]->RotateTree.traverse;
+    goto rotateLeft(context, traverse);
+}
+    
+__code rotateLeft1(struct Node* node, struct EntryTree* eTree, 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 {
+        eTree->root = tmp;
+    }
+
+    node->right = tmp->left;
+    tmp->left = node;
+    eTree->current = tmp;
+    
+    goto meta(context, rotateTree->next);
+}
+
+__code rotateLeft1_stub(struct Context* context) {
+    struct EntryTree* 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 EntryTree* eTree) {
+    struct Stack* nodeStack = eTree->nodeStack;
+    goto nodeStack->get(rotateRight1);
+}
+
+__code rotateRight_stub(struct Context* context) {
+    struct EntryTree* traverse = context->data[D_RotateTree]->RotateTree.traverse;
+    goto rotateLeft(context, traverse);
+}
+
+__code rotateRight1(struct Node* node, struct EntryTree* 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 EntryTree* 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 EntryTree* eTree, struct Stack* nodeStack, __code next(...)) {
+    eTree->current = 0;
+    nodeStack->stack = (union Data*)eTree->nodeStack;
+    nodeStack->next = next;
+    goto meta(context, eTree->nodeStack->clear);
+}
+
+__code getEntryTree(struct EntryTree* eTree, struct Node* node, __code next(...)) {
+    if (eTree->root) {
+        eTree->current = eTree->root;
+
+        goto search(node);
+    }
+
+    goto next(...);
+}
+
+__code search(struct EntryTree* eTree, struct Node* node, __code next(...)) {
+    // compare(context, traverse, traverse->current->key, node->key);
+    eTree->result = compare(eTree->current, node);
+    if (eTree->result == EQ) {
+        *node = *eTree->current;
+        Gearef(context, ETree)->node = node;
+        goto next(node, ...);
+        // goto meta(context, next);
+    } else if (eTree->result == GT) {
+        eTree->current = eTree->current->right;
+    } else {
+        eTree->current = eTree->current->left;
+    }
+        
+    if (eTree->current) {
+        goto meta(context, C_search);
+    }
+
+    goto next(...);
+}
+
+
+__code removeEntryTree(struct EntryTree* eTree, struct Node* node, __code next(...)) {
+    struct Node* newNode = &ALLOCATE(context, Node)->Node;
+    struct Node* root = eTree->root;
+    printTree((union Data*)(eTree->root));
+    eTree->newNode = newNode;
+    eTree->root = newNode; // this should done at stackClear
+    eTree->parent = NULL;
+    if (root) {
+        eTree->current = root;
+        eTree->result = compare(eTree->current, node);
+        eTree->findNodeNext = C_replaceNodeForDelete2;
+        goto findNode(eTree);
+    }
+    goto next(...);
+}
+
+
+
+__code delete2(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 deleteCase1(current);
+    }
+
+    goto delete3(eTree, current);
+}
+
+
+
+__code delete3(struct EntryTree* eTree, struct Node* current, __code next(...)) {
+    struct Node* tmp = current->right == NULL ? current->left : current->right;
+    struct Stack* nodeStack = eTree->nodeStack;
+
+    if (eTree->parent) {
+        if (current == eTree->parent->left)
+            eTree->parent->left = tmp;
+        else
+            eTree->parent->right = tmp;
+    } else {
+        eTree->root = tmp;
+    }
+
+
+    if (eTree->parent == NULL && tmp) {
+        tmp->color = Black;
+    }
+
+    current == eTree->parent->left ? (eTree->parent->left = NULL) : (eTree->parent->right = NULL);
+
+    Gearef(context, Stack)->stack = (union Data*) nodeStack;
+    Gearef(context, Stack)->next = next;
+    goto meta(context, nodeStack->pop);
+
+//    gato nodeStack->pop(next);
+}
+
+
+
+__code replaceNodeForDelete2(struct EntryTree* eTree, struct Node* newNode) {
+    if (eTree->current->left && eTree->current->right) {
+        eTree->parent = newNode;
+        eTree->current = newNode->left;
+        newNode->left = context->heap;
+
+
+        eTree->parent = newNode;
+        
+        goto findMax1(eTree,oldNode, newNode);
+    }
+
+    goto delete2(current);
+}
+
+
+__code findMax1(struct EntryTree* eTree, struct Node* oldNode, struct Node* newNode) {
+    *newNode = *oldNode;
+
+    if (newNode->right) {
+        goto findMax2(eTree, oldNode, newNode);
+    }
+    
+    eTree->current = newNode;
+
+    goto delete2(current);
+}
+
+
+    
+
+__code findMax2(struct EntryTree* eTree, struct Node* oldNode, struct Node* newNode) {
+    *newNode = *oldNode;
+
+    if (newNode->right->right) {
+        eTree->current = newNode->right;
+        newNode->right = context->heap;
+
+        eTree->parent = newNode;
+        
+        goto findMax2(eTree, oldNode, newNode);
+    }
+
+    eTree->current = newNode;
+    
+    goto delete2(eTree,current);
+}
+    
+
+__code deleteCase1(struct EntryTree* eTree, struct Node* current) {
+    if (eTree->parent) {
+        goto deleteCase2(eTree,current);
+    }
+
+    goto delete3(eTree, current);
+}
+
+
+
+__code deleteCase2(struct EntryTree* eTree, struct Node* current, struct RotateTree* rotateTree) {
+    struct Node* sibling = current == eTree->parent->left ? eTree->parent->right : eTree->parent->left;
+    struct Stack* nodeStack = eTree->nodeStack;
+    
+    if ((sibling == NULL ? Black : sibling->color) == Red) {
+        eTree->parent->color = Red;
+        sibling->color = Black;
+
+        current == eTree->parent->left ? (eTree->parent->left = context->heap) : (eTree->parent->right = context->heap);
+
+        struct Node* node = sibling;
+        
+        eTree->current = eTree->parent;
+
+        rotateTree->traverse = eTree;
+        rotateTree->next = C_deleteCase3;
+
+        if (current == eTree->parent->left) {
+            goto nodeStack->push((union Data*)node,rotateLeft);
+        } else {
+            goto nodeStack->push((union Data*)node,rotateRight);
+        }
+
+        goto deleteCase3(eTree,current);
+    }
+}
+
+
+
+__code deleteCase3(struct EntryTree* eTree, struct Node* current) {
+    struct Node* sibling = current == eTree->parent->left ? eTree->parent->right : eTree->parent->left;
+    
+    if (eTree->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;
+
+        eTree->current = eTree->parent;
+        goto deleteCase1(current);
+    }
+
+    goto deleteCase4(current);
+}
+
+
+
+__code deleteCase4(struct EntryTree* eTree,struct Node* current) {
+    struct Node* sibling = current == eTree->parent->left ? eTree->parent->right : eTree->parent->left;
+    
+    if (eTree->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;
+        eTree->parent->color = Black;
+
+        goto delete3(eTree,current);
+    }
+
+    goto deleteCase5(eTree,current);
+}
+
+
+
+__code deleteCase5(struct EntryTree* eTree, struct Node* current, struct RotateTree* rotateTree) {
+    struct Node* sibling = current == eTree->parent->left ? eTree->parent->right : eTree->parent->left;
+    struct Stack* nodeStack = eTree->nodeStack;
+    // sibling->parent = eTree->parent;
+    
+    if (current == eTree->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);
+        sibling == eTree->parent->left ? (eTree->parent->left = context->heap) : (eTree->parent->right = context->heap);
+
+        struct Node* node = new Node();
+        node = sibling->left;
+
+        struct Node* tmp = node;
+        *tmp = *sibling;
+        eTree->parent = current;
+        
+        tmp->left = context->heap;
+/*         struct Node* node = new Node(); */
+/*         node = *sibling->left; */
+        eTree->parent = tmp;
+
+        eTree->current = tmp;
+        
+
+        rotateTree->traverse = eTree;
+        rotateTree->next = C_deleteCase6;
+
+        goto nodeStack->push((union Data*)node,rotateRight);
+    } else if (current == eTree->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 == eTree->parent->left ? (eTree->parent->left = context->heap) : (eTree->parent->right = context->heap);
+
+        struct Node* node = new Node();
+        node = sibling->right;
+
+        struct Node* tmp = node;
+        *tmp = *sibling;
+        // tmp->parent = current;
+
+        tmp->right = context->heap;
+/*         struct Node* node = new Node(); */
+/*         node = *sibling->right; */
+        //node->parent = tmp;
+
+        eTree->current = tmp;
+        
+
+        rotateTree->traverse = eTree;
+        rotateTree->next = C_deleteCase6;
+
+        goto nodeStack->push((union Data*)node,rotateLeft);
+    }
+
+    goto deleteCase6(eTree,current);
+}
+
+
+__code deleteCase6(struct EntryTree* eTree, struct Node* current, struct RotateTree* rotateTree) {
+    struct Node* sibling = current == eTree->parent->left ? eTree->parent->right : eTree->parent->left;
+    struct Stack* nodeStack = eTree->nodeStack;
+    sibling == eTree->parent->left ? (eTree->parent->left = context->heap) : (eTree->parent->right = context->heap);
+
+    struct Node* tmp = sibling;
+    // *tmp = *sibling;
+    eTree->parent = current;
+
+    tmp->color = eTree->parent->color;
+    eTree->parent->color = Black;
+    
+    
+    if (current == eTree->parent->left) {
+        tmp->right->color = Black;
+        eTree->current = eTree->parent;
+
+        rotateTree->traverse = eTree;
+        rotateTree->next = C_delete3;
+
+        goto nodeStack->push((union Data*)tmp,rotateLeft);
+    } else {
+        tmp->left->color = Black;
+        eTree->current = eTree->parent;
+
+        rotateTree->traverse = eTree;
+        rotateTree->next = C_delete3;
+
+        goto nodeStack->push((union Data*)tmp,rotateLeft);
+    }
+}
--- a/src/parallel_execution/SynchronizedQueue.cbc	Thu Dec 23 16:59:01 2021 +0900
+++ b/src/parallel_execution/SynchronizedQueue.cbc	Thu Dec 23 16:59:31 2021 +0900
@@ -14,7 +14,7 @@
     synchronizedQueue->top = new Element(); // allocate a free node
     synchronizedQueue->top->next = NULL;
     synchronizedQueue->last = synchronizedQueue->top;
-    synchronizedQueue->atomic = createAtomicReference(context);
+    synchronizedQueue->atomic = createAtomicReference(context); // not used
     queue->queue = (union Data*)synchronizedQueue;
     queue->take  = C_takeSynchronizedQueue;
     queue->put  = C_putSynchronizedQueue;
--- a/src/parallel_execution/examples/gearsDirectory/GearsDirectoryImpl.cbc	Thu Dec 23 16:59:01 2021 +0900
+++ b/src/parallel_execution/examples/gearsDirectory/GearsDirectoryImpl.cbc	Thu Dec 23 16:59:31 2021 +0900
@@ -2,12 +2,13 @@
 #interface "GearsDirectory.h"
 #interface "Stack.h"
 #interface "FTree.h"
+#interface "ETree.h"
 #interface "Integer.h"
 #impl "GearsDirectory.h" as "GearsDirectoryImpl.h"
 
 // ----
 // typedef struct GearsDirectoryImpl <> impl GearsDirectory {
-//   struct FTree* currentDirectory;
+//   struct ETree* currentDirectory;
 //   struct Stack* directoryStack;
 // } GearsDirectoryImpl;
 // ----
@@ -17,8 +18,10 @@
     struct GearsDirectoryImpl* gears_directory_impl = new GearsDirectoryImpl();
     gearsDirectory->gearsDirectory = (union Data*)gears_directory_impl;
 
-    struct FTree* firstTree = createFileSystemTree(context, NULL);
-    gears_directory_impl->currentDirectory = firstTree;
+    struct ETree* firstDirectory = createEntryTree(context, NULL);
+    struct FTree* iNodeTree = createFileSystemTree(context, NULL);    
+    gears_directory_impl->currentDirectory = firstDirectory;
+    gears_directory_impl->iNodeTree = iNodeTree;
     gears_directory_impl->directoryStack = createSingleLinkedStack(context);
     gearsDirectory->mkdir = C_mkdirGearsDirectoryImpl;
     gearsDirectory->cd2Child = C_cd2ChildGearsDirectoryImpl;
@@ -27,18 +30,18 @@
 }
 
 __code mkdir(struct GearsDirectoryImpl* gearsDirectory, struct Integer* name, __code next(...)) {
-    struct FTree* newDirectory = createFileSystemTree(context, gearsDirectory->currentDirectory);
+    struct ETree* newDirectory = createEntryTree(context, gearsDirectory->currentDirectory);
     Node* node = new Node();
     node->value = newDirectory;
     node->key = name->value;
-    struct FTree* cDirectory = new FTree();
+    struct ETree* cDirectory = new ETree();
     cDirectory = gearsDirectory->currentDirectory;
     goto cDirectory->put(node, next(...));
 }
 
 __code cd2Child(struct GearsDirectoryImpl* gearsDirectory, struct Integer* name, __code next(...)) {
     // 現在のtreeからnode->keyがnameと一致するものをsearch
-    struct FTree* cDirectory = new FTree();
+    struct ETree* cDirectory = new ETree();
     cDirectory = gearsDirectory->currentDirectory;
     struct Node* node = new Node();
     node->key = name->value;
@@ -47,9 +50,9 @@
 
 __code cd2Child2(struct GearsDirectoryImpl* gearsDirectory, struct Node* node0, __code next(...)) {
     // treeを作る
-    // struct FTree* tree = new FileSystemTree();
+    // struct ETree* tree = new FileSystemTree();
     // currentDirectoryを作ったtreeに変更する
-    // struct FTree* parentDirectory = gearsDirectory->currentDirectory;
+    // struct ETree* parentDirectory = gearsDirectory->currentDirectory;
     // gearsDirectory->currentDirectory = tree;
     // current treeをstackにpushする
     // struct Stack* ds = gearsDirectory->directoryStack;
@@ -63,7 +66,7 @@
 __code cd2Child2_stub(struct Context* context) {
 	GearsDirectoryImpl* gearsDirectory = (GearsDirectoryImpl*)GearImpl(context, GearsDirectory, gearsDirectory);
 	enum Code next = Gearef(context, GearsDirectory)->next;
-    Node* node0 = Gearef(context, FTree)->node;
+    Node* node0 = Gearef(context, ETree)->node;
 	goto cd2Child2(context, gearsDirectory, node0, next);
 }
 
--- a/src/parallel_execution/examples/gearsDirectory/GearsDirectoryImpl.h	Thu Dec 23 16:59:01 2021 +0900
+++ b/src/parallel_execution/examples/gearsDirectory/GearsDirectoryImpl.h	Thu Dec 23 16:59:31 2021 +0900
@@ -1,4 +1,5 @@
 typedef struct GearsDirectoryImpl <> impl GearsDirectory {
-  struct FTree* currentDirectory;
+  struct ETree* currentDirectory;
+  struct FTree* iNodeTree;
   struct Stack* directoryStack;
 } GearsDirectoryImpl;
\ No newline at end of file
--- a/src/parallel_execution/lib/Gears/Template/Context.pm	Thu Dec 23 16:59:01 2021 +0900
+++ b/src/parallel_execution/lib/Gears/Template/Context.pm	Thu Dec 23 16:59:31 2021 +0900
@@ -46,6 +46,7 @@
     context->data[D_##dseg] = context->heap; context->heap += sizeof(t); (t *)context->data[D_##dseg]; })
 
 #define ALLOCATE(context, t) ({ \
+    context->heap =  __builtin_align_up(context->heap + sizeof(Meta) , sizeof(void *)) - sizeof(Meta); \
     Meta* meta = (Meta*)context->heap;\
     context->heap += sizeof(Meta);\
     union Data* data = context->heap; \
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/parallel_execution/plautogen/impl/EntryTree.h	Thu Dec 23 16:59:31 2021 +0900
@@ -0,0 +1,11 @@
+typedef struct EntryTree <> impl ETree {
+  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;
+  __code findNodeNext(...);
+  int result;
+} EntryTree;
--- a/src/parallel_execution/test/rbTree_test.cbc	Thu Dec 23 16:59:01 2021 +0900
+++ b/src/parallel_execution/test/rbTree_test.cbc	Thu Dec 23 16:59:31 2021 +0900
@@ -72,8 +72,8 @@
   Node* node = new Node();
   node->value = (union Data*)new Integer();
   ((Integer*)node->value)->value = 0;
-  node->key = 7;
-  goto tree->get(rbTreeTest6);
+  node->key = 10;
+  goto tree->put(exit_code);
 }
 
 __code rbTreeTest5_stub(struct Context* context) {
@@ -81,21 +81,6 @@
   goto rbTreeTest5(context,tree);
 }
 
-
-__code rbTreeTest6(struct Tree* tree) {
-  printf("test6\n");
-  Node* node = new Node();
-  node->value = (union Data*)new Integer();
-  ((Integer*)node->value)->value = 9;
-  node->key = 9;
-  goto tree->put(node,exit_code);
-}
-
-__code rbTreeTest6_stub(struct Context* context) {
-  Tree* tree = (struct Tree*)Gearef(context, Tree)->tree;
-  goto rbTreeTest6(context,tree);
-}
-
 int main(int argc, char const* argv[]) {
   printf("test_main\n");
   goto rbTreeTest1();
--- a/src/parallel_execution/tmp_tool/_orig_context.h	Thu Dec 23 16:59:01 2021 +0900
+++ b/src/parallel_execution/tmp_tool/_orig_context.h	Thu Dec 23 16:59:31 2021 +0900
@@ -32,6 +32,7 @@
 
 #define ALLOCATE(context, t) ({ \
     Meta* meta = (Meta*)context->heap;\
+    context->heap =  __builtin_align_up(context->heap + sizeof(Meta) , 64) - sizeof(Meta); \
     context->heap += sizeof(Meta);\
     union Data* data = context->heap; \
     context->heap += sizeof(t); \