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