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