Add an optional optimization to FoldingSet to allow ID values to be

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

diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index df497d37d76d16e26374626e96ab7082840e9adc..e18be8963d48bda4032b4425b5a41762e062754b 100644 (file)
--- a/include/llvm/ADT/DenseMap.h
+++ b/include/llvm/ADT/DenseMap.h
@@ -14,10 +14,11 @@
 #ifndef LLVM_ADT_DENSEMAP_H
 #define LLVM_ADT_DENSEMAP_H
 
-#include "llvm/Support/DataTypes.h"
+#include "llvm/Support/PointerLikeTypeTraits.h"
 #include "llvm/Support/MathExtras.h"
 #include <cassert>
 #include <utility>
+#include <new>
 
 namespace llvm {
 
@@ -33,8 +34,16 @@ struct DenseMapInfo {
 // Provide DenseMapInfo for all pointers.
 template<typename T>
 struct DenseMapInfo<T*> {
-  static inline T* getEmptyKey() { return reinterpret_cast<T*>(-1); }
-  static inline T* getTombstoneKey() { return reinterpret_cast<T*>(-2); }
+  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);
@@ -43,6 +52,17 @@ struct DenseMapInfo<T*> {
   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; }
@@ -58,7 +78,9 @@ template<> struct DenseMapInfo<unsigned> {
 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 Val * 37L; }
+  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;
@@ -269,6 +291,18 @@ public:
     return *this;
   }
 
+  /// isPointerIntoBucketsArray - Return true if the specified pointer points
+  /// somewhere into the DenseMap's array of buckets (i.e. either to a key or
+  /// value in the DenseMap).
+  bool isPointerIntoBucketsArray(const void *Ptr) const {
+    return Ptr >= Buckets && Ptr < Buckets+NumBuckets;
+  }
+
+  /// getPointerIntoBucketsArray() - Return an opaque pointer into the buckets
+  /// array.  In conjunction with the previous method, this can be used to
+  /// determine whether an insertion caused the DenseMap to reallocate.
+  const void *getPointerIntoBucketsArray() const { return Buckets; }
+
 private:
   void CopyFrom(const DenseMap& other) {
     if (NumBuckets != 0 && (!KeyInfoT::isPod() || !ValueInfoT::isPod())) {
@@ -312,12 +346,12 @@ private:
     // 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.
+    ++NumEntries;
     if (NumEntries*4 >= NumBuckets*3 ||
         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()))