Asterisk - The Open Source Telephony Project  GIT-master-e8cda4b
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  */
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  */
125  char check[1 / (AO2_TRAVERSAL_STATE_SIZE / sizeof(struct rbtree_traversal_state))];
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  * \retval 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  * \retval 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  * \retval 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  * \retval 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  * \retval node on success.
307  * \retval NULL if no node.
308  */
310 {
311  for (;;) {
312  node = rb_node_next(node);
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  * \retval node on success.
327  * \retval NULL if no node.
328  */
330 {
331  for (;;) {
332  node = rb_node_prev(node);
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 enum 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  * \return Nothing
458  */
459 static void rb_rotate_left(struct ao2_container_rbtree *self, struct rbtree_node *node)
460 {
461  struct rbtree_node *child; /*!< Node's right child. */
462 
463  child = node->right;
464 
465  /* Link the node's parent to the child. */
466  if (!node->parent) {
467  /* Node is the root so we get a new root node. */
468  self->root = child;
469  } else if (node->parent->left == node) {
470  /* Node is a left child. */
471  node->parent->left = child;
472  } else {
473  /* Node is a right child. */
474  node->parent->right = child;
475  }
476  child->parent = node->parent;
477 
478  /* Link node's right subtree to the child's left subtree. */
479  node->right = child->left;
480  if (node->right) {
481  node->right->parent = node;
482  }
483 
484  /* Link the node to the child's left. */
485  node->parent = child;
486  child->left = node;
487 }
488 
489 /*!
490  * \internal
491  * \brief Tree node rotation right.
492  * \since 12.0.0
493  *
494  * \param self Container holding node.
495  * \param node Node to perform a right rotation with.
496  *
497  * p p
498  * | Right rotation |
499  * Ch N
500  * / \ <--- / \
501  * a N Ch c
502  * / \ / \
503  * b c a b
504  *
505  * N = node
506  * Ch = child
507  * p = parent
508  * a,b,c = other nodes that are unaffected by the rotation.
509  *
510  * \note It is assumed that the node's left child exists.
511  *
512  * \return Nothing
513  */
514 static void rb_rotate_right(struct ao2_container_rbtree *self, struct rbtree_node *node)
515 {
516  struct rbtree_node *child; /*!< Node's left child. */
517 
518  child = node->left;
519 
520  /* Link the node's parent to the child. */
521  if (!node->parent) {
522  /* Node is the root so we get a new root node. */
523  self->root = child;
524  } else if (node->parent->right == node) {
525  /* Node is a right child. */
526  node->parent->right = child;
527  } else {
528  /* Node is a left child. */
529  node->parent->left = child;
530  }
531  child->parent = node->parent;
532 
533  /* Link node's left subtree to the child's right subtree. */
534  node->left = child->right;
535  if (node->left) {
536  node->left->parent = node;
537  }
538 
539  /* Link the node to the child's right. */
540  node->parent = child;
541  child->right = node;
542 }
543 
544 /*!
545  * \internal
546  * \brief Create an empty copy of this container. (Debug version)
547  * \since 14.0.0
548  *
549  * \param self Container to operate upon.
550  * \param tag used for debugging.
551  * \param file Debug file name invoked from
552  * \param line Debug line invoked from
553  * \param func Debug function name invoked from
554  *
555  * \retval empty-clone-container on success.
556  * \retval NULL on error.
557  */
559  const char *tag, const char *file, int line, const char *func)
560 {
561  if (!__is_ao2_object(self, file, line, func)) {
562  return NULL;
563  }
564 
565  return __ao2_container_alloc_rbtree(ao2_options_get(self), self->common.options,
566  self->common.sort_fn, self->common.cmp_fn, tag, file, line, func);
567 }
568 
569 /*!
570  * \internal
571  * \brief Fixup the rbtree after deleting a node.
572  * \since 12.0.0
573  *
574  * \param self Container to operate upon.
575  * \param child Child of the node just deleted from the container.
576  *
577  * \note The child must be a dummy black node if there really
578  * was no child of the deleted node. Otherwise, the caller must
579  * pass in the parent node and which child was deleted. In
580  * addition, the fixup routine would be more complicated.
581  *
582  * \return Nothing
583  */
584 static void rb_delete_fixup(struct ao2_container_rbtree *self, struct rbtree_node *child)
585 {
586  struct rbtree_node *sibling;
587 
588  while (self->root != child && !child->is_red) {
589  if (child->parent->left == child) {
590  /* Child is a left child. */
591  sibling = child->parent->right;
592  ast_assert(sibling != NULL);
593  if (sibling->is_red) {
594  /* Case 1: The child's sibling is red. */
595  AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[0]);
596  sibling->is_red = 0;
597  child->parent->is_red = 1;
598  rb_rotate_left(self, child->parent);
599  sibling = child->parent->right;
600  ast_assert(sibling != NULL);
601  }
602  /*
603  * The sibling is black. A black node must have two children,
604  * or one red child, or no children.
605  */
606  if ((!sibling->left || !sibling->left->is_red)
607  && (!sibling->right || !sibling->right->is_red)) {
608  /*
609  * Case 2: The sibling is black and both of its children are black.
610  *
611  * This case handles the two black children or no children
612  * possibilities of a black node.
613  */
614  AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[1]);
615  sibling->is_red = 1;
616  child = child->parent;
617  } else {
618  /* At this point the sibling has at least one red child. */
619  if (!sibling->right || !sibling->right->is_red) {
620  /*
621  * Case 3: The sibling is black, its left child is red, and its
622  * right child is black.
623  */
624  AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[2]);
625  ast_assert(sibling->left != NULL);
626  ast_assert(sibling->left->is_red);
627  sibling->left->is_red = 0;
628  sibling->is_red = 1;
629  rb_rotate_right(self, sibling);
630  sibling = child->parent->right;
631  ast_assert(sibling != NULL);
632  }
633  /* Case 4: The sibling is black and its right child is red. */
634  AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[3]);
635  sibling->is_red = child->parent->is_red;
636  child->parent->is_red = 0;
637  if (sibling->right) {
638  sibling->right->is_red = 0;
639  }
640  rb_rotate_left(self, child->parent);
641  child = self->root;
642  }
643  } else {
644  /* Child is a right child. */
645  sibling = child->parent->left;
646  ast_assert(sibling != NULL);
647  if (sibling->is_red) {
648  /* Case 1: The child's sibling is red. */
649  AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[0]);
650  sibling->is_red = 0;
651  child->parent->is_red = 1;
652  rb_rotate_right(self, child->parent);
653  sibling = child->parent->left;
654  ast_assert(sibling != NULL);
655  }
656  /*
657  * The sibling is black. A black node must have two children,
658  * or one red child, or no children.
659  */
660  if ((!sibling->right || !sibling->right->is_red)
661  && (!sibling->left || !sibling->left->is_red)) {
662  /*
663  * Case 2: The sibling is black and both of its children are black.
664  *
665  * This case handles the two black children or no children
666  * possibilities of a black node.
667  */
668  AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[1]);
669  sibling->is_red = 1;
670  child = child->parent;
671  } else {
672  /* At this point the sibling has at least one red child. */
673  if (!sibling->left || !sibling->left->is_red) {
674  /*
675  * Case 3: The sibling is black, its right child is red, and its
676  * left child is black.
677  */
678  AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[2]);
679  ast_assert(sibling->right != NULL);
680  ast_assert(sibling->right->is_red);
681  sibling->right->is_red = 0;
682  sibling->is_red = 1;
683  rb_rotate_left(self, sibling);
684  sibling = child->parent->left;
685  ast_assert(sibling != NULL);
686  }
687  /* Case 4: The sibling is black and its left child is red. */
688  AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[3]);
689  sibling->is_red = child->parent->is_red;
690  child->parent->is_red = 0;
691  if (sibling->left) {
692  sibling->left->is_red = 0;
693  }
694  rb_rotate_right(self, child->parent);
695  child = self->root;
696  }
697  }
698  }
699 
700  /*
701  * Case 2 could leave the child node red and it needs to leave
702  * with it black.
703  *
704  * Case 4 sets the child node to the root which of course must
705  * be black.
706  */
707  child->is_red = 0;
708 }
709 
710 /*!
711  * \internal
712  * \brief Delete the doomed node from this container.
713  * \since 12.0.0
714  *
715  * \param self Container to operate upon.
716  * \param doomed Container node to delete from the container.
717  *
718  * \return Nothing
719  */
720 static void rb_delete_node(struct ao2_container_rbtree *self, struct rbtree_node *doomed)
721 {
722  struct rbtree_node *child;
723  int need_fixup;
724 
725  if (doomed->left && doomed->right) {
726  struct rbtree_node *next;
727  int is_red;
728 
729  /*
730  * The doomed node has two children.
731  *
732  * Find the next child node and swap it with the doomed node in
733  * the tree.
734  */
735  AO2_DEVMODE_STAT(++self->stats.delete_children[2]);
736  next = rb_node_most_left(doomed->right);
737  SWAP(doomed->parent, next->parent);
738  SWAP(doomed->left, next->left);
739  SWAP(doomed->right, next->right);
740  is_red = doomed->is_red;
741  doomed->is_red = next->is_red;
742  next->is_red = is_red;
743 
744  /* Link back in the next node. */
745  if (!next->parent) {
746  /* Doomed was the root so we get a new root node. */
747  self->root = next;
748  } else if (next->parent->left == doomed) {
749  /* Doomed was the left child. */
750  next->parent->left = next;
751  } else {
752  /* Doomed was the right child. */
753  next->parent->right = next;
754  }
755  next->left->parent = next;
756  if (next->right == next) {
757  /* The next node was the right child of doomed. */
758  next->right = doomed;
759  doomed->parent = next;
760  } else {
761  next->right->parent = next;
762  doomed->parent->left = doomed;
763  }
764 
765  /* The doomed node has no left child now. */
766  ast_assert(doomed->left == NULL);
767 
768  /*
769  * We don't have to link the right child back in with doomed
770  * since we are going to link it with doomed's parent anyway.
771  */
772  child = doomed->right;
773  } else {
774  /* Doomed has at most one child. */
775  child = doomed->left;
776  if (!child) {
777  child = doomed->right;
778  }
779  }
780  if (child) {
781  AO2_DEVMODE_STAT(++self->stats.delete_children[1]);
782  } else {
783  AO2_DEVMODE_STAT(++self->stats.delete_children[0]);
784  }
785 
786  need_fixup = (!doomed->is_red && !self->common.destroying);
787  if (need_fixup && !child) {
788  /*
789  * Use the doomed node as a place holder node for the
790  * nonexistent child so we also don't have to pass to the fixup
791  * routine the parent and which child the deleted node came
792  * from.
793  */
794  rb_delete_fixup(self, doomed);
795  ast_assert(doomed->left == NULL);
796  ast_assert(doomed->right == NULL);
797  ast_assert(!doomed->is_red);
798  }
799 
800  /* Link the child in place of doomed. */
801  if (!doomed->parent) {
802  /* Doomed was the root so we get a new root node. */
803  self->root = child;
804  } else if (doomed->parent->left == doomed) {
805  /* Doomed was the left child. */
806  doomed->parent->left = child;
807  } else {
808  /* Doomed was the right child. */
809  doomed->parent->right = child;
810  }
811  if (child) {
812  child->parent = doomed->parent;
813  if (need_fixup) {
814  rb_delete_fixup(self, child);
815  }
816  }
817 
818  AO2_DEVMODE_STAT(--self->common.nodes);
819 }
820 
821 /*!
822  * \internal
823  * \brief Destroy a rbtree container node.
824  * \since 12.0.0
825  *
826  * \param v_doomed Container node to destroy.
827  *
828  * \details
829  * The container node unlinks itself from the container as part
830  * of its destruction. The node must be destroyed while the
831  * container is already locked.
832  *
833  * \note The container must be locked when the node is
834  * unreferenced.
835  *
836  * \return Nothing
837  */
838 static void rb_ao2_node_destructor(void *v_doomed)
839 {
840  struct rbtree_node *doomed = v_doomed;
841 
842  if (doomed->common.is_linked) {
843  struct ao2_container_rbtree *my_container;
844 
845  /*
846  * Promote to write lock if not already there. Since
847  * adjust_lock() can potentially release and block waiting for a
848  * write lock, care must be taken to ensure that node references
849  * are released before releasing the container references.
850  *
851  * Node references held by an iterator can only be held while
852  * the iterator also holds a reference to the container. These
853  * node references must be unreferenced before the container can
854  * be unreferenced to ensure that the node will not get a
855  * negative reference and the destructor called twice for the
856  * same node.
857  */
858  my_container = (struct ao2_container_rbtree *) doomed->common.my_container;
859 #ifdef AST_DEVMODE
860  is_ao2_object(my_container);
861 #endif
862 
863  __adjust_lock(my_container, AO2_LOCK_REQ_WRLOCK, 1);
864 
865 #if defined(AO2_DEBUG)
866  if (!my_container->common.destroying
868  ast_log(LOG_ERROR, "Container integrity failed before node deletion.\n");
869  }
870 #endif /* defined(AO2_DEBUG) */
871  rb_delete_node(my_container, doomed);
872 #if defined(AO2_DEBUG)
873  if (!my_container->common.destroying
875  ast_log(LOG_ERROR, "Container integrity failed after node deletion.\n");
876  }
877 #endif /* defined(AO2_DEBUG) */
878  }
879 
880  /*
881  * We could have an object in the node if the container is being
882  * destroyed or the node had not been linked in yet.
883  */
884  if (doomed->common.obj) {
886  }
887 }
888 
889 /*!
890  * \internal
891  * \brief Create a new container node.
892  * \since 12.0.0
893  *
894  * \param self Container to operate upon.
895  * \param obj_new Object to put into the node.
896  * \param tag used for debugging.
897  * \param file Debug file name invoked from
898  * \param line Debug line invoked from
899  * \param func Debug function name invoked from
900  *
901  * \retval initialized-node on success.
902  * \retval NULL on error.
903  */
904 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)
905 {
906  struct rbtree_node *node;
907 
908  node = ao2_alloc_options(sizeof(*node), rb_ao2_node_destructor,
910  if (!node) {
911  return NULL;
912  }
913 
914  __ao2_ref(obj_new, +1, tag ?: "Container node creation", file, line, func);
915  node->common.obj = obj_new;
916  node->common.my_container = (struct ao2_container *) self;
917 
918  return node;
919 }
920 
921 /*!
922  * \internal
923  * \brief Fixup the rbtree after inserting a node.
924  * \since 12.0.0
925  *
926  * \param self Container to operate upon.
927  * \param node Container node just inserted into the container.
928  *
929  * \note The just inserted node is red.
930  *
931  * \return Nothing
932  */
933 static void rb_insert_fixup(struct ao2_container_rbtree *self, struct rbtree_node *node)
934 {
935  struct rbtree_node *g_parent; /* Grand parent node. */
936 
937  while (node->parent && node->parent->is_red) {
938  g_parent = node->parent->parent;
939 
940  /* The grand parent must exist if the parent is red. */
941  ast_assert(g_parent != NULL);
942 
943  if (node->parent == g_parent->left) {
944  /* The parent is a left child. */
945  if (g_parent->right && g_parent->right->is_red) {
946  /* Case 1: Push the black down from the grand parent node. */
947  AO2_DEVMODE_STAT(++self->stats.fixup_insert_left[0]);
948  g_parent->right->is_red = 0;
949  g_parent->left->is_red = 0;
950  g_parent->is_red = 1;
951 
952  node = g_parent;
953  } else {
954  /* The uncle node is black. */
955  if (node->parent->right == node) {
956  /*
957  * Case 2: The node is a right child.
958  *
959  * Which node is the grand parent does not change.
960  */
961  AO2_DEVMODE_STAT(++self->stats.fixup_insert_left[1]);
962  node = node->parent;
963  rb_rotate_left(self, node);
964  }
965  /* Case 3: The node is a left child. */
966  AO2_DEVMODE_STAT(++self->stats.fixup_insert_left[2]);
967  node->parent->is_red = 0;
968  g_parent->is_red = 1;
969  rb_rotate_right(self, g_parent);
970  }
971  } else {
972  /* The parent is a right child. */
973  if (g_parent->left && g_parent->left->is_red) {
974  /* Case 1: Push the black down from the grand parent node. */
975  AO2_DEVMODE_STAT(++self->stats.fixup_insert_right[0]);
976  g_parent->left->is_red = 0;
977  g_parent->right->is_red = 0;
978  g_parent->is_red = 1;
979 
980  node = g_parent;
981  } else {
982  /* The uncle node is black. */
983  if (node->parent->left == node) {
984  /*
985  * Case 2: The node is a left child.
986  *
987  * Which node is the grand parent does not change.
988  */
989  AO2_DEVMODE_STAT(++self->stats.fixup_insert_right[1]);
990  node = node->parent;
991  rb_rotate_right(self, node);
992  }
993  /* Case 3: The node is a right child. */
994  AO2_DEVMODE_STAT(++self->stats.fixup_insert_right[2]);
995  node->parent->is_red = 0;
996  g_parent->is_red = 1;
997  rb_rotate_left(self, g_parent);
998  }
999  }
1000  }
1001 
1002  /*
1003  * The root could be red here because:
1004  * 1) We just inserted the root node in an empty tree.
1005  *
1006  * 2) Case 1 could leave the root red if the grand parent were
1007  * the root.
1008  */
1009  self->root->is_red = 0;
1010 }
1011 
1012 /*!
1013  * \internal
1014  * \brief Insert a node into this container.
1015  * \since 12.0.0
1016  *
1017  * \param self Container to operate upon.
1018  * \param node Container node to insert into the container.
1019  *
1020  * \return enum ao2_container_insert value.
1021  */
1023 {
1024  int cmp;
1025  struct rbtree_node *cur;
1026  struct rbtree_node *next;
1027  ao2_sort_fn *sort_fn;
1028  uint32_t options;
1029  enum equal_node_bias bias;
1030 
1031  if (!self->root) {
1032  /* The tree is empty. */
1033  self->root = node;
1035  }
1036 
1037  sort_fn = self->common.sort_fn;
1038  options = self->common.options;
1039  switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
1040  default:
1042  if (options & AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN) {
1043  bias = BIAS_FIRST;
1044  } else {
1045  bias = BIAS_LAST;
1046  }
1047  break;
1051  bias = BIAS_EQUAL;
1052  break;
1053  }
1054 
1055  /*
1056  * New nodes are always colored red when initially inserted into
1057  * the tree. (Except for the root which is always black.)
1058  */
1059  node->is_red = 1;
1060 
1061  /* Find node where normal insert would put a new node. */
1062  cur = self->root;
1063  for (;;) {
1064  if (!cur->common.obj) {
1065  /* Which direction do we go to insert this node? */
1066  if (rb_find_empty_direction(cur, sort_fn, node->common.obj, OBJ_SEARCH_OBJECT, bias)
1067  == GO_LEFT) {
1068  if (cur->left) {
1069  cur = cur->left;
1070  continue;
1071  }
1072 
1073  /* Node becomes a left child */
1074  cur->left = node;
1075  node->parent = cur;
1076  rb_insert_fixup(self, node);
1078  }
1079  if (cur->right) {
1080  cur = cur->right;
1081  continue;
1082  }
1083 
1084  /* Node becomes a right child */
1085  cur->right = node;
1086  node->parent = cur;
1087  rb_insert_fixup(self, node);
1089  }
1090  cmp = sort_fn(cur->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
1091  if (cmp > 0) {
1092  if (cur->left) {
1093  cur = cur->left;
1094  continue;
1095  }
1096 
1097  /* Node becomes a left child */
1098  cur->left = node;
1099  node->parent = cur;
1100  rb_insert_fixup(self, node);
1102  } else if (cmp < 0) {
1103  if (cur->right) {
1104  cur = cur->right;
1105  continue;
1106  }
1107 
1108  /* Node becomes a right child */
1109  cur->right = node;
1110  node->parent = cur;
1111  rb_insert_fixup(self, node);
1113  }
1114  switch (bias) {
1115  case BIAS_FIRST:
1116  /* Duplicate nodes unconditionally accepted. */
1117  if (cur->left) {
1118  cur = cur->left;
1119  continue;
1120  }
1121 
1122  /* Node becomes a left child */
1123  cur->left = node;
1124  node->parent = cur;
1125  rb_insert_fixup(self, node);
1127  case BIAS_EQUAL:
1128  break;
1129  case BIAS_LAST:
1130  /* Duplicate nodes unconditionally accepted. */
1131  if (cur->right) {
1132  cur = cur->right;
1133  continue;
1134  }
1135 
1136  /* Node becomes a right child */
1137  cur->right = node;
1138  node->parent = cur;
1139  rb_insert_fixup(self, node);
1141  }
1142 
1143  break;
1144  }
1145 
1146  /* Node is a dupliate */
1147  switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
1148  default:
1150  ast_assert(0);/* Case already handled by BIAS_FIRST/BIAS_LAST. */
1153  /* Reject all objects with the same key. */
1156  if (cur->common.obj == node->common.obj) {
1157  /* Reject inserting the same object */
1159  }
1160  next = cur;
1161  if (options & AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN) {
1162  /* Search to end of duplicates for the same object. */
1163  for (;;) {
1164  next = rb_node_next_full(next);
1165  if (!next) {
1166  break;
1167  }
1168  if (next->common.obj == node->common.obj) {
1169  /* Reject inserting the same object */
1171  }
1172  cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
1173  if (cmp) {
1174  break;
1175  }
1176  }
1177 
1178  /* Find first duplicate node. */
1179  for (;;) {
1180  next = rb_node_prev_full(cur);
1181  if (!next) {
1182  break;
1183  }
1184  if (next->common.obj == node->common.obj) {
1185  /* Reject inserting the same object */
1187  }
1188  cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
1189  if (cmp) {
1190  break;
1191  }
1192  cur = next;
1193  }
1194  if (!cur->left) {
1195  /* Node becomes a left child */
1196  cur->left = node;
1197  } else {
1198  /* Node becomes a right child */
1199  cur = rb_node_most_right(cur->left);
1200  cur->right = node;
1201  }
1202  } else {
1203  /* Search to beginning of duplicates for the same object. */
1204  for (;;) {
1205  next = rb_node_prev_full(next);
1206  if (!next) {
1207  break;
1208  }
1209  if (next->common.obj == node->common.obj) {
1210  /* Reject inserting the same object */
1212  }
1213  cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
1214  if (cmp) {
1215  break;
1216  }
1217  }
1218 
1219  /* Find last duplicate node. */
1220  for (;;) {
1221  next = rb_node_next_full(cur);
1222  if (!next) {
1223  break;
1224  }
1225  if (next->common.obj == node->common.obj) {
1226  /* Reject inserting the same object */
1228  }
1229  cmp = sort_fn(next->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
1230  if (cmp) {
1231  break;
1232  }
1233  cur = next;
1234  }
1235  if (!cur->right) {
1236  /* Node becomes a right child */
1237  cur->right = node;
1238  } else {
1239  /* Node becomes a left child */
1240  cur = rb_node_most_left(cur->right);
1241  cur->left = node;
1242  }
1243  }
1244  break;
1246  SWAP(cur->common.obj, node->common.obj);
1247  ao2_ref(node, -1);
1249  }
1250 
1251  /* Complete inserting duplicate node. */
1252  node->parent = cur;
1253  rb_insert_fixup(self, node);
1255 }
1256 
1257 /*!
1258  * \internal
1259  * \brief Find the next rbtree container node in a traversal.
1260  * \since 12.0.0
1261  *
1262  * \param self Container to operate upon.
1263  * \param state Traversal state to restart rbtree container traversal.
1264  * \param prev Previous node returned by the traversal search functions.
1265  * The ref ownership is passed back to this function.
1266  *
1267  * \retval node-ptr of found node (Reffed).
1268  * \retval NULL when no node found.
1269  */
1271 {
1272  struct rbtree_node *node;
1273  void *arg;
1274  enum search_flags flags;
1275  int cmp;
1276 
1277  arg = state->arg;
1278  flags = state->flags;
1279 
1280  node = prev;
1281  for (;;) {
1282  /* Find next node in traversal order. */
1283  switch (flags & OBJ_ORDER_MASK) {
1284  default:
1285  case OBJ_ORDER_ASCENDING:
1286  node = rb_node_next(node);
1287  break;
1288  case OBJ_ORDER_DESCENDING:
1289  node = rb_node_prev(node);
1290  break;
1291  case OBJ_ORDER_PRE:
1292  node = rb_node_pre(node);
1293  break;
1294  case OBJ_ORDER_POST:
1295  node = rb_node_post(node);
1296  break;
1297  }
1298  if (!node) {
1299  /* No more nodes left to traverse. */
1300  break;
1301  }
1302  if (!node->common.obj) {
1303  /* Node is empty */
1304  continue;
1305  }
1306 
1307  if (state->sort_fn) {
1308  /* Filter node through the sort_fn */
1309  cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
1310  if (cmp) {
1311  /* No more nodes in this container are possible to match. */
1312  break;
1313  }
1314  }
1315 
1316  /* We have the next traversal node */
1317  ao2_ref(node, +1);
1318 
1319  /*
1320  * Dereferencing the prev node may result in our next node
1321  * object being removed by another thread. This could happen if
1322  * the container uses RW locks and the container was read
1323  * locked.
1324  */
1325  ao2_ref(prev, -1);
1326  if (node->common.obj) {
1327  return node;
1328  }
1329  prev = node;
1330  }
1331 
1332  /* No more nodes in the container left to traverse. */
1333  ao2_ref(prev, -1);
1334  return NULL;
1335 }
1336 
1337 /*!
1338  * \internal
1339  * \brief Find an initial matching node.
1340  * \since 12.0.0
1341  *
1342  * \param self Container to operate upon.
1343  * \param obj_right pointer to the (user-defined part) of an object.
1344  * \param flags flags from ao2_callback()
1345  * OBJ_SEARCH_OBJECT - if set, 'obj_right', is an object.
1346  * OBJ_SEARCH_KEY - if set, 'obj_right', is a search key item that is not an object.
1347  * OBJ_SEARCH_PARTIAL_KEY - if set, 'obj_right', is a partial search key item that is not an object.
1348  * \param bias How to bias search direction for duplicates
1349  *
1350  * \retval node on success.
1351  * \retval NULL if not found.
1352  */
1353 static struct rbtree_node *rb_find_initial(struct ao2_container_rbtree *self, void *obj_right, enum search_flags flags, enum equal_node_bias bias)
1354 {
1355  int cmp;
1356  enum search_flags sort_flags;
1357  struct rbtree_node *node;
1358  struct rbtree_node *next = NULL;
1359  ao2_sort_fn *sort_fn;
1360 
1361  sort_flags = flags & OBJ_SEARCH_MASK;
1362  sort_fn = self->common.sort_fn;
1363 
1364  /* Find node where normal search would find it. */
1365  node = self->root;
1366  if (!node) {
1367  return NULL;
1368  }
1369  for (;;) {
1370  if (!node->common.obj) {
1371  /* Which direction do we go to find the node? */
1372  if (rb_find_empty_direction(node, sort_fn, obj_right, sort_flags, bias)
1373  == GO_LEFT) {
1374  next = node->left;
1375  } else {
1376  next = node->right;
1377  }
1378  if (!next) {
1379  switch (bias) {
1380  case BIAS_FIRST:
1381  /* Check successor node for match. */
1382  next = rb_node_next_full(node);
1383  break;
1384  case BIAS_EQUAL:
1385  break;
1386  case BIAS_LAST:
1387  /* Check previous node for match. */
1388  next = rb_node_prev_full(node);
1389  break;
1390  }
1391  if (next) {
1392  cmp = sort_fn(next->common.obj, obj_right, sort_flags);
1393  if (cmp == 0) {
1394  /* Found the first/last matching node. */
1395  return next;
1396  }
1397  next = NULL;
1398  }
1399 
1400  /* No match found. */
1401  return next;
1402  }
1403  } else {
1404  cmp = sort_fn(node->common.obj, obj_right, sort_flags);
1405  if (cmp > 0) {
1406  next = node->left;
1407  } else if (cmp < 0) {
1408  next = node->right;
1409  } else {
1410  switch (bias) {
1411  case BIAS_FIRST:
1412  next = node->left;
1413  break;
1414  case BIAS_EQUAL:
1415  return node;
1416  case BIAS_LAST:
1417  next = node->right;
1418  break;
1419  }
1420  if (!next) {
1421  /* Found the first/last matching node. */
1422  return node;
1423  }
1424  }
1425  if (!next) {
1426  switch (bias) {
1427  case BIAS_FIRST:
1428  if (cmp < 0) {
1429  /* Check successor node for match. */
1430  next = rb_node_next_full(node);
1431  }
1432  break;
1433  case BIAS_EQUAL:
1434  break;
1435  case BIAS_LAST:
1436  if (cmp > 0) {
1437  /* Check previous node for match. */
1438  next = rb_node_prev_full(node);
1439  }
1440  break;
1441  }
1442  if (next) {
1443  cmp = sort_fn(next->common.obj, obj_right, sort_flags);
1444  if (cmp == 0) {
1445  /* Found the first/last matching node. */
1446  return next;
1447  }
1448  }
1449 
1450  /* No match found. */
1451  return NULL;
1452  }
1453  }
1454  node = next;
1455  }
1456 }
1457 
1458 /*!
1459  * \internal
1460  * \brief Find the first rbtree container node in a traversal.
1461  * \since 12.0.0
1462  *
1463  * \param self Container to operate upon.
1464  * \param flags search_flags to control traversing the container
1465  * \param arg Comparison callback arg parameter.
1466  * \param state Traversal state to restart rbtree container traversal.
1467  *
1468  * \retval node-ptr of found node (Reffed).
1469  * \retval NULL when no node found.
1470  */
1471 static struct rbtree_node *rb_ao2_find_first(struct ao2_container_rbtree *self, enum search_flags flags, void *arg, struct rbtree_traversal_state *state)
1472 {
1473  struct rbtree_node *node;
1474  enum equal_node_bias bias;
1475 
1476  if (self->common.destroying) {
1477  /* Force traversal to be post order for tree destruction. */
1479  }
1480 
1481  memset(state, 0, sizeof(*state));
1482  state->arg = arg;
1483  state->flags = flags;
1484 
1485  switch (flags & OBJ_SEARCH_MASK) {
1486  case OBJ_SEARCH_OBJECT:
1487  case OBJ_SEARCH_KEY:
1489  /* We are asked to do a directed search. */
1490  state->sort_fn = self->common.sort_fn;
1491  break;
1492  default:
1493  /* Don't know, let's visit all nodes */
1494  state->sort_fn = NULL;
1495  break;
1496  }
1497 
1498  if (!self->root) {
1499  /* Tree is empty. */
1500  return NULL;
1501  }
1502 
1503  /* Find first traversal node. */
1504  switch (flags & OBJ_ORDER_MASK) {
1505  default:
1506  case OBJ_ORDER_ASCENDING:
1507  if (!state->sort_fn) {
1508  /* Find left most child. */
1509  node = rb_node_most_left(self->root);
1510  if (!node->common.obj) {
1511  node = rb_node_next_full(node);
1512  if (!node) {
1513  return NULL;
1514  }
1515  }
1516  break;
1517  }
1518 
1519  /* Search for initial node. */
1520  switch (self->common.options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
1523  if ((flags & OBJ_SEARCH_MASK) != OBJ_SEARCH_PARTIAL_KEY) {
1524  /* There are no duplicates allowed. */
1525  bias = BIAS_EQUAL;
1526  break;
1527  }
1528  /* Fall through */
1529  default:
1532  /* Find first duplicate node. */
1533  bias = BIAS_FIRST;
1534  break;
1535  }
1536  node = rb_find_initial(self, arg, flags, bias);
1537  if (!node) {
1538  return NULL;
1539  }
1540  break;
1541  case OBJ_ORDER_DESCENDING:
1542  if (!state->sort_fn) {
1543  /* Find right most child. */
1544  node = rb_node_most_right(self->root);
1545  if (!node->common.obj) {
1546  node = rb_node_prev_full(node);
1547  if (!node) {
1548  return NULL;
1549  }
1550  }
1551  break;
1552  }
1553 
1554  /* Search for initial node. */
1555  switch (self->common.options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
1558  if ((flags & OBJ_SEARCH_MASK) != OBJ_SEARCH_PARTIAL_KEY) {
1559  /* There are no duplicates allowed. */
1560  bias = BIAS_EQUAL;
1561  break;
1562  }
1563  /* Fall through */
1564  default:
1567  /* Find last duplicate node. */
1568  bias = BIAS_LAST;
1569  break;
1570  }
1571  node = rb_find_initial(self, arg, flags, bias);
1572  if (!node) {
1573  return NULL;
1574  }
1575  break;
1576  case OBJ_ORDER_PRE:
1577  /* This is a tree structure traversal so we must visit all nodes. */
1578  state->sort_fn = NULL;
1579 
1580  node = self->root;
1581 
1582  /* Find a non-empty node. */
1583  while (!node->common.obj) {
1584  node = rb_node_pre(node);
1585  if (!node) {
1586  return NULL;
1587  }
1588  }
1589  break;
1590  case OBJ_ORDER_POST:
1591  /* This is a tree structure traversal so we must visit all nodes. */
1592  state->sort_fn = NULL;
1593 
1594  /* Find the left most childless node. */
1595  node = self->root;
1596  for (;;) {
1597  node = rb_node_most_left(node);
1598  if (!node->right) {
1599  /* This node has no children. */
1600  break;
1601  }
1602  node = node->right;
1603  }
1604 
1605  /* Find a non-empty node. */
1606  while (!node->common.obj) {
1607  node = rb_node_post(node);
1608  if (!node) {
1609  return NULL;
1610  }
1611  }
1612  break;
1613  }
1614 
1615  /* We have the first traversal node */
1616  ao2_ref(node, +1);
1617  return node;
1618 }
1619 
1620 /*!
1621  * \internal
1622  * \brief Find the next non-empty iteration node in the container.
1623  * \since 12.0.0
1624  *
1625  * \param self Container to operate upon.
1626  * \param node Previous node returned by the iterator.
1627  * \param flags search_flags to control iterating the container.
1628  * Only AO2_ITERATOR_DESCENDING is useful by the method.
1629  *
1630  * \note The container is already locked.
1631  *
1632  * \retval node on success.
1633  * \retval NULL on error or no more nodes in the container.
1634  */
1636 {
1637  if (flags & AO2_ITERATOR_DESCENDING) {
1638  if (!node) {
1639  /* Find right most node. */
1640  if (!self->root) {
1641  return NULL;
1642  }
1643  node = rb_node_most_right(self->root);
1644  if (node->common.obj) {
1645  /* Found a non-empty node. */
1646  return node;
1647  }
1648  }
1649  /* Find next non-empty node. */
1650  node = rb_node_prev_full(node);
1651  } else {
1652  if (!node) {
1653  /* Find left most node. */
1654  if (!self->root) {
1655  return NULL;
1656  }
1657  node = rb_node_most_left(self->root);
1658  if (node->common.obj) {
1659  /* Found a non-empty node. */
1660  return node;
1661  }
1662  }
1663  /* Find next non-empty node. */
1664  node = rb_node_next_full(node);
1665  }
1666 
1667  return node;
1668 }
1669 
1670 /*!
1671  * \internal
1672  *
1673  * \brief Destroy this container.
1674  * \since 12.0.0
1675  *
1676  * \param self Container to operate upon.
1677  *
1678  * \return Nothing
1679  */
1680 static void rb_ao2_destroy(struct ao2_container_rbtree *self)
1681 {
1682  /* Check that the container no longer has any nodes */
1683  if (self->root) {
1684  ast_log(LOG_ERROR, "Node ref leak. Red-Black tree container still has nodes!\n");
1685  ast_assert(0);
1686  }
1687 }
1688 
1689 #if defined(AO2_DEBUG)
1690 /*!
1691  * \internal
1692  * \brief Display contents of the specified container.
1693  * \since 12.0.0
1694  *
1695  * \param self Container to dump.
1696  * \param where User data needed by prnt to determine where to put output.
1697  * \param prnt Print output callback function to use.
1698  * \param prnt_obj Callback function to print the given object's key. (NULL if not available)
1699  *
1700  * \return Nothing
1701  */
1702 static void rb_ao2_dump(struct ao2_container_rbtree *self, void *where, ao2_prnt_fn *prnt, ao2_prnt_obj_fn *prnt_obj)
1703 {
1704 #define FORMAT "%16s, %16s, %16s, %16s, %5s, %16s, %s\n"
1705 #define FORMAT2 "%16p, %16p, %16p, %16p, %5s, %16p, "
1706 
1707  struct rbtree_node *node;
1708 
1709  prnt(where, FORMAT, "Node", "Parent", "Left", "Right", "Color", "Obj", "Key");
1710  for (node = self->root; node; node = rb_node_pre(node)) {
1711  prnt(where, FORMAT2,
1712  node,
1713  node->parent,
1714  node->left,
1715  node->right,
1716  node->is_red ? "Red" : "Black",
1717  node->common.obj);
1718  if (node->common.obj && prnt_obj) {
1719  prnt_obj(node->common.obj, where, prnt);
1720  }
1721  prnt(where, "\n");
1722  }
1723 
1724 #undef FORMAT
1725 #undef FORMAT2
1726 }
1727 #endif /* defined(AO2_DEBUG) */
1728 
1729 #if defined(AO2_DEBUG)
1730 /*!
1731  * \internal
1732  * \brief Display statistics of the specified container.
1733  * \since 12.0.0
1734  *
1735  * \param self Container to display statistics.
1736  * \param where User data needed by prnt to determine where to put output.
1737  * \param prnt Print output callback function to use.
1738  *
1739  * \note The container is already locked for reading.
1740  *
1741  * \return Nothing
1742  */
1743 static void rb_ao2_stats(struct ao2_container_rbtree *self, void *where, ao2_prnt_fn *prnt)
1744 {
1745  int idx;
1746 
1747  for (idx = 0; idx < ARRAY_LEN(self->stats.fixup_insert_left); ++idx) {
1748  prnt(where, "Number of left insert fixups case %d: %d\n", idx + 1,
1749  self->stats.fixup_insert_left[idx]);
1750  }
1751  for (idx = 0; idx < ARRAY_LEN(self->stats.fixup_insert_right); ++idx) {
1752  prnt(where, "Number of right insert fixups case %d: %d\n", idx + 1,
1753  self->stats.fixup_insert_right[idx]);
1754  }
1755 
1756  for (idx = 0; idx < ARRAY_LEN(self->stats.delete_children); ++idx) {
1757  prnt(where, "Number of nodes deleted with %d children: %d\n", idx,
1758  self->stats.delete_children[idx]);
1759  }
1760  for (idx = 0; idx < ARRAY_LEN(self->stats.fixup_delete_left); ++idx) {
1761  prnt(where, "Number of left delete fixups case %d: %d\n", idx + 1,
1762  self->stats.fixup_delete_left[idx]);
1763  }
1764  for (idx = 0; idx < ARRAY_LEN(self->stats.fixup_delete_right); ++idx) {
1765  prnt(where, "Number of right delete fixups case %d: %d\n", idx + 1,
1766  self->stats.fixup_delete_right[idx]);
1767  }
1768 }
1769 #endif /* defined(AO2_DEBUG) */
1770 
1771 #if defined(AO2_DEBUG)
1772 /*!
1773  * \internal
1774  * \brief Check the black height of the given node.
1775  * \since 12.0.0
1776  *
1777  * \param node Node to check black height.
1778  *
1779  * \retval black-height of node on success.
1780  * \retval -1 on error. Node black height did not balance.
1781  */
1782 static int rb_check_black_height(struct rbtree_node *node)
1783 {
1784  int height_left;
1785  int height_right;
1786 
1787  if (!node) {
1788  /* A NULL child is a black node. */
1789  return 0;
1790  }
1791 
1792  height_left = rb_check_black_height(node->left);
1793  if (height_left < 0) {
1794  return -1;
1795  }
1796  height_right = rb_check_black_height(node->right);
1797  if (height_right < 0) {
1798  return -1;
1799  }
1800  if (height_left != height_right) {
1802  "Tree node black height of children does not match! L:%d != R:%d\n",
1803  height_left, height_right);
1804  return -1;
1805  }
1806  if (!node->is_red) {
1807  /* The node itself is black. */
1808  ++height_left;
1809  }
1810  return height_left;
1811 }
1812 
1813 #endif /* defined(AO2_DEBUG) */
1814 
1815 #if defined(AO2_DEBUG)
1816 /*!
1817  * \internal
1818  * \brief Perform an integrity check on the specified container.
1819  * \since 12.0.0
1820  *
1821  * \param self Container to check integrity.
1822  *
1823  * \note The container is already locked for reading.
1824  *
1825  * \retval 0 on success.
1826  * \retval -1 on error.
1827  */
1828 static int rb_ao2_integrity(struct ao2_container_rbtree *self)
1829 {
1830  int res;
1831  int count_node;
1832  int count_obj;
1833  void *obj_last;
1834  struct rbtree_node *node;
1835 
1836  res = 0;
1837 
1838  count_node = 0;
1839  count_obj = 0;
1840 
1841  /*
1842  * See the properties listed at struct rbtree_node definition.
1843  *
1844  * The rbtree properties 1 and 3 are not testable.
1845  *
1846  * Property 1 is not testable because we are not rebalancing at
1847  * this time so all nodes are either red or black.
1848  *
1849  * Property 3 is not testable because it is the definition of a
1850  * NULL child.
1851  */
1852  if (self->root) {
1853  /* Check tree links. */
1854  if (self->root->parent) {
1855  if (self->root->parent == self->root) {
1856  ast_log(LOG_ERROR, "Tree root parent pointer points to itself!\n");
1857  } else {
1858  ast_log(LOG_ERROR, "Tree root is not a root node!\n");
1859  }
1860  return -1;
1861  }
1862  if (self->root->is_red) {
1863  /* Violation rbtree property 2. */
1864  ast_log(LOG_ERROR, "Tree root is red!\n");
1865  res = -1;
1866  }
1867  node = self->root;
1868  do {
1869  if (node->left) {
1870  if (node->left == node) {
1871  ast_log(LOG_ERROR, "Tree node's left pointer points to itself!\n");
1872  return -1;
1873  }
1874  if (node->left->parent != node) {
1875  ast_log(LOG_ERROR, "Tree node's left child does not link back!\n");
1876  return -1;
1877  }
1878  }
1879  if (node->right) {
1880  if (node->right == node) {
1881  ast_log(LOG_ERROR, "Tree node's right pointer points to itself!\n");
1882  return -1;
1883  }
1884  if (node->right->parent != node) {
1885  ast_log(LOG_ERROR, "Tree node's right child does not link back!\n");
1886  return -1;
1887  }
1888  }
1889 
1890  /* Check red/black node flags. */
1891  if (node->is_red) {
1892  /* A red node must have two black children or no children. */
1893  if (node->left && node->right) {
1894  /* Node has two children. */
1895  if (node->left->is_red) {
1896  /* Violation rbtree property 4. */
1897  ast_log(LOG_ERROR, "Tree node is red and its left child is red!\n");
1898  res = -1;
1899  }
1900  if (node->right->is_red) {
1901  /* Violation rbtree property 4. */
1902  ast_log(LOG_ERROR, "Tree node is red and its right child is red!\n");
1903  res = -1;
1904  }
1905  } else if (node->left || node->right) {
1906  /*
1907  * Violation rbtree property 4 if the child is red.
1908  * Violation rbtree property 5 if the child is black.
1909  */
1910  ast_log(LOG_ERROR, "Tree node is red and it only has one child!\n");
1911  res = -1;
1912  }
1913  } else {
1914  /*
1915  * A black node must have two children, or one red child, or no
1916  * children. If the black node has two children and only one of
1917  * them is red, that red child must have two children.
1918  */
1919  if (node->left && node->right) {
1920  /* Node has two children. */
1921  if (node->left->is_red != node->right->is_red) {
1922  /* The children are not the same color. */
1923  struct rbtree_node *red;
1924 
1925  if (node->left->is_red) {
1926  red = node->left;
1927  } else {
1928  red = node->right;
1929  }
1930  if (!red->left || !red->right) {
1931  /* Violation rbtree property 5. */
1933  "Tree node is black and the red child does not have two children!\n");
1934  res = -1;
1935  }
1936  }
1937  } else if ((node->left && !node->left->is_red)
1938  || (node->right && !node->right->is_red)) {
1939  /* Violation rbtree property 5. */
1940  ast_log(LOG_ERROR, "Tree node is black and its only child is black!\n");
1941  res = -1;
1942  }
1943  }
1944 
1945  /* Count nodes and objects. */
1946  ++count_node;
1947  if (node->common.obj) {
1948  ++count_obj;
1949  }
1950 
1951  node = rb_node_pre(node);
1952  } while (node);
1953 
1954  /* Check node key sort order. */
1955  obj_last = NULL;
1956  for (node = rb_node_most_left(self->root); node; node = rb_node_next(node)) {
1957  if (!node->common.obj) {
1958  /* Node is empty. */
1959  continue;
1960  }
1961 
1962  if (obj_last) {
1963  if (self->common.sort_fn(obj_last, node->common.obj, OBJ_SEARCH_OBJECT) > 0) {
1964  ast_log(LOG_ERROR, "Tree nodes are out of sorted order!\n");
1965  return -1;
1966  }
1967  }
1968  obj_last = node->common.obj;
1969  }
1970 
1971  /* Completely check property 5 */
1972  if (!res && rb_check_black_height(self->root) < 0) {
1973  /* Violation rbtree property 5. */
1974  res = -1;
1975  }
1976  }
1977 
1978  /* Check total obj count. */
1979  if (count_obj != ao2_container_count(&self->common)) {
1980  ast_log(LOG_ERROR, "Total object count does not match ao2_container_count()!\n");
1981  return -1;
1982  }
1983 
1984  /* Check total node count. */
1985  if (count_node != self->common.nodes) {
1986  ast_log(LOG_ERROR, "Total node count of %d does not match stat of %d!\n",
1987  count_node, self->common.nodes);
1988  return -1;
1989  }
1990 
1991  return res;
1992 }
1993 #endif /* defined(AO2_DEBUG) */
1994 
1995 /*! rbtree container virtual method table. */
1996 static const struct ao2_container_methods v_table_rbtree = {
2001  .traverse_next = (ao2_container_find_next_fn) rb_ao2_find_next,
2004 #if defined(AO2_DEBUG)
2005  .dump = (ao2_container_display) rb_ao2_dump,
2006  .stats = (ao2_container_statistics) rb_ao2_stats,
2007  .integrity = (ao2_container_integrity) rb_ao2_integrity,
2008 #endif /* defined(AO2_DEBUG) */
2009 };
2010 
2011 /*!
2012  * \brief Initialize a rbtree container.
2013  *
2014  * \param self Container to initialize.
2015  * \param options Container behaviour options (See enum ao2_container_opts)
2016  * \param sort_fn Pointer to a sort function.
2017  * \param cmp_fn Pointer to a compare function used by ao2_find.
2018  *
2019  * \return A pointer to a struct container.
2020  */
2023 {
2024  if (!self) {
2025  return NULL;
2026  }
2027 
2028  self->common.v_table = &v_table_rbtree;
2029  self->common.sort_fn = sort_fn;
2030  self->common.cmp_fn = cmp_fn;
2031  self->common.options = options;
2032 
2033 #ifdef AO2_DEBUG
2034  ast_atomic_fetchadd_int(&ao2.total_containers, 1);
2035 #endif /* defined(AO2_DEBUG) */
2036 
2037  return (struct ao2_container *) self;
2038 }
2039 
2040 struct ao2_container *__ao2_container_alloc_rbtree(unsigned int ao2_options, unsigned int container_options,
2042  const char *tag, const char *file, int line, const char *func)
2043 {
2044  struct ao2_container_rbtree *self;
2045 
2046  if (!sort_fn) {
2047  /* Sanity checks. */
2048  ast_log(__LOG_ERROR, file, line, func, "Missing sort_fn()!\n");
2049  return NULL;
2050  }
2051 
2052  self = __ao2_alloc(sizeof(*self), container_destruct, ao2_options,
2053  tag ?: __PRETTY_FUNCTION__, file, line, func);
2054  return rb_ao2_container_init(self, container_options, sort_fn, cmp_fn);
2055 }
static void rb_ao2_node_destructor(void *v_doomed)
static void rb_delete_fixup(struct ao2_container_rbtree *self, struct rbtree_node *child)
static struct rbtree_node * rb_node_pre(struct rbtree_node *node)
Definition: test_heap.c:38
struct rbtree_node * root
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.
Asterisk main include file. File version handling, generic pbx functions.
int ao2_container_count(struct ao2_container *c)
Returns the number of elements in a container.
#define ARRAY_LEN(a)
Definition: isdn_lib.c:42
static struct rbtree_node * rb_node_next_full(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)
#define __is_ao2_object(user_data, file, line, func)
static void rb_rotate_right(struct ao2_container_rbtree *self, struct rbtree_node *node)
The arg parameter is a search key, but is not an object.
Definition: astobj2.h:1105
#define __container_unlink_node(node, flags)
void container_destruct(void *_c)
static struct rbtree_node * rb_node_post(struct rbtree_node *node)
Common, private definitions for astobj2.
unsigned int is_red
Allow objects with duplicate keys in container.
Definition: astobj2.h:1185
#define FORMAT2
struct rbtree_node * right
enum search_flags flags
enum ao2_container_insert(* ao2_container_insert_fn)(struct ao2_container *self, struct ao2_container_node *node)
Insert a node into this container.
static void rb_insert_fixup(struct ao2_container_rbtree *self, struct rbtree_node *node)
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:765
int() ao2_sort_fn(const void *obj_left, const void *obj_right, int flags)
Type of generic container sort function.
Definition: astobj2.h:1280
static struct rbtree_node * rb_find_initial(struct ao2_container_rbtree *self, void *obj_right, enum search_flags flags, enum equal_node_bias bias)
Assume that the ao2_container is already locked.
Definition: astobj2.h:1067
int(* ao2_container_integrity)(struct ao2_container *self)
Perform an integrity check on the specified container.
struct ao2_container common
Items common to all containers.
#define ao2_alloc_options(data_size, destructor_fn, options)
Definition: astobj2.h:406
#define ast_assert(a)
Definition: utils.h:710
static const struct ao2_container_methods v_table_rbtree
#define __LOG_ERROR
Definition: logger.h:284
#define SWAP(a, b)
Definition: utils.h:230
ao2_container_find_first_fn traverse_first
search_flags
Flags passed to ao2_callback_fn(), ao2_hash_fn(), and ao2_sort_fn() to modify behaviour.
Definition: astobj2.h:1038
#define NULL
Definition: resample.c:96
static struct rbtree_node * rb_node_next(struct rbtree_node *node)
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
Insert objects at the beginning of the container. (Otherwise it is the opposite; insert at the end...
Definition: astobj2.h:1176
Utility functions.
void() ao2_prnt_fn(void *where, const char *fmt,...)
Print output.
Definition: astobj2.h:1442
Generic container node.
#define is_ao2_object(user_data)
equal_node_bias
Traverse in ascending order (First to last container object)
Definition: astobj2.h:1125
int ao2_container_check(struct ao2_container *self, enum search_flags flags)
Perform an integrity check on the specified container.
int __ao2_ref(void *o, int delta, const char *tag, const char *file, int line, const char *func)
Definition: astobj2.c:498
int() ao2_callback_fn(void *obj, void *arg, int flags)
Type of a generic callback function.
Definition: astobj2.h:1230
#define ast_log
Definition: astobj2.c:42
The arg parameter is a partial search key similar to OBJ_SEARCH_KEY.
Definition: astobj2.h:1120
static struct rbtree_node * rb_node_prev_full(struct rbtree_node *node)
empty_node_direction
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.
The ao2 container objects with duplicate keys option field mask.
Definition: astobj2.h:1181
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 struct rbtree_node * rb_node_most_left(struct rbtree_node *node)
#define ao2_ref(o, delta)
Definition: astobj2.h:464
struct rbtree_node * parent
#define AO2_DEVMODE_STAT(stat)
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_delete_node(struct ao2_container_rbtree *self, struct rbtree_node *doomed)
static struct rbtree_node * rb_node_most_right(struct rbtree_node *node)
Traverse in descending order (Last to first container object)
Definition: astobj2.h:1127
static void rb_ao2_destroy(struct ao2_container_rbtree *self)
void(* ao2_container_destroy_fn)(struct ao2_container *self)
Destroy this container.
void(* ao2_container_statistics)(struct ao2_container *self, void *where, ao2_prnt_fn *prnt)
Display statistics of the specified container.
#define LOG_ERROR
Definition: logger.h:285
ao2_iterator_next_fn iterator_next
Traverse in pre-order (Node then children, for tree container)
Definition: astobj2.h:1136
static struct rbtree_node * rb_node_prev(struct rbtree_node *node)
#define FORMAT
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 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)
unsigned int destroying
TRUE if the container is being destroyed.
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)
Prototypes for public functions only of internal interest,.
#define AO2_TRAVERSAL_STATE_SIZE
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)
struct ao2_container_node common
Items common to all container nodes.
The arg parameter is an object of the same type.
Definition: astobj2.h:1091
Replace objects with duplicate keys in container.
Definition: astobj2.h:1215
Traverse in post-order (Children then node, for tree container)
Definition: astobj2.h:1145
unsigned int ao2_options_get(void *obj)
Retrieve the ao2 options used to create the object.
Definition: astobj2.c:778
static void rb_rotate_left(struct ao2_container_rbtree *self, struct rbtree_node *node)
Common, private definitions for astobj2 containers.
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.
enum ao2_lock_req __adjust_lock(void *user_data, enum ao2_lock_req lock_how, int keep_stronger)
Definition: astobj2.c:425
struct rbtree_node * left
Reject objects with duplicate keys in container.
Definition: astobj2.h:1192
Generic container type.
static struct test_options options
Search option field mask.
Definition: astobj2.h:1076
void() ao2_prnt_obj_fn(void *v_obj, void *where, ao2_prnt_fn *prnt)
Print object key.
Definition: astobj2.h:1454
struct ao2_container * my_container
static struct rbtree_node * rb_ao2_iterator_next(struct ao2_container_rbtree *self, struct rbtree_node *node, enum ao2_iterator_flags flags)
ao2_iterator_flags
Definition: astobj2.h:1855
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.
ao2_container_alloc_empty_clone_fn alloc_empty_clone
Create an empty copy of this container.
Reject duplicate objects in container.
Definition: astobj2.h:1205
static enum ao2_container_insert rb_ao2_insert_node(struct ao2_container_rbtree *self, struct rbtree_node *node)
ao2_callback_fn * cmp_fn
ao2_container_new_node_fn new_node
Traverse order option field mask.
Definition: astobj2.h:1123
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.