Struct narwhal_dag::node_dag::NodeDag

pub struct NodeDag<T: Affiliated> { /* private fields */ }

The Dag data structure This consists morally of two tables folded in one:

• the node table, which contains mappings from node hashes to weak references, maintaining which nodes were historically processed by the graph,
• the heads of the graph (aka the roots): those nodes which do not have antecedents in the graph, and are holding transitive references to all the other nodes.

Those two tables are coalesced into one, which value type is either a weak reference (regular node) or a strong one (heads). During the normal processing of the graph, heads which gain antecedents lost their head status and become regular nodes. Moreover, the transitive references to nodes in the graph may disappear because of its changing topology (see above: path compression). In this case, the weak references may be invalidate. We do not remove them from the graph, and their presence serves as a “tombstone”.

/!\ Warning /!: do not drop the heads of the graph without having given them new antecedents, as this will transitively drop all the nodes they point to and may cause loss of data.

Implementations

impl<T: Affiliated> NodeDag<T>

pub fn new() -> NodeDag<T>

Creates a new Node dag

pub fn get_weak(
    &self,
    digest: T::TypedDigest
) -> Result<WeakNodeRef<T>, NodeDagError>

Returns a weak reference to the requested vertex. This does not prevent the vertex from being dropped off the graph.

pub fn get(&self, digest: T::TypedDigest) -> Result<NodeRef<T>, NodeDagError>

pub fn contains(&self, hash: T::TypedDigest) -> bool

Returns whether the vertex pointed to by the hash passed as an argument was contained in the DAG at any point in the past.

pub fn contains_live(&self, digest: T::TypedDigest) -> bool

Returns whether the vertex pointed to by the hash passed as an argument is contained in the DAG and still a live (uncompressed) reference.

pub fn head_digests(&self) -> impl Iterator<Item = T::TypedDigest> + '_

Returns an iterator over the digests of the heads of the graph, i.e. the nodes which do not have a child.

pub fn has_head(&self, hash: T::TypedDigest) -> Result<bool, NodeDagError>

Returns whether the vertex pointed to by the hash passed as an argument is a head of the DAG (nodes not pointed to by any other). Heads carry strong references to many downward nodes and dropping them might GC large spans of the graph.

This returns an error if the queried node is unknown

pub fn make_compressible(
    &self,
    hash: T::TypedDigest
) -> Result<bool, NodeDagError>

Marks the node passed as argument as compressible, leaving it to be reaped by path compression. Returns true if the node was made compressible, and false if it already was

This return an error if the queried node is unknown or dropped from the graph

pub fn try_insert(&mut self, value: T) -> Result<(), NodeDagError>

Inserts a node in the Dag from the provided value

When the value is inserted, its parent references are interpreted as hash pointers (see Affiliated). Those hash pointers are converted to [NodeRef`] based on the pointed nodes that are already in the DAG.

Note: the dag currently does not do any causal completion. It is an error to insert a node which parents are unknown by the DAG it’s inserted into.

This insertion procedure only maintains the invariant that

• insertion should be idempotent
• an unseen node is a head (not pointed) to by any other node.

impl<T: Affiliated + Sync + Send + Debug> NodeDag<T>

pub fn bft(
    &self,
    hash: T::TypedDigest
) -> Result<impl Iterator<Item = NodeRef<T>>, NodeDagError>

Performs a breadth-first traversal of the Dag starting at the given vertex

pub fn size(&self) -> usize

Returns the number of elements (nodes) stored

Trait Implementations

impl<T: Debug + Affiliated> Debug for NodeDag<T>where
    T::TypedDigest: Debug,

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

Formats the value using the given formatter.

impl<T: Affiliated> Default for NodeDag<T>

fn default() -> Self

Returns the “default value” for a type.