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