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
pointer_type internal_find_position(size_type level, pointer_type &prev, const K &key, const comparator &cmp) const
static size_type calc_node_size(size_type height)
static const bool allow_multimapping
iterator unsafe_erase(iterator pos)
void deallocate_node(node_ptr node, size_type sz)
iterator lower_bound(const K &key)
iterator unsafe_erase(const_iterator pos)
const_iterator begin() const
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::pair< iterator, bool > insert(value_type &&value)
bool operator()(const K1 &first, const K2 &second) const
node_type unsafe_extract(const key_type &key)
const_range_type(const concurrent_skip_list &l)
iterator find(const K &key)
const_iterator lower_bound(const K &key) const
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)
skip_list_node & operator=(const skip_list_node &)=delete
concurrent_skip_list(concurrent_skip_list &&other, const allocator_type &alloc)
void allocator_copy_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
static iterator get_iterator(const_iterator it)
void allocator_move_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
std::pair< iterator, bool > insert(const value_type &value)
pointer operator->() const
Base class for types that should not be assigned.
const_iterator find(const K &key) const
size_type count(const K &key) const
atomic_node_pointer & my_next(size_type level)
iterator find(const key_type &key)
const value_type * const_pointer
const value_type & const_reference
const_iterator internal_find(const K &key) const
std::pair< iterator, bool > emplace(Args &&... args)
void swap(concurrent_skip_list &other)
bool fully_linked() const
void fill_prev_next_arrays(array_type &prev_nodes, array_type &next_nodes, node_ptr prev, const key_type &key, const comparator &cmp)
value_compare value_comp() const
void allocator_swap(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)
const_iterator end() const
void insert(std::initializer_list< value_type > init)
bool try_insert_node(node_ptr new_node, array_type &prev_nodes, array_type &next_nodes)
std::pair< iterator, iterator > equal_range(const K &key)
concurrent_skip_list(const concurrent_skip_list &other, const allocator_type &alloc)
concurrent_skip_list(InputIt first, InputIt last, const key_compare &comp=key_compare(), const allocator_type &alloc=allocator_type())
void swap(atomic< T > &lhs, atomic< T > &rhs)
typename concurrent_skip_list::const_iterator iterator
const_iterator lower_bound(const key_type &key) const
iterator unsafe_erase(const_iterator first, const_iterator last)
iterator upper_bound(const key_type &key)
typename traits_type::node_type node_type
iterator internal_find(const K &key)
typename std::conditional< is_const, typename node_type::const_pointer, typename node_type::pointer >::type pointer
std::pair< iterator, bool > internal_insert(Args &&... args)
typename std::allocator_traits< allocator_type >::template rebind_alloc< uint8_t > node_allocator_type
typename traits_type::value_type value_type
void delete_node(node_ptr node)
const_iterator cend() const
const key_compare & my_less_compare
concurrent_skip_list & operator=(const concurrent_skip_list &other)
typename traits_type::value_compare value_compare
aligned_storage_type my_val
typename concurrent_skip_list::iterator iterator
skip_list_iterator(node_type *n)
size_type unsafe_erase(const key_type &key)
iterator insert(const_iterator, value_type &&value)
std::ptrdiff_t difference_type
void internal_move_assign(concurrent_skip_list &&other, std::true_type)
typename allocator_traits_type::const_pointer const_pointer
void internal_copy(Iterator first, Iterator last)
concurrent_skip_list & operator=(std::initializer_list< value_type > il)
node_ptr create_node(Args &&... args)
key_compare key_comp() const
skip_list_iterator operator++(int)
skip_list_iterator(const skip_list_iterator< node_type, true > &other)
bool is_divisible() const
bool contains(const K &key) const
static constexpr size_type MAX_LEVEL
const_iterator upper_bound(const K &key) const
concurrent_skip_list(const concurrent_skip_list &other)
std::atomic_bool my_fullyLinked
iterator emplace_hint(const_iterator, Args &&... args)
#define __TBB_STATIC_ASSERT(condition, msg)
void set_next(size_type level, node_pointer next)
iterator insert(const_iterator, node_type &&nh)
void move(tbb_thread &t1, tbb_thread &t2)
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
size_type unsafe_erase(const K &key)
typename traits_type::random_level_generator_type random_level_generator_type
bool operator==(const skip_list_iterator< NodeType, is_const1 > &lhs, const skip_list_iterator< NodeType, is_const2 > &rhs)
const_range_type(const_range_type &r, split)
void internal_move_assign(concurrent_skip_list &&other, std::false_type)
node_pointer next(size_type level) const
std::array< node_ptr, MAX_LEVEL > array_type
typename node_type::value_type value_type
const_iterator find(const key_type &key) const
typename traits_type::key_type key_type
Dummy type that distinguishes splitting constructor from copy constructor.
allocator_type get_allocator() const
skip_list_iterator & operator++()
auto first(Container &c) -> decltype(begin(c))
std::geometric_distribution< size_t > distribution
skip_list_iterator< list_node_type, false > iterator
concurrent_skip_list(const key_compare &comp, const allocator_type &alloc=allocator_type())
The enumerable_thread_specific container.
std::unique_lock< mutex_type > lock_type
bool_constant< true > true_type
void internal_merge(SourceType &&source)
std::array< typename list_node_type::lock_type, MAX_LEVEL > lock_array
std::pair< const_iterator, const_iterator > equal_range(const K &key) const
typename std::aligned_storage< sizeof(value_type), alignof(value_type)>::type aligned_storage_type
static constexpr size_t max_level
const_range_type range() const
std::reverse_iterator< const_iterator > const_reverse_iterator
std::atomic< size_type > my_size
std::pair< iterator, iterator > equal_range(const key_type &key)
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
typename traits_type::allocator_type allocator_type
skip_list_iterator(const skip_list_iterator< node_type, false > &other)
bool try_lock_nodes(size_type height, array_type &prevs, array_type &next_nodes, lock_array &locks)
node_type unsafe_extract(const_iterator pos)
skip_list_iterator< list_node_type, true > const_iterator
const_iterator upper_bound(const key_type &key) const
typename traits_type::compare_type key_compare
std::reverse_iterator< iterator > reverse_iterator
std::forward_iterator_tag iterator_category
std::pair< node_ptr, node_ptr > internal_extract(const_iterator it)
skip_list_node(size_type levels)
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
range_type(const concurrent_skip_list &l)
iterator insert(const_iterator, const_reference value)
range_type(range_type &r, split)
typename std::conditional< is_const, typename node_type::const_reference, typename node_type::reference >::type reference
iterator upper_bound(const K &key)
friend bool operator!=(const skip_list_iterator< T, M > &, const skip_list_iterator< T, U > &)
friend bool operator==(const skip_list_iterator< T, M > &, const skip_list_iterator< T, U > &)
node_allocator_type my_node_allocator
size_type max_size() const
void internal_copy(const concurrent_skip_list &other)
auto last(Container &c) -> decltype(begin(c))
bool_constant< false > false_type
concurrent_geometric_level_generator()
concurrent_skip_list(concurrent_skip_list &&other)
std::atomic< node_pointer > atomic_node_pointer
skip_list_node< value_type, typename traits_type::mutex_type > list_node_type
typename concurrent_skip_list::value_type value_type
const atomic_node_pointer & my_next(size_type level) const
const value_type & const_reference
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
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)
std::pair< iterator, bool > insert(node_type &&nh)
void internal_move(concurrent_skip_list &&other)
typename allocator_traits_type::pointer pointer
concurrent_skip_list & operator=(concurrent_skip_list &&other)
not_greater_compare(const key_compare &less_compare)
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
std::allocator_traits< allocator_type > allocator_traits_type
std::ptrdiff_t difference_type
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 h
std::pair< const_iterator, const_iterator > equal_range(const key_type &key) const
typename concurrent_skip_list::size_type size_type
size_type count(const key_type &key) const
iterator lower_bound(const key_type &key)
reference operator*() const
void insert(InputIterator first, InputIterator last)
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.