LLVM 20.0.0git
Public Types | Public Member Functions | List of all members
llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs > Class Template Reference

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"

Inheritance diagram for llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >:
Inheritance graph
[legend]

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, booltry_emplace (const key_type &Hash, const original_key_type &Key, Ts &&...Args)
 
template<typename... Ts>
std::pair< iterator, booltry_emplace (const original_key_type &Key, Ts &&...Args)
 
template<typename... Ts>
std::pair< iterator, boolemplace (Ts &&...Args)
 
mapped_typeoperator[] (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

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
MapTThe underlying associative container type.
KeyTThe original key type, which requires the implementation of llvm::hash_value(KeyT).
ValueTThe original mapped type, which has the same requirement as the underlying container.
MapTArgsAdditional template parameters passed to the underlying container.

Definition at line 52 of file HashKeyMap.h.

Member Typedef Documentation

◆ base_type

template<template< typename, typename, typename... > typename MapT, typename KeyT , typename ValueT , typename... MapTArgs>
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

template<template< typename, typename, typename... > typename MapT, typename KeyT , typename ValueT , typename... MapTArgs>
using llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::const_iterator = typename base_type::const_iterator

Definition at line 62 of file HashKeyMap.h.

◆ iterator

template<template< typename, typename, typename... > typename MapT, typename KeyT , typename ValueT , typename... MapTArgs>
using llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::iterator = typename base_type::iterator

Definition at line 61 of file HashKeyMap.h.

◆ key_type

template<template< typename, typename, typename... > typename MapT, typename KeyT , typename ValueT , typename... MapTArgs>
using llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::key_type = decltype(hash_value(KeyT()))

Definition at line 56 of file HashKeyMap.h.

◆ mapped_type

template<template< typename, typename, typename... > typename MapT, typename KeyT , typename ValueT , typename... MapTArgs>
using llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::mapped_type = ValueT

Definition at line 58 of file HashKeyMap.h.

◆ original_key_type

template<template< typename, typename, typename... > typename MapT, typename KeyT , typename ValueT , typename... MapTArgs>
using llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::original_key_type = KeyT

Definition at line 57 of file HashKeyMap.h.

◆ value_type

template<template< typename, typename, typename... > typename MapT, typename KeyT , typename ValueT , typename... MapTArgs>
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()

template<template< typename, typename, typename... > typename MapT, typename KeyT , typename ValueT , typename... MapTArgs>
size_t llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::count ( const original_key_type Key) const
inline

Definition at line 107 of file HashKeyMap.h.

References llvm::sampleprof::hash_value().

◆ emplace()

template<template< typename, typename, typename... > typename MapT, typename KeyT , typename ValueT , typename... MapTArgs>
template<typename... Ts>
std::pair< iterator, bool > llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::emplace ( Ts &&...  Args)
inline

◆ erase() [1/2]

template<template< typename, typename, typename... > typename MapT, typename KeyT , typename ValueT , typename... MapTArgs>
size_t llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::erase ( const original_key_type Ctx)
inline

◆ erase() [2/2]

template<template< typename, typename, typename... > typename MapT, typename KeyT , typename ValueT , typename... MapTArgs>
iterator llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::erase ( const_iterator  It)
inline

Definition at line 120 of file HashKeyMap.h.

◆ find() [1/2]

template<template< typename, typename, typename... > typename MapT, typename KeyT , typename ValueT , typename... MapTArgs>
iterator llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::find ( const original_key_type Key)
inline

◆ find() [2/2]

template<template< typename, typename, typename... > typename MapT, typename KeyT , typename ValueT , typename... MapTArgs>
const_iterator llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::find ( const original_key_type Key) const
inline

Definition at line 93 of file HashKeyMap.h.

References llvm::sampleprof::hash_value().

◆ lookup()

template<template< typename, typename, typename... > typename MapT, typename KeyT , typename ValueT , typename... MapTArgs>
mapped_type llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::lookup ( const original_key_type Key) const
inline

Definition at line 100 of file HashKeyMap.h.

References llvm::sampleprof::hash_value().

◆ operator[]()

template<template< typename, typename, typename... > typename MapT, typename KeyT , typename ValueT , typename... MapTArgs>
mapped_type & llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::operator[] ( const original_key_type Key)
inline

◆ try_emplace() [1/2]

template<template< typename, typename, typename... > typename MapT, typename KeyT , typename ValueT , typename... MapTArgs>
template<typename... Ts>
std::pair< iterator, bool > llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::try_emplace ( const key_type Hash,
const original_key_type Key,
Ts &&...  Args 
)
inline

◆ try_emplace() [2/2]

template<template< typename, typename, typename... > typename MapT, typename KeyT , typename ValueT , typename... MapTArgs>
template<typename... Ts>
std::pair< iterator, bool > llvm::sampleprof::HashKeyMap< MapT, KeyT, ValueT, MapTArgs >::try_emplace ( const original_key_type Key,
Ts &&...  Args 
)
inline

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