PMDK C++ bindings  1.12
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 
103 template <typename Key, typename Value,
104  typename BytesView = detail::bytes_view<Key>>
105 class radix_tree {
106  template <bool IsConst>
107  struct radix_tree_iterator;
108 
109 public:
110  using key_type = Key;
111  using mapped_type = Value;
112  using value_type = detail::pair<const key_type, mapped_type>;
113  using size_type = std::size_t;
114  using reference = value_type &;
115  using const_reference = const value_type &;
118  using reverse_iterator = std::reverse_iterator<iterator>;
119  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
120  using difference_type = std::ptrdiff_t;
121 
122  radix_tree();
123 
124  template <class InputIt>
125  radix_tree(InputIt first, InputIt last);
126  radix_tree(const radix_tree &m);
127  radix_tree(radix_tree &&m);
128  radix_tree(std::initializer_list<value_type> il);
129 
130  radix_tree &operator=(const radix_tree &m);
132  radix_tree &operator=(std::initializer_list<value_type> ilist);
133 
134  ~radix_tree();
135 
136  template <class... Args>
137  std::pair<iterator, bool> emplace(Args &&... args);
138 
139  std::pair<iterator, bool> insert(const value_type &v);
140  std::pair<iterator, bool> insert(value_type &&v);
141  template <typename P,
142  typename = typename std::enable_if<
143  std::is_constructible<value_type, P &&>::value,
144  P>::type>
145  std::pair<iterator, bool> insert(P &&p);
146  /* iterator insert(const_iterator position, const value_type &v); */
147  /* iterator insert(const_iterator position, value_type &&v); */
148  /* template <
149  typename P,
150  typename = typename std::enable_if<
151  detail::has_is_transparent<BytesView>::value, P>::type>
152  iterator insert(const_iterator position, P &&p); */
153  template <class InputIterator>
154  void insert(InputIterator first, InputIterator last);
155  void insert(std::initializer_list<value_type> il);
156  // insert_return_type insert(node_type&& nh);
157  // iterator insert(const_iterator hint, node_type&& nh);
158 
159  template <class... Args>
160  std::pair<iterator, bool> try_emplace(const key_type &k,
161  Args &&... args);
162  template <class... Args>
163  std::pair<iterator, bool> try_emplace(key_type &&k, Args &&... args);
164  /*template <class... Args>
165  iterator try_emplace(const_iterator hint, const key_type &k,
166  Args &&... args);*/
167  /*template <class... Args>
168  iterator try_emplace(const_iterator hint, key_type &&k,
169  Args &&... args);*/
170  /* https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96976 */
171  template <typename K, typename BV = BytesView, class... Args>
172  auto try_emplace(K &&k, Args &&... args) -> typename std::enable_if<
173  detail::has_is_transparent<BV>::value &&
174  !std::is_same<typename std::remove_const<
175  typename std::remove_reference<
176  K>::type>::type,
177  key_type>::value,
178  std::pair<iterator, bool>>::type;
179 
180  template <typename M>
181  std::pair<iterator, bool> insert_or_assign(const key_type &k, M &&obj);
182  template <typename M>
183  std::pair<iterator, bool> insert_or_assign(key_type &&k, M &&obj);
184  /*template <typename M>
185  iterator insert_or_assign(const_iterator hint, const key_type &k,
186  M &&obj);*/
187  /*template <typename M>
188  iterator insert_or_assign(const_iterator hint, key_type &&k, M &&obj);*/
189  template <
190  typename M, typename K,
191  typename = typename std::enable_if<
192  detail::has_is_transparent<BytesView>::value, K>::type>
193  std::pair<iterator, bool> insert_or_assign(K &&k, M &&obj);
194 
197  size_type erase(const key_type &k);
198  template <typename K,
199  typename = typename std::enable_if<
200  detail::has_is_transparent<BytesView>::value &&
201  !std::is_same<K, iterator>::value &&
202  !std::is_same<K, const_iterator>::value,
203  K>::type>
204  size_type erase(const K &k);
205 
206  void clear();
207 
208  size_type count(const key_type &k) const;
209  template <
210  typename K,
211  typename = typename std::enable_if<
212  detail::has_is_transparent<BytesView>::value, K>::type>
213  size_type count(const K &k) const;
214 
215  iterator find(const key_type &k);
216  const_iterator find(const key_type &k) const;
217  template <
218  typename K,
219  typename = typename std::enable_if<
220  detail::has_is_transparent<BytesView>::value, K>::type>
221  iterator find(const K &k);
222  template <
223  typename K,
224  typename = typename std::enable_if<
225  detail::has_is_transparent<BytesView>::value, K>::type>
226  const_iterator find(const K &k) const;
227 
228  iterator lower_bound(const key_type &k);
229  const_iterator lower_bound(const key_type &k) const;
230  template <
231  typename K,
232  typename = typename std::enable_if<
233  detail::has_is_transparent<BytesView>::value, K>::type>
234  iterator lower_bound(const K &k);
235  template <
236  typename K,
237  typename = typename std::enable_if<
238  detail::has_is_transparent<BytesView>::value, K>::type>
239  const_iterator lower_bound(const K &k) const;
240 
241  iterator upper_bound(const key_type &k);
242  const_iterator upper_bound(const key_type &k) const;
243  template <
244  typename K,
245  typename = typename std::enable_if<
246  detail::has_is_transparent<BytesView>::value, K>::type>
247  iterator upper_bound(const K &k);
248  template <
249  typename K,
250  typename = typename std::enable_if<
251  detail::has_is_transparent<BytesView>::value, K>::type>
252  const_iterator upper_bound(const K &k) const;
253 
254  iterator begin();
255  iterator end();
256  const_iterator cbegin() const;
257  const_iterator cend() const;
258  const_iterator begin() const;
259  const_iterator end() const;
260 
261  reverse_iterator rbegin();
262  reverse_iterator rend();
263  const_reverse_iterator crbegin() const;
264  const_reverse_iterator crend() const;
265  const_reverse_iterator rbegin() const;
266  const_reverse_iterator rend() const;
267 
268  /* capacity: */
269  bool empty() const noexcept;
270  size_type max_size() const noexcept;
271  uint64_t size() const noexcept;
272 
273  void swap(radix_tree &rhs);
274 
275  template <typename K, typename V, typename BV>
276  friend std::ostream &operator<<(std::ostream &os,
277  const radix_tree<K, V, BV> &tree);
278 
279 private:
280  using byten_t = uint64_t;
281  using bitn_t = uint8_t;
282 
283  /* Size of a chunk which differentiates subtrees of a node */
284  static constexpr std::size_t SLICE = 4;
285  /* Mask for SLICE */
286  static constexpr std::size_t NIB = ((1ULL << SLICE) - 1);
287  /* Number of children in internal nodes */
288  static constexpr std::size_t SLNODES = (1 << SLICE);
289  /* Mask for SLICE */
290  static constexpr bitn_t SLICE_MASK = (bitn_t) ~(SLICE - 1);
291  /* Position of the first SLICE */
292  static constexpr bitn_t FIRST_NIB = 8 - SLICE;
293 
294  struct tagged_node_ptr;
295  struct leaf;
296  struct node;
297 
298  /*** pmem members ***/
299  tagged_node_ptr root;
300  p<uint64_t> size_;
301 
302  /* helper functions */
303  template <typename K, typename F, class... Args>
304  std::pair<iterator, bool> internal_emplace(const K &, F &&);
305  template <typename K>
306  leaf *internal_find(const K &k) const;
307 
308  static tagged_node_ptr &parent_ref(tagged_node_ptr n);
309  template <typename K1, typename K2>
310  static bool keys_equal(const K1 &k1, const K2 &k2);
311  template <typename K1, typename K2>
312  static int compare(const K1 &k1, const K2 &k2, byten_t offset = 0);
313  template <bool Direction, typename Iterator>
314  static leaf *next_leaf(Iterator child, tagged_node_ptr parent);
315  template <bool Direction>
316  static leaf *find_leaf(tagged_node_ptr n);
317  static unsigned slice_index(char k, uint8_t shift);
318  template <typename K1, typename K2>
319  static byten_t prefix_diff(const K1 &lhs, const K2 &rhs,
320  byten_t offset = 0);
321  leaf *any_leftmost_leaf(tagged_node_ptr n, size_type min_depth) const;
322  template <typename K1, typename K2>
323  static bitn_t bit_diff(const K1 &leaf_key, const K2 &key, byten_t diff);
324  template <typename K>
325  leaf *common_prefix_leaf(const K &key) const;
326  static void print_rec(std::ostream &os, radix_tree::tagged_node_ptr n);
327  template <typename K>
328  static BytesView bytes_view(const K &k);
329  static string_view bytes_view(string_view s);
330  static bool path_length_equal(size_t key_size, tagged_node_ptr n);
331  template <typename K>
332  std::tuple<const tagged_node_ptr *, tagged_node_ptr>
333  descend(const K &k, byten_t diff, bitn_t sh) const;
334  template <typename K>
335  std::tuple<tagged_node_ptr *, tagged_node_ptr>
336  descend(const K &k, byten_t diff, bitn_t sh);
337  template <bool Lower, typename K>
338  const_iterator internal_bound(const K &k) const;
339 
340  void check_pmem();
341  void check_tx_stage_work();
342 
343  static_assert(sizeof(node) == 256,
344  "Internal node should have size equal to 256 bytes.");
345 };
346 
347 template <typename Key, typename Value, typename BytesView>
350 
351 template <typename Key, typename Value, typename BytesView>
352 struct radix_tree<Key, Value, BytesView>::tagged_node_ptr {
353  tagged_node_ptr() = default;
354  tagged_node_ptr(const tagged_node_ptr &rhs) = default;
355 
356  tagged_node_ptr(std::nullptr_t);
357  tagged_node_ptr(const persistent_ptr<leaf> &ptr);
358  tagged_node_ptr(const persistent_ptr<node> &ptr);
359 
360  tagged_node_ptr &operator=(const tagged_node_ptr &rhs) = default;
361 
362  tagged_node_ptr &operator=(std::nullptr_t);
363  tagged_node_ptr &operator=(const persistent_ptr<leaf> &rhs);
364  tagged_node_ptr &operator=(const persistent_ptr<node> &rhs);
365 
366  bool operator==(const tagged_node_ptr &rhs) const;
367  bool operator!=(const tagged_node_ptr &rhs) const;
368 
369  bool operator==(const radix_tree::leaf *rhs) const;
370  bool operator!=(const radix_tree::leaf *rhs) const;
371 
372  void swap(tagged_node_ptr &rhs);
373 
374  bool is_leaf() const;
375 
376  radix_tree::leaf *get_leaf() const;
377  radix_tree::node *get_node() const;
378 
379  radix_tree::node *operator->() const noexcept;
380 
381  explicit operator bool() const noexcept;
382 
383 private:
384  static constexpr uintptr_t IS_LEAF = 1;
385  void *add_tag(radix_tree::leaf *ptr) const;
386  void *remove_tag(void *ptr) const;
387 
389 };
390 
400 template <typename Key, typename Value, typename BytesView>
401 struct radix_tree<Key, Value, BytesView>::leaf {
403 
404  leaf(const leaf &) = delete;
405  leaf(leaf &&) = delete;
406 
407  leaf &operator=(const leaf &) = delete;
408  leaf &operator=(leaf &&) = delete;
409 
410  ~leaf();
411 
412  Key &key();
413  Value &value();
414 
415  const Key &key() const;
416  const Value &value() const;
417 
418  static persistent_ptr<leaf> make(tagged_node_ptr parent);
419 
420  template <typename... Args1, typename... Args2>
421  static persistent_ptr<leaf>
422  make(tagged_node_ptr parent, std::piecewise_construct_t pc,
423  std::tuple<Args1...> first_args, std::tuple<Args2...> second_args);
424  template <typename K, typename V>
425  static persistent_ptr<leaf> make(tagged_node_ptr parent, K &&k, V &&v);
426  static persistent_ptr<leaf> make(tagged_node_ptr parent, const Key &k,
427  const Value &v);
428  template <typename K, typename... Args>
429  static persistent_ptr<leaf> make_key_args(tagged_node_ptr parent, K &&k,
430  Args &&... args);
431  template <typename K, typename V>
432  static persistent_ptr<leaf> make(tagged_node_ptr parent,
433  detail::pair<K, V> &&p);
434  template <typename K, typename V>
435  static persistent_ptr<leaf> make(tagged_node_ptr parent,
436  const detail::pair<K, V> &p);
437  template <typename K, typename V>
438  static persistent_ptr<leaf> make(tagged_node_ptr parent,
439  std::pair<K, V> &&p);
440  template <typename K, typename V>
441  static persistent_ptr<leaf> make(tagged_node_ptr parent,
442  const std::pair<K, V> &p);
443  static persistent_ptr<leaf> make(tagged_node_ptr parent,
444  const leaf &other);
445 
446 private:
447  friend class radix_tree<Key, Value, BytesView>;
448 
449  leaf() = default;
450 
451  template <typename... Args1, typename... Args2, size_t... I1,
452  size_t... I2>
453  static persistent_ptr<leaf>
454  make(tagged_node_ptr parent, std::piecewise_construct_t,
455  std::tuple<Args1...> &first_args,
456  std::tuple<Args2...> &second_args, detail::index_sequence<I1...>,
457  detail::index_sequence<I2...>);
458 
459  tagged_node_ptr parent = nullptr;
460 };
461 
466 template <typename Key, typename Value, typename BytesView>
467 struct radix_tree<Key, Value, BytesView>::node {
468  node(tagged_node_ptr parent, byten_t byte, bitn_t bit);
469 
473  tagged_node_ptr parent;
474 
481  tagged_node_ptr embedded_entry;
482 
483  /* Children can be both leaves and internal nodes. */
484  tagged_node_ptr child[SLNODES];
485 
496  byten_t byte;
497  bitn_t bit;
498 
499  struct direction {
500  static constexpr bool Forward = 0;
501  static constexpr bool Reverse = 1;
502  };
503 
504  struct forward_iterator;
505  using reverse_iterator = std::reverse_iterator<forward_iterator>;
506 
507  template <bool Direction>
508  using iterator =
509  typename std::conditional<Direction == direction::Forward,
510  forward_iterator,
511  reverse_iterator>::type;
512 
513  template <bool Direction = direction::Forward>
514  typename std::enable_if<
515  Direction ==
516  radix_tree<Key, Value,
517  BytesView>::node::direction::Forward,
518  typename radix_tree<Key, Value,
519  BytesView>::node::forward_iterator>::type
520  begin() const;
521 
522  template <bool Direction = direction::Forward>
523  typename std::enable_if<
524  Direction ==
525  radix_tree<Key, Value,
526  BytesView>::node::direction::Forward,
527  typename radix_tree<Key, Value,
528  BytesView>::node::forward_iterator>::type
529  end() const;
530 
531  /* rbegin */
532  template <bool Direction = direction::Forward>
533  typename std::enable_if<
534  Direction ==
535  radix_tree<Key, Value,
536  BytesView>::node::direction::Reverse,
537  typename radix_tree<Key, Value,
538  BytesView>::node::reverse_iterator>::type
539  begin() const;
540 
541  /* rend */
542  template <bool Direction = direction::Forward>
543  typename std::enable_if<
544  Direction ==
545  radix_tree<Key, Value,
546  BytesView>::node::direction::Reverse,
547  typename radix_tree<Key, Value,
548  BytesView>::node::reverse_iterator>::type
549  end() const;
550 
551  template <bool Direction = direction::Forward, typename Ptr>
552  auto find_child(const Ptr &n) const -> decltype(begin<Direction>());
553 
554  template <bool Direction = direction::Forward,
555  typename Enable = typename std::enable_if<
556  Direction == direction::Forward>::type>
557  auto make_iterator(const tagged_node_ptr *ptr) const
558  -> decltype(begin<Direction>());
559 
560  uint8_t padding[256 - sizeof(parent) - sizeof(leaf) - sizeof(child) -
561  sizeof(byte) - sizeof(bit)];
562 };
563 
569 template <typename Key, typename Value, typename BytesView>
570 template <bool IsConst>
571 struct radix_tree<Key, Value, BytesView>::radix_tree_iterator {
572 private:
573  using leaf_ptr =
574  typename std::conditional<IsConst, const leaf *, leaf *>::type;
575  using node_ptr =
576  typename std::conditional<IsConst, const tagged_node_ptr *,
577  tagged_node_ptr *>::type;
578  friend struct radix_tree_iterator<true>;
579 
580 public:
581  using difference_type = std::ptrdiff_t;
583  using reference = typename std::conditional<IsConst, const value_type &,
584  value_type &>::type;
585  using pointer = typename std::conditional<IsConst, value_type const *,
586  value_type *>::type;
587  using iterator_category = std::bidirectional_iterator_tag;
588 
589  radix_tree_iterator() = default;
590  radix_tree_iterator(leaf_ptr leaf_, node_ptr root);
591  radix_tree_iterator(const radix_tree_iterator &rhs) = default;
592 
593  template <bool C = IsConst,
594  typename Enable = typename std::enable_if<C>::type>
596 
598  operator=(const radix_tree_iterator &rhs) = default;
599 
600  reference operator*() const;
601  pointer operator->() const;
602 
603  template <typename V = Value,
604  typename Enable = typename std::enable_if<
605  detail::is_inline_string<V>::value>::type>
606  void assign_val(basic_string_view<typename V::value_type,
607  typename V::traits_type>
608  rhs);
609 
610  template <typename T, typename V = Value,
611  typename Enable = typename std::enable_if<
612  !detail::is_inline_string<V>::value>::type>
613  void assign_val(T &&rhs);
614 
617 
620 
621  template <bool C>
622  bool operator!=(const radix_tree_iterator<C> &rhs) const;
623 
624  template <bool C>
625  bool operator==(const radix_tree_iterator<C> &rhs) const;
626 
627 private:
628  friend class radix_tree;
629 
630  leaf_ptr leaf_ = nullptr;
631  node_ptr root = nullptr;
632 };
633 
634 template <typename Key, typename Value, typename BytesView>
635 struct radix_tree<Key, Value, BytesView>::node::forward_iterator {
636  using difference_type = std::ptrdiff_t;
637  using value_type = tagged_node_ptr;
638  using pointer = const value_type *;
639  using reference = const value_type &;
640  using iterator_category = std::forward_iterator_tag;
641 
642  forward_iterator(pointer child, const node *node);
643 
644  forward_iterator operator++();
645  forward_iterator operator++(int);
646 
647  forward_iterator operator--();
648 
649  reference operator*() const;
650  pointer operator->() const;
651 
652  pointer get_node() const;
653 
654  bool operator!=(const forward_iterator &rhs) const;
655  bool operator==(const forward_iterator &rhs) const;
656 
657 private:
658  pointer child;
659  const node *n;
660 };
661 
670 template <typename Key, typename Value, typename BytesView>
672 {
673  check_pmem();
675 }
676 
696 template <typename Key, typename Value, typename BytesView>
697 template <class InputIt>
699  : root(nullptr), size_(0)
700 {
701  check_pmem();
703 
704  for (auto it = first; it != last; it++)
705  emplace(*it);
706 }
707 
723 template <typename Key, typename Value, typename BytesView>
725 {
726  check_pmem();
727  check_tx_stage_work();
728 
729  root = nullptr;
730  size_ = 0;
731 
732  for (auto it = m.cbegin(); it != m.cend(); it++)
733  emplace(*it);
734 }
735 
748 template <typename Key, typename Value, typename BytesView>
750 {
751  check_pmem();
752  check_tx_stage_work();
753 
754  root = m.root;
755  size_ = m.size_;
756  m.root = nullptr;
757  m.size_ = 0;
758 }
759 
774 template <typename Key, typename Value, typename BytesView>
776  std::initializer_list<value_type> il)
777  : radix_tree(il.begin(), il.end())
778 {
779 }
780 
790 template <typename Key, typename Value, typename BytesView>
793 {
794  check_pmem();
795 
796  auto pop = pool_by_vptr(this);
797 
798  if (this != &other) {
799  flat_transaction::run(pop, [&] {
800  clear();
801 
802  this->root = nullptr;
803  this->size_ = 0;
804 
805  for (auto it = other.cbegin(); it != other.cend(); it++)
806  emplace(*it);
807  });
808  }
809 
810  return *this;
811 }
812 
821 template <typename Key, typename Value, typename BytesView>
824 {
825  check_pmem();
826 
827  auto pop = pool_by_vptr(this);
828 
829  if (this != &other) {
830  flat_transaction::run(pop, [&] {
831  clear();
832 
833  this->root = other.root;
834  this->size_ = other.size_;
835  other.root = nullptr;
836  other.size_ = 0;
837  });
838  }
839 
840  return *this;
841 }
842 
853 template <typename Key, typename Value, typename BytesView>
856  std::initializer_list<value_type> ilist)
857 {
858  check_pmem();
859 
860  auto pop = pool_by_vptr(this);
861 
862  transaction::run(pop, [&] {
863  clear();
864 
865  this->root = nullptr;
866  this->size_ = 0;
867 
868  for (auto it = ilist.begin(); it != ilist.end(); it++)
869  emplace(*it);
870  });
871 
872  return *this;
873 }
874 
878 template <typename Key, typename Value, typename BytesView>
880 {
881  try {
882  clear();
883  } catch (...) {
884  std::terminate();
885  }
886 }
887 
893 template <typename Key, typename Value, typename BytesView>
894 bool
896 {
897  return size_ == 0;
898 }
899 
903 template <typename Key, typename Value, typename BytesView>
904 typename radix_tree<Key, Value, BytesView>::size_type
906 {
907  return std::numeric_limits<difference_type>::max();
908 }
909 
913 template <typename Key, typename Value, typename BytesView>
914 uint64_t
916 {
917  return this->size_;
918 }
919 
925 template <typename Key, typename Value, typename BytesView>
926 void
928 {
929  auto pop = pool_by_vptr(this);
930 
931  flat_transaction::run(pop, [&] {
932  this->size_.swap(rhs.size_);
933  this->root.swap(rhs.root);
934  });
935 }
936 
937 /*
938  * Returns reference to n->parent (handles both internal and leaf nodes).
939  */
940 template <typename Key, typename Value, typename BytesView>
943 {
944  if (n.is_leaf())
945  return n.get_leaf()->parent;
946 
947  return n->parent;
948 }
949 
950 /*
951  * Find a leftmost leaf in a subtree of @param n.
952  *
953  * @param min_depth specifies minimum depth of the leaf. If the
954  * tree is shorter than min_depth, a bottom leaf is returned.
955  */
956 template <typename Key, typename Value, typename BytesView>
957 typename radix_tree<Key, Value, BytesView>::leaf *
958 radix_tree<Key, Value, BytesView>::any_leftmost_leaf(
959  typename radix_tree<Key, Value, BytesView>::tagged_node_ptr n,
960  size_type min_depth) const
961 {
962  assert(n);
963 
964  while (!n.is_leaf()) {
965  if (n->embedded_entry && n->byte >= min_depth)
966  return n->embedded_entry.get_leaf();
967 
968  for (size_t i = 0; i < SLNODES; i++) {
969  tagged_node_ptr m;
970  if ((m = n->child[i])) {
971  n = m;
972  break;
973  }
974  }
975  }
976 
977  return n.get_leaf();
978 }
979 
980 /*
981  * Descends to the leaf that shares a common prefix with the key.
982  */
983 template <typename Key, typename Value, typename BytesView>
984 template <typename K>
985 typename radix_tree<Key, Value, BytesView>::leaf *
986 radix_tree<Key, Value, BytesView>::common_prefix_leaf(const K &key) const
987 {
988  auto n = root;
989 
990  while (n && !n.is_leaf() && n->byte < key.size()) {
991  auto nn = n->child[slice_index(key[n->byte], n->bit)];
992 
993  if (nn)
994  n = nn;
995  else {
996  n = any_leftmost_leaf(n, key.size());
997  break;
998  }
999  }
1000 
1001  /* This can happen when key is a prefix of some leaf or when the node at
1002  * which the keys diverge isn't a leaf */
1003  if (!n.is_leaf())
1004  n = any_leftmost_leaf(n, key.size());
1005 
1006  return n.get_leaf();
1007 }
1008 
1009 template <typename Key, typename Value, typename BytesView>
1010 template <typename K>
1011 BytesView
1012 radix_tree<Key, Value, BytesView>::bytes_view(const K &key)
1013 {
1014  /* bytes_view accepts const pointer instead of reference to make sure
1015  * there is no implicit conversion to a temporary type (and hence
1016  * dangling references). */
1017  return BytesView(&key);
1018 }
1019 
1020 template <typename Key, typename Value, typename BytesView>
1021 string_view
1022 radix_tree<Key, Value, BytesView>::bytes_view(string_view key)
1023 {
1024  return key;
1025 }
1026 
1027 /*
1028  * Checks for key equality.
1029  */
1030 template <typename Key, typename Value, typename BytesView>
1031 template <typename K1, typename K2>
1032 bool
1033 radix_tree<Key, Value, BytesView>::keys_equal(const K1 &k1, const K2 &k2)
1034 {
1035  return k1.size() == k2.size() && compare(k1, k2) == 0;
1036 }
1037 
1038 /*
1039  * Checks for key equality.
1040  */
1041 template <typename Key, typename Value, typename BytesView>
1042 template <typename K1, typename K2>
1043 int
1044 radix_tree<Key, Value, BytesView>::compare(const K1 &k1, const K2 &k2,
1045  byten_t offset)
1046 {
1047  auto ret = prefix_diff(k1, k2, offset);
1048 
1049  if (ret != (std::min)(k1.size(), k2.size()))
1050  return (unsigned char)(k1[ret]) - (unsigned char)(k2[ret]);
1051 
1052  return k1.size() - k2.size();
1053 }
1054 
1055 /*
1056  * Returns length of common prefix of lhs and rhs.
1057  */
1058 template <typename Key, typename Value, typename BytesView>
1059 template <typename K1, typename K2>
1060 typename radix_tree<Key, Value, BytesView>::byten_t
1061 radix_tree<Key, Value, BytesView>::prefix_diff(const K1 &lhs, const K2 &rhs,
1062  byten_t offset)
1063 {
1064  byten_t diff;
1065  for (diff = offset; diff < (std::min)(lhs.size(), rhs.size()); diff++) {
1066  if (lhs[diff] != rhs[diff])
1067  return diff;
1068  }
1069 
1070  return diff;
1071 }
1072 
1073 /*
1074  * Checks whether length of the path from root to n is equal
1075  * to key_size.
1076  */
1077 template <typename Key, typename Value, typename BytesView>
1078 bool
1079 radix_tree<Key, Value, BytesView>::path_length_equal(size_t key_size,
1080  tagged_node_ptr n)
1081 {
1082  return n->byte == key_size && n->bit == bitn_t(FIRST_NIB);
1083 }
1084 
1085 template <typename Key, typename Value, typename BytesView>
1086 template <typename K1, typename K2>
1087 typename radix_tree<Key, Value, BytesView>::bitn_t
1088 radix_tree<Key, Value, BytesView>::bit_diff(const K1 &leaf_key, const K2 &key,
1089  byten_t diff)
1090 {
1091  auto min_key_len = (std::min)(leaf_key.size(), key.size());
1092  bitn_t sh = 8;
1093 
1094  /* If key differs from leaf_key at some point (neither is a prefix of
1095  * another) we will descend to the point of divergence. Otherwise we
1096  * will look for a node which represents the prefix. */
1097  if (diff < min_key_len) {
1098  auto at =
1099  static_cast<unsigned char>(leaf_key[diff] ^ key[diff]);
1100  sh = pmem::detail::mssb_index((uint32_t)at) & SLICE_MASK;
1101  }
1102 
1103  return sh;
1104 }
1105 
1106 template <typename Key, typename Value, typename BytesView>
1107 template <typename K>
1108 std::tuple<const typename radix_tree<Key, Value, BytesView>::tagged_node_ptr *,
1109  typename radix_tree<Key, Value, BytesView>::tagged_node_ptr>
1110 radix_tree<Key, Value, BytesView>::descend(const K &key, byten_t diff,
1111  bitn_t sh) const
1112 {
1113  auto n = root;
1114  auto prev = n;
1115  auto slot = &root;
1116 
1117  while (n && !n.is_leaf() &&
1118  (n->byte < diff || (n->byte == diff && n->bit >= sh))) {
1119  prev = n;
1120  slot = &n->child[slice_index(key[n->byte], n->bit)];
1121  n = *slot;
1122  }
1123 
1124  return {slot, prev};
1125 }
1126 
1127 template <typename Key, typename Value, typename BytesView>
1128 template <typename K>
1129 std::tuple<typename radix_tree<Key, Value, BytesView>::tagged_node_ptr *,
1130  typename radix_tree<Key, Value, BytesView>::tagged_node_ptr>
1131 radix_tree<Key, Value, BytesView>::descend(const K &key, byten_t diff,
1132  bitn_t sh)
1133 {
1134  const tagged_node_ptr *slot;
1135  tagged_node_ptr prev;
1136 
1137  std::tie(slot, prev) =
1138  const_cast<const radix_tree *>(this)->descend(key, diff, sh);
1139 
1140  return {const_cast<tagged_node_ptr *>(slot), prev};
1141 }
1142 
1143 template <typename Key, typename Value, typename BytesView>
1144 template <typename K, typename F, class... Args>
1145 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1146 radix_tree<Key, Value, BytesView>::internal_emplace(const K &k, F &&make_leaf)
1147 {
1148  auto key = bytes_view(k);
1149  auto pop = pool_base(pmemobj_pool_by_ptr(this));
1150 
1151  if (!root) {
1153  [&] { this->root = make_leaf(nullptr); });
1154  return {iterator(root.get_leaf(), &root), true};
1155  }
1156 
1157  /*
1158  * Need to descend the tree twice. First to find a leaf that
1159  * represents a subtree that shares a common prefix with the key.
1160  * This is needed to find out the actual labels between nodes (they
1161  * are not known due to a possible path compression). Second time to
1162  * find the place for the new element.
1163  */
1164  auto leaf = common_prefix_leaf(key);
1165  auto leaf_key = bytes_view(leaf->key());
1166  auto diff = prefix_diff(key, leaf_key);
1167  auto sh = bit_diff(leaf_key, key, diff);
1168 
1169  /* Key exists. */
1170  if (diff == key.size() && leaf_key.size() == key.size())
1171  return {iterator(leaf, &root), false};
1172 
1173  /* Descend into the tree again. */
1174  tagged_node_ptr *slot;
1175  tagged_node_ptr prev;
1176  std::tie(slot, prev) = descend(key, diff, sh);
1177 
1178  auto n = *slot;
1179 
1180  /*
1181  * If the divergence point is at same nib as an existing node, and
1182  * the subtree there is empty, just place our leaf there and we're
1183  * done. Obviously this can't happen if SLICE == 1.
1184  */
1185  if (!n) {
1186  assert(diff < (std::min)(leaf_key.size(), key.size()));
1187 
1188  flat_transaction::run(pop, [&] { *slot = make_leaf(prev); });
1189  return {iterator(slot->get_leaf(), &root), true};
1190  }
1191 
1192  /* New key is a prefix of the leaf key or they are equal. We need to add
1193  * leaf ptr to internal node. */
1194  if (diff == key.size()) {
1195  if (!n.is_leaf() && path_length_equal(key.size(), n)) {
1196  assert(!n->embedded_entry);
1197 
1199  pop, [&] { n->embedded_entry = make_leaf(n); });
1200 
1201  return {iterator(n->embedded_entry.get_leaf(), &root),
1202  true};
1203  }
1204 
1205  /* Path length from root to n is longer than key.size().
1206  * We have to allocate new internal node above n. */
1207  tagged_node_ptr node;
1208  flat_transaction::run(pop, [&] {
1209  node = make_persistent<radix_tree::node>(
1210  parent_ref(n), diff, bitn_t(FIRST_NIB));
1211  node->embedded_entry = make_leaf(node);
1212  node->child[slice_index(leaf_key[diff],
1213  bitn_t(FIRST_NIB))] = n;
1214 
1215  parent_ref(n) = node;
1216  *slot = node;
1217  });
1218 
1219  return {iterator(node->embedded_entry.get_leaf(), &root), true};
1220  }
1221 
1222  if (diff == leaf_key.size()) {
1223  /* Leaf key is a prefix of the new key. We need to convert leaf
1224  * to a node. */
1225  tagged_node_ptr node;
1226  flat_transaction::run(pop, [&] {
1227  /* We have to add new node at the edge from parent to n
1228  */
1229  node = make_persistent<radix_tree::node>(
1230  parent_ref(n), diff, bitn_t(FIRST_NIB));
1231  node->embedded_entry = n;
1232  node->child[slice_index(key[diff], bitn_t(FIRST_NIB))] =
1233  make_leaf(node);
1234 
1235  parent_ref(n) = node;
1236  *slot = node;
1237  });
1238 
1239  return {iterator(node->child[slice_index(key[diff],
1240  bitn_t(FIRST_NIB))]
1241  .get_leaf(),
1242  &root),
1243  true};
1244  }
1245 
1246  /* There is already a subtree at the divergence point
1247  * (slice_index(key[diff], sh)). This means that a tree is vertically
1248  * compressed and we have to "break" this compression and add a new
1249  * node. */
1250  tagged_node_ptr node;
1251  flat_transaction::run(pop, [&] {
1252  node = make_persistent<radix_tree::node>(parent_ref(n), diff,
1253  sh);
1254  node->child[slice_index(leaf_key[diff], sh)] = n;
1255  node->child[slice_index(key[diff], sh)] = make_leaf(node);
1256 
1257  parent_ref(n) = node;
1258  *slot = node;
1259  });
1260 
1261  return {iterator(node->child[slice_index(key[diff], sh)].get_leaf(),
1262  &root),
1263  true};
1264 }
1265 
1294 template <typename Key, typename Value, typename BytesView>
1295 template <class... Args>
1296 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1298  Args &&... args)
1299 {
1300  return internal_emplace(k, [&](tagged_node_ptr parent) {
1301  size_++;
1302  return leaf::make_key_args(parent, k,
1303  std::forward<Args>(args)...);
1304  });
1305 }
1306 
1333 template <typename Key, typename Value, typename BytesView>
1334 template <class... Args>
1335 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1337 {
1338  auto pop = pool_base(pmemobj_pool_by_ptr(this));
1339  std::pair<iterator, bool> ret;
1340 
1341  flat_transaction::run(pop, [&] {
1342  auto leaf_ = leaf::make(nullptr, std::forward<Args>(args)...);
1343  auto make_leaf = [&](tagged_node_ptr parent) {
1344  leaf_->parent = parent;
1345  size_++;
1346  return leaf_;
1347  };
1348 
1349  ret = internal_emplace(leaf_->key(), make_leaf);
1350 
1351  if (!ret.second)
1352  delete_persistent<leaf>(leaf_);
1353  });
1354 
1355  return ret;
1356 }
1357 
1373 template <typename Key, typename Value, typename BytesView>
1374 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1376 {
1377  return try_emplace(v.first, v.second);
1378 }
1379 
1395 template <typename Key, typename Value, typename BytesView>
1396 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1398 {
1399  return try_emplace(std::move(v.first), std::move(v.second));
1400 }
1401 
1421 template <typename Key, typename Value, typename BytesView>
1422 template <typename P, typename>
1423 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1425 {
1426  return emplace(std::forward<P>(p));
1427 }
1428 
1440 template <typename Key, typename Value, typename BytesView>
1441 template <typename InputIterator>
1442 void
1444  InputIterator last)
1445 {
1446  for (auto it = first; it != last; it++)
1447  try_emplace((*it).first, (*it).second);
1448 }
1449 
1460 template <typename Key, typename Value, typename BytesView>
1461 void
1462 radix_tree<Key, Value, BytesView>::insert(std::initializer_list<value_type> il)
1463 {
1464  insert(il.begin(), il.end());
1465 }
1466 
1491 template <typename Key, typename Value, typename BytesView>
1492 template <class... Args>
1493 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1495 {
1496  return internal_emplace(k, [&](tagged_node_ptr parent) {
1497  size_++;
1498  return leaf::make_key_args(parent, std::move(k),
1499  std::forward<Args>(args)...);
1500  });
1501 }
1502 
1531 template <typename Key, typename Value, typename BytesView>
1532 template <typename K, typename BV, class... Args>
1533 auto
1535  typename std::enable_if<
1536  detail::has_is_transparent<BV>::value &&
1537  !std::is_same<typename std::remove_const<
1538  typename std::remove_reference<
1539  K>::type>::type,
1540  key_type>::value,
1541  std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
1542  bool>>::type
1543 
1544 {
1545  return internal_emplace(k, [&](tagged_node_ptr parent) {
1546  size_++;
1547  return leaf::make_key_args(parent, std::forward<K>(k),
1548  std::forward<Args>(args)...);
1549  });
1550 }
1551 
1570 template <typename Key, typename Value, typename BytesView>
1571 template <typename M>
1572 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1574 {
1575  auto ret = try_emplace(k, std::forward<M>(obj));
1576  if (!ret.second)
1577  ret.first.assign_val(std::forward<M>(obj));
1578  return ret;
1579 }
1580 
1599 template <typename Key, typename Value, typename BytesView>
1600 template <typename M>
1601 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1603 {
1604  auto ret = try_emplace(std::move(k), std::forward<M>(obj));
1605  if (!ret.second)
1606  ret.first.assign_val(std::forward<M>(obj));
1607  return ret;
1608 }
1609 
1631 template <typename Key, typename Value, typename BytesView>
1632 template <typename M, typename K, typename>
1633 std::pair<typename radix_tree<Key, Value, BytesView>::iterator, bool>
1635 {
1636  auto ret = try_emplace(std::forward<K>(k), std::forward<M>(obj));
1637  if (!ret.second)
1638  ret.first.assign_val(std::forward<M>(obj));
1639  return ret;
1640 }
1641 
1651 template <typename Key, typename Value, typename BytesView>
1652 typename radix_tree<Key, Value, BytesView>::size_type
1654 {
1655  return internal_find(k) != nullptr ? 1 : 0;
1656 }
1657 
1670 template <typename Key, typename Value, typename BytesView>
1671 template <typename K, typename>
1672 typename radix_tree<Key, Value, BytesView>::size_type
1674 {
1675  return internal_find(k) != nullptr ? 1 : 0;
1676 }
1677 
1686 template <typename Key, typename Value, typename BytesView>
1689 {
1690  return iterator(internal_find(k), &root);
1691 }
1692 
1701 template <typename Key, typename Value, typename BytesView>
1704 {
1705  return const_iterator(internal_find(k), &root);
1706 }
1707 
1719 template <typename Key, typename Value, typename BytesView>
1720 template <typename K, typename>
1723 {
1724  return iterator(internal_find(k), &root);
1725 }
1726 
1738 template <typename Key, typename Value, typename BytesView>
1739 template <typename K, typename>
1742 {
1743  return const_iterator(internal_find(k), &root);
1744 }
1745 
1746 template <typename Key, typename Value, typename BytesView>
1747 template <typename K>
1750 {
1751  auto key = bytes_view(k);
1752 
1753  auto n = root;
1754  while (n && !n.is_leaf()) {
1755  if (path_length_equal(key.size(), n))
1756  n = n->embedded_entry;
1757  else if (n->byte >= key.size())
1758  return nullptr;
1759  else
1760  n = n->child[slice_index(key[n->byte], n->bit)];
1761  }
1762 
1763  if (!n)
1764  return nullptr;
1765 
1766  if (!keys_equal(key, bytes_view(n.get_leaf()->key())))
1767  return nullptr;
1768 
1769  return n.get_leaf();
1770 }
1771 
1779 template <typename Key, typename Value, typename BytesView>
1780 void
1782 {
1783  if (size() != 0)
1784  erase(begin(), end());
1785 }
1786 
1802 template <typename Key, typename Value, typename BytesView>
1805 {
1806  auto pop = pool_base(pmemobj_pool_by_ptr(this));
1807 
1808  flat_transaction::run(pop, [&] {
1809  auto *leaf = pos.leaf_;
1810  auto parent = leaf->parent;
1811 
1812  /* there are more elements in the container */
1813  if (parent)
1814  ++pos;
1815 
1816  delete_persistent<radix_tree::leaf>(
1818 
1819  size_--;
1820 
1821  /* was root */
1822  if (!parent) {
1823  this->root = nullptr;
1824  pos = begin();
1825  return;
1826  }
1827 
1828  /* It's safe to cast because we're inside non-const method. */
1829  const_cast<tagged_node_ptr &>(*parent->find_child(leaf)) =
1830  nullptr;
1831 
1832  /* Compress the tree vertically. */
1833  auto n = parent;
1834  parent = n->parent;
1835  tagged_node_ptr only_child = nullptr;
1836  for (size_t i = 0; i < SLNODES; i++) {
1837  if (n->child[i]) {
1838  if (only_child) {
1839  /* more than one child */
1840  return;
1841  }
1842  only_child = n->child[i];
1843  }
1844  }
1845 
1846  if (only_child && n->embedded_entry) {
1847  /* There are actually 2 "children" so we can't compress.
1848  */
1849  return;
1850  } else if (n->embedded_entry) {
1851  only_child = n->embedded_entry;
1852  }
1853 
1854  assert(only_child);
1855  parent_ref(only_child) = n->parent;
1856 
1857  auto *child_slot = parent
1858  ? const_cast<tagged_node_ptr *>(&*parent->find_child(n))
1859  : &root;
1860  *child_slot = only_child;
1861 
1862  delete_persistent<radix_tree::node>(n.get_node());
1863  });
1864 
1865  return iterator(const_cast<typename iterator::leaf_ptr>(pos.leaf_),
1866  &root);
1867 }
1868 
1882 template <typename Key, typename Value, typename BytesView>
1885  const_iterator last)
1886 {
1887  auto pop = pool_base(pmemobj_pool_by_ptr(this));
1888 
1889  flat_transaction::run(pop, [&] {
1890  while (first != last)
1891  first = erase(first);
1892  });
1893 
1894  return iterator(const_cast<typename iterator::leaf_ptr>(first.leaf_),
1895  &root);
1896 }
1897 
1910 template <typename Key, typename Value, typename BytesView>
1911 typename radix_tree<Key, Value, BytesView>::size_type
1913 {
1914  auto it = const_iterator(internal_find(k), &root);
1915 
1916  if (it == end())
1917  return 0;
1918 
1919  erase(it);
1920 
1921  return 1;
1922 }
1923 
1939 template <typename Key, typename Value, typename BytesView>
1940 template <typename K, typename>
1941 typename radix_tree<Key, Value, BytesView>::size_type
1943 {
1944  auto it = const_iterator(internal_find(k), &root);
1945 
1946  if (it == end())
1947  return 0;
1948 
1949  erase(it);
1950 
1951  return 1;
1952 }
1953 
1954 template <typename Key, typename Value, typename BytesView>
1955 template <bool Lower, typename K>
1958 {
1959  auto key = bytes_view(k);
1960  auto pop = pool_base(pmemobj_pool_by_ptr(this));
1961 
1962  if (!root)
1963  return end();
1964 
1965  /*
1966  * Need to descend the tree twice. First to find a leaf that
1967  * represents a subtree that shares a common prefix with the key.
1968  * This is needed to find out the actual labels between nodes (they
1969  * are not known due to a possible path compression). Second time to
1970  * get the actual element.
1971  */
1972  auto leaf = common_prefix_leaf(key);
1973  auto leaf_key = bytes_view(leaf->key());
1974  auto diff = prefix_diff(key, leaf_key);
1975  auto sh = bit_diff(leaf_key, key, diff);
1976 
1977  /* Key exists. */
1978  if (diff == key.size() && leaf_key.size() == key.size()) {
1979  if (Lower)
1980  return const_iterator(leaf, &root);
1981  else
1982  return ++const_iterator(leaf, &root);
1983  }
1984 
1985  /* Descend into the tree again. */
1986  const tagged_node_ptr *slot;
1987  tagged_node_ptr prev;
1988  std::tie(slot, prev) = descend(key, diff, sh);
1989 
1990  if (!*slot) {
1991  leaf = next_leaf<node::direction::Forward>(
1992  prev->template make_iterator<node::direction::Forward>(
1993  slot),
1994  prev);
1995 
1996  return const_iterator(leaf, &root);
1997  }
1998 
1999  /* The looked-for key is a prefix of the leaf key. The target node must
2000  * be the smallest leaf within *slot subtree. Key represented by a path
2001  * from root to n is larger than the looked-for key. Additionally keys
2002  * under right siblings of *slot are > key and keys under left siblings
2003  * are < key. */
2004  if (diff == key.size()) {
2005  leaf = find_leaf<node::direction::Forward>(*slot);
2006  return const_iterator(leaf, &root);
2007  }
2008 
2009  /* Leaf's key is a prefix of the looked-for key. Leaf's key is the
2010  * biggest key less than the looked-for key.
2011  * The target node must be the next leaf. */
2012  if (diff == leaf_key.size())
2013  return ++const_iterator(leaf, &root);
2014 
2015  /* *slot is the point of divergence. */
2016  assert(diff < leaf_key.size() && diff < key.size());
2017 
2018  /* The target node must be within *slot subtree. The left siblings
2019  * of *slot are all less than the looked-for key. */
2020  if (compare(key, leaf_key, diff) < 0) {
2021  leaf = find_leaf<node::direction::Forward>(*slot);
2022  return const_iterator(leaf, &root);
2023  }
2024 
2025  if (slot == &root) {
2026  return const_iterator(nullptr, &root);
2027  }
2028 
2029  /* Since looked-for key is larger than *slot, the target node must be
2030  * within subtree of a right sibling of *slot. */
2031  leaf = next_leaf<node::direction::Forward>(
2032  prev->template make_iterator<node::direction::Forward>(slot),
2033  prev);
2034 
2035  return const_iterator(leaf, &root);
2036 }
2037 
2048 template <typename Key, typename Value, typename BytesView>
2049 typename radix_tree<Key, Value, BytesView>::const_iterator
2051 {
2052  return internal_bound<true>(k);
2053 }
2054 
2065 template <typename Key, typename Value, typename BytesView>
2068 {
2069  auto it = const_cast<const radix_tree *>(this)->lower_bound(k);
2070  return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2071  &root);
2072 }
2073 
2087 template <typename Key, typename Value, typename BytesView>
2088 template <typename K, typename>
2091 {
2092  auto it = const_cast<const radix_tree *>(this)->lower_bound(k);
2093  return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2094  &root);
2095 }
2096 
2110 template <typename Key, typename Value, typename BytesView>
2111 template <typename K, typename>
2114 {
2115  return internal_bound<true>(k);
2116 }
2117 
2128 template <typename Key, typename Value, typename BytesView>
2131 {
2132  return internal_bound<false>(k);
2133 }
2134 
2145 template <typename Key, typename Value, typename BytesView>
2148 {
2149  auto it = const_cast<const radix_tree *>(this)->upper_bound(k);
2150  return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2151  &root);
2152 }
2153 
2167 template <typename Key, typename Value, typename BytesView>
2168 template <typename K, typename>
2171 {
2172  auto it = const_cast<const radix_tree *>(this)->upper_bound(k);
2173  return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2174  &root);
2175 }
2176 
2190 template <typename Key, typename Value, typename BytesView>
2191 template <typename K, typename>
2194 {
2195  return internal_bound<false>(k);
2196 }
2197 
2204 template <typename Key, typename Value, typename BytesView>
2207 {
2208  auto const_begin = const_cast<const radix_tree *>(this)->begin();
2209  return iterator(
2210  const_cast<typename iterator::leaf_ptr>(const_begin.leaf_),
2211  &root);
2212 }
2213 
2221 template <typename Key, typename Value, typename BytesView>
2224 {
2225  auto const_end = const_cast<const radix_tree *>(this)->end();
2226  return iterator(
2227  const_cast<typename iterator::leaf_ptr>(const_end.leaf_),
2228  &root);
2229 }
2230 
2237 template <typename Key, typename Value, typename BytesView>
2240 {
2241  if (!root)
2242  return const_iterator(nullptr, &root);
2243 
2244  return const_iterator(
2245  radix_tree::find_leaf<radix_tree::node::direction::Forward>(
2246  root),
2247  &root);
2248 }
2249 
2257 template <typename Key, typename Value, typename BytesView>
2260 {
2261  return const_iterator(nullptr, &root);
2262 }
2263 
2270 template <typename Key, typename Value, typename BytesView>
2273 {
2274  return cbegin();
2275 }
2276 
2284 template <typename Key, typename Value, typename BytesView>
2287 {
2288  return cend();
2289 }
2290 
2296 template <typename Key, typename Value, typename BytesView>
2297 typename radix_tree<Key, Value, BytesView>::reverse_iterator
2299 {
2300  return reverse_iterator(end());
2301 }
2302 
2309 template <typename Key, typename Value, typename BytesView>
2310 typename radix_tree<Key, Value, BytesView>::reverse_iterator
2312 {
2313  return reverse_iterator(begin());
2314 }
2315 
2321 template <typename Key, typename Value, typename BytesView>
2322 typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
2324 {
2325  return const_reverse_iterator(cend());
2326 }
2327 
2334 template <typename Key, typename Value, typename BytesView>
2335 typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
2337 {
2338  return const_reverse_iterator(cbegin());
2339 }
2340 
2341 template <typename Key, typename Value, typename BytesView>
2342 typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
2344 {
2345  return const_reverse_iterator(cend());
2346 }
2347 
2348 template <typename Key, typename Value, typename BytesView>
2349 typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
2351 {
2352  return const_reverse_iterator(cbegin());
2353 }
2354 
2355 template <typename Key, typename Value, typename BytesView>
2356 void
2357 radix_tree<Key, Value, BytesView>::print_rec(std::ostream &os,
2358  radix_tree::tagged_node_ptr n)
2359 {
2360  if (!n.is_leaf()) {
2361  os << "\"" << n.get_node() << "\""
2362  << " [style=filled,color=\"blue\"]" << std::endl;
2363  os << "\"" << n.get_node() << "\" [label=\"byte:" << n->byte
2364  << ", bit:" << int(n->bit) << "\"]" << std::endl;
2365 
2366  auto parent = n->parent ? n->parent.get_node() : 0;
2367  os << "\"" << n.get_node() << "\" -> "
2368  << "\"" << parent << "\" [label=\"parent\"]" << std::endl;
2369 
2370  for (auto it = n->begin(); it != n->end(); ++it) {
2371  if (!(*it))
2372  continue;
2373 
2374  auto ch = it->is_leaf() ? (void *)it->get_leaf()
2375  : (void *)it->get_node();
2376 
2377  os << "\"" << n.get_node() << "\" -> \"" << ch << "\""
2378  << std::endl;
2379  print_rec(os, *it);
2380  }
2381  } else {
2382  auto bv = bytes_view(n.get_leaf()->key());
2383 
2384  os << "\"" << n.get_leaf()
2385  << "\" [style=filled,color=\"green\"]" << std::endl;
2386  os << "\"" << n.get_leaf() << "\" [label=\"key:";
2387 
2388  for (size_t i = 0; i < bv.size(); i++)
2389  os << bv[i];
2390 
2391  os << "\"]" << std::endl;
2392 
2393  auto parent = n.get_leaf()->parent
2394  ? n.get_leaf()->parent.get_node()
2395  : nullptr;
2396 
2397  os << "\"" << n.get_leaf() << "\" -> \"" << parent
2398  << "\" [label=\"parent\"]" << std::endl;
2399 
2400  if (parent && n == parent->embedded_entry) {
2401  os << "{rank=same;\"" << parent << "\";\""
2402  << n.get_leaf() << "\"}" << std::endl;
2403  }
2404  }
2405 }
2406 
2410 template <typename K, typename V, typename BV>
2411 std::ostream &
2412 operator<<(std::ostream &os, const radix_tree<K, V, BV> &tree)
2413 {
2414  os << "digraph Radix {" << std::endl;
2415 
2416  if (tree.root)
2417  radix_tree<K, V, BV>::print_rec(os, tree.root);
2418 
2419  os << "}" << std::endl;
2420 
2421  return os;
2422 }
2423 
2424 /*
2425  * internal: slice_index -- return index of child at the given nib
2426  */
2427 template <typename Key, typename Value, typename BytesView>
2428 unsigned
2430 {
2431  return static_cast<unsigned>(b >> bit) & NIB;
2432 }
2433 
2434 template <typename Key, typename Value, typename BytesView>
2435 radix_tree<Key, Value, BytesView>::tagged_node_ptr::tagged_node_ptr(
2436  std::nullptr_t)
2437  : ptr(nullptr)
2438 {
2439  assert(!(bool)*this);
2440 }
2441 
2442 template <typename Key, typename Value, typename BytesView>
2443 radix_tree<Key, Value, BytesView>::tagged_node_ptr::tagged_node_ptr(
2444  const persistent_ptr<leaf> &ptr)
2445  : ptr(add_tag(ptr.get()))
2446 {
2447  assert(get_leaf() == ptr.get());
2448 }
2449 
2450 template <typename Key, typename Value, typename BytesView>
2451 radix_tree<Key, Value, BytesView>::tagged_node_ptr::tagged_node_ptr(
2452  const persistent_ptr<node> &ptr)
2453  : ptr(ptr.get())
2454 {
2455  assert(get_node() == ptr.get());
2456 }
2457 
2458 template <typename Key, typename Value, typename BytesView>
2459 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr &
2460  radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator=(
2461  std::nullptr_t)
2462 {
2463  ptr = nullptr;
2464  assert(!(bool)*this);
2465 
2466  return *this;
2467 }
2468 
2469 template <typename Key, typename Value, typename BytesView>
2470 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr &
2471 radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator=(
2472  const persistent_ptr<leaf> &rhs)
2473 {
2474  ptr = add_tag(rhs.get());
2475  assert(get_leaf() == rhs.get());
2476 
2477  return *this;
2478 }
2479 
2480 template <typename Key, typename Value, typename BytesView>
2481 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr &
2482 radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator=(
2483  const persistent_ptr<node> &rhs)
2484 {
2485  ptr = rhs.get();
2486  assert(get_node() == rhs.get());
2487 
2488  return *this;
2489 }
2490 
2491 template <typename Key, typename Value, typename BytesView>
2492 bool
2494  const radix_tree::tagged_node_ptr &rhs) const
2495 {
2496  return ptr.to_byte_pointer() == rhs.ptr.to_byte_pointer();
2497 }
2498 
2499 template <typename Key, typename Value, typename BytesView>
2500 bool
2502  const radix_tree::tagged_node_ptr &rhs) const
2503 {
2504  return !(*this == rhs);
2505 }
2506 
2507 template <typename Key, typename Value, typename BytesView>
2508 bool
2510  const radix_tree::leaf *rhs) const
2511 {
2512  return is_leaf() && get_leaf() == rhs;
2513 }
2514 
2515 template <typename Key, typename Value, typename BytesView>
2516 bool
2518  const radix_tree::leaf *rhs) const
2519 {
2520  return !(*this == rhs);
2521 }
2522 
2523 template <typename Key, typename Value, typename BytesView>
2524 void
2526 {
2527  ptr.swap(rhs.ptr);
2528 }
2529 
2530 template <typename Key, typename Value, typename BytesView>
2531 void *
2532 radix_tree<Key, Value, BytesView>::tagged_node_ptr::add_tag(
2533  radix_tree::leaf *ptr) const
2534 {
2535  auto tagged = reinterpret_cast<uintptr_t>(ptr) | uintptr_t(IS_LEAF);
2536  return reinterpret_cast<radix_tree::leaf *>(tagged);
2537 }
2538 
2539 template <typename Key, typename Value, typename BytesView>
2540 void *
2541 radix_tree<Key, Value, BytesView>::tagged_node_ptr::remove_tag(void *ptr) const
2542 {
2543  auto untagged = reinterpret_cast<uintptr_t>(ptr) & ~uintptr_t(IS_LEAF);
2544  return reinterpret_cast<void *>(untagged);
2545 }
2546 
2547 template <typename Key, typename Value, typename BytesView>
2548 bool
2549 radix_tree<Key, Value, BytesView>::tagged_node_ptr::is_leaf() const
2550 {
2551  auto value = reinterpret_cast<uintptr_t>(ptr.to_void_pointer());
2552  return value & uintptr_t(IS_LEAF);
2553 }
2554 
2555 template <typename Key, typename Value, typename BytesView>
2556 typename radix_tree<Key, Value, BytesView>::leaf *
2557 radix_tree<Key, Value, BytesView>::tagged_node_ptr::get_leaf() const
2558 {
2559  assert(is_leaf());
2560  return static_cast<radix_tree::leaf *>(
2561  remove_tag(ptr.to_void_pointer()));
2562 }
2563 
2564 template <typename Key, typename Value, typename BytesView>
2565 typename radix_tree<Key, Value, BytesView>::node *
2566 radix_tree<Key, Value, BytesView>::tagged_node_ptr::get_node() const
2567 {
2568  assert(!is_leaf());
2569  return static_cast<radix_tree::node *>(ptr.to_void_pointer());
2570 }
2571 
2572 template <typename Key, typename Value, typename BytesView>
2573 radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator bool() const
2574  noexcept
2575 {
2576  return remove_tag(ptr.to_void_pointer()) != nullptr;
2577 }
2578 
2579 template <typename Key, typename Value, typename BytesView>
2580 typename radix_tree<Key, Value, BytesView>::node *
2581  radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator->() const
2582  noexcept
2583 {
2584  return get_node();
2585 }
2586 
2587 template <typename Key, typename Value, typename BytesView>
2588 radix_tree<Key, Value, BytesView>::node::forward_iterator::forward_iterator(
2589  pointer child, const node *n)
2590  : child(child), n(n)
2591 {
2592 }
2593 
2594 template <typename Key, typename Value, typename BytesView>
2595 typename radix_tree<Key, Value, BytesView>::node::forward_iterator
2597 {
2598  if (child == &n->embedded_entry)
2599  child = &n->child[0];
2600  else
2601  child++;
2602 
2603  return *this;
2604 }
2605 
2606 template <typename Key, typename Value, typename BytesView>
2607 radix_tree<Key, Value, BytesView>::node::node(tagged_node_ptr parent,
2608  byten_t byte, bitn_t bit)
2609  : parent(parent), byte(byte), bit(bit)
2610 {
2611 }
2612 
2613 template <typename Key, typename Value, typename BytesView>
2614 typename radix_tree<Key, Value, BytesView>::node::forward_iterator
2616 {
2617  if (child == &n->child[0])
2618  child = &n->embedded_entry;
2619  else
2620  child--;
2621 
2622  return *this;
2623 }
2624 
2625 template <typename Key, typename Value, typename BytesView>
2626 typename radix_tree<Key, Value, BytesView>::node::forward_iterator
2628 {
2629  forward_iterator tmp(child, n);
2630  operator++();
2631  return tmp;
2632 }
2633 
2634 template <typename Key, typename Value, typename BytesView>
2635 typename radix_tree<Key, Value, BytesView>::node::forward_iterator::reference
2636  radix_tree<Key, Value, BytesView>::node::forward_iterator::operator*()
2637  const
2638 {
2639  return *child;
2640 }
2641 
2642 template <typename Key, typename Value, typename BytesView>
2643 typename radix_tree<Key, Value, BytesView>::node::forward_iterator::pointer
2644  radix_tree<Key, Value, BytesView>::node::forward_iterator::operator->()
2645  const
2646 {
2647  return child;
2648 }
2649 
2650 template <typename Key, typename Value, typename BytesView>
2651 typename radix_tree<Key, Value, BytesView>::node::forward_iterator::pointer
2652 radix_tree<Key, Value, BytesView>::node::forward_iterator::get_node() const
2653 {
2654  return n;
2655 }
2656 
2657 template <typename Key, typename Value, typename BytesView>
2658 bool
2660  const forward_iterator &rhs) const
2661 {
2662  return child == rhs.child && n == rhs.n;
2663 }
2664 
2665 template <typename Key, typename Value, typename BytesView>
2666 bool
2668  const forward_iterator &rhs) const
2669 {
2670  return child != rhs.child || n != rhs.n;
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
2680 radix_tree<Key, Value, BytesView>::node::begin() const
2681 {
2682  return forward_iterator(&embedded_entry, 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::Forward,
2690  typename radix_tree<Key, Value,
2691  BytesView>::node::forward_iterator>::type
2692 radix_tree<Key, Value, BytesView>::node::end() const
2693 {
2694  return forward_iterator(&child[SLNODES], this);
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
2704 radix_tree<Key, Value, BytesView>::node::begin() const
2705 {
2706  return reverse_iterator(end<direction::Forward>());
2707 }
2708 
2709 template <typename Key, typename Value, typename BytesView>
2710 template <bool Direction>
2711 typename std::enable_if<
2712  Direction ==
2713  radix_tree<Key, Value, BytesView>::node::direction::Reverse,
2714  typename radix_tree<Key, Value,
2715  BytesView>::node::reverse_iterator>::type
2716 radix_tree<Key, Value, BytesView>::node::end() const
2717 {
2718  return reverse_iterator(begin<direction::Forward>());
2719 }
2720 
2721 template <typename Key, typename Value, typename BytesView>
2722 template <bool Direction, typename Ptr>
2723 auto
2724 radix_tree<Key, Value, BytesView>::node::find_child(const Ptr &n) const
2725  -> decltype(begin<Direction>())
2726 {
2727  return std::find(begin<Direction>(), end<Direction>(), n);
2728 }
2729 
2730 template <typename Key, typename Value, typename BytesView>
2731 template <bool Direction, typename Enable>
2732 auto
2733 radix_tree<Key, Value, BytesView>::node::make_iterator(
2734  const tagged_node_ptr *ptr) const -> decltype(begin<Direction>())
2735 {
2736  return forward_iterator(ptr, this);
2737 }
2738 
2739 template <typename Key, typename Value, typename BytesView>
2740 template <bool IsConst>
2741 radix_tree<Key, Value, BytesView>::radix_tree_iterator<
2742  IsConst>::radix_tree_iterator(leaf_ptr leaf_, node_ptr root)
2743  : leaf_(leaf_), root(root)
2744 {
2745 }
2746 
2747 template <typename Key, typename Value, typename BytesView>
2748 template <bool IsConst>
2749 template <bool C, typename Enable>
2750 radix_tree<Key, Value, BytesView>::radix_tree_iterator<
2751  IsConst>::radix_tree_iterator(const radix_tree_iterator<false> &rhs)
2752  : leaf_(rhs.leaf_)
2753 {
2754 }
2755 
2756 template <typename Key, typename Value, typename BytesView>
2757 template <bool IsConst>
2758 typename radix_tree<Key, Value,
2759  BytesView>::template radix_tree_iterator<IsConst>::reference
2760  radix_tree<Key, Value,
2761  BytesView>::radix_tree_iterator<IsConst>::operator*() const
2762 {
2763  assert(leaf_);
2764  return *leaf_;
2765 }
2766 
2767 template <typename Key, typename Value, typename BytesView>
2768 template <bool IsConst>
2769 typename radix_tree<Key, Value,
2770  BytesView>::template radix_tree_iterator<IsConst>::pointer
2771  radix_tree<Key, Value,
2772  BytesView>::radix_tree_iterator<IsConst>::operator->() const
2773 {
2774  assert(leaf_);
2775  return leaf_;
2776 }
2777 
2787 template <typename Key, typename Value, typename BytesView>
2788 template <bool IsConst>
2789 template <typename V, typename Enable>
2790 void
2793 {
2794  auto pop = pool_base(pmemobj_pool_by_ptr(leaf_));
2795 
2796  if (rhs.size() <= leaf_->value().capacity()) {
2797  flat_transaction::run(pop, [&] { leaf_->value() = rhs; });
2798  } else {
2799  tagged_node_ptr *slot;
2800 
2801  if (!leaf_->parent) {
2802  assert(root->get_leaf() == leaf_);
2803  slot = root;
2804  } else {
2805  slot = const_cast<tagged_node_ptr *>(
2806  &*leaf_->parent->find_child(leaf_));
2807  }
2808 
2809  auto old_leaf = leaf_;
2810 
2811  flat_transaction::run(pop, [&] {
2812  *slot = leaf::make_key_args(old_leaf->parent,
2813  old_leaf->key(), rhs);
2814  delete_persistent<typename radix_tree::leaf>(old_leaf);
2815  });
2816 
2817  leaf_ = slot->get_leaf();
2818  }
2819 }
2820 
2826 template <typename Key, typename Value, typename BytesView>
2827 template <bool IsConst>
2828 template <typename T, typename V, typename Enable>
2829 void
2831  T &&rhs)
2832 {
2833  auto pop = pool_base(pmemobj_pool_by_ptr(leaf_));
2834 
2836  [&] { leaf_->value() = std::forward<T>(rhs); });
2837 }
2838 
2839 template <typename Key, typename Value, typename BytesView>
2840 template <bool IsConst>
2841 typename radix_tree<Key, Value,
2842  BytesView>::template radix_tree_iterator<IsConst> &
2844 {
2845  assert(leaf_);
2846 
2847  /* leaf is root, there is no other leaf in the tree */
2848  if (!leaf_->parent)
2849  leaf_ = nullptr;
2850  else {
2851  auto it = leaf_->parent->template find_child<
2852  radix_tree::node::direction::Forward>(leaf_);
2853 
2854  leaf_ = const_cast<leaf_ptr>(
2855  next_leaf<radix_tree::node::direction::Forward>(
2856  it, leaf_->parent));
2857  }
2858 
2859  return *this;
2860 }
2861 
2862 template <typename Key, typename Value, typename BytesView>
2863 template <bool IsConst>
2864 typename radix_tree<Key, Value,
2865  BytesView>::template radix_tree_iterator<IsConst> &
2867 {
2868  if (!leaf_) {
2869  /* this == end() */
2870  leaf_ = const_cast<leaf_ptr>(
2871  radix_tree::find_leaf<
2872  radix_tree::node::direction::Reverse>(*root));
2873  } else {
2874  /* Iterator must be decrementable. */
2875  assert(leaf_->parent);
2876 
2877  auto it = leaf_->parent->template find_child<
2878  radix_tree::node::direction::Reverse>(leaf_);
2879 
2880  leaf_ = const_cast<leaf_ptr>(
2881  next_leaf<radix_tree::node::direction::Reverse>(
2882  it, leaf_->parent));
2883  }
2884 
2885  return *this;
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 typename radix_tree<Key, Value,
2904  BytesView>::template radix_tree_iterator<IsConst>
2906 {
2907  auto tmp = *this;
2908 
2909  --(*this);
2910 
2911  return tmp;
2912 }
2913 
2914 template <typename Key, typename Value, typename BytesView>
2915 template <bool IsConst>
2916 template <bool C>
2917 bool
2919  const radix_tree_iterator<C> &rhs) const
2920 {
2921  return leaf_ != rhs.leaf_;
2922 }
2923 
2924 template <typename Key, typename Value, typename BytesView>
2925 template <bool IsConst>
2926 template <bool C>
2927 bool
2929  const radix_tree_iterator<C> &rhs) const
2930 {
2931  return !(*this != rhs);
2932 }
2933 
2934 /*
2935  * Returns next leaf (either with smaller or larger key, depending on
2936  * ChildIterator type). This function might need to traverse the
2937  * tree upwards.
2938  */
2939 template <typename Key, typename Value, typename BytesView>
2940 template <bool Direction, typename Iterator>
2941 typename radix_tree<Key, Value, BytesView>::leaf *
2942 radix_tree<Key, Value, BytesView>::next_leaf(Iterator node,
2943  tagged_node_ptr parent)
2944 {
2945  do {
2946  ++node;
2947  } while (node != parent->template end<Direction>() && !(*node));
2948 
2949  /* No more children on this level, need to go up. */
2950  if (node == parent->template end<Direction>()) {
2951  auto p = parent->parent;
2952  if (!p) // parent == root
2953  return nullptr;
2954 
2955  auto p_it = p->template find_child<Direction>(parent);
2956  return next_leaf<Direction>(p_it, p);
2957  }
2958 
2959  return find_leaf<Direction>(*node);
2960 }
2961 
2962 /*
2963  * Returns smallest (or biggest, depending on ChildIterator) leaf
2964  * in a subtree.
2965  */
2966 template <typename Key, typename Value, typename BytesView>
2967 template <bool Direction>
2968 typename radix_tree<Key, Value, BytesView>::leaf *
2969 radix_tree<Key, Value, BytesView>::find_leaf(
2970  typename radix_tree<Key, Value, BytesView>::tagged_node_ptr n)
2971 {
2972  assert(n);
2973 
2974  if (n.is_leaf())
2975  return n.get_leaf();
2976 
2977  for (auto it = n->template begin<Direction>();
2978  it != n->template end<Direction>(); ++it) {
2979  if (*it)
2980  return find_leaf<Direction>(*it);
2981  }
2982 
2983  /* There must be at least one leaf at the bottom. */
2984  std::abort();
2985 }
2986 
2987 template <typename Key, typename Value, typename BytesView>
2988 Key &
2989 radix_tree<Key, Value, BytesView>::leaf::key()
2990 {
2991  return *reinterpret_cast<Key *>(this + 1);
2992 }
2993 
2994 template <typename Key, typename Value, typename BytesView>
2995 Value &
2996 radix_tree<Key, Value, BytesView>::leaf::value()
2997 {
2998  auto key_dst = reinterpret_cast<char *>(this + 1);
2999  auto val_dst = reinterpret_cast<Value *>(
3000  key_dst + total_sizeof<Key>::value(key()));
3001 
3002  return *reinterpret_cast<Value *>(val_dst);
3003 }
3004 
3005 template <typename Key, typename Value, typename BytesView>
3006 const Key &
3007 radix_tree<Key, Value, BytesView>::leaf::key() const
3008 {
3009  return *reinterpret_cast<const Key *>(this + 1);
3010 }
3011 
3012 template <typename Key, typename Value, typename BytesView>
3013 const Value &
3014 radix_tree<Key, Value, BytesView>::leaf::value() const
3015 {
3016  auto key_dst = reinterpret_cast<const char *>(this + 1);
3017  auto val_dst = reinterpret_cast<const Value *>(
3018  key_dst + total_sizeof<Key>::value(key()));
3019 
3020  return *reinterpret_cast<const Value *>(val_dst);
3021 }
3022 
3023 template <typename Key, typename Value, typename BytesView>
3024 radix_tree<Key, Value, BytesView>::leaf::~leaf()
3025 {
3026  detail::destroy<Key>(key());
3027  detail::destroy<Value>(value());
3028 }
3029 
3030 template <typename Key, typename Value, typename BytesView>
3031 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3032 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent)
3033 {
3034  auto t = std::make_tuple();
3035  return make(parent, std::piecewise_construct, t, t,
3036  typename detail::make_index_sequence<>::type{},
3037  typename detail::make_index_sequence<>::type{});
3038 }
3039 
3040 template <typename Key, typename Value, typename BytesView>
3041 template <typename... Args1, typename... Args2>
3042 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3043 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
3044  std::piecewise_construct_t pc,
3045  std::tuple<Args1...> first_args,
3046  std::tuple<Args2...> second_args)
3047 {
3048  return make(parent, pc, first_args, second_args,
3049  typename detail::make_index_sequence<Args1...>::type{},
3050  typename detail::make_index_sequence<Args2...>::type{});
3051 }
3052 
3053 template <typename Key, typename Value, typename BytesView>
3054 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3055 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
3056  const Key &k, const Value &v)
3057 {
3058  return make(parent, std::piecewise_construct, std::forward_as_tuple(k),
3059  std::forward_as_tuple(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(tagged_node_ptr parent, K &&k,
3066  V &&v)
3067 {
3068  return make(parent, std::piecewise_construct,
3069  std::forward_as_tuple(std::forward<K>(k)),
3070  std::forward_as_tuple(std::forward<V>(v)));
3071 }
3072 
3073 template <typename Key, typename Value, typename BytesView>
3074 template <typename K, typename... Args>
3075 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3076 radix_tree<Key, Value, BytesView>::leaf::make_key_args(tagged_node_ptr parent,
3077  K &&k, Args &&... args)
3078 {
3079  return make(parent, std::piecewise_construct,
3080  std::forward_as_tuple(std::forward<K>(k)),
3081  std::forward_as_tuple(std::forward<Args>(args)...));
3082 }
3083 
3084 template <typename Key, typename Value, typename BytesView>
3085 template <typename K, typename V>
3086 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3087 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
3088  detail::pair<K, V> &&p)
3089 {
3090  return make(parent, std::piecewise_construct,
3091  std::forward_as_tuple(std::move(p.first)),
3092  std::forward_as_tuple(std::move(p.second)));
3093 }
3094 
3095 template <typename Key, typename Value, typename BytesView>
3096 template <typename K, typename V>
3097 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3098 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
3099  const detail::pair<K, V> &p)
3100 {
3101  return make(parent, std::piecewise_construct,
3102  std::forward_as_tuple(p.first),
3103  std::forward_as_tuple(p.second));
3104 }
3105 
3106 template <typename Key, typename Value, typename BytesView>
3107 template <typename K, typename V>
3108 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3109 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
3110  std::pair<K, V> &&p)
3111 {
3112  return make(parent, std::piecewise_construct,
3113  std::forward_as_tuple(std::move(p.first)),
3114  std::forward_as_tuple(std::move(p.second)));
3115 }
3116 
3117 template <typename Key, typename Value, typename BytesView>
3118 template <typename K, typename V>
3119 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3120 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
3121  const std::pair<K, V> &p)
3122 {
3123  return make(parent, std::piecewise_construct,
3124  std::forward_as_tuple(p.first),
3125  std::forward_as_tuple(p.second));
3126 }
3127 
3128 template <typename Key, typename Value, typename BytesView>
3129 template <typename... Args1, typename... Args2, size_t... I1, size_t... I2>
3130 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3131 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
3132  std::piecewise_construct_t,
3133  std::tuple<Args1...> &first_args,
3134  std::tuple<Args2...> &second_args,
3135  detail::index_sequence<I1...>,
3136  detail::index_sequence<I2...>)
3137 {
3138  standard_alloc_policy<void> a;
3139  auto key_size = total_sizeof<Key>::value(std::get<I1>(first_args)...);
3140  auto val_size =
3141  total_sizeof<Value>::value(std::get<I2>(second_args)...);
3142  auto ptr = static_cast<persistent_ptr<leaf>>(
3143  a.allocate(sizeof(leaf) + key_size + val_size));
3144 
3145  auto key_dst = reinterpret_cast<Key *>(ptr.get() + 1);
3146  auto val_dst = reinterpret_cast<Value *>(
3147  reinterpret_cast<char *>(key_dst) + key_size);
3148 
3149  new (ptr.get()) leaf();
3150  new (key_dst) Key(std::forward<Args1>(std::get<I1>(first_args))...);
3151  new (val_dst) Value(std::forward<Args2>(std::get<I2>(second_args))...);
3152 
3153  ptr->parent = parent;
3154 
3155  return ptr;
3156 }
3157 
3158 template <typename Key, typename Value, typename BytesView>
3159 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3160 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
3161  const leaf &other)
3162 {
3163  return make(parent, other.key(), other.value());
3164 }
3165 
3172 template <typename Key, typename Value, typename BytesView>
3173 void
3175 {
3176  if (nullptr == pmemobj_pool_by_ptr(this))
3177  throw pmem::pool_error("Invalid pool handle.");
3178 }
3179 
3187 template <typename Key, typename Value, typename BytesView>
3188 void
3190 {
3191  if (pmemobj_tx_stage() != TX_STAGE_WORK)
3193  "Function called out of transaction scope.");
3194 }
3195 
3199 template <typename Key, typename Value, typename BytesView>
3200 void
3203 {
3204  lhs.swap(rhs);
3205 }
3206 
3207 } /* namespace experimental */
3208 } /* namespace obj */
3209 
3210 namespace detail
3211 {
3212 /* Check if type is pmem::obj::basic_string or
3213  * pmem::obj::basic_inline_string */
3214 template <typename>
3215 struct is_string : std::false_type {
3216 };
3217 
3218 template <typename CharT, typename Traits>
3219 struct is_string<obj::basic_string<CharT, Traits>> : std::true_type {
3220 };
3221 
3222 template <typename CharT, typename Traits>
3223 struct is_string<obj::experimental::basic_inline_string<CharT, Traits>>
3224  : std::true_type {
3225 };
3226 
3227 template <typename T>
3228 struct bytes_view<T, typename std::enable_if<is_string<T>::value>::type> {
3229  using CharT = typename T::value_type;
3230  using Traits = typename T::traits_type;
3231 
3232  template <
3233  typename C,
3234  typename Enable = typename std::enable_if<std::is_constructible<
3235  obj::basic_string_view<CharT, Traits>, C>::value>::type>
3236  bytes_view(const C *s) : s(*s)
3237  {
3238  }
3239 
3240  char operator[](std::size_t p) const
3241  {
3242  return reinterpret_cast<const char *>(s.data())[p];
3243  }
3244 
3245  size_t
3246  size() const
3247  {
3248  return s.size() * sizeof(CharT);
3249  }
3250 
3251  obj::basic_string_view<CharT, Traits> s;
3252 
3253  using is_transparent = void;
3254 };
3255 
3256 template <typename T>
3257 struct bytes_view<T,
3258  typename std::enable_if<std::is_integral<T>::value &&
3259  !std::is_signed<T>::value>::type> {
3260  bytes_view(const T *k) : k(k)
3261  {
3262 #if __cpp_lib_endian
3263  static_assert(
3264  std::endian::native == std::endian::little,
3265  "Scalar type are not little endian on this platform!");
3266 #elif !defined(NDEBUG)
3267  /* Assert little endian is used. */
3268  uint16_t word = (2 << 8) + 1;
3269  assert(((char *)&word)[0] == 1);
3270 #endif
3271  }
3272 
3273  char operator[](std::size_t p) const
3274  {
3275  return reinterpret_cast<const char *>(k)[size() - p - 1];
3276  }
3277 
3278  constexpr size_t
3279  size() const
3280  {
3281  return sizeof(T);
3282  }
3283 
3284  const T *k;
3285 };
3286 } /* namespace detail */
3287 
3288 } /* namespace pmem */
3289 
3290 #endif /* LIBPMEMOBJ_CPP_RADIX_HPP */
Persistent memory aware allocator.
Our partial std::string_view implementation.
Definition: string_view.hpp:46
constexpr size_type size() const noexcept
Returns count of characters stored in this pmem::obj::string_view data.
Definition: string_view.hpp:334
static void run(obj::pool_base &pool, std::function< void()> tx, Locks &... locks)
Execute a closure-like transaction and lock locks.
Definition: transaction.hpp:688
Radix tree is an associative, ordered container.
Definition: radix_tree.hpp:105
const_iterator cend() const
Returns a const iterator to the element following the last element of the map.
Definition: radix_tree.hpp:2259
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:1375
void check_tx_stage_work()
Private helper function.
Definition: radix_tree.hpp:3189
friend std::ostream & operator<<(std::ostream &os, const radix_tree< K, V, BV > &tree)
Prints tree in DOT format.
Definition: radix_tree.hpp:2412
void swap(radix_tree &rhs)
Member swap.
Definition: radix_tree.hpp:927
const_iterator cbegin() const
Returns a const iterator to the first element of the container.
Definition: radix_tree.hpp:2239
reverse_iterator rend()
Returns a reverse iterator to the end.
Definition: radix_tree.hpp:2311
void clear()
Erases all elements from the container transactionally.
Definition: radix_tree.hpp:1781
iterator end()
Returns an iterator to the element following the last element of the map.
Definition: radix_tree.hpp:2223
void check_pmem()
Private helper function.
Definition: radix_tree.hpp:3174
const_reverse_iterator crbegin() const
Returns a const, reverse iterator to the beginning.
Definition: radix_tree.hpp:2323
iterator upper_bound(const key_type &k)
Returns an iterator pointing to the first element that is greater than key.
Definition: radix_tree.hpp:2147
uint64_t size() const noexcept
Definition: radix_tree.hpp:915
reverse_iterator rbegin()
Returns a reverse iterator to the beginning.
Definition: radix_tree.hpp:2298
bool empty() const noexcept
Checks whether the container is empty.
Definition: radix_tree.hpp:895
radix_tree()
Default radix tree constructor.
Definition: radix_tree.hpp:671
size_type max_size() const noexcept
Definition: radix_tree.hpp:905
~radix_tree()
Destructor.
Definition: radix_tree.hpp:879
radix_tree & operator=(const radix_tree &m)
Copy assignment operator.
Definition: radix_tree.hpp:792
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:2067
iterator find(const key_type &k)
Finds an element with key equivalent to key.
Definition: radix_tree.hpp:1688
iterator begin()
Returns an iterator to the first element of the container.
Definition: radix_tree.hpp:2206
iterator erase(const_iterator pos)
Removes the element at pos from the container.
Definition: radix_tree.hpp:1804
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:1653
const_reverse_iterator crend() const
Returns a const, reverse iterator to the end.
Definition: radix_tree.hpp:2336
Volatile residing on pmem class.
Definition: v.hpp:42
static void run(obj::pool_base &pool, std::function< void()> tx, Locks &... locks)
Execute a closure-like transaction and lock locks.
Definition: transaction.hpp:817
Resides on pmem class.
Definition: p.hpp:35
Persistent pointer class.
Definition: persistent_ptr.hpp:152
The non-template pool base class.
Definition: pool.hpp:46
Custom pool error class.
Definition: pexceptions.hpp:45
Custom transaction error class.
Definition: pexceptions.hpp:158
Commonly used functionality.
Inline string implementation.
Create c++14 style index sequence.
Persistent_ptr transactional allocation functions for objects.
bool operator==(self_relative_ptr< T > const &lhs, self_relative_ptr< Y > const &rhs) noexcept
Equality operator.
Definition: self_relative_ptr.hpp:387
std::ostream & operator<<(std::ostream &os, const radix_tree< K, V, BV > &tree)
Prints tree in DOT format.
Definition: radix_tree.hpp:2412
void swap(concurrent_map< Key, Value, Comp, Allocator > &lhs, concurrent_map< Key, Value, Comp, Allocator > &rhs)
Non-member swap.
Definition: concurrent_map.hpp:151
void swap(radix_tree< Key, Value, BytesView > &lhs, radix_tree< Key, Value, BytesView > &rhs)
Non-member swap.
Definition: radix_tree.hpp:3201
bool operator!=(self_relative_ptr< T > const &lhs, self_relative_ptr< Y > const &rhs) noexcept
Inequality operator.
Definition: self_relative_ptr.hpp:398
p< T > & operator++(p< T > &pp)
Prefix increment operator overload.
Definition: pext.hpp:48
pmem::obj::array< T, N >::const_iterator cbegin(const pmem::obj::array< T, N > &a)
Non-member cbegin.
Definition: array.hpp:760
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
p< T > & operator--(p< T > &pp)
Prefix decrement operator overload.
Definition: pext.hpp:59
pmem::obj::array< T, N >::iterator end(pmem::obj::array< T, N > &a)
Non-member end.
Definition: array.hpp:820
T & get(pmem::obj::array< T, N > &a)
Non-member get function.
Definition: array.hpp:890
pool_base pool_by_vptr(const T *that)
Retrieve pool handle for the given pointer.
Definition: utils.hpp:32
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::array< T, N >::const_iterator cend(const pmem::obj::array< T, N > &a)
Non-member cend.
Definition: array.hpp:770
pmem::obj::array< T, N >::iterator begin(pmem::obj::array< T, N > &a)
Non-member begin.
Definition: array.hpp:800
Persistent memory namespace.
Definition: allocation_flag.hpp:15
Resides on pmem property template.
Persistent smart pointer.
Convenience extensions for the resides on pmem property template.
C++ pmemobj pool.
Persistent self-relative smart pointer.
String typedefs for common character types.
Our partial std::string_view implementation.
This is the structure which 'holds' key/value pair.
Definition: radix_tree.hpp:401
This is internal node.
Definition: radix_tree.hpp:467
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:496
tagged_node_ptr parent
Pointer to a parent node.
Definition: radix_tree.hpp:473
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:481
Radix tree iterator supports multipass and bidirectional iteration.
Definition: radix_tree.hpp:571
Commonly used SFINAE helpers.
C++ pmemobj transactions.
Libpmemobj C++ utils.