Struct SHashMap 

pub struct SHashMap<K: StableType + AsFixedSizeBytes + Hash + Eq, V: StableType + AsFixedSizeBytes> { /* private fields */ }

Reallocating, open addressing, linear probing, eager removes hash map

Conceptually the same thing as std::collections::HashMap, but with a couple of twists:

1. zwohash is used, instead of SipHash, to make hashes faster and deterministic between canister upgrades.
2. eager removes (no tombstones) are performed in order to prevent performance degradation.

This is a “finite” data structure - it can only handle up to u32::MAX / (1 + K::SIZE + V::SIZE) elements total. Putting more elements inside will panic.

Both K and V have to implement StableType and AsFixedSizeBytes traits. SHashMap also implements these traits itself, so you can nest it inside other stable structures.

Implementations

impl<K: StableType + AsFixedSizeBytes + Hash + Eq, V: StableType + AsFixedSizeBytes> SHashMap<K, V>

pub fn new() -> Self

Creates a new SHashMap of default capacity

Does not allocate any heap or stable memory.

Example

// won't allocate until you insert something in it
let mut number_pairs = SHashMap::<u64, u64>::new();

pub fn new_with_capacity(capacity: usize) -> Result<Self, OutOfMemory>

Creates a SHashMap of requested capacity.

Does allocate stable memory, returning OutOfMemory if there is not enough of it. If this function returns Ok, you are guaranteed to have enough stable memory to store at least capacity entries in it.

Example

let mut at_least_10_number_pairs = SHashMap::<u64, u64>::new_with_capacity(10)
    .expect("Out of memory");

pub fn insert(&mut self, key: K, value: V) -> Result<Option<V>, (K, V)>

Inserts a key-value pair in this SHashMap

Will try to reallocate, if length == capacity * 3/4 and there is no key-value pair stored by the same key. If the canister is out of stable memory, will return Err with the key-value pair that was about to get inserted.

If the insertion was successful, returns Option with a previous value stored by this key, if there was one.

Reallocation triggers a process of complete rehashing of keys.

Example

let mut map = SHashMap::new();

match map.insert(1, 10) {
    Ok(prev) => println!("Success! Previous value == {prev:?}"),
    Err((k, v)) => println!("Out of memory. Unable to insert: {k}, {v}"),
};

pub fn remove<Q>(&mut self, key: &Q) -> Option<V>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Removes a key-value pair by the provided key

Returns None if no pair was found by this key

Examples

let mut map = SHashMap::new();

map.insert(1, 10).expect("Out of memory");

assert_eq!(map.remove(&1).unwrap(), 10);

Borrowed type is also accepted. If your key type is, for example, [SBox] of String, then you can remove the pair by String.

let mut map = SHashMap::new();
let str_key = String::from("The key");
let key = SBox::new(str_key.clone()).expect("Out of memory");

map.insert(key, 10).expect("Out of memory");

assert_eq!(map.remove(&str_key).unwrap(), 10);

pub fn get<Q>(&self, key: &Q) -> Option<SRef<'_, V>>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns an immutable reference SRef to a value stored by the key

See also SHashMap::get_mut.

If no such key-value pair is found, returns None

Borrowed type is also accepted. If your key type is, for example, [SBox] of String, then you can get the value by String.

Example

let mut map = SHashMap::new();   

let str_key = String::from("The key");
let key = SBox::new(str_key.clone()).expect("Out of memory");

map.insert(key, 10).expect("Out of memory");

assert_eq!(*map.get(&str_key).unwrap(), 10);

pub fn get_mut<Q>(&mut self, key: &Q) -> Option<SRefMut<'_, V>>

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns a mutable reference SRefMut to a value stored by the key

See also SHashMap::get.

If no such key-value pair is found, returns None

Borrowed type is also accepted. If your key type is, for example, [SBox] of String, then you can get the value by String.

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

where K: Borrow<Q>, Q: Hash + Eq + ?Sized,

Returns true if there exists a key-value pair stored by the provided key

Borrowed type is also accepted. If your key type is, for example, [SBox] of String, then you can get the value by String.

pub const fn len(&self) -> usize

Returns the length of this SHashMap

pub const fn capacity(&self) -> usize

Returns the capacity of this SHashMap

pub const fn max_capacity() -> usize

Returns the maximum possible capacity of this SHashMap

pub fn is_empty(&self) -> bool

Returns true if the length of this SHashMap is 0

pub const fn is_full(&self) -> bool

Returns true if the next unique key insert will trigger the reallocation and rehashing

pub fn iter(&self) -> SHashMapIter<'_, K, V>

Returns an iterator over entries of this SHashMap

Elements of this iterator are presented in unpredictable and non-deterministic order.

Example

let mut map = SHashMap::new();

for i in 0..100 {
    map.insert(i, i).expect("Out of memory");
}

for (k, v) in map.iter() {
    println!("{}, {}", *k, *v);
}

pub fn clear(&mut self)

Removes all elements from this SHashMap

pub fn retain<F>(&mut self, f: F)

where F: FnMut(&K, &V) -> bool,

Filters this SHashMap, so only entries for which the provided lambda returns true are left

pub fn debug_print(&self)

Prints byte representation of this SHashMap

Useful for tests

Trait Implementations

impl<K: StableType + AsFixedSizeBytes + Hash + Eq, V: StableType + AsFixedSizeBytes> AsFixedSizeBytes for SHashMap<K, V>

const SIZE: usize = 24usize

Size of self when encoded

type Buf = [u8; 24]

Buffer that is used to encode this value into

fn as_fixed_size_bytes(&self, buf: &mut [u8])

Encodes itself into a slice of bytes.

fn from_fixed_size_bytes(buf: &[u8]) -> Self

Decodes itself from a slice of bytes.

fn as_new_fixed_size_bytes(&self) -> Self::Buf

Encodes itself into a new Self::Buf of size == Self::SIZE

impl<K: StableType + AsFixedSizeBytes + Hash + Eq + Debug, V: StableType + AsFixedSizeBytes + Debug> Debug for SHashMap<K, V>

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

Formats the value using the given formatter.

impl<K: StableType + AsFixedSizeBytes + Hash + Eq, V: StableType + AsFixedSizeBytes> Default for SHashMap<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<K: StableType + AsFixedSizeBytes + Hash + Eq, V: StableType + AsFixedSizeBytes> Drop for SHashMap<K, V>

fn drop(&mut self)

Executes the destructor for this type.

impl<K: StableType + AsFixedSizeBytes + Hash + Eq, V: StableType + AsFixedSizeBytes> StableType for SHashMap<K, V>

unsafe fn stable_drop_flag_off(&mut self)

Sets stable drop flag to off position, if it is applicable

unsafe fn stable_drop_flag_on(&mut self)

Should set stable drop flag to on position, if it is applicable

fn should_stable_drop(&self) -> bool

Should return the value of the stable drop flag

unsafe fn stable_drop(&mut self)

Performs stable drop, releasing all underlying stable memory of this data structure