ldns/drill: Update vendor branch to 1.6.9
[dragonfly.git] / contrib / ldns / rbtree.c
CommitLineData
825eb42b
JL
1/*
2 * rbtree.c -- generic red black tree
3 *
4 * Taken from Unbound, modified for ldns
5 *
6 * Copyright (c) 2001-2008, NLnet Labs. All rights reserved.
7 *
8 * This software is open source.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 *
14 * Redistributions of source code must retain the above copyright notice,
15 * this list of conditions and the following disclaimer.
16 *
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.
20 *
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.
24 *
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.
36 *
37 */
38
39/**
40 * \file
41 * Implementation of a redblack tree.
42 */
43
44#include <ldns/config.h>
45#include <ldns/rbtree.h>
46#include <stdlib.h>
47
48/** Node colour black */
49#define BLACK 0
50/** Node colour red */
51#define RED 1
52
53/** the NULL node, global alloc */
54ldns_rbnode_t ldns_rbtree_null_node = {
55 LDNS_RBTREE_NULL, /* Parent. */
56 LDNS_RBTREE_NULL, /* Left. */
57 LDNS_RBTREE_NULL, /* Right. */
58 NULL, /* Key. */
59 NULL, /* Data. */
60 BLACK /* Color. */
61};
62
63/** rotate subtree left (to preserve redblack property) */
64static void ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
65/** rotate subtree right (to preserve redblack property) */
66static void ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
67/** Fixup node colours when insert happened */
68static void ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node);
69/** Fixup node colours when delete happened */
70static void ldns_rbtree_delete_fixup(ldns_rbtree_t* rbtree, ldns_rbnode_t* child, ldns_rbnode_t* child_parent);
71
72/*
73 * Creates a new red black tree, intializes and returns a pointer to it.
74 *
75 * Return NULL on failure.
76 *
77 */
78ldns_rbtree_t *
79ldns_rbtree_create (int (*cmpf)(const void *, const void *))
80{
81 ldns_rbtree_t *rbtree;
82
83 /* Allocate memory for it */
84 rbtree = (ldns_rbtree_t *) malloc(sizeof(ldns_rbtree_t));
85 if (!rbtree) {
86 return NULL;
87 }
88
89 /* Initialize it */
90 ldns_rbtree_init(rbtree, cmpf);
91
92 return rbtree;
93}
94
95void
96ldns_rbtree_init(ldns_rbtree_t *rbtree, int (*cmpf)(const void *, const void *))
97{
98 /* Initialize it */
99 rbtree->root = LDNS_RBTREE_NULL;
100 rbtree->count = 0;
101 rbtree->cmp = cmpf;
102}
103
104void
105ldns_rbtree_free(ldns_rbtree_t *rbtree)
106{
107 free(rbtree);
108}
109
110/*
111 * Rotates the node to the left.
112 *
113 */
114static void
115ldns_rbtree_rotate_left(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
116{
117 ldns_rbnode_t *right = node->right;
118 node->right = right->left;
119 if (right->left != LDNS_RBTREE_NULL)
120 right->left->parent = node;
121
122 right->parent = node->parent;
123
124 if (node->parent != LDNS_RBTREE_NULL) {
125 if (node == node->parent->left) {
126 node->parent->left = right;
127 } else {
128 node->parent->right = right;
129 }
130 } else {
131 rbtree->root = right;
132 }
133 right->left = node;
134 node->parent = right;
135}
136
137/*
138 * Rotates the node to the right.
139 *
140 */
141static void
142ldns_rbtree_rotate_right(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
143{
144 ldns_rbnode_t *left = node->left;
145 node->left = left->right;
146 if (left->right != LDNS_RBTREE_NULL)
147 left->right->parent = node;
148
149 left->parent = node->parent;
150
151 if (node->parent != LDNS_RBTREE_NULL) {
152 if (node == node->parent->right) {
153 node->parent->right = left;
154 } else {
155 node->parent->left = left;
156 }
157 } else {
158 rbtree->root = left;
159 }
160 left->right = node;
161 node->parent = left;
162}
163
164static void
165ldns_rbtree_insert_fixup(ldns_rbtree_t *rbtree, ldns_rbnode_t *node)
166{
167 ldns_rbnode_t *uncle;
168
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;
174
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;
180
181 /* And the grandparent red... */
182 node->parent->parent->color = RED;
183
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) {
189 node = node->parent;
190 ldns_rbtree_rotate_left(rbtree, node);
191 }
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);
196 }
197 } else {
198 uncle = node->parent->parent->left;
199
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;
205
206 /* And the grandparent red... */
207 node->parent->parent->color = RED;
208
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) {
214 node = node->parent;
215 ldns_rbtree_rotate_right(rbtree, node);
216 }
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);
221 }
222 }
223 }
224 rbtree->root->color = BLACK;
225}
226
227void
228ldns_rbtree_insert_vref(ldns_rbnode_t *data, void *rbtree)
229{
230 (void) ldns_rbtree_insert((ldns_rbtree_t *) rbtree,
231 data);
232}
233
234/*
235 * Inserts a node into a red black tree.
236 *
237 * Returns NULL on failure or the pointer to the newly added node
238 * otherwise.
239 */
240ldns_rbnode_t *
241ldns_rbtree_insert (ldns_rbtree_t *rbtree, ldns_rbnode_t *data)
242{
243 /* XXX Not necessary, but keeps compiler quiet... */
244 int r = 0;
245
246 /* We start at the root of the tree */
247 ldns_rbnode_t *node = rbtree->root;
248 ldns_rbnode_t *parent = LDNS_RBTREE_NULL;
249
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) {
254 return NULL;
255 }
256 parent = node;
257
258 if (r < 0) {
259 node = node->left;
260 } else {
261 node = node->right;
262 }
263 }
264
265 /* Initialize the new node */
266 data->parent = parent;
267 data->left = data->right = LDNS_RBTREE_NULL;
268 data->color = RED;
269 rbtree->count++;
270
271 /* Insert it into the tree... */
272 if (parent != LDNS_RBTREE_NULL) {
273 if (r < 0) {
274 parent->left = data;
275 } else {
276 parent->right = data;
277 }
278 } else {
279 rbtree->root = data;
280 }
281
282 /* Fix up the red-black properties... */
283 ldns_rbtree_insert_fixup(rbtree, data);
284
285 return data;
286}
287
288/*
289 * Searches the red black tree, returns the data if key is found or NULL otherwise.
290 *
291 */
292ldns_rbnode_t *
293ldns_rbtree_search (ldns_rbtree_t *rbtree, const void *key)
294{
295 ldns_rbnode_t *node;
296
297 if (ldns_rbtree_find_less_equal(rbtree, key, &node)) {
298 return node;
299 } else {
300 return NULL;
301 }
302}
303
304/** helpers for delete: swap node colours */
305static void swap_int8(uint8_t* x, uint8_t* y)
306{
307 uint8_t t = *x; *x = *y; *y = t;
308}
309
310/** helpers for delete: swap node pointers */
311static void swap_np(ldns_rbnode_t** x, ldns_rbnode_t** y)
312{
313 ldns_rbnode_t* t = *x; *x = *y; *y = t;
314}
315
316/** Update parent pointers of child trees of 'parent' */
317static void change_parent_ptr(ldns_rbtree_t* rbtree, ldns_rbnode_t* parent, ldns_rbnode_t* old, ldns_rbnode_t* new)
318{
319 if(parent == LDNS_RBTREE_NULL)
320 {
321 if(rbtree->root == old) rbtree->root = new;
322 return;
323 }
324 if(parent->left == old) parent->left = new;
325 if(parent->right == old) parent->right = new;
326}
327/** Update parent pointer of a node 'child' */
328static void change_child_ptr(ldns_rbnode_t* child, ldns_rbnode_t* old, ldns_rbnode_t* new)
329{
330 if(child == LDNS_RBTREE_NULL) return;
331 if(child->parent == old) child->parent = new;
332}
333
334ldns_rbnode_t*
335ldns_rbtree_delete(ldns_rbtree_t *rbtree, const void *key)
336{
337 ldns_rbnode_t *to_delete;
338 ldns_rbnode_t *child;
339 if((to_delete = ldns_rbtree_search(rbtree, key)) == 0) return 0;
340 rbtree->count--;
341
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)
345 {
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 */
354
355 /* swap colors - colors are tied to the position in the tree */
356 swap_int8(&to_delete->color, &smright->color);
357
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);
362
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)
372 {
373 /* set up so after swap they work */
374 to_delete->right = to_delete;
375 smright->parent = smright;
376 }
377
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);
382
383 /* now delete to_delete (which is at the location where the smright previously was) */
384 }
385
386 if(to_delete->left != LDNS_RBTREE_NULL) child = to_delete->left;
387 else child = to_delete->right;
388
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);
392
393 if(to_delete->color == RED)
394 {
395 /* if node is red then the child (black) can be swapped in */
396 }
397 else if(child->color == RED)
398 {
399 /* change child to BLACK, removing a RED node is no problem */
400 if(child!=LDNS_RBTREE_NULL) child->color = BLACK;
401 }
402 else ldns_rbtree_delete_fixup(rbtree, child, to_delete->parent);
403
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;
409 return to_delete;
410}
411
412static void ldns_rbtree_delete_fixup(ldns_rbtree_t* rbtree, ldns_rbnode_t* child, ldns_rbnode_t* child_parent)
413{
414 ldns_rbnode_t* sibling;
415 int go_up = 1;
416
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;
420
421 while(go_up)
422 {
423 if(child_parent == LDNS_RBTREE_NULL)
424 {
425 /* removed parent==black from root, every path, so ok */
426 return;
427 }
428
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;
439 }
440
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;
448
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;
454 }
455 else go_up = 0;
456 }
457
458 if(child_parent->color == RED
459 && sibling->color == BLACK
460 && sibling->left->color == BLACK
461 && sibling->right->color == BLACK)
462 {
463 /* move red to sibling to rebalance */
464 if(sibling != LDNS_RBTREE_NULL)
465 sibling->color = RED;
466 child_parent->color = BLACK;
467 return;
468 }
469
470 /* get a new sibling, by rotating at sibling. See which child
471 of sibling is red */
472 if(child_parent->right == child
473 && sibling->color == BLACK
474 && sibling->right->color == RED
475 && sibling->left->color == BLACK)
476 {
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;
483 }
484 else if(child_parent->left == child
485 && sibling->color == BLACK
486 && sibling->left->color == RED
487 && sibling->right->color == BLACK)
488 {
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;
495 }
496
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)
501 {
502 sibling->left->color = BLACK;
503 ldns_rbtree_rotate_right(rbtree, child_parent);
504 }
505 else
506 {
507 sibling->right->color = BLACK;
508 ldns_rbtree_rotate_left(rbtree, child_parent);
509 }
510}
511
512int
513ldns_rbtree_find_less_equal(ldns_rbtree_t *rbtree, const void *key, ldns_rbnode_t **result)
514{
515 int r;
516 ldns_rbnode_t *node;
517
518 /* We start at root... */
519 node = rbtree->root;
520
521 *result = NULL;
522
523 /* While there are children... */
524 while (node != LDNS_RBTREE_NULL) {
525 r = rbtree->cmp(key, node->key);
526 if (r == 0) {
527 /* Exact match */
528 *result = node;
529 return 1;
530 }
531 if (r < 0) {
532 node = node->left;
533 } else {
534 /* Temporary match */
535 *result = node;
536 node = node->right;
537 }
538 }
539 return 0;
540}
541
542/*
543 * Finds the first element in the red black tree
544 *
545 */
546ldns_rbnode_t *
547ldns_rbtree_first (ldns_rbtree_t *rbtree)
548{
ac996e71 549 ldns_rbnode_t *node = rbtree->root;
825eb42b 550
ac996e71
JL
551 if (rbtree->root != LDNS_RBTREE_NULL) {
552 for (node = rbtree->root; node->left != LDNS_RBTREE_NULL; node = node->left);
553 }
825eb42b
JL
554 return node;
555}
556
557ldns_rbnode_t *
558ldns_rbtree_last (ldns_rbtree_t *rbtree)
559{
ac996e71 560 ldns_rbnode_t *node = rbtree->root;
825eb42b 561
ac996e71
JL
562 if (rbtree->root != LDNS_RBTREE_NULL) {
563 for (node = rbtree->root; node->right != LDNS_RBTREE_NULL; node = node->right);
564 }
825eb42b
JL
565 return node;
566}
567
568/*
569 * Returns the next node...
570 *
571 */
572ldns_rbnode_t *
573ldns_rbtree_next (ldns_rbnode_t *node)
574{
575 ldns_rbnode_t *parent;
576
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;
581 node = node->left);
582 } else {
583 parent = node->parent;
584 while (parent != LDNS_RBTREE_NULL && node == parent->right) {
585 node = parent;
586 parent = parent->parent;
587 }
588 node = parent;
589 }
590 return node;
591}
592
593ldns_rbnode_t *
594ldns_rbtree_previous(ldns_rbnode_t *node)
595{
596 ldns_rbnode_t *parent;
597
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;
602 node = node->right);
603 } else {
604 parent = node->parent;
605 while (parent != LDNS_RBTREE_NULL && node == parent->left) {
606 node = parent;
607 parent = parent->parent;
608 }
609 node = parent;
610 }
611 return node;
612}
613
614/**
615 * split off elements number of elements from the start
616 * of the name tree and return a new tree
617 */
618ldns_rbtree_t *
619ldns_rbtree_split(ldns_rbtree_t *tree,
620 size_t elements)
621{
622 ldns_rbtree_t *new_tree;
623 ldns_rbnode_t *cur_node;
624 ldns_rbnode_t *move_node;
625 size_t count = 0;
626
627 new_tree = ldns_rbtree_create(tree->cmp);
628
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);
fd185f4d 632 (void)ldns_rbtree_insert(new_tree, move_node);
825eb42b
JL
633 cur_node = ldns_rbtree_first(tree);
634 count++;
635 }
636
637 return new_tree;
638}
639
640/*
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
643 */
644void
645ldns_rbtree_join(ldns_rbtree_t *tree1, ldns_rbtree_t *tree2)
646{
647 ldns_traverse_postorder(tree2, ldns_rbtree_insert_vref, tree1);
648}
649
650/** recursive descent traverse */
651static void
652traverse_post(void (*func)(ldns_rbnode_t*, void*), void* arg,
653 ldns_rbnode_t* node)
654{
655 if(!node || node == LDNS_RBTREE_NULL)
656 return;
657 /* recurse */
658 traverse_post(func, arg, node->left);
659 traverse_post(func, arg, node->right);
660 /* call user func */
661 (*func)(node, arg);
662}
663
664void
665ldns_traverse_postorder(ldns_rbtree_t* tree,
666 void (*func)(ldns_rbnode_t*, void*), void* arg)
667{
668 traverse_post(func, arg, tree->root);
669}