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 2 : func (lm *LevelMetadata) clone() LevelMetadata {
31 2 : return LevelMetadata{
32 2 : level: lm.level,
33 2 : totalSize: lm.totalSize,
34 2 : NumVirtual: lm.NumVirtual,
35 2 : VirtualSize: lm.VirtualSize,
36 2 : tree: lm.tree.Clone(),
37 2 : }
38 2 : }
39 :
40 2 : func (lm *LevelMetadata) release() (obsolete []*FileBacking) {
41 2 : return lm.tree.Release()
42 2 : }
43 :
44 : // MakeLevelMetadata creates a LevelMetadata with the given files.
45 2 : func MakeLevelMetadata(cmp Compare, level int, files []*FileMetadata) LevelMetadata {
46 2 : bcmp := btreeCmpSeqNum
47 2 : if level > 0 {
48 2 : bcmp = btreeCmpSmallestKey(cmp)
49 2 : }
50 2 : var lm LevelMetadata
51 2 : lm.level = level
52 2 : lm.tree, _ = makeBTree(bcmp, files)
53 2 : 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 2 : return lm
61 : }
62 :
63 2 : func makeBTree(cmp btreeCmp, files []*FileMetadata) (btree, LevelSlice) {
64 2 : var t btree
65 2 : t.cmp = cmp
66 2 : for _, f := range files {
67 2 : t.Insert(f)
68 2 : }
69 2 : return t, newLevelSlice(t.Iter())
70 : }
71 :
72 2 : func (lm *LevelMetadata) insert(f *FileMetadata) error {
73 2 : if err := lm.tree.Insert(f); err != nil {
74 1 : return err
75 1 : }
76 2 : lm.totalSize += f.Size
77 2 : if f.Virtual {
78 2 : lm.NumVirtual++
79 2 : lm.VirtualSize += f.Size
80 2 : }
81 2 : return nil
82 : }
83 :
84 2 : func (lm *LevelMetadata) remove(f *FileMetadata) bool {
85 2 : lm.totalSize -= f.Size
86 2 : if f.Virtual {
87 2 : lm.NumVirtual--
88 2 : lm.VirtualSize -= f.Size
89 2 : }
90 2 : return lm.tree.Delete(f)
91 : }
92 :
93 : // Empty indicates whether there are any files in the level.
94 2 : func (lm *LevelMetadata) Empty() bool {
95 2 : return lm.tree.Count() == 0
96 2 : }
97 :
98 : // Len returns the number of files within the level.
99 2 : func (lm *LevelMetadata) Len() int {
100 2 : return lm.tree.Count()
101 2 : }
102 :
103 : // Size returns the cumulative size of all the files within the level.
104 2 : func (lm *LevelMetadata) Size() uint64 {
105 2 : return lm.totalSize
106 2 : }
107 :
108 : // Iter constructs a LevelIterator over the entire level.
109 2 : func (lm *LevelMetadata) Iter() LevelIterator {
110 2 : return LevelIterator{iter: lm.tree.Iter()}
111 2 : }
112 :
113 : // Slice constructs a slice containing the entire level.
114 2 : func (lm *LevelMetadata) Slice() LevelSlice {
115 2 : return newLevelSlice(lm.tree.Iter())
116 2 : }
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 2 : func (lm *LevelMetadata) Find(cmp base.Compare, m *FileMetadata) LevelSlice {
121 2 : iter := lm.Iter()
122 2 : 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 2 : } else {
134 2 : // For levels other than L0, UserKeyBounds in the level are non-overlapping
135 2 : // so we only need to check one file.
136 2 : if f := iter.SeekGE(cmp, m.UserKeyBounds().Start); f == m {
137 2 : return iter.Take().slice
138 2 : }
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 2 : func (lm *LevelMetadata) Annotation(annotator Annotator) interface{} {
149 2 : if lm.Empty() {
150 2 : return annotator.Zero(nil)
151 2 : }
152 2 : v, _ := lm.tree.root.Annotation(annotator)
153 2 : 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 2 : func (lf LevelFile) Slice() LevelSlice {
177 2 : return lf.slice
178 2 : }
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 2 : func NewLevelSliceSeqSorted(files []*FileMetadata) LevelSlice {
185 2 : tr, slice := makeBTree(btreeCmpSeqNum, files)
186 2 : tr.Release()
187 2 : slice.verifyInvariants()
188 2 : return slice
189 2 : }
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 2 : func NewLevelSliceKeySorted(cmp base.Compare, files []*FileMetadata) LevelSlice {
196 2 : tr, slice := makeBTree(btreeCmpSmallestKey(cmp), files)
197 2 : tr.Release()
198 2 : slice.verifyInvariants()
199 2 : return slice
200 2 : }
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 2 : func newLevelSlice(iter iterator) LevelSlice {
215 2 : s := LevelSlice{iter: iter}
216 2 : if iter.r != nil {
217 2 : s.length = iter.r.subtreeCount
218 2 : }
219 2 : s.verifyInvariants()
220 2 : 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 2 : func newBoundedLevelSlice(iter iterator, startBound, endBound *iterator) LevelSlice {
228 2 : s := LevelSlice{
229 2 : iter: iter,
230 2 : start: startBound,
231 2 : end: endBound,
232 2 : }
233 2 : if iter.valid() {
234 2 : s.length = endBound.countLeft() - startBound.countLeft()
235 2 : // NB: The +1 is a consequence of the end bound being inclusive.
236 2 : if endBound.valid() {
237 2 : s.length++
238 2 : }
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 2 : if s.length < 0 {
245 2 : s.length = 0
246 2 : }
247 : }
248 2 : s.verifyInvariants()
249 2 : 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 2 : func (ls LevelSlice) verifyInvariants() {
269 2 : if invariants.Enabled {
270 2 : i := ls.Iter()
271 2 : var length int
272 2 : for f := i.First(); f != nil; f = i.Next() {
273 2 : length++
274 2 : }
275 2 : 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 2 : func (ls LevelSlice) Each(fn func(*FileMetadata)) {
283 2 : iter := ls.Iter()
284 2 : for f := iter.First(); f != nil; f = iter.Next() {
285 2 : fn(f)
286 2 : }
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 2 : func (ls *LevelSlice) Empty() bool {
304 2 : return emptyWithBounds(ls.iter, ls.start, ls.end)
305 2 : }
306 :
307 : // Iter constructs a LevelIterator that iterates over the slice.
308 2 : func (ls *LevelSlice) Iter() LevelIterator {
309 2 : return LevelIterator{
310 2 : start: ls.start,
311 2 : end: ls.end,
312 2 : iter: ls.iter.clone(),
313 2 : }
314 2 : }
315 :
316 : // Len returns the number of files in the slice. Its runtime is constant.
317 2 : func (ls *LevelSlice) Len() int {
318 2 : return ls.length
319 2 : }
320 :
321 : // SizeSum sums the size of all files in the slice. Its runtime is linear in
322 : // the length of the slice.
323 2 : func (ls *LevelSlice) SizeSum() uint64 {
324 2 : var sum uint64
325 2 : iter := ls.Iter()
326 2 : for f := iter.First(); f != nil; f = iter.Next() {
327 2 : sum += f.Size
328 2 : }
329 2 : 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 2 : func (ls *LevelSlice) NumVirtual() uint64 {
335 2 : var n uint64
336 2 : iter := ls.Iter()
337 2 : for f := iter.First(); f != nil; f = iter.Next() {
338 2 : if f.Virtual {
339 2 : n++
340 2 : }
341 : }
342 2 : return n
343 : }
344 :
345 : // VirtualSizeSum returns the sum of the sizes of the virtual sstables in the
346 : // level.
347 2 : func (ls *LevelSlice) VirtualSizeSum() uint64 {
348 2 : var sum uint64
349 2 : iter := ls.Iter()
350 2 : for f := iter.First(); f != nil; f = iter.Next() {
351 2 : if f.Virtual {
352 2 : sum += f.Size
353 2 : }
354 : }
355 2 : 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 2 : func (ls LevelSlice) Reslice(resliceFunc func(start, end *LevelIterator)) LevelSlice {
367 2 : if ls.iter.r == nil {
368 1 : return ls
369 1 : }
370 2 : var start, end LevelIterator
371 2 : if ls.start == nil {
372 1 : start.iter = ls.iter.clone()
373 1 : start.iter.first()
374 2 : } else {
375 2 : start.iter = ls.start.clone()
376 2 : }
377 2 : if ls.end == nil {
378 1 : end.iter = ls.iter.clone()
379 1 : end.iter.last()
380 2 : } else {
381 2 : end.iter = ls.end.clone()
382 2 : }
383 2 : resliceFunc(&start, &end)
384 2 : 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 2 : func (ls LevelSlice) Overlaps(cmp Compare, bounds base.UserKeyBounds) LevelSlice {
390 2 : startIter := ls.Iter()
391 2 : startIter.SeekGE(cmp, bounds.Start)
392 2 :
393 2 : // Note: newBoundedLevelSlice uses inclusive bounds, so we need to position
394 2 : // endIter at the last overlapping file.
395 2 : endIter := ls.Iter()
396 2 : endIterFile := endIter.SeekGE(cmp, bounds.End.Key)
397 2 : // The first file that ends at/after bounds.End.Key might or might not overlap
398 2 : // the bounds; we need to check the start key.
399 2 : if endIterFile == nil || !bounds.End.IsUpperBoundFor(cmp, endIterFile.Smallest.UserKey) {
400 2 : endIter.Prev()
401 2 : }
402 2 : 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 2 : func (i *LevelIterator) Clone() LevelIterator {
474 2 : if i.iter.r == nil {
475 2 : return *i
476 2 : }
477 : // The start and end iterators are not cloned and are treated as
478 : // immutable.
479 2 : return LevelIterator{
480 2 : iter: i.iter.clone(),
481 2 : start: i.start,
482 2 : end: i.end,
483 2 : filter: i.filter,
484 2 : }
485 : }
486 :
487 : // Current returns the item at the current iterator position.
488 : //
489 : // Current is deprecated. Callers should instead use the return value of a
490 : // positioning operation.
491 2 : func (i *LevelIterator) Current() *FileMetadata {
492 2 : if !i.iter.valid() ||
493 2 : (i.end != nil && cmpIter(i.iter, *i.end) > 0) ||
494 2 : (i.start != nil && cmpIter(i.iter, *i.start) < 0) {
495 2 : return nil
496 2 : }
497 2 : return i.iter.cur()
498 : }
499 :
500 2 : func (i *LevelIterator) empty() bool {
501 2 : return emptyWithBounds(i.iter, i.start, i.end)
502 2 : }
503 :
504 : // Filter clones the iterator and sets the desired KeyType as the key to filter
505 : // files on.
506 2 : func (i *LevelIterator) Filter(keyType KeyType) LevelIterator {
507 2 : l := i.Clone()
508 2 : l.filter = keyType
509 2 : return l
510 2 : }
511 :
512 2 : func emptyWithBounds(i iterator, start, end *iterator) bool {
513 2 : // If i.r is nil, the iterator was constructed from an empty btree.
514 2 : // If the end bound is before the start bound, the bounds represent an
515 2 : // empty slice of the B-Tree.
516 2 : return i.r == nil || (start != nil && end != nil && cmpIter(*end, *start) < 0)
517 2 : }
518 :
519 : // First seeks to the first file in the iterator and returns it.
520 2 : func (i *LevelIterator) First() *FileMetadata {
521 2 : if i.empty() {
522 2 : return nil
523 2 : }
524 2 : if i.start != nil {
525 2 : i.iter = i.start.clone()
526 2 : } else {
527 2 : i.iter.first()
528 2 : }
529 2 : if !i.iter.valid() {
530 2 : return nil
531 2 : }
532 2 : return i.skipFilteredForward(i.iter.cur())
533 : }
534 :
535 : // Last seeks to the last file in the iterator and returns it.
536 2 : func (i *LevelIterator) Last() *FileMetadata {
537 2 : if i.empty() {
538 2 : return nil
539 2 : }
540 2 : if i.end != nil {
541 2 : i.iter = i.end.clone()
542 2 : } else {
543 2 : i.iter.last()
544 2 : }
545 2 : if !i.iter.valid() {
546 0 : return nil
547 0 : }
548 2 : return i.skipFilteredBackward(i.iter.cur())
549 : }
550 :
551 : // Next advances the iterator to the next file and returns it.
552 2 : func (i *LevelIterator) Next() *FileMetadata {
553 2 : if i.iter.r == nil {
554 0 : return nil
555 0 : }
556 2 : if invariants.Enabled && (i.iter.pos >= i.iter.n.count || (i.end != nil && cmpIter(i.iter, *i.end) > 0)) {
557 0 : panic("pebble: cannot next forward-exhausted iterator")
558 : }
559 2 : i.iter.next()
560 2 : if !i.iter.valid() {
561 2 : return nil
562 2 : }
563 2 : return i.skipFilteredForward(i.iter.cur())
564 : }
565 :
566 : // Prev moves the iterator the previous file and returns it.
567 2 : func (i *LevelIterator) Prev() *FileMetadata {
568 2 : if i.iter.r == nil {
569 2 : return nil
570 2 : }
571 2 : if invariants.Enabled && (i.iter.pos < 0 || (i.start != nil && cmpIter(i.iter, *i.start) < 0)) {
572 0 : panic("pebble: cannot prev backward-exhausted iterator")
573 : }
574 2 : i.iter.prev()
575 2 : if !i.iter.valid() {
576 2 : return nil
577 2 : }
578 2 : return i.skipFilteredBackward(i.iter.cur())
579 : }
580 :
581 : // SeekGE seeks to the first file with a largest key (of the desired type) that
582 : // is an upper bound for the given user key. This is the first file that could
583 : // contain a user key that is greater than or equal to userKey.
584 : //
585 : // More specifically, userKey is less than the file's largest.UserKey or they
586 : // are equal and largest is not an exclusive sentinel.
587 : //
588 : // The iterator must have been constructed from L1+ or from a single sublevel of
589 : // L0, because it requires the underlying files to be sorted by user keys and
590 : // non-overlapping.
591 2 : func (i *LevelIterator) SeekGE(cmp Compare, userKey []byte) *FileMetadata {
592 2 : if i.iter.r == nil {
593 2 : return nil
594 2 : }
595 2 : i.assertNotL0Cmp()
596 2 : m := i.seek(func(m *FileMetadata) bool {
597 2 : return m.Largest.IsUpperBoundFor(cmp, userKey)
598 2 : })
599 2 : if i.filter != KeyTypePointAndRange && m != nil {
600 2 : b, ok := m.LargestBound(i.filter)
601 2 : if !ok || !b.IsUpperBoundFor(cmp, userKey) {
602 2 : // The file does not contain any keys of desired key types
603 2 : // that are >= userKey.
604 2 : return i.Next()
605 2 : }
606 : }
607 2 : return i.skipFilteredForward(m)
608 : }
609 :
610 : // SeekLT seeks to the last file with a smallest key (of the desired type) that
611 : // is less than the given user key. This is the last file that could contain a
612 : // key less than userKey.
613 : //
614 : // The iterator must have been constructed from L1+ or from a single sublevel of
615 : // L0, because it requires the underlying files to be sorted by user keys and
616 : // non-overlapping.
617 2 : func (i *LevelIterator) SeekLT(cmp Compare, userKey []byte) *FileMetadata {
618 2 : if i.iter.r == nil {
619 2 : return nil
620 2 : }
621 2 : i.assertNotL0Cmp()
622 2 : i.seek(func(m *FileMetadata) bool {
623 2 : return cmp(m.Smallest.UserKey, userKey) >= 0
624 2 : })
625 2 : m := i.Prev()
626 2 : // Although i.Prev() guarantees that the current file contains keys of the
627 2 : // relevant type, it doesn't guarantee that the keys of the relevant type
628 2 : // are < userKey. For example, say that we have these two files:
629 2 : // f1: [a, f) with keys of the desired type in the range [c, d)
630 2 : // f2: [h, k)
631 2 : // and userKey is b. The seek call above will position us at f2 and Prev will
632 2 : // position us at f1.
633 2 : if i.filter != KeyTypePointAndRange && m != nil {
634 2 : b, ok := m.SmallestBound(i.filter)
635 2 : if !ok {
636 0 : panic("unreachable")
637 : }
638 2 : if cmp(b.UserKey, userKey) >= 0 {
639 2 : // This file does not contain any keys of desired key types
640 2 : // that are <= userKey.
641 2 : return i.Prev()
642 2 : }
643 : }
644 2 : return m
645 : }
646 :
647 : // assertNotL0Cmp verifies that the btree associated with the iterator is
648 : // ordered by Smallest key (i.e. L1+ or L0 sublevel) and not by LargestSeqNum
649 : // (L0).
650 2 : func (i *LevelIterator) assertNotL0Cmp() {
651 2 : if invariants.Enabled {
652 2 : if reflect.ValueOf(i.iter.cmp).Pointer() == reflect.ValueOf(btreeCmpSeqNum).Pointer() {
653 0 : panic("Seek used with btreeCmpSeqNum")
654 : }
655 : }
656 : }
657 :
658 : // skipFilteredForward takes the file metadata at the iterator's current
659 : // position, and skips forward if the current key-type filter (i.filter)
660 : // excludes the file. It skips until it finds an unfiltered file or exhausts the
661 : // level. If lower is != nil, skipFilteredForward skips any files that do not
662 : // contain keys with the provided key-type ≥ lower.
663 : //
664 : // skipFilteredForward also enforces the upper bound, returning nil if at any
665 : // point the upper bound is exceeded.
666 2 : func (i *LevelIterator) skipFilteredForward(meta *FileMetadata) *FileMetadata {
667 2 : for meta != nil && !meta.ContainsKeyType(i.filter) {
668 2 : i.iter.next()
669 2 : if !i.iter.valid() {
670 2 : meta = nil
671 2 : } else {
672 2 : meta = i.iter.cur()
673 2 : }
674 : }
675 2 : if meta != nil && i.end != nil && cmpIter(i.iter, *i.end) > 0 {
676 2 : // Exceeded upper bound.
677 2 : meta = nil
678 2 : }
679 2 : return meta
680 : }
681 :
682 : // skipFilteredBackward takes the file metadata at the iterator's current
683 : // position, and skips backward if the current key-type filter (i.filter)
684 : // excludes the file. It skips until it finds an unfiltered file or exhausts the
685 : // level. If upper is != nil, skipFilteredBackward skips any files that do not
686 : // contain keys with the provided key-type < upper.
687 : //
688 : // skipFilteredBackward also enforces the lower bound, returning nil if at any
689 : // point the lower bound is exceeded.
690 2 : func (i *LevelIterator) skipFilteredBackward(meta *FileMetadata) *FileMetadata {
691 2 : for meta != nil && !meta.ContainsKeyType(i.filter) {
692 2 : i.iter.prev()
693 2 : if !i.iter.valid() {
694 2 : meta = nil
695 2 : } else {
696 2 : meta = i.iter.cur()
697 2 : }
698 : }
699 2 : if meta != nil && i.start != nil && cmpIter(i.iter, *i.start) < 0 {
700 1 : // Exceeded lower bound.
701 1 : meta = nil
702 1 : }
703 2 : return meta
704 : }
705 :
706 : // seek repositions the iterator over the first file for which fn returns true,
707 : // mirroring the semantics of the standard library's sort.Search function: fn
708 : // returns false for some (possibly empty) prefix of the tree's files, and then
709 : // true for the (possibly empty) remainder.
710 2 : func (i *LevelIterator) seek(fn func(*FileMetadata) bool) *FileMetadata {
711 2 : i.iter.seek(fn)
712 2 :
713 2 : // i.iter.seek seeked in the unbounded underlying B-Tree. If the iterator
714 2 : // has start or end bounds, we may have exceeded them. Reset to the bounds
715 2 : // if necessary.
716 2 : //
717 2 : // NB: The LevelIterator and LevelSlice semantics require that a bounded
718 2 : // LevelIterator/LevelSlice containing files x0, x1, ..., xn behave
719 2 : // identically to an unbounded LevelIterator/LevelSlice of a B-Tree
720 2 : // containing x0, x1, ..., xn. In other words, any files outside the
721 2 : // LevelIterator's bounds should not influence the iterator's behavior.
722 2 : // When seeking, this means a SeekGE that seeks beyond the end bound,
723 2 : // followed by a Prev should return the last element within bounds.
724 2 : if i.end != nil && cmpIter(i.iter, *i.end) > 0 {
725 2 : i.iter = i.end.clone()
726 2 : // Since seek(fn) positioned beyond i.end, we know there is nothing to
727 2 : // return within bounds.
728 2 : i.iter.next()
729 2 : return nil
730 2 : } else if i.start != nil && cmpIter(i.iter, *i.start) < 0 {
731 1 : i.iter = i.start.clone()
732 1 : }
733 2 : if !i.iter.valid() {
734 2 : return nil
735 2 : }
736 2 : return i.iter.cur()
737 : }
738 :
739 : // Take constructs a LevelFile containing the file at the iterator's current
740 : // position. Take panics if the iterator is not currently positioned over a
741 : // file.
742 2 : func (i *LevelIterator) Take() LevelFile {
743 2 : m := i.Current()
744 2 : if m == nil {
745 0 : panic("Take called on invalid LevelIterator")
746 : }
747 : // LevelSlice's start and end fields are immutable and are positioned to
748 : // the same position for a LevelFile because they're inclusive, so we can
749 : // share one iterator stack between the two bounds.
750 2 : boundsIter := i.iter.clone()
751 2 : s := newBoundedLevelSlice(i.iter.clone(), &boundsIter, &boundsIter)
752 2 : return LevelFile{
753 2 : FileMetadata: m,
754 2 : slice: s,
755 2 : }
756 : }
|
