rev |
line source |
nuclear@0
|
1 #include <stdio.h>
|
nuclear@0
|
2 #include <stdlib.h>
|
nuclear@0
|
3 #include <string.h>
|
nuclear@0
|
4 #include "rbtree.h"
|
nuclear@0
|
5
|
nuclear@0
|
6 #define INT2PTR(x) ((void*)(x))
|
nuclear@0
|
7 #define PTR2INT(x) ((int)(x))
|
nuclear@0
|
8
|
nuclear@0
|
9 struct rbtree {
|
nuclear@0
|
10 struct rbnode *root;
|
nuclear@0
|
11
|
nuclear@0
|
12 rb_alloc_func_t alloc;
|
nuclear@0
|
13 rb_free_func_t free;
|
nuclear@0
|
14
|
nuclear@0
|
15 rb_cmp_func_t cmp;
|
nuclear@0
|
16 rb_del_func_t del;
|
nuclear@0
|
17 void *del_cls;
|
nuclear@0
|
18
|
nuclear@0
|
19 struct rbnode *rstack, *iter;
|
nuclear@0
|
20 };
|
nuclear@0
|
21
|
nuclear@0
|
22 static int cmpaddr(void *ap, void *bp);
|
nuclear@0
|
23 static int cmpint(void *ap, void *bp);
|
nuclear@0
|
24
|
nuclear@0
|
25 static int count_nodes(struct rbnode *node);
|
nuclear@0
|
26 static void del_tree(struct rbnode *node, void (*delfunc)(struct rbnode*, void*), void *cls);
|
nuclear@0
|
27 static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data);
|
nuclear@0
|
28 static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key);
|
nuclear@3
|
29 /*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key);*/
|
nuclear@0
|
30 static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls);
|
nuclear@0
|
31
|
nuclear@0
|
32 struct rbtree *rb_create(rb_cmp_func_t cmp_func)
|
nuclear@0
|
33 {
|
nuclear@0
|
34 struct rbtree *rb;
|
nuclear@0
|
35
|
nuclear@0
|
36 if(!(rb = malloc(sizeof *rb))) {
|
nuclear@0
|
37 return 0;
|
nuclear@0
|
38 }
|
nuclear@0
|
39 if(rb_init(rb, cmp_func) == -1) {
|
nuclear@0
|
40 free(rb);
|
nuclear@0
|
41 return 0;
|
nuclear@0
|
42 }
|
nuclear@0
|
43 return rb;
|
nuclear@0
|
44 }
|
nuclear@0
|
45
|
nuclear@0
|
46 void rb_free(struct rbtree *rb)
|
nuclear@0
|
47 {
|
nuclear@0
|
48 rb_destroy(rb);
|
nuclear@0
|
49 free(rb);
|
nuclear@0
|
50 }
|
nuclear@0
|
51
|
nuclear@0
|
52
|
nuclear@0
|
53 int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func)
|
nuclear@0
|
54 {
|
nuclear@0
|
55 memset(rb, 0, sizeof *rb);
|
nuclear@0
|
56
|
nuclear@0
|
57 if(cmp_func == RB_KEY_INT) {
|
nuclear@0
|
58 rb->cmp = cmpint;
|
nuclear@0
|
59 } else if(cmp_func == RB_KEY_STRING) {
|
nuclear@0
|
60 rb->cmp = (rb_cmp_func_t)strcmp;
|
nuclear@0
|
61 } else {
|
nuclear@0
|
62 rb->cmp = cmpaddr;
|
nuclear@0
|
63 }
|
nuclear@0
|
64
|
nuclear@0
|
65 rb->alloc = malloc;
|
nuclear@0
|
66 rb->free = free;
|
nuclear@0
|
67 return 0;
|
nuclear@0
|
68 }
|
nuclear@0
|
69
|
nuclear@0
|
70 void rb_destroy(struct rbtree *rb)
|
nuclear@0
|
71 {
|
nuclear@0
|
72 del_tree(rb->root, rb->del, rb->del_cls);
|
nuclear@0
|
73 }
|
nuclear@0
|
74
|
nuclear@0
|
75 void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free)
|
nuclear@0
|
76 {
|
nuclear@0
|
77 rb->alloc = alloc;
|
nuclear@0
|
78 rb->free = free;
|
nuclear@0
|
79 }
|
nuclear@0
|
80
|
nuclear@0
|
81
|
nuclear@0
|
82 void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func)
|
nuclear@0
|
83 {
|
nuclear@0
|
84 rb->cmp = func;
|
nuclear@0
|
85 }
|
nuclear@0
|
86
|
nuclear@0
|
87 void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls)
|
nuclear@0
|
88 {
|
nuclear@0
|
89 rb->del = func;
|
nuclear@0
|
90 rb->del_cls = cls;
|
nuclear@0
|
91 }
|
nuclear@0
|
92
|
nuclear@0
|
93 int rb_size(struct rbtree *rb)
|
nuclear@0
|
94 {
|
nuclear@0
|
95 return count_nodes(rb->root);
|
nuclear@0
|
96 }
|
nuclear@0
|
97
|
nuclear@0
|
98 int rb_insert(struct rbtree *rb, void *key, void *data)
|
nuclear@0
|
99 {
|
nuclear@0
|
100 rb->root = insert(rb, rb->root, key, data);
|
nuclear@0
|
101 rb->root->red = 0;
|
nuclear@0
|
102 return 0;
|
nuclear@0
|
103 }
|
nuclear@0
|
104
|
nuclear@0
|
105 int rb_inserti(struct rbtree *rb, int key, void *data)
|
nuclear@0
|
106 {
|
nuclear@0
|
107 rb->root = insert(rb, rb->root, INT2PTR(key), data);
|
nuclear@0
|
108 rb->root->red = 0;
|
nuclear@0
|
109 return 0;
|
nuclear@0
|
110 }
|
nuclear@0
|
111
|
nuclear@0
|
112
|
nuclear@0
|
113 int rb_delete(struct rbtree *rb, void *key)
|
nuclear@0
|
114 {
|
nuclear@0
|
115 rb->root = delete(rb, rb->root, key);
|
nuclear@0
|
116 rb->root->red = 0;
|
nuclear@0
|
117 return 0;
|
nuclear@0
|
118 }
|
nuclear@0
|
119
|
nuclear@0
|
120 int rb_deletei(struct rbtree *rb, int key)
|
nuclear@0
|
121 {
|
nuclear@0
|
122 rb->root = delete(rb, rb->root, INT2PTR(key));
|
nuclear@0
|
123 rb->root->red = 0;
|
nuclear@0
|
124 return 0;
|
nuclear@0
|
125 }
|
nuclear@0
|
126
|
nuclear@0
|
127
|
nuclear@0
|
128 void *rb_find(struct rbtree *rb, void *key)
|
nuclear@0
|
129 {
|
nuclear@3
|
130 struct rbnode *node = rb->root;
|
nuclear@3
|
131
|
nuclear@3
|
132 while(node) {
|
nuclear@3
|
133 int cmp = rb->cmp(key, node->key);
|
nuclear@3
|
134 if(cmp == 0) {
|
nuclear@3
|
135 return node;
|
nuclear@3
|
136 }
|
nuclear@3
|
137 node = cmp < 0 ? node->left : node->right;
|
nuclear@3
|
138 }
|
nuclear@3
|
139 return 0;
|
nuclear@0
|
140 }
|
nuclear@0
|
141
|
nuclear@0
|
142 void *rb_findi(struct rbtree *rb, int key)
|
nuclear@0
|
143 {
|
nuclear@3
|
144 return rb_find(rb, INT2PTR(key));
|
nuclear@0
|
145 }
|
nuclear@0
|
146
|
nuclear@0
|
147
|
nuclear@0
|
148 void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls)
|
nuclear@0
|
149 {
|
nuclear@0
|
150 traverse(rb->root, func, cls);
|
nuclear@0
|
151 }
|
nuclear@0
|
152
|
nuclear@0
|
153
|
nuclear@0
|
154 struct rbnode *rb_root(struct rbtree *rb)
|
nuclear@0
|
155 {
|
nuclear@0
|
156 return rb->root;
|
nuclear@0
|
157 }
|
nuclear@0
|
158
|
nuclear@0
|
159 void rb_begin(struct rbtree *rb)
|
nuclear@0
|
160 {
|
nuclear@0
|
161 rb->rstack = 0;
|
nuclear@0
|
162 rb->iter = rb->root;
|
nuclear@0
|
163 }
|
nuclear@0
|
164
|
nuclear@0
|
165 #define push(sp, x) ((x)->next = (sp), (sp) = (x))
|
nuclear@0
|
166 #define pop(sp) ((sp) = (sp)->next)
|
nuclear@0
|
167 #define top(sp) (sp)
|
nuclear@0
|
168
|
nuclear@0
|
169 struct rbnode *rb_next(struct rbtree *rb)
|
nuclear@0
|
170 {
|
nuclear@0
|
171 struct rbnode *res = 0;
|
nuclear@0
|
172
|
nuclear@0
|
173 while(rb->rstack || rb->iter) {
|
nuclear@0
|
174 if(rb->iter) {
|
nuclear@0
|
175 push(rb->rstack, rb->iter);
|
nuclear@0
|
176 rb->iter = rb->iter->left;
|
nuclear@0
|
177 } else {
|
nuclear@0
|
178 rb->iter = top(rb->rstack);
|
nuclear@0
|
179 pop(rb->rstack);
|
nuclear@0
|
180 res = rb->iter;
|
nuclear@0
|
181 rb->iter = rb->iter->right;
|
nuclear@0
|
182 break;
|
nuclear@0
|
183 }
|
nuclear@0
|
184 }
|
nuclear@0
|
185 return res;
|
nuclear@0
|
186 }
|
nuclear@0
|
187
|
nuclear@0
|
188 void *rb_node_key(struct rbnode *node)
|
nuclear@0
|
189 {
|
nuclear@0
|
190 return node ? node->key : 0;
|
nuclear@0
|
191 }
|
nuclear@0
|
192
|
nuclear@0
|
193 int rb_node_keyi(struct rbnode *node)
|
nuclear@0
|
194 {
|
nuclear@0
|
195 return node ? PTR2INT(node->key) : 0;
|
nuclear@0
|
196 }
|
nuclear@0
|
197
|
nuclear@0
|
198 void *rb_node_data(struct rbnode *node)
|
nuclear@0
|
199 {
|
nuclear@0
|
200 return node ? node->data : 0;
|
nuclear@0
|
201 }
|
nuclear@0
|
202
|
nuclear@0
|
203 static int cmpaddr(void *ap, void *bp)
|
nuclear@0
|
204 {
|
nuclear@0
|
205 return ap < bp ? -1 : (ap > bp ? 1 : 0);
|
nuclear@0
|
206 }
|
nuclear@0
|
207
|
nuclear@0
|
208 static int cmpint(void *ap, void *bp)
|
nuclear@0
|
209 {
|
nuclear@0
|
210 return PTR2INT(ap) - PTR2INT(bp);
|
nuclear@0
|
211 }
|
nuclear@0
|
212
|
nuclear@0
|
213
|
nuclear@0
|
214 /* ---- left-leaning 2-3 red-black implementation ---- */
|
nuclear@0
|
215
|
nuclear@0
|
216 /* helper prototypes */
|
nuclear@0
|
217 static int is_red(struct rbnode *tree);
|
nuclear@0
|
218 static void color_flip(struct rbnode *tree);
|
nuclear@0
|
219 static struct rbnode *rot_left(struct rbnode *a);
|
nuclear@0
|
220 static struct rbnode *rot_right(struct rbnode *a);
|
nuclear@0
|
221 static struct rbnode *find_min(struct rbnode *tree);
|
nuclear@0
|
222 static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree);
|
nuclear@0
|
223 /*static struct rbnode *move_red_right(struct rbnode *tree);*/
|
nuclear@0
|
224 static struct rbnode *move_red_left(struct rbnode *tree);
|
nuclear@0
|
225 static struct rbnode *fix_up(struct rbnode *tree);
|
nuclear@0
|
226
|
nuclear@0
|
227 static int count_nodes(struct rbnode *node)
|
nuclear@0
|
228 {
|
nuclear@0
|
229 if(!node)
|
nuclear@0
|
230 return 0;
|
nuclear@0
|
231
|
nuclear@0
|
232 return 1 + count_nodes(node->left) + count_nodes(node->right);
|
nuclear@0
|
233 }
|
nuclear@0
|
234
|
nuclear@0
|
235 static void del_tree(struct rbnode *node, rb_del_func_t delfunc, void *cls)
|
nuclear@0
|
236 {
|
nuclear@0
|
237 if(!node)
|
nuclear@0
|
238 return;
|
nuclear@0
|
239
|
nuclear@0
|
240 del_tree(node->left, delfunc, cls);
|
nuclear@0
|
241 del_tree(node->right, delfunc, cls);
|
nuclear@0
|
242
|
nuclear@0
|
243 delfunc(node, cls);
|
nuclear@0
|
244 free(node);
|
nuclear@0
|
245 }
|
nuclear@0
|
246
|
nuclear@0
|
247 static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data)
|
nuclear@0
|
248 {
|
nuclear@0
|
249 int cmp;
|
nuclear@0
|
250
|
nuclear@0
|
251 if(!tree) {
|
nuclear@0
|
252 struct rbnode *node = rb->alloc(sizeof *node);
|
nuclear@0
|
253 node->red = 1;
|
nuclear@0
|
254 node->key = key;
|
nuclear@0
|
255 node->data = data;
|
nuclear@0
|
256 node->left = node->right = 0;
|
nuclear@0
|
257 return node;
|
nuclear@0
|
258 }
|
nuclear@0
|
259
|
nuclear@0
|
260 cmp = rb->cmp(key, tree->key);
|
nuclear@0
|
261
|
nuclear@0
|
262 if(cmp < 0) {
|
nuclear@0
|
263 tree->left = insert(rb, tree->left, key, data);
|
nuclear@0
|
264 } else if(cmp > 0) {
|
nuclear@0
|
265 tree->right = insert(rb, tree->right, key, data);
|
nuclear@0
|
266 } else {
|
nuclear@0
|
267 tree->data = data;
|
nuclear@0
|
268 }
|
nuclear@0
|
269
|
nuclear@0
|
270 /* fix right-leaning reds */
|
nuclear@0
|
271 if(is_red(tree->right)) {
|
nuclear@0
|
272 tree = rot_left(tree);
|
nuclear@0
|
273 }
|
nuclear@0
|
274 /* fix two reds in a row */
|
nuclear@0
|
275 if(is_red(tree->left) && is_red(tree->left->left)) {
|
nuclear@0
|
276 tree = rot_right(tree);
|
nuclear@0
|
277 }
|
nuclear@0
|
278
|
nuclear@0
|
279 /* if 4-node, split it by color inversion */
|
nuclear@0
|
280 if(is_red(tree->left) && is_red(tree->right)) {
|
nuclear@0
|
281 color_flip(tree);
|
nuclear@0
|
282 }
|
nuclear@0
|
283
|
nuclear@0
|
284 return tree;
|
nuclear@0
|
285 }
|
nuclear@0
|
286
|
nuclear@0
|
287 static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key)
|
nuclear@0
|
288 {
|
nuclear@0
|
289 int cmp;
|
nuclear@0
|
290
|
nuclear@0
|
291 if(!tree) {
|
nuclear@0
|
292 return 0;
|
nuclear@0
|
293 }
|
nuclear@0
|
294
|
nuclear@0
|
295 cmp = rb->cmp(key, tree->key);
|
nuclear@0
|
296
|
nuclear@0
|
297 if(cmp < 0) {
|
nuclear@0
|
298 if(!is_red(tree->left) && !is_red(tree->left->left)) {
|
nuclear@0
|
299 tree = move_red_left(tree);
|
nuclear@0
|
300 }
|
nuclear@0
|
301 tree->left = delete(rb, tree->left, key);
|
nuclear@0
|
302 } else {
|
nuclear@0
|
303 /* need reds on the right */
|
nuclear@0
|
304 if(is_red(tree->left)) {
|
nuclear@0
|
305 tree = rot_right(tree);
|
nuclear@0
|
306 }
|
nuclear@0
|
307
|
nuclear@0
|
308 /* found it at the bottom (XXX what certifies left is null?) */
|
nuclear@0
|
309 if(cmp == 0 && !tree->right) {
|
nuclear@0
|
310 if(rb->del) {
|
nuclear@0
|
311 rb->del(tree, rb->del_cls);
|
nuclear@0
|
312 }
|
nuclear@0
|
313 rb->free(tree);
|
nuclear@0
|
314 return 0;
|
nuclear@0
|
315 }
|
nuclear@0
|
316
|
nuclear@0
|
317 if(!is_red(tree->right) && !is_red(tree->right->left)) {
|
nuclear@0
|
318 tree = move_red_left(tree);
|
nuclear@0
|
319 }
|
nuclear@0
|
320
|
nuclear@0
|
321 if(key == tree->key) {
|
nuclear@0
|
322 struct rbnode *rmin = find_min(tree->right);
|
nuclear@0
|
323 tree->key = rmin->key;
|
nuclear@0
|
324 tree->data = rmin->data;
|
nuclear@0
|
325 tree->right = del_min(rb, tree->right);
|
nuclear@0
|
326 } else {
|
nuclear@0
|
327 tree->right = delete(rb, tree->right, key);
|
nuclear@0
|
328 }
|
nuclear@0
|
329 }
|
nuclear@0
|
330
|
nuclear@0
|
331 return fix_up(tree);
|
nuclear@0
|
332 }
|
nuclear@0
|
333
|
nuclear@3
|
334 /*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key)
|
nuclear@0
|
335 {
|
nuclear@0
|
336 int cmp;
|
nuclear@0
|
337
|
nuclear@0
|
338 if(!node)
|
nuclear@0
|
339 return 0;
|
nuclear@0
|
340
|
nuclear@0
|
341 if((cmp = rb->cmp(key, node->key)) == 0) {
|
nuclear@0
|
342 return node;
|
nuclear@0
|
343 }
|
nuclear@0
|
344 return find(rb, cmp < 0 ? node->left : node->right, key);
|
nuclear@3
|
345 }*/
|
nuclear@0
|
346
|
nuclear@0
|
347 static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls)
|
nuclear@0
|
348 {
|
nuclear@0
|
349 if(!node)
|
nuclear@0
|
350 return;
|
nuclear@0
|
351
|
nuclear@0
|
352 traverse(node->left, func, cls);
|
nuclear@0
|
353 func(node, cls);
|
nuclear@0
|
354 traverse(node->right, func, cls);
|
nuclear@0
|
355 }
|
nuclear@0
|
356
|
nuclear@0
|
357 /* helpers */
|
nuclear@0
|
358
|
nuclear@0
|
359 static int is_red(struct rbnode *tree)
|
nuclear@0
|
360 {
|
nuclear@0
|
361 return tree && tree->red;
|
nuclear@0
|
362 }
|
nuclear@0
|
363
|
nuclear@0
|
364 static void color_flip(struct rbnode *tree)
|
nuclear@0
|
365 {
|
nuclear@0
|
366 tree->red = !tree->red;
|
nuclear@0
|
367 tree->left->red = !tree->left->red;
|
nuclear@0
|
368 tree->right->red = !tree->right->red;
|
nuclear@0
|
369 }
|
nuclear@0
|
370
|
nuclear@0
|
371 static struct rbnode *rot_left(struct rbnode *a)
|
nuclear@0
|
372 {
|
nuclear@0
|
373 struct rbnode *b = a->right;
|
nuclear@0
|
374 a->right = b->left;
|
nuclear@0
|
375 b->left = a;
|
nuclear@0
|
376 b->red = a->red;
|
nuclear@0
|
377 a->red = 1;
|
nuclear@0
|
378 return b;
|
nuclear@0
|
379 }
|
nuclear@0
|
380
|
nuclear@0
|
381 static struct rbnode *rot_right(struct rbnode *a)
|
nuclear@0
|
382 {
|
nuclear@0
|
383 struct rbnode *b = a->left;
|
nuclear@0
|
384 a->left = b->right;
|
nuclear@0
|
385 b->right = a;
|
nuclear@0
|
386 b->red = a->red;
|
nuclear@0
|
387 a->red = 1;
|
nuclear@0
|
388 return b;
|
nuclear@0
|
389 }
|
nuclear@0
|
390
|
nuclear@0
|
391 static struct rbnode *find_min(struct rbnode *tree)
|
nuclear@0
|
392 {
|
nuclear@3
|
393 struct rbnode *node;
|
nuclear@3
|
394
|
nuclear@3
|
395 if(!tree)
|
nuclear@3
|
396 return 0;
|
nuclear@3
|
397
|
nuclear@3
|
398 while(node->left) {
|
nuclear@3
|
399 node = node->left;
|
nuclear@0
|
400 }
|
nuclear@3
|
401 return node;
|
nuclear@0
|
402 }
|
nuclear@0
|
403
|
nuclear@0
|
404 static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree)
|
nuclear@0
|
405 {
|
nuclear@0
|
406 if(!tree->left) {
|
nuclear@0
|
407 if(rb->del) {
|
nuclear@0
|
408 rb->del(tree->left, rb->del_cls);
|
nuclear@0
|
409 }
|
nuclear@0
|
410 rb->free(tree->left);
|
nuclear@0
|
411 return 0;
|
nuclear@0
|
412 }
|
nuclear@0
|
413
|
nuclear@0
|
414 /* make sure we've got red (3/4-nodes) at the left side so we can delete at the bottom */
|
nuclear@0
|
415 if(!is_red(tree->left) && !is_red(tree->left->left)) {
|
nuclear@0
|
416 tree = move_red_left(tree);
|
nuclear@0
|
417 }
|
nuclear@0
|
418 tree->left = del_min(rb, tree->left);
|
nuclear@0
|
419
|
nuclear@0
|
420 /* fix right-reds, red-reds, and split 4-nodes on the way up */
|
nuclear@0
|
421 return fix_up(tree);
|
nuclear@0
|
422 }
|
nuclear@0
|
423
|
nuclear@0
|
424 #if 0
|
nuclear@0
|
425 /* push a red link on this node to the right */
|
nuclear@0
|
426 static struct rbnode *move_red_right(struct rbnode *tree)
|
nuclear@0
|
427 {
|
nuclear@0
|
428 /* flipping it makes both children go red, so we have a red to the right */
|
nuclear@0
|
429 color_flip(tree);
|
nuclear@0
|
430
|
nuclear@0
|
431 /* if after the flip we've got a red-red situation to the left, fix it */
|
nuclear@0
|
432 if(is_red(tree->left->left)) {
|
nuclear@0
|
433 tree = rot_right(tree);
|
nuclear@0
|
434 color_flip(tree);
|
nuclear@0
|
435 }
|
nuclear@0
|
436 return tree;
|
nuclear@0
|
437 }
|
nuclear@0
|
438 #endif
|
nuclear@0
|
439
|
nuclear@0
|
440 /* push a red link on this node to the left */
|
nuclear@0
|
441 static struct rbnode *move_red_left(struct rbnode *tree)
|
nuclear@0
|
442 {
|
nuclear@0
|
443 /* flipping it makes both children go red, so we have a red to the left */
|
nuclear@0
|
444 color_flip(tree);
|
nuclear@0
|
445
|
nuclear@0
|
446 /* if after the flip we've got a red-red on the right-left, fix it */
|
nuclear@0
|
447 if(is_red(tree->right->left)) {
|
nuclear@0
|
448 tree->right = rot_right(tree->right);
|
nuclear@0
|
449 tree = rot_left(tree);
|
nuclear@0
|
450 color_flip(tree);
|
nuclear@0
|
451 }
|
nuclear@0
|
452 return tree;
|
nuclear@0
|
453 }
|
nuclear@0
|
454
|
nuclear@0
|
455 static struct rbnode *fix_up(struct rbnode *tree)
|
nuclear@0
|
456 {
|
nuclear@0
|
457 /* fix right-leaning */
|
nuclear@0
|
458 if(is_red(tree->right)) {
|
nuclear@0
|
459 tree = rot_left(tree);
|
nuclear@0
|
460 }
|
nuclear@0
|
461 /* change invalid red-red pairs into a proper 4-node */
|
nuclear@0
|
462 if(is_red(tree->left) && is_red(tree->left->left)) {
|
nuclear@0
|
463 tree = rot_right(tree);
|
nuclear@0
|
464 }
|
nuclear@0
|
465 /* split 4-nodes */
|
nuclear@0
|
466 if(is_red(tree->left) && is_red(tree->right)) {
|
nuclear@0
|
467 color_flip(tree);
|
nuclear@0
|
468 }
|
nuclear@0
|
469 return tree;
|
nuclear@0
|
470 }
|