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];
157 while (
node->right) {
181 while (
node->parent) {
208 while (
node->parent) {
243 if (
node->parent->left ==
node &&
node->parent->right) {
248 return node->parent->right;
278 while (
node->right) {
368 cmp = sort_fn(right_most->
common.
obj, obj_right, flags);
385 cmp = sort_fn(cur->
common.
obj, obj_right, flags);
408 if (cur->
parent == empty) {
422 cmp = sort_fn(cur->
common.
obj, obj_right, flags);
467 }
else if (
node->parent->left ==
node) {
469 node->parent->left = child;
472 node->parent->right = child;
483 node->parent = child;
520 }
else if (
node->parent->right ==
node) {
522 node->parent->right = child;
525 node->parent->left = child;
536 node->parent = child;
555 const char *tag,
const char *
file,
int line,
const char *func)
582 while (self->
root != child && !child->
is_red) {
631 if (sibling->
right) {
748 if (next->
right == next) {
750 next->
right = doomed;
764 child = doomed->
right;
767 child = doomed->
left;
769 child = doomed->
right;
779 if (need_fixup && !child) {
855#if defined(AO2_DEBUG)
862#if defined(AO2_DEBUG)
904 __ao2_ref(obj_new, +1, tag ?:
"Container node creation",
file, line, func);
905 node->common.obj = obj_new;
925 while (
node->parent &&
node->parent->is_red) {
926 g_parent =
node->parent->parent;
931 if (
node->parent == g_parent->
left) {
955 node->parent->is_red = 0;
983 node->parent->is_red = 0;
1090 }
else if (cmp < 0) {
1266 flags =
state->flags;
1290 if (!
node->common.obj) {
1295 if (
state->sort_fn) {
1314 if (
node->common.obj) {
1358 if (!
node->common.obj) {
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) {
1431 cmp = sort_fn(next->
common.
obj, obj_right, sort_flags);
1471 state->flags = flags;
1495 if (!
state->sort_fn) {
1498 if (!
node->common.obj) {
1530 if (!
state->sort_fn) {
1533 if (!
node->common.obj) {
1571 while (!
node->common.obj) {
1594 while (!
node->common.obj) {
1632 if (
node->common.obj) {
1646 if (
node->common.obj) {
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");
1700 node->is_red ?
"Red" :
"Black",
1702 if (
node->common.obj && prnt_obj) {
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)
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);
1788 if (!
node->is_red) {
1797#if defined(AO2_DEBUG)
1877 if (
node->left->is_red) {
1882 if (
node->right->is_red) {
1887 }
else if (
node->left ||
node->right) {
1903 if (
node->left->is_red !=
node->right->is_red) {
1907 if (
node->left->is_red) {
1915 "Tree node is black and the red child does not have two children!\n");
1919 }
else if ((
node->left && !
node->left->is_red)
1920 || (
node->right && !
node->right->is_red)) {
1929 if (
node->common.obj) {
1939 if (!
node->common.obj) {
1950 obj_last =
node->common.obj;
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) {
1969 count_node, self->
common.nodes);
1986#
if defined(AO2_DEBUG)
2024 const char *tag,
const char *
file,
int line,
const char *func)
2035 tag ?: __PRETTY_FUNCTION__,
file, line, func);
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)
void() ao2_prnt_obj_fn(void *v_obj, void *where, ao2_prnt_fn *prnt)
Print object key.
unsigned int ao2_options_get(void *obj)
Retrieve the ao2 options used to create the object.
@ AO2_ALLOC_OPT_LOCK_NOLOCK
@ AO2_ALLOC_OPT_NO_REF_DEBUG
int ao2_container_check(struct ao2_container *self, enum search_flags flags)
Perform an integrity check on the specified container.
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.
@ AO2_ITERATOR_DESCENDING
int() ao2_sort_fn(const void *obj_left, const void *obj_right, int flags)
Type of generic container sort function.
#define ao2_ref(o, delta)
Reference/unreference an object and return the old refcount.
#define ao2_alloc_options(data_size, destructor_fn, options)
int __ao2_ref(void *o, int delta, const char *tag, const char *file, int line, const char *func)
search_flags
Flags passed to ao2_callback_fn(), ao2_hash_fn(), and ao2_sort_fn() to modify behaviour.
@ OBJ_ORDER_MASK
Traverse order option field mask.
@ OBJ_SEARCH_PARTIAL_KEY
The arg parameter is a partial search key similar to OBJ_SEARCH_KEY.
@ OBJ_ORDER_DESCENDING
Traverse in descending order (Last to first container object)
@ OBJ_SEARCH_OBJECT
The arg parameter is an object of the same type.
@ OBJ_ORDER_PRE
Traverse in pre-order (Node then children, for tree container)
@ OBJ_ORDER_ASCENDING
Traverse in ascending order (First to last container object)
@ OBJ_NOLOCK
Assume that the ao2_container is already locked.
@ OBJ_SEARCH_MASK
Search option field mask.
@ OBJ_ORDER_POST
Traverse in post-order (Children then node, for tree container)
@ OBJ_SEARCH_KEY
The arg parameter is a search key, but is not an object.
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
void() ao2_prnt_fn(void *where, const char *fmt,...)
Print output.
@ AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT
Reject duplicate objects in container.
@ AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN
Insert objects at the beginning of the container. (Otherwise it is the opposite; insert at the end....
@ AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW
Allow objects with duplicate keys in container.
@ AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT
Reject objects with duplicate keys in container.
@ AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE
Replace objects with duplicate keys in container.
@ AO2_CONTAINER_ALLOC_OPT_DUPS_MASK
The ao2 container objects with duplicate keys option field mask.
void container_destruct(void *_c)
Common, private definitions for astobj2 containers.
void(* ao2_container_statistics)(struct ao2_container *self, void *where, ao2_prnt_fn *prnt)
Display statistics of the specified container.
void(* ao2_container_destroy_fn)(struct ao2_container *self)
Destroy this container.
int(* ao2_container_integrity)(struct ao2_container *self)
Perform an integrity check on the specified container.
struct ao2_container_node *(* ao2_container_new_node_fn)(struct ao2_container *self, void *obj_new, const char *tag, const char *file, int line, const char *func)
Create a new container node.
void(* ao2_container_display)(struct ao2_container *self, void *where, ao2_prnt_fn *prnt, ao2_prnt_obj_fn *prnt_obj)
Display contents of the specified container.
#define __container_unlink_node(node, flags)
#define AO2_TRAVERSAL_STATE_SIZE
struct ao2_container_node *(* ao2_iterator_next_fn)(struct ao2_container *self, struct ao2_container_node *prev, enum ao2_iterator_flags flags)
Find the next non-empty iteration node in the container.
struct ao2_container_node *(* ao2_container_find_first_fn)(struct ao2_container *self, enum search_flags flags, void *arg, void *v_state)
Find the first container node in a traversal.
struct ao2_container_node *(* ao2_container_find_next_fn)(struct ao2_container *self, void *v_state, struct ao2_container_node *prev)
Find the next container node in a traversal.
struct ao2_container *(* ao2_container_alloc_empty_clone_fn)(struct ao2_container *self, const char *tag, const char *file, int line, const char *func)
Create an empty copy of this container.
@ AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED
@ AO2_CONTAINER_INSERT_NODE_REJECTED
@ AO2_CONTAINER_INSERT_NODE_INSERTED
@ AO2_UNLINK_NODE_UNLINK_OBJECT
enum ao2_container_insert(* ao2_container_insert_fn)(struct ao2_container *self, struct ao2_container_node *node)
Insert a node into this container.
Common, private definitions for astobj2.
#define is_ao2_object(user_data)
#define AO2_DEVMODE_STAT(stat)
#define __is_ao2_object(user_data, file, line, func)
static void rb_rotate_right(struct ao2_container_rbtree *self, struct rbtree_node *node)
static void rb_insert_fixup(struct ao2_container_rbtree *self, struct rbtree_node *node)
struct ao2_container * __ao2_container_alloc_rbtree(unsigned int ao2_options, unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn, const char *tag, const char *file, int line, const char *func)
static enum empty_node_direction rb_find_empty_direction(struct rbtree_node *empty, ao2_sort_fn *sort_fn, void *obj_right, enum search_flags flags, enum equal_node_bias bias)
static struct rbtree_node * rb_node_prev_full(struct rbtree_node *node)
static struct rbtree_node * rb_node_post(struct rbtree_node *node)
static struct rbtree_node * rb_ao2_find_next(struct ao2_container_rbtree *self, struct rbtree_traversal_state *state, struct rbtree_node *prev)
static void rb_ao2_destroy(struct ao2_container_rbtree *self)
static struct rbtree_node * rb_node_most_left(struct rbtree_node *node)
static void rb_rotate_left(struct ao2_container_rbtree *self, struct rbtree_node *node)
static struct rbtree_node * rb_node_next(struct rbtree_node *node)
static struct rbtree_node * rb_ao2_new_node(struct ao2_container_rbtree *self, void *obj_new, const char *tag, const char *file, int line, const char *func)
static struct ao2_container * rb_ao2_container_init(struct ao2_container_rbtree *self, unsigned int options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
Initialize a rbtree container.
static enum ao2_container_insert rb_ao2_insert_node(struct ao2_container_rbtree *self, struct rbtree_node *node)
static struct rbtree_node * rb_ao2_iterator_next(struct ao2_container_rbtree *self, struct rbtree_node *node, enum ao2_iterator_flags flags)
static struct ao2_container * rb_ao2_alloc_empty_clone(struct ao2_container_rbtree *self, const char *tag, const char *file, int line, const char *func)
static struct rbtree_node * rb_node_most_right(struct rbtree_node *node)
static struct rbtree_node * rb_node_pre(struct rbtree_node *node)
static struct rbtree_node * rb_find_initial(struct ao2_container_rbtree *self, void *obj_right, enum search_flags flags, enum equal_node_bias bias)
static const struct ao2_container_methods v_table_rbtree
static void rb_delete_node(struct ao2_container_rbtree *self, struct rbtree_node *doomed)
static void rb_delete_fixup(struct ao2_container_rbtree *self, struct rbtree_node *child)
static struct rbtree_node * rb_ao2_find_first(struct ao2_container_rbtree *self, enum search_flags flags, void *arg, struct rbtree_traversal_state *state)
static struct rbtree_node * rb_node_prev(struct rbtree_node *node)
static void rb_ao2_node_destructor(void *v_doomed)
static struct rbtree_node * rb_node_next_full(struct rbtree_node *node)
int ast_atomic_fetchadd_int(volatile int *p, int v)
Atomically add v to *p and return the previous value of *p.
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
struct ao2_container * my_container
struct ao2_container common
Items common to all containers.
struct rbtree_node * root
unsigned int destroying
TRUE if the container is being destroyed.
const struct ao2_container_methods * v_table
struct rbtree_node * right
struct rbtree_node * parent
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))]