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