Mercurial > hg > Gears > Gears
view src/parallel_execution/EntryTree.cbc @ 1031:2caac93dee00
try to compile each app independentry. move context.h to c-twice/context.h
author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
---|---|
date | Tue, 24 Oct 2023 12:15:07 +0900 |
parents | 088a7d2b203d |
children |
line wrap: on
line source
#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); } }