X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSmallPtrSet.h;h=3d98e8fac43b61a36d965cca0509cbf4c3e34ef8;hb=697fe024f6dad16e21c9b8e41bb27463971939c0;hp=b07300532148ba89551a2cc54398cca3ee840a35;hpb=e3f87943291d589059a9f2838e5dbb05bc91d7dd;p=oota-llvm.git diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index b0730053214..3d98e8fac43 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -22,6 +22,7 @@ #include #include #include +#include namespace llvm { @@ -47,6 +48,7 @@ class SmallPtrSetIteratorImpl; /// class SmallPtrSetImplBase { friend class SmallPtrSetIteratorImpl; + protected: /// SmallArray - Points to a fixed size set of buckets, used in 'small mode'. const void **SmallArray; @@ -62,10 +64,8 @@ protected: // Helpers to copy and move construct a SmallPtrSet. SmallPtrSetImplBase(const void **SmallStorage, const SmallPtrSetImplBase &that); -#if LLVM_HAS_RVALUE_REFERENCES SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize, SmallPtrSetImplBase &&that); -#endif explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize) : SmallArray(SmallStorage), CurArray(SmallStorage), CurArraySize(SmallSize) { assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 && @@ -75,8 +75,9 @@ protected: ~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, @@ -101,7 +102,7 @@ protected: /// insert_imp - This returns true if the pointer was new to the set, false if /// it was already in the set. This is hidden from the client so that the /// derived class can check that the right type of pointer is passed in. - bool insert_imp(const void * Ptr); + std::pair insert_imp(const void *Ptr); /// erase_imp - If the set contains the specified pointer, remove it and /// return true, otherwise return false. This is hidden from the client so @@ -132,16 +133,15 @@ private: /// Grow - Allocate a larger backing store for the buckets and move it over. void Grow(unsigned NewSize); - void operator=(const SmallPtrSetImplBase &RHS) LLVM_DELETED_FUNCTION; + void operator=(const SmallPtrSetImplBase &RHS) = delete; + protected: /// swap - Swaps the elements of two sets. /// Note: This method assumes that both sets have the same small size. void swap(SmallPtrSetImplBase &RHS); void CopyFrom(const SmallPtrSetImplBase &RHS); -#if LLVM_HAS_RVALUE_REFERENCES void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS); -#endif }; /// SmallPtrSetIteratorImpl - This is the common base class shared between all @@ -150,6 +150,7 @@ class SmallPtrSetIteratorImpl { protected: const void *const *Bucket; const void *const *End; + public: explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E) : Bucket(BP), End(E) { @@ -180,14 +181,14 @@ protected: template class SmallPtrSetIterator : public SmallPtrSetIteratorImpl { typedef PointerLikeTypeTraits PtrTraits; - + public: typedef PtrTy value_type; typedef PtrTy reference; typedef PtrTy pointer; typedef std::ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; - + explicit SmallPtrSetIterator(const void *const *BP, const void *const *E) : SmallPtrSetIteratorImpl(BP, E) {} @@ -233,36 +234,39 @@ template struct RoundUpToPowerOfTwo { enum { Val = RoundUpToPowerOfTwoH::Val }; }; - -/// 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 SmallPtrSet : public SmallPtrSetImplBase { - // Make sure that SmallSize is a power of two, round up if not. - enum { SmallSizePowTwo = RoundUpToPowerOfTwo::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 +class SmallPtrSetImpl : public SmallPtrSetImplBase { typedef PointerLikeTypeTraits PtrTraits; -public: - SmallPtrSet() : SmallPtrSetImplBase(SmallStorage, SmallSizePowTwo) {} - SmallPtrSet(const SmallPtrSet &that) : SmallPtrSetImplBase(SmallStorage, that) {} -#if LLVM_HAS_RVALUE_REFERENCES - SmallPtrSet(SmallPtrSet &&that) - : SmallPtrSetImplBase(SmallStorage, SmallSizePowTwo, std::move(that)) {} -#endif - template - SmallPtrSet(It I, It E) : SmallPtrSetImplBase(SmallStorage, SmallSizePowTwo) { - insert(I, E); - } + SmallPtrSetImpl(const SmallPtrSetImpl &) = delete; + +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: + typedef SmallPtrSetIterator iterator; + typedef SmallPtrSetIterator const_iterator; - /// insert - This returns true if the pointer was new to the set, false if it - /// was already in the set. - bool insert(PtrType Ptr) { - return insert_imp(PtrTraits::getAsVoidPointer(Ptr)); + /// Inserts Ptr if and only if there is no element in the container equal to + /// Ptr. The bool component of the returned pair is true if and only if the + /// insertion takes place, and the iterator component of the pair points to + /// the element equal to Ptr. + std::pair insert(PtrType Ptr) { + auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr)); + return std::make_pair(iterator(p.first, CurArray + CurArraySize), p.second); } /// erase - If the set contains the specified pointer, remove it and return @@ -272,7 +276,7 @@ public: } /// count - Return 1 if the specified pointer is in the set, 0 otherwise. - unsigned count(PtrType Ptr) const { + size_type count(PtrType Ptr) const { return count_imp(PtrTraits::getAsVoidPointer(Ptr)) ? 1 : 0; } @@ -282,37 +286,57 @@ public: insert(*I); } - typedef SmallPtrSetIterator iterator; - typedef SmallPtrSetIterator const_iterator; inline iterator begin() const { return iterator(CurArray, CurArray+CurArraySize); } inline iterator end() const { return iterator(CurArray+CurArraySize, CurArray+CurArraySize); } +}; + +/// 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 SmallPtrSet : public SmallPtrSetImpl { + typedef SmallPtrSetImpl BaseT; + + // Make sure that SmallSize is a power of two, round up if not. + enum { SmallSizePowTwo = RoundUpToPowerOfTwo::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 + SmallPtrSet(It I, It E) : BaseT(SmallStorage, SmallSizePowTwo) { + this->insert(I, E); + } SmallPtrSet & operator=(const SmallPtrSet &RHS) { if (&RHS != this) - CopyFrom(RHS); + this->CopyFrom(RHS); return *this; } -#if LLVM_HAS_RVALUE_REFERENCES SmallPtrSet& operator=(SmallPtrSet &&RHS) { if (&RHS != this) - MoveFrom(SmallSizePowTwo, std::move(RHS)); + this->MoveFrom(SmallSizePowTwo, std::move(RHS)); return *this; } -#endif /// swap - Swaps the elements of two sets. void swap(SmallPtrSet &RHS) { SmallPtrSetImplBase::swap(RHS); } }; - } namespace std {