Struct SBTreeMap 

pub struct SBTreeMap<K: StableType + AsFixedSizeBytes + Ord, V: StableType + AsFixedSizeBytes> { /* private fields */ }

Right-biased B-plus tree based map data structure

Entries are stored in ascending order of their keys. Use std::cmp::Reverse or a custom std::cmp::Ord impl, to differ the order.

B is 8. This implementation is optimized to perform as few stable memory (de)allocations as possible. Also, this data structure implements several non-conventional functions in order to share code with other data structures, based on this one.

This is an “infinite” data structure - it can handle up to u64::MAX key-value entries.

Both K and V have to implement StableType and AsFixedSizeBytes traits. SBTreeMap also implements these trait, so you can nest it in other stable structures.

Implementations

impl<K: StableType + AsFixedSizeBytes + Ord, V: StableType + AsFixedSizeBytes> SBTreeMap<K, V>

pub fn new() -> Self

Creates a new SBTreeMap

Does not allocate any heap or stable memory.

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

Inserts the provided key-value pair into this SBTreeMap

May allocate stable and heap memory. If your canister is out of stable memory, will return Err with the key-value pair that was about to get inserted.

If the insertion is successful, returns Option with a value, that was previously stored under this key.

Example

let mut map = SBTreeMap::new();

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

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

where K: Borrow<Q>, Q: Ord + ?Sized,

Removes a key-value pair by the provided key

Returns None if no pair was found by this key. May release some of stable memory occupied by this stable structure.

Examples

let mut map = SBTreeMap::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 = SBTreeMap::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: Ord + ?Sized,

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

See also SBTreeMap::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 = SBTreeMap::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_random_key(&self, seed: u32) -> Option<SRef<'_, K>>

Returns a random key, deterministically deriving the randomness from the seed. This function is usefull, when you have a source of real randomness.

If the collection is empty, returns None.

Same seed on the same collection leads to the same returned key. Same seed on a modified collection may still lead to the same returned key. You can use [utils::math::shuffle_bits] function to pseudo-randomly generate more seeds.

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

where K: Borrow<Q>, Q: Ord + ?Sized,

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

See also SBTreeMap::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: Ord + ?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 fn iter(&self) -> SBTreeMapIter<'_, K, V>

Returns an iterator over entries of this SBTreeMap

Elements of this iterator are presented in ascending order.

Example

let mut map = SBTreeMap::new();

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

let mut i = 0;
for (k, v) in map.iter() {
    assert_eq!(*k, i);
    assert_eq!(*v, i);

    i += 1;
}

assert_eq!(i, 100);

One can use .rev() to get elements in reverse order.

Example

let mut map = SBTreeMap::new();

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

let mut i = 100;
for (k, v) in map.iter().rev() {
    i -= 1;

    assert_eq!(*k, i);
    assert_eq!(*v, i);
}

assert_eq!(i, 0);

pub fn len(&self) -> u64

Returns the length of this SBTreeMap

pub fn is_empty(&self) -> bool

Returns true if the length of this SBTreeMap is 0

pub fn clear(&mut self)

Removes all key-value pairs from this collection, releasing all occupied stable memory

impl<K: StableType + AsFixedSizeBytes + Ord + Debug, V: StableType + AsFixedSizeBytes + Debug> SBTreeMap<K, V>

pub fn debug_print_stack(&self)

pub fn debug_print(&self)

Trait Implementations

impl<K: StableType + AsFixedSizeBytes + Ord, V: StableType + AsFixedSizeBytes> AsFixedSizeBytes for SBTreeMap<K, V>

const SIZE: usize = 16usize

Size of self when encoded

type Buf = [u8; 16]

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 + Ord + Debug, V: StableType + AsFixedSizeBytes + Debug> Debug for SBTreeMap<K, V>

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

Formats the value using the given formatter.

impl<K: StableType + AsFixedSizeBytes + Ord, V: StableType + AsFixedSizeBytes> Default for SBTreeMap<K, V>

fn default() -> Self

Returns the “default value” for a type.

impl<K: StableType + AsFixedSizeBytes + Ord, V: StableType + AsFixedSizeBytes> Drop for SBTreeMap<K, V>

fn drop(&mut self)

Executes the destructor for this type.

impl<K: StableType + AsFixedSizeBytes + Ord, V: StableType + AsFixedSizeBytes> StableType for SBTreeMap<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