Line data Source code
1 : //===- llvm/ADT/DenseMapInfo.h - Type traits for DenseMap -------*- C++ -*-===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file defines DenseMapInfo traits for DenseMap.
11 : //
12 : //===----------------------------------------------------------------------===//
13 :
14 : #ifndef LLVM_ADT_DENSEMAPINFO_H
15 : #define LLVM_ADT_DENSEMAPINFO_H
16 :
17 : #include "llvm/ADT/ArrayRef.h"
18 : #include "llvm/ADT/Hashing.h"
19 : #include "llvm/ADT/StringRef.h"
20 : #include "llvm/Support/PointerLikeTypeTraits.h"
21 : #include <cassert>
22 : #include <cstddef>
23 : #include <cstdint>
24 : #include <utility>
25 :
26 : namespace llvm {
27 :
28 : template<typename T>
29 : struct DenseMapInfo {
30 : //static inline T getEmptyKey();
31 : //static inline T getTombstoneKey();
32 : //static unsigned getHashValue(const T &Val);
33 : //static bool isEqual(const T &LHS, const T &RHS);
34 : };
35 :
36 : // Provide DenseMapInfo for all pointers.
37 : template<typename T>
38 : struct DenseMapInfo<T*> {
39 : static inline T* getEmptyKey() {
40 : uintptr_t Val = static_cast<uintptr_t>(-1);
41 : Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
42 : return reinterpret_cast<T*>(Val);
43 : }
44 :
45 : static inline T* getTombstoneKey() {
46 : uintptr_t Val = static_cast<uintptr_t>(-2);
47 : Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
48 : return reinterpret_cast<T*>(Val);
49 : }
50 :
51 : static unsigned getHashValue(const T *PtrVal) {
52 10207752152 : return (unsigned((uintptr_t)PtrVal) >> 4) ^
53 9317407270 : (unsigned((uintptr_t)PtrVal) >> 9);
54 : }
55 :
56 12079686373 : static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
57 : };
58 :
59 : // Provide DenseMapInfo for chars.
60 : template<> struct DenseMapInfo<char> {
61 : static inline char getEmptyKey() { return ~0; }
62 : static inline char getTombstoneKey() { return ~0 - 1; }
63 200 : static unsigned getHashValue(const char& Val) { return Val * 37U; }
64 :
65 0 : static bool isEqual(const char &LHS, const char &RHS) {
66 200 : return LHS == RHS;
67 : }
68 : };
69 :
70 : // Provide DenseMapInfo for unsigned shorts.
71 : template <> struct DenseMapInfo<unsigned short> {
72 : static inline unsigned short getEmptyKey() { return 0xFFFF; }
73 : static inline unsigned short getTombstoneKey() { return 0xFFFF - 1; }
74 257617 : static unsigned getHashValue(const unsigned short &Val) { return Val * 37U; }
75 :
76 0 : static bool isEqual(const unsigned short &LHS, const unsigned short &RHS) {
77 336668 : return LHS == RHS;
78 : }
79 : };
80 :
81 : // Provide DenseMapInfo for unsigned ints.
82 : template<> struct DenseMapInfo<unsigned> {
83 : static inline unsigned getEmptyKey() { return ~0U; }
84 : static inline unsigned getTombstoneKey() { return ~0U - 1; }
85 1134898716 : static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
86 :
87 0 : static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
88 1363910409 : return LHS == RHS;
89 : }
90 : };
91 :
92 : // Provide DenseMapInfo for unsigned longs.
93 : template<> struct DenseMapInfo<unsigned long> {
94 : static inline unsigned long getEmptyKey() { return ~0UL; }
95 : static inline unsigned long getTombstoneKey() { return ~0UL - 1L; }
96 :
97 0 : static unsigned getHashValue(const unsigned long& Val) {
98 226299685 : return (unsigned)(Val * 37UL);
99 : }
100 :
101 0 : static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
102 90649146 : return LHS == RHS;
103 : }
104 : };
105 :
106 : // Provide DenseMapInfo for unsigned long longs.
107 : template<> struct DenseMapInfo<unsigned long long> {
108 : static inline unsigned long long getEmptyKey() { return ~0ULL; }
109 : static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; }
110 :
111 : static unsigned getHashValue(const unsigned long long& Val) {
112 : return (unsigned)(Val * 37ULL);
113 : }
114 :
115 : static bool isEqual(const unsigned long long& LHS,
116 : const unsigned long long& RHS) {
117 : return LHS == RHS;
118 : }
119 : };
120 :
121 : // Provide DenseMapInfo for shorts.
122 : template <> struct DenseMapInfo<short> {
123 : static inline short getEmptyKey() { return 0x7FFF; }
124 : static inline short getTombstoneKey() { return -0x7FFF - 1; }
125 : static unsigned getHashValue(const short &Val) { return Val * 37U; }
126 : static bool isEqual(const short &LHS, const short &RHS) { return LHS == RHS; }
127 : };
128 :
129 : // Provide DenseMapInfo for ints.
130 : template<> struct DenseMapInfo<int> {
131 : static inline int getEmptyKey() { return 0x7fffffff; }
132 : static inline int getTombstoneKey() { return -0x7fffffff - 1; }
133 1870826 : static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); }
134 :
135 0 : static bool isEqual(const int& LHS, const int& RHS) {
136 388126 : return LHS == RHS;
137 : }
138 : };
139 :
140 : // Provide DenseMapInfo for longs.
141 : template<> struct DenseMapInfo<long> {
142 : static inline long getEmptyKey() {
143 : return (1UL << (sizeof(long) * 8 - 1)) - 1UL;
144 : }
145 :
146 : static inline long getTombstoneKey() { return getEmptyKey() - 1L; }
147 :
148 0 : static unsigned getHashValue(const long& Val) {
149 16004760 : return (unsigned)(Val * 37UL);
150 : }
151 :
152 0 : static bool isEqual(const long& LHS, const long& RHS) {
153 10226825 : return LHS == RHS;
154 : }
155 : };
156 :
157 : // Provide DenseMapInfo for long longs.
158 : template<> struct DenseMapInfo<long long> {
159 : static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; }
160 : static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; }
161 :
162 0 : static unsigned getHashValue(const long long& Val) {
163 1393974 : return (unsigned)(Val * 37ULL);
164 : }
165 :
166 0 : static bool isEqual(const long long& LHS,
167 : const long long& RHS) {
168 3428401 : return LHS == RHS;
169 : }
170 : };
171 :
172 : // Provide DenseMapInfo for all pairs whose members have info.
173 : template<typename T, typename U>
174 : struct DenseMapInfo<std::pair<T, U>> {
175 : using Pair = std::pair<T, U>;
176 : using FirstInfo = DenseMapInfo<T>;
177 : using SecondInfo = DenseMapInfo<U>;
178 :
179 : static inline Pair getEmptyKey() {
180 12570013 : return std::make_pair(FirstInfo::getEmptyKey(),
181 : SecondInfo::getEmptyKey());
182 : }
183 :
184 : static inline Pair getTombstoneKey() {
185 7506954 : return std::make_pair(FirstInfo::getTombstoneKey(),
186 : SecondInfo::getTombstoneKey());
187 : }
188 :
189 338438443 : static unsigned getHashValue(const Pair& PairVal) {
190 922579260 : uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32
191 587979440 : | (uint64_t)SecondInfo::getHashValue(PairVal.second);
192 338438443 : key += ~(key << 32);
193 338438443 : key ^= (key >> 22);
194 338438443 : key += ~(key << 13);
195 338438443 : key ^= (key >> 8);
196 338438443 : key += (key << 3);
197 338438443 : key ^= (key >> 15);
198 338438443 : key += ~(key << 27);
199 338438443 : key ^= (key >> 31);
200 338438443 : return (unsigned)key;
201 : }
202 30394394 :
203 91174855 : static bool isEqual(const Pair &LHS, const Pair &RHS) {
204 1079634262 : return FirstInfo::isEqual(LHS.first, RHS.first) &&
205 274107813 : SecondInfo::isEqual(LHS.second, RHS.second);
206 30394394 : }
207 30394394 : };
208 30394394 :
209 30394394 : // Provide DenseMapInfo for StringRefs.
210 30394394 : template <> struct DenseMapInfo<StringRef> {
211 30394394 : static inline StringRef getEmptyKey() {
212 30394394 : return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(0)),
213 30394394 : 0);
214 : }
215 173168190 :
216 433155108 : static inline StringRef getTombstoneKey() {
217 264317235 : return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(1)),
218 173168190 : 0);
219 173168190 : }
220 173168190 :
221 173168190 : static unsigned getHashValue(StringRef Val) {
222 173168190 : assert(Val.data() != getEmptyKey().data() && "Cannot hash the empty key!");
223 173168190 : assert(Val.data() != getTombstoneKey().data() &&
224 173168190 : "Cannot hash the tombstone key!");
225 180778843 : return (unsigned)(hash_value(Val));
226 173168190 : }
227 :
228 29525060 : static bool isEqual(StringRef LHS, StringRef RHS) {
229 377665564 : if (RHS.data() == getEmptyKey().data())
230 295596230 : return LHS.data() == getEmptyKey().data();
231 379099635 : if (RHS.data() == getTombstoneKey().data())
232 4845034 : return LHS.data() == getTombstoneKey().data();
233 2425096 : return LHS == RHS;
234 2425096 : }
235 2425096 : };
236 2425096 :
237 2425096 : // Provide DenseMapInfo for ArrayRefs.
238 2425096 : template <typename T> struct DenseMapInfo<ArrayRef<T>> {
239 2425096 : static inline ArrayRef<T> getEmptyKey() {
240 : return ArrayRef<T>(reinterpret_cast<const T *>(~static_cast<uintptr_t>(0)),
241 999294 : size_t(0));
242 2997882 : }
243 185309255 :
244 101510742 : static inline ArrayRef<T> getTombstoneKey() {
245 999294 : return ArrayRef<T>(reinterpret_cast<const T *>(~static_cast<uintptr_t>(1)),
246 999294 : size_t(0));
247 999294 : }
248 999294 :
249 999294 : static unsigned getHashValue(ArrayRef<T> Val) {
250 999294 : assert(Val.data() != getEmptyKey().data() && "Cannot hash the empty key!");
251 1008373 : assert(Val.data() != getTombstoneKey().data() &&
252 999294 : "Cannot hash the tombstone key!");
253 : return (unsigned)(hash_value(Val));
254 558344 : }
255 915748 :
256 7844745 : static bool isEqual(ArrayRef<T> LHS, ArrayRef<T> RHS) {
257 2584484 : if (RHS.data() == getEmptyKey().data())
258 180743 : return LHS.data() == getEmptyKey().data();
259 179350 : if (RHS.data() == getTombstoneKey().data())
260 178705 : return LHS.data() == getTombstoneKey().data();
261 178702 : return LHS == RHS;
262 179915 : }
263 179915 : };
264 179716 :
265 178901 : template <> struct DenseMapInfo<hash_code> {
266 0 : static inline hash_code getEmptyKey() { return hash_code(-1); }
267 137 : static inline hash_code getTombstoneKey() { return hash_code(-2); }
268 70 : static unsigned getHashValue(hash_code val) { return val; }
269 864504 : static bool isEqual(hash_code LHS, hash_code RHS) { return LHS == RHS; }
270 5091 : };
271 1987 :
272 1605 : } // end namespace llvm
273 382 :
274 302 : #endif // LLVM_ADT_DENSEMAPINFO_H
|
