X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FDenseMap.h;h=9a66c8b6c1171c35d7e2b8c4768aeba2a3d1c01f;hb=6de603071879bdc5d7d663826354c24a9d176469;hp=df8f464adafd5b968bc1e9aec5142256402c4256;hpb=2dba6a1bdb7d78b4d1e5e69b81989816193e6b70;p=oota-llvm.git diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h index df8f464adaf..9a66c8b6c11 100644 --- a/include/llvm/ADT/DenseMap.h +++ b/include/llvm/ADT/DenseMap.h @@ -20,7 +20,7 @@ #include namespace llvm { - + template struct DenseMapInfo { //static inline T getEmptyKey(); @@ -36,7 +36,7 @@ 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) ^ + return (unsigned((uintptr_t)PtrVal) >> 4) ^ (unsigned((uintptr_t)PtrVal) >> 9); } static bool isEqual(const T *LHS, const T *RHS) { return LHS == RHS; } @@ -44,12 +44,25 @@ struct DenseMapInfo { }; // 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 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 uint32_t& LHS, const uint32_t& RHS) { + static bool isEqual(const unsigned long& LHS, const unsigned long& RHS) { return LHS == RHS; } }; @@ -61,31 +74,32 @@ struct DenseMapInfo > { 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 false; } + 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; @@ -101,21 +115,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) { @@ -126,7 +142,7 @@ public: } operator delete(Buckets); } - + typedef DenseMapIterator iterator; typedef DenseMapConstIterator const_iterator; inline iterator begin() { @@ -141,13 +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. @@ -155,7 +171,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)) { @@ -175,7 +191,7 @@ public: BucketT *TheBucket; return LookupBucketFor(Val, TheBucket); } - + iterator find(const KeyT &Val) { BucketT *TheBucket; if (LookupBucketFor(Val, TheBucket)) @@ -188,19 +204,36 @@ 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 { + 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 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) { + for (; I != E; ++I) + insert(*I); + } + + bool erase(const KeyT &Val) { BucketT *TheBucket; if (!LookupBucketFor(Val, TheBucket)) @@ -225,19 +258,19 @@ 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; } - + private: void CopyFrom(const DenseMap& other) { if (NumBuckets != 0 && (!KeyInfoT::isPod() || !ValueInfoT::isPod())) { @@ -249,15 +282,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 @@ -269,7 +302,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 @@ -282,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) { + 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; @@ -306,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 @@ -315,7 +348,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(); @@ -323,7 +356,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. @@ -331,7 +364,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)) { @@ -341,12 +374,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++; @@ -365,11 +398,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; @@ -393,21 +426,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; @@ -429,10 +462,10 @@ private: } B->first.~KeyT(); } - + // Free the old table. operator delete(OldBuckets); - + NumEntries = 0; } }; @@ -443,24 +476,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(); @@ -469,13 +504,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; @@ -485,6 +520,7 @@ private: template class DenseMapConstIterator : public DenseMapIterator { public: + DenseMapConstIterator(void) : DenseMapIterator() {} DenseMapConstIterator(const std::pair *Pos, const std::pair *E) : DenseMapIterator(Pos, E) {