Struct TreeIndex

pub struct TreeIndex { /* private fields */ }

Index a tree structure or something.

Implementations

impl TreeIndex

pub fn new(bitfield: Bitfield) -> Self

Create a new TreeIndex by passing it a sparse_bitfield instance.

pub fn get(&mut self, index: u64) -> bool

Get a bit from the bitfield.

pub fn set(&mut self, index: u64) -> Change

Set an index on the tree to true, and also all of the parents to the index. Walks the flat-tree upward, until it finds the upper most node.

pub fn proof<'a>( &'a mut self, index: u64, include_hash: bool, nodes: &'a mut impl AsMut<Vec<u64>>, remote_tree: &mut Self, ) -> Option<Proof<'_>>

Prove a method.

pub fn proof_with_digest<'a>( &'a mut self, index: u64, digest: u64, include_hash: bool, nodes: &'a mut impl AsMut<Vec<u64>>, remote_tree: &mut Self, ) -> Option<Proof<'_>>

Determine which Nodes prove the correctness for the Node at index.

The passed buffer is filled with nodes that are verified by the same index. This is done so allocations can happen at the top level, and a buffer (pool) can be used to prevent extra allocations.

pub fn digest(&mut self, index: u64) -> u64

Create a digest for data at index.

pub fn blocks(&mut self) -> u64

Get the position of the highest entry in the tree. Aka max.

NOTE: should we rename this to .len() ?

Examples

       3
   1       5
 0   2   4   6

extern crate tree_index as tree;
use tree::{Change, TreeIndex, Verification};

let mut tree = TreeIndex::default();
for i in (0..8).step_by(2) {
  tree.set(i);
}
assert_eq!(tree.blocks(), 4);
tree = TreeIndex::default();
tree.set(1);
tree.set(5);
assert_eq!(tree.blocks(), 4);
tree = TreeIndex::default();
tree.set(3);
assert_eq!(tree.blocks(), 4);

pub fn roots(&mut self, roots: &mut Vec<u64>)

Get all root nodes.

TODO: don’t make this allocate, but fill a vector instead.

pub fn verified_by(&mut self, index: u64) -> Verification

Find the node that verified the node that’s passed.

This is different from the Javascript implementation in that it doesn’t push the top value into an array, but returns it instead through the Verification type.

pub fn as_bitfield(&self) -> &Bitfield

Get a reference to underlying bitfield

Trait Implementations

impl Debug for TreeIndex

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

Formats the value using the given formatter.

impl Default for TreeIndex

Create a TreeIndex with an empty sparse_bitfield instance with a page size of 1024.

fn default() -> Self

Returns the “default value” for a type.