rtree

package
v1.1.0-beta.0...-9c4fa27 Latest Latest
Warning

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

 Go to latest Published: Jan 7, 2026 License: Apache-2.0, Apache-2.0 Imports: 15 Imported by: 0

Documentation

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func NeedsMerge 

func NeedsMerge(left, right *RangeStats, splitSizeBytes, splitKeyCount uint64) bool

NeedsMerge checks whether two ranges needs to be merged.

func ZapRanges 

func ZapRanges(ranges []KeyRange) zapcore.Field

ZapRanges make zap fields for logging Range slice.

Types

type DeletedRange 

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

type KeyRange 

type KeyRange struct {
	StartKey []byte
	EndKey   []byte
}

KeyRange represents a origin key range.

func (*KeyRange) Contains 

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

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

func (*KeyRange) ContainsRange 

func (rg *KeyRange) ContainsRange(startKey, endKey []byte) bool

ContainsRange check if the range contains the region's key range.

func (*KeyRange) Intersect 

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

Intersect returns intersect range in the tree.

func (KeyRange) String 

func (rg KeyRange) String() string

String formats a range to a string.

type ProgressRange 

type ProgressRange struct {
	Res    RangeTree
	Origin KeyRange
}

func (*ProgressRange) Less 

func (pr *ProgressRange) Less(than *ProgressRange) bool

Less impls btree.Item.

type ProgressRangeTree 

type ProgressRangeTree struct {
	*btree.BTreeG[*ProgressRange]
	// contains filtered or unexported fields
}

ProgressRangeTree is a sorted tree for ProgressRanges. All the progress ranges it sorted do not overlap.

func NewProgressRangeTree 

func NewProgressRangeTree(metaWriter *metautil.MetaWriter, skipChecksum bool) ProgressRangeTree

NewProgressRangeTree returns an empty range tree.

func (*ProgressRangeTree) FindContained 

func (rangeTree *ProgressRangeTree) FindContained(startKey, endKey []byte) (*ProgressRange, error)

FindContained finds if there is a progress range containing the key range [startKey, endKey).

func (*ProgressRangeTree) GetChecksumMap 

func (rangeTree *ProgressRangeTree) GetChecksumMap() map[int64]*metautil.ChecksumStats

GetChecksumMap get the checksum map from physical ID to checksum.

func (*ProgressRangeTree) GetIncompleteRanges 

func (rangeTree *ProgressRangeTree) GetIncompleteRanges() ([]*kvrpcpb.KeyRange, error)

func (*ProgressRangeTree) Insert 

func (rangeTree *ProgressRangeTree) Insert(pr *ProgressRange) error

Insert inserts a ProgressRange into the tree, it will return an error if there is a overlapping range.

func (*ProgressRangeTree) SetCallBack 

func (rangeTree *ProgressRangeTree) SetCallBack(callback func())

SetCallBack set the complete call back to update the progress.

func (*ProgressRangeTree) UpdateChecksum 

func (rangeTree *ProgressRangeTree) UpdateChecksum(physicalID int64, crc, kvs, bytes uint64)

type Range 

type Range struct {
	KeyRange
	Files []*backuppb.File
}

Range represents a backup response.

func (*Range) BytesAndKeys 

func (rg *Range) BytesAndKeys() (bytes, keys uint64)

BytesAndKeys returns total bytes and keys in a range.

func (*Range) Less 

func (rg *Range) Less(ta *Range) bool

Less impls btree.Item.

type RangeStats 

type RangeStats struct {
	Range
	Size  uint64
	Count uint64
}

RangeStats represents a restore merge result.

func (*RangeStats) Less 

func (rg *RangeStats) Less(ta *RangeStats) bool

Less impls btree.Item.

type RangeStatsTree 

type RangeStatsTree struct {
	*btree.BTreeG[*RangeStats]
}

func NewRangeStatsTree 

func NewRangeStatsTree() RangeStatsTree

func (*RangeStatsTree) InsertRange 

func (rangeTree *RangeStatsTree) InsertRange(rg *Range, rangeSize, rangeCount uint64) *RangeStats

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

func (*RangeStatsTree) MergedRanges 

func (rangeTree *RangeStatsTree) MergedRanges(splitSizeBytes, splitKeyCount uint64) []RangeStats

MergedRanges output the sortedRanges having merged according to given `splitSizeBytes` and `splitKeyCount`.

type RangeTree 

type RangeTree struct {
	*btree.BTreeG[*Range]

	PhysicalID int64
}

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 NewRangeTreeWithFreeListG 

func NewRangeTreeWithFreeListG(physicalID int64, f *btree.FreeListG[*Range]) RangeTree

NewRangeTreeWithFreeListG returns an empty range tree with the specified free list

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,
) []*kvrpcpb.KeyRange

GetIncompleteRange returns missing range covered by startKey and endKey.

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 []*backuppb.File,
)

Put forms a range and inserts it into tree.

func (*RangeTree) PutForce 

func (rangeTree *RangeTree) PutForce(
	startKey, endKey []byte, files []*backuppb.File, force bool,
) bool

PutForce forms a range and inserts it into tree without force.

func (*RangeTree) Update 

func (rangeTree *RangeTree) Update(rg Range) bool

Update inserts range into tree and delete overlapping ranges.

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.