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