X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSmallPtrSet.h;h=7d00e9a073e78f4bb50f29861715fa225f257ee9;hb=f5fdf73238dfd923f33bcbbd397cff6752d9c41e;hp=e165d145578164e9e67912d2c91f52109f705930;hpb=7ed47a13356daed2a34cd2209a31f92552e3bdd8;p=oota-llvm.git diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index e165d145578..7d00e9a073e 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -17,10 +17,14 @@ #include #include +#include #include "llvm/Support/DataTypes.h" +#include "llvm/Support/PointerLikeTypeTraits.h" 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,6 +44,7 @@ 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'. @@ -48,7 +53,7 @@ protected: /// 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 unsigned NumElements; unsigned NumTombstones; @@ -56,8 +61,7 @@ protected: // Helper to copy construct a SmallPtrSet. SmallPtrSetImpl(const SmallPtrSetImpl& that); -public: - SmallPtrSetImpl(unsigned SmallSize) { + explicit SmallPtrSetImpl(unsigned SmallSize) { assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 && "Initial size must be a power of two!"); CurArray = &SmallArray[0]; @@ -68,41 +72,42 @@ public: 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,23 +117,23 @@ protected: return true; return false; } - + // Big set case. return *FindBucketFor(Ptr) == Ptr; } - + private: bool isSmall() const { return CurArray == &SmallArray[0]; } unsigned Hash(const void *Ptr) const { - return ((uintptr_t)Ptr >> 4) & (CurArraySize-1); + 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 operator=(const SmallPtrSetImpl &RHS); // DO NOT IMPLEMENT. protected: void CopyFrom(const SmallPtrSetImpl &RHS); @@ -140,17 +145,17 @@ class SmallPtrSetIteratorImpl { protected: const void *const *Bucket; public: - SmallPtrSetIteratorImpl(const void *const *BP) : Bucket(BP) { + 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,21 +170,30 @@ protected: /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet. template class SmallPtrSetIterator : public SmallPtrSetIteratorImpl { + typedef PointerLikeTypeTraits PtrTraits; + public: - SmallPtrSetIterator(const 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) + : 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; } @@ -209,7 +223,7 @@ template struct NextPowerOfTwo { enum { Val = NextPowerOfTwoH::Val }; }; - + /// SmallPtrSet - This class implements a set which is optimizer for holding /// SmallSize or less elements. This internally rounds up SmallSize to the next @@ -220,33 +234,40 @@ class SmallPtrSet : public SmallPtrSetImpl { // Make sure that SmallSize is a power of two, round up if not. enum { SmallSizePowTwo = NextPowerOfTwo::Val }; void *SmallArray[SmallSizePowTwo]; + typedef PointerLikeTypeTraits PtrTraits; public: SmallPtrSet() : SmallPtrSetImpl(NextPowerOfTwo::Val) {} SmallPtrSet(const SmallPtrSet &that) : SmallPtrSetImpl(that) {} - + template SmallPtrSet(It I, It E) : SmallPtrSetImpl(NextPowerOfTwo::Val) { 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 { @@ -255,7 +276,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&