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