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