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 : }