CI: Various updates to buildAsterisk.sh
[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 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
84 int ast_hashtab_resize_java(struct ast_hashtab *tab)
85 {
86         double loadfactor = (double) tab->hash_tab_elements / (double) tab->hash_tab_size;
87
88         return (loadfactor > 0.75);
89 }
90
91 int ast_hashtab_resize_tight(struct ast_hashtab *tab)
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
127 int ast_hashtab_newsize_java(struct ast_hashtab *tab)
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
137 int ast_hashtab_newsize_tight(struct ast_hashtab *tab)
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)
253                 ht->resize = ast_hashtab_resize_java;
254
255         if (!ht->newsize)
256                 ht->newsize = ast_hashtab_newsize_java;
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
338 void ast_hashtab_wrlock(struct ast_hashtab *tab)
339 {
340         ast_rwlock_wrlock(&tab->lock);
341 }
342
343 void ast_hashtab_rdlock(struct ast_hashtab *tab)
344 {
345         ast_rwlock_rdlock(&tab->lock);
346 }
347
348 void ast_hashtab_initlock(struct ast_hashtab *tab)
349 {
350         ast_rwlock_init(&tab->lock);
351 }
352
353 void ast_hashtab_destroylock(struct ast_hashtab *tab)
354 {
355         ast_rwlock_destroy(&tab->lock);
356 }
357
358 void ast_hashtab_unlock(struct ast_hashtab *tab)
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 */
577 int ast_hashtab_size(struct ast_hashtab *tab)
578 {
579         return tab->hash_tab_elements;
580 }
581
582 /* this function returns the size of the bucket array in the hashtab */
583 int ast_hashtab_capacity( struct ast_hashtab *tab)
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
674 void ast_hashtab_end_traversal(struct ast_hashtab_iter *it)
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
683 void *ast_hashtab_next(struct ast_hashtab_iter *it)
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
746 void *ast_hashtab_remove_object_via_lookup(struct ast_hashtab *tab, void *obj)
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
757         obj2 = ast_hashtab_remove_object_via_lookup_nolock(tab,obj);
758
759         if (tab->do_locking)
760                 ast_rwlock_unlock(&tab->lock);
761
762         return (void *)obj2;
763 }
764
765 void *ast_hashtab_remove_object_via_lookup_nolock(struct ast_hashtab *tab, void *obj)
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
802         obj2 = ast_hashtab_remove_this_object_nolock(tab,obj);
803
804         if (tab->do_locking)
805                 ast_rwlock_unlock(&tab->lock);
806
807         return (void *)obj2;
808 }
809
810 void *ast_hashtab_remove_this_object_nolock(struct ast_hashtab *tab, void *obj)
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 }