Struct miri::borrow_tracker::tree_borrows::unimap::UniKeyMap

pub struct UniKeyMap<K> {
    mapping: FxHashMap<K, u32>,
    deassigned: Vec<u32>,
}

From K to UniIndex

Fields

mapping: FxHashMap<K, u32>

Underlying map that does all the hard work. Key invariant: the contents of deassigned are disjoint from the keys of mapping, and together they form the set of contiguous integers 0 .. (mapping.len() + deassigned.len()).

deassigned: Vec<u32>

Indexes that can be reused: memory gain when the map gets sparse due to many deletions.

Implementations

impl<K> UniKeyMap<K>where K: Hash + Eq,

pub fn len(&self) -> usize

How many keys/index pairs are currently active.

pub fn contains_key(&self, key: &K) -> bool

Whether this key has an associated index or not.

pub fn insert(&mut self, key: K) -> UniIndex

Assign this key to a new index. Panics if the key is already assigned, use get_or_insert for a version that instead returns the existing assignment.

pub fn get(&self, key: &K) -> Option<UniIndex>

If it exists, the index this key maps to.

pub fn get_or_insert(&mut self, key: K) -> UniIndex

Either get a previously existing entry, or create a new one if it is not yet present.

pub fn remove(&mut self, key: &K)

Return whatever index this key was using to the deassigned pool.

Note: calling this function can be dangerous. If the index still exists somewhere in a UniValMap and is reassigned by the UniKeyMap then it will inherit the old value of a completely unrelated key. If you UniKeyMap::remove a key you should make sure to also UniValMap::remove the associated UniIndex from ALL UniValMaps.

Example of such behavior:

let mut keymap = UniKeyMap::<char>::default();
let mut valmap = UniValMap::<char>::default();
// Insert 'a' -> _ -> 'A'
let idx_a = keymap.insert('a');
valmap.insert(idx_a, 'A');
// Remove 'a' -> _, but forget to remove _ -> 'A'
keymap.remove(&'a');
// valmap.remove(idx_a); // If we uncomment this line the issue is fixed
// Insert 'b' -> _
let idx_b = keymap.insert('b');
let val_b = valmap.get(idx_b);
assert_eq!(val_b, Some('A')); // Oh no
// assert_eq!(val_b, None); // This is what we would have expected

Trait Implementations

impl<K: Clone> Clone for UniKeyMap<K>

fn clone(&self) -> UniKeyMap<K>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Debug> Debug for UniKeyMap<K>

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

Formats the value using the given formatter.

impl<K: Default> Default for UniKeyMap<K>

fn default() -> UniKeyMap<K>

Returns the “default value” for a type.

Layout

Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...) attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.

Size: 56 bytes