Mercurial > hg > Members > innparusu > Gears

comparison src/llrb/llrb.c @ 81:dc6f665bb753

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