Implement offline variable substitution in order to reduce memory

[oota-llvm.git] / include / llvm / ADT / DenseMap.h

diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index 43382492856cbfe471d62db431454a256d292727..78d8f83cbb407b28257b233e2975f32e026e7aa2 100644 (file)
--- a/include/llvm/ADT/DenseMap.h
+++ b/include/llvm/ADT/DenseMap.h
@@ -22,34 +22,39 @@
 namespace llvm {
   
 template<typename T>
-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<typename T>
-struct DenseMapKeyInfo<T*> {
+struct DenseMapInfo<T*> {
   static inline T* getEmptyKey() { return reinterpret_cast<T*>(-1); }
   static inline T* getTombstoneKey() { return reinterpret_cast<T*>(-2); }
   static unsigned getHashValue(const T *PtrVal) {
     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<typename KeyT, typename ValueT, 
-         typename KeyInfoT = DenseMapKeyInfo<KeyT> >
+         typename KeyInfoT = DenseMapInfo<KeyT>,
+         typename ValueInfoT = DenseMapInfo<ValueT> >
 class DenseMapIterator;
 template<typename KeyT, typename ValueT,
-         typename KeyInfoT = DenseMapKeyInfo<KeyT> >
+         typename KeyInfoT = DenseMapInfo<KeyT>,
+         typename ValueInfoT = DenseMapInfo<ValueT> >
 class DenseMapConstIterator;
 
 template<typename KeyT, typename ValueT,
-         typename KeyInfoT = DenseMapKeyInfo<KeyT> >
+         typename KeyInfoT = DenseMapInfo<KeyT>,
+         typename ValueInfoT = DenseMapInfo<ValueT> >
 class DenseMap {
   typedef std::pair<KeyT, ValueT> BucketT;
   unsigned NumBuckets;
@@ -94,6 +99,9 @@ public:
   
   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,
@@ -181,7 +189,7 @@ public:
   
 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)
@@ -198,14 +206,14 @@ private:
     Buckets = reinterpret_cast<BucketT*>(new char[sizeof(BucketT) *
                                                   other.NumBuckets]);
     
-    if (KeyInfoT::isPod())
+    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);
+            Buckets[i].first != getTombstoneKey())
+          new (&Buckets[i].second) ValueT(other.Buckets[i].second);
       }
     NumBuckets = other.NumBuckets;
   }
@@ -223,7 +231,7 @@ private:
     // causing infinite loops in lookup.
     if (NumEntries*4 >= NumBuckets*3 ||
         NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) {        
-      this->grow();
+      this->grow(NumBuckets * 2);
       LookupBucketFor(Key, TheBucket);
     }
     ++NumEntries;
@@ -266,14 +274,14 @@ private:
     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;
@@ -283,7 +291,7 @@ private:
       
       // 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
@@ -305,12 +313,13 @@ private:
       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<BucketT*>(new char[sizeof(BucketT)*NumBuckets]);
 
@@ -373,7 +382,7 @@ private:
   }
 };
 
-template<typename KeyT, typename ValueT, typename KeyInfoT>
+template<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT>
 class DenseMapIterator {
   typedef std::pair<KeyT, ValueT> BucketT;
 protected:
@@ -411,12 +420,14 @@ private:
     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<typename KeyT, typename ValueT, typename KeyInfoT>
+template<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT>
 class DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT, KeyInfoT> {
 public:
   DenseMapConstIterator(const std::pair<KeyT, ValueT> *Pos,