src/leveldb/db/skiplist.h

   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
  33 namespace leveldb {
  34
  35 class Arena;
  36
  37 template<typename Key, class Comparator>
  38 class 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
 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 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
 179 template<typename Key, class Comparator>
 180 typename SkipList<Key,Comparator>::Node*
 181 SkipList<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
 187 template<typename Key, class Comparator>
 188 inline SkipList<Key,Comparator>::Iterator::Iterator(const SkipList* list) {
 189   list_ = list;
 190   node_ = NULL;
 191 }
 192
 193 template<typename Key, class Comparator>
 194 inline bool SkipList<Key,Comparator>::Iterator::Valid() const {
 195   return node_ != NULL;
 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_ = NULL;
 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, NULL);
 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_ = NULL;
 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_.Next() % kBranching) == 0)) {
 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 != NULL) && (compare_(n->key, key) < 0);
 256 }
 257
 258 template<typename Key, class Comparator>
 259 typename 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
 280 template<typename Key, class Comparator>
 281 typename SkipList<Key,Comparator>::Node*
 282 SkipList<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
 301 template<typename Key, class Comparator>
 302 typename 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
 321 template<typename Key, class Comparator>
 322 SkipList<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
 333 template<typename Key, class Comparator>
 334 void 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
 369 template<typename Key, class Comparator>
 370 bool 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