These support the relatively common use case of removing all segments in a
given range (unconditionally) but doing something with them before they're
removed. This is always more compact, and may be slightly faster in some cases
(every replaced loop calls Isolate per iteration, while RemoveRangeWith avoids
redundant split checks between segments), at the cost of a direct function
call.
Also slightly optimize Set.LowerBoundSegmentSplitBefore() and
Set.UpperBoundSegmentSplitAfter() by inlining LowerBoundSegment and
UpperBoundSegment respectively; in the cases where Find() returns a
GapIterator, the segment that is returned doesn't need to be split since it
doesn't contain min/max respectively.
PiperOrigin-RevId: 675824581
This allows for external information to be passed to restore code.
Similar to c087777e37 ("Plumb restore context to afterLoad()").
Updates #1956.
PiperOrigin-RevId: 614125262
- 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
These are primarily simplification and lint mistakes. However, minor
fixes are also included and tests added where appropriate.
PiperOrigin-RevId: 351425971
Our "Preconditions:" blocks are very useful to determine the input invariants,
but they are bit inconsistent throughout the codebase, which makes them harder
to read (particularly cases with 5+ conditions in a single paragraph).
I've reformatted all of the cases to fit in simple rules:
1. Cases with a single condition are placed on a single line.
2. Cases with multiple conditions are placed in a bulleted list.
This format has been added to the style guide.
I've also mentioned "Postconditions:", though those are much less frequently
used, and all uses already match this style.
PiperOrigin-RevId: 327687465
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
Addresses obvious typos, in the documentation only.
COPYBARA_INTEGRATE_REVIEW=https://github.com/google/gvisor/pull/443 from Pixep:fix/documentation-spelling 4d0688164eafaf0b3010e5f4824b35d1e7176d65
PiperOrigin-RevId: 255477779
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
Jamie Liu
Jing Chen
Ayush Ranjan
Adin Scannell
Kevin Krakauer
Michael Pratt
Reapor-Yurnero
Nicolas Lacasse
Ian Gudger
Zhaozhong Ni