llvm/ProfileData/HashKeyMap.h

0001 //===--- HashKeyMap.h - Wrapper for maps using hash value key ---*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008 ///
0009 /// \file
0010 ///
0011 /// Defines HashKeyMap template.
0012 ///
0013 //===----------------------------------------------------------------------===//
0014
0015 #ifndef LLVM_PROFILEDATA_HASHKEYMAP_H
0016 #define LLVM_PROFILEDATA_HASHKEYMAP_H
0017
0018 #include "llvm/ADT/Hashing.h"
0019 #include <iterator>
0020 #include <utility>
0021
0022 namespace llvm {
0023
0024 namespace sampleprof {
0025
0026 /// This class is a wrapper to associative container MapT<KeyT, ValueT> using
0027 /// the hash value of the original key as the new key. This greatly improves the
0028 /// performance of insert and query operations especially when hash values of
0029 /// keys are available a priori, and reduces memory usage if KeyT has a large
0030 /// size.
0031 /// All keys with the same hash value are considered equivalent (i.e. hash
0032 /// collision is silently ignored). Given such feature this class should only be
0033 /// used where it does not affect compilation correctness, for example, when
0034 /// loading a sample profile. The original key is not stored, so if the user
0035 /// needs to preserve it, it should be stored in the mapped type.
0036 /// Assuming the hashing algorithm is uniform, we use the formula
0037 /// 1 - Permute(n, k) / n ^ k where n is the universe size and k is number of
0038 /// elements chosen at random to calculate the probability of collision. With
0039 /// 1,000,000 entries the probability is negligible:
0040 /// 1 - (2^64)!/((2^64-1000000)!*(2^64)^1000000) ~= 3*10^-8.
0041 /// Source: https://en.wikipedia.org/wiki/Birthday_problem
0042 ///
0043 /// \param MapT The underlying associative container type.
0044 /// \param KeyT The original key type, which requires the implementation of
0045 ///   llvm::hash_value(KeyT).
0046 /// \param ValueT The original mapped type, which has the same requirement as
0047 ///   the underlying container.
0048 /// \param MapTArgs Additional template parameters passed to the underlying
0049 ///   container.
0050 template <template <typename, typename, typename...> typename MapT,
0051           typename KeyT, typename ValueT, typename... MapTArgs>
0052 class HashKeyMap :
0053     public MapT<decltype(hash_value(KeyT())), ValueT, MapTArgs...> {
0054 public:
0055   using base_type = MapT<decltype(hash_value(KeyT())), ValueT, MapTArgs...>;
0056   using key_type = decltype(hash_value(KeyT()));
0057   using original_key_type = KeyT;
0058   using mapped_type = ValueT;
0059   using value_type = typename base_type::value_type;
0060
0061   using iterator = typename base_type::iterator;
0062   using const_iterator = typename base_type::const_iterator;
0063
0064   template <typename... Ts>
0065   std::pair<iterator, bool> try_emplace(const key_type &Hash,
0066                                         const original_key_type &Key,
0067                                         Ts &&...Args) {
0068     assert(Hash == hash_value(Key));
0069     return base_type::try_emplace(Hash, std::forward<Ts>(Args)...);
0070   }
0071
0072   template <typename... Ts>
0073   std::pair<iterator, bool> try_emplace(const original_key_type &Key,
0074                                         Ts &&...Args) {
0075     return try_emplace(hash_value(Key), Key, std::forward<Ts>(Args)...);
0076   }
0077
0078   template <typename... Ts> std::pair<iterator, bool> emplace(Ts &&...Args) {
0079     return try_emplace(std::forward<Ts>(Args)...);
0080   }
0081
0082   mapped_type &operator[](const original_key_type &Key) {
0083     return try_emplace(Key, mapped_type()).first->second;
0084   }
0085
0086   iterator find(const original_key_type &Key) {
0087     auto It = base_type::find(hash_value(Key));
0088     if (It != base_type::end())
0089       return It;
0090     return base_type::end();
0091   }
0092
0093   const_iterator find(const original_key_type &Key) const {
0094     auto It = base_type::find(hash_value(Key));
0095     if (It != base_type::end())
0096       return It;
0097     return base_type::end();
0098   }
0099
0100   mapped_type lookup(const original_key_type &Key) const {
0101     auto It = base_type::find(hash_value(Key));
0102     if (It != base_type::end())
0103       return It->second;
0104     return mapped_type();
0105   }
0106
0107   size_t count(const original_key_type &Key) const {
0108     return base_type::count(hash_value(Key));
0109   }
0110
0111   size_t erase(const original_key_type &Ctx) {
0112     auto It = find(Ctx);
0113     if (It != base_type::end()) {
0114       base_type::erase(It);
0115       return 1;
0116     }
0117     return 0;
0118   }
0119
0120   iterator erase(const_iterator It) {
0121     return base_type::erase(It);
0122   }
0123 };
0124
0125 }
0126
0127 }
0128
0129 #endif // LLVM_PROFILEDATA_HASHKEYMAP_H