~singpolyma/asterisk

ref: 51af79b42e4ae7d1831603633d73bf0df179720e asterisk/main/astobj2_hash.c -rw-r--r-- 30.1 KiB
51af79b4Christopher Vollick Content Created By Initiator 2: Electric Boogaloo 9 months ago
                                                                                
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
/*
 * astobj2_hash - Hash table implementation for astobj2.
 *
 * Copyright (C) 2006 Marta Carbone, Luigi Rizzo - Univ. di Pisa, Italy
 *
 * See http://www.asterisk.org for more information about
 * the Asterisk project. Please do not directly contact
 * any of the maintainers of this project for assistance;
 * the project provides a web site, mailing lists and IRC
 * channels for your use.
 *
 * This program is free software, distributed under the terms of
 * the GNU General Public License Version 2. See the LICENSE file
 * at the top of the source tree.
 */

/*! \file
 *
 * \brief Hash table functions implementing astobj2 containers.
 *
 * \author Richard Mudgett <rmudgett@digium.com>
 */

#include "asterisk.h"

#include "asterisk/_private.h"
#include "asterisk/astobj2.h"
#include "astobj2_private.h"
#include "astobj2_container_private.h"
#include "asterisk/dlinkedlists.h"
#include "asterisk/utils.h"

/*!
 * A structure to create a linked list of entries,
 * used within a bucket.
 */
struct hash_bucket_node {
	/*!
	 * \brief Items common to all container nodes.
	 * \note Must be first in the specific node struct.
	 */
	struct ao2_container_node common;
	/*! Next node links in the list. */
	AST_DLLIST_ENTRY(hash_bucket_node) links;
	/*! Hash bucket holding the node. */
	int my_bucket;
};

struct hash_bucket {
	/*! List of objects held in the bucket. */
	AST_DLLIST_HEAD_NOLOCK(, hash_bucket_node) list;
#if defined(AO2_DEBUG)
	/*! Number of elements currently in the bucket. */
	int elements;
	/*! Maximum number of elements in the bucket. */
	int max_elements;
#endif	/* defined(AO2_DEBUG) */
};

/*!
 * A hash container in addition to values common to all
 * container types, stores the hash callback function, the
 * number of hash buckets, and the hash bucket heads.
 */
struct ao2_container_hash {
	/*!
	 * \brief Items common to all containers.
	 * \note Must be first in the specific container struct.
	 */
	struct ao2_container common;
	ao2_hash_fn *hash_fn;
	/*! Number of hash buckets in this container. */
	int n_buckets;
	/*! Hash bucket array of n_buckets.  Variable size. */
	struct hash_bucket buckets[0];
};

/*! Traversal state to restart a hash container traversal. */
struct hash_traversal_state {
	/*! Active sort function in the traversal if not NULL. */
	ao2_sort_fn *sort_fn;
	/*! Saved comparison callback arg pointer. */
	void *arg;
	/*! Starting hash bucket */
	int bucket_start;
	/*! Stopping hash bucket */
	int bucket_last;
	/*! Saved search flags to control traversing the container. */
	enum search_flags flags;
	/*! TRUE if it is a descending search */
	unsigned int descending:1;
};

struct hash_traversal_state_check {
	/*
	 * If we have a division by zero compile error here then there
	 * is not enough room for the state.  Increase AO2_TRAVERSAL_STATE_SIZE.
	 */
	char check[1 / (AO2_TRAVERSAL_STATE_SIZE / sizeof(struct hash_traversal_state))];
};

/*!
 * \internal
 * \brief Create an empty copy of this container.
 * \since 14.0.0
 *
 * \param self Container to operate upon.
 * \param tag used for debugging.
 * \param file Debug file name invoked from
 * \param line Debug line invoked from
 * \param func Debug function name invoked from
 *
 * \retval empty-clone-container on success.
 * \retval NULL on error.
 */
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)
{
	if (!__is_ao2_object(self, file, line, func)) {
		return NULL;
	}

	return __ao2_container_alloc_hash(ao2_options_get(self), self->common.options,
		self->n_buckets, self->hash_fn, self->common.sort_fn, self->common.cmp_fn,
		tag, file, line, func);
}

/*!
 * \internal
 * \brief Destroy a hash container list node.
 * \since 12.0.0
 *
 * \param v_doomed Container node to destroy.
 *
 * \details
 * The container node unlinks itself from the container as part
 * of its destruction.  The node must be destroyed while the
 * container is already locked.
 *
 * \note The container must be locked when the node is
 * unreferenced.
 *
 * \return Nothing
 */
static void hash_ao2_node_destructor(void *v_doomed)
{
	struct hash_bucket_node *doomed = v_doomed;

	if (doomed->common.is_linked) {
		struct ao2_container_hash *my_container;
		struct hash_bucket *bucket;

		/*
		 * Promote to write lock if not already there.  Since
		 * adjust_lock() can potentially release and block waiting for a
		 * write lock, care must be taken to ensure that node references
		 * are released before releasing the container references.
		 *
		 * Node references held by an iterator can only be held while
		 * the iterator also holds a reference to the container.  These
		 * node references must be unreferenced before the container can
		 * be unreferenced to ensure that the node will not get a
		 * negative reference and the destructor called twice for the
		 * same node.
		 */
		my_container = (struct ao2_container_hash *) doomed->common.my_container;
#ifdef AST_DEVMODE
		is_ao2_object(my_container);
#endif

		__adjust_lock(my_container, AO2_LOCK_REQ_WRLOCK, 1);

#if defined(AO2_DEBUG)
		if (!my_container->common.destroying
			&& ao2_container_check(doomed->common.my_container, OBJ_NOLOCK)) {
			ast_log(LOG_ERROR, "Container integrity failed before node deletion.\n");
		}
#endif	/* defined(AO2_DEBUG) */
		bucket = &my_container->buckets[doomed->my_bucket];
		AST_DLLIST_REMOVE(&bucket->list, doomed, links);
		AO2_DEVMODE_STAT(--my_container->common.nodes);
	}

	/*
	 * We could have an object in the node if the container is being
	 * destroyed or the node had not been linked in yet.
	 */
	if (doomed->common.obj) {
		__container_unlink_node(&doomed->common, AO2_UNLINK_NODE_UNLINK_OBJECT);
	}
}

/*!
 * \internal
 * \brief Create a new container node.
 * \since 12.0.0
 *
 * \param self Container to operate upon.
 * \param obj_new Object to put into the node.
 * \param tag used for debugging.
 * \param file Debug file name invoked from
 * \param line Debug line invoked from
 * \param func Debug function name invoked from
 *
 * \retval initialized-node on success.
 * \retval NULL on error.
 */
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)
{
	struct hash_bucket_node *node;
	int i;

	node = ao2_t_alloc_options(sizeof(*node), hash_ao2_node_destructor, AO2_ALLOC_OPT_LOCK_NOLOCK, NULL);
	if (!node) {
		return NULL;
	}

	i = abs(self->hash_fn(obj_new, OBJ_SEARCH_OBJECT) % self->n_buckets);

	__ao2_ref(obj_new, +1, tag ?: "Container node creation", file, line, func);
	node->common.obj = obj_new;
	node->common.my_container = (struct ao2_container *) self;
	node->my_bucket = i;

	return node;
}

/*!
 * \internal
 * \brief Insert a node into this container.
 * \since 12.0.0
 *
 * \param self Container to operate upon.
 * \param node Container node to insert into the container.
 *
 * \return enum ao2_container_insert value.
 */
static enum ao2_container_insert hash_ao2_insert_node(struct ao2_container_hash *self,
	struct hash_bucket_node *node)
{
	int cmp;
	struct hash_bucket *bucket;
	struct hash_bucket_node *cur;
	ao2_sort_fn *sort_fn;
	uint32_t options;

	bucket = &self->buckets[node->my_bucket];
	sort_fn = self->common.sort_fn;
	options = self->common.options;

	if (options & AO2_CONTAINER_ALLOC_OPT_INSERT_BEGIN) {
		if (sort_fn) {
			AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_BEGIN(&bucket->list, cur, links) {
				cmp = sort_fn(cur->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
				if (cmp > 0) {
					continue;
				}
				if (cmp < 0) {
					AST_DLLIST_INSERT_AFTER_CURRENT(node, links);
					return AO2_CONTAINER_INSERT_NODE_INSERTED;
				}
				switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
				default:
				case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW:
					break;
				case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT:
					/* Reject all objects with the same key. */
					return AO2_CONTAINER_INSERT_NODE_REJECTED;
				case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT:
					if (cur->common.obj == node->common.obj) {
						/* Reject inserting the same object */
						return AO2_CONTAINER_INSERT_NODE_REJECTED;
					}
					break;
				case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE:
					SWAP(cur->common.obj, node->common.obj);
					ao2_t_ref(node, -1, NULL);
					return AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED;
				}
			}
			AST_DLLIST_TRAVERSE_BACKWARDS_SAFE_END;
		}
		AST_DLLIST_INSERT_HEAD(&bucket->list, node, links);
	} else {
		if (sort_fn) {
			AST_DLLIST_TRAVERSE_SAFE_BEGIN(&bucket->list, cur, links) {
				cmp = sort_fn(cur->common.obj, node->common.obj, OBJ_SEARCH_OBJECT);
				if (cmp < 0) {
					continue;
				}
				if (cmp > 0) {
					AST_DLLIST_INSERT_BEFORE_CURRENT(node, links);
					return AO2_CONTAINER_INSERT_NODE_INSERTED;
				}
				switch (options & AO2_CONTAINER_ALLOC_OPT_DUPS_MASK) {
				default:
				case AO2_CONTAINER_ALLOC_OPT_DUPS_ALLOW:
					break;
				case AO2_CONTAINER_ALLOC_OPT_DUPS_REJECT:
					/* Reject all objects with the same key. */
					return AO2_CONTAINER_INSERT_NODE_REJECTED;
				case AO2_CONTAINER_ALLOC_OPT_DUPS_OBJ_REJECT:
					if (cur->common.obj == node->common.obj) {
						/* Reject inserting the same object */
						return AO2_CONTAINER_INSERT_NODE_REJECTED;
					}
					break;
				case AO2_CONTAINER_ALLOC_OPT_DUPS_REPLACE:
					SWAP(cur->common.obj, node->common.obj);
					ao2_t_ref(node, -1, NULL);
					return AO2_CONTAINER_INSERT_NODE_OBJ_REPLACED;
				}
			}
			AST_DLLIST_TRAVERSE_SAFE_END;
		}
		AST_DLLIST_INSERT_TAIL(&bucket->list, node, links);
	}
	return AO2_CONTAINER_INSERT_NODE_INSERTED;
}

/*!
 * \internal
 * \brief Find the first hash container node in a traversal.
 * \since 12.0.0
 *
 * \param self Container to operate upon.
 * \param flags search_flags to control traversing the container
 * \param arg Comparison callback arg parameter.
 * \param state Traversal state to restart hash container traversal.
 *
 * \retval node-ptr of found node (Reffed).
 * \retval NULL when no node found.
 */
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)
{
	struct hash_bucket_node *node;
	int bucket_cur;
	int cmp;

	memset(state, 0, sizeof(*state));
	state->arg = arg;
	state->flags = flags;

	/* Determine traversal order. */
	switch (flags & OBJ_ORDER_MASK) {
	case OBJ_ORDER_POST:
	case OBJ_ORDER_DESCENDING:
		state->descending = 1;
		break;
	case OBJ_ORDER_PRE:
	case OBJ_ORDER_ASCENDING:
	default:
		break;
	}

	/*
	 * If lookup by pointer or search key, run the hash and optional
	 * sort functions.  Otherwise, traverse the whole container.
	 */
	switch (flags & OBJ_SEARCH_MASK) {
	case OBJ_SEARCH_OBJECT:
	case OBJ_SEARCH_KEY:
		/* we know hash can handle this case */
		bucket_cur = abs(self->hash_fn(arg, flags & OBJ_SEARCH_MASK)
				% self->n_buckets);
		state->sort_fn = self->common.sort_fn;
		break;
	case OBJ_SEARCH_PARTIAL_KEY:
		/* scan all buckets for partial key matches */
		bucket_cur = -1;
		state->sort_fn = self->common.sort_fn;
		break;
	default:
		/* don't know, let's scan all buckets */
		bucket_cur = -1;
		state->sort_fn = NULL;
		break;
	}

	if (state->descending) {
		/*
		 * Determine the search boundaries of a descending traversal.
		 *
		 * bucket_cur downto state->bucket_last
		 */
		if (bucket_cur < 0) {
			bucket_cur = self->n_buckets - 1;
			state->bucket_last = 0;
		} else {
			state->bucket_last = bucket_cur;
		}
		state->bucket_start = bucket_cur;

		/* For each bucket */
		for (; state->bucket_last <= bucket_cur; --bucket_cur) {
			/* For each node in the bucket. */
			for (node = AST_DLLIST_LAST(&self->buckets[bucket_cur].list);
				node;
				node = AST_DLLIST_PREV(node, links)) {
				if (!node->common.obj) {
					/* Node is empty */
					continue;
				}

				if (state->sort_fn) {
					/* Filter node through the sort_fn */
					cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
					if (cmp > 0) {
						continue;
					}
					if (cmp < 0) {
						/* No more nodes in this bucket are possible to match. */
						break;
					}
				}

				/* We have the first traversal node */
				ao2_t_ref(node, +1, NULL);
				return node;
			}
		}
	} else {
		/*
		 * Determine the search boundaries of an ascending traversal.
		 *
		 * bucket_cur to state->bucket_last-1
		 */
		if (bucket_cur < 0) {
			bucket_cur = 0;
			state->bucket_last = self->n_buckets;
		} else {
			state->bucket_last = bucket_cur + 1;
		}
		state->bucket_start = bucket_cur;

		/* For each bucket */
		for (; bucket_cur < state->bucket_last; ++bucket_cur) {
			/* For each node in the bucket. */
			for (node = AST_DLLIST_FIRST(&self->buckets[bucket_cur].list);
				node;
				node = AST_DLLIST_NEXT(node, links)) {
				if (!node->common.obj) {
					/* Node is empty */
					continue;
				}

				if (state->sort_fn) {
					/* Filter node through the sort_fn */
					cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
					if (cmp < 0) {
						continue;
					}
					if (cmp > 0) {
						/* No more nodes in this bucket are possible to match. */
						break;
					}
				}

				/* We have the first traversal node */
				ao2_t_ref(node, +1, NULL);
				return node;
			}
		}
	}

	return NULL;
}

/*!
 * \internal
 * \brief Find the next hash container node in a traversal.
 * \since 12.0.0
 *
 * \param self Container to operate upon.
 * \param state Traversal state to restart hash container traversal.
 * \param prev Previous node returned by the traversal search functions.
 *    The ref ownership is passed back to this function.
 *
 * \retval node-ptr of found node (Reffed).
 * \retval NULL when no node found.
 */
static struct hash_bucket_node *hash_ao2_find_next(struct ao2_container_hash *self, struct hash_traversal_state *state, struct hash_bucket_node *prev)
{
	struct hash_bucket_node *node;
	void *arg;
	enum search_flags flags;
	int bucket_cur;
	int cmp;

	arg = state->arg;
	flags = state->flags;
	bucket_cur = prev->my_bucket;
	node = prev;

	/*
	 * This function is structured the same as hash_ao2_find_first()
	 * intentionally.  We are resuming the search loops from
	 * hash_ao2_find_first() in order to find the next node.  The
	 * search loops must be resumed where hash_ao2_find_first()
	 * returned with the first node.
	 */
	if (state->descending) {
		goto hash_descending_resume;

		/* For each bucket */
		for (; state->bucket_last <= bucket_cur; --bucket_cur) {
			/* For each node in the bucket. */
			for (node = AST_DLLIST_LAST(&self->buckets[bucket_cur].list);
				node;
				node = AST_DLLIST_PREV(node, links)) {
				if (!node->common.obj) {
					/* Node is empty */
					continue;
				}

				if (state->sort_fn) {
					/* Filter node through the sort_fn */
					cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
					if (cmp > 0) {
						continue;
					}
					if (cmp < 0) {
						/* No more nodes in this bucket are possible to match. */
						break;
					}
				}

				/* We have the next traversal node */
				ao2_t_ref(node, +1, NULL);

				/*
				 * Dereferencing the prev node may result in our next node
				 * object being removed by another thread.  This could happen if
				 * the container uses RW locks and the container was read
				 * locked.
				 */
				ao2_t_ref(prev, -1, NULL);
				if (node->common.obj) {
					return node;
				}
				prev = node;

hash_descending_resume:;
			}
		}
	} else {
		goto hash_ascending_resume;

		/* For each bucket */
		for (; bucket_cur < state->bucket_last; ++bucket_cur) {
			/* For each node in the bucket. */
			for (node = AST_DLLIST_FIRST(&self->buckets[bucket_cur].list);
				node;
				node = AST_DLLIST_NEXT(node, links)) {
				if (!node->common.obj) {
					/* Node is empty */
					continue;
				}

				if (state->sort_fn) {
					/* Filter node through the sort_fn */
					cmp = state->sort_fn(node->common.obj, arg, flags & OBJ_SEARCH_MASK);
					if (cmp < 0) {
						continue;
					}
					if (cmp > 0) {
						/* No more nodes in this bucket are possible to match. */
						break;
					}
				}

				/* We have the next traversal node */
				ao2_t_ref(node, +1, NULL);

				/*
				 * Dereferencing the prev node may result in our next node
				 * object being removed by another thread.  This could happen if
				 * the container uses RW locks and the container was read
				 * locked.
				 */
				ao2_t_ref(prev, -1, NULL);
				if (node->common.obj) {
					return node;
				}
				prev = node;

hash_ascending_resume:;
			}
		}
	}

	/* No more nodes in the container left to traverse. */
	ao2_t_ref(prev, -1, NULL);
	return NULL;
}

/*!
 * \internal
 * \brief Find the next non-empty iteration node in the container.
 * \since 12.0.0
 *
 * \param self Container to operate upon.
 * \param node Previous node returned by the iterator.
 * \param flags search_flags to control iterating the container.
 *   Only AO2_ITERATOR_DESCENDING is useful by the method.
 *
 * \note The container is already locked.
 *
 * \retval node on success.
 * \retval NULL on error or no more nodes in the container.
 */
static struct hash_bucket_node *hash_ao2_iterator_next(struct ao2_container_hash *self, struct hash_bucket_node *node, enum ao2_iterator_flags flags)
{
	int cur_bucket;

	if (flags & AO2_ITERATOR_DESCENDING) {
		if (node) {
			cur_bucket = node->my_bucket;

			/* Find next non-empty node. */
			for (;;) {
				node = AST_DLLIST_PREV(node, links);
				if (!node) {
					break;
				}
				if (node->common.obj) {
					/* Found a non-empty node. */
					return node;
				}
			}
		} else {
			/* Find first non-empty node. */
			cur_bucket = self->n_buckets;
		}

		/* Find a non-empty node in the remaining buckets */
		while (0 <= --cur_bucket) {
			node = AST_DLLIST_LAST(&self->buckets[cur_bucket].list);
			while (node) {
				if (node->common.obj) {
					/* Found a non-empty node. */
					return node;
				}
				node = AST_DLLIST_PREV(node, links);
			}
		}
	} else {
		if (node) {
			cur_bucket = node->my_bucket;

			/* Find next non-empty node. */
			for (;;) {
				node = AST_DLLIST_NEXT(node, links);
				if (!node) {
					break;
				}
				if (node->common.obj) {
					/* Found a non-empty node. */
					return node;
				}
			}
		} else {
			/* Find first non-empty node. */
			cur_bucket = -1;
		}

		/* Find a non-empty node in the remaining buckets */
		while (++cur_bucket < self->n_buckets) {
			node = AST_DLLIST_FIRST(&self->buckets[cur_bucket].list);
			while (node) {
				if (node->common.obj) {
					/* Found a non-empty node. */
					return node;
				}
				node = AST_DLLIST_NEXT(node, links);
			}
		}
	}

	/* No more nodes to visit in the container. */
	return NULL;
}

#if defined(AO2_DEBUG)
/*!
 * \internal
 * \brief Increment the hash container linked object statistic.
 * \since 12.0.0
 *
 * \param hash Container to operate upon.
 * \param hash_node Container node linking object to.
 *
 * \return Nothing
 */
static void hash_ao2_link_node_stat(struct ao2_container *hash, struct ao2_container_node *hash_node)
{
	struct ao2_container_hash *self = (struct ao2_container_hash *) hash;
	struct hash_bucket_node *node = (struct hash_bucket_node *) hash_node;
	int i = node->my_bucket;

	++self->buckets[i].elements;
	if (self->buckets[i].max_elements < self->buckets[i].elements) {
		self->buckets[i].max_elements = self->buckets[i].elements;
	}
}
#endif	/* defined(AO2_DEBUG) */

#if defined(AO2_DEBUG)
/*!
 * \internal
 * \brief Decrement the hash container linked object statistic.
 * \since 12.0.0
 *
 * \param hash Container to operate upon.
 * \param hash_node Container node unlinking object from.
 *
 * \return Nothing
 */
static void hash_ao2_unlink_node_stat(struct ao2_container *hash, struct ao2_container_node *hash_node)
{
	struct ao2_container_hash *self = (struct ao2_container_hash *) hash;
	struct hash_bucket_node *node = (struct hash_bucket_node *) hash_node;

	--self->buckets[node->my_bucket].elements;
}
#endif	/* defined(AO2_DEBUG) */

/*!
 * \internal
 *
 * \brief Destroy this container.
 * \since 12.0.0
 *
 * \param self Container to operate upon.
 *
 * \return Nothing
 */
static void hash_ao2_destroy(struct ao2_container_hash *self)
{
	int idx;

	/* Check that the container no longer has any nodes */
	for (idx = self->n_buckets; idx--;) {
		if (!AST_DLLIST_EMPTY(&self->buckets[idx].list)) {
			ast_log(LOG_ERROR, "Node ref leak.  Hash container still has nodes!\n");
			ast_assert(0);
			break;
		}
	}
}

#if defined(AO2_DEBUG)
/*!
 * \internal
 * \brief Display contents of the specified container.
 * \since 12.0.0
 *
 * \param self Container to dump.
 * \param where User data needed by prnt to determine where to put output.
 * \param prnt Print output callback function to use.
 * \param prnt_obj Callback function to print the given object's key. (NULL if not available)
 *
 * \return Nothing
 */
static void hash_ao2_dump(struct ao2_container_hash *self, void *where, ao2_prnt_fn *prnt, ao2_prnt_obj_fn *prnt_obj)
{
#define FORMAT  "%6s, %16s, %16s, %16s, %16s, %s\n"
#define FORMAT2 "%6d, %16p, %16p, %16p, %16p, "

	int bucket;
	int suppressed_buckets = 0;
	struct hash_bucket_node *node;

	prnt(where, "Number of buckets: %d\n\n", self->n_buckets);

	prnt(where, FORMAT, "Bucket", "Node", "Prev", "Next", "Obj", "Key");
	for (bucket = 0; bucket < self->n_buckets; ++bucket) {
		node = AST_DLLIST_FIRST(&self->buckets[bucket].list);
		if (node) {
			suppressed_buckets = 0;
			do {
				prnt(where, FORMAT2,
					bucket,
					node,
					AST_DLLIST_PREV(node, links),
					AST_DLLIST_NEXT(node, links),
					node->common.obj);
				if (node->common.obj && prnt_obj) {
					prnt_obj(node->common.obj, where, prnt);
				}
				prnt(where, "\n");

				node = AST_DLLIST_NEXT(node, links);
			} while (node);
		} else if (!suppressed_buckets) {
			suppressed_buckets = 1;
			prnt(where, "...\n");
		}
	}

#undef FORMAT
#undef FORMAT2
}
#endif	/* defined(AO2_DEBUG) */

#if defined(AO2_DEBUG)
/*!
 * \internal
 * \brief Display statistics of the specified container.
 * \since 12.0.0
 *
 * \param self Container to display statistics.
 * \param where User data needed by prnt to determine where to put output.
 * \param prnt Print output callback function to use.
 *
 * \note The container is already locked for reading.
 *
 * \return Nothing
 */
static void hash_ao2_stats(struct ao2_container_hash *self, void *where, ao2_prnt_fn *prnt)
{
#define FORMAT  "%10.10s %10.10s %10.10s\n"
#define FORMAT2 "%10d %10d %10d\n"

	int bucket;
	int suppressed_buckets = 0;

	prnt(where, "Number of buckets: %d\n\n", self->n_buckets);

	prnt(where, FORMAT, "Bucket", "Objects", "Max");
	for (bucket = 0; bucket < self->n_buckets; ++bucket) {
		if (self->buckets[bucket].max_elements) {
			suppressed_buckets = 0;
			prnt(where, FORMAT2, bucket, self->buckets[bucket].elements,
				self->buckets[bucket].max_elements);
		} else if (!suppressed_buckets) {
			suppressed_buckets = 1;
			prnt(where, "...\n");
		}
	}

#undef FORMAT
#undef FORMAT2
}
#endif	/* defined(AO2_DEBUG) */

#if defined(AO2_DEBUG)
/*!
 * \internal
 * \brief Perform an integrity check on the specified container.
 * \since 12.0.0
 *
 * \param self Container to check integrity.
 *
 * \note The container is already locked for reading.
 *
 * \retval 0 on success.
 * \retval -1 on error.
 */
static int hash_ao2_integrity(struct ao2_container_hash *self)
{
	int bucket_exp;
	int bucket;
	int count_obj;
	int count_total_obj;
	int count_total_node;
	void *obj_last;
	struct hash_bucket_node *node;
	struct hash_bucket_node *prev;
	struct hash_bucket_node *next;

	count_total_obj = 0;
	count_total_node = 0;

	/* For each bucket in the container. */
	for (bucket = 0; bucket < self->n_buckets; ++bucket) {
		if (!AST_DLLIST_FIRST(&self->buckets[bucket].list)
			&& !AST_DLLIST_LAST(&self->buckets[bucket].list)) {
			/* The bucket list is empty. */
			continue;
		}

		count_obj = 0;
		obj_last = NULL;

		/* Check bucket list links and nodes. */
		node = AST_DLLIST_LAST(&self->buckets[bucket].list);
		if (!node) {
			ast_log(LOG_ERROR, "Bucket %d list tail is NULL when it should not be!\n",
				bucket);
			return -1;
		}
		if (AST_DLLIST_NEXT(node, links)) {
			ast_log(LOG_ERROR, "Bucket %d list tail node is not the last node!\n",
				bucket);
			return -1;
		}
		node = AST_DLLIST_FIRST(&self->buckets[bucket].list);
		if (!node) {
			ast_log(LOG_ERROR, "Bucket %d list head is NULL when it should not be!\n",
				bucket);
			return -1;
		}
		if (AST_DLLIST_PREV(node, links)) {
			ast_log(LOG_ERROR, "Bucket %d list head node is not the first node!\n",
				bucket);
			return -1;
		}
		for (; node; node = next) {
			/* Check backward link. */
			prev = AST_DLLIST_PREV(node, links);
			if (prev) {
				if (prev == node) {
					ast_log(LOG_ERROR, "Bucket %d list node's prev pointer points to itself!\n",
						bucket);
					return -1;
				}
				if (node != AST_DLLIST_NEXT(prev, links)) {
					ast_log(LOG_ERROR, "Bucket %d list node's prev node does not link back!\n",
						bucket);
					return -1;
				}
			} else if (node != AST_DLLIST_FIRST(&self->buckets[bucket].list)) {
				ast_log(LOG_ERROR, "Bucket %d backward list chain is broken!\n",
					bucket);
				return -1;
			}

			/* Check forward link. */
			next = AST_DLLIST_NEXT(node, links);
			if (next) {
				if (next == node) {
					ast_log(LOG_ERROR, "Bucket %d list node's next pointer points to itself!\n",
						bucket);
					return -1;
				}
				if (node != AST_DLLIST_PREV(next, links)) {
					ast_log(LOG_ERROR, "Bucket %d list node's next node does not link back!\n",
						bucket);
					return -1;
				}
			} else if (node != AST_DLLIST_LAST(&self->buckets[bucket].list)) {
				ast_log(LOG_ERROR, "Bucket %d forward list chain is broken!\n",
					bucket);
				return -1;
			}

			if (bucket != node->my_bucket) {
				ast_log(LOG_ERROR, "Bucket %d node claims to be in bucket %d!\n",
					bucket, node->my_bucket);
				return -1;
			}

			++count_total_node;
			if (!node->common.obj) {
				/* Node is empty. */
				continue;
			}
			++count_obj;

			/* Check container hash key for expected bucket. */
			bucket_exp = abs(self->hash_fn(node->common.obj, OBJ_SEARCH_OBJECT)
					% self->n_buckets);
			if (bucket != bucket_exp) {
				ast_log(LOG_ERROR, "Bucket %d node hashes to bucket %d!\n",
					bucket, bucket_exp);
				return -1;
			}

			/* Check sort if configured. */
			if (self->common.sort_fn) {
				if (obj_last
					&& self->common.sort_fn(obj_last, node->common.obj, OBJ_SEARCH_OBJECT) > 0) {
					ast_log(LOG_ERROR, "Bucket %d nodes out of sorted order!\n",
						bucket);
					return -1;
				}
				obj_last = node->common.obj;
			}
		}

		/* Check bucket obj count statistic. */
		if (count_obj != self->buckets[bucket].elements) {
			ast_log(LOG_ERROR, "Bucket %d object count of %d does not match stat of %d!\n",
				bucket, count_obj, self->buckets[bucket].elements);
			return -1;
		}

		/* Accumulate found object counts. */
		count_total_obj += count_obj;
	}

	/* Check total obj count. */
	if (count_total_obj != ao2_container_count(&self->common)) {
		ast_log(LOG_ERROR,
			"Total object count of %d does not match ao2_container_count() of %d!\n",
			count_total_obj, ao2_container_count(&self->common));
		return -1;
	}

	/* Check total node count. */
	if (count_total_node != self->common.nodes) {
		ast_log(LOG_ERROR, "Total node count of %d does not match stat of %d!\n",
			count_total_node, self->common.nodes);
		return -1;
	}

	return 0;
}
#endif	/* defined(AO2_DEBUG) */

/*! Hash container virtual method table. */
static const struct ao2_container_methods v_table_hash = {
	.alloc_empty_clone = (ao2_container_alloc_empty_clone_fn) hash_ao2_alloc_empty_clone,
	.new_node = (ao2_container_new_node_fn) hash_ao2_new_node,
	.insert = (ao2_container_insert_fn) hash_ao2_insert_node,
	.traverse_first = (ao2_container_find_first_fn) hash_ao2_find_first,
	.traverse_next = (ao2_container_find_next_fn) hash_ao2_find_next,
	.iterator_next = (ao2_iterator_next_fn) hash_ao2_iterator_next,
	.destroy = (ao2_container_destroy_fn) hash_ao2_destroy,
#if defined(AO2_DEBUG)
	.link_stat = hash_ao2_link_node_stat,
	.unlink_stat = hash_ao2_unlink_node_stat,
	.dump = (ao2_container_display) hash_ao2_dump,
	.stats = (ao2_container_statistics) hash_ao2_stats,
	.integrity = (ao2_container_integrity) hash_ao2_integrity,
#endif	/* defined(AO2_DEBUG) */
};

/*!
 * \brief always zero hash function
 *
 * it is convenient to have a hash function that always returns 0.
 * This is basically used when we want to have a container that is
 * a simple linked list.
 *
 * \returns 0
 */
static int hash_zero(const void *user_obj, const int flags)
{
	return 0;
}

/*!
 * \brief Initialize a hash container with the desired number of buckets.
 *
 * \param self Container to initialize.
 * \param options Container behaviour options (See enum ao2_container_opts)
 * \param n_buckets Number of buckets for hash
 * \param hash_fn Pointer to a function computing a hash value.
 * \param sort_fn Pointer to a sort function.
 * \param cmp_fn Pointer to a compare function used by ao2_find.
 *
 * \return A pointer to a struct container.
 */
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)
{
	if (!self) {
		return NULL;
	}

	self->common.v_table = &v_table_hash;
	self->common.sort_fn = sort_fn;
	self->common.cmp_fn = cmp_fn;
	self->common.options = options;
	self->hash_fn = hash_fn ? hash_fn : hash_zero;
	self->n_buckets = n_buckets;

#ifdef AO2_DEBUG
	ast_atomic_fetchadd_int(&ao2.total_containers, 1);
#endif	/* defined(AO2_DEBUG) */

	return (struct ao2_container *) self;
}

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)
{
	unsigned int num_buckets;
	size_t container_size;
	struct ao2_container_hash *self;

	num_buckets = hash_fn ? n_buckets : 1;
	container_size = sizeof(struct ao2_container_hash) + num_buckets * sizeof(struct hash_bucket);

	self = __ao2_alloc(container_size, container_destruct, ao2_options,
		tag ?: __PRETTY_FUNCTION__, file, line, func);
	return hash_ao2_container_init(self, container_options, num_buckets, hash_fn,
		sort_fn, cmp_fn);
}

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)
{
	return __ao2_container_alloc_hash(ao2_options, container_options, 1, NULL,
		sort_fn, cmp_fn, tag, file, line, func);
}