X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FDenseMap.h;h=82cf5229e8b3bed7b99ed250bbcc53b2aa258efb;hb=29ce95511f905df3a63e3b953a4a0179ead46865;hp=7e8b8c5e02f2300ceff405f05d9614648577cba6;hpb=a76b1febd4fd258e8054395adedcbd477668d956;p=oota-llvm.git diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index 7e8b8c5e02f..82cf5229e8b 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -15,6 +15,7 @@ #define LLVM_ADT_DENSEMAP_H #include "llvm/Support/DataTypes.h" +#include "llvm/Support/MathExtras.h" #include #include @@ -31,24 +32,38 @@ struct DenseMapKeyInfo { // Provide DenseMapKeyInfo for all pointers. template struct DenseMapKeyInfo { - static inline T* getEmptyKey() { return (T*)-1; } - static inline T* getTombstoneKey() { return (T*)-2; } + static inline T* getEmptyKey() { return reinterpret_cast(-1); } + static inline T* getTombstoneKey() { return reinterpret_cast(-2); } 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 isPod() { return true; } }; +template +struct DenseMapValueInfo { + //static bool isPod() +}; + +// Provide DenseMapValueInfo for all pointers. +template +struct DenseMapValueInfo { + static bool isPod() { return true; } +}; + template > + typename KeyInfoT = DenseMapKeyInfo, + typename ValueInfoT = DenseMapValueInfo > class DenseMapIterator; template > + typename KeyInfoT = DenseMapKeyInfo, + typename ValueInfoT = DenseMapValueInfo > class DenseMapConstIterator; template > + typename KeyInfoT = DenseMapKeyInfo, + typename ValueInfoT = DenseMapValueInfo > class DenseMap { typedef std::pair BucketT; unsigned NumBuckets; @@ -56,11 +71,16 @@ class DenseMap { unsigned NumEntries; unsigned NumTombstones; - DenseMap(const DenseMap &); // not implemented. public: + 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) { @@ -68,7 +88,7 @@ public: P->second.~ValueT(); P->first.~KeyT(); } - delete[] (char*)Buckets; + delete[] reinterpret_cast(Buckets); } typedef DenseMapIterator iterator; @@ -90,30 +110,45 @@ public: unsigned size() const { return NumEntries; } void clear() { + // If the capacity of the array is huge, and the # elements used is small, + // shrink the array. + if (NumEntries * 4 < NumBuckets && NumBuckets > 64) { + shrink_and_clear(); + return; + } + const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey(); for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) { - if (P->first != EmptyKey && P->first != TombstoneKey) { + if (P->first != EmptyKey) { + if (P->first != TombstoneKey) { + P->second.~ValueT(); + --NumEntries; + } P->first = EmptyKey; - P->second.~ValueT(); - --NumEntries; } } assert(NumEntries == 0 && "Node count imbalance!"); NumTombstones = 0; } - + /// count - Return true if the specified key is in the map. bool count(const KeyT &Val) const { BucketT *TheBucket; return LookupBucketFor(Val, TheBucket); } - iterator find(const KeyT &Val) const { + iterator find(const KeyT &Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) return iterator(TheBucket, Buckets+NumBuckets); return end(); } + const_iterator find(const KeyT &Val) const { + BucketT *TheBucket; + if (LookupBucketFor(Val, TheBucket)) + return const_iterator(TheBucket, Buckets+NumBuckets); + return end(); + } bool insert(const std::pair &KV) { BucketT *TheBucket; @@ -153,7 +188,42 @@ public: return InsertIntoBucket(Key, ValueT(), TheBucket)->second; } + DenseMap& operator=(const DenseMap& other) { + CopyFrom(other); + return *this; + } + 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) + 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]); + + 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].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 @@ -242,7 +312,7 @@ private: NumBuckets = InitBuckets; assert(InitBuckets && (InitBuckets & InitBuckets-1) == 0 && "# initial buckets must be a power of two!"); - Buckets = (BucketT*)new char[sizeof(BucketT)*InitBuckets]; + Buckets = reinterpret_cast(new char[sizeof(BucketT)*InitBuckets]); // Initialize all the keys to EmptyKey. const KeyT EmptyKey = getEmptyKey(); for (unsigned i = 0; i != InitBuckets; ++i) @@ -256,7 +326,7 @@ private: // Double the number of buckets. NumBuckets <<= 1; NumTombstones = 0; - Buckets = (BucketT*)new char[sizeof(BucketT)*NumBuckets]; + Buckets = reinterpret_cast(new char[sizeof(BucketT)*NumBuckets]); // Initialize all the keys to EmptyKey. const KeyT EmptyKey = getEmptyKey(); @@ -282,11 +352,42 @@ private: } // Free the old table. - delete[] (char*)OldBuckets; + delete[] reinterpret_cast(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]); + + // Initialize all the keys to EmptyKey. + const KeyT EmptyKey = getEmptyKey(); + for (unsigned i = 0, e = NumBuckets; i != e; ++i) + new (&Buckets[i].first) KeyT(EmptyKey); + + // 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) { + // Free the value. + B->second.~ValueT(); + } + B->first.~KeyT(); + } + + // Free the old table. + delete[] reinterpret_cast(OldBuckets); + + NumEntries = 0; } }; -template +template class DenseMapIterator { typedef std::pair BucketT; protected: @@ -329,12 +430,12 @@ private: } }; -template +template class DenseMapConstIterator : public DenseMapIterator { public: DenseMapConstIterator(const std::pair *Pos, const std::pair *E) - : DenseMapIterator(Pos, E) { + : DenseMapIterator(Pos, E) { } const std::pair &operator*() const { return *this->Ptr;