Deleted Added
sdiff udiff text old ( 286866 ) new ( 296221 )
full compact
ckh.c (286866) ckh.c (296221)
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

--- 85 unchanged lines hidden (view full) ---

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 */
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

--- 85 unchanged lines hidden (view full) ---

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 */
102 prng32(offset, LG_CKH_BUCKET_CELLS, ckh->prng_state, CKH_A, CKH_C);
102 offset = (unsigned)prng_lg_range(&ckh->prng_state, LG_CKH_BUCKET_CELLS);
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);

--- 25 unchanged lines hidden (view full) ---

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 */
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);

--- 25 unchanged lines hidden (view full) ---

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 */
144 prng32(i, LG_CKH_BUCKET_CELLS, ckh->prng_state, CKH_A, CKH_C);
144 i = (unsigned)prng_lg_range(&ckh->prng_state,
145 LG_CKH_BUCKET_CELLS);
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

--- 89 unchanged lines hidden (view full) ---

242 return (false);
243}
244
245static bool
246ckh_grow(tsd_t *tsd, ckh_t *ckh)
247{
248 bool ret;
249 ckhc_t *tab, *ttab;
146 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i];
147 assert(cell->key != NULL);
148
149 /* Swap cell->{key,data} and {key,data} (evict). */
150 tkey = cell->key; tdata = cell->data;
151 cell->key = key; cell->data = data;
152 key = tkey; data = tdata;
153

--- 89 unchanged lines hidden (view full) ---

243 return (false);
244}
245
246static bool
247ckh_grow(tsd_t *tsd, ckh_t *ckh)
248{
249 bool ret;
250 ckhc_t *tab, *ttab;
250 size_t lg_curcells;
251 unsigned lg_prevbuckets;
251 unsigned lg_prevbuckets, lg_curcells;
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) {
265 size_t usize;
266
267 lg_curcells++;
268 usize = sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE);
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) {
265 size_t usize;
266
267 lg_curcells++;
268 usize = sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE);
269 if (usize == 0) {
269 if (unlikely(usize == 0 || usize > HUGE_MAXCLASS)) {
270 ret = true;
271 goto label_return;
272 }
273 tab = (ckhc_t *)ipallocztm(tsd, usize, CACHELINE, true, NULL,
274 true, NULL);
275 if (tab == NULL) {
276 ret = true;
277 goto label_return;
278 }
279 /* Swap in new table. */
280 ttab = ckh->tab;
281 ckh->tab = tab;
282 tab = ttab;
283 ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS;
284
285 if (!ckh_rebuild(ckh, tab)) {
270 ret = true;
271 goto label_return;
272 }
273 tab = (ckhc_t *)ipallocztm(tsd, usize, CACHELINE, true, NULL,
274 true, NULL);
275 if (tab == NULL) {
276 ret = true;
277 goto label_return;
278 }
279 /* Swap in new table. */
280 ttab = ckh->tab;
281 ckh->tab = tab;
282 tab = ttab;
283 ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS;
284
285 if (!ckh_rebuild(ckh, tab)) {
286 idalloctm(tsd, tab, tcache_get(tsd, false), true);
286 idalloctm(tsd, tab, tcache_get(tsd, false), true, true);
287 break;
288 }
289
290 /* Rebuilding failed, so back out partially rebuilt table. */
287 break;
288 }
289
290 /* Rebuilding failed, so back out partially rebuilt table. */
291 idalloctm(tsd, ckh->tab, tcache_get(tsd, false), true);
291 idalloctm(tsd, ckh->tab, tcache_get(tsd, false), true, true);
292 ckh->tab = tab;
293 ckh->lg_curbuckets = lg_prevbuckets;
294 }
295
296 ret = false;
297label_return:
298 return (ret);
299}
300
301static void
302ckh_shrink(tsd_t *tsd, ckh_t *ckh)
303{
304 ckhc_t *tab, *ttab;
292 ckh->tab = tab;
293 ckh->lg_curbuckets = lg_prevbuckets;
294 }
295
296 ret = false;
297label_return:
298 return (ret);
299}
300
301static void
302ckh_shrink(tsd_t *tsd, ckh_t *ckh)
303{
304 ckhc_t *tab, *ttab;
305 size_t lg_curcells, usize;
306 unsigned lg_prevbuckets;
305 size_t usize;
306 unsigned lg_prevbuckets, lg_curcells;
307
308 /*
309 * It is possible (though unlikely, given well behaved hashes) that the
310 * table rebuild will fail.
311 */
312 lg_prevbuckets = ckh->lg_curbuckets;
313 lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS - 1;
314 usize = sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE);
307
308 /*
309 * It is possible (though unlikely, given well behaved hashes) that the
310 * table rebuild will fail.
311 */
312 lg_prevbuckets = ckh->lg_curbuckets;
313 lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS - 1;
314 usize = sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE);
315 if (usize == 0)
315 if (unlikely(usize == 0 || usize > HUGE_MAXCLASS))
316 return;
317 tab = (ckhc_t *)ipallocztm(tsd, usize, CACHELINE, true, NULL, true,
318 NULL);
319 if (tab == NULL) {
320 /*
321 * An OOM error isn't worth propagating, since it doesn't
322 * prevent this or future operations from proceeding.
323 */
324 return;
325 }
326 /* Swap in new table. */
327 ttab = ckh->tab;
328 ckh->tab = tab;
329 tab = ttab;
330 ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS;
331
332 if (!ckh_rebuild(ckh, tab)) {
316 return;
317 tab = (ckhc_t *)ipallocztm(tsd, usize, CACHELINE, true, NULL, true,
318 NULL);
319 if (tab == NULL) {
320 /*
321 * An OOM error isn't worth propagating, since it doesn't
322 * prevent this or future operations from proceeding.
323 */
324 return;
325 }
326 /* Swap in new table. */
327 ttab = ckh->tab;
328 ckh->tab = tab;
329 tab = ttab;
330 ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS;
331
332 if (!ckh_rebuild(ckh, tab)) {
333 idalloctm(tsd, tab, tcache_get(tsd, false), true);
333 idalloctm(tsd, tab, tcache_get(tsd, false), true, true);
334#ifdef CKH_COUNT
335 ckh->nshrinks++;
336#endif
337 return;
338 }
339
340 /* Rebuilding failed, so back out partially rebuilt table. */
334#ifdef CKH_COUNT
335 ckh->nshrinks++;
336#endif
337 return;
338 }
339
340 /* Rebuilding failed, so back out partially rebuilt table. */
341 idalloctm(tsd, ckh->tab, tcache_get(tsd, false), true);
341 idalloctm(tsd, ckh->tab, tcache_get(tsd, false), true, true);
342 ckh->tab = tab;
343 ckh->lg_curbuckets = lg_prevbuckets;
344#ifdef CKH_COUNT
345 ckh->nshrinkfails++;
346#endif
347}
348
349bool

--- 32 unchanged lines hidden (view full) ---

382 lg_mincells++)
383 ; /* Do nothing. */
384 ckh->lg_minbuckets = lg_mincells - LG_CKH_BUCKET_CELLS;
385 ckh->lg_curbuckets = lg_mincells - LG_CKH_BUCKET_CELLS;
386 ckh->hash = hash;
387 ckh->keycomp = keycomp;
388
389 usize = sa2u(sizeof(ckhc_t) << lg_mincells, CACHELINE);
342 ckh->tab = tab;
343 ckh->lg_curbuckets = lg_prevbuckets;
344#ifdef CKH_COUNT
345 ckh->nshrinkfails++;
346#endif
347}
348
349bool

--- 32 unchanged lines hidden (view full) ---

382 lg_mincells++)
383 ; /* Do nothing. */
384 ckh->lg_minbuckets = lg_mincells - LG_CKH_BUCKET_CELLS;
385 ckh->lg_curbuckets = lg_mincells - LG_CKH_BUCKET_CELLS;
386 ckh->hash = hash;
387 ckh->keycomp = keycomp;
388
389 usize = sa2u(sizeof(ckhc_t) << lg_mincells, CACHELINE);
390 if (usize == 0) {
390 if (unlikely(usize == 0 || usize > HUGE_MAXCLASS)) {
391 ret = true;
392 goto label_return;
393 }
394 ckh->tab = (ckhc_t *)ipallocztm(tsd, usize, CACHELINE, true, NULL, true,
395 NULL);
396 if (ckh->tab == NULL) {
397 ret = true;
398 goto label_return;

--- 17 unchanged lines hidden (view full) ---

416 " nrelocs: %"FMTu64"\n", __func__, ckh,
417 (unsigned long long)ckh->ngrows,
418 (unsigned long long)ckh->nshrinks,
419 (unsigned long long)ckh->nshrinkfails,
420 (unsigned long long)ckh->ninserts,
421 (unsigned long long)ckh->nrelocs);
422#endif
423
391 ret = true;
392 goto label_return;
393 }
394 ckh->tab = (ckhc_t *)ipallocztm(tsd, usize, CACHELINE, true, NULL, true,
395 NULL);
396 if (ckh->tab == NULL) {
397 ret = true;
398 goto label_return;

--- 17 unchanged lines hidden (view full) ---

416 " nrelocs: %"FMTu64"\n", __func__, ckh,
417 (unsigned long long)ckh->ngrows,
418 (unsigned long long)ckh->nshrinks,
419 (unsigned long long)ckh->nshrinkfails,
420 (unsigned long long)ckh->ninserts,
421 (unsigned long long)ckh->nrelocs);
422#endif
423
424 idalloctm(tsd, ckh->tab, tcache_get(tsd, false), true);
424 idalloctm(tsd, ckh->tab, tcache_get(tsd, false), true, true);
425 if (config_debug)
426 memset(ckh, 0x5a, sizeof(ckh_t));
427}
428
429size_t
430ckh_count(ckh_t *ckh)
431{
432

--- 136 unchanged lines hidden --- 		425 if (config_debug)
426 memset(ckh, 0x5a, sizeof(ckh_t));
427}
428
429size_t
430ckh_count(ckh_t *ckh)
431{
432

--- 136 unchanged lines hidden ---