16#ifndef LIBPMEMOBJ_CPP_RADIX_HPP
17#define LIBPMEMOBJ_CPP_RADIX_HPP
21#include <libpmemobj++/detail/pair.hpp>
45#include <libpmemobj++/detail/tagged_ptr.hpp>
56template <
typename T,
typename Enable =
void>
118template <
typename Key,
typename Value,
typename BytesView =
bytes_view<Key>,
121 template <
bool IsConst>
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;
137 using worker_type = detail::ebr::worker;
141 template <
class InputIt>
145 radix_tree(std::initializer_list<value_type> il);
153 template <
class... Args>
154 std::pair<iterator, bool> emplace(Args &&... args);
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,
162 std::pair<iterator, bool>
insert(P &&
p);
170 template <
class InputIterator>
171 void insert(InputIterator first, InputIterator last);
172 void insert(std::initializer_list<value_type> il);
176 template <
class... Args>
177 std::pair<iterator, bool> try_emplace(
const key_type &k,
179 template <
class... Args>
180 std::pair<iterator, bool> try_emplace(key_type &&k, Args &&... args);
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<
195 std::pair<iterator, bool>>::type;
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);
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);
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,
221 size_type
erase(
const K &k);
225 size_type
count(
const key_type &k)
const;
228 typename =
typename std::enable_if<
229 detail::has_is_transparent<BytesView>::value, K>::type>
230 size_type
count(
const K &k)
const;
236 typename =
typename std::enable_if<
237 detail::has_is_transparent<BytesView>::value, K>::type>
241 typename =
typename std::enable_if<
242 detail::has_is_transparent<BytesView>::value, K>::type>
249 typename =
typename std::enable_if<
250 detail::has_is_transparent<BytesView>::value, K>::type>
254 typename =
typename std::enable_if<
255 detail::has_is_transparent<BytesView>::value, K>::type>
262 typename =
typename std::enable_if<
263 detail::has_is_transparent<BytesView>::value, K>::type>
267 typename =
typename std::enable_if<
268 detail::has_is_transparent<BytesView>::value, K>::type>
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;
286 bool empty()
const noexcept;
287 size_type
max_size()
const noexcept;
288 uint64_t
size()
const noexcept;
292 template <
typename K,
typename V,
typename BV,
bool Mt>
293 friend std::ostream &
operator<<(std::ostream &os,
296 template <
bool Mt = MtMode,
297 typename Enable =
typename std::enable_if<Mt>::type>
299 template <
bool Mt = MtMode,
300 typename Enable =
typename std::enable_if<Mt>::type>
303 template <
bool Mt = MtMode,
304 typename Enable =
typename std::enable_if<Mt>::type>
306 template <
bool Mt = MtMode,
307 typename Enable =
typename std::enable_if<Mt>::type>
310 template <
bool Mt = MtMode,
311 typename Enable =
typename std::enable_if<Mt>::type>
315 using byten_t = uint64_t;
316 using bitn_t = uint8_t;
319 static constexpr std::size_t SLICE = 4;
321 static constexpr std::size_t NIB = ((1ULL << SLICE) - 1);
323 static constexpr std::size_t SLNODES = (1 << SLICE);
325 static constexpr bitn_t SLICE_MASK = (bitn_t) ~(SLICE - 1);
327 static constexpr bitn_t FIRST_NIB = 8 - SLICE;
329 static constexpr size_t EPOCHS_NUMBER = 3;
334 using pointer_type = detail::tagged_ptr<leaf, node>;
335 using atomic_pointer_type =
336 typename std::conditional<MtMode, std::atomic<pointer_type>,
341 const atomic_pointer_type *slot;
346 using path_type = std::vector<node_desc>;
350 static constexpr size_t PATH_INIT_CAP = 64;
353 atomic_pointer_type root;
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;
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,
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 *,
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);
390 static bool path_length_equal(
size_t key_size, pointer_type n);
391 template <
bool Lower,
typename K>
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
397 template <
bool Mt = MtMode>
398 typename std::enable_if<!Mt, bool>::type
400 template <
bool Lower,
typename K>
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>
407 void clear_garbage(
size_t n);
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);
417 static_assert(
sizeof(
node) == 256,
418 "Internal node should have size equal to 256 bytes.");
421template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
434template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
449 const Key &key()
const;
450 const Value &value()
const;
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>
462 template <
typename K,
typename... Args>
465 template <
typename K,
typename V>
467 detail::pair<K, V> &&
p);
468 template <
typename K,
typename V>
470 const detail::pair<K, V> &
p);
471 template <
typename K,
typename V>
473 std::pair<K, V> &&
p);
474 template <
typename K,
typename V>
476 const std::pair<K, V> &
p);
481 friend class radix_tree<Key, Value, BytesView, MtMode>;
485 template <
typename... Args1,
typename... Args2,
size_t... I1,
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...>);
493 atomic_pointer_type parent;
500template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
502 node(pointer_type parent, byten_t
byte, bitn_t bit);
518 atomic_pointer_type child[SLNODES];
534 static constexpr bool Forward = 0;
535 static constexpr bool Reverse = 1;
538 struct forward_iterator;
539 using reverse_iterator = std::reverse_iterator<forward_iterator>;
541 template <
bool Direction>
543 typename std::conditional<Direction == direction::Forward,
545 reverse_iterator>::type;
547 template <
bool Direction = direction::Forward>
548 typename std::enable_if<
551 MtMode>::node::direction::Forward,
553 MtMode>::node::forward_iterator>::type
556 template <
bool Direction = direction::Forward>
557 typename std::enable_if<
560 MtMode>::node::direction::Forward,
562 MtMode>::node::forward_iterator>::type
566 template <
bool Direction = direction::Forward>
567 typename std::enable_if<
570 MtMode>::node::direction::Reverse,
572 MtMode>::node::reverse_iterator>::type
576 template <
bool Direction = direction::Forward>
577 typename std::enable_if<
580 MtMode>::node::direction::Reverse,
582 MtMode>::node::reverse_iterator>::type
585 template <
bool Direction = direction::Forward,
typename Ptr>
586 auto find_child(
const Ptr &n)
const ->
decltype(begin<Direction>());
588 template <
bool Direction = direction::Forward,
589 typename Enable =
typename std::enable_if<
590 Direction == direction::Forward>::type>
591 auto make_iterator(
const atomic_pointer_type *ptr)
const
592 ->
decltype(begin<Direction>());
594 uint8_t padding[256 -
sizeof(parent) -
sizeof(
leaf) -
sizeof(child) -
595 sizeof(
byte) -
sizeof(bit)];
603template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
604template <
bool IsConst>
608 typename std::conditional<IsConst, const leaf *, leaf *>::type;
609 using tree_ptr =
typename std::conditional<IsConst,
const radix_tree *,
614 using difference_type = std::ptrdiff_t;
616 using reference =
typename std::conditional<IsConst,
const value_type &,
618 using pointer =
typename std::conditional<IsConst,
value_type const *,
620 using iterator_category =
typename std::conditional<
621 MtMode, std::forward_iterator_tag,
622 std::bidirectional_iterator_tag>::type;
628 template <
bool C = IsConst,
629 typename Enable =
typename std::enable_if<C>::type>
635 reference operator*()
const;
636 pointer operator->()
const;
638 template <
typename V = Value,
639 typename Enable =
typename std::enable_if<
640 detail::is_inline_string<V>::value>::type>
642 typename V::traits_type>
645 template <
typename T,
typename V = Value,
646 typename Enable =
typename std::enable_if<
647 !detail::is_inline_string<V>::value>::type>
648 void assign_val(T &&rhs);
651 template <
bool Mt = MtMode,
652 typename Enable =
typename std::enable_if<!Mt>::type>
656 template <
bool Mt = MtMode,
657 typename Enable =
typename std::enable_if<!Mt>::type>
669 leaf_ptr leaf_ =
nullptr;
670 tree_ptr tree =
nullptr;
672 template <
typename T>
673 void replace_val(T &&rhs);
675 bool try_increment();
676 bool try_decrement();
679template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
680struct radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator {
681 using difference_type = std::ptrdiff_t;
682 using value_type = atomic_pointer_type;
683 using pointer =
const value_type *;
684 using reference =
const value_type &;
685 using iterator_category = std::forward_iterator_tag;
687 forward_iterator(pointer child,
const node *
node);
694 reference operator*()
const;
695 pointer operator->()
const;
697 pointer get_node()
const;
699 bool operator!=(
const forward_iterator &rhs)
const;
700 bool operator==(
const forward_iterator &rhs)
const;
715template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
717 : root(nullptr), size_(0)
742template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
743template <
class InputIt>
746 : root(nullptr), size_(0)
751 for (
auto it = first; it != last; it++)
770template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
772 : root(nullptr), size_(0)
777 for (
auto it = m.
cbegin(); it != m.
cend(); it++)
793template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
797 check_tx_stage_work();
799 store(root, load(m.root));
801 store(m.root,
nullptr);
819template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
821 std::initializer_list<value_type> il)
835template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
843 if (
this != &other) {
847 store(this->root,
nullptr);
850 for (
auto it = other.
cbegin(); it != other.
cend(); it++)
866template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
874 if (
this != &other) {
878 store(this->root, load(other.root));
879 this->size_ = other.size_;
880 store(other.root,
nullptr);
898template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
901 std::initializer_list<value_type> ilist)
910 store(this->root,
nullptr);
913 for (
auto it = ilist.begin(); it != ilist.end(); it++)
923template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
928 for (
size_t i = 0; i < EPOCHS_NUMBER; ++i)
940template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
950template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
951typename radix_tree<Key, Value, BytesView, MtMode>::size_type
954 return std::numeric_limits<difference_type>::max();
960template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
972template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
979 this->size_.swap(rhs.size_);
980 this->root.swap(rhs.root);
993template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
994template <
bool Mt,
typename Enable>
999 for (
size_t i = 0; i < EPOCHS_NUMBER; ++i) {
1014template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1015template <
bool Mt,
typename Enable>
1020 clear_garbage(ebr_->gc_epoch());
1023template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1027 assert(n >= 0 && n < EPOCHS_NUMBER);
1032 for (
auto &e : garbages[n]) {
1034 delete_persistent<radix_tree::leaf>(
1038 delete_persistent<radix_tree::node>(
1043 garbages[n].clear();
1047template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1048typename radix_tree<Key, Value, BytesView, MtMode>::pointer_type
1049radix_tree<Key, Value, BytesView, MtMode>::load(
1050 const std::atomic<detail::tagged_ptr<leaf, node>> &ptr)
1052 return ptr.load_acquire();
1055template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1056typename radix_tree<Key, Value, BytesView, MtMode>::pointer_type
1057radix_tree<Key, Value, BytesView, MtMode>::load(
const pointer_type &ptr)
1062template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1064radix_tree<Key, Value, BytesView, MtMode>::store(
1065 std::atomic<detail::tagged_ptr<leaf, node>> &ptr, pointer_type desired)
1067 ptr.store_with_snapshot_release(desired);
1070template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1072radix_tree<Key, Value, BytesView, MtMode>::store(pointer_type &ptr,
1073 pointer_type desired)
1086template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1087template <
bool Mt,
typename Enable>
1091#if LIBPMEMOBJ_CPP_VG_PMEMCHECK_ENABLED
1092 VALGRIND_PMC_REMOVE_PMEM_MAPPING(&ebr_,
sizeof(
ebr *));
1101template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1102template <
bool Mt,
typename Enable>
1120template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1121template <
bool Mt,
typename Enable>
1122typename radix_tree<Key, Value, BytesView, MtMode>::worker_type
1127 return ebr_->register_worker();
1133template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1134typename radix_tree<Key, Value, BytesView, MtMode>::atomic_pointer_type &
1138 return get_leaf(n)->parent;
1151template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1152typename radix_tree<Key, Value, BytesView, MtMode>::leaf *
1153radix_tree<Key, Value, BytesView, MtMode>::any_leftmost_leaf(
1154 typename radix_tree<Key, Value, BytesView, MtMode>::pointer_type n,
1155 size_type min_depth)
const
1159 while (n && !is_leaf(n)) {
1160 auto ne = load(n->embedded_entry);
1161 if (ne && n->byte >= min_depth)
1162 return get_leaf(ne);
1164 pointer_type nn =
nullptr;
1165 for (
size_t i = 0; i < SLNODES; i++) {
1166 nn = load(n->child[i]);
1175 return n ? get_leaf(n) : nullptr;
1189template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1190template <
typename K>
1191std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::leaf *,
1192 typename radix_tree<Key, Value, BytesView, MtMode>::path_type>
1193radix_tree<Key, Value, BytesView, MtMode>::descend(pointer_type root_snap,
1198 auto slot = &this->root;
1200 decltype(n) prev =
nullptr;
1203 path.reserve(PATH_INIT_CAP);
1204 path.push_back(node_desc{slot, n, prev});
1206 while (n && !is_leaf(n) && n->byte < key.size()) {
1208 slot = &n->child[slice_index(key[n->byte], n->bit)];
1209 auto nn = load(*slot);
1212 path.push_back(node_desc{slot, nn, prev});
1215 path.push_back(node_desc{slot,
nullptr, prev});
1216 n = any_leftmost_leaf(n, key.size());
1222 return {
nullptr, std::move(path)};
1227 n = any_leftmost_leaf(n, key.size());
1231 return std::pair<leaf *, path_type>{get_leaf(n),
1234 return std::pair<leaf *, path_type>{
nullptr, std::move(path)};
1238template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1239template <
typename K>
1241radix_tree<Key, Value, BytesView, MtMode>::bytes_view(
const K &key)
1246 return BytesView(&key);
1249template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1251radix_tree<Key, Value, BytesView, MtMode>::bytes_view(string_view key)
1259template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1260template <
typename K1,
typename K2>
1262radix_tree<Key, Value, BytesView, MtMode>::keys_equal(
const K1 &k1,
1265 return k1.size() == k2.size() && compare(k1, k2) == 0;
1271template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1272template <
typename K1,
typename K2>
1274radix_tree<Key, Value, BytesView, MtMode>::compare(
const K1 &k1,
const K2 &k2,
1277 auto ret = prefix_diff(k1, k2, offset);
1279 if (ret != (std::min)(k1.size(), k2.size()))
1280 return (
unsigned char)(k1[ret]) - (
unsigned char)(k2[ret]);
1282 return k1.size() - k2.size();
1288template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1289template <
typename K1,
typename K2>
1290typename radix_tree<Key, Value, BytesView, MtMode>::byten_t
1291radix_tree<Key, Value, BytesView, MtMode>::prefix_diff(
const K1 &lhs,
1296 for (diff = offset; diff < (std::min)(lhs.size(), rhs.size()); diff++) {
1297 if (lhs[diff] != rhs[diff])
1308template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1310radix_tree<Key, Value, BytesView, MtMode>::path_length_equal(
size_t key_size,
1313 return n->byte == key_size && n->bit == bitn_t(FIRST_NIB);
1316template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1317template <
typename K1,
typename K2>
1318typename radix_tree<Key, Value, BytesView, MtMode>::bitn_t
1319radix_tree<Key, Value, BytesView, MtMode>::bit_diff(
const K1 &leaf_key,
1320 const K2 &key, byten_t diff)
1322 auto min_key_len = (std::min)(leaf_key.size(), key.size());
1328 if (diff < min_key_len) {
1330 static_cast<unsigned char>(leaf_key[diff] ^ key[diff]);
1331 sh = pmem::detail::mssb_index((uint32_t)at) & SLICE_MASK;
1341template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1342typename radix_tree<Key, Value, BytesView, MtMode>::node_desc
1343radix_tree<Key, Value, BytesView, MtMode>::follow_path(
const path_type &path,
1347 assert(path.size());
1352 while (n.node && !is_leaf(n.node) &&
1353 (n.node->byte < diff ||
1354 (n.node->byte == diff && n.node->bit >= sh))) {
1357 assert(idx < path.size());
1365template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1366template <
typename K,
typename F,
class... Args>
1367std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator,
bool>
1368radix_tree<Key, Value, BytesView, MtMode>::internal_emplace(
const K &k,
1371 auto key = bytes_view(k);
1372 auto pop = pool_base(pmemobj_pool_by_ptr(
this));
1374 auto r = load(root);
1378 leaf = make_leaf(
nullptr);
1379 store(this->root, leaf);
1381 return {iterator(get_leaf(leaf),
this),
true};
1391 auto ret = descend(r, key);
1392 auto leaf = ret.first;
1393 auto path = ret.second;
1397 auto leaf_key = bytes_view(leaf->key());
1398 auto diff = prefix_diff(key, leaf_key);
1399 auto sh = bit_diff(leaf_key, key, diff);
1402 if (diff == key.size() && leaf_key.size() == key.size())
1403 return {iterator(leaf,
this),
false};
1406 auto node_d = follow_path(path, diff, sh);
1407 auto slot =
const_cast<atomic_pointer_type *
>(node_d.slot);
1408 auto prev = node_d.prev;
1409 auto n = node_d.node;
1417 assert(diff < (std::min)(leaf_key.size(), key.size()));
1420 [&] { store(*slot, make_leaf(prev)); });
1421 return {iterator(get_leaf(load(*slot)),
this),
true};
1426 if (diff == key.size()) {
1427 if (!is_leaf(n) && path_length_equal(key.size(), n)) {
1428 assert(!load(n->embedded_entry));
1431 store(n->embedded_entry, make_leaf(n));
1434 return {iterator(get_leaf(load(n->embedded_entry)),
1443 node = make_persistent<radix_tree::node>(
1444 load(parent_ref(n)), diff, bitn_t(FIRST_NIB));
1445 store(node->embedded_entry, make_leaf(node));
1446 store(node->child[slice_index(leaf_key[diff],
1447 bitn_t(FIRST_NIB))],
1450 store(parent_ref(n), node);
1454 return {iterator(get_leaf(load(node->embedded_entry)),
this),
1458 if (diff == leaf_key.size()) {
1465 node = make_persistent<radix_tree::node>(
1466 load(parent_ref(n)), diff, bitn_t(FIRST_NIB));
1467 store(node->embedded_entry, n);
1468 store(node->child[slice_index(key[diff],
1469 bitn_t(FIRST_NIB))],
1472 store(parent_ref(n), node);
1476 return {iterator(get_leaf(load(node->child[slice_index(
1477 key[diff], bitn_t(FIRST_NIB))])),
1488 node = make_persistent<radix_tree::node>(load(parent_ref(n)),
1490 store(node->child[slice_index(leaf_key[diff], sh)], n);
1491 store(node->child[slice_index(key[diff], sh)], make_leaf(node));
1493 store(parent_ref(n), node);
1498 get_leaf(load(node->child[slice_index(key[diff], sh)])),
1531template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1532template <
class... Args>
1533std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator,
bool>
1537 return internal_emplace(k, [&](pointer_type parent) {
1539 return leaf::make_key_args(parent, k,
1540 std::forward<Args>(args)...);
1570template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1571template <
class... Args>
1572std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator,
bool>
1575 auto pop =
pool_base(pmemobj_pool_by_ptr(
this));
1576 std::pair<iterator, bool> ret;
1579 auto leaf_ = leaf::make(
nullptr, std::forward<Args>(args)...);
1580 auto make_leaf = [&](pointer_type parent) {
1581 store(leaf_->parent, parent);
1586 ret = internal_emplace(leaf_->key(), make_leaf);
1589 delete_persistent<leaf>(leaf_);
1610template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1611std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator,
bool>
1614 return try_emplace(
v.first,
v.second);
1632template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1633std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator,
bool>
1636 return try_emplace(std::move(
v.first), std::move(
v.second));
1658template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1659template <
typename P,
typename>
1660std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator,
bool>
1663 return emplace(std::forward<P>(
p));
1677template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1678template <
typename InputIterator>
1683 for (
auto it = first; it != last; it++)
1684 try_emplace((*it).first, (*it).second);
1697template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1700 std::initializer_list<value_type> il)
1702 insert(il.begin(), il.end());
1729template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1730template <
class... Args>
1731std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator,
bool>
1735 return internal_emplace(k, [&](pointer_type parent) {
1737 return leaf::make_key_args(parent, std::move(k),
1738 std::forward<Args>(args)...);
1770template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1771template <
typename K,
typename BV,
class... Args>
1774 ->
typename std::enable_if<
1775 detail::has_is_transparent<BV>::value &&
1776 !std::is_same<
typename std::remove_const<
1777 typename std::remove_reference<
1780 std::pair<
typename radix_tree<Key, Value, BytesView,
1785 return internal_emplace(k, [&](pointer_type parent) {
1787 return leaf::make_key_args(parent, std::forward<K>(k),
1788 std::forward<Args>(args)...);
1810template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1811template <
typename M>
1812std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator,
bool>
1816 auto ret = try_emplace(k, std::forward<M>(obj));
1818 ret.first.assign_val(std::forward<M>(obj));
1840template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1841template <
typename M>
1842std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator,
bool>
1846 auto ret = try_emplace(std::move(k), std::forward<M>(obj));
1848 ret.first.assign_val(std::forward<M>(obj));
1873template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1874template <
typename M,
typename K,
typename>
1875std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator,
bool>
1878 auto ret = try_emplace(std::forward<K>(k), std::forward<M>(obj));
1880 ret.first.assign_val(std::forward<M>(obj));
1893template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1894typename radix_tree<Key, Value, BytesView, MtMode>::size_type
1897 return internal_find(k) !=
nullptr ? 1 : 0;
1912template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1913template <
typename K,
typename>
1914typename radix_tree<Key, Value, BytesView, MtMode>::size_type
1917 return internal_find(k) !=
nullptr ? 1 : 0;
1928template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1932 return iterator(internal_find(k),
this);
1943template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1961template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1962template <
typename K,
typename>
1966 return iterator(internal_find(k),
this);
1980template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1981template <
typename K,
typename>
1988template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1989template <
typename K>
1993 auto key = bytes_view(k);
1995 auto n = load(root);
1996 while (n && !is_leaf(n)) {
1997 if (path_length_equal(key.size(), n))
1998 n = load(n->embedded_entry);
1999 else if (n->byte >= key.size())
2002 n = load(n->child[slice_index(key[n->byte], n->bit)]);
2008 if (!keys_equal(key, bytes_view(get_leaf(n)->key())))
2021template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2044template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2048 auto pop =
pool_base(pmemobj_pool_by_ptr(
this));
2051 auto *
leaf = pos.leaf_;
2052 auto parent = load(
leaf->parent);
2064 store(this->root,
nullptr);
2070 store(
const_cast<atomic_pointer_type &
>(
2071 *parent->find_child(
leaf)),
2076 parent = load(n->parent);
2077 pointer_type only_child =
nullptr;
2078 for (
size_t i = 0; i < SLNODES; i++) {
2079 if (load(n->child[i])) {
2084 only_child = load(n->child[i]);
2088 if (only_child && load(n->embedded_entry)) {
2092 }
else if (load(n->embedded_entry)) {
2093 only_child = load(n->embedded_entry);
2097 store(parent_ref(only_child), load(n->parent));
2099 auto *child_slot = parent ?
const_cast<atomic_pointer_type *
>(
2100 &*parent->find_child(n))
2102 store(*child_slot, only_child);
2107 return iterator(
const_cast<typename iterator::leaf_ptr
>(pos.leaf_),
2124template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2129 auto pop =
pool_base(pmemobj_pool_by_ptr(
this));
2132 while (first != last)
2133 first = erase(first);
2136 return iterator(
const_cast<typename iterator::leaf_ptr
>(first.leaf_),
2152template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2153typename radix_tree<Key, Value, BytesView, MtMode>::size_type
2180template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2181template <
typename K,
typename>
2182typename radix_tree<Key, Value, BytesView, MtMode>::size_type
2199template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2200template <
typename T>
2204 if (MtMode && ebr_ !=
nullptr)
2205 garbages[ebr_->staging_epoch()].emplace_back(ptr);
2207 delete_persistent<T>(ptr);
2214template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2215template <
bool Lower,
typename K>
2224 return (compare(bytes_view(it->key()), bytes_view(key)) >= 0);
2226 return (compare(bytes_view(it->key()), bytes_view(key)) > 0);
2232template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2234typename std::enable_if<Mt, bool>::type
2236 const path_type &path)
const
2238 for (
auto i = 0ULL; i < path.size(); i++) {
2239 if (path[i].
node != load(*path[i].slot))
2243 load(parent_ref(path[i].
node)) != path[i].prev)
2250template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2252typename std::enable_if<!Mt, bool>::type
2254 const path_type &path)
const
2259template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2260template <
bool Lower,
typename K>
2261typename radix_tree<Key, Value, BytesView, MtMode>::const_iterator
2262radix_tree<Key, Value, BytesView, MtMode>::internal_bound(
const K &k)
const
2264 auto key = bytes_view(k);
2265 auto pop =
pool_base(pmemobj_pool_by_ptr(
this));
2268 const_iterator result;
2271 auto r = load(root);
2283 auto ret = descend(r, key);
2284 auto leaf = ret.first;
2290 auto leaf_key = bytes_view(leaf->key());
2291 auto diff = prefix_diff(key, leaf_key);
2292 auto sh = bit_diff(leaf_key, key, diff);
2295 if (diff == key.size() && leaf_key.size() == key.size()) {
2296 result = const_iterator(leaf,
this);
2303 if (result.try_increment())
2310 auto node_d = follow_path(path, diff, sh);
2312 auto n = node_d.node;
2313 auto slot = node_d.slot;
2314 auto prev = node_d.prev;
2322 assert(prev && !is_leaf(prev));
2324 auto target_leaf = next_leaf<node::direction::Forward>(
2325 prev->template make_iterator<
2326 node::direction::Forward>(slot),
2329 if (!target_leaf.first)
2332 result = const_iterator(target_leaf.second,
this);
2333 }
else if (diff == key.size()) {
2341 find_leaf<node::direction::Forward>(n);
2346 result = const_iterator(target_leaf,
this);
2347 }
else if (diff == leaf_key.size()) {
2363 auto target_leaf = next_leaf<
2364 node::direction::Forward>(
2365 prev->template make_iterator<
2366 node::direction::Forward>(slot),
2369 if (!target_leaf.first)
2372 result = const_iterator(target_leaf.second,
2376 assert(diff < leaf_key.size() && diff < key.size());
2402 if (
static_cast<unsigned char>(key[diff]) <
2403 static_cast<unsigned char>(leaf_key[diff])) {
2405 find_leaf<node::direction::Forward>(n);
2410 result = const_iterator(target_leaf,
this);
2411 }
else if (slot == &root) {
2412 result = const_iterator(
nullptr,
this);
2415 assert(
static_cast<unsigned char>(key[diff]) >
2416 static_cast<unsigned char>(
2429 auto target_leaf = next_leaf<
2430 node::direction::Forward>(
2431 prev->template make_iterator<
2432 node::direction::Forward>(slot),
2435 if (!target_leaf.first)
2438 result = const_iterator(target_leaf.second,
2445 if (validate_path(path))
2449 assert(validate_bound<Lower>(result, k));
2464template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2465typename radix_tree<Key, Value, BytesView, MtMode>::const_iterator
2468 return internal_bound<true>(k);
2481template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2485 auto it =
const_cast<const radix_tree *
>(
this)->lower_bound(k);
2486 return iterator(
const_cast<typename iterator::leaf_ptr
>(it.leaf_),
2503template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2504template <
typename K,
typename>
2508 auto it =
const_cast<const radix_tree *
>(
this)->lower_bound(k);
2509 return iterator(
const_cast<typename iterator::leaf_ptr
>(it.leaf_),
2526template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2527template <
typename K,
typename>
2531 return internal_bound<true>(k);
2544template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2548 return internal_bound<false>(k);
2561template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2565 auto it =
const_cast<const radix_tree *
>(
this)->upper_bound(k);
2566 return iterator(
const_cast<typename iterator::leaf_ptr
>(it.leaf_),
2583template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2584template <
typename K,
typename>
2588 auto it =
const_cast<const radix_tree *
>(
this)->upper_bound(k);
2589 return iterator(
const_cast<typename iterator::leaf_ptr
>(it.leaf_),
2606template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2607template <
typename K,
typename>
2611 return internal_bound<false>(k);
2620template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2626 const_cast<typename iterator::leaf_ptr
>(const_begin.leaf_),
2637template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2641 auto const_end =
const_cast<const radix_tree *
>(
this)->
end();
2643 const_cast<typename iterator::leaf_ptr
>(const_end.leaf_),
this);
2652template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2657 auto root_ptr = load(root);
2661 auto leaf = find_leaf<radix_tree::node::direction::Forward>(
2676template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2689template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2703template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2717template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2718typename radix_tree<Key, Value, BytesView, MtMode>::reverse_iterator
2721 return reverse_iterator(
end());
2732template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2733typename radix_tree<Key, Value, BytesView, MtMode>::reverse_iterator
2736 return reverse_iterator(
begin());
2746template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2747typename radix_tree<Key, Value, BytesView, MtMode>::const_reverse_iterator
2750 return const_reverse_iterator(
cend());
2761template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2762typename radix_tree<Key, Value, BytesView, MtMode>::const_reverse_iterator
2765 return const_reverse_iterator(
cbegin());
2768template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2769typename radix_tree<Key, Value, BytesView, MtMode>::const_reverse_iterator
2772 return const_reverse_iterator(
cend());
2775template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2776typename radix_tree<Key, Value, BytesView, MtMode>::const_reverse_iterator
2779 return const_reverse_iterator(
cbegin());
2782template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2784radix_tree<Key, Value, BytesView, MtMode>::print_rec(std::ostream &os,
2785 radix_tree::pointer_type n)
2788 os <<
"\"" << get_node(n) <<
"\""
2789 <<
" [style=filled,color=\"blue\"]" << std::endl;
2790 os <<
"\"" << get_node(n) <<
"\" [label=\"byte:" << n->byte
2791 <<
", bit:" << int(n->bit) <<
"\"]" << std::endl;
2793 auto p = load(n->parent);
2794 auto parent = p ? get_node(p) : 0;
2795 os <<
"\"" << get_node(n) <<
"\" -> "
2796 <<
"\"" << parent <<
"\" [label=\"parent\"]" << std::endl;
2798 for (
auto it = n->begin(); it != n->end(); ++it) {
2804 auto ch = is_leaf(c) ? (
void *)get_leaf(c)
2805 : (
void *)get_node(c);
2807 os <<
"\"" << get_node(n) <<
"\" -> \"" << ch <<
"\""
2812 auto bv = bytes_view(get_leaf(n)->key());
2814 os <<
"\"" << get_leaf(n) <<
"\" [style=filled,color=\"green\"]"
2816 os <<
"\"" << get_leaf(n) <<
"\" [label=\"key:";
2818 for (
size_t i = 0; i < bv.size(); i++)
2821 os <<
"\"]" << std::endl;
2823 auto p = load(get_leaf(n)->parent);
2824 auto parent = p ? get_node(p) : nullptr;
2826 os <<
"\"" << get_leaf(n) <<
"\" -> \"" << parent
2827 <<
"\" [label=\"parent\"]" << std::endl;
2829 if (parent && n == load(parent->embedded_entry)) {
2830 os <<
"{rank=same;\"" << parent <<
"\";\""
2831 << get_leaf(n) <<
"\"}" << std::endl;
2839template <
typename K,
typename V,
typename BV,
bool MtMode>
2843 os <<
"digraph Radix {" << std::endl;
2849 os <<
"}" << std::endl;
2857template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2859radix_tree<Key, Value, BytesView, MtMode>::slice_index(
char b, uint8_t bit)
2861 return static_cast<unsigned>(b >> bit) & NIB;
2864template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2865radix_tree<Key, Value, BytesView,
2866 MtMode>::node::forward_iterator::forward_iterator(pointer child,
2868 : child(child), n(n)
2872template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2873typename radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator
2876 if (child == &n->embedded_entry)
2877 child = &n->child[0];
2884template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2885radix_tree<Key, Value, BytesView, MtMode>::node::node(pointer_type parent,
2886 byten_t
byte, bitn_t bit)
2887 : parent(parent), byte(byte), bit(bit)
2891template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2892typename radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator
2895 if (child == &n->child[0])
2896 child = &n->embedded_entry;
2903template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2904typename radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator
2908 forward_iterator tmp(child, n);
2913template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2914typename radix_tree<Key, Value, BytesView,
2915 MtMode>::node::forward_iterator::reference
2916 radix_tree<Key, Value, BytesView,
2917 MtMode>::node::forward_iterator::operator*()
const
2922template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2923typename radix_tree<Key, Value, BytesView,
2924 MtMode>::node::forward_iterator::pointer
2925 radix_tree<Key, Value, BytesView,
2926 MtMode>::node::forward_iterator::operator->()
const
2931template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2932typename radix_tree<Key, Value, BytesView,
2933 MtMode>::node::forward_iterator::pointer
2934radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator::get_node()
2940template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2943 const forward_iterator &rhs)
const
2945 return child == rhs.child && n == rhs.n;
2948template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2951 const forward_iterator &rhs)
const
2953 return child != rhs.child || n != rhs.n;
2956template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2957template <
bool Direction>
2958typename std::enable_if<Direction ==
2959 radix_tree<Key, Value, BytesView,
2960 MtMode>::node::direction::Forward,
2961 typename radix_tree<Key, Value, BytesView, MtMode>::
2962 node::forward_iterator>::type
2965 return forward_iterator(&embedded_entry,
this);
2968template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2969template <
bool Direction>
2970typename std::enable_if<Direction ==
2971 radix_tree<Key, Value, BytesView,
2972 MtMode>::node::direction::Forward,
2973 typename radix_tree<Key, Value, BytesView, MtMode>::
2974 node::forward_iterator>::type
2977 return forward_iterator(&child[SLNODES],
this);
2980template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2981template <
bool Direction>
2982typename std::enable_if<Direction ==
2983 radix_tree<Key, Value, BytesView,
2984 MtMode>::node::direction::Reverse,
2985 typename radix_tree<Key, Value, BytesView, MtMode>::
2986 node::reverse_iterator>::type
2989 return reverse_iterator(end<direction::Forward>());
2992template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2993template <
bool Direction>
2994typename std::enable_if<Direction ==
2995 radix_tree<Key, Value, BytesView,
2996 MtMode>::node::direction::Reverse,
2997 typename radix_tree<Key, Value, BytesView, MtMode>::
2998 node::reverse_iterator>::type
3001 return reverse_iterator(begin<direction::Forward>());
3004template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3005template <
bool Direction,
typename Ptr>
3007radix_tree<Key, Value, BytesView, MtMode>::node::find_child(
const Ptr &n)
const
3008 ->
decltype(begin<Direction>())
3010 auto it = begin<Direction>();
3011 while (it != end<Direction>()) {
3019template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3020template <
bool Direction,
typename Enable>
3022radix_tree<Key, Value, BytesView, MtMode>::node::make_iterator(
3023 const atomic_pointer_type *ptr)
const ->
decltype(begin<Direction>())
3025 return forward_iterator(ptr,
this);
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)
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)
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
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
3084template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3085template <
bool IsConst>
3086template <
typename V,
typename Enable>
3088radix_tree<Key, Value, BytesView, MtMode>::radix_tree_iterator<
3090 typename V::traits_type>
3096 auto pop =
pool_base(pmemobj_pool_by_ptr(leaf_));
3098 if (rhs.size() <= leaf_->value().capacity() && !MtMode) {
3105template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3106template <
bool IsConst>
3107template <
typename T>
3112 auto pop =
pool_base(pmemobj_pool_by_ptr(leaf_));
3113 atomic_pointer_type *slot;
3115 if (!load(leaf_->parent)) {
3116 assert(get_leaf(load(tree->root)) == leaf_);
3119 slot =
const_cast<atomic_pointer_type *
>(
3120 &*load(leaf_->parent)->find_child(leaf_));
3123 auto old_leaf = leaf_;
3127 leaf::make_key_args(load(old_leaf->parent),
3129 std::forward<T>(rhs)));
3133 leaf_ = get_leaf(load(*slot));
3143template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3144template <
bool IsConst>
3145template <
typename T,
typename V,
typename Enable>
3147radix_tree<Key, Value, BytesView,
3150 if (MtMode && tree->ebr_ !=
nullptr)
3151 replace_val(std::forward<T>(rhs));
3153 auto pop =
pool_base(pmemobj_pool_by_ptr(leaf_));
3155 pop, [&] { leaf_->value() = std::forward<T>(rhs); });
3159template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3160template <
bool IsConst>
3167 if (!try_increment())
3168 *
this = tree->upper_bound(leaf_->key());
3177template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3178template <
bool IsConst>
3181 MtMode>::radix_tree_iterator<IsConst>::try_increment()
3186 constexpr auto direction = radix_tree::node::direction::Forward;
3187 auto parent_ptr = load(leaf_->parent);
3193 auto it = parent_ptr->template find_child<direction>(leaf_);
3195 if (it == parent_ptr->template end<direction>())
3198 auto ret = tree->template next_leaf<direction>(it, parent_ptr);
3203 leaf_ =
const_cast<leaf_ptr
>(ret.second);
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--()
3223 while (!try_decrement()) {
3224 *
this = tree->lower_bound(leaf_->key());
3234template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3235template <
bool IsConst>
3237radix_tree<Key, Value, BytesView,
3238 MtMode>::radix_tree_iterator<IsConst>::try_decrement()
3240 constexpr auto direction = radix_tree::node::direction::Reverse;
3246 auto r = load(tree->root);
3251 leaf_ =
const_cast<leaf_ptr
>(
3252 tree->template find_leaf<direction>(r));
3257 auto parent_ptr = load(leaf_->parent);
3262 auto it = parent_ptr->template find_child<direction>(
3265 if (it == parent_ptr->template end<direction>())
3268 auto ret = tree->template next_leaf<direction>(
3274 leaf_ =
const_cast<leaf_ptr
>(ret.second);
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)
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)
3315template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3316template <
bool IsConst>
3319radix_tree<Key, Value, BytesView, MtMode>::radix_tree_iterator<
3320 IsConst>::operator!=(
const radix_tree_iterator<C> &rhs)
const
3322 return leaf_ != rhs.leaf_;
3325template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3326template <
bool IsConst>
3329radix_tree<Key, Value, BytesView, MtMode>::radix_tree_iterator<
3330 IsConst>::operator==(
const radix_tree_iterator<C> &rhs)
const
3332 return !(*
this != rhs);
3344template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3345template <
bool Direction,
typename Iterator>
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
3355 if (node == parent->template end<Direction>()) {
3356 auto p = load(parent->parent);
3358 return {
true,
nullptr};
3360 auto p_it = p->template find_child<Direction>(parent);
3361 if (p_it == p->template end<Direction>()) {
3363 return {
false,
nullptr};
3366 return next_leaf<Direction>(p_it, p);
3369 auto n = load(*node);
3373 auto leaf = find_leaf<Direction>(n);
3375 return {
false,
nullptr};
3377 return {
true, leaf};
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)
3400 for (
auto it = n->template begin<Direction>();
3401 it != n->template end<Direction>(); ++it) {
3402 auto ptr = load(*it);
3404 return find_leaf<Direction>(ptr);
3412template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3414radix_tree<Key, Value, BytesView, MtMode>::leaf::key()
3416 auto &const_key =
const_cast<const leaf *
>(
this)->key();
3417 return *
const_cast<Key *
>(&const_key);
3420template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3422radix_tree<Key, Value, BytesView, MtMode>::leaf::value()
3424 auto &const_value =
const_cast<const leaf *
>(
this)->value();
3425 return *
const_cast<Value *
>(&const_value);
3428template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3430radix_tree<Key, Value, BytesView, MtMode>::leaf::key()
const
3432 return *
reinterpret_cast<const Key *
>(
this + 1);
3435template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3437radix_tree<Key, Value, BytesView, MtMode>::leaf::value()
const
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;
3443 reinterpret_cast<const Value *
>(key_dst + padding + key_size);
3448template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3449radix_tree<Key, Value, BytesView, MtMode>::leaf::~leaf()
3451 detail::destroy<Key>(key());
3452 detail::destroy<Value>(value());
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)
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{});
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)
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{});
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,
3483 return make(parent, std::piecewise_construct, std::forward_as_tuple(k),
3484 std::forward_as_tuple(v));
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,
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)));
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)
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)...));
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)
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)));
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)
3526 return make(parent, std::piecewise_construct,
3527 std::forward_as_tuple(p.first),
3528 std::forward_as_tuple(p.second));
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)
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)));
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)
3548 return make(parent, std::piecewise_construct,
3549 std::forward_as_tuple(p.first),
3550 std::forward_as_tuple(p.second));
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...>)
3561 standard_alloc_policy<void> a;
3562 auto key_size = total_sizeof<Key>::value(std::get<I1>(first_args)...);
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));
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);
3573 assert(
reinterpret_cast<uintptr_t
>(key_dst) %
alignof(Key) == 0);
3574 assert(
reinterpret_cast<uintptr_t
>(val_dst) %
alignof(Value) == 0);
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))...);
3580 store(ptr->parent, parent);
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,
3590 return make(parent, other.key(), other.value());
3599template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3603 if (
nullptr == pmemobj_pool_by_ptr(
this))
3614template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3618 if (pmemobj_tx_stage() != TX_STAGE_WORK)
3620 "Function called out of transaction scope.");
3623template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3626 const radix_tree<Key, Value, BytesView, MtMode>::pointer_type &
p)
3628 return p.template is<leaf>();
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)
3636 return p.template get<leaf>();
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)
3644 return p.template get<node>();
3650template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
3661struct is_string : std::false_type {
3664template <
typename CharT,
typename Traits>
3665struct is_string<obj::basic_string<CharT, Traits>> : std::true_type {
3668template <
typename CharT,
typename Traits>
3669struct is_string<obj::experimental::basic_inline_string<CharT, Traits>>
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;
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)
3686 char operator[](std::size_t p)
const
3688 return reinterpret_cast<const char *
>(s.data())[p];
3694 return s.size() *
sizeof(CharT);
3697 obj::basic_string_view<CharT, Traits> s;
3699 using is_transparent = void;
3702template <
typename 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)
3710 std::endian::native == std::endian::little,
3711 "Scalar type are not little endian on this platform!");
3712#elif !defined(NDEBUG)
3714 uint16_t word = (2 << 8) + 1;
3715 assert(((
char *)&word)[0] == 1);
3719 char operator[](std::size_t p)
const
3721 return reinterpret_cast<const char *
>(k)[size() - p - 1];
Persistent memory aware allocator.
Epoch-based reclamation (EBR).
Definition: ebr.hpp:71
Our partial std::string_view implementation.
Definition: string_view.hpp:46
static void run(obj::pool_base &pool, std::function< void()> tx, Locks &... locks)
Execute a closure-like transaction and lock locks.
Definition: transaction.hpp:694
Radix tree is an associative, ordered container.
Definition: radix_tree.hpp:120
void check_pmem()
Private helper function.
Definition: radix_tree.hpp:3601
const_reverse_iterator crend() const
Returns a const, reverse iterator to the end.
Definition: radix_tree.hpp:2763
const_iterator cbegin() const
Returns a const iterator to the first element of the container.
Definition: radix_tree.hpp:2654
void runtime_finalize_mt()
If MtMode == true, this function must be called before each application close and before calling radi...
Definition: radix_tree.hpp:1104
bool validate_bound(const_iterator it, const K &key) const
Checks if iterator points to element which compares bigger (or equal) to key.
Definition: radix_tree.hpp:2217
reverse_iterator rend()
Returns a reverse iterator to the end.
Definition: radix_tree.hpp:2734
void swap(radix_tree &rhs)
Member swap.
Definition: radix_tree.hpp:974
iterator begin()
Returns an iterator to the first element of the container.
Definition: radix_tree.hpp:2622
const_reverse_iterator crbegin() const
Returns a const, reverse iterator to the beginning.
Definition: radix_tree.hpp:2748
uint64_t size() const noexcept
Definition: radix_tree.hpp:962
void check_tx_stage_work()
Private helper function.
Definition: radix_tree.hpp:3616
iterator end()
Returns an iterator to the element following the last element of the map.
Definition: radix_tree.hpp:2639
void runtime_initialize_mt(ebr *e=new ebr())
If MtMode == true, this function must be called after each application restart.
Definition: radix_tree.hpp:1089
bool empty() const noexcept
Checks whether the container is empty.
Definition: radix_tree.hpp:942
size_type max_size() const noexcept
Definition: radix_tree.hpp:952
std::pair< iterator, bool > insert(const value_type &v)
Inserts element if the tree doesn't already contain an element with an equivalent key.
Definition: radix_tree.hpp:1612
reverse_iterator rbegin()
Returns a reverse iterator to the beginning.
Definition: radix_tree.hpp:2719
iterator erase(const_iterator pos)
Removes the element at pos from the container.
Definition: radix_tree.hpp:2046
worker_type register_worker()
Registers and returns a new worker, which can perform critical operations (accessing some shared data...
Definition: radix_tree.hpp:1123
iterator lower_bound(const key_type &k)
Returns an iterator pointing to the first element that is not less than (i.e.
Definition: radix_tree.hpp:2483
~radix_tree()
Destructor.
Definition: radix_tree.hpp:924
void clear()
Erases all elements from the container transactionally.
Definition: radix_tree.hpp:2023
std::enable_if< Mt, bool >::type validate_path(const path_type &path) const
Checks if any node in the.
Definition: radix_tree.hpp:2235
iterator find(const key_type &k)
Finds an element with key equivalent to key.
Definition: radix_tree.hpp:1930
void garbage_collect()
Tries to collect and free some garbage produced by erase, clear, insert_or_assign or assign_val in co...
Definition: radix_tree.hpp:1017
radix_tree & operator=(const radix_tree &m)
Copy assignment operator.
Definition: radix_tree.hpp:837
iterator upper_bound(const key_type &k)
Returns an iterator pointing to the first element that is greater than key.
Definition: radix_tree.hpp:2563
void garbage_collect_force()
Performs full epochs synchronisation.
Definition: radix_tree.hpp:996
const_iterator cend() const
Returns a const iterator to the element following the last element of the map.
Definition: radix_tree.hpp:2678
void free(persistent_ptr< T > ptr)
Deletes node/leaf pointed by ptr.
Definition: radix_tree.hpp:2202
size_type count(const key_type &k) const
Returns the number of elements with key that compares equivalent to the specified argument.
Definition: radix_tree.hpp:1895
radix_tree()
Default radix tree constructor.
Definition: radix_tree.hpp:716
Volatile residing on pmem class.
Definition: v.hpp:42
static void run(obj::pool_base &pool, std::function< void()> tx, Locks &... locks)
Execute a closure-like transaction and lock locks.
Definition: transaction.hpp:823
Resides on pmem class.
Definition: p.hpp:35
Persistent pointer class.
Definition: persistent_ptr.hpp:152
The non-template pool base class.
Definition: pool.hpp:50
pmem::obj::vector - persistent container with std::vector compatible interface.
Definition: vector.hpp:41
Custom pool error class.
Definition: pexceptions.hpp:45
Custom transaction error class.
Definition: pexceptions.hpp:176
Commonly used functionality.
Inline string implementation.
Create c++14 style index sequence.
Persistent_ptr transactional allocation functions for objects.
bool operator==(self_relative_ptr< T > const &lhs, self_relative_ptr< Y > const &rhs) noexcept
Equality operator.
Definition: self_relative_ptr.hpp:424
void swap(concurrent_map< Key, Value, Comp, Allocator > &lhs, concurrent_map< Key, Value, Comp, Allocator > &rhs)
Non-member swap.
Definition: concurrent_map.hpp:151
std::ostream & operator<<(std::ostream &os, const radix_tree< K, V, BV, MtMode > &tree)
Prints tree in DOT format.
Definition: radix_tree.hpp:2841
bool operator!=(self_relative_ptr< T > const &lhs, self_relative_ptr< Y > const &rhs) noexcept
Inequality operator.
Definition: self_relative_ptr.hpp:435
p< T > & operator--(p< T > &pp)
Prefix decrement operator overload.
Definition: pext.hpp:59
pmem::obj::array< T, N >::const_iterator cend(const pmem::obj::array< T, N > &a)
Non-member cend.
Definition: array.hpp:799
pmem::obj::array< T, N >::iterator end(pmem::obj::array< T, N > &a)
Non-member end.
Definition: array.hpp:849
bool operator!=(const allocator< T, P, Tr > &lhs, const OtherAllocator &rhs)
Determines if memory from another allocator can be deallocated from this one.
Definition: allocator.hpp:536
p< T > & operator++(p< T > &pp)
Prefix increment operator overload.
Definition: pext.hpp:48
pool_base pool_by_vptr(const T *that)
Retrieve pool handle for the given pointer.
Definition: utils.hpp:32
bool operator==(standard_alloc_policy< T > const &, standard_alloc_policy< T2 > const &)
Determines if memory from another allocator can be deallocated from this one.
Definition: allocator.hpp:420
pmem::obj::array< T, N >::const_iterator cbegin(const pmem::obj::array< T, N > &a)
Non-member cbegin.
Definition: array.hpp:789
pmem::obj::array< T, N >::iterator begin(pmem::obj::array< T, N > &a)
Non-member begin.
Definition: array.hpp:829
void swap(pmem::obj::array< T, N > &lhs, pmem::obj::array< T, N > &rhs)
Non-member swap function.
Definition: array.hpp:909
Persistent memory namespace.
Definition: allocation_flag.hpp:15
Resides on pmem property template.
Persistent smart pointer.
Convenience extensions for the resides on pmem property template.
Persistent self-relative smart pointer.
String typedefs for common character types.
Our partial std::string_view implementation.
This is the structure which 'holds' key/value pair.
Definition: radix_tree.hpp:435
This is internal node.
Definition: radix_tree.hpp:501
atomic_pointer_type parent
Pointer to a parent node.
Definition: radix_tree.hpp:507
byten_t byte
Byte and bit together are used to calculate the NIB which is used to index the child array.
Definition: radix_tree.hpp:530
atomic_pointer_type embedded_entry
The embedded_entry ptr is used only for nodes for which length of the path from root is a multiple of...
Definition: radix_tree.hpp:515
Radix tree iterator supports multipass and bidirectional iteration.
Definition: radix_tree.hpp:605
Commonly used SFINAE helpers.
C++ pmemobj transactions.
Volatile residing on pmem property template.