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 //! This module provides build meta support for lookups in these tables, as well as the shared hash
11 //! function used for probing.
12 
13 use std::iter;
14 
15 /// A primitive hash function for matching opcodes.
16 pub fn simple_hash(s: &str) -> usize {
17     let mut h: u32 = 5381;
18     for c in s.chars() {
19         h = (h ^ c as u32).wrapping_add(h.rotate_right(6));
20     }
21     h as usize
22 }
23 
24 /// Compute an open addressed, quadratically probed hash table containing
25 /// `items`. The returned table is a list containing the elements of the
26 /// iterable `items` and `None` in unused slots.
27 #[allow(clippy::float_arithmetic)]
28 pub fn generate_table<'cont, T, I: iter::Iterator<Item = &'cont T>, H: Fn(&T) -> usize>(
29     items: I,
30     num_items: usize,
31     hash_function: H,
32 ) -> Vec<Option<&'cont T>> {
33     let size = (1.20 * num_items as f64) as usize;
34 
35     // Probing code's stop condition relies on the table having one vacant entry at least.
36     let size = if size.is_power_of_two() {
37         size * 2
38     } else {
39         size.next_power_of_two()
40     };
41 
42     let mut table = vec![None; size];
43 
44     for i in items {
45         let mut h = hash_function(&i) % size;
46         let mut s = 0;
47         while table[h].is_some() {
48             s += 1;
49             h = (h + s) % size;
50         }
51         table[h] = Some(i);
52     }
53 
54     table
55 }
56 
57 #[cfg(test)]
58 mod tests {
59     use super::{generate_table, simple_hash};
60 
61     #[test]
62     fn basic() {
63         assert_eq!(simple_hash("Hello"), 0x2fa70c01);
64         assert_eq!(simple_hash("world"), 0x5b0c31d5);
65     }
66 
67     #[test]
68     fn test_generate_table() {
69         let v = vec!["Hello".to_string(), "world".to_string()];
70         let table = generate_table(v.iter(), v.len(), |s| simple_hash(&s));
71         assert_eq!(
72             table,
73             vec![
74                 None,
75                 Some(&"Hello".to_string()),
76                 Some(&"world".to_string()),
77                 None
78             ]
79         );
80     }
81 }
82