forest

Documentation

Index

• func IsInvalidVertexError(err error) bool
• func VertexToString(v Vertex) string
• type InvalidVertexError
  • func NewInvalidVertexErrorf(vertex Vertex, msg string, args ...interface{}) InvalidVertexError
  • func (err InvalidVertexError) Error() string
• type LevelledForest
  • func NewLevelledForest(lowestLevel uint64) *LevelledForest
  • func (f *LevelledForest) AddVertex(vertex Vertex)
  • func (f *LevelledForest) GetChildren(id flow.Identifier) VertexIterator
  • func (f *LevelledForest) GetNumberOfChildren(id flow.Identifier) int
  • func (f *LevelledForest) GetNumberOfVerticesAtLevel(level uint64) int
  • func (f *LevelledForest) GetSize() uint64
  • func (f *LevelledForest) GetVertex(id flow.Identifier) (Vertex, bool)
  • func (f *LevelledForest) GetVerticesAtLevel(level uint64) VertexIterator
  • func (f *LevelledForest) HasVertex(id flow.Identifier) bool
  • func (f *LevelledForest) PruneUpToLevel(level uint64) error
  • func (f *LevelledForest) VerifyVertex(v Vertex) error
• type Vertex
• type VertexIterator
  • func (it *VertexIterator) HasNext() bool
  • func (it *VertexIterator) NextVertex() Vertex
• type VertexList
• type VertexSet

Functions

func IsInvalidVertexError

func IsInvalidVertexError(err error) bool

func VertexToString

func VertexToString(v Vertex) string

VertexToString returns a string representation of the vertex.

Types

type InvalidVertexError

type InvalidVertexError struct {
	// Vertex is the invalid vertex
	Vertex Vertex
	// contains filtered or unexported fields
}

InvalidVertexError indicates that a proposed vertex is invalid for insertion to the forest.

func NewInvalidVertexErrorf

func NewInvalidVertexErrorf(vertex Vertex, msg string, args ...interface{}) InvalidVertexError

func (InvalidVertexError) Error

func (err InvalidVertexError) Error() string

type LevelledForest

type LevelledForest struct {
	LowestLevel uint64
	// contains filtered or unexported fields
}

LevelledForest contains multiple trees (which is a potentially disconnected planar graph). Each vertex in the graph has a level and a hash. A vertex can only have one parent, which must have strictly smaller level. A vertex can have multiple children, all with strictly larger level. A LevelledForest provides the ability to prune all vertices up to a specific level. A tree whose root is below the pruning threshold might decompose into multiple disconnected subtrees as a result of pruning. By design, the LevelledForest does _not_ touch the parent information for vertices that are on the lowest retained level. Thereby, it is possible to initialize the LevelledForest with a root vertex at the lowest retained level, without this root needing to have a parent. Furthermore, the root vertex can be at level 0 and in absence of a parent still satisfy the condition that any parent must be of lower level (mathematical principle of vacuous truth) without the implementation needing to worry about unsigned integer underflow.

LevelledForest is NOT safe for concurrent use by multiple goroutines.

func NewLevelledForest

func NewLevelledForest(lowestLevel uint64) *LevelledForest

NewLevelledForest initializes a LevelledForest

func (*LevelledForest) AddVertex

func (f *LevelledForest) AddVertex(vertex Vertex)

AddVertex adds vertex to forest if vertex is within non-pruned levels Handles repeated addition of same vertex (keeps first added vertex). If vertex is at or below pruning level: method is NoOp. UNVALIDATED: requires that vertex would pass validity check LevelledForest.VerifyVertex(vertex).

func (*LevelledForest) GetChildren

func (f *LevelledForest) GetChildren(id flow.Identifier) VertexIterator

GetChildren returns a VertexIterator to iterate over the children An empty VertexIterator is returned, if no vertices are known whose parent is `id`.

func (*LevelledForest) GetNumberOfChildren

func (f *LevelledForest) GetNumberOfChildren(id flow.Identifier) int

GetNumberOfChildren returns number of children of given vertex

func (*LevelledForest) GetNumberOfVerticesAtLevel

func (f *LevelledForest) GetNumberOfVerticesAtLevel(level uint64) int

GetNumberOfVerticesAtLevel returns the number of full vertices at given level. A full vertex is a vertex that was explicitly added to the forest. In contrast, an empty vertex container represents a vertex that is _referenced_ as parent by one or more full vertices, but has not been added itself to the forest. We only count vertices that have been explicitly added to the forest and not yet pruned. (In comparision, we do _not_ count vertices that are _referenced_ as parent by vertices, but have not been added themselves).

func (*LevelledForest) GetSize

func (f *LevelledForest) GetSize() uint64

GetSize returns the total number of vertices above the lowest pruned level. Note this call is not concurrent-safe, caller is responsible to ensure concurrency safety.

func (*LevelledForest) GetVertex

func (f *LevelledForest) GetVertex(id flow.Identifier) (Vertex, bool)

GetVertex returns (<full vertex>, true) if the vertex with `id` and `level` was found (nil, false) if full vertex is unknown

func (*LevelledForest) GetVerticesAtLevel

func (f *LevelledForest) GetVerticesAtLevel(level uint64) VertexIterator

GetVerticesAtLevel returns a VertexIterator to iterate over the Vertices at the specified level. An empty VertexIterator is returned, if no vertices are known at the specified level. If `level` is already pruned, an empty VertexIterator is returned.

func (*LevelledForest) HasVertex

func (f *LevelledForest) HasVertex(id flow.Identifier) bool

HasVertex returns true iff full vertex exists.

func (*LevelledForest) PruneUpToLevel

func (f *LevelledForest) PruneUpToLevel(level uint64) error

PruneUpToLevel prunes all blocks UP TO but NOT INCLUDING `level`. Error returns: * mempool.BelowPrunedThresholdError if input level is below the lowest retained level

func (*LevelledForest) VerifyVertex

func (f *LevelledForest) VerifyVertex(v Vertex) error

VerifyVertex verifies that adding vertex `v` would yield a valid Levelled Forest. Specifically, we verify that _all_ of the following conditions are satisfied:

1. `v.Level()` must be strictly larger than the level that `v` reports for its parent (maintains an acyclic graph).

2. If a vertex with the same ID as `v.VertexID()` exists in the graph or is referenced by another vertex within the graph, the level must be identical. (In other words, we don't have vertices with the same ID but different level)

3. Let `ParentLevel`, `ParentID` denote the level, ID that `v` reports for its parent. If a vertex with `ParentID` exists (or is referenced by other vertices as their parent), we require that the respective level is identical to `ParentLevel`.

Notes:

• If `v.Level()` has already been pruned, adding it to the forest is a NoOp. Hence, any vertex with level below the pruning threshold automatically passes.
• By design, the LevelledForest does _not_ touch the parent information for vertices that are on the lowest retained level. Thereby, it is possible to initialize the LevelledForest with a root vertex at the lowest retained level, without this root needing to have a parent. Furthermore, the root vertex can be at level 0 and in absence of a parent still satisfy the condition that any parent must be of lower level (mathematical principle of vacuous truth) without the implementation needing to worry about unsigned integer underflow.

Error returns: * InvalidVertexError if the input vertex is invalid for insertion to the forest.

type Vertex

type Vertex interface {
	// VertexID returns the vertex's ID (in most cases its hash)
	VertexID() flow.Identifier
	// Level returns the vertex's level
	Level() uint64
	// Parent returns the parent's (level, ID)
	Parent() (flow.Identifier, uint64)
}

type VertexIterator

type VertexIterator struct {
	// contains filtered or unexported fields
}

VertexIterator is a stateful iterator for VertexList. Internally operates directly on the Vertex Containers It has one-element look ahead for skipping empty vertex containers.

func (*VertexIterator) HasNext

func (it *VertexIterator) HasNext() bool

HasNext returns true if and only if there is a next Vertex

func (*VertexIterator) NextVertex

func (it *VertexIterator) NextVertex() Vertex

NextVertex returns the next Vertex or nil if there is none

type VertexList

type VertexList []*vertexContainer

type VertexSet

type VertexSet map[flow.Identifier]*vertexContainer