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