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