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