Wed Jan 8 2020 09:49:48

Asterisk developer's documentation


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