Home | History | Annotate | Download | only in ADT 
      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     return (unsigned((uintptr_t)PtrVal) >> 4) ^
     53            (unsigned((uintptr_t)PtrVal) >> 9);
     54   }
     55 
     56   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   static unsigned getHashValue(const char& Val) { return Val * 37U; }
     64 
     65   static bool isEqual(const char &LHS, const char &RHS) {
     66     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   static unsigned getHashValue(const unsigned short &Val) { return Val * 37U; }
     75 
     76   static bool isEqual(const unsigned short &LHS, const unsigned short &RHS) {
     77     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   static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
     86 
     87   static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
     88     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   static unsigned getHashValue(const unsigned long& Val) {
     98     return (unsigned)(Val * 37UL);
     99   }
    100 
    101   static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
    102     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   static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); }
    134 
    135   static bool isEqual(const int& LHS, const int& RHS) {
    136     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   static unsigned getHashValue(const long& Val) {
    149     return (unsigned)(Val * 37UL);
    150   }
    151 
    152   static bool isEqual(const long& LHS, const long& RHS) {
    153     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   static unsigned getHashValue(const long long& Val) {
    163     return (unsigned)(Val * 37ULL);
    164   }
    165 
    166   static bool isEqual(const long long& LHS,
    167                       const long long& RHS) {
    168     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     return std::make_pair(FirstInfo::getEmptyKey(),
    181                           SecondInfo::getEmptyKey());
    182   }
    183 
    184   static inline Pair getTombstoneKey() {
    185     return std::make_pair(FirstInfo::getTombstoneKey(),
    186                           SecondInfo::getTombstoneKey());
    187   }
    188 
    189   static unsigned getHashValue(const Pair& PairVal) {
    190     uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32
    191           | (uint64_t)SecondInfo::getHashValue(PairVal.second);
    192     key += ~(key << 32);
    193     key ^= (key >> 22);
    194     key += ~(key << 13);
    195     key ^= (key >> 8);
    196     key += (key << 3);
    197     key ^= (key >> 15);
    198     key += ~(key << 27);
    199     key ^= (key >> 31);
    200     return (unsigned)key;
    201   }
    202 
    203   static bool isEqual(const Pair &LHS, const Pair &RHS) {
    204     return FirstInfo::isEqual(LHS.first, RHS.first) &&
    205            SecondInfo::isEqual(LHS.second, RHS.second);
    206   }
    207 };
    208 
    209 // Provide DenseMapInfo for StringRefs.
    210 template <> struct DenseMapInfo<StringRef> {
    211   static inline StringRef getEmptyKey() {
    212     return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(0)),
    213                      0);
    214   }
    215 
    216   static inline StringRef getTombstoneKey() {
    217     return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(1)),
    218                      0);
    219   }
    220 
    221   static unsigned getHashValue(StringRef Val) {
    222     assert(Val.data() != getEmptyKey().data() && "Cannot hash the empty key!");
    223     assert(Val.data() != getTombstoneKey().data() &&
    224            "Cannot hash the tombstone key!");
    225     return (unsigned)(hash_value(Val));
    226   }
    227 
    228   static bool isEqual(StringRef LHS, StringRef RHS) {
    229     if (RHS.data() == getEmptyKey().data())
    230       return LHS.data() == getEmptyKey().data();
    231     if (RHS.data() == getTombstoneKey().data())
    232       return LHS.data() == getTombstoneKey().data();
    233     return LHS == RHS;
    234   }
    235 };
    236 
    237 // Provide DenseMapInfo for ArrayRefs.
    238 template <typename T> struct DenseMapInfo<ArrayRef<T>> {
    239   static inline ArrayRef<T> getEmptyKey() {
    240     return ArrayRef<T>(reinterpret_cast<const T *>(~static_cast<uintptr_t>(0)),
    241                        size_t(0));
    242   }
    243 
    244   static inline ArrayRef<T> getTombstoneKey() {
    245     return ArrayRef<T>(reinterpret_cast<const T *>(~static_cast<uintptr_t>(1)),
    246                        size_t(0));
    247   }
    248 
    249   static unsigned getHashValue(ArrayRef<T> Val) {
    250     assert(Val.data() != getEmptyKey().data() && "Cannot hash the empty key!");
    251     assert(Val.data() != getTombstoneKey().data() &&
    252            "Cannot hash the tombstone key!");
    253     return (unsigned)(hash_value(Val));
    254   }
    255 
    256   static bool isEqual(ArrayRef<T> LHS, ArrayRef<T> RHS) {
    257     if (RHS.data() == getEmptyKey().data())
    258       return LHS.data() == getEmptyKey().data();
    259     if (RHS.data() == getTombstoneKey().data())
    260       return LHS.data() == getTombstoneKey().data();
    261     return LHS == RHS;
    262   }
    263 };
    264 
    265 } // end namespace llvm
    266 
    267 #endif // LLVM_ADT_DENSEMAPINFO_H
    268