Asterisk - The Open Source Telephony Project GIT-master-85241bd
astobj2_rbtree.c
Go to the documentation of this file.
1/*
2 * astobj2_hash - RBTree implementation for astobj2.
3 *
4 * Copyright (C) 2006 Marta Carbone, Luigi Rizzo - Univ. di Pisa, Italy
5 *
6 * See http://www.asterisk.org for more information about
7 * the Asterisk project. Please do not directly contact
8 * any of the maintainers of this project for assistance;
9 * the project provides a web site, mailing lists and IRC
10 * channels for your use.
11 *
12 * This program is free software, distributed under the terms of
13 * the GNU General Public License Version 2. See the LICENSE file
14 * at the top of the source tree.
15 */
16
17/*! \file
18 *
19 * \brief RBTree functions implementing astobj2 containers.
20 *
21 * \author Richard Mudgett <rmudgett@digium.com>
22 */
23
24#include "asterisk.h"
25
26#include "asterisk/_private.h"
27#include "asterisk/astobj2.h"
28#include "asterisk/utils.h"
29#include "astobj2_private.h"
31
32/*!
33 * A structure to hold the object held by the container and
34 * where it is located in it.
35 *
36 * A red-black tree has the following properties:
37 *
38 * 1) Every node is either black or red.
39 *
40 * 2) The root is black.
41 *
42 * 3) If a node has a NULL child, that "child" is considered
43 * black.
44 *
45 * 4) If a node is red, then both of its children are black.
46 *
47 * 5) Every path from a node to a descendant NULL child has the
48 * same number of black nodes. (Including the black NULL
49 * child.)
50 */
52 /*!
53 * \brief Items common to all container nodes.
54 * \note Must be first in the specific node struct.
55 */
57 /*! Parent node of this node. NULL if this is the root node. */
59 /*! Left child node of this node. NULL if does not have this child. */
61 /*! Right child node of this node. NULL if does not have this child. */
63 /*! TRUE if the node is red. */
64 unsigned int is_red:1;
65};
66
67/*!
68 * A rbtree container in addition to values common to all
69 * container types, stores the pointer to the root node of the
70 * tree.
71 */
73 /*!
74 * \brief Items common to all containers.
75 * \note Must be first in the specific container struct.
76 */
78 /*! Root node of the tree. NULL if the tree is empty. */
80#if defined(AO2_DEBUG)
81 struct {
82 /*! Fixup insert left cases 1-3 */
83 int fixup_insert_left[3];
84 /*! Fixup insert right cases 1-3 */
85 int fixup_insert_right[3];
86 /*! Fixup delete left cases 1-4 */
87 int fixup_delete_left[4];
88 /*! Fixup delete right cases 1-4 */
89 int fixup_delete_right[4];
90 /*! Deletion of node with number of children (0-2). */
91 int delete_children[3];
92 } stats;
93#endif /* defined(AO2_DEBUG) */
94};
95
97 /*! Bias search toward first matching node in the container. */
99 /*! Bias search toward any matching node. */
101 /*! Bias search toward last matching node in the container. */
103};
104
108};
109
110/*! Traversal state to restart a rbtree container traversal. */
112 /*! Active sort function in the traversal if not NULL. */
114 /*! Saved comparison callback arg pointer. */
115 void *arg;
116 /*! Saved search flags to control traversing the container. */
118};
119
121 /*
122 * If we have a division by zero compile error here then there
123 * is not enough room for the state. Increase AO2_TRAVERSAL_STATE_SIZE.
124 */
126};
127
128/*!
129 * \internal
130 * \brief Get the most left node in the tree.
131 * \since 12.0.0
132 *
133 * \param node Starting node to find the most left node.
134 *
135 * \return Left most node. Never NULL.
136 */
138{
139 while (node->left) {
140 node = node->left;
141 }
142
143 return node;
144}
145
146/*!
147 * \internal
148 * \brief Get the most right node in the tree.
149 * \since 12.0.0
150 *
151 * \param node Starting node to find the most right node.
152 *
153 * \return Right most node. Never NULL.
154 */
156{
157 while (node->right) {
158 node = node->right;
159 }
160
161 return node;
162}
163
164/*!
165 * \internal
166 * \brief Get the next node in ascending sequence.
167 * \since 12.0.0
168 *
169 * \param node Starting node to find the next node.
170 *
171 * \return node on success.
172 * \retval NULL if no node.
173 */
175{
176 if (node->right) {
177 return rb_node_most_left(node->right);
178 }
179
180 /* Find the parent that the node is a left child of. */
181 while (node->parent) {
182 if (node->parent->left == node) {
183 /* We are the left child. The parent is the next node. */
184 return node->parent;
185 }
186 node = node->parent;
187 }
188 return NULL;
189}
190
191/*!
192 * \internal
193 * \brief Get the next node in descending sequence.
194 * \since 12.0.0
195 *
196 * \param node Starting node to find the previous node.
197 *
198 * \return node on success.
199 * \retval NULL if no node.
200 */
202{
203 if (node->left) {
204 return rb_node_most_right(node->left);
205 }
206
207 /* Find the parent that the node is a right child of. */
208 while (node->parent) {
209 if (node->parent->right == node) {
210 /* We are the right child. The parent is the previous node. */
211 return node->parent;
212 }
213 node = node->parent;
214 }
215 return NULL;
216}
217
218/*!
219 * \internal
220 * \brief Get the next node in pre-order sequence.
221 * \since 12.0.0
222 *
223 * \param node Starting node to find the next node.
224 *
225 * \return node on success.
226 * \retval NULL if no node.
227 */
229{
230 /* Visit the children if the node has any. */
231 if (node->left) {
232 return node->left;
233 }
234 if (node->right) {
235 return node->right;
236 }
237
238 /* Time to go back up. */
239 for (;;) {
240 if (!node->parent) {
241 return NULL;
242 }
243 if (node->parent->left == node && node->parent->right) {
244 /*
245 * We came up the left child and there's a right child. Visit
246 * it.
247 */
248 return node->parent->right;
249 }
250 node = node->parent;
251 }
252}
253
254/*!
255 * \internal
256 * \brief Get the next node in post-order sequence.
257 * \since 12.0.0
258 *
259 * \param node Starting node to find the next node.
260 *
261 * \return node on success.
262 * \retval NULL if no node.
263 */
265{
266 /* This node's children have already been visited. */
267 for (;;) {
268 if (!node->parent) {
269 return NULL;
270 }
271 if (node->parent->left == node) {
272 /* We came up the left child. */
273 node = node->parent;
274
275 /*
276 * Find the right child's left most childless node.
277 */
278 while (node->right) {
279 node = rb_node_most_left(node->right);
280 }
281
282 /*
283 * This node's left child has already been visited or it doesn't
284 * have any children.
285 */
286 return node;
287 }
288
289 /*
290 * We came up the right child.
291 *
292 * This node's children have already been visited. Time to
293 * visit the parent.
294 */
295 return node->parent;
296 }
297}
298
299/*!
300 * \internal
301 * \brief Get the next non-empty node in ascending sequence.
302 * \since 12.0.0
303 *
304 * \param node Starting node to find the next node.
305 *
306 * \return node on success.
307 * \retval NULL if no node.
308 */
310{
311 for (;;) {
313 if (!node || node->common.obj) {
314 return node;
315 }
316 }
317}
318
319/*!
320 * \internal
321 * \brief Get the next non-empty node in descending sequence.
322 * \since 12.0.0
323 *
324 * \param node Starting node to find the previous node.
325 *
326 * \return node on success.
327 * \retval NULL if no node.
328 */
330{
331 for (;;) {
333 if (!node || node->common.obj) {
334 return node;
335 }
336 }
337}
338
339/*!
340 * \internal
341 * \brief Determine which way to go from an empty node.
342 * \since 12.0.0
343 *
344 * \param empty Empty node to determine which side obj_right goes on.
345 * \param sort_fn Sort comparison function for non-empty nodes.
346 * \param obj_right pointer to the (user-defined part) of an object.
347 * \param flags flags from ao2_callback()
348 * OBJ_SEARCH_OBJECT - if set, 'obj_right', is an object.
349 * OBJ_SEARCH_KEY - if set, 'obj_right', is a search key item that is not an object.
350 * OBJ_SEARCH_PARTIAL_KEY - if set, 'obj_right', is a partial search key item that is not an object.
351 * \param bias How to bias search direction for duplicates
352 *
353 * \return \ref empty_node_direction to proceed.
354 */
355static enum empty_node_direction rb_find_empty_direction(struct rbtree_node *empty, ao2_sort_fn *sort_fn, void *obj_right, enum search_flags flags, enum equal_node_bias bias)
356{
357 int cmp;
358 struct rbtree_node *cur;
359 struct rbtree_node *right_most;
360
361 /* Try for a quick definite go left. */
362 if (!empty->left) {
363 /* The empty node has no left child. */
364 return GO_RIGHT;
365 }
366 right_most = rb_node_most_right(empty->left);
367 if (right_most->common.obj) {
368 cmp = sort_fn(right_most->common.obj, obj_right, flags);
369 if (cmp < 0) {
370 return GO_RIGHT;
371 }
372 if (cmp == 0 && bias == BIAS_LAST) {
373 return GO_RIGHT;
374 }
375 return GO_LEFT;
376 }
377
378 /* Try for a quick definite go right. */
379 if (!empty->right) {
380 /* The empty node has no right child. */
381 return GO_LEFT;
382 }
383 cur = rb_node_most_left(empty->right);
384 if (cur->common.obj) {
385 cmp = sort_fn(cur->common.obj, obj_right, flags);
386 if (cmp > 0) {
387 return GO_LEFT;
388 }
389 if (cmp == 0 && bias == BIAS_FIRST) {
390 return GO_LEFT;
391 }
392 return GO_RIGHT;
393 }
394
395 /*
396 * Have to scan the previous nodes from the right_most node of
397 * the left subtree for the first non-empty node to determine
398 * direction.
399 */
400 cur = right_most;
401 for (;;) {
402 /* Find previous node. */
403 if (cur->left) {
404 cur = rb_node_most_right(cur->left);
405 } else {
406 /* Find the parent that the node is a right child of. */
407 for (;;) {
408 if (cur->parent == empty) {
409 /* The left side of the empty node is all empty nodes. */
410 return GO_RIGHT;
411 }
412 if (cur->parent->right == cur) {
413 /* We are the right child. The parent is the previous node. */
414 cur = cur->parent;
415 break;
416 }
417 cur = cur->parent;
418 }
419 }
420
421 if (cur->common.obj) {
422 cmp = sort_fn(cur->common.obj, obj_right, flags);
423 if (cmp < 0) {
424 return GO_RIGHT;
425 }
426 if (cmp == 0 && bias == BIAS_LAST) {
427 return GO_RIGHT;
428 }
429 return GO_LEFT;
430 }
431 }
432}
433
434/*!
435 * \internal
436 * \brief Tree node rotation left.
437 * \since 12.0.0
438 *
439 * \param self Container holding node.
440 * \param node Node to perform a left rotation with.
441 *
442 * p p
443 * | Left rotation |
444 * N ---> Ch
445 * / \ / \
446 * a Ch N c
447 * / \ / \
448 * b c a b
449 *
450 * N = node
451 * Ch = child
452 * p = parent
453 * a,b,c = other nodes that are unaffected by the rotation.
454 *
455 * \note It is assumed that the node's right child exists.
456 */
457static void rb_rotate_left(struct ao2_container_rbtree *self, struct rbtree_node *node)
458{
459 struct rbtree_node *child; /*!< Node's right child. */
460
461 child = node->right;
462
463 /* Link the node's parent to the child. */
464 if (!node->parent) {
465 /* Node is the root so we get a new root node. */
466 self->root = child;
467 } else if (node->parent->left == node) {
468 /* Node is a left child. */
469 node->parent->left = child;
470 } else {
471 /* Node is a right child. */
472 node->parent->right = child;
473 }
474 child->parent = node->parent;
475
476 /* Link node's right subtree to the child's left subtree. */
477 node->right = child->left;
478 if (node->right) {
479 node->right->parent = node;
480 }
481
482 /* Link the node to the child's left. */
483 node->parent = child;
484 child->left = node;
485}
486
487/*!
488 * \internal
489 * \brief Tree node rotation right.
490 * \since 12.0.0
491 *
492 * \param self Container holding node.
493 * \param node Node to perform a right rotation with.
494 *
495 * p p
496 * | Right rotation |
497 * Ch N
498 * / \ <--- / \
499 * a N Ch c
500 * / \ / \
501 * b c a b
502 *
503 * N = node
504 * Ch = child
505 * p = parent
506 * a,b,c = other nodes that are unaffected by the rotation.
507 *
508 * \note It is assumed that the node's left child exists.
509 */
510static void rb_rotate_right(struct ao2_container_rbtree *self, struct rbtree_node *node)
511{
512 struct rbtree_node *child; /*!< Node's left child. */
513
514 child = node->left;
515
516 /* Link the node's parent to the child. */
517 if (!node->parent) {
518 /* Node is the root so we get a new root node. */
519 self->root = child;
520 } else if (node->parent->right == node) {
521 /* Node is a right child. */
522 node->parent->right = child;
523 } else {
524 /* Node is a left child. */
525 node->parent->left = child;
526 }
527 child->parent = node->parent;
528
529 /* Link node's left subtree to the child's right subtree. */
530 node->left = child->right;
531 if (node->left) {
532 node->left->parent = node;
533 }
534
535 /* Link the node to the child's right. */
536 node->parent = child;
537 child->right = node;
538}
539
540/*!
541 * \internal
542 * \brief Create an empty copy of this container. (Debug version)
543 * \since 14.0.0
544 *
545 * \param self Container to operate upon.
546 * \param tag used for debugging.
547 * \param file Debug file name invoked from
548 * \param line Debug line invoked from
549 * \param func Debug function name invoked from
550 *
551 * \return empty-clone-container on success.
552 * \retval NULL on error.
553 */
555 const char *tag, const char *file, int line, const char *func)
556{
557 if (!__is_ao2_object(self, file, line, func)) {
558 return NULL;
559 }
560
562 self->common.sort_fn, self->common.cmp_fn, tag, file, line, func);
563}
564
565/*!
566 * \internal
567 * \brief Fixup the rbtree after deleting a node.
568 * \since 12.0.0
569 *
570 * \param self Container to operate upon.
571 * \param child Child of the node just deleted from the container.
572 *
573 * \note The child must be a dummy black node if there really
574 * was no child of the deleted node. Otherwise, the caller must
575 * pass in the parent node and which child was deleted. In
576 * addition, the fixup routine would be more complicated.
577 */
578static void rb_delete_fixup(struct ao2_container_rbtree *self, struct rbtree_node *child)
579{
580 struct rbtree_node *sibling;
581
582 while (self->root != child && !child->is_red) {
583 if (child->parent->left == child) {
584 /* Child is a left child. */
585 sibling = child->parent->right;
586 ast_assert(sibling != NULL);
587 if (sibling->is_red) {
588 /* Case 1: The child's sibling is red. */
589 AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[0]);
590 sibling->is_red = 0;
591 child->parent->is_red = 1;
592 rb_rotate_left(self, child->parent);
593 sibling = child->parent->right;
594 ast_assert(sibling != NULL);
595 }
596 /*
597 * The sibling is black. A black node must have two children,
598 * or one red child, or no children.
599 */
600 if ((!sibling->left || !sibling->left->is_red)
601 && (!sibling->right || !sibling->right->is_red)) {
602 /*
603 * Case 2: The sibling is black and both of its children are black.
604 *
605 * This case handles the two black children or no children
606 * possibilities of a black node.
607 */
608 AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[1]);
609 sibling->is_red = 1;
610 child = child->parent;
611 } else {
612 /* At this point the sibling has at least one red child. */
613 if (!sibling->right || !sibling->right->is_red) {
614 /*
615 * Case 3: The sibling is black, its left child is red, and its
616 * right child is black.
617 */
618 AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[2]);
619 ast_assert(sibling->left != NULL);
620 ast_assert(sibling->left->is_red);
621 sibling->left->is_red = 0;
622 sibling->is_red = 1;
623 rb_rotate_right(self, sibling);
624 sibling = child->parent->right;
625 ast_assert(sibling != NULL);
626 }
627 /* Case 4: The sibling is black and its right child is red. */
628 AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[3]);
629 sibling->is_red = child->parent->is_red;
630 child->parent->is_red = 0;
631 if (sibling->right) {
632 sibling->right->is_red = 0;
633 }
634 rb_rotate_left(self, child->parent);
635 child = self->root;
636 }
637 } else {
638 /* Child is a right child. */
639 sibling = child->parent->left;
640 ast_assert(sibling != NULL);
641 if (sibling->is_red) {
642 /* Case 1: The child's sibling is red. */
643 AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[0]);
644 sibling->is_red = 0;
645 child->parent->is_red = 1;
646 rb_rotate_right(self, child->parent);
647 sibling = child->parent->left;
648 ast_assert(sibling != NULL);
649 }
650 /*
651 * The sibling is black. A black node must have two children,
652 * or one red child, or no children.
653 */
654 if ((!sibling->right || !sibling->right->is_red)
655 && (!sibling->left || !sibling->left->is_red)) {
656 /*
657 * Case 2: The sibling is black and both of its children are black.
658 *
659 * This case handles the two black children or no children
660 * possibilities of a black node.
661 */
662 AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[1]);
663 sibling->is_red = 1;
664 child = child->parent;
665 } else {
666 /* At this point the sibling has at least one red child. */
667 if (!sibling->left || !sibling->left->is_red) {
668 /*
669 * Case 3: The sibling is black, its right child is red, and its
670 * left child is black.
671 */
672 AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[2]);
673 ast_assert(sibling->right != NULL);
674 ast_assert(sibling->right->is_red);
675 sibling->right->is_red = 0;
676 sibling->is_red = 1;
677 rb_rotate_left(self, sibling);
678 sibling = child->parent->left;
679 ast_assert(sibling != NULL);
680 }
681 /* Case 4: The sibling is black and its left child is red. */
682 AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[3]);
683 sibling->is_red = child->parent->is_red;
684 child->parent->is_red = 0;
685 if (sibling->left) {
686 sibling->left->is_red = 0;
687 }
688 rb_rotate_right(self, child->parent);
689 child = self->root;
690 }
691 }
692 }
693
694 /*
695 * Case 2 could leave the child node red and it needs to leave
696 * with it black.
697 *
698 * Case 4 sets the child node to the root which of course must
699 * be black.
700 */
701 child->is_red = 0;
702}
703
704/*!
705 * \internal
706 * \brief Delete the doomed node from this container.
707 * \since 12.0.0
708 *
709 * \param self Container to operate upon.
710 * \param doomed Container node to delete from the container.
711 */
712static void rb_delete_node(struct ao2_container_rbtree *self, struct rbtree_node *doomed)
713{
714 struct rbtree_node *child;
715 int need_fixup;
716
717 if (doomed->left && doomed->right) {
718 struct rbtree_node *next;
719 int is_red;
720
721 /*
722 * The doomed node has two children.
723 *
724 * Find the next child node and swap it with the doomed node in
725 * the tree.
726 */
727 AO2_DEVMODE_STAT(++self->stats.delete_children[2]);
728 next = rb_node_most_left(doomed->right);
729 SWAP(doomed->parent, next->parent);
730 SWAP(doomed->left, next->left);
731 SWAP(doomed->right, next->right);
732 is_red = doomed->is_red;
733 doomed->is_red = next->is_red;
734 next->is_red = is_red;
735
736 /* Link back in the next node. */
737 if (!next->parent) {
738 /* Doomed was the root so we get a new root node. */
739 self->root = next;
740 } else if (next->parent->left == doomed) {
741 /* Doomed was the left child. */
742 next->parent->left = next;
743 } else {
744 /* Doomed was the right child. */
745 next->parent->right = next;
746 }
747 next->left->parent = next;
748 if (next->right == next) {
749 /* The next node was the right child of doomed. */
750 next->right = doomed;
751 doomed->parent = next;
752 } else {
753 next->right->parent = next;
754 doomed->parent->left = doomed;
755 }
756
757 /* The doomed node has no left child now. */
758 ast_assert(doomed->left == NULL);
759
760 /*
761 * We don't have to link the right child back in with doomed
762 * since we are going to link it with doomed's parent anyway.
763 */
764 child = doomed->right;
765 } else {
766 /* Doomed has at most one child. */
767 child = doomed->left;
768 if (!child) {
769 child = doomed->right;
770 }
771 }
772 if (child) {
773 AO2_DEVMODE_STAT(++self->stats.delete_children[1]);
774 } else {
775 AO2_DEVMODE_STAT(++self->stats.delete_children[0]);
776 }
777
778 need_fixup = (!doomed->is_red && !self->common.destroying);
779 if (need_fixup && !child) {
780 /*
781 * Use the doomed node as a place holder node for the
782 * nonexistent child so we also don't have to pass to the fixup
783 * routine the parent and which child the deleted node came
784 * from.
785 */
786 rb_delete_fixup(self, doomed);
787 ast_assert(doomed->left == NULL);
788 ast_assert(doomed->right == NULL);
789 ast_assert(!doomed->is_red);
790 }
791
792 /* Link the child in place of doomed. */
793 if (!doomed->parent) {
794 /* Doomed was the root so we get a new root node. */
795 self->root = child;
796 } else if (doomed->parent->left == doomed) {
797 /* Doomed was the left child. */
798 doomed->parent->left = child;
799 } else {
800 /* Doomed was the right child. */
801 doomed->parent->right = child;
802 }
803 if (child) {
804 child->parent = doomed->parent;
805 if (need_fixup) {
806 rb_delete_fixup(self, child);
807 }
808 }
809
810 AO2_DEVMODE_STAT(--self->common.nodes);
811}
812
813/*!
814 * \internal
815 * \brief Destroy a rbtree container node.
816 * \since 12.0.0
817 *
818 * \param v_doomed Container node to destroy.
819 *
820 * \details
821 * The container node unlinks itself from the container as part
822 * of its destruction. The node must be destroyed while the
823 * container is already locked.
824 *
825 * \note The container must be locked when the node is
826 * unreferenced.
827 */
828static void rb_ao2_node_destructor(void *v_doomed)
829{
830 struct rbtree_node *doomed = v_doomed;
831
832 if (doomed->common.is_linked) {
833 struct ao2_container_rbtree *my_container;
834
835 /*
836 * Promote to write lock if not already there. Since
837 * adjust_lock() can potentially release and block waiting for a
838 * write lock, care must be taken to ensure that node references
839 * are released before releasing the container references.
840 *
841 * Node references held by an iterator can only be held while
842 * the iterator also holds a reference to the container. These
843 * node references must be unreferenced before the container can
844 * be unreferenced to ensure that the node will not get a
845 * negative reference and the destructor called twice for the
846 * same node.
847 */
848 my_container = (struct ao2_container_rbtree *) doomed->common.my_container;
849#ifdef AST_DEVMODE
850 is_ao2_object(my_container);
851#endif
852
853 __adjust_lock(my_container, AO2_LOCK_REQ_WRLOCK, 1);
854
855#if defined(AO2_DEBUG)
856 if (!my_container->common.destroying
858 ast_log(LOG_ERROR, "Container integrity failed before node deletion.\n");
859 }
860#endif /* defined(AO2_DEBUG) */
861 rb_delete_node(my_container, doomed);
862#if defined(AO2_DEBUG)
863 if (!my_container->common.destroying
865 ast_log(LOG_ERROR, "Container integrity failed after node deletion.\n");
866 }
867#endif /* defined(AO2_DEBUG) */
868 }
869
870 /*
871 * We could have an object in the node if the container is being
872 * destroyed or the node had not been linked in yet.
873 */
874 if (doomed->common.obj) {
876 }
877}
878
879/*!
880 * \internal
881 * \brief Create a new container node.
882 * \since 12.0.0
883 *
884 * \param self Container to operate upon.
885 * \param obj_new Object to put into the node.
886 * \param tag used for debugging.
887 * \param file Debug file name invoked from
888 * \param line Debug line invoked from
889 * \param func Debug function name invoked from
890 *
891 * \return initialized-node on success.
892 * \retval NULL on error.
893 */
894static struct rbtree_node *rb_ao2_new_node(struct ao2_container_rbtree *self, void *obj_new, const char *tag, const char *file, int line, const char *func)
895{
896 struct rbtree_node *node;
897
900 if (!node) {
901 return NULL;
902 }
903
904 __ao2_ref(obj_new, +1, tag ?: "Container node creation", file, line, func);
905 node->common.obj = obj_new;
906 node->common.my_container = (struct ao2_container *) self;
907
908 return node;
909}
910
911/*!
912 * \internal
913 * \brief Fixup the rbtree after inserting a node.
914 * \since 12.0.0
915 *
916 * \param self Container to operate upon.
917 * \param node Container node just inserted into the container.
918 *
919 * \note The just inserted node is red.
920 */
921static void rb_insert_fixup(struct ao2_container_rbtree *self, struct rbtree_node *node)
922{
923 struct rbtree_node *g_parent; /* Grand parent node. */
924
925 while (node->parent && node->parent->is_red) {
926 g_parent = node->parent->parent;
927
928 /* The grand parent must exist if the parent is red. */
929 ast_assert(g_parent != NULL);
930
931 if (node->parent == g_parent->left) {
932 /* The parent is a left child. */
933 if (g_parent->right && g_parent->right->is_red) {
934 /* Case 1: Push the black down from the grand parent node. */
935 AO2_DEVMODE_STAT(++self->stats.fixup_insert_left[0]);
936 g_parent->right->is_red = 0;
937 g_parent->left->is_red = 0;
938 g_parent->is_red = 1;
939
940 node = g_parent;
941 } else {
942 /* The uncle node is black. */
943 if (node->parent->right == node) {
944 /*
945 * Case 2: The node is a right child.
946 *
947 * Which node is the grand parent does not change.
948 */
949 AO2_DEVMODE_STAT(++self->stats.fixup_insert_left[1]);
950 node = node->parent;
951 rb_rotate_left(self, node);
952 }
953 /* Case 3: The node is a left child. */
954 AO2_DEVMODE_STAT(++self->stats.fixup_insert_left[2]);
955 node->parent->is_red = 0;
956 g_parent->is_red = 1;
957 rb_rotate_right(self, g_parent);
958 }
959 } else {
960 /* The parent is a right child. */
961 if (g_parent->left && g_parent->left->is_red) {
962 /* Case 1: Push the black down from the grand parent node. */
963 AO2_DEVMODE_STAT(++self->stats.fixup_insert_right[0]);
964 g_parent->left->is_red = 0;
965 g_parent->right->is_red = 0;
966 g_parent->is_red = 1;
967
968 node = g_parent;
969 } else {
970 /* The uncle node is black. */
971 if (node->parent->left == node) {
972 /*
973 * Case 2: The node is a left child.
974 *
975 * Which node is the grand parent does not change.
976 */
977 AO2_DEVMODE_STAT(++self->stats.fixup_insert_right[1]);
978 node = node->parent;
979 rb_rotate_right(self, node);
980 }
981 /* Case 3: The node is a right child. */
982 AO2_DEVMODE_STAT(++self->stats.fixup_insert_right[2]);
983 node->parent->is_red = 0;
984 g_parent->is_red = 1;
985 rb_rotate_left(self, g_parent);
986 }
987 }
988 }
989
990 /*
991 * The root could be red here because:
992 * 1) We just inserted the root node in an empty tree.
993 *
994 * 2) Case 1 could leave the root red if the grand parent were
995 * the root.
996 */
997 self->root->is_red = 0;
998}
999
1000/*!
1001 * \internal
1002 * \brief Insert a node into this container.
1003 * \since 12.0.0
1004 *
1005 * \param self Container to operate upon.
1006 * \param node Container node to insert into the container.
1007 *
1008 * \return \ref ao2_container_insert value.
1009 */
1011{
1012 int cmp;
1013 struct rbtree_node *cur;
1014 struct rbtree_node *next;
1015 ao2_sort_fn *sort_fn;
1016 uint32_t options;
1017 enum equal_node_bias bias;
1018
1019 if (!self->root) {
1020 /* The tree is empty. */
1021 self->root = node;
1023 }
1024
1025 sort_fn = self->common.sort_fn;
1026 options = self->common.options;
1028 default:
1031 bias = BIAS_FIRST;
1032 } else {
1033 bias = BIAS_LAST;
1034 }
1035 break;
1039 bias = BIAS_EQUAL;
1040 break;
1041 }
1042
1043 /*
1044 * New nodes are always colored red when initially inserted into
1045 * the tree. (Except for the root which is always black.)
1046 */
1047 node->is_red = 1;
1048
1049 /* Find node where normal insert would put a new node. */
1050 cur = self->root;
1051 for (;;) {
1052 if (!cur->common.obj) {
1053 /* Which direction do we go to insert this node? */
1054 if (rb_find_empty_direction(cur, sort_fn, node->common.obj, OBJ_SEARCH_OBJECT, bias)
1055 == GO_LEFT) {
1056 if (cur->left) {
1057 cur = cur->left;
1058 continue;
1059 }
1060
1061 /* Node becomes a left child */
1062 cur->left = node;
1063 node->parent = cur;
1064 rb_insert_fixup(self, node);
1066 }
1067 if (cur->right) {
1068 cur = cur->right;
1069 continue;
1070 }
1071
1072 /* Node becomes a right child */
1073 cur->right = node;
1074 node->parent = cur;
1075 rb_insert_fixup(self, node);
1077 }
1078 cmp = sort_fn(cur->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
1079 if (cmp > 0) {
1080 if (cur->left) {
1081 cur = cur->left;
1082 continue;
1083 }
1084
1085 /* Node becomes a left child */
1086 cur->left = node;
1087 node->parent = cur;
1088 rb_insert_fixup(self, node);
1090 } else if (cmp < 0) {
1091 if (cur->right) {
1092 cur = cur->right;
1093 continue;
1094 }
1095
1096 /* Node becomes a right child */
1097 cur->right = node;
1098 node->parent = cur;
1099 rb_insert_fixup(self, node);
1101 }
1102 switch (bias) {
1103 case BIAS_FIRST:
1104 /* Duplicate nodes unconditionally accepted. */
1105 if (cur->left) {
1106 cur = cur->left;
1107 continue;
1108 }
1109
1110 /* Node becomes a left child */
1111 cur->left = node;
1112 node->parent = cur;
1113 rb_insert_fixup(self, node);
1115 case BIAS_EQUAL:
1116 break;
1117 case BIAS_LAST:
1118 /* Duplicate nodes unconditionally accepted. */
1119 if (cur->right) {
1120 cur = cur->right;
1121 continue;
1122 }
1123
1124 /* Node becomes a right child */
1125 cur->right = node;
1126 node->parent = cur;
1127 rb_insert_fixup(self, node);
1129 }
1130
1131 break;
1132 }
1133
1134 /* Node is a duplicate */
1136 default:
1138 ast_assert(0);/* Case already handled by BIAS_FIRST/BIAS_LAST. */
1141 /* Reject all objects with the same key. */
1144 if (cur->common.obj == node->common.obj) {
1145 /* Reject inserting the same object */
1147 }
1148 next = cur;
1150 /* Search to end of duplicates for the same object. */
1151 for (;;) {
1152 next = rb_node_next_full(next);
1153 if (!next) {
1154 break;
1155 }
1156 if (next->common.obj == node->common.obj) {
1157 /* Reject inserting the same object */
1159 }
1160 cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
1161 if (cmp) {
1162 break;
1163 }
1164 }
1165
1166 /* Find first duplicate node. */
1167 for (;;) {
1168 next = rb_node_prev_full(cur);
1169 if (!next) {
1170 break;
1171 }
1172 if (next->common.obj == node->common.obj) {
1173 /* Reject inserting the same object */
1175 }
1176 cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
1177 if (cmp) {
1178 break;
1179 }
1180 cur = next;
1181 }
1182 if (!cur->left) {
1183 /* Node becomes a left child */
1184 cur->left = node;
1185 } else {
1186 /* Node becomes a right child */
1187 cur = rb_node_most_right(cur->left);
1188 cur->right = node;
1189 }
1190 } else {
1191 /* Search to beginning of duplicates for the same object. */
1192 for (;;) {
1193 next = rb_node_prev_full(next);
1194 if (!next) {
1195 break;
1196 }
1197 if (next->common.obj == node->common.obj) {
1198 /* Reject inserting the same object */
1200 }
1201 cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
1202 if (cmp) {
1203 break;
1204 }
1205 }
1206
1207 /* Find last duplicate node. */
1208 for (;;) {
1209 next = rb_node_next_full(cur);
1210 if (!next) {
1211 break;
1212 }
1213 if (next->common.obj == node->common.obj) {
1214 /* Reject inserting the same object */
1216 }
1217 cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
1218 if (cmp) {
1219 break;
1220 }
1221 cur = next;
1222 }
1223 if (!cur->right) {
1224 /* Node becomes a right child */
1225 cur->right = node;
1226 } else {
1227 /* Node becomes a left child */
1228 cur = rb_node_most_left(cur->right);
1229 cur->left = node;
1230 }
1231 }
1232 break;
1234 SWAP(cur->common.obj, node->common.obj);
1235 ao2_ref(node, -1);
1237 }
1238
1239 /* Complete inserting duplicate node. */
1240 node->parent = cur;
1241 rb_insert_fixup(self, node);
1243}
1244
1245/*!
1246 * \internal
1247 * \brief Find the next rbtree container node in a traversal.
1248 * \since 12.0.0
1249 *
1250 * \param self Container to operate upon.
1251 * \param state Traversal state to restart rbtree container traversal.
1252 * \param prev Previous node returned by the traversal search functions.
1253 * The ref ownership is passed back to this function.
1254 *
1255 * \return node-ptr of found node (Reffed).
1256 * \retval NULL when no node found.
1257 */
1259{
1260 struct rbtree_node *node;
1261 void *arg;
1262 enum search_flags flags;
1263 int cmp;
1264
1265 arg = state->arg;
1266 flags = state->flags;
1267
1268 node = prev;
1269 for (;;) {
1270 /* Find next node in traversal order. */
1271 switch (flags & OBJ_ORDER_MASK) {
1272 default:
1275 break;
1278 break;
1279 case OBJ_ORDER_PRE:
1281 break;
1282 case OBJ_ORDER_POST:
1284 break;
1285 }
1286 if (!node) {
1287 /* No more nodes left to traverse. */
1288 break;
1289 }
1290 if (!node->common.obj) {
1291 /* Node is empty */
1292 continue;
1293 }
1294
1295 if (state->sort_fn) {
1296 /* Filter node through the sort_fn */
1297 cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
1298 if (cmp) {
1299 /* No more nodes in this container are possible to match. */
1300 break;
1301 }
1302 }
1303
1304 /* We have the next traversal node */
1305 ao2_ref(node, +1);
1306
1307 /*
1308 * Dereferencing the prev node may result in our next node
1309 * object being removed by another thread. This could happen if
1310 * the container uses RW locks and the container was read
1311 * locked.
1312 */
1313 ao2_ref(prev, -1);
1314 if (node->common.obj) {
1315 return node;
1316 }
1317 prev = node;
1318 }
1319
1320 /* No more nodes in the container left to traverse. */
1321 ao2_ref(prev, -1);
1322 return NULL;
1323}
1324
1325/*!
1326 * \internal
1327 * \brief Find an initial matching node.
1328 * \since 12.0.0
1329 *
1330 * \param self Container to operate upon.
1331 * \param obj_right pointer to the (user-defined part) of an object.
1332 * \param flags flags from ao2_callback()
1333 * OBJ_SEARCH_OBJECT - if set, 'obj_right', is an object.
1334 * OBJ_SEARCH_KEY - if set, 'obj_right', is a search key item that is not an object.
1335 * OBJ_SEARCH_PARTIAL_KEY - if set, 'obj_right', is a partial search key item that is not an object.
1336 * \param bias How to bias search direction for duplicates
1337 *
1338 * \return node on success.
1339 * \retval NULL if not found.
1340 */
1341static struct rbtree_node *rb_find_initial(struct ao2_container_rbtree *self, void *obj_right, enum search_flags flags, enum equal_node_bias bias)
1342{
1343 int cmp;
1344 enum search_flags sort_flags;
1345 struct rbtree_node *node;
1346 struct rbtree_node *next = NULL;
1347 ao2_sort_fn *sort_fn;
1348
1349 sort_flags = flags & OBJ_SEARCH_MASK;
1350 sort_fn = self->common.sort_fn;
1351
1352 /* Find node where normal search would find it. */
1353 node = self->root;
1354 if (!node) {
1355 return NULL;
1356 }
1357 for (;;) {
1358 if (!node->common.obj) {
1359 /* Which direction do we go to find the node? */
1360 if (rb_find_empty_direction(node, sort_fn, obj_right, sort_flags, bias)
1361 == GO_LEFT) {
1362 next = node->left;
1363 } else {
1364 next = node->right;
1365 }
1366 if (!next) {
1367 switch (bias) {
1368 case BIAS_FIRST:
1369 /* Check successor node for match. */
1370 next = rb_node_next_full(node);
1371 break;
1372 case BIAS_EQUAL:
1373 break;
1374 case BIAS_LAST:
1375 /* Check previous node for match. */
1376 next = rb_node_prev_full(node);
1377 break;
1378 }
1379 if (next) {
1380 cmp = sort_fn(next->common.obj, obj_right, sort_flags);
1381 if (cmp == 0) {
1382 /* Found the first/last matching node. */
1383 return next;
1384 }
1385 next = NULL;
1386 }
1387
1388 /* No match found. */
1389 return next;
1390 }
1391 } else {
1392 cmp = sort_fn(node->common.obj, obj_right, sort_flags);
1393 if (cmp > 0) {
1394 next = node->left;
1395 } else if (cmp < 0) {
1396 next = node->right;
1397 } else {
1398 switch (bias) {
1399 case BIAS_FIRST:
1400 next = node->left;
1401 break;
1402 case BIAS_EQUAL:
1403 return node;
1404 case BIAS_LAST:
1405 next = node->right;
1406 break;
1407 }
1408 if (!next) {
1409 /* Found the first/last matching node. */
1410 return node;
1411 }
1412 }
1413 if (!next) {
1414 switch (bias) {
1415 case BIAS_FIRST:
1416 if (cmp < 0) {
1417 /* Check successor node for match. */
1418 next = rb_node_next_full(node);
1419 }
1420 break;
1421 case BIAS_EQUAL:
1422 break;
1423 case BIAS_LAST:
1424 if (cmp > 0) {
1425 /* Check previous node for match. */
1426 next = rb_node_prev_full(node);
1427 }
1428 break;
1429 }
1430 if (next) {
1431 cmp = sort_fn(next->common.obj, obj_right, sort_flags);
1432 if (cmp == 0) {
1433 /* Found the first/last matching node. */
1434 return next;
1435 }
1436 }
1437
1438 /* No match found. */
1439 return NULL;
1440 }
1441 }
1442 node = next;
1443 }
1444}
1445
1446/*!
1447 * \internal
1448 * \brief Find the first rbtree container node in a traversal.
1449 * \since 12.0.0
1450 *
1451 * \param self Container to operate upon.
1452 * \param flags search_flags to control traversing the container
1453 * \param arg Comparison callback arg parameter.
1454 * \param state Traversal state to restart rbtree container traversal.
1455 *
1456 * \return node-ptr of found node (Reffed).
1457 * \retval NULL when no node found.
1458 */
1459static struct rbtree_node *rb_ao2_find_first(struct ao2_container_rbtree *self, enum search_flags flags, void *arg, struct rbtree_traversal_state *state)
1460{
1461 struct rbtree_node *node;
1462 enum equal_node_bias bias;
1463
1464 if (self->common.destroying) {
1465 /* Force traversal to be post order for tree destruction. */
1467 }
1468
1469 memset(state, 0, sizeof(*state));
1470 state->arg = arg;
1471 state->flags = flags;
1472
1473 switch (flags & OBJ_SEARCH_MASK) {
1474 case OBJ_SEARCH_OBJECT:
1475 case OBJ_SEARCH_KEY:
1477 /* We are asked to do a directed search. */
1478 state->sort_fn = self->common.sort_fn;
1479 break;
1480 default:
1481 /* Don't know, let's visit all nodes */
1482 state->sort_fn = NULL;
1483 break;
1484 }
1485
1486 if (!self->root) {
1487 /* Tree is empty. */
1488 return NULL;
1489 }
1490
1491 /* Find first traversal node. */
1492 switch (flags & OBJ_ORDER_MASK) {
1493 default:
1495 if (!state->sort_fn) {
1496 /* Find left most child. */
1497 node = rb_node_most_left(self->root);
1498 if (!node->common.obj) {
1500 if (!node) {
1501 return NULL;
1502 }
1503 }
1504 break;
1505 }
1506
1507 /* Search for initial node. */
1511 if ((flags & OBJ_SEARCH_MASK) != OBJ_SEARCH_PARTIAL_KEY) {
1512 /* There are no duplicates allowed. */
1513 bias = BIAS_EQUAL;
1514 break;
1515 }
1516 /* Fall through */
1517 default:
1520 /* Find first duplicate node. */
1521 bias = BIAS_FIRST;
1522 break;
1523 }
1524 node = rb_find_initial(self, arg, flags, bias);
1525 if (!node) {
1526 return NULL;
1527 }
1528 break;
1530 if (!state->sort_fn) {
1531 /* Find right most child. */
1532 node = rb_node_most_right(self->root);
1533 if (!node->common.obj) {
1535 if (!node) {
1536 return NULL;
1537 }
1538 }
1539 break;
1540 }
1541
1542 /* Search for initial node. */
1546 if ((flags & OBJ_SEARCH_MASK) != OBJ_SEARCH_PARTIAL_KEY) {
1547 /* There are no duplicates allowed. */
1548 bias = BIAS_EQUAL;
1549 break;
1550 }
1551 /* Fall through */
1552 default:
1555 /* Find last duplicate node. */
1556 bias = BIAS_LAST;
1557 break;
1558 }
1559 node = rb_find_initial(self, arg, flags, bias);
1560 if (!node) {
1561 return NULL;
1562 }
1563 break;
1564 case OBJ_ORDER_PRE:
1565 /* This is a tree structure traversal so we must visit all nodes. */
1566 state->sort_fn = NULL;
1567
1568 node = self->root;
1569
1570 /* Find a non-empty node. */
1571 while (!node->common.obj) {
1573 if (!node) {
1574 return NULL;
1575 }
1576 }
1577 break;
1578 case OBJ_ORDER_POST:
1579 /* This is a tree structure traversal so we must visit all nodes. */
1580 state->sort_fn = NULL;
1581
1582 /* Find the left most childless node. */
1583 node = self->root;
1584 for (;;) {
1586 if (!node->right) {
1587 /* This node has no children. */
1588 break;
1589 }
1590 node = node->right;
1591 }
1592
1593 /* Find a non-empty node. */
1594 while (!node->common.obj) {
1596 if (!node) {
1597 return NULL;
1598 }
1599 }
1600 break;
1601 }
1602
1603 /* We have the first traversal node */
1604 ao2_ref(node, +1);
1605 return node;
1606}
1607
1608/*!
1609 * \internal
1610 * \brief Find the next non-empty iteration node in the container.
1611 * \since 12.0.0
1612 *
1613 * \param self Container to operate upon.
1614 * \param node Previous node returned by the iterator.
1615 * \param flags search_flags to control iterating the container.
1616 * Only AO2_ITERATOR_DESCENDING is useful by the method.
1617 *
1618 * \note The container is already locked.
1619 *
1620 * \return node on success.
1621 * \retval NULL on error or no more nodes in the container.
1622 */
1624{
1625 if (flags & AO2_ITERATOR_DESCENDING) {
1626 if (!node) {
1627 /* Find right most node. */
1628 if (!self->root) {
1629 return NULL;
1630 }
1631 node = rb_node_most_right(self->root);
1632 if (node->common.obj) {
1633 /* Found a non-empty node. */
1634 return node;
1635 }
1636 }
1637 /* Find next non-empty node. */
1639 } else {
1640 if (!node) {
1641 /* Find left most node. */
1642 if (!self->root) {
1643 return NULL;
1644 }
1645 node = rb_node_most_left(self->root);
1646 if (node->common.obj) {
1647 /* Found a non-empty node. */
1648 return node;
1649 }
1650 }
1651 /* Find next non-empty node. */
1653 }
1654
1655 return node;
1656}
1657
1658/*!
1659 * \internal
1660 *
1661 * \brief Destroy this container.
1662 * \since 12.0.0
1663 *
1664 * \param self Container to operate upon.
1665 */
1666static void rb_ao2_destroy(struct ao2_container_rbtree *self)
1667{
1668 /* Check that the container no longer has any nodes */
1669 if (self->root) {
1670 ast_log(LOG_ERROR, "Node ref leak. Red-Black tree container still has nodes!\n");
1671 ast_assert(0);
1672 }
1673}
1674
1675#if defined(AO2_DEBUG)
1676/*!
1677 * \internal
1678 * \brief Display contents of the specified container.
1679 * \since 12.0.0
1680 *
1681 * \param self Container to dump.
1682 * \param where User data needed by prnt to determine where to put output.
1683 * \param prnt Print output callback function to use.
1684 * \param prnt_obj Callback function to print the given object's key. (NULL if not available)
1685 */
1686static void rb_ao2_dump(struct ao2_container_rbtree *self, void *where, ao2_prnt_fn *prnt, ao2_prnt_obj_fn *prnt_obj)
1687{
1688#define FORMAT "%16s, %16s, %16s, %16s, %5s, %16s, %s\n"
1689#define FORMAT2 "%16p, %16p, %16p, %16p, %5s, %16p, "
1690
1691 struct rbtree_node *node;
1692
1693 prnt(where, FORMAT, "Node", "Parent", "Left", "Right", "Color", "Obj", "Key");
1694 for (node = self->root; node; node = rb_node_pre(node)) {
1695 prnt(where, FORMAT2,
1696 node,
1697 node->parent,
1698 node->left,
1699 node->right,
1700 node->is_red ? "Red" : "Black",
1701 node->common.obj);
1702 if (node->common.obj && prnt_obj) {
1703 prnt_obj(node->common.obj, where, prnt);
1704 }
1705 prnt(where, "\n");
1706 }
1707
1708#undef FORMAT
1709#undef FORMAT2
1710}
1711#endif /* defined(AO2_DEBUG) */
1712
1713#if defined(AO2_DEBUG)
1714/*!
1715 * \internal
1716 * \brief Display statistics of the specified container.
1717 * \since 12.0.0
1718 *
1719 * \param self Container to display statistics.
1720 * \param where User data needed by prnt to determine where to put output.
1721 * \param prnt Print output callback function to use.
1722 *
1723 * \note The container is already locked for reading.
1724 */
1725static void rb_ao2_stats(struct ao2_container_rbtree *self, void *where, ao2_prnt_fn *prnt)
1726{
1727 int idx;
1728
1729 for (idx = 0; idx < ARRAY_LEN(self->stats.fixup_insert_left); ++idx) {
1730 prnt(where, "Number of left insert fixups case %d: %d\n", idx + 1,
1731 self->stats.fixup_insert_left[idx]);
1732 }
1733 for (idx = 0; idx < ARRAY_LEN(self->stats.fixup_insert_right); ++idx) {
1734 prnt(where, "Number of right insert fixups case %d: %d\n", idx + 1,
1735 self->stats.fixup_insert_right[idx]);
1736 }
1737
1738 for (idx = 0; idx < ARRAY_LEN(self->stats.delete_children); ++idx) {
1739 prnt(where, "Number of nodes deleted with %d children: %d\n", idx,
1740 self->stats.delete_children[idx]);
1741 }
1742 for (idx = 0; idx < ARRAY_LEN(self->stats.fixup_delete_left); ++idx) {
1743 prnt(where, "Number of left delete fixups case %d: %d\n", idx + 1,
1744 self->stats.fixup_delete_left[idx]);
1745 }
1746 for (idx = 0; idx < ARRAY_LEN(self->stats.fixup_delete_right); ++idx) {
1747 prnt(where, "Number of right delete fixups case %d: %d\n", idx + 1,
1748 self->stats.fixup_delete_right[idx]);
1749 }
1750}
1751#endif /* defined(AO2_DEBUG) */
1752
1753#if defined(AO2_DEBUG)
1754/*!
1755 * \internal
1756 * \brief Check the black height of the given node.
1757 * \since 12.0.0
1758 *
1759 * \param node Node to check black height.
1760 *
1761 * \return black-height of node on success.
1762 * \retval -1 on error. Node black height did not balance.
1763 */
1764static int rb_check_black_height(struct rbtree_node *node)
1765{
1766 int height_left;
1767 int height_right;
1768
1769 if (!node) {
1770 /* A NULL child is a black node. */
1771 return 0;
1772 }
1773
1774 height_left = rb_check_black_height(node->left);
1775 if (height_left < 0) {
1776 return -1;
1777 }
1778 height_right = rb_check_black_height(node->right);
1779 if (height_right < 0) {
1780 return -1;
1781 }
1782 if (height_left != height_right) {
1784 "Tree node black height of children does not match! L:%d != R:%d\n",
1785 height_left, height_right);
1786 return -1;
1787 }
1788 if (!node->is_red) {
1789 /* The node itself is black. */
1790 ++height_left;
1791 }
1792 return height_left;
1793}
1794
1795#endif /* defined(AO2_DEBUG) */
1796
1797#if defined(AO2_DEBUG)
1798/*!
1799 * \internal
1800 * \brief Perform an integrity check on the specified container.
1801 * \since 12.0.0
1802 *
1803 * \param self Container to check integrity.
1804 *
1805 * \note The container is already locked for reading.
1806 *
1807 * \retval 0 on success.
1808 * \retval -1 on error.
1809 */
1810static int rb_ao2_integrity(struct ao2_container_rbtree *self)
1811{
1812 int res;
1813 int count_node;
1814 int count_obj;
1815 void *obj_last;
1816 struct rbtree_node *node;
1817
1818 res = 0;
1819
1820 count_node = 0;
1821 count_obj = 0;
1822
1823 /*
1824 * See the properties listed at struct rbtree_node definition.
1825 *
1826 * The rbtree properties 1 and 3 are not testable.
1827 *
1828 * Property 1 is not testable because we are not rebalancing at
1829 * this time so all nodes are either red or black.
1830 *
1831 * Property 3 is not testable because it is the definition of a
1832 * NULL child.
1833 */
1834 if (self->root) {
1835 /* Check tree links. */
1836 if (self->root->parent) {
1837 if (self->root->parent == self->root) {
1838 ast_log(LOG_ERROR, "Tree root parent pointer points to itself!\n");
1839 } else {
1840 ast_log(LOG_ERROR, "Tree root is not a root node!\n");
1841 }
1842 return -1;
1843 }
1844 if (self->root->is_red) {
1845 /* Violation rbtree property 2. */
1846 ast_log(LOG_ERROR, "Tree root is red!\n");
1847 res = -1;
1848 }
1849 node = self->root;
1850 do {
1851 if (node->left) {
1852 if (node->left == node) {
1853 ast_log(LOG_ERROR, "Tree node's left pointer points to itself!\n");
1854 return -1;
1855 }
1856 if (node->left->parent != node) {
1857 ast_log(LOG_ERROR, "Tree node's left child does not link back!\n");
1858 return -1;
1859 }
1860 }
1861 if (node->right) {
1862 if (node->right == node) {
1863 ast_log(LOG_ERROR, "Tree node's right pointer points to itself!\n");
1864 return -1;
1865 }
1866 if (node->right->parent != node) {
1867 ast_log(LOG_ERROR, "Tree node's right child does not link back!\n");
1868 return -1;
1869 }
1870 }
1871
1872 /* Check red/black node flags. */
1873 if (node->is_red) {
1874 /* A red node must have two black children or no children. */
1875 if (node->left && node->right) {
1876 /* Node has two children. */
1877 if (node->left->is_red) {
1878 /* Violation rbtree property 4. */
1879 ast_log(LOG_ERROR, "Tree node is red and its left child is red!\n");
1880 res = -1;
1881 }
1882 if (node->right->is_red) {
1883 /* Violation rbtree property 4. */
1884 ast_log(LOG_ERROR, "Tree node is red and its right child is red!\n");
1885 res = -1;
1886 }
1887 } else if (node->left || node->right) {
1888 /*
1889 * Violation rbtree property 4 if the child is red.
1890 * Violation rbtree property 5 if the child is black.
1891 */
1892 ast_log(LOG_ERROR, "Tree node is red and it only has one child!\n");
1893 res = -1;
1894 }
1895 } else {
1896 /*
1897 * A black node must have two children, or one red child, or no
1898 * children. If the black node has two children and only one of
1899 * them is red, that red child must have two children.
1900 */
1901 if (node->left && node->right) {
1902 /* Node has two children. */
1903 if (node->left->is_red != node->right->is_red) {
1904 /* The children are not the same color. */
1905 struct rbtree_node *red;
1906
1907 if (node->left->is_red) {
1908 red = node->left;
1909 } else {
1910 red = node->right;
1911 }
1912 if (!red->left || !red->right) {
1913 /* Violation rbtree property 5. */
1915 "Tree node is black and the red child does not have two children!\n");
1916 res = -1;
1917 }
1918 }
1919 } else if ((node->left && !node->left->is_red)
1920 || (node->right && !node->right->is_red)) {
1921 /* Violation rbtree property 5. */
1922 ast_log(LOG_ERROR, "Tree node is black and its only child is black!\n");
1923 res = -1;
1924 }
1925 }
1926
1927 /* Count nodes and objects. */
1928 ++count_node;
1929 if (node->common.obj) {
1930 ++count_obj;
1931 }
1932
1934 } while (node);
1935
1936 /* Check node key sort order. */
1937 obj_last = NULL;
1938 for (node = rb_node_most_left(self->root); node; node = rb_node_next(node)) {
1939 if (!node->common.obj) {
1940 /* Node is empty. */
1941 continue;
1942 }
1943
1944 if (obj_last) {
1945 if (self->common.sort_fn(obj_last, node->common.obj, OBJ_SEARCH_OBJECT) > 0) {
1946 ast_log(LOG_ERROR, "Tree nodes are out of sorted order!\n");
1947 return -1;
1948 }
1949 }
1950 obj_last = node->common.obj;
1951 }
1952
1953 /* Completely check property 5 */
1954 if (!res && rb_check_black_height(self->root) < 0) {
1955 /* Violation rbtree property 5. */
1956 res = -1;
1957 }
1958 }
1959
1960 /* Check total obj count. */
1961 if (count_obj != ao2_container_count(&self->common)) {
1962 ast_log(LOG_ERROR, "Total object count does not match ao2_container_count()!\n");
1963 return -1;
1964 }
1965
1966 /* Check total node count. */
1967 if (count_node != self->common.nodes) {
1968 ast_log(LOG_ERROR, "Total node count of %d does not match stat of %d!\n",
1969 count_node, self->common.nodes);
1970 return -1;
1971 }
1972
1973 return res;
1974}
1975#endif /* defined(AO2_DEBUG) */
1976
1977/*! rbtree container virtual method table. */
1986#if defined(AO2_DEBUG)
1987 .dump = (ao2_container_display) rb_ao2_dump,
1988 .stats = (ao2_container_statistics) rb_ao2_stats,
1989 .integrity = (ao2_container_integrity) rb_ao2_integrity,
1990#endif /* defined(AO2_DEBUG) */
1991};
1992
1993/*!
1994 * \brief Initialize a rbtree container.
1995 *
1996 * \param self Container to initialize.
1997 * \param options Container behaviour options (See enum ao2_container_opts)
1998 * \param sort_fn Pointer to a sort function.
1999 * \param cmp_fn Pointer to a compare function used by ao2_find.
2000 *
2001 * \return A pointer to a struct container.
2002 */
2005{
2006 if (!self) {
2007 return NULL;
2008 }
2009
2010 self->common.v_table = &v_table_rbtree;
2011 self->common.sort_fn = sort_fn;
2012 self->common.cmp_fn = cmp_fn;
2013 self->common.options = options;
2014
2015#ifdef AO2_DEBUG
2016 ast_atomic_fetchadd_int(&ao2.total_containers, 1);
2017#endif /* defined(AO2_DEBUG) */
2018
2019 return (struct ao2_container *) self;
2020}
2021
2022struct ao2_container *__ao2_container_alloc_rbtree(unsigned int ao2_options, unsigned int container_options,
2024 const char *tag, const char *file, int line, const char *func)
2025{
2026 struct ao2_container_rbtree *self;
2027
2028 if (!sort_fn) {
2029 /* Sanity checks. */
2030 ast_log(__LOG_ERROR, file, line, func, "Missing sort_fn()!\n");
2031 return NULL;
2032 }
2033
2034 self = __ao2_alloc(sizeof(*self), container_destruct, ao2_options,
2035 tag ?: __PRETTY_FUNCTION__, file, line, func);
2036 return rb_ao2_container_init(self, container_options, sort_fn, cmp_fn);
2037}
Prototypes for public functions only of internal interest,.
Asterisk main include file. File version handling, generic pbx functions.
enum ao2_lock_req __adjust_lock(void *user_data, enum ao2_lock_req lock_how, int keep_stronger)
Definition: astobj2.c:425
#define ast_log
Definition: astobj2.c:42
void() ao2_prnt_obj_fn(void *v_obj, void *where, ao2_prnt_fn *prnt)
Print object key.
Definition: astobj2.h:1445
unsigned int ao2_options_get(void *obj)
Retrieve the ao2 options used to create the object.
Definition: astobj2.c:781
@ AO2_ALLOC_OPT_LOCK_NOLOCK
Definition: astobj2.h:367
@ AO2_ALLOC_OPT_NO_REF_DEBUG
Definition: astobj2.h:378
int ao2_container_check(struct ao2_container *self, enum search_flags flags)
Perform an integrity check on the specified container.
@ AO2_LOCK_REQ_WRLOCK
Definition: astobj2.h:706
int ao2_container_count(struct ao2_container *c)
Returns the number of elements in a container.
int() ao2_callback_fn(void *obj, void *arg, int flags)
Type of a generic callback function.
Definition: astobj2.h:1226
ao2_iterator_flags
Definition: astobj2.h:1835
@ AO2_ITERATOR_DESCENDING
Definition: astobj2.h:1875
int() ao2_sort_fn(const void *obj_left, const void *obj_right, int flags)
Type of generic container sort function.
Definition: astobj2.h:1276
#define ao2_ref(o, delta)
Reference/unreference an object and return the old refcount.
Definition: astobj2.h:459
#define ao2_alloc_options(data_size, destructor_fn, options)
Definition: astobj2.h:404
int __ao2_ref(void *o, int delta, const char *tag, const char *file, int line, const char *func)
Definition: astobj2.c:498
search_flags
Flags passed to ao2_callback_fn(), ao2_hash_fn(), and ao2_sort_fn() to modify behaviour.
Definition: astobj2.h:1034
@ OBJ_ORDER_MASK
Traverse order option field mask.
Definition: astobj2.h:1119
@ OBJ_SEARCH_PARTIAL_KEY
The arg parameter is a partial search key similar to OBJ_SEARCH_KEY.
Definition: astobj2.h:1116
@ OBJ_ORDER_DESCENDING
Traverse in descending order (Last to first container object)
Definition: astobj2.h:1123
@ OBJ_SEARCH_OBJECT
The arg parameter is an object of the same type.
Definition: astobj2.h:1087
@ OBJ_ORDER_PRE
Traverse in pre-order (Node then children, for tree container)
Definition: astobj2.h:1132
@ OBJ_ORDER_ASCENDING
Traverse in ascending order (First to last container object)
Definition: astobj2.h:1121
@ OBJ_NOLOCK
Assume that the ao2_container is already locked.
Definition: astobj2.h:1063
@ OBJ_NODATA
Definition: astobj2.h:1044
@ OBJ_SEARCH_MASK
Search option field mask.
Definition: astobj2.h:1072
@ OBJ_MULTIPLE
Definition: astobj2.h:1049
@ OBJ_UNLINK
Definition: astobj2.h:1039
@ OBJ_ORDER_POST
Traverse in post-order (Children then node, for tree container)
Definition: astobj2.h:1141
@ OBJ_SEARCH_KEY
The arg parameter is a search key, but is not an object.
Definition: astobj2.h:1101
void * __ao2_alloc(size_t data_size, ao2_destructor_fn destructor_fn, unsigned int options, const char *tag, const char *file, int line, const char *func) attribute_warn_unused_result
Definition: astobj2.c:768
void() ao2_prnt_fn(void *where, const char *fmt,...)
Print output.
Definition: astobj2.h:1435
@ AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT
Reject duplicate objects in container.
Definition: astobj2.h:1201
@ AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN
Insert objects at the beginning of the container. (Otherwise it is the opposite; insert at the end....
Definition: astobj2.h:1172
@ AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW
Allow objects with duplicate keys in container.
Definition: astobj2.h:1181
@ AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT
Reject objects with duplicate keys in container.
Definition: astobj2.h:1188
@ AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE
Replace objects with duplicate keys in container.
Definition: astobj2.h:1211
@ AO2_CONTAINER_ALLOC_OPT_DUPS_MASK
The ao2 container objects with duplicate keys option field mask.
Definition: astobj2.h:1177
void container_destruct(void *_c)
Common, private definitions for astobj2 containers.
void(* ao2_container_statistics)(struct ao2_container *self, void *where, ao2_prnt_fn *prnt)
Display statistics of the specified container.
void(* ao2_container_destroy_fn)(struct ao2_container *self)
Destroy this container.
int(* ao2_container_integrity)(struct ao2_container *self)
Perform an integrity check on the specified container.
struct ao2_container_node *(* ao2_container_new_node_fn)(struct ao2_container *self, void *obj_new, const char *tag, const char *file, int line, const char *func)
Create a new container node.
void(* ao2_container_display)(struct ao2_container *self, void *where, ao2_prnt_fn *prnt, ao2_prnt_obj_fn *prnt_obj)
Display contents of the specified container.
#define __container_unlink_node(node, flags)
#define AO2_TRAVERSAL_STATE_SIZE
struct ao2_container_node *(* ao2_iterator_next_fn)(struct ao2_container *self, struct ao2_container_node *prev, enum ao2_iterator_flags flags)
Find the next non-empty iteration node in the container.
struct ao2_container_node *(* ao2_container_find_first_fn)(struct ao2_container *self, enum search_flags flags, void *arg, void *v_state)
Find the first container node in a traversal.
struct ao2_container_node *(* ao2_container_find_next_fn)(struct ao2_container *self, void *v_state, struct ao2_container_node *prev)
Find the next container node in a traversal.
struct ao2_container *(* ao2_container_alloc_empty_clone_fn)(struct ao2_container *self, const char *tag, const char *file, int line, const char *func)
Create an empty copy of this container.
@ AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED
@ AO2_CONTAINER_INSERT_NODE_REJECTED
@ AO2_CONTAINER_INSERT_NODE_INSERTED
@ AO2_UNLINK_NODE_UNLINK_OBJECT
enum ao2_container_insert(* ao2_container_insert_fn)(struct ao2_container *self, struct ao2_container_node *node)
Insert a node into this container.
Common, private definitions for astobj2.
#define is_ao2_object(user_data)
#define AO2_DEVMODE_STAT(stat)
#define __is_ao2_object(user_data, file, line, func)
static void rb_rotate_right(struct ao2_container_rbtree *self, struct rbtree_node *node)
static void rb_insert_fixup(struct ao2_container_rbtree *self, struct rbtree_node *node)
struct ao2_container * __ao2_container_alloc_rbtree(unsigned int ao2_options, unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn, const char *tag, const char *file, int line, const char *func)
static enum empty_node_direction rb_find_empty_direction(struct rbtree_node *empty, ao2_sort_fn *sort_fn, void *obj_right, enum search_flags flags, enum equal_node_bias bias)
static struct rbtree_node * rb_node_prev_full(struct rbtree_node *node)
equal_node_bias
@ BIAS_LAST
@ BIAS_EQUAL
@ BIAS_FIRST
static struct rbtree_node * rb_node_post(struct rbtree_node *node)
static struct rbtree_node * rb_ao2_find_next(struct ao2_container_rbtree *self, struct rbtree_traversal_state *state, struct rbtree_node *prev)
static void rb_ao2_destroy(struct ao2_container_rbtree *self)
static struct rbtree_node * rb_node_most_left(struct rbtree_node *node)
static void rb_rotate_left(struct ao2_container_rbtree *self, struct rbtree_node *node)
static struct rbtree_node * rb_node_next(struct rbtree_node *node)
static struct rbtree_node * rb_ao2_new_node(struct ao2_container_rbtree *self, void *obj_new, const char *tag, const char *file, int line, const char *func)
static struct ao2_container * rb_ao2_container_init(struct ao2_container_rbtree *self, unsigned int options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
Initialize a rbtree container.
static enum ao2_container_insert rb_ao2_insert_node(struct ao2_container_rbtree *self, struct rbtree_node *node)
static struct rbtree_node * rb_ao2_iterator_next(struct ao2_container_rbtree *self, struct rbtree_node *node, enum ao2_iterator_flags flags)
static struct ao2_container * rb_ao2_alloc_empty_clone(struct ao2_container_rbtree *self, const char *tag, const char *file, int line, const char *func)
static struct rbtree_node * rb_node_most_right(struct rbtree_node *node)
static struct rbtree_node * rb_node_pre(struct rbtree_node *node)
static struct rbtree_node * rb_find_initial(struct ao2_container_rbtree *self, void *obj_right, enum search_flags flags, enum equal_node_bias bias)
static const struct ao2_container_methods v_table_rbtree
static void rb_delete_node(struct ao2_container_rbtree *self, struct rbtree_node *doomed)
static void rb_delete_fixup(struct ao2_container_rbtree *self, struct rbtree_node *child)
static struct rbtree_node * rb_ao2_find_first(struct ao2_container_rbtree *self, enum search_flags flags, void *arg, struct rbtree_traversal_state *state)
static struct rbtree_node * rb_node_prev(struct rbtree_node *node)
static void rb_ao2_node_destructor(void *v_doomed)
static struct rbtree_node * rb_node_next_full(struct rbtree_node *node)
empty_node_direction
@ GO_RIGHT
@ GO_LEFT
#define FORMAT2
#define FORMAT
#define __LOG_ERROR
#define LOG_ERROR
int ast_atomic_fetchadd_int(volatile int *p, int v)
Atomically add v to *p and return the previous value of *p.
Definition: lock.h:757
#define NULL
Definition: resample.c:96
ao2_container_alloc_empty_clone_fn alloc_empty_clone
Create an empty copy of this container.
ao2_iterator_next_fn iterator_next
ao2_container_new_node_fn new_node
ao2_container_find_first_fn traverse_first
Generic container node.
struct ao2_container * my_container
struct ao2_container common
Items common to all containers.
struct rbtree_node * root
Generic container type.
ao2_callback_fn * cmp_fn
unsigned int destroying
TRUE if the container is being destroyed.
const struct ao2_container_methods * v_table
Definition: test_heap.c:38
struct rbtree_node * right
struct rbtree_node * parent
unsigned int is_red
struct ao2_container_node common
Items common to all container nodes.
struct rbtree_node * left
char check[1/(AO2_TRAVERSAL_STATE_SIZE/sizeof(struct rbtree_traversal_state))]
enum search_flags flags
static struct test_options options
Utility functions.
#define ast_assert(a)
Definition: utils.h:739
#define SWAP(a, b)
Definition: utils.h:235
#define ARRAY_LEN(a)
Definition: utils.h:666