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;
112 using reference = value_type &;
113 using const_reference =
const value_type &;
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);
134 template <
class... Args>
135 std::pair<iterator, bool> emplace(Args &&... args);
137 std::pair<iterator, bool>
insert(
const value_type &
v);
138 std::pair<iterator, bool>
insert(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>
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>
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>
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>
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>
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>
721 check_tx_stage_work();
726 for (
auto it = m.
cbegin(); it != m.
cend(); it++)
742 template <
typename Key,
typename Value,
typename BytesView>
746 check_tx_stage_work();
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>
951 typename radix_tree<Key, Value, BytesView>::leaf *
952 radix_tree<Key, Value, BytesView>::any_leftmost_leaf(
953 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr n,
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>
979 typename radix_tree<Key, Value, BytesView>::leaf *
980 radix_tree<Key, Value, BytesView>::common_prefix_leaf(
const K &key)
const
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>
1006 radix_tree<Key, Value, BytesView>::bytes_view(
const K &key)
1011 return BytesView(&key);
1014 template <
typename Key,
typename Value,
typename BytesView>
1016 radix_tree<Key, Value, BytesView>::bytes_view(string_view key)
1024 template <
typename Key,
typename Value,
typename BytesView>
1025 template <
typename K1,
typename K2>
1027 radix_tree<Key, Value, BytesView>::keys_equal(
const K1 &k1,
const K2 &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>
1038 radix_tree<Key, Value, BytesView>::compare(
const K1 &k1,
const K2 &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
1055 radix_tree<Key, Value, BytesView>::prefix_diff(
const K1 &lhs,
const K2 &rhs,
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>
1073 radix_tree<Key, Value, BytesView>::path_length_equal(
size_t key_size,
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
1082 radix_tree<Key, Value, BytesView>::bit_diff(
const K1 &leaf_key,
const K2 &key,
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 *,
1103 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr>
1104 radix_tree<Key, Value, BytesView>::descend(
const K &key, byten_t diff,
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 *,
1124 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr>
1125 radix_tree<Key, Value, BytesView>::descend(
const K &key, byten_t diff,
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>
1140 radix_tree<Key, Value, BytesView>::internal_emplace(
const K &k, F &&make_leaf)
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()) {
1968 return const_iterator(leaf, &root);
1970 return ++const_iterator(leaf, &root);
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>(
1984 return const_iterator(leaf, &root);
1992 if (diff == key.size()) {
1993 leaf = find_leaf<node::direction::Forward>(*slot);
1994 return const_iterator(leaf, &root);
2000 if (diff == leaf_key.size())
2001 return ++const_iterator(leaf, &root);
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);
2010 return const_iterator(leaf, &root);
2013 if (slot == &root) {
2014 return const_iterator(
nullptr, &root);
2019 leaf = next_leaf<node::direction::Forward>(
2020 prev->template make_iterator<node::direction::Forward>(slot),
2023 return const_iterator(leaf, &root);
2036 template <
typename Key,
typename Value,
typename BytesView>
2037 typename radix_tree<Key, Value, BytesView>::const_iterator
2040 return internal_bound<true>(k);
2053 template <
typename Key,
typename Value,
typename BytesView>
2057 auto it =
const_cast<const radix_tree *
>(
this)->lower_bound(k);
2058 return iterator(
const_cast<typename iterator::leaf_ptr
>(it.leaf_),
2075 template <
typename Key,
typename Value,
typename BytesView>
2076 template <
typename K,
typename>
2080 auto it =
const_cast<const radix_tree *
>(
this)->lower_bound(k);
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>
2137 auto it =
const_cast<const radix_tree *
>(
this)->upper_bound(k);
2138 return iterator(
const_cast<typename iterator::leaf_ptr
>(it.leaf_),
2155 template <
typename Key,
typename Value,
typename BytesView>
2156 template <
typename K,
typename>
2160 auto it =
const_cast<const radix_tree *
>(
this)->upper_bound(k);
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>
2345 radix_tree<Key, Value, BytesView>::print_rec(std::ostream &os,
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>
2402 os <<
"digraph Radix {" << std::endl;
2407 os <<
"}" << std::endl;
2415 template <
typename Key,
typename Value,
typename BytesView>
2417 radix_tree<Key, Value, BytesView>::slice_index(
char b, uint8_t bit)
2419 return static_cast<unsigned>(b >> bit) & NIB;
2422 template <
typename Key,
typename Value,
typename BytesView>
2423 radix_tree<Key, Value, BytesView>::tagged_node_ptr::tagged_node_ptr(
2427 assert(!(
bool)*
this);
2430 template <
typename Key,
typename Value,
typename BytesView>
2431 radix_tree<Key, Value, BytesView>::tagged_node_ptr::tagged_node_ptr(
2432 const persistent_ptr<leaf> &ptr)
2433 : ptr(add_tag(ptr.
get()))
2435 assert(get_leaf() == ptr.get());
2438 template <
typename Key,
typename Value,
typename BytesView>
2439 radix_tree<Key, Value, BytesView>::tagged_node_ptr::tagged_node_ptr(
2440 const persistent_ptr<node> &ptr)
2443 assert(get_node() == ptr.get());
2446 template <
typename Key,
typename Value,
typename BytesView>
2447 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr &
2448 radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator=(
2452 assert(!(
bool)*
this);
2457 template <
typename Key,
typename Value,
typename BytesView>
2458 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr &
2459 radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator=(
2460 const persistent_ptr<leaf> &rhs)
2462 ptr = add_tag(rhs.get());
2463 assert(get_leaf() == rhs.get());
2468 template <
typename Key,
typename Value,
typename BytesView>
2469 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr &
2470 radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator=(
2471 const persistent_ptr<node> &rhs)
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>
2498 const radix_tree::leaf *rhs)
const
2500 return is_leaf() && get_leaf() == rhs;
2503 template <
typename Key,
typename Value,
typename BytesView>
2506 const radix_tree::leaf *rhs)
const
2508 return !(*
this == rhs);
2511 template <
typename Key,
typename Value,
typename BytesView>
2518 template <
typename Key,
typename Value,
typename BytesView>
2520 radix_tree<Key, Value, BytesView>::tagged_node_ptr::add_tag(
2521 radix_tree::leaf *ptr)
const
2523 auto tagged =
reinterpret_cast<uintptr_t
>(ptr) | uintptr_t(IS_LEAF);
2524 return reinterpret_cast<radix_tree::leaf *
>(tagged);
2527 template <
typename Key,
typename Value,
typename BytesView>
2529 radix_tree<Key, Value, BytesView>::tagged_node_ptr::remove_tag(
void *ptr)
const
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>
2537 radix_tree<Key, Value, BytesView>::tagged_node_ptr::is_leaf()
const
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>
2544 typename radix_tree<Key, Value, BytesView>::leaf *
2545 radix_tree<Key, Value, BytesView>::tagged_node_ptr::get_leaf()
const
2548 return static_cast<radix_tree::leaf *
>(
2549 remove_tag(ptr.to_void_pointer()));
2552 template <
typename Key,
typename Value,
typename BytesView>
2553 typename radix_tree<Key, Value, BytesView>::node *
2554 radix_tree<Key, Value, BytesView>::tagged_node_ptr::get_node()
const
2557 return static_cast<radix_tree::node *
>(ptr.to_void_pointer());
2560 template <
typename Key,
typename Value,
typename BytesView>
2561 radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator bool() const
2564 return remove_tag(ptr.to_void_pointer()) !=
nullptr;
2567 template <
typename Key,
typename Value,
typename BytesView>
2568 typename radix_tree<Key, Value, BytesView>::node *
2569 radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator->() const
2575 template <
typename Key,
typename Value,
typename BytesView>
2576 radix_tree<Key, Value, BytesView>::node::forward_iterator::forward_iterator(
2577 pointer child,
const node *n)
2578 : child(child), n(n)
2582 template <
typename Key,
typename Value,
typename BytesView>
2583 typename radix_tree<Key, Value, BytesView>::node::forward_iterator
2586 if (child == &n->embedded_entry)
2587 child = &n->child[0];
2594 template <
typename Key,
typename Value,
typename BytesView>
2595 radix_tree<Key, Value, BytesView>::node::node(tagged_node_ptr parent,
2596 byten_t
byte, bitn_t bit)
2597 : parent(parent), byte(byte), bit(bit)
2601 template <
typename Key,
typename Value,
typename BytesView>
2602 typename radix_tree<Key, Value, BytesView>::node::forward_iterator
2605 if (child == &n->child[0])
2606 child = &n->embedded_entry;
2613 template <
typename Key,
typename Value,
typename BytesView>
2614 typename radix_tree<Key, Value, BytesView>::node::forward_iterator
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
2624 radix_tree<Key, Value, BytesView>::node::forward_iterator::operator*()
2630 template <
typename Key,
typename Value,
typename BytesView>
2631 typename radix_tree<Key, Value, BytesView>::node::forward_iterator::pointer
2632 radix_tree<Key, Value, BytesView>::node::forward_iterator::operator->()
2638 template <
typename Key,
typename Value,
typename BytesView>
2639 typename radix_tree<Key, Value, BytesView>::node::forward_iterator::pointer
2640 radix_tree<Key, Value, BytesView>::node::forward_iterator::get_node()
const
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<
2665 radix_tree<Key, Value, BytesView>::node::direction::Forward,
2666 typename radix_tree<Key, Value,
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<
2677 radix_tree<Key, Value, BytesView>::node::direction::Forward,
2678 typename radix_tree<Key, Value,
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<
2689 radix_tree<Key, Value, BytesView>::node::direction::Reverse,
2690 typename radix_tree<Key, Value,
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<
2701 radix_tree<Key, Value, BytesView>::node::direction::Reverse,
2702 typename radix_tree<Key, Value,
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>
2712 radix_tree<Key, Value, BytesView>::node::find_child(
const Ptr &n)
const
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>
2721 radix_tree<Key, Value, BytesView>::node::make_iterator(
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>
2729 radix_tree<Key, Value, BytesView>::radix_tree_iterator<
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>
2738 radix_tree<Key, Value, BytesView>::radix_tree_iterator<
2739 IsConst>::radix_tree_iterator(
const radix_tree_iterator<false> &rhs)
2744 template <
typename Key,
typename Value,
typename BytesView>
2745 template <
bool IsConst>
2746 typename radix_tree<Key, Value,
2747 BytesView>::template radix_tree_iterator<IsConst>::reference
2748 radix_tree<Key, Value,
2749 BytesView>::radix_tree_iterator<IsConst>::operator*()
const
2755 template <
typename Key,
typename Value,
typename BytesView>
2756 template <
bool IsConst>
2757 typename radix_tree<Key, Value,
2758 BytesView>::template radix_tree_iterator<IsConst>::pointer
2759 radix_tree<Key, Value,
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>
2851 typename radix_tree<Key, Value,
2852 BytesView>::template radix_tree_iterator<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>
2877 typename radix_tree<Key, Value,
2878 BytesView>::template radix_tree_iterator<IsConst>
2888 template <
typename Key,
typename Value,
typename BytesView>
2889 template <
bool IsConst>
2890 typename radix_tree<Key, Value,
2891 BytesView>::template radix_tree_iterator<IsConst>
2901 template <
typename Key,
typename Value,
typename BytesView>
2902 template <
bool IsConst>
2906 const radix_tree_iterator<C> &rhs)
const
2908 return leaf_ != rhs.leaf_;
2911 template <
typename Key,
typename Value,
typename BytesView>
2912 template <
bool IsConst>
2916 const radix_tree_iterator<C> &rhs)
const
2918 return !(*
this != rhs);
2926 template <
typename Key,
typename Value,
typename BytesView>
2927 template <
bool Direction,
typename Iterator>
2928 typename radix_tree<Key, Value, BytesView>::leaf *
2929 radix_tree<Key, Value, BytesView>::next_leaf(Iterator node,
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>
2955 typename radix_tree<Key, Value, BytesView>::leaf *
2956 radix_tree<Key, Value, BytesView>::find_leaf(
2957 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr n)
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>
2976 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
2977 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
2980 auto ptr = make_internal(std::forward<Args>(args)...);
2981 ptr->parent = parent;
2986 template <
typename Key,
typename Value,
typename BytesView>
2988 radix_tree<Key, Value, BytesView>::leaf::key()
2990 return *
reinterpret_cast<Key *
>(
this + 1);
2993 template <
typename Key,
typename Value,
typename BytesView>
2995 radix_tree<Key, Value, BytesView>::leaf::value()
2997 auto key_dst =
reinterpret_cast<char *
>(
this + 1);
2998 auto val_dst =
reinterpret_cast<Value *
>(
2999 key_dst + total_sizeof<Key>::value(key()));
3001 return *
reinterpret_cast<Value *
>(val_dst);
3004 template <
typename Key,
typename Value,
typename BytesView>
3006 radix_tree<Key, Value, BytesView>::leaf::key()
const
3008 return *
reinterpret_cast<const Key *
>(
this + 1);
3011 template <
typename Key,
typename Value,
typename BytesView>
3013 radix_tree<Key, Value, BytesView>::leaf::value()
const
3015 auto key_dst =
reinterpret_cast<const char *
>(
this + 1);
3016 auto val_dst =
reinterpret_cast<const Value *
>(
3017 key_dst + total_sizeof<Key>::value(key()));
3019 return *
reinterpret_cast<const Value *
>(val_dst);
3022 template <
typename Key,
typename Value,
typename BytesView>
3023 radix_tree<Key, Value, BytesView>::leaf::~leaf()
3025 detail::destroy<Key>(key());
3026 detail::destroy<Value>(value());
3029 template <
typename Key,
typename Value,
typename BytesView>
3030 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3031 radix_tree<Key, Value, BytesView>::leaf::make_internal()
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>
3041 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3042 radix_tree<Key, Value, BytesView>::leaf::make_internal(
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>
3054 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3055 radix_tree<Key, Value, BytesView>::leaf::make_internal(K &&k, V &&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>
3064 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3065 radix_tree<Key, Value, BytesView>::leaf::make_internal(
const K &k,
const V &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>
3073 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3074 radix_tree<Key, Value, BytesView>::leaf::make_internal(detail::pair<K, V> &&p)
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>
3083 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3084 radix_tree<Key, Value, BytesView>::leaf::make_internal(
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>
3094 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3095 radix_tree<Key, Value, BytesView>::leaf::make_internal(std::pair<K, V> &&p)
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>
3104 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3105 radix_tree<Key, Value, BytesView>::leaf::make_internal(
const std::pair<K, V> &p)
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>
3114 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3115 radix_tree<Key, Value, BytesView>::leaf::make_internal(
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...>)
3120 standard_alloc_policy<void> a;
3121 auto key_size = total_sizeof<Key>::value(std::get<I1>(first_args)...);
3123 total_sizeof<Value>::value(std::get<I2>(second_args)...);
3124 auto ptr =
static_cast<persistent_ptr<leaf>
>(
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>
3139 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3140 radix_tree<Key, Value, BytesView>::leaf::make_internal(
const leaf &other)
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<
3199 obj::basic_string_view<CharT, Traits>, C>::value>::type>
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];