Split astobj2.c into more maintainable components.
[asterisk/asterisk.git] / main / astobj2_container.c
1 /* astobj2 - replacement containers for asterisk data structures.
2  *
3  * Copyright (C) 2006 Marta Carbone, Luigi Rizzo - Univ. di Pisa, Italy
4  *
5  * See http://www.asterisk.org for more information about
6  * the Asterisk project. Please do not directly contact
7  * any of the maintainers of this project for assistance;
8  * the project provides a web site, mailing lists and IRC
9  * channels for your use.
10  *
11  * This program is free software, distributed under the terms of
12  * the GNU General Public License Version 2. See the LICENSE file
13  * at the top of the source tree.
14  */
15
16 /*! \file
17  *
18  * \brief Functions implementing astobj2 objects.
19  *
20  * \author Richard Mudgett <rmudgett@digium.com>
21  */
22
23 #include "asterisk.h"
24
25 ASTERISK_FILE_VERSION(__FILE__, "$Revision$")
26
27 #include "asterisk/_private.h"
28 #include "asterisk/astobj2.h"
29 #include "astobj2_private.h"
30 #include "astobj2_container_private.h"
31 #include "asterisk/cli.h"
32
33 /*!
34  * return the number of elements in the container
35  */
36 int ao2_container_count(struct ao2_container *c)
37 {
38         return ast_atomic_fetchadd_int(&c->elements, 0);
39 }
40
41 /*!
42  * \internal
43  * \brief Link an object into this container.  (internal)
44  *
45  * \param self Container to operate upon.
46  * \param obj_new Object to insert into the container.
47  * \param flags search_flags to control linking the object.  (OBJ_NOLOCK)
48  * \param tag used for debugging.
49  * \param file Debug file name invoked from
50  * \param line Debug line invoked from
51  * \param func Debug function name invoked from
52  *
53  * \retval 0 on errors.
54  * \retval 1 on success.
55  */
56 static int internal_ao2_link(struct ao2_container *self, void *obj_new, int flags, const char *tag, const char *file, int line, const char *func)
57 {
58         int res;
59         enum ao2_lock_req orig_lock;
60         struct ao2_container_node *node;
61
62         if (!is_ao2_object(obj_new) || !is_ao2_object(self)
63                 || !self->v_table || !self->v_table->new_node || !self->v_table->insert) {
64                 /* Sanity checks. */
65                 ast_assert(0);
66                 return 0;
67         }
68
69         if (flags & OBJ_NOLOCK) {
70                 orig_lock = __adjust_lock(self, AO2_LOCK_REQ_WRLOCK, 1);
71         } else {
72                 ao2_wrlock(self);
73                 orig_lock = AO2_LOCK_REQ_MUTEX;
74         }
75
76         res = 0;
77         node = self->v_table->new_node(self, obj_new, tag, file, line, func);
78         if (node) {
79 #if defined(AO2_DEBUG) && defined(AST_DEVMODE)
80                 switch (self->v_table->type) {
81                 case AO2_CONTAINER_RTTI_HASH:
82                         if (!self->sort_fn) {
83                                 /*
84                                  * XXX chan_iax2 plays games with the hash function so we cannot
85                                  * routinely do an integrity check on this type of container.
86                                  * chan_iax2 should be changed to not abuse the hash function.
87                                  */
88                                 break;
89                         }
90                         /* Fall through. */
91                 case AO2_CONTAINER_RTTI_RBTREE:
92                         if (ao2_container_check(self, OBJ_NOLOCK)) {
93                                 ast_log(LOG_ERROR, "Container integrity failed before insert.\n");
94                         }
95                         break;
96                 }
97 #endif  /* defined(AO2_DEBUG) && defined(AST_DEVMODE) */
98                 /* Insert the new node. */
99                 switch (self->v_table->insert(self, node)) {
100                 case AO2_CONTAINER_INSERT_NODE_INSERTED:
101                         node->is_linked = 1;
102                         ast_atomic_fetchadd_int(&self->elements, 1);
103 #if defined(AST_DEVMODE)
104                         AO2_DEVMODE_STAT(++self->nodes);
105                         switch (self->v_table->type) {
106                         case AO2_CONTAINER_RTTI_HASH:
107                                 hash_ao2_link_node_stat(self, node);
108                                 break;
109                         case AO2_CONTAINER_RTTI_RBTREE:
110                                 break;
111                         }
112 #endif  /* defined(AST_DEVMODE) */
113
114                         res = 1;
115                         break;
116                 case AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED:
117                         res = 1;
118                         /* Fall through */
119                 case AO2_CONTAINER_INSERT_NODE_REJECTED:
120                         __ao2_ref(node, -1);
121                         break;
122                 }
123 #if defined(AO2_DEBUG) && defined(AST_DEVMODE)
124                 if (res) {
125                         switch (self->v_table->type) {
126                         case AO2_CONTAINER_RTTI_HASH:
127                                 if (!self->sort_fn) {
128                                         /*
129                                          * XXX chan_iax2 plays games with the hash function so we cannot
130                                          * routinely do an integrity check on this type of container.
131                                          * chan_iax2 should be changed to not abuse the hash function.
132                                          */
133                                         break;
134                                 }
135                                 /* Fall through. */
136                         case AO2_CONTAINER_RTTI_RBTREE:
137                                 if (ao2_container_check(self, OBJ_NOLOCK)) {
138                                         ast_log(LOG_ERROR, "Container integrity failed after insert.\n");
139                                 }
140                                 break;
141                         }
142                 }
143 #endif  /* defined(AO2_DEBUG) && defined(AST_DEVMODE) */
144         }
145
146         if (flags & OBJ_NOLOCK) {
147                 __adjust_lock(self, orig_lock, 0);
148         } else {
149                 ao2_unlock(self);
150         }
151
152         return res;
153 }
154
155 int __ao2_link_debug(struct ao2_container *c, void *obj_new, int flags, const char *tag, const char *file, int line, const char *func)
156 {
157         return internal_ao2_link(c, obj_new, flags, tag, file, line, func);
158 }
159
160 int __ao2_link(struct ao2_container *c, void *obj_new, int flags)
161 {
162         return internal_ao2_link(c, obj_new, flags, NULL, __FILE__, __LINE__, __PRETTY_FUNCTION__);
163 }
164
165 /*!
166  * \brief another convenience function is a callback that matches on address
167  */
168 int ao2_match_by_addr(void *user_data, void *arg, int flags)
169 {
170         return (user_data == arg) ? (CMP_MATCH | CMP_STOP) : 0;
171 }
172
173 /*
174  * Unlink an object from the container
175  * and destroy the associated * bucket_entry structure.
176  */
177 void *__ao2_unlink_debug(struct ao2_container *c, void *user_data, int flags,
178         const char *tag, const char *file, int line, const char *func)
179 {
180         if (!is_ao2_object(user_data)) {
181                 /* Sanity checks. */
182                 ast_assert(0);
183                 return NULL;
184         }
185
186         flags &= ~OBJ_SEARCH_MASK;
187         flags |= (OBJ_UNLINK | OBJ_SEARCH_OBJECT | OBJ_NODATA);
188         __ao2_callback_debug(c, flags, ao2_match_by_addr, user_data, tag, file, line, func);
189
190         return NULL;
191 }
192
193 void *__ao2_unlink(struct ao2_container *c, void *user_data, int flags)
194 {
195         if (!is_ao2_object(user_data)) {
196                 /* Sanity checks. */
197                 ast_assert(0);
198                 return NULL;
199         }
200
201         flags &= ~OBJ_SEARCH_MASK;
202         flags |= (OBJ_UNLINK | OBJ_SEARCH_OBJECT | OBJ_NODATA);
203         __ao2_callback(c, flags, ao2_match_by_addr, user_data);
204
205         return NULL;
206 }
207
208 /*!
209  * \brief special callback that matches all
210  */
211 static int cb_true(void *user_data, void *arg, int flags)
212 {
213         return CMP_MATCH;
214 }
215
216 /*!
217  * \brief similar to cb_true, but is an ao2_callback_data_fn instead
218  */
219 static int cb_true_data(void *user_data, void *arg, void *data, int flags)
220 {
221         return CMP_MATCH;
222 }
223
224 /*!
225  * \internal
226  * \brief Traverse the container.  (internal)
227  *
228  * \param self Container to operate upon.
229  * \param flags search_flags to control traversing the container
230  * \param cb_fn Comparison callback function.
231  * \param arg Comparison callback arg parameter.
232  * \param data Data comparison callback data parameter.
233  * \param type Type of comparison callback cb_fn.
234  * \param tag used for debugging.
235  * \param file Debug file name invoked from
236  * \param line Debug line invoked from
237  * \param func Debug function name invoked from
238  *
239  * \retval NULL on failure or no matching object found.
240  *
241  * \retval object found if OBJ_MULTIPLE is not set in the flags
242  * parameter.
243  *
244  * \retval ao2_iterator pointer if OBJ_MULTIPLE is set in the
245  * flags parameter.  The iterator must be destroyed with
246  * ao2_iterator_destroy() when the caller no longer needs it.
247  */
248 static void *internal_ao2_traverse(struct ao2_container *self, enum search_flags flags,
249         void *cb_fn, void *arg, void *data, enum ao2_callback_type type,
250         const char *tag, const char *file, int line, const char *func)
251 {
252         void *ret;
253         ao2_callback_fn *cb_default = NULL;
254         ao2_callback_data_fn *cb_withdata = NULL;
255         struct ao2_container_node *node;
256         void *traversal_state;
257
258         enum ao2_lock_req orig_lock;
259         struct ao2_container *multi_container = NULL;
260         struct ao2_iterator *multi_iterator = NULL;
261
262         if (!is_ao2_object(self) || !self->v_table || !self->v_table->traverse_first
263                 || !self->v_table->traverse_next) {
264                 /* Sanity checks. */
265                 ast_assert(0);
266                 return NULL;
267         }
268
269         /*
270          * This logic is used so we can support OBJ_MULTIPLE with OBJ_NODATA
271          * turned off.  This if statement checks for the special condition
272          * where multiple items may need to be returned.
273          */
274         if ((flags & (OBJ_MULTIPLE | OBJ_NODATA)) == OBJ_MULTIPLE) {
275                 /* we need to return an ao2_iterator with the results,
276                  * as there could be more than one. the iterator will
277                  * hold the only reference to a container that has all the
278                  * matching objects linked into it, so when the iterator
279                  * is destroyed, the container will be automatically
280                  * destroyed as well.
281                  */
282                 multi_container = ao2_t_container_alloc_list(AO2_ALLOC_OPT_LOCK_NOLOCK, 0, NULL,
283                         NULL, "OBJ_MULTIPLE return container creation");
284                 if (!multi_container) {
285                         return NULL;
286                 }
287                 if (!(multi_iterator = ast_calloc(1, sizeof(*multi_iterator)))) {
288                         ao2_t_ref(multi_container, -1, "OBJ_MULTIPLE interator creation failed.");
289                         return NULL;
290                 }
291         }
292
293         if (!cb_fn) {
294                 /* Match everything if no callback match function provided. */
295                 if (type == AO2_CALLBACK_WITH_DATA) {
296                         cb_withdata = cb_true_data;
297                 } else {
298                         cb_default = cb_true;
299                 }
300         } else {
301                 /*
302                  * We do this here to avoid the per object casting penalty (even
303                  * though that is probably optimized away anyway).
304                  */
305                 if (type == AO2_CALLBACK_WITH_DATA) {
306                         cb_withdata = cb_fn;
307                 } else {
308                         cb_default = cb_fn;
309                 }
310         }
311
312         /* avoid modifications to the content */
313         if (flags & OBJ_NOLOCK) {
314                 if (flags & OBJ_UNLINK) {
315                         orig_lock = __adjust_lock(self, AO2_LOCK_REQ_WRLOCK, 1);
316                 } else {
317                         orig_lock = __adjust_lock(self, AO2_LOCK_REQ_RDLOCK, 1);
318                 }
319         } else {
320                 orig_lock = AO2_LOCK_REQ_MUTEX;
321                 if (flags & OBJ_UNLINK) {
322                         ao2_wrlock(self);
323                 } else {
324                         ao2_rdlock(self);
325                 }
326         }
327
328         /* Create a buffer for the traversal state. */
329         traversal_state = alloca(AO2_TRAVERSAL_STATE_SIZE);
330
331         ret = NULL;
332         for (node = self->v_table->traverse_first(self, flags, arg, traversal_state);
333                 node;
334                 node = self->v_table->traverse_next(self, traversal_state, node)) {
335                 int match;
336
337                 /* Visit the current node. */
338                 match = (CMP_MATCH | CMP_STOP);
339                 if (type == AO2_CALLBACK_WITH_DATA) {
340                         match &= cb_withdata(node->obj, arg, data, flags);
341                 } else {
342                         match &= cb_default(node->obj, arg, flags);
343                 }
344                 if (match == 0) {
345                         /* no match, no stop, continue */
346                         continue;
347                 }
348                 if (match == CMP_STOP) {
349                         /* no match but stop, we are done */
350                         break;
351                 }
352
353                 /*
354                  * CMP_MATCH is set here
355                  *
356                  * we found the object, performing operations according to flags
357                  */
358                 if (node->obj) {
359                         /* The object is still in the container. */
360                         if (!(flags & OBJ_NODATA)) {
361                                 /*
362                                  * We are returning the object, record the value.  It is
363                                  * important to handle this case before the unlink.
364                                  */
365                                 if (multi_container) {
366                                         /*
367                                          * Link the object into the container that will hold the
368                                          * results.
369                                          */
370                                         if (tag) {
371                                                 __ao2_link_debug(multi_container, node->obj, flags,
372                                                         tag, file, line, func);
373                                         } else {
374                                                 __ao2_link(multi_container, node->obj, flags);
375                                         }
376                                 } else {
377                                         ret = node->obj;
378                                         /* Returning a single object. */
379                                         if (!(flags & OBJ_UNLINK)) {
380                                                 /*
381                                                  * Bump the ref count since we are not going to unlink and
382                                                  * transfer the container's object ref to the returned object.
383                                                  */
384                                                 if (tag) {
385                                                         __ao2_ref_debug(ret, 1, tag, file, line, func);
386                                                 } else {
387                                                         ao2_t_ref(ret, 1, "Traversal found object");
388                                                 }
389                                         }
390                                 }
391                         }
392
393                         if (flags & OBJ_UNLINK) {
394                                 /* update number of elements */
395                                 ast_atomic_fetchadd_int(&self->elements, -1);
396 #if defined(AST_DEVMODE)
397                                 {
398                                         int empty = self->nodes - self->elements;
399
400                                         if (self->max_empty_nodes < empty) {
401                                                 self->max_empty_nodes = empty;
402                                         }
403                                 }
404                                 switch (self->v_table->type) {
405                                 case AO2_CONTAINER_RTTI_HASH:
406                                         hash_ao2_unlink_node_stat(self, node);
407                                         break;
408                                 case AO2_CONTAINER_RTTI_RBTREE:
409                                         break;
410                                 }
411 #endif  /* defined(AST_DEVMODE) */
412
413                                 /*
414                                  * - When unlinking and not returning the result, OBJ_NODATA is
415                                  * set, the ref from the container must be decremented.
416                                  *
417                                  * - When unlinking with a multi_container the ref from the
418                                  * original container must be decremented.  This is because the
419                                  * result is returned in a new container that already holds its
420                                  * own ref for the object.
421                                  *
422                                  * If the ref from the original container is not accounted for
423                                  * here a memory leak occurs.
424                                  */
425                                 if (multi_container || (flags & OBJ_NODATA)) {
426                                         if (tag) {
427                                                 __ao2_ref_debug(node->obj, -1, tag, file, line, func);
428                                         } else {
429                                                 ao2_t_ref(node->obj, -1, "Unlink container obj reference.");
430                                         }
431                                 }
432                                 node->obj = NULL;
433
434                                 /* Unref the node from the container. */
435                                 __ao2_ref(node, -1);
436                         }
437                 }
438
439                 if ((match & CMP_STOP) || !(flags & OBJ_MULTIPLE)) {
440                         /* We found our only (or last) match, so we are done */
441                         break;
442                 }
443         }
444         if (self->v_table->traverse_cleanup) {
445                 self->v_table->traverse_cleanup(traversal_state);
446         }
447         if (node) {
448                 /* Unref the node from self->v_table->traverse_first/traverse_next() */
449                 __ao2_ref(node, -1);
450         }
451
452         if (flags & OBJ_NOLOCK) {
453                 __adjust_lock(self, orig_lock, 0);
454         } else {
455                 ao2_unlock(self);
456         }
457
458         /* if multi_container was created, we are returning multiple objects */
459         if (multi_container) {
460                 *multi_iterator = ao2_iterator_init(multi_container,
461                         AO2_ITERATOR_UNLINK | AO2_ITERATOR_MALLOCD);
462                 ao2_t_ref(multi_container, -1,
463                         "OBJ_MULTIPLE for multiple objects traversal complete.");
464                 return multi_iterator;
465         } else {
466                 return ret;
467         }
468 }
469
470 void *__ao2_callback_debug(struct ao2_container *c, enum search_flags flags,
471         ao2_callback_fn *cb_fn, void *arg, const char *tag, const char *file, int line,
472         const char *func)
473 {
474         return internal_ao2_traverse(c, flags, cb_fn, arg, NULL, AO2_CALLBACK_DEFAULT, tag, file, line, func);
475 }
476
477 void *__ao2_callback(struct ao2_container *c, enum search_flags flags,
478         ao2_callback_fn *cb_fn, void *arg)
479 {
480         return internal_ao2_traverse(c, flags, cb_fn, arg, NULL, AO2_CALLBACK_DEFAULT, NULL, NULL, 0, NULL);
481 }
482
483 void *__ao2_callback_data_debug(struct ao2_container *c, enum search_flags flags,
484         ao2_callback_data_fn *cb_fn, void *arg, void *data, const char *tag, const char *file,
485         int line, const char *func)
486 {
487         return internal_ao2_traverse(c, flags, cb_fn, arg, data, AO2_CALLBACK_WITH_DATA, tag, file, line, func);
488 }
489
490 void *__ao2_callback_data(struct ao2_container *c, enum search_flags flags,
491         ao2_callback_data_fn *cb_fn, void *arg, void *data)
492 {
493         return internal_ao2_traverse(c, flags, cb_fn, arg, data, AO2_CALLBACK_WITH_DATA, NULL, NULL, 0, NULL);
494 }
495
496 /*!
497  * the find function just invokes the default callback with some reasonable flags.
498  */
499 void *__ao2_find_debug(struct ao2_container *c, const void *arg, enum search_flags flags,
500         const char *tag, const char *file, int line, const char *func)
501 {
502         void *arged = (void *) arg;/* Done to avoid compiler const warning */
503
504         if (!c) {
505                 /* Sanity checks. */
506                 ast_assert(0);
507                 return NULL;
508         }
509         return __ao2_callback_debug(c, flags, c->cmp_fn, arged, tag, file, line, func);
510 }
511
512 void *__ao2_find(struct ao2_container *c, const void *arg, enum search_flags flags)
513 {
514         void *arged = (void *) arg;/* Done to avoid compiler const warning */
515
516         if (!c) {
517                 /* Sanity checks. */
518                 ast_assert(0);
519                 return NULL;
520         }
521         return __ao2_callback(c, flags, c->cmp_fn, arged);
522 }
523
524 /*!
525  * initialize an iterator so we start from the first object
526  */
527 struct ao2_iterator ao2_iterator_init(struct ao2_container *c, int flags)
528 {
529         struct ao2_iterator a = {
530                 .c = c,
531                 .flags = flags
532         };
533
534         ao2_t_ref(c, +1, "Init iterator with container.");
535
536         return a;
537 }
538
539 void ao2_iterator_restart(struct ao2_iterator *iter)
540 {
541         /* Release the last container node reference if we have one. */
542         if (iter->last_node) {
543                 enum ao2_lock_req orig_lock;
544
545                 /*
546                  * Do a read lock in case the container node unref does not
547                  * destroy the node.  If the container node is destroyed then
548                  * the lock will be upgraded to a write lock.
549                  */
550                 if (iter->flags & AO2_ITERATOR_DONTLOCK) {
551                         orig_lock = __adjust_lock(iter->c, AO2_LOCK_REQ_RDLOCK, 1);
552                 } else {
553                         orig_lock = AO2_LOCK_REQ_MUTEX;
554                         ao2_rdlock(iter->c);
555                 }
556
557                 __ao2_ref(iter->last_node, -1);
558                 iter->last_node = NULL;
559
560                 if (iter->flags & AO2_ITERATOR_DONTLOCK) {
561                         __adjust_lock(iter->c, orig_lock, 0);
562                 } else {
563                         ao2_unlock(iter->c);
564                 }
565         }
566
567         /* The iteration is no longer complete. */
568         iter->complete = 0;
569 }
570
571 void ao2_iterator_destroy(struct ao2_iterator *iter)
572 {
573         /* Release any last container node reference. */
574         ao2_iterator_restart(iter);
575
576         /* Release the iterated container reference. */
577         ao2_t_ref(iter->c, -1, "Unref iterator in ao2_iterator_destroy");
578         iter->c = NULL;
579
580         /* Free the malloced iterator. */
581         if (iter->flags & AO2_ITERATOR_MALLOCD) {
582                 ast_free(iter);
583         }
584 }
585
586 void ao2_iterator_cleanup(struct ao2_iterator *iter)
587 {
588         if (iter) {
589                 ao2_iterator_destroy(iter);
590         }
591 }
592
593 /*
594  * move to the next element in the container.
595  */
596 static void *internal_ao2_iterator_next(struct ao2_iterator *iter, const char *tag, const char *file, int line, const char *func)
597 {
598         enum ao2_lock_req orig_lock;
599         struct ao2_container_node *node;
600         void *ret;
601
602         if (!is_ao2_object(iter->c) || !iter->c->v_table || !iter->c->v_table->iterator_next) {
603                 /* Sanity checks. */
604                 ast_assert(0);
605                 return NULL;
606         }
607
608         if (iter->complete) {
609                 /* Don't return any more objects. */
610                 return NULL;
611         }
612
613         if (iter->flags & AO2_ITERATOR_DONTLOCK) {
614                 if (iter->flags & AO2_ITERATOR_UNLINK) {
615                         orig_lock = __adjust_lock(iter->c, AO2_LOCK_REQ_WRLOCK, 1);
616                 } else {
617                         orig_lock = __adjust_lock(iter->c, AO2_LOCK_REQ_RDLOCK, 1);
618                 }
619         } else {
620                 orig_lock = AO2_LOCK_REQ_MUTEX;
621                 if (iter->flags & AO2_ITERATOR_UNLINK) {
622                         ao2_wrlock(iter->c);
623                 } else {
624                         ao2_rdlock(iter->c);
625                 }
626         }
627
628         node = iter->c->v_table->iterator_next(iter->c, iter->last_node, iter->flags);
629         if (node) {
630                 ret = node->obj;
631
632                 if (iter->flags & AO2_ITERATOR_UNLINK) {
633                         /* update number of elements */
634                         ast_atomic_fetchadd_int(&iter->c->elements, -1);
635 #if defined(AST_DEVMODE)
636                         {
637                                 int empty = iter->c->nodes - iter->c->elements;
638
639                                 if (iter->c->max_empty_nodes < empty) {
640                                         iter->c->max_empty_nodes = empty;
641                                 }
642                         }
643                         switch (iter->c->v_table->type) {
644                         case AO2_CONTAINER_RTTI_HASH:
645                                 hash_ao2_unlink_node_stat(iter->c, node);
646                                 break;
647                         case AO2_CONTAINER_RTTI_RBTREE:
648                                 break;
649                         }
650 #endif  /* defined(AST_DEVMODE) */
651
652                         /* Transfer the object ref from the container to the returned object. */
653                         node->obj = NULL;
654
655                         /* Transfer the container's node ref to the iterator. */
656                 } else {
657                         /* Bump ref of returned object */
658                         if (tag) {
659                                 __ao2_ref_debug(ret, +1, tag, file, line, func);
660                         } else {
661                                 ao2_t_ref(ret, +1, "Next iterator object.");
662                         }
663
664                         /* Bump the container's node ref for the iterator. */
665                         __ao2_ref(node, +1);
666                 }
667         } else {
668                 /* The iteration has completed. */
669                 iter->complete = 1;
670                 ret = NULL;
671         }
672
673         /* Replace the iterator's node */
674         if (iter->last_node) {
675                 __ao2_ref(iter->last_node, -1);
676         }
677         iter->last_node = node;
678
679         if (iter->flags & AO2_ITERATOR_DONTLOCK) {
680                 __adjust_lock(iter->c, orig_lock, 0);
681         } else {
682                 ao2_unlock(iter->c);
683         }
684
685         return ret;
686 }
687
688 void *__ao2_iterator_next_debug(struct ao2_iterator *iter, const char *tag, const char *file, int line, const char *func)
689 {
690         return internal_ao2_iterator_next(iter, tag, file, line, func);
691 }
692
693 void *__ao2_iterator_next(struct ao2_iterator *iter)
694 {
695         return internal_ao2_iterator_next(iter, NULL, __FILE__, __LINE__, __PRETTY_FUNCTION__);
696 }
697
698 int ao2_iterator_count(struct ao2_iterator *iter)
699 {
700         return ao2_container_count(iter->c);
701 }
702
703 void container_destruct(void *_c)
704 {
705         struct ao2_container *c = _c;
706
707         /* Unlink any stored objects in the container. */
708         c->destroying = 1;
709         __ao2_callback(c, OBJ_UNLINK | OBJ_NODATA | OBJ_MULTIPLE, NULL, NULL);
710
711         /* Perform any extra container cleanup. */
712         if (c->v_table && c->v_table->destroy) {
713                 c->v_table->destroy(c);
714         }
715
716 #ifdef AO2_DEBUG
717         ast_atomic_fetchadd_int(&ao2.total_containers, -1);
718 #endif
719 }
720
721 void container_destruct_debug(void *_c)
722 {
723         struct ao2_container *c = _c;
724
725         /* Unlink any stored objects in the container. */
726         c->destroying = 1;
727         __ao2_callback_debug(c, OBJ_UNLINK | OBJ_NODATA | OBJ_MULTIPLE, NULL, NULL,
728                 "container_destruct_debug called", __FILE__, __LINE__, __PRETTY_FUNCTION__);
729
730         /* Perform any extra container cleanup. */
731         if (c->v_table && c->v_table->destroy) {
732                 c->v_table->destroy(c);
733         }
734
735 #ifdef AO2_DEBUG
736         ast_atomic_fetchadd_int(&ao2.total_containers, -1);
737 #endif
738 }
739
740 /*!
741  * \internal
742  * \brief Put obj into the arg container.
743  * \since 11.0
744  *
745  * \param obj  pointer to the (user-defined part) of an object.
746  * \param arg callback argument from ao2_callback()
747  * \param flags flags from ao2_callback()
748  *
749  * \retval 0 on success.
750  * \retval CMP_STOP|CMP_MATCH on error.
751  */
752 static int dup_obj_cb(void *obj, void *arg, int flags)
753 {
754         struct ao2_container *dest = arg;
755
756         return __ao2_link(dest, obj, OBJ_NOLOCK) ? 0 : (CMP_MATCH | CMP_STOP);
757 }
758
759 int ao2_container_dup(struct ao2_container *dest, struct ao2_container *src, enum search_flags flags)
760 {
761         void *obj;
762         int res = 0;
763
764         if (!(flags & OBJ_NOLOCK)) {
765                 ao2_rdlock(src);
766                 ao2_wrlock(dest);
767         }
768         obj = __ao2_callback(src, OBJ_NOLOCK, dup_obj_cb, dest);
769         if (obj) {
770                 /* Failed to put this obj into the dest container. */
771                 ao2_t_ref(obj, -1, "Failed to put this object into the dest container.");
772
773                 /* Remove all items from the dest container. */
774                 __ao2_callback(dest, OBJ_NOLOCK | OBJ_UNLINK | OBJ_NODATA | OBJ_MULTIPLE, NULL,
775                         NULL);
776                 res = -1;
777         }
778         if (!(flags & OBJ_NOLOCK)) {
779                 ao2_unlock(dest);
780                 ao2_unlock(src);
781         }
782
783         return res;
784 }
785
786 struct ao2_container *__ao2_container_clone(struct ao2_container *orig, enum search_flags flags)
787 {
788         struct ao2_container *clone;
789         int failed;
790
791         /* Create the clone container with the same properties as the original. */
792         if (!is_ao2_object(orig) || !orig->v_table || !orig->v_table->alloc_empty_clone) {
793                 /* Sanity checks. */
794                 ast_assert(0);
795                 return NULL;
796         }
797         clone = orig->v_table->alloc_empty_clone(orig);
798         if (!clone) {
799                 return NULL;
800         }
801
802         if (flags & OBJ_NOLOCK) {
803                 ao2_wrlock(clone);
804         }
805         failed = ao2_container_dup(clone, orig, flags);
806         if (flags & OBJ_NOLOCK) {
807                 ao2_unlock(clone);
808         }
809         if (failed) {
810                 /* Object copy into the clone container failed. */
811                 ao2_t_ref(clone, -1, "Clone creation failed.");
812                 clone = NULL;
813         }
814         return clone;
815 }
816
817 struct ao2_container *__ao2_container_clone_debug(struct ao2_container *orig, enum search_flags flags, const char *tag, const char *file, int line, const char *func, int ref_debug)
818 {
819         struct ao2_container *clone;
820         int failed;
821
822         /* Create the clone container with the same properties as the original. */
823         if (!is_ao2_object(orig) || !orig->v_table || !orig->v_table->alloc_empty_clone_debug) {
824                 /* Sanity checks. */
825                 ast_assert(0);
826                 return NULL;
827         }
828         clone = orig->v_table->alloc_empty_clone_debug(orig, tag, file, line, func, ref_debug);
829         if (!clone) {
830                 return NULL;
831         }
832
833         if (flags & OBJ_NOLOCK) {
834                 ao2_wrlock(clone);
835         }
836         failed = ao2_container_dup(clone, orig, flags);
837         if (flags & OBJ_NOLOCK) {
838                 ao2_unlock(clone);
839         }
840         if (failed) {
841                 /* Object copy into the clone container failed. */
842                 if (ref_debug) {
843                         __ao2_ref_debug(clone, -1, tag, file, line, func);
844                 } else {
845                         ao2_t_ref(clone, -1, "Clone creation failed.");
846                 }
847                 clone = NULL;
848         }
849         return clone;
850 }
851
852 void ao2_container_dump(struct ao2_container *self, enum search_flags flags, const char *name, void *where, ao2_prnt_fn *prnt, ao2_prnt_obj_fn *prnt_obj)
853 {
854         if (!is_ao2_object(self) || !self->v_table) {
855                 prnt(where, "Invalid container\n");
856                 ast_assert(0);
857                 return;
858         }
859
860         if (!(flags & OBJ_NOLOCK)) {
861                 ao2_rdlock(self);
862         }
863         if (name) {
864                 prnt(where, "Container name: %s\n", name);
865         }
866 #if defined(AST_DEVMODE)
867         if (self->v_table->dump) {
868                 self->v_table->dump(self, where, prnt, prnt_obj);
869         } else
870 #endif  /* defined(AST_DEVMODE) */
871         {
872                 prnt(where, "Container dump not available.\n");
873         }
874         if (!(flags & OBJ_NOLOCK)) {
875                 ao2_unlock(self);
876         }
877 }
878
879 void ao2_container_stats(struct ao2_container *self, enum search_flags flags, const char *name, void *where, ao2_prnt_fn *prnt)
880 {
881         if (!is_ao2_object(self) || !self->v_table) {
882                 prnt(where, "Invalid container\n");
883                 ast_assert(0);
884                 return;
885         }
886
887         if (!(flags & OBJ_NOLOCK)) {
888                 ao2_rdlock(self);
889         }
890         if (name) {
891                 prnt(where, "Container name: %s\n", name);
892         }
893         prnt(where, "Number of objects: %d\n", self->elements);
894 #if defined(AST_DEVMODE)
895         prnt(where, "Number of nodes: %d\n", self->nodes);
896         prnt(where, "Number of empty nodes: %d\n", self->nodes - self->elements);
897         /*
898          * XXX
899          * If the max_empty_nodes count gets out of single digits you
900          * likely have a code path where ao2_iterator_destroy() is not
901          * called.
902          *
903          * Empty nodes do not harm the container but they do make
904          * container operations less efficient.
905          */
906         prnt(where, "Maximum empty nodes: %d\n", self->max_empty_nodes);
907         if (self->v_table->stats) {
908                 self->v_table->stats(self, where, prnt);
909         }
910 #endif  /* defined(AST_DEVMODE) */
911         if (!(flags & OBJ_NOLOCK)) {
912                 ao2_unlock(self);
913         }
914 }
915
916 int ao2_container_check(struct ao2_container *self, enum search_flags flags)
917 {
918         int res = 0;
919
920         if (!is_ao2_object(self) || !self->v_table) {
921                 /* Sanity checks. */
922                 ast_assert(0);
923                 return -1;
924         }
925 #if defined(AST_DEVMODE)
926         if (!self->v_table->integrity) {
927                 /* No ingetrigy check available.  Assume container is ok. */
928                 return 0;
929         }
930
931         if (!(flags & OBJ_NOLOCK)) {
932                 ao2_rdlock(self);
933         }
934         res = self->v_table->integrity(self);
935         if (!(flags & OBJ_NOLOCK)) {
936                 ao2_unlock(self);
937         }
938 #endif  /* defined(AST_DEVMODE) */
939         return res;
940 }
941
942 #if defined(AST_DEVMODE)
943 static struct ao2_container *reg_containers;
944
945 struct ao2_reg_container {
946         /*! Registered container pointer. */
947         struct ao2_container *registered;
948         /*! Callback function to print the given object's key. (NULL if not available) */
949         ao2_prnt_obj_fn *prnt_obj;
950         /*! Name container registered under. */
951         char name[1];
952 };
953
954 struct ao2_reg_partial_key {
955         /*! Length of partial key match. */
956         int len;
957         /*! Registration partial key name. */
958         const char *name;
959 };
960
961 struct ao2_reg_match {
962         /*! The nth match to find. */
963         int find_nth;
964         /*! Count of the matches already found. */
965         int count;
966 };
967 #endif  /* defined(AST_DEVMODE) */
968
969 #if defined(AST_DEVMODE)
970 static int ao2_reg_sort_cb(const void *obj_left, const void *obj_right, int flags)
971 {
972         const struct ao2_reg_container *reg_left = obj_left;
973         int cmp;
974
975         switch (flags & OBJ_SEARCH_MASK) {
976         case OBJ_SEARCH_OBJECT:
977                 {
978                         const struct ao2_reg_container *reg_right = obj_right;
979
980                         cmp = strcasecmp(reg_left->name, reg_right->name);
981                 }
982                 break;
983         case OBJ_SEARCH_KEY:
984                 {
985                         const char *name = obj_right;
986
987                         cmp = strcasecmp(reg_left->name, name);
988                 }
989                 break;
990         case OBJ_SEARCH_PARTIAL_KEY:
991                 {
992                         const struct ao2_reg_partial_key *partial_key = obj_right;
993
994                         cmp = strncasecmp(reg_left->name, partial_key->name, partial_key->len);
995                 }
996                 break;
997         default:
998                 /* Sort can only work on something with a full or partial key. */
999                 ast_assert(0);
1000                 cmp = 0;
1001                 break;
1002         }
1003         return cmp;
1004 }
1005 #endif  /* defined(AST_DEVMODE) */
1006
1007 #if defined(AST_DEVMODE)
1008 static void ao2_reg_destructor(void *v_doomed)
1009 {
1010         struct ao2_reg_container *doomed = v_doomed;
1011
1012         if (doomed->registered) {
1013                 ao2_t_ref(doomed->registered, -1, "Releasing registered container.");
1014         }
1015 }
1016 #endif  /* defined(AST_DEVMODE) */
1017
1018 int ao2_container_register(const char *name, struct ao2_container *self, ao2_prnt_obj_fn *prnt_obj)
1019 {
1020         int res = 0;
1021 #if defined(AST_DEVMODE)
1022         struct ao2_reg_container *reg;
1023
1024         reg = ao2_t_alloc_options(sizeof(*reg) + strlen(name), ao2_reg_destructor,
1025                 AO2_ALLOC_OPT_LOCK_NOLOCK, "Container registration object.");
1026         if (!reg) {
1027                 return -1;
1028         }
1029
1030         /* Fill in registered entry */
1031         ao2_t_ref(self, +1, "Registering container.");
1032         reg->registered = self;
1033         reg->prnt_obj = prnt_obj;
1034         strcpy(reg->name, name);/* safe */
1035
1036         if (!ao2_t_link(reg_containers, reg, "Save registration object.")) {
1037                 res = -1;
1038         }
1039
1040         ao2_t_ref(reg, -1, "Done registering container.");
1041 #endif  /* defined(AST_DEVMODE) */
1042         return res;
1043 }
1044
1045 void ao2_container_unregister(const char *name)
1046 {
1047 #if defined(AST_DEVMODE)
1048         ao2_t_find(reg_containers, name, OBJ_UNLINK | OBJ_NODATA | OBJ_SEARCH_KEY,
1049                 "Unregister container");
1050 #endif  /* defined(AST_DEVMODE) */
1051 }
1052
1053 #if defined(AST_DEVMODE)
1054 static int ao2_complete_reg_cb(void *obj, void *arg, void *data, int flags)
1055 {
1056         struct ao2_reg_match *which = data;
1057
1058         /* ao2_reg_sort_cb() has already filtered the search to matching keys */
1059         return (which->find_nth < ++which->count) ? (CMP_MATCH | CMP_STOP) : 0;
1060 }
1061 #endif  /* defined(AST_DEVMODE) */
1062
1063 #if defined(AST_DEVMODE)
1064 static char *complete_container_names(struct ast_cli_args *a)
1065 {
1066         struct ao2_reg_partial_key partial_key;
1067         struct ao2_reg_match which;
1068         struct ao2_reg_container *reg;
1069         char *name;
1070
1071         if (a->pos != 3) {
1072                 return NULL;
1073         }
1074
1075         partial_key.len = strlen(a->word);
1076         partial_key.name = a->word;
1077         which.find_nth = a->n;
1078         which.count = 0;
1079         reg = ao2_t_callback_data(reg_containers, partial_key.len ? OBJ_SEARCH_PARTIAL_KEY : 0,
1080                 ao2_complete_reg_cb, &partial_key, &which, "Find partial registered container");
1081         if (reg) {
1082                 name = ast_strdup(reg->name);
1083                 ao2_t_ref(reg, -1, "Done with registered container object.");
1084         } else {
1085                 name = NULL;
1086         }
1087         return name;
1088 }
1089 #endif  /* defined(AST_DEVMODE) */
1090
1091 #if defined(AST_DEVMODE)
1092 AST_THREADSTORAGE(ao2_out_buf);
1093
1094 /*!
1095  * \brief Print CLI output.
1096  * \since 12.0.0
1097  *
1098  * \param where User data pointer needed to determine where to put output.
1099  * \param fmt printf type format string.
1100  *
1101  * \return Nothing
1102  */
1103 static void cli_output(void *where, const char *fmt, ...) __attribute__((format(printf, 2, 3)));
1104 static void cli_output(void *where, const char *fmt, ...)
1105 {
1106         int res;
1107         struct ast_str *buf;
1108         va_list ap;
1109
1110         buf = ast_str_thread_get(&ao2_out_buf, 256);
1111         if (!buf) {
1112                 return;
1113         }
1114
1115         va_start(ap, fmt);
1116         res = ast_str_set_va(&buf, 0, fmt, ap);
1117         va_end(ap);
1118
1119         if (res != AST_DYNSTR_BUILD_FAILED) {
1120                 ast_cli(*(int *) where, "%s", ast_str_buffer(buf));
1121         }
1122 }
1123 #endif  /* defined(AST_DEVMODE) */
1124
1125 #if defined(AST_DEVMODE)
1126 /*! \brief Show container contents - CLI command */
1127 static char *handle_cli_astobj2_container_dump(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
1128 {
1129         const char *name;
1130         struct ao2_reg_container *reg;
1131
1132         switch (cmd) {
1133         case CLI_INIT:
1134                 e->command = "astobj2 container dump";
1135                 e->usage =
1136                         "Usage: astobj2 container dump <name>\n"
1137                         "       Show contents of the container <name>.\n";
1138                 return NULL;
1139         case CLI_GENERATE:
1140                 return complete_container_names(a);
1141         }
1142
1143         if (a->argc != 4) {
1144                 return CLI_SHOWUSAGE;
1145         }
1146
1147         name = a->argv[3];
1148         reg = ao2_t_find(reg_containers, name, OBJ_SEARCH_KEY, "Find registered container");
1149         if (reg) {
1150                 ao2_container_dump(reg->registered, 0, name, (void *) &a->fd, cli_output,
1151                         reg->prnt_obj);
1152                 ao2_t_ref(reg, -1, "Done with registered container object.");
1153         } else {
1154                 ast_cli(a->fd, "Container '%s' not found.\n", name);
1155         }
1156
1157         return CLI_SUCCESS;
1158 }
1159 #endif  /* defined(AST_DEVMODE) */
1160
1161 #if defined(AST_DEVMODE)
1162 /*! \brief Show container statistics - CLI command */
1163 static char *handle_cli_astobj2_container_stats(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
1164 {
1165         const char *name;
1166         struct ao2_reg_container *reg;
1167
1168         switch (cmd) {
1169         case CLI_INIT:
1170                 e->command = "astobj2 container stats";
1171                 e->usage =
1172                         "Usage: astobj2 container stats <name>\n"
1173                         "       Show statistics about the specified container <name>.\n";
1174                 return NULL;
1175         case CLI_GENERATE:
1176                 return complete_container_names(a);
1177         }
1178
1179         if (a->argc != 4) {
1180                 return CLI_SHOWUSAGE;
1181         }
1182
1183         name = a->argv[3];
1184         reg = ao2_t_find(reg_containers, name, OBJ_SEARCH_KEY, "Find registered container");
1185         if (reg) {
1186                 ao2_container_stats(reg->registered, 0, name, (void *) &a->fd, cli_output);
1187                 ao2_t_ref(reg, -1, "Done with registered container object.");
1188         } else {
1189                 ast_cli(a->fd, "Container '%s' not found.\n", name);
1190         }
1191
1192         return CLI_SUCCESS;
1193 }
1194 #endif  /* defined(AST_DEVMODE) */
1195
1196 #if defined(AST_DEVMODE)
1197 /*! \brief Show container check results - CLI command */
1198 static char *handle_cli_astobj2_container_check(struct ast_cli_entry *e, int cmd, struct ast_cli_args *a)
1199 {
1200         const char *name;
1201         struct ao2_reg_container *reg;
1202
1203         switch (cmd) {
1204         case CLI_INIT:
1205                 e->command = "astobj2 container check";
1206                 e->usage =
1207                         "Usage: astobj2 container check <name>\n"
1208                         "       Perform a container integrity check on <name>.\n";
1209                 return NULL;
1210         case CLI_GENERATE:
1211                 return complete_container_names(a);
1212         }
1213
1214         if (a->argc != 4) {
1215                 return CLI_SHOWUSAGE;
1216         }
1217
1218         name = a->argv[3];
1219         reg = ao2_t_find(reg_containers, name, OBJ_SEARCH_KEY, "Find registered container");
1220         if (reg) {
1221                 ast_cli(a->fd, "Container check of '%s': %s.\n", name,
1222                         ao2_container_check(reg->registered, 0) ? "failed" : "OK");
1223                 ao2_t_ref(reg, -1, "Done with registered container object.");
1224         } else {
1225                 ast_cli(a->fd, "Container '%s' not found.\n", name);
1226         }
1227
1228         return CLI_SUCCESS;
1229 }
1230 #endif  /* defined(AST_DEVMODE) */
1231
1232 #if defined(AST_DEVMODE)
1233 static struct ast_cli_entry cli_astobj2[] = {
1234         AST_CLI_DEFINE(handle_cli_astobj2_container_dump, "Show container contents"),
1235         AST_CLI_DEFINE(handle_cli_astobj2_container_stats, "Show container statistics"),
1236         AST_CLI_DEFINE(handle_cli_astobj2_container_check, "Perform a container integrity check"),
1237 };
1238 #endif  /* defined(AST_DEVMODE) */
1239
1240 #if defined(AST_DEVMODE)
1241 static void container_cleanup(void)
1242 {
1243         ao2_t_ref(reg_containers, -1, "Releasing container registration container");
1244         reg_containers = NULL;
1245
1246         ast_cli_unregister_multiple(cli_astobj2, ARRAY_LEN(cli_astobj2));
1247 }
1248 #endif  /* defined(AST_DEVMODE) */
1249
1250 int container_init(void)
1251 {
1252 #if defined(AST_DEVMODE)
1253         reg_containers = ao2_t_container_alloc_list(AO2_ALLOC_OPT_LOCK_RWLOCK,
1254                 AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE, ao2_reg_sort_cb, NULL,
1255                 "Container registration container.");
1256         if (!reg_containers) {
1257                 return -1;
1258         }
1259
1260         ast_cli_register_multiple(cli_astobj2, ARRAY_LEN(cli_astobj2));
1261         ast_register_atexit(container_cleanup);
1262 #endif  /* defined(AST_DEVMODE) */
1263
1264         return 0;
1265 }
1266