LCOV - code coverage report
Current view: top level - include/llvm/ADT - DenseMapInfo.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 55 55 100.0 %
Date: 2017-09-14 15:23:50 Functions: 77 82 93.9 %
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  3610440877 :     uintptr_t Val = static_cast<uintptr_t>(-1);
      41  3610440877 :     Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
      42             :     return reinterpret_cast<T*>(Val);
      43             :   }
      44             : 
      45             :   static inline T* getTombstoneKey() {
      46  3096012751 :     uintptr_t Val = static_cast<uintptr_t>(-2);
      47  3096012751 :     Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
      48             :     return reinterpret_cast<T*>(Val);
      49             :   }
      50             : 
      51             :   static unsigned getHashValue(const T *PtrVal) {
      52  3531188536 :     return (unsigned((uintptr_t)PtrVal) >> 4) ^
      53  3531188536 :            (unsigned((uintptr_t)PtrVal) >> 9);
      54             :   }
      55             : 
      56  4598943566 :   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         360 :   static unsigned getHashValue(const unsigned short &Val) { return Val * 37U; }
      75             : 
      76             :   static bool isEqual(const unsigned short &LHS, const unsigned short &RHS) {
      77         699 :     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   517687077 :   static unsigned getHashValue(const unsigned& Val) { return Val * 37U; }
      86             : 
      87             :   static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
      88  1270845842 :     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    57311540 :     return (unsigned)(Val * 37UL);
      99             :   }
     100             : 
     101             :   static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
     102     7345914 :     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      431604 :   static unsigned getHashValue(const int& Val) { return (unsigned)(Val * 37U); }
     134             : 
     135             :   static bool isEqual(const int& LHS, const int& RHS) {
     136      373298 :     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    13122431 :     return (unsigned)(Val * 37UL);
     150             :   }
     151             : 
     152             :   static bool isEqual(const long& LHS, const long& RHS) {
     153    10009058 :     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     1070408 :     return (unsigned)(Val * 37ULL);
     164             :   }
     165             : 
     166             :   static bool isEqual(const long long& LHS,
     167             :                       const long long& RHS) {
     168     5781119 :     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    64387392 :     return std::make_pair(FirstInfo::getEmptyKey(),
     181    66694106 :                           SecondInfo::getEmptyKey());
     182             :   }
     183             : 
     184             :   static inline Pair getTombstoneKey() {
     185    43167237 :     return std::make_pair(FirstInfo::getTombstoneKey(),
     186    44524743 :                           SecondInfo::getTombstoneKey());
     187             :   }
     188             : 
     189    58981059 :   static unsigned getHashValue(const Pair& PairVal) {
     190   151420346 :     uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32
     191    92274553 :           | (uint64_t)SecondInfo::getHashValue(PairVal.second);
     192    58981059 :     key += ~(key << 32);
     193    58981059 :     key ^= (key >> 22);
     194    58981059 :     key += ~(key << 13);
     195    58981059 :     key ^= (key >> 8);
     196    58981059 :     key += (key << 3);
     197    58981059 :     key ^= (key >> 15);
     198    58981059 :     key += ~(key << 27);
     199    58981059 :     key ^= (key >> 31);
     200    58981059 :     return (unsigned)key;
     201             :   }
     202             : 
     203    50231975 :   static bool isEqual(const Pair &LHS, const Pair &RHS) {
     204   268698945 :     return FirstInfo::isEqual(LHS.first, RHS.first) &&
     205   128328963 :            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    33573565 :     return StringRef(reinterpret_cast<const char *>(~static_cast<uintptr_t>(0)),
     213             :                      0);
     214             :   }
     215             : 
     216             :   static inline StringRef getTombstoneKey() {
     217    10926278 :     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     5475556 :     return (unsigned)(hash_value(Val));
     226             :   }
     227             : 
     228    15803604 :   static bool isEqual(StringRef LHS, StringRef RHS) {
     229    31607208 :     if (RHS.data() == getEmptyKey().data())
     230    23719712 :       return LHS.data() == getEmptyKey().data();
     231     7887496 :     if (RHS.data() == getTombstoneKey().data())
     232     4543096 :       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       10454 :                        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         323 :                        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          86 :     return (unsigned)(hash_value(Val));
     254             :   }
     255             : 
     256        5114 :   static bool isEqual(ArrayRef<T> LHS, ArrayRef<T> RHS) {
     257       10228 :     if (RHS.data() == getEmptyKey().data())
     258       10056 :       return LHS.data() == getEmptyKey().data();
     259         172 :     if (RHS.data() == getTombstoneKey().data())
     260         152 :       return LHS.data() == getTombstoneKey().data();
     261          10 :     return LHS == RHS;
     262             :   }
     263             : };
     264             : 
     265             : } // end namespace llvm
     266             : 
     267             : #endif // LLVM_ADT_DENSEMAPINFO_H

Generated by: LCOV version 1.13