X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FDenseMap.h;h=e18be8963d48bda4032b4425b5a41762e062754b;hb=d6a2aab53e3c4fcd53399cfa6f66d62913e53663;hp=78d8f83cbb407b28257b233e2975f32e026e7aa2;hpb=d81ccc2806b2c8a498d16f1a547d0cc9c00d602d;p=oota-llvm.git diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index 78d8f83cbb4..e18be8963d4 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by Chris Lattner and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -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,17 +34,92 @@ 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) ^ - (unsigned(uintptr_t(PtrVal)) >> 9); + 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; } }; -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 > class DenseMapIterator; @@ -59,29 +135,34 @@ 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) { - if (P->first != EmptyKey && P->first != TombstoneKey) + if (!KeyInfoT::isEqual(P->first, EmptyKey) && + !KeyInfoT::isEqual(P->first, TombstoneKey)) P->second.~ValueT(); P->first.~KeyT(); } - delete[] reinterpret_cast(Buckets); + operator delete(Buckets); } - + typedef DenseMapIterator iterator; typedef DenseMapConstIterator const_iterator; inline iterator begin() { @@ -96,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. @@ -110,11 +191,11 @@ public: shrink_and_clear(); return; } - + const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { - if (P->first != EmptyKey) { - if (P->first != TombstoneKey) { + if (!KeyInfoT::isEqual(P->first, EmptyKey)) { + if (!KeyInfoT::isEqual(P->first, TombstoneKey)) { P->second.~ValueT(); --NumEntries; } @@ -130,7 +211,7 @@ public: BucketT *TheBucket; return LookupBucketFor(Val, TheBucket); } - + iterator find(const KeyT &Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) @@ -143,17 +224,36 @@ public: return const_iterator(TheBucket, Buckets+NumBuckets); return end(); } - - bool insert(const std::pair &KV) { + + /// lookup - Return the entry for the specified key, or a default + /// constructed value if no such entry exists. + ValueT lookup(const KeyT &Val) const { + BucketT *TheBucket; + if (LookupBucketFor(Val, TheBucket)) + return TheBucket->second; + return ValueT(); + } + + std::pair insert(const std::pair &KV) { BucketT *TheBucket; if (LookupBucketFor(KV.first, TheBucket)) - return false; // Already in map. - + return std::make_pair(iterator(TheBucket, Buckets+NumBuckets), + false); // Already in map. + // Otherwise, insert the new element. - InsertIntoBucket(KV.first, KV.second, TheBucket); - return true; + 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) { + for (; I != E; ++I) + insert(*I); + } + + bool erase(const KeyT &Val) { BucketT *TheBucket; if (!LookupBucketFor(Val, TheBucket)) @@ -173,51 +273,68 @@ public: ++NumTombstones; return true; } - - ValueT &operator[](const KeyT &Key) { + + value_type& FindAndConstruct(const KeyT &Key) { BucketT *TheBucket; if (LookupBucketFor(Key, TheBucket)) - return TheBucket->second; + return *TheBucket; - return InsertIntoBucket(Key, ValueT(), TheBucket)->second; + 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())) { const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { - if (P->first != EmptyKey && P->first != TombstoneKey) + if (!KeyInfoT::isEqual(P->first, EmptyKey) && + !KeyInfoT::isEqual(P->first, TombstoneKey)) P->second.~ValueT(); P->first.~KeyT(); } } - + NumEntries = other.NumEntries; NumTombstones = other.NumTombstones; - + if (NumBuckets) - delete[] reinterpret_cast(Buckets); - Buckets = reinterpret_cast(new char[sizeof(BucketT) * - other.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 for (size_t i = 0; i < other.NumBuckets; ++i) { - new (Buckets[i].first) KeyT(other.Buckets[i].first); - if (Buckets[i].first != getEmptyKey() && - Buckets[i].first != getTombstoneKey()) + new (&Buckets[i].first) KeyT(other.Buckets[i].first); + if (!KeyInfoT::isEqual(Buckets[i].first, getEmptyKey()) && + !KeyInfoT::isEqual(Buckets[i].first, getTombstoneKey())) new (&Buckets[i].second) ValueT(other.Buckets[i].second); } 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 @@ -229,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 (TheBucket->first != getEmptyKey()) + if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) --NumTombstones; - + TheBucket->first = Key; new (&TheBucket->second) ValueT(Value); return TheBucket; @@ -254,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 @@ -263,14 +380,15 @@ 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(); const KeyT TombstoneKey = getTombstoneKey(); - assert(Val != EmptyKey && Val != TombstoneKey && + 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. @@ -278,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)) { @@ -288,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++; @@ -304,24 +422,24 @@ private: NumEntries = 0; NumTombstones = 0; NumBuckets = InitBuckets; - assert(InitBuckets && (InitBuckets & InitBuckets-1) == 0 && + assert(InitBuckets && (InitBuckets & (InitBuckets-1)) == 0 && "# initial buckets must be a power of two!"); - Buckets = reinterpret_cast(new char[sizeof(BucketT)*InitBuckets]); + Buckets = static_cast(operator new(sizeof(BucketT)*InitBuckets)); // Initialize all the keys to EmptyKey. const KeyT EmptyKey = getEmptyKey(); 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; NumTombstones = 0; - Buckets = reinterpret_cast(new char[sizeof(BucketT)*NumBuckets]); + Buckets = static_cast(operator new(sizeof(BucketT)*NumBuckets)); // Initialize all the keys to EmptyKey. const KeyT EmptyKey = getEmptyKey(); @@ -331,7 +449,8 @@ private: // Insert all the old elements. const KeyT TombstoneKey = getTombstoneKey(); for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { - if (B->first != EmptyKey && B->first != TombstoneKey) { + if (!KeyInfoT::isEqual(B->first, EmptyKey) && + !KeyInfoT::isEqual(B->first, TombstoneKey)) { // Insert the key/value into the new table. BucketT *DestBucket; bool FoundVal = LookupBucketFor(B->first, DestBucket); @@ -339,26 +458,26 @@ 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. - delete[] reinterpret_cast(OldBuckets); + 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; NumTombstones = 0; - Buckets = reinterpret_cast(new char[sizeof(BucketT)*NumBuckets]); + Buckets = static_cast(operator new(sizeof(BucketT)*NumBuckets)); // Initialize all the keys to EmptyKey. const KeyT EmptyKey = getEmptyKey(); @@ -368,16 +487,17 @@ private: // Free the old buckets. const KeyT TombstoneKey = getTombstoneKey(); for (BucketT *B = OldBuckets, *E = OldBuckets+OldNumBuckets; B != E; ++B) { - if (B->first != EmptyKey && B->first != TombstoneKey) { + if (!KeyInfoT::isEqual(B->first, EmptyKey) && + !KeyInfoT::isEqual(B->first, TombstoneKey)) { // Free the value. B->second.~ValueT(); } B->first.~KeyT(); } - + // Free the old table. - delete[] reinterpret_cast(OldBuckets); - + operator delete(OldBuckets); + NumEntries = 0; } }; @@ -388,24 +508,26 @@ class DenseMapIterator { protected: const BucketT *Ptr, *End; public: + DenseMapIterator(void) : Ptr(0), End(0) {} + 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(); @@ -414,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; @@ -430,6 +552,7 @@ private: template class DenseMapConstIterator : public DenseMapIterator { public: + DenseMapConstIterator(void) : DenseMapIterator() {} DenseMapConstIterator(const std::pair *Pos, const std::pair *E) : DenseMapIterator(Pos, E) {