16 #ifndef LIBPMEMOBJ_CPP_RADIX_HPP 17 #define LIBPMEMOBJ_CPP_RADIX_HPP 21 #include <libpmemobj++/detail/pair.hpp> 49 template <
typename T,
typename Enable =
void>
56 namespace experimental
101 template <
typename Key,
typename Value,
102 typename BytesView = detail::bytes_view<Key>>
104 template <
bool IsConst>
108 using key_type = Key;
109 using mapped_type = Value;
110 using value_type = detail::pair<const key_type, mapped_type>;
111 using size_type = std::size_t;
116 using reverse_iterator = std::reverse_iterator<iterator>;
117 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
118 using difference_type = std::ptrdiff_t;
122 template <
class InputIt>
126 radix_tree(std::initializer_list<value_type> il);
130 radix_tree &operator=(std::initializer_list<value_type> ilist);
134 template <
class... Args>
135 std::pair<iterator, bool> emplace(Args &&... args);
137 std::pair<iterator, bool> insert(
const value_type &
v);
139 template <
typename P,
140 typename =
typename std::enable_if<
141 std::is_constructible<value_type, P &&>::value,
143 std::pair<iterator, bool> insert(P &&
p);
151 template <
class InputIterator>
152 void insert(InputIterator first, InputIterator last);
153 void insert(std::initializer_list<value_type> il);
157 template <
class... Args>
158 std::pair<iterator, bool> try_emplace(
const key_type &k,
160 template <
class... Args>
161 std::pair<iterator, bool> try_emplace(key_type &&k, Args &&... args);
169 template <
typename K,
typename BV = BytesView,
class... Args>
170 auto try_emplace(K &&k, Args &&... args) ->
typename std::enable_if<
171 detail::has_is_transparent<BV>::value &&
172 !std::is_same<typename std::remove_reference<K>::type,
174 std::pair<iterator, bool>>::type;
176 template <
typename M>
177 std::pair<iterator, bool> insert_or_assign(
const key_type &k, M &&obj);
178 template <
typename M>
179 std::pair<iterator, bool> insert_or_assign(key_type &&k, M &&obj);
186 typename M,
typename K,
187 typename =
typename std::enable_if<
188 detail::has_is_transparent<BytesView>::value, K>::type>
189 std::pair<iterator, bool> insert_or_assign(K &&k, M &&obj);
193 size_type erase(
const key_type &k);
194 template <
typename K,
195 typename =
typename std::enable_if<
196 detail::has_is_transparent<BytesView>::value &&
197 !std::is_same<K, iterator>::value &&
198 !std::is_same<K, const_iterator>::value,
200 size_type erase(
const K &k);
204 size_type count(
const key_type &k)
const;
207 typename =
typename std::enable_if<
208 detail::has_is_transparent<BytesView>::value, K>::type>
209 size_type count(
const K &k)
const;
215 typename =
typename std::enable_if<
216 detail::has_is_transparent<BytesView>::value, K>::type>
220 typename =
typename std::enable_if<
221 detail::has_is_transparent<BytesView>::value, K>::type>
224 iterator lower_bound(
const key_type &k);
228 typename =
typename std::enable_if<
229 detail::has_is_transparent<BytesView>::value, K>::type>
233 typename =
typename std::enable_if<
234 detail::has_is_transparent<BytesView>::value, K>::type>
237 iterator upper_bound(
const key_type &k);
241 typename =
typename std::enable_if<
242 detail::has_is_transparent<BytesView>::value, K>::type>
246 typename =
typename std::enable_if<
247 detail::has_is_transparent<BytesView>::value, K>::type>
257 reverse_iterator
rbegin();
258 reverse_iterator
rend();
259 const_reverse_iterator
crbegin()
const;
260 const_reverse_iterator
crend()
const;
261 const_reverse_iterator
rbegin()
const;
262 const_reverse_iterator
rend()
const;
265 bool empty() const noexcept;
266 size_type max_size() const noexcept;
267 uint64_t size() const noexcept;
271 template <typename K, typename V, typename BV>
272 friend
std::ostream &operator<<(
std::ostream &os,
276 using byten_t = uint64_t;
277 using bitn_t = uint8_t;
280 static constexpr
std::
size_t SLICE = 4;
282 static constexpr
std::
size_t NIB = ((1ULL << SLICE) - 1);
284 static constexpr
std::
size_t SLNODES = (1 << SLICE);
286 static constexpr bitn_t SLICE_MASK = (bitn_t) ~(SLICE - 1);
288 static constexpr bitn_t FIRST_NIB = 8 - SLICE;
290 struct tagged_node_ptr;
295 tagged_node_ptr root;
299 template <typename K, typename F, class... Args>
300 std::pair<
iterator,
bool> internal_emplace(const K &, F &&);
301 template <typename K>
302 leaf *internal_find(const K &k) const;
304 static tagged_node_ptr &parent_ref(tagged_node_ptr n);
305 template <typename K1, typename K2>
306 static
bool keys_equal(const K1 &k1, const K2 &k2);
307 template <typename K1, typename K2>
308 static
int compare(const K1 &k1, const K2 &k2, byten_t offset = 0);
309 template <
bool Direction, typename Iterator>
310 static leaf *next_leaf(Iterator child, tagged_node_ptr parent);
311 template <
bool Direction>
312 static leaf *find_leaf(tagged_node_ptr n);
313 static
unsigned slice_index(
char k, uint8_t shift);
314 template <typename K1, typename K2>
315 static byten_t prefix_diff(const K1 &lhs, const K2 &rhs,
317 leaf *any_leftmost_leaf(tagged_node_ptr n, size_type min_depth) const;
318 template <typename K1, typename K2>
319 static bitn_t bit_diff(const K1 &leaf_key, const K2 &key, byten_t diff);
320 template <typename K>
321 leaf *common_prefix_leaf(const K &key) const;
322 static
void print_rec(
std::ostream &os,
radix_tree::tagged_node_ptr n);
323 template <typename K>
324 static BytesView bytes_view(const K &k);
326 static
bool path_length_equal(
size_t key_size, tagged_node_ptr n);
327 template <typename K>
328 std::tuple<const tagged_node_ptr *, tagged_node_ptr>
329 descend(const K &k, byten_t diff, bitn_t sh) const;
330 template <typename K>
331 std::tuple<tagged_node_ptr *, tagged_node_ptr>
332 descend(const K &k, byten_t diff, bitn_t sh);
333 template <
bool Lower, typename K>
337 void check_tx_stage_work();
339 static_assert(sizeof(node) == 256,
340 "Internal node should have size equal to 256 bytes.");
343 template <typename Key, typename Value, typename BytesView>
347 template <typename Key, typename Value, typename BytesView>
348 struct
radix_tree<Key, Value, BytesView>::tagged_node_ptr {
349 tagged_node_ptr() =
default;
350 tagged_node_ptr(
const tagged_node_ptr &rhs) =
default;
352 tagged_node_ptr(std::nullptr_t);
356 tagged_node_ptr &operator=(
const tagged_node_ptr &rhs) =
default;
358 tagged_node_ptr &operator=(std::nullptr_t);
362 bool operator==(
const tagged_node_ptr &rhs)
const;
363 bool operator!=(
const tagged_node_ptr &rhs)
const;
368 void swap(tagged_node_ptr &rhs);
370 bool is_leaf()
const;
377 explicit operator
bool() const noexcept;
380 static constexpr uintptr_t IS_LEAF = 1;
382 void *remove_tag(
void *ptr) const;
396 template <typename Key, typename Value, typename BytesView>
400 leaf(
const leaf &) =
delete;
401 leaf(leaf &&) =
delete;
403 leaf &operator=(
const leaf &) =
delete;
404 leaf &operator=(leaf &&) =
delete;
411 const Key &key()
const;
412 const Value &value()
const;
415 friend class radix_tree<Key, Value, BytesView>;
419 template <
typename... Args>
425 template <
typename... Args1,
typename... Args2>
427 make_internal(std::piecewise_construct_t pc,
428 std::tuple<Args1...> first_args,
429 std::tuple<Args2...> second_args);
431 template <
typename K,
typename V>
433 template <
typename K,
typename V>
436 template <
typename K,
typename V>
438 template <
typename K,
typename V>
441 template <
typename K,
typename V>
443 template <
typename K,
typename V>
446 template <
typename... Args1,
typename... Args2,
size_t... I1,
449 std::piecewise_construct_t, std::tuple<Args1...> &first_args,
450 std::tuple<Args2...> &second_args,
451 detail::index_sequence<I1...>, detail::index_sequence<I2...>);
455 tagged_node_ptr parent =
nullptr;
462 template <
typename Key,
typename Value,
typename BytesView>
464 node(tagged_node_ptr parent, byten_t byte, bitn_t bit);
480 tagged_node_ptr child[SLNODES];
496 static constexpr
bool Forward = 0;
497 static constexpr
bool Reverse = 1;
500 struct forward_iterator;
501 using reverse_iterator = std::reverse_iterator<forward_iterator>;
503 template <
bool Direction>
505 typename std::conditional<Direction == direction::Forward,
507 reverse_iterator>::type;
509 template <
bool Direction = direction::Forward>
510 typename std::enable_if<
513 BytesView>::node::direction::Forward,
515 BytesView>::node::forward_iterator>::type
518 template <
bool Direction = direction::Forward>
519 typename std::enable_if<
522 BytesView>::node::direction::Forward,
524 BytesView>::node::forward_iterator>::type
528 template <
bool Direction = direction::Forward>
529 typename std::enable_if<
532 BytesView>::node::direction::Reverse,
534 BytesView>::node::reverse_iterator>::type
538 template <
bool Direction = direction::Forward>
539 typename std::enable_if<
542 BytesView>::node::direction::Reverse,
544 BytesView>::node::reverse_iterator>::type
547 template <
bool Direction = direction::Forward,
typename Ptr>
548 auto find_child(
const Ptr &n)
const -> decltype(begin<Direction>());
550 template <
bool Direction = direction::Forward,
551 typename Enable =
typename std::enable_if<
552 Direction == direction::Forward>::type>
553 auto make_iterator(
const tagged_node_ptr *ptr)
const 554 -> decltype(begin<Direction>());
556 uint8_t padding[256 -
sizeof(parent) -
sizeof(leaf) -
sizeof(child) -
557 sizeof(byte) -
sizeof(bit)];
565 template <
typename Key,
typename Value,
typename BytesView>
566 template <
bool IsConst>
570 typename std::conditional<IsConst, const leaf *, leaf *>::type;
572 typename std::conditional<IsConst,
const tagged_node_ptr *,
573 tagged_node_ptr *>::type;
577 using difference_type = std::ptrdiff_t;
579 using reference =
typename std::conditional<IsConst,
const value_type &,
581 using pointer =
typename std::conditional<IsConst, value_type
const *,
583 using iterator_category = std::bidirectional_iterator_tag;
589 template <
bool C = IsConst,
590 typename Enable =
typename std::enable_if<C>::type>
593 radix_tree_iterator &
594 operator=(
const radix_tree_iterator &rhs) =
default;
596 reference operator*()
const;
597 pointer operator->()
const;
599 template <
typename V = Value,
600 typename Enable =
typename std::enable_if<
601 std::is_same<V, inline_string>::value>::type>
604 template <
typename T,
typename V = Value,
605 typename Enable =
typename std::enable_if<
606 !std::is_same<V, inline_string>::value>::type>
607 void assign_val(T &&rhs);
624 leaf_ptr leaf_ =
nullptr;
625 node_ptr root =
nullptr;
628 template <
typename Key,
typename Value,
typename BytesView>
629 struct radix_tree<Key, Value, BytesView>::node::forward_iterator {
630 using difference_type = std::ptrdiff_t;
631 using value_type = tagged_node_ptr;
632 using pointer =
const value_type *;
633 using reference =
const value_type &;
634 using iterator_category = std::forward_iterator_tag;
636 forward_iterator(pointer child,
const node *node);
643 reference operator*()
const;
644 pointer operator->()
const;
646 pointer get_node()
const;
648 bool operator!=(
const forward_iterator &rhs)
const;
649 bool operator==(
const forward_iterator &rhs)
const;
664 template <
typename Key,
typename Value,
typename BytesView>
690 template <
typename Key,
typename Value,
typename BytesView>
691 template <
class InputIt>
693 : root(nullptr), size_(0)
698 for (
auto it = first; it != last; it++)
717 template <
typename Key,
typename Value,
typename BytesView>
726 for (
auto it = m.
cbegin(); it != m.
cend(); it++)
742 template <
typename Key,
typename Value,
typename BytesView>
768 template <
typename Key,
typename Value,
typename BytesView>
770 std::initializer_list<value_type> il)
784 template <
typename Key,
typename Value,
typename BytesView>
792 if (
this != &other) {
796 this->root =
nullptr;
799 for (
auto it = other.
cbegin(); it != other.
cend(); it++)
815 template <
typename Key,
typename Value,
typename BytesView>
823 if (
this != &other) {
827 this->root = other.root;
828 this->size_ = other.size_;
829 other.root =
nullptr;
847 template <
typename Key,
typename Value,
typename BytesView>
850 std::initializer_list<value_type> ilist)
859 this->root =
nullptr;
862 for (
auto it = ilist.begin(); it != ilist.end(); it++)
872 template <
typename Key,
typename Value,
typename BytesView>
887 template <
typename Key,
typename Value,
typename BytesView>
897 template <
typename Key,
typename Value,
typename BytesView>
898 typename radix_tree<Key, Value, BytesView>::size_type
901 return std::numeric_limits<difference_type>::max();
907 template <
typename Key,
typename Value,
typename BytesView>
919 template <
typename Key,
typename Value,
typename BytesView>
926 this->size_.swap(rhs.size_);
927 this->root.swap(rhs.root);
934 template <
typename Key,
typename Value,
typename BytesView>
939 return n.get_leaf()->parent;
950 template <
typename Key,
typename Value,
typename BytesView>
954 size_type min_depth)
const 958 while (!n.is_leaf()) {
959 if (n->embedded_entry && n->byte >= min_depth)
960 return n->embedded_entry.get_leaf();
962 for (
size_t i = 0; i < SLNODES; i++) {
964 if ((m = n->child[i])) {
977 template <
typename Key,
typename Value,
typename BytesView>
978 template <
typename K>
984 while (n && !n.is_leaf() && n->byte < key.
size()) {
985 auto nn = n->child[slice_index(key[n->byte], n->bit)];
990 n = any_leftmost_leaf(n, key.
size());
998 n = any_leftmost_leaf(n, key.
size());
1000 return n.get_leaf();
1003 template <
typename Key,
typename Value,
typename BytesView>
1004 template <
typename K>
1011 return BytesView(&key);
1014 template <
typename Key,
typename Value,
typename BytesView>
1024 template <
typename Key,
typename Value,
typename BytesView>
1025 template <
typename K1,
typename K2>
1029 return k1.
size() == k2.size() && compare(k1, k2) == 0;
1035 template <
typename Key,
typename Value,
typename BytesView>
1036 template <
typename K1,
typename K2>
1041 auto ret = prefix_diff(k1, k2, offset);
1043 if (ret != (std::min)(k1.size(), k2.size()))
1044 return (
unsigned char)(k1[ret]) - (
unsigned char)(k2[ret]);
1046 return k1.size() - k2.size();
1052 template <
typename Key,
typename Value,
typename BytesView>
1053 template <
typename K1,
typename K2>
1054 typename radix_tree<Key, Value, BytesView>::byten_t
1059 for (diff = offset; diff < (std::min)(lhs.size(), rhs.size()); diff++) {
1060 if (lhs[diff] != rhs[diff])
1071 template <
typename Key,
typename Value,
typename BytesView>
1076 return n->byte == key_size && n->bit == bitn_t(FIRST_NIB);
1079 template <
typename Key,
typename Value,
typename BytesView>
1080 template <
typename K1,
typename K2>
1081 typename radix_tree<Key, Value, BytesView>::bitn_t
1085 auto min_key_len = (std::min)(leaf_key.size(), key.size());
1091 if (diff < min_key_len) {
1093 static_cast<unsigned char>(leaf_key[diff] ^ key[diff]);
1094 sh = pmem::detail::mssb_index((uint32_t)at) & SLICE_MASK;
1100 template <
typename Key,
typename Value,
typename BytesView>
1101 template <
typename K>
1102 std::tuple<const typename radix_tree<Key, Value, BytesView>::tagged_node_ptr *,
1111 while (n && !n.is_leaf() &&
1112 (n->byte < diff || (n->byte == diff && n->bit >= sh))) {
1114 slot = &n->child[slice_index(key[n->byte], n->bit)];
1118 return {slot, prev};
1121 template <
typename Key,
typename Value,
typename BytesView>
1122 template <
typename K>
1123 std::tuple<typename radix_tree<Key, Value, BytesView>::tagged_node_ptr *,
1128 const tagged_node_ptr *slot;
1129 tagged_node_ptr prev;
1131 std::tie(slot, prev) =
1132 const_cast<const radix_tree *
>(
this)->descend(key, diff, sh);
1134 return {
const_cast<tagged_node_ptr *
>(slot), prev};
1137 template <
typename Key,
typename Value,
typename BytesView>
1138 template <
typename K,
typename F,
class... Args>
1139 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1142 auto key = bytes_view(k);
1143 auto pop =
pool_base(pmemobj_pool_by_ptr(
this));
1147 return {iterator(root.get_leaf(), &root),
true};
1157 auto leaf = common_prefix_leaf(key);
1158 auto leaf_key = bytes_view(leaf->key());
1159 auto diff = prefix_diff(key, leaf_key);
1160 auto sh = bit_diff(leaf_key, key, diff);
1163 if (diff == key.size() && leaf_key.size() == key.size())
1164 return {iterator(leaf, &root),
false};
1167 tagged_node_ptr *slot;
1168 tagged_node_ptr prev;
1169 std::tie(slot, prev) = descend(key, diff, sh);
1179 assert(diff < (std::min)(leaf_key.size(), key.size()));
1182 return {iterator(slot->get_leaf(), &root),
true};
1187 if (diff == key.size()) {
1188 if (!n.is_leaf() && path_length_equal(key.size(), n)) {
1189 assert(!n->embedded_entry);
1192 pop, [&] { n->embedded_entry = make_leaf(n); });
1194 return {iterator(n->embedded_entry.get_leaf(), &root),
1200 tagged_node_ptr node;
1202 node = make_persistent<radix_tree::node>(
1203 parent_ref(n), diff, bitn_t(FIRST_NIB));
1204 node->embedded_entry = make_leaf(node);
1205 node->child[slice_index(leaf_key[diff],
1206 bitn_t(FIRST_NIB))] = n;
1208 parent_ref(n) = node;
1212 return {iterator(node->embedded_entry.get_leaf(), &root),
true};
1215 if (diff == leaf_key.size()) {
1218 tagged_node_ptr node;
1222 node = make_persistent<radix_tree::node>(
1223 parent_ref(n), diff, bitn_t(FIRST_NIB));
1224 node->embedded_entry = n;
1225 node->child[slice_index(key[diff], bitn_t(FIRST_NIB))] =
1228 parent_ref(n) = node;
1232 return {iterator(node->child[slice_index(key[diff],
1243 tagged_node_ptr node;
1245 node = make_persistent<radix_tree::node>(parent_ref(n), diff,
1247 node->child[slice_index(leaf_key[diff], sh)] = n;
1248 node->child[slice_index(key[diff], sh)] = make_leaf(node);
1250 parent_ref(n) = node;
1254 return {iterator(node->child[slice_index(key[diff], sh)].get_leaf(),
1287 template <
typename Key,
typename Value,
typename BytesView>
1288 template <
class... Args>
1289 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1293 return internal_emplace(k, [&](tagged_node_ptr parent) {
1295 return leaf::make(parent, k, std::forward<Args>(args)...);
1325 template <
typename Key,
typename Value,
typename BytesView>
1326 template <
class... Args>
1327 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1330 auto pop =
pool_base(pmemobj_pool_by_ptr(
this));
1331 std::pair<iterator, bool> ret;
1334 auto leaf_ = leaf::make(
nullptr, std::forward<Args>(args)...);
1335 auto make_leaf = [&](tagged_node_ptr parent) {
1336 leaf_->parent = parent;
1341 ret = internal_emplace(leaf_->key(), make_leaf);
1344 delete_persistent<leaf>(leaf_);
1365 template <
typename Key,
typename Value,
typename BytesView>
1366 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1387 template <
typename Key,
typename Value,
typename BytesView>
1388 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1391 return emplace(std::move(
v));
1413 template <
typename Key,
typename Value,
typename BytesView>
1414 template <
typename P,
typename>
1415 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1418 return emplace(std::forward<P>(
p));
1432 template <
typename Key,
typename Value,
typename BytesView>
1433 template <
typename InputIterator>
1438 for (
auto it = first; it != last; it++)
1452 template <
typename Key,
typename Value,
typename BytesView>
1456 insert(il.begin(), il.end());
1483 template <
typename Key,
typename Value,
typename BytesView>
1484 template <
class... Args>
1485 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1488 return internal_emplace(k, [&](tagged_node_ptr parent) {
1490 return leaf::make(parent, std::move(k),
1491 std::forward<Args>(args)...);
1523 template <
typename Key,
typename Value,
typename BytesView>
1524 template <
typename K,
typename BV,
class... Args>
1527 typename std::enable_if<
1528 detail::has_is_transparent<BV>::value &&
1529 !std::is_same<typename std::remove_reference<K>::type,
1531 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
1535 return internal_emplace(k, [&](tagged_node_ptr parent) {
1537 return leaf::make(parent, std::forward<K>(k),
1538 std::forward<Args>(args)...);
1560 template <
typename Key,
typename Value,
typename BytesView>
1561 template <
typename M>
1562 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1565 auto ret = try_emplace(k, std::forward<M>(obj));
1567 ret.first.assign_val(std::forward<M>(obj));
1589 template <
typename Key,
typename Value,
typename BytesView>
1590 template <
typename M>
1591 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1594 auto ret = try_emplace(std::move(k), std::forward<M>(obj));
1596 ret.first.assign_val(std::forward<M>(obj));
1621 template <
typename Key,
typename Value,
typename BytesView>
1622 template <
typename M,
typename K,
typename>
1623 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1626 auto ret = try_emplace(std::forward<K>(k), std::forward<M>(obj));
1628 ret.first.assign_val(std::forward<M>(obj));
1641 template <
typename Key,
typename Value,
typename BytesView>
1642 typename radix_tree<Key, Value, BytesView>::size_type
1645 return internal_find(k) !=
nullptr ? 1 : 0;
1660 template <
typename Key,
typename Value,
typename BytesView>
1661 template <
typename K,
typename>
1662 typename radix_tree<Key, Value, BytesView>::size_type
1665 return internal_find(k) !=
nullptr ? 1 : 0;
1676 template <
typename Key,
typename Value,
typename BytesView>
1680 return iterator(internal_find(k), &root);
1691 template <
typename Key,
typename Value,
typename BytesView>
1709 template <
typename Key,
typename Value,
typename BytesView>
1710 template <
typename K,
typename>
1714 return iterator(internal_find(k), &root);
1728 template <
typename Key,
typename Value,
typename BytesView>
1729 template <
typename K,
typename>
1736 template <
typename Key,
typename Value,
typename BytesView>
1737 template <
typename K>
1741 auto key = bytes_view(k);
1744 while (n && !n.is_leaf()) {
1745 if (path_length_equal(key.size(), n))
1746 n = n->embedded_entry;
1747 else if (n->byte > key.size())
1750 n = n->child[slice_index(key[n->byte], n->bit)];
1756 if (!keys_equal(key, bytes_view(n.get_leaf()->key())))
1759 return n.get_leaf();
1769 template <
typename Key,
typename Value,
typename BytesView>
1792 template <
typename Key,
typename Value,
typename BytesView>
1796 auto pop =
pool_base(pmemobj_pool_by_ptr(
this));
1799 auto *leaf = pos.leaf_;
1800 auto parent = leaf->parent;
1802 delete_persistent<radix_tree::leaf>(
1809 this->root =
nullptr;
1817 const_cast<tagged_node_ptr &
>(*parent->find_child(leaf)) =
1823 tagged_node_ptr only_child =
nullptr;
1824 for (
size_t i = 0; i < SLNODES; i++) {
1830 only_child = n->child[i];
1834 if (only_child && n->embedded_entry) {
1838 }
else if (n->embedded_entry) {
1839 only_child = n->embedded_entry;
1843 parent_ref(only_child) = n->parent;
1845 auto *child_slot = parent
1846 ?
const_cast<tagged_node_ptr *
>(&*parent->find_child(n))
1848 *child_slot = only_child;
1850 delete_persistent<radix_tree::node>(n.get_node());
1853 return iterator(const_cast<typename iterator::leaf_ptr>(pos.leaf_),
1870 template <
typename Key,
typename Value,
typename BytesView>
1875 auto pop =
pool_base(pmemobj_pool_by_ptr(
this));
1878 while (first != last)
1879 first =
erase(first);
1882 return iterator(const_cast<typename iterator::leaf_ptr>(first.leaf_),
1898 template <
typename Key,
typename Value,
typename BytesView>
1899 typename radix_tree<Key, Value, BytesView>::size_type
1927 template <
typename Key,
typename Value,
typename BytesView>
1928 template <
typename K,
typename>
1929 typename radix_tree<Key, Value, BytesView>::size_type
1942 template <
typename Key,
typename Value,
typename BytesView>
1943 template <
bool Lower,
typename K>
1947 auto key = bytes_view(k);
1948 auto pop =
pool_base(pmemobj_pool_by_ptr(
this));
1960 auto leaf = common_prefix_leaf(key);
1961 auto leaf_key = bytes_view(leaf->key());
1962 auto diff = prefix_diff(key, leaf_key);
1963 auto sh = bit_diff(leaf_key, key, diff);
1966 if (diff == key.size() && leaf_key.size() == key.size()) {
1974 const tagged_node_ptr *slot;
1975 tagged_node_ptr prev;
1976 std::tie(slot, prev) = descend(key, diff, sh);
1979 leaf = next_leaf<node::direction::Forward>(
1980 prev->template make_iterator<node::direction::Forward>(
1992 if (diff == key.size()) {
1993 leaf = find_leaf<node::direction::Forward>(*slot);
2000 if (diff == leaf_key.size())
2004 assert(diff < leaf_key.size() && diff < key.size());
2008 if (compare(key, leaf_key, diff) < 0) {
2009 leaf = find_leaf<node::direction::Forward>(*slot);
2013 if (slot == &root) {
2019 leaf = next_leaf<node::direction::Forward>(
2020 prev->template make_iterator<node::direction::Forward>(slot),
2036 template <
typename Key,
typename Value,
typename BytesView>
2040 return internal_bound<true>(k);
2053 template <
typename Key,
typename Value,
typename BytesView>
2058 return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2075 template <
typename Key,
typename Value,
typename BytesView>
2076 template <
typename K,
typename>
2081 return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2098 template <
typename Key,
typename Value,
typename BytesView>
2099 template <
typename K,
typename>
2103 return internal_bound<true>(k);
2116 template <
typename Key,
typename Value,
typename BytesView>
2120 return internal_bound<false>(k);
2133 template <
typename Key,
typename Value,
typename BytesView>
2138 return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2155 template <
typename Key,
typename Value,
typename BytesView>
2156 template <
typename K,
typename>
2161 return iterator(const_cast<typename iterator::leaf_ptr>(it.leaf_),
2178 template <
typename Key,
typename Value,
typename BytesView>
2179 template <
typename K,
typename>
2183 return internal_bound<false>(k);
2192 template <
typename Key,
typename Value,
typename BytesView>
2198 const_cast<typename iterator::leaf_ptr>(const_begin.leaf_),
2209 template <
typename Key,
typename Value,
typename BytesView>
2213 auto const_end =
const_cast<const radix_tree *
>(
this)->
end();
2215 const_cast<typename iterator::leaf_ptr>(const_end.leaf_),
2225 template <
typename Key,
typename Value,
typename BytesView>
2233 radix_tree::find_leaf<radix_tree::node::direction::Forward>(
2245 template <
typename Key,
typename Value,
typename BytesView>
2258 template <
typename Key,
typename Value,
typename BytesView>
2272 template <
typename Key,
typename Value,
typename BytesView>
2284 template <
typename Key,
typename Value,
typename BytesView>
2285 typename radix_tree<Key, Value, BytesView>::reverse_iterator
2288 return reverse_iterator(
end());
2297 template <
typename Key,
typename Value,
typename BytesView>
2298 typename radix_tree<Key, Value, BytesView>::reverse_iterator
2301 return reverse_iterator(
begin());
2309 template <
typename Key,
typename Value,
typename BytesView>
2310 typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
2313 return const_reverse_iterator(
cend());
2322 template <
typename Key,
typename Value,
typename BytesView>
2323 typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
2326 return const_reverse_iterator(
cbegin());
2329 template <
typename Key,
typename Value,
typename BytesView>
2330 typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
2333 return const_reverse_iterator(
cend());
2336 template <
typename Key,
typename Value,
typename BytesView>
2337 typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
2340 return const_reverse_iterator(
cbegin());
2343 template <
typename Key,
typename Value,
typename BytesView>
2346 radix_tree::tagged_node_ptr n)
2349 os <<
"\"" << n.get_node() <<
"\"" 2350 <<
" [style=filled,color=\"blue\"]" << std::endl;
2351 os <<
"\"" << n.get_node() <<
"\" [label=\"byte:" << n->byte
2352 <<
", bit:" << int(n->bit) <<
"\"]" << std::endl;
2354 auto parent = n->parent ? n->parent.get_node() : 0;
2355 os <<
"\"" << n.get_node() <<
"\" -> " 2356 <<
"\"" << parent <<
"\" [label=\"parent\"]" << std::endl;
2358 for (
auto it = n->begin(); it != n->end(); ++it) {
2362 auto ch = it->is_leaf() ? (
void *)it->get_leaf()
2363 : (
void *)it->get_node();
2365 os <<
"\"" << n.get_node() <<
"\" -> \"" << ch <<
"\"" 2370 auto bv = bytes_view(n.get_leaf()->key());
2372 os <<
"\"" << n.get_leaf()
2373 <<
"\" [style=filled,color=\"green\"]" << std::endl;
2374 os <<
"\"" << n.get_leaf() <<
"\" [label=\"key:";
2376 for (
size_t i = 0; i < bv.size(); i++)
2379 os <<
"\"]" << std::endl;
2381 auto parent = n.get_leaf()->parent
2382 ? n.get_leaf()->parent.get_node()
2385 os <<
"\"" << n.get_leaf() <<
"\" -> \"" << parent
2386 <<
"\" [label=\"parent\"]" << std::endl;
2388 if (parent && n == parent->embedded_entry) {
2389 os <<
"{rank=same;\"" << parent <<
"\";\"" 2390 << n.get_leaf() <<
"\"}" << std::endl;
2398 template <
typename K,
typename V,
typename BV>
2400 operator<<(std::ostream &os, const radix_tree<K, V, BV> &tree)
2402 os <<
"digraph Radix {" << std::endl;
2407 os <<
"}" << std::endl;
2415 template <
typename Key,
typename Value,
typename BytesView>
2419 return static_cast<unsigned>(b >> bit) & NIB;
2422 template <
typename Key,
typename Value,
typename BytesView>
2427 assert(!(
bool)*
this);
2430 template <
typename Key,
typename Value,
typename BytesView>
2433 : ptr(add_tag(ptr.
get()))
2435 assert(get_leaf() == ptr.
get());
2438 template <
typename Key,
typename Value,
typename BytesView>
2443 assert(get_node() == ptr.
get());
2446 template <
typename Key,
typename Value,
typename BytesView>
2452 assert(!(
bool)*
this);
2457 template <
typename Key,
typename Value,
typename BytesView>
2462 ptr = add_tag(rhs.
get());
2463 assert(get_leaf() == rhs.
get());
2468 template <
typename Key,
typename Value,
typename BytesView>
2474 assert(get_node() == rhs.
get());
2479 template <
typename Key,
typename Value,
typename BytesView>
2482 const radix_tree::tagged_node_ptr &rhs)
const 2484 return ptr.to_byte_pointer() == rhs.ptr.to_byte_pointer();
2487 template <
typename Key,
typename Value,
typename BytesView>
2490 const radix_tree::tagged_node_ptr &rhs)
const 2492 return !(*
this == rhs);
2495 template <
typename Key,
typename Value,
typename BytesView>
2500 return is_leaf() && get_leaf() == rhs;
2503 template <
typename Key,
typename Value,
typename BytesView>
2508 return !(*
this == rhs);
2511 template <
typename Key,
typename Value,
typename BytesView>
2518 template <
typename Key,
typename Value,
typename BytesView>
2523 auto tagged =
reinterpret_cast<uintptr_t
>(ptr) | uintptr_t(IS_LEAF);
2527 template <
typename Key,
typename Value,
typename BytesView>
2531 auto untagged =
reinterpret_cast<uintptr_t
>(ptr) & ~uintptr_t(IS_LEAF);
2532 return reinterpret_cast<void *
>(untagged);
2535 template <
typename Key,
typename Value,
typename BytesView>
2539 auto value =
reinterpret_cast<uintptr_t
>(ptr.to_void_pointer());
2540 return value & uintptr_t(IS_LEAF);
2543 template <
typename Key,
typename Value,
typename BytesView>
2549 remove_tag(ptr.to_void_pointer()));
2552 template <
typename Key,
typename Value,
typename BytesView>
2560 template <
typename Key,
typename Value,
typename BytesView>
2564 return remove_tag(ptr.to_void_pointer()) !=
nullptr;
2567 template <
typename Key,
typename Value,
typename BytesView>
2575 template <
typename Key,
typename Value,
typename BytesView>
2577 pointer child,
const node *n)
2578 : child(child), n(n)
2582 template <
typename Key,
typename Value,
typename BytesView>
2586 if (child == &n->embedded_entry)
2587 child = &n->child[0];
2594 template <
typename Key,
typename Value,
typename BytesView>
2596 byten_t byte, bitn_t bit)
2597 : parent(parent), byte(byte), bit(bit)
2601 template <
typename Key,
typename Value,
typename BytesView>
2605 if (child == &n->child[0])
2606 child = &n->embedded_entry;
2613 template <
typename Key,
typename Value,
typename BytesView>
2617 forward_iterator tmp(child, n);
2622 template <
typename Key,
typename Value,
typename BytesView>
2623 typename radix_tree<Key, Value, BytesView>::node::forward_iterator::reference
2630 template <
typename Key,
typename Value,
typename BytesView>
2631 typename radix_tree<Key, Value, BytesView>::node::forward_iterator::pointer
2638 template <
typename Key,
typename Value,
typename BytesView>
2639 typename radix_tree<Key, Value, BytesView>::node::forward_iterator::pointer
2645 template <
typename Key,
typename Value,
typename BytesView>
2648 const forward_iterator &rhs)
const 2650 return child == rhs.child && n == rhs.n;
2653 template <
typename Key,
typename Value,
typename BytesView>
2656 const forward_iterator &rhs)
const 2658 return child != rhs.child || n != rhs.n;
2661 template <
typename Key,
typename Value,
typename BytesView>
2662 template <
bool Direction>
2663 typename std::enable_if<
2667 BytesView>::node::forward_iterator>::type
2670 return forward_iterator(&embedded_entry,
this);
2673 template <
typename Key,
typename Value,
typename BytesView>
2674 template <
bool Direction>
2675 typename std::enable_if<
2679 BytesView>::node::forward_iterator>::type
2682 return forward_iterator(&child[SLNODES],
this);
2685 template <
typename Key,
typename Value,
typename BytesView>
2686 template <
bool Direction>
2687 typename std::enable_if<
2691 BytesView>::node::reverse_iterator>::type
2694 return reverse_iterator(end<direction::Forward>());
2697 template <
typename Key,
typename Value,
typename BytesView>
2698 template <
bool Direction>
2699 typename std::enable_if<
2703 BytesView>::node::reverse_iterator>::type
2706 return reverse_iterator(begin<direction::Forward>());
2709 template <
typename Key,
typename Value,
typename BytesView>
2710 template <
bool Direction,
typename Ptr>
2713 -> decltype(begin<Direction>())
2715 return std::find(begin<Direction>(), end<Direction>(), n);
2718 template <
typename Key,
typename Value,
typename BytesView>
2719 template <
bool Direction,
typename Enable>
2722 const tagged_node_ptr *ptr)
const -> decltype(begin<Direction>())
2724 return forward_iterator(ptr,
this);
2727 template <
typename Key,
typename Value,
typename BytesView>
2728 template <
bool IsConst>
2730 IsConst>::radix_tree_iterator(leaf_ptr leaf_, node_ptr root)
2731 : leaf_(leaf_), root(root)
2735 template <
typename Key,
typename Value,
typename BytesView>
2736 template <
bool IsConst>
2737 template <
bool C,
typename Enable>
2739 IsConst>::radix_tree_iterator(
const radix_tree_iterator<false> &rhs)
2744 template <
typename Key,
typename Value,
typename BytesView>
2745 template <
bool IsConst>
2747 BytesView>::template radix_tree_iterator<IsConst>::reference
2749 BytesView>::radix_tree_iterator<IsConst>::operator*()
const 2755 template <
typename Key,
typename Value,
typename BytesView>
2756 template <
bool IsConst>
2758 BytesView>::template radix_tree_iterator<IsConst>::pointer
2760 BytesView>::radix_tree_iterator<IsConst>::operator->()
const 2775 template <
typename Key,
typename Value,
typename BytesView>
2776 template <
bool IsConst>
2777 template <
typename V,
typename Enable>
2782 auto pop =
pool_base(pmemobj_pool_by_ptr(leaf_));
2784 if (rhs.
size() <= leaf_->value().capacity()) {
2787 tagged_node_ptr *slot;
2789 if (!leaf_->parent) {
2790 assert(root->get_leaf() == leaf_);
2793 slot =
const_cast<tagged_node_ptr *
>(
2794 &*leaf_->parent->find_child(leaf_));
2797 auto old_leaf = leaf_;
2800 *slot = leaf::make(old_leaf->parent, old_leaf->key(),
2802 delete_persistent<typename radix_tree::leaf>(old_leaf);
2805 leaf_ = slot->get_leaf();
2814 template <
typename Key,
typename Value,
typename BytesView>
2815 template <
bool IsConst>
2816 template <
typename T,
typename V,
typename Enable>
2821 auto pop =
pool_base(pmemobj_pool_by_ptr(leaf_));
2826 template <
typename Key,
typename Value,
typename BytesView>
2827 template <
bool IsConst>
2838 auto it = leaf_->parent->template find_child<
2839 radix_tree::node::direction::Forward>(leaf_);
2841 leaf_ =
const_cast<leaf_ptr
>(
2842 next_leaf<radix_tree::node::direction::Forward>(
2843 it, leaf_->parent));
2849 template <
typename Key,
typename Value,
typename BytesView>
2850 template <
bool IsConst>
2857 leaf_ =
const_cast<leaf_ptr
>(
2858 radix_tree::find_leaf<
2859 radix_tree::node::direction::Reverse>(*root));
2862 assert(leaf_->parent);
2864 auto it = leaf_->parent->template find_child<
2865 radix_tree::node::direction::Reverse>(leaf_);
2867 leaf_ =
const_cast<leaf_ptr
>(
2868 next_leaf<radix_tree::node::direction::Reverse>(
2869 it, leaf_->parent));
2875 template <
typename Key,
typename Value,
typename BytesView>
2876 template <
bool IsConst>
2888 template <
typename Key,
typename Value,
typename BytesView>
2889 template <
bool IsConst>
2901 template <
typename Key,
typename Value,
typename BytesView>
2902 template <
bool IsConst>
2908 return leaf_ != rhs.leaf_;
2911 template <
typename Key,
typename Value,
typename BytesView>
2912 template <
bool IsConst>
2918 return !(*
this != rhs);
2926 template <
typename Key,
typename Value,
typename BytesView>
2927 template <
bool Direction,
typename Iterator>
2930 tagged_node_ptr parent)
2934 }
while (node != parent->template end<Direction>() && !(*node));
2937 if (node == parent->template end<Direction>()) {
2938 auto p = parent->parent;
2942 auto p_it =
p->template find_child<Direction>(parent);
2943 return next_leaf<Direction>(p_it,
p);
2946 return find_leaf<Direction>(*node);
2953 template <
typename Key,
typename Value,
typename BytesView>
2954 template <
bool Direction>
2962 return n.get_leaf();
2964 for (
auto it = n->template begin<Direction>();
2965 it != n->template end<Direction>(); ++it) {
2967 return find_leaf<Direction>(*it);
2974 template <
typename Key,
typename Value,
typename BytesView>
2975 template <
typename... Args>
2980 auto ptr = make_internal(std::forward<Args>(args)...);
2981 ptr->parent = parent;
2986 template <
typename Key,
typename Value,
typename BytesView>
2990 return *
reinterpret_cast<Key *
>(
this + 1);
2993 template <
typename Key,
typename Value,
typename BytesView>
2997 auto key_dst =
reinterpret_cast<char *
>(
this + 1);
2998 auto val_dst =
reinterpret_cast<Value *
>(
3001 return *
reinterpret_cast<Value *
>(val_dst);
3004 template <
typename Key,
typename Value,
typename BytesView>
3008 return *
reinterpret_cast<const Key *
>(
this + 1);
3011 template <
typename Key,
typename Value,
typename BytesView>
3015 auto key_dst =
reinterpret_cast<const char *
>(
this + 1);
3016 auto val_dst =
reinterpret_cast<const Value *
>(
3019 return *
reinterpret_cast<const Value *
>(val_dst);
3022 template <
typename Key,
typename Value,
typename BytesView>
3025 detail::destroy<Key>(key());
3026 detail::destroy<Value>(value());
3029 template <
typename Key,
typename Value,
typename BytesView>
3033 auto t = std::make_tuple();
3034 return make_internal(std::piecewise_construct, t, t,
3035 typename detail::make_index_sequence<>::type{},
3036 typename detail::make_index_sequence<>::type{});
3039 template <
typename Key,
typename Value,
typename BytesView>
3040 template <
typename... Args1,
typename... Args2>
3043 std::piecewise_construct_t pc, std::tuple<Args1...> first_args,
3044 std::tuple<Args2...> second_args)
3046 return make_internal(
3047 pc, first_args, second_args,
3048 typename detail::make_index_sequence<Args1...>::type{},
3049 typename detail::make_index_sequence<Args2...>::type{});
3052 template <
typename Key,
typename Value,
typename BytesView>
3053 template <
typename K,
typename V>
3057 return make_internal(std::piecewise_construct,
3058 std::forward_as_tuple(std::forward<K>(k)),
3059 std::forward_as_tuple(std::forward<V>(
v)));
3062 template <
typename Key,
typename Value,
typename BytesView>
3063 template <
typename K,
typename V>
3067 return make_internal(std::piecewise_construct, std::forward_as_tuple(k),
3068 std::forward_as_tuple(v));
3071 template <
typename Key,
typename Value,
typename BytesView>
3072 template <
typename K,
typename V>
3076 return make_internal(std::piecewise_construct,
3077 std::forward_as_tuple(std::forward<K>(
p.first)),
3078 std::forward_as_tuple(std::forward<V>(
p.second)));
3081 template <
typename Key,
typename Value,
typename BytesView>
3082 template <
typename K,
typename V>
3085 const detail::pair<K, V> &
p)
3087 return make_internal(std::piecewise_construct,
3088 std::forward_as_tuple(p.first),
3089 std::forward_as_tuple(p.second));
3092 template <
typename Key,
typename Value,
typename BytesView>
3093 template <
typename K,
typename V>
3097 return make_internal(std::piecewise_construct,
3098 std::forward_as_tuple(std::forward<K>(p.first)),
3099 std::forward_as_tuple(std::forward<V>(p.second)));
3102 template <
typename Key,
typename Value,
typename BytesView>
3103 template <
typename K,
typename V>
3107 return make_internal(std::piecewise_construct,
3108 std::forward_as_tuple(p.first),
3109 std::forward_as_tuple(p.second));
3112 template <
typename Key,
typename Value,
typename BytesView>
3113 template <
typename... Args1,
typename... Args2,
size_t... I1,
size_t... I2>
3116 std::piecewise_construct_t, std::tuple<Args1...> &first_args,
3117 std::tuple<Args2...> &second_args, detail::index_sequence<I1...>,
3118 detail::index_sequence<I2...>)
3125 a.
allocate(
sizeof(leaf) + key_size + val_size));
3127 auto key_dst =
reinterpret_cast<Key *
>(ptr.get() + 1);
3128 auto val_dst =
reinterpret_cast<Value *
>(
3129 reinterpret_cast<char *
>(key_dst) + key_size);
3131 new (ptr.get()) leaf();
3132 new (key_dst) Key(std::forward<Args1>(std::get<I1>(first_args))...);
3133 new (val_dst) Value(std::forward<Args2>(std::get<I2>(second_args))...);
3138 template <
typename Key,
typename Value,
typename BytesView>
3142 return make_internal(other.key(), other.value());
3151 template <
typename Key,
typename Value,
typename BytesView>
3155 if (
nullptr == pmemobj_pool_by_ptr(
this))
3166 template <
typename Key,
typename Value,
typename BytesView>
3170 if (pmemobj_tx_stage() != TX_STAGE_WORK)
3172 "Function called out of transaction scope.");
3178 template <
typename Key,
typename Value,
typename BytesView>
3191 template <
typename T>
3192 struct bytes_view<T, typename std::enable_if<is_string<T>::value>::type> {
3193 using CharT =
typename T::value_type;
3194 using Traits =
typename T::traits_type;
3198 typename Enable =
typename std::enable_if<std::is_constructible<
3200 bytes_view(
const C *s) : s(*s)
3204 char operator[](std::size_t
p)
const 3206 return static_cast<char>(s[p]);
3215 obj::basic_string_view<CharT, Traits> s;
3217 using is_transparent = void;
3220 template <
typename T>
3221 struct bytes_view<T,
3222 typename std::enable_if<std::is_integral<T>::value &&
3223 !std::is_signed<T>::value>::type> {
3224 bytes_view(
const T *k) : k(k)
3226 #if __cpp_lib_endian 3228 std::endian::native == std::endian::little,
3229 "Scalar type are not little endian on this platform!");
3230 #elif !defined(NDEBUG) 3232 uint16_t word = (2 << 8) + 1;
3233 assert(((
char *)&word)[0] == 1);
3237 char operator[](std::size_t
p)
const 3239 return reinterpret_cast<const char *
>(k)[
size() - p - 1];
iterator begin()
Returns an iterator to the first element of the container.
Definition: radix_tree.hpp:2194
pointer allocate(size_type cnt, const_pointer=0)
Allocate storage for cnt bytes.
Definition: allocator.hpp:357
tagged_node_ptr parent
Pointer to a parent node.
Definition: radix_tree.hpp:469
tagged_node_ptr embedded_entry
The embedded_entry ptr is used only for nodes for which length of the path from root is a multiple of...
Definition: radix_tree.hpp:477
pmem::obj::array< T, N >::const_reverse_iterator crbegin(const pmem::obj::array< T, N > &a)
Non-member crbegin.
Definition: array.hpp:780
radix_tree()
Default radix tree constructor.
Definition: radix_tree.hpp:665
Persistent self-relative smart pointer.
pmem::obj::array< T, N >::reverse_iterator rbegin(pmem::obj::array< T, N > &a)
Non-member rbegin.
Definition: array.hpp:840
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:492
Persistent pointer class.
Definition: common.hpp:107
Persistent_ptr transactional allocation functions for objects.
The non-template pool base class.
Definition: pool.hpp:46
size_type max_size() const noexcept
Definition: radix_tree.hpp:899
void swap(persistent_ptr_base &other)
Swaps two persistent_ptr objects of the same type.
Definition: persistent_ptr_base.hpp:136
A helper trait which calculates required memory capacity (in bytes) for a type.
Definition: inline_string.hpp:281
Radix tree is an associative, ordered container.
Definition: radix_tree.hpp:103
iterator find(const key_type &k)
Finds an element with key equivalent to key.
Definition: radix_tree.hpp:1678
Custom pool error class.
Definition: pexceptions.hpp:45
Definition: concurrent_hash_map.hpp:42
const_iterator cbegin() const
Returns a const iterator to the first element of the container.
Definition: radix_tree.hpp:2227
Volatile residing on pmem class.
Definition: v.hpp:42
Resides on pmem property template.
void check_pmem()
Private helper function.
Definition: radix_tree.hpp:3153
pmem::obj::array< T, N >::const_iterator cend(const pmem::obj::array< T, N > &a)
Non-member cend.
Definition: array.hpp:770
C++ pmemobj transactions.
Convenience extensions for the resides on pmem property template.
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 decrement operator overload.
Definition: pext.hpp:59
Commonly used functionality.
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:1643
const_reverse_iterator crbegin() const
Returns a const, reverse iterator to the beginning.
Definition: radix_tree.hpp:2311
void check_tx_stage_work()
Private helper function.
Definition: radix_tree.hpp:3168
pmem::obj::array< T, N >::iterator end(pmem::obj::array< T, N > &a)
Non-member end.
Definition: array.hpp:820
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:2055
size_type size() const noexcept
Returns count of characters stored in this pmem::obj::string_view data.
Definition: string_view.hpp:150
radix_tree & operator=(const radix_tree &m)
Copy assignment operator.
Definition: radix_tree.hpp:786
Radix tree iterator supports multipass and bidirectional iteration.
Definition: radix_tree.hpp:105
pool_base pool_by_vptr(const T *that)
Retrieve pool handle for the given pointer.
Definition: utils.hpp:32
pmem::obj::array< T, N >::reverse_iterator rend(pmem::obj::array< T, N > &a)
Non-member rend.
Definition: array.hpp:860
pmem::obj::array< T, N >::const_iterator cbegin(const pmem::obj::array< T, N > &a)
Non-member cbegin.
Definition: array.hpp:760
reverse_iterator rbegin()
Returns a reverse iterator to the beginning.
Definition: radix_tree.hpp:2286
const_reverse_iterator crend() const
Returns a const, reverse iterator to the end.
Definition: radix_tree.hpp:2324
~radix_tree()
Destructor.
Definition: radix_tree.hpp:873
Persistent memory aware allocator.
Void specialization of the standard allocation policy.
Definition: allocator.hpp:303
String typedefs for common character types.
Our partial std::string_view implementation.
pmem::obj::array< T, N >::const_reverse_iterator crend(const pmem::obj::array< T, N > &a)
Non-member crend.
Definition: array.hpp:790
reverse_iterator rend()
Returns a reverse iterator to the end.
Definition: radix_tree.hpp:2299
Commonly used SFINAE helpers.
Persistent smart pointer.
iterator upper_bound(const key_type &k)
Returns an iterator pointing to the first element that is greater than key.
Definition: radix_tree.hpp:2135
void swap(radix_tree< Key, Value, BytesView > &lhs, radix_tree< Key, Value, BytesView > &rhs)
Non-member swap.
Definition: radix_tree.hpp:3180
const_iterator cend() const
Returns a const iterator to the element following the last element of the map.
Definition: radix_tree.hpp:2247
p< T > & operator++(p< T > &pp)
Prefix increment operator overload.
Definition: pext.hpp:48
Inline string implementation.
iterator end()
Returns an iterator to the element following the last element of the map.
Definition: radix_tree.hpp:2211
Resides on pmem class.
Definition: p.hpp:35
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:1367
bool empty() const noexcept
Checks whether the container is empty.
Definition: radix_tree.hpp:889
void swap(radix_tree &rhs)
Member swap.
Definition: radix_tree.hpp:921
Our partial std::string_view implementation.
Definition: string_view.hpp:43
Custom transaction error class.
Definition: pexceptions.hpp:158
iterator erase(const_iterator pos)
Removes the element at pos from the container.
Definition: radix_tree.hpp:1794
Persistent memory namespace.
Definition: allocation_flag.hpp:14
Create c++14 style index sequence.
This is the structure which 'holds' key/value pair.
Definition: radix_tree.hpp:397
This is internal node.
Definition: radix_tree.hpp:463
uint64_t size() const noexcept
Definition: radix_tree.hpp:909
static void run(pool_base &pool, std::function< void()> tx, Locks &... locks)
Execute a closure-like transaction and lock locks.
Definition: transaction.hpp:406
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 >::iterator begin(pmem::obj::array< T, N > &a)
Non-member begin.
Definition: array.hpp:800
void clear()
Erases all elements from the container transactionally.
Definition: radix_tree.hpp:1771
element_type * get() const noexcept
Get the direct pointer.
Definition: persistent_ptr.hpp:478