ckh.c revision a1ee7838e14b321a97bfacb1f1cf5004198f2203
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 436109fe07a14b7a619365977d9523db9f8b333792Jason Evansstatic bool ckh_grow(ckh_t *ckh); 446109fe07a14b7a619365977d9523db9f8b333792Jason Evansstatic void ckh_shrink(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 */ 526109fe07a14b7a619365977d9523db9f8b333792Jason EvansJEMALLOC_INLINE 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 */ 706109fe07a14b7a619365977d9523db9f8b333792Jason EvansJEMALLOC_INLINE size_t 716109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_isearch(ckh_t *ckh, const void *key) 726109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 736109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t hash1, hash2, bucket, cell; 746109fe07a14b7a619365977d9523db9f8b333792Jason Evans 756109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh != NULL); 766109fe07a14b7a619365977d9523db9f8b333792Jason Evans 776109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->hash(key, ckh->lg_curbuckets, &hash1, &hash2); 786109fe07a14b7a619365977d9523db9f8b333792Jason Evans 796109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Search primary bucket. */ 806109fe07a14b7a619365977d9523db9f8b333792Jason Evans bucket = hash1 & ((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. */ 866109fe07a14b7a619365977d9523db9f8b333792Jason Evans bucket = hash2 & ((ZU(1) << ckh->lg_curbuckets) - 1); 876109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell = ckh_bucket_search(ckh, bucket, key); 886109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (cell); 896109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 906109fe07a14b7a619365977d9523db9f8b333792Jason Evans 916109fe07a14b7a619365977d9523db9f8b333792Jason EvansJEMALLOC_INLINE 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 */ 10284f7cdb0c588322dfd50a26497fc1cb54b792018Jason Evans prng32(offset, LG_CKH_BUCKET_CELLS, ckh->prng_state, CKH_A, CKH_C); 1036109fe07a14b7a619365977d9523db9f8b333792Jason Evans for (i = 0; i < (ZU(1) << LG_CKH_BUCKET_CELLS); i++) { 1046109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + 1056109fe07a14b7a619365977d9523db9f8b333792Jason Evans ((i + offset) & ((ZU(1) << LG_CKH_BUCKET_CELLS) - 1))]; 1066109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (cell->key == NULL) { 1076109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell->key = key; 1086109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell->data = data; 1096109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->count++; 1106109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 1116109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 1126109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 1136109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1146109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (true); 1156109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 1166109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1176109fe07a14b7a619365977d9523db9f8b333792Jason Evans/* 1186109fe07a14b7a619365977d9523db9f8b333792Jason Evans * No space is available in bucket. Randomly evict an item, then try to find an 1196109fe07a14b7a619365977d9523db9f8b333792Jason Evans * alternate location for that item. Iteratively repeat this 1206109fe07a14b7a619365977d9523db9f8b333792Jason Evans * eviction/relocation procedure until either success or detection of an 1216109fe07a14b7a619365977d9523db9f8b333792Jason Evans * eviction/relocation bucket cycle. 1226109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 1236109fe07a14b7a619365977d9523db9f8b333792Jason EvansJEMALLOC_INLINE bool 1246109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_evict_reloc_insert(ckh_t *ckh, size_t argbucket, void const **argkey, 1256109fe07a14b7a619365977d9523db9f8b333792Jason Evans void const **argdata) 1266109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 1276109fe07a14b7a619365977d9523db9f8b333792Jason Evans const void *key, *data, *tkey, *tdata; 1286109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckhc_t *cell; 1296109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t hash1, hash2, bucket, tbucket; 1306109fe07a14b7a619365977d9523db9f8b333792Jason Evans unsigned i; 1316109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1326109fe07a14b7a619365977d9523db9f8b333792Jason Evans bucket = argbucket; 1336109fe07a14b7a619365977d9523db9f8b333792Jason Evans key = *argkey; 1346109fe07a14b7a619365977d9523db9f8b333792Jason Evans data = *argdata; 1356109fe07a14b7a619365977d9523db9f8b333792Jason Evans while (true) { 1366109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 1376109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Choose a random item within the bucket to evict. This is 1386109fe07a14b7a619365977d9523db9f8b333792Jason Evans * critical to correct function, because without (eventually) 1396109fe07a14b7a619365977d9523db9f8b333792Jason Evans * evicting all items within a bucket during iteration, it 1406109fe07a14b7a619365977d9523db9f8b333792Jason Evans * would be possible to get stuck in an infinite loop if there 1416109fe07a14b7a619365977d9523db9f8b333792Jason Evans * were an item for which both hashes indicated the same 1426109fe07a14b7a619365977d9523db9f8b333792Jason Evans * bucket. 1436109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 14484f7cdb0c588322dfd50a26497fc1cb54b792018Jason Evans prng32(i, LG_CKH_BUCKET_CELLS, ckh->prng_state, CKH_A, CKH_C); 1456109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; 1466109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(cell->key != NULL); 1476109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1486109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Swap cell->{key,data} and {key,data} (evict). */ 1496109fe07a14b7a619365977d9523db9f8b333792Jason Evans tkey = cell->key; tdata = cell->data; 1506109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell->key = key; cell->data = data; 1516109fe07a14b7a619365977d9523db9f8b333792Jason Evans key = tkey; data = tdata; 1526109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1536109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_COUNT 1546109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->nrelocs++; 1556109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 1566109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1576109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Find the alternate bucket for the evicted item. */ 1586109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->hash(key, ckh->lg_curbuckets, &hash1, &hash2); 1596109fe07a14b7a619365977d9523db9f8b333792Jason Evans tbucket = hash2 & ((ZU(1) << ckh->lg_curbuckets) - 1); 1606109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (tbucket == bucket) { 1616109fe07a14b7a619365977d9523db9f8b333792Jason Evans tbucket = hash1 & ((ZU(1) << ckh->lg_curbuckets) - 1); 1626109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 1636109fe07a14b7a619365977d9523db9f8b333792Jason Evans * It may be that (tbucket == bucket) still, if the 1646109fe07a14b7a619365977d9523db9f8b333792Jason Evans * item's hashes both indicate this bucket. However, 1656109fe07a14b7a619365977d9523db9f8b333792Jason Evans * we are guaranteed to eventually escape this bucket 1666109fe07a14b7a619365977d9523db9f8b333792Jason Evans * during iteration, assuming pseudo-random item 1676109fe07a14b7a619365977d9523db9f8b333792Jason Evans * selection (true randomness would make infinite 1686109fe07a14b7a619365977d9523db9f8b333792Jason Evans * looping a remote possibility). The reason we can 1696109fe07a14b7a619365977d9523db9f8b333792Jason Evans * never get trapped forever is that there are two 1706109fe07a14b7a619365977d9523db9f8b333792Jason Evans * cases: 1716109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 1726109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 1) This bucket == argbucket, so we will quickly 1736109fe07a14b7a619365977d9523db9f8b333792Jason Evans * detect an eviction cycle and terminate. 1746109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 2) An item was evicted to this bucket from another, 1756109fe07a14b7a619365977d9523db9f8b333792Jason Evans * which means that at least one item in this bucket 1766109fe07a14b7a619365977d9523db9f8b333792Jason Evans * has hashes that indicate distinct buckets. 1776109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 1786109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 1796109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Check for a cycle. */ 1806109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (tbucket == argbucket) { 1816109fe07a14b7a619365977d9523db9f8b333792Jason Evans *argkey = key; 1826109fe07a14b7a619365977d9523db9f8b333792Jason Evans *argdata = data; 1836109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (true); 1846109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 1856109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1866109fe07a14b7a619365977d9523db9f8b333792Jason Evans bucket = tbucket; 1876109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh_try_bucket_insert(ckh, bucket, key, data) == false) 1886109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 1896109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 1906109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 1916109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1926109fe07a14b7a619365977d9523db9f8b333792Jason EvansJEMALLOC_INLINE bool 1936109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_try_insert(ckh_t *ckh, void const**argkey, void const**argdata) 1946109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 1956109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t hash1, hash2, bucket; 1966109fe07a14b7a619365977d9523db9f8b333792Jason Evans const void *key = *argkey; 1976109fe07a14b7a619365977d9523db9f8b333792Jason Evans const void *data = *argdata; 1986109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1996109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->hash(key, ckh->lg_curbuckets, &hash1, &hash2); 2006109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2016109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Try to insert in primary bucket. */ 2026109fe07a14b7a619365977d9523db9f8b333792Jason Evans bucket = hash1 & ((ZU(1) << ckh->lg_curbuckets) - 1); 2036109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh_try_bucket_insert(ckh, bucket, key, data) == false) 2046109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 2056109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2066109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Try to insert in secondary bucket. */ 2076109fe07a14b7a619365977d9523db9f8b333792Jason Evans bucket = hash2 & ((ZU(1) << ckh->lg_curbuckets) - 1); 2086109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh_try_bucket_insert(ckh, bucket, key, data) == false) 2096109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 2106109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2116109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 2126109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Try to find a place for this item via iterative eviction/relocation. 2136109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 2146109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (ckh_evict_reloc_insert(ckh, bucket, argkey, argdata)); 2156109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 2166109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2176109fe07a14b7a619365977d9523db9f8b333792Jason Evans/* 2186109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Try to rebuild the hash table from scratch by inserting all items from the 2196109fe07a14b7a619365977d9523db9f8b333792Jason Evans * old table into the new. 2206109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 2216109fe07a14b7a619365977d9523db9f8b333792Jason EvansJEMALLOC_INLINE bool 2226109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_rebuild(ckh_t *ckh, ckhc_t *aTab) 2236109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 2246109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t count, i, nins; 2256109fe07a14b7a619365977d9523db9f8b333792Jason Evans const void *key, *data; 2266109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2276109fe07a14b7a619365977d9523db9f8b333792Jason Evans count = ckh->count; 2286109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->count = 0; 2296109fe07a14b7a619365977d9523db9f8b333792Jason Evans for (i = nins = 0; nins < count; i++) { 2306109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (aTab[i].key != NULL) { 2316109fe07a14b7a619365977d9523db9f8b333792Jason Evans key = aTab[i].key; 2326109fe07a14b7a619365977d9523db9f8b333792Jason Evans data = aTab[i].data; 2336109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh_try_insert(ckh, &key, &data)) { 2346109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->count = count; 2356109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (true); 2366109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 2376109fe07a14b7a619365977d9523db9f8b333792Jason Evans nins++; 2386109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 2396109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 2406109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2416109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 2426109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 2436109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2446109fe07a14b7a619365977d9523db9f8b333792Jason Evansstatic bool 2456109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_grow(ckh_t *ckh) 2466109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 2476109fe07a14b7a619365977d9523db9f8b333792Jason Evans bool ret; 2486109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckhc_t *tab, *ttab; 2496109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t lg_curcells; 2506109fe07a14b7a619365977d9523db9f8b333792Jason Evans unsigned lg_prevbuckets; 2516109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2526109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_COUNT 2536109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->ngrows++; 2546109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 2556109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2566109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 2576109fe07a14b7a619365977d9523db9f8b333792Jason Evans * It is possible (though unlikely, given well behaved hashes) that the 2586109fe07a14b7a619365977d9523db9f8b333792Jason Evans * table will have to be doubled more than once in order to create a 2596109fe07a14b7a619365977d9523db9f8b333792Jason Evans * usable table. 2606109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 2616109fe07a14b7a619365977d9523db9f8b333792Jason Evans lg_prevbuckets = ckh->lg_curbuckets; 2626109fe07a14b7a619365977d9523db9f8b333792Jason Evans lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS; 2636109fe07a14b7a619365977d9523db9f8b333792Jason Evans while (true) { 26438d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans size_t usize; 26538d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans 2666109fe07a14b7a619365977d9523db9f8b333792Jason Evans lg_curcells++; 26738d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans usize = sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE, NULL); 26838d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans if (usize == 0) { 26938d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans ret = true; 270a1ee7838e14b321a97bfacb1f1cf5004198f2203Jason Evans goto label_return; 27138d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans } 27238d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans tab = (ckhc_t *)ipalloc(usize, CACHELINE, true); 2736109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (tab == NULL) { 2746109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret = true; 275a1ee7838e14b321a97bfacb1f1cf5004198f2203Jason Evans goto label_return; 2766109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 2776109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Swap in new table. */ 2786109fe07a14b7a619365977d9523db9f8b333792Jason Evans ttab = ckh->tab; 2796109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->tab = tab; 2806109fe07a14b7a619365977d9523db9f8b333792Jason Evans tab = ttab; 2816109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; 2826109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2836109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh_rebuild(ckh, tab) == false) { 2846109fe07a14b7a619365977d9523db9f8b333792Jason Evans idalloc(tab); 2856109fe07a14b7a619365977d9523db9f8b333792Jason Evans break; 2866109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 2876109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2886109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Rebuilding failed, so back out partially rebuilt table. */ 2896109fe07a14b7a619365977d9523db9f8b333792Jason Evans idalloc(ckh->tab); 2906109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->tab = tab; 2916109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->lg_curbuckets = lg_prevbuckets; 2926109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 2936109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2946109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret = false; 295a1ee7838e14b321a97bfacb1f1cf5004198f2203Jason Evanslabel_return: 2966109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (ret); 2976109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 2986109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2996109fe07a14b7a619365977d9523db9f8b333792Jason Evansstatic void 3006109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_shrink(ckh_t *ckh) 3016109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 3026109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckhc_t *tab, *ttab; 30338d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans size_t lg_curcells, usize; 3046109fe07a14b7a619365977d9523db9f8b333792Jason Evans unsigned lg_prevbuckets; 3056109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3066109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 3076109fe07a14b7a619365977d9523db9f8b333792Jason Evans * It is possible (though unlikely, given well behaved hashes) that the 3086109fe07a14b7a619365977d9523db9f8b333792Jason Evans * table rebuild will fail. 3096109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 3106109fe07a14b7a619365977d9523db9f8b333792Jason Evans lg_prevbuckets = ckh->lg_curbuckets; 3116109fe07a14b7a619365977d9523db9f8b333792Jason Evans lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS - 1; 31238d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans usize = sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE, NULL); 31338d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans if (usize == 0) 31438d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans return; 31538d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans tab = (ckhc_t *)ipalloc(usize, CACHELINE, true); 3166109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (tab == NULL) { 3176109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 3186109fe07a14b7a619365977d9523db9f8b333792Jason Evans * An OOM error isn't worth propagating, since it doesn't 3196109fe07a14b7a619365977d9523db9f8b333792Jason Evans * prevent this or future operations from proceeding. 3206109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 3216109fe07a14b7a619365977d9523db9f8b333792Jason Evans return; 3226109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 3236109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Swap in new table. */ 3246109fe07a14b7a619365977d9523db9f8b333792Jason Evans ttab = ckh->tab; 3256109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->tab = tab; 3266109fe07a14b7a619365977d9523db9f8b333792Jason Evans tab = ttab; 3276109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; 3286109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3296109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh_rebuild(ckh, tab) == false) { 3306109fe07a14b7a619365977d9523db9f8b333792Jason Evans idalloc(tab); 3316109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_COUNT 3326109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->nshrinks++; 3336109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 3346109fe07a14b7a619365977d9523db9f8b333792Jason Evans return; 3356109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 3366109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3376109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Rebuilding failed, so back out partially rebuilt table. */ 3386109fe07a14b7a619365977d9523db9f8b333792Jason Evans idalloc(ckh->tab); 3396109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->tab = tab; 3406109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->lg_curbuckets = lg_prevbuckets; 3416109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_COUNT 3426109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->nshrinkfails++; 3436109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 3446109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 3456109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3466109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 3476109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_new(ckh_t *ckh, size_t minitems, ckh_hash_t *hash, ckh_keycomp_t *keycomp) 3486109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 3496109fe07a14b7a619365977d9523db9f8b333792Jason Evans bool ret; 35038d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans size_t mincells, usize; 3516109fe07a14b7a619365977d9523db9f8b333792Jason Evans unsigned lg_mincells; 3526109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3536109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(minitems > 0); 3546109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(hash != NULL); 3556109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(keycomp != NULL); 3566109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3576109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_COUNT 3586109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->ngrows = 0; 3596109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->nshrinks = 0; 3606109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->nshrinkfails = 0; 3616109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->ninserts = 0; 3626109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->nrelocs = 0; 3636109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 36484f7cdb0c588322dfd50a26497fc1cb54b792018Jason Evans ckh->prng_state = 42; /* Value doesn't really matter. */ 3656109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->count = 0; 3666109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3676109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 3686109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Find the minimum power of 2 that is large enough to fit aBaseCount 3696109fe07a14b7a619365977d9523db9f8b333792Jason Evans * entries. We are using (2+,2) cuckoo hashing, which has an expected 3706109fe07a14b7a619365977d9523db9f8b333792Jason Evans * maximum load factor of at least ~0.86, so 0.75 is a conservative load 3716109fe07a14b7a619365977d9523db9f8b333792Jason Evans * factor that will typically allow 2^aLgMinItems to fit without ever 3726109fe07a14b7a619365977d9523db9f8b333792Jason Evans * growing the table. 3736109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 3746109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(LG_CKH_BUCKET_CELLS > 0); 3756109fe07a14b7a619365977d9523db9f8b333792Jason Evans mincells = ((minitems + (3 - (minitems % 3))) / 3) << 2; 3766109fe07a14b7a619365977d9523db9f8b333792Jason Evans for (lg_mincells = LG_CKH_BUCKET_CELLS; 3776109fe07a14b7a619365977d9523db9f8b333792Jason Evans (ZU(1) << lg_mincells) < mincells; 3786109fe07a14b7a619365977d9523db9f8b333792Jason Evans lg_mincells++) 3796109fe07a14b7a619365977d9523db9f8b333792Jason Evans ; /* Do nothing. */ 3806109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->lg_minbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; 3816109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->lg_curbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; 3826109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->hash = hash; 3836109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->keycomp = keycomp; 3846109fe07a14b7a619365977d9523db9f8b333792Jason Evans 38538d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans usize = sa2u(sizeof(ckhc_t) << lg_mincells, CACHELINE, NULL); 38638d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans if (usize == 0) { 38738d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans ret = true; 388a1ee7838e14b321a97bfacb1f1cf5004198f2203Jason Evans goto label_return; 38938d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans } 39038d9210c464c4ad49655a4da6bc84ea4fbec83d2Jason Evans ckh->tab = (ckhc_t *)ipalloc(usize, CACHELINE, true); 3916109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh->tab == NULL) { 3926109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret = true; 393a1ee7838e14b321a97bfacb1f1cf5004198f2203Jason Evans goto label_return; 3946109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 3956109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3966109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret = false; 397a1ee7838e14b321a97bfacb1f1cf5004198f2203Jason Evanslabel_return: 3986109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (ret); 3996109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 4006109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4016109fe07a14b7a619365977d9523db9f8b333792Jason Evansvoid 4026109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_delete(ckh_t *ckh) 4036109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 4046109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4056109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh != NULL); 4066109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4076109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_VERBOSE 4086109fe07a14b7a619365977d9523db9f8b333792Jason Evans malloc_printf( 4096109fe07a14b7a619365977d9523db9f8b333792Jason Evans "%s(%p): ngrows: %"PRIu64", nshrinks: %"PRIu64"," 4106109fe07a14b7a619365977d9523db9f8b333792Jason Evans " nshrinkfails: %"PRIu64", ninserts: %"PRIu64"," 4116109fe07a14b7a619365977d9523db9f8b333792Jason Evans " nrelocs: %"PRIu64"\n", __func__, ckh, 4126109fe07a14b7a619365977d9523db9f8b333792Jason Evans (unsigned long long)ckh->ngrows, 4136109fe07a14b7a619365977d9523db9f8b333792Jason Evans (unsigned long long)ckh->nshrinks, 4146109fe07a14b7a619365977d9523db9f8b333792Jason Evans (unsigned long long)ckh->nshrinkfails, 4156109fe07a14b7a619365977d9523db9f8b333792Jason Evans (unsigned long long)ckh->ninserts, 4166109fe07a14b7a619365977d9523db9f8b333792Jason Evans (unsigned long long)ckh->nrelocs); 4176109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 4186109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4196109fe07a14b7a619365977d9523db9f8b333792Jason Evans idalloc(ckh->tab); 4206109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef JEMALLOC_DEBUG 4216109fe07a14b7a619365977d9523db9f8b333792Jason Evans memset(ckh, 0x5a, sizeof(ckh_t)); 4226109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 4236109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 4246109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4256109fe07a14b7a619365977d9523db9f8b333792Jason Evanssize_t 4266109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_count(ckh_t *ckh) 4276109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 4286109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4296109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh != NULL); 4306109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4316109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (ckh->count); 4326109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 4336109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4346109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 4356109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data) 4366109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 4376109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t i, ncells; 4386109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4396109fe07a14b7a619365977d9523db9f8b333792Jason Evans for (i = *tabind, ncells = (ZU(1) << (ckh->lg_curbuckets + 4406109fe07a14b7a619365977d9523db9f8b333792Jason Evans LG_CKH_BUCKET_CELLS)); i < ncells; i++) { 4416109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh->tab[i].key != NULL) { 4426109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (key != NULL) 4436109fe07a14b7a619365977d9523db9f8b333792Jason Evans *key = (void *)ckh->tab[i].key; 4446109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (data != NULL) 4456109fe07a14b7a619365977d9523db9f8b333792Jason Evans *data = (void *)ckh->tab[i].data; 4466109fe07a14b7a619365977d9523db9f8b333792Jason Evans *tabind = i + 1; 4476109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 4486109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 4496109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 4506109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4516109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (true); 4526109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 4536109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4546109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 4556109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_insert(ckh_t *ckh, const void *key, const void *data) 4566109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 4576109fe07a14b7a619365977d9523db9f8b333792Jason Evans bool ret; 4586109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4596109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh != NULL); 4606109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh_search(ckh, key, NULL, NULL)); 4616109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4626109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_COUNT 4636109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->ninserts++; 4646109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 4656109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4666109fe07a14b7a619365977d9523db9f8b333792Jason Evans while (ckh_try_insert(ckh, &key, &data)) { 4676109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh_grow(ckh)) { 4686109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret = true; 469a1ee7838e14b321a97bfacb1f1cf5004198f2203Jason Evans goto label_return; 4706109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 4716109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 4726109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4736109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret = false; 474a1ee7838e14b321a97bfacb1f1cf5004198f2203Jason Evanslabel_return: 4756109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (ret); 4766109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 4776109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4786109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 4796109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_remove(ckh_t *ckh, const void *searchkey, void **key, void **data) 4806109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 4816109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t cell; 4826109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4836109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh != NULL); 4846109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4856109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell = ckh_isearch(ckh, searchkey); 4866109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (cell != SIZE_T_MAX) { 4876109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (key != NULL) 4886109fe07a14b7a619365977d9523db9f8b333792Jason Evans *key = (void *)ckh->tab[cell].key; 4896109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (data != NULL) 4906109fe07a14b7a619365977d9523db9f8b333792Jason Evans *data = (void *)ckh->tab[cell].data; 4916109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->tab[cell].key = NULL; 4926109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->tab[cell].data = NULL; /* Not necessary. */ 4936109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4946109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->count--; 4956109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Try to halve the table if it is less than 1/4 full. */ 4966109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh->count < (ZU(1) << (ckh->lg_curbuckets 4976109fe07a14b7a619365977d9523db9f8b333792Jason Evans + LG_CKH_BUCKET_CELLS - 2)) && ckh->lg_curbuckets 4986109fe07a14b7a619365977d9523db9f8b333792Jason Evans > ckh->lg_minbuckets) { 4996109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Ignore error due to OOM. */ 5006109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh_shrink(ckh); 5016109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 5026109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5036109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 5046109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 5056109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5066109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (true); 5076109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 5086109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5096109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 5106109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data) 5116109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 5126109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t cell; 5136109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5146109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh != NULL); 5156109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5166109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell = ckh_isearch(ckh, searchkey); 5176109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (cell != SIZE_T_MAX) { 5186109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (key != NULL) 5196109fe07a14b7a619365977d9523db9f8b333792Jason Evans *key = (void *)ckh->tab[cell].key; 5206109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (data != NULL) 5216109fe07a14b7a619365977d9523db9f8b333792Jason Evans *data = (void *)ckh->tab[cell].data; 5226109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 5236109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 5246109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5256109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (true); 5266109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 5276109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5286109fe07a14b7a619365977d9523db9f8b333792Jason Evansvoid 5296109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_string_hash(const void *key, unsigned minbits, size_t *hash1, size_t *hash2) 5306109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 5316109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t ret1, ret2; 5326109fe07a14b7a619365977d9523db9f8b333792Jason Evans uint64_t h; 5336109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5346109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(minbits <= 32 || (SIZEOF_PTR == 8 && minbits <= 64)); 5356109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(hash1 != NULL); 5366109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(hash2 != NULL); 5376109fe07a14b7a619365977d9523db9f8b333792Jason Evans 538b8c8be7f8abe72f4cb4f315f3078ad864fd6a2d8Jason Evans h = hash(key, strlen((const char *)key), UINT64_C(0x94122f335b332aea)); 5396109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (minbits <= 32) { 5406109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 5416109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Avoid doing multiple hashes, since a single hash provides 5426109fe07a14b7a619365977d9523db9f8b333792Jason Evans * enough bits. 5436109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 5446109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret1 = h & ZU(0xffffffffU); 5456109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret2 = h >> 32; 5466109fe07a14b7a619365977d9523db9f8b333792Jason Evans } else { 5476109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret1 = h; 5486109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret2 = hash(key, strlen((const char *)key), 549b8c8be7f8abe72f4cb4f315f3078ad864fd6a2d8Jason Evans UINT64_C(0x8432a476666bbc13)); 5506109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 5516109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5526109fe07a14b7a619365977d9523db9f8b333792Jason Evans *hash1 = ret1; 5536109fe07a14b7a619365977d9523db9f8b333792Jason Evans *hash2 = ret2; 5546109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 5556109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5566109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 5576109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_string_keycomp(const void *k1, const void *k2) 5586109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 5596109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5606109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(k1 != NULL); 5616109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(k2 != NULL); 5626109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5636109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (strcmp((char *)k1, (char *)k2) ? false : true); 5646109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 5656109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5666109fe07a14b7a619365977d9523db9f8b333792Jason Evansvoid 5676109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_pointer_hash(const void *key, unsigned minbits, size_t *hash1, 5686109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t *hash2) 5696109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 5706109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t ret1, ret2; 5716109fe07a14b7a619365977d9523db9f8b333792Jason Evans uint64_t h; 572355b438c854227bbf8185cb7a3ce247d271a842eJason Evans union { 573355b438c854227bbf8185cb7a3ce247d271a842eJason Evans const void *v; 574355b438c854227bbf8185cb7a3ce247d271a842eJason Evans uint64_t i; 575355b438c854227bbf8185cb7a3ce247d271a842eJason Evans } u; 5766109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5776109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(minbits <= 32 || (SIZEOF_PTR == 8 && minbits <= 64)); 5786109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(hash1 != NULL); 5796109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(hash2 != NULL); 5806109fe07a14b7a619365977d9523db9f8b333792Jason Evans 581355b438c854227bbf8185cb7a3ce247d271a842eJason Evans assert(sizeof(u.v) == sizeof(u.i)); 582355b438c854227bbf8185cb7a3ce247d271a842eJason Evans#if (LG_SIZEOF_PTR != LG_SIZEOF_INT) 583355b438c854227bbf8185cb7a3ce247d271a842eJason Evans u.i = 0; 584355b438c854227bbf8185cb7a3ce247d271a842eJason Evans#endif 585355b438c854227bbf8185cb7a3ce247d271a842eJason Evans u.v = key; 586b8c8be7f8abe72f4cb4f315f3078ad864fd6a2d8Jason Evans h = hash(&u.i, sizeof(u.i), UINT64_C(0xd983396e68886082)); 5876109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (minbits <= 32) { 5886109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 5896109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Avoid doing multiple hashes, since a single hash provides 5906109fe07a14b7a619365977d9523db9f8b333792Jason Evans * enough bits. 5916109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 5926109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret1 = h & ZU(0xffffffffU); 5936109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret2 = h >> 32; 5946109fe07a14b7a619365977d9523db9f8b333792Jason Evans } else { 5956109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(SIZEOF_PTR == 8); 5966109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret1 = h; 597b8c8be7f8abe72f4cb4f315f3078ad864fd6a2d8Jason Evans ret2 = hash(&u.i, sizeof(u.i), UINT64_C(0x5e2be9aff8709a5d)); 5986109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 5996109fe07a14b7a619365977d9523db9f8b333792Jason Evans 6006109fe07a14b7a619365977d9523db9f8b333792Jason Evans *hash1 = ret1; 6016109fe07a14b7a619365977d9523db9f8b333792Jason Evans *hash2 = ret2; 6026109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 6036109fe07a14b7a619365977d9523db9f8b333792Jason Evans 6046109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 6056109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_pointer_keycomp(const void *k1, const void *k2) 6066109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 6076109fe07a14b7a619365977d9523db9f8b333792Jason Evans 6086109fe07a14b7a619365977d9523db9f8b333792Jason Evans return ((k1 == k2) ? true : false); 6096109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 610