X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSmallPtrSet.h;h=3d98e8fac43b61a36d965cca0509cbf4c3e34ef8;hb=82c835626fc509771e3927e2ca4886cf0f4245db;hp=27cc5535c1da18f90580bf9c4003911e6851bfc7;hpb=1629a1fa87f8c32d6d33173d6d6e77dc4ed1ca4f;p=oota-llvm.git diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index 27cc5535c1d..3d98e8fac43 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -2,26 +2,33 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by Chris Lattner and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // // 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 "llvm/Support/DataTypes.h" +#include +#include namespace llvm { -/// SmallPtrSetImpl - This is the common code shared among all the +class SmallPtrSetIteratorImpl; + +/// 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. /// @@ -39,124 +46,133 @@ namespace llvm { /// (-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: - /// CurArray - This is the current set of buckets. If it points to - /// SmallArray, then the set is in 'small mode'. - void **CurArray; + /// SmallArray - Points to a fixed size set of buckets, used in 'small mode'. + const void **SmallArray; + /// CurArray - This is the current set of buckets. If equal to SmallArray, + /// 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; - void *SmallArray[1]; // Must be last ivar. - // Helper to copy construct a SmallPtrSet. - SmallPtrSetImpl(const SmallPtrSetImpl& that); -public: - SmallPtrSetImpl(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!"); - CurArray = &SmallArray[0]; - CurArraySize = SmallSize; - // The end pointer, always valid, is set to a valid element to help the - // iterator. - CurArray[SmallSize] = 0; clear(); } - ~SmallPtrSetImpl() { - if (!isSmall()) - free(CurArray); - } - - bool empty() const { return size() == 0; } - unsigned size() const { return NumElements; } - - static void *getTombstoneMarker() { return reinterpret_cast(-2); } - static void *getEmptyMarker() { - // Note that -1 is chosen to make clear() efficiently implementable with - // memset and because it's not a valid pointer value. - return reinterpret_cast(-1); - } - + ~SmallPtrSetImplBase(); + +public: + 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, + // shrink the array. + if (!isSmall() && NumElements*4 < CurArraySize && CurArraySize > 32) + return shrink_and_clear(); + // Fill the array with empty markers. memset(CurArray, -1, CurArraySize*sizeof(void*)); NumElements = 0; NumTombstones = 0; } - - /// insert - This returns true if the pointer was new to the set, false if it - /// was already in the set. - bool insert(void *Ptr); - - template - void insert(IterT I, IterT E) { - for (; I != E; ++I) - insert((void*)*I); + +protected: + static void *getTombstoneMarker() { return reinterpret_cast(-2); } + static void *getEmptyMarker() { + // Note that -1 is chosen to make clear() efficiently implementable with + // memset and because it's not a valid pointer value. + return reinterpret_cast(-1); } - - /// erase - If the set contains the specified pointer, remove it and return - /// true, otherwise return false. - bool erase(void *Ptr); - - bool count(void *Ptr) const { + + /// 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. + 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 + /// that the derived class can check that the right type of pointer is passed + /// in. + bool erase_imp(const void * Ptr); + + bool count_imp(const void * Ptr) const { if (isSmall()) { // Linear search for the item. - for (void *const *APtr = SmallArray, *const *E = SmallArray+NumElements; - APtr != E; ++APtr) + for (const void *const *APtr = SmallArray, + *const *E = SmallArray+NumElements; APtr != E; ++APtr) if (*APtr == Ptr) return true; return false; } - + // Big set case. return *FindBucketFor(Ptr) == Ptr; } - + private: - bool isSmall() const { return CurArray == &SmallArray[0]; } + bool isSmall() const { return CurArray == SmallArray; } + + const void * const *FindBucketFor(const void *Ptr) const; + void shrink_and_clear(); - unsigned Hash(void *Ptr) const { - return ((uintptr_t)Ptr >> 4) & (CurArraySize-1); - } - void * const *FindBucketFor(void *Ptr) const; - /// Grow - Allocate a larger backing store for the buckets and move it over. - void Grow(); - - void operator=(const SmallPtrSetImpl &RHS); // DO NOT IMPLEMENT. + void Grow(unsigned NewSize); + + void operator=(const SmallPtrSetImplBase &RHS) = delete; + 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 /// instances of SmallPtrSetIterator. class SmallPtrSetIteratorImpl { protected: - void *const *Bucket; + const void *const *Bucket; + const void *const *End; + public: - SmallPtrSetIteratorImpl(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 { return Bucket == RHS.Bucket; } bool operator!=(const SmallPtrSetIteratorImpl &RHS) const { return Bucket != RHS.Bucket; } - + protected: /// AdvanceIfNotValid - If the current bucket isn't valid, advance to a bucket /// 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; } }; @@ -164,90 +180,171 @@ protected: /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet. template class SmallPtrSetIterator : public SmallPtrSetIteratorImpl { + typedef PointerLikeTypeTraits PtrTraits; + public: - SmallPtrSetIterator(void *const *BP) : SmallPtrSetIteratorImpl(BP) {} + 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) {} // Most methods provided by baseclass. - - PtrTy operator*() const { - return static_cast(*Bucket); + + const PtrTy operator*() const { + assert(Bucket < End); + return PtrTraits::getFromVoidPointer(const_cast(*Bucket)); } - + inline SmallPtrSetIterator& operator++() { // Preincrement ++Bucket; AdvanceIfNotValid(); return *this; } - + SmallPtrSetIterator operator++(int) { // Postincrement SmallPtrSetIterator tmp = *this; ++*this; return tmp; } }; -/// NextPowerOfTwo - This is a helper template that rounds N up to the next -/// power of two. +/// 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 }; }; +/// \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; + + 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) {} -/// SmallPtrSet - This class implements a set which is optimizer 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 }; - void *SmallArray[SmallSizePowTwo]; public: - SmallPtrSet() : SmallPtrSetImpl(NextPowerOfTwo::Val) {} - SmallPtrSet(const SmallPtrSet &that) : SmallPtrSetImpl(that) {} - - template - SmallPtrSet(It I, It E) - : SmallPtrSetImpl(NextPowerOfTwo::Val) { - insert(I, E); - } - 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 + /// true, otherwise return false. + bool erase(PtrType Ptr) { + return erase_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 + void insert(IterT I, IterT E) { + for (; I != E; ++I) + insert(*I); + } + 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