LLVM: llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs (original) (raw)

This class is a wrapper to associative container MapT<KeyT, ValueT> using the hash value of the original key as the new key. More...

#include "[llvm/ProfileData/HashKeyMap.h](HashKeyMap%5F8h%5Fsource.html)"

Public Types
using	base_type = MapT<decltype(hash_value(KeyT())), ValueT, MapTArgs...>
using	key_type = decltype(hash_value(KeyT()))
using	original_key_type = KeyT
using	mapped_type = ValueT
using	value_type = typename base_type::value_type
using	iterator = typename base_type::iterator
using	const_iterator = typename base_type::const_iterator

Public Member Functions
template<typename... Ts>
std::pair< iterator, bool >	try_emplace (const key_type &Hash, const original_key_type &Key, Ts &&...Args)
template<typename... Ts>
std::pair< iterator, bool >	try_emplace (const original_key_type &Key, Ts &&...Args)
template<typename... Ts>
std::pair< iterator, bool >	emplace (Ts &&...Args)
mapped_type &	operator[] (const original_key_type &Key)
iterator	find (const original_key_type &Key)
const_iterator	find (const original_key_type &Key) const
mapped_type	lookup (const original_key_type &Key) const
size_t	count (const original_key_type &Key) const
size_t	erase (const original_key_type &Ctx)
iterator	erase (const_iterator It)

template<template< typename, typename, typename... > typename MapT, typename KeyT, typename ValueT, typename... MapTArgs>
class llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >

This class is a wrapper to associative container MapT<KeyT, ValueT> using the hash value of the original key as the new key.

This greatly improves the performance of insert and query operations especially when hash values of keys are available a priori, and reduces memory usage if KeyT has a large size. All keys with the same hash value are considered equivalent (i.e. hash collision is silently ignored). Given such feature this class should only be used where it does not affect compilation correctness, for example, when loading a sample profile. The original key is not stored, so if the user needs to preserve it, it should be stored in the mapped type. Assuming the hashing algorithm is uniform, we use the formula 1 - Permute(n, k) / n ^ k where n is the universe size and k is number of elements chosen at random to calculate the probability of collision. With 1,000,000 entries the probability is negligible: 1 - (2^64)!/((2^64-1000000)!*(2^64)^1000000) ~= 3*10^-8. Source: https://en.wikipedia.org/wiki/Birthday_problem

Parameters

MapT	The underlying associative container type.
KeyT	The original key type, which requires the implementation of llvm::hash_value(KeyT).
ValueT	The original mapped type, which has the same requirement as the underlying container.
MapTArgs	Additional template parameters passed to the underlying container.

Definition at line 51 of file HashKeyMap.h.