Merge "pbx: Reduce verbosity while loading extensions"
[asterisk/asterisk.git] / main / hashtab.c
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 #ifdef __AST_DEBUG_MALLOC
45 static void _ast_hashtab_resize(struct ast_hashtab *tab, const char *file, int lineno, const char *func);
46 #define ast_hashtab_resize(a)   _ast_hashtab_resize(a,__FILE__, __LINE__, __PRETTY_FUNCTION__)
47 #else
48 static void ast_hashtab_resize(struct ast_hashtab *tab);
49 #endif
50 static void *ast_hashtab_lookup_internal(struct ast_hashtab *tab, const void *obj, unsigned int h);
51
52 /* some standard, default routines for general use */
53
54 int ast_hashtab_compare_strings(const void *a, const void *b)
55 {
56         return strcmp(a, b);
57 }
58
59 int ast_hashtab_compare_strings_nocase(const void *a, const void *b)
60 {
61         return strcasecmp(a, b);
62 }
63
64 int ast_hashtab_compare_ints(const void *a, const void *b)
65 {
66         int ai = *((int *) a);
67         int bi = *((int *) b);
68
69         if (ai < bi)
70                 return -1;
71
72         return !(ai == bi);
73 }
74
75 int ast_hashtab_compare_shorts(const void *a, const void *b)
76 {
77         short as = *((short *) a);
78         short bs = *((short *) b);
79
80         if (as < bs)
81                 return -1;
82
83         return !(as == bs);
84 }
85
86 int ast_hashtab_resize_java(struct ast_hashtab *tab)
87 {
88         double loadfactor = (double) tab->hash_tab_elements / (double) tab->hash_tab_size;
89
90         return (loadfactor > 0.75);
91 }
92
93 int ast_hashtab_resize_tight(struct ast_hashtab *tab)
94 {
95         return (tab->hash_tab_elements > tab->hash_tab_size); /* this is quicker than division */
96 }
97
98 int ast_hashtab_resize_none(struct ast_hashtab *tab) /* always return 0 -- no resizing */
99 {
100         return 0;
101 }
102
103 int ast_is_prime(int num)
104 {
105         int tnum, limit;
106
107         if (!(num & 0x1)) /* even number -- not prime */
108                 return 0;
109
110         /* Loop through ODD numbers starting with 3 */
111
112         tnum = 3;
113         limit = num;
114         while (tnum < limit) {
115                 if (!(num % tnum))
116                         return 0;
117
118                 /* really, we only need to check sqrt(num) numbers */
119                 limit = num / tnum;
120
121                 /* we only check odd numbers */
122                 tnum = tnum + 2;
123         }
124
125         /* if we made it through the loop, the number is a prime */
126         return 1;
127 }
128
129 int ast_hashtab_newsize_java(struct ast_hashtab *tab)
130 {
131         int i = (tab->hash_tab_size << 1); /* multiply by two */
132
133         while (!ast_is_prime(i))
134                 i++;
135
136         return i;
137 }
138
139 int ast_hashtab_newsize_tight(struct ast_hashtab *tab)
140 {
141         int x = (tab->hash_tab_size << 1);
142         int i = (tab->hash_tab_size + x);
143
144         while (!ast_is_prime(i))
145                 i++;
146
147         return i;
148 }
149
150 int ast_hashtab_newsize_none(struct ast_hashtab *tab) /* always return current size -- no resizing */
151 {
152         return tab->hash_tab_size;
153 }
154
155 unsigned int ast_hashtab_hash_string(const void *obj)
156 {
157         unsigned char *str = (unsigned char *) obj;
158         unsigned int total;
159
160         for (total = 0; *str; str++) {
161                 unsigned int tmp = total;
162                 total <<= 1; /* multiply by 2 */
163                 total += tmp; /* multiply by 3 */
164                 total <<= 2; /* multiply by 12 */
165                 total += tmp; /* multiply by 13 */
166
167                 total += ((unsigned int)(*str));
168         }
169         return total;
170 }
171
172 unsigned int ast_hashtab_hash_string_sax(const void *obj) /* from Josh */
173 {
174         const unsigned char *str = obj;
175         unsigned int total = 0, c = 0;
176
177         while ((c = *str++))
178                 total ^= (total << 5) + (total >> 2) + (total << 10) + c;
179
180         return total;
181 }
182
183 unsigned int ast_hashtab_hash_string_nocase(const void *obj)
184 {
185         const unsigned char *str = obj;
186         unsigned int total;
187
188         for (total = 0; *str; str++) {
189                 unsigned int tmp = total;
190                 unsigned int charval = toupper(*str);
191
192                 /* hopefully, the following is faster than multiplication by 7 */
193                 /* why do I go to this bother? A good compiler will do this
194                    anyway, if I say total *= 13 */
195                 /* BTW, tried *= 7, and it doesn't do as well in spreading things around! */
196                 total <<= 1; /* multiply by 2 */
197                 total += tmp; /* multiply by 3 */
198                 total <<= 2; /* multiply by 12 */
199                 total += tmp; /* multiply by 13 */
200
201                 total += (charval);
202         }
203
204         return total;
205 }
206
207 unsigned int ast_hashtab_hash_int(const int x)
208 {
209         return x;
210 }
211
212 unsigned int ast_hashtab_hash_short(const short x)
213 {
214         /* hmmmm.... modulus is best < 65535 !! */
215         return x;
216 }
217
218 struct ast_hashtab *
219 #ifdef __AST_DEBUG_MALLOC
220 _ast_hashtab_create
221 #else
222 ast_hashtab_create
223 #endif
224 (int initial_buckets,
225         int (*compare)(const void *a, const void *b),
226         int (*resize)(struct ast_hashtab *),
227         int (*newsize)(struct ast_hashtab *tab),
228         unsigned int (*hash)(const void *obj),
229         int do_locking
230 #ifdef __AST_DEBUG_MALLOC
231         , const char *file, int lineno, const char *function
232 #endif
233 )
234 {
235         struct ast_hashtab *ht;
236
237 #ifdef __AST_DEBUG_MALLOC
238         if (!(ht = __ast_calloc(1, sizeof(*ht), file, lineno, function)))
239 #else
240         if (!(ht = ast_calloc(1, sizeof(*ht))))
241 #endif
242                 return NULL;
243
244         while (!ast_is_prime(initial_buckets)) /* make sure this is prime */
245                 initial_buckets++;
246
247 #ifdef __AST_DEBUG_MALLOC
248         if (!(ht->array = __ast_calloc(initial_buckets, sizeof(*(ht->array)), file, lineno, function))) {
249 #else
250         if (!(ht->array = ast_calloc(initial_buckets, sizeof(*(ht->array))))) {
251 #endif
252                 ast_free(ht);
253                 return NULL;
254         }
255
256         ht->hash_tab_size = initial_buckets;
257         ht->compare = compare;
258         ht->resize = resize;
259         ht->newsize = newsize;
260         ht->hash = hash;
261         ht->do_locking = do_locking;
262
263         if (do_locking)
264                 ast_rwlock_init(&ht->lock);
265
266         if (!ht->resize)
267                 ht->resize = ast_hashtab_resize_java;
268
269         if (!ht->newsize)
270                 ht->newsize = ast_hashtab_newsize_java;
271
272         return ht;
273 }
274
275 #ifdef __AST_DEBUG_MALLOC
276 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)
277 #else
278 struct ast_hashtab *ast_hashtab_dup(struct ast_hashtab *tab, void *(*obj_dup_func)(const void *obj))
279 #endif
280 {
281         struct ast_hashtab *ht;
282         unsigned int i;
283
284         if (!(ht = ast_calloc(1, sizeof(*ht))))
285                 return NULL;
286
287         if (!(ht->array =
288 #ifdef __AST_DEBUG_MALLOC
289                 __ast_calloc(tab->hash_tab_size, sizeof(*(ht->array)), file, lineno, func)
290 #else
291                 ast_calloc(tab->hash_tab_size, sizeof(*(ht->array)))
292 #endif
293                 )) {
294                 ast_free(ht);
295                 return NULL;
296         }
297
298         ht->hash_tab_size = tab->hash_tab_size;
299         ht->compare = tab->compare;
300         ht->resize = tab->resize;
301         ht->newsize = tab->newsize;
302         ht->hash = tab->hash;
303         ht->do_locking = tab->do_locking;
304
305         if (ht->do_locking)
306                 ast_rwlock_init(&ht->lock);
307
308         /* now, dup the objects in the buckets and get them into the table */
309         /* the fast way is to use the existing array index, and not have to hash
310            the objects again */
311         for (i = 0; i < ht->hash_tab_size; i++) {
312                 struct ast_hashtab_bucket *b = tab->array[i];
313                 while (b) {
314                         void *newobj = (*obj_dup_func)(b->object);
315                         if (newobj)
316 #ifdef __AST_DEBUG_MALLOC
317                                 _ast_hashtab_insert_immediate_bucket(ht, newobj, i, file, lineno, func);
318 #else
319                                 ast_hashtab_insert_immediate_bucket(ht, newobj, i);
320 #endif
321                         b = b->next;
322                 }
323         }
324
325         return ht;
326 }
327
328 static void tlist_del_item(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
329 {
330         /* item had better be in the list! or suffer the weirdness that occurs, later! */
331         if (*head == item) { /* first item in the list */
332                 *head = item->tnext;
333                 if (item->tnext)
334                         item->tnext->tprev = NULL;
335         } else {
336                 /* short circuit stuff */
337                 item->tprev->tnext = item->tnext;
338                 if (item->tnext)
339                         item->tnext->tprev = item->tprev;
340         }
341 }
342
343 static void tlist_add_head(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
344 {
345         if (*head) {
346                 item->tnext = *head;
347                 item->tprev = NULL;
348                 (*head)->tprev = item;
349                 *head = item;
350         } else {
351                 /* the list is empty */
352                 *head = item;
353                 item->tprev = NULL;
354                 item->tnext = NULL;
355         }
356 }
357
358 /* user-controlled hashtab locking. Create a hashtab without locking, then call the
359    following locking routines yourself to lock the table between threads. */
360
361 void ast_hashtab_wrlock(struct ast_hashtab *tab)
362 {
363         ast_rwlock_wrlock(&tab->lock);
364 }
365
366 void ast_hashtab_rdlock(struct ast_hashtab *tab)
367 {
368         ast_rwlock_rdlock(&tab->lock);
369 }
370
371 void ast_hashtab_initlock(struct ast_hashtab *tab)
372 {
373         ast_rwlock_init(&tab->lock);
374 }
375
376 void ast_hashtab_destroylock(struct ast_hashtab *tab)
377 {
378         ast_rwlock_destroy(&tab->lock);
379 }
380
381 void ast_hashtab_unlock(struct ast_hashtab *tab)
382 {
383         ast_rwlock_unlock(&tab->lock);
384 }
385
386 void ast_hashtab_destroy(struct ast_hashtab *tab, void (*objdestroyfunc)(void *obj))
387 {
388         /* this func will free the hash table and all its memory. It
389            doesn't touch the objects stored in it */
390         if (tab) {
391
392                 if (tab->do_locking)
393                         ast_rwlock_wrlock(&tab->lock);
394
395                 if (tab->array) {
396                         /* go thru and destroy the buckets */
397                         struct ast_hashtab_bucket *t;
398                         int i;
399
400                         while (tab->tlist) {
401                                 t = tab->tlist;
402                                 if (t->object && objdestroyfunc) {
403                                         /* I cast this because I'm not going to MOD it, I'm going to DESTROY
404                                          * it.
405                                          */
406                                         (*objdestroyfunc)((void *) t->object);
407                                 }
408
409                                 tlist_del_item(&(tab->tlist), tab->tlist);
410                                 ast_free(t);
411                         }
412
413                         for (i = 0; i < tab->hash_tab_size; i++) {
414                                 /* Not totally necessary, but best to destroy old pointers */
415                                 tab->array[i] = NULL;
416                         }
417                         ast_free(tab->array);
418                 }
419                 if (tab->do_locking) {
420                         ast_rwlock_unlock(&tab->lock);
421                         ast_rwlock_destroy(&tab->lock);
422                 }
423                 ast_free(tab);
424         }
425 }
426
427 #ifdef __AST_DEBUG_MALLOC
428 int _ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj, const char *file, int lineno, const char *func)
429 #else
430 int ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj)
431 #endif
432 {
433         unsigned int h;
434         int res=0;
435
436         if (!tab || !obj)
437                 return res;
438
439         if (tab->do_locking)
440                 ast_rwlock_wrlock(&tab->lock);
441
442         h = (*tab->hash)(obj) % tab->hash_tab_size;
443
444 #ifdef __AST_DEBUG_MALLOC
445         res = _ast_hashtab_insert_immediate_bucket(tab, obj, h, file, lineno, func);
446 #else
447         res = ast_hashtab_insert_immediate_bucket(tab, obj, h);
448 #endif
449
450         if (tab->do_locking)
451                 ast_rwlock_unlock(&tab->lock);
452
453         return res;
454 }
455
456 #ifdef __AST_DEBUG_MALLOC
457 int _ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h, const char *file, int lineno, const char *func)
458 #else
459 int ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h)
460 #endif
461 {
462         int c;
463         struct ast_hashtab_bucket *b;
464
465         if (!tab || !obj)
466                 return 0;
467
468         for (c = 0, b = tab->array[h]; b; b= b->next)
469                 c++;
470
471         if (c + 1 > tab->largest_bucket_size)
472                 tab->largest_bucket_size = c + 1;
473
474         if (!(b =
475 #ifdef __AST_DEBUG_MALLOC
476                         __ast_calloc(1, sizeof(*b), file, lineno, func)
477 #else
478                         ast_calloc(1, sizeof(*b))
479 #endif
480                 )) return 0;
481
482         b->object = obj;
483         b->next = tab->array[h];
484         tab->array[h] = b;
485
486         if (b->next)
487                 b->next->prev = b;
488
489         tlist_add_head(&(tab->tlist), b);
490         tab->hash_tab_elements++;
491
492         if ((*tab->resize)(tab))
493                 ast_hashtab_resize(tab);
494
495         return 1;
496 }
497
498 #ifdef __AST_DEBUG_MALLOC
499 int _ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj, const char *file, int lineno, const char *func)
500 #else
501 int ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj)
502 #endif
503 {
504         /* check to see if the element is already there; insert only if
505            it is not there. */
506         /* will force a resize if the resize func returns 1 */
507         /* returns 1 on success, 0 if there's a problem, or it's already there. */
508         unsigned int bucket = 0;
509
510         if (tab->do_locking)
511                 ast_rwlock_wrlock(&tab->lock);
512
513         if (!ast_hashtab_lookup_bucket(tab, obj, &bucket)) {
514 #ifdef __AST_DEBUG_MALLOC
515                 int ret2 = _ast_hashtab_insert_immediate_bucket(tab, obj, bucket, file, lineno, func);
516 #else
517                 int ret2 = ast_hashtab_insert_immediate_bucket(tab, obj, bucket);
518 #endif
519
520                 if (tab->do_locking)
521                         ast_rwlock_unlock(&tab->lock);
522
523                 return ret2;
524         }
525
526         if (tab->do_locking)
527                 ast_rwlock_unlock(&tab->lock);
528
529         return 0;
530 }
531
532 void *ast_hashtab_lookup(struct ast_hashtab *tab, const void *obj)
533 {
534         /* lookup this object in the hash table. return a ptr if found, or NULL if not */
535         unsigned int h;
536         void *ret;
537
538         if (!tab || !obj)
539                 return 0;
540
541         if (tab->do_locking)
542                 ast_rwlock_rdlock(&tab->lock);
543
544         h = (*tab->hash)(obj) % tab->hash_tab_size;
545
546         ret = ast_hashtab_lookup_internal(tab,obj,h);
547
548         if (tab->do_locking)
549                 ast_rwlock_unlock(&tab->lock);
550
551         return ret;
552 }
553
554
555 void *ast_hashtab_lookup_with_hash(struct ast_hashtab *tab, const void *obj, unsigned int hashval)
556 {
557         /* lookup this object in the hash table. return a ptr if found, or NULL if not */
558         unsigned int h;
559         void *ret;
560
561         if (!tab || !obj)
562                 return 0;
563
564         if (tab->do_locking)
565                 ast_rwlock_rdlock(&tab->lock);
566
567         h = hashval % tab->hash_tab_size;
568
569         ret = ast_hashtab_lookup_internal(tab,obj,h);
570
571         if (tab->do_locking)
572                 ast_rwlock_unlock(&tab->lock);
573
574         return ret;
575 }
576
577 void *ast_hashtab_lookup_bucket(struct ast_hashtab *tab, const void *obj, unsigned int *bucket)
578 {
579         /* lookup this object in the hash table. return a ptr if found, or NULL if not */
580         unsigned int h;
581         void *ret;
582
583         if (!tab || !obj)
584                 return 0;
585
586         h = (*tab->hash)(obj) % tab->hash_tab_size;
587
588         ret = ast_hashtab_lookup_internal(tab,obj,h);
589
590         *bucket = h;
591
592         return ret;
593 }
594
595 static void *ast_hashtab_lookup_internal(struct ast_hashtab *tab, const void *obj, unsigned int h)
596 {
597         struct ast_hashtab_bucket *b;
598
599         for (b = tab->array[h]; b; b = b->next) {
600                 if (!(*tab->compare)(obj,b->object)) {
601                         /* I can't touch obj in this func, but the outside world is welcome to */
602                         return (void*) b->object;
603                 }
604         }
605
606         return NULL;
607 }
608
609 void ast_hashtab_get_stats(struct ast_hashtab *tab, int *biggest_bucket_size, int *resize_count, int *num_objects, int *num_buckets)
610 {
611         /* returns key stats for the table */
612         if (tab->do_locking)
613                 ast_rwlock_rdlock(&tab->lock);
614         *biggest_bucket_size = tab->largest_bucket_size;
615         *resize_count = tab->resize_count;
616         *num_objects = tab->hash_tab_elements;
617         *num_buckets = tab->hash_tab_size;
618         if (tab->do_locking)
619                 ast_rwlock_unlock(&tab->lock);
620 }
621
622 /* this function returns the number of elements stored in the hashtab */
623 int ast_hashtab_size(struct ast_hashtab *tab)
624 {
625         return tab->hash_tab_elements;
626 }
627
628 /* this function returns the size of the bucket array in the hashtab */
629 int ast_hashtab_capacity( struct ast_hashtab *tab)
630 {
631         return tab->hash_tab_size;
632 }
633
634 /* the insert operation calls this, and is wrlock'd when it does. */
635 /* if you want to call it, you should set the wrlock yourself */
636
637 #ifdef __AST_DEBUG_MALLOC
638 static void _ast_hashtab_resize(struct ast_hashtab *tab, const char *file, int lineno, const char *func)
639 #else
640 static void ast_hashtab_resize(struct ast_hashtab *tab)
641 #endif
642 {
643         /* this function is called either internally, when the resize func returns 1, or
644            externally by the user to force a resize of the hash table */
645         int newsize = (*tab->newsize)(tab), i, c;
646         unsigned int h;
647         struct ast_hashtab_bucket *b,*bn;
648
649         /* Since we keep a DLL of all the buckets in tlist,
650            all we have to do is free the array, malloc a new one,
651            and then go thru the tlist array and reassign them into
652            the bucket arrayj.
653         */
654         for (i = 0; i < tab->hash_tab_size; i++) { /* don't absolutely have to do this, but
655                                                                                         why leave ptrs laying around */
656                 tab->array[i] = 0; /* erase old ptrs */
657         }
658         ast_free(tab->array);
659         if (!(tab->array =
660 #ifdef __AST_DEBUG_MALLOC
661                 __ast_calloc(newsize, sizeof(*(tab->array)), file, lineno, func)
662 #else
663                 ast_calloc(newsize, sizeof(*(tab->array)))
664 #endif
665                 ))
666                 return;
667
668         /* now sort the buckets into their rightful new slots */
669         tab->resize_count++;
670         tab->hash_tab_size = newsize;
671         tab->largest_bucket_size = 0;
672
673         for (b = tab->tlist; b; b = bn) {
674                 b->prev = 0;
675                 bn = b->tnext;
676                 h = (*tab->hash)(b->object) % tab->hash_tab_size;
677                 b->next = tab->array[h];
678                 if (b->next)
679                         b->next->prev = b;
680                 tab->array[h] = b;
681         }
682         /* recalc the largest bucket size */
683         for (i = 0; i < tab->hash_tab_size; i++) {
684                 for (c = 0, b = tab->array[i]; b; b = b->next)
685                         c++;
686                 if (c > tab->largest_bucket_size)
687                         tab->largest_bucket_size = c;
688         }
689 }
690
691 #ifdef __AST_DEBUG_MALLOC
692 struct ast_hashtab_iter *_ast_hashtab_start_traversal(struct ast_hashtab *tab, const char *file, int lineno, const char *func)
693 #else
694 struct ast_hashtab_iter *ast_hashtab_start_traversal(struct ast_hashtab *tab)
695 #endif
696 {
697         /* returns an iterator */
698         struct ast_hashtab_iter *it;
699
700         if (!(it =
701 #ifdef __AST_DEBUG_MALLOC
702                         __ast_calloc(1, sizeof(*it), file, lineno, func)
703 #else
704                         ast_calloc(1, sizeof(*it))
705 #endif
706                 ))
707                 return NULL;
708
709         it->next = tab->tlist;
710         it->tab = tab;
711         if (tab->do_locking)
712                 ast_rwlock_rdlock(&tab->lock);
713
714         return it;
715 }
716
717 /* use this function to get a write lock */
718 #ifdef __AST_DEBUG_MALLOC
719 struct ast_hashtab_iter *_ast_hashtab_start_write_traversal(struct ast_hashtab *tab, const char *file, int lineno, const char *func)
720 #else
721 struct ast_hashtab_iter *ast_hashtab_start_write_traversal(struct ast_hashtab *tab)
722 #endif
723 {
724         /* returns an iterator */
725         struct ast_hashtab_iter *it;
726
727         if (!(it =
728 #ifdef __AST_DEBUG_MALLOC
729                         __ast_calloc(1, sizeof(*it), file, lineno, func)
730 #else
731                         ast_calloc(1, sizeof(*it))
732 #endif
733                 ))
734                 return NULL;
735
736         it->next = tab->tlist;
737         it->tab = tab;
738         if (tab->do_locking)
739                 ast_rwlock_wrlock(&tab->lock);
740
741         return it;
742 }
743
744 void ast_hashtab_end_traversal(struct ast_hashtab_iter *it)
745 {
746         if (!it)
747                 return;
748         if (it->tab->do_locking)
749                 ast_rwlock_unlock(&it->tab->lock);
750         ast_free(it);
751 }
752
753 void *ast_hashtab_next(struct ast_hashtab_iter *it)
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         ast_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
816 void *ast_hashtab_remove_object_via_lookup(struct ast_hashtab *tab, void *obj)
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
827         obj2 = ast_hashtab_remove_object_via_lookup_nolock(tab,obj);
828
829         if (tab->do_locking)
830                 ast_rwlock_unlock(&tab->lock);
831
832         return (void *)obj2;
833 }
834
835 void *ast_hashtab_remove_object_via_lookup_nolock(struct ast_hashtab *tab, void *obj)
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
872         obj2 = ast_hashtab_remove_this_object_nolock(tab,obj);
873
874         if (tab->do_locking)
875                 ast_rwlock_unlock(&tab->lock);
876
877         return (void *)obj2;
878 }
879
880 void *ast_hashtab_remove_this_object_nolock(struct ast_hashtab *tab, void *obj)
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 }