interval

Documentation

Index

• func Add(db database.KeyValueWriterDeleter, tree *Tree, lastAcceptedHeight uint64, ...) (bool, error)
• func DeleteBlock(db database.KeyValueDeleter, height uint64) error
• func DeleteInterval(db database.KeyValueDeleter, upperBound uint64) error
• func GetBlock(db database.KeyValueReader, height uint64) ([]byte, error)
• func GetBlockIterator(db database.Iteratee) database.Iterator
• func GetBlockIteratorWithStart(db database.Iteratee, height uint64) database.Iterator
• func PutBlock(db database.KeyValueWriter, height uint64, bytes []byte) error
• func PutInterval(db database.KeyValueWriter, upperBound uint64, lowerBound uint64) error
• func Remove(db database.KeyValueWriterDeleter, tree *Tree, height uint64) error
• type Interval
  • func GetIntervals(db database.Iteratee) ([]*Interval, error)
  • func (i *Interval) AdjacentToLowerBound(height uint64) bool
  • func (i *Interval) AdjacentToUpperBound(height uint64) bool
  • func (i *Interval) Contains(height uint64) bool
  • func (i *Interval) Less(other *Interval) bool
• type Tree
  • func NewTree(db database.Iteratee) (*Tree, error)
  • func (t *Tree) Add(db database.KeyValueWriterDeleter, height uint64) error
  • func (t *Tree) Contains(height uint64) bool
  • func (t *Tree) Flatten() []*Interval
  • func (t *Tree) Len() uint64
  • func (t *Tree) Remove(db database.KeyValueWriterDeleter, height uint64) error

Functions

func Add

func Add(
	db database.KeyValueWriterDeleter,
	tree *Tree,
	lastAcceptedHeight uint64,
	height uint64,
	blkBytes []byte,
) (bool, error)

Add the block to the tree and return if the parent block should be fetched, but wasn't desired before.

func DeleteBlock

func DeleteBlock(db database.KeyValueDeleter, height uint64) error

func DeleteInterval

func DeleteInterval(db database.KeyValueDeleter, upperBound uint64) error

func GetBlock

func GetBlock(db database.KeyValueReader, height uint64) ([]byte, error)

func GetBlockIterator

func GetBlockIterator(db database.Iteratee) database.Iterator

GetBlockIterator returns a block iterator that will produce values corresponding to persisted blocks in order of increasing height.

func GetBlockIteratorWithStart

func GetBlockIteratorWithStart(db database.Iteratee, height uint64) database.Iterator

GetBlockIterator returns a block iterator that will produce values corresponding to persisted blocks in order of increasing height starting at [height].

func PutBlock

func PutBlock(db database.KeyValueWriter, height uint64, bytes []byte) error

func PutInterval

func PutInterval(db database.KeyValueWriter, upperBound uint64, lowerBound uint64) error

func Remove

func Remove(
	db database.KeyValueWriterDeleter,
	tree *Tree,
	height uint64,
) error

Remove the block from the tree.

Types

type Interval

type Interval struct {
	LowerBound uint64
	UpperBound uint64
}

func GetIntervals

func GetIntervals(db database.Iteratee) ([]*Interval, error)

func (*Interval) AdjacentToLowerBound

func (i *Interval) AdjacentToLowerBound(height uint64) bool

AdjacentToLowerBound returns true if height is 1 less than lowerBound.

func (*Interval) AdjacentToUpperBound

func (i *Interval) AdjacentToUpperBound(height uint64) bool

AdjacentToUpperBound returns true if height is 1 greater than upperBound.

func (*Interval) Contains

func (i *Interval) Contains(height uint64) bool

func (*Interval) Less

func (i *Interval) Less(other *Interval) bool

type Tree

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

Tree implements a set of numbers by tracking intervals. It supports adding and removing new values. It also allows checking if a value is included in the set.

Tree is more space efficient than a map implementation if the values that it contains are continuous. The tree takes O(n) space where n is the number of continuous ranges that have been inserted into the tree.

Add, Remove, and Contains all run in O(log n) where n is the number of continuous ranges that have been inserted into the tree.

func NewTree

func NewTree(db database.Iteratee) (*Tree, error)

NewTree creates a new interval tree from the provided database.

It is assumed that persisted intervals are non-overlapping. Providing a database with overlapping intervals will result in undefined behavior of the structure.

func (*Tree) Add

func (t *Tree) Add(db database.KeyValueWriterDeleter, height uint64) error

func (*Tree) Contains

func (t *Tree) Contains(height uint64) bool

func (*Tree) Flatten

func (t *Tree) Flatten() []*Interval

func (*Tree) Len

func (t *Tree) Len() uint64

Len returns the number of heights in the tree; not the number of intervals.

Because Len returns a uint64 and is describing the number of values in the range of uint64s, it will return 0 if the tree contains the full interval [0, MaxUint64].

func (*Tree) Remove

func (t *Tree) Remove(db database.KeyValueWriterDeleter, height uint64) error