Struct Table 

pub struct Table<H> { /* private fields */ }

An open-addressing multimap from 64-bit hashes to caller-owned handles.

See the module documentation for the lookup contract.

Example

use commonware_utils::handles::Table;

// FNV-1a stands in for a keyed hasher.
fn hash(key: &str) -> u64 {
    key.bytes().fold(0xcbf2_9ce4_8422_2325, |h, b| {
        (h ^ u64::from(b)).wrapping_mul(0x0100_0000_01b3)
    })
}

let keys = ["apple", "banana", "cherry"];
let mut table = Table::new();
for (handle, key) in keys.iter().enumerate() {
    table.insert(hash(key), handle, |handle| hash(keys[handle]));
}

// Confirm each candidate against the key it resolves to.
let find = |table: &Table<usize>, key| table.get(hash(key)).find(|&handle| keys[handle] == key);
assert_eq!(find(&table, "banana"), Some(1));
assert!(table.remove(hash("banana"), 1));
assert_eq!(find(&table, "banana"), None);

Implementations

impl<H: Copy + Eq + Default> Table<H>

pub const fn new() -> Self

Creates an empty table without allocating.

pub fn with_capacity(entries: usize) -> Self

Creates an empty table that fits entries entries without growing.

Panics

Panics if the required slot count overflows usize.

pub const fn len(&self) -> usize

Returns the number of entries.

pub const fn is_empty(&self) -> bool

Returns whether the table has no entries.

pub const fn capacity(&self) -> usize

Returns the number of entries that fit before the next growth.

pub fn reserve(&mut self, additional: usize, rehash: impl FnMut(H) -> u64)

Grows the table, if needed, so that inserting additional more entries never grows it. rehash is as for Table::insert.

Panics

Panics if the required entry or slot count overflows usize, or if the slots need more than isize::MAX bytes.

pub fn get(&self, hash: u64) -> impl Iterator<Item = H> + '_

Returns the handles whose home slot and fingerprint match hash, in probe order.

Every handle inserted under hash is yielded. Callers confirm each candidate against the key it resolves to, since entries with a different hash that shares the home slot and fingerprint are yielded too.

pub fn prefetch(&self, hash: u64)

Hints the CPU to load the home slot of hash, so that a following lookup, insertion, or removal under hash waits less on memory.

pub fn insert(&mut self, hash: u64, handle: H, rehash: impl FnMut(H) -> u64)

Inserts handle under hash.

Duplicate hashes and duplicate handles are allowed. rehash must map every handle already in the table to the hash it was inserted under, and it is called only when the table grows.

Panics

Panics if an entry would end up more than 2^24 - 2 slots from its home, which takes a run of 2^24 occupied slots (for example, 2^24 entries with identical hashes).

pub fn find_or_insert( &mut self, hash: u64, matches: impl FnMut(H) -> bool, handle: H, rehash: impl FnMut(H) -> u64, ) -> (H, bool)

Returns the first handle among the candidates for hash that matches accepts, or inserts handle under hash and returns it, in one walk of the run. The second value reports whether handle was inserted.

A full table grows first, even if a candidate is then accepted, so the candidates are those Table::get yields after any growth, in the same order. rehash is as for Table::insert.

Panics

Panics if an entry would end up more than 2^24 - 2 slots from its home, or if growing the table would need more than isize::MAX bytes of slots.

pub fn remove(&mut self, hash: u64, handle: H) -> bool

Removes one entry holding handle whose home slot and fingerprint match hash, returning whether one existed.

hash must be the hash the entry was inserted under. Like Table::get, matching is by home slot and fingerprint, so a different hash sharing both would remove the entry too.

Trait Implementations

impl<H> Debug for Table<H>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<H: Copy + Eq + Default> Default for Table<H>

fn default() -> Self

Returns the “default value” for a type.