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) in ckh_bucket_search() argument
59 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; in ckh_bucket_search()
60 if (cell->key != NULL && ckh->keycomp(key, cell->key)) in ckh_bucket_search()
71 ckh_isearch(ckh_t *ckh, const void *key) in ckh_isearch() argument
75 assert(ckh != NULL); in ckh_isearch()
77 ckh->hash(key, hashes); in ckh_isearch()
80 bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1); in ckh_isearch()
81 cell = ckh_bucket_search(ckh, bucket, key); in ckh_isearch()
86 bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); in ckh_isearch()
87 cell = ckh_bucket_search(ckh, bucket, key); in ckh_isearch()
92 ckh_try_bucket_insert(ckh_t *ckh, size_t bucket, const void *key, in ckh_try_bucket_insert() argument
102 offset = (unsigned)prng_lg_range_u64(&ckh->prng_state, in ckh_try_bucket_insert()
105 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + in ckh_try_bucket_insert()
110 ckh->count++; in ckh_try_bucket_insert()
125 ckh_evict_reloc_insert(ckh_t *ckh, size_t argbucket, void const **argkey, in ckh_evict_reloc_insert() argument
145 i = (unsigned)prng_lg_range_u64(&ckh->prng_state, in ckh_evict_reloc_insert()
147 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; in ckh_evict_reloc_insert()
156 ckh->nrelocs++; in ckh_evict_reloc_insert()
160 ckh->hash(key, hashes); in ckh_evict_reloc_insert()
161 tbucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); in ckh_evict_reloc_insert()
163 tbucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) in ckh_evict_reloc_insert()
190 if (!ckh_try_bucket_insert(ckh, bucket, key, data)) in ckh_evict_reloc_insert()
196 ckh_try_insert(ckh_t *ckh, void const**argkey, void const**argdata) in ckh_try_insert() argument
202 ckh->hash(key, hashes); in ckh_try_insert()
205 bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1); in ckh_try_insert()
206 if (!ckh_try_bucket_insert(ckh, bucket, key, data)) in ckh_try_insert()
210 bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); in ckh_try_insert()
211 if (!ckh_try_bucket_insert(ckh, bucket, key, data)) in ckh_try_insert()
217 return (ckh_evict_reloc_insert(ckh, bucket, argkey, argdata)); in ckh_try_insert()
225 ckh_rebuild(ckh_t *ckh, ckhc_t *aTab) in ckh_rebuild() argument
230 count = ckh->count; in ckh_rebuild()
231 ckh->count = 0; in ckh_rebuild()
236 if (ckh_try_insert(ckh, &key, &data)) { in ckh_rebuild()
237 ckh->count = count; in ckh_rebuild()
248 ckh_grow(tsd_t *tsd, ckh_t *ckh) in ckh_grow() argument
255 ckh->ngrows++; in ckh_grow()
263 lg_prevbuckets = ckh->lg_curbuckets; in ckh_grow()
264 lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS; in ckh_grow()
281 ttab = ckh->tab; in ckh_grow()
282 ckh->tab = tab; in ckh_grow()
284 ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; in ckh_grow()
286 if (!ckh_rebuild(ckh, tab)) { in ckh_grow()
292 idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, true, true); in ckh_grow()
293 ckh->tab = tab; in ckh_grow()
294 ckh->lg_curbuckets = lg_prevbuckets; in ckh_grow()
303 ckh_shrink(tsd_t *tsd, ckh_t *ckh) in ckh_shrink() argument
313 lg_prevbuckets = ckh->lg_curbuckets; in ckh_shrink()
314 lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS - 1; in ckh_shrink()
328 ttab = ckh->tab; in ckh_shrink()
329 ckh->tab = tab; in ckh_shrink()
331 ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; in ckh_shrink()
333 if (!ckh_rebuild(ckh, tab)) { in ckh_shrink()
336 ckh->nshrinks++; in ckh_shrink()
342 idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, true, true); in ckh_shrink()
343 ckh->tab = tab; in ckh_shrink()
344 ckh->lg_curbuckets = lg_prevbuckets; in ckh_shrink()
346 ckh->nshrinkfails++; in ckh_shrink()
351 ckh_new(tsd_t *tsd, ckh_t *ckh, size_t minitems, ckh_hash_t *hash, in ckh_new() argument
363 ckh->ngrows = 0; in ckh_new()
364 ckh->nshrinks = 0; in ckh_new()
365 ckh->nshrinkfails = 0; in ckh_new()
366 ckh->ninserts = 0; in ckh_new()
367 ckh->nrelocs = 0; in ckh_new()
369 ckh->prng_state = 42; /* Value doesn't really matter. */ in ckh_new()
370 ckh->count = 0; in ckh_new()
385 ckh->lg_minbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; in ckh_new()
386 ckh->lg_curbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; in ckh_new()
387 ckh->hash = hash; in ckh_new()
388 ckh->keycomp = keycomp; in ckh_new()
395 ckh->tab = (ckhc_t *)ipallocztm(tsd_tsdn(tsd), usize, CACHELINE, true, in ckh_new()
397 if (ckh->tab == NULL) { in ckh_new()
408 ckh_delete(tsd_t *tsd, ckh_t *ckh) in ckh_delete() argument
411 assert(ckh != NULL); in ckh_delete()
417 " nrelocs: %"FMTu64"\n", __func__, ckh, in ckh_delete()
418 (unsigned long long)ckh->ngrows, in ckh_delete()
419 (unsigned long long)ckh->nshrinks, in ckh_delete()
420 (unsigned long long)ckh->nshrinkfails, in ckh_delete()
421 (unsigned long long)ckh->ninserts, in ckh_delete()
422 (unsigned long long)ckh->nrelocs); in ckh_delete()
425 idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, true, true); in ckh_delete()
427 memset(ckh, JEMALLOC_FREE_JUNK, sizeof(ckh_t)); in ckh_delete()
431 ckh_count(ckh_t *ckh) in ckh_count() argument
434 assert(ckh != NULL); in ckh_count()
436 return (ckh->count); in ckh_count()
440 ckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data) in ckh_iter() argument
444 for (i = *tabind, ncells = (ZU(1) << (ckh->lg_curbuckets + in ckh_iter()
446 if (ckh->tab[i].key != NULL) { in ckh_iter()
448 *key = (void *)ckh->tab[i].key; in ckh_iter()
450 *data = (void *)ckh->tab[i].data; in ckh_iter()
460 ckh_insert(tsd_t *tsd, ckh_t *ckh, const void *key, const void *data) in ckh_insert() argument
464 assert(ckh != NULL); in ckh_insert()
465 assert(ckh_search(ckh, key, NULL, NULL)); in ckh_insert()
468 ckh->ninserts++; in ckh_insert()
471 while (ckh_try_insert(ckh, &key, &data)) { in ckh_insert()
472 if (ckh_grow(tsd, ckh)) { in ckh_insert()
484 ckh_remove(tsd_t *tsd, ckh_t *ckh, const void *searchkey, void **key, in ckh_remove() argument
489 assert(ckh != NULL); in ckh_remove()
491 cell = ckh_isearch(ckh, searchkey); in ckh_remove()
494 *key = (void *)ckh->tab[cell].key; in ckh_remove()
496 *data = (void *)ckh->tab[cell].data; in ckh_remove()
497 ckh->tab[cell].key = NULL; in ckh_remove()
498 ckh->tab[cell].data = NULL; /* Not necessary. */ in ckh_remove()
500 ckh->count--; in ckh_remove()
502 if (ckh->count < (ZU(1) << (ckh->lg_curbuckets in ckh_remove()
503 + LG_CKH_BUCKET_CELLS - 2)) && ckh->lg_curbuckets in ckh_remove()
504 > ckh->lg_minbuckets) { in ckh_remove()
506 ckh_shrink(tsd, ckh); in ckh_remove()
516 ckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data) in ckh_search() argument
520 assert(ckh != NULL); in ckh_search()
522 cell = ckh_isearch(ckh, searchkey); in ckh_search()
525 *key = (void *)ckh->tab[cell].key; in ckh_search()
527 *data = (void *)ckh->tab[cell].data; in ckh_search()