Merge "PJSIP_CONTACT: add missing argument documentation"
[asterisk/asterisk.git] / main / astobj2_hash.c
1 /*
2  * astobj2_hash - Hash table 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 Hash table 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 "astobj2_private.h"
29 #include "astobj2_container_private.h"
30 #include "asterisk/dlinkedlists.h"
31 #include "asterisk/utils.h"
32
33 /*!
34  * A structure to create a linked list of entries,
35  * used within a bucket.
36  */
37 struct hash_bucket_node {
38         /*!
39          * \brief Items common to all container nodes.
40          * \note Must be first in the specific node struct.
41          */
42         struct ao2_container_node common;
43         /*! Next node links in the list. */
44         AST_DLLIST_ENTRY(hash_bucket_node) links;
45         /*! Hash bucket holding the node. */
46         int my_bucket;
47 };
48
49 struct hash_bucket {
50         /*! List of objects held in the bucket. */
51         AST_DLLIST_HEAD_NOLOCK(, hash_bucket_node) list;
52 #if defined(AO2_DEBUG)
53         /*! Number of elements currently in the bucket. */
54         int elements;
55         /*! Maximum number of elements in the bucket. */
56         int max_elements;
57 #endif  /* defined(AO2_DEBUG) */
58 };
59
60 /*!
61  * A hash container in addition to values common to all
62  * container types, stores the hash callback function, the
63  * number of hash buckets, and the hash bucket heads.
64  */
65 struct ao2_container_hash {
66         /*!
67          * \brief Items common to all containers.
68          * \note Must be first in the specific container struct.
69          */
70         struct ao2_container common;
71         ao2_hash_fn *hash_fn;
72         /*! Number of hash buckets in this container. */
73         int n_buckets;
74         /*! Hash bucket array of n_buckets.  Variable size. */
75         struct hash_bucket buckets[0];
76 };
77
78 /*! Traversal state to restart a hash container traversal. */
79 struct hash_traversal_state {
80         /*! Active sort function in the traversal if not NULL. */
81         ao2_sort_fn *sort_fn;
82         /*! Saved comparison callback arg pointer. */
83         void *arg;
84         /*! Starting hash bucket */
85         int bucket_start;
86         /*! Stopping hash bucket */
87         int bucket_last;
88         /*! Saved search flags to control traversing the container. */
89         enum search_flags flags;
90         /*! TRUE if it is a descending search */
91         unsigned int descending:1;
92 };
93
94 struct hash_traversal_state_check {
95         /*
96          * If we have a division by zero compile error here then there
97          * is not enough room for the state.  Increase AO2_TRAVERSAL_STATE_SIZE.
98          */
99         char check[1 / (AO2_TRAVERSAL_STATE_SIZE / sizeof(struct hash_traversal_state))];
100 };
101
102 /*!
103  * \internal
104  * \brief Create an empty copy of this container.
105  * \since 14.0.0
106  *
107  * \param self Container to operate upon.
108  * \param tag used for debugging.
109  * \param file Debug file name invoked from
110  * \param line Debug line invoked from
111  * \param func Debug function name invoked from
112  *
113  * \retval empty-clone-container on success.
114  * \retval NULL on error.
115  */
116 static struct ao2_container *hash_ao2_alloc_empty_clone(struct ao2_container_hash *self,
117         const char *tag, const char *file, int line, const char *func)
118 {
119         if (!__is_ao2_object(self, file, line, func)) {
120                 return NULL;
121         }
122
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);
126 }
127
128 /*!
129  * \internal
130  * \brief Destroy a hash container list node.
131  * \since 12.0.0
132  *
133  * \param v_doomed Container node to destroy.
134  *
135  * \details
136  * The container node unlinks itself from the container as part
137  * of its destruction.  The node must be destroyed while the
138  * container is already locked.
139  *
140  * \note The container must be locked when the node is
141  * unreferenced.
142  *
143  * \return Nothing
144  */
145 static void hash_ao2_node_destructor(void *v_doomed)
146 {
147         struct hash_bucket_node *doomed = v_doomed;
148
149         if (doomed->common.is_linked) {
150                 struct ao2_container_hash *my_container;
151                 struct hash_bucket *bucket;
152
153                 /*
154                  * Promote to write lock if not already there.  Since
155                  * adjust_lock() can potentially release and block waiting for a
156                  * write lock, care must be taken to ensure that node references
157                  * are released before releasing the container references.
158                  *
159                  * Node references held by an iterator can only be held while
160                  * the iterator also holds a reference to the container.  These
161                  * node references must be unreferenced before the container can
162                  * be unreferenced to ensure that the node will not get a
163                  * negative reference and the destructor called twice for the
164                  * same node.
165                  */
166                 my_container = (struct ao2_container_hash *) doomed->common.my_container;
167 #ifdef AST_DEVMODE
168                 is_ao2_object(my_container);
169 #endif
170
171                 __adjust_lock(my_container, AO2_LOCK_REQ_WRLOCK, 1);
172
173 #if defined(AO2_DEBUG)
174                 if (!my_container->common.destroying
175                         && ao2_container_check(doomed->common.my_container, OBJ_NOLOCK)) {
176                         ast_log(LOG_ERROR, "Container integrity failed before node deletion.\n");
177                 }
178 #endif  /* defined(AO2_DEBUG) */
179                 bucket = &my_container->buckets[doomed->my_bucket];
180                 AST_DLLIST_REMOVE(&bucket->list, doomed, links);
181                 AO2_DEVMODE_STAT(--my_container->common.nodes);
182         }
183
184         /*
185          * We could have an object in the node if the container is being
186          * destroyed or the node had not been linked in yet.
187          */
188         if (doomed->common.obj) {
189                 __container_unlink_node(&doomed->common, AO2_UNLINK_NODE_UNLINK_OBJECT);
190         }
191 }
192
193 /*!
194  * \internal
195  * \brief Create a new container node.
196  * \since 12.0.0
197  *
198  * \param self Container to operate upon.
199  * \param obj_new Object to put into the node.
200  * \param tag used for debugging.
201  * \param file Debug file name invoked from
202  * \param line Debug line invoked from
203  * \param func Debug function name invoked from
204  *
205  * \retval initialized-node on success.
206  * \retval NULL on error.
207  */
208 static struct hash_bucket_node *hash_ao2_new_node(struct ao2_container_hash *self, void *obj_new, const char *tag, const char *file, int line, const char *func)
209 {
210         struct hash_bucket_node *node;
211         int i;
212
213         node = ao2_alloc_options(sizeof(*node), hash_ao2_node_destructor,
214                 AO2_ALLOC_OPT_LOCK_NOLOCK | AO2_ALLOC_OPT_NO_REF_DEBUG);
215         if (!node) {
216                 return NULL;
217         }
218
219         i = abs(self->hash_fn(obj_new, OBJ_SEARCH_OBJECT) % self->n_buckets);
220
221         __ao2_ref(obj_new, +1, tag ?: "Container node creation", file, line, func);
222         node->common.obj = obj_new;
223         node->common.my_container = (struct ao2_container *) self;
224         node->my_bucket = i;
225
226         return node;
227 }
228
229 /*!
230  * \internal
231  * \brief Insert a node into this container.
232  * \since 12.0.0
233  *
234  * \param self Container to operate upon.
235  * \param node Container node to insert into the container.
236  *
237  * \return enum ao2_container_insert value.
238  */
239 static enum ao2_container_insert hash_ao2_insert_node(struct ao2_container_hash *self,
240         struct hash_bucket_node *node)
241 {
242         int cmp;
243         struct hash_bucket *bucket;
244         struct hash_bucket_node *cur;
245         ao2_sort_fn *sort_fn;
246         uint32_t options;
247
248         bucket = &self->buckets[node->my_bucket];
249         sort_fn = self->common.sort_fn;
250         options = self->common.options;
251
252         if (options & AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN) {
253                 if (sort_fn) {
254                         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&bucket->list, cur, links) {
255                                 cmp = sort_fn(cur->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
256                                 if (cmp > 0) {
257                                         continue;
258                                 }
259                                 if (cmp < 0) {
260                                         AST_DLLIST_INSERT_AFTER_CURRENT(node, links);
261                                         return AO2_CONTAINER_INSERT_NODE_INSERTED;
262                                 }
263                                 switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
264                                 default:
265                                 case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW:
266                                         break;
267                                 case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT:
268                                         /* Reject all objects with the same key. */
269                                         return AO2_CONTAINER_INSERT_NODE_REJECTED;
270                                 case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT:
271                                         if (cur->common.obj == node->common.obj) {
272                                                 /* Reject inserting the same object */
273                                                 return AO2_CONTAINER_INSERT_NODE_REJECTED;
274                                         }
275                                         break;
276                                 case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE:
277                                         SWAP(cur->common.obj, node->common.obj);
278                                         ao2_ref(node, -1);
279                                         return AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED;
280                                 }
281                         }
282                         AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END;
283                 }
284                 AST_DLLIST_INSERT_HEAD(&bucket->list, node, links);
285         } else {
286                 if (sort_fn) {
287                         AST_DLLIST_TRAVERSE_SAFE_BEGIN(&bucket->list, cur, links) {
288                                 cmp = sort_fn(cur->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
289                                 if (cmp < 0) {
290                                         continue;
291                                 }
292                                 if (cmp > 0) {
293                                         AST_DLLIST_INSERT_BEFORE_CURRENT(node, links);
294                                         return AO2_CONTAINER_INSERT_NODE_INSERTED;
295                                 }
296                                 switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
297                                 default:
298                                 case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW:
299                                         break;
300                                 case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT:
301                                         /* Reject all objects with the same key. */
302                                         return AO2_CONTAINER_INSERT_NODE_REJECTED;
303                                 case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT:
304                                         if (cur->common.obj == node->common.obj) {
305                                                 /* Reject inserting the same object */
306                                                 return AO2_CONTAINER_INSERT_NODE_REJECTED;
307                                         }
308                                         break;
309                                 case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE:
310                                         SWAP(cur->common.obj, node->common.obj);
311                                         ao2_ref(node, -1);
312                                         return AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED;
313                                 }
314                         }
315                         AST_DLLIST_TRAVERSE_SAFE_END;
316                 }
317                 AST_DLLIST_INSERT_TAIL(&bucket->list, node, links);
318         }
319         return AO2_CONTAINER_INSERT_NODE_INSERTED;
320 }
321
322 /*!
323  * \internal
324  * \brief Find the first hash container node in a traversal.
325  * \since 12.0.0
326  *
327  * \param self Container to operate upon.
328  * \param flags search_flags to control traversing the container
329  * \param arg Comparison callback arg parameter.
330  * \param state Traversal state to restart hash container traversal.
331  *
332  * \retval node-ptr of found node (Reffed).
333  * \retval NULL when no node found.
334  */
335 static struct hash_bucket_node *hash_ao2_find_first(struct ao2_container_hash *self, enum search_flags flags, void *arg, struct hash_traversal_state *state)
336 {
337         struct hash_bucket_node *node;
338         int bucket_cur;
339         int cmp;
340
341         memset(state, 0, sizeof(*state));
342         state->arg = arg;
343         state->flags = flags;
344
345         /* Determine traversal order. */
346         switch (flags & OBJ_ORDER_MASK) {
347         case OBJ_ORDER_POST:
348         case OBJ_ORDER_DESCENDING:
349                 state->descending = 1;
350                 break;
351         case OBJ_ORDER_PRE:
352         case OBJ_ORDER_ASCENDING:
353         default:
354                 break;
355         }
356
357         /*
358          * If lookup by pointer or search key, run the hash and optional
359          * sort functions.  Otherwise, traverse the whole container.
360          */
361         switch (flags & OBJ_SEARCH_MASK) {
362         case OBJ_SEARCH_OBJECT:
363         case OBJ_SEARCH_KEY:
364                 /* we know hash can handle this case */
365                 bucket_cur = abs(self->hash_fn(arg, flags & OBJ_SEARCH_MASK)
366                                 % self->n_buckets);
367                 state->sort_fn = self->common.sort_fn;
368                 break;
369         case OBJ_SEARCH_PARTIAL_KEY:
370                 /* scan all buckets for partial key matches */
371                 bucket_cur = -1;
372                 state->sort_fn = self->common.sort_fn;
373                 break;
374         default:
375                 /* don't know, let's scan all buckets */
376                 bucket_cur = -1;
377                 state->sort_fn = NULL;
378                 break;
379         }
380
381         if (state->descending) {
382                 /*
383                  * Determine the search boundaries of a descending traversal.
384                  *
385                  * bucket_cur downto state->bucket_last
386                  */
387                 if (bucket_cur < 0) {
388                         bucket_cur = self->n_buckets - 1;
389                         state->bucket_last = 0;
390                 } else {
391                         state->bucket_last = bucket_cur;
392                 }
393                 state->bucket_start = bucket_cur;
394
395                 /* For each bucket */
396                 for (; state->bucket_last <= bucket_cur; --bucket_cur) {
397                         /* For each node in the bucket. */
398                         for (node = AST_DLLIST_LAST(&self->buckets[bucket_cur].list);
399                                 node;
400                                 node = AST_DLLIST_PREV(node, links)) {
401                                 if (!node->common.obj) {
402                                         /* Node is empty */
403                                         continue;
404                                 }
405
406                                 if (state->sort_fn) {
407                                         /* Filter node through the sort_fn */
408                                         cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
409                                         if (cmp > 0) {
410                                                 continue;
411                                         }
412                                         if (cmp < 0) {
413                                                 /* No more nodes in this bucket are possible to match. */
414                                                 break;
415                                         }
416                                 }
417
418                                 /* We have the first traversal node */
419                                 ao2_ref(node, +1);
420                                 return node;
421                         }
422                 }
423         } else {
424                 /*
425                  * Determine the search boundaries of an ascending traversal.
426                  *
427                  * bucket_cur to state->bucket_last-1
428                  */
429                 if (bucket_cur < 0) {
430                         bucket_cur = 0;
431                         state->bucket_last = self->n_buckets;
432                 } else {
433                         state->bucket_last = bucket_cur + 1;
434                 }
435                 state->bucket_start = bucket_cur;
436
437                 /* For each bucket */
438                 for (; bucket_cur < state->bucket_last; ++bucket_cur) {
439                         /* For each node in the bucket. */
440                         for (node = AST_DLLIST_FIRST(&self->buckets[bucket_cur].list);
441                                 node;
442                                 node = AST_DLLIST_NEXT(node, links)) {
443                                 if (!node->common.obj) {
444                                         /* Node is empty */
445                                         continue;
446                                 }
447
448                                 if (state->sort_fn) {
449                                         /* Filter node through the sort_fn */
450                                         cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
451                                         if (cmp < 0) {
452                                                 continue;
453                                         }
454                                         if (cmp > 0) {
455                                                 /* No more nodes in this bucket are possible to match. */
456                                                 break;
457                                         }
458                                 }
459
460                                 /* We have the first traversal node */
461                                 ao2_ref(node, +1);
462                                 return node;
463                         }
464                 }
465         }
466
467         return NULL;
468 }
469
470 /*!
471  * \internal
472  * \brief Find the next hash container node in a traversal.
473  * \since 12.0.0
474  *
475  * \param self Container to operate upon.
476  * \param state Traversal state to restart hash container traversal.
477  * \param prev Previous node returned by the traversal search functions.
478  *    The ref ownership is passed back to this function.
479  *
480  * \retval node-ptr of found node (Reffed).
481  * \retval NULL when no node found.
482  */
483 static struct hash_bucket_node *hash_ao2_find_next(struct ao2_container_hash *self, struct hash_traversal_state *state, struct hash_bucket_node *prev)
484 {
485         struct hash_bucket_node *node;
486         void *arg;
487         enum search_flags flags;
488         int bucket_cur;
489         int cmp;
490
491         arg = state->arg;
492         flags = state->flags;
493         bucket_cur = prev->my_bucket;
494         node = prev;
495
496         /*
497          * This function is structured the same as hash_ao2_find_first()
498          * intentionally.  We are resuming the search loops from
499          * hash_ao2_find_first() in order to find the next node.  The
500          * search loops must be resumed where hash_ao2_find_first()
501          * returned with the first node.
502          */
503         if (state->descending) {
504                 goto hash_descending_resume;
505
506                 /* For each bucket */
507                 for (; state->bucket_last <= bucket_cur; --bucket_cur) {
508                         /* For each node in the bucket. */
509                         for (node = AST_DLLIST_LAST(&self->buckets[bucket_cur].list);
510                                 node;
511                                 node = AST_DLLIST_PREV(node, links)) {
512                                 if (!node->common.obj) {
513                                         /* Node is empty */
514                                         continue;
515                                 }
516
517                                 if (state->sort_fn) {
518                                         /* Filter node through the sort_fn */
519                                         cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
520                                         if (cmp > 0) {
521                                                 continue;
522                                         }
523                                         if (cmp < 0) {
524                                                 /* No more nodes in this bucket are possible to match. */
525                                                 break;
526                                         }
527                                 }
528
529                                 /* We have the next traversal node */
530                                 ao2_ref(node, +1);
531
532                                 /*
533                                  * Dereferencing the prev node may result in our next node
534                                  * object being removed by another thread.  This could happen if
535                                  * the container uses RW locks and the container was read
536                                  * locked.
537                                  */
538                                 ao2_ref(prev, -1);
539                                 if (node->common.obj) {
540                                         return node;
541                                 }
542                                 prev = node;
543
544 hash_descending_resume:;
545                         }
546                 }
547         } else {
548                 goto hash_ascending_resume;
549
550                 /* For each bucket */
551                 for (; bucket_cur < state->bucket_last; ++bucket_cur) {
552                         /* For each node in the bucket. */
553                         for (node = AST_DLLIST_FIRST(&self->buckets[bucket_cur].list);
554                                 node;
555                                 node = AST_DLLIST_NEXT(node, links)) {
556                                 if (!node->common.obj) {
557                                         /* Node is empty */
558                                         continue;
559                                 }
560
561                                 if (state->sort_fn) {
562                                         /* Filter node through the sort_fn */
563                                         cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
564                                         if (cmp < 0) {
565                                                 continue;
566                                         }
567                                         if (cmp > 0) {
568                                                 /* No more nodes in this bucket are possible to match. */
569                                                 break;
570                                         }
571                                 }
572
573                                 /* We have the next traversal node */
574                                 ao2_ref(node, +1);
575
576                                 /*
577                                  * Dereferencing the prev node may result in our next node
578                                  * object being removed by another thread.  This could happen if
579                                  * the container uses RW locks and the container was read
580                                  * locked.
581                                  */
582                                 ao2_ref(prev, -1);
583                                 if (node->common.obj) {
584                                         return node;
585                                 }
586                                 prev = node;
587
588 hash_ascending_resume:;
589                         }
590                 }
591         }
592
593         /* No more nodes in the container left to traverse. */
594         ao2_ref(prev, -1);
595         return NULL;
596 }
597
598 /*!
599  * \internal
600  * \brief Find the next non-empty iteration node in the container.
601  * \since 12.0.0
602  *
603  * \param self Container to operate upon.
604  * \param node Previous node returned by the iterator.
605  * \param flags search_flags to control iterating the container.
606  *   Only AO2_ITERATOR_DESCENDING is useful by the method.
607  *
608  * \note The container is already locked.
609  *
610  * \retval node on success.
611  * \retval NULL on error or no more nodes in the container.
612  */
613 static struct hash_bucket_node *hash_ao2_iterator_next(struct ao2_container_hash *self, struct hash_bucket_node *node, enum ao2_iterator_flags flags)
614 {
615         int cur_bucket;
616
617         if (flags & AO2_ITERATOR_DESCENDING) {
618                 if (node) {
619                         cur_bucket = node->my_bucket;
620
621                         /* Find next non-empty node. */
622                         for (;;) {
623                                 node = AST_DLLIST_PREV(node, links);
624                                 if (!node) {
625                                         break;
626                                 }
627                                 if (node->common.obj) {
628                                         /* Found a non-empty node. */
629                                         return node;
630                                 }
631                         }
632                 } else {
633                         /* Find first non-empty node. */
634                         cur_bucket = self->n_buckets;
635                 }
636
637                 /* Find a non-empty node in the remaining buckets */
638                 while (0 <= --cur_bucket) {
639                         node = AST_DLLIST_LAST(&self->buckets[cur_bucket].list);
640                         while (node) {
641                                 if (node->common.obj) {
642                                         /* Found a non-empty node. */
643                                         return node;
644                                 }
645                                 node = AST_DLLIST_PREV(node, links);
646                         }
647                 }
648         } else {
649                 if (node) {
650                         cur_bucket = node->my_bucket;
651
652                         /* Find next non-empty node. */
653                         for (;;) {
654                                 node = AST_DLLIST_NEXT(node, links);
655                                 if (!node) {
656                                         break;
657                                 }
658                                 if (node->common.obj) {
659                                         /* Found a non-empty node. */
660                                         return node;
661                                 }
662                         }
663                 } else {
664                         /* Find first non-empty node. */
665                         cur_bucket = -1;
666                 }
667
668                 /* Find a non-empty node in the remaining buckets */
669                 while (++cur_bucket < self->n_buckets) {
670                         node = AST_DLLIST_FIRST(&self->buckets[cur_bucket].list);
671                         while (node) {
672                                 if (node->common.obj) {
673                                         /* Found a non-empty node. */
674                                         return node;
675                                 }
676                                 node = AST_DLLIST_NEXT(node, links);
677                         }
678                 }
679         }
680
681         /* No more nodes to visit in the container. */
682         return NULL;
683 }
684
685 #if defined(AO2_DEBUG)
686 /*!
687  * \internal
688  * \brief Increment the hash container linked object statistic.
689  * \since 12.0.0
690  *
691  * \param hash Container to operate upon.
692  * \param hash_node Container node linking object to.
693  *
694  * \return Nothing
695  */
696 static void hash_ao2_link_node_stat(struct ao2_container *hash, struct ao2_container_node *hash_node)
697 {
698         struct ao2_container_hash *self = (struct ao2_container_hash *) hash;
699         struct hash_bucket_node *node = (struct hash_bucket_node *) hash_node;
700         int i = node->my_bucket;
701
702         ++self->buckets[i].elements;
703         if (self->buckets[i].max_elements < self->buckets[i].elements) {
704                 self->buckets[i].max_elements = self->buckets[i].elements;
705         }
706 }
707 #endif  /* defined(AO2_DEBUG) */
708
709 #if defined(AO2_DEBUG)
710 /*!
711  * \internal
712  * \brief Decrement the hash container linked object statistic.
713  * \since 12.0.0
714  *
715  * \param hash Container to operate upon.
716  * \param hash_node Container node unlinking object from.
717  *
718  * \return Nothing
719  */
720 static void hash_ao2_unlink_node_stat(struct ao2_container *hash, struct ao2_container_node *hash_node)
721 {
722         struct ao2_container_hash *self = (struct ao2_container_hash *) hash;
723         struct hash_bucket_node *node = (struct hash_bucket_node *) hash_node;
724
725         --self->buckets[node->my_bucket].elements;
726 }
727 #endif  /* defined(AO2_DEBUG) */
728
729 /*!
730  * \internal
731  *
732  * \brief Destroy this container.
733  * \since 12.0.0
734  *
735  * \param self Container to operate upon.
736  *
737  * \return Nothing
738  */
739 static void hash_ao2_destroy(struct ao2_container_hash *self)
740 {
741         int idx;
742
743         /* Check that the container no longer has any nodes */
744         for (idx = self->n_buckets; idx--;) {
745                 if (!AST_DLLIST_EMPTY(&self->buckets[idx].list)) {
746                         ast_log(LOG_ERROR, "Node ref leak.  Hash container still has nodes!\n");
747                         ast_assert(0);
748                         break;
749                 }
750         }
751 }
752
753 #if defined(AO2_DEBUG)
754 /*!
755  * \internal
756  * \brief Display contents of the specified container.
757  * \since 12.0.0
758  *
759  * \param self Container to dump.
760  * \param where User data needed by prnt to determine where to put output.
761  * \param prnt Print output callback function to use.
762  * \param prnt_obj Callback function to print the given object's key. (NULL if not available)
763  *
764  * \return Nothing
765  */
766 static void hash_ao2_dump(struct ao2_container_hash *self, void *where, ao2_prnt_fn *prnt, ao2_prnt_obj_fn *prnt_obj)
767 {
768 #define FORMAT  "%6s, %16s, %16s, %16s, %16s, %s\n"
769 #define FORMAT2 "%6d, %16p, %16p, %16p, %16p, "
770
771         int bucket;
772         int suppressed_buckets = 0;
773         struct hash_bucket_node *node;
774
775         prnt(where, "Number of buckets: %d\n\n", self->n_buckets);
776
777         prnt(where, FORMAT, "Bucket", "Node", "Prev", "Next", "Obj", "Key");
778         for (bucket = 0; bucket < self->n_buckets; ++bucket) {
779                 node = AST_DLLIST_FIRST(&self->buckets[bucket].list);
780                 if (node) {
781                         suppressed_buckets = 0;
782                         do {
783                                 prnt(where, FORMAT2,
784                                         bucket,
785                                         node,
786                                         AST_DLLIST_PREV(node, links),
787                                         AST_DLLIST_NEXT(node, links),
788                                         node->common.obj);
789                                 if (node->common.obj && prnt_obj) {
790                                         prnt_obj(node->common.obj, where, prnt);
791                                 }
792                                 prnt(where, "\n");
793
794                                 node = AST_DLLIST_NEXT(node, links);
795                         } while (node);
796                 } else if (!suppressed_buckets) {
797                         suppressed_buckets = 1;
798                         prnt(where, "...\n");
799                 }
800         }
801
802 #undef FORMAT
803 #undef FORMAT2
804 }
805 #endif  /* defined(AO2_DEBUG) */
806
807 #if defined(AO2_DEBUG)
808 /*!
809  * \internal
810  * \brief Display statistics of the specified container.
811  * \since 12.0.0
812  *
813  * \param self Container to display statistics.
814  * \param where User data needed by prnt to determine where to put output.
815  * \param prnt Print output callback function to use.
816  *
817  * \note The container is already locked for reading.
818  *
819  * \return Nothing
820  */
821 static void hash_ao2_stats(struct ao2_container_hash *self, void *where, ao2_prnt_fn *prnt)
822 {
823 #define FORMAT  "%10.10s %10.10s %10.10s\n"
824 #define FORMAT2 "%10d %10d %10d\n"
825
826         int bucket;
827         int suppressed_buckets = 0;
828
829         prnt(where, "Number of buckets: %d\n\n", self->n_buckets);
830
831         prnt(where, FORMAT, "Bucket", "Objects", "Max");
832         for (bucket = 0; bucket < self->n_buckets; ++bucket) {
833                 if (self->buckets[bucket].max_elements) {
834                         suppressed_buckets = 0;
835                         prnt(where, FORMAT2, bucket, self->buckets[bucket].elements,
836                                 self->buckets[bucket].max_elements);
837                 } else if (!suppressed_buckets) {
838                         suppressed_buckets = 1;
839                         prnt(where, "...\n");
840                 }
841         }
842
843 #undef FORMAT
844 #undef FORMAT2
845 }
846 #endif  /* defined(AO2_DEBUG) */
847
848 #if defined(AO2_DEBUG)
849 /*!
850  * \internal
851  * \brief Perform an integrity check on the specified container.
852  * \since 12.0.0
853  *
854  * \param self Container to check integrity.
855  *
856  * \note The container is already locked for reading.
857  *
858  * \retval 0 on success.
859  * \retval -1 on error.
860  */
861 static int hash_ao2_integrity(struct ao2_container_hash *self)
862 {
863         int bucket_exp;
864         int bucket;
865         int count_obj;
866         int count_total_obj;
867         int count_total_node;
868         void *obj_last;
869         struct hash_bucket_node *node;
870         struct hash_bucket_node *prev;
871         struct hash_bucket_node *next;
872
873         count_total_obj = 0;
874         count_total_node = 0;
875
876         /* For each bucket in the container. */
877         for (bucket = 0; bucket < self->n_buckets; ++bucket) {
878                 if (!AST_DLLIST_FIRST(&self->buckets[bucket].list)
879                         && !AST_DLLIST_LAST(&self->buckets[bucket].list)) {
880                         /* The bucket list is empty. */
881                         continue;
882                 }
883
884                 count_obj = 0;
885                 obj_last = NULL;
886
887                 /* Check bucket list links and nodes. */
888                 node = AST_DLLIST_LAST(&self->buckets[bucket].list);
889                 if (!node) {
890                         ast_log(LOG_ERROR, "Bucket %d list tail is NULL when it should not be!\n",
891                                 bucket);
892                         return -1;
893                 }
894                 if (AST_DLLIST_NEXT(node, links)) {
895                         ast_log(LOG_ERROR, "Bucket %d list tail node is not the last node!\n",
896                                 bucket);
897                         return -1;
898                 }
899                 node = AST_DLLIST_FIRST(&self->buckets[bucket].list);
900                 if (!node) {
901                         ast_log(LOG_ERROR, "Bucket %d list head is NULL when it should not be!\n",
902                                 bucket);
903                         return -1;
904                 }
905                 if (AST_DLLIST_PREV(node, links)) {
906                         ast_log(LOG_ERROR, "Bucket %d list head node is not the first node!\n",
907                                 bucket);
908                         return -1;
909                 }
910                 for (; node; node = next) {
911                         /* Check backward link. */
912                         prev = AST_DLLIST_PREV(node, links);
913                         if (prev) {
914                                 if (prev == node) {
915                                         ast_log(LOG_ERROR, "Bucket %d list node's prev pointer points to itself!\n",
916                                                 bucket);
917                                         return -1;
918                                 }
919                                 if (node != AST_DLLIST_NEXT(prev, links)) {
920                                         ast_log(LOG_ERROR, "Bucket %d list node's prev node does not link back!\n",
921                                                 bucket);
922                                         return -1;
923                                 }
924                         } else if (node != AST_DLLIST_FIRST(&self->buckets[bucket].list)) {
925                                 ast_log(LOG_ERROR, "Bucket %d backward list chain is broken!\n",
926                                         bucket);
927                                 return -1;
928                         }
929
930                         /* Check forward link. */
931                         next = AST_DLLIST_NEXT(node, links);
932                         if (next) {
933                                 if (next == node) {
934                                         ast_log(LOG_ERROR, "Bucket %d list node's next pointer points to itself!\n",
935                                                 bucket);
936                                         return -1;
937                                 }
938                                 if (node != AST_DLLIST_PREV(next, links)) {
939                                         ast_log(LOG_ERROR, "Bucket %d list node's next node does not link back!\n",
940                                                 bucket);
941                                         return -1;
942                                 }
943                         } else if (node != AST_DLLIST_LAST(&self->buckets[bucket].list)) {
944                                 ast_log(LOG_ERROR, "Bucket %d forward list chain is broken!\n",
945                                         bucket);
946                                 return -1;
947                         }
948
949                         if (bucket != node->my_bucket) {
950                                 ast_log(LOG_ERROR, "Bucket %d node claims to be in bucket %d!\n",
951                                         bucket, node->my_bucket);
952                                 return -1;
953                         }
954
955                         ++count_total_node;
956                         if (!node->common.obj) {
957                                 /* Node is empty. */
958                                 continue;
959                         }
960                         ++count_obj;
961
962                         /* Check container hash key for expected bucket. */
963                         bucket_exp = abs(self->hash_fn(node->common.obj, OBJ_SEARCH_OBJECT)
964                                         % self->n_buckets);
965                         if (bucket != bucket_exp) {
966                                 ast_log(LOG_ERROR, "Bucket %d node hashes to bucket %d!\n",
967                                         bucket, bucket_exp);
968                                 return -1;
969                         }
970
971                         /* Check sort if configured. */
972                         if (self->common.sort_fn) {
973                                 if (obj_last
974                                         && self->common.sort_fn(obj_last, node->common.obj, OBJ_SEARCH_OBJECT) > 0) {
975                                         ast_log(LOG_ERROR, "Bucket %d nodes out of sorted order!\n",
976                                                 bucket);
977                                         return -1;
978                                 }
979                                 obj_last = node->common.obj;
980                         }
981                 }
982
983                 /* Check bucket obj count statistic. */
984                 if (count_obj != self->buckets[bucket].elements) {
985                         ast_log(LOG_ERROR, "Bucket %d object count of %d does not match stat of %d!\n",
986                                 bucket, count_obj, self->buckets[bucket].elements);
987                         return -1;
988                 }
989
990                 /* Accumulate found object counts. */
991                 count_total_obj += count_obj;
992         }
993
994         /* Check total obj count. */
995         if (count_total_obj != ao2_container_count(&self->common)) {
996                 ast_log(LOG_ERROR,
997                         "Total object count of %d does not match ao2_container_count() of %d!\n",
998                         count_total_obj, ao2_container_count(&self->common));
999                 return -1;
1000         }
1001
1002         /* Check total node count. */
1003         if (count_total_node != self->common.nodes) {
1004                 ast_log(LOG_ERROR, "Total node count of %d does not match stat of %d!\n",
1005                         count_total_node, self->common.nodes);
1006                 return -1;
1007         }
1008
1009         return 0;
1010 }
1011 #endif  /* defined(AO2_DEBUG) */
1012
1013 /*! Hash container virtual method table. */
1014 static const struct ao2_container_methods v_table_hash = {
1015         .alloc_empty_clone = (ao2_container_alloc_empty_clone_fn) hash_ao2_alloc_empty_clone,
1016         .new_node = (ao2_container_new_node_fn) hash_ao2_new_node,
1017         .insert = (ao2_container_insert_fn) hash_ao2_insert_node,
1018         .traverse_first = (ao2_container_find_first_fn) hash_ao2_find_first,
1019         .traverse_next = (ao2_container_find_next_fn) hash_ao2_find_next,
1020         .iterator_next = (ao2_iterator_next_fn) hash_ao2_iterator_next,
1021         .destroy = (ao2_container_destroy_fn) hash_ao2_destroy,
1022 #if defined(AO2_DEBUG)
1023         .link_stat = hash_ao2_link_node_stat,
1024         .unlink_stat = hash_ao2_unlink_node_stat,
1025         .dump = (ao2_container_display) hash_ao2_dump,
1026         .stats = (ao2_container_statistics) hash_ao2_stats,
1027         .integrity = (ao2_container_integrity) hash_ao2_integrity,
1028 #endif  /* defined(AO2_DEBUG) */
1029 };
1030
1031 /*!
1032  * \brief always zero hash function
1033  *
1034  * it is convenient to have a hash function that always returns 0.
1035  * This is basically used when we want to have a container that is
1036  * a simple linked list.
1037  *
1038  * \returns 0
1039  */
1040 static int hash_zero(const void *user_obj, const int flags)
1041 {
1042         return 0;
1043 }
1044
1045 /*!
1046  * \brief Initialize a hash container with the desired number of buckets.
1047  *
1048  * \param self Container to initialize.
1049  * \param options Container behaviour options (See enum ao2_container_opts)
1050  * \param n_buckets Number of buckets for hash
1051  * \param hash_fn Pointer to a function computing a hash value.
1052  * \param sort_fn Pointer to a sort function.
1053  * \param cmp_fn Pointer to a compare function used by ao2_find.
1054  *
1055  * \return A pointer to a struct container.
1056  */
1057 static struct ao2_container *hash_ao2_container_init(
1058         struct ao2_container_hash *self, unsigned int options, unsigned int n_buckets,
1059         ao2_hash_fn *hash_fn, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn)
1060 {
1061         if (!self) {
1062                 return NULL;
1063         }
1064
1065         self->common.v_table = &v_table_hash;
1066         self->common.sort_fn = sort_fn;
1067         self->common.cmp_fn = cmp_fn;
1068         self->common.options = options;
1069         self->hash_fn = hash_fn ? hash_fn : hash_zero;
1070         self->n_buckets = n_buckets;
1071
1072 #ifdef AO2_DEBUG
1073         ast_atomic_fetchadd_int(&ao2.total_containers, 1);
1074 #endif  /* defined(AO2_DEBUG) */
1075
1076         return (struct ao2_container *) self;
1077 }
1078
1079 struct ao2_container *__ao2_container_alloc_hash(unsigned int ao2_options,
1080         unsigned int container_options, unsigned int n_buckets, ao2_hash_fn *hash_fn,
1081         ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn,
1082         const char *tag, const char *file, int line, const char *func)
1083 {
1084         unsigned int num_buckets;
1085         size_t container_size;
1086         struct ao2_container_hash *self;
1087
1088         num_buckets = hash_fn ? n_buckets : 1;
1089         container_size = sizeof(struct ao2_container_hash) + num_buckets * sizeof(struct hash_bucket);
1090
1091         self = __ao2_alloc(container_size, container_destruct, ao2_options,
1092                 tag ?: __PRETTY_FUNCTION__, file, line, func);
1093         return hash_ao2_container_init(self, container_options, num_buckets, hash_fn,
1094                 sort_fn, cmp_fn);
1095 }
1096
1097 struct ao2_container *__ao2_container_alloc_list(unsigned int ao2_options,
1098         unsigned int container_options, ao2_sort_fn *sort_fn, ao2_callback_fn *cmp_fn,
1099         const char *tag, const char *file, int line, const char *func)
1100 {
1101         return __ao2_container_alloc_hash(ao2_options, container_options, 1, NULL,
1102                 sort_fn, cmp_fn, tag, file, line, func);
1103 }