1 //! Runtime support for precomputed constant hash tables.
2 //!
3 //! The shared module with the same name can generate constant hash tables using open addressing
4 //! and quadratic probing.
5 //!
6 //! The hash tables are arrays that are guaranteed to:
7 //!
8 //! - Have a power-of-two size.
9 //! - Contain at least one empty slot.
10 //!
11 //! This module provides runtime support for lookups in these tables.
12 
13 // Re-export entities from constant_hash for simplicity of use.
14 pub use cranelift_codegen_shared::constant_hash::*;
15 
16 /// Trait that must be implemented by the entries in a constant hash table.
17 pub trait Table<K: Copy + Eq> {
18     /// Get the number of entries in this table which must be a power of two.
19     fn len(&self) -> usize;
20 
21     /// Get the key corresponding to the entry at `idx`, or `None` if the entry is empty.
22     /// The `idx` must be in range.
23     fn key(&self, idx: usize) -> Option<K>;
24 }
25 
26 /// Look for `key` in `table`.
27 ///
28 /// The provided `hash` value must have been computed from `key` using the same hash function that
29 /// was used to construct the table.
30 ///
31 /// Returns `Ok(idx)` with the table index containing the found entry, or `Err(idx)` with the empty
32 /// sentinel entry if no entry could be found.
33 pub fn probe<K: Copy + Eq, T: Table<K> + ?Sized>(
34     table: &T,
35     key: K,
36     hash: usize,
37 ) -> Result<usize, usize> {
38     debug_assert!(table.len().is_power_of_two());
39     let mask = table.len() - 1;
40 
41     let mut idx = hash;
42     let mut step = 0;
43 
44     loop {
45         idx &= mask;
46 
47         match table.key(idx) {
48             None => return Err(idx),
49             Some(k) if k == key => return Ok(idx),
50             _ => {}
51         }
52 
53         // Quadratic probing.
54         step += 1;
55 
56         // When `table.len()` is a power of two, it can be proven that `idx` will visit all
57         // entries. This means that this loop will always terminate if the hash table has even
58         // one unused entry.
59         debug_assert!(step < table.len());
60         idx += step;
61     }
62 }
63