dag

package
v2.0.1 Latest Latest
Warning

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

 Go to latest Published: Oct 5, 2023 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.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.