Branch data Line data Source code
1 : : // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
2 : : // Use of this source code is governed by a BSD-style license that can be
3 : : // found in the LICENSE file. See the AUTHORS file for names of contributors.
4 : :
5 : : #ifndef STORAGE_LEVELDB_DB_SKIPLIST_H_
6 : : #define STORAGE_LEVELDB_DB_SKIPLIST_H_
7 : :
8 : : // Thread safety
9 : : // -------------
10 : : //
11 : : // Writes require external synchronization, most likely a mutex.
12 : : // Reads require a guarantee that the SkipList will not be destroyed
13 : : // while the read is in progress. Apart from that, reads progress
14 : : // without any internal locking or synchronization.
15 : : //
16 : : // Invariants:
17 : : //
18 : : // (1) Allocated nodes are never deleted until the SkipList is
19 : : // destroyed. This is trivially guaranteed by the code since we
20 : : // never delete any skip list nodes.
21 : : //
22 : : // (2) The contents of a Node except for the next/prev pointers are
23 : : // immutable after the Node has been linked into the SkipList.
24 : : // Only Insert() modifies the list, and it is careful to initialize
25 : : // a node and use release-stores to publish the nodes in one or
26 : : // more lists.
27 : : //
28 : : // ... prev vs. next pointer ordering ...
29 : :
30 : : #include <atomic>
31 : : #include <cassert>
32 : : #include <cstdlib>
33 : :
34 : : #include "util/arena.h"
35 : : #include "util/random.h"
36 : :
37 : : namespace leveldb {
38 : :
39 : : class Arena;
40 : :
41 : : template <typename Key, class Comparator>
42 : 551 : class SkipList {
43 : : private:
44 : : struct Node;
45 : :
46 : : public:
47 : : // Create a new SkipList object that will use "cmp" for comparing keys,
48 : : // and will allocate memory using "*arena". Objects allocated in the arena
49 : : // must remain allocated for the lifetime of the skiplist object.
50 : : explicit SkipList(Comparator cmp, Arena* arena);
51 : :
52 : : SkipList(const SkipList&) = delete;
53 : : SkipList& operator=(const SkipList&) = delete;
54 : :
55 : : // Insert key into the list.
56 : : // REQUIRES: nothing that compares equal to key is currently in the list.
57 : : void Insert(const Key& key);
58 : :
59 : : // Returns true iff an entry that compares equal to key is in the list.
60 : : bool Contains(const Key& key) const;
61 : :
62 : : // Iteration over the contents of a skip list
63 : : class Iterator {
64 : : public:
65 : : // Initialize an iterator over the specified list.
66 : : // The returned iterator is not valid.
67 : : explicit Iterator(const SkipList* list);
68 : :
69 : : // Returns true iff the iterator is positioned at a valid node.
70 : : bool Valid() const;
71 : :
72 : : // Returns the key at the current position.
73 : : // REQUIRES: Valid()
74 : : const Key& key() const;
75 : :
76 : : // Advances to the next position.
77 : : // REQUIRES: Valid()
78 : : void Next();
79 : :
80 : : // Advances to the previous position.
81 : : // REQUIRES: Valid()
82 : : void Prev();
83 : :
84 : : // Advance to the first entry with a key >= target
85 : : void Seek(const Key& target);
86 : :
87 : : // Position at the first entry in list.
88 : : // Final state of iterator is Valid() iff list is not empty.
89 : : void SeekToFirst();
90 : :
91 : : // Position at the last entry in list.
92 : : // Final state of iterator is Valid() iff list is not empty.
93 : : void SeekToLast();
94 : :
95 : : private:
96 : : const SkipList* list_;
97 : : Node* node_;
98 : : // Intentionally copyable
99 : : };
100 : :
101 : : private:
102 : : enum { kMaxHeight = 12 };
103 : :
104 : 4932345 : inline int GetMaxHeight() const {
105 : 537 : return max_height_.load(std::memory_order_relaxed);
106 : : }
107 : :
108 : : Node* NewNode(const Key& key, int height);
109 : : int RandomHeight();
110 : 100918 : bool Equal(const Key& a, const Key& b) const { return (compare_(a, b) == 0); }
111 : :
112 : : // Return true if key is greater than the data stored in "n"
113 : : bool KeyIsAfterNode(const Key& key, Node* n) const;
114 : :
115 : : // Return the earliest node that comes at or after key.
116 : : // Return nullptr if there is no such node.
117 : : //
118 : : // If prev is non-null, fills prev[level] with pointer to previous
119 : : // node at "level" for every level in [0..max_height_-1].
120 : : Node* FindGreaterOrEqual(const Key& key, Node** prev) const;
121 : :
122 : : // Return the latest node with a key < key.
123 : : // Return head_ if there is no such node.
124 : : Node* FindLessThan(const Key& key) const;
125 : :
126 : : // Return the last node in the list.
127 : : // Return head_ if list is empty.
128 : : Node* FindLast() const;
129 : :
130 : : // Immutable after construction
131 : : Comparator const compare_;
132 : : Arena* const arena_; // Arena used for allocations of nodes
133 : :
134 : : Node* const head_;
135 : :
136 : : // Modified only by Insert(). Read racily by readers, but stale
137 : : // values are ok.
138 : : std::atomic<int> max_height_; // Height of the entire list
139 : :
140 : : // Read/written only by Insert().
141 : : Random rnd_;
142 : : };
143 : :
144 : : // Implementation details follow
145 : : template <typename Key, class Comparator>
146 : : struct SkipList<Key, Comparator>::Node {
147 : 102688 : explicit Node(const Key& k) : key(k) {}
148 : :
149 : : Key const key;
150 : :
151 : : // Accessors/mutators for links. Wrapped in methods so we can
152 : : // add the appropriate barriers as necessary.
153 : 115955107 : Node* Next(int n) {
154 [ - + ]: 115922904 : assert(n >= 0);
155 : : // Use an 'acquire load' so that we observe a fully initialized
156 : : // version of the returned Node.
157 : 115955107 : return next_[n].load(std::memory_order_acquire);
158 : : }
159 : 142929 : void SetNext(int n, Node* x) {
160 [ - + ]: 142929 : assert(n >= 0);
161 : : // Use a 'release store' so that anybody who reads through this
162 : : // pointer observes a fully initialized version of the inserted node.
163 : 142929 : next_[n].store(x, std::memory_order_release);
164 : 142929 : }
165 : :
166 : : // No-barrier variants that can be safely used in a few locations.
167 : 136317 : Node* NoBarrier_Next(int n) {
168 [ - + ]: 136317 : assert(n >= 0);
169 : 136317 : return next_[n].load(std::memory_order_relaxed);
170 : : }
171 : 136317 : void NoBarrier_SetNext(int n, Node* x) {
172 [ - + ]: 136317 : assert(n >= 0);
173 : 136317 : next_[n].store(x, std::memory_order_relaxed);
174 : 136317 : }
175 : :
176 : : private:
177 : : // Array of length equal to the node height. next_[0] is lowest level link.
178 : : std::atomic<Node*> next_[1];
179 : : };
180 : :
181 : : template <typename Key, class Comparator>
182 : 102688 : typename SkipList<Key, Comparator>::Node* SkipList<Key, Comparator>::NewNode(
183 : : const Key& key, int height) {
184 : 205376 : char* const node_memory = arena_->AllocateAligned(
185 : 102688 : sizeof(Node) + sizeof(std::atomic<Node*>) * (height - 1));
186 : 102688 : return new (node_memory) Node(key);
187 : : }
188 : :
189 : : template <typename Key, class Comparator>
190 : 4727809 : inline SkipList<Key, Comparator>::Iterator::Iterator(const SkipList* list) {
191 : 4727809 : list_ = list;
192 : 4727809 : node_ = nullptr;
193 : : }
194 : :
195 : : template <typename Key, class Comparator>
196 : 4836525 : inline bool SkipList<Key, Comparator>::Iterator::Valid() const {
197 : 4836525 : return node_ != nullptr;
198 : : }
199 : :
200 : : template <typename Key, class Comparator>
201 : 4767423 : inline const Key& SkipList<Key, Comparator>::Iterator::key() const {
202 [ - + ]: 4767423 : assert(Valid());
203 : 4767423 : return node_->key;
204 : : }
205 : :
206 : : template <typename Key, class Comparator>
207 : 31926 : inline void SkipList<Key, Comparator>::Iterator::Next() {
208 [ - + ]: 31926 : assert(Valid());
209 : 31926 : node_ = node_->Next(0);
210 : 31926 : }
211 : :
212 : : template <typename Key, class Comparator>
213 : 0 : inline void SkipList<Key, Comparator>::Iterator::Prev() {
214 : : // Instead of using explicit "prev" links, we just search for the
215 : : // last node that falls before key.
216 [ # # ]: 0 : assert(Valid());
217 : 0 : node_ = list_->FindLessThan(node_->key);
218 [ # # ]: 0 : if (node_ == list_->head_) {
219 : 0 : node_ = nullptr;
220 : : }
221 : 0 : }
222 : :
223 : : template <typename Key, class Comparator>
224 : 4727534 : inline void SkipList<Key, Comparator>::Iterator::Seek(const Key& target) {
225 [ + + ]: 4727534 : node_ = list_->FindGreaterOrEqual(target, nullptr);
226 : : }
227 : :
228 : : template <typename Key, class Comparator>
229 : 277 : inline void SkipList<Key, Comparator>::Iterator::SeekToFirst() {
230 : 277 : node_ = list_->head_->Next(0);
231 : 277 : }
232 : :
233 : : template <typename Key, class Comparator>
234 : 0 : inline void SkipList<Key, Comparator>::Iterator::SeekToLast() {
235 : 0 : node_ = list_->FindLast();
236 [ # # ]: 0 : if (node_ == list_->head_) {
237 : 0 : node_ = nullptr;
238 : : }
239 : 0 : }
240 : :
241 : : template <typename Key, class Comparator>
242 : 102137 : int SkipList<Key, Comparator>::RandomHeight() {
243 : : // Increase height with probability 1 in kBranching
244 : : static const unsigned int kBranching = 4;
245 : 102137 : int height = 1;
246 [ + - - + : 136317 : while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {
+ + ]
247 : 34180 : height++;
248 : : }
249 [ - + ]: 102137 : assert(height > 0);
250 [ - + ]: 102137 : assert(height <= kMaxHeight);
251 : 102137 : return height;
252 : : }
253 : :
254 : : template <typename Key, class Comparator>
255 : 115922904 : bool SkipList<Key, Comparator>::KeyIsAfterNode(const Key& key, Node* n) const {
256 : : // null n is considered infinite
257 [ + + + + ]: 115922904 : return (n != nullptr) && (compare_(n->key, key) < 0);
258 : : }
259 : :
260 : : template <typename Key, class Comparator>
261 : : typename SkipList<Key, Comparator>::Node*
262 : 4829671 : SkipList<Key, Comparator>::FindGreaterOrEqual(const Key& key,
263 : : Node** prev) const {
264 : 4829671 : Node* x = head_;
265 : 4829671 : int level = GetMaxHeight() - 1;
266 : : while (true) {
267 : 115922904 : Node* next = x->Next(level);
268 [ + + ]: 115922904 : if (KeyIsAfterNode(key, next)) {
269 : : // Keep searching in this list
270 : : x = next;
271 : : } else {
272 [ + + ]: 37728001 : if (prev != nullptr) prev[level] = x;
273 [ + + ]: 37728001 : if (level == 0) {
274 : 4829671 : return next;
275 : : } else {
276 : : // Switch to next list
277 : 32898330 : level--;
278 : : }
279 : : }
280 : : }
281 : : }
282 : :
283 : : template <typename Key, class Comparator>
284 : : typename SkipList<Key, Comparator>::Node*
285 : 0 : SkipList<Key, Comparator>::FindLessThan(const Key& key) const {
286 : 0 : Node* x = head_;
287 : 0 : int level = GetMaxHeight() - 1;
288 : : while (true) {
289 [ # # # # ]: 0 : assert(x == head_ || compare_(x->key, key) < 0);
290 : 0 : Node* next = x->Next(level);
291 [ # # # # ]: 0 : if (next == nullptr || compare_(next->key, key) >= 0) {
292 [ # # ]: 0 : if (level == 0) {
293 : 0 : return x;
294 : : } else {
295 : : // Switch to next list
296 : 0 : level--;
297 : : }
298 : : } else {
299 : : x = next;
300 : : }
301 : : }
302 : : }
303 : :
304 : : template <typename Key, class Comparator>
305 : 0 : typename SkipList<Key, Comparator>::Node* SkipList<Key, Comparator>::FindLast()
306 : : const {
307 : 0 : Node* x = head_;
308 : 0 : int level = GetMaxHeight() - 1;
309 : : while (true) {
310 : 0 : Node* next = x->Next(level);
311 [ # # ]: 0 : if (next == nullptr) {
312 [ # # ]: 0 : if (level == 0) {
313 : 0 : return x;
314 : : } else {
315 : : // Switch to next list
316 : 0 : level--;
317 : : }
318 : : } else {
319 : : x = next;
320 : : }
321 : : }
322 : : }
323 : :
324 : : template <typename Key, class Comparator>
325 : 551 : SkipList<Key, Comparator>::SkipList(Comparator cmp, Arena* arena)
326 [ + - ]: 551 : : compare_(cmp),
327 : 551 : arena_(arena),
328 [ + - ]: 551 : head_(NewNode(0 /* any key will do */, kMaxHeight)),
329 : 551 : max_height_(1),
330 : 551 : rnd_(0xdeadbeef) {
331 [ + + ]: 7163 : for (int i = 0; i < kMaxHeight; i++) {
332 : 6612 : head_->SetNext(i, nullptr);
333 : : }
334 : 551 : }
335 : :
336 : : template <typename Key, class Comparator>
337 : 102137 : void SkipList<Key, Comparator>::Insert(const Key& key) {
338 : : // TODO(opt): We can use a barrier-free variant of FindGreaterOrEqual()
339 : : // here since Insert() is externally synchronized.
340 : : Node* prev[kMaxHeight];
341 : 102137 : Node* x = FindGreaterOrEqual(key, prev);
342 : :
343 : : // Our data structure does not allow duplicate insertion
344 [ + + - + ]: 102137 : assert(x == nullptr || !Equal(key, x->key));
345 : :
346 [ + + ]: 102137 : int height = RandomHeight();
347 [ + + ]: 102137 : if (height > GetMaxHeight()) {
348 [ + + ]: 1129 : for (int i = GetMaxHeight(); i < height; i++) {
349 : 592 : prev[i] = head_;
350 : : }
351 : : // It is ok to mutate max_height_ without any synchronization
352 : : // with concurrent readers. A concurrent reader that observes
353 : : // the new value of max_height_ will see either the old value of
354 : : // new level pointers from head_ (nullptr), or a new value set in
355 : : // the loop below. In the former case the reader will
356 : : // immediately drop to the next level since nullptr sorts after all
357 : : // keys. In the latter case the reader will use the new node.
358 : 537 : max_height_.store(height, std::memory_order_relaxed);
359 : : }
360 : :
361 : 102137 : x = NewNode(key, height);
362 [ + + ]: 238454 : for (int i = 0; i < height; i++) {
363 : : // NoBarrier_SetNext() suffices since we will add a barrier when
364 : : // we publish a pointer to "x" in prev[i].
365 : 136317 : x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
366 : 136317 : prev[i]->SetNext(i, x);
367 : : }
368 : 102137 : }
369 : :
370 : : template <typename Key, class Comparator>
371 : : bool SkipList<Key, Comparator>::Contains(const Key& key) const {
372 : : Node* x = FindGreaterOrEqual(key, nullptr);
373 : : if (x != nullptr && Equal(key, x->key)) {
374 : : return true;
375 : : } else {
376 : : return false;
377 : : }
378 : : }
379 : :
380 : : } // namespace leveldb
381 : :
382 : : #endif // STORAGE_LEVELDB_DB_SKIPLIST_H_
|
