X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSmallPtrSet.h;h=47af22884dd9c35fda264692d2515c1f806c08f7;hb=1717f3af087e44d2c4b7fe2b35abc29a33d6d315;hp=f73a4a9bc4ca1eba06476fd11478cb0af50bef9a;hpb=34cd4a484e532cc463fd5a4bf59b88d13c5467c1;p=oota-llvm.git diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index f73a4a9bc4c..47af22884dd 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -20,6 +20,33 @@ #include "llvm/Support/DataTypes.h" namespace llvm { + +/// PointerLikeTypeInfo - This is a traits object that is used to handle pointer +/// types and things that are just wrappers for pointers as a uniform entity. +template +class PointerLikeTypeInfo { + //getAsVoidPointer/getFromVoidPointer +}; + +// Provide PointerLikeTypeInfo for all pointers. +template +class PointerLikeTypeInfo { +public: + static inline void *getAsVoidPointer(T* P) { return P; } + static inline T *getFromVoidPointer(void *P) { + return static_cast(P); + } +}; +template +class PointerLikeTypeInfo { +public: + static inline const void *getAsVoidPointer(const T* P) { return P; } + static inline const T *getFromVoidPointer(const void *P) { + return static_cast(P); + } +}; + +class SmallPtrSetIteratorImpl; /// SmallPtrSetImpl - This is the common code shared among all the /// SmallPtrSet<>'s, which is almost everything. SmallPtrSet has two modes, one @@ -40,6 +67,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 +76,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,7 +84,6 @@ protected: // Helper to copy construct a SmallPtrSet. SmallPtrSetImpl(const SmallPtrSetImpl& that); -public: explicit SmallPtrSetImpl(unsigned SmallSize) { assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 && "Initial size must be a power of two!"); @@ -68,41 +95,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,11 +140,11 @@ protected: return true; return false; } - + // Big set case. return *FindBucketFor(Ptr) == Ptr; } - + private: bool isSmall() const { return CurArray == &SmallArray[0]; } @@ -125,10 +153,10 @@ private: } 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); @@ -143,14 +171,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,22 +193,23 @@ protected: /// SmallPtrSetIterator - This implements a const_iterator for SmallPtrSet. template class SmallPtrSetIterator : public SmallPtrSetIteratorImpl { + typedef PointerLikeTypeInfo PtrTraits; public: 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; } @@ -210,7 +239,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 @@ -221,33 +250,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 PointerLikeTypeInfo 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 { @@ -256,7 +292,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&