PMDK C++ bindings  1.13.0-git107.g7e59f08f
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-2022, Intel Corporation */
3 
12 #ifndef LIBPMEMOBJ_CPP_RADIX_HPP
13 #define LIBPMEMOBJ_CPP_RADIX_HPP
14 
15 #include <libpmemobj++/allocator.hpp>
16 #include <libpmemobj++/container/string.hpp>
17 #include <libpmemobj++/detail/pair.hpp>
18 #include <libpmemobj++/detail/template_helpers.hpp>
19 #include <libpmemobj++/experimental/inline_string.hpp>
20 #include <libpmemobj++/experimental/self_relative_ptr.hpp>
21 #include <libpmemobj++/experimental/v.hpp>
22 #include <libpmemobj++/make_persistent.hpp>
23 #include <libpmemobj++/p.hpp>
24 #include <libpmemobj++/persistent_ptr.hpp>
25 #include <libpmemobj++/pext.hpp>
26 #include <libpmemobj++/pool.hpp>
27 #include <libpmemobj++/string_view.hpp>
28 #include <libpmemobj++/transaction.hpp>
29 #include <libpmemobj++/utils.hpp>
30 
31 #include <algorithm>
32 #include <iostream>
33 #include <string>
34 #if __cpp_lib_endian
35 #include <bit>
36 #endif
37 
38 #include <libpmemobj++/detail/common.hpp>
39 #include <libpmemobj++/detail/ebr.hpp>
40 #include <libpmemobj++/detail/integer_sequence.hpp>
41 #include <libpmemobj++/detail/tagged_ptr.hpp>
42 
43 namespace pmem
44 {
45 
46 namespace obj
47 {
48 
49 namespace experimental
50 {
51 
52 template <typename T, typename Enable = void>
53 struct bytes_view;
54 
121 template <typename Key, typename Value, typename BytesView = bytes_view<Key>,
122  bool MtMode = false>
123 class radix_tree {
124  template <bool IsConst>
125  struct radix_tree_iterator;
126 
127 public:
128  using key_type = Key;
129  using mapped_type = Value;
130  using value_type = detail::pair<const key_type, mapped_type>;
131  using size_type = std::size_t;
132  using reference = value_type &;
133  using const_reference = const value_type &;
134  using iterator = radix_tree_iterator<false>;
135  using const_iterator = radix_tree_iterator<true>;
136  using reverse_iterator = std::reverse_iterator<iterator>;
137  using const_reverse_iterator = std::reverse_iterator<const_iterator>;
138  using difference_type = std::ptrdiff_t;
139  using ebr = detail::ebr;
140  using worker_type = detail::ebr::worker;
141 
142  radix_tree();
143 
144  template <class InputIt>
145  radix_tree(InputIt first, InputIt last);
146  radix_tree(const radix_tree &m);
147  radix_tree(radix_tree &&m);
148  radix_tree(std::initializer_list<value_type> il);
149 
150  radix_tree &operator=(const radix_tree &m);
151  radix_tree &operator=(radix_tree &&m);
152  radix_tree &operator=(std::initializer_list<value_type> ilist);
153 
154  ~radix_tree();
155 
156  template <class... Args>
157  std::pair<iterator, bool> emplace(Args &&... args);
158 
159  std::pair<iterator, bool> insert(const value_type &v);
160  std::pair<iterator, bool> insert(value_type &&v);
161  template <typename P,
162  typename = typename std::enable_if<
163  std::is_constructible<value_type, P &&>::value,
164  P>::type>
165  std::pair<iterator, bool> insert(P &&p);
166  /* iterator insert(const_iterator position, const value_type &v); */
167  /* iterator insert(const_iterator position, value_type &&v); */
168  /* template <
169  typename P,
170  typename = typename std::enable_if<
171  detail::has_is_transparent<BytesView>::value, P>::type>
172  iterator insert(const_iterator position, P &&p); */
173  template <class InputIterator>
174  void insert(InputIterator first, InputIterator last);
175  void insert(std::initializer_list<value_type> il);
176  // insert_return_type insert(node_type&& nh);
177  // iterator insert(const_iterator hint, node_type&& nh);
178 
179  template <class... Args>
180  std::pair<iterator, bool> try_emplace(const key_type &k,
181  Args &&... args);
182  template <class... Args>
183  std::pair<iterator, bool> try_emplace(key_type &&k, Args &&... args);
184  /*template <class... Args>
185  iterator try_emplace(const_iterator hint, const key_type &k,
186  Args &&... args);*/
187  /*template <class... Args>
188  iterator try_emplace(const_iterator hint, key_type &&k,
189  Args &&... args);*/
190  /* https://gcc.gnu.org/bugzilla/show_bug.cgi?id=96976 */
191  template <typename K, typename BV = BytesView, class... Args>
192  auto try_emplace(K &&k, Args &&... args) -> typename std::enable_if<
193  detail::has_is_transparent<BV>::value &&
194  !std::is_same<typename std::remove_const<
195  typename std::remove_reference<
196  K>::type>::type,
197  key_type>::value,
198  std::pair<iterator, bool>>::type;
199 
200  template <typename M>
201  std::pair<iterator, bool> insert_or_assign(const key_type &k, M &&obj);
202  template <typename M>
203  std::pair<iterator, bool> insert_or_assign(key_type &&k, M &&obj);
204  /*template <typename M>
205  iterator insert_or_assign(const_iterator hint, const key_type &k,
206  M &&obj);*/
207  /*template <typename M>
208  iterator insert_or_assign(const_iterator hint, key_type &&k, M &&obj);*/
209  template <
210  typename M, typename K,
211  typename = typename std::enable_if<
212  detail::has_is_transparent<BytesView>::value, K>::type>
213  std::pair<iterator, bool> insert_or_assign(K &&k, M &&obj);
214 
215  iterator erase(const_iterator pos);
216  iterator erase(const_iterator first, const_iterator last);
217  size_type erase(const key_type &k);
218  template <typename K,
219  typename = typename std::enable_if<
220  detail::has_is_transparent<BytesView>::value &&
221  !std::is_same<K, iterator>::value &&
222  !std::is_same<K, const_iterator>::value,
223  K>::type>
224  size_type erase(const K &k);
225 
226  void clear();
227 
228  size_type count(const key_type &k) const;
229  template <
230  typename K,
231  typename = typename std::enable_if<
232  detail::has_is_transparent<BytesView>::value, K>::type>
233  size_type count(const K &k) const;
234 
235  iterator find(const key_type &k);
236  const_iterator find(const key_type &k) const;
237  template <
238  typename K,
239  typename = typename std::enable_if<
240  detail::has_is_transparent<BytesView>::value, K>::type>
241  iterator find(const K &k);
242  template <
243  typename K,
244  typename = typename std::enable_if<
245  detail::has_is_transparent<BytesView>::value, K>::type>
246  const_iterator find(const K &k) const;
247 
248  iterator lower_bound(const key_type &k);
249  const_iterator lower_bound(const key_type &k) const;
250  template <
251  typename K,
252  typename = typename std::enable_if<
253  detail::has_is_transparent<BytesView>::value, K>::type>
254  iterator lower_bound(const K &k);
255  template <
256  typename K,
257  typename = typename std::enable_if<
258  detail::has_is_transparent<BytesView>::value, K>::type>
259  const_iterator lower_bound(const K &k) const;
260 
261  iterator upper_bound(const key_type &k);
262  const_iterator upper_bound(const key_type &k) const;
263  template <
264  typename K,
265  typename = typename std::enable_if<
266  detail::has_is_transparent<BytesView>::value, K>::type>
267  iterator upper_bound(const K &k);
268  template <
269  typename K,
270  typename = typename std::enable_if<
271  detail::has_is_transparent<BytesView>::value, K>::type>
272  const_iterator upper_bound(const K &k) const;
273 
274  iterator begin();
275  iterator end();
276  const_iterator cbegin() const;
277  const_iterator cend() const;
278  const_iterator begin() const;
279  const_iterator end() const;
280 
281  reverse_iterator rbegin();
282  reverse_iterator rend();
283  const_reverse_iterator crbegin() const;
284  const_reverse_iterator crend() const;
285  const_reverse_iterator rbegin() const;
286  const_reverse_iterator rend() const;
287 
288  /* capacity: */
289  bool empty() const noexcept;
290  size_type max_size() const noexcept;
291  uint64_t size() const noexcept;
292 
293  void swap(radix_tree &rhs);
294 
295  template <typename K, typename V, typename BV, bool Mt>
296  friend std::ostream &operator<<(std::ostream &os,
297  const radix_tree<K, V, BV, Mt> &tree);
298 
299  template <bool Mt = MtMode,
300  typename Enable = typename std::enable_if<Mt>::type>
301  void garbage_collect();
302  template <bool Mt = MtMode,
303  typename Enable = typename std::enable_if<Mt>::type>
304  void garbage_collect_force();
305 
306  template <bool Mt = MtMode,
307  typename Enable = typename std::enable_if<Mt>::type>
308  void runtime_initialize_mt(ebr *e = new ebr());
309  template <bool Mt = MtMode,
310  typename Enable = typename std::enable_if<Mt>::type>
311  void runtime_finalize_mt();
312 
313  template <bool Mt = MtMode,
314  typename Enable = typename std::enable_if<Mt>::type>
315  worker_type register_worker();
316 
317 private:
318  using byten_t = uint64_t;
319  using bitn_t = uint8_t;
320 
321  /* Size of a chunk which differentiates subtrees of a node */
322  static constexpr std::size_t SLICE = 4;
323  /* Mask for SLICE */
324  static constexpr std::size_t NIB = ((1ULL << SLICE) - 1);
325  /* Number of children in internal nodes */
326  static constexpr std::size_t SLNODES = (1 << SLICE);
327  /* Mask for SLICE */
328  static constexpr bitn_t SLICE_MASK = (bitn_t) ~(SLICE - 1);
329  /* Position of the first SLICE */
330  static constexpr bitn_t FIRST_NIB = 8 - SLICE;
331  /* Number of EBR epochs */
332  static constexpr size_t EPOCHS_NUMBER = 3;
333 
334  struct leaf;
335  struct node;
336 
337  using pointer_type = detail::tagged_ptr<leaf, node>;
338  using atomic_pointer_type =
339  typename std::conditional<MtMode, std::atomic<pointer_type>,
340  pointer_type>::type;
341 
342  /* This structure holds snapshotted view of a node. */
343  struct node_desc {
344  const atomic_pointer_type *slot;
345  pointer_type node;
346  pointer_type prev;
347  };
348 
349  using path_type = std::vector<node_desc>;
350 
351  /* Arbitrarily chosen value, overhead of vector resizing for deep radix
352  * tree will not be noticeable. */
353  static constexpr size_t PATH_INIT_CAP = 64;
354 
355  /*** pmem members ***/
356  atomic_pointer_type root;
357  p<uint64_t> size_;
358  vector<pointer_type> garbages[EPOCHS_NUMBER];
359 
360  ebr *ebr_ = nullptr;
361 
362  /* helper functions */
363  template <typename K, typename F, class... Args>
364  std::pair<iterator, bool> internal_emplace(const K &, F &&);
365  template <typename K>
366  leaf *internal_find(const K &k) const;
367 
368  static atomic_pointer_type &parent_ref(pointer_type n);
369  template <typename K1, typename K2>
370  static bool keys_equal(const K1 &k1, const K2 &k2);
371  template <typename K1, typename K2>
372  static int compare(const K1 &k1, const K2 &k2, byten_t offset = 0);
373  template <bool Direction, typename Iterator>
374  std::pair<bool, const leaf *> next_leaf(Iterator child,
375  pointer_type parent) const;
376  template <bool Direction>
377  const leaf *find_leaf(pointer_type n) const;
378  static unsigned slice_index(char k, uint8_t shift);
379  template <typename K1, typename K2>
380  static byten_t prefix_diff(const K1 &lhs, const K2 &rhs,
381  byten_t offset = 0);
382  leaf *any_leftmost_leaf(pointer_type n, size_type min_depth) const;
383  template <typename K1, typename K2>
384  static bitn_t bit_diff(const K1 &leaf_key, const K2 &key, byten_t diff);
385  template <typename K>
386  std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::leaf *,
387  path_type>
388  descend(pointer_type n, const K &key) const;
389  static void print_rec(std::ostream &os, radix_tree::pointer_type n);
390  template <typename K>
391  static BytesView bytes_view(const K &k);
392  static string_view bytes_view(string_view s);
393  static bool path_length_equal(size_t key_size, pointer_type n);
394  template <bool Lower, typename K>
395  bool validate_bound(const_iterator it, const K &key) const;
396  node_desc follow_path(const path_type &, byten_t diff, bitn_t sh) const;
397  template <bool Mt = MtMode>
398  typename std::enable_if<Mt, bool>::type
399  validate_path(const path_type &path) const;
400  template <bool Mt = MtMode>
401  typename std::enable_if<!Mt, bool>::type
402  validate_path(const path_type &path) const;
403  template <bool Lower, typename K>
404  const_iterator internal_bound(const K &k) const;
405  static bool is_leaf(const pointer_type &p);
406  static leaf *get_leaf(const pointer_type &p);
407  static node *get_node(const pointer_type &p);
408  template <typename T>
409  void free(persistent_ptr<T> ptr);
410  void clear_garbage(size_t n);
411  static pointer_type
412  load(const std::atomic<detail::tagged_ptr<leaf, node>> &ptr);
413  static pointer_type load(const pointer_type &ptr);
414  static void store(std::atomic<detail::tagged_ptr<leaf, node>> &ptr,
415  pointer_type desired);
416  static void store(pointer_type &ptr, pointer_type desired);
417  void check_pmem();
418  void check_tx_stage_work();
419 
420  static_assert(sizeof(node) == 256,
421  "Internal node should have size equal to 256 bytes.");
422 };
423 
424 template <typename Key, typename Value, typename BytesView, bool MtMode>
425 void swap(radix_tree<Key, Value, BytesView, MtMode> &lhs,
426  radix_tree<Key, Value, BytesView, MtMode> &rhs);
427 
437 template <typename Key, typename Value, typename BytesView, bool MtMode>
438 struct radix_tree<Key, Value, BytesView, MtMode>::leaf {
439  using tree_type = radix_tree<Key, Value, BytesView, MtMode>;
440 
441  leaf(const leaf &) = delete;
442  leaf(leaf &&) = delete;
443 
444  leaf &operator=(const leaf &) = delete;
445  leaf &operator=(leaf &&) = delete;
446 
447  ~leaf();
448 
449  Key &key();
450  Value &value();
451 
452  const Key &key() const;
453  const Value &value() const;
454 
455  static persistent_ptr<leaf> make(pointer_type parent);
456 
457  template <typename... Args1, typename... Args2>
458  static persistent_ptr<leaf>
459  make(pointer_type parent, std::piecewise_construct_t pc,
460  std::tuple<Args1...> first_args, std::tuple<Args2...> second_args);
461  template <typename K, typename V>
462  static persistent_ptr<leaf> make(pointer_type parent, K &&k, V &&v);
463  static persistent_ptr<leaf> make(pointer_type parent, const Key &k,
464  const Value &v);
465  template <typename K, typename... Args>
466  static persistent_ptr<leaf> make_key_args(pointer_type parent, K &&k,
467  Args &&... args);
468  template <typename K, typename V>
469  static persistent_ptr<leaf> make(pointer_type parent,
470  detail::pair<K, V> &&p);
471  template <typename K, typename V>
472  static persistent_ptr<leaf> make(pointer_type parent,
473  const detail::pair<K, V> &p);
474  template <typename K, typename V>
475  static persistent_ptr<leaf> make(pointer_type parent,
476  std::pair<K, V> &&p);
477  template <typename K, typename V>
478  static persistent_ptr<leaf> make(pointer_type parent,
479  const std::pair<K, V> &p);
480  static persistent_ptr<leaf> make(pointer_type parent,
481  const leaf &other);
482 
483 private:
484  friend class radix_tree<Key, Value, BytesView, MtMode>;
485 
486  leaf() = default;
487 
488  template <typename... Args1, typename... Args2, size_t... I1,
489  size_t... I2>
490  static persistent_ptr<leaf>
491  make(pointer_type parent, std::piecewise_construct_t,
492  std::tuple<Args1...> &first_args,
493  std::tuple<Args2...> &second_args, detail::index_sequence<I1...>,
494  detail::index_sequence<I2...>);
495 
496  atomic_pointer_type parent;
497 };
498 
503 template <typename Key, typename Value, typename BytesView, bool MtMode>
504 struct radix_tree<Key, Value, BytesView, MtMode>::node {
505  node(pointer_type parent, byten_t byte, bitn_t bit);
506 
510  atomic_pointer_type parent;
511 
518  atomic_pointer_type embedded_entry;
519 
520  /* Children can be both leaves and internal nodes. */
521  atomic_pointer_type child[SLNODES];
522 
533  byten_t byte;
534  bitn_t bit;
535 
536  struct direction {
537  static constexpr bool Forward = 0;
538  static constexpr bool Reverse = 1;
539  };
540 
541  struct forward_iterator;
542  using reverse_iterator = std::reverse_iterator<forward_iterator>;
543 
544  template <bool Direction>
545  using iterator =
546  typename std::conditional<Direction == direction::Forward,
547  forward_iterator,
548  reverse_iterator>::type;
549 
550  template <bool Direction = direction::Forward>
551  typename std::enable_if<
552  Direction ==
553  radix_tree<Key, Value, BytesView,
554  MtMode>::node::direction::Forward,
555  typename radix_tree<Key, Value, BytesView,
556  MtMode>::node::forward_iterator>::type
557  begin() const;
558 
559  template <bool Direction = direction::Forward>
560  typename std::enable_if<
561  Direction ==
562  radix_tree<Key, Value, BytesView,
563  MtMode>::node::direction::Forward,
564  typename radix_tree<Key, Value, BytesView,
565  MtMode>::node::forward_iterator>::type
566  end() const;
567 
568  /* rbegin */
569  template <bool Direction = direction::Forward>
570  typename std::enable_if<
571  Direction ==
572  radix_tree<Key, Value, BytesView,
573  MtMode>::node::direction::Reverse,
574  typename radix_tree<Key, Value, BytesView,
575  MtMode>::node::reverse_iterator>::type
576  begin() const;
577 
578  /* rend */
579  template <bool Direction = direction::Forward>
580  typename std::enable_if<
581  Direction ==
582  radix_tree<Key, Value, BytesView,
583  MtMode>::node::direction::Reverse,
584  typename radix_tree<Key, Value, BytesView,
585  MtMode>::node::reverse_iterator>::type
586  end() const;
587 
588  template <bool Direction = direction::Forward, typename Ptr>
589  iterator<Direction> find_child(const Ptr &n) const;
590 
591  template <bool Direction = direction::Forward,
592  typename Enable = typename std::enable_if<
593  Direction == direction::Forward>::type>
594  iterator<Direction> make_iterator(const atomic_pointer_type *ptr) const;
595 
596  uint8_t padding[256 - sizeof(parent) - sizeof(leaf) - sizeof(child) -
597  sizeof(byte) - sizeof(bit)];
598 };
599 
605 template <typename Key, typename Value, typename BytesView, bool MtMode>
606 template <bool IsConst>
607 struct radix_tree<Key, Value, BytesView, MtMode>::radix_tree_iterator {
608 private:
609  using leaf_ptr =
610  typename std::conditional<IsConst, const leaf *, leaf *>::type;
611  using tree_ptr = typename std::conditional<IsConst, const radix_tree *,
612  radix_tree *>::type;
613  friend struct radix_tree_iterator<true>;
614 
615 public:
616  using difference_type = std::ptrdiff_t;
617  using value_type = radix_tree::leaf;
618  using reference = typename std::conditional<IsConst, const value_type &,
619  value_type &>::type;
620  using pointer = typename std::conditional<IsConst, value_type const *,
621  value_type *>::type;
622  using iterator_category = typename std::conditional<
623  MtMode, std::forward_iterator_tag,
624  std::bidirectional_iterator_tag>::type;
625 
626  radix_tree_iterator() = default;
627  radix_tree_iterator(leaf_ptr leaf_, tree_ptr tree);
628  radix_tree_iterator(const radix_tree_iterator &rhs) = default;
629 
630  template <bool C = IsConst,
631  typename Enable = typename std::enable_if<C>::type>
632  radix_tree_iterator(const radix_tree_iterator<false> &rhs);
633 
634  radix_tree_iterator &
635  operator=(const radix_tree_iterator &rhs) = default;
636 
637  reference operator*() const;
638  pointer operator->() const;
639 
640  template <typename V = Value,
641  typename Enable = typename std::enable_if<
642  detail::is_inline_string<V>::value>::type>
643  void assign_val(basic_string_view<typename V::value_type,
644  typename V::traits_type>
645  rhs);
646 
647  template <typename T, typename V = Value,
648  typename Enable = typename std::enable_if<
649  !detail::is_inline_string<V>::value>::type>
650  void assign_val(T &&rhs);
651 
652  radix_tree_iterator &operator++();
653  template <bool Mt = MtMode,
654  typename Enable = typename std::enable_if<!Mt>::type>
655  radix_tree_iterator &operator--();
656 
657  radix_tree_iterator operator++(int);
658  template <bool Mt = MtMode,
659  typename Enable = typename std::enable_if<!Mt>::type>
660  radix_tree_iterator operator--(int);
661 
662  template <bool C>
663  bool operator!=(const radix_tree_iterator<C> &rhs) const;
664 
665  template <bool C>
666  bool operator==(const radix_tree_iterator<C> &rhs) const;
667 
668 private:
669  friend class radix_tree;
670 
671  leaf_ptr leaf_ = nullptr;
672  tree_ptr tree = nullptr;
673 
674  template <typename T>
675  void replace_val(T &&rhs);
676 
677  bool try_increment();
678  bool try_decrement();
679 };
680 
681 template <typename Key, typename Value, typename BytesView, bool MtMode>
682 struct radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator {
683  using difference_type = std::ptrdiff_t;
684  using value_type = atomic_pointer_type;
685  using pointer = const value_type *;
686  using reference = const value_type &;
687  using iterator_category = std::forward_iterator_tag;
688 
689  forward_iterator(pointer child, const node *node);
690 
691  forward_iterator operator++();
692  forward_iterator operator++(int);
693 
694  forward_iterator operator--();
695 
696  reference operator*() const;
697  pointer operator->() const;
698 
699  pointer get_node() const;
700 
701  bool operator!=(const forward_iterator &rhs) const;
702  bool operator==(const forward_iterator &rhs) const;
703 
704 private:
705  pointer child;
706  const node *n;
707 };
708 
717 template <typename Key, typename Value, typename BytesView, bool MtMode>
718 radix_tree<Key, Value, BytesView, MtMode>::radix_tree()
719  : root(nullptr), size_(0)
720 {
721  check_pmem();
722  check_tx_stage_work();
723 }
724 
744 template <typename Key, typename Value, typename BytesView, bool MtMode>
745 template <class InputIt>
746 radix_tree<Key, Value, BytesView, MtMode>::radix_tree(InputIt first,
747  InputIt last)
748  : root(nullptr), size_(0)
749 {
750  check_pmem();
751  check_tx_stage_work();
752 
753  for (auto it = first; it != last; it++)
754  emplace(*it);
755 }
756 
772 template <typename Key, typename Value, typename BytesView, bool MtMode>
773 radix_tree<Key, Value, BytesView, MtMode>::radix_tree(const radix_tree &m)
774  : root(nullptr), size_(0)
775 {
776  check_pmem();
777  check_tx_stage_work();
778 
779  for (auto it = m.cbegin(); it != m.cend(); it++)
780  emplace(*it);
781 }
782 
795 template <typename Key, typename Value, typename BytesView, bool MtMode>
796 radix_tree<Key, Value, BytesView, MtMode>::radix_tree(radix_tree &&m)
797 {
798  check_pmem();
799  check_tx_stage_work();
800 
801  store(root, load(m.root));
802  size_ = m.size_;
803  store(m.root, nullptr);
804  m.size_ = 0;
805 }
806 
821 template <typename Key, typename Value, typename BytesView, bool MtMode>
822 radix_tree<Key, Value, BytesView, MtMode>::radix_tree(
823  std::initializer_list<value_type> il)
824  : radix_tree(il.begin(), il.end())
825 {
826 }
827 
837 template <typename Key, typename Value, typename BytesView, bool MtMode>
838 radix_tree<Key, Value, BytesView, MtMode> &
839 radix_tree<Key, Value, BytesView, MtMode>::operator=(const radix_tree &other)
840 {
841  check_pmem();
842 
843  auto pop = pool_by_vptr(this);
844 
845  if (this != &other) {
846  flat_transaction::run(pop, [&] {
847  clear();
848 
849  store(this->root, nullptr);
850  this->size_ = 0;
851 
852  for (auto it = other.cbegin(); it != other.cend(); it++)
853  emplace(*it);
854  });
855  }
856 
857  return *this;
858 }
859 
868 template <typename Key, typename Value, typename BytesView, bool MtMode>
869 radix_tree<Key, Value, BytesView, MtMode> &
870 radix_tree<Key, Value, BytesView, MtMode>::operator=(radix_tree &&other)
871 {
872  check_pmem();
873 
874  auto pop = pool_by_vptr(this);
875 
876  if (this != &other) {
877  flat_transaction::run(pop, [&] {
878  clear();
879 
880  store(this->root, load(other.root));
881  this->size_ = other.size_;
882  store(other.root, nullptr);
883  other.size_ = 0;
884  });
885  }
886 
887  return *this;
888 }
889 
900 template <typename Key, typename Value, typename BytesView, bool MtMode>
901 radix_tree<Key, Value, BytesView, MtMode> &
902 radix_tree<Key, Value, BytesView, MtMode>::operator=(
903  std::initializer_list<value_type> ilist)
904 {
905  check_pmem();
906 
907  auto pop = pool_by_vptr(this);
908 
909  transaction::run(pop, [&] {
910  clear();
911 
912  store(this->root, nullptr);
913  this->size_ = 0;
914 
915  for (auto it = ilist.begin(); it != ilist.end(); it++)
916  emplace(*it);
917  });
918 
919  return *this;
920 }
921 
925 template <typename Key, typename Value, typename BytesView, bool MtMode>
926 radix_tree<Key, Value, BytesView, MtMode>::~radix_tree()
927 {
928  try {
929  clear();
930  for (size_t i = 0; i < EPOCHS_NUMBER; ++i)
931  clear_garbage(i);
932  } catch (...) {
933  std::terminate();
934  }
935 }
936 
942 template <typename Key, typename Value, typename BytesView, bool MtMode>
943 bool
944 radix_tree<Key, Value, BytesView, MtMode>::empty() const noexcept
945 {
946  return size_ == 0;
947 }
948 
952 template <typename Key, typename Value, typename BytesView, bool MtMode>
953 typename radix_tree<Key, Value, BytesView, MtMode>::size_type
954 radix_tree<Key, Value, BytesView, MtMode>::max_size() const noexcept
955 {
956  return std::numeric_limits<difference_type>::max();
957 }
958 
962 template <typename Key, typename Value, typename BytesView, bool MtMode>
963 uint64_t
964 radix_tree<Key, Value, BytesView, MtMode>::size() const noexcept
965 {
966  return this->size_;
967 }
968 
974 template <typename Key, typename Value, typename BytesView, bool MtMode>
975 void
976 radix_tree<Key, Value, BytesView, MtMode>::swap(radix_tree &rhs)
977 {
978  auto pop = pool_by_vptr(this);
979 
980  flat_transaction::run(pop, [&] {
981  this->size_.swap(rhs.size_);
982  this->root.swap(rhs.root);
983  });
984 }
985 
995 template <typename Key, typename Value, typename BytesView, bool MtMode>
996 template <bool Mt, typename Enable>
997 void
998 radix_tree<Key, Value, BytesView, MtMode>::garbage_collect_force()
999 {
1000  ebr_->full_sync();
1001  for (size_t i = 0; i < EPOCHS_NUMBER; ++i) {
1002  clear_garbage(i);
1003  }
1004 }
1005 
1016 template <typename Key, typename Value, typename BytesView, bool MtMode>
1017 template <bool Mt, typename Enable>
1018 void
1019 radix_tree<Key, Value, BytesView, MtMode>::garbage_collect()
1020 {
1021  ebr_->sync();
1022  clear_garbage(ebr_->gc_epoch());
1023 }
1024 
1025 template <typename Key, typename Value, typename BytesView, bool MtMode>
1026 void
1027 radix_tree<Key, Value, BytesView, MtMode>::clear_garbage(size_t n)
1028 {
1029  assert(n >= 0 && n < EPOCHS_NUMBER);
1030 
1031  auto pop = pool_by_vptr(this);
1032 
1033  flat_transaction::run(pop, [&] {
1034  for (auto &e : garbages[n]) {
1035  if (is_leaf(e))
1036  delete_persistent<radix_tree::leaf>(
1037  persistent_ptr<radix_tree::leaf>(
1038  get_leaf(e)));
1039  else
1040  delete_persistent<radix_tree::node>(
1041  persistent_ptr<radix_tree::node>(
1042  get_node(e)));
1043  }
1044 
1045  garbages[n].clear();
1046  });
1047 }
1048 
1049 template <typename Key, typename Value, typename BytesView, bool MtMode>
1050 typename radix_tree<Key, Value, BytesView, MtMode>::pointer_type
1051 radix_tree<Key, Value, BytesView, MtMode>::load(
1052  const std::atomic<detail::tagged_ptr<leaf, node>> &ptr)
1053 {
1054  return ptr.load_acquire();
1055 }
1056 
1057 template <typename Key, typename Value, typename BytesView, bool MtMode>
1058 typename radix_tree<Key, Value, BytesView, MtMode>::pointer_type
1059 radix_tree<Key, Value, BytesView, MtMode>::load(const pointer_type &ptr)
1060 {
1061  return ptr;
1062 }
1063 
1064 template <typename Key, typename Value, typename BytesView, bool MtMode>
1065 void
1066 radix_tree<Key, Value, BytesView, MtMode>::store(
1067  std::atomic<detail::tagged_ptr<leaf, node>> &ptr, pointer_type desired)
1068 {
1069  ptr.store_with_snapshot_release(desired);
1070 }
1071 
1072 template <typename Key, typename Value, typename BytesView, bool MtMode>
1073 void
1074 radix_tree<Key, Value, BytesView, MtMode>::store(pointer_type &ptr,
1075  pointer_type desired)
1076 {
1077  ptr = desired;
1078 }
1079 
1088 template <typename Key, typename Value, typename BytesView, bool MtMode>
1089 template <bool Mt, typename Enable>
1090 void
1091 radix_tree<Key, Value, BytesView, MtMode>::runtime_initialize_mt(ebr *e)
1092 {
1093 #if LIBPMEMOBJ_CPP_VG_PMEMCHECK_ENABLED
1094  VALGRIND_PMC_REMOVE_PMEM_MAPPING(&ebr_, sizeof(ebr *));
1095 #endif
1096  ebr_ = e;
1097 }
1098 
1103 template <typename Key, typename Value, typename BytesView, bool MtMode>
1104 template <bool Mt, typename Enable>
1105 void
1106 radix_tree<Key, Value, BytesView, MtMode>::runtime_finalize_mt()
1107 {
1108  if (ebr_) {
1109  delete ebr_;
1110  }
1111  ebr_ = nullptr;
1112 }
1113 
1122 template <typename Key, typename Value, typename BytesView, bool MtMode>
1123 template <bool Mt, typename Enable>
1124 typename radix_tree<Key, Value, BytesView, MtMode>::worker_type
1125 radix_tree<Key, Value, BytesView, MtMode>::register_worker()
1126 {
1127  assert(ebr_);
1128 
1129  return ebr_->register_worker();
1130 }
1131 
1132 /*
1133  * Returns reference to n->parent (handles both internal and leaf nodes).
1134  */
1135 template <typename Key, typename Value, typename BytesView, bool MtMode>
1136 typename radix_tree<Key, Value, BytesView, MtMode>::atomic_pointer_type &
1137 radix_tree<Key, Value, BytesView, MtMode>::parent_ref(pointer_type n)
1138 {
1139  if (is_leaf(n))
1140  return get_leaf(n)->parent;
1141 
1142  return n->parent;
1143 }
1144 
1145 /*
1146  * Find a leftmost leaf in a subtree of @param n.
1147  *
1148  * @param min_depth specifies minimum depth of the leaf. If the
1149  * tree is shorter than min_depth, a bottom leaf is returned.
1150  *
1151  * Can return nullptr if there is a conflicting, concurrent operation.
1152  */
1153 template <typename Key, typename Value, typename BytesView, bool MtMode>
1154 typename radix_tree<Key, Value, BytesView, MtMode>::leaf *
1155 radix_tree<Key, Value, BytesView, MtMode>::any_leftmost_leaf(
1156  typename radix_tree<Key, Value, BytesView, MtMode>::pointer_type n,
1157  size_type min_depth) const
1158 {
1159  assert(n);
1160 
1161  while (n && !is_leaf(n)) {
1162  auto ne = load(n->embedded_entry);
1163  if (ne && n->byte >= min_depth)
1164  return get_leaf(ne);
1165 
1166  pointer_type nn = nullptr;
1167  for (size_t i = 0; i < SLNODES; i++) {
1168  nn = load(n->child[i]);
1169  if (nn) {
1170  break;
1171  }
1172  }
1173 
1174  n = nn;
1175  }
1176 
1177  return n ? get_leaf(n) : nullptr;
1178 }
1179 
1180 /*
1181  * Descends to the leaf that shares a common prefix with the @param key.
1182  * Returns a pair consisting of a pointer to above mentioned leaf and
1183  * object of type `path_type` which represents path to a divergence point.
1184  *
1185  * @param root_snap is a pointer to the root node (we pass it here because
1186  * loading it within this function might cause inconsistency if outer code
1187  * sees a different root.
1188  *
1189  * Can return nullptr if there is a conflicting, concurrent operation.
1190  */
1191 template <typename Key, typename Value, typename BytesView, bool MtMode>
1192 template <typename K>
1193 std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::leaf *,
1194  typename radix_tree<Key, Value, BytesView, MtMode>::path_type>
1195 radix_tree<Key, Value, BytesView, MtMode>::descend(pointer_type root_snap,
1196  const K &key) const
1197 {
1198  assert(root_snap);
1199 
1200  auto slot = &this->root;
1201  auto n = root_snap;
1202  decltype(n) prev = nullptr;
1203 
1204  path_type path;
1205  path.reserve(PATH_INIT_CAP);
1206  path.push_back(node_desc{slot, n, prev});
1207 
1208  while (n && !is_leaf(n) && n->byte < key.size()) {
1209  auto prev = n;
1210  slot = &n->child[slice_index(key[n->byte], n->bit)];
1211  auto nn = load(*slot);
1212 
1213  if (nn) {
1214  path.push_back(node_desc{slot, nn, prev});
1215  n = nn;
1216  } else {
1217  path.push_back(node_desc{slot, nullptr, prev});
1218  n = any_leftmost_leaf(n, key.size());
1219  break;
1220  }
1221  }
1222 
1223  if (!n)
1224  return {nullptr, std::move(path)};
1225 
1226  /* This can happen when key is a prefix of some leaf or when the node at
1227  * which the keys diverge isn't a leaf */
1228  if (!is_leaf(n)) {
1229  n = any_leftmost_leaf(n, key.size());
1230  }
1231 
1232  if (n) {
1233  return std::pair<leaf *, path_type>{get_leaf(n),
1234  std::move(path)};
1235  } else {
1236  return std::pair<leaf *, path_type>{nullptr, std::move(path)};
1237  }
1238 }
1239 
1240 template <typename Key, typename Value, typename BytesView, bool MtMode>
1241 template <typename K>
1242 BytesView
1243 radix_tree<Key, Value, BytesView, MtMode>::bytes_view(const K &key)
1244 {
1245  /* bytes_view accepts const pointer instead of reference to make sure
1246  * there is no implicit conversion to a temporary type (and hence
1247  * dangling references). */
1248  return BytesView(&key);
1249 }
1250 
1251 template <typename Key, typename Value, typename BytesView, bool MtMode>
1252 string_view
1253 radix_tree<Key, Value, BytesView, MtMode>::bytes_view(string_view key)
1254 {
1255  return key;
1256 }
1257 
1258 /*
1259  * Checks for key equality.
1260  */
1261 template <typename Key, typename Value, typename BytesView, bool MtMode>
1262 template <typename K1, typename K2>
1263 bool
1264 radix_tree<Key, Value, BytesView, MtMode>::keys_equal(const K1 &k1,
1265  const K2 &k2)
1266 {
1267  return k1.size() == k2.size() && compare(k1, k2) == 0;
1268 }
1269 
1270 /*
1271  * Checks for key equality.
1272  */
1273 template <typename Key, typename Value, typename BytesView, bool MtMode>
1274 template <typename K1, typename K2>
1275 int
1276 radix_tree<Key, Value, BytesView, MtMode>::compare(const K1 &k1, const K2 &k2,
1277  byten_t offset)
1278 {
1279  auto ret = prefix_diff(k1, k2, offset);
1280 
1281  if (ret != (std::min)(k1.size(), k2.size()))
1282  return (unsigned char)(k1[ret]) - (unsigned char)(k2[ret]);
1283 
1284  return k1.size() - k2.size();
1285 }
1286 
1287 /*
1288  * Returns length of common prefix of lhs and rhs.
1289  */
1290 template <typename Key, typename Value, typename BytesView, bool MtMode>
1291 template <typename K1, typename K2>
1292 typename radix_tree<Key, Value, BytesView, MtMode>::byten_t
1293 radix_tree<Key, Value, BytesView, MtMode>::prefix_diff(const K1 &lhs,
1294  const K2 &rhs,
1295  byten_t offset)
1296 {
1297  byten_t diff;
1298  for (diff = offset; diff < (std::min)(lhs.size(), rhs.size()); diff++) {
1299  if (lhs[diff] != rhs[diff])
1300  return diff;
1301  }
1302 
1303  return diff;
1304 }
1305 
1306 /*
1307  * Checks whether length of the path from root to n is equal
1308  * to key_size.
1309  */
1310 template <typename Key, typename Value, typename BytesView, bool MtMode>
1311 bool
1312 radix_tree<Key, Value, BytesView, MtMode>::path_length_equal(size_t key_size,
1313  pointer_type n)
1314 {
1315  return n->byte == key_size && n->bit == bitn_t(FIRST_NIB);
1316 }
1317 
1318 template <typename Key, typename Value, typename BytesView, bool MtMode>
1319 template <typename K1, typename K2>
1320 typename radix_tree<Key, Value, BytesView, MtMode>::bitn_t
1321 radix_tree<Key, Value, BytesView, MtMode>::bit_diff(const K1 &leaf_key,
1322  const K2 &key, byten_t diff)
1323 {
1324  auto min_key_len = (std::min)(leaf_key.size(), key.size());
1325  bitn_t sh = 8;
1326 
1327  /* If key differs from leaf_key at some point (neither is a prefix of
1328  * another) we will descend to the point of divergence. Otherwise we
1329  * will look for a node which represents the prefix. */
1330  if (diff < min_key_len) {
1331  auto at =
1332  static_cast<unsigned char>(leaf_key[diff] ^ key[diff]);
1333  sh = pmem::detail::mssb_index((uint32_t)at) & SLICE_MASK;
1334  }
1335 
1336  return sh;
1337 }
1338 
1339 /*
1340  * Follows path saved in @param path until appropriate node is found
1341  * (for which @param diff and @param sh matches with byte and bit).
1342  */
1343 template <typename Key, typename Value, typename BytesView, bool MtMode>
1344 typename radix_tree<Key, Value, BytesView, MtMode>::node_desc
1345 radix_tree<Key, Value, BytesView, MtMode>::follow_path(const path_type &path,
1346  byten_t diff,
1347  bitn_t sh) const
1348 {
1349  assert(path.size());
1350 
1351  auto idx = 0ULL;
1352  auto n = path[idx];
1353 
1354  while (n.node && !is_leaf(n.node) &&
1355  (n.node->byte < diff ||
1356  (n.node->byte == diff && n.node->bit >= sh))) {
1357 
1358  idx++;
1359  assert(idx < path.size());
1360 
1361  n = path[idx];
1362  }
1363 
1364  return n;
1365 }
1366 
1367 template <typename Key, typename Value, typename BytesView, bool MtMode>
1368 template <typename K, typename F, class... Args>
1369 std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1370 radix_tree<Key, Value, BytesView, MtMode>::internal_emplace(const K &k,
1371  F &&make_leaf)
1372 {
1373  auto key = bytes_view(k);
1374  auto pop = pool_base(pmemobj_pool_by_ptr(this));
1375 
1376  auto r = load(root);
1377  if (!r) {
1378  pointer_type leaf;
1379  flat_transaction::run(pop, [&] {
1380  leaf = make_leaf(nullptr);
1381  store(this->root, leaf);
1382  });
1383  return {iterator(get_leaf(leaf), this), true};
1384  }
1385 
1386  /*
1387  * Need to descend the tree twice. First to find a leaf that
1388  * represents a subtree that shares a common prefix with the key.
1389  * This is needed to find out the actual labels between nodes (they
1390  * are not known due to a possible path compression). Second time to
1391  * find the place for the new element.
1392  */
1393  auto ret = descend(r, key);
1394  auto leaf = ret.first;
1395  auto path = ret.second;
1396 
1397  assert(leaf);
1398 
1399  auto leaf_key = bytes_view(leaf->key());
1400  auto diff = prefix_diff(key, leaf_key);
1401  auto sh = bit_diff(leaf_key, key, diff);
1402 
1403  /* Key exists. */
1404  if (diff == key.size() && leaf_key.size() == key.size())
1405  return {iterator(leaf, this), false};
1406 
1407  /* Descend the tree again by following the path. */
1408  auto node_d = follow_path(path, diff, sh);
1409  auto slot = const_cast<atomic_pointer_type *>(node_d.slot);
1410  auto prev = node_d.prev;
1411  auto n = node_d.node;
1412 
1413  /*
1414  * If the divergence point is at same nib as an existing node, and
1415  * the subtree there is empty, just place our leaf there and we're
1416  * done. Obviously this can't happen if SLICE == 1.
1417  */
1418  if (!n) {
1419  assert(diff < (std::min)(leaf_key.size(), key.size()));
1420 
1421  flat_transaction::run(pop,
1422  [&] { store(*slot, make_leaf(prev)); });
1423  return {iterator(get_leaf(load(*slot)), this), true};
1424  }
1425 
1426  /* New key is a prefix of the leaf key or they are equal. We need to add
1427  * leaf ptr to internal node. */
1428  if (diff == key.size()) {
1429  if (!is_leaf(n) && path_length_equal(key.size(), n)) {
1430  assert(!load(n->embedded_entry));
1431 
1432  flat_transaction::run(pop, [&] {
1433  store(n->embedded_entry, make_leaf(n));
1434  });
1435 
1436  return {iterator(get_leaf(load(n->embedded_entry)),
1437  this),
1438  true};
1439  }
1440 
1441  /* Path length from root to n is longer than key.size().
1442  * We have to allocate new internal node above n. */
1443  pointer_type node;
1444  flat_transaction::run(pop, [&] {
1445  node = make_persistent<radix_tree::node>(
1446  load(parent_ref(n)), diff, bitn_t(FIRST_NIB));
1447  store(node->embedded_entry, make_leaf(node));
1448  store(node->child[slice_index(leaf_key[diff],
1449  bitn_t(FIRST_NIB))],
1450  n);
1451 
1452  store(parent_ref(n), node);
1453  store(*slot, node);
1454  });
1455 
1456  return {iterator(get_leaf(load(node->embedded_entry)), this),
1457  true};
1458  }
1459 
1460  if (diff == leaf_key.size()) {
1461  /* Leaf key is a prefix of the new key. We need to convert leaf
1462  * to a node. */
1463  pointer_type node;
1464  flat_transaction::run(pop, [&] {
1465  /* We have to add new node at the edge from parent to n
1466  */
1467  node = make_persistent<radix_tree::node>(
1468  load(parent_ref(n)), diff, bitn_t(FIRST_NIB));
1469  store(node->embedded_entry, n);
1470  store(node->child[slice_index(key[diff],
1471  bitn_t(FIRST_NIB))],
1472  make_leaf(node));
1473 
1474  store(parent_ref(n), node);
1475  store(*slot, node);
1476  });
1477 
1478  return {iterator(get_leaf(load(node->child[slice_index(
1479  key[diff], bitn_t(FIRST_NIB))])),
1480  this),
1481  true};
1482  }
1483 
1484  /* There is already a subtree at the divergence point
1485  * (slice_index(key[diff], sh)). This means that a tree is vertically
1486  * compressed and we have to "break" this compression and add a new
1487  * node. */
1488  pointer_type node;
1489  flat_transaction::run(pop, [&] {
1490  node = make_persistent<radix_tree::node>(load(parent_ref(n)),
1491  diff, sh);
1492  store(node->child[slice_index(leaf_key[diff], sh)], n);
1493  store(node->child[slice_index(key[diff], sh)], make_leaf(node));
1494 
1495  store(parent_ref(n), node);
1496  store(*slot, node);
1497  });
1498 
1499  return {iterator(
1500  get_leaf(load(node->child[slice_index(key[diff], sh)])),
1501  this),
1502  true};
1503 }
1504 
1533 template <typename Key, typename Value, typename BytesView, bool MtMode>
1534 template <class... Args>
1535 std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1536 radix_tree<Key, Value, BytesView, MtMode>::try_emplace(const key_type &k,
1537  Args &&... args)
1538 {
1539  return internal_emplace(k, [&](pointer_type parent) {
1540  size_++;
1541  return leaf::make_key_args(parent, k,
1542  std::forward<Args>(args)...);
1543  });
1544 }
1545 
1572 template <typename Key, typename Value, typename BytesView, bool MtMode>
1573 template <class... Args>
1574 std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1575 radix_tree<Key, Value, BytesView, MtMode>::emplace(Args &&... args)
1576 {
1577  auto pop = pool_base(pmemobj_pool_by_ptr(this));
1578  std::pair<iterator, bool> ret;
1579 
1580  flat_transaction::run(pop, [&] {
1581  auto leaf_ = leaf::make(nullptr, std::forward<Args>(args)...);
1582  auto make_leaf = [&](pointer_type parent) {
1583  store(leaf_->parent, parent);
1584  size_++;
1585  return leaf_;
1586  };
1587 
1588  ret = internal_emplace(leaf_->key(), make_leaf);
1589 
1590  if (!ret.second)
1591  delete_persistent<leaf>(leaf_);
1592  });
1593 
1594  return ret;
1595 }
1596 
1612 template <typename Key, typename Value, typename BytesView, bool MtMode>
1613 std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1614 radix_tree<Key, Value, BytesView, MtMode>::insert(const value_type &v)
1615 {
1616  return try_emplace(v.first, v.second);
1617 }
1618 
1634 template <typename Key, typename Value, typename BytesView, bool MtMode>
1635 std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1636 radix_tree<Key, Value, BytesView, MtMode>::insert(value_type &&v)
1637 {
1638  return try_emplace(std::move(v.first), std::move(v.second));
1639 }
1640 
1660 template <typename Key, typename Value, typename BytesView, bool MtMode>
1661 template <typename P, typename>
1662 std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1663 radix_tree<Key, Value, BytesView, MtMode>::insert(P &&p)
1664 {
1665  return emplace(std::forward<P>(p));
1666 }
1667 
1679 template <typename Key, typename Value, typename BytesView, bool MtMode>
1680 template <typename InputIterator>
1681 void
1682 radix_tree<Key, Value, BytesView, MtMode>::insert(InputIterator first,
1683  InputIterator last)
1684 {
1685  for (auto it = first; it != last; it++)
1686  try_emplace((*it).first, (*it).second);
1687 }
1688 
1699 template <typename Key, typename Value, typename BytesView, bool MtMode>
1700 void
1701 radix_tree<Key, Value, BytesView, MtMode>::insert(
1702  std::initializer_list<value_type> il)
1703 {
1704  insert(il.begin(), il.end());
1705 }
1706 
1731 template <typename Key, typename Value, typename BytesView, bool MtMode>
1732 template <class... Args>
1733 std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1734 radix_tree<Key, Value, BytesView, MtMode>::try_emplace(key_type &&k,
1735  Args &&... args)
1736 {
1737  return internal_emplace(k, [&](pointer_type parent) {
1738  size_++;
1739  return leaf::make_key_args(parent, std::move(k),
1740  std::forward<Args>(args)...);
1741  });
1742 }
1743 
1772 template <typename Key, typename Value, typename BytesView, bool MtMode>
1773 template <typename K, typename BV, class... Args>
1774 auto
1775 radix_tree<Key, Value, BytesView, MtMode>::try_emplace(K &&k, Args &&... args)
1776  -> typename std::enable_if<
1777  detail::has_is_transparent<BV>::value &&
1778  !std::is_same<typename std::remove_const<
1779  typename std::remove_reference<
1780  K>::type>::type,
1781  key_type>::value,
1782  std::pair<typename radix_tree<Key, Value, BytesView,
1783  MtMode>::iterator,
1784  bool>>::type
1785 
1786 {
1787  return internal_emplace(k, [&](pointer_type parent) {
1788  size_++;
1789  return leaf::make_key_args(parent, std::forward<K>(k),
1790  std::forward<Args>(args)...);
1791  });
1792 }
1793 
1812 template <typename Key, typename Value, typename BytesView, bool MtMode>
1813 template <typename M>
1814 std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1815 radix_tree<Key, Value, BytesView, MtMode>::insert_or_assign(const key_type &k,
1816  M &&obj)
1817 {
1818  auto ret = try_emplace(k, std::forward<M>(obj));
1819  if (!ret.second)
1820  ret.first.assign_val(std::forward<M>(obj));
1821  return ret;
1822 }
1823 
1842 template <typename Key, typename Value, typename BytesView, bool MtMode>
1843 template <typename M>
1844 std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1845 radix_tree<Key, Value, BytesView, MtMode>::insert_or_assign(key_type &&k,
1846  M &&obj)
1847 {
1848  auto ret = try_emplace(std::move(k), std::forward<M>(obj));
1849  if (!ret.second)
1850  ret.first.assign_val(std::forward<M>(obj));
1851  return ret;
1852 }
1853 
1875 template <typename Key, typename Value, typename BytesView, bool MtMode>
1876 template <typename M, typename K, typename>
1877 std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1878 radix_tree<Key, Value, BytesView, MtMode>::insert_or_assign(K &&k, M &&obj)
1879 {
1880  auto ret = try_emplace(std::forward<K>(k), std::forward<M>(obj));
1881  if (!ret.second)
1882  ret.first.assign_val(std::forward<M>(obj));
1883  return ret;
1884 }
1885 
1895 template <typename Key, typename Value, typename BytesView, bool MtMode>
1896 typename radix_tree<Key, Value, BytesView, MtMode>::size_type
1897 radix_tree<Key, Value, BytesView, MtMode>::count(const key_type &k) const
1898 {
1899  return internal_find(k) != nullptr ? 1 : 0;
1900 }
1901 
1914 template <typename Key, typename Value, typename BytesView, bool MtMode>
1915 template <typename K, typename>
1916 typename radix_tree<Key, Value, BytesView, MtMode>::size_type
1917 radix_tree<Key, Value, BytesView, MtMode>::count(const K &k) const
1918 {
1919  return internal_find(k) != nullptr ? 1 : 0;
1920 }
1921 
1930 template <typename Key, typename Value, typename BytesView, bool MtMode>
1931 typename radix_tree<Key, Value, BytesView, MtMode>::iterator
1932 radix_tree<Key, Value, BytesView, MtMode>::find(const key_type &k)
1933 {
1934  return iterator(internal_find(k), this);
1935 }
1936 
1945 template <typename Key, typename Value, typename BytesView, bool MtMode>
1946 typename radix_tree<Key, Value, BytesView, MtMode>::const_iterator
1947 radix_tree<Key, Value, BytesView, MtMode>::find(const key_type &k) const
1948 {
1949  return const_iterator(internal_find(k), this);
1950 }
1951 
1963 template <typename Key, typename Value, typename BytesView, bool MtMode>
1964 template <typename K, typename>
1965 typename radix_tree<Key, Value, BytesView, MtMode>::iterator
1966 radix_tree<Key, Value, BytesView, MtMode>::find(const K &k)
1967 {
1968  return iterator(internal_find(k), this);
1969 }
1970 
1982 template <typename Key, typename Value, typename BytesView, bool MtMode>
1983 template <typename K, typename>
1984 typename radix_tree<Key, Value, BytesView, MtMode>::const_iterator
1985 radix_tree<Key, Value, BytesView, MtMode>::find(const K &k) const
1986 {
1987  return const_iterator(internal_find(k), this);
1988 }
1989 
1990 template <typename Key, typename Value, typename BytesView, bool MtMode>
1991 template <typename K>
1992 typename radix_tree<Key, Value, BytesView, MtMode>::leaf *
1993 radix_tree<Key, Value, BytesView, MtMode>::internal_find(const K &k) const
1994 {
1995  auto key = bytes_view(k);
1996 
1997  auto n = load(root);
1998  while (n && !is_leaf(n)) {
1999  if (path_length_equal(key.size(), n))
2000  n = load(n->embedded_entry);
2001  else if (n->byte >= key.size())
2002  return nullptr;
2003  else
2004  n = load(n->child[slice_index(key[n->byte], n->bit)]);
2005  }
2006 
2007  if (!n)
2008  return nullptr;
2009 
2010  if (!keys_equal(key, bytes_view(get_leaf(n)->key())))
2011  return nullptr;
2012 
2013  return get_leaf(n);
2014 }
2015 
2023 template <typename Key, typename Value, typename BytesView, bool MtMode>
2024 void
2025 radix_tree<Key, Value, BytesView, MtMode>::clear()
2026 {
2027  if (size() != 0)
2028  erase(begin(), end());
2029 }
2030 
2046 template <typename Key, typename Value, typename BytesView, bool MtMode>
2047 typename radix_tree<Key, Value, BytesView, MtMode>::iterator
2048 radix_tree<Key, Value, BytesView, MtMode>::erase(const_iterator pos)
2049 {
2050  auto pop = pool_base(pmemobj_pool_by_ptr(this));
2051 
2052  flat_transaction::run(pop, [&] {
2053  auto *leaf = pos.leaf_;
2054  auto parent = load(leaf->parent);
2055 
2056  /* there are more elements in the container */
2057  if (parent)
2058  ++pos;
2059 
2060  free(persistent_ptr<radix_tree::leaf>(leaf));
2061 
2062  size_--;
2063 
2064  /* was root */
2065  if (!parent) {
2066  store(this->root, nullptr);
2067  pos = begin();
2068  return;
2069  }
2070 
2071  /* It's safe to cast because we're inside non-const method. */
2072  store(const_cast<atomic_pointer_type &>(
2073  *parent->find_child(leaf)),
2074  nullptr);
2075 
2076  /* Compress the tree vertically. */
2077  auto n = parent;
2078  parent = load(n->parent);
2079  pointer_type only_child = nullptr;
2080  for (size_t i = 0; i < SLNODES; i++) {
2081  if (load(n->child[i])) {
2082  if (only_child) {
2083  /* more than one child */
2084  return;
2085  }
2086  only_child = load(n->child[i]);
2087  }
2088  }
2089 
2090  if (only_child && load(n->embedded_entry)) {
2091  /* There are actually 2 "children" so we can't compress.
2092  */
2093  return;
2094  } else if (load(n->embedded_entry)) {
2095  only_child = load(n->embedded_entry);
2096  }
2097 
2098  assert(only_child);
2099  store(parent_ref(only_child), load(n->parent));
2100 
2101  auto *child_slot = parent ? const_cast<atomic_pointer_type *>(
2102  &*parent->find_child(n))
2103  : &root;
2104  store(*child_slot, only_child);
2105 
2106  free(persistent_ptr<radix_tree::node>(get_node(n)));
2107  });
2108 
2109  return iterator(const_cast<typename iterator::leaf_ptr>(pos.leaf_),
2110  this);
2111 }
2112 
2126 template <typename Key, typename Value, typename BytesView, bool MtMode>
2127 typename radix_tree<Key, Value, BytesView, MtMode>::iterator
2128 radix_tree<Key, Value, BytesView, MtMode>::erase(const_iterator first,
2129  const_iterator last)
2130 {
2131  auto pop = pool_base(pmemobj_pool_by_ptr(this));
2132 
2133  flat_transaction::run(pop, [&] {
2134  while (first != last)
2135  first = erase(first);
2136  });
2137 
2138  return iterator(const_cast<typename iterator::leaf_ptr>(first.leaf_),
2139  this);
2140 }
2141 
2154 template <typename Key, typename Value, typename BytesView, bool MtMode>
2155 typename radix_tree<Key, Value, BytesView, MtMode>::size_type
2156 radix_tree<Key, Value, BytesView, MtMode>::erase(const key_type &k)
2157 {
2158  auto it = const_iterator(internal_find(k), this);
2159 
2160  if (it == end())
2161  return 0;
2162 
2163  erase(it);
2164 
2165  return 1;
2166 }
2167 
2182 template <typename Key, typename Value, typename BytesView, bool MtMode>
2183 template <typename K, typename>
2184 typename radix_tree<Key, Value, BytesView, MtMode>::size_type
2185 radix_tree<Key, Value, BytesView, MtMode>::erase(const K &k)
2186 {
2187  auto it = const_iterator(internal_find(k), this);
2188 
2189  if (it == end())
2190  return 0;
2191 
2192  erase(it);
2193 
2194  return 1;
2195 }
2196 
2201 template <typename Key, typename Value, typename BytesView, bool MtMode>
2202 template <typename T>
2203 void
2204 radix_tree<Key, Value, BytesView, MtMode>::free(persistent_ptr<T> ptr)
2205 {
2206  if (MtMode && ebr_ != nullptr)
2207  garbages[ebr_->staging_epoch()].emplace_back(ptr);
2208  else
2209  delete_persistent<T>(ptr);
2210 }
2211 
2216 template <typename Key, typename Value, typename BytesView, bool MtMode>
2217 template <bool Lower, typename K>
2218 bool
2219 radix_tree<Key, Value, BytesView, MtMode>::validate_bound(const_iterator it,
2220  const K &key) const
2221 {
2222  if (it == cend())
2223  return true;
2224 
2225  if (Lower)
2226  return (compare(bytes_view(it->key()), bytes_view(key)) >= 0);
2227 
2228  return (compare(bytes_view(it->key()), bytes_view(key)) > 0);
2229 }
2230 
2234 template <typename Key, typename Value, typename BytesView, bool MtMode>
2235 template <bool Mt>
2236 typename std::enable_if<Mt, bool>::type
2237 radix_tree<Key, Value, BytesView, MtMode>::validate_path(
2238  const path_type &path) const
2239 {
2240  for (auto i = 0ULL; i < path.size(); i++) {
2241  if (path[i].node != load(*path[i].slot))
2242  return false;
2243 
2244  if (path[i].node &&
2245  load(parent_ref(path[i].node)) != path[i].prev)
2246  return false;
2247  }
2248 
2249  return true;
2250 }
2251 
2252 template <typename Key, typename Value, typename BytesView, bool MtMode>
2253 template <bool Mt>
2254 typename std::enable_if<!Mt, bool>::type
2255 radix_tree<Key, Value, BytesView, MtMode>::validate_path(
2256  const path_type &path) const
2257 {
2258  return true;
2259 }
2260 
2261 template <typename Key, typename Value, typename BytesView, bool MtMode>
2262 template <bool Lower, typename K>
2263 typename radix_tree<Key, Value, BytesView, MtMode>::const_iterator
2264 radix_tree<Key, Value, BytesView, MtMode>::internal_bound(const K &k) const
2265 {
2266  auto key = bytes_view(k);
2267  auto pop = pool_base(pmemobj_pool_by_ptr(this));
2268 
2269  path_type path;
2270  const_iterator result;
2271 
2272  while (true) {
2273  auto r = load(root);
2274 
2275  if (!r)
2276  return end();
2277 
2278  /*
2279  * Need to descend the tree twice. First to find a leaf that
2280  * represents a subtree that shares a common prefix with the
2281  * key. This is needed to find out the actual labels between
2282  * nodes (they are not known due to a possible path
2283  * compression). Second time to get the actual element.
2284  */
2285  auto ret = descend(r, key);
2286  auto leaf = ret.first;
2287  path = ret.second;
2288 
2289  if (!leaf)
2290  continue;
2291 
2292  auto leaf_key = bytes_view(leaf->key());
2293  auto diff = prefix_diff(key, leaf_key);
2294  auto sh = bit_diff(leaf_key, key, diff);
2295 
2296  /* Key exists. */
2297  if (diff == key.size() && leaf_key.size() == key.size()) {
2298  result = const_iterator(leaf, this);
2299 
2300  /* For lower_bound, result is looked-for element. */
2301  if (Lower)
2302  break;
2303 
2304  /* For upper_bound, we need to find larger element. */
2305  if (result.try_increment())
2306  break;
2307 
2308  continue;
2309  }
2310 
2311  /* Descend the tree again by following the path. */
2312  auto node_d = follow_path(path, diff, sh);
2313 
2314  auto n = node_d.node;
2315  auto slot = node_d.slot;
2316  auto prev = node_d.prev;
2317 
2318  if (!n) {
2319  /*
2320  * n would point to element with key which we are
2321  * looking for (if it existed). All elements on the left
2322  * are smaller and all element on the right are bigger.
2323  */
2324  assert(prev && !is_leaf(prev));
2325 
2326  auto target_leaf = next_leaf<node::direction::Forward>(
2327  prev->template make_iterator<
2328  node::direction::Forward>(slot),
2329  prev);
2330 
2331  if (!target_leaf.first)
2332  continue;
2333 
2334  result = const_iterator(target_leaf.second, this);
2335  } else if (diff == key.size()) {
2336  /* The looked-for key is a prefix of the leaf key. The
2337  * target node must be the smallest leaf within *slot's
2338  * subtree. Key represented by a path from root to n is
2339  * larger than the looked-for key. Additionally keys
2340  * under right siblings of *slot are > key and keys
2341  * under left siblings are < key. */
2342  auto target_leaf =
2343  find_leaf<node::direction::Forward>(n);
2344 
2345  if (!target_leaf)
2346  continue;
2347 
2348  result = const_iterator(target_leaf, this);
2349  } else if (diff == leaf_key.size()) {
2350  assert(n == leaf);
2351 
2352  if (!prev) {
2353  /* There is only one element in the tree and
2354  * it's smaller. */
2355  result = cend();
2356  } else {
2357  /* Leaf's key is a prefix of the looked-for key.
2358  * Leaf's key is the biggest key less than the
2359  * looked-for key. The target node must be the
2360  * next leaf. Note that we cannot just call
2361  * const_iterator(leaf, this).try_increment()
2362  * because some other element with key larger
2363  * than leaf and smaller than k could be
2364  * inserted concurrently. */
2365  auto target_leaf = next_leaf<
2366  node::direction::Forward>(
2367  prev->template make_iterator<
2368  node::direction::Forward>(slot),
2369  prev);
2370 
2371  if (!target_leaf.first)
2372  continue;
2373 
2374  result = const_iterator(target_leaf.second,
2375  this);
2376  }
2377  } else {
2378  assert(diff < leaf_key.size() && diff < key.size());
2379 
2380  /* *slot is the point of divergence. It means the tree
2381  * is compressed.
2382  *
2383  * Example for key AXXB or AZZB
2384  * ROOT
2385  * / \
2386  * A B
2387  * / \
2388  * *slot ...
2389  * / \
2390  * YYA YYC
2391  * / \
2392  * ... ...
2393  *
2394  * We need to compare the first bytes of key and
2395  * leaf_key to decide where to continue our search (for
2396  * AXXB we would compare X with Y).
2397  */
2398 
2399  /* If next byte in key is less than in leaf_key it means
2400  * that the target node must be within *slot's subtree.
2401  * The left siblings of *slot are all less than the
2402  * looked-for key (this is the case for AXXB from the
2403  * example above). */
2404  if (static_cast<unsigned char>(key[diff]) <
2405  static_cast<unsigned char>(leaf_key[diff])) {
2406  auto target_leaf =
2407  find_leaf<node::direction::Forward>(n);
2408 
2409  if (!target_leaf)
2410  continue;
2411 
2412  result = const_iterator(target_leaf, this);
2413  } else if (slot == &root) {
2414  result = const_iterator(nullptr, this);
2415  } else {
2416  assert(prev);
2417  assert(static_cast<unsigned char>(key[diff]) >
2418  static_cast<unsigned char>(
2419  leaf_key[diff]));
2420 
2421  /* Since next byte in key is greater
2422  * than in leaf_key, the target node
2423  * must be within subtree of a right
2424  * sibling of *slot. All leaves in the
2425  * subtree under *slot are smaller than
2426  * key (this is the case of AZZB). This
2427  * is because the tree is compressed so
2428  * all nodes under *slot share common prefix
2429  * ("YY" in the example above) - leaf_key[diff]
2430  * is the same for all keys under *slot. */
2431  auto target_leaf = next_leaf<
2432  node::direction::Forward>(
2433  prev->template make_iterator<
2434  node::direction::Forward>(slot),
2435  prev);
2436 
2437  if (!target_leaf.first)
2438  continue;
2439 
2440  result = const_iterator(target_leaf.second,
2441  this);
2442  }
2443  }
2444 
2445  /* If some node on the path was modified, the calculated result
2446  * might not be correct. */
2447  if (validate_path(path))
2448  break;
2449  }
2450 
2451  assert(validate_bound<Lower>(result, k));
2452 
2453  return result;
2454 }
2455 
2466 template <typename Key, typename Value, typename BytesView, bool MtMode>
2467 typename radix_tree<Key, Value, BytesView, MtMode>::const_iterator
2468 radix_tree<Key, Value, BytesView, MtMode>::lower_bound(const key_type &k) const
2469 {
2470  return internal_bound<true>(k);
2471 }
2472 
2483 template <typename Key, typename Value, typename BytesView, bool MtMode>
2484 typename radix_tree<Key, Value, BytesView, MtMode>::iterator
2485 radix_tree<Key, Value, BytesView, MtMode>::lower_bound(const key_type &k)
2486 {
2487  auto it = const_cast<const radix_tree *>(this)->lower_bound(k);
2488  return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2489  this);
2490 }
2491 
2505 template <typename Key, typename Value, typename BytesView, bool MtMode>
2506 template <typename K, typename>
2507 typename radix_tree<Key, Value, BytesView, MtMode>::iterator
2508 radix_tree<Key, Value, BytesView, MtMode>::lower_bound(const K &k)
2509 {
2510  auto it = const_cast<const radix_tree *>(this)->lower_bound(k);
2511  return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2512  this);
2513 }
2514 
2528 template <typename Key, typename Value, typename BytesView, bool MtMode>
2529 template <typename K, typename>
2530 typename radix_tree<Key, Value, BytesView, MtMode>::const_iterator
2531 radix_tree<Key, Value, BytesView, MtMode>::lower_bound(const K &k) const
2532 {
2533  return internal_bound<true>(k);
2534 }
2535 
2546 template <typename Key, typename Value, typename BytesView, bool MtMode>
2547 typename radix_tree<Key, Value, BytesView, MtMode>::const_iterator
2548 radix_tree<Key, Value, BytesView, MtMode>::upper_bound(const key_type &k) const
2549 {
2550  return internal_bound<false>(k);
2551 }
2552 
2563 template <typename Key, typename Value, typename BytesView, bool MtMode>
2564 typename radix_tree<Key, Value, BytesView, MtMode>::iterator
2565 radix_tree<Key, Value, BytesView, MtMode>::upper_bound(const key_type &k)
2566 {
2567  auto it = const_cast<const radix_tree *>(this)->upper_bound(k);
2568  return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2569  this);
2570 }
2571 
2585 template <typename Key, typename Value, typename BytesView, bool MtMode>
2586 template <typename K, typename>
2587 typename radix_tree<Key, Value, BytesView, MtMode>::iterator
2588 radix_tree<Key, Value, BytesView, MtMode>::upper_bound(const K &k)
2589 {
2590  auto it = const_cast<const radix_tree *>(this)->upper_bound(k);
2591  return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2592  this);
2593 }
2594 
2608 template <typename Key, typename Value, typename BytesView, bool MtMode>
2609 template <typename K, typename>
2610 typename radix_tree<Key, Value, BytesView, MtMode>::const_iterator
2611 radix_tree<Key, Value, BytesView, MtMode>::upper_bound(const K &k) const
2612 {
2613  return internal_bound<false>(k);
2614 }
2615 
2622 template <typename Key, typename Value, typename BytesView, bool MtMode>
2623 typename radix_tree<Key, Value, BytesView, MtMode>::iterator
2624 radix_tree<Key, Value, BytesView, MtMode>::begin()
2625 {
2626  auto const_begin = const_cast<const radix_tree *>(this)->begin();
2627  return iterator(
2628  const_cast<typename iterator::leaf_ptr>(const_begin.leaf_),
2629  this);
2630 }
2631 
2639 template <typename Key, typename Value, typename BytesView, bool MtMode>
2640 typename radix_tree<Key, Value, BytesView, MtMode>::iterator
2641 radix_tree<Key, Value, BytesView, MtMode>::end()
2642 {
2643  auto const_end = const_cast<const radix_tree *>(this)->end();
2644  return iterator(
2645  const_cast<typename iterator::leaf_ptr>(const_end.leaf_), this);
2646 }
2647 
2654 template <typename Key, typename Value, typename BytesView, bool MtMode>
2655 typename radix_tree<Key, Value, BytesView, MtMode>::const_iterator
2656 radix_tree<Key, Value, BytesView, MtMode>::cbegin() const
2657 {
2658  while (true) {
2659  auto root_ptr = load(root);
2660  if (!root_ptr)
2661  return const_iterator(nullptr, this);
2662 
2663  auto leaf = find_leaf<radix_tree::node::direction::Forward>(
2664  root_ptr);
2665  if (leaf) {
2666  return const_iterator(leaf, this);
2667  }
2668  }
2669 }
2670 
2678 template <typename Key, typename Value, typename BytesView, bool MtMode>
2679 typename radix_tree<Key, Value, BytesView, MtMode>::const_iterator
2680 radix_tree<Key, Value, BytesView, MtMode>::cend() const
2681 {
2682  return const_iterator(nullptr, this);
2683 }
2684 
2691 template <typename Key, typename Value, typename BytesView, bool MtMode>
2692 typename radix_tree<Key, Value, BytesView, MtMode>::const_iterator
2693 radix_tree<Key, Value, BytesView, MtMode>::begin() const
2694 {
2695  return cbegin();
2696 }
2697 
2705 template <typename Key, typename Value, typename BytesView, bool MtMode>
2706 typename radix_tree<Key, Value, BytesView, MtMode>::const_iterator
2707 radix_tree<Key, Value, BytesView, MtMode>::end() const
2708 {
2709  return cend();
2710 }
2711 
2719 template <typename Key, typename Value, typename BytesView, bool MtMode>
2720 typename radix_tree<Key, Value, BytesView, MtMode>::reverse_iterator
2721 radix_tree<Key, Value, BytesView, MtMode>::rbegin()
2722 {
2723  return reverse_iterator(end());
2724 }
2725 
2734 template <typename Key, typename Value, typename BytesView, bool MtMode>
2735 typename radix_tree<Key, Value, BytesView, MtMode>::reverse_iterator
2736 radix_tree<Key, Value, BytesView, MtMode>::rend()
2737 {
2738  return reverse_iterator(begin());
2739 }
2740 
2748 template <typename Key, typename Value, typename BytesView, bool MtMode>
2749 typename radix_tree<Key, Value, BytesView, MtMode>::const_reverse_iterator
2750 radix_tree<Key, Value, BytesView, MtMode>::crbegin() const
2751 {
2752  return const_reverse_iterator(cend());
2753 }
2754 
2763 template <typename Key, typename Value, typename BytesView, bool MtMode>
2764 typename radix_tree<Key, Value, BytesView, MtMode>::const_reverse_iterator
2765 radix_tree<Key, Value, BytesView, MtMode>::crend() const
2766 {
2767  return const_reverse_iterator(cbegin());
2768 }
2769 
2770 template <typename Key, typename Value, typename BytesView, bool MtMode>
2771 typename radix_tree<Key, Value, BytesView, MtMode>::const_reverse_iterator
2772 radix_tree<Key, Value, BytesView, MtMode>::rbegin() const
2773 {
2774  return const_reverse_iterator(cend());
2775 }
2776 
2777 template <typename Key, typename Value, typename BytesView, bool MtMode>
2778 typename radix_tree<Key, Value, BytesView, MtMode>::const_reverse_iterator
2779 radix_tree<Key, Value, BytesView, MtMode>::rend() const
2780 {
2781  return const_reverse_iterator(cbegin());
2782 }
2783 
2784 template <typename Key, typename Value, typename BytesView, bool MtMode>
2785 void
2786 radix_tree<Key, Value, BytesView, MtMode>::print_rec(std::ostream &os,
2787  radix_tree::pointer_type n)
2788 {
2789  if (!is_leaf(n)) {
2790  os << "\"" << get_node(n) << "\""
2791  << " [style=filled,color=\"blue\"]" << std::endl;
2792  os << "\"" << get_node(n) << "\" [label=\"byte:" << n->byte
2793  << ", bit:" << int(n->bit) << "\"]" << std::endl;
2794 
2795  auto p = load(n->parent);
2796  auto parent = p ? get_node(p) : 0;
2797  os << "\"" << get_node(n) << "\" -> "
2798  << "\"" << parent << "\" [label=\"parent\"]" << std::endl;
2799 
2800  for (auto it = n->begin(); it != n->end(); ++it) {
2801  auto c = load(*it);
2802 
2803  if (!c)
2804  continue;
2805 
2806  auto ch = is_leaf(c) ? (void *)get_leaf(c)
2807  : (void *)get_node(c);
2808 
2809  os << "\"" << get_node(n) << "\" -> \"" << ch << "\""
2810  << std::endl;
2811  print_rec(os, c);
2812  }
2813  } else {
2814  auto bv = bytes_view(get_leaf(n)->key());
2815 
2816  os << "\"" << get_leaf(n) << "\" [style=filled,color=\"green\"]"
2817  << std::endl;
2818  os << "\"" << get_leaf(n) << "\" [label=\"key:";
2819 
2820  for (size_t i = 0; i < bv.size(); i++)
2821  os << bv[i];
2822 
2823  os << "\"]" << std::endl;
2824 
2825  auto p = load(get_leaf(n)->parent);
2826  auto parent = p ? get_node(p) : nullptr;
2827 
2828  os << "\"" << get_leaf(n) << "\" -> \"" << parent
2829  << "\" [label=\"parent\"]" << std::endl;
2830 
2831  if (parent && n == load(parent->embedded_entry)) {
2832  os << "{rank=same;\"" << parent << "\";\""
2833  << get_leaf(n) << "\"}" << std::endl;
2834  }
2835  }
2836 }
2837 
2841 template <typename K, typename V, typename BV, bool MtMode>
2842 std::ostream &
2843 operator<<(std::ostream &os, const radix_tree<K, V, BV, MtMode> &tree)
2844 {
2845  os << "digraph Radix {" << std::endl;
2846 
2847  if (radix_tree<K, V, BV, MtMode>::load(tree.root))
2848  radix_tree<K, V, BV, MtMode>::print_rec(
2849  os, radix_tree<K, V, BV, MtMode>::load(tree.root));
2850 
2851  os << "}" << std::endl;
2852 
2853  return os;
2854 }
2855 
2856 /*
2857  * internal: slice_index -- return index of child at the given nib
2858  */
2859 template <typename Key, typename Value, typename BytesView, bool MtMode>
2860 unsigned
2861 radix_tree<Key, Value, BytesView, MtMode>::slice_index(char b, uint8_t bit)
2862 {
2863  return static_cast<unsigned>(b >> bit) & NIB;
2864 }
2865 
2866 template <typename Key, typename Value, typename BytesView, bool MtMode>
2867 radix_tree<Key, Value, BytesView,
2868  MtMode>::node::forward_iterator::forward_iterator(pointer child,
2869  const node *n)
2870  : child(child), n(n)
2871 {
2872 }
2873 
2874 template <typename Key, typename Value, typename BytesView, bool MtMode>
2875 typename radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator
2876 radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator::operator++()
2877 {
2878  if (child == &n->embedded_entry)
2879  child = &n->child[0];
2880  else
2881  child++;
2882 
2883  return *this;
2884 }
2885 
2886 template <typename Key, typename Value, typename BytesView, bool MtMode>
2887 radix_tree<Key, Value, BytesView, MtMode>::node::node(pointer_type parent,
2888  byten_t byte, bitn_t bit)
2889  : parent(parent), byte(byte), bit(bit)
2890 {
2891 }
2892 
2893 template <typename Key, typename Value, typename BytesView, bool MtMode>
2894 typename radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator
2895 radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator::operator--()
2896 {
2897  if (child == &n->child[0])
2898  child = &n->embedded_entry;
2899  else
2900  child--;
2901 
2902  return *this;
2903 }
2904 
2905 template <typename Key, typename Value, typename BytesView, bool MtMode>
2906 typename radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator
2907 radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator::operator++(
2908  int)
2909 {
2910  forward_iterator tmp(child, n);
2911  operator++();
2912  return tmp;
2913 }
2914 
2915 template <typename Key, typename Value, typename BytesView, bool MtMode>
2916 typename radix_tree<Key, Value, BytesView,
2917  MtMode>::node::forward_iterator::reference
2918  radix_tree<Key, Value, BytesView,
2919  MtMode>::node::forward_iterator::operator*() const
2920 {
2921  return *child;
2922 }
2923 
2924 template <typename Key, typename Value, typename BytesView, bool MtMode>
2925 typename radix_tree<Key, Value, BytesView,
2926  MtMode>::node::forward_iterator::pointer
2927  radix_tree<Key, Value, BytesView,
2928  MtMode>::node::forward_iterator::operator->() const
2929 {
2930  return child;
2931 }
2932 
2933 template <typename Key, typename Value, typename BytesView, bool MtMode>
2934 typename radix_tree<Key, Value, BytesView,
2935  MtMode>::node::forward_iterator::pointer
2936 radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator::get_node()
2937  const
2938 {
2939  return n;
2940 }
2941 
2942 template <typename Key, typename Value, typename BytesView, bool MtMode>
2943 bool
2944 radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator::operator==(
2945  const forward_iterator &rhs) const
2946 {
2947  return child == rhs.child && n == rhs.n;
2948 }
2949 
2950 template <typename Key, typename Value, typename BytesView, bool MtMode>
2951 bool
2952 radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator::operator!=(
2953  const forward_iterator &rhs) const
2954 {
2955  return child != rhs.child || n != rhs.n;
2956 }
2957 
2958 template <typename Key, typename Value, typename BytesView, bool MtMode>
2959 template <bool Direction>
2960 typename std::enable_if<Direction ==
2961  radix_tree<Key, Value, BytesView,
2962  MtMode>::node::direction::Forward,
2963  typename radix_tree<Key, Value, BytesView, MtMode>::
2964  node::forward_iterator>::type
2965 radix_tree<Key, Value, BytesView, MtMode>::node::begin() const
2966 {
2967  return forward_iterator(&embedded_entry, this);
2968 }
2969 
2970 template <typename Key, typename Value, typename BytesView, bool MtMode>
2971 template <bool Direction>
2972 typename std::enable_if<Direction ==
2973  radix_tree<Key, Value, BytesView,
2974  MtMode>::node::direction::Forward,
2975  typename radix_tree<Key, Value, BytesView, MtMode>::
2976  node::forward_iterator>::type
2977 radix_tree<Key, Value, BytesView, MtMode>::node::end() const
2978 {
2979  return forward_iterator(&child[SLNODES], this);
2980 }
2981 
2982 template <typename Key, typename Value, typename BytesView, bool MtMode>
2983 template <bool Direction>
2984 typename std::enable_if<Direction ==
2985  radix_tree<Key, Value, BytesView,
2986  MtMode>::node::direction::Reverse,
2987  typename radix_tree<Key, Value, BytesView, MtMode>::
2988  node::reverse_iterator>::type
2989 radix_tree<Key, Value, BytesView, MtMode>::node::begin() const
2990 {
2991  return reverse_iterator(end<direction::Forward>());
2992 }
2993 
2994 template <typename Key, typename Value, typename BytesView, bool MtMode>
2995 template <bool Direction>
2996 typename std::enable_if<Direction ==
2997  radix_tree<Key, Value, BytesView,
2998  MtMode>::node::direction::Reverse,
2999  typename radix_tree<Key, Value, BytesView, MtMode>::
3000  node::reverse_iterator>::type
3001 radix_tree<Key, Value, BytesView, MtMode>::node::end() const
3002 {
3003  return reverse_iterator(begin<direction::Forward>());
3004 }
3005 
3006 template <typename Key, typename Value, typename BytesView, bool MtMode>
3007 template <bool Direction, typename Ptr>
3008 typename radix_tree<Key, Value, BytesView,
3009  MtMode>::node::template iterator<Direction>
3010 radix_tree<Key, Value, BytesView, MtMode>::node::find_child(const Ptr &n) const
3011 {
3012  auto it = begin<Direction>();
3013  while (it != end<Direction>()) {
3014  if (load(*it) == n)
3015  return it;
3016  ++it;
3017  }
3018  return it;
3019 }
3020 
3021 template <typename Key, typename Value, typename BytesView, bool MtMode>
3022 template <bool Direction, typename Enable>
3023 typename radix_tree<Key, Value, BytesView,
3024  MtMode>::node::template iterator<Direction>
3025 radix_tree<Key, Value, BytesView, MtMode>::node::make_iterator(
3026  const atomic_pointer_type *ptr) const
3027 {
3028  return forward_iterator(ptr, this);
3029 }
3030 
3031 template <typename Key, typename Value, typename BytesView, bool MtMode>
3032 template <bool IsConst>
3033 radix_tree<Key, Value, BytesView, MtMode>::radix_tree_iterator<
3034  IsConst>::radix_tree_iterator(leaf_ptr leaf_, tree_ptr tree)
3035  : leaf_(leaf_), tree(tree)
3036 {
3037  assert(tree);
3038 }
3039 
3040 template <typename Key, typename Value, typename BytesView, bool MtMode>
3041 template <bool IsConst>
3042 template <bool C, typename Enable>
3043 radix_tree<Key, Value, BytesView, MtMode>::radix_tree_iterator<
3044  IsConst>::radix_tree_iterator(const radix_tree_iterator<false> &rhs)
3045  : leaf_(rhs.leaf_), tree(rhs.tree)
3046 {
3047  assert(tree);
3048 }
3049 
3050 template <typename Key, typename Value, typename BytesView, bool MtMode>
3051 template <bool IsConst>
3052 typename radix_tree<Key, Value, BytesView,
3053  MtMode>::template radix_tree_iterator<IsConst>::reference
3054  radix_tree<Key, Value, BytesView,
3055  MtMode>::radix_tree_iterator<IsConst>::operator*() const
3056 {
3057  assert(leaf_);
3058  assert(tree);
3059 
3060  return *leaf_;
3061 }
3062 
3063 template <typename Key, typename Value, typename BytesView, bool MtMode>
3064 template <bool IsConst>
3065 typename radix_tree<Key, Value, BytesView,
3066  MtMode>::template radix_tree_iterator<IsConst>::pointer
3067  radix_tree<Key, Value, BytesView,
3068  MtMode>::radix_tree_iterator<IsConst>::operator->() const
3069 {
3070  assert(leaf_);
3071  assert(tree);
3072 
3073  return leaf_;
3074 }
3075 
3087 template <typename Key, typename Value, typename BytesView, bool MtMode>
3088 template <bool IsConst>
3089 template <typename V, typename Enable>
3090 void
3091 radix_tree<Key, Value, BytesView, MtMode>::radix_tree_iterator<
3092  IsConst>::assign_val(basic_string_view<typename V::value_type,
3093  typename V::traits_type>
3094  rhs)
3095 {
3096  assert(leaf_);
3097  assert(tree);
3098 
3099  auto pop = pool_base(pmemobj_pool_by_ptr(leaf_));
3100 
3101  if (rhs.size() <= leaf_->value().capacity() && !MtMode) {
3102  flat_transaction::run(pop, [&] { leaf_->value() = rhs; });
3103  } else {
3104  replace_val(rhs);
3105  }
3106 }
3107 
3108 template <typename Key, typename Value, typename BytesView, bool MtMode>
3109 template <bool IsConst>
3110 template <typename T>
3111 void
3112 radix_tree<Key, Value, BytesView,
3113  MtMode>::radix_tree_iterator<IsConst>::replace_val(T &&rhs)
3114 {
3115  auto pop = pool_base(pmemobj_pool_by_ptr(leaf_));
3116  atomic_pointer_type *slot;
3117 
3118  if (!load(leaf_->parent)) {
3119  assert(get_leaf(load(tree->root)) == leaf_);
3120  slot = &tree->root;
3121  } else {
3122  slot = const_cast<atomic_pointer_type *>(
3123  &*load(leaf_->parent)->find_child(leaf_));
3124  }
3125 
3126  auto old_leaf = leaf_;
3127 
3128  flat_transaction::run(pop, [&] {
3129  store(*slot,
3130  leaf::make_key_args(load(old_leaf->parent),
3131  old_leaf->key(),
3132  std::forward<T>(rhs)));
3133  tree->free(persistent_ptr<radix_tree::leaf>(old_leaf));
3134  });
3135 
3136  leaf_ = get_leaf(load(*slot));
3137 }
3138 
3146 template <typename Key, typename Value, typename BytesView, bool MtMode>
3147 template <bool IsConst>
3148 template <typename T, typename V, typename Enable>
3149 void
3150 radix_tree<Key, Value, BytesView,
3151  MtMode>::radix_tree_iterator<IsConst>::assign_val(T &&rhs)
3152 {
3153  if (MtMode && tree->ebr_ != nullptr)
3154  replace_val(std::forward<T>(rhs));
3155  else {
3156  auto pop = pool_base(pmemobj_pool_by_ptr(leaf_));
3157  flat_transaction::run(
3158  pop, [&] { leaf_->value() = std::forward<T>(rhs); });
3159  }
3160 }
3161 
3162 template <typename Key, typename Value, typename BytesView, bool MtMode>
3163 template <bool IsConst>
3164 typename radix_tree<Key, Value, BytesView,
3165  MtMode>::template radix_tree_iterator<IsConst> &
3166 radix_tree<Key, Value, BytesView,
3167  MtMode>::radix_tree_iterator<IsConst>::operator++()
3168 {
3169  /* Fallback to top-down search. */
3170  if (!try_increment())
3171  *this = tree->upper_bound(leaf_->key());
3172 
3173  return *this;
3174 }
3175 
3176 /*
3177  * Tries to increment iterator. Returns true on success, false otherwise.
3178  * Increment can fail in case of concurrent, conflicting operation.
3179  */
3180 template <typename Key, typename Value, typename BytesView, bool MtMode>
3181 template <bool IsConst>
3182 bool
3183 radix_tree<Key, Value, BytesView,
3184  MtMode>::radix_tree_iterator<IsConst>::try_increment()
3185 {
3186  assert(leaf_);
3187  assert(tree);
3188 
3189  constexpr auto direction = radix_tree::node::direction::Forward;
3190  auto parent_ptr = load(leaf_->parent);
3191 
3192  /* leaf is root, there is no other leaf in the tree */
3193  if (!parent_ptr) {
3194  leaf_ = nullptr;
3195  } else {
3196  auto it = parent_ptr->template find_child<direction>(leaf_);
3197 
3198  if (it == parent_ptr->template end<direction>())
3199  return false;
3200 
3201  auto ret = tree->template next_leaf<direction>(it, parent_ptr);
3202 
3203  if (!ret.first)
3204  return false;
3205 
3206  leaf_ = const_cast<leaf_ptr>(ret.second);
3207  }
3208 
3209  return true;
3210 }
3211 
3212 /*
3213  * If MtMode == true it's not safe to use this operator (iterator may end up
3214  * invalid if concurrent erase happen).
3215  * XXX: it's not enabled in MtMode due to:
3216  * https://github.com/pmem/libpmemobj-cpp/issues/1159
3217  */
3218 template <typename Key, typename Value, typename BytesView, bool MtMode>
3219 template <bool IsConst>
3220 template <bool Mt, typename Enable>
3221 typename radix_tree<Key, Value, BytesView,
3222  MtMode>::template radix_tree_iterator<IsConst> &
3223 radix_tree<Key, Value, BytesView,
3224  MtMode>::radix_tree_iterator<IsConst>::operator--()
3225 {
3226  while (!try_decrement()) {
3227  *this = tree->lower_bound(leaf_->key());
3228  }
3229 
3230  return *this;
3231 }
3232 
3233 /*
3234  * Tries to decrement iterator. Returns true on success, false otherwise.
3235  * Decrement can fail in case of concurrent, conflicting operation.
3236  */
3237 template <typename Key, typename Value, typename BytesView, bool MtMode>
3238 template <bool IsConst>
3239 bool
3240 radix_tree<Key, Value, BytesView,
3241  MtMode>::radix_tree_iterator<IsConst>::try_decrement()
3242 {
3243  constexpr auto direction = radix_tree::node::direction::Reverse;
3244  assert(tree);
3245 
3246  while (true) {
3247  if (!leaf_) {
3248  /* this == end() */
3249  auto r = load(tree->root);
3250 
3251  /* Iterator must be decrementable. */
3252  assert(r);
3253 
3254  leaf_ = const_cast<leaf_ptr>(
3255  tree->template find_leaf<direction>(r));
3256 
3257  if (leaf_)
3258  return true;
3259  } else {
3260  auto parent_ptr = load(leaf_->parent);
3261 
3262  /* Iterator must be decrementable. */
3263  assert(parent_ptr);
3264 
3265  auto it = parent_ptr->template find_child<direction>(
3266  leaf_);
3267 
3268  if (it == parent_ptr->template end<direction>())
3269  return false;
3270 
3271  auto ret = tree->template next_leaf<direction>(
3272  it, parent_ptr);
3273 
3274  if (!ret.first)
3275  return false;
3276 
3277  leaf_ = const_cast<leaf_ptr>(ret.second);
3278  return true;
3279  }
3280  }
3281 }
3282 
3283 template <typename Key, typename Value, typename BytesView, bool MtMode>
3284 template <bool IsConst>
3285 typename radix_tree<Key, Value, BytesView,
3286  MtMode>::template radix_tree_iterator<IsConst>
3287 radix_tree<Key, Value, BytesView,
3288  MtMode>::radix_tree_iterator<IsConst>::operator++(int)
3289 {
3290  auto tmp = *this;
3291 
3292  ++(*this);
3293 
3294  return tmp;
3295 }
3296 
3297 /*
3298  * If MtMode == true it's not safe to use this operator (iterator may end up
3299  * invalid if concurrent erase happen).
3300  * XXX: it's not enabled in MtMode due to:
3301  * https://github.com/pmem/libpmemobj-cpp/issues/1159
3302  */
3303 template <typename Key, typename Value, typename BytesView, bool MtMode>
3304 template <bool IsConst>
3305 template <bool Mt, typename Enable>
3306 typename radix_tree<Key, Value, BytesView,
3307  MtMode>::template radix_tree_iterator<IsConst>
3308 radix_tree<Key, Value, BytesView,
3309  MtMode>::radix_tree_iterator<IsConst>::operator--(int)
3310 {
3311  auto tmp = *this;
3312 
3313  --(*this);
3314 
3315  return tmp;
3316 }
3317 
3318 template <typename Key, typename Value, typename BytesView, bool MtMode>
3319 template <bool IsConst>
3320 template <bool C>
3321 bool
3322 radix_tree<Key, Value, BytesView, MtMode>::radix_tree_iterator<
3323  IsConst>::operator!=(const radix_tree_iterator<C> &rhs) const
3324 {
3325  return leaf_ != rhs.leaf_;
3326 }
3327 
3328 template <typename Key, typename Value, typename BytesView, bool MtMode>
3329 template <bool IsConst>
3330 template <bool C>
3331 bool
3332 radix_tree<Key, Value, BytesView, MtMode>::radix_tree_iterator<
3333  IsConst>::operator==(const radix_tree_iterator<C> &rhs) const
3334 {
3335  return !(*this != rhs);
3336 }
3337 
3338 /*
3339  * Returns a pair consisting of a bool and a leaf pointer to the
3340  * next leaf (either with smaller or larger key than k, depending on
3341  * ChildIterator type). This function might need to traverse the
3342  * tree upwards. Pointer can be null if there is no such leaf.
3343  *
3344  * Bool variable is set to true on success, false otherwise.
3345  * Failure can occur in case of a concurrent, conflicting operation.
3346  */
3347 template <typename Key, typename Value, typename BytesView, bool MtMode>
3348 template <bool Direction, typename Iterator>
3349 std::pair<bool,
3350  const typename radix_tree<Key, Value, BytesView, MtMode>::leaf *>
3351 radix_tree<Key, Value, BytesView, MtMode>::next_leaf(Iterator node,
3352  pointer_type parent) const
3353 {
3354  while (true) {
3355  ++node;
3356 
3357  /* No more children on this level, need to go up. */
3358  if (node == parent->template end<Direction>()) {
3359  auto p = load(parent->parent);
3360  if (!p) /* parent == root */
3361  return {true, nullptr};
3362 
3363  auto p_it = p->template find_child<Direction>(parent);
3364  if (p_it == p->template end<Direction>()) {
3365  /* Detached leaf, cannot advance. */
3366  return {false, nullptr};
3367  }
3368 
3369  return next_leaf<Direction>(p_it, p);
3370  }
3371 
3372  auto n = load(*node);
3373  if (!n)
3374  continue;
3375 
3376  auto leaf = find_leaf<Direction>(n);
3377  if (!leaf)
3378  return {false, nullptr};
3379 
3380  return {true, leaf};
3381  }
3382 }
3383 
3384 /*
3385  * Returns smallest (or biggest, depending on ChildIterator) leaf
3386  * in a subtree.
3387  *
3388  * Return value is null only if there was some concurrent, conflicting
3389  * operation.
3390  */
3391 template <typename Key, typename Value, typename BytesView, bool MtMode>
3392 template <bool Direction>
3393 const typename radix_tree<Key, Value, BytesView, MtMode>::leaf *
3394 radix_tree<Key, Value, BytesView, MtMode>::find_leaf(
3395  typename radix_tree<Key, Value, BytesView, MtMode>::pointer_type n)
3396  const
3397 {
3398  assert(n);
3399 
3400  if (is_leaf(n))
3401  return get_leaf(n);
3402 
3403  for (auto it = n->template begin<Direction>();
3404  it != n->template end<Direction>(); ++it) {
3405  auto ptr = load(*it);
3406  if (ptr)
3407  return find_leaf<Direction>(ptr);
3408  }
3409 
3410  /* If there is no leaf at the bottom this means that concurrent erase
3411  * happened. */
3412  return nullptr;
3413 }
3414 
3415 template <typename Key, typename Value, typename BytesView, bool MtMode>
3416 Key &
3417 radix_tree<Key, Value, BytesView, MtMode>::leaf::key()
3418 {
3419  auto &const_key = const_cast<const leaf *>(this)->key();
3420  return *const_cast<Key *>(&const_key);
3421 }
3422 
3423 template <typename Key, typename Value, typename BytesView, bool MtMode>
3424 Value &
3425 radix_tree<Key, Value, BytesView, MtMode>::leaf::value()
3426 {
3427  auto &const_value = const_cast<const leaf *>(this)->value();
3428  return *const_cast<Value *>(&const_value);
3429 }
3430 
3431 template <typename Key, typename Value, typename BytesView, bool MtMode>
3432 const Key &
3433 radix_tree<Key, Value, BytesView, MtMode>::leaf::key() const
3434 {
3435  return *reinterpret_cast<const Key *>(this + 1);
3436 }
3437 
3438 template <typename Key, typename Value, typename BytesView, bool MtMode>
3439 const Value &
3440 radix_tree<Key, Value, BytesView, MtMode>::leaf::value() const
3441 {
3442  auto key_dst = reinterpret_cast<const char *>(this + 1);
3443  auto key_size = total_sizeof<Key>::value(key());
3444  auto padding = detail::align_up(key_size, alignof(Value)) - key_size;
3445  auto val_dst =
3446  reinterpret_cast<const Value *>(key_dst + padding + key_size);
3447 
3448  return *val_dst;
3449 }
3450 
3451 template <typename Key, typename Value, typename BytesView, bool MtMode>
3452 radix_tree<Key, Value, BytesView, MtMode>::leaf::~leaf()
3453 {
3454  detail::destroy<Key>(key());
3455  detail::destroy<Value>(value());
3456 }
3457 
3458 template <typename Key, typename Value, typename BytesView, bool MtMode>
3459 persistent_ptr<typename radix_tree<Key, Value, BytesView, MtMode>::leaf>
3460 radix_tree<Key, Value, BytesView, MtMode>::leaf::make(pointer_type parent)
3461 {
3462  auto t = std::make_tuple();
3463  return make(parent, std::piecewise_construct, t, t,
3464  detail::index_sequence_for<>{},
3465  detail::index_sequence_for<>{});
3466 }
3467 
3468 template <typename Key, typename Value, typename BytesView, bool MtMode>
3469 template <typename... Args1, typename... Args2>
3470 persistent_ptr<typename radix_tree<Key, Value, BytesView, MtMode>::leaf>
3471 radix_tree<Key, Value, BytesView, MtMode>::leaf::make(
3472  pointer_type parent, std::piecewise_construct_t pc,
3473  std::tuple<Args1...> first_args, std::tuple<Args2...> second_args)
3474 {
3475  return make(parent, pc, first_args, second_args,
3476  detail::index_sequence_for<Args1...>{},
3477  detail::index_sequence_for<Args2...>{});
3478 }
3479 
3480 template <typename Key, typename Value, typename BytesView, bool MtMode>
3481 persistent_ptr<typename radix_tree<Key, Value, BytesView, MtMode>::leaf>
3482 radix_tree<Key, Value, BytesView, MtMode>::leaf::make(pointer_type parent,
3483  const Key &k,
3484  const Value &v)
3485 {
3486  return make(parent, std::piecewise_construct, std::forward_as_tuple(k),
3487  std::forward_as_tuple(v));
3488 }
3489 
3490 template <typename Key, typename Value, typename BytesView, bool MtMode>
3491 template <typename K, typename V>
3492 persistent_ptr<typename radix_tree<Key, Value, BytesView, MtMode>::leaf>
3493 radix_tree<Key, Value, BytesView, MtMode>::leaf::make(pointer_type parent,
3494  K &&k, V &&v)
3495 {
3496  return make(parent, std::piecewise_construct,
3497  std::forward_as_tuple(std::forward<K>(k)),
3498  std::forward_as_tuple(std::forward<V>(v)));
3499 }
3500 
3501 template <typename Key, typename Value, typename BytesView, bool MtMode>
3502 template <typename K, typename... Args>
3503 persistent_ptr<typename radix_tree<Key, Value, BytesView, MtMode>::leaf>
3504 radix_tree<Key, Value, BytesView, MtMode>::leaf::make_key_args(
3505  pointer_type parent, K &&k, Args &&... args)
3506 {
3507  return make(parent, std::piecewise_construct,
3508  std::forward_as_tuple(std::forward<K>(k)),
3509  std::forward_as_tuple(std::forward<Args>(args)...));
3510 }
3511 
3512 template <typename Key, typename Value, typename BytesView, bool MtMode>
3513 template <typename K, typename V>
3514 persistent_ptr<typename radix_tree<Key, Value, BytesView, MtMode>::leaf>
3515 radix_tree<Key, Value, BytesView, MtMode>::leaf::make(pointer_type parent,
3516  detail::pair<K, V> &&p)
3517 {
3518  return make(parent, std::piecewise_construct,
3519  std::forward_as_tuple(std::move(p.first)),
3520  std::forward_as_tuple(std::move(p.second)));
3521 }
3522 
3523 template <typename Key, typename Value, typename BytesView, bool MtMode>
3524 template <typename K, typename V>
3525 persistent_ptr<typename radix_tree<Key, Value, BytesView, MtMode>::leaf>
3526 radix_tree<Key, Value, BytesView, MtMode>::leaf::make(
3527  pointer_type parent, const detail::pair<K, V> &p)
3528 {
3529  return make(parent, std::piecewise_construct,
3530  std::forward_as_tuple(p.first),
3531  std::forward_as_tuple(p.second));
3532 }
3533 
3534 template <typename Key, typename Value, typename BytesView, bool MtMode>
3535 template <typename K, typename V>
3536 persistent_ptr<typename radix_tree<Key, Value, BytesView, MtMode>::leaf>
3537 radix_tree<Key, Value, BytesView, MtMode>::leaf::make(pointer_type parent,
3538  std::pair<K, V> &&p)
3539 {
3540  return make(parent, std::piecewise_construct,
3541  std::forward_as_tuple(std::move(p.first)),
3542  std::forward_as_tuple(std::move(p.second)));
3543 }
3544 
3545 template <typename Key, typename Value, typename BytesView, bool MtMode>
3546 template <typename K, typename V>
3547 persistent_ptr<typename radix_tree<Key, Value, BytesView, MtMode>::leaf>
3548 radix_tree<Key, Value, BytesView, MtMode>::leaf::make(pointer_type parent,
3549  const std::pair<K, V> &p)
3550 {
3551  return make(parent, std::piecewise_construct,
3552  std::forward_as_tuple(p.first),
3553  std::forward_as_tuple(p.second));
3554 }
3555 
3556 template <typename Key, typename Value, typename BytesView, bool MtMode>
3557 template <typename... Args1, typename... Args2, size_t... I1, size_t... I2>
3558 persistent_ptr<typename radix_tree<Key, Value, BytesView, MtMode>::leaf>
3559 radix_tree<Key, Value, BytesView, MtMode>::leaf::make(
3560  pointer_type parent, std::piecewise_construct_t,
3561  std::tuple<Args1...> &first_args, std::tuple<Args2...> &second_args,
3562  detail::index_sequence<I1...>, detail::index_sequence<I2...>)
3563 {
3564  standard_alloc_policy<void> a;
3565  auto key_size = total_sizeof<Key>::value(std::get<I1>(first_args)...);
3566  auto val_size =
3567  total_sizeof<Value>::value(std::get<I2>(second_args)...);
3568  auto padding = detail::align_up(key_size, alignof(Value)) - key_size;
3569  auto ptr = static_cast<persistent_ptr<leaf>>(
3570  a.allocate(sizeof(leaf) + key_size + padding + val_size));
3571 
3572  auto key_dst = reinterpret_cast<Key *>(ptr.get() + 1);
3573  auto val_dst = reinterpret_cast<Value *>(
3574  reinterpret_cast<char *>(key_dst) + padding + key_size);
3575 
3576  assert(reinterpret_cast<uintptr_t>(key_dst) % alignof(Key) == 0);
3577  assert(reinterpret_cast<uintptr_t>(val_dst) % alignof(Value) == 0);
3578 
3579  new (ptr.get()) leaf();
3580  new (key_dst) Key(std::forward<Args1>(std::get<I1>(first_args))...);
3581  new (val_dst) Value(std::forward<Args2>(std::get<I2>(second_args))...);
3582 
3583  store(ptr->parent, parent);
3584 
3585  return ptr;
3586 }
3587 
3588 template <typename Key, typename Value, typename BytesView, bool MtMode>
3589 persistent_ptr<typename radix_tree<Key, Value, BytesView, MtMode>::leaf>
3590 radix_tree<Key, Value, BytesView, MtMode>::leaf::make(pointer_type parent,
3591  const leaf &other)
3592 {
3593  return make(parent, other.key(), other.value());
3594 }
3595 
3602 template <typename Key, typename Value, typename BytesView, bool MtMode>
3603 void
3604 radix_tree<Key, Value, BytesView, MtMode>::check_pmem()
3605 {
3606  if (nullptr == pmemobj_pool_by_ptr(this))
3607  throw pmem::pool_error("Invalid pool handle.");
3608 }
3609 
3617 template <typename Key, typename Value, typename BytesView, bool MtMode>
3618 void
3619 radix_tree<Key, Value, BytesView, MtMode>::check_tx_stage_work()
3620 {
3621  if (pmemobj_tx_stage() != TX_STAGE_WORK)
3622  throw pmem::transaction_scope_error(
3623  "Function called out of transaction scope.");
3624 }
3625 
3626 template <typename Key, typename Value, typename BytesView, bool MtMode>
3627 bool
3628 radix_tree<Key, Value, BytesView, MtMode>::is_leaf(
3629  const radix_tree<Key, Value, BytesView, MtMode>::pointer_type &p)
3630 {
3631  return p.template is<leaf>();
3632 }
3633 
3634 template <typename Key, typename Value, typename BytesView, bool MtMode>
3635 typename radix_tree<Key, Value, BytesView, MtMode>::leaf *
3636 radix_tree<Key, Value, BytesView, MtMode>::get_leaf(
3637  const radix_tree<Key, Value, BytesView, MtMode>::pointer_type &p)
3638 {
3639  return p.template get<leaf>();
3640 }
3641 
3642 template <typename Key, typename Value, typename BytesView, bool MtMode>
3643 typename radix_tree<Key, Value, BytesView, MtMode>::node *
3644 radix_tree<Key, Value, BytesView, MtMode>::get_node(
3645  const radix_tree<Key, Value, BytesView, MtMode>::pointer_type &p)
3646 {
3647  return p.template get<node>();
3648 }
3649 
3654 template <typename Key, typename Value, typename BytesView, bool MtMode>
3655 void
3656 swap(radix_tree<Key, Value, BytesView, MtMode> &lhs,
3657  radix_tree<Key, Value, BytesView, MtMode> &rhs)
3658 {
3659  lhs.swap(rhs);
3660 }
3661 
3662 /* Check if type is pmem::obj::basic_string or
3663  * pmem::obj::basic_inline_string */
3664 template <typename>
3665 struct is_string : std::false_type {
3666 };
3667 
3668 template <typename CharT, typename Traits>
3669 struct is_string<obj::basic_string<CharT, Traits>> : std::true_type {
3670 };
3671 
3672 template <typename CharT, typename Traits>
3673 struct is_string<obj::experimental::basic_inline_string<CharT, Traits>>
3674  : std::true_type {
3675 };
3676 
3677 template <typename T>
3678 struct bytes_view<T, typename std::enable_if<is_string<T>::value>::type> {
3679  using CharT = typename T::value_type;
3680  using Traits = typename T::traits_type;
3681 
3682  template <
3683  typename C,
3684  typename Enable = typename std::enable_if<std::is_constructible<
3685  obj::basic_string_view<CharT, Traits>, C>::value>::type>
3686  bytes_view(const C *s) : s(*s)
3687  {
3688  }
3689 
3690  char operator[](std::size_t p) const
3691  {
3692  return reinterpret_cast<const char *>(s.data())[p];
3693  }
3694 
3695  size_t
3696  size() const
3697  {
3698  return s.size() * sizeof(CharT);
3699  }
3700 
3701  obj::basic_string_view<CharT, Traits> s;
3702 
3703  using is_transparent = void;
3704 };
3705 
3706 template <typename T>
3707 struct bytes_view<T,
3708  typename std::enable_if<std::is_integral<T>::value &&
3709  !std::is_signed<T>::value>::type> {
3710  bytes_view(const T *k) : k(k)
3711  {
3712 #if __cpp_lib_endian
3713  static_assert(
3714  std::endian::native == std::endian::little,
3715  "Scalar type are not little endian on this platform!");
3716 #elif !defined(NDEBUG)
3717  /* Assert little endian is used. */
3718  uint16_t word = (2 << 8) + 1;
3719  assert(((char *)&word)[0] == 1);
3720 #endif
3721  }
3722 
3723  char operator[](std::size_t p) const
3724  {
3725  return reinterpret_cast<const char *>(k)[size() - p - 1];
3726  }
3727 
3728  constexpr size_t
3729  size() const
3730  {
3731  return sizeof(T);
3732  }
3733 
3734  const T *k;
3735 };
3736 
3737 } /* namespace experimental */
3738 } /* namespace obj */
3739 } /* namespace pmem */
3740 
3741 #endif /* LIBPMEMOBJ_CPP_RADIX_HPP */
allocator.hpp
Persistent memory aware allocator.
pmem::detail::ebr
Epoch-based reclamation (EBR).
Definition: ebr.hpp:68
pmem::obj::basic_string_view
Our partial std::string_view implementation.
Definition: string_view.hpp:48
pmem::obj::basic_string
Persistent string container with std::basic_string compatible interface.
Definition: basic_string.hpp:48
pmem::obj::basic_transaction::run
static void run(obj::pool_base &pool, std::function< void()> tx, Locks &... locks)
Execute a closure-like transaction and lock locks.
Definition: transaction.hpp:676
pmem::obj::experimental::radix_tree
Persistent associative, ordered container with API similar and partially compatible with the API of s...
Definition: radix_tree.hpp:123
pmem::obj::experimental::radix_tree::crend
const_reverse_iterator crend() const
Returns a const, reverse iterator to the end.
Definition: radix_tree.hpp:2765
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:2656
pmem::obj::experimental::radix_tree::runtime_finalize_mt
void runtime_finalize_mt()
If MtMode == true, this function must be called before each application close and before calling radi...
Definition: radix_tree.hpp:1106
pmem::obj::experimental::radix_tree::rend
reverse_iterator rend()
Returns a reverse iterator to the end.
Definition: radix_tree.hpp:2736
pmem::obj::experimental::radix_tree::swap
void swap(radix_tree &rhs)
Member swap.
Definition: radix_tree.hpp:976
pmem::obj::experimental::radix_tree::begin
iterator begin()
Returns an iterator to the first element of the container.
Definition: radix_tree.hpp:2624
pmem::obj::experimental::radix_tree::crbegin
const_reverse_iterator crbegin() const
Returns a const, reverse iterator to the beginning.
Definition: radix_tree.hpp:2750
pmem::obj::experimental::radix_tree::size
uint64_t size() const noexcept
Definition: radix_tree.hpp:964
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:2641
pmem::obj::experimental::radix_tree::swap
void swap(radix_tree< Key, Value, BytesView, MtMode > &lhs, radix_tree< Key, Value, BytesView, MtMode > &rhs)
Non-member swap.
Definition: radix_tree.hpp:3656
pmem::obj::experimental::radix_tree::runtime_initialize_mt
void runtime_initialize_mt(ebr *e=new ebr())
If MtMode == true, this function must be called after each application restart.
Definition: radix_tree.hpp:1091
pmem::obj::experimental::radix_tree::empty
bool empty() const noexcept
Checks whether the container is empty.
Definition: radix_tree.hpp:944
pmem::obj::experimental::radix_tree::max_size
size_type max_size() const noexcept
Definition: radix_tree.hpp:954
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:1614
pmem::obj::experimental::radix_tree::rbegin
reverse_iterator rbegin()
Returns a reverse iterator to the beginning.
Definition: radix_tree.hpp:2721
pmem::obj::experimental::radix_tree::erase
iterator erase(const_iterator pos)
Removes the element at pos from the container.
Definition: radix_tree.hpp:2048
pmem::obj::experimental::radix_tree::register_worker
worker_type register_worker()
Registers and returns a new worker, which can perform critical operations (accessing some shared data...
Definition: radix_tree.hpp:1125
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:2485
pmem::obj::experimental::radix_tree::~radix_tree
~radix_tree()
Destructor.
Definition: radix_tree.hpp:926
pmem::obj::experimental::radix_tree::clear
void clear()
Erases all elements from the container transactionally.
Definition: radix_tree.hpp:2025
pmem::obj::experimental::radix_tree::find
iterator find(const key_type &k)
Finds an element with key equivalent to key.
Definition: radix_tree.hpp:1932
pmem::obj::experimental::radix_tree::garbage_collect
void garbage_collect()
Tries to collect and free some garbage produced by erase, clear, insert_or_assign or assign_val in co...
Definition: radix_tree.hpp:1019
pmem::obj::experimental::radix_tree::operator=
radix_tree & operator=(const radix_tree &m)
Copy assignment operator.
Definition: radix_tree.hpp:839
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:2565
pmem::obj::experimental::radix_tree::garbage_collect_force
void garbage_collect_force()
Performs full epochs synchronisation.
Definition: radix_tree.hpp:998
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:2680
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:1897
pmem::obj::experimental::radix_tree::radix_tree
radix_tree()
Default radix tree constructor.
Definition: radix_tree.hpp:718
pmem::obj::experimental::v
Volatile residing on pmem class.
Definition: v.hpp:43
pmem::obj::flat_transaction::run
static void run(obj::pool_base &pool, std::function< void()> tx, Locks &... locks)
Execute a closure-like transaction and lock locks.
Definition: transaction.hpp:810
pmem::obj::p
Resides on pmem class.
Definition: p.hpp:36
pmem::obj::persistent_ptr
Persistent pointer class.
Definition: persistent_ptr.hpp:153
pmem::obj::persistent_ptr::get
element_type * get() const noexcept
Get the direct pointer.
Definition: persistent_ptr.hpp:479
pmem::obj::pool_base
The non-template pool base class.
Definition: pool.hpp:51
pmem::pool_error
Custom pool error class.
Definition: pexceptions.hpp:84
pmem::transaction_scope_error
Custom transaction error class.
Definition: pexceptions.hpp:167
common.hpp
Commonly used functionality.
ebr.hpp
C++ Epoch-based reclamation API.
pmem::obj::string_view
basic_string_view< char > string_view
The most typical string_view usage - the char specialization.
Definition: string_view.hpp:169
inline_string.hpp
Inline string implementation.
integer_sequence.hpp
Create c++14 style index sequence.
make_persistent.hpp
persistent_ptr transactional allocation functions for objects.
pmem::detail::mssb_index
static uint8_t mssb_index(unsigned int value)
Returns index of most significant set bit.
Definition: common.hpp:289
pmem::obj::experimental::operator<<
std::ostream & operator<<(std::ostream &os, const radix_tree< K, V, BV, MtMode > &tree)
Prints tree in DOT format.
Definition: radix_tree.hpp:2843
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
Persistent memory namespace.
Definition: allocation_flag.hpp:15
p.hpp
Resides on pmem property template.
pair.hpp
Pair implementation.
persistent_ptr.hpp
Persistent smart pointer.
pext.hpp
Convenience extensions for the resides on pmem property template.
pool.hpp
C++ pmemobj pool.
self_relative_ptr.hpp
Persistent self-relative smart pointer.
string.hpp
String typedefs for common character types.
string_view.hpp
Our partial std::string_view implementation.
pmem::obj::experimental::radix_tree::leaf
This is the structure which 'holds' key/value pair.
Definition: radix_tree.hpp:438
pmem::obj::experimental::radix_tree::node
This is internal node.
Definition: radix_tree.hpp:504
pmem::obj::experimental::radix_tree::node::parent
atomic_pointer_type parent
Pointer to a parent node.
Definition: radix_tree.hpp:510
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:533
pmem::obj::experimental::radix_tree::node::embedded_entry
atomic_pointer_type 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:518
tagged_ptr.hpp
Persistent tagged pointer.
template_helpers.hpp
Commonly used SFINAE helpers.
transaction.hpp
C++ pmemobj transactions.
utils.hpp
Libpmemobj C++ utils.
v.hpp
Volatile residing on pmem property template.