1 package state
2 3 import (
4 "bytes"
5 "context"
6 "fmt"
7 )
8 9 // trackGaps is an optional parameter.
10 //
11 // If trackGaps is 1, the Set will track maximum gap size recursively,
12 // enabling the GapIterator.{Prev,Next}LargeEnoughGap functions. In this
13 // case, Key must be an unsigned integer.
14 //
15 // trackGaps must be 0 or 1.
16 const addrtrackGaps = 0
17 18 var _ = uint8(addrtrackGaps << 7) // Will fail if not zero or one.
19 20 // dynamicGap is a type that disappears if trackGaps is 0.
21 type addrdynamicGap [addrtrackGaps]uintptr
22 23 // Get returns the value of the gap.
24 //
25 // Precondition: trackGaps must be non-zero.
26 func (d *addrdynamicGap) Get() uintptr {
27 return d[:][0]
28 }
29 30 // Set sets the value of the gap.
31 //
32 // Precondition: trackGaps must be non-zero.
33 func (d *addrdynamicGap) Set(v uintptr) {
34 d[:][0] = v
35 }
36 37 const (
38 // minDegree is the minimum degree of an internal node in a Set B-tree.
39 //
40 // - Any non-root node has at least minDegree-1 segments.
41 //
42 // - Any non-root internal (non-leaf) node has at least minDegree children.
43 //
44 // - The root node may have fewer than minDegree-1 segments, but it may
45 // only have 0 segments if the tree is empty.
46 //
47 // Our implementation requires minDegree >= 3. Higher values of minDegree
48 // usually improve performance, but increase memory usage for small sets.
49 addrminDegree = 10
50 51 addrmaxDegree = 2 * addrminDegree
52 )
53 54 // A Set is a mapping of segments with non-overlapping Range keys. The zero
55 // value for a Set is an empty set. Set values are not safely movable nor
56 // copyable. Set is thread-compatible.
57 //
58 // +stateify savable
59 type addrSet struct {
60 root addrnode `state:".([]addrFlatSegment)"`
61 }
62 63 // IsEmpty returns true if the set contains no segments.
64 func (s *addrSet) IsEmpty() bool {
65 return s.root.nrSegments == 0
66 }
67 68 // IsEmptyRange returns true iff no segments in the set overlap the given
69 // range. This is semantically equivalent to s.SpanRange(r) == 0, but may be
70 // more efficient.
71 func (s *addrSet) IsEmptyRange(r addrRange) bool {
72 switch {
73 case r.Length() < 0:
74 panic(fmt.Sprintf("invalid range %v", r))
75 case r.Length() == 0:
76 return true
77 }
78 _, gap := s.Find(r.Start)
79 if !gap.Ok() {
80 return false
81 }
82 return r.End <= gap.End()
83 }
84 85 // Span returns the total size of all segments in the set.
86 func (s *addrSet) Span() uintptr {
87 var sz uintptr
88 for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() {
89 sz += seg.Range().Length()
90 }
91 return sz
92 }
93 94 // SpanRange returns the total size of the intersection of segments in the set
95 // with the given range.
96 func (s *addrSet) SpanRange(r addrRange) uintptr {
97 switch {
98 case r.Length() < 0:
99 panic(fmt.Sprintf("invalid range %v", r))
100 case r.Length() == 0:
101 return 0
102 }
103 var sz uintptr
104 for seg := s.LowerBoundSegment(r.Start); seg.Ok() && seg.Start() < r.End; seg = seg.NextSegment() {
105 sz += seg.Range().Intersect(r).Length()
106 }
107 return sz
108 }
109 110 // FirstSegment returns the first segment in the set. If the set is empty,
111 // FirstSegment returns a terminal iterator.
112 func (s *addrSet) FirstSegment() addrIterator {
113 if s.root.nrSegments == 0 {
114 return addrIterator{}
115 }
116 return s.root.firstSegment()
117 }
118 119 // LastSegment returns the last segment in the set. If the set is empty,
120 // LastSegment returns a terminal iterator.
121 func (s *addrSet) LastSegment() addrIterator {
122 if s.root.nrSegments == 0 {
123 return addrIterator{}
124 }
125 return s.root.lastSegment()
126 }
127 128 // FirstGap returns the first gap in the set.
129 func (s *addrSet) FirstGap() addrGapIterator {
130 n := &s.root
131 for n.hasChildren {
132 n = n.children[0]
133 }
134 return addrGapIterator{n, 0}
135 }
136 137 // LastGap returns the last gap in the set.
138 func (s *addrSet) LastGap() addrGapIterator {
139 n := &s.root
140 for n.hasChildren {
141 n = n.children[n.nrSegments]
142 }
143 return addrGapIterator{n, n.nrSegments}
144 }
145 146 // Find returns the segment or gap whose range contains the given key. If a
147 // segment is found, the returned Iterator is non-terminal and the
148 // returned GapIterator is terminal. Otherwise, the returned Iterator is
149 // terminal and the returned GapIterator is non-terminal.
150 func (s *addrSet) Find(key uintptr) (addrIterator, addrGapIterator) {
151 n := &s.root
152 for {
153 154 lower := 0
155 upper := n.nrSegments
156 for lower < upper {
157 i := lower + (upper-lower)/2
158 if r := n.keys[i]; key < r.End {
159 if key >= r.Start {
160 return addrIterator{n, i}, addrGapIterator{}
161 }
162 upper = i
163 } else {
164 lower = i + 1
165 }
166 }
167 i := lower
168 if !n.hasChildren {
169 return addrIterator{}, addrGapIterator{n, i}
170 }
171 n = n.children[i]
172 }
173 }
174 175 // FindSegment returns the segment whose range contains the given key. If no
176 // such segment exists, FindSegment returns a terminal iterator.
177 func (s *addrSet) FindSegment(key uintptr) addrIterator {
178 seg, _ := s.Find(key)
179 return seg
180 }
181 182 // LowerBoundSegment returns the segment with the lowest range that contains a
183 // key greater than or equal to min. If no such segment exists,
184 // LowerBoundSegment returns a terminal iterator.
185 func (s *addrSet) LowerBoundSegment(min uintptr) addrIterator {
186 seg, gap := s.Find(min)
187 if seg.Ok() {
188 return seg
189 }
190 return gap.NextSegment()
191 }
192 193 // UpperBoundSegment returns the segment with the highest range that contains a
194 // key less than or equal to max. If no such segment exists, UpperBoundSegment
195 // returns a terminal iterator.
196 func (s *addrSet) UpperBoundSegment(max uintptr) addrIterator {
197 seg, gap := s.Find(max)
198 if seg.Ok() {
199 return seg
200 }
201 return gap.PrevSegment()
202 }
203 204 // FindGap returns the gap containing the given key. If no such gap exists
205 // (i.e. the set contains a segment containing that key), FindGap returns a
206 // terminal iterator.
207 func (s *addrSet) FindGap(key uintptr) addrGapIterator {
208 _, gap := s.Find(key)
209 return gap
210 }
211 212 // LowerBoundGap returns the gap with the lowest range that is greater than or
213 // equal to min.
214 func (s *addrSet) LowerBoundGap(min uintptr) addrGapIterator {
215 seg, gap := s.Find(min)
216 if gap.Ok() {
217 return gap
218 }
219 return seg.NextGap()
220 }
221 222 // UpperBoundGap returns the gap with the highest range that is less than or
223 // equal to max.
224 func (s *addrSet) UpperBoundGap(max uintptr) addrGapIterator {
225 seg, gap := s.Find(max)
226 if gap.Ok() {
227 return gap
228 }
229 return seg.PrevGap()
230 }
231 232 // FirstLargeEnoughGap returns the first gap in the set with at least the given
233 // length. If no such gap exists, FirstLargeEnoughGap returns a terminal
234 // iterator.
235 //
236 // Precondition: trackGaps must be 1.
237 func (s *addrSet) FirstLargeEnoughGap(minSize uintptr) addrGapIterator {
238 if addrtrackGaps != 1 {
239 panic("set is not tracking gaps")
240 }
241 gap := s.FirstGap()
242 if gap.Range().Length() >= minSize {
243 return gap
244 }
245 return gap.NextLargeEnoughGap(minSize)
246 }
247 248 // LastLargeEnoughGap returns the last gap in the set with at least the given
249 // length. If no such gap exists, LastLargeEnoughGap returns a terminal
250 // iterator.
251 //
252 // Precondition: trackGaps must be 1.
253 func (s *addrSet) LastLargeEnoughGap(minSize uintptr) addrGapIterator {
254 if addrtrackGaps != 1 {
255 panic("set is not tracking gaps")
256 }
257 gap := s.LastGap()
258 if gap.Range().Length() >= minSize {
259 return gap
260 }
261 return gap.PrevLargeEnoughGap(minSize)
262 }
263 264 // LowerBoundLargeEnoughGap returns the first gap in the set with at least the
265 // given length and whose range contains a key greater than or equal to min. If
266 // no such gap exists, LowerBoundLargeEnoughGap returns a terminal iterator.
267 //
268 // Precondition: trackGaps must be 1.
269 func (s *addrSet) LowerBoundLargeEnoughGap(min, minSize uintptr) addrGapIterator {
270 if addrtrackGaps != 1 {
271 panic("set is not tracking gaps")
272 }
273 gap := s.LowerBoundGap(min)
274 if gap.Range().Length() >= minSize {
275 return gap
276 }
277 return gap.NextLargeEnoughGap(minSize)
278 }
279 280 // UpperBoundLargeEnoughGap returns the last gap in the set with at least the
281 // given length and whose range contains a key less than or equal to max. If no
282 // such gap exists, UpperBoundLargeEnoughGap returns a terminal iterator.
283 //
284 // Precondition: trackGaps must be 1.
285 func (s *addrSet) UpperBoundLargeEnoughGap(max, minSize uintptr) addrGapIterator {
286 if addrtrackGaps != 1 {
287 panic("set is not tracking gaps")
288 }
289 gap := s.UpperBoundGap(max)
290 if gap.Range().Length() >= minSize {
291 return gap
292 }
293 return gap.PrevLargeEnoughGap(minSize)
294 }
295 296 // Insert inserts the given segment into the given gap. If the new segment can
297 // be merged with adjacent segments, Insert will do so. Insert returns an
298 // iterator to the segment containing the inserted value (which may have been
299 // merged with other values). All existing iterators (including gap, but not
300 // including the returned iterator) are invalidated.
301 //
302 // If the gap cannot accommodate the segment, or if r is invalid, Insert panics.
303 //
304 // Insert is semantically equivalent to a InsertWithoutMerging followed by a
305 // Merge, but may be more efficient. Note that there is no unchecked variant of
306 // Insert since Insert must retrieve and inspect gap's predecessor and
307 // successor segments regardless.
308 func (s *addrSet) Insert(gap addrGapIterator, r addrRange, val *objectEncodeState) addrIterator {
309 if r.Length() <= 0 {
310 panic(fmt.Sprintf("invalid segment range %v", r))
311 }
312 prev, next := gap.PrevSegment(), gap.NextSegment()
313 if prev.Ok() && prev.End() > r.Start {
314 panic(fmt.Sprintf("new segment %v overlaps predecessor %v", r, prev.Range()))
315 }
316 if next.Ok() && next.Start() < r.End {
317 panic(fmt.Sprintf("new segment %v overlaps successor %v", r, next.Range()))
318 }
319 if prev.Ok() && prev.End() == r.Start {
320 if mval, ok := (addrSetFunctions{}).Merge(prev.Range(), prev.Value(), r, val); ok {
321 shrinkMaxGap := addrtrackGaps != 0 && gap.Range().Length() == gap.node.maxGap.Get()
322 prev.SetEndUnchecked(r.End)
323 prev.SetValue(mval)
324 if shrinkMaxGap {
325 gap.node.updateMaxGapLeaf()
326 }
327 if next.Ok() && next.Start() == r.End {
328 val = mval
329 if mval, ok := (addrSetFunctions{}).Merge(prev.Range(), val, next.Range(), next.Value()); ok {
330 prev.SetEndUnchecked(next.End())
331 prev.SetValue(mval)
332 return s.Remove(next).PrevSegment()
333 }
334 }
335 return prev
336 }
337 }
338 if next.Ok() && next.Start() == r.End {
339 if mval, ok := (addrSetFunctions{}).Merge(r, val, next.Range(), next.Value()); ok {
340 shrinkMaxGap := addrtrackGaps != 0 && gap.Range().Length() == gap.node.maxGap.Get()
341 next.SetStartUnchecked(r.Start)
342 next.SetValue(mval)
343 if shrinkMaxGap {
344 gap.node.updateMaxGapLeaf()
345 }
346 return next
347 }
348 }
349 350 return s.InsertWithoutMergingUnchecked(gap, r, val)
351 }
352 353 // InsertWithoutMerging inserts the given segment into the given gap and
354 // returns an iterator to the inserted segment. All existing iterators
355 // (including gap, but not including the returned iterator) are invalidated.
356 //
357 // If the gap cannot accommodate the segment, or if r is invalid,
358 // InsertWithoutMerging panics.
359 func (s *addrSet) InsertWithoutMerging(gap addrGapIterator, r addrRange, val *objectEncodeState) addrIterator {
360 if r.Length() <= 0 {
361 panic(fmt.Sprintf("invalid segment range %v", r))
362 }
363 if gr := gap.Range(); !gr.IsSupersetOf(r) {
364 panic(fmt.Sprintf("cannot insert segment range %v into gap range %v", r, gr))
365 }
366 return s.InsertWithoutMergingUnchecked(gap, r, val)
367 }
368 369 // InsertWithoutMergingUnchecked inserts the given segment into the given gap
370 // and returns an iterator to the inserted segment. All existing iterators
371 // (including gap, but not including the returned iterator) are invalidated.
372 //
373 // Preconditions:
374 // - r.Start >= gap.Start().
375 // - r.End <= gap.End().
376 func (s *addrSet) InsertWithoutMergingUnchecked(gap addrGapIterator, r addrRange, val *objectEncodeState) addrIterator {
377 gap = gap.node.rebalanceBeforeInsert(gap)
378 splitMaxGap := addrtrackGaps != 0 && (gap.node.nrSegments == 0 || gap.Range().Length() == gap.node.maxGap.Get())
379 copy(gap.node.keys[gap.index+1:], gap.node.keys[gap.index:gap.node.nrSegments])
380 copy(gap.node.values[gap.index+1:], gap.node.values[gap.index:gap.node.nrSegments])
381 gap.node.keys[gap.index] = r
382 gap.node.values[gap.index] = val
383 gap.node.nrSegments++
384 if splitMaxGap {
385 gap.node.updateMaxGapLeaf()
386 }
387 return addrIterator{gap.node, gap.index}
388 }
389 390 // InsertRange inserts the given segment into the set. If the new segment can
391 // be merged with adjacent segments, InsertRange will do so. InsertRange
392 // returns an iterator to the segment containing the inserted value (which may
393 // have been merged with other values). All existing iterators (excluding the
394 // returned iterator) are invalidated.
395 //
396 // If the new segment would overlap an existing segment, or if r is invalid,
397 // InsertRange panics.
398 //
399 // InsertRange searches the set to find the gap to insert into. If the caller
400 // already has the appropriate GapIterator, or if the caller needs to do
401 // additional work between finding the gap and insertion, use Insert instead.
402 func (s *addrSet) InsertRange(r addrRange, val *objectEncodeState) addrIterator {
403 if r.Length() <= 0 {
404 panic(fmt.Sprintf("invalid segment range %v", r))
405 }
406 seg, gap := s.Find(r.Start)
407 if seg.Ok() {
408 panic(fmt.Sprintf("new segment %v overlaps existing segment %v", r, seg.Range()))
409 }
410 if gap.End() < r.End {
411 panic(fmt.Sprintf("new segment %v overlaps existing segment %v", r, gap.NextSegment().Range()))
412 }
413 return s.Insert(gap, r, val)
414 }
415 416 // InsertWithoutMergingRange inserts the given segment into the set and returns
417 // an iterator to the inserted segment. All existing iterators (excluding the
418 // returned iterator) are invalidated.
419 //
420 // If the new segment would overlap an existing segment, or if r is invalid,
421 // InsertWithoutMergingRange panics.
422 //
423 // InsertWithoutMergingRange searches the set to find the gap to insert into.
424 // If the caller already has the appropriate GapIterator, or if the caller
425 // needs to do additional work between finding the gap and insertion, use
426 // InsertWithoutMerging instead.
427 func (s *addrSet) InsertWithoutMergingRange(r addrRange, val *objectEncodeState) addrIterator {
428 if r.Length() <= 0 {
429 panic(fmt.Sprintf("invalid segment range %v", r))
430 }
431 seg, gap := s.Find(r.Start)
432 if seg.Ok() {
433 panic(fmt.Sprintf("new segment %v overlaps existing segment %v", r, seg.Range()))
434 }
435 if gap.End() < r.End {
436 panic(fmt.Sprintf("new segment %v overlaps existing segment %v", r, gap.NextSegment().Range()))
437 }
438 return s.InsertWithoutMerging(gap, r, val)
439 }
440 441 // TryInsertRange attempts to insert the given segment into the set. If the new
442 // segment can be merged with adjacent segments, TryInsertRange will do so.
443 // TryInsertRange returns an iterator to the segment containing the inserted
444 // value (which may have been merged with other values). All existing iterators
445 // (excluding the returned iterator) are invalidated.
446 //
447 // If the new segment would overlap an existing segment, TryInsertRange does
448 // nothing and returns a terminal iterator.
449 //
450 // TryInsertRange searches the set to find the gap to insert into. If the
451 // caller already has the appropriate GapIterator, or if the caller needs to do
452 // additional work between finding the gap and insertion, use Insert instead.
453 func (s *addrSet) TryInsertRange(r addrRange, val *objectEncodeState) addrIterator {
454 if r.Length() <= 0 {
455 panic(fmt.Sprintf("invalid segment range %v", r))
456 }
457 seg, gap := s.Find(r.Start)
458 if seg.Ok() {
459 return addrIterator{}
460 }
461 if gap.End() < r.End {
462 return addrIterator{}
463 }
464 return s.Insert(gap, r, val)
465 }
466 467 // TryInsertWithoutMergingRange attempts to insert the given segment into the
468 // set. If successful, it returns an iterator to the inserted segment; all
469 // existing iterators (excluding the returned iterator) are invalidated. If the
470 // new segment would overlap an existing segment, TryInsertWithoutMergingRange
471 // does nothing and returns a terminal iterator.
472 //
473 // TryInsertWithoutMergingRange searches the set to find the gap to insert
474 // into. If the caller already has the appropriate GapIterator, or if the
475 // caller needs to do additional work between finding the gap and insertion,
476 // use InsertWithoutMerging instead.
477 func (s *addrSet) TryInsertWithoutMergingRange(r addrRange, val *objectEncodeState) addrIterator {
478 if r.Length() <= 0 {
479 panic(fmt.Sprintf("invalid segment range %v", r))
480 }
481 seg, gap := s.Find(r.Start)
482 if seg.Ok() {
483 return addrIterator{}
484 }
485 if gap.End() < r.End {
486 return addrIterator{}
487 }
488 return s.InsertWithoutMerging(gap, r, val)
489 }
490 491 // Remove removes the given segment and returns an iterator to the vacated gap.
492 // All existing iterators (including seg, but not including the returned
493 // iterator) are invalidated.
494 func (s *addrSet) Remove(seg addrIterator) addrGapIterator {
495 496 if seg.node.hasChildren {
497 498 victim := seg.PrevSegment()
499 500 seg.SetRangeUnchecked(victim.Range())
501 seg.SetValue(victim.Value())
502 503 nextAdjacentNode := seg.NextSegment().node
504 if addrtrackGaps != 0 {
505 nextAdjacentNode.updateMaxGapLeaf()
506 }
507 return s.Remove(victim).NextGap()
508 }
509 copy(seg.node.keys[seg.index:], seg.node.keys[seg.index+1:seg.node.nrSegments])
510 copy(seg.node.values[seg.index:], seg.node.values[seg.index+1:seg.node.nrSegments])
511 addrSetFunctions{}.ClearValue(&seg.node.values[seg.node.nrSegments-1])
512 seg.node.nrSegments--
513 if addrtrackGaps != 0 {
514 seg.node.updateMaxGapLeaf()
515 }
516 return seg.node.rebalanceAfterRemove(addrGapIterator{seg.node, seg.index})
517 }
518 519 // RemoveAll removes all segments from the set. All existing iterators are
520 // invalidated.
521 func (s *addrSet) RemoveAll() {
522 s.root = addrnode{}
523 }
524 525 // RemoveRange removes all segments in the given range. An iterator to the
526 // newly formed gap is returned, and all existing iterators are invalidated.
527 //
528 // RemoveRange searches the set to find segments to remove. If the caller
529 // already has an iterator to either end of the range of segments to remove, or
530 // if the caller needs to do additional work before removing each segment,
531 // iterate segments and call Remove in a loop instead.
532 func (s *addrSet) RemoveRange(r addrRange) addrGapIterator {
533 return s.RemoveRangeWith(r, nil)
534 }
535 536 // RemoveFullRange is equivalent to RemoveRange, except that if any key in the
537 // given range does not correspond to a segment, RemoveFullRange panics.
538 func (s *addrSet) RemoveFullRange(r addrRange) addrGapIterator {
539 return s.RemoveFullRangeWith(r, nil)
540 }
541 542 // RemoveRangeWith removes all segments in the given range. An iterator to the
543 // newly formed gap is returned, and all existing iterators are invalidated.
544 //
545 // The function f is applied to each segment immediately before it is removed,
546 // in order of ascending keys. Segments that lie partially outside r are split
547 // before f is called, such that f only observes segments entirely within r.
548 // Non-empty gaps between segments are skipped.
549 //
550 // RemoveRangeWith searches the set to find segments to remove. If the caller
551 // already has an iterator to either end of the range of segments to remove, or
552 // if the caller needs to do additional work before removing each segment,
553 // iterate segments and call Remove in a loop instead.
554 //
555 // N.B. f must not invalidate iterators into s.
556 func (s *addrSet) RemoveRangeWith(r addrRange, f func(seg addrIterator)) addrGapIterator {
557 seg, gap := s.Find(r.Start)
558 if seg.Ok() {
559 seg = s.Isolate(seg, r)
560 if f != nil {
561 f(seg)
562 }
563 gap = s.Remove(seg)
564 }
565 for seg = gap.NextSegment(); seg.Ok() && seg.Start() < r.End; seg = gap.NextSegment() {
566 seg = s.SplitAfter(seg, r.End)
567 if f != nil {
568 f(seg)
569 }
570 gap = s.Remove(seg)
571 }
572 return gap
573 }
574 575 // RemoveFullRangeWith is equivalent to RemoveRangeWith, except that if any key
576 // in the given range does not correspond to a segment, RemoveFullRangeWith
577 // panics.
578 func (s *addrSet) RemoveFullRangeWith(r addrRange, f func(seg addrIterator)) addrGapIterator {
579 seg := s.FindSegment(r.Start)
580 if !seg.Ok() {
581 panic(fmt.Sprintf("missing segment at %v", r.Start))
582 }
583 seg = s.SplitBefore(seg, r.Start)
584 for {
585 seg = s.SplitAfter(seg, r.End)
586 if f != nil {
587 f(seg)
588 }
589 end := seg.End()
590 gap := s.Remove(seg)
591 if r.End <= end {
592 return gap
593 }
594 seg = gap.NextSegment()
595 if !seg.Ok() || seg.Start() != end {
596 panic(fmt.Sprintf("missing segment at %v", end))
597 }
598 }
599 }
600 601 // Merge attempts to merge two neighboring segments. If successful, Merge
602 // returns an iterator to the merged segment, and all existing iterators are
603 // invalidated. Otherwise, Merge returns a terminal iterator.
604 //
605 // If first is not the predecessor of second, Merge panics.
606 func (s *addrSet) Merge(first, second addrIterator) addrIterator {
607 if first.NextSegment() != second {
608 panic(fmt.Sprintf("attempt to merge non-neighboring segments %v, %v", first.Range(), second.Range()))
609 }
610 return s.MergeUnchecked(first, second)
611 }
612 613 // MergeUnchecked attempts to merge two neighboring segments. If successful,
614 // MergeUnchecked returns an iterator to the merged segment, and all existing
615 // iterators are invalidated. Otherwise, MergeUnchecked returns a terminal
616 // iterator.
617 //
618 // Precondition: first is the predecessor of second: first.NextSegment() ==
619 // second, first == second.PrevSegment().
620 func (s *addrSet) MergeUnchecked(first, second addrIterator) addrIterator {
621 if first.End() == second.Start() {
622 if mval, ok := (addrSetFunctions{}).Merge(first.Range(), first.Value(), second.Range(), second.Value()); ok {
623 624 first.SetEndUnchecked(second.End())
625 first.SetValue(mval)
626 627 return s.Remove(second).PrevSegment()
628 }
629 }
630 return addrIterator{}
631 }
632 633 // MergePrev attempts to merge the given segment with its predecessor if
634 // possible, and returns an updated iterator to the extended segment. All
635 // existing iterators (including seg, but not including the returned iterator)
636 // are invalidated.
637 //
638 // MergePrev is usually used when mutating segments while iterating them in
639 // order of increasing keys, to attempt merging of each mutated segment with
640 // its previously-mutated predecessor. In such cases, merging a mutated segment
641 // with its unmutated successor would incorrectly cause the latter to be
642 // skipped.
643 func (s *addrSet) MergePrev(seg addrIterator) addrIterator {
644 if prev := seg.PrevSegment(); prev.Ok() {
645 if mseg := s.MergeUnchecked(prev, seg); mseg.Ok() {
646 seg = mseg
647 }
648 }
649 return seg
650 }
651 652 // MergeNext attempts to merge the given segment with its successor if
653 // possible, and returns an updated iterator to the extended segment. All
654 // existing iterators (including seg, but not including the returned iterator)
655 // are invalidated.
656 //
657 // MergeNext is usually used when mutating segments while iterating them in
658 // order of decreasing keys, to attempt merging of each mutated segment with
659 // its previously-mutated successor. In such cases, merging a mutated segment
660 // with its unmutated predecessor would incorrectly cause the latter to be
661 // skipped.
662 func (s *addrSet) MergeNext(seg addrIterator) addrIterator {
663 if next := seg.NextSegment(); next.Ok() {
664 if mseg := s.MergeUnchecked(seg, next); mseg.Ok() {
665 seg = mseg
666 }
667 }
668 return seg
669 }
670 671 // Unisolate attempts to merge the given segment with its predecessor and
672 // successor if possible, and returns an updated iterator to the extended
673 // segment. All existing iterators (including seg, but not including the
674 // returned iterator) are invalidated.
675 //
676 // Unisolate is usually used in conjunction with Isolate when mutating part of
677 // a single segment in a way that may affect its mergeability. For the reasons
678 // described by MergePrev and MergeNext, it is usually incorrect to use the
679 // return value of Unisolate in a loop variable.
680 func (s *addrSet) Unisolate(seg addrIterator) addrIterator {
681 if prev := seg.PrevSegment(); prev.Ok() {
682 if mseg := s.MergeUnchecked(prev, seg); mseg.Ok() {
683 seg = mseg
684 }
685 }
686 if next := seg.NextSegment(); next.Ok() {
687 if mseg := s.MergeUnchecked(seg, next); mseg.Ok() {
688 seg = mseg
689 }
690 }
691 return seg
692 }
693 694 // MergeAll merges all mergeable adjacent segments in the set. All existing
695 // iterators are invalidated.
696 func (s *addrSet) MergeAll() {
697 seg := s.FirstSegment()
698 if !seg.Ok() {
699 return
700 }
701 next := seg.NextSegment()
702 for next.Ok() {
703 if mseg := s.MergeUnchecked(seg, next); mseg.Ok() {
704 seg, next = mseg, mseg.NextSegment()
705 } else {
706 seg, next = next, next.NextSegment()
707 }
708 }
709 }
710 711 // MergeInsideRange attempts to merge all adjacent segments that contain a key
712 // in the specific range. All existing iterators are invalidated.
713 //
714 // MergeInsideRange only makes sense after mutating the set in a way that may
715 // change the mergeability of modified segments; callers should prefer to use
716 // MergePrev or MergeNext during the mutating loop instead (depending on the
717 // direction of iteration), in order to avoid a redundant search.
718 func (s *addrSet) MergeInsideRange(r addrRange) {
719 seg := s.LowerBoundSegment(r.Start)
720 if !seg.Ok() {
721 return
722 }
723 next := seg.NextSegment()
724 for next.Ok() && next.Start() < r.End {
725 if mseg := s.MergeUnchecked(seg, next); mseg.Ok() {
726 seg, next = mseg, mseg.NextSegment()
727 } else {
728 seg, next = next, next.NextSegment()
729 }
730 }
731 }
732 733 // MergeOutsideRange attempts to merge the segment containing r.Start with its
734 // predecessor, and the segment containing r.End-1 with its successor.
735 //
736 // MergeOutsideRange only makes sense after mutating the set in a way that may
737 // change the mergeability of modified segments; callers should prefer to use
738 // MergePrev or MergeNext during the mutating loop instead (depending on the
739 // direction of iteration), in order to avoid two redundant searches.
740 func (s *addrSet) MergeOutsideRange(r addrRange) {
741 first := s.FindSegment(r.Start)
742 if first.Ok() {
743 if prev := first.PrevSegment(); prev.Ok() {
744 s.Merge(prev, first)
745 }
746 }
747 last := s.FindSegment(r.End - 1)
748 if last.Ok() {
749 if next := last.NextSegment(); next.Ok() {
750 s.Merge(last, next)
751 }
752 }
753 }
754 755 // Split splits the given segment at the given key and returns iterators to the
756 // two resulting segments. All existing iterators (including seg, but not
757 // including the returned iterators) are invalidated.
758 //
759 // If the segment cannot be split at split (because split is at the start or
760 // end of the segment's range, so splitting would produce a segment with zero
761 // length, or because split falls outside the segment's range altogether),
762 // Split panics.
763 func (s *addrSet) Split(seg addrIterator, split uintptr) (addrIterator, addrIterator) {
764 if !seg.Range().CanSplitAt(split) {
765 panic(fmt.Sprintf("can't split %v at %v", seg.Range(), split))
766 }
767 return s.SplitUnchecked(seg, split)
768 }
769 770 // SplitUnchecked splits the given segment at the given key and returns
771 // iterators to the two resulting segments. All existing iterators (including
772 // seg, but not including the returned iterators) are invalidated.
773 //
774 // Preconditions: seg.Start() < key < seg.End().
775 func (s *addrSet) SplitUnchecked(seg addrIterator, split uintptr) (addrIterator, addrIterator) {
776 val1, val2 := (addrSetFunctions{}).Split(seg.Range(), seg.Value(), split)
777 end2 := seg.End()
778 seg.SetEndUnchecked(split)
779 seg.SetValue(val1)
780 seg2 := s.InsertWithoutMergingUnchecked(seg.NextGap(), addrRange{split, end2}, val2)
781 782 return seg2.PrevSegment(), seg2
783 }
784 785 // SplitBefore ensures that the given segment's start is at least start by
786 // splitting at start if necessary, and returns an updated iterator to the
787 // bounded segment. All existing iterators (including seg, but not including
788 // the returned iterator) are invalidated.
789 //
790 // SplitBefore is usually when mutating segments in a range. In such cases,
791 // when iterating segments in order of increasing keys, the first segment may
792 // extend beyond the start of the range to be mutated, and needs to be
793 // SplitBefore to ensure that only the part of the segment within the range is
794 // mutated. When iterating segments in order of decreasing keys, SplitBefore
795 // and SplitAfter; i.e. SplitBefore needs to be invoked on each segment, while
796 // SplitAfter only needs to be invoked on the first.
797 //
798 // Preconditions: start < seg.End().
799 func (s *addrSet) SplitBefore(seg addrIterator, start uintptr) addrIterator {
800 if seg.Range().CanSplitAt(start) {
801 _, seg = s.SplitUnchecked(seg, start)
802 }
803 return seg
804 }
805 806 // SplitAfter ensures that the given segment's end is at most end by splitting
807 // at end if necessary, and returns an updated iterator to the bounded segment.
808 // All existing iterators (including seg, but not including the returned
809 // iterator) are invalidated.
810 //
811 // SplitAfter is usually used when mutating segments in a range. In such cases,
812 // when iterating segments in order of increasing keys, each iterated segment
813 // may extend beyond the end of the range to be mutated, and needs to be
814 // SplitAfter to ensure that only the part of the segment within the range is
815 // mutated. When iterating segments in order of decreasing keys, SplitBefore
816 // and SplitAfter exchange roles; i.e. SplitBefore needs to be invoked on each
817 // segment, while SplitAfter only needs to be invoked on the first.
818 //
819 // Preconditions: seg.Start() < end.
820 func (s *addrSet) SplitAfter(seg addrIterator, end uintptr) addrIterator {
821 if seg.Range().CanSplitAt(end) {
822 seg, _ = s.SplitUnchecked(seg, end)
823 }
824 return seg
825 }
826 827 // Isolate ensures that the given segment's range is a subset of r by splitting
828 // at r.Start and r.End if necessary, and returns an updated iterator to the
829 // bounded segment. All existing iterators (including seg, but not including
830 // the returned iterators) are invalidated.
831 //
832 // Isolate is usually used when mutating part of a single segment, or when
833 // mutating segments in a range where the first segment is not necessarily
834 // split, making use of SplitBefore/SplitAfter complex.
835 //
836 // Preconditions: seg.Range().Overlaps(r).
837 func (s *addrSet) Isolate(seg addrIterator, r addrRange) addrIterator {
838 if seg.Range().CanSplitAt(r.Start) {
839 _, seg = s.SplitUnchecked(seg, r.Start)
840 }
841 if seg.Range().CanSplitAt(r.End) {
842 seg, _ = s.SplitUnchecked(seg, r.End)
843 }
844 return seg
845 }
846 847 // LowerBoundSegmentSplitBefore combines LowerBoundSegment and SplitBefore.
848 //
849 // LowerBoundSegmentSplitBefore is usually used when mutating segments in a
850 // range while iterating them in order of increasing keys. In such cases,
851 // LowerBoundSegmentSplitBefore provides an iterator to the first segment to be
852 // mutated, suitable as the initial value for a loop variable.
853 func (s *addrSet) LowerBoundSegmentSplitBefore(min uintptr) addrIterator {
854 seg, gap := s.Find(min)
855 if seg.Ok() {
856 return s.SplitBefore(seg, min)
857 }
858 return gap.NextSegment()
859 }
860 861 // UpperBoundSegmentSplitAfter combines UpperBoundSegment and SplitAfter.
862 //
863 // UpperBoundSegmentSplitAfter is usually used when mutating segments in a
864 // range while iterating them in order of decreasing keys. In such cases,
865 // UpperBoundSegmentSplitAfter provides an iterator to the first segment to be
866 // mutated, suitable as the initial value for a loop variable.
867 func (s *addrSet) UpperBoundSegmentSplitAfter(max uintptr) addrIterator {
868 seg, gap := s.Find(max)
869 if seg.Ok() {
870 return s.SplitAfter(seg, max)
871 }
872 return gap.PrevSegment()
873 }
874 875 // VisitRange applies the function f to all segments intersecting the range r,
876 // in order of ascending keys. Segments will not be split, so f may be called
877 // on segments lying partially outside r. Non-empty gaps between segments are
878 // skipped. If a call to f returns false, VisitRange stops iteration
879 // immediately.
880 //
881 // N.B. f must not invalidate iterators into s.
882 func (s *addrSet) VisitRange(r addrRange, f func(seg addrIterator) bool) {
883 for seg := s.LowerBoundSegment(r.Start); seg.Ok() && seg.Start() < r.End; seg = seg.NextSegment() {
884 if !f(seg) {
885 return
886 }
887 }
888 }
889 890 // VisitFullRange is equivalent to VisitRange, except that if any key in r that
891 // is visited before f returns false does not correspond to a segment,
892 // VisitFullRange panics.
893 func (s *addrSet) VisitFullRange(r addrRange, f func(seg addrIterator) bool) {
894 pos := r.Start
895 seg := s.FindSegment(r.Start)
896 for {
897 if !seg.Ok() {
898 panic(fmt.Sprintf("missing segment at %v", pos))
899 }
900 if !f(seg) {
901 return
902 }
903 pos = seg.End()
904 if r.End <= pos {
905 return
906 }
907 seg, _ = seg.NextNonEmpty()
908 }
909 }
910 911 // MutateRange applies the function f to all segments intersecting the range r,
912 // in order of ascending keys. Segments that lie partially outside r are split
913 // before f is called, such that f only observes segments entirely within r.
914 // Iterated segments are merged again after f is called. Non-empty gaps between
915 // segments are skipped. If a call to f returns false, MutateRange stops
916 // iteration immediately.
917 //
918 // MutateRange invalidates all existing iterators.
919 //
920 // N.B. f must not invalidate iterators into s.
921 func (s *addrSet) MutateRange(r addrRange, f func(seg addrIterator) bool) {
922 seg := s.LowerBoundSegmentSplitBefore(r.Start)
923 for seg.Ok() && seg.Start() < r.End {
924 seg = s.SplitAfter(seg, r.End)
925 cont := f(seg)
926 seg = s.MergePrev(seg)
927 if !cont {
928 s.MergeNext(seg)
929 return
930 }
931 seg = seg.NextSegment()
932 }
933 if seg.Ok() {
934 s.MergePrev(seg)
935 }
936 }
937 938 // MutateFullRange is equivalent to MutateRange, except that if any key in r
939 // that is visited before f returns false does not correspond to a segment,
940 // MutateFullRange panics.
941 func (s *addrSet) MutateFullRange(r addrRange, f func(seg addrIterator) bool) {
942 seg := s.FindSegment(r.Start)
943 if !seg.Ok() {
944 panic(fmt.Sprintf("missing segment at %v", r.Start))
945 }
946 seg = s.SplitBefore(seg, r.Start)
947 for {
948 seg = s.SplitAfter(seg, r.End)
949 cont := f(seg)
950 end := seg.End()
951 seg = s.MergePrev(seg)
952 if !cont || r.End <= end {
953 s.MergeNext(seg)
954 return
955 }
956 seg = seg.NextSegment()
957 if !seg.Ok() || seg.Start() != end {
958 panic(fmt.Sprintf("missing segment at %v", end))
959 }
960 }
961 }
962 963 // +stateify savable
964 type addrnode struct {
965 // An internal binary tree node looks like:
966 //
967 // K
968 // / \
969 // Cl Cr
970 //
971 // where all keys in the subtree rooted by Cl (the left subtree) are less
972 // than K (the key of the parent node), and all keys in the subtree rooted
973 // by Cr (the right subtree) are greater than K.
974 //
975 // An internal B-tree node's indexes work out to look like:
976 //
977 // K0 K1 K2 ... Kn-1
978 // / \/ \/ \ ... / \
979 // C0 C1 C2 C3 ... Cn-1 Cn
980 //
981 // where n is nrSegments.
982 nrSegments int
983 984 // parent is a pointer to this node's parent. If this node is root, parent
985 // is nil.
986 parent *addrnode
987 988 // parentIndex is the index of this node in parent.children.
989 parentIndex int
990 991 // Flag for internal nodes that is technically redundant with "children[0]
992 // != nil", but is stored in the first cache line. "hasChildren" rather
993 // than "isLeaf" because false must be the correct value for an empty root.
994 hasChildren bool
995 996 // The longest gap within this node. If the node is a leaf, it's simply the
997 // maximum gap among all the (nrSegments+1) gaps formed by its nrSegments keys
998 // including the 0th and nrSegments-th gap possibly shared with its upper-level
999 // nodes; if it's a non-leaf node, it's the max of all children's maxGap.
1000 maxGap addrdynamicGap
1001 1002 // Nodes store keys and values in separate arrays to maximize locality in
1003 // the common case (scanning keys for lookup).
1004 keys [addrmaxDegree - 1]addrRange
1005 values [addrmaxDegree - 1]*objectEncodeState
1006 children [addrmaxDegree]*addrnode
1007 }
1008 1009 // firstSegment returns the first segment in the subtree rooted by n.
1010 //
1011 // Preconditions: n.nrSegments != 0.
1012 func (n *addrnode) firstSegment() addrIterator {
1013 for n.hasChildren {
1014 n = n.children[0]
1015 }
1016 return addrIterator{n, 0}
1017 }
1018 1019 // lastSegment returns the last segment in the subtree rooted by n.
1020 //
1021 // Preconditions: n.nrSegments != 0.
1022 func (n *addrnode) lastSegment() addrIterator {
1023 for n.hasChildren {
1024 n = n.children[n.nrSegments]
1025 }
1026 return addrIterator{n, n.nrSegments - 1}
1027 }
1028 1029 func (n *addrnode) prevSibling() *addrnode {
1030 if n.parent == nil || n.parentIndex == 0 {
1031 return nil
1032 }
1033 return n.parent.children[n.parentIndex-1]
1034 }
1035 1036 func (n *addrnode) nextSibling() *addrnode {
1037 if n.parent == nil || n.parentIndex == n.parent.nrSegments {
1038 return nil
1039 }
1040 return n.parent.children[n.parentIndex+1]
1041 }
1042 1043 // rebalanceBeforeInsert splits n and its ancestors if they are full, as
1044 // required for insertion, and returns an updated iterator to the position
1045 // represented by gap.
1046 func (n *addrnode) rebalanceBeforeInsert(gap addrGapIterator) addrGapIterator {
1047 if n.nrSegments < addrmaxDegree-1 {
1048 return gap
1049 }
1050 if n.parent != nil {
1051 gap = n.parent.rebalanceBeforeInsert(gap)
1052 }
1053 if n.parent == nil {
1054 1055 left := &addrnode{
1056 nrSegments: addrminDegree - 1,
1057 parent: n,
1058 parentIndex: 0,
1059 hasChildren: n.hasChildren,
1060 }
1061 right := &addrnode{
1062 nrSegments: addrminDegree - 1,
1063 parent: n,
1064 parentIndex: 1,
1065 hasChildren: n.hasChildren,
1066 }
1067 copy(left.keys[:addrminDegree-1], n.keys[:addrminDegree-1])
1068 copy(left.values[:addrminDegree-1], n.values[:addrminDegree-1])
1069 copy(right.keys[:addrminDegree-1], n.keys[addrminDegree:])
1070 copy(right.values[:addrminDegree-1], n.values[addrminDegree:])
1071 n.keys[0], n.values[0] = n.keys[addrminDegree-1], n.values[addrminDegree-1]
1072 addrzeroValueSlice(n.values[1:])
1073 if n.hasChildren {
1074 copy(left.children[:addrminDegree], n.children[:addrminDegree])
1075 copy(right.children[:addrminDegree], n.children[addrminDegree:])
1076 addrzeroNodeSlice(n.children[2:])
1077 for i := 0; i < addrminDegree; i++ {
1078 left.children[i].parent = left
1079 left.children[i].parentIndex = i
1080 right.children[i].parent = right
1081 right.children[i].parentIndex = i
1082 }
1083 }
1084 n.nrSegments = 1
1085 n.hasChildren = true
1086 n.children[0] = left
1087 n.children[1] = right
1088 1089 if addrtrackGaps != 0 {
1090 left.updateMaxGapLocal()
1091 right.updateMaxGapLocal()
1092 }
1093 if gap.node != n {
1094 return gap
1095 }
1096 if gap.index < addrminDegree {
1097 return addrGapIterator{left, gap.index}
1098 }
1099 return addrGapIterator{right, gap.index - addrminDegree}
1100 }
1101 1102 copy(n.parent.keys[n.parentIndex+1:], n.parent.keys[n.parentIndex:n.parent.nrSegments])
1103 copy(n.parent.values[n.parentIndex+1:], n.parent.values[n.parentIndex:n.parent.nrSegments])
1104 n.parent.keys[n.parentIndex], n.parent.values[n.parentIndex] = n.keys[addrminDegree-1], n.values[addrminDegree-1]
1105 copy(n.parent.children[n.parentIndex+2:], n.parent.children[n.parentIndex+1:n.parent.nrSegments+1])
1106 for i := n.parentIndex + 2; i < n.parent.nrSegments+2; i++ {
1107 n.parent.children[i].parentIndex = i
1108 }
1109 sibling := &addrnode{
1110 nrSegments: addrminDegree - 1,
1111 parent: n.parent,
1112 parentIndex: n.parentIndex + 1,
1113 hasChildren: n.hasChildren,
1114 }
1115 n.parent.children[n.parentIndex+1] = sibling
1116 n.parent.nrSegments++
1117 copy(sibling.keys[:addrminDegree-1], n.keys[addrminDegree:])
1118 copy(sibling.values[:addrminDegree-1], n.values[addrminDegree:])
1119 addrzeroValueSlice(n.values[addrminDegree-1:])
1120 if n.hasChildren {
1121 copy(sibling.children[:addrminDegree], n.children[addrminDegree:])
1122 addrzeroNodeSlice(n.children[addrminDegree:])
1123 for i := 0; i < addrminDegree; i++ {
1124 sibling.children[i].parent = sibling
1125 sibling.children[i].parentIndex = i
1126 }
1127 }
1128 n.nrSegments = addrminDegree - 1
1129 1130 if addrtrackGaps != 0 {
1131 n.updateMaxGapLocal()
1132 sibling.updateMaxGapLocal()
1133 }
1134 1135 if gap.node != n {
1136 return gap
1137 }
1138 if gap.index < addrminDegree {
1139 return gap
1140 }
1141 return addrGapIterator{sibling, gap.index - addrminDegree}
1142 }
1143 1144 // rebalanceAfterRemove "unsplits" n and its ancestors if they are deficient
1145 // (contain fewer segments than required by B-tree invariants), as required for
1146 // removal, and returns an updated iterator to the position represented by gap.
1147 //
1148 // Precondition: n is the only node in the tree that may currently violate a
1149 // B-tree invariant.
1150 func (n *addrnode) rebalanceAfterRemove(gap addrGapIterator) addrGapIterator {
1151 for {
1152 if n.nrSegments >= addrminDegree-1 {
1153 return gap
1154 }
1155 if n.parent == nil {
1156 1157 return gap
1158 }
1159 1160 if sibling := n.prevSibling(); sibling != nil && sibling.nrSegments >= addrminDegree {
1161 copy(n.keys[1:], n.keys[:n.nrSegments])
1162 copy(n.values[1:], n.values[:n.nrSegments])
1163 n.keys[0] = n.parent.keys[n.parentIndex-1]
1164 n.values[0] = n.parent.values[n.parentIndex-1]
1165 n.parent.keys[n.parentIndex-1] = sibling.keys[sibling.nrSegments-1]
1166 n.parent.values[n.parentIndex-1] = sibling.values[sibling.nrSegments-1]
1167 addrSetFunctions{}.ClearValue(&sibling.values[sibling.nrSegments-1])
1168 if n.hasChildren {
1169 copy(n.children[1:], n.children[:n.nrSegments+1])
1170 n.children[0] = sibling.children[sibling.nrSegments]
1171 sibling.children[sibling.nrSegments] = nil
1172 n.children[0].parent = n
1173 n.children[0].parentIndex = 0
1174 for i := 1; i < n.nrSegments+2; i++ {
1175 n.children[i].parentIndex = i
1176 }
1177 }
1178 n.nrSegments++
1179 sibling.nrSegments--
1180 1181 if addrtrackGaps != 0 {
1182 n.updateMaxGapLocal()
1183 sibling.updateMaxGapLocal()
1184 }
1185 if gap.node == sibling && gap.index == sibling.nrSegments {
1186 return addrGapIterator{n, 0}
1187 }
1188 if gap.node == n {
1189 return addrGapIterator{n, gap.index + 1}
1190 }
1191 return gap
1192 }
1193 if sibling := n.nextSibling(); sibling != nil && sibling.nrSegments >= addrminDegree {
1194 n.keys[n.nrSegments] = n.parent.keys[n.parentIndex]
1195 n.values[n.nrSegments] = n.parent.values[n.parentIndex]
1196 n.parent.keys[n.parentIndex] = sibling.keys[0]
1197 n.parent.values[n.parentIndex] = sibling.values[0]
1198 copy(sibling.keys[:sibling.nrSegments-1], sibling.keys[1:])
1199 copy(sibling.values[:sibling.nrSegments-1], sibling.values[1:])
1200 addrSetFunctions{}.ClearValue(&sibling.values[sibling.nrSegments-1])
1201 if n.hasChildren {
1202 n.children[n.nrSegments+1] = sibling.children[0]
1203 copy(sibling.children[:sibling.nrSegments], sibling.children[1:])
1204 sibling.children[sibling.nrSegments] = nil
1205 n.children[n.nrSegments+1].parent = n
1206 n.children[n.nrSegments+1].parentIndex = n.nrSegments + 1
1207 for i := 0; i < sibling.nrSegments; i++ {
1208 sibling.children[i].parentIndex = i
1209 }
1210 }
1211 n.nrSegments++
1212 sibling.nrSegments--
1213 1214 if addrtrackGaps != 0 {
1215 n.updateMaxGapLocal()
1216 sibling.updateMaxGapLocal()
1217 }
1218 if gap.node == sibling {
1219 if gap.index == 0 {
1220 return addrGapIterator{n, n.nrSegments}
1221 }
1222 return addrGapIterator{sibling, gap.index - 1}
1223 }
1224 return gap
1225 }
1226 1227 p := n.parent
1228 if p.nrSegments == 1 {
1229 1230 left, right := p.children[0], p.children[1]
1231 p.nrSegments = left.nrSegments + right.nrSegments + 1
1232 p.hasChildren = left.hasChildren
1233 p.keys[left.nrSegments] = p.keys[0]
1234 p.values[left.nrSegments] = p.values[0]
1235 copy(p.keys[:left.nrSegments], left.keys[:left.nrSegments])
1236 copy(p.values[:left.nrSegments], left.values[:left.nrSegments])
1237 copy(p.keys[left.nrSegments+1:], right.keys[:right.nrSegments])
1238 copy(p.values[left.nrSegments+1:], right.values[:right.nrSegments])
1239 if left.hasChildren {
1240 copy(p.children[:left.nrSegments+1], left.children[:left.nrSegments+1])
1241 copy(p.children[left.nrSegments+1:], right.children[:right.nrSegments+1])
1242 for i := 0; i < p.nrSegments+1; i++ {
1243 p.children[i].parent = p
1244 p.children[i].parentIndex = i
1245 }
1246 } else {
1247 p.children[0] = nil
1248 p.children[1] = nil
1249 }
1250 1251 if gap.node == left {
1252 return addrGapIterator{p, gap.index}
1253 }
1254 if gap.node == right {
1255 return addrGapIterator{p, gap.index + left.nrSegments + 1}
1256 }
1257 return gap
1258 }
1259 // Merge n and either sibling, along with the segment separating the
1260 // two, into whichever of the two nodes comes first. This is the
1261 // reverse of the non-root splitting case in
1262 // node.rebalanceBeforeInsert.
1263 var left, right *addrnode
1264 if n.parentIndex > 0 {
1265 left = n.prevSibling()
1266 right = n
1267 } else {
1268 left = n
1269 right = n.nextSibling()
1270 }
1271 1272 if gap.node == right {
1273 gap = addrGapIterator{left, gap.index + left.nrSegments + 1}
1274 }
1275 left.keys[left.nrSegments] = p.keys[left.parentIndex]
1276 left.values[left.nrSegments] = p.values[left.parentIndex]
1277 copy(left.keys[left.nrSegments+1:], right.keys[:right.nrSegments])
1278 copy(left.values[left.nrSegments+1:], right.values[:right.nrSegments])
1279 if left.hasChildren {
1280 copy(left.children[left.nrSegments+1:], right.children[:right.nrSegments+1])
1281 for i := left.nrSegments + 1; i < left.nrSegments+right.nrSegments+2; i++ {
1282 left.children[i].parent = left
1283 left.children[i].parentIndex = i
1284 }
1285 }
1286 left.nrSegments += right.nrSegments + 1
1287 copy(p.keys[left.parentIndex:], p.keys[left.parentIndex+1:p.nrSegments])
1288 copy(p.values[left.parentIndex:], p.values[left.parentIndex+1:p.nrSegments])
1289 addrSetFunctions{}.ClearValue(&p.values[p.nrSegments-1])
1290 copy(p.children[left.parentIndex+1:], p.children[left.parentIndex+2:p.nrSegments+1])
1291 for i := 0; i < p.nrSegments; i++ {
1292 p.children[i].parentIndex = i
1293 }
1294 p.children[p.nrSegments] = nil
1295 p.nrSegments--
1296 1297 if addrtrackGaps != 0 {
1298 left.updateMaxGapLocal()
1299 }
1300 1301 n = p
1302 }
1303 }
1304 1305 // updateMaxGapLeaf updates maxGap bottom-up from the calling leaf until no
1306 // necessary update.
1307 //
1308 // Preconditions: n must be a leaf node, trackGaps must be 1.
1309 func (n *addrnode) updateMaxGapLeaf() {
1310 if n.hasChildren {
1311 panic(fmt.Sprintf("updateMaxGapLeaf should always be called on leaf node: %v", n))
1312 }
1313 max := n.calculateMaxGapLeaf()
1314 if max == n.maxGap.Get() {
1315 1316 return
1317 }
1318 oldMax := n.maxGap.Get()
1319 n.maxGap.Set(max)
1320 if max > oldMax {
1321 1322 for p := n.parent; p != nil; p = p.parent {
1323 if p.maxGap.Get() >= max {
1324 1325 break
1326 }
1327 1328 p.maxGap.Set(max)
1329 }
1330 return
1331 }
1332 1333 for p := n.parent; p != nil; p = p.parent {
1334 if p.maxGap.Get() > oldMax {
1335 1336 break
1337 }
1338 1339 parentNewMax := p.calculateMaxGapInternal()
1340 if p.maxGap.Get() == parentNewMax {
1341 1342 break
1343 }
1344 1345 p.maxGap.Set(parentNewMax)
1346 }
1347 }
1348 1349 // updateMaxGapLocal updates maxGap of the calling node solely with no
1350 // propagation to ancestor nodes.
1351 //
1352 // Precondition: trackGaps must be 1.
1353 func (n *addrnode) updateMaxGapLocal() {
1354 if !n.hasChildren {
1355 1356 n.maxGap.Set(n.calculateMaxGapLeaf())
1357 } else {
1358 1359 n.maxGap.Set(n.calculateMaxGapInternal())
1360 }
1361 }
1362 1363 // calculateMaxGapLeaf iterates the gaps within a leaf node and calculate the
1364 // max.
1365 //
1366 // Preconditions: n must be a leaf node.
1367 func (n *addrnode) calculateMaxGapLeaf() uintptr {
1368 max := addrGapIterator{n, 0}.Range().Length()
1369 for i := 1; i <= n.nrSegments; i++ {
1370 if current := (addrGapIterator{n, i}).Range().Length(); current > max {
1371 max = current
1372 }
1373 }
1374 return max
1375 }
1376 1377 // calculateMaxGapInternal iterates children's maxGap within an internal node n
1378 // and calculate the max.
1379 //
1380 // Preconditions: n must be a non-leaf node.
1381 func (n *addrnode) calculateMaxGapInternal() uintptr {
1382 max := n.children[0].maxGap.Get()
1383 for i := 1; i <= n.nrSegments; i++ {
1384 if current := n.children[i].maxGap.Get(); current > max {
1385 max = current
1386 }
1387 }
1388 return max
1389 }
1390 1391 // searchFirstLargeEnoughGap returns the first gap having at least minSize length
1392 // in the subtree rooted by n. If not found, return a terminal gap iterator.
1393 func (n *addrnode) searchFirstLargeEnoughGap(minSize uintptr) addrGapIterator {
1394 if n.maxGap.Get() < minSize {
1395 return addrGapIterator{}
1396 }
1397 if n.hasChildren {
1398 for i := 0; i <= n.nrSegments; i++ {
1399 if largeEnoughGap := n.children[i].searchFirstLargeEnoughGap(minSize); largeEnoughGap.Ok() {
1400 return largeEnoughGap
1401 }
1402 }
1403 } else {
1404 for i := 0; i <= n.nrSegments; i++ {
1405 currentGap := addrGapIterator{n, i}
1406 if currentGap.Range().Length() >= minSize {
1407 return currentGap
1408 }
1409 }
1410 }
1411 panic(fmt.Sprintf("invalid maxGap in %v", n))
1412 }
1413 1414 // searchLastLargeEnoughGap returns the last gap having at least minSize length
1415 // in the subtree rooted by n. If not found, return a terminal gap iterator.
1416 func (n *addrnode) searchLastLargeEnoughGap(minSize uintptr) addrGapIterator {
1417 if n.maxGap.Get() < minSize {
1418 return addrGapIterator{}
1419 }
1420 if n.hasChildren {
1421 for i := n.nrSegments; i >= 0; i-- {
1422 if largeEnoughGap := n.children[i].searchLastLargeEnoughGap(minSize); largeEnoughGap.Ok() {
1423 return largeEnoughGap
1424 }
1425 }
1426 } else {
1427 for i := n.nrSegments; i >= 0; i-- {
1428 currentGap := addrGapIterator{n, i}
1429 if currentGap.Range().Length() >= minSize {
1430 return currentGap
1431 }
1432 }
1433 }
1434 panic(fmt.Sprintf("invalid maxGap in %v", n))
1435 }
1436 1437 // A Iterator is conceptually one of:
1438 //
1439 // - A pointer to a segment in a set; or
1440 //
1441 // - A terminal iterator, which is a sentinel indicating that the end of
1442 // iteration has been reached.
1443 //
1444 // Iterators are copyable values and are meaningfully equality-comparable. The
1445 // zero value of Iterator is a terminal iterator.
1446 //
1447 // Unless otherwise specified, any mutation of a set invalidates all existing
1448 // iterators into the set.
1449 type addrIterator struct {
1450 // node is the node containing the iterated segment. If the iterator is
1451 // terminal, node is nil.
1452 node *addrnode
1453 1454 // index is the index of the segment in node.keys/values.
1455 index int
1456 }
1457 1458 // Ok returns true if the iterator is not terminal. All other methods are only
1459 // valid for non-terminal iterators.
1460 func (seg addrIterator) Ok() bool {
1461 return seg.node != nil
1462 }
1463 1464 // Range returns the iterated segment's range key.
1465 func (seg addrIterator) Range() addrRange {
1466 return seg.node.keys[seg.index]
1467 }
1468 1469 // Start is equivalent to Range().Start, but should be preferred if only the
1470 // start of the range is needed.
1471 func (seg addrIterator) Start() uintptr {
1472 return seg.node.keys[seg.index].Start
1473 }
1474 1475 // End is equivalent to Range().End, but should be preferred if only the end of
1476 // the range is needed.
1477 func (seg addrIterator) End() uintptr {
1478 return seg.node.keys[seg.index].End
1479 }
1480 1481 // SetRangeUnchecked mutates the iterated segment's range key. This operation
1482 // does not invalidate any iterators.
1483 //
1484 // Preconditions:
1485 // - r.Length() > 0.
1486 // - The new range must not overlap an existing one:
1487 // - If seg.NextSegment().Ok(), then r.end <= seg.NextSegment().Start().
1488 // - If seg.PrevSegment().Ok(), then r.start >= seg.PrevSegment().End().
1489 func (seg addrIterator) SetRangeUnchecked(r addrRange) {
1490 seg.node.keys[seg.index] = r
1491 }
1492 1493 // SetRange mutates the iterated segment's range key. If the new range would
1494 // cause the iterated segment to overlap another segment, or if the new range
1495 // is invalid, SetRange panics. This operation does not invalidate any
1496 // iterators.
1497 func (seg addrIterator) SetRange(r addrRange) {
1498 if r.Length() <= 0 {
1499 panic(fmt.Sprintf("invalid segment range %v", r))
1500 }
1501 if prev := seg.PrevSegment(); prev.Ok() && r.Start < prev.End() {
1502 panic(fmt.Sprintf("new segment range %v overlaps segment range %v", r, prev.Range()))
1503 }
1504 if next := seg.NextSegment(); next.Ok() && r.End > next.Start() {
1505 panic(fmt.Sprintf("new segment range %v overlaps segment range %v", r, next.Range()))
1506 }
1507 seg.SetRangeUnchecked(r)
1508 }
1509 1510 // SetStartUnchecked mutates the iterated segment's start. This operation does
1511 // not invalidate any iterators.
1512 //
1513 // Preconditions: The new start must be valid:
1514 // - start < seg.End()
1515 // - If seg.PrevSegment().Ok(), then start >= seg.PrevSegment().End().
1516 func (seg addrIterator) SetStartUnchecked(start uintptr) {
1517 seg.node.keys[seg.index].Start = start
1518 }
1519 1520 // SetStart mutates the iterated segment's start. If the new start value would
1521 // cause the iterated segment to overlap another segment, or would result in an
1522 // invalid range, SetStart panics. This operation does not invalidate any
1523 // iterators.
1524 func (seg addrIterator) SetStart(start uintptr) {
1525 if start >= seg.End() {
1526 panic(fmt.Sprintf("new start %v would invalidate segment range %v", start, seg.Range()))
1527 }
1528 if prev := seg.PrevSegment(); prev.Ok() && start < prev.End() {
1529 panic(fmt.Sprintf("new start %v would cause segment range %v to overlap segment range %v", start, seg.Range(), prev.Range()))
1530 }
1531 seg.SetStartUnchecked(start)
1532 }
1533 1534 // SetEndUnchecked mutates the iterated segment's end. This operation does not
1535 // invalidate any iterators.
1536 //
1537 // Preconditions: The new end must be valid:
1538 // - end > seg.Start().
1539 // - If seg.NextSegment().Ok(), then end <= seg.NextSegment().Start().
1540 func (seg addrIterator) SetEndUnchecked(end uintptr) {
1541 seg.node.keys[seg.index].End = end
1542 }
1543 1544 // SetEnd mutates the iterated segment's end. If the new end value would cause
1545 // the iterated segment to overlap another segment, or would result in an
1546 // invalid range, SetEnd panics. This operation does not invalidate any
1547 // iterators.
1548 func (seg addrIterator) SetEnd(end uintptr) {
1549 if end <= seg.Start() {
1550 panic(fmt.Sprintf("new end %v would invalidate segment range %v", end, seg.Range()))
1551 }
1552 if next := seg.NextSegment(); next.Ok() && end > next.Start() {
1553 panic(fmt.Sprintf("new end %v would cause segment range %v to overlap segment range %v", end, seg.Range(), next.Range()))
1554 }
1555 seg.SetEndUnchecked(end)
1556 }
1557 1558 // Value returns a copy of the iterated segment's value.
1559 func (seg addrIterator) Value() *objectEncodeState {
1560 return seg.node.values[seg.index]
1561 }
1562 1563 // ValuePtr returns a pointer to the iterated segment's value. The pointer is
1564 // invalidated if the iterator is invalidated. This operation does not
1565 // invalidate any iterators.
1566 func (seg addrIterator) ValuePtr() **objectEncodeState {
1567 return &seg.node.values[seg.index]
1568 }
1569 1570 // SetValue mutates the iterated segment's value. This operation does not
1571 // invalidate any iterators.
1572 func (seg addrIterator) SetValue(val *objectEncodeState) {
1573 seg.node.values[seg.index] = val
1574 }
1575 1576 // PrevSegment returns the iterated segment's predecessor. If there is no
1577 // preceding segment, PrevSegment returns a terminal iterator.
1578 func (seg addrIterator) PrevSegment() addrIterator {
1579 if seg.node.hasChildren {
1580 return seg.node.children[seg.index].lastSegment()
1581 }
1582 if seg.index > 0 {
1583 return addrIterator{seg.node, seg.index - 1}
1584 }
1585 if seg.node.parent == nil {
1586 return addrIterator{}
1587 }
1588 return addrsegmentBeforePosition(seg.node.parent, seg.node.parentIndex)
1589 }
1590 1591 // NextSegment returns the iterated segment's successor. If there is no
1592 // succeeding segment, NextSegment returns a terminal iterator.
1593 func (seg addrIterator) NextSegment() addrIterator {
1594 if seg.node.hasChildren {
1595 return seg.node.children[seg.index+1].firstSegment()
1596 }
1597 if seg.index < seg.node.nrSegments-1 {
1598 return addrIterator{seg.node, seg.index + 1}
1599 }
1600 if seg.node.parent == nil {
1601 return addrIterator{}
1602 }
1603 return addrsegmentAfterPosition(seg.node.parent, seg.node.parentIndex)
1604 }
1605 1606 // PrevGap returns the gap immediately before the iterated segment.
1607 func (seg addrIterator) PrevGap() addrGapIterator {
1608 if seg.node.hasChildren {
1609 1610 return seg.node.children[seg.index].lastSegment().NextGap()
1611 }
1612 return addrGapIterator{seg.node, seg.index}
1613 }
1614 1615 // NextGap returns the gap immediately after the iterated segment.
1616 func (seg addrIterator) NextGap() addrGapIterator {
1617 if seg.node.hasChildren {
1618 return seg.node.children[seg.index+1].firstSegment().PrevGap()
1619 }
1620 return addrGapIterator{seg.node, seg.index + 1}
1621 }
1622 1623 // PrevNonEmpty returns the iterated segment's predecessor if it is adjacent,
1624 // or the gap before the iterated segment otherwise. If seg.Start() ==
1625 // Functions.MinKey(), PrevNonEmpty will return two terminal iterators.
1626 // Otherwise, exactly one of the iterators returned by PrevNonEmpty will be
1627 // non-terminal.
1628 func (seg addrIterator) PrevNonEmpty() (addrIterator, addrGapIterator) {
1629 if prev := seg.PrevSegment(); prev.Ok() && prev.End() == seg.Start() {
1630 return prev, addrGapIterator{}
1631 }
1632 return addrIterator{}, seg.PrevGap()
1633 }
1634 1635 // NextNonEmpty returns the iterated segment's successor if it is adjacent, or
1636 // the gap after the iterated segment otherwise. If seg.End() ==
1637 // Functions.MaxKey(), NextNonEmpty will return two terminal iterators.
1638 // Otherwise, exactly one of the iterators returned by NextNonEmpty will be
1639 // non-terminal.
1640 func (seg addrIterator) NextNonEmpty() (addrIterator, addrGapIterator) {
1641 if next := seg.NextSegment(); next.Ok() && next.Start() == seg.End() {
1642 return next, addrGapIterator{}
1643 }
1644 return addrIterator{}, seg.NextGap()
1645 }
1646 1647 // A GapIterator is conceptually one of:
1648 //
1649 // - A pointer to a position between two segments, before the first segment, or
1650 // after the last segment in a set, called a *gap*; or
1651 //
1652 // - A terminal iterator, which is a sentinel indicating that the end of
1653 // iteration has been reached.
1654 //
1655 // Note that the gap between two adjacent segments exists (iterators to it are
1656 // non-terminal), but has a length of zero. GapIterator.IsEmpty returns true
1657 // for such gaps. An empty set contains a single gap, spanning the entire range
1658 // of the set's keys.
1659 //
1660 // GapIterators are copyable values and are meaningfully equality-comparable.
1661 // The zero value of GapIterator is a terminal iterator.
1662 //
1663 // Unless otherwise specified, any mutation of a set invalidates all existing
1664 // iterators into the set.
1665 type addrGapIterator struct {
1666 // The representation of a GapIterator is identical to that of an Iterator,
1667 // except that index corresponds to positions between segments in the same
1668 // way as for node.children (see comment for node.nrSegments).
1669 node *addrnode
1670 index int
1671 }
1672 1673 // Ok returns true if the iterator is not terminal. All other methods are only
1674 // valid for non-terminal iterators.
1675 func (gap addrGapIterator) Ok() bool {
1676 return gap.node != nil
1677 }
1678 1679 // Range returns the range spanned by the iterated gap.
1680 func (gap addrGapIterator) Range() addrRange {
1681 return addrRange{gap.Start(), gap.End()}
1682 }
1683 1684 // Start is equivalent to Range().Start, but should be preferred if only the
1685 // start of the range is needed.
1686 func (gap addrGapIterator) Start() uintptr {
1687 if ps := gap.PrevSegment(); ps.Ok() {
1688 return ps.End()
1689 }
1690 return addrSetFunctions{}.MinKey()
1691 }
1692 1693 // End is equivalent to Range().End, but should be preferred if only the end of
1694 // the range is needed.
1695 func (gap addrGapIterator) End() uintptr {
1696 if ns := gap.NextSegment(); ns.Ok() {
1697 return ns.Start()
1698 }
1699 return addrSetFunctions{}.MaxKey()
1700 }
1701 1702 // IsEmpty returns true if the iterated gap is empty (that is, the "gap" is
1703 // between two adjacent segments.)
1704 func (gap addrGapIterator) IsEmpty() bool {
1705 return gap.Range().Length() == 0
1706 }
1707 1708 // PrevSegment returns the segment immediately before the iterated gap. If no
1709 // such segment exists, PrevSegment returns a terminal iterator.
1710 func (gap addrGapIterator) PrevSegment() addrIterator {
1711 return addrsegmentBeforePosition(gap.node, gap.index)
1712 }
1713 1714 // NextSegment returns the segment immediately after the iterated gap. If no
1715 // such segment exists, NextSegment returns a terminal iterator.
1716 func (gap addrGapIterator) NextSegment() addrIterator {
1717 return addrsegmentAfterPosition(gap.node, gap.index)
1718 }
1719 1720 // PrevGap returns the iterated gap's predecessor. If no such gap exists,
1721 // PrevGap returns a terminal iterator.
1722 func (gap addrGapIterator) PrevGap() addrGapIterator {
1723 seg := gap.PrevSegment()
1724 if !seg.Ok() {
1725 return addrGapIterator{}
1726 }
1727 return seg.PrevGap()
1728 }
1729 1730 // NextGap returns the iterated gap's successor. If no such gap exists, NextGap
1731 // returns a terminal iterator.
1732 func (gap addrGapIterator) NextGap() addrGapIterator {
1733 seg := gap.NextSegment()
1734 if !seg.Ok() {
1735 return addrGapIterator{}
1736 }
1737 return seg.NextGap()
1738 }
1739 1740 // NextLargeEnoughGap returns the iterated gap's first next gap with larger
1741 // length than minSize. If not found, return a terminal gap iterator (does NOT
1742 // include this gap itself).
1743 //
1744 // Precondition: trackGaps must be 1.
1745 func (gap addrGapIterator) NextLargeEnoughGap(minSize uintptr) addrGapIterator {
1746 if addrtrackGaps != 1 {
1747 panic("set is not tracking gaps")
1748 }
1749 if gap.node != nil && gap.node.hasChildren && gap.index == gap.node.nrSegments {
1750 1751 gap.node = gap.NextSegment().node
1752 gap.index = 0
1753 return gap.nextLargeEnoughGapHelper(minSize)
1754 }
1755 return gap.nextLargeEnoughGapHelper(minSize)
1756 }
1757 1758 // nextLargeEnoughGapHelper is the helper function used by NextLargeEnoughGap
1759 // to do the real recursions.
1760 //
1761 // Preconditions: gap is NOT the trailing gap of a non-leaf node.
1762 func (gap addrGapIterator) nextLargeEnoughGapHelper(minSize uintptr) addrGapIterator {
1763 for {
1764 1765 for gap.node != nil &&
1766 (gap.node.maxGap.Get() < minSize || (!gap.node.hasChildren && gap.index == gap.node.nrSegments)) {
1767 gap.node, gap.index = gap.node.parent, gap.node.parentIndex
1768 }
1769 1770 if gap.node == nil {
1771 return addrGapIterator{}
1772 }
1773 1774 gap.index++
1775 for gap.index <= gap.node.nrSegments {
1776 if gap.node.hasChildren {
1777 if largeEnoughGap := gap.node.children[gap.index].searchFirstLargeEnoughGap(minSize); largeEnoughGap.Ok() {
1778 return largeEnoughGap
1779 }
1780 } else {
1781 if gap.Range().Length() >= minSize {
1782 return gap
1783 }
1784 }
1785 gap.index++
1786 }
1787 gap.node, gap.index = gap.node.parent, gap.node.parentIndex
1788 if gap.node != nil && gap.index == gap.node.nrSegments {
1789 1790 gap.node, gap.index = gap.node.parent, gap.node.parentIndex
1791 }
1792 }
1793 }
1794 1795 // PrevLargeEnoughGap returns the iterated gap's first prev gap with larger or
1796 // equal length than minSize. If not found, return a terminal gap iterator
1797 // (does NOT include this gap itself).
1798 //
1799 // Precondition: trackGaps must be 1.
1800 func (gap addrGapIterator) PrevLargeEnoughGap(minSize uintptr) addrGapIterator {
1801 if addrtrackGaps != 1 {
1802 panic("set is not tracking gaps")
1803 }
1804 if gap.node != nil && gap.node.hasChildren && gap.index == 0 {
1805 1806 gap.node = gap.PrevSegment().node
1807 gap.index = gap.node.nrSegments
1808 return gap.prevLargeEnoughGapHelper(minSize)
1809 }
1810 return gap.prevLargeEnoughGapHelper(minSize)
1811 }
1812 1813 // prevLargeEnoughGapHelper is the helper function used by PrevLargeEnoughGap
1814 // to do the real recursions.
1815 //
1816 // Preconditions: gap is NOT the first gap of a non-leaf node.
1817 func (gap addrGapIterator) prevLargeEnoughGapHelper(minSize uintptr) addrGapIterator {
1818 for {
1819 1820 for gap.node != nil &&
1821 (gap.node.maxGap.Get() < minSize || (!gap.node.hasChildren && gap.index == 0)) {
1822 gap.node, gap.index = gap.node.parent, gap.node.parentIndex
1823 }
1824 1825 if gap.node == nil {
1826 return addrGapIterator{}
1827 }
1828 1829 gap.index--
1830 for gap.index >= 0 {
1831 if gap.node.hasChildren {
1832 if largeEnoughGap := gap.node.children[gap.index].searchLastLargeEnoughGap(minSize); largeEnoughGap.Ok() {
1833 return largeEnoughGap
1834 }
1835 } else {
1836 if gap.Range().Length() >= minSize {
1837 return gap
1838 }
1839 }
1840 gap.index--
1841 }
1842 gap.node, gap.index = gap.node.parent, gap.node.parentIndex
1843 if gap.node != nil && gap.index == 0 {
1844 1845 gap.node, gap.index = gap.node.parent, gap.node.parentIndex
1846 }
1847 }
1848 }
1849 1850 // segmentBeforePosition returns the predecessor segment of the position given
1851 // by n.children[i], which may or may not contain a child. If no such segment
1852 // exists, segmentBeforePosition returns a terminal iterator.
1853 func addrsegmentBeforePosition(n *addrnode, i int) addrIterator {
1854 for i == 0 {
1855 if n.parent == nil {
1856 return addrIterator{}
1857 }
1858 n, i = n.parent, n.parentIndex
1859 }
1860 return addrIterator{n, i - 1}
1861 }
1862 1863 // segmentAfterPosition returns the successor segment of the position given by
1864 // n.children[i], which may or may not contain a child. If no such segment
1865 // exists, segmentAfterPosition returns a terminal iterator.
1866 func addrsegmentAfterPosition(n *addrnode, i int) addrIterator {
1867 for i == n.nrSegments {
1868 if n.parent == nil {
1869 return addrIterator{}
1870 }
1871 n, i = n.parent, n.parentIndex
1872 }
1873 return addrIterator{n, i}
1874 }
1875 1876 func addrzeroValueSlice(slice []*objectEncodeState) {
1877 1878 for i := range slice {
1879 addrSetFunctions{}.ClearValue(&slice[i])
1880 }
1881 }
1882 1883 func addrzeroNodeSlice(slice []*addrnode) {
1884 for i := range slice {
1885 slice[i] = nil
1886 }
1887 }
1888 1889 // String stringifies a Set for debugging.
1890 func (s *addrSet) String() string {
1891 return s.root.String()
1892 }
1893 1894 // String stringifies a node (and all of its children) for debugging.
1895 func (n *addrnode) String() string {
1896 var buf bytes.Buffer
1897 n.writeDebugString(&buf, "")
1898 return buf.String()
1899 }
1900 1901 func (n *addrnode) writeDebugString(buf *bytes.Buffer, prefix string) {
1902 if n.hasChildren != (n.nrSegments > 0 && n.children[0] != nil) {
1903 buf.WriteString(prefix)
1904 buf.WriteString(fmt.Sprintf("WARNING: inconsistent value of hasChildren: got %v, want %v\n", n.hasChildren, !n.hasChildren))
1905 }
1906 for i := 0; i < n.nrSegments; i++ {
1907 if child := n.children[i]; child != nil {
1908 cprefix := fmt.Sprintf("%s- % 3d ", prefix, i)
1909 if child.parent != n || child.parentIndex != i {
1910 buf.WriteString(cprefix)
1911 buf.WriteString(fmt.Sprintf("WARNING: inconsistent linkage to parent: got (%p, %d), want (%p, %d)\n", child.parent, child.parentIndex, n, i))
1912 }
1913 child.writeDebugString(buf, fmt.Sprintf("%s- % 3d ", prefix, i))
1914 }
1915 buf.WriteString(prefix)
1916 if n.hasChildren {
1917 if addrtrackGaps != 0 {
1918 buf.WriteString(fmt.Sprintf("- % 3d: %v => %v, maxGap: %d\n", i, n.keys[i], n.values[i], n.maxGap.Get()))
1919 } else {
1920 buf.WriteString(fmt.Sprintf("- % 3d: %v => %v\n", i, n.keys[i], n.values[i]))
1921 }
1922 } else {
1923 buf.WriteString(fmt.Sprintf("- % 3d: %v => %v\n", i, n.keys[i], n.values[i]))
1924 }
1925 }
1926 if child := n.children[n.nrSegments]; child != nil {
1927 child.writeDebugString(buf, fmt.Sprintf("%s- % 3d ", prefix, n.nrSegments))
1928 }
1929 }
1930 1931 // FlatSegment represents a segment as a single object. FlatSegment is used as
1932 // an intermediate representation for save/restore and tests.
1933 //
1934 // +stateify savable
1935 type addrFlatSegment struct {
1936 Start uintptr
1937 End uintptr
1938 Value *objectEncodeState
1939 }
1940 1941 // ExportSlice returns a copy of all segments in the given set, in ascending
1942 // key order.
1943 func (s *addrSet) ExportSlice() []addrFlatSegment {
1944 var fs []addrFlatSegment
1945 for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() {
1946 fs = append(fs, addrFlatSegment{
1947 Start: seg.Start(),
1948 End: seg.End(),
1949 Value: seg.Value(),
1950 })
1951 }
1952 return fs
1953 }
1954 1955 // ImportSlice initializes the given set from the given slice.
1956 //
1957 // Preconditions:
1958 // - s must be empty.
1959 // - fs must represent a valid set (the segments in fs must have valid
1960 // lengths that do not overlap).
1961 // - The segments in fs must be sorted in ascending key order.
1962 func (s *addrSet) ImportSlice(fs []addrFlatSegment) error {
1963 if !s.IsEmpty() {
1964 return fmt.Errorf("cannot import into non-empty set %v", s)
1965 }
1966 gap := s.FirstGap()
1967 for i := range fs {
1968 f := &fs[i]
1969 r := addrRange{f.Start, f.End}
1970 if !gap.Range().IsSupersetOf(r) {
1971 return fmt.Errorf("segment overlaps a preceding segment or is incorrectly sorted: %v => %v", r, f.Value)
1972 }
1973 gap = s.InsertWithoutMerging(gap, r, f.Value).NextGap()
1974 }
1975 return nil
1976 }
1977 1978 // segmentTestCheck returns an error if s is incorrectly sorted, does not
1979 // contain exactly expectedSegments segments, or contains a segment which
1980 // fails the passed check.
1981 //
1982 // This should be used only for testing, and has been added to this package for
1983 // templating convenience.
1984 func (s *addrSet) segmentTestCheck(expectedSegments int, segFunc func(int, addrRange, *objectEncodeState) error) error {
1985 havePrev := false
1986 prev := uintptr(0)
1987 nrSegments := 0
1988 for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() {
1989 next := seg.Start()
1990 if havePrev && prev >= next {
1991 return fmt.Errorf("incorrect order: key %d (segment %d) >= key %d (segment %d)", prev, nrSegments-1, next, nrSegments)
1992 }
1993 if segFunc != nil {
1994 if err := segFunc(nrSegments, seg.Range(), seg.Value()); err != nil {
1995 return err
1996 }
1997 }
1998 prev = next
1999 havePrev = true
2000 nrSegments++
2001 }
2002 if nrSegments != expectedSegments {
2003 return fmt.Errorf("incorrect number of segments: got %d, wanted %d", nrSegments, expectedSegments)
2004 }
2005 return nil
2006 }
2007 2008 // countSegments counts the number of segments in the set.
2009 //
2010 // Similar to Check, this should only be used for testing.
2011 func (s *addrSet) countSegments() (segments int) {
2012 for seg := s.FirstSegment(); seg.Ok(); seg = seg.NextSegment() {
2013 segments++
2014 }
2015 return segments
2016 }
2017 func (s *addrSet) saveRoot() []addrFlatSegment {
2018 fs := s.ExportSlice()
2019 2020 fs = fs[:len(fs):len(fs)]
2021 return fs
2022 }
2023 2024 func (s *addrSet) loadRoot(_ context.Context, fs []addrFlatSegment) {
2025 if err := s.ImportSlice(fs); err != nil {
2026 panic(err)
2027 }
2028 }
2029