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,
179 my_node_ptr = my_node_ptr->next(0);
194 template <
typename Traits>
199 friend class const_range;
202 template <
typename T,
bool M,
bool U>
205 template <
typename T,
bool M,
bool U>
209 template <
typename NodeType,
bool is_const1,
bool is_const2>
214 template <
typename NodeType,
bool is_const1,
bool is_const2>
219 template <
typename Traits>
239 using pointer =
typename allocator_traits_type::pointer;
245 using node_allocator_type =
typename std::allocator_traits<allocator_type>::template rebind_alloc<uint8_t>;
249 static constexpr
size_type MAX_LEVEL = traits_type::MAX_LEVEL;
252 using lock_array = std::array<typename list_node_type::lock_type, MAX_LEVEL>;
255 static bool const allow_multimapping = traits_type::allow_multimapping;
265 : my_node_allocator(alloc), my_compare(comp), my_size(0)
270 template<
class InputIt>
273 : my_node_allocator(alloc), my_compare(comp), my_size(0)
276 internal_copy(first, last);
281 : my_node_allocator(
node_allocator_traits::select_on_container_copy_construction(other.get_allocator())),
282 my_compare(other.my_compare), my_rnd_generator(other.my_rnd_generator), my_size(0)
285 internal_copy(other);
290 : my_node_allocator(alloc), my_compare(other.my_compare),
291 my_rnd_generator(other.my_rnd_generator), my_size(0)
294 internal_copy(other);
299 : my_node_allocator(
std::
move(other.my_node_allocator)), my_compare(other.my_compare),
300 my_rnd_generator(other.my_rnd_generator)
306 : my_node_allocator(alloc), my_compare(other.my_compare),
307 my_rnd_generator(other.my_rnd_generator)
309 if (alloc == other.get_allocator()) {
314 internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()));
324 if (
this != &other) {
325 using pocca_type =
typename node_allocator_traits::propagate_on_container_copy_assignment;
330 internal_copy(other);
336 if (
this != &other) {
337 using pocma_type =
typename node_allocator_traits::propagate_on_container_move_assignment;
339 my_compare = other.my_compare;
340 my_rnd_generator = other.my_rnd_generator;
341 internal_move_assign(
std::move(other), pocma_type());
349 insert(il.begin(),il.end());
354 return internal_insert(value);
363 return insert(value).first;
371 template<
typename InputIterator>
372 void insert(InputIterator first, InputIterator last) {
373 for (InputIterator it = first; it !=
last; ++it)
377 void insert(std::initializer_list<value_type> init) {
378 insert(init.begin(), init.end());
383 std::pair<iterator, bool> insert_result = internal_insert_node(nh.my_node);
384 if(insert_result.second) {
387 return insert_result;
389 return std::pair<iterator, bool>(
end(),
false);
397 template<
typename... Args >
398 std::pair<iterator, bool>
emplace(Args&&... args) {
399 return internal_insert(std::forward<Args>(args)...);
402 template<
typename... Args>
405 return emplace(std::forward<Args>(args)...).first;
409 std::pair<node_ptr, node_ptr> extract_result = internal_extract(pos);
410 if(extract_result.first) {
411 delete_node(extract_result.first);
412 return iterator(extract_result.second);
418 return unsafe_erase(get_iterator(pos));
421 template <
typename K,
typename = tbb::
internal::is_transparent<key_compare, K>,
422 typename =
typename std::enable_if<!std::is_convertible<K, iterator>::value &&
423 !std::is_convertible<K, const_iterator>::value>::type>
425 std::pair<iterator, iterator> range = equal_range(key);
426 size_type sz = std::distance(range.first, range.second);
427 unsafe_erase(range.first, range.second);
432 while(first != last) {
433 first = unsafe_erase(get_iterator(first));
435 return get_iterator(first);
439 std::pair<iterator, iterator> range = equal_range(key);
440 size_type sz = std::distance(range.first, range.second);
441 unsafe_erase(range.first, range.second);
446 std::pair<node_ptr, node_ptr> extract_result = internal_extract(pos);
451 return unsafe_extract(find(key));
455 return internal_get_bound(key, my_compare);
459 return internal_get_bound(key, my_compare);
462 template <
typename K,
typename =
typename tbb::
internal::is_transparent<key_compare, K> >
464 return internal_get_bound(key, my_compare);
467 template <
typename K,
typename =
typename tbb::
internal::is_transparent<key_compare, K> >
469 return internal_get_bound(key, my_compare);
480 template <
typename K,
typename =
typename tbb::
internal::is_transparent<key_compare, K> >
485 template <
typename K,
typename =
typename tbb::
internal::is_transparent<key_compare, K> >
491 return internal_find(key);
495 return internal_find(key);
498 template <
typename K,
typename =
typename tbb::
internal::is_transparent<key_compare, K> >
500 return internal_find(key);
503 template <
typename K,
typename =
typename tbb::
internal::is_transparent<key_compare, K> >
505 return internal_find(key);
509 return internal_count(key);
512 template <
typename K,
typename =
typename tbb::
internal::is_transparent<key_compare, K> >
514 return internal_count(key);
518 return find(key) !=
end();
521 template <
typename K,
typename =
typename tbb::
internal::is_transparent<key_compare, K> >
523 return find(key) !=
end();
533 delete_node(current);
538 for (
size_type i = 0; i < dummy_head->height(); ++i) {
544 return iterator(dummy_head->next(0));
572 return my_node_allocator.max_size();
580 return my_node_allocator;
585 using pocs_type =
typename node_allocator_traits::propagate_on_container_swap;
597 return std::pair<iterator, iterator>(lower_bound(key), upper_bound(key));
601 return std::pair<const_iterator, const_iterator>(lower_bound(key), upper_bound(key));
604 template <
typename K,
typename =
typename tbb::
internal::is_transparent<key_compare, K> >
606 return std::pair<iterator, iterator>(lower_bound(key), upper_bound(key));
609 template <
typename K,
typename =
typename tbb::
internal::is_transparent<key_compare, K> >
611 return std::pair<const_iterator, const_iterator>(lower_bound(key), upper_bound(key));
648 : my_end(l.
end()), my_begin(l.
begin()), my_level(my_begin.my_node_ptr->
height() ) {}
678 dummy_head = other.dummy_head;
679 other.dummy_head =
nullptr;
680 other.create_dummy_head();
682 my_size = other.my_size.load();
688 return traits_type::get_key(n->
value());
691 template <
typename K>
694 return (it ==
end() || my_compare(key, traits_type::get_key(*it))) ?
end() : it;
697 template <
typename K>
700 return (it ==
end() || my_compare(key, traits_type::get_key(*it))) ?
end() : it;
703 template <
typename K>
705 if (allow_multimapping) {
706 std::pair<const_iterator, const_iterator> range = equal_range(key);
707 return std::distance(range.first, range.second);
721 template <
typename K,
typename po
inter_type,
typename comparator>
723 const comparator& cmp)
const {
725 pointer_type curr = prev->next(level);
727 while (curr && cmp(get_key(curr), key)) {
730 curr = prev->next(level);
736 template <
typename comparator>
738 const comparator& cmp) {
739 prev_nodes.fill(dummy_head);
740 next_nodes.fill(
nullptr);
743 node_ptr next = internal_find_position(
h - 1, prev, key, cmp);
744 prev_nodes[
h - 1] = prev;
745 next_nodes[
h - 1] =
next;
749 template <
typename comparator>
751 const comparator& cmp) {
757 internal_find_position(
h - 1, prev, key, cmp);
764 curr = prev->
next(
h - 1);
766 prev_nodes[
h - 1] = prev;
769 std::fill(next_nodes.begin(), next_nodes.begin() + node_height, erase_node);
772 template<
typename... Args>
774 node_ptr new_node = create_node(std::forward<Args>(args)...);
775 std::pair<iterator, bool> insert_result = internal_insert_node(new_node);
776 if(!insert_result.second) {
777 delete_node(new_node);
779 return insert_result;
785 __TBB_ASSERT(dummy_head->height() >= new_node->
height(),
"Wrong height for new node");
788 if (allow_multimapping) {
789 fill_prev_next_arrays(prev_nodes, next_nodes, dummy_head, get_key(new_node),
792 fill_prev_next_arrays(prev_nodes, next_nodes, dummy_head, get_key(new_node), my_compare);
796 if (next && !allow_multimapping && !my_compare(get_key(new_node), get_key(next))) {
802 return std::pair<iterator, bool>(
iterator(next),
false);
804 __TBB_ASSERT(allow_multimapping || !next || my_compare(get_key(new_node), get_key(next)),
805 "Wrong elements order");
807 }
while (!try_insert_node(new_node, prev_nodes, next_nodes));
810 return std::pair<iterator, bool>(
iterator(new_node),
true);
818 if (!try_lock_nodes(new_node->
height(), prev_nodes, next_nodes, locks)) {
823 ((prev_nodes[0] == dummy_head ||
824 my_compare(get_key(prev_nodes[0]), get_key(new_node))) &&
825 (next_nodes[0] ==
nullptr || my_compare(get_key(new_node), get_key(next_nodes[0])))),
826 "Wrong elements order");
831 new_node->
set_next(level, next_nodes[level]);
832 prev_nodes[level]->set_next(level, new_node);
843 if (l == 0 || prevs[l] != prevs[l - 1])
844 locks[l] = prevs[l]->acquire();
847 if ( next != next_nodes[l])
return false;
853 template <
typename K,
typename comparator>
860 next = internal_find_position(
h - 1, prev, key, cmp);
866 template <
typename K,
typename comparator>
873 next = internal_find_position(
h - 1, prev, key, cmp);
888 fill_prev_next_by_ptr(prev_nodes, next_nodes, it, key, my_compare);
890 node_ptr erase_node = next_nodes[0];
894 if (!my_compare(key, get_key(erase_node))) {
898 prev_nodes[level]->set_next(level, erase_node->
next(level));
901 return std::pair<node_ptr, node_ptr>(erase_node, next_node);
904 return std::pair<node_ptr, node_ptr>(
nullptr,
nullptr);
908 template<
typename SourceType>
911 using source_iterator =
typename source_type::iterator;
914 for(source_iterator it = source.begin(); it != source.end();) {
915 source_iterator where = it++;
916 if (allow_multimapping || !contains(traits_type::get_key(*where))) {
917 std::pair<node_ptr, node_ptr> extract_result = source.internal_extract(where);
921 __TBB_ASSERT(!handle.empty(),
"Extracted handle in merge is empty");
933 internal_copy(other.
begin(), other.
end());
936 template<
typename Iterator>
940 for (
auto it = first; it !=
last; ++it)
952 return my_rnd_generator();
960 template <
typename... Args>
966 node_ptr node =
reinterpret_cast<node_ptr>(node_allocator_traits::allocate(my_node_allocator, sz));
969 node_allocator_traits::construct(my_node_allocator, node, levels);
973 deallocate_node(node, sz);
978 node_allocator_traits::construct(my_node_allocator, node->
storage(), std::forward<Args>(args)...);
981 node_allocator_traits::destroy(my_node_allocator, node);
982 deallocate_node(node, sz);
990 size_type sz = calc_node_size(MAX_LEVEL);
992 dummy_head =
reinterpret_cast<node_ptr>(node_allocator_traits::allocate(my_node_allocator, sz));
994 auto max_level = MAX_LEVEL;
997 node_allocator_traits::construct(my_node_allocator, dummy_head, max_level);
1000 deallocate_node(dummy_head, sz);
1005 template <
bool is_dummy = false>
1009 if (!is_dummy) node_allocator_traits::destroy(my_node_allocator, node->
storage());
1011 node_allocator_traits::destroy(my_node_allocator, node);
1013 deallocate_node(node, sz);
1017 node_allocator_traits::deallocate(my_node_allocator, reinterpret_cast<uint8_t*>(node), sz);
1021 delete_node<true>(dummy_head);
1029 delete_dummy_head();
1035 if (my_node_allocator == other.my_node_allocator) {
1036 delete_dummy_head();
1039 internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()));
1048 template <
typename K1,
typename K2>
1050 return !my_less_compare(second, first);
1059 template<
typename OtherTraits>
1065 template <
size_t MAX_LEVEL>
1068 static constexpr
size_t max_level = MAX_LEVEL;
1073 return (distribution(engines.local()) % MAX_LEVEL) + 1;
1085 #endif // __TBB_concurrent_skip_list_H iterator upper_bound(const key_type &key)
std::array< node_ptr, MAX_LEVEL > array_type
iterator insert(const_iterator, node_type &&nh)
node_ptr create_node(Args &&... args)
void internal_merge(SourceType &&source)
void insert(InputIterator first, InputIterator last)
const_iterator internal_find(const K &key) const
void move(tbb_thread &t1, tbb_thread &t2)
bool_constant< true > true_type
typename traits_type::random_level_generator_type random_level_generator_type
iterator emplace_hint(const_iterator, Args &&... args)
value_compare value_comp() const
const atomic_node_pointer & my_next(size_type level) const
Dummy type that distinguishes splitting constructor from copy constructor.
node_pointer next(size_type level) const
#define __TBB_STATIC_ASSERT(condition, msg)
aligned_storage_type my_val
typename concurrent_skip_list::size_type size_type
typename traits_type::allocator_type allocator_type
concurrent_skip_list(concurrent_skip_list &&other, const allocator_type &alloc)
std::reverse_iterator< iterator > reverse_iterator
node_type unsafe_extract(const key_type &key)
static size_type calc_node_size(size_type height)
typename std::conditional< is_const, typename node_type::const_pointer, typename node_type::pointer >::type pointer
bool contains(const K &key) const
Base class for types that should not be assigned.
static const key_type & get_key(node_ptr n)
concurrent_skip_list(const concurrent_skip_list &other)
node_allocator_type my_node_allocator
skip_list_iterator< list_node_type, false > iterator
skip_list_iterator(node_type *n)
node_type unsafe_extract(const_iterator pos)
concurrent_skip_list(const key_compare &comp, const allocator_type &alloc=allocator_type())
void set_next(size_type level, node_pointer next)
const_iterator internal_get_bound(const K &key, const comparator &cmp) const
std::pair< iterator, bool > internal_insert_node(node_ptr new_node)
void internal_copy(const concurrent_skip_list &other)
const_range_type(const_range_type &r, split)
void deallocate_node(node_ptr node, size_type sz)
void swap(concurrent_skip_list &other)
skip_list_iterator operator++(int)
void internal_move_assign(concurrent_skip_list &&other, std::false_type)
key_compare key_comp() const
iterator internal_find(const K &key)
typename concurrent_skip_list::value_type value_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 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
const_iterator lower_bound(const key_type &key) const
std::geometric_distribution< size_t > distribution
void fill_prev_next_by_ptr(array_type &prev_nodes, array_type &next_nodes, const_iterator it, const key_type &key, const comparator &cmp)
std::array< typename list_node_type::lock_type, MAX_LEVEL > lock_array
typename std::conditional< is_const, typename node_type::const_reference, typename node_type::reference >::type reference
typename allocator_traits_type::pointer pointer
iterator unsafe_erase(const_iterator pos)
size_type unsafe_erase(const key_type &key)
void allocator_copy_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
const value_type & const_reference
skip_list_iterator & operator++()
The enumerable_thread_specific container.
auto first(Container &c) -> decltype(begin(c))
bool contains(const key_type &key) const
const value_type * const_pointer
const_iterator begin() const
const_iterator cbegin() const
range_type(const concurrent_skip_list &l)
std::pair< node_ptr, node_ptr > internal_extract(const_iterator it)
concurrent_skip_list & operator=(std::initializer_list< value_type > il)
typename traits_type::value_type value_type
const_range_type range() 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 size
typename node_type::value_type value_type
iterator insert(const_iterator, value_type &&value)
size_type internal_count(const K &key) const
skip_list_iterator & operator=(const skip_list_iterator< node_type, false > &other)
auto last(Container &c) -> decltype(begin(c))
reference operator*() const
bool try_lock_nodes(size_type height, array_type &prevs, array_type &next_nodes, lock_array &locks)
iterator insert(const_iterator, const_reference value)
std::atomic_bool my_fullyLinked
atomic_node_pointer & my_next(size_type level)
random_level_generator_type my_rnd_generator
bool operator!=(const skip_list_iterator< NodeType, is_const1 > &lhs, const skip_list_iterator< NodeType, is_const2 > &rhs)
std::pair< iterator, iterator > equal_range(const K &key)
std::pair< iterator, iterator > equal_range(const key_type &key)
size_type count(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 h
void swap(atomic< T > &lhs, atomic< T > &rhs)
void insert(std::initializer_list< value_type > init)
iterator unsafe_erase(iterator pos)
concurrent_skip_list & operator=(concurrent_skip_list &&other)
void internal_move(concurrent_skip_list &&other)
skip_list_iterator(const skip_list_iterator< node_type, false > &other)
bool operator()(const K1 &first, const K2 &second) const
iterator upper_bound(const K &key)
const_iterator cend() const
std::reverse_iterator< const_iterator > const_reverse_iterator
std::pair< iterator, bool > insert(node_type &&nh)
std::pair< iterator, bool > insert(value_type &&value)
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
bool is_divisible() const
size_type unsafe_erase(const K &key)
bool_constant< false > false_type
const value_type & const_reference
std::atomic< node_pointer > atomic_node_pointer
pointer operator->() const
void delete_node(node_ptr node)
const_iterator upper_bound(const K &key) const
iterator lower_bound(const key_type &key)
skip_list_node & operator=(const skip_list_node &)=delete
iterator lower_bound(const K &key)
const_range_type(const concurrent_skip_list &l)
range_type(range_type &r, split)
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
const_iterator end() const
std::atomic< size_type > my_size
concurrent_skip_list(const concurrent_skip_list &other, const allocator_type &alloc)
std::ptrdiff_t difference_type
typename std::allocator_traits< allocator_type >::template rebind_traits< uint8_t > node_allocator_traits
iterator find(const key_type &key)
typename concurrent_skip_list::const_iterator iterator
pointer_type internal_find_position(size_type level, pointer_type &prev, const K &key, const comparator &cmp) const
std::pair< iterator, bool > insert(const value_type &value)
skip_list_node(size_type levels)
iterator unsafe_erase(const_iterator first, const_iterator last)
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
std::pair< iterator, bool > internal_insert(Args &&... args)
const_iterator lower_bound(const K &key) const
skip_list_iterator< list_node_type, true > const_iterator
typename std::aligned_storage< sizeof(value_type), alignof(value_type)>::type aligned_storage_type
typename traits_type::compare_type key_compare
skip_list_iterator(const skip_list_iterator< node_type, true > &other)
std::unique_lock< mutex_type > lock_type
void internal_copy(Iterator first, Iterator last)
static iterator get_iterator(const_iterator it)
bool try_insert_node(node_ptr new_node, array_type &prev_nodes, array_type &next_nodes)
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
concurrent_skip_list(InputIt first, InputIt last, const key_compare &comp=key_compare(), const allocator_type &alloc=allocator_type())
iterator internal_get_bound(const K &key, const comparator &cmp)
concurrent_geometric_level_generator()
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
typename allocator_traits_type::const_pointer const_pointer
const_iterator find(const key_type &key) const
typename traits_type::key_type key_type
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
size_type count(const K &key) const
iterator find(const K &key)
std::pair< iterator, bool > emplace(Args &&... args)
void swap(concurrent_hash_map< Key, T, HashCompare, A > &a, concurrent_hash_map< Key, T, HashCompare, A > &b)
typename std::allocator_traits< allocator_type >::template rebind_alloc< uint8_t > node_allocator_type
std::ptrdiff_t difference_type
const key_compare & my_less_compare
std::allocator_traits< allocator_type > allocator_traits_type
void internal_move_assign(concurrent_skip_list &&other, std::true_type)
typename traits_type::value_compare value_compare
void allocator_move_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
std::forward_iterator_tag iterator_category
size_type max_size() const
concurrent_skip_list & operator=(const concurrent_skip_list &other)
const_iterator upper_bound(const key_type &key) const
tbb::enumerable_thread_specific< std::mt19937_64 > engines
allocator_type get_allocator() const
concurrent_skip_list(concurrent_skip_list &&other)
bool operator==(const skip_list_iterator< NodeType, is_const1 > &lhs, const skip_list_iterator< NodeType, is_const2 > &rhs)
not_greater_compare(const key_compare &less_compare)
void allocator_swap(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
typename traits_type::node_type node_type
bool fully_linked() 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
void fill_prev_next_arrays(array_type &prev_nodes, array_type &next_nodes, node_ptr prev, const key_type &key, const comparator &cmp)