//! Runtime support for precomputed constant hash tables.

//!

//! The shared module with the same name can generate constant hash tables using open addressing

//! and quadratic probing.

//!

//! The hash tables are arrays that are guaranteed to:

//!

//! - Have a power-of-two size.

//! - Contain at least one empty slot.

//!

//! This module provides runtime support for lookups in these tables.

// Re-export entities from constant_hash for simplicity of use.

pub use cranelift_codegen_shared::constant_hash::*;

/// Trait that must be implemented by the entries in a constant hash table.

pub trait Table<K: Copy + Eq> {

    /// Get the number of entries in this table which must be a power of two.

    fn len(&self) -> usize;

    /// Get the key corresponding to the entry at `idx`, or `None` if the entry is empty.

    /// The `idx` must be in range.

    fn key(&self, idx: usize) -> Option<K>;

}

/// Look for `key` in `table`.

///

/// The provided `hash` value must have been computed from `key` using the same hash function that

/// was used to construct the table.

///

/// Returns `Ok(idx)` with the table index containing the found entry, or `Err(idx)` with the empty

/// sentinel entry if no entry could be found.

pub fn probe<K: Copy + Eq, T: Table<K> + ?Sized>(

    table: &T,

    key: K,

    hash: usize,

) -> Result<usize, usize> {

    debug_assert!(table.len().is_power_of_two());

    let mask = table.len() - 1;

    let mut idx = hash;

    let mut step = 0;

    loop {

        idx &= mask;

        match table.key(idx) {

            None => return Err(idx),

            Some(k) if k == key => return Ok(idx),

            _ => {}

        }

        // Quadratic probing.

        step += 1;

        // When `table.len()` is a power of two, it can be proven that `idx` will visit all

        // entries. This means that this loop will always terminate if the hash table has even

        // one unused entry.

        debug_assert!(step < table.len());

        idx += step;

    }

}

cranelift_codegen::constant_hash::probe::<&str, cranelift_codegen::settings::detail::Template>

Line

Count

Source

33

149k

pub fn probe<K: Copy + Eq, T: Table<K> + ?Sized>(

34

149k

    table: &T,

35

149k

    key: K,

36

149k

    hash: usize,

37

149k

) -> Result<usize, usize> {

38

149k

    debug_assert!(table.len().is_power_of_two());

39

149k

    let mask = table.len() - 1;

40

41

149k

    let mut idx = hash;

42

149k

    let mut step = 0;

43

44

    loop {

45

202k

        idx &= mask;

46

47

202k

        match table.key(idx) {

48

0

            None => return Err(idx),

49

202k

            Some(k) if k == key => return Ok(idx),

50

52.8k

            _ => {}

51

        }

52

53

        // Quadratic probing.

54

52.8k

        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

52.8k

        debug_assert!(step < table.len());

60

52.8k

        idx += step;

61

    }

62

149k

}

Unexecuted instantiation: cranelift_codegen::constant_hash::probe::<&str, [core::option::Option<cranelift_codegen::ir::instructions::Opcode>]>

cranelift_codegen::constant_hash::probe::<&str, cranelift_codegen::settings::detail::Template>

Line

Count

Source

33

214k

pub fn probe<K: Copy + Eq, T: Table<K> + ?Sized>(

34

214k

    table: &T,

35

214k

    key: K,

36

214k

    hash: usize,

37

214k

) -> Result<usize, usize> {

38

214k

    debug_assert!(table.len().is_power_of_two());

39

214k

    let mask = table.len() - 1;

40

41

214k

    let mut idx = hash;

42

214k

    let mut step = 0;

43

44

    loop {

45

289k

        idx &= mask;

46

47

289k

        match table.key(idx) {

48

0

            None => return Err(idx),

49

289k

            Some(k) if k == key => return Ok(idx),

50

75.5k

            _ => {}

51

        }

52

53

        // Quadratic probing.

54

75.5k

        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

75.5k

        debug_assert!(step < table.len());

60

75.5k

        idx += step;

61

    }

62

214k

}

Unexecuted instantiation: cranelift_codegen::constant_hash::probe::<&str, [core::option::Option<cranelift_codegen::ir::instructions::Opcode>]>