Lines Matching refs:ckh
53 static bool ckh_grow(tsd_t *tsd, ckh_t *ckh);
54 static void ckh_shrink(tsd_t *tsd, ckh_t *ckh);
63 ckh_bucket_search(ckh_t *ckh, size_t bucket, const void *key) { in ckh_bucket_search() argument
68 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; in ckh_bucket_search()
69 if (cell->key != NULL && ckh->keycomp(key, cell->key)) { in ckh_bucket_search()
81 ckh_isearch(ckh_t *ckh, const void *key) { in ckh_isearch() argument
84 assert(ckh != NULL); in ckh_isearch()
86 ckh->hash(key, hashes); in ckh_isearch()
89 bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1); in ckh_isearch()
90 cell = ckh_bucket_search(ckh, bucket, key); in ckh_isearch()
96 bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); in ckh_isearch()
97 cell = ckh_bucket_search(ckh, bucket, key); in ckh_isearch()
102 ckh_try_bucket_insert(ckh_t *ckh, size_t bucket, const void *key, in ckh_try_bucket_insert() argument
111 offset = (unsigned)prng_lg_range_u64(&ckh->prng_state, in ckh_try_bucket_insert()
114 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + in ckh_try_bucket_insert()
119 ckh->count++; in ckh_try_bucket_insert()
134 ckh_evict_reloc_insert(ckh_t *ckh, size_t argbucket, void const **argkey, in ckh_evict_reloc_insert() argument
153 i = (unsigned)prng_lg_range_u64(&ckh->prng_state, in ckh_evict_reloc_insert()
155 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; in ckh_evict_reloc_insert()
164 ckh->nrelocs++; in ckh_evict_reloc_insert()
168 ckh->hash(key, hashes); in ckh_evict_reloc_insert()
169 tbucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); in ckh_evict_reloc_insert()
171 tbucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) in ckh_evict_reloc_insert()
198 if (!ckh_try_bucket_insert(ckh, bucket, key, data)) { in ckh_evict_reloc_insert()
205 ckh_try_insert(ckh_t *ckh, void const**argkey, void const**argdata) { in ckh_try_insert() argument
210 ckh->hash(key, hashes); in ckh_try_insert()
213 bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1); in ckh_try_insert()
214 if (!ckh_try_bucket_insert(ckh, bucket, key, data)) { in ckh_try_insert()
219 bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); in ckh_try_insert()
220 if (!ckh_try_bucket_insert(ckh, bucket, key, data)) { in ckh_try_insert()
227 return ckh_evict_reloc_insert(ckh, bucket, argkey, argdata); in ckh_try_insert()
235 ckh_rebuild(ckh_t *ckh, ckhc_t *aTab) { in ckh_rebuild() argument
239 count = ckh->count; in ckh_rebuild()
240 ckh->count = 0; in ckh_rebuild()
245 if (ckh_try_insert(ckh, &key, &data)) { in ckh_rebuild()
246 ckh->count = count; in ckh_rebuild()
257 ckh_grow(tsd_t *tsd, ckh_t *ckh) { in ckh_grow() argument
263 ckh->ngrows++; in ckh_grow()
271 lg_prevbuckets = ckh->lg_curbuckets; in ckh_grow()
272 lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS; in ckh_grow()
289 ttab = ckh->tab; in ckh_grow()
290 ckh->tab = tab; in ckh_grow()
292 ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; in ckh_grow()
294 if (!ckh_rebuild(ckh, tab)) { in ckh_grow()
300 idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, NULL, true, true); in ckh_grow()
301 ckh->tab = tab; in ckh_grow()
302 ckh->lg_curbuckets = lg_prevbuckets; in ckh_grow()
311 ckh_shrink(tsd_t *tsd, ckh_t *ckh) { in ckh_shrink() argument
320 lg_prevbuckets = ckh->lg_curbuckets; in ckh_shrink()
321 lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS - 1; in ckh_shrink()
336 ttab = ckh->tab; in ckh_shrink()
337 ckh->tab = tab; in ckh_shrink()
339 ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; in ckh_shrink()
341 if (!ckh_rebuild(ckh, tab)) { in ckh_shrink()
344 ckh->nshrinks++; in ckh_shrink()
350 idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, NULL, true, true); in ckh_shrink()
351 ckh->tab = tab; in ckh_shrink()
352 ckh->lg_curbuckets = lg_prevbuckets; in ckh_shrink()
354 ckh->nshrinkfails++; in ckh_shrink()
359 ckh_new(tsd_t *tsd, ckh_t *ckh, size_t minitems, ckh_hash_t *hash, in ckh_new() argument
370 ckh->ngrows = 0; in ckh_new()
371 ckh->nshrinks = 0; in ckh_new()
372 ckh->nshrinkfails = 0; in ckh_new()
373 ckh->ninserts = 0; in ckh_new()
374 ckh->nrelocs = 0; in ckh_new()
376 ckh->prng_state = 42; /* Value doesn't really matter. */ in ckh_new()
377 ckh->count = 0; in ckh_new()
393 ckh->lg_minbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; in ckh_new()
394 ckh->lg_curbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; in ckh_new()
395 ckh->hash = hash; in ckh_new()
396 ckh->keycomp = keycomp; in ckh_new()
403 ckh->tab = (ckhc_t *)ipallocztm(tsd_tsdn(tsd), usize, CACHELINE, true, in ckh_new()
405 if (ckh->tab == NULL) { in ckh_new()
416 ckh_delete(tsd_t *tsd, ckh_t *ckh) { in ckh_delete() argument
417 assert(ckh != NULL); in ckh_delete()
423 " nrelocs: %"FMTu64"\n", __func__, ckh, in ckh_delete()
424 (unsigned long long)ckh->ngrows, in ckh_delete()
425 (unsigned long long)ckh->nshrinks, in ckh_delete()
426 (unsigned long long)ckh->nshrinkfails, in ckh_delete()
427 (unsigned long long)ckh->ninserts, in ckh_delete()
428 (unsigned long long)ckh->nrelocs); in ckh_delete()
431 idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, NULL, true, true); in ckh_delete()
433 memset(ckh, JEMALLOC_FREE_JUNK, sizeof(ckh_t)); in ckh_delete()
438 ckh_count(ckh_t *ckh) { in ckh_count() argument
439 assert(ckh != NULL); in ckh_count()
441 return ckh->count; in ckh_count()
445 ckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data) { in ckh_iter() argument
448 for (i = *tabind, ncells = (ZU(1) << (ckh->lg_curbuckets + in ckh_iter()
450 if (ckh->tab[i].key != NULL) { in ckh_iter()
452 *key = (void *)ckh->tab[i].key; in ckh_iter()
455 *data = (void *)ckh->tab[i].data; in ckh_iter()
466 ckh_insert(tsd_t *tsd, ckh_t *ckh, const void *key, const void *data) { in ckh_insert() argument
469 assert(ckh != NULL); in ckh_insert()
470 assert(ckh_search(ckh, key, NULL, NULL)); in ckh_insert()
473 ckh->ninserts++; in ckh_insert()
476 while (ckh_try_insert(ckh, &key, &data)) { in ckh_insert()
477 if (ckh_grow(tsd, ckh)) { in ckh_insert()
489 ckh_remove(tsd_t *tsd, ckh_t *ckh, const void *searchkey, void **key, in ckh_remove() argument
493 assert(ckh != NULL); in ckh_remove()
495 cell = ckh_isearch(ckh, searchkey); in ckh_remove()
498 *key = (void *)ckh->tab[cell].key; in ckh_remove()
501 *data = (void *)ckh->tab[cell].data; in ckh_remove()
503 ckh->tab[cell].key = NULL; in ckh_remove()
504 ckh->tab[cell].data = NULL; /* Not necessary. */ in ckh_remove()
506 ckh->count--; in ckh_remove()
508 if (ckh->count < (ZU(1) << (ckh->lg_curbuckets in ckh_remove()
509 + LG_CKH_BUCKET_CELLS - 2)) && ckh->lg_curbuckets in ckh_remove()
510 > ckh->lg_minbuckets) { in ckh_remove()
512 ckh_shrink(tsd, ckh); in ckh_remove()
522 ckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data) { in ckh_search() argument
525 assert(ckh != NULL); in ckh_search()
527 cell = ckh_isearch(ckh, searchkey); in ckh_search()
530 *key = (void *)ckh->tab[cell].key; in ckh_search()
533 *data = (void *)ckh->tab[cell].data; in ckh_search()