PMDK C++ bindings 1.13.0
This is the C++ bindings documentation for PMDK's libpmemobj.
Loading...
Searching...
No Matches
radix_tree.hpp
Go to the documentation of this file.
1// SPDX-License-Identifier: BSD-3-Clause
2/* Copyright 2020-2022, Intel Corporation */
3
16#ifndef LIBPMEMOBJ_CPP_RADIX_HPP
17#define LIBPMEMOBJ_CPP_RADIX_HPP
18
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 iterator<Direction> find_child(const Ptr &n) const;
587
588 template <bool Direction = direction::Forward,
589 typename Enable = typename std::enable_if<
590 Direction == direction::Forward>::type>
591 iterator<Direction> make_iterator(const atomic_pointer_type *ptr) const;
592
593 uint8_t padding[256 - sizeof(parent) - sizeof(leaf) - sizeof(child) -
594 sizeof(byte) - sizeof(bit)];
595};
596
602template <typename Key, typename Value, typename BytesView, bool MtMode>
603template <bool IsConst>
604struct radix_tree<Key, Value, BytesView, MtMode>::radix_tree_iterator {
605private:
606 using leaf_ptr =
607 typename std::conditional<IsConst, const leaf *, leaf *>::type;
608 using tree_ptr = typename std::conditional<IsConst, const radix_tree *,
609 radix_tree *>::type;
610 friend struct radix_tree_iterator<true>;
611
612public:
613 using difference_type = std::ptrdiff_t;
615 using reference = typename std::conditional<IsConst, const value_type &,
616 value_type &>::type;
617 using pointer = typename std::conditional<IsConst, value_type const *,
618 value_type *>::type;
619 using iterator_category = typename std::conditional<
620 MtMode, std::forward_iterator_tag,
621 std::bidirectional_iterator_tag>::type;
622
623 radix_tree_iterator() = default;
624 radix_tree_iterator(leaf_ptr leaf_, tree_ptr tree);
625 radix_tree_iterator(const radix_tree_iterator &rhs) = default;
626
627 template <bool C = IsConst,
628 typename Enable = typename std::enable_if<C>::type>
630
632 operator=(const radix_tree_iterator &rhs) = default;
633
634 reference operator*() const;
635 pointer operator->() const;
636
637 template <typename V = Value,
638 typename Enable = typename std::enable_if<
639 detail::is_inline_string<V>::value>::type>
640 void assign_val(basic_string_view<typename V::value_type,
641 typename V::traits_type>
642 rhs);
643
644 template <typename T, typename V = Value,
645 typename Enable = typename std::enable_if<
646 !detail::is_inline_string<V>::value>::type>
647 void assign_val(T &&rhs);
648
650 template <bool Mt = MtMode,
651 typename Enable = typename std::enable_if<!Mt>::type>
653
655 template <bool Mt = MtMode,
656 typename Enable = typename std::enable_if<!Mt>::type>
658
659 template <bool C>
660 bool operator!=(const radix_tree_iterator<C> &rhs) const;
661
662 template <bool C>
663 bool operator==(const radix_tree_iterator<C> &rhs) const;
664
665private:
666 friend class radix_tree;
667
668 leaf_ptr leaf_ = nullptr;
669 tree_ptr tree = nullptr;
670
671 template <typename T>
672 void replace_val(T &&rhs);
673
674 bool try_increment();
675 bool try_decrement();
676};
677
678template <typename Key, typename Value, typename BytesView, bool MtMode>
679struct radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator {
680 using difference_type = std::ptrdiff_t;
681 using value_type = atomic_pointer_type;
682 using pointer = const value_type *;
683 using reference = const value_type &;
684 using iterator_category = std::forward_iterator_tag;
685
686 forward_iterator(pointer child, const node *node);
687
688 forward_iterator operator++();
689 forward_iterator operator++(int);
690
691 forward_iterator operator--();
692
693 reference operator*() const;
694 pointer operator->() const;
695
696 pointer get_node() const;
697
698 bool operator!=(const forward_iterator &rhs) const;
699 bool operator==(const forward_iterator &rhs) const;
700
701private:
702 pointer child;
703 const node *n;
704};
705
714template <typename Key, typename Value, typename BytesView, bool MtMode>
716 : root(nullptr), size_(0)
717{
718 check_pmem();
720}
721
741template <typename Key, typename Value, typename BytesView, bool MtMode>
742template <class InputIt>
744 InputIt last)
745 : root(nullptr), size_(0)
746{
747 check_pmem();
749
750 for (auto it = first; it != last; it++)
751 emplace(*it);
752}
753
769template <typename Key, typename Value, typename BytesView, bool MtMode>
771 : root(nullptr), size_(0)
772{
773 check_pmem();
775
776 for (auto it = m.cbegin(); it != m.cend(); it++)
777 emplace(*it);
778}
779
792template <typename Key, typename Value, typename BytesView, bool MtMode>
794{
795 check_pmem();
796 check_tx_stage_work();
797
798 store(root, load(m.root));
799 size_ = m.size_;
800 store(m.root, nullptr);
801 m.size_ = 0;
802}
803
818template <typename Key, typename Value, typename BytesView, bool MtMode>
820 std::initializer_list<value_type> il)
821 : radix_tree(il.begin(), il.end())
822{
823}
824
834template <typename Key, typename Value, typename BytesView, bool MtMode>
837{
838 check_pmem();
839
840 auto pop = pool_by_vptr(this);
841
842 if (this != &other) {
843 flat_transaction::run(pop, [&] {
844 clear();
845
846 store(this->root, nullptr);
847 this->size_ = 0;
848
849 for (auto it = other.cbegin(); it != other.cend(); it++)
850 emplace(*it);
851 });
852 }
853
854 return *this;
855}
856
865template <typename Key, typename Value, typename BytesView, bool MtMode>
868{
869 check_pmem();
870
871 auto pop = pool_by_vptr(this);
872
873 if (this != &other) {
874 flat_transaction::run(pop, [&] {
875 clear();
876
877 store(this->root, load(other.root));
878 this->size_ = other.size_;
879 store(other.root, nullptr);
880 other.size_ = 0;
881 });
882 }
883
884 return *this;
885}
886
897template <typename Key, typename Value, typename BytesView, bool MtMode>
900 std::initializer_list<value_type> ilist)
901{
902 check_pmem();
903
904 auto pop = pool_by_vptr(this);
905
906 transaction::run(pop, [&] {
907 clear();
908
909 store(this->root, nullptr);
910 this->size_ = 0;
911
912 for (auto it = ilist.begin(); it != ilist.end(); it++)
913 emplace(*it);
914 });
915
916 return *this;
917}
918
922template <typename Key, typename Value, typename BytesView, bool MtMode>
924{
925 try {
926 clear();
927 for (size_t i = 0; i < EPOCHS_NUMBER; ++i)
928 clear_garbage(i);
929 } catch (...) {
930 std::terminate();
931 }
932}
933
939template <typename Key, typename Value, typename BytesView, bool MtMode>
940bool
942{
943 return size_ == 0;
944}
945
949template <typename Key, typename Value, typename BytesView, bool MtMode>
950typename radix_tree<Key, Value, BytesView, MtMode>::size_type
952{
953 return std::numeric_limits<difference_type>::max();
954}
955
959template <typename Key, typename Value, typename BytesView, bool MtMode>
960uint64_t
962{
963 return this->size_;
964}
965
971template <typename Key, typename Value, typename BytesView, bool MtMode>
972void
974{
975 auto pop = pool_by_vptr(this);
976
977 flat_transaction::run(pop, [&] {
978 this->size_.swap(rhs.size_);
979 this->root.swap(rhs.root);
980 });
981}
982
992template <typename Key, typename Value, typename BytesView, bool MtMode>
993template <bool Mt, typename Enable>
994void
996{
997 ebr_->full_sync();
998 for (size_t i = 0; i < EPOCHS_NUMBER; ++i) {
999 clear_garbage(i);
1000 }
1001}
1002
1013template <typename Key, typename Value, typename BytesView, bool MtMode>
1014template <bool Mt, typename Enable>
1015void
1017{
1018 ebr_->sync();
1019 clear_garbage(ebr_->gc_epoch());
1020}
1021
1022template <typename Key, typename Value, typename BytesView, bool MtMode>
1023void
1025{
1026 assert(n >= 0 && n < EPOCHS_NUMBER);
1027
1028 auto pop = pool_by_vptr(this);
1029
1030 flat_transaction::run(pop, [&] {
1031 for (auto &e : garbages[n]) {
1032 if (is_leaf(e))
1033 delete_persistent<radix_tree::leaf>(
1035 get_leaf(e)));
1036 else
1037 delete_persistent<radix_tree::node>(
1039 get_node(e)));
1040 }
1041
1042 garbages[n].clear();
1043 });
1044}
1045
1046template <typename Key, typename Value, typename BytesView, bool MtMode>
1047typename radix_tree<Key, Value, BytesView, MtMode>::pointer_type
1048radix_tree<Key, Value, BytesView, MtMode>::load(
1049 const std::atomic<detail::tagged_ptr<leaf, node>> &ptr)
1050{
1051 return ptr.load_acquire();
1052}
1053
1054template <typename Key, typename Value, typename BytesView, bool MtMode>
1055typename radix_tree<Key, Value, BytesView, MtMode>::pointer_type
1056radix_tree<Key, Value, BytesView, MtMode>::load(const pointer_type &ptr)
1057{
1058 return ptr;
1059}
1060
1061template <typename Key, typename Value, typename BytesView, bool MtMode>
1062void
1063radix_tree<Key, Value, BytesView, MtMode>::store(
1064 std::atomic<detail::tagged_ptr<leaf, node>> &ptr, pointer_type desired)
1065{
1066 ptr.store_with_snapshot_release(desired);
1067}
1068
1069template <typename Key, typename Value, typename BytesView, bool MtMode>
1070void
1071radix_tree<Key, Value, BytesView, MtMode>::store(pointer_type &ptr,
1072 pointer_type desired)
1073{
1074 ptr = desired;
1075}
1076
1085template <typename Key, typename Value, typename BytesView, bool MtMode>
1086template <bool Mt, typename Enable>
1087void
1089{
1090#if LIBPMEMOBJ_CPP_VG_PMEMCHECK_ENABLED
1091 VALGRIND_PMC_REMOVE_PMEM_MAPPING(&ebr_, sizeof(ebr *));
1092#endif
1093 ebr_ = e;
1094}
1095
1100template <typename Key, typename Value, typename BytesView, bool MtMode>
1101template <bool Mt, typename Enable>
1102void
1104{
1105 if (ebr_) {
1106 delete ebr_;
1107 }
1108 ebr_ = nullptr;
1109}
1110
1119template <typename Key, typename Value, typename BytesView, bool MtMode>
1120template <bool Mt, typename Enable>
1121typename radix_tree<Key, Value, BytesView, MtMode>::worker_type
1123{
1124 assert(ebr_);
1125
1126 return ebr_->register_worker();
1127}
1128
1129/*
1130 * Returns reference to n->parent (handles both internal and leaf nodes).
1131 */
1132template <typename Key, typename Value, typename BytesView, bool MtMode>
1133typename radix_tree<Key, Value, BytesView, MtMode>::atomic_pointer_type &
1135{
1136 if (is_leaf(n))
1137 return get_leaf(n)->parent;
1138
1139 return n->parent;
1140}
1141
1142/*
1143 * Find a leftmost leaf in a subtree of @param n.
1144 *
1145 * @param min_depth specifies minimum depth of the leaf. If the
1146 * tree is shorter than min_depth, a bottom leaf is returned.
1147 *
1148 * Can return nullptr if there is a conflicting, concurrent operation.
1149 */
1150template <typename Key, typename Value, typename BytesView, bool MtMode>
1151typename radix_tree<Key, Value, BytesView, MtMode>::leaf *
1152radix_tree<Key, Value, BytesView, MtMode>::any_leftmost_leaf(
1153 typename radix_tree<Key, Value, BytesView, MtMode>::pointer_type n,
1154 size_type min_depth) const
1155{
1156 assert(n);
1157
1158 while (n && !is_leaf(n)) {
1159 auto ne = load(n->embedded_entry);
1160 if (ne && n->byte >= min_depth)
1161 return get_leaf(ne);
1162
1163 pointer_type nn = nullptr;
1164 for (size_t i = 0; i < SLNODES; i++) {
1165 nn = load(n->child[i]);
1166 if (nn) {
1167 break;
1168 }
1169 }
1170
1171 n = nn;
1172 }
1173
1174 return n ? get_leaf(n) : nullptr;
1175}
1176
1177/*
1178 * Descends to the leaf that shares a common prefix with the @param key.
1179 * Returns a pair consisting of a pointer to above mentioned leaf and
1180 * object of type `path_type` which represents path to a divergence point.
1181 *
1182 * @param root_snap is a pointer to the root node (we pass it here because
1183 * loading it within this function might cause inconsistency if outer code
1184 * sees a different root.
1185 *
1186 * Can return nullptr if there is a conflicting, concurrent operation.
1187 */
1188template <typename Key, typename Value, typename BytesView, bool MtMode>
1189template <typename K>
1190std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::leaf *,
1191 typename radix_tree<Key, Value, BytesView, MtMode>::path_type>
1192radix_tree<Key, Value, BytesView, MtMode>::descend(pointer_type root_snap,
1193 const K &key) const
1194{
1195 assert(root_snap);
1196
1197 auto slot = &this->root;
1198 auto n = root_snap;
1199 decltype(n) prev = nullptr;
1200
1201 path_type path;
1202 path.reserve(PATH_INIT_CAP);
1203 path.push_back(node_desc{slot, n, prev});
1204
1205 while (n && !is_leaf(n) && n->byte < key.size()) {
1206 auto prev = n;
1207 slot = &n->child[slice_index(key[n->byte], n->bit)];
1208 auto nn = load(*slot);
1209
1210 if (nn) {
1211 path.push_back(node_desc{slot, nn, prev});
1212 n = nn;
1213 } else {
1214 path.push_back(node_desc{slot, nullptr, prev});
1215 n = any_leftmost_leaf(n, key.size());
1216 break;
1217 }
1218 }
1219
1220 if (!n)
1221 return {nullptr, std::move(path)};
1222
1223 /* This can happen when key is a prefix of some leaf or when the node at
1224 * which the keys diverge isn't a leaf */
1225 if (!is_leaf(n)) {
1226 n = any_leftmost_leaf(n, key.size());
1227 }
1228
1229 if (n) {
1230 return std::pair<leaf *, path_type>{get_leaf(n),
1231 std::move(path)};
1232 } else {
1233 return std::pair<leaf *, path_type>{nullptr, std::move(path)};
1234 }
1235}
1236
1237template <typename Key, typename Value, typename BytesView, bool MtMode>
1238template <typename K>
1239BytesView
1240radix_tree<Key, Value, BytesView, MtMode>::bytes_view(const K &key)
1241{
1242 /* bytes_view accepts const pointer instead of reference to make sure
1243 * there is no implicit conversion to a temporary type (and hence
1244 * dangling references). */
1245 return BytesView(&key);
1246}
1247
1248template <typename Key, typename Value, typename BytesView, bool MtMode>
1249string_view
1250radix_tree<Key, Value, BytesView, MtMode>::bytes_view(string_view key)
1251{
1252 return key;
1253}
1254
1255/*
1256 * Checks for key equality.
1257 */
1258template <typename Key, typename Value, typename BytesView, bool MtMode>
1259template <typename K1, typename K2>
1260bool
1261radix_tree<Key, Value, BytesView, MtMode>::keys_equal(const K1 &k1,
1262 const K2 &k2)
1263{
1264 return k1.size() == k2.size() && compare(k1, k2) == 0;
1265}
1266
1267/*
1268 * Checks for key equality.
1269 */
1270template <typename Key, typename Value, typename BytesView, bool MtMode>
1271template <typename K1, typename K2>
1272int
1273radix_tree<Key, Value, BytesView, MtMode>::compare(const K1 &k1, const K2 &k2,
1274 byten_t offset)
1275{
1276 auto ret = prefix_diff(k1, k2, offset);
1277
1278 if (ret != (std::min)(k1.size(), k2.size()))
1279 return (unsigned char)(k1[ret]) - (unsigned char)(k2[ret]);
1280
1281 return k1.size() - k2.size();
1282}
1283
1284/*
1285 * Returns length of common prefix of lhs and rhs.
1286 */
1287template <typename Key, typename Value, typename BytesView, bool MtMode>
1288template <typename K1, typename K2>
1289typename radix_tree<Key, Value, BytesView, MtMode>::byten_t
1290radix_tree<Key, Value, BytesView, MtMode>::prefix_diff(const K1 &lhs,
1291 const K2 &rhs,
1292 byten_t offset)
1293{
1294 byten_t diff;
1295 for (diff = offset; diff < (std::min)(lhs.size(), rhs.size()); diff++) {
1296 if (lhs[diff] != rhs[diff])
1297 return diff;
1298 }
1299
1300 return diff;
1301}
1302
1303/*
1304 * Checks whether length of the path from root to n is equal
1305 * to key_size.
1306 */
1307template <typename Key, typename Value, typename BytesView, bool MtMode>
1308bool
1309radix_tree<Key, Value, BytesView, MtMode>::path_length_equal(size_t key_size,
1310 pointer_type n)
1311{
1312 return n->byte == key_size && n->bit == bitn_t(FIRST_NIB);
1313}
1314
1315template <typename Key, typename Value, typename BytesView, bool MtMode>
1316template <typename K1, typename K2>
1317typename radix_tree<Key, Value, BytesView, MtMode>::bitn_t
1318radix_tree<Key, Value, BytesView, MtMode>::bit_diff(const K1 &leaf_key,
1319 const K2 &key, byten_t diff)
1320{
1321 auto min_key_len = (std::min)(leaf_key.size(), key.size());
1322 bitn_t sh = 8;
1323
1324 /* If key differs from leaf_key at some point (neither is a prefix of
1325 * another) we will descend to the point of divergence. Otherwise we
1326 * will look for a node which represents the prefix. */
1327 if (diff < min_key_len) {
1328 auto at =
1329 static_cast<unsigned char>(leaf_key[diff] ^ key[diff]);
1330 sh = pmem::detail::mssb_index((uint32_t)at) & SLICE_MASK;
1331 }
1332
1333 return sh;
1334}
1335
1336/*
1337 * Follows path saved in @param path until appropriate node is found
1338 * (for which @param diff and @param sh matches with byte and bit).
1339 */
1340template <typename Key, typename Value, typename BytesView, bool MtMode>
1341typename radix_tree<Key, Value, BytesView, MtMode>::node_desc
1342radix_tree<Key, Value, BytesView, MtMode>::follow_path(const path_type &path,
1343 byten_t diff,
1344 bitn_t sh) const
1345{
1346 assert(path.size());
1347
1348 auto idx = 0ULL;
1349 auto n = path[idx];
1350
1351 while (n.node && !is_leaf(n.node) &&
1352 (n.node->byte < diff ||
1353 (n.node->byte == diff && n.node->bit >= sh))) {
1354
1355 idx++;
1356 assert(idx < path.size());
1357
1358 n = path[idx];
1359 }
1360
1361 return n;
1362}
1363
1364template <typename Key, typename Value, typename BytesView, bool MtMode>
1365template <typename K, typename F, class... Args>
1366std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1367radix_tree<Key, Value, BytesView, MtMode>::internal_emplace(const K &k,
1368 F &&make_leaf)
1369{
1370 auto key = bytes_view(k);
1371 auto pop = pool_base(pmemobj_pool_by_ptr(this));
1372
1373 auto r = load(root);
1374 if (!r) {
1375 pointer_type leaf;
1376 flat_transaction::run(pop, [&] {
1377 leaf = make_leaf(nullptr);
1378 store(this->root, leaf);
1379 });
1380 return {iterator(get_leaf(leaf), this), true};
1381 }
1382
1383 /*
1384 * Need to descend the tree twice. First to find a leaf that
1385 * represents a subtree that shares a common prefix with the key.
1386 * This is needed to find out the actual labels between nodes (they
1387 * are not known due to a possible path compression). Second time to
1388 * find the place for the new element.
1389 */
1390 auto ret = descend(r, key);
1391 auto leaf = ret.first;
1392 auto path = ret.second;
1393
1394 assert(leaf);
1395
1396 auto leaf_key = bytes_view(leaf->key());
1397 auto diff = prefix_diff(key, leaf_key);
1398 auto sh = bit_diff(leaf_key, key, diff);
1399
1400 /* Key exists. */
1401 if (diff == key.size() && leaf_key.size() == key.size())
1402 return {iterator(leaf, this), false};
1403
1404 /* Descend the tree again by following the path. */
1405 auto node_d = follow_path(path, diff, sh);
1406 auto slot = const_cast<atomic_pointer_type *>(node_d.slot);
1407 auto prev = node_d.prev;
1408 auto n = node_d.node;
1409
1410 /*
1411 * If the divergence point is at same nib as an existing node, and
1412 * the subtree there is empty, just place our leaf there and we're
1413 * done. Obviously this can't happen if SLICE == 1.
1414 */
1415 if (!n) {
1416 assert(diff < (std::min)(leaf_key.size(), key.size()));
1417
1419 [&] { store(*slot, make_leaf(prev)); });
1420 return {iterator(get_leaf(load(*slot)), this), true};
1421 }
1422
1423 /* New key is a prefix of the leaf key or they are equal. We need to add
1424 * leaf ptr to internal node. */
1425 if (diff == key.size()) {
1426 if (!is_leaf(n) && path_length_equal(key.size(), n)) {
1427 assert(!load(n->embedded_entry));
1428
1429 flat_transaction::run(pop, [&] {
1430 store(n->embedded_entry, make_leaf(n));
1431 });
1432
1433 return {iterator(get_leaf(load(n->embedded_entry)),
1434 this),
1435 true};
1436 }
1437
1438 /* Path length from root to n is longer than key.size().
1439 * We have to allocate new internal node above n. */
1440 pointer_type node;
1441 flat_transaction::run(pop, [&] {
1442 node = make_persistent<radix_tree::node>(
1443 load(parent_ref(n)), diff, bitn_t(FIRST_NIB));
1444 store(node->embedded_entry, make_leaf(node));
1445 store(node->child[slice_index(leaf_key[diff],
1446 bitn_t(FIRST_NIB))],
1447 n);
1448
1449 store(parent_ref(n), node);
1450 store(*slot, node);
1451 });
1452
1453 return {iterator(get_leaf(load(node->embedded_entry)), this),
1454 true};
1455 }
1456
1457 if (diff == leaf_key.size()) {
1458 /* Leaf key is a prefix of the new key. We need to convert leaf
1459 * to a node. */
1460 pointer_type node;
1461 flat_transaction::run(pop, [&] {
1462 /* We have to add new node at the edge from parent to n
1463 */
1464 node = make_persistent<radix_tree::node>(
1465 load(parent_ref(n)), diff, bitn_t(FIRST_NIB));
1466 store(node->embedded_entry, n);
1467 store(node->child[slice_index(key[diff],
1468 bitn_t(FIRST_NIB))],
1469 make_leaf(node));
1470
1471 store(parent_ref(n), node);
1472 store(*slot, node);
1473 });
1474
1475 return {iterator(get_leaf(load(node->child[slice_index(
1476 key[diff], bitn_t(FIRST_NIB))])),
1477 this),
1478 true};
1479 }
1480
1481 /* There is already a subtree at the divergence point
1482 * (slice_index(key[diff], sh)). This means that a tree is vertically
1483 * compressed and we have to "break" this compression and add a new
1484 * node. */
1485 pointer_type node;
1486 flat_transaction::run(pop, [&] {
1487 node = make_persistent<radix_tree::node>(load(parent_ref(n)),
1488 diff, sh);
1489 store(node->child[slice_index(leaf_key[diff], sh)], n);
1490 store(node->child[slice_index(key[diff], sh)], make_leaf(node));
1491
1492 store(parent_ref(n), node);
1493 store(*slot, node);
1494 });
1495
1496 return {iterator(
1497 get_leaf(load(node->child[slice_index(key[diff], sh)])),
1498 this),
1499 true};
1500}
1501
1530template <typename Key, typename Value, typename BytesView, bool MtMode>
1531template <class... Args>
1532std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1534 Args &&... args)
1535{
1536 return internal_emplace(k, [&](pointer_type parent) {
1537 size_++;
1538 return leaf::make_key_args(parent, k,
1539 std::forward<Args>(args)...);
1540 });
1541}
1542
1569template <typename Key, typename Value, typename BytesView, bool MtMode>
1570template <class... Args>
1571std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1573{
1574 auto pop = pool_base(pmemobj_pool_by_ptr(this));
1575 std::pair<iterator, bool> ret;
1576
1577 flat_transaction::run(pop, [&] {
1578 auto leaf_ = leaf::make(nullptr, std::forward<Args>(args)...);
1579 auto make_leaf = [&](pointer_type parent) {
1580 store(leaf_->parent, parent);
1581 size_++;
1582 return leaf_;
1583 };
1584
1585 ret = internal_emplace(leaf_->key(), make_leaf);
1586
1587 if (!ret.second)
1588 delete_persistent<leaf>(leaf_);
1589 });
1590
1591 return ret;
1592}
1593
1609template <typename Key, typename Value, typename BytesView, bool MtMode>
1610std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1612{
1613 return try_emplace(v.first, v.second);
1614}
1615
1631template <typename Key, typename Value, typename BytesView, bool MtMode>
1632std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1634{
1635 return try_emplace(std::move(v.first), std::move(v.second));
1636}
1637
1657template <typename Key, typename Value, typename BytesView, bool MtMode>
1658template <typename P, typename>
1659std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1661{
1662 return emplace(std::forward<P>(p));
1663}
1664
1676template <typename Key, typename Value, typename BytesView, bool MtMode>
1677template <typename InputIterator>
1678void
1680 InputIterator last)
1681{
1682 for (auto it = first; it != last; it++)
1683 try_emplace((*it).first, (*it).second);
1684}
1685
1696template <typename Key, typename Value, typename BytesView, bool MtMode>
1697void
1699 std::initializer_list<value_type> il)
1700{
1701 insert(il.begin(), il.end());
1702}
1703
1728template <typename Key, typename Value, typename BytesView, bool MtMode>
1729template <class... Args>
1730std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1732 Args &&... args)
1733{
1734 return internal_emplace(k, [&](pointer_type parent) {
1735 size_++;
1736 return leaf::make_key_args(parent, std::move(k),
1737 std::forward<Args>(args)...);
1738 });
1739}
1740
1769template <typename Key, typename Value, typename BytesView, bool MtMode>
1770template <typename K, typename BV, class... Args>
1771auto
1773 -> typename std::enable_if<
1774 detail::has_is_transparent<BV>::value &&
1775 !std::is_same<typename std::remove_const<
1776 typename std::remove_reference<
1777 K>::type>::type,
1778 key_type>::value,
1779 std::pair<typename radix_tree<Key, Value, BytesView,
1780 MtMode>::iterator,
1781 bool>>::type
1782
1783{
1784 return internal_emplace(k, [&](pointer_type parent) {
1785 size_++;
1786 return leaf::make_key_args(parent, std::forward<K>(k),
1787 std::forward<Args>(args)...);
1788 });
1789}
1790
1809template <typename Key, typename Value, typename BytesView, bool MtMode>
1810template <typename M>
1811std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1813 M &&obj)
1814{
1815 auto ret = try_emplace(k, std::forward<M>(obj));
1816 if (!ret.second)
1817 ret.first.assign_val(std::forward<M>(obj));
1818 return ret;
1819}
1820
1839template <typename Key, typename Value, typename BytesView, bool MtMode>
1840template <typename M>
1841std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1843 M &&obj)
1844{
1845 auto ret = try_emplace(std::move(k), std::forward<M>(obj));
1846 if (!ret.second)
1847 ret.first.assign_val(std::forward<M>(obj));
1848 return ret;
1849}
1850
1872template <typename Key, typename Value, typename BytesView, bool MtMode>
1873template <typename M, typename K, typename>
1874std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator, bool>
1876{
1877 auto ret = try_emplace(std::forward<K>(k), std::forward<M>(obj));
1878 if (!ret.second)
1879 ret.first.assign_val(std::forward<M>(obj));
1880 return ret;
1881}
1882
1892template <typename Key, typename Value, typename BytesView, bool MtMode>
1893typename radix_tree<Key, Value, BytesView, MtMode>::size_type
1895{
1896 return internal_find(k) != nullptr ? 1 : 0;
1897}
1898
1911template <typename Key, typename Value, typename BytesView, bool MtMode>
1912template <typename K, typename>
1913typename radix_tree<Key, Value, BytesView, MtMode>::size_type
1915{
1916 return internal_find(k) != nullptr ? 1 : 0;
1917}
1918
1927template <typename Key, typename Value, typename BytesView, bool MtMode>
1930{
1931 return iterator(internal_find(k), this);
1932}
1933
1942template <typename Key, typename Value, typename BytesView, bool MtMode>
1945{
1946 return const_iterator(internal_find(k), this);
1947}
1948
1960template <typename Key, typename Value, typename BytesView, bool MtMode>
1961template <typename K, typename>
1964{
1965 return iterator(internal_find(k), this);
1966}
1967
1979template <typename Key, typename Value, typename BytesView, bool MtMode>
1980template <typename K, typename>
1983{
1984 return const_iterator(internal_find(k), this);
1985}
1986
1987template <typename Key, typename Value, typename BytesView, bool MtMode>
1988template <typename K>
1991{
1992 auto key = bytes_view(k);
1993
1994 auto n = load(root);
1995 while (n && !is_leaf(n)) {
1996 if (path_length_equal(key.size(), n))
1997 n = load(n->embedded_entry);
1998 else if (n->byte >= key.size())
1999 return nullptr;
2000 else
2001 n = load(n->child[slice_index(key[n->byte], n->bit)]);
2002 }
2003
2004 if (!n)
2005 return nullptr;
2006
2007 if (!keys_equal(key, bytes_view(get_leaf(n)->key())))
2008 return nullptr;
2009
2010 return get_leaf(n);
2011}
2012
2020template <typename Key, typename Value, typename BytesView, bool MtMode>
2021void
2023{
2024 if (size() != 0)
2025 erase(begin(), end());
2026}
2027
2043template <typename Key, typename Value, typename BytesView, bool MtMode>
2046{
2047 auto pop = pool_base(pmemobj_pool_by_ptr(this));
2048
2049 flat_transaction::run(pop, [&] {
2050 auto *leaf = pos.leaf_;
2051 auto parent = load(leaf->parent);
2052
2053 /* there are more elements in the container */
2054 if (parent)
2055 ++pos;
2056
2058
2059 size_--;
2060
2061 /* was root */
2062 if (!parent) {
2063 store(this->root, nullptr);
2064 pos = begin();
2065 return;
2066 }
2067
2068 /* It's safe to cast because we're inside non-const method. */
2069 store(const_cast<atomic_pointer_type &>(
2070 *parent->find_child(leaf)),
2071 nullptr);
2072
2073 /* Compress the tree vertically. */
2074 auto n = parent;
2075 parent = load(n->parent);
2076 pointer_type only_child = nullptr;
2077 for (size_t i = 0; i < SLNODES; i++) {
2078 if (load(n->child[i])) {
2079 if (only_child) {
2080 /* more than one child */
2081 return;
2082 }
2083 only_child = load(n->child[i]);
2084 }
2085 }
2086
2087 if (only_child && load(n->embedded_entry)) {
2088 /* There are actually 2 "children" so we can't compress.
2089 */
2090 return;
2091 } else if (load(n->embedded_entry)) {
2092 only_child = load(n->embedded_entry);
2093 }
2094
2095 assert(only_child);
2096 store(parent_ref(only_child), load(n->parent));
2097
2098 auto *child_slot = parent ? const_cast<atomic_pointer_type *>(
2099 &*parent->find_child(n))
2100 : &root;
2101 store(*child_slot, only_child);
2102
2103 free(persistent_ptr<radix_tree::node>(get_node(n)));
2104 });
2105
2106 return iterator(const_cast<typename iterator::leaf_ptr>(pos.leaf_),
2107 this);
2108}
2109
2123template <typename Key, typename Value, typename BytesView, bool MtMode>
2126 const_iterator last)
2127{
2128 auto pop = pool_base(pmemobj_pool_by_ptr(this));
2129
2130 flat_transaction::run(pop, [&] {
2131 while (first != last)
2132 first = erase(first);
2133 });
2134
2135 return iterator(const_cast<typename iterator::leaf_ptr>(first.leaf_),
2136 this);
2137}
2138
2151template <typename Key, typename Value, typename BytesView, bool MtMode>
2152typename radix_tree<Key, Value, BytesView, MtMode>::size_type
2154{
2155 auto it = const_iterator(internal_find(k), this);
2156
2157 if (it == end())
2158 return 0;
2159
2160 erase(it);
2161
2162 return 1;
2163}
2164
2179template <typename Key, typename Value, typename BytesView, bool MtMode>
2180template <typename K, typename>
2181typename radix_tree<Key, Value, BytesView, MtMode>::size_type
2183{
2184 auto it = const_iterator(internal_find(k), this);
2185
2186 if (it == end())
2187 return 0;
2188
2189 erase(it);
2190
2191 return 1;
2192}
2193
2198template <typename Key, typename Value, typename BytesView, bool MtMode>
2199template <typename T>
2200void
2202{
2203 if (MtMode && ebr_ != nullptr)
2204 garbages[ebr_->staging_epoch()].emplace_back(ptr);
2205 else
2206 delete_persistent<T>(ptr);
2207}
2208
2213template <typename Key, typename Value, typename BytesView, bool MtMode>
2214template <bool Lower, typename K>
2215bool
2217 const K &key) const
2218{
2219 if (it == cend())
2220 return true;
2221
2222 if (Lower)
2223 return (compare(bytes_view(it->key()), bytes_view(key)) >= 0);
2224
2225 return (compare(bytes_view(it->key()), bytes_view(key)) > 0);
2226}
2227
2231template <typename Key, typename Value, typename BytesView, bool MtMode>
2232template <bool Mt>
2233typename std::enable_if<Mt, bool>::type
2235 const path_type &path) const
2236{
2237 for (auto i = 0ULL; i < path.size(); i++) {
2238 if (path[i].node != load(*path[i].slot))
2239 return false;
2240
2241 if (path[i].node &&
2242 load(parent_ref(path[i].node)) != path[i].prev)
2243 return false;
2244 }
2245
2246 return true;
2247}
2248
2249template <typename Key, typename Value, typename BytesView, bool MtMode>
2250template <bool Mt>
2251typename std::enable_if<!Mt, bool>::type
2253 const path_type &path) const
2254{
2255 return true;
2256}
2257
2258template <typename Key, typename Value, typename BytesView, bool MtMode>
2259template <bool Lower, typename K>
2260typename radix_tree<Key, Value, BytesView, MtMode>::const_iterator
2261radix_tree<Key, Value, BytesView, MtMode>::internal_bound(const K &k) const
2262{
2263 auto key = bytes_view(k);
2264 auto pop = pool_base(pmemobj_pool_by_ptr(this));
2265
2266 path_type path;
2267 const_iterator result;
2268
2269 while (true) {
2270 auto r = load(root);
2271
2272 if (!r)
2273 return end();
2274
2275 /*
2276 * Need to descend the tree twice. First to find a leaf that
2277 * represents a subtree that shares a common prefix with the
2278 * key. This is needed to find out the actual labels between
2279 * nodes (they are not known due to a possible path
2280 * compression). Second time to get the actual element.
2281 */
2282 auto ret = descend(r, key);
2283 auto leaf = ret.first;
2284 path = ret.second;
2285
2286 if (!leaf)
2287 continue;
2288
2289 auto leaf_key = bytes_view(leaf->key());
2290 auto diff = prefix_diff(key, leaf_key);
2291 auto sh = bit_diff(leaf_key, key, diff);
2292
2293 /* Key exists. */
2294 if (diff == key.size() && leaf_key.size() == key.size()) {
2295 result = const_iterator(leaf, this);
2296
2297 /* For lower_bound, result is looked-for element. */
2298 if (Lower)
2299 break;
2300
2301 /* For upper_bound, we need to find larger element. */
2302 if (result.try_increment())
2303 break;
2304
2305 continue;
2306 }
2307
2308 /* Descend the tree again by following the path. */
2309 auto node_d = follow_path(path, diff, sh);
2310
2311 auto n = node_d.node;
2312 auto slot = node_d.slot;
2313 auto prev = node_d.prev;
2314
2315 if (!n) {
2316 /*
2317 * n would point to element with key which we are
2318 * looking for (if it existed). All elements on the left
2319 * are smaller and all element on the right are bigger.
2320 */
2321 assert(prev && !is_leaf(prev));
2322
2323 auto target_leaf = next_leaf<node::direction::Forward>(
2324 prev->template make_iterator<
2325 node::direction::Forward>(slot),
2326 prev);
2327
2328 if (!target_leaf.first)
2329 continue;
2330
2331 result = const_iterator(target_leaf.second, this);
2332 } else if (diff == key.size()) {
2333 /* The looked-for key is a prefix of the leaf key. The
2334 * target node must be the smallest leaf within *slot's
2335 * subtree. Key represented by a path from root to n is
2336 * larger than the looked-for key. Additionally keys
2337 * under right siblings of *slot are > key and keys
2338 * under left siblings are < key. */
2339 auto target_leaf =
2340 find_leaf<node::direction::Forward>(n);
2341
2342 if (!target_leaf)
2343 continue;
2344
2345 result = const_iterator(target_leaf, this);
2346 } else if (diff == leaf_key.size()) {
2347 assert(n == leaf);
2348
2349 if (!prev) {
2350 /* There is only one element in the tree and
2351 * it's smaller. */
2352 result = cend();
2353 } else {
2354 /* Leaf's key is a prefix of the looked-for key.
2355 * Leaf's key is the biggest key less than the
2356 * looked-for key. The target node must be the
2357 * next leaf. Note that we cannot just call
2358 * const_iterator(leaf, this).try_increment()
2359 * because some other element with key larger
2360 * than leaf and smaller than k could be
2361 * inserted concurrently. */
2362 auto target_leaf = next_leaf<
2363 node::direction::Forward>(
2364 prev->template make_iterator<
2365 node::direction::Forward>(slot),
2366 prev);
2367
2368 if (!target_leaf.first)
2369 continue;
2370
2371 result = const_iterator(target_leaf.second,
2372 this);
2373 }
2374 } else {
2375 assert(diff < leaf_key.size() && diff < key.size());
2376
2377 /* *slot is the point of divergence. It means the tree
2378 * is compressed.
2379 *
2380 * Example for key AXXB or AZZB
2381 * ROOT
2382 * / \
2383 * A B
2384 * / \
2385 * *slot ...
2386 * / \
2387 * YYA YYC
2388 * / \
2389 * ... ...
2390 *
2391 * We need to compare the first bytes of key and
2392 * leaf_key to decide where to continue our search (for
2393 * AXXB we would compare X with Y).
2394 */
2395
2396 /* If next byte in key is less than in leaf_key it means
2397 * that the target node must be within *slot's subtree.
2398 * The left siblings of *slot are all less than the
2399 * looked-for key (this is the case fo AXXB from the
2400 * example above). */
2401 if (static_cast<unsigned char>(key[diff]) <
2402 static_cast<unsigned char>(leaf_key[diff])) {
2403 auto target_leaf =
2404 find_leaf<node::direction::Forward>(n);
2405
2406 if (!target_leaf)
2407 continue;
2408
2409 result = const_iterator(target_leaf, this);
2410 } else if (slot == &root) {
2411 result = const_iterator(nullptr, this);
2412 } else {
2413 assert(prev);
2414 assert(static_cast<unsigned char>(key[diff]) >
2415 static_cast<unsigned char>(
2416 leaf_key[diff]));
2417
2418 /* Since next byte in key is greater
2419 * than in leaf_key, the target node
2420 * must be within subtree of a right
2421 * sibling of *slot. All leaves in the
2422 * subtree under *slot are smaller than
2423 * key (this is the case of AZZB). This
2424 * is because the tree is compressed so
2425 * all nodes under *slot share common prefix
2426 * ("YY" in the example above) - leaf_key[diff]
2427 * is the same for all keys under *slot. */
2428 auto target_leaf = next_leaf<
2429 node::direction::Forward>(
2430 prev->template make_iterator<
2431 node::direction::Forward>(slot),
2432 prev);
2433
2434 if (!target_leaf.first)
2435 continue;
2436
2437 result = const_iterator(target_leaf.second,
2438 this);
2439 }
2440 }
2441
2442 /* If some node on the path was modified, the calculated result
2443 * might not be correct. */
2444 if (validate_path(path))
2445 break;
2446 }
2447
2448 assert(validate_bound<Lower>(result, k));
2449
2450 return result;
2451}
2452
2463template <typename Key, typename Value, typename BytesView, bool MtMode>
2464typename radix_tree<Key, Value, BytesView, MtMode>::const_iterator
2466{
2467 return internal_bound<true>(k);
2468}
2469
2480template <typename Key, typename Value, typename BytesView, bool MtMode>
2483{
2484 auto it = const_cast<const radix_tree *>(this)->lower_bound(k);
2485 return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2486 this);
2487}
2488
2502template <typename Key, typename Value, typename BytesView, bool MtMode>
2503template <typename K, typename>
2506{
2507 auto it = const_cast<const radix_tree *>(this)->lower_bound(k);
2508 return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2509 this);
2510}
2511
2525template <typename Key, typename Value, typename BytesView, bool MtMode>
2526template <typename K, typename>
2529{
2530 return internal_bound<true>(k);
2531}
2532
2543template <typename Key, typename Value, typename BytesView, bool MtMode>
2546{
2547 return internal_bound<false>(k);
2548}
2549
2560template <typename Key, typename Value, typename BytesView, bool MtMode>
2563{
2564 auto it = const_cast<const radix_tree *>(this)->upper_bound(k);
2565 return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2566 this);
2567}
2568
2582template <typename Key, typename Value, typename BytesView, bool MtMode>
2583template <typename K, typename>
2586{
2587 auto it = const_cast<const radix_tree *>(this)->upper_bound(k);
2588 return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2589 this);
2590}
2591
2605template <typename Key, typename Value, typename BytesView, bool MtMode>
2606template <typename K, typename>
2609{
2610 return internal_bound<false>(k);
2611}
2612
2619template <typename Key, typename Value, typename BytesView, bool MtMode>
2622{
2623 auto const_begin = const_cast<const radix_tree *>(this)->begin();
2624 return iterator(
2625 const_cast<typename iterator::leaf_ptr>(const_begin.leaf_),
2626 this);
2627}
2628
2636template <typename Key, typename Value, typename BytesView, bool MtMode>
2639{
2640 auto const_end = const_cast<const radix_tree *>(this)->end();
2641 return iterator(
2642 const_cast<typename iterator::leaf_ptr>(const_end.leaf_), this);
2643}
2644
2651template <typename Key, typename Value, typename BytesView, bool MtMode>
2654{
2655 while (true) {
2656 auto root_ptr = load(root);
2657 if (!root_ptr)
2658 return const_iterator(nullptr, this);
2659
2660 auto leaf = find_leaf<radix_tree::node::direction::Forward>(
2661 root_ptr);
2662 if (leaf) {
2663 return const_iterator(leaf, this);
2664 }
2665 }
2666}
2667
2675template <typename Key, typename Value, typename BytesView, bool MtMode>
2678{
2679 return const_iterator(nullptr, this);
2680}
2681
2688template <typename Key, typename Value, typename BytesView, bool MtMode>
2691{
2692 return cbegin();
2693}
2694
2702template <typename Key, typename Value, typename BytesView, bool MtMode>
2705{
2706 return cend();
2707}
2708
2716template <typename Key, typename Value, typename BytesView, bool MtMode>
2717typename radix_tree<Key, Value, BytesView, MtMode>::reverse_iterator
2719{
2720 return reverse_iterator(end());
2721}
2722
2731template <typename Key, typename Value, typename BytesView, bool MtMode>
2732typename radix_tree<Key, Value, BytesView, MtMode>::reverse_iterator
2734{
2735 return reverse_iterator(begin());
2736}
2737
2745template <typename Key, typename Value, typename BytesView, bool MtMode>
2746typename radix_tree<Key, Value, BytesView, MtMode>::const_reverse_iterator
2748{
2749 return const_reverse_iterator(cend());
2750}
2751
2760template <typename Key, typename Value, typename BytesView, bool MtMode>
2761typename radix_tree<Key, Value, BytesView, MtMode>::const_reverse_iterator
2763{
2764 return const_reverse_iterator(cbegin());
2765}
2766
2767template <typename Key, typename Value, typename BytesView, bool MtMode>
2768typename radix_tree<Key, Value, BytesView, MtMode>::const_reverse_iterator
2770{
2771 return const_reverse_iterator(cend());
2772}
2773
2774template <typename Key, typename Value, typename BytesView, bool MtMode>
2775typename radix_tree<Key, Value, BytesView, MtMode>::const_reverse_iterator
2777{
2778 return const_reverse_iterator(cbegin());
2779}
2780
2781template <typename Key, typename Value, typename BytesView, bool MtMode>
2782void
2783radix_tree<Key, Value, BytesView, MtMode>::print_rec(std::ostream &os,
2784 radix_tree::pointer_type n)
2785{
2786 if (!is_leaf(n)) {
2787 os << "\"" << get_node(n) << "\""
2788 << " [style=filled,color=\"blue\"]" << std::endl;
2789 os << "\"" << get_node(n) << "\" [label=\"byte:" << n->byte
2790 << ", bit:" << int(n->bit) << "\"]" << std::endl;
2791
2792 auto p = load(n->parent);
2793 auto parent = p ? get_node(p) : 0;
2794 os << "\"" << get_node(n) << "\" -> "
2795 << "\"" << parent << "\" [label=\"parent\"]" << std::endl;
2796
2797 for (auto it = n->begin(); it != n->end(); ++it) {
2798 auto c = load(*it);
2799
2800 if (!c)
2801 continue;
2802
2803 auto ch = is_leaf(c) ? (void *)get_leaf(c)
2804 : (void *)get_node(c);
2805
2806 os << "\"" << get_node(n) << "\" -> \"" << ch << "\""
2807 << std::endl;
2808 print_rec(os, c);
2809 }
2810 } else {
2811 auto bv = bytes_view(get_leaf(n)->key());
2812
2813 os << "\"" << get_leaf(n) << "\" [style=filled,color=\"green\"]"
2814 << std::endl;
2815 os << "\"" << get_leaf(n) << "\" [label=\"key:";
2816
2817 for (size_t i = 0; i < bv.size(); i++)
2818 os << bv[i];
2819
2820 os << "\"]" << std::endl;
2821
2822 auto p = load(get_leaf(n)->parent);
2823 auto parent = p ? get_node(p) : nullptr;
2824
2825 os << "\"" << get_leaf(n) << "\" -> \"" << parent
2826 << "\" [label=\"parent\"]" << std::endl;
2827
2828 if (parent && n == load(parent->embedded_entry)) {
2829 os << "{rank=same;\"" << parent << "\";\""
2830 << get_leaf(n) << "\"}" << std::endl;
2831 }
2832 }
2833}
2834
2838template <typename K, typename V, typename BV, bool MtMode>
2839std::ostream &
2840operator<<(std::ostream &os, const radix_tree<K, V, BV, MtMode> &tree)
2841{
2842 os << "digraph Radix {" << std::endl;
2843
2846 os, radix_tree<K, V, BV, MtMode>::load(tree.root));
2847
2848 os << "}" << std::endl;
2849
2850 return os;
2851}
2852
2853/*
2854 * internal: slice_index -- return index of child at the given nib
2855 */
2856template <typename Key, typename Value, typename BytesView, bool MtMode>
2857unsigned
2858radix_tree<Key, Value, BytesView, MtMode>::slice_index(char b, uint8_t bit)
2859{
2860 return static_cast<unsigned>(b >> bit) & NIB;
2861}
2862
2863template <typename Key, typename Value, typename BytesView, bool MtMode>
2864radix_tree<Key, Value, BytesView,
2865 MtMode>::node::forward_iterator::forward_iterator(pointer child,
2866 const node *n)
2867 : child(child), n(n)
2868{
2869}
2870
2871template <typename Key, typename Value, typename BytesView, bool MtMode>
2872typename radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator
2873radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator::operator++()
2874{
2875 if (child == &n->embedded_entry)
2876 child = &n->child[0];
2877 else
2878 child++;
2879
2880 return *this;
2881}
2882
2883template <typename Key, typename Value, typename BytesView, bool MtMode>
2884radix_tree<Key, Value, BytesView, MtMode>::node::node(pointer_type parent,
2885 byten_t byte, bitn_t bit)
2886 : parent(parent), byte(byte), bit(bit)
2887{
2888}
2889
2890template <typename Key, typename Value, typename BytesView, bool MtMode>
2891typename radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator
2892radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator::operator--()
2893{
2894 if (child == &n->child[0])
2895 child = &n->embedded_entry;
2896 else
2897 child--;
2898
2899 return *this;
2900}
2901
2902template <typename Key, typename Value, typename BytesView, bool MtMode>
2903typename radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator
2904radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator::operator++(
2905 int)
2906{
2907 forward_iterator tmp(child, n);
2908 operator++();
2909 return tmp;
2910}
2911
2912template <typename Key, typename Value, typename BytesView, bool MtMode>
2913typename radix_tree<Key, Value, BytesView,
2914 MtMode>::node::forward_iterator::reference
2915 radix_tree<Key, Value, BytesView,
2916 MtMode>::node::forward_iterator::operator*() const
2917{
2918 return *child;
2919}
2920
2921template <typename Key, typename Value, typename BytesView, bool MtMode>
2922typename radix_tree<Key, Value, BytesView,
2923 MtMode>::node::forward_iterator::pointer
2924 radix_tree<Key, Value, BytesView,
2925 MtMode>::node::forward_iterator::operator->() const
2926{
2927 return child;
2928}
2929
2930template <typename Key, typename Value, typename BytesView, bool MtMode>
2931typename radix_tree<Key, Value, BytesView,
2932 MtMode>::node::forward_iterator::pointer
2933radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator::get_node()
2934 const
2935{
2936 return n;
2937}
2938
2939template <typename Key, typename Value, typename BytesView, bool MtMode>
2940bool
2941radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator::operator==(
2942 const forward_iterator &rhs) const
2943{
2944 return child == rhs.child && n == rhs.n;
2945}
2946
2947template <typename Key, typename Value, typename BytesView, bool MtMode>
2948bool
2949radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator::operator!=(
2950 const forward_iterator &rhs) const
2951{
2952 return child != rhs.child || n != rhs.n;
2953}
2954
2955template <typename Key, typename Value, typename BytesView, bool MtMode>
2956template <bool Direction>
2957typename std::enable_if<Direction ==
2958 radix_tree<Key, Value, BytesView,
2959 MtMode>::node::direction::Forward,
2960 typename radix_tree<Key, Value, BytesView, MtMode>::
2961 node::forward_iterator>::type
2962radix_tree<Key, Value, BytesView, MtMode>::node::begin() const
2963{
2964 return forward_iterator(&embedded_entry, this);
2965}
2966
2967template <typename Key, typename Value, typename BytesView, bool MtMode>
2968template <bool Direction>
2969typename std::enable_if<Direction ==
2970 radix_tree<Key, Value, BytesView,
2971 MtMode>::node::direction::Forward,
2972 typename radix_tree<Key, Value, BytesView, MtMode>::
2973 node::forward_iterator>::type
2974radix_tree<Key, Value, BytesView, MtMode>::node::end() const
2975{
2976 return forward_iterator(&child[SLNODES], this);
2977}
2978
2979template <typename Key, typename Value, typename BytesView, bool MtMode>
2980template <bool Direction>
2981typename std::enable_if<Direction ==
2982 radix_tree<Key, Value, BytesView,
2983 MtMode>::node::direction::Reverse,
2984 typename radix_tree<Key, Value, BytesView, MtMode>::
2985 node::reverse_iterator>::type
2986radix_tree<Key, Value, BytesView, MtMode>::node::begin() const
2987{
2988 return reverse_iterator(end<direction::Forward>());
2989}
2990
2991template <typename Key, typename Value, typename BytesView, bool MtMode>
2992template <bool Direction>
2993typename std::enable_if<Direction ==
2994 radix_tree<Key, Value, BytesView,
2995 MtMode>::node::direction::Reverse,
2996 typename radix_tree<Key, Value, BytesView, MtMode>::
2997 node::reverse_iterator>::type
2998radix_tree<Key, Value, BytesView, MtMode>::node::end() const
2999{
3000 return reverse_iterator(begin<direction::Forward>());
3001}
3002
3003template <typename Key, typename Value, typename BytesView, bool MtMode>
3004template <bool Direction, typename Ptr>
3005typename radix_tree<Key, Value, BytesView,
3006 MtMode>::node::template iterator<Direction>
3007radix_tree<Key, Value, BytesView, MtMode>::node::find_child(const Ptr &n) const
3008{
3009 auto it = begin<Direction>();
3010 while (it != end<Direction>()) {
3011 if (load(*it) == n)
3012 return it;
3013 ++it;
3014 }
3015 return it;
3016}
3017
3018template <typename Key, typename Value, typename BytesView, bool MtMode>
3019template <bool Direction, typename Enable>
3020typename radix_tree<Key, Value, BytesView,
3021 MtMode>::node::template iterator<Direction>
3022radix_tree<Key, Value, BytesView, MtMode>::node::make_iterator(
3023 const atomic_pointer_type *ptr) const
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,
3110 MtMode>::radix_tree_iterator<IsConst>::replace_val(T &&rhs)
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,
3148 MtMode>::radix_tree_iterator<IsConst>::assign_val(T &&rhs)
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,
3164 MtMode>::radix_tree_iterator<IsConst>::operator++()
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:2762
const_iterator cbegin() const
Returns a const iterator to the first element of the container.
Definition: radix_tree.hpp:2653
void runtime_finalize_mt()
If MtMode == true, this function must be called before each application close and before calling radi...
Definition: radix_tree.hpp:1103
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:2216
reverse_iterator rend()
Returns a reverse iterator to the end.
Definition: radix_tree.hpp:2733
void swap(radix_tree &rhs)
Member swap.
Definition: radix_tree.hpp:973
iterator begin()
Returns an iterator to the first element of the container.
Definition: radix_tree.hpp:2621
const_reverse_iterator crbegin() const
Returns a const, reverse iterator to the beginning.
Definition: radix_tree.hpp:2747
uint64_t size() const noexcept
Definition: radix_tree.hpp:961
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:2638
void runtime_initialize_mt(ebr *e=new ebr())
If MtMode == true, this function must be called after each application restart.
Definition: radix_tree.hpp:1088
bool empty() const noexcept
Checks whether the container is empty.
Definition: radix_tree.hpp:941
size_type max_size() const noexcept
Definition: radix_tree.hpp:951
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:1611
reverse_iterator rbegin()
Returns a reverse iterator to the beginning.
Definition: radix_tree.hpp:2718
iterator erase(const_iterator pos)
Removes the element at pos from the container.
Definition: radix_tree.hpp:2045
worker_type register_worker()
Registers and returns a new worker, which can perform critical operations (accessing some shared data...
Definition: radix_tree.hpp:1122
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:2482
~radix_tree()
Destructor.
Definition: radix_tree.hpp:923
void clear()
Erases all elements from the container transactionally.
Definition: radix_tree.hpp:2022
std::enable_if< Mt, bool >::type validate_path(const path_type &path) const
Checks if any node in the.
Definition: radix_tree.hpp:2234
iterator find(const key_type &k)
Finds an element with key equivalent to key.
Definition: radix_tree.hpp:1929
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:1016
radix_tree & operator=(const radix_tree &m)
Copy assignment operator.
Definition: radix_tree.hpp:836
iterator upper_bound(const key_type &k)
Returns an iterator pointing to the first element that is greater than key.
Definition: radix_tree.hpp:2562
void garbage_collect_force()
Performs full epochs synchronisation.
Definition: radix_tree.hpp:995
const_iterator cend() const
Returns a const iterator to the element following the last element of the map.
Definition: radix_tree.hpp:2677
void free(persistent_ptr< T > ptr)
Deletes node/leaf pointed by ptr.
Definition: radix_tree.hpp:2201
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:1894
radix_tree()
Default radix tree constructor.
Definition: radix_tree.hpp:715
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:2840
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
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
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:604
Commonly used SFINAE helpers.
C++ pmemobj transactions.
Libpmemobj C++ utils.
Volatile residing on pmem property template.