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> try_emplace(const key_type & Hash,const original_key_type & Key,Ts &&...Args)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> try_emplace(const original_key_type & Key,Ts &&...Args)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 emplace(Ts &&...Args)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 find(const original_key_type & Key)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 find(const original_key_type & Key)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 lookup(const original_key_type & Key)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 count(const original_key_type & Key)107 size_t count(const original_key_type &Key) const { 108 return base_type::count(hash_value(Key)); 109 } 110 erase(const original_key_type & Ctx)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 erase(const_iterator It)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