GearsTemplate: src/parallel_execution/rb

annotate src/parallel_execution/rb_tree.c @ 130:2bb5e4f0fd35

Stackinterface

author	ikkun
date	Mon, 10 Oct 2016 20:19:26 +0900
parents	fe1fbfec7d01
children	a4507906938c

rev	line source
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	1 #include <stdio.h>
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	2
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	3 #include "context.h"
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	4 #include "origin_cs.h"
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	5
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	6 extern void allocator(struct Context* context);
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	7 extern void compare(struct Context* context, struct Traverse* traverse, int key1, int key2);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	8
126 c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	9 void printTree1(union Data* data) {
c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	10 struct Node* node = (struct Node*)data;
c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	11 if (node == NULL) {
c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	12 printf("NULL");
c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	13 } else {
c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	14 printf("key = %d (", node->key);
c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	15 printTree1((union Data*)node->right);
c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	16 printf("), (");
c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	17 printTree1((union Data*)node->left);
c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	18 printf(")");
c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	19 }
c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	20 }
c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	21
c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	22 void printTree(union Data* data) {
c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	23 printTree1(data);
c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	24 printf("\n");
c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	25 }
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	26
130 2bb5e4f0fd35 Stackinterface ikkun parents: 127 diff changeset	27 __code put(struct Context* context, struct Stack* nodeStack, struct Tree* tree, struct Node* node, struct Traverse* traverse, struct Node* root, struct Node* newNode) {
126 c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	28 printTree((union Data*)tree->root);
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	29 traverse->newNode = newNode;
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	30 tree->root = newNode; // this should done at stackClear
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	31 if (root) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	32 traverse->current = root;
117 a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	33 // traverse->result=compare(...)
130 2bb5e4f0fd35 Stackinterface ikkun parents: 127 diff changeset	34 traverse->result = traverse->compare(traverse->current, node);
2bb5e4f0fd35 Stackinterface ikkun parents: 127 diff changeset	35 nodeStack->stack = traverse->nodeStack;
2bb5e4f0fd35 Stackinterface ikkun parents: 127 diff changeset	36 nodeStack->data = (union Data*)newNode;
2bb5e4f0fd35 Stackinterface ikkun parents: 127 diff changeset	37 nodeStack->next = Replace1;
2bb5e4f0fd35 Stackinterface ikkun parents: 127 diff changeset	38 goto meta(context, nodeStack->push);
2bb5e4f0fd35 Stackinterface ikkun parents: 127 diff changeset	39 // goto traverse->nodeStack->push(newNode, replaceNode1, traverse, node);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	40 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	41
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	42 goto meta(context, Insert);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	43 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	44
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	45 __code put_stub(struct Context* context) {
121 f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	46 struct Allocate* allocate = &context->data[Allocate]->allocate;
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	47 allocate->size = sizeof(struct Node);
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	48 allocator(context);
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	49
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	50 goto put(context,
130 2bb5e4f0fd35 Stackinterface ikkun parents: 127 diff changeset	51 &context->data[Stack]->stack,
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	52 &context->data[Tree]->tree,
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	53 &context->data[Node]->node,
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	54 &context->data[Traverse]->traverse,
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	55 context->data[Tree]->tree.root,
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	56 &context->data[context->dataNum]->node
36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	57 );
121 f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	58 }
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	59
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	60 __code replaceNode(struct Context* context, struct Traverse* traverse, struct Node* oldNode, struct Node* newNode, struct Element* element) {
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	61 newNode = oldNode;
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	62 element->next = traverse->nodeStack;
36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	63 element->data = (union Data* )newNode;
36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	64 traverse->nodeStack = element;
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	65 // goto replaceNode1(struct Traverse* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, +struct Node* newnewNode, int result)
121 f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	66 goto meta(context, Replace1);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	67 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	68
121 f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	69 __code replaceNode_stub(struct Context* context) {
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	70 struct Allocate* allocate = &context->data[Allocate]->allocate;
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	71 allocate->size = sizeof(struct Element);
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	72 allocator(context);
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	73 struct Element* element = &context->data[context->dataNum]->element;
121 f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	74 goto replaceNode(context,
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	75 &context->data[Traverse]->traverse,
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	76 context->data[Traverse]->traverse.current,
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	77 context->data[Traverse]->traverse.newNode,
121 f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	78 element);
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	79 }
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	80
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	81 __code replaceNode1(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* oldNode, struct Node* newNode, struct Node* newnewNode, int result) {
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	82 if (result == EQ) {
121 f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	83 newNode->value = node->value;
117 a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	84 // go to stack clear
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	85 goto meta(context, context->next);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	86 } else if (result == GT) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	87 traverse->current = oldNode->right;
121 f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	88 newNode->right = newnewNode;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	89 } else {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	90 traverse->current = oldNode->left;
121 f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	91 newNode->left = newnewNode;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	92 }
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	93 traverse->newNode = newnewNode;
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	94 if (traverse->current) {
121 f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	95 compare(context, traverse, traverse->current->key, node->key);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	96 goto meta(context, Replace);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	97 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	98
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	99 goto meta(context, Insert);
121 f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	100
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	101 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	102
121 f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	103 __code replaceNode1_stub(struct Context* context) {
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	104 struct Allocate* allocate = &context->data[Allocate]->allocate;
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	105 allocate->size = sizeof(struct Node);
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	106 allocator(context);
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	107 struct Node* newnewNode = &context->data[context->dataNum]->node;
f708b271a7b8 node stack rewrite ikkun parents: 120 diff changeset	108 goto replaceNode1(context,
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	109 &context->data[Traverse]->traverse,
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	110 &context->data[Node]->node,
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	111 context->data[Traverse]->traverse.current,
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	112 &context->data[Traverse]->traverse.nodeStack->data->node,
36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	113 newnewNode,
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	114 context->data[Traverse]->traverse.result);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	115 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	116
127 fe1fbfec7d01 stack clear kono parents: 126 diff changeset	117 __code insertNode(struct Context* context, struct Traverse* traverse, struct Node* node, struct Node* newNode) {
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	118 newNode = node;
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	119 newNode->color = Red;
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	120 traverse->current = newNode;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	121 goto meta(context, InsertCase1);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	122 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	123
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	124 __code insertNode_stub(struct Context* context) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	125 goto insertNode(context,
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	126 &context->data[Traverse]->traverse,
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	127 &context->data[Node]->node,
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	128 context->data[Traverse]->traverse.newNode);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	129 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	130
127 fe1fbfec7d01 stack clear kono parents: 126 diff changeset	131 __code insertCase1(struct Context* context, struct Tree* tree,struct Element* nodeStack) {
125 9ae7ce6c83f5 Fix segmentation falt innparusu parents: 124 diff changeset	132 if (nodeStack!=NULL) {
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	133 goto meta(context, InsertCase2);
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	134 }
127 fe1fbfec7d01 stack clear kono parents: 126 diff changeset	135 tree->root->color = Black;
119 b224aa7b80a0 remove code stack, stack clear is directly called ikkun parents: 118 diff changeset	136 goto meta(context, StackClear);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	137 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	138
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	139 __code insert1_stub(struct Context* context) {
127 fe1fbfec7d01 stack clear kono parents: 126 diff changeset	140 goto insertCase1(context,
fe1fbfec7d01 stack clear kono parents: 126 diff changeset	141 &context->data[Tree]->tree,
fe1fbfec7d01 stack clear kono parents: 126 diff changeset	142 context->data[Traverse]->traverse.nodeStack);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	143 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	144
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	145 __code insertCase2(struct Context* context, struct Node* parent) {
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	146 if (parent->color == Black) {
119 b224aa7b80a0 remove code stack, stack clear is directly called ikkun parents: 118 diff changeset	147 goto meta(context, StackClear);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	148 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	149 goto meta(context, InsertCase3);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	150 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	151
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	152 __code insert2_stub(struct Context* context) {
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	153 goto insertCase2(context, (struct Node*)context->data[Traverse]->traverse.nodeStack->data);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	154 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	155
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	156 __code insertCase3(struct Context* context, struct Traverse* traverse, struct Node* parent, struct Node* grandparent) {
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	157 struct Node* uncle;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	158
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	159 if (grandparent->left == parent)
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	160 uncle = grandparent->right;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	161 else
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	162 uncle = grandparent->left;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	163
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	164 if (uncle && (uncle->color == Red)) {
117 a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	165 // do insertcase1 on grandparent, stack must be pop by two
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	166 parent->color = Black;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	167 uncle->color = Black;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	168 grandparent->color = Red;
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	169 traverse->current = grandparent;
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	170 goto meta(context, InsertCase31);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	171 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	172 goto meta(context, InsertCase4);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	173 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	174
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	175 __code insert3_stub(struct Context* context) {
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	176 goto insertCase3(context, &context->data[Traverse]->traverse,
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	177 (struct Node*)context->data[Traverse]->traverse.nodeStack->data,
36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	178 (struct Node*)context->data[Traverse]->traverse.nodeStack->next->data
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	179 );
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	180 }
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	181 __code insertCase31(struct Context* context, struct Traverse* traverse) {
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	182 traverse->nodeStack = traverse->nodeStack->next->next;
120 2493f4226ca6 remove code stack, add stackPop2 ikkun parents: 119 diff changeset	183 goto meta(context, InsertCase1);
2493f4226ca6 remove code stack, add stackPop2 ikkun parents: 119 diff changeset	184 }
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	185 __code insert31_stub(struct Context* context) {
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	186 goto insertCase31(context, &context->data[Traverse]->traverse);
120 2493f4226ca6 remove code stack, add stackPop2 ikkun parents: 119 diff changeset	187 }
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	188
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	189 __code insertCase4(struct Context* context, struct Traverse* traverse, struct Node* current,struct Node* parent, struct Node* grandparent) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	190 traverse->current = parent;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	191
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	192 if ((current == parent->right) && (parent == grandparent->left)) {
119 b224aa7b80a0 remove code stack, stack clear is directly called ikkun parents: 118 diff changeset	193 traverse->rotateNext = InsertCase4_1;
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	194 goto meta(context, InsertCase4_01);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	195 } else if ((current == parent->left) && (parent == grandparent->right)) {
119 b224aa7b80a0 remove code stack, stack clear is directly called ikkun parents: 118 diff changeset	196 traverse->rotateNext = InsertCase4_2;
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	197 goto meta(context, InsertCase4_02);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	198 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	199
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	200 traverse->current = current;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	201 goto meta(context, InsertCase5);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	202 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	203
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	204 __code insert4_stub(struct Context* context) {
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	205 goto insertCase4(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current,
36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	206 &context->data[Traverse]->traverse.nodeStack->data->node,
36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	207 &context->data[Traverse]->traverse.nodeStack->next->data->node);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	208 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	209
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	210 __code insertCase4_01(struct Context* context, struct Traverse* traverse) {
126 c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	211 traverse->nodeStack = traverse->nodeStack -> next;
c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	212 traverse->rotateNext = InsertCase5;
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	213 goto meta(context, RotateL);
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	214 }
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	215
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	216 __code insert4_01_stub(struct Context* context) {
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	217 goto insertCase4_01(context, &context->data[Traverse]->traverse);
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	218 }
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	219 __code insertCase4_1(struct Context* context, struct Traverse* traverse) {
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	220 traverse->current = traverse->current->left;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	221 goto meta(context, InsertCase5);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	222 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	223
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	224 __code insert4_1_stub(struct Context* context) {
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	225 struct Allocate* allocate = &context->data[Allocate]->allocate;
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	226 allocate->size = sizeof(struct Element);
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	227 allocator(context);
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	228 struct Element* element = &context->data[context->dataNum]->element;
36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	229 struct Traverse* traverse = &context->data[Traverse]->traverse;
36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	230 element->data = (union Data*)traverse->current;
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	231 goto insertCase4_1(context, &context->data[Traverse]->traverse);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	232 }
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	233 __code insertCase4_02(struct Context* context, struct Traverse* traverse) {
126 c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	234 traverse->nodeStack = traverse->nodeStack -> next;
c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	235 traverse->rotateNext = InsertCase5;
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	236 goto meta(context, RotateR);
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	237 }
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	238
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	239 __code insert4_02_stub(struct Context* context) {
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	240 goto insertCase4_02(context, &context->data[Traverse]->traverse);
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	241 }
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	242
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	243 __code insertCase4_2(struct Context* context, struct Traverse* traverse) {
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	244 traverse->current = traverse->current->right;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	245 goto meta(context, InsertCase5);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	246 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	247
123 933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	248 __code insert4_2_stub(struct Context* context) {
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	249 struct Allocate* allocate = &context->data[Allocate]->allocate;
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	250 allocate->size = sizeof(struct Element);
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	251 allocator(context);
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	252 struct Element* element = &context->data[context->dataNum]->element;
36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	253 struct Traverse* traverse = &context->data[Traverse]->traverse;
36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	254 element->data = (union Data*)traverse->current;
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	255 goto insertCase4_2(context, &context->data[Traverse]->traverse);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	256 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	257
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	258 __code insertCase5(struct Context* context, struct Traverse* traverse, struct Node* current, struct Node* parent, struct Node* grandparent) {
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	259 parent->color = Black;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	260 grandparent->color = Red;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	261
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	262 traverse->current = grandparent;
119 b224aa7b80a0 remove code stack, stack clear is directly called ikkun parents: 118 diff changeset	263 traverse->rotateNext = StackClear;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	264 if ((current == parent->left) && (parent == grandparent->left))
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	265 goto meta(context, RotateR);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	266 else
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	267 goto meta(context, RotateL);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	268 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	269
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	270 __code insert5_stub(struct Context* context) {
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	271 struct Traverse* traverse = &context->data[Traverse]->traverse;
122 73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	272 struct Node* parent = (struct Node*)traverse->nodeStack->data;
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	273 struct Node* grandparent = (struct Node*)traverse->nodeStack->next->data;
73a679a85c04 node stack rewrite ikkun parents: 121 diff changeset	274 traverse->nodeStack = traverse->nodeStack->next->next;
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	275 goto insertCase5(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current, parent, grandparent);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	276 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	277
117 a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	278 // put rotateLeft's continuation as argument
126 c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	279 __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) {
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	280 struct Node* tmp = node->right;
123 933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	281
933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	282 if (parent) {
933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	283 if (node == parent->left)
933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	284 parent->left = tmp;
933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	285 else
933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	286 parent->right = tmp;
933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	287 } else {
933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	288 tree->root = tmp;
933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	289 }
117 a574ba0da60f add comment rb_tree ikkun parents: 103 diff changeset	290
123 933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	291 node->right = tmp->left;
933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	292 tmp->left = node;
933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	293 traverse->current = tmp;
933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	294
933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	295 goto meta(context, traverse->rotateNext);
933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	296 }
933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	297
933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	298 __code rotateLeft_stub(struct Context* context) {
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	299 struct Traverse* traverse = &context->data[Traverse]->traverse;
123 933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	300 struct Node* parent = (traverse->nodeStack)?(struct Node*)traverse->nodeStack->data:NULL;
933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	301 goto rotateLeft(context,
125 9ae7ce6c83f5 Fix segmentation falt innparusu parents: 124 diff changeset	302 context->data[Traverse]->traverse.current,
123 933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	303 &context->data[Tree]->tree,
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	304 &context->data[Traverse]->traverse,
126 c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	305 parent);
123 933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	306 }
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	307
126 c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	308 __code rotateRight(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent) {
123 933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	309 struct Node* tmp = node->left;
933c80f48d06 node stack rewrite ikkun parents: 122 diff changeset	310
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	311 if (parent) {
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	312 if (node == parent->left)
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	313 parent->left = tmp;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	314 else
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	315 parent->right = tmp;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	316 } else {
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	317 tree->root = tmp;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	318 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	319
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	320 node->left = tmp->right;
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	321 tmp->right = node;
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	322 traverse->current = tmp;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	323
119 b224aa7b80a0 remove code stack, stack clear is directly called ikkun parents: 118 diff changeset	324 goto meta(context, traverse->rotateNext);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	325 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	326
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	327 __code rotateRight_stub(struct Context* context) {
125 9ae7ce6c83f5 Fix segmentation falt innparusu parents: 124 diff changeset	328 struct Traverse* traverse = &context->data[Traverse]->traverse;
9ae7ce6c83f5 Fix segmentation falt innparusu parents: 124 diff changeset	329 struct Node* parent = (traverse->nodeStack)?(struct Node*)traverse->nodeStack->data:NULL;
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	330 goto rotateRight(context,
125 9ae7ce6c83f5 Fix segmentation falt innparusu parents: 124 diff changeset	331 context->data[Traverse]->traverse.current,
124 36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	332 &context->data[Tree]->tree,
36ac17d37be4 Fix compile error but not work one parents: 123 diff changeset	333 &context->data[Traverse]->traverse,
126 c7ac153f86dd Fix rotate cs stack one parents: 125 diff changeset	334 parent);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	335 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	336
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	337 __code stackClear(struct Context* context, stack_ptr node_stack, struct Traverse* traverse) {
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	338 traverse->current = 0;
127 fe1fbfec7d01 stack clear kono parents: 126 diff changeset	339 traverse->nodeStack = NULL;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	340
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	341 goto meta(context, context->next);
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	342 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	343
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	344 __code stackClear_stub(struct Context* context) {
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	345 goto stackClear(context, context->node_stack, &context->data[Traverse]->traverse);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	346 }
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	347
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	348
92 851da1107223 implement twice Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 91 diff changeset	349 __code get(struct Context* context, struct Tree* tree, struct Traverse* traverse) {
851da1107223 implement twice Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 91 diff changeset	350 if (tree->root) {
851da1107223 implement twice Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 91 diff changeset	351 traverse->current = tree->root;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	352
92 851da1107223 implement twice Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 91 diff changeset	353 goto meta(context, Search);
851da1107223 implement twice Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 91 diff changeset	354 }
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	355
119 b224aa7b80a0 remove code stack, stack clear is directly called ikkun parents: 118 diff changeset	356 goto meta(context, context->next);
92 851da1107223 implement twice Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 91 diff changeset	357 }
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	358
92 851da1107223 implement twice Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 91 diff changeset	359 __code get_stub(struct Context* context) {
851da1107223 implement twice Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 91 diff changeset	360 goto get(context, &context->data[Tree]->tree, &context->data[Traverse]->traverse);
851da1107223 implement twice Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 91 diff changeset	361 }
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	362
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	363 __code search(struct Context* context, struct Traverse* traverse, struct Node* node) {
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	364 compare(context, traverse, traverse->current->key, node->key);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	365
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	366 if (traverse->result == EQ) {
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	367 node = traverse->current;
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	368
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	369 goto meta(context, context->next);
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	370 } else if (traverse->result == GT) {
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	371 traverse->current = traverse->current->right;
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	372 } else {
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	373 traverse->current = traverse->current->left;
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	374 }
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	375
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	376 if (traverse->current)
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	377 goto meta(context, Search);
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	378
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	379 goto meta(context, context->next);
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	380 }
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	381
91 1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	382 __code search_stub(struct Context* context) {
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	383 goto search(context, &context->data[Traverse]->traverse, &context->data[Node]->node);
1e074c3878c7 modify tree Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: 87 diff changeset	384 }
86 e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	385
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	386 /* /\* __code delete(struct Context* context, struct Tree* tree) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	387 /* /\* if (tree->root) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	388 /* /\* stack_push(context->code_stack, &context->next); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	389 /* /\* context->next = Delete1; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	390 /* /\* goto meta(context, Get); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	391 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	392
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	393 /* /\* goto meta(context, context->next); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	394 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	395
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	396 /* /\* __code delete_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	397 /* /\* goto delete(context, &context->data[Tree]->tree); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	398 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	399
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	400 /* /\* __code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	401 /* /\* allocate->size = sizeof(struct Node); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	402 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	403
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	404 /* /\* struct Node* root = tree->root; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	405
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	406 /* /\* tree->root = &context->data[context->dataNum]->node; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	407 /* /\* tree->current = root; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	408
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	409 /* /\* compare(context, tree, tree->current->key, context->data[Node]->node.key); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	410
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	411 /* /\* goto meta(context, Replace_d1); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	412 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	413
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	414 /* /\* __code delete1_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	415 /* /\* goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	416 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	417
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	418 /* /\* __code delete2(struct Context* context, struct Node* current) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	419 /* /\* if (current->color == Black) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	420 /* /\* struct Node* child = current->right == NULL ? current->left : current->right; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	421 /* /\* current->color = child == NULL ? Black : child->color; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	422
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	423 /* /\* goto meta(context, DeleteCase1); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	424 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	425
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	426 /* /\* goto meta(context, Delete3); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	427 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	428
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	429 /* /\* __code delete2_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	430 /* /\* goto delete2(context, context->data[Tree]->tree.current); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	431 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	432
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	433 /* /\* __code delete3(struct Context* context, struct Tree* tree, struct Node* current) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	434 /* /\* struct Node* tmp = current->right == NULL ? current->left : current->right; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	435
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	436 /* /\* if (current->parent) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	437 /* /\* if (current == current->parent->left) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	438 /* /\* current->parent->left = tmp; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	439 /* /\* else \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	440 /* /\* current->parent->right = tmp; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	441 /* /\* } else { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	442 /* /\* tree->root = tmp; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	443 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	444
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	445 /* /\* if (tmp) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	446 /* /\* tmp->parent = current->parent; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	447
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	448 /* /\* if (current->parent == NULL && tmp) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	449 /* /\* tmp->color = Black; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	450
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	451 /* /\* current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	452
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	453 /* /\* stack_pop(context->code_stack, &context->next); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	454 /* /\* goto meta(context, context->next); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	455 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	456
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	457 /* /\* __code delete3_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	458 /* /\* goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	459 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	460
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	461 /* /\* __code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	462 /* /\* newNode = oldNode; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	463
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	464 /* /\* if (result == EQ) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	465 /* /\* goto meta(context, Replace_d2); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	466 /* /\* else if (result == GT) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	467 /* /\* tree->current = newNode->right; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	468 /* /\* else \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	469 /* /\* tree->current = newNode->left; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	470
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	471 /* /\* tree->current->parent = newNode; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	472
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	473 /* /\* if (tree->current->left == NULL && tree->current->right == NULL) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	474 /* /\* goto meta(context, Delete2); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	475
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	476 /* /\* if (result == GT) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	477 /* /\* newNode->right = context->heap; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	478 /* /\* else if (result == LT) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	479 /* /\* newNode->left = context->heap; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	480
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	481 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	482
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	483 /* /\* compare(context, tree, tree->current->key, context->data[Node]->node.key); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	484
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	485 /* /\* goto meta(context, Replace_d1); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	486 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	487
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	488 /* /\* __code replaceNodeForDelete1_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	489 /* /\* goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	490 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	491
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	492 /* /\* __code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	493 /* /\* if (tree->current->left && tree->current->right) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	494 /* /\* newNode->left->parent = newNode; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	495 /* /\* tree->current = newNode->left; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	496 /* /\* newNode->left = context->heap; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	497 /* /\* tree->deleted = newNode; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	498
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	499 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	500 /* /\* tree->current->parent = newNode; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	501
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	502 /* /\* goto meta(context, FindMax1); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	503 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	504
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	505 /* /\* goto meta(context, Delete2); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	506 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	507
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	508 /* /\* __code replaceNodeForDelete2_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	509 /* /\* goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	510 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	511
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	512 /* /\* __code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	513 /* /\* newNode = oldNode; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	514
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	515 /* /\* if (newNode->right) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	516 /* /\* goto meta(context, FindMax2); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	517
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	518 /* /\* tree->deleted->key = newNode->key; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	519 /* /\* tree->deleted->value = newNode->value; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	520
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	521 /* /\* tree->current = newNode; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	522
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	523 /* /\* goto meta(context, Delete2); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	524 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	525
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	526 /* /\* __code findMax1_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	527 /* /\* goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	528 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	529
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	530
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	531 /* /\* __code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	532 /* /\* newNode = oldNode; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	533
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	534 /* /\* if (newNode->right->right) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	535 /* /\* tree->current = newNode->right; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	536 /* /\* newNode->right = context->heap; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	537
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	538 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	539 /* /\* tree->current->parent = newNode; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	540
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	541 /* /\* goto meta(context, FindMax2); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	542 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	543
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	544 /* /\* tree->deleted->key = newNode->right->key; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	545 /* /\* tree->deleted->value = newNode->right->value; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	546
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	547 /* /\* tree->current = newNode; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	548
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	549 /* /\* goto meta(context, Delete2); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	550 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	551
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	552 /* /\* __code findMax2_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	553 /* /\* goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	554 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	555
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	556 /* /\* __code deleteCase1(struct Context* context, struct Node* current) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	557 /* /\* if (current->parent) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	558 /* /\* goto meta(context, DeleteCase2); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	559
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	560 /* /\* goto meta(context, Delete3); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	561 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	562
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	563 /* /\* __code deleteCase1_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	564 /* /\* goto deleteCase1(context, context->data[Tree]->tree.current); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	565 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	566
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	567 /* /\* __code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	568 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	569
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	570 /* /\* if ((sibling == NULL ? Black : sibling->color) == Red) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	571 /* /\* current->parent->color = Red; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	572 /* /\* sibling->color = Black; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	573
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	574 /* /\* current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	575 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	576 /* /\* context->data[context->dataNum]->node = sibling; \/ */
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	577
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	578 /* /\* tree->current = current->parent; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	579
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	580 /* /\* context->next = DeleteCase3; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	581 /* /\* stack_push(context->code_stack, &context->next); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	582
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	583 /* /\* if (current == current->parent->left) \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	584 /* /\* goto meta(context, RotateL); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	585 /* /\* else \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	586 /* /\* goto meta(context, RotateR); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	587 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	588
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	589 /* /\* goto meta(context, DeleteCase3); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	590 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	591
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	592 /* /\* __code deleteCase2_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	593 /* /\* goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	594 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	595
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	596 /* /\* __code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	597 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	598
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	599 /* /\* if (current->parent->color == Black && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	600 /* /\* (sibling == NULL ? Black : sibling->color) == Black && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	601 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	602 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	603 /* /\* sibling->color = Red; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	604
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	605 /* /\* tree->current = current->parent; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	606 /* /\* goto meta(context, DeleteCase1); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	607 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	608
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	609 /* /\* goto meta(context, DeleteCase4); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	610 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	611
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	612 /* /\* __code deleteCase3_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	613 /* /\* goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	614 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	615
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	616 /* /\* __code deleteCase4(struct Context* context, struct Node* current) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	617 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	618
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	619 /* /\* if (current->parent->color == Red && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	620 /* /\* (sibling == NULL ? Black : sibling->color) == Black && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	621 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	622 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	623 /* /\* sibling->color = Red; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	624 /* /\* current->parent->color = Black; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	625
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	626 /* /\* goto meta(context, Delete3); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	627 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	628
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	629 /* /\* goto meta(context, DeleteCase5); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	630 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	631
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	632 /* /\* __code deleteCase4_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	633 /* /\* goto deleteCase4(context, context->data[Tree]->tree.current); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	634 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	635
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	636 /* /\* __code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	637 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	638 /* /\* sibling->parent = current->parent; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	639
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	640 /* /\* if (current == current->parent->left && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	641 /* /\* (sibling == NULL ? Black : sibling->color) == Black && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	642 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Red && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	643 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	644 /* /\* sibling->color = Red; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	645 /* /\* sibling->left->color = Black; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	646
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	647 /* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	648 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	649 /* /\* struct Node* tmp = &context->data[context->dataNum]->node; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	650 /* /\* tmp = sibling; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	651 /* /\* tmp->parent = current; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	652
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	653 /* /\* tmp->left = context->heap; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	654 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	655 /* /\* context->data[context->dataNum]->node = sibling->left; \/ */
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	656 /* /\* context->data[context->dataNum]->node.parent = tmp; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	657
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	658 /* /\* tree->current = tmp; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	659
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	660 /* /\* context->next = DeleteCase6; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	661 /* /\* stack_push(context->code_stack, &context->next); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	662
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	663 /* /\* goto meta(context, RotateR); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	664 /* /\* } else if (current == current->parent->right && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	665 /* /\* (sibling == NULL ? Black : sibling->color) == Black && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	666 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	667 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Red) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	668 /* /\* sibling->color = Red; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	669 /* /\* sibling->right->color = Black; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	670
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	671 /* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	672 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	673 /* /\* struct Node* tmp = &context->data[context->dataNum]->node; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	674 /* /\* tmp = sibling; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	675 /* /\* tmp->parent = current; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	676
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	677 /* /\* tmp->right = context->heap; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	678 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	679 /* /\* context->data[context->dataNum]->node = sibling->right; \/ */
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	680 /* /\* context->data[context->dataNum]->node.parent = tmp; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	681
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	682 /* /\* tree->current = tmp; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	683
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	684 /* /\* context->next = DeleteCase6; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	685 /* /\* stack_push(context->code_stack, &context->next); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	686 /* /\* goto meta(context, RotateL); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	687 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	688
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	689 /* /\* goto meta(context, DeleteCase6); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	690 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	691
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	692 /* /\* __code deleteCase5_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	693 /* /\* goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	694 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	695
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	696 /* /\* __code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	697 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	698
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	699 /* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	700 /* /\* allocator(context); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	701 /* /\* struct Node* tmp = &context->data[context->dataNum]->node; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	702 /* /\* tmp = sibling; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	703 /* /\* tmp->parent = current; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	704
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	705 /* /\* tmp->color = current->parent->color; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	706 /* /\* current->parent->color = Black; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	707
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	708 /* /\* context->next = Delete3; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	709 /* /\* stack_push(context->code_stack, &context->next); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	710
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	711 /* /\* if (current == current->parent->left) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	712 /* /\* tmp->right->color = Black; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	713 /* /\* tree->current = current->parent; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	714
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	715 /* /\* goto meta(context, RotateL); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	716 /* /\* } else { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	717 /* /\* tmp->left->color = Black; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	718 /* /\* tree->current = current->parent; \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	719
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	720 /* /\* goto meta(context, RotateR); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	721 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	722 /* /\* } \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	723
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	724 /* /\* __code deleteCase6_stub(struct Context* context) { \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	725 /* /\* goto deleteCase6(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); \/ /
e06e1a9e569e create worker Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp> parents: diff changeset	726 /* /\* } \/ /

Mercurial > hg > GearsTemplate

annotate src/parallel_execution/rb_tree.c @ 130:2bb5e4f0fd35