2 * rbtree.c -- generic red black tree
4 * Taken from Unbound, modified for ldns
6 * Copyright (c) 2001-2008, NLnet Labs. All rights reserved.
8 * This software is open source.
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
14 * Redistributions of source code must retain the above copyright notice,
15 * this list of conditions and the following disclaimer.
17 * Redistributions in binary form must reproduce the above copyright notice,
18 * this list of conditions and the following disclaimer in the documentation
19 * and/or other materials provided with the distribution.
21 * Neither the name of the NLNET LABS nor the names of its contributors may
22 * be used to endorse or promote products derived from this software without
23 * specific prior written permission.
25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
27 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
28 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE
29 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
30 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
31 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
32 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
33 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
34 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
35 * POSSIBILITY OF SUCH DAMAGE.
41 * Implementation of a redblack tree.
44 #include <ldns/config.h>
45 #include <ldns/rbtree.h>
48 /** Node colour black */
50 /** Node colour red */
53 /** the NULL node, global alloc */
54 ldns_rbnode_t ldns_rbtree_null_node
= {
55 LDNS_RBTREE_NULL
, /* Parent. */
56 LDNS_RBTREE_NULL
, /* Left. */
57 LDNS_RBTREE_NULL
, /* Right. */
63 /** rotate subtree left (to preserve redblack property) */
64 static void ldns_rbtree_rotate_left(ldns_rbtree_t
*rbtree
, ldns_rbnode_t
*node
);
65 /** rotate subtree right (to preserve redblack property) */
66 static void ldns_rbtree_rotate_right(ldns_rbtree_t
*rbtree
, ldns_rbnode_t
*node
);
67 /** Fixup node colours when insert happened */
68 static void ldns_rbtree_insert_fixup(ldns_rbtree_t
*rbtree
, ldns_rbnode_t
*node
);
69 /** Fixup node colours when delete happened */
70 static void ldns_rbtree_delete_fixup(ldns_rbtree_t
* rbtree
, ldns_rbnode_t
* child
, ldns_rbnode_t
* child_parent
);
73 * Creates a new red black tree, intializes and returns a pointer to it.
75 * Return NULL on failure.
79 ldns_rbtree_create (int (*cmpf
)(const void *, const void *))
81 ldns_rbtree_t
*rbtree
;
83 /* Allocate memory for it */
84 rbtree
= (ldns_rbtree_t
*) malloc(sizeof(ldns_rbtree_t
));
90 ldns_rbtree_init(rbtree
, cmpf
);
96 ldns_rbtree_init(ldns_rbtree_t
*rbtree
, int (*cmpf
)(const void *, const void *))
99 rbtree
->root
= LDNS_RBTREE_NULL
;
105 ldns_rbtree_free(ldns_rbtree_t
*rbtree
)
111 * Rotates the node to the left.
115 ldns_rbtree_rotate_left(ldns_rbtree_t
*rbtree
, ldns_rbnode_t
*node
)
117 ldns_rbnode_t
*right
= node
->right
;
118 node
->right
= right
->left
;
119 if (right
->left
!= LDNS_RBTREE_NULL
)
120 right
->left
->parent
= node
;
122 right
->parent
= node
->parent
;
124 if (node
->parent
!= LDNS_RBTREE_NULL
) {
125 if (node
== node
->parent
->left
) {
126 node
->parent
->left
= right
;
128 node
->parent
->right
= right
;
131 rbtree
->root
= right
;
134 node
->parent
= right
;
138 * Rotates the node to the right.
142 ldns_rbtree_rotate_right(ldns_rbtree_t
*rbtree
, ldns_rbnode_t
*node
)
144 ldns_rbnode_t
*left
= node
->left
;
145 node
->left
= left
->right
;
146 if (left
->right
!= LDNS_RBTREE_NULL
)
147 left
->right
->parent
= node
;
149 left
->parent
= node
->parent
;
151 if (node
->parent
!= LDNS_RBTREE_NULL
) {
152 if (node
== node
->parent
->right
) {
153 node
->parent
->right
= left
;
155 node
->parent
->left
= left
;
165 ldns_rbtree_insert_fixup(ldns_rbtree_t
*rbtree
, ldns_rbnode_t
*node
)
167 ldns_rbnode_t
*uncle
;
169 /* While not at the root and need fixing... */
170 while (node
!= rbtree
->root
&& node
->parent
->color
== RED
) {
171 /* If our parent is left child of our grandparent... */
172 if (node
->parent
== node
->parent
->parent
->left
) {
173 uncle
= node
->parent
->parent
->right
;
175 /* If our uncle is red... */
176 if (uncle
->color
== RED
) {
177 /* Paint the parent and the uncle black... */
178 node
->parent
->color
= BLACK
;
179 uncle
->color
= BLACK
;
181 /* And the grandparent red... */
182 node
->parent
->parent
->color
= RED
;
184 /* And continue fixing the grandparent */
185 node
= node
->parent
->parent
;
186 } else { /* Our uncle is black... */
187 /* Are we the right child? */
188 if (node
== node
->parent
->right
) {
190 ldns_rbtree_rotate_left(rbtree
, node
);
192 /* Now we're the left child, repaint and rotate... */
193 node
->parent
->color
= BLACK
;
194 node
->parent
->parent
->color
= RED
;
195 ldns_rbtree_rotate_right(rbtree
, node
->parent
->parent
);
198 uncle
= node
->parent
->parent
->left
;
200 /* If our uncle is red... */
201 if (uncle
->color
== RED
) {
202 /* Paint the parent and the uncle black... */
203 node
->parent
->color
= BLACK
;
204 uncle
->color
= BLACK
;
206 /* And the grandparent red... */
207 node
->parent
->parent
->color
= RED
;
209 /* And continue fixing the grandparent */
210 node
= node
->parent
->parent
;
211 } else { /* Our uncle is black... */
212 /* Are we the right child? */
213 if (node
== node
->parent
->left
) {
215 ldns_rbtree_rotate_right(rbtree
, node
);
217 /* Now we're the right child, repaint and rotate... */
218 node
->parent
->color
= BLACK
;
219 node
->parent
->parent
->color
= RED
;
220 ldns_rbtree_rotate_left(rbtree
, node
->parent
->parent
);
224 rbtree
->root
->color
= BLACK
;
228 ldns_rbtree_insert_vref(ldns_rbnode_t
*data
, void *rbtree
)
230 (void) ldns_rbtree_insert((ldns_rbtree_t
*) rbtree
,
235 * Inserts a node into a red black tree.
237 * Returns NULL on failure or the pointer to the newly added node
241 ldns_rbtree_insert (ldns_rbtree_t
*rbtree
, ldns_rbnode_t
*data
)
243 /* XXX Not necessary, but keeps compiler quiet... */
246 /* We start at the root of the tree */
247 ldns_rbnode_t
*node
= rbtree
->root
;
248 ldns_rbnode_t
*parent
= LDNS_RBTREE_NULL
;
250 /* Lets find the new parent... */
251 while (node
!= LDNS_RBTREE_NULL
) {
252 /* Compare two keys, do we have a duplicate? */
253 if ((r
= rbtree
->cmp(data
->key
, node
->key
)) == 0) {
265 /* Initialize the new node */
266 data
->parent
= parent
;
267 data
->left
= data
->right
= LDNS_RBTREE_NULL
;
271 /* Insert it into the tree... */
272 if (parent
!= LDNS_RBTREE_NULL
) {
276 parent
->right
= data
;
282 /* Fix up the red-black properties... */
283 ldns_rbtree_insert_fixup(rbtree
, data
);
289 * Searches the red black tree, returns the data if key is found or NULL otherwise.
293 ldns_rbtree_search (ldns_rbtree_t
*rbtree
, const void *key
)
297 if (ldns_rbtree_find_less_equal(rbtree
, key
, &node
)) {
304 /** helpers for delete: swap node colours */
305 static void swap_int8(uint8_t* x
, uint8_t* y
)
307 uint8_t t
= *x
; *x
= *y
; *y
= t
;
310 /** helpers for delete: swap node pointers */
311 static void swap_np(ldns_rbnode_t
** x
, ldns_rbnode_t
** y
)
313 ldns_rbnode_t
* t
= *x
; *x
= *y
; *y
= t
;
316 /** Update parent pointers of child trees of 'parent' */
317 static void change_parent_ptr(ldns_rbtree_t
* rbtree
, ldns_rbnode_t
* parent
, ldns_rbnode_t
* old
, ldns_rbnode_t
* new)
319 if(parent
== LDNS_RBTREE_NULL
)
321 if(rbtree
->root
== old
) rbtree
->root
= new;
324 if(parent
->left
== old
) parent
->left
= new;
325 if(parent
->right
== old
) parent
->right
= new;
327 /** Update parent pointer of a node 'child' */
328 static void change_child_ptr(ldns_rbnode_t
* child
, ldns_rbnode_t
* old
, ldns_rbnode_t
* new)
330 if(child
== LDNS_RBTREE_NULL
) return;
331 if(child
->parent
== old
) child
->parent
= new;
335 ldns_rbtree_delete(ldns_rbtree_t
*rbtree
, const void *key
)
337 ldns_rbnode_t
*to_delete
;
338 ldns_rbnode_t
*child
;
339 if((to_delete
= ldns_rbtree_search(rbtree
, key
)) == 0) return 0;
342 /* make sure we have at most one non-leaf child */
343 if(to_delete
->left
!= LDNS_RBTREE_NULL
&&
344 to_delete
->right
!= LDNS_RBTREE_NULL
)
346 /* swap with smallest from right subtree (or largest from left) */
347 ldns_rbnode_t
*smright
= to_delete
->right
;
348 while(smright
->left
!= LDNS_RBTREE_NULL
)
349 smright
= smright
->left
;
350 /* swap the smright and to_delete elements in the tree,
351 * but the ldns_rbnode_t is first part of user data struct
352 * so cannot just swap the keys and data pointers. Instead
353 * readjust the pointers left,right,parent */
355 /* swap colors - colors are tied to the position in the tree */
356 swap_int8(&to_delete
->color
, &smright
->color
);
358 /* swap child pointers in parents of smright/to_delete */
359 change_parent_ptr(rbtree
, to_delete
->parent
, to_delete
, smright
);
360 if(to_delete
->right
!= smright
)
361 change_parent_ptr(rbtree
, smright
->parent
, smright
, to_delete
);
363 /* swap parent pointers in children of smright/to_delete */
364 change_child_ptr(smright
->left
, smright
, to_delete
);
365 change_child_ptr(smright
->left
, smright
, to_delete
);
366 change_child_ptr(smright
->right
, smright
, to_delete
);
367 change_child_ptr(smright
->right
, smright
, to_delete
);
368 change_child_ptr(to_delete
->left
, to_delete
, smright
);
369 if(to_delete
->right
!= smright
)
370 change_child_ptr(to_delete
->right
, to_delete
, smright
);
371 if(to_delete
->right
== smright
)
373 /* set up so after swap they work */
374 to_delete
->right
= to_delete
;
375 smright
->parent
= smright
;
378 /* swap pointers in to_delete/smright nodes */
379 swap_np(&to_delete
->parent
, &smright
->parent
);
380 swap_np(&to_delete
->left
, &smright
->left
);
381 swap_np(&to_delete
->right
, &smright
->right
);
383 /* now delete to_delete (which is at the location where the smright previously was) */
386 if(to_delete
->left
!= LDNS_RBTREE_NULL
) child
= to_delete
->left
;
387 else child
= to_delete
->right
;
389 /* unlink to_delete from the tree, replace to_delete with child */
390 change_parent_ptr(rbtree
, to_delete
->parent
, to_delete
, child
);
391 change_child_ptr(child
, to_delete
, to_delete
->parent
);
393 if(to_delete
->color
== RED
)
395 /* if node is red then the child (black) can be swapped in */
397 else if(child
->color
== RED
)
399 /* change child to BLACK, removing a RED node is no problem */
400 if(child
!=LDNS_RBTREE_NULL
) child
->color
= BLACK
;
402 else ldns_rbtree_delete_fixup(rbtree
, child
, to_delete
->parent
);
404 /* unlink completely */
405 to_delete
->parent
= LDNS_RBTREE_NULL
;
406 to_delete
->left
= LDNS_RBTREE_NULL
;
407 to_delete
->right
= LDNS_RBTREE_NULL
;
408 to_delete
->color
= BLACK
;
412 static void ldns_rbtree_delete_fixup(ldns_rbtree_t
* rbtree
, ldns_rbnode_t
* child
, ldns_rbnode_t
* child_parent
)
414 ldns_rbnode_t
* sibling
;
417 /* determine sibling to the node that is one-black short */
418 if(child_parent
->right
== child
) sibling
= child_parent
->left
;
419 else sibling
= child_parent
->right
;
423 if(child_parent
== LDNS_RBTREE_NULL
)
425 /* removed parent==black from root, every path, so ok */
429 if(sibling
->color
== RED
)
430 { /* rotate to get a black sibling */
431 child_parent
->color
= RED
;
432 sibling
->color
= BLACK
;
433 if(child_parent
->right
== child
)
434 ldns_rbtree_rotate_right(rbtree
, child_parent
);
435 else ldns_rbtree_rotate_left(rbtree
, child_parent
);
436 /* new sibling after rotation */
437 if(child_parent
->right
== child
) sibling
= child_parent
->left
;
438 else sibling
= child_parent
->right
;
441 if(child_parent
->color
== BLACK
442 && sibling
->color
== BLACK
443 && sibling
->left
->color
== BLACK
444 && sibling
->right
->color
== BLACK
)
445 { /* fixup local with recolor of sibling */
446 if(sibling
!= LDNS_RBTREE_NULL
)
447 sibling
->color
= RED
;
449 child
= child_parent
;
450 child_parent
= child_parent
->parent
;
451 /* prepare to go up, new sibling */
452 if(child_parent
->right
== child
) sibling
= child_parent
->left
;
453 else sibling
= child_parent
->right
;
458 if(child_parent
->color
== RED
459 && sibling
->color
== BLACK
460 && sibling
->left
->color
== BLACK
461 && sibling
->right
->color
== BLACK
)
463 /* move red to sibling to rebalance */
464 if(sibling
!= LDNS_RBTREE_NULL
)
465 sibling
->color
= RED
;
466 child_parent
->color
= BLACK
;
470 /* get a new sibling, by rotating at sibling. See which child
472 if(child_parent
->right
== child
473 && sibling
->color
== BLACK
474 && sibling
->right
->color
== RED
475 && sibling
->left
->color
== BLACK
)
477 sibling
->color
= RED
;
478 sibling
->right
->color
= BLACK
;
479 ldns_rbtree_rotate_left(rbtree
, sibling
);
480 /* new sibling after rotation */
481 if(child_parent
->right
== child
) sibling
= child_parent
->left
;
482 else sibling
= child_parent
->right
;
484 else if(child_parent
->left
== child
485 && sibling
->color
== BLACK
486 && sibling
->left
->color
== RED
487 && sibling
->right
->color
== BLACK
)
489 sibling
->color
= RED
;
490 sibling
->left
->color
= BLACK
;
491 ldns_rbtree_rotate_right(rbtree
, sibling
);
492 /* new sibling after rotation */
493 if(child_parent
->right
== child
) sibling
= child_parent
->left
;
494 else sibling
= child_parent
->right
;
497 /* now we have a black sibling with a red child. rotate and exchange colors. */
498 sibling
->color
= child_parent
->color
;
499 child_parent
->color
= BLACK
;
500 if(child_parent
->right
== child
)
502 sibling
->left
->color
= BLACK
;
503 ldns_rbtree_rotate_right(rbtree
, child_parent
);
507 sibling
->right
->color
= BLACK
;
508 ldns_rbtree_rotate_left(rbtree
, child_parent
);
513 ldns_rbtree_find_less_equal(ldns_rbtree_t
*rbtree
, const void *key
, ldns_rbnode_t
**result
)
518 /* We start at root... */
523 /* While there are children... */
524 while (node
!= LDNS_RBTREE_NULL
) {
525 r
= rbtree
->cmp(key
, node
->key
);
534 /* Temporary match */
543 * Finds the first element in the red black tree
547 ldns_rbtree_first (ldns_rbtree_t
*rbtree
)
549 ldns_rbnode_t
*node
= rbtree
->root
;
551 if (rbtree
->root
!= LDNS_RBTREE_NULL
) {
552 for (node
= rbtree
->root
; node
->left
!= LDNS_RBTREE_NULL
; node
= node
->left
);
558 ldns_rbtree_last (ldns_rbtree_t
*rbtree
)
560 ldns_rbnode_t
*node
= rbtree
->root
;
562 if (rbtree
->root
!= LDNS_RBTREE_NULL
) {
563 for (node
= rbtree
->root
; node
->right
!= LDNS_RBTREE_NULL
; node
= node
->right
);
569 * Returns the next node...
573 ldns_rbtree_next (ldns_rbnode_t
*node
)
575 ldns_rbnode_t
*parent
;
577 if (node
->right
!= LDNS_RBTREE_NULL
) {
578 /* One right, then keep on going left... */
579 for (node
= node
->right
;
580 node
->left
!= LDNS_RBTREE_NULL
;
583 parent
= node
->parent
;
584 while (parent
!= LDNS_RBTREE_NULL
&& node
== parent
->right
) {
586 parent
= parent
->parent
;
594 ldns_rbtree_previous(ldns_rbnode_t
*node
)
596 ldns_rbnode_t
*parent
;
598 if (node
->left
!= LDNS_RBTREE_NULL
) {
599 /* One left, then keep on going right... */
600 for (node
= node
->left
;
601 node
->right
!= LDNS_RBTREE_NULL
;
604 parent
= node
->parent
;
605 while (parent
!= LDNS_RBTREE_NULL
&& node
== parent
->left
) {
607 parent
= parent
->parent
;
615 * split off elements number of elements from the start
616 * of the name tree and return a new tree
619 ldns_rbtree_split(ldns_rbtree_t
*tree
,
622 ldns_rbtree_t
*new_tree
;
623 ldns_rbnode_t
*cur_node
;
624 ldns_rbnode_t
*move_node
;
627 new_tree
= ldns_rbtree_create(tree
->cmp
);
629 cur_node
= ldns_rbtree_first(tree
);
630 while (count
< elements
&& cur_node
!= LDNS_RBTREE_NULL
) {
631 move_node
= ldns_rbtree_delete(tree
, cur_node
->key
);
632 (void)ldns_rbtree_insert(new_tree
, move_node
);
633 cur_node
= ldns_rbtree_first(tree
);
641 * add all node from the second tree to the first (removing them from the
642 * second), and fix up nsec(3)s if present
645 ldns_rbtree_join(ldns_rbtree_t
*tree1
, ldns_rbtree_t
*tree2
)
647 ldns_traverse_postorder(tree2
, ldns_rbtree_insert_vref
, tree1
);
650 /** recursive descent traverse */
652 traverse_post(void (*func
)(ldns_rbnode_t
*, void*), void* arg
,
655 if(!node
|| node
== LDNS_RBTREE_NULL
)
658 traverse_post(func
, arg
, node
->left
);
659 traverse_post(func
, arg
, node
->right
);
665 ldns_traverse_postorder(ldns_rbtree_t
* tree
,
666 void (*func
)(ldns_rbnode_t
*, void*), void* arg
)
668 traverse_post(func
, arg
, tree
->root
);