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: 132051 $")
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 *ast_hashtab_create(int initial_buckets,
00213 int (*compare)(const void *a, const void *b),
00214 int (*resize)(struct ast_hashtab *),
00215 int (*newsize)(struct ast_hashtab *tab),
00216 unsigned int (*hash)(const void *obj),
00217 int do_locking)
00218 {
00219 struct ast_hashtab *ht;
00220
00221 if (!(ht = ast_calloc(1, sizeof(*ht))))
00222 return NULL;
00223
00224 while (!ast_is_prime(initial_buckets))
00225 initial_buckets++;
00226
00227 if (!(ht->array = ast_calloc(initial_buckets, sizeof(*(ht->array))))) {
00228 free(ht);
00229 return NULL;
00230 }
00231
00232 ht->hash_tab_size = initial_buckets;
00233 ht->compare = compare;
00234 ht->resize = resize;
00235 ht->newsize = newsize;
00236 ht->hash = hash;
00237 ht->do_locking = do_locking;
00238
00239 if (do_locking)
00240 ast_rwlock_init(&ht->lock);
00241
00242 if (!ht->resize)
00243 ht->resize = ast_hashtab_resize_java;
00244
00245 if (!ht->newsize)
00246 ht->newsize = ast_hashtab_newsize_java;
00247
00248 return ht;
00249 }
00250
00251 struct ast_hashtab *ast_hashtab_dup(struct ast_hashtab *tab, void *(*obj_dup_func)(const void *obj))
00252 {
00253 struct ast_hashtab *ht;
00254 unsigned int i;
00255
00256 if (!(ht = ast_calloc(1, sizeof(*ht))))
00257 return NULL;
00258
00259 if (!(ht->array = ast_calloc(tab->hash_tab_size, sizeof(*(ht->array))))) {
00260 free(ht);
00261 return NULL;
00262 }
00263
00264 ht->hash_tab_size = tab->hash_tab_size;
00265 ht->compare = tab->compare;
00266 ht->resize = tab->resize;
00267 ht->newsize = tab->newsize;
00268 ht->hash = tab->hash;
00269 ht->do_locking = tab->do_locking;
00270
00271 if (ht->do_locking)
00272 ast_rwlock_init(&ht->lock);
00273
00274
00275
00276
00277 for (i = 0; i < ht->hash_tab_size; i++) {
00278 struct ast_hashtab_bucket *b = tab->array[i];
00279 while (b) {
00280 void *newobj = (*obj_dup_func)(b->object);
00281 if (newobj)
00282 ast_hashtab_insert_immediate_bucket(ht, newobj, i);
00283 b = b->next;
00284 }
00285 }
00286
00287 return ht;
00288 }
00289
00290 static void tlist_del_item(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
00291 {
00292
00293 if (*head == item) {
00294 *head = item->tnext;
00295 if (item->tnext)
00296 item->tnext->tprev = NULL;
00297 } else {
00298
00299 item->tprev->tnext = item->tnext;
00300 if (item->tnext)
00301 item->tnext->tprev = item->tprev;
00302 }
00303 }
00304
00305 static void tlist_add_head(struct ast_hashtab_bucket **head, struct ast_hashtab_bucket *item)
00306 {
00307 if (*head) {
00308 item->tnext = *head;
00309 item->tprev = NULL;
00310 (*head)->tprev = item;
00311 *head = item;
00312 } else {
00313
00314 *head = item;
00315 item->tprev = NULL;
00316 item->tnext = NULL;
00317 }
00318 }
00319
00320
00321
00322
00323 void ast_hashtab_wrlock(struct ast_hashtab *tab)
00324 {
00325 ast_rwlock_wrlock(&tab->lock);
00326 }
00327
00328 void ast_hashtab_rdlock(struct ast_hashtab *tab)
00329 {
00330 ast_rwlock_rdlock(&tab->lock);
00331 }
00332
00333 void ast_hashtab_initlock(struct ast_hashtab *tab)
00334 {
00335 ast_rwlock_init(&tab->lock);
00336 }
00337
00338 void ast_hashtab_destroylock(struct ast_hashtab *tab)
00339 {
00340 ast_rwlock_destroy(&tab->lock);
00341 }
00342
00343 void ast_hashtab_unlock(struct ast_hashtab *tab)
00344 {
00345 ast_rwlock_unlock(&tab->lock);
00346 }
00347
00348 void ast_hashtab_destroy( struct ast_hashtab *tab, void (*objdestroyfunc)(void *obj))
00349 {
00350
00351
00352 if (tab) {
00353
00354 if (tab->do_locking)
00355 ast_rwlock_wrlock(&tab->lock);
00356
00357 if (tab->array) {
00358
00359 struct ast_hashtab_bucket *t;
00360 int i;
00361
00362 while (tab->tlist) {
00363 t = tab->tlist;
00364 if (t->object && objdestroyfunc)
00365 (*objdestroyfunc)((void *) t->object);
00366
00367 tlist_del_item(&(tab->tlist), tab->tlist);
00368 free(t);
00369 }
00370
00371 for (i = 0; i < tab->hash_tab_size; i++)
00372 tab->array[i] = NULL;
00373
00374 free(tab->array);
00375 }
00376 if (tab->do_locking) {
00377 ast_rwlock_unlock(&tab->lock);
00378 ast_rwlock_destroy(&tab->lock);
00379 }
00380 free(tab);
00381 }
00382 }
00383
00384 int ast_hashtab_insert_immediate(struct ast_hashtab *tab, const void *obj)
00385 {
00386 unsigned int h;
00387 int res=0;
00388
00389 if (!tab || !obj)
00390 return res;
00391
00392 if (tab->do_locking)
00393 ast_rwlock_wrlock(&tab->lock);
00394
00395 h = (*tab->hash)(obj) % tab->hash_tab_size;
00396
00397 res = ast_hashtab_insert_immediate_bucket(tab,obj,h);
00398
00399 if (tab->do_locking)
00400 ast_rwlock_unlock(&tab->lock);
00401
00402 return res;
00403 }
00404
00405 int ast_hashtab_insert_immediate_bucket(struct ast_hashtab *tab, const void *obj, unsigned int h)
00406 {
00407 int c;
00408 struct ast_hashtab_bucket *b;
00409
00410 if (!tab || !obj)
00411 return 0;
00412
00413 for (c = 0, b = tab->array[h]; b; b= b->next)
00414 c++;
00415
00416 if (c + 1 > tab->largest_bucket_size)
00417 tab->largest_bucket_size = c + 1;
00418
00419 if (!(b = ast_calloc(1, sizeof(*b))))
00420 return 0;
00421
00422 b->object = obj;
00423 b->next = tab->array[h];
00424 tab->array[h] = b;
00425
00426 if (b->next)
00427 b->next->prev = b;
00428
00429 tlist_add_head(&(tab->tlist), b);
00430 tab->hash_tab_elements++;
00431
00432 if ((*tab->resize)(tab))
00433 ast_hashtab_resize(tab);
00434
00435 return 1;
00436 }
00437
00438 int ast_hashtab_insert_safe(struct ast_hashtab *tab, const void *obj)
00439 {
00440
00441
00442
00443
00444 unsigned int bucket = 0;
00445
00446 if (tab->do_locking)
00447 ast_rwlock_wrlock(&tab->lock);
00448
00449 if (!ast_hashtab_lookup_bucket(tab, obj, &bucket)) {
00450 int ret2 = ast_hashtab_insert_immediate_bucket(tab, obj, bucket);
00451
00452 if (tab->do_locking)
00453 ast_rwlock_unlock(&tab->lock);
00454
00455 return ret2;
00456 }
00457
00458 if (tab->do_locking)
00459 ast_rwlock_unlock(&tab->lock);
00460
00461 return 0;
00462 }
00463
00464 void *ast_hashtab_lookup(struct ast_hashtab *tab, const void *obj)
00465 {
00466
00467 unsigned int h;
00468 void *ret;
00469
00470 if (!tab || !obj)
00471 return 0;
00472
00473 if (tab->do_locking)
00474 ast_rwlock_rdlock(&tab->lock);
00475
00476 h = (*tab->hash)(obj) % tab->hash_tab_size;
00477
00478 ret = ast_hashtab_lookup_internal(tab,obj,h);
00479
00480 if (tab->do_locking)
00481 ast_rwlock_unlock(&tab->lock);
00482
00483 return ret;
00484 }
00485
00486
00487 void *ast_hashtab_lookup_with_hash(struct ast_hashtab *tab, const void *obj, unsigned int hashval)
00488 {
00489
00490 unsigned int h;
00491 void *ret;
00492
00493 if (!tab || !obj)
00494 return 0;
00495
00496 if (tab->do_locking)
00497 ast_rwlock_rdlock(&tab->lock);
00498
00499 h = hashval % tab->hash_tab_size;
00500
00501 ret = ast_hashtab_lookup_internal(tab,obj,h);
00502
00503 if (tab->do_locking)
00504 ast_rwlock_unlock(&tab->lock);
00505
00506 return ret;
00507 }
00508
00509 void *ast_hashtab_lookup_bucket(struct ast_hashtab *tab, const void *obj, unsigned int *bucket)
00510 {
00511
00512 unsigned int h;
00513 void *ret;
00514
00515 if (!tab || !obj)
00516 return 0;
00517
00518 h = (*tab->hash)(obj) % tab->hash_tab_size;
00519
00520 ret = ast_hashtab_lookup_internal(tab,obj,h);
00521
00522 *bucket = h;
00523
00524 return ret;
00525 }
00526
00527 static void *ast_hashtab_lookup_internal(struct ast_hashtab *tab, const void *obj, unsigned int h)
00528 {
00529 struct ast_hashtab_bucket *b;
00530
00531 for (b = tab->array[h]; b; b = b->next) {
00532 if (!(*tab->compare)(obj,b->object)) {
00533 return (void*) b->object;
00534 }
00535 }
00536
00537 return NULL;
00538 }
00539
00540 void ast_hashtab_get_stats( struct ast_hashtab *tab, int *biggest_bucket_size, int *resize_count, int *num_objects, int *num_buckets)
00541 {
00542
00543 if (tab->do_locking)
00544 ast_rwlock_rdlock(&tab->lock);
00545 *biggest_bucket_size = tab->largest_bucket_size;
00546 *resize_count = tab->resize_count;
00547 *num_objects = tab->hash_tab_elements;
00548 *num_buckets = tab->hash_tab_size;
00549 if (tab->do_locking)
00550 ast_rwlock_unlock(&tab->lock);
00551 }
00552
00553
00554 int ast_hashtab_size( struct ast_hashtab *tab)
00555 {
00556 return tab->hash_tab_elements;
00557 }
00558
00559
00560 int ast_hashtab_capacity( struct ast_hashtab *tab)
00561 {
00562 return tab->hash_tab_size;
00563 }
00564
00565
00566
00567
00568
00569
00570
00571 static void ast_hashtab_resize( struct ast_hashtab *tab)
00572 {
00573
00574
00575 int newsize = (*tab->newsize)(tab), i, c;
00576 unsigned int h;
00577 struct ast_hashtab_bucket *b,*bn;
00578
00579
00580
00581
00582
00583
00584 for (i = 0; i < tab->hash_tab_size; i++) {
00585
00586 tab->array[i] = 0;
00587 }
00588 free(tab->array);
00589 if (!(tab->array = ast_calloc(newsize, sizeof(*(tab->array)))))
00590 return;
00591
00592
00593 tab->resize_count++;
00594 tab->hash_tab_size = newsize;
00595 tab->largest_bucket_size = 0;
00596
00597 for (b = tab->tlist; b; b = bn) {
00598 b->prev = 0;
00599 bn = b->tnext;
00600 h = (*tab->hash)(b->object) % tab->hash_tab_size;
00601 b->next = tab->array[h];
00602 if (b->next)
00603 b->next->prev = b;
00604 tab->array[h] = b;
00605 }
00606
00607 for (i = 0; i < tab->hash_tab_size; i++) {
00608 for (c = 0, b = tab->array[i]; b; b = b->next)
00609 c++;
00610 if (c > tab->largest_bucket_size)
00611 tab->largest_bucket_size = c;
00612 }
00613 }
00614
00615 struct ast_hashtab_iter *ast_hashtab_start_traversal(struct ast_hashtab *tab)
00616 {
00617
00618 struct ast_hashtab_iter *it;
00619
00620 if (!(it = ast_calloc(1, sizeof(*it))))
00621 return NULL;
00622
00623 it->next = tab->tlist;
00624 it->tab = tab;
00625 if (tab->do_locking)
00626 ast_rwlock_rdlock(&tab->lock);
00627
00628 return it;
00629 }
00630
00631
00632 struct ast_hashtab_iter *ast_hashtab_start_write_traversal(struct ast_hashtab *tab)
00633 {
00634
00635 struct ast_hashtab_iter *it;
00636
00637 if (!(it = ast_calloc(1, sizeof(*it))))
00638 return NULL;
00639
00640 it->next = tab->tlist;
00641 it->tab = tab;
00642 if (tab->do_locking)
00643 ast_rwlock_wrlock(&tab->lock);
00644
00645 return it;
00646 }
00647
00648 void ast_hashtab_end_traversal(struct ast_hashtab_iter *it)
00649 {
00650 if (it->tab->do_locking)
00651 ast_rwlock_unlock(&it->tab->lock);
00652 free(it);
00653 }
00654
00655 void *ast_hashtab_next(struct ast_hashtab_iter *it)
00656 {
00657
00658 struct ast_hashtab_bucket *retval;
00659
00660 if (it && it->next) {
00661 retval = it->next;
00662 it->next = retval->tnext;
00663 return (void *) retval->object;
00664 }
00665
00666 return NULL;
00667 }
00668
00669 static void *ast_hashtab_remove_object_internal(struct ast_hashtab *tab, struct ast_hashtab_bucket *b, int h)
00670 {
00671 const void *obj2;
00672
00673 if (b->prev)
00674 b->prev->next = b->next;
00675 else
00676 tab->array[h] = b->next;
00677
00678 if (b->next)
00679 b->next->prev = b->prev;
00680
00681 tlist_del_item(&(tab->tlist), b);
00682
00683 obj2 = b->object;
00684 b->object = b->next = (void*)2;
00685 free(b);
00686 tab->hash_tab_elements--;
00687 #ifdef DEBUG
00688 {
00689 int c2;
00690 struct ast_hashtab_bucket *b2;
00691
00692 for (c2 = 0, b2 = tab->tlist; b2; b2 = b2->tnext) {
00693 c2++;
00694 }
00695 if (c2 != tab->hash_tab_elements) {
00696 printf("Hey! we didn't delete right! there are %d elements in the list, and we expected %d\n",
00697 c2, tab->hash_tab_elements);
00698 }
00699 for (c2 = 0, b2 = tab->tlist; b2; b2 = b2->tnext) {
00700 unsigned int obj3 = (unsigned long) obj2;
00701 unsigned int b3 = (unsigned long) b;
00702 if (b2->object == obj2)
00703 printf("Hey-- you've still got a bucket pointing at ht_element %x\n", obj3);
00704 if (b2->next == b)
00705 printf("Hey-- you've still got a bucket with next ptr pointing to deleted bucket %x\n", b3);
00706 if (b2->prev == b)
00707 printf("Hey-- you've still got a bucket with prev ptr pointing to deleted bucket %x\n", b3);
00708 if (b2->tprev == b)
00709 printf("Hey-- you've still got a bucket with tprev ptr pointing to deleted bucket %x\n", b3);
00710 if (b2->tnext == b)
00711 printf("Hey-- you've still got a bucket with tnext ptr pointing to deleted bucket %x\n", b3);
00712 }
00713 }
00714 #endif
00715 return (void *) obj2;
00716 }
00717
00718 void *ast_hashtab_remove_object_via_lookup(struct ast_hashtab *tab, void *obj)
00719 {
00720
00721 const void *obj2;
00722
00723 if (!tab || !obj)
00724 return 0;
00725
00726 if (tab->do_locking)
00727 ast_rwlock_wrlock(&tab->lock);
00728
00729 obj2 = ast_hashtab_remove_object_via_lookup_nolock(tab,obj);
00730
00731 if (tab->do_locking)
00732 ast_rwlock_unlock(&tab->lock);
00733
00734 return (void *)obj2;
00735 }
00736
00737 void *ast_hashtab_remove_object_via_lookup_nolock(struct ast_hashtab *tab, void *obj)
00738 {
00739
00740 unsigned int h;
00741 struct ast_hashtab_bucket *b;
00742
00743 if (!tab || !obj)
00744 return 0;
00745
00746 h = (*tab->hash)(obj) % tab->hash_tab_size;
00747 for (b = tab->array[h]; b; b = b->next) {
00748
00749 if (!(*tab->compare)(obj, b->object)) {
00750 const void *obj2;
00751
00752 obj2 = ast_hashtab_remove_object_internal(tab, b, h);
00753
00754 return (void *) obj2;
00755 }
00756 }
00757
00758 return 0;
00759 }
00760
00761 void *ast_hashtab_remove_this_object(struct ast_hashtab *tab, void *obj)
00762 {
00763
00764
00765
00766 const void *obj2;
00767
00768 if (!tab || !obj)
00769 return 0;
00770
00771 if (tab->do_locking)
00772 ast_rwlock_wrlock(&tab->lock);
00773
00774 obj2 = ast_hashtab_remove_this_object_nolock(tab,obj);
00775
00776 if (tab->do_locking)
00777 ast_rwlock_unlock(&tab->lock);
00778
00779 return (void *)obj2;
00780 }
00781
00782 void *ast_hashtab_remove_this_object_nolock(struct ast_hashtab *tab, void *obj)
00783 {
00784
00785
00786
00787 unsigned int h;
00788 struct ast_hashtab_bucket *b;
00789
00790 if (!tab || !obj)
00791 return 0;
00792
00793 h = (*tab->hash)(obj) % tab->hash_tab_size;
00794 for (b = tab->array[h]; b; b = b->next) {
00795
00796 if (obj == b->object) {
00797 const void *obj2;
00798 obj2 = ast_hashtab_remove_object_internal(tab, b, h);
00799
00800 return (void *) obj2;
00801 }
00802 }
00803
00804 return 0;
00805 }