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