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

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

35 *
36 ******************************************************************************/
37#define JEMALLOC_CKH_C_
38#include "jemalloc/internal/jemalloc_internal.h"
39
40/******************************************************************************/
41/* Function prototypes for non-inline static functions. */
42
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

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

35 *
36 ******************************************************************************/
37#define JEMALLOC_CKH_C_
38#include "jemalloc/internal/jemalloc_internal.h"
39
40/******************************************************************************/
41/* Function prototypes for non-inline static functions. */
42
43static bool ckh_grow(tsd_t *tsd, ckh_t *ckh);
44static void ckh_shrink(tsd_t *tsd, ckh_t *ckh);
43static bool ckh_grow(tsdn_t *tsdn, ckh_t *ckh);
44static void ckh_shrink(tsdn_t *tsdn, ckh_t *ckh);
45
46/******************************************************************************/
47
48/*
49 * Search bucket for key and return the cell number if found; SIZE_T_MAX
50 * otherwise.
51 */
52JEMALLOC_INLINE_C size_t

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

239 nins++;
240 }
241 }
242
243 return (false);
244}
245
246static bool
45
46/******************************************************************************/
47
48/*
49 * Search bucket for key and return the cell number if found; SIZE_T_MAX
50 * otherwise.
51 */
52JEMALLOC_INLINE_C size_t

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

239 nins++;
240 }
241 }
242
243 return (false);
244}
245
246static bool
247ckh_grow(tsd_t *tsd, ckh_t *ckh)
247ckh_grow(tsdn_t *tsdn, ckh_t *ckh)
248{
249 bool ret;
250 ckhc_t *tab, *ttab;
251 unsigned lg_prevbuckets, lg_curcells;
252
253#ifdef CKH_COUNT
254 ckh->ngrows++;
255#endif

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

265 size_t usize;
266
267 lg_curcells++;
268 usize = sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE);
269 if (unlikely(usize == 0 || usize > HUGE_MAXCLASS)) {
270 ret = true;
271 goto label_return;
272 }
248{
249 bool ret;
250 ckhc_t *tab, *ttab;
251 unsigned lg_prevbuckets, lg_curcells;
252
253#ifdef CKH_COUNT
254 ckh->ngrows++;
255#endif

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

265 size_t usize;
266
267 lg_curcells++;
268 usize = sa2u(sizeof(ckhc_t) << lg_curcells, CACHELINE);
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);
273 tab = (ckhc_t *)ipallocztm(tsdn, usize, CACHELINE, true, NULL,
274 true, arena_ichoose(tsdn, 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)) {
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, true);
286 idalloctm(tsdn, tab, NULL, 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, true);
291 idalloctm(tsdn, ckh->tab, NULL, 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
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)
302ckh_shrink(tsdn_t *tsdn, ckh_t *ckh)
303{
304 ckhc_t *tab, *ttab;
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);
315 if (unlikely(usize == 0 || usize > HUGE_MAXCLASS))
316 return;
303{
304 ckhc_t *tab, *ttab;
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);
315 if (unlikely(usize == 0 || usize > HUGE_MAXCLASS))
316 return;
317 tab = (ckhc_t *)ipallocztm(tsd, usize, CACHELINE, true, NULL, true,
318 NULL);
317 tab = (ckhc_t *)ipallocztm(tsdn, usize, CACHELINE, true, NULL, true,
318 arena_ichoose(tsdn, 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)) {
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, true);
333 idalloctm(tsdn, tab, NULL, 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, true);
341 idalloctm(tsdn, ckh->tab, NULL, true, true);
342 ckh->tab = tab;
343 ckh->lg_curbuckets = lg_prevbuckets;
344#ifdef CKH_COUNT
345 ckh->nshrinkfails++;
346#endif
347}
348
349bool
342 ckh->tab = tab;
343 ckh->lg_curbuckets = lg_prevbuckets;
344#ifdef CKH_COUNT
345 ckh->nshrinkfails++;
346#endif
347}
348
349bool
350ckh_new(tsd_t *tsd, ckh_t *ckh, size_t minitems, ckh_hash_t *hash,
350ckh_new(tsdn_t *tsdn, ckh_t *ckh, size_t minitems, ckh_hash_t *hash,
351 ckh_keycomp_t *keycomp)
352{
353 bool ret;
354 size_t mincells, usize;
355 unsigned lg_mincells;
356
357 assert(minitems > 0);
358 assert(hash != NULL);

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

386 ckh->hash = hash;
387 ckh->keycomp = keycomp;
388
389 usize = sa2u(sizeof(ckhc_t) << lg_mincells, CACHELINE);
390 if (unlikely(usize == 0 || usize > HUGE_MAXCLASS)) {
391 ret = true;
392 goto label_return;
393 }
351 ckh_keycomp_t *keycomp)
352{
353 bool ret;
354 size_t mincells, usize;
355 unsigned lg_mincells;
356
357 assert(minitems > 0);
358 assert(hash != NULL);

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

386 ckh->hash = hash;
387 ckh->keycomp = keycomp;
388
389 usize = sa2u(sizeof(ckhc_t) << lg_mincells, CACHELINE);
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);
394 ckh->tab = (ckhc_t *)ipallocztm(tsdn, usize, CACHELINE, true, NULL,
395 true, arena_ichoose(tsdn, NULL));
396 if (ckh->tab == NULL) {
397 ret = true;
398 goto label_return;
399 }
400
401 ret = false;
402label_return:
403 return (ret);
404}
405
406void
396 if (ckh->tab == NULL) {
397 ret = true;
398 goto label_return;
399 }
400
401 ret = false;
402label_return:
403 return (ret);
404}
405
406void
407ckh_delete(tsd_t *tsd, ckh_t *ckh)
407ckh_delete(tsdn_t *tsdn, ckh_t *ckh)
408{
409
410 assert(ckh != NULL);
411
412#ifdef CKH_VERBOSE
413 malloc_printf(
414 "%s(%p): ngrows: %"FMTu64", nshrinks: %"FMTu64","
415 " nshrinkfails: %"FMTu64", ninserts: %"FMTu64","
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
408{
409
410 assert(ckh != NULL);
411
412#ifdef CKH_VERBOSE
413 malloc_printf(
414 "%s(%p): ngrows: %"FMTu64", nshrinks: %"FMTu64","
415 " nshrinkfails: %"FMTu64", ninserts: %"FMTu64","
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, true);
424 idalloctm(tsdn, ckh->tab, NULL, true, true);
425 if (config_debug)
425 if (config_debug)
426 memset(ckh, 0x5a, sizeof(ckh_t));
426 memset(ckh, JEMALLOC_FREE_JUNK, sizeof(ckh_t));
427}
428
429size_t
430ckh_count(ckh_t *ckh)
431{
432
433 assert(ckh != NULL);
434

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

451 return (false);
452 }
453 }
454
455 return (true);
456}
457
458bool
427}
428
429size_t
430ckh_count(ckh_t *ckh)
431{
432
433 assert(ckh != NULL);
434

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

451 return (false);
452 }
453 }
454
455 return (true);
456}
457
458bool
459ckh_insert(tsd_t *tsd, ckh_t *ckh, const void *key, const void *data)
459ckh_insert(tsdn_t *tsdn, ckh_t *ckh, const void *key, const void *data)
460{
461 bool ret;
462
463 assert(ckh != NULL);
464 assert(ckh_search(ckh, key, NULL, NULL));
465
466#ifdef CKH_COUNT
467 ckh->ninserts++;
468#endif
469
470 while (ckh_try_insert(ckh, &key, &data)) {
460{
461 bool ret;
462
463 assert(ckh != NULL);
464 assert(ckh_search(ckh, key, NULL, NULL));
465
466#ifdef CKH_COUNT
467 ckh->ninserts++;
468#endif
469
470 while (ckh_try_insert(ckh, &key, &data)) {
471 if (ckh_grow(tsd, ckh)) {
471 if (ckh_grow(tsdn, ckh)) {
472 ret = true;
473 goto label_return;
474 }
475 }
476
477 ret = false;
478label_return:
479 return (ret);
480}
481
482bool
472 ret = true;
473 goto label_return;
474 }
475 }
476
477 ret = false;
478label_return:
479 return (ret);
480}
481
482bool
483ckh_remove(tsd_t *tsd, ckh_t *ckh, const void *searchkey, void **key,
483ckh_remove(tsdn_t *tsdn, ckh_t *ckh, const void *searchkey, void **key,
484 void **data)
485{
486 size_t cell;
487
488 assert(ckh != NULL);
489
490 cell = ckh_isearch(ckh, searchkey);
491 if (cell != SIZE_T_MAX) {

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

497 ckh->tab[cell].data = NULL; /* Not necessary. */
498
499 ckh->count--;
500 /* Try to halve the table if it is less than 1/4 full. */
501 if (ckh->count < (ZU(1) << (ckh->lg_curbuckets
502 + LG_CKH_BUCKET_CELLS - 2)) && ckh->lg_curbuckets
503 > ckh->lg_minbuckets) {
504 /* Ignore error due to OOM. */
484 void **data)
485{
486 size_t cell;
487
488 assert(ckh != NULL);
489
490 cell = ckh_isearch(ckh, searchkey);
491 if (cell != SIZE_T_MAX) {

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

497 ckh->tab[cell].data = NULL; /* Not necessary. */
498
499 ckh->count--;
500 /* Try to halve the table if it is less than 1/4 full. */
501 if (ckh->count < (ZU(1) << (ckh->lg_curbuckets
502 + LG_CKH_BUCKET_CELLS - 2)) && ckh->lg_curbuckets
503 > ckh->lg_minbuckets) {
504 /* Ignore error due to OOM. */
505 ckh_shrink(tsd, ckh);
505 ckh_shrink(tsdn, ckh);
506 }
507
508 return (false);
509 }
510
511 return (true);
512}
513

--- 55 unchanged lines hidden --- 		506 }
507
508 return (false);
509 }
510
511 return (true);
512}
513

--- 55 unchanged lines hidden ---