Intel(R) Threading Building Blocks Doxygen Documentation version 4.2.3
Loading...
Searching...
No Matches
tbb::interface10::internal::concurrent_skip_list< Traits > Class Template Reference

#include <_concurrent_skip_list_impl.h>

Collaboration diagram for tbb::interface10::internal::concurrent_skip_list< Traits >:

Classes

class  const_range_type
 
struct  not_greater_compare
 
class  range_type
 

Public Member Functions

 concurrent_skip_list ()
 
 concurrent_skip_list (const key_compare &comp, const allocator_type &alloc=allocator_type())
 
template<class InputIt >
 concurrent_skip_list (InputIt first, InputIt last, const key_compare &comp=key_compare(), const allocator_type &alloc=allocator_type())
 
 concurrent_skip_list (const concurrent_skip_list &other)
 
 concurrent_skip_list (const concurrent_skip_list &other, const allocator_type &alloc)
 
 concurrent_skip_list (concurrent_skip_list &&other)
 
 concurrent_skip_list (concurrent_skip_list &&other, const allocator_type &alloc)
 
 ~concurrent_skip_list ()
 
concurrent_skip_listoperator= (const concurrent_skip_list &other)
 
concurrent_skip_listoperator= (concurrent_skip_list &&other)
 
concurrent_skip_listoperator= (std::initializer_list< value_type > il)
 
std::pair< iterator, bool > insert (const value_type &value)
 
std::pair< iterator, bool > insert (value_type &&value)
 
iterator insert (const_iterator, const_reference value)
 
iterator insert (const_iterator, value_type &&value)
 
template<typename InputIterator >
void insert (InputIterator first, InputIterator last)
 
void insert (std::initializer_list< value_type > init)
 
std::pair< iterator, bool > insert (node_type &&nh)
 
iterator insert (const_iterator, node_type &&nh)
 
template<typename... Args>
std::pair< iterator, bool > emplace (Args &&... args)
 
template<typename... Args>
iterator emplace_hint (const_iterator, Args &&... args)
 
iterator unsafe_erase (iterator pos)
 
iterator unsafe_erase (const_iterator pos)
 
template<typename K , typename = tbb::internal::is_transparent<key_compare, K>, typename = typename std::enable_if<!std::is_convertible<K, iterator>::value && !std::is_convertible<K, const_iterator>::value>::type>
size_type unsafe_erase (const K &key)
 
iterator unsafe_erase (const_iterator first, const_iterator last)
 
size_type unsafe_erase (const key_type &key)
 
node_type unsafe_extract (const_iterator pos)
 
node_type unsafe_extract (const key_type &key)
 
iterator lower_bound (const key_type &key)
 
const_iterator lower_bound (const key_type &key) const
 
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
iterator lower_bound (const K &key)
 
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
const_iterator lower_bound (const K &key) const
 
iterator upper_bound (const key_type &key)
 
const_iterator upper_bound (const key_type &key) const
 
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
iterator upper_bound (const K &key)
 
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
const_iterator upper_bound (const K &key) const
 
iterator find (const key_type &key)
 
const_iterator find (const key_type &key) const
 
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
iterator find (const K &key)
 
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
const_iterator find (const K &key) const
 
size_type count (const key_type &key) const
 
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
size_type count (const K &key) const
 
bool contains (const key_type &key) const
 
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
bool contains (const K &key) const
 
void clear () noexcept
 
iterator begin ()
 
const_iterator begin () const
 
const_iterator cbegin () const
 
iterator end ()
 
const_iterator end () const
 
const_iterator cend () const
 
size_type size () const
 
size_type max_size () const
 
bool empty () const
 
allocator_type get_allocator () const
 
void swap (concurrent_skip_list &other)
 
std::pair< iterator, iteratorequal_range (const key_type &key)
 
std::pair< const_iterator, const_iteratorequal_range (const key_type &key) const
 
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
std::pair< iterator, iteratorequal_range (const K &key)
 
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
std::pair< const_iterator, const_iteratorequal_range (const K &key) const
 
key_compare key_comp () const
 
value_compare value_comp () const
 
range_type range ()
 
const_range_type range () const
 

Static Public Attributes

static bool const allow_multimapping = traits_type::allow_multimapping
 

Protected Types

using traits_type = Traits
 
using allocator_type = typename traits_type::allocator_type
 
using allocator_traits_type = std::allocator_traits< allocator_type >
 
using key_compare = typename traits_type::compare_type
 
using value_compare = typename traits_type::value_compare
 
using key_type = typename traits_type::key_type
 
using value_type = typename traits_type::value_type
 
using node_type = typename traits_type::node_type
 
using list_node_type = skip_list_node< value_type, typename traits_type::mutex_type >
 
using iterator = skip_list_iterator< list_node_type, false >
 
using const_iterator = skip_list_iterator< list_node_type, true >
 
using reverse_iterator = std::reverse_iterator< iterator >
 
using const_reverse_iterator = std::reverse_iterator< const_iterator >
 
using reference = value_type &
 
using const_reference = const value_type &
 
using pointer = typename allocator_traits_type::pointer
 
using const_pointer = typename allocator_traits_type::const_pointer
 
using size_type = std::size_t
 
using difference_type = std::ptrdiff_t
 
using random_level_generator_type = typename traits_type::random_level_generator_type
 
using node_allocator_type = typename std::allocator_traits< allocator_type >::template rebind_alloc< uint8_t >
 
using node_allocator_traits = typename std::allocator_traits< allocator_type >::template rebind_traits< uint8_t >
 
using node_ptr = list_node_type *
 
using array_type = std::array< node_ptr, MAX_LEVEL >
 
using lock_array = std::array< typename list_node_type::lock_type, MAX_LEVEL >
 

Protected Member Functions

template<typename SourceType >
void internal_merge (SourceType &&source)
 

Static Protected Attributes

static constexpr size_type MAX_LEVEL = traits_type::MAX_LEVEL
 

Private Member Functions

void internal_move (concurrent_skip_list &&other)
 
template<typename K >
iterator internal_find (const K &key)
 
template<typename K >
const_iterator internal_find (const K &key) const
 
template<typename K >
size_type internal_count (const K &key) const
 
template<typename K , typename pointer_type , typename comparator >
pointer_type internal_find_position (size_type level, pointer_type &prev, const K &key, const comparator &cmp) const
 
template<typename comparator >
void fill_prev_next_arrays (array_type &prev_nodes, array_type &next_nodes, node_ptr prev, const key_type &key, const comparator &cmp)
 
template<typename comparator >
void fill_prev_next_by_ptr (array_type &prev_nodes, array_type &next_nodes, const_iterator it, const key_type &key, const comparator &cmp)
 
template<typename... Args>
std::pair< iterator, bool > internal_insert (Args &&... args)
 
std::pair< iterator, bool > internal_insert_node (node_ptr new_node)
 
bool try_insert_node (node_ptr new_node, array_type &prev_nodes, array_type &next_nodes)
 
bool try_lock_nodes (size_type height, array_type &prevs, array_type &next_nodes, lock_array &locks)
 
template<typename K , typename comparator >
const_iterator internal_get_bound (const K &key, const comparator &cmp) const
 
template<typename K , typename comparator >
iterator internal_get_bound (const K &key, const comparator &cmp)
 
std::pair< node_ptr, node_ptrinternal_extract (const_iterator it)
 
void internal_copy (const concurrent_skip_list &other)
 
template<typename Iterator >
void internal_copy (Iterator first, Iterator last)
 
size_type random_level ()
 
template<typename... Args>
node_ptr create_node (Args &&... args)
 
void create_dummy_head ()
 
template<bool is_dummy = false>
void delete_node (node_ptr node)
 
void deallocate_node (node_ptr node, size_type sz)
 
void delete_dummy_head ()
 
void internal_move_assign (concurrent_skip_list &&other, std::true_type)
 
void internal_move_assign (concurrent_skip_list &&other, std::false_type)
 

Static Private Member Functions

static const key_typeget_key (node_ptr n)
 
static size_type calc_node_size (size_type height)
 
static iterator get_iterator (const_iterator it)
 

Private Attributes

node_allocator_type my_node_allocator
 
key_compare my_compare
 
random_level_generator_type my_rnd_generator
 
node_ptr dummy_head
 
std::atomic< size_typemy_size
 

Friends

template<typename OtherTraits >
class concurrent_skip_list
 

Detailed Description

template<typename Traits>
class tbb::interface10::internal::concurrent_skip_list< Traits >

Definition at line 220 of file _concurrent_skip_list_impl.h.

Member Typedef Documentation

◆ allocator_traits_type

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::allocator_traits_type = std::allocator_traits<allocator_type>
protected

Definition at line 224 of file _concurrent_skip_list_impl.h.

◆ allocator_type

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::allocator_type = typename traits_type::allocator_type
protected

Definition at line 223 of file _concurrent_skip_list_impl.h.

◆ array_type

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::array_type = std::array<node_ptr, MAX_LEVEL>
protected

Definition at line 251 of file _concurrent_skip_list_impl.h.

◆ const_iterator

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::const_iterator = skip_list_iterator<list_node_type, true>
protected

Definition at line 233 of file _concurrent_skip_list_impl.h.

◆ const_pointer

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::const_pointer = typename allocator_traits_type::const_pointer
protected

Definition at line 240 of file _concurrent_skip_list_impl.h.

◆ const_reference

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::const_reference = const value_type&
protected

Definition at line 238 of file _concurrent_skip_list_impl.h.

◆ const_reverse_iterator

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::const_reverse_iterator = std::reverse_iterator<const_iterator>
protected

Definition at line 235 of file _concurrent_skip_list_impl.h.

◆ difference_type

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::difference_type = std::ptrdiff_t
protected

Definition at line 242 of file _concurrent_skip_list_impl.h.

◆ iterator

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::iterator = skip_list_iterator<list_node_type, false>
protected

Definition at line 232 of file _concurrent_skip_list_impl.h.

◆ key_compare

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::key_compare = typename traits_type::compare_type
protected

Definition at line 225 of file _concurrent_skip_list_impl.h.

◆ key_type

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::key_type = typename traits_type::key_type
protected

Definition at line 227 of file _concurrent_skip_list_impl.h.

◆ list_node_type

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::list_node_type = skip_list_node<value_type, typename traits_type::mutex_type>
protected

Definition at line 230 of file _concurrent_skip_list_impl.h.

◆ lock_array

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::lock_array = std::array<typename list_node_type::lock_type, MAX_LEVEL>
protected

Definition at line 252 of file _concurrent_skip_list_impl.h.

◆ node_allocator_traits

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::node_allocator_traits = typename std::allocator_traits<allocator_type>::template rebind_traits<uint8_t>
protected

Definition at line 246 of file _concurrent_skip_list_impl.h.

◆ node_allocator_type

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::node_allocator_type = typename std::allocator_traits<allocator_type>::template rebind_alloc<uint8_t>
protected

Definition at line 245 of file _concurrent_skip_list_impl.h.

◆ node_ptr

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::node_ptr = list_node_type*
protected

Definition at line 247 of file _concurrent_skip_list_impl.h.

◆ node_type

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::node_type = typename traits_type::node_type
protected

Definition at line 229 of file _concurrent_skip_list_impl.h.

◆ pointer

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::pointer = typename allocator_traits_type::pointer
protected

Definition at line 239 of file _concurrent_skip_list_impl.h.

◆ random_level_generator_type

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::random_level_generator_type = typename traits_type::random_level_generator_type
protected

Definition at line 244 of file _concurrent_skip_list_impl.h.

◆ reference

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::reference = value_type&
protected

Definition at line 237 of file _concurrent_skip_list_impl.h.

◆ reverse_iterator

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::reverse_iterator = std::reverse_iterator<iterator>
protected

Definition at line 234 of file _concurrent_skip_list_impl.h.

◆ size_type

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::size_type = std::size_t
protected

Definition at line 241 of file _concurrent_skip_list_impl.h.

◆ traits_type

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::traits_type = Traits
protected

Definition at line 222 of file _concurrent_skip_list_impl.h.

◆ value_compare

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::value_compare = typename traits_type::value_compare
protected

Definition at line 226 of file _concurrent_skip_list_impl.h.

◆ value_type

template<typename Traits >
using tbb::interface10::internal::concurrent_skip_list< Traits >::value_type = typename traits_type::value_type
protected

Definition at line 228 of file _concurrent_skip_list_impl.h.

Constructor & Destructor Documentation

◆ concurrent_skip_list() [1/7]

template<typename Traits >
tbb::interface10::internal::concurrent_skip_list< Traits >::concurrent_skip_list ( )
inline

Default constructor. Construct empty skip list.

Definition at line 260 of file _concurrent_skip_list_impl.h.

References tbb::interface10::internal::concurrent_skip_list< Traits >::create_dummy_head().

Here is the call graph for this function:

◆ concurrent_skip_list() [2/7]

template<typename Traits >
tbb::interface10::internal::concurrent_skip_list< Traits >::concurrent_skip_list ( const key_compare comp,
const allocator_type alloc = allocator_type() 
)
inlineexplicit

Definition at line 264 of file _concurrent_skip_list_impl.h.

References tbb::interface10::internal::concurrent_skip_list< Traits >::create_dummy_head().

Here is the call graph for this function:

◆ concurrent_skip_list() [3/7]

template<typename Traits >
template<class InputIt >
tbb::interface10::internal::concurrent_skip_list< Traits >::concurrent_skip_list ( InputIt  first,
InputIt  last,
const key_compare comp = key_compare(),
const allocator_type alloc = allocator_type() 
)
inline

Definition at line 271 of file _concurrent_skip_list_impl.h.

273 : my_node_allocator(alloc), my_compare(comp), my_size(0)
274 {
277 }
auto last(Container &c) -> decltype(begin(c))
auto first(Container &c) -> decltype(begin(c))
void internal_copy(const concurrent_skip_list &other)

References tbb::interface10::internal::concurrent_skip_list< Traits >::create_dummy_head(), tbb::internal::first(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_copy(), and tbb::internal::last().

Here is the call graph for this function:

◆ concurrent_skip_list() [4/7]

template<typename Traits >
tbb::interface10::internal::concurrent_skip_list< Traits >::concurrent_skip_list ( const concurrent_skip_list< Traits > &  other)
inline

Copy constructor

Definition at line 280 of file _concurrent_skip_list_impl.h.

281 : my_node_allocator(node_allocator_traits::select_on_container_copy_construction(other.get_allocator())),
282 my_compare(other.my_compare), my_rnd_generator(other.my_rnd_generator), my_size(0)
283 {
285 internal_copy(other);
286 __TBB_ASSERT(my_size == other.my_size, "Wrong size of copy-constructed container");
287 }
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition tbb_stddef.h:165

References __TBB_ASSERT, tbb::interface10::internal::concurrent_skip_list< Traits >::create_dummy_head(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_copy(), and tbb::interface10::internal::concurrent_skip_list< Traits >::my_size.

Here is the call graph for this function:

◆ concurrent_skip_list() [5/7]

template<typename Traits >
tbb::interface10::internal::concurrent_skip_list< Traits >::concurrent_skip_list ( const concurrent_skip_list< Traits > &  other,
const allocator_type alloc 
)
inline

Definition at line 289 of file _concurrent_skip_list_impl.h.

290 : my_node_allocator(alloc), my_compare(other.my_compare),
291 my_rnd_generator(other.my_rnd_generator), my_size(0)
292 {
294 internal_copy(other);
295 __TBB_ASSERT(my_size == other.my_size, "Wrong size of copy-constructed container");
296 }

References __TBB_ASSERT, tbb::interface10::internal::concurrent_skip_list< Traits >::create_dummy_head(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_copy(), and tbb::interface10::internal::concurrent_skip_list< Traits >::my_size.

Here is the call graph for this function:

◆ concurrent_skip_list() [6/7]

template<typename Traits >
tbb::interface10::internal::concurrent_skip_list< Traits >::concurrent_skip_list ( concurrent_skip_list< Traits > &&  other)
inline

Definition at line 298 of file _concurrent_skip_list_impl.h.

299 : my_node_allocator(std::move(other.my_node_allocator)), my_compare(other.my_compare),
300 my_rnd_generator(other.my_rnd_generator)
301 {
302 internal_move(std::move(other));
303 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_move(), and tbb::move().

Here is the call graph for this function:

◆ concurrent_skip_list() [7/7]

template<typename Traits >
tbb::interface10::internal::concurrent_skip_list< Traits >::concurrent_skip_list ( concurrent_skip_list< Traits > &&  other,
const allocator_type alloc 
)
inline

Definition at line 305 of file _concurrent_skip_list_impl.h.

306 : my_node_allocator(alloc), my_compare(other.my_compare),
307 my_rnd_generator(other.my_rnd_generator)
308 {
309 if (alloc == other.get_allocator()) {
310 internal_move(std::move(other));
311 } else {
312 my_size = 0;
314 internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()));
315 }
316 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::create_dummy_head(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_copy(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_move(), and tbb::interface10::internal::concurrent_skip_list< Traits >::my_size.

Here is the call graph for this function:

◆ ~concurrent_skip_list()

template<typename Traits >
tbb::interface10::internal::concurrent_skip_list< Traits >::~concurrent_skip_list ( )
inline

Definition at line 318 of file _concurrent_skip_list_impl.h.

References tbb::interface10::internal::concurrent_skip_list< Traits >::clear(), and tbb::interface10::internal::concurrent_skip_list< Traits >::delete_dummy_head().

Here is the call graph for this function:

Member Function Documentation

◆ begin() [1/2]

template<typename Traits >
iterator tbb::interface10::internal::concurrent_skip_list< Traits >::begin ( )
inline

Definition at line 543 of file _concurrent_skip_list_impl.h.

References tbb::interface10::internal::concurrent_skip_list< Traits >::dummy_head, and tbb::interface10::internal::skip_list_node< Value, Mutex >::next().

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::internal_copy().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ begin() [2/2]

template<typename Traits >
const_iterator tbb::interface10::internal::concurrent_skip_list< Traits >::begin ( ) const
inline

Definition at line 547 of file _concurrent_skip_list_impl.h.

547 {
548 return const_iterator(dummy_head->next(0));
549 }
skip_list_iterator< list_node_type, true > const_iterator

References tbb::interface10::internal::concurrent_skip_list< Traits >::dummy_head, and tbb::interface10::internal::skip_list_node< Value, Mutex >::next().

Here is the call graph for this function:

◆ calc_node_size()

template<typename Traits >
static size_type tbb::interface10::internal::concurrent_skip_list< Traits >::calc_node_size ( size_type  height)
inlinestaticprivate

Definition at line 955 of file _concurrent_skip_list_impl.h.

955 {
956 return sizeof(list_node_type) + height*sizeof(typename list_node_type::atomic_node_pointer);
957 }
skip_list_node< value_type, typename traits_type::mutex_type > list_node_type

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::create_dummy_head(), tbb::interface10::internal::concurrent_skip_list< Traits >::create_node(), and tbb::interface10::internal::concurrent_skip_list< Traits >::delete_node().

Here is the caller graph for this function:

◆ cbegin()

template<typename Traits >
const_iterator tbb::interface10::internal::concurrent_skip_list< Traits >::cbegin ( ) const
inline

Definition at line 551 of file _concurrent_skip_list_impl.h.

551 {
552 return const_iterator(dummy_head->next(0));
553 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::dummy_head, and tbb::interface10::internal::skip_list_node< Value, Mutex >::next().

Here is the call graph for this function:

◆ cend()

template<typename Traits >
const_iterator tbb::interface10::internal::concurrent_skip_list< Traits >::cend ( ) const
inline

Definition at line 563 of file _concurrent_skip_list_impl.h.

563 {
564 return const_iterator(nullptr);
565 }

◆ clear()

template<typename Traits >
void tbb::interface10::internal::concurrent_skip_list< Traits >::clear ( )
inlinenoexcept

Definition at line 526 of file _concurrent_skip_list_impl.h.

526 {
527 __TBB_ASSERT(dummy_head->height() > 0, NULL);
528
529 node_ptr current = dummy_head->next(0);
530 while (current) {
531 __TBB_ASSERT(current->height() > 0, NULL);
532 node_ptr next = current->next(0);
533 delete_node(current);
534 current = next;
535 }
536
537 my_size = 0;
538 for (size_type i = 0; i < dummy_head->height(); ++i) {
539 dummy_head->set_next(i, nullptr);
540 }
541 }
void set_next(size_type level, node_pointer next)

References __TBB_ASSERT, tbb::interface10::internal::concurrent_skip_list< Traits >::delete_node(), tbb::interface10::internal::concurrent_skip_list< Traits >::dummy_head, tbb::interface10::internal::skip_list_node< Value, Mutex >::height(), tbb::interface10::internal::concurrent_skip_list< Traits >::my_size, tbb::interface10::internal::skip_list_node< Value, Mutex >::next(), and tbb::interface10::internal::skip_list_node< Value, Mutex >::set_next().

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::internal_copy(), tbb::interface10::internal::concurrent_skip_list< Traits >::operator=(), tbb::interface10::internal::concurrent_skip_list< Traits >::operator=(), tbb::interface10::internal::concurrent_skip_list< Traits >::operator=(), and tbb::interface10::internal::concurrent_skip_list< Traits >::~concurrent_skip_list().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ contains() [1/2]

template<typename Traits >
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
bool tbb::interface10::internal::concurrent_skip_list< Traits >::contains ( const K &  key) const
inline

Definition at line 522 of file _concurrent_skip_list_impl.h.

522 {
523 return find(key) != end();
524 }
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

References tbb::interface10::internal::concurrent_skip_list< Traits >::end(), tbb::interface10::internal::concurrent_skip_list< Traits >::find(), and key.

Here is the call graph for this function:

◆ contains() [2/2]

template<typename Traits >
bool tbb::interface10::internal::concurrent_skip_list< Traits >::contains ( const key_type key) const
inline

Definition at line 517 of file _concurrent_skip_list_impl.h.

517 {
518 return find(key) != end();
519 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::end(), tbb::interface10::internal::concurrent_skip_list< Traits >::find(), and key.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::internal_merge().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ count() [1/2]

template<typename Traits >
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
size_type tbb::interface10::internal::concurrent_skip_list< Traits >::count ( const K &  key) const
inline

Definition at line 513 of file _concurrent_skip_list_impl.h.

513 {
514 return internal_count(key);
515 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_count(), and key.

Here is the call graph for this function:

◆ count() [2/2]

template<typename Traits >
size_type tbb::interface10::internal::concurrent_skip_list< Traits >::count ( const key_type key) const
inline

Definition at line 508 of file _concurrent_skip_list_impl.h.

508 {
509 return internal_count(key);
510 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_count(), and key.

Here is the call graph for this function:

◆ create_dummy_head()

template<typename Traits >
void tbb::interface10::internal::concurrent_skip_list< Traits >::create_dummy_head ( )
inlineprivate

Definition at line 989 of file _concurrent_skip_list_impl.h.

989 {
991
992 dummy_head = reinterpret_cast<node_ptr>(node_allocator_traits::allocate(my_node_allocator, sz));
993 // TODO: investigate linkage fail in debug without this workaround
994 auto max_level = MAX_LEVEL;
995
996 try {
997 node_allocator_traits::construct(my_node_allocator, dummy_head, max_level);
998 }
999 catch(...) {
1001 throw;
1002 }
1003 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::calc_node_size(), tbb::interface10::internal::concurrent_skip_list< Traits >::deallocate_node(), tbb::interface10::internal::concurrent_skip_list< Traits >::dummy_head, tbb::interface10::internal::concurrent_skip_list< Traits >::MAX_LEVEL, and tbb::interface10::internal::concurrent_skip_list< Traits >::my_node_allocator.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::concurrent_skip_list(), tbb::interface10::internal::concurrent_skip_list< Traits >::concurrent_skip_list(), tbb::interface10::internal::concurrent_skip_list< Traits >::concurrent_skip_list(), tbb::interface10::internal::concurrent_skip_list< Traits >::concurrent_skip_list(), tbb::interface10::internal::concurrent_skip_list< Traits >::concurrent_skip_list(), and tbb::interface10::internal::concurrent_skip_list< Traits >::concurrent_skip_list().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ create_node()

template<typename Traits >
template<typename... Args>
node_ptr tbb::interface10::internal::concurrent_skip_list< Traits >::create_node ( Args &&...  args)
inlineprivate

Creates new node

Definition at line 961 of file _concurrent_skip_list_impl.h.

961 {
962 size_type levels = random_level();
963
964 size_type sz = calc_node_size(levels);
965
966 node_ptr node = reinterpret_cast<node_ptr>(node_allocator_traits::allocate(my_node_allocator, sz));
967
968 try {
969 node_allocator_traits::construct(my_node_allocator, node, levels);
970
971 }
972 catch(...) {
973 deallocate_node(node, sz);
974 throw;
975 }
976
977 try {
978 node_allocator_traits::construct(my_node_allocator, node->storage(), std::forward<Args>(args)...);
979 }
980 catch (...) {
981 node_allocator_traits::destroy(my_node_allocator, node);
982 deallocate_node(node, sz);
983 throw;
984 }
985
986 return node;
987 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::calc_node_size(), tbb::interface10::internal::concurrent_skip_list< Traits >::deallocate_node(), tbb::interface10::internal::concurrent_skip_list< Traits >::my_node_allocator, tbb::interface10::internal::concurrent_skip_list< Traits >::random_level(), and tbb::interface10::internal::skip_list_node< Value, Mutex >::storage().

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::internal_insert().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ deallocate_node()

template<typename Traits >
void tbb::interface10::internal::concurrent_skip_list< Traits >::deallocate_node ( node_ptr  node,
size_type  sz 
)
inlineprivate

Definition at line 1016 of file _concurrent_skip_list_impl.h.

1016 {
1017 node_allocator_traits::deallocate(my_node_allocator, reinterpret_cast<uint8_t*>(node), sz);
1018 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::my_node_allocator.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::create_dummy_head(), tbb::interface10::internal::concurrent_skip_list< Traits >::create_node(), and tbb::interface10::internal::concurrent_skip_list< Traits >::delete_node().

Here is the caller graph for this function:

◆ delete_dummy_head()

template<typename Traits >
void tbb::interface10::internal::concurrent_skip_list< Traits >::delete_dummy_head ( )
inlineprivate

◆ delete_node()

template<typename Traits >
template<bool is_dummy = false>
void tbb::interface10::internal::concurrent_skip_list< Traits >::delete_node ( node_ptr  node)
inlineprivate

Definition at line 1006 of file _concurrent_skip_list_impl.h.

1006 {
1007 size_type sz = calc_node_size(node->height());
1008 // Destroy value
1009 if (!is_dummy) node_allocator_traits::destroy(my_node_allocator, node->storage());
1010 // Destroy node
1011 node_allocator_traits::destroy(my_node_allocator, node);
1012 // Deallocate memory
1013 deallocate_node(node, sz);
1014 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::calc_node_size(), tbb::interface10::internal::concurrent_skip_list< Traits >::deallocate_node(), tbb::interface10::internal::skip_list_node< Value, Mutex >::height(), tbb::interface10::internal::concurrent_skip_list< Traits >::my_node_allocator, and tbb::interface10::internal::skip_list_node< Value, Mutex >::storage().

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::clear(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_insert(), and tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ emplace()

template<typename Traits >
template<typename... Args>
std::pair< iterator, bool > tbb::interface10::internal::concurrent_skip_list< Traits >::emplace ( Args &&...  args)
inline

Definition at line 398 of file _concurrent_skip_list_impl.h.

398 {
399 return internal_insert(std::forward<Args>(args)...);
400 }
std::pair< iterator, bool > internal_insert(Args &&... args)

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_insert().

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::emplace_hint().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ emplace_hint()

template<typename Traits >
template<typename... Args>
iterator tbb::interface10::internal::concurrent_skip_list< Traits >::emplace_hint ( const_iterator  ,
Args &&...  args 
)
inline

Definition at line 403 of file _concurrent_skip_list_impl.h.

403 {
404 // Ignore hint
405 return emplace(std::forward<Args>(args)...).first;
406 }
std::pair< iterator, bool > emplace(Args &&... args)

References tbb::interface10::internal::concurrent_skip_list< Traits >::emplace().

Here is the call graph for this function:

◆ empty()

template<typename Traits >
bool tbb::interface10::internal::concurrent_skip_list< Traits >::empty ( ) const
inline

Definition at line 575 of file _concurrent_skip_list_impl.h.

575 {
576 return 0 == size();
577 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::size().

Here is the call graph for this function:

◆ end() [1/2]

◆ end() [2/2]

template<typename Traits >
const_iterator tbb::interface10::internal::concurrent_skip_list< Traits >::end ( ) const
inline

Definition at line 559 of file _concurrent_skip_list_impl.h.

559 {
560 return const_iterator(nullptr);
561 }

◆ equal_range() [1/4]

template<typename Traits >
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
std::pair< iterator, iterator > tbb::interface10::internal::concurrent_skip_list< Traits >::equal_range ( const K &  key)
inline

Definition at line 605 of file _concurrent_skip_list_impl.h.

605 {
606 return std::pair<iterator, iterator>(lower_bound(key), upper_bound(key));
607 }

References key, tbb::interface10::internal::concurrent_skip_list< Traits >::lower_bound(), and tbb::interface10::internal::concurrent_skip_list< Traits >::upper_bound().

Here is the call graph for this function:

◆ equal_range() [2/4]

template<typename Traits >
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
std::pair< const_iterator, const_iterator > tbb::interface10::internal::concurrent_skip_list< Traits >::equal_range ( const K &  key) const
inline

Definition at line 610 of file _concurrent_skip_list_impl.h.

610 {
611 return std::pair<const_iterator, const_iterator>(lower_bound(key), upper_bound(key));
612 }

References key, tbb::interface10::internal::concurrent_skip_list< Traits >::lower_bound(), and tbb::interface10::internal::concurrent_skip_list< Traits >::upper_bound().

Here is the call graph for this function:

◆ equal_range() [3/4]

template<typename Traits >
std::pair< iterator, iterator > tbb::interface10::internal::concurrent_skip_list< Traits >::equal_range ( const key_type key)
inline

Definition at line 596 of file _concurrent_skip_list_impl.h.

596 {
597 return std::pair<iterator, iterator>(lower_bound(key), upper_bound(key));
598 }

References key, tbb::interface10::internal::concurrent_skip_list< Traits >::lower_bound(), and tbb::interface10::internal::concurrent_skip_list< Traits >::upper_bound().

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::internal_count(), tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase(), and tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ equal_range() [4/4]

template<typename Traits >
std::pair< const_iterator, const_iterator > tbb::interface10::internal::concurrent_skip_list< Traits >::equal_range ( const key_type key) const
inline

Definition at line 600 of file _concurrent_skip_list_impl.h.

600 {
601 return std::pair<const_iterator, const_iterator>(lower_bound(key), upper_bound(key));
602 }

References key, tbb::interface10::internal::concurrent_skip_list< Traits >::lower_bound(), and tbb::interface10::internal::concurrent_skip_list< Traits >::upper_bound().

Here is the call graph for this function:

◆ fill_prev_next_arrays()

template<typename Traits >
template<typename comparator >
void tbb::interface10::internal::concurrent_skip_list< Traits >::fill_prev_next_arrays ( array_type prev_nodes,
array_type next_nodes,
node_ptr  prev,
const key_type key,
const comparator &  cmp 
)
inlineprivate

Definition at line 737 of file _concurrent_skip_list_impl.h.

738 {
739 prev_nodes.fill(dummy_head);
740 next_nodes.fill(nullptr);
741
742 for (size_type h = prev->height(); h > 0; --h) {
743 node_ptr next = internal_find_position(h - 1, prev, key, cmp);
744 prev_nodes[h - 1] = prev;
745 next_nodes[h - 1] = next;
746 }
747 }
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
pointer_type internal_find_position(size_type level, pointer_type &prev, const K &key, const comparator &cmp) const

References tbb::interface10::internal::concurrent_skip_list< Traits >::dummy_head, h, tbb::interface10::internal::skip_list_node< Value, Mutex >::height(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_find_position(), and key.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::internal_insert_node().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ fill_prev_next_by_ptr()

template<typename Traits >
template<typename comparator >
void tbb::interface10::internal::concurrent_skip_list< Traits >::fill_prev_next_by_ptr ( array_type prev_nodes,
array_type next_nodes,
const_iterator  it,
const key_type key,
const comparator &  cmp 
)
inlineprivate

Definition at line 750 of file _concurrent_skip_list_impl.h.

751 {
752 node_ptr prev = dummy_head;
753 node_ptr erase_node = it.my_node_ptr;
754 size_type node_height = erase_node->height();
755
756 for (size_type h = prev->height(); h >= node_height; --h) {
757 internal_find_position(h - 1, prev, key, cmp);
758 }
759
760 for (size_type h = node_height; h > 0; --h) {
761 node_ptr curr = prev->next(h - 1);
762 while (const_iterator(curr) != it) {
763 prev = curr;
764 curr = prev->next(h - 1);
765 }
766 prev_nodes[h - 1] = prev;
767 }
768
769 std::fill(next_nodes.begin(), next_nodes.begin() + node_height, erase_node);
770 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::dummy_head, h, tbb::interface10::internal::skip_list_node< Value, Mutex >::height(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_find_position(), key, tbb::interface10::internal::skip_list_iterator< NodeType, is_const >::my_node_ptr, and tbb::interface10::internal::skip_list_node< Value, Mutex >::next().

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::internal_extract().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ find() [1/4]

template<typename Traits >
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
iterator tbb::interface10::internal::concurrent_skip_list< Traits >::find ( const K &  key)
inline

Definition at line 499 of file _concurrent_skip_list_impl.h.

499 {
500 return internal_find(key);
501 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_find(), and key.

Here is the call graph for this function:

◆ find() [2/4]

template<typename Traits >
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
const_iterator tbb::interface10::internal::concurrent_skip_list< Traits >::find ( const K &  key) const
inline

Definition at line 504 of file _concurrent_skip_list_impl.h.

504 {
505 return internal_find(key);
506 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_find(), and key.

Here is the call graph for this function:

◆ find() [3/4]

template<typename Traits >
iterator tbb::interface10::internal::concurrent_skip_list< Traits >::find ( const key_type key)
inline

Definition at line 490 of file _concurrent_skip_list_impl.h.

490 {
491 return internal_find(key);
492 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_find(), and key.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::contains(), tbb::interface10::internal::concurrent_skip_list< Traits >::contains(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_count(), and tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_extract().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ find() [4/4]

template<typename Traits >
const_iterator tbb::interface10::internal::concurrent_skip_list< Traits >::find ( const key_type key) const
inline

Definition at line 494 of file _concurrent_skip_list_impl.h.

494 {
495 return internal_find(key);
496 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_find(), and key.

Here is the call graph for this function:

◆ get_allocator()

template<typename Traits >
allocator_type tbb::interface10::internal::concurrent_skip_list< Traits >::get_allocator ( ) const
inline

◆ get_iterator()

template<typename Traits >
static iterator tbb::interface10::internal::concurrent_skip_list< Traits >::get_iterator ( const_iterator  it)
inlinestaticprivate

Definition at line 1024 of file _concurrent_skip_list_impl.h.

1024 {
1025 return iterator(it.my_node_ptr);
1026 }

References tbb::interface10::internal::skip_list_iterator< NodeType, is_const >::my_node_ptr.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase(), and tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase().

Here is the caller graph for this function:

◆ get_key()

template<typename Traits >
static const key_type & tbb::interface10::internal::concurrent_skip_list< Traits >::get_key ( node_ptr  n)
inlinestaticprivate

Definition at line 686 of file _concurrent_skip_list_impl.h.

686 {
687 __TBB_ASSERT(n, NULL);
688 return traits_type::get_key(n->value());
689 }

References __TBB_ASSERT, and tbb::interface10::internal::skip_list_node< Value, Mutex >::value().

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::internal_extract(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_find_position(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_insert_node(), and tbb::interface10::internal::concurrent_skip_list< Traits >::try_insert_node().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ insert() [1/8]

template<typename Traits >
std::pair< iterator, bool > tbb::interface10::internal::concurrent_skip_list< Traits >::insert ( const value_type value)
inline

Definition at line 353 of file _concurrent_skip_list_impl.h.

353 {
354 return internal_insert(value);
355 }
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

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_insert(), and value.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::insert(), tbb::interface10::internal::concurrent_skip_list< Traits >::insert(), tbb::interface10::internal::concurrent_skip_list< Traits >::insert(), tbb::interface10::internal::concurrent_skip_list< Traits >::insert(), tbb::interface10::internal::concurrent_skip_list< Traits >::insert(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_copy(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_merge(), and tbb::interface10::internal::concurrent_skip_list< Traits >::operator=().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ insert() [2/8]

template<typename Traits >
iterator tbb::interface10::internal::concurrent_skip_list< Traits >::insert ( const_iterator  ,
const_reference  value 
)
inline

Definition at line 361 of file _concurrent_skip_list_impl.h.

361 {
362 // Ignore hint
363 return insert(value).first;
364 }
std::pair< iterator, bool > insert(const value_type &value)

References tbb::interface10::internal::concurrent_skip_list< Traits >::insert(), and value.

Here is the call graph for this function:

◆ insert() [3/8]

template<typename Traits >
iterator tbb::interface10::internal::concurrent_skip_list< Traits >::insert ( const_iterator  ,
node_type &&  nh 
)
inline

Definition at line 392 of file _concurrent_skip_list_impl.h.

392 {
393 // Ignore hint
394 return insert(std::move(nh)).first;
395 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::insert().

Here is the call graph for this function:

◆ insert() [4/8]

template<typename Traits >
iterator tbb::interface10::internal::concurrent_skip_list< Traits >::insert ( const_iterator  ,
value_type &&  value 
)
inline

Definition at line 366 of file _concurrent_skip_list_impl.h.

366 {
367 // Ignore hint
368 return insert(std::move(value)).first;
369 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::insert(), and value.

Here is the call graph for this function:

◆ insert() [5/8]

template<typename Traits >
template<typename InputIterator >
void tbb::interface10::internal::concurrent_skip_list< Traits >::insert ( InputIterator  first,
InputIterator  last 
)
inline

Definition at line 372 of file _concurrent_skip_list_impl.h.

372 {
373 for (InputIterator it = first; it != last; ++it)
374 insert(*it);
375 }

References tbb::internal::first(), tbb::interface10::internal::concurrent_skip_list< Traits >::insert(), and tbb::internal::last().

Here is the call graph for this function:

◆ insert() [6/8]

template<typename Traits >
std::pair< iterator, bool > tbb::interface10::internal::concurrent_skip_list< Traits >::insert ( node_type &&  nh)
inline

Definition at line 381 of file _concurrent_skip_list_impl.h.

381 {
382 if(!nh.empty()) {
383 std::pair<iterator, bool> insert_result = internal_insert_node(nh.my_node);
384 if(insert_result.second) {
385 nh.deactivate();
386 }
387 return insert_result;
388 }
389 return std::pair<iterator, bool>(end(), false);
390 }
std::pair< iterator, bool > internal_insert_node(node_ptr new_node)

References tbb::interface10::internal::concurrent_skip_list< Traits >::end(), and tbb::interface10::internal::concurrent_skip_list< Traits >::internal_insert_node().

Here is the call graph for this function:

◆ insert() [7/8]

template<typename Traits >
void tbb::interface10::internal::concurrent_skip_list< Traits >::insert ( std::initializer_list< value_type init)
inline

Definition at line 377 of file _concurrent_skip_list_impl.h.

377 {
378 insert(init.begin(), init.end());
379 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::insert().

Here is the call graph for this function:

◆ insert() [8/8]

template<typename Traits >
std::pair< iterator, bool > tbb::interface10::internal::concurrent_skip_list< Traits >::insert ( value_type &&  value)
inline

Definition at line 357 of file _concurrent_skip_list_impl.h.

357 {
358 return internal_insert(std::move(value));
359 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_insert(), and value.

Here is the call graph for this function:

◆ internal_copy() [1/2]

◆ internal_copy() [2/2]

template<typename Traits >
template<typename Iterator >
void tbb::interface10::internal::concurrent_skip_list< Traits >::internal_copy ( Iterator  first,
Iterator  last 
)
inlineprivate

Definition at line 937 of file _concurrent_skip_list_impl.h.

937 {
938 clear();
939 try {
940 for (auto it = first; it != last; ++it)
941 insert(*it);
942 }
943 catch (...) {
944 clear();
946 throw;
947 }
948 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::clear(), tbb::interface10::internal::concurrent_skip_list< Traits >::delete_dummy_head(), tbb::internal::first(), tbb::interface10::internal::concurrent_skip_list< Traits >::insert(), and tbb::internal::last().

Here is the call graph for this function:

◆ internal_count()

template<typename Traits >
template<typename K >
size_type tbb::interface10::internal::concurrent_skip_list< Traits >::internal_count ( const K &  key) const
inlineprivate

Definition at line 704 of file _concurrent_skip_list_impl.h.

704 {
705 if (allow_multimapping) {
706 std::pair<const_iterator, const_iterator> range = equal_range(key);
707 return std::distance(range.first, range.second);
708 }
709 return (find(key) == end()) ? size_type(0) : size_type(1);
710 }
std::pair< iterator, iterator > equal_range(const key_type &key)

References tbb::interface10::internal::concurrent_skip_list< Traits >::allow_multimapping, tbb::interface10::internal::concurrent_skip_list< Traits >::end(), tbb::interface10::internal::concurrent_skip_list< Traits >::equal_range(), tbb::interface10::internal::concurrent_skip_list< Traits >::find(), key, and tbb::interface10::internal::concurrent_skip_list< Traits >::range().

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::count(), and tbb::interface10::internal::concurrent_skip_list< Traits >::count().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ internal_extract()

template<typename Traits >
std::pair< node_ptr, node_ptr > tbb::interface10::internal::concurrent_skip_list< Traits >::internal_extract ( const_iterator  it)
inlineprivate

Definition at line 880 of file _concurrent_skip_list_impl.h.

880 {
881 if ( it != end() ) {
882 key_type key = traits_type::get_key(*it);
883 __TBB_ASSERT(dummy_head->height() > 0, NULL);
884
885 array_type prev_nodes;
886 array_type next_nodes;
887
888 fill_prev_next_by_ptr(prev_nodes, next_nodes, it, key, my_compare);
889
890 node_ptr erase_node = next_nodes[0];
891 __TBB_ASSERT(erase_node != nullptr, NULL);
892 node_ptr next_node = erase_node->next(0);
893
894 if (!my_compare(key, get_key(erase_node))) {
895 for(size_type level = 0; level < erase_node->height(); ++level) {
896 __TBB_ASSERT(prev_nodes[level]->height() > level, NULL);
897 __TBB_ASSERT(next_nodes[level] == erase_node, NULL);
898 prev_nodes[level]->set_next(level, erase_node->next(level));
899 }
900 --my_size;
901 return std::pair<node_ptr, node_ptr>(erase_node, next_node);
902 }
903 }
904 return std::pair<node_ptr, node_ptr>(nullptr, nullptr);
905 }
void fill_prev_next_by_ptr(array_type &prev_nodes, array_type &next_nodes, const_iterator it, const key_type &key, const comparator &cmp)

References __TBB_ASSERT, tbb::interface10::internal::concurrent_skip_list< Traits >::dummy_head, tbb::interface10::internal::concurrent_skip_list< Traits >::end(), tbb::interface10::internal::concurrent_skip_list< Traits >::fill_prev_next_by_ptr(), tbb::interface10::internal::concurrent_skip_list< Traits >::get_key(), tbb::interface10::internal::skip_list_node< Value, Mutex >::height(), key, tbb::interface10::internal::concurrent_skip_list< Traits >::my_compare, tbb::interface10::internal::concurrent_skip_list< Traits >::my_size, and tbb::interface10::internal::skip_list_node< Value, Mutex >::next().

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase(), and tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_extract().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ internal_find() [1/2]

template<typename Traits >
template<typename K >
iterator tbb::interface10::internal::concurrent_skip_list< Traits >::internal_find ( const K &  key)
inlineprivate

Definition at line 692 of file _concurrent_skip_list_impl.h.

692 {
694 return (it == end() || my_compare(key, traits_type::get_key(*it))) ? end() : it;
695 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::end(), key, tbb::interface10::internal::concurrent_skip_list< Traits >::lower_bound(), and tbb::interface10::internal::concurrent_skip_list< Traits >::my_compare.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::find(), tbb::interface10::internal::concurrent_skip_list< Traits >::find(), tbb::interface10::internal::concurrent_skip_list< Traits >::find(), and tbb::interface10::internal::concurrent_skip_list< Traits >::find().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ internal_find() [2/2]

template<typename Traits >
template<typename K >
const_iterator tbb::interface10::internal::concurrent_skip_list< Traits >::internal_find ( const K &  key) const
inlineprivate

Definition at line 698 of file _concurrent_skip_list_impl.h.

698 {
700 return (it == end() || my_compare(key, traits_type::get_key(*it))) ? end() : it;
701 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::end(), key, tbb::interface10::internal::concurrent_skip_list< Traits >::lower_bound(), and tbb::interface10::internal::concurrent_skip_list< Traits >::my_compare.

Here is the call graph for this function:

◆ internal_find_position()

template<typename Traits >
template<typename K , typename pointer_type , typename comparator >
pointer_type tbb::interface10::internal::concurrent_skip_list< Traits >::internal_find_position ( size_type  level,
pointer_type &  prev,
const K &  key,
const comparator &  cmp 
) const
inlineprivate

Finds position on the

Parameters
levelusing
cmp
level- on which level search prev node
prev- pointer to the start node to search
key- key to search
cmp- callable object to compare two objects (my_compare member is default comparator)
Returns
pointer to the node which is not satisfy the comparison with
Parameters
key

Definition at line 722 of file _concurrent_skip_list_impl.h.

723 {
724 __TBB_ASSERT(level < prev->height(), "Wrong level to find position");
725 pointer_type curr = prev->next(level);
726
727 while (curr && cmp(get_key(curr), key)) {
728 prev = curr;
729 __TBB_ASSERT(level < prev->height(), NULL);
730 curr = prev->next(level);
731 }
732
733 return curr;
734 }

References __TBB_ASSERT, tbb::interface10::internal::concurrent_skip_list< Traits >::get_key(), and key.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::fill_prev_next_arrays(), tbb::interface10::internal::concurrent_skip_list< Traits >::fill_prev_next_by_ptr(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_get_bound(), and tbb::interface10::internal::concurrent_skip_list< Traits >::internal_get_bound().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ internal_get_bound() [1/2]

template<typename Traits >
template<typename K , typename comparator >
iterator tbb::interface10::internal::concurrent_skip_list< Traits >::internal_get_bound ( const K &  key,
const comparator &  cmp 
)
inlineprivate

Definition at line 867 of file _concurrent_skip_list_impl.h.

867 {
868 node_ptr prev = dummy_head;
869 __TBB_ASSERT(dummy_head->height() > 0, NULL);
870 node_ptr next = nullptr;
871
872 for (size_type h = prev->height(); h > 0; --h) {
873 next = internal_find_position(h - 1, prev, key, cmp);
874 }
875
876 return iterator(next);
877 }

References __TBB_ASSERT, tbb::interface10::internal::concurrent_skip_list< Traits >::dummy_head, h, tbb::interface10::internal::skip_list_node< Value, Mutex >::height(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_find_position(), and key.

Here is the call graph for this function:

◆ internal_get_bound() [2/2]

template<typename Traits >
template<typename K , typename comparator >
const_iterator tbb::interface10::internal::concurrent_skip_list< Traits >::internal_get_bound ( const K &  key,
const comparator &  cmp 
) const
inlineprivate

Definition at line 854 of file _concurrent_skip_list_impl.h.

854 {
855 node_ptr prev = dummy_head;
856 __TBB_ASSERT(dummy_head->height() > 0, NULL);
857 node_ptr next = nullptr;
858
859 for (size_type h = prev->height(); h > 0; --h) {
860 next = internal_find_position(h - 1, prev, key, cmp);
861 }
862
863 return const_iterator(next);
864 }

References __TBB_ASSERT, tbb::interface10::internal::concurrent_skip_list< Traits >::dummy_head, h, tbb::interface10::internal::skip_list_node< Value, Mutex >::height(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_find_position(), and key.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::lower_bound(), tbb::interface10::internal::concurrent_skip_list< Traits >::lower_bound(), tbb::interface10::internal::concurrent_skip_list< Traits >::lower_bound(), tbb::interface10::internal::concurrent_skip_list< Traits >::lower_bound(), tbb::interface10::internal::concurrent_skip_list< Traits >::upper_bound(), tbb::interface10::internal::concurrent_skip_list< Traits >::upper_bound(), tbb::interface10::internal::concurrent_skip_list< Traits >::upper_bound(), and tbb::interface10::internal::concurrent_skip_list< Traits >::upper_bound().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ internal_insert()

template<typename Traits >
template<typename... Args>
std::pair< iterator, bool > tbb::interface10::internal::concurrent_skip_list< Traits >::internal_insert ( Args &&...  args)
inlineprivate

Definition at line 773 of file _concurrent_skip_list_impl.h.

773 {
774 node_ptr new_node = create_node(std::forward<Args>(args)...);
775 std::pair<iterator, bool> insert_result = internal_insert_node(new_node);
776 if(!insert_result.second) {
777 delete_node(new_node);
778 }
779 return insert_result;
780 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::create_node(), tbb::interface10::internal::concurrent_skip_list< Traits >::delete_node(), and tbb::interface10::internal::concurrent_skip_list< Traits >::internal_insert_node().

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::emplace(), tbb::interface10::internal::concurrent_skip_list< Traits >::insert(), and tbb::interface10::internal::concurrent_skip_list< Traits >::insert().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ internal_insert_node()

template<typename Traits >
std::pair< iterator, bool > tbb::interface10::internal::concurrent_skip_list< Traits >::internal_insert_node ( node_ptr  new_node)
inlineprivate

Definition at line 782 of file _concurrent_skip_list_impl.h.

782 {
783 array_type prev_nodes;
784 array_type next_nodes;
785 __TBB_ASSERT(dummy_head->height() >= new_node->height(), "Wrong height for new node");
786
787 do {
788 if (allow_multimapping) {
789 fill_prev_next_arrays(prev_nodes, next_nodes, dummy_head, get_key(new_node),
790 not_greater_compare(my_compare));
791 } else {
792 fill_prev_next_arrays(prev_nodes, next_nodes, dummy_head, get_key(new_node), my_compare);
793 }
794
795 node_ptr next = next_nodes[0];
796 if (next && !allow_multimapping && !my_compare(get_key(new_node), get_key(next))) {
797 // TODO: do we really need to wait?
798 while (!next->fully_linked()) {
799 // TODO: atomic backoff
800 }
801
802 return std::pair<iterator, bool>(iterator(next), false);
803 }
804 __TBB_ASSERT(allow_multimapping || !next || my_compare(get_key(new_node), get_key(next)),
805 "Wrong elements order");
806
807 } while (!try_insert_node(new_node, prev_nodes, next_nodes));
808
809 __TBB_ASSERT(new_node, NULL);
810 return std::pair<iterator, bool>(iterator(new_node), true);
811 }
bool try_insert_node(node_ptr new_node, array_type &prev_nodes, array_type &next_nodes)
void fill_prev_next_arrays(array_type &prev_nodes, array_type &next_nodes, node_ptr prev, const key_type &key, const comparator &cmp)

References __TBB_ASSERT, tbb::interface10::internal::concurrent_skip_list< Traits >::allow_multimapping, tbb::interface10::internal::concurrent_skip_list< Traits >::dummy_head, tbb::interface10::internal::concurrent_skip_list< Traits >::fill_prev_next_arrays(), tbb::interface10::internal::skip_list_node< Value, Mutex >::fully_linked(), tbb::interface10::internal::concurrent_skip_list< Traits >::get_key(), tbb::interface10::internal::skip_list_node< Value, Mutex >::height(), tbb::interface10::internal::concurrent_skip_list< Traits >::my_compare, and tbb::interface10::internal::concurrent_skip_list< Traits >::try_insert_node().

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::insert(), and tbb::interface10::internal::concurrent_skip_list< Traits >::internal_insert().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ internal_merge()

template<typename Traits >
template<typename SourceType >
void tbb::interface10::internal::concurrent_skip_list< Traits >::internal_merge ( SourceType &&  source)
inlineprotected

Definition at line 909 of file _concurrent_skip_list_impl.h.

909 {
910 using source_type = typename std::decay<SourceType>::type;
911 using source_iterator = typename source_type::iterator;
912 __TBB_STATIC_ASSERT((std::is_same<node_type, typename source_type::node_type>::value), "Incompatible containers cannot be merged");
913
914 for(source_iterator it = source.begin(); it != source.end();) {
915 source_iterator where = it++;
916 if (allow_multimapping || !contains(traits_type::get_key(*where))) {
917 std::pair<node_ptr, node_ptr> extract_result = source.internal_extract(where);
918
919 //If the insertion fails - return the node into source
920 node_type handle(extract_result.first);
921 __TBB_ASSERT(!handle.empty(), "Extracted handle in merge is empty");
922
923 if (!insert(std::move(handle)).second) {
924 source.insert(std::move(handle));
925 }
926 handle.deactivate();
927 }
928 }
929 }
#define __TBB_STATIC_ASSERT(condition, msg)
Definition tbb_stddef.h:553

References __TBB_ASSERT, __TBB_STATIC_ASSERT, tbb::interface10::internal::concurrent_skip_list< Traits >::allow_multimapping, tbb::interface10::internal::concurrent_skip_list< Traits >::contains(), and tbb::interface10::internal::concurrent_skip_list< Traits >::insert().

Here is the call graph for this function:

◆ internal_move()

template<typename Traits >
void tbb::interface10::internal::concurrent_skip_list< Traits >::internal_move ( concurrent_skip_list< Traits > &&  other)
inlineprivate

Definition at line 677 of file _concurrent_skip_list_impl.h.

677 {
678 dummy_head = other.dummy_head;
679 other.dummy_head = nullptr;
680 other.create_dummy_head();
681
682 my_size = other.my_size.load();
683 other.my_size = 0;
684 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::dummy_head, and tbb::interface10::internal::concurrent_skip_list< Traits >::my_size.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::concurrent_skip_list(), tbb::interface10::internal::concurrent_skip_list< Traits >::concurrent_skip_list(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_move_assign(), and tbb::interface10::internal::concurrent_skip_list< Traits >::internal_move_assign().

Here is the caller graph for this function:

◆ internal_move_assign() [1/2]

template<typename Traits >
void tbb::interface10::internal::concurrent_skip_list< Traits >::internal_move_assign ( concurrent_skip_list< Traits > &&  other,
std::false_type   
)
inlineprivate

Definition at line 1034 of file _concurrent_skip_list_impl.h.

1034 {
1035 if (my_node_allocator == other.my_node_allocator) {
1037 internal_move(std::move(other));
1038 } else {
1039 internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()));
1040 }
1041 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::delete_dummy_head(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_copy(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_move(), and tbb::interface10::internal::concurrent_skip_list< Traits >::my_node_allocator.

Here is the call graph for this function:

◆ internal_move_assign() [2/2]

template<typename Traits >
void tbb::interface10::internal::concurrent_skip_list< Traits >::internal_move_assign ( concurrent_skip_list< Traits > &&  other,
std::true_type   
)
inlineprivate

Definition at line 1028 of file _concurrent_skip_list_impl.h.

1028 {
1030 tbb::internal::allocator_move_assignment(my_node_allocator, other.my_node_allocator, std::true_type());
1031 internal_move(std::move(other));
1032 }
void allocator_move_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)

References tbb::internal::allocator_move_assignment(), tbb::interface10::internal::concurrent_skip_list< Traits >::delete_dummy_head(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_move(), and tbb::interface10::internal::concurrent_skip_list< Traits >::my_node_allocator.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::operator=().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ key_comp()

template<typename Traits >
key_compare tbb::interface10::internal::concurrent_skip_list< Traits >::key_comp ( ) const
inline

◆ lower_bound() [1/4]

template<typename Traits >
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
iterator tbb::interface10::internal::concurrent_skip_list< Traits >::lower_bound ( const K &  key)
inline

Definition at line 463 of file _concurrent_skip_list_impl.h.

463 {
465 }
const_iterator internal_get_bound(const K &key, const comparator &cmp) const

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_get_bound(), key, and tbb::interface10::internal::concurrent_skip_list< Traits >::my_compare.

Here is the call graph for this function:

◆ lower_bound() [2/4]

template<typename Traits >
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
const_iterator tbb::interface10::internal::concurrent_skip_list< Traits >::lower_bound ( const K &  key) const
inline

Definition at line 468 of file _concurrent_skip_list_impl.h.

468 {
470 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_get_bound(), key, and tbb::interface10::internal::concurrent_skip_list< Traits >::my_compare.

Here is the call graph for this function:

◆ lower_bound() [3/4]

◆ lower_bound() [4/4]

template<typename Traits >
const_iterator tbb::interface10::internal::concurrent_skip_list< Traits >::lower_bound ( const key_type key) const
inline

Definition at line 458 of file _concurrent_skip_list_impl.h.

458 {
460 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_get_bound(), key, and tbb::interface10::internal::concurrent_skip_list< Traits >::my_compare.

Here is the call graph for this function:

◆ max_size()

template<typename Traits >
size_type tbb::interface10::internal::concurrent_skip_list< Traits >::max_size ( ) const
inline

◆ operator=() [1/3]

template<typename Traits >
concurrent_skip_list & tbb::interface10::internal::concurrent_skip_list< Traits >::operator= ( concurrent_skip_list< Traits > &&  other)
inline

Definition at line 335 of file _concurrent_skip_list_impl.h.

335 {
336 if (this != &other) {
337 using pocma_type = typename node_allocator_traits::propagate_on_container_move_assignment;
338 clear();
339 my_compare = other.my_compare;
340 my_rnd_generator = other.my_rnd_generator;
341 internal_move_assign(std::move(other), pocma_type());
342 }
343 return *this;
344 }
void internal_move_assign(concurrent_skip_list &&other, std::true_type)

References tbb::interface10::internal::concurrent_skip_list< Traits >::clear(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_move_assign(), tbb::interface10::internal::concurrent_skip_list< Traits >::my_compare, and tbb::interface10::internal::concurrent_skip_list< Traits >::my_rnd_generator.

Here is the call graph for this function:

◆ operator=() [2/3]

template<typename Traits >
concurrent_skip_list & tbb::interface10::internal::concurrent_skip_list< Traits >::operator= ( const concurrent_skip_list< Traits > &  other)
inline

Definition at line 323 of file _concurrent_skip_list_impl.h.

323 {
324 if (this != &other) {
325 using pocca_type = typename node_allocator_traits::propagate_on_container_copy_assignment;
326 clear();
327 tbb::internal::allocator_copy_assignment(my_node_allocator, other.my_node_allocator, pocca_type());
328 my_compare = other.my_compare;
329 my_rnd_generator = other.my_rnd_generator;
330 internal_copy(other);
331 }
332 return *this;
333 }
void allocator_copy_assignment(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)

References tbb::internal::allocator_copy_assignment(), tbb::interface10::internal::concurrent_skip_list< Traits >::clear(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_copy(), tbb::interface10::internal::concurrent_skip_list< Traits >::my_compare, tbb::interface10::internal::concurrent_skip_list< Traits >::my_node_allocator, and tbb::interface10::internal::concurrent_skip_list< Traits >::my_rnd_generator.

Here is the call graph for this function:

◆ operator=() [3/3]

template<typename Traits >
concurrent_skip_list & tbb::interface10::internal::concurrent_skip_list< Traits >::operator= ( std::initializer_list< value_type il)
inline

Definition at line 346 of file _concurrent_skip_list_impl.h.

347 {
348 clear();
349 insert(il.begin(),il.end());
350 return *this;
351 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::clear(), and tbb::interface10::internal::concurrent_skip_list< Traits >::insert().

Here is the call graph for this function:

◆ random_level()

template<typename Traits >
size_type tbb::interface10::internal::concurrent_skip_list< Traits >::random_level ( )
inlineprivate

Generate random level

Definition at line 951 of file _concurrent_skip_list_impl.h.

951 {
952 return my_rnd_generator();
953 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::my_rnd_generator.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::create_node().

Here is the caller graph for this function:

◆ range() [1/2]

template<typename Traits >
range_type tbb::interface10::internal::concurrent_skip_list< Traits >::range ( )
inline

Definition at line 673 of file _concurrent_skip_list_impl.h.

673{ return range_type(*this); }

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::internal_count(), tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase(), and tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase().

Here is the caller graph for this function:

◆ range() [2/2]

template<typename Traits >
const_range_type tbb::interface10::internal::concurrent_skip_list< Traits >::range ( ) const
inline

Definition at line 674 of file _concurrent_skip_list_impl.h.

674{ return const_range_type(*this); }

◆ size()

template<typename Traits >
size_type tbb::interface10::internal::concurrent_skip_list< Traits >::size ( ) const
inline

Definition at line 567 of file _concurrent_skip_list_impl.h.

567 {
568 return my_size.load(std::memory_order_relaxed);
569 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::my_size.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::empty().

Here is the caller graph for this function:

◆ swap()

template<typename Traits >
void tbb::interface10::internal::concurrent_skip_list< Traits >::swap ( concurrent_skip_list< Traits > &  other)
inline

Definition at line 583 of file _concurrent_skip_list_impl.h.

583 {
584 using std::swap;
585 using pocs_type = typename node_allocator_traits::propagate_on_container_swap;
586 tbb::internal::allocator_swap(my_node_allocator, other.my_node_allocator, pocs_type());
587 swap(my_compare, other.my_compare);
588 swap(my_rnd_generator, other.my_rnd_generator);
589 swap(dummy_head, other.dummy_head);
590
591 size_type tmp = my_size;
592 my_size.store(other.my_size);
593 other.my_size.store(tmp);
594 }
void allocator_swap(MyAlloc &my_allocator, OtherAlloc &other_allocator, traits_true_type)

References tbb::internal::allocator_swap(), tbb::interface10::internal::concurrent_skip_list< Traits >::dummy_head, tbb::interface10::internal::concurrent_skip_list< Traits >::my_compare, tbb::interface10::internal::concurrent_skip_list< Traits >::my_node_allocator, tbb::interface10::internal::concurrent_skip_list< Traits >::my_rnd_generator, tbb::interface10::internal::concurrent_skip_list< Traits >::my_size, and tbb::interface10::internal::concurrent_skip_list< Traits >::swap().

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::swap().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ try_insert_node()

template<typename Traits >
bool tbb::interface10::internal::concurrent_skip_list< Traits >::try_insert_node ( node_ptr  new_node,
array_type prev_nodes,
array_type next_nodes 
)
inlineprivate

Definition at line 813 of file _concurrent_skip_list_impl.h.

813 {
814 __TBB_ASSERT(dummy_head->height() >= new_node->height(), NULL);
815
816 lock_array locks;
817
818 if (!try_lock_nodes(new_node->height(), prev_nodes, next_nodes, locks)) {
819 return false;
820 }
821
823 ((prev_nodes[0] == dummy_head ||
824 my_compare(get_key(prev_nodes[0]), get_key(new_node))) &&
825 (next_nodes[0] == nullptr || my_compare(get_key(new_node), get_key(next_nodes[0])))),
826 "Wrong elements order");
827
828 for (size_type level = 0; level < new_node->height(); ++level) {
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);
833 }
834 new_node->mark_linked();
835
836 ++my_size;
837
838 return true;
839 }
bool try_lock_nodes(size_type height, array_type &prevs, array_type &next_nodes, lock_array &locks)
std::array< typename list_node_type::lock_type, MAX_LEVEL > lock_array

References __TBB_ASSERT, tbb::interface10::internal::concurrent_skip_list< Traits >::allow_multimapping, tbb::interface10::internal::concurrent_skip_list< Traits >::dummy_head, tbb::interface10::internal::concurrent_skip_list< Traits >::get_key(), tbb::interface10::internal::skip_list_node< Value, Mutex >::height(), tbb::interface10::internal::skip_list_node< Value, Mutex >::mark_linked(), tbb::interface10::internal::concurrent_skip_list< Traits >::my_compare, tbb::interface10::internal::concurrent_skip_list< Traits >::my_size, tbb::interface10::internal::skip_list_node< Value, Mutex >::set_next(), and tbb::interface10::internal::concurrent_skip_list< Traits >::try_lock_nodes().

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::internal_insert_node().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ try_lock_nodes()

template<typename Traits >
bool tbb::interface10::internal::concurrent_skip_list< Traits >::try_lock_nodes ( size_type  height,
array_type prevs,
array_type next_nodes,
lock_array locks 
)
inlineprivate

Definition at line 841 of file _concurrent_skip_list_impl.h.

841 {
842 for (size_type l = 0; l < height; ++l) {
843 if (l == 0 || prevs[l] != prevs[l - 1])
844 locks[l] = prevs[l]->acquire();
845
846 node_ptr next = prevs[l]->next(l);
847 if ( next != next_nodes[l]) return false;
848 }
849
850 return true;
851 }

References tbb::interface10::internal::skip_list_node< Value, Mutex >::next().

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::try_insert_node().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ unsafe_erase() [1/5]

template<typename Traits >
template<typename K , typename = tbb::internal::is_transparent<key_compare, K>, typename = typename std::enable_if<!std::is_convertible<K, iterator>::value && !std::is_convertible<K, const_iterator>::value>::type>
size_type tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase ( const K &  key)
inline

Definition at line 424 of file _concurrent_skip_list_impl.h.

424 {
425 std::pair<iterator, iterator> range = equal_range(key);
426 size_type sz = std::distance(range.first, range.second);
427 unsafe_erase(range.first, range.second);
428 return sz;
429 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::equal_range(), key, tbb::interface10::internal::concurrent_skip_list< Traits >::range(), and tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase().

Here is the call graph for this function:

◆ unsafe_erase() [2/5]

template<typename Traits >
size_type tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase ( const key_type key)
inline

Definition at line 438 of file _concurrent_skip_list_impl.h.

438 {
439 std::pair<iterator, iterator> range = equal_range(key);
440 size_type sz = std::distance(range.first, range.second);
441 unsafe_erase(range.first, range.second);
442 return sz;
443 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::equal_range(), key, tbb::interface10::internal::concurrent_skip_list< Traits >::range(), and tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase().

Here is the call graph for this function:

◆ unsafe_erase() [3/5]

template<typename Traits >
iterator tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase ( const_iterator  first,
const_iterator  last 
)
inline

Definition at line 431 of file _concurrent_skip_list_impl.h.

431 {
432 while(first != last) {
434 }
435 return get_iterator(first);
436 }

References tbb::internal::first(), tbb::interface10::internal::concurrent_skip_list< Traits >::get_iterator(), tbb::internal::last(), and tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase().

Here is the call graph for this function:

◆ unsafe_erase() [4/5]

template<typename Traits >
iterator tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase ( const_iterator  pos)
inline

Definition at line 417 of file _concurrent_skip_list_impl.h.

417 {
418 return unsafe_erase(get_iterator(pos));
419 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::get_iterator(), and tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase().

Here is the call graph for this function:

◆ unsafe_erase() [5/5]

template<typename Traits >
iterator tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase ( iterator  pos)
inline

Definition at line 408 of file _concurrent_skip_list_impl.h.

408 {
409 std::pair<node_ptr, node_ptr> extract_result = internal_extract(pos);
410 if(extract_result.first) { // node was extracted
411 delete_node(extract_result.first);
412 return iterator(extract_result.second);
413 }
414 return end();
415 }
std::pair< node_ptr, node_ptr > internal_extract(const_iterator it)

References tbb::interface10::internal::concurrent_skip_list< Traits >::delete_node(), tbb::interface10::internal::concurrent_skip_list< Traits >::end(), and tbb::interface10::internal::concurrent_skip_list< Traits >::internal_extract().

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase(), tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase(), tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase(), and tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ unsafe_extract() [1/2]

template<typename Traits >
node_type tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_extract ( const key_type key)
inline

Definition at line 450 of file _concurrent_skip_list_impl.h.

450 {
451 return unsafe_extract(find(key));
452 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::find(), key, and tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_extract().

Here is the call graph for this function:

◆ unsafe_extract() [2/2]

template<typename Traits >
node_type tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_extract ( const_iterator  pos)
inline

Definition at line 445 of file _concurrent_skip_list_impl.h.

445 {
446 std::pair<node_ptr, node_ptr> extract_result = internal_extract(pos);
447 return extract_result.first ? node_type(extract_result.first) : node_type();
448 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_extract().

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_extract().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ upper_bound() [1/4]

template<typename Traits >
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
iterator tbb::interface10::internal::concurrent_skip_list< Traits >::upper_bound ( const K &  key)
inline

Definition at line 481 of file _concurrent_skip_list_impl.h.

481 {
482 return internal_get_bound(key, not_greater_compare(my_compare));
483 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_get_bound(), key, and tbb::interface10::internal::concurrent_skip_list< Traits >::my_compare.

Here is the call graph for this function:

◆ upper_bound() [2/4]

template<typename Traits >
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
const_iterator tbb::interface10::internal::concurrent_skip_list< Traits >::upper_bound ( const K &  key) const
inline

Definition at line 486 of file _concurrent_skip_list_impl.h.

486 {
487 return internal_get_bound(key, not_greater_compare(my_compare));
488 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_get_bound(), key, and tbb::interface10::internal::concurrent_skip_list< Traits >::my_compare.

Here is the call graph for this function:

◆ upper_bound() [3/4]

template<typename Traits >
iterator tbb::interface10::internal::concurrent_skip_list< Traits >::upper_bound ( const key_type key)
inline

Definition at line 472 of file _concurrent_skip_list_impl.h.

472 {
473 return internal_get_bound(key, not_greater_compare(my_compare));
474 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_get_bound(), key, and tbb::interface10::internal::concurrent_skip_list< Traits >::my_compare.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::equal_range(), tbb::interface10::internal::concurrent_skip_list< Traits >::equal_range(), tbb::interface10::internal::concurrent_skip_list< Traits >::equal_range(), and tbb::interface10::internal::concurrent_skip_list< Traits >::equal_range().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ upper_bound() [4/4]

template<typename Traits >
const_iterator tbb::interface10::internal::concurrent_skip_list< Traits >::upper_bound ( const key_type key) const
inline

Definition at line 476 of file _concurrent_skip_list_impl.h.

476 {
477 return internal_get_bound(key, not_greater_compare(my_compare));
478 }

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_get_bound(), key, and tbb::interface10::internal::concurrent_skip_list< Traits >::my_compare.

Here is the call graph for this function:

◆ value_comp()

template<typename Traits >
value_compare tbb::interface10::internal::concurrent_skip_list< Traits >::value_comp ( ) const
inline

Definition at line 616 of file _concurrent_skip_list_impl.h.

616{ return traits_type::value_comp(my_compare); }

References tbb::interface10::internal::concurrent_skip_list< Traits >::my_compare.

Friends And Related Symbol Documentation

◆ concurrent_skip_list

template<typename Traits >
template<typename OtherTraits >
friend class concurrent_skip_list
friend

Definition at line 1060 of file _concurrent_skip_list_impl.h.

Member Data Documentation

◆ allow_multimapping

◆ dummy_head

◆ MAX_LEVEL

template<typename Traits >
constexpr size_type tbb::interface10::internal::concurrent_skip_list< Traits >::MAX_LEVEL = traits_type::MAX_LEVEL
staticconstexprprotected

◆ my_compare

template<typename Traits >
key_compare tbb::interface10::internal::concurrent_skip_list< Traits >::my_compare
private

◆ my_node_allocator

◆ my_rnd_generator

◆ my_size


The documentation for this class was generated from the following file:

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.