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.
15 #[allow(clippy::float_arithmetic)]
16 pub fn generate_table<'cont, T, I: iter::Iterator<Item = &'cont T>, H: Fn(&T) -> usize>(
17     items: I,
18     num_items: usize,
19     hash_function: H,
20 ) -> Vec<Option<&'cont T>> {
21     let size = (1.20 * num_items as f64) as usize;
22 
23     // Probing code's stop condition relies on the table having one vacant entry at least.
24     let size = if size.is_power_of_two() {
25         size * 2
26     } else {
27         size.next_power_of_two()
28     };
29 
30     let mut table = vec![None; size];
31 
32     for i in items {
33         let mut h = hash_function(&i) % size;
34         let mut s = 0;
35         while table[h].is_some() {
36             s += 1;
37             h = (h + s) % size;
38         }
39         table[h] = Some(i);
40     }
41 
42     table
43 }
44 
45 #[cfg(test)]
46 mod tests {
47     use super::generate_table;
48     use cranelift_codegen_shared::constant_hash::simple_hash;
49 
50     #[test]
51     fn test_generate_table() {
52         let v = vec!["Hello".to_string(), "world".to_string()];
53         let table = generate_table(v.iter(), v.len(), |s| simple_hash(&s));
54         assert_eq!(
55             table,
56             vec![
57                 None,
58                 Some(&"Hello".to_string()),
59                 Some(&"world".to_string()),
60                 None
61             ]
62         );
63     }
64 }
65