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