LLVM 20.0.0git
HashKeyMap.h
Go to the documentation of this file.
1//===--- HashKeyMap.h - Wrapper for maps using hash value key ---*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8///
9/// \file
10///
11/// Defines HashKeyMap template.
12///
13//===----------------------------------------------------------------------===//
14
15#ifndef LLVM_PROFILEDATA_HASHKEYMAP_H
16#define LLVM_PROFILEDATA_HASHKEYMAP_H
17
18#include "llvm/ADT/Hashing.h"
19#include <iterator>
20#include <utility>
21
22namespace llvm {
23
24namespace sampleprof {
25
26/// This class is a wrapper to associative container MapT<KeyT, ValueT> using
27/// the hash value of the original key as the new key. This greatly improves the
28/// performance of insert and query operations especially when hash values of
29/// keys are available a priori, and reduces memory usage if KeyT has a large
30/// size.
31/// All keys with the same hash value are considered equivalent (i.e. hash
32/// collision is silently ignored). Given such feature this class should only be
33/// used where it does not affect compilation correctness, for example, when
34/// loading a sample profile. The original key is not stored, so if the user
35/// needs to preserve it, it should be stored in the mapped type.
36/// Assuming the hashing algorithm is uniform, we use the formula
37/// 1 - Permute(n, k) / n ^ k where n is the universe size and k is number of
38/// elements chosen at random to calculate the probability of collision. With
39/// 1,000,000 entries the probability is negligible:
40/// 1 - (2^64)!/((2^64-1000000)!*(2^64)^1000000) ~= 3*10^-8.
41/// Source: https://en.wikipedia.org/wiki/Birthday_problem
42///
43/// \param MapT The underlying associative container type.
44/// \param KeyT The original key type, which requires the implementation of
45/// llvm::hash_value(KeyT).
46/// \param ValueT The original mapped type, which has the same requirement as
47/// the underlying container.
48/// \param MapTArgs Additional template parameters passed to the underlying
49/// container.
50template <template <typename, typename, typename...> typename MapT,
51 typename KeyT, typename ValueT, typename... MapTArgs>
53 public MapT<decltype(hash_value(KeyT())), ValueT, MapTArgs...> {
54public:
55 using base_type = MapT<decltype(hash_value(KeyT())), ValueT, MapTArgs...>;
56 using key_type = decltype(hash_value(KeyT()));
59 using value_type = typename base_type::value_type;
60
61 using iterator = typename base_type::iterator;
62 using const_iterator = typename base_type::const_iterator;
63
64 template <typename... Ts>
65 std::pair<iterator, bool> try_emplace(const key_type &Hash,
66 const original_key_type &Key,
67 Ts &&...Args) {
68 assert(Hash == hash_value(Key));
69 return base_type::try_emplace(Hash, std::forward<Ts>(Args)...);
70 }
71
72 template <typename... Ts>
73 std::pair<iterator, bool> try_emplace(const original_key_type &Key,
74 Ts &&...Args) {
75 return try_emplace(hash_value(Key), Key, std::forward<Ts>(Args)...);
76 }
77
78 template <typename... Ts> std::pair<iterator, bool> emplace(Ts &&...Args) {
79 return try_emplace(std::forward<Ts>(Args)...);
80 }
81
83 return try_emplace(Key, mapped_type()).first->second;
84 }
85
87 auto It = base_type::find(hash_value(Key));
88 if (It != base_type::end())
89 return It;
90 return base_type::end();
91 }
92
94 auto It = base_type::find(hash_value(Key));
95 if (It != base_type::end())
96 return It;
97 return base_type::end();
98 }
99
101 auto It = base_type::find(hash_value(Key));
102 if (It != base_type::end())
103 return It->second;
104 return mapped_type();
105 }
106
107 size_t count(const original_key_type &Key) const {
108 return base_type::count(hash_value(Key));
109 }
110
111 size_t erase(const original_key_type &Ctx) {
112 auto It = find(Ctx);
113 if (It != base_type::end()) {
114 base_type::erase(It);
115 return 1;
116 }
117 return 0;
118 }
119
121 return base_type::erase(It);
122 }
123};
124
125}
126
127}
128
129#endif // LLVM_PROFILEDATA_HASHKEYMAP_H
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This class is a wrapper to associative container MapT<KeyT, ValueT> using the hash value of the origi...
Definition: HashKeyMap.h:53
MapT< decltype(hash_value(KeyT())), ValueT, MapTArgs... > base_type
Definition: HashKeyMap.h:55
std::pair< iterator, bool > emplace(Ts &&...Args)
Definition: HashKeyMap.h:78
std::pair< iterator, bool > try_emplace(const key_type &Hash, const original_key_type &Key, Ts &&...Args)
Definition: HashKeyMap.h:65
typename base_type::iterator iterator
Definition: HashKeyMap.h:61
const_iterator find(const original_key_type &Key) const
Definition: HashKeyMap.h:93
typename base_type::value_type value_type
Definition: HashKeyMap.h:59
std::pair< iterator, bool > try_emplace(const original_key_type &Key, Ts &&...Args)
Definition: HashKeyMap.h:73
decltype(hash_value(KeyT())) key_type
Definition: HashKeyMap.h:56
size_t erase(const original_key_type &Ctx)
Definition: HashKeyMap.h:111
mapped_type & operator[](const original_key_type &Key)
Definition: HashKeyMap.h:82
size_t count(const original_key_type &Key) const
Definition: HashKeyMap.h:107
iterator find(const original_key_type &Key)
Definition: HashKeyMap.h:86
mapped_type lookup(const original_key_type &Key) const
Definition: HashKeyMap.h:100
typename base_type::const_iterator const_iterator
Definition: HashKeyMap.h:62
iterator erase(const_iterator It)
Definition: HashKeyMap.h:120
uint64_t hash_value(const FunctionId &Obj)
Definition: FunctionId.h:171
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18