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