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