X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FDenseMap.h;h=9a66c8b6c1171c35d7e2b8c4768aeba2a3d1c01f;hb=6de603071879bdc5d7d663826354c24a9d176469;hp=fe912404cd9a43cdc4bda366589ea02b426ec6b4;hpb=9544dc294f63ce116fbab398a8874ebf834cf41e;p=oota-llvm.git diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index fe912404cd9..9a66c8b6c11 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. // //===----------------------------------------------------------------------===// // @@ -20,63 +20,129 @@ #include namespace llvm { - + template -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 -struct DenseMapKeyInfo { +struct DenseMapInfo { 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 isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } + static bool isPod() { return true; } +}; + +// 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; + } }; -template > +// 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; template > + typename KeyInfoT = DenseMapInfo, + typename ValueInfoT = DenseMapInfo > class DenseMapConstIterator; template > + typename KeyInfoT = DenseMapInfo, + typename ValueInfoT = DenseMapInfo > 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() { @@ -91,10 +157,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. @@ -102,11 +171,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; } @@ -122,7 +191,7 @@ public: BucketT *TheBucket; return LookupBucketFor(Val, TheBucket); } - + iterator find(const KeyT &Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) @@ -135,17 +204,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)) @@ -165,49 +253,56 @@ 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; } - + private: void CopyFrom(const DenseMap& other) { - if (NumBuckets != 0 && !KeyInfoT::isPod()) { + 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]); - - if (KeyInfoT::isPod()) + 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); - new (Buckets[i].second) ValueT(other.Buckets[i].second); + 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 @@ -220,16 +315,16 @@ private: // table completely filled with tombstones, no lookup would ever succeed, // causing infinite loops in lookup. if (NumEntries*4 >= NumBuckets*3 || - NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) { - this->grow(); + 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; @@ -244,7 +339,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 @@ -253,37 +348,38 @@ 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. - 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; 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 (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 // probing. BucketNo += ProbeAmt++; @@ -294,23 +390,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() { + + void grow(unsigned AtLeast) { unsigned OldNumBuckets = NumBuckets; BucketT *OldBuckets = Buckets; - + // Double the number of buckets. - NumBuckets <<= 1; + 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(); @@ -320,7 +417,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); @@ -328,26 +426,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(); @@ -357,44 +455,47 @@ 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; } }; -template +template class DenseMapIterator { typedef std::pair BucketT; 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(); @@ -403,20 +504,23 @@ 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 && (Ptr->first == Empty || Ptr->first == Tombstone)) + while (Ptr != End && + (KeyInfoT::isEqual(Ptr->first, Empty) || + KeyInfoT::isEqual(Ptr->first, Tombstone))) ++Ptr; } }; -template +template class DenseMapConstIterator : public DenseMapIterator { public: + DenseMapConstIterator(void) : DenseMapIterator() {} DenseMapConstIterator(const std::pair *Pos, const std::pair *E) : DenseMapIterator(Pos, E) {