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