Bitcoin ABC  0.24.7
P2P Digital Currency
radix.h
Go to the documentation of this file.
1 // Copyright (c) 2019 The Bitcoin developers
2 // Distributed under the MIT software license, see the accompanying
3 // file COPYING or http://www.opensource.org/licenses/mit-license.php.
4 
5 #ifndef BITCOIN_RADIX_H
6 #define BITCOIN_RADIX_H
7 
8 #include <rcu.h>
9 #include <util/system.h>
10 
11 #include <array>
12 #include <atomic>
13 #include <cstdint>
14 #include <memory>
15 #include <type_traits>
16 
35 template <typename T> struct RadixTree {
36 private:
37  static const int BITS = 4;
38  static const int MASK = (1 << BITS) - 1;
39  static const size_t CHILD_PER_LEVEL = 1 << BITS;
40 
41  using K = typename std::remove_reference<decltype(
42  std::declval<T &>().getId())>::type;
43  static const size_t KEY_BITS = 8 * sizeof(K);
44  static const uint32_t TOP_LEVEL = (KEY_BITS - 1) / BITS;
45 
46  struct RadixElement;
47  struct RadixNode;
48 
49  std::atomic<RadixElement> root;
50 
51 public:
53  ~RadixTree() { root.load().release(); }
54 
55  RadixTree(const RadixTree &) = delete;
56  RadixTree &operator=(const RadixTree &) = delete;
57 
62  bool insert(const RCUPtr<T> &value) {
63  return insert(value->getId(), value);
64  }
65 
70  RCUPtr<T> get(const K &key) {
71  uint32_t level = TOP_LEVEL;
72 
73  RCULock lock;
74  RadixElement e = root.load();
75 
76  // Find a leaf.
77  while (e.isNode()) {
78  e = e.getNode()->get(level--, key)->load();
79  }
80 
81  T *leaf = e.getLeaf();
82  if (leaf == nullptr || leaf->getId() != key) {
83  // We failed to find the proper element.
84  return RCUPtr<T>();
85  }
86 
87  // The leaf is non-null and the keys match. We have our guy.
88  return RCUPtr<T>::copy(leaf);
89  }
90 
91  RCUPtr<const T> get(const K &key) const {
92  T const *ptr = const_cast<RadixTree *>(this)->get(key).release();
93  return RCUPtr<const T>::acquire(ptr);
94  }
95 
100  RCUPtr<T> remove(const K &key) {
101  uint32_t level = TOP_LEVEL;
102 
103  RCULock lock;
104  std::atomic<RadixElement> *eptr = &root;
105 
106  RadixElement e = eptr->load();
107 
108  // Walk down the tree until we find a leaf for our node.
109  while (e.isNode()) {
110  Node:
111  eptr = e.getNode()->get(level--, key);
112  e = eptr->load();
113  }
114 
115  T *leaf = e.getLeaf();
116  if (leaf == nullptr || leaf->getId() != key) {
117  // We failed to find the proper element.
118  return RCUPtr<T>();
119  }
120 
121  // We have the proper element, try to delete it.
122  if (eptr->compare_exchange_strong(e, RadixElement())) {
123  return RCUPtr<T>::acquire(leaf);
124  }
125 
126  // The element was replaced, either by a subtree or another element.
127  if (e.isNode()) {
128  goto Node;
129  }
130 
131  // The element in the slot is not the one we are looking for.
132  return RCUPtr<T>();
133  }
134 
135 private:
136  bool insert(const K &key, RCUPtr<T> value) {
137  uint32_t level = TOP_LEVEL;
138 
139  RCULock lock;
140  std::atomic<RadixElement> *eptr = &root;
141 
142  while (true) {
143  RadixElement e = eptr->load();
144 
145  // Walk down the tree until we find a leaf for our node.
146  while (e.isNode()) {
147  Node:
148  eptr = e.getNode()->get(level--, key);
149  e = eptr->load();
150  }
151 
152  // If the slot is empty, try to insert right there.
153  if (e.getLeaf() == nullptr) {
154  if (eptr->compare_exchange_strong(e,
155  RadixElement(value.get()))) {
156  value.release();
157  return true;
158  }
159 
160  // CAS failed, we may have a node in there now.
161  if (e.isNode()) {
162  goto Node;
163  }
164  }
165 
166  // The element was already in the tree.
167  const K &leafKey = e.getLeaf()->getId();
168  if (key == leafKey) {
169  return false;
170  }
171 
172  // There is an element there, but it isn't a subtree. We need to
173  // convert it into a subtree and resume insertion into that subtree.
174  auto newChild = std::make_unique<RadixNode>(level, leafKey, e);
175  if (eptr->compare_exchange_strong(e,
176  RadixElement(newChild.get()))) {
177  // We have a subtree, resume normal operations from there.
178  newChild.release();
179  } else {
180  // We failed to insert our subtree, clean it before it is freed.
181  newChild->get(level, leafKey)->store(RadixElement());
182  }
183  }
184  }
185 
186  struct RadixElement {
187  private:
188  union {
190  T *leaf;
191  uintptr_t raw;
192  };
193 
194  static const uintptr_t DISCRIMINANT = 0x01;
195  bool getDiscriminant() const { return (raw & DISCRIMINANT) != 0; }
196 
197  public:
198  explicit RadixElement() noexcept : raw(DISCRIMINANT) {}
199  explicit RadixElement(RadixNode *nodeIn) noexcept : node(nodeIn) {}
200  explicit RadixElement(T *leafIn) noexcept : leaf(leafIn) {
201  raw |= DISCRIMINANT;
202  }
203 
208  void release() {
209  if (isNode()) {
210  RadixNode *ptr = getNode();
212  } else {
213  T *ptr = getLeaf();
214  RCUPtr<T>::acquire(ptr);
215  }
216  }
217 
221  bool isNode() const { return !getDiscriminant(); }
222 
224  assert(isNode());
225  return node;
226  }
227 
228  const RadixNode *getNode() const {
229  assert(isNode());
230  return node;
231  }
232 
236  bool isLeaf() const { return getDiscriminant(); }
237 
238  T *getLeaf() {
239  assert(isLeaf());
240  return reinterpret_cast<T *>(raw & ~DISCRIMINANT);
241  }
242 
243  const T *getLeaf() const {
244  assert(isLeaf());
245  return const_cast<RadixElement *>(this)->getLeaf();
246  }
247  };
248 
249  struct RadixNode {
250  IMPLEMENT_RCU_REFCOUNT(uint64_t);
251 
252  private:
253  union {
254  std::array<std::atomic<RadixElement>, CHILD_PER_LEVEL> children;
255  std::array<RadixElement, CHILD_PER_LEVEL>
257  };
258 
259  public:
260  RadixNode(uint32_t level, const K &key, RadixElement e)
262  get(level, key)->store(e);
263  }
264 
267  e.release();
268  }
269  }
270 
271  RadixNode(const RadixNode &) = delete;
272  RadixNode &operator=(const RadixNode &) = delete;
273 
274  std::atomic<RadixElement> *get(uint32_t level, const K &key) {
275  return &children[(key >> (level * BITS)) & MASK];
276  }
277  };
278 
279  // Make sure the alignment works for T and RadixElement.
280  static_assert(alignof(T) > 1, "T's alignment must be 2 or more.");
281  static_assert(alignof(RadixNode) > 1,
282  "RadixNode alignment must be 2 or more.");
283 };
284 
285 #endif // BITCOIN_RADIX_H
RadixTree::RadixElement::isNode
bool isNode() const
Node features.
Definition: radix.h:221
RadixTree::RadixElement::RadixElement
RadixElement() noexcept
Definition: radix.h:198
RCUPtr
Definition: rcu.h:79
RCULock
Definition: rcu.h:58
RadixTree::RadixNode::operator=
RadixNode & operator=(const RadixNode &)=delete
RadixTree
This is a radix tree storing values identified by a unique key.
Definition: radix.h:35
RadixTree::RadixNode::children
std::array< std::atomic< RadixElement >, CHILD_PER_LEVEL > children
Definition: radix.h:254
RadixTree::RadixNode::RadixNode
RadixNode(uint32_t level, const K &key, RadixElement e)
Definition: radix.h:260
RadixTree::RadixElement::getNode
RadixNode * getNode()
Definition: radix.h:223
RadixTree::operator=
RadixTree & operator=(const RadixTree &)=delete
RadixTree::MASK
static const int MASK
Definition: radix.h:38
RadixTree::RadixElement::RadixElement
RadixElement(T *leafIn) noexcept
Definition: radix.h:200
RadixTree::RadixElement::release
void release()
RadixElement is designed to be a dumb wrapper.
Definition: radix.h:208
RadixTree::RadixNode
Definition: radix.h:249
rcu.h
RadixTree::RadixElement::getLeaf
T * getLeaf()
Definition: radix.h:238
RadixTree::RadixElement::getNode
const RadixNode * getNode() const
Definition: radix.h:228
RCUPtr::release
T * release()
Release transfers ownership of the pointer from RCUPtr to the caller.
Definition: rcu.h:154
RadixTree::remove
RCUPtr< T > remove(const K &key)
Remove an element from the tree.
Definition: radix.h:100
RCUPtr::copy
static RCUPtr copy(T *ptr)
Construct a new RCUPtr without transferring owership.
Definition: rcu.h:113
RCUPtr::acquire
static RCUPtr acquire(T *&ptrIn)
Acquire ownership of some pointer.
Definition: rcu.h:97
RadixTree::RadixElement::DISCRIMINANT
static const uintptr_t DISCRIMINANT
Definition: radix.h:194
RadixTree::RadixNode::~RadixNode
~RadixNode()
Definition: radix.h:265
RadixTree::TOP_LEVEL
static const uint32_t TOP_LEVEL
Definition: radix.h:44
RadixTree::RadixElement::isLeaf
bool isLeaf() const
Leaf features.
Definition: radix.h:236
RadixTree::RadixNode::get
std::atomic< RadixElement > * get(uint32_t level, const K &key)
Definition: radix.h:274
RadixTree::CHILD_PER_LEVEL
static const size_t CHILD_PER_LEVEL
Definition: radix.h:39
RadixTree::RadixElement::getDiscriminant
bool getDiscriminant() const
Definition: radix.h:195
RadixTree::RadixElement::node
RadixNode * node
Definition: radix.h:189
RadixTree::RadixElement::raw
uintptr_t raw
Definition: radix.h:191
RadixTree::RadixNode::IMPLEMENT_RCU_REFCOUNT
IMPLEMENT_RCU_REFCOUNT(uint64_t)
RadixTree::RadixElement
Definition: radix.h:186
RadixTree::BITS
static const int BITS
Definition: radix.h:37
RadixTree::RadixTree
RadixTree()
Definition: radix.h:52
system.h
RadixTree::root
std::atomic< RadixElement > root
Definition: radix.h:47
RCUPtr::get
T * get()
Get allows to access the undelying pointer.
Definition: rcu.h:148
RadixTree::RadixElement::RadixElement
RadixElement(RadixNode *nodeIn) noexcept
Definition: radix.h:199
RadixTree::RadixNode::non_atomic_children_DO_NOT_USE
std::array< RadixElement, CHILD_PER_LEVEL > non_atomic_children_DO_NOT_USE
Definition: radix.h:256
RadixTree::get
RCUPtr< T > get(const K &key)
Get the value corresponding to a key.
Definition: radix.h:70
RadixTree::K
typename std::remove_reference< decltype(std::declval< T & >().getId())>::type K
Definition: radix.h:42
RadixTree::insert
bool insert(const K &key, RCUPtr< T > value)
Definition: radix.h:136
RadixTree::KEY_BITS
static const size_t KEY_BITS
Definition: radix.h:43
RadixTree::RadixElement::leaf
T * leaf
Definition: radix.h:190
RadixTree::insert
bool insert(const RCUPtr< T > &value)
Insert a value into the tree.
Definition: radix.h:62
RadixTree::get
RCUPtr< const T > get(const K &key) const
Definition: radix.h:91
RadixTree::RadixElement::getLeaf
const T * getLeaf() const
Definition: radix.h:243
RadixTree::~RadixTree
~RadixTree()
Definition: radix.h:53