LCOV - code coverage report
Current view: top level - include/llvm/ADT - DenseMapInfo.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 103 115 89.6 %
Date: 2018-10-20 13:21:21 Functions: 97 147 66.0 %
Legend: Lines: hit not hit

          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

Generated by: LCOV version 1.13