src/leveldb/db/skiplist.h

   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 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         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   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   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     assert(n >= 0);
 156     // Use an 'acquire load' so that we observe a fully initialized
 157     // version of the returned Node.
 158     return reinterpret_cast<Node*>(next_[n].Acquire_Load());
 159   }
 160   void SetNext(int n, Node* x) {
 161     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     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     assert(n >= 0);
 170     return reinterpret_cast<Node*>(next_[n].NoBarrier_Load());
 171   }
 172   void NoBarrier_SetNext(int n, Node* x) {
 173     assert(n >= 0);
 174     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 SkipList<Key,Comparator>::NewNode(const Key& key, int height) {
 185   char* mem = arena_->AllocateAligned(
 186       sizeof(Node) + sizeof(port::AtomicPointer) * (height - 1));
 187   return new (mem) Node(key);
 188 }
 189
 190 template<typename Key, class Comparator>
 191 inline SkipList<Key,Comparator>::Iterator::Iterator(const SkipList* list) {
 192   list_ = list;
 193   node_ = NULL;
 194 }
 195
 196 template<typename Key, class Comparator>
 197 inline bool SkipList<Key,Comparator>::Iterator::Valid() const {
 198   return node_ != NULL;
 199 }
 200
 201 template<typename Key, class Comparator>
 202 inline const Key& SkipList<Key,Comparator>::Iterator::key() const {
 203   assert(Valid());
 204   return node_->key;
 205 }
 206
 207 template<typename Key, class Comparator>
 208 inline void SkipList<Key,Comparator>::Iterator::Next() {
 209   assert(Valid());
 210   node_ = node_->Next(0);
 211 }
 212
 213 template<typename Key, class Comparator>
 214 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   assert(Valid());
 218   node_ = list_->FindLessThan(node_->key);
 219   if (node_ == list_->head_) {
 220     node_ = NULL;
 221   }
 222 }
 223
 224 template<typename Key, class Comparator>
 225 inline void SkipList<Key,Comparator>::Iterator::Seek(const Key& target) {
 226   node_ = list_->FindGreaterOrEqual(target, NULL);
 227 }
 228
 229 template<typename Key, class Comparator>
 230 inline void SkipList<Key,Comparator>::Iterator::SeekToFirst() {
 231   node_ = list_->head_->Next(0);
 232 }
 233
 234 template<typename Key, class Comparator>
 235 inline void SkipList<Key,Comparator>::Iterator::SeekToLast() {
 236   node_ = list_->FindLast();
 237   if (node_ == list_->head_) {
 238     node_ = NULL;
 239   }
 240 }
 241
 242 template<typename Key, class Comparator>
 243 int SkipList<Key,Comparator>::RandomHeight() {
 244   // Increase height with probability 1 in kBranching
 245   static const unsigned int kBranching = 4;
 246   int height = 1;
 247   while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {
 248     height++;
 249   }
 250   assert(height > 0);
 251   assert(height <= kMaxHeight);
 252   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   return (n != NULL) && (compare_(n->key, key) < 0);
 259 }
 260
 261 template<typename Key, class Comparator>
 262 typename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindGreaterOrEqual(const Key& key, Node** prev)
 263     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 != NULL) 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 == NULL || 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 == NULL) {
 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_(reinterpret_cast<void*>(1)),
 330       rnd_(0xdeadbeef) {
 331   for (int i = 0; i < kMaxHeight; i++) {
 332     head_->SetNext(i, NULL);
 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 == NULL || !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     //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     max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));
 361   }
 362
 363   x = NewNode(key, height);
 364   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     x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
 368     prev[i]->SetNext(i, x);
 369   }
 370 }
 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_