16109fe07a14b7a619365977d9523db9f8b333792Jason Evans/* 26109fe07a14b7a619365977d9523db9f8b333792Jason Evans ******************************************************************************* 36109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Implementation of (2^1+,2) cuckoo hashing, where 2^1+ indicates that each 46109fe07a14b7a619365977d9523db9f8b333792Jason Evans * hash bucket contains 2^n cells, for n >= 1, and 2 indicates that two hash 56109fe07a14b7a619365977d9523db9f8b333792Jason Evans * functions are employed. The original cuckoo hashing algorithm was described 66109fe07a14b7a619365977d9523db9f8b333792Jason Evans * in: 76109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 86109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Pagh, R., F.F. Rodler (2004) Cuckoo Hashing. Journal of Algorithms 96109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 51(2):122-144. 106109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 116109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Generalization of cuckoo hashing was discussed in: 126109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 136109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Erlingsson, U., M. Manasse, F. McSherry (2006) A cool and practical 146109fe07a14b7a619365977d9523db9f8b333792Jason Evans * alternative to traditional hash tables. In Proceedings of the 7th 156109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Workshop on Distributed Data and Structures (WDAS'06), Santa Clara, CA, 166109fe07a14b7a619365977d9523db9f8b333792Jason Evans * January 2006. 176109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 186109fe07a14b7a619365977d9523db9f8b333792Jason Evans * This implementation uses precisely two hash functions because that is the 196109fe07a14b7a619365977d9523db9f8b333792Jason Evans * fewest that can work, and supporting multiple hashes is an implementation 206109fe07a14b7a619365977d9523db9f8b333792Jason Evans * burden. Here is a reproduction of Figure 1 from Erlingsson et al. (2006) 216109fe07a14b7a619365977d9523db9f8b333792Jason Evans * that shows approximate expected maximum load factors for various 226109fe07a14b7a619365977d9523db9f8b333792Jason Evans * configurations: 236109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 246109fe07a14b7a619365977d9523db9f8b333792Jason Evans * | #cells/bucket | 256109fe07a14b7a619365977d9523db9f8b333792Jason Evans * #hashes | 1 | 2 | 4 | 8 | 266109fe07a14b7a619365977d9523db9f8b333792Jason Evans * --------+-------+-------+-------+-------+ 276109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 1 | 0.006 | 0.006 | 0.03 | 0.12 | 286109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 2 | 0.49 | 0.86 |>0.93< |>0.96< | 296109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 3 | 0.91 | 0.97 | 0.98 | 0.999 | 306109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 4 | 0.97 | 0.99 | 0.999 | | 316109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 326109fe07a14b7a619365977d9523db9f8b333792Jason Evans * The number of cells per bucket is chosen such that a bucket fits in one cache 336109fe07a14b7a619365977d9523db9f8b333792Jason Evans * line. So, on 32- and 64-bit systems, we use (8,2) and (4,2) cuckoo hashing, 346109fe07a14b7a619365977d9523db9f8b333792Jason Evans * respectively. 356109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 366109fe07a14b7a619365977d9523db9f8b333792Jason Evans ******************************************************************************/ 370657f12acd43eb2082a71230341449eca648bc9bJason Evans#define JEMALLOC_CKH_C_ 38376b1529a383c39adf4674baf6db83a5e63f97acJason Evans#include "jemalloc/internal/jemalloc_internal.h" 396109fe07a14b7a619365977d9523db9f8b333792Jason Evans 406109fe07a14b7a619365977d9523db9f8b333792Jason Evans/******************************************************************************/ 416109fe07a14b7a619365977d9523db9f8b333792Jason Evans/* Function prototypes for non-inline static functions. */ 426109fe07a14b7a619365977d9523db9f8b333792Jason Evans 43962a2979e353f876f3725417179f201e671d9dbbJason Evansstatic bool ckh_grow(tsd_t *tsd, ckh_t *ckh); 44962a2979e353f876f3725417179f201e671d9dbbJason Evansstatic void ckh_shrink(tsd_t *tsd, ckh_t *ckh); 456109fe07a14b7a619365977d9523db9f8b333792Jason Evans 466109fe07a14b7a619365977d9523db9f8b333792Jason Evans/******************************************************************************/ 476109fe07a14b7a619365977d9523db9f8b333792Jason Evans 486109fe07a14b7a619365977d9523db9f8b333792Jason Evans/* 496109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Search bucket for key and return the cell number if found; SIZE_T_MAX 506109fe07a14b7a619365977d9523db9f8b333792Jason Evans * otherwise. 516109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 526edc97db15311fdac189798ec24e3eb39dc75d8eJason EvansJEMALLOC_INLINE_C size_t 536109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_bucket_search(ckh_t *ckh, size_t bucket, const void *key) 546109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 556109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckhc_t *cell; 566109fe07a14b7a619365977d9523db9f8b333792Jason Evans unsigned i; 576109fe07a14b7a619365977d9523db9f8b333792Jason Evans 586109fe07a14b7a619365977d9523db9f8b333792Jason Evans for (i = 0; i < (ZU(1) << LG_CKH_BUCKET_CELLS); i++) { 596109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; 606109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (cell->key != NULL && ckh->keycomp(key, cell->key)) 616109fe07a14b7a619365977d9523db9f8b333792Jason Evans return ((bucket << LG_CKH_BUCKET_CELLS) + i); 626109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 636109fe07a14b7a619365977d9523db9f8b333792Jason Evans 646109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (SIZE_T_MAX); 656109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 666109fe07a14b7a619365977d9523db9f8b333792Jason Evans 676109fe07a14b7a619365977d9523db9f8b333792Jason Evans/* 686109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Search table for key and return cell number if found; SIZE_T_MAX otherwise. 696109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 706edc97db15311fdac189798ec24e3eb39dc75d8eJason EvansJEMALLOC_INLINE_C size_t 716109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_isearch(ckh_t *ckh, const void *key) 726109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 73ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans size_t hashes[2], bucket, cell; 746109fe07a14b7a619365977d9523db9f8b333792Jason Evans 756109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh != NULL); 766109fe07a14b7a619365977d9523db9f8b333792Jason Evans 77ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans ckh->hash(key, hashes); 786109fe07a14b7a619365977d9523db9f8b333792Jason Evans 796109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Search primary bucket. */ 80ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1); 816109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell = ckh_bucket_search(ckh, bucket, key); 826109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (cell != SIZE_T_MAX) 836109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (cell); 846109fe07a14b7a619365977d9523db9f8b333792Jason Evans 856109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Search secondary bucket. */ 86ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); 876109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell = ckh_bucket_search(ckh, bucket, key); 886109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (cell); 896109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 906109fe07a14b7a619365977d9523db9f8b333792Jason Evans 916edc97db15311fdac189798ec24e3eb39dc75d8eJason EvansJEMALLOC_INLINE_C bool 926109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_try_bucket_insert(ckh_t *ckh, size_t bucket, const void *key, 936109fe07a14b7a619365977d9523db9f8b333792Jason Evans const void *data) 946109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 956109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckhc_t *cell; 966109fe07a14b7a619365977d9523db9f8b333792Jason Evans unsigned offset, i; 976109fe07a14b7a619365977d9523db9f8b333792Jason Evans 986109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 996109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Cycle through the cells in the bucket, starting at a random position. 1006109fe07a14b7a619365977d9523db9f8b333792Jason Evans * The randomness avoids worst-case search overhead as buckets fill up. 1016109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 1025d6cb6eb66b05261cccd2b416f50ad98d1735229Jason Evans offset = (unsigned)prng_lg_range_u64(&ckh->prng_state, 1035d6cb6eb66b05261cccd2b416f50ad98d1735229Jason Evans LG_CKH_BUCKET_CELLS); 1046109fe07a14b7a619365977d9523db9f8b333792Jason Evans for (i = 0; i < (ZU(1) << LG_CKH_BUCKET_CELLS); i++) { 1056109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + 1066109fe07a14b7a619365977d9523db9f8b333792Jason Evans ((i + offset) & ((ZU(1) << LG_CKH_BUCKET_CELLS) - 1))]; 1076109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (cell->key == NULL) { 1086109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell->key = key; 1096109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell->data = data; 1106109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->count++; 1116109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 1126109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 1136109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 1146109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1156109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (true); 1166109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 1176109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1186109fe07a14b7a619365977d9523db9f8b333792Jason Evans/* 1196109fe07a14b7a619365977d9523db9f8b333792Jason Evans * No space is available in bucket. Randomly evict an item, then try to find an 1206109fe07a14b7a619365977d9523db9f8b333792Jason Evans * alternate location for that item. Iteratively repeat this 1216109fe07a14b7a619365977d9523db9f8b333792Jason Evans * eviction/relocation procedure until either success or detection of an 1226109fe07a14b7a619365977d9523db9f8b333792Jason Evans * eviction/relocation bucket cycle. 1236109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 1246edc97db15311fdac189798ec24e3eb39dc75d8eJason EvansJEMALLOC_INLINE_C bool 1256109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_evict_reloc_insert(ckh_t *ckh, size_t argbucket, void const **argkey, 1266109fe07a14b7a619365977d9523db9f8b333792Jason Evans void const **argdata) 1276109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 1286109fe07a14b7a619365977d9523db9f8b333792Jason Evans const void *key, *data, *tkey, *tdata; 1296109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckhc_t *cell; 130ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans size_t hashes[2], bucket, tbucket; 1316109fe07a14b7a619365977d9523db9f8b333792Jason Evans unsigned i; 1326109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1336109fe07a14b7a619365977d9523db9f8b333792Jason Evans bucket = argbucket; 1346109fe07a14b7a619365977d9523db9f8b333792Jason Evans key = *argkey; 1356109fe07a14b7a619365977d9523db9f8b333792Jason Evans data = *argdata; 1366109fe07a14b7a619365977d9523db9f8b333792Jason Evans while (true) { 1376109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 1386109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Choose a random item within the bucket to evict. This is 1396109fe07a14b7a619365977d9523db9f8b333792Jason Evans * critical to correct function, because without (eventually) 1406109fe07a14b7a619365977d9523db9f8b333792Jason Evans * evicting all items within a bucket during iteration, it 1416109fe07a14b7a619365977d9523db9f8b333792Jason Evans * would be possible to get stuck in an infinite loop if there 1426109fe07a14b7a619365977d9523db9f8b333792Jason Evans * were an item for which both hashes indicated the same 1436109fe07a14b7a619365977d9523db9f8b333792Jason Evans * bucket. 1446109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 1455d6cb6eb66b05261cccd2b416f50ad98d1735229Jason Evans i = (unsigned)prng_lg_range_u64(&ckh->prng_state, 1469e1810ca9dc4a5f5f0841b9a6c1abb4337753552Jason Evans LG_CKH_BUCKET_CELLS); 1476109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; 1486109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(cell->key != NULL); 1496109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1506109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Swap cell->{key,data} and {key,data} (evict). */ 1516109fe07a14b7a619365977d9523db9f8b333792Jason Evans tkey = cell->key; tdata = cell->data; 1526109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell->key = key; cell->data = data; 1536109fe07a14b7a619365977d9523db9f8b333792Jason Evans key = tkey; data = tdata; 1546109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1556109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_COUNT 1566109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->nrelocs++; 1576109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 1586109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1596109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Find the alternate bucket for the evicted item. */ 160ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans ckh->hash(key, hashes); 161ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans tbucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); 1626109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (tbucket == bucket) { 163ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans tbucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) 164ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans - 1); 1656109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 1666109fe07a14b7a619365977d9523db9f8b333792Jason Evans * It may be that (tbucket == bucket) still, if the 1676109fe07a14b7a619365977d9523db9f8b333792Jason Evans * item's hashes both indicate this bucket. However, 1686109fe07a14b7a619365977d9523db9f8b333792Jason Evans * we are guaranteed to eventually escape this bucket 1696109fe07a14b7a619365977d9523db9f8b333792Jason Evans * during iteration, assuming pseudo-random item 1706109fe07a14b7a619365977d9523db9f8b333792Jason Evans * selection (true randomness would make infinite 1716109fe07a14b7a619365977d9523db9f8b333792Jason Evans * looping a remote possibility). The reason we can 1726109fe07a14b7a619365977d9523db9f8b333792Jason Evans * never get trapped forever is that there are two 1736109fe07a14b7a619365977d9523db9f8b333792Jason Evans * cases: 1746109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 1756109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 1) This bucket == argbucket, so we will quickly 1766109fe07a14b7a619365977d9523db9f8b333792Jason Evans * detect an eviction cycle and terminate. 1776109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 2) An item was evicted to this bucket from another, 1786109fe07a14b7a619365977d9523db9f8b333792Jason Evans * which means that at least one item in this bucket 1796109fe07a14b7a619365977d9523db9f8b333792Jason Evans * has hashes that indicate distinct buckets. 1806109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 1816109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 1826109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Check for a cycle. */ 1836109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (tbucket == argbucket) { 1846109fe07a14b7a619365977d9523db9f8b333792Jason Evans *argkey = key; 1856109fe07a14b7a619365977d9523db9f8b333792Jason Evans *argdata = data; 1866109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (true); 1876109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 1886109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1896109fe07a14b7a619365977d9523db9f8b333792Jason Evans bucket = tbucket; 190551ebc43647521bdd0bc78558b106762b3388928Jason Evans if (!ckh_try_bucket_insert(ckh, bucket, key, data)) 1916109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 1926109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 1936109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 1946109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1956edc97db15311fdac189798ec24e3eb39dc75d8eJason EvansJEMALLOC_INLINE_C bool 1966109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_try_insert(ckh_t *ckh, void const**argkey, void const**argdata) 1976109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 198ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans size_t hashes[2], bucket; 1996109fe07a14b7a619365977d9523db9f8b333792Jason Evans const void *key = *argkey; 2006109fe07a14b7a619365977d9523db9f8b333792Jason Evans const void *data = *argdata; 2016109fe07a14b7a619365977d9523db9f8b333792Jason Evans 202ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans ckh->hash(key, hashes); 2036109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2046109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Try to insert in primary bucket. */ 205ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1); 206551ebc43647521bdd0bc78558b106762b3388928Jason Evans if (!ckh_try_bucket_insert(ckh, bucket, key, data)) 2076109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 2086109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2096109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Try to insert in secondary bucket. */ 210ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); 211551ebc43647521bdd0bc78558b106762b3388928Jason Evans if (!ckh_try_bucket_insert(ckh, bucket, key, data)) 2126109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 2136109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2146109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 2156109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Try to find a place for this item via iterative eviction/relocation. 2166109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 2176109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (ckh_evict_reloc_insert(ckh, bucket, argkey, argdata)); 2186109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 2196109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2206109fe07a14b7a619365977d9523db9f8b333792Jason Evans/* 2216109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Try to rebuild the hash table from scratch by inserting all items from the 2226109fe07a14b7a619365977d9523db9f8b333792Jason Evans * old table into the new. 2236109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 2246edc97db15311fdac189798ec24e3eb39dc75d8eJason EvansJEMALLOC_INLINE_C bool 2256109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_rebuild(ckh_t *ckh, ckhc_t *aTab) 2266109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 2276109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t count, i, nins; 2286109fe07a14b7a619365977d9523db9f8b333792Jason Evans const void *key, *data; 2296109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2306109fe07a14b7a619365977d9523db9f8b333792Jason Evans count = ckh->count; 2316109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->count = 0; 2326109fe07a14b7a619365977d9523db9f8b333792Jason Evans for (i = nins = 0; nins < count; i++) { 2336109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (aTab[i].key != NULL) { 2346109fe07a14b7a619365977d9523db9f8b333792Jason Evans key = aTab[i].key; 2356109fe07a14b7a619365977d9523db9f8b333792Jason Evans data = aTab[i].data; 2366109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh_try_insert(ckh, &key, &data)) { 2376109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->count = count; 2386109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (true); 2396109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 2406109fe07a14b7a619365977d9523db9f8b333792Jason Evans nins++; 2416109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 2426109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 2436109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2446109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 2456109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 2466109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2476109fe07a14b7a619365977d9523db9f8b333792Jason Evansstatic bool 248962a2979e353f876f3725417179f201e671d9dbbJason Evansckh_grow(tsd_t *tsd, ckh_t *ckh) 2496109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 2506109fe07a14b7a619365977d9523db9f8b333792Jason Evans bool ret; 2516109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckhc_t *tab, *ttab; 2529e1810ca9dc4a5f5f0841b9a6c1abb4337753552Jason Evans unsigned lg_prevbuckets, lg_curcells; 2536109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2546109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_COUNT 2556109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->ngrows++; 2566109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 2576109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2586109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 2596109fe07a14b7a619365977d9523db9f8b333792Jason Evans * It is possible (though unlikely, given well behaved hashes) that the 2606109fe07a14b7a619365977d9523db9f8b333792Jason Evans * table will have to be doubled more than once in order to create a 2616109fe07a14b7a619365977d9523db9f8b333792Jason Evans * usable table. 2626109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 2636109fe07a14b7a619365977d9523db9f8b333792Jason Evans lg_prevbuckets = ckh->lg_curbuckets; 2646109fe07a14b7a619365977d9523db9f8b333792Jason Evans lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS; 2656109fe07a14b7a619365977d9523db9f8b333792Jason Evans while (true) { 26638d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans size_t usize; 26738d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans 2686109fe07a14b7a619365977d9523db9f8b333792Jason Evans lg_curcells++; 2695ff709c264e52651de25b788692c62ff1f6f389cJason Evans usize = sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE); 2700c516a00c4cb28cff55ce0995f756b5aae074c9eJason Evans if (unlikely(usize == 0 || usize > HUGE_MAXCLASS)) { 27138d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans ret = true; 272a1ee7838e14b321a97bfacb1f1cf5004198f2203Jason Evans goto label_return; 27338d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans } 274962a2979e353f876f3725417179f201e671d9dbbJason Evans tab = (ckhc_t *)ipallocztm(tsd_tsdn(tsd), usize, CACHELINE, 275962a2979e353f876f3725417179f201e671d9dbbJason Evans true, NULL, true, arena_ichoose(tsd, NULL)); 2766109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (tab == NULL) { 2776109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret = true; 278a1ee7838e14b321a97bfacb1f1cf5004198f2203Jason Evans goto label_return; 2796109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 2806109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Swap in new table. */ 2816109fe07a14b7a619365977d9523db9f8b333792Jason Evans ttab = ckh->tab; 2826109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->tab = tab; 2836109fe07a14b7a619365977d9523db9f8b333792Jason Evans tab = ttab; 2846109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; 2856109fe07a14b7a619365977d9523db9f8b333792Jason Evans 286551ebc43647521bdd0bc78558b106762b3388928Jason Evans if (!ckh_rebuild(ckh, tab)) { 287962a2979e353f876f3725417179f201e671d9dbbJason Evans idalloctm(tsd_tsdn(tsd), tab, NULL, true, true); 2886109fe07a14b7a619365977d9523db9f8b333792Jason Evans break; 2896109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 2906109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2916109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Rebuilding failed, so back out partially rebuilt table. */ 292962a2979e353f876f3725417179f201e671d9dbbJason Evans idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, true, true); 2936109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->tab = tab; 2946109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->lg_curbuckets = lg_prevbuckets; 2956109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 2966109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2976109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret = false; 298a1ee7838e14b321a97bfacb1f1cf5004198f2203Jason Evanslabel_return: 2996109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (ret); 3006109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 3016109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3026109fe07a14b7a619365977d9523db9f8b333792Jason Evansstatic void 303962a2979e353f876f3725417179f201e671d9dbbJason Evansckh_shrink(tsd_t *tsd, ckh_t *ckh) 3046109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 3056109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckhc_t *tab, *ttab; 3069e1810ca9dc4a5f5f0841b9a6c1abb4337753552Jason Evans size_t usize; 3079e1810ca9dc4a5f5f0841b9a6c1abb4337753552Jason Evans unsigned lg_prevbuckets, lg_curcells; 3086109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3096109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 3106109fe07a14b7a619365977d9523db9f8b333792Jason Evans * It is possible (though unlikely, given well behaved hashes) that the 3116109fe07a14b7a619365977d9523db9f8b333792Jason Evans * table rebuild will fail. 3126109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 3136109fe07a14b7a619365977d9523db9f8b333792Jason Evans lg_prevbuckets = ckh->lg_curbuckets; 3146109fe07a14b7a619365977d9523db9f8b333792Jason Evans lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS - 1; 3155ff709c264e52651de25b788692c62ff1f6f389cJason Evans usize = sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE); 3160c516a00c4cb28cff55ce0995f756b5aae074c9eJason Evans if (unlikely(usize == 0 || usize > HUGE_MAXCLASS)) 31738d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans return; 318962a2979e353f876f3725417179f201e671d9dbbJason Evans tab = (ckhc_t *)ipallocztm(tsd_tsdn(tsd), usize, CACHELINE, true, NULL, 319962a2979e353f876f3725417179f201e671d9dbbJason Evans true, arena_ichoose(tsd, NULL)); 3206109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (tab == NULL) { 3216109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 3226109fe07a14b7a619365977d9523db9f8b333792Jason Evans * An OOM error isn't worth propagating, since it doesn't 3236109fe07a14b7a619365977d9523db9f8b333792Jason Evans * prevent this or future operations from proceeding. 3246109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 3256109fe07a14b7a619365977d9523db9f8b333792Jason Evans return; 3266109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 3276109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Swap in new table. */ 3286109fe07a14b7a619365977d9523db9f8b333792Jason Evans ttab = ckh->tab; 3296109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->tab = tab; 3306109fe07a14b7a619365977d9523db9f8b333792Jason Evans tab = ttab; 3316109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; 3326109fe07a14b7a619365977d9523db9f8b333792Jason Evans 333551ebc43647521bdd0bc78558b106762b3388928Jason Evans if (!ckh_rebuild(ckh, tab)) { 334962a2979e353f876f3725417179f201e671d9dbbJason Evans idalloctm(tsd_tsdn(tsd), tab, NULL, true, true); 3356109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_COUNT 3366109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->nshrinks++; 3376109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 3386109fe07a14b7a619365977d9523db9f8b333792Jason Evans return; 3396109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 3406109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3416109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Rebuilding failed, so back out partially rebuilt table. */ 342962a2979e353f876f3725417179f201e671d9dbbJason Evans idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, true, true); 3436109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->tab = tab; 3446109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->lg_curbuckets = lg_prevbuckets; 3456109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_COUNT 3466109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->nshrinkfails++; 3476109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 3486109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 3496109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3506109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 351962a2979e353f876f3725417179f201e671d9dbbJason Evansckh_new(tsd_t *tsd, ckh_t *ckh, size_t minitems, ckh_hash_t *hash, 3525460aa6f6676c7f253bfcb75c028dfd38cae8aafJason Evans ckh_keycomp_t *keycomp) 3536109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 3546109fe07a14b7a619365977d9523db9f8b333792Jason Evans bool ret; 35538d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans size_t mincells, usize; 3566109fe07a14b7a619365977d9523db9f8b333792Jason Evans unsigned lg_mincells; 3576109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3586109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(minitems > 0); 3596109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(hash != NULL); 3606109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(keycomp != NULL); 3616109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3626109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_COUNT 3636109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->ngrows = 0; 3646109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->nshrinks = 0; 3656109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->nshrinkfails = 0; 3666109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->ninserts = 0; 3676109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->nrelocs = 0; 3686109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 36984f7cdb0c588322dfd50a26497fc1cb54b792018Jason Evans ckh->prng_state = 42; /* Value doesn't really matter. */ 3706109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->count = 0; 3716109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3726109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 373e12eaf93dca308a426c182956197b0eeb5f2cff3Jason Evans * Find the minimum power of 2 that is large enough to fit minitems 3746109fe07a14b7a619365977d9523db9f8b333792Jason Evans * entries. We are using (2+,2) cuckoo hashing, which has an expected 3756109fe07a14b7a619365977d9523db9f8b333792Jason Evans * maximum load factor of at least ~0.86, so 0.75 is a conservative load 376e12eaf93dca308a426c182956197b0eeb5f2cff3Jason Evans * factor that will typically allow mincells items to fit without ever 3776109fe07a14b7a619365977d9523db9f8b333792Jason Evans * growing the table. 3786109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 3796109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(LG_CKH_BUCKET_CELLS > 0); 3806109fe07a14b7a619365977d9523db9f8b333792Jason Evans mincells = ((minitems + (3 - (minitems % 3))) / 3) << 2; 3816109fe07a14b7a619365977d9523db9f8b333792Jason Evans for (lg_mincells = LG_CKH_BUCKET_CELLS; 3826109fe07a14b7a619365977d9523db9f8b333792Jason Evans (ZU(1) << lg_mincells) < mincells; 3836109fe07a14b7a619365977d9523db9f8b333792Jason Evans lg_mincells++) 3846109fe07a14b7a619365977d9523db9f8b333792Jason Evans ; /* Do nothing. */ 3856109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->lg_minbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; 3866109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->lg_curbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; 3876109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->hash = hash; 3886109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->keycomp = keycomp; 3896109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3905ff709c264e52651de25b788692c62ff1f6f389cJason Evans usize = sa2u(sizeof(ckhc_t) << lg_mincells, CACHELINE); 3910c516a00c4cb28cff55ce0995f756b5aae074c9eJason Evans if (unlikely(usize == 0 || usize > HUGE_MAXCLASS)) { 39238d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans ret = true; 393a1ee7838e14b321a97bfacb1f1cf5004198f2203Jason Evans goto label_return; 39438d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans } 395962a2979e353f876f3725417179f201e671d9dbbJason Evans ckh->tab = (ckhc_t *)ipallocztm(tsd_tsdn(tsd), usize, CACHELINE, true, 396962a2979e353f876f3725417179f201e671d9dbbJason Evans NULL, true, arena_ichoose(tsd, NULL)); 3976109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh->tab == NULL) { 3986109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret = true; 399a1ee7838e14b321a97bfacb1f1cf5004198f2203Jason Evans goto label_return; 4006109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 4016109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4026109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret = false; 403a1ee7838e14b321a97bfacb1f1cf5004198f2203Jason Evanslabel_return: 4046109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (ret); 4056109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 4066109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4076109fe07a14b7a619365977d9523db9f8b333792Jason Evansvoid 408962a2979e353f876f3725417179f201e671d9dbbJason Evansckh_delete(tsd_t *tsd, ckh_t *ckh) 4096109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 4106109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4116109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh != NULL); 4126109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4136109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_VERBOSE 4146109fe07a14b7a619365977d9523db9f8b333792Jason Evans malloc_printf( 4155fae7dc1b316d0e93aa20cc3aaf050f509aec705Jason Evans "%s(%p): ngrows: %"FMTu64", nshrinks: %"FMTu64"," 4165fae7dc1b316d0e93aa20cc3aaf050f509aec705Jason Evans " nshrinkfails: %"FMTu64", ninserts: %"FMTu64"," 4175fae7dc1b316d0e93aa20cc3aaf050f509aec705Jason Evans " nrelocs: %"FMTu64"\n", __func__, ckh, 4186109fe07a14b7a619365977d9523db9f8b333792Jason Evans (unsigned long long)ckh->ngrows, 4196109fe07a14b7a619365977d9523db9f8b333792Jason Evans (unsigned long long)ckh->nshrinks, 4206109fe07a14b7a619365977d9523db9f8b333792Jason Evans (unsigned long long)ckh->nshrinkfails, 4216109fe07a14b7a619365977d9523db9f8b333792Jason Evans (unsigned long long)ckh->ninserts, 4226109fe07a14b7a619365977d9523db9f8b333792Jason Evans (unsigned long long)ckh->nrelocs); 4236109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 4246109fe07a14b7a619365977d9523db9f8b333792Jason Evans 425962a2979e353f876f3725417179f201e671d9dbbJason Evans idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, true, true); 426ba175a2bfb236d79404012d9b5bb6e9b3c8be8ddJason Evans if (config_debug) 427a82070ef5fc3aa81fda43086cdcc22bfa826b894Chris Peterson memset(ckh, JEMALLOC_FREE_JUNK, sizeof(ckh_t)); 4286109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 4296109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4306109fe07a14b7a619365977d9523db9f8b333792Jason Evanssize_t 4316109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_count(ckh_t *ckh) 4326109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 4336109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4346109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh != NULL); 4356109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4366109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (ckh->count); 4376109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 4386109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4396109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 4406109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data) 4416109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 4426109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t i, ncells; 4436109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4446109fe07a14b7a619365977d9523db9f8b333792Jason Evans for (i = *tabind, ncells = (ZU(1) << (ckh->lg_curbuckets + 4456109fe07a14b7a619365977d9523db9f8b333792Jason Evans LG_CKH_BUCKET_CELLS)); i < ncells; i++) { 4466109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh->tab[i].key != NULL) { 4476109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (key != NULL) 4486109fe07a14b7a619365977d9523db9f8b333792Jason Evans *key = (void *)ckh->tab[i].key; 4496109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (data != NULL) 4506109fe07a14b7a619365977d9523db9f8b333792Jason Evans *data = (void *)ckh->tab[i].data; 4516109fe07a14b7a619365977d9523db9f8b333792Jason Evans *tabind = i + 1; 4526109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 4536109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 4546109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 4556109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4566109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (true); 4576109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 4586109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4596109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 460962a2979e353f876f3725417179f201e671d9dbbJason Evansckh_insert(tsd_t *tsd, ckh_t *ckh, const void *key, const void *data) 4616109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 4626109fe07a14b7a619365977d9523db9f8b333792Jason Evans bool ret; 4636109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4646109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh != NULL); 4656109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh_search(ckh, key, NULL, NULL)); 4666109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4676109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_COUNT 4686109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->ninserts++; 4696109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 4706109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4716109fe07a14b7a619365977d9523db9f8b333792Jason Evans while (ckh_try_insert(ckh, &key, &data)) { 472962a2979e353f876f3725417179f201e671d9dbbJason Evans if (ckh_grow(tsd, ckh)) { 4736109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret = true; 474a1ee7838e14b321a97bfacb1f1cf5004198f2203Jason Evans goto label_return; 4756109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 4766109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 4776109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4786109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret = false; 479a1ee7838e14b321a97bfacb1f1cf5004198f2203Jason Evanslabel_return: 4806109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (ret); 4816109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 4826109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4836109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 484962a2979e353f876f3725417179f201e671d9dbbJason Evansckh_remove(tsd_t *tsd, ckh_t *ckh, const void *searchkey, void **key, 4855460aa6f6676c7f253bfcb75c028dfd38cae8aafJason Evans void **data) 4866109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 4876109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t cell; 4886109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4896109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh != NULL); 4906109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4916109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell = ckh_isearch(ckh, searchkey); 4926109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (cell != SIZE_T_MAX) { 4936109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (key != NULL) 4946109fe07a14b7a619365977d9523db9f8b333792Jason Evans *key = (void *)ckh->tab[cell].key; 4956109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (data != NULL) 4966109fe07a14b7a619365977d9523db9f8b333792Jason Evans *data = (void *)ckh->tab[cell].data; 4976109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->tab[cell].key = NULL; 4986109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->tab[cell].data = NULL; /* Not necessary. */ 4996109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5006109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->count--; 5016109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Try to halve the table if it is less than 1/4 full. */ 5026109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh->count < (ZU(1) << (ckh->lg_curbuckets 5036109fe07a14b7a619365977d9523db9f8b333792Jason Evans + LG_CKH_BUCKET_CELLS - 2)) && ckh->lg_curbuckets 5046109fe07a14b7a619365977d9523db9f8b333792Jason Evans > ckh->lg_minbuckets) { 5056109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Ignore error due to OOM. */ 506962a2979e353f876f3725417179f201e671d9dbbJason Evans ckh_shrink(tsd, ckh); 5076109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 5086109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5096109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 5106109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 5116109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5126109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (true); 5136109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 5146109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5156109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 5166109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data) 5176109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 5186109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t cell; 5196109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5206109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh != NULL); 5216109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5226109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell = ckh_isearch(ckh, searchkey); 5236109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (cell != SIZE_T_MAX) { 5246109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (key != NULL) 5256109fe07a14b7a619365977d9523db9f8b333792Jason Evans *key = (void *)ckh->tab[cell].key; 5266109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (data != NULL) 5276109fe07a14b7a619365977d9523db9f8b333792Jason Evans *data = (void *)ckh->tab[cell].data; 5286109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 5296109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 5306109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5316109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (true); 5326109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 5336109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5346109fe07a14b7a619365977d9523db9f8b333792Jason Evansvoid 535ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evansckh_string_hash(const void *key, size_t r_hash[2]) 5366109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 5376109fe07a14b7a619365977d9523db9f8b333792Jason Evans 538ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans hash(key, strlen((const char *)key), 0x94122f33U, r_hash); 5396109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 5406109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5416109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 5426109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_string_keycomp(const void *k1, const void *k2) 5436109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 5446109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5456109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(k1 != NULL); 5466109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(k2 != NULL); 5476109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5486109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (strcmp((char *)k1, (char *)k2) ? false : true); 5496109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 5506109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5516109fe07a14b7a619365977d9523db9f8b333792Jason Evansvoid 552ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evansckh_pointer_hash(const void *key, size_t r_hash[2]) 5536109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 554355b438c854227bbf8185cb7a3ce247d271a842eJason Evans union { 555355b438c854227bbf8185cb7a3ce247d271a842eJason Evans const void *v; 556ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans size_t i; 557355b438c854227bbf8185cb7a3ce247d271a842eJason Evans } u; 5586109fe07a14b7a619365977d9523db9f8b333792Jason Evans 559355b438c854227bbf8185cb7a3ce247d271a842eJason Evans assert(sizeof(u.v) == sizeof(u.i)); 560355b438c854227bbf8185cb7a3ce247d271a842eJason Evans u.v = key; 561ae03bf6a57f0dd6a009288fa6477a300cabf6d5eJason Evans hash(&u.i, sizeof(u.i), 0xd983396eU, r_hash); 5626109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 5636109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5646109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 5656109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_pointer_keycomp(const void *k1, const void *k2) 5666109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 5676109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5686109fe07a14b7a619365977d9523db9f8b333792Jason Evans return ((k1 == k2) ? true : false); 5696109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 570