80 #if defined(AO2_DEBUG)
83 int fixup_insert_left[3];
85 int fixup_insert_right[3];
87 int fixup_delete_left[4];
89 int fixup_delete_right[4];
91 int delete_children[3];
105 enum empty_node_direction {
157 while (node->
right) {
177 return rb_node_most_left(node->
right);
204 return rb_node_most_right(node->
left);
278 while (node->
right) {
279 node = rb_node_most_left(node->
right);
312 node = rb_node_next(node);
332 node = rb_node_prev(node);
366 right_most = rb_node_most_right(empty->
left);
368 cmp = sort_fn(right_most->
common.
obj, obj_right, flags);
383 cur = rb_node_most_left(empty->
right);
385 cmp = sort_fn(cur->
common.
obj, obj_right, flags);
404 cur = rb_node_most_right(cur->
left);
408 if (cur->
parent == empty) {
422 cmp = sort_fn(cur->
common.
obj, obj_right, flags);
555 const char *tag,
const char *file,
int line,
const char *func)
557 if (!__is_ao2_object(
self, file, line, func)) {
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);
582 while (self->root != child && !child->
is_red) {
586 ast_assert(sibling != NULL);
589 AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[0]);
594 ast_assert(sibling != NULL);
608 AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[1]);
618 AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[2]);
619 ast_assert(sibling->
left != NULL);
625 ast_assert(sibling != NULL);
628 AO2_DEVMODE_STAT(++self->stats.fixup_delete_left[3]);
631 if (sibling->
right) {
640 ast_assert(sibling != NULL);
643 AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[0]);
648 ast_assert(sibling != NULL);
662 AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[1]);
672 AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[2]);
673 ast_assert(sibling->
right != NULL);
679 ast_assert(sibling != NULL);
682 AO2_DEVMODE_STAT(++self->stats.fixup_delete_right[3]);
727 AO2_DEVMODE_STAT(++self->stats.delete_children[2]);
728 next = rb_node_most_left(doomed->
right);
748 if (next->
right == next) {
750 next->
right = doomed;
758 ast_assert(doomed->
left == NULL);
764 child = doomed->
right;
767 child = doomed->
left;
769 child = doomed->
right;
773 AO2_DEVMODE_STAT(++self->stats.delete_children[1]);
775 AO2_DEVMODE_STAT(++self->stats.delete_children[0]);
778 need_fixup = (!doomed->
is_red && !
self->common.destroying);
779 if (need_fixup && !child) {
786 rb_delete_fixup(
self, doomed);
787 ast_assert(doomed->
left == NULL);
788 ast_assert(doomed->
right == NULL);
789 ast_assert(!doomed->
is_red);
806 rb_delete_fixup(
self, child);
810 AO2_DEVMODE_STAT(--self->common.nodes);
828 static void rb_ao2_node_destructor(
void *v_doomed)
850 is_ao2_object(my_container);
855 #if defined(AO2_DEBUG)
858 ast_log(LOG_ERROR,
"Container integrity failed before node deletion.\n");
861 rb_delete_node(my_container, doomed);
862 #if defined(AO2_DEBUG)
865 ast_log(LOG_ERROR,
"Container integrity failed after node deletion.\n");
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)
898 node = ao2_alloc_options(
sizeof(*node), rb_ao2_node_destructor,
904 __ao2_ref(obj_new, +1, tag ?:
"Container node creation", file, line, func);
929 ast_assert(g_parent != NULL);
935 AO2_DEVMODE_STAT(++self->stats.fixup_insert_left[0]);
949 AO2_DEVMODE_STAT(++self->stats.fixup_insert_left[1]);
954 AO2_DEVMODE_STAT(++self->stats.fixup_insert_left[2]);
963 AO2_DEVMODE_STAT(++self->stats.fixup_insert_right[0]);
977 AO2_DEVMODE_STAT(++self->stats.fixup_insert_right[1]);
982 AO2_DEVMODE_STAT(++self->stats.fixup_insert_right[2]);
997 self->root->is_red = 0;
1025 sort_fn =
self->common.sort_fn;
1026 options =
self->common.options;
1064 rb_insert_fixup(
self, node);
1075 rb_insert_fixup(
self, node);
1088 rb_insert_fixup(
self, node);
1090 }
else if (cmp < 0) {
1099 rb_insert_fixup(
self, node);
1113 rb_insert_fixup(
self, node);
1127 rb_insert_fixup(
self, node);
1135 switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
1152 next = rb_node_next_full(next);
1168 next = rb_node_prev_full(cur);
1187 cur = rb_node_most_right(cur->
left);
1193 next = rb_node_prev_full(next);
1209 next = rb_node_next_full(cur);
1228 cur = rb_node_most_left(cur->
right);
1241 rb_insert_fixup(
self, node);
1266 flags = state->
flags;
1274 node = rb_node_next(node);
1277 node = rb_node_prev(node);
1280 node = rb_node_pre(node);
1283 node = rb_node_post(node);
1350 sort_fn =
self->common.sort_fn;
1360 if (rb_find_empty_direction(node, sort_fn, obj_right, sort_flags, bias)
1370 next = rb_node_next_full(node);
1376 next = rb_node_prev_full(node);
1380 cmp = sort_fn(next->
common.
obj, obj_right, sort_flags);
1392 cmp = sort_fn(node->
common.
obj, obj_right, sort_flags);
1395 }
else if (cmp < 0) {
1418 next = rb_node_next_full(node);
1426 next = rb_node_prev_full(node);
1431 cmp = sort_fn(next->
common.
obj, obj_right, sort_flags);
1464 if (self->common.destroying) {
1469 memset(state, 0,
sizeof(*state));
1471 state->
flags = flags;
1473 switch (flags & OBJ_SEARCH_MASK) {
1478 state->
sort_fn =
self->common.sort_fn;
1492 switch (flags & OBJ_ORDER_MASK) {
1497 node = rb_node_most_left(self->root);
1499 node = rb_node_next_full(node);
1508 switch (self->common.options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
1524 node = rb_find_initial(
self, arg, flags, bias);
1532 node = rb_node_most_right(self->root);
1534 node = rb_node_prev_full(node);
1543 switch (self->common.options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
1559 node = rb_find_initial(
self, arg, flags, bias);
1572 node = rb_node_pre(node);
1585 node = rb_node_most_left(node);
1595 node = rb_node_post(node);
1631 node = rb_node_most_right(self->root);
1638 node = rb_node_prev_full(node);
1645 node = rb_node_most_left(self->root);
1652 node = rb_node_next_full(node);
1670 ast_log(LOG_ERROR,
"Node ref leak. Red-Black tree container still has nodes!\n");
1675 #if defined(AO2_DEBUG)
1688 #define FORMAT "%16s, %16s, %16s, %16s, %5s, %16s, %s\n"
1689 #define FORMAT2 "%16p, %16p, %16p, %16p, %5s, %16p, "
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,
1700 node->
is_red ?
"Red" :
"Black",
1703 prnt_obj(node->
common.
obj, where, prnt);
1713 #if defined(AO2_DEBUG)
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]);
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]);
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]);
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]);
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]);
1753 #if defined(AO2_DEBUG)
1764 static int rb_check_black_height(
struct rbtree_node *node)
1774 height_left = rb_check_black_height(node->
left);
1775 if (height_left < 0) {
1778 height_right = rb_check_black_height(node->
right);
1779 if (height_right < 0) {
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);
1797 #if defined(AO2_DEBUG)
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");
1840 ast_log(LOG_ERROR,
"Tree root is not a root node!\n");
1844 if (self->root->is_red) {
1846 ast_log(LOG_ERROR,
"Tree root is red!\n");
1852 if (node->
left == node) {
1853 ast_log(LOG_ERROR,
"Tree node's left pointer points to itself!\n");
1857 ast_log(LOG_ERROR,
"Tree node's left child does not link back!\n");
1862 if (node->
right == node) {
1863 ast_log(LOG_ERROR,
"Tree node's right pointer points to itself!\n");
1867 ast_log(LOG_ERROR,
"Tree node's right child does not link back!\n");
1879 ast_log(LOG_ERROR,
"Tree node is red and its left child is red!\n");
1884 ast_log(LOG_ERROR,
"Tree node is red and its right child is red!\n");
1892 ast_log(LOG_ERROR,
"Tree node is red and it only has one child!\n");
1915 "Tree node is black and the red child does not have two children!\n");
1922 ast_log(LOG_ERROR,
"Tree node is black and its only child is black!\n");
1933 node = rb_node_pre(node);
1938 for (node = rb_node_most_left(self->root); node; node = rb_node_next(node)) {
1946 ast_log(LOG_ERROR,
"Tree nodes are out of sorted order!\n");
1954 if (!res && rb_check_black_height(self->root) < 0) {
1962 ast_log(LOG_ERROR,
"Total object count does not match ao2_container_count()!\n");
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);
1986 #
if defined(AO2_DEBUG)
2011 self->common.sort_fn =
sort_fn;
2012 self->common.cmp_fn =
cmp_fn;
2013 self->common.options =
options;
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)
2030 ast_log(__LOG_ERROR, file, line, func,
"Missing sort_fn()!\n");
2034 self = __ao2_alloc(
sizeof(*
self), container_destruct, ao2_options,
2035 tag ?: __PRETTY_FUNCTION__, file, line, func);
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.
void( ao2_prnt_fn)(void *where, const char *fmt,...)
Print output.
void( ao2_prnt_obj_fn)(void *v_obj, void *where, ao2_prnt_fn *prnt)
Print object key.
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.
int( ao2_callback_fn)(void *obj, void *arg, int flags)
Type of a generic callback function.
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.
Common, private definitions for astobj2.
Allow objects with duplicate keys in container.
struct rbtree_node * right
enum ao2_container_insert(* ao2_container_insert_fn)(struct ao2_container *self, struct ao2_container_node *node)
Insert a node into this container.
Assume that the ao2_container is already locked.
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.
static const struct ao2_container_methods v_table_rbtree
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.
int ast_atomic_fetchadd_int(volatile int *p, int v)
Atomically add v to *p and return the previous value of *p.
Insert objects at the beginning of the container. (Otherwise it is the opposite; insert at the end...
Traverse in ascending order (First to last container object)
int ao2_container_check(struct ao2_container *self, enum search_flags flags)
Perform an integrity check on the specified container.
The arg parameter is a partial search key similar to OBJ_SEARCH_KEY.
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.
#define ao2_ref(o, delta)
Reference/unreference an object and return the old refcount.
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.
struct rbtree_node * parent
Traverse in descending order (Last to first container object)
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.
ao2_iterator_next_fn iterator_next
Traverse in pre-order (Node then children, for tree container)
unsigned int destroying
TRUE if the container is being destroyed.
Prototypes for public functions only of internal interest,.
#define AO2_TRAVERSAL_STATE_SIZE
struct ao2_container_node common
Items common to all container nodes.
The arg parameter is an object of the same type.
Replace objects with duplicate keys in container.
Traverse in post-order (Children then node, for tree container)
unsigned int ao2_options_get(void *obj)
Retrieve the ao2 options used to create the object.
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.
struct rbtree_node * left
Reject objects with duplicate keys in container.
int( ao2_sort_fn)(const void *obj_left, const void *obj_right, int flags)
Type of generic container sort function.
Search option field mask.
struct ao2_container * my_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.
ao2_container_alloc_empty_clone_fn alloc_empty_clone
Create an empty copy of this container.
Reject duplicate objects in container.
ao2_container_new_node_fn new_node
Traverse order option field mask.
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.