tbb::interface5::internal::split_ordered_list< T, Allocator > Class Template Reference

#include <_concurrent_unordered_impl.h>

Inheritance diagram for tbb::interface5::internal::split_ordered_list< T, Allocator >:

Collaboration diagram for tbb::interface5::internal::split_ordered_list< T, Allocator >:

Classes
struct	node

Public Types
typedef split_ordered_list< T, Allocator >	self_type
typedef tbb::internal::allocator_rebind< Allocator, T >::type	allocator_type
typedef node *	nodeptr_t
typedef tbb::internal::allocator_traits< allocator_type >::value_type	value_type
typedef tbb::internal::allocator_traits< allocator_type >::size_type	size_type
typedef tbb::internal::allocator_traits< allocator_type >::difference_type	difference_type
typedef tbb::internal::allocator_traits< allocator_type >::pointer	pointer
typedef tbb::internal::allocator_traits< allocator_type >::const_pointer	const_pointer
typedef value_type &	reference
typedef const value_type &	const_reference
typedef solist_iterator< self_type, const value_type >	const_iterator
typedef solist_iterator< self_type, value_type >	iterator
typedef flist_iterator< self_type, const value_type >	raw_const_iterator
typedef flist_iterator< self_type, value_type >	raw_iterator

Public Member Functions
nodeptr_t	create_node (sokey_t order_key)
template<typename Arg >
nodeptr_t	create_node (sokey_t order_key, __TBB_FORWARDING_REF(Arg) t, tbb::internal::true_type=tbb::internal::true_type())
template<typename Arg >
nodeptr_t	create_node (sokey_t, __TBB_FORWARDING_REF(Arg), tbb::internal::false_type)
template<typename __TBB_PARAMETER_PACK Args>
nodeptr_t	create_node_v (__TBB_FORWARDING_REF(Args) __TBB_PARAMETER_PACK args)
	split_ordered_list (allocator_type a=allocator_type())
	~split_ordered_list ()
allocator_type	get_allocator () const
void	clear ()
iterator	begin ()
const_iterator	begin () const
iterator	end ()
const_iterator	end () const
const_iterator	cbegin () const
const_iterator	cend () const
bool	empty () const
size_type	size () const
size_type	max_size () const
void	swap (self_type &other)
raw_iterator	raw_begin ()
raw_const_iterator	raw_begin () const
raw_iterator	raw_end ()
raw_const_iterator	raw_end () const
iterator	get_iterator (raw_iterator it)
const_iterator	get_iterator (raw_const_iterator it) const
raw_iterator	get_iterator (raw_const_iterator it)
iterator	first_real_iterator (raw_iterator it)
const_iterator	first_real_iterator (raw_const_iterator it) const
void	destroy_node (nodeptr_t pnode)
std::pair< iterator, bool >	try_insert (raw_iterator it, raw_iterator next, nodeptr_t pnode, size_type *new_count)
raw_iterator	insert_dummy (raw_iterator it, sokey_t order_key)
nodeptr_t	erase_node_impl (raw_iterator previous, raw_const_iterator &where)
void	erase_node (raw_iterator previous, raw_const_iterator &where, tbb::internal::true_type)
void	erase_node (raw_iterator previous, raw_const_iterator &where, tbb::internal::false_type)
void	erase_node (raw_iterator previous, raw_const_iterator &where)
template<typename AllowDestroy >
iterator	erase_node (raw_iterator previous, const_iterator where, AllowDestroy)
iterator	erase_node (raw_iterator previous, const_iterator &where)
void	move_all (self_type &source)

Static Public Member Functions
static sokey_t	get_order_key (const raw_const_iterator &it)
static sokey_t	get_safe_order_key (const raw_const_iterator &it)
static iterator	get_iterator (const_iterator it)
static nodeptr_t	try_insert_atomic (nodeptr_t previous, nodeptr_t new_node, nodeptr_t current_node)

Private Member Functions
void	check_range (raw_iterator first, raw_iterator last)
void	check_range ()

Private Attributes
tbb::internal::allocator_rebind< allocator_type, node >::type	my_node_allocator
size_type	my_element_count
nodeptr_t	my_head

Friends
template<typename Traits >
class	concurrent_unordered_base

Detailed Description

template<typename T, typename Allocator>
class tbb::interface5::internal::split_ordered_list< T, Allocator >

Definition at line 61 of file _concurrent_unordered_impl.h.

Member Typedef Documentation

allocator_type

template<typename T, typename Allocator>

typedef tbb::internal::allocator_rebind<Allocator, T>::type tbb::interface5::internal::split_ordered_list< T, Allocator >::allocator_type

Definition at line 208 of file _concurrent_unordered_impl.h.

const_iterator

template<typename T, typename Allocator>

typedef solist_iterator<self_type, const value_type> tbb::interface5::internal::split_ordered_list< T, Allocator >::const_iterator

Definition at line 222 of file _concurrent_unordered_impl.h.

const_pointer

template<typename T, typename Allocator>

typedef tbb::internal::allocator_traits<allocator_type>::const_pointer tbb::interface5::internal::split_ordered_list< T, Allocator >::const_pointer

Definition at line 217 of file _concurrent_unordered_impl.h.

const_reference

template<typename T, typename Allocator>

typedef const value_type& tbb::interface5::internal::split_ordered_list< T, Allocator >::const_reference

Definition at line 220 of file _concurrent_unordered_impl.h.

difference_type

template<typename T, typename Allocator>

typedef tbb::internal::allocator_traits<allocator_type>::difference_type tbb::interface5::internal::split_ordered_list< T, Allocator >::difference_type

Definition at line 215 of file _concurrent_unordered_impl.h.

iterator

template<typename T, typename Allocator>

typedef solist_iterator<self_type, value_type> tbb::interface5::internal::split_ordered_list< T, Allocator >::iterator

Definition at line 223 of file _concurrent_unordered_impl.h.

nodeptr_t

template<typename T, typename Allocator>

typedef node* tbb::interface5::internal::split_ordered_list< T, Allocator >::nodeptr_t

Definition at line 210 of file _concurrent_unordered_impl.h.

pointer

template<typename T, typename Allocator>

typedef tbb::internal::allocator_traits<allocator_type>::pointer tbb::interface5::internal::split_ordered_list< T, Allocator >::pointer

Definition at line 216 of file _concurrent_unordered_impl.h.

raw_const_iterator

template<typename T, typename Allocator>

typedef flist_iterator<self_type, const value_type> tbb::interface5::internal::split_ordered_list< T, Allocator >::raw_const_iterator

Definition at line 224 of file _concurrent_unordered_impl.h.

raw_iterator

template<typename T, typename Allocator>

typedef flist_iterator<self_type, value_type> tbb::interface5::internal::split_ordered_list< T, Allocator >::raw_iterator

Definition at line 225 of file _concurrent_unordered_impl.h.

reference

template<typename T, typename Allocator>

typedef value_type& tbb::interface5::internal::split_ordered_list< T, Allocator >::reference

Definition at line 219 of file _concurrent_unordered_impl.h.

self_type

template<typename T, typename Allocator>

typedef split_ordered_list<T, Allocator> tbb::interface5::internal::split_ordered_list< T, Allocator >::self_type

Definition at line 206 of file _concurrent_unordered_impl.h.

size_type

template<typename T, typename Allocator>

typedef tbb::internal::allocator_traits<allocator_type>::size_type tbb::interface5::internal::split_ordered_list< T, Allocator >::size_type

Definition at line 214 of file _concurrent_unordered_impl.h.

value_type

template<typename T, typename Allocator>

typedef tbb::internal::allocator_traits<allocator_type>::value_type tbb::interface5::internal::split_ordered_list< T, Allocator >::value_type

Definition at line 213 of file _concurrent_unordered_impl.h.

Constructor & Destructor Documentation

split_ordered_list()

template<typename T, typename Allocator>

tbb::interface5::internal::split_ordered_list< T, Allocator >::split_ordered_list ( allocator_type  a = allocator_type() )

inline

Definition at line 333 of file _concurrent_unordered_impl.h.

       : my_node_allocator(a), my_element_count(0)
    {
        // Immediately allocate a dummy node with order key of 0. This node
        // will always be the head of the list.
        my_head = create_node(sokey_t(0));
    }

~split_ordered_list()

template<typename T, typename Allocator>

tbb::interface5::internal::split_ordered_list< T, Allocator >::~split_ordered_list ( )

inline

Definition at line 341 of file _concurrent_unordered_impl.h.

    {
        // Clear the list
        clear();

        // Remove the head element which is not cleared by clear()
        nodeptr_t pnode = my_head;
        my_head = NULL;

        __TBB_ASSERT(pnode != NULL && pnode->my_next == NULL, "Invalid head list node");

        destroy_node(pnode);
    }

Member Function Documentation

begin() [1/2]

template<typename T, typename Allocator>

iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::begin ( )

inline

Definition at line 381 of file _concurrent_unordered_impl.h.

                     {
        return first_real_iterator(raw_begin());
    }

Referenced by tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::begin(), and tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::cbegin().

Here is the caller graph for this function:

begin() [2/2]

template<typename T, typename Allocator>

const_iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::begin ( ) const

inline

Definition at line 386 of file _concurrent_unordered_impl.h.

                                 {
        return first_real_iterator(raw_begin());
    }

cbegin()

template<typename T, typename Allocator>

const_iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::cbegin ( ) const

inline

Definition at line 398 of file _concurrent_unordered_impl.h.

                                  {
        return (((const self_type *)this)->begin());
    }

Referenced by tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::cbegin().

Here is the caller graph for this function:

cend()

template<typename T, typename Allocator>

const_iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::cend ( ) const

inline

Definition at line 402 of file _concurrent_unordered_impl.h.

                                {
        return (((const self_type *)this)->end());
    }

Referenced by tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::cend().

Here is the caller graph for this function:

check_range() [1/2]

template<typename T, typename Allocator>

void tbb::interface5::internal::split_ordered_list< T, Allocator >::check_range ( raw_iterator  first, raw_iterator  last  )

inlineprivate

Definition at line 674 of file _concurrent_unordered_impl.h.

    {
#if TBB_USE_ASSERT
        for (raw_iterator it = first; it != last; ++it)
        {
            raw_iterator next = it;
            ++next;

            __TBB_ASSERT(next == raw_end() || get_order_key(next) >= get_order_key(it), "!!! List order inconsistency !!!");
        }
#else
        tbb::internal::suppress_unused_warning(first, last);
#endif
    }

Referenced by tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::concurrent_unordered_base().

Here is the caller graph for this function:

check_range() [2/2]

template<typename T, typename Allocator>

void tbb::interface5::internal::split_ordered_list< T, Allocator >::check_range ( )

inlineprivate

Definition at line 688 of file _concurrent_unordered_impl.h.

    {
#if TBB_USE_ASSERT
        check_range( raw_begin(), raw_end() );
#endif
    }

Referenced by tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::check_range(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::insert_dummy(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::move_all(), and tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::try_insert().

Here is the caller graph for this function:

clear()

template<typename T, typename Allocator>

void tbb::interface5::internal::split_ordered_list< T, Allocator >::clear ( )

inline

Definition at line 361 of file _concurrent_unordered_impl.h.

                 {
        nodeptr_t pnext;
        nodeptr_t pnode = my_head;

        __TBB_ASSERT(my_head != NULL, "Invalid head list node");
        pnext = pnode->my_next;
        pnode->my_next = NULL;
        pnode = pnext;

        while (pnode != NULL)
        {
            pnext = pnode->my_next;
            destroy_node(pnode);
            pnode = pnext;
        }

        my_element_count = 0;
    }

Referenced by tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::clear(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_copy(), and tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::~split_ordered_list().

Here is the caller graph for this function:

create_node() [1/3]

template<typename T, typename Allocator>

nodeptr_t tbb::interface5::internal::split_ordered_list< T, Allocator >::create_node ( sokey_t  order_key )

inline

Definition at line 285 of file _concurrent_unordered_impl.h.

                                             {
        nodeptr_t pnode = my_node_allocator.allocate(1);
        pnode->init(order_key);
        return (pnode);
    }

Referenced by tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::concurrent_unordered_base(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::insert_dummy(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_insert(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::move_all(), and tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::split_ordered_list().

Here is the caller graph for this function:

create_node() [2/3]

template<typename T, typename Allocator>

template<typename Arg >

nodeptr_t tbb::interface5::internal::split_ordered_list< T, Allocator >::create_node ( sokey_t  order_key, __TBB_FORWARDING_REF(Arg)  t, tbb::internal::true_type  = tbb::internal::true_type()  )

inline

Definition at line 293 of file _concurrent_unordered_impl.h.

                                                                       {
        nodeptr_t pnode = my_node_allocator.allocate(1);

        //TODO: use RAII scoped guard instead of explicit catch
        __TBB_TRY {
            new(static_cast<void*>(&pnode->my_element)) T(tbb::internal::forward<Arg>(t));
            pnode->init(order_key);
        } __TBB_CATCH(...) {
            my_node_allocator.deallocate(pnode, 1);
            __TBB_RETHROW();
        }

        return (pnode);
    }

create_node() [3/3]

template<typename T, typename Allocator>

template<typename Arg >

nodeptr_t tbb::interface5::internal::split_ordered_list< T, Allocator >::create_node ( sokey_t  , __TBB_FORWARDING_REF(Arg)  , tbb::internal::false_type    )

inline

Definition at line 311 of file _concurrent_unordered_impl.h.

                                                 {
        __TBB_ASSERT(false, "This compile-time helper should never get called");
        return nodeptr_t();
    }

create_node_v()

template<typename T, typename Allocator>

template<typename __TBB_PARAMETER_PACK Args>

nodeptr_t tbb::interface5::internal::split_ordered_list< T, Allocator >::create_node_v ( __TBB_FORWARDING_REF(Args) __TBB_PARAMETER_PACK  args )

inline

Definition at line 319 of file _concurrent_unordered_impl.h.

                                                                                  {
        nodeptr_t pnode = my_node_allocator.allocate(1);

        //TODO: use RAII scoped guard instead of explicit catch
        __TBB_TRY {
            new(static_cast<void*>(&pnode->my_element)) T(__TBB_PACK_EXPANSION(tbb::internal::forward<Args>(args)));
        } __TBB_CATCH(...) {
            my_node_allocator.deallocate(pnode, 1);
            __TBB_RETHROW();
        }

        return (pnode);
    }

Referenced by tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::emplace().

Here is the caller graph for this function:

destroy_node()

template<typename T, typename Allocator>

void tbb::interface5::internal::split_ordered_list< T, Allocator >::destroy_node ( nodeptr_t  pnode )

inline

Definition at line 510 of file _concurrent_unordered_impl.h.

                                       {
        if (!pnode->is_dummy()) my_node_allocator.destroy(pnode);
        my_node_allocator.deallocate(pnode, 1);
    }

Referenced by tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::clear(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::erase_node(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::insert_dummy(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_insert(), and tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::~split_ordered_list().

Here is the caller graph for this function:

empty()

template<typename T, typename Allocator>

bool tbb::interface5::internal::split_ordered_list< T, Allocator >::empty ( ) const

inline

Definition at line 407 of file _concurrent_unordered_impl.h.

                       {
        return (my_element_count == 0);
    }

Referenced by tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::empty().

Here is the caller graph for this function:

end() [1/2]

template<typename T, typename Allocator>

iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::end ( )

inline

Definition at line 390 of file _concurrent_unordered_impl.h.

                   {
        return (iterator(0, this));
    }

Referenced by tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::cend(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::end(), and tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::try_insert().

Here is the caller graph for this function:

end() [2/2]

template<typename T, typename Allocator>

const_iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::end ( ) const

inline

Definition at line 394 of file _concurrent_unordered_impl.h.

                               {
        return (const_iterator(0, this));
    }

erase_node() [1/5]

template<typename T, typename Allocator>

void tbb::interface5::internal::split_ordered_list< T, Allocator >::erase_node ( raw_iterator  previous, raw_const_iterator &  where, tbb::internal::true_type    )

inline

Definition at line 607 of file _concurrent_unordered_impl.h.

    {
        nodeptr_t pnode = erase_node_impl(previous, where);
        destroy_node(pnode);
    }

Referenced by tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::erase_node(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_erase(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_extract(), and tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::move_all().

Here is the caller graph for this function:

erase_node() [2/5]

template<typename T, typename Allocator>

void tbb::interface5::internal::split_ordered_list< T, Allocator >::erase_node ( raw_iterator  previous, raw_const_iterator &  where, tbb::internal::false_type    )

inline

Definition at line 614 of file _concurrent_unordered_impl.h.

    {
        erase_node_impl(previous, where);
    }

erase_node() [3/5]

template<typename T, typename Allocator>

void tbb::interface5::internal::split_ordered_list< T, Allocator >::erase_node ( raw_iterator  previous, raw_const_iterator &  where  )

inline

Definition at line 620 of file _concurrent_unordered_impl.h.

                                                                      {
        erase_node(previous, where, /*allow_destroy*/tbb::internal::true_type());
    }

erase_node() [4/5]

template<typename T, typename Allocator>

template<typename AllowDestroy >

iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::erase_node ( raw_iterator  previous, const_iterator  where, AllowDestroy    )

inline

Definition at line 626 of file _concurrent_unordered_impl.h.

    {
        raw_const_iterator it = where;
        erase_node(previous, it, AllowDestroy());
        my_element_count--;

        return get_iterator(first_real_iterator(it));
    }

erase_node() [5/5]

template<typename T, typename Allocator>

iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::erase_node ( raw_iterator  previous, const_iterator &  where  )

inline

Definition at line 635 of file _concurrent_unordered_impl.h.

                                                                      {
        return erase_node(previous, where, /*allow_destroy*/tbb::internal::true_type());
    }

erase_node_impl()

template<typename T, typename Allocator>

nodeptr_t tbb::interface5::internal::split_ordered_list< T, Allocator >::erase_node_impl ( raw_iterator  previous, raw_const_iterator &  where  )

inline

Definition at line 598 of file _concurrent_unordered_impl.h.

                                                                                 {
        nodeptr_t pnode = (where++).get_node_ptr();
        nodeptr_t prevnode = previous.get_node_ptr();
        __TBB_ASSERT(prevnode->my_next == pnode, "Erase must take consecutive iterators");
        prevnode->my_next = pnode->my_next;
        return pnode;
    }

Referenced by tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::erase_node().

Here is the caller graph for this function:

first_real_iterator() [1/2]

template<typename T, typename Allocator>

iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::first_real_iterator ( raw_iterator  it )

inline

Definition at line 489 of file _concurrent_unordered_impl.h.

    {
        // Skip all dummy, internal only iterators
        while (it != raw_end() && it.get_node_ptr()->is_dummy())
            ++it;

        return iterator(it.get_node_ptr(), this);
    }

Referenced by tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::begin(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::erase_node(), tbb::interface5::internal::concurrent_unordered_base< Traits >::const_range_type::set_midpoint(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::unsafe_begin(), and tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::unsafe_end().

Here is the caller graph for this function:

first_real_iterator() [2/2]

template<typename T, typename Allocator>

const_iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::first_real_iterator ( raw_const_iterator  it ) const

inline

Definition at line 500 of file _concurrent_unordered_impl.h.

    {
        // Skip all dummy, internal only iterators
        while (it != raw_end() && it.get_node_ptr()->is_dummy())
            ++it;

        return const_iterator(it.get_node_ptr(), this);
    }

get_allocator()

template<typename T, typename Allocator>

allocator_type tbb::interface5::internal::split_ordered_list< T, Allocator >::get_allocator ( ) const

inline

Definition at line 357 of file _concurrent_unordered_impl.h.

                                         {
        return (my_node_allocator);
    }

Referenced by tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::get_allocator().

Here is the caller graph for this function:

get_iterator() [1/4]

template<typename T, typename Allocator>

iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::get_iterator ( raw_iterator  it )

inline

Definition at line 465 of file _concurrent_unordered_impl.h.

                                           {
        __TBB_ASSERT(it.get_node_ptr() == NULL || !it.get_node_ptr()->is_dummy(), "Invalid user node (dummy)");
        return iterator(it.get_node_ptr(), this);
    }

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::const_range_type::begin(), tbb::interface5::internal::concurrent_unordered_base< Traits >::const_range_type::end(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::erase_node(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_equal_range(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_erase(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_extract(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_find(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_insert(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::move_all(), and tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::unsafe_erase().

Here is the caller graph for this function:

get_iterator() [2/4]

template<typename T, typename Allocator>

const_iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::get_iterator ( raw_const_iterator  it ) const

inline

Definition at line 472 of file _concurrent_unordered_impl.h.

                                                             {
        __TBB_ASSERT(it.get_node_ptr() == NULL || !it.get_node_ptr()->is_dummy(), "Invalid user node (dummy)");
        return const_iterator(it.get_node_ptr(), this);
    }

get_iterator() [3/4]

template<typename T, typename Allocator>

raw_iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::get_iterator ( raw_const_iterator  it )

inline

Definition at line 478 of file _concurrent_unordered_impl.h.

                                                     {
        return raw_iterator(it.get_node_ptr());
    }

get_iterator() [4/4]

template<typename T, typename Allocator>

static iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::get_iterator ( const_iterator  it )

inlinestatic

Definition at line 483 of file _concurrent_unordered_impl.h.

                                                    {
        return iterator(it.my_node_ptr, it.my_list_ptr);
    }

get_order_key()

template<typename T, typename Allocator>

static sokey_t tbb::interface5::internal::split_ordered_list< T, Allocator >::get_order_key ( const raw_const_iterator &  it )

inlinestatic

Definition at line 454 of file _concurrent_unordered_impl.h.

                                                               {
        return it.get_node_ptr()->get_order_key();
    }

Referenced by tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::check_range(), and tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::insert_dummy().

Here is the caller graph for this function:

get_safe_order_key()

template<typename T, typename Allocator>

static sokey_t tbb::interface5::internal::split_ordered_list< T, Allocator >::get_safe_order_key ( const raw_const_iterator &  it )

inlinestatic

Definition at line 458 of file _concurrent_unordered_impl.h.

                                                                    {
        if( !it.get_node_ptr() )  return ~sokey_t(0);
        return it.get_node_ptr()->get_order_key();
    }

insert_dummy()

template<typename T, typename Allocator>

raw_iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::insert_dummy ( raw_iterator  it, sokey_t  order_key  )

inline

Definition at line 541 of file _concurrent_unordered_impl.h.

    {
        raw_iterator last = raw_end();
        raw_iterator where = it;

        __TBB_ASSERT(where != last, "Invalid head node");

        ++where;

        // Create a dummy element up front, even though it may be discarded (due to concurrent insertion)
        nodeptr_t dummy_node = create_node(order_key);

        for (;;)
        {
            __TBB_ASSERT(it != last, "Invalid head list node");

            // If the head iterator is at the end of the list, or past the point where this dummy
            // node needs to be inserted, then try to insert it.
            if (where == last || get_order_key(where) > order_key)
            {
                __TBB_ASSERT(get_order_key(it) < order_key, "Invalid node order in the list");

                // Try to insert it in the right place
                nodeptr_t inserted_node = try_insert_atomic(it.get_node_ptr(), dummy_node, where.get_node_ptr());

                if (inserted_node == dummy_node)
                {
                    // Insertion succeeded, check the list for order violations
                    check_range(it, where);
                    return raw_iterator(dummy_node);
                }
                else
                {
                    // Insertion failed: either dummy node was inserted by another thread, or
                    // a real element was inserted at exactly the same place as dummy node.
                    // Proceed with the search from the previous location where order key was
                    // known to be larger (note: this is legal only because there is no safe
                    // concurrent erase operation supported).
                    where = it;
                    ++where;
                    continue;
                }
            }
            else if (get_order_key(where) == order_key)
            {
                // Another dummy node with the same value found, discard the new one.
                destroy_node(dummy_node);
                return where;
            }

            // Move the iterator forward
            it = where;
            ++where;
        }

    }

Referenced by tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::init_bucket().

Here is the caller graph for this function:

max_size()

template<typename T, typename Allocator>

size_type tbb::interface5::internal::split_ordered_list< T, Allocator >::max_size ( ) const

inline

Definition at line 417 of file _concurrent_unordered_impl.h.

                               {
        return my_node_allocator.max_size();
    }

Referenced by tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::max_size().

Here is the caller graph for this function:

move_all()

template<typename T, typename Allocator>

void tbb::interface5::internal::split_ordered_list< T, Allocator >::move_all ( self_type &  source )

inline

Definition at line 642 of file _concurrent_unordered_impl.h.

    {
        raw_const_iterator first = source.raw_begin();
        raw_const_iterator last = source.raw_end();

        if (first == last)
            return;

        nodeptr_t previous_node = my_head;
        raw_const_iterator begin_iterator = first++;

        // Move all elements one by one, including dummy ones
        for (raw_const_iterator it = first; it != last;)
        {
            nodeptr_t pnode = it.get_node_ptr();

            nodeptr_t dummy_node = pnode->is_dummy() ? create_node(pnode->get_order_key()) : create_node(pnode->get_order_key(), pnode->my_element);
            previous_node = try_insert_atomic(previous_node, dummy_node, NULL);
            __TBB_ASSERT(previous_node != NULL, "Insertion must succeed");
            raw_const_iterator where = it++;
            source.erase_node(get_iterator(begin_iterator), where);
        }
        check_range();
    }

raw_begin() [1/2]

template<typename T, typename Allocator>

raw_iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::raw_begin ( )

inline

Definition at line 437 of file _concurrent_unordered_impl.h.

                             {
        return raw_iterator(my_head);
    }

Referenced by tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::begin(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::check_range(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::clear(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_init(), and tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::move_all().

Here is the caller graph for this function:

raw_begin() [2/2]

template<typename T, typename Allocator>

raw_const_iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::raw_begin ( ) const

inline

Definition at line 442 of file _concurrent_unordered_impl.h.

                                         {
        return raw_const_iterator(my_head);
    }

raw_end() [1/2]

template<typename T, typename Allocator>

raw_iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::raw_end ( )

inline

Definition at line 446 of file _concurrent_unordered_impl.h.

                           {
        return raw_iterator(0);
    }

Referenced by tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::check_range(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::first_real_iterator(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::insert_dummy(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_equal_range(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_erase(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_extract(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_find(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_insert(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::move_all(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::unsafe_bucket_size(), and tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::unsafe_end().

Here is the caller graph for this function:

raw_end() [2/2]

template<typename T, typename Allocator>

raw_const_iterator tbb::interface5::internal::split_ordered_list< T, Allocator >::raw_end ( ) const

inline

Definition at line 450 of file _concurrent_unordered_impl.h.

                                       {
        return raw_const_iterator(0);
    }

size()

template<typename T, typename Allocator>

size_type tbb::interface5::internal::split_ordered_list< T, Allocator >::size ( ) const

inline

Definition at line 412 of file _concurrent_unordered_impl.h.

                           {
        return my_element_count;
    }

Referenced by tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::size().

Here is the caller graph for this function:

swap()

template<typename T, typename Allocator>

void tbb::interface5::internal::split_ordered_list< T, Allocator >::swap ( self_type &  other )

inline

Definition at line 422 of file _concurrent_unordered_impl.h.

    {
        if (this == &other)
        {
            // Nothing to do
            return;
        }

            std::swap(my_element_count, other.my_element_count);
            std::swap(my_head, other.my_head);
    }

Referenced by tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::swap().

Here is the caller graph for this function:

try_insert()

template<typename T, typename Allocator>

std::pair<iterator, bool> tbb::interface5::internal::split_ordered_list< T, Allocator >::try_insert ( raw_iterator  it, raw_iterator  next, nodeptr_t  pnode, size_type *  new_count  )

inline

Definition at line 523 of file _concurrent_unordered_impl.h.

    {
        nodeptr_t inserted_node = try_insert_atomic(it.get_node_ptr(), pnode, next.get_node_ptr());

        if (inserted_node == pnode)
        {
            // If the insert succeeded, check that the order is correct and increment the element count
            check_range(it, next);
            *new_count = tbb::internal::as_atomic(my_element_count).fetch_and_increment();
            return std::pair<iterator, bool>(iterator(pnode, this), true);
        }
        else
        {
            return std::pair<iterator, bool>(end(), false);
        }
    }

Referenced by tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_insert().

Here is the caller graph for this function:

try_insert_atomic()

template<typename T, typename Allocator>

static nodeptr_t tbb::interface5::internal::split_ordered_list< T, Allocator >::try_insert_atomic ( nodeptr_t  previous, nodeptr_t  new_node, nodeptr_t  current_node  )

inlinestatic

Definition at line 517 of file _concurrent_unordered_impl.h.

                                                                                                       {
        new_node->my_next = current_node;
        return previous->atomic_set_next(new_node, current_node);
    }

Referenced by tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::concurrent_unordered_base(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::insert_dummy(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::move_all(), and tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::try_insert().

Here is the caller graph for this function:

Friends And Related Function Documentation

concurrent_unordered_base

template<typename T, typename Allocator>

template<typename Traits >

friend class concurrent_unordered_base

friend

Definition at line 671 of file _concurrent_unordered_impl.h.

Member Data Documentation

my_element_count

template<typename T, typename Allocator>

size_type tbb::interface5::internal::split_ordered_list< T, Allocator >::my_element_count

private

Definition at line 696 of file _concurrent_unordered_impl.h.

Referenced by tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::clear(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::concurrent_unordered_base(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::empty(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::erase_node(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::size(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::swap(), and tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::try_insert().

my_head

template<typename T, typename Allocator>

nodeptr_t tbb::interface5::internal::split_ordered_list< T, Allocator >::my_head

private

Definition at line 697 of file _concurrent_unordered_impl.h.

Referenced by tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::clear(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::concurrent_unordered_base(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::move_all(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::raw_begin(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::split_ordered_list(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::swap(), and tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::~split_ordered_list().

my_node_allocator

template<typename T, typename Allocator>

tbb::internal::allocator_rebind<allocator_type, node>::type tbb::interface5::internal::split_ordered_list< T, Allocator >::my_node_allocator

private

Definition at line 695 of file _concurrent_unordered_impl.h.

Referenced by tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::create_node(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::create_node_v(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::destroy_node(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::get_allocator(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::max_size(), and tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::operator=().

---

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

• _concurrent_unordered_impl.h