Struct StorageMap 

pub struct StorageMap { /* private fields */ }

An account storage map is a sparse merkle tree of depth Self::DEPTH.

It can be used to store a large amount of data in an account than would be otherwise possible using just the account’s storage slots. This works by storing the root of the map’s underlying SMT in one account storage slot. Each map entry is a leaf in the tree and its inclusion is proven while retrieving it (e.g. via active_account::get_map_item).

As a side-effect, this also means that not all entries of the map have to be present at transaction execution time in order to access or modify the map. It is sufficient if just the accessed/modified items are present in the advice provider.

Because the keys of the map are user-chosen and thus not necessarily uniformly distributed, the tree could be imbalanced and made less efficient. To mitigate that, the keys used in the storage map are hashed before they are inserted into the SMT, which creates a uniform distribution. The original keys are retained in a separate map. This causes redundancy but allows for introspection of the map, e.g. by querying the set of stored (original) keys which is useful in debugging and explorer scenarios.

Implementations

impl StorageMap

pub const DEPTH: u8 = 64u8

The depth of the SMT that represents the storage map.

pub const EMPTY_VALUE: Word = Smt::EMPTY_VALUE

The default value of empty leaves.

pub fn new() -> Self

Returns a new StorageMap.

All leaves in the returned tree are set to Self::EMPTY_VALUE.

pub fn with_entries<I: ExactSizeIterator<Item = (Word, Word)>>( entries: impl IntoIterator<Item = (Word, Word), IntoIter = I>, ) -> Result<Self, StorageMapError>

Creates a new StorageMap from the provided key-value entries.

Errors

Returns an error if:

• the provided entries contain multiple values for the same key.

pub fn root(&self) -> Word

Returns the root of the underlying sparse merkle tree.

pub fn num_leaves(&self) -> usize

Returns the number of non-empty leaves in this storage map.

Note that this may return a different value from Self::num_entries() as a single leaf may contain more than one key-value pair.

pub fn num_entries(&self) -> usize

Returns the number of key-value pairs with non-default values in this storage map.

Note that this may return a different value from Self::num_leaves() as a single leaf may contain more than one key-value pair.

pub fn get(&self, raw_key: &Word) -> Word

Returns the value corresponding to the key or Self::EMPTY_VALUE if the key is not associated with a value.

pub fn open(&self, raw_key: &Word) -> StorageMapWitness

Returns an opening of the leaf associated with raw key.

Conceptually, an opening is a Merkle path to the leaf, as well as the leaf itself.

pub fn leaves(&self) -> impl Iterator<Item = (LeafIndex<SMT_DEPTH>, &SmtLeaf)>

Returns an iterator over the leaves of the underlying Smt.

pub fn entries(&self) -> impl Iterator<Item = (&Word, &Word)>

Returns an iterator over the key-value pairs in this storage map.

Note that the returned key is the raw map key.

pub fn inner_nodes(&self) -> impl Iterator<Item = InnerNodeInfo> + '_

Returns an iterator over the inner nodes of the underlying Smt.

pub fn insert( &mut self, raw_key: Word, value: Word, ) -> Result<Word, AccountError>

Inserts or updates the given key value pair and returns the previous value, or Self::EMPTY_VALUE if no entry was previously present.

If the provided value is Self::EMPTY_VALUE the entry will be removed.

pub fn apply_delta( &mut self, delta: &StorageMapDelta, ) -> Result<Word, AccountError>

Applies the provided delta to this account storage.

pub fn into_entries(self) -> BTreeMap<Word, Word>

Consumes the map and returns the underlying map of entries.

pub fn hash_key(raw_key: Word) -> Word

Hashes the given key to get the key of the SMT.

pub fn hashed_map_key_to_leaf_index(hashed_map_key: Word) -> Felt

Returns the leaf index of a map key.

Trait Implementations

impl Clone for StorageMap

fn clone(&self) -> StorageMap

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for StorageMap

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

Formats the value using the given formatter.

impl Default for StorageMap

fn default() -> Self

Returns the “default value” for a type.

impl Deserializable for StorageMap

fn read_from<R: ByteReader>( source: &mut R, ) -> Result<Self, DeserializationError>

Reads a sequence of bytes from the provided source, attempts to deserialize these bytes into Self, and returns the result.

fn read_from_bytes(bytes: &[u8]) -> Result<Self, DeserializationError>

Attempts to deserialize the provided bytes into Self and returns the result.

impl From<StorageMap> for StorageMapDelta

Converts a StorageMap into a StorageMapDelta for initial delta construction.

fn from(map: StorageMap) -> Self

Converts to this type from the input type.

impl PartialEq for StorageMap

fn eq(&self, other: &StorageMap) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl Serializable for StorageMap

fn write_into<W: ByteWriter>(&self, target: &mut W)

Serializes self into bytes and writes these bytes into the target.

fn get_size_hint(&self) -> usize

Returns an estimate of how many bytes are needed to represent self.

fn to_bytes(&self) -> Vec<u8>

Serializes self into a vector of bytes.

impl Eq for StorageMap

impl StructuralPartialEq for StorageMap