jemalloc/src/ckh.c

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;