Added iterator and profiling (i.e. FoldingSetNodeID) support to ImmutableMap.

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

diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index 78d8f83cbb407b28257b233e2975f32e026e7aa2..fdfb3294ea3d2553524aafca9e51b893228029e3 100644 (file)
--- 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.
 //
 //===----------------------------------------------------------------------===//
 //
@@ -36,8 +36,8 @@ 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);
+    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; }
@@ -63,6 +63,8 @@ class DenseMap {
   unsigned NumEntries;
   unsigned NumTombstones;
 public:
+  typedef BucketT value_type;
+  
   DenseMap(const DenseMap& other) {
     NumBuckets = 0;
     CopyFrom(other);
@@ -75,7 +77,8 @@ public:
   ~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();
     }
@@ -113,8 +116,8 @@ public:
     
     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;
         }
@@ -173,13 +176,17 @@ 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 InsertIntoBucket(Key, ValueT(), TheBucket)->second;
+      return *TheBucket;
+    
+    return *InsertIntoBucket(Key, ValueT(), TheBucket);
+  }
+  
+  ValueT &operator[](const KeyT &Key) {
+    return FindAndConstruct(Key).second;
   }
   
   DenseMap& operator=(const DenseMap& other) {
@@ -192,7 +199,8 @@ private:
     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();
       }
@@ -211,8 +219,8 @@ private:
     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())
+        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;
@@ -237,7 +245,7 @@ private:
     ++NumEntries;
     
     // If we are writing over a tombstone, remember this.
-    if (TheBucket->first != getEmptyKey())
+    if (!KeyInfoT::isEqual(TheBucket->first, getEmptyKey()))
       --NumTombstones;
     
     TheBucket->first = Key;
@@ -268,7 +276,8 @@ private:
     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) {
@@ -331,7 +340,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);
@@ -368,7 +378,8 @@ 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();
       }