Mercurial > hg > Members > innparusu > Gears

comparison src/llrb/llrb.c @ 83:c13575c3dbe9

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
use stack
author Shohei KOKUBO <e105744@ie.u-ryukyu.ac.jp>
date Thu, 07 Jan 2016 08:20:03 +0900
parents dc6f665bb753
children 4db311ba1289
comparison
equal deleted inserted replaced
82:69d0637e52fd 83:c13575c3dbe9
12 allocate->size = sizeof(struct Node); 12 allocate->size = sizeof(struct Node);
13 allocator(context); 13 allocator(context);
14 14
15 stack_push(context->code_stack, &context->next); 15 stack_push(context->code_stack, &context->next);
16 16
17 context->next = StackClear;
18 stack_push(context->code_stack, &context->next);
19
17 tree->root = &context->data[context->dataNum]->node; 20 tree->root = &context->data[context->dataNum]->node;
18 21
19 if (root) { 22 if (root) {
20 tree->current = root; 23 tree->current = root;
21 compare(context, tree, tree->current->key, context->data[Node]->node.key); 24 compare(context, tree, tree->current->key, context->data[Node]->node.key);
30 goto put(context, &context->data[Tree]->tree, context->data[Tree]->tree.root, &context->data[Allocate]->allocate); 33 goto put(context, &context->data[Tree]->tree, context->data[Tree]->tree.root, &context->data[Allocate]->allocate);
31 } 34 }
32 35
33 __code replaceNode(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) { 36 __code replaceNode(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) {
34 *newNode = *oldNode; 37 *newNode = *oldNode;
38 stack_push(context->node_stack, &newNode);
35 39
36 if (result == EQ) { 40 if (result == EQ) {
37 newNode->value = context->data[Node]->node.value; 41 newNode->value = context->data[Node]->node.value;
38 42
39 stack_pop(context->code_stack, &context->next); 43 stack_pop(context->code_stack, &context->next);
47 } 51 }
48 52
49 allocator(context); 53 allocator(context);
50 54
51 if (tree->current) { 55 if (tree->current) {
52 tree->current->parent = newNode;
53 compare(context, tree, tree->current->key, context->data[Node]->node.key); 56 compare(context, tree, tree->current->key, context->data[Node]->node.key);
54 goto meta(context, Replace); 57 goto meta(context, Replace);
55 } 58 }
56 59
57 tree->current = newNode;
58 goto meta(context, Insert); 60 goto meta(context, Insert);
59 } 61 }
60 62
61 __code replaceNode_stub(struct Context* context) { 63 __code replaceNode_stub(struct Context* context) {
62 goto replaceNode(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result); 64 goto replaceNode(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result);
63 } 65 }
64 66
65 __code insertNode(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) { 67 __code insertNode(struct Context* context, struct Tree* tree, struct Node* node, struct Node* newNode) {
66 node->color = Red; 68 node->color = Red;
67 *newNode = *node; 69 *newNode = *node;
68 newNode->parent = tree->current;
69 70
70 tree->current = newNode; 71 tree->current = newNode;
71 72
72 goto meta(context, InsertCase1); 73 goto meta(context, InsertCase1);
73 } 74 }
75 __code insertNode_stub(struct Context* context) { 76 __code insertNode_stub(struct Context* context) {
76 goto insertNode(context, &context->data[Tree]->tree, &context->data[Node]->node, &context->data[context->dataNum]->node); 77 goto insertNode(context, &context->data[Tree]->tree, &context->data[Node]->node, &context->data[context->dataNum]->node);
77 } 78 }
78 79
79 __code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) { 80 __code insertCase1(struct Context* context, struct Tree* tree, struct Node* current) {
80 if (current->parent) 81 if (!isEmpty(context->node_stack))
81 goto meta(context, InsertCase2); 82 goto meta(context, InsertCase2);
82 83
83 tree->root->color = Black; 84 tree->root->color = Black;
84 tree->current = 0;
85 85
86 stack_pop(context->code_stack, &context->next); 86 stack_pop(context->code_stack, &context->next);
87 goto meta(context, context->next); 87 goto meta(context, context->next);
88 } 88 }
89 89
90 __code insert1_stub(struct Context* context) { 90 __code insert1_stub(struct Context* context) {
91 goto insertCase1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); 91 goto insertCase1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
92 } 92 }
93 93
94 __code insertCase2(struct Context* context, struct Node* current) { 94 __code insertCase2(struct Context* context, struct Node* current) {
95 if (current->parent->color == Black) { 95 struct Node* parent;
96 stack_pop(context->node_stack, &parent);
97
98 if (parent->color == Black) {
96 stack_pop(context->code_stack, &context->next); 99 stack_pop(context->code_stack, &context->next);
97 goto meta(context, context->next); 100 goto meta(context, context->next);
98 } 101 }
99 102
103 stack_push(context->node_stack, &parent);
100 goto meta(context, InsertCase3); 104 goto meta(context, InsertCase3);
101 } 105 }
102 106
103 __code insert2_stub(struct Context* context) { 107 __code insert2_stub(struct Context* context) {
104 goto insertCase2(context, context->data[Tree]->tree.current); 108 goto insertCase2(context, context->data[Tree]->tree.current);
105 } 109 }
106 110
107 __code insertCase3(struct Context* context, struct Tree* tree, struct Node* current) { 111 __code insertCase3(struct Context* context, struct Tree* tree, struct Node* current) {
112 struct Node* parent;
108 struct Node* uncle; 113 struct Node* uncle;
109 struct Node* grandparent = current->parent->parent; 114 struct Node* grandparent;
110 115
111 if (grandparent->left == current->parent) 116 stack_pop(context->node_stack, &parent);
117 stack_pop(context->node_stack, &grandparent);
118
119 if (grandparent->left == parent)
112 uncle = grandparent->right; 120 uncle = grandparent->right;
113 else 121 else
114 uncle = grandparent->left; 122 uncle = grandparent->left;
115 123
116 if (uncle && (uncle->color == Red)) { 124 if (uncle && (uncle->color == Red)) {
117 current->parent->color = Black; 125 parent->color = Black;
118 uncle->color = Black; 126 uncle->color = Black;
119 grandparent->color = Red; 127 grandparent->color = Red;
120 tree->current = grandparent; 128 tree->current = grandparent;
121 goto meta(context, InsertCase1); 129 goto meta(context, InsertCase1);
122 } 130 }
123 131
132 stack_push(context->node_stack, &grandparent);
133 stack_push(context->node_stack, &parent);
134
124 goto meta(context, InsertCase4); 135 goto meta(context, InsertCase4);
125 } 136 }
126 137
127 __code insert3_stub(struct Context* context) { 138 __code insert3_stub(struct Context* context) {
128 goto insertCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); 139 goto insertCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
129 } 140 }
130 141
131 __code insertCase4(struct Context* context, struct Node* current) { 142 __code insertCase4(struct Context* context, struct Tree* tree, struct Node* current) {
132 struct Node* grandparent = current->parent->parent; 143 struct Node* parent;
133 144 struct Node* grandparent;
134 if ((current == current->parent->right) && (current->parent == grandparent->left)) { 145
146 stack_pop(context->node_stack, &parent);
147 stack_pop(context->node_stack, &grandparent);
148
149 stack_push(context->node_stack, &grandparent);
150
151 tree->current = parent;
152
153 if ((current == parent->right) && (parent == grandparent->left)) {
135 context->next = InsertCase4_1; 154 context->next = InsertCase4_1;
136 155
137 stack_push(context->code_stack, &context->next); 156 stack_push(context->code_stack, &context->next);
138 goto meta(context, RotateL); 157 goto meta(context, RotateL);
139 } else if ((current == current->parent->left) && (current->parent == grandparent->right)) { 158 } else if ((current == parent->left) && (parent == grandparent->right)) {
140 context->next = InsertCase4_2; 159 context->next = InsertCase4_2;
141 160
142 stack_push(context->code_stack, &context->next); 161 stack_push(context->code_stack, &context->next);
143 goto meta(context, RotateR); 162 goto meta(context, RotateR);
144 } 163 }
145 164
165 stack_push(context->node_stack, &parent);
166 tree->current = current;
146 goto meta(context, InsertCase5); 167 goto meta(context, InsertCase5);
147 } 168 }
148 169
149 __code insert4_stub(struct Context* context) { 170 __code insert4_stub(struct Context* context) {
150 goto insertCase4(context, context->data[Tree]->tree.current); 171 goto insertCase4(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
151 } 172 }
152 173
153 __code insertCase4_1(struct Context* context, struct Tree* tree) { 174 __code insertCase4_1(struct Context* context, struct Tree* tree) {
175 stack_push(context->node_stack, &tree->current);
154 tree->current = tree->current->left; 176 tree->current = tree->current->left;
155 goto meta(context, InsertCase5); 177 goto meta(context, InsertCase5);
156 } 178 }
157 179
158 __code insert4_1_stub(struct Context* context) { 180 __code insert4_1_stub(struct Context* context) {
159 goto insertCase4_1(context, &context->data[Tree]->tree); 181 goto insertCase4_1(context, &context->data[Tree]->tree);
160 } 182 }
161 183
162 __code insertCase4_2(struct Context* context, struct Tree* tree) { 184 __code insertCase4_2(struct Context* context, struct Tree* tree) {
185 stack_push(context->node_stack, &tree->current);
163 tree->current = tree->current->right; 186 tree->current = tree->current->right;
164 goto meta(context, InsertCase5); 187 goto meta(context, InsertCase5);
165 } 188 }
166 189
167 __code insert4_2_stub(struct Context* context) { 190 __code insert4_2_stub(struct Context* context) {
168 goto insertCase4_2(context, &context->data[Tree]->tree); 191 goto insertCase4_2(context, &context->data[Tree]->tree);
169 } 192 }
170 193
171 __code insertCase5(struct Context* context, struct Tree* tree, struct Node* current) { 194 __code insertCase5(struct Context* context, struct Tree* tree, struct Node* current) {
172 current->parent->color = Black; 195 struct Node* parent;
173 current->parent->parent->color = Red; 196 struct Node* grandparent;
174 197
175 tree->current = current->parent->parent; 198 stack_pop(context->node_stack, &parent);
176 199 stack_pop(context->node_stack, &grandparent);
177 context->next = InsertCase5_1; 200
178 stack_push(context->code_stack, &context->next); 201 parent->color = Black;
179 202 grandparent->color = Red;
180 if ((current == current->parent->left) && (current->parent == current->parent->parent->left)) 203
204 tree->current = grandparent;
205
206 if ((current == parent->left) && (parent == grandparent->left))
181 goto meta(context, RotateR); 207 goto meta(context, RotateR);
182 else 208 else
183 goto meta(context, RotateL); 209 goto meta(context, RotateL);
184 } 210 }
185 211
186 __code insert5_stub(struct Context* context) { 212 __code insert5_stub(struct Context* context) {
187 goto insertCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); 213 goto insertCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current);
188 } 214 }
189 215
190 __code insertCase5_1(struct Context* context, struct Tree* tree) { 216 __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree) {
191 tree->current = NULL; 217 struct Node* tmp = node->right;
192 218 struct Node* parent = 0;
219
220 stack_pop(context->node_stack, &parent);
221
222 if (parent) {
223 if (node == parent->left)
224 parent->left = tmp;
225 else
226 parent->right = tmp;
227 } else {
228 tree->root = tmp;
229 }
230
231 stack_push(context->node_stack, &parent);
232
233 node->right = tmp->left;
234 tmp->left = node;
235 tree->current = tmp;
236
193 stack_pop(context->code_stack, &context->next); 237 stack_pop(context->code_stack, &context->next);
194 goto meta(context, context->next); 238 goto meta(context, context->next);
195 } 239 }
196 240
197 __code insert5_1_stub(struct Context* context) { 241 __code rotateLeft_stub(struct Context* context) {
198 goto insertCase5_1(context, &context->data[context->dataNum]->tree); 242 goto rotateLeft(context, context->data[Tree]->tree.current, &context->data[Tree]->tree);
199 } 243 }
200 244
201 __code rotateLeft(struct Context* context, struct Node* node, struct Tree* tree) { 245 __code rotateRight(struct Context* context, struct Node* node, struct Tree* tree) {
202 struct Node* tmp = node->right; 246 struct Node* tmp = node->left;
203 247 struct Node* parent = 0;
204 if (node->parent) { 248
205 if (node == node->parent->left) 249 stack_pop(context->node_stack, &parent);
206 node->parent->left = tmp; 250
251 if (parent) {
252 if (node == parent->left)
253 parent->left = tmp;
207 else 254 else
208 node->parent->right = tmp; 255 parent->right = tmp;
209 } else { 256 } else {
210 tree->root = tmp; 257 tree->root = tmp;
211 } 258 }
212 259
213 if (tmp) 260 stack_push(context->node_stack, &parent);
214 tmp->parent = node->parent; 261
215 262 node->left = tmp->right;
216 node->right = tmp->left; 263 tmp->right = node;
217
218 if (tmp->left)
219 tmp->left->parent = node;
220
221 tmp->left = node;
222 node->parent = tmp;
223 tree->current = tmp; 264 tree->current = tmp;
224 265
225 stack_pop(context->code_stack, &context->next); 266 stack_pop(context->code_stack, &context->next);
226 goto meta(context, context->next); 267 goto meta(context, context->next);
227 } 268 }
228 269
229 __code rotateLeft_stub(struct Context* context) { 270 __code rotateRight_stub(struct Context* context) {
230 goto rotateLeft(context, context->data[Tree]->tree.current, &context->data[Tree]->tree); 271 goto rotateRight(context, context->data[Tree]->tree.current, &context->data[Tree]->tree);
231 } 272 }
232 273
233 __code rotateRight(struct Context* context, struct Node* node, struct Tree* tree) { 274 __code stackClear(struct Context* context, stack_ptr node_stack, struct Tree* tree) {
234 struct Node* tmp = node->left; 275 if (stack_pop(node_stack, &tree->current) == 0)
235 276 goto meta(context, StackClear);
236 if (node->parent) { 277
237 if (node == node->parent->left) 278 tree->current = 0;
238 node->parent->left = tmp; 279
239 else
240 node->parent->right = tmp;
241 } else {
242 tree->root = tmp;
243 }
244
245 if (tmp)
246 tmp->parent = node->parent;
247
248 node->left = tmp->right;
249
250 if (tmp->right)
251 tmp->right->parent = node;
252
253 tmp->right = node;
254 node->parent = tmp;
255 tree->current = tmp;
256
257 stack_pop(context->code_stack, &context->next); 280 stack_pop(context->code_stack, &context->next);
258 goto meta(context, context->next); 281 goto meta(context, context->next);
259 } 282 }
260 283
261 __code rotateRight_stub(struct Context* context) { 284 __code stackClear_stub(struct Context* context) {
262 goto rotateRight(context, context->data[Tree]->tree.current, &context->data[Tree]->tree); 285 goto stackClear(context, context->node_stack, &context->data[Tree]->tree);
263 } 286 }
264 287
265 __code get(struct Context* context, struct Tree* tree) { 288
266 if (tree->root) { 289 /* /\* __code get(struct Context* context, struct Tree* tree) { *\/ */
267 tree->current = tree->root; 290 /* /\* if (tree->root) { *\/ */
268 291 /* /\* tree->current = tree->root; *\/ */
269 goto meta(context, Search); 292
270 } 293 /* /\* goto meta(context, Search); *\/ */
271 294 /* /\* } *\/ */
272 stack_pop(context->code_stack, &context->next); 295
273 goto meta(context, context->next); 296 /* /\* stack_pop(context->code_stack, &context->next); *\/ */
274 } 297 /* /\* goto meta(context, context->next); *\/ */
275 298 /* /\* } *\/ */
276 __code get_stub(struct Context* context) { 299
277 goto get(context, &context->data[Tree]->tree); 300 /* /\* __code get_stub(struct Context* context) { *\/ */
278 } 301 /* /\* goto get(context, &context->data[Tree]->tree); *\/ */
279 302 /* /\* } *\/ */
280 __code search(struct Context* context, struct Tree* tree, struct Node* node) { 303
281 compare(context, tree, tree->current->key, node->key); 304 /* /\* __code search(struct Context* context, struct Tree* tree, struct Node* node) { *\/ */
282 305 /* /\* compare(context, tree, tree->current->key, node->key); *\/ */
283 if (tree->result == EQ) { 306
284 *node = *tree->current; 307 /* /\* if (tree->result == EQ) { *\/ */
285 308 /* /\* *node = *tree->current; *\/ */
286 goto meta(context, context->next); 309
287 } else if (tree->result == GT) { 310 /* /\* goto meta(context, context->next); *\/ */
288 tree->current = tree->current->right; 311 /* /\* } else if (tree->result == GT) { *\/ */
289 } else { 312 /* /\* tree->current = tree->current->right; *\/ */
290 tree->current = tree->current->left; 313 /* /\* } else { *\/ */
291 } 314 /* /\* tree->current = tree->current->left; *\/ */
292 315 /* /\* } *\/ */
293 if (tree->current) 316
294 goto meta(context, Search); 317 /* /\* if (tree->current) *\/ */
295 318 /* /\* goto meta(context, Search); *\/ */
296 stack_pop(context->code_stack, &context->next); 319
297 goto meta(context, context->next); 320 /* /\* stack_pop(context->code_stack, &context->next); *\/ */
298 } 321 /* /\* goto meta(context, context->next); *\/ */
299 322 /* /\* } *\/ */
300 __code search_stub(struct Context* context) { 323
301 goto search(context, &context->data[Tree]->tree, &context->data[Node]->node); 324 /* /\* __code search_stub(struct Context* context) { *\/ */
302 } 325 /* /\* goto search(context, &context->data[Tree]->tree, &context->data[Node]->node); *\/ */
303 326 /* /\* } *\/ */
304 __code delete(struct Context* context, struct Tree* tree) { 327
305 if (tree->root) { 328 /* /\* __code delete(struct Context* context, struct Tree* tree) { *\/ */
306 stack_push(context->code_stack, &context->next); 329 /* /\* if (tree->root) { *\/ */
307 context->next = Delete1; 330 /* /\* stack_push(context->code_stack, &context->next); *\/ */
308 goto meta(context, Get); 331 /* /\* context->next = Delete1; *\/ */
309 } 332 /* /\* goto meta(context, Get); *\/ */
310 333 /* /\* } *\/ */
311 goto meta(context, context->next); 334
312 } 335 /* /\* goto meta(context, context->next); *\/ */
313 336 /* /\* } *\/ */
314 __code delete_stub(struct Context* context) { 337
315 goto delete(context, &context->data[Tree]->tree); 338 /* /\* __code delete_stub(struct Context* context) { *\/ */
316 } 339 /* /\* goto delete(context, &context->data[Tree]->tree); *\/ */
317 340 /* /\* } *\/ */
318 __code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) { 341
319 allocate->size = sizeof(struct Node); 342 /* /\* __code delete1(struct Context* context, struct Tree* tree, struct Allocate* allocate) { *\/ */
320 allocator(context); 343 /* /\* allocate->size = sizeof(struct Node); *\/ */
321 344 /* /\* allocator(context); *\/ */
322 struct Node* root = tree->root; 345
323 346 /* /\* struct Node* root = tree->root; *\/ */
324 tree->root = &context->data[context->dataNum]->node; 347
325 tree->current = root; 348 /* /\* tree->root = &context->data[context->dataNum]->node; *\/ */
326 349 /* /\* tree->current = root; *\/ */
327 compare(context, tree, tree->current->key, context->data[Node]->node.key); 350
328 351 /* /\* compare(context, tree, tree->current->key, context->data[Node]->node.key); *\/ */
329 goto meta(context, Replace_d1); 352
330 } 353 /* /\* goto meta(context, Replace_d1); *\/ */
331 354 /* /\* } *\/ */
332 __code delete1_stub(struct Context* context) { 355
333 goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate); 356 /* /\* __code delete1_stub(struct Context* context) { *\/ */
334 } 357 /* /\* goto delete1(context, &context->data[Tree]->tree, &context->data[Allocate]->allocate); *\/ */
335 358 /* /\* } *\/ */
336 __code delete2(struct Context* context, struct Node* current) { 359
337 if (current->color == Black) { 360 /* /\* __code delete2(struct Context* context, struct Node* current) { *\/ */
338 struct Node* child = current->right == NULL ? current->left : current->right; 361 /* /\* if (current->color == Black) { *\/ */
339 current->color = child == NULL ? Black : child->color; 362 /* /\* struct Node* child = current->right == NULL ? current->left : current->right; *\/ */
340 363 /* /\* current->color = child == NULL ? Black : child->color; *\/ */
341 goto meta(context, DeleteCase1); 364
342 } 365 /* /\* goto meta(context, DeleteCase1); *\/ */
343 366 /* /\* } *\/ */
344 goto meta(context, Delete3); 367
345 } 368 /* /\* goto meta(context, Delete3); *\/ */
346 369 /* /\* } *\/ */
347 __code delete2_stub(struct Context* context) { 370
348 goto delete2(context, context->data[Tree]->tree.current); 371 /* /\* __code delete2_stub(struct Context* context) { *\/ */
349 } 372 /* /\* goto delete2(context, context->data[Tree]->tree.current); *\/ */
350 373 /* /\* } *\/ */
351 __code delete3(struct Context* context, struct Tree* tree, struct Node* current) { 374
352 struct Node* tmp = current->right == NULL ? current->left : current->right; 375 /* /\* __code delete3(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
353 376 /* /\* struct Node* tmp = current->right == NULL ? current->left : current->right; *\/ */
354 if (current->parent) { 377
355 if (current == current->parent->left) 378 /* /\* if (current->parent) { *\/ */
356 current->parent->left = tmp; 379 /* /\* if (current == current->parent->left) *\/ */
357 else 380 /* /\* current->parent->left = tmp; *\/ */
358 current->parent->right = tmp; 381 /* /\* else *\/ */
359 } else { 382 /* /\* current->parent->right = tmp; *\/ */
360 tree->root = tmp; 383 /* /\* } else { *\/ */
361 } 384 /* /\* tree->root = tmp; *\/ */
362 385 /* /\* } *\/ */
363 if (tmp) 386
364 tmp->parent = current->parent; 387 /* /\* if (tmp) *\/ */
365 388 /* /\* tmp->parent = current->parent; *\/ */
366 if (current->parent == NULL && tmp) 389
367 tmp->color = Black; 390 /* /\* if (current->parent == NULL && tmp) *\/ */
368 391 /* /\* tmp->color = Black; *\/ */
369 current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL); 392
370 393 /* /\* current == current->parent->left ? (current->parent->left = NULL) : (current->parent->right = NULL); *\/ */
371 stack_pop(context->code_stack, &context->next); 394
372 goto meta(context, context->next); 395 /* /\* stack_pop(context->code_stack, &context->next); *\/ */
373 } 396 /* /\* goto meta(context, context->next); *\/ */
374 397 /* /\* } *\/ */
375 __code delete3_stub(struct Context* context) { 398
376 goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); 399 /* /\* __code delete3_stub(struct Context* context) { *\/ */
377 } 400 /* /\* goto delete3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
378 401 /* /\* } *\/ */
379 __code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) { 402
380 *newNode = *oldNode; 403 /* /\* __code replaceNodeForDelete1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode, int result) { *\/ */
381 404 /* /\* *newNode = *oldNode; *\/ */
382 if (result == EQ) 405
383 goto meta(context, Replace_d2); 406 /* /\* if (result == EQ) *\/ */
384 else if (result == GT) 407 /* /\* goto meta(context, Replace_d2); *\/ */
385 tree->current = newNode->right; 408 /* /\* else if (result == GT) *\/ */
386 else 409 /* /\* tree->current = newNode->right; *\/ */
387 tree->current = newNode->left; 410 /* /\* else *\/ */
388 411 /* /\* tree->current = newNode->left; *\/ */
389 tree->current->parent = newNode; 412
390 413 /* /\* tree->current->parent = newNode; *\/ */
391 if (tree->current->left == NULL && tree->current->right == NULL) 414
392 goto meta(context, Delete2); 415 /* /\* if (tree->current->left == NULL && tree->current->right == NULL) *\/ */
393 416 /* /\* goto meta(context, Delete2); *\/ */
394 if (result == GT) 417
395 newNode->right = context->heap; 418 /* /\* if (result == GT) *\/ */
396 else if (result == LT) 419 /* /\* newNode->right = context->heap; *\/ */
397 newNode->left = context->heap; 420 /* /\* else if (result == LT) *\/ */
398 421 /* /\* newNode->left = context->heap; *\/ */
399 allocator(context); 422
400 423 /* /\* allocator(context); *\/ */
401 compare(context, tree, tree->current->key, context->data[Node]->node.key); 424
402 425 /* /\* compare(context, tree, tree->current->key, context->data[Node]->node.key); *\/ */
403 goto meta(context, Replace_d1); 426
404 } 427 /* /\* goto meta(context, Replace_d1); *\/ */
405 428 /* /\* } *\/ */
406 __code replaceNodeForDelete1_stub(struct Context* context) { 429
407 goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result); 430 /* /\* __code replaceNodeForDelete1_stub(struct Context* context) { *\/ */
408 } 431 /* /\* goto replaceNodeForDelete1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node, context->data[Tree]->tree.result); *\/ */
409 432 /* /\* } *\/ */
410 __code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) { 433
411 if (tree->current->left && tree->current->right) { 434 /* /\* __code replaceNodeForDelete2(struct Context* context, struct Tree* tree, struct Node* newNode) { *\/ */
412 newNode->left->parent = newNode; 435 /* /\* if (tree->current->left && tree->current->right) { *\/ */
413 tree->current = newNode->left; 436 /* /\* newNode->left->parent = newNode; *\/ */
414 newNode->left = context->heap; 437 /* /\* tree->current = newNode->left; *\/ */
415 tree->deleted = newNode; 438 /* /\* newNode->left = context->heap; *\/ */
416 439 /* /\* tree->deleted = newNode; *\/ */
417 allocator(context); 440
418 tree->current->parent = newNode; 441 /* /\* allocator(context); *\/ */
419 442 /* /\* tree->current->parent = newNode; *\/ */
420 goto meta(context, FindMax1); 443
421 } 444 /* /\* goto meta(context, FindMax1); *\/ */
422 445 /* /\* } *\/ */
423 goto meta(context, Delete2); 446
424 } 447 /* /\* goto meta(context, Delete2); *\/ */
425 448 /* /\* } *\/ */
426 __code replaceNodeForDelete2_stub(struct Context* context) { 449
427 goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node); 450 /* /\* __code replaceNodeForDelete2_stub(struct Context* context) { *\/ */
428 } 451 /* /\* goto replaceNodeForDelete2(context, &context->data[Tree]->tree, &context->data[context->dataNum]->node); *\/ */
429 452 /* /\* } *\/ */
430 __code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { 453
431 *newNode = *oldNode; 454 /* /\* __code findMax1(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { *\/ */
432 455 /* /\* *newNode = *oldNode; *\/ */
433 if (newNode->right) 456
434 goto meta(context, FindMax2); 457 /* /\* if (newNode->right) *\/ */
435 458 /* /\* goto meta(context, FindMax2); *\/ */
436 tree->deleted->key = newNode->key; 459
437 tree->deleted->value = newNode->value; 460 /* /\* tree->deleted->key = newNode->key; *\/ */
438 461 /* /\* tree->deleted->value = newNode->value; *\/ */
439 tree->current = newNode; 462
440 463 /* /\* tree->current = newNode; *\/ */
441 goto meta(context, Delete2); 464
442 } 465 /* /\* goto meta(context, Delete2); *\/ */
443 466 /* /\* } *\/ */
444 __code findMax1_stub(struct Context* context) { 467
445 goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); 468 /* /\* __code findMax1_stub(struct Context* context) { *\/ */
446 } 469 /* /\* goto findMax1(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); *\/ */
447 470 /* /\* } *\/ */
448 471
449 __code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { 472
450 *newNode = *oldNode; 473 /* /\* __code findMax2(struct Context* context, struct Tree* tree, struct Node* oldNode, struct Node* newNode) { *\/ */
451 474 /* /\* *newNode = *oldNode; *\/ */
452 if (newNode->right->right) { 475
453 tree->current = newNode->right; 476 /* /\* if (newNode->right->right) { *\/ */
454 newNode->right = context->heap; 477 /* /\* tree->current = newNode->right; *\/ */
455 478 /* /\* newNode->right = context->heap; *\/ */
456 allocator(context); 479
457 tree->current->parent = newNode; 480 /* /\* allocator(context); *\/ */
458 481 /* /\* tree->current->parent = newNode; *\/ */
459 goto meta(context, FindMax2); 482
460 } 483 /* /\* goto meta(context, FindMax2); *\/ */
461 484 /* /\* } *\/ */
462 tree->deleted->key = newNode->right->key; 485
463 tree->deleted->value = newNode->right->value; 486 /* /\* tree->deleted->key = newNode->right->key; *\/ */
464 487 /* /\* tree->deleted->value = newNode->right->value; *\/ */
465 tree->current = newNode; 488
466 489 /* /\* tree->current = newNode; *\/ */
467 goto meta(context, Delete2); 490
468 } 491 /* /\* goto meta(context, Delete2); *\/ */
469 492 /* /\* } *\/ */
470 __code findMax2_stub(struct Context* context) { 493
471 goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); 494 /* /\* __code findMax2_stub(struct Context* context) { *\/ */
472 } 495 /* /\* goto findMax2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current, &context->data[context->dataNum]->node); *\/ */
473 496 /* /\* } *\/ */
474 __code deleteCase1(struct Context* context, struct Node* current) { 497
475 if (current->parent) 498 /* /\* __code deleteCase1(struct Context* context, struct Node* current) { *\/ */
476 goto meta(context, DeleteCase2); 499 /* /\* if (current->parent) *\/ */
477 500 /* /\* goto meta(context, DeleteCase2); *\/ */
478 goto meta(context, Delete3); 501
479 } 502 /* /\* goto meta(context, Delete3); *\/ */
480 503 /* /\* } *\/ */
481 __code deleteCase1_stub(struct Context* context) { 504
482 goto deleteCase1(context, context->data[Tree]->tree.current); 505 /* /\* __code deleteCase1_stub(struct Context* context) { *\/ */
483 } 506 /* /\* goto deleteCase1(context, context->data[Tree]->tree.current); *\/ */
484 507 /* /\* } *\/ */
485 __code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) { 508
486 struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; 509 /* /\* __code deleteCase2(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
487 510 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
488 if ((sibling == NULL ? Black : sibling->color) == Red) { 511
489 current->parent->color = Red; 512 /* /\* if ((sibling == NULL ? Black : sibling->color) == Red) { *\/ */
490 sibling->color = Black; 513 /* /\* current->parent->color = Red; *\/ */
491 514 /* /\* sibling->color = Black; *\/ */
492 current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap); 515
493 allocator(context); 516 /* /\* current == current->parent->left ? (current->parent->left = context->heap) : (current->parent->right = context->heap); *\/ */
494 context->data[context->dataNum]->node = *sibling; 517 /* /\* allocator(context); *\/ */
495 518 /* /\* context->data[context->dataNum]->node = *sibling; *\/ */
496 tree->current = current->parent; 519
497 520 /* /\* tree->current = current->parent; *\/ */
498 context->next = DeleteCase3; 521
499 stack_push(context->code_stack, &context->next); 522 /* /\* context->next = DeleteCase3; *\/ */
500 523 /* /\* stack_push(context->code_stack, &context->next); *\/ */
501 if (current == current->parent->left) 524
502 goto meta(context, RotateL); 525 /* /\* if (current == current->parent->left) *\/ */
503 else 526 /* /\* goto meta(context, RotateL); *\/ */
504 goto meta(context, RotateR); 527 /* /\* else *\/ */
505 } 528 /* /\* goto meta(context, RotateR); *\/ */
506 529 /* /\* } *\/ */
507 goto meta(context, DeleteCase3); 530
508 } 531 /* /\* goto meta(context, DeleteCase3); *\/ */
509 532 /* /\* } *\/ */
510 __code deleteCase2_stub(struct Context* context) { 533
511 goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); 534 /* /\* __code deleteCase2_stub(struct Context* context) { *\/ */
512 } 535 /* /\* goto deleteCase2(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
513 536 /* /\* } *\/ */
514 __code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) { 537
515 struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; 538 /* /\* __code deleteCase3(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
516 539 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
517 if (current->parent->color == Black && 540
518 (sibling == NULL ? Black : sibling->color) == Black && 541 /* /\* if (current->parent->color == Black && *\/ */
519 (sibling->left == NULL ? Black : sibling->left->color) == Black && 542 /* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */
520 (sibling->right == NULL ? Black : sibling->right->color) == Black) { 543 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */
521 sibling->color = Red; 544 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */
522 545 /* /\* sibling->color = Red; *\/ */
523 tree->current = current->parent; 546
524 goto meta(context, DeleteCase1); 547 /* /\* tree->current = current->parent; *\/ */
525 } 548 /* /\* goto meta(context, DeleteCase1); *\/ */
526 549 /* /\* } *\/ */
527 goto meta(context, DeleteCase4); 550
528 } 551 /* /\* goto meta(context, DeleteCase4); *\/ */
529 552 /* /\* } *\/ */
530 __code deleteCase3_stub(struct Context* context) { 553
531 goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); 554 /* /\* __code deleteCase3_stub(struct Context* context) { *\/ */
532 } 555 /* /\* goto deleteCase3(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
533 556 /* /\* } *\/ */
534 __code deleteCase4(struct Context* context, struct Node* current) { 557
535 struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; 558 /* /\* __code deleteCase4(struct Context* context, struct Node* current) { *\/ */
536 559 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
537 if (current->parent->color == Red && 560
538 (sibling == NULL ? Black : sibling->color) == Black && 561 /* /\* if (current->parent->color == Red && *\/ */
539 (sibling->left == NULL ? Black : sibling->left->color) == Black && 562 /* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */
540 (sibling->right == NULL ? Black : sibling->right->color) == Black) { 563 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */
541 sibling->color = Red; 564 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */
542 current->parent->color = Black; 565 /* /\* sibling->color = Red; *\/ */
543 566 /* /\* current->parent->color = Black; *\/ */
544 goto meta(context, Delete3); 567
545 } 568 /* /\* goto meta(context, Delete3); *\/ */
546 569 /* /\* } *\/ */
547 goto meta(context, DeleteCase5); 570
548 } 571 /* /\* goto meta(context, DeleteCase5); *\/ */
549 572 /* /\* } *\/ */
550 __code deleteCase4_stub(struct Context* context) { 573
551 goto deleteCase4(context, context->data[Tree]->tree.current); 574 /* /\* __code deleteCase4_stub(struct Context* context) { *\/ */
552 } 575 /* /\* goto deleteCase4(context, context->data[Tree]->tree.current); *\/ */
553 576 /* /\* } *\/ */
554 __code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) { 577
555 struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; 578 /* /\* __code deleteCase5(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
556 sibling->parent = current->parent; 579 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
557 580 /* /\* sibling->parent = current->parent; *\/ */
558 if (current == current->parent->left && 581
559 (sibling == NULL ? Black : sibling->color) == Black && 582 /* /\* if (current == current->parent->left && *\/ */
560 (sibling->left == NULL ? Black : sibling->left->color) == Red && 583 /* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */
561 (sibling->right == NULL ? Black : sibling->right->color) == Black) { 584 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Red && *\/ */
562 sibling->color = Red; 585 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Black) { *\/ */
563 sibling->left->color = Black; 586 /* /\* sibling->color = Red; *\/ */
564 587 /* /\* sibling->left->color = Black; *\/ */
565 sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); 588
566 allocator(context); 589 /* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */
567 struct Node* tmp = &context->data[context->dataNum]->node; 590 /* /\* allocator(context); *\/ */
568 *tmp = *sibling; 591 /* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */
569 tmp->parent = current; 592 /* /\* *tmp = *sibling; *\/ */
570 593 /* /\* tmp->parent = current; *\/ */
571 tmp->left = context->heap; 594
572 allocator(context); 595 /* /\* tmp->left = context->heap; *\/ */
573 context->data[context->dataNum]->node = *sibling->left; 596 /* /\* allocator(context); *\/ */
574 context->data[context->dataNum]->node.parent = tmp; 597 /* /\* context->data[context->dataNum]->node = *sibling->left; *\/ */
575 598 /* /\* context->data[context->dataNum]->node.parent = tmp; *\/ */
576 tree->current = tmp; 599
577 600 /* /\* tree->current = tmp; *\/ */
578 context->next = DeleteCase6; 601
579 stack_push(context->code_stack, &context->next); 602 /* /\* context->next = DeleteCase6; *\/ */
580 603 /* /\* stack_push(context->code_stack, &context->next); *\/ */
581 goto meta(context, RotateR); 604
582 } else if (current == current->parent->right && 605 /* /\* goto meta(context, RotateR); *\/ */
583 (sibling == NULL ? Black : sibling->color) == Black && 606 /* /\* } else if (current == current->parent->right && *\/ */
584 (sibling->left == NULL ? Black : sibling->left->color) == Black && 607 /* /\* (sibling == NULL ? Black : sibling->color) == Black && *\/ */
585 (sibling->right == NULL ? Black : sibling->right->color) == Red) { 608 /* /\* (sibling->left == NULL ? Black : sibling->left->color) == Black && *\/ */
586 sibling->color = Red; 609 /* /\* (sibling->right == NULL ? Black : sibling->right->color) == Red) { *\/ */
587 sibling->right->color = Black; 610 /* /\* sibling->color = Red; *\/ */
588 611 /* /\* sibling->right->color = Black; *\/ */
589 sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); 612
590 allocator(context); 613 /* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */
591 struct Node* tmp = &context->data[context->dataNum]->node; 614 /* /\* allocator(context); *\/ */
592 *tmp = *sibling; 615 /* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */
593 tmp->parent = current; 616 /* /\* *tmp = *sibling; *\/ */
594 617 /* /\* tmp->parent = current; *\/ */
595 tmp->right = context->heap; 618
596 allocator(context); 619 /* /\* tmp->right = context->heap; *\/ */
597 context->data[context->dataNum]->node = *sibling->right; 620 /* /\* allocator(context); *\/ */
598 context->data[context->dataNum]->node.parent = tmp; 621 /* /\* context->data[context->dataNum]->node = *sibling->right; *\/ */
599 622 /* /\* context->data[context->dataNum]->node.parent = tmp; *\/ */
600 tree->current = tmp; 623
601 624 /* /\* tree->current = tmp; *\/ */
602 context->next = DeleteCase6; 625
603 stack_push(context->code_stack, &context->next); 626 /* /\* context->next = DeleteCase6; *\/ */
604 goto meta(context, RotateL); 627 /* /\* stack_push(context->code_stack, &context->next); *\/ */
605 } 628 /* /\* goto meta(context, RotateL); *\/ */
606 629 /* /\* } *\/ */
607 goto meta(context, DeleteCase6); 630
608 } 631 /* /\* goto meta(context, DeleteCase6); *\/ */
609 632 /* /\* } *\/ */
610 __code deleteCase5_stub(struct Context* context) { 633
611 goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); 634 /* /\* __code deleteCase5_stub(struct Context* context) { *\/ */
612 } 635 /* /\* goto deleteCase5(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
613 636 /* /\* } *\/ */
614 __code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) { 637
615 struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; 638 /* /\* __code deleteCase6(struct Context* context, struct Tree* tree, struct Node* current) { *\/ */
616 639 /* /\* struct Node* sibling = current == current->parent->left ? current->parent->right : current->parent->left; *\/ */
617 sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); 640
618 allocator(context); 641 /* /\* sibling == sibling->parent->left ? (sibling->parent->left = context->heap) : (sibling->parent->right = context->heap); *\/ */
619 struct Node* tmp = &context->data[context->dataNum]->node; 642 /* /\* allocator(context); *\/ */
620 *tmp = *sibling; 643 /* /\* struct Node* tmp = &context->data[context->dataNum]->node; *\/ */
621 tmp->parent = current; 644 /* /\* *tmp = *sibling; *\/ */
622 645 /* /\* tmp->parent = current; *\/ */
623 tmp->color = current->parent->color; 646
624 current->parent->color = Black; 647 /* /\* tmp->color = current->parent->color; *\/ */
625 648 /* /\* current->parent->color = Black; *\/ */
626 context->next = Delete3; 649
627 stack_push(context->code_stack, &context->next); 650 /* /\* context->next = Delete3; *\/ */
628 651 /* /\* stack_push(context->code_stack, &context->next); *\/ */
629 if (current == current->parent->left) { 652
630 tmp->right->color = Black; 653 /* /\* if (current == current->parent->left) { *\/ */
631 tree->current = current->parent; 654 /* /\* tmp->right->color = Black; *\/ */
632 655 /* /\* tree->current = current->parent; *\/ */
633 goto meta(context, RotateL); 656
634 } else { 657 /* /\* goto meta(context, RotateL); *\/ */
635 tmp->left->color = Black; 658 /* /\* } else { *\/ */
636 tree->current = current->parent; 659 /* /\* tmp->left->color = Black; *\/ */
637 660 /* /\* tree->current = current->parent; *\/ */
638 goto meta(context, RotateR); 661
639 } 662 /* /\* goto meta(context, RotateR); *\/ */
640 } 663 /* /\* } *\/ */
641 664 /* /\* } *\/ */
642 __code deleteCase6_stub(struct Context* context) { 665
643 goto deleteCase6(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); 666 /* /\* __code deleteCase6_stub(struct Context* context) { *\/ */
644 } 667 /* /\* goto deleteCase6(context, &context->data[Tree]->tree, context->data[Tree]->tree.current); *\/ */
668 /* /\* } *\/ */