Line data Source code
1 : // Copyright 2020 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 manifest
6 :
7 : import (
8 : "bytes"
9 : "fmt"
10 :
11 : "github.com/cockroachdb/pebble/internal/base"
12 : "github.com/cockroachdb/pebble/internal/invariants"
13 : )
14 :
15 : // LevelMetadata contains metadata for all of the files within
16 : // a level of the LSM.
17 : type LevelMetadata struct {
18 : level int
19 : totalSize uint64
20 : // NumVirtual is the number of virtual sstables in the level.
21 : NumVirtual uint64
22 : // VirtualSize is the size of the virtual sstables in the level.
23 : VirtualSize uint64
24 : tree btree
25 : }
26 :
27 : // clone makes a copy of the level metadata, implicitly increasing the ref
28 : // count of every file contained within lm.
29 2 : func (lm *LevelMetadata) clone() LevelMetadata {
30 2 : return LevelMetadata{
31 2 : level: lm.level,
32 2 : totalSize: lm.totalSize,
33 2 : NumVirtual: lm.NumVirtual,
34 2 : VirtualSize: lm.VirtualSize,
35 2 : tree: lm.tree.Clone(),
36 2 : }
37 2 : }
38 :
39 2 : func (lm *LevelMetadata) release() (obsolete []*FileBacking) {
40 2 : return lm.tree.Release()
41 2 : }
42 :
43 2 : func makeLevelMetadata(cmp Compare, level int, files []*FileMetadata) LevelMetadata {
44 2 : bcmp := btreeCmpSeqNum
45 2 : if level > 0 {
46 2 : bcmp = btreeCmpSmallestKey(cmp)
47 2 : }
48 2 : var lm LevelMetadata
49 2 : lm.level = level
50 2 : lm.tree, _ = makeBTree(bcmp, files)
51 2 : for _, f := range files {
52 0 : lm.totalSize += f.Size
53 0 : if f.Virtual {
54 0 : lm.NumVirtual++
55 0 : lm.VirtualSize += f.Size
56 0 : }
57 : }
58 2 : return lm
59 : }
60 :
61 2 : func makeBTree(cmp btreeCmp, files []*FileMetadata) (btree, LevelSlice) {
62 2 : var t btree
63 2 : t.cmp = cmp
64 2 : for _, f := range files {
65 2 : t.Insert(f)
66 2 : }
67 2 : return t, newLevelSlice(t.Iter())
68 : }
69 :
70 2 : func (lm *LevelMetadata) insert(f *FileMetadata) error {
71 2 : if err := lm.tree.Insert(f); err != nil {
72 1 : return err
73 1 : }
74 2 : lm.totalSize += f.Size
75 2 : if f.Virtual {
76 2 : lm.NumVirtual++
77 2 : lm.VirtualSize += f.Size
78 2 : }
79 2 : return nil
80 : }
81 :
82 2 : func (lm *LevelMetadata) remove(f *FileMetadata) bool {
83 2 : lm.totalSize -= f.Size
84 2 : if f.Virtual {
85 2 : lm.NumVirtual--
86 2 : lm.VirtualSize -= f.Size
87 2 : }
88 2 : return lm.tree.Delete(f)
89 : }
90 :
91 : // Empty indicates whether there are any files in the level.
92 2 : func (lm *LevelMetadata) Empty() bool {
93 2 : return lm.tree.Count() == 0
94 2 : }
95 :
96 : // Len returns the number of files within the level.
97 2 : func (lm *LevelMetadata) Len() int {
98 2 : return lm.tree.Count()
99 2 : }
100 :
101 : // Size returns the cumulative size of all the files within the level.
102 2 : func (lm *LevelMetadata) Size() uint64 {
103 2 : return lm.totalSize
104 2 : }
105 :
106 : // Iter constructs a LevelIterator over the entire level.
107 2 : func (lm *LevelMetadata) Iter() LevelIterator {
108 2 : return LevelIterator{iter: lm.tree.Iter()}
109 2 : }
110 :
111 : // Slice constructs a slice containing the entire level.
112 2 : func (lm *LevelMetadata) Slice() LevelSlice {
113 2 : return newLevelSlice(lm.tree.Iter())
114 2 : }
115 :
116 : // Find finds the provided file in the level if it exists.
117 2 : func (lm *LevelMetadata) Find(cmp base.Compare, m *FileMetadata) *LevelFile {
118 2 : iter := lm.Iter()
119 2 : if lm.level != 0 {
120 2 : // If lm holds files for levels >0, we can narrow our search by binary
121 2 : // searching by bounds.
122 2 : o := overlaps(iter, cmp, m.Smallest.UserKey,
123 2 : m.Largest.UserKey, m.Largest.IsExclusiveSentinel())
124 2 : iter = o.Iter()
125 2 : }
126 2 : for f := iter.First(); f != nil; f = iter.Next() {
127 2 : if f == m {
128 2 : lf := iter.Take()
129 2 : return &lf
130 2 : }
131 : }
132 0 : return nil
133 : }
134 :
135 : // Annotation lazily calculates and returns the annotation defined by
136 : // Annotator. The Annotator is used as the key for pre-calculated
137 : // values, so equal Annotators must be used to avoid duplicate computations
138 : // and cached annotations. Annotation must not be called concurrently, and in
139 : // practice this is achieved by requiring callers to hold DB.mu.
140 2 : func (lm *LevelMetadata) Annotation(annotator Annotator) interface{} {
141 2 : if lm.Empty() {
142 2 : return annotator.Zero(nil)
143 2 : }
144 2 : v, _ := lm.tree.root.Annotation(annotator)
145 2 : return v
146 : }
147 :
148 : // InvalidateAnnotation clears any cached annotations defined by Annotator. The
149 : // Annotator is used as the key for pre-calculated values, so equal Annotators
150 : // must be used to clear the appropriate cached annotation. InvalidateAnnotation
151 : // must not be called concurrently, and in practice this is achieved by
152 : // requiring callers to hold DB.mu.
153 1 : func (lm *LevelMetadata) InvalidateAnnotation(annotator Annotator) {
154 1 : if lm.Empty() {
155 0 : return
156 0 : }
157 1 : lm.tree.root.InvalidateAnnotation(annotator)
158 : }
159 :
160 : // LevelFile holds a file's metadata along with its position
161 : // within a level of the LSM.
162 : type LevelFile struct {
163 : *FileMetadata
164 : slice LevelSlice
165 : }
166 :
167 : // Slice constructs a LevelSlice containing only this file.
168 2 : func (lf LevelFile) Slice() LevelSlice {
169 2 : return lf.slice
170 2 : }
171 :
172 : // NewLevelSliceSeqSorted constructs a LevelSlice over the provided files,
173 : // sorted by the L0 sequence number sort order.
174 : // TODO(jackson): Can we improve this interface or avoid needing to export
175 : // a slice constructor like this?
176 2 : func NewLevelSliceSeqSorted(files []*FileMetadata) LevelSlice {
177 2 : tr, slice := makeBTree(btreeCmpSeqNum, files)
178 2 : tr.Release()
179 2 : slice.verifyInvariants()
180 2 : return slice
181 2 : }
182 :
183 : // NewLevelSliceKeySorted constructs a LevelSlice over the provided files,
184 : // sorted by the files smallest keys.
185 : // TODO(jackson): Can we improve this interface or avoid needing to export
186 : // a slice constructor like this?
187 2 : func NewLevelSliceKeySorted(cmp base.Compare, files []*FileMetadata) LevelSlice {
188 2 : tr, slice := makeBTree(btreeCmpSmallestKey(cmp), files)
189 2 : tr.Release()
190 2 : slice.verifyInvariants()
191 2 : return slice
192 2 : }
193 :
194 : // NewLevelSliceSpecificOrder constructs a LevelSlice over the provided files,
195 : // ordering the files by their order in the provided slice. It's used in
196 : // tests.
197 : // TODO(jackson): Update tests to avoid requiring this and remove it.
198 1 : func NewLevelSliceSpecificOrder(files []*FileMetadata) LevelSlice {
199 1 : tr, slice := makeBTree(btreeCmpSpecificOrder(files), files)
200 1 : tr.Release()
201 1 : slice.verifyInvariants()
202 1 : return slice
203 1 : }
204 :
205 : // newLevelSlice constructs a new LevelSlice backed by iter.
206 2 : func newLevelSlice(iter iterator) LevelSlice {
207 2 : s := LevelSlice{iter: iter}
208 2 : if iter.r != nil {
209 2 : s.length = iter.r.subtreeCount
210 2 : }
211 2 : s.verifyInvariants()
212 2 : return s
213 : }
214 :
215 : // newBoundedLevelSlice constructs a new LevelSlice backed by iter and bounded
216 : // by the provided start and end bounds. The provided startBound and endBound
217 : // iterators must be iterators over the same B-Tree. Both start and end bounds
218 : // are inclusive.
219 2 : func newBoundedLevelSlice(iter iterator, startBound, endBound *iterator) LevelSlice {
220 2 : s := LevelSlice{
221 2 : iter: iter,
222 2 : start: startBound,
223 2 : end: endBound,
224 2 : }
225 2 : if iter.valid() {
226 2 : s.length = endBound.countLeft() - startBound.countLeft()
227 2 : // NB: The +1 is a consequence of the end bound being inclusive.
228 2 : if endBound.valid() {
229 2 : s.length++
230 2 : }
231 : // NB: A slice that's empty due to its bounds may have an endBound
232 : // positioned before the startBound due to the inclusive bounds.
233 : // TODO(jackson): Consider refactoring the end boundary to be exclusive;
234 : // it would simplify some areas (eg, here) and complicate others (eg,
235 : // Reslice-ing to grow compactions).
236 2 : if s.length < 0 {
237 2 : s.length = 0
238 2 : }
239 : }
240 2 : s.verifyInvariants()
241 2 : return s
242 : }
243 :
244 : // LevelSlice contains a slice of the files within a level of the LSM.
245 : // A LevelSlice is immutable once created, but may be used to construct a
246 : // mutable LevelIterator over the slice's files.
247 : //
248 : // LevelSlices should be constructed through one of the existing constructors,
249 : // not manually initialized.
250 : type LevelSlice struct {
251 : iter iterator
252 : length int
253 : // start and end form the inclusive bounds of a slice of files within a
254 : // level of the LSM. They may be nil if the entire B-Tree backing iter is
255 : // accessible.
256 : start *iterator
257 : end *iterator
258 : }
259 :
260 2 : func (ls LevelSlice) verifyInvariants() {
261 2 : if invariants.Enabled {
262 2 : i := ls.Iter()
263 2 : var length int
264 2 : for f := i.First(); f != nil; f = i.Next() {
265 2 : length++
266 2 : }
267 2 : if ls.length != length {
268 0 : panic(fmt.Sprintf("LevelSlice %s has length %d value; actual length is %d", ls, ls.length, length))
269 : }
270 : }
271 : }
272 :
273 : // Each invokes fn for each element in the slice.
274 2 : func (ls LevelSlice) Each(fn func(*FileMetadata)) {
275 2 : iter := ls.Iter()
276 2 : for f := iter.First(); f != nil; f = iter.Next() {
277 2 : fn(f)
278 2 : }
279 : }
280 :
281 : // String implements fmt.Stringer.
282 1 : func (ls LevelSlice) String() string {
283 1 : var buf bytes.Buffer
284 1 : fmt.Fprintf(&buf, "%d files: ", ls.length)
285 1 : ls.Each(func(f *FileMetadata) {
286 1 : if buf.Len() > 0 {
287 1 : fmt.Fprintf(&buf, " ")
288 1 : }
289 1 : fmt.Fprint(&buf, f)
290 : })
291 1 : return buf.String()
292 : }
293 :
294 : // Empty indicates whether the slice contains any files.
295 2 : func (ls *LevelSlice) Empty() bool {
296 2 : return emptyWithBounds(ls.iter, ls.start, ls.end)
297 2 : }
298 :
299 : // Iter constructs a LevelIterator that iterates over the slice.
300 2 : func (ls *LevelSlice) Iter() LevelIterator {
301 2 : return LevelIterator{
302 2 : start: ls.start,
303 2 : end: ls.end,
304 2 : iter: ls.iter.clone(),
305 2 : }
306 2 : }
307 :
308 : // Len returns the number of files in the slice. Its runtime is constant.
309 2 : func (ls *LevelSlice) Len() int {
310 2 : return ls.length
311 2 : }
312 :
313 : // SizeSum sums the size of all files in the slice. Its runtime is linear in
314 : // the length of the slice.
315 2 : func (ls *LevelSlice) SizeSum() uint64 {
316 2 : var sum uint64
317 2 : iter := ls.Iter()
318 2 : for f := iter.First(); f != nil; f = iter.Next() {
319 2 : sum += f.Size
320 2 : }
321 2 : return sum
322 : }
323 :
324 : // NumVirtual returns the number of virtual sstables in the level. Its runtime is
325 : // linear in the length of the slice.
326 2 : func (ls *LevelSlice) NumVirtual() uint64 {
327 2 : var n uint64
328 2 : iter := ls.Iter()
329 2 : for f := iter.First(); f != nil; f = iter.Next() {
330 2 : if f.Virtual {
331 2 : n++
332 2 : }
333 : }
334 2 : return n
335 : }
336 :
337 : // VirtualSizeSum returns the sum of the sizes of the virtual sstables in the
338 : // level.
339 2 : func (ls *LevelSlice) VirtualSizeSum() uint64 {
340 2 : var sum uint64
341 2 : iter := ls.Iter()
342 2 : for f := iter.First(); f != nil; f = iter.Next() {
343 2 : if f.Virtual {
344 2 : sum += f.Size
345 2 : }
346 : }
347 2 : return sum
348 : }
349 :
350 : // Reslice constructs a new slice backed by the same underlying level, with
351 : // new start and end positions. Reslice invokes the provided function, passing
352 : // two LevelIterators: one positioned to i's inclusive start and one
353 : // positioned to i's inclusive end. The resliceFunc may move either iterator
354 : // forward or backwards, including beyond the callee's original bounds to
355 : // capture additional files from the underlying level. Reslice constructs and
356 : // returns a new LevelSlice with the final bounds of the iterators after
357 : // calling resliceFunc.
358 2 : func (ls LevelSlice) Reslice(resliceFunc func(start, end *LevelIterator)) LevelSlice {
359 2 : if ls.iter.r == nil {
360 2 : return ls
361 2 : }
362 2 : var start, end LevelIterator
363 2 : if ls.start == nil {
364 2 : start.iter = ls.iter.clone()
365 2 : start.iter.first()
366 2 : } else {
367 2 : start.iter = ls.start.clone()
368 2 : }
369 2 : if ls.end == nil {
370 2 : end.iter = ls.iter.clone()
371 2 : end.iter.last()
372 2 : } else {
373 2 : end.iter = ls.end.clone()
374 2 : }
375 2 : resliceFunc(&start, &end)
376 2 : return newBoundedLevelSlice(start.iter.clone(), &start.iter, &end.iter)
377 : }
378 :
379 : // KeyType is used to specify the type of keys we're looking for in
380 : // LevelIterator positioning operations. Files not containing any keys of the
381 : // desired type are skipped.
382 : type KeyType int8
383 :
384 : const (
385 : // KeyTypePointAndRange denotes a search among the entire keyspace, including
386 : // both point keys and range keys. No sstables are skipped.
387 : KeyTypePointAndRange KeyType = iota
388 : // KeyTypePoint denotes a search among the point keyspace. SSTables with no
389 : // point keys will be skipped. Note that the point keyspace includes rangedels.
390 : KeyTypePoint
391 : // KeyTypeRange denotes a search among the range keyspace. SSTables with no
392 : // range keys will be skipped.
393 : KeyTypeRange
394 : )
395 :
396 : type keyTypeAnnotator struct{}
397 :
398 : var _ Annotator = keyTypeAnnotator{}
399 :
400 0 : func (k keyTypeAnnotator) Zero(dst interface{}) interface{} {
401 0 : var val *KeyType
402 0 : if dst != nil {
403 0 : val = dst.(*KeyType)
404 0 : } else {
405 0 : val = new(KeyType)
406 0 : }
407 0 : *val = KeyTypePoint
408 0 : return val
409 : }
410 :
411 0 : func (k keyTypeAnnotator) Accumulate(m *FileMetadata, dst interface{}) (interface{}, bool) {
412 0 : v := dst.(*KeyType)
413 0 : switch *v {
414 0 : case KeyTypePoint:
415 0 : if m.HasRangeKeys {
416 0 : *v = KeyTypePointAndRange
417 0 : }
418 0 : case KeyTypePointAndRange:
419 : // Do nothing.
420 0 : default:
421 0 : panic("unexpected key type")
422 : }
423 0 : return v, true
424 : }
425 :
426 0 : func (k keyTypeAnnotator) Merge(src interface{}, dst interface{}) interface{} {
427 0 : v := dst.(*KeyType)
428 0 : srcVal := src.(*KeyType)
429 0 : switch *v {
430 0 : case KeyTypePoint:
431 0 : if *srcVal == KeyTypePointAndRange {
432 0 : *v = KeyTypePointAndRange
433 0 : }
434 0 : case KeyTypePointAndRange:
435 : // Do nothing.
436 0 : default:
437 0 : panic("unexpected key type")
438 : }
439 0 : return v
440 : }
441 :
442 : // LevelIterator iterates over a set of files' metadata. Its zero value is an
443 : // empty iterator.
444 : type LevelIterator struct {
445 : iter iterator
446 : start *iterator
447 : end *iterator
448 : filter KeyType
449 : }
450 :
451 0 : func (i LevelIterator) String() string {
452 0 : var buf bytes.Buffer
453 0 : iter := i.iter.clone()
454 0 : iter.first()
455 0 : iter.prev()
456 0 : if i.iter.pos == -1 {
457 0 : fmt.Fprint(&buf, "(<start>)*")
458 0 : }
459 0 : iter.next()
460 0 : for ; iter.valid(); iter.next() {
461 0 : if buf.Len() > 0 {
462 0 : fmt.Fprint(&buf, " ")
463 0 : }
464 :
465 0 : if i.start != nil && cmpIter(iter, *i.start) == 0 {
466 0 : fmt.Fprintf(&buf, " [ ")
467 0 : }
468 0 : isCurrentPos := cmpIter(iter, i.iter) == 0
469 0 : if isCurrentPos {
470 0 : fmt.Fprint(&buf, " ( ")
471 0 : }
472 0 : fmt.Fprint(&buf, iter.cur().String())
473 0 : if isCurrentPos {
474 0 : fmt.Fprint(&buf, " )*")
475 0 : }
476 0 : if i.end != nil && cmpIter(iter, *i.end) == 0 {
477 0 : fmt.Fprintf(&buf, " ]")
478 0 : }
479 : }
480 0 : if i.iter.n != nil && i.iter.pos >= i.iter.n.count {
481 0 : if buf.Len() > 0 {
482 0 : fmt.Fprint(&buf, " ")
483 0 : }
484 0 : fmt.Fprint(&buf, "(<end>)*")
485 : }
486 0 : return buf.String()
487 : }
488 :
489 : // Clone copies the iterator, returning an independent iterator at the same
490 : // position.
491 2 : func (i *LevelIterator) Clone() LevelIterator {
492 2 : if i.iter.r == nil {
493 2 : return *i
494 2 : }
495 : // The start and end iterators are not cloned and are treated as
496 : // immutable.
497 2 : return LevelIterator{
498 2 : iter: i.iter.clone(),
499 2 : start: i.start,
500 2 : end: i.end,
501 2 : filter: i.filter,
502 2 : }
503 : }
504 :
505 : // Current returns the item at the current iterator position.
506 : //
507 : // Current is deprecated. Callers should instead use the return value of a
508 : // positioning operation.
509 2 : func (i *LevelIterator) Current() *FileMetadata {
510 2 : if !i.iter.valid() ||
511 2 : (i.end != nil && cmpIter(i.iter, *i.end) > 0) ||
512 2 : (i.start != nil && cmpIter(i.iter, *i.start) < 0) {
513 2 : return nil
514 2 : }
515 2 : return i.iter.cur()
516 : }
517 :
518 2 : func (i *LevelIterator) empty() bool {
519 2 : return emptyWithBounds(i.iter, i.start, i.end)
520 2 : }
521 :
522 : // Filter clones the iterator and sets the desired KeyType as the key to filter
523 : // files on.
524 2 : func (i *LevelIterator) Filter(keyType KeyType) LevelIterator {
525 2 : l := i.Clone()
526 2 : l.filter = keyType
527 2 : return l
528 2 : }
529 :
530 2 : func emptyWithBounds(i iterator, start, end *iterator) bool {
531 2 : // If i.r is nil, the iterator was constructed from an empty btree.
532 2 : // If the end bound is before the start bound, the bounds represent an
533 2 : // empty slice of the B-Tree.
534 2 : return i.r == nil || (start != nil && end != nil && cmpIter(*end, *start) < 0)
535 2 : }
536 :
537 : // First seeks to the first file in the iterator and returns it.
538 2 : func (i *LevelIterator) First() *FileMetadata {
539 2 : if i.empty() {
540 2 : return nil
541 2 : }
542 2 : if i.start != nil {
543 2 : i.iter = i.start.clone()
544 2 : } else {
545 2 : i.iter.first()
546 2 : }
547 2 : if !i.iter.valid() {
548 2 : return nil
549 2 : }
550 2 : return i.skipFilteredForward(i.iter.cur())
551 : }
552 :
553 : // Last seeks to the last file in the iterator and returns it.
554 2 : func (i *LevelIterator) Last() *FileMetadata {
555 2 : if i.empty() {
556 2 : return nil
557 2 : }
558 2 : if i.end != nil {
559 2 : i.iter = i.end.clone()
560 2 : } else {
561 2 : i.iter.last()
562 2 : }
563 2 : if !i.iter.valid() {
564 0 : return nil
565 0 : }
566 2 : return i.skipFilteredBackward(i.iter.cur())
567 : }
568 :
569 : // Next advances the iterator to the next file and returns it.
570 2 : func (i *LevelIterator) Next() *FileMetadata {
571 2 : if i.iter.r == nil {
572 0 : return nil
573 0 : }
574 2 : if invariants.Enabled && (i.iter.pos >= i.iter.n.count || (i.end != nil && cmpIter(i.iter, *i.end) > 0)) {
575 0 : panic("pebble: cannot next forward-exhausted iterator")
576 : }
577 2 : i.iter.next()
578 2 : if !i.iter.valid() {
579 2 : return nil
580 2 : }
581 2 : return i.skipFilteredForward(i.iter.cur())
582 : }
583 :
584 : // Prev moves the iterator the previous file and returns it.
585 2 : func (i *LevelIterator) Prev() *FileMetadata {
586 2 : if i.iter.r == nil {
587 2 : return nil
588 2 : }
589 2 : if invariants.Enabled && (i.iter.pos < 0 || (i.start != nil && cmpIter(i.iter, *i.start) < 0)) {
590 0 : panic("pebble: cannot prev backward-exhausted iterator")
591 : }
592 2 : i.iter.prev()
593 2 : if !i.iter.valid() {
594 2 : return nil
595 2 : }
596 2 : return i.skipFilteredBackward(i.iter.cur())
597 : }
598 :
599 : // SeekGE seeks to the first file in the iterator's file set with a largest
600 : // user key greater than or equal to the provided user key. The iterator must
601 : // have been constructed from L1+, because it requires the underlying files to
602 : // be sorted by user keys and non-overlapping.
603 2 : func (i *LevelIterator) SeekGE(cmp Compare, userKey []byte) *FileMetadata {
604 2 : // TODO(jackson): Assert that i.iter.cmp == btreeCmpSmallestKey.
605 2 : if i.iter.r == nil {
606 2 : return nil
607 2 : }
608 2 : m := i.seek(func(m *FileMetadata) bool {
609 2 : return cmp(m.Largest.UserKey, userKey) >= 0
610 2 : })
611 2 : if i.filter != KeyTypePointAndRange && m != nil {
612 2 : b, ok := m.LargestBound(i.filter)
613 2 : if !ok {
614 2 : m = i.Next()
615 2 : } else if c := cmp(b.UserKey, userKey); c < 0 || c == 0 && b.IsExclusiveSentinel() {
616 2 : // This file does not contain any keys of the type ≥ lower. It
617 2 : // should be filtered, even though it does contain point keys.
618 2 : m = i.Next()
619 2 : }
620 : }
621 2 : return i.skipFilteredForward(m)
622 : }
623 :
624 : // SeekLT seeks to the last file in the iterator's file set with a smallest
625 : // user key less than the provided user key. The iterator must have been
626 : // constructed from L1+, because it requires the underlying files to be sorted
627 : // by user keys and non-overlapping.
628 2 : func (i *LevelIterator) SeekLT(cmp Compare, userKey []byte) *FileMetadata {
629 2 : // TODO(jackson): Assert that i.iter.cmp == btreeCmpSmallestKey.
630 2 : if i.iter.r == nil {
631 2 : return nil
632 2 : }
633 2 : i.seek(func(m *FileMetadata) bool {
634 2 : return cmp(m.Smallest.UserKey, userKey) >= 0
635 2 : })
636 2 : m := i.Prev()
637 2 : // Although i.Prev() guarantees that the current file contains keys of the
638 2 : // relevant type, it doesn't guarantee that the keys of the relevant type
639 2 : // are < userKey.
640 2 : if i.filter != KeyTypePointAndRange && m != nil {
641 2 : b, ok := m.SmallestBound(i.filter)
642 2 : if !ok {
643 0 : panic("unreachable")
644 : }
645 2 : if c := cmp(b.UserKey, userKey); c >= 0 {
646 2 : // This file does not contain any keys of the type ≥ lower. It
647 2 : // should be filtered, even though it does contain point keys.
648 2 : m = i.Prev()
649 2 : }
650 : }
651 2 : return i.skipFilteredBackward(m)
652 : }
653 :
654 : // skipFilteredForward takes the file metadata at the iterator's current
655 : // position, and skips forward if the current key-type filter (i.filter)
656 : // excludes the file. It skips until it finds an unfiltered file or exhausts the
657 : // level. If lower is != nil, skipFilteredForward skips any files that do not
658 : // contain keys with the provided key-type ≥ lower.
659 : //
660 : // skipFilteredForward also enforces the upper bound, returning nil if at any
661 : // point the upper bound is exceeded.
662 2 : func (i *LevelIterator) skipFilteredForward(meta *FileMetadata) *FileMetadata {
663 2 : for meta != nil && !meta.ContainsKeyType(i.filter) {
664 2 : i.iter.next()
665 2 : if !i.iter.valid() {
666 2 : meta = nil
667 2 : } else {
668 2 : meta = i.iter.cur()
669 2 : }
670 : }
671 2 : if meta != nil && i.end != nil && cmpIter(i.iter, *i.end) > 0 {
672 2 : // Exceeded upper bound.
673 2 : meta = nil
674 2 : }
675 2 : return meta
676 : }
677 :
678 : // skipFilteredBackward takes the file metadata at the iterator's current
679 : // position, and skips backward if the current key-type filter (i.filter)
680 : // excludes the file. It skips until it finds an unfiltered file or exhausts the
681 : // level. If upper is != nil, skipFilteredBackward skips any files that do not
682 : // contain keys with the provided key-type < upper.
683 : //
684 : // skipFilteredBackward also enforces the lower bound, returning nil if at any
685 : // point the lower bound is exceeded.
686 2 : func (i *LevelIterator) skipFilteredBackward(meta *FileMetadata) *FileMetadata {
687 2 : for meta != nil && !meta.ContainsKeyType(i.filter) {
688 2 : i.iter.prev()
689 2 : if !i.iter.valid() {
690 2 : meta = nil
691 2 : } else {
692 2 : meta = i.iter.cur()
693 2 : }
694 : }
695 2 : if meta != nil && i.start != nil && cmpIter(i.iter, *i.start) < 0 {
696 0 : // Exceeded lower bound.
697 0 : meta = nil
698 0 : }
699 2 : return meta
700 : }
701 :
702 2 : func (i *LevelIterator) seek(fn func(*FileMetadata) bool) *FileMetadata {
703 2 : i.iter.seek(fn)
704 2 :
705 2 : // i.iter.seek seeked in the unbounded underlying B-Tree. If the iterator
706 2 : // has start or end bounds, we may have exceeded them. Reset to the bounds
707 2 : // if necessary.
708 2 : //
709 2 : // NB: The LevelIterator and LevelSlice semantics require that a bounded
710 2 : // LevelIterator/LevelSlice containing files x0, x1, ..., xn behave
711 2 : // identically to an unbounded LevelIterator/LevelSlice of a B-Tree
712 2 : // containing x0, x1, ..., xn. In other words, any files outside the
713 2 : // LevelIterator's bounds should not influence the iterator's behavior.
714 2 : // When seeking, this means a SeekGE that seeks beyond the end bound,
715 2 : // followed by a Prev should return the last element within bounds.
716 2 : if i.end != nil && cmpIter(i.iter, *i.end) > 0 {
717 2 : i.iter = i.end.clone()
718 2 : // Since seek(fn) positioned beyond i.end, we know there is nothing to
719 2 : // return within bounds.
720 2 : i.iter.next()
721 2 : return nil
722 2 : } else if i.start != nil && cmpIter(i.iter, *i.start) < 0 {
723 2 : i.iter = i.start.clone()
724 2 : }
725 2 : if !i.iter.valid() {
726 2 : return nil
727 2 : }
728 2 : return i.iter.cur()
729 : }
730 :
731 : // Take constructs a LevelFile containing the file at the iterator's current
732 : // position. Take panics if the iterator is not currently positioned over a
733 : // file.
734 2 : func (i *LevelIterator) Take() LevelFile {
735 2 : m := i.Current()
736 2 : if m == nil {
737 0 : panic("Take called on invalid LevelIterator")
738 : }
739 : // LevelSlice's start and end fields are immutable and are positioned to
740 : // the same position for a LevelFile because they're inclusive, so we can
741 : // share one iterator stack between the two bounds.
742 2 : boundsIter := i.iter.clone()
743 2 : s := newBoundedLevelSlice(i.iter.clone(), &boundsIter, &boundsIter)
744 2 : return LevelFile{
745 2 : FileMetadata: m,
746 2 : slice: s,
747 2 : }
748 : }
|
