jemalloc/src/ckh.c

4  * hash bucket contains 2^n cells, for n >= 1, and 2 indicates that two hash
24  *           |         #cells/bucket         |
32  * The number of cells per bucket is chosen such that a bucket fits in one cache
49  * Search bucket for key and return the cell number if found; SIZE_T_MAX
53 ckh_bucket_search(ckh_t *ckh, size_t bucket, const void *key)
59 		cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i];
61 			return ((bucket << LG_CKH_BUCKET_CELLS) + i);
73 	size_t hashes[2], bucket, cell;
79 	/* Search primary bucket. */
80 	bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1);
81 	cell = ckh_bucket_search(ckh, bucket, key);
85 	/* Search secondary bucket. */
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,
99 	 * Cycle through the cells in the bucket, starting at a random position.
105 		cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) +
119  * No space is available in bucket.  Randomly evict an item, then try to find an
122  * eviction/relocation bucket cycle.
130 	size_t hashes[2], bucket, tbucket;
133 	bucket = argbucket;
138 		 * Choose a random item within the bucket to evict.  This is
140 		 * evicting all items within a bucket during iteration, it
143 		 * bucket.
147 		cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i];
159 		/* Find the alternate bucket for the evicted item. */
162 		if (tbucket == bucket) {
166 			 * It may be that (tbucket == bucket) still, if the
167 			 * item's hashes both indicate this bucket.  However,
168 			 * we are guaranteed to eventually escape this bucket
175 			 * 1) This bucket == argbucket, so we will quickly
177 			 * 2) An item was evicted to this bucket from another,
178 			 *    which means that at least one item in this bucket
189 		bucket = tbucket;
190 		if (!ckh_try_bucket_insert(ckh, bucket, key, data))
198 	size_t hashes[2], bucket;
204 	/* Try to insert in primary bucket. */
205 	bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1);
206 	if (!ckh_try_bucket_insert(ckh, bucket, key, data))
209 	/* Try to insert in secondary bucket. */
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));