#include <hashtable.h>

Inheritance diagram for eastl::hashtable< Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys >:

[legend]

Collaboration diagram for eastl::hashtable< Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys >:

[legend]

Public Types
enum	{ kAllocFlagBuckets = eastl::kHashtableAllocFlagBuckets }

typedef Key	key_type

typedef Value	value_type

typedef ExtractKey::result_type	mapped_type

typedef hash_code_base< Key, Value, ExtractKey, Equal, H1, H2, H, bCacheHashCode >	hash_code_base_type

typedef hash_code_base_type::hash_code_t	hash_code_t

typedef Allocator	allocator_type

typedef Equal	key_equal

typedef ptrdiff_t	difference_type

typedef eastl_size_t	size_type

typedef value_type &	reference

typedef const value_type &	const_reference

typedef node_iterator< value_type, !bMutableIterators, bCacheHashCode >	local_iterator

typedef node_iterator< value_type, true, bCacheHashCode >	const_local_iterator

typedef hashtable_iterator< value_type, !bMutableIterators, bCacheHashCode >	iterator

typedef hashtable_iterator< value_type, true, bCacheHashCode >	const_iterator

typedef hash_node< value_type, bCacheHashCode >	node_type

typedef type_select< bUniqueKeys, eastl::pair< iterator, bool >, iterator >::type	insert_return_type

typedef hashtable< Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys >	this_type

typedef RehashPolicy	rehash_policy_type

typedef ExtractKey	extract_key_type

typedef H1	h1_type

typedef H2	h2_type

typedef H	h_type

typedef integral_constant< bool, bUniqueKeys >	has_unique_keys_type

Public Member Functions
	hashtable (size_type nBucketCount, const H1 &, const H2 &, const H &, const Equal &, const ExtractKey &, const allocator_type &allocator=EASTL_HASHTABLE_DEFAULT_ALLOCATOR)

template<typename FowardIterator >
	hashtable (FowardIterator first, FowardIterator last, size_type nBucketCount, const H1 &, const H2 &, const H &, const Equal &, const ExtractKey &, const allocator_type &allocator=EASTL_HASHTABLE_DEFAULT_ALLOCATOR)

	hashtable (const hashtable &x)

	hashtable (this_type &&x)

	hashtable (this_type &&x, const allocator_type &allocator)

const allocator_type &	get_allocator () const EA_NOEXCEPT

allocator_type &	get_allocator () EA_NOEXCEPT

void	set_allocator (const allocator_type &allocator)

this_type &	operator= (const this_type &x)

this_type &	operator= (std::initializer_list< value_type > ilist)

this_type &	operator= (this_type &&x)

void	swap (this_type &x)

iterator	begin () EA_NOEXCEPT

const_iterator	begin () const EA_NOEXCEPT

const_iterator	cbegin () const EA_NOEXCEPT

iterator	end () EA_NOEXCEPT

const_iterator	end () const EA_NOEXCEPT

const_iterator	cend () const EA_NOEXCEPT

local_iterator	begin (size_type n) EA_NOEXCEPT

const_local_iterator	begin (size_type n) const EA_NOEXCEPT

const_local_iterator	cbegin (size_type n) const EA_NOEXCEPT

local_iterator	end (size_type) EA_NOEXCEPT

const_local_iterator	end (size_type) const EA_NOEXCEPT

const_local_iterator	cend (size_type) const EA_NOEXCEPT

bool	empty () const EA_NOEXCEPT

size_type	size () const EA_NOEXCEPT

size_type	bucket_count () const EA_NOEXCEPT

size_type	bucket_size (size_type n) const EA_NOEXCEPT

float	load_factor () const EA_NOEXCEPT

const rehash_policy_type &	rehash_policy () const EA_NOEXCEPT

void	rehash_policy (const rehash_policy_type &rehashPolicy)

template<class... Args>
insert_return_type	emplace (Args &&... args)

template<class... Args>
iterator	emplace_hint (const_iterator position, Args &&... args)

template<class... Args>
insert_return_type	try_emplace (const key_type &k, Args &&... args)

template<class... Args>
insert_return_type	try_emplace (key_type &&k, Args &&... args)

template<class... Args>
iterator	try_emplace (const_iterator position, const key_type &k, Args &&... args)

template<class... Args>
iterator	try_emplace (const_iterator position, key_type &&k, Args &&... args)

insert_return_type	insert (const value_type &value)

insert_return_type	insert (value_type &&otherValue)

iterator	insert (const_iterator hint, const value_type &value)

iterator	insert (const_iterator hint, value_type &&value)

void	insert (std::initializer_list< value_type > ilist)

template<typename InputIterator >
void	insert (InputIterator first, InputIterator last)

template<class P , class = typename eastl::enable_if_t< !eastl::is_literal_type_v<P> && eastl::is_constructible_v<value_type, P&&>>>
insert_return_type	insert (P &&otherValue)

template<class P >
insert_return_type	insert (hash_code_t c, node_type *pNodeNew, P &&otherValue)

insert_return_type	insert (hash_code_t c, node_type *pNodeNew, const value_type &value)

template<class M >
eastl::pair< iterator, bool >	insert_or_assign (const key_type &k, M &&obj)

template<class M >
eastl::pair< iterator, bool >	insert_or_assign (key_type &&k, M &&obj)

template<class M >
iterator	insert_or_assign (const_iterator hint, const key_type &k, M &&obj)

template<class M >
iterator	insert_or_assign (const_iterator hint, key_type &&k, M &&obj)

node_type *	allocate_uninitialized_node ()

void	free_uninitialized_node (node_type *pNode)

iterator	erase (const_iterator position)

iterator	erase (const_iterator first, const_iterator last)

size_type	erase (const key_type &k)

void	clear ()

void	clear (bool clearBuckets)

void	reset_lose_memory () EA_NOEXCEPT

void	rehash (size_type nBucketCount)

void	reserve (size_type nElementCount)

iterator	find (const key_type &key)

const_iterator	find (const key_type &key) const

template<typename U , typename UHash , typename BinaryPredicate >
iterator	find_as (const U &u, UHash uhash, BinaryPredicate predicate)

template<typename U , typename UHash , typename BinaryPredicate >
const_iterator	find_as (const U &u, UHash uhash, BinaryPredicate predicate) const

template<typename U >
iterator	find_as (const U &u)

template<typename U >
const_iterator	find_as (const U &u) const

template<typename HashCodeT >
	ENABLE_IF_HASHCODE_EASTLSIZET (HashCodeT, iterator) find_by_hash(HashCodeT c)

template<typename HashCodeT >
	ENABLE_IF_HASHCODE_EASTLSIZET (HashCodeT, const_iterator) find_by_hash(HashCodeT c) const

iterator	find_by_hash (const key_type &k, hash_code_t c)

const_iterator	find_by_hash (const key_type &k, hash_code_t c) const

eastl::pair< iterator, iterator >	find_range_by_hash (hash_code_t c)

eastl::pair< const_iterator, const_iterator >	find_range_by_hash (hash_code_t c) const

size_type	count (const key_type &k) const EA_NOEXCEPT

eastl::pair< iterator, iterator >	equal_range (const key_type &k)

eastl::pair< const_iterator, const_iterator >	equal_range (const key_type &k) const

bool	validate () const

int	validate_iterator (const_iterator i) const

template<typename FowardIterator >
	hashtable (FowardIterator first, FowardIterator last, size_type nBucketCount, const H1 &h1, const H2 &h2, const H &h, const Eq &eq, const EK &ek, const allocator_type &allocator)

template<typename BoolConstantT , class... Args, ENABLE_IF_TRUETYPE(BoolConstantT) >
eastl::pair< typename hashtable< K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU >::iterator, bool >	DoInsertValue (BoolConstantT, Args &&... args)

template<typename BoolConstantT >
eastl::pair< typename hashtable< K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU >::iterator, bool >	DoInsertValueExtra (BoolConstantT, const key_type &k, hash_code_t c, node_type *pNodeNew, value_type &&value, ENABLE_IF_TRUETYPE(BoolConstantT))

template<typename BoolConstantT >
eastl::pair< typename hashtable< K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU >::iterator, bool >	DoInsertValue (BoolConstantT, value_type &&value, ENABLE_IF_TRUETYPE(BoolConstantT))

template<typename BoolConstantT >
eastl::pair< typename hashtable< K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU >::iterator, bool >	DoInsertValueExtra (BoolConstantT, const key_type &k, hash_code_t c, node_type *pNodeNew, const value_type &value, ENABLE_IF_TRUETYPE(BoolConstantT))

template<typename BoolConstantT >
eastl::pair< typename hashtable< K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU >::iterator, bool >	DoInsertValue (BoolConstantT, const value_type &value, ENABLE_IF_TRUETYPE(BoolConstantT))

template<class M >
eastl::pair< typename hashtable< K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU >::iterator, bool >	insert_or_assign (const key_type &k, M &&obj)

template<class M >
eastl::pair< typename hashtable< K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU >::iterator, bool >	insert_or_assign (key_type &&k, M &&obj)

Static Public Attributes
static const bool	kCacheHashCode = bCacheHashCode

Protected Member Functions
template<typename BoolConstantT >
iterator	DoGetResultIterator (BoolConstantT, const insert_return_type &irt, ENABLE_IF_TRUETYPE(BoolConstantT)=nullptr) const EA_NOEXCEPT

template<typename BoolConstantT >
iterator	DoGetResultIterator (BoolConstantT, const insert_return_type &irt, DISABLE_IF_TRUETYPE(BoolConstantT)=nullptr) const EA_NOEXCEPT

node_type *	DoAllocateNodeFromKey (const key_type &key)

node_type *	DoAllocateNodeFromKey (key_type &&key)

void	DoFreeNode (node_type *pNode)

void	DoFreeNodes (node_type **pBucketArray, size_type)

node_type **	DoAllocateBuckets (size_type n)

void	DoFreeBuckets (node_type **pBucketArray, size_type n)

template<typename BoolConstantT , class... Args, ENABLE_IF_TRUETYPE(BoolConstantT) = nullptr>
eastl::pair< iterator, bool >	DoInsertValue (BoolConstantT, Args &&... args)

template<typename BoolConstantT , class... Args, DISABLE_IF_TRUETYPE(BoolConstantT) = nullptr>
iterator	DoInsertValue (BoolConstantT, Args &&... args)

template<typename BoolConstantT >
eastl::pair< iterator, bool >	DoInsertValueExtra (BoolConstantT, const key_type &k, hash_code_t c, node_type *pNodeNew, value_type &&value, ENABLE_IF_TRUETYPE(BoolConstantT)=nullptr)

template<typename BoolConstantT >
eastl::pair< iterator, bool >	DoInsertValue (BoolConstantT, value_type &&value, ENABLE_IF_TRUETYPE(BoolConstantT)=nullptr)

template<typename BoolConstantT >
iterator	DoInsertValueExtra (BoolConstantT, const key_type &k, hash_code_t c, node_type *pNodeNew, value_type &&value, DISABLE_IF_TRUETYPE(BoolConstantT)=nullptr)

template<typename BoolConstantT >
iterator	DoInsertValue (BoolConstantT, value_type &&value, DISABLE_IF_TRUETYPE(BoolConstantT)=nullptr)

template<typename BoolConstantT >
eastl::pair< iterator, bool >	DoInsertValueExtra (BoolConstantT, const key_type &k, hash_code_t c, node_type *pNodeNew, const value_type &value, ENABLE_IF_TRUETYPE(BoolConstantT)=nullptr)

template<typename BoolConstantT >
eastl::pair< iterator, bool >	DoInsertValue (BoolConstantT, const value_type &value, ENABLE_IF_TRUETYPE(BoolConstantT)=nullptr)

template<typename BoolConstantT >
iterator	DoInsertValueExtra (BoolConstantT, const key_type &k, hash_code_t c, node_type *pNodeNew, const value_type &value, DISABLE_IF_TRUETYPE(BoolConstantT)=nullptr)

template<typename BoolConstantT >
iterator	DoInsertValue (BoolConstantT, const value_type &value, DISABLE_IF_TRUETYPE(BoolConstantT)=nullptr)

template<class... Args>
node_type *	DoAllocateNode (Args &&... args)

node_type *	DoAllocateNode (value_type &&value)

node_type *	DoAllocateNode (const value_type &value)

eastl::pair< iterator, bool >	DoInsertKey (true_type, const key_type &key, hash_code_t c)

iterator	DoInsertKey (false_type, const key_type &key, hash_code_t c)

eastl::pair< iterator, bool >	DoInsertKey (true_type, key_type &&key, hash_code_t c)

iterator	DoInsertKey (false_type, key_type &&key, hash_code_t c)

eastl::pair< iterator, bool >	DoInsertKey (true_type, const key_type &key)

iterator	DoInsertKey (false_type, const key_type &key)

eastl::pair< iterator, bool >	DoInsertKey (true_type, key_type &&key)

iterator	DoInsertKey (false_type, key_type &&key)

void	DoRehash (size_type nBucketCount)

node_type *	DoFindNode (node_type *pNode, const key_type &k, hash_code_t c) const

template<typename T >
	ENABLE_IF_HAS_HASHCODE (T, node_type) DoFindNode(T *pNode

template<typename U , typename BinaryPredicate >
node_type *	DoFindNodeT (node_type *pNode, const U &u, BinaryPredicate predicate) const

Protected Attributes
node_type **	mpBucketArray

size_type	mnBucketCount

size_type	mnElementCount

RehashPolicy	mRehashPolicy

allocator_type	mAllocator

hash_code_t c	const

Detailed Description

template<typename Key, typename Value, typename Allocator, typename ExtractKey, typename Equal, typename H1, typename H2, typename H, typename RehashPolicy, bool bCacheHashCode, bool bMutableIterators, bool bUniqueKeys>
class eastl::hashtable< Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys >

hashtable

Key and Value: arbitrary CopyConstructible types.

ExtractKey: function object that takes a object of type Value and returns a value of type Key.

Equal: function object that takes two objects of type k and returns a bool-like value that is true if the two objects are considered equal.

H1: a hash function. A unary function object with argument type Key and result type size_t. Return values should be distributed over the entire range [0, numeric_limits<uint32_t>::max()].

H2: a range-hashing function (in the terminology of Tavori and Dreizin). This is a function which takes the output of H1 and converts it to the range of [0, n]. Usually it merely takes the output of H1 and mods it to n.

H: a ranged hash function (Tavori and Dreizin). This is merely a class that combines the functionality of H1 and H2 together, possibly in some way that is somehow improved over H1 and H2 It is a binary function whose argument types are Key and size_t and whose result type is uint32_t. Given arguments k and n, the return value is in the range [0, n). Default: h(k, n) = h2(h1(k), n). If H is anything other than the default, H1 and H2 are ignored, as H is thus overriding H1 and H2.

RehashPolicy: Policy class with three members, all of which govern the bucket count. nBucket(n) returns a bucket count no smaller than n. GetBucketCount(n) returns a bucket count appropriate for an element count of n. GetRehashRequired(nBucketCount, nElementCount, nElementAdd) determines whether, if the current bucket count is nBucket and the current element count is nElementCount, we need to increase the bucket count. If so, returns pair(true, n), where n is the new bucket count. If not, returns pair(false, <anything>).

Currently it is hard-wired that the number of buckets never shrinks. Should we allow RehashPolicy to change that?

bCacheHashCode: true if we store the value of the hash function along with the value. This is a time-space tradeoff. Storing it may improve lookup speed by reducing the number of times we need to call the Equal function.

bMutableIterators: true if hashtable::iterator is a mutable iterator, false if iterator and const_iterator are both const iterators. This is true for hash_map and hash_multimap, false for hash_set and hash_multiset.

bUniqueKeys: true if the return value of hashtable::count(k) is always at most one, false if it may be an arbitrary number. This is true for hash_set and hash_map and is false for hash_multiset and hash_multimap.

Note: If you want to make a hashtable never increase its bucket usage, call set_max_load_factor with a very high value such as 100000.f.

find_as In order to support the ability to have a hashtable of strings but be able to do efficiently lookups via char pointers (i.e. so they aren't converted to string objects), we provide the find_as function. This function allows you to do a find with a key of a type other than the hashtable key type. See the find_as function for more documentation on this.

find_by_hash In the interest of supporting fast operations wherever possible, we provide a find_by_hash function which finds a node using its hash code. This is useful for cases where the node's hash is already known, allowing us to avoid a redundant hash operation in the normal find path.

Member Function Documentation

◆ ENABLE_IF_HASHCODE_EASTLSIZET()

template<typename Key , typename Value , typename Allocator , typename ExtractKey , typename Equal , typename H1 , typename H2 , typename H , typename RehashPolicy , bool bCacheHashCode, bool bMutableIterators, bool bUniqueKeys>

template<typename HashCodeT >

eastl::hashtable< Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys >::ENABLE_IF_HASHCODE_EASTLSIZET	(	HashCodeT	,
		iterator
	)

inline

Implements a find whereby the user supplies the node's hash code. It returns an iterator to the first element that matches the given hash. However, there may be multiple elements that match the given hash.

◆ find_as()

template<typename K , typename V , typename A , typename EK , typename Eq , typename H1 , typename H2 , typename H , typename RP , bool bC, bool bM, bool bU>

template<typename U , typename UHash , typename BinaryPredicate >

hashtable< K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU >::iterator eastl::hashtable< K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU >::find_as	(	const U &	u,
		UHash	uhash,
		BinaryPredicate	predicate
	)

inline

Implements a find whereby the user supplies a comparison of a different type than the hashtable value_type. A useful case of this is one whereby you have a container of string objects but want to do searches via passing in char pointers. The problem is that without this kind of find, you need to do the expensive operation of converting the char pointer to a string so it can be used as the argument to the find function.

Example usage (namespaces omitted for brevity): hash_set<string> hashSet; hashSet.find_as("hello"); // Use default hash and compare.

Example usage (note that the predicate uses string as first type and char* as second): hash_set<string> hashSet; hashSet.find_as("hello", hash<char*>(), equal_to_2<string, char*>());

◆ rehash_policy() [1/2]

template<typename Key , typename Value , typename Allocator , typename ExtractKey , typename Equal , typename H1 , typename H2 , typename H , typename RehashPolicy , bool bCacheHashCode, bool bMutableIterators, bool bUniqueKeys>

const rehash_policy_type& eastl::hashtable< Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys >::rehash_policy ( ) const

inline

Generalization of get_max_load_factor. This is an extension that's not present in C++ hash tables (unordered containers).

◆ rehash_policy() [2/2]

template<typename K , typename V , typename A , typename EK , typename Eq , typename H1 , typename H2 , typename H , typename RP , bool bC, bool bM, bool bU>

void eastl::hashtable< K, V, A, EK, Eq, H1, H2, H, RP, bC, bM, bU >::rehash_policy ( const rehash_policy_type & rehashPolicy )

inline

Generalization of set_max_load_factor. This is an extension that's not present in C++ hash tables (unordered containers).

Member Data Documentation

◆ const

template<typename Key , typename Value , typename Allocator , typename ExtractKey , typename Equal , typename H1 , typename H2 , typename H , typename RehashPolicy , bool bCacheHashCode, bool bMutableIterators, bool bUniqueKeys>

hash_code_t c eastl::hashtable< Key, Value, Allocator, ExtractKey, Equal, H1, H2, H, RehashPolicy, bCacheHashCode, bMutableIterators, bUniqueKeys >::const

protected

Initial value:

{
            for (; pNode; pNode = pNode->mpNext)
            {
                if (pNode->mnHashCode == c)
                    return pNode;
            }
            return NULL

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

third_party/EASTL/include/EASTL/internal/hashtable.h

Public Types

Public Member Functions

Static Public Attributes

Protected Member Functions

Protected Attributes

Detailed Description

Member Function Documentation

◆ ENABLE_IF_HASHCODE_EASTLSIZET()

◆ find_as()

◆ rehash_policy() [1/2]

◆ rehash_policy() [2/2]

Member Data Documentation

◆ const