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