- 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
This change was derived from a change by:
Reapor-Yurnero <reapor.yurnero@gmail.com>
And has been modified by:
Adin Scannell <ascannell@google.com>
(The original change author is preserved for the commit.)
This change implements gap tracking in the segment set by adding additional
information in each node, and using that information to speed up gap finding
from a linear scan to a O(log(n)) walk of the tree.
This gap tracking is optional, and will default to off except for segment
instances that set gapTracking equal to 1 in their const lists.
PiperOrigin-RevId: 312621607
Based on the guidelines at
https://opensource.google.com/docs/releasing/authors/.
1. $ rg -l "Google LLC" | xargs sed -i 's/Google LLC.*/The gVisor Authors./'
2. Manual fixup of "Google Inc" references.
3. Add AUTHORS file. Authors may request to be added to this file.
4. Point netstack AUTHORS to gVisor AUTHORS. Drop CONTRIBUTORS.
Fixes#209
PiperOrigin-RevId: 245823212
Change-Id: I64530b24ad021a7d683137459cafc510f5ee1de9
Nothing reads them and they can simply get stale.
Generated with:
$ sed -i "s/licenses(\(.*\)).*/licenses(\1)/" **/BUILD
PiperOrigin-RevId: 231818945
Change-Id: Ibc3f9838546b7e94f13f217060d31f4ada9d4bf0
We have been unnecessarily creating too many savable types implicitly.
PiperOrigin-RevId: 206334201
Change-Id: Idc5a3a14bfb7ee125c4f2bb2b1c53164e46f29a8
Jing Chen
Jamie Liu
Adin Scannell
Reapor-Yurnero
Kevin Krakauer
Michael Pratt
Nicolas Lacasse
Ian Gudger
Zhaozhong Ni
Googler