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 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 inline int GetMaxHeight() const {
105 return max_height_.load(std::memory_order_relaxed);
106 }
107 108 Node* NewNode(const Key& key, int height);
109 int RandomHeight();
110 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 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 Node* Next(int n) {
154 assert(n >= 0);
155 // Use an 'acquire load' so that we observe a fully initialized
156 // version of the returned Node.
157 return next_[n].load(std::memory_order_acquire);
158 }
159 void SetNext(int n, Node* x) {
160 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 next_[n].store(x, std::memory_order_release);
164 }
165 166 // No-barrier variants that can be safely used in a few locations.
167 Node* NoBarrier_Next(int n) {
168 assert(n >= 0);
169 return next_[n].load(std::memory_order_relaxed);
170 }
171 void NoBarrier_SetNext(int n, Node* x) {
172 assert(n >= 0);
173 next_[n].store(x, std::memory_order_relaxed);
174 }
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 typename SkipList<Key, Comparator>::Node* SkipList<Key, Comparator>::NewNode(
183 const Key& key, int height) {
184 char* const node_memory = arena_->AllocateAligned(
185 sizeof(Node) + sizeof(std::atomic<Node*>) * (height - 1));
186 return new (node_memory) Node(key);
187 }
188 189 template <typename Key, class Comparator>
190 inline SkipList<Key, Comparator>::Iterator::Iterator(const SkipList* list) {
191 list_ = list;
192 node_ = nullptr;
193 }
194 195 template <typename Key, class Comparator>
196 inline bool SkipList<Key, Comparator>::Iterator::Valid() const {
197 return node_ != nullptr;
198 }
199 200 template <typename Key, class Comparator>
201 inline const Key& SkipList<Key, Comparator>::Iterator::key() const {
202 assert(Valid());
203 return node_->key;
204 }
205 206 template <typename Key, class Comparator>
207 inline void SkipList<Key, Comparator>::Iterator::Next() {
208 assert(Valid());
209 node_ = node_->Next(0);
210 }
211 212 template <typename Key, class Comparator>
213 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 assert(Valid());
217 node_ = list_->FindLessThan(node_->key);
218 if (node_ == list_->head_) {
219 node_ = nullptr;
220 }
221 }
222 223 template <typename Key, class Comparator>
224 inline void SkipList<Key, Comparator>::Iterator::Seek(const Key& target) {
225 node_ = list_->FindGreaterOrEqual(target, nullptr);
226 }
227 228 template <typename Key, class Comparator>
229 inline void SkipList<Key, Comparator>::Iterator::SeekToFirst() {
230 node_ = list_->head_->Next(0);
231 }
232 233 template <typename Key, class Comparator>
234 inline void SkipList<Key, Comparator>::Iterator::SeekToLast() {
235 node_ = list_->FindLast();
236 if (node_ == list_->head_) {
237 node_ = nullptr;
238 }
239 }
240 241 template <typename Key, class Comparator>
242 int SkipList<Key, Comparator>::RandomHeight() {
243 // Increase height with probability 1 in kBranching
244 static const unsigned int kBranching = 4;
245 int height = 1;
246 while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {
247 height++;
248 }
249 assert(height > 0);
250 assert(height <= kMaxHeight);
251 return height;
252 }
253 254 template <typename Key, class Comparator>
255 bool SkipList<Key, Comparator>::KeyIsAfterNode(const Key& key, Node* n) const {
256 // null n is considered infinite
257 return (n != nullptr) && (compare_(n->key, key) < 0);
258 }
259 260 template <typename Key, class Comparator>
261 typename SkipList<Key, Comparator>::Node*
262 SkipList<Key, Comparator>::FindGreaterOrEqual(const Key& key,
263 Node** prev) const {
264 Node* x = head_;
265 int level = GetMaxHeight() - 1;
266 while (true) {
267 Node* next = x->Next(level);
268 if (KeyIsAfterNode(key, next)) {
269 // Keep searching in this list
270 x = next;
271 } else {
272 if (prev != nullptr) prev[level] = x;
273 if (level == 0) {
274 return next;
275 } else {
276 // Switch to next list
277 level--;
278 }
279 }
280 }
281 }
282 283 template <typename Key, class Comparator>
284 typename SkipList<Key, Comparator>::Node*
285 SkipList<Key, Comparator>::FindLessThan(const Key& key) const {
286 Node* x = head_;
287 int level = GetMaxHeight() - 1;
288 while (true) {
289 assert(x == head_ || compare_(x->key, key) < 0);
290 Node* next = x->Next(level);
291 if (next == nullptr || compare_(next->key, key) >= 0) {
292 if (level == 0) {
293 return x;
294 } else {
295 // Switch to next list
296 level--;
297 }
298 } else {
299 x = next;
300 }
301 }
302 }
303 304 template <typename Key, class Comparator>
305 typename SkipList<Key, Comparator>::Node* SkipList<Key, Comparator>::FindLast()
306 const {
307 Node* x = head_;
308 int level = GetMaxHeight() - 1;
309 while (true) {
310 Node* next = x->Next(level);
311 if (next == nullptr) {
312 if (level == 0) {
313 return x;
314 } else {
315 // Switch to next list
316 level--;
317 }
318 } else {
319 x = next;
320 }
321 }
322 }
323 324 template <typename Key, class Comparator>
325 SkipList<Key, Comparator>::SkipList(Comparator cmp, Arena* arena)
326 : compare_(cmp),
327 arena_(arena),
328 head_(NewNode(0 /* any key will do */, kMaxHeight)),
329 max_height_(1),
330 rnd_(0xdeadbeef) {
331 for (int i = 0; i < kMaxHeight; i++) {
332 head_->SetNext(i, nullptr);
333 }
334 }
335 336 template <typename Key, class Comparator>
337 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 Node* x = FindGreaterOrEqual(key, prev);
342 343 // Our data structure does not allow duplicate insertion
344 assert(x == nullptr || !Equal(key, x->key));
345 346 int height = RandomHeight();
347 if (height > GetMaxHeight()) {
348 for (int i = GetMaxHeight(); i < height; i++) {
349 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 max_height_.store(height, std::memory_order_relaxed);
359 }
360 361 x = NewNode(key, height);
362 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 x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
366 prev[i]->SetNext(i, x);
367 }
368 }
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_
383