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