Struct StateBTreeSet

pub struct StateBTreeSet<K, const M: usize = 8> { /* private fields */ }

An ordered set based on B-Tree, where each node is stored separately in the low-level key-value store.

Operation	Performance
contains	O(k + log(n))
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 StateBTreeSet<K, M> is parametrized by the types:

• K: Keys used in the set. Most operations on the set require this to implement Serialize. Keys cannot contain references to the low-level state, such as types containing StateBox, StateMap and StateSet.
• M: A const usize determining the minimum degree of the B-tree. Must be a value of 2 or 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 sets can be constructed using the new_btree_set method on the StateBuilder.

/// In an init method:
let mut map1 = state_builder.new_btree_set();
/// In a receive method:
let mut map2 = host.state_builder().new_btree_set();

Caution

StateBTreeSets must be explicitly deleted when they are no longer needed, otherwise they will remain in the contract’s state, albeit unreachable.

struct MyState {
    inner: StateBTreeSet<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_set(); // ⚠️
}

Instead, the set should be cleared:

fn correct_replace(state_builder: &mut StateBuilder, state: &mut MyState) {
    state.inner.clear();
}

Implementations

impl<const M: usize, K> StateBTreeSet<K, M>

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

where K: Serialize + Ord,

Insert a key into the set. Returns true if the key is new in the collection.

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

where K: Serialize + Ord,

Returns true if the set contains an element equal to the key.

pub fn len(&self) -> u32

Return the number of elements in the set.

pub fn is_empty(&self) -> bool

Returns true is the set contains no elements.

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

Get an iterator over the elements in the StateBTreeSet. The iterator returns elements in increasing order.

pub fn clear(&mut self)

Clears the set, removing all elements.

pub fn higher(&self, key: &K) -> Option<StateRef<'_, K>>

where K: Serialize + Ord,

Returns the smallest key in the set that is strictly larger than the provided key. None meaning no such key is present in the set.

pub fn eq_or_higher(&self, key: &K) -> Option<StateRef<'_, K>>

where K: Serialize + Ord,

Returns the smallest key in the set that is equal or larger than the provided key. None meaning no such key is present in the set.

pub fn lower(&self, key: &K) -> Option<StateRef<'_, K>>

where K: Serialize + Ord,

Returns the largest key in the set that is strictly smaller than the provided key. None meaning no such key is present in the set.

pub fn eq_or_lower(&self, key: &K) -> Option<StateRef<'_, K>>

where K: Serialize + Ord,

Returns the largest key in the set that is equal or smaller than the provided key. None meaning no such key is present in the set.

pub fn first(&self) -> Option<StateRef<'_, K>>

where K: Serialize + Ord,

Returns a reference to the first key in the set, if any. This key is always the minimum of all keys in the set.

pub fn last(&self) -> Option<StateRef<'_, K>>

where K: Serialize + Ord,

Returns a reference to the last key in the set, if any. This key is always the maximum of all keys in the set.

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

where K: Ord + Serialize,

Remove a key from the set. Returns whether such an element was present.

Trait Implementations

impl<const M: usize, K> DeserialWithState<ExternStateApi> for StateBTreeSet<K, M>

fn deserial_with_state<R: Read>( state: &StateApi, source: &mut R, ) -> ParseResult<Self>

Attempt to read a structure from a given source and state, failing if an error occurs during deserialization or reading.

impl<const M: usize, K> Serial for StateBTreeSet<K, M>

fn serial<W: Write>(&self, out: &mut W) -> Result<(), W::Err>

Attempt to write the structure into the provided writer, failing if only part of the structure could be written.