dag

package
v1.2.1 Latest Latest
Warning

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

 Go to latest Published: Apr 29, 2022 License: Apache-2.0 Imports: 15 Imported by: 0

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 added in v1.0.5 

func ConeRootIndexes(ctx context.Context, parentsTraverserStorage ParentsTraverserStorage, cachedMsgMeta *storage.CachedMetadata, cmi milestone.Index) (youngestConeRootIndex milestone.Index, oldestConeRootIndex milestone.Index, err error)

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

func TraverseChildren added in v1.0.0 

func TraverseChildren(ctx context.Context, childrenTraverserStorage ChildrenTraverserStorage, startMessageID hornet.MessageID, condition Predicate, consumer Consumer, walkAlreadyDiscovered bool) error

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

func TraverseParents added in v1.0.0 

func TraverseParents(ctx context.Context, parentsTraverserStorage ParentsTraverserStorage, parents hornet.MessageIDs, 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 messages 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 TraverseParentsOfMessage added in v1.0.0 

func TraverseParentsOfMessage(ctx context.Context, parentsTraverserStorage ParentsTraverserStorage, startMessageID hornet.MessageID, condition Predicate, consumer Consumer, onMissingParent OnMissingParent, onSolidEntryPoint OnSolidEntryPoint, traverseSolidEntryPoints bool) error

TraverseParentsOfMessage starts to traverse the parents (past cone) of the given start message until the traversal stops due to no more messages 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 added in v1.0.0 

func UpdateConeRootIndexes(ctx context.Context, traverserStorage TraverserStorage, messageIDs hornet.MessageIDs, cmi milestone.Index) error

UpdateConeRootIndexes updates the cone root indexes of the future cone of all given messages. all the messages 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 messages 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 messages multiple times.

Types

type ChildrenTraverser added in v1.0.0 

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 added in v1.0.0 

func NewChildrenTraverser(childrenTraverserStorage ChildrenTraverserStorage) *ChildrenTraverser

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

func (*ChildrenTraverser) Traverse added in v1.0.0 

func (t *ChildrenTraverser) Traverse(ctx context.Context, startMessageID hornet.MessageID, condition Predicate, consumer Consumer, walkAlreadyDiscovered bool) error

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

type ChildrenTraverserStorage added in v1.2.0 

type ChildrenTraverserStorage interface {
	CachedMessageMetadata(messageID hornet.MessageID) (*storage.CachedMetadata, error)
	ChildrenMessageIDs(messageID hornet.MessageID, iteratorOptions ...storage.IteratorOption) (hornet.MessageIDs, error)
}

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

type ConcurrentParentsTraverser added in v1.2.0 

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 added in v1.2.0 

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 added in v1.2.0 

func (t *ConcurrentParentsTraverser) Traverse(ctx context.Context, parents hornet.MessageIDs, 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 messages passing the given condition. Caution: not in DFS order

type Consumer 

type Consumer func(cachedMsgMeta *storage.CachedMetadata) error

Consumer consumes the given message metadata during traversal.

type MemcachedChildrenTraverserStorage added in v1.2.0 

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

func NewMemcachedChildrenTraverserStorage added in v1.2.0 

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

func (*MemcachedChildrenTraverserStorage) CachedMessageMetadata added in v1.2.0 

func (m *MemcachedChildrenTraverserStorage) CachedMessageMetadata(messageID hornet.MessageID) (*storage.CachedMetadata, error)

func (*MemcachedChildrenTraverserStorage) ChildrenMessageIDs added in v1.2.0 

func (m *MemcachedChildrenTraverserStorage) ChildrenMessageIDs(messageID hornet.MessageID, iteratorOptions ...storage.IteratorOption) (hornet.MessageIDs, error)

func (*MemcachedChildrenTraverserStorage) Cleanup added in v1.2.0 

func (m *MemcachedChildrenTraverserStorage) Cleanup(forceRelease bool)

type MemcachedParentsTraverserStorage added in v1.2.0 

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

func NewMemcachedParentsTraverserStorage added in v1.2.0 

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

func (*MemcachedParentsTraverserStorage) CachedMessageMetadata added in v1.2.0 

func (m *MemcachedParentsTraverserStorage) CachedMessageMetadata(messageID hornet.MessageID) (*storage.CachedMetadata, error)

func (*MemcachedParentsTraverserStorage) Cleanup added in v1.2.0 

func (m *MemcachedParentsTraverserStorage) Cleanup(forceRelease bool)

func (*MemcachedParentsTraverserStorage) SolidEntryPointsContain added in v1.2.0 

func (m *MemcachedParentsTraverserStorage) SolidEntryPointsContain(messageID hornet.MessageID) (bool, error)

func (*MemcachedParentsTraverserStorage) SolidEntryPointsIndex added in v1.2.0 

func (m *MemcachedParentsTraverserStorage) SolidEntryPointsIndex(messageID hornet.MessageID) (milestone.Index, bool, error)

type MemcachedTraverserStorage added in v1.2.0 

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

func NewMemcachedTraverserStorage added in v1.2.0 

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

func (*MemcachedTraverserStorage) CachedMessageMetadata added in v1.2.0 

func (m *MemcachedTraverserStorage) CachedMessageMetadata(messageID hornet.MessageID) (*storage.CachedMetadata, error)

func (*MemcachedTraverserStorage) ChildrenMessageIDs added in v1.2.0 

func (m *MemcachedTraverserStorage) ChildrenMessageIDs(messageID hornet.MessageID, iteratorOptions ...storage.IteratorOption) (hornet.MessageIDs, error)

func (*MemcachedTraverserStorage) Cleanup added in v1.2.0 

func (m *MemcachedTraverserStorage) Cleanup(forceRelease bool)

func (*MemcachedTraverserStorage) SolidEntryPointsContain added in v1.2.0 

func (m *MemcachedTraverserStorage) SolidEntryPointsContain(messageID hornet.MessageID) (bool, error)

func (*MemcachedTraverserStorage) SolidEntryPointsIndex added in v1.2.0 

func (m *MemcachedTraverserStorage) SolidEntryPointsIndex(messageID hornet.MessageID) (milestone.Index, bool, error)

type OnMissingParent added in v1.0.0 

type OnMissingParent func(parentMessageID hornet.MessageID) error

OnMissingParent gets called when during traversal a parent is missing.

type OnSolidEntryPoint added in v0.4.1 

type OnSolidEntryPoint func(messageID hornet.MessageID) error

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

type ParentsTraverser added in v1.2.0 

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 added in v1.2.0 

func NewParentsTraverser(parentsTraverserStorage ParentsTraverserStorage) *ParentsTraverser

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

func (*ParentsTraverser) Traverse added in v1.2.0 

func (t *ParentsTraverser) Traverse(ctx context.Context, parents hornet.MessageIDs, 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 messages 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 added in v1.2.0 

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

type ParentsTraverserStorage added in v1.2.0 

type ParentsTraverserStorage interface {
	CachedMessageMetadata(messageID hornet.MessageID) (*storage.CachedMetadata, error)
	SolidEntryPointsContain(messageID hornet.MessageID) (bool, error)
	SolidEntryPointsIndex(messageID hornet.MessageID) (milestone.Index, bool, error)
}

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

type Predicate 

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

Predicate defines whether a traversal should continue or not.

type TraverserStorage added in v1.2.0 

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.