X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSmallPtrSet.h;h=3bb883088c598d489f07534a446e096e6be93fb5;hb=b61054ff8f5568489109a0ccf2799307c3671309;hp=8b85a67afb78220869f23a5238fd650c6362a4ec;hpb=950a4c40b823cd4f09dc71be635229246dfd6cac;p=oota-llvm.git diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index 8b85a67afb7..3bb883088c5 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -15,12 +15,18 @@ #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 namespace llvm { +class SmallPtrSetIteratorImpl; + /// SmallPtrSetImpl - 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. @@ -40,69 +46,70 @@ namespace llvm { /// more. When this happens, the table is doubled in size. /// class SmallPtrSetImpl { + friend class SmallPtrSetIteratorImpl; protected: - /// CurArray - This is the current set of buckets. If it points to - /// SmallArray, then the set is in 'small mode'. + /// 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; - const void *SmallArray[1]; // Must be last ivar. // Helper to copy construct a SmallPtrSet. - SmallPtrSetImpl(const SmallPtrSetImpl& that); -public: - explicit SmallPtrSetImpl(unsigned SmallSize) { + SmallPtrSetImpl(const void **SmallStorage, const SmallPtrSetImpl& that); + explicit SmallPtrSetImpl(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(); - + +public: 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); - } - + 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; } - + 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); + } + /// 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); - + /// 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. @@ -112,25 +119,26 @@ protected: 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; } - unsigned Hash(const void *Ptr) const { - return ((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 operator=(const SmallPtrSetImpl &RHS); // DO NOT IMPLEMENT. + void Grow(unsigned NewSize); + + void operator=(const SmallPtrSetImpl &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 CopyFrom(const SmallPtrSetImpl &RHS); }; @@ -143,14 +151,14 @@ public: explicit SmallPtrSetIteratorImpl(const void *const *BP) : Bucket(BP) { 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 @@ -165,89 +173,105 @@ protected: /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet. 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) {} // Most methods provided by baseclass. - + const PtrTy operator*() const { - return static_cast(const_cast(*Bucket)); + 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 }; }; + - -/// SmallPtrSet - This class implements a set which is optimizer for holding +/// 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 }; - void *SmallArray[SmallSizePowTwo]; + 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]; + typedef PointerLikeTypeTraits PtrTraits; public: - SmallPtrSet() : SmallPtrSetImpl(NextPowerOfTwo::Val) {} - SmallPtrSet(const SmallPtrSet &that) : SmallPtrSetImpl(that) {} - + SmallPtrSet() : SmallPtrSetImpl(SmallStorage, SmallSizePowTwo) {} + SmallPtrSet(const SmallPtrSet &that) : SmallPtrSetImpl(SmallStorage, that) {} + template - SmallPtrSet(It I, It E) - : SmallPtrSetImpl(NextPowerOfTwo::Val) { + SmallPtrSet(It I, It E) : SmallPtrSetImpl(SmallStorage, SmallSizePowTwo) { insert(I, E); } - + /// 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(Ptr); } - + bool insert(PtrType Ptr) { + return insert_imp(PtrTraits::getAsVoidPointer(Ptr)); + } + /// erase - If the set contains the specified pointer, remove it and return /// true, otherwise return false. - bool erase(PtrType Ptr) { return erase_imp(Ptr); } - + bool erase(PtrType Ptr) { + 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(Ptr); } - + bool count(PtrType Ptr) const { + return count_imp(PtrTraits::getAsVoidPointer(Ptr)); + } + template void insert(IterT I, IterT E) { for (; I != E; ++I) insert(*I); } - + typedef SmallPtrSetIterator iterator; typedef SmallPtrSetIterator const_iterator; inline iterator begin() const { @@ -256,7 +280,7 @@ public: inline iterator end() const { return iterator(CurArray+CurArraySize); } - + // Allow assignment from any smallptrset with the same element type even if it // doesn't have the same smallsize. const SmallPtrSet& @@ -265,8 +289,20 @@ public: return *this; } + /// swap - Swaps the elements of two sets. + void swap(SmallPtrSet &RHS) { + SmallPtrSetImpl::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