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_ 38a4bd5210SJason Evans #include "jemalloc/internal/jemalloc_internal.h" 39a4bd5210SJason Evans 40a4bd5210SJason Evans /******************************************************************************/ 41a4bd5210SJason Evans /* Function prototypes for non-inline static functions. */ 42a4bd5210SJason Evans 43a4bd5210SJason Evans static bool ckh_grow(ckh_t *ckh); 44a4bd5210SJason Evans static void ckh_shrink(ckh_t *ckh); 45a4bd5210SJason Evans 46a4bd5210SJason Evans /******************************************************************************/ 47a4bd5210SJason Evans 48a4bd5210SJason Evans /* 49a4bd5210SJason Evans * Search bucket for key and return the cell number if found; SIZE_T_MAX 50a4bd5210SJason Evans * otherwise. 51a4bd5210SJason Evans */ 52a4bd5210SJason Evans JEMALLOC_INLINE size_t 53a4bd5210SJason Evans ckh_bucket_search(ckh_t *ckh, size_t bucket, const void *key) 54a4bd5210SJason Evans { 55a4bd5210SJason Evans ckhc_t *cell; 56a4bd5210SJason Evans unsigned i; 57a4bd5210SJason Evans 58a4bd5210SJason Evans for (i = 0; i < (ZU(1) << LG_CKH_BUCKET_CELLS); i++) { 59a4bd5210SJason Evans cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; 60a4bd5210SJason Evans if (cell->key != NULL && ckh->keycomp(key, cell->key)) 61a4bd5210SJason Evans return ((bucket << LG_CKH_BUCKET_CELLS) + i); 62a4bd5210SJason Evans } 63a4bd5210SJason Evans 64a4bd5210SJason Evans return (SIZE_T_MAX); 65a4bd5210SJason Evans } 66a4bd5210SJason Evans 67a4bd5210SJason Evans /* 68a4bd5210SJason Evans * Search table for key and return cell number if found; SIZE_T_MAX otherwise. 69a4bd5210SJason Evans */ 70a4bd5210SJason Evans JEMALLOC_INLINE size_t 71a4bd5210SJason Evans ckh_isearch(ckh_t *ckh, const void *key) 72a4bd5210SJason Evans { 73a4bd5210SJason Evans size_t hash1, hash2, bucket, cell; 74a4bd5210SJason Evans 75a4bd5210SJason Evans assert(ckh != NULL); 76a4bd5210SJason Evans 77a4bd5210SJason Evans ckh->hash(key, ckh->lg_curbuckets, &hash1, &hash2); 78a4bd5210SJason Evans 79a4bd5210SJason Evans /* Search primary bucket. */ 80a4bd5210SJason Evans bucket = hash1 & ((ZU(1) << ckh->lg_curbuckets) - 1); 81a4bd5210SJason Evans cell = ckh_bucket_search(ckh, bucket, key); 82a4bd5210SJason Evans if (cell != SIZE_T_MAX) 83a4bd5210SJason Evans return (cell); 84a4bd5210SJason Evans 85a4bd5210SJason Evans /* Search secondary bucket. */ 86a4bd5210SJason Evans bucket = hash2 & ((ZU(1) << ckh->lg_curbuckets) - 1); 87a4bd5210SJason Evans cell = ckh_bucket_search(ckh, bucket, key); 88a4bd5210SJason Evans return (cell); 89a4bd5210SJason Evans } 90a4bd5210SJason Evans 91a4bd5210SJason Evans JEMALLOC_INLINE bool 92a4bd5210SJason Evans ckh_try_bucket_insert(ckh_t *ckh, size_t bucket, const void *key, 93a4bd5210SJason Evans const void *data) 94a4bd5210SJason Evans { 95a4bd5210SJason Evans ckhc_t *cell; 96a4bd5210SJason Evans unsigned offset, i; 97a4bd5210SJason Evans 98a4bd5210SJason Evans /* 99a4bd5210SJason Evans * Cycle through the cells in the bucket, starting at a random position. 100a4bd5210SJason Evans * The randomness avoids worst-case search overhead as buckets fill up. 101a4bd5210SJason Evans */ 102a4bd5210SJason Evans prng32(offset, LG_CKH_BUCKET_CELLS, ckh->prng_state, CKH_A, CKH_C); 103a4bd5210SJason Evans for (i = 0; i < (ZU(1) << LG_CKH_BUCKET_CELLS); i++) { 104a4bd5210SJason Evans cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + 105a4bd5210SJason Evans ((i + offset) & ((ZU(1) << LG_CKH_BUCKET_CELLS) - 1))]; 106a4bd5210SJason Evans if (cell->key == NULL) { 107a4bd5210SJason Evans cell->key = key; 108a4bd5210SJason Evans cell->data = data; 109a4bd5210SJason Evans ckh->count++; 110a4bd5210SJason Evans return (false); 111a4bd5210SJason Evans } 112a4bd5210SJason Evans } 113a4bd5210SJason Evans 114a4bd5210SJason Evans return (true); 115a4bd5210SJason Evans } 116a4bd5210SJason Evans 117a4bd5210SJason Evans /* 118a4bd5210SJason Evans * No space is available in bucket. Randomly evict an item, then try to find an 119a4bd5210SJason Evans * alternate location for that item. Iteratively repeat this 120a4bd5210SJason Evans * eviction/relocation procedure until either success or detection of an 121a4bd5210SJason Evans * eviction/relocation bucket cycle. 122a4bd5210SJason Evans */ 123a4bd5210SJason Evans JEMALLOC_INLINE bool 124a4bd5210SJason Evans ckh_evict_reloc_insert(ckh_t *ckh, size_t argbucket, void const **argkey, 125a4bd5210SJason Evans void const **argdata) 126a4bd5210SJason Evans { 127a4bd5210SJason Evans const void *key, *data, *tkey, *tdata; 128a4bd5210SJason Evans ckhc_t *cell; 129a4bd5210SJason Evans size_t hash1, hash2, bucket, tbucket; 130a4bd5210SJason Evans unsigned i; 131a4bd5210SJason Evans 132a4bd5210SJason Evans bucket = argbucket; 133a4bd5210SJason Evans key = *argkey; 134a4bd5210SJason Evans data = *argdata; 135a4bd5210SJason Evans while (true) { 136a4bd5210SJason Evans /* 137a4bd5210SJason Evans * Choose a random item within the bucket to evict. This is 138a4bd5210SJason Evans * critical to correct function, because without (eventually) 139a4bd5210SJason Evans * evicting all items within a bucket during iteration, it 140a4bd5210SJason Evans * would be possible to get stuck in an infinite loop if there 141a4bd5210SJason Evans * were an item for which both hashes indicated the same 142a4bd5210SJason Evans * bucket. 143a4bd5210SJason Evans */ 144a4bd5210SJason Evans prng32(i, LG_CKH_BUCKET_CELLS, ckh->prng_state, CKH_A, CKH_C); 145a4bd5210SJason Evans cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; 146a4bd5210SJason Evans assert(cell->key != NULL); 147a4bd5210SJason Evans 148a4bd5210SJason Evans /* Swap cell->{key,data} and {key,data} (evict). */ 149a4bd5210SJason Evans tkey = cell->key; tdata = cell->data; 150a4bd5210SJason Evans cell->key = key; cell->data = data; 151a4bd5210SJason Evans key = tkey; data = tdata; 152a4bd5210SJason Evans 153a4bd5210SJason Evans #ifdef CKH_COUNT 154a4bd5210SJason Evans ckh->nrelocs++; 155a4bd5210SJason Evans #endif 156a4bd5210SJason Evans 157a4bd5210SJason Evans /* Find the alternate bucket for the evicted item. */ 158a4bd5210SJason Evans ckh->hash(key, ckh->lg_curbuckets, &hash1, &hash2); 159a4bd5210SJason Evans tbucket = hash2 & ((ZU(1) << ckh->lg_curbuckets) - 1); 160a4bd5210SJason Evans if (tbucket == bucket) { 161a4bd5210SJason Evans tbucket = hash1 & ((ZU(1) << ckh->lg_curbuckets) - 1); 162a4bd5210SJason Evans /* 163a4bd5210SJason Evans * It may be that (tbucket == bucket) still, if the 164a4bd5210SJason Evans * item's hashes both indicate this bucket. However, 165a4bd5210SJason Evans * we are guaranteed to eventually escape this bucket 166a4bd5210SJason Evans * during iteration, assuming pseudo-random item 167a4bd5210SJason Evans * selection (true randomness would make infinite 168a4bd5210SJason Evans * looping a remote possibility). The reason we can 169a4bd5210SJason Evans * never get trapped forever is that there are two 170a4bd5210SJason Evans * cases: 171a4bd5210SJason Evans * 172a4bd5210SJason Evans * 1) This bucket == argbucket, so we will quickly 173a4bd5210SJason Evans * detect an eviction cycle and terminate. 174a4bd5210SJason Evans * 2) An item was evicted to this bucket from another, 175a4bd5210SJason Evans * which means that at least one item in this bucket 176a4bd5210SJason Evans * has hashes that indicate distinct buckets. 177a4bd5210SJason Evans */ 178a4bd5210SJason Evans } 179a4bd5210SJason Evans /* Check for a cycle. */ 180a4bd5210SJason Evans if (tbucket == argbucket) { 181a4bd5210SJason Evans *argkey = key; 182a4bd5210SJason Evans *argdata = data; 183a4bd5210SJason Evans return (true); 184a4bd5210SJason Evans } 185a4bd5210SJason Evans 186a4bd5210SJason Evans bucket = tbucket; 187a4bd5210SJason Evans if (ckh_try_bucket_insert(ckh, bucket, key, data) == false) 188a4bd5210SJason Evans return (false); 189a4bd5210SJason Evans } 190a4bd5210SJason Evans } 191a4bd5210SJason Evans 192a4bd5210SJason Evans JEMALLOC_INLINE bool 193a4bd5210SJason Evans ckh_try_insert(ckh_t *ckh, void const**argkey, void const**argdata) 194a4bd5210SJason Evans { 195a4bd5210SJason Evans size_t hash1, hash2, bucket; 196a4bd5210SJason Evans const void *key = *argkey; 197a4bd5210SJason Evans const void *data = *argdata; 198a4bd5210SJason Evans 199a4bd5210SJason Evans ckh->hash(key, ckh->lg_curbuckets, &hash1, &hash2); 200a4bd5210SJason Evans 201a4bd5210SJason Evans /* Try to insert in primary bucket. */ 202a4bd5210SJason Evans bucket = hash1 & ((ZU(1) << ckh->lg_curbuckets) - 1); 203a4bd5210SJason Evans if (ckh_try_bucket_insert(ckh, bucket, key, data) == false) 204a4bd5210SJason Evans return (false); 205a4bd5210SJason Evans 206a4bd5210SJason Evans /* Try to insert in secondary bucket. */ 207a4bd5210SJason Evans bucket = hash2 & ((ZU(1) << ckh->lg_curbuckets) - 1); 208a4bd5210SJason Evans if (ckh_try_bucket_insert(ckh, bucket, key, data) == false) 209a4bd5210SJason Evans return (false); 210a4bd5210SJason Evans 211a4bd5210SJason Evans /* 212a4bd5210SJason Evans * Try to find a place for this item via iterative eviction/relocation. 213a4bd5210SJason Evans */ 214a4bd5210SJason Evans return (ckh_evict_reloc_insert(ckh, bucket, argkey, argdata)); 215a4bd5210SJason Evans } 216a4bd5210SJason Evans 217a4bd5210SJason Evans /* 218a4bd5210SJason Evans * Try to rebuild the hash table from scratch by inserting all items from the 219a4bd5210SJason Evans * old table into the new. 220a4bd5210SJason Evans */ 221a4bd5210SJason Evans JEMALLOC_INLINE bool 222a4bd5210SJason Evans ckh_rebuild(ckh_t *ckh, ckhc_t *aTab) 223a4bd5210SJason Evans { 224a4bd5210SJason Evans size_t count, i, nins; 225a4bd5210SJason Evans const void *key, *data; 226a4bd5210SJason Evans 227a4bd5210SJason Evans count = ckh->count; 228a4bd5210SJason Evans ckh->count = 0; 229a4bd5210SJason Evans for (i = nins = 0; nins < count; i++) { 230a4bd5210SJason Evans if (aTab[i].key != NULL) { 231a4bd5210SJason Evans key = aTab[i].key; 232a4bd5210SJason Evans data = aTab[i].data; 233a4bd5210SJason Evans if (ckh_try_insert(ckh, &key, &data)) { 234a4bd5210SJason Evans ckh->count = count; 235a4bd5210SJason Evans return (true); 236a4bd5210SJason Evans } 237a4bd5210SJason Evans nins++; 238a4bd5210SJason Evans } 239a4bd5210SJason Evans } 240a4bd5210SJason Evans 241a4bd5210SJason Evans return (false); 242a4bd5210SJason Evans } 243a4bd5210SJason Evans 244a4bd5210SJason Evans static bool 245a4bd5210SJason Evans ckh_grow(ckh_t *ckh) 246a4bd5210SJason Evans { 247a4bd5210SJason Evans bool ret; 248a4bd5210SJason Evans ckhc_t *tab, *ttab; 249a4bd5210SJason Evans size_t lg_curcells; 250a4bd5210SJason Evans unsigned lg_prevbuckets; 251a4bd5210SJason Evans 252a4bd5210SJason Evans #ifdef CKH_COUNT 253a4bd5210SJason Evans ckh->ngrows++; 254a4bd5210SJason Evans #endif 255a4bd5210SJason Evans 256a4bd5210SJason Evans /* 257a4bd5210SJason Evans * It is possible (though unlikely, given well behaved hashes) that the 258a4bd5210SJason Evans * table will have to be doubled more than once in order to create a 259a4bd5210SJason Evans * usable table. 260a4bd5210SJason Evans */ 261a4bd5210SJason Evans lg_prevbuckets = ckh->lg_curbuckets; 262a4bd5210SJason Evans lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS; 263a4bd5210SJason Evans while (true) { 264a4bd5210SJason Evans size_t usize; 265a4bd5210SJason Evans 266a4bd5210SJason Evans lg_curcells++; 267a4bd5210SJason Evans usize = sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE); 268a4bd5210SJason Evans if (usize == 0) { 269a4bd5210SJason Evans ret = true; 270a4bd5210SJason Evans goto label_return; 271a4bd5210SJason Evans } 272a4bd5210SJason Evans tab = (ckhc_t *)ipalloc(usize, CACHELINE, true); 273a4bd5210SJason Evans if (tab == NULL) { 274a4bd5210SJason Evans ret = true; 275a4bd5210SJason Evans goto label_return; 276a4bd5210SJason Evans } 277a4bd5210SJason Evans /* Swap in new table. */ 278a4bd5210SJason Evans ttab = ckh->tab; 279a4bd5210SJason Evans ckh->tab = tab; 280a4bd5210SJason Evans tab = ttab; 281a4bd5210SJason Evans ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; 282a4bd5210SJason Evans 283a4bd5210SJason Evans if (ckh_rebuild(ckh, tab) == false) { 284a4bd5210SJason Evans idalloc(tab); 285a4bd5210SJason Evans break; 286a4bd5210SJason Evans } 287a4bd5210SJason Evans 288a4bd5210SJason Evans /* Rebuilding failed, so back out partially rebuilt table. */ 289a4bd5210SJason Evans idalloc(ckh->tab); 290a4bd5210SJason Evans ckh->tab = tab; 291a4bd5210SJason Evans ckh->lg_curbuckets = lg_prevbuckets; 292a4bd5210SJason Evans } 293a4bd5210SJason Evans 294a4bd5210SJason Evans ret = false; 295a4bd5210SJason Evans label_return: 296a4bd5210SJason Evans return (ret); 297a4bd5210SJason Evans } 298a4bd5210SJason Evans 299a4bd5210SJason Evans static void 300a4bd5210SJason Evans ckh_shrink(ckh_t *ckh) 301a4bd5210SJason Evans { 302a4bd5210SJason Evans ckhc_t *tab, *ttab; 303a4bd5210SJason Evans size_t lg_curcells, usize; 304a4bd5210SJason Evans unsigned lg_prevbuckets; 305a4bd5210SJason Evans 306a4bd5210SJason Evans /* 307a4bd5210SJason Evans * It is possible (though unlikely, given well behaved hashes) that the 308a4bd5210SJason Evans * table rebuild will fail. 309a4bd5210SJason Evans */ 310a4bd5210SJason Evans lg_prevbuckets = ckh->lg_curbuckets; 311a4bd5210SJason Evans lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS - 1; 312a4bd5210SJason Evans usize = sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE); 313a4bd5210SJason Evans if (usize == 0) 314a4bd5210SJason Evans return; 315a4bd5210SJason Evans tab = (ckhc_t *)ipalloc(usize, CACHELINE, true); 316a4bd5210SJason Evans if (tab == NULL) { 317a4bd5210SJason Evans /* 318a4bd5210SJason Evans * An OOM error isn't worth propagating, since it doesn't 319a4bd5210SJason Evans * prevent this or future operations from proceeding. 320a4bd5210SJason Evans */ 321a4bd5210SJason Evans return; 322a4bd5210SJason Evans } 323a4bd5210SJason Evans /* Swap in new table. */ 324a4bd5210SJason Evans ttab = ckh->tab; 325a4bd5210SJason Evans ckh->tab = tab; 326a4bd5210SJason Evans tab = ttab; 327a4bd5210SJason Evans ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; 328a4bd5210SJason Evans 329a4bd5210SJason Evans if (ckh_rebuild(ckh, tab) == false) { 330a4bd5210SJason Evans idalloc(tab); 331a4bd5210SJason Evans #ifdef CKH_COUNT 332a4bd5210SJason Evans ckh->nshrinks++; 333a4bd5210SJason Evans #endif 334a4bd5210SJason Evans return; 335a4bd5210SJason Evans } 336a4bd5210SJason Evans 337a4bd5210SJason Evans /* Rebuilding failed, so back out partially rebuilt table. */ 338a4bd5210SJason Evans idalloc(ckh->tab); 339a4bd5210SJason Evans ckh->tab = tab; 340a4bd5210SJason Evans ckh->lg_curbuckets = lg_prevbuckets; 341a4bd5210SJason Evans #ifdef CKH_COUNT 342a4bd5210SJason Evans ckh->nshrinkfails++; 343a4bd5210SJason Evans #endif 344a4bd5210SJason Evans } 345a4bd5210SJason Evans 346a4bd5210SJason Evans bool 347a4bd5210SJason Evans ckh_new(ckh_t *ckh, size_t minitems, ckh_hash_t *hash, ckh_keycomp_t *keycomp) 348a4bd5210SJason Evans { 349a4bd5210SJason Evans bool ret; 350a4bd5210SJason Evans size_t mincells, usize; 351a4bd5210SJason Evans unsigned lg_mincells; 352a4bd5210SJason Evans 353a4bd5210SJason Evans assert(minitems > 0); 354a4bd5210SJason Evans assert(hash != NULL); 355a4bd5210SJason Evans assert(keycomp != NULL); 356a4bd5210SJason Evans 357a4bd5210SJason Evans #ifdef CKH_COUNT 358a4bd5210SJason Evans ckh->ngrows = 0; 359a4bd5210SJason Evans ckh->nshrinks = 0; 360a4bd5210SJason Evans ckh->nshrinkfails = 0; 361a4bd5210SJason Evans ckh->ninserts = 0; 362a4bd5210SJason Evans ckh->nrelocs = 0; 363a4bd5210SJason Evans #endif 364a4bd5210SJason Evans ckh->prng_state = 42; /* Value doesn't really matter. */ 365a4bd5210SJason Evans ckh->count = 0; 366a4bd5210SJason Evans 367a4bd5210SJason Evans /* 368a4bd5210SJason Evans * Find the minimum power of 2 that is large enough to fit aBaseCount 369a4bd5210SJason Evans * entries. We are using (2+,2) cuckoo hashing, which has an expected 370a4bd5210SJason Evans * maximum load factor of at least ~0.86, so 0.75 is a conservative load 371a4bd5210SJason Evans * factor that will typically allow 2^aLgMinItems to fit without ever 372a4bd5210SJason Evans * growing the table. 373a4bd5210SJason Evans */ 374a4bd5210SJason Evans assert(LG_CKH_BUCKET_CELLS > 0); 375a4bd5210SJason Evans mincells = ((minitems + (3 - (minitems % 3))) / 3) << 2; 376a4bd5210SJason Evans for (lg_mincells = LG_CKH_BUCKET_CELLS; 377a4bd5210SJason Evans (ZU(1) << lg_mincells) < mincells; 378a4bd5210SJason Evans lg_mincells++) 379a4bd5210SJason Evans ; /* Do nothing. */ 380a4bd5210SJason Evans ckh->lg_minbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; 381a4bd5210SJason Evans ckh->lg_curbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; 382a4bd5210SJason Evans ckh->hash = hash; 383a4bd5210SJason Evans ckh->keycomp = keycomp; 384a4bd5210SJason Evans 385a4bd5210SJason Evans usize = sa2u(sizeof(ckhc_t) << lg_mincells, CACHELINE); 386a4bd5210SJason Evans if (usize == 0) { 387a4bd5210SJason Evans ret = true; 388a4bd5210SJason Evans goto label_return; 389a4bd5210SJason Evans } 390a4bd5210SJason Evans ckh->tab = (ckhc_t *)ipalloc(usize, CACHELINE, true); 391a4bd5210SJason Evans if (ckh->tab == NULL) { 392a4bd5210SJason Evans ret = true; 393a4bd5210SJason Evans goto label_return; 394a4bd5210SJason Evans } 395a4bd5210SJason Evans 396a4bd5210SJason Evans ret = false; 397a4bd5210SJason Evans label_return: 398a4bd5210SJason Evans return (ret); 399a4bd5210SJason Evans } 400a4bd5210SJason Evans 401a4bd5210SJason Evans void 402a4bd5210SJason Evans ckh_delete(ckh_t *ckh) 403a4bd5210SJason Evans { 404a4bd5210SJason Evans 405a4bd5210SJason Evans assert(ckh != NULL); 406a4bd5210SJason Evans 407a4bd5210SJason Evans #ifdef CKH_VERBOSE 408a4bd5210SJason Evans malloc_printf( 409a4bd5210SJason Evans "%s(%p): ngrows: %"PRIu64", nshrinks: %"PRIu64"," 410a4bd5210SJason Evans " nshrinkfails: %"PRIu64", ninserts: %"PRIu64"," 411a4bd5210SJason Evans " nrelocs: %"PRIu64"\n", __func__, ckh, 412a4bd5210SJason Evans (unsigned long long)ckh->ngrows, 413a4bd5210SJason Evans (unsigned long long)ckh->nshrinks, 414a4bd5210SJason Evans (unsigned long long)ckh->nshrinkfails, 415a4bd5210SJason Evans (unsigned long long)ckh->ninserts, 416a4bd5210SJason Evans (unsigned long long)ckh->nrelocs); 417a4bd5210SJason Evans #endif 418a4bd5210SJason Evans 419a4bd5210SJason Evans idalloc(ckh->tab); 420a4bd5210SJason Evans #ifdef JEMALLOC_DEBUG 421a4bd5210SJason Evans memset(ckh, 0x5a, sizeof(ckh_t)); 422a4bd5210SJason Evans #endif 423a4bd5210SJason Evans } 424a4bd5210SJason Evans 425a4bd5210SJason Evans size_t 426a4bd5210SJason Evans ckh_count(ckh_t *ckh) 427a4bd5210SJason Evans { 428a4bd5210SJason Evans 429a4bd5210SJason Evans assert(ckh != NULL); 430a4bd5210SJason Evans 431a4bd5210SJason Evans return (ckh->count); 432a4bd5210SJason Evans } 433a4bd5210SJason Evans 434a4bd5210SJason Evans bool 435a4bd5210SJason Evans ckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data) 436a4bd5210SJason Evans { 437a4bd5210SJason Evans size_t i, ncells; 438a4bd5210SJason Evans 439a4bd5210SJason Evans for (i = *tabind, ncells = (ZU(1) << (ckh->lg_curbuckets + 440a4bd5210SJason Evans LG_CKH_BUCKET_CELLS)); i < ncells; i++) { 441a4bd5210SJason Evans if (ckh->tab[i].key != NULL) { 442a4bd5210SJason Evans if (key != NULL) 443a4bd5210SJason Evans *key = (void *)ckh->tab[i].key; 444a4bd5210SJason Evans if (data != NULL) 445a4bd5210SJason Evans *data = (void *)ckh->tab[i].data; 446a4bd5210SJason Evans *tabind = i + 1; 447a4bd5210SJason Evans return (false); 448a4bd5210SJason Evans } 449a4bd5210SJason Evans } 450a4bd5210SJason Evans 451a4bd5210SJason Evans return (true); 452a4bd5210SJason Evans } 453a4bd5210SJason Evans 454a4bd5210SJason Evans bool 455a4bd5210SJason Evans ckh_insert(ckh_t *ckh, const void *key, const void *data) 456a4bd5210SJason Evans { 457a4bd5210SJason Evans bool ret; 458a4bd5210SJason Evans 459a4bd5210SJason Evans assert(ckh != NULL); 460a4bd5210SJason Evans assert(ckh_search(ckh, key, NULL, NULL)); 461a4bd5210SJason Evans 462a4bd5210SJason Evans #ifdef CKH_COUNT 463a4bd5210SJason Evans ckh->ninserts++; 464a4bd5210SJason Evans #endif 465a4bd5210SJason Evans 466a4bd5210SJason Evans while (ckh_try_insert(ckh, &key, &data)) { 467a4bd5210SJason Evans if (ckh_grow(ckh)) { 468a4bd5210SJason Evans ret = true; 469a4bd5210SJason Evans goto label_return; 470a4bd5210SJason Evans } 471a4bd5210SJason Evans } 472a4bd5210SJason Evans 473a4bd5210SJason Evans ret = false; 474a4bd5210SJason Evans label_return: 475a4bd5210SJason Evans return (ret); 476a4bd5210SJason Evans } 477a4bd5210SJason Evans 478a4bd5210SJason Evans bool 479a4bd5210SJason Evans ckh_remove(ckh_t *ckh, const void *searchkey, void **key, void **data) 480a4bd5210SJason Evans { 481a4bd5210SJason Evans size_t cell; 482a4bd5210SJason Evans 483a4bd5210SJason Evans assert(ckh != NULL); 484a4bd5210SJason Evans 485a4bd5210SJason Evans cell = ckh_isearch(ckh, searchkey); 486a4bd5210SJason Evans if (cell != SIZE_T_MAX) { 487a4bd5210SJason Evans if (key != NULL) 488a4bd5210SJason Evans *key = (void *)ckh->tab[cell].key; 489a4bd5210SJason Evans if (data != NULL) 490a4bd5210SJason Evans *data = (void *)ckh->tab[cell].data; 491a4bd5210SJason Evans ckh->tab[cell].key = NULL; 492a4bd5210SJason Evans ckh->tab[cell].data = NULL; /* Not necessary. */ 493a4bd5210SJason Evans 494a4bd5210SJason Evans ckh->count--; 495a4bd5210SJason Evans /* Try to halve the table if it is less than 1/4 full. */ 496a4bd5210SJason Evans if (ckh->count < (ZU(1) << (ckh->lg_curbuckets 497a4bd5210SJason Evans + LG_CKH_BUCKET_CELLS - 2)) && ckh->lg_curbuckets 498a4bd5210SJason Evans > ckh->lg_minbuckets) { 499a4bd5210SJason Evans /* Ignore error due to OOM. */ 500a4bd5210SJason Evans ckh_shrink(ckh); 501a4bd5210SJason Evans } 502a4bd5210SJason Evans 503a4bd5210SJason Evans return (false); 504a4bd5210SJason Evans } 505a4bd5210SJason Evans 506a4bd5210SJason Evans return (true); 507a4bd5210SJason Evans } 508a4bd5210SJason Evans 509a4bd5210SJason Evans bool 510a4bd5210SJason Evans ckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data) 511a4bd5210SJason Evans { 512a4bd5210SJason Evans size_t cell; 513a4bd5210SJason Evans 514a4bd5210SJason Evans assert(ckh != NULL); 515a4bd5210SJason Evans 516a4bd5210SJason Evans cell = ckh_isearch(ckh, searchkey); 517a4bd5210SJason Evans if (cell != SIZE_T_MAX) { 518a4bd5210SJason Evans if (key != NULL) 519a4bd5210SJason Evans *key = (void *)ckh->tab[cell].key; 520a4bd5210SJason Evans if (data != NULL) 521a4bd5210SJason Evans *data = (void *)ckh->tab[cell].data; 522a4bd5210SJason Evans return (false); 523a4bd5210SJason Evans } 524a4bd5210SJason Evans 525a4bd5210SJason Evans return (true); 526a4bd5210SJason Evans } 527a4bd5210SJason Evans 528a4bd5210SJason Evans void 529a4bd5210SJason Evans ckh_string_hash(const void *key, unsigned minbits, size_t *hash1, size_t *hash2) 530a4bd5210SJason Evans { 531a4bd5210SJason Evans size_t ret1, ret2; 532a4bd5210SJason Evans uint64_t h; 533a4bd5210SJason Evans 534a4bd5210SJason Evans assert(minbits <= 32 || (SIZEOF_PTR == 8 && minbits <= 64)); 535a4bd5210SJason Evans assert(hash1 != NULL); 536a4bd5210SJason Evans assert(hash2 != NULL); 537a4bd5210SJason Evans 538a4bd5210SJason Evans h = hash(key, strlen((const char *)key), UINT64_C(0x94122f335b332aea)); 539a4bd5210SJason Evans if (minbits <= 32) { 540a4bd5210SJason Evans /* 541a4bd5210SJason Evans * Avoid doing multiple hashes, since a single hash provides 542a4bd5210SJason Evans * enough bits. 543a4bd5210SJason Evans */ 544a4bd5210SJason Evans ret1 = h & ZU(0xffffffffU); 545a4bd5210SJason Evans ret2 = h >> 32; 546a4bd5210SJason Evans } else { 547a4bd5210SJason Evans ret1 = h; 548a4bd5210SJason Evans ret2 = hash(key, strlen((const char *)key), 549a4bd5210SJason Evans UINT64_C(0x8432a476666bbc13)); 550a4bd5210SJason Evans } 551a4bd5210SJason Evans 552a4bd5210SJason Evans *hash1 = ret1; 553a4bd5210SJason Evans *hash2 = ret2; 554a4bd5210SJason Evans } 555a4bd5210SJason Evans 556a4bd5210SJason Evans bool 557a4bd5210SJason Evans ckh_string_keycomp(const void *k1, const void *k2) 558a4bd5210SJason Evans { 559a4bd5210SJason Evans 560a4bd5210SJason Evans assert(k1 != NULL); 561a4bd5210SJason Evans assert(k2 != NULL); 562a4bd5210SJason Evans 563a4bd5210SJason Evans return (strcmp((char *)k1, (char *)k2) ? false : true); 564a4bd5210SJason Evans } 565a4bd5210SJason Evans 566a4bd5210SJason Evans void 567a4bd5210SJason Evans ckh_pointer_hash(const void *key, unsigned minbits, size_t *hash1, 568a4bd5210SJason Evans size_t *hash2) 569a4bd5210SJason Evans { 570a4bd5210SJason Evans size_t ret1, ret2; 571a4bd5210SJason Evans uint64_t h; 572a4bd5210SJason Evans union { 573a4bd5210SJason Evans const void *v; 574a4bd5210SJason Evans uint64_t i; 575a4bd5210SJason Evans } u; 576a4bd5210SJason Evans 577a4bd5210SJason Evans assert(minbits <= 32 || (SIZEOF_PTR == 8 && minbits <= 64)); 578a4bd5210SJason Evans assert(hash1 != NULL); 579a4bd5210SJason Evans assert(hash2 != NULL); 580a4bd5210SJason Evans 581a4bd5210SJason Evans assert(sizeof(u.v) == sizeof(u.i)); 582a4bd5210SJason Evans #if (LG_SIZEOF_PTR != LG_SIZEOF_INT) 583a4bd5210SJason Evans u.i = 0; 584a4bd5210SJason Evans #endif 585a4bd5210SJason Evans u.v = key; 586a4bd5210SJason Evans h = hash(&u.i, sizeof(u.i), UINT64_C(0xd983396e68886082)); 587a4bd5210SJason Evans if (minbits <= 32) { 588a4bd5210SJason Evans /* 589a4bd5210SJason Evans * Avoid doing multiple hashes, since a single hash provides 590a4bd5210SJason Evans * enough bits. 591a4bd5210SJason Evans */ 592a4bd5210SJason Evans ret1 = h & ZU(0xffffffffU); 593a4bd5210SJason Evans ret2 = h >> 32; 594a4bd5210SJason Evans } else { 595a4bd5210SJason Evans assert(SIZEOF_PTR == 8); 596a4bd5210SJason Evans ret1 = h; 597a4bd5210SJason Evans ret2 = hash(&u.i, sizeof(u.i), UINT64_C(0x5e2be9aff8709a5d)); 598a4bd5210SJason Evans } 599a4bd5210SJason Evans 600a4bd5210SJason Evans *hash1 = ret1; 601a4bd5210SJason Evans *hash2 = ret2; 602a4bd5210SJason Evans } 603a4bd5210SJason Evans 604a4bd5210SJason Evans bool 605a4bd5210SJason Evans ckh_pointer_keycomp(const void *k1, const void *k2) 606a4bd5210SJason Evans { 607a4bd5210SJason Evans 608a4bd5210SJason Evans return ((k1 == k2) ? true : false); 609a4bd5210SJason Evans } 610