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"
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) |
Detailed Description
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 52 of file HashKeyMap.h.
Member Typedef Documentation
◆ base_type
| using llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::base_type = MapT<decltype(hash_value(KeyT())), ValueT, MapTArgs...> |
Definition at line 55 of file HashKeyMap.h.
◆ const_iterator
| using llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::const_iterator = typename base_type::const_iterator |
Definition at line 62 of file HashKeyMap.h.
◆ iterator
| using llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::iterator = typename base_type::iterator |
Definition at line 61 of file HashKeyMap.h.
◆ key_type
| using llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::key_type = decltype(hash_value(KeyT())) |
Definition at line 56 of file HashKeyMap.h.
◆ mapped_type
| using llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::mapped_type = ValueT |
Definition at line 58 of file HashKeyMap.h.
◆ original_key_type
| using llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::original_key_type = KeyT |
Definition at line 57 of file HashKeyMap.h.
◆ value_type
| using llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::value_type = typename base_type::value_type |
Definition at line 59 of file HashKeyMap.h.
Member Function Documentation
◆ count()
|
inline |
Definition at line 107 of file HashKeyMap.h.
References llvm::sampleprof::hash_value().
◆ emplace()
|
inline |
Definition at line 78 of file HashKeyMap.h.
References llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::try_emplace().
◆ erase() [1/2]
|
inline |
Definition at line 111 of file HashKeyMap.h.
References llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::find().
Referenced by llvm::sampleprof::SampleProfileMap::erase().
◆ erase() [2/2]
|
inline |
Definition at line 120 of file HashKeyMap.h.
◆ find() [1/2]
|
inline |
Definition at line 86 of file HashKeyMap.h.
References llvm::sampleprof::hash_value().
Referenced by llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::erase(), and llvm::sampleprof::SampleProfileMap::find().
◆ find() [2/2]
|
inline |
Definition at line 93 of file HashKeyMap.h.
References llvm::sampleprof::hash_value().
◆ lookup()
|
inline |
Definition at line 100 of file HashKeyMap.h.
References llvm::sampleprof::hash_value().
◆ operator[]()
|
inline |
Definition at line 82 of file HashKeyMap.h.
References llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::try_emplace().
◆ try_emplace() [1/2]
|
inline |
Definition at line 65 of file HashKeyMap.h.
References assert(), and llvm::sampleprof::hash_value().
Referenced by llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::emplace(), llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::operator[](), llvm::sampleprof::SampleProfileReaderBinary::readFuncProfile(), and llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::try_emplace().
◆ try_emplace() [2/2]
|
inline |
Definition at line 73 of file HashKeyMap.h.
References llvm::sampleprof::hash_value(), and llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::try_emplace().
The documentation for this class was generated from the following file:
- include/llvm/ProfileData/HashKeyMap.h
