X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSmallPtrSet.h;h=3d98e8fac43b61a36d965cca0509cbf4c3e34ef8;hb=44fb5881d8edf448d6231a5b8df583aecd6bcd42;hp=3bb883088c598d489f07534a446e096e6be93fb5;hpb=f630e49efc7bf3f1716b6daab3c2cc11a908754a;p=oota-llvm.git diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index 3bb883088c5..3d98e8fac43 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. // //===----------------------------------------------------------------------===// @@ -22,12 +22,13 @@ #include #include #include +#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. /// @@ -45,8 +46,9 @@ 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'. const void **SmallArray; @@ -54,30 +56,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 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, @@ -102,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 @@ -133,13 +133,15 @@ 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) = delete; + 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 @@ -147,9 +149,12 @@ 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 { @@ -164,8 +169,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; } }; @@ -174,20 +181,21 @@ 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) - : 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)); } @@ -226,33 +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 -/// 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 = RoundUpToPowerOfTwo::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 &) = 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 @@ -261,9 +275,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 @@ -272,29 +286,57 @@ 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); } +}; - // Allow assignment from any smallptrset with the same element type even if it - // doesn't have the same smallsize. - const SmallPtrSet& +/// 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) { - 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) { - SmallPtrSetImpl::swap(RHS); + SmallPtrSetImplBase::swap(RHS); } }; - } namespace std {