Struct grin_store::prune_list::PruneList

pub struct PruneList { /* private fields */ }

Maintains a list of previously pruned nodes in PMMR, compacting the list as parents get pruned and allowing checking whether a leaf is pruned. Given a node’s position, computes how much it should get shifted given the subtrees that have been pruned before.

The PruneList is useful when implementing compact backends for a PMMR (for example a single large byte array or a file). As nodes get pruned and removed from the backend to free space, the backend will get more compact but positions of a node within the PMMR will not match positions in the backend storage anymore. The PruneList accounts for that mismatch and does the position translation.

Implementations

impl PruneList

pub fn new(path: Option<PathBuf>, bitmap: Bitmap) -> PruneList

Instantiate a new prune list from the provided path and 1-based bitmap. Note: Does not flush the bitmap to disk. Caller is responsible for doing this.

pub fn empty() -> PruneList

Instatiate a new empty prune list.

pub fn open<P: AsRef<Path>>(path: P) -> Result<PruneList>

Open an existing prune_list or create a new one. Takes an optional bitmap of new pruned pos to be combined with existing pos.

pub fn init_caches(&mut self)

Init our internal shift caches.

pub fn flush(&mut self) -> Result<()>

Save the prune_list to disk.

pub fn get_total_shift(&self) -> u64

Return the total shift from all entries in the prune_list. This is the shift we need to account for when adding new entries to our PMMR.

pub fn get_total_leaf_shift(&self) -> u64

Return the total leaf_shift from all entries in the prune_list. This is the leaf_shift we need to account for when adding new entries to our PMMR.

pub fn get_shift(&self, pos0: u64) -> u64

Computes by how many positions a node at pos should be shifted given the number of nodes that have already been pruned before it. Note: the node at pos may be pruned and may be compacted away itself and the caller needs to be aware of this.

pub fn get_leaf_shift(&self, pos0: u64) -> u64

As above, but only returning the number of leaf nodes to skip for a given leaf. Helpful if, for instance, data for each leaf is being stored separately in a continuous flat-file.

pub fn append(&mut self, pos0: u64)

Push the node at the provided position in the prune list. Handles rollup of siblings and children as we go (relatively slow). Once we find a subtree root that can not be rolled up any further we cleanup everything beneath it and replace it with a single appended node.

pub fn len(&self) -> u64

Number of entries in the prune_list.

pub fn is_empty(&self) -> bool

Is the prune_list empty?

pub fn is_pruned(&self, pos0: u64) -> bool

A pos is pruned if it is a pruned root directly or if it is beneath the “next” pruned subtree. We only need to consider the “next” subtree due to the append-only MMR structure.

pub fn to_vec(&self) -> Vec<u64>

Convert the prune_list to a vec of pos.

pub fn shift_cache(&self) -> &[u64]

Internal shift cache as slice. only used in store/tests/prune_list.rs tests

pub fn leaf_shift_cache(&self) -> &[u64]

Internal leaf shift cache as slice. only used in store/tests/prune_list.rs tests

pub fn is_pruned_root(&self, pos0: u64) -> bool

Is the specified position a root of a pruned subtree?

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

Iterator over the entries in the prune list (pruned roots).

pub fn pruned_bintree_range_iter(&self) -> impl Iterator<Item = Range<u64>> + '_

Iterator over the pruned “bintree range” for each pruned root.

pub fn unpruned_iter(&self, cutoff_pos: u64) -> impl Iterator<Item = u64> + '_

Iterator over all pos that are not pruned based on current prune_list.

pub fn unpruned_leaf_iter( &self, cutoff_pos: u64 ) -> impl Iterator<Item = u64> + '_

Iterator over all leaf pos that are not pruned based on current prune_list. Note this is not necessarily the same as the “leaf_set” as an output can be spent but not yet pruned.

pub fn bitmap(&self) -> Bitmap

Return a clone of our internal bitmap.

Trait Implementations

impl Debug for PruneList

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

Formats the value using the given formatter.