17 #ifndef __TBB_concurrent_skip_list_H 18 #define __TBB_concurrent_skip_list_H 20 #if !defined(__TBB_concurrent_map_H) && !defined(__TBB_concurrent_set_H) 21 #error Do not #include this internal file directly; use public TBB headers instead. 24 #include "../tbb_config.h" 25 #include "../tbb_stddef.h" 26 #include "../tbb_allocator.h" 27 #include "../spin_mutex.h" 28 #include "../tbb_exception.h" 29 #include "../enumerable_thread_specific.h" 35 #include <initializer_list> 41 #include <type_traits> 47 #pragma warning(disable: 4189) // warning 4189 -- local variable is initialized but not referenced 48 #pragma warning(disable: 4127) // warning 4127 -- while (true) has a constant expression in it 52 namespace interface10 {
55 template <
typename Value,
typename Mutex>
143 template <
typename NodeType,
bool is_const>
151 using pointer =
typename std::conditional<is_const,
typename node_type::const_pointer,
153 using reference =
typename std::conditional<is_const,
typename node_type::const_reference,
174 my_node_ptr = my_node_ptr->next(0);
189 template <
typename Traits>
194 friend class const_range;
197 template <
typename T,
bool M,
bool U>
200 template <
typename T,
bool M,
bool U>
204 template <
typename NodeType,
bool is_const1,
bool is_const2>
209 template <
typename NodeType,
bool is_const1,
bool is_const2>
214 template <
typename Traits>
234 using pointer =
typename allocator_traits_type::pointer;
240 using node_allocator_type =
typename std::allocator_traits<allocator_type>::template rebind_alloc<uint8_t>;
244 static constexpr
size_type MAX_LEVEL = traits_type::MAX_LEVEL;
247 using lock_array = std::array<typename list_node_type::lock_type, MAX_LEVEL>;
250 static bool const allow_multimapping = traits_type::allow_multimapping;
260 : my_node_allocator(alloc), my_compare(comp), my_size(0)
265 template<
class InputIt>
268 : my_node_allocator(alloc), my_compare(comp), my_size(0)
271 internal_copy(first, last);
276 : my_node_allocator(
node_allocator_traits::select_on_container_copy_construction(other.get_allocator())),
277 my_compare(other.my_compare), my_rnd_generator(other.my_rnd_generator), my_size(0)
280 internal_copy(other);
285 : my_node_allocator(alloc), my_compare(other.my_compare),
286 my_rnd_generator(other.my_rnd_generator), my_size(0)
289 internal_copy(other);
294 : my_node_allocator(
std::
move(other.my_node_allocator)), my_compare(other.my_compare),
295 my_rnd_generator(other.my_rnd_generator)
301 : my_node_allocator(alloc), my_compare(other.my_compare),
302 my_rnd_generator(other.my_rnd_generator)
304 if (alloc == other.get_allocator()) {
309 internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()));
319 if (
this != &other) {
320 using pocca_type =
typename node_allocator_traits::propagate_on_container_copy_assignment;
325 internal_copy(other);
331 if (
this != &other) {
332 using pocma_type =
typename node_allocator_traits::propagate_on_container_move_assignment;
334 my_compare = other.my_compare;
335 my_rnd_generator = other.my_rnd_generator;
336 internal_move_assign(
std::move(other), pocma_type());
344 insert(il.begin(),il.end());
349 return internal_insert(value);
358 return insert(value).first;
366 template<
typename InputIterator>
367 void insert(InputIterator first, InputIterator last) {
368 for (InputIterator it = first; it !=
last; ++it)
372 void insert(std::initializer_list<value_type> init) {
373 insert(init.begin(), init.end());
378 std::pair<iterator, bool> insert_result = internal_insert_node(nh.my_node);
379 if(insert_result.second) {
382 return insert_result;
384 return std::pair<iterator, bool>(
end(),
false);
392 template<
typename... Args >
393 std::pair<iterator, bool>
emplace(Args&&... args) {
394 return internal_insert(std::forward<Args>(args)...);
397 template<
typename... Args>
400 return emplace(std::forward<Args>(args)...).first;
404 std::pair<node_ptr, node_ptr> extract_result = internal_extract(pos);
405 if(extract_result.first) {
406 delete_node(extract_result.first);
407 return extract_result.second;
413 while(first != last) {
414 first = unsafe_erase(get_iterator(first));
416 return get_iterator(first);
420 std::pair<iterator, iterator> range = equal_range(key);
421 size_type sz = std::distance(range.first, range.second);
422 unsafe_erase(range.first, range.second);
427 std::pair<node_ptr, node_ptr> extract_result = internal_extract(pos);
432 return unsafe_extract(find(key));
436 return internal_get_bound(key, my_compare);
440 return internal_get_bound(key, my_compare);
445 return internal_get_bound(key, my_compare);
450 return internal_get_bound(key, my_compare);
472 return internal_find(key);
476 return internal_find(key);
481 return internal_find(key);
486 return internal_find(key);
490 return internal_count(key);
495 return internal_count(key);
499 return find(key) !=
end();
504 return find(key) !=
end();
514 delete_node(current);
519 for (
size_type i = 0; i < dummy_head->height(); ++i) {
525 return iterator(dummy_head->next(0));
553 return my_node_allocator.max_size();
561 return my_node_allocator;
566 using pocs_type =
typename node_allocator_traits::propagate_on_container_swap;
578 return std::pair<iterator, iterator>(lower_bound(key), upper_bound(key));
582 return std::pair<const_iterator, const_iterator>(lower_bound(key), upper_bound(key));
587 return std::pair<iterator, iterator>(lower_bound(key), upper_bound(key));
590 template<typename K, typename = typename std::enable_if<tbb::internal::has_is_transparent<key_compare>::value, K>
::type>
592 return std::pair<const_iterator, const_iterator>(lower_bound(key), upper_bound(key));
629 : my_end(l.
end()), my_begin(l.
begin()), my_level(my_begin.my_node_ptr->
height() ) {}
659 dummy_head = other.dummy_head;
660 other.dummy_head =
nullptr;
661 other.create_dummy_head();
663 my_size = other.my_size.load();
669 return traits_type::get_key(n->
value());
672 template <
typename K>
675 return (it ==
end() || my_compare(key, traits_type::get_key(*it))) ?
end() : it;
678 template <
typename K>
681 return (it ==
end() || my_compare(key, traits_type::get_key(*it))) ?
end() : it;
684 template <
typename K>
686 if (allow_multimapping) {
687 std::pair<const_iterator, const_iterator> range = equal_range(key);
688 return std::distance(range.first, range.second);
702 template <
typename K,
typename po
inter_type,
typename comparator>
704 const comparator& cmp)
const {
706 pointer_type curr = prev->next(level);
708 while (curr && cmp(get_key(curr), key)) {
711 curr = prev->next(level);
717 template <
typename comparator>
719 const comparator& cmp) {
720 prev_nodes.fill(dummy_head);
721 next_nodes.fill(
nullptr);
724 node_ptr next = internal_find_position(
h - 1, prev, key, cmp);
725 prev_nodes[
h - 1] = prev;
726 next_nodes[
h - 1] =
next;
730 template<
typename... Args>
732 node_ptr new_node = create_node(std::forward<Args>(args)...);
733 std::pair<iterator, bool> insert_result = internal_insert_node(new_node);
734 if(!insert_result.second) {
735 delete_node(new_node);
737 return insert_result;
743 __TBB_ASSERT(dummy_head->height() >= new_node->
height(),
"Wrong height for new node");
746 if (allow_multimapping) {
747 fill_prev_next_arrays(prev_nodes, next_nodes, dummy_head, get_key(new_node),
750 fill_prev_next_arrays(prev_nodes, next_nodes, dummy_head, get_key(new_node), my_compare);
754 if (next && !allow_multimapping && !my_compare(get_key(new_node), get_key(next))) {
760 return std::pair<iterator, bool>(
iterator(next),
false);
762 __TBB_ASSERT(allow_multimapping || !next || my_compare(get_key(new_node), get_key(next)),
763 "Wrong elements order");
765 }
while (!try_insert_node(new_node, prev_nodes, next_nodes));
768 return std::pair<iterator, bool>(
iterator(new_node),
true);
776 if (!try_lock_nodes(new_node->
height(), prev_nodes, next_nodes, locks)) {
781 ((prev_nodes[0] == dummy_head ||
782 my_compare(get_key(prev_nodes[0]), get_key(new_node))) &&
783 (next_nodes[0] ==
nullptr || my_compare(get_key(new_node), get_key(next_nodes[0])))),
784 "Wrong elements order");
789 new_node->
set_next(level, next_nodes[level]);
790 prev_nodes[level]->set_next(level, new_node);
801 if (l == 0 || prevs[l] != prevs[l - 1])
802 locks[l] = prevs[l]->acquire();
805 if ( next != next_nodes[l])
return false;
811 template <
typename K,
typename comparator>
818 next = internal_find_position(
h - 1, prev, key, cmp);
824 template <
typename K,
typename comparator>
831 next = internal_find_position(
h - 1, prev, key, cmp);
847 fill_prev_next_arrays(prev_nodes, next_nodes, prev, key, my_compare);
849 node_ptr erase_node = next_nodes[0];
852 if (erase_node && !my_compare(key, get_key(erase_node))) {
856 prev_nodes[level]->set_next(level, erase_node->
next(level));
859 return std::pair<node_ptr, node_ptr>(erase_node, next_node);
862 return std::pair<node_ptr, node_ptr>(
nullptr,
nullptr);
866 template<
typename SourceType>
869 using source_iterator =
typename source_type::iterator;
872 for(source_iterator it = source.begin(); it != source.end();) {
873 source_iterator where = it++;
874 if (allow_multimapping || !contains(traits_type::get_key(*where))) {
875 std::pair<node_ptr, node_ptr> extract_result = source.internal_extract(where);
879 __TBB_ASSERT(!handle.empty(),
"Extracted handle in merge is empty");
891 internal_copy(other.
begin(), other.
end());
894 template<
typename Iterator>
898 for (
auto it = first; it !=
last; ++it)
910 return my_rnd_generator();
918 template <
typename... Args>
924 node_ptr node =
reinterpret_cast<node_ptr>(node_allocator_traits::allocate(my_node_allocator, sz));
927 node_allocator_traits::construct(my_node_allocator, node, levels);
931 deallocate_node(node, sz);
936 node_allocator_traits::construct(my_node_allocator, node->
storage(), std::forward<Args>(args)...);
939 node_allocator_traits::destroy(my_node_allocator, node);
940 deallocate_node(node, sz);
948 size_type sz = calc_node_size(MAX_LEVEL);
950 dummy_head =
reinterpret_cast<node_ptr>(node_allocator_traits::allocate(my_node_allocator, sz));
952 auto max_level = MAX_LEVEL;
955 node_allocator_traits::construct(my_node_allocator, dummy_head, max_level);
958 deallocate_node(dummy_head, sz);
963 template <
bool is_dummy = false>
967 if (!is_dummy) node_allocator_traits::destroy(my_node_allocator, node->
storage());
969 node_allocator_traits::destroy(my_node_allocator, node);
971 deallocate_node(node, sz);
975 node_allocator_traits::deallocate(my_node_allocator, reinterpret_cast<uint8_t*>(node), sz);
979 delete_node<true>(dummy_head);
993 if (my_node_allocator == other.my_node_allocator) {
997 internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()));
1006 template <
typename K1,
typename K2>
1008 return !my_less_compare(second, first);
1017 template<
typename OtherTraits>
1023 template <
size_t MAX_LEVEL>
1026 static constexpr
size_t max_level = MAX_LEVEL;
1031 return (distribution(engines.local()) % MAX_LEVEL) + 1;
1043 #endif // __TBB_concurrent_skip_list_H pointer_type internal_find_position(size_type level, pointer_type &prev, const K &key, const comparator &cmp) const
bool operator()(const K1 &first, const K2 &second) const
iterator unsafe_erase(const_iterator first, const_iterator last)
std::reverse_iterator< iterator > reverse_iterator
node_type unsafe_extract(const key_type &key)
const_iterator lower_bound(const key_type &key) const
size_type max_size() const
typename std::aligned_storage< sizeof(value_type), alignof(value_type)>::type aligned_storage_type
iterator internal_get_bound(const K &key, const comparator &cmp)
const atomic_node_pointer & my_next(size_type level) const
const value_type & const_reference
allocator_type get_allocator() const
skip_list_iterator< list_node_type, false > iterator
concurrent_skip_list(const key_compare &comp, const allocator_type &alloc=allocator_type())
typename allocator_traits_type::const_pointer const_pointer
const_iterator begin() const
typename traits_type::node_type node_type
size_type count(const K &key) const
auto last(Container &c) -> decltype(begin(c))
bool_constant< false > false_type
void internal_copy(const concurrent_skip_list &other)
typename std::conditional< is_const, typename node_type::const_pointer, typename node_type::pointer >::type pointer
skip_list_node & operator=(const skip_list_node &)=delete
typename node_type::value_type value_type
iterator upper_bound(const key_type &key)
void insert(InputIterator first, InputIterator last)
skip_list_node(size_type levels)
random_level_generator_type my_rnd_generator
std::pair< iterator, iterator > equal_range(const K &key)
bool fully_linked() const
size_type count(const key_type &key) const
concurrent_skip_list & operator=(concurrent_skip_list &&other)
void internal_move(concurrent_skip_list &&other)
skip_list_iterator(node_type *n)
void set_next(size_type level, node_pointer next)
concurrent_skip_list(concurrent_skip_list &&other, const allocator_type &alloc)
iterator lower_bound(const key_type &key)
std::pair< node_ptr, node_ptr > internal_extract(const_iterator it)
concurrent_skip_list & operator=(std::initializer_list< value_type > il)
iterator lower_bound(const K &key)
typename traits_type::value_type value_type
const_range_type range() const
auto first(Container &c) -> decltype(begin(c))
range_type(range_type &r, split)
const_range_type(const_range_type &r, split)
const_iterator end() const
bool contains(const K &key) const
std::array< node_ptr, MAX_LEVEL > array_type
void allocator_swap(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
#define __TBB_STATIC_ASSERT(condition, msg)
bool try_lock_nodes(size_type height, array_type &prevs, array_type &next_nodes, lock_array &locks)
std::pair< iterator, iterator > equal_range(const key_type &key)
typename std::conditional< is_const, typename node_type::const_reference, typename node_type::reference >::type reference
skip_list_iterator operator++(int)
const_iterator cend() const
bool is_divisible() const
iterator internal_find(const K &key)
std::ptrdiff_t difference_type
std::pair< iterator, bool > insert(value_type &&value)
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
std::forward_iterator_tag iterator_category
void allocator_copy_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
pointer operator->() const
const_iterator find(const key_type &key) const
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long value
const_range_type(const concurrent_skip_list &l)
typename traits_type::key_type key_type
static size_type calc_node_size(size_type height)
std::array< typename list_node_type::lock_type, MAX_LEVEL > lock_array
tbb::enumerable_thread_specific< std::mt19937_64 > engines
typename allocator_traits_type::pointer pointer
size_type unsafe_erase(const key_type &key)
skip_list_iterator & operator++()
concurrent_skip_list(const concurrent_skip_list &other)
node_allocator_type my_node_allocator
typename std::allocator_traits< allocator_type >::template rebind_traits< uint8_t > node_allocator_traits
reference operator*() const
const key_compare & my_less_compare
concurrent_geometric_level_generator()
node_type unsafe_extract(const_iterator pos)
atomic_node_pointer & my_next(size_type level)
Dummy type that distinguishes splitting constructor from copy constructor.
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
std::pair< iterator, bool > insert(const value_type &value)
const_iterator cbegin() const
const_iterator internal_get_bound(const K &key, const comparator &cmp) const
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
not_greater_compare(const key_compare &less_compare)
void deallocate_node(node_ptr node, size_type sz)
void swap(concurrent_skip_list &other)
void move(tbb_thread &t1, tbb_thread &t2)
concurrent_skip_list & operator=(const concurrent_skip_list &other)
const_iterator lower_bound(const K &key) const
const_iterator upper_bound(const key_type &key) const
void internal_move_assign(concurrent_skip_list &&other, std::false_type)
skip_list_iterator(const skip_list_iterator< node_type, true > &other)
typename traits_type::compare_type key_compare
iterator insert(const_iterator, value_type &&value)
std::unique_lock< mutex_type > lock_type
void internal_copy(Iterator first, Iterator last)
static iterator get_iterator(const_iterator it)
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle * key
concurrent_skip_list(InputIt first, InputIt last, const key_compare &comp=key_compare(), const allocator_type &alloc=allocator_type())
size_type internal_count(const K &key) const
node_pointer next(size_type level) const
iterator insert(const_iterator, const_reference value)
std::atomic_bool my_fullyLinked
bool operator!=(const skip_list_iterator< NodeType, is_const1 > &lhs, const skip_list_iterator< NodeType, is_const2 > &rhs)
concurrent_skip_list(concurrent_skip_list &&other)
void insert(std::initializer_list< value_type > init)
iterator unsafe_erase(iterator pos)
skip_list_iterator(const skip_list_iterator< node_type, false > &other)
iterator upper_bound(const K &key)
std::pair< iterator, bool > insert(node_type &&nh)
std::ptrdiff_t difference_type
std::allocator_traits< allocator_type > allocator_traits_type
typename concurrent_skip_list::value_type value_type
typename concurrent_skip_list::const_iterator iterator
node_ptr create_node(Args &&... args)
void internal_merge(SourceType &&source)
bool contains(const key_type &key) const
const value_type & const_reference
typename traits_type::value_compare value_compare
const value_type * const_pointer
range_type(const concurrent_skip_list &l)
The enumerable_thread_specific container.
const_iterator upper_bound(const K &key) const
typename traits_type::random_level_generator_type random_level_generator_type
iterator emplace_hint(const_iterator, Args &&... args)
concurrent_skip_list(const concurrent_skip_list &other, const allocator_type &alloc)
void allocator_move_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
iterator find(const key_type &key)
aligned_storage_type my_val
std::atomic< node_pointer > atomic_node_pointer
typename concurrent_skip_list::size_type size_type
typename traits_type::allocator_type allocator_type
std::pair< iterator, bool > internal_insert(Args &&... args)
Base class for types that should not be assigned.
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp begin
skip_list_iterator< list_node_type, true > const_iterator
void fill_prev_next_arrays(array_type &prev_nodes, array_type &next_nodes, node_ptr prev, const key_type &key, const comparator &cmp)
std::reverse_iterator< const_iterator > const_reverse_iterator
bool try_insert_node(node_ptr new_node, array_type &prev_nodes, array_type &next_nodes)
iterator insert(const_iterator, node_type &&nh)
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp end
static const key_type & get_key(node_ptr n)
void swap(concurrent_hash_map< Key, T, HashCompare, A > &a, concurrent_hash_map< Key, T, HashCompare, A > &b)
const_iterator internal_find(const K &key) const
void delete_node(node_ptr node)
const_iterator find(const K &key) const
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type type
iterator find(const K &key)
std::pair< iterator, bool > emplace(Args &&... args)
std::pair< iterator, bool > internal_insert_node(node_ptr new_node)
typename std::allocator_traits< allocator_type >::template rebind_alloc< uint8_t > node_allocator_type
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t size
std::geometric_distribution< size_t > distribution
std::atomic< size_type > my_size
value_compare value_comp() const
void internal_move_assign(concurrent_skip_list &&other, std::true_type)
key_compare key_comp() const
void swap(atomic< T > &lhs, atomic< T > &rhs)
bool_constant< true > true_type
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function h
bool operator==(const skip_list_iterator< NodeType, is_const1 > &lhs, const skip_list_iterator< NodeType, is_const2 > &rhs)