forest

Documentation

Index

• 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(vertex Vertex) error
• type Vertex
• type VertexIterator
  • func (it *VertexIterator) HasNext() bool
  • func (it *VertexIterator) NextVertex() Vertex
• type VertexList
• type VertexSet

Types

type LevelledForest

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

LevelledForest contains multiple trees (which is a potentially disconnected planar graph). Each vertexContainer in the graph has a level (view) and a hash. A vertexContainer can only have one parent with strictly smaller level (view). A vertexContainer can have multiple children, all with strictly larger level (view). 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.

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` , `level`

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 number of vertices at given level

func (*LevelledForest) GetSize

func (f *LevelledForest) GetSize() uint64

GetSize returns the total number of vertices above the pruned lowest 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 height An empty VertexIterator is returned, if no vertices are known at the specified `level`

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`

func (*LevelledForest) VerifyVertex

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

VerifyVertex verifies that vertex satisfies the following conditions (1)

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 returns the parents (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