Struct ic_stable_structures::btreemap::BTreeMap
source · pub struct BTreeMap<K, V, M>where
K: BoundedStorable + Ord + Clone,
V: BoundedStorable,
M: Memory,{ /* private fields */ }
Expand description
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§
source§impl<K, V, M> BTreeMap<K, V, M>where
K: BoundedStorable + Ord + Clone,
V: BoundedStorable,
M: Memory,
impl<K, V, M> BTreeMap<K, V, M>where
K: BoundedStorable + Ord + Clone,
V: BoundedStorable,
M: Memory,
sourcepub fn init(memory: M) -> Self
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.
sourcepub fn new(memory: M) -> Self
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.
sourcepub fn insert(&mut self, key: K, value: V) -> Option<V>
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.to_bytes().len() <= Key::MAX_SIZE value.to_bytes().len() <= Value::MAX_SIZE
sourcepub fn get(&self, key: &K) -> Option<V>
pub fn get(&self, key: &K) -> Option<V>
Returns the value associated with the given key if it exists.
sourcepub fn contains_key(&self, key: &K) -> bool
pub fn contains_key(&self, key: &K) -> bool
Returns true
if the key exists in the map, false
otherwise.
sourcepub fn into_memory(self) -> M
pub fn into_memory(self) -> M
Returns the underlying memory.
sourcepub fn remove(&mut self, key: &K) -> Option<V>
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.
sourcepub fn iter(&self) -> Iter<'_, K, V, M> ⓘ
pub fn iter(&self) -> Iter<'_, K, V, M> ⓘ
Returns an iterator over the entries of the map, sorted by key.
sourcepub fn range(&self, key_range: impl RangeBounds<K>) -> Iter<'_, K, V, M> ⓘ
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.