1 files changed, 72 insertions, 39 deletions

diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h
index bd0d8838ef02..74f3fd43cec4 100644
--- a/include/llvm/ADT/SmallPtrSet.h
+++ b/include/llvm/ADT/SmallPtrSet.h
@@ -8,7 +8,7 @@
 //===----------------------------------------------------------------------===//
 //
 // This file defines the SmallPtrSet class.  See the doxygen comment for
-// SmallPtrSetImpl for more details on the algorithm used.
+// SmallPtrSetImplBase for more details on the algorithm used.
 //
 //===----------------------------------------------------------------------===//
 
@@ -27,7 +27,7 @@ namespace llvm {
 
 class SmallPtrSetIteratorImpl;
 
-/// SmallPtrSetImpl - This is the common code shared among all the
+/// SmallPtrSetImplBase - This is the common code shared among all the
 /// SmallPtrSet<>'s, which is almost everything.  SmallPtrSet has two modes, one
 /// for small and one for large sets.
 ///
@@ -45,7 +45,7 @@ class SmallPtrSetIteratorImpl;
 /// (-2), to allow deletion.  The hash table is resized when the table is 3/4 or
 /// more.  When this happens, the table is doubled in size.
 ///
-class SmallPtrSetImpl {
+class SmallPtrSetImplBase {
   friend class SmallPtrSetIteratorImpl;
 protected:
   /// SmallArray - Points to a fixed size set of buckets, used in 'small mode'.
@@ -60,19 +60,22 @@ protected:
   unsigned NumElements;
   unsigned NumTombstones;
 
-  // Helper to copy construct a SmallPtrSet.
-  SmallPtrSetImpl(const void **SmallStorage, const SmallPtrSetImpl& that);
-  explicit SmallPtrSetImpl(const void **SmallStorage, unsigned SmallSize) :
+  // Helpers to copy and move construct a SmallPtrSet.
+  SmallPtrSetImplBase(const void **SmallStorage, const SmallPtrSetImplBase &that);
+  SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize,
+                  SmallPtrSetImplBase &&that);
+  explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize) :
     SmallArray(SmallStorage), CurArray(SmallStorage), CurArraySize(SmallSize) {
     assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 &&
            "Initial size must be a power of two!");
     clear();
   }
-  ~SmallPtrSetImpl();
+  ~SmallPtrSetImplBase();
 
 public:
+  typedef unsigned size_type;
   bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return size() == 0; }
-  unsigned size() const { return NumElements; }
+  size_type size() const { return NumElements; }
 
   void clear() {
     // If the capacity of the array is huge, and the # elements used is small,
@@ -128,13 +131,14 @@ private:
   /// Grow - Allocate a larger backing store for the buckets and move it over.
   void Grow(unsigned NewSize);
 
-  void operator=(const SmallPtrSetImpl &RHS) LLVM_DELETED_FUNCTION;
+  void operator=(const SmallPtrSetImplBase &RHS) LLVM_DELETED_FUNCTION;
 protected:
   /// swap - Swaps the elements of two sets.
   /// Note: This method assumes that both sets have the same small size.
-  void swap(SmallPtrSetImpl &RHS);
+  void swap(SmallPtrSetImplBase &RHS);
 
-  void CopyFrom(const SmallPtrSetImpl &RHS);
+  void CopyFrom(const SmallPtrSetImplBase &RHS);
+  void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS);
 };
 
 /// SmallPtrSetIteratorImpl - This is the common base class shared between all
@@ -163,8 +167,8 @@ protected:
   void AdvanceIfNotValid() {
     assert(Bucket <= End);
     while (Bucket != End &&
-           (*Bucket == SmallPtrSetImpl::getEmptyMarker() ||
-            *Bucket == SmallPtrSetImpl::getTombstoneMarker()))
+           (*Bucket == SmallPtrSetImplBase::getEmptyMarker() ||
+            *Bucket == SmallPtrSetImplBase::getTombstoneMarker()))
       ++Bucket;
   }
 };
@@ -228,26 +232,25 @@ struct RoundUpToPowerOfTwo {
 };
   
 
-/// SmallPtrSet - This class implements a set which is optimized for holding
-/// SmallSize or less elements.  This internally rounds up SmallSize to the next
-/// power of two if it is not already a power of two.  See the comments above
-/// SmallPtrSetImpl for details of the algorithm.
-template<class PtrType, unsigned SmallSize>
-class SmallPtrSet : public SmallPtrSetImpl {
-  // Make sure that SmallSize is a power of two, round up if not.
-  enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val };
-  /// SmallStorage - Fixed size storage used in 'small mode'.
-  const void *SmallStorage[SmallSizePowTwo];
+/// \brief A templated base class for \c SmallPtrSet which provides the
+/// typesafe interface that is common across all small sizes.
+///
+/// This is particularly useful for passing around between interface boundaries
+/// to avoid encoding a particular small size in the interface boundary.
+template <typename PtrType>
+class SmallPtrSetImpl : public SmallPtrSetImplBase {
   typedef PointerLikeTypeTraits<PtrType> PtrTraits;
-public:
-  SmallPtrSet() : SmallPtrSetImpl(SmallStorage, SmallSizePowTwo) {}
-  SmallPtrSet(const SmallPtrSet &that) : SmallPtrSetImpl(SmallStorage, that) {}
-
-  template<typename It>
-  SmallPtrSet(It I, It E) : SmallPtrSetImpl(SmallStorage, SmallSizePowTwo) {
-    insert(I, E);
-  }
+protected:
+  // Constructors that forward to the base.
+  SmallPtrSetImpl(const void **SmallStorage, const SmallPtrSetImpl &that)
+      : SmallPtrSetImplBase(SmallStorage, that) {}
+  SmallPtrSetImpl(const void **SmallStorage, unsigned SmallSize,
+                  SmallPtrSetImpl &&that)
+      : SmallPtrSetImplBase(SmallStorage, SmallSize, std::move(that)) {}
+  explicit SmallPtrSetImpl(const void **SmallStorage, unsigned SmallSize)
+      : SmallPtrSetImplBase(SmallStorage, SmallSize) {}
 
+public:
   /// insert - This returns true if the pointer was new to the set, false if it
   /// was already in the set.
   bool insert(PtrType Ptr) {
@@ -260,9 +263,9 @@ public:
     return erase_imp(PtrTraits::getAsVoidPointer(Ptr));
   }
 
-  /// count - Return true if the specified pointer is in the set.
-  bool count(PtrType Ptr) const {
-    return count_imp(PtrTraits::getAsVoidPointer(Ptr));
+  /// count - Return 1 if the specified pointer is in the set, 0 otherwise.
+  size_type count(PtrType Ptr) const {
+    return count_imp(PtrTraits::getAsVoidPointer(Ptr)) ? 1 : 0;
   }
 
   template <typename IterT>
@@ -279,18 +282,48 @@ public:
   inline iterator end() const {
     return iterator(CurArray+CurArraySize, CurArray+CurArraySize);
   }
+};
 
-  // Allow assignment from any smallptrset with the same element type even if it
-  // doesn't have the same smallsize.
-  const SmallPtrSet<PtrType, SmallSize>&
+/// SmallPtrSet - This class implements a set which is optimized for holding
+/// SmallSize or less elements.  This internally rounds up SmallSize to the next
+/// power of two if it is not already a power of two.  See the comments above
+/// SmallPtrSetImplBase for details of the algorithm.
+template<class PtrType, unsigned SmallSize>
+class SmallPtrSet : public SmallPtrSetImpl<PtrType> {
+  typedef SmallPtrSetImpl<PtrType> BaseT;
+
+  // Make sure that SmallSize is a power of two, round up if not.
+  enum { SmallSizePowTwo = RoundUpToPowerOfTwo<SmallSize>::Val };
+  /// SmallStorage - Fixed size storage used in 'small mode'.
+  const void *SmallStorage[SmallSizePowTwo];
+public:
+  SmallPtrSet() : BaseT(SmallStorage, SmallSizePowTwo) {}
+  SmallPtrSet(const SmallPtrSet &that) : BaseT(SmallStorage, that) {}
+  SmallPtrSet(SmallPtrSet &&that)
+      : BaseT(SmallStorage, SmallSizePowTwo, std::move(that)) {}
+
+  template<typename It>
+  SmallPtrSet(It I, It E) : BaseT(SmallStorage, SmallSizePowTwo) {
+    this->insert(I, E);
+  }
+
+  SmallPtrSet<PtrType, SmallSize> &
   operator=(const SmallPtrSet<PtrType, SmallSize> &RHS) {
-    CopyFrom(RHS);
+    if (&RHS != this)
+      this->CopyFrom(RHS);
+    return *this;
+  }
+
+  SmallPtrSet<PtrType, SmallSize>&
+  operator=(SmallPtrSet<PtrType, SmallSize> &&RHS) {
+    if (&RHS != this)
+      this->MoveFrom(SmallSizePowTwo, std::move(RHS));
     return *this;
   }
 
   /// swap - Swaps the elements of two sets.
   void swap(SmallPtrSet<PtrType, SmallSize> &RHS) {
-    SmallPtrSetImpl::swap(RHS);
+    SmallPtrSetImplBase::swap(RHS);
   }
 };