rtree

Documentation

Index

• type Range
  • func (rg *Range) Contains(key []byte) bool
  • func (rg *Range) Intersect(start, end []byte) (subStart, subEnd []byte, isIntersect bool)
  • func (rg *Range) Less(than btree.Item) bool
  • func (rg *Range) String() string
• type RangeTree
  • func NewRangeTree() RangeTree
  • func (rangeTree *RangeTree) Find(rg *Range) *Range
  • func (rangeTree *RangeTree) GetIncompleteRange(startKey, endKey []byte) []Range
  • func (rangeTree *RangeTree) GetSortedRanges() []Range
  • func (rangeTree *RangeTree) InsertRange(rg Range) *Range
  • func (rangeTree *RangeTree) Put(startKey, endKey []byte, files []*backup.File)
  • func (rangeTree *RangeTree) Update(rg Range)

Types

type Range

type Range struct {
	StartKey []byte
	EndKey   []byte
	Files    []*backup.File
}

Range represents a backup response.

func (*Range) Contains

func (rg *Range) Contains(key []byte) bool

Contains check if the range contains the given key, [start, end).

func (*Range) Intersect

func (rg *Range) Intersect(
	start, end []byte,
) (subStart, subEnd []byte, isIntersect bool)

Intersect returns intersect range in the tree.

func (*Range) Less

func (rg *Range) Less(than btree.Item) bool

Less impls btree.Item.

func (*Range) String

func (rg *Range) String() string

String formats a range to a string.

type RangeTree

type RangeTree struct {
	*btree.BTree
}

RangeTree is sorted tree for Ranges. All the ranges it stored do not overlap.

func NewRangeTree

func NewRangeTree() RangeTree

NewRangeTree returns an empty range tree.

func (*RangeTree) Find

func (rangeTree *RangeTree) Find(rg *Range) *Range

Find is a helper function to find an item that contains the range start key.

func (*RangeTree) GetIncompleteRange

func (rangeTree *RangeTree) GetIncompleteRange(
	startKey, endKey []byte,
) []Range

GetIncompleteRange returns missing range covered by startKey and endKey.

func (*RangeTree) GetSortedRanges

func (rangeTree *RangeTree) GetSortedRanges() []Range

GetSortedRanges collects and returns sorted ranges.

func (*RangeTree) InsertRange

func (rangeTree *RangeTree) InsertRange(rg Range) *Range

InsertRange inserts ranges into the range tree. It returns a non-nil range if there are soe overlapped ranges.

func (*RangeTree) Put

func (rangeTree *RangeTree) Put(
	startKey, endKey []byte, files []*backup.File,
)

Put forms a range and inserts it into tree.

func (*RangeTree) Update

func (rangeTree *RangeTree) Update(rg Range)

Update inserts range into tree and delete overlapping ranges.