Gears/GearsAgda: src/parallel_execution/rb

annotate src/parallel_execution/rb_tree.c @ 132:7c309e1aea73

Code Gears stack api

author	one
date	Thu, 27 Oct 2016 18:54:11 +0900
parents	a4507906938c
children	568730b1239e

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

Mercurial > hg > Gears > GearsAgda

annotate src/parallel_execution/rb_tree.c @ 132:7c309e1aea73