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