LLVM API Documentation

DenseMapInfo.h

Go to the documentation of this file.
00001 //===- llvm/ADT/DenseMapInfo.h - Type traits for DenseMap -------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This file defines DenseMapInfo traits for DenseMap.
00011 //
00012 //===----------------------------------------------------------------------===//
00013 
00014 #ifndef LLVM_ADT_DENSEMAPINFO_H
00015 #define LLVM_ADT_DENSEMAPINFO_H
00016 
00017 #include "llvm/Support/PointerLikeTypeTraits.h"
00018 #include <utility>
00019 
00020 namespace llvm {
00021 
00022 template<typename T>
00023 struct DenseMapInfo {
00024   //static inline T getEmptyKey();
00025   //static inline T getTombstoneKey();
00026   //static unsigned getHashValue(const T &Val);
00027   //static bool isEqual(const T &LHS, const T &RHS);
00028   //static bool isPod()
00029 };
00030 
00031 // Provide DenseMapInfo for all pointers.
00032 template<typename T>
00033 struct DenseMapInfo<T*> {
00034   static inline T* getEmptyKey() {
00035     intptr_t Val = -1;
00036     Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
00037     return reinterpret_cast<T*>(Val);
00038   }
00039   static inline T* getTombstoneKey() {
00040     intptr_t Val = -2;
00041     Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
00042     return reinterpret_cast<T*>(Val);
00043   }
00044   static unsigned getHashValue(const T *PtrVal) {
00045     return (unsigned((uintptr_t)PtrVal) >> 4) ^
00046            (unsigned((uintptr_t)PtrVal) >> 9);
00047   }
00048   static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; }
00049   static bool isPod() { return true; }
00050 };
00051 
00052 // Provide DenseMapInfo for chars.
00053 template<> struct DenseMapInfo<char> {
00054   static inline char getEmptyKey() { return ~0; }
00055   static inline char getTombstoneKey() { return ~0 - 1; }
00056   static unsigned getHashValue(const char& Val) { return Val * 37; }
00057   static bool isPod() { return true; }
00058   static bool isEqual(const char &LHS, const char &RHS) {
00059     return LHS == RHS;
00060   }
00061 };
00062   
00063 // Provide DenseMapInfo for unsigned ints.
00064 template<> struct DenseMapInfo<unsigned> {
00065   static inline unsigned getEmptyKey() { return ~0; }
00066   static inline unsigned getTombstoneKey() { return ~0 - 1; }
00067   static unsigned getHashValue(const unsigned& Val) { return Val * 37; }
00068   static bool isPod() { return true; }
00069   static bool isEqual(const unsigned& LHS, const unsigned& RHS) {
00070   return LHS == RHS;
00071   }
00072 };
00073 
00074 // Provide DenseMapInfo for unsigned longs.
00075 template<> struct DenseMapInfo<unsigned long> {
00076   static inline unsigned long getEmptyKey() { return ~0L; }
00077   static inline unsigned long getTombstoneKey() { return ~0L - 1L; }
00078   static unsigned getHashValue(const unsigned long& Val) {
00079     return (unsigned)(Val * 37L);
00080   }
00081   static bool isPod() { return true; }
00082   static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) {
00083   return LHS == RHS;
00084   }
00085 };
00086 
00087 // Provide DenseMapInfo for all pairs whose members have info.
00088 template<typename T, typename U>
00089 struct DenseMapInfo<std::pair<T, U> > {
00090   typedef std::pair<T, U> Pair;
00091   typedef DenseMapInfo<T> FirstInfo;
00092   typedef DenseMapInfo<U> SecondInfo;
00093 
00094   static inline Pair getEmptyKey() {
00095     return std::make_pair(FirstInfo::getEmptyKey(),
00096                           SecondInfo::getEmptyKey());
00097   }
00098   static inline Pair getTombstoneKey() {
00099     return std::make_pair(FirstInfo::getTombstoneKey(),
00100                             SecondInfo::getEmptyKey());
00101   }
00102   static unsigned getHashValue(const Pair& PairVal) {
00103     uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32
00104           | (uint64_t)SecondInfo::getHashValue(PairVal.second);
00105     key += ~(key << 32);
00106     key ^= (key >> 22);
00107     key += ~(key << 13);
00108     key ^= (key >> 8);
00109     key += (key << 3);
00110     key ^= (key >> 15);
00111     key += ~(key << 27);
00112     key ^= (key >> 31);
00113     return (unsigned)key;
00114   }
00115   static bool isEqual(const Pair& LHS, const Pair& RHS) { return LHS == RHS; }
00116   static bool isPod() { return FirstInfo::isPod() && SecondInfo::isPod(); }
00117 };
00118 
00119 } // end namespace llvm
00120 
00121 #endif