Wed Oct 28 11:51:04 2009

Asterisk developer's documentation


hashtab.c

Go to the documentation of this file.
00001 /*
00002  * Asterisk -- An open source telephony toolkit.
00003  *
00004  * Copyright (C) 2007, Digium, Inc.
00005  *
00006  * Steve Murphy <murf@digium.com>
00007  *
00008  * See http://www.asterisk.org for more information about
00009  * the Asterisk project. Please do not directly contact
00010  * any of the maintainers of this project for assistance;
00011  * the project provides a web site, mailing lists and IRC
00012  * channels for your use.
00013  *
00014  * This program is free software, distributed under the terms of
00015  * the GNU General Public License Version 2. See the LICENSE file
00016  * at the top of the source tree.
00017  */
00018 /*! \file
00019  *
00020  *  \brief code to implement generic hash tables
00021  *
00022  *  \author Steve Murphy <murf@digium.com>
00023  */
00024 
00025 #include "asterisk.h"
00026 
00027 ASTERISK_FILE_VERSION(__FILE__, "$Revision: 149202 $")
00028 
00029 #include <ctype.h>
00030 
00031 #include "asterisk/lock.h"
00032 #include "asterisk/frame.h"
00033 #include "asterisk/channel.h"
00034 #include "asterisk/cli.h"
00035 #include "asterisk/term.h"
00036 #include "asterisk/utils.h"
00037 #include "asterisk/threadstorage.h"
00038 #include "asterisk/linkedlists.h"
00039 #include "asterisk/hashtab.h"
00040 
00041 static void ast_hashtab_resize( struct ast_hashtab *tab);
00042 static void *ast_hashtab_lookup_internal(struct ast_hashtab *tab, const void *obj, unsigned int h);
00043 
00044 /* some standard, default routines for general use */
00045 
00046 int ast_hashtab_compare_strings(const void *a, const void *b)
00047 {
00048    return strcmp(a, b);
00049 }
00050 
00051 int ast_hashtab_compare_strings_nocase(const void *a, const void *b)
00052 {
00053    return strcasecmp(a, b);
00054 }
00055 
00056 int ast_hashtab_compare_ints(const void *a, const void *b)
00057 {
00058    int ai = *((int *) a);
00059    int bi = *((int *) b);
00060 
00061    if (ai < bi)
00062       return -1;
00063    
00064    return !(ai == bi);
00065 }
00066 
00067 int ast_hashtab_compare_shorts(const void *a, const void *b)
00068 {
00069    short as = *((short *) a);
00070    short bs = *((short *) b);
00071    
00072    if (as < bs)
00073       return -1;
00074 
00075    return !(as == bs);
00076 }
00077 
00078 int ast_hashtab_resize_java(struct ast_hashtab *tab)
00079 {
00080    double loadfactor = (double) tab->hash_tab_elements / (double) tab->hash_tab_size;
00081 
00082    return (loadfactor > 0.75);
00083 }
00084 
00085 int ast_hashtab_resize_tight(struct ast_hashtab *tab)
00086 {
00087    return (tab->hash_tab_elements > tab->hash_tab_size); /* this is quicker than division */
00088 }
00089 
00090 int ast_hashtab_resize_none(struct ast_hashtab *tab) /* always return 0 -- no resizing */
00091 {
00092    return 0;
00093 }
00094 
00095 int ast_is_prime(int num)
00096 {
00097    int tnum, limit;
00098        
00099    if (!(num & 0x1)) /* even number -- not prime */
00100       return 0;
00101           
00102    /* Loop through ODD numbers starting with 3 */
00103 
00104    tnum = 3;
00105    limit = num;
00106    while (tnum < limit) {
00107       if (!(num % tnum))
00108          return 0;
00109 
00110       /* really, we only need to check sqrt(num) numbers */
00111       limit = num / tnum;
00112       
00113       /* we only check odd numbers */
00114       tnum = tnum + 2;
00115    }
00116 
00117    /* if we made it through the loop, the number is a prime */
00118 
00119    return 1;
00120 }
00121 
00122 int ast_hashtab_newsize_java(struct ast_hashtab *tab)
00123 {
00124    int i = (tab->hash_tab_size << 1); /* multiply by two */
00125    
00126    while (!ast_is_prime(i))
00127       i++;
00128 
00129    return i;
00130 }
00131 
00132 int ast_hashtab_newsize_tight(struct ast_hashtab *tab)
00133 {
00134    int x = (tab->hash_tab_size << 1);
00135    int i = (tab->hash_tab_size + x);
00136    
00137    while (!ast_is_prime(i))
00138       i++;
00139 
00140    return i;
00141 }
00142 
00143 int ast_hashtab_newsize_none(struct ast_hashtab *tab) /* always return current size -- no resizing */
00144 {
00145    return tab->hash_tab_size;
00146 }
00147 
00148 unsigned int ast_hashtab_hash_string(const void *obj)
00149 {
00150    unsigned char *str = (unsigned char *) obj;
00151    unsigned int total;
00152 
00153    for (total = 0; *str; str++)
00154    {
00155       unsigned int tmp = total;
00156       total <<= 1; /* multiply by 2 */
00157       total += tmp; /* multiply by 3 */
00158       total <<= 2; /* multiply by 12 */
00159       total += tmp; /* multiply by 13 */
00160       
00161       total += ((unsigned int)(*str));
00162    }
00163    return total;
00164 }
00165 
00166 unsigned int ast_hashtab_hash_string_sax(const void *obj) /* from Josh */
00167 {
00168    const unsigned char *str = obj;
00169    unsigned int total = 0, c = 0;
00170 
00171    while ((c = *str++))
00172       total ^= (total << 5) + (total >> 2) + (total << 10) + c;
00173 
00174    return total;
00175 }
00176 
00177 unsigned int ast_hashtab_hash_string_nocase(const void *obj)
00178 {
00179    const unsigned char *str = obj;
00180    unsigned int total;
00181 
00182    for (total = 0; *str; str++) {
00183       unsigned int tmp = total;
00184       unsigned int charval = toupper(*str);
00185 
00186       /* hopefully, the following is faster than multiplication by 7 */
00187       /* why do I go to this bother? A good compiler will do this 
00188          anyway, if I say total *= 13 */
00189       /* BTW, tried *= 7, and it doesn't do as well in spreading things around! */
00190       total <<= 1; /* multiply by 2 */
00191       total += tmp; /* multiply by 3 */
00192       total <<= 2; /* multiply by 12 */
00193       total += tmp; /* multiply by 13 */
00194       
00195       total += (charval);
00196    }
00197 
00198    return total;
00199 }
00200 
00201 unsigned int ast_hashtab_hash_int(const int x)
00202 {
00203    return x;
00204 }
00205 
00206 unsigned int ast_hashtab_hash_short(const short x)
00207 {
00208    /* hmmmm.... modulus is best < 65535 !! */
00209    return x;
00210 }
00211 
00212 struct ast_hashtab *
00213 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00214 _ast_hashtab_create
00215 #else
00216 ast_hashtab_create
00217 #endif
00218 (int initial_buckets, 
00219    int (*compare)(const void *a, const void *b), 
00220    int (*resize)(struct ast_hashtab *), 
00221    int (*newsize)(struct ast_hashtab *tab),
00222    unsigned int (*hash)(const void *obj), 
00223    int do_locking
00224 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00225    , const char *file, int lineno, const char *function
00226 #endif
00227 )
00228 {
00229    struct ast_hashtab *ht;
00230 
00231 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00232    if (!(ht = __ast_calloc(1, sizeof(*ht), file, lineno, function)))
00233 #else
00234    if (!(ht = ast_calloc(1, sizeof(*ht))))
00235 #endif
00236       return NULL;
00237 
00238    while (!ast_is_prime(initial_buckets)) /* make sure this is prime */
00239       initial_buckets++;
00240 
00241 #if (defined(MALLOC_DEBUG) && !defined(STANDALONE))
00242    if (!(ht->array = __ast_calloc(initial_buckets, sizeof(*(ht->array)), file, lineno, function))) {
00243 #else
00244    if (!(ht->array = ast_calloc(initial_buckets, sizeof(*(ht->array))))) {
00245 #endif
00246       free(ht);
00247       return NULL;
00248    }
00249 
00250    ht->hash_tab_size = initial_buckets;
00251    ht->compare = compare;
00252    ht->resize = resize;
00253    ht->newsize = newsize;
00254    ht->hash = hash;
00255    ht->do_locking = do_locking;
00256 
00257    if (do_locking)
00258       ast_rwlock_init(&ht->lock);
00259 
00260    if (!ht->resize)
00261       ht->resize = ast_hashtab_resize_java;
00262 
00263    if (!ht->newsize)
00264       ht->newsize = ast_hashtab_newsize_java;
00265 
00266    return ht;
00267 }
00268 
00269 struct ast_hashtab *ast_hashtab_dup(struct ast_hashtab *tab, void *(*obj_dup_func)(const void *obj))
00270 {
00271    struct ast_hashtab *ht;
00272    unsigned int i;
00273 
00274    if (!(ht = ast_calloc(1, sizeof(*ht))))
00275       return NULL;
00276 
00277    if (!(ht->array = ast_calloc(tab->hash_tab_size, sizeof(*(ht->array))))) {
00278       free(ht);
00279       return NULL;
00280    }
00281 
00282    ht->hash_tab_size = tab->hash_tab_size;
00283    ht->compare = tab->compare;
00284    ht->resize = tab->resize;
00285    ht->newsize = tab->newsize;
00286    ht->hash = tab->hash;
00287    ht->do_locking = tab->do_locking;
00288 
00289    if (ht->do_locking)
00290       ast_rwlock_init(&ht->lock);
00291 
00292    /* now, dup the objects in the buckets and get them into the table */
00293    /* the fast way is to use the existing array index, and not have to hash
00294       the objects again */
00295    for (i = 0; i < ht->hash_tab_size; i++) {
00296       struct ast_hashtab_bucket *b = tab->array[i];
00297       while (b) {
00298          void *newobj = (*obj_dup_func)(b->object);
00299          if (newobj)
00300             ast_hashtab_insert_immediate_bucket(ht, newobj, i);
00301          b = b->next;
00302       }
00303    }
00304 
00305    return ht;
00306 }
00307 
00308 static void tlist_del_item(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
00309 {
00310    /* item had better be in the list! or suffer the weirdness that occurs, later! */
00311    if (*head == item) { /* first item in the list */
00312       *head = item->tnext;
00313       if (item->tnext)
00314          item->tnext->tprev = NULL;
00315    } else {
00316       /* short circuit stuff */
00317       item->tprev->tnext = item->tnext;
00318       if (item->tnext)
00319          item->tnext->tprev = item->tprev;
00320    }
00321 }
00322 
00323 static void tlist_add_head(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
00324 {
00325    if (*head) {
00326       item->tnext = *head;
00327       item->tprev = NULL;
00328       (*head)->tprev = item;
00329       *head = item;
00330    } else {
00331       /* the list is empty */
00332       *head = item;
00333       item->tprev = NULL;
00334       item->tnext = NULL;
00335    }
00336 }
00337 
00338 /* user-controlled hashtab locking. Create a hashtab without locking, then call the
00339    following locking routines yourself to lock the table between threads. */
00340 
00341 void ast_hashtab_wrlock(struct ast_hashtab *tab)
00342 {
00343    ast_rwlock_wrlock(&tab->lock);
00344 }
00345 
00346 void ast_hashtab_rdlock(struct ast_hashtab *tab)
00347 {
00348    ast_rwlock_rdlock(&tab->lock);
00349 }
00350 
00351 void ast_hashtab_initlock(struct ast_hashtab *tab)
00352 {
00353    ast_rwlock_init(&tab->lock);
00354 }
00355 
00356 void ast_hashtab_destroylock(struct ast_hashtab *tab)
00357 {
00358    ast_rwlock_destroy(&tab->lock);
00359 }
00360 
00361 void ast_hashtab_unlock(struct ast_hashtab *tab)
00362 {
00363    ast_rwlock_unlock(&tab->lock);
00364 }
00365 
00366 void ast_hashtab_destroy( struct ast_hashtab *tab, void (*objdestroyfunc)(void *obj))
00367 {
00368    /* this func will free the hash table and all its memory. It
00369       doesn't touch the objects stored in it */
00370    if (tab) {
00371       
00372       if (tab->do_locking)
00373          ast_rwlock_wrlock(&tab->lock);
00374 
00375       if (tab->array) {
00376          /* go thru and destroy the buckets */
00377          struct ast_hashtab_bucket *t;
00378          int i;
00379          
00380          while (tab->tlist) {
00381             t = tab->tlist;
00382             if (t->object && objdestroyfunc)
00383                (*objdestroyfunc)((void *) t->object); /* I cast this because I'm not going to MOD it, I'm going to DESTROY it */
00384             
00385             tlist_del_item(&(tab->tlist), tab->tlist);
00386             free(t);
00387          }
00388          
00389          for (i = 0; i < tab->hash_tab_size; i++)
00390             tab->array[i] = NULL; /* not totally necc., but best to destroy old ptrs */
00391          
00392          free(tab->array);
00393       }
00394       if (tab->do_locking) {
00395          ast_rwlock_unlock(&tab->lock);
00396          ast_rwlock_destroy(&tab->lock);
00397       }
00398       free(tab);
00399    }
00400 }
00401 
00402 int ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj)
00403 {
00404    unsigned int h;
00405    int res=0;
00406    
00407    if (!tab || !obj)
00408       return res;
00409 
00410    if (tab->do_locking)
00411       ast_rwlock_wrlock(&tab->lock);
00412 
00413    h = (*tab->hash)(obj) % tab->hash_tab_size;
00414 
00415    res = ast_hashtab_insert_immediate_bucket(tab,obj,h);
00416 
00417    if (tab->do_locking)
00418       ast_rwlock_unlock(&tab->lock);
00419 
00420    return res;
00421 }
00422 
00423 int ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h)
00424 {
00425    int c;
00426    struct ast_hashtab_bucket *b;
00427    
00428    if (!tab || !obj)
00429       return 0;
00430    
00431    for (c = 0, b = tab->array[h]; b; b= b->next)
00432       c++;
00433 
00434    if (c + 1 > tab->largest_bucket_size)
00435       tab->largest_bucket_size = c + 1;
00436 
00437    if (!(b = ast_calloc(1, sizeof(*b))))
00438       return 0;
00439 
00440    b->object = obj;
00441    b->next = tab->array[h];
00442    tab->array[h] = b;
00443 
00444    if (b->next)
00445       b->next->prev = b;
00446 
00447    tlist_add_head(&(tab->tlist), b);
00448    tab->hash_tab_elements++;
00449 
00450    if ((*tab->resize)(tab))
00451       ast_hashtab_resize(tab);
00452 
00453    return 1;
00454 }
00455 
00456 int ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj)
00457 {
00458    /* check to see if the element is already there; insert only if
00459       it is not there. */
00460    /* will force a resize if the resize func returns 1 */
00461    /* returns 1 on success, 0 if there's a problem, or it's already there. */
00462    unsigned int bucket = 0;
00463 
00464    if (tab->do_locking)
00465       ast_rwlock_wrlock(&tab->lock);
00466 
00467    if (!ast_hashtab_lookup_bucket(tab, obj, &bucket)) {
00468       int ret2 = ast_hashtab_insert_immediate_bucket(tab, obj, bucket);
00469 
00470       if (tab->do_locking)
00471          ast_rwlock_unlock(&tab->lock);
00472       
00473       return ret2;
00474    }
00475 
00476    if (tab->do_locking)
00477       ast_rwlock_unlock(&tab->lock);
00478       
00479    return 0;
00480 }
00481 
00482 void *ast_hashtab_lookup(struct ast_hashtab *tab, const void *obj)
00483 {
00484    /* lookup this object in the hash table. return a ptr if found, or NULL if not */
00485    unsigned int h;
00486    void *ret;
00487 
00488    if (!tab || !obj)
00489       return 0;
00490    
00491    if (tab->do_locking)
00492       ast_rwlock_rdlock(&tab->lock);
00493 
00494    h = (*tab->hash)(obj) % tab->hash_tab_size;
00495 
00496    ret = ast_hashtab_lookup_internal(tab,obj,h);
00497 
00498    if (tab->do_locking)
00499       ast_rwlock_unlock(&tab->lock);
00500 
00501    return ret;
00502 }
00503 
00504 
00505 void *ast_hashtab_lookup_with_hash(struct ast_hashtab *tab, const void *obj, unsigned int hashval)
00506 {
00507    /* lookup this object in the hash table. return a ptr if found, or NULL if not */
00508    unsigned int h;
00509    void *ret;
00510 
00511    if (!tab || !obj)
00512       return 0;
00513    
00514    if (tab->do_locking)
00515       ast_rwlock_rdlock(&tab->lock);
00516       
00517    h = hashval % tab->hash_tab_size;
00518 
00519    ret = ast_hashtab_lookup_internal(tab,obj,h);
00520    
00521    if (tab->do_locking)
00522       ast_rwlock_unlock(&tab->lock);
00523 
00524    return ret;
00525 }
00526 
00527 void *ast_hashtab_lookup_bucket(struct ast_hashtab *tab, const void *obj, unsigned int *bucket)
00528 {
00529    /* lookup this object in the hash table. return a ptr if found, or NULL if not */
00530    unsigned int h;
00531    void *ret;
00532 
00533    if (!tab || !obj)
00534       return 0;
00535    
00536    h = (*tab->hash)(obj) % tab->hash_tab_size;
00537    
00538    ret = ast_hashtab_lookup_internal(tab,obj,h);
00539    
00540    *bucket = h; 
00541    
00542    return ret;
00543 }
00544 
00545 static void *ast_hashtab_lookup_internal(struct ast_hashtab *tab, const void *obj, unsigned int h)
00546 {
00547    struct ast_hashtab_bucket *b;
00548 
00549    for (b = tab->array[h]; b; b = b->next) {
00550       if (!(*tab->compare)(obj,b->object)) {
00551          return (void*) b->object; /* I can't touch obj in this func, but the outside world is welcome to */
00552       }
00553    }
00554 
00555    return NULL;
00556 }
00557 
00558 void ast_hashtab_get_stats( struct ast_hashtab *tab, int *biggest_bucket_size, int *resize_count, int *num_objects, int *num_buckets)
00559 {
00560    /* returns key stats for the table */
00561    if (tab->do_locking)
00562       ast_rwlock_rdlock(&tab->lock);
00563    *biggest_bucket_size = tab->largest_bucket_size;
00564    *resize_count = tab->resize_count;
00565    *num_objects = tab->hash_tab_elements;
00566    *num_buckets = tab->hash_tab_size;
00567    if (tab->do_locking)
00568       ast_rwlock_unlock(&tab->lock);
00569 }
00570 
00571    /* this function returns the number of elements stored in the hashtab */
00572 int  ast_hashtab_size( struct ast_hashtab *tab)
00573 {
00574    return tab->hash_tab_elements;
00575 }
00576 
00577    /* this function returns the size of the bucket array in the hashtab */
00578 int  ast_hashtab_capacity( struct ast_hashtab *tab)
00579 {
00580    return tab->hash_tab_size;
00581 }
00582 
00583 
00584 
00585 /* the insert operation calls this, and is wrlock'd when it does. */
00586 /* if you want to call it, you should set the wrlock yourself */
00587 
00588 
00589 static void ast_hashtab_resize( struct ast_hashtab *tab)
00590 {
00591    /* this function is called either internally, when the resize func returns 1, or
00592       externally by the user to force a resize of the hash table */
00593    int newsize = (*tab->newsize)(tab), i, c;
00594    unsigned int h;
00595    struct ast_hashtab_bucket *b,*bn;
00596    
00597    /* Since we keep a DLL of all the buckets in tlist,
00598       all we have to do is free the array, malloc a new one,
00599       and then go thru the tlist array and reassign them into 
00600       the bucket arrayj.
00601    */
00602    for (i = 0; i < tab->hash_tab_size; i++) { /* don't absolutely have to do this, but
00603                                  why leave ptrs laying around */
00604       tab->array[i] = 0; /* erase old ptrs */
00605    }
00606    free(tab->array);
00607    if (!(tab->array = ast_calloc(newsize, sizeof(*(tab->array)))))
00608       return;
00609 
00610    /* now sort the buckets into their rightful new slots */
00611    tab->resize_count++;
00612    tab->hash_tab_size = newsize;
00613    tab->largest_bucket_size = 0;
00614 
00615    for (b = tab->tlist; b; b = bn) {
00616       b->prev = 0;
00617       bn = b->tnext;
00618       h = (*tab->hash)(b->object) % tab->hash_tab_size;
00619       b->next = tab->array[h];
00620       if (b->next)
00621          b->next->prev = b;
00622       tab->array[h] = b;
00623    }
00624    /* recalc the largest bucket size */
00625    for (i = 0; i < tab->hash_tab_size; i++) {
00626       for (c = 0, b = tab->array[i]; b; b = b->next)
00627          c++;
00628       if (c > tab->largest_bucket_size)
00629          tab->largest_bucket_size = c;
00630    }
00631 }
00632 
00633 struct ast_hashtab_iter *ast_hashtab_start_traversal(struct ast_hashtab *tab)
00634 {
00635    /* returns an iterator */
00636    struct ast_hashtab_iter *it;
00637    
00638    if (!(it = ast_calloc(1, sizeof(*it))))
00639       return NULL;
00640 
00641    it->next = tab->tlist;
00642    it->tab = tab;
00643    if (tab->do_locking)
00644       ast_rwlock_rdlock(&tab->lock);
00645 
00646    return it;
00647 }
00648 
00649 /* use this function to get a write lock */
00650 struct ast_hashtab_iter *ast_hashtab_start_write_traversal(struct ast_hashtab *tab)
00651 {
00652    /* returns an iterator */
00653    struct ast_hashtab_iter *it;
00654    
00655    if (!(it = ast_calloc(1, sizeof(*it))))
00656       return NULL;
00657 
00658    it->next = tab->tlist;
00659    it->tab = tab;
00660    if (tab->do_locking)
00661       ast_rwlock_wrlock(&tab->lock);
00662 
00663    return it;
00664 }
00665 
00666 void ast_hashtab_end_traversal(struct ast_hashtab_iter *it)
00667 {
00668    if (it->tab->do_locking)
00669       ast_rwlock_unlock(&it->tab->lock);
00670    free(it);
00671 }
00672 
00673 void *ast_hashtab_next(struct ast_hashtab_iter *it)
00674 {
00675    /* returns the next object in the list, advances iter one step */
00676    struct ast_hashtab_bucket *retval;
00677    
00678    if (it && it->next) { /* there's a next in the bucket list */
00679       retval = it->next;
00680       it->next = retval->tnext;
00681       return (void *) retval->object;
00682    }
00683 
00684    return NULL;
00685 }
00686 
00687 static void *ast_hashtab_remove_object_internal(struct ast_hashtab *tab, struct ast_hashtab_bucket *b, int h)
00688 {
00689    const void *obj2;
00690    
00691    if (b->prev)
00692       b->prev->next = b->next;
00693    else
00694       tab->array[h] = b->next;
00695    
00696    if (b->next)
00697       b->next->prev = b->prev;
00698    
00699    tlist_del_item(&(tab->tlist), b);
00700    
00701    obj2 = b->object;
00702    b->object = b->next = (void*)2;
00703    free(b); /* free up the hashbucket */
00704    tab->hash_tab_elements--;
00705 #ifdef DEBUG
00706    {
00707       int c2;
00708       struct ast_hashtab_bucket *b2;
00709       /* do a little checking */
00710       for (c2 = 0, b2 = tab->tlist; b2; b2 = b2->tnext) {
00711          c2++;
00712       }
00713       if (c2 != tab->hash_tab_elements) {
00714          printf("Hey! we didn't delete right! there are %d elements in the list, and we expected %d\n",
00715                c2, tab->hash_tab_elements);
00716       }
00717       for (c2 = 0, b2 = tab->tlist; b2; b2 = b2->tnext) {
00718          unsigned int obj3 = (unsigned long) obj2;
00719          unsigned int b3 = (unsigned long) b;
00720          if (b2->object == obj2)
00721             printf("Hey-- you've still got a bucket pointing at ht_element %x\n", obj3);
00722          if (b2->next == b)
00723             printf("Hey-- you've still got a bucket with next ptr pointing to deleted bucket %x\n", b3);
00724          if (b2->prev == b)
00725             printf("Hey-- you've still got a bucket with prev ptr pointing to deleted bucket %x\n", b3);
00726          if (b2->tprev == b)
00727             printf("Hey-- you've still got a bucket with tprev ptr pointing to deleted bucket %x\n", b3);
00728          if (b2->tnext == b)
00729             printf("Hey-- you've still got a bucket with tnext ptr pointing to deleted bucket %x\n", b3);
00730       }
00731    }
00732 #endif
00733    return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
00734 }
00735 
00736 void *ast_hashtab_remove_object_via_lookup(struct ast_hashtab *tab, void *obj)
00737 {
00738    /* looks up the object; removes the corresponding bucket */
00739    const void *obj2;
00740 
00741    if (!tab || !obj)
00742       return 0;
00743 
00744    if (tab->do_locking)
00745       ast_rwlock_wrlock(&tab->lock);
00746 
00747    obj2 = ast_hashtab_remove_object_via_lookup_nolock(tab,obj);
00748 
00749    if (tab->do_locking)
00750       ast_rwlock_unlock(&tab->lock);
00751 
00752    return (void *)obj2;
00753 }
00754 
00755 void *ast_hashtab_remove_object_via_lookup_nolock(struct ast_hashtab *tab, void *obj)
00756 {
00757    /* looks up the object; removes the corresponding bucket */
00758    unsigned int h;
00759    struct ast_hashtab_bucket *b;
00760 
00761    if (!tab || !obj)
00762       return 0;
00763 
00764    h = (*tab->hash)(obj) % tab->hash_tab_size;
00765    for (b = tab->array[h]; b; b = b->next) {
00766       
00767       if (!(*tab->compare)(obj, b->object)) {
00768          const void *obj2;
00769 
00770          obj2 = ast_hashtab_remove_object_internal(tab, b, h);
00771          
00772          return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
00773       }
00774    }
00775 
00776    return 0;
00777 }
00778 
00779 void *ast_hashtab_remove_this_object(struct ast_hashtab *tab, void *obj)
00780 {
00781    /* looks up the object by hash and then comparing pts in bucket list instead of
00782       calling the compare routine; removes the bucket -- a slightly cheaper operation */
00783    /* looks up the object; removes the corresponding bucket */
00784    const void *obj2;
00785 
00786    if (!tab || !obj)
00787       return 0;
00788  
00789    if (tab->do_locking)
00790       ast_rwlock_wrlock(&tab->lock);
00791 
00792    obj2 = ast_hashtab_remove_this_object_nolock(tab,obj);
00793    
00794    if (tab->do_locking)
00795       ast_rwlock_unlock(&tab->lock);
00796 
00797    return (void *)obj2;
00798 }
00799 
00800 void *ast_hashtab_remove_this_object_nolock(struct ast_hashtab *tab, void *obj)
00801 {
00802    /* looks up the object by hash and then comparing pts in bucket list instead of
00803       calling the compare routine; removes the bucket -- a slightly cheaper operation */
00804    /* looks up the object; removes the corresponding bucket */
00805    unsigned int h;
00806    struct ast_hashtab_bucket *b;
00807 
00808    if (!tab || !obj)
00809       return 0;
00810  
00811    h = (*tab->hash)(obj) % tab->hash_tab_size;
00812    for (b = tab->array[h]; b; b = b->next) {
00813       
00814       if (obj == b->object) {
00815          const void *obj2;
00816          obj2 = ast_hashtab_remove_object_internal(tab, b, h);
00817          
00818          return (void *) obj2; /* inside this code, the obj's are untouchable, but outside, they aren't */
00819       }
00820    }
00821 
00822    return 0;
00823 }

Generated on Wed Oct 28 11:51:04 2009 for Asterisk - the Open Source PBX by  doxygen 1.5.6