Inside Bitcoin

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
37namespace leveldb {
38
39class Arena;
40
41template <typename Key, class Comparator>
42class 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  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();
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
145template <typename Key, class Comparator>
146struct 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
181template <typename Key, class Comparator>
182typename 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
189template <typename Key, class Comparator>
190inline SkipList<Key, Comparator>::Iterator::Iterator(const SkipList* list) {
191  list_ = list;
192  node_ = nullptr;
193}
194
195template <typename Key, class Comparator>
196inline bool SkipList<Key, Comparator>::Iterator::Valid() const {
197  return node_ != nullptr;
198}
199
200template <typename Key, class Comparator>
201inline const Key& SkipList<Key, Comparator>::Iterator::key() const {
202  assert(Valid());
203  return node_->key;
204}
205
206template <typename Key, class Comparator>
207inline void SkipList<Key, Comparator>::Iterator::Next() {
208  assert(Valid());
209  node_ = node_->Next(0);
210}
211
212template <typename Key, class Comparator>
213inline 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
223template <typename Key, class Comparator>
224inline void SkipList<Key, Comparator>::Iterator::Seek(const Key& target) {
225  node_ = list_->FindGreaterOrEqual(target, nullptr);
226}
227
228template <typename Key, class Comparator>
229inline void SkipList<Key, Comparator>::Iterator::SeekToFirst() {
230  node_ = list_->head_->Next(0);
231}
232
233template <typename Key, class Comparator>
234inline void SkipList<Key, Comparator>::Iterator::SeekToLast() {
235  node_ = list_->FindLast();
236  if (node_ == list_->head_) {
237    node_ = nullptr;
238  }
239}
240
241template <typename Key, class Comparator>
242int 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);