Implement TLSLDM.

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

diff --git a/include/llvm/ADT/DenseMap.h b/include/llvm/ADT/DenseMap.h
index 52354b7f222cabdceaa408874cbe94ba9ef2e459..06a1575da4d0f124d5f136c4e362f06791ad087f 100644 (file)
--- a/include/llvm/ADT/DenseMap.h
+++ b/include/llvm/ADT/DenseMap.h
@@ -14,25 +14,23 @@
 #ifndef LLVM_ADT_DENSEMAP_H
 #define LLVM_ADT_DENSEMAP_H
 
-#include "llvm/Support/PointerLikeTypeTraits.h"
 #include "llvm/Support/MathExtras.h"
+#include "llvm/Support/PointerLikeTypeTraits.h"
+#include "llvm/Support/type_traits.h"
 #include "llvm/ADT/DenseMapInfo.h"
 #include <iterator>
 #include <new>
 #include <utility>
 #include <cassert>
+#include <cstddef>
 #include <cstring>
 
 namespace llvm {
 
 template<typename KeyT, typename ValueT,
          typename KeyInfoT = DenseMapInfo<KeyT>,
-         typename ValueInfoT = DenseMapInfo<ValueT> >
+         typename ValueInfoT = DenseMapInfo<ValueT>, bool IsConst = false>
 class DenseMapIterator;
-template<typename KeyT, typename ValueT,
-         typename KeyInfoT = DenseMapInfo<KeyT>,
-         typename ValueInfoT = DenseMapInfo<ValueT> >
-class DenseMapConstIterator;
 
 template<typename KeyT, typename ValueT,
          typename KeyInfoT = DenseMapInfo<KeyT>,
@@ -49,7 +47,7 @@ public:
   typedef ValueT mapped_type;
   typedef BucketT value_type;
 
-  DenseMap(const DenseMap& other) {
+  DenseMap(const DenseMap &other) {
     NumBuckets = 0;
     CopyFrom(other);
   }
@@ -58,6 +56,12 @@ public:
     init(NumInitBuckets);
   }
 
+  template<typename InputIt>
+  DenseMap(const InputIt &I, const InputIt &E) {
+    init(64);
+    insert(I, E);
+  }
+  
   ~DenseMap() {
     const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
     for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
@@ -73,15 +77,17 @@ public:
   }
 
   typedef DenseMapIterator<KeyT, ValueT, KeyInfoT> iterator;
-  typedef DenseMapConstIterator<KeyT, ValueT, KeyInfoT> const_iterator;
+  typedef DenseMapIterator<KeyT, ValueT,
+                           KeyInfoT, ValueInfoT, true> const_iterator;
   inline iterator begin() {
-     return iterator(Buckets, Buckets+NumBuckets);
+    // When the map is empty, avoid the overhead of AdvancePastEmptyBuckets().
+    return empty() ? end() : iterator(Buckets, Buckets+NumBuckets);
   }
   inline iterator end() {
     return iterator(Buckets+NumBuckets, Buckets+NumBuckets);
   }
   inline const_iterator begin() const {
-    return const_iterator(Buckets, Buckets+NumBuckets);
+    return empty() ? end() : const_iterator(Buckets, Buckets+NumBuckets);
   }
   inline const_iterator end() const {
     return const_iterator(Buckets+NumBuckets, Buckets+NumBuckets);
@@ -179,13 +185,19 @@ public:
     ++NumTombstones;
     return true;
   }
-  bool erase(iterator I) {
+  void erase(iterator I) {
     BucketT *TheBucket = &*I;
     TheBucket->second.~ValueT();
     TheBucket->first = getTombstoneKey();
     --NumEntries;
     ++NumTombstones;
-    return true;
+  }
+
+  void swap(DenseMap& RHS) {
+    std::swap(NumBuckets, RHS.NumBuckets);
+    std::swap(Buckets, RHS.Buckets);
+    std::swap(NumEntries, RHS.NumEntries);
+    std::swap(NumTombstones, RHS.NumTombstones);
   }
 
   value_type& FindAndConstruct(const KeyT &Key) {
@@ -219,7 +231,8 @@ public:
 
 private:
   void CopyFrom(const DenseMap& other) {
-    if (NumBuckets != 0 && (!KeyInfoT::isPod() || !ValueInfoT::isPod())) {
+    if (NumBuckets != 0 &&
+        (!isPodLike<KeyInfoT>::value || !isPodLike<ValueInfoT>::value)) {
       const KeyT EmptyKey = getEmptyKey(), TombstoneKey = getTombstoneKey();
       for (BucketT *P = Buckets, *E = Buckets+NumBuckets; P != E; ++P) {
         if (!KeyInfoT::isEqual(P->first, EmptyKey) &&
@@ -241,7 +254,7 @@ private:
     Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT) *
                                                  other.NumBuckets));
 
-    if (KeyInfoT::isPod() && ValueInfoT::isPod())
+    if (isPodLike<KeyInfoT>::value && isPodLike<ValueInfoT>::value)
       memcpy(Buckets, other.Buckets, other.NumBuckets * sizeof(BucketT));
     else
       for (size_t i = 0; i < other.NumBuckets; ++i) {
@@ -354,7 +367,7 @@ private:
     BucketT *OldBuckets = Buckets;
 
     // Double the number of buckets.
-    while (NumBuckets <= AtLeast)
+    while (NumBuckets < AtLeast)
       NumBuckets <<= 1;
     NumTombstones = 0;
     Buckets = static_cast<BucketT*>(operator new(sizeof(BucketT)*NumBuckets));
@@ -426,32 +439,47 @@ private:
   }
 };
 
-template<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT>
-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;
+template<typename KeyT, typename ValueT,
+         typename KeyInfoT, typename ValueInfoT, bool IsConst>
+class DenseMapIterator {
+  typedef std::pair<KeyT, ValueT> Bucket;
+  typedef DenseMapIterator<KeyT, ValueT,
+                           KeyInfoT, ValueInfoT, true> ConstIterator;
+  friend class DenseMapIterator<KeyT, ValueT, KeyInfoT, ValueInfoT, true>;
+public:
+  typedef ptrdiff_t difference_type;
+  typedef typename conditional<IsConst, const Bucket, Bucket>::type value_type;
+  typedef value_type *pointer;
+  typedef value_type &reference;
+  typedef std::forward_iterator_tag iterator_category;
+private:
+  pointer Ptr, End;
 public:
   DenseMapIterator() : Ptr(0), End(0) {}
 
-  DenseMapIterator(const BucketT *Pos, const BucketT *E) : Ptr(Pos), End(E) {
+  DenseMapIterator(pointer Pos, pointer E) : Ptr(Pos), End(E) {
     AdvancePastEmptyBuckets();
   }
 
-  std::pair<KeyT, ValueT> &operator*() const {
-    return *const_cast<BucketT*>(Ptr);
+  // If IsConst is true this is a converting constructor from iterator to
+  // const_iterator and the default copy constructor is used.
+  // Otherwise this is a copy constructor for iterator.
+  DenseMapIterator(const DenseMapIterator<KeyT, ValueT,
+                                          KeyInfoT, ValueInfoT, false>& I)
+    : Ptr(I.Ptr), End(I.End) {}
+
+  reference operator*() const {
+    return *Ptr;
   }
-  std::pair<KeyT, ValueT> *operator->() const {
-    return const_cast<BucketT*>(Ptr);
+  pointer operator->() const {
+    return Ptr;
   }
 
-  bool operator==(const DenseMapIterator &RHS) const {
-    return Ptr == RHS.Ptr;
+  bool operator==(const ConstIterator &RHS) const {
+    return Ptr == RHS.operator->();
   }
-  bool operator!=(const DenseMapIterator &RHS) const {
-    return Ptr != RHS.Ptr;
+  bool operator!=(const ConstIterator &RHS) const {
+    return Ptr != RHS.operator->();
   }
 
   inline DenseMapIterator& operator++() {  // Preincrement
@@ -475,22 +503,6 @@ private:
   }
 };
 
-template<typename KeyT, typename ValueT, typename KeyInfoT, typename ValueInfoT>
-class DenseMapConstIterator : public DenseMapIterator<KeyT, ValueT, KeyInfoT> {
-public:
-  DenseMapConstIterator() : DenseMapIterator<KeyT, ValueT, KeyInfoT>() {}
-  DenseMapConstIterator(const std::pair<KeyT, ValueT> *Pos,
-                        const std::pair<KeyT, ValueT> *E)
-    : DenseMapIterator<KeyT, ValueT, KeyInfoT>(Pos, E) {
-  }
-  const std::pair<KeyT, ValueT> &operator*() const {
-    return *this->Ptr;
-  }
-  const std::pair<KeyT, ValueT> *operator->() const {
-    return this->Ptr;
-  }
-};
-
 } // end namespace llvm
 
 #endif