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