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