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 GetMaxHeight()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(); Equal(const Key & a,const Key & b)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