1 //! Build support for precomputed constant hash tables.
2 //!
3 //! This module can generate constant hash tables using open addressing and quadratic probing.
4 //!
5 //! The hash tables are arrays that are guaranteed to:
6 //!
7 //! - Have a power-of-two size.
8 //! - Contain at least one empty slot.
9
10 use std::iter;
11
12 /// Compute an open addressed, quadratically probed hash table containing
13 /// `items`. The returned table is a list containing the elements of the
14 /// iterable `items` and `None` in unused slots.
generate_table<'cont, T, I: iter::Iterator<Item = &'cont T>, H: Fn(&T) -> usize>( items: I, num_items: usize, hash_function: H, ) -> Vec<Option<&'cont T>>15 pub fn generate_table<'cont, T, I: iter::Iterator<Item = &'cont T>, H: Fn(&T) -> usize>(
16 items: I,
17 num_items: usize,
18 hash_function: H,
19 ) -> Vec<Option<&'cont T>> {
20 let size = (1.20 * num_items as f64) as usize;
21
22 // Probing code's stop condition relies on the table having one vacant entry at least.
23 let size = if size.is_power_of_two() {
24 size * 2
25 } else {
26 size.next_power_of_two()
27 };
28
29 let mut table = vec![None; size];
30
31 for i in items {
32 let mut h = hash_function(i) % size;
33 let mut s = 0;
34 while table[h].is_some() {
35 s += 1;
36 h = (h + s) % size;
37 }
38 table[h] = Some(i);
39 }
40
41 table
42 }
43
44 #[cfg(test)]
45 mod tests {
46 use super::generate_table;
47 use cranelift_codegen_shared::constant_hash::simple_hash;
48
49 #[test]
test_generate_table()50 fn test_generate_table() {
51 let v = vec!["Hello".to_string(), "world".to_string()];
52 let table = generate_table(v.iter(), v.len(), |s| simple_hash(&s));
53 assert_eq!(
54 table,
55 vec![
56 None,
57 Some(&"Hello".to_string()),
58 Some(&"world".to_string()),
59 None
60 ]
61 );
62 }
63 }
64