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>
89 return reinterpret_cast<pointer>(&
my_val);
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,
189 template <
typename Traits>
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>;
247 using lock_array = std::array<typename list_node_type::lock_type, MAX_LEVEL>;
265 template<
class InputIt>
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;
331 if (
this != &other) {
332 using pocma_type =
typename node_allocator_traits::propagate_on_container_move_assignment;
344 insert(il.begin(),il.end());
366 template<
typename InputIterator>
368 for (InputIterator it =
first; it !=
last; ++it)
372 void insert(std::initializer_list<value_type> init) {
373 insert(init.begin(), init.end());
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) {
397 template<
typename... Args>
400 return emplace(std::forward<Args>(args)...).first;
405 if(extract_result.first) {
407 return extract_result.second;
566 using pocs_type =
typename node_allocator_traits::propagate_on_container_swap;
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>
678 template <
typename K>
684 template <
typename K>
688 return std::distance(
range.first,
range.second);
702 template <
typename K,
typename po
inter_type,
typename comparator>
704 const comparator& cmp)
const {
705 __TBB_ASSERT(level < prev->height(),
"Wrong level to find position");
706 pointer_type curr = prev->next(level);
711 curr = prev->next(level);
717 template <
typename comparator>
719 const comparator& cmp) {
721 next_nodes.fill(
nullptr);
725 prev_nodes[
h - 1] = prev;
726 next_nodes[
h - 1] = next;
730 template<
typename... Args>
734 if(!insert_result.second) {
737 return insert_result;
760 return std::pair<iterator, bool>(
iterator(next),
false);
763 "Wrong elements order");
768 return std::pair<iterator, bool>(
iterator(new_node),
true);
784 "Wrong elements order");
787 __TBB_ASSERT(prev_nodes[level]->height() > level, NULL);
788 __TBB_ASSERT(prev_nodes[level]->next(level) == next_nodes[level], NULL);
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>
824 template <
typename K,
typename comparator>
849 node_ptr erase_node = next_nodes[0];
854 __TBB_ASSERT(prev_nodes[level]->height() > level, NULL);
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++;
875 std::pair<node_ptr, node_ptr> extract_result = source.internal_extract(where);
879 __TBB_ASSERT(!handle.empty(),
"Extracted handle in merge is empty");
894 template<
typename Iterator>
918 template <
typename... Args>
963 template <
bool is_dummy = false>
975 node_allocator_traits::deallocate(
my_node_allocator, reinterpret_cast<uint8_t*>(node), sz);
997 internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()));
1006 template <
typename K1,
typename K2>
1017 template<
typename OtherTraits>
1023 template <
size_t MAX_LEVEL>
1043 #endif // __TBB_concurrent_skip_list_H friend bool operator!=(const skip_list_iterator< T, M > &, const skip_list_iterator< T, U > &)
const_iterator internal_find(const K &key) const
typename allocator_traits_type::const_pointer const_pointer
void set_next(size_type level, node_pointer next)
typename traits_type::node_type node_type
std::geometric_distribution< size_t > distribution
skip_list_iterator(const skip_list_iterator< node_type, false > &other)
const_range_type(const_range_type &r, split)
iterator upper_bound(const key_type &key)
value_compare value_comp() const
const atomic_node_pointer & my_next(size_type level) const
key_compare key_comp() const
iterator internal_find(const K &key)
node_pointer next(size_type level) const
node_ptr create_node(Args &&... args)
void insert(InputIterator first, InputIterator last)
typename concurrent_skip_list::size_type size_type
node_type unsafe_extract(const key_type &key)
const_iterator lower_bound(const key_type &key) const
auto last(Container &c) -> decltype(begin(c))
bool_constant< false > false_type
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 emplace_hint(const_iterator, Args &&... args)
std::ptrdiff_t difference_type
tbb::enumerable_thread_specific< std::mt19937_64 > engines
skip_list_iterator< list_node_type, false > iterator
concurrent_skip_list(const key_compare &comp, const allocator_type &alloc=allocator_type())
aligned_storage_type my_val
concurrent_skip_list(concurrent_skip_list &&other, const allocator_type &alloc)
reference operator *() const
void internal_copy(const concurrent_skip_list &other)
typename node_type::value_type value_type
range_type(const concurrent_skip_list &l)
bool contains(const K &key) const
iterator insert(const_iterator, value_type &&value)
iterator insert(const_iterator, node_type &&nh)
static const key_type & get_key(node_ptr n)
typename concurrent_skip_list::value_type value_type
concurrent_geometric_level_generator()
random_level_generator_type my_rnd_generator
size_type count(const key_type &key) const
void insert(std::initializer_list< value_type > init)
std::pair< iterator, bool > internal_insert_node(node_ptr new_node)
bool operator()(const K1 &first, const K2 &second) const
skip_list_iterator operator++(int)
auto first(Container &c) -> decltype(begin(c))
std::pair< iterator, bool > insert(node_type &&nh)
void allocator_swap(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
skip_list_iterator & operator++()
#define __TBB_STATIC_ASSERT(condition, msg)
const value_type & const_reference
std::reverse_iterator< iterator > reverse_iterator
iterator lower_bound(const key_type &key)
static size_type calc_node_size(size_type height)
std::pair< node_ptr, node_ptr > internal_extract(const_iterator it)
const_iterator end() const
concurrent_skip_list(const concurrent_skip_list &other, const allocator_type &alloc)
size_type unsafe_erase(const key_type &key)
static constexpr size_type MAX_LEVEL
concurrent_skip_list(const concurrent_skip_list &other)
node_allocator_type my_node_allocator
const value_type & const_reference
bool try_lock_nodes(size_type height, array_type &prevs, array_type &next_nodes, lock_array &locks)
node_type unsafe_extract(const_iterator pos)
The enumerable_thread_specific container.
const value_type * const_pointer
std::pair< iterator, iterator > equal_range(const key_type &key)
void allocator_copy_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
skip_list_node< value_type, typename traits_type::mutex_type > list_node_type
const_iterator begin() const
const_iterator cbegin() 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_iterator internal_get_bound(const K &key, const comparator &cmp) const
std::pair< iterator, bool > internal_insert(Args &&... args)
void deallocate_node(node_ptr node, size_type sz)
void swap(concurrent_skip_list &other)
skip_list_iterator< list_node_type, true > const_iterator
typename std::aligned_storage< sizeof(value_type), alignof(value_type)>::type aligned_storage_type
void internal_move_assign(concurrent_skip_list &&other, std::false_type)
range_type(range_type &r, split)
typename std::conditional< is_const, typename node_type::const_pointer, typename node_type::pointer >::type pointer
bool try_insert_node(node_ptr new_node, array_type &prev_nodes, array_type &next_nodes)
std::pair< iterator, bool > insert(value_type &&value)
size_type internal_count(const K &key) const
bool is_divisible() const
skip_list_iterator(node_type *n)
iterator insert(const_iterator, const_reference value)
std::atomic_bool my_fullyLinked
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
atomic_node_pointer & my_next(size_type level)
std::pair< iterator, iterator > equal_range(const K &key)
void delete_node(node_ptr node)
const_iterator find(const K &key) const
skip_list_node & operator=(const skip_list_node &)=delete
iterator unsafe_erase(iterator pos)
concurrent_skip_list & operator=(concurrent_skip_list &&other)
void internal_move(concurrent_skip_list &&other)
void move(tbb_thread &t1, tbb_thread &t2)
iterator upper_bound(const K &key)
void internal_move_assign(concurrent_skip_list &&other, std::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 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
bool contains(const key_type &key) const
bool operator!=(const skip_list_iterator< NodeType, is_const1 > &lhs, const skip_list_iterator< NodeType, is_const2 > &rhs)
std::atomic< node_pointer > atomic_node_pointer
std::pair< iterator, bool > insert(const value_type &value)
std::forward_iterator_tag iterator_category
iterator unsafe_erase(const_iterator first, const_iterator last)
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
const_iterator upper_bound(const K &key) const
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(const concurrent_skip_list &l)
const_range_type range() const
const_iterator lower_bound(const K &key) const
typename traits_type::compare_type key_compare
void internal_copy(Iterator first, Iterator last)
typename concurrent_skip_list::iterator iterator
allocator_type get_allocator() const
iterator find(const key_type &key)
Base class for types that should not be assigned.
concurrent_skip_list(concurrent_skip_list &&other)
skip_list_node(size_type levels)
static bool const allow_multimapping
size_type count(const K &key) const
const_iterator cend() const
std::ptrdiff_t difference_type
const key_compare & my_less_compare
std::reverse_iterator< const_iterator > const_reverse_iterator
std::allocator_traits< allocator_type > allocator_traits_type
void allocator_move_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
void internal_merge(SourceType &&source)
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
typename traits_type::value_compare value_compare
const_iterator find(const key_type &key) const
static constexpr size_t max_level
typename traits_type::key_type key_type
iterator find(const K &key)
typename traits_type::random_level_generator_type random_level_generator_type
std::pair< iterator, bool > emplace(Args &&... args)
typename std::allocator_traits< allocator_type >::template rebind_alloc< uint8_t > node_allocator_type
std::atomic< size_type > my_size
friend bool operator==(const skip_list_iterator< T, M > &, const skip_list_iterator< T, U > &)
typename std::allocator_traits< allocator_type >::template rebind_traits< uint8_t > node_allocator_traits
typename concurrent_skip_list::const_iterator iterator
not_greater_compare(const key_compare &less_compare)
pointer operator->() const
pointer_type internal_find_position(size_type level, pointer_type &prev, const K &key, const comparator &cmp) const
typename traits_type::allocator_type 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 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
bool fully_linked() const
size_type max_size() const
concurrent_skip_list & operator=(const concurrent_skip_list &other)
const_iterator upper_bound(const key_type &key) const
void fill_prev_next_arrays(array_type &prev_nodes, array_type &next_nodes, node_ptr prev, const key_type &key, const comparator &cmp)
Dummy type that distinguishes splitting constructor from copy constructor.
std::array< node_ptr, MAX_LEVEL > array_type
skip_list_iterator(const skip_list_iterator< node_type, true > &other)
std::unique_lock< mutex_type > lock_type
static iterator get_iterator(const_iterator it)
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)
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)