Line data Source code
1 : /*
2 : * Copyright 2017 Dgraph Labs, Inc. and Contributors
3 : * Modifications copyright (C) 2017 Andy Kimball and Contributors
4 : *
5 : * Licensed under the Apache License, Version 2.0 (the "License");
6 : * you may not use this file except in compliance with the License.
7 : * You may obtain a copy of the License at
8 : *
9 : * http://www.apache.org/licenses/LICENSE-2.0
10 : *
11 : * Unless required by applicable law or agreed to in writing, software
12 : * distributed under the License is distributed on an "AS IS" BASIS,
13 : * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 : * See the License for the specific language governing permissions and
15 : * limitations under the License.
16 : */
17 :
18 : package arenaskl
19 :
20 : import (
21 : "context"
22 : "sync"
23 :
24 : "github.com/cockroachdb/pebble/internal/base"
25 : "github.com/cockroachdb/pebble/internal/treeprinter"
26 : )
27 :
28 : type splice struct {
29 : prev *node
30 : next *node
31 : }
32 :
33 2 : func (s *splice) init(prev, next *node) {
34 2 : s.prev = prev
35 2 : s.next = next
36 2 : }
37 :
38 : // Iterator is an iterator over the skiplist object. Use Skiplist.NewIter
39 : // to construct an iterator. The current state of the iterator can be cloned by
40 : // simply value copying the struct. All iterator methods are thread-safe.
41 : type Iterator struct {
42 : list *Skiplist
43 : nd *node
44 : kv base.InternalKV
45 : lower []byte
46 : upper []byte
47 : // {lower|upper}Node are lazily populated with an arbitrary node that is
48 : // beyond the lower or upper bound respectively. Note the node is
49 : // "arbitrary" because it may not be the first node that exceeds the bound.
50 : // Concurrent insertions into the skiplist may introduce new nodes with keys
51 : // that exceed the bounds but are closer to the bounds than the current
52 : // values of [lower|upper]Node.
53 : //
54 : // Once populated, [lower|upper]Node may be used to detect when iteration
55 : // has reached a bound without performing a key comparison. This may be
56 : // beneficial when performing repeated SeekGEs with TrySeekUsingNext and an
57 : // upper bound set. Once the upper bound has been met, no additional key
58 : // comparisons are necessary.
59 : lowerNode *node
60 : upperNode *node
61 : }
62 :
63 : // Iterator implements the base.InternalIterator interface.
64 : var _ base.InternalIterator = (*Iterator)(nil)
65 :
66 : var iterPool = sync.Pool{
67 2 : New: func() interface{} {
68 2 : return &Iterator{}
69 2 : },
70 : }
71 :
72 : // Close resets the iterator.
73 2 : func (it *Iterator) Close() error {
74 2 : *it = Iterator{}
75 2 : iterPool.Put(it)
76 2 : return nil
77 2 : }
78 :
79 2 : func (it *Iterator) String() string {
80 2 : return "memtable"
81 2 : }
82 :
83 : // Error returns any accumulated error.
84 2 : func (it *Iterator) Error() error {
85 2 : return nil
86 2 : }
87 :
88 : // SeekGE moves the iterator to the first entry whose key is greater than or
89 : // equal to the given key. Returns the KV pair if the iterator is pointing at a
90 : // valid entry, and nil otherwise. Note that SeekGE only checks the upper bound.
91 : // It is up to the caller to ensure that key is greater than or equal to the
92 : // lower bound.
93 2 : func (it *Iterator) SeekGE(key []byte, flags base.SeekGEFlags) *base.InternalKV {
94 2 : if flags.TrySeekUsingNext() {
95 2 : if it.nd == it.list.tail || it.nd == it.upperNode {
96 2 : // Iterator is done.
97 2 : return nil
98 2 : }
99 2 : less := it.list.cmp(it.kv.K.UserKey, key) < 0
100 2 : // Arbitrary constant. By measuring the seek cost as a function of the
101 2 : // number of elements in the skip list, and fitting to a model, we
102 2 : // could adjust the number of nexts based on the current size of the
103 2 : // skip list.
104 2 : const numNexts = 5
105 2 : kv := &it.kv
106 2 : for i := 0; less && i < numNexts; i++ {
107 2 : if kv = it.Next(); kv == nil {
108 2 : // Iterator is done.
109 2 : return nil
110 2 : }
111 2 : less = it.list.cmp(kv.K.UserKey, key) < 0
112 : }
113 2 : if !less {
114 2 : return kv
115 2 : }
116 : }
117 2 : _, it.nd, _ = it.seekForBaseSplice(key)
118 2 : if it.nd == it.list.tail || it.nd == it.upperNode {
119 2 : return nil
120 2 : }
121 2 : it.decodeKey()
122 2 : if it.upper != nil && it.list.cmp(it.upper, it.kv.K.UserKey) <= 0 {
123 2 : it.upperNode = it.nd
124 2 : return nil
125 2 : }
126 2 : it.kv.V = base.MakeInPlaceValue(it.value())
127 2 : return &it.kv
128 : }
129 :
130 : // SeekPrefixGE moves the iterator to the first entry whose key is greater than
131 : // or equal to the given key. This method is equivalent to SeekGE and is
132 : // provided so that an arenaskl.Iterator implements the
133 : // internal/base.InternalIterator interface.
134 2 : func (it *Iterator) SeekPrefixGE(prefix, key []byte, flags base.SeekGEFlags) *base.InternalKV {
135 2 : return it.SeekGE(key, flags)
136 2 : }
137 :
138 : // SeekLT moves the iterator to the last entry whose key is less than the given
139 : // key. Returns the KV pair if the iterator is pointing at a valid entry, and
140 : // nil otherwise. Note that SeekLT only checks the lower bound. It is up to the
141 : // caller to ensure that key is less than the upper bound.
142 2 : func (it *Iterator) SeekLT(key []byte, flags base.SeekLTFlags) *base.InternalKV {
143 2 : // NB: the top-level Iterator has already adjusted key based on
144 2 : // the upper-bound.
145 2 : it.nd, _, _ = it.seekForBaseSplice(key)
146 2 : if it.nd == it.list.head || it.nd == it.lowerNode {
147 2 : return nil
148 2 : }
149 2 : it.decodeKey()
150 2 : if it.lower != nil && it.list.cmp(it.lower, it.kv.K.UserKey) > 0 {
151 2 : it.lowerNode = it.nd
152 2 : return nil
153 2 : }
154 2 : it.kv.V = base.MakeInPlaceValue(it.value())
155 2 : return &it.kv
156 : }
157 :
158 : // First seeks position at the first entry in list. Returns the KV pair if the
159 : // iterator is pointing at a valid entry, and nil otherwise. Note that First
160 : // only checks the upper bound. It is up to the caller to ensure that key is
161 : // greater than or equal to the lower bound (e.g. via a call to SeekGE(lower)).
162 2 : func (it *Iterator) First() *base.InternalKV {
163 2 : it.nd = it.list.getNext(it.list.head, 0)
164 2 : if it.nd == it.list.tail || it.nd == it.upperNode {
165 2 : return nil
166 2 : }
167 2 : it.decodeKey()
168 2 : if it.upper != nil && it.list.cmp(it.upper, it.kv.K.UserKey) <= 0 {
169 2 : it.upperNode = it.nd
170 2 : return nil
171 2 : }
172 2 : it.kv.V = base.MakeInPlaceValue(it.value())
173 2 : return &it.kv
174 : }
175 :
176 : // Last seeks position at the last entry in list. Returns the KV pair if the
177 : // iterator is pointing at a valid entry, and nil otherwise. Note that Last only
178 : // checks the lower bound. It is up to the caller to ensure that key is less
179 : // than the upper bound (e.g. via a call to SeekLT(upper)).
180 2 : func (it *Iterator) Last() *base.InternalKV {
181 2 : it.nd = it.list.getPrev(it.list.tail, 0)
182 2 : if it.nd == it.list.head || it.nd == it.lowerNode {
183 2 : return nil
184 2 : }
185 2 : it.decodeKey()
186 2 : if it.lower != nil && it.list.cmp(it.lower, it.kv.K.UserKey) > 0 {
187 0 : it.lowerNode = it.nd
188 0 : return nil
189 0 : }
190 2 : it.kv.V = base.MakeInPlaceValue(it.value())
191 2 : return &it.kv
192 : }
193 :
194 : // Next advances to the next position. Returns the KV pair if the iterator is
195 : // pointing at a valid entry, and nil otherwise.
196 : // Note: flushIterator.Next mirrors the implementation of Iterator.Next
197 : // due to performance. Keep the two in sync.
198 2 : func (it *Iterator) Next() *base.InternalKV {
199 2 : it.nd = it.list.getNext(it.nd, 0)
200 2 : if it.nd == it.list.tail || it.nd == it.upperNode {
201 2 : return nil
202 2 : }
203 2 : it.decodeKey()
204 2 : if it.upper != nil && it.list.cmp(it.upper, it.kv.K.UserKey) <= 0 {
205 2 : it.upperNode = it.nd
206 2 : return nil
207 2 : }
208 2 : it.kv.V = base.MakeInPlaceValue(it.value())
209 2 : return &it.kv
210 : }
211 :
212 : // NextPrefix advances to the next position with a new prefix. Returns the KV
213 : // pair if the iterator is pointing at a valid entry and nil otherwise.
214 2 : func (it *Iterator) NextPrefix(succKey []byte) *base.InternalKV {
215 2 : return it.SeekGE(succKey, base.SeekGEFlagsNone.EnableTrySeekUsingNext())
216 2 : }
217 :
218 : // Prev moves to the previous position. Returns the KV pair if the iterator is
219 : // pointing at a valid entry and nil otherwise.
220 2 : func (it *Iterator) Prev() *base.InternalKV {
221 2 : it.nd = it.list.getPrev(it.nd, 0)
222 2 : if it.nd == it.list.head || it.nd == it.lowerNode {
223 2 : return nil
224 2 : }
225 2 : it.decodeKey()
226 2 : if it.lower != nil && it.list.cmp(it.lower, it.kv.K.UserKey) > 0 {
227 2 : it.lowerNode = it.nd
228 2 : return nil
229 2 : }
230 2 : it.kv.V = base.MakeInPlaceValue(it.value())
231 2 : return &it.kv
232 : }
233 :
234 : // value returns the value at the current position.
235 2 : func (it *Iterator) value() []byte {
236 2 : return it.nd.getValue(it.list.arena)
237 2 : }
238 :
239 : // SetBounds sets the lower and upper bounds for the iterator. Note that the
240 : // result of Next and Prev will be undefined until the iterator has been
241 : // repositioned with SeekGE, SeekPrefixGE, SeekLT, First, or Last.
242 2 : func (it *Iterator) SetBounds(lower, upper []byte) {
243 2 : it.lower = lower
244 2 : it.upper = upper
245 2 : it.lowerNode = nil
246 2 : it.upperNode = nil
247 2 : }
248 :
249 : // SetContext implements base.InternalIterator.
250 0 : func (it *Iterator) SetContext(_ context.Context) {}
251 :
252 : // DebugTree is part of the InternalIterator interface.
253 0 : func (it *Iterator) DebugTree(tp treeprinter.Node) {
254 0 : tp.Childf("%T(%p)", it, it)
255 0 : }
256 :
257 2 : func (it *Iterator) decodeKey() {
258 2 : it.kv.K.UserKey = it.list.arena.getBytes(it.nd.keyOffset, it.nd.keySize)
259 2 : it.kv.K.Trailer = it.nd.keyTrailer
260 2 : }
261 :
262 2 : func (it *Iterator) seekForBaseSplice(key []byte) (prev, next *node, found bool) {
263 2 : ikey := base.MakeSearchKey(key)
264 2 : level := int(it.list.Height() - 1)
265 2 :
266 2 : prev = it.list.head
267 2 : for {
268 2 : prev, next, found = it.list.findSpliceForLevel(ikey, level, prev)
269 2 :
270 2 : if found {
271 0 : if level != 0 {
272 0 : // next is pointing at the target node, but we need to find previous on
273 0 : // the bottom level.
274 0 : prev = it.list.getPrev(next, 0)
275 0 : }
276 0 : break
277 : }
278 :
279 2 : if level == 0 {
280 2 : break
281 : }
282 :
283 2 : level--
284 : }
285 :
286 2 : return
287 : }
|
