mirror of
https://github.com/hanzoai/visor.git
synced 2026-09-24 17:04:14 +00:00
Jamie LiuandgVisor bot
8ce145a027
- Replace Add with TryInsertRange; for symmetry with RemoveRange, to establish
the convention that *Range methods perform an implicit search in the set, and
so that we can fork InsertRange which has Insert-like semantics (panics on
conflict), which the majority of callers want.
- Rename MergeRange and MergeAdjacent to MergeInsideRange and MergeOutsideRange
respectively; for the same convention, and to more clearly describe the
difference between these functions.
- Add MergePrev and MergeNext. These solve the longstanding problem of
requiring a separate call to Merge{Inside,Outside}Range (which will perform
additional searches) after mutating a set in a relatively simple manner.
- Add SplitBefore and SplitAfter, which are halves of Isolate. These are
slightly preferable to Isolate in many use cases for the latter (when
iterating segments within a range, only the first segment can include a key
before the start, so this saves some useless comparisons in almost every
iteration of such loops), and are useful in some more complex algorithms.
Also add LowerBoundSegmentSplitBefore and UpperBoundSegmentSplitAfter as
ergonomic aids for the former use case.
- Add {Visit,Mutate}[Full]Range, which are convenience wrappers around the
iterator API (including new functions) for simple use cases (and hence also
serve to demonstrate how the new iterator functions are used).
MutateFullRange in particular replaces ApplyContiguous and adds merging
during iteration.
- Add RemoveFullRange, which (analogous to {Visit,Mutate}FullRange) is a
variant of RemoveRange that checks that the range is fully covered by
segments.
- Add Unisolate, which combines MergePrev and MergeNext in the same way that
Isolate combines SplitBefore and SplitAfter. This is useful for merging after
mutation of a single segment.
- Add {First,Last,LowerBound,UpperBound}LargeEnoughGap, which are convenient
loop starters when using gap tracking.
- Replace SegmentDataSlices with FlatSegment, which is easier to use when
specifying "set literals" (as in tests).
- Make {prev,next}LargeEnoughGapHelper iterative rather than tail-recursive.
- Slightly optimize Iterator.{Prev,Next}NonEmpty: GapIterator.{Start,End} needs
to find the corresponding Iterator, so call Iterator.{Prev,Next}Segment
directly rather than doing so twice.
PiperOrigin-RevId: 583506148
56 lines
1.6 KiB
Go
56 lines
1.6 KiB
Go
// Copyright 2018 The gVisor Authors.
|
|
//
|
|
// Licensed under the Apache License, Version 2.0 (the "License");
|
|
// you may not use this file except in compliance with the License.
|
|
// You may obtain a copy of the License at
|
|
//
|
|
// http://www.apache.org/licenses/LICENSE-2.0
|
|
//
|
|
// Unless required by applicable law or agreed to in writing, software
|
|
// distributed under the License is distributed on an "AS IS" BASIS,
|
|
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
// See the License for the specific language governing permissions and
|
|
// limitations under the License.
|
|
|
|
// Package segment is a test package.
|
|
package segment
|
|
|
|
type setFunctions struct{}
|
|
|
|
// MinKey returns the minimum key for the set.
|
|
func (s setFunctions) MinKey() int {
|
|
return -s.MaxKey() - 1
|
|
}
|
|
|
|
// MaxKey returns the maximum key for the set.
|
|
func (setFunctions) MaxKey() int {
|
|
return int(^uint(0) >> 1)
|
|
}
|
|
|
|
func (setFunctions) ClearValue(*int) {}
|
|
|
|
func (setFunctions) Merge(_ Range, val1 int, _ Range, val2 int) (int, bool) {
|
|
return val1, val1 == val2
|
|
}
|
|
|
|
func (setFunctions) Split(_ Range, val int, _ int) (int, int) {
|
|
return val, val
|
|
}
|
|
|
|
type gapSetFunctions struct {
|
|
setFunctions
|
|
}
|
|
|
|
// MinKey is adjusted to make sure no add overflow would happen in test cases.
|
|
// e.g. A gap with range {MinInt32, 2} would cause overflow in Range().Length().
|
|
//
|
|
// Normally Keys should be unsigned to avoid these issues.
|
|
func (s gapSetFunctions) MinKey() int {
|
|
return s.setFunctions.MinKey() / 2
|
|
}
|
|
|
|
// MaxKey returns the maximum key for the set.
|
|
func (s gapSetFunctions) MaxKey() int {
|
|
return s.setFunctions.MaxKey() / 2
|
|
}
|