Lines Matching defs:bucket

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
58  * Search bucket for key and return the cell number if found; SIZE_T_MAX
62 ckh_bucket_search(ckh_t *ckh, size_t bucket, const void *key) {
67 		cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i];
69 			return (bucket << LG_CKH_BUCKET_CELLS) + i;
81 	size_t hashes[2], bucket, cell;
87 	/* Search primary bucket. */
88 	bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1);
89 	cell = ckh_bucket_search(ckh, bucket, key);
94 	/* Search secondary bucket. */
95 	bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1);
96 	cell = ckh_bucket_search(ckh, bucket, key);
101 ckh_try_bucket_insert(ckh_t *ckh, size_t bucket, const void *key,
107 	 * Cycle through the cells in the bucket, starting at a random position.
113 		cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) +
127  * No space is available in bucket.  Randomly evict an item, then try to find an
130  * eviction/relocation bucket cycle.
137 	size_t hashes[2], bucket, tbucket;
140 	bucket = argbucket;
145 		 * Choose a random item within the bucket to evict.  This is
147 		 * evicting all items within a bucket during iteration, it
150 		 * bucket.
154 		cell = &ckh->tab[(bucket << LG_CKH_BUCKET_CELLS) + i];
166 		/* Find the alternate bucket for the evicted item. */
169 		if (tbucket == bucket) {
173 			 * It may be that (tbucket == bucket) still, if the
174 			 * item's hashes both indicate this bucket.  However,
175 			 * we are guaranteed to eventually escape this bucket
182 			 * 1) This bucket == argbucket, so we will quickly
184 			 * 2) An item was evicted to this bucket from another,
185 			 *    which means that at least one item in this bucket
196 		bucket = tbucket;
197 		if (!ckh_try_bucket_insert(ckh, bucket, key, data)) {
205 	size_t hashes[2], bucket;
211 	/* Try to insert in primary bucket. */
212 	bucket = hashes[0] & ((ZU(1) << ckh->lg_curbuckets) - 1);
213 	if (!ckh_try_bucket_insert(ckh, bucket, key, data)) {
217 	/* Try to insert in secondary bucket. */
218 	bucket = hashes[1] & ((ZU(1) << ckh->lg_curbuckets) - 1);
219 	if (!ckh_try_bucket_insert(ckh, bucket, key, data)) {
226 	return ckh_evict_reloc_insert(ckh, bucket, argkey, argdata);