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 2 : func makeLevelMetadata(cmp Compare, level int, files []*FileMetadata) LevelMetadata {
45 2 : bcmp := btreeCmpSeqNum
46 2 : if level > 0 {
47 2 : bcmp = btreeCmpSmallestKey(cmp)
48 2 : }
49 2 : var lm LevelMetadata
50 2 : lm.level = level
51 2 : lm.tree, _ = makeBTree(bcmp, files)
52 2 : for _, f := range files {
53 1 : lm.totalSize += f.Size
54 1 : if f.Virtual {
55 0 : lm.NumVirtual++
56 0 : lm.VirtualSize += f.Size
57 0 : }
58 : }
59 2 : return lm
60 : }
61 :
62 2 : func makeBTree(cmp btreeCmp, files []*FileMetadata) (btree, LevelSlice) {
63 2 : var t btree
64 2 : t.cmp = cmp
65 2 : for _, f := range files {
66 2 : t.Insert(f)
67 2 : }
68 2 : return t, newLevelSlice(t.Iter())
69 : }
70 :
71 2 : func (lm *LevelMetadata) insert(f *FileMetadata) error {
72 2 : if err := lm.tree.Insert(f); err != nil {
73 1 : return err
74 1 : }
75 2 : lm.totalSize += f.Size
76 2 : if f.Virtual {
77 2 : lm.NumVirtual++
78 2 : lm.VirtualSize += f.Size
79 2 : }
80 2 : return nil
81 : }
82 :
83 2 : func (lm *LevelMetadata) remove(f *FileMetadata) bool {
84 2 : lm.totalSize -= f.Size
85 2 : if f.Virtual {
86 2 : lm.NumVirtual--
87 2 : lm.VirtualSize -= f.Size
88 2 : }
89 2 : return lm.tree.Delete(f)
90 : }
91 :
92 : // Empty indicates whether there are any files in the level.
93 2 : func (lm *LevelMetadata) Empty() bool {
94 2 : return lm.tree.Count() == 0
95 2 : }
96 :
97 : // Len returns the number of files within the level.
98 2 : func (lm *LevelMetadata) Len() int {
99 2 : return lm.tree.Count()
100 2 : }
101 :
102 : // Size returns the cumulative size of all the files within the level.
103 2 : func (lm *LevelMetadata) Size() uint64 {
104 2 : return lm.totalSize
105 2 : }
106 :
107 : // Iter constructs a LevelIterator over the entire level.
108 2 : func (lm *LevelMetadata) Iter() LevelIterator {
109 2 : return LevelIterator{iter: lm.tree.Iter()}
110 2 : }
111 :
112 : // Slice constructs a slice containing the entire level.
113 2 : func (lm *LevelMetadata) Slice() LevelSlice {
114 2 : return newLevelSlice(lm.tree.Iter())
115 2 : }
116 :
117 : // Find finds the provided file in the level if it exists.
118 2 : func (lm *LevelMetadata) Find(cmp base.Compare, m *FileMetadata) *LevelFile {
119 2 : iter := lm.Iter()
120 2 : if lm.level != 0 {
121 2 : // If lm holds files for levels >0, we can narrow our search by binary
122 2 : // searching by bounds.
123 2 : o := overlaps(iter, cmp, m.UserKeyBounds())
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 : // LevelIterator iterates over a set of files' metadata. Its zero value is an
397 : // empty iterator.
398 : type LevelIterator struct {
399 : iter iterator
400 : start *iterator
401 : end *iterator
402 : filter KeyType
403 : }
404 :
405 0 : func (i LevelIterator) String() string {
406 0 : var buf bytes.Buffer
407 0 : iter := i.iter.clone()
408 0 : iter.first()
409 0 : iter.prev()
410 0 : if i.iter.pos == -1 {
411 0 : fmt.Fprint(&buf, "(<start>)*")
412 0 : }
413 0 : iter.next()
414 0 : for ; iter.valid(); iter.next() {
415 0 : if buf.Len() > 0 {
416 0 : fmt.Fprint(&buf, " ")
417 0 : }
418 :
419 0 : if i.start != nil && cmpIter(iter, *i.start) == 0 {
420 0 : fmt.Fprintf(&buf, " [ ")
421 0 : }
422 0 : isCurrentPos := cmpIter(iter, i.iter) == 0
423 0 : if isCurrentPos {
424 0 : fmt.Fprint(&buf, " ( ")
425 0 : }
426 0 : fmt.Fprint(&buf, iter.cur().String())
427 0 : if isCurrentPos {
428 0 : fmt.Fprint(&buf, " )*")
429 0 : }
430 0 : if i.end != nil && cmpIter(iter, *i.end) == 0 {
431 0 : fmt.Fprintf(&buf, " ]")
432 0 : }
433 : }
434 0 : if i.iter.n != nil && i.iter.pos >= i.iter.n.count {
435 0 : if buf.Len() > 0 {
436 0 : fmt.Fprint(&buf, " ")
437 0 : }
438 0 : fmt.Fprint(&buf, "(<end>)*")
439 : }
440 0 : return buf.String()
441 : }
442 :
443 : // Clone copies the iterator, returning an independent iterator at the same
444 : // position.
445 2 : func (i *LevelIterator) Clone() LevelIterator {
446 2 : if i.iter.r == nil {
447 2 : return *i
448 2 : }
449 : // The start and end iterators are not cloned and are treated as
450 : // immutable.
451 2 : return LevelIterator{
452 2 : iter: i.iter.clone(),
453 2 : start: i.start,
454 2 : end: i.end,
455 2 : filter: i.filter,
456 2 : }
457 : }
458 :
459 : // Current returns the item at the current iterator position.
460 : //
461 : // Current is deprecated. Callers should instead use the return value of a
462 : // positioning operation.
463 2 : func (i *LevelIterator) Current() *FileMetadata {
464 2 : if !i.iter.valid() ||
465 2 : (i.end != nil && cmpIter(i.iter, *i.end) > 0) ||
466 2 : (i.start != nil && cmpIter(i.iter, *i.start) < 0) {
467 2 : return nil
468 2 : }
469 2 : return i.iter.cur()
470 : }
471 :
472 2 : func (i *LevelIterator) empty() bool {
473 2 : return emptyWithBounds(i.iter, i.start, i.end)
474 2 : }
475 :
476 : // Filter clones the iterator and sets the desired KeyType as the key to filter
477 : // files on.
478 2 : func (i *LevelIterator) Filter(keyType KeyType) LevelIterator {
479 2 : l := i.Clone()
480 2 : l.filter = keyType
481 2 : return l
482 2 : }
483 :
484 2 : func emptyWithBounds(i iterator, start, end *iterator) bool {
485 2 : // If i.r is nil, the iterator was constructed from an empty btree.
486 2 : // If the end bound is before the start bound, the bounds represent an
487 2 : // empty slice of the B-Tree.
488 2 : return i.r == nil || (start != nil && end != nil && cmpIter(*end, *start) < 0)
489 2 : }
490 :
491 : // First seeks to the first file in the iterator and returns it.
492 2 : func (i *LevelIterator) First() *FileMetadata {
493 2 : if i.empty() {
494 2 : return nil
495 2 : }
496 2 : if i.start != nil {
497 2 : i.iter = i.start.clone()
498 2 : } else {
499 2 : i.iter.first()
500 2 : }
501 2 : if !i.iter.valid() {
502 2 : return nil
503 2 : }
504 2 : return i.skipFilteredForward(i.iter.cur())
505 : }
506 :
507 : // Last seeks to the last file in the iterator and returns it.
508 2 : func (i *LevelIterator) Last() *FileMetadata {
509 2 : if i.empty() {
510 2 : return nil
511 2 : }
512 2 : if i.end != nil {
513 2 : i.iter = i.end.clone()
514 2 : } else {
515 2 : i.iter.last()
516 2 : }
517 2 : if !i.iter.valid() {
518 0 : return nil
519 0 : }
520 2 : return i.skipFilteredBackward(i.iter.cur())
521 : }
522 :
523 : // Next advances the iterator to the next file and returns it.
524 2 : func (i *LevelIterator) Next() *FileMetadata {
525 2 : if i.iter.r == nil {
526 0 : return nil
527 0 : }
528 2 : if invariants.Enabled && (i.iter.pos >= i.iter.n.count || (i.end != nil && cmpIter(i.iter, *i.end) > 0)) {
529 0 : panic("pebble: cannot next forward-exhausted iterator")
530 : }
531 2 : i.iter.next()
532 2 : if !i.iter.valid() {
533 2 : return nil
534 2 : }
535 2 : return i.skipFilteredForward(i.iter.cur())
536 : }
537 :
538 : // Prev moves the iterator the previous file and returns it.
539 2 : func (i *LevelIterator) Prev() *FileMetadata {
540 2 : if i.iter.r == nil {
541 2 : return nil
542 2 : }
543 2 : if invariants.Enabled && (i.iter.pos < 0 || (i.start != nil && cmpIter(i.iter, *i.start) < 0)) {
544 0 : panic("pebble: cannot prev backward-exhausted iterator")
545 : }
546 2 : i.iter.prev()
547 2 : if !i.iter.valid() {
548 2 : return nil
549 2 : }
550 2 : return i.skipFilteredBackward(i.iter.cur())
551 : }
552 :
553 : // SeekGE seeks to the first file in the iterator's file set with a largest
554 : // user key greater than or equal to the provided user key. The iterator must
555 : // have been constructed from L1+ or from a single sublevel of L0, because it
556 : // requires the underlying files to be sorted by user keys and non-overlapping.
557 2 : func (i *LevelIterator) SeekGE(cmp Compare, userKey []byte) *FileMetadata {
558 2 : if i.iter.r == nil {
559 2 : return nil
560 2 : }
561 2 : if invariants.Enabled {
562 2 : i.assertNotL0Cmp()
563 2 : }
564 2 : m := i.seek(func(m *FileMetadata) bool {
565 2 : return cmp(m.Largest.UserKey, userKey) >= 0
566 2 : })
567 2 : if i.filter != KeyTypePointAndRange && m != nil {
568 2 : b, ok := m.LargestBound(i.filter)
569 2 : if !ok {
570 2 : m = i.Next()
571 2 : } else if c := cmp(b.UserKey, userKey); c < 0 || c == 0 && b.IsExclusiveSentinel() {
572 2 : // This file does not contain any keys of the type ≥ lower. It
573 2 : // should be filtered, even though it does contain point keys.
574 2 : m = i.Next()
575 2 : }
576 : }
577 2 : return i.skipFilteredForward(m)
578 : }
579 :
580 : // assertNotL0Cmp verifies that the btree associated with the iterator is
581 : // ordered by Smallest key (i.e. L1+ or L0 sublevel) and not by LargestSeqNum
582 : // (L0).
583 2 : func (i *LevelIterator) assertNotL0Cmp() {
584 2 : if reflect.ValueOf(i.iter.cmp).Pointer() == reflect.ValueOf(btreeCmpSeqNum).Pointer() {
585 0 : panic("Seek used with btreeCmpSeqNum")
586 : }
587 : }
588 :
589 : // SeekLT seeks to the last file in the iterator's file set with a smallest user
590 : // key less than the provided user key. The iterator must have been constructed
591 : // from L1+ or from a single sublevel of L0, because it requires the underlying
592 : // files to be sorted by user keys and non-overlapping.
593 2 : func (i *LevelIterator) SeekLT(cmp Compare, userKey []byte) *FileMetadata {
594 2 : if i.iter.r == nil {
595 2 : return nil
596 2 : }
597 2 : if invariants.Enabled {
598 2 : i.assertNotL0Cmp()
599 2 : }
600 2 : i.seek(func(m *FileMetadata) bool {
601 2 : return cmp(m.Smallest.UserKey, userKey) >= 0
602 2 : })
603 2 : m := i.Prev()
604 2 : // Although i.Prev() guarantees that the current file contains keys of the
605 2 : // relevant type, it doesn't guarantee that the keys of the relevant type
606 2 : // are < userKey.
607 2 : if i.filter != KeyTypePointAndRange && m != nil {
608 2 : b, ok := m.SmallestBound(i.filter)
609 2 : if !ok {
610 0 : panic("unreachable")
611 : }
612 2 : if c := cmp(b.UserKey, userKey); c >= 0 {
613 2 : // This file does not contain any keys of the type ≥ lower. It
614 2 : // should be filtered, even though it does contain point keys.
615 2 : m = i.Prev()
616 2 : }
617 : }
618 2 : return i.skipFilteredBackward(m)
619 : }
620 :
621 : // skipFilteredForward takes the file metadata at the iterator's current
622 : // position, and skips forward if the current key-type filter (i.filter)
623 : // excludes the file. It skips until it finds an unfiltered file or exhausts the
624 : // level. If lower is != nil, skipFilteredForward skips any files that do not
625 : // contain keys with the provided key-type ≥ lower.
626 : //
627 : // skipFilteredForward also enforces the upper bound, returning nil if at any
628 : // point the upper bound is exceeded.
629 2 : func (i *LevelIterator) skipFilteredForward(meta *FileMetadata) *FileMetadata {
630 2 : for meta != nil && !meta.ContainsKeyType(i.filter) {
631 2 : i.iter.next()
632 2 : if !i.iter.valid() {
633 2 : meta = nil
634 2 : } else {
635 2 : meta = i.iter.cur()
636 2 : }
637 : }
638 2 : if meta != nil && i.end != nil && cmpIter(i.iter, *i.end) > 0 {
639 2 : // Exceeded upper bound.
640 2 : meta = nil
641 2 : }
642 2 : return meta
643 : }
644 :
645 : // skipFilteredBackward takes the file metadata at the iterator's current
646 : // position, and skips backward 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 upper is != nil, skipFilteredBackward skips any files that do not
649 : // contain keys with the provided key-type < upper.
650 : //
651 : // skipFilteredBackward also enforces the lower bound, returning nil if at any
652 : // point the lower bound is exceeded.
653 2 : func (i *LevelIterator) skipFilteredBackward(meta *FileMetadata) *FileMetadata {
654 2 : for meta != nil && !meta.ContainsKeyType(i.filter) {
655 2 : i.iter.prev()
656 2 : if !i.iter.valid() {
657 2 : meta = nil
658 2 : } else {
659 2 : meta = i.iter.cur()
660 2 : }
661 : }
662 2 : if meta != nil && i.start != nil && cmpIter(i.iter, *i.start) < 0 {
663 1 : // Exceeded lower bound.
664 1 : meta = nil
665 1 : }
666 2 : return meta
667 : }
668 :
669 2 : func (i *LevelIterator) seek(fn func(*FileMetadata) bool) *FileMetadata {
670 2 : i.iter.seek(fn)
671 2 :
672 2 : // i.iter.seek seeked in the unbounded underlying B-Tree. If the iterator
673 2 : // has start or end bounds, we may have exceeded them. Reset to the bounds
674 2 : // if necessary.
675 2 : //
676 2 : // NB: The LevelIterator and LevelSlice semantics require that a bounded
677 2 : // LevelIterator/LevelSlice containing files x0, x1, ..., xn behave
678 2 : // identically to an unbounded LevelIterator/LevelSlice of a B-Tree
679 2 : // containing x0, x1, ..., xn. In other words, any files outside the
680 2 : // LevelIterator's bounds should not influence the iterator's behavior.
681 2 : // When seeking, this means a SeekGE that seeks beyond the end bound,
682 2 : // followed by a Prev should return the last element within bounds.
683 2 : if i.end != nil && cmpIter(i.iter, *i.end) > 0 {
684 2 : i.iter = i.end.clone()
685 2 : // Since seek(fn) positioned beyond i.end, we know there is nothing to
686 2 : // return within bounds.
687 2 : i.iter.next()
688 2 : return nil
689 2 : } else if i.start != nil && cmpIter(i.iter, *i.start) < 0 {
690 2 : i.iter = i.start.clone()
691 2 : }
692 2 : if !i.iter.valid() {
693 2 : return nil
694 2 : }
695 2 : return i.iter.cur()
696 : }
697 :
698 : // Take constructs a LevelFile containing the file at the iterator's current
699 : // position. Take panics if the iterator is not currently positioned over a
700 : // file.
701 2 : func (i *LevelIterator) Take() LevelFile {
702 2 : m := i.Current()
703 2 : if m == nil {
704 0 : panic("Take called on invalid LevelIterator")
705 : }
706 : // LevelSlice's start and end fields are immutable and are positioned to
707 : // the same position for a LevelFile because they're inclusive, so we can
708 : // share one iterator stack between the two bounds.
709 2 : boundsIter := i.iter.clone()
710 2 : s := newBoundedLevelSlice(i.iter.clone(), &boundsIter, &boundsIter)
711 2 : return LevelFile{
712 2 : FileMetadata: m,
713 2 : slice: s,
714 2 : }
715 : }
|
