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