1/* 2 ******************************************************************************* 3 * Implementation of (2^1+,2) cuckoo hashing, where 2^1+ indicates that each 4 * hash bucket contains 2^n cells, for n >= 1, and 2 indicates that two hash 5 * functions are employed. The original cuckoo hashing algorithm was described 6 * in: 7 * 8 * Pagh, R., F.F. Rodler (2004) Cuckoo Hashing. Journal of Algorithms --- 56 unchanged lines hidden (view full) --- 65} 66 67/* 68 * Search table for key and return cell number if found; SIZE_T_MAX otherwise. 69 */ 70JEMALLOC_INLINE size_t 71ckh_isearch(ckh_t *ckh, const void *key) 72{ |
73 size_t hashes[2], bucket, cell; |
74 75 assert(ckh != NULL); 76 |
77 ckh->hash(key, hashes); |
78 79 /* Search primary bucket. */ |
80 bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1); |
81 cell = ckh_bucket_search(ckh, bucket, key); 82 if (cell != SIZE_T_MAX) 83 return (cell); 84 85 /* Search secondary bucket. */ |
86 bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); |
87 cell = ckh_bucket_search(ckh, bucket, key); 88 return (cell); 89} 90 91JEMALLOC_INLINE bool 92ckh_try_bucket_insert(ckh_t *ckh, size_t bucket, const void *key, 93 const void *data) 94{ --- 26 unchanged lines hidden (view full) --- 121 * eviction/relocation bucket cycle. 122 */ 123JEMALLOC_INLINE bool 124ckh_evict_reloc_insert(ckh_t *ckh, size_t argbucket, void const **argkey, 125 void const **argdata) 126{ 127 const void *key, *data, *tkey, *tdata; 128 ckhc_t *cell; |
129 size_t hashes[2], bucket, tbucket; |
130 unsigned i; 131 132 bucket = argbucket; 133 key = *argkey; 134 data = *argdata; 135 while (true) { 136 /* 137 * Choose a random item within the bucket to evict. This is --- 12 unchanged lines hidden (view full) --- 150 cell->key = key; cell->data = data; 151 key = tkey; data = tdata; 152 153#ifdef CKH_COUNT 154 ckh->nrelocs++; 155#endif 156 157 /* Find the alternate bucket for the evicted item. */ |
158 ckh->hash(key, hashes); 159 tbucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); |
160 if (tbucket == bucket) { |
161 tbucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) 162 - 1); |
163 /* 164 * It may be that (tbucket == bucket) still, if the 165 * item's hashes both indicate this bucket. However, 166 * we are guaranteed to eventually escape this bucket 167 * during iteration, assuming pseudo-random item 168 * selection (true randomness would make infinite 169 * looping a remote possibility). The reason we can 170 * never get trapped forever is that there are two --- 17 unchanged lines hidden (view full) --- 188 if (ckh_try_bucket_insert(ckh, bucket, key, data) == false) 189 return (false); 190 } 191} 192 193JEMALLOC_INLINE bool 194ckh_try_insert(ckh_t *ckh, void const**argkey, void const**argdata) 195{ |
196 size_t hashes[2], bucket; |
197 const void *key = *argkey; 198 const void *data = *argdata; 199 |
200 ckh->hash(key, hashes); |
201 202 /* Try to insert in primary bucket. */ |
203 bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1); |
204 if (ckh_try_bucket_insert(ckh, bucket, key, data) == false) 205 return (false); 206 207 /* Try to insert in secondary bucket. */ |
208 bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); |
209 if (ckh_try_bucket_insert(ckh, bucket, key, data) == false) 210 return (false); 211 212 /* 213 * Try to find a place for this item via iterative eviction/relocation. 214 */ 215 return (ckh_evict_reloc_insert(ckh, bucket, argkey, argdata)); 216} --- 196 unchanged lines hidden (view full) --- 413 (unsigned long long)ckh->ngrows, 414 (unsigned long long)ckh->nshrinks, 415 (unsigned long long)ckh->nshrinkfails, 416 (unsigned long long)ckh->ninserts, 417 (unsigned long long)ckh->nrelocs); 418#endif 419 420 idalloc(ckh->tab); |
421 if (config_debug) 422 memset(ckh, 0x5a, sizeof(ckh_t)); |
423} 424 425size_t 426ckh_count(ckh_t *ckh) 427{ 428 429 assert(ckh != NULL); 430 --- 90 unchanged lines hidden (view full) --- 521 *data = (void *)ckh->tab[cell].data; 522 return (false); 523 } 524 525 return (true); 526} 527 528void |
529ckh_string_hash(const void *key, size_t r_hash[2]) |
530{ |
531 |
532 hash(key, strlen((const char *)key), 0x94122f33U, r_hash); |
533} 534 535bool 536ckh_string_keycomp(const void *k1, const void *k2) 537{ 538 539 assert(k1 != NULL); 540 assert(k2 != NULL); 541 542 return (strcmp((char *)k1, (char *)k2) ? false : true); 543} 544 545void |
546ckh_pointer_hash(const void *key, size_t r_hash[2]) |
547{ |
548 union { 549 const void *v; |
550 size_t i; |
551 } u; 552 |
553 assert(sizeof(u.v) == sizeof(u.i)); |
554 u.v = key; |
555 hash(&u.i, sizeof(u.i), 0xd983396eU, r_hash); |
556} 557 558bool 559ckh_pointer_keycomp(const void *k1, const void *k2) 560{ 561 562 return ((k1 == k2) ? true : false); 563} |