Struct ArenaParallelSparseTrie 

pub struct ArenaParallelSparseTrie { /* private fields */ }

An arena-based sparse trie whose subtries can be mutated in parallel.

Structure

Uses arena allocation (slotmap::SlotMap) for node storage with direct index-based child pointers, avoiding the per-node hashing overhead of a HashMap-based trie. The trie is split into two tiers:

• Upper trie (upper_arena): Contains nodes whose path is shorter than UPPER_TRIE_MAX_DEPTH nibbles. These are the root and its immediate children.
• Lower subtries (ArenaSparseSubtrie): Each child of an upper-trie branch at the depth boundary becomes the root of its own subtrie, stored as an ArenaSparseNode::Subtrie child in the upper arena. Each subtrie owns its own arena, enabling lock-free parallel mutation.

Node placement is determined by path length (not counting a branch’s short key):

• Paths with < UPPER_TRIE_MAX_DEPTH nibbles live in upper_arena.
• Paths with ≥ UPPER_TRIE_MAX_DEPTH nibbles live in a subtrie.

Node Revealing

Nodes are lazily revealed from proof data via SparseTrie::reveal_nodes. Each node is placed into the upper arena or delegated to its subtrie based on path depth. Unrevealed children are stored as ArenaSparseNodeBranchChild::Blinded with their RLP encoding. When multiple subtries have pending reveals, they are processed in parallel using rayon (controlled by ArenaParallelismThresholds::min_revealed_nodes).

Leaf Operations

Leaf updates and removals are applied via SparseTrie::update_leaves. The method walks the upper trie to route each update to the correct subtrie, then processes subtries in parallel when the update count exceeds ArenaParallelismThresholds::min_updates.

SparseTrie::update_leaf and SparseTrie::remove_leaf are not yet implemented.

After updates, structural changes (branch collapse, subtrie unwrapping) are handled by propagating dirty state back up through the upper trie.

Root Hash Calculation

Root hash computation follows a bottom-up approach:

1. SparseTrie::update_subtrie_hashes: Takes dirty subtries from the upper arena and hashes them in parallel (when dirty leaf count meets ArenaParallelismThresholds::min_dirty_leaves), then walks the upper trie to restore hashed subtries and inline-hash any remaining dirty nodes.
2. SparseTrie::root: Calls update_subtrie_hashes, then RLP-encodes the full upper trie depth-first to produce the root hash.

Each node tracks its state via ArenaSparseNodeState (Revealed, Cached, or Dirty) so only modified subtrees are recomputed.

Pruning

SparseTrie::prune removes revealed nodes that are not ancestors of any retained leaf. Pruned nodes are replaced with ArenaSparseNodeBranchChild::Blinded entries using their cached RLP. Subtries are pruned in parallel when their leaf count exceeds ArenaParallelismThresholds::min_leaves_for_prune.

Implementations

impl ArenaParallelSparseTrie

pub const fn with_parallelism_thresholds( self, thresholds: ArenaParallelismThresholds, ) -> Self

Sets the thresholds that control when parallelism is used during operations.

Trait Implementations

impl Clone for ArenaParallelSparseTrie

fn clone(&self) -> ArenaParallelSparseTrie

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for ArenaParallelSparseTrie

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

Formats the value using the given formatter.

impl Default for ArenaParallelSparseTrie

fn default() -> Self

Returns the “default value” for a type.

impl Drop for ArenaParallelSparseTrie

Available on debug-assertions enabled only.

fn drop(&mut self)

Executes the destructor for this type.

impl SparseTrie for ArenaParallelSparseTrie

fn set_root( &mut self, root: TrieNodeV2, masks: Option<BranchNodeMasks>, retain_updates: bool, ) -> SparseTrieResult<()>

Configures the trie to have the given root node revealed.

fn set_updates(&mut self, retain_updates: bool)

Configures the trie to retain information about updates.

fn reserve_nodes(&mut self, additional: usize)

Reserves capacity for additional trie nodes.

fn reveal_nodes( &mut self, nodes: &mut [ProofTrieNodeV2], ) -> SparseTrieResult<()>

Reveals one or more trie nodes if they have not been revealed before.

fn update_leaf<P: TrieNodeProvider>( &mut self, _full_path: Nibbles, _value: Vec<u8>, _provider: P, ) -> SparseTrieResult<()>

Updates the value of a leaf node at the specified path.

fn remove_leaf<P: TrieNodeProvider>( &mut self, _full_path: &Nibbles, _provider: P, ) -> SparseTrieResult<()>

Removes a leaf node at the specified path.

fn root(&mut self) -> B256

Calculates and returns the root hash of the trie.

fn is_root_cached(&self) -> bool

Returns true if the root node is cached and does not need any recomputation.

fn update_subtrie_hashes(&mut self)

Recalculates and updates the RLP hashes of subtries deeper than a certain level. The level is defined in the implementation.

fn get_leaf_value(&self, full_path: &Nibbles) -> Option<&Vec<u8>>

Retrieves a reference to the leaf value at the specified path.

fn find_leaf( &self, full_path: &Nibbles, expected_value: Option<&Vec<u8>>, ) -> Result<LeafLookup, LeafLookupError>

Attempts to find a leaf node at the specified path.

fn updates_ref(&self) -> Cow<'_, SparseTrieUpdates>

Returns a reference to the current sparse trie updates.

fn take_updates(&mut self) -> SparseTrieUpdates

Consumes and returns the currently accumulated trie updates.

fn wipe(&mut self)

Removes all nodes and values from the trie, resetting it to a blank state with only an empty root node. This is used when a storage root is deleted.

fn clear(&mut self)

This clears all data structures in the sparse trie, keeping the backing data structures allocated. A crate::SparseNode::Empty is inserted at the root.

fn shrink_nodes_to(&mut self, _size: usize)

Shrink the capacity of the sparse trie’s node storage to the given size. This will reduce memory usage if the current capacity is higher than the given size.

fn shrink_values_to(&mut self, _size: usize)

Shrink the capacity of the sparse trie’s value storage to the given size. This will reduce memory usage if the current capacity is higher than the given size.

fn size_hint(&self) -> usize

Returns a cheap O(1) size hint for the trie representing the count of revealed (non-Hash) nodes.

fn memory_size(&self) -> usize

Returns a heuristic for the in-memory size of this trie in bytes.

fn prune(&mut self, retained_leaves: &[Nibbles]) -> usize

Prunes all subtrees that do not contain retained leaves.

fn update_leaves( &mut self, updates: &mut B256Map<LeafUpdate>, proof_required_fn: impl FnMut(B256, u8), ) -> SparseTrieResult<()>

Applies leaf updates to the sparse trie.

fn take_debug_recorder(&mut self) -> TrieDebugRecorder

Takes the debug recorder out of this trie, replacing it with an empty one.

fn commit_updates( &mut self, _updated: &HashMap<Nibbles, BranchNodeCompact>, _removed: &HashSet<Nibbles>, )

Commits the updated nodes to internal trie state.

fn with_root( self, root: TrieNodeV2, masks: Option<BranchNodeMasks>, retain_updates: bool, ) -> SparseTrieResult<Self>

Configures the trie to have the given root node revealed.

fn with_updates(self, retain_updates: bool) -> Self

Configures the trie to retain information about updates.

fn reveal_node( &mut self, path: Nibbles, node: TrieNodeV2, masks: Option<BranchNodeMasks>, ) -> SparseTrieResult<()>

The single-node version of reveal_nodes.

Layout

Note: Most layout information is completely unstable and may even differ between compilations. The only exception is types with certain repr(...) attributes. Please see the Rust Reference's “Type Layout” chapter for details on type layout guarantees.

Size: 352 bytes