Lines Matching refs:ckh
43 static bool ckh_grow(tsd_t *tsd, ckh_t *ckh);
44 static void ckh_shrink(tsd_t *tsd, ckh_t *ckh);
53 ckh_bucket_search(ckh_t *ckh, size_t bucket, const void *key)
59 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i];
60 if (cell->key != NULL && ckh->keycomp(key, cell->key))
71 ckh_isearch(ckh_t *ckh, const void *key)
75 assert(ckh != NULL);
77 ckh->hash(key, hashes);
80 bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1);
81 cell = ckh_bucket_search(ckh, bucket, key);
86 bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1);
87 cell = ckh_bucket_search(ckh, bucket, key);
92 ckh_try_bucket_insert(ckh_t *ckh, size_t bucket, const void *key,
102 offset = (unsigned)prng_lg_range_u64(&ckh->prng_state,
105 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) +
110 ckh->count++;
125 ckh_evict_reloc_insert(ckh_t *ckh, size_t argbucket, void const **argkey,
145 i = (unsigned)prng_lg_range_u64(&ckh->prng_state,
147 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i];
156 ckh->nrelocs++;
160 ckh->hash(key, hashes);
161 tbucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1);
163 tbucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets)
190 if (!ckh_try_bucket_insert(ckh, bucket, key, data))
196 ckh_try_insert(ckh_t *ckh, void const**argkey, void const**argdata)
202 ckh->hash(key, hashes);
205 bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1);
206 if (!ckh_try_bucket_insert(ckh, bucket, key, data))
210 bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1);
211 if (!ckh_try_bucket_insert(ckh, bucket, key, data))
217 return (ckh_evict_reloc_insert(ckh, bucket, argkey, argdata));
225 ckh_rebuild(ckh_t *ckh, ckhc_t *aTab)
230 count = ckh->count;
231 ckh->count = 0;
236 if (ckh_try_insert(ckh, &key, &data)) {
237 ckh->count = count;
248 ckh_grow(tsd_t *tsd, ckh_t *ckh)
255 ckh->ngrows++;
263 lg_prevbuckets = ckh->lg_curbuckets;
264 lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS;
281 ttab = ckh->tab;
282 ckh->tab = tab;
284 ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS;
286 if (!ckh_rebuild(ckh, tab)) {
293 idalloctm(tsd_tsdn(tsd), iealloc(tsd_tsdn(tsd), ckh->tab),
294 ckh->tab, NULL, true, true);
295 ckh->tab = tab;
296 ckh->lg_curbuckets = lg_prevbuckets;
305 ckh_shrink(tsd_t *tsd, ckh_t *ckh)
315 lg_prevbuckets = ckh->lg_curbuckets;
316 lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS - 1;
330 ttab = ckh->tab;
331 ckh->tab = tab;
333 ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS;
335 if (!ckh_rebuild(ckh, tab)) {
339 ckh->nshrinks++;
345 idalloctm(tsd_tsdn(tsd), iealloc(tsd_tsdn(tsd), ckh->tab), ckh->tab,
347 ckh->tab = tab;
348 ckh->lg_curbuckets = lg_prevbuckets;
350 ckh->nshrinkfails++;
355 ckh_new(tsd_t *tsd, ckh_t *ckh, size_t minitems, ckh_hash_t *hash,
367 ckh->ngrows = 0;
368 ckh->nshrinks = 0;
369 ckh->nshrinkfails = 0;
370 ckh->ninserts = 0;
371 ckh->nrelocs = 0;
373 ckh->prng_state = 42; /* Value doesn't really matter. */
374 ckh->count = 0;
389 ckh->lg_minbuckets = lg_mincells - LG_CKH_BUCKET_CELLS;
390 ckh->lg_curbuckets = lg_mincells - LG_CKH_BUCKET_CELLS;
391 ckh->hash = hash;
392 ckh->keycomp = keycomp;
399 ckh->tab = (ckhc_t *)ipallocztm(tsd_tsdn(tsd), usize, CACHELINE, true,
401 if (ckh->tab == NULL) {
412 ckh_delete(tsd_t *tsd, ckh_t *ckh)
414 assert(ckh != NULL);
420 " nrelocs: %"FMTu64"\n", __func__, ckh,
421 (unsigned long long)ckh->ngrows,
422 (unsigned long long)ckh->nshrinks,
423 (unsigned long long)ckh->nshrinkfails,
424 (unsigned long long)ckh->ninserts,
425 (unsigned long long)ckh->nrelocs);
428 idalloctm(tsd_tsdn(tsd), iealloc(tsd_tsdn(tsd), ckh->tab), ckh->tab,
431 memset(ckh, JEMALLOC_FREE_JUNK, sizeof(ckh_t));
435 ckh_count(ckh_t *ckh)
437 assert(ckh != NULL);
439 return (ckh->count);
443 ckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data)
447 for (i = *tabind, ncells = (ZU(1) << (ckh->lg_curbuckets +
449 if (ckh->tab[i].key != NULL) {
451 *key = (void *)ckh->tab[i].key;
453 *data = (void *)ckh->tab[i].data;
463 ckh_insert(tsd_t *tsd, ckh_t *ckh, const void *key, const void *data)
467 assert(ckh != NULL);
468 assert(ckh_search(ckh, key, NULL, NULL));
471 ckh->ninserts++;
474 while (ckh_try_insert(ckh, &key, &data)) {
475 if (ckh_grow(tsd, ckh)) {
487 ckh_remove(tsd_t *tsd, ckh_t *ckh, const void *searchkey, void **key,
492 assert(ckh != NULL);
494 cell = ckh_isearch(ckh, searchkey);
497 *key = (void *)ckh->tab[cell].key;
499 *data = (void *)ckh->tab[cell].data;
500 ckh->tab[cell].key = NULL;
501 ckh->tab[cell].data = NULL; /* Not necessary. */
503 ckh->count--;
505 if (ckh->count < (ZU(1) << (ckh->lg_curbuckets
506 + LG_CKH_BUCKET_CELLS - 2)) && ckh->lg_curbuckets
507 > ckh->lg_minbuckets) {
509 ckh_shrink(tsd, ckh);
519 ckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data)
523 assert(ckh != NULL);
525 cell = ckh_isearch(ckh, searchkey);
528 *key = (void *)ckh->tab[cell].key;
530 *data = (void *)ckh->tab[cell].data;