md/dm-vdo/int-map.c

15  * are stored in a fixed array of buckets, with no dynamic allocation for collisions. Unlike linear
23  * that process fails (typically when the buckets are around 90% full), the table must be resized
26  * Unlike linear probing, the number of buckets that must be searched in the worst case has a fixed
60 #define NEIGHBORHOOD 255    /* the number of buckets in each neighborhood */
70  * it's crucial to keep the hop fields near the buckets that they use them so they'll tend to share
91  * bucket array, we allocate a few more buckets at the end of the array instead, which is why
99 	/* @bucket_count: The number of buckets in the bucket array. */
101 	/** @buckets: The array of hash buckets. */
102 	struct bucket *buckets;
163 	 * Allocate NEIGHBORHOOD - 1 extra buckets so the last bucket can have a full neighborhood
168 			    "struct int_map buckets", &map->buckets);
220 	vdo_free(vdo_forget(map->buckets));
307 	return &map->buckets[(hash * map->capacity) >> 32];
366  * resize_buckets() - Increase the number of hash buckets.
369  * Resizes and rehashes all the existing entries, storing them in the new buckets.
394 		struct bucket *entry = &old_map.buckets[i];
402 			vdo_free(vdo_forget(map->buckets));
409 	vdo_free(vdo_forget(old_map.buckets));
416  * @map: The map containing the buckets to search.
418  * @max_probes: The maximum number of buckets to search.
432 	ptrdiff_t remaining = &map->buckets[map->bucket_count] - bucket;
451  * the start of the array. If such a bucket is found, this swaps the two buckets by moving the
477 			 * There are no buckets in this neighborhood that are in use by this one
642 		 * the entries into those buckets, and try again (a very expensive operation for
650 		 * Resizing the map invalidates all pointers to buckets, so recalculate the