cranelift_codegen_meta/
constant_hash.rs

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
10use 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.
15pub 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)]
45mod tests {
46    use super::generate_table;
47    use cranelift_codegen_shared::constant_hash::simple_hash;
48
49    #[test]
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}
cranelift_codegen_meta/constant_hash.rs

cranelift_codegen_meta/
constant_hash.rs
