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 prng32(offset, LG_CKH_BUCKET_CELLS, ckh->prng_state, CKH_A, CKH_C); in ckh_try_bucket_insert()
104 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + in ckh_try_bucket_insert()
109 ckh->count++; in ckh_try_bucket_insert()
124 ckh_evict_reloc_insert(ckh_t *ckh, size_t argbucket, void const **argkey, in ckh_evict_reloc_insert() argument
144 prng32(i, LG_CKH_BUCKET_CELLS, ckh->prng_state, CKH_A, CKH_C); in ckh_evict_reloc_insert()
145 cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i]; in ckh_evict_reloc_insert()
154 ckh->nrelocs++; in ckh_evict_reloc_insert()
158 ckh->hash(key, hashes); in ckh_evict_reloc_insert()
159 tbucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); in ckh_evict_reloc_insert()
161 tbucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) in ckh_evict_reloc_insert()
188 if (!ckh_try_bucket_insert(ckh, bucket, key, data)) in ckh_evict_reloc_insert()
194 ckh_try_insert(ckh_t *ckh, void const**argkey, void const**argdata) in ckh_try_insert() argument
200 ckh->hash(key, hashes); in ckh_try_insert()
203 bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1); in ckh_try_insert()
204 if (!ckh_try_bucket_insert(ckh, bucket, key, data)) in ckh_try_insert()
208 bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1); in ckh_try_insert()
209 if (!ckh_try_bucket_insert(ckh, bucket, key, data)) in ckh_try_insert()
215 return (ckh_evict_reloc_insert(ckh, bucket, argkey, argdata)); in ckh_try_insert()
223 ckh_rebuild(ckh_t *ckh, ckhc_t *aTab) in ckh_rebuild() argument
228 count = ckh->count; in ckh_rebuild()
229 ckh->count = 0; in ckh_rebuild()
234 if (ckh_try_insert(ckh, &key, &data)) { in ckh_rebuild()
235 ckh->count = count; in ckh_rebuild()
246 ckh_grow(tsd_t *tsd, ckh_t *ckh) in ckh_grow() argument
254 ckh->ngrows++; in ckh_grow()
262 lg_prevbuckets = ckh->lg_curbuckets; in ckh_grow()
263 lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS; in ckh_grow()
280 ttab = ckh->tab; in ckh_grow()
281 ckh->tab = tab; in ckh_grow()
283 ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; in ckh_grow()
285 if (!ckh_rebuild(ckh, tab)) { in ckh_grow()
291 idalloctm(tsd, ckh->tab, tcache_get(tsd, false), true); in ckh_grow()
292 ckh->tab = tab; in ckh_grow()
293 ckh->lg_curbuckets = lg_prevbuckets; in ckh_grow()
302 ckh_shrink(tsd_t *tsd, ckh_t *ckh) in ckh_shrink() argument
312 lg_prevbuckets = ckh->lg_curbuckets; in ckh_shrink()
313 lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS - 1; in ckh_shrink()
327 ttab = ckh->tab; in ckh_shrink()
328 ckh->tab = tab; in ckh_shrink()
330 ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS; in ckh_shrink()
332 if (!ckh_rebuild(ckh, tab)) { in ckh_shrink()
335 ckh->nshrinks++; in ckh_shrink()
341 idalloctm(tsd, ckh->tab, tcache_get(tsd, false), true); in ckh_shrink()
342 ckh->tab = tab; in ckh_shrink()
343 ckh->lg_curbuckets = lg_prevbuckets; in ckh_shrink()
345 ckh->nshrinkfails++; in ckh_shrink()
350 ckh_new(tsd_t *tsd, ckh_t *ckh, size_t minitems, ckh_hash_t *hash, in ckh_new() argument
362 ckh->ngrows = 0; in ckh_new()
363 ckh->nshrinks = 0; in ckh_new()
364 ckh->nshrinkfails = 0; in ckh_new()
365 ckh->ninserts = 0; in ckh_new()
366 ckh->nrelocs = 0; in ckh_new()
368 ckh->prng_state = 42; /* Value doesn't really matter. */ in ckh_new()
369 ckh->count = 0; in ckh_new()
384 ckh->lg_minbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; in ckh_new()
385 ckh->lg_curbuckets = lg_mincells - LG_CKH_BUCKET_CELLS; in ckh_new()
386 ckh->hash = hash; in ckh_new()
387 ckh->keycomp = keycomp; in ckh_new()
394 ckh->tab = (ckhc_t *)ipallocztm(tsd, usize, CACHELINE, true, NULL, true, in ckh_new()
396 if (ckh->tab == NULL) { in ckh_new()
407 ckh_delete(tsd_t *tsd, ckh_t *ckh) in ckh_delete() argument
410 assert(ckh != NULL); in ckh_delete()
416 " nrelocs: %"PRIu64"\n", __func__, ckh, in ckh_delete()
417 (unsigned long long)ckh->ngrows, in ckh_delete()
418 (unsigned long long)ckh->nshrinks, in ckh_delete()
419 (unsigned long long)ckh->nshrinkfails, in ckh_delete()
420 (unsigned long long)ckh->ninserts, in ckh_delete()
421 (unsigned long long)ckh->nrelocs); in ckh_delete()
424 idalloctm(tsd, ckh->tab, tcache_get(tsd, false), true); in ckh_delete()
426 memset(ckh, 0x5a, sizeof(ckh_t)); in ckh_delete()
430 ckh_count(ckh_t *ckh) in ckh_count() argument
433 assert(ckh != NULL); in ckh_count()
435 return (ckh->count); in ckh_count()
439 ckh_iter(ckh_t *ckh, size_t *tabind, void **key, void **data) in ckh_iter() argument
443 for (i = *tabind, ncells = (ZU(1) << (ckh->lg_curbuckets + in ckh_iter()
445 if (ckh->tab[i].key != NULL) { in ckh_iter()
447 *key = (void *)ckh->tab[i].key; in ckh_iter()
449 *data = (void *)ckh->tab[i].data; in ckh_iter()
459 ckh_insert(tsd_t *tsd, ckh_t *ckh, const void *key, const void *data) in ckh_insert() argument
463 assert(ckh != NULL); in ckh_insert()
464 assert(ckh_search(ckh, key, NULL, NULL)); in ckh_insert()
467 ckh->ninserts++; in ckh_insert()
470 while (ckh_try_insert(ckh, &key, &data)) { in ckh_insert()
471 if (ckh_grow(tsd, ckh)) { in ckh_insert()
483 ckh_remove(tsd_t *tsd, ckh_t *ckh, const void *searchkey, void **key, in ckh_remove() argument
488 assert(ckh != NULL); in ckh_remove()
490 cell = ckh_isearch(ckh, searchkey); in ckh_remove()
493 *key = (void *)ckh->tab[cell].key; in ckh_remove()
495 *data = (void *)ckh->tab[cell].data; in ckh_remove()
496 ckh->tab[cell].key = NULL; in ckh_remove()
497 ckh->tab[cell].data = NULL; /* Not necessary. */ in ckh_remove()
499 ckh->count--; in ckh_remove()
501 if (ckh->count < (ZU(1) << (ckh->lg_curbuckets in ckh_remove()
502 + LG_CKH_BUCKET_CELLS - 2)) && ckh->lg_curbuckets in ckh_remove()
503 > ckh->lg_minbuckets) { in ckh_remove()
505 ckh_shrink(tsd, ckh); in ckh_remove()
515 ckh_search(ckh_t *ckh, const void *searchkey, void **key, void **data) in ckh_search() argument
519 assert(ckh != NULL); in ckh_search()
521 cell = ckh_isearch(ckh, searchkey); in ckh_search()
524 *key = (void *)ckh->tab[cell].key; in ckh_search()
526 *data = (void *)ckh->tab[cell].data; in ckh_search()