ckh.c revision 0657f12acd43eb2082a71230341449eca648bc9b
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); 7684c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans dassert(ckh->magic == CKH_MAGIC); 776109fe07a14b7a619365977d9523db9f8b333792Jason Evans 786109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->hash(key, ckh->lg_curbuckets, &hash1, &hash2); 796109fe07a14b7a619365977d9523db9f8b333792Jason Evans 806109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Search primary bucket. */ 816109fe07a14b7a619365977d9523db9f8b333792Jason Evans bucket = hash1 & ((ZU(1) << ckh->lg_curbuckets) - 1); 826109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell = ckh_bucket_search(ckh, bucket, key); 836109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (cell != SIZE_T_MAX) 846109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (cell); 856109fe07a14b7a619365977d9523db9f8b333792Jason Evans 866109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Search secondary bucket. */ 876109fe07a14b7a619365977d9523db9f8b333792Jason Evans bucket = hash2 & ((ZU(1) << ckh->lg_curbuckets) - 1); 886109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell = ckh_bucket_search(ckh, bucket, key); 896109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (cell); 906109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 916109fe07a14b7a619365977d9523db9f8b333792Jason Evans 926109fe07a14b7a619365977d9523db9f8b333792Jason EvansJEMALLOC_INLINE bool 936109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_try_bucket_insert(ckh_t *ckh, size_t bucket, const void *key, 946109fe07a14b7a619365977d9523db9f8b333792Jason Evans const void *data) 956109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 966109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckhc_t *cell; 976109fe07a14b7a619365977d9523db9f8b333792Jason Evans unsigned offset, i; 986109fe07a14b7a619365977d9523db9f8b333792Jason Evans 996109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 1006109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Cycle through the cells in the bucket, starting at a random position. 1016109fe07a14b7a619365977d9523db9f8b333792Jason Evans * The randomness avoids worst-case search overhead as buckets fill up. 1026109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 103b9477e782b07afa38c4b1dc0688e053be8a84dd8Jason Evans prn32(offset, LG_CKH_BUCKET_CELLS, ckh->prn_state, CKH_A, CKH_C); 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 */ 1246109fe07a14b7a619365977d9523db9f8b333792Jason EvansJEMALLOC_INLINE 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; 1306109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t hash1, hash2, 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 */ 145b9477e782b07afa38c4b1dc0688e053be8a84dd8Jason Evans prn32(i, LG_CKH_BUCKET_CELLS, ckh->prn_state, CKH_A, CKH_C); 1466109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; 1476109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(cell->key != NULL); 1486109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1496109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Swap cell->{key,data} and {key,data} (evict). */ 1506109fe07a14b7a619365977d9523db9f8b333792Jason Evans tkey = cell->key; tdata = cell->data; 1516109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell->key = key; cell->data = data; 1526109fe07a14b7a619365977d9523db9f8b333792Jason Evans key = tkey; data = tdata; 1536109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1546109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_COUNT 1556109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->nrelocs++; 1566109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 1576109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1586109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Find the alternate bucket for the evicted item. */ 1596109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->hash(key, ckh->lg_curbuckets, &hash1, &hash2); 1606109fe07a14b7a619365977d9523db9f8b333792Jason Evans tbucket = hash2 & ((ZU(1) << ckh->lg_curbuckets) - 1); 1616109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (tbucket == bucket) { 1626109fe07a14b7a619365977d9523db9f8b333792Jason Evans tbucket = hash1 & ((ZU(1) << ckh->lg_curbuckets) - 1); 1636109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 1646109fe07a14b7a619365977d9523db9f8b333792Jason Evans * It may be that (tbucket == bucket) still, if the 1656109fe07a14b7a619365977d9523db9f8b333792Jason Evans * item's hashes both indicate this bucket. However, 1666109fe07a14b7a619365977d9523db9f8b333792Jason Evans * we are guaranteed to eventually escape this bucket 1676109fe07a14b7a619365977d9523db9f8b333792Jason Evans * during iteration, assuming pseudo-random item 1686109fe07a14b7a619365977d9523db9f8b333792Jason Evans * selection (true randomness would make infinite 1696109fe07a14b7a619365977d9523db9f8b333792Jason Evans * looping a remote possibility). The reason we can 1706109fe07a14b7a619365977d9523db9f8b333792Jason Evans * never get trapped forever is that there are two 1716109fe07a14b7a619365977d9523db9f8b333792Jason Evans * cases: 1726109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 1736109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 1) This bucket == argbucket, so we will quickly 1746109fe07a14b7a619365977d9523db9f8b333792Jason Evans * detect an eviction cycle and terminate. 1756109fe07a14b7a619365977d9523db9f8b333792Jason Evans * 2) An item was evicted to this bucket from another, 1766109fe07a14b7a619365977d9523db9f8b333792Jason Evans * which means that at least one item in this bucket 1776109fe07a14b7a619365977d9523db9f8b333792Jason Evans * has hashes that indicate distinct buckets. 1786109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 1796109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 1806109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Check for a cycle. */ 1816109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (tbucket == argbucket) { 1826109fe07a14b7a619365977d9523db9f8b333792Jason Evans *argkey = key; 1836109fe07a14b7a619365977d9523db9f8b333792Jason Evans *argdata = data; 1846109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (true); 1856109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 1866109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1876109fe07a14b7a619365977d9523db9f8b333792Jason Evans bucket = tbucket; 1886109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh_try_bucket_insert(ckh, bucket, key, data) == false) 1896109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 1906109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 1916109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 1926109fe07a14b7a619365977d9523db9f8b333792Jason Evans 1936109fe07a14b7a619365977d9523db9f8b333792Jason EvansJEMALLOC_INLINE bool 1946109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_try_insert(ckh_t *ckh, void const**argkey, void const**argdata) 1956109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 1966109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t hash1, hash2, bucket; 1976109fe07a14b7a619365977d9523db9f8b333792Jason Evans const void *key = *argkey; 1986109fe07a14b7a619365977d9523db9f8b333792Jason Evans const void *data = *argdata; 1996109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2006109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->hash(key, ckh->lg_curbuckets, &hash1, &hash2); 2016109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2026109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Try to insert in primary bucket. */ 2036109fe07a14b7a619365977d9523db9f8b333792Jason Evans bucket = hash1 & ((ZU(1) << ckh->lg_curbuckets) - 1); 2046109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh_try_bucket_insert(ckh, bucket, key, data) == false) 2056109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 2066109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2076109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Try to insert in secondary bucket. */ 2086109fe07a14b7a619365977d9523db9f8b333792Jason Evans bucket = hash2 & ((ZU(1) << ckh->lg_curbuckets) - 1); 2096109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh_try_bucket_insert(ckh, bucket, key, data) == false) 2106109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 2116109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2126109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 2136109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Try to find a place for this item via iterative eviction/relocation. 2146109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 2156109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (ckh_evict_reloc_insert(ckh, bucket, argkey, argdata)); 2166109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 2176109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2186109fe07a14b7a619365977d9523db9f8b333792Jason Evans/* 2196109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Try to rebuild the hash table from scratch by inserting all items from the 2206109fe07a14b7a619365977d9523db9f8b333792Jason Evans * old table into the new. 2216109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 2226109fe07a14b7a619365977d9523db9f8b333792Jason EvansJEMALLOC_INLINE bool 2236109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_rebuild(ckh_t *ckh, ckhc_t *aTab) 2246109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 2256109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t count, i, nins; 2266109fe07a14b7a619365977d9523db9f8b333792Jason Evans const void *key, *data; 2276109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2286109fe07a14b7a619365977d9523db9f8b333792Jason Evans count = ckh->count; 2296109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->count = 0; 2306109fe07a14b7a619365977d9523db9f8b333792Jason Evans for (i = nins = 0; nins < count; i++) { 2316109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (aTab[i].key != NULL) { 2326109fe07a14b7a619365977d9523db9f8b333792Jason Evans key = aTab[i].key; 2336109fe07a14b7a619365977d9523db9f8b333792Jason Evans data = aTab[i].data; 2346109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh_try_insert(ckh, &key, &data)) { 2356109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->count = count; 2366109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (true); 2376109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 2386109fe07a14b7a619365977d9523db9f8b333792Jason Evans nins++; 2396109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 2406109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 2416109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2426109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 2436109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 2446109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2456109fe07a14b7a619365977d9523db9f8b333792Jason Evansstatic bool 2466109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_grow(ckh_t *ckh) 2476109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 2486109fe07a14b7a619365977d9523db9f8b333792Jason Evans bool ret; 2496109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckhc_t *tab, *ttab; 2506109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t lg_curcells; 2516109fe07a14b7a619365977d9523db9f8b333792Jason Evans unsigned lg_prevbuckets; 2526109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2536109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_COUNT 2546109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->ngrows++; 2556109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 2566109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2576109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 2586109fe07a14b7a619365977d9523db9f8b333792Jason Evans * It is possible (though unlikely, given well behaved hashes) that the 2596109fe07a14b7a619365977d9523db9f8b333792Jason Evans * table will have to be doubled more than once in order to create a 2606109fe07a14b7a619365977d9523db9f8b333792Jason Evans * usable table. 2616109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 2626109fe07a14b7a619365977d9523db9f8b333792Jason Evans lg_prevbuckets = ckh->lg_curbuckets; 2636109fe07a14b7a619365977d9523db9f8b333792Jason Evans lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS; 2646109fe07a14b7a619365977d9523db9f8b333792Jason Evans while (true) { 2656109fe07a14b7a619365977d9523db9f8b333792Jason Evans lg_curcells++; 2668e3c3c61b5bb676a705450708e7e79698cdc9e0cJason Evans tab = (ckhc_t *)ipalloc(sizeof(ckhc_t) << lg_curcells, 2678e3c3c61b5bb676a705450708e7e79698cdc9e0cJason Evans ZU(1) << LG_CACHELINE, true); 2686109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (tab == NULL) { 2696109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret = true; 2706109fe07a14b7a619365977d9523db9f8b333792Jason Evans goto RETURN; 2716109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 2726109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Swap in new table. */ 2736109fe07a14b7a619365977d9523db9f8b333792Jason Evans ttab = ckh->tab; 2746109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->tab = tab; 2756109fe07a14b7a619365977d9523db9f8b333792Jason Evans tab = ttab; 2766109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; 2776109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2786109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh_rebuild(ckh, tab) == false) { 2796109fe07a14b7a619365977d9523db9f8b333792Jason Evans idalloc(tab); 2806109fe07a14b7a619365977d9523db9f8b333792Jason Evans break; 2816109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 2826109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2836109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Rebuilding failed, so back out partially rebuilt table. */ 2846109fe07a14b7a619365977d9523db9f8b333792Jason Evans idalloc(ckh->tab); 2856109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->tab = tab; 2866109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->lg_curbuckets = lg_prevbuckets; 2876109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 2886109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2896109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret = false; 2906109fe07a14b7a619365977d9523db9f8b333792Jason EvansRETURN: 2916109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (ret); 2926109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 2936109fe07a14b7a619365977d9523db9f8b333792Jason Evans 2946109fe07a14b7a619365977d9523db9f8b333792Jason Evansstatic void 2956109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_shrink(ckh_t *ckh) 2966109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 2976109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckhc_t *tab, *ttab; 2986109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t lg_curcells; 2996109fe07a14b7a619365977d9523db9f8b333792Jason Evans unsigned lg_prevbuckets; 3006109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3016109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 3026109fe07a14b7a619365977d9523db9f8b333792Jason Evans * It is possible (though unlikely, given well behaved hashes) that the 3036109fe07a14b7a619365977d9523db9f8b333792Jason Evans * table rebuild will fail. 3046109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 3056109fe07a14b7a619365977d9523db9f8b333792Jason Evans lg_prevbuckets = ckh->lg_curbuckets; 3066109fe07a14b7a619365977d9523db9f8b333792Jason Evans lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS - 1; 3078e3c3c61b5bb676a705450708e7e79698cdc9e0cJason Evans tab = (ckhc_t *)ipalloc(sizeof(ckhc_t) << lg_curcells, 3088e3c3c61b5bb676a705450708e7e79698cdc9e0cJason Evans ZU(1) << LG_CACHELINE, true); 3096109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (tab == NULL) { 3106109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 3116109fe07a14b7a619365977d9523db9f8b333792Jason Evans * An OOM error isn't worth propagating, since it doesn't 3126109fe07a14b7a619365977d9523db9f8b333792Jason Evans * prevent this or future operations from proceeding. 3136109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 3146109fe07a14b7a619365977d9523db9f8b333792Jason Evans return; 3156109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 3166109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Swap in new table. */ 3176109fe07a14b7a619365977d9523db9f8b333792Jason Evans ttab = ckh->tab; 3186109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->tab = tab; 3196109fe07a14b7a619365977d9523db9f8b333792Jason Evans tab = ttab; 3206109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; 3216109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3226109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh_rebuild(ckh, tab) == false) { 3236109fe07a14b7a619365977d9523db9f8b333792Jason Evans idalloc(tab); 3246109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_COUNT 3256109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->nshrinks++; 3266109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 3276109fe07a14b7a619365977d9523db9f8b333792Jason Evans return; 3286109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 3296109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3306109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Rebuilding failed, so back out partially rebuilt table. */ 3316109fe07a14b7a619365977d9523db9f8b333792Jason Evans idalloc(ckh->tab); 3326109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->tab = tab; 3336109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->lg_curbuckets = lg_prevbuckets; 3346109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_COUNT 3356109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->nshrinkfails++; 3366109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 3376109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 3386109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3396109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 3406109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_new(ckh_t *ckh, size_t minitems, ckh_hash_t *hash, ckh_keycomp_t *keycomp) 3416109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 3426109fe07a14b7a619365977d9523db9f8b333792Jason Evans bool ret; 3436109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t mincells; 3446109fe07a14b7a619365977d9523db9f8b333792Jason Evans unsigned lg_mincells; 3456109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3466109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(minitems > 0); 3476109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(hash != NULL); 3486109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(keycomp != NULL); 3496109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3506109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_COUNT 3516109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->ngrows = 0; 3526109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->nshrinks = 0; 3536109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->nshrinkfails = 0; 3546109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->ninserts = 0; 3556109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->nrelocs = 0; 3566109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 3576109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->prn_state = 42; /* Value doesn't really matter. */ 3586109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->count = 0; 3596109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3606109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 3616109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Find the minimum power of 2 that is large enough to fit aBaseCount 3626109fe07a14b7a619365977d9523db9f8b333792Jason Evans * entries. We are using (2+,2) cuckoo hashing, which has an expected 3636109fe07a14b7a619365977d9523db9f8b333792Jason Evans * maximum load factor of at least ~0.86, so 0.75 is a conservative load 3646109fe07a14b7a619365977d9523db9f8b333792Jason Evans * factor that will typically allow 2^aLgMinItems to fit without ever 3656109fe07a14b7a619365977d9523db9f8b333792Jason Evans * growing the table. 3666109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 3676109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(LG_CKH_BUCKET_CELLS > 0); 3686109fe07a14b7a619365977d9523db9f8b333792Jason Evans mincells = ((minitems + (3 - (minitems % 3))) / 3) << 2; 3696109fe07a14b7a619365977d9523db9f8b333792Jason Evans for (lg_mincells = LG_CKH_BUCKET_CELLS; 3706109fe07a14b7a619365977d9523db9f8b333792Jason Evans (ZU(1) << lg_mincells) < mincells; 3716109fe07a14b7a619365977d9523db9f8b333792Jason Evans lg_mincells++) 3726109fe07a14b7a619365977d9523db9f8b333792Jason Evans ; /* Do nothing. */ 3736109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->lg_minbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; 3746109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->lg_curbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; 3756109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->hash = hash; 3766109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->keycomp = keycomp; 3776109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3788e3c3c61b5bb676a705450708e7e79698cdc9e0cJason Evans ckh->tab = (ckhc_t *)ipalloc(sizeof(ckhc_t) << lg_mincells, 3798e3c3c61b5bb676a705450708e7e79698cdc9e0cJason Evans (ZU(1) << LG_CACHELINE), true); 3806109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh->tab == NULL) { 3816109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret = true; 3826109fe07a14b7a619365977d9523db9f8b333792Jason Evans goto RETURN; 3836109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 3846109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3856109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef JEMALLOC_DEBUG 386dbd3832d207d93e47b4fd3ba3f4824abd1463363Jason Evans ckh->magic = CKH_MAGIC; 3876109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 3886109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3896109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret = false; 3906109fe07a14b7a619365977d9523db9f8b333792Jason EvansRETURN: 3916109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (ret); 3926109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 3936109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3946109fe07a14b7a619365977d9523db9f8b333792Jason Evansvoid 3956109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_delete(ckh_t *ckh) 3966109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 3976109fe07a14b7a619365977d9523db9f8b333792Jason Evans 3986109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh != NULL); 39984c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans dassert(ckh->magic == CKH_MAGIC); 4006109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4016109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_VERBOSE 4026109fe07a14b7a619365977d9523db9f8b333792Jason Evans malloc_printf( 4036109fe07a14b7a619365977d9523db9f8b333792Jason Evans "%s(%p): ngrows: %"PRIu64", nshrinks: %"PRIu64"," 4046109fe07a14b7a619365977d9523db9f8b333792Jason Evans " nshrinkfails: %"PRIu64", ninserts: %"PRIu64"," 4056109fe07a14b7a619365977d9523db9f8b333792Jason Evans " nrelocs: %"PRIu64"\n", __func__, ckh, 4066109fe07a14b7a619365977d9523db9f8b333792Jason Evans (unsigned long long)ckh->ngrows, 4076109fe07a14b7a619365977d9523db9f8b333792Jason Evans (unsigned long long)ckh->nshrinks, 4086109fe07a14b7a619365977d9523db9f8b333792Jason Evans (unsigned long long)ckh->nshrinkfails, 4096109fe07a14b7a619365977d9523db9f8b333792Jason Evans (unsigned long long)ckh->ninserts, 4106109fe07a14b7a619365977d9523db9f8b333792Jason Evans (unsigned long long)ckh->nrelocs); 4116109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 4126109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4136109fe07a14b7a619365977d9523db9f8b333792Jason Evans idalloc(ckh->tab); 4146109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef JEMALLOC_DEBUG 4156109fe07a14b7a619365977d9523db9f8b333792Jason Evans memset(ckh, 0x5a, sizeof(ckh_t)); 4166109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 4176109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 4186109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4196109fe07a14b7a619365977d9523db9f8b333792Jason Evanssize_t 4206109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_count(ckh_t *ckh) 4216109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 4226109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4236109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh != NULL); 42484c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans dassert(ckh->magic == CKH_MAGIC); 4256109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4266109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (ckh->count); 4276109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 4286109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4296109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 4306109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data) 4316109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 4326109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t i, ncells; 4336109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4346109fe07a14b7a619365977d9523db9f8b333792Jason Evans for (i = *tabind, ncells = (ZU(1) << (ckh->lg_curbuckets + 4356109fe07a14b7a619365977d9523db9f8b333792Jason Evans LG_CKH_BUCKET_CELLS)); i < ncells; i++) { 4366109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh->tab[i].key != NULL) { 4376109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (key != NULL) 4386109fe07a14b7a619365977d9523db9f8b333792Jason Evans *key = (void *)ckh->tab[i].key; 4396109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (data != NULL) 4406109fe07a14b7a619365977d9523db9f8b333792Jason Evans *data = (void *)ckh->tab[i].data; 4416109fe07a14b7a619365977d9523db9f8b333792Jason Evans *tabind = i + 1; 4426109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 4436109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 4446109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 4456109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4466109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (true); 4476109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 4486109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4496109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 4506109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_insert(ckh_t *ckh, const void *key, const void *data) 4516109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 4526109fe07a14b7a619365977d9523db9f8b333792Jason Evans bool ret; 4536109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4546109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh != NULL); 45584c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans dassert(ckh->magic == CKH_MAGIC); 4566109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh_search(ckh, key, NULL, NULL)); 4576109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4586109fe07a14b7a619365977d9523db9f8b333792Jason Evans#ifdef CKH_COUNT 4596109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->ninserts++; 4606109fe07a14b7a619365977d9523db9f8b333792Jason Evans#endif 4616109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4626109fe07a14b7a619365977d9523db9f8b333792Jason Evans while (ckh_try_insert(ckh, &key, &data)) { 4636109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh_grow(ckh)) { 4646109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret = true; 4656109fe07a14b7a619365977d9523db9f8b333792Jason Evans goto RETURN; 4666109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 4676109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 4686109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4696109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret = false; 4706109fe07a14b7a619365977d9523db9f8b333792Jason EvansRETURN: 4716109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (ret); 4726109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 4736109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4746109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 4756109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_remove(ckh_t *ckh, const void *searchkey, void **key, void **data) 4766109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 4776109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t cell; 4786109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4796109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh != NULL); 48084c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans dassert(ckh->magic == CKH_MAGIC); 4816109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4826109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell = ckh_isearch(ckh, searchkey); 4836109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (cell != SIZE_T_MAX) { 4846109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (key != NULL) 4856109fe07a14b7a619365977d9523db9f8b333792Jason Evans *key = (void *)ckh->tab[cell].key; 4866109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (data != NULL) 4876109fe07a14b7a619365977d9523db9f8b333792Jason Evans *data = (void *)ckh->tab[cell].data; 4886109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->tab[cell].key = NULL; 4896109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->tab[cell].data = NULL; /* Not necessary. */ 4906109fe07a14b7a619365977d9523db9f8b333792Jason Evans 4916109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh->count--; 4926109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Try to halve the table if it is less than 1/4 full. */ 4936109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (ckh->count < (ZU(1) << (ckh->lg_curbuckets 4946109fe07a14b7a619365977d9523db9f8b333792Jason Evans + LG_CKH_BUCKET_CELLS - 2)) && ckh->lg_curbuckets 4956109fe07a14b7a619365977d9523db9f8b333792Jason Evans > ckh->lg_minbuckets) { 4966109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* Ignore error due to OOM. */ 4976109fe07a14b7a619365977d9523db9f8b333792Jason Evans ckh_shrink(ckh); 4986109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 4996109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5006109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 5016109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 5026109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5036109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (true); 5046109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 5056109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5066109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 5076109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data) 5086109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 5096109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t cell; 5106109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5116109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(ckh != NULL); 51284c8eefeffa246607790ad12e28b0f6a24ecc59dJason Evans dassert(ckh->magic == CKH_MAGIC); 5136109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5146109fe07a14b7a619365977d9523db9f8b333792Jason Evans cell = ckh_isearch(ckh, searchkey); 5156109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (cell != SIZE_T_MAX) { 5166109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (key != NULL) 5176109fe07a14b7a619365977d9523db9f8b333792Jason Evans *key = (void *)ckh->tab[cell].key; 5186109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (data != NULL) 5196109fe07a14b7a619365977d9523db9f8b333792Jason Evans *data = (void *)ckh->tab[cell].data; 5206109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (false); 5216109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 5226109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5236109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (true); 5246109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 5256109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5266109fe07a14b7a619365977d9523db9f8b333792Jason Evansvoid 5276109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_string_hash(const void *key, unsigned minbits, size_t *hash1, size_t *hash2) 5286109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 5296109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t ret1, ret2; 5306109fe07a14b7a619365977d9523db9f8b333792Jason Evans uint64_t h; 5316109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5326109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(minbits <= 32 || (SIZEOF_PTR == 8 && minbits <= 64)); 5336109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(hash1 != NULL); 5346109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(hash2 != NULL); 5356109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5366109fe07a14b7a619365977d9523db9f8b333792Jason Evans h = hash(key, strlen((const char *)key), 0x94122f335b332aeaLLU); 5376109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (minbits <= 32) { 5386109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 5396109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Avoid doing multiple hashes, since a single hash provides 5406109fe07a14b7a619365977d9523db9f8b333792Jason Evans * enough bits. 5416109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 5426109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret1 = h & ZU(0xffffffffU); 5436109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret2 = h >> 32; 5446109fe07a14b7a619365977d9523db9f8b333792Jason Evans } else { 5456109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret1 = h; 5466109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret2 = hash(key, strlen((const char *)key), 5476109fe07a14b7a619365977d9523db9f8b333792Jason Evans 0x8432a476666bbc13U); 5486109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 5496109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5506109fe07a14b7a619365977d9523db9f8b333792Jason Evans *hash1 = ret1; 5516109fe07a14b7a619365977d9523db9f8b333792Jason Evans *hash2 = ret2; 5526109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 5536109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5546109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 5556109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_string_keycomp(const void *k1, const void *k2) 5566109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 5576109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5586109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(k1 != NULL); 5596109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(k2 != NULL); 5606109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5616109fe07a14b7a619365977d9523db9f8b333792Jason Evans return (strcmp((char *)k1, (char *)k2) ? false : true); 5626109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 5636109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5646109fe07a14b7a619365977d9523db9f8b333792Jason Evansvoid 5656109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_pointer_hash(const void *key, unsigned minbits, size_t *hash1, 5666109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t *hash2) 5676109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 5686109fe07a14b7a619365977d9523db9f8b333792Jason Evans size_t ret1, ret2; 5696109fe07a14b7a619365977d9523db9f8b333792Jason Evans uint64_t h; 570355b438c854227bbf8185cb7a3ce247d271a842eJason Evans union { 571355b438c854227bbf8185cb7a3ce247d271a842eJason Evans const void *v; 572355b438c854227bbf8185cb7a3ce247d271a842eJason Evans uint64_t i; 573355b438c854227bbf8185cb7a3ce247d271a842eJason Evans } u; 5746109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5756109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(minbits <= 32 || (SIZEOF_PTR == 8 && minbits <= 64)); 5766109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(hash1 != NULL); 5776109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(hash2 != NULL); 5786109fe07a14b7a619365977d9523db9f8b333792Jason Evans 579355b438c854227bbf8185cb7a3ce247d271a842eJason Evans assert(sizeof(u.v) == sizeof(u.i)); 580355b438c854227bbf8185cb7a3ce247d271a842eJason Evans#if (LG_SIZEOF_PTR != LG_SIZEOF_INT) 581355b438c854227bbf8185cb7a3ce247d271a842eJason Evans u.i = 0; 582355b438c854227bbf8185cb7a3ce247d271a842eJason Evans#endif 583355b438c854227bbf8185cb7a3ce247d271a842eJason Evans u.v = key; 584355b438c854227bbf8185cb7a3ce247d271a842eJason Evans h = hash(&u.i, sizeof(u.i), 0xd983396e68886082LLU); 5856109fe07a14b7a619365977d9523db9f8b333792Jason Evans if (minbits <= 32) { 5866109fe07a14b7a619365977d9523db9f8b333792Jason Evans /* 5876109fe07a14b7a619365977d9523db9f8b333792Jason Evans * Avoid doing multiple hashes, since a single hash provides 5886109fe07a14b7a619365977d9523db9f8b333792Jason Evans * enough bits. 5896109fe07a14b7a619365977d9523db9f8b333792Jason Evans */ 5906109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret1 = h & ZU(0xffffffffU); 5916109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret2 = h >> 32; 5926109fe07a14b7a619365977d9523db9f8b333792Jason Evans } else { 5936109fe07a14b7a619365977d9523db9f8b333792Jason Evans assert(SIZEOF_PTR == 8); 5946109fe07a14b7a619365977d9523db9f8b333792Jason Evans ret1 = h; 595355b438c854227bbf8185cb7a3ce247d271a842eJason Evans ret2 = hash(&u.i, sizeof(u.i), 0x5e2be9aff8709a5dLLU); 5966109fe07a14b7a619365977d9523db9f8b333792Jason Evans } 5976109fe07a14b7a619365977d9523db9f8b333792Jason Evans 5986109fe07a14b7a619365977d9523db9f8b333792Jason Evans *hash1 = ret1; 5996109fe07a14b7a619365977d9523db9f8b333792Jason Evans *hash2 = ret2; 6006109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 6016109fe07a14b7a619365977d9523db9f8b333792Jason Evans 6026109fe07a14b7a619365977d9523db9f8b333792Jason Evansbool 6036109fe07a14b7a619365977d9523db9f8b333792Jason Evansckh_pointer_keycomp(const void *k1, const void *k2) 6046109fe07a14b7a619365977d9523db9f8b333792Jason Evans{ 6056109fe07a14b7a619365977d9523db9f8b333792Jason Evans 6066109fe07a14b7a619365977d9523db9f8b333792Jason Evans return ((k1 == k2) ? true : false); 6076109fe07a14b7a619365977d9523db9f8b333792Jason Evans} 608