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.
len(&self) -> usize19 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.
key(&self, idx: usize) -> Option<K>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.
probe<K: Copy + Eq, T: Table<K> + ?Sized>( table: &T, key: K, hash: usize, ) -> Result<usize, usize>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