4 #ifndef PMEMOBJ_CONCURRENT_SKIP_LIST_IMPL_HPP 5 #define PMEMOBJ_CONCURRENT_SKIP_LIST_IMPL_HPP 14 #include <type_traits> 19 #include <libpmemobj++/detail/pair.hpp> 26 #include <libpmemobj++/experimental/atomic_self_relative_ptr.hpp> 47 try_insert_node_finish_marker()
56 template <
typename MyAlloc,
typename OtherAlloc>
61 my_allocator = other_allocator;
68 template <
typename MyAlloc,
typename OtherAlloc>
78 template <
typename MyAlloc,
typename OtherAlloc>
83 my_allocator = std::move(other_allocator);
90 template <
typename MyAlloc,
typename OtherAlloc>
100 template <
typename MyAlloc,
typename OtherAlloc>
105 std::swap(my_allocator, other_allocator);
112 template <
typename MyAlloc,
typename OtherAlloc>
119 typename LockType = std::unique_lock<Mutex>>
120 class skip_list_node {
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 *;
130 using atomic_node_pointer = std::atomic<node_pointer>;
131 using mutex_type = Mutex;
132 using lock_type = LockType;
134 skip_list_node(size_type levels) : height_(levels)
136 for (size_type lev = 0; lev < height_; ++lev)
137 detail::create<atomic_node_pointer>(&get_next(lev),
140 assert(height() == levels);
141 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED 146 for (size_type lev = 0; lev < height_; ++lev) {
147 VALGRIND_HG_DISABLE_CHECKING(&get_next(lev),
148 sizeof(get_next(lev)));
153 skip_list_node(size_type levels,
const node_pointer *new_nexts)
156 for (size_type lev = 0; lev < height_; ++lev)
157 detail::create<atomic_node_pointer>(&get_next(lev),
160 assert(height() == levels);
161 #if LIBPMEMOBJ_CPP_VG_HELGRIND_ENABLED 166 for (size_type lev = 0; lev < height_; ++lev) {
167 VALGRIND_HG_DISABLE_CHECKING(&get_next(lev),
168 sizeof(get_next(lev)));
175 for (size_type lev = 0; lev < height_; ++lev)
176 detail::destroy<atomic_node_pointer>(get_next(lev));
179 skip_list_node(
const skip_list_node &) =
delete;
181 skip_list_node &operator=(
const skip_list_node &) =
delete;
202 next(size_type level)
const 204 assert(level < height());
205 return get_next(level).load(std::memory_order_acquire);
213 set_next_tx(size_type level, node_pointer next)
215 assert(level < height());
216 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
217 auto &node = get_next(level);
218 obj::transaction::snapshot<atomic_node_pointer>(&node);
219 node.store(next, std::memory_order_release);
225 assert(level < height());
226 auto &node = get_next(level);
227 node.store(next, std::memory_order_release);
228 pop.
persist(&node,
sizeof(node));
232 set_nexts(
const node_pointer *new_nexts, size_type h)
234 assert(h == height());
235 auto *nexts = get_nexts();
237 for (size_type i = 0; i < h; i++) {
238 nexts[i].store(new_nexts[i], std::memory_order_relaxed);
246 set_nexts(new_nexts, h);
248 auto *nexts = get_nexts();
249 pop.
persist(nexts,
sizeof(nexts[0]) * h);
262 return lock_type(mutex);
266 atomic_node_pointer *
269 return reinterpret_cast<atomic_node_pointer *
>(
this + 1);
272 atomic_node_pointer &
273 get_next(size_type level)
275 auto *arr = get_nexts();
279 const atomic_node_pointer &
280 get_next(size_type level)
const 283 reinterpret_cast<const atomic_node_pointer *
>(
this + 1);
294 template <
typename NodeType,
bool is_const>
295 class skip_list_iterator {
296 using node_type = NodeType;
297 using node_ptr =
typename std::conditional<is_const,
const node_type *,
299 friend class skip_list_iterator<node_type, true>;
302 using value_type =
typename node_type::value_type;
303 using iterator_category = std::forward_iterator_tag;
304 using difference_type = std::ptrdiff_t;
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 *,
312 skip_list_iterator() : node(
nullptr)
317 skip_list_iterator(
const skip_list_iterator &other) : node(other.node)
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)
329 reference operator*()
const 331 return *(node->get());
334 pointer operator->()
const 342 assert(node !=
nullptr);
343 node = node->next(0).get();
350 skip_list_iterator tmp = *
this;
356 operator=(
const skip_list_iterator &other)
363 explicit skip_list_iterator(node_type *n) : node(n)
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)
375 template <
typename Traits>
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);
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);
387 template <
typename T,
bool M,
bool U>
389 operator==(
const skip_list_iterator<T, M> &lhs,
390 const skip_list_iterator<T, U> &rhs)
392 return lhs.node == rhs.node;
395 template <
typename T,
bool M,
bool U>
397 operator!=(
const skip_list_iterator<T, M> &lhs,
398 const skip_list_iterator<T, U> &rhs)
400 return lhs.node != rhs.node;
403 struct default_random_generator {
404 using gen_type = std::mt19937_64;
405 using result_type =
typename gen_type::result_type;
410 static thread_local gen_type engine(
411 static_cast<size_t>(time(0)));
416 static constexpr result_type
419 return gen_type::min();
422 static constexpr result_type
425 return gen_type::max();
429 template <
typename RndGenerator,
size_t MAX_LEVEL>
430 class geometric_level_generator {
432 using rnd_generator_type = RndGenerator;
434 static constexpr
size_t max_level = MAX_LEVEL;
441 static rnd_generator_type gen;
444 static thread_local std::geometric_distribution<size_t> d;
446 return (d(gen) % MAX_LEVEL) + 1;
478 template <
typename Traits>
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>;
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;
496 using list_node_type = skip_list_node<value_type>;
498 using iterator = skip_list_iterator<list_node_type, false>;
499 using const_iterator = skip_list_iterator<list_node_type, true>;
501 static constexpr size_type MAX_LEVEL = traits_type::max_level;
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 *;
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>;
520 static constexpr
bool allow_multimapping =
521 traits_type::allow_multimapping;
533 check_tx_stage_work();
554 const key_compare &comp,
555 const allocator_type &alloc = allocator_type())
556 : _node_allocator(alloc), _compare(comp)
558 check_tx_stage_work();
585 template <
class InputIt>
587 const key_compare &comp = key_compare(),
588 const allocator_type &alloc = allocator_type())
589 : _node_allocator(alloc), _compare(comp)
591 check_tx_stage_work();
593 while (first != last)
594 internal_unsafe_emplace(*first++);
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)
621 check_tx_stage_work();
623 internal_copy(other);
624 assert(_size == other._size);
647 const allocator_type &alloc)
648 : _node_allocator(alloc),
649 _compare(other._compare),
650 _rnd_generator(other._rnd_generator)
652 check_tx_stage_work();
654 internal_copy(other);
655 assert(_size == other._size);
677 : _node_allocator(
std::move(other._node_allocator)),
678 _compare(other._compare),
679 _rnd_generator(other._rnd_generator)
681 check_tx_stage_work();
683 internal_move(std::move(other));
706 const allocator_type &alloc)
707 : _node_allocator(alloc),
708 _compare(other._compare),
709 _rnd_generator(other._rnd_generator)
711 check_tx_stage_work();
713 if (alloc == other.get_allocator()) {
714 internal_move(std::move(other));
717 internal_copy(std::make_move_iterator(other.begin()),
718 std::make_move_iterator(other.end()));
733 assert(this->size() ==
734 size_type(std::distance(this->
begin(), this->
end())));
752 if (dummy_head ==
nullptr)
755 auto pop = get_pool_base();
803 using pocca_t =
typename node_allocator_traits::
804 propagate_on_container_copy_assignment;
807 other._node_allocator,
809 _compare = other._compare;
810 _rnd_generator = other._rnd_generator;
812 internal_copy(other);
845 using pocma_t =
typename node_allocator_traits::
846 propagate_on_container_move_assignment;
848 if (pocma_t::value ||
849 _node_allocator == other._node_allocator) {
852 other._node_allocator,
854 _compare = other._compare;
855 _rnd_generator = other._rnd_generator;
856 internal_move(std::move(other));
859 std::make_move_iterator(other.begin()),
860 std::make_move_iterator(other.end()));
883 for (
auto it = il.begin(); it != il.end(); ++it)
884 internal_unsafe_emplace(*it);
905 std::pair<iterator, bool>
908 return internal_insert(value.first, value);
929 template <
typename P,
930 typename std::enable_if<
931 std::is_constructible<value_type, P &&>::value>::type>
932 std::pair<iterator, bool>
935 return emplace(std::forward<P>(value));
954 std::pair<iterator, bool>
957 return internal_insert(value.first, std::move(value));
978 insert(const_iterator hint, const_reference value)
981 return insert(value).first;
1004 template <
typename P,
1005 typename std::enable_if<
1006 std::is_constructible<value_type, P &&>::value>::type>
1010 return emplace_hint(hint, std::forward<P>(value));
1027 template <
typename InputIterator>
1029 insert(InputIterator first, InputIterator last)
1031 for (InputIterator it = first; it != last; ++it)
1049 insert(std::initializer_list<value_type> ilist)
1051 insert(ilist.begin(), ilist.end());
1081 template <
typename... Args>
1082 std::pair<iterator, bool>
1085 return internal_emplace(std::forward<Args>(args)...);
1118 template <
typename... Args>
1123 return emplace(std::forward<Args>(args)...).first;
1149 template <
typename... Args>
1150 std::pair<iterator, bool>
1153 return internal_try_emplace(k, std::forward<Args>(args)...);
1179 template <
typename... Args>
1180 std::pair<iterator, bool>
1183 return internal_try_emplace(std::move(k),
1184 std::forward<Args>(args)...);
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
1220 return internal_try_emplace(std::forward<K>(k),
1221 std::forward<Args>(args)...);
1244 auto &size_diff = tls_data.local().size_diff;
1245 return internal_erase(pos, size_diff);
1267 return unsafe_erase(get_iterator(pos));
1289 auto &size_diff = tls_data.local().size_diff;
1292 while (first != last) {
1293 first = internal_erase(first, size_diff);
1297 return get_iterator(first);
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);
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,
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);
1370 return internal_get_bound(key, _compare);
1386 return internal_get_bound(key, _compare);
1402 template <
typename K,
1403 typename =
typename std::enable_if<
1404 has_is_transparent<key_compare>::value, K>::type>
1408 return internal_get_bound(x, _compare);
1424 template <
typename K,
1425 typename =
typename std::enable_if<
1426 has_is_transparent<key_compare>::value, K>::type>
1430 return internal_get_bound(x, _compare);
1446 return internal_get_bound(key, _compare);
1462 return internal_get_bound(key, _compare);
1479 template <
typename K,
1480 typename =
typename std::enable_if<
1481 has_is_transparent<key_compare>::value, K>::type>
1485 return internal_get_bound(x, _compare);
1502 template <
typename K,
1503 typename =
typename std::enable_if<
1504 has_is_transparent<key_compare>::value, K>::type>
1508 return internal_get_bound(x, _compare);
1524 return internal_get_bound(key, not_greater_compare(_compare));
1540 return internal_get_bound(key, not_greater_compare(_compare));
1556 template <
typename K,
1557 typename =
typename std::enable_if<
1558 has_is_transparent<key_compare>::value, K>::type>
1562 return internal_get_bound(x, not_greater_compare(_compare));
1578 template <
typename K,
1579 typename =
typename std::enable_if<
1580 has_is_transparent<key_compare>::value, K>::type>
1584 return internal_get_bound(x, not_greater_compare(_compare));
1600 return internal_get_bound(key, not_greater_compare(_compare));
1616 return internal_get_bound(key, not_greater_compare(_compare));
1632 template <
typename K,
1633 typename =
typename std::enable_if<
1634 has_is_transparent<key_compare>::value, K>::type>
1638 return internal_get_bound(x, not_greater_compare(_compare));
1654 template <
typename K,
1655 typename =
typename std::enable_if<
1656 has_is_transparent<key_compare>::value, K>::type>
1660 return internal_get_bound(x, not_greater_compare(_compare));
1676 auto it = internal_get_biggest_less_than(key, _compare);
1678 const_cast<typename iterator::node_ptr>(it.node));
1694 return internal_get_biggest_less_than(key, _compare);
1710 template <
typename K,
1711 typename =
typename std::enable_if<
1712 has_is_transparent<key_compare>::value, K>::type>
1716 auto it = internal_get_biggest_less_than(key, _compare);
1718 const_cast<typename iterator::node_ptr>(it.node));
1734 template <
typename K,
1735 typename =
typename std::enable_if<
1736 has_is_transparent<key_compare>::value, K>::type>
1740 return internal_get_biggest_less_than(key, _compare);
1756 auto it = internal_get_biggest_less_than(
1757 key, not_greater_compare(_compare));
1759 const_cast<typename iterator::node_ptr>(it.node));
1775 return internal_get_biggest_less_than(
1776 key, not_greater_compare(_compare));
1792 template <
typename K,
1793 typename =
typename std::enable_if<
1794 has_is_transparent<key_compare>::value, K>::type>
1798 auto it = internal_get_biggest_less_than(
1799 key, not_greater_compare(_compare));
1801 const_cast<typename iterator::node_ptr>(it.node));
1817 template <
typename K,
1818 typename =
typename std::enable_if<
1819 has_is_transparent<key_compare>::value, K>::type>
1823 return internal_get_biggest_less_than(
1824 key, not_greater_compare(_compare));
1838 return internal_find(key);
1852 return internal_find(key);
1867 template <
typename K,
1868 typename =
typename std::enable_if<
1869 has_is_transparent<key_compare>::value, K>::type>
1873 return internal_find(x);
1888 template <
typename K,
1889 typename =
typename std::enable_if<
1890 has_is_transparent<key_compare>::value, K>::type>
1894 return internal_find(x);
1909 return internal_count(key);
1924 template <
typename K,
1925 typename =
typename std::enable_if<
1926 has_is_transparent<key_compare>::value, K>::type>
1930 return internal_count(key);
1944 return find(key) !=
end();
1959 template <
typename K,
1960 typename =
typename std::enable_if<
1961 has_is_transparent<key_compare>::value, K>::type>
1965 return find(x) !=
end();
1979 assert(dummy_head->height() > 0);
1986 assert(current->height() > 0);
1988 delete_node(current);
1992 node_ptr head = dummy_head.
get();
1993 for (size_type i = 0; i < head->height(); ++i) {
1994 head->set_next_tx(i,
nullptr);
2013 return iterator(dummy_head.get()->next(0).get());
2025 return const_iterator(dummy_head.get()->next(0).get());
2037 return const_iterator(dummy_head.get()->next(0).get());
2050 return iterator(
nullptr);
2063 return const_iterator(
nullptr);
2076 return const_iterator(
nullptr);
2088 return _size.load(std::memory_order_relaxed);
2101 return std::numeric_limits<difference_type>::max();
2133 using pocs_t =
typename node_allocator_traits::
2134 propagate_on_container_swap;
2138 std::swap(_rnd_generator, other._rnd_generator);
2139 std::swap(dummy_head, other.dummy_head);
2144 _size = other._size.exchange(_size,
2145 std::memory_order_relaxed);
2168 std::pair<iterator, iterator>
2171 return std::pair<iterator, iterator>(lower_bound(key),
2194 std::pair<const_iterator, const_iterator>
2197 return std::pair<const_iterator, const_iterator>(
2198 lower_bound(key), upper_bound(key));
2223 template <
typename K,
2224 typename =
typename std::enable_if<
2225 has_is_transparent<key_compare>::value, K>::type>
2226 std::pair<iterator, iterator>
2229 return std::pair<iterator, iterator>(lower_bound(x),
2255 template <
typename K,
2256 typename =
typename std::enable_if<
2257 has_is_transparent<key_compare>::value, K>::type>
2258 std::pair<const_iterator, const_iterator>
2261 return std::pair<const_iterator, const_iterator>(
2262 lower_bound(key), upper_bound(key));
2289 enum insert_stage_type : uint8_t { not_started = 0, in_progress = 1 };
2294 struct tls_entry_type {
2299 char reserved[64 -
sizeof(decltype(ptr)) -
2300 sizeof(decltype(size_diff)) -
2301 sizeof(decltype(insert_stage))];
2303 static_assert(
sizeof(tls_entry_type) == 64,
2304 "The size of tls_entry_type should be 64 bytes.");
2316 if (pmemobj_tx_stage() != TX_STAGE_WORK)
2318 "Function called out of transaction scope.");
2325 if (pmemobj_tx_stage() != TX_STAGE_NONE)
2327 "Function called inside transaction scope.");
2338 create_dummy_head();
2344 assert(this->empty());
2345 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2346 dummy_head = other.dummy_head;
2347 other.dummy_head =
nullptr;
2348 other.create_dummy_head();
2350 _size.store(other._size.load(std::memory_order_relaxed),
2351 std::memory_order_relaxed);
2352 on_init_size = other.on_init_size;
2355 static const_reference
2356 get_val(const_node_ptr n)
2369 static const key_type &
2370 get_key(const_node_ptr n)
2373 return traits_type::get_key(get_val(n));
2376 template <
typename K>
2378 internal_find(
const K &key)
2380 iterator it = lower_bound(key);
2381 return (it ==
end() || _compare(key, traits_type::get_key(*it)))
2386 template <
typename K>
2388 internal_find(
const K &key)
const 2390 const_iterator it = lower_bound(key);
2391 return (it ==
end() || _compare(key, traits_type::get_key(*it)))
2396 template <
typename K>
2398 internal_count(
const K &key)
const 2400 if (allow_multimapping) {
2401 std::pair<const_iterator, const_iterator> range =
2403 return static_cast<size_type
>(
2404 std::distance(range.first, range.second));
2406 return (find(key) ==
end()) ? size_type(0) : size_type(1);
2419 template <
typename K,
typename po
inter_type,
typename comparator>
2422 const K &key,
const comparator &cmp)
const 2424 assert(level < prev->height());
2426 pointer_type curr = next.
get();
2428 while (curr && cmp(get_key(curr), key)) {
2430 assert(level < prev->height());
2431 next = prev->next(level);
2448 template <
typename K>
2451 next_array_type &next_nodes,
const K &key)
2453 if (allow_multimapping) {
2454 fill_prev_next_arrays(prev_nodes, next_nodes, key,
2455 not_greater_compare(_compare));
2457 fill_prev_next_arrays(prev_nodes, next_nodes, key,
2473 template <
typename K,
typename comparator>
2476 next_array_type &next_nodes,
const K &key,
2477 const comparator &cmp)
2479 node_ptr prev = dummy_head.get();
2480 prev_nodes.fill(prev);
2481 next_nodes.fill(
nullptr);
2483 for (size_type h = prev->height(); h > 0; --h) {
2485 internal_find_position(h - 1, prev, key, cmp);
2486 prev_nodes[h - 1] = prev;
2487 next_nodes[h - 1] = next;
2491 template <
typename K,
typename... Args>
2492 std::pair<iterator, bool>
2493 internal_try_emplace(K &&key, Args &&... args)
2495 return internal_insert(
2496 key, std::piecewise_construct,
2497 std::forward_as_tuple(std::forward<K>(key)),
2498 std::forward_as_tuple(std::forward<Args>(args)...));
2501 template <
typename... Args>
2502 std::pair<iterator, bool>
2503 internal_emplace(Args &&... args)
2506 tls_entry_type &tls_entry = tls_data.local();
2510 assert(tls_entry.ptr ==
nullptr);
2512 create_node(std::forward<Args>(args)...);
2513 ++tls_entry.size_diff;
2514 tls_entry.insert_stage = not_started;
2517 node_ptr n = tls_entry.ptr.get();
2518 size_type height = n->height();
2520 std::pair<iterator, bool> insert_result = internal_insert_node(
2522 [&](
const next_array_type &next_nodes)
2524 assert(tls_entry.insert_stage == not_started);
2525 assert(tls_entry.ptr !=
nullptr);
2527 n->set_nexts(pop, next_nodes.data(), height);
2529 tls_entry.insert_stage = in_progress;
2530 pop.
persist(&(tls_entry.insert_stage),
2531 sizeof(tls_entry.insert_stage));
2533 return tls_entry.ptr;
2536 if (!insert_result.second) {
2537 assert(tls_entry.ptr !=
nullptr);
2538 assert(tls_entry.insert_stage == not_started);
2541 --tls_entry.size_diff;
2542 delete_node(tls_entry.ptr);
2543 tls_entry.ptr =
nullptr;
2547 assert(tls_entry.ptr ==
nullptr);
2548 return insert_result;
2555 template <
typename... Args>
2556 std::pair<iterator, bool>
2559 check_tx_stage_work();
2562 create_node(std::forward<Args>(args)...);
2564 node_ptr n = new_node.
get();
2565 size_type height = n->height();
2567 std::pair<iterator, bool> insert_result = internal_insert_node(
2569 [&](
const next_array_type &next_nodes)
2571 assert(new_node !=
nullptr);
2573 n->set_nexts(next_nodes.data(), height);
2578 if (insert_result.second) {
2581 assert(new_node !=
nullptr);
2583 delete_node(new_node);
2586 return insert_result;
2592 template <
typename K,
typename... Args>
2593 std::pair<iterator, bool>
2597 tls_entry_type &tls_entry = tls_data.local();
2598 assert(tls_entry.ptr ==
nullptr);
2600 size_type height = random_level();
2602 std::pair<iterator, bool> insert_result = internal_insert_node(
2604 [&](
const next_array_type &next_nodes)
2609 tls_entry.ptr = create_node(
2610 std::forward_as_tuple(
2611 height, next_nodes.data()),
2612 std::forward_as_tuple(
2613 std::forward<Args>(args)...));
2615 ++(tls_entry.size_diff);
2616 tls_entry.insert_stage = in_progress;
2619 assert(tls_entry.ptr !=
nullptr);
2620 return tls_entry.ptr;
2623 assert(tls_entry.ptr ==
nullptr);
2625 return insert_result;
2631 template <
typename K,
typename PrepareNode>
2632 std::pair<iterator, bool>
2634 PrepareNode &&prepare_new_node)
2636 prev_array_type prev_nodes;
2637 next_array_type next_nodes;
2638 node_ptr n =
nullptr;
2641 find_insert_pos(prev_nodes, next_nodes, key);
2643 node_ptr next = next_nodes[0].get();
2644 if (next && !allow_multimapping &&
2645 !_compare(key, get_key(next))) {
2647 return std::pair<iterator, bool>(iterator(next),
2651 }
while ((n = try_insert_node(prev_nodes, next_nodes, height,
2652 std::forward<PrepareNode>(
2653 prepare_new_node))) ==
2657 return std::pair<iterator, bool>(iterator(n),
true);
2665 template <
typename PrepareNode>
2668 const next_array_type &next_nodes, size_type height,
2669 PrepareNode &&prepare_new_node)
2671 assert(dummy_head->height() >= height);
2674 if (!try_lock_nodes(height, prev_nodes, next_nodes, locks)) {
2678 node_lock_type new_node_lock;
2681 assert(new_node !=
nullptr);
2682 node_ptr n = new_node.
get();
2690 new_node_lock = n->acquire();
2702 for (size_type level = 0; level < height; ++level) {
2703 assert(prev_nodes[level]->height() > level);
2704 assert(prev_nodes[level]->next(level) ==
2706 assert(prev_nodes[level]->next(level) ==
2708 prev_nodes[level]->set_next(pop, level, new_node);
2712 try_insert_node_finish_marker();
2719 pop.
persist(&new_node,
sizeof(new_node));
2722 #if LIBPMEMOBJ_CPP_VG_PMEMCHECK_ENABLED 2723 VALGRIND_PMC_DO_FLUSH(&_size,
sizeof(_size));
2737 for (size_type l = 1; l < height; ++l) {
2738 if (prevs[l] == dummy_head.get()) {
2742 assert(prevs[l - 1] != dummy_head.get());
2743 assert(!_compare(get_key(prevs[l - 1]),
2744 get_key(prevs[l])));
2751 try_lock_nodes(size_type height, prev_array_type &prevs,
2752 const next_array_type &nexts, lock_array &locks)
2754 assert(check_prev_array(prevs, height));
2756 for (size_type l = 0; l < height; ++l) {
2757 if (l == 0 || prevs[l] != prevs[l - 1]) {
2758 locks[l] = prevs[l]->acquire();
2762 if (next != nexts[l])
2783 template <
typename K,
typename comparator>
2787 const_node_ptr prev = dummy_head.get();
2788 assert(prev->height() > 0);
2791 for (size_type h = prev->height(); h > 0; --h) {
2792 next = internal_find_position(h - 1, prev, key, cmp);
2795 return const_iterator(next.get());
2809 template <
typename K,
typename comparator>
2813 node_ptr prev = dummy_head.get();
2814 assert(prev->height() > 0);
2817 for (size_type h = prev->height(); h > 0; --h) {
2818 next = internal_find_position(h - 1, prev, key, cmp);
2821 return iterator(next.get());
2835 template <
typename K,
typename comparator>
2838 const comparator &cmp)
const 2840 const_node_ptr prev = dummy_head.get();
2841 assert(prev->height() > 0);
2843 for (size_type h = prev->height(); h > 0; --h) {
2844 internal_find_position(h - 1, prev, key, cmp);
2847 if (prev == dummy_head.get())
2850 return const_iterator(prev);
2856 assert(pos !=
end());
2860 std::pair<persistent_node_ptr, persistent_node_ptr>
2861 extract_result(
nullptr,
nullptr);
2864 extract_result = internal_extract(pos);
2867 assert(extract_result.first !=
nullptr);
2868 delete_node(extract_result.first);
2874 return iterator(extract_result.second.get());
2880 std::pair<persistent_node_ptr, persistent_node_ptr>
2883 assert(dummy_head->height() > 0);
2884 assert(it !=
end());
2885 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2887 const key_type &key = traits_type::get_key(*it);
2889 prev_array_type prev_nodes;
2890 next_array_type next_nodes;
2892 fill_prev_next_arrays(prev_nodes, next_nodes, key, _compare);
2894 node_ptr erase_node = next_nodes[0].get();
2895 assert(erase_node !=
nullptr);
2897 if (!_compare(key, get_key(erase_node))) {
2901 assert(erase_node == it.node);
2902 return internal_extract_node(prev_nodes, next_nodes,
2906 return std::pair<persistent_node_ptr, persistent_node_ptr>(
2910 std::pair<persistent_node_ptr, persistent_node_ptr>
2911 internal_extract_node(
const prev_array_type &prev_nodes,
2912 const next_array_type &next_nodes,
2913 node_ptr erase_node)
2915 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2916 assert(erase_node !=
nullptr);
2917 for (size_type level = 0; level < erase_node->height();
2919 assert(prev_nodes[level]->height() > level);
2920 assert(next_nodes[level].
get() == erase_node);
2921 prev_nodes[level]->set_next_tx(level,
2922 erase_node->next(level));
2925 return std::pair<persistent_node_ptr, persistent_node_ptr>(
2926 next_nodes[0], erase_node->next(0));
2936 PMEMobjpool *pop = pmemobj_pool_by_ptr(
this);
2943 internal_copy(other.
begin(), other.
end());
2946 template <
typename Iterator>
2948 internal_copy(Iterator first, Iterator last)
2950 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
2952 prev_array_type prev_nodes;
2953 prev_nodes.fill(dummy_head.get());
2956 for (; first != last; ++first, ++sz) {
2958 node_ptr n = new_node.
get();
2959 for (size_type level = 0; level < n->height();
2961 prev_nodes[level]->set_next_tx(level, new_node);
2962 prev_nodes[level] = n;
2974 assert(std::is_sorted(
2976 [&](
const value_type &lhs,
const value_type &rhs) {
2977 return lhs.first < rhs.first;
2985 return _rnd_generator();
2989 calc_node_size(size_type height)
2991 return sizeof(list_node_type) +
2996 template <
typename... Args>
3000 size_type levels = random_level();
3003 std::forward_as_tuple(levels),
3004 std::forward_as_tuple(std::forward<Args>(args)...));
3007 template <
typename... NodeArgs,
typename... ValueArgs>
3009 create_node(std::tuple<NodeArgs...> &&node_args,
3010 std::tuple<ValueArgs...> &&value_args)
3012 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
3015 std::forward<std::tuple<NodeArgs...>>(node_args),
3016 index_sequence_for<NodeArgs...>{});
3018 construct_value_type(
3020 std::forward<std::tuple<ValueArgs...>>(value_args),
3021 index_sequence_for<ValueArgs...>{});
3026 template <
typename Tuple,
size_t... I>
3029 index_sequence<I...>)
3031 node_ptr new_node = node.
get();
3033 node_allocator_traits::construct(
3034 _node_allocator, new_node->get(),
3035 std::get<I>(std::forward<Tuple>(args))...);
3046 dummy_head = creates_dummy_node(MAX_LEVEL);
3049 template <
typename Tuple,
size_t... I>
3051 creates_dummy_node(Tuple &&args, index_sequence<I...>)
3053 return creates_dummy_node(
3054 std::get<I>(std::forward<Tuple>(args))...);
3066 template <
typename... Args>
3070 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
3071 size_type sz = calc_node_size(height);
3074 node_allocator_traits::allocate(_node_allocator, sz)
3077 assert(n !=
nullptr);
3079 node_allocator_traits::construct(_node_allocator, n.
get(),
3081 std::forward<Args>(args)...);
3086 template <
bool is_dummy = false>
3090 assert(pmemobj_tx_stage() == TX_STAGE_WORK);
3091 node_ptr n = node.
get();
3092 size_type sz = calc_node_size(n->height());
3096 node_allocator_traits::destroy(_node_allocator,
3099 node_allocator_traits::destroy(_node_allocator, n);
3101 deallocate_node(node, sz);
3116 node_allocator_traits::deallocate(_node_allocator, tmp, sz);
3122 assert(dummy_head !=
nullptr);
3123 delete_node<true>(dummy_head);
3124 assert(dummy_head ==
nullptr);
3128 get_iterator(const_iterator it)
3131 const_cast<typename iterator::node_ptr>(it.node));
3138 int64_t last_run_size = 0;
3141 for (
auto &tls_entry : tls_data) {
3143 auto &size_diff = tls_entry.size_diff;
3155 if (tls_entry.insert_stage == in_progress) {
3156 complete_insert(tls_entry);
3159 --(tls_entry.size_diff);
3166 assert(node ==
nullptr);
3168 last_run_size += size_diff;
3172 assert(last_run_size >= 0 ||
3174 static_cast<size_type>(std::abs(last_run_size)));
3177 on_init_size +=
static_cast<size_t>(last_run_size);
3179 _size = on_init_size;
3180 #if LIBPMEMOBJ_CPP_VG_PMEMCHECK_ENABLED 3181 VALGRIND_PMC_DO_FLUSH(&_size,
sizeof(_size));
3186 complete_insert(tls_entry_type &tls_entry)
3189 assert(node !=
nullptr);
3190 assert(tls_entry.insert_stage == in_progress);
3191 prev_array_type prev_nodes;
3192 next_array_type next_nodes;
3193 node_ptr n = node.
get();
3194 const key_type &key = get_key(n);
3195 size_type height = n->height();
3197 fill_prev_next_arrays(prev_nodes, next_nodes, key, _compare);
3201 for (size_type level = 0; level < height; ++level) {
3202 assert(prev_nodes[level]->height() > level);
3203 assert(prev_nodes[level]->next(level) ==
3206 if (prev_nodes[level]->next(level) != node) {
3209 assert(n->next(level) == next_nodes[level]);
3210 prev_nodes[level]->set_next(pop, level, node);
3215 pop.
persist(&node,
sizeof(node));
3218 struct not_greater_compare {
3219 const key_compare &my_less_compare;
3221 not_greater_compare(
const key_compare &less_compare)
3222 : my_less_compare(less_compare)
3226 template <
typename K1,
typename K2>
3228 operator()(
const K1 &first,
const K2 &second)
const 3230 return !my_less_compare(second, first);
3234 const uint64_t pool_uuid = pmemobj_oid(
this).pool_uuid_lo;
3235 node_allocator_type _node_allocator;
3236 key_compare _compare;
3237 random_level_generator_type _rnd_generator;
3242 std::atomic<size_type> _size;
3252 template <
typename Key,
typename Value,
typename KeyCompare,
3253 typename RND_GENERATOR,
typename Allocator,
bool AllowMultimapping,
3257 static constexpr
size_t max_level = MAX_LEVEL;
3258 using random_generator_type = RND_GENERATOR;
3259 using key_type = Key;
3260 using mapped_type = Value;
3261 using compare_type = KeyCompare;
3262 using value_type = pair<const key_type, mapped_type>;
3263 using reference = value_type &;
3264 using const_reference =
const value_type &;
3265 using allocator_type = Allocator;
3273 constexpr
static bool allow_multimapping = AllowMultimapping;
3275 static const key_type &
3276 get_key(const_reference val)
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:2557
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
Persistent self-relative smart pointer.
std::pair< iterator, bool > insert(value_type &&value)
Inserts value using move semantic.
Definition: concurrent_skip_list_impl.hpp:955
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
void free_data()
Should be called before concurrent_skip_list destructor is called.
Definition: concurrent_skip_list_impl.hpp:750
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:2421
concurrent_skip_list(const concurrent_skip_list &other, const allocator_type &alloc)
Copy constructor.
Definition: concurrent_skip_list_impl.hpp:646
Persistent pointer class.
Definition: common.hpp:107
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
void swap(pmem::obj::array< T, N > &lhs, pmem::obj::array< T, N > &rhs)
Non-member swap function.
Definition: array.hpp:880
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, key) is false.
Definition: concurrent_skip_list_impl.hpp:2785
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
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:2667
The non-template pool base class.
Definition: pool.hpp:46
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
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
concurrent_skip_list(concurrent_skip_list &&other, const allocator_type &alloc)
Move constructor.
Definition: concurrent_skip_list_impl.hpp:705
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:2259
Custom pool error class.
Definition: pexceptions.hpp:45
void clear()
Erases all elements from the container transactionally.
Definition: concurrent_skip_list_impl.hpp:1977
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
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
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
const key_compare & key_comp() const
Returns a const reference to the object that compares the keys.
Definition: concurrent_skip_list_impl.hpp:2271
iterator find(const K &x)
Finds an element with key that compares equivalent to the value x.
Definition: concurrent_skip_list_impl.hpp:1871
void swap(concurrent_skip_list &other)
XXX: Implement get_allocator() interface.
Definition: concurrent_skip_list_impl.hpp:2129
Definition: concurrent_hash_map.hpp:42
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 ...
Definition: transaction.hpp:496
void runtime_initialize()
Intialize concurrent_skip_list after process restart.
Definition: concurrent_skip_list_impl.hpp:729
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:2475
obj::pool_base get_pool_base() const
Get the persistent memory pool where hashmap resides.
Definition: concurrent_skip_list_impl.hpp:2934
concurrent_skip_list()
Default constructor.
Definition: concurrent_skip_list_impl.hpp:531
size_type random_level()
Generate random level.
Definition: concurrent_skip_list_impl.hpp:2983
C++ manual scope transaction class.
Definition: transaction.hpp:84
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 check_tx_stage_work() const
Private helper function.
Definition: concurrent_skip_list_impl.hpp:2314
C++ pmemobj transactions.
iterator unsafe_erase(iterator pos)
Removes the element at pos from the container.
Definition: concurrent_skip_list_impl.hpp:1241
bool check_prev_array(const prev_array_type &prevs, size_type height)
Used only inside asserts.
Definition: concurrent_skip_list_impl.hpp:2735
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
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
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:2633
Functions for destroying arrays.
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
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
Commonly used functionality.
iterator unsafe_erase(const_iterator pos)
Removes the element at pos from the container.
Definition: concurrent_skip_list_impl.hpp:1265
std::pair< persistent_node_ptr, persistent_node_ptr > internal_extract(const_iterator it)
Definition: concurrent_skip_list_impl.hpp:2881
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:2227
iterator begin()
Returns an iterator to the first element of the container.
Definition: concurrent_skip_list_impl.hpp:2011
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
key_compare & key_comp()
Returns a reference to the object that compares the keys.
Definition: concurrent_skip_list_impl.hpp:2282
Persistent memory aware implementation of the concurrent skip list.
Definition: concurrent_skip_list_impl.hpp:479
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
iterator find(const key_type &key)
Finds an element with key equivalent to key.
Definition: concurrent_skip_list_impl.hpp:1836
pmem::obj::array< T, N >::iterator end(pmem::obj::array< T, N > &a)
Non-member end.
Definition: array.hpp:820
void insert(std::initializer_list< value_type > ilist)
Inserts elements from initializer list ilist.
Definition: concurrent_skip_list_impl.hpp:1049
concurrent_skip_list & operator=(concurrent_skip_list &&other)
Move assignment operator.
Definition: concurrent_skip_list_impl.hpp:838
obj::p< size_type > on_init_size
This variable holds real size after the skip list is initialized.
Definition: concurrent_skip_list_impl.hpp:3249
bool empty() const
Checks if the container has no elements, i.e.
Definition: concurrent_skip_list_impl.hpp:2111
static void commit()
Manually commit a transaction.
Definition: transaction.hpp:353
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
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
void persist(const void *addr, size_t len) noexcept
Performs persist operation on a given chunk of memory.
Definition: pool.hpp:283
Persistent memory resident mutex implementation.
Definition: mutex.hpp:31
const_iterator end() const
Returns an iterator to the element following the last element of the map.
Definition: concurrent_skip_list_impl.hpp:2061
const_iterator begin() const
Returns an iterator to the first element of the container.
Definition: concurrent_skip_list_impl.hpp:2023
concurrent_skip_list & operator=(const concurrent_skip_list &other)
Copy assignment operator.
Definition: concurrent_skip_list_impl.hpp:796
A persistent version of thread-local storage.
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:2450
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
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
element_type * get() const noexcept
Get the direct pointer.
Definition: self_relative_ptr.hpp:159
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
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:2195
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
persistent_node_ptr create_node(Args &&... args)
Creates new node.
Definition: concurrent_skip_list_impl.hpp:2998
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
void create_dummy_head()
Creates dummy head.
Definition: concurrent_skip_list_impl.hpp:3044
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 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, key) is true.
Definition: concurrent_skip_list_impl.hpp:2837
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:2169
iterator end()
Returns an iterator to the element following the last element of the map.
Definition: concurrent_skip_list_impl.hpp:2048
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
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 > insert(P &&value)
Inserts value.
Definition: concurrent_skip_list_impl.hpp:933
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
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
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
Commonly used SFINAE helpers.
const_iterator find(const key_type &key) const
Finds an element with key equivalent to key.
Definition: concurrent_skip_list_impl.hpp:1850
size_type size() const
Returns the number of elements in the container, i.e.
Definition: concurrent_skip_list_impl.hpp:2086
const_iterator cbegin() const
Returns an iterator to the first element of the container.
Definition: concurrent_skip_list_impl.hpp:2035
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
Persistent smart pointer.
concurrent_skip_list(const key_compare &comp, const allocator_type &alloc=allocator_type())
Constructs an empty container.
Definition: concurrent_skip_list_impl.hpp:553
Persistent self-relative pointer class.
Definition: self_relative_ptr.hpp:44
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
~concurrent_skip_list()
Destructor.
Definition: concurrent_skip_list_impl.hpp:771
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, key) is false.
Definition: concurrent_skip_list_impl.hpp:2811
concurrent_skip_list(const concurrent_skip_list &other)
Copy constructor.
Definition: concurrent_skip_list_impl.hpp:614
void insert(InputIterator first, InputIterator last)
Inserts elements from range [first, last).
Definition: concurrent_skip_list_impl.hpp:1029
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 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
p< T > & operator++(p< T > &pp)
Prefix increment operator overload.
Definition: pext.hpp:48
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
persistent_ptr< T > to_persistent_ptr() const
Conversion to persitent ptr.
Definition: self_relative_ptr.hpp:169
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
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
const_iterator cend() const
Returns an iterator to the element following the last element of the map.
Definition: concurrent_skip_list_impl.hpp:2074
Custom transaction error class.
Definition: pexceptions.hpp:158
Persistent memory namespace.
Definition: allocation_flag.hpp:14
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
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
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
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
void tls_restore()
Process any information which was saved to tls and clears tls.
Definition: concurrent_skip_list_impl.hpp:3136
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
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
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
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
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:3068
std::pair< iterator, bool > insert(const value_type &value)
Inserts value in a thread-safe way.
Definition: concurrent_skip_list_impl.hpp:906
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:2594
concurrent_skip_list(concurrent_skip_list &&other)
Move constructor.
Definition: concurrent_skip_list_impl.hpp:676
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
static void run(pool_base &pool, std::function< void()> tx, Locks &... locks)
Execute a closure-like transaction and lock locks.
Definition: transaction.hpp:406
bool operator==(standard_alloc_policy< T > const &, standard_alloc_policy< T2 > const &)
Determines if memory from another allocator can be deallocated from this one.
Definition: allocator.hpp:420
pmem::obj::array< T, N >::iterator begin(pmem::obj::array< T, N > &a)
Non-member begin.
Definition: array.hpp:800
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