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