X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSmallPtrSet.h;h=f5af42dc4298b750ad6efe2868432135d1cbf050;hb=1f6efa3996dd1929fbc129203ce5009b620e6969;hp=a1ce7ba0dc5d364aa44c751a02c77687fedf80d5;hpb=c95dc987e9e369c1c63819dbc4f76ab9b913772c;p=oota-llvm.git diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index a1ce7ba0dc5..f5af42dc429 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -2,12 +2,13 @@ // // 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. +// This file defines the SmallPtrSet class. See the doxygen comment for +// SmallPtrSetImpl for more details on the algorithm used. // //===----------------------------------------------------------------------===// @@ -16,98 +17,145 @@ #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. +/// +/// Small sets use an array of pointers allocated in the SmallPtrSet object, +/// which is treated as a simple array of pointers. When a pointer is added to +/// the set, the array is scanned to see if the element already exists, if not +/// the element is 'pushed back' onto the array. If we run out of space in the +/// array, we grow into the 'large set' case. SmallSet should be used when the +/// sets are often small. In this case, no memory allocation is used, and only +/// light-weight and cache-efficient scanning is used. +/// +/// Large sets use a classic exponentially-probed hash table. Empty buckets are +/// represented with an illegal pointer value (-1) to allow null pointers to be +/// inserted. Tombstones are represented with another illegal pointer value +/// (-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 { + 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 unsigned NumElements; - void *SmallArray[1]; // Must be last ivar. -public: - SmallPtrSetImpl(unsigned SmallSize) { + unsigned NumTombstones; + + // Helper to copy construct a SmallPtrSet. + 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() { - if (!isSmall()) - delete[] CurArray; + ~SmallPtrSetImpl(); + +public: + bool empty() const { return size() == 0; } + unsigned 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; } - - bool isSmall() const { return CurArray == &SmallArray[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); } - - void clear() { - // Fill the array with empty markers. - memset(CurArray, -1, CurArraySize*sizeof(void*)); - NumElements = 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); - - 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. + 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. - 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: - unsigned Hash(void *Ptr) const { - return ((uintptr_t)Ptr >> 4) & (CurArraySize-1); + bool isSmall() const { return CurArray == SmallArray; } + + unsigned Hash(const void *Ptr) const { + return static_cast(((uintptr_t)Ptr >> 4) & (CurArraySize-1)); } - void * const *FindBucketFor(void *Ptr) const; - + 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); }; /// SmallPtrSetIteratorImpl - This is the common base class shared between all /// instances of SmallPtrSetIterator. class SmallPtrSetIteratorImpl { protected: - void *const *Bucket; + const void *const *Bucket; public: - SmallPtrSetIteratorImpl(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 @@ -122,34 +170,105 @@ 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) + : SmallPtrSetIteratorImpl(BP) {} // Most methods provided by baseclass. - - PtrTy operator*() const { - return static_cast(*Bucket); + + const PtrTy operator*() const { + return PtrTraits::getFromVoidPointer(const_cast(*Bucket)); } - + inline SmallPtrSetIterator& operator++() { // Preincrement ++Bucket; AdvanceIfNotValid(); return *this; } - + SmallPtrSetIterator operator++(int) { // Postincrement SmallPtrSetIterator tmp = *this; ++*this; return tmp; } }; +/// 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 RoundUpToPowerOfTwo; + +/// RoundUpToPowerOfTwoH - If N is not a power of two, increase it. This is a +/// helper template used to implement RoundUpToPowerOfTwo. +template +struct RoundUpToPowerOfTwoH { + enum { Val = N }; +}; +template +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 = RoundUpToPowerOfTwo<(N|(N-1)) + 1>::Val + }; +}; + +template +struct RoundUpToPowerOfTwo { + enum { Val = RoundUpToPowerOfTwoH::Val }; +}; + -/// SmallPtrSet - This class implements +/// 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 { - void *SmallArray[SmallSize]; + // 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]; + typedef PointerLikeTypeTraits PtrTraits; public: - SmallPtrSet() : SmallPtrSetImpl(SmallSize) {} - + SmallPtrSet() : SmallPtrSetImpl(SmallStorage, SmallSizePowTwo) {} + SmallPtrSet(const SmallPtrSet &that) : SmallPtrSetImpl(SmallStorage, that) {} + + template + 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(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(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)); + } + + template + void insert(IterT I, IterT E) { + for (; I != E; ++I) + insert(*I); + } + typedef SmallPtrSetIterator iterator; typedef SmallPtrSetIterator const_iterator; inline iterator begin() const { @@ -158,6 +277,15 @@ 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& + operator=(const SmallPtrSet &RHS) { + CopyFrom(RHS); + return *this; + } + }; }