Implementation of std::unordered_map. More...

#include <arcane/utils/HashTableMap2.h>

Inheritance diagram for Arcane::impl::HashTableMap2< KeyT, ValueT, HashT, EqT >:

Collaboration diagram for Arcane::impl::HashTableMap2< KeyT, ValueT, HashT, EqT >:

Classes
class	iterator
class	const_iterator

Public Types
using	htype = HashTableMap2<KeyT, ValueT, HashT, EqT>
using	value_type = std::pair<KeyT, ValueT>
using	key_type = KeyT
using	mapped_type = ValueT
using	hasher = HashT
using	key_equal = EqT
Public Types inherited from Arcane::impl::HashTableMap2Base
using	size_type = uint32_t

Public Member Functions
void	init (size_type bucket, float mlf=EMH_DEFAULT_LOAD_FACTOR)
	HashTableMap2 (size_type bucket=2, float mlf=EMH_DEFAULT_LOAD_FACTOR)
	HashTableMap2 (const HashTableMap2 &rhs)
	HashTableMap2 (HashTableMap2 &&rhs) noexcept
	HashTableMap2 (std::initializer_list< value_type > ilist)
template<class InputIt>
	HashTableMap2 (InputIt first, InputIt last, size_type bucket_count=4)
HashTableMap2 &	operator= (const HashTableMap2 &rhs)
HashTableMap2 &	operator= (HashTableMap2 &&rhs) noexcept
template<typename Con>
bool	operator== (const Con &rhs) const
template<typename Con>
bool	operator!= (const Con &rhs) const
void	clone (const HashTableMap2 &rhs)
void	swap (HashTableMap2 &rhs)
iterator	first () const
iterator	last () const
value_type &	front ()
const value_type &	front () const
value_type &	back ()
const value_type &	back () const
void	pop_front ()
void	pop_back ()
iterator	begin ()
const_iterator	cbegin () const
const_iterator	begin () const
iterator	end ()
const_iterator	cend () const
const_iterator	end () const
const value_type *	values () const
const Index *	index () const
size_type	size () const
bool	empty () const
size_type	bucket_count () const
double	load_factor () const
	Returns average number of elements per bucket.
HashT &	hash_function () const
EqT &	key_eq () const
void	max_load_factor (double mlf)
constexpr double	max_load_factor () const
constexpr size_type	max_size () const
constexpr size_type	max_bucket_count () const
template<typename K = KeyT>
iterator	find (const K &key) noexcept
template<typename K = KeyT>
const_iterator	find (const K &key) const noexcept
template<typename K = KeyT>
ValueT &	at (const K &key)
template<typename K = KeyT>
const ValueT &	at (const K &key) const
const ValueT &	index (const uint32_t index) const
ValueT &	index (const uint32_t index)
template<typename K = KeyT>
bool	contains (const K &key) const noexcept
template<typename K = KeyT>
size_type	count (const K &key) const noexcept
template<typename K = KeyT>
std::pair< iterator, iterator >	equal_range (const K &key)
void	merge (HashTableMap2 &rhs)
std::pair< iterator, bool >	add (const KeyT &key, const ValueT &value)
std::pair< iterator, bool >	insert (const value_type &p)
std::pair< iterator, bool >	insert (value_type &&p)
void	insert (std::initializer_list< value_type > ilist)
template<typename Iter>
void	insert (Iter first, Iter last)
template<class... Args>
std::pair< iterator, bool >	emplace (Args &&... args) noexcept
template<class... Args>
iterator	emplace_hint (const_iterator hint, Args &&... args)
template<class... Args>
std::pair< iterator, bool >	try_emplace (const KeyT &k, Args &&... args)
template<class... Args>
std::pair< iterator, bool >	try_emplace (KeyT &&k, Args &&... args)
template<class... Args>
size_type	emplace_unique (Args &&... args)
std::pair< iterator, bool >	insert_or_assign (const KeyT &key, ValueT &&val)
std::pair< iterator, bool >	insert_or_assign (KeyT &&key, ValueT &&val)
ValueT	set_get (const KeyT &key, const ValueT &val)
	Return the old value or ValueT() if it didn't exist.
ValueT &	operator[] (const KeyT &key) noexcept
	Like std::map<KeyT, ValueT>::operator[].
ValueT &	operator[] (KeyT &&key) noexcept
size_type	erase (const KeyT &key) noexcept
iterator	erase (const const_iterator &cit) noexcept
iterator	erase (const_iterator first, const_iterator last) noexcept
template<typename Pred>
size_type	erase_if (Pred pred)
void	clear () noexcept
	Remove all elements, keeping full capacity.
void	shrink_to_fit (const float min_factor=EMH_DEFAULT_LOAD_FACTOR/4)
bool	reserve (uint64_t num_elems, bool force)
	Make room for this many elements.
bool	reserve (size_type required_buckets) noexcept
void	rehash (uint64_t required_buckets)

Static Public Member Functions
static constexpr bool	is_triviall_destructable ()
static constexpr bool	is_copy_trivially ()

Static Public Attributes
static constexpr size_type	INACTIVE = 0xFFFFFFFF
static constexpr size_type	END = 0xFFFFFFFF

Private Member Functions
void	clearkv ()
void	rebuild (size_type num_buckets) noexcept
void	pack_zero (ValueT zero)
bool	try_get (const KeyT &key, ValueT &val) const noexcept
	Returns the matching ValueT or nullptr if k isn't found.
ValueT *	try_get (const KeyT &key) noexcept
	Returns the matching ValueT or nullptr if k isn't found.
ValueT *	try_get (const KeyT &key) const noexcept
	Const version of the above.
bool	try_set (const KeyT &key, const ValueT &val) noexcept
	set value if key exist
bool	try_set (const KeyT &key, ValueT &&val) noexcept
	set value if key exist
ValueT	get_or_return_default (const KeyT &key) const noexcept
	Convenience function.
std::pair< iterator, bool >	_doInsert (const value_type &value) noexcept
std::pair< iterator, bool >	_doInsert (value_type &&value) noexcept
template<typename K, typename V>
std::pair< iterator, bool >	_doInsert (K &&key, V &&val) noexcept
template<typename K, typename V>
std::pair< iterator, bool >	do_assign (K &&key, V &&val) noexcept
template<typename K, typename V>
size_type	insert_unique (K &&key, V &&val)
size_type	insert_unique (value_type &&value)
size_type	insert_unique (const value_type &value)
bool	check_expand_need ()
size_type	slot_to_bucket (const size_type slot) const noexcept
void	erase_slot (const size_type sbucket, const size_type main_bucket) noexcept
size_type	erase_bucket (const size_type bucket, const size_type main_bucket) noexcept
size_type	find_slot_bucket (const size_type slot, size_type &main_bucket) const
size_type	find_filled_bucket (const KeyT &key, uint64_t key_hash) const noexcept
template<typename K = KeyT>
size_type	find_filled_slot (const K &key) const noexcept
size_type	kickout_bucket (const size_type kmain, const size_type bucket) noexcept
template<typename K = KeyT>
size_type	_findOrAllocate (const K &key, uint64_t key_hash) noexcept
size_type	_findUniqueBucket (uint64_t key_hash) noexcept
size_type	_findEmptyBucket (const size_type bucket_from, uint32_t csize) noexcept
size_type	find_last_bucket (size_type main_bucket) const
size_type	find_prev_bucket (const size_type main_bucket, const size_type bucket) const
size_type	hash_bucket (const KeyT &key) const noexcept
size_type	hash_main (const size_type bucket) const noexcept
template<typename UType, typename std::enable_if< std::is_integral< UType >::value, uint32_t >::type = 0>
uint64_t	hash_key (const UType key) const
template<typename UType, typename std::enable_if< std::is_same< UType, std::string >::value, uint32_t >::type = 0>
uint64_t	hash_key (const UType &key) const
template<typename UType, typename std::enable_if<!std::is_integral< UType >::value &&!std::is_same< UType, std::string >::value, uint32_t >::type = 0>
uint64_t	hash_key (const UType &key) const
value_type *	_allocBucket (size_type num_buckets)
void	_freeBuckets ()

Static Private Member Functions
static void	prefetch_heap_block (char *ctrl)

Private Attributes
value_type *	m_pairs = nullptr
HashT	m_hasher
EqT	m_eq
Int64	m_pairs_allocated_size = 0

Static Private Attributes
static constexpr float	EMH_DEFAULT_LOAD_FACTOR = 0.80f
static constexpr float	EMH_MIN_LOAD_FACTOR = 0.25f
static constexpr uint32_t	EMH_CACHE_LINE_SIZE = 64

Additional Inherited Members
Protected Member Functions inherited from Arcane::impl::HashTableMap2Base
void	_allocIndex (size_type num_buckets)
void	_freeIndex ()
void	_doSwap (HashTableMap2Base &rhs)
void	_doClone (const HashTableMap2Base &rhs)
Protected Attributes inherited from Arcane::impl::HashTableMap2Base
Index *	m_index = nullptr
uint32_t	m_mlf = 0
size_type	m_mask = 0
size_type	m_num_buckets = 0
size_type	m_num_filled = 0
size_type	m_last = 0
size_type	m_etail = 0
IMemoryAllocator *	m_memory_allocator = _defaultAllocator()
Static Protected Attributes inherited from Arcane::impl::HashTableMap2Base
static constexpr size_type	EAD = 2

Detailed Description

template<typename KeyT, typename ValueT, typename HashT = std::hash<KeyT>, typename EqT = std::equal_to<KeyT>>
class Arcane::impl::HashTableMap2< KeyT, ValueT, HashT, EqT >

Implementation of std::unordered_map.

Warning: This class is experimental and internal to Arcane.

Definition at line 166 of file HashTableMap2.h.