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