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