diff options
author | Chris Lattner <sabre@nondot.org> | 2007-09-17 18:34:04 +0000 |
---|---|---|
committer | Chris Lattner <sabre@nondot.org> | 2007-09-17 18:34:04 +0000 |
commit | 76c1b97e4020faace8c95a127f1eab66c278fb58 (patch) | |
tree | 9fbf93a4ca6637674eaffdef7af40539b80d9f4e /include/llvm | |
parent | 430817ba181071d20f5c7c3ec4dcd5d8b8e318f4 (diff) | |
download | external_llvm-76c1b97e4020faace8c95a127f1eab66c278fb58.zip external_llvm-76c1b97e4020faace8c95a127f1eab66c278fb58.tar.gz external_llvm-76c1b97e4020faace8c95a127f1eab66c278fb58.tar.bz2 |
Merge DenseMapKeyInfo & DenseMapValueInfo into DenseMapInfo
Add a new DenseMapInfo::isEqual method to allow clients to redefine
the equality predicate used when probing the hash table.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@42042 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'include/llvm')
-rw-r--r-- | include/llvm/ADT/DenseMap.h | 41 | ||||
-rw-r--r-- | include/llvm/CodeGen/SelectionDAGNodes.h | 7 |
2 files changed, 22 insertions, 26 deletions
diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index 82cf522..c291406 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -22,48 +22,39 @@ namespace llvm { template<typename T> -struct DenseMapKeyInfo { +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 DenseMapKeyInfo for all pointers. +// Provide DenseMapInfo for all pointers. template<typename T> -struct DenseMapKeyInfo<T*> { +struct DenseMapInfo<T*> { static inline T* getEmptyKey() { return reinterpret_cast<T*>(-1); } static inline T* getTombstoneKey() { return reinterpret_cast<T*>(-2); } static unsigned getHashValue(const T *PtrVal) { return (unsigned(uintptr_t(PtrVal)) >> 4) ^ (unsigned(uintptr_t(PtrVal)) >> 9); } - static bool isPod() { return true; } -}; - -template<typename T> -struct DenseMapValueInfo { - //static bool isPod() -}; - -// Provide DenseMapValueInfo for all pointers. -template<typename T> -struct DenseMapValueInfo<T*> { + static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } static bool isPod() { return true; } }; template<typename KeyT, typename ValueT, - typename KeyInfoT = DenseMapKeyInfo<KeyT>, - typename ValueInfoT = DenseMapValueInfo<ValueT> > + typename KeyInfoT = DenseMapInfo<KeyT>, + typename ValueInfoT = DenseMapInfo<ValueT> > class DenseMapIterator; template<typename KeyT, typename ValueT, - typename KeyInfoT = DenseMapKeyInfo<KeyT>, - typename ValueInfoT = DenseMapValueInfo<ValueT> > + typename KeyInfoT = DenseMapInfo<KeyT>, + typename ValueInfoT = DenseMapInfo<ValueT> > class DenseMapConstIterator; template<typename KeyT, typename ValueT, - typename KeyInfoT = DenseMapKeyInfo<KeyT>, - typename ValueInfoT = DenseMapValueInfo<ValueT> > + typename KeyInfoT = DenseMapInfo<KeyT>, + typename ValueInfoT = DenseMapInfo<ValueT> > class DenseMap { typedef std::pair<KeyT, ValueT> BucketT; unsigned NumBuckets; @@ -280,14 +271,14 @@ private: while (1) { BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1)); // Found Val's bucket? If so, return it. - if (ThisBucket->first == Val) { + if (KeyInfoT::isEqual(ThisBucket->first, Val)) { FoundBucket = ThisBucket; return true; } // If we found an empty bucket, the key doesn't exist in the set. // Insert it and return the default value. - if (ThisBucket->first == EmptyKey) { + if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { // If we've already seen a tombstone while probing, fill it in instead // of the empty bucket we eventually probed to. if (FoundTombstone) ThisBucket = FoundTombstone; @@ -297,7 +288,7 @@ private: // If this is a tombstone, remember it. If Val ends up not in the map, we // prefer to return it than something that would require more probing. - if (ThisBucket->first == TombstoneKey && !FoundTombstone) + if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) FoundTombstone = ThisBucket; // Remember the first tombstone found. // Otherwise, it's a hash collision or a tombstone, continue quadratic @@ -425,7 +416,9 @@ private: const KeyT Empty = KeyInfoT::getEmptyKey(); const KeyT Tombstone = KeyInfoT::getTombstoneKey(); - while (Ptr != End && (Ptr->first == Empty || Ptr->first == Tombstone)) + while (Ptr != End && + (KeyInfoT::isEqual(Ptr->first, Empty) || + KeyInfoT::isEqual(Ptr->first, Tombstone))) ++Ptr; } }; diff --git a/include/llvm/CodeGen/SelectionDAGNodes.h b/include/llvm/CodeGen/SelectionDAGNodes.h index 40a88eb..b3e217b 100644 --- a/include/llvm/CodeGen/SelectionDAGNodes.h +++ b/include/llvm/CodeGen/SelectionDAGNodes.h @@ -35,7 +35,7 @@ class GlobalValue; class MachineBasicBlock; class MachineConstantPoolValue; class SDNode; -template <typename T> struct DenseMapKeyInfo; +template <typename T> struct DenseMapInfo; template <typename T> struct simplify_type; template <typename T> struct ilist_traits; template<typename NodeTy, typename Traits> class iplist; @@ -773,13 +773,16 @@ public: }; -template<> struct DenseMapKeyInfo<SDOperand> { +template<> struct DenseMapInfo<SDOperand> { static inline SDOperand getEmptyKey() { return SDOperand((SDNode*)-1, -1U); } static inline SDOperand getTombstoneKey() { return SDOperand((SDNode*)-1, 0);} static unsigned getHashValue(const SDOperand &Val) { return (unsigned)((uintptr_t)Val.Val >> 4) ^ (unsigned)((uintptr_t)Val.Val >> 9) + Val.ResNo; } + static bool isEqual(const SDOperand &LHS, const SDOperand &RHS) { + return LHS == RHS; + } static bool isPod() { return true; } }; |