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