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