Asterisk - The Open Source Telephony Project GIT-master-5782b03
hashtab.c
Go to the documentation of this file.
1/*
2 * Asterisk -- An open source telephony toolkit.
3 *
4 * Copyright (C) 2007, Digium, Inc.
5 *
6 * Steve Murphy <murf@digium.com>
7 *
8 * See http://www.asterisk.org for more information about
9 * the Asterisk project. Please do not directly contact
10 * any of the maintainers of this project for assistance;
11 * the project provides a web site, mailing lists and IRC
12 * channels for your use.
13 *
14 * This program is free software, distributed under the terms of
15 * the GNU General Public License Version 2. See the LICENSE file
16 * at the top of the source tree.
17 */
18/*! \file
19 *
20 * \brief code to implement generic hash tables
21 *
22 * \author Steve Murphy <murf@digium.com>
23 */
24
25/*** MODULEINFO
26 <support_level>core</support_level>
27 ***/
28
29#include "asterisk.h"
30
31#include <ctype.h>
32
33#include "asterisk/lock.h"
34#include "asterisk/frame.h"
35#include "asterisk/channel.h"
36#include "asterisk/cli.h"
37#include "asterisk/term.h"
38#include "asterisk/utils.h"
41#include "asterisk/hashtab.h"
42
43
44static void _ast_hashtab_resize(struct ast_hashtab *tab, const char *file, int lineno, const char *func);
45#define ast_hashtab_resize(tab) \
46 _ast_hashtab_resize(tab, __FILE__, __LINE__, __PRETTY_FUNCTION__)
47
48static void *ast_hashtab_lookup_internal(struct ast_hashtab *tab, const void *obj, unsigned int h);
49
50/* some standard, default routines for general use */
51
52int ast_hashtab_compare_strings(const void *a, const void *b)
53{
54 return strcmp(a, b);
55}
56
57int ast_hashtab_compare_strings_nocase(const void *a, const void *b)
58{
59 return strcasecmp(a, b);
60}
61
62int ast_hashtab_compare_ints(const void *a, const void *b)
63{
64 int ai = *((int *) a);
65 int bi = *((int *) b);
66
67 if (ai < bi)
68 return -1;
69
70 return !(ai == bi);
71}
72
73int ast_hashtab_compare_shorts(const void *a, const void *b)
74{
75 short as = *((short *) a);
76 short bs = *((short *) b);
77
78 if (as < bs)
79 return -1;
80
81 return !(as == bs);
82}
83
85{
86 double loadfactor = (double) tab->hash_tab_elements / (double) tab->hash_tab_size;
87
88 return (loadfactor > 0.75);
89}
90
92{
93 return (tab->hash_tab_elements > tab->hash_tab_size); /* this is quicker than division */
94}
95
96int ast_hashtab_resize_none(struct ast_hashtab *tab) /* always return 0 -- no resizing */
97{
98 return 0;
99}
100
101int ast_is_prime(int num)
102{
103 int tnum, limit;
104
105 if (!(num & 0x1)) /* even number -- not prime */
106 return 0;
107
108 /* Loop through ODD numbers starting with 3 */
109
110 tnum = 3;
111 limit = num;
112 while (tnum < limit) {
113 if (!(num % tnum))
114 return 0;
115
116 /* really, we only need to check sqrt(num) numbers */
117 limit = num / tnum;
118
119 /* we only check odd numbers */
120 tnum = tnum + 2;
121 }
122
123 /* if we made it through the loop, the number is a prime */
124 return 1;
125}
126
128{
129 int i = (tab->hash_tab_size << 1); /* multiply by two */
130
131 while (!ast_is_prime(i))
132 i++;
133
134 return i;
135}
136
138{
139 int x = (tab->hash_tab_size << 1);
140 int i = (tab->hash_tab_size + x);
141
142 while (!ast_is_prime(i))
143 i++;
144
145 return i;
146}
147
148int ast_hashtab_newsize_none(struct ast_hashtab *tab) /* always return current size -- no resizing */
149{
150 return tab->hash_tab_size;
151}
152
153unsigned int ast_hashtab_hash_string(const void *obj)
154{
155 unsigned char *str = (unsigned char *) obj;
156 unsigned int total;
157
158 for (total = 0; *str; str++) {
159 unsigned int tmp = total;
160 total <<= 1; /* multiply by 2 */
161 total += tmp; /* multiply by 3 */
162 total <<= 2; /* multiply by 12 */
163 total += tmp; /* multiply by 13 */
164
165 total += ((unsigned int)(*str));
166 }
167 return total;
168}
169
170unsigned int ast_hashtab_hash_string_sax(const void *obj) /* from Josh */
171{
172 const unsigned char *str = obj;
173 unsigned int total = 0, c = 0;
174
175 while ((c = *str++))
176 total ^= (total << 5) + (total >> 2) + (total << 10) + c;
177
178 return total;
179}
180
181unsigned int ast_hashtab_hash_string_nocase(const void *obj)
182{
183 const unsigned char *str = obj;
184 unsigned int total;
185
186 for (total = 0; *str; str++) {
187 unsigned int tmp = total;
188 unsigned int charval = toupper(*str);
189
190 /* hopefully, the following is faster than multiplication by 7 */
191 /* why do I go to this bother? A good compiler will do this
192 anyway, if I say total *= 13 */
193 /* BTW, tried *= 7, and it doesn't do as well in spreading things around! */
194 total <<= 1; /* multiply by 2 */
195 total += tmp; /* multiply by 3 */
196 total <<= 2; /* multiply by 12 */
197 total += tmp; /* multiply by 13 */
198
199 total += (charval);
200 }
201
202 return total;
203}
204
205unsigned int ast_hashtab_hash_int(const int x)
206{
207 return x;
208}
209
210unsigned int ast_hashtab_hash_short(const short x)
211{
212 /* hmmmm.... modulus is best < 65535 !! */
213 return x;
214}
215
216struct ast_hashtab *_ast_hashtab_create(int initial_buckets,
217 int (*compare)(const void *a, const void *b),
218 int (*resize)(struct ast_hashtab *),
219 int (*newsize)(struct ast_hashtab *tab),
220 unsigned int (*hash)(const void *obj),
221 int do_locking,
222 const char *file, int lineno, const char *function
223)
224{
225 struct ast_hashtab *ht;
226
227 ht = __ast_calloc(1, sizeof(*ht), file, lineno, function);
228 if (!ht) {
229 return NULL;
230 }
231
232 while (!ast_is_prime(initial_buckets)) /* make sure this is prime */
233 initial_buckets++;
234
235 ht->array = __ast_calloc(initial_buckets, sizeof(*(ht->array)),
236 file, lineno, function);
237 if (!ht->array) {
238 ast_free(ht);
239 return NULL;
240 }
241
242 ht->hash_tab_size = initial_buckets;
243 ht->compare = compare;
244 ht->resize = resize;
245 ht->newsize = newsize;
246 ht->hash = hash;
248
249 if (do_locking)
250 ast_rwlock_init(&ht->lock);
251
252 if (!ht->resize)
254
255 if (!ht->newsize)
257
258 return ht;
259}
260
261struct ast_hashtab *_ast_hashtab_dup(struct ast_hashtab *tab, void *(*obj_dup_func)(const void *obj), const char *file, int lineno, const char *func)
262{
263 struct ast_hashtab *ht;
264 unsigned int i;
265
266 ht = __ast_calloc(1, sizeof(*ht), file, lineno, func);
267 if (!ht) {
268 return NULL;
269 }
270
271 ht->array = __ast_calloc(tab->hash_tab_size, sizeof(*(ht->array)),
272 file, lineno, func);
273 if (!ht->array) {
274 ast_free(ht);
275 return NULL;
276 }
277
278 ht->hash_tab_size = tab->hash_tab_size;
279 ht->compare = tab->compare;
280 ht->resize = tab->resize;
281 ht->newsize = tab->newsize;
282 ht->hash = tab->hash;
283 ht->do_locking = tab->do_locking;
284
285 if (ht->do_locking)
286 ast_rwlock_init(&ht->lock);
287
288 /* now, dup the objects in the buckets and get them into the table */
289 /* the fast way is to use the existing array index, and not have to hash
290 the objects again */
291 for (i = 0; i < ht->hash_tab_size; i++) {
292 struct ast_hashtab_bucket *b = tab->array[i];
293 while (b) {
294 void *newobj = (*obj_dup_func)(b->object);
295 if (newobj) {
296 _ast_hashtab_insert_immediate_bucket(ht, newobj, i, file, lineno, func);
297 }
298 b = b->next;
299 }
300 }
301
302 return ht;
303}
304
305static void tlist_del_item(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
306{
307 /* item had better be in the list! or suffer the weirdness that occurs, later! */
308 if (*head == item) { /* first item in the list */
309 *head = item->tnext;
310 if (item->tnext)
311 item->tnext->tprev = NULL;
312 } else {
313 /* short circuit stuff */
314 item->tprev->tnext = item->tnext;
315 if (item->tnext)
316 item->tnext->tprev = item->tprev;
317 }
318}
319
320static void tlist_add_head(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
321{
322 if (*head) {
323 item->tnext = *head;
324 item->tprev = NULL;
325 (*head)->tprev = item;
326 *head = item;
327 } else {
328 /* the list is empty */
329 *head = item;
330 item->tprev = NULL;
331 item->tnext = NULL;
332 }
333}
334
335/* user-controlled hashtab locking. Create a hashtab without locking, then call the
336 following locking routines yourself to lock the table between threads. */
337
339{
340 ast_rwlock_wrlock(&tab->lock);
341}
342
344{
345 ast_rwlock_rdlock(&tab->lock);
346}
347
349{
350 ast_rwlock_init(&tab->lock);
351}
352
354{
356}
357
359{
360 ast_rwlock_unlock(&tab->lock);
361}
362
363void ast_hashtab_destroy(struct ast_hashtab *tab, void (*objdestroyfunc)(void *obj))
364{
365 /* this func will free the hash table and all its memory. It
366 doesn't touch the objects stored in it */
367 if (tab) {
368
369 if (tab->do_locking)
370 ast_rwlock_wrlock(&tab->lock);
371
372 if (tab->array) {
373 /* go thru and destroy the buckets */
374 struct ast_hashtab_bucket *t;
375 int i;
376
377 while (tab->tlist) {
378 t = tab->tlist;
379 if (t->object && objdestroyfunc) {
380 /* I cast this because I'm not going to MOD it, I'm going to DESTROY
381 * it.
382 */
383 (*objdestroyfunc)((void *) t->object);
384 }
385
386 tlist_del_item(&(tab->tlist), tab->tlist);
387 ast_free(t);
388 }
389
390 for (i = 0; i < tab->hash_tab_size; i++) {
391 /* Not totally necessary, but best to destroy old pointers */
392 tab->array[i] = NULL;
393 }
394 ast_free(tab->array);
395 }
396 if (tab->do_locking) {
397 ast_rwlock_unlock(&tab->lock);
399 }
400 ast_free(tab);
401 }
402}
403
404int _ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj, const char *file, int lineno, const char *func)
405{
406 unsigned int h;
407 int res=0;
408
409 if (!tab || !obj)
410 return res;
411
412 if (tab->do_locking)
413 ast_rwlock_wrlock(&tab->lock);
414
415 h = (*tab->hash)(obj) % tab->hash_tab_size;
416
417 res = _ast_hashtab_insert_immediate_bucket(tab, obj, h, file, lineno, func);
418
419 if (tab->do_locking)
420 ast_rwlock_unlock(&tab->lock);
421
422 return res;
423}
424
425int _ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h, const char *file, int lineno, const char *func)
426{
427 int c;
428 struct ast_hashtab_bucket *b;
429
430 if (!tab || !obj)
431 return 0;
432
433 for (c = 0, b = tab->array[h]; b; b= b->next)
434 c++;
435
436 if (c + 1 > tab->largest_bucket_size)
437 tab->largest_bucket_size = c + 1;
438
439 b = __ast_calloc(1, sizeof(*b), file, lineno, func);
440 if (!b) {
441 return 0;
442 }
443
444 b->object = obj;
445 b->next = tab->array[h];
446 tab->array[h] = b;
447
448 if (b->next)
449 b->next->prev = b;
450
451 tlist_add_head(&(tab->tlist), b);
452 tab->hash_tab_elements++;
453
454 if ((*tab->resize)(tab))
456
457 return 1;
458}
459
460int _ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj, const char *file, int lineno, const char *func)
461{
462 /* check to see if the element is already there; insert only if
463 it is not there. */
464 /* will force a resize if the resize func returns 1 */
465 /* returns 1 on success, 0 if there's a problem, or it's already there. */
466 unsigned int bucket = 0;
467
468 if (tab->do_locking)
469 ast_rwlock_wrlock(&tab->lock);
470
471 if (!ast_hashtab_lookup_bucket(tab, obj, &bucket)) {
472 int ret2 = _ast_hashtab_insert_immediate_bucket(tab, obj, bucket, file, lineno, func);
473
474 if (tab->do_locking)
475 ast_rwlock_unlock(&tab->lock);
476
477 return ret2;
478 }
479
480 if (tab->do_locking)
481 ast_rwlock_unlock(&tab->lock);
482
483 return 0;
484}
485
486void *ast_hashtab_lookup(struct ast_hashtab *tab, const void *obj)
487{
488 /* lookup this object in the hash table. return a ptr if found, or NULL if not */
489 unsigned int h;
490 void *ret;
491
492 if (!tab || !obj)
493 return 0;
494
495 if (tab->do_locking)
496 ast_rwlock_rdlock(&tab->lock);
497
498 h = (*tab->hash)(obj) % tab->hash_tab_size;
499
500 ret = ast_hashtab_lookup_internal(tab,obj,h);
501
502 if (tab->do_locking)
503 ast_rwlock_unlock(&tab->lock);
504
505 return ret;
506}
507
508
509void *ast_hashtab_lookup_with_hash(struct ast_hashtab *tab, const void *obj, unsigned int hashval)
510{
511 /* lookup this object in the hash table. return a ptr if found, or NULL if not */
512 unsigned int h;
513 void *ret;
514
515 if (!tab || !obj)
516 return 0;
517
518 if (tab->do_locking)
519 ast_rwlock_rdlock(&tab->lock);
520
521 h = hashval % tab->hash_tab_size;
522
523 ret = ast_hashtab_lookup_internal(tab,obj,h);
524
525 if (tab->do_locking)
526 ast_rwlock_unlock(&tab->lock);
527
528 return ret;
529}
530
531void *ast_hashtab_lookup_bucket(struct ast_hashtab *tab, const void *obj, unsigned int *bucket)
532{
533 /* lookup this object in the hash table. return a ptr if found, or NULL if not */
534 unsigned int h;
535 void *ret;
536
537 if (!tab || !obj)
538 return 0;
539
540 h = (*tab->hash)(obj) % tab->hash_tab_size;
541
542 ret = ast_hashtab_lookup_internal(tab,obj,h);
543
544 *bucket = h;
545
546 return ret;
547}
548
549static void *ast_hashtab_lookup_internal(struct ast_hashtab *tab, const void *obj, unsigned int h)
550{
551 struct ast_hashtab_bucket *b;
552
553 for (b = tab->array[h]; b; b = b->next) {
554 if (!(*tab->compare)(obj,b->object)) {
555 /* I can't touch obj in this func, but the outside world is welcome to */
556 return (void*) b->object;
557 }
558 }
559
560 return NULL;
561}
562
563void ast_hashtab_get_stats(struct ast_hashtab *tab, int *biggest_bucket_size, int *resize_count, int *num_objects, int *num_buckets)
564{
565 /* returns key stats for the table */
566 if (tab->do_locking)
567 ast_rwlock_rdlock(&tab->lock);
568 *biggest_bucket_size = tab->largest_bucket_size;
569 *resize_count = tab->resize_count;
570 *num_objects = tab->hash_tab_elements;
571 *num_buckets = tab->hash_tab_size;
572 if (tab->do_locking)
573 ast_rwlock_unlock(&tab->lock);
574}
575
576/* this function returns the number of elements stored in the hashtab */
578{
579 return tab->hash_tab_elements;
580}
581
582/* this function returns the size of the bucket array in the hashtab */
584{
585 return tab->hash_tab_size;
586}
587
588/* the insert operation calls this, and is wrlock'd when it does. */
589/* if you want to call it, you should set the wrlock yourself */
590
591static void _ast_hashtab_resize(struct ast_hashtab *tab, const char *file, int lineno, const char *func)
592{
593 /* this function is called either internally, when the resize func returns 1, or
594 externally by the user to force a resize of the hash table */
595 int newsize = (*tab->newsize)(tab), i, c;
596 unsigned int h;
597 struct ast_hashtab_bucket *b,*bn;
598
599 /* Since we keep a DLL of all the buckets in tlist,
600 all we have to do is free the array, malloc a new one,
601 and then go thru the tlist array and reassign them into
602 the bucket arrayj.
603 */
604 for (i = 0; i < tab->hash_tab_size; i++) { /* don't absolutely have to do this, but
605 why leave ptrs laying around */
606 tab->array[i] = 0; /* erase old ptrs */
607 }
608 ast_free(tab->array);
609 tab->array = __ast_calloc(newsize, sizeof(*(tab->array)), file, lineno, func);
610 if (!tab->array) {
611 return;
612 }
613
614 /* now sort the buckets into their rightful new slots */
615 tab->resize_count++;
616 tab->hash_tab_size = newsize;
617 tab->largest_bucket_size = 0;
618
619 for (b = tab->tlist; b; b = bn) {
620 b->prev = 0;
621 bn = b->tnext;
622 h = (*tab->hash)(b->object) % tab->hash_tab_size;
623 b->next = tab->array[h];
624 if (b->next)
625 b->next->prev = b;
626 tab->array[h] = b;
627 }
628 /* recalc the largest bucket size */
629 for (i = 0; i < tab->hash_tab_size; i++) {
630 for (c = 0, b = tab->array[i]; b; b = b->next)
631 c++;
632 if (c > tab->largest_bucket_size)
633 tab->largest_bucket_size = c;
634 }
635}
636
637struct ast_hashtab_iter *_ast_hashtab_start_traversal(struct ast_hashtab *tab, const char *file, int lineno, const char *func)
638{
639 /* returns an iterator */
640 struct ast_hashtab_iter *it;
641
642 it = __ast_calloc(1, sizeof(*it), file, lineno, func);
643 if (!it) {
644 return NULL;
645 }
646
647 it->next = tab->tlist;
648 it->tab = tab;
649 if (tab->do_locking)
651
652 return it;
653}
654
655/* use this function to get a write lock */
656struct ast_hashtab_iter *_ast_hashtab_start_write_traversal(struct ast_hashtab *tab, const char *file, int lineno, const char *func)
657{
658 /* returns an iterator */
659 struct ast_hashtab_iter *it;
660
661 it = __ast_calloc(1, sizeof(*it), file, lineno, func);
662 if (!it) {
663 return NULL;
664 }
665
666 it->next = tab->tlist;
667 it->tab = tab;
668 if (tab->do_locking)
670
671 return it;
672}
673
675{
676 if (!it)
677 return;
678 if (it->tab->do_locking)
680 ast_free(it);
681}
682
684{
685 /* returns the next object in the list, advances iter one step */
687
688 if (it && it->next) { /* there's a next in the bucket list */
689 retval = it->next;
690 it->next = retval->tnext;
691 return (void *) retval->object;
692 }
693
694 return NULL;
695}
696
698{
699 const void *obj2;
700
701 if (b->prev)
702 b->prev->next = b->next;
703 else
704 tab->array[h] = b->next;
705
706 if (b->next)
707 b->next->prev = b->prev;
708
709 tlist_del_item(&(tab->tlist), b);
710
711 obj2 = b->object;
712 b->object = b->next = (void*)2;
713 ast_free(b); /* free up the hashbucket */
714 tab->hash_tab_elements--;
715#ifdef DEBUG
716 {
717 int c2;
718 struct ast_hashtab_bucket *b2;
719 /* do a little checking */
720 for (c2 = 0, b2 = tab->tlist; b2; b2 = b2->tnext) {
721 c2++;
722 }
723 if (c2 != tab->hash_tab_elements) {
724 printf("Hey! we didn't delete right! there are %d elements in the list, and we expected %d\n",
725 c2, tab->hash_tab_elements);
726 }
727 for (c2 = 0, b2 = tab->tlist; b2; b2 = b2->tnext) {
728 unsigned int obj3 = (unsigned long) obj2;
729 unsigned int b3 = (unsigned long) b;
730 if (b2->object == obj2)
731 printf("Hey-- you've still got a bucket pointing at ht_element %x\n", obj3);
732 if (b2->next == b)
733 printf("Hey-- you've still got a bucket with next ptr pointing to deleted bucket %x\n", b3);
734 if (b2->prev == b)
735 printf("Hey-- you've still got a bucket with prev ptr pointing to deleted bucket %x\n", b3);
736 if (b2->tprev == b)
737 printf("Hey-- you've still got a bucket with tprev ptr pointing to deleted bucket %x\n", b3);
738 if (b2->tnext == b)
739 printf("Hey-- you've still got a bucket with tnext ptr pointing to deleted bucket %x\n", b3);
740 }
741 }
742#endif
743 return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
744}
745
747{
748 /* looks up the object; removes the corresponding bucket */
749 const void *obj2;
750
751 if (!tab || !obj)
752 return 0;
753
754 if (tab->do_locking)
755 ast_rwlock_wrlock(&tab->lock);
756
758
759 if (tab->do_locking)
760 ast_rwlock_unlock(&tab->lock);
761
762 return (void *)obj2;
763}
764
766{
767 /* looks up the object; removes the corresponding bucket */
768 unsigned int h;
769 struct ast_hashtab_bucket *b;
770
771 if (!tab || !obj)
772 return 0;
773
774 h = (*tab->hash)(obj) % tab->hash_tab_size;
775 for (b = tab->array[h]; b; b = b->next) {
776
777 if (!(*tab->compare)(obj, b->object)) {
778 const void *obj2;
779
781
782 return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
783 }
784 }
785
786 return 0;
787}
788
789void *ast_hashtab_remove_this_object(struct ast_hashtab *tab, void *obj)
790{
791 /* looks up the object by hash and then comparing pts in bucket list instead of
792 calling the compare routine; removes the bucket -- a slightly cheaper operation */
793 /* looks up the object; removes the corresponding bucket */
794 const void *obj2;
795
796 if (!tab || !obj)
797 return 0;
798
799 if (tab->do_locking)
800 ast_rwlock_wrlock(&tab->lock);
801
803
804 if (tab->do_locking)
805 ast_rwlock_unlock(&tab->lock);
806
807 return (void *)obj2;
808}
809
811{
812 /* looks up the object by hash and then comparing pts in bucket list instead of
813 calling the compare routine; removes the bucket -- a slightly cheaper operation */
814 /* looks up the object; removes the corresponding bucket */
815 unsigned int h;
816 struct ast_hashtab_bucket *b;
817
818 if (!tab || !obj)
819 return 0;
820
821 h = (*tab->hash)(obj) % tab->hash_tab_size;
822 for (b = tab->array[h]; b; b = b->next) {
823
824 if (obj == b->object) {
825 const void *obj2;
827
828 return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
829 }
830 }
831
832 return 0;
833}
static int compare(const char *text, const char *template)
const char * str
Definition: app_jack.c:147
Asterisk main include file. File version handling, generic pbx functions.
#define ast_free(a)
Definition: astmm.h:180
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func) attribute_malloc
Definition: astmm.c:1603
static int tmp()
Definition: bt_open.c:389
General Asterisk PBX channel definitions.
Standard Command Line Interface.
char * bs
Definition: eagi_proxy.c:73
void ast_hashtab_unlock(struct ast_hashtab *tab)
release a read- or write- lock.
Definition: hashtab.c:358
struct ast_hashtab * _ast_hashtab_create(int initial_buckets, int(*compare)(const void *a, const void *b), int(*resize)(struct ast_hashtab *), int(*newsize)(struct ast_hashtab *tab), unsigned int(*hash)(const void *obj), int do_locking, const char *file, int lineno, const char *function)
Definition: hashtab.c:216
unsigned int ast_hashtab_hash_string_nocase(const void *obj)
Hashes a string to a number ignoring case.
Definition: hashtab.c:181
static void tlist_add_head(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
Definition: hashtab.c:320
int _ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h, const char *file, int lineno, const char *func)
Definition: hashtab.c:425
void * ast_hashtab_remove_object_via_lookup_nolock(struct ast_hashtab *tab, void *obj)
Looks up the object, removes the corresponding bucket.
Definition: hashtab.c:765
static void * ast_hashtab_remove_object_internal(struct ast_hashtab *tab, struct ast_hashtab_bucket *b, int h)
Definition: hashtab.c:697
struct ast_hashtab_iter * _ast_hashtab_start_traversal(struct ast_hashtab *tab, const char *file, int lineno, const char *func)
Gives an iterator to hastable.
Definition: hashtab.c:637
void ast_hashtab_wrlock(struct ast_hashtab *tab)
Request a write-lock on the table.
Definition: hashtab.c:338
void ast_hashtab_destroylock(struct ast_hashtab *tab)
Call this before you destroy the table.
Definition: hashtab.c:353
void * ast_hashtab_remove_this_object(struct ast_hashtab *tab, void *obj)
Hash the object and then compare ptrs in bucket list instead of calling the compare routine,...
Definition: hashtab.c:789
void ast_hashtab_rdlock(struct ast_hashtab *tab)
Request a read-lock on the table – don't change anything!
Definition: hashtab.c:343
int ast_hashtab_compare_ints(const void *a, const void *b)
Compares two integers for equality.
Definition: hashtab.c:62
void ast_hashtab_destroy(struct ast_hashtab *tab, void(*objdestroyfunc)(void *obj))
This func will free the hash table and all its memory.
Definition: hashtab.c:363
int ast_hashtab_newsize_java(struct ast_hashtab *tab)
Create a prime number roughly 2x the current table size.
Definition: hashtab.c:127
int ast_is_prime(int num)
Determines if the specified number is prime.
Definition: hashtab.c:101
int _ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj, const char *file, int lineno, const char *func)
Check and insert new object only if it is not there.
Definition: hashtab.c:460
int ast_hashtab_compare_strings(const void *a, const void *b)
Compares two strings for equality.
Definition: hashtab.c:52
void * ast_hashtab_remove_this_object_nolock(struct ast_hashtab *tab, void *obj)
Hash the object and then compare ptrs in bucket list instead of calling the compare routine,...
Definition: hashtab.c:810
unsigned int ast_hashtab_hash_short(const short x)
Definition: hashtab.c:210
static void _ast_hashtab_resize(struct ast_hashtab *tab, const char *file, int lineno, const char *func)
Definition: hashtab.c:591
int ast_hashtab_compare_strings_nocase(const void *a, const void *b)
Compares two strings for equality, ignoring case.
Definition: hashtab.c:57
void ast_hashtab_end_traversal(struct ast_hashtab_iter *it)
end the traversal, free the iterator, unlock if necc.
Definition: hashtab.c:674
int ast_hashtab_newsize_none(struct ast_hashtab *tab)
always return current size – no resizing
Definition: hashtab.c:148
struct ast_hashtab * _ast_hashtab_dup(struct ast_hashtab *tab, void *(*obj_dup_func)(const void *obj), const char *file, int lineno, const char *func)
Return a copy of the hash table.
Definition: hashtab.c:261
static void * ast_hashtab_lookup_internal(struct ast_hashtab *tab, const void *obj, unsigned int h)
Definition: hashtab.c:549
unsigned int ast_hashtab_hash_string_sax(const void *obj)
Hashes a string to a number using a modified Shift-And-XOR algorithm.
Definition: hashtab.c:170
int ast_hashtab_size(struct ast_hashtab *tab)
Returns the number of elements stored in the hashtab.
Definition: hashtab.c:577
void * ast_hashtab_next(struct ast_hashtab_iter *it)
Gets the next object in the list, advances iter one step returns null on end of traversal.
Definition: hashtab.c:683
#define ast_hashtab_resize(tab)
Definition: hashtab.c:45
int ast_hashtab_newsize_tight(struct ast_hashtab *tab)
Definition: hashtab.c:137
static void tlist_del_item(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
Definition: hashtab.c:305
int ast_hashtab_resize_tight(struct ast_hashtab *tab)
Causes a resize whenever the number of elements stored in the table exceeds the number of buckets in ...
Definition: hashtab.c:91
void * ast_hashtab_lookup(struct ast_hashtab *tab, const void *obj)
Lookup this object in the hash table.
Definition: hashtab.c:486
int _ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj, const char *file, int lineno, const char *func)
Definition: hashtab.c:404
struct ast_hashtab_iter * _ast_hashtab_start_write_traversal(struct ast_hashtab *tab, const char *file, int lineno, const char *func)
Gives an iterator to hastable.
Definition: hashtab.c:656
int ast_hashtab_compare_shorts(const void *a, const void *b)
Compares two shorts for equality.
Definition: hashtab.c:73
void ast_hashtab_get_stats(struct ast_hashtab *tab, int *biggest_bucket_size, int *resize_count, int *num_objects, int *num_buckets)
Returns key stats for the table.
Definition: hashtab.c:563
void * ast_hashtab_lookup_with_hash(struct ast_hashtab *tab, const void *obj, unsigned int hashval)
Use this if have the hash val for the object.
Definition: hashtab.c:509
int ast_hashtab_resize_java(struct ast_hashtab *tab)
Determines if a table resize should occur using the Java algorithm (if the table load factor is 75% o...
Definition: hashtab.c:84
int ast_hashtab_capacity(struct ast_hashtab *tab)
Returns the size of the bucket array in the hashtab.
Definition: hashtab.c:583
void * ast_hashtab_remove_object_via_lookup(struct ast_hashtab *tab, void *obj)
Looks up the object, removes the corresponding bucket.
Definition: hashtab.c:746
void * ast_hashtab_lookup_bucket(struct ast_hashtab *tab, const void *obj, unsigned int *bucket)
Similar to ast_hashtab_lookup but sets h to the key hash value if the lookup fails.
Definition: hashtab.c:531
unsigned int ast_hashtab_hash_string(const void *obj)
Hashes a string to a number.
Definition: hashtab.c:153
void ast_hashtab_initlock(struct ast_hashtab *tab)
Call this after you create the table to init the lock.
Definition: hashtab.c:348
int ast_hashtab_resize_none(struct ast_hashtab *tab)
Effectively disables resizing by always returning 0, regardless of of load factor.
Definition: hashtab.c:96
unsigned int ast_hashtab_hash_int(const int x)
Definition: hashtab.c:205
Generic (perhaps overly so) hashtable implementation Hash Table support in Asterisk.
static ENTRY retval
Definition: hsearch.c:50
Asterisk internal frame definitions.
A set of macros to manage forward-linked lists.
Asterisk locking-related definitions:
#define ast_rwlock_wrlock(a)
Definition: lock.h:236
#define ast_rwlock_rdlock(a)
Definition: lock.h:235
#define ast_rwlock_init(rwlock)
wrapper for rwlock with tracking enabled
Definition: lock.h:224
#define ast_rwlock_destroy(rwlock)
Definition: lock.h:233
#define ast_rwlock_unlock(a)
Definition: lock.h:234
static int total
Definition: res_adsi.c:970
#define NULL
Definition: resample.c:96
struct ast_hashtab_bucket * next
Definition: hashtab.h:77
struct ast_hashtab_bucket * tprev
Definition: hashtab.h:80
const void * object
Definition: hashtab.h:76
struct ast_hashtab_bucket * tnext
Definition: hashtab.h:79
struct ast_hashtab_bucket * prev
Definition: hashtab.h:78
an iterator for traversing the buckets
Definition: hashtab.h:106
struct ast_hashtab_bucket * next
Definition: hashtab.h:108
struct ast_hashtab * tab
Definition: hashtab.h:107
int(* newsize)(struct ast_hashtab *tab)
Definition: hashtab.h:90
int hash_tab_elements
Definition: hashtab.h:95
int(* compare)(const void *a, const void *b)
Definition: hashtab.h:88
int(* resize)(struct ast_hashtab *tab)
Definition: hashtab.h:91
int hash_tab_size
Definition: hashtab.h:94
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
struct ast_hashtab_bucket * tlist
Definition: hashtab.h:86
int do_locking
Definition: hashtab.h:99
int resize_count
Definition: hashtab.h:97
ast_rwlock_t lock
Definition: hashtab.h:101
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85
int largest_bucket_size
Definition: hashtab.h:96
struct test_val * next
Handy terminal functions for vt* terms.
static struct aco_type item
Definition: test_config.c:1463
static struct test_val b
static struct test_val a
static struct test_val c
Definitions to aid in the use of thread local storage.
Utility functions.