Struct MultikeyIsolatedMap

pub(crate) struct MultikeyIsolatedMap<I, K1, K2, V>
where
    I: Key,
    K1: Hash + Eq,
    K2: Eq,
{
    index: HashMap<K1, Vec<I>>,
    table: DenseSlotMap<I, Record<K2, V>>,
}

Data structure indexed by multiple keys and an isolation

This is a map keyed by:

• K1, a hashable key type
• K2, a possibly-non-hashable key type,
• Box<dyn Isolation>, a circuit/client isolation

Lookup/inserts will look for a suitable entry with a compatible isolation and, if found, narrow that entry’s isolation.

A lookup/insert yields a table index I, which can later be used to do an O(1) lookup of the same entry. (This is particularly useful given that an isolation cannot be simply compared; a proper lookup might narrow the isolation of an existing record.)

I must implement slotmap:Key.

The values are V.

Internally, it looks like this:

          index                                         table
          HashMap           Vec_______________          SlotMap_____________________
          |     | contains  | table_index    |  t._i.   | K2, isol, V  /  <vacant> |
    K1 -> |  ---+---------> | table_index    | -------> | K2, isol, V  /  <vacant> |
          |_____|           | table_index    | 1      1 | K2, isol, V  /  <vacant> |
                            | table_index    |          | K2, isol, V  /  <vacant> |
  K2, isol ---------------> | .............. |          | K2, isol, V  /  <vacant> |
            linear search   |________________|          | ...             ....     |
```                                                     |__________________________|

Fields

index: HashMap<K1, Vec<I>>

The first stage index, mapping K1 to I

table: DenseSlotMap<I, Record<K2, V>>

Actual table containing the entries, including K2 and the isolation, and V

Invariant

Entries in table and index correspond precisely, one-to-one: each Vec element in index refers to an (occupied) entry in table, and each (occupied) entry in table is referenced precisely once from index.

Implementations

impl<I, K1, K2, V> MultikeyIsolatedMap<I, K1, K2, V>

where I: Key, K1: Hash + Eq, K2: Eq,

pub(crate) fn index_or_insert_with( &mut self, k1: &K1, k2: &K2, isolation: Box<dyn Isolation>, create: impl FnOnce() -> V, ) -> I

where K1: Clone, K2: Clone,

Lookup, or insert, an entry

Looks for an entry with keys k1 and k2 and a compatible isolation. If it finds one, narrows the isolation and returns the entry’s index.

If no entry is found, inserts a new value made by create.

pub(crate) fn by_index(&self, t_index: I) -> Option<&Record<K2, V>>

Look up an existing entry by index

If the entry was removed in the meantime, will return None

pub(crate) fn by_index_mut(&mut self, t_index: I) -> Option<&mut Record<K2, V>>

Look up an existing entry by index (mutably)

If the entry was removed in the meantime, will return None

pub(crate) fn retain( &mut self, test: impl FnMut(&K1, &Record<K2, V>, I) -> bool, )

Keep only entries that match a predicate

Each entry is passed to test, and removed unless test returned true.

Trait Implementations

impl<I, K1, K2, V: Debug> Debug for MultikeyIsolatedMap<I, K1, K2, V>

where I: Key + Debug, K1: Hash + Eq + Debug, K2: Eq + Debug,

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

Formats the value using the given formatter.

impl<I, K1, K2, V> Default for MultikeyIsolatedMap<I, K1, K2, V>

where I: Key, K1: Hash + Eq, K2: Eq,

fn default() -> Self

Returns the “default value” for a type.