Mercurial > hg > Members > Moririn

comparison src/tmp/rb_tree.c @ 86:e06e1a9e569e parallel_execution

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