Asterisk - The Open Source Telephony Project  GIT-master-a24979a
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  */
51 struct rbtree_node {
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. */
60  struct rbtree_node *left;
61  /*! Right child node of this node. NULL if does not have this child. */
62  struct rbtree_node *right;
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  */
77  struct ao2_container common;
78  /*! Root node of the tree. NULL if the tree is empty. */
79  struct rbtree_node *root;
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. */
117  enum search_flags flags;
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  */
174 static struct rbtree_node *rb_node_next(struct rbtree_node *node)
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  */
201 static struct rbtree_node *rb_node_prev(struct rbtree_node *node)
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  */
228 static struct rbtree_node *rb_node_pre(struct rbtree_node *node)
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  */
264 static struct rbtree_node *rb_node_post(struct rbtree_node *node)
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  */
355 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)
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  */
457 static 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  */
510 static 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 
561  return __ao2_container_alloc_rbtree(ao2_options_get(self), self->common.options,
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  */
578 static 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  */
712 static 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  */
828 static 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  */
894 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)
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  */
921 static 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:
1273  case OBJ_ORDER_ASCENDING:
1274  node = rb_node_next(node);
1275  break;
1276  case OBJ_ORDER_DESCENDING:
1277  node = rb_node_prev(node);
1278  break;
1279  case OBJ_ORDER_PRE:
1280  node = rb_node_pre(node);
1281  break;
1282  case OBJ_ORDER_POST:
1283  node = rb_node_post(node);
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  */
1341 static 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  */
1459 static 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:
1494  case OBJ_ORDER_ASCENDING:
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. */
1508  switch (self->common.options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
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;
1529  case OBJ_ORDER_DESCENDING:
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. */
1543  switch (self->common.options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
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) {
1572  node = rb_node_pre(node);
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) {
1595  node = rb_node_post(node);
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  */
1666 static 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  */
1686 static 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  */
1725 static 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  */
1764 static 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  */
1810 static 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 
1933  node = rb_node_pre(node);
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. */
1978 static const struct ao2_container_methods v_table_rbtree = {
1983  .traverse_next = (ao2_container_find_next_fn) rb_ao2_find_next,
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 
2022 struct 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.
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.
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.
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.
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 *(* 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
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.
@ 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)
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)
equal_node_bias
@ BIAS_LAST
@ BIAS_EQUAL
@ BIAS_FIRST
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 void rb_ao2_destroy(struct ao2_container_rbtree *self)
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_post(struct rbtree_node *node)
static void rb_rotate_left(struct ao2_container_rbtree *self, struct rbtree_node *node)
static struct rbtree_node * rb_node_most_right(struct rbtree_node *node)
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_node_next_full(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 const struct ao2_container_methods v_table_rbtree
static void rb_delete_node(struct ao2_container_rbtree *self, struct rbtree_node *doomed)
static struct rbtree_node * rb_node_prev(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 void rb_delete_fixup(struct ao2_container_rbtree *self, struct rbtree_node *child)
static void rb_ao2_node_destructor(void *v_doomed)
static struct rbtree_node * rb_node_next(struct rbtree_node *node)
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_left(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 rbtree_node * rb_node_prev_full(struct rbtree_node *node)
empty_node_direction
@ GO_RIGHT
@ GO_LEFT
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)
#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:755
#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.
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:734
#define SWAP(a, b)
Definition: utils.h:230
#define ARRAY_LEN(a)
Definition: utils.h:661