1234370Sjasone/* 2234370Sjasone ******************************************************************************* 3234370Sjasone * Implementation of (2^1+,2) cuckoo hashing, where 2^1+ indicates that each 4234370Sjasone * hash bucket contains 2^n cells, for n >= 1, and 2 indicates that two hash 5234370Sjasone * functions are employed. The original cuckoo hashing algorithm was described 6234370Sjasone * in: 7234370Sjasone * 8234370Sjasone * Pagh, R., F.F. Rodler (2004) Cuckoo Hashing. Journal of Algorithms 9234370Sjasone * 51(2):122-144. 10234370Sjasone * 11234370Sjasone * Generalization of cuckoo hashing was discussed in: 12234370Sjasone * 13234370Sjasone * Erlingsson, U., M. Manasse, F. McSherry (2006) A cool and practical 14234370Sjasone * alternative to traditional hash tables. In Proceedings of the 7th 15234370Sjasone * Workshop on Distributed Data and Structures (WDAS'06), Santa Clara, CA, 16234370Sjasone * January 2006. 17234370Sjasone * 18234370Sjasone * This implementation uses precisely two hash functions because that is the 19234370Sjasone * fewest that can work, and supporting multiple hashes is an implementation 20234370Sjasone * burden. Here is a reproduction of Figure 1 from Erlingsson et al. (2006) 21234370Sjasone * that shows approximate expected maximum load factors for various 22234370Sjasone * configurations: 23234370Sjasone * 24234370Sjasone * | #cells/bucket | 25234370Sjasone * #hashes | 1 | 2 | 4 | 8 | 26234370Sjasone * --------+-------+-------+-------+-------+ 27234370Sjasone * 1 | 0.006 | 0.006 | 0.03 | 0.12 | 28234370Sjasone * 2 | 0.49 | 0.86 |>0.93< |>0.96< | 29234370Sjasone * 3 | 0.91 | 0.97 | 0.98 | 0.999 | 30234370Sjasone * 4 | 0.97 | 0.99 | 0.999 | | 31234370Sjasone * 32234370Sjasone * The number of cells per bucket is chosen such that a bucket fits in one cache 33234370Sjasone * line. So, on 32- and 64-bit systems, we use (8,2) and (4,2) cuckoo hashing, 34234370Sjasone * respectively. 35234370Sjasone * 36234370Sjasone ******************************************************************************/ 37234370Sjasone#define JEMALLOC_CKH_C_ 38234370Sjasone#include "jemalloc/internal/jemalloc_internal.h" 39234370Sjasone 40234370Sjasone/******************************************************************************/ 41234370Sjasone/* Function prototypes for non-inline static functions. */ 42234370Sjasone 43234370Sjasonestatic bool ckh_grow(ckh_t *ckh); 44234370Sjasonestatic void ckh_shrink(ckh_t *ckh); 45234370Sjasone 46234370Sjasone/******************************************************************************/ 47234370Sjasone 48234370Sjasone/* 49234370Sjasone * Search bucket for key and return the cell number if found; SIZE_T_MAX 50234370Sjasone * otherwise. 51234370Sjasone */ 52234370SjasoneJEMALLOC_INLINE size_t 53234370Sjasoneckh_bucket_search(ckh_t *ckh, size_t bucket, const void *key) 54234370Sjasone{ 55234370Sjasone ckhc_t *cell; 56234370Sjasone unsigned i; 57234370Sjasone 58234370Sjasone for (i = 0; i < (ZU(1) << LG_CKH_BUCKET_CELLS); i++) { 59234370Sjasone cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; 60234370Sjasone if (cell->key != NULL && ckh->keycomp(key, cell->key)) 61234370Sjasone return ((bucket << LG_CKH_BUCKET_CELLS) + i); 62234370Sjasone } 63234370Sjasone 64234370Sjasone return (SIZE_T_MAX); 65234370Sjasone} 66234370Sjasone 67234370Sjasone/* 68234370Sjasone * Search table for key and return cell number if found; SIZE_T_MAX otherwise. 69234370Sjasone */ 70234370SjasoneJEMALLOC_INLINE size_t 71234370Sjasoneckh_isearch(ckh_t *ckh, const void *key) 72234370Sjasone{ 73245868Sjasone size_t hashes[2], bucket, cell; 74234370Sjasone 75234370Sjasone assert(ckh != NULL); 76234370Sjasone 77245868Sjasone ckh->hash(key, hashes); 78234370Sjasone 79234370Sjasone /* Search primary bucket. */ 80245868Sjasone bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1); 81234370Sjasone cell = ckh_bucket_search(ckh, bucket, key); 82234370Sjasone if (cell != SIZE_T_MAX) 83234370Sjasone return (cell); 84234370Sjasone 85234370Sjasone /* Search secondary bucket. */ 86245868Sjasone bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); 87234370Sjasone cell = ckh_bucket_search(ckh, bucket, key); 88234370Sjasone return (cell); 89234370Sjasone} 90234370Sjasone 91234370SjasoneJEMALLOC_INLINE bool 92234370Sjasoneckh_try_bucket_insert(ckh_t *ckh, size_t bucket, const void *key, 93234370Sjasone const void *data) 94234370Sjasone{ 95234370Sjasone ckhc_t *cell; 96234370Sjasone unsigned offset, i; 97234370Sjasone 98234370Sjasone /* 99234370Sjasone * Cycle through the cells in the bucket, starting at a random position. 100234370Sjasone * The randomness avoids worst-case search overhead as buckets fill up. 101234370Sjasone */ 102234370Sjasone prng32(offset, LG_CKH_BUCKET_CELLS, ckh->prng_state, CKH_A, CKH_C); 103234370Sjasone for (i = 0; i < (ZU(1) << LG_CKH_BUCKET_CELLS); i++) { 104234370Sjasone cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + 105234370Sjasone ((i + offset) & ((ZU(1) << LG_CKH_BUCKET_CELLS) - 1))]; 106234370Sjasone if (cell->key == NULL) { 107234370Sjasone cell->key = key; 108234370Sjasone cell->data = data; 109234370Sjasone ckh->count++; 110234370Sjasone return (false); 111234370Sjasone } 112234370Sjasone } 113234370Sjasone 114234370Sjasone return (true); 115234370Sjasone} 116234370Sjasone 117234370Sjasone/* 118234370Sjasone * No space is available in bucket. Randomly evict an item, then try to find an 119234370Sjasone * alternate location for that item. Iteratively repeat this 120234370Sjasone * eviction/relocation procedure until either success or detection of an 121234370Sjasone * eviction/relocation bucket cycle. 122234370Sjasone */ 123234370SjasoneJEMALLOC_INLINE bool 124234370Sjasoneckh_evict_reloc_insert(ckh_t *ckh, size_t argbucket, void const **argkey, 125234370Sjasone void const **argdata) 126234370Sjasone{ 127234370Sjasone const void *key, *data, *tkey, *tdata; 128234370Sjasone ckhc_t *cell; 129245868Sjasone size_t hashes[2], bucket, tbucket; 130234370Sjasone unsigned i; 131234370Sjasone 132234370Sjasone bucket = argbucket; 133234370Sjasone key = *argkey; 134234370Sjasone data = *argdata; 135234370Sjasone while (true) { 136234370Sjasone /* 137234370Sjasone * Choose a random item within the bucket to evict. This is 138234370Sjasone * critical to correct function, because without (eventually) 139234370Sjasone * evicting all items within a bucket during iteration, it 140234370Sjasone * would be possible to get stuck in an infinite loop if there 141234370Sjasone * were an item for which both hashes indicated the same 142234370Sjasone * bucket. 143234370Sjasone */ 144234370Sjasone prng32(i, LG_CKH_BUCKET_CELLS, ckh->prng_state, CKH_A, CKH_C); 145234370Sjasone cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; 146234370Sjasone assert(cell->key != NULL); 147234370Sjasone 148234370Sjasone /* Swap cell->{key,data} and {key,data} (evict). */ 149234370Sjasone tkey = cell->key; tdata = cell->data; 150234370Sjasone cell->key = key; cell->data = data; 151234370Sjasone key = tkey; data = tdata; 152234370Sjasone 153234370Sjasone#ifdef CKH_COUNT 154234370Sjasone ckh->nrelocs++; 155234370Sjasone#endif 156234370Sjasone 157234370Sjasone /* Find the alternate bucket for the evicted item. */ 158245868Sjasone ckh->hash(key, hashes); 159245868Sjasone tbucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); 160234370Sjasone if (tbucket == bucket) { 161245868Sjasone tbucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) 162245868Sjasone - 1); 163234370Sjasone /* 164234370Sjasone * It may be that (tbucket == bucket) still, if the 165234370Sjasone * item's hashes both indicate this bucket. However, 166234370Sjasone * we are guaranteed to eventually escape this bucket 167234370Sjasone * during iteration, assuming pseudo-random item 168234370Sjasone * selection (true randomness would make infinite 169234370Sjasone * looping a remote possibility). The reason we can 170234370Sjasone * never get trapped forever is that there are two 171234370Sjasone * cases: 172234370Sjasone * 173234370Sjasone * 1) This bucket == argbucket, so we will quickly 174234370Sjasone * detect an eviction cycle and terminate. 175234370Sjasone * 2) An item was evicted to this bucket from another, 176234370Sjasone * which means that at least one item in this bucket 177234370Sjasone * has hashes that indicate distinct buckets. 178234370Sjasone */ 179234370Sjasone } 180234370Sjasone /* Check for a cycle. */ 181234370Sjasone if (tbucket == argbucket) { 182234370Sjasone *argkey = key; 183234370Sjasone *argdata = data; 184234370Sjasone return (true); 185234370Sjasone } 186234370Sjasone 187234370Sjasone bucket = tbucket; 188234370Sjasone if (ckh_try_bucket_insert(ckh, bucket, key, data) == false) 189234370Sjasone return (false); 190234370Sjasone } 191234370Sjasone} 192234370Sjasone 193234370SjasoneJEMALLOC_INLINE bool 194234370Sjasoneckh_try_insert(ckh_t *ckh, void const**argkey, void const**argdata) 195234370Sjasone{ 196245868Sjasone size_t hashes[2], bucket; 197234370Sjasone const void *key = *argkey; 198234370Sjasone const void *data = *argdata; 199234370Sjasone 200245868Sjasone ckh->hash(key, hashes); 201234370Sjasone 202234370Sjasone /* Try to insert in primary bucket. */ 203245868Sjasone bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1); 204234370Sjasone if (ckh_try_bucket_insert(ckh, bucket, key, data) == false) 205234370Sjasone return (false); 206234370Sjasone 207234370Sjasone /* Try to insert in secondary bucket. */ 208245868Sjasone bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); 209234370Sjasone if (ckh_try_bucket_insert(ckh, bucket, key, data) == false) 210234370Sjasone return (false); 211234370Sjasone 212234370Sjasone /* 213234370Sjasone * Try to find a place for this item via iterative eviction/relocation. 214234370Sjasone */ 215234370Sjasone return (ckh_evict_reloc_insert(ckh, bucket, argkey, argdata)); 216234370Sjasone} 217234370Sjasone 218234370Sjasone/* 219234370Sjasone * Try to rebuild the hash table from scratch by inserting all items from the 220234370Sjasone * old table into the new. 221234370Sjasone */ 222234370SjasoneJEMALLOC_INLINE bool 223234370Sjasoneckh_rebuild(ckh_t *ckh, ckhc_t *aTab) 224234370Sjasone{ 225234370Sjasone size_t count, i, nins; 226234370Sjasone const void *key, *data; 227234370Sjasone 228234370Sjasone count = ckh->count; 229234370Sjasone ckh->count = 0; 230234370Sjasone for (i = nins = 0; nins < count; i++) { 231234370Sjasone if (aTab[i].key != NULL) { 232234370Sjasone key = aTab[i].key; 233234370Sjasone data = aTab[i].data; 234234370Sjasone if (ckh_try_insert(ckh, &key, &data)) { 235234370Sjasone ckh->count = count; 236234370Sjasone return (true); 237234370Sjasone } 238234370Sjasone nins++; 239234370Sjasone } 240234370Sjasone } 241234370Sjasone 242234370Sjasone return (false); 243234370Sjasone} 244234370Sjasone 245234370Sjasonestatic bool 246234370Sjasoneckh_grow(ckh_t *ckh) 247234370Sjasone{ 248234370Sjasone bool ret; 249234370Sjasone ckhc_t *tab, *ttab; 250234370Sjasone size_t lg_curcells; 251234370Sjasone unsigned lg_prevbuckets; 252234370Sjasone 253234370Sjasone#ifdef CKH_COUNT 254234370Sjasone ckh->ngrows++; 255234370Sjasone#endif 256234370Sjasone 257234370Sjasone /* 258234370Sjasone * It is possible (though unlikely, given well behaved hashes) that the 259234370Sjasone * table will have to be doubled more than once in order to create a 260234370Sjasone * usable table. 261234370Sjasone */ 262234370Sjasone lg_prevbuckets = ckh->lg_curbuckets; 263234370Sjasone lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS; 264234370Sjasone while (true) { 265234370Sjasone size_t usize; 266234370Sjasone 267234370Sjasone lg_curcells++; 268234370Sjasone usize = sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE); 269234370Sjasone if (usize == 0) { 270234370Sjasone ret = true; 271234370Sjasone goto label_return; 272234370Sjasone } 273234370Sjasone tab = (ckhc_t *)ipalloc(usize, CACHELINE, true); 274234370Sjasone if (tab == NULL) { 275234370Sjasone ret = true; 276234370Sjasone goto label_return; 277234370Sjasone } 278234370Sjasone /* Swap in new table. */ 279234370Sjasone ttab = ckh->tab; 280234370Sjasone ckh->tab = tab; 281234370Sjasone tab = ttab; 282234370Sjasone ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; 283234370Sjasone 284234370Sjasone if (ckh_rebuild(ckh, tab) == false) { 285234370Sjasone idalloc(tab); 286234370Sjasone break; 287234370Sjasone } 288234370Sjasone 289234370Sjasone /* Rebuilding failed, so back out partially rebuilt table. */ 290234370Sjasone idalloc(ckh->tab); 291234370Sjasone ckh->tab = tab; 292234370Sjasone ckh->lg_curbuckets = lg_prevbuckets; 293234370Sjasone } 294234370Sjasone 295234370Sjasone ret = false; 296234370Sjasonelabel_return: 297234370Sjasone return (ret); 298234370Sjasone} 299234370Sjasone 300234370Sjasonestatic void 301234370Sjasoneckh_shrink(ckh_t *ckh) 302234370Sjasone{ 303234370Sjasone ckhc_t *tab, *ttab; 304234370Sjasone size_t lg_curcells, usize; 305234370Sjasone unsigned lg_prevbuckets; 306234370Sjasone 307234370Sjasone /* 308234370Sjasone * It is possible (though unlikely, given well behaved hashes) that the 309234370Sjasone * table rebuild will fail. 310234370Sjasone */ 311234370Sjasone lg_prevbuckets = ckh->lg_curbuckets; 312234370Sjasone lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS - 1; 313234370Sjasone usize = sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE); 314234370Sjasone if (usize == 0) 315234370Sjasone return; 316234370Sjasone tab = (ckhc_t *)ipalloc(usize, CACHELINE, true); 317234370Sjasone if (tab == NULL) { 318234370Sjasone /* 319234370Sjasone * An OOM error isn't worth propagating, since it doesn't 320234370Sjasone * prevent this or future operations from proceeding. 321234370Sjasone */ 322234370Sjasone return; 323234370Sjasone } 324234370Sjasone /* Swap in new table. */ 325234370Sjasone ttab = ckh->tab; 326234370Sjasone ckh->tab = tab; 327234370Sjasone tab = ttab; 328234370Sjasone ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; 329234370Sjasone 330234370Sjasone if (ckh_rebuild(ckh, tab) == false) { 331234370Sjasone idalloc(tab); 332234370Sjasone#ifdef CKH_COUNT 333234370Sjasone ckh->nshrinks++; 334234370Sjasone#endif 335234370Sjasone return; 336234370Sjasone } 337234370Sjasone 338234370Sjasone /* Rebuilding failed, so back out partially rebuilt table. */ 339234370Sjasone idalloc(ckh->tab); 340234370Sjasone ckh->tab = tab; 341234370Sjasone ckh->lg_curbuckets = lg_prevbuckets; 342234370Sjasone#ifdef CKH_COUNT 343234370Sjasone ckh->nshrinkfails++; 344234370Sjasone#endif 345234370Sjasone} 346234370Sjasone 347234370Sjasonebool 348234370Sjasoneckh_new(ckh_t *ckh, size_t minitems, ckh_hash_t *hash, ckh_keycomp_t *keycomp) 349234370Sjasone{ 350234370Sjasone bool ret; 351234370Sjasone size_t mincells, usize; 352234370Sjasone unsigned lg_mincells; 353234370Sjasone 354234370Sjasone assert(minitems > 0); 355234370Sjasone assert(hash != NULL); 356234370Sjasone assert(keycomp != NULL); 357234370Sjasone 358234370Sjasone#ifdef CKH_COUNT 359234370Sjasone ckh->ngrows = 0; 360234370Sjasone ckh->nshrinks = 0; 361234370Sjasone ckh->nshrinkfails = 0; 362234370Sjasone ckh->ninserts = 0; 363234370Sjasone ckh->nrelocs = 0; 364234370Sjasone#endif 365234370Sjasone ckh->prng_state = 42; /* Value doesn't really matter. */ 366234370Sjasone ckh->count = 0; 367234370Sjasone 368234370Sjasone /* 369234370Sjasone * Find the minimum power of 2 that is large enough to fit aBaseCount 370234370Sjasone * entries. We are using (2+,2) cuckoo hashing, which has an expected 371234370Sjasone * maximum load factor of at least ~0.86, so 0.75 is a conservative load 372234370Sjasone * factor that will typically allow 2^aLgMinItems to fit without ever 373234370Sjasone * growing the table. 374234370Sjasone */ 375234370Sjasone assert(LG_CKH_BUCKET_CELLS > 0); 376234370Sjasone mincells = ((minitems + (3 - (minitems % 3))) / 3) << 2; 377234370Sjasone for (lg_mincells = LG_CKH_BUCKET_CELLS; 378234370Sjasone (ZU(1) << lg_mincells) < mincells; 379234370Sjasone lg_mincells++) 380234370Sjasone ; /* Do nothing. */ 381234370Sjasone ckh->lg_minbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; 382234370Sjasone ckh->lg_curbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; 383234370Sjasone ckh->hash = hash; 384234370Sjasone ckh->keycomp = keycomp; 385234370Sjasone 386234370Sjasone usize = sa2u(sizeof(ckhc_t) << lg_mincells, CACHELINE); 387234370Sjasone if (usize == 0) { 388234370Sjasone ret = true; 389234370Sjasone goto label_return; 390234370Sjasone } 391234370Sjasone ckh->tab = (ckhc_t *)ipalloc(usize, CACHELINE, true); 392234370Sjasone if (ckh->tab == NULL) { 393234370Sjasone ret = true; 394234370Sjasone goto label_return; 395234370Sjasone } 396234370Sjasone 397234370Sjasone ret = false; 398234370Sjasonelabel_return: 399234370Sjasone return (ret); 400234370Sjasone} 401234370Sjasone 402234370Sjasonevoid 403234370Sjasoneckh_delete(ckh_t *ckh) 404234370Sjasone{ 405234370Sjasone 406234370Sjasone assert(ckh != NULL); 407234370Sjasone 408234370Sjasone#ifdef CKH_VERBOSE 409234370Sjasone malloc_printf( 410234370Sjasone "%s(%p): ngrows: %"PRIu64", nshrinks: %"PRIu64"," 411234370Sjasone " nshrinkfails: %"PRIu64", ninserts: %"PRIu64"," 412234370Sjasone " nrelocs: %"PRIu64"\n", __func__, ckh, 413234370Sjasone (unsigned long long)ckh->ngrows, 414234370Sjasone (unsigned long long)ckh->nshrinks, 415234370Sjasone (unsigned long long)ckh->nshrinkfails, 416234370Sjasone (unsigned long long)ckh->ninserts, 417234370Sjasone (unsigned long long)ckh->nrelocs); 418234370Sjasone#endif 419234370Sjasone 420234370Sjasone idalloc(ckh->tab); 421245868Sjasone if (config_debug) 422245868Sjasone memset(ckh, 0x5a, sizeof(ckh_t)); 423234370Sjasone} 424234370Sjasone 425234370Sjasonesize_t 426234370Sjasoneckh_count(ckh_t *ckh) 427234370Sjasone{ 428234370Sjasone 429234370Sjasone assert(ckh != NULL); 430234370Sjasone 431234370Sjasone return (ckh->count); 432234370Sjasone} 433234370Sjasone 434234370Sjasonebool 435234370Sjasoneckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data) 436234370Sjasone{ 437234370Sjasone size_t i, ncells; 438234370Sjasone 439234370Sjasone for (i = *tabind, ncells = (ZU(1) << (ckh->lg_curbuckets + 440234370Sjasone LG_CKH_BUCKET_CELLS)); i < ncells; i++) { 441234370Sjasone if (ckh->tab[i].key != NULL) { 442234370Sjasone if (key != NULL) 443234370Sjasone *key = (void *)ckh->tab[i].key; 444234370Sjasone if (data != NULL) 445234370Sjasone *data = (void *)ckh->tab[i].data; 446234370Sjasone *tabind = i + 1; 447234370Sjasone return (false); 448234370Sjasone } 449234370Sjasone } 450234370Sjasone 451234370Sjasone return (true); 452234370Sjasone} 453234370Sjasone 454234370Sjasonebool 455234370Sjasoneckh_insert(ckh_t *ckh, const void *key, const void *data) 456234370Sjasone{ 457234370Sjasone bool ret; 458234370Sjasone 459234370Sjasone assert(ckh != NULL); 460234370Sjasone assert(ckh_search(ckh, key, NULL, NULL)); 461234370Sjasone 462234370Sjasone#ifdef CKH_COUNT 463234370Sjasone ckh->ninserts++; 464234370Sjasone#endif 465234370Sjasone 466234370Sjasone while (ckh_try_insert(ckh, &key, &data)) { 467234370Sjasone if (ckh_grow(ckh)) { 468234370Sjasone ret = true; 469234370Sjasone goto label_return; 470234370Sjasone } 471234370Sjasone } 472234370Sjasone 473234370Sjasone ret = false; 474234370Sjasonelabel_return: 475234370Sjasone return (ret); 476234370Sjasone} 477234370Sjasone 478234370Sjasonebool 479234370Sjasoneckh_remove(ckh_t *ckh, const void *searchkey, void **key, void **data) 480234370Sjasone{ 481234370Sjasone size_t cell; 482234370Sjasone 483234370Sjasone assert(ckh != NULL); 484234370Sjasone 485234370Sjasone cell = ckh_isearch(ckh, searchkey); 486234370Sjasone if (cell != SIZE_T_MAX) { 487234370Sjasone if (key != NULL) 488234370Sjasone *key = (void *)ckh->tab[cell].key; 489234370Sjasone if (data != NULL) 490234370Sjasone *data = (void *)ckh->tab[cell].data; 491234370Sjasone ckh->tab[cell].key = NULL; 492234370Sjasone ckh->tab[cell].data = NULL; /* Not necessary. */ 493234370Sjasone 494234370Sjasone ckh->count--; 495234370Sjasone /* Try to halve the table if it is less than 1/4 full. */ 496234370Sjasone if (ckh->count < (ZU(1) << (ckh->lg_curbuckets 497234370Sjasone + LG_CKH_BUCKET_CELLS - 2)) && ckh->lg_curbuckets 498234370Sjasone > ckh->lg_minbuckets) { 499234370Sjasone /* Ignore error due to OOM. */ 500234370Sjasone ckh_shrink(ckh); 501234370Sjasone } 502234370Sjasone 503234370Sjasone return (false); 504234370Sjasone } 505234370Sjasone 506234370Sjasone return (true); 507234370Sjasone} 508234370Sjasone 509234370Sjasonebool 510234370Sjasoneckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data) 511234370Sjasone{ 512234370Sjasone size_t cell; 513234370Sjasone 514234370Sjasone assert(ckh != NULL); 515234370Sjasone 516234370Sjasone cell = ckh_isearch(ckh, searchkey); 517234370Sjasone if (cell != SIZE_T_MAX) { 518234370Sjasone if (key != NULL) 519234370Sjasone *key = (void *)ckh->tab[cell].key; 520234370Sjasone if (data != NULL) 521234370Sjasone *data = (void *)ckh->tab[cell].data; 522234370Sjasone return (false); 523234370Sjasone } 524234370Sjasone 525234370Sjasone return (true); 526234370Sjasone} 527234370Sjasone 528234370Sjasonevoid 529245868Sjasoneckh_string_hash(const void *key, size_t r_hash[2]) 530234370Sjasone{ 531234370Sjasone 532245868Sjasone hash(key, strlen((const char *)key), 0x94122f33U, r_hash); 533234370Sjasone} 534234370Sjasone 535234370Sjasonebool 536234370Sjasoneckh_string_keycomp(const void *k1, const void *k2) 537234370Sjasone{ 538234370Sjasone 539234370Sjasone assert(k1 != NULL); 540234370Sjasone assert(k2 != NULL); 541234370Sjasone 542234370Sjasone return (strcmp((char *)k1, (char *)k2) ? false : true); 543234370Sjasone} 544234370Sjasone 545234370Sjasonevoid 546245868Sjasoneckh_pointer_hash(const void *key, size_t r_hash[2]) 547234370Sjasone{ 548234370Sjasone union { 549234370Sjasone const void *v; 550245868Sjasone size_t i; 551234370Sjasone } u; 552234370Sjasone 553234370Sjasone assert(sizeof(u.v) == sizeof(u.i)); 554234370Sjasone u.v = key; 555245868Sjasone hash(&u.i, sizeof(u.i), 0xd983396eU, r_hash); 556234370Sjasone} 557234370Sjasone 558234370Sjasonebool 559234370Sjasoneckh_pointer_keycomp(const void *k1, const void *k2) 560234370Sjasone{ 561234370Sjasone 562234370Sjasone return ((k1 == k2) ? true : false); 563234370Sjasone} 564