Struct PageRange

pub struct PageRange<'a, K> { /* private fields */ }

A serialised representation of the range of keys contained within the sub-tree rooted at a given Page, and the associated PageDigest.

A PageRange contains all the information needed to perform a tree difference calculation, used as the input to the diff() function.

The contents of this type can be serialised and transmitted over the network, and reconstructed by the receiver by calling PageRange::new() with the serialised values.

Exchanging Between Peers

Exchange the ordered sets of PageRange between peers by serialising their content, accessed through the accessor methods:

/// A network wire representation used by the application.
struct NetworkPage {
    start_bounds: String,
    end_bounds: String,
    hash: [u8; 16],
}

let mut t = MerkleSearchTree::default();
t.upsert("bananas".to_string(), &"platanos".to_string());
t.root_hash();

let network_request: Vec<NetworkPage> = t
    .serialise_page_ranges()
    .unwrap()
    .into_iter()
    .map(|page| NetworkPage {
        start_bounds: page.start().clone(),
        end_bounds: page.end().clone(),
        hash: *page.hash().as_bytes(),
    })
    .collect();

// Send network_request to a peer over the network

And reconstruct the PageRange on the receiver:

// Receive network_request from a peer over the network

// PageRange construction is zero-copy for the page keys, borrowing the keys
// from the underlying network request.
let page_refs = network_request
    .iter()
    .map(|p| {
        // If this request is coming from an untrusted source, validate that
        // start <= end to avoid the PageRange constructor panic.
        PageRange::new(&p.start_bounds, &p.end_bounds, PageDigest::new(p.hash))
    })
    .collect::<Vec<_>>();

// Feed page_refs into diff()

Borrowed vs. Owned

A PageRange borrows the keys from the tree to avoid unnecessary clones, retaining an immutable reference to the tree.

If an owned / long-lived set of PageRange is desired (avoiding the immutable reference to the tree), generate a PageRangeSnapshot from the set of PageRange.

Implementations

impl<'a, K> PageRange<'a, K>

pub fn new(start: &'a K, end: &'a K, hash: PageDigest) -> Self

where K: PartialOrd,

Construct a PageRange for the given key interval and PageDigest.

Panics

If start is greater than end, this method panics.

pub fn start(&self) -> &'a K

Returns the inclusive start of this PageRange.

pub fn end(&self) -> &'a K

Returns the inclusive end of this PageRange

pub fn hash(&self) -> &PageDigest

Returns the PageDigest of this page, representing the content of the page and all pages within the sub-tree rooted at it.

pub fn into_hash(self) -> PageDigest

Consume this PageRange, returning the PageDigest that covers the subtree rooted at this page.

Trait Implementations

impl<'a, K> Clone for PageRange<'a, K>

fn clone(&self) -> Self

Returns a copy of the value.

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

Performs copy-assignment from source.

impl<'a, K: Debug> Debug for PageRange<'a, K>

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

Formats the value using the given formatter.

impl<'a, K> Display for PageRange<'a, K>

where K: Display,

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

Formats the value using the given formatter.

impl<'a, const N: usize, K> From<&'a Page<N, K>> for PageRange<'a, K>

fn from(page: &'a Page<N, K>) -> Self

Converts to this type from the input type.

impl<'a, K> From<PageRange<'a, K>> for OwnedPageRange<K>

where K: Clone,

fn from(v: PageRange<'a, K>) -> Self

Converts to this type from the input type.

impl<'a, K> FromIterator<PageRange<'a, K>> for PageRangeSnapshot<K>

where K: Clone + 'a,

fn from_iter<T: IntoIterator<Item = PageRange<'a, K>>>(iter: T) -> Self

Creates a value from an iterator.

impl<'a, K: PartialEq> PartialEq for PageRange<'a, K>

fn eq(&self, other: &PageRange<'a, K>) -> 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<'a, K> StructuralPartialEq for PageRange<'a, K>