File indexing completed on 2025-07-30 08:46:15
0001
0002
0003
0004
0005
0006
0007
0008
0009
0010
0011
0012
0013
0014
0015
0016
0017 #ifndef __TBB_detail__concurrent_skip_list_H
0018 #define __TBB_detail__concurrent_skip_list_H
0019
0020 #if !defined(__TBB_concurrent_map_H) && !defined(__TBB_concurrent_set_H)
0021 #error Do not #include this internal file directly; use public TBB headers instead.
0022 #endif
0023
0024 #include "_config.h"
0025 #include "_range_common.h"
0026 #include "_allocator_traits.h"
0027 #include "_template_helpers.h"
0028 #include "_node_handle.h"
0029 #include "_containers_helpers.h"
0030 #include "_assert.h"
0031 #include "_exception.h"
0032 #include "../enumerable_thread_specific.h"
0033 #include <utility>
0034 #include <initializer_list>
0035 #include <atomic>
0036 #include <array>
0037 #include <type_traits>
0038 #include <random> // Need std::geometric_distribution
0039 #include <algorithm> // Need std::equal and std::lexicographical_compare
0040 #include <cstdint>
0041 #if __TBB_CPP20_COMPARISONS_PRESENT
0042 #include <compare>
0043 #endif
0044
0045 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
0046 #pragma warning(push)
0047 #pragma warning(disable: 4127)
0048 #endif
0049
0050 namespace tbb {
0051 namespace detail {
0052 namespace d2 {
0053
0054 template <typename Value, typename Allocator>
0055 class skip_list_node {
0056 using node_ptr = skip_list_node*;
0057 public:
0058 using value_type = Value;
0059 using atomic_node_ptr = std::atomic<node_ptr>;
0060 using size_type = std::size_t;
0061 using container_allocator_type = Allocator;
0062
0063 using reference = value_type&;
0064 using const_reference = const value_type&;
0065 private:
0066 using allocator_traits = tbb::detail::allocator_traits<container_allocator_type>;
0067
0068
0069
0070 using value_allocator_traits = typename allocator_traits::template rebind_traits<value_type>;
0071 public:
0072 using pointer = typename value_allocator_traits::pointer;
0073 using const_pointer = typename value_allocator_traits::const_pointer;
0074
0075
0076
0077
0078
0079 skip_list_node( size_type levels )
0080 : my_height(levels), my_index_number(0)
0081 {}
0082
0083
0084 ~skip_list_node() {}
0085
0086 skip_list_node( const skip_list_node& ) = delete;
0087 skip_list_node( skip_list_node&& ) = delete;
0088 skip_list_node& operator=( const skip_list_node& ) = delete;
0089 skip_list_node& operator=( skip_list_node&& ) = delete;
0090
0091 static skip_list_node* create( container_allocator_type& alloc, size_type height ) {
0092 size_type sz = calc_node_size(height);
0093 static_assert(std::is_same<typename allocator_traits::value_type, std::uint8_t>::value, "skip_list_node assumes that passed in allocator operates on bytes");
0094 auto* node = reinterpret_cast<skip_list_node*>(allocator_traits::allocate(alloc, sz));
0095
0096
0097 allocator_traits::construct(alloc, node, height);
0098
0099
0100 for (size_type l = 0; l < height; ++l) {
0101 allocator_traits::construct(alloc, &node->get_atomic_next(l), nullptr);
0102 }
0103
0104 return node;
0105 }
0106
0107 static void destroy( container_allocator_type& alloc, skip_list_node* node ) {
0108
0109 for (size_type l = 0; l < node->height(); ++l) {
0110 allocator_traits::destroy(alloc, &node->atomic_next(l));
0111 }
0112 size_type sz = calc_node_size(node->height());
0113
0114 allocator_traits::destroy(alloc, node);
0115
0116
0117 allocator_traits::deallocate(alloc, reinterpret_cast<std::uint8_t*>(node), sz);
0118 }
0119
0120
0121 pointer storage() {
0122 return &my_value;
0123 }
0124
0125 reference value() {
0126 return *storage();
0127 }
0128
0129 node_ptr next( size_type level ) const {
0130 node_ptr res = get_atomic_next(level).load(std::memory_order_acquire);
0131 __TBB_ASSERT(res == nullptr || res->height() > level, "Broken internal structure");
0132 return res;
0133 }
0134
0135 atomic_node_ptr& atomic_next( size_type level ) {
0136 atomic_node_ptr& res = get_atomic_next(level);
0137 #if TBB_USE_DEBUG
0138 node_ptr node = res.load(std::memory_order_acquire);
0139 __TBB_ASSERT(node == nullptr || node->height() > level, "Broken internal structure");
0140 #endif
0141 return res;
0142 }
0143
0144 void set_next( size_type level, node_ptr n ) {
0145 __TBB_ASSERT(n == nullptr || n->height() > level, "Broken internal structure");
0146 get_atomic_next(level).store(n, std::memory_order_relaxed);
0147 }
0148
0149 size_type height() const {
0150 return my_height;
0151 }
0152
0153 void set_index_number( size_type index_num ) {
0154 my_index_number = index_num;
0155 }
0156
0157 size_type index_number() const {
0158 return my_index_number;
0159 }
0160
0161 private:
0162 static size_type calc_node_size( size_type height ) {
0163 static_assert(alignof(skip_list_node) >= alignof(atomic_node_ptr), "Incorrect alignment");
0164 return sizeof(skip_list_node) + height * sizeof(atomic_node_ptr);
0165 }
0166
0167 atomic_node_ptr& get_atomic_next( size_type level ) {
0168 atomic_node_ptr* arr = reinterpret_cast<atomic_node_ptr*>(this + 1);
0169 return arr[level];
0170 }
0171
0172 const atomic_node_ptr& get_atomic_next( size_type level ) const {
0173 const atomic_node_ptr* arr = reinterpret_cast<const atomic_node_ptr*>(this + 1);
0174 return arr[level];
0175 }
0176
0177 union {
0178 value_type my_value;
0179 };
0180 size_type my_height;
0181 size_type my_index_number;
0182 };
0183
0184 template <typename NodeType, typename ValueType>
0185 class skip_list_iterator {
0186 using node_type = NodeType;
0187 using node_ptr = node_type*;
0188 public:
0189 using iterator_category = std::forward_iterator_tag;
0190 using value_type = ValueType;
0191
0192 using difference_type = std::ptrdiff_t;
0193 using pointer = value_type*;
0194 using reference = value_type&;
0195
0196 skip_list_iterator() : skip_list_iterator(nullptr) {}
0197
0198 skip_list_iterator( const skip_list_iterator<node_type, typename node_type::value_type>& other )
0199 : my_node_ptr(other.my_node_ptr) {}
0200
0201 skip_list_iterator& operator=( const skip_list_iterator<node_type, typename node_type::value_type>& other ) {
0202 my_node_ptr = other.my_node_ptr;
0203 return *this;
0204 }
0205
0206 reference operator*() const { return my_node_ptr->value(); }
0207 pointer operator->() const { return my_node_ptr->storage(); }
0208
0209 skip_list_iterator& operator++() {
0210 __TBB_ASSERT(my_node_ptr != nullptr, nullptr);
0211 my_node_ptr = my_node_ptr->next(0);
0212 return *this;
0213 }
0214
0215 skip_list_iterator operator++(int) {
0216 skip_list_iterator tmp = *this;
0217 ++*this;
0218 return tmp;
0219 }
0220
0221 private:
0222 skip_list_iterator(node_type* n) : my_node_ptr(n) {}
0223
0224 node_ptr my_node_ptr;
0225
0226 template <typename Traits>
0227 friend class concurrent_skip_list;
0228
0229 template <typename N, typename V>
0230 friend class skip_list_iterator;
0231
0232 friend class const_range;
0233 friend class range;
0234
0235 friend bool operator==( const skip_list_iterator& lhs, const skip_list_iterator& rhs ) {
0236 return lhs.my_node_ptr == rhs.my_node_ptr;
0237 }
0238
0239 friend bool operator!=( const skip_list_iterator& lhs, const skip_list_iterator& rhs ) {
0240 return lhs.my_node_ptr != rhs.my_node_ptr;
0241 }
0242 };
0243
0244 template <typename Traits>
0245 class concurrent_skip_list {
0246 protected:
0247 using container_traits = Traits;
0248 using self_type = concurrent_skip_list<container_traits>;
0249 using allocator_type = typename container_traits::allocator_type;
0250 using allocator_traits_type = tbb::detail::allocator_traits<allocator_type>;
0251 using key_compare = typename container_traits::compare_type;
0252 using value_compare = typename container_traits::value_compare;
0253 using key_type = typename container_traits::key_type;
0254 using value_type = typename container_traits::value_type;
0255 static_assert(std::is_same<value_type, typename allocator_type::value_type>::value,
0256 "value_type of the container should be the same as its allocator");
0257
0258 using size_type = std::size_t;
0259 using difference_type = std::ptrdiff_t;
0260
0261 static constexpr size_type max_level = container_traits::max_level;
0262
0263 using node_allocator_type = typename allocator_traits_type::template rebind_alloc<std::uint8_t>;
0264 using node_allocator_traits = tbb::detail::allocator_traits<node_allocator_type>;
0265
0266 using list_node_type = skip_list_node<value_type, node_allocator_type>;
0267 using node_type = d1::node_handle<key_type, value_type, list_node_type, allocator_type>;
0268
0269 using iterator = skip_list_iterator<list_node_type, value_type>;
0270 using const_iterator = skip_list_iterator<list_node_type, const value_type>;
0271
0272 using reference = value_type&;
0273 using const_reference = const value_type&;
0274 using pointer = typename allocator_traits_type::pointer;
0275 using const_pointer = typename allocator_traits_type::const_pointer;
0276
0277 using random_level_generator_type = typename container_traits::random_level_generator_type;
0278
0279 using node_ptr = list_node_type*;
0280
0281 using array_type = std::array<node_ptr, max_level>;
0282 private:
0283 template <typename T>
0284 using is_transparent = dependent_bool<comp_is_transparent<key_compare>, T>;
0285 public:
0286 static constexpr bool allow_multimapping = container_traits::allow_multimapping;
0287
0288 concurrent_skip_list() : my_head_ptr(nullptr), my_size(0), my_max_height(0) {}
0289
0290 explicit concurrent_skip_list( const key_compare& comp, const allocator_type& alloc = allocator_type() )
0291 : my_node_allocator(alloc), my_compare(comp), my_head_ptr(nullptr), my_size(0), my_max_height(0) {}
0292
0293 explicit concurrent_skip_list( const allocator_type& alloc )
0294 : concurrent_skip_list(key_compare(), alloc) {}
0295
0296 template<typename InputIterator>
0297 concurrent_skip_list( InputIterator first, InputIterator last, const key_compare& comp = key_compare(),
0298 const allocator_type& alloc = allocator_type() )
0299 : concurrent_skip_list(comp, alloc)
0300 {
0301 internal_copy(first, last);
0302 }
0303
0304 template <typename InputIterator>
0305 concurrent_skip_list( InputIterator first, InputIterator last, const allocator_type& alloc )
0306 : concurrent_skip_list(first, last, key_compare(), alloc) {}
0307
0308 concurrent_skip_list( std::initializer_list<value_type> init, const key_compare& comp = key_compare(),
0309 const allocator_type& alloc = allocator_type() )
0310 : concurrent_skip_list(init.begin(), init.end(), comp, alloc) {}
0311
0312 concurrent_skip_list( std::initializer_list<value_type> init, const allocator_type& alloc )
0313 : concurrent_skip_list(init, key_compare(), alloc) {}
0314
0315 concurrent_skip_list( const concurrent_skip_list& other )
0316 : my_node_allocator(node_allocator_traits::select_on_container_copy_construction(other.get_allocator())),
0317 my_compare(other.my_compare), my_rng(other.my_rng), my_head_ptr(nullptr),
0318 my_size(0), my_max_height(0)
0319 {
0320 internal_copy(other);
0321 __TBB_ASSERT(my_size == other.my_size, "Wrong size of copy-constructed container");
0322 }
0323
0324 concurrent_skip_list( const concurrent_skip_list& other, const allocator_type& alloc )
0325 : my_node_allocator(alloc), my_compare(other.my_compare), my_rng(other.my_rng), my_head_ptr(nullptr),
0326 my_size(0), my_max_height(0)
0327 {
0328 internal_copy(other);
0329 __TBB_ASSERT(my_size == other.my_size, "Wrong size of copy-constructed container");
0330 }
0331
0332 concurrent_skip_list( concurrent_skip_list&& other )
0333 : my_node_allocator(std::move(other.my_node_allocator)), my_compare(other.my_compare),
0334 my_rng(std::move(other.my_rng)), my_head_ptr(nullptr)
0335 {
0336 internal_move(std::move(other));
0337 }
0338
0339 concurrent_skip_list( concurrent_skip_list&& other, const allocator_type& alloc )
0340 : my_node_allocator(alloc), my_compare(other.my_compare),
0341 my_rng(std::move(other.my_rng)), my_head_ptr(nullptr)
0342 {
0343 using is_always_equal = typename allocator_traits_type::is_always_equal;
0344 internal_move_construct_with_allocator(std::move(other), is_always_equal());
0345 }
0346
0347 ~concurrent_skip_list() {
0348 clear();
0349 delete_head();
0350 }
0351
0352 concurrent_skip_list& operator=( const concurrent_skip_list& other ) {
0353 if (this != &other) {
0354 clear();
0355 copy_assign_allocators(my_node_allocator, other.my_node_allocator);
0356 my_compare = other.my_compare;
0357 my_rng = other.my_rng;
0358 internal_copy(other);
0359 }
0360 return *this;
0361 }
0362
0363 concurrent_skip_list& operator=( concurrent_skip_list&& other ) {
0364 if (this != &other) {
0365 clear();
0366 delete_head();
0367
0368 my_compare = std::move(other.my_compare);
0369 my_rng = std::move(other.my_rng);
0370
0371 move_assign_allocators(my_node_allocator, other.my_node_allocator);
0372 using pocma_type = typename node_allocator_traits::propagate_on_container_move_assignment;
0373 using is_always_equal = typename node_allocator_traits::is_always_equal;
0374 internal_move_assign(std::move(other), tbb::detail::disjunction<pocma_type, is_always_equal>());
0375 }
0376 return *this;
0377 }
0378
0379 concurrent_skip_list& operator=( std::initializer_list<value_type> il )
0380 {
0381 clear();
0382 insert(il.begin(),il.end());
0383 return *this;
0384 }
0385
0386 std::pair<iterator, bool> insert( const value_type& value ) {
0387 return internal_insert(value);
0388 }
0389
0390 std::pair<iterator, bool> insert( value_type&& value ) {
0391 return internal_insert(std::move(value));
0392 }
0393
0394 iterator insert( const_iterator, const_reference value ) {
0395
0396 return insert(value).first;
0397 }
0398
0399 iterator insert( const_iterator, value_type&& value ) {
0400
0401 return insert(std::move(value)).first;
0402 }
0403
0404 template<typename InputIterator>
0405 void insert( InputIterator first, InputIterator last ) {
0406 while (first != last) {
0407 insert(*first);
0408 ++first;
0409 }
0410 }
0411
0412 void insert( std::initializer_list<value_type> init ) {
0413 insert(init.begin(), init.end());
0414 }
0415
0416 std::pair<iterator, bool> insert( node_type&& nh ) {
0417 if (!nh.empty()) {
0418 auto insert_node = d1::node_handle_accessor::get_node_ptr(nh);
0419 std::pair<iterator, bool> insert_result = internal_insert_node(insert_node);
0420 if (insert_result.second) {
0421 d1::node_handle_accessor::deactivate(nh);
0422 }
0423 return insert_result;
0424 }
0425 return std::pair<iterator, bool>(end(), false);
0426 }
0427
0428 iterator insert( const_iterator, node_type&& nh ) {
0429
0430 return insert(std::move(nh)).first;
0431 }
0432
0433 template<typename... Args>
0434 std::pair<iterator, bool> emplace( Args&&... args ) {
0435 return internal_insert(std::forward<Args>(args)...);
0436 }
0437
0438 template<typename... Args>
0439 iterator emplace_hint( const_iterator, Args&&... args ) {
0440
0441 return emplace(std::forward<Args>(args)...).first;
0442 }
0443
0444 iterator unsafe_erase( iterator pos ) {
0445 std::pair<node_ptr, node_ptr> extract_result = internal_extract(pos);
0446 if (extract_result.first) {
0447 delete_value_node(extract_result.first);
0448 return extract_result.second;
0449 }
0450 return end();
0451 }
0452
0453 iterator unsafe_erase( const_iterator pos ) {
0454 return unsafe_erase(get_iterator(pos));
0455 }
0456
0457 iterator unsafe_erase( const_iterator first, const_iterator last ) {
0458 while (first != last) {
0459
0460 first = unsafe_erase(first);
0461 }
0462 return get_iterator(first);
0463 }
0464
0465 size_type unsafe_erase( const key_type& key ) {
0466 return internal_erase(key);
0467 }
0468
0469 template <typename K>
0470 typename std::enable_if<is_transparent<K>::value
0471 && !std::is_convertible<K, const_iterator>::value
0472 && !std::is_convertible<K, iterator>::value,
0473 size_type>::type unsafe_erase( const K& key )
0474 {
0475 return internal_erase(key);
0476 }
0477
0478 node_type unsafe_extract( const_iterator pos ) {
0479 std::pair<node_ptr, node_ptr> extract_result = internal_extract(pos);
0480 return extract_result.first ? d1::node_handle_accessor::construct<node_type>(extract_result.first) : node_type();
0481 }
0482
0483 node_type unsafe_extract( iterator pos ) {
0484 return unsafe_extract(const_iterator(pos));
0485 }
0486
0487 node_type unsafe_extract( const key_type& key ) {
0488 return unsafe_extract(find(key));
0489 }
0490
0491 template <typename K>
0492 typename std::enable_if<is_transparent<K>::value
0493 && !std::is_convertible<K, const_iterator>::value
0494 && !std::is_convertible<K, iterator>::value,
0495 node_type>::type unsafe_extract( const K& key )
0496 {
0497 return unsafe_extract(find(key));
0498 }
0499
0500 iterator lower_bound( const key_type& key ) {
0501 return iterator(internal_get_bound(key, my_compare));
0502 }
0503
0504 const_iterator lower_bound( const key_type& key ) const {
0505 return const_iterator(internal_get_bound(key, my_compare));
0506 }
0507
0508 template <typename K>
0509 typename std::enable_if<is_transparent<K>::value, iterator>::type lower_bound( const K& key ) {
0510 return iterator(internal_get_bound(key, my_compare));
0511 }
0512
0513 template <typename K>
0514 typename std::enable_if<is_transparent<K>::value, const_iterator>::type lower_bound( const K& key ) const {
0515 return const_iterator(internal_get_bound(key, my_compare));
0516 }
0517
0518 iterator upper_bound( const key_type& key ) {
0519 return iterator(internal_get_bound(key, not_greater_compare(my_compare)));
0520 }
0521
0522 const_iterator upper_bound( const key_type& key ) const {
0523 return const_iterator(internal_get_bound(key, not_greater_compare(my_compare)));
0524 }
0525
0526 template <typename K>
0527 typename std::enable_if<is_transparent<K>::value, iterator>::type upper_bound( const K& key ) {
0528 return iterator(internal_get_bound(key, not_greater_compare(my_compare)));
0529 }
0530
0531 template <typename K>
0532 typename std::enable_if<is_transparent<K>::value, const_iterator>::type upper_bound( const K& key ) const {
0533 return const_iterator(internal_get_bound(key, not_greater_compare(my_compare)));
0534 }
0535
0536 iterator find( const key_type& key ) {
0537 return iterator(internal_find(key));
0538 }
0539
0540 const_iterator find( const key_type& key ) const {
0541 return const_iterator(internal_find(key));
0542 }
0543
0544 template <typename K>
0545 typename std::enable_if<is_transparent<K>::value, iterator>::type find( const K& key ) {
0546 return iterator(internal_find(key));
0547 }
0548
0549 template <typename K>
0550 typename std::enable_if<is_transparent<K>::value, const_iterator>::type find( const K& key ) const {
0551 return const_iterator(internal_find(key));
0552 }
0553
0554 size_type count( const key_type& key ) const {
0555 return internal_count(key);
0556 }
0557
0558 template <typename K>
0559 typename std::enable_if<is_transparent<K>::value, size_type>::type count( const K& key ) const {
0560 return internal_count(key);
0561 }
0562
0563 bool contains( const key_type& key ) const {
0564 return find(key) != end();
0565 }
0566
0567 template <typename K>
0568 typename std::enable_if<is_transparent<K>::value, bool>::type contains( const K& key ) const {
0569 return find(key) != end();
0570 }
0571
0572 void clear() noexcept {
0573
0574 node_ptr head = my_head_ptr.load(std::memory_order_relaxed);
0575
0576 if (head == nullptr) return;
0577
0578 node_ptr current = head->next(0);
0579
0580
0581 while (current) {
0582 node_ptr next = current->next(0);
0583 delete_value_node(current);
0584 current = next;
0585 }
0586
0587 for (size_type level = 0; level < head->height(); ++level) {
0588 head->set_next(level, nullptr);
0589 }
0590
0591 my_size.store(0, std::memory_order_relaxed);
0592 my_max_height.store(0, std::memory_order_relaxed);
0593 }
0594
0595 iterator begin() {
0596 return iterator(internal_begin());
0597 }
0598
0599 const_iterator begin() const {
0600 return const_iterator(internal_begin());
0601 }
0602
0603 const_iterator cbegin() const {
0604 return const_iterator(internal_begin());
0605 }
0606
0607 iterator end() {
0608 return iterator(nullptr);
0609 }
0610
0611 const_iterator end() const {
0612 return const_iterator(nullptr);
0613 }
0614
0615 const_iterator cend() const {
0616 return const_iterator(nullptr);
0617 }
0618
0619 size_type size() const {
0620 return my_size.load(std::memory_order_relaxed);
0621 }
0622
0623 size_type max_size() const {
0624 return node_allocator_traits::max_size(my_node_allocator);
0625 }
0626
0627 __TBB_nodiscard bool empty() const {
0628 return 0 == size();
0629 }
0630
0631 allocator_type get_allocator() const {
0632 return my_node_allocator;
0633 }
0634
0635 void swap(concurrent_skip_list& other) {
0636 if (this != &other) {
0637 using pocs_type = typename node_allocator_traits::propagate_on_container_swap;
0638 using is_always_equal = typename node_allocator_traits::is_always_equal;
0639 internal_swap(other, tbb::detail::disjunction<pocs_type, is_always_equal>());
0640 }
0641 }
0642
0643 std::pair<iterator, iterator> equal_range(const key_type& key) {
0644 return internal_equal_range(key);
0645 }
0646
0647 std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const {
0648 return internal_equal_range(key);
0649 }
0650
0651 template <typename K>
0652 typename std::enable_if<is_transparent<K>::value, std::pair<iterator, iterator>>::type equal_range( const K& key ) {
0653 return internal_equal_range(key);
0654 }
0655
0656 template <typename K>
0657 typename std::enable_if<is_transparent<K>::value, std::pair<const_iterator, const_iterator>>::type equal_range( const K& key ) const {
0658 return internal_equal_range(key);
0659 }
0660
0661 key_compare key_comp() const { return my_compare; }
0662
0663 value_compare value_comp() const { return container_traits::value_comp(my_compare); }
0664
0665 class const_range_type {
0666 public:
0667 using size_type = typename concurrent_skip_list::size_type;
0668 using difference_type = typename concurrent_skip_list::difference_type;
0669 using iterator = typename concurrent_skip_list::const_iterator;
0670 using value_type = typename iterator::value_type;
0671 using reference = typename iterator::reference;
0672
0673 bool empty() const {
0674 return my_begin.my_node_ptr ? (my_begin.my_node_ptr->next(0) == my_end.my_node_ptr)
0675 : true;
0676 }
0677
0678 bool is_divisible() const {
0679 return my_begin.my_node_ptr && my_level != 0
0680 ? my_begin.my_node_ptr->next(my_level - 1) != my_end.my_node_ptr
0681 : false;
0682 }
0683
0684 size_type size() const { return std::distance(my_begin, my_end); }
0685
0686 const_range_type( const_range_type& r, split)
0687 : my_end(r.my_end) {
0688 if (r.empty()) {
0689 __TBB_ASSERT(my_end.my_node_ptr == nullptr, nullptr);
0690 my_begin = my_end;
0691 my_level = 0;
0692 } else {
0693 my_begin = iterator(r.my_begin.my_node_ptr->next(r.my_level - 1));
0694 my_level = my_begin.my_node_ptr->height();
0695 }
0696 r.my_end = my_begin;
0697 }
0698
0699 const_range_type( const concurrent_skip_list& l)
0700 : my_end(l.end()), my_begin(l.begin()),
0701 my_level(my_begin.my_node_ptr ? my_begin.my_node_ptr->height() : 0) {}
0702
0703 iterator begin() const { return my_begin; }
0704 iterator end() const { return my_end; }
0705 size_type grainsize() const { return 1; }
0706
0707 private:
0708 const_iterator my_end;
0709 const_iterator my_begin;
0710 size_type my_level;
0711 };
0712
0713 class range_type : public const_range_type {
0714 public:
0715 using iterator = typename concurrent_skip_list::iterator;
0716 using value_type = typename iterator::value_type;
0717 using reference = typename iterator::reference;
0718
0719 range_type(range_type& r, split) : const_range_type(r, split()) {}
0720 range_type(const concurrent_skip_list& l) : const_range_type(l) {}
0721
0722 iterator begin() const {
0723 node_ptr node = const_range_type::begin().my_node_ptr;
0724 return iterator(node);
0725 }
0726
0727 iterator end() const {
0728 node_ptr node = const_range_type::end().my_node_ptr;
0729 return iterator(node);
0730 }
0731 };
0732
0733 range_type range() { return range_type(*this); }
0734 const_range_type range() const { return const_range_type(*this); }
0735
0736 private:
0737 node_ptr internal_begin() const {
0738 node_ptr head = get_head();
0739 return head == nullptr ? head : head->next(0);
0740 }
0741
0742 void internal_move(concurrent_skip_list&& other) {
0743 my_head_ptr.store(other.my_head_ptr.load(std::memory_order_relaxed), std::memory_order_relaxed);
0744 other.my_head_ptr.store(nullptr, std::memory_order_relaxed);
0745
0746 my_size.store(other.my_size.load(std::memory_order_relaxed), std::memory_order_relaxed);
0747 other.my_size.store(0, std::memory_order_relaxed);
0748
0749 my_max_height.store(other.my_max_height.load(std::memory_order_relaxed), std::memory_order_relaxed);
0750 other.my_max_height.store(0, std::memory_order_relaxed);
0751 }
0752
0753 void internal_move_construct_with_allocator(concurrent_skip_list&& other,
0754 std::true_type) {
0755 internal_move(std::move(other));
0756 }
0757
0758 void internal_move_construct_with_allocator(concurrent_skip_list&& other,
0759 std::false_type) {
0760 if (my_node_allocator == other.get_allocator()) {
0761 internal_move(std::move(other));
0762 } else {
0763 my_size.store(0, std::memory_order_relaxed);
0764 my_max_height.store(other.my_max_height.load(std::memory_order_relaxed), std::memory_order_relaxed);
0765 internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()));
0766 }
0767 }
0768
0769 static const key_type& get_key( node_ptr n ) {
0770 __TBB_ASSERT(n, nullptr);
0771 return container_traits::get_key(static_cast<node_ptr>(n)->value());
0772 }
0773
0774 template <typename K>
0775 bool found( node_ptr node, const K& key ) const {
0776 return node != nullptr && !my_compare(key, get_key(node));
0777 }
0778
0779 template <typename K>
0780 node_ptr internal_find(const K& key) const {
0781 return allow_multimapping ? internal_find_multi(key) : internal_find_unique(key);
0782 }
0783
0784 template <typename K>
0785 node_ptr internal_find_multi( const K& key ) const {
0786 node_ptr prev = get_head();
0787 if (prev == nullptr) return nullptr;
0788
0789 node_ptr curr = nullptr;
0790 node_ptr old_curr = curr;
0791
0792 for (size_type h = my_max_height.load(std::memory_order_acquire); h > 0; --h) {
0793 curr = internal_find_position(h - 1, prev, key, my_compare);
0794
0795 if (curr != old_curr && found(curr, key)) {
0796 return curr;
0797 }
0798 old_curr = curr;
0799 }
0800 return nullptr;
0801 }
0802
0803 template <typename K>
0804 node_ptr internal_find_unique( const K& key ) const {
0805 const_iterator it = lower_bound(key);
0806 return (it == end() || my_compare(key, container_traits::get_key(*it))) ? nullptr : it.my_node_ptr;
0807 }
0808
0809 template <typename K>
0810 size_type internal_count( const K& key ) const {
0811 if (allow_multimapping) {
0812
0813 std::pair<const_iterator, const_iterator> r = equal_range(key);
0814 return std::distance(r.first, r.second);
0815 }
0816 return size_type(contains(key) ? 1 : 0);
0817 }
0818
0819 template <typename K>
0820 std::pair<iterator, iterator> internal_equal_range(const K& key) const {
0821 iterator lb = get_iterator(lower_bound(key));
0822 auto result = std::make_pair(lb, lb);
0823
0824
0825 if (found(lb.my_node_ptr, key)) {
0826
0827 if (!allow_multimapping) {
0828
0829 ++result.second;
0830 } else {
0831
0832 node_ptr prev = lb.my_node_ptr;
0833 node_ptr curr = nullptr;
0834 not_greater_compare cmp(my_compare);
0835
0836
0837 for (size_type h = prev->height(); h > 0; --h) {
0838 curr = prev->next(h - 1);
0839 while (curr && cmp(get_key(curr), key)) {
0840 prev = curr;
0841
0842 if (h < curr->height()) {
0843 h = curr->height();
0844 }
0845 curr = prev->next(h - 1);
0846 }
0847 }
0848 result.second = iterator(curr);
0849 }
0850 }
0851
0852 return result;
0853 }
0854
0855
0856 template <typename K, typename Comparator>
0857 node_ptr internal_find_position( size_type level, node_ptr& prev, const K& key,
0858 const Comparator& cmp ) const {
0859 __TBB_ASSERT(level < prev->height(), "Wrong level to find position");
0860 node_ptr curr = prev->next(level);
0861
0862 while (curr && cmp(get_key(curr), key)) {
0863 prev = curr;
0864 __TBB_ASSERT(level < prev->height(), nullptr);
0865 curr = prev->next(level);
0866 }
0867
0868 return curr;
0869 }
0870
0871
0872 template <typename Comparator>
0873 node_ptr internal_find_position( size_type level, node_ptr& prev, node_ptr node,
0874 const Comparator& cmp ) const {
0875 __TBB_ASSERT(level < prev->height(), "Wrong level to find position");
0876 node_ptr curr = prev->next(level);
0877
0878 while (curr && cmp(get_key(curr), get_key(node))) {
0879 if (allow_multimapping && cmp(get_key(node), get_key(curr)) && curr->index_number() > node->index_number()) {
0880 break;
0881 }
0882
0883 prev = curr;
0884 __TBB_ASSERT(level < prev->height(), nullptr);
0885 curr = prev->next(level);
0886 }
0887 return curr;
0888 }
0889
0890 template <typename Comparator>
0891 void fill_prev_curr_arrays(array_type& prev_nodes, array_type& curr_nodes, node_ptr node, const key_type& key,
0892 const Comparator& cmp, node_ptr head ) {
0893
0894 size_type curr_max_height = my_max_height.load(std::memory_order_acquire);
0895 size_type node_height = node->height();
0896 if (curr_max_height < node_height) {
0897 std::fill(prev_nodes.begin() + curr_max_height, prev_nodes.begin() + node_height, head);
0898 std::fill(curr_nodes.begin() + curr_max_height, curr_nodes.begin() + node_height, nullptr);
0899 }
0900
0901 node_ptr prev = head;
0902 for (size_type level = curr_max_height; level > 0; --level) {
0903 node_ptr curr = internal_find_position(level - 1, prev, key, cmp);
0904 prev_nodes[level - 1] = prev;
0905 curr_nodes[level - 1] = curr;
0906 }
0907 }
0908
0909 void fill_prev_array_for_existing_node( array_type& prev_nodes, node_ptr node ) {
0910 node_ptr head = create_head_if_necessary();
0911 prev_nodes.fill(head);
0912
0913 node_ptr prev = head;
0914 for (size_type level = node->height(); level > 0; --level) {
0915 while (prev->next(level - 1) != node) {
0916 prev = prev->next(level - 1);
0917 }
0918 prev_nodes[level - 1] = prev;
0919 }
0920 }
0921
0922 struct not_greater_compare {
0923 const key_compare& my_less_compare;
0924
0925 not_greater_compare( const key_compare& less_compare ) : my_less_compare(less_compare) {}
0926
0927 template <typename K1, typename K2>
0928 bool operator()( const K1& first, const K2& second ) const {
0929 return !my_less_compare(second, first);
0930 }
0931 };
0932
0933 not_greater_compare select_comparator( std::true_type ) {
0934 return not_greater_compare(my_compare);
0935 }
0936
0937 key_compare select_comparator( std::false_type ) {
0938 return my_compare;
0939 }
0940
0941 template<typename... Args>
0942 std::pair<iterator, bool> internal_insert( Args&&... args ) {
0943 node_ptr new_node = create_value_node(std::forward<Args>(args)...);
0944 std::pair<iterator, bool> insert_result = internal_insert_node(new_node);
0945 if (!insert_result.second) {
0946 delete_value_node(new_node);
0947 }
0948 return insert_result;
0949 }
0950
0951 std::pair<iterator, bool> internal_insert_node( node_ptr new_node ) {
0952 array_type prev_nodes;
0953 array_type curr_nodes;
0954 size_type new_height = new_node->height();
0955 auto compare = select_comparator(std::integral_constant<bool, allow_multimapping>{});
0956
0957 node_ptr head_node = create_head_if_necessary();
0958
0959 for (;;) {
0960 fill_prev_curr_arrays(prev_nodes, curr_nodes, new_node, get_key(new_node), compare, head_node);
0961
0962 node_ptr prev = prev_nodes[0];
0963 node_ptr next = curr_nodes[0];
0964
0965 if (allow_multimapping) {
0966 new_node->set_index_number(prev->index_number() + 1);
0967 } else {
0968 if (found(next, get_key(new_node))) {
0969 return std::pair<iterator, bool>(iterator(next), false);
0970 }
0971 }
0972
0973 new_node->set_next(0, next);
0974 if (!prev->atomic_next(0).compare_exchange_strong(next, new_node)) {
0975 continue;
0976 }
0977
0978
0979
0980
0981
0982 size_type max_height = my_max_height.load(std::memory_order_acquire);
0983 for (;;) {
0984 if (new_height <= max_height || my_max_height.compare_exchange_strong(max_height, new_height)) {
0985
0986
0987 break;
0988 }
0989 }
0990
0991 for (std::size_t level = 1; level < new_height; ++level) {
0992
0993 for (;;) {
0994 prev = prev_nodes[level];
0995 next = static_cast<node_ptr>(curr_nodes[level]);
0996
0997 new_node->set_next(level, next);
0998 __TBB_ASSERT(new_node->height() > level, "Internal structure break");
0999 if (prev->atomic_next(level).compare_exchange_strong(next, new_node)) {
1000 break;
1001 }
1002
1003 for (size_type lev = level; lev != new_height; ++lev ) {
1004 curr_nodes[lev] = internal_find_position(lev, prev_nodes[lev], new_node, compare);
1005 }
1006 }
1007 }
1008 ++my_size;
1009 return std::pair<iterator, bool>(iterator(new_node), true);
1010 }
1011 }
1012
1013 template <typename K, typename Comparator>
1014 node_ptr internal_get_bound( const K& key, const Comparator& cmp ) const {
1015 node_ptr prev = get_head();
1016 if (prev == nullptr) return nullptr;
1017
1018 node_ptr curr = nullptr;
1019
1020 for (size_type h = my_max_height.load(std::memory_order_acquire); h > 0; --h) {
1021 curr = internal_find_position(h - 1, prev, key, cmp);
1022 }
1023
1024 return curr;
1025 }
1026
1027 template <typename K>
1028 size_type internal_erase( const K& key ) {
1029 auto eq = equal_range(key);
1030 size_type old_size = size();
1031 unsafe_erase(eq.first, eq.second);
1032 return old_size - size();
1033 }
1034
1035
1036 std::pair<node_ptr, node_ptr> internal_extract( const_iterator it ) {
1037 std::pair<node_ptr, node_ptr> result(nullptr, nullptr);
1038 if ( it != end() ) {
1039 array_type prev_nodes;
1040
1041 node_ptr erase_node = it.my_node_ptr;
1042 node_ptr next_node = erase_node->next(0);
1043 fill_prev_array_for_existing_node(prev_nodes, erase_node);
1044
1045 for (size_type level = 0; level < erase_node->height(); ++level) {
1046 prev_nodes[level]->set_next(level, erase_node->next(level));
1047 erase_node->set_next(level, nullptr);
1048 }
1049 my_size.fetch_sub(1, std::memory_order_relaxed);
1050
1051 result.first = erase_node;
1052 result.second = next_node;
1053 }
1054 return result;
1055 }
1056
1057 protected:
1058 template<typename SourceType>
1059 void internal_merge( SourceType&& source ) {
1060 using source_type = typename std::decay<SourceType>::type;
1061 using source_iterator = typename source_type::iterator;
1062 static_assert((std::is_same<node_type, typename source_type::node_type>::value), "Incompatible containers cannot be merged");
1063
1064 for (source_iterator it = source.begin(); it != source.end();) {
1065 source_iterator where = it++;
1066 if (allow_multimapping || !contains(container_traits::get_key(*where))) {
1067 node_type handle = source.unsafe_extract(where);
1068 __TBB_ASSERT(!handle.empty(), "Extracted handle in merge is empty");
1069
1070 if (!insert(std::move(handle)).second) {
1071 __TBB_ASSERT(!handle.empty(), "Handle should not be empty if insert fails");
1072
1073 source.insert(std::move(handle));
1074 }
1075 __TBB_ASSERT(handle.empty(), "Node handle should be empty after the insertion");
1076 }
1077 }
1078 }
1079
1080 private:
1081 void internal_copy( const concurrent_skip_list& other ) {
1082 internal_copy(other.begin(), other.end());
1083 }
1084
1085 template<typename Iterator>
1086 void internal_copy( Iterator first, Iterator last ) {
1087 try_call([&] {
1088 for (auto it = first; it != last; ++it) {
1089 insert(*it);
1090 }
1091 }).on_exception([&] {
1092 clear();
1093 delete_head();
1094 });
1095 }
1096
1097 node_ptr create_node( size_type height ) {
1098 return list_node_type::create(my_node_allocator, height);
1099 }
1100
1101 template <typename... Args>
1102 node_ptr create_value_node( Args&&... args ) {
1103 node_ptr node = create_node(my_rng());
1104
1105
1106
1107 auto value_guard = make_raii_guard([&] {
1108 delete_node(node);
1109 });
1110
1111
1112 node_allocator_traits::construct(my_node_allocator, node->storage(), std::forward<Args>(args)...);
1113 value_guard.dismiss();
1114 return node;
1115 }
1116
1117 node_ptr create_head_node() {
1118 return create_node(max_level);
1119 }
1120
1121 void delete_head() {
1122 node_ptr head = my_head_ptr.load(std::memory_order_relaxed);
1123 if (head != nullptr) {
1124 delete_node(head);
1125 my_head_ptr.store(nullptr, std::memory_order_relaxed);
1126 }
1127 }
1128
1129 void delete_node( node_ptr node ) {
1130 list_node_type::destroy(my_node_allocator, node);
1131 }
1132
1133 void delete_value_node( node_ptr node ) {
1134
1135 node_allocator_traits::destroy(my_node_allocator, node->storage());
1136 delete_node(node);
1137 }
1138
1139 node_ptr get_head() const {
1140 return my_head_ptr.load(std::memory_order_acquire);
1141 }
1142
1143 node_ptr create_head_if_necessary() {
1144 node_ptr current_head = get_head();
1145 if (current_head == nullptr) {
1146
1147 node_ptr new_head = create_head_node();
1148 if (my_head_ptr.compare_exchange_strong(current_head, new_head)) {
1149 current_head = new_head;
1150 } else {
1151
1152
1153 delete_node(new_head);
1154 }
1155 }
1156 __TBB_ASSERT(my_head_ptr.load(std::memory_order_relaxed) != nullptr, nullptr);
1157 __TBB_ASSERT(current_head != nullptr, nullptr);
1158 return current_head;
1159 }
1160
1161 static iterator get_iterator( const_iterator it ) {
1162 return iterator(it.my_node_ptr);
1163 }
1164
1165 void internal_move_assign( concurrent_skip_list&& other, std::true_type ) {
1166 internal_move(std::move(other));
1167 }
1168
1169 void internal_move_assign( concurrent_skip_list&& other, std::false_type ) {
1170 if (my_node_allocator == other.my_node_allocator) {
1171 internal_move(std::move(other));
1172 } else {
1173 internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()));
1174 }
1175 }
1176
1177 void internal_swap_fields( concurrent_skip_list& other ) {
1178 using std::swap;
1179 swap_allocators(my_node_allocator, other.my_node_allocator);
1180 swap(my_compare, other.my_compare);
1181 swap(my_rng, other.my_rng);
1182
1183 swap_atomics_relaxed(my_head_ptr, other.my_head_ptr);
1184 swap_atomics_relaxed(my_size, other.my_size);
1185 swap_atomics_relaxed(my_max_height, other.my_max_height);
1186 }
1187
1188 void internal_swap( concurrent_skip_list& other, std::true_type ) {
1189 internal_swap_fields(other);
1190 }
1191
1192 void internal_swap( concurrent_skip_list& other, std::false_type ) {
1193 __TBB_ASSERT(my_node_allocator == other.my_node_allocator, "Swapping with unequal allocators is not allowed");
1194 internal_swap_fields(other);
1195 }
1196
1197 node_allocator_type my_node_allocator;
1198 key_compare my_compare;
1199 random_level_generator_type my_rng;
1200 std::atomic<list_node_type*> my_head_ptr;
1201 std::atomic<size_type> my_size;
1202 std::atomic<size_type> my_max_height;
1203
1204 template<typename OtherTraits>
1205 friend class concurrent_skip_list;
1206 };
1207
1208 template <typename Traits>
1209 bool operator==( const concurrent_skip_list<Traits>& lhs, const concurrent_skip_list<Traits>& rhs ) {
1210 if (lhs.size() != rhs.size()) return false;
1211 #if _MSC_VER
1212
1213
1214
1215
1216 return std::equal(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
1217 #else
1218 return std::equal(lhs.begin(), lhs.end(), rhs.begin());
1219 #endif
1220 }
1221
1222 #if !__TBB_CPP20_COMPARISONS_PRESENT
1223 template <typename Traits>
1224 bool operator!=( const concurrent_skip_list<Traits>& lhs, const concurrent_skip_list<Traits>& rhs ) {
1225 return !(lhs == rhs);
1226 }
1227 #endif
1228
1229 #if __TBB_CPP20_COMPARISONS_PRESENT && __TBB_CPP20_CONCEPTS_PRESENT
1230 template <typename Traits>
1231 tbb::detail::synthesized_three_way_result<typename Traits::value_type>
1232 operator<=>( const concurrent_skip_list<Traits>& lhs, const concurrent_skip_list<Traits>& rhs ) {
1233 return std::lexicographical_compare_three_way(lhs.begin(), lhs.end(),
1234 rhs.begin(), rhs.end(),
1235 tbb::detail::synthesized_three_way_comparator{});
1236 }
1237 #else
1238 template <typename Traits>
1239 bool operator<( const concurrent_skip_list<Traits>& lhs, const concurrent_skip_list<Traits>& rhs ) {
1240 return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end());
1241 }
1242
1243 template <typename Traits>
1244 bool operator>( const concurrent_skip_list<Traits>& lhs, const concurrent_skip_list<Traits>& rhs ) {
1245 return rhs < lhs;
1246 }
1247
1248 template <typename Traits>
1249 bool operator<=( const concurrent_skip_list<Traits>& lhs, const concurrent_skip_list<Traits>& rhs ) {
1250 return !(rhs < lhs);
1251 }
1252
1253 template <typename Traits>
1254 bool operator>=( const concurrent_skip_list<Traits>& lhs, const concurrent_skip_list<Traits>& rhs ) {
1255 return !(lhs < rhs);
1256 }
1257 #endif
1258
1259
1260 template <std::size_t MaxLevel>
1261 class concurrent_geometric_level_generator {
1262 public:
1263 static constexpr std::size_t max_level = MaxLevel;
1264
1265 static_assert(max_level == 32, "Incompatible max_level for rng");
1266
1267 concurrent_geometric_level_generator() : engines(std::minstd_rand::result_type(time(nullptr))) {}
1268
1269 std::size_t operator()() {
1270
1271
1272 std::size_t result = max_level - std::size_t(tbb::detail::log2(engines.local()() + 1)) - 1;
1273 __TBB_ASSERT(result <= max_level, nullptr);
1274 return result;
1275 }
1276
1277 private:
1278 tbb::enumerable_thread_specific<std::minstd_rand> engines;
1279 };
1280
1281 }
1282
1283 }
1284 }
1285
1286 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
1287 #pragma warning(pop)
1288 #endif
1289
1290 #endif