Back to home page

EIC code displayed by LXR

 
 

    


File indexing completed on 2025-07-30 08:46:15

0001 /*
0002     Copyright (c) 2019-2022 Intel Corporation
0003 
0004     Licensed under the Apache License, Version 2.0 (the "License");
0005     you may not use this file except in compliance with the License.
0006     You may obtain a copy of the License at
0007 
0008         http://www.apache.org/licenses/LICENSE-2.0
0009 
0010     Unless required by applicable law or agreed to in writing, software
0011     distributed under the License is distributed on an "AS IS" BASIS,
0012     WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
0013     See the License for the specific language governing permissions and
0014     limitations under the License.
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) // warning C4127: conditional expression is constant
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     // Allocator is the same as the container allocator=> allocates unitptr_t
0069     // It is required to rebind it to value_type to get the correct pointer and const_pointer
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     //In perfect world these constructor and destructor would have been private,
0076     //however this seems technically impractical due to use of allocator_traits.
0077 
0078     //Should not be called directly, instead use create method
0079     skip_list_node( size_type levels )
0080         : my_height(levels), my_index_number(0)
0081     {}
0082 
0083     //Should not be called directly, instead use destroy method
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         //Construct the node itself
0097         allocator_traits::construct(alloc, node, height);
0098 
0099         //Construct the level pointers
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         //Destroy the level pointers
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         // Destroy the node itself
0114         allocator_traits::destroy(alloc, node);
0115 
0116         // Deallocate the node
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 }; // class skip_list_node
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 }; // class skip_list_iterator
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) // my_head_ptr would be stored in internal_move
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         // Ignore hint
0396         return insert(value).first;
0397     }
0398 
0399     iterator insert( const_iterator, value_type&& value ) {
0400         // Ignore hint
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         // Ignore hint
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         // Ignore hint
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) { // node was extracted
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             // Unsafe erase returns the iterator which follows the erased one
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         // clear is not thread safe - load can be relaxed
0574         node_ptr head = my_head_ptr.load(std::memory_order_relaxed);
0575 
0576         if (head == nullptr) return; // Head is not allocated => container is empty
0577 
0578         node_ptr current = head->next(0);
0579 
0580         // Delete all value nodes in the container
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     }; // class const_range_type
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     }; // class range_type
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                                                 /*is_always_equal = */std::true_type) {
0755         internal_move(std::move(other));
0756     }
0757 
0758     void internal_move_construct_with_allocator(concurrent_skip_list&& other,
0759                                                 /*is_always_equal = */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; // If the head node is not allocated - exit
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             // TODO: reimplement without double traversal
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         // If the lower bound points to the node with the requested key
0825         if (found(lb.my_node_ptr, key)) {
0826 
0827             if (!allow_multimapping) {
0828                 // For unique containers - move the second iterator forward and exit
0829                 ++result.second;
0830             } else {
0831                 // For multi containers - find the upper bound starting from the lower bound
0832                 node_ptr prev = lb.my_node_ptr;
0833                 node_ptr curr = nullptr;
0834                 not_greater_compare cmp(my_compare);
0835 
0836                 // Start from the lower bound of the range
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                         // If the height of the next node is greater than the current one - jump to its height
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     // Finds position on the level using comparator cmp starting from the node prev
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     // The same as previous overload, but allows index_number comparison
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( /*allow_multimapping = */ std::true_type ) {
0934         return not_greater_compare(my_compare);
0935     }
0936 
0937     key_compare select_comparator( /*allow_multimapping = */ 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             // If the node was successfully linked on the first level - it will be linked on other levels
0979             // Insertion cannot fail starting from this point
0980 
0981             // If the height of inserted node is greater than maximum - increase maximum
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                     // If the maximum was successfully updated by current thread
0986                     // or by an other thread for the value, greater or equal to new_height
0987                     break;
0988                 }
0989             }
0990 
0991             for (std::size_t level = 1; level < new_height; ++level) {
0992                 // Link the node on upper levels
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; // If the head node is not allocated - exit
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     // Returns node_ptr to the extracted node and node_ptr to the next node after the extracted
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                     //If the insertion fails - return the node into source
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         // try_call API is not convenient here due to broken
1106         // variadic capture on GCC 4.8.5
1107         auto value_guard = make_raii_guard([&] {
1108             delete_node(node);
1109         });
1110 
1111         // Construct the value inside the node
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         // Destroy the value inside the node
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             // Head node was not created - create it
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                 // If an other thread has already created the head node - destroy new_head
1152                 // current_head now points to the actual head node
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, /*POCMA || is_always_equal =*/std::true_type ) {
1166         internal_move(std::move(other));
1167     }
1168 
1169     void internal_move_assign( concurrent_skip_list&& other, /*POCMA || is_always_equal =*/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, /*POCMA || is_always_equal =*/std::true_type ) {
1189         internal_swap_fields(other);
1190     }
1191 
1192     void internal_swap( concurrent_skip_list& other, /*POCMA || is_always_equal =*/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 }; // class concurrent_skip_list
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     // Passing "unchecked" iterators to std::equal with 3 parameters
1213     // causes compiler warnings.
1214     // The workaround is to use overload with 4 parameters, which is
1215     // available since C++14 - minimally supported version on MSVC
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 // __TBB_CPP20_COMPARISONS_PRESENT && __TBB_CPP20_CONCEPTS_PRESENT
1258 
1259 // Generates a number from the interval [0, MaxLevel).
1260 template <std::size_t MaxLevel>
1261 class concurrent_geometric_level_generator {
1262 public:
1263     static constexpr std::size_t max_level = MaxLevel;
1264     // TODO: modify the algorithm to accept other values of max_level
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         // +1 is required to pass at least 1 into log2 (log2(0) is undefined)
1271         // -1 is required to have an ability to return 0 from the generator (max_level - log2(2^31) - 1)
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 } // namespace d2
1282 
1283 } // namespace detail
1284 } // namespace tbb
1285 
1286 #if defined(_MSC_VER) && !defined(__INTEL_COMPILER)
1287 #pragma warning(pop) // warning 4127 is back
1288 #endif
1289 
1290 #endif // __TBB_detail__concurrent_skip_list_H