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