md/dm-vdo/int-map.c

16  * probing, all the entries that hash to a given bucket are stored within a fixed neighborhood
36  * entries of the hash bucket at the start of the neighborhood, a pair of small offset fields each
66  * struct bucket - hash bucket
101 	/** @buckets: The array of hash buckets. */
106  * mix() - The Google CityHash 16-byte hash mixing function.
110  * Return: A hash of the two inputs.
115 	u64 hash = (input1 ^ input2);
117 	hash *= CITY_MULTIPLIER;
118 	hash ^= (hash >> 47);
119 	hash ^= input2;
120 	hash *= CITY_MULTIPLIER;
121 	hash ^= (hash >> 47);
122 	hash *= CITY_MULTIPLIER;
123 	return hash;
127  * hash_key() - Calculate a 64-bit non-cryptographic hash value for the provided 64-bit integer
134  * Return: The hash of the mapping key.
289  * select_bucket() - Select and return the hash bucket for a given search key.
296 	 * Calculate a good hash value for the provided key. We want exactly 32 bits, so mask the
299 	u64 hash = hash_key(key) & 0xFFFFFFFF;
302 	 * Scale the 32-bit hash to a bucket index by treating it as a binary fraction and
303 	 * multiplying that by the capacity. If the hash is uniformly distributed over [0 ..
304 	 * 2^32-1], then (hash * capacity / 2^32) should be uniformly distributed over [0 ..
307 	return &map->buckets[(hash * map->capacity) >> 32];
311  * search_hop_list() - Search the hop list associated with given hash bucket for a given search
366  * resize_buckets() - Increase the number of hash buckets.
392 	/* Populate the new hash table from the entries in the old bucket array. */
471 		 * the hash bucket whose neighborhood is full.
492 		 * the hole closer to the hash bucket, if not all the way into its neighborhood.
578 			 * hash bucket to be referenced by its hop vector.
641 		 * we're forced to allocate a new bucket array with a larger capacity, re-hash all