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
103 template <
typename Key,
typename Value,
104 typename BytesView = detail::bytes_view<Key>>
106 template <
bool IsConst>
110 using key_type = Key;
111 using mapped_type = Value;
112 using value_type = detail::pair<const key_type, mapped_type>;
113 using size_type = std::size_t;
114 using reference = value_type &;
115 using const_reference =
const value_type &;
118 using reverse_iterator = std::reverse_iterator<iterator>;
119 using const_reverse_iterator = std::reverse_iterator<const_iterator>;
120 using difference_type = std::ptrdiff_t;
124 template <
class InputIt>
128 radix_tree(std::initializer_list<value_type> il);
136 template <
class... Args>
137 std::pair<iterator, bool> emplace(Args &&... args);
139 std::pair<iterator, bool>
insert(
const value_type &
v);
140 std::pair<iterator, bool>
insert(value_type &&
v);
141 template <
typename P,
142 typename =
typename std::enable_if<
143 std::is_constructible<value_type, P &&>::value,
145 std::pair<iterator, bool>
insert(P &&
p);
153 template <
class InputIterator>
154 void insert(InputIterator first, InputIterator last);
155 void insert(std::initializer_list<value_type> il);
159 template <
class... Args>
160 std::pair<iterator, bool> try_emplace(
const key_type &k,
162 template <
class... Args>
163 std::pair<iterator, bool> try_emplace(key_type &&k, Args &&... args);
171 template <
typename K,
typename BV = BytesView,
class... Args>
172 auto try_emplace(K &&k, Args &&... args) ->
typename std::enable_if<
173 detail::has_is_transparent<BV>::value &&
174 !std::is_same<
typename std::remove_const<
175 typename std::remove_reference<
178 std::pair<iterator, bool>>::type;
180 template <
typename M>
181 std::pair<iterator, bool> insert_or_assign(
const key_type &k, M &&obj);
182 template <
typename M>
183 std::pair<iterator, bool> insert_or_assign(key_type &&k, M &&obj);
190 typename M,
typename K,
191 typename =
typename std::enable_if<
192 detail::has_is_transparent<BytesView>::value, K>::type>
193 std::pair<iterator, bool> insert_or_assign(K &&k, M &&obj);
197 size_type
erase(
const key_type &k);
198 template <
typename K,
199 typename =
typename std::enable_if<
200 detail::has_is_transparent<BytesView>::value &&
201 !std::is_same<K, iterator>::value &&
202 !std::is_same<K, const_iterator>::value,
204 size_type
erase(
const K &k);
208 size_type
count(
const key_type &k)
const;
211 typename =
typename std::enable_if<
212 detail::has_is_transparent<BytesView>::value, K>::type>
213 size_type
count(
const K &k)
const;
219 typename =
typename std::enable_if<
220 detail::has_is_transparent<BytesView>::value, K>::type>
224 typename =
typename std::enable_if<
225 detail::has_is_transparent<BytesView>::value, K>::type>
232 typename =
typename std::enable_if<
233 detail::has_is_transparent<BytesView>::value, K>::type>
237 typename =
typename std::enable_if<
238 detail::has_is_transparent<BytesView>::value, K>::type>
245 typename =
typename std::enable_if<
246 detail::has_is_transparent<BytesView>::value, K>::type>
250 typename =
typename std::enable_if<
251 detail::has_is_transparent<BytesView>::value, K>::type>
261 reverse_iterator
rbegin();
262 reverse_iterator
rend();
263 const_reverse_iterator
crbegin()
const;
264 const_reverse_iterator
crend()
const;
265 const_reverse_iterator
rbegin()
const;
266 const_reverse_iterator
rend()
const;
269 bool empty()
const noexcept;
270 size_type
max_size()
const noexcept;
271 uint64_t
size()
const noexcept;
275 template <
typename K,
typename V,
typename BV>
276 friend std::ostream &
operator<<(std::ostream &os,
280 using byten_t = uint64_t;
281 using bitn_t = uint8_t;
284 static constexpr std::size_t SLICE = 4;
286 static constexpr std::size_t NIB = ((1ULL << SLICE) - 1);
288 static constexpr std::size_t SLNODES = (1 << SLICE);
290 static constexpr bitn_t SLICE_MASK = (bitn_t) ~(SLICE - 1);
292 static constexpr bitn_t FIRST_NIB = 8 - SLICE;
294 struct tagged_node_ptr;
299 tagged_node_ptr root;
303 template <
typename K,
typename F,
class... Args>
304 std::pair<iterator, bool> internal_emplace(
const K &, F &&);
305 template <
typename K>
306 leaf *internal_find(
const K &k)
const;
308 static tagged_node_ptr &parent_ref(tagged_node_ptr n);
309 template <
typename K1,
typename K2>
310 static bool keys_equal(
const K1 &k1,
const K2 &k2);
311 template <
typename K1,
typename K2>
312 static int compare(
const K1 &k1,
const K2 &k2, byten_t offset = 0);
313 template <
bool Direction,
typename Iterator>
314 static leaf *next_leaf(Iterator child, tagged_node_ptr parent);
315 template <
bool Direction>
316 static leaf *find_leaf(tagged_node_ptr n);
317 static unsigned slice_index(
char k, uint8_t shift);
318 template <
typename K1,
typename K2>
319 static byten_t prefix_diff(
const K1 &lhs,
const K2 &rhs,
321 leaf *any_leftmost_leaf(tagged_node_ptr n, size_type min_depth)
const;
322 template <
typename K1,
typename K2>
323 static bitn_t bit_diff(
const K1 &leaf_key,
const K2 &key, byten_t diff);
324 template <
typename K>
325 leaf *common_prefix_leaf(
const K &key)
const;
326 static void print_rec(std::ostream &os, radix_tree::tagged_node_ptr n);
327 template <
typename K>
328 static BytesView bytes_view(
const K &k);
330 static bool path_length_equal(
size_t key_size, tagged_node_ptr n);
331 template <
typename K>
332 std::tuple<const tagged_node_ptr *, tagged_node_ptr>
333 descend(
const K &k, byten_t diff, bitn_t sh)
const;
334 template <
typename K>
335 std::tuple<tagged_node_ptr *, tagged_node_ptr>
336 descend(
const K &k, byten_t diff, bitn_t sh);
337 template <
bool Lower,
typename K>
343 static_assert(
sizeof(
node) == 256,
344 "Internal node should have size equal to 256 bytes.");
347 template <
typename Key,
typename Value,
typename BytesView>
351 template <
typename Key,
typename Value,
typename BytesView>
352 struct radix_tree<Key, Value, BytesView>::tagged_node_ptr {
353 tagged_node_ptr() =
default;
354 tagged_node_ptr(
const tagged_node_ptr &rhs) =
default;
356 tagged_node_ptr(std::nullptr_t);
360 tagged_node_ptr &
operator=(
const tagged_node_ptr &rhs) =
default;
362 tagged_node_ptr &
operator=(std::nullptr_t);
366 bool operator==(
const tagged_node_ptr &rhs)
const;
367 bool operator!=(
const tagged_node_ptr &rhs)
const;
372 void swap(tagged_node_ptr &rhs);
374 bool is_leaf()
const;
381 explicit operator
bool() const noexcept;
384 static constexpr uintptr_t IS_LEAF = 1;
386 void *remove_tag(
void *ptr) const;
400 template <typename Key, typename Value, typename BytesView>
415 const Key &key()
const;
416 const Value &value()
const;
420 template <
typename... Args1,
typename... Args2>
422 make(tagged_node_ptr parent, std::piecewise_construct_t pc,
423 std::tuple<Args1...> first_args, std::tuple<Args2...> second_args);
424 template <
typename K,
typename V>
428 template <
typename K,
typename... Args>
431 template <
typename K,
typename V>
433 detail::pair<K, V> &&
p);
434 template <
typename K,
typename V>
436 const detail::pair<K, V> &
p);
437 template <
typename K,
typename V>
439 std::pair<K, V> &&
p);
440 template <
typename K,
typename V>
442 const std::pair<K, V> &
p);
447 friend class radix_tree<Key, Value, BytesView>;
451 template <
typename... Args1,
typename... Args2,
size_t... I1,
454 make(tagged_node_ptr parent, std::piecewise_construct_t,
455 std::tuple<Args1...> &first_args,
456 std::tuple<Args2...> &second_args, detail::index_sequence<I1...>,
457 detail::index_sequence<I2...>);
459 tagged_node_ptr parent =
nullptr;
466 template <
typename Key,
typename Value,
typename BytesView>
468 node(tagged_node_ptr parent, byten_t
byte, bitn_t bit);
484 tagged_node_ptr child[SLNODES];
500 static constexpr
bool Forward = 0;
501 static constexpr
bool Reverse = 1;
504 struct forward_iterator;
505 using reverse_iterator = std::reverse_iterator<forward_iterator>;
507 template <
bool Direction>
509 typename std::conditional<Direction == direction::Forward,
511 reverse_iterator>::type;
513 template <
bool Direction = direction::Forward>
514 typename std::enable_if<
517 BytesView>::node::direction::Forward,
519 BytesView>::node::forward_iterator>::type
522 template <
bool Direction = direction::Forward>
523 typename std::enable_if<
526 BytesView>::node::direction::Forward,
528 BytesView>::node::forward_iterator>::type
532 template <
bool Direction = direction::Forward>
533 typename std::enable_if<
536 BytesView>::node::direction::Reverse,
538 BytesView>::node::reverse_iterator>::type
542 template <
bool Direction = direction::Forward>
543 typename std::enable_if<
546 BytesView>::node::direction::Reverse,
548 BytesView>::node::reverse_iterator>::type
551 template <
bool Direction = direction::Forward,
typename Ptr>
552 auto find_child(
const Ptr &n)
const -> decltype(begin<Direction>());
554 template <
bool Direction = direction::Forward,
555 typename Enable =
typename std::enable_if<
556 Direction == direction::Forward>::type>
557 auto make_iterator(
const tagged_node_ptr *ptr)
const
558 -> decltype(begin<Direction>());
560 uint8_t padding[256 -
sizeof(parent) -
sizeof(
leaf) -
sizeof(child) -
561 sizeof(
byte) -
sizeof(bit)];
569 template <
typename Key,
typename Value,
typename BytesView>
570 template <
bool IsConst>
574 typename std::conditional<IsConst, const leaf *, leaf *>::type;
576 typename std::conditional<IsConst,
const tagged_node_ptr *,
577 tagged_node_ptr *>::type;
581 using difference_type = std::ptrdiff_t;
583 using reference =
typename std::conditional<IsConst,
const value_type &,
585 using pointer =
typename std::conditional<IsConst,
value_type const *,
587 using iterator_category = std::bidirectional_iterator_tag;
593 template <
bool C = IsConst,
594 typename Enable =
typename std::enable_if<C>::type>
600 reference operator*()
const;
601 pointer operator->()
const;
603 template <
typename V = Value,
604 typename Enable =
typename std::enable_if<
605 detail::is_inline_string<V>::value>::type>
607 typename V::traits_type>
610 template <
typename T,
typename V = Value,
611 typename Enable =
typename std::enable_if<
612 !detail::is_inline_string<V>::value>::type>
613 void assign_val(T &&rhs);
630 leaf_ptr leaf_ =
nullptr;
631 node_ptr root =
nullptr;
634 template <
typename Key,
typename Value,
typename BytesView>
635 struct radix_tree<Key, Value, BytesView>::node::forward_iterator {
636 using difference_type = std::ptrdiff_t;
637 using value_type = tagged_node_ptr;
638 using pointer =
const value_type *;
639 using reference =
const value_type &;
640 using iterator_category = std::forward_iterator_tag;
642 forward_iterator(pointer child,
const node *
node);
649 reference operator*()
const;
650 pointer operator->()
const;
652 pointer get_node()
const;
654 bool operator!=(
const forward_iterator &rhs)
const;
655 bool operator==(
const forward_iterator &rhs)
const;
670 template <
typename Key,
typename Value,
typename BytesView>
696 template <
typename Key,
typename Value,
typename BytesView>
697 template <
class InputIt>
699 : root(nullptr), size_(0)
704 for (
auto it = first; it != last; it++)
723 template <
typename Key,
typename Value,
typename BytesView>
727 check_tx_stage_work();
732 for (
auto it = m.
cbegin(); it != m.
cend(); it++)
748 template <
typename Key,
typename Value,
typename BytesView>
752 check_tx_stage_work();
774 template <
typename Key,
typename Value,
typename BytesView>
776 std::initializer_list<value_type> il)
790 template <
typename Key,
typename Value,
typename BytesView>
798 if (
this != &other) {
802 this->root =
nullptr;
805 for (
auto it = other.
cbegin(); it != other.
cend(); it++)
821 template <
typename Key,
typename Value,
typename BytesView>
829 if (
this != &other) {
833 this->root = other.root;
834 this->size_ = other.size_;
835 other.root =
nullptr;
853 template <
typename Key,
typename Value,
typename BytesView>
856 std::initializer_list<value_type> ilist)
865 this->root =
nullptr;
868 for (
auto it = ilist.begin(); it != ilist.end(); it++)
878 template <
typename Key,
typename Value,
typename BytesView>
893 template <
typename Key,
typename Value,
typename BytesView>
903 template <
typename Key,
typename Value,
typename BytesView>
904 typename radix_tree<Key, Value, BytesView>::size_type
907 return std::numeric_limits<difference_type>::max();
913 template <
typename Key,
typename Value,
typename BytesView>
925 template <
typename Key,
typename Value,
typename BytesView>
932 this->size_.swap(rhs.size_);
933 this->root.swap(rhs.root);
940 template <
typename Key,
typename Value,
typename BytesView>
945 return n.get_leaf()->parent;
956 template <
typename Key,
typename Value,
typename BytesView>
957 typename radix_tree<Key, Value, BytesView>::leaf *
958 radix_tree<Key, Value, BytesView>::any_leftmost_leaf(
959 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr n,
960 size_type min_depth)
const
964 while (!n.is_leaf()) {
965 if (n->embedded_entry && n->byte >= min_depth)
966 return n->embedded_entry.get_leaf();
968 for (
size_t i = 0; i < SLNODES; i++) {
970 if ((m = n->child[i])) {
983 template <
typename Key,
typename Value,
typename BytesView>
984 template <
typename K>
985 typename radix_tree<Key, Value, BytesView>::leaf *
986 radix_tree<Key, Value, BytesView>::common_prefix_leaf(
const K &key)
const
990 while (n && !n.is_leaf() && n->byte < key.size()) {
991 auto nn = n->child[slice_index(key[n->byte], n->bit)];
996 n = any_leftmost_leaf(n, key.size());
1004 n = any_leftmost_leaf(n, key.size());
1006 return n.get_leaf();
1009 template <
typename Key,
typename Value,
typename BytesView>
1010 template <
typename K>
1012 radix_tree<Key, Value, BytesView>::bytes_view(
const K &key)
1017 return BytesView(&key);
1020 template <
typename Key,
typename Value,
typename BytesView>
1022 radix_tree<Key, Value, BytesView>::bytes_view(string_view key)
1030 template <
typename Key,
typename Value,
typename BytesView>
1031 template <
typename K1,
typename K2>
1033 radix_tree<Key, Value, BytesView>::keys_equal(
const K1 &k1,
const K2 &k2)
1035 return k1.size() == k2.size() && compare(k1, k2) == 0;
1041 template <
typename Key,
typename Value,
typename BytesView>
1042 template <
typename K1,
typename K2>
1044 radix_tree<Key, Value, BytesView>::compare(
const K1 &k1,
const K2 &k2,
1047 auto ret = prefix_diff(k1, k2, offset);
1049 if (ret != (std::min)(k1.size(), k2.size()))
1050 return (
unsigned char)(k1[ret]) - (
unsigned char)(k2[ret]);
1052 return k1.size() - k2.size();
1058 template <
typename Key,
typename Value,
typename BytesView>
1059 template <
typename K1,
typename K2>
1060 typename radix_tree<Key, Value, BytesView>::byten_t
1061 radix_tree<Key, Value, BytesView>::prefix_diff(
const K1 &lhs,
const K2 &rhs,
1065 for (diff = offset; diff < (std::min)(lhs.size(), rhs.size()); diff++) {
1066 if (lhs[diff] != rhs[diff])
1077 template <
typename Key,
typename Value,
typename BytesView>
1079 radix_tree<Key, Value, BytesView>::path_length_equal(
size_t key_size,
1082 return n->byte == key_size && n->bit == bitn_t(FIRST_NIB);
1085 template <
typename Key,
typename Value,
typename BytesView>
1086 template <
typename K1,
typename K2>
1087 typename radix_tree<Key, Value, BytesView>::bitn_t
1088 radix_tree<Key, Value, BytesView>::bit_diff(
const K1 &leaf_key,
const K2 &key,
1091 auto min_key_len = (std::min)(leaf_key.size(), key.size());
1097 if (diff < min_key_len) {
1099 static_cast<unsigned char>(leaf_key[diff] ^ key[diff]);
1100 sh = pmem::detail::mssb_index((uint32_t)at) & SLICE_MASK;
1106 template <
typename Key,
typename Value,
typename BytesView>
1107 template <
typename K>
1108 std::tuple<const typename radix_tree<Key, Value, BytesView>::tagged_node_ptr *,
1109 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr>
1110 radix_tree<Key, Value, BytesView>::descend(
const K &key, byten_t diff,
1117 while (n && !n.is_leaf() &&
1118 (n->byte < diff || (n->byte == diff && n->bit >= sh))) {
1120 slot = &n->child[slice_index(key[n->byte], n->bit)];
1124 return {slot, prev};
1127 template <
typename Key,
typename Value,
typename BytesView>
1128 template <
typename K>
1129 std::tuple<typename radix_tree<Key, Value, BytesView>::tagged_node_ptr *,
1130 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr>
1131 radix_tree<Key, Value, BytesView>::descend(
const K &key, byten_t diff,
1134 const tagged_node_ptr *slot;
1135 tagged_node_ptr prev;
1137 std::tie(slot, prev) =
1138 const_cast<const radix_tree *
>(
this)->descend(key, diff, sh);
1140 return {
const_cast<tagged_node_ptr *
>(slot), prev};
1143 template <
typename Key,
typename Value,
typename BytesView>
1144 template <
typename K,
typename F,
class... Args>
1145 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1146 radix_tree<Key, Value, BytesView>::internal_emplace(
const K &k, F &&make_leaf)
1148 auto key = bytes_view(k);
1149 auto pop = pool_base(pmemobj_pool_by_ptr(
this));
1153 [&] { this->root = make_leaf(
nullptr); });
1154 return {iterator(root.get_leaf(), &root),
true};
1164 auto leaf = common_prefix_leaf(key);
1165 auto leaf_key = bytes_view(leaf->key());
1166 auto diff = prefix_diff(key, leaf_key);
1167 auto sh = bit_diff(leaf_key, key, diff);
1170 if (diff == key.size() && leaf_key.size() == key.size())
1171 return {iterator(leaf, &root),
false};
1174 tagged_node_ptr *slot;
1175 tagged_node_ptr prev;
1176 std::tie(slot, prev) = descend(key, diff, sh);
1186 assert(diff < (std::min)(leaf_key.size(), key.size()));
1189 return {iterator(slot->get_leaf(), &root),
true};
1194 if (diff == key.size()) {
1195 if (!n.is_leaf() && path_length_equal(key.size(), n)) {
1196 assert(!n->embedded_entry);
1199 pop, [&] { n->embedded_entry = make_leaf(n); });
1201 return {iterator(n->embedded_entry.get_leaf(), &root),
1207 tagged_node_ptr node;
1209 node = make_persistent<radix_tree::node>(
1210 parent_ref(n), diff, bitn_t(FIRST_NIB));
1211 node->embedded_entry = make_leaf(node);
1212 node->child[slice_index(leaf_key[diff],
1213 bitn_t(FIRST_NIB))] = n;
1215 parent_ref(n) = node;
1219 return {iterator(node->embedded_entry.get_leaf(), &root),
true};
1222 if (diff == leaf_key.size()) {
1225 tagged_node_ptr node;
1229 node = make_persistent<radix_tree::node>(
1230 parent_ref(n), diff, bitn_t(FIRST_NIB));
1231 node->embedded_entry = n;
1232 node->child[slice_index(key[diff], bitn_t(FIRST_NIB))] =
1235 parent_ref(n) = node;
1239 return {iterator(node->child[slice_index(key[diff],
1250 tagged_node_ptr node;
1252 node = make_persistent<radix_tree::node>(parent_ref(n), diff,
1254 node->child[slice_index(leaf_key[diff], sh)] = n;
1255 node->child[slice_index(key[diff], sh)] = make_leaf(node);
1257 parent_ref(n) = node;
1261 return {iterator(node->child[slice_index(key[diff], sh)].get_leaf(),
1294 template <
typename Key,
typename Value,
typename BytesView>
1295 template <
class... Args>
1296 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1300 return internal_emplace(k, [&](tagged_node_ptr parent) {
1302 return leaf::make_key_args(parent, k,
1303 std::forward<Args>(args)...);
1333 template <
typename Key,
typename Value,
typename BytesView>
1334 template <
class... Args>
1335 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1338 auto pop =
pool_base(pmemobj_pool_by_ptr(
this));
1339 std::pair<iterator, bool> ret;
1342 auto leaf_ = leaf::make(
nullptr, std::forward<Args>(args)...);
1343 auto make_leaf = [&](tagged_node_ptr parent) {
1344 leaf_->parent = parent;
1349 ret = internal_emplace(leaf_->key(), make_leaf);
1352 delete_persistent<leaf>(leaf_);
1373 template <
typename Key,
typename Value,
typename BytesView>
1374 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1377 return try_emplace(
v.first,
v.second);
1395 template <
typename Key,
typename Value,
typename BytesView>
1396 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1399 return try_emplace(std::move(
v.first), std::move(
v.second));
1421 template <
typename Key,
typename Value,
typename BytesView>
1422 template <
typename P,
typename>
1423 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1426 return emplace(std::forward<P>(
p));
1440 template <
typename Key,
typename Value,
typename BytesView>
1441 template <
typename InputIterator>
1446 for (
auto it = first; it != last; it++)
1447 try_emplace((*it).first, (*it).second);
1460 template <
typename Key,
typename Value,
typename BytesView>
1464 insert(il.begin(), il.end());
1491 template <
typename Key,
typename Value,
typename BytesView>
1492 template <
class... Args>
1493 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1496 return internal_emplace(k, [&](tagged_node_ptr parent) {
1498 return leaf::make_key_args(parent, std::move(k),
1499 std::forward<Args>(args)...);
1531 template <
typename Key,
typename Value,
typename BytesView>
1532 template <
typename K,
typename BV,
class... Args>
1535 typename std::enable_if<
1536 detail::has_is_transparent<BV>::value &&
1537 !std::is_same<
typename std::remove_const<
1538 typename std::remove_reference<
1541 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
1545 return internal_emplace(k, [&](tagged_node_ptr parent) {
1547 return leaf::make_key_args(parent, std::forward<K>(k),
1548 std::forward<Args>(args)...);
1570 template <
typename Key,
typename Value,
typename BytesView>
1571 template <
typename M>
1572 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1575 auto ret = try_emplace(k, std::forward<M>(obj));
1577 ret.first.assign_val(std::forward<M>(obj));
1599 template <
typename Key,
typename Value,
typename BytesView>
1600 template <
typename M>
1601 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1604 auto ret = try_emplace(std::move(k), std::forward<M>(obj));
1606 ret.first.assign_val(std::forward<M>(obj));
1631 template <
typename Key,
typename Value,
typename BytesView>
1632 template <
typename M,
typename K,
typename>
1633 std::pair<typename radix_tree<Key, Value, BytesView>::iterator,
bool>
1636 auto ret = try_emplace(std::forward<K>(k), std::forward<M>(obj));
1638 ret.first.assign_val(std::forward<M>(obj));
1651 template <
typename Key,
typename Value,
typename BytesView>
1652 typename radix_tree<Key, Value, BytesView>::size_type
1655 return internal_find(k) !=
nullptr ? 1 : 0;
1670 template <
typename Key,
typename Value,
typename BytesView>
1671 template <
typename K,
typename>
1672 typename radix_tree<Key, Value, BytesView>::size_type
1675 return internal_find(k) !=
nullptr ? 1 : 0;
1686 template <
typename Key,
typename Value,
typename BytesView>
1690 return iterator(internal_find(k), &root);
1701 template <
typename Key,
typename Value,
typename BytesView>
1719 template <
typename Key,
typename Value,
typename BytesView>
1720 template <
typename K,
typename>
1724 return iterator(internal_find(k), &root);
1738 template <
typename Key,
typename Value,
typename BytesView>
1739 template <
typename K,
typename>
1746 template <
typename Key,
typename Value,
typename BytesView>
1747 template <
typename K>
1751 auto key = bytes_view(k);
1754 while (n && !n.is_leaf()) {
1755 if (path_length_equal(key.size(), n))
1756 n = n->embedded_entry;
1757 else if (n->byte >= key.size())
1760 n = n->child[slice_index(key[n->byte], n->bit)];
1766 if (!keys_equal(key, bytes_view(n.get_leaf()->key())))
1769 return n.get_leaf();
1779 template <
typename Key,
typename Value,
typename BytesView>
1802 template <
typename Key,
typename Value,
typename BytesView>
1806 auto pop =
pool_base(pmemobj_pool_by_ptr(
this));
1809 auto *
leaf = pos.leaf_;
1810 auto parent =
leaf->parent;
1816 delete_persistent<radix_tree::leaf>(
1823 this->root =
nullptr;
1829 const_cast<tagged_node_ptr &
>(*parent->find_child(
leaf)) =
1835 tagged_node_ptr only_child =
nullptr;
1836 for (
size_t i = 0; i < SLNODES; i++) {
1842 only_child = n->child[i];
1846 if (only_child && n->embedded_entry) {
1850 }
else if (n->embedded_entry) {
1851 only_child = n->embedded_entry;
1855 parent_ref(only_child) = n->parent;
1857 auto *child_slot = parent
1858 ?
const_cast<tagged_node_ptr *
>(&*parent->find_child(n))
1860 *child_slot = only_child;
1862 delete_persistent<radix_tree::node>(n.get_node());
1865 return iterator(
const_cast<typename iterator::leaf_ptr
>(pos.leaf_),
1882 template <
typename Key,
typename Value,
typename BytesView>
1887 auto pop =
pool_base(pmemobj_pool_by_ptr(
this));
1890 while (first != last)
1891 first = erase(first);
1894 return iterator(
const_cast<typename iterator::leaf_ptr
>(first.leaf_),
1910 template <
typename Key,
typename Value,
typename BytesView>
1911 typename radix_tree<Key, Value, BytesView>::size_type
1939 template <
typename Key,
typename Value,
typename BytesView>
1940 template <
typename K,
typename>
1941 typename radix_tree<Key, Value, BytesView>::size_type
1954 template <
typename Key,
typename Value,
typename BytesView>
1955 template <
bool Lower,
typename K>
1959 auto key = bytes_view(k);
1960 auto pop =
pool_base(pmemobj_pool_by_ptr(
this));
1972 auto leaf = common_prefix_leaf(key);
1973 auto leaf_key = bytes_view(leaf->key());
1974 auto diff = prefix_diff(key, leaf_key);
1975 auto sh = bit_diff(leaf_key, key, diff);
1978 if (diff == key.size() && leaf_key.size() == key.size()) {
1980 return const_iterator(leaf, &root);
1982 return ++const_iterator(leaf, &root);
1986 const tagged_node_ptr *slot;
1987 tagged_node_ptr prev;
1988 std::tie(slot, prev) = descend(key, diff, sh);
1991 leaf = next_leaf<node::direction::Forward>(
1992 prev->template make_iterator<node::direction::Forward>(
1996 return const_iterator(leaf, &root);
2004 if (diff == key.size()) {
2005 leaf = find_leaf<node::direction::Forward>(*slot);
2006 return const_iterator(leaf, &root);
2012 if (diff == leaf_key.size())
2013 return ++const_iterator(leaf, &root);
2016 assert(diff < leaf_key.size() && diff < key.size());
2020 if (compare(key, leaf_key, diff) < 0) {
2021 leaf = find_leaf<node::direction::Forward>(*slot);
2022 return const_iterator(leaf, &root);
2025 if (slot == &root) {
2026 return const_iterator(
nullptr, &root);
2031 leaf = next_leaf<node::direction::Forward>(
2032 prev->template make_iterator<node::direction::Forward>(slot),
2035 return const_iterator(leaf, &root);
2048 template <
typename Key,
typename Value,
typename BytesView>
2049 typename radix_tree<Key, Value, BytesView>::const_iterator
2052 return internal_bound<true>(k);
2065 template <
typename Key,
typename Value,
typename BytesView>
2069 auto it =
const_cast<const radix_tree *
>(
this)->lower_bound(k);
2070 return iterator(
const_cast<typename iterator::leaf_ptr
>(it.leaf_),
2087 template <
typename Key,
typename Value,
typename BytesView>
2088 template <
typename K,
typename>
2092 auto it =
const_cast<const radix_tree *
>(
this)->lower_bound(k);
2093 return iterator(
const_cast<typename iterator::leaf_ptr
>(it.leaf_),
2110 template <
typename Key,
typename Value,
typename BytesView>
2111 template <
typename K,
typename>
2115 return internal_bound<true>(k);
2128 template <
typename Key,
typename Value,
typename BytesView>
2132 return internal_bound<false>(k);
2145 template <
typename Key,
typename Value,
typename BytesView>
2149 auto it =
const_cast<const radix_tree *
>(
this)->upper_bound(k);
2150 return iterator(
const_cast<typename iterator::leaf_ptr
>(it.leaf_),
2167 template <
typename Key,
typename Value,
typename BytesView>
2168 template <
typename K,
typename>
2172 auto it =
const_cast<const radix_tree *
>(
this)->upper_bound(k);
2173 return iterator(
const_cast<typename iterator::leaf_ptr
>(it.leaf_),
2190 template <
typename Key,
typename Value,
typename BytesView>
2191 template <
typename K,
typename>
2195 return internal_bound<false>(k);
2204 template <
typename Key,
typename Value,
typename BytesView>
2210 const_cast<typename iterator::leaf_ptr
>(const_begin.leaf_),
2221 template <
typename Key,
typename Value,
typename BytesView>
2225 auto const_end =
const_cast<const radix_tree *
>(
this)->
end();
2227 const_cast<typename iterator::leaf_ptr
>(const_end.leaf_),
2237 template <
typename Key,
typename Value,
typename BytesView>
2245 radix_tree::find_leaf<radix_tree::node::direction::Forward>(
2257 template <
typename Key,
typename Value,
typename BytesView>
2270 template <
typename Key,
typename Value,
typename BytesView>
2284 template <
typename Key,
typename Value,
typename BytesView>
2296 template <
typename Key,
typename Value,
typename BytesView>
2297 typename radix_tree<Key, Value, BytesView>::reverse_iterator
2300 return reverse_iterator(
end());
2309 template <
typename Key,
typename Value,
typename BytesView>
2310 typename radix_tree<Key, Value, BytesView>::reverse_iterator
2313 return reverse_iterator(
begin());
2321 template <
typename Key,
typename Value,
typename BytesView>
2322 typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
2325 return const_reverse_iterator(
cend());
2334 template <
typename Key,
typename Value,
typename BytesView>
2335 typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
2338 return const_reverse_iterator(
cbegin());
2341 template <
typename Key,
typename Value,
typename BytesView>
2342 typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
2345 return const_reverse_iterator(
cend());
2348 template <
typename Key,
typename Value,
typename BytesView>
2349 typename radix_tree<Key, Value, BytesView>::const_reverse_iterator
2352 return const_reverse_iterator(
cbegin());
2355 template <
typename Key,
typename Value,
typename BytesView>
2357 radix_tree<Key, Value, BytesView>::print_rec(std::ostream &os,
2358 radix_tree::tagged_node_ptr n)
2361 os <<
"\"" << n.get_node() <<
"\""
2362 <<
" [style=filled,color=\"blue\"]" << std::endl;
2363 os <<
"\"" << n.get_node() <<
"\" [label=\"byte:" << n->byte
2364 <<
", bit:" << int(n->bit) <<
"\"]" << std::endl;
2366 auto parent = n->parent ? n->parent.get_node() : 0;
2367 os <<
"\"" << n.get_node() <<
"\" -> "
2368 <<
"\"" << parent <<
"\" [label=\"parent\"]" << std::endl;
2370 for (
auto it = n->begin(); it != n->end(); ++it) {
2374 auto ch = it->is_leaf() ? (
void *)it->get_leaf()
2375 : (
void *)it->get_node();
2377 os <<
"\"" << n.get_node() <<
"\" -> \"" << ch <<
"\""
2382 auto bv = bytes_view(n.get_leaf()->key());
2384 os <<
"\"" << n.get_leaf()
2385 <<
"\" [style=filled,color=\"green\"]" << std::endl;
2386 os <<
"\"" << n.get_leaf() <<
"\" [label=\"key:";
2388 for (
size_t i = 0; i < bv.size(); i++)
2391 os <<
"\"]" << std::endl;
2393 auto parent = n.get_leaf()->parent
2394 ? n.get_leaf()->parent.get_node()
2397 os <<
"\"" << n.get_leaf() <<
"\" -> \"" << parent
2398 <<
"\" [label=\"parent\"]" << std::endl;
2400 if (parent && n == parent->embedded_entry) {
2401 os <<
"{rank=same;\"" << parent <<
"\";\""
2402 << n.get_leaf() <<
"\"}" << std::endl;
2410 template <
typename K,
typename V,
typename BV>
2414 os <<
"digraph Radix {" << std::endl;
2419 os <<
"}" << std::endl;
2427 template <
typename Key,
typename Value,
typename BytesView>
2431 return static_cast<unsigned>(b >> bit) & NIB;
2434 template <
typename Key,
typename Value,
typename BytesView>
2435 radix_tree<Key, Value, BytesView>::tagged_node_ptr::tagged_node_ptr(
2439 assert(!(
bool)*
this);
2442 template <
typename Key,
typename Value,
typename BytesView>
2443 radix_tree<Key, Value, BytesView>::tagged_node_ptr::tagged_node_ptr(
2444 const persistent_ptr<leaf> &ptr)
2445 : ptr(add_tag(ptr.
get()))
2447 assert(get_leaf() == ptr.get());
2450 template <
typename Key,
typename Value,
typename BytesView>
2451 radix_tree<Key, Value, BytesView>::tagged_node_ptr::tagged_node_ptr(
2452 const persistent_ptr<node> &ptr)
2455 assert(get_node() == ptr.get());
2458 template <
typename Key,
typename Value,
typename BytesView>
2459 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr &
2460 radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator=(
2464 assert(!(
bool)*
this);
2469 template <
typename Key,
typename Value,
typename BytesView>
2470 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr &
2471 radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator=(
2472 const persistent_ptr<leaf> &rhs)
2474 ptr = add_tag(rhs.get());
2475 assert(get_leaf() == rhs.get());
2480 template <
typename Key,
typename Value,
typename BytesView>
2481 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr &
2482 radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator=(
2483 const persistent_ptr<node> &rhs)
2486 assert(get_node() == rhs.get());
2491 template <
typename Key,
typename Value,
typename BytesView>
2494 const radix_tree::tagged_node_ptr &rhs)
const
2496 return ptr.to_byte_pointer() == rhs.ptr.to_byte_pointer();
2499 template <
typename Key,
typename Value,
typename BytesView>
2502 const radix_tree::tagged_node_ptr &rhs)
const
2504 return !(*
this == rhs);
2507 template <
typename Key,
typename Value,
typename BytesView>
2510 const radix_tree::leaf *rhs)
const
2512 return is_leaf() && get_leaf() == rhs;
2515 template <
typename Key,
typename Value,
typename BytesView>
2518 const radix_tree::leaf *rhs)
const
2520 return !(*
this == rhs);
2523 template <
typename Key,
typename Value,
typename BytesView>
2530 template <
typename Key,
typename Value,
typename BytesView>
2532 radix_tree<Key, Value, BytesView>::tagged_node_ptr::add_tag(
2533 radix_tree::leaf *ptr)
const
2535 auto tagged =
reinterpret_cast<uintptr_t
>(ptr) | uintptr_t(IS_LEAF);
2536 return reinterpret_cast<radix_tree::leaf *
>(tagged);
2539 template <
typename Key,
typename Value,
typename BytesView>
2541 radix_tree<Key, Value, BytesView>::tagged_node_ptr::remove_tag(
void *ptr)
const
2543 auto untagged =
reinterpret_cast<uintptr_t
>(ptr) & ~uintptr_t(IS_LEAF);
2544 return reinterpret_cast<void *
>(untagged);
2547 template <
typename Key,
typename Value,
typename BytesView>
2549 radix_tree<Key, Value, BytesView>::tagged_node_ptr::is_leaf()
const
2551 auto value =
reinterpret_cast<uintptr_t
>(ptr.to_void_pointer());
2552 return value & uintptr_t(IS_LEAF);
2555 template <
typename Key,
typename Value,
typename BytesView>
2556 typename radix_tree<Key, Value, BytesView>::leaf *
2557 radix_tree<Key, Value, BytesView>::tagged_node_ptr::get_leaf()
const
2560 return static_cast<radix_tree::leaf *
>(
2561 remove_tag(ptr.to_void_pointer()));
2564 template <
typename Key,
typename Value,
typename BytesView>
2565 typename radix_tree<Key, Value, BytesView>::node *
2566 radix_tree<Key, Value, BytesView>::tagged_node_ptr::get_node()
const
2569 return static_cast<radix_tree::node *
>(ptr.to_void_pointer());
2572 template <
typename Key,
typename Value,
typename BytesView>
2573 radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator bool() const
2576 return remove_tag(ptr.to_void_pointer()) !=
nullptr;
2579 template <
typename Key,
typename Value,
typename BytesView>
2580 typename radix_tree<Key, Value, BytesView>::node *
2581 radix_tree<Key, Value, BytesView>::tagged_node_ptr::operator->() const
2587 template <
typename Key,
typename Value,
typename BytesView>
2588 radix_tree<Key, Value, BytesView>::node::forward_iterator::forward_iterator(
2589 pointer child,
const node *n)
2590 : child(child), n(n)
2594 template <
typename Key,
typename Value,
typename BytesView>
2595 typename radix_tree<Key, Value, BytesView>::node::forward_iterator
2598 if (child == &n->embedded_entry)
2599 child = &n->child[0];
2606 template <
typename Key,
typename Value,
typename BytesView>
2607 radix_tree<Key, Value, BytesView>::node::node(tagged_node_ptr parent,
2608 byten_t
byte, bitn_t bit)
2609 : parent(parent), byte(byte), bit(bit)
2613 template <
typename Key,
typename Value,
typename BytesView>
2614 typename radix_tree<Key, Value, BytesView>::node::forward_iterator
2617 if (child == &n->child[0])
2618 child = &n->embedded_entry;
2625 template <
typename Key,
typename Value,
typename BytesView>
2626 typename radix_tree<Key, Value, BytesView>::node::forward_iterator
2629 forward_iterator tmp(child, n);
2634 template <
typename Key,
typename Value,
typename BytesView>
2635 typename radix_tree<Key, Value, BytesView>::node::forward_iterator::reference
2636 radix_tree<Key, Value, BytesView>::node::forward_iterator::operator*()
2642 template <
typename Key,
typename Value,
typename BytesView>
2643 typename radix_tree<Key, Value, BytesView>::node::forward_iterator::pointer
2644 radix_tree<Key, Value, BytesView>::node::forward_iterator::operator->()
2650 template <
typename Key,
typename Value,
typename BytesView>
2651 typename radix_tree<Key, Value, BytesView>::node::forward_iterator::pointer
2652 radix_tree<Key, Value, BytesView>::node::forward_iterator::get_node()
const
2657 template <
typename Key,
typename Value,
typename BytesView>
2660 const forward_iterator &rhs)
const
2662 return child == rhs.child && n == rhs.n;
2665 template <
typename Key,
typename Value,
typename BytesView>
2668 const forward_iterator &rhs)
const
2670 return child != rhs.child || n != rhs.n;
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
2680 radix_tree<Key, Value, BytesView>::node::begin()
const
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::Forward,
2691 BytesView>::node::forward_iterator>::type
2692 radix_tree<Key, Value, BytesView>::node::end()
const
2694 return forward_iterator(&child[SLNODES],
this);
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,
2703 BytesView>::node::reverse_iterator>::type
2704 radix_tree<Key, Value, BytesView>::node::begin()
const
2706 return reverse_iterator(end<direction::Forward>());
2709 template <
typename Key,
typename Value,
typename BytesView>
2710 template <
bool Direction>
2711 typename std::enable_if<
2713 radix_tree<Key, Value, BytesView>::node::direction::Reverse,
2715 BytesView>::node::reverse_iterator>::type
2716 radix_tree<Key, Value, BytesView>::node::end()
const
2718 return reverse_iterator(begin<direction::Forward>());
2721 template <
typename Key,
typename Value,
typename BytesView>
2722 template <
bool Direction,
typename Ptr>
2724 radix_tree<Key, Value, BytesView>::node::find_child(
const Ptr &n)
const
2725 -> decltype(begin<Direction>())
2727 return std::find(begin<Direction>(), end<Direction>(), n);
2730 template <
typename Key,
typename Value,
typename BytesView>
2731 template <
bool Direction,
typename Enable>
2733 radix_tree<Key, Value, BytesView>::node::make_iterator(
2734 const tagged_node_ptr *ptr)
const -> decltype(begin<Direction>())
2736 return forward_iterator(ptr,
this);
2739 template <
typename Key,
typename Value,
typename BytesView>
2740 template <
bool IsConst>
2741 radix_tree<Key, Value, BytesView>::radix_tree_iterator<
2742 IsConst>::radix_tree_iterator(leaf_ptr leaf_, node_ptr root)
2743 : leaf_(leaf_), root(root)
2747 template <
typename Key,
typename Value,
typename BytesView>
2748 template <
bool IsConst>
2749 template <
bool C,
typename Enable>
2750 radix_tree<Key, Value, BytesView>::radix_tree_iterator<
2751 IsConst>::radix_tree_iterator(
const radix_tree_iterator<false> &rhs)
2756 template <
typename Key,
typename Value,
typename BytesView>
2757 template <
bool IsConst>
2758 typename radix_tree<Key, Value,
2759 BytesView>::template radix_tree_iterator<IsConst>::reference
2760 radix_tree<Key, Value,
2761 BytesView>::radix_tree_iterator<IsConst>::operator*()
const
2767 template <
typename Key,
typename Value,
typename BytesView>
2768 template <
bool IsConst>
2769 typename radix_tree<Key, Value,
2770 BytesView>::template radix_tree_iterator<IsConst>::pointer
2771 radix_tree<Key, Value,
2772 BytesView>::radix_tree_iterator<IsConst>::operator->()
const
2787 template <
typename Key,
typename Value,
typename BytesView>
2788 template <
bool IsConst>
2789 template <
typename V,
typename Enable>
2794 auto pop =
pool_base(pmemobj_pool_by_ptr(leaf_));
2796 if (rhs.
size() <= leaf_->value().capacity()) {
2799 tagged_node_ptr *slot;
2801 if (!leaf_->parent) {
2802 assert(root->get_leaf() == leaf_);
2805 slot =
const_cast<tagged_node_ptr *
>(
2806 &*leaf_->parent->find_child(leaf_));
2809 auto old_leaf = leaf_;
2812 *slot = leaf::make_key_args(old_leaf->parent,
2813 old_leaf->key(), rhs);
2814 delete_persistent<typename radix_tree::leaf>(old_leaf);
2817 leaf_ = slot->get_leaf();
2826 template <
typename Key,
typename Value,
typename BytesView>
2827 template <
bool IsConst>
2828 template <
typename T,
typename V,
typename Enable>
2833 auto pop =
pool_base(pmemobj_pool_by_ptr(leaf_));
2836 [&] { leaf_->value() = std::forward<T>(rhs); });
2839 template <
typename Key,
typename Value,
typename BytesView>
2840 template <
bool IsConst>
2851 auto it = leaf_->parent->template find_child<
2852 radix_tree::node::direction::Forward>(leaf_);
2854 leaf_ =
const_cast<leaf_ptr
>(
2855 next_leaf<radix_tree::node::direction::Forward>(
2856 it, leaf_->parent));
2862 template <
typename Key,
typename Value,
typename BytesView>
2863 template <
bool IsConst>
2864 typename radix_tree<Key, Value,
2865 BytesView>::template radix_tree_iterator<IsConst> &
2870 leaf_ =
const_cast<leaf_ptr
>(
2871 radix_tree::find_leaf<
2872 radix_tree::node::direction::Reverse>(*root));
2875 assert(leaf_->parent);
2877 auto it = leaf_->parent->template find_child<
2878 radix_tree::node::direction::Reverse>(leaf_);
2880 leaf_ =
const_cast<leaf_ptr
>(
2881 next_leaf<radix_tree::node::direction::Reverse>(
2882 it, leaf_->parent));
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>
2903 typename radix_tree<Key, Value,
2904 BytesView>::template radix_tree_iterator<IsConst>
2914 template <
typename Key,
typename Value,
typename BytesView>
2915 template <
bool IsConst>
2919 const radix_tree_iterator<C> &rhs)
const
2921 return leaf_ != rhs.leaf_;
2924 template <
typename Key,
typename Value,
typename BytesView>
2925 template <
bool IsConst>
2929 const radix_tree_iterator<C> &rhs)
const
2931 return !(*
this != rhs);
2939 template <
typename Key,
typename Value,
typename BytesView>
2940 template <
bool Direction,
typename Iterator>
2941 typename radix_tree<Key, Value, BytesView>::leaf *
2942 radix_tree<Key, Value, BytesView>::next_leaf(Iterator node,
2943 tagged_node_ptr parent)
2947 }
while (node != parent->template end<Direction>() && !(*node));
2950 if (node == parent->template end<Direction>()) {
2951 auto p = parent->parent;
2955 auto p_it = p->template find_child<Direction>(parent);
2956 return next_leaf<Direction>(p_it, p);
2959 return find_leaf<Direction>(*node);
2966 template <
typename Key,
typename Value,
typename BytesView>
2967 template <
bool Direction>
2968 typename radix_tree<Key, Value, BytesView>::leaf *
2969 radix_tree<Key, Value, BytesView>::find_leaf(
2970 typename radix_tree<Key, Value, BytesView>::tagged_node_ptr n)
2975 return n.get_leaf();
2977 for (
auto it = n->template begin<Direction>();
2978 it != n->template end<Direction>(); ++it) {
2980 return find_leaf<Direction>(*it);
2987 template <
typename Key,
typename Value,
typename BytesView>
2989 radix_tree<Key, Value, BytesView>::leaf::key()
2991 return *
reinterpret_cast<Key *
>(
this + 1);
2994 template <
typename Key,
typename Value,
typename BytesView>
2996 radix_tree<Key, Value, BytesView>::leaf::value()
2998 auto key_dst =
reinterpret_cast<char *
>(
this + 1);
2999 auto val_dst =
reinterpret_cast<Value *
>(
3000 key_dst + total_sizeof<Key>::value(key()));
3002 return *
reinterpret_cast<Value *
>(val_dst);
3005 template <
typename Key,
typename Value,
typename BytesView>
3007 radix_tree<Key, Value, BytesView>::leaf::key()
const
3009 return *
reinterpret_cast<const Key *
>(
this + 1);
3012 template <
typename Key,
typename Value,
typename BytesView>
3014 radix_tree<Key, Value, BytesView>::leaf::value()
const
3016 auto key_dst =
reinterpret_cast<const char *
>(
this + 1);
3017 auto val_dst =
reinterpret_cast<const Value *
>(
3018 key_dst + total_sizeof<Key>::value(key()));
3020 return *
reinterpret_cast<const Value *
>(val_dst);
3023 template <
typename Key,
typename Value,
typename BytesView>
3024 radix_tree<Key, Value, BytesView>::leaf::~leaf()
3026 detail::destroy<Key>(key());
3027 detail::destroy<Value>(value());
3030 template <
typename Key,
typename Value,
typename BytesView>
3031 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3032 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent)
3034 auto t = std::make_tuple();
3035 return make(parent, std::piecewise_construct, t, t,
3036 typename detail::make_index_sequence<>::type{},
3037 typename detail::make_index_sequence<>::type{});
3040 template <
typename Key,
typename Value,
typename BytesView>
3041 template <
typename... Args1,
typename... Args2>
3042 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3043 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
3044 std::piecewise_construct_t pc,
3045 std::tuple<Args1...> first_args,
3046 std::tuple<Args2...> second_args)
3048 return make(parent, pc, first_args, second_args,
3049 typename detail::make_index_sequence<Args1...>::type{},
3050 typename detail::make_index_sequence<Args2...>::type{});
3053 template <
typename Key,
typename Value,
typename BytesView>
3054 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3055 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
3056 const Key &k,
const Value &v)
3058 return make(parent, std::piecewise_construct, std::forward_as_tuple(k),
3059 std::forward_as_tuple(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(tagged_node_ptr parent, K &&k,
3068 return make(parent, std::piecewise_construct,
3069 std::forward_as_tuple(std::forward<K>(k)),
3070 std::forward_as_tuple(std::forward<V>(v)));
3073 template <
typename Key,
typename Value,
typename BytesView>
3074 template <
typename K,
typename... Args>
3075 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3076 radix_tree<Key, Value, BytesView>::leaf::make_key_args(tagged_node_ptr parent,
3077 K &&k, Args &&... args)
3079 return make(parent, std::piecewise_construct,
3080 std::forward_as_tuple(std::forward<K>(k)),
3081 std::forward_as_tuple(std::forward<Args>(args)...));
3084 template <
typename Key,
typename Value,
typename BytesView>
3085 template <
typename K,
typename V>
3086 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3087 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
3088 detail::pair<K, V> &&p)
3090 return make(parent, std::piecewise_construct,
3091 std::forward_as_tuple(std::move(p.first)),
3092 std::forward_as_tuple(std::move(p.second)));
3095 template <
typename Key,
typename Value,
typename BytesView>
3096 template <
typename K,
typename V>
3097 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3098 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
3099 const detail::pair<K, V> &p)
3101 return make(parent, std::piecewise_construct,
3102 std::forward_as_tuple(p.first),
3103 std::forward_as_tuple(p.second));
3106 template <
typename Key,
typename Value,
typename BytesView>
3107 template <
typename K,
typename V>
3108 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3109 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
3110 std::pair<K, V> &&p)
3112 return make(parent, std::piecewise_construct,
3113 std::forward_as_tuple(std::move(p.first)),
3114 std::forward_as_tuple(std::move(p.second)));
3117 template <
typename Key,
typename Value,
typename BytesView>
3118 template <
typename K,
typename V>
3119 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3120 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
3121 const std::pair<K, V> &p)
3123 return make(parent, std::piecewise_construct,
3124 std::forward_as_tuple(p.first),
3125 std::forward_as_tuple(p.second));
3128 template <
typename Key,
typename Value,
typename BytesView>
3129 template <
typename... Args1,
typename... Args2,
size_t... I1,
size_t... I2>
3130 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3131 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
3132 std::piecewise_construct_t,
3133 std::tuple<Args1...> &first_args,
3134 std::tuple<Args2...> &second_args,
3135 detail::index_sequence<I1...>,
3136 detail::index_sequence<I2...>)
3138 standard_alloc_policy<void> a;
3139 auto key_size = total_sizeof<Key>::value(std::get<I1>(first_args)...);
3141 total_sizeof<Value>::value(std::get<I2>(second_args)...);
3142 auto ptr =
static_cast<persistent_ptr<leaf>
>(
3143 a.allocate(
sizeof(leaf) + key_size + val_size));
3145 auto key_dst =
reinterpret_cast<Key *
>(ptr.get() + 1);
3146 auto val_dst =
reinterpret_cast<Value *
>(
3147 reinterpret_cast<char *
>(key_dst) + key_size);
3149 new (ptr.get()) leaf();
3150 new (key_dst) Key(std::forward<Args1>(std::get<I1>(first_args))...);
3151 new (val_dst) Value(std::forward<Args2>(std::get<I2>(second_args))...);
3153 ptr->parent = parent;
3158 template <
typename Key,
typename Value,
typename BytesView>
3159 persistent_ptr<typename radix_tree<Key, Value, BytesView>::leaf>
3160 radix_tree<Key, Value, BytesView>::leaf::make(tagged_node_ptr parent,
3163 return make(parent, other.key(), other.value());
3172 template <
typename Key,
typename Value,
typename BytesView>
3176 if (
nullptr == pmemobj_pool_by_ptr(
this))
3187 template <
typename Key,
typename Value,
typename BytesView>
3191 if (pmemobj_tx_stage() != TX_STAGE_WORK)
3193 "Function called out of transaction scope.");
3199 template <
typename Key,
typename Value,
typename BytesView>
3215 struct is_string : std::false_type {
3218 template <
typename CharT,
typename Traits>
3219 struct is_string<obj::basic_string<CharT, Traits>> : std::true_type {
3222 template <
typename CharT,
typename Traits>
3223 struct is_string<obj::experimental::basic_inline_string<CharT, Traits>>
3227 template <
typename T>
3228 struct bytes_view<T, typename std::enable_if<is_string<T>::value>::type> {
3229 using CharT =
typename T::value_type;
3230 using Traits =
typename T::traits_type;
3234 typename Enable =
typename std::enable_if<std::is_constructible<
3235 obj::basic_string_view<CharT, Traits>, C>::value>::type>
3236 bytes_view(
const C *s) : s(*s)
3240 char operator[](std::size_t p)
const
3242 return reinterpret_cast<const char *
>(s.data())[p];
3248 return s.size() *
sizeof(CharT);
3251 obj::basic_string_view<CharT, Traits> s;
3253 using is_transparent = void;
3256 template <
typename T>
3257 struct bytes_view<T,
3258 typename std::enable_if<std::is_integral<T>::value &&
3259 !std::is_signed<T>::value>::type> {
3260 bytes_view(
const T *k) : k(k)
3262 #if __cpp_lib_endian
3264 std::endian::native == std::endian::little,
3265 "Scalar type are not little endian on this platform!");
3266 #elif !defined(NDEBUG)
3268 uint16_t word = (2 << 8) + 1;
3269 assert(((
char *)&word)[0] == 1);
3273 char operator[](std::size_t p)
const
3275 return reinterpret_cast<const char *
>(k)[size() - p - 1];
Persistent memory aware allocator.
Our partial std::string_view implementation.
Definition: string_view.hpp:46
constexpr size_type size() const noexcept
Returns count of characters stored in this pmem::obj::string_view data.
Definition: string_view.hpp:334
static void run(obj::pool_base &pool, std::function< void()> tx, Locks &... locks)
Execute a closure-like transaction and lock locks.
Definition: transaction.hpp:688
Radix tree is an associative, ordered container.
Definition: radix_tree.hpp:105
const_iterator cend() const
Returns a const iterator to the element following the last element of the map.
Definition: radix_tree.hpp:2259
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:1375
void check_tx_stage_work()
Private helper function.
Definition: radix_tree.hpp:3189
friend std::ostream & operator<<(std::ostream &os, const radix_tree< K, V, BV > &tree)
Prints tree in DOT format.
Definition: radix_tree.hpp:2412
void swap(radix_tree &rhs)
Member swap.
Definition: radix_tree.hpp:927
const_iterator cbegin() const
Returns a const iterator to the first element of the container.
Definition: radix_tree.hpp:2239
reverse_iterator rend()
Returns a reverse iterator to the end.
Definition: radix_tree.hpp:2311
void clear()
Erases all elements from the container transactionally.
Definition: radix_tree.hpp:1781
iterator end()
Returns an iterator to the element following the last element of the map.
Definition: radix_tree.hpp:2223
void check_pmem()
Private helper function.
Definition: radix_tree.hpp:3174
const_reverse_iterator crbegin() const
Returns a const, reverse iterator to the beginning.
Definition: radix_tree.hpp:2323
iterator upper_bound(const key_type &k)
Returns an iterator pointing to the first element that is greater than key.
Definition: radix_tree.hpp:2147
uint64_t size() const noexcept
Definition: radix_tree.hpp:915
reverse_iterator rbegin()
Returns a reverse iterator to the beginning.
Definition: radix_tree.hpp:2298
bool empty() const noexcept
Checks whether the container is empty.
Definition: radix_tree.hpp:895
radix_tree()
Default radix tree constructor.
Definition: radix_tree.hpp:671
size_type max_size() const noexcept
Definition: radix_tree.hpp:905
~radix_tree()
Destructor.
Definition: radix_tree.hpp:879
radix_tree & operator=(const radix_tree &m)
Copy assignment operator.
Definition: radix_tree.hpp:792
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:2067
iterator find(const key_type &k)
Finds an element with key equivalent to key.
Definition: radix_tree.hpp:1688
iterator begin()
Returns an iterator to the first element of the container.
Definition: radix_tree.hpp:2206
iterator erase(const_iterator pos)
Removes the element at pos from the container.
Definition: radix_tree.hpp:1804
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:1653
const_reverse_iterator crend() const
Returns a const, reverse iterator to the end.
Definition: radix_tree.hpp:2336
Volatile residing on pmem class.
Definition: v.hpp:42
static void run(obj::pool_base &pool, std::function< void()> tx, Locks &... locks)
Execute a closure-like transaction and lock locks.
Definition: transaction.hpp:817
Resides on pmem class.
Definition: p.hpp:35
Persistent pointer class.
Definition: persistent_ptr.hpp:152
The non-template pool base class.
Definition: pool.hpp:46
Custom pool error class.
Definition: pexceptions.hpp:45
Custom transaction error class.
Definition: pexceptions.hpp:158
Commonly used functionality.
Inline string implementation.
Create c++14 style index sequence.
Persistent_ptr transactional allocation functions for objects.
bool operator==(self_relative_ptr< T > const &lhs, self_relative_ptr< Y > const &rhs) noexcept
Equality operator.
Definition: self_relative_ptr.hpp:387
std::ostream & operator<<(std::ostream &os, const radix_tree< K, V, BV > &tree)
Prints tree in DOT format.
Definition: radix_tree.hpp:2412
void swap(concurrent_map< Key, Value, Comp, Allocator > &lhs, concurrent_map< Key, Value, Comp, Allocator > &rhs)
Non-member swap.
Definition: concurrent_map.hpp:151
void swap(radix_tree< Key, Value, BytesView > &lhs, radix_tree< Key, Value, BytesView > &rhs)
Non-member swap.
Definition: radix_tree.hpp:3201
bool operator!=(self_relative_ptr< T > const &lhs, self_relative_ptr< Y > const &rhs) noexcept
Inequality operator.
Definition: self_relative_ptr.hpp:398
p< T > & operator++(p< T > &pp)
Prefix increment operator overload.
Definition: pext.hpp:48
pmem::obj::array< T, N >::const_iterator cbegin(const pmem::obj::array< T, N > &a)
Non-member cbegin.
Definition: array.hpp:760
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
pmem::obj::array< T, N >::iterator end(pmem::obj::array< T, N > &a)
Non-member end.
Definition: array.hpp:820
T & get(pmem::obj::array< T, N > &a)
Non-member get function.
Definition: array.hpp:890
pool_base pool_by_vptr(const T *that)
Retrieve pool handle for the given pointer.
Definition: utils.hpp:32
bool operator==(standard_alloc_policy< T > const &, standard_alloc_policy< T2 > const &)
Determines if memory from another allocator can be deallocated from this one.
Definition: allocator.hpp:420
pmem::obj::array< T, N >::const_iterator cend(const pmem::obj::array< T, N > &a)
Non-member cend.
Definition: array.hpp:770
pmem::obj::array< T, N >::iterator begin(pmem::obj::array< T, N > &a)
Non-member begin.
Definition: array.hpp:800
Persistent memory namespace.
Definition: allocation_flag.hpp:15
Resides on pmem property template.
Persistent smart pointer.
Convenience extensions for the resides on pmem property template.
Persistent self-relative smart pointer.
String typedefs for common character types.
Our partial std::string_view implementation.
This is the structure which 'holds' key/value pair.
Definition: radix_tree.hpp:401
This is internal node.
Definition: radix_tree.hpp:467
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:496
tagged_node_ptr parent
Pointer to a parent node.
Definition: radix_tree.hpp:473
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:481
Radix tree iterator supports multipass and bidirectional iteration.
Definition: radix_tree.hpp:571
Commonly used SFINAE helpers.
C++ pmemobj transactions.