From fb3af88ba75898896714d49c608b8daa4f106636 Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Fri, 31 Jul 2009 18:18:19 +0000 Subject: [PATCH] Split DenseMapInfo into a separate header file, so that it can be included separately. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@77693 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/DenseMap.h | 98 +------------------------- include/llvm/ADT/DenseMapInfo.h | 121 ++++++++++++++++++++++++++++++++ 2 files changed, 122 insertions(+), 97 deletions(-) create mode 100644 include/llvm/ADT/DenseMapInfo.h diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index c8a90eb3098..79672f996d2 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -16,6 +16,7 @@ #include "llvm/Support/PointerLikeTypeTraits.h" #include "llvm/Support/MathExtras.h" +#include "llvm/ADT/DenseMapInfo.h" #include #include #include @@ -23,103 +24,6 @@ namespace llvm { -template -struct DenseMapInfo { - //static inline T getEmptyKey(); - //static inline T getTombstoneKey(); - //static unsigned getHashValue(const T &Val); - //static bool isEqual(const T &LHS, const T &RHS); - //static bool isPod() -}; - -// Provide DenseMapInfo for all pointers. -template -struct DenseMapInfo { - static inline T* getEmptyKey() { - intptr_t Val = -1; - Val <<= PointerLikeTypeTraits::NumLowBitsAvailable; - return reinterpret_cast(Val); - } - static inline T* getTombstoneKey() { - intptr_t Val = -2; - Val <<= PointerLikeTypeTraits::NumLowBitsAvailable; - return reinterpret_cast(Val); - } - static unsigned getHashValue(const T *PtrVal) { - return (unsigned((uintptr_t)PtrVal) >> 4) ^ - (unsigned((uintptr_t)PtrVal) >> 9); - } - static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } - static bool isPod() { return true; } -}; - -// Provide DenseMapInfo for chars. -template<> struct DenseMapInfo { - static inline char getEmptyKey() { return ~0; } - static inline char getTombstoneKey() { return ~0 - 1; } - static unsigned getHashValue(const char& Val) { return Val * 37; } - static bool isPod() { return true; } - static bool isEqual(const char &LHS, const char &RHS) { - return LHS == RHS; - } -}; - -// Provide DenseMapInfo for unsigned ints. -template<> struct DenseMapInfo { - static inline unsigned getEmptyKey() { return ~0; } - static inline unsigned getTombstoneKey() { return ~0 - 1; } - static unsigned getHashValue(const unsigned& Val) { return Val * 37; } - static bool isPod() { return true; } - static bool isEqual(const unsigned& LHS, const unsigned& RHS) { - return LHS == RHS; - } -}; - -// Provide DenseMapInfo for unsigned longs. -template<> struct DenseMapInfo { - static inline unsigned long getEmptyKey() { return ~0L; } - static inline unsigned long getTombstoneKey() { return ~0L - 1L; } - static unsigned getHashValue(const unsigned long& Val) { - return (unsigned)(Val * 37L); - } - static bool isPod() { return true; } - static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) { - return LHS == RHS; - } -}; - -// Provide DenseMapInfo for all pairs whose members have info. -template -struct DenseMapInfo > { - typedef std::pair Pair; - typedef DenseMapInfo FirstInfo; - typedef DenseMapInfo SecondInfo; - - static inline Pair getEmptyKey() { - return std::make_pair(FirstInfo::getEmptyKey(), - SecondInfo::getEmptyKey()); - } - static inline Pair getTombstoneKey() { - return std::make_pair(FirstInfo::getTombstoneKey(), - SecondInfo::getEmptyKey()); - } - static unsigned getHashValue(const Pair& PairVal) { - uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32 - | (uint64_t)SecondInfo::getHashValue(PairVal.second); - key += ~(key << 32); - key ^= (key >> 22); - key += ~(key << 13); - key ^= (key >> 8); - key += (key << 3); - key ^= (key >> 15); - key += ~(key << 27); - key ^= (key >> 31); - return (unsigned)key; - } - static bool isEqual(const Pair& LHS, const Pair& RHS) { return LHS == RHS; } - static bool isPod() { return FirstInfo::isPod() && SecondInfo::isPod(); } -}; - template, typename ValueInfoT = DenseMapInfo > diff --git a/include/llvm/ADT/DenseMapInfo.h b/include/llvm/ADT/DenseMapInfo.h new file mode 100644 index 00000000000..a895074220d --- /dev/null +++ b/include/llvm/ADT/DenseMapInfo.h @@ -0,0 +1,121 @@ +//===- llvm/ADT/DenseMapInfo.h - Type traits for DenseMap -------*- C++ -*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This file defines DenseMapInfo traits for DenseMap. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ADT_DENSEMAPINFO_H +#define LLVM_ADT_DENSEMAPINFO_H + +#include "llvm/Support/PointerLikeTypeTraits.h" +#include + +namespace llvm { + +template +struct DenseMapInfo { + //static inline T getEmptyKey(); + //static inline T getTombstoneKey(); + //static unsigned getHashValue(const T &Val); + //static bool isEqual(const T &LHS, const T &RHS); + //static bool isPod() +}; + +// Provide DenseMapInfo for all pointers. +template +struct DenseMapInfo { + static inline T* getEmptyKey() { + intptr_t Val = -1; + Val <<= PointerLikeTypeTraits::NumLowBitsAvailable; + return reinterpret_cast(Val); + } + static inline T* getTombstoneKey() { + intptr_t Val = -2; + Val <<= PointerLikeTypeTraits::NumLowBitsAvailable; + return reinterpret_cast(Val); + } + static unsigned getHashValue(const T *PtrVal) { + return (unsigned((uintptr_t)PtrVal) >> 4) ^ + (unsigned((uintptr_t)PtrVal) >> 9); + } + static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } + static bool isPod() { return true; } +}; + +// Provide DenseMapInfo for chars. +template<> struct DenseMapInfo { + static inline char getEmptyKey() { return ~0; } + static inline char getTombstoneKey() { return ~0 - 1; } + static unsigned getHashValue(const char& Val) { return Val * 37; } + static bool isPod() { return true; } + static bool isEqual(const char &LHS, const char &RHS) { + return LHS == RHS; + } +}; + +// Provide DenseMapInfo for unsigned ints. +template<> struct DenseMapInfo { + static inline unsigned getEmptyKey() { return ~0; } + static inline unsigned getTombstoneKey() { return ~0 - 1; } + static unsigned getHashValue(const unsigned& Val) { return Val * 37; } + static bool isPod() { return true; } + static bool isEqual(const unsigned& LHS, const unsigned& RHS) { + return LHS == RHS; + } +}; + +// Provide DenseMapInfo for unsigned longs. +template<> struct DenseMapInfo { + static inline unsigned long getEmptyKey() { return ~0L; } + static inline unsigned long getTombstoneKey() { return ~0L - 1L; } + static unsigned getHashValue(const unsigned long& Val) { + return (unsigned)(Val * 37L); + } + static bool isPod() { return true; } + static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) { + return LHS == RHS; + } +}; + +// Provide DenseMapInfo for all pairs whose members have info. +template +struct DenseMapInfo > { + typedef std::pair Pair; + typedef DenseMapInfo FirstInfo; + typedef DenseMapInfo SecondInfo; + + static inline Pair getEmptyKey() { + return std::make_pair(FirstInfo::getEmptyKey(), + SecondInfo::getEmptyKey()); + } + static inline Pair getTombstoneKey() { + return std::make_pair(FirstInfo::getTombstoneKey(), + SecondInfo::getEmptyKey()); + } + static unsigned getHashValue(const Pair& PairVal) { + uint64_t key = (uint64_t)FirstInfo::getHashValue(PairVal.first) << 32 + | (uint64_t)SecondInfo::getHashValue(PairVal.second); + key += ~(key << 32); + key ^= (key >> 22); + key += ~(key << 13); + key ^= (key >> 8); + key += (key << 3); + key ^= (key >> 15); + key += ~(key << 27); + key ^= (key >> 31); + return (unsigned)key; + } + static bool isEqual(const Pair& LHS, const Pair& RHS) { return LHS == RHS; } + static bool isPod() { return FirstInfo::isPod() && SecondInfo::isPod(); } +}; + +} // end namespace llvm + +#endif -- 2.34.1