X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FDenseMap.h;h=e18be8963d48bda4032b4425b5a41762e062754b;hb=d6a2aab53e3c4fcd53399cfa6f66d62913e53663;hp=4b815f697833e656e1375a0a9f20787a1c0e769b;hpb=b6bbe6320b4a60b7399eea08426aec834701d514;p=oota-llvm.git diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index 4b815f69783..e18be8963d4 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -14,13 +14,14 @@ #ifndef LLVM_ADT_DENSEMAP_H #define LLVM_ADT_DENSEMAP_H -#include "llvm/Support/DataTypes.h" +#include "llvm/Support/PointerLikeTypeTraits.h" #include "llvm/Support/MathExtras.h" #include #include +#include namespace llvm { - + template struct DenseMapInfo { //static inline T getEmptyKey(); @@ -33,23 +34,55 @@ struct DenseMapInfo { // Provide DenseMapInfo for all pointers. template struct DenseMapInfo { - static inline T* getEmptyKey() { return reinterpret_cast(-1); } - static inline T* getTombstoneKey() { return reinterpret_cast(-2); } + 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) ^ + 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 uint32_t getEmptyKey() { return ~0; } - static inline uint32_t getTombstoneKey() { return ~0 - 1; } - static unsigned getHashValue(const uint32_t& Val) { return Val * 37; } +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 uint32_t& LHS, const uint32_t& RHS) { + 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; } }; @@ -61,12 +94,12 @@ struct DenseMapInfo > { typedef DenseMapInfo FirstInfo; typedef DenseMapInfo SecondInfo; - static inline Pair getEmptyKey() { - return std::make_pair(FirstInfo::getEmptyKey(), - SecondInfo::getEmptyKey()); + static inline Pair getEmptyKey() { + return std::make_pair(FirstInfo::getEmptyKey(), + SecondInfo::getEmptyKey()); } - static inline Pair getTombstoneKey() { - return std::make_pair(FirstInfo::getTombstoneKey(), + static inline Pair getTombstoneKey() { + return std::make_pair(FirstInfo::getTombstoneKey(), SecondInfo::getEmptyKey()); } static unsigned getHashValue(const Pair& PairVal) { @@ -86,7 +119,7 @@ struct DenseMapInfo > { static bool isPod() { return FirstInfo::isPod() && SecondInfo::isPod(); } }; -template, typename ValueInfoT = DenseMapInfo > class DenseMapIterator; @@ -102,23 +135,23 @@ class DenseMap { typedef std::pair BucketT; unsigned NumBuckets; BucketT *Buckets; - + unsigned NumEntries; unsigned NumTombstones; public: typedef KeyT key_type; typedef ValueT mapped_type; typedef BucketT value_type; - + DenseMap(const DenseMap& other) { NumBuckets = 0; CopyFrom(other); } - + explicit DenseMap(unsigned NumInitBuckets = 64) { init(NumInitBuckets); } - + ~DenseMap() { const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { @@ -129,7 +162,7 @@ public: } operator delete(Buckets); } - + typedef DenseMapIterator iterator; typedef DenseMapConstIterator const_iterator; inline iterator begin() { @@ -144,13 +177,13 @@ public: inline const_iterator end() const { return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets); } - + bool empty() const { return NumEntries == 0; } unsigned size() const { return NumEntries; } /// Grow the densemap so that it has at least Size buckets. Does not shrink void resize(size_t Size) { grow(Size); } - + void clear() { // If the capacity of the array is huge, and the # elements used is small, // shrink the array. @@ -158,7 +191,7 @@ public: shrink_and_clear(); return; } - + const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { if (!KeyInfoT::isEqual(P->first, EmptyKey)) { @@ -178,7 +211,7 @@ public: BucketT *TheBucket; return LookupBucketFor(Val, TheBucket); } - + iterator find(const KeyT &Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) @@ -191,7 +224,7 @@ public: return const_iterator(TheBucket, Buckets+NumBuckets); return end(); } - + /// lookup - Return the entry for the specified key, or a default /// constructed value if no such entry exists. ValueT lookup(const KeyT &Val) const { @@ -206,13 +239,13 @@ public: if (LookupBucketFor(KV.first, TheBucket)) return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), false); // Already in map. - + // Otherwise, insert the new element. TheBucket = InsertIntoBucket(KV.first, KV.second, TheBucket); return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), true); } - + /// insert - Range insertion of pairs. template void insert(InputIt I, InputIt E) { @@ -220,7 +253,7 @@ public: insert(*I); } - + bool erase(const KeyT &Val) { BucketT *TheBucket; if (!LookupBucketFor(Val, TheBucket)) @@ -245,19 +278,31 @@ public: BucketT *TheBucket; if (LookupBucketFor(Key, TheBucket)) return *TheBucket; - + return *InsertIntoBucket(Key, ValueT(), TheBucket); } - + ValueT &operator[](const KeyT &Key) { return FindAndConstruct(Key).second; } - + DenseMap& operator=(const DenseMap& other) { CopyFrom(other); return *this; } - + + /// isPointerIntoBucketsArray - Return true if the specified pointer points + /// somewhere into the DenseMap's array of buckets (i.e. either to a key or + /// value in the DenseMap). + bool isPointerIntoBucketsArray(const void *Ptr) const { + return Ptr >= Buckets && Ptr < Buckets+NumBuckets; + } + + /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets + /// array. In conjunction with the previous method, this can be used to + /// determine whether an insertion caused the DenseMap to reallocate. + const void *getPointerIntoBucketsArray() const { return Buckets; } + private: void CopyFrom(const DenseMap& other) { if (NumBuckets != 0 && (!KeyInfoT::isPod() || !ValueInfoT::isPod())) { @@ -269,15 +314,15 @@ private: P->first.~KeyT(); } } - + NumEntries = other.NumEntries; NumTombstones = other.NumTombstones; - + if (NumBuckets) operator delete(Buckets); Buckets = static_cast(operator new(sizeof(BucketT) * other.NumBuckets)); - + if (KeyInfoT::isPod() && ValueInfoT::isPod()) memcpy(Buckets, other.Buckets, other.NumBuckets * sizeof(BucketT)); else @@ -289,7 +334,7 @@ private: } NumBuckets = other.NumBuckets; } - + BucketT *InsertIntoBucket(const KeyT &Key, const ValueT &Value, BucketT *TheBucket) { // If the load of the hash table is more than 3/4, or if fewer than 1/8 of @@ -301,17 +346,17 @@ private: // probe almost the entire table until it found the empty bucket. If the // table completely filled with tombstones, no lookup would ever succeed, // causing infinite loops in lookup. + ++NumEntries; if (NumEntries*4 >= NumBuckets*3 || - NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) { + NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) { this->grow(NumBuckets * 2); LookupBucketFor(Key, TheBucket); } - ++NumEntries; - + // If we are writing over a tombstone, remember this. if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) --NumTombstones; - + TheBucket->first = Key; new (&TheBucket->second) ValueT(Value); return TheBucket; @@ -326,7 +371,7 @@ private: static const KeyT getTombstoneKey() { return KeyInfoT::getTombstoneKey(); } - + /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in /// FoundBucket. If the bucket contains the key and a value, this returns /// true, otherwise it returns a bucket with an empty marker or tombstone and @@ -335,7 +380,7 @@ private: unsigned BucketNo = getHashValue(Val); unsigned ProbeAmt = 1; BucketT *BucketsPtr = Buckets; - + // FoundTombstone - Keep track of whether we find a tombstone while probing. BucketT *FoundTombstone = 0; const KeyT EmptyKey = getEmptyKey(); @@ -343,7 +388,7 @@ private: assert(!KeyInfoT::isEqual(Val, EmptyKey) && !KeyInfoT::isEqual(Val, TombstoneKey) && "Empty/Tombstone value shouldn't be inserted into map!"); - + while (1) { BucketT *ThisBucket = BucketsPtr + (BucketNo & (NumBuckets-1)); // Found Val's bucket? If so, return it. @@ -351,7 +396,7 @@ private: 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 (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) { @@ -361,12 +406,12 @@ private: FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket; return false; } - + // 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 (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone) FoundTombstone = ThisBucket; // Remember the first tombstone found. - + // Otherwise, it's a hash collision or a tombstone, continue quadratic // probing. BucketNo += ProbeAmt++; @@ -385,11 +430,11 @@ private: for (unsigned i = 0; i != InitBuckets; ++i) new (&Buckets[i].first) KeyT(EmptyKey); } - + void grow(unsigned AtLeast) { unsigned OldNumBuckets = NumBuckets; BucketT *OldBuckets = Buckets; - + // Double the number of buckets. while (NumBuckets <= AtLeast) NumBuckets <<= 1; @@ -413,21 +458,21 @@ private: assert(!FoundVal && "Key already in new map?"); DestBucket->first = B->first; new (&DestBucket->second) ValueT(B->second); - + // Free the value. B->second.~ValueT(); } B->first.~KeyT(); } - + // Free the old table. operator delete(OldBuckets); } - + void shrink_and_clear() { unsigned OldNumBuckets = NumBuckets; BucketT *OldBuckets = Buckets; - + // Reduce the number of buckets. NumBuckets = NumEntries > 32 ? 1 << (Log2_32_Ceil(NumEntries) + 1) : 64; @@ -449,10 +494,10 @@ private: } B->first.~KeyT(); } - + // Free the old table. operator delete(OldBuckets); - + NumEntries = 0; } }; @@ -468,21 +513,21 @@ public: DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) { AdvancePastEmptyBuckets(); } - + std::pair &operator*() const { return *const_cast(Ptr); } std::pair *operator->() const { return const_cast(Ptr); } - + bool operator==(const DenseMapIterator &RHS) const { return Ptr == RHS.Ptr; } bool operator!=(const DenseMapIterator &RHS) const { return Ptr != RHS.Ptr; } - + inline DenseMapIterator& operator++() { // Preincrement ++Ptr; AdvancePastEmptyBuckets(); @@ -491,13 +536,13 @@ public: DenseMapIterator operator++(int) { // Postincrement DenseMapIterator tmp = *this; ++*this; return tmp; } - + private: void AdvancePastEmptyBuckets() { const KeyT Empty = KeyInfoT::getEmptyKey(); const KeyT Tombstone = KeyInfoT::getTombstoneKey(); - while (Ptr != End && + while (Ptr != End && (KeyInfoT::isEqual(Ptr->first, Empty) || KeyInfoT::isEqual(Ptr->first, Tombstone))) ++Ptr;