1a4bd5210SJason Evans /* 2a4bd5210SJason Evans ******************************************************************************* 3a4bd5210SJason Evans * Implementation of (2^1+,2) cuckoo hashing, where 2^1+ indicates that each 4a4bd5210SJason Evans * hash bucket contains 2^n cells, for n >= 1, and 2 indicates that two hash 5a4bd5210SJason Evans * functions are employed. The original cuckoo hashing algorithm was described 6a4bd5210SJason Evans * in: 7a4bd5210SJason Evans * 8a4bd5210SJason Evans * Pagh, R., F.F. Rodler (2004) Cuckoo Hashing. Journal of Algorithms 9a4bd5210SJason Evans * 51(2):122-144. 10a4bd5210SJason Evans * 11a4bd5210SJason Evans * Generalization of cuckoo hashing was discussed in: 12a4bd5210SJason Evans * 13a4bd5210SJason Evans * Erlingsson, U., M. Manasse, F. McSherry (2006) A cool and practical 14a4bd5210SJason Evans * alternative to traditional hash tables. In Proceedings of the 7th 15a4bd5210SJason Evans * Workshop on Distributed Data and Structures (WDAS'06), Santa Clara, CA, 16a4bd5210SJason Evans * January 2006. 17a4bd5210SJason Evans * 18a4bd5210SJason Evans * This implementation uses precisely two hash functions because that is the 19a4bd5210SJason Evans * fewest that can work, and supporting multiple hashes is an implementation 20a4bd5210SJason Evans * burden. Here is a reproduction of Figure 1 from Erlingsson et al. (2006) 21a4bd5210SJason Evans * that shows approximate expected maximum load factors for various 22a4bd5210SJason Evans * configurations: 23a4bd5210SJason Evans * 24a4bd5210SJason Evans * | #cells/bucket | 25a4bd5210SJason Evans * #hashes | 1 | 2 | 4 | 8 | 26a4bd5210SJason Evans * --------+-------+-------+-------+-------+ 27a4bd5210SJason Evans * 1 | 0.006 | 0.006 | 0.03 | 0.12 | 28a4bd5210SJason Evans * 2 | 0.49 | 0.86 |>0.93< |>0.96< | 29a4bd5210SJason Evans * 3 | 0.91 | 0.97 | 0.98 | 0.999 | 30a4bd5210SJason Evans * 4 | 0.97 | 0.99 | 0.999 | | 31a4bd5210SJason Evans * 32a4bd5210SJason Evans * The number of cells per bucket is chosen such that a bucket fits in one cache 33a4bd5210SJason Evans * line. So, on 32- and 64-bit systems, we use (8,2) and (4,2) cuckoo hashing, 34a4bd5210SJason Evans * respectively. 35a4bd5210SJason Evans * 36a4bd5210SJason Evans ******************************************************************************/ 37a4bd5210SJason Evans #define JEMALLOC_CKH_C_ 38b7eaed25SJason Evans #include "jemalloc/internal/jemalloc_preamble.h" 39b7eaed25SJason Evans 40b7eaed25SJason Evans #include "jemalloc/internal/ckh.h" 41b7eaed25SJason Evans 42b7eaed25SJason Evans #include "jemalloc/internal/jemalloc_internal_includes.h" 43b7eaed25SJason Evans 44b7eaed25SJason Evans #include "jemalloc/internal/assert.h" 45b7eaed25SJason Evans #include "jemalloc/internal/hash.h" 46b7eaed25SJason Evans #include "jemalloc/internal/malloc_io.h" 47b7eaed25SJason Evans #include "jemalloc/internal/prng.h" 48b7eaed25SJason Evans #include "jemalloc/internal/util.h" 49a4bd5210SJason Evans 50a4bd5210SJason Evans /******************************************************************************/ 51a4bd5210SJason Evans /* Function prototypes for non-inline static functions. */ 52a4bd5210SJason Evans 53bde95144SJason Evans static bool ckh_grow(tsd_t *tsd, ckh_t *ckh); 54bde95144SJason Evans static void ckh_shrink(tsd_t *tsd, ckh_t *ckh); 55a4bd5210SJason Evans 56a4bd5210SJason Evans /******************************************************************************/ 57a4bd5210SJason Evans 58a4bd5210SJason Evans /* 59a4bd5210SJason Evans * Search bucket for key and return the cell number if found; SIZE_T_MAX 60a4bd5210SJason Evans * otherwise. 61a4bd5210SJason Evans */ 62b7eaed25SJason Evans static size_t 63b7eaed25SJason Evans ckh_bucket_search(ckh_t *ckh, size_t bucket, const void *key) { 64a4bd5210SJason Evans ckhc_t *cell; 65a4bd5210SJason Evans unsigned i; 66a4bd5210SJason Evans 67a4bd5210SJason Evans for (i = 0; i < (ZU(1) << LG_CKH_BUCKET_CELLS); i++) { 68a4bd5210SJason Evans cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; 69b7eaed25SJason Evans if (cell->key != NULL && ckh->keycomp(key, cell->key)) { 70b7eaed25SJason Evans return (bucket << LG_CKH_BUCKET_CELLS) + i; 71b7eaed25SJason Evans } 72a4bd5210SJason Evans } 73a4bd5210SJason Evans 74b7eaed25SJason Evans return SIZE_T_MAX; 75a4bd5210SJason Evans } 76a4bd5210SJason Evans 77a4bd5210SJason Evans /* 78a4bd5210SJason Evans * Search table for key and return cell number if found; SIZE_T_MAX otherwise. 79a4bd5210SJason Evans */ 80b7eaed25SJason Evans static size_t 81b7eaed25SJason Evans ckh_isearch(ckh_t *ckh, const void *key) { 8288ad2f8dSJason Evans size_t hashes[2], bucket, cell; 83a4bd5210SJason Evans 84a4bd5210SJason Evans assert(ckh != NULL); 85a4bd5210SJason Evans 8688ad2f8dSJason Evans ckh->hash(key, hashes); 87a4bd5210SJason Evans 88a4bd5210SJason Evans /* Search primary bucket. */ 8988ad2f8dSJason Evans bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1); 90a4bd5210SJason Evans cell = ckh_bucket_search(ckh, bucket, key); 91b7eaed25SJason Evans if (cell != SIZE_T_MAX) { 92b7eaed25SJason Evans return cell; 93b7eaed25SJason Evans } 94a4bd5210SJason Evans 95a4bd5210SJason Evans /* Search secondary bucket. */ 9688ad2f8dSJason Evans bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); 97a4bd5210SJason Evans cell = ckh_bucket_search(ckh, bucket, key); 98b7eaed25SJason Evans return cell; 99a4bd5210SJason Evans } 100a4bd5210SJason Evans 101b7eaed25SJason Evans static bool 102a4bd5210SJason Evans ckh_try_bucket_insert(ckh_t *ckh, size_t bucket, const void *key, 103b7eaed25SJason Evans const void *data) { 104a4bd5210SJason Evans ckhc_t *cell; 105a4bd5210SJason Evans unsigned offset, i; 106a4bd5210SJason Evans 107a4bd5210SJason Evans /* 108a4bd5210SJason Evans * Cycle through the cells in the bucket, starting at a random position. 109a4bd5210SJason Evans * The randomness avoids worst-case search overhead as buckets fill up. 110a4bd5210SJason Evans */ 111bde95144SJason Evans offset = (unsigned)prng_lg_range_u64(&ckh->prng_state, 112bde95144SJason Evans LG_CKH_BUCKET_CELLS); 113a4bd5210SJason Evans for (i = 0; i < (ZU(1) << LG_CKH_BUCKET_CELLS); i++) { 114a4bd5210SJason Evans cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + 115a4bd5210SJason Evans ((i + offset) & ((ZU(1) << LG_CKH_BUCKET_CELLS) - 1))]; 116a4bd5210SJason Evans if (cell->key == NULL) { 117a4bd5210SJason Evans cell->key = key; 118a4bd5210SJason Evans cell->data = data; 119a4bd5210SJason Evans ckh->count++; 120b7eaed25SJason Evans return false; 121a4bd5210SJason Evans } 122a4bd5210SJason Evans } 123a4bd5210SJason Evans 124b7eaed25SJason Evans return true; 125a4bd5210SJason Evans } 126a4bd5210SJason Evans 127a4bd5210SJason Evans /* 128a4bd5210SJason Evans * No space is available in bucket. Randomly evict an item, then try to find an 129a4bd5210SJason Evans * alternate location for that item. Iteratively repeat this 130a4bd5210SJason Evans * eviction/relocation procedure until either success or detection of an 131a4bd5210SJason Evans * eviction/relocation bucket cycle. 132a4bd5210SJason Evans */ 133b7eaed25SJason Evans static bool 134a4bd5210SJason Evans ckh_evict_reloc_insert(ckh_t *ckh, size_t argbucket, void const **argkey, 135b7eaed25SJason Evans void const **argdata) { 136a4bd5210SJason Evans const void *key, *data, *tkey, *tdata; 137a4bd5210SJason Evans ckhc_t *cell; 13888ad2f8dSJason Evans size_t hashes[2], bucket, tbucket; 139a4bd5210SJason Evans unsigned i; 140a4bd5210SJason Evans 141a4bd5210SJason Evans bucket = argbucket; 142a4bd5210SJason Evans key = *argkey; 143a4bd5210SJason Evans data = *argdata; 144a4bd5210SJason Evans while (true) { 145a4bd5210SJason Evans /* 146a4bd5210SJason Evans * Choose a random item within the bucket to evict. This is 147a4bd5210SJason Evans * critical to correct function, because without (eventually) 148a4bd5210SJason Evans * evicting all items within a bucket during iteration, it 149a4bd5210SJason Evans * would be possible to get stuck in an infinite loop if there 150a4bd5210SJason Evans * were an item for which both hashes indicated the same 151a4bd5210SJason Evans * bucket. 152a4bd5210SJason Evans */ 153bde95144SJason Evans i = (unsigned)prng_lg_range_u64(&ckh->prng_state, 154df0d881dSJason Evans LG_CKH_BUCKET_CELLS); 155a4bd5210SJason Evans cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; 156a4bd5210SJason Evans assert(cell->key != NULL); 157a4bd5210SJason Evans 158a4bd5210SJason Evans /* Swap cell->{key,data} and {key,data} (evict). */ 159a4bd5210SJason Evans tkey = cell->key; tdata = cell->data; 160a4bd5210SJason Evans cell->key = key; cell->data = data; 161a4bd5210SJason Evans key = tkey; data = tdata; 162a4bd5210SJason Evans 163a4bd5210SJason Evans #ifdef CKH_COUNT 164a4bd5210SJason Evans ckh->nrelocs++; 165a4bd5210SJason Evans #endif 166a4bd5210SJason Evans 167a4bd5210SJason Evans /* Find the alternate bucket for the evicted item. */ 16888ad2f8dSJason Evans ckh->hash(key, hashes); 16988ad2f8dSJason Evans tbucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); 170a4bd5210SJason Evans if (tbucket == bucket) { 17188ad2f8dSJason Evans tbucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) 17288ad2f8dSJason Evans - 1); 173a4bd5210SJason Evans /* 174a4bd5210SJason Evans * It may be that (tbucket == bucket) still, if the 175a4bd5210SJason Evans * item's hashes both indicate this bucket. However, 176a4bd5210SJason Evans * we are guaranteed to eventually escape this bucket 177a4bd5210SJason Evans * during iteration, assuming pseudo-random item 178a4bd5210SJason Evans * selection (true randomness would make infinite 179a4bd5210SJason Evans * looping a remote possibility). The reason we can 180a4bd5210SJason Evans * never get trapped forever is that there are two 181a4bd5210SJason Evans * cases: 182a4bd5210SJason Evans * 183a4bd5210SJason Evans * 1) This bucket == argbucket, so we will quickly 184a4bd5210SJason Evans * detect an eviction cycle and terminate. 185a4bd5210SJason Evans * 2) An item was evicted to this bucket from another, 186a4bd5210SJason Evans * which means that at least one item in this bucket 187a4bd5210SJason Evans * has hashes that indicate distinct buckets. 188a4bd5210SJason Evans */ 189a4bd5210SJason Evans } 190a4bd5210SJason Evans /* Check for a cycle. */ 191a4bd5210SJason Evans if (tbucket == argbucket) { 192a4bd5210SJason Evans *argkey = key; 193a4bd5210SJason Evans *argdata = data; 194b7eaed25SJason Evans return true; 195a4bd5210SJason Evans } 196a4bd5210SJason Evans 197a4bd5210SJason Evans bucket = tbucket; 198b7eaed25SJason Evans if (!ckh_try_bucket_insert(ckh, bucket, key, data)) { 199b7eaed25SJason Evans return false; 200b7eaed25SJason Evans } 201a4bd5210SJason Evans } 202a4bd5210SJason Evans } 203a4bd5210SJason Evans 204b7eaed25SJason Evans static bool 205b7eaed25SJason Evans ckh_try_insert(ckh_t *ckh, void const**argkey, void const**argdata) { 20688ad2f8dSJason Evans size_t hashes[2], bucket; 207a4bd5210SJason Evans const void *key = *argkey; 208a4bd5210SJason Evans const void *data = *argdata; 209a4bd5210SJason Evans 21088ad2f8dSJason Evans ckh->hash(key, hashes); 211a4bd5210SJason Evans 212a4bd5210SJason Evans /* Try to insert in primary bucket. */ 21388ad2f8dSJason Evans bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1); 214b7eaed25SJason Evans if (!ckh_try_bucket_insert(ckh, bucket, key, data)) { 215b7eaed25SJason Evans return false; 216b7eaed25SJason Evans } 217a4bd5210SJason Evans 218a4bd5210SJason Evans /* Try to insert in secondary bucket. */ 21988ad2f8dSJason Evans bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); 220b7eaed25SJason Evans if (!ckh_try_bucket_insert(ckh, bucket, key, data)) { 221b7eaed25SJason Evans return false; 222b7eaed25SJason Evans } 223a4bd5210SJason Evans 224a4bd5210SJason Evans /* 225a4bd5210SJason Evans * Try to find a place for this item via iterative eviction/relocation. 226a4bd5210SJason Evans */ 227b7eaed25SJason Evans return ckh_evict_reloc_insert(ckh, bucket, argkey, argdata); 228a4bd5210SJason Evans } 229a4bd5210SJason Evans 230a4bd5210SJason Evans /* 231a4bd5210SJason Evans * Try to rebuild the hash table from scratch by inserting all items from the 232a4bd5210SJason Evans * old table into the new. 233a4bd5210SJason Evans */ 234b7eaed25SJason Evans static bool 235b7eaed25SJason Evans ckh_rebuild(ckh_t *ckh, ckhc_t *aTab) { 236a4bd5210SJason Evans size_t count, i, nins; 237a4bd5210SJason Evans const void *key, *data; 238a4bd5210SJason Evans 239a4bd5210SJason Evans count = ckh->count; 240a4bd5210SJason Evans ckh->count = 0; 241a4bd5210SJason Evans for (i = nins = 0; nins < count; i++) { 242a4bd5210SJason Evans if (aTab[i].key != NULL) { 243a4bd5210SJason Evans key = aTab[i].key; 244a4bd5210SJason Evans data = aTab[i].data; 245a4bd5210SJason Evans if (ckh_try_insert(ckh, &key, &data)) { 246a4bd5210SJason Evans ckh->count = count; 247b7eaed25SJason Evans return true; 248a4bd5210SJason Evans } 249a4bd5210SJason Evans nins++; 250a4bd5210SJason Evans } 251a4bd5210SJason Evans } 252a4bd5210SJason Evans 253b7eaed25SJason Evans return false; 254a4bd5210SJason Evans } 255a4bd5210SJason Evans 256a4bd5210SJason Evans static bool 257b7eaed25SJason Evans ckh_grow(tsd_t *tsd, ckh_t *ckh) { 258a4bd5210SJason Evans bool ret; 259a4bd5210SJason Evans ckhc_t *tab, *ttab; 260df0d881dSJason Evans unsigned lg_prevbuckets, lg_curcells; 261a4bd5210SJason Evans 262a4bd5210SJason Evans #ifdef CKH_COUNT 263a4bd5210SJason Evans ckh->ngrows++; 264a4bd5210SJason Evans #endif 265a4bd5210SJason Evans 266a4bd5210SJason Evans /* 267a4bd5210SJason Evans * It is possible (though unlikely, given well behaved hashes) that the 268a4bd5210SJason Evans * table will have to be doubled more than once in order to create a 269a4bd5210SJason Evans * usable table. 270a4bd5210SJason Evans */ 271a4bd5210SJason Evans lg_prevbuckets = ckh->lg_curbuckets; 272a4bd5210SJason Evans lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS; 273a4bd5210SJason Evans while (true) { 274a4bd5210SJason Evans size_t usize; 275a4bd5210SJason Evans 276a4bd5210SJason Evans lg_curcells++; 277b7eaed25SJason Evans usize = sz_sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE); 278b7eaed25SJason Evans if (unlikely(usize == 0 || usize > LARGE_MAXCLASS)) { 279a4bd5210SJason Evans ret = true; 280a4bd5210SJason Evans goto label_return; 281a4bd5210SJason Evans } 282bde95144SJason Evans tab = (ckhc_t *)ipallocztm(tsd_tsdn(tsd), usize, CACHELINE, 283bde95144SJason Evans true, NULL, true, arena_ichoose(tsd, NULL)); 284a4bd5210SJason Evans if (tab == NULL) { 285a4bd5210SJason Evans ret = true; 286a4bd5210SJason Evans goto label_return; 287a4bd5210SJason Evans } 288a4bd5210SJason Evans /* Swap in new table. */ 289a4bd5210SJason Evans ttab = ckh->tab; 290a4bd5210SJason Evans ckh->tab = tab; 291a4bd5210SJason Evans tab = ttab; 292a4bd5210SJason Evans ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; 293a4bd5210SJason Evans 294d0e79aa3SJason Evans if (!ckh_rebuild(ckh, tab)) { 295b7eaed25SJason Evans idalloctm(tsd_tsdn(tsd), tab, NULL, NULL, true, true); 296a4bd5210SJason Evans break; 297a4bd5210SJason Evans } 298a4bd5210SJason Evans 299a4bd5210SJason Evans /* Rebuilding failed, so back out partially rebuilt table. */ 300b7eaed25SJason Evans idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, NULL, true, true); 301a4bd5210SJason Evans ckh->tab = tab; 302a4bd5210SJason Evans ckh->lg_curbuckets = lg_prevbuckets; 303a4bd5210SJason Evans } 304a4bd5210SJason Evans 305a4bd5210SJason Evans ret = false; 306a4bd5210SJason Evans label_return: 307b7eaed25SJason Evans return ret; 308a4bd5210SJason Evans } 309a4bd5210SJason Evans 310a4bd5210SJason Evans static void 311b7eaed25SJason Evans ckh_shrink(tsd_t *tsd, ckh_t *ckh) { 312a4bd5210SJason Evans ckhc_t *tab, *ttab; 313df0d881dSJason Evans size_t usize; 314df0d881dSJason Evans unsigned lg_prevbuckets, lg_curcells; 315a4bd5210SJason Evans 316a4bd5210SJason Evans /* 317a4bd5210SJason Evans * It is possible (though unlikely, given well behaved hashes) that the 318a4bd5210SJason Evans * table rebuild will fail. 319a4bd5210SJason Evans */ 320a4bd5210SJason Evans lg_prevbuckets = ckh->lg_curbuckets; 321a4bd5210SJason Evans lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS - 1; 322b7eaed25SJason Evans usize = sz_sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE); 323b7eaed25SJason Evans if (unlikely(usize == 0 || usize > LARGE_MAXCLASS)) { 324a4bd5210SJason Evans return; 325b7eaed25SJason Evans } 326bde95144SJason Evans tab = (ckhc_t *)ipallocztm(tsd_tsdn(tsd), usize, CACHELINE, true, NULL, 327bde95144SJason Evans true, arena_ichoose(tsd, NULL)); 328a4bd5210SJason Evans if (tab == NULL) { 329a4bd5210SJason Evans /* 330a4bd5210SJason Evans * An OOM error isn't worth propagating, since it doesn't 331a4bd5210SJason Evans * prevent this or future operations from proceeding. 332a4bd5210SJason Evans */ 333a4bd5210SJason Evans return; 334a4bd5210SJason Evans } 335a4bd5210SJason Evans /* Swap in new table. */ 336a4bd5210SJason Evans ttab = ckh->tab; 337a4bd5210SJason Evans ckh->tab = tab; 338a4bd5210SJason Evans tab = ttab; 339a4bd5210SJason Evans ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; 340a4bd5210SJason Evans 341d0e79aa3SJason Evans if (!ckh_rebuild(ckh, tab)) { 342b7eaed25SJason Evans idalloctm(tsd_tsdn(tsd), tab, NULL, NULL, true, true); 343a4bd5210SJason Evans #ifdef CKH_COUNT 344a4bd5210SJason Evans ckh->nshrinks++; 345a4bd5210SJason Evans #endif 346a4bd5210SJason Evans return; 347a4bd5210SJason Evans } 348a4bd5210SJason Evans 349a4bd5210SJason Evans /* Rebuilding failed, so back out partially rebuilt table. */ 350b7eaed25SJason Evans idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, NULL, true, true); 351a4bd5210SJason Evans ckh->tab = tab; 352a4bd5210SJason Evans ckh->lg_curbuckets = lg_prevbuckets; 353a4bd5210SJason Evans #ifdef CKH_COUNT 354a4bd5210SJason Evans ckh->nshrinkfails++; 355a4bd5210SJason Evans #endif 356a4bd5210SJason Evans } 357a4bd5210SJason Evans 358a4bd5210SJason Evans bool 359bde95144SJason Evans ckh_new(tsd_t *tsd, ckh_t *ckh, size_t minitems, ckh_hash_t *hash, 360b7eaed25SJason Evans ckh_keycomp_t *keycomp) { 361a4bd5210SJason Evans bool ret; 362a4bd5210SJason Evans size_t mincells, usize; 363a4bd5210SJason Evans unsigned lg_mincells; 364a4bd5210SJason Evans 365a4bd5210SJason Evans assert(minitems > 0); 366a4bd5210SJason Evans assert(hash != NULL); 367a4bd5210SJason Evans assert(keycomp != NULL); 368a4bd5210SJason Evans 369a4bd5210SJason Evans #ifdef CKH_COUNT 370a4bd5210SJason Evans ckh->ngrows = 0; 371a4bd5210SJason Evans ckh->nshrinks = 0; 372a4bd5210SJason Evans ckh->nshrinkfails = 0; 373a4bd5210SJason Evans ckh->ninserts = 0; 374a4bd5210SJason Evans ckh->nrelocs = 0; 375a4bd5210SJason Evans #endif 376a4bd5210SJason Evans ckh->prng_state = 42; /* Value doesn't really matter. */ 377a4bd5210SJason Evans ckh->count = 0; 378a4bd5210SJason Evans 379a4bd5210SJason Evans /* 380d0e79aa3SJason Evans * Find the minimum power of 2 that is large enough to fit minitems 381a4bd5210SJason Evans * entries. We are using (2+,2) cuckoo hashing, which has an expected 382a4bd5210SJason Evans * maximum load factor of at least ~0.86, so 0.75 is a conservative load 383d0e79aa3SJason Evans * factor that will typically allow mincells items to fit without ever 384a4bd5210SJason Evans * growing the table. 385a4bd5210SJason Evans */ 386a4bd5210SJason Evans assert(LG_CKH_BUCKET_CELLS > 0); 387a4bd5210SJason Evans mincells = ((minitems + (3 - (minitems % 3))) / 3) << 2; 388a4bd5210SJason Evans for (lg_mincells = LG_CKH_BUCKET_CELLS; 389a4bd5210SJason Evans (ZU(1) << lg_mincells) < mincells; 390b7eaed25SJason Evans lg_mincells++) { 391b7eaed25SJason Evans /* Do nothing. */ 392b7eaed25SJason Evans } 393a4bd5210SJason Evans ckh->lg_minbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; 394a4bd5210SJason Evans ckh->lg_curbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; 395a4bd5210SJason Evans ckh->hash = hash; 396a4bd5210SJason Evans ckh->keycomp = keycomp; 397a4bd5210SJason Evans 398b7eaed25SJason Evans usize = sz_sa2u(sizeof(ckhc_t) << lg_mincells, CACHELINE); 399b7eaed25SJason Evans if (unlikely(usize == 0 || usize > LARGE_MAXCLASS)) { 400a4bd5210SJason Evans ret = true; 401a4bd5210SJason Evans goto label_return; 402a4bd5210SJason Evans } 403bde95144SJason Evans ckh->tab = (ckhc_t *)ipallocztm(tsd_tsdn(tsd), usize, CACHELINE, true, 404bde95144SJason Evans NULL, true, arena_ichoose(tsd, NULL)); 405a4bd5210SJason Evans if (ckh->tab == NULL) { 406a4bd5210SJason Evans ret = true; 407a4bd5210SJason Evans goto label_return; 408a4bd5210SJason Evans } 409a4bd5210SJason Evans 410a4bd5210SJason Evans ret = false; 411a4bd5210SJason Evans label_return: 412b7eaed25SJason Evans return ret; 413a4bd5210SJason Evans } 414a4bd5210SJason Evans 415a4bd5210SJason Evans void 416b7eaed25SJason Evans ckh_delete(tsd_t *tsd, ckh_t *ckh) { 417a4bd5210SJason Evans assert(ckh != NULL); 418a4bd5210SJason Evans 419a4bd5210SJason Evans #ifdef CKH_VERBOSE 420a4bd5210SJason Evans malloc_printf( 421d0e79aa3SJason Evans "%s(%p): ngrows: %"FMTu64", nshrinks: %"FMTu64"," 422d0e79aa3SJason Evans " nshrinkfails: %"FMTu64", ninserts: %"FMTu64"," 423d0e79aa3SJason Evans " nrelocs: %"FMTu64"\n", __func__, ckh, 424a4bd5210SJason Evans (unsigned long long)ckh->ngrows, 425a4bd5210SJason Evans (unsigned long long)ckh->nshrinks, 426a4bd5210SJason Evans (unsigned long long)ckh->nshrinkfails, 427a4bd5210SJason Evans (unsigned long long)ckh->ninserts, 428a4bd5210SJason Evans (unsigned long long)ckh->nrelocs); 429a4bd5210SJason Evans #endif 430a4bd5210SJason Evans 431b7eaed25SJason Evans idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, NULL, true, true); 432b7eaed25SJason Evans if (config_debug) { 4331f0a49e8SJason Evans memset(ckh, JEMALLOC_FREE_JUNK, sizeof(ckh_t)); 434a4bd5210SJason Evans } 435b7eaed25SJason Evans } 436a4bd5210SJason Evans 437a4bd5210SJason Evans size_t 438b7eaed25SJason Evans ckh_count(ckh_t *ckh) { 439a4bd5210SJason Evans assert(ckh != NULL); 440a4bd5210SJason Evans 441b7eaed25SJason Evans return ckh->count; 442a4bd5210SJason Evans } 443a4bd5210SJason Evans 444a4bd5210SJason Evans bool 445b7eaed25SJason Evans ckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data) { 446a4bd5210SJason Evans size_t i, ncells; 447a4bd5210SJason Evans 448a4bd5210SJason Evans for (i = *tabind, ncells = (ZU(1) << (ckh->lg_curbuckets + 449a4bd5210SJason Evans LG_CKH_BUCKET_CELLS)); i < ncells; i++) { 450a4bd5210SJason Evans if (ckh->tab[i].key != NULL) { 451b7eaed25SJason Evans if (key != NULL) { 452a4bd5210SJason Evans *key = (void *)ckh->tab[i].key; 453b7eaed25SJason Evans } 454b7eaed25SJason Evans if (data != NULL) { 455a4bd5210SJason Evans *data = (void *)ckh->tab[i].data; 456b7eaed25SJason Evans } 457a4bd5210SJason Evans *tabind = i + 1; 458b7eaed25SJason Evans return false; 459a4bd5210SJason Evans } 460a4bd5210SJason Evans } 461a4bd5210SJason Evans 462b7eaed25SJason Evans return true; 463a4bd5210SJason Evans } 464a4bd5210SJason Evans 465a4bd5210SJason Evans bool 466b7eaed25SJason Evans ckh_insert(tsd_t *tsd, ckh_t *ckh, const void *key, const void *data) { 467a4bd5210SJason Evans bool ret; 468a4bd5210SJason Evans 469a4bd5210SJason Evans assert(ckh != NULL); 470a4bd5210SJason Evans assert(ckh_search(ckh, key, NULL, NULL)); 471a4bd5210SJason Evans 472a4bd5210SJason Evans #ifdef CKH_COUNT 473a4bd5210SJason Evans ckh->ninserts++; 474a4bd5210SJason Evans #endif 475a4bd5210SJason Evans 476a4bd5210SJason Evans while (ckh_try_insert(ckh, &key, &data)) { 477bde95144SJason Evans if (ckh_grow(tsd, ckh)) { 478a4bd5210SJason Evans ret = true; 479a4bd5210SJason Evans goto label_return; 480a4bd5210SJason Evans } 481a4bd5210SJason Evans } 482a4bd5210SJason Evans 483a4bd5210SJason Evans ret = false; 484a4bd5210SJason Evans label_return: 485b7eaed25SJason Evans return ret; 486a4bd5210SJason Evans } 487a4bd5210SJason Evans 488a4bd5210SJason Evans bool 489bde95144SJason Evans ckh_remove(tsd_t *tsd, ckh_t *ckh, const void *searchkey, void **key, 490b7eaed25SJason Evans void **data) { 491a4bd5210SJason Evans size_t cell; 492a4bd5210SJason Evans 493a4bd5210SJason Evans assert(ckh != NULL); 494a4bd5210SJason Evans 495a4bd5210SJason Evans cell = ckh_isearch(ckh, searchkey); 496a4bd5210SJason Evans if (cell != SIZE_T_MAX) { 497b7eaed25SJason Evans if (key != NULL) { 498a4bd5210SJason Evans *key = (void *)ckh->tab[cell].key; 499b7eaed25SJason Evans } 500b7eaed25SJason Evans if (data != NULL) { 501a4bd5210SJason Evans *data = (void *)ckh->tab[cell].data; 502b7eaed25SJason Evans } 503a4bd5210SJason Evans ckh->tab[cell].key = NULL; 504a4bd5210SJason Evans ckh->tab[cell].data = NULL; /* Not necessary. */ 505a4bd5210SJason Evans 506a4bd5210SJason Evans ckh->count--; 507a4bd5210SJason Evans /* Try to halve the table if it is less than 1/4 full. */ 508a4bd5210SJason Evans if (ckh->count < (ZU(1) << (ckh->lg_curbuckets 509a4bd5210SJason Evans + LG_CKH_BUCKET_CELLS - 2)) && ckh->lg_curbuckets 510a4bd5210SJason Evans > ckh->lg_minbuckets) { 511a4bd5210SJason Evans /* Ignore error due to OOM. */ 512bde95144SJason Evans ckh_shrink(tsd, ckh); 513a4bd5210SJason Evans } 514a4bd5210SJason Evans 515b7eaed25SJason Evans return false; 516a4bd5210SJason Evans } 517a4bd5210SJason Evans 518b7eaed25SJason Evans return true; 519a4bd5210SJason Evans } 520a4bd5210SJason Evans 521a4bd5210SJason Evans bool 522b7eaed25SJason Evans ckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data) { 523a4bd5210SJason Evans size_t cell; 524a4bd5210SJason Evans 525a4bd5210SJason Evans assert(ckh != NULL); 526a4bd5210SJason Evans 527a4bd5210SJason Evans cell = ckh_isearch(ckh, searchkey); 528a4bd5210SJason Evans if (cell != SIZE_T_MAX) { 529b7eaed25SJason Evans if (key != NULL) { 530a4bd5210SJason Evans *key = (void *)ckh->tab[cell].key; 531b7eaed25SJason Evans } 532b7eaed25SJason Evans if (data != NULL) { 533a4bd5210SJason Evans *data = (void *)ckh->tab[cell].data; 534b7eaed25SJason Evans } 535b7eaed25SJason Evans return false; 536a4bd5210SJason Evans } 537a4bd5210SJason Evans 538b7eaed25SJason Evans return true; 539a4bd5210SJason Evans } 540a4bd5210SJason Evans 541a4bd5210SJason Evans void 542b7eaed25SJason Evans ckh_string_hash(const void *key, size_t r_hash[2]) { 54388ad2f8dSJason Evans hash(key, strlen((const char *)key), 0x94122f33U, r_hash); 544a4bd5210SJason Evans } 545a4bd5210SJason Evans 546a4bd5210SJason Evans bool 547b7eaed25SJason Evans ckh_string_keycomp(const void *k1, const void *k2) { 548a4bd5210SJason Evans assert(k1 != NULL); 549a4bd5210SJason Evans assert(k2 != NULL); 550a4bd5210SJason Evans 551b7eaed25SJason Evans return !strcmp((char *)k1, (char *)k2); 552a4bd5210SJason Evans } 553a4bd5210SJason Evans 554a4bd5210SJason Evans void 555b7eaed25SJason Evans ckh_pointer_hash(const void *key, size_t r_hash[2]) { 556a4bd5210SJason Evans union { 557a4bd5210SJason Evans const void *v; 55888ad2f8dSJason Evans size_t i; 559a4bd5210SJason Evans } u; 560a4bd5210SJason Evans 561a4bd5210SJason Evans assert(sizeof(u.v) == sizeof(u.i)); 562a4bd5210SJason Evans u.v = key; 56388ad2f8dSJason Evans hash(&u.i, sizeof(u.i), 0xd983396eU, r_hash); 564a4bd5210SJason Evans } 565a4bd5210SJason Evans 566a4bd5210SJason Evans bool 567b7eaed25SJason Evans ckh_pointer_keycomp(const void *k1, const void *k2) { 568b7eaed25SJason Evans return (k1 == k2); 569a4bd5210SJason Evans } 570