Line data Source code
1 : #ifndef STORAGE_LEVELDB_DB_SKIPLIST_H_
2 : #define STORAGE_LEVELDB_DB_SKIPLIST_H_
3 :
4 : // Copyright (c) 2011 The LevelDB Authors. All rights reserved.
5 : // Use of this source code is governed by a BSD-style license that can be
6 : // found in the LICENSE file. See the AUTHORS file for names of contributors.
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 <assert.h>
31 : #include <stdlib.h>
32 : #include "port/port.h"
33 : #include "util/arena.h"
34 : #include "util/random.h"
35 :
36 : namespace leveldb {
37 :
38 : class Arena;
39 :
40 : template<typename Key, class Comparator>
41 718 : class SkipList {
42 : private:
43 : struct Node;
44 :
45 : public:
46 : // Create a new SkipList object that will use "cmp" for comparing keys,
47 : // and will allocate memory using "*arena". Objects allocated in the arena
48 : // must remain allocated for the lifetime of the skiplist object.
49 : explicit SkipList(Comparator cmp, Arena* arena);
50 :
51 : // Insert key into the list.
52 : // REQUIRES: nothing that compares equal to key is currently in the list.
53 : void Insert(const Key& key);
54 :
55 : // Returns true iff an entry that compares equal to key is in the list.
56 : bool Contains(const Key& key) const;
57 :
58 : // Iteration over the contents of a skip list
59 : class Iterator {
60 : public:
61 : // Initialize an iterator over the specified list.
62 : // The returned iterator is not valid.
63 : explicit Iterator(const SkipList* list);
64 :
65 : // Returns true iff the iterator is positioned at a valid node.
66 : bool Valid() const;
67 :
68 : // Returns the key at the current position.
69 : // REQUIRES: Valid()
70 : const Key& key() const;
71 :
72 : // Advances to the next position.
73 : // REQUIRES: Valid()
74 : void Next();
75 :
76 : // Advances to the previous position.
77 : // REQUIRES: Valid()
78 : void Prev();
79 :
80 : // Advance to the first entry with a key >= target
81 : void Seek(const Key& target);
82 :
83 : // Position at the first entry in list.
84 : // Final state of iterator is Valid() iff list is not empty.
85 : void SeekToFirst();
86 :
87 : // Position at the last entry in list.
88 : // Final state of iterator is Valid() iff list is not empty.
89 : void SeekToLast();
90 :
91 : private:
92 : const SkipList* list_;
93 : Node* node_;
94 : // Intentionally copyable
95 : };
96 :
97 : private:
98 : enum { kMaxHeight = 12 };
99 :
100 : // Immutable after construction
101 : Comparator const compare_;
102 : Arena* const arena_; // Arena used for allocations of nodes
103 :
104 : Node* const head_;
105 :
106 : // Modified only by Insert(). Read racily by readers, but stale
107 : // values are ok.
108 : port::AtomicPointer max_height_; // Height of the entire list
109 :
110 : inline int GetMaxHeight() const {
111 : return static_cast<int>(
112 187698 : reinterpret_cast<intptr_t>(max_height_.NoBarrier_Load()));
113 : }
114 :
115 : // Read/written only by Insert().
116 : Random rnd_;
117 :
118 : Node* NewNode(const Key& key, int height);
119 : int RandomHeight();
120 27361 : bool Equal(const Key& a, const Key& b) const { return (compare_(a, b) == 0); }
121 :
122 : // Return true if key is greater than the data stored in "n"
123 : bool KeyIsAfterNode(const Key& key, Node* n) const;
124 :
125 : // Return the earliest node that comes at or after key.
126 : // Return NULL if there is no such node.
127 : //
128 : // If prev is non-NULL, fills prev[level] with pointer to previous
129 : // node at "level" for every level in [0..max_height_-1].
130 : Node* FindGreaterOrEqual(const Key& key, Node** prev) const;
131 :
132 : // Return the latest node with a key < key.
133 : // Return head_ if there is no such node.
134 : Node* FindLessThan(const Key& key) const;
135 :
136 : // Return the last node in the list.
137 : // Return head_ if list is empty.
138 : Node* FindLast() const;
139 :
140 : // No copying allowed
141 : SkipList(const SkipList&);
142 : void operator=(const SkipList&);
143 : };
144 :
145 : // Implementation details follow
146 : template<typename Key, class Comparator>
147 : struct SkipList<Key,Comparator>::Node {
148 28908 : explicit Node(const Key& k) : key(k) { }
149 :
150 : Key const key;
151 :
152 : // Accessors/mutators for links. Wrapped in methods so we can
153 : // add the appropriate barriers as necessary.
154 : Node* Next(int n) {
155 413365 : assert(n >= 0);
156 : // Use an 'acquire load' so that we observe a fully initialized
157 : // version of the returned Node.
158 430264 : return reinterpret_cast<Node*>(next_[n].Acquire_Load());
159 : }
160 : void SetNext(int n, Node* x) {
161 41489 : assert(n >= 0);
162 : // Use a 'release store' so that anybody who reads through this
163 : // pointer observes a fully initialized version of the inserted node.
164 41489 : next_[n].Release_Store(x);
165 : }
166 :
167 : // No-barrier variants that can be safely used in a few locations.
168 : Node* NoBarrier_Next(int n) {
169 37181 : assert(n >= 0);
170 37181 : return reinterpret_cast<Node*>(next_[n].NoBarrier_Load());
171 : }
172 : void NoBarrier_SetNext(int n, Node* x) {
173 37181 : assert(n >= 0);
174 37181 : next_[n].NoBarrier_Store(x);
175 : }
176 :
177 : private:
178 : // Array of length equal to the node height. next_[0] is lowest level link.
179 : port::AtomicPointer next_[1];
180 : };
181 :
182 : template<typename Key, class Comparator>
183 : typename SkipList<Key,Comparator>::Node*
184 28908 : SkipList<Key,Comparator>::NewNode(const Key& key, int height) {
185 : char* mem = arena_->AllocateAligned(
186 28908 : sizeof(Node) + sizeof(port::AtomicPointer) * (height - 1));
187 57816 : return new (mem) Node(key);
188 : }
189 :
190 : template<typename Key, class Comparator>
191 0 : inline SkipList<Key,Comparator>::Iterator::Iterator(const SkipList* list) {
192 36932 : list_ = list;
193 36932 : node_ = NULL;
194 0 : }
195 :
196 : template<typename Key, class Comparator>
197 0 : inline bool SkipList<Key,Comparator>::Iterator::Valid() const {
198 17166 : return node_ != NULL;
199 : }
200 :
201 : template<typename Key, class Comparator>
202 : inline const Key& SkipList<Key,Comparator>::Iterator::key() const {
203 33558 : assert(Valid());
204 : return node_->key;
205 : }
206 :
207 : template<typename Key, class Comparator>
208 16718 : inline void SkipList<Key,Comparator>::Iterator::Next() {
209 16718 : assert(Valid());
210 33436 : node_ = node_->Next(0);
211 16718 : }
212 :
213 : template<typename Key, class Comparator>
214 0 : inline void SkipList<Key,Comparator>::Iterator::Prev() {
215 : // Instead of using explicit "prev" links, we just search for the
216 : // last node that falls before key.
217 0 : assert(Valid());
218 0 : node_ = list_->FindLessThan(node_->key);
219 0 : if (node_ == list_->head_) {
220 0 : node_ = NULL;
221 : }
222 0 : }
223 :
224 : template<typename Key, class Comparator>
225 : inline void SkipList<Key,Comparator>::Iterator::Seek(const Key& target) {
226 36751 : node_ = list_->FindGreaterOrEqual(target, NULL);
227 : }
228 :
229 : template<typename Key, class Comparator>
230 : inline void SkipList<Key,Comparator>::Iterator::SeekToFirst() {
231 362 : node_ = list_->head_->Next(0);
232 : }
233 :
234 : template<typename Key, class Comparator>
235 0 : inline void SkipList<Key,Comparator>::Iterator::SeekToLast() {
236 0 : node_ = list_->FindLast();
237 0 : if (node_ == list_->head_) {
238 0 : node_ = NULL;
239 : }
240 0 : }
241 :
242 : template<typename Key, class Comparator>
243 28549 : int SkipList<Key,Comparator>::RandomHeight() {
244 : // Increase height with probability 1 in kBranching
245 : static const unsigned int kBranching = 4;
246 28549 : int height = 1;
247 102911 : while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {
248 8632 : height++;
249 : }
250 28549 : assert(height > 0);
251 28549 : assert(height <= kMaxHeight);
252 28549 : return height;
253 : }
254 :
255 : template<typename Key, class Comparator>
256 : bool SkipList<Key,Comparator>::KeyIsAfterNode(const Key& key, Node* n) const {
257 : // NULL n is considered infinite
258 413365 : return (n != NULL) && (compare_(n->key, key) < 0);
259 : }
260 :
261 : template<typename Key, class Comparator>
262 65300 : typename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindGreaterOrEqual(const Key& key, Node** prev)
263 : const {
264 65300 : Node* x = head_;
265 65300 : int level = GetMaxHeight() - 1;
266 : while (true) {
267 413365 : Node* next = x->Next(level);
268 413365 : if (KeyIsAfterNode(key, next)) {
269 : // Keep searching in this list
270 : x = next;
271 : } else {
272 175486 : if (prev != NULL) prev[level] = x;
273 175486 : if (level == 0) {
274 65300 : return next;
275 : } else {
276 : // Switch to next list
277 110186 : 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 == NULL || 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 == NULL) {
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 359 : SkipList<Key,Comparator>::SkipList(Comparator cmp, Arena* arena)
326 : : compare_(cmp),
327 : arena_(arena),
328 718 : head_(NewNode(0 /* any key will do */, kMaxHeight)),
329 : max_height_(reinterpret_cast<void*>(1)),
330 1795 : rnd_(0xdeadbeef) {
331 4667 : for (int i = 0; i < kMaxHeight; i++) {
332 4308 : head_->SetNext(i, NULL);
333 : }
334 359 : }
335 :
336 : template<typename Key, class Comparator>
337 28549 : 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 28549 : Node* x = FindGreaterOrEqual(key, prev);
342 :
343 : // Our data structure does not allow duplicate insertion
344 55910 : assert(x == NULL || !Equal(key, x->key));
345 :
346 28549 : int height = RandomHeight();
347 28549 : if (height > GetMaxHeight()) {
348 983 : for (int i = GetMaxHeight(); i < height; i++) {
349 983 : prev[i] = head_;
350 : }
351 : //fprintf(stderr, "Change height from %d to %d\n", max_height_, height);
352 :
353 : // It is ok to mutate max_height_ without any synchronization
354 : // with concurrent readers. A concurrent reader that observes
355 : // the new value of max_height_ will see either the old value of
356 : // new level pointers from head_ (NULL), or a new value set in
357 : // the loop below. In the former case the reader will
358 : // immediately drop to the next level since NULL sorts after all
359 : // keys. In the latter case the reader will use the new node.
360 833 : max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));
361 : }
362 :
363 28549 : x = NewNode(key, height);
364 37181 : for (int i = 0; i < height; i++) {
365 : // NoBarrier_SetNext() suffices since we will add a barrier when
366 : // we publish a pointer to "x" in prev[i].
367 74362 : x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
368 37181 : prev[i]->SetNext(i, x);
369 : }
370 28549 : }
371 :
372 : template<typename Key, class Comparator>
373 : bool SkipList<Key,Comparator>::Contains(const Key& key) const {
374 : Node* x = FindGreaterOrEqual(key, NULL);
375 : if (x != NULL && Equal(key, x->key)) {
376 : return true;
377 : } else {
378 : return false;
379 : }
380 : }
381 :
382 : } // namespace leveldb
383 :
384 : #endif // STORAGE_LEVELDB_DB_SKIPLIST_H_
|
