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_list &	operator= (const concurrent_skip_list &other)
concurrent_skip_list &	operator= (concurrent_skip_list &&other)
concurrent_skip_list &	operator= (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, iterator >	equal_range (const key_type &key)
std::pair< const_iterator, const_iterator >	equal_range (const key_type &key) const
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
std::pair< iterator, iterator >	equal_range (const K &key)
template<typename K , typename = typename tbb::internal::is_transparent<key_compare, K>>
std::pair< const_iterator, const_iterator >	equal_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_ptr >	internal_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_type &	get_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_type >	my_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.

                           : my_size(0) {
        create_dummy_head();
    }

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.

        : my_node_allocator(alloc), my_compare(comp), my_size(0)
    {
        create_dummy_head();
    }

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.

        : my_node_allocator(alloc), my_compare(comp), my_size(0)
    {
        create_dummy_head();
        internal_copy(first, last);
    }

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.

        : my_node_allocator(node_allocator_traits::select_on_container_copy_construction(other.get_allocator())),
          my_compare(other.my_compare), my_rnd_generator(other.my_rnd_generator), my_size(0)
    {
        create_dummy_head();
        internal_copy(other);
        __TBB_ASSERT(my_size == other.my_size, "Wrong size of copy-constructed container");
    }

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.

        : my_node_allocator(alloc), my_compare(other.my_compare),
          my_rnd_generator(other.my_rnd_generator), my_size(0)
    {
        create_dummy_head();
        internal_copy(other);
        __TBB_ASSERT(my_size == other.my_size, "Wrong size of copy-constructed container");
    }

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.

        : my_node_allocator(std::move(other.my_node_allocator)), my_compare(other.my_compare),
          my_rnd_generator(other.my_rnd_generator)
    {
        internal_move(std::move(other));
    }

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.

        : my_node_allocator(alloc), my_compare(other.my_compare),
          my_rnd_generator(other.my_rnd_generator)
    {
        if (alloc == other.get_allocator()) {
            internal_move(std::move(other));
        } else {
            my_size = 0;
            create_dummy_head();
            internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()));
        }
    }

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(), tbb::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.

                            {
        clear();
        delete_dummy_head();
    }

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.

                     {
        return iterator(dummy_head->next(0));
    }

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.

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

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.

                                                      {
        return sizeof(list_node_type) + height*sizeof(typename list_node_type::atomic_node_pointer);
    }

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.

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

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.

                                {
        return const_iterator(nullptr);
    }

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.

                          {
        __TBB_ASSERT(dummy_head->height() > 0, NULL);

        node_ptr current = dummy_head->next(0);
        while (current) {
            __TBB_ASSERT(current->height() > 0, NULL);
            node_ptr next = current->next(0);
            delete_node(current);
            current = next;
        }

        my_size = 0;
        for (size_type i = 0; i < dummy_head->height(); ++i) {
            dummy_head->set_next(i, nullptr);
        }
    }

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=(), 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 >

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.

                                             {
        return find(key) != end();
    }

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:

contains() [2/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.

                                      {
        return find(key) != end();
    }

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:

count() [1/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.

                                                 {
        return internal_count(key);
    }

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 >

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.

                                        {
        return internal_count(key);
    }

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.

                             {
        size_type sz = calc_node_size(MAX_LEVEL);

        dummy_head = reinterpret_cast<node_ptr>(node_allocator_traits::allocate(my_node_allocator, sz));
        // TODO: investigate linkage fail in debug without this workaround
        auto max_level = MAX_LEVEL;

        try {
            node_allocator_traits::construct(my_node_allocator, dummy_head, max_level);
        }
        catch(...) {
            deallocate_node(dummy_head, sz);
            throw;
        }
    }

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().

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.

                                         {
        size_type levels = random_level();

        size_type sz = calc_node_size(levels);

        node_ptr node = reinterpret_cast<node_ptr>(node_allocator_traits::allocate(my_node_allocator, sz));

        try {
            node_allocator_traits::construct(my_node_allocator, node, levels);

        }
        catch(...) {
            deallocate_node(node, sz);
            throw;
        }

        try {
            node_allocator_traits::construct(my_node_allocator, node->storage(), std::forward<Args>(args)...);
        }
        catch (...) {
            node_allocator_traits::destroy(my_node_allocator, node);
            deallocate_node(node, sz);
            throw;
        }

        return node;
    }

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.

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

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

Definition at line 1020 of file _concurrent_skip_list_impl.h.

                             {
        delete_node<true>(dummy_head);
    }

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

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

Here is the caller graph for this function:

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.

                                    {
        size_type sz = calc_node_size(node->height());
        // Destroy value
        if (!is_dummy) node_allocator_traits::destroy(my_node_allocator, node->storage());
        // Destroy node
        node_allocator_traits::destroy(my_node_allocator, node);
        // Deallocate memory
        deallocate_node(node, sz);
    }

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.

                                                    {
        return internal_insert(std::forward<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.

                                                          {
        // Ignore hint
        return emplace(std::forward<Args>(args)...).first;
    }

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.

                       {
        return 0 == size();
    }

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

Here is the call graph for this function:

end() [1/2]

template<typename Traits >

iterator tbb::interface10::internal::concurrent_skip_list< Traits >::end ( )

inline

Definition at line 555 of file _concurrent_skip_list_impl.h.

                   {
        return iterator(nullptr);
    }

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::contains(), 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_count(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_extract(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_find(), and tbb::interface10::internal::concurrent_skip_list< Traits >::unsafe_erase().

Here is the caller graph for this function:

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.

                               {
        return const_iterator(nullptr);
    }

equal_range() [1/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.

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

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(), 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() [2/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.

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

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 >

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.

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

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() [4/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.

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

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.

                                                      {
        prev_nodes.fill(dummy_head);
        next_nodes.fill(nullptr);

        for (size_type h = prev->height(); h > 0; --h) {
            node_ptr next = internal_find_position(h - 1, prev, key, cmp);
            prev_nodes[h - 1] = prev;
            next_nodes[h - 1] = next;
        }
    }

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.

                                                      {
        node_ptr prev = dummy_head;
        node_ptr erase_node = it.my_node_ptr;
        size_type node_height = erase_node->height();

        for (size_type h = prev->height(); h >= node_height; --h) {
            internal_find_position(h - 1, prev, key, cmp);
        }

        for (size_type h = node_height; h > 0; --h) {
            node_ptr curr = prev->next(h - 1);
            while (const_iterator(curr) != it) {
                prev = curr;
                curr = prev->next(h - 1);
            }
            prev_nodes[h - 1] = prev;
        }

        std::fill(next_nodes.begin(), next_nodes.begin() + node_height, erase_node);
    }

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 >

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.

                                       {
        return internal_find(key);
    }

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 >::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() [2/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.

                                                   {
        return internal_find(key);
    }

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 >

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.

                                {
        return internal_find(key);
    }

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

Here is the call graph for this function:

find() [4/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.

                                            {
        return internal_find(key);
    }

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

Definition at line 579 of file _concurrent_skip_list_impl.h.

                                         {
        return my_node_allocator;
    }

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

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.

                                                    {
        return iterator(it.my_node_ptr);
    }

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

Referenced by 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.

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

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.

                                                            {
        return internal_insert(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 >::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 >

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.

                                                       {
        return internal_insert(std::move(value));
    }

References tbb::interface10::internal::concurrent_skip_list< Traits >::internal_insert(), tbb::move(), 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  , const_reference  value  )

inline

Definition at line 361 of file _concurrent_skip_list_impl.h.

                                                           {
        // Ignore hint
        return insert(value).first;
    }

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

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.

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

References tbb::interface10::internal::concurrent_skip_list< Traits >::insert(), tbb::move(), 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.

                                                         {
        for (InputIterator it = first; it != last; ++it)
            insert(*it);
    }

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 >

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.

                                                      {
        insert(init.begin(), init.end());
    }

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

Here is the call graph for this function:

insert() [7/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.

                                                   {
        if(!nh.empty()) {
            std::pair<iterator, bool> insert_result = internal_insert_node(nh.my_node);
            if(insert_result.second) {
                nh.deactivate();
            }
            return insert_result;
        }
        return std::pair<iterator, bool>(end(), false);
    }

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() [8/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.

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

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

Here is the call graph for this function:

internal_copy() [1/2]

template<typename Traits >

void tbb::interface10::internal::concurrent_skip_list< Traits >::internal_copy ( const concurrent_skip_list< Traits > &  other )

inlineprivate

Definition at line 932 of file _concurrent_skip_list_impl.h.

                                                          {
        internal_copy(other.begin(), other.end());
    }

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

Referenced by 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 >::operator=().

Here is the call graph for this function:

Here is the caller graph for this function:

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.

                                                      {
        clear();
        try {
            for (auto it = first; it != last; ++it)
                insert(*it);
        }
        catch (...) {
            clear();
            delete_dummy_head();
            throw;
        }
    }

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.

                                                   {
        if (allow_multimapping) {
            std::pair<const_iterator, const_iterator> range = equal_range(key);
            return std::distance(range.first, range.second);
        }
        return (find(key) == end()) ? size_type(0) : size_type(1);
    }

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().

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.

                                                                    {
        if ( it != end() ) {
            key_type key = traits_type::get_key(*it);
            __TBB_ASSERT(dummy_head->height() > 0, NULL);

            array_type prev_nodes;
            array_type next_nodes;

            fill_prev_next_by_ptr(prev_nodes, next_nodes, it, key, my_compare);

            node_ptr erase_node = next_nodes[0];
            __TBB_ASSERT(erase_node != nullptr, NULL);
            node_ptr next_node = erase_node->next(0);

            if (!my_compare(key, get_key(erase_node))) {
                for(size_type level = 0; level < erase_node->height(); ++level) {
                    __TBB_ASSERT(prev_nodes[level]->height() > level, NULL);
                    __TBB_ASSERT(next_nodes[level] == erase_node, NULL);
                    prev_nodes[level]->set_next(level, erase_node->next(level));
                }
                --my_size;
                return std::pair<node_ptr, node_ptr>(erase_node, next_node);
            }
        }
        return std::pair<node_ptr, node_ptr>(nullptr, nullptr);
    }

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.

                                         {
        iterator it = lower_bound(key);
        return (it == end() || my_compare(key, traits_type::get_key(*it))) ? end() : it;
    }

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().

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.

                                                     {
        const_iterator it = lower_bound(key);
        return (it == end() || my_compare(key, traits_type::get_key(*it))) ? end() : it;
    }

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

level	using
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.

                                                                      {
        __TBB_ASSERT(level < prev->height(), "Wrong level to find position");
        pointer_type curr = prev->next(level);

        while (curr && cmp(get_key(curr), key)) {
            prev = curr;
            __TBB_ASSERT(level < prev->height(), NULL);
            curr = prev->next(level);
        }

        return curr;
    }

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(), 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 >

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.

                                                                                 {
        node_ptr prev = dummy_head;
        __TBB_ASSERT(dummy_head->height() > 0, NULL);
        node_ptr next = nullptr;

        for (size_type h = prev->height(); h > 0; --h) {
            next = internal_find_position(h - 1, prev, key, cmp);
        }

        return const_iterator(next);
    }

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(), 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_get_bound() [2/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.

                                                                    {
        node_ptr prev = dummy_head;
        __TBB_ASSERT(dummy_head->height() > 0, NULL);
        node_ptr next = nullptr;

        for (size_type h = prev->height(); h > 0; --h) {
            next = internal_find_position(h - 1, prev, key, cmp);
        }

        return iterator(next);
    }

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_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.

                                                            {
        node_ptr new_node = create_node(std::forward<Args>(args)...);
        std::pair<iterator, bool> insert_result = internal_insert_node(new_node);
        if(!insert_result.second) {
            delete_node(new_node);
        }
        return insert_result;
    }

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(), 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.

                                                                    {
        array_type prev_nodes;
        array_type next_nodes;
        __TBB_ASSERT(dummy_head->height() >= new_node->height(), "Wrong height for new node");

        do {
            if (allow_multimapping) {
                fill_prev_next_arrays(prev_nodes, next_nodes, dummy_head, get_key(new_node),
                                      not_greater_compare(my_compare));
            } else {
                fill_prev_next_arrays(prev_nodes, next_nodes, dummy_head, get_key(new_node), my_compare);
            }

            node_ptr next = next_nodes[0];
            if (next && !allow_multimapping && !my_compare(get_key(new_node), get_key(next))) {
                // TODO: do we really need to wait?
                while (!next->fully_linked()) {
                    // TODO: atomic backoff
                }

                return std::pair<iterator, bool>(iterator(next), false);
            }
            __TBB_ASSERT(allow_multimapping || !next || my_compare(get_key(new_node), get_key(next)),
                         "Wrong elements order");

        } while (!try_insert_node(new_node, prev_nodes, next_nodes));

        __TBB_ASSERT(new_node, NULL);
        return std::pair<iterator, bool>(iterator(new_node), true);
    }

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.

                                             {
        using source_type = typename std::decay<SourceType>::type;
        using source_iterator = typename source_type::iterator;
        __TBB_STATIC_ASSERT((std::is_same<node_type, typename source_type::node_type>::value), "Incompatible containers cannot be merged");

        for(source_iterator it = source.begin(); it != source.end();) {
            source_iterator where = it++;
            if (allow_multimapping || !contains(traits_type::get_key(*where))) {
                std::pair<node_ptr, node_ptr> extract_result = source.internal_extract(where);

                //If the insertion fails - return the node into source
                node_type handle(extract_result.first);
                __TBB_ASSERT(!handle.empty(), "Extracted handle in merge is empty");

                if (!insert(std::move(handle)).second) {
                    source.insert(std::move(handle));
                }
                handle.deactivate();
            }
        }
    }

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

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.

                                                     {
        dummy_head = other.dummy_head;
        other.dummy_head = nullptr;
        other.create_dummy_head();

        my_size = other.my_size.load();
        other.my_size = 0;
    }

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(), 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::true_type    )

inlineprivate

Definition at line 1028 of file _concurrent_skip_list_impl.h.

                                                                           {
        delete_dummy_head();
        tbb::internal::allocator_move_assignment(my_node_allocator, other.my_node_allocator, std::true_type());
        internal_move(std::move(other));
    }

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(), tbb::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:

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::false_type    )

inlineprivate

Definition at line 1034 of file _concurrent_skip_list_impl.h.

                                                                            {
        if (my_node_allocator == other.my_node_allocator) {
            delete_dummy_head();
            internal_move(std::move(other));
        } else {
            internal_copy(std::make_move_iterator(other.begin()), std::make_move_iterator(other.end()));
        }
    }

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(), tbb::move(), and tbb::interface10::internal::concurrent_skip_list< Traits >::my_node_allocator.

Here is the call graph for this function:

key_comp()

template<typename Traits >

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

inline

Definition at line 614 of file _concurrent_skip_list_impl.h.

{ return my_compare; }

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

lower_bound() [1/4]

template<typename Traits >

iterator tbb::interface10::internal::concurrent_skip_list< Traits >::lower_bound ( const key_type &  key )

inline

Definition at line 454 of file _concurrent_skip_list_impl.h.

                                              {
        return internal_get_bound(key, my_compare);
    }

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(), and tbb::interface10::internal::concurrent_skip_list< Traits >::internal_find().

Here is the call graph for this function:

Here is the caller graph for this function:

lower_bound() [2/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.

                                                          {
        return internal_get_bound(key, my_compare);
    }

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]

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.

                                       {
        return internal_get_bound(key, my_compare);
    }

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() [4/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.

                                                   {
        return internal_get_bound(key, my_compare);
    }

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

Definition at line 571 of file _concurrent_skip_list_impl.h.

                               {
        return my_node_allocator.max_size();
    }

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

operator=() [1/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.

                                                                       {
        if (this != &other) {
            using pocca_type = typename node_allocator_traits::propagate_on_container_copy_assignment;
            clear();
            tbb::internal::allocator_copy_assignment(my_node_allocator, other.my_node_allocator, pocca_type());
            my_compare = other.my_compare;
            my_rnd_generator = other.my_rnd_generator;
            internal_copy(other);
        }
        return *this;
    }

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=() [2/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.

                                                                  {
        if (this != &other) {
            using pocma_type = typename node_allocator_traits::propagate_on_container_move_assignment;
            clear();
            my_compare = other.my_compare;
            my_rnd_generator = other.my_rnd_generator;
            internal_move_assign(std::move(other), pocma_type());
        }
        return *this;
    }

References tbb::interface10::internal::concurrent_skip_list< Traits >::clear(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_move_assign(), tbb::move(), 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=() [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.

    {
        clear();
        insert(il.begin(),il.end());
        return *this;
    }

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.

                             {
        return my_rnd_generator();
    }

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.

{ return range_type(*this); }

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::internal_count(), 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.

{ 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.

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

References tbb::internal::memory_order_relaxed, and 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.

                                           {
        using std::swap;
        using pocs_type = typename node_allocator_traits::propagate_on_container_swap;
        tbb::internal::allocator_swap(my_node_allocator, other.my_node_allocator, pocs_type());
        swap(my_compare, other.my_compare);
        swap(my_rnd_generator, other.my_rnd_generator);
        swap(dummy_head, other.dummy_head);

        size_type tmp = my_size;
        my_size.store(other.my_size);
        other.my_size.store(tmp);
    }

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::internal::swap().

Here is the call 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.

                                                                                            {
        __TBB_ASSERT(dummy_head->height() >= new_node->height(), NULL);

        lock_array locks;

        if (!try_lock_nodes(new_node->height(), prev_nodes, next_nodes, locks)) {
            return false;
        }

        __TBB_ASSERT(allow_multimapping ||
                    ((prev_nodes[0] == dummy_head ||
                      my_compare(get_key(prev_nodes[0]), get_key(new_node))) &&
                      (next_nodes[0] == nullptr || my_compare(get_key(new_node), get_key(next_nodes[0])))),
                    "Wrong elements order");

        for (size_type level = 0; level < new_node->height(); ++level) {
            __TBB_ASSERT(prev_nodes[level]->height() > level, NULL);
            __TBB_ASSERT(prev_nodes[level]->next(level) == next_nodes[level], NULL);
            new_node->set_next(level, next_nodes[level]);
            prev_nodes[level]->set_next(level, new_node);
        }
        new_node->mark_linked();

        ++my_size;

        return true;
    }

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.

                                                                                                        {
        for (size_type l = 0; l < height; ++l) {
            if (l == 0 || prevs[l] != prevs[l - 1])
                locks[l] = prevs[l]->acquire();

            node_ptr next = prevs[l]->next(l);
            if ( next != next_nodes[l]) return false;
        }

        return true;
    }

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 >

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

inline

Definition at line 408 of file _concurrent_skip_list_impl.h.

                                        {
        std::pair<node_ptr, node_ptr> extract_result = internal_extract(pos);
        if(extract_result.first) { // node was extracted
            delete_node(extract_result.first);
            return iterator(extract_result.second);
        }
        return end();
    }

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().

Here is the call graph for this function:

Here is the caller graph for this function:

unsafe_erase() [2/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.

                                              {
        return unsafe_erase(get_iterator(pos));
    }

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() [3/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.

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

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() [4/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.

                                                                     {
        while(first != last) {
            first = unsafe_erase(get_iterator(first));
        }
        return get_iterator(first);
    }

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() [5/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.

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

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_extract() [1/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.

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

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:

unsafe_extract() [2/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.

                                                  {
        return unsafe_extract(find(key));
    }

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:

upper_bound() [1/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.

                                              {
        return internal_get_bound(key, not_greater_compare(my_compare));
    }

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().

Here is the call graph for this function:

Here is the caller graph for this function:

upper_bound() [2/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.

                                                          {
        return internal_get_bound(key, not_greater_compare(my_compare));
    }

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 >

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.

                                       {
        return internal_get_bound(key, not_greater_compare(my_compare));
    }

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() [4/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.

                                                   {
        return internal_get_bound(key, not_greater_compare(my_compare));
    }

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.

{ return traits_type::value_comp(my_compare); }

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

Friends And Related Function 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

template<typename Traits >

bool const tbb::interface10::internal::concurrent_skip_list< Traits >::allow_multimapping = traits_type::allow_multimapping

static

Definition at line 255 of file _concurrent_skip_list_impl.h.

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

dummy_head

template<typename Traits >

node_ptr tbb::interface10::internal::concurrent_skip_list< Traits >::dummy_head

private

Definition at line 1057 of file _concurrent_skip_list_impl.h.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::begin(), tbb::interface10::internal::concurrent_skip_list< Traits >::cbegin(), tbb::interface10::internal::concurrent_skip_list< Traits >::clear(), tbb::interface10::internal::concurrent_skip_list< Traits >::create_dummy_head(), tbb::interface10::internal::concurrent_skip_list< Traits >::delete_dummy_head(), 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_extract(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_get_bound(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_insert_node(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_move(), tbb::interface10::internal::concurrent_skip_list< Traits >::swap(), and tbb::interface10::internal::concurrent_skip_list< Traits >::try_insert_node().

MAX_LEVEL

template<typename Traits >

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

staticprotected

Definition at line 249 of file _concurrent_skip_list_impl.h.

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

my_compare

template<typename Traits >

key_compare tbb::interface10::internal::concurrent_skip_list< Traits >::my_compare

private

Definition at line 1055 of file _concurrent_skip_list_impl.h.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::internal_extract(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_find(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_insert_node(), tbb::interface10::internal::concurrent_skip_list< Traits >::key_comp(), tbb::interface10::internal::concurrent_skip_list< Traits >::lower_bound(), tbb::interface10::internal::concurrent_skip_list< Traits >::operator=(), tbb::interface10::internal::concurrent_skip_list< Traits >::swap(), tbb::interface10::internal::concurrent_skip_list< Traits >::try_insert_node(), tbb::interface10::internal::concurrent_skip_list< Traits >::upper_bound(), and tbb::interface10::internal::concurrent_skip_list< Traits >::value_comp().

my_node_allocator

template<typename Traits >

node_allocator_type tbb::interface10::internal::concurrent_skip_list< Traits >::my_node_allocator

private

Definition at line 1054 of file _concurrent_skip_list_impl.h.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::create_dummy_head(), tbb::interface10::internal::concurrent_skip_list< Traits >::create_node(), tbb::interface10::internal::concurrent_skip_list< Traits >::deallocate_node(), tbb::interface10::internal::concurrent_skip_list< Traits >::delete_node(), tbb::interface10::internal::concurrent_skip_list< Traits >::get_allocator(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_move_assign(), tbb::interface10::internal::concurrent_skip_list< Traits >::max_size(), tbb::interface10::internal::concurrent_skip_list< Traits >::operator=(), and tbb::interface10::internal::concurrent_skip_list< Traits >::swap().

my_rnd_generator

template<typename Traits >

random_level_generator_type tbb::interface10::internal::concurrent_skip_list< Traits >::my_rnd_generator

private

Definition at line 1056 of file _concurrent_skip_list_impl.h.

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

my_size

template<typename Traits >

std::atomic<size_type> tbb::interface10::internal::concurrent_skip_list< Traits >::my_size

private

Definition at line 1062 of file _concurrent_skip_list_impl.h.

Referenced by tbb::interface10::internal::concurrent_skip_list< Traits >::clear(), tbb::interface10::internal::concurrent_skip_list< Traits >::concurrent_skip_list(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_extract(), tbb::interface10::internal::concurrent_skip_list< Traits >::internal_move(), tbb::interface10::internal::concurrent_skip_list< Traits >::size(), tbb::interface10::internal::concurrent_skip_list< Traits >::swap(), and tbb::interface10::internal::concurrent_skip_list< Traits >::try_insert_node().

---

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

• _concurrent_skip_list_impl.h