PMDK C++ bindings 1.13.0
This is the C++ bindings documentation for PMDK's libpmemobj.
concurrent_skip_list_impl.hpp
1// SPDX-License-Identifier: BSD-3-Clause
2/* Copyright 2020-2021, Intel Corporation */
3
4#ifndef PMEMOBJ_CONCURRENT_SKIP_LIST_IMPL_HPP
5#define PMEMOBJ_CONCURRENT_SKIP_LIST_IMPL_HPP
6
7#include <algorithm>
8#include <array>
9#include <atomic>
10#include <cstdlib>
11#include <limits>
12#include <mutex> /* for std::unique_lock */
13#include <random>
14#include <type_traits>
15
19#include <libpmemobj++/detail/pair.hpp>
23#include <libpmemobj++/pool.hpp>
25
26#include <libpmemobj++/experimental/atomic_self_relative_ptr.hpp>
28
29/* Windows has a max and a min macros which collides with min() and max()
30 * methods of default_random_generator */
31#if defined(_WIN32)
32#if defined(max)
33#undef max
34#endif
35#if defined(min)
36#undef min
37#endif
38#endif
39
40namespace pmem
41{
42namespace detail
43{
44
45#ifndef NDEBUG
46inline void
47try_insert_node_finish_marker()
48{
49}
50#endif
51
56template <typename MyAlloc, typename OtherAlloc>
57inline void
58allocator_copy_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator,
59 std::true_type)
60{
61 my_allocator = other_allocator;
62}
63
68template <typename MyAlloc, typename OtherAlloc>
69inline void
70allocator_copy_assignment(MyAlloc &, OtherAlloc &, std::false_type)
71{ /* NO COPY */
72}
73
78template <typename MyAlloc, typename OtherAlloc>
79inline void
80allocator_move_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator,
81 std::true_type)
82{
83 my_allocator = std::move(other_allocator);
84}
85
90template <typename MyAlloc, typename OtherAlloc>
91inline void
92allocator_move_assignment(MyAlloc &, OtherAlloc &, std::false_type)
93{ /* NO MOVE */
94}
95
100template <typename MyAlloc, typename OtherAlloc>
101inline void
102allocator_swap(MyAlloc &my_allocator, OtherAlloc &other_allocator,
103 std::true_type)
104{
105 std::swap(my_allocator, other_allocator);
106}
107
112template <typename MyAlloc, typename OtherAlloc>
113inline void
114allocator_swap(MyAlloc &, OtherAlloc &, std::false_type)
115{ /* NO SWAP */
116}
117
118template <typename Value, typename Mutex = pmem::obj::mutex,
119 typename LockType = std::unique_lock<Mutex>>
120class skip_list_node {
121public:
122 using value_type = Value;
123 using size_type = std::size_t;
124 using reference = value_type &;
125 using const_reference = const value_type &;
126 using pointer = value_type *;
127 using const_pointer = const value_type *;
128 using node_pointer =
130 using atomic_node_pointer = std::atomic<node_pointer>;
131 using mutex_type = Mutex;
132 using lock_type = LockType;
133
134 skip_list_node(size_type levels) : height_(levels)
135 {
136 for (size_type lev = 0; lev < height_; ++lev)
137 detail::create<atomic_node_pointer>(&get_next(lev),
138 nullptr);
139
140 assert(height() == levels);
141#if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
142 /*
143 * Valgrind does not understand atomic semantic and reports
144 * false-postives in drd and helgrind tools.
145 */
146 for (size_type lev = 0; lev < height_; ++lev) {
147 VALGRIND_HG_DISABLE_CHECKING(&get_next(lev),
148 sizeof(get_next(lev)));
149 }
150#endif
151 }
152
153 skip_list_node(size_type levels, const node_pointer *new_nexts)
154 : height_(levels)
155 {
156 for (size_type lev = 0; lev < height_; ++lev)
157 detail::create<atomic_node_pointer>(&get_next(lev),
158 new_nexts[lev]);
159
160 assert(height() == levels);
161#if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED
162 /*
163 * Valgrind does not understand atomic semantic and reports
164 * false-postives in drd and helgrind tools.
165 */
166 for (size_type lev = 0; lev < height_; ++lev) {
167 VALGRIND_HG_DISABLE_CHECKING(&get_next(lev),
168 sizeof(get_next(lev)));
169 }
170#endif
171 }
172
173 ~skip_list_node()
174 {
175 for (size_type lev = 0; lev < height_; ++lev)
176 detail::destroy<atomic_node_pointer>(get_next(lev));
177 }
178
179 skip_list_node(const skip_list_node &) = delete;
180
181 skip_list_node &operator=(const skip_list_node &) = delete;
182
183 pointer
184 get() noexcept
185 {
186 return &val;
187 }
188
189 const_pointer
190 get() const noexcept
191 {
192 return &val;
193 }
194
195 reference
196 value()
197 {
198 return *get();
199 }
200
201 node_pointer
202 next(size_type level) const
203 {
204 assert(level < height());
205 return get_next(level).load(std::memory_order_acquire);
206 }
207
212 void
213 set_next_tx(size_type level, node_pointer next)
214 {
215 assert(level < height());
216 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
217 auto &node = get_next(level);
218 obj::flat_transaction::snapshot<atomic_node_pointer>(&node);
219 node.store(next, std::memory_order_release);
220 }
221
222 void
223 set_next(obj::pool_base pop, size_type level, node_pointer next)
224 {
225 assert(level < height());
226 auto &node = get_next(level);
227 node.store(next, std::memory_order_release);
228 pop.persist(&node, sizeof(node));
229 }
230
231 void
232 set_nexts(const node_pointer *new_nexts, size_type h)
233 {
234 assert(h == height());
235 auto *nexts = get_nexts();
236
237 for (size_type i = 0; i < h; i++) {
238 nexts[i].store(new_nexts[i], std::memory_order_relaxed);
239 }
240 }
241
242 void
243 set_nexts(obj::pool_base pop, const node_pointer *new_nexts,
244 size_type h)
245 {
246 set_nexts(new_nexts, h);
247
248 auto *nexts = get_nexts();
249 pop.persist(nexts, sizeof(nexts[0]) * h);
250 }
251
253 size_type
254 height() const
255 {
256 return height_;
257 }
258
259 lock_type
260 acquire()
261 {
262 return lock_type(mutex);
263 }
264
265private:
266 atomic_node_pointer *
267 get_nexts()
268 {
269 return reinterpret_cast<atomic_node_pointer *>(this + 1);
270 }
271
272 atomic_node_pointer &
273 get_next(size_type level)
274 {
275 auto *arr = get_nexts();
276 return arr[level];
277 }
278
279 const atomic_node_pointer &
280 get_next(size_type level) const
281 {
282 auto *arr =
283 reinterpret_cast<const atomic_node_pointer *>(this + 1);
284 return arr[level];
285 }
286
287 mutex_type mutex;
288 union {
289 value_type val;
290 };
291 size_type height_;
292};
293
294template <typename NodeType, bool is_const>
295class skip_list_iterator {
296 using node_type = NodeType;
297 using node_ptr = typename std::conditional<is_const, const node_type *,
298 node_type *>::type;
299 friend class skip_list_iterator<node_type, true>;
300
301public:
302 using value_type = typename node_type::value_type;
303 using iterator_category = std::forward_iterator_tag;
304 using difference_type = std::ptrdiff_t;
305 using reference =
306 typename std::conditional<is_const,
307 typename node_type::const_reference,
308 typename node_type::reference>::type;
309 using pointer = typename std::conditional<is_const, const value_type *,
310 value_type *>::type;
311
312 skip_list_iterator() : node(nullptr)
313 {
314 }
315
317 skip_list_iterator(const skip_list_iterator &other) : node(other.node)
318 {
319 }
320
322 template <typename U = void,
323 typename = typename std::enable_if<is_const, U>::type>
324 skip_list_iterator(const skip_list_iterator<node_type, false> &other)
325 : node(other.node)
326 {
327 }
328
329 reference operator*() const
330 {
331 return *(node->get());
332 }
333
334 pointer operator->() const
335 {
336 return node->get();
337 }
338
339 skip_list_iterator &
340 operator++()
341 {
342 assert(node != nullptr);
343 node = node->next(0).get();
344 return *this;
345 }
346
347 skip_list_iterator
348 operator++(int)
349 {
350 skip_list_iterator tmp = *this;
351 ++*this;
352 return tmp;
353 }
354
355 skip_list_iterator &
356 operator=(const skip_list_iterator &other)
357 {
358 node = other.node;
359 return *this;
360 }
361
362private:
363 explicit skip_list_iterator(node_type *n) : node(n)
364 {
365 }
366
367 template <typename T = void,
368 typename = typename std::enable_if<is_const, T>::type>
369 explicit skip_list_iterator(const node_type *n) : node(n)
370 {
371 }
372
373 node_ptr node;
374
375 template <typename Traits>
376 friend class concurrent_skip_list;
377
378 template <typename T, bool M, bool U>
379 friend bool operator==(const skip_list_iterator<T, M> &lhs,
380 const skip_list_iterator<T, U> &rhs);
381
382 template <typename T, bool M, bool U>
383 friend bool operator!=(const skip_list_iterator<T, M> &lhs,
384 const skip_list_iterator<T, U> &rhs);
385};
386
387template <typename T, bool M, bool U>
388bool
389operator==(const skip_list_iterator<T, M> &lhs,
390 const skip_list_iterator<T, U> &rhs)
391{
392 return lhs.node == rhs.node;
393}
394
395template <typename T, bool M, bool U>
396bool
397operator!=(const skip_list_iterator<T, M> &lhs,
398 const skip_list_iterator<T, U> &rhs)
399{
400 return lhs.node != rhs.node;
401}
402
403struct default_random_generator {
404 using gen_type = std::mt19937_64;
405 using result_type = typename gen_type::result_type;
406
407 size_t
408 operator()()
409 {
410 static thread_local gen_type engine(
411 static_cast<size_t>(time(0)));
412
413 return engine();
414 }
415
416 static constexpr result_type
417 min()
418 {
419 return gen_type::min();
420 }
421
422 static constexpr result_type
423 max()
424 {
425 return gen_type::max();
426 }
427};
428
429template <typename RndGenerator, size_t MAX_LEVEL>
430class geometric_level_generator {
431public:
432 using rnd_generator_type = RndGenerator;
433
434 static constexpr size_t max_level = MAX_LEVEL;
435
436 size_t
437 operator()()
438 {
439 /* rnd_generator_type should be thread-safe random number
440 * generator. */
441 static rnd_generator_type gen;
442 /* std::geometric_distribution is not thread-safe. We mark it as
443 * a thread_local to avoid data races. */
444 static thread_local std::geometric_distribution<size_t> d;
445
446 return (d(gen) % MAX_LEVEL) + 1;
447 }
448};
449
478template <typename Traits>
480protected:
481 using traits_type = Traits;
482 using key_type = typename traits_type::key_type;
483 using mapped_type = typename traits_type::mapped_type;
484 using value_type = typename traits_type::value_type;
485 using size_type = std::size_t;
486 using difference_type = std::ptrdiff_t;
487 using key_compare = typename traits_type::compare_type;
488 using allocator_type = typename traits_type::allocator_type;
489 using allocator_traits_type = std::allocator_traits<allocator_type>;
490
491 using reference = value_type &;
492 using const_reference = const value_type &;
493 using pointer = typename allocator_traits_type::pointer;
494 using const_pointer = typename allocator_traits_type::const_pointer;
495
496 using list_node_type = skip_list_node<value_type>;
497
498 using iterator = skip_list_iterator<list_node_type, false>;
499 using const_iterator = skip_list_iterator<list_node_type, true>;
500
501 static constexpr size_type MAX_LEVEL = traits_type::max_level;
502
503 using random_level_generator_type = geometric_level_generator<
504 typename traits_type::random_generator_type, MAX_LEVEL>;
505 using node_allocator_type = typename std::allocator_traits<
506 allocator_type>::template rebind_alloc<uint8_t>;
507 using node_allocator_traits = typename std::allocator_traits<
508 allocator_type>::template rebind_traits<uint8_t>;
509 using node_ptr = list_node_type *;
510 using const_node_ptr = const list_node_type *;
511 using persistent_node_ptr =
513
514 using prev_array_type = std::array<node_ptr, MAX_LEVEL>;
515 using next_array_type = std::array<persistent_node_ptr, MAX_LEVEL>;
516 using node_lock_type = typename list_node_type::lock_type;
517 using lock_array = std::array<node_lock_type, MAX_LEVEL>;
518
519public:
520 static constexpr bool allow_multimapping =
521 traits_type::allow_multimapping;
522
532 {
534 init();
535 }
536
554 const key_compare &comp,
555 const allocator_type &alloc = allocator_type())
556 : _node_allocator(alloc), _compare(comp)
557 {
559 init();
560 }
561
585 template <class InputIt>
586 concurrent_skip_list(InputIt first, InputIt last,
587 const key_compare &comp = key_compare(),
588 const allocator_type &alloc = allocator_type())
589 : _node_allocator(alloc), _compare(comp)
590 {
592 init();
593 while (first != last)
594 internal_unsafe_emplace(*first++);
595 }
596
615 : _node_allocator(node_allocator_traits::
616 select_on_container_copy_construction(
617 other._node_allocator)),
618 _compare(other._compare),
619 _rnd_generator(other._rnd_generator)
620 {
622 init();
623 internal_copy(other);
624 assert(_size == other._size);
625 }
626
647 const allocator_type &alloc)
648 : _node_allocator(alloc),
649 _compare(other._compare),
650 _rnd_generator(other._rnd_generator)
651 {
653 init();
654 internal_copy(other);
655 assert(_size == other._size);
656 }
657
677 : _node_allocator(std::move(other._node_allocator)),
678 _compare(other._compare),
679 _rnd_generator(other._rnd_generator)
680 {
682 init();
683 internal_move(std::move(other));
684 }
685
706 const allocator_type &alloc)
707 : _node_allocator(alloc),
708 _compare(other._compare),
709 _rnd_generator(other._rnd_generator)
710 {
712 init();
713 if (alloc == other.get_allocator()) {
714 internal_move(std::move(other));
715 } else {
716 init();
717 internal_copy(std::make_move_iterator(other.begin()),
718 std::make_move_iterator(other.end()));
719 }
720 }
721
728 void
730 {
731 tls_restore();
732
733 assert(this->size() ==
734 size_type(std::distance(this->begin(), this->end())));
735 }
736
749 void
751 {
752 if (dummy_head == nullptr)
753 return;
754
755 auto pop = get_pool_base();
757 clear();
758 delete_dummy_head();
759 });
760 }
761
772 {
773 try {
774 free_data();
775 } catch (...) {
776 std::terminate();
777 }
778 }
779
797 {
798 if (this == &other)
799 return *this;
800
803 using pocca_t = typename node_allocator_traits::
804 propagate_on_container_copy_assignment;
805 clear();
806 allocator_copy_assignment(_node_allocator,
807 other._node_allocator,
808 pocca_t());
809 _compare = other._compare;
810 _rnd_generator = other._rnd_generator;
811
812 internal_copy(other);
813 });
814 return *this;
815 }
816
839 {
840 if (this == &other)
841 return *this;
842
845 using pocma_t = typename node_allocator_traits::
846 propagate_on_container_move_assignment;
847 clear();
848 if (pocma_t::value ||
849 _node_allocator == other._node_allocator) {
850 delete_dummy_head();
851 allocator_move_assignment(_node_allocator,
852 other._node_allocator,
853 pocma_t());
854 _compare = other._compare;
855 _rnd_generator = other._rnd_generator;
856 internal_move(std::move(other));
857 } else {
858 internal_copy(
859 std::make_move_iterator(other.begin()),
860 std::make_move_iterator(other.end()));
861 }
862 });
863 return *this;
864 }
865
878 operator=(std::initializer_list<value_type> il)
879 {
882 clear();
883 for (auto it = il.begin(); it != il.end(); ++it)
885 });
886 return *this;
887 }
888
905 std::pair<iterator, bool>
906 insert(const value_type &value)
907 {
908 return internal_insert(value.first, value);
909 }
910
929 template <typename P,
930 typename std::enable_if<
931 std::is_constructible<value_type, P &&>::value>::type>
932 std::pair<iterator, bool>
933 insert(P &&value)
934 {
935 return emplace(std::forward<P>(value));
936 }
937
954 std::pair<iterator, bool>
955 insert(value_type &&value)
956 {
957 return internal_insert(value.first, std::move(value));
958 }
959
977 iterator
978 insert(const_iterator hint, const_reference value)
979 {
980 /* Ignore hint */
981 return insert(value).first;
982 }
983
1004 template <typename P,
1005 typename std::enable_if<
1006 std::is_constructible<value_type, P &&>::value>::type>
1007 iterator
1008 insert(const_iterator hint, P &&value)
1009 {
1010 return emplace_hint(hint, std::forward<P>(value));
1011 }
1012
1027 template <typename InputIterator>
1028 void
1029 insert(InputIterator first, InputIterator last)
1030 {
1031 for (InputIterator it = first; it != last; ++it)
1032 insert(*it);
1033 }
1034
1048 void
1049 insert(std::initializer_list<value_type> ilist)
1050 {
1051 insert(ilist.begin(), ilist.end());
1052 }
1053
1081 template <typename... Args>
1082 std::pair<iterator, bool>
1083 emplace(Args &&... args)
1084 {
1085 return internal_emplace(std::forward<Args>(args)...);
1086 }
1087
1118 template <typename... Args>
1119 iterator
1120 emplace_hint(const_iterator hint, Args &&... args)
1121 {
1122 /* Ignore hint */
1123 return emplace(std::forward<Args>(args)...).first;
1124 }
1125
1149 template <typename... Args>
1150 std::pair<iterator, bool>
1151 try_emplace(const key_type &k, Args &&... args)
1152 {
1153 return internal_try_emplace(k, std::forward<Args>(args)...);
1154 }
1155
1179 template <typename... Args>
1180 std::pair<iterator, bool>
1181 try_emplace(key_type &&k, Args &&... args)
1182 {
1183 return internal_try_emplace(std::move(k),
1184 std::forward<Args>(args)...);
1185 }
1186
1213 template <typename K, typename... Args>
1214 typename std::enable_if<
1215 has_is_transparent<key_compare>::value &&
1216 std::is_constructible<key_type, K &&>::value,
1217 std::pair<iterator, bool>>::type
1218 try_emplace(K &&k, Args &&... args)
1219 {
1220 return internal_try_emplace(std::forward<K>(k),
1221 std::forward<Args>(args)...);
1222 }
1223
1240 iterator
1241 unsafe_erase(iterator pos)
1242 {
1243 check_outside_tx();
1244 auto &size_diff = tls_data.local().size_diff;
1245 return internal_erase(pos, size_diff);
1246 }
1247
1264 iterator
1265 unsafe_erase(const_iterator pos)
1266 {
1267 return unsafe_erase(get_iterator(pos));
1268 }
1269
1284 iterator
1285 unsafe_erase(const_iterator first, const_iterator last)
1286 {
1287 check_outside_tx();
1289 auto &size_diff = tls_data.local().size_diff;
1290
1292 while (first != last) {
1293 first = internal_erase(first, size_diff);
1294 }
1295 });
1296
1297 return get_iterator(first);
1298 }
1299
1312 size_type
1313 unsafe_erase(const key_type &key)
1314 {
1315 std::pair<iterator, iterator> range = equal_range(key);
1316 size_type sz = static_cast<size_type>(
1317 std::distance(range.first, range.second));
1318 unsafe_erase(range.first, range.second);
1319 return sz;
1320 }
1321
1340 template <
1341 typename K,
1342 typename = typename std::enable_if<
1343 has_is_transparent<key_compare>::value &&
1344 !std::is_convertible<K, iterator>::value &&
1345 !std::is_convertible<K, const_iterator>::value,
1346 K>::type>
1347 size_type
1348 unsafe_erase(const K &key)
1349 {
1350 std::pair<iterator, iterator> range = equal_range(key);
1351 size_type sz = static_cast<size_type>(
1352 std::distance(range.first, range.second));
1353 unsafe_erase(range.first, range.second);
1354 return sz;
1355 }
1356
1367 iterator
1368 lower_bound(const key_type &key)
1369 {
1370 return internal_get_bound(key, _compare);
1371 }
1372
1383 const_iterator
1384 lower_bound(const key_type &key) const
1385 {
1386 return internal_get_bound(key, _compare);
1387 }
1388
1402 template <typename K,
1403 typename = typename std::enable_if<
1404 has_is_transparent<key_compare>::value, K>::type>
1405 iterator
1406 lower_bound(const K &x)
1407 {
1408 return internal_get_bound(x, _compare);
1409 }
1410
1424 template <typename K,
1425 typename = typename std::enable_if<
1426 has_is_transparent<key_compare>::value, K>::type>
1427 const_iterator
1428 lower_bound(const K &x) const
1429 {
1430 return internal_get_bound(x, _compare);
1431 }
1432
1443 iterator
1444 find_higher_eq(const key_type &key)
1445 {
1446 return internal_get_bound(key, _compare);
1447 }
1448
1459 const_iterator
1460 find_higher_eq(const key_type &key) const
1461 {
1462 return internal_get_bound(key, _compare);
1463 }
1464
1479 template <typename K,
1480 typename = typename std::enable_if<
1481 has_is_transparent<key_compare>::value, K>::type>
1482 iterator
1483 find_higher_eq(const K &x)
1484 {
1485 return internal_get_bound(x, _compare);
1486 }
1487
1502 template <typename K,
1503 typename = typename std::enable_if<
1504 has_is_transparent<key_compare>::value, K>::type>
1505 const_iterator
1506 find_higher_eq(const K &x) const
1507 {
1508 return internal_get_bound(x, _compare);
1509 }
1510
1521 iterator
1522 upper_bound(const key_type &key)
1523 {
1524 return internal_get_bound(key, not_greater_compare(_compare));
1525 }
1526
1537 const_iterator
1538 upper_bound(const key_type &key) const
1539 {
1540 return internal_get_bound(key, not_greater_compare(_compare));
1541 }
1542
1556 template <typename K,
1557 typename = typename std::enable_if<
1558 has_is_transparent<key_compare>::value, K>::type>
1559 iterator
1560 upper_bound(const K &x)
1561 {
1562 return internal_get_bound(x, not_greater_compare(_compare));
1563 }
1564
1578 template <typename K,
1579 typename = typename std::enable_if<
1580 has_is_transparent<key_compare>::value, K>::type>
1581 const_iterator
1582 upper_bound(const K &x) const
1583 {
1584 return internal_get_bound(x, not_greater_compare(_compare));
1585 }
1586
1597 iterator
1598 find_higher(const key_type &key)
1599 {
1600 return internal_get_bound(key, not_greater_compare(_compare));
1601 }
1602
1613 const_iterator
1614 find_higher(const key_type &key) const
1615 {
1616 return internal_get_bound(key, not_greater_compare(_compare));
1617 }
1618
1632 template <typename K,
1633 typename = typename std::enable_if<
1634 has_is_transparent<key_compare>::value, K>::type>
1635 iterator
1636 find_higher(const K &x)
1637 {
1638 return internal_get_bound(x, not_greater_compare(_compare));
1639 }
1640
1654 template <typename K,
1655 typename = typename std::enable_if<
1656 has_is_transparent<key_compare>::value, K>::type>
1657 const_iterator
1658 find_higher(const K &x) const
1659 {
1660 return internal_get_bound(x, not_greater_compare(_compare));
1661 }
1662
1673 iterator
1674 find_lower(const key_type &key)
1675 {
1676 auto it = internal_get_biggest_less_than(key, _compare);
1677 return iterator(
1678 const_cast<typename iterator::node_ptr>(it.node));
1679 }
1680
1691 const_iterator
1692 find_lower(const key_type &key) const
1693 {
1694 return internal_get_biggest_less_than(key, _compare);
1695 }
1696
1710 template <typename K,
1711 typename = typename std::enable_if<
1712 has_is_transparent<key_compare>::value, K>::type>
1713 iterator
1714 find_lower(const K &key)
1715 {
1716 auto it = internal_get_biggest_less_than(key, _compare);
1717 return iterator(
1718 const_cast<typename iterator::node_ptr>(it.node));
1719 }
1720
1734 template <typename K,
1735 typename = typename std::enable_if<
1736 has_is_transparent<key_compare>::value, K>::type>
1737 const_iterator
1738 find_lower(const K &key) const
1739 {
1740 return internal_get_biggest_less_than(key, _compare);
1741 }
1742
1753 iterator
1754 find_lower_eq(const key_type &key)
1755 {
1757 key, not_greater_compare(_compare));
1758 return iterator(
1759 const_cast<typename iterator::node_ptr>(it.node));
1760 }
1761
1772 const_iterator
1773 find_lower_eq(const key_type &key) const
1774 {
1776 key, not_greater_compare(_compare));
1777 }
1778
1792 template <typename K,
1793 typename = typename std::enable_if<
1794 has_is_transparent<key_compare>::value, K>::type>
1795 iterator
1796 find_lower_eq(const K &key)
1797 {
1799 key, not_greater_compare(_compare));
1800 return iterator(
1801 const_cast<typename iterator::node_ptr>(it.node));
1802 }
1803
1817 template <typename K,
1818 typename = typename std::enable_if<
1819 has_is_transparent<key_compare>::value, K>::type>
1820 const_iterator
1821 find_lower_eq(const K &key) const
1822 {
1824 key, not_greater_compare(_compare));
1825 }
1826
1835 iterator
1836 find(const key_type &key)
1837 {
1838 return internal_find(key);
1839 }
1840
1849 const_iterator
1850 find(const key_type &key) const
1851 {
1852 return internal_find(key);
1853 }
1854
1867 template <typename K,
1868 typename = typename std::enable_if<
1869 has_is_transparent<key_compare>::value, K>::type>
1870 iterator
1871 find(const K &x)
1872 {
1873 return internal_find(x);
1874 }
1875
1888 template <typename K,
1889 typename = typename std::enable_if<
1890 has_is_transparent<key_compare>::value, K>::type>
1891 const_iterator
1892 find(const K &x) const
1893 {
1894 return internal_find(x);
1895 }
1896
1906 size_type
1907 count(const key_type &key) const
1908 {
1909 return internal_count(key);
1910 }
1911
1924 template <typename K,
1925 typename = typename std::enable_if<
1926 has_is_transparent<key_compare>::value, K>::type>
1927 size_type
1928 count(const K &key) const
1929 {
1930 return internal_count(key);
1931 }
1932
1941 bool
1942 contains(const key_type &key) const
1943 {
1944 return find(key) != end();
1945 }
1946
1959 template <typename K,
1960 typename = typename std::enable_if<
1961 has_is_transparent<key_compare>::value, K>::type>
1962 bool
1963 contains(const K &x) const
1964 {
1965 return find(x) != end();
1966 }
1967
1976 void
1978 {
1979 assert(dummy_head->height() > 0);
1981
1982 persistent_node_ptr current = dummy_head->next(0);
1983
1985 while (current) {
1986 assert(current->height() > 0);
1987 persistent_node_ptr next = current->next(0);
1988 delete_node(current);
1989 current = next;
1990 }
1991
1992 node_ptr head = dummy_head.get();
1993 for (size_type i = 0; i < head->height(); ++i) {
1994 head->set_next_tx(i, nullptr);
1995 }
1996
1997 on_init_size = 0;
1998 tls_data.clear();
1999 obj::flat_transaction::snapshot((size_t *)&_size);
2000 _size = 0;
2001 });
2002 }
2003
2010 iterator
2012 {
2013 return iterator(dummy_head.get()->next(0).get());
2014 }
2015
2022 const_iterator
2023 begin() const
2024 {
2025 return const_iterator(dummy_head.get()->next(0).get());
2026 }
2027
2034 const_iterator
2035 cbegin() const
2036 {
2037 return const_iterator(dummy_head.get()->next(0).get());
2038 }
2039
2047 iterator
2049 {
2050 return iterator(nullptr);
2051 }
2052
2060 const_iterator
2061 end() const
2062 {
2063 return const_iterator(nullptr);
2064 }
2065
2073 const_iterator
2074 cend() const
2075 {
2076 return const_iterator(nullptr);
2077 }
2078
2085 size_type
2086 size() const
2087 {
2088 return _size.load(std::memory_order_relaxed);
2089 }
2090
2098 size_type
2099 max_size() const
2100 {
2101 return std::numeric_limits<difference_type>::max();
2102 }
2103
2110 bool
2111 empty() const
2112 {
2113 return 0 == size();
2114 }
2115
2128 void
2130 {
2133 using pocs_t = typename node_allocator_traits::
2134 propagate_on_container_swap;
2135 allocator_swap(_node_allocator, other._node_allocator,
2136 pocs_t());
2137 std::swap(_compare, other._compare);
2138 std::swap(_rnd_generator, other._rnd_generator);
2139 std::swap(dummy_head, other.dummy_head);
2140 on_init_size.swap(other.on_init_size);
2141
2142 obj::flat_transaction::snapshot((size_t *)&_size);
2144 (size_t *)&(other._size));
2145 _size = other._size.exchange(_size,
2146 std::memory_order_relaxed);
2147 });
2148 }
2149
2169 std::pair<iterator, iterator>
2170 equal_range(const key_type &key)
2171 {
2172 return std::pair<iterator, iterator>(lower_bound(key),
2173 upper_bound(key));
2174 }
2175
2195 std::pair<const_iterator, const_iterator>
2196 equal_range(const key_type &key) const
2197 {
2198 return std::pair<const_iterator, const_iterator>(
2199 lower_bound(key), upper_bound(key));
2200 }
2201
2224 template <typename K,
2225 typename = typename std::enable_if<
2226 has_is_transparent<key_compare>::value, K>::type>
2227 std::pair<iterator, iterator>
2228 equal_range(const K &x)
2229 {
2230 return std::pair<iterator, iterator>(lower_bound(x),
2231 upper_bound(x));
2232 }
2233
2256 template <typename K,
2257 typename = typename std::enable_if<
2258 has_is_transparent<key_compare>::value, K>::type>
2259 std::pair<const_iterator, const_iterator>
2260 equal_range(const K &key) const
2261 {
2262 return std::pair<const_iterator, const_iterator>(
2263 lower_bound(key), upper_bound(key));
2264 }
2265
2271 const key_compare &
2272 key_comp() const
2273 {
2274 return _compare;
2275 }
2276
2282 key_compare &
2284 {
2285 return _compare;
2286 }
2287
2288private:
2289 /* Status flags stored in insert_stage field */
2290 enum insert_stage_type : uint8_t { not_started = 0, in_progress = 1 };
2291 /*
2292 * Structure of thread local data.
2293 * Size should be 64 bytes.
2294 */
2295 struct tls_entry_type {
2296 persistent_node_ptr ptr;
2297 obj::p<difference_type> size_diff;
2298 obj::p<insert_stage_type> insert_stage;
2299
2300 char reserved[64 - sizeof(decltype(ptr)) -
2301 sizeof(decltype(size_diff)) -
2302 sizeof(decltype(insert_stage))];
2303 };
2304 static_assert(sizeof(tls_entry_type) == 64,
2305 "The size of tls_entry_type should be 64 bytes.");
2306
2314 void
2316 {
2317 if (pmemobj_tx_stage() != TX_STAGE_WORK)
2319 "Function called out of transaction scope.");
2320 }
2321
2322 /* Helper method which throws an exception when called in a tx */
2323 static inline void
2324 check_outside_tx()
2325 {
2326 if (pmemobj_tx_stage() != TX_STAGE_NONE)
2328 "Function called inside transaction scope.");
2329 }
2330
2331 void
2332 init()
2333 {
2334 if (pool_uuid == 0)
2335 throw pmem::pool_error("Invalid pool handle.");
2336
2337 _size = 0;
2338 on_init_size = 0;
2340 }
2341
2342 void
2343 internal_move(concurrent_skip_list &&other)
2344 {
2345 assert(this->empty());
2346 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2347 dummy_head = other.dummy_head;
2348 other.dummy_head = nullptr;
2349 other.create_dummy_head();
2350
2351 _size.store(other._size.load(std::memory_order_relaxed),
2352 std::memory_order_relaxed);
2353 on_init_size = other.on_init_size;
2354 }
2355
2356 static const_reference
2357 get_val(const_node_ptr n)
2358 {
2359 assert(n);
2360 return *(n->get());
2361 }
2362
2363 static reference
2364 get_val(node_ptr n)
2365 {
2366 assert(n);
2367 return *(n->get());
2368 }
2369
2370 static const key_type &
2371 get_key(const_node_ptr n)
2372 {
2373 assert(n);
2374 return traits_type::get_key(get_val(n));
2375 }
2376
2377 template <typename K>
2378 iterator
2379 internal_find(const K &key)
2380 {
2381 iterator it = lower_bound(key);
2382 return (it == end() || _compare(key, traits_type::get_key(*it)))
2383 ? end()
2384 : it;
2385 }
2386
2387 template <typename K>
2388 const_iterator
2389 internal_find(const K &key) const
2390 {
2391 const_iterator it = lower_bound(key);
2392 return (it == end() || _compare(key, traits_type::get_key(*it)))
2393 ? end()
2394 : it;
2395 }
2396
2397 template <typename K>
2398 size_type
2399 internal_count(const K &key) const
2400 {
2401 if (allow_multimapping) {
2402 std::pair<const_iterator, const_iterator> range =
2403 equal_range(key);
2404 return static_cast<size_type>(
2405 std::distance(range.first, range.second));
2406 }
2407 return (find(key) == end()) ? size_type(0) : size_type(1);
2408 }
2409
2420 template <typename K, typename pointer_type, typename comparator>
2421 persistent_node_ptr
2422 internal_find_position(size_type level, pointer_type &prev,
2423 const K &key, const comparator &cmp) const
2424 {
2425 assert(level < prev->height());
2426 persistent_node_ptr next = prev->next(level);
2427 pointer_type curr = next.get();
2428
2429 while (curr && cmp(get_key(curr), key)) {
2430 prev = curr;
2431 assert(level < prev->height());
2432 next = prev->next(level);
2433 curr = next.get();
2434 }
2435
2436 return next;
2437 }
2438
2449 template <typename K>
2450 void
2451 find_insert_pos(prev_array_type &prev_nodes,
2452 next_array_type &next_nodes, const K &key)
2453 {
2454 if (allow_multimapping) {
2455 fill_prev_next_arrays(prev_nodes, next_nodes, key,
2456 not_greater_compare(_compare));
2457 } else {
2458 fill_prev_next_arrays(prev_nodes, next_nodes, key,
2459 _compare);
2460 }
2461 }
2462
2474 template <typename K, typename comparator>
2475 void
2476 fill_prev_next_arrays(prev_array_type &prev_nodes,
2477 next_array_type &next_nodes, const K &key,
2478 const comparator &cmp)
2479 {
2480 node_ptr prev = dummy_head.get();
2481 prev_nodes.fill(prev);
2482 next_nodes.fill(nullptr);
2483
2484 for (size_type h = prev->height(); h > 0; --h) {
2485 persistent_node_ptr next =
2486 internal_find_position(h - 1, prev, key, cmp);
2487 prev_nodes[h - 1] = prev;
2488 next_nodes[h - 1] = next;
2489 }
2490 }
2491
2492 template <typename K, typename... Args>
2493 std::pair<iterator, bool>
2494 internal_try_emplace(K &&key, Args &&... args)
2495 {
2496 return internal_insert(
2497 key, std::piecewise_construct,
2498 std::forward_as_tuple(std::forward<K>(key)),
2499 std::forward_as_tuple(std::forward<Args>(args)...));
2500 }
2501
2502 template <typename... Args>
2503 std::pair<iterator, bool>
2504 internal_emplace(Args &&... args)
2505 {
2506 check_outside_tx();
2507 tls_entry_type &tls_entry = tls_data.local();
2509
2511 assert(tls_entry.ptr == nullptr);
2512 tls_entry.ptr =
2513 create_node(std::forward<Args>(args)...);
2514 ++tls_entry.size_diff;
2515 tls_entry.insert_stage = not_started;
2516 });
2517
2518 node_ptr n = tls_entry.ptr.get();
2519 size_type height = n->height();
2520
2521 std::pair<iterator, bool> insert_result = internal_insert_node(
2522 get_key(n), height,
2523 [&](const next_array_type &next_nodes)
2524 -> persistent_node_ptr & {
2525 assert(tls_entry.insert_stage == not_started);
2526 assert(tls_entry.ptr != nullptr);
2527
2528 n->set_nexts(pop, next_nodes.data(), height);
2529
2530 tls_entry.insert_stage = in_progress;
2531 pop.persist(&(tls_entry.insert_stage),
2532 sizeof(tls_entry.insert_stage));
2533
2534 return tls_entry.ptr;
2535 });
2536
2537 if (!insert_result.second) {
2538 assert(tls_entry.ptr != nullptr);
2539 assert(tls_entry.insert_stage == not_started);
2540
2542 --tls_entry.size_diff;
2543 delete_node(tls_entry.ptr);
2544 tls_entry.ptr = nullptr;
2545 });
2546 }
2547
2548 assert(tls_entry.ptr == nullptr);
2549 return insert_result;
2550 }
2551
2556 template <typename... Args>
2557 std::pair<iterator, bool>
2559 {
2561
2562 persistent_node_ptr new_node =
2563 create_node(std::forward<Args>(args)...);
2564
2565 node_ptr n = new_node.get();
2566 size_type height = n->height();
2567
2568 std::pair<iterator, bool> insert_result = internal_insert_node(
2569 get_key(n), height,
2570 [&](const next_array_type &next_nodes)
2571 -> persistent_node_ptr & {
2572 assert(new_node != nullptr);
2573
2574 n->set_nexts(next_nodes.data(), height);
2575
2576 return new_node;
2577 });
2578
2579 if (insert_result.second) {
2580 ++on_init_size;
2581 } else {
2582 assert(new_node != nullptr);
2583
2584 delete_node(new_node);
2585 }
2586
2587 return insert_result;
2588 }
2589
2593 template <typename K, typename... Args>
2594 std::pair<iterator, bool>
2595 internal_insert(const K &key, Args &&... args)
2596 {
2597 check_outside_tx();
2598 tls_entry_type &tls_entry = tls_data.local();
2599 assert(tls_entry.ptr == nullptr);
2600
2601 size_type height = random_level();
2602
2603 std::pair<iterator, bool> insert_result = internal_insert_node(
2604 key, height,
2605 [&](const next_array_type &next_nodes)
2606 -> persistent_node_ptr & {
2608
2610 tls_entry.ptr = create_node(
2611 std::forward_as_tuple(
2612 height, next_nodes.data()),
2613 std::forward_as_tuple(
2614 std::forward<Args>(args)...));
2615
2616 ++(tls_entry.size_diff);
2617 tls_entry.insert_stage = in_progress;
2619
2620 assert(tls_entry.ptr != nullptr);
2621 return tls_entry.ptr;
2622 });
2623
2624 assert(tls_entry.ptr == nullptr);
2625
2626 return insert_result;
2627 }
2628
2632 template <typename K, typename PrepareNode>
2633 std::pair<iterator, bool>
2634 internal_insert_node(const K &key, size_type height,
2635 PrepareNode &&prepare_new_node)
2636 {
2637 prev_array_type prev_nodes;
2638 next_array_type next_nodes;
2639 node_ptr n = nullptr;
2640
2641 do {
2642 find_insert_pos(prev_nodes, next_nodes, key);
2643
2644 node_ptr next = next_nodes[0].get();
2645 if (next && !allow_multimapping &&
2646 !_compare(key, get_key(next))) {
2647
2648 return std::pair<iterator, bool>(iterator(next),
2649 false);
2650 }
2651
2652 } while ((n = try_insert_node(prev_nodes, next_nodes, height,
2653 std::forward<PrepareNode>(
2654 prepare_new_node))) ==
2655 nullptr);
2656
2657 assert(n);
2658 return std::pair<iterator, bool>(iterator(n), true);
2659 }
2660
2666 template <typename PrepareNode>
2667 node_ptr
2668 try_insert_node(prev_array_type &prev_nodes,
2669 const next_array_type &next_nodes, size_type height,
2670 PrepareNode &&prepare_new_node)
2671 {
2672 assert(dummy_head->height() >= height);
2673
2674 lock_array locks;
2675 if (!try_lock_nodes(height, prev_nodes, next_nodes, locks)) {
2676 return nullptr;
2677 }
2678
2679 node_lock_type new_node_lock;
2680
2681 persistent_node_ptr &new_node = prepare_new_node(next_nodes);
2682 assert(new_node != nullptr);
2683 node_ptr n = new_node.get();
2684
2685 /*
2686 * We need to hold lock to the new node until changes
2687 * are committed to persistent domain. Otherwise, the
2688 * new node would be visible to concurrent inserts
2689 * before it is persisted.
2690 */
2691 new_node_lock = n->acquire();
2692
2694 /*
2695 * In the loop below we are linking a new node to all layers of
2696 * the skip list. Transaction is not required because in case of
2697 * failure the node is reachable via a pointer from persistent
2698 * TLS. During recovery, we will complete the insert. It is also
2699 * OK if concurrent readers will see not a fully-linked node
2700 * because during recovery the insert procedure will be
2701 * completed.
2702 */
2703 for (size_type level = 0; level < height; ++level) {
2704 assert(prev_nodes[level]->height() > level);
2705 assert(prev_nodes[level]->next(level) ==
2706 next_nodes[level]);
2707 assert(prev_nodes[level]->next(level) ==
2708 n->next(level));
2709 prev_nodes[level]->set_next(pop, level, new_node);
2710 }
2711
2712#ifndef NDEBUG
2713 try_insert_node_finish_marker();
2714#endif
2715
2716 new_node = nullptr;
2717 /* We need to persist the node pointer. Otherwise, on a restart,
2718 * this pointer might be not null but the node can be already
2719 * deleted. */
2720 pop.persist(&new_node, sizeof(new_node));
2721
2722 ++_size;
2723#if LIBPMEMOBJ_CPP_VG_PMEMCHECK_ENABLED
2724 VALGRIND_PMC_DO_FLUSH(&_size, sizeof(_size));
2725#endif
2726
2727 assert(n);
2728 return n;
2729 }
2730
2735 bool
2736 check_prev_array(const prev_array_type &prevs, size_type height)
2737 {
2738 for (size_type l = 1; l < height; ++l) {
2739 if (prevs[l] == dummy_head.get()) {
2740 continue;
2741 }
2742
2743 assert(prevs[l - 1] != dummy_head.get());
2744 assert(!_compare(get_key(prevs[l - 1]),
2745 get_key(prevs[l])));
2746 }
2747
2748 return true;
2749 }
2750
2751 bool
2752 try_lock_nodes(size_type height, prev_array_type &prevs,
2753 const next_array_type &nexts, lock_array &locks)
2754 {
2755 assert(check_prev_array(prevs, height));
2756
2757 for (size_type l = 0; l < height; ++l) {
2758 if (l == 0 || prevs[l] != prevs[l - 1]) {
2759 locks[l] = prevs[l]->acquire();
2760 }
2761
2762 persistent_node_ptr next = prevs[l]->next(l);
2763 if (next != nexts[l])
2764 /* Other thread inserted to this position and
2765 * modified the pointer before we acquired the
2766 * lock */
2767 return false;
2768 }
2769
2770 return true;
2771 }
2772
2784 template <typename K, typename comparator>
2785 const_iterator
2786 internal_get_bound(const K &key, const comparator &cmp) const
2787 {
2788 const_node_ptr prev = dummy_head.get();
2789 assert(prev->height() > 0);
2790 persistent_node_ptr next = nullptr;
2791
2792 for (size_type h = prev->height(); h > 0; --h) {
2793 next = internal_find_position(h - 1, prev, key, cmp);
2794 }
2795
2796 return const_iterator(next.get());
2797 }
2798
2810 template <typename K, typename comparator>
2811 iterator
2812 internal_get_bound(const K &key, const comparator &cmp)
2813 {
2814 node_ptr prev = dummy_head.get();
2815 assert(prev->height() > 0);
2816 persistent_node_ptr next = nullptr;
2817
2818 for (size_type h = prev->height(); h > 0; --h) {
2819 next = internal_find_position(h - 1, prev, key, cmp);
2820 }
2821
2822 return iterator(next.get());
2823 }
2824
2836 template <typename K, typename comparator>
2837 const_iterator
2839 const comparator &cmp) const
2840 {
2841 const_node_ptr prev = dummy_head.get();
2842 assert(prev->height() > 0);
2843
2844 for (size_type h = prev->height(); h > 0; --h) {
2845 internal_find_position(h - 1, prev, key, cmp);
2846 }
2847
2848 if (prev == dummy_head.get())
2849 return end();
2850
2851 return const_iterator(prev);
2852 }
2853
2854 iterator
2855 internal_erase(const_iterator pos, obj::p<difference_type> &size_diff)
2856 {
2857 assert(pos != end());
2858
2860
2861 std::pair<persistent_node_ptr, persistent_node_ptr>
2862 extract_result(nullptr, nullptr);
2863
2865 extract_result = internal_extract(pos);
2866
2867 /* Make sure that node was extracted */
2868 assert(extract_result.first != nullptr);
2869 delete_node(extract_result.first);
2870 --size_diff;
2871 obj::flat_transaction::snapshot((size_type *)&_size);
2872 --_size;
2873 });
2874
2875 return iterator(extract_result.second.get());
2876 }
2877
2881 std::pair<persistent_node_ptr, persistent_node_ptr>
2882 internal_extract(const_iterator it)
2883 {
2884 assert(dummy_head->height() > 0);
2885 assert(it != end());
2886 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2887
2888 const key_type &key = traits_type::get_key(*it);
2889
2890 prev_array_type prev_nodes;
2891 next_array_type next_nodes;
2892
2893 fill_prev_next_arrays(prev_nodes, next_nodes, key, _compare);
2894
2895 node_ptr erase_node = next_nodes[0].get();
2896 assert(erase_node != nullptr);
2897
2898 if (!_compare(key, get_key(erase_node))) {
2899 /* XXX: this assertion will fail in case of multimap
2900 * because we take the first node with the same key.
2901 * Need to extend algorithm for mutimap. */
2902 assert(erase_node == it.node);
2903 return internal_extract_node(prev_nodes, next_nodes,
2904 erase_node);
2905 }
2906
2907 return std::pair<persistent_node_ptr, persistent_node_ptr>(
2908 nullptr, nullptr);
2909 }
2910
2911 std::pair<persistent_node_ptr, persistent_node_ptr>
2912 internal_extract_node(const prev_array_type &prev_nodes,
2913 const next_array_type &next_nodes,
2914 node_ptr erase_node)
2915 {
2916 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2917 assert(erase_node != nullptr);
2918 for (size_type level = 0; level < erase_node->height();
2919 ++level) {
2920 assert(prev_nodes[level]->height() > level);
2921 assert(next_nodes[level].get() == erase_node);
2922 prev_nodes[level]->set_next_tx(level,
2923 erase_node->next(level));
2924 }
2925
2926 return std::pair<persistent_node_ptr, persistent_node_ptr>(
2927 next_nodes[0], erase_node->next(0));
2928 }
2929
2934 obj::pool_base
2936 {
2937 PMEMobjpool *pop = pmemobj_pool_by_ptr(this);
2938 return obj::pool_base(pop);
2939 }
2940
2941 void
2942 internal_copy(const concurrent_skip_list &other)
2943 {
2944 internal_copy(other.begin(), other.end());
2945 }
2946
2947 template <typename Iterator>
2948 void
2949 internal_copy(Iterator first, Iterator last)
2950 {
2951 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2952
2953 prev_array_type prev_nodes;
2954 prev_nodes.fill(dummy_head.get());
2955 size_type sz = 0;
2956
2957 for (; first != last; ++first, ++sz) {
2958 persistent_node_ptr new_node = create_node(*first);
2959 node_ptr n = new_node.get();
2960 for (size_type level = 0; level < n->height();
2961 ++level) {
2962 prev_nodes[level]->set_next_tx(level, new_node);
2963 prev_nodes[level] = n;
2964 }
2965 }
2966
2967 on_init_size = sz;
2968 /*
2969 * As internal_swap can only be called from one thread, and
2970 * there can be an outer transaction we must make sure that size
2971 * change is transactional
2972 */
2973 obj::flat_transaction::snapshot((size_type *)&_size);
2974 _size = sz;
2975 assert(std::is_sorted(
2976 this->begin(), this->end(),
2977 [&](const value_type &lhs, const value_type &rhs) {
2978 return lhs.first < rhs.first;
2979 }));
2980 }
2981
2983 size_type
2985 {
2986 return _rnd_generator();
2987 }
2988
2989 static size_type
2990 calc_node_size(size_type height)
2991 {
2992 return sizeof(list_node_type) +
2993 height * sizeof(typename list_node_type::node_pointer);
2994 }
2995
2997 template <typename... Args>
2998 persistent_node_ptr
2999 create_node(Args &&... args)
3000 {
3001 size_type levels = random_level();
3002
3003 return create_node(
3004 std::forward_as_tuple(levels),
3005 std::forward_as_tuple(std::forward<Args>(args)...));
3006 }
3007
3008 template <typename... NodeArgs, typename... ValueArgs>
3009 persistent_node_ptr
3010 create_node(std::tuple<NodeArgs...> &&node_args,
3011 std::tuple<ValueArgs...> &&value_args)
3012 {
3013 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
3014
3015 persistent_node_ptr node = creates_dummy_node(
3016 std::forward<std::tuple<NodeArgs...>>(node_args),
3017 index_sequence_for<NodeArgs...>{});
3018
3019 construct_value_type(
3020 node,
3021 std::forward<std::tuple<ValueArgs...>>(value_args),
3022 index_sequence_for<ValueArgs...>{});
3023
3024 return node;
3025 }
3026
3027 template <typename Tuple, size_t... I>
3028 void
3029 construct_value_type(persistent_node_ptr node, Tuple &&args,
3030 index_sequence<I...>)
3031 {
3032 node_ptr new_node = node.get();
3033
3034 node_allocator_traits::construct(
3035 _node_allocator, new_node->get(),
3036 std::get<I>(std::forward<Tuple>(args))...);
3037 }
3038
3044 void
3046 {
3047 dummy_head = creates_dummy_node(MAX_LEVEL);
3048 }
3049
3050 template <typename Tuple, size_t... I>
3051 persistent_node_ptr
3052 creates_dummy_node(Tuple &&args, index_sequence<I...>)
3053 {
3054 return creates_dummy_node(
3055 std::get<I>(std::forward<Tuple>(args))...);
3056 }
3057
3067 template <typename... Args>
3068 persistent_node_ptr
3069 creates_dummy_node(size_type height, Args &&... args)
3070 {
3071 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
3072 size_type sz = calc_node_size(height);
3073
3075 node_allocator_traits::allocate(_node_allocator, sz)
3076 .raw();
3077
3078 assert(n != nullptr);
3079
3080 node_allocator_traits::construct(_node_allocator, n.get(),
3081 height,
3082 std::forward<Args>(args)...);
3083
3084 return n;
3085 }
3086
3087 template <bool is_dummy = false>
3088 void
3089 delete_node(persistent_node_ptr &node)
3090 {
3091 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
3092 node_ptr n = node.get();
3093 size_type sz = calc_node_size(n->height());
3094
3095 /* Destroy value */
3096 if (!is_dummy)
3097 node_allocator_traits::destroy(_node_allocator,
3098 n->get());
3099 /* Destroy node */
3100 node_allocator_traits::destroy(_node_allocator, n);
3101 /* Deallocate memory */
3102 deallocate_node(node, sz);
3103 node = nullptr;
3104 }
3105
3106 void
3107 deallocate_node(persistent_node_ptr &node, size_type sz)
3108 {
3109 /*
3110 * Each node object has different size which depends on number
3111 * of layers the node is linked. Therefore, allocate/deallocate
3112 * just a raw byte array. persistent_ptr<uint8_t> is used as a
3113 * pointer to raw array of bytes.
3114 */
3116 node.to_persistent_ptr().raw();
3117 node_allocator_traits::deallocate(_node_allocator, tmp, sz);
3118 }
3119
3120 void
3121 delete_dummy_head()
3122 {
3123 assert(dummy_head != nullptr);
3124 delete_node<true>(dummy_head);
3125 assert(dummy_head == nullptr);
3126 }
3127
3128 iterator
3129 get_iterator(const_iterator it)
3130 {
3131 return iterator(
3132 const_cast<typename iterator::node_ptr>(it.node));
3133 }
3134
3136 void
3138 {
3139 int64_t last_run_size = 0;
3141
3142 for (auto &tls_entry : tls_data) {
3143 persistent_node_ptr &node = tls_entry.ptr;
3144 auto &size_diff = tls_entry.size_diff;
3145 if (node) {
3146 /*
3147 * We are completing inserts which were in
3148 * progress before the crash because readers
3149 * might saw incompleted inserts before the
3150 * crash. We set the in_progress flag inside
3151 * try_insert_node function when we locked the
3152 * predecessors for the new node, therefore,
3153 * only single node with the same key might have
3154 * the in_progress status.
3155 */
3156 if (tls_entry.insert_stage == in_progress) {
3157 complete_insert(tls_entry);
3158 } else {
3160 --(tls_entry.size_diff);
3161 delete_node(node);
3162 node = nullptr;
3163 });
3164 }
3165 }
3166
3167 assert(node == nullptr);
3168
3169 last_run_size += size_diff;
3170 }
3171
3172 /* Make sure that on_init_size + last_run_size >= 0 */
3173 assert(last_run_size >= 0 ||
3174 on_init_size >
3175 static_cast<size_type>(std::abs(last_run_size)));
3177 tls_data.clear();
3178 on_init_size += static_cast<size_t>(last_run_size);
3179 });
3180 _size = on_init_size;
3181#if LIBPMEMOBJ_CPP_VG_PMEMCHECK_ENABLED
3182 VALGRIND_PMC_DO_FLUSH(&_size, sizeof(_size));
3183#endif
3184 }
3185
3186 void
3187 complete_insert(tls_entry_type &tls_entry)
3188 {
3189 persistent_node_ptr &node = tls_entry.ptr;
3190 assert(node != nullptr);
3191 assert(tls_entry.insert_stage == in_progress);
3192 prev_array_type prev_nodes;
3193 next_array_type next_nodes;
3194 node_ptr n = node.get();
3195 const key_type &key = get_key(n);
3196 size_type height = n->height();
3197
3198 fill_prev_next_arrays(prev_nodes, next_nodes, key, _compare);
3200
3201 /* Node was partially linked */
3202 for (size_type level = 0; level < height; ++level) {
3203 assert(prev_nodes[level]->height() > level);
3204 assert(prev_nodes[level]->next(level) ==
3205 next_nodes[level]);
3206
3207 if (prev_nodes[level]->next(level) != node) {
3208 /* Otherwise, node already linked on
3209 * this layer */
3210 assert(n->next(level) == next_nodes[level]);
3211 prev_nodes[level]->set_next(pop, level, node);
3212 }
3213 }
3214
3215 node = nullptr;
3216 pop.persist(&node, sizeof(node));
3217 }
3218
3219 struct not_greater_compare {
3220 const key_compare &my_less_compare;
3221
3222 not_greater_compare(const key_compare &less_compare)
3223 : my_less_compare(less_compare)
3224 {
3225 }
3226
3227 template <typename K1, typename K2>
3228 bool
3229 operator()(const K1 &first, const K2 &second) const
3230 {
3231 return !my_less_compare(second, first);
3232 }
3233 };
3234
3235 const uint64_t pool_uuid = pmemobj_oid(this).pool_uuid_lo;
3236 node_allocator_type _node_allocator;
3237 key_compare _compare;
3238 random_level_generator_type _rnd_generator;
3239 persistent_node_ptr dummy_head;
3240
3241 enumerable_thread_specific<tls_entry_type> tls_data;
3242
3243 std::atomic<size_type> _size;
3244
3251}; /* class concurrent_skip_list */
3252
3253template <typename Key, typename Value, typename KeyCompare,
3254 typename RND_GENERATOR, typename Allocator, bool AllowMultimapping,
3255 size_t MAX_LEVEL>
3256class map_traits {
3257public:
3258 static constexpr size_t max_level = MAX_LEVEL;
3259 using random_generator_type = RND_GENERATOR;
3260 using key_type = Key;
3261 using mapped_type = Value;
3262 using compare_type = KeyCompare;
3263 using value_type = pair<const key_type, mapped_type>;
3264 using reference = value_type &;
3265 using const_reference = const value_type &;
3266 using allocator_type = Allocator;
3267
3274 constexpr static bool allow_multimapping = AllowMultimapping;
3275
3276 static const key_type &
3277 get_key(const_reference val)
3278 {
3279 return val.first;
3280 }
3281}; /* class map_traits */
3282
3283} /* namespace detail */
3284} /* namespace pmem */
3285
3286#endif /* PMEMOBJ_CONCURRENT_SKIP_LIST_IMPL_HPP */
Persistent memory aware implementation of the concurrent skip list.
Definition: concurrent_skip_list_impl.hpp:479
const_iterator internal_get_biggest_less_than(const K &key, const comparator &cmp) const
Returns an iterator pointing to the last element from the list for which cmp(element,...
Definition: concurrent_skip_list_impl.hpp:2838
bool contains(const key_type &key) const
Checks if there is an element with key equivalent to key in the container.
Definition: concurrent_skip_list_impl.hpp:1942
const_iterator internal_get_bound(const K &key, const comparator &cmp) const
Returns an iterator pointing to the first element from the list for which cmp(element,...
Definition: concurrent_skip_list_impl.hpp:2786
iterator internal_get_bound(const K &key, const comparator &cmp)
Returns an iterator pointing to the first element from the list for which cmp(element,...
Definition: concurrent_skip_list_impl.hpp:2812
key_compare & key_comp()
Returns a reference to the object that compares the keys.
Definition: concurrent_skip_list_impl.hpp:2283
persistent_node_ptr create_node(Args &&... args)
Creates new node.
Definition: concurrent_skip_list_impl.hpp:2999
iterator find_higher_eq(const K &x)
Returns an iterator pointing to the first element that compares not less (i.e.
Definition: concurrent_skip_list_impl.hpp:1483
void check_tx_stage_work() const
Private helper function.
Definition: concurrent_skip_list_impl.hpp:2315
std::pair< iterator, bool > internal_insert(const K &key, Args &&... args)
Construct and insert new node to the skip list in a thread-safe way.
Definition: concurrent_skip_list_impl.hpp:2595
const_iterator lower_bound(const key_type &key) const
Returns an iterator pointing to the first element that is not less than (i.e.
Definition: concurrent_skip_list_impl.hpp:1384
iterator find_higher(const key_type &key)
Returns an iterator pointing to the first element that is greater than key.
Definition: concurrent_skip_list_impl.hpp:1598
const_iterator find_lower_eq(const K &key) const
Returns a const iterator pointing to the biggest element that is less than or equal to key.
Definition: concurrent_skip_list_impl.hpp:1821
concurrent_skip_list & operator=(std::initializer_list< value_type > il)
Replaces the contents with those identified by initializer list il.
Definition: concurrent_skip_list_impl.hpp:878
concurrent_skip_list(const concurrent_skip_list &other, const allocator_type &alloc)
Copy constructor.
Definition: concurrent_skip_list_impl.hpp:646
iterator find_higher_eq(const key_type &key)
Returns an iterator pointing to the first element that is not less than (i.e.
Definition: concurrent_skip_list_impl.hpp:1444
void swap(concurrent_skip_list &other)
XXX: Implement get_allocator() interface.
Definition: concurrent_skip_list_impl.hpp:2129
const_iterator find_lower(const K &key) const
Returns a const iterator pointing to the biggest element that is less than key.
Definition: concurrent_skip_list_impl.hpp:1738
const_iterator find(const K &x) const
Finds an element with key that compares equivalent to the value x.
Definition: concurrent_skip_list_impl.hpp:1892
~concurrent_skip_list()
Destructor.
Definition: concurrent_skip_list_impl.hpp:771
const_iterator cend() const
Returns an iterator to the element following the last element of the map.
Definition: concurrent_skip_list_impl.hpp:2074
std::pair< iterator, bool > insert(const value_type &value)
Inserts value in a thread-safe way.
Definition: concurrent_skip_list_impl.hpp:906
concurrent_skip_list()
Default constructor.
Definition: concurrent_skip_list_impl.hpp:531
iterator upper_bound(const key_type &key)
Returns an iterator pointing to the first element that is greater than key.
Definition: concurrent_skip_list_impl.hpp:1522
const_iterator cbegin() const
Returns an iterator to the first element of the container.
Definition: concurrent_skip_list_impl.hpp:2035
iterator lower_bound(const key_type &key)
Returns an iterator pointing to the first element that is not less than (i.e.
Definition: concurrent_skip_list_impl.hpp:1368
const_iterator begin() const
Returns an iterator to the first element of the container.
Definition: concurrent_skip_list_impl.hpp:2023
bool check_prev_array(const prev_array_type &prevs, size_type height)
Used only inside asserts.
Definition: concurrent_skip_list_impl.hpp:2736
iterator begin()
Returns an iterator to the first element of the container.
Definition: concurrent_skip_list_impl.hpp:2011
concurrent_skip_list(concurrent_skip_list &&other)
Move constructor.
Definition: concurrent_skip_list_impl.hpp:676
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
Returns a range containing all elements with the given key in the container.
Definition: concurrent_skip_list_impl.hpp:2196
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
Returns a range containing all elements with the given key in the container.
Definition: concurrent_skip_list_impl.hpp:2260
std::pair< iterator, bool > insert(value_type &&value)
Inserts value using move semantic.
Definition: concurrent_skip_list_impl.hpp:955
iterator find_lower_eq(const K &key)
Returns an iterator pointing to the biggest element that is less than or equal to key.
Definition: concurrent_skip_list_impl.hpp:1796
size_type max_size() const
Returns the maximum number of elements the container is able to hold due to system or library impleme...
Definition: concurrent_skip_list_impl.hpp:2099
iterator find_lower(const key_type &key)
Returns an iterator pointing to the biggest element that is less than key.
Definition: concurrent_skip_list_impl.hpp:1674
std::pair< iterator, bool > try_emplace(key_type &&k, Args &&... args)
If a key equivalent to k already exists in the container, does nothing.
Definition: concurrent_skip_list_impl.hpp:1181
const_iterator find_lower(const key_type &key) const
Returns a const iterator pointing to the biggest element that is less than key.
Definition: concurrent_skip_list_impl.hpp:1692
void tls_restore()
Process any information which was saved to tls and clears tls.
Definition: concurrent_skip_list_impl.hpp:3137
iterator insert(const_iterator hint, const_reference value)
Inserts value in the position as close as possible, just prior to hint.
Definition: concurrent_skip_list_impl.hpp:978
const key_compare & key_comp() const
Returns a const reference to the object that compares the keys.
Definition: concurrent_skip_list_impl.hpp:2272
concurrent_skip_list(const key_compare &comp, const allocator_type &alloc=allocator_type())
Constructs an empty container.
Definition: concurrent_skip_list_impl.hpp:553
const_iterator find_higher_eq(const key_type &key) const
Returns an iterator pointing to the first element that is not less than (i.e.
Definition: concurrent_skip_list_impl.hpp:1460
const_iterator find_higher(const key_type &key) const
Returns an iterator pointing to the first element that is greater than key.
Definition: concurrent_skip_list_impl.hpp:1614
std::pair< iterator, bool > insert(P &&value)
Inserts value.
Definition: concurrent_skip_list_impl.hpp:933
iterator insert(const_iterator hint, P &&value)
Inserts value in the position as close as possible, just prior to hint.
Definition: concurrent_skip_list_impl.hpp:1008
size_type count(const K &key) const
Returns the number of elements with key that compares equivalent to the specified argument.
Definition: concurrent_skip_list_impl.hpp:1928
size_type unsafe_erase(const K &key)
Removes the element (if one exists) with the key equivalent to key.
Definition: concurrent_skip_list_impl.hpp:1348
concurrent_skip_list(const concurrent_skip_list &other)
Copy constructor.
Definition: concurrent_skip_list_impl.hpp:614
std::pair< iterator, bool > emplace(Args &&... args)
Inserts a new element into the container constructed in-place with the given args if there is no elem...
Definition: concurrent_skip_list_impl.hpp:1083
void create_dummy_head()
Creates dummy head.
Definition: concurrent_skip_list_impl.hpp:3045
bool contains(const K &x) const
Checks if there is an element with key that compares equivalent to the value x.
Definition: concurrent_skip_list_impl.hpp:1963
iterator end()
Returns an iterator to the element following the last element of the map.
Definition: concurrent_skip_list_impl.hpp:2048
iterator find(const key_type &key)
Finds an element with key equivalent to key.
Definition: concurrent_skip_list_impl.hpp:1836
const_iterator find(const key_type &key) const
Finds an element with key equivalent to key.
Definition: concurrent_skip_list_impl.hpp:1850
iterator lower_bound(const K &x)
Returns an iterator pointing to the first element that compares not less (i.e.
Definition: concurrent_skip_list_impl.hpp:1406
concurrent_skip_list(InputIt first, InputIt last, const key_compare &comp=key_compare(), const allocator_type &alloc=allocator_type())
Constructs the container with the contents of the range [first, last).
Definition: concurrent_skip_list_impl.hpp:586
std::pair< persistent_node_ptr, persistent_node_ptr > internal_extract(const_iterator it)
Definition: concurrent_skip_list_impl.hpp:2882
iterator unsafe_erase(const_iterator pos)
Removes the element at pos from the container.
Definition: concurrent_skip_list_impl.hpp:1265
iterator find(const K &x)
Finds an element with key that compares equivalent to the value x.
Definition: concurrent_skip_list_impl.hpp:1871
obj::p< size_type > on_init_size
This variable holds real size after the skip list is initialized.
Definition: concurrent_skip_list_impl.hpp:3250
const_iterator end() const
Returns an iterator to the element following the last element of the map.
Definition: concurrent_skip_list_impl.hpp:2061
obj::pool_base get_pool_base() const
Get the persistent memory pool where hashmap resides.
Definition: concurrent_skip_list_impl.hpp:2935
std::pair< iterator, bool > internal_insert_node(const K &key, size_type height, PrepareNode &&prepare_new_node)
Try to insert new node to the skip list in a thread-safe way.
Definition: concurrent_skip_list_impl.hpp:2634
void clear()
Erases all elements from the container transactionally.
Definition: concurrent_skip_list_impl.hpp:1977
concurrent_skip_list(concurrent_skip_list &&other, const allocator_type &alloc)
Move constructor.
Definition: concurrent_skip_list_impl.hpp:705
const_iterator find_lower_eq(const key_type &key) const
Returns a const iterator pointing to the biggest element that is less than or equal to key.
Definition: concurrent_skip_list_impl.hpp:1773
const_iterator find_higher_eq(const K &x) const
Returns an iterator pointing to the first element that compares not less (i.e.
Definition: concurrent_skip_list_impl.hpp:1506
size_type unsafe_erase(const key_type &key)
Removes the element (if one exists) with the key equivalent to key.
Definition: concurrent_skip_list_impl.hpp:1313
iterator emplace_hint(const_iterator hint, Args &&... args)
Inserts a new element to the container as close as possible to the position just before hint.
Definition: concurrent_skip_list_impl.hpp:1120
void insert(InputIterator first, InputIterator last)
Inserts elements from range [first, last).
Definition: concurrent_skip_list_impl.hpp:1029
std::pair< iterator, iterator > equal_range(const K &x)
Returns a range containing all elements with the given key in the container.
Definition: concurrent_skip_list_impl.hpp:2228
iterator upper_bound(const K &x)
Returns an iterator pointing to the first element that compares greater to the value x.
Definition: concurrent_skip_list_impl.hpp:1560
std::pair< iterator, bool > internal_unsafe_emplace(Args &&... args)
Not thread-safe but can be called within a transaction.
Definition: concurrent_skip_list_impl.hpp:2558
iterator find_lower_eq(const key_type &key)
Returns an iterator pointing to the biggest element that is less than or equal to key.
Definition: concurrent_skip_list_impl.hpp:1754
void runtime_initialize()
Initialize concurrent_skip_list after process restart.
Definition: concurrent_skip_list_impl.hpp:729
persistent_node_ptr creates_dummy_node(size_type height, Args &&... args)
Creates new node, value_type should be constructed separately.
Definition: concurrent_skip_list_impl.hpp:3069
size_type count(const key_type &key) const
Returns the number of elements with key that compares equivalent to the specified argument.
Definition: concurrent_skip_list_impl.hpp:1907
size_type random_level()
Generate random level.
Definition: concurrent_skip_list_impl.hpp:2984
const_iterator lower_bound(const K &x) const
Returns an iterator pointing to the first element that compares not less (i.e.
Definition: concurrent_skip_list_impl.hpp:1428
iterator unsafe_erase(iterator pos)
Removes the element at pos from the container.
Definition: concurrent_skip_list_impl.hpp:1241
void free_data()
Should be called before concurrent_skip_list destructor is called.
Definition: concurrent_skip_list_impl.hpp:750
concurrent_skip_list & operator=(concurrent_skip_list &&other)
Move assignment operator.
Definition: concurrent_skip_list_impl.hpp:838
persistent_node_ptr internal_find_position(size_type level, pointer_type &prev, const K &key, const comparator &cmp) const
Finds position on the.
Definition: concurrent_skip_list_impl.hpp:2422
std::enable_if< has_is_transparent< key_compare >::value &&std::is_constructible< key_type, K && >::value, std::pair< iterator, bool > >::type try_emplace(K &&k, Args &&... args)
If a key equivalent to k already exists in the container, does nothing.
Definition: concurrent_skip_list_impl.hpp:1218
node_ptr try_insert_node(prev_array_type &prev_nodes, const next_array_type &next_nodes, size_type height, PrepareNode &&prepare_new_node)
Try to insert new node to the skip list.
Definition: concurrent_skip_list_impl.hpp:2668
const_iterator upper_bound(const K &x) const
Returns an iterator pointing to the first element that compares greater to the value x.
Definition: concurrent_skip_list_impl.hpp:1582
void fill_prev_next_arrays(prev_array_type &prev_nodes, next_array_type &next_nodes, const K &key, const comparator &cmp)
The method finds successor and predecessor nodes on each level of the skip list for the given.
Definition: concurrent_skip_list_impl.hpp:2476
const_iterator find_higher(const K &x) const
Returns an iterator pointing to the first element that compares greater to the value x.
Definition: concurrent_skip_list_impl.hpp:1658
std::pair< iterator, iterator > equal_range(const key_type &key)
Returns a range containing all elements with the given key in the container.
Definition: concurrent_skip_list_impl.hpp:2170
bool empty() const
Checks if the container has no elements, i.e.
Definition: concurrent_skip_list_impl.hpp:2111
size_type size() const
Returns the number of elements in the container, i.e.
Definition: concurrent_skip_list_impl.hpp:2086
const_iterator upper_bound(const key_type &key) const
Returns an iterator pointing to the first element that is greater than key.
Definition: concurrent_skip_list_impl.hpp:1538
iterator find_lower(const K &key)
Returns an iterator pointing to the biggest element that is less than key.
Definition: concurrent_skip_list_impl.hpp:1714
std::pair< iterator, bool > try_emplace(const key_type &k, Args &&... args)
If a key equivalent to k already exists in the container, does nothing.
Definition: concurrent_skip_list_impl.hpp:1151
iterator find_higher(const K &x)
Returns an iterator pointing to the first element that compares greater to the value x.
Definition: concurrent_skip_list_impl.hpp:1636
void insert(std::initializer_list< value_type > ilist)
Inserts elements from initializer list ilist.
Definition: concurrent_skip_list_impl.hpp:1049
iterator unsafe_erase(const_iterator first, const_iterator last)
Removes the elements in the range [first; last), which must be a valid range in *this.
Definition: concurrent_skip_list_impl.hpp:1285
void find_insert_pos(prev_array_type &prev_nodes, next_array_type &next_nodes, const K &key)
The method finds insert position for the given.
Definition: concurrent_skip_list_impl.hpp:2451
concurrent_skip_list & operator=(const concurrent_skip_list &other)
Copy assignment operator.
Definition: concurrent_skip_list_impl.hpp:796
static void commit()
Manually commit a transaction.
Definition: transaction.hpp:325
static void snapshot(const T *addr, size_t num=1)
Takes a “snapshot” of given elements of type T number (1 by default), located at the given address pt...
Definition: transaction.hpp:428
Persistent self-relative pointer class.
Definition: self_relative_ptr.hpp:81
element_type * get() const noexcept
Get the direct pointer.
Definition: self_relative_ptr.hpp:196
typename detail::transaction_base< true >::manual manual
C++ manual scope transaction class.
Definition: transaction.hpp:762
static void run(obj::pool_base &pool, std::function< void()> tx, Locks &... locks)
Execute a closure-like transaction and lock locks.
Definition: transaction.hpp:823
Persistent memory resident mutex implementation.
Definition: mutex.hpp:31
Resides on pmem class.
Definition: p.hpp:35
const PMEMoid & raw() const noexcept
Get PMEMoid encapsulated by this object.
Definition: persistent_ptr_base.hpp:151
Persistent pointer class.
Definition: persistent_ptr.hpp:152
The non-template pool base class.
Definition: pool.hpp:50
void persist(const void *addr, size_t len) noexcept
Performs persist operation on a given chunk of memory.
Definition: pool.hpp:279
Custom pool error class.
Definition: pexceptions.hpp:45
Custom transaction error class.
Definition: pexceptions.hpp:176
Commonly used functionality.
A persistent version of thread-local storage.
Functions for destroying arrays.
Pmem-resident mutex.
void allocator_move_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, std::true_type)
Move assignment implementation for allocator if propagate_on_container_move_assignment == true_type.
Definition: concurrent_skip_list_impl.hpp:80
void allocator_copy_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, std::true_type)
Copy assignment implementation for allocator if propagate_on_container_copy_assignment == true_type.
Definition: concurrent_skip_list_impl.hpp:58
void allocator_swap(MyAlloc &my_allocator, OtherAlloc &other_allocator, std::true_type)
Swap implementation for allocators if propagate_on_container_swap == true_type.
Definition: concurrent_skip_list_impl.hpp:102
T & get(pmem::obj::array< T, N > &a)
Non-member get function.
Definition: array.hpp:919
bool operator!=(const allocator< T, P, Tr > &lhs, const OtherAllocator &rhs)
Determines if memory from another allocator can be deallocated from this one.
Definition: allocator.hpp:536
p< T > & operator++(p< T > &pp)
Prefix increment operator overload.
Definition: pext.hpp:48
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
void swap(pmem::obj::array< T, N > &lhs, pmem::obj::array< T, N > &rhs)
Non-member swap function.
Definition: array.hpp:909
Persistent memory namespace.
Definition: allocation_flag.hpp:15
Persistent smart pointer.
C++ pmemobj pool.
Persistent self-relative smart pointer.
Commonly used SFINAE helpers.
C++ pmemobj transactions.