Documentation
¶
Overview ¶
Package linear implements the algorithm for extending partial dag order into linear order.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type CommonRandomPermutation ¶
type CommonRandomPermutation struct {
// contains filtered or unexported fields
}
CommonRandomPermutation is a type responsible for iterating units on level by the mean of a Common Random Permutation.
func NewCommonRandomPermutation ¶
func NewCommonRandomPermutation(dag gomel.Dag, randomSource gomel.RandomSource, crpFixedPrefix uint16) *CommonRandomPermutation
NewCommonRandomPermutation creates an instance of the CommonRandomPermutation type.
func (*CommonRandomPermutation) CRPIterate ¶
func (crp *CommonRandomPermutation) CRPIterate(level int, previousTU gomel.Unit, work func(gomel.Unit) bool) bool
CRPIterate iterates over all the prime units on a given level in random order. It calls the given work function on each of the units until the function returns false or the contents run out. The underlying random permutation of units is generated in two steps (1) the prefix is based only on the previous timing unit and hashes of units (2) the suffix is computed using the random source The second part of the permutation is being calculated only when needed, i.e. the given work function returns true on all the units in the prefix.
The function itself returns
- false when generating the suffix of the permutation failed (because the dag hasn't reached a level high enough to reveal the randomBytes needed)
- true otherwise
type Extender ¶
type Extender struct {
// contains filtered or unexported fields
}
Extender is a type that implements an algorithm that extends order of units provided by an instance of a Dag to a linear order.
func NewExtender ¶
func NewExtender(dag gomel.Dag, rs gomel.RandomSource, conf config.Config, log zerolog.Logger) *Extender
NewExtender constructs an iterator like object that is responsible of ordering units in a given dag.
func (*Extender) NextRound ¶
func (ext *Extender) NextRound() *TimingRound
NextRound tries to pick the next timing unit. Returns nil if it cannot be decided yet.
type ExtenderService ¶
type ExtenderService struct {
// contains filtered or unexported fields
}
ExtenderService is a component working on a dag that extends a partial order of units defined by dag to a linear order. ExtenderService should be notified, by the means of its Notify method, when it should try to perform its task. If successful, ExtenderService collects all the units belonging to newest timing round, and sends them to the output channel.
func NewExtenderService ¶
func NewExtenderService(dag gomel.Dag, rs gomel.RandomSource, conf config.Config, output chan<- []gomel.Unit, log zerolog.Logger) *ExtenderService
NewExtenderService constructs an extender working on the given dag and sending rounds of ordered units to the given output.
func (*ExtenderService) Notify ¶
func (ext *ExtenderService) Notify()
Notify ExtenderService to attempt choosing next timing units.
type TimingRound ¶
type TimingRound struct {
// contains filtered or unexported fields
}
TimingRound represents a single round of ordered units.
func (*TimingRound) OrderedUnits ¶
func (tr *TimingRound) OrderedUnits() []gomel.Unit
OrderedUnits returns all units ordered in this timing round.
Source Files