]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
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/Support/PointerLikeTypeTraits.h" | |
18 | #include "llvm/Support/type_traits.h" | |
19 | ||
20 | namespace llvm { | |
21 | ||
22 | template<typename T> | |
23 | struct DenseMapInfo { | |
24 | //static inline T getEmptyKey(); | |
25 | //static inline T getTombstoneKey(); | |
26 | //static unsigned getHashValue(const T &Val); | |
27 | //static bool isEqual(const T &LHS, const T &RHS); | |
28 | }; | |
29 | ||
30 | // Provide DenseMapInfo for all pointers. | |
31 | template<typename T> | |
32 | struct DenseMapInfo<T*> { | |
33 | static inline T* getEmptyKey() { | |
34 | uintptr_t Val = static_cast<uintptr_t>(-1); | |
35 | Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; | |
36 | return reinterpret_cast<T*>(Val); | |
37 | } | |
38 | static inline T* getTombstoneKey() { | |
39 | uintptr_t Val = static_cast<uintptr_t>(-2); | |
40 | Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable; | |
41 | return reinterpret_cast<T*>(Val); | |
42 | } | |
43 | static unsigned getHashValue(const T *PtrVal) { | |
44 | return (unsigned((uintptr_t)PtrVal) >> 4) ^ | |
45 | (unsigned((uintptr_t)PtrVal) >> 9); | |
46 | } | |
47 | static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } | |
48 | }; | |
49 | ||
50 | // Provide DenseMapInfo for chars. | |
51 | template<> struct DenseMapInfo<char> { | |
52 | static inline char getEmptyKey() { return ~0; } | |
53 | static inline char getTombstoneKey() { return ~0 - 1; } | |
54 | static unsigned getHashValue(const char& Val) { return Val * 37U; } | |
55 | static bool isEqual(const char &LHS, const char &RHS) { | |
56 | return LHS == RHS; | |
57 | } | |
58 | }; | |
59 | ||
60 | // Provide DenseMapInfo for unsigned ints. | |
61 | template<> struct DenseMapInfo<unsigned> { | |
62 | static inline unsigned getEmptyKey() { return ~0U; } | |
63 | static inline unsigned getTombstoneKey() { return ~0U - 1; } | |
64 | static unsigned getHashValue(const unsigned& Val) { return Val * 37U; } | |
65 | static bool isEqual(const unsigned& LHS, const unsigned& RHS) { | |
66 | return LHS == RHS; | |
67 | } | |
68 | }; | |
69 | ||
70 | // Provide DenseMapInfo for unsigned longs. | |
71 | template<> struct DenseMapInfo<unsigned long> { | |
72 | static inline unsigned long getEmptyKey() { return ~0UL; } | |
73 | static inline unsigned long getTombstoneKey() { return ~0UL - 1L; } | |
74 | static unsigned getHashValue(const unsigned long& Val) { | |
75 | return (unsigned)(Val * 37UL); | |
76 | } | |
77 | static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) { | |
78 | return LHS == RHS; | |
79 | } | |
80 | }; | |
81 | ||
82 | // Provide DenseMapInfo for unsigned long longs. | |
83 | template<> struct DenseMapInfo<unsigned long long> { | |
84 | static inline unsigned long long getEmptyKey() { return ~0ULL; } | |
85 | static inline unsigned long long getTombstoneKey() { return ~0ULL - 1ULL; } | |
86 | static unsigned getHashValue(const unsigned long long& Val) { | |
87 | return (unsigned)(Val * 37ULL); | |
88 | } | |
89 | static bool isEqual(const unsigned long long& LHS, | |
90 | const unsigned long long& RHS) { | |
91 | return LHS == RHS; | |
92 | } | |
93 | }; | |
94 | ||
95 | // Provide DenseMapInfo for ints. | |
96 | template<> struct DenseMapInfo<int> { | |
97 | static inline int getEmptyKey() { return 0x7fffffff; } | |
98 | static inline int getTombstoneKey() { return -0x7fffffff - 1; } | |
99 | static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); } | |
100 | static bool isEqual(const int& LHS, const int& RHS) { | |
101 | return LHS == RHS; | |
102 | } | |
103 | }; | |
104 | ||
105 | // Provide DenseMapInfo for longs. | |
106 | template<> struct DenseMapInfo<long> { | |
107 | static inline long getEmptyKey() { | |
108 | return (1UL << (sizeof(long) * 8 - 1)) - 1UL; | |
109 | } | |
110 | static inline long getTombstoneKey() { return getEmptyKey() - 1L; } | |
111 | static unsigned getHashValue(const long& Val) { | |
112 | return (unsigned)(Val * 37UL); | |
113 | } | |
114 | static bool isEqual(const long& LHS, const long& RHS) { | |
115 | return LHS == RHS; | |
116 | } | |
117 | }; | |
118 | ||
119 | // Provide DenseMapInfo for long longs. | |
120 | template<> struct DenseMapInfo<long long> { | |
121 | static inline long long getEmptyKey() { return 0x7fffffffffffffffLL; } | |
122 | static inline long long getTombstoneKey() { return -0x7fffffffffffffffLL-1; } | |
123 | static unsigned getHashValue(const long long& Val) { | |
124 | return (unsigned)(Val * 37ULL); | |
125 | } | |
126 | static bool isEqual(const long long& LHS, | |
127 | const long long& RHS) { | |
128 | return LHS == RHS; | |
129 | } | |
130 | }; | |
131 | ||
132 | // Provide DenseMapInfo for all pairs whose members have info. | |
133 | template<typename T, typename U> | |
134 | struct DenseMapInfo<std::pair<T, U> > { | |
135 | typedef std::pair<T, U> Pair; | |
136 | typedef DenseMapInfo<T> FirstInfo; | |
137 | typedef DenseMapInfo<U> SecondInfo; | |
138 | ||
139 | static inline Pair getEmptyKey() { | |
140 | return std::make_pair(FirstInfo::getEmptyKey(), | |
141 | SecondInfo::getEmptyKey()); | |
142 | } | |
143 | static inline Pair getTombstoneKey() { | |
144 | return std::make_pair(FirstInfo::getTombstoneKey(), | |
145 | SecondInfo::getTombstoneKey()); | |
146 | } | |
147 | static unsigned getHashValue(const Pair& PairVal) { | |
148 | uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32 | |
149 | | (uint64_t)SecondInfo::getHashValue(PairVal.second); | |
150 | key += ~(key << 32); | |
151 | key ^= (key >> 22); | |
152 | key += ~(key << 13); | |
153 | key ^= (key >> 8); | |
154 | key += (key << 3); | |
155 | key ^= (key >> 15); | |
156 | key += ~(key << 27); | |
157 | key ^= (key >> 31); | |
158 | return (unsigned)key; | |
159 | } | |
160 | static bool isEqual(const Pair &LHS, const Pair &RHS) { | |
161 | return FirstInfo::isEqual(LHS.first, RHS.first) && | |
162 | SecondInfo::isEqual(LHS.second, RHS.second); | |
163 | } | |
164 | }; | |
165 | ||
166 | } // end namespace llvm | |
167 | ||
168 | #endif |