9  *     51(2):122-144.
26  *   --------+-------+-------+-------+-------+
29  *         3 | 0.91  | 0.97  | 0.98  | 0.999 |
33  * line.  So, on 32- and 64-bit systems, we use (8,2) and (4,2) cuckoo hashing,
51 /* Function prototypes for non-inline static functions. */
59  * Search bucket for key and return the cell number if found; SIZE_T_MAX
64 	ckhc_t *cell;  in ckh_bucket_search()  local
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()
78  * Search table for key and return cell number if found; SIZE_T_MAX otherwise.
82 	size_t hashes[2], bucket, cell;  in ckh_isearch()  local
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()
91 	if (cell != SIZE_T_MAX) {  in ckh_isearch()
92 		return cell;  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()
98 	return cell;  in ckh_isearch()
104 	ckhc_t *cell;  in ckh_try_bucket_insert()  local
109 	 * The randomness avoids worst-case search overhead as buckets fill up.  in ckh_try_bucket_insert()
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()
115 		    ((i + offset) & ((ZU(1) << LG_CKH_BUCKET_CELLS) - 1))];  in ckh_try_bucket_insert()
116 		if (cell->key == NULL) {  in ckh_try_bucket_insert()
117 			cell->key = key;  in ckh_try_bucket_insert()
118 			cell->data = data;  in ckh_try_bucket_insert()
119 			ckh->count++;  in ckh_try_bucket_insert()
137 	ckhc_t *cell;  in ckh_evict_reloc_insert()  local
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()
156 		assert(cell->key != NULL);  in ckh_evict_reloc_insert()
158 		/* Swap cell->{key,data} and {key,data} (evict). */  in ckh_evict_reloc_insert()
159 		tkey = cell->key; tdata = cell->data;  in ckh_evict_reloc_insert()
160 		cell->key = key; cell->data = data;  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()
172 			    - 1);  in ckh_evict_reloc_insert()
177 			 * during iteration, assuming pseudo-random item  in ckh_evict_reloc_insert()
210 	ckh->hash(key, hashes);  in ckh_try_insert()
213 	bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1);  in ckh_try_insert()
219 	bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1);  in ckh_try_insert()
239 	count = ckh->count;  in ckh_rebuild()
240 	ckh->count = 0;  in ckh_rebuild()
246 				ckh->count = count;  in ckh_rebuild()
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()
290 		ttab = ckh->tab;  in ckh_grow()
291 		ckh->tab = tab;  in ckh_grow()
293 		ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS;  in ckh_grow()
301 		idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, NULL, true, true);  in ckh_grow()
302 		ckh->tab = tab;  in ckh_grow()
303 		ckh->lg_curbuckets = lg_prevbuckets;  in ckh_grow()
321 	lg_prevbuckets = ckh->lg_curbuckets;  in ckh_shrink()
322 	lg_curcells = ckh->lg_curbuckets + LG_CKH_BUCKET_CELLS - 1;  in ckh_shrink()
337 	ttab = ckh->tab;  in ckh_shrink()
338 	ckh->tab = tab;  in ckh_shrink()
340 	ckh->lg_curbuckets = lg_curcells - LG_CKH_BUCKET_CELLS;  in ckh_shrink()
345 		ckh->nshrinks++;  in ckh_shrink()
351 	idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, NULL, true, true);  in ckh_shrink()
352 	ckh->tab = tab;  in ckh_shrink()
353 	ckh->lg_curbuckets = lg_prevbuckets;  in ckh_shrink()
355 	ckh->nshrinkfails++;  in ckh_shrink()
371 	ckh->ngrows = 0;  in ckh_new()
372 	ckh->nshrinks = 0;  in ckh_new()
373 	ckh->nshrinkfails = 0;  in ckh_new()
374 	ckh->ninserts = 0;  in ckh_new()
375 	ckh->nrelocs = 0;  in ckh_new()
377 	ckh->prng_state = 42; /* Value doesn't really matter. */  in ckh_new()
378 	ckh->count = 0;  in ckh_new()
388 	mincells = ((minitems + (3 - (minitems % 3))) / 3) << 2;  in ckh_new()
394 	ckh->lg_minbuckets = lg_mincells - LG_CKH_BUCKET_CELLS;  in ckh_new()
395 	ckh->lg_curbuckets = lg_mincells - LG_CKH_BUCKET_CELLS;  in ckh_new()
396 	ckh->hash = hash;  in ckh_new()
397 	ckh->keycomp = keycomp;  in ckh_new()
404 	ckh->tab = (ckhc_t *)ipallocztm(tsd_tsdn(tsd), usize, CACHELINE, true,  in ckh_new()
406 	if (ckh->tab == NULL) {  in ckh_new()
425 	    (unsigned long long)ckh->ngrows,  in ckh_delete()
426 	    (unsigned long long)ckh->nshrinks,  in ckh_delete()
427 	    (unsigned long long)ckh->nshrinkfails,  in ckh_delete()
428 	    (unsigned long long)ckh->ninserts,  in ckh_delete()
429 	    (unsigned long long)ckh->nrelocs);  in ckh_delete()
432 	idalloctm(tsd_tsdn(tsd), ckh->tab, NULL, NULL, true, true);  in ckh_delete()
442 	return ckh->count;  in ckh_count()
449 	for (i = *tabind, ncells = (ZU(1) << (ckh->lg_curbuckets +  in ckh_iter()
451 		if (ckh->tab[i].key != NULL) {  in ckh_iter()
453 				*key = (void *)ckh->tab[i].key;  in ckh_iter()
456 				*data = (void *)ckh->tab[i].data;  in ckh_iter()
474 	ckh->ninserts++;  in ckh_insert()
492 	size_t cell;  in ckh_remove()  local
496 	cell = ckh_isearch(ckh, searchkey);  in ckh_remove()
497 	if (cell != SIZE_T_MAX) {  in ckh_remove()
499 			*key = (void *)ckh->tab[cell].key;  in ckh_remove()
502 			*data = (void *)ckh->tab[cell].data;  in ckh_remove()
504 		ckh->tab[cell].key = NULL;  in ckh_remove()
505 		ckh->tab[cell].data = NULL; /* Not necessary. */  in ckh_remove()
507 		ckh->count--;  in ckh_remove()
509 		if (ckh->count < (ZU(1) << (ckh->lg_curbuckets  in ckh_remove()
510 		    + LG_CKH_BUCKET_CELLS - 2)) && ckh->lg_curbuckets  in ckh_remove()
511 		    > ckh->lg_minbuckets) {  in ckh_remove()
524 	size_t cell;  in ckh_search()  local
528 	cell = ckh_isearch(ckh, searchkey);  in ckh_search()
529 	if (cell != SIZE_T_MAX) {  in ckh_search()
531 			*key = (void *)ckh->tab[cell].key;  in ckh_search()
534 			*data = (void *)ckh->tab[cell].data;  in ckh_search()