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

## Public Attributes

const typedef value_type & | const_reference

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

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

inline private

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:

## check_range() [2/2]

template<typename T, typename Allocator>

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

inline private

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:

## 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>

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

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

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);
}

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

## 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>

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

inline static

Definition at line 483 of file _concurrent_unordered_impl.h.

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

## get_iterator() [2/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() [3/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() [4/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_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 | ) |

inline static

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

inline static

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

inline static

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

## const_reference

template<typename T, typename Allocator>

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

Definition at line 220 of file _concurrent_unordered_impl.h.

## 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

tbb::interface5::internal::split_ordered_list::const_iterator
solist_iterator< self_type, const value_type > const_iterator
Definition: _concurrent_unordered_impl.h:222
tbb::interface5::internal::split_ordered_list::get_iterator
iterator get_iterator(raw_iterator it)
Definition: _concurrent_unordered_impl.h:465
tbb::interface5::internal::split_ordered_list::my_node_allocator
tbb::internal::allocator_rebind< allocator_type, node >::type my_node_allocator
Definition: _concurrent_unordered_impl.h:695
__TBB_ASSERT
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
tbb::interface5::internal::sokey_t
size_t sokey_t
Definition: _concurrent_unordered_impl.h:198
tbb::interface5::internal::split_ordered_list::erase_node_impl
nodeptr_t erase_node_impl(raw_iterator previous, raw_const_iterator &where)
Definition: _concurrent_unordered_impl.h:598
tbb::interface5::internal::split_ordered_list::clear
void clear()
Definition: _concurrent_unordered_impl.h:361
tbb::interface5::internal::split_ordered_list::raw_end
raw_iterator raw_end()
Definition: _concurrent_unordered_impl.h:446
tbb::internal::swap
void swap(atomic< T > &lhs, atomic< T > &rhs)
Definition: atomic.h:564
tbb::internal::bool_constant
Definition: tbb_stddef.h:486
tbb::interface5::internal::split_ordered_list::check_range
void check_range()
Definition: _concurrent_unordered_impl.h:688
tbb::interface5::internal::split_ordered_list::erase_node
void erase_node(raw_iterator previous, raw_const_iterator &where, tbb::internal::true_type)
Definition: _concurrent_unordered_impl.h:607
tbb::interface5::internal::split_ordered_list::raw_begin
raw_iterator raw_begin()
Definition: _concurrent_unordered_impl.h:437
tbb::interface5::internal::split_ordered_list::end
iterator end()
Definition: _concurrent_unordered_impl.h:390
tbb::interface5::internal::split_ordered_list::my_element_count
size_type my_element_count
Definition: _concurrent_unordered_impl.h:696
tbb::interface5::internal::split_ordered_list::first_real_iterator
iterator first_real_iterator(raw_iterator it)
Definition: _concurrent_unordered_impl.h:489
tbb::interface5::internal::split_ordered_list::iterator
solist_iterator< self_type, value_type > iterator
Definition: _concurrent_unordered_impl.h:223
tbb::interface5::internal::flist_iterator::get_node_ptr
nodeptr_t get_node_ptr() const
Definition: _concurrent_unordered_impl.h:108
tbb::interface5::internal::split_ordered_list::get_order_key
static sokey_t get_order_key(const raw_const_iterator &it)
Definition: _concurrent_unordered_impl.h:454
tbb::interface5::internal::split_ordered_list::try_insert_atomic
static nodeptr_t try_insert_atomic(nodeptr_t previous, nodeptr_t new_node, nodeptr_t current_node)
Definition: _concurrent_unordered_impl.h:517
tbb::interface5::internal::split_ordered_list::create_node
nodeptr_t create_node(sokey_t order_key)
Definition: _concurrent_unordered_impl.h:285
tbb::interface5::internal::split_ordered_list::nodeptr_t
node * nodeptr_t
Definition: _concurrent_unordered_impl.h:210
tbb::internal::first
auto first(Container &c) -> decltype(begin(c))
Definition: _range_iterator.h:34
tbb::interface5::internal::split_ordered_list::self_type
split_ordered_list< T, Allocator > self_type
Definition: _concurrent_unordered_impl.h:206
__TBB_TRY
#define __TBB_TRY
Definition: tbb_stddef.h:283
tbb::interface5::internal::split_ordered_list::destroy_node
void destroy_node(nodeptr_t pnode)
Definition: _concurrent_unordered_impl.h:510
tbb::internal::suppress_unused_warning
void suppress_unused_warning(const T1 &)
Utility template function to prevent "unused" warnings by various compilers.
Definition: tbb_stddef.h:398
tbb::interface5::internal::split_ordered_list::raw_const_iterator
flist_iterator< self_type, const value_type > raw_const_iterator
Definition: _concurrent_unordered_impl.h:224
tbb::internal::as_atomic
atomic< T > & as_atomic(T &t)
Definition: atomic.h:572
tbb::internal::last
auto last(Container &c) -> decltype(begin(c))
Definition: _range_iterator.h:40
__TBB_CATCH
#define __TBB_CATCH(e)
Definition: tbb_stddef.h:284
tbb::interface5::internal::split_ordered_list::my_head
nodeptr_t my_head
Definition: _concurrent_unordered_impl.h:697
__TBB_RETHROW
#define __TBB_RETHROW()
Definition: tbb_stddef.h:286
tbb::interface5::internal::split_ordered_list::raw_iterator
flist_iterator< self_type, value_type > raw_iterator
Definition: _concurrent_unordered_impl.h:225
__TBB_PACK_EXPANSION
#define __TBB_PACK_EXPANSION(A)
Definition: tbb_stddef.h:525
tbb::interface5::internal::split_ordered_list::node::is_dummy
bool is_dummy() const
Definition: _concurrent_unordered_impl.h:274
tbb::interface5::internal::split_ordered_list::begin
iterator begin()
Definition: _concurrent_unordered_impl.h:381

Copyright © 2005-2020 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.