1 files changed, 29 insertions, 103 deletions

diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index e18be89..0ed2d5a 100644
--- a/include/llvm/ADT/DenseMap.h
+++ b/include/llvm/ADT/DenseMap.h
@@ -16,109 +16,15 @@
 
 #include "llvm/Support/PointerLikeTypeTraits.h"
 #include "llvm/Support/MathExtras.h"
-#include <cassert>
-#include <utility>
+#include "llvm/ADT/DenseMapInfo.h"
+#include <iterator>
 #include <new>
+#include <utility>
+#include <cassert>
+#include <cstring>
 
 namespace llvm {
 
-template<typename T>
-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 DenseMapInfo for all pointers.
-template<typename T>
-struct DenseMapInfo<T*> {
-  static inline T* getEmptyKey() {
-    intptr_t Val = -1;
-    Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
-    return reinterpret_cast<T*>(Val);
-  }
-  static inline T* getTombstoneKey() {
-    intptr_t Val = -2;
-    Val <<= PointerLikeTypeTraits<T*>::NumLowBitsAvailable;
-    return reinterpret_cast<T*>(Val);
-  }
-  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; }
-};
-
-// Provide DenseMapInfo for chars.
-template<> struct DenseMapInfo<char> {
-  static inline char getEmptyKey() { return ~0; }
-  static inline char getTombstoneKey() { return ~0 - 1; }
-  static unsigned getHashValue(const char& Val) { return Val * 37; }
-  static bool isPod() { return true; }
-  static bool isEqual(const char &LHS, const char &RHS) {
-    return LHS == RHS;
-  }
-};
-  
-// Provide DenseMapInfo for unsigned ints.
-template<> struct DenseMapInfo<unsigned> {
-  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<unsigned long> {
-  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;
-  }
-};
-
-// Provide DenseMapInfo for all pairs whose members have info.
-template<typename T, typename U>
-struct DenseMapInfo<std::pair<T, U> > {
-  typedef std::pair<T, U> Pair;
-  typedef DenseMapInfo<T> FirstInfo;
-  typedef DenseMapInfo<U> 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 KeyT, typename ValueT,
          typename KeyInfoT = DenseMapInfo<KeyT>,
          typename ValueInfoT = DenseMapInfo<ValueT> >
@@ -160,6 +66,9 @@ public:
         P->second.~ValueT();
       P->first.~KeyT();
     }
+#ifndef NDEBUG
+    memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets);
+#endif
     operator delete(Buckets);
   }
 
@@ -185,6 +94,8 @@ public:
   void resize(size_t Size) { grow(Size); }
 
   void clear() {
+    if (NumEntries == 0 && NumTombstones == 0) return;
+    
     // If the capacity of the array is huge, and the # elements used is small,
     // shrink the array.
     if (NumEntries * 4 < NumBuckets && NumBuckets > 64) {
@@ -234,6 +145,9 @@ public:
     return ValueT();
   }
 
+  // Inserts key,value pair into the map if the key isn't already in the map.
+  // If the key is already in the map, it returns false and doesn't update the
+  // value.
   std::pair<iterator, bool> insert(const std::pair<KeyT, ValueT> &KV) {
     BucketT *TheBucket;
     if (LookupBucketFor(KV.first, TheBucket))
@@ -318,8 +232,12 @@ private:
     NumEntries = other.NumEntries;
     NumTombstones = other.NumTombstones;
 
-    if (NumBuckets)
+    if (NumBuckets) {
+#ifndef NDEBUG
+      memset(Buckets, 0x5a, sizeof(BucketT)*NumBuckets);
+#endif
       operator delete(Buckets);
+    }
     Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) *
                                                  other.NumBuckets));
 
@@ -465,6 +383,9 @@ private:
       B->first.~KeyT();
     }
 
+#ifndef NDEBUG
+    memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets);
+#endif
     // Free the old table.
     operator delete(OldBuckets);
   }
@@ -495,6 +416,9 @@ private:
       B->first.~KeyT();
     }
 
+#ifndef NDEBUG
+    memset(OldBuckets, 0x5a, sizeof(BucketT)*OldNumBuckets);
+#endif
     // Free the old table.
     operator delete(OldBuckets);
 
@@ -503,12 +427,14 @@ private:
 };
 
 template<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT>
-class DenseMapIterator {
+class DenseMapIterator : 
+      public std::iterator<std::forward_iterator_tag, std::pair<KeyT, ValueT>,
+                          ptrdiff_t> {
   typedef std::pair<KeyT, ValueT> BucketT;
 protected:
   const BucketT *Ptr, *End;
 public:
-  DenseMapIterator(void) : Ptr(0), End(0) {}
+  DenseMapIterator() : Ptr(0), End(0) {}
 
   DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) {
     AdvancePastEmptyBuckets();
@@ -552,7 +478,7 @@ private:
 template<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT>
 class DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT, KeyInfoT> {
 public:
-  DenseMapConstIterator(void) : DenseMapIterator<KeyT, ValueT, KeyInfoT>() {}
+  DenseMapConstIterator() : DenseMapIterator<KeyT, ValueT, KeyInfoT>() {}
   DenseMapConstIterator(const std::pair<KeyT, ValueT> *Pos,
                         const std::pair<KeyT, ValueT> *E)
     : DenseMapIterator<KeyT, ValueT, KeyInfoT>(Pos, E) {