Line data Source code
1 : // Copyright 2022 The LevelDB-Go and Pebble Authors. All rights reserved. Use
2 : // of this source code is governed by a BSD-style license that can be found in
3 : // the LICENSE file.
4 :
5 : package keyspanimpl
6 :
7 : import (
8 : "bytes"
9 : "cmp"
10 : "fmt"
11 : "slices"
12 :
13 : "github.com/cockroachdb/pebble/internal/base"
14 : "github.com/cockroachdb/pebble/internal/invariants"
15 : "github.com/cockroachdb/pebble/internal/keyspan"
16 : "github.com/cockroachdb/pebble/internal/manifest"
17 : )
18 :
19 : // TODO(jackson): Consider implementing an optimization to seek lower levels
20 : // past higher levels' RANGEKEYDELs. This would be analaogous to the
21 : // optimization pebble.mergingIter performs for RANGEDELs during point key
22 : // seeks. It may not be worth it, because range keys are rare and cascading
23 : // seeks would require introducing key comparisons to switchTo{Min,Max}Heap
24 : // where there currently are none.
25 :
26 : // MergingIter merges spans across levels of the LSM, exposing an iterator over
27 : // spans that yields sets of spans fragmented at unique user key boundaries.
28 : //
29 : // A MergingIter is initialized with an arbitrary number of child iterators over
30 : // fragmented spans. Each child iterator exposes fragmented key spans, such that
31 : // overlapping keys are surfaced in a single Span. Key spans from one child
32 : // iterator may overlap key spans from another child iterator arbitrarily.
33 : //
34 : // The spans combined by MergingIter will return spans with keys sorted by
35 : // trailer descending. If the MergingIter is configured with a Transformer, it's
36 : // permitted to modify the ordering of the spans' keys returned by MergingIter.
37 : //
38 : // # Algorithm
39 : //
40 : // The merging iterator wraps child iterators, merging and fragmenting spans
41 : // across levels. The high-level algorithm is:
42 : //
43 : // 1. Initialize the heap with bound keys from child iterators' spans.
44 : // 2. Find the next [or previous] two unique user keys' from bounds.
45 : // 3. Consider the span formed between the two unique user keys a candidate
46 : // span.
47 : // 4. Determine if any of the child iterators' spans overlap the candidate
48 : // span.
49 : // 4a. If any of the child iterator's current bounds are end keys
50 : // (during forward iteration) or start keys (during reverse
51 : // iteration), then all the spans with that bound overlap the
52 : // candidate span.
53 : // 4b. Apply the configured transform, which may remove keys.
54 : // 4c. If no spans overlap, forget the smallest (forward iteration)
55 : // or largest (reverse iteration) unique user key and advance
56 : // the iterators to the next unique user key. Start again from 3.
57 : //
58 : // # Detailed algorithm
59 : //
60 : // Each level (i0, i1, ...) has a user-provided input FragmentIterator. The
61 : // merging iterator steps through individual boundaries of the underlying
62 : // spans separately. If the underlying FragmentIterator has fragments
63 : // [a,b){#2,#1} [b,c){#1} the mergingIterLevel.{next,prev} step through:
64 : //
65 : // (a, start), (b, end), (b, start), (c, end)
66 : //
67 : // Note that (a, start) and (b, end) are observed ONCE each, despite two keys
68 : // sharing those bounds. Also note that (b, end) and (b, start) are two distinct
69 : // iterator positions of a mergingIterLevel.
70 : //
71 : // The merging iterator maintains a heap (min during forward iteration, max
72 : // during reverse iteration) containing the boundKeys. Each boundKey is a
73 : // 3-tuple holding the bound user key, whether the bound is a start or end key
74 : // and the set of keys from that level that have that bound. The heap orders
75 : // based on the boundKey's user key only.
76 : //
77 : // The merging iterator is responsible for merging spans across levels to
78 : // determine which span is next, but it's also responsible for fragmenting
79 : // overlapping spans. Consider the example:
80 : //
81 : // i0: b---d e-----h
82 : // i1: a---c h-----k
83 : // i2: a------------------------------p
84 : //
85 : // fragments: a-b-c-d-e-----h-----k----------p
86 : //
87 : // None of the individual child iterators contain a span with the exact bounds
88 : // [c,d), but the merging iterator must produce a span [c,d). To accomplish
89 : // this, the merging iterator visits every span between unique boundary user
90 : // keys. In the above example, this is:
91 : //
92 : // [a,b), [b,c), [c,d), [d,e), [e, h), [h, k), [k, p)
93 : //
94 : // The merging iterator first initializes the heap to prepare for iteration.
95 : // The description below discusses the mechanics of forward iteration after a
96 : // call to First, but the mechanics are similar for reverse iteration and
97 : // other positioning methods.
98 : //
99 : // During a call to First, the heap is initialized by seeking every
100 : // mergingIterLevel to the first bound of the first fragment. In the above
101 : // example, this seeks the child iterators to:
102 : //
103 : // i0: (b, boundKindFragmentStart, [ [b,d) ])
104 : // i1: (a, boundKindFragmentStart, [ [a,c) ])
105 : // i2: (a, boundKindFragmentStart, [ [a,p) ])
106 : //
107 : // After fixing up the heap, the root of the heap is a boundKey with the
108 : // smallest user key ('a' in the example). Once the heap is setup for iteration
109 : // in the appropriate direction and location, the merging iterator uses
110 : // find{Next,Prev}FragmentSet to find the next/previous span bounds.
111 : //
112 : // During forward iteration, the root of the heap's user key is the start key
113 : // key of next merged span. findNextFragmentSet sets m.start to this user
114 : // key. The heap may contain other boundKeys with the same user key if another
115 : // level has a fragment starting or ending at the same key, so the
116 : // findNextFragmentSet method pulls from the heap until it finds the first key
117 : // greater than m.start. This key is used as the end key.
118 : //
119 : // In the above example, this results in m.start = 'a', m.end = 'b' and child
120 : // iterators in the following positions:
121 : //
122 : // i0: (b, boundKindFragmentStart, [ [b,d) ])
123 : // i1: (c, boundKindFragmentEnd, [ [a,c) ])
124 : // i2: (p, boundKindFragmentEnd, [ [a,p) ])
125 : //
126 : // With the user key bounds of the next merged span established,
127 : // findNextFragmentSet must determine which, if any, fragments overlap the span.
128 : // During forward iteration any child iterator that is now positioned at an end
129 : // boundary has an overlapping span. (Justification: The child iterator's end
130 : // boundary is ≥ m.end. The corresponding start boundary must be ≤ m.start since
131 : // there were no other user keys between m.start and m.end. So the fragments
132 : // associated with the iterator's current end boundary have start and end bounds
133 : // such that start ≤ m.start < m.end ≤ end).
134 : //
135 : // findNextFragmentSet iterates over the levels, collecting keys from any child
136 : // iterators positioned at end boundaries. In the above example, i1 and i2 are
137 : // positioned at end boundaries, so findNextFragmentSet collects the keys of
138 : // [a,c) and [a,p). These spans contain the merging iterator's [m.start, m.end)
139 : // span, but they may also extend beyond the m.start and m.end. The merging
140 : // iterator returns the keys with the merging iter's m.start and m.end bounds,
141 : // preserving the underlying keys' sequence numbers, key kinds and values.
142 : //
143 : // A MergingIter is configured with a Transform that's applied to the span
144 : // before surfacing it to the iterator user. A Transform may remove keys
145 : // arbitrarily, but it may not modify the values themselves.
146 : //
147 : // It may be the case that findNextFragmentSet finds no levels positioned at end
148 : // boundaries, or that there are no spans remaining after applying a transform,
149 : // in which case the span [m.start, m.end) overlaps with nothing. In this case
150 : // findNextFragmentSet loops, repeating the above process again until it finds a
151 : // span that does contain keys.
152 : //
153 : // # Memory safety
154 : //
155 : // The FragmentIterator interface only guarantees stability of a Span and its
156 : // associated slices until the next positioning method is called. Adjacent Spans
157 : // may be contained in different sstables, requring the FragmentIterator
158 : // implementation to close one sstable, releasing its memory, before opening the
159 : // next. Most of the state used by the MergingIter is derived from spans at
160 : // current child iterator positions only, ensuring state is stable. The one
161 : // exception is the start bound during forward iteration and the end bound
162 : // during reverse iteration.
163 : //
164 : // If the heap root originates from an end boundary when findNextFragmentSet
165 : // begins, a Next on the heap root level may invalidate the end boundary. To
166 : // accommodate this, find{Next,Prev}FragmentSet copy the initial boundary if the
167 : // subsequent Next/Prev would move to the next span.
168 : type MergingIter struct {
169 : comparer *base.Comparer
170 : *MergingBuffers
171 : // start and end hold the bounds for the span currently under the
172 : // iterator position.
173 : //
174 : // Invariant: None of the levels' iterators contain spans with a bound
175 : // between start and end. For all bounds b, b ≤ start || b ≥ end.
176 : start, end []byte
177 :
178 : // transformer defines a transformation to be applied to a span before it's
179 : // yielded to the user. Transforming may filter individual keys contained
180 : // within the span.
181 : transformer keyspan.Transformer
182 : // span holds the iterator's current span. This span is used as the
183 : // destination for transforms. Every tranformed span overwrites the
184 : // previous.
185 : span keyspan.Span
186 : dir int8
187 :
188 : // alloc preallocates mergingIterLevel and mergingIterItems for use by the
189 : // merging iterator. As long as the merging iterator is used with
190 : // manifest.NumLevels+3 and fewer fragment iterators, the merging iterator
191 : // will not need to allocate upon initialization. The value NumLevels+3
192 : // mirrors the preallocated levels in iterAlloc used for point iterators.
193 : // Invariant: cap(levels) == cap(items)
194 : alloc struct {
195 : levels [manifest.NumLevels + 3]mergingIterLevel
196 : items [manifest.NumLevels + 3]mergingIterItem
197 : }
198 : }
199 :
200 : // MergingBuffers holds buffers used while merging keyspans.
201 : type MergingBuffers struct {
202 : // keys holds all of the keys across all levels that overlap the key span
203 : // [start, end), sorted by Trailer descending. This slice is reconstituted
204 : // in synthesizeKeys from each mergingIterLevel's keys every time the
205 : // [start, end) bounds change.
206 : //
207 : // Each element points into a child iterator's memory, so the keys may not
208 : // be directly modified.
209 : keys []keyspan.Key
210 : // levels holds levels allocated by MergingIter.init. The MergingIter will
211 : // prefer use of its `manifest.NumLevels+3` array, so this slice will be
212 : // longer if set.
213 : levels []mergingIterLevel
214 : wrapFn keyspan.WrapFn
215 : // heap holds a slice for the merging iterator heap allocated by
216 : // MergingIter.init. The MergingIter will prefer use of its
217 : // `manifest.NumLevels+3` items array, so this slice will be longer if set.
218 : heap mergingIterHeap
219 : // buf is a buffer used to save [start, end) boundary keys.
220 : buf []byte
221 : }
222 :
223 : // PrepareForReuse discards any excessively large buffers.
224 2 : func (bufs *MergingBuffers) PrepareForReuse() {
225 2 : if cap(bufs.buf) > keyspan.BufferReuseMaxCapacity {
226 0 : bufs.buf = nil
227 0 : }
228 : }
229 :
230 : // MergingIter implements the FragmentIterator interface.
231 : var _ keyspan.FragmentIterator = (*MergingIter)(nil)
232 :
233 : type mergingIterLevel struct {
234 : iter keyspan.FragmentIterator
235 :
236 : // heapKey holds the current key at this level for use within the heap.
237 : heapKey boundKey
238 : }
239 :
240 2 : func (l *mergingIterLevel) next() error {
241 2 : if l.heapKey.kind == boundKindFragmentStart {
242 2 : l.heapKey = boundKey{
243 2 : kind: boundKindFragmentEnd,
244 2 : key: l.heapKey.span.End,
245 2 : span: l.heapKey.span,
246 2 : }
247 2 : return nil
248 2 : }
249 2 : s, err := l.iter.Next()
250 2 : switch {
251 1 : case err != nil:
252 1 : return err
253 2 : case s == nil:
254 2 : l.heapKey = boundKey{kind: boundKindInvalid}
255 2 : return nil
256 2 : default:
257 2 : l.heapKey = boundKey{
258 2 : kind: boundKindFragmentStart,
259 2 : key: s.Start,
260 2 : span: s,
261 2 : }
262 2 : return nil
263 : }
264 : }
265 :
266 2 : func (l *mergingIterLevel) prev() error {
267 2 : if l.heapKey.kind == boundKindFragmentEnd {
268 2 : l.heapKey = boundKey{
269 2 : kind: boundKindFragmentStart,
270 2 : key: l.heapKey.span.Start,
271 2 : span: l.heapKey.span,
272 2 : }
273 2 : return nil
274 2 : }
275 2 : s, err := l.iter.Prev()
276 2 : switch {
277 1 : case err != nil:
278 1 : return err
279 2 : case s == nil:
280 2 : l.heapKey = boundKey{kind: boundKindInvalid}
281 2 : return nil
282 2 : default:
283 2 : l.heapKey = boundKey{
284 2 : kind: boundKindFragmentEnd,
285 2 : key: s.End,
286 2 : span: s,
287 2 : }
288 2 : return nil
289 : }
290 : }
291 :
292 : // Init initializes the merging iterator with the provided fragment iterators.
293 : func (m *MergingIter) Init(
294 : comparer *base.Comparer,
295 : transformer keyspan.Transformer,
296 : bufs *MergingBuffers,
297 : iters ...keyspan.FragmentIterator,
298 2 : ) {
299 2 : *m = MergingIter{
300 2 : comparer: comparer,
301 2 : MergingBuffers: bufs,
302 2 : transformer: transformer,
303 2 : }
304 2 : m.heap.cmp = comparer.Compare
305 2 : levels, items := m.levels, m.heap.items
306 2 :
307 2 : // Invariant: cap(levels) >= cap(items)
308 2 : // Invariant: cap(alloc.levels) == cap(alloc.items)
309 2 : if len(iters) <= len(m.alloc.levels) {
310 2 : // The slices allocated on the MergingIter struct are large enough.
311 2 : m.levels = m.alloc.levels[:len(iters)]
312 2 : m.heap.items = m.alloc.items[:0]
313 2 : } else if len(iters) <= cap(levels) {
314 0 : // The existing heap-allocated slices are large enough, so reuse them.
315 0 : m.levels = levels[:len(iters)]
316 0 : m.heap.items = items[:0]
317 2 : } else {
318 2 : // Heap allocate new slices.
319 2 : m.levels = make([]mergingIterLevel, len(iters))
320 2 : m.heap.items = make([]mergingIterItem, 0, len(iters))
321 2 : }
322 2 : for i := range m.levels {
323 2 : m.levels[i] = mergingIterLevel{iter: iters[i]}
324 2 : if m.wrapFn != nil {
325 0 : m.levels[i].iter = m.wrapFn(m.levels[i].iter)
326 0 : }
327 : }
328 : }
329 :
330 : // AddLevel adds a new level to the bottom of the merging iterator. AddLevel
331 : // must be called after Init and before any other method.
332 2 : func (m *MergingIter) AddLevel(iter keyspan.FragmentIterator) {
333 2 : if m.wrapFn != nil {
334 0 : iter = m.wrapFn(iter)
335 0 : }
336 2 : m.levels = append(m.levels, mergingIterLevel{iter: iter})
337 : }
338 :
339 : // SeekGE moves the iterator to the first span covering a key greater than
340 : // or equal to the given key. This is equivalent to seeking to the first
341 : // span with an end key greater than the given key.
342 2 : func (m *MergingIter) SeekGE(key []byte) (*keyspan.Span, error) {
343 2 : // SeekGE(k) seeks to the first span with an end key greater than the given
344 2 : // key. The merged span M that we're searching for might straddle the seek
345 2 : // `key`. In this case, the M.Start may be a key ≤ the seek key.
346 2 : //
347 2 : // Consider a SeekGE(dog) in the following example.
348 2 : //
349 2 : // i0: b---d e-----h
350 2 : // i1: a---c h-----k
351 2 : // i2: a------------------------------p
352 2 : // merged: a-b-c-d-e-----h-----k----------p
353 2 : //
354 2 : // The merged span M containing 'dog' is [d,e). The 'd' of the merged span
355 2 : // comes from i0's [b,d)'s end boundary. The [b,d) span does not cover any
356 2 : // key >= dog, so we cannot find the span by positioning the child iterators
357 2 : // using a SeekGE(dog).
358 2 : //
359 2 : // Instead, if we take all the child iterators' spans bounds:
360 2 : // a b c d e h k p
361 2 : // We want to partition them into keys ≤ `key` and keys > `key`.
362 2 : // dog
363 2 : // │
364 2 : // a b c d│e h k p
365 2 : // │
366 2 : // The largest key on the left of the partition forms the merged span's
367 2 : // start key, and the smallest key on the right of the partition forms the
368 2 : // merged span's end key. Recharacterized:
369 2 : //
370 2 : // M.Start: the largest boundary ≤ k of any child span
371 2 : // M.End: the smallest boundary > k of any child span
372 2 : //
373 2 : // The FragmentIterator interface doesn't implement seeking by all bounds,
374 2 : // it implements seeking by containment. A SeekGE(k) will ensure we observe
375 2 : // all start boundaries ≥ k and all end boundaries > k but does not ensure
376 2 : // we observe end boundaries = k or any boundaries < k. A SeekLT(k) will
377 2 : // ensure we observe all start boundaries < k and all end boundaries ≤ k but
378 2 : // does not ensure we observe any start boundaries = k or any boundaries >
379 2 : // k. This forces us to seek in one direction and step in the other.
380 2 : //
381 2 : // In a SeekGE, we want to end up oriented in the forward direction when
382 2 : // complete, so we begin with searching for M.Start by SeekLT-ing every
383 2 : // child iterator to `k`. For every child span found, we determine the
384 2 : // largest bound ≤ `k` and use it to initialize our max heap. The resulting
385 2 : // root of the max heap is a preliminary value for `M.Start`.
386 2 : for i := range m.levels {
387 2 : l := &m.levels[i]
388 2 : s, err := l.iter.SeekLT(key)
389 2 : switch {
390 1 : case err != nil:
391 1 : return nil, err
392 2 : case s == nil:
393 2 : l.heapKey = boundKey{kind: boundKindInvalid}
394 2 : case m.comparer.Compare(s.End, key) <= 0:
395 2 : l.heapKey = boundKey{
396 2 : kind: boundKindFragmentEnd,
397 2 : key: s.End,
398 2 : span: s,
399 2 : }
400 2 : default:
401 2 : // s.End > key && s.Start < key
402 2 : // We need to use this span's start bound, since that's the largest
403 2 : // bound ≤ key.
404 2 : l.heapKey = boundKey{
405 2 : kind: boundKindFragmentStart,
406 2 : key: s.Start,
407 2 : span: s,
408 2 : }
409 : }
410 : }
411 2 : m.initMaxHeap()
412 2 : if len(m.heap.items) == 0 {
413 2 : // There are no spans covering any key < `key`. There is no span that
414 2 : // straddles the seek key. Reorient the heap into a min heap and return
415 2 : // the first span we find in the forward direction.
416 2 : if err := m.switchToMinHeap(); err != nil {
417 1 : return nil, err
418 1 : }
419 2 : return m.findNextFragmentSet()
420 : }
421 :
422 : // The heap root is now the largest boundary key b such that:
423 : // 1. b < k
424 : // 2. b = k, and b is an end boundary
425 : // There's a third case that we will need to consider later, after we've
426 : // switched to a min heap:
427 : // 3. there exists a start boundary key b such that b = k.
428 : // A start boundary key equal to k would not be surfaced when we seeked all
429 : // the levels using SeekLT(k), since no key <k would be covered within a
430 : // span within an inclusive `k` start boundary.
431 : //
432 : // Assume that the tightest boundary ≤ k is the current heap root (cases 1 &
433 : // 2). After we switch to a min heap, we'll check for the third case and
434 : // adjust the start boundary if necessary.
435 2 : m.start = m.heap.items[0].boundKey.key
436 2 :
437 2 : // Before switching the direction of the heap, save a copy of the start
438 2 : // boundary if it's the end boundary of some child span. Next-ing the child
439 2 : // iterator might switch files and invalidate the memory of the bound.
440 2 : if m.heap.items[0].boundKey.kind == boundKindFragmentEnd {
441 2 : m.buf = append(m.buf[:0], m.start...)
442 2 : m.start = m.buf
443 2 : }
444 :
445 : // Switch to a min heap. This will move each level to the next bound in
446 : // every level, and then establish a min heap. This allows us to obtain the
447 : // smallest boundary key > `key`, which will serve as our candidate end
448 : // bound.
449 2 : if err := m.switchToMinHeap(); err != nil {
450 1 : return nil, err
451 2 : } else if len(m.heap.items) == 0 {
452 2 : return nil, nil
453 2 : }
454 :
455 : // Check for the case 3 described above. It's possible that when we switch
456 : // heap directions, we discover a start boundary of some child span that is
457 : // equal to the seek key `key`. In this case, we want this key to be our
458 : // start boundary.
459 2 : if m.heap.items[0].boundKey.kind == boundKindFragmentStart &&
460 2 : m.comparer.Equal(m.heap.items[0].boundKey.key, key) {
461 2 : // Call findNextFragmentSet, which will set m.start to the heap root and
462 2 : // proceed forward.
463 2 : return m.findNextFragmentSet()
464 2 : }
465 :
466 2 : m.end = m.heap.items[0].boundKey.key
467 2 : if found, s, err := m.synthesizeKeys(+1); err != nil {
468 0 : return nil, err
469 2 : } else if found && s != nil {
470 2 : return s, nil
471 2 : }
472 2 : return m.findNextFragmentSet()
473 : }
474 :
475 : // SeekLT moves the iterator to the last span covering a key less than the
476 : // given key. This is equivalent to seeking to the last span with a start
477 : // key less than the given key.
478 2 : func (m *MergingIter) SeekLT(key []byte) (*keyspan.Span, error) {
479 2 : // SeekLT(k) seeks to the last span with a start key less than the given
480 2 : // key. The merged span M that we're searching for might straddle the seek
481 2 : // `key`. In this case, the M.End may be a key ≥ the seek key.
482 2 : //
483 2 : // Consider a SeekLT(dog) in the following example.
484 2 : //
485 2 : // i0: b---d e-----h
486 2 : // i1: a---c h-----k
487 2 : // i2: a------------------------------p
488 2 : // merged: a-b-c-d-e-----h-----k----------p
489 2 : //
490 2 : // The merged span M containing the largest key <'dog' is [d,e). The 'e' of
491 2 : // the merged span comes from i0's [e,h)'s start boundary. The [e,h) span
492 2 : // does not cover any key < dog, so we cannot find the span by positioning
493 2 : // the child iterators using a SeekLT(dog).
494 2 : //
495 2 : // Instead, if we take all the child iterators' spans bounds:
496 2 : // a b c d e h k p
497 2 : // We want to partition them into keys < `key` and keys ≥ `key`.
498 2 : // dog
499 2 : // │
500 2 : // a b c d│e h k p
501 2 : // │
502 2 : // The largest key on the left of the partition forms the merged span's
503 2 : // start key, and the smallest key on the right of the partition forms the
504 2 : // merged span's end key. Recharacterized:
505 2 : //
506 2 : // M.Start: the largest boundary < k of any child span
507 2 : // M.End: the smallest boundary ≥ k of any child span
508 2 : //
509 2 : // The FragmentIterator interface doesn't implement seeking by all bounds,
510 2 : // it implements seeking by containment. A SeekGE(k) will ensure we observe
511 2 : // all start boundaries ≥ k and all end boundaries > k but does not ensure
512 2 : // we observe end boundaries = k or any boundaries < k. A SeekLT(k) will
513 2 : // ensure we observe all start boundaries < k and all end boundaries ≤ k but
514 2 : // does not ensure we observe any start boundaries = k or any boundaries >
515 2 : // k. This forces us to seek in one direction and step in the other.
516 2 : //
517 2 : // In a SeekLT, we want to end up oriented in the backward direction when
518 2 : // complete, so we begin with searching for M.End by SeekGE-ing every
519 2 : // child iterator to `k`. For every child span found, we determine the
520 2 : // smallest bound ≥ `k` and use it to initialize our min heap. The resulting
521 2 : // root of the min heap is a preliminary value for `M.End`.
522 2 : for i := range m.levels {
523 2 : l := &m.levels[i]
524 2 : s, err := l.iter.SeekGE(key)
525 2 : switch {
526 1 : case err != nil:
527 1 : return nil, err
528 2 : case s == nil:
529 2 : l.heapKey = boundKey{kind: boundKindInvalid}
530 2 : case m.comparer.Compare(s.Start, key) >= 0:
531 2 : l.heapKey = boundKey{
532 2 : kind: boundKindFragmentStart,
533 2 : key: s.Start,
534 2 : span: s,
535 2 : }
536 2 : default:
537 2 : // s.Start < key
538 2 : // We need to use this span's end bound, since that's the smallest
539 2 : // bound > key.
540 2 : l.heapKey = boundKey{
541 2 : kind: boundKindFragmentEnd,
542 2 : key: s.End,
543 2 : span: s,
544 2 : }
545 : }
546 : }
547 2 : m.initMinHeap()
548 2 : if len(m.heap.items) == 0 {
549 2 : // There are no spans covering any key ≥ `key`. There is no span that
550 2 : // straddles the seek key. Reorient the heap into a max heap and return
551 2 : // the first span we find in the reverse direction.
552 2 : if err := m.switchToMaxHeap(); err != nil {
553 0 : return nil, err
554 0 : }
555 2 : return m.findPrevFragmentSet()
556 : }
557 :
558 : // The heap root is now the smallest boundary key b such that:
559 : // 1. b > k
560 : // 2. b = k, and b is a start boundary
561 : // There's a third case that we will need to consider later, after we've
562 : // switched to a max heap:
563 : // 3. there exists an end boundary key b such that b = k.
564 : // An end boundary key equal to k would not be surfaced when we seeked all
565 : // the levels using SeekGE(k), since k would not be contained within the
566 : // exclusive end boundary.
567 : //
568 : // Assume that the tightest boundary ≥ k is the current heap root (cases 1 &
569 : // 2). After we switch to a max heap, we'll check for the third case and
570 : // adjust the end boundary if necessary.
571 2 : m.end = m.heap.items[0].boundKey.key
572 2 :
573 2 : // Before switching the direction of the heap, save a copy of the end
574 2 : // boundary if it's the start boundary of some child span. Prev-ing the
575 2 : // child iterator might switch files and invalidate the memory of the bound.
576 2 : if m.heap.items[0].boundKey.kind == boundKindFragmentStart {
577 2 : m.buf = append(m.buf[:0], m.end...)
578 2 : m.end = m.buf
579 2 : }
580 :
581 : // Switch to a max heap. This will move each level to the previous bound in
582 : // every level, and then establish a max heap. This allows us to obtain the
583 : // largest boundary key < `key`, which will serve as our candidate start
584 : // bound.
585 2 : if err := m.switchToMaxHeap(); err != nil {
586 1 : return nil, err
587 2 : } else if len(m.heap.items) == 0 {
588 2 : return nil, nil
589 2 : }
590 : // Check for the case 3 described above. It's possible that when we switch
591 : // heap directions, we discover an end boundary of some child span that is
592 : // equal to the seek key `key`. In this case, we want this key to be our end
593 : // boundary.
594 2 : if m.heap.items[0].boundKey.kind == boundKindFragmentEnd &&
595 2 : m.comparer.Equal(m.heap.items[0].boundKey.key, key) {
596 2 : // Call findPrevFragmentSet, which will set m.end to the heap root and
597 2 : // proceed backwards.
598 2 : return m.findPrevFragmentSet()
599 2 : }
600 :
601 2 : m.start = m.heap.items[0].boundKey.key
602 2 : if found, s, err := m.synthesizeKeys(-1); err != nil {
603 0 : return nil, err
604 2 : } else if found && s != nil {
605 2 : return s, nil
606 2 : }
607 2 : return m.findPrevFragmentSet()
608 : }
609 :
610 : // First seeks the iterator to the first span.
611 2 : func (m *MergingIter) First() (*keyspan.Span, error) {
612 2 : for i := range m.levels {
613 2 : s, err := m.levels[i].iter.First()
614 2 : switch {
615 1 : case err != nil:
616 1 : return nil, err
617 2 : case s == nil:
618 2 : m.levels[i].heapKey = boundKey{kind: boundKindInvalid}
619 2 : default:
620 2 : m.levels[i].heapKey = boundKey{
621 2 : kind: boundKindFragmentStart,
622 2 : key: s.Start,
623 2 : span: s,
624 2 : }
625 : }
626 : }
627 2 : m.initMinHeap()
628 2 : return m.findNextFragmentSet()
629 : }
630 :
631 : // Last seeks the iterator to the last span.
632 2 : func (m *MergingIter) Last() (*keyspan.Span, error) {
633 2 : for i := range m.levels {
634 2 : s, err := m.levels[i].iter.Last()
635 2 : switch {
636 1 : case err != nil:
637 1 : return nil, err
638 0 : case s == nil:
639 0 : m.levels[i].heapKey = boundKey{kind: boundKindInvalid}
640 2 : default:
641 2 : m.levels[i].heapKey = boundKey{
642 2 : kind: boundKindFragmentEnd,
643 2 : key: s.End,
644 2 : span: s,
645 2 : }
646 : }
647 : }
648 2 : m.initMaxHeap()
649 2 : return m.findPrevFragmentSet()
650 : }
651 :
652 : // Next advances the iterator to the next span.
653 2 : func (m *MergingIter) Next() (*keyspan.Span, error) {
654 2 : if m.dir == +1 && (m.end == nil || m.start == nil) {
655 0 : return nil, nil
656 0 : }
657 2 : if m.dir != +1 {
658 2 : if err := m.switchToMinHeap(); err != nil {
659 1 : return nil, err
660 1 : }
661 : }
662 2 : return m.findNextFragmentSet()
663 : }
664 :
665 : // Prev advances the iterator to the previous span.
666 2 : func (m *MergingIter) Prev() (*keyspan.Span, error) {
667 2 : if m.dir == -1 && (m.end == nil || m.start == nil) {
668 0 : return nil, nil
669 0 : }
670 2 : if m.dir != -1 {
671 2 : if err := m.switchToMaxHeap(); err != nil {
672 1 : return nil, err
673 1 : }
674 : }
675 2 : return m.findPrevFragmentSet()
676 : }
677 :
678 : // Close closes the iterator, releasing all acquired resources.
679 2 : func (m *MergingIter) Close() error {
680 2 : var err error
681 2 : for i := range m.levels {
682 2 : err = firstError(err, m.levels[i].iter.Close())
683 2 : }
684 2 : m.levels = nil
685 2 : m.heap.items = m.heap.items[:0]
686 2 : return err
687 : }
688 :
689 : // String implements fmt.Stringer.
690 0 : func (m *MergingIter) String() string {
691 0 : return "merging-keyspan"
692 0 : }
693 :
694 2 : func (m *MergingIter) initMinHeap() {
695 2 : m.dir = +1
696 2 : m.heap.reverse = false
697 2 : m.initHeap()
698 2 : }
699 :
700 2 : func (m *MergingIter) initMaxHeap() {
701 2 : m.dir = -1
702 2 : m.heap.reverse = true
703 2 : m.initHeap()
704 2 : }
705 :
706 2 : func (m *MergingIter) initHeap() {
707 2 : m.heap.items = m.heap.items[:0]
708 2 : for i := range m.levels {
709 2 : if l := &m.levels[i]; l.heapKey.kind != boundKindInvalid {
710 2 : m.heap.items = append(m.heap.items, mergingIterItem{
711 2 : index: i,
712 2 : boundKey: &l.heapKey,
713 2 : })
714 2 : }
715 : }
716 2 : m.heap.init()
717 : }
718 :
719 2 : func (m *MergingIter) switchToMinHeap() error {
720 2 : // switchToMinHeap reorients the heap for forward iteration, without moving
721 2 : // the current MergingIter position.
722 2 :
723 2 : // The iterator is currently positioned at the span [m.start, m.end),
724 2 : // oriented in the reverse direction, so each level's iterator is positioned
725 2 : // to the largest key ≤ m.start. To reorient in the forward direction, we
726 2 : // must advance each level's iterator to the smallest key ≥ m.end. Consider
727 2 : // this three-level example.
728 2 : //
729 2 : // i0: b---d e-----h
730 2 : // i1: a---c h-----k
731 2 : // i2: a------------------------------p
732 2 : //
733 2 : // merged: a-b-c-d-e-----h-----k----------p
734 2 : //
735 2 : // If currently positioned at the merged span [c,d), then the level
736 2 : // iterators' heap keys are:
737 2 : //
738 2 : // i0: (b, [b, d)) i1: (c, [a,c)) i2: (a, [a,p))
739 2 : //
740 2 : // Reversing the heap should not move the merging iterator and should not
741 2 : // change the current [m.start, m.end) bounds. It should only prepare for
742 2 : // forward iteration by updating the child iterators' heap keys to:
743 2 : //
744 2 : // i0: (d, [b, d)) i1: (h, [h,k)) i2: (p, [a,p))
745 2 : //
746 2 : // In every level the first key ≥ m.end is the next in the iterator.
747 2 : // Justification: Suppose not and a level iterator's next key was some key k
748 2 : // such that k < m.end. The max-heap invariant dictates that the current
749 2 : // iterator position is the largest entry with a user key ≥ m.start. This
750 2 : // means k > m.start. We started with the assumption that k < m.end, so
751 2 : // m.start < k < m.end. But then k is between our current span bounds,
752 2 : // and reverse iteration would have constructed the current interval to be
753 2 : // [k, m.end) not [m.start, m.end).
754 2 :
755 2 : if invariants.Enabled {
756 2 : for i := range m.levels {
757 2 : l := &m.levels[i]
758 2 : if l.heapKey.kind != boundKindInvalid && m.comparer.Compare(l.heapKey.key, m.start) > 0 {
759 0 : panic("pebble: invariant violation: max-heap key > m.start")
760 : }
761 : }
762 : }
763 :
764 2 : for i := range m.levels {
765 2 : if err := m.levels[i].next(); err != nil {
766 1 : return err
767 1 : }
768 : }
769 2 : m.initMinHeap()
770 2 : return nil
771 : }
772 :
773 2 : func (m *MergingIter) switchToMaxHeap() error {
774 2 : // switchToMaxHeap reorients the heap for reverse iteration, without moving
775 2 : // the current MergingIter position.
776 2 :
777 2 : // The iterator is currently positioned at the span [m.start, m.end),
778 2 : // oriented in the forward direction. Each level's iterator is positioned at
779 2 : // the smallest bound ≥ m.end. To reorient in the reverse direction, we must
780 2 : // move each level's iterator to the largest key ≤ m.start. Consider this
781 2 : // three-level example.
782 2 : //
783 2 : // i0: b---d e-----h
784 2 : // i1: a---c h-----k
785 2 : // i2: a------------------------------p
786 2 : //
787 2 : // merged: a-b-c-d-e-----h-----k----------p
788 2 : //
789 2 : // If currently positioned at the merged span [c,d), then the level
790 2 : // iterators' heap keys are:
791 2 : //
792 2 : // i0: (d, [b, d)) i1: (h, [h,k)) i2: (p, [a,p))
793 2 : //
794 2 : // Reversing the heap should not move the merging iterator and should not
795 2 : // change the current [m.start, m.end) bounds. It should only prepare for
796 2 : // reverse iteration by updating the child iterators' heap keys to:
797 2 : //
798 2 : // i0: (b, [b, d)) i1: (c, [a,c)) i2: (a, [a,p))
799 2 : //
800 2 : // In every level the largest key ≤ m.start is the prev in the iterator.
801 2 : // Justification: Suppose not and a level iterator's prev key was some key k
802 2 : // such that k > m.start. The min-heap invariant dictates that the current
803 2 : // iterator position is the smallest entry with a user key ≥ m.end. This
804 2 : // means k < m.end, otherwise the iterator would be positioned at k. We
805 2 : // started with the assumption that k > m.start, so m.start < k < m.end. But
806 2 : // then k is between our current span bounds, and reverse iteration
807 2 : // would have constructed the current interval to be [m.start, k) not
808 2 : // [m.start, m.end).
809 2 :
810 2 : if invariants.Enabled {
811 2 : for i := range m.levels {
812 2 : l := &m.levels[i]
813 2 : if l.heapKey.kind != boundKindInvalid && m.comparer.Compare(l.heapKey.key, m.end) < 0 {
814 0 : panic("pebble: invariant violation: min-heap key < m.end")
815 : }
816 : }
817 : }
818 :
819 2 : for i := range m.levels {
820 2 : if err := m.levels[i].prev(); err != nil {
821 1 : return err
822 1 : }
823 : }
824 2 : m.initMaxHeap()
825 2 : return nil
826 : }
827 :
828 2 : func (m *MergingIter) findNextFragmentSet() (*keyspan.Span, error) {
829 2 : // Each iteration of this loop considers a new merged span between unique
830 2 : // user keys. An iteration may find that there exists no overlap for a given
831 2 : // span, (eg, if the spans [a,b), [d, e) exist within level iterators, the
832 2 : // below loop will still consider [b,d) before continuing to [d, e)). It
833 2 : // returns when it finds a span that is covered by at least one key.
834 2 :
835 2 : for m.heap.len() > 0 {
836 2 : // Initialize the next span's start bound. SeekGE and First prepare the
837 2 : // heap without advancing. Next leaves the heap in a state such that the
838 2 : // root is the smallest bound key equal to the returned span's end key,
839 2 : // so the heap is already positioned at the next merged span's start key.
840 2 :
841 2 : // NB: m.heapRoot() might be either an end boundary OR a start boundary
842 2 : // of a level's span. Both end and start boundaries may still be a start
843 2 : // key of a span in the set of fragmented spans returned by MergingIter.
844 2 : // Consider the scenario:
845 2 : // a----------l #1
846 2 : // b-----------m #2
847 2 : //
848 2 : // The merged, fully-fragmented spans that MergingIter exposes to the caller
849 2 : // have bounds:
850 2 : // a-b #1
851 2 : // b--------l #1
852 2 : // b--------l #2
853 2 : // l-m #2
854 2 : //
855 2 : // When advancing to l-m#2, we must set m.start to 'l', which originated
856 2 : // from [a,l)#1's end boundary.
857 2 : m.start = m.heap.items[0].boundKey.key
858 2 :
859 2 : // Before calling nextEntry, consider whether it might invalidate our
860 2 : // start boundary. If the start boundary key originated from an end
861 2 : // boundary, then we need to copy the start key before advancing the
862 2 : // underlying iterator to the next Span.
863 2 : if m.heap.items[0].boundKey.kind == boundKindFragmentEnd {
864 2 : m.buf = append(m.buf[:0], m.start...)
865 2 : m.start = m.buf
866 2 : }
867 :
868 : // There may be many entries all with the same user key. Spans in other
869 : // levels may also start or end at this same user key. For eg:
870 : // L1: [a, c) [c, d)
871 : // L2: [c, e)
872 : // If we're positioned at L1's end(c) end boundary, we want to advance
873 : // to the first bound > c.
874 2 : if err := m.nextEntry(); err != nil {
875 1 : return nil, err
876 1 : }
877 2 : for len(m.heap.items) > 0 && m.comparer.Equal(m.heapRoot(), m.start) {
878 2 : if err := m.nextEntry(); err != nil {
879 0 : return nil, err
880 0 : }
881 : }
882 2 : if len(m.heap.items) == 0 {
883 2 : break
884 : }
885 :
886 : // The current entry at the top of the heap is the first key > m.start.
887 : // It must become the end bound for the span we will return to the user.
888 : // In the above example, the root of the heap is L1's end(d).
889 2 : m.end = m.heap.items[0].boundKey.key
890 2 :
891 2 : // Each level within m.levels may have a span that overlaps the
892 2 : // fragmented key span [m.start, m.end). Update m.keys to point to them
893 2 : // and sort them by kind, sequence number. There may not be any keys
894 2 : // defined over [m.start, m.end) if we're between the end of one span
895 2 : // and the start of the next, OR if the configured transform filters any
896 2 : // keys out. We allow empty spans that were emitted by child iterators, but
897 2 : // we elide empty spans created by the mergingIter itself that don't overlap
898 2 : // with any child iterator returned spans (i.e. empty spans that bridge two
899 2 : // distinct child-iterator-defined spans).
900 2 : if found, s, err := m.synthesizeKeys(+1); err != nil {
901 0 : return nil, err
902 2 : } else if found && s != nil {
903 2 : return s, nil
904 2 : }
905 : }
906 : // Exhausted.
907 2 : m.clear()
908 2 : return nil, nil
909 : }
910 :
911 2 : func (m *MergingIter) findPrevFragmentSet() (*keyspan.Span, error) {
912 2 : // Each iteration of this loop considers a new merged span between unique
913 2 : // user keys. An iteration may find that there exists no overlap for a given
914 2 : // span, (eg, if the spans [a,b), [d, e) exist within level iterators, the
915 2 : // below loop will still consider [b,d) before continuing to [a, b)). It
916 2 : // returns when it finds a span that is covered by at least one key.
917 2 :
918 2 : for m.heap.len() > 0 {
919 2 : // Initialize the next span's end bound. SeekLT and Last prepare the
920 2 : // heap without advancing. Prev leaves the heap in a state such that the
921 2 : // root is the largest bound key equal to the returned span's start key,
922 2 : // so the heap is already positioned at the next merged span's end key.
923 2 :
924 2 : // NB: m.heapRoot() might be either an end boundary OR a start boundary
925 2 : // of a level's span. Both end and start boundaries may still be a start
926 2 : // key of a span returned by MergingIter. Consider the scenario:
927 2 : // a----------l #2
928 2 : // b-----------m #1
929 2 : //
930 2 : // The merged, fully-fragmented spans that MergingIter exposes to the caller
931 2 : // have bounds:
932 2 : // a-b #2
933 2 : // b--------l #2
934 2 : // b--------l #1
935 2 : // l-m #1
936 2 : //
937 2 : // When Preving to a-b#2, we must set m.end to 'b', which originated
938 2 : // from [b,m)#1's start boundary.
939 2 : m.end = m.heap.items[0].boundKey.key
940 2 :
941 2 : // Before calling prevEntry, consider whether it might invalidate our
942 2 : // end boundary. If the end boundary key originated from a start
943 2 : // boundary, then we need to copy the end key before advancing the
944 2 : // underlying iterator to the previous Span.
945 2 : if m.heap.items[0].boundKey.kind == boundKindFragmentStart {
946 2 : m.buf = append(m.buf[:0], m.end...)
947 2 : m.end = m.buf
948 2 : }
949 :
950 : // There may be many entries all with the same user key. Spans in other
951 : // levels may also start or end at this same user key. For eg:
952 : // L1: [a, c) [c, d)
953 : // L2: [c, e)
954 : // If we're positioned at L1's start(c) start boundary, we want to prev
955 : // to move to the first bound < c.
956 2 : if err := m.prevEntry(); err != nil {
957 1 : return nil, err
958 1 : }
959 2 : for len(m.heap.items) > 0 && m.comparer.Equal(m.heapRoot(), m.end) {
960 2 : if err := m.prevEntry(); err != nil {
961 0 : return nil, err
962 0 : }
963 : }
964 2 : if len(m.heap.items) == 0 {
965 2 : break
966 : }
967 :
968 : // The current entry at the top of the heap is the first key < m.end.
969 : // It must become the start bound for the span we will return to the
970 : // user. In the above example, the root of the heap is L1's start(a).
971 2 : m.start = m.heap.items[0].boundKey.key
972 2 :
973 2 : // Each level within m.levels may have a set of keys that overlap the
974 2 : // fragmented key span [m.start, m.end). Update m.keys to point to them
975 2 : // and sort them by kind, sequence number. There may not be any keys
976 2 : // spanning [m.start, m.end) if we're between the end of one span and
977 2 : // the start of the next, OR if the configured transform filters any
978 2 : // keys out. We allow empty spans that were emitted by child iterators, but
979 2 : // we elide empty spans created by the mergingIter itself that don't overlap
980 2 : // with any child iterator returned spans (i.e. empty spans that bridge two
981 2 : // distinct child-iterator-defined spans).
982 2 : if found, s, err := m.synthesizeKeys(-1); err != nil {
983 0 : return nil, err
984 2 : } else if found && s != nil {
985 2 : return s, nil
986 2 : }
987 : }
988 : // Exhausted.
989 2 : m.clear()
990 2 : return nil, nil
991 : }
992 :
993 2 : func (m *MergingIter) heapRoot() []byte {
994 2 : return m.heap.items[0].boundKey.key
995 2 : }
996 :
997 : // synthesizeKeys is called by find{Next,Prev}FragmentSet to populate and
998 : // sort the set of keys overlapping [m.start, m.end).
999 : //
1000 : // During forward iteration, if the current heap item is a fragment end,
1001 : // then the fragment's start must be ≤ m.start and the fragment overlaps the
1002 : // current iterator position of [m.start, m.end).
1003 : //
1004 : // During reverse iteration, if the current heap item is a fragment start,
1005 : // then the fragment's end must be ≥ m.end and the fragment overlaps the
1006 : // current iteration position of [m.start, m.end).
1007 : //
1008 : // The boolean return value, `found`, is true if the returned span overlaps
1009 : // with a span returned by a child iterator.
1010 2 : func (m *MergingIter) synthesizeKeys(dir int8) (bool, *keyspan.Span, error) {
1011 2 : if invariants.Enabled {
1012 2 : if m.comparer.Compare(m.start, m.end) >= 0 {
1013 0 : panic(fmt.Sprintf("pebble: invariant violation: span start ≥ end: %s >= %s", m.start, m.end))
1014 : }
1015 : }
1016 :
1017 2 : m.keys = m.keys[:0]
1018 2 : found := false
1019 2 : for i := range m.levels {
1020 2 : if dir == +1 && m.levels[i].heapKey.kind == boundKindFragmentEnd ||
1021 2 : dir == -1 && m.levels[i].heapKey.kind == boundKindFragmentStart {
1022 2 : m.keys = append(m.keys, m.levels[i].heapKey.span.Keys...)
1023 2 : found = true
1024 2 : }
1025 : }
1026 : // Sort the keys by sequence number in descending order.
1027 : //
1028 : // TODO(jackson): We should be able to remove this sort and instead
1029 : // guarantee that we'll return keys in the order of the levels they're from.
1030 : // With careful iterator construction, this would guarantee that they're
1031 : // sorted by trailer descending for the range key iteration use case.
1032 2 : slices.SortFunc(m.keys, func(a, b keyspan.Key) int {
1033 2 : return cmp.Compare(b.Trailer, a.Trailer)
1034 2 : })
1035 :
1036 : // Apply the configured transform. See VisibleTransform.
1037 2 : m.span = keyspan.Span{
1038 2 : Start: m.start,
1039 2 : End: m.end,
1040 2 : Keys: m.keys,
1041 2 : KeysOrder: keyspan.ByTrailerDesc,
1042 2 : }
1043 2 : if err := m.transformer.Transform(m.comparer.Compare, m.span, &m.span); err != nil {
1044 0 : return false, nil, err
1045 0 : }
1046 2 : return found, &m.span, nil
1047 : }
1048 :
1049 2 : func (m *MergingIter) clear() {
1050 2 : for fi := range m.keys {
1051 2 : m.keys[fi] = keyspan.Key{}
1052 2 : }
1053 2 : m.keys = m.keys[:0]
1054 : }
1055 :
1056 : // nextEntry steps to the next entry.
1057 2 : func (m *MergingIter) nextEntry() error {
1058 2 : l := &m.levels[m.heap.items[0].index]
1059 2 : if err := l.next(); err != nil {
1060 1 : return err
1061 1 : }
1062 2 : if !l.heapKey.valid() {
1063 2 : // l.iter is exhausted.
1064 2 : m.heap.pop()
1065 2 : return nil
1066 2 : }
1067 :
1068 2 : if m.heap.len() > 1 {
1069 2 : m.heap.fix(0)
1070 2 : }
1071 2 : return nil
1072 : }
1073 :
1074 : // prevEntry steps to the previous entry.
1075 2 : func (m *MergingIter) prevEntry() error {
1076 2 : l := &m.levels[m.heap.items[0].index]
1077 2 : if err := l.prev(); err != nil {
1078 1 : return err
1079 1 : }
1080 2 : if !l.heapKey.valid() {
1081 2 : // l.iter is exhausted.
1082 2 : m.heap.pop()
1083 2 : return nil
1084 2 : }
1085 :
1086 2 : if m.heap.len() > 1 {
1087 2 : m.heap.fix(0)
1088 2 : }
1089 2 : return nil
1090 : }
1091 :
1092 : // DebugString returns a string representing the current internal state of the
1093 : // merging iterator and its heap for debugging purposes.
1094 0 : func (m *MergingIter) DebugString() string {
1095 0 : var buf bytes.Buffer
1096 0 : fmt.Fprintf(&buf, "Current bounds: [%q, %q)\n", m.start, m.end)
1097 0 : for i := range m.levels {
1098 0 : fmt.Fprintf(&buf, "%d: heap key %s\n", i, m.levels[i].heapKey)
1099 0 : }
1100 0 : return buf.String()
1101 : }
1102 :
1103 : // WrapChildren implements FragmentIterator.
1104 0 : func (m *MergingIter) WrapChildren(wrap keyspan.WrapFn) {
1105 0 : for i := range m.levels {
1106 0 : m.levels[i].iter = wrap(m.levels[i].iter)
1107 0 : }
1108 0 : m.wrapFn = wrap
1109 : }
1110 :
1111 : type mergingIterItem struct {
1112 : // boundKey points to the corresponding mergingIterLevel's `iterKey`.
1113 : *boundKey
1114 : // index is the index of this level within the MergingIter's levels field.
1115 : index int
1116 : }
1117 :
1118 : // mergingIterHeap is copied from mergingIterHeap defined in the root pebble
1119 : // package for use with point keys.
1120 :
1121 : type mergingIterHeap struct {
1122 : cmp base.Compare
1123 : reverse bool
1124 : items []mergingIterItem
1125 : }
1126 :
1127 2 : func (h *mergingIterHeap) len() int {
1128 2 : return len(h.items)
1129 2 : }
1130 :
1131 2 : func (h *mergingIterHeap) less(i, j int) bool {
1132 2 : // This key comparison only uses the user key and not the boundKind. Bound
1133 2 : // kind doesn't matter because when stepping over a user key,
1134 2 : // findNextFragmentSet and findPrevFragmentSet skip past all heap items with
1135 2 : // that user key, and makes no assumptions on ordering. All other heap
1136 2 : // examinations only consider the user key.
1137 2 : ik, jk := h.items[i].key, h.items[j].key
1138 2 : c := h.cmp(ik, jk)
1139 2 : if h.reverse {
1140 2 : return c > 0
1141 2 : }
1142 2 : return c < 0
1143 : }
1144 :
1145 2 : func (h *mergingIterHeap) swap(i, j int) {
1146 2 : h.items[i], h.items[j] = h.items[j], h.items[i]
1147 2 : }
1148 :
1149 : // init, fix, up and down are copied from the go stdlib.
1150 2 : func (h *mergingIterHeap) init() {
1151 2 : // heapify
1152 2 : n := h.len()
1153 2 : for i := n/2 - 1; i >= 0; i-- {
1154 2 : h.down(i, n)
1155 2 : }
1156 : }
1157 :
1158 2 : func (h *mergingIterHeap) fix(i int) {
1159 2 : if !h.down(i, h.len()) {
1160 2 : h.up(i)
1161 2 : }
1162 : }
1163 :
1164 2 : func (h *mergingIterHeap) pop() *mergingIterItem {
1165 2 : n := h.len() - 1
1166 2 : h.swap(0, n)
1167 2 : h.down(0, n)
1168 2 : item := &h.items[n]
1169 2 : h.items = h.items[:n]
1170 2 : return item
1171 2 : }
1172 :
1173 2 : func (h *mergingIterHeap) up(j int) {
1174 2 : for {
1175 2 : i := (j - 1) / 2 // parent
1176 2 : if i == j || !h.less(j, i) {
1177 2 : break
1178 : }
1179 0 : h.swap(i, j)
1180 0 : j = i
1181 : }
1182 : }
1183 :
1184 2 : func (h *mergingIterHeap) down(i0, n int) bool {
1185 2 : i := i0
1186 2 : for {
1187 2 : j1 := 2*i + 1
1188 2 : if j1 >= n || j1 < 0 { // j1 < 0 after int overflow
1189 2 : break
1190 : }
1191 2 : j := j1 // left child
1192 2 : if j2 := j1 + 1; j2 < n && h.less(j2, j1) {
1193 2 : j = j2 // = 2*i + 2 // right child
1194 2 : }
1195 2 : if !h.less(j, i) {
1196 2 : break
1197 : }
1198 2 : h.swap(i, j)
1199 2 : i = j
1200 : }
1201 2 : return i > i0
1202 : }
1203 :
1204 : type boundKind int8
1205 :
1206 : const (
1207 : boundKindInvalid boundKind = iota
1208 : boundKindFragmentStart
1209 : boundKindFragmentEnd
1210 : )
1211 :
1212 : type boundKey struct {
1213 : kind boundKind
1214 : key []byte
1215 : // span holds the span the bound key comes from.
1216 : //
1217 : // If kind is boundKindFragmentStart, then key is span.Start. If kind is
1218 : // boundKindFragmentEnd, then key is span.End.
1219 : span *keyspan.Span
1220 : }
1221 :
1222 2 : func (k boundKey) valid() bool {
1223 2 : return k.kind != boundKindInvalid
1224 2 : }
1225 :
1226 0 : func (k boundKey) String() string {
1227 0 : var buf bytes.Buffer
1228 0 : switch k.kind {
1229 0 : case boundKindInvalid:
1230 0 : fmt.Fprint(&buf, "invalid")
1231 0 : case boundKindFragmentStart:
1232 0 : fmt.Fprint(&buf, "fragment-start")
1233 0 : case boundKindFragmentEnd:
1234 0 : fmt.Fprint(&buf, "fragment-end ")
1235 0 : default:
1236 0 : fmt.Fprintf(&buf, "unknown-kind(%d)", k.kind)
1237 : }
1238 0 : fmt.Fprintf(&buf, " %s [", k.key)
1239 0 : fmt.Fprintf(&buf, "%s", k.span)
1240 0 : fmt.Fprint(&buf, "]")
1241 0 : return buf.String()
1242 : }
1243 :
1244 2 : func firstError(e1, e2 error) error {
1245 2 : if e1 == nil {
1246 2 : return e2
1247 2 : }
1248 1 : return e1
1249 : }
|
