52 #if defined(AO2_DEBUG)
91 unsigned int descending:1;
117 const char *tag,
const char *file,
int line,
const char *func)
119 if (!__is_ao2_object(
self, file, line, func)) {
123 return __ao2_container_alloc_hash(
ao2_options_get(
self), self->common.options,
124 self->n_buckets, self->hash_fn, self->common.sort_fn, self->common.cmp_fn,
125 tag, file, line, func);
143 static void hash_ao2_node_destructor(
void *v_doomed)
166 is_ao2_object(my_container);
171 #if defined(AO2_DEBUG)
174 ast_log(LOG_ERROR,
"Container integrity failed before node deletion.\n");
179 AO2_DEVMODE_STAT(--my_container->
common.nodes);
211 node = ao2_alloc_options(
sizeof(*node), hash_ao2_node_destructor,
219 __ao2_ref(obj_new, +1, tag ?:
"Container node creation", file, line, func);
246 bucket = &
self->buckets[node->
my_bucket];
247 sort_fn =
self->common.sort_fn;
248 options =
self->common.options;
339 memset(state, 0,
sizeof(*state));
341 state->
flags = flags;
363 bucket_cur = abs(self->hash_fn(arg, flags & OBJ_SEARCH_MASK)
365 state->
sort_fn =
self->common.sort_fn;
370 state->
sort_fn =
self->common.sort_fn;
385 if (bucket_cur < 0) {
386 bucket_cur =
self->n_buckets - 1;
394 for (; state->
bucket_last <= bucket_cur; --bucket_cur) {
427 if (bucket_cur < 0) {
436 for (; bucket_cur < state->
bucket_last; ++bucket_cur) {
490 flags = state->
flags;
502 goto hash_descending_resume;
505 for (; state->
bucket_last <= bucket_cur; --bucket_cur) {
542 hash_descending_resume:;
546 goto hash_ascending_resume;
549 for (; bucket_cur < state->
bucket_last; ++bucket_cur) {
586 hash_ascending_resume:;
632 cur_bucket =
self->n_buckets;
636 while (0 <= --cur_bucket) {
667 while (++cur_bucket < self->n_buckets) {
683 #if defined(AO2_DEBUG)
698 ++
self->buckets[i].elements;
699 if (self->buckets[i].max_elements < self->buckets[i].elements) {
700 self->buckets[i].max_elements =
self->buckets[i].elements;
705 #if defined(AO2_DEBUG)
719 --
self->buckets[node->
my_bucket].elements;
736 for (idx = self->n_buckets; idx--;) {
738 ast_log(LOG_ERROR,
"Node ref leak. Hash container still has nodes!\n");
745 #if defined(AO2_DEBUG)
758 #define FORMAT "%6s, %16s, %16s, %16s, %16s, %s\n"
759 #define FORMAT2 "%6d, %16p, %16p, %16p, %16p, "
762 int suppressed_buckets = 0;
765 prnt(where,
"Number of buckets: %d\n\n", self->n_buckets);
767 prnt(where, FORMAT,
"Bucket",
"Node",
"Prev",
"Next",
"Obj",
"Key");
768 for (bucket = 0; bucket <
self->n_buckets; ++bucket) {
771 suppressed_buckets = 0;
786 }
else if (!suppressed_buckets) {
787 suppressed_buckets = 1;
788 prnt(where,
"...\n");
797 #if defined(AO2_DEBUG)
811 #define FORMAT "%10.10s %10.10s %10.10s\n"
812 #define FORMAT2 "%10d %10d %10d\n"
815 int suppressed_buckets = 0;
817 prnt(where,
"Number of buckets: %d\n\n", self->n_buckets);
819 prnt(where, FORMAT,
"Bucket",
"Objects",
"Max");
820 for (bucket = 0; bucket <
self->n_buckets; ++bucket) {
821 if (self->buckets[bucket].max_elements) {
822 suppressed_buckets = 0;
823 prnt(where, FORMAT2, bucket, self->buckets[bucket].elements,
824 self->buckets[bucket].max_elements);
825 }
else if (!suppressed_buckets) {
826 suppressed_buckets = 1;
827 prnt(where,
"...\n");
836 #if defined(AO2_DEBUG)
855 int count_total_node;
862 count_total_node = 0;
865 for (bucket = 0; bucket <
self->n_buckets; ++bucket) {
878 ast_log(LOG_ERROR,
"Bucket %d list tail is NULL when it should not be!\n",
883 ast_log(LOG_ERROR,
"Bucket %d list tail node is not the last node!\n",
889 ast_log(LOG_ERROR,
"Bucket %d list head is NULL when it should not be!\n",
894 ast_log(LOG_ERROR,
"Bucket %d list head node is not the first node!\n",
898 for (; node; node = next) {
903 ast_log(LOG_ERROR,
"Bucket %d list node's prev pointer points to itself!\n",
908 ast_log(LOG_ERROR,
"Bucket %d list node's prev node does not link back!\n",
913 ast_log(LOG_ERROR,
"Bucket %d backward list chain is broken!\n",
922 ast_log(LOG_ERROR,
"Bucket %d list node's next pointer points to itself!\n",
927 ast_log(LOG_ERROR,
"Bucket %d list node's next node does not link back!\n",
932 ast_log(LOG_ERROR,
"Bucket %d forward list chain is broken!\n",
938 ast_log(LOG_ERROR,
"Bucket %d node claims to be in bucket %d!\n",
953 if (bucket != bucket_exp) {
954 ast_log(LOG_ERROR,
"Bucket %d node hashes to bucket %d!\n",
960 if (self->common.sort_fn) {
963 ast_log(LOG_ERROR,
"Bucket %d nodes out of sorted order!\n",
972 if (count_obj != self->buckets[bucket].elements) {
973 ast_log(LOG_ERROR,
"Bucket %d object count of %d does not match stat of %d!\n",
974 bucket, count_obj, self->buckets[bucket].elements);
979 count_total_obj += count_obj;
985 "Total object count of %d does not match ao2_container_count() of %d!\n",
991 if (count_total_node != self->common.nodes) {
992 ast_log(LOG_ERROR,
"Total node count of %d does not match stat of %d!\n",
993 count_total_node, self->common.nodes);
1010 #
if defined(AO2_DEBUG)
1011 .link_stat = hash_ao2_link_node_stat,
1012 .unlink_stat = hash_ao2_unlink_node_stat,
1054 self->common.sort_fn =
sort_fn;
1055 self->common.cmp_fn =
cmp_fn;
1056 self->common.options =
options;
1057 self->hash_fn = hash_fn ? hash_fn :
hash_zero;
1058 self->n_buckets = n_buckets;
1067 struct ao2_container *__ao2_container_alloc_hash(
unsigned int ao2_options,
1068 unsigned int container_options,
unsigned int n_buckets,
ao2_hash_fn *hash_fn,
1070 const char *tag,
const char *file,
int line,
const char *func)
1072 unsigned int num_buckets;
1073 size_t container_size;
1076 num_buckets = hash_fn ? n_buckets : 1;
1079 self = __ao2_alloc(container_size, container_destruct, ao2_options,
1080 tag ?: __PRETTY_FUNCTION__, file, line, func);
1085 struct ao2_container *__ao2_container_alloc_list(
unsigned int ao2_options,
1087 const char *tag,
const char *file,
int line,
const char *func)
1089 return __ao2_container_alloc_hash(ao2_options, container_options, 1, NULL,
1090 sort_fn, cmp_fn, tag, file, line, func);
#define AST_DLLIST_TRAVERSE_SAFE_BEGIN(head, var, field)
Loops safely over (traverses) the entries in a list.
struct ao2_container common
Items common to all containers.
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.
#define AST_DLLIST_INSERT_HEAD(head, elm, field)
Inserts a list entry at the head of a list.
The arg parameter is a search key, but is not an object.
Common, private definitions for astobj2.
Allow objects with duplicate keys in container.
enum ao2_container_insert(* ao2_container_insert_fn)(struct ao2_container *self, struct ao2_container_node *node)
Insert a node into this container.
int( ao2_hash_fn)(const void *obj, int flags)
#define AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(head, var, field)
Loops safely over (traverses) the entries in a list.
Assume that the ao2_container is already locked.
int(* ao2_container_integrity)(struct ao2_container *self)
Perform an integrity check on the specified container.
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.
#define AST_DLLIST_INSERT_AFTER_CURRENT(elm, field)
Inserts a list node after the current node during a traversal.
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.
static struct ao2_container * hash_ao2_container_init(struct ao2_container_hash *self, unsigned int options, unsigned int n_buckets, ao2_hash_fn *hash_fn, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
Initialize a hash container with the desired number of buckets.
#define AST_DLLIST_INSERT_TAIL(head, elm, field)
Appends a list entry to the tail of a list.
The arg parameter is a partial search key similar to OBJ_SEARCH_KEY.
#define AST_DLLIST_NEXT(elm, field)
Returns the next entry in the list after the given entry.
A set of macros to manage doubly-linked lists.
#define AST_DLLIST_HEAD_NOLOCK(name, type)
Defines a structure to be used to hold a list of specified type (with no lock).
static int hash_zero(const void *user_obj, const int flags)
always zero hash function
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.
Traverse in descending order (Last to first container object)
#define AST_DLLIST_INSERT_BEFORE_CURRENT(elm, field)
Inserts a list node before the current node during a traversal.
struct ao2_container_node common
Items common to all container nodes.
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)
static const struct ao2_container_methods v_table_hash
unsigned int destroying
TRUE if the container is being destroyed.
#define AST_DLLIST_EMPTY(head)
Checks whether the specified list contains any entries.
Prototypes for public functions only of internal interest,.
#define AO2_TRAVERSAL_STATE_SIZE
#define AST_DLLIST_TRAVERSE_SAFE_END
Closes a safe loop traversal block.
The arg parameter is an object of the same type.
Replace objects with duplicate keys in container.
#define AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END
Closes a safe loop traversal block.
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.
#define AST_DLLIST_PREV(elm, field)
Returns the previous entry in the list before the given entry.
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.
#define AST_DLLIST_REMOVE(head, elm, field)
Removes a specific entry from a list.
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 hash_bucket buckets[0]
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.
#define AST_DLLIST_FIRST(head)
Returns the first entry contained in a list.
ao2_container_alloc_empty_clone_fn alloc_empty_clone
Create an empty copy of this container.
struct hash_bucket_node::@304 links
struct hash_bucket::@305 list
Reject duplicate objects in container.
ao2_container_new_node_fn new_node
Traverse order option field mask.
#define AST_DLLIST_LAST(head)
Returns the last entry contained in a list.
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.
#define AST_DLLIST_ENTRY(type)
Declare previous/forward links inside a list entry.
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.