accel

package
v0.0.0-...-5477640 Latest Latest
Warning

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

 Go to latest Published: Dec 17, 2024 License: Apache-2.0, MIT Imports: 26 Imported by: 0

Documentation

Overview

Package accel implements a proxy for gasket based accel devices.

Index

Constants

View Source 
const (
	// minDegree is the minimum degree of an internal node in a Set B-tree.
	//
	//	- Any non-root node has at least minDegree-1 segments.
	//
	//	- Any non-root internal (non-leaf) node has at least minDegree children.
	//
	//	- The root node may have fewer than minDegree-1 segments, but it may
	// only have 0 segments if the tree is empty.
	//
	// Our implementation requires minDegree >= 3. Higher values of minDegree
	// usually improve performance, but increase memory usage for small sets.
	DevAddrminDegree = 3

	DevAddrmaxDegree = 2 * DevAddrminDegree
)
View Source 
const DevAddrtrackGaps = 0

trackGaps is an optional parameter.

If trackGaps is 1, the Set will track maximum gap size recursively, enabling the GapIterator.{Prev,Next}LargeEnoughGap functions. In this case, Key must be an unsigned integer.

trackGaps must be 0 or 1.

Variables

This section is empty.

Functions

func DevAddrzeroNodeSlice 

func DevAddrzeroNodeSlice(slice []*DevAddrnode)

func DevAddrzeroValueSlice 

func DevAddrzeroValueSlice(slice []pinnedAccelMem)

func RegisterTPUDevice 

func RegisterTPUDevice(vfsObj *vfs.VirtualFilesystem, minor uint32, lite bool) error

RegisterTPUDevice registers all devices implemented by this package in vfsObj.

Types

type DevAddrFlatSegment 

type DevAddrFlatSegment struct {
	Start uint64
	End   uint64
	Value pinnedAccelMem
}

FlatSegment represents a segment as a single object. FlatSegment is used as an intermediate representation for save/restore and tests.

+stateify savable

func (*DevAddrFlatSegment) StateFields 

func (d *DevAddrFlatSegment) StateFields() []string

func (*DevAddrFlatSegment) StateLoad 

func (d *DevAddrFlatSegment) StateLoad(ctx context.Context, stateSourceObject state.Source)

+checklocksignore

func (*DevAddrFlatSegment) StateSave 

func (d *DevAddrFlatSegment) StateSave(stateSinkObject state.Sink)

+checklocksignore

func (*DevAddrFlatSegment) StateTypeName 

func (d *DevAddrFlatSegment) StateTypeName() string

type DevAddrGapIterator 

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

A GapIterator is conceptually one of:

  • A pointer to a position between two segments, before the first segment, or after the last segment in a set, called a *gap*; or

  • A terminal iterator, which is a sentinel indicating that the end of iteration has been reached.

Note that the gap between two adjacent segments exists (iterators to it are non-terminal), but has a length of zero. GapIterator.IsEmpty returns true for such gaps. An empty set contains a single gap, spanning the entire range of the set's keys.

GapIterators are copyable values and are meaningfully equality-comparable. The zero value of GapIterator is a terminal iterator.

Unless otherwise specified, any mutation of a set invalidates all existing iterators into the set.

func (DevAddrGapIterator) End 

func (gap DevAddrGapIterator) End() uint64

End is equivalent to Range().End, but should be preferred if only the end of the range is needed.

func (DevAddrGapIterator) IsEmpty 

func (gap DevAddrGapIterator) IsEmpty() bool

IsEmpty returns true if the iterated gap is empty (that is, the "gap" is between two adjacent segments.)

func (DevAddrGapIterator) NextGap 

func (gap DevAddrGapIterator) NextGap() DevAddrGapIterator

NextGap returns the iterated gap's successor. If no such gap exists, NextGap returns a terminal iterator.

func (DevAddrGapIterator) NextLargeEnoughGap 

func (gap DevAddrGapIterator) NextLargeEnoughGap(minSize uint64) DevAddrGapIterator

NextLargeEnoughGap returns the iterated gap's first next gap with larger length than minSize. If not found, return a terminal gap iterator (does NOT include this gap itself).

Precondition: trackGaps must be 1.

func (DevAddrGapIterator) NextSegment 

func (gap DevAddrGapIterator) NextSegment() DevAddrIterator

NextSegment returns the segment immediately after the iterated gap. If no such segment exists, NextSegment returns a terminal iterator.

func (DevAddrGapIterator) Ok 

func (gap DevAddrGapIterator) Ok() bool

Ok returns true if the iterator is not terminal. All other methods are only valid for non-terminal iterators.

func (DevAddrGapIterator) PrevGap 

func (gap DevAddrGapIterator) PrevGap() DevAddrGapIterator

PrevGap returns the iterated gap's predecessor. If no such gap exists, PrevGap returns a terminal iterator.

func (DevAddrGapIterator) PrevLargeEnoughGap 

func (gap DevAddrGapIterator) PrevLargeEnoughGap(minSize uint64) DevAddrGapIterator

PrevLargeEnoughGap returns the iterated gap's first prev gap with larger or equal length than minSize. If not found, return a terminal gap iterator (does NOT include this gap itself).

Precondition: trackGaps must be 1.

func (DevAddrGapIterator) PrevSegment 

func (gap DevAddrGapIterator) PrevSegment() DevAddrIterator

PrevSegment returns the segment immediately before the iterated gap. If no such segment exists, PrevSegment returns a terminal iterator.

func (DevAddrGapIterator) Range 

func (gap DevAddrGapIterator) Range() DevAddrRange

Range returns the range spanned by the iterated gap.

func (DevAddrGapIterator) Start 

func (gap DevAddrGapIterator) Start() uint64

Start is equivalent to Range().Start, but should be preferred if only the start of the range is needed.

type DevAddrIterator 

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

A Iterator is conceptually one of:

  • A pointer to a segment in a set; or

  • A terminal iterator, which is a sentinel indicating that the end of iteration has been reached.

Iterators are copyable values and are meaningfully equality-comparable. The zero value of Iterator is a terminal iterator.

Unless otherwise specified, any mutation of a set invalidates all existing iterators into the set.

func DevAddrsegmentAfterPosition 

func DevAddrsegmentAfterPosition(n *DevAddrnode, i int) DevAddrIterator

segmentAfterPosition returns the successor segment of the position given by n.children[i], which may or may not contain a child. If no such segment exists, segmentAfterPosition returns a terminal iterator.

func DevAddrsegmentBeforePosition 

func DevAddrsegmentBeforePosition(n *DevAddrnode, i int) DevAddrIterator

segmentBeforePosition returns the predecessor segment of the position given by n.children[i], which may or may not contain a child. If no such segment exists, segmentBeforePosition returns a terminal iterator.

func (DevAddrIterator) End 

func (seg DevAddrIterator) End() uint64

End is equivalent to Range().End, but should be preferred if only the end of the range is needed.

func (DevAddrIterator) NextGap 

func (seg DevAddrIterator) NextGap() DevAddrGapIterator

NextGap returns the gap immediately after the iterated segment.

func (DevAddrIterator) NextNonEmpty 

func (seg DevAddrIterator) NextNonEmpty() (DevAddrIterator, DevAddrGapIterator)

NextNonEmpty returns the iterated segment's successor if it is adjacent, or the gap after the iterated segment otherwise. If seg.End() == Functions.MaxKey(), NextNonEmpty will return two terminal iterators. Otherwise, exactly one of the iterators returned by NextNonEmpty will be non-terminal.

func (DevAddrIterator) NextSegment 

func (seg DevAddrIterator) NextSegment() DevAddrIterator

NextSegment returns the iterated segment's successor. If there is no succeeding segment, NextSegment returns a terminal iterator.

func (DevAddrIterator) Ok 

func (seg DevAddrIterator) Ok() bool

Ok returns true if the iterator is not terminal. All other methods are only valid for non-terminal iterators.

func (DevAddrIterator) PrevGap 

func (seg DevAddrIterator) PrevGap() DevAddrGapIterator

PrevGap returns the gap immediately before the iterated segment.

func (DevAddrIterator) PrevNonEmpty 

func (seg DevAddrIterator) PrevNonEmpty() (DevAddrIterator, DevAddrGapIterator)

PrevNonEmpty returns the iterated segment's predecessor if it is adjacent, or the gap before the iterated segment otherwise. If seg.Start() == Functions.MinKey(), PrevNonEmpty will return two terminal iterators. Otherwise, exactly one of the iterators returned by PrevNonEmpty will be non-terminal.

func (DevAddrIterator) PrevSegment 

func (seg DevAddrIterator) PrevSegment() DevAddrIterator

PrevSegment returns the iterated segment's predecessor. If there is no preceding segment, PrevSegment returns a terminal iterator.

func (DevAddrIterator) Range 

func (seg DevAddrIterator) Range() DevAddrRange

Range returns the iterated segment's range key.

func (DevAddrIterator) SetEnd 

func (seg DevAddrIterator) SetEnd(end uint64)

SetEnd mutates the iterated segment's end. If the new end value would cause the iterated segment to overlap another segment, or would result in an invalid range, SetEnd panics. This operation does not invalidate any iterators.

func (DevAddrIterator) SetEndUnchecked 

func (seg DevAddrIterator) SetEndUnchecked(end uint64)

SetEndUnchecked mutates the iterated segment's end. This operation does not invalidate any iterators.

Preconditions: The new end must be valid:

  • end > seg.Start().
  • If seg.NextSegment().Ok(), then end <= seg.NextSegment().Start().

func (DevAddrIterator) SetRange 

func (seg DevAddrIterator) SetRange(r DevAddrRange)

SetRange mutates the iterated segment's range key. If the new range would cause the iterated segment to overlap another segment, or if the new range is invalid, SetRange panics. This operation does not invalidate any iterators.

func (DevAddrIterator) SetRangeUnchecked 

func (seg DevAddrIterator) SetRangeUnchecked(r DevAddrRange)

SetRangeUnchecked mutates the iterated segment's range key. This operation does not invalidate any iterators.

Preconditions: - r.Length() > 0. - The new range must not overlap an existing one:

  • If seg.NextSegment().Ok(), then r.end <= seg.NextSegment().Start().
  • If seg.PrevSegment().Ok(), then r.start >= seg.PrevSegment().End().

func (DevAddrIterator) SetStart 

func (seg DevAddrIterator) SetStart(start uint64)

SetStart mutates the iterated segment's start. If the new start value would cause the iterated segment to overlap another segment, or would result in an invalid range, SetStart panics. This operation does not invalidate any iterators.

func (DevAddrIterator) SetStartUnchecked 

func (seg DevAddrIterator) SetStartUnchecked(start uint64)

SetStartUnchecked mutates the iterated segment's start. This operation does not invalidate any iterators.

Preconditions: The new start must be valid:

  • start < seg.End()
  • If seg.PrevSegment().Ok(), then start >= seg.PrevSegment().End().

func (DevAddrIterator) SetValue 

func (seg DevAddrIterator) SetValue(val pinnedAccelMem)

SetValue mutates the iterated segment's value. This operation does not invalidate any iterators.

func (DevAddrIterator) Start 

func (seg DevAddrIterator) Start() uint64

Start is equivalent to Range().Start, but should be preferred if only the start of the range is needed.

func (DevAddrIterator) Value 

func (seg DevAddrIterator) Value() pinnedAccelMem

Value returns a copy of the iterated segment's value.

func (DevAddrIterator) ValuePtr 

func (seg DevAddrIterator) ValuePtr() *pinnedAccelMem

ValuePtr returns a pointer to the iterated segment's value. The pointer is invalidated if the iterator is invalidated. This operation does not invalidate any iterators.

type DevAddrRange 

type DevAddrRange struct {
	// Start is the inclusive start of the range.
	Start uint64

	// End is the exclusive end of the range.
	End uint64
}

A Range represents a contiguous range of T.

+stateify savable

func (DevAddrRange) CanSplitAt 

func (r DevAddrRange) CanSplitAt(x uint64) bool

CanSplitAt returns true if it is legal to split a segment spanning the range r at x; that is, splitting at x would produce two ranges, both of which have non-zero length.

func (DevAddrRange) Contains 

func (r DevAddrRange) Contains(x uint64) bool

Contains returns true if r contains x.

func (DevAddrRange) Intersect 

func (r DevAddrRange) Intersect(r2 DevAddrRange) DevAddrRange

Intersect returns a range consisting of the intersection between r and r2. If r and r2 do not overlap, Intersect returns a range with unspecified bounds, but for which Length() == 0.

func (DevAddrRange) IsSupersetOf 

func (r DevAddrRange) IsSupersetOf(r2 DevAddrRange) bool

IsSupersetOf returns true if r is a superset of r2; that is, the range r2 is contained within r.

func (DevAddrRange) Length 

func (r DevAddrRange) Length() uint64

Length returns the length of the range.

func (DevAddrRange) Overlaps 

func (r DevAddrRange) Overlaps(r2 DevAddrRange) bool

Overlaps returns true if r and r2 overlap.

func (*DevAddrRange) StateFields 

func (r *DevAddrRange) StateFields() []string

func (*DevAddrRange) StateLoad 

func (r *DevAddrRange) StateLoad(ctx context.Context, stateSourceObject state.Source)

+checklocksignore

func (*DevAddrRange) StateSave 

func (r *DevAddrRange) StateSave(stateSinkObject state.Sink)

+checklocksignore

func (*DevAddrRange) StateTypeName 

func (r *DevAddrRange) StateTypeName() string

func (DevAddrRange) WellFormed 

func (r DevAddrRange) WellFormed() bool

WellFormed returns true if r.Start <= r.End. All other methods on a Range require that the Range is well-formed.

type DevAddrSet 

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

A Set is a mapping of segments with non-overlapping Range keys. The zero value for a Set is an empty set. Set values are not safely movable nor copyable. Set is thread-compatible.

+stateify savable

func (*DevAddrSet) ExportSlice 

func (s *DevAddrSet) ExportSlice() []DevAddrFlatSegment

ExportSlice returns a copy of all segments in the given set, in ascending key order.

func (*DevAddrSet) Find 

func (s *DevAddrSet) Find(key uint64) (DevAddrIterator, DevAddrGapIterator)

Find returns the segment or gap whose range contains the given key. If a segment is found, the returned Iterator is non-terminal and the returned GapIterator is terminal. Otherwise, the returned Iterator is terminal and the returned GapIterator is non-terminal.

func (*DevAddrSet) FindGap 

func (s *DevAddrSet) FindGap(key uint64) DevAddrGapIterator

FindGap returns the gap containing the given key. If no such gap exists (i.e. the set contains a segment containing that key), FindGap returns a terminal iterator.

func (*DevAddrSet) FindSegment 

func (s *DevAddrSet) FindSegment(key uint64) DevAddrIterator

FindSegment returns the segment whose range contains the given key. If no such segment exists, FindSegment returns a terminal iterator.

func (*DevAddrSet) FirstGap 

func (s *DevAddrSet) FirstGap() DevAddrGapIterator

FirstGap returns the first gap in the set.

func (*DevAddrSet) FirstLargeEnoughGap 

func (s *DevAddrSet) FirstLargeEnoughGap(minSize uint64) DevAddrGapIterator

FirstLargeEnoughGap returns the first gap in the set with at least the given length. If no such gap exists, FirstLargeEnoughGap returns a terminal iterator.

Precondition: trackGaps must be 1.

func (*DevAddrSet) FirstSegment 

func (s *DevAddrSet) FirstSegment() DevAddrIterator

FirstSegment returns the first segment in the set. If the set is empty, FirstSegment returns a terminal iterator.

func (*DevAddrSet) ImportSlice 

func (s *DevAddrSet) ImportSlice(fs []DevAddrFlatSegment) error

ImportSlice initializes the given set from the given slice.

Preconditions:

  • s must be empty.
  • fs must represent a valid set (the segments in fs must have valid lengths that do not overlap).
  • The segments in fs must be sorted in ascending key order.

func (*DevAddrSet) Insert 

func (s *DevAddrSet) Insert(gap DevAddrGapIterator, r DevAddrRange, val pinnedAccelMem) DevAddrIterator

Insert inserts the given segment into the given gap. If the new segment can be merged with adjacent segments, Insert will do so. Insert returns an iterator to the segment containing the inserted value (which may have been merged with other values). All existing iterators (including gap, but not including the returned iterator) are invalidated.

If the gap cannot accommodate the segment, or if r is invalid, Insert panics.

Insert is semantically equivalent to a InsertWithoutMerging followed by a Merge, but may be more efficient. Note that there is no unchecked variant of Insert since Insert must retrieve and inspect gap's predecessor and successor segments regardless.

func (*DevAddrSet) InsertRange 

func (s *DevAddrSet) InsertRange(r DevAddrRange, val pinnedAccelMem) DevAddrIterator

InsertRange inserts the given segment into the set. If the new segment can be merged with adjacent segments, InsertRange will do so. InsertRange returns an iterator to the segment containing the inserted value (which may have been merged with other values). All existing iterators (excluding the returned iterator) are invalidated.

If the new segment would overlap an existing segment, or if r is invalid, InsertRange panics.

InsertRange searches the set to find the gap to insert into. If the caller already has the appropriate GapIterator, or if the caller needs to do additional work between finding the gap and insertion, use Insert instead.

func (*DevAddrSet) InsertWithoutMerging 

func (s *DevAddrSet) InsertWithoutMerging(gap DevAddrGapIterator, r DevAddrRange, val pinnedAccelMem) DevAddrIterator

InsertWithoutMerging inserts the given segment into the given gap and returns an iterator to the inserted segment. All existing iterators (including gap, but not including the returned iterator) are invalidated.

If the gap cannot accommodate the segment, or if r is invalid, InsertWithoutMerging panics.

func (*DevAddrSet) InsertWithoutMergingRange 

func (s *DevAddrSet) InsertWithoutMergingRange(r DevAddrRange, val pinnedAccelMem) DevAddrIterator

InsertWithoutMergingRange inserts the given segment into the set and returns an iterator to the inserted segment. All existing iterators (excluding the returned iterator) are invalidated.

If the new segment would overlap an existing segment, or if r is invalid, InsertWithoutMergingRange panics.

InsertWithoutMergingRange searches the set to find the gap to insert into. If the caller already has the appropriate GapIterator, or if the caller needs to do additional work between finding the gap and insertion, use InsertWithoutMerging instead.

func (*DevAddrSet) InsertWithoutMergingUnchecked 

func (s *DevAddrSet) InsertWithoutMergingUnchecked(gap DevAddrGapIterator, r DevAddrRange, val pinnedAccelMem) DevAddrIterator

InsertWithoutMergingUnchecked inserts the given segment into the given gap and returns an iterator to the inserted segment. All existing iterators (including gap, but not including the returned iterator) are invalidated.

Preconditions:

  • r.Start >= gap.Start().
  • r.End <= gap.End().

func (*DevAddrSet) IsEmpty 

func (s *DevAddrSet) IsEmpty() bool

IsEmpty returns true if the set contains no segments.

func (*DevAddrSet) IsEmptyRange 

func (s *DevAddrSet) IsEmptyRange(r DevAddrRange) bool

IsEmptyRange returns true iff no segments in the set overlap the given range. This is semantically equivalent to s.SpanRange(r) == 0, but may be more efficient.

func (*DevAddrSet) Isolate 

func (s *DevAddrSet) Isolate(seg DevAddrIterator, r DevAddrRange) DevAddrIterator

Isolate ensures that the given segment's range is a subset of r by splitting at r.Start and r.End if necessary, and returns an updated iterator to the bounded segment. All existing iterators (including seg, but not including the returned iterators) are invalidated.

Isolate is usually used when mutating part of a single segment, or when mutating segments in a range where the first segment is not necessarily split, making use of SplitBefore/SplitAfter complex.

Preconditions: seg.Range().Overlaps(r).

func (*DevAddrSet) LastGap 

func (s *DevAddrSet) LastGap() DevAddrGapIterator

LastGap returns the last gap in the set.

func (*DevAddrSet) LastLargeEnoughGap 

func (s *DevAddrSet) LastLargeEnoughGap(minSize uint64) DevAddrGapIterator

LastLargeEnoughGap returns the last gap in the set with at least the given length. If no such gap exists, LastLargeEnoughGap returns a terminal iterator.

Precondition: trackGaps must be 1.

func (*DevAddrSet) LastSegment 

func (s *DevAddrSet) LastSegment() DevAddrIterator

LastSegment returns the last segment in the set. If the set is empty, LastSegment returns a terminal iterator.

func (*DevAddrSet) LowerBoundGap 

func (s *DevAddrSet) LowerBoundGap(min uint64) DevAddrGapIterator

LowerBoundGap returns the gap with the lowest range that is greater than or equal to min.

func (*DevAddrSet) LowerBoundLargeEnoughGap 

func (s *DevAddrSet) LowerBoundLargeEnoughGap(min, minSize uint64) DevAddrGapIterator

LowerBoundLargeEnoughGap returns the first gap in the set with at least the given length and whose range contains a key greater than or equal to min. If no such gap exists, LowerBoundLargeEnoughGap returns a terminal iterator.

Precondition: trackGaps must be 1.

func (*DevAddrSet) LowerBoundSegment 

func (s *DevAddrSet) LowerBoundSegment(min uint64) DevAddrIterator

LowerBoundSegment returns the segment with the lowest range that contains a key greater than or equal to min. If no such segment exists, LowerBoundSegment returns a terminal iterator.

func (*DevAddrSet) LowerBoundSegmentSplitBefore 

func (s *DevAddrSet) LowerBoundSegmentSplitBefore(min uint64) DevAddrIterator

LowerBoundSegmentSplitBefore combines LowerBoundSegment and SplitBefore.

LowerBoundSegmentSplitBefore is usually used when mutating segments in a range while iterating them in order of increasing keys. In such cases, LowerBoundSegmentSplitBefore provides an iterator to the first segment to be mutated, suitable as the initial value for a loop variable.

func (*DevAddrSet) Merge 

func (s *DevAddrSet) Merge(first, second DevAddrIterator) DevAddrIterator

Merge attempts to merge two neighboring segments. If successful, Merge returns an iterator to the merged segment, and all existing iterators are invalidated. Otherwise, Merge returns a terminal iterator.

If first is not the predecessor of second, Merge panics.

func (*DevAddrSet) MergeAll 

func (s *DevAddrSet) MergeAll()

MergeAll merges all mergeable adjacent segments in the set. All existing iterators are invalidated.

func (*DevAddrSet) MergeInsideRange 

func (s *DevAddrSet) MergeInsideRange(r DevAddrRange)

MergeInsideRange attempts to merge all adjacent segments that contain a key in the specific range. All existing iterators are invalidated.

MergeInsideRange only makes sense after mutating the set in a way that may change the mergeability of modified segments; callers should prefer to use MergePrev or MergeNext during the mutating loop instead (depending on the direction of iteration), in order to avoid a redundant search.

func (*DevAddrSet) MergeNext 

func (s *DevAddrSet) MergeNext(seg DevAddrIterator) DevAddrIterator

MergeNext attempts to merge the given segment with its successor if possible, and returns an updated iterator to the extended segment. All existing iterators (including seg, but not including the returned iterator) are invalidated.

MergeNext is usually used when mutating segments while iterating them in order of decreasing keys, to attempt merging of each mutated segment with its previously-mutated successor. In such cases, merging a mutated segment with its unmutated predecessor would incorrectly cause the latter to be skipped.

func (*DevAddrSet) MergeOutsideRange 

func (s *DevAddrSet) MergeOutsideRange(r DevAddrRange)

MergeOutsideRange attempts to merge the segment containing r.Start with its predecessor, and the segment containing r.End-1 with its successor.

MergeOutsideRange only makes sense after mutating the set in a way that may change the mergeability of modified segments; callers should prefer to use MergePrev or MergeNext during the mutating loop instead (depending on the direction of iteration), in order to avoid two redundant searches.

func (*DevAddrSet) MergePrev 

func (s *DevAddrSet) MergePrev(seg DevAddrIterator) DevAddrIterator

MergePrev attempts to merge the given segment with its predecessor if possible, and returns an updated iterator to the extended segment. All existing iterators (including seg, but not including the returned iterator) are invalidated.

MergePrev is usually used when mutating segments while iterating them in order of increasing keys, to attempt merging of each mutated segment with its previously-mutated predecessor. In such cases, merging a mutated segment with its unmutated successor would incorrectly cause the latter to be skipped.

func (*DevAddrSet) MergeUnchecked 

func (s *DevAddrSet) MergeUnchecked(first, second DevAddrIterator) DevAddrIterator

MergeUnchecked attempts to merge two neighboring segments. If successful, MergeUnchecked returns an iterator to the merged segment, and all existing iterators are invalidated. Otherwise, MergeUnchecked returns a terminal iterator.

Precondition: first is the predecessor of second: first.NextSegment() == second, first == second.PrevSegment().

func (*DevAddrSet) MutateFullRange 

func (s *DevAddrSet) MutateFullRange(r DevAddrRange, f func(seg DevAddrIterator) bool)

MutateFullRange is equivalent to MutateRange, except that if any key in r that is visited before f returns false does not correspond to a segment, MutateFullRange panics.

func (*DevAddrSet) MutateRange 

func (s *DevAddrSet) MutateRange(r DevAddrRange, f func(seg DevAddrIterator) bool)

MutateRange applies the function f to all segments intersecting the range r, in order of ascending keys. Segments that lie partially outside r are split before f is called, such that f only observes segments entirely within r. Iterated segments are merged again after f is called. Non-empty gaps between segments are skipped. If a call to f returns false, MutateRange stops iteration immediately.

MutateRange invalidates all existing iterators.

N.B. f must not invalidate iterators into s.

func (*DevAddrSet) Remove 

func (s *DevAddrSet) Remove(seg DevAddrIterator) DevAddrGapIterator

Remove removes the given segment and returns an iterator to the vacated gap. All existing iterators (including seg, but not including the returned iterator) are invalidated.

func (*DevAddrSet) RemoveAll 

func (s *DevAddrSet) RemoveAll()

RemoveAll removes all segments from the set. All existing iterators are invalidated.

func (*DevAddrSet) RemoveFullRange 

func (s *DevAddrSet) RemoveFullRange(r DevAddrRange) DevAddrGapIterator

RemoveFullRange is equivalent to RemoveRange, except that if any key in the given range does not correspond to a segment, RemoveFullRange panics.

func (*DevAddrSet) RemoveFullRangeWith 

func (s *DevAddrSet) RemoveFullRangeWith(r DevAddrRange, f func(seg DevAddrIterator)) DevAddrGapIterator

RemoveFullRangeWith is equivalent to RemoveRangeWith, except that if any key in the given range does not correspond to a segment, RemoveFullRangeWith panics.

func (*DevAddrSet) RemoveRange 

func (s *DevAddrSet) RemoveRange(r DevAddrRange) DevAddrGapIterator

RemoveRange removes all segments in the given range. An iterator to the newly formed gap is returned, and all existing iterators are invalidated.

RemoveRange searches the set to find segments to remove. If the caller already has an iterator to either end of the range of segments to remove, or if the caller needs to do additional work before removing each segment, iterate segments and call Remove in a loop instead.

func (*DevAddrSet) RemoveRangeWith 

func (s *DevAddrSet) RemoveRangeWith(r DevAddrRange, f func(seg DevAddrIterator)) DevAddrGapIterator

RemoveRangeWith removes all segments in the given range. An iterator to the newly formed gap is returned, and all existing iterators are invalidated.

The function f is applied to each segment immediately before it is removed, in order of ascending keys. Segments that lie partially outside r are split before f is called, such that f only observes segments entirely within r. Non-empty gaps between segments are skipped.

RemoveRangeWith searches the set to find segments to remove. If the caller already has an iterator to either end of the range of segments to remove, or if the caller needs to do additional work before removing each segment, iterate segments and call Remove in a loop instead.

N.B. f must not invalidate iterators into s.

func (*DevAddrSet) Span 

func (s *DevAddrSet) Span() uint64

Span returns the total size of all segments in the set.

func (*DevAddrSet) SpanRange 

func (s *DevAddrSet) SpanRange(r DevAddrRange) uint64

SpanRange returns the total size of the intersection of segments in the set with the given range.

func (*DevAddrSet) Split 

func (s *DevAddrSet) Split(seg DevAddrIterator, split uint64) (DevAddrIterator, DevAddrIterator)

Split splits the given segment at the given key and returns iterators to the two resulting segments. All existing iterators (including seg, but not including the returned iterators) are invalidated.

If the segment cannot be split at split (because split is at the start or end of the segment's range, so splitting would produce a segment with zero length, or because split falls outside the segment's range altogether), Split panics.

func (*DevAddrSet) SplitAfter 

func (s *DevAddrSet) SplitAfter(seg DevAddrIterator, end uint64) DevAddrIterator

SplitAfter ensures that the given segment's end is at most end by splitting at end if necessary, and returns an updated iterator to the bounded segment. All existing iterators (including seg, but not including the returned iterator) are invalidated.

SplitAfter is usually used when mutating segments in a range. In such cases, when iterating segments in order of increasing keys, each iterated segment may extend beyond the end of the range to be mutated, and needs to be SplitAfter to ensure that only the part of the segment within the range is mutated. When iterating segments in order of decreasing keys, SplitBefore and SplitAfter exchange roles; i.e. SplitBefore needs to be invoked on each segment, while SplitAfter only needs to be invoked on the first.

Preconditions: seg.Start() < end.

func (*DevAddrSet) SplitBefore 

func (s *DevAddrSet) SplitBefore(seg DevAddrIterator, start uint64) DevAddrIterator

SplitBefore ensures that the given segment's start is at least start by splitting at start if necessary, and returns an updated iterator to the bounded segment. All existing iterators (including seg, but not including the returned iterator) are invalidated.

SplitBefore is usually when mutating segments in a range. In such cases, when iterating segments in order of increasing keys, the first segment may extend beyond the start of the range to be mutated, and needs to be SplitBefore to ensure that only the part of the segment within the range is mutated. When iterating segments in order of decreasing keys, SplitBefore and SplitAfter; i.e. SplitBefore needs to be invoked on each segment, while SplitAfter only needs to be invoked on the first.

Preconditions: start < seg.End().

func (*DevAddrSet) SplitUnchecked 

func (s *DevAddrSet) SplitUnchecked(seg DevAddrIterator, split uint64) (DevAddrIterator, DevAddrIterator)

SplitUnchecked splits the given segment at the given key and returns iterators to the two resulting segments. All existing iterators (including seg, but not including the returned iterators) are invalidated.

Preconditions: seg.Start() < key < seg.End().

func (*DevAddrSet) StateFields 

func (s *DevAddrSet) StateFields() []string

func (*DevAddrSet) StateLoad 

func (s *DevAddrSet) StateLoad(ctx context.Context, stateSourceObject state.Source)

+checklocksignore

func (*DevAddrSet) StateSave 

func (s *DevAddrSet) StateSave(stateSinkObject state.Sink)

+checklocksignore

func (*DevAddrSet) StateTypeName 

func (s *DevAddrSet) StateTypeName() string

func (*DevAddrSet) String 

func (s *DevAddrSet) String() string

String stringifies a Set for debugging.

func (*DevAddrSet) TryInsertRange 

func (s *DevAddrSet) TryInsertRange(r DevAddrRange, val pinnedAccelMem) DevAddrIterator

TryInsertRange attempts to insert the given segment into the set. If the new segment can be merged with adjacent segments, TryInsertRange will do so. TryInsertRange returns an iterator to the segment containing the inserted value (which may have been merged with other values). All existing iterators (excluding the returned iterator) are invalidated.

If the new segment would overlap an existing segment, TryInsertRange does nothing and returns a terminal iterator.

TryInsertRange searches the set to find the gap to insert into. If the caller already has the appropriate GapIterator, or if the caller needs to do additional work between finding the gap and insertion, use Insert instead.

func (*DevAddrSet) TryInsertWithoutMergingRange 

func (s *DevAddrSet) TryInsertWithoutMergingRange(r DevAddrRange, val pinnedAccelMem) DevAddrIterator

TryInsertWithoutMergingRange attempts to insert the given segment into the set. If successful, it returns an iterator to the inserted segment; all existing iterators (excluding the returned iterator) are invalidated. If the new segment would overlap an existing segment, TryInsertWithoutMergingRange does nothing and returns a terminal iterator.

TryInsertWithoutMergingRange searches the set to find the gap to insert into. If the caller already has the appropriate GapIterator, or if the caller needs to do additional work between finding the gap and insertion, use InsertWithoutMerging instead.

func (*DevAddrSet) Unisolate 

func (s *DevAddrSet) Unisolate(seg DevAddrIterator) DevAddrIterator

Unisolate attempts to merge the given segment with its predecessor and successor if possible, and returns an updated iterator to the extended segment. All existing iterators (including seg, but not including the returned iterator) are invalidated.

Unisolate is usually used in conjunction with Isolate when mutating part of a single segment in a way that may affect its mergeability. For the reasons described by MergePrev and MergeNext, it is usually incorrect to use the return value of Unisolate in a loop variable.

func (*DevAddrSet) UpperBoundGap 

func (s *DevAddrSet) UpperBoundGap(max uint64) DevAddrGapIterator

UpperBoundGap returns the gap with the highest range that is less than or equal to max.

func (*DevAddrSet) UpperBoundLargeEnoughGap 

func (s *DevAddrSet) UpperBoundLargeEnoughGap(max, minSize uint64) DevAddrGapIterator

UpperBoundLargeEnoughGap returns the last gap in the set with at least the given length and whose range contains a key less than or equal to max. If no such gap exists, UpperBoundLargeEnoughGap returns a terminal iterator.

Precondition: trackGaps must be 1.

func (*DevAddrSet) UpperBoundSegment 

func (s *DevAddrSet) UpperBoundSegment(max uint64) DevAddrIterator

UpperBoundSegment returns the segment with the highest range that contains a key less than or equal to max. If no such segment exists, UpperBoundSegment returns a terminal iterator.

func (*DevAddrSet) UpperBoundSegmentSplitAfter 

func (s *DevAddrSet) UpperBoundSegmentSplitAfter(max uint64) DevAddrIterator

UpperBoundSegmentSplitAfter combines UpperBoundSegment and SplitAfter.

UpperBoundSegmentSplitAfter is usually used when mutating segments in a range while iterating them in order of decreasing keys. In such cases, UpperBoundSegmentSplitAfter provides an iterator to the first segment to be mutated, suitable as the initial value for a loop variable.

func (*DevAddrSet) VisitFullRange 

func (s *DevAddrSet) VisitFullRange(r DevAddrRange, f func(seg DevAddrIterator) bool)

VisitFullRange is equivalent to VisitRange, except that if any key in r that is visited before f returns false does not correspond to a segment, VisitFullRange panics.

func (*DevAddrSet) VisitRange 

func (s *DevAddrSet) VisitRange(r DevAddrRange, f func(seg DevAddrIterator) bool)

VisitRange applies the function f to all segments intersecting the range r, in order of ascending keys. Segments will not be split, so f may be called on segments lying partially outside r. Non-empty gaps between segments are skipped. If a call to f returns false, VisitRange stops iteration immediately.

N.B. f must not invalidate iterators into s.

type DevAddrdynamicGap 

type DevAddrdynamicGap [DevAddrtrackGaps]uint64

dynamicGap is a type that disappears if trackGaps is 0.

func (*DevAddrdynamicGap) Get 

func (d *DevAddrdynamicGap) Get() uint64

Get returns the value of the gap.

Precondition: trackGaps must be non-zero.

func (*DevAddrdynamicGap) Set 

func (d *DevAddrdynamicGap) Set(v uint64)

Set sets the value of the gap.

Precondition: trackGaps must be non-zero.

type DevAddrnode 

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

+stateify savable

func (*DevAddrnode) StateFields 

func (n *DevAddrnode) StateFields() []string

func (*DevAddrnode) StateLoad 

func (n *DevAddrnode) StateLoad(ctx context.Context, stateSourceObject state.Source)

+checklocksignore

func (*DevAddrnode) StateSave 

func (n *DevAddrnode) StateSave(stateSinkObject state.Sink)

+checklocksignore

func (*DevAddrnode) StateTypeName 

func (n *DevAddrnode) StateTypeName() string

func (*DevAddrnode) String 

func (n *DevAddrnode) String() string

String stringifies a node (and all of its children) for debugging.

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.