Mercurial > hg > Gears > GearsAgda

annotate src/parallel_execution/rb_tree.c @ 124:36ac17d37be4

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Fix compile error but not work
author one
date Thu, 29 Sep 2016 16:58:23 +0900
parents 933c80f48d06
children 9ae7ce6c83f5
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
9 extern int num;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
10
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
11 __code put(struct Context* context, struct Tree* tree, struct Node* node, struct Traverse* traverse, struct Node* root, struct Node* newNode) {
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
12 traverse->newNode = newNode;
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
13 tree->root = newNode; // this should done at stackClear
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
14 if (root) {
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
15 traverse->current = root;
117
a574ba0da60f add comment rb_tree
ikkun
parents: 103
diff changeset
16 // traverse->result=compare(...)
121
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
17 compare(context, traverse, traverse->current->key, node->key);
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
18 // goto replaceNode(traverse->current, newNode, traverse->result);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
19 goto meta(context, Replace);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
20 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
21
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
22 goto meta(context, Insert);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
23 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
24
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
25 __code put_stub(struct Context* context) {
121
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
26 struct Allocate* allocate = &context->data[Allocate]->allocate;
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
27 allocate->size = sizeof(struct Node);
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
28 allocator(context);
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
29
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
30 goto put(context,
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
31 &context->data[Tree]->tree,
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
32 &context->data[Node]->node,
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
33 &context->data[Traverse]->traverse,
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
34 context->data[Tree]->tree.root,
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
35 &context->data[context->dataNum]->node
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
36 );
121
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
37 }
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
38
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
39 __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
40 *newNode = *oldNode;
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
41 element->next = traverse->nodeStack;
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
42 element->data = (union Data* )newNode;
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
43 traverse->nodeStack = element;
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
44 // 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
45 goto meta(context, Replace1);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
46 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
47
121
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
48 __code replaceNode_stub(struct Context* context) {
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
49 struct Allocate* allocate = &context->data[Allocate]->allocate;
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
50 allocate->size = sizeof(struct Element);
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
51 allocator(context);
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
52 struct Element* element = &context->data[context->dataNum]->element;
121
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
53 goto replaceNode(context,
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
54 &context->data[Traverse]->traverse,
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
55 context->data[Traverse]->traverse.current,
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
56 context->data[Traverse]->traverse.newNode,
121
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
57 element);
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 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
61 if (result == EQ) {
121
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
62 newNode->value = node->value;
117
a574ba0da60f add comment rb_tree
ikkun
parents: 103
diff changeset
63 // go to stack clear
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
64 goto meta(context, context->next);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
65 } else if (result == GT) {
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
66 traverse->current = oldNode->right;
121
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
67 newNode->right = newnewNode;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
68 } else {
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
69 traverse->current = oldNode->left;
121
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
70 newNode->left = newnewNode;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
71 }
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
72 traverse->newNode = newnewNode;
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
73 if (traverse->current) {
121
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
74 compare(context, traverse, traverse->current->key, node->key);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
75 goto meta(context, Replace);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
76 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
77
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
78 goto meta(context, Insert);
121
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
79
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
80 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
81
121
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
82 __code replaceNode1_stub(struct Context* context) {
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
83 struct Allocate* allocate = &context->data[Allocate]->allocate;
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
84 allocate->size = sizeof(struct Node);
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
85 allocator(context);
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
86 struct Node* newnewNode = &context->data[context->dataNum]->node;
f708b271a7b8 node stack rewrite
ikkun
parents: 120
diff changeset
87 goto replaceNode1(context,
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
88 &context->data[Traverse]->traverse,
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
89 &context->data[Node]->node,
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
90 context->data[Traverse]->traverse.current,
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
91 &context->data[Traverse]->traverse.nodeStack->data->node,
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
92 newnewNode,
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
93 context->data[Traverse]->traverse.result);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
94 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
95
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
96 __code insertNode(struct Context* context, struct Traverse* traverse, struct Tree* tree, struct Node* node, struct Node* newNode) {
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
97 *newNode = *node;
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
98 newNode->color = Red;
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
99 traverse->current = newNode;
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
100 tree->root->color = Black;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
101 goto meta(context, InsertCase1);
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
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
104 __code insertNode_stub(struct Context* context) {
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
105 goto insertNode(context,
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
106 &context->data[Traverse]->traverse,
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
107 &context->data[Tree]->tree,
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
108 &context->data[Node]->node,
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
109 context->data[Traverse]->traverse.newNode);
86
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
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
112 __code insertCase1(struct Context* context, struct Node* parent) {
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
113 if (parent!=NULL) {
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
114 goto meta(context, InsertCase2);
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
115 }
119
b224aa7b80a0 remove code stack, stack clear is directly called
ikkun
parents: 118
diff changeset
116 goto meta(context, StackClear);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
117 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
118
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
119 __code insert1_stub(struct Context* context) {
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
120 goto insertCase1(context, (struct Node*)context->data[Traverse]->traverse.nodeStack->data);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
121 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
122
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
123 __code insertCase2(struct Context* context, struct Node* parent) {
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
124 if (parent->color == Black) {
119
b224aa7b80a0 remove code stack, stack clear is directly called
ikkun
parents: 118
diff changeset
125 goto meta(context, StackClear);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
126 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
127 goto meta(context, InsertCase3);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
128 }
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 __code insert2_stub(struct Context* context) {
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
131 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
132 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
133
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
134 __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
135 struct Node* uncle;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
136
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
137 if (grandparent->left == parent)
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
138 uncle = grandparent->right;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
139 else
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
140 uncle = grandparent->left;
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 if (uncle && (uncle->color == Red)) {
117
a574ba0da60f add comment rb_tree
ikkun
parents: 103
diff changeset
143 // 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
144 parent->color = Black;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
145 uncle->color = Black;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
146 grandparent->color = Red;
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
147 traverse->current = grandparent;
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
148 goto meta(context, InsertCase31);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
149 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
150 goto meta(context, InsertCase4);
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
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
153 __code insert3_stub(struct Context* context) {
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
154 goto insertCase3(context, &context->data[Traverse]->traverse,
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
155 (struct Node*)context->data[Traverse]->traverse.nodeStack->data,
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
156 (struct Node*)context->data[Traverse]->traverse.nodeStack->next->data
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
157 );
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
158 }
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
159 __code insertCase31(struct Context* context, struct Traverse* traverse) {
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
160 traverse->nodeStack = traverse->nodeStack->next->next;
120
2493f4226ca6 remove code stack, add stackPop2
ikkun
parents: 119
diff changeset
161 goto meta(context, InsertCase1);
2493f4226ca6 remove code stack, add stackPop2
ikkun
parents: 119
diff changeset
162 }
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
163 __code insert31_stub(struct Context* context) {
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
164 goto insertCase31(context, &context->data[Traverse]->traverse);
120
2493f4226ca6 remove code stack, add stackPop2
ikkun
parents: 119
diff changeset
165 }
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
166
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
167 __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
168 traverse->current = parent;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
169
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
170 if ((current == parent->right) && (parent == grandparent->left)) {
119
b224aa7b80a0 remove code stack, stack clear is directly called
ikkun
parents: 118
diff changeset
171 traverse->rotateNext = InsertCase4_1;
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
172 goto meta(context, InsertCase4_01);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
173 } else if ((current == parent->left) && (parent == grandparent->right)) {
119
b224aa7b80a0 remove code stack, stack clear is directly called
ikkun
parents: 118
diff changeset
174 traverse->rotateNext = InsertCase4_2;
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
175 goto meta(context, InsertCase4_02);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
176 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
177
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
178 traverse->current = current;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
179 goto meta(context, InsertCase5);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
180 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
181
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
182 __code insert4_stub(struct Context* context) {
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
183 goto insertCase4(context, &context->data[Traverse]->traverse, context->data[Traverse]->traverse.current,
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
184 &context->data[Traverse]->traverse.nodeStack->data->node,
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
185 &context->data[Traverse]->traverse.nodeStack->next->data->node);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
186 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
187
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
188 __code insertCase4_01(struct Context* context, struct Traverse* traverse) {
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
189 context->data[Traverse]->traverse.nodeStack = context->data[Traverse]->traverse.nodeStack -> next;
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
190 goto meta(context, RotateL);
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
191 }
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
192
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
193 __code insert4_01_stub(struct Context* context) {
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
194 goto insertCase4_01(context, &context->data[Traverse]->traverse);
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
195 }
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
196 __code insertCase4_1(struct Context* context, struct Traverse* traverse) {
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
197 traverse->current = traverse->current->left;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
198 goto meta(context, InsertCase5);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
199 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
200
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
201 __code insert4_1_stub(struct Context* context) {
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
202 struct Allocate* allocate = &context->data[Allocate]->allocate;
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
203 allocate->size = sizeof(struct Element);
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
204 allocator(context);
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
205 struct Element* element = &context->data[context->dataNum]->element;
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
206 struct Traverse* traverse = &context->data[Traverse]->traverse;
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
207 element->data = (union Data*)traverse->current;
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
208 goto insertCase4_1(context, &context->data[Traverse]->traverse);
86
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_02(struct Context* context, struct Traverse* traverse) {
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
211 context->data[Traverse]->traverse.nodeStack = context->data[Traverse]->traverse.nodeStack -> next;
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
212 goto meta(context, RotateR);
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
213 }
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
214
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
215 __code insert4_02_stub(struct Context* context) {
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
216 goto insertCase4_02(context, &context->data[Traverse]->traverse);
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
217 }
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
218
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
219 __code insertCase4_2(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->right;
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
123
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
224 __code insert4_2_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_2(context, &context->data[Traverse]->traverse);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
232 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
233
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
234 __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
235 parent->color = Black;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
236 grandparent->color = Red;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
237
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
238 traverse->current = grandparent;
119
b224aa7b80a0 remove code stack, stack clear is directly called
ikkun
parents: 118
diff changeset
239 traverse->rotateNext = StackClear;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
240 if ((current == parent->left) && (parent == grandparent->left))
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
241 goto meta(context, RotateR);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
242 else
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
243 goto meta(context, RotateL);
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
244 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
245
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
246 __code insert5_stub(struct Context* context) {
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
247 struct Traverse* traverse = &context->data[Traverse]->traverse;
122
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
248 struct Node* parent = (struct Node*)traverse->nodeStack->data;
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
249 struct Node* grandparent = (struct Node*)traverse->nodeStack->next->data;
73a679a85c04 node stack rewrite
ikkun
parents: 121
diff changeset
250 traverse->nodeStack = traverse->nodeStack->next->next;
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
251 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
252 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
253
117
a574ba0da60f add comment rb_tree
ikkun
parents: 103
diff changeset
254 // put rotateLeft's continuation as argument
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
255 __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent, struct Element* element) {
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
256 struct Node* tmp = node->right;
123
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
257
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
258 if (parent) {
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
259 if (node == parent->left)
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
260 parent->left = tmp;
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
261 else
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
262 parent->right = tmp;
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
263 } else {
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
264 tree->root = tmp;
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
265 }
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
266 element->data = (union Data*)parent;
117
a574ba0da60f add comment rb_tree
ikkun
parents: 103
diff changeset
267
123
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
268 node->right = tmp->left;
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
269 tmp->left = node;
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
270 traverse->current = tmp;
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
271
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
272 goto meta(context, traverse->rotateNext);
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
273 }
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
274
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
275 __code rotateLeft_stub(struct Context* context) {
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
276 struct Traverse* traverse = &context->data[Traverse]->traverse;
123
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
277 struct Node* parent = (traverse->nodeStack)?(struct Node*)traverse->nodeStack->data:NULL;
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
278 traverse->nodeStack = traverse->nodeStack->next;
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
279 struct Allocate* allocate = &context->data[Allocate]->allocate;
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
280 allocate->size = sizeof(struct Element);
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
281 allocator(context);
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
282 struct Element* element = &context->data[context->dataNum]->element;
123
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
283 goto rotateLeft(context,
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
284 &context->data[Node]->node,
123
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
285 &context->data[Tree]->tree,
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
286 &context->data[Traverse]->traverse,
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
287 parent,
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
288 element);
123
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
289 }
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
290
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
291 __code rotateRight(struct Context* context, struct Node* node, struct Tree* tree, struct Traverse* traverse, struct Node* parent, struct Element* element) {
123
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
292 struct Node* tmp = node->left;
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 if (parent) {
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
295 if (node == parent->left)
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
296 parent->left = tmp;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
297 else
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
298 parent->right = tmp;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
299 } else {
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
300 tree->root = tmp;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
301 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
302
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
303 element->data = (union Data*)parent;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
304
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
305 node->left = tmp->right;
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
306 tmp->right = node;
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
307 traverse->current = tmp;
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
308
119
b224aa7b80a0 remove code stack, stack clear is directly called
ikkun
parents: 118
diff changeset
309 goto meta(context, traverse->rotateNext);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
310 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
311
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
312 __code rotateRight_stub(struct Context* context) {
123
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
313 struct Allocate* allocate = &context->data[Allocate]->allocate;
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
314 allocate->size = sizeof(struct Element);
933c80f48d06 node stack rewrite
ikkun
parents: 122
diff changeset
315 allocator(context);
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
316 struct Element* element = &context->data[context->dataNum]->element;
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
317 goto rotateRight(context,
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
318 &context->data[Node]->node,
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,
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
321 context->data[Traverse]->traverse.current,
124
36ac17d37be4 Fix compile error but not work
one
parents: 123
diff changeset
322 element);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
323 }
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
324
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
325 __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
326 traverse->current = 0;
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) {
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
332 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
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
119
b224aa7b80a0 remove code stack, stack clear is directly called
ikkun
parents: 118
diff changeset
343 goto meta(context, context->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) {
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
351 compare(context, traverse, traverse->current->key, node->key);
86
e06e1a9e569e create worker
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents:
diff changeset
352
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
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
356 goto meta(context, context->next);
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
91
1e074c3878c7 modify tree
Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
parents: 87
diff changeset
366 goto meta(context, context->next);
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 /* /\* } *\/ */