PMDK C++ bindings  1.11
This is the C++ bindings documentation for PMDK's libpmemobj.
radix_tree.hpp
Go to the documentation of this file.
1 // SPDX-License-Identifier: BSD-3-Clause
2 /* Copyright 2020, Intel Corporation */
3 
16 #ifndef LIBPMEMOBJ_CPP_RADIX_HPP
17 #define LIBPMEMOBJ_CPP_RADIX_HPP
18 
21 #include <libpmemobj++/detail/pair.hpp>
26 #include <libpmemobj++/p.hpp>
28 #include <libpmemobj++/pext.hpp>
29 #include <libpmemobj++/pool.hpp>
32 #include <libpmemobj++/utils.hpp>
33 
34 #include <algorithm>
35 #include <iostream>
36 #include <string>
37 #if __cpp_lib_endian
38 #include <bit>
39 #endif
40 
43 
44 namespace pmem
45 {
46 
47 namespace detail
48 {
49 template <typename T, typename Enable = void>
50 struct bytes_view;
51 }
52 
53 namespace obj
54 {
55 
56 namespace experimental
57 {
58 
101 template <typename Key, typename Value,
102  typename BytesView = detail::bytes_view<Key>>
103 class radix_tree {
104  template <bool IsConst>
105  struct radix_tree_iterator;
106 
107 public:
108  using key_type = Key;
109  using mapped_type = Value;
110  using value_type = detail::pair<const key_type, mapped_type>;
111  using size_type = std::size_t;
112  using reference = value_type &;
113  using const_reference = const value_type &;
116  using reverse_iterator = std::reverse_iterator<iterator>;
117  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
118  using difference_type = std::ptrdiff_t;
119 
120  radix_tree();
121 
122  template <class InputIt>
123  radix_tree(InputIt first, InputIt last);
124  radix_tree(const radix_tree &m);
125  radix_tree(radix_tree &&m);
126  radix_tree(std::initializer_list<value_type> il);
127 
128  radix_tree &operator=(const radix_tree &m);
130  radix_tree &operator=(std::initializer_list<value_type> ilist);
131 
132  ~radix_tree();
133 
134  template <class... Args>
135  std::pair<iterator, bool> emplace(Args &&... args);
136 
137  std::pair<iterator, bool> insert(const value_type &v);
138  std::pair<iterator, bool> insert(value_type &&v);
139  template <typename P,
140  typename = typename std::enable_if<
141  std::is_constructible<value_type, P &&>::value,
142  P>::type>
143  std::pair<iterator, bool> insert(P &&p);
144  /* iterator insert(const_iterator position, const value_type &v); */
145  /* iterator insert(const_iterator position, value_type &&v); */
146  /* template <
147  typename P,
148  typename = typename std::enable_if<
149  detail::has_is_transparent<BytesView>::value, P>::type>
150  iterator insert(const_iterator position, P &&p); */
151  template <class InputIterator>
152  void insert(InputIterator first, InputIterator last);
153  void insert(std::initializer_list<value_type> il);
154  // insert_return_type insert(node_type&& nh);
155  // iterator insert(const_iterator hint, node_type&& nh);
156 
157  template <class... Args>
158  std::pair<iterator, bool> try_emplace(const key_type &k,
159  Args &&... args);
160  template <class... Args>
161  std::pair<iterator, bool> try_emplace(key_type &&k, Args &&... args);
162  /*template <class... Args>
163  iterator try_emplace(const_iterator hint, const key_type &k,
164  Args &&... args);*/
165  /*template <class... Args>
166  iterator try_emplace(const_iterator hint, key_type &&k,
167  Args &&... args);*/
168  /* https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96976 */
169  template <typename K, typename BV = BytesView, class... Args>
170  auto try_emplace(K &&k, Args &&... args) -> typename std::enable_if<
171  detail::has_is_transparent<BV>::value &&
172  !std::is_same<typename std::remove_reference<K>::type,
173  key_type>::value,
174  std::pair<iterator, bool>>::type;
175 
176  template <typename M>
177  std::pair<iterator, bool> insert_or_assign(const key_type &k, M &&obj);
178  template <typename M>
179  std::pair<iterator, bool> insert_or_assign(key_type &&k, M &&obj);
180  /*template <typename M>
181  iterator insert_or_assign(const_iterator hint, const key_type &k,
182  M &&obj);*/
183  /*template <typename M>
184  iterator insert_or_assign(const_iterator hint, key_type &&k, M &&obj);*/
185  template <
186  typename M, typename K,
187  typename = typename std::enable_if<
188  detail::has_is_transparent<BytesView>::value, K>::type>
189  std::pair<iterator, bool> insert_or_assign(K &&k, M &&obj);
190 
193  size_type erase(const key_type &k);
194  template <typename K,
195  typename = typename std::enable_if<
196  detail::has_is_transparent<BytesView>::value &&
197  !std::is_same<K, iterator>::value &&
198  !std::is_same<K, const_iterator>::value,
199  K>::type>
200  size_type erase(const K &k);
201 
202  void clear();
203 
204  size_type count(const key_type &k) const;
205  template <
206  typename K,
207  typename = typename std::enable_if<
208  detail::has_is_transparent<BytesView>::value, K>::type>
209  size_type count(const K &k) const;
210 
211  iterator find(const key_type &k);
212  const_iterator find(const key_type &k) const;
213  template <
214  typename K,
215  typename = typename std::enable_if<
216  detail::has_is_transparent<BytesView>::value, K>::type>
217  iterator find(const K &k);
218  template <
219  typename K,
220  typename = typename std::enable_if<
221  detail::has_is_transparent<BytesView>::value, K>::type>
222  const_iterator find(const K &k) const;
223 
224  iterator lower_bound(const key_type &k);
225  const_iterator lower_bound(const key_type &k) const;
226  template <
227  typename K,
228  typename = typename std::enable_if<
229  detail::has_is_transparent<BytesView>::value, K>::type>
230  iterator lower_bound(const K &k);
231  template <
232  typename K,
233  typename = typename std::enable_if<
234  detail::has_is_transparent<BytesView>::value, K>::type>
235  const_iterator lower_bound(const K &k) const;
236 
237  iterator upper_bound(const key_type &k);
238  const_iterator upper_bound(const key_type &k) const;
239  template <
240  typename K,
241  typename = typename std::enable_if<
242  detail::has_is_transparent<BytesView>::value, K>::type>
243  iterator upper_bound(const K &k);
244  template <
245  typename K,
246  typename = typename std::enable_if<
247  detail::has_is_transparent<BytesView>::value, K>::type>
248  const_iterator upper_bound(const K &k) const;
249 
250  iterator begin();
251  iterator end();
252  const_iterator cbegin() const;
253  const_iterator cend() const;
254  const_iterator begin() const;
255  const_iterator end() const;
256 
257  reverse_iterator rbegin();
258  reverse_iterator rend();
259  const_reverse_iterator crbegin() const;
260  const_reverse_iterator crend() const;
261  const_reverse_iterator rbegin() const;
262  const_reverse_iterator rend() const;
263 
264  /* capacity: */
265  bool empty() const noexcept;
266  size_type max_size() const noexcept;
267  uint64_t size() const noexcept;
268 
269  void swap(radix_tree &rhs);
270 
271  template <typename K, typename V, typename BV>
272  friend std::ostream &operator<<(std::ostream &os,
273  const radix_tree<K, V, BV> &tree);
274 
275 private:
276  using byten_t = uint64_t;
277  using bitn_t = uint8_t;
278 
279  /* Size of a chunk which differentiates subtrees of a node */
280  static constexpr std::size_t SLICE = 4;
281  /* Mask for SLICE */
282  static constexpr std::size_t NIB = ((1ULL << SLICE) - 1);
283  /* Number of children in internal nodes */
284  static constexpr std::size_t SLNODES = (1 << SLICE);
285  /* Mask for SLICE */
286  static constexpr bitn_t SLICE_MASK = (bitn_t) ~(SLICE - 1);
287  /* Position of the first SLICE */
288  static constexpr bitn_t FIRST_NIB = 8 - SLICE;
289 
290  struct tagged_node_ptr;
291  struct leaf;
292  struct node;
293 
294  /*** pmem members ***/
295  tagged_node_ptr root;
296  p<uint64_t> size_;
297 
298  /* helper functions */
299  template <typename K, typename F, class... Args>
300  std::pair<iterator, bool> internal_emplace(const K &, F &&);
301  template <typename K>
302  leaf *internal_find(const K &k) const;
303 
304  static tagged_node_ptr &parent_ref(tagged_node_ptr n);
305  template <typename K1, typename K2>
306  static bool keys_equal(const K1 &k1, const K2 &k2);
307  template <typename K1, typename K2>
308  static int compare(const K1 &k1, const K2 &k2, byten_t offset = 0);
309  template <bool Direction, typename Iterator>
310  static leaf *next_leaf(Iterator child, tagged_node_ptr parent);
311  template <bool Direction>
312  static leaf *find_leaf(tagged_node_ptr n);
313  static unsigned slice_index(char k, uint8_t shift);
314  template <typename K1, typename K2>
315  static byten_t prefix_diff(const K1 &lhs, const K2 &rhs,
316  byten_t offset = 0);
317  leaf *any_leftmost_leaf(tagged_node_ptr n, size_type min_depth) const;
318  template <typename K1, typename K2>
319  static bitn_t bit_diff(const K1 &leaf_key, const K2 &key, byten_t diff);
320  template <typename K>
321  leaf *common_prefix_leaf(const K &key) const;
322  static void print_rec(std::ostream &os, radix_tree::tagged_node_ptr n);
323  template <typename K>
324  static BytesView bytes_view(const K &k);
325  static string_view bytes_view(string_view s);
326  static bool path_length_equal(size_t key_size, tagged_node_ptr n);
327  template <typename K>
328  std::tuple<const tagged_node_ptr *, tagged_node_ptr>
329  descend(const K &k, byten_t diff, bitn_t sh) const;
330  template <typename K>
331  std::tuple<tagged_node_ptr *, tagged_node_ptr>
332  descend(const K &k, byten_t diff, bitn_t sh);
333  template <bool Lower, typename K>
334  const_iterator internal_bound(const K &k) const;
335 
336  void check_pmem();
337  void check_tx_stage_work();
338 
339  static_assert(sizeof(node) == 256,
340  "Internal node should have size equal to 256 bytes.");
341 };
342 
343 template <typename Key, typename Value, typename BytesView>
346 
347 template <typename Key, typename Value, typename BytesView>
348 struct radix_tree<Key, Value, BytesView>::tagged_node_ptr {
349  tagged_node_ptr() = default;
350  tagged_node_ptr(const tagged_node_ptr &rhs) = default;
351 
352  tagged_node_ptr(std::nullptr_t);
353  tagged_node_ptr(const persistent_ptr<leaf> &ptr);
354  tagged_node_ptr(const persistent_ptr<node> &ptr);
355 
356  tagged_node_ptr &operator=(const tagged_node_ptr &rhs) = default;
357 
358  tagged_node_ptr &operator=(std::nullptr_t);
359  tagged_node_ptr &operator=(const persistent_ptr<leaf> &rhs);
360  tagged_node_ptr &operator=(const persistent_ptr<node> &rhs);
361 
362  bool operator==(const tagged_node_ptr &rhs) const;
363  bool operator!=(const tagged_node_ptr &rhs) const;
364 
365  bool operator==(const radix_tree::leaf *rhs) const;
366  bool operator!=(const radix_tree::leaf *rhs) const;
367 
368  void swap(tagged_node_ptr &rhs);
369 
370  bool is_leaf() const;
371 
372  radix_tree::leaf *get_leaf() const;
373  radix_tree::node *get_node() const;
374 
375  radix_tree::node *operator->() const noexcept;
376 
377  explicit operator bool() const noexcept;
378 
379 private:
380  static constexpr uintptr_t IS_LEAF = 1;
381  void *add_tag(radix_tree::leaf *ptr) const;
382  void *remove_tag(void *ptr) const;
383 
385 };
386 
396 template <typename Key, typename Value, typename BytesView>
397 struct radix_tree<Key, Value, BytesView>::leaf {
399 
400  leaf(const leaf &) = delete;
401  leaf(leaf &&) = delete;
402 
403  leaf &operator=(const leaf &) = delete;
404  leaf &operator=(leaf &&) = delete;
405 
406  ~leaf();
407 
408  Key &key();
409  Value &value();
410 
411  const Key &key() const;
412  const Value &value() const;
413 
414 private:
415  friend class radix_tree<Key, Value, BytesView>;
416 
417  leaf() = default;
418 
419  template <typename... Args>
420  static persistent_ptr<leaf> make(tagged_node_ptr parent,
421  Args &&... args);
422 
423  static persistent_ptr<leaf> make_internal();
424 
425  template <typename... Args1, typename... Args2>
426  static persistent_ptr<leaf>
427  make_internal(std::piecewise_construct_t pc,
428  std::tuple<Args1...> first_args,
429  std::tuple<Args2...> second_args);
430 
431  template <typename K, typename V>
432  static persistent_ptr<leaf> make_internal(K &&k, V &&v);
433  template <typename K, typename V>
434  static persistent_ptr<leaf> make_internal(const K &k, const V &v);
435 
436  template <typename K, typename V>
437  static persistent_ptr<leaf> make_internal(detail::pair<K, V> &&p);
438  template <typename K, typename V>
439  static persistent_ptr<leaf> make_internal(const detail::pair<K, V> &p);
440 
441  template <typename K, typename V>
442  static persistent_ptr<leaf> make_internal(std::pair<K, V> &&p);
443  template <typename K, typename V>
444  static persistent_ptr<leaf> make_internal(const std::pair<K, V> &p);
445 
446  template <typename... Args1, typename... Args2, size_t... I1,
447  size_t... I2>
448  static persistent_ptr<leaf> make_internal(
449  std::piecewise_construct_t, std::tuple<Args1...> &first_args,
450  std::tuple<Args2...> &second_args,
451  detail::index_sequence<I1...>, detail::index_sequence<I2...>);
452 
453  static persistent_ptr<leaf> make_internal(const leaf &other);
454 
455  tagged_node_ptr parent = nullptr;
456 };
457 
462 template <typename Key, typename Value, typename BytesView>
463 struct radix_tree<Key, Value, BytesView>::node {
464  node(tagged_node_ptr parent, byten_t byte, bitn_t bit);
465 
469  tagged_node_ptr parent;
470 
477  tagged_node_ptr embedded_entry;
478 
479  /* Children can be both leaves and internal nodes. */
480  tagged_node_ptr child[SLNODES];
481 
492  byten_t byte;
493  bitn_t bit;
494 
495  struct direction {
496  static constexpr bool Forward = 0;
497  static constexpr bool Reverse = 1;
498  };
499 
500  struct forward_iterator;
501  using reverse_iterator = std::reverse_iterator<forward_iterator>;
502 
503  template <bool Direction>
504  using iterator =
505  typename std::conditional<Direction == direction::Forward,
506  forward_iterator,
507  reverse_iterator>::type;
508 
509  template <bool Direction = direction::Forward>
510  typename std::enable_if<
511  Direction ==
512  radix_tree<Key, Value,
513  BytesView>::node::direction::Forward,
514  typename radix_tree<Key, Value,
515  BytesView>::node::forward_iterator>::type
516  begin() const;
517 
518  template <bool Direction = direction::Forward>
519  typename std::enable_if<
520  Direction ==
521  radix_tree<Key, Value,
522  BytesView>::node::direction::Forward,
523  typename radix_tree<Key, Value,
524  BytesView>::node::forward_iterator>::type
525  end() const;
526 
527  /* rbegin */
528  template <bool Direction = direction::Forward>
529  typename std::enable_if<
530  Direction ==
531  radix_tree<Key, Value,
532  BytesView>::node::direction::Reverse,
533  typename radix_tree<Key, Value,
534  BytesView>::node::reverse_iterator>::type
535  begin() const;
536 
537  /* rend */
538  template <bool Direction = direction::Forward>
539  typename std::enable_if<
540  Direction ==
541  radix_tree<Key, Value,
542  BytesView>::node::direction::Reverse,
543  typename radix_tree<Key, Value,
544  BytesView>::node::reverse_iterator>::type
545  end() const;
546 
547  template <bool Direction = direction::Forward, typename Ptr>
548  auto find_child(const Ptr &n) const -> decltype(begin<Direction>());
549 
550  template <bool Direction = direction::Forward,
551  typename Enable = typename std::enable_if<
552  Direction == direction::Forward>::type>
553  auto make_iterator(const tagged_node_ptr *ptr) const
554  -> decltype(begin<Direction>());
555 
556  uint8_t padding[256 - sizeof(parent) - sizeof(leaf) - sizeof(child) -
557  sizeof(byte) - sizeof(bit)];
558 };
559 
565 template <typename Key, typename Value, typename BytesView>
566 template <bool IsConst>
567 struct radix_tree<Key, Value, BytesView>::radix_tree_iterator {
568 private:
569  using leaf_ptr =
570  typename std::conditional<IsConst, const leaf *, leaf *>::type;
571  using node_ptr =
572  typename std::conditional<IsConst, const tagged_node_ptr *,
573  tagged_node_ptr *>::type;
574  friend struct radix_tree_iterator<true>;
575 
576 public:
577  using difference_type = std::ptrdiff_t;
579  using reference = typename std::conditional<IsConst, const value_type &,
580  value_type &>::type;
581  using pointer = typename std::conditional<IsConst, value_type const *,
582  value_type *>::type;
583  using iterator_category = std::bidirectional_iterator_tag;
584 
585  radix_tree_iterator() = default;
586  radix_tree_iterator(leaf_ptr leaf_, node_ptr root);
587  radix_tree_iterator(const radix_tree_iterator &rhs) = default;
588 
589  template <bool C = IsConst,
590  typename Enable = typename std::enable_if<C>::type>
592 
594  operator=(const radix_tree_iterator &rhs) = default;
595 
596  reference operator*() const;
597  pointer operator->() const;
598 
599  template <typename V = Value,
600  typename Enable = typename std::enable_if<
601  std::is_same<V, inline_string>::value>::type>
602  void assign_val(string_view rhs);
603 
604  template <typename T, typename V = Value,
605  typename Enable = typename std::enable_if<
606  !std::is_same<V, inline_string>::value>::type>
607  void assign_val(T &&rhs);
608 
611 
614 
615  template <bool C>
616  bool operator!=(const radix_tree_iterator<C> &rhs) const;
617 
618  template <bool C>
619  bool operator==(const radix_tree_iterator<C> &rhs) const;
620 
621 private:
622  friend class radix_tree;
623 
624  leaf_ptr leaf_ = nullptr;
625  node_ptr root = nullptr;
626 };
627 
628 template <typename Key, typename Value, typename BytesView>
629 struct radix_tree<Key, Value, BytesView>::node::forward_iterator {
630  using difference_type = std::ptrdiff_t;
631  using value_type = tagged_node_ptr;
632  using pointer = const value_type *;
633  using reference = const value_type &;
634  using iterator_category = std::forward_iterator_tag;
635 
636  forward_iterator(pointer child, const node *node);
637 
638  forward_iterator operator++();
639  forward_iterator operator++(int);
640 
641  forward_iterator operator--();
642 
643  reference operator*() const;
644  pointer operator->() const;
645 
646  pointer get_node() const;
647 
648  bool operator!=(const forward_iterator &rhs) const;
649  bool operator==(const forward_iterator &rhs) const;
650 
651 private:
652  pointer child;
653  const node *n;
654 };
655 
664 template <typename Key, typename Value, typename BytesView>
666 {
667  check_pmem();
669 }
670 
690 template <typename Key, typename Value, typename BytesView>
691 template <class InputIt>
693  : root(nullptr), size_(0)
694 {
695  check_pmem();
697 
698  for (auto it = first; it != last; it++)
699  emplace(*it);
700 }
701 
717 template <typename Key, typename Value, typename BytesView>
719 {
720  check_pmem();
721  check_tx_stage_work();
722 
723  root = nullptr;
724  size_ = 0;
725 
726  for (auto it = m.cbegin(); it != m.cend(); it++)
727  emplace(*it);
728 }
729 
742 template <typename Key, typename Value, typename BytesView>
744 {
745  check_pmem();
746  check_tx_stage_work();
747 
748  root = m.root;
749  size_ = m.size_;
750  m.root = nullptr;
751  m.size_ = 0;
752 }
753 
768 template <typename Key, typename Value, typename BytesView>
770  std::initializer_list<value_type> il)
771  : radix_tree(il.begin(), il.end())
772 {
773 }
774 
784 template <typename Key, typename Value, typename BytesView>
787 {
788  check_pmem();
789 
790  auto pop = pool_by_vptr(this);
791 
792  if (this != &other) {
793  transaction::run(pop, [&] {
794  clear();
795 
796  this->root = nullptr;
797  this->size_ = 0;
798 
799  for (auto it = other.cbegin(); it != other.cend(); it++)
800  emplace(*it);
801  });
802  }
803 
804  return *this;
805 }
806 
815 template <typename Key, typename Value, typename BytesView>
818 {
819  check_pmem();
820 
821  auto pop = pool_by_vptr(this);
822 
823  if (this != &other) {
824  transaction::run(pop, [&] {
825  clear();
826 
827  this->root = other.root;
828  this->size_ = other.size_;
829  other.root = nullptr;
830  other.size_ = 0;
831  });
832  }
833 
834  return *this;
835 }
836 
847 template <typename Key, typename Value, typename BytesView>
850  std::initializer_list<value_type> ilist)
851 {
852  check_pmem();
853 
854  auto pop = pool_by_vptr(this);
855 
856  transaction::run(pop, [&] {
857  clear();
858 
859  this->root = nullptr;
860  this->size_ = 0;
861 
862  for (auto it = ilist.begin(); it != ilist.end(); it++)
863  emplace(*it);
864  });
865 
866  return *this;
867 }
868 
872 template <typename Key, typename Value, typename BytesView>
874 {
875  try {
876  clear();
877  } catch (...) {
878  std::terminate();
879  }
880 }
881 
887 template <typename Key, typename Value, typename BytesView>
888 bool
890 {
891  return size_ == 0;
892 }
893 
897 template <typename Key, typename Value, typename BytesView>
898 typename radix_tree<Key, Value, BytesView>::size_type
900 {
901  return std::numeric_limits<difference_type>::max();
902 }
903 
907 template <typename Key, typename Value, typename BytesView>
908 uint64_t
910 {
911  return this->size_;
912 }
913 
919 template <typename Key, typename Value, typename BytesView>
920 void
922 {
923  auto pop = pool_by_vptr(this);
924 
925  transaction::run(pop, [&] {
926  this->size_.swap(rhs.size_);
927  this->root.swap(rhs.root);
928  });
929 }
930 
931 /*
932  * Returns reference to n->parent (handles both internal and leaf nodes).
933  */
934 template <typename Key, typename Value, typename BytesView>
937 {
938  if (n.is_leaf())
939  return n.get_leaf()->parent;
940 
941  return n->parent;
942 }
943 
944 /*
945  * Find a leftmost leaf in a subtree of @param n.
946  *
947  * @param min_depth specifies minimum depth of the leaf. If the
948  * tree is shorter than min_depth, a bottom leaf is returned.
949  */
950 template <typename Key, typename Value, typename BytesView>
951 typename radix_tree<Key, Value, BytesView>::leaf *
952 radix_tree<Key, Value, BytesView>::any_leftmost_leaf(
953  typename radix_tree<Key, Value, BytesView>::tagged_node_ptr n,
954  size_type min_depth) const
955 {
956  assert(n);
957 
958  while (!n.is_leaf()) {
959  if (n->embedded_entry && n->byte >= min_depth)
960  return n->embedded_entry.get_leaf();
961 
962  for (size_t i = 0; i < SLNODES; i++) {
963  tagged_node_ptr m;
964  if ((m = n->child[i])) {
965  n = m;
966  break;
967  }
968  }
969  }
970 
971  return n.get_leaf();
972 }
973 
974 /*
975  * Descends to the leaf that shares a common prefix with the key.
976  */
977 template <typename Key, typename Value, typename BytesView>
978 template <typename K>
979 typename radix_tree<Key, Value, BytesView>::leaf *
980 radix_tree<Key, Value, BytesView>::common_prefix_leaf(const K &key) const
981 {
982  auto n = root;
983 
984  while (n && !n.is_leaf() && n->byte < key.size()) {
985  auto nn = n->child[slice_index(key[n->byte], n->bit)];
986 
987  if (nn)
988  n = nn;
989  else {
990  n = any_leftmost_leaf(n, key.size());
991  break;
992  }
993  }
994 
995  /* This can happen when key is a prefix of some leaf or when the node at
996  * which the keys diverge isn't a leaf */
997  if (!n.is_leaf())
998  n = any_leftmost_leaf(n, key.size());
999 
1000  return n.get_leaf();
1001 }
1002 
1003 template <typename Key, typename Value, typename BytesView>
1004 template <typename K>
1005 BytesView
1006 radix_tree<Key, Value, BytesView>::bytes_view(const K &key)
1007 {
1008  /* bytes_view accepts const pointer instead of reference to make sure
1009  * there is no implicit conversion to a temporary type (and hence
1010  * dangling references). */
1011  return BytesView(&key);
1012 }
1013 
1014 template <typename Key, typename Value, typename BytesView>
1015 string_view
1016 radix_tree<Key, Value, BytesView>::bytes_view(string_view key)
1017 {
1018  return key;
1019 }
1020 
1021 /*
1022  * Checks for key equality.
1023  */
1024 template <typename Key, typename Value, typename BytesView>
1025 template <typename K1, typename K2>
1026 bool
1027 radix_tree<Key, Value, BytesView>::keys_equal(const K1 &k1, const K2 &k2)
1028 {
1029  return k1.size() == k2.size() && compare(k1, k2) == 0;
1030 }
1031 
1032 /*
1033  * Checks for key equality.
1034  */
1035 template <typename Key, typename Value, typename BytesView>
1036 template <typename K1, typename K2>
1037 int
1038 radix_tree<Key, Value, BytesView>::compare(const K1 &k1, const K2 &k2,
1039  byten_t offset)
1040 {
1041  auto ret = prefix_diff(k1, k2, offset);
1042 
1043  if (ret != (std::min)(k1.size(), k2.size()))
1044  return (unsigned char)(k1[ret]) - (unsigned char)(k2[ret]);
1045 
1046  return k1.size() - k2.size();
1047 }
1048 
1049 /*
1050  * Returns length of common prefix of lhs and rhs.
1051  */
1052 template <typename Key, typename Value, typename BytesView>
1053 template <typename K1, typename K2>
1054 typename radix_tree<Key, Value, BytesView>::byten_t
1055 radix_tree<Key, Value, BytesView>::prefix_diff(const K1 &lhs, const K2 &rhs,
1056  byten_t offset)
1057 {
1058  byten_t diff;
1059  for (diff = offset; diff < (std::min)(lhs.size(), rhs.size()); diff++) {
1060  if (lhs[diff] != rhs[diff])
1061  return diff;
1062  }
1063 
1064  return diff;
1065 }
1066 
1067 /*
1068  * Checks whether length of the path from root to n is equal
1069  * to key_size.
1070  */
1071 template <typename Key, typename Value, typename BytesView>
1072 bool
1073 radix_tree<Key, Value, BytesView>::path_length_equal(size_t key_size,
1074  tagged_node_ptr n)
1075 {
1076  return n->byte == key_size && n->bit == bitn_t(FIRST_NIB);
1077 }
1078 
1079 template <typename Key, typename Value, typename BytesView>
1080 template <typename K1, typename K2>
1081 typename radix_tree<Key, Value, BytesView>::bitn_t
1082 radix_tree<Key, Value, BytesView>::bit_diff(const K1 &leaf_key, const K2 &key,
1083  byten_t diff)
1084 {
1085  auto min_key_len = (std::min)(leaf_key.size(), key.size());
1086  bitn_t sh = 8;
1087 
1088  /* If key differs from leaf_key at some point (neither is a prefix of
1089  * another) we will descend to the point of divergence. Otherwise we
1090  * will look for a node which represents the prefix. */
1091  if (diff < min_key_len) {
1092  auto at =
1093  static_cast<unsigned char>(leaf_key[diff] ^ key[diff]);
1094  sh = pmem::detail::mssb_index((uint32_t)at) & SLICE_MASK;
1095  }
1096 
1097  return sh;
1098 }
1099 
1100 template <typename Key, typename Value, typename BytesView>
1101 template <typename K>
1102 std::tuple<const typename radix_tree<Key, Value, BytesView>::tagged_node_ptr *,
1103  typename radix_tree<Key, Value, BytesView>::tagged_node_ptr>
1104 radix_tree<Key, Value, BytesView>::descend(const K &key, byten_t diff,
1105  bitn_t sh) const
1106 {
1107  auto n = root;
1108  auto prev = n;
1109  auto slot = &root;
1110 
1111  while (n && !n.is_leaf() &&
1112  (n->byte < diff || (n->byte == diff && n->bit >= sh))) {
1113  prev = n;
1114  slot = &n->child[slice_index(key[n->byte], n->bit)];
1115  n = *slot;
1116  }
1117 
1118  return {slot, prev};
1119 }
1120 
1121 template <typename Key, typename Value, typename BytesView>
1122 template <typename K>
1123 std::tuple<typename radix_tree<Key, Value, BytesView>::tagged_node_ptr *,
1124  typename radix_tree<Key, Value, BytesView>::tagged_node_ptr>
1125 radix_tree<Key, Value, BytesView>::descend(const K &key, byten_t diff,
1126  bitn_t sh)
1127 {
1128  const tagged_node_ptr *slot;
1129  tagged_node_ptr prev;
1130 
1131  std::tie(slot, prev) =
1132  const_cast<const radix_tree *>(this)->descend(key, diff, sh);
1133 
1134  return {const_cast<tagged_node_ptr *>(slot), prev};
1135 }
1136 
1137 template <typename Key, typename Value, typename BytesView>
1138 template <typename K, typename F, class... Args>
1139 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1140 radix_tree<Key, Value, BytesView>::internal_emplace(const K &k, F &&make_leaf)
1141 {
1142  auto key = bytes_view(k);
1143  auto pop = pool_base(pmemobj_pool_by_ptr(this));
1144 
1145  if (!root) {
1146  transaction::run(pop, [&] { this->root = make_leaf(nullptr); });
1147  return {iterator(root.get_leaf(), &root), true};
1148  }
1149 
1150  /*
1151  * Need to descend the tree twice. First to find a leaf that
1152  * represents a subtree that shares a common prefix with the key.
1153  * This is needed to find out the actual labels between nodes (they
1154  * are not known due to a possible path compression). Second time to
1155  * find the place for the new element.
1156  */
1157  auto leaf = common_prefix_leaf(key);
1158  auto leaf_key = bytes_view(leaf->key());
1159  auto diff = prefix_diff(key, leaf_key);
1160  auto sh = bit_diff(leaf_key, key, diff);
1161 
1162  /* Key exists. */
1163  if (diff == key.size() && leaf_key.size() == key.size())
1164  return {iterator(leaf, &root), false};
1165 
1166  /* Descend into the tree again. */
1167  tagged_node_ptr *slot;
1168  tagged_node_ptr prev;
1169  std::tie(slot, prev) = descend(key, diff, sh);
1170 
1171  auto n = *slot;
1172 
1173  /*
1174  * If the divergence point is at same nib as an existing node, and
1175  * the subtree there is empty, just place our leaf there and we're
1176  * done. Obviously this can't happen if SLICE == 1.
1177  */
1178  if (!n) {
1179  assert(diff < (std::min)(leaf_key.size(), key.size()));
1180 
1181  transaction::run(pop, [&] { *slot = make_leaf(prev); });
1182  return {iterator(slot->get_leaf(), &root), true};
1183  }
1184 
1185  /* New key is a prefix of the leaf key or they are equal. We need to add
1186  * leaf ptr to internal node. */
1187  if (diff == key.size()) {
1188  if (!n.is_leaf() && path_length_equal(key.size(), n)) {
1189  assert(!n->embedded_entry);
1190 
1192  pop, [&] { n->embedded_entry = make_leaf(n); });
1193 
1194  return {iterator(n->embedded_entry.get_leaf(), &root),
1195  true};
1196  }
1197 
1198  /* Path length from root to n is longer than key.size().
1199  * We have to allocate new internal node above n. */
1200  tagged_node_ptr node;
1201  transaction::run(pop, [&] {
1202  node = make_persistent<radix_tree::node>(
1203  parent_ref(n), diff, bitn_t(FIRST_NIB));
1204  node->embedded_entry = make_leaf(node);
1205  node->child[slice_index(leaf_key[diff],
1206  bitn_t(FIRST_NIB))] = n;
1207 
1208  parent_ref(n) = node;
1209  *slot = node;
1210  });
1211 
1212  return {iterator(node->embedded_entry.get_leaf(), &root), true};
1213  }
1214 
1215  if (diff == leaf_key.size()) {
1216  /* Leaf key is a prefix of the new key. We need to convert leaf
1217  * to a node. */
1218  tagged_node_ptr node;
1219  transaction::run(pop, [&] {
1220  /* We have to add new node at the edge from parent to n
1221  */
1222  node = make_persistent<radix_tree::node>(
1223  parent_ref(n), diff, bitn_t(FIRST_NIB));
1224  node->embedded_entry = n;
1225  node->child[slice_index(key[diff], bitn_t(FIRST_NIB))] =
1226  make_leaf(node);
1227 
1228  parent_ref(n) = node;
1229  *slot = node;
1230  });
1231 
1232  return {iterator(node->child[slice_index(key[diff],
1233  bitn_t(FIRST_NIB))]
1234  .get_leaf(),
1235  &root),
1236  true};
1237  }
1238 
1239  /* There is already a subtree at the divergence point
1240  * (slice_index(key[diff], sh)). This means that a tree is vertically
1241  * compressed and we have to "break" this compression and add a new
1242  * node. */
1243  tagged_node_ptr node;
1244  transaction::run(pop, [&] {
1245  node = make_persistent<radix_tree::node>(parent_ref(n), diff,
1246  sh);
1247  node->child[slice_index(leaf_key[diff], sh)] = n;
1248  node->child[slice_index(key[diff], sh)] = make_leaf(node);
1249 
1250  parent_ref(n) = node;
1251  *slot = node;
1252  });
1253 
1254  return {iterator(node->child[slice_index(key[diff], sh)].get_leaf(),
1255  &root),
1256  true};
1257 }
1258 
1287 template <typename Key, typename Value, typename BytesView>
1288 template <class... Args>
1289 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1291  Args &&... args)
1292 {
1293  return internal_emplace(k, [&](tagged_node_ptr parent) {
1294  size_++;
1295  return leaf::make(parent, k, std::forward<Args>(args)...);
1296  });
1297 }
1298 
1325 template <typename Key, typename Value, typename BytesView>
1326 template <class... Args>
1327 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1329 {
1330  auto pop = pool_base(pmemobj_pool_by_ptr(this));
1331  std::pair<iterator, bool> ret;
1332 
1333  transaction::run(pop, [&] {
1334  auto leaf_ = leaf::make(nullptr, std::forward<Args>(args)...);
1335  auto make_leaf = [&](tagged_node_ptr parent) {
1336  leaf_->parent = parent;
1337  size_++;
1338  return leaf_;
1339  };
1340 
1341  ret = internal_emplace(leaf_->key(), make_leaf);
1342 
1343  if (!ret.second)
1344  delete_persistent<leaf>(leaf_);
1345  });
1346 
1347  return ret;
1348 }
1349 
1365 template <typename Key, typename Value, typename BytesView>
1366 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1368 {
1369  return emplace(v);
1370 }
1371 
1387 template <typename Key, typename Value, typename BytesView>
1388 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1390 {
1391  return emplace(std::move(v));
1392 }
1393 
1413 template <typename Key, typename Value, typename BytesView>
1414 template <typename P, typename>
1415 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1417 {
1418  return emplace(std::forward<P>(p));
1419 }
1420 
1432 template <typename Key, typename Value, typename BytesView>
1433 template <typename InputIterator>
1434 void
1436  InputIterator last)
1437 {
1438  for (auto it = first; it != last; it++)
1439  emplace(*it);
1440 }
1441 
1452 template <typename Key, typename Value, typename BytesView>
1453 void
1454 radix_tree<Key, Value, BytesView>::insert(std::initializer_list<value_type> il)
1455 {
1456  insert(il.begin(), il.end());
1457 }
1458 
1483 template <typename Key, typename Value, typename BytesView>
1484 template <class... Args>
1485 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1487 {
1488  return internal_emplace(k, [&](tagged_node_ptr parent) {
1489  size_++;
1490  return leaf::make(parent, std::move(k),
1491  std::forward<Args>(args)...);
1492  });
1493 }
1494 
1523 template <typename Key, typename Value, typename BytesView>
1524 template <typename K, typename BV, class... Args>
1525 auto
1527  typename std::enable_if<
1528  detail::has_is_transparent<BV>::value &&
1529  !std::is_same<typename std::remove_reference<K>::type,
1530  key_type>::value,
1531  std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
1532  bool>>::type
1533 
1534 {
1535  return internal_emplace(k, [&](tagged_node_ptr parent) {
1536  size_++;
1537  return leaf::make(parent, std::forward<K>(k),
1538  std::forward<Args>(args)...);
1539  });
1540 }
1541 
1560 template <typename Key, typename Value, typename BytesView>
1561 template <typename M>
1562 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1564 {
1565  auto ret = try_emplace(k, std::forward<M>(obj));
1566  if (!ret.second)
1567  ret.first.assign_val(std::forward<M>(obj));
1568  return ret;
1569 }
1570 
1589 template <typename Key, typename Value, typename BytesView>
1590 template <typename M>
1591 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1593 {
1594  auto ret = try_emplace(std::move(k), std::forward<M>(obj));
1595  if (!ret.second)
1596  ret.first.assign_val(std::forward<M>(obj));
1597  return ret;
1598 }
1599 
1621 template <typename Key, typename Value, typename BytesView>
1622 template <typename M, typename K, typename>
1623 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1625 {
1626  auto ret = try_emplace(std::forward<K>(k), std::forward<M>(obj));
1627  if (!ret.second)
1628  ret.first.assign_val(std::forward<M>(obj));
1629  return ret;
1630 }
1631 
1641 template <typename Key, typename Value, typename BytesView>
1642 typename radix_tree<Key, Value, BytesView>::size_type
1644 {
1645  return internal_find(k) != nullptr ? 1 : 0;
1646 }
1647 
1660 template <typename Key, typename Value, typename BytesView>
1661 template <typename K, typename>
1662 typename radix_tree<Key, Value, BytesView>::size_type
1664 {
1665  return internal_find(k) != nullptr ? 1 : 0;
1666 }
1667 
1676 template <typename Key, typename Value, typename BytesView>
1679 {
1680  return iterator(internal_find(k), &root);
1681 }
1682 
1691 template <typename Key, typename Value, typename BytesView>
1694 {
1695  return const_iterator(internal_find(k), &root);
1696 }
1697 
1709 template <typename Key, typename Value, typename BytesView>
1710 template <typename K, typename>
1713 {
1714  return iterator(internal_find(k), &root);
1715 }
1716 
1728 template <typename Key, typename Value, typename BytesView>
1729 template <typename K, typename>
1732 {
1733  return const_iterator(internal_find(k), &root);
1734 }
1735 
1736 template <typename Key, typename Value, typename BytesView>
1737 template <typename K>
1740 {
1741  auto key = bytes_view(k);
1742 
1743  auto n = root;
1744  while (n && !n.is_leaf()) {
1745  if (path_length_equal(key.size(), n))
1746  n = n->embedded_entry;
1747  else if (n->byte > key.size())
1748  return nullptr;
1749  else
1750  n = n->child[slice_index(key[n->byte], n->bit)];
1751  }
1752 
1753  if (!n)
1754  return nullptr;
1755 
1756  if (!keys_equal(key, bytes_view(n.get_leaf()->key())))
1757  return nullptr;
1758 
1759  return n.get_leaf();
1760 }
1761 
1769 template <typename Key, typename Value, typename BytesView>
1770 void
1772 {
1773  if (size() != 0)
1774  erase(begin(), end());
1775 }
1776 
1792 template <typename Key, typename Value, typename BytesView>
1795 {
1796  auto pop = pool_base(pmemobj_pool_by_ptr(this));
1797 
1798  transaction::run(pop, [&] {
1799  auto *leaf = pos.leaf_;
1800  auto parent = leaf->parent;
1801 
1802  delete_persistent<radix_tree::leaf>(
1804 
1805  size_--;
1806 
1807  /* was root */
1808  if (!parent) {
1809  this->root = nullptr;
1810  pos = begin();
1811  return;
1812  }
1813 
1814  ++pos;
1815 
1816  /* It's safe to cast because we're inside non-const method. */
1817  const_cast<tagged_node_ptr &>(*parent->find_child(leaf)) =
1818  nullptr;
1819 
1820  /* Compress the tree vertically. */
1821  auto n = parent;
1822  parent = n->parent;
1823  tagged_node_ptr only_child = nullptr;
1824  for (size_t i = 0; i < SLNODES; i++) {
1825  if (n->child[i]) {
1826  if (only_child) {
1827  /* more than one child */
1828  return;
1829  }
1830  only_child = n->child[i];
1831  }
1832  }
1833 
1834  if (only_child && n->embedded_entry) {
1835  /* There are actually 2 "children" so we can't compress.
1836  */
1837  return;
1838  } else if (n->embedded_entry) {
1839  only_child = n->embedded_entry;
1840  }
1841 
1842  assert(only_child);
1843  parent_ref(only_child) = n->parent;
1844 
1845  auto *child_slot = parent
1846  ? const_cast<tagged_node_ptr *>(&*parent->find_child(n))
1847  : &root;
1848  *child_slot = only_child;
1849 
1850  delete_persistent<radix_tree::node>(n.get_node());
1851  });
1852 
1853  return iterator(const_cast<typename iterator::leaf_ptr>(pos.leaf_),
1854  &root);
1855 }
1856 
1870 template <typename Key, typename Value, typename BytesView>
1873  const_iterator last)
1874 {
1875  auto pop = pool_base(pmemobj_pool_by_ptr(this));
1876 
1877  transaction::run(pop, [&] {
1878  while (first != last)
1879  first = erase(first);
1880  });
1881 
1882  return iterator(const_cast<typename iterator::leaf_ptr>(first.leaf_),
1883  &root);
1884 }
1885 
1898 template <typename Key, typename Value, typename BytesView>
1899 typename radix_tree<Key, Value, BytesView>::size_type
1901 {
1902  auto it = const_iterator(internal_find(k), &root);
1903 
1904  if (it == end())
1905  return 0;
1906 
1907  erase(it);
1908 
1909  return 1;
1910 }
1911 
1927 template <typename Key, typename Value, typename BytesView>
1928 template <typename K, typename>
1929 typename radix_tree<Key, Value, BytesView>::size_type
1931 {
1932  auto it = const_iterator(internal_find(k), &root);
1933 
1934  if (it == end())
1935  return 0;
1936 
1937  erase(it);
1938 
1939  return 1;
1940 }
1941 
1942 template <typename Key, typename Value, typename BytesView>
1943 template <bool Lower, typename K>
1946 {
1947  auto key = bytes_view(k);
1948  auto pop = pool_base(pmemobj_pool_by_ptr(this));
1949 
1950  if (!root)
1951  return end();
1952 
1953  /*
1954  * Need to descend the tree twice. First to find a leaf that
1955  * represents a subtree that shares a common prefix with the key.
1956  * This is needed to find out the actual labels between nodes (they
1957  * are not known due to a possible path compression). Second time to
1958  * get the actual element.
1959  */
1960  auto leaf = common_prefix_leaf(key);
1961  auto leaf_key = bytes_view(leaf->key());
1962  auto diff = prefix_diff(key, leaf_key);
1963  auto sh = bit_diff(leaf_key, key, diff);
1964 
1965  /* Key exists. */
1966  if (diff == key.size() && leaf_key.size() == key.size()) {
1967  if (Lower)
1968  return const_iterator(leaf, &root);
1969  else
1970  return ++const_iterator(leaf, &root);
1971  }
1972 
1973  /* Descend into the tree again. */
1974  const tagged_node_ptr *slot;
1975  tagged_node_ptr prev;
1976  std::tie(slot, prev) = descend(key, diff, sh);
1977 
1978  if (!*slot) {
1979  leaf = next_leaf<node::direction::Forward>(
1980  prev->template make_iterator<node::direction::Forward>(
1981  slot),
1982  prev);
1983 
1984  return const_iterator(leaf, &root);
1985  }
1986 
1987  /* The looked-for key is a prefix of the leaf key. The target node must
1988  * be the smallest leaf within *slot subtree. Key represented by a path
1989  * from root to n is larger than the looked-for key. Additionally keys
1990  * under right siblings of *slot are > key and keys under left siblings
1991  * are < key. */
1992  if (diff == key.size()) {
1993  leaf = find_leaf<node::direction::Forward>(*slot);
1994  return const_iterator(leaf, &root);
1995  }
1996 
1997  /* Leaf's key is a prefix of the looked-for key. Leaf's key is the
1998  * biggest key less than the looked-for key.
1999  * The target node must be the next leaf. */
2000  if (diff == leaf_key.size())
2001  return ++const_iterator(leaf, &root);
2002 
2003  /* *slot is the point of divergence. */
2004  assert(diff < leaf_key.size() && diff < key.size());
2005 
2006  /* The target node must be within *slot subtree. The left siblings
2007  * of *slot are all less than the looked-for key. */
2008  if (compare(key, leaf_key, diff) < 0) {
2009  leaf = find_leaf<node::direction::Forward>(*slot);
2010  return const_iterator(leaf, &root);
2011  }
2012 
2013  if (slot == &root) {
2014  return const_iterator(nullptr, &root);
2015  }
2016 
2017  /* Since looked-for key is larger than *slot, the target node must be
2018  * within subtree of a right sibling of *slot. */
2019  leaf = next_leaf<node::direction::Forward>(
2020  prev->template make_iterator<node::direction::Forward>(slot),
2021  prev);
2022 
2023  return const_iterator(leaf, &root);
2024 }
2025 
2036 template <typename Key, typename Value, typename BytesView>
2037 typename radix_tree<Key, Value, BytesView>::const_iterator
2039 {
2040  return internal_bound<true>(k);
2041 }
2042 
2053 template <typename Key, typename Value, typename BytesView>
2056 {
2057  auto it = const_cast<const radix_tree *>(this)->lower_bound(k);
2058  return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2059  &root);
2060 }
2061 
2075 template <typename Key, typename Value, typename BytesView>
2076 template <typename K, typename>
2079 {
2080  auto it = const_cast<const radix_tree *>(this)->lower_bound(k);
2081  return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2082  &root);
2083 }
2084 
2098 template <typename Key, typename Value, typename BytesView>
2099 template <typename K, typename>
2102 {
2103  return internal_bound<true>(k);
2104 }
2105 
2116 template <typename Key, typename Value, typename BytesView>
2119 {
2120  return internal_bound<false>(k);
2121 }
2122 
2133 template <typename Key, typename Value, typename BytesView>
2136 {
2137  auto it = const_cast<const radix_tree *>(this)->upper_bound(k);
2138  return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2139  &root);
2140 }
2141 
2155 template <typename Key, typename Value, typename BytesView>
2156 template <typename K, typename>
2159 {
2160  auto it = const_cast<const radix_tree *>(this)->upper_bound(k);
2161  return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2162  &root);
2163 }
2164 
2178 template <typename Key, typename Value, typename BytesView>
2179 template <typename K, typename>
2182 {
2183  return internal_bound<false>(k);
2184 }
2185 
2192 template <typename Key, typename Value, typename BytesView>
2195 {
2196  auto const_begin = const_cast<const radix_tree *>(this)->begin();
2197  return iterator(
2198  const_cast<typename iterator::leaf_ptr>(const_begin.leaf_),
2199  &root);
2200 }
2201 
2209 template <typename Key, typename Value, typename BytesView>
2212 {
2213  auto const_end = const_cast<const radix_tree *>(this)->end();
2214  return iterator(
2215  const_cast<typename iterator::leaf_ptr>(const_end.leaf_),
2216  &root);
2217 }
2218 
2225 template <typename Key, typename Value, typename BytesView>
2228 {
2229  if (!root)
2230  return const_iterator(nullptr, &root);
2231 
2232  return const_iterator(
2233  radix_tree::find_leaf<radix_tree::node::direction::Forward>(
2234  root),
2235  &root);
2236 }
2237 
2245 template <typename Key, typename Value, typename BytesView>
2248 {
2249  return const_iterator(nullptr, &root);
2250 }
2251 
2258 template <typename Key, typename Value, typename BytesView>
2261 {
2262  return cbegin();
2263 }
2264 
2272 template <typename Key, typename Value, typename BytesView>
2275 {
2276  return cend();
2277 }
2278 
2284 template <typename Key, typename Value, typename BytesView>
2285 typename radix_tree<Key, Value, BytesView>::reverse_iterator
2287 {
2288  return reverse_iterator(end());
2289 }
2290 
2297 template <typename Key, typename Value, typename BytesView>
2298 typename radix_tree<Key, Value, BytesView>::reverse_iterator
2300 {
2301  return reverse_iterator(begin());
2302 }
2303 
2309 template <typename Key, typename Value, typename BytesView>
2310 typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
2312 {
2313  return const_reverse_iterator(cend());
2314 }
2315 
2322 template <typename Key, typename Value, typename BytesView>
2323 typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
2325 {
2326  return const_reverse_iterator(cbegin());
2327 }
2328 
2329 template <typename Key, typename Value, typename BytesView>
2330 typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
2332 {
2333  return const_reverse_iterator(cend());
2334 }
2335 
2336 template <typename Key, typename Value, typename BytesView>
2337 typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
2339 {
2340  return const_reverse_iterator(cbegin());
2341 }
2342 
2343 template <typename Key, typename Value, typename BytesView>
2344 void
2345 radix_tree<Key, Value, BytesView>::print_rec(std::ostream &os,
2346  radix_tree::tagged_node_ptr n)
2347 {
2348  if (!n.is_leaf()) {
2349  os << "\"" << n.get_node() << "\""
2350  << " [style=filled,color=\"blue\"]" << std::endl;
2351  os << "\"" << n.get_node() << "\" [label=\"byte:" << n->byte
2352  << ", bit:" << int(n->bit) << "\"]" << std::endl;
2353 
2354  auto parent = n->parent ? n->parent.get_node() : 0;
2355  os << "\"" << n.get_node() << "\" -> "
2356  << "\"" << parent << "\" [label=\"parent\"]" << std::endl;
2357 
2358  for (auto it = n->begin(); it != n->end(); ++it) {
2359  if (!(*it))
2360  continue;
2361 
2362  auto ch = it->is_leaf() ? (void *)it->get_leaf()
2363  : (void *)it->get_node();
2364 
2365  os << "\"" << n.get_node() << "\" -> \"" << ch << "\""
2366  << std::endl;
2367  print_rec(os, *it);
2368  }
2369  } else {
2370  auto bv = bytes_view(n.get_leaf()->key());
2371 
2372  os << "\"" << n.get_leaf()
2373  << "\" [style=filled,color=\"green\"]" << std::endl;
2374  os << "\"" << n.get_leaf() << "\" [label=\"key:";
2375 
2376  for (size_t i = 0; i < bv.size(); i++)
2377  os << bv[i];
2378 
2379  os << "\"]" << std::endl;
2380 
2381  auto parent = n.get_leaf()->parent
2382  ? n.get_leaf()->parent.get_node()
2383  : nullptr;
2384 
2385  os << "\"" << n.get_leaf() << "\" -> \"" << parent
2386  << "\" [label=\"parent\"]" << std::endl;
2387 
2388  if (parent && n == parent->embedded_entry) {
2389  os << "{rank=same;\"" << parent << "\";\""
2390  << n.get_leaf() << "\"}" << std::endl;
2391  }
2392  }
2393 }
2394 
2398 template <typename K, typename V, typename BV>
2399 std::ostream &
2400 operator<<(std::ostream &os, const radix_tree<K, V, BV> &tree)
2401 {
2402  os << "digraph Radix {" << std::endl;
2403 
2404  if (tree.root)
2405  radix_tree<K, V, BV>::print_rec(os, tree.root);
2406 
2407  os << "}" << std::endl;
2408 
2409  return os;
2410 }
2411 
2412 /*
2413  * internal: slice_index -- return index of child at the given nib
2414  */
2415 template <typename Key, typename Value, typename BytesView>
2416 unsigned
2417 radix_tree<Key, Value, BytesView>::slice_index(char b, uint8_t bit)
2418 {
2419  return static_cast<unsigned>(b >> bit) & NIB;
2420 }
2421 
2422 template <typename Key, typename Value, typename BytesView>
2423 radix_tree<Key, Value, BytesView>::tagged_node_ptr::tagged_node_ptr(
2424  std::nullptr_t)
2425  : ptr(nullptr)
2426 {
2427  assert(!(bool)*this);
2428 }
2429 
2430 template <typename Key, typename Value, typename BytesView>
2431 radix_tree<Key, Value, BytesView>::tagged_node_ptr::tagged_node_ptr(
2432  const persistent_ptr<leaf> &ptr)
2433  : ptr(add_tag(ptr.get()))
2434 {
2435  assert(get_leaf() == ptr.get());
2436 }
2437 
2438 template <typename Key, typename Value, typename BytesView>
2439 radix_tree<Key, Value, BytesView>::tagged_node_ptr::tagged_node_ptr(
2440  const persistent_ptr<node> &ptr)
2441  : ptr(ptr.get())
2442 {
2443  assert(get_node() == ptr.get());
2444 }
2445 
2446 template <typename Key, typename Value, typename BytesView>
2447 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr &
2448  radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator=(
2449  std::nullptr_t)
2450 {
2451  ptr = nullptr;
2452  assert(!(bool)*this);
2453 
2454  return *this;
2455 }
2456 
2457 template <typename Key, typename Value, typename BytesView>
2458 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr &
2459 radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator=(
2460  const persistent_ptr<leaf> &rhs)
2461 {
2462  ptr = add_tag(rhs.get());
2463  assert(get_leaf() == rhs.get());
2464 
2465  return *this;
2466 }
2467 
2468 template <typename Key, typename Value, typename BytesView>
2469 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr &
2470 radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator=(
2471  const persistent_ptr<node> &rhs)
2472 {
2473  ptr = rhs.get();
2474  assert(get_node() == rhs.get());
2475 
2476  return *this;
2477 }
2478 
2479 template <typename Key, typename Value, typename BytesView>
2480 bool
2482  const radix_tree::tagged_node_ptr &rhs) const
2483 {
2484  return ptr.to_byte_pointer() == rhs.ptr.to_byte_pointer();
2485 }
2486 
2487 template <typename Key, typename Value, typename BytesView>
2488 bool
2490  const radix_tree::tagged_node_ptr &rhs) const
2491 {
2492  return !(*this == rhs);
2493 }
2494 
2495 template <typename Key, typename Value, typename BytesView>
2496 bool
2498  const radix_tree::leaf *rhs) const
2499 {
2500  return is_leaf() && get_leaf() == rhs;
2501 }
2502 
2503 template <typename Key, typename Value, typename BytesView>
2504 bool
2506  const radix_tree::leaf *rhs) const
2507 {
2508  return !(*this == rhs);
2509 }
2510 
2511 template <typename Key, typename Value, typename BytesView>
2512 void
2514 {
2515  ptr.swap(rhs.ptr);
2516 }
2517 
2518 template <typename Key, typename Value, typename BytesView>
2519 void *
2520 radix_tree<Key, Value, BytesView>::tagged_node_ptr::add_tag(
2521  radix_tree::leaf *ptr) const
2522 {
2523  auto tagged = reinterpret_cast<uintptr_t>(ptr) | uintptr_t(IS_LEAF);
2524  return reinterpret_cast<radix_tree::leaf *>(tagged);
2525 }
2526 
2527 template <typename Key, typename Value, typename BytesView>
2528 void *
2529 radix_tree<Key, Value, BytesView>::tagged_node_ptr::remove_tag(void *ptr) const
2530 {
2531  auto untagged = reinterpret_cast<uintptr_t>(ptr) & ~uintptr_t(IS_LEAF);
2532  return reinterpret_cast<void *>(untagged);
2533 }
2534 
2535 template <typename Key, typename Value, typename BytesView>
2536 bool
2537 radix_tree<Key, Value, BytesView>::tagged_node_ptr::is_leaf() const
2538 {
2539  auto value = reinterpret_cast<uintptr_t>(ptr.to_void_pointer());
2540  return value & uintptr_t(IS_LEAF);
2541 }
2542 
2543 template <typename Key, typename Value, typename BytesView>
2544 typename radix_tree<Key, Value, BytesView>::leaf *
2545 radix_tree<Key, Value, BytesView>::tagged_node_ptr::get_leaf() const
2546 {
2547  assert(is_leaf());
2548  return static_cast<radix_tree::leaf *>(
2549  remove_tag(ptr.to_void_pointer()));
2550 }
2551 
2552 template <typename Key, typename Value, typename BytesView>
2553 typename radix_tree<Key, Value, BytesView>::node *
2554 radix_tree<Key, Value, BytesView>::tagged_node_ptr::get_node() const
2555 {
2556  assert(!is_leaf());
2557  return static_cast<radix_tree::node *>(ptr.to_void_pointer());
2558 }
2559 
2560 template <typename Key, typename Value, typename BytesView>
2561 radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator bool() const
2562  noexcept
2563 {
2564  return remove_tag(ptr.to_void_pointer()) != nullptr;
2565 }
2566 
2567 template <typename Key, typename Value, typename BytesView>
2568 typename radix_tree<Key, Value, BytesView>::node *
2569  radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator->() const
2570  noexcept
2571 {
2572  return get_node();
2573 }
2574 
2575 template <typename Key, typename Value, typename BytesView>
2576 radix_tree<Key, Value, BytesView>::node::forward_iterator::forward_iterator(
2577  pointer child, const node *n)
2578  : child(child), n(n)
2579 {
2580 }
2581 
2582 template <typename Key, typename Value, typename BytesView>
2583 typename radix_tree<Key, Value, BytesView>::node::forward_iterator
2585 {
2586  if (child == &n->embedded_entry)
2587  child = &n->child[0];
2588  else
2589  child++;
2590 
2591  return *this;
2592 }
2593 
2594 template <typename Key, typename Value, typename BytesView>
2595 radix_tree<Key, Value, BytesView>::node::node(tagged_node_ptr parent,
2596  byten_t byte, bitn_t bit)
2597  : parent(parent), byte(byte), bit(bit)
2598 {
2599 }
2600 
2601 template <typename Key, typename Value, typename BytesView>
2602 typename radix_tree<Key, Value, BytesView>::node::forward_iterator
2604 {
2605  if (child == &n->child[0])
2606  child = &n->embedded_entry;
2607  else
2608  child--;
2609 
2610  return *this;
2611 }
2612 
2613 template <typename Key, typename Value, typename BytesView>
2614 typename radix_tree<Key, Value, BytesView>::node::forward_iterator
2616 {
2617  forward_iterator tmp(child, n);
2618  operator++();
2619  return tmp;
2620 }
2621 
2622 template <typename Key, typename Value, typename BytesView>
2623 typename radix_tree<Key, Value, BytesView>::node::forward_iterator::reference
2624  radix_tree<Key, Value, BytesView>::node::forward_iterator::operator*()
2625  const
2626 {
2627  return *child;
2628 }
2629 
2630 template <typename Key, typename Value, typename BytesView>
2631 typename radix_tree<Key, Value, BytesView>::node::forward_iterator::pointer
2632  radix_tree<Key, Value, BytesView>::node::forward_iterator::operator->()
2633  const
2634 {
2635  return child;
2636 }
2637 
2638 template <typename Key, typename Value, typename BytesView>
2639 typename radix_tree<Key, Value, BytesView>::node::forward_iterator::pointer
2640 radix_tree<Key, Value, BytesView>::node::forward_iterator::get_node() const
2641 {
2642  return n;
2643 }
2644 
2645 template <typename Key, typename Value, typename BytesView>
2646 bool
2648  const forward_iterator &rhs) const
2649 {
2650  return child == rhs.child && n == rhs.n;
2651 }
2652 
2653 template <typename Key, typename Value, typename BytesView>
2654 bool
2656  const forward_iterator &rhs) const
2657 {
2658  return child != rhs.child || n != rhs.n;
2659 }
2660 
2661 template <typename Key, typename Value, typename BytesView>
2662 template <bool Direction>
2663 typename std::enable_if<
2664  Direction ==
2665  radix_tree<Key, Value, BytesView>::node::direction::Forward,
2666  typename radix_tree<Key, Value,
2667  BytesView>::node::forward_iterator>::type
2669 {
2670  return forward_iterator(&embedded_entry, this);
2671 }
2672 
2673 template <typename Key, typename Value, typename BytesView>
2674 template <bool Direction>
2675 typename std::enable_if<
2676  Direction ==
2677  radix_tree<Key, Value, BytesView>::node::direction::Forward,
2678  typename radix_tree<Key, Value,
2679  BytesView>::node::forward_iterator>::type
2681 {
2682  return forward_iterator(&child[SLNODES], this);
2683 }
2684 
2685 template <typename Key, typename Value, typename BytesView>
2686 template <bool Direction>
2687 typename std::enable_if<
2688  Direction ==
2689  radix_tree<Key, Value, BytesView>::node::direction::Reverse,
2690  typename radix_tree<Key, Value,
2691  BytesView>::node::reverse_iterator>::type
2693 {
2694  return reverse_iterator(end<direction::Forward>());
2695 }
2696 
2697 template <typename Key, typename Value, typename BytesView>
2698 template <bool Direction>
2699 typename std::enable_if<
2700  Direction ==
2701  radix_tree<Key, Value, BytesView>::node::direction::Reverse,
2702  typename radix_tree<Key, Value,
2703  BytesView>::node::reverse_iterator>::type
2705 {
2706  return reverse_iterator(begin<direction::Forward>());
2707 }
2708 
2709 template <typename Key, typename Value, typename BytesView>
2710 template <bool Direction, typename Ptr>
2711 auto
2712 radix_tree<Key, Value, BytesView>::node::find_child(const Ptr &n) const
2713  -> decltype(begin<Direction>())
2714 {
2715  return std::find(begin<Direction>(), end<Direction>(), n);
2716 }
2717 
2718 template <typename Key, typename Value, typename BytesView>
2719 template <bool Direction, typename Enable>
2720 auto
2721 radix_tree<Key, Value, BytesView>::node::make_iterator(
2722  const tagged_node_ptr *ptr) const -> decltype(begin<Direction>())
2723 {
2724  return forward_iterator(ptr, this);
2725 }
2726 
2727 template <typename Key, typename Value, typename BytesView>
2728 template <bool IsConst>
2729 radix_tree<Key, Value, BytesView>::radix_tree_iterator<
2730  IsConst>::radix_tree_iterator(leaf_ptr leaf_, node_ptr root)
2731  : leaf_(leaf_), root(root)
2732 {
2733 }
2734 
2735 template <typename Key, typename Value, typename BytesView>
2736 template <bool IsConst>
2737 template <bool C, typename Enable>
2738 radix_tree<Key, Value, BytesView>::radix_tree_iterator<
2739  IsConst>::radix_tree_iterator(const radix_tree_iterator<false> &rhs)
2740  : leaf_(rhs.leaf_)
2741 {
2742 }
2743 
2744 template <typename Key, typename Value, typename BytesView>
2745 template <bool IsConst>
2746 typename radix_tree<Key, Value,
2747  BytesView>::template radix_tree_iterator<IsConst>::reference
2748  radix_tree<Key, Value,
2749  BytesView>::radix_tree_iterator<IsConst>::operator*() const
2750 {
2751  assert(leaf_);
2752  return *leaf_;
2753 }
2754 
2755 template <typename Key, typename Value, typename BytesView>
2756 template <bool IsConst>
2757 typename radix_tree<Key, Value,
2758  BytesView>::template radix_tree_iterator<IsConst>::pointer
2759  radix_tree<Key, Value,
2760  BytesView>::radix_tree_iterator<IsConst>::operator->() const
2761 {
2762  assert(leaf_);
2763  return leaf_;
2764 }
2765 
2775 template <typename Key, typename Value, typename BytesView>
2776 template <bool IsConst>
2777 template <typename V, typename Enable>
2778 void
2780  string_view rhs)
2781 {
2782  auto pop = pool_base(pmemobj_pool_by_ptr(leaf_));
2783 
2784  if (rhs.size() <= leaf_->value().capacity()) {
2785  transaction::run(pop, [&] { leaf_->value() = rhs; });
2786  } else {
2787  tagged_node_ptr *slot;
2788 
2789  if (!leaf_->parent) {
2790  assert(root->get_leaf() == leaf_);
2791  slot = root;
2792  } else {
2793  slot = const_cast<tagged_node_ptr *>(
2794  &*leaf_->parent->find_child(leaf_));
2795  }
2796 
2797  auto old_leaf = leaf_;
2798 
2799  transaction::run(pop, [&] {
2800  *slot = leaf::make(old_leaf->parent, old_leaf->key(),
2801  rhs);
2802  delete_persistent<typename radix_tree::leaf>(old_leaf);
2803  });
2804 
2805  leaf_ = slot->get_leaf();
2806  }
2807 }
2808 
2814 template <typename Key, typename Value, typename BytesView>
2815 template <bool IsConst>
2816 template <typename T, typename V, typename Enable>
2817 void
2819  T &&rhs)
2820 {
2821  auto pop = pool_base(pmemobj_pool_by_ptr(leaf_));
2822 
2823  transaction::run(pop, [&] { leaf_->value() = std::forward<T>(rhs); });
2824 }
2825 
2826 template <typename Key, typename Value, typename BytesView>
2827 template <bool IsConst>
2828 typename radix_tree<Key, Value,
2829  BytesView>::template radix_tree_iterator<IsConst> &
2831 {
2832  assert(leaf_);
2833 
2834  /* leaf is root, there is no other leaf in the tree */
2835  if (!leaf_->parent)
2836  leaf_ = nullptr;
2837  else {
2838  auto it = leaf_->parent->template find_child<
2839  radix_tree::node::direction::Forward>(leaf_);
2840 
2841  leaf_ = const_cast<leaf_ptr>(
2842  next_leaf<radix_tree::node::direction::Forward>(
2843  it, leaf_->parent));
2844  }
2845 
2846  return *this;
2847 }
2848 
2849 template <typename Key, typename Value, typename BytesView>
2850 template <bool IsConst>
2851 typename radix_tree<Key, Value,
2852  BytesView>::template radix_tree_iterator<IsConst> &
2854 {
2855  if (!leaf_) {
2856  /* this == end() */
2857  leaf_ = const_cast<leaf_ptr>(
2858  radix_tree::find_leaf<
2859  radix_tree::node::direction::Reverse>(*root));
2860  } else {
2861  /* Iterator must be decrementable. */
2862  assert(leaf_->parent);
2863 
2864  auto it = leaf_->parent->template find_child<
2865  radix_tree::node::direction::Reverse>(leaf_);
2866 
2867  leaf_ = const_cast<leaf_ptr>(
2868  next_leaf<radix_tree::node::direction::Reverse>(
2869  it, leaf_->parent));
2870  }
2871 
2872  return *this;
2873 }
2874 
2875 template <typename Key, typename Value, typename BytesView>
2876 template <bool IsConst>
2877 typename radix_tree<Key, Value,
2878  BytesView>::template radix_tree_iterator<IsConst>
2880 {
2881  auto tmp = *this;
2882 
2883  ++(*this);
2884 
2885  return tmp;
2886 }
2887 
2888 template <typename Key, typename Value, typename BytesView>
2889 template <bool IsConst>
2890 typename radix_tree<Key, Value,
2891  BytesView>::template radix_tree_iterator<IsConst>
2893 {
2894  auto tmp = *this;
2895 
2896  --(*this);
2897 
2898  return tmp;
2899 }
2900 
2901 template <typename Key, typename Value, typename BytesView>
2902 template <bool IsConst>
2903 template <bool C>
2904 bool
2906  const radix_tree_iterator<C> &rhs) const
2907 {
2908  return leaf_ != rhs.leaf_;
2909 }
2910 
2911 template <typename Key, typename Value, typename BytesView>
2912 template <bool IsConst>
2913 template <bool C>
2914 bool
2916  const radix_tree_iterator<C> &rhs) const
2917 {
2918  return !(*this != rhs);
2919 }
2920 
2921 /*
2922  * Returns next leaf (either with smaller or larger key, depending on
2923  * ChildIterator type). This function might need to traverse the
2924  * tree upwards.
2925  */
2926 template <typename Key, typename Value, typename BytesView>
2927 template <bool Direction, typename Iterator>
2928 typename radix_tree<Key, Value, BytesView>::leaf *
2929 radix_tree<Key, Value, BytesView>::next_leaf(Iterator node,
2930  tagged_node_ptr parent)
2931 {
2932  do {
2933  ++node;
2934  } while (node != parent->template end<Direction>() && !(*node));
2935 
2936  /* No more children on this level, need to go up. */
2937  if (node == parent->template end<Direction>()) {
2938  auto p = parent->parent;
2939  if (!p) // parent == root
2940  return nullptr;
2941 
2942  auto p_it = p->template find_child<Direction>(parent);
2943  return next_leaf<Direction>(p_it, p);
2944  }
2945 
2946  return find_leaf<Direction>(*node);
2947 }
2948 
2949 /*
2950  * Returns smallest (or biggest, depending on ChildIterator) leaf
2951  * in a subtree.
2952  */
2953 template <typename Key, typename Value, typename BytesView>
2954 template <bool Direction>
2955 typename radix_tree<Key, Value, BytesView>::leaf *
2956 radix_tree<Key, Value, BytesView>::find_leaf(
2957  typename radix_tree<Key, Value, BytesView>::tagged_node_ptr n)
2958 {
2959  assert(n);
2960 
2961  if (n.is_leaf())
2962  return n.get_leaf();
2963 
2964  for (auto it = n->template begin<Direction>();
2965  it != n->template end<Direction>(); ++it) {
2966  if (*it)
2967  return find_leaf<Direction>(*it);
2968  }
2969 
2970  /* There must be at least one leaf at the bottom. */
2971  std::abort();
2972 }
2973 
2974 template <typename Key, typename Value, typename BytesView>
2975 template <typename... Args>
2976 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
2977 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
2978  Args &&... args)
2979 {
2980  auto ptr = make_internal(std::forward<Args>(args)...);
2981  ptr->parent = parent;
2982 
2983  return ptr;
2984 }
2985 
2986 template <typename Key, typename Value, typename BytesView>
2987 Key &
2988 radix_tree<Key, Value, BytesView>::leaf::key()
2989 {
2990  return *reinterpret_cast<Key *>(this + 1);
2991 }
2992 
2993 template <typename Key, typename Value, typename BytesView>
2994 Value &
2995 radix_tree<Key, Value, BytesView>::leaf::value()
2996 {
2997  auto key_dst = reinterpret_cast<char *>(this + 1);
2998  auto val_dst = reinterpret_cast<Value *>(
2999  key_dst + total_sizeof<Key>::value(key()));
3000 
3001  return *reinterpret_cast<Value *>(val_dst);
3002 }
3003 
3004 template <typename Key, typename Value, typename BytesView>
3005 const Key &
3006 radix_tree<Key, Value, BytesView>::leaf::key() const
3007 {
3008  return *reinterpret_cast<const Key *>(this + 1);
3009 }
3010 
3011 template <typename Key, typename Value, typename BytesView>
3012 const Value &
3013 radix_tree<Key, Value, BytesView>::leaf::value() const
3014 {
3015  auto key_dst = reinterpret_cast<const char *>(this + 1);
3016  auto val_dst = reinterpret_cast<const Value *>(
3017  key_dst + total_sizeof<Key>::value(key()));
3018 
3019  return *reinterpret_cast<const Value *>(val_dst);
3020 }
3021 
3022 template <typename Key, typename Value, typename BytesView>
3023 radix_tree<Key, Value, BytesView>::leaf::~leaf()
3024 {
3025  detail::destroy<Key>(key());
3026  detail::destroy<Value>(value());
3027 }
3028 
3029 template <typename Key, typename Value, typename BytesView>
3030 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3031 radix_tree<Key, Value, BytesView>::leaf::make_internal()
3032 {
3033  auto t = std::make_tuple();
3034  return make_internal(std::piecewise_construct, t, t,
3035  typename detail::make_index_sequence<>::type{},
3036  typename detail::make_index_sequence<>::type{});
3037 }
3038 
3039 template <typename Key, typename Value, typename BytesView>
3040 template <typename... Args1, typename... Args2>
3041 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3042 radix_tree<Key, Value, BytesView>::leaf::make_internal(
3043  std::piecewise_construct_t pc, std::tuple<Args1...> first_args,
3044  std::tuple<Args2...> second_args)
3045 {
3046  return make_internal(
3047  pc, first_args, second_args,
3048  typename detail::make_index_sequence<Args1...>::type{},
3049  typename detail::make_index_sequence<Args2...>::type{});
3050 }
3051 
3052 template <typename Key, typename Value, typename BytesView>
3053 template <typename K, typename V>
3054 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3055 radix_tree<Key, Value, BytesView>::leaf::make_internal(K &&k, V &&v)
3056 {
3057  return make_internal(std::piecewise_construct,
3058  std::forward_as_tuple(std::forward<K>(k)),
3059  std::forward_as_tuple(std::forward<V>(v)));
3060 }
3061 
3062 template <typename Key, typename Value, typename BytesView>
3063 template <typename K, typename V>
3064 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3065 radix_tree<Key, Value, BytesView>::leaf::make_internal(const K &k, const V &v)
3066 {
3067  return make_internal(std::piecewise_construct, std::forward_as_tuple(k),
3068  std::forward_as_tuple(v));
3069 }
3070 
3071 template <typename Key, typename Value, typename BytesView>
3072 template <typename K, typename V>
3073 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3074 radix_tree<Key, Value, BytesView>::leaf::make_internal(detail::pair<K, V> &&p)
3075 {
3076  return make_internal(std::piecewise_construct,
3077  std::forward_as_tuple(std::forward<K>(p.first)),
3078  std::forward_as_tuple(std::forward<V>(p.second)));
3079 }
3080 
3081 template <typename Key, typename Value, typename BytesView>
3082 template <typename K, typename V>
3083 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3084 radix_tree<Key, Value, BytesView>::leaf::make_internal(
3085  const detail::pair<K, V> &p)
3086 {
3087  return make_internal(std::piecewise_construct,
3088  std::forward_as_tuple(p.first),
3089  std::forward_as_tuple(p.second));
3090 }
3091 
3092 template <typename Key, typename Value, typename BytesView>
3093 template <typename K, typename V>
3094 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3095 radix_tree<Key, Value, BytesView>::leaf::make_internal(std::pair<K, V> &&p)
3096 {
3097  return make_internal(std::piecewise_construct,
3098  std::forward_as_tuple(std::forward<K>(p.first)),
3099  std::forward_as_tuple(std::forward<V>(p.second)));
3100 }
3101 
3102 template <typename Key, typename Value, typename BytesView>
3103 template <typename K, typename V>
3104 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3105 radix_tree<Key, Value, BytesView>::leaf::make_internal(const std::pair<K, V> &p)
3106 {
3107  return make_internal(std::piecewise_construct,
3108  std::forward_as_tuple(p.first),
3109  std::forward_as_tuple(p.second));
3110 }
3111 
3112 template <typename Key, typename Value, typename BytesView>
3113 template <typename... Args1, typename... Args2, size_t... I1, size_t... I2>
3114 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3115 radix_tree<Key, Value, BytesView>::leaf::make_internal(
3116  std::piecewise_construct_t, std::tuple<Args1...> &first_args,
3117  std::tuple<Args2...> &second_args, detail::index_sequence<I1...>,
3118  detail::index_sequence<I2...>)
3119 {
3120  standard_alloc_policy<void> a;
3121  auto key_size = total_sizeof<Key>::value(std::get<I1>(first_args)...);
3122  auto val_size =
3123  total_sizeof<Value>::value(std::get<I2>(second_args)...);
3124  auto ptr = static_cast<persistent_ptr<leaf>>(
3125  a.allocate(sizeof(leaf) + key_size + val_size));
3126 
3127  auto key_dst = reinterpret_cast<Key *>(ptr.get() + 1);
3128  auto val_dst = reinterpret_cast<Value *>(
3129  reinterpret_cast<char *>(key_dst) + key_size);
3130 
3131  new (ptr.get()) leaf();
3132  new (key_dst) Key(std::forward<Args1>(std::get<I1>(first_args))...);
3133  new (val_dst) Value(std::forward<Args2>(std::get<I2>(second_args))...);
3134 
3135  return ptr;
3136 }
3137 
3138 template <typename Key, typename Value, typename BytesView>
3139 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3140 radix_tree<Key, Value, BytesView>::leaf::make_internal(const leaf &other)
3141 {
3142  return make_internal(other.key(), other.value());
3143 }
3144 
3151 template <typename Key, typename Value, typename BytesView>
3152 void
3154 {
3155  if (nullptr == pmemobj_pool_by_ptr(this))
3156  throw pmem::pool_error("Invalid pool handle.");
3157 }
3158 
3166 template <typename Key, typename Value, typename BytesView>
3167 void
3169 {
3170  if (pmemobj_tx_stage() != TX_STAGE_WORK)
3172  "Function called out of transaction scope.");
3173 }
3174 
3178 template <typename Key, typename Value, typename BytesView>
3179 void
3182 {
3183  lhs.swap(rhs);
3184 }
3185 
3186 } /* namespace experimental */
3187 } /* namespace obj */
3188 
3189 namespace detail
3190 {
3191 template <typename T>
3192 struct bytes_view<T, typename std::enable_if<is_string<T>::value>::type> {
3193  using CharT = typename T::value_type;
3194  using Traits = typename T::traits_type;
3195 
3196  template <
3197  typename C,
3198  typename Enable = typename std::enable_if<std::is_constructible<
3199  obj::basic_string_view<CharT, Traits>, C>::value>::type>
3200  bytes_view(const C *s) : s(*s)
3201  {
3202  }
3203 
3204  char operator[](std::size_t p) const
3205  {
3206  return static_cast<char>(s[p]);
3207  }
3208 
3209  size_t
3210  size() const
3211  {
3212  return s.size();
3213  }
3214 
3215  obj::basic_string_view<CharT, Traits> s;
3216 
3217  using is_transparent = void;
3218 };
3219 
3220 template <typename T>
3221 struct bytes_view<T,
3222  typename std::enable_if<std::is_integral<T>::value &&
3223  !std::is_signed<T>::value>::type> {
3224  bytes_view(const T *k) : k(k)
3225  {
3226 #if __cpp_lib_endian
3227  static_assert(
3228  std::endian::native == std::endian::little,
3229  "Scalar type are not little endian on this platform!");
3230 #elif !defined(NDEBUG)
3231  /* Assert little endian is used. */
3232  uint16_t word = (2 << 8) + 1;
3233  assert(((char *)&word)[0] == 1);
3234 #endif
3235  }
3236 
3237  char operator[](std::size_t p) const
3238  {
3239  return reinterpret_cast<const char *>(k)[size() - p - 1];
3240  }
3241 
3242  constexpr size_t
3243  size() const
3244  {
3245  return sizeof(T);
3246  }
3247 
3248  const T *k;
3249 };
3250 } /* namespace detail */
3251 
3252 } /* namespace pmem */
3253 
3254 #endif /* LIBPMEMOBJ_CPP_RADIX_HPP */
pmem::obj::basic_string_view
Our partial std::string_view implementation.
Definition: string_view.hpp:43
pmem::obj::experimental::radix_tree::erase
iterator erase(const_iterator pos)
Removes the element at pos from the container.
Definition: radix_tree.hpp:1794
pmem::obj::experimental::radix_tree::node::parent
tagged_node_ptr parent
Pointer to a parent node.
Definition: radix_tree.hpp:469
pmem::pool_error
Custom pool error class.
Definition: pexceptions.hpp:45
utils.hpp
Libpmemobj C++ utils.
string_view.hpp
Our partial std::string_view implementation.
pmem
Persistent memory namespace.
Definition: allocation_flag.hpp:15
pmem::obj::experimental::radix_tree::count
size_type count(const key_type &k) const
Returns the number of elements with key that compares equivalent to the specified argument.
Definition: radix_tree.hpp:1643
pmem::obj::begin
pmem::obj::array< T, N >::iterator begin(pmem::obj::array< T, N > &a)
Non-member begin.
Definition: array.hpp:800
pmem::obj::experimental::swap
void swap(radix_tree< Key, Value, BytesView > &lhs, radix_tree< Key, Value, BytesView > &rhs)
Non-member swap.
Definition: radix_tree.hpp:3180
common.hpp
Commonly used functionality.
template_helpers.hpp
Commonly used SFINAE helpers.
pmem::obj::experimental::radix_tree::crbegin
const_reverse_iterator crbegin() const
Returns a const, reverse iterator to the beginning.
Definition: radix_tree.hpp:2311
pmem::obj::experimental::radix_tree::lower_bound
iterator lower_bound(const key_type &k)
Returns an iterator pointing to the first element that is not less than (i.e.
Definition: radix_tree.hpp:2055
pmem::obj::operator++
p< T > & operator++(p< T > &pp)
Prefix increment operator overload.
Definition: pext.hpp:48
pmem::obj::experimental::radix_tree
Radix tree is an associative, ordered container.
Definition: radix_tree.hpp:103
pmem::obj::experimental::radix_tree::check_tx_stage_work
void check_tx_stage_work()
Private helper function.
Definition: radix_tree.hpp:3168
pmem::obj::operator==
bool operator==(standard_alloc_policy< T > const &, standard_alloc_policy< T2 > const &)
Determines if memory from another allocator can be deallocated from this one.
Definition: allocator.hpp:420
pmem::obj::p
Resides on pmem class.
Definition: p.hpp:35
pool.hpp
C++ pmemobj pool.
make_persistent.hpp
Persistent_ptr transactional allocation functions for objects.
pmem::obj::experimental::radix_tree::rbegin
reverse_iterator rbegin()
Returns a reverse iterator to the beginning.
Definition: radix_tree.hpp:2286
string.hpp
String typedefs for common character types.
pmem::obj::experimental::radix_tree::crend
const_reverse_iterator crend() const
Returns a const, reverse iterator to the end.
Definition: radix_tree.hpp:2324
pmem::obj::transaction::run
static void run(pool_base &pool, std::function< void()> tx, Locks &... locks)
Execute a closure-like transaction and lock locks.
Definition: transaction.hpp:406
pmem::obj::experimental::radix_tree::find
iterator find(const key_type &k)
Finds an element with key equivalent to key.
Definition: radix_tree.hpp:1678
pmem::obj::swap
void swap(pmem::obj::array< T, N > &lhs, pmem::obj::array< T, N > &rhs)
Non-member swap function.
Definition: array.hpp:880
pmem::obj::experimental::radix_tree::operator<<
friend std::ostream & operator<<(std::ostream &os, const radix_tree< K, V, BV > &tree)
Prints tree in DOT format.
Definition: radix_tree.hpp:2400
pmem::obj::operator!=
bool operator!=(const allocator< T, P, Tr > &lhs, const OtherAllocator &rhs)
Determines if memory from another allocator can be deallocated from this one.
Definition: allocator.hpp:536
pmem::obj::cend
pmem::obj::array< T, N >::const_iterator cend(const pmem::obj::array< T, N > &a)
Non-member cend.
Definition: array.hpp:770
pmem::obj::experimental::radix_tree::node::embedded_entry
tagged_node_ptr embedded_entry
The embedded_entry ptr is used only for nodes for which length of the path from root is a multiple of...
Definition: radix_tree.hpp:477
pmem::obj::experimental::radix_tree::cbegin
const_iterator cbegin() const
Returns a const iterator to the first element of the container.
Definition: radix_tree.hpp:2227
transaction.hpp
C++ pmemobj transactions.
pmem::obj::experimental::radix_tree::leaf
This is the structure which 'holds' key/value pair.
Definition: radix_tree.hpp:397
pmem::obj::experimental::radix_tree::upper_bound
iterator upper_bound(const key_type &k)
Returns an iterator pointing to the first element that is greater than key.
Definition: radix_tree.hpp:2135
inline_string.hpp
Inline string implementation.
pmem::obj::experimental::radix_tree::radix_tree_iterator
Radix tree iterator supports multipass and bidirectional iteration.
Definition: radix_tree.hpp:567
allocator.hpp
Persistent memory aware allocator.
pmem::obj::experimental::swap
void swap(concurrent_map< Key, Value, Comp, Allocator > &lhs, concurrent_map< Key, Value, Comp, Allocator > &rhs)
Non-member swap.
Definition: concurrent_map.hpp:151
pmem::obj::experimental::radix_tree::check_pmem
void check_pmem()
Private helper function.
Definition: radix_tree.hpp:3153
pmem::obj::experimental::radix_tree::end
iterator end()
Returns an iterator to the element following the last element of the map.
Definition: radix_tree.hpp:2211
pmem::obj::persistent_ptr
Persistent pointer class.
Definition: persistent_ptr.hpp:152
pmem::obj::end
pmem::obj::array< T, N >::iterator end(pmem::obj::array< T, N > &a)
Non-member end.
Definition: array.hpp:820
p.hpp
Resides on pmem property template.
integer_sequence.hpp
Create c++14 style index sequence.
pmem::obj::experimental::radix_tree::node
This is internal node.
Definition: radix_tree.hpp:463
pmem::obj::cbegin
pmem::obj::array< T, N >::const_iterator cbegin(const pmem::obj::array< T, N > &a)
Non-member cbegin.
Definition: array.hpp:760
pmem::obj::experimental::operator!=
bool operator!=(self_relative_ptr< T > const &lhs, self_relative_ptr< Y > const &rhs) noexcept
Inequality operator.
Definition: self_relative_ptr.hpp:398
pmem::obj::get
T & get(pmem::obj::array< T, N > &a)
Non-member get function.
Definition: array.hpp:890
pmem::obj::experimental::radix_tree::cend
const_iterator cend() const
Returns a const iterator to the element following the last element of the map.
Definition: radix_tree.hpp:2247
pmem::obj::experimental::radix_tree::~radix_tree
~radix_tree()
Destructor.
Definition: radix_tree.hpp:873
pmem::obj::experimental::radix_tree::insert
std::pair< iterator, bool > insert(const value_type &v)
Inserts element if the tree doesn't already contain an element with an equivalent key.
Definition: radix_tree.hpp:1367
pmem::obj::experimental::radix_tree::clear
void clear()
Erases all elements from the container transactionally.
Definition: radix_tree.hpp:1771
pmem::obj::experimental::radix_tree::swap
void swap(radix_tree &rhs)
Member swap.
Definition: radix_tree.hpp:921
pext.hpp
Convenience extensions for the resides on pmem property template.
pmem::obj::experimental::radix_tree::begin
iterator begin()
Returns an iterator to the first element of the container.
Definition: radix_tree.hpp:2194
self_relative_ptr.hpp
Persistent self-relative smart pointer.
pmem::obj::experimental::operator==
bool operator==(self_relative_ptr< T > const &lhs, self_relative_ptr< Y > const &rhs) noexcept
Equality operator.
Definition: self_relative_ptr.hpp:387
pmem::obj::experimental::radix_tree::operator=
radix_tree & operator=(const radix_tree &m)
Copy assignment operator.
Definition: radix_tree.hpp:786
pmem::transaction_scope_error
Custom transaction error class.
Definition: pexceptions.hpp:158
pmem::obj::pool_by_vptr
pool_base pool_by_vptr(const T *that)
Retrieve pool handle for the given pointer.
Definition: utils.hpp:32
pmem::detail::self_relative_ptr_base_impl< std::ptrdiff_t >
pmem::obj::experimental::radix_tree::size
uint64_t size() const noexcept
Definition: radix_tree.hpp:909
pmem::obj::experimental::radix_tree::radix_tree
radix_tree()
Default radix tree constructor.
Definition: radix_tree.hpp:665
pmem::obj::experimental::v
Volatile residing on pmem class.
Definition: v.hpp:42
pmem::obj::pool_base
The non-template pool base class.
Definition: pool.hpp:46
pmem::obj::experimental::radix_tree::rend
reverse_iterator rend()
Returns a reverse iterator to the end.
Definition: radix_tree.hpp:2299
pmem::obj::experimental::operator<<
std::ostream & operator<<(std::ostream &os, const radix_tree< K, V, BV > &tree)
Prints tree in DOT format.
Definition: radix_tree.hpp:2400
pmem::obj::experimental::radix_tree::node::byte
byten_t byte
Byte and bit together are used to calculate the NIB which is used to index the child array.
Definition: radix_tree.hpp:492
persistent_ptr.hpp
Persistent smart pointer.
pmem::obj::experimental::radix_tree::empty
bool empty() const noexcept
Checks whether the container is empty.
Definition: radix_tree.hpp:889
pmem::obj::basic_string_view::size
size_type size() const noexcept
Returns count of characters stored in this pmem::obj::string_view data.
Definition: string_view.hpp:150
pmem::obj::operator--
p< T > & operator--(p< T > &pp)
Prefix decrement operator overload.
Definition: pext.hpp:59
pmem::obj::experimental::radix_tree::max_size
size_type max_size() const noexcept
Definition: radix_tree.hpp:899