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>
52class HashKeyMap :
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()));
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