cranelift_codegen/
constant_hash.rs

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.
14pub use cranelift_codegen_shared::constant_hash::*;
15
16/// Trait that must be implemented by the entries in a constant hash table.
17pub 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.
33pub 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}
cranelift_codegen/constant_hash.rs

cranelift_codegen/
constant_hash.rs
