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 | |
22 | namespace llvm { |
23 | |
24 | namespace 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. |
50 | template <template <typename, typename, typename...> typename MapT, |
51 | typename KeyT, typename ValueT, typename... MapTArgs> |
52 | class HashKeyMap : |
53 | public MapT<decltype(hash_value(KeyT())), ValueT, MapTArgs...> { |
54 | public: |
55 | using base_type = MapT<decltype(hash_value(KeyT())), ValueT, MapTArgs...>; |
56 | using key_type = decltype(hash_value(KeyT())); |
57 | using original_key_type = KeyT; |
58 | using mapped_type = ValueT; |
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 | |
82 | mapped_type &operator[](const original_key_type &Key) { |
83 | return try_emplace(Key, mapped_type()).first->second; |
84 | } |
85 | |
86 | iterator find(const original_key_type &Key) { |
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 | |
93 | const_iterator find(const original_key_type &Key) const { |
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 | |
100 | mapped_type lookup(const original_key_type &Key) const { |
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 | |
120 | iterator erase(const_iterator It) { |
121 | return base_type::erase(It); |
122 | } |
123 | }; |
124 | |
125 | } |
126 | |
127 | } |
128 | |
129 | #endif // LLVM_PROFILEDATA_HASHKEYMAP_H |
130 | |