Branch data Line data Source code
# 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 : :
# 104 : 11057780 : inline int GetMaxHeight() const {
# 105 : 11057780 : return max_height_.load(std::memory_order_relaxed);
# 106 : 11057780 : }
# 107 : :
# 108 : : Node* NewNode(const Key& key, int height);
# 109 : : int RandomHeight();
# 110 : 463567 : 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 : 481710 : 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 : 225641612 : Node* Next(int n) {
# 154 : 225641612 : assert(n >= 0);
# 155 : : // Use an 'acquire load' so that we observe a fully initialized
# 156 : : // version of the returned Node.
# 157 : 0 : return next_[n].load(std::memory_order_acquire);
# 158 : 225641612 : }
# 159 : 669388 : void SetNext(int n, Node* x) {
# 160 : 669388 : 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 : 0 : next_[n].store(x, std::memory_order_release);
# 164 : 669388 : }
# 165 : :
# 166 : : // No-barrier variants that can be safely used in a few locations.
# 167 : 631468 : Node* NoBarrier_Next(int n) {
# 168 : 631468 : assert(n >= 0);
# 169 : 0 : return next_[n].load(std::memory_order_relaxed);
# 170 : 631468 : }
# 171 : 631468 : void NoBarrier_SetNext(int n, Node* x) {
# 172 : 631468 : assert(n >= 0);
# 173 : 0 : next_[n].store(x, std::memory_order_relaxed);
# 174 : 631468 : }
# 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 : 481710 : const Key& key, int height) {
# 184 : 481710 : char* const node_memory = arena_->AllocateAligned(
# 185 : 481710 : sizeof(Node) + sizeof(std::atomic<Node*>) * (height - 1));
# 186 : 481710 : return new (node_memory) Node(key);
# 187 : 481710 : }
# 188 : :
# 189 : : template <typename Key, class Comparator>
# 190 : 10096281 : inline SkipList<Key, Comparator>::Iterator::Iterator(const SkipList* list) {
# 191 : 10096281 : list_ = list;
# 192 : 10096281 : node_ = nullptr;
# 193 : 10096281 : }
# 194 : :
# 195 : : template <typename Key, class Comparator>
# 196 : 20013866 : inline bool SkipList<Key, Comparator>::Iterator::Valid() const {
# 197 : 20013866 : return node_ != nullptr;
# 198 : 20013866 : }
# 199 : :
# 200 : : template <typename Key, class Comparator>
# 201 : 9554523 : inline const Key& SkipList<Key, Comparator>::Iterator::key() const {
# 202 : 9554523 : assert(Valid());
# 203 : 0 : return node_->key;
# 204 : 9554523 : }
# 205 : :
# 206 : : template <typename Key, class Comparator>
# 207 : 177324 : inline void SkipList<Key, Comparator>::Iterator::Next() {
# 208 : 177324 : assert(Valid());
# 209 : 0 : node_ = node_->Next(0);
# 210 : 177324 : }
# 211 : :
# 212 : : template <typename Key, class Comparator>
# 213 : 0 : 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 : 0 : assert(Valid());
# 217 : 0 : node_ = list_->FindLessThan(node_->key);
# 218 [ # # ]: 0 : if (node_ == list_->head_) {
# 219 : 0 : node_ = nullptr;
# 220 : 0 : }
# 221 : 0 : }
# 222 : :
# 223 : : template <typename Key, class Comparator>
# 224 : 10094817 : inline void SkipList<Key, Comparator>::Iterator::Seek(const Key& target) {
# 225 : 10094817 : node_ = list_->FindGreaterOrEqual(target, nullptr);
# 226 : 10094817 : }
# 227 : :
# 228 : : template <typename Key, class Comparator>
# 229 : 1468 : inline void SkipList<Key, Comparator>::Iterator::SeekToFirst() {
# 230 : 1468 : node_ = list_->head_->Next(0);
# 231 : 1468 : }
# 232 : :
# 233 : : template <typename Key, class Comparator>
# 234 : 0 : inline void SkipList<Key, Comparator>::Iterator::SeekToLast() {
# 235 : 0 : node_ = list_->FindLast();
# 236 [ # # ]: 0 : if (node_ == list_->head_) {
# 237 : 0 : node_ = nullptr;
# 238 : 0 : }
# 239 : 0 : }
# 240 : :
# 241 : : template <typename Key, class Comparator>
# 242 : 478550 : int SkipList<Key, Comparator>::RandomHeight() {
# 243 : : // Increase height with probability 1 in kBranching
# 244 : 478550 : static const unsigned int kBranching = 4;
# 245 : 478550 : int height = 1;
# 246 [ + - ][ + + ]: 631468 : while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {
# 247 : 152918 : height++;
# 248 : 152918 : }
# 249 : 478550 : assert(height > 0);
# 250 : 0 : assert(height <= kMaxHeight);
# 251 : 0 : return height;
# 252 : 478550 : }
# 253 : :
# 254 : : template <typename Key, class Comparator>
# 255 : 225475187 : bool SkipList<Key, Comparator>::KeyIsAfterNode(const Key& key, Node* n) const {
# 256 : : // null n is considered infinite
# 257 [ + + ][ + + ]: 225475187 : return (n != nullptr) && (compare_(n->key, key) < 0);
# 258 : 225475187 : }
# 259 : :
# 260 : : template <typename Key, class Comparator>
# 261 : : typename SkipList<Key, Comparator>::Node*
# 262 : : SkipList<Key, Comparator>::FindGreaterOrEqual(const Key& key,
# 263 : 10573367 : Node** prev) const {
# 264 : 10573367 : Node* x = head_;
# 265 : 10573367 : int level = GetMaxHeight() - 1;
# 266 : 225475185 : while (true) {
# 267 : 225475185 : Node* next = x->Next(level);
# 268 [ + + ]: 225475185 : if (KeyIsAfterNode(key, next)) {
# 269 : : // Keep searching in this list
# 270 : 150093760 : x = next;
# 271 : 150093760 : } else {
# 272 [ + + ]: 75381425 : if (prev != nullptr) prev[level] = x;
# 273 [ + + ]: 75381425 : if (level == 0) {
# 274 : 10573367 : return next;
# 275 : 64808058 : } else {
# 276 : : // Switch to next list
# 277 : 64808058 : level--;
# 278 : 64808058 : }
# 279 : 75381425 : }
# 280 : 225475185 : }
# 281 : 10573367 : }
# 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 : 0 : while (true) {
# 289 : 0 : assert(x == head_ || compare_(x->key, key) < 0);
# 290 : 0 : Node* next = x->Next(level);
# 291 [ # # ][ # # ]: 0 : if (next == nullptr || compare_(next->key, key) >= 0) {
# 292 [ # # ]: 0 : if (level == 0) {
# 293 : 0 : return x;
# 294 : 0 : } else {
# 295 : : // Switch to next list
# 296 : 0 : level--;
# 297 : 0 : }
# 298 : 0 : } else {
# 299 : 0 : x = next;
# 300 : 0 : }
# 301 : 0 : }
# 302 : 0 : }
# 303 : :
# 304 : : template <typename Key, class Comparator>
# 305 : : typename SkipList<Key, Comparator>::Node* SkipList<Key, Comparator>::FindLast()
# 306 : 0 : const {
# 307 : 0 : Node* x = head_;
# 308 : 0 : int level = GetMaxHeight() - 1;
# 309 : 0 : while (true) {
# 310 : 0 : Node* next = x->Next(level);
# 311 [ # # ]: 0 : if (next == nullptr) {
# 312 [ # # ]: 0 : if (level == 0) {
# 313 : 0 : return x;
# 314 : 0 : } else {
# 315 : : // Switch to next list
# 316 : 0 : level--;
# 317 : 0 : }
# 318 : 0 : } else {
# 319 : 0 : x = next;
# 320 : 0 : }
# 321 : 0 : }
# 322 : 0 : }
# 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 : 3160 : rnd_(0xdeadbeef) {
# 331 [ + + ]: 41080 : for (int i = 0; i < kMaxHeight; i++) {
# 332 : 37920 : head_->SetNext(i, nullptr);
# 333 : 37920 : }
# 334 : 3160 : }
# 335 : :
# 336 : : template <typename Key, class Comparator>
# 337 : 478550 : 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 : 478550 : Node* prev[kMaxHeight];
# 341 : 478550 : Node* x = FindGreaterOrEqual(key, prev);
# 342 : :
# 343 : : // Our data structure does not allow duplicate insertion
# 344 : 478550 : assert(x == nullptr || !Equal(key, x->key));
# 345 : :
# 346 : 0 : int height = RandomHeight();
# 347 [ + + ]: 478550 : if (height > GetMaxHeight()) {
# 348 [ + + ]: 12721 : for (int i = GetMaxHeight(); i < height; i++) {
# 349 : 6858 : prev[i] = head_;
# 350 : 6858 : }
# 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 : 5863 : max_height_.store(height, std::memory_order_relaxed);
# 359 : 5863 : }
# 360 : :
# 361 : 478550 : x = NewNode(key, height);
# 362 [ + + ]: 1110018 : 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 : 631468 : x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
# 366 : 631468 : prev[i]->SetNext(i, x);
# 367 : 631468 : }
# 368 : 478550 : }
# 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_
|
