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