minor cleanups. Add provisions for a new standard BLOCKINFO_BLOCK

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

diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index fa3e2df8947a344162c5b2f344ed34c192496069..83edd640e33493125f6539b91125bbce70170b6f 100644 (file)
--- a/include/llvm/ADT/DenseMap.h
+++ b/include/llvm/ADT/DenseMap.h
@@ -28,6 +28,7 @@ struct DenseMapKeyInfo {
   //static bool isPod()
 };
 
+// Provide DenseMapKeyInfo for all pointers.
 template<typename T>
 struct DenseMapKeyInfo<T*> {
   static inline T* getEmptyKey() { return (T*)-1; }
@@ -39,21 +40,25 @@ struct DenseMapKeyInfo<T*> {
   static bool isPod() { return true; }
 };
 
-template<typename KeyT, typename ValueT>
+template<typename KeyT, typename ValueT, 
+         typename KeyInfoT = DenseMapKeyInfo<KeyT> >
 class DenseMapIterator;
-template<typename KeyT, typename ValueT>
+template<typename KeyT, typename ValueT,
+         typename KeyInfoT = DenseMapKeyInfo<KeyT> >
 class DenseMapConstIterator;
 
-template<typename KeyT, typename ValueT>
+template<typename KeyT, typename ValueT,
+         typename KeyInfoT = DenseMapKeyInfo<KeyT> >
 class DenseMap {
   typedef std::pair<KeyT, ValueT> BucketT;
   unsigned NumBuckets;
   BucketT *Buckets;
   
   unsigned NumEntries;
+  unsigned NumTombstones;
   DenseMap(const DenseMap &); // not implemented.
 public:
-  explicit DenseMap(unsigned NumInitBuckets = 8) {
+  explicit DenseMap(unsigned NumInitBuckets = 64) {
     init(NumInitBuckets);
   }
   ~DenseMap() {
@@ -66,21 +71,19 @@ public:
     delete[] (char*)Buckets;
   }
   
-  typedef DenseMapIterator<KeyT, ValueT> iterator;
-  typedef DenseMapConstIterator<KeyT, ValueT> const_iterator;
+  typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator;
+  typedef DenseMapConstIterator<KeyT, ValueT, KeyInfoT> const_iterator;
   inline iterator begin() {
-     return DenseMapIterator<KeyT, ValueT>(Buckets, Buckets+NumBuckets);
+     return iterator(Buckets, Buckets+NumBuckets);
   }
   inline iterator end() {
-    return DenseMapIterator<KeyT, ValueT>(Buckets+NumBuckets, 
-                                          Buckets+NumBuckets);
+    return iterator(Buckets+NumBuckets, Buckets+NumBuckets);
   }
   inline const_iterator begin() const {
-    return DenseMapConstIterator<KeyT, ValueT>(Buckets, Buckets+NumBuckets);
+    return const_iterator(Buckets, Buckets+NumBuckets);
   }
   inline const_iterator end() const {
-    return DenseMapConstIterator<KeyT, ValueT>(Buckets+NumBuckets, 
-                                               Buckets+NumBuckets);
+    return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets);
   }
   
   bool empty() const { return NumEntries == 0; }
@@ -96,6 +99,7 @@ public:
       }
     }
     assert(NumEntries == 0 && "Node count imbalance!");
+    NumTombstones = 0;
   }
   
   /// count - Return true if the specified key is in the map.
@@ -104,12 +108,28 @@ public:
     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<KeyT, ValueT> &KV) {
+    BucketT *TheBucket;
+    if (LookupBucketFor(KV.first, TheBucket))
+      return false; // Already in map.
+    
+    // Otherwise, insert the new element.
+    InsertIntoBucket(KV.first, KV.second, TheBucket);
+    return true;
+  }
   
   bool erase(const KeyT &Val) {
     BucketT *TheBucket;
@@ -119,6 +139,7 @@ public:
     TheBucket->second.~ValueT();
     TheBucket->first = getTombstoneKey();
     --NumEntries;
+    ++NumTombstones;
     return true;
   }
   bool erase(iterator I) {
@@ -126,34 +147,54 @@ public:
     TheBucket->second.~ValueT();
     TheBucket->first = getTombstoneKey();
     --NumEntries;
+    ++NumTombstones;
     return true;
   }
   
-  ValueT &operator[](const KeyT &Val) {
+  ValueT &operator[](const KeyT &Key) {
     BucketT *TheBucket;
-    if (LookupBucketFor(Val, TheBucket))
+    if (LookupBucketFor(Key, TheBucket))
       return TheBucket->second;
 
-    // If the load of the hash table is more than 3/4, grow it.
-    if (NumEntries*4 >= NumBuckets*3) {
+    return InsertIntoBucket(Key, ValueT(), TheBucket)->second;
+  }
+  
+private:
+  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
+    // the buckets are empty (meaning that many are filled with tombstones),
+    // grow the table.
+    //
+    // The later case is tricky.  For example, if we had one empty bucket with
+    // tons of tombstones, failing lookups (e.g. for insertion) would have to
+    // 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.
+    if (NumEntries*4 >= NumBuckets*3 ||
+        NumBuckets-(NumEntries+NumTombstones) < NumBuckets/8) {        
       this->grow();
-      LookupBucketFor(Val, TheBucket);
+      LookupBucketFor(Key, TheBucket);
     }
     ++NumEntries;
-    TheBucket->first = Val;
-    new (&TheBucket->second) ValueT();
-    return TheBucket->second;
+    
+    // If we are writing over a tombstone, remember this.
+    if (TheBucket->first != getEmptyKey())
+      --NumTombstones;
+    
+    TheBucket->first = Key;
+    new (&TheBucket->second) ValueT(Value);
+    return TheBucket;
   }
-  
-private:
+
   static unsigned getHashValue(const KeyT &Val) {
-    return DenseMapKeyInfo<KeyT>::getHashValue(Val);
+    return KeyInfoT::getHashValue(Val);
   }
   static const KeyT getEmptyKey() {
-    return DenseMapKeyInfo<KeyT>::getEmptyKey();
+    return KeyInfoT::getEmptyKey();
   }
   static const KeyT getTombstoneKey() {
-    return DenseMapKeyInfo<KeyT>::getTombstoneKey();
+    return KeyInfoT::getTombstoneKey();
   }
   
   /// LookupBucketFor - Lookup the appropriate bucket for Val, returning it in
@@ -203,6 +244,7 @@ private:
 
   void init(unsigned InitBuckets) {
     NumEntries = 0;
+    NumTombstones = 0;
     NumBuckets = InitBuckets;
     assert(InitBuckets && (InitBuckets & InitBuckets-1) == 0 &&
            "# initial buckets must be a power of two!");
@@ -219,6 +261,7 @@ private:
     
     // Double the number of buckets.
     NumBuckets <<= 1;
+    NumTombstones = 0;
     Buckets = (BucketT*)new char[sizeof(BucketT)*NumBuckets];
 
     // Initialize all the keys to EmptyKey.
@@ -249,7 +292,7 @@ private:
   }
 };
 
-template<typename KeyT, typename ValueT>
+template<typename KeyT, typename ValueT, typename KeyInfoT>
 class DenseMapIterator {
   typedef std::pair<KeyT, ValueT> BucketT;
 protected:
@@ -284,20 +327,20 @@ public:
   
 private:
   void AdvancePastEmptyBuckets() {
-    const KeyT Empty = DenseMapKeyInfo<KeyT>::getEmptyKey();
-    const KeyT Tombstone = DenseMapKeyInfo<KeyT>::getTombstoneKey();
+    const KeyT Empty = KeyInfoT::getEmptyKey();
+    const KeyT Tombstone = KeyInfoT::getTombstoneKey();
 
     while (Ptr != End && (Ptr->first == Empty || Ptr->first == Tombstone))
       ++Ptr;
   }
 };
 
-template<typename KeyT, typename ValueT>
-class DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT> {
+template<typename KeyT, typename ValueT, typename KeyInfoT>
+class DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT, KeyInfoT> {
 public:
   DenseMapConstIterator(const std::pair<KeyT, ValueT> *Pos,
                         const std::pair<KeyT, ValueT> *E)
-    : DenseMapIterator<KeyT, ValueT>(Pos, E) {
+    : DenseMapIterator<KeyT, ValueT, KeyInfoT>(Pos, E) {
   }
   const std::pair<KeyT, ValueT> &operator*() const {
     return *this->Ptr;