Wed Aug 7 17:15:42 2019

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

Generated on 7 Aug 2019 for Asterisk - The Open Source Telephony Project by  doxygen 1.6.1