segment

package
v0.0.0-...-ba09d25 Latest Latest
Warning

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

 Go to latest Published: Dec 29, 2021 License: Apache-2.0, MIT Imports: 2 Imported by: 0

Documentation

Overview

Package segment provides tools for working with collections of segments. A segment is a key-value mapping, where the key is a non-empty contiguous range of values of type Key, and the value is a single value of type Value.

Clients using this package must use the go_template_instance rule in tools/go_generics/defs.bzl to create an instantiation of this template package, providing types to use in place of Key, Range, Value, and Functions. See pkg/segment/test/BUILD for a usage example.

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

This section is empty.

Types

type Functions 

type Functions interface {
	// MinKey returns the minimum allowed key.
	MinKey() Key

	// MaxKey returns the maximum allowed key + 1.
	MaxKey() Key

	// ClearValue deinitializes the given value. (For example, if Value is a
	// pointer or interface type, ClearValue should set it to nil.)
	ClearValue(*Value)

	// Merge attempts to merge the values corresponding to two consecutive
	// segments. If successful, Merge returns (merged value, true). Otherwise,
	// it returns (unspecified, false).
	//
	// Preconditions: r1.End == r2.Start.
	//
	// Postconditions: If merging succeeds, val1 and val2 are invalidated.
	Merge(r1 Range, val1 Value, r2 Range, val2 Value) (Value, bool)

	// Split splits a segment's value at a key within its range, such that the
	// first returned value corresponds to the range [r.Start, split) and the
	// second returned value corresponds to the range [split, r.End).
	//
	// Preconditions: r.Start < split < r.End.
	//
	// Postconditions: The original value val is invalidated.
	Split(r Range, val Value, split Key) (Value, Value)
}

Functions is a required type parameter that must be a struct implementing the methods defined by Functions.

type GapIterator 

type GapIterator 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 (GapIterator) End 

func (gap GapIterator) End() Key

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

func (GapIterator) IsEmpty 

func (gap GapIterator) IsEmpty() bool

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

func (GapIterator) NextGap 

func (gap GapIterator) NextGap() GapIterator

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

func (GapIterator) NextLargeEnoughGap 

func (gap GapIterator) NextLargeEnoughGap(minSize Key) GapIterator

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 (GapIterator) NextSegment 

func (gap GapIterator) NextSegment() Iterator

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

func (GapIterator) Ok 

func (gap GapIterator) Ok() bool

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

func (GapIterator) PrevGap 

func (gap GapIterator) PrevGap() GapIterator

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

func (GapIterator) PrevLargeEnoughGap 

func (gap GapIterator) PrevLargeEnoughGap(minSize Key) GapIterator

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 (GapIterator) PrevSegment 

func (gap GapIterator) PrevSegment() Iterator

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

func (GapIterator) Range 

func (gap GapIterator) Range() Range

Range returns the range spanned by the iterated gap.

func (GapIterator) Start 

func (gap GapIterator) Start() Key

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

type Iterator 

type Iterator 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 (Iterator) End 

func (seg Iterator) End() Key

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

func (Iterator) NextGap 

func (seg Iterator) NextGap() GapIterator

NextGap returns the gap immediately after the iterated segment.

func (Iterator) NextNonEmpty 

func (seg Iterator) NextNonEmpty() (Iterator, GapIterator)

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 (Iterator) NextSegment 

func (seg Iterator) NextSegment() Iterator

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

func (Iterator) Ok 

func (seg Iterator) Ok() bool

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

func (Iterator) PrevGap 

func (seg Iterator) PrevGap() GapIterator

PrevGap returns the gap immediately before the iterated segment.

func (Iterator) PrevNonEmpty 

func (seg Iterator) PrevNonEmpty() (Iterator, GapIterator)

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 (Iterator) PrevSegment 

func (seg Iterator) PrevSegment() Iterator

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

func (Iterator) Range 

func (seg Iterator) Range() Range

Range returns the iterated segment's range key.

func (Iterator) SetEnd 

func (seg Iterator) SetEnd(end Key)

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 (Iterator) SetEndUnchecked 

func (seg Iterator) SetEndUnchecked(end Key)

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 (Iterator) SetRange 

func (seg Iterator) SetRange(r Range)

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 (Iterator) SetRangeUnchecked 

func (seg Iterator) SetRangeUnchecked(r Range)

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 (Iterator) SetStart 

func (seg Iterator) SetStart(start Key)

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 (Iterator) SetStartUnchecked 

func (seg Iterator) SetStartUnchecked(start Key)

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 (Iterator) SetValue 

func (seg Iterator) SetValue(val Value)

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

func (Iterator) Start 

func (seg Iterator) Start() Key

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

func (Iterator) Value 

func (seg Iterator) Value() Value

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

func (Iterator) ValuePtr 

func (seg Iterator) ValuePtr() *Value

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 Key 

type Key uint64

Key is a required type parameter that must be an integral type.

type Range 

type Range interface{}

Range is a required type parameter equivalent to Range<Key>.

func (Range) CanSplitAt 

func (r Range) CanSplitAt(x T) 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 (Range) Contains 

func (r Range) Contains(x T) bool

Contains returns true if r contains x.

func (Range) Intersect 

func (r Range) Intersect(r2 Range) Range

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 (Range) IsSupersetOf 

func (r Range) IsSupersetOf(r2 Range) bool

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

func (Range) Length 

func (r Range) Length() T

Length returns the length of the range.

func (Range) Overlaps 

func (r Range) Overlaps(r2 Range) bool

Overlaps returns true if r and r2 overlap.

func (Range) WellFormed 

func (r Range) WellFormed() bool

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

type SegmentDataSlices 

type SegmentDataSlices struct {
	Start  []Key
	End    []Key
	Values []Value
}

SegmentDataSlices represents segments from a set as slices of start, end, and values. SegmentDataSlices is primarily used as an intermediate representation for save/restore and the layout here is optimized for that.

+stateify savable

type Set 

type Set 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 (*Set) Add 

func (s *Set) Add(r Range, val Value) bool

Add inserts the given segment into the set and returns true. If the new segment can be merged with adjacent segments, Add will do so. If the new segment would overlap an existing segment, Add returns false. If Add succeeds, all existing iterators are invalidated.

func (*Set) AddWithoutMerging 

func (s *Set) AddWithoutMerging(r Range, val Value) bool

AddWithoutMerging inserts the given segment into the set and returns true. If it would overlap an existing segment, AddWithoutMerging does nothing and returns false. If AddWithoutMerging succeeds, all existing iterators are invalidated.

func (*Set) ApplyContiguous 

func (s *Set) ApplyContiguous(r Range, fn func(seg Iterator)) GapIterator

ApplyContiguous applies a function to a contiguous range of segments, splitting if necessary. The function is applied until the first gap is encountered, at which point the gap is returned. If the function is applied across the entire range, a terminal gap is returned. All existing iterators are invalidated.

N.B. The Iterator must not be invalidated by the function.

func (*Set) ExportSortedSlices 

func (s *Set) ExportSortedSlices() *SegmentDataSlices

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

func (*Set) Find 

func (s *Set) Find(key Key) (Iterator, GapIterator)

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 (*Set) FindGap 

func (s *Set) FindGap(key Key) GapIterator

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 (*Set) FindSegment 

func (s *Set) FindSegment(key Key) Iterator

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

func (*Set) FirstGap 

func (s *Set) FirstGap() GapIterator

FirstGap returns the first gap in the set.

func (*Set) FirstSegment 

func (s *Set) FirstSegment() Iterator

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

func (*Set) ImportSortedSlices 

func (s *Set) ImportSortedSlices(sds *SegmentDataSlices) error

ImportSortedSlices initializes the given set from the given slice.

Preconditions:

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

func (*Set) Insert 

func (s *Set) Insert(gap GapIterator, r Range, val Value) Iterator

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 (*Set) InsertWithoutMerging 

func (s *Set) InsertWithoutMerging(gap GapIterator, r Range, val Value) Iterator

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 (*Set) InsertWithoutMergingUnchecked 

func (s *Set) InsertWithoutMergingUnchecked(gap GapIterator, r Range, val Value) Iterator

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 (*Set) IsEmpty 

func (s *Set) IsEmpty() bool

IsEmpty returns true if the set contains no segments.

func (*Set) IsEmptyRange 

func (s *Set) IsEmptyRange(r Range) 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 (*Set) Isolate 

func (s *Set) Isolate(seg Iterator, r Range) Iterator

Isolate ensures that the given segment's range does not escape 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.

func (*Set) LastGap 

func (s *Set) LastGap() GapIterator

LastGap returns the last gap in the set.

func (*Set) LastSegment 

func (s *Set) LastSegment() Iterator

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

func (*Set) LowerBoundGap 

func (s *Set) LowerBoundGap(min Key) GapIterator

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

func (*Set) LowerBoundSegment 

func (s *Set) LowerBoundSegment(min Key) Iterator

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 (*Set) Merge 

func (s *Set) Merge(first, second Iterator) Iterator

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 (*Set) MergeAdjacent 

func (s *Set) MergeAdjacent(r Range)

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

func (*Set) MergeAll 

func (s *Set) MergeAll()

MergeAll attempts to merge all adjacent segments in the set. All existing iterators are invalidated.

func (*Set) MergeRange 

func (s *Set) MergeRange(r Range)

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

func (*Set) MergeUnchecked 

func (s *Set) MergeUnchecked(first, second Iterator) Iterator

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 (*Set) Remove 

func (s *Set) Remove(seg Iterator) GapIterator

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 (*Set) RemoveAll 

func (s *Set) RemoveAll()

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

func (*Set) RemoveRange 

func (s *Set) RemoveRange(r Range) GapIterator

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

func (*Set) Span 

func (s *Set) Span() Key

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

func (*Set) SpanRange 

func (s *Set) SpanRange(r Range) Key

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

func (*Set) Split 

func (s *Set) Split(seg Iterator, split Key) (Iterator, Iterator)

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 (*Set) SplitAt 

func (s *Set) SplitAt(split Key) bool

SplitAt splits the segment straddling split, if one exists. SplitAt returns true if a segment was split and false otherwise. If SplitAt splits a segment, all existing iterators are invalidated.

func (*Set) SplitUnchecked 

func (s *Set) SplitUnchecked(seg Iterator, split Key) (Iterator, Iterator)

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 (*Set) String 

func (s *Set) String() string

String stringifies a Set for debugging.

func (*Set) UpperBoundGap 

func (s *Set) UpperBoundGap(max Key) GapIterator

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

func (*Set) UpperBoundSegment 

func (s *Set) UpperBoundSegment(max Key) Iterator

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.

type T 

type T uint64

T is a required type parameter that must be an integral type.

type Value 

type Value interface{}

Value is a required type parameter.

Source Files

View all Source files

Directories

Path Synopsis
Package segment is a test package.
 Package segment is a test package.

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.