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(cmp, 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 base.Compare, bcmp btreeCmp, files []*FileMetadata) (btree, LevelSlice) {
64 2 : var t btree
65 2 : t.cmp = cmp
66 2 : t.bcmp = bcmp
67 2 : for _, f := range files {
68 2 : t.Insert(f)
69 2 : }
70 2 : return t, newLevelSlice(t.Iter())
71 : }
72 :
73 2 : func (lm *LevelMetadata) insert(f *FileMetadata) error {
74 2 : if err := lm.tree.Insert(f); err != nil {
75 1 : return err
76 1 : }
77 2 : lm.totalSize += f.Size
78 2 : if f.Virtual {
79 2 : lm.NumVirtual++
80 2 : lm.VirtualSize += f.Size
81 2 : }
82 2 : return nil
83 : }
84 :
85 2 : func (lm *LevelMetadata) remove(f *FileMetadata) bool {
86 2 : lm.totalSize -= f.Size
87 2 : if f.Virtual {
88 2 : lm.NumVirtual--
89 2 : lm.VirtualSize -= f.Size
90 2 : }
91 2 : return lm.tree.Delete(f)
92 : }
93 :
94 : // Empty indicates whether there are any files in the level.
95 2 : func (lm *LevelMetadata) Empty() bool {
96 2 : return lm.tree.Count() == 0
97 2 : }
98 :
99 : // Len returns the number of files within the level.
100 2 : func (lm *LevelMetadata) Len() int {
101 2 : return lm.tree.Count()
102 2 : }
103 :
104 : // Size returns the cumulative size of all the files within the level.
105 2 : func (lm *LevelMetadata) Size() uint64 {
106 2 : return lm.totalSize
107 2 : }
108 :
109 : // Iter constructs a LevelIterator over the entire level.
110 2 : func (lm *LevelMetadata) Iter() LevelIterator {
111 2 : return LevelIterator{iter: lm.tree.Iter()}
112 2 : }
113 :
114 : // Slice constructs a slice containing the entire level.
115 2 : func (lm *LevelMetadata) Slice() LevelSlice {
116 2 : return newLevelSlice(lm.tree.Iter())
117 2 : }
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 2 : func (lm *LevelMetadata) Find(cmp base.Compare, m *FileMetadata) LevelSlice {
122 2 : iter := lm.Iter()
123 2 : 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 2 : } else {
135 2 : // For levels other than L0, UserKeyBounds in the level are non-overlapping
136 2 : // so we only need to check one file.
137 2 : if f := iter.SeekGE(cmp, m.UserKeyBounds().Start); f == m {
138 2 : return iter.Take().slice
139 2 : }
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 2 : func (lf LevelFile) Slice() LevelSlice {
153 2 : return lf.slice
154 2 : }
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 2 : func NewLevelSliceSeqSorted(files []*FileMetadata) LevelSlice {
161 2 : tr, slice := makeBTree(nil, btreeCmpSeqNum, files)
162 2 : tr.Release()
163 2 : slice.verifyInvariants()
164 2 : return slice
165 2 : }
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 2 : func NewLevelSliceKeySorted(cmp base.Compare, files []*FileMetadata) LevelSlice {
172 2 : tr, slice := makeBTree(cmp, btreeCmpSmallestKey(cmp), files)
173 2 : tr.Release()
174 2 : slice.verifyInvariants()
175 2 : return slice
176 2 : }
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 2 : func newLevelSlice(iter iterator) LevelSlice {
191 2 : s := LevelSlice{iter: iter}
192 2 : if iter.r != nil {
193 2 : s.length = iter.r.subtreeCount
194 2 : }
195 2 : s.verifyInvariants()
196 2 : 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 2 : func newBoundedLevelSlice(iter iterator, startBound, endBound *iterator) LevelSlice {
204 2 : s := LevelSlice{
205 2 : iter: iter,
206 2 : start: startBound,
207 2 : end: endBound,
208 2 : }
209 2 : if iter.valid() {
210 2 : s.length = endBound.countLeft() - startBound.countLeft()
211 2 : // NB: The +1 is a consequence of the end bound being inclusive.
212 2 : if endBound.valid() {
213 2 : s.length++
214 2 : }
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 2 : if s.length < 0 {
221 2 : s.length = 0
222 2 : }
223 : }
224 2 : s.verifyInvariants()
225 2 : 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 2 : func (ls LevelSlice) verifyInvariants() {
245 2 : if invariants.Enabled {
246 2 : i := ls.Iter()
247 2 : var length int
248 2 : for f := i.First(); f != nil; f = i.Next() {
249 2 : length++
250 2 : }
251 2 : 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 2 : func (ls LevelSlice) Each(fn func(*FileMetadata)) {
259 2 : iter := ls.Iter()
260 2 : for f := iter.First(); f != nil; f = iter.Next() {
261 2 : fn(f)
262 2 : }
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 2 : func (ls *LevelSlice) Empty() bool {
280 2 : return emptyWithBounds(ls.iter, ls.start, ls.end)
281 2 : }
282 :
283 : // Iter constructs a LevelIterator that iterates over the slice.
284 2 : func (ls *LevelSlice) Iter() LevelIterator {
285 2 : return LevelIterator{
286 2 : start: ls.start,
287 2 : end: ls.end,
288 2 : iter: ls.iter.clone(),
289 2 : }
290 2 : }
291 :
292 : // Len returns the number of files in the slice. Its runtime is constant.
293 2 : func (ls *LevelSlice) Len() int {
294 2 : return ls.length
295 2 : }
296 :
297 : // SizeSum sums the size of all files in the slice. Its runtime is linear in
298 : // the length of the slice.
299 2 : func (ls *LevelSlice) SizeSum() uint64 {
300 2 : var sum uint64
301 2 : iter := ls.Iter()
302 2 : for f := iter.First(); f != nil; f = iter.Next() {
303 2 : sum += f.Size
304 2 : }
305 2 : 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 2 : func (ls *LevelSlice) NumVirtual() uint64 {
311 2 : var n uint64
312 2 : iter := ls.Iter()
313 2 : for f := iter.First(); f != nil; f = iter.Next() {
314 2 : if f.Virtual {
315 2 : n++
316 2 : }
317 : }
318 2 : return n
319 : }
320 :
321 : // VirtualSizeSum returns the sum of the sizes of the virtual sstables in the
322 : // level.
323 2 : func (ls *LevelSlice) VirtualSizeSum() uint64 {
324 2 : var sum uint64
325 2 : iter := ls.Iter()
326 2 : for f := iter.First(); f != nil; f = iter.Next() {
327 2 : if f.Virtual {
328 2 : sum += f.Size
329 2 : }
330 : }
331 2 : 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 2 : func (ls LevelSlice) Reslice(resliceFunc func(start, end *LevelIterator)) LevelSlice {
343 2 : if ls.iter.r == nil {
344 1 : return ls
345 1 : }
346 2 : var start, end LevelIterator
347 2 : if ls.start == nil {
348 1 : start.iter = ls.iter.clone()
349 1 : start.iter.first()
350 2 : } else {
351 2 : start.iter = ls.start.clone()
352 2 : }
353 2 : if ls.end == nil {
354 1 : end.iter = ls.iter.clone()
355 1 : end.iter.last()
356 2 : } else {
357 2 : end.iter = ls.end.clone()
358 2 : }
359 2 : resliceFunc(&start, &end)
360 2 : 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 2 : func (ls LevelSlice) Overlaps(cmp Compare, bounds base.UserKeyBounds) LevelSlice {
366 2 : startIter := ls.Iter()
367 2 : startIter.SeekGE(cmp, bounds.Start)
368 2 :
369 2 : // Note: newBoundedLevelSlice uses inclusive bounds, so we need to position
370 2 : // endIter at the last overlapping file.
371 2 : endIter := ls.Iter()
372 2 : endIterFile := endIter.SeekGE(cmp, bounds.End.Key)
373 2 : // The first file that ends at/after bounds.End.Key might or might not overlap
374 2 : // the bounds; we need to check the start key.
375 2 : if endIterFile == nil || !bounds.End.IsUpperBoundFor(cmp, endIterFile.Smallest.UserKey) {
376 2 : endIter.Prev()
377 2 : }
378 2 : 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 2 : func (i *LevelIterator) Clone() LevelIterator {
450 2 : if i.iter.r == nil {
451 2 : return *i
452 2 : }
453 : // The start and end iterators are not cloned and are treated as
454 : // immutable.
455 2 : return LevelIterator{
456 2 : iter: i.iter.clone(),
457 2 : start: i.start,
458 2 : end: i.end,
459 2 : filter: i.filter,
460 2 : }
461 : }
462 :
463 2 : func (i *LevelIterator) empty() bool {
464 2 : return emptyWithBounds(i.iter, i.start, i.end)
465 2 : }
466 :
467 : // Filter clones the iterator and sets the desired KeyType as the key to filter
468 : // files on.
469 2 : func (i *LevelIterator) Filter(keyType KeyType) LevelIterator {
470 2 : l := i.Clone()
471 2 : l.filter = keyType
472 2 : return l
473 2 : }
474 :
475 2 : func emptyWithBounds(i iterator, start, end *iterator) bool {
476 2 : // If i.r is nil, the iterator was constructed from an empty btree.
477 2 : // If the end bound is before the start bound, the bounds represent an
478 2 : // empty slice of the B-Tree.
479 2 : return i.r == nil || (start != nil && end != nil && cmpIter(*end, *start) < 0)
480 2 : }
481 :
482 : // First seeks to the first file in the iterator and returns it.
483 2 : func (i *LevelIterator) First() *FileMetadata {
484 2 : if i.empty() {
485 2 : return nil
486 2 : }
487 2 : if i.start != nil {
488 2 : i.iter = i.start.clone()
489 2 : } else {
490 2 : i.iter.first()
491 2 : }
492 2 : if !i.iter.valid() {
493 2 : return nil
494 2 : }
495 2 : return i.skipFilteredForward(i.iter.cur())
496 : }
497 :
498 : // Last seeks to the last file in the iterator and returns it.
499 2 : func (i *LevelIterator) Last() *FileMetadata {
500 2 : if i.empty() {
501 2 : return nil
502 2 : }
503 2 : if i.end != nil {
504 2 : i.iter = i.end.clone()
505 2 : } else {
506 2 : i.iter.last()
507 2 : }
508 2 : if !i.iter.valid() {
509 0 : return nil
510 0 : }
511 2 : return i.skipFilteredBackward(i.iter.cur())
512 : }
513 :
514 : // Next advances the iterator to the next file and returns it.
515 2 : func (i *LevelIterator) Next() *FileMetadata {
516 2 : if i.iter.r == nil {
517 0 : return nil
518 0 : }
519 2 : 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 2 : i.iter.next()
523 2 : if !i.iter.valid() {
524 2 : return nil
525 2 : }
526 2 : return i.skipFilteredForward(i.iter.cur())
527 : }
528 :
529 : // Prev moves the iterator the previous file and returns it.
530 2 : func (i *LevelIterator) Prev() *FileMetadata {
531 2 : if i.iter.r == nil {
532 2 : return nil
533 2 : }
534 2 : 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 2 : i.iter.prev()
538 2 : if !i.iter.valid() {
539 2 : return nil
540 2 : }
541 2 : 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 2 : func (i *LevelIterator) SeekGE(cmp Compare, userKey []byte) *FileMetadata {
555 2 : if i.iter.r == nil {
556 2 : return nil
557 2 : }
558 2 : i.assertNotL0Cmp()
559 2 : m := i.seek(func(m *FileMetadata) bool {
560 2 : return m.Largest.IsUpperBoundFor(cmp, userKey)
561 2 : })
562 2 : if i.filter != KeyTypePointAndRange && m != nil {
563 2 : b, ok := m.LargestBound(i.filter)
564 2 : if !ok || !b.IsUpperBoundFor(cmp, userKey) {
565 2 : // The file does not contain any keys of desired key types
566 2 : // that are >= userKey.
567 2 : return i.Next()
568 2 : }
569 : }
570 2 : 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 2 : func (i *LevelIterator) SeekLT(cmp Compare, userKey []byte) *FileMetadata {
581 2 : if i.iter.r == nil {
582 2 : return nil
583 2 : }
584 2 : i.assertNotL0Cmp()
585 2 : i.seek(func(m *FileMetadata) bool {
586 2 : return cmp(m.Smallest.UserKey, userKey) >= 0
587 2 : })
588 2 : m := i.Prev()
589 2 : // Although i.Prev() guarantees that the current file contains keys of the
590 2 : // relevant type, it doesn't guarantee that the keys of the relevant type
591 2 : // are < userKey. For example, say that we have these two files:
592 2 : // f1: [a, f) with keys of the desired type in the range [c, d)
593 2 : // f2: [h, k)
594 2 : // and userKey is b. The seek call above will position us at f2 and Prev will
595 2 : // position us at f1.
596 2 : if i.filter != KeyTypePointAndRange && m != nil {
597 2 : b, ok := m.SmallestBound(i.filter)
598 2 : if !ok {
599 0 : panic("unreachable")
600 : }
601 2 : if cmp(b.UserKey, userKey) >= 0 {
602 2 : // This file does not contain any keys of desired key types
603 2 : // that are <= userKey.
604 2 : return i.Prev()
605 2 : }
606 : }
607 2 : 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 2 : func (i *LevelIterator) assertNotL0Cmp() {
614 2 : if invariants.Enabled {
615 2 : 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 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 : // 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 2 : func (i *LevelIterator) seek(fn func(*FileMetadata) bool) *FileMetadata {
674 2 : i.iter.seek(fn)
675 2 :
676 2 : // i.iter.seek seeked in the unbounded underlying B-Tree. If the iterator
677 2 : // has start or end bounds, we may have exceeded them. Reset to the bounds
678 2 : // if necessary.
679 2 : //
680 2 : // NB: The LevelIterator and LevelSlice semantics require that a bounded
681 2 : // LevelIterator/LevelSlice containing files x0, x1, ..., xn behave
682 2 : // identically to an unbounded LevelIterator/LevelSlice of a B-Tree
683 2 : // containing x0, x1, ..., xn. In other words, any files outside the
684 2 : // LevelIterator's bounds should not influence the iterator's behavior.
685 2 : // When seeking, this means a SeekGE that seeks beyond the end bound,
686 2 : // followed by a Prev should return the last element within bounds.
687 2 : if i.end != nil && cmpIter(i.iter, *i.end) > 0 {
688 2 : i.iter = i.end.clone()
689 2 : // Since seek(fn) positioned beyond i.end, we know there is nothing to
690 2 : // return within bounds.
691 2 : i.iter.next()
692 2 : return nil
693 2 : } else if i.start != nil && cmpIter(i.iter, *i.start) < 0 {
694 1 : i.iter = i.start.clone()
695 1 : }
696 2 : if !i.iter.valid() {
697 2 : return nil
698 2 : }
699 2 : 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 2 : func (i *LevelIterator) Take() LevelFile {
706 2 : if !i.iter.valid() ||
707 2 : (i.end != nil && cmpIter(i.iter, *i.end) > 0) ||
708 2 : (i.start != nil && cmpIter(i.iter, *i.start) < 0) {
709 0 : panic("Take called on invalid LevelIterator")
710 : }
711 2 : m := i.iter.cur()
712 2 : // LevelSlice's start and end fields are immutable and are positioned to
713 2 : // the same position for a LevelFile because they're inclusive, so we can
714 2 : // share one iterator stack between the two bounds.
715 2 : boundsIter := i.iter.clone()
716 2 : s := newBoundedLevelSlice(i.iter.clone(), &boundsIter, &boundsIter)
717 2 : return LevelFile{
718 2 : FileMetadata: m,
719 2 : slice: s,
720 2 : }
721 : }
|
