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