dag

package
v2.0.0-beta.7 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Aug 30, 2022 License: Apache-2.0 Imports: 12 Imported by: 1

Documentation

Index

Constants

This section is empty.

Variables

View Source
var (
	// ErrTraversalDone is returned when the traversal was already marked as done by another thread.
	ErrTraversalDone = errors.New("traversal is done")
)

Functions

func ConeRootIndexes

func ConeRootIndexes(ctx context.Context, parentsTraverserStorage ParentsTraverserStorage, cachedBlockMeta *storage.CachedMetadata, cmi iotago.MilestoneIndex) (youngestConeRootIndex iotago.MilestoneIndex, oldestConeRootIndex iotago.MilestoneIndex, err error)

ConeRootIndexes searches the cone root indexes for a given block. cachedBlockMeta has to be solid, otherwise youngestConeRootIndex and oldestConeRootIndex will be 0 if a block is missing in the cone.

func ForEachSolidEntryPoint

func ForEachSolidEntryPoint(
	ctx context.Context,
	dbStorage *storage.Storage,
	targetIndex iotago.MilestoneIndex,
	solidEntryPointCheckThresholdPast iotago.MilestoneIndex,
	solidEntryPointConsumer func(sep *storage.SolidEntryPoint) bool) error

ForEachSolidEntryPoint calculates the solid entry points for the given target index.

func TraverseChildren

func TraverseChildren(ctx context.Context, childrenTraverserStorage ChildrenTraverserStorage, startBlockID iotago.BlockID, condition Predicate, consumer Consumer, walkAlreadyDiscovered bool) error

TraverseChildren starts to traverse the children (future cone) of the given start block until the traversal stops due to no more blocks passing the given condition. It is unsorted BFS because the children are not ordered in the database.

func TraverseParents

func TraverseParents(ctx context.Context, parentsTraverserStorage ParentsTraverserStorage, parents iotago.BlockIDs, condition Predicate, consumer Consumer, onMissingParent OnMissingParent, onSolidEntryPoint OnSolidEntryPoint, traverseSolidEntryPoints bool) error

TraverseParents starts to traverse the parents (past cone) in the given order until the traversal stops due to no more blocks passing the given condition. It is a DFS of the paths of the parents one after another. Caution: condition func is not in DFS order.

func TraverseParentsOfBlock

func TraverseParentsOfBlock(ctx context.Context, parentsTraverserStorage ParentsTraverserStorage, startBlockID iotago.BlockID, condition Predicate, consumer Consumer, onMissingParent OnMissingParent, onSolidEntryPoint OnSolidEntryPoint, traverseSolidEntryPoints bool) error

TraverseParentsOfBlock starts to traverse the parents (past cone) of the given start block until the traversal stops due to no more blocks passing the given condition. It is a DFS of the paths of the parents one after another. Caution: condition func is not in DFS order.

func UpdateConeRootIndexes

func UpdateConeRootIndexes(ctx context.Context, traverserStorage TraverserStorage, blockIDs iotago.BlockIDs, cmi iotago.MilestoneIndex) error

UpdateConeRootIndexes updates the cone root indexes of the future cone of all given blocks. all the blocks of the newly referenced cone already have updated cone root indexes. we have to walk the future cone, and update the past cone of all blocks that reference an old cone. as a special property, invocations of the yielded function share the same 'already traversed' set to circumvent walking the future cone of the same blocks multiple times.

Types

type ChildrenTraverser

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

ChildrenTraverser can be used to walk the dag in direction of the tips (future cone).

func NewChildrenTraverser

func NewChildrenTraverser(childrenTraverserStorage ChildrenTraverserStorage) *ChildrenTraverser

NewChildrenTraverser create a new traverser to traverse the children (future cone).

func (*ChildrenTraverser) Traverse

func (t *ChildrenTraverser) Traverse(ctx context.Context, startBlockID iotago.BlockID, condition Predicate, consumer Consumer, walkAlreadyDiscovered bool) error

Traverse starts to traverse the children (future cone) of the given start block until the traversal stops due to no more blocks passing the given condition. It is unsorted BFS because the children are not ordered in the database.

type ChildrenTraverserStorage

type ChildrenTraverserStorage interface {
	CachedBlockMetadata(blockID iotago.BlockID) (*storage.CachedMetadata, error)
	SolidEntryPointsContain(blockID iotago.BlockID) (bool, error)
	ChildrenBlockIDs(blockID iotago.BlockID, iteratorOptions ...storage.IteratorOption) (iotago.BlockIDs, error)
}

ChildrenTraverserStorage provides the interface to the used storage in the ChildrenTraverser.

type ConcurrentParentsTraverser

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

ConcurrentParentsTraverser can be used to walk the dag in a multihreaded but unsorted way in direction of the parents (past cone).

func NewConcurrentParentsTraverser

func NewConcurrentParentsTraverser(parentsTraverserStorage ParentsTraverserStorage, parallelism ...int) *ConcurrentParentsTraverser

NewConcurrentParentsTraverser creates a new traverser that can be used to walk the dag in a multihreaded but unsorted way in direction of the parents (past cone).

func (*ConcurrentParentsTraverser) Traverse

func (t *ConcurrentParentsTraverser) Traverse(ctx context.Context, parents iotago.BlockIDs, condition Predicate, consumer Consumer, onMissingParent OnMissingParent, onSolidEntryPoint OnSolidEntryPoint, traverseSolidEntryPoints bool) error

Traverse starts to traverse the parents (past cone) in a multihreaded but unsorted way in direction of the parents. the traversal stops due to no more blocks passing the given condition. Caution: not in DFS order.

type Consumer

type Consumer func(cachedBlockMeta *storage.CachedMetadata) error

Consumer consumes the given block metadata during traversal.

type MemcachedChildrenTraverserStorage

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

func NewMemcachedChildrenTraverserStorage

func NewMemcachedChildrenTraverserStorage(childrenTraverserStorage ChildrenTraverserStorage, metadataMemcache *storage.MetadataMemcache) *MemcachedChildrenTraverserStorage

func (*MemcachedChildrenTraverserStorage) CachedBlockMetadata

func (m *MemcachedChildrenTraverserStorage) CachedBlockMetadata(blockID iotago.BlockID) (*storage.CachedMetadata, error)

func (*MemcachedChildrenTraverserStorage) ChildrenBlockIDs

func (m *MemcachedChildrenTraverserStorage) ChildrenBlockIDs(blockID iotago.BlockID, iteratorOptions ...storage.IteratorOption) (iotago.BlockIDs, error)

func (*MemcachedChildrenTraverserStorage) Cleanup

func (m *MemcachedChildrenTraverserStorage) Cleanup(forceRelease bool)

type MemcachedParentsTraverserStorage

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

func NewMemcachedParentsTraverserStorage

func NewMemcachedParentsTraverserStorage(parentsTraverserStorage ParentsTraverserStorage, metadataMemcache *storage.MetadataMemcache) *MemcachedParentsTraverserStorage

func (*MemcachedParentsTraverserStorage) CachedBlockMetadata

func (m *MemcachedParentsTraverserStorage) CachedBlockMetadata(blockID iotago.BlockID) (*storage.CachedMetadata, error)

func (*MemcachedParentsTraverserStorage) Cleanup

func (m *MemcachedParentsTraverserStorage) Cleanup(forceRelease bool)

func (*MemcachedParentsTraverserStorage) SolidEntryPointsContain

func (m *MemcachedParentsTraverserStorage) SolidEntryPointsContain(blockID iotago.BlockID) (bool, error)

func (*MemcachedParentsTraverserStorage) SolidEntryPointsIndex

func (m *MemcachedParentsTraverserStorage) SolidEntryPointsIndex(blockID iotago.BlockID) (iotago.MilestoneIndex, bool, error)

type MemcachedTraverserStorage

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

func NewMemcachedTraverserStorage

func NewMemcachedTraverserStorage(traverserStorage TraverserStorage, metadataMemcache *storage.MetadataMemcache) *MemcachedTraverserStorage

func (*MemcachedTraverserStorage) CachedBlockMetadata

func (m *MemcachedTraverserStorage) CachedBlockMetadata(blockID iotago.BlockID) (*storage.CachedMetadata, error)

func (*MemcachedTraverserStorage) ChildrenBlockIDs

func (m *MemcachedTraverserStorage) ChildrenBlockIDs(blockID iotago.BlockID, iteratorOptions ...storage.IteratorOption) (iotago.BlockIDs, error)

func (*MemcachedTraverserStorage) Cleanup

func (m *MemcachedTraverserStorage) Cleanup(forceRelease bool)

func (*MemcachedTraverserStorage) SolidEntryPointsContain

func (m *MemcachedTraverserStorage) SolidEntryPointsContain(blockID iotago.BlockID) (bool, error)

func (*MemcachedTraverserStorage) SolidEntryPointsIndex

func (m *MemcachedTraverserStorage) SolidEntryPointsIndex(blockID iotago.BlockID) (iotago.MilestoneIndex, bool, error)

type OnMissingParent

type OnMissingParent func(parentBlockID iotago.BlockID) error

OnMissingParent gets called when during traversal a parent is missing.

type OnSolidEntryPoint

type OnSolidEntryPoint func(blockID iotago.BlockID) error

OnSolidEntryPoint gets called when during traversal the startBlock or parent is a solid entry point.

type ParentsTraverser

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

ParentsTraverser can be used to walk the dag in direction of the parents (past cone).

func NewParentsTraverser

func NewParentsTraverser(parentsTraverserStorage ParentsTraverserStorage) *ParentsTraverser

NewParentsTraverser create a new traverser to traverse the parents (past cone).

func (*ParentsTraverser) Traverse

func (t *ParentsTraverser) Traverse(ctx context.Context, parents iotago.BlockIDs, condition Predicate, consumer Consumer, onMissingParent OnMissingParent, onSolidEntryPoint OnSolidEntryPoint, traverseSolidEntryPoints bool) error

Traverse starts to traverse the parents (past cone) in the given order until the traversal stops due to no more blocks passing the given condition. It is a DFS of the paths of the parents one after another. Caution: condition func is not in DFS order.

type ParentsTraverserInterface

type ParentsTraverserInterface interface {
	Traverse(ctx context.Context, parents iotago.BlockIDs, condition Predicate, consumer Consumer, onMissingParent OnMissingParent, onSolidEntryPoint OnSolidEntryPoint, traverseSolidEntryPoints bool) error
}

type ParentsTraverserStorage

type ParentsTraverserStorage interface {
	CachedBlockMetadata(blockID iotago.BlockID) (*storage.CachedMetadata, error)
	SolidEntryPointsContain(blockID iotago.BlockID) (bool, error)
	SolidEntryPointsIndex(blockID iotago.BlockID) (iotago.MilestoneIndex, bool, error)
}

ParentsTraverserStorage provides the interface to the used storage in the ParentsTraverser.

type Predicate

type Predicate func(cachedBlockMeta *storage.CachedMetadata) (bool, error)

Predicate defines whether a traversal should continue or not.

type TraverserStorage

type TraverserStorage interface {
	ParentsTraverserStorage
	ChildrenTraverserStorage
}

TraverserStorage provides the interface to the used storage in the ParentsTraverser and ChildrenTraverser.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL