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