Wed Apr 6 11:29:45 2011

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

Generated on Wed Apr 6 11:29:45 2011 for Asterisk - The Open Source Telephony Project by  doxygen 1.4.7