1 /*
2 * rbtree.c -- generic red black tree
3 *
4 * Copyright (c) 2001-2007, NLnet Labs. All rights reserved.
5 *
6 * This software is open source.
7 *
8 * Redistribution and use in source and binary forms, with or without
9 * modification, are permitted provided that the following conditions
10 * are met:
11 *
12 * Redistributions of source code must retain the above copyright notice,
13 * this list of conditions and the following disclaimer.
14 *
15 * Redistributions in binary form must reproduce the above copyright notice,
16 * this list of conditions and the following disclaimer in the documentation
17 * and/or other materials provided with the distribution.
18 *
19 * Neither the name of the NLNET LABS nor the names of its contributors may
20 * be used to endorse or promote products derived from this software without
21 * specific prior written permission.
22 *
23 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27 * HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
29 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 *
35 */
36
37 /**
38 * \file
39 * Implementation of a redblack tree.
40 */
41
42 #include "config.h"
43 #include "log.h"
44 #include "fptr_wlist.h"
45 #include "util/rbtree.h"
46
47 /** Node colour black */
48 #define BLACK 0
49 /** Node colour red */
50 #define RED 1
51
52 /** the NULL node, global alloc */
53 rbnode_type rbtree_null_node = {
54 RBTREE_NULL, /* Parent. */
55 RBTREE_NULL, /* Left. */
56 RBTREE_NULL, /* Right. */
57 NULL, /* Key. */
58 BLACK /* Color. */
59 };
60
61 /** rotate subtree left (to preserve redblack property) */
62 static void rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node);
63 /** rotate subtree right (to preserve redblack property) */
64 static void rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node);
65 /** Fixup node colours when insert happened */
66 static void rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node);
67 /** Fixup node colours when delete happened */
68 static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child,
69 rbnode_type* child_parent);
70
71 /*
72 * Creates a new red black tree, initializes and returns a pointer to it.
73 *
74 * Return NULL on failure.
75 *
76 */
77 rbtree_type *
rbtree_create(int (* cmpf)(const void *,const void *))78 rbtree_create (int (*cmpf)(const void *, const void *))
79 {
80 rbtree_type *rbtree;
81
82 /* Allocate memory for it */
83 rbtree = (rbtree_type *) malloc(sizeof(rbtree_type));
84 if (!rbtree) {
85 return NULL;
86 }
87
88 /* Initialize it */
89 rbtree_init(rbtree, cmpf);
90
91 return rbtree;
92 }
93
94 void
rbtree_init(rbtree_type * rbtree,int (* cmpf)(const void *,const void *))95 rbtree_init(rbtree_type *rbtree, int (*cmpf)(const void *, const void *))
96 {
97 /* Initialize it */
98 rbtree->root = RBTREE_NULL;
99 rbtree->count = 0;
100 rbtree->cmp = cmpf;
101 }
102
103 /*
104 * Rotates the node to the left.
105 *
106 */
107 static void
rbtree_rotate_left(rbtree_type * rbtree,rbnode_type * node)108 rbtree_rotate_left(rbtree_type *rbtree, rbnode_type *node)
109 {
110 rbnode_type *right = node->right;
111 node->right = right->left;
112 if (right->left != RBTREE_NULL)
113 right->left->parent = node;
114
115 right->parent = node->parent;
116
117 if (node->parent != RBTREE_NULL) {
118 if (node == node->parent->left) {
119 node->parent->left = right;
120 } else {
121 node->parent->right = right;
122 }
123 } else {
124 rbtree->root = right;
125 }
126 right->left = node;
127 node->parent = right;
128 }
129
130 /*
131 * Rotates the node to the right.
132 *
133 */
134 static void
rbtree_rotate_right(rbtree_type * rbtree,rbnode_type * node)135 rbtree_rotate_right(rbtree_type *rbtree, rbnode_type *node)
136 {
137 rbnode_type *left = node->left;
138 node->left = left->right;
139 if (left->right != RBTREE_NULL)
140 left->right->parent = node;
141
142 left->parent = node->parent;
143
144 if (node->parent != RBTREE_NULL) {
145 if (node == node->parent->right) {
146 node->parent->right = left;
147 } else {
148 node->parent->left = left;
149 }
150 } else {
151 rbtree->root = left;
152 }
153 left->right = node;
154 node->parent = left;
155 }
156
157 static void
rbtree_insert_fixup(rbtree_type * rbtree,rbnode_type * node)158 rbtree_insert_fixup(rbtree_type *rbtree, rbnode_type *node)
159 {
160 rbnode_type *uncle;
161
162 /* While not at the root and need fixing... */
163 while (node != rbtree->root && node->parent->color == RED) {
164 /* If our parent is left child of our grandparent... */
165 if (node->parent == node->parent->parent->left) {
166 uncle = node->parent->parent->right;
167
168 /* If our uncle is red... */
169 if (uncle->color == RED) {
170 /* Paint the parent and the uncle black... */
171 node->parent->color = BLACK;
172 uncle->color = BLACK;
173
174 /* And the grandparent red... */
175 node->parent->parent->color = RED;
176
177 /* And continue fixing the grandparent */
178 node = node->parent->parent;
179 } else { /* Our uncle is black... */
180 /* Are we the right child? */
181 if (node == node->parent->right) {
182 node = node->parent;
183 rbtree_rotate_left(rbtree, node);
184 }
185 /* Now we're the left child, repaint and rotate... */
186 node->parent->color = BLACK;
187 node->parent->parent->color = RED;
188 rbtree_rotate_right(rbtree, node->parent->parent);
189 }
190 } else {
191 uncle = node->parent->parent->left;
192
193 /* If our uncle is red... */
194 if (uncle->color == RED) {
195 /* Paint the parent and the uncle black... */
196 node->parent->color = BLACK;
197 uncle->color = BLACK;
198
199 /* And the grandparent red... */
200 node->parent->parent->color = RED;
201
202 /* And continue fixing the grandparent */
203 node = node->parent->parent;
204 } else { /* Our uncle is black... */
205 /* Are we the right child? */
206 if (node == node->parent->left) {
207 node = node->parent;
208 rbtree_rotate_right(rbtree, node);
209 }
210 /* Now we're the right child, repaint and rotate... */
211 node->parent->color = BLACK;
212 node->parent->parent->color = RED;
213 rbtree_rotate_left(rbtree, node->parent->parent);
214 }
215 }
216 }
217 rbtree->root->color = BLACK;
218 }
219
220
221 /*
222 * Inserts a node into a red black tree.
223 *
224 * Returns NULL on failure or the pointer to the newly added node
225 * otherwise.
226 */
227 rbnode_type *
rbtree_insert(rbtree_type * rbtree,rbnode_type * data)228 rbtree_insert (rbtree_type *rbtree, rbnode_type *data)
229 {
230 /* XXX Not necessary, but keeps compiler quiet... */
231 int r = 0;
232
233 /* We start at the root of the tree */
234 rbnode_type *node = rbtree->root;
235 rbnode_type *parent = RBTREE_NULL;
236
237 fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp));
238 /* Lets find the new parent... */
239 while (node != RBTREE_NULL) {
240 /* Compare two keys, do we have a duplicate? */
241 if ((r = rbtree->cmp(data->key, node->key)) == 0) {
242 return NULL;
243 }
244 parent = node;
245
246 if (r < 0) {
247 node = node->left;
248 } else {
249 node = node->right;
250 }
251 }
252
253 /* Initialize the new node */
254 data->parent = parent;
255 data->left = data->right = RBTREE_NULL;
256 data->color = RED;
257 rbtree->count++;
258
259 /* Insert it into the tree... */
260 if (parent != RBTREE_NULL) {
261 if (r < 0) {
262 parent->left = data;
263 } else {
264 parent->right = data;
265 }
266 } else {
267 rbtree->root = data;
268 }
269
270 /* Fix up the red-black properties... */
271 rbtree_insert_fixup(rbtree, data);
272
273 return data;
274 }
275
276 /*
277 * Searches the red black tree, returns the data if key is found or NULL otherwise.
278 *
279 */
280 rbnode_type *
rbtree_search(rbtree_type * rbtree,const void * key)281 rbtree_search (rbtree_type *rbtree, const void *key)
282 {
283 rbnode_type *node;
284
285 if (rbtree_find_less_equal(rbtree, key, &node)) {
286 return node;
287 } else {
288 return NULL;
289 }
290 }
291
292 /** helpers for delete: swap node colours */
swap_int8(uint8_t * x,uint8_t * y)293 static void swap_int8(uint8_t* x, uint8_t* y)
294 {
295 uint8_t t = *x; *x = *y; *y = t;
296 }
297
298 /** helpers for delete: swap node pointers */
swap_np(rbnode_type ** x,rbnode_type ** y)299 static void swap_np(rbnode_type** x, rbnode_type** y)
300 {
301 rbnode_type* t = *x; *x = *y; *y = t;
302 }
303
304 /** Update parent pointers of child trees of 'parent' */
change_parent_ptr(rbtree_type * rbtree,rbnode_type * parent,rbnode_type * old,rbnode_type * new)305 static void change_parent_ptr(rbtree_type* rbtree, rbnode_type* parent,
306 rbnode_type* old, rbnode_type* new)
307 {
308 if(parent == RBTREE_NULL)
309 {
310 log_assert(rbtree->root == old);
311 if(rbtree->root == old) rbtree->root = new;
312 return;
313 }
314 log_assert(parent->left == old || parent->right == old
315 || parent->left == new || parent->right == new);
316 if(parent->left == old) parent->left = new;
317 if(parent->right == old) parent->right = new;
318 }
319 /** Update parent pointer of a node 'child' */
change_child_ptr(rbnode_type * child,rbnode_type * old,rbnode_type * new)320 static void change_child_ptr(rbnode_type* child, rbnode_type* old,
321 rbnode_type* new)
322 {
323 if(child == RBTREE_NULL) return;
324 log_assert(child->parent == old || child->parent == new);
325 if(child->parent == old) child->parent = new;
326 }
327
328 rbnode_type*
rbtree_delete(rbtree_type * rbtree,const void * key)329 rbtree_delete(rbtree_type *rbtree, const void *key)
330 {
331 rbnode_type *to_delete;
332 rbnode_type *child;
333 if((to_delete = rbtree_search(rbtree, key)) == 0) return 0;
334 rbtree->count--;
335
336 /* make sure we have at most one non-leaf child */
337 if(to_delete->left != RBTREE_NULL && to_delete->right != RBTREE_NULL)
338 {
339 /* swap with smallest from right subtree (or largest from left) */
340 rbnode_type *smright = to_delete->right;
341 while(smright->left != RBTREE_NULL)
342 smright = smright->left;
343 /* swap the smright and to_delete elements in the tree,
344 * but the rbnode_type is first part of user data struct
345 * so cannot just swap the keys and data pointers. Instead
346 * readjust the pointers left,right,parent */
347
348 /* swap colors - colors are tied to the position in the tree */
349 swap_int8(&to_delete->color, &smright->color);
350
351 /* swap child pointers in parents of smright/to_delete */
352 change_parent_ptr(rbtree, to_delete->parent, to_delete, smright);
353 if(to_delete->right != smright)
354 change_parent_ptr(rbtree, smright->parent, smright, to_delete);
355
356 /* swap parent pointers in children of smright/to_delete */
357 change_child_ptr(smright->left, smright, to_delete);
358 change_child_ptr(smright->left, smright, to_delete);
359 change_child_ptr(smright->right, smright, to_delete);
360 change_child_ptr(smright->right, smright, to_delete);
361 change_child_ptr(to_delete->left, to_delete, smright);
362 if(to_delete->right != smright)
363 change_child_ptr(to_delete->right, to_delete, smright);
364 if(to_delete->right == smright)
365 {
366 /* set up so after swap they work */
367 to_delete->right = to_delete;
368 smright->parent = smright;
369 }
370
371 /* swap pointers in to_delete/smright nodes */
372 swap_np(&to_delete->parent, &smright->parent);
373 swap_np(&to_delete->left, &smright->left);
374 swap_np(&to_delete->right, &smright->right);
375
376 /* now delete to_delete (which is at the location where the smright previously was) */
377 }
378 log_assert(to_delete->left == RBTREE_NULL || to_delete->right == RBTREE_NULL);
379
380 if(to_delete->left != RBTREE_NULL) child = to_delete->left;
381 else child = to_delete->right;
382
383 /* unlink to_delete from the tree, replace to_delete with child */
384 change_parent_ptr(rbtree, to_delete->parent, to_delete, child);
385 change_child_ptr(child, to_delete, to_delete->parent);
386
387 if(to_delete->color == RED)
388 {
389 /* if node is red then the child (black) can be swapped in */
390 }
391 else if(child->color == RED)
392 {
393 /* change child to BLACK, removing a RED node is no problem */
394 if(child!=RBTREE_NULL) child->color = BLACK;
395 }
396 else rbtree_delete_fixup(rbtree, child, to_delete->parent);
397
398 /* unlink completely */
399 to_delete->parent = RBTREE_NULL;
400 to_delete->left = RBTREE_NULL;
401 to_delete->right = RBTREE_NULL;
402 to_delete->color = BLACK;
403 return to_delete;
404 }
405
rbtree_delete_fixup(rbtree_type * rbtree,rbnode_type * child,rbnode_type * child_parent)406 static void rbtree_delete_fixup(rbtree_type* rbtree, rbnode_type* child,
407 rbnode_type* child_parent)
408 {
409 rbnode_type* sibling;
410 int go_up = 1;
411
412 /* determine sibling to the node that is one-black short */
413 if(child_parent->right == child) sibling = child_parent->left;
414 else sibling = child_parent->right;
415
416 while(go_up)
417 {
418 if(child_parent == RBTREE_NULL)
419 {
420 /* removed parent==black from root, every path, so ok */
421 return;
422 }
423
424 if(sibling->color == RED)
425 { /* rotate to get a black sibling */
426 child_parent->color = RED;
427 sibling->color = BLACK;
428 if(child_parent->right == child)
429 rbtree_rotate_right(rbtree, child_parent);
430 else rbtree_rotate_left(rbtree, child_parent);
431 /* new sibling after rotation */
432 if(child_parent->right == child) sibling = child_parent->left;
433 else sibling = child_parent->right;
434 }
435
436 if(child_parent->color == BLACK
437 && sibling->color == BLACK
438 && sibling->left->color == BLACK
439 && sibling->right->color == BLACK)
440 { /* fixup local with recolor of sibling */
441 if(sibling != RBTREE_NULL)
442 sibling->color = RED;
443
444 child = child_parent;
445 child_parent = child_parent->parent;
446 /* prepare to go up, new sibling */
447 if(child_parent->right == child) sibling = child_parent->left;
448 else sibling = child_parent->right;
449 }
450 else go_up = 0;
451 }
452
453 if(child_parent->color == RED
454 && sibling->color == BLACK
455 && sibling->left->color == BLACK
456 && sibling->right->color == BLACK)
457 {
458 /* move red to sibling to rebalance */
459 if(sibling != RBTREE_NULL)
460 sibling->color = RED;
461 child_parent->color = BLACK;
462 return;
463 }
464 log_assert(sibling != RBTREE_NULL);
465
466 /* get a new sibling, by rotating at sibling. See which child
467 of sibling is red */
468 if(child_parent->right == child
469 && sibling->color == BLACK
470 && sibling->right->color == RED
471 && sibling->left->color == BLACK)
472 {
473 sibling->color = RED;
474 sibling->right->color = BLACK;
475 rbtree_rotate_left(rbtree, sibling);
476 /* new sibling after rotation */
477 if(child_parent->right == child) sibling = child_parent->left;
478 else sibling = child_parent->right;
479 }
480 else if(child_parent->left == child
481 && sibling->color == BLACK
482 && sibling->left->color == RED
483 && sibling->right->color == BLACK)
484 {
485 sibling->color = RED;
486 sibling->left->color = BLACK;
487 rbtree_rotate_right(rbtree, sibling);
488 /* new sibling after rotation */
489 if(child_parent->right == child) sibling = child_parent->left;
490 else sibling = child_parent->right;
491 }
492
493 /* now we have a black sibling with a red child. rotate and exchange colors. */
494 sibling->color = child_parent->color;
495 child_parent->color = BLACK;
496 if(child_parent->right == child)
497 {
498 log_assert(sibling->left->color == RED);
499 sibling->left->color = BLACK;
500 rbtree_rotate_right(rbtree, child_parent);
501 }
502 else
503 {
504 log_assert(sibling->right->color == RED);
505 sibling->right->color = BLACK;
506 rbtree_rotate_left(rbtree, child_parent);
507 }
508 }
509
510 int
rbtree_find_less_equal(rbtree_type * rbtree,const void * key,rbnode_type ** result)511 rbtree_find_less_equal(rbtree_type *rbtree, const void *key,
512 rbnode_type **result)
513 {
514 int r;
515 rbnode_type *node;
516
517 log_assert(result);
518
519 /* We start at root... */
520 node = rbtree->root;
521
522 *result = NULL;
523 fptr_ok(fptr_whitelist_rbtree_cmp(rbtree->cmp));
524
525 /* While there are children... */
526 while (node != RBTREE_NULL) {
527 r = rbtree->cmp(key, node->key);
528 if (r == 0) {
529 /* Exact match */
530 *result = node;
531 return 1;
532 }
533 if (r < 0) {
534 node = node->left;
535 } else {
536 /* Temporary match */
537 *result = node;
538 node = node->right;
539 }
540 }
541 return 0;
542 }
543
544 /*
545 * Finds the first element in the red black tree
546 *
547 */
548 rbnode_type *
rbtree_first(rbtree_type * rbtree)549 rbtree_first (rbtree_type *rbtree)
550 {
551 rbnode_type *node;
552
553 for (node = rbtree->root; node->left != RBTREE_NULL; node = node->left);
554 return node;
555 }
556
557 rbnode_type *
rbtree_last(rbtree_type * rbtree)558 rbtree_last (rbtree_type *rbtree)
559 {
560 rbnode_type *node;
561
562 for (node = rbtree->root; node->right != RBTREE_NULL; node = node->right);
563 return node;
564 }
565
566 /*
567 * Returns the next node...
568 *
569 */
570 rbnode_type *
rbtree_next(rbnode_type * node)571 rbtree_next (rbnode_type *node)
572 {
573 rbnode_type *parent;
574
575 if (node->right != RBTREE_NULL) {
576 /* One right, then keep on going left... */
577 for (node = node->right; node->left != RBTREE_NULL; node = node->left);
578 } else {
579 parent = node->parent;
580 while (parent != RBTREE_NULL && node == parent->right) {
581 node = parent;
582 parent = parent->parent;
583 }
584 node = parent;
585 }
586 return node;
587 }
588
589 rbnode_type *
rbtree_previous(rbnode_type * node)590 rbtree_previous(rbnode_type *node)
591 {
592 rbnode_type *parent;
593
594 if (node->left != RBTREE_NULL) {
595 /* One left, then keep on going right... */
596 for (node = node->left; node->right != RBTREE_NULL; node = node->right);
597 } else {
598 parent = node->parent;
599 while (parent != RBTREE_NULL && node == parent->left) {
600 node = parent;
601 parent = parent->parent;
602 }
603 node = parent;
604 }
605 return node;
606 }
607
608 /** recursive descent traverse */
609 static void
traverse_post(void (* func)(rbnode_type *,void *),void * arg,rbnode_type * node)610 traverse_post(void (*func)(rbnode_type*, void*), void* arg, rbnode_type* node)
611 {
612 if(!node || node == RBTREE_NULL)
613 return;
614 /* recurse */
615 traverse_post(func, arg, node->left);
616 traverse_post(func, arg, node->right);
617 /* call user func */
618 (*func)(node, arg);
619 }
620
621 void
traverse_postorder(rbtree_type * tree,void (* func)(rbnode_type *,void *),void * arg)622 traverse_postorder(rbtree_type* tree, void (*func)(rbnode_type*, void*),
623 void* arg)
624 {
625 traverse_post(func, arg, tree->root);
626 }
627