Intel(R) Threading Building Blocks Doxygen Documentation version 4.2.3
tbb::interface5::internal::concurrent_unordered_base< Traits > Class Template Reference

#include <_concurrent_unordered_impl.h>

Inheritance diagram for tbb::interface5::internal::concurrent_unordered_base< Traits >:
Collaboration diagram for tbb::interface5::internal::concurrent_unordered_base< Traits >:

Classes

struct  call_internal_clear_on_exit
 
class  const_range_type
 
class  range_type
 

Public Member Functions

allocator_type get_allocator () const
 
bool empty () const
 
size_type size () const
 
size_type max_size () const
 
iterator begin ()
 
const_iterator begin () const
 
iterator end ()
 
const_iterator end () const
 
const_iterator cbegin () const
 
const_iterator cend () const
 
range_type range ()
 
const_range_type range () const
 
std::pair< iterator, bool > insert (const value_type &value)
 
iterator insert (const_iterator, const value_type &value)
 
std::pair< iterator, bool > insert (value_type &&value)
 
iterator insert (const_iterator, value_type &&value)
 
std::pair< iterator, bool > insert (node_type &&nh)
 
iterator insert (const_iterator, node_type &&nh)
 
template<typename... Args>
std::pair< iterator, bool > emplace (Args &&... args)
 
template<typename... Args>
iterator emplace_hint (const_iterator, Args &&... args)
 
template<class Iterator >
void insert (Iterator first, Iterator last)
 
void insert (std::initializer_list< value_type > il)
 Insert initializer list. More...
 
iterator unsafe_erase (const_iterator where)
 
iterator unsafe_erase (const_iterator first, const_iterator last)
 
size_type unsafe_erase (const key_type &key)
 
node_type unsafe_extract (const_iterator where)
 
node_type unsafe_extract (const key_type &key)
 
void swap (concurrent_unordered_base &right)
 
hasher hash_function () const
 
key_equal key_eq () const
 
void clear ()
 
iterator find (const key_type &key)
 
const_iterator find (const key_type &key) const
 
size_type count (const key_type &key) const
 
std::pair< iterator, iteratorequal_range (const key_type &key)
 
std::pair< const_iterator, const_iteratorequal_range (const key_type &key) const
 
size_type unsafe_bucket_count () const
 
size_type unsafe_max_bucket_count () const
 
size_type unsafe_bucket_size (size_type bucket)
 
size_type unsafe_bucket (const key_type &key) const
 
local_iterator unsafe_begin (size_type bucket)
 
const_local_iterator unsafe_begin (size_type bucket) const
 
local_iterator unsafe_end (size_type bucket)
 
const_local_iterator unsafe_end (size_type bucket) const
 
const_local_iterator unsafe_cbegin (size_type bucket) const
 
const_local_iterator unsafe_cend (size_type bucket) const
 
float load_factor () const
 
float max_load_factor () const
 
void max_load_factor (float newmax)
 
void rehash (size_type buckets)
 

Protected Types

typedef concurrent_unordered_base< Traits > self_type
 
typedef Traits::value_type value_type
 
typedef Traits::key_type key_type
 
typedef Traits::hash_compare hash_compare
 
typedef Traits::allocator_type allocator_type
 
typedef hash_compare::hasher hasher
 
typedef hash_compare::key_equal key_equal
 
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 allocator_type::value_typereference
 
typedef const allocator_type::value_typeconst_reference
 
typedef split_ordered_list< value_type, typename Traits::allocator_type > solist_t
 
typedef solist_t::nodeptr_t nodeptr_t
 
typedef solist_t::raw_iterator raw_iterator
 
typedef solist_t::raw_const_iterator raw_const_iterator
 
typedef solist_t::iterator iterator
 
typedef solist_t::const_iterator const_iterator
 
typedef iterator local_iterator
 
typedef const_iterator const_local_iterator
 
typedef Traits::node_type node_type
 

Protected Member Functions

 concurrent_unordered_base (size_type n_of_buckets=initial_bucket_number, const hash_compare &hc=hash_compare(), const allocator_type &a=allocator_type())
 
 concurrent_unordered_base (const concurrent_unordered_base &right, const allocator_type &a)
 
 concurrent_unordered_base (const concurrent_unordered_base &right)
 
 concurrent_unordered_base (concurrent_unordered_base &&right)
 
 concurrent_unordered_base (concurrent_unordered_base &&right, const allocator_type &a)
 
concurrent_unordered_baseoperator= (const concurrent_unordered_base &right)
 
concurrent_unordered_baseoperator= (concurrent_unordered_base &&other)
 
concurrent_unordered_baseoperator= (std::initializer_list< value_type > il)
 assignment operator from initializer_list More...
 
 ~concurrent_unordered_base ()
 
template<typename SourceType >
void internal_merge (SourceType &source)
 

Static Protected Attributes

static const size_type initial_bucket_number = 8
 

Private Types

typedef std::pair< iterator, iteratorpairii_t
 
typedef std::pair< const_iterator, const_iteratorpaircc_t
 

Private Member Functions

void internal_init ()
 
void internal_clear ()
 
void internal_copy (const self_type &right)
 
void internal_swap_buckets (concurrent_unordered_base &right)
 
template<typename AllowCreate , typename AllowDestroy , typename ValueType >
std::pair< iterator, bool > internal_insert (__TBB_FORWARDING_REF(ValueType) value, nodeptr_t pnode=NULL)
 
iterator internal_find (const key_type &key)
 
iterator internal_erase (const_iterator it)
 
std::pair< node_type, raw_iteratorinternal_extract (const_iterator it)
 
pairii_t internal_equal_range (const key_type &key)
 
void init_bucket (size_type bucket)
 
void adjust_table_size (size_type total_elements, size_type current_size)
 
size_type get_parent (size_type bucket) const
 
raw_iterator get_bucket (size_type bucket) const
 
raw_iterator prepare_bucket (sokey_t hash_key)
 
void set_bucket (size_type bucket, raw_iterator dummy_head)
 
bool is_initialized (size_type bucket) const
 
sokey_t split_order_key_regular (sokey_t order_key) const
 
sokey_t split_order_key_dummy (sokey_t order_key) const
 

Static Private Member Functions

static size_type internal_distance (const_iterator first, const_iterator last)
 
static size_type segment_index_of (size_type index)
 
static size_type segment_base (size_type k)
 
static size_type segment_size (size_type k)
 

Private Attributes

atomic< size_typemy_number_of_buckets
 
solist_t my_solist
 
tbb::internal::allocator_rebind< allocator_type, raw_iterator >::type my_allocator
 
float my_maximum_bucket_size
 
atomic< raw_iterator * > my_buckets [pointers_per_table]
 

Static Private Attributes

static size_type const pointers_per_table = sizeof(size_type) * 8
 
static const size_type initial_bucket_load = 4
 

Friends

template<typename OtherTraits >
class concurrent_unordered_base
 

Detailed Description

template<typename Traits>
class tbb::interface5::internal::concurrent_unordered_base< Traits >

Definition at line 706 of file _concurrent_unordered_impl.h.

Member Typedef Documentation

◆ allocator_type

template<typename Traits >
typedef Traits::allocator_type tbb::interface5::internal::concurrent_unordered_base< Traits >::allocator_type
protected

Definition at line 714 of file _concurrent_unordered_impl.h.

◆ const_iterator

template<typename Traits >
typedef solist_t::const_iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::const_iterator
protected

Definition at line 732 of file _concurrent_unordered_impl.h.

◆ const_local_iterator

template<typename Traits >
typedef const_iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::const_local_iterator
protected

Definition at line 734 of file _concurrent_unordered_impl.h.

◆ const_pointer

template<typename Traits >
typedef tbb::internal::allocator_traits<allocator_type>::const_pointer tbb::interface5::internal::concurrent_unordered_base< Traits >::const_pointer
protected

Definition at line 721 of file _concurrent_unordered_impl.h.

◆ const_reference

template<typename Traits >
typedef const allocator_type::value_type& tbb::interface5::internal::concurrent_unordered_base< Traits >::const_reference
protected

Definition at line 724 of file _concurrent_unordered_impl.h.

◆ difference_type

template<typename Traits >
typedef tbb::internal::allocator_traits<allocator_type>::difference_type tbb::interface5::internal::concurrent_unordered_base< Traits >::difference_type
protected

Definition at line 719 of file _concurrent_unordered_impl.h.

◆ hash_compare

template<typename Traits >
typedef Traits::hash_compare tbb::interface5::internal::concurrent_unordered_base< Traits >::hash_compare
protected

Definition at line 713 of file _concurrent_unordered_impl.h.

◆ hasher

template<typename Traits >
typedef hash_compare::hasher tbb::interface5::internal::concurrent_unordered_base< Traits >::hasher
protected

Definition at line 715 of file _concurrent_unordered_impl.h.

◆ iterator

template<typename Traits >
typedef solist_t::iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::iterator
protected

Definition at line 731 of file _concurrent_unordered_impl.h.

◆ key_equal

template<typename Traits >
typedef hash_compare::key_equal tbb::interface5::internal::concurrent_unordered_base< Traits >::key_equal
protected

Definition at line 716 of file _concurrent_unordered_impl.h.

◆ key_type

template<typename Traits >
typedef Traits::key_type tbb::interface5::internal::concurrent_unordered_base< Traits >::key_type
protected

Definition at line 712 of file _concurrent_unordered_impl.h.

◆ local_iterator

template<typename Traits >
typedef iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::local_iterator
protected

Definition at line 733 of file _concurrent_unordered_impl.h.

◆ node_type

template<typename Traits >
typedef Traits::node_type tbb::interface5::internal::concurrent_unordered_base< Traits >::node_type
protected

Definition at line 736 of file _concurrent_unordered_impl.h.

◆ nodeptr_t

template<typename Traits >
typedef solist_t::nodeptr_t tbb::interface5::internal::concurrent_unordered_base< Traits >::nodeptr_t
protected

Definition at line 727 of file _concurrent_unordered_impl.h.

◆ paircc_t

template<typename Traits >
typedef std::pair<const_iterator, const_iterator> tbb::interface5::internal::concurrent_unordered_base< Traits >::paircc_t
private

Definition at line 749 of file _concurrent_unordered_impl.h.

◆ pairii_t

template<typename Traits >
typedef std::pair<iterator, iterator> tbb::interface5::internal::concurrent_unordered_base< Traits >::pairii_t
private

Definition at line 748 of file _concurrent_unordered_impl.h.

◆ pointer

template<typename Traits >
typedef tbb::internal::allocator_traits<allocator_type>::pointer tbb::interface5::internal::concurrent_unordered_base< Traits >::pointer
protected

Definition at line 720 of file _concurrent_unordered_impl.h.

◆ raw_const_iterator

template<typename Traits >
typedef solist_t::raw_const_iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::raw_const_iterator
protected

Definition at line 730 of file _concurrent_unordered_impl.h.

◆ raw_iterator

template<typename Traits >
typedef solist_t::raw_iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::raw_iterator
protected

Definition at line 729 of file _concurrent_unordered_impl.h.

◆ reference

template<typename Traits >
typedef allocator_type::value_type& tbb::interface5::internal::concurrent_unordered_base< Traits >::reference
protected

Definition at line 723 of file _concurrent_unordered_impl.h.

◆ self_type

template<typename Traits >
typedef concurrent_unordered_base<Traits> tbb::interface5::internal::concurrent_unordered_base< Traits >::self_type
protected

Definition at line 710 of file _concurrent_unordered_impl.h.

◆ size_type

template<typename Traits >
typedef tbb::internal::allocator_traits<allocator_type>::size_type tbb::interface5::internal::concurrent_unordered_base< Traits >::size_type
protected

Definition at line 718 of file _concurrent_unordered_impl.h.

◆ solist_t

template<typename Traits >
typedef split_ordered_list<value_type, typename Traits::allocator_type> tbb::interface5::internal::concurrent_unordered_base< Traits >::solist_t
protected

Definition at line 726 of file _concurrent_unordered_impl.h.

◆ value_type

template<typename Traits >
typedef Traits::value_type tbb::interface5::internal::concurrent_unordered_base< Traits >::value_type
protected

Definition at line 711 of file _concurrent_unordered_impl.h.

Constructor & Destructor Documentation

◆ concurrent_unordered_base() [1/5]

template<typename Traits >
tbb::interface5::internal::concurrent_unordered_base< Traits >::concurrent_unordered_base ( size_type  n_of_buckets = initial_bucket_number,
const hash_compare hc = hash_compare(),
const allocator_type a = allocator_type() 
)
inlineprotected

Definition at line 766 of file _concurrent_unordered_impl.h.

768 : Traits(hc), my_solist(a),
770 {
771 if( n_of_buckets == 0) ++n_of_buckets;
772 my_number_of_buckets = size_type(1)<<__TBB_Log2((uintptr_t)n_of_buckets*2-1); // round up to power of 2
774 }
intptr_t __TBB_Log2(uintptr_t x)
Definition: tbb_machine.h:860
tbb::internal::allocator_rebind< allocator_type, raw_iterator >::type my_allocator
tbb::internal::allocator_traits< allocator_type >::size_type size_type

References __TBB_Log2(), tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_init(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::my_number_of_buckets.

Here is the call graph for this function:

◆ concurrent_unordered_base() [2/5]

template<typename Traits >
tbb::interface5::internal::concurrent_unordered_base< Traits >::concurrent_unordered_base ( const concurrent_unordered_base< Traits > &  right,
const allocator_type a 
)
inlineprotected

Definition at line 776 of file _concurrent_unordered_impl.h.

777 : Traits(right.my_hash_compare), my_solist(a), my_allocator(a)
778 {
780 internal_copy(right);
781 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_copy(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_init().

Here is the call graph for this function:

◆ concurrent_unordered_base() [3/5]

template<typename Traits >
tbb::interface5::internal::concurrent_unordered_base< Traits >::concurrent_unordered_base ( const concurrent_unordered_base< Traits > &  right)
inlineprotected

Definition at line 783 of file _concurrent_unordered_impl.h.

784 : Traits(right.my_hash_compare), my_solist(right.get_allocator()), my_allocator(right.get_allocator())
785 {
786 //FIXME:exception safety seems to be broken here
788 internal_copy(right);
789 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_copy(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_init().

Here is the call graph for this function:

◆ concurrent_unordered_base() [4/5]

◆ concurrent_unordered_base() [5/5]

template<typename Traits >
tbb::interface5::internal::concurrent_unordered_base< Traits >::concurrent_unordered_base ( concurrent_unordered_base< Traits > &&  right,
const allocator_type a 
)
inlineprotected

Definition at line 801 of file _concurrent_unordered_impl.h.

802 : Traits(right.my_hash_compare), my_solist(a), my_allocator(a)
803 {
804 call_internal_clear_on_exit clear_buckets_on_exception(this);
805
807 if (a == right.get_allocator()){
810 this->swap(right);
811 }else{
812 my_maximum_bucket_size = right.my_maximum_bucket_size;
813 my_number_of_buckets = right.my_number_of_buckets;
814 my_solist.my_element_count = right.my_solist.my_element_count;
815
816 if (! right.my_solist.empty()){
817 nodeptr_t previous_node = my_solist.my_head;
818
819 // Move all elements one by one, including dummy ones
820 for (raw_const_iterator it = ++(right.my_solist.raw_begin()), last = right.my_solist.raw_end(); it != last; ++it)
821 {
822 const nodeptr_t pnode = it.get_node_ptr();
823 nodeptr_t node;
824 if (pnode->is_dummy()) {
825 node = my_solist.create_node(pnode->get_order_key());
826 size_type bucket = __TBB_ReverseBits(pnode->get_order_key()) % my_number_of_buckets;
827 set_bucket(bucket, node);
828 }else{
829 node = my_solist.create_node(pnode->get_order_key(), std::move(pnode->my_element));
830 }
831
832 previous_node = my_solist.try_insert_atomic(previous_node, node, NULL);
833 __TBB_ASSERT(previous_node != NULL, "Insertion of node failed. Concurrent inserts in constructor ?");
834 }
836 }
837 }
838
839 clear_buckets_on_exception.dismiss();
840 }
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
T __TBB_ReverseBits(T src)
Definition: tbb_machine.h:967
void move(tbb_thread &t1, tbb_thread &t2)
Definition: tbb_thread.h:319
auto last(Container &c) -> decltype(begin(c))
static nodeptr_t try_insert_atomic(nodeptr_t previous, nodeptr_t new_node, nodeptr_t current_node)
void check_range(raw_iterator first, raw_iterator last)
void set_bucket(size_type bucket, raw_iterator dummy_head)

References __TBB_ASSERT, __TBB_ReverseBits(), tbb::interface5::internal::split_ordered_list< T, Allocator >::check_range(), tbb::interface5::internal::split_ordered_list< T, Allocator >::create_node(), tbb::interface5::internal::concurrent_unordered_base< Traits >::call_internal_clear_on_exit::dismiss(), tbb::interface5::internal::concurrent_unordered_base< Traits >::initial_bucket_load, tbb::interface5::internal::concurrent_unordered_base< Traits >::initial_bucket_number, tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_init(), tbb::internal::last(), tbb::move(), tbb::interface5::internal::split_ordered_list< T, Allocator >::my_element_count, tbb::interface5::internal::split_ordered_list< T, Allocator >::my_head, tbb::interface5::internal::concurrent_unordered_base< Traits >::my_maximum_bucket_size, tbb::interface5::internal::concurrent_unordered_base< Traits >::my_number_of_buckets, tbb::interface5::internal::concurrent_unordered_base< Traits >::my_solist, tbb::interface5::internal::concurrent_unordered_base< Traits >::set_bucket(), tbb::interface5::internal::concurrent_unordered_base< Traits >::swap(), and tbb::interface5::internal::split_ordered_list< T, Allocator >::try_insert_atomic().

Here is the call graph for this function:

◆ ~concurrent_unordered_base()

template<typename Traits >
tbb::interface5::internal::concurrent_unordered_base< Traits >::~concurrent_unordered_base ( )
inlineprotected

Definition at line 885 of file _concurrent_unordered_impl.h.

885 {
886 // Delete all node segments
888 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_clear().

Here is the call graph for this function:

Member Function Documentation

◆ adjust_table_size()

template<typename Traits >
void tbb::interface5::internal::concurrent_unordered_base< Traits >::adjust_table_size ( size_type  total_elements,
size_type  current_size 
)
inlineprivate

Definition at line 1578 of file _concurrent_unordered_impl.h.

1579 {
1580 // Grow the table by a factor of 2 if possible and needed
1581 if ( ((float) total_elements / (float) current_size) > my_maximum_bucket_size )
1582 {
1583 // Double the size of the hash only if size has not changed in between loads
1584 my_number_of_buckets.compare_and_swap(2u*current_size, current_size);
1585 //Simple "my_number_of_buckets.compare_and_swap( current_size<<1, current_size );" does not work for VC8
1586 //due to overzealous compiler warnings in /Wp64 mode
1587 }
1588 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::my_maximum_bucket_size, and tbb::interface5::internal::concurrent_unordered_base< Traits >::my_number_of_buckets.

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_insert().

Here is the caller graph for this function:

◆ begin() [1/2]

◆ begin() [2/2]

template<typename Traits >
const_iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::begin ( ) const
inline

◆ cbegin()

◆ cend()

◆ clear()

template<typename Traits >
void tbb::interface5::internal::concurrent_unordered_base< Traits >::clear ( )
inline

Definition at line 1188 of file _concurrent_unordered_impl.h.

1188 {
1189 // Clear list
1190 my_solist.clear();
1191
1192 // Clear buckets
1194
1195 // Initialize bucket 0
1196 __TBB_ASSERT(my_buckets[0] == NULL, NULL);
1197 raw_iterator dummy_node = my_solist.raw_begin();
1198 set_bucket(0, dummy_node);
1199 }
atomic< raw_iterator * > my_buckets[pointers_per_table]

References __TBB_ASSERT, tbb::interface5::internal::split_ordered_list< T, Allocator >::clear(), tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_clear(), tbb::interface5::internal::concurrent_unordered_base< Traits >::my_buckets, tbb::interface5::internal::concurrent_unordered_base< Traits >::my_solist, tbb::interface5::internal::split_ordered_list< T, Allocator >::raw_begin(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::set_bucket().

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_copy(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::operator=().

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

◆ count()

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

Definition at line 1210 of file _concurrent_unordered_impl.h.

1210 {
1211 if(allow_multimapping) {
1212 paircc_t answer = equal_range(key);
1213 size_type item_count = internal_distance(answer.first, answer.second);
1214 return item_count;
1215 } else {
1216 return const_cast<self_type*>(this)->internal_find(key) == end()?0:1;
1217 }
1218 }
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle * key
std::pair< iterator, iterator > equal_range(const key_type &key)
std::pair< const_iterator, const_iterator > paircc_t
static size_type internal_distance(const_iterator first, const_iterator last)

References tbb::interface5::internal::concurrent_unordered_base< Traits >::end(), tbb::interface5::internal::concurrent_unordered_base< Traits >::equal_range(), tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_distance(), tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_find(), and key.

Here is the call graph for this function:

◆ emplace()

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

Definition at line 1112 of file _concurrent_unordered_impl.h.

1112 {
1113 nodeptr_t pnode = my_solist.create_node_v(tbb::internal::forward<Args>(args)...);
1114
1115 return internal_insert</*AllowCreate=*/tbb::internal::false_type,
1116 /*AllowDestroy=*/tbb::internal::true_type>(pnode->my_element, pnode);
1117 }
bool_constant< false > false_type
Definition: tbb_stddef.h:490
nodeptr_t create_node_v(__TBB_FORWARDING_REF(Args) __TBB_PARAMETER_PACK args)
std::pair< iterator, bool > internal_insert(__TBB_FORWARDING_REF(ValueType) value, nodeptr_t pnode=NULL)

References tbb::interface5::internal::split_ordered_list< T, Allocator >::create_node_v(), tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_insert(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::my_solist.

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::emplace_hint().

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

◆ emplace_hint()

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

Definition at line 1120 of file _concurrent_unordered_impl.h.

1120 {
1121 // Ignore hint
1122 return emplace(tbb::internal::forward<Args>(args)...).first;
1123 }
std::pair< iterator, bool > emplace(Args &&... args)

References tbb::interface5::internal::concurrent_unordered_base< Traits >::emplace().

Here is the call graph for this function:

◆ empty()

template<typename Traits >
bool tbb::interface5::internal::concurrent_unordered_base< Traits >::empty ( ) const
inline

◆ end() [1/2]

◆ end() [2/2]

template<typename Traits >
const_iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::end ( ) const
inline

◆ equal_range() [1/2]

◆ equal_range() [2/2]

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

Definition at line 1224 of file _concurrent_unordered_impl.h.

1224 {
1225 return const_cast<self_type*>(this)->internal_equal_range(key);
1226 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_equal_range(), and key.

Here is the call graph for this function:

◆ find() [1/2]

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

Definition at line 1202 of file _concurrent_unordered_impl.h.

1202 {
1203 return internal_find(key);
1204 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_find(), and key.

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_merge().

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

◆ find() [2/2]

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

Definition at line 1206 of file _concurrent_unordered_impl.h.

1206 {
1207 return const_cast<self_type*>(this)->internal_find(key);
1208 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_find(), and key.

Here is the call graph for this function:

◆ get_allocator()

◆ get_bucket()

template<typename Traits >
raw_iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::get_bucket ( size_type  bucket) const
inlineprivate

◆ get_parent()

template<typename Traits >
size_type tbb::interface5::internal::concurrent_unordered_base< Traits >::get_parent ( size_type  bucket) const
inlineprivate

Definition at line 1590 of file _concurrent_unordered_impl.h.

1591 {
1592 // Unsets bucket's most significant turned-on bit
1593 size_type msb = __TBB_Log2((uintptr_t)bucket);
1594 return bucket & ~(size_type(1) << msb);
1595 }

References __TBB_Log2().

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::init_bucket(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::const_range_type::set_midpoint().

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

◆ hash_function()

template<typename Traits >
hasher tbb::interface5::internal::concurrent_unordered_base< Traits >::hash_function ( ) const
inline

Definition at line 1180 of file _concurrent_unordered_impl.h.

1180 {
1181 return my_hash_compare.my_hash_object;
1182 }

◆ init_bucket()

template<typename Traits >
void tbb::interface5::internal::concurrent_unordered_base< Traits >::init_bucket ( size_type  bucket)
inlineprivate

Definition at line 1560 of file _concurrent_unordered_impl.h.

1561 {
1562 // Bucket 0 has no parent.
1563 __TBB_ASSERT( bucket != 0, "The first bucket must always be initialized");
1564
1565 size_type parent_bucket = get_parent(bucket);
1566
1567 // All parent_bucket buckets have to be initialized before this bucket is
1568 if (!is_initialized(parent_bucket))
1569 init_bucket(parent_bucket);
1570
1571 raw_iterator parent = get_bucket(parent_bucket);
1572
1573 // Create a dummy first node in this bucket
1575 set_bucket(bucket, dummy_node);
1576 }
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id parent
raw_iterator insert_dummy(raw_iterator it, sokey_t order_key)

References __TBB_ASSERT, tbb::interface5::internal::concurrent_unordered_base< Traits >::get_bucket(), tbb::interface5::internal::concurrent_unordered_base< Traits >::get_parent(), tbb::interface5::internal::concurrent_unordered_base< Traits >::init_bucket(), tbb::interface5::internal::split_ordered_list< T, Allocator >::insert_dummy(), tbb::interface5::internal::concurrent_unordered_base< Traits >::is_initialized(), tbb::interface5::internal::concurrent_unordered_base< Traits >::my_solist, parent, tbb::interface5::internal::concurrent_unordered_base< Traits >::set_bucket(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::split_order_key_dummy().

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::init_bucket(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::prepare_bucket().

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

◆ insert() [1/8]

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

Definition at line 1068 of file _concurrent_unordered_impl.h.

1068 {
1069 return internal_insert</*AllowCreate=*/tbb::internal::true_type,
1070 /*AllowDestroy=*/tbb::internal::true_type>(value);
1071 }
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long value
bool_constant< true > true_type
Definition: tbb_stddef.h:489

References tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_insert(), and value.

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

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

◆ insert() [2/8]

template<typename Traits >
iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::insert ( const_iterator  ,
const value_type value 
)
inline

Definition at line 1073 of file _concurrent_unordered_impl.h.

1073 {
1074 // Ignore hint
1075 return insert(value).first;
1076 }
std::pair< iterator, bool > insert(const value_type &value)

References tbb::interface5::internal::concurrent_unordered_base< Traits >::insert(), and value.

Here is the call graph for this function:

◆ insert() [3/8]

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

Definition at line 1105 of file _concurrent_unordered_impl.h.

1105 {
1106 return insert(std::move(nh)).first;
1107 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::insert(), and tbb::move().

Here is the call graph for this function:

◆ insert() [4/8]

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

Definition at line 1084 of file _concurrent_unordered_impl.h.

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

References tbb::interface5::internal::concurrent_unordered_base< Traits >::insert(), tbb::move(), and value.

Here is the call graph for this function:

◆ insert() [5/8]

template<typename Traits >
template<class Iterator >
void tbb::interface5::internal::concurrent_unordered_base< Traits >::insert ( Iterator  first,
Iterator  last 
)
inline

Definition at line 1128 of file _concurrent_unordered_impl.h.

1128 {
1129 for (Iterator it = first; it != last; ++it)
1130 insert(*it);
1131 }
auto first(Container &c) -> decltype(begin(c))

References tbb::internal::first(), tbb::interface5::internal::concurrent_unordered_base< Traits >::insert(), and tbb::internal::last().

Here is the call graph for this function:

◆ insert() [6/8]

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

Definition at line 1091 of file _concurrent_unordered_impl.h.

1091 {
1092 if (!nh.empty()) {
1093 nodeptr_t handled_node = nh.my_node;
1094 std::pair<iterator, bool> insert_result =
1096 /*AllowDestroy=*/tbb::internal::false_type>
1097 (handled_node->my_element, handled_node);
1098 if (insert_result.second)
1099 nh.deactivate();
1100 return insert_result;
1101 }
1102 return std::pair<iterator, bool>(end(), false);
1103 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::end(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_insert().

Here is the call graph for this function:

◆ insert() [7/8]

template<typename Traits >
void tbb::interface5::internal::concurrent_unordered_base< Traits >::insert ( std::initializer_list< value_type il)
inline

Insert initializer list.

Definition at line 1135 of file _concurrent_unordered_impl.h.

1135 {
1136 insert(il.begin(), il.end());
1137 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::insert().

Here is the call graph for this function:

◆ insert() [8/8]

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

Definition at line 1079 of file _concurrent_unordered_impl.h.

1079 {
1080 return internal_insert</*AllowCreate=*/tbb::internal::true_type,
1081 /*AllowDestroy=*/tbb::internal::true_type>(std::move(value));
1082 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_insert(), tbb::move(), and value.

Here is the call graph for this function:

◆ internal_clear()

template<typename Traits >
void tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_clear ( )
inlineprivate

◆ internal_copy()

template<typename Traits >
void tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_copy ( const self_type right)
inlineprivate

Definition at line 1364 of file _concurrent_unordered_impl.h.

1364 {
1365 clear();
1366
1367 my_maximum_bucket_size = right.my_maximum_bucket_size;
1368 my_number_of_buckets = right.my_number_of_buckets;
1369
1370 __TBB_TRY {
1371 insert(right.begin(), right.end());
1372 my_hash_compare = right.my_hash_compare;
1373 } __TBB_CATCH(...) {
1374 my_solist.clear();
1375 __TBB_RETHROW();
1376 }
1377 }
#define __TBB_CATCH(e)
Definition: tbb_stddef.h:284
#define __TBB_TRY
Definition: tbb_stddef.h:283
#define __TBB_RETHROW()
Definition: tbb_stddef.h:286

References __TBB_CATCH, __TBB_RETHROW, __TBB_TRY, tbb::interface5::internal::concurrent_unordered_base< Traits >::begin(), tbb::interface5::internal::split_ordered_list< T, Allocator >::clear(), tbb::interface5::internal::concurrent_unordered_base< Traits >::clear(), tbb::interface5::internal::concurrent_unordered_base< Traits >::end(), tbb::interface5::internal::concurrent_unordered_base< Traits >::insert(), tbb::interface5::internal::concurrent_unordered_base< Traits >::my_maximum_bucket_size, tbb::interface5::internal::concurrent_unordered_base< Traits >::my_number_of_buckets, and tbb::interface5::internal::concurrent_unordered_base< Traits >::my_solist.

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::concurrent_unordered_base(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::operator=().

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

◆ internal_distance()

template<typename Traits >
static size_type tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_distance ( const_iterator  first,
const_iterator  last 
)
inlinestaticprivate

Definition at line 1392 of file _concurrent_unordered_impl.h.

1393 {
1394 size_type num = 0;
1395
1396 for (const_iterator it = first; it != last; ++it)
1397 ++num;
1398
1399 return num;
1400 }

References tbb::internal::first(), and tbb::internal::last().

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::count(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_erase().

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

◆ internal_equal_range()

template<typename Traits >
pairii_t tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_equal_range ( const key_type key)
inlineprivate

Definition at line 1533 of file _concurrent_unordered_impl.h.

1534 {
1535 sokey_t hash_key = (sokey_t) my_hash_compare(key);
1536 sokey_t order_key = split_order_key_regular(hash_key);
1537 raw_iterator end_it = my_solist.raw_end();
1538
1539 for (raw_iterator it = prepare_bucket(hash_key); it != end_it; ++it)
1540 {
1541 if (solist_t::get_order_key(it) > order_key)
1542 {
1543 // There is no element with the given key
1544 return pairii_t(end(), end());
1545 }
1546 else if (solist_t::get_order_key(it) == order_key &&
1547 !my_hash_compare(get_key(*it), key)) // TODO: fix negation; also below
1548 {
1551 do ++last; while( allow_multimapping && last != end() && !my_hash_compare(get_key(*last), key) );
1552 return pairii_t(first, last);
1553 }
1554 }
1555
1556 return pairii_t(end(), end());
1557 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::end(), tbb::internal::first(), tbb::interface5::internal::split_ordered_list< T, Allocator >::get_iterator(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::get_order_key(), key, tbb::internal::last(), tbb::interface5::internal::concurrent_unordered_base< Traits >::my_solist, tbb::interface5::internal::concurrent_unordered_base< Traits >::prepare_bucket(), tbb::interface5::internal::split_ordered_list< T, Allocator >::raw_end(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::split_order_key_regular().

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::equal_range().

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

◆ internal_erase()

template<typename Traits >
iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_erase ( const_iterator  it)
inlineprivate

Definition at line 1495 of file _concurrent_unordered_impl.h.

1496 {
1497 sokey_t hash_key = (sokey_t) my_hash_compare(get_key(*it));
1498 raw_iterator previous = prepare_bucket(hash_key);
1500 __TBB_ASSERT(previous != last, "Invalid head node");
1501
1502 // First node is a dummy node
1503 for (raw_iterator where = previous; where != last; previous = where) {
1504 ++where;
1505 if (my_solist.get_iterator(where) == it)
1506 return my_solist.erase_node(previous, it);
1507 }
1508 return end();
1509 }
void erase_node(raw_iterator previous, raw_const_iterator &where, tbb::internal::true_type)

References __TBB_ASSERT, tbb::interface5::internal::concurrent_unordered_base< Traits >::end(), tbb::interface5::internal::split_ordered_list< T, Allocator >::erase_node(), tbb::interface5::internal::split_ordered_list< T, Allocator >::get_iterator(), tbb::internal::last(), tbb::interface5::internal::concurrent_unordered_base< Traits >::my_solist, tbb::interface5::internal::concurrent_unordered_base< Traits >::prepare_bucket(), and tbb::interface5::internal::split_ordered_list< T, Allocator >::raw_end().

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_erase().

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

◆ internal_extract()

template<typename Traits >
std::pair< node_type, raw_iterator > tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_extract ( const_iterator  it)
inlineprivate

Definition at line 1512 of file _concurrent_unordered_impl.h.

1512 {
1513 sokey_t hash_key = sokey_t(my_hash_compare(get_key(*it)));
1514 raw_iterator previous = prepare_bucket(hash_key);
1516 __TBB_ASSERT(previous != last, "Invalid head node");
1517
1518 for(raw_iterator where = previous; where != last; previous = where) {
1519 ++where;
1520 if (my_solist.get_iterator(where) == it) {
1521 const_iterator result = it;
1522 my_solist.erase_node(previous, it, /*allow_destroy*/tbb::internal::false_type());
1523 return std::pair<node_type, raw_iterator>( node_type(result.get_node_ptr()),
1524 previous);
1525 }
1526 }
1527 return std::pair<node_type, iterator>(node_type(), end());
1528 }

References __TBB_ASSERT, tbb::interface5::internal::concurrent_unordered_base< Traits >::end(), tbb::interface5::internal::split_ordered_list< T, Allocator >::erase_node(), tbb::interface5::internal::split_ordered_list< T, Allocator >::get_iterator(), tbb::interface5::internal::solist_iterator< Solist, Value >::get_node_ptr(), tbb::internal::last(), tbb::interface5::internal::concurrent_unordered_base< Traits >::my_solist, tbb::interface5::internal::concurrent_unordered_base< Traits >::prepare_bucket(), and tbb::interface5::internal::split_ordered_list< T, Allocator >::raw_end().

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_extract().

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

◆ internal_find()

template<typename Traits >
iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_find ( const key_type key)
inlineprivate

Definition at line 1467 of file _concurrent_unordered_impl.h.

1468 {
1469 sokey_t hash_key = (sokey_t) my_hash_compare(key);
1470 sokey_t order_key = split_order_key_regular(hash_key);
1472
1473 for (raw_iterator it = prepare_bucket(hash_key); it != last; ++it)
1474 {
1475 if (solist_t::get_order_key(it) > order_key)
1476 {
1477 // If the order key is smaller than the current order key, the element
1478 // is not in the hash.
1479 return end();
1480 }
1481 else if (solist_t::get_order_key(it) == order_key)
1482 {
1483 // The fact that order keys match does not mean that the element is found.
1484 // Key function comparison has to be performed to check whether this is the
1485 // right element. If not, keep searching while order key is the same.
1486 if (!my_hash_compare(get_key(*it), key)) // TODO: fix negation
1487 return my_solist.get_iterator(it);
1488 }
1489 }
1490
1491 return end();
1492 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::end(), tbb::interface5::internal::split_ordered_list< T, Allocator >::get_iterator(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::get_order_key(), key, tbb::internal::last(), tbb::interface5::internal::concurrent_unordered_base< Traits >::my_solist, tbb::interface5::internal::concurrent_unordered_base< Traits >::prepare_bucket(), tbb::interface5::internal::split_ordered_list< T, Allocator >::raw_end(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::split_order_key_regular().

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::count(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::find().

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

◆ internal_init()

template<typename Traits >
void tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_init ( )
inlineprivate

Definition at line 1343 of file _concurrent_unordered_impl.h.

1343 {
1344 // Initialize the array of segment pointers
1345 memset(my_buckets, 0, sizeof(my_buckets));
1346
1347 // Initialize bucket 0
1348 raw_iterator dummy_node = my_solist.raw_begin();
1349 set_bucket(0, dummy_node);
1350 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::my_buckets, tbb::interface5::internal::concurrent_unordered_base< Traits >::my_solist, tbb::interface5::internal::split_ordered_list< T, Allocator >::raw_begin(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::set_bucket().

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::concurrent_unordered_base().

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

◆ internal_insert()

template<typename Traits >
template<typename AllowCreate , typename AllowDestroy , typename ValueType >
std::pair< iterator, bool > tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_insert ( __TBB_FORWARDING_REF(ValueType)  value,
nodeptr_t  pnode = NULL 
)
inlineprivate

Definition at line 1404 of file _concurrent_unordered_impl.h.

1405 {
1406 const key_type *pkey = &get_key(value);
1407 sokey_t hash_key = (sokey_t) my_hash_compare(*pkey);
1408 size_type new_count = 0;
1409 sokey_t order_key = split_order_key_regular(hash_key);
1410 raw_iterator previous = prepare_bucket(hash_key);
1412 __TBB_ASSERT(previous != last, "Invalid head node");
1413
1414 if (pnode) {
1415 // Set new order_key to node
1416 pnode->init(order_key);
1417 }
1418
1419 // First node is a dummy node
1420 for (raw_iterator where = previous;;)
1421 {
1422 ++where;
1423 if (where == last || solist_t::get_order_key(where) > order_key ||
1424 // if multimapped, stop at the first item equal to us.
1425 (allow_multimapping && solist_t::get_order_key(where) == order_key &&
1426 !my_hash_compare(get_key(*where), *pkey))) // TODO: fix negation
1427 {
1428 if (!pnode) {
1429 pnode = my_solist.create_node(order_key, tbb::internal::forward<ValueType>(value), AllowCreate());
1430 // If the value was moved, the known reference to key might be invalid
1431 pkey = &get_key(pnode->my_element);
1432 }
1433
1434 // Try to insert 'pnode' between 'previous' and 'where'
1435 std::pair<iterator, bool> result = my_solist.try_insert(previous, where, pnode, &new_count);
1436
1437 if (result.second)
1438 {
1439 // Insertion succeeded, adjust the table size, if needed
1441 return result;
1442 }
1443 else
1444 {
1445 // Insertion failed: either the same node was inserted by another thread, or
1446 // another element was inserted at exactly the same place as this node.
1447 // Proceed with the search from the previous location where order key was
1448 // known to be larger (note: this is legal only because there is no safe
1449 // concurrent erase operation supported).
1450 where = previous;
1451 continue;
1452 }
1453 }
1454 else if (!allow_multimapping && solist_t::get_order_key(where) == order_key &&
1455 !my_hash_compare(get_key(*where), *pkey)) // TODO: fix negation
1456 { // Element already in the list, return it
1457 if (pnode && AllowDestroy::value)
1458 my_solist.destroy_node(pnode);
1459 return std::pair<iterator, bool>(my_solist.get_iterator(where), false);
1460 }
1461 // Move the iterator forward
1462 previous = where;
1463 }
1464 }
std::pair< iterator, bool > try_insert(raw_iterator it, raw_iterator next, nodeptr_t pnode, size_type *new_count)
void adjust_table_size(size_type total_elements, size_type current_size)

References __TBB_ASSERT, tbb::interface5::internal::concurrent_unordered_base< Traits >::adjust_table_size(), tbb::interface5::internal::split_ordered_list< T, Allocator >::create_node(), tbb::interface5::internal::split_ordered_list< T, Allocator >::destroy_node(), tbb::interface5::internal::split_ordered_list< T, Allocator >::get_iterator(), tbb::interface5::internal::split_ordered_list< value_type, typename Traits::allocator_type >::get_order_key(), tbb::internal::last(), tbb::interface5::internal::concurrent_unordered_base< Traits >::my_number_of_buckets, tbb::interface5::internal::concurrent_unordered_base< Traits >::my_solist, tbb::interface5::internal::concurrent_unordered_base< Traits >::prepare_bucket(), tbb::interface5::internal::split_ordered_list< T, Allocator >::raw_end(), tbb::interface5::internal::concurrent_unordered_base< Traits >::split_order_key_regular(), tbb::interface5::internal::split_ordered_list< T, Allocator >::try_insert(), and value.

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::emplace(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::insert().

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

◆ internal_merge()

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

Definition at line 892 of file _concurrent_unordered_impl.h.

892 {
893 typedef typename SourceType::iterator source_iterator;
895 typename SourceType::node_type>::value),
896 "Incompatible containers cannot be merged");
897
898 for(source_iterator it = source.begin(); it != source.end();) {
899 source_iterator where = it++;
900 if (allow_multimapping || find(get_key(*where)) == end()) {
901 std::pair<node_type, raw_iterator> extract_result = source.internal_extract(where);
902
903 // Remember the old order key
904 sokey_t old_order_key = extract_result.first.my_node->get_order_key();
905
906 // If the insertion fails, it returns ownership of the node to extract_result.first
907 // extract_result.first remains valid node handle
908 if (!insert(std::move(extract_result.first)).second) {
909 raw_iterator next = extract_result.second;
910 raw_iterator current = next++;
911
912 // Revert order key to old value
913 extract_result.first.my_node->init(old_order_key);
914
915 __TBB_ASSERT(extract_result.first.my_node->get_order_key() >= current.get_node_ptr()->get_order_key(),
916 "Wrong nodes order in source container");
917 __TBB_ASSERT(next==source.my_solist.raw_end() ||
918 extract_result.first.my_node->get_order_key() <= next.get_node_ptr()->get_order_key(),
919 "Wrong nodes order in source container");
920
921 size_t new_count = 0;// To use try_insert()
922 bool insert_result =
923 source.my_solist.try_insert(current, next, extract_result.first.my_node, &new_count).second;
924 __TBB_ASSERT_EX(insert_result, "Return to source must be successful. "
925 "Changing source container while merging is unsafe.");
926 }
927 extract_result.first.deactivate();
928 }
929 }
930 }
#define __TBB_ASSERT_EX(predicate, comment)
"Extended" version is useful to suppress warnings if a variable is only used with an assert
Definition: tbb_stddef.h:167
#define __TBB_STATIC_ASSERT(condition, msg)
Definition: tbb_stddef.h:553
Detects whether two given types are the same.

References __TBB_ASSERT, __TBB_ASSERT_EX, __TBB_STATIC_ASSERT, tbb::interface5::internal::concurrent_unordered_base< Traits >::end(), tbb::interface5::internal::concurrent_unordered_base< Traits >::find(), tbb::interface5::internal::flist_iterator< Solist, Value >::get_node_ptr(), tbb::interface5::internal::concurrent_unordered_base< Traits >::insert(), tbb::move(), and value.

Here is the call graph for this function:

◆ internal_swap_buckets()

template<typename Traits >
void tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_swap_buckets ( concurrent_unordered_base< Traits > &  right)
inlineprivate

Definition at line 1379 of file _concurrent_unordered_impl.h.

1380 {
1381 // Swap all node segments
1382 for (size_type index = 0; index < pointers_per_table; ++index)
1383 {
1384 raw_iterator * iterator_pointer = my_buckets[index];
1385 my_buckets[index] = right.my_buckets[index];
1386 right.my_buckets[index] = iterator_pointer;
1387 }
1388 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::my_buckets, and tbb::interface5::internal::concurrent_unordered_base< Traits >::pointers_per_table.

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::swap().

Here is the caller graph for this function:

◆ is_initialized()

◆ key_eq()

template<typename Traits >
key_equal tbb::interface5::internal::concurrent_unordered_base< Traits >::key_eq ( ) const
inline

Definition at line 1184 of file _concurrent_unordered_impl.h.

1184 {
1185 return my_hash_compare.my_key_compare_object;
1186 }

◆ load_factor()

◆ max_load_factor() [1/2]

template<typename Traits >
float tbb::interface5::internal::concurrent_unordered_base< Traits >::max_load_factor ( ) const
inline

◆ max_load_factor() [2/2]

template<typename Traits >
void tbb::interface5::internal::concurrent_unordered_base< Traits >::max_load_factor ( float  newmax)
inline

Definition at line 1324 of file _concurrent_unordered_impl.h.

1324 {
1325 if (newmax != newmax || newmax < 0)
1327 my_maximum_bucket_size = newmax;
1328 }
void throw_exception(exception_id eid)
Versionless convenience wrapper for throw_exception_v4()

References tbb::internal::eid_invalid_load_factor, tbb::interface5::internal::concurrent_unordered_base< Traits >::my_maximum_bucket_size, and tbb::internal::throw_exception().

Here is the call graph for this function:

◆ max_size()

◆ operator=() [1/3]

template<typename Traits >
concurrent_unordered_base & tbb::interface5::internal::concurrent_unordered_base< Traits >::operator= ( concurrent_unordered_base< Traits > &&  other)
inlineprotected

Definition at line 851 of file _concurrent_unordered_impl.h.

852 {
853 if(this != &other){
855 if(pocma_t::value || this->my_allocator == other.my_allocator) {
857 swap(other);
858 if (pocma_t::value) {
859 using std::swap;
860 //TODO: swapping allocators here may be a problem, replace with single direction moving
861 swap(this->my_solist.my_node_allocator, other.my_solist.my_node_allocator);
862 swap(this->my_allocator, other.my_allocator);
863 }
864 } else {
865 concurrent_unordered_base moved_copy(std::move(other),this->my_allocator);
866 this->swap(moved_copy);
867 }
868 }
869 return *this;
870 }
void swap(atomic< T > &lhs, atomic< T > &rhs)
Definition: atomic.h:564
tbb::internal::allocator_rebind< allocator_type, node >::type my_node_allocator

References tbb::move(), tbb::interface5::internal::concurrent_unordered_base< Traits >::my_allocator, tbb::interface5::internal::split_ordered_list< T, Allocator >::my_node_allocator, tbb::interface5::internal::concurrent_unordered_base< Traits >::my_solist, tbb::internal::swap(), tbb::interface5::internal::concurrent_unordered_base< Traits >::swap(), and value.

Here is the call graph for this function:

◆ operator=() [2/3]

template<typename Traits >
concurrent_unordered_base & tbb::interface5::internal::concurrent_unordered_base< Traits >::operator= ( const concurrent_unordered_base< Traits > &  right)
inlineprotected

Definition at line 844 of file _concurrent_unordered_impl.h.

844 {
845 if (this != &right)
846 internal_copy(right);
847 return (*this);
848 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_copy().

Here is the call graph for this function:

◆ operator=() [3/3]

template<typename Traits >
concurrent_unordered_base & tbb::interface5::internal::concurrent_unordered_base< Traits >::operator= ( std::initializer_list< value_type il)
inlineprotected

assignment operator from initializer_list

Definition at line 876 of file _concurrent_unordered_impl.h.

877 {
878 this->clear();
879 this->insert(il.begin(),il.end());
880 return (*this);
881 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::clear(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::insert().

Here is the call graph for this function:

◆ prepare_bucket()

◆ range() [1/2]

template<typename Traits >
range_type tbb::interface5::internal::concurrent_unordered_base< Traits >::range ( )
inline

Definition at line 1059 of file _concurrent_unordered_impl.h.

1059 {
1060 return range_type( *this );
1061 }

◆ range() [2/2]

template<typename Traits >
const_range_type tbb::interface5::internal::concurrent_unordered_base< Traits >::range ( ) const
inline

Definition at line 1063 of file _concurrent_unordered_impl.h.

1063 {
1064 return const_range_type( *this );
1065 }

◆ rehash()

template<typename Traits >
void tbb::interface5::internal::concurrent_unordered_base< Traits >::rehash ( size_type  buckets)
inline

Definition at line 1333 of file _concurrent_unordered_impl.h.

1333 {
1334 size_type current_buckets = my_number_of_buckets;
1335 if (current_buckets >= buckets)
1336 return;
1337 my_number_of_buckets = size_type(1)<<__TBB_Log2((uintptr_t)buckets*2-1); // round up to power of 2
1338 }

References __TBB_Log2(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::my_number_of_buckets.

Here is the call graph for this function:

◆ segment_base()

◆ segment_index_of()

template<typename Traits >
static size_type tbb::interface5::internal::concurrent_unordered_base< Traits >::segment_index_of ( size_type  index)
inlinestaticprivate
Returns
segment index of given index in the array

Definition at line 1600 of file _concurrent_unordered_impl.h.

1600 {
1601 return size_type( __TBB_Log2( uintptr_t(index|1) ) );
1602 }

References __TBB_Log2().

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::get_bucket(), tbb::interface5::internal::concurrent_unordered_base< Traits >::is_initialized(), tbb::interface5::internal::concurrent_unordered_base< Traits >::prepare_bucket(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::set_bucket().

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

◆ segment_size()

template<typename Traits >
static size_type tbb::interface5::internal::concurrent_unordered_base< Traits >::segment_size ( size_type  k)
inlinestaticprivate

◆ set_bucket()

template<typename Traits >
void tbb::interface5::internal::concurrent_unordered_base< Traits >::set_bucket ( size_type  bucket,
raw_iterator  dummy_head 
)
inlineprivate

◆ size()

template<typename Traits >
size_type tbb::interface5::internal::concurrent_unordered_base< Traits >::size ( ) const
inline

◆ split_order_key_dummy()

template<typename Traits >
sokey_t tbb::interface5::internal::concurrent_unordered_base< Traits >::split_order_key_dummy ( sokey_t  order_key) const
inlineprivate

Definition at line 1665 of file _concurrent_unordered_impl.h.

1665 {
1666 return __TBB_ReverseBits(order_key) & ~sokey_t(0x1);
1667 }

References __TBB_ReverseBits().

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::init_bucket().

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

◆ split_order_key_regular()

template<typename Traits >
sokey_t tbb::interface5::internal::concurrent_unordered_base< Traits >::split_order_key_regular ( sokey_t  order_key) const
inlineprivate

◆ swap()

template<typename Traits >
void tbb::interface5::internal::concurrent_unordered_base< Traits >::swap ( concurrent_unordered_base< Traits > &  right)
inline

◆ unsafe_begin() [1/2]

◆ unsafe_begin() [2/2]

◆ unsafe_bucket()

template<typename Traits >
size_type tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_bucket ( const key_type key) const
inline

Definition at line 1248 of file _concurrent_unordered_impl.h.

1248 {
1249 sokey_t order_key = (sokey_t) my_hash_compare(key);
1250 size_type bucket = order_key % my_number_of_buckets;
1251 return bucket;
1252 }

References key, and tbb::interface5::internal::concurrent_unordered_base< Traits >::my_number_of_buckets.

◆ unsafe_bucket_count()

template<typename Traits >
size_type tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_bucket_count ( ) const
inline

◆ unsafe_bucket_size()

◆ unsafe_cbegin()

template<typename Traits >
const_local_iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_cbegin ( size_type  bucket) const
inline

Definition at line 1307 of file _concurrent_unordered_impl.h.

1307 {
1308 return ((const self_type *) this)->unsafe_begin(bucket);
1309 }

◆ unsafe_cend()

template<typename Traits >
const_local_iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_cend ( size_type  bucket) const
inline

Definition at line 1311 of file _concurrent_unordered_impl.h.

1311 {
1312 return ((const self_type *) this)->unsafe_end(bucket);
1313 }

◆ unsafe_end() [1/2]

◆ unsafe_end() [2/2]

◆ unsafe_erase() [1/3]

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

Definition at line 1150 of file _concurrent_unordered_impl.h.

1150 {
1151 pairii_t where = equal_range(key);
1152 size_type item_count = internal_distance(where.first, where.second);
1153 unsafe_erase(where.first, where.second);
1154 return item_count;
1155 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::equal_range(), tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_distance(), key, and tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_erase().

Here is the call graph for this function:

◆ unsafe_erase() [2/3]

◆ unsafe_erase() [3/3]

template<typename Traits >
iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_erase ( const_iterator  where)
inline

Definition at line 1140 of file _concurrent_unordered_impl.h.

1140 {
1141 return internal_erase(where);
1142 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_erase().

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_erase().

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

◆ unsafe_extract() [1/2]

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

Definition at line 1162 of file _concurrent_unordered_impl.h.

1162 {
1163 pairii_t where = equal_range(key);
1164 if (where.first == end()) return node_type(); // element was not found
1165 return internal_extract(where.first).first;
1166 }
std::pair< node_type, raw_iterator > internal_extract(const_iterator it)

References tbb::interface5::internal::concurrent_unordered_base< Traits >::end(), tbb::interface5::internal::concurrent_unordered_base< Traits >::equal_range(), tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_extract(), and key.

Here is the call graph for this function:

◆ unsafe_extract() [2/2]

template<typename Traits >
node_type tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_extract ( const_iterator  where)
inline

Definition at line 1158 of file _concurrent_unordered_impl.h.

1158 {
1159 return internal_extract(where).first;
1160 }

References tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_extract().

Here is the call graph for this function:

◆ unsafe_max_bucket_count()

template<typename Traits >
size_type tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_max_bucket_count ( ) const
inline

Friends And Related Function Documentation

◆ concurrent_unordered_base

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

Definition at line 746 of file _concurrent_unordered_impl.h.

Member Data Documentation

◆ initial_bucket_load

template<typename Traits >
const size_type tbb::interface5::internal::concurrent_unordered_base< Traits >::initial_bucket_load = 4
staticprivate

◆ initial_bucket_number

template<typename Traits >
const size_type tbb::interface5::internal::concurrent_unordered_base< Traits >::initial_bucket_number = 8
staticprotected

◆ my_allocator

◆ my_buckets

◆ my_maximum_bucket_size

◆ my_number_of_buckets

◆ my_solist

template<typename Traits >
solist_t tbb::interface5::internal::concurrent_unordered_base< Traits >::my_solist
private

Definition at line 1671 of file _concurrent_unordered_impl.h.

Referenced by tbb::interface5::internal::concurrent_unordered_base< Traits >::begin(), tbb::interface5::internal::concurrent_unordered_base< Traits >::const_range_type::begin(), tbb::interface5::internal::concurrent_unordered_base< Traits >::cbegin(), tbb::interface5::internal::concurrent_unordered_base< Traits >::cend(), tbb::interface5::internal::concurrent_unordered_base< Traits >::clear(), tbb::interface5::internal::concurrent_unordered_base< Traits >::concurrent_unordered_base(), tbb::interface5::internal::concurrent_unordered_base< Traits >::emplace(), tbb::interface5::internal::concurrent_unordered_base< Traits >::empty(), tbb::interface5::internal::concurrent_unordered_base< Traits >::end(), tbb::interface5::internal::concurrent_unordered_base< Traits >::const_range_type::end(), tbb::interface5::internal::concurrent_unordered_base< Traits >::get_allocator(), tbb::interface5::internal::concurrent_unordered_base< Traits >::init_bucket(), tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_copy(), tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_equal_range(), tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_erase(), tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_extract(), tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_find(), tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_init(), tbb::interface5::internal::concurrent_unordered_base< Traits >::internal_insert(), tbb::interface5::internal::concurrent_unordered_base< Traits >::max_size(), tbb::interface5::internal::concurrent_unordered_base< Traits >::operator=(), tbb::interface5::internal::concurrent_unordered_base< Traits >::const_range_type::set_midpoint(), tbb::interface5::internal::concurrent_unordered_base< Traits >::size(), tbb::interface5::internal::concurrent_unordered_base< Traits >::swap(), tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_begin(), tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_bucket_size(), tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_end(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_erase().

◆ pointers_per_table


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

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

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

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