1 /*
2 * rbtree.c RED-BLACK balanced binary trees.
3 *
4 * Version: $Id: d9892bdeb7c8145357db0324b2ac8d4934af2f2c $
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2.1 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
19 *
20 * Copyright 2004,2006 The FreeRADIUS server project
21 */
22
23 RCSID("$Id: d9892bdeb7c8145357db0324b2ac8d4934af2f2c $")
24
25 #include <freeradius-devel/libradius.h>
26
27 #ifdef HAVE_PTHREAD_H
28 #include <pthread.h>
29
30 #define PTHREAD_MUTEX_LOCK(_x) if (_x->lock) pthread_mutex_lock(&((_x)->mutex))
31 #define PTHREAD_MUTEX_UNLOCK(_x) if (_x->lock) pthread_mutex_unlock(&((_x)->mutex))
32 #else
33 #define PTHREAD_MUTEX_LOCK(_x)
34 #define PTHREAD_MUTEX_UNLOCK(_x)
35 #endif
36
37 /* Red-Black tree description */
38 typedef enum {
39 BLACK,
40 RED
41 } node_colour_t;
42
43 struct rbnode_t {
44 rbnode_t *left; //!< Left child
45 rbnode_t *right; //!< Right child
46 rbnode_t *parent; //!< Parent
47 node_colour_t colour; //!< Node colour (BLACK, RED)
48 void *data; //!< data stored in node
49 };
50
51 #define NIL &sentinel /* all leafs are sentinels */
52 static rbnode_t sentinel = { NIL, NIL, NIL, BLACK, NULL};
53
54 #define NOT_AT_ROOT(_node) ((_node) != NIL)
55
56 struct rbtree_t {
57 #ifndef NDEBUG
58 uint32_t magic;
59 #endif
60 rbnode_t *root;
61 int num_elements;
62 rb_comparator_t compare;
63 rb_free_t free;
64 bool replace;
65 #ifdef HAVE_PTHREAD_H
66 bool lock;
67 pthread_mutex_t mutex;
68 #endif
69 };
70 #define RBTREE_MAGIC (0x5ad09c42)
71
72 /** Walks the tree to delete all nodes Does NOT re-balance it!
73 *
74 */
free_walker(rbtree_t * tree,rbnode_t * x)75 static void free_walker(rbtree_t *tree, rbnode_t *x)
76 {
77 (void) talloc_get_type_abort(x, rbnode_t);
78
79 if (x->left != NIL) free_walker(tree, x->left);
80 if (x->right != NIL) free_walker(tree, x->right);
81
82 if (tree->free) tree->free(x->data);
83 talloc_free(x);
84 }
85
rbtree_free(rbtree_t * tree)86 void rbtree_free(rbtree_t *tree)
87 {
88 if (!tree) return;
89
90 PTHREAD_MUTEX_LOCK(tree);
91
92 /*
93 * walk the tree, deleting the nodes...
94 */
95 if (tree->root != NIL) free_walker(tree, tree->root);
96
97 #ifndef NDEBUG
98 tree->magic = 0;
99 #endif
100 tree->root = NULL;
101
102 PTHREAD_MUTEX_UNLOCK(tree);
103
104 #ifdef HAVE_PTHREAD_H
105 if (tree->lock) pthread_mutex_destroy(&tree->mutex);
106 #endif
107
108 talloc_free(tree);
109 }
110
111 /** Create a new RED-BLACK tree
112 *
113 */
rbtree_create(TALLOC_CTX * ctx,rb_comparator_t compare,rb_free_t node_free,int flags)114 rbtree_t *rbtree_create(TALLOC_CTX *ctx, rb_comparator_t compare, rb_free_t node_free, int flags)
115 {
116 rbtree_t *tree;
117
118 if (!compare) return NULL;
119
120 tree = talloc_zero(ctx, rbtree_t);
121 if (!tree) return NULL;
122
123 #ifndef NDEBUG
124 tree->magic = RBTREE_MAGIC;
125 #endif
126 tree->root = NIL;
127 tree->compare = compare;
128 tree->replace = (flags & RBTREE_FLAG_REPLACE) != 0 ? true : false;
129 #ifdef HAVE_PTHREAD_H
130 tree->lock = (flags & RBTREE_FLAG_LOCK) != 0 ? true : false;
131 if (tree->lock) {
132 pthread_mutex_init(&tree->mutex, NULL);
133 }
134 #endif
135 tree->free = node_free;
136
137 return tree;
138 }
139
140 /** Rotate Node x to left
141 *
142 */
rotate_left(rbtree_t * tree,rbnode_t * x)143 static void rotate_left(rbtree_t *tree, rbnode_t *x)
144 {
145
146 rbnode_t *y = x->right;
147
148 /* establish x->right link */
149 x->right = y->left;
150 if (y->left != NIL) y->left->parent = x;
151
152 /* establish y->parent link */
153 if (y != NIL) y->parent = x->parent;
154 if (NOT_AT_ROOT(x->parent)) {
155 if (x == x->parent->left) {
156 x->parent->left = y;
157 } else {
158 x->parent->right = y;
159 }
160 } else {
161 tree->root = y;
162 }
163
164 /* link x and y */
165 y->left = x;
166 if (x != NIL) x->parent = y;
167 }
168
169 /** Rotate Node x to right
170 *
171 */
rotate_right(rbtree_t * tree,rbnode_t * x)172 static void rotate_right(rbtree_t *tree, rbnode_t *x)
173 {
174 rbnode_t *y = x->left;
175
176 /* establish x->left link */
177 x->left = y->right;
178 if (y->right != NIL) y->right->parent = x;
179
180 /* establish y->parent link */
181 if (y != NIL) y->parent = x->parent;
182 if (NOT_AT_ROOT(x->parent)) {
183 if (x == x->parent->right) {
184 x->parent->right = y;
185 } else {
186 x->parent->left = y;
187 }
188 } else {
189 tree->root = y;
190 }
191
192 /* link x and y */
193 y->right = x;
194 if (x != NIL) x->parent = y;
195 }
196
197 /** Maintain red-black tree balance after inserting node x
198 *
199 */
insert_fixup(rbtree_t * tree,rbnode_t * x)200 static void insert_fixup(rbtree_t *tree, rbnode_t *x)
201 {
202 /* check RED-BLACK properties */
203 while ((x != tree->root) && (x->parent->colour == RED)) {
204 /* we have a violation */
205 if (x->parent == x->parent->parent->left) {
206 rbnode_t *y = x->parent->parent->right;
207 if (y->colour == RED) {
208
209 /* uncle is RED */
210 x->parent->colour = BLACK;
211 y->colour = BLACK;
212 x->parent->parent->colour = RED;
213 x = x->parent->parent;
214 } else {
215
216 /* uncle is BLACK */
217 if (x == x->parent->right) {
218 /* make x a left child */
219 x = x->parent;
220 rotate_left(tree, x);
221 }
222
223 /* recolour and rotate */
224 x->parent->colour = BLACK;
225 x->parent->parent->colour = RED;
226 rotate_right(tree, x->parent->parent);
227 }
228 } else {
229
230 /* mirror image of above code */
231 rbnode_t *y = x->parent->parent->left;
232 if (y->colour == RED) {
233
234 /* uncle is RED */
235 x->parent->colour = BLACK;
236 y->colour = BLACK;
237 x->parent->parent->colour = RED;
238 x = x->parent->parent;
239 } else {
240
241 /* uncle is BLACK */
242 if (x == x->parent->left) {
243 x = x->parent;
244 rotate_right(tree, x);
245 }
246 x->parent->colour = BLACK;
247 x->parent->parent->colour = RED;
248 rotate_left(tree, x->parent->parent);
249 }
250 }
251 }
252
253 if (tree->root != NIL) tree->root->colour = BLACK; /* Avoid cache-dirty on NIL */
254 }
255
256
257 /** Insert an element into the tree
258 *
259 */
rbtree_insert_node(rbtree_t * tree,void * data)260 rbnode_t *rbtree_insert_node(rbtree_t *tree, void *data)
261 {
262 rbnode_t *current, *parent, *x;
263
264 PTHREAD_MUTEX_LOCK(tree);
265
266 /* find where node belongs */
267 current = tree->root;
268 parent = NIL;
269 while (current != NIL) {
270 int result;
271
272 /*
273 * See if two entries are identical.
274 */
275 result = tree->compare(data, current->data);
276 if (result == 0) {
277 /*
278 * Don't replace the entry.
279 */
280 if (!tree->replace) {
281 PTHREAD_MUTEX_UNLOCK(tree);
282 return NULL;
283 }
284
285 /*
286 * Do replace the entry.
287 */
288 if (tree->free) tree->free(current->data);
289 current->data = data;
290 PTHREAD_MUTEX_UNLOCK(tree);
291 return current;
292 }
293
294 parent = current;
295 current = (result < 0) ? current->left : current->right;
296 }
297
298 /* setup new node */
299 x = talloc_zero(tree, rbnode_t);
300 if (!x) {
301 fr_strerror_printf("No memory for new rbtree node");
302 PTHREAD_MUTEX_UNLOCK(tree);
303 return NULL;
304 }
305
306 x->data = data;
307 x->parent = parent;
308 x->left = NIL;
309 x->right = NIL;
310 x->colour = RED;
311
312 /* insert node in tree */
313 if (NOT_AT_ROOT(parent)) {
314 if (tree->compare(data, parent->data) <= 0) {
315 parent->left = x;
316 } else {
317 parent->right = x;
318 }
319 } else {
320 tree->root = x;
321 }
322
323 insert_fixup(tree, x);
324
325 tree->num_elements++;
326
327 PTHREAD_MUTEX_UNLOCK(tree);
328 return x;
329 }
330
rbtree_insert(rbtree_t * tree,void * data)331 bool rbtree_insert(rbtree_t *tree, void *data)
332 {
333 if (rbtree_insert_node(tree, data)) return true;
334 return false;
335 }
336
337 /** Maintain RED-BLACK tree balance after deleting node x
338 *
339 */
delete_fixup(rbtree_t * tree,rbnode_t * x,rbnode_t * parent)340 static void delete_fixup(rbtree_t *tree, rbnode_t *x, rbnode_t *parent)
341 {
342
343 while (x != tree->root && x->colour == BLACK) {
344 if (x == parent->left) {
345 rbnode_t *w = parent->right;
346 if (w->colour == RED) {
347 w->colour = BLACK;
348 parent->colour = RED; /* parent != NIL? */
349 rotate_left(tree, parent);
350 w = parent->right;
351 }
352 if ((w->left->colour == BLACK) && (w->right->colour == BLACK)) {
353 if (w != NIL) w->colour = RED;
354 x = parent;
355 parent = x->parent;
356 } else {
357 if (w->right->colour == BLACK) {
358 if (w->left != NIL) w->left->colour = BLACK;
359 w->colour = RED;
360 rotate_right(tree, w);
361 w = parent->right;
362 }
363 w->colour = parent->colour;
364 if (parent != NIL) parent->colour = BLACK;
365 if (w->right->colour != BLACK) {
366 w->right->colour = BLACK;
367 }
368 rotate_left(tree, parent);
369 x = tree->root;
370 }
371 } else {
372 rbnode_t *w = parent->left;
373 if (w->colour == RED) {
374 w->colour = BLACK;
375 parent->colour = RED; /* parent != NIL? */
376 rotate_right(tree, parent);
377 w = parent->left;
378 }
379 if ((w->right->colour == BLACK) && (w->left->colour == BLACK)) {
380 if (w != NIL) w->colour = RED;
381 x = parent;
382 parent = x->parent;
383 } else {
384 if (w->left->colour == BLACK) {
385 if (w->right != NIL) w->right->colour = BLACK;
386 w->colour = RED;
387 rotate_left(tree, w);
388 w = parent->left;
389 }
390 w->colour = parent->colour;
391 if (parent != NIL) parent->colour = BLACK;
392 if (w->left->colour != BLACK) {
393 w->left->colour = BLACK;
394 }
395 rotate_right(tree, parent);
396 x = tree->root;
397 }
398 }
399 }
400 if (x != NIL) x->colour = BLACK; /* Avoid cache-dirty on NIL */
401 }
402
403 /** Delete an element (z) from the tree
404 *
405 */
rbtree_delete_internal(rbtree_t * tree,rbnode_t * z,bool skiplock)406 static void rbtree_delete_internal(rbtree_t *tree, rbnode_t *z, bool skiplock)
407 {
408 rbnode_t *x, *y;
409 rbnode_t *parent;
410
411 if (!z || z == NIL) return;
412
413 if (!skiplock) {
414 PTHREAD_MUTEX_LOCK(tree);
415 }
416
417 if (z->left == NIL || z->right == NIL) {
418 /* y has a NIL node as a child */
419 y = z;
420 } else {
421 /* find tree successor with a NIL node as a child */
422 y = z->right;
423 while (y->left != NIL) y = y->left;
424 }
425
426 /* x is y's only child */
427 if (y->left != NIL) {
428 x = y->left;
429 } else {
430 x = y->right; /* may be NIL! */
431 }
432
433 /* remove y from the parent chain */
434 parent = y->parent;
435 if (x != NIL) x->parent = parent;
436
437 if (NOT_AT_ROOT(parent)) {
438 if (y == parent->left) {
439 parent->left = x;
440 } else {
441 parent->right = x;
442 }
443 } else {
444 tree->root = x;
445 }
446
447 if (y != z) {
448 if (tree->free) tree->free(z->data);
449 z->data = y->data;
450 y->data = NULL;
451
452 if ((y->colour == BLACK) && NOT_AT_ROOT(parent)) {
453 delete_fixup(tree, x, parent);
454 }
455
456 /*
457 * The user structure in y->data MAy include a
458 * pointer to y. In that case, we CANNOT delete
459 * y. Instead, we copy z (which is now in the
460 * tree) to y, and fix up the parent/child
461 * pointers.
462 */
463 memcpy(y, z, sizeof(*y));
464
465 if (NOT_AT_ROOT(y->parent)) {
466 if (y->parent->left == z) y->parent->left = y;
467 if (y->parent->right == z) y->parent->right = y;
468 } else {
469 tree->root = y;
470 }
471 if (y->left->parent == z) y->left->parent = y;
472 if (y->right->parent == z) y->right->parent = y;
473
474 talloc_free(z);
475
476 } else {
477 if (tree->free) tree->free(y->data);
478
479 if (y->colour == BLACK)
480 delete_fixup(tree, x, parent);
481
482 talloc_free(y);
483 }
484
485 tree->num_elements--;
486 if (!skiplock) {
487 PTHREAD_MUTEX_UNLOCK(tree);
488 }
489 }
rbtree_delete(rbtree_t * tree,rbnode_t * z)490 void rbtree_delete(rbtree_t *tree, rbnode_t *z) {
491 rbtree_delete_internal(tree, z, false);
492 }
493
494 /** Delete a node from the tree, based on given data, which MUST have come from rbtree_finddata().
495 *
496 *
497 */
rbtree_deletebydata(rbtree_t * tree,void const * data)498 bool rbtree_deletebydata(rbtree_t *tree, void const *data)
499 {
500 rbnode_t *node = rbtree_find(tree, data);
501
502 if (!node) return false;
503
504 rbtree_delete(tree, node);
505
506 return true;
507 }
508
509
510 /** Find an element in the tree, returning the data, not the node
511 *
512 */
rbtree_find(rbtree_t * tree,void const * data)513 rbnode_t *rbtree_find(rbtree_t *tree, void const *data)
514 {
515 rbnode_t *current;
516
517 PTHREAD_MUTEX_LOCK(tree);
518 current = tree->root;
519
520 while (current != NIL) {
521 int result = tree->compare(data, current->data);
522
523 if (result == 0) {
524 PTHREAD_MUTEX_UNLOCK(tree);
525 return current;
526 } else {
527 current = (result < 0) ?
528 current->left : current->right;
529 }
530 }
531
532 PTHREAD_MUTEX_UNLOCK(tree);
533 return NULL;
534 }
535
536 /** Find the user data.
537 *
538 */
rbtree_finddata(rbtree_t * tree,void const * data)539 void *rbtree_finddata(rbtree_t *tree, void const *data)
540 {
541 rbnode_t *x;
542
543 x = rbtree_find(tree, data);
544 if (!x) return NULL;
545
546 return x->data;
547 }
548
549 /** Walk the tree, Pre-order
550 *
551 * We call ourselves recursively for each function, but that's OK,
552 * as the stack is only log(N) deep, which is ~12 entries deep.
553 */
walk_node_pre_order(rbnode_t * x,rb_walker_t compare,void * context)554 static int walk_node_pre_order(rbnode_t *x, rb_walker_t compare, void *context)
555 {
556 int rcode;
557 rbnode_t *left, *right;
558
559 left = x->left;
560 right = x->right;
561
562 rcode = compare(context, x->data);
563 if (rcode != 0) return rcode;
564
565 if (left != NIL) {
566 rcode = walk_node_pre_order(left, compare, context);
567 if (rcode != 0) return rcode;
568 }
569
570 if (right != NIL) {
571 rcode = walk_node_pre_order(right, compare, context);
572 if (rcode != 0) return rcode;
573 }
574
575 return 0; /* we know everything returned zero */
576 }
577
578 /** rbtree_in_order
579 *
580 */
walk_node_in_order(rbnode_t * x,rb_walker_t compare,void * context)581 static int walk_node_in_order(rbnode_t *x, rb_walker_t compare, void *context)
582 {
583 int rcode;
584 rbnode_t *right;
585
586 if (x->left != NIL) {
587 rcode = walk_node_in_order(x->left, compare, context);
588 if (rcode != 0) return rcode;
589 }
590
591 right = x->right;
592
593 rcode = compare(context, x->data);
594 if (rcode != 0) return rcode;
595
596 if (right != NIL) {
597 rcode = walk_node_in_order(right, compare, context);
598 if (rcode != 0) return rcode;
599 }
600
601 return 0; /* we know everything returned zero */
602 }
603
604
605 /** rbtree_post_order
606 *
607 */
walk_node_post_order(rbnode_t * x,rb_walker_t compare,void * context)608 static int walk_node_post_order(rbnode_t *x, rb_walker_t compare, void *context)
609 {
610 int rcode;
611
612 if (x->left != NIL) {
613 rcode = walk_node_post_order(x->left, compare, context);
614 if (rcode != 0) return rcode;
615 }
616
617 if (x->right != NIL) {
618 rcode = walk_node_post_order(x->right, compare, context);
619 if (rcode != 0) return rcode;
620 }
621
622 rcode = compare(context, x->data);
623 if (rcode != 0) return rcode;
624
625 return 0; /* we know everything returned zero */
626 }
627
628
629 /** rbtree_delete_order
630 *
631 * This executes an rbtree_in_order-like walk that adapts to changes in the
632 * tree above it, which may occur because we allow the compare to
633 * tell us to delete the current node.
634 *
635 * The compare should return:
636 *
637 * < 0 - on error
638 * 0 - continue walking, don't delete the node
639 * 1 - delete the node and stop walking
640 * 2 - delete the node and continue walking
641 */
walk_delete_order(rbtree_t * tree,rb_walker_t compare,void * context)642 static int walk_delete_order(rbtree_t *tree, rb_walker_t compare, void *context)
643 {
644 rbnode_t *solid, *x;
645 int rcode = 0;
646
647 /* Keep track of last node that refused deletion. */
648 solid = NIL;
649 while (solid == NIL) {
650 x = tree->root;
651 if (x == NIL) break;
652 descend:
653 while (x->left != NIL) {
654 x = x->left;
655 }
656 visit:
657 rcode = compare(context, x->data);
658 if (rcode < 0) {
659 return rcode;
660 }
661 if (rcode) {
662 rbtree_delete_internal(tree, x, true);
663 if (rcode != 2) {
664 return rcode;
665 }
666 } else {
667 solid = x;
668 }
669 }
670 if (solid != NIL) {
671 x = solid;
672 if (x->right != NIL) {
673 x = x->right;
674 goto descend;
675 }
676 while (NOT_AT_ROOT(x->parent)) {
677 if (x->parent->left == x) {
678 x = x->parent;
679 goto visit;
680 }
681 x = x->parent;
682 }
683 }
684 return rcode;
685 }
686
687
688 /*
689 * walk the entire tree. The compare function CANNOT modify
690 * the tree.
691 *
692 * The compare function should return 0 to continue walking.
693 * Any other value stops the walk, and is returned.
694 */
rbtree_walk(rbtree_t * tree,rb_order_t order,rb_walker_t compare,void * context)695 int rbtree_walk(rbtree_t *tree, rb_order_t order, rb_walker_t compare, void *context)
696 {
697 int rcode;
698
699 if (tree->root == NIL) return 0;
700
701 PTHREAD_MUTEX_LOCK(tree);
702
703 switch (order) {
704 case RBTREE_PRE_ORDER:
705 rcode = walk_node_pre_order(tree->root, compare, context);
706 break;
707
708 case RBTREE_IN_ORDER:
709 rcode = walk_node_in_order(tree->root, compare, context);
710 break;
711
712 case RBTREE_POST_ORDER:
713 rcode = walk_node_post_order(tree->root, compare, context);
714 break;
715
716 case RBTREE_DELETE_ORDER:
717 rcode = walk_delete_order(tree, compare, context);
718 break;
719
720 default:
721 rcode = -1;
722 break;
723 }
724
725 PTHREAD_MUTEX_UNLOCK(tree);
726 return rcode;
727 }
728
rbtree_num_elements(rbtree_t * tree)729 uint32_t rbtree_num_elements(rbtree_t *tree)
730 {
731 if (!tree) return 0;
732
733 return tree->num_elements;
734 }
735
736 /*
737 * Given a Node, return the data.
738 */
rbtree_node2data(UNUSED rbtree_t * tree,rbnode_t * node)739 void *rbtree_node2data(UNUSED rbtree_t *tree, rbnode_t *node)
740 {
741 if (!node) return NULL;
742
743 return node->data;
744 }
745