Bitcoin ABC  0.22.13
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 <boost/noncopyable.hpp>
12 
13 #include <array>
14 #include <atomic>
15 #include <cstdint>
16 #include <memory>
17 #include <type_traits>
18 
41 template <typename T> struct RadixTree : public boost::noncopyable {
42 private:
43  static const int BITS = 4;
44  static const int MASK = (1 << BITS) - 1;
45  static const size_t CHILD_PER_LEVEL = 1 << BITS;
46 
47  typedef typename std::remove_reference<decltype(
48  std::declval<T &>().getId())>::type K;
49  static const size_t KEY_BITS = 8 * sizeof(K);
50  static const uint32_t TOP_LEVEL = (KEY_BITS - 1) / BITS;
51 
52  struct RadixElement;
53  struct RadixNode;
54 
55  std::atomic<RadixElement> root;
56 
57 public:
58  RadixTree() : root(RadixElement()) {}
59  ~RadixTree() { root.load().release(); }
60 
65  bool insert(const RCUPtr<T> &value) {
66  return insert(value->getId(), value);
67  }
68 
73  RCUPtr<T> get(const K &key) {
74  uint32_t level = TOP_LEVEL;
75 
76  RCULock lock;
77  RadixElement e = root.load();
78 
79  // Find a leaf.
80  while (e.isNode()) {
81  e = e.getNode()->get(level--, key)->load();
82  }
83 
84  T *leaf = e.getLeaf();
85  if (leaf == nullptr || leaf->getId() != key) {
86  // We failed to find the proper element.
87  return RCUPtr<T>();
88  }
89 
90  // The leaf is non-null and the keys match. We have our guy.
91  return RCUPtr<T>::copy(leaf);
92  }
93 
94  RCUPtr<const T> get(const K &key) const {
95  T const *ptr = const_cast<RadixTree *>(this)->get(key).release();
96  return RCUPtr<const T>::acquire(ptr);
97  }
98 
103  RCUPtr<T> remove(const K &key) {
104  uint32_t level = TOP_LEVEL;
105 
106  RCULock lock;
107  std::atomic<RadixElement> *eptr = &root;
108 
109  RadixElement e = eptr->load();
110 
111  // Walk down the tree until we find a leaf for our node.
112  while (e.isNode()) {
113  Node:
114  eptr = e.getNode()->get(level--, key);
115  e = eptr->load();
116  }
117 
118  T *leaf = e.getLeaf();
119  if (leaf == nullptr || leaf->getId() != key) {
120  // We failed to find the proper element.
121  return RCUPtr<T>();
122  }
123 
124  // We have the proper element, try to delete it.
125  if (eptr->compare_exchange_strong(e, RadixElement())) {
126  return RCUPtr<T>::acquire(leaf);
127  }
128 
129  // The element was replaced, either by a subtree or another element.
130  if (e.isNode()) {
131  goto Node;
132  }
133 
134  // The element in the slot is not the one we are looking for.
135  return RCUPtr<T>();
136  }
137 
138 private:
139  bool insert(const K &key, RCUPtr<T> value) {
140  uint32_t level = TOP_LEVEL;
141 
142  RCULock lock;
143  std::atomic<RadixElement> *eptr = &root;
144 
145  while (true) {
146  RadixElement e = eptr->load();
147 
148  // Walk down the tree until we find a leaf for our node.
149  while (e.isNode()) {
150  Node:
151  eptr = e.getNode()->get(level--, key);
152  e = eptr->load();
153  }
154 
155  // If the slot is empty, try to insert right there.
156  if (e.getLeaf() == nullptr) {
157  if (eptr->compare_exchange_strong(e,
158  RadixElement(value.get()))) {
159  value.release();
160  return true;
161  }
162 
163  // CAS failed, we may have a node in there now.
164  if (e.isNode()) {
165  goto Node;
166  }
167  }
168 
169  // The element was already in the tree.
170  const K &leafKey = e.getLeaf()->getId();
171  if (key == leafKey) {
172  return false;
173  }
174 
175  // There is an element there, but it isn't a subtree. We need to
176  // convert it into a subtree and resume insertion into that subtree.
177  auto newChild = std::make_unique<RadixNode>(level, leafKey, e);
178  if (eptr->compare_exchange_strong(e,
179  RadixElement(newChild.get()))) {
180  // We have a subtree, resume normal operations from there.
181  newChild.release();
182  } else {
183  // We failed to insert our subtree, clean it before it is freed.
184  newChild->get(level, leafKey)->store(RadixElement());
185  }
186  }
187  }
188 
189  struct RadixElement {
190  private:
191  union {
193  T *leaf;
194  uintptr_t raw;
195  };
196 
197  static const uintptr_t DISCRIMINANT = 0x01;
198  bool getDiscriminant() const { return (raw & DISCRIMINANT) != 0; }
199 
200  public:
201  explicit RadixElement() noexcept : raw(DISCRIMINANT) {}
202  explicit RadixElement(RadixNode *nodeIn) noexcept : node(nodeIn) {}
203  explicit RadixElement(T *leafIn) noexcept : leaf(leafIn) {
204  raw |= DISCRIMINANT;
205  }
206 
211  void release() {
212  if (isNode()) {
213  RadixNode *ptr = getNode();
215  } else {
216  T *ptr = getLeaf();
217  RCUPtr<T>::acquire(ptr);
218  }
219  }
220 
224  bool isNode() const { return !getDiscriminant(); }
225 
227  assert(isNode());
228  return node;
229  }
230 
231  const RadixNode *getNode() const {
232  assert(isNode());
233  return node;
234  }
235 
239  bool isLeaf() const { return getDiscriminant(); }
240 
241  T *getLeaf() {
242  assert(isLeaf());
243  return reinterpret_cast<T *>(raw & ~DISCRIMINANT);
244  }
245 
246  const T *getLeaf() const {
247  assert(isLeaf());
248  return const_cast<RadixElement *>(this)->getLeaf();
249  }
250  };
251 
252  struct RadixNode : public boost::noncopyable {
253  IMPLEMENT_RCU_REFCOUNT(uint64_t);
254 
255  private:
256  union {
257  std::array<std::atomic<RadixElement>, CHILD_PER_LEVEL> children;
258  std::array<RadixElement, CHILD_PER_LEVEL>
260  };
261 
262  public:
263  RadixNode(uint32_t level, const K &key, RadixElement e)
264  : non_atomic_children_DO_NOT_USE() {
265  get(level, key)->store(e);
266  }
267 
269  for (RadixElement e : non_atomic_children_DO_NOT_USE) {
270  e.release();
271  }
272  }
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
std::atomic< RadixElement > * get(uint32_t level, const K &key)
Definition: radix.h:274
static RCUPtr acquire(T *&ptrIn)
Acquire ownership of some pointer.
Definition: rcu.h:96
static const uintptr_t DISCRIMINANT
Definition: radix.h:197
RadixNode(uint32_t level, const K &key, RadixElement e)
Definition: radix.h:263
This is a radix tree storing values identified by a unique key.
Definition: radix.h:41
const T * getLeaf() const
Definition: radix.h:246
static const uint32_t TOP_LEVEL
Definition: radix.h:50
void release()
RadixElement is designed to be a dumb wrapper.
Definition: radix.h:211
T * get()
Get allows to access the undelying pointer.
Definition: rcu.h:147
bool getDiscriminant() const
Definition: radix.h:198
static const size_t CHILD_PER_LEVEL
Definition: radix.h:45
bool insert(const RCUPtr< T > &value)
Insert a value into the tree.
Definition: radix.h:65
bool isNode() const
Node features.
Definition: radix.h:224
std::remove_reference< decltype(std::declval< T & >).getId())>::type K
Definition: radix.h:48
static const int BITS
Definition: radix.h:43
RadixTree()
Definition: radix.h:58
std::array< RadixElement, CHILD_PER_LEVEL > non_atomic_children_DO_NOT_USE
Definition: radix.h:259
~RadixTree()
Definition: radix.h:59
std::array< std::atomic< RadixElement >, CHILD_PER_LEVEL > children
Definition: radix.h:257
RadixNode * getNode()
Definition: radix.h:226
static const int MASK
Definition: radix.h:44
Definition: rcu.h:60
static const size_t KEY_BITS
Definition: radix.h:49
#define IMPLEMENT_RCU_REFCOUNT(T)
Definition: rcu.h:197
bool isLeaf() const
Leaf features.
Definition: radix.h:239
RadixElement(RadixNode *nodeIn) noexcept
Definition: radix.h:202
T * release()
Release transfers ownership of the pointer from RCUPtr to the caller.
Definition: rcu.h:153
bool insert(const K &key, RCUPtr< T > value)
Definition: radix.h:139
const RadixNode * getNode() const
Definition: radix.h:231
static RCUPtr copy(T *ptr)
Construct a new RCUPtr without transferring owership.
Definition: rcu.h:112
Definition: rcu.h:78
RadixNode * node
Definition: radix.h:192
RadixElement(T *leafIn) noexcept
Definition: radix.h:203
std::atomic< RadixElement > root
Definition: radix.h:53
RadixElement() noexcept
Definition: radix.h:201