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