Struct Node 

pub struct Node {
    pub left: Option<Cid>,
    pub entries: Vec<Entry>,
}

One node of the tree.

A node holds every key at its own layer within some range, and a pointer to a subtree between each pair of them. left is the subtree before the first entry. A node with no entries is legal and common — it is what the layering rule produces when a run of low keys hangs under a much taller one — and it carries left alone.

Fields

left: Option<Cid>

Keys below this node’s layer that sort before every entry.

entries: Vec<Entry>

This node’s own keys, in order.

Implementations

impl Node

pub fn decode(block: &[u8]) -> Result<Self, NodeError>

Decodes one node out of its block.

use std::collections::BTreeMap;
use didbot_data::mst::{Node, Tree};

let tree = Tree::build(&BTreeMap::new());
let block = &tree.blocks()[tree.root()];
assert_eq!(Node::decode(block).unwrap(), Node::default());

pub fn from_value(value: &Value) -> Result<Self, NodeError>

Reads a node out of an already-decoded value.

pub fn parts(&self) -> Parts

The node with its keys rebuilt; see Parts.

Every key was checked to be UTF-8 when the node was decoded, and a node this crate built has UTF-8 keys because it was handed strings. A node assembled by hand out of arbitrary bytes is the one case where this is lossy, and it is the case Node::decode refuses.

pub fn from_parts(parts: &Parts) -> Self

Builds a node from full keys, values and subtrees.

The inverse of Node::parts, and the only way to make a node without going through Tree::build: the shared prefixes are computed here, so a caller cannot hold a node whose encoding disagrees with its keys.

Panics

If there is not exactly one more subtree than there are keys, or if the keys and values are of different lengths. Both are the caller building something that is not a node.

pub fn block(&self) -> (Cid, Vec<u8>)

The block this node encodes to, and the CID naming it.

pub fn layer(&self) -> Option<usize>

Which layer this node is on, where that can be told from the node alone.

A node with keys is at the layer its keys are at — they all share one, which Node::decode checks. A node with no keys and no left subtree is the empty root, which is layer zero by definition. A node with no keys and a left subtree is the empty intermediate the layering rule produces, and it has no height of its own: it is one below whatever pointed at it, and nothing inside it says what that was.

pub fn is_empty(&self) -> bool

Whether this is the empty node: no keys, and nothing below it.

This is the node an account’s first commit signs over, and it is also what a subtree pointer of null means — which is why an empty node is never stored as a subtree. A tree carrying one would have two spellings of “nothing here”.

impl Node

pub fn to_value(&self) -> Value

The node as a data-model value, which is what it is hashed as.

The field names are the protocol’s and are one letter each: l for the left subtree, e for the entries, and within an entry p for the shared prefix length, k for the rest of the key, v for the record and t for the subtree to its right. k is a byte string and not text — a node is keyed on bytes, and a prefix length may land inside a multi-byte character.

Ordering is not decided here. dag_cbor sorts map keys length-first and then bytewise, so a node built with the fields in any order encodes to the same bytes.

Trait Implementations

impl Clone for Node

fn clone(&self) -> Node

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl Debug for Node

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

Formats the value using the given formatter.

impl Default for Node

fn default() -> Node

Returns the “default value” for a type.

impl PartialEq for Node

fn eq(&self, other: &Node) -> 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 Eq for Node

impl StructuralPartialEq for Node