X-Git-Url: http://plrg.eecs.uci.edu/git/?p=oota-llvm.git;a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSmallPtrSet.h;h=cb1c5e1fa96a464e511c72c9f2135f5f4bedaf1c;hp=5326d69bdf53ec5d8265106145dd0fff8d3717ee;hb=1b2c37ecce212d590f68cdd9a3c212c335a66069;hpb=2e502577ab3645ab5c54434671d299e35c2245cc diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index 5326d69bdf5..cb1c5e1fa96 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -8,24 +8,27 @@ //===----------------------------------------------------------------------===// // // 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. // //===----------------------------------------------------------------------===// #ifndef LLVM_ADT_SMALLPTRSET_H #define LLVM_ADT_SMALLPTRSET_H +#include "llvm/Support/Compiler.h" +#include "llvm/Support/DataTypes.h" +#include "llvm/Support/PointerLikeTypeTraits.h" #include +#include #include #include -#include "llvm/System/DataTypes.h" -#include "llvm/Support/PointerLikeTypeTraits.h" +#include 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. /// @@ -43,7 +46,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'. @@ -52,30 +55,28 @@ protected: /// then the set is in 'small mode'. const void **CurArray; /// CurArraySize - The allocated size of CurArray, always a power of two. - /// Note that CurArray points to an array that has CurArraySize+1 elements in - /// it, so that the end iterator actually points to valid memory. unsigned CurArraySize; - // If small, this is # elts allocated consequtively + // If small, this is # elts allocated consecutively 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!"); - // The end pointer, always valid, is set to a valid element to help the - // iterator. - CurArray[SmallSize] = 0; clear(); } - ~SmallPtrSetImpl(); + ~SmallPtrSetImplBase(); public: - bool empty() const { return size() == 0; } - unsigned size() const { return NumElements; } + typedef unsigned size_type; + bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return size() == 0; } + size_type size() const { return NumElements; } void clear() { // If the capacity of the array is huge, and the # elements used is small, @@ -100,7 +101,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 @@ -125,18 +126,20 @@ protected: private: bool isSmall() const { return CurArray == SmallArray; } - unsigned Hash(const void *Ptr) const { - return static_cast(((uintptr_t)Ptr >> 4) & (CurArraySize-1)); - } const void * const *FindBucketFor(const void *Ptr) const; void shrink_and_clear(); /// Grow - Allocate a larger backing store for the buckets and move it over. - void Grow(); + void Grow(unsigned NewSize); - void operator=(const SmallPtrSetImpl &RHS); // DO NOT IMPLEMENT. + void operator=(const SmallPtrSetImplBase &RHS) LLVM_DELETED_FUNCTION; protected: - void CopyFrom(const SmallPtrSetImpl &RHS); + /// 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); + void MoveFrom(unsigned SmallSize, SmallPtrSetImplBase &&RHS); }; /// SmallPtrSetIteratorImpl - This is the common base class shared between all @@ -144,9 +147,11 @@ protected: class SmallPtrSetIteratorImpl { protected: const void *const *Bucket; + const void *const *End; public: - explicit SmallPtrSetIteratorImpl(const void *const *BP) : Bucket(BP) { - AdvanceIfNotValid(); + explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E) + : Bucket(BP), End(E) { + AdvanceIfNotValid(); } bool operator==(const SmallPtrSetIteratorImpl &RHS) const { @@ -161,8 +166,10 @@ protected: /// that is. This is guaranteed to stop because the end() bucket is marked /// valid. void AdvanceIfNotValid() { - while (*Bucket == SmallPtrSetImpl::getEmptyMarker() || - *Bucket == SmallPtrSetImpl::getTombstoneMarker()) + assert(Bucket <= End); + while (Bucket != End && + (*Bucket == SmallPtrSetImplBase::getEmptyMarker() || + *Bucket == SmallPtrSetImplBase::getTombstoneMarker())) ++Bucket; } }; @@ -179,12 +186,13 @@ public: typedef std::ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; - explicit SmallPtrSetIterator(const void *const *BP) - : SmallPtrSetIteratorImpl(BP) {} + explicit SmallPtrSetIterator(const void *const *BP, const void *const *E) + : SmallPtrSetIteratorImpl(BP, E) {} // Most methods provided by baseclass. const PtrTy operator*() const { + assert(Bucket < End); return PtrTraits::getFromVoidPointer(const_cast(*Bucket)); } @@ -199,57 +207,63 @@ public: } }; -/// NextPowerOfTwo - This is a helper template that rounds N up to the next +/// RoundUpToPowerOfTwo - This is a helper template that rounds N up to the next /// power of two (which means N itself if N is already a power of two). template -struct NextPowerOfTwo; +struct RoundUpToPowerOfTwo; -/// NextPowerOfTwoH - If N is not a power of two, increase it. This is a helper -/// template used to implement NextPowerOfTwo. +/// RoundUpToPowerOfTwoH - If N is not a power of two, increase it. This is a +/// helper template used to implement RoundUpToPowerOfTwo. template -struct NextPowerOfTwoH { +struct RoundUpToPowerOfTwoH { enum { Val = N }; }; template -struct NextPowerOfTwoH { +struct RoundUpToPowerOfTwoH { enum { // We could just use NextVal = N+1, but this converges faster. N|(N-1) sets // the right-most zero bits to one all at once, e.g. 0b0011000 -> 0b0011111. - Val = NextPowerOfTwo<(N|(N-1)) + 1>::Val + Val = RoundUpToPowerOfTwo<(N|(N-1)) + 1>::Val }; }; template -struct NextPowerOfTwo { - enum { Val = NextPowerOfTwoH::Val }; +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 -/// SmallPtrSetImpl for details of the algorithm. -template -class SmallPtrSet : public SmallPtrSetImpl { - // Make sure that SmallSize is a power of two, round up if not. - enum { SmallSizePowTwo = NextPowerOfTwo::Val }; - /// SmallStorage - Fixed size storage used in 'small mode'. The extra element - /// ensures that the end iterator actually points to valid memory. - const void *SmallStorage[SmallSizePowTwo+1]; +/// \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() : SmallPtrSetImpl(SmallStorage, SmallSizePowTwo) {} - SmallPtrSet(const SmallPtrSet &that) : SmallPtrSetImpl(SmallStorage, that) {} - template - SmallPtrSet(It I, It E) : SmallPtrSetImpl(SmallStorage, SmallSizePowTwo) { - insert(I, E); - } + SmallPtrSetImpl(const SmallPtrSetImpl&) LLVM_DELETED_FUNCTION; +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) {} - /// 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)); +public: + typedef SmallPtrSetIterator iterator; + typedef SmallPtrSetIterator const_iterator; + + /// 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 @@ -258,9 +272,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 @@ -269,25 +283,65 @@ public: insert(*I); } - typedef SmallPtrSetIterator iterator; - typedef SmallPtrSetIterator const_iterator; inline iterator begin() const { - return iterator(CurArray); + return iterator(CurArray, CurArray+CurArraySize); } inline iterator end() const { - return iterator(CurArray+CurArraySize); + 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); } - // Allow assignment from any smallptrset with the same element type even if it - // doesn't have the same smallsize. - const SmallPtrSet& + SmallPtrSet & operator=(const SmallPtrSet &RHS) { - CopyFrom(RHS); + if (&RHS != this) + this->CopyFrom(RHS); + return *this; + } + + SmallPtrSet& + operator=(SmallPtrSet &&RHS) { + if (&RHS != this) + this->MoveFrom(SmallSizePowTwo, std::move(RHS)); return *this; } + /// swap - Swaps the elements of two sets. + void swap(SmallPtrSet &RHS) { + SmallPtrSetImplBase::swap(RHS); + } }; } +namespace std { + /// Implement std::swap in terms of SmallPtrSet swap. + template + inline void swap(llvm::SmallPtrSet &LHS, llvm::SmallPtrSet &RHS) { + LHS.swap(RHS); + } +} + #endif