Struct concordium_std::StateBTreeMap
source · pub struct StateBTreeMap<K, V, const M: usize = 8> { /* private fields */ }Expand description
An ordered map based on B-Tree, where each node is stored separately in the low-level key-value store.
It can be seen as an extension adding tracking of the keys ordering on top
of StateMap to provide functions such as higher and
lower. This results in some overhead when inserting and
deleting entries from the map compared to using StateMap.
| Operation | Performance |
|---|---|
get / get_mut | O(k) |
insert | O(k + log(n)) |
remove | O(k + log(n)) |
higher/lower | O(k + log(n)) |
Where k is the byte size of the serialized keys and n is the number of
entries in the map.
§Type parameters
The map StateBTreeMap<K, V, M> is parametrized by the types:
K: Keys used in the map. Most operations on the map require this to implementSerialize. Keys cannot contain references to the low-level state, such as types containingStateBox,StateMapandStateSet.V: Values stored in the map. Most operations on the map require this to implementSerialandDeserialWithState<StateApi>.M: Aconst usizedetermining the minimum degree of the B-tree. Must be a value of2or above for the tree to work. This can be used to tweak the height of the tree vs size of each node in the tree. The default is set to 8, which seems to perform well on benchmarks. These benchmarks ran operations on a collection of 1000 elements, some using keys of 4 bytes others 16 bytes.
§Usage
New maps can be constructed using the
new_btree_map method on the
StateBuilder.
/// In an init method:
let mut map1 = state_builder.new_btree_map();
/// In a receive method:
let mut map2 = host.state_builder().new_btree_map();§Caution
StateBTreeMaps must be explicitly deleted when they are no longer needed,
otherwise they will remain in the contract’s state, albeit unreachable.
struct MyState {
inner: StateBTreeMap<u64, u64>,
}
fn incorrect_replace(state_builder: &mut StateBuilder, state: &mut MyState) {
// The following is incorrect. The old value of `inner` is not properly deleted.
// from the state.
state.inner = state_builder.new_btree_map(); // ⚠️
}Instead, either the map should be cleared or explicitly deleted.
fn correct_replace(state_builder: &mut StateBuilder, state: &mut MyState) {
state.inner.clear_flat();
}Or alternatively
fn correct_replace(state_builder: &mut StateBuilder, state: &mut MyState) {
let old_map = mem::replace(&mut state.inner, state_builder.new_btree_map());
old_map.delete()
}Implementations§
source§impl<const M: usize, K, V> StateBTreeMap<K, V, M>
impl<const M: usize, K, V> StateBTreeMap<K, V, M>
sourcepub fn insert(&mut self, key: K, value: V) -> Option<V>
pub fn insert(&mut self, key: K, value: V) -> Option<V>
Insert a key-value pair into the map. Returns the previous value if the key was already in the map.
Caution: If Option<V> is to be deleted and contains a data structure
prefixed with State (such as StateBox or
StateMap), then it is important to call
Deletable::delete on the value returned
when you’re finished with it. Otherwise, it will remain in the
contract state.
sourcepub fn remove_and_get(&mut self, key: &K) -> Option<V>
pub fn remove_and_get(&mut self, key: &K) -> Option<V>
Remove a key from the map, returning the value at the key if the key was previously in the map.
Caution: If V is a StateBox,
StateMap, then it is important to call
Deletable::delete on the value returned
when you’re finished with it. Otherwise, it will remain in the
contract state.
sourcepub fn remove(&mut self, key: &K)
pub fn remove(&mut self, key: &K)
Remove a key from the map. This also deletes the value in the state.
sourcepub fn get(&self, key: &K) -> Option<StateRef<'_, V>>
pub fn get(&self, key: &K) -> Option<StateRef<'_, V>>
Get a reference to the value corresponding to the key.
sourcepub fn get_mut(&mut self, key: &K) -> Option<StateRefMut<'_, V, StateApi>>
pub fn get_mut(&mut self, key: &K) -> Option<StateRefMut<'_, V, StateApi>>
Get a mutable reference to the value corresponding to the key.
sourcepub fn contains_key(&self, key: &K) -> bool
pub fn contains_key(&self, key: &K) -> bool
Returns true if the map contains a value for the specified key.
sourcepub fn higher(&self, key: &K) -> Option<StateRef<'_, K>>
pub fn higher(&self, key: &K) -> Option<StateRef<'_, K>>
Returns the smallest key in the map that is strictly larger than the
provided key. None meaning no such key is present in the map.
sourcepub fn eq_or_higher(&self, key: &K) -> Option<StateRef<'_, K>>
pub fn eq_or_higher(&self, key: &K) -> Option<StateRef<'_, K>>
Returns the smallest key in the map that is equal or larger than the
provided key. None meaning no such key is present in the map.
sourcepub fn lower(&self, key: &K) -> Option<StateRef<'_, K>>
pub fn lower(&self, key: &K) -> Option<StateRef<'_, K>>
Returns the largest key in the map that is strictly smaller than the
provided key. None meaning no such key is present in the map.
sourcepub fn eq_or_lower(&self, key: &K) -> Option<StateRef<'_, K>>
pub fn eq_or_lower(&self, key: &K) -> Option<StateRef<'_, K>>
Returns the largest key in the map that is equal or smaller than the
provided key. None meaning no such key is present in the map.
sourcepub fn first_key(&self) -> Option<StateRef<'_, K>>
pub fn first_key(&self) -> Option<StateRef<'_, K>>
Returns a reference to the first key in the map, if any. This key is always the minimum of all keys in the map.
sourcepub fn last_key(&self) -> Option<StateRef<'_, K>>
pub fn last_key(&self) -> Option<StateRef<'_, K>>
Returns a reference to the last key in the map, if any. This key is always the maximum of all keys in the map.
sourcepub fn iter(&self) -> StateBTreeMapIter<'_, '_, K, V, M> ⓘ
pub fn iter(&self) -> StateBTreeMapIter<'_, '_, K, V, M> ⓘ
Create an iterator over the entries of StateBTreeMap.
Ordered by K ascending.
sourcepub fn clear(&mut self)
pub fn clear(&mut self)
Clears the map, removing all key-value pairs.
This also includes values pointed at, if V, for example, is a
StateBox. If applicable use
clear_flat instead.
sourcepub fn clear_flat(&mut self)
pub fn clear_flat(&mut self)
Clears the map, removing all key-value pairs.
This should be used over clear if it is
applicable. It avoids recursive deletion of values since the
values are required to be flat.
Unfortunately it is not possible to automatically choose between these implementations. Once Rust gets trait specialization then this might be possible.