Struct ic_stable_structures::btreemap::BTreeMap

pub struct BTreeMap<K, V, M>
where
    K: Storable + Ord + Clone,
    V: Storable,
    M: Memory,
{ /* private fields */ }

A “stable” map based on a B-tree.

The implementation is based on the algorithm outlined in “Introduction to Algorithms” by Cormen et al.

Implementations

impl<K, V, M> BTreeMap<K, V, M>

where K: Storable + Ord + Clone, V: Storable, M: Memory,

pub fn init(memory: M) -> Self

Initializes a BTreeMap.

If the memory provided already contains a BTreeMap, then that map is loaded. Otherwise, a new BTreeMap instance is created.

pub fn new(memory: M) -> Self

Creates a new instance a BTreeMap.

The given memory is assumed to be exclusively reserved for this data structure and that it starts at address zero. Typically memory will be an instance of RestrictedMemory.

When initialized, the data structure has the following memory layout:

| BTreeHeader | Allocator | … free memory for nodes |

See Allocator for more details on its own memory layout.

pub fn load(memory: M) -> Self

Loads the map from memory.

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

Inserts a key-value pair into the map.

The previous value of the key, if present, is returned.

PRECONDITION: Key is bounded in size Value is bounded in size key.to_bytes().len() <= max_size(Key) value.to_bytes().len() <= max_size(Value)

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

Returns the value associated with the given key if it exists.

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

Returns true if the key exists in the map, false otherwise.

pub fn is_empty(&self) -> bool

Returns true if the map contains no elements.

pub fn len(&self) -> u64

Returns the number of elements in the map.

pub fn into_memory(self) -> M

Returns the underlying memory.

pub fn clear(self) -> Self

Removes all elements from the map.

pub fn first_key_value(&self) -> Option<(K, V)>

Returns the first key-value pair in the map. The key in this pair is the minimum key in the map.

pub fn last_key_value(&self) -> Option<(K, V)>

Returns the last key-value pair in the map. The key in this pair is the maximum key in the map.

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

Removes a key from the map, returning the previous value at the key if it exists.

pub fn pop_last(&mut self) -> Option<(K, V)>

Removes and returns the last element in the map. The key of this element is the maximum key that was in the map

pub fn pop_first(&mut self) -> Option<(K, V)>

Removes and returns the first element in the map. The key of this element is the minimum key that was in the map

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

Returns an iterator over the entries of the map, sorted by key.

pub fn range(&self, key_range: impl RangeBounds<K>) -> Iter<'_, K, V, M>

Returns an iterator over the entries in the map where keys belong to the specified range.

pub fn iter_upper_bound(&self, bound: &K) -> Iter<'_, K, V, M>

Returns an iterator pointing to the first element below the given bound. Returns an empty iterator if there are no keys below the given bound.