#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, iterator >	equal_range (const key_type &key)

std::pair< const_iterator, const_iterator >	equal_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_type &	reference

typedef const allocator_type::value_type &	const_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_base &	operator= (const concurrent_unordered_base &right)

concurrent_unordered_base &	operator= (concurrent_unordered_base &&other)

concurrent_unordered_base &	operator= (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, iterator >	pairii_t

typedef std::pair< const_iterator, const_iterator >	paircc_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_iterator >	internal_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_type >	my_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 63 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.

         : Traits(hc), my_solist(a),
           my_allocator(a), my_maximum_bucket_size((float) initial_bucket_load)
     {
         if( n_of_buckets == 0) ++n_of_buckets;
         my_number_of_buckets = size_type(1)<<__TBB_Log2((uintptr_t)n_of_buckets*2-1); // round up to power of 2
         internal_init();
     }

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

         : Traits(right.my_hash_compare), my_solist(a), my_allocator(a)
     {
         internal_init();
         internal_copy(right);
     }

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

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

◆ concurrent_unordered_base() [4/5]

template<typename Traits>

tbb::interface5::internal::concurrent_unordered_base< Traits >::concurrent_unordered_base ( concurrent_unordered_base< Traits > && right )

inlineprotected

Definition at line 792 of file _concurrent_unordered_impl.h.

         : Traits(right.my_hash_compare), my_solist(right.get_allocator()), my_allocator(right.get_allocator()),
           my_maximum_bucket_size(float(initial_bucket_load))
     {
         my_number_of_buckets = initial_bucket_number;
         internal_init();
         swap(right);
     }

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

         : Traits(right.my_hash_compare), my_solist(a), my_allocator(a)
     {
         call_internal_clear_on_exit clear_buckets_on_exception(this);
 
         internal_init();
         if (a == right.get_allocator()){
             my_number_of_buckets = initial_bucket_number;
             my_maximum_bucket_size = float(initial_bucket_load);
             this->swap(right);
         }else{
             my_maximum_bucket_size = right.my_maximum_bucket_size;
             my_number_of_buckets = right.my_number_of_buckets;
             my_solist.my_element_count = right.my_solist.my_element_count;
 
             if (! right.my_solist.empty()){
                 nodeptr_t previous_node = my_solist.my_head;
 
                 // Move all elements one by one, including dummy ones
                 for (raw_const_iterator it = ++(right.my_solist.raw_begin()), last = right.my_solist.raw_end(); it != last; ++it)
                 {
                     const nodeptr_t pnode = it.get_node_ptr();
                     nodeptr_t node;
                     if (pnode->is_dummy()) {
                         node = my_solist.create_node(pnode->get_order_key());
                         size_type bucket = __TBB_ReverseBits(pnode->get_order_key()) % my_number_of_buckets;
                         set_bucket(bucket, node);
                     }else{
                         node = my_solist.create_node(pnode->get_order_key(), std::move(pnode->my_element));
                     }
 
                     previous_node = my_solist.try_insert_atomic(previous_node, node, NULL);
                     __TBB_ASSERT(previous_node != NULL, "Insertion of node failed. Concurrent inserts in constructor ?");
                 }
                 my_solist.check_range();
             }
         }
 
         clear_buckets_on_exception.dismiss();
     }

◆ ~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.

                                  {
         // Delete all node segments
         internal_clear();
     }

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.

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

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:

◆ begin() [1/2]

template<typename Traits>

iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::begin ( )

inline

Definition at line 952 of file _concurrent_unordered_impl.h.

                      {
         return my_solist.begin();
     }

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

Here is the caller graph for this function:

◆ begin() [2/2]

template<typename Traits>

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

inline

Definition at line 956 of file _concurrent_unordered_impl.h.

                                  {
         return my_solist.begin();
     }

◆ cbegin()

template<typename Traits>

const_iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::cbegin ( ) const

inline

Definition at line 968 of file _concurrent_unordered_impl.h.

                                   {
         return my_solist.cbegin();
     }

◆ cend()

template<typename Traits>

const_iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::cend ( ) const

inline

Definition at line 972 of file _concurrent_unordered_impl.h.

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

                  {
         // Clear list
         my_solist.clear();
 
         // Clear buckets
         internal_clear();
 
         // Initialize bucket 0
         __TBB_ASSERT(my_buckets[0] == NULL, NULL);
         raw_iterator dummy_node = my_solist.raw_begin();
         set_bucket(0, dummy_node);
     }

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

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.

                                                {
         if(allow_multimapping) {
             paircc_t answer = equal_range(key);
             size_type item_count = internal_distance(answer.first, answer.second);
             return item_count;
         } else {
             return const_cast<self_type*>(this)->internal_find(key) == end()?0:1;
         }
     }

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

                                                     {
         nodeptr_t pnode = my_solist.create_node_v(tbb::internal::forward<Args>(args)...);
 
         return internal_insert</*AllowCreate=*/tbb::internal::false_type,
                                /*AllowDestroy=*/tbb::internal::true_type>(pnode->my_element, 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_hint().

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.

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

◆ empty()

template<typename Traits>

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

inline

Definition at line 939 of file _concurrent_unordered_impl.h.

                        {
         return my_solist.empty();
     }

◆ end() [1/2]

template<typename Traits>

iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::end ( )

inline

Definition at line 960 of file _concurrent_unordered_impl.h.

                    {
         return my_solist.end();
     }

Here is the caller graph for this function:

◆ end() [2/2]

template<typename Traits>

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

inline

Definition at line 964 of file _concurrent_unordered_impl.h.

                                {
         return my_solist.end();
     }

◆ equal_range() [1/2]

template<typename Traits>

std::pair<iterator, iterator> tbb::interface5::internal::concurrent_unordered_base< Traits >::equal_range ( const key_type & key )

inline

Definition at line 1220 of file _concurrent_unordered_impl.h.

                                                                  {
         return internal_equal_range(key);
     }

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

Here is the caller graph for this function:

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

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

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

                                        {
         return internal_find(key);
     }

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

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.

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

◆ get_allocator()

template<typename Traits>

allocator_type tbb::interface5::internal::concurrent_unordered_base< Traits >::get_allocator ( ) const

inline

Definition at line 934 of file _concurrent_unordered_impl.h.

                                          {
         return my_solist.get_allocator();
     }

◆ get_bucket()

template<typename Traits>

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

inlineprivate

Definition at line 1614 of file _concurrent_unordered_impl.h.

                                                     {
         size_type segment = segment_index_of(bucket);
         bucket -= segment_base(segment);
         __TBB_ASSERT( my_buckets[segment], "bucket must be in an allocated segment" );
         return my_buckets[segment][bucket];
     }

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

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

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

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(), and tbb::interface5::internal::concurrent_unordered_base< Traits >::const_range_type::set_midpoint().

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.

                                  {
         return my_hash_compare.my_hash_object;
     }

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

     {
         // Bucket 0 has no parent.
         __TBB_ASSERT( bucket != 0, "The first bucket must always be initialized");
 
         size_type parent_bucket = get_parent(bucket);
 
         // All parent_bucket buckets have to be initialized before this bucket is
         if (!is_initialized(parent_bucket))
             init_bucket(parent_bucket);
 
         raw_iterator parent = get_bucket(parent_bucket);
 
         // Create a dummy first node in this bucket
         raw_iterator dummy_node = my_solist.insert_dummy(parent, split_order_key_dummy(bucket));
         set_bucket(bucket, dummy_node);
     }

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(), and tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::prepare_bucket().

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.

                                                             {
         return internal_insert</*AllowCreate=*/tbb::internal::true_type,
                                /*AllowDestroy=*/tbb::internal::true_type>(value);
     }

Referenced by tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::insert(), 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::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_merge().

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.

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

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

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

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

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

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

                                                    {
         if (!nh.empty()) {
             nodeptr_t handled_node = nh.my_node;
             std::pair<iterator, bool> insert_result =
                                       internal_insert</*AllowCreate=*/tbb::internal::false_type,
                                                       /*AllowDestroy=*/tbb::internal::false_type>
                                                       (handled_node->my_element, handled_node);
             if (insert_result.second)
                 nh.deactivate();
             return insert_result;
         }
         return std::pair<iterator, bool>(end(), false);
     }

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

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

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

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

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

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

◆ internal_clear()

template<typename Traits>

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

inlineprivate

Definition at line 1352 of file _concurrent_unordered_impl.h.

                           {
         for (size_type index = 0; index < pointers_per_table; ++index) {
             if (my_buckets[index] != NULL) {
                 size_type sz = segment_size(index);
                 for (size_type index2 = 0; index2 < sz; ++index2)
                     my_allocator.destroy(&my_buckets[index][index2]);
                 my_allocator.deallocate(my_buckets[index], sz);
                 my_buckets[index] = 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< Traits >::call_internal_clear_on_exit::~call_internal_clear_on_exit(), and 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:

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

                                                {
         clear();
 
         my_maximum_bucket_size = right.my_maximum_bucket_size;
         my_number_of_buckets = right.my_number_of_buckets;
 
         __TBB_TRY {
             insert(right.begin(), right.end());
             my_hash_compare = right.my_hash_compare;
         } __TBB_CATCH(...) {
             my_solist.clear();
             __TBB_RETHROW();
         }
     }

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(), and tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::operator=().

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.

     {
         size_type num = 0;
 
         for (const_iterator it = first; it != last; ++it)
             ++num;
 
         return num;
     }

Referenced by tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::count(), 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:

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

     {
         sokey_t hash_key = (sokey_t) my_hash_compare(key);
         sokey_t order_key = split_order_key_regular(hash_key);
         raw_iterator end_it = my_solist.raw_end();
 
         for (raw_iterator it = prepare_bucket(hash_key); it != end_it; ++it)
         {
             if (solist_t::get_order_key(it) > order_key)
             {
                 // There is no element with the given key
                 return pairii_t(end(), end());
             }
             else if (solist_t::get_order_key(it) == order_key &&
                      !my_hash_compare(get_key(*it), key)) // TODO: fix negation; also below
             {
                 iterator first = my_solist.get_iterator(it);
                 iterator last = first;
                 do ++last; while( allow_multimapping && last != end() && !my_hash_compare(get_key(*last), key) );
                 return pairii_t(first, last);
             }
         }
 
         return pairii_t(end(), end());
     }

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

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.

     {
         sokey_t hash_key = (sokey_t) my_hash_compare(get_key(*it));
         raw_iterator previous = prepare_bucket(hash_key);
         raw_iterator last = my_solist.raw_end();
         __TBB_ASSERT(previous != last, "Invalid head node");
 
         // First node is a dummy node
         for (raw_iterator where = previous; where != last; previous = where) {
             ++where;
             if (my_solist.get_iterator(where) == it)
                 return my_solist.erase_node(previous, it);
         }
         return end();
     }

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

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

                                                                          {
         sokey_t hash_key = sokey_t(my_hash_compare(get_key(*it)));
         raw_iterator previous = prepare_bucket(hash_key);
         raw_iterator last = my_solist.raw_end();
         __TBB_ASSERT(previous != last, "Invalid head node");
 
         for(raw_iterator where = previous; where != last; previous = where) {
             ++where;
             if (my_solist.get_iterator(where) == it) {
                 const_iterator result = it;
                 my_solist.erase_node(previous, it, /*allow_destroy*/tbb::internal::false_type());
                 return std::pair<node_type, raw_iterator>( node_type(result.get_node_ptr()),
                                                            previous);
             }
         }
         return std::pair<node_type, iterator>(node_type(), end());
     }

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

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.

     {
         sokey_t hash_key = (sokey_t) my_hash_compare(key);
         sokey_t order_key = split_order_key_regular(hash_key);
         raw_iterator last = my_solist.raw_end();
 
         for (raw_iterator it = prepare_bucket(hash_key); it != last; ++it)
         {
             if (solist_t::get_order_key(it) > order_key)
             {
                 // If the order key is smaller than the current order key, the element
                 // is not in the hash.
                 return end();
             }
             else if (solist_t::get_order_key(it) == order_key)
             {
                 // The fact that order keys match does not mean that the element is found.
                 // Key function comparison has to be performed to check whether this is the
                 // right element. If not, keep searching while order key is the same.
                 if (!my_hash_compare(get_key(*it), key)) // TODO: fix negation
                     return my_solist.get_iterator(it);
             }
         }
 
         return end();
     }

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

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.

                          {
         // Initialize the array of segment pointers
         memset(my_buckets, 0, sizeof(my_buckets));
 
         // Initialize bucket 0
         raw_iterator dummy_node = my_solist.raw_begin();
         set_bucket(0, dummy_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().

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.

     {
         const key_type *pkey = &get_key(value);
         sokey_t hash_key = (sokey_t) my_hash_compare(*pkey);
         size_type new_count = 0;
         sokey_t order_key = split_order_key_regular(hash_key);
         raw_iterator previous = prepare_bucket(hash_key);
         raw_iterator last = my_solist.raw_end();
         __TBB_ASSERT(previous != last, "Invalid head node");
 
         if (pnode) {
             // Set new order_key to node
             pnode->init(order_key);
         }
 
         // First node is a dummy node
         for (raw_iterator where = previous;;)
         {
             ++where;
             if (where == last || solist_t::get_order_key(where) > order_key ||
                 // if multimapped, stop at the first item equal to us.
                 (allow_multimapping && solist_t::get_order_key(where) == order_key &&
                  !my_hash_compare(get_key(*where), *pkey))) // TODO: fix negation
             {
                 if (!pnode) {
                     pnode = my_solist.create_node(order_key, tbb::internal::forward<ValueType>(value), AllowCreate());
                     // If the value was moved, the known reference to key might be invalid
                     pkey = &get_key(pnode->my_element);
                 }
 
                 // Try to insert 'pnode' between 'previous' and 'where'
                 std::pair<iterator, bool> result = my_solist.try_insert(previous, where, pnode, &new_count);
 
                 if (result.second)
                 {
                     // Insertion succeeded, adjust the table size, if needed
                     adjust_table_size(new_count, my_number_of_buckets);
                     return result;
                 }
                 else
                 {
                     // Insertion failed: either the same node was inserted by another thread, or
                     // another element was inserted at exactly the same place as this 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 = previous;
                     continue;
                 }
             }
             else if (!allow_multimapping && solist_t::get_order_key(where) == order_key &&
                      !my_hash_compare(get_key(*where), *pkey)) // TODO: fix negation
             { // Element already in the list, return it
                  if (pnode && AllowDestroy::value)
                      my_solist.destroy_node(pnode);
                 return std::pair<iterator, bool>(my_solist.get_iterator(where), false);
             }
             // Move the iterator forward
             previous = where;
         }
     }

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

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.

                                             {
         typedef typename SourceType::iterator source_iterator;
         __TBB_STATIC_ASSERT((tbb::internal::is_same_type<node_type,
                             typename SourceType::node_type>::value),
                             "Incompatible containers cannot be merged");
 
         for(source_iterator it = source.begin(); it != source.end();) {
             source_iterator where = it++;
             if (allow_multimapping || find(get_key(*where)) == end()) {
                 std::pair<node_type, raw_iterator> extract_result = source.internal_extract(where);
 
                 // Remember the old order key
                 sokey_t old_order_key = extract_result.first.my_node->get_order_key();
 
                 // If the insertion fails, it returns ownership of the node to extract_result.first
                 // extract_result.first remains valid node handle
                 if (!insert(std::move(extract_result.first)).second) {
                     raw_iterator next = extract_result.second;
                     raw_iterator current = next++;
 
                     // Revert order key to old value
                     extract_result.first.my_node->init(old_order_key);
 
                     __TBB_ASSERT(extract_result.first.my_node->get_order_key() >= current.get_node_ptr()->get_order_key(),
                                 "Wrong nodes order in source container");
                     __TBB_ASSERT(next==source.my_solist.raw_end() ||
                                  extract_result.first.my_node->get_order_key() <= next.get_node_ptr()->get_order_key(),
                                  "Wrong nodes order in source container");
 
                     size_t new_count = 0;// To use try_insert()
                     bool insert_result =
                         source.my_solist.try_insert(current, next, extract_result.first.my_node, &new_count).second;
                     __TBB_ASSERT_EX(insert_result, "Return to source must be successful. "
                                                    "Changing source container while merging is unsafe.");
                 }
                 extract_result.first.deactivate();
             }
         }
     }

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

     {
         // Swap all node segments
         for (size_type index = 0; index < pointers_per_table; ++index)
         {
             raw_iterator * iterator_pointer = my_buckets[index];
             my_buckets[index] = right.my_buckets[index];
             right.my_buckets[index] = iterator_pointer;
         }
     }

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:

◆ is_initialized()

template<typename Traits>

bool tbb::interface5::internal::concurrent_unordered_base< Traits >::is_initialized ( size_type bucket ) const

inlineprivate

Definition at line 1646 of file _concurrent_unordered_impl.h.

                                                 {
         size_type segment = segment_index_of(bucket);
         bucket -= segment_base(segment);
 
         if (my_buckets[segment] == NULL)
             return false;
 
         raw_iterator it = my_buckets[segment][bucket];
         return (it.get_node_ptr() != NULL);
     }

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

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

                              {
         return my_hash_compare.my_key_compare_object;
     }

◆ load_factor()

template<typename Traits>

float tbb::interface5::internal::concurrent_unordered_base< Traits >::load_factor ( ) const

inline

Definition at line 1316 of file _concurrent_unordered_impl.h.

                               {
         return (float) size() / (float) unsafe_bucket_count();
     }

◆ max_load_factor() [1/2]

template<typename Traits>

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

inline

Definition at line 1320 of file _concurrent_unordered_impl.h.

                                   {
         return my_maximum_bucket_size;
     }

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

                                        {
         if (newmax != newmax || newmax < 0)
             tbb::internal::throw_exception(tbb::internal::eid_invalid_load_factor);
         my_maximum_bucket_size = newmax;
     }

◆ max_size()

template<typename Traits>

size_type tbb::interface5::internal::concurrent_unordered_base< Traits >::max_size ( ) const

inline

Definition at line 947 of file _concurrent_unordered_impl.h.

                                {
         return my_solist.max_size();
     }

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

                                                                                  {
         if (this != &right)
             internal_copy(right);
         return (*this);
     }

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

     {
         if(this != &other){
             typedef typename tbb::internal::allocator_traits<allocator_type>::propagate_on_container_move_assignment pocma_t;
             if(pocma_t::value || this->my_allocator == other.my_allocator) {
                 concurrent_unordered_base trash (std::move(*this));
                 swap(other);
                 if (pocma_t::value) {
                     using std::swap;
                     //TODO: swapping allocators here may be a problem, replace with single direction moving
                     swap(this->my_solist.my_node_allocator, other.my_solist.my_node_allocator);
                     swap(this->my_allocator, other.my_allocator);
                 }
             } else {
                 concurrent_unordered_base moved_copy(std::move(other),this->my_allocator);
                 this->swap(moved_copy);
             }
         }
         return *this;
     }

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

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

◆ prepare_bucket()

template<typename Traits>

raw_iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::prepare_bucket ( sokey_t hash_key )

inlineprivate

Definition at line 1621 of file _concurrent_unordered_impl.h.

                                                   {
         size_type bucket = hash_key % my_number_of_buckets;
         size_type segment = segment_index_of(bucket);
         size_type index = bucket - segment_base(segment);
         if (my_buckets[segment] == NULL || my_buckets[segment][index].get_node_ptr() == NULL)
             init_bucket(bucket);
         return my_buckets[segment][index];
     }

Here is the caller graph for this function:

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

                        {
         return range_type( *this );
     }

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

                                    {
         return const_range_type( *this );
     }

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

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

◆ segment_base()

template<typename Traits>

static size_type tbb::interface5::internal::concurrent_unordered_base< Traits >::segment_base ( size_type k )

inlinestaticprivate

Returns: the first array index of given segment

Definition at line 1605 of file _concurrent_unordered_impl.h.

                                                  {
         return (size_type(1)<<k & ~size_type(1));
     }

Here is the caller graph for this function:

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

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

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

Returns: segment size

Definition at line 1610 of file _concurrent_unordered_impl.h.

                                                  {
         return k? size_type(1)<<k : 2;
     }

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

Here is the caller graph for this function:

◆ set_bucket()

template<typename Traits>

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

inlineprivate

Definition at line 1630 of file _concurrent_unordered_impl.h.

                                                                {
         size_type segment = segment_index_of(bucket);
         bucket -= segment_base(segment);
 
         if (my_buckets[segment] == NULL) {
             size_type sz = segment_size(segment);
             raw_iterator * new_segment = my_allocator.allocate(sz);
             std::memset(static_cast<void*>(new_segment), 0, sz*sizeof(raw_iterator));
 
             if (my_buckets[segment].compare_and_swap( new_segment, NULL) != NULL)
                 my_allocator.deallocate(new_segment, sz);
         }
 
         my_buckets[segment][bucket] = dummy_head;
     }

Here is the caller graph for this function:

◆ size()

template<typename Traits>

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

inline

Definition at line 943 of file _concurrent_unordered_impl.h.

                            {
         return my_solist.size();
     }

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

Here is the caller graph for this function:

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

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

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:

◆ 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

Definition at line 1660 of file _concurrent_unordered_impl.h.

                                                              {
         return __TBB_ReverseBits(order_key) | 0x1;
     }

Referenced by 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_find(), and 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:

◆ swap()

template<typename Traits>

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

inline

Definition at line 1169 of file _concurrent_unordered_impl.h.

                                                 {
         if (this != &right) {
             std::swap(my_hash_compare, right.my_hash_compare);
             my_solist.swap(right.my_solist);
             internal_swap_buckets(right);
             std::swap(my_number_of_buckets, right.my_number_of_buckets);
             std::swap(my_maximum_bucket_size, right.my_maximum_bucket_size);
         }
     }

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(), and tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::operator=().

Here is the caller graph for this function:

◆ unsafe_begin() [1/2]

template<typename Traits>

local_iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_begin ( size_type bucket )

inline

Definition at line 1255 of file _concurrent_unordered_impl.h.

                                                   {
         if (!is_initialized(bucket))
             return end();
 
         raw_iterator it = get_bucket(bucket);
         return my_solist.first_real_iterator(it);
     }

◆ unsafe_begin() [2/2]

template<typename Traits>

const_local_iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_begin ( size_type bucket ) const

inline

Definition at line 1264 of file _concurrent_unordered_impl.h.

     {
         if (!is_initialized(bucket))
             return end();
 
         raw_const_iterator it = get_bucket(bucket);
         return my_solist.first_real_iterator(it);
     }

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

                                                        {
         sokey_t order_key = (sokey_t) my_hash_compare(key);
         size_type bucket = order_key % my_number_of_buckets;
         return bucket;
     }

◆ unsafe_bucket_count()

template<typename Traits>

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

inline

Definition at line 1229 of file _concurrent_unordered_impl.h.

                                           {
         return my_number_of_buckets;
     }

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

Here is the caller graph for this function:

◆ unsafe_bucket_size()

template<typename Traits>

size_type tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_bucket_size ( size_type bucket )

inline

Definition at line 1237 of file _concurrent_unordered_impl.h.

                                                    {
         size_type item_count = 0;
         if (is_initialized(bucket)) {
             raw_iterator it = get_bucket(bucket);
             ++it;
             for (; it != my_solist.raw_end() && !it.get_node_ptr()->is_dummy(); ++it)
                 ++item_count;
         }
         return item_count;
     }

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

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

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

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

◆ unsafe_end() [1/2]

template<typename Traits>

local_iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_end ( size_type bucket )

inline

Definition at line 1275 of file _concurrent_unordered_impl.h.

     {
         if (!is_initialized(bucket))
             return end();
 
         raw_iterator it = get_bucket(bucket);
 
         // Find the end of the bucket, denoted by the dummy element
         do ++it;
         while(it != my_solist.raw_end() && !it.get_node_ptr()->is_dummy());
 
         // Return the first real element past the end of the bucket
         return my_solist.first_real_iterator(it);
     }

◆ unsafe_end() [2/2]

template<typename Traits>

const_local_iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_end ( size_type bucket ) const

inline

Definition at line 1292 of file _concurrent_unordered_impl.h.

     {
         if (!is_initialized(bucket))
             return end();
 
         raw_const_iterator it = get_bucket(bucket);
 
         // Find the end of the bucket, denoted by the dummy element
         do ++it;
         while(it != my_solist.raw_end() && !it.get_node_ptr()->is_dummy());
 
         // Return the first real element past the end of the bucket
         return my_solist.first_real_iterator(it);
     }

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

                                                 {
         return internal_erase(where);
     }

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

◆ unsafe_erase() [2/3]

template<typename Traits>

iterator tbb::interface5::internal::concurrent_unordered_base< Traits >::unsafe_erase	(	const_iterator	first,
		const_iterator	last
	)

inline

Definition at line 1144 of file _concurrent_unordered_impl.h.

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

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

                                                 {
         pairii_t where = equal_range(key);
         size_type item_count = internal_distance(where.first, where.second);
         unsafe_erase(where.first, where.second);
         return item_count;
     }

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

                                                    {
         return internal_extract(where).first;
     }

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

                                                   {
         pairii_t where = equal_range(key);
         if (where.first == end()) return node_type(); // element was not found
         return internal_extract(where.first).first;
     }

◆ unsafe_max_bucket_count()

template<typename Traits>

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

inline

Definition at line 1233 of file _concurrent_unordered_impl.h.

                                               {
         return segment_size(pointers_per_table-1);
     }

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

Definition at line 752 of file _concurrent_unordered_impl.h.

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

◆ initial_bucket_number

template<typename Traits>

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

staticprotected

Definition at line 742 of file _concurrent_unordered_impl.h.

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

◆ my_allocator

template<typename Traits>

tbb::internal::allocator_rebind<allocator_type, raw_iterator>::type tbb::interface5::internal::concurrent_unordered_base< Traits >::my_allocator

private

Definition at line 1672 of file _concurrent_unordered_impl.h.

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

◆ my_buckets

template<typename Traits>

atomic<raw_iterator*> tbb::interface5::internal::concurrent_unordered_base< Traits >::my_buckets[pointers_per_table]

private

Definition at line 1674 of file _concurrent_unordered_impl.h.

◆ my_maximum_bucket_size

template<typename Traits>

float tbb::interface5::internal::concurrent_unordered_base< Traits >::my_maximum_bucket_size

private

Definition at line 1673 of file _concurrent_unordered_impl.h.

Referenced by tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::adjust_table_size(), 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::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::internal_copy(), tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::max_load_factor(), and tbb::interface5::internal::concurrent_unordered_base< concurrent_unordered_map_traits< Key, T, internal::hash_compare< Key, Hasher, Key_equality >, Allocator, false > >::swap().

◆ my_number_of_buckets

template<typename Traits>

atomic<size_type> tbb::interface5::internal::concurrent_unordered_base< Traits >::my_number_of_buckets

private

Definition at line 1670 of file _concurrent_unordered_impl.h.

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

◆ pointers_per_table

template<typename Traits>

size_type const tbb::interface5::internal::concurrent_unordered_base< Traits >::pointers_per_table = sizeof(size_type) * 8

staticprivate

Definition at line 751 of file _concurrent_unordered_impl.h.

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

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

_concurrent_unordered_impl.h

Classes

Public Member Functions

Protected Types

Protected Member Functions

Static Protected Attributes

Private Types

Private Member Functions

Static Private Member Functions

Private Attributes

Static Private Attributes

Friends

Detailed Description

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

Member Typedef Documentation

◆ allocator_type

◆ const_iterator

◆ const_local_iterator

◆ const_pointer

◆ const_reference

◆ difference_type

◆ hash_compare

◆ hasher

◆ iterator

◆ key_equal

◆ key_type

◆ local_iterator

◆ node_type

◆ nodeptr_t

◆ paircc_t

◆ pairii_t

◆ pointer

◆ raw_const_iterator

◆ raw_iterator

◆ reference

◆ self_type

◆ size_type

◆ solist_t

◆ value_type

Constructor & Destructor Documentation

◆ concurrent_unordered_base() [1/5]

◆ concurrent_unordered_base() [2/5]

◆ concurrent_unordered_base() [3/5]

◆ concurrent_unordered_base() [4/5]

◆ concurrent_unordered_base() [5/5]

◆ ~concurrent_unordered_base()

Member Function Documentation

◆ adjust_table_size()

◆ begin() [1/2]

◆ begin() [2/2]

◆ cbegin()

◆ cend()

◆ clear()

◆ count()

◆ emplace()

◆ emplace_hint()

◆ empty()

◆ end() [1/2]

◆ end() [2/2]

◆ equal_range() [1/2]

◆ equal_range() [2/2]

◆ find() [1/2]

◆ find() [2/2]

◆ get_allocator()

◆ get_bucket()

◆ get_parent()

◆ hash_function()

◆ init_bucket()

◆ insert() [1/8]

◆ insert() [2/8]

◆ insert() [3/8]

◆ insert() [4/8]

◆ insert() [5/8]

◆ insert() [6/8]

◆ insert() [7/8]

◆ insert() [8/8]

◆ internal_clear()

◆ internal_copy()

◆ internal_distance()

◆ internal_equal_range()

◆ internal_erase()

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