00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
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
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);
00088 }
00089
00090 int ast_hashtab_resize_none(struct ast_hashtab *tab)
00091 {
00092 return 0;
00093 }
00094
00095 int ast_is_prime(int num)
00096 {
00097 int tnum, limit;
00098
00099 if (!(num & 0x1))
00100 return 0;
00101
00102
00103
00104 tnum = 3;
00105 limit = num;
00106 while (tnum < limit) {
00107 if (!(num % tnum))
00108 return 0;
00109
00110
00111 limit = num / tnum;
00112
00113
00114 tnum = tnum + 2;
00115 }
00116
00117
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);
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)
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;
00157 total += tmp;
00158 total <<= 2;
00159 total += tmp;
00160
00161 total += ((unsigned int)(*str));
00162 }
00163 return total;
00164 }
00165
00166 unsigned int ast_hashtab_hash_string_sax(const void *obj)
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
00187
00188
00189
00190 total <<= 1;
00191 total += tmp;
00192 total <<= 2;
00193 total += tmp;
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
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))
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
00293
00294
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
00311 if (*head == item) {
00312 *head = item->tnext;
00313 if (item->tnext)
00314 item->tnext->tprev = NULL;
00315 } else {
00316
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
00332 *head = item;
00333 item->tprev = NULL;
00334 item->tnext = NULL;
00335 }
00336 }
00337
00338
00339
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
00369
00370 if (tab) {
00371
00372 if (tab->do_locking)
00373 ast_rwlock_wrlock(&tab->lock);
00374
00375 if (tab->array) {
00376
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);
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;
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
00459
00460
00461
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
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
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
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;
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
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
00572 int ast_hashtab_size( struct ast_hashtab *tab)
00573 {
00574 return tab->hash_tab_elements;
00575 }
00576
00577
00578 int ast_hashtab_capacity( struct ast_hashtab *tab)
00579 {
00580 return tab->hash_tab_size;
00581 }
00582
00583
00584
00585
00586
00587
00588
00589 static void ast_hashtab_resize( struct ast_hashtab *tab)
00590 {
00591
00592
00593 int newsize = (*tab->newsize)(tab), i, c;
00594 unsigned int h;
00595 struct ast_hashtab_bucket *b,*bn;
00596
00597
00598
00599
00600
00601
00602 for (i = 0; i < tab->hash_tab_size; i++) {
00603
00604 tab->array[i] = 0;
00605 }
00606 free(tab->array);
00607 if (!(tab->array = ast_calloc(newsize, sizeof(*(tab->array)))))
00608 return;
00609
00610
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
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
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
00650 struct ast_hashtab_iter *ast_hashtab_start_write_traversal(struct ast_hashtab *tab)
00651 {
00652
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
00676 struct ast_hashtab_bucket *retval;
00677
00678 if (it && it->next) {
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);
00704 tab->hash_tab_elements--;
00705 #ifdef DEBUG
00706 {
00707 int c2;
00708 struct ast_hashtab_bucket *b2;
00709
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;
00734 }
00735
00736 void *ast_hashtab_remove_object_via_lookup(struct ast_hashtab *tab, void *obj)
00737 {
00738
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
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;
00773 }
00774 }
00775
00776 return 0;
00777 }
00778
00779 void *ast_hashtab_remove_this_object(struct ast_hashtab *tab, void *obj)
00780 {
00781
00782
00783
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
00803
00804
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;
00819 }
00820 }
00821
00822 return 0;
00823 }