Line data    Source code

       1             : // Copyright 2018 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 keyspan
       6             : 
       7             : import (
       8             :         "github.com/cockroachdb/pebble/internal/base"
       9             :         "github.com/cockroachdb/pebble/internal/manifest"
      10             : )
      11             : 
      12             : // FragmentIterator defines an iterator interface over spans. The spans
      13             : // surfaced by a FragmentIterator must be non-overlapping. This is achieved by
      14             : // fragmenting spans at overlap points (see Fragmenter).
      15             : //
      16             : // A Span returned by a FragmentIterator is only valid until the next
      17             : // positioning method. Some implementations (eg, keyspan.Iter) may provide
      18             : // longer lifetimes but implementations need only guarantee stability until the
      19             : // next positioning method.
      20             : //
      21             : // If any positioning method fails to find a span, the iterator is left
      22             : // positioned at an exhausted position in the direction of iteration. For
      23             : // example, a caller than finds SeekGE(k)=nil may call Prev to move the iterator
      24             : // to the last span.
      25             : type FragmentIterator interface {
      26             :         // SeekGE moves the iterator to the first span covering a key greater than
      27             :         // or equal to the given key. This is equivalent to seeking to the first
      28             :         // span with an end key greater than the given key.
      29             :         SeekGE(key []byte) *Span
      30             : 
      31             :         // SeekLT moves the iterator to the last span covering a key less than the
      32             :         // given key. This is equivalent to seeking to the last span with a start
      33             :         // key less than the given key.
      34             :         SeekLT(key []byte) *Span
      35             : 
      36             :         // First moves the iterator to the first span.
      37             :         First() *Span
      38             : 
      39             :         // Last moves the iterator to the last span.
      40             :         Last() *Span
      41             : 
      42             :         // Next moves the iterator to the next span.
      43             :         //
      44             :         // It is valid to call Next when the iterator is positioned before the first
      45             :         // key/value pair due to either a prior call to SeekLT or Prev which
      46             :         // returned an invalid span. It is not allowed to call Next when the
      47             :         // previous call to SeekGE, SeekPrefixGE or Next returned an invalid span.
      48             :         Next() *Span
      49             : 
      50             :         // Prev moves the iterator to the previous span.
      51             :         //
      52             :         // It is valid to call Prev when the iterator is positioned after the last
      53             :         // key/value pair due to either a prior call to SeekGE or Next which
      54             :         // returned an invalid span. It is not allowed to call Prev when the
      55             :         // previous call to SeekLT or Prev returned an invalid span.
      56             :         Prev() *Span
      57             : 
      58             :         // Error returns any accumulated error.
      59             :         //
      60             :         // TODO(jackson): Lift errors into return values on the positioning methods.
      61             :         Error() error
      62             : 
      63             :         // Close closes the iterator and returns any accumulated error. Exhausting
      64             :         // the iterator is not considered to be an error. It is valid to call Close
      65             :         // multiple times. Other methods should not be called after the iterator has
      66             :         // been closed.
      67             :         Close() error
      68             : 
      69             :         // WrapChildren wraps any child iterators using the given function. The
      70             :         // function can call WrapChildren to recursively wrap an entire iterator
      71             :         // stack. Used only for debug logging.
      72             :         WrapChildren(wrap WrapFn)
      73             : }
      74             : 
      75             : // TableNewSpanIter creates a new iterator for range key spans for the given
      76             : // file.
      77             : type TableNewSpanIter func(file *manifest.FileMetadata, iterOptions SpanIterOptions) (FragmentIterator, error)
      78             : 
      79             : // SpanIterOptions is a subset of IterOptions that are necessary to instantiate
      80             : // per-sstable span iterators.
      81             : type SpanIterOptions struct {
      82             :         // RangeKeyFilters can be used to avoid scanning tables and blocks in tables
      83             :         // when iterating over range keys.
      84             :         RangeKeyFilters []base.BlockPropertyFilter
      85             : }
      86             : 
      87             : // Iter is an iterator over a set of fragmented spans.
      88             : type Iter struct {
      89             :         cmp   base.Compare
      90             :         spans []Span
      91             :         index int
      92             : }
      93             : 
      94             : // Iter implements the FragmentIterator interface.
      95             : var _ FragmentIterator = (*Iter)(nil)
      96             : 
      97             : // NewIter returns a new iterator over a set of fragmented spans.
      98           1 : func NewIter(cmp base.Compare, spans []Span) *Iter {
      99           1 :         i := &Iter{}
     100           1 :         i.Init(cmp, spans)
     101           1 :         return i
     102           1 : }
     103             : 
     104             : // Count returns the number of spans contained by Iter.
     105           1 : func (i *Iter) Count() int {
     106           1 :         return len(i.spans)
     107           1 : }
     108             : 
     109             : // Init initializes an Iter with the provided spans.
     110           1 : func (i *Iter) Init(cmp base.Compare, spans []Span) {
     111           1 :         *i = Iter{
     112           1 :                 cmp:   cmp,
     113           1 :                 spans: spans,
     114           1 :                 index: -1,
     115           1 :         }
     116           1 : }
     117             : 
     118             : // SeekGE implements FragmentIterator.SeekGE.
     119           1 : func (i *Iter) SeekGE(key []byte) *Span {
     120           1 :         // NB: manually inlined sort.Search is ~5% faster.
     121           1 :         //
     122           1 :         // Define f(j) = false iff the span i.spans[j] is strictly before `key`
     123           1 :         // (equivalently, i.spans[j].End ≤ key.)
     124           1 :         //
     125           1 :         // Define f(-1) == false and f(n) == true.
     126           1 :         // Invariant: f(index-1) == false, f(upper) == true.
     127           1 :         i.index = 0
     128           1 :         upper := len(i.spans)
     129           1 :         for i.index < upper {
     130           1 :                 h := int(uint(i.index+upper) >> 1) // avoid overflow when computing h
     131           1 :                 // i.index ≤ h < upper
     132           1 :                 if i.cmp(key, i.spans[h].End) >= 0 {
     133           1 :                         i.index = h + 1 // preserves f(i-1) == false
     134           1 :                 } else {
     135           1 :                         upper = h // preserves f(j) == true
     136           1 :                 }
     137             :         }
     138             : 
     139             :         // i.index == upper, f(i.index-1) == false, and f(upper) (= f(i.index)) ==
     140             :         // true => answer is i.index.
     141           1 :         if i.index >= len(i.spans) {
     142           1 :                 return nil
     143           1 :         }
     144           1 :         return &i.spans[i.index]
     145             : }
     146             : 
     147             : // SeekLT implements FragmentIterator.SeekLT.
     148           1 : func (i *Iter) SeekLT(key []byte) *Span {
     149           1 :         // NB: manually inlined sort.Search is ~5% faster.
     150           1 :         //
     151           1 :         // Define f(-1) == false and f(n) == true.
     152           1 :         // Invariant: f(index-1) == false, f(upper) == true.
     153           1 :         i.index = 0
     154           1 :         upper := len(i.spans)
     155           1 :         for i.index < upper {
     156           1 :                 h := int(uint(i.index+upper) >> 1) // avoid overflow when computing h
     157           1 :                 // i.index ≤ h < upper
     158           1 :                 if i.cmp(key, i.spans[h].Start) > 0 {
     159           1 :                         i.index = h + 1 // preserves f(i-1) == false
     160           1 :                 } else {
     161           1 :                         upper = h // preserves f(j) == true
     162           1 :                 }
     163             :         }
     164             :         // i.index == upper, f(i.index-1) == false, and f(upper) (= f(i.index)) ==
     165             :         // true => answer is i.index.
     166             : 
     167             :         // Since keys are strictly increasing, if i.index > 0 then i.index-1 will be
     168             :         // the largest whose key is < the key sought.
     169           1 :         i.index--
     170           1 :         if i.index < 0 {
     171           1 :                 return nil
     172           1 :         }
     173           1 :         return &i.spans[i.index]
     174             : }
     175             : 
     176             : // First implements FragmentIterator.First.
     177           1 : func (i *Iter) First() *Span {
     178           1 :         if len(i.spans) == 0 {
     179           1 :                 return nil
     180           1 :         }
     181           1 :         i.index = 0
     182           1 :         return &i.spans[i.index]
     183             : }
     184             : 
     185             : // Last implements FragmentIterator.Last.
     186           1 : func (i *Iter) Last() *Span {
     187           1 :         if len(i.spans) == 0 {
     188           1 :                 return nil
     189           1 :         }
     190           1 :         i.index = len(i.spans) - 1
     191           1 :         return &i.spans[i.index]
     192             : }
     193             : 
     194             : // Next implements FragmentIterator.Next.
     195           1 : func (i *Iter) Next() *Span {
     196           1 :         if i.index >= len(i.spans) {
     197           1 :                 return nil
     198           1 :         }
     199           1 :         i.index++
     200           1 :         if i.index >= len(i.spans) {
     201           1 :                 return nil
     202           1 :         }
     203           1 :         return &i.spans[i.index]
     204             : }
     205             : 
     206             : // Prev implements FragmentIterator.Prev.
     207           1 : func (i *Iter) Prev() *Span {
     208           1 :         if i.index < 0 {
     209           1 :                 return nil
     210           1 :         }
     211           1 :         i.index--
     212           1 :         if i.index < 0 {
     213           1 :                 return nil
     214           1 :         }
     215           1 :         return &i.spans[i.index]
     216             : }
     217             : 
     218             : // Error implements FragmentIterator.Error.
     219           1 : func (i *Iter) Error() error {
     220           1 :         return nil
     221           1 : }
     222             : 
     223             : // Close implements FragmentIterator.Close.
     224           1 : func (i *Iter) Close() error {
     225           1 :         return nil
     226           1 : }
     227             : 
     228           0 : func (i *Iter) String() string {
     229           0 :         return "fragmented-spans"
     230           0 : }
     231             : 
     232             : // WrapChildren implements FragmentIterator.
     233           1 : func (i *Iter) WrapChildren(wrap WrapFn) {}