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