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>
588 template <
bool Direction = direction::Forward,
589 typename Enable =
typename std::enable_if<
590 Direction == direction::Forward>::type>
593 uint8_t padding[256 -
sizeof(parent) -
sizeof(
leaf) -
sizeof(child) -
594 sizeof(
byte) -
sizeof(bit)];
602template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
603template <
bool IsConst>
607 typename std::conditional<IsConst, const leaf *, leaf *>::type;
608 using tree_ptr =
typename std::conditional<IsConst,
const radix_tree *,
613 using difference_type = std::ptrdiff_t;
615 using reference =
typename std::conditional<IsConst,
const value_type &,
617 using pointer =
typename std::conditional<IsConst,
value_type const *,
619 using iterator_category =
typename std::conditional<
620 MtMode, std::forward_iterator_tag,
621 std::bidirectional_iterator_tag>::type;
627 template <
bool C = IsConst,
628 typename Enable =
typename std::enable_if<C>::type>
634 reference operator*()
const;
635 pointer operator->()
const;
637 template <
typename V = Value,
638 typename Enable =
typename std::enable_if<
639 detail::is_inline_string<V>::value>::type>
641 typename V::traits_type>
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);
650 template <
bool Mt = MtMode,
651 typename Enable =
typename std::enable_if<!Mt>::type>
655 template <
bool Mt = MtMode,
656 typename Enable =
typename std::enable_if<!Mt>::type>
668 leaf_ptr leaf_ =
nullptr;
669 tree_ptr tree =
nullptr;
671 template <
typename T>
672 void replace_val(T &&rhs);
674 bool try_increment();
675 bool try_decrement();
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;
686 forward_iterator(pointer child,
const node *
node);
693 reference operator*()
const;
694 pointer operator->()
const;
696 pointer get_node()
const;
698 bool operator!=(
const forward_iterator &rhs)
const;
699 bool operator==(
const forward_iterator &rhs)
const;
714template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
716 : root(nullptr), size_(0)
741template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
742template <
class InputIt>
745 : root(nullptr), size_(0)
750 for (
auto it = first; it != last; it++)
769template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
771 : root(nullptr), size_(0)
776 for (
auto it = m.
cbegin(); it != m.
cend(); it++)
792template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
796 check_tx_stage_work();
798 store(root, load(m.root));
800 store(m.root,
nullptr);
818template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
820 std::initializer_list<value_type> il)
834template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
842 if (
this != &other) {
846 store(this->root,
nullptr);
849 for (
auto it = other.
cbegin(); it != other.
cend(); it++)
865template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
873 if (
this != &other) {
877 store(this->root, load(other.root));
878 this->size_ = other.size_;
879 store(other.root,
nullptr);
897template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
900 std::initializer_list<value_type> ilist)
909 store(this->root,
nullptr);
912 for (
auto it = ilist.begin(); it != ilist.end(); it++)
922template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
927 for (
size_t i = 0; i < EPOCHS_NUMBER; ++i)
939template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
949template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
950typename radix_tree<Key, Value, BytesView, MtMode>::size_type
953 return std::numeric_limits<difference_type>::max();
959template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
971template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
978 this->size_.swap(rhs.size_);
979 this->root.swap(rhs.root);
992template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
993template <
bool Mt,
typename Enable>
998 for (
size_t i = 0; i < EPOCHS_NUMBER; ++i) {
1013template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1014template <
bool Mt,
typename Enable>
1019 clear_garbage(ebr_->gc_epoch());
1022template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1026 assert(n >= 0 && n < EPOCHS_NUMBER);
1031 for (
auto &e : garbages[n]) {
1033 delete_persistent<radix_tree::leaf>(
1037 delete_persistent<radix_tree::node>(
1042 garbages[n].clear();
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)
1051 return ptr.load_acquire();
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)
1061template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1063radix_tree<Key, Value, BytesView, MtMode>::store(
1064 std::atomic<detail::tagged_ptr<leaf, node>> &ptr, pointer_type desired)
1066 ptr.store_with_snapshot_release(desired);
1069template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1071radix_tree<Key, Value, BytesView, MtMode>::store(pointer_type &ptr,
1072 pointer_type desired)
1085template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1086template <
bool Mt,
typename Enable>
1090#if LIBPMEMOBJ_CPP_VG_PMEMCHECK_ENABLED
1091 VALGRIND_PMC_REMOVE_PMEM_MAPPING(&ebr_,
sizeof(
ebr *));
1100template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1101template <
bool Mt,
typename Enable>
1119template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1120template <
bool Mt,
typename Enable>
1121typename radix_tree<Key, Value, BytesView, MtMode>::worker_type
1126 return ebr_->register_worker();
1132template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1133typename radix_tree<Key, Value, BytesView, MtMode>::atomic_pointer_type &
1137 return get_leaf(n)->parent;
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
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);
1163 pointer_type nn =
nullptr;
1164 for (
size_t i = 0; i < SLNODES; i++) {
1165 nn = load(n->child[i]);
1174 return n ? get_leaf(n) : nullptr;
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,
1197 auto slot = &this->root;
1199 decltype(n) prev =
nullptr;
1202 path.reserve(PATH_INIT_CAP);
1203 path.push_back(node_desc{slot, n, prev});
1205 while (n && !is_leaf(n) && n->byte < key.size()) {
1207 slot = &n->child[slice_index(key[n->byte], n->bit)];
1208 auto nn = load(*slot);
1211 path.push_back(node_desc{slot, nn, prev});
1214 path.push_back(node_desc{slot,
nullptr, prev});
1215 n = any_leftmost_leaf(n, key.size());
1221 return {
nullptr, std::move(path)};
1226 n = any_leftmost_leaf(n, key.size());
1230 return std::pair<leaf *, path_type>{get_leaf(n),
1233 return std::pair<leaf *, path_type>{
nullptr, std::move(path)};
1237template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1238template <
typename K>
1240radix_tree<Key, Value, BytesView, MtMode>::bytes_view(
const K &key)
1245 return BytesView(&key);
1248template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1250radix_tree<Key, Value, BytesView, MtMode>::bytes_view(string_view key)
1258template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1259template <
typename K1,
typename K2>
1261radix_tree<Key, Value, BytesView, MtMode>::keys_equal(
const K1 &k1,
1264 return k1.size() == k2.size() && compare(k1, k2) == 0;
1270template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1271template <
typename K1,
typename K2>
1273radix_tree<Key, Value, BytesView, MtMode>::compare(
const K1 &k1,
const K2 &k2,
1276 auto ret = prefix_diff(k1, k2, offset);
1278 if (ret != (std::min)(k1.size(), k2.size()))
1279 return (
unsigned char)(k1[ret]) - (
unsigned char)(k2[ret]);
1281 return k1.size() - k2.size();
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,
1295 for (diff = offset; diff < (std::min)(lhs.size(), rhs.size()); diff++) {
1296 if (lhs[diff] != rhs[diff])
1307template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1309radix_tree<Key, Value, BytesView, MtMode>::path_length_equal(
size_t key_size,
1312 return n->byte == key_size && n->bit == bitn_t(FIRST_NIB);
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)
1321 auto min_key_len = (std::min)(leaf_key.size(), key.size());
1327 if (diff < min_key_len) {
1329 static_cast<unsigned char>(leaf_key[diff] ^ key[diff]);
1330 sh = pmem::detail::mssb_index((uint32_t)at) & SLICE_MASK;
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,
1346 assert(path.size());
1351 while (n.node && !is_leaf(n.node) &&
1352 (n.node->byte < diff ||
1353 (n.node->byte == diff && n.node->bit >= sh))) {
1356 assert(idx < path.size());
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,
1370 auto key = bytes_view(k);
1371 auto pop = pool_base(pmemobj_pool_by_ptr(
this));
1373 auto r = load(root);
1377 leaf = make_leaf(
nullptr);
1378 store(this->root, leaf);
1380 return {iterator(get_leaf(leaf),
this),
true};
1390 auto ret = descend(r, key);
1391 auto leaf = ret.first;
1392 auto path = ret.second;
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);
1401 if (diff == key.size() && leaf_key.size() == key.size())
1402 return {iterator(leaf,
this),
false};
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;
1416 assert(diff < (std::min)(leaf_key.size(), key.size()));
1419 [&] { store(*slot, make_leaf(prev)); });
1420 return {iterator(get_leaf(load(*slot)),
this),
true};
1425 if (diff == key.size()) {
1426 if (!is_leaf(n) && path_length_equal(key.size(), n)) {
1427 assert(!load(n->embedded_entry));
1430 store(n->embedded_entry, make_leaf(n));
1433 return {iterator(get_leaf(load(n->embedded_entry)),
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))],
1449 store(parent_ref(n), node);
1453 return {iterator(get_leaf(load(node->embedded_entry)),
this),
1457 if (diff == leaf_key.size()) {
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))],
1471 store(parent_ref(n), node);
1475 return {iterator(get_leaf(load(node->child[slice_index(
1476 key[diff], bitn_t(FIRST_NIB))])),
1487 node = make_persistent<radix_tree::node>(load(parent_ref(n)),
1489 store(node->child[slice_index(leaf_key[diff], sh)], n);
1490 store(node->child[slice_index(key[diff], sh)], make_leaf(node));
1492 store(parent_ref(n), node);
1497 get_leaf(load(node->child[slice_index(key[diff], sh)])),
1530template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1531template <
class... Args>
1532std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator,
bool>
1536 return internal_emplace(k, [&](pointer_type parent) {
1538 return leaf::make_key_args(parent, k,
1539 std::forward<Args>(args)...);
1569template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1570template <
class... Args>
1571std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator,
bool>
1574 auto pop =
pool_base(pmemobj_pool_by_ptr(
this));
1575 std::pair<iterator, bool> ret;
1578 auto leaf_ = leaf::make(
nullptr, std::forward<Args>(args)...);
1579 auto make_leaf = [&](pointer_type parent) {
1580 store(leaf_->parent, parent);
1585 ret = internal_emplace(leaf_->key(), make_leaf);
1588 delete_persistent<leaf>(leaf_);
1609template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1610std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator,
bool>
1613 return try_emplace(
v.first,
v.second);
1631template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1632std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator,
bool>
1635 return try_emplace(std::move(
v.first), std::move(
v.second));
1657template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1658template <
typename P,
typename>
1659std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator,
bool>
1662 return emplace(std::forward<P>(
p));
1676template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1677template <
typename InputIterator>
1682 for (
auto it = first; it != last; it++)
1683 try_emplace((*it).first, (*it).second);
1696template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1699 std::initializer_list<value_type> il)
1701 insert(il.begin(), il.end());
1728template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1729template <
class... Args>
1730std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator,
bool>
1734 return internal_emplace(k, [&](pointer_type parent) {
1736 return leaf::make_key_args(parent, std::move(k),
1737 std::forward<Args>(args)...);
1769template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1770template <
typename K,
typename BV,
class... Args>
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<
1779 std::pair<
typename radix_tree<Key, Value, BytesView,
1784 return internal_emplace(k, [&](pointer_type parent) {
1786 return leaf::make_key_args(parent, std::forward<K>(k),
1787 std::forward<Args>(args)...);
1809template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1810template <
typename M>
1811std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator,
bool>
1815 auto ret = try_emplace(k, std::forward<M>(obj));
1817 ret.first.assign_val(std::forward<M>(obj));
1839template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1840template <
typename M>
1841std::pair<typename radix_tree<Key, Value, BytesView, MtMode>::iterator,
bool>
1845 auto ret = try_emplace(std::move(k), std::forward<M>(obj));
1847 ret.first.assign_val(std::forward<M>(obj));
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>
1877 auto ret = try_emplace(std::forward<K>(k), std::forward<M>(obj));
1879 ret.first.assign_val(std::forward<M>(obj));
1892template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1893typename radix_tree<Key, Value, BytesView, MtMode>::size_type
1896 return internal_find(k) !=
nullptr ? 1 : 0;
1911template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1912template <
typename K,
typename>
1913typename radix_tree<Key, Value, BytesView, MtMode>::size_type
1916 return internal_find(k) !=
nullptr ? 1 : 0;
1927template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1931 return iterator(internal_find(k),
this);
1942template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1960template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1961template <
typename K,
typename>
1965 return iterator(internal_find(k),
this);
1979template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1980template <
typename K,
typename>
1987template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
1988template <
typename K>
1992 auto key = bytes_view(k);
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())
2001 n = load(n->child[slice_index(key[n->byte], n->bit)]);
2007 if (!keys_equal(key, bytes_view(get_leaf(n)->key())))
2020template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2043template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2047 auto pop =
pool_base(pmemobj_pool_by_ptr(
this));
2050 auto *
leaf = pos.leaf_;
2051 auto parent = load(
leaf->parent);
2063 store(this->root,
nullptr);
2069 store(
const_cast<atomic_pointer_type &
>(
2070 *parent->find_child(
leaf)),
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])) {
2083 only_child = load(n->child[i]);
2087 if (only_child && load(n->embedded_entry)) {
2091 }
else if (load(n->embedded_entry)) {
2092 only_child = load(n->embedded_entry);
2096 store(parent_ref(only_child), load(n->parent));
2098 auto *child_slot = parent ?
const_cast<atomic_pointer_type *
>(
2099 &*parent->find_child(n))
2101 store(*child_slot, only_child);
2106 return iterator(
const_cast<typename iterator::leaf_ptr
>(pos.leaf_),
2123template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2128 auto pop =
pool_base(pmemobj_pool_by_ptr(
this));
2131 while (first != last)
2132 first = erase(first);
2135 return iterator(
const_cast<typename iterator::leaf_ptr
>(first.leaf_),
2151template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2152typename radix_tree<Key, Value, BytesView, MtMode>::size_type
2179template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2180template <
typename K,
typename>
2181typename radix_tree<Key, Value, BytesView, MtMode>::size_type
2198template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2199template <
typename T>
2203 if (MtMode && ebr_ !=
nullptr)
2204 garbages[ebr_->staging_epoch()].emplace_back(ptr);
2206 delete_persistent<T>(ptr);
2213template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2214template <
bool Lower,
typename K>
2223 return (compare(bytes_view(it->key()), bytes_view(key)) >= 0);
2225 return (compare(bytes_view(it->key()), bytes_view(key)) > 0);
2231template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2233typename std::enable_if<Mt, bool>::type
2235 const path_type &path)
const
2237 for (
auto i = 0ULL; i < path.size(); i++) {
2238 if (path[i].
node != load(*path[i].slot))
2242 load(parent_ref(path[i].
node)) != path[i].prev)
2249template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2251typename std::enable_if<!Mt, bool>::type
2253 const path_type &path)
const
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
2263 auto key = bytes_view(k);
2264 auto pop =
pool_base(pmemobj_pool_by_ptr(
this));
2267 const_iterator result;
2270 auto r = load(root);
2282 auto ret = descend(r, key);
2283 auto leaf = ret.first;
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);
2294 if (diff == key.size() && leaf_key.size() == key.size()) {
2295 result = const_iterator(leaf,
this);
2302 if (result.try_increment())
2309 auto node_d = follow_path(path, diff, sh);
2311 auto n = node_d.node;
2312 auto slot = node_d.slot;
2313 auto prev = node_d.prev;
2321 assert(prev && !is_leaf(prev));
2323 auto target_leaf = next_leaf<node::direction::Forward>(
2324 prev->template make_iterator<
2325 node::direction::Forward>(slot),
2328 if (!target_leaf.first)
2331 result = const_iterator(target_leaf.second,
this);
2332 }
else if (diff == key.size()) {
2340 find_leaf<node::direction::Forward>(n);
2345 result = const_iterator(target_leaf,
this);
2346 }
else if (diff == leaf_key.size()) {
2362 auto target_leaf = next_leaf<
2363 node::direction::Forward>(
2364 prev->template make_iterator<
2365 node::direction::Forward>(slot),
2368 if (!target_leaf.first)
2371 result = const_iterator(target_leaf.second,
2375 assert(diff < leaf_key.size() && diff < key.size());
2401 if (
static_cast<unsigned char>(key[diff]) <
2402 static_cast<unsigned char>(leaf_key[diff])) {
2404 find_leaf<node::direction::Forward>(n);
2409 result = const_iterator(target_leaf,
this);
2410 }
else if (slot == &root) {
2411 result = const_iterator(
nullptr,
this);
2414 assert(
static_cast<unsigned char>(key[diff]) >
2415 static_cast<unsigned char>(
2428 auto target_leaf = next_leaf<
2429 node::direction::Forward>(
2430 prev->template make_iterator<
2431 node::direction::Forward>(slot),
2434 if (!target_leaf.first)
2437 result = const_iterator(target_leaf.second,
2444 if (validate_path(path))
2448 assert(validate_bound<Lower>(result, k));
2463template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2464typename radix_tree<Key, Value, BytesView, MtMode>::const_iterator
2467 return internal_bound<true>(k);
2480template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2484 auto it =
const_cast<const radix_tree *
>(
this)->lower_bound(k);
2485 return iterator(
const_cast<typename iterator::leaf_ptr
>(it.leaf_),
2502template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2503template <
typename K,
typename>
2507 auto it =
const_cast<const radix_tree *
>(
this)->lower_bound(k);
2508 return iterator(
const_cast<typename iterator::leaf_ptr
>(it.leaf_),
2525template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2526template <
typename K,
typename>
2530 return internal_bound<true>(k);
2543template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2547 return internal_bound<false>(k);
2560template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2564 auto it =
const_cast<const radix_tree *
>(
this)->upper_bound(k);
2565 return iterator(
const_cast<typename iterator::leaf_ptr
>(it.leaf_),
2582template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2583template <
typename K,
typename>
2587 auto it =
const_cast<const radix_tree *
>(
this)->upper_bound(k);
2588 return iterator(
const_cast<typename iterator::leaf_ptr
>(it.leaf_),
2605template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2606template <
typename K,
typename>
2610 return internal_bound<false>(k);
2619template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2625 const_cast<typename iterator::leaf_ptr
>(const_begin.leaf_),
2636template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2640 auto const_end =
const_cast<const radix_tree *
>(
this)->
end();
2642 const_cast<typename iterator::leaf_ptr
>(const_end.leaf_),
this);
2651template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2656 auto root_ptr = load(root);
2660 auto leaf = find_leaf<radix_tree::node::direction::Forward>(
2675template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2688template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2702template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2716template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2717typename radix_tree<Key, Value, BytesView, MtMode>::reverse_iterator
2720 return reverse_iterator(
end());
2731template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2732typename radix_tree<Key, Value, BytesView, MtMode>::reverse_iterator
2735 return reverse_iterator(
begin());
2745template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2746typename radix_tree<Key, Value, BytesView, MtMode>::const_reverse_iterator
2749 return const_reverse_iterator(
cend());
2760template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2761typename radix_tree<Key, Value, BytesView, MtMode>::const_reverse_iterator
2764 return const_reverse_iterator(
cbegin());
2767template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2768typename radix_tree<Key, Value, BytesView, MtMode>::const_reverse_iterator
2771 return const_reverse_iterator(
cend());
2774template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2775typename radix_tree<Key, Value, BytesView, MtMode>::const_reverse_iterator
2778 return const_reverse_iterator(
cbegin());
2781template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2783radix_tree<Key, Value, BytesView, MtMode>::print_rec(std::ostream &os,
2784 radix_tree::pointer_type 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;
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;
2797 for (
auto it = n->begin(); it != n->end(); ++it) {
2803 auto ch = is_leaf(c) ? (
void *)get_leaf(c)
2804 : (
void *)get_node(c);
2806 os <<
"\"" << get_node(n) <<
"\" -> \"" << ch <<
"\""
2811 auto bv = bytes_view(get_leaf(n)->key());
2813 os <<
"\"" << get_leaf(n) <<
"\" [style=filled,color=\"green\"]"
2815 os <<
"\"" << get_leaf(n) <<
"\" [label=\"key:";
2817 for (
size_t i = 0; i < bv.size(); i++)
2820 os <<
"\"]" << std::endl;
2822 auto p = load(get_leaf(n)->parent);
2823 auto parent = p ? get_node(p) : nullptr;
2825 os <<
"\"" << get_leaf(n) <<
"\" -> \"" << parent
2826 <<
"\" [label=\"parent\"]" << std::endl;
2828 if (parent && n == load(parent->embedded_entry)) {
2829 os <<
"{rank=same;\"" << parent <<
"\";\""
2830 << get_leaf(n) <<
"\"}" << std::endl;
2838template <
typename K,
typename V,
typename BV,
bool MtMode>
2842 os <<
"digraph Radix {" << std::endl;
2848 os <<
"}" << std::endl;
2856template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2858radix_tree<Key, Value, BytesView, MtMode>::slice_index(
char b, uint8_t bit)
2860 return static_cast<unsigned>(b >> bit) & NIB;
2863template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2864radix_tree<Key, Value, BytesView,
2865 MtMode>::node::forward_iterator::forward_iterator(pointer child,
2867 : child(child), n(n)
2871template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2872typename radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator
2875 if (child == &n->embedded_entry)
2876 child = &n->child[0];
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)
2890template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2891typename radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator
2894 if (child == &n->child[0])
2895 child = &n->embedded_entry;
2902template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2903typename radix_tree<Key, Value, BytesView, MtMode>::node::forward_iterator
2907 forward_iterator tmp(child, n);
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
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
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()
2939template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2942 const forward_iterator &rhs)
const
2944 return child == rhs.child && n == rhs.n;
2947template <
typename Key,
typename Value,
typename BytesView,
bool MtMode>
2950 const forward_iterator &rhs)
const
2952 return child != rhs.child || n != rhs.n;
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
2964 return forward_iterator(&embedded_entry,
this);
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
2976 return forward_iterator(&child[SLNODES],
this);
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
2988 return reverse_iterator(end<direction::Forward>());
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
3000 return reverse_iterator(begin<direction::Forward>());
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
3009 auto it = begin<Direction>();
3010 while (it != end<Direction>()) {
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
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>
3110 MtMode>::radix_tree_iterator<IsConst>::replace_val(T &&rhs)
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,
3148 MtMode>::radix_tree_iterator<IsConst>::assign_val(T &&rhs)
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>
3164 MtMode>::radix_tree_iterator<IsConst>::operator++()
3167 if (!try_increment())
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: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
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: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
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:604
Commonly used SFINAE helpers.
C++ pmemobj transactions.
Volatile residing on pmem property template.