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