Asterisk - The Open Source Telephony Project  GIT-master-932eae6
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"
39 #include "asterisk/threadstorage.h"
40 #include "asterisk/linkedlists.h"
41 #include "asterisk/hashtab.h"
42 
43 
44 static 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 
48 static 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 
52 int ast_hashtab_compare_strings(const void *a, const void *b)
53 {
54  return strcmp(a, b);
55 }
56 
57 int ast_hashtab_compare_strings_nocase(const void *a, const void *b)
58 {
59  return strcasecmp(a, b);
60 }
61 
62 int 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 
73 int 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 
96 int ast_hashtab_resize_none(struct ast_hashtab *tab) /* always return 0 -- no resizing */
97 {
98  return 0;
99 }
100 
101 int 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 
148 int ast_hashtab_newsize_none(struct ast_hashtab *tab) /* always return current size -- no resizing */
149 {
150  return tab->hash_tab_size;
151 }
152 
153 unsigned 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 
170 unsigned 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 
181 unsigned 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 
205 unsigned int ast_hashtab_hash_int(const int x)
206 {
207  return x;
208 }
209 
210 unsigned int ast_hashtab_hash_short(const short x)
211 {
212  /* hmmmm.... modulus is best < 65535 !! */
213  return x;
214 }
215 
216 struct 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;
247  ht->do_locking = do_locking;
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 
261 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)
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 
305 static 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 
320 static 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 {
355  ast_rwlock_destroy(&tab->lock);
356 }
357 
359 {
360  ast_rwlock_unlock(&tab->lock);
361 }
362 
363 void 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);
398  ast_rwlock_destroy(&tab->lock);
399  }
400  ast_free(tab);
401  }
402 }
403 
404 int _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 
425 int _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))
455  ast_hashtab_resize(tab);
456 
457  return 1;
458 }
459 
460 int _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 
486 void *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 
509 void *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 
531 void *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 
549 static 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 
563 void 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 
591 static 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 
637 struct 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)
650  ast_rwlock_rdlock(&tab->lock);
651 
652  return it;
653 }
654 
655 /* use this function to get a write lock */
656 struct 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)
669  ast_rwlock_wrlock(&tab->lock);
670 
671  return it;
672 }
673 
675 {
676  if (!it)
677  return;
678  if (it->tab->do_locking)
679  ast_rwlock_unlock(&it->tab->lock);
680  ast_free(it);
681 }
682 
684 {
685  /* returns the next object in the list, advances iter one step */
686  struct ast_hashtab_bucket *retval;
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 
697 static void *ast_hashtab_remove_object_internal(struct ast_hashtab *tab, struct ast_hashtab_bucket *b, int h)
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 
780  obj2 = ast_hashtab_remove_object_internal(tab, b, h);
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 
789 void *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;
826  obj2 = ast_hashtab_remove_object_internal(tab, b, h);
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 }
#define ast_rwlock_rdlock(a)
Definition: lock.h:233
void * __ast_calloc(size_t nmemb, size_t size, const char *file, int lineno, const char *func) attribute_malloc
Definition: astmm.c:1635
struct ast_hashtab_bucket * tnext
Definition: hashtab.h:79
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
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
Asterisk locking-related definitions:
Asterisk main include file. File version handling, generic pbx functions.
int ast_hashtab_compare_strings(const void *a, const void *b)
Compares two strings for equality.
Definition: hashtab.c:52
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
int hash_tab_size
Definition: hashtab.h:94
unsigned int ast_hashtab_hash_int(const int x)
Definition: hashtab.c:205
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
#define ast_rwlock_destroy(rwlock)
Definition: lock.h:231
int largest_bucket_size
Definition: hashtab.h:96
ast_rwlock_t lock
Definition: hashtab.h:101
static void _ast_hashtab_resize(struct ast_hashtab *tab, const char *file, int lineno, const char *func)
Definition: hashtab.c:591
struct ast_hashtab_bucket * tprev
Definition: hashtab.h:80
static int tmp()
Definition: bt_open.c:389
Generic (perhaps overly so) hashtable implementation Hash Table support in Asterisk.
void ast_hashtab_end_traversal(struct ast_hashtab_iter *it)
end the traversal, free the iterator, unlock if necc.
Definition: hashtab.c:674
unsigned int ast_hashtab_hash_string(const void *obj)
Hashes a string to a number.
Definition: hashtab.c:153
int resize_count
Definition: hashtab.h:97
static struct aco_type item
Definition: test_config.c:1463
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
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
static struct test_val c
struct ast_hashtab_bucket * prev
Definition: hashtab.h:78
const char * str
Definition: app_jack.c:147
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
#define NULL
Definition: resample.c:96
Definitions to aid in the use of thread local storage.
#define ast_rwlock_unlock(a)
Definition: lock.h:232
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
void ast_hashtab_rdlock(struct ast_hashtab *tab)
Request a read-lock on the table – don&#39;t change anything!
Definition: hashtab.c:343
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
struct ast_hashtab_bucket * next
Definition: hashtab.h:108
char * bs
Definition: eagi_proxy.c:73
static void * ast_hashtab_lookup_internal(struct ast_hashtab *tab, const void *obj, unsigned int h)
Definition: hashtab.c:549
Utility functions.
int ast_hashtab_compare_strings_nocase(const void *a, const void *b)
Compares two strings for equality, ignoring case.
Definition: hashtab.c:57
int do_locking
Definition: hashtab.h:99
int ast_hashtab_size(struct ast_hashtab *tab)
Returns the number of elements stored in the hashtab.
Definition: hashtab.c:577
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
General Asterisk PBX channel definitions.
#define ast_hashtab_resize(tab)
Definition: hashtab.c:45
void ast_hashtab_destroylock(struct ast_hashtab *tab)
Call this before you destroy the table.
Definition: hashtab.c:353
int ast_is_prime(int num)
Determines if the specified number is prime.
Definition: hashtab.c:101
Asterisk internal frame definitions.
int ast_hashtab_compare_shorts(const void *a, const void *b)
Compares two shorts for equality.
Definition: hashtab.c:73
void ast_hashtab_initlock(struct ast_hashtab *tab)
Call this after you create the table to init the lock.
Definition: hashtab.c:348
A set of macros to manage forward-linked lists.
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_remove_object_via_lookup_nolock(struct ast_hashtab *tab, void *obj)
Looks up the object, removes the corresponding bucket.
Definition: hashtab.c:765
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_lookup(struct ast_hashtab *tab, const void *obj)
Lookup this object in the hash table.
Definition: hashtab.c:486
int ast_hashtab_newsize_java(struct ast_hashtab *tab)
Create a prime number roughly 2x the current table size.
Definition: hashtab.c:127
struct ast_hashtab_bucket ** array
Definition: hashtab.h:85
struct ast_hashtab * tab
Definition: hashtab.h:107
static void tlist_del_item(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
Definition: hashtab.c:305
int(* compare)(const void *a, const void *b)
Definition: hashtab.h:88
#define ast_rwlock_init(rwlock)
wrapper for rwlock with tracking enabled
Definition: lock.h:222
static void tlist_add_head(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
Definition: hashtab.c:320
int(* resize)(struct ast_hashtab *tab)
Definition: hashtab.h:91
int _ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj, const char *file, int lineno, const char *func)
Insert without checking.
Definition: hashtab.c:404
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:697
int _ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h, const char *file, int lineno, const char *func)
Insert without checking, hashing or locking.
Definition: hashtab.c:425
an iterator for traversing the buckets
Definition: hashtab.h:105
int ast_hashtab_newsize_none(struct ast_hashtab *tab)
always return current size – no resizing
Definition: hashtab.c:148
#define ast_free(a)
Definition: astmm.h:182
unsigned int(* hash)(const void *obj)
Definition: hashtab.h:92
unsigned int ast_hashtab_hash_string_nocase(const void *obj)
Hashes a string to a number ignoring case.
Definition: hashtab.c:181
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
int ast_hashtab_newsize_tight(struct ast_hashtab *tab)
Definition: hashtab.c:137
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
#define ast_rwlock_wrlock(a)
Definition: lock.h:234
const void * object
Definition: hashtab.h:76
Standard Command Line Interface.
struct ast_hashtab_bucket * next
Definition: hashtab.h:77
static int compare(const char *text, const char *template)
unsigned int ast_hashtab_hash_short(const short x)
Definition: hashtab.c:210
int ast_hashtab_compare_ints(const void *a, const void *b)
Compares two integers for equality.
Definition: hashtab.c:62
static ENTRY retval
Definition: hsearch.c:50
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
static int total
Definition: res_adsi.c:968
static struct test_val b
Handy terminal functions for vt* terms.
int(* newsize)(struct ast_hashtab *tab)
Definition: hashtab.h:90
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
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
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)
Create the hashtable list.
Definition: hashtab.c:216
void ast_hashtab_wrlock(struct ast_hashtab *tab)
Request a write-lock on the table.
Definition: hashtab.c:338
int hash_tab_elements
Definition: hashtab.h:95
static struct test_val a