Intel(R) Threading Building Blocks Doxygen Documentation
version 4.2.3
|
Go to the documentation of this file.
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,
194 template <
typename Traits>
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>;
252 using lock_array = std::array<typename list_node_type::lock_type, MAX_LEVEL>;
270 template<
class InputIt>
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;
336 if (
this != &other) {
337 using pocma_type =
typename node_allocator_traits::propagate_on_container_move_assignment;
349 insert(il.begin(),il.end());
371 template<
typename InputIterator>
373 for (InputIterator it =
first; it !=
last; ++it)
377 void insert(std::initializer_list<value_type> init) {
378 insert(init.begin(), init.end());
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) {
402 template<
typename... Args>
405 return emplace(std::forward<Args>(args)...).first;
410 if(extract_result.first) {
412 return iterator(extract_result.second);
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>
462 template <
typename K,
typename =
typename tbb::
internal::is_transparent<key_compare, K> >
467 template <
typename K,
typename =
typename tbb::
internal::is_transparent<key_compare, K> >
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> >
498 template <
typename K,
typename =
typename tbb::
internal::is_transparent<key_compare, K> >
503 template <
typename K,
typename =
typename tbb::
internal::is_transparent<key_compare, K> >
512 template <
typename K,
typename =
typename tbb::
internal::is_transparent<key_compare, K> >
521 template <
typename K,
typename =
typename tbb::
internal::is_transparent<key_compare, K> >
585 using pocs_type =
typename node_allocator_traits::propagate_on_container_swap;
604 template <
typename K,
typename =
typename tbb::
internal::is_transparent<key_compare, K> >
609 template <
typename K,
typename =
typename tbb::
internal::is_transparent<key_compare, K> >
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>
697 template <
typename K>
703 template <
typename K>
707 return std::distance(
range.first,
range.second);
721 template <
typename K,
typename po
inter_type,
typename comparator>
723 const comparator& cmp)
const {
724 __TBB_ASSERT(level < prev->height(),
"Wrong level to find position");
725 pointer_type curr = prev->next(level);
730 curr = prev->next(level);
736 template <
typename comparator>
738 const comparator& cmp) {
740 next_nodes.fill(
nullptr);
744 prev_nodes[
h - 1] = prev;
745 next_nodes[
h - 1] = next;
749 template <
typename comparator>
751 const comparator& 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>
776 if(!insert_result.second) {
779 return insert_result;
802 return std::pair<iterator, bool>(
iterator(next),
false);
805 "Wrong elements order");
810 return std::pair<iterator, bool>(
iterator(new_node),
true);
826 "Wrong elements order");
829 __TBB_ASSERT(prev_nodes[level]->height() > level, NULL);
830 __TBB_ASSERT(prev_nodes[level]->next(level) == next_nodes[level], NULL);
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>
866 template <
typename K,
typename comparator>
890 node_ptr erase_node = next_nodes[0];
896 __TBB_ASSERT(prev_nodes[level]->height() > level, NULL);
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++;
917 std::pair<node_ptr, node_ptr> extract_result = source.internal_extract(where);
921 __TBB_ASSERT(!handle.empty(),
"Extracted handle in merge is empty");
936 template<
typename Iterator>
960 template <
typename... Args>
1005 template <
bool is_dummy = false>
1017 node_allocator_traits::deallocate(
my_node_allocator, reinterpret_cast<uint8_t*>(node), sz);
1039 internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()));
1048 template <
typename K1,
typename K2>
1059 template<
typename OtherTraits>
1065 template <
size_t MAX_LEVEL>
1085 #endif // __TBB_concurrent_skip_list_H
typename traits_type::key_type key_type
aligned_storage_type my_val
iterator insert(const_iterator, value_type &&value)
std::ptrdiff_t difference_type
void internal_move_assign(concurrent_skip_list &&other, std::true_type)
void internal_copy(Iterator first, Iterator last)
key_compare key_comp() const
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
bool operator!=(const skip_list_iterator< NodeType, is_const1 > &lhs, const skip_list_iterator< NodeType, is_const2 > &rhs)
const_range_type range() const
std::reverse_iterator< const_iterator > const_reverse_iterator
std::atomic< size_type > my_size
iterator internal_get_bound(const K &key, const comparator &cmp)
static const key_type & get_key(node_ptr n)
typename std::allocator_traits< allocator_type >::template rebind_traits< uint8_t > node_allocator_traits
void allocator_copy_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
node_type unsafe_extract(const_iterator pos)
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
const_iterator upper_bound(const key_type &key) const
void allocator_move_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
std::reverse_iterator< iterator > reverse_iterator
typename traits_type::random_level_generator_type random_level_generator_type
iterator insert(const_iterator, const_reference value)
iterator upper_bound(const K &key)
node_allocator_type my_node_allocator
size_type max_size() const
std::array< node_ptr, MAX_LEVEL > array_type
not_greater_compare(const key_compare &less_compare)
void allocator_swap(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
typename node_type::value_type value_type
pointer operator->() const
void swap(atomic< T > &lhs, atomic< T > &rhs)
const_iterator internal_get_bound(const K &key, const comparator &cmp) const
std::pair< iterator, bool > internal_insert_node(node_ptr new_node)
tbb::enumerable_thread_specific< std::mt19937_64 > engines
typename concurrent_skip_list::value_type value_type
size_type internal_count(const K &key) const
bool contains(const key_type &key) const
skip_list_iterator & operator=(const skip_list_iterator< node_type, false > &other)
typename concurrent_skip_list::iterator iterator
typename concurrent_skip_list::const_iterator iterator
bool fully_linked() const
void internal_move(concurrent_skip_list &&other)
allocator_type get_allocator() const
skip_list_iterator & operator++()
concurrent_skip_list & operator=(concurrent_skip_list &&other)
skip_list_iterator< list_node_type, false > iterator
atomic_node_pointer & my_next(size_type level)
const_iterator cbegin() const
concurrent_skip_list(const key_compare &comp, const allocator_type &alloc=allocator_type())
void internal_merge(SourceType &&source)
reference operator*() const
void insert(InputIterator first, InputIterator last)
std::array< typename list_node_type::lock_type, MAX_LEVEL > lock_array
pointer_type internal_find_position(size_type level, pointer_type &prev, const K &key, const comparator &cmp) const
std::pair< iterator, iterator > equal_range(const key_type &key)
static size_type calc_node_size(size_type height)
static const bool allow_multimapping
iterator unsafe_erase(iterator pos)
typename traits_type::allocator_type allocator_type
bool try_lock_nodes(size_type height, array_type &prevs, array_type &next_nodes, lock_array &locks)
void deallocate_node(node_ptr node, size_type sz)
bool is_divisible() const
typename std::conditional< is_const, typename node_type::const_pointer, typename node_type::pointer >::type pointer
iterator lower_bound(const K &key)
skip_list_iterator< list_node_type, true > const_iterator
skip_list_node(size_type levels)
typename traits_type::compare_type key_compare
const_iterator begin() const
std::forward_iterator_tag iterator_category
std::pair< node_ptr, node_ptr > internal_extract(const_iterator it)
iterator find(const K &key)
range_type(const concurrent_skip_list &l)
skip_list_iterator(node_type *n)
std::atomic< node_pointer > atomic_node_pointer
typename std::conditional< is_const, typename node_type::const_reference, typename node_type::reference >::type reference
concurrent_skip_list(concurrent_skip_list &&other, const allocator_type &alloc)
void internal_copy(const concurrent_skip_list &other)
const value_type & const_reference
skip_list_node & operator=(const skip_list_node &)=delete
concurrent_skip_list(concurrent_skip_list &&other)
#define __TBB_STATIC_ASSERT(condition, msg)
static iterator get_iterator(const_iterator it)
skip_list_node< value_type, typename traits_type::mutex_type > list_node_type
void move(tbb_thread &t1, tbb_thread &t2)
iterator find(const key_type &key)
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_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle * key
node_pointer next(size_type level) const
std::atomic_bool my_fullyLinked
bool operator==(const skip_list_iterator< NodeType, is_const1 > &lhs, const skip_list_iterator< NodeType, is_const2 > &rhs)
std::pair< iterator, bool > insert(node_type &&nh)
std::pair< iterator, bool > emplace(Args &&... args)
typename allocator_traits_type::pointer pointer
void swap(concurrent_skip_list &other)
std::geometric_distribution< size_t > distribution
std::allocator_traits< allocator_type > allocator_traits_type
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
std::pair< iterator, iterator > equal_range(const K &key)
concurrent_skip_list(InputIt first, InputIt last, const key_compare &comp=key_compare(), const allocator_type &alloc=allocator_type())
size_type count(const key_type &key) const
iterator lower_bound(const key_type &key)
iterator upper_bound(const key_type &key)
const value_type * const_pointer
typename traits_type::node_type node_type
const atomic_node_pointer & my_next(size_type level) const
auto first(Container &c) -> decltype(begin(c))
skip_list_iterator(const skip_list_iterator< node_type, false > &other)
typename std::allocator_traits< allocator_type >::template rebind_alloc< uint8_t > node_allocator_type
typename traits_type::value_type value_type
iterator unsafe_erase(const_iterator pos)
const_iterator cend() const
typename std::aligned_storage< sizeof(value_type), alignof(value_type)>::type aligned_storage_type
concurrent_skip_list & operator=(const concurrent_skip_list &other)
The enumerable_thread_specific container.
void fill_prev_next_by_ptr(array_type &prev_nodes, array_type &next_nodes, const_iterator it, const key_type &key, const comparator &cmp)
bool_constant< true > true_type
std::pair< iterator, bool > insert(value_type &&value)
node_type unsafe_extract(const key_type &key)
Base class for types that should not be assigned.
const_iterator lower_bound(const K &key) const
random_level_generator_type my_rnd_generator
size_type unsafe_erase(const key_type &key)
friend bool operator!=(const skip_list_iterator< T, M > &, const skip_list_iterator< T, U > &)
concurrent_geometric_level_generator()
typename allocator_traits_type::const_pointer const_pointer
std::pair< iterator, bool > insert(const value_type &value)
const_iterator find(const K &key) const
concurrent_skip_list & operator=(std::initializer_list< value_type > il)
node_ptr create_node(Args &&... args)
size_type count(const K &key) const
bool operator()(const K1 &first, const K2 &second) 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
static constexpr size_t max_level
skip_list_iterator operator++(int)
const value_type & const_reference
skip_list_iterator(const skip_list_iterator< node_type, true > &other)
const_iterator internal_find(const K &key) const
bool contains(const K &key) const
static constexpr size_type MAX_LEVEL
const_range_type(const_range_type &r, split)
const_iterator upper_bound(const K &key) const
concurrent_skip_list(const concurrent_skip_list &other)
auto last(Container &c) -> decltype(begin(c))
bool_constant< false > false_type
void fill_prev_next_arrays(array_type &prev_nodes, array_type &next_nodes, node_ptr prev, const key_type &key, const comparator &cmp)
iterator emplace_hint(const_iterator, Args &&... args)
typename concurrent_skip_list::size_type size_type
value_compare value_comp() const
const key_compare & my_less_compare
std::ptrdiff_t difference_type
const_iterator end() const
void insert(std::initializer_list< value_type > init)
iterator insert(const_iterator, node_type &&nh)
bool try_insert_node(node_ptr new_node, array_type &prev_nodes, array_type &next_nodes)
concurrent_skip_list(const concurrent_skip_list &other, const allocator_type &alloc)
const_iterator lower_bound(const key_type &key) const
size_type unsafe_erase(const K &key)
const_range_type(const concurrent_skip_list &l)
range_type(range_type &r, split)
Dummy type that distinguishes splitting constructor from copy constructor.
iterator unsafe_erase(const_iterator first, const_iterator last)
void internal_move_assign(concurrent_skip_list &&other, std::false_type)
std::unique_lock< mutex_type > lock_type
friend bool operator==(const skip_list_iterator< T, M > &, const skip_list_iterator< T, U > &)
iterator internal_find(const K &key)
std::pair< iterator, bool > internal_insert(Args &&... args)
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_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type type
void delete_node(node_ptr node)
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
typename traits_type::value_compare value_compare
void set_next(size_type level, node_pointer next)
const_iterator find(const key_type &key) const
Copyright © 2005-2020 Intel Corporation. All Rights Reserved.
Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are
registered trademarks or trademarks of Intel Corporation or its
subsidiaries in the United States and other countries.
* Other names and brands may be claimed as the property of others.