X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=include%2Fllvm%2FADT%2FSmallPtrSet.h;h=db1583424bf85432821113c4c5d97663a0a4b2e6;hb=76d38384542e2f596e14eb8e80b8e1c6a2652fd1;hp=134a7da96c308b196ebe588eb499bae68fab951f;hpb=894d264f3ee965645656ddd6566acbe4d3a3ed55;p=oota-llvm.git diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index 134a7da96c3..db1583424bf 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -2,8 +2,8 @@ // // 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. // //===----------------------------------------------------------------------===// // @@ -17,9 +17,12 @@ #include #include +#include "llvm/Support/DataTypes.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. @@ -39,20 +42,24 @@ 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'. - void **CurArray; + 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; + const void *SmallArray[1]; // Must be last ivar. + + // Helper to copy construct a SmallPtrSet. + SmallPtrSetImpl(const SmallPtrSetImpl& that); + explicit SmallPtrSetImpl(unsigned SmallSize) { assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 && "Initial size must be a power of two!"); CurArray = &SmallArray[0]; @@ -62,78 +69,91 @@ public: 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; + } + +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); - - /// 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. + 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: bool isSmall() const { return CurArray == &SmallArray[0]; } - unsigned Hash(void *Ptr) const { - return ((uintptr_t)Ptr >> 4) & (CurArraySize-1); + 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 @@ -149,20 +169,21 @@ protected: template class SmallPtrSetIterator : public SmallPtrSetIteratorImpl { public: - SmallPtrSetIterator(void *const *BP) : SmallPtrSetIteratorImpl(BP) {} + 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 static_cast(const_cast(*Bucket)); } - + inline SmallPtrSetIterator& operator++() { // Preincrement ++Bucket; AdvanceIfNotValid(); return *this; } - + SmallPtrSetIterator operator++(int) { // Postincrement SmallPtrSetIterator tmp = *this; ++*this; return tmp; } @@ -184,8 +205,7 @@ struct NextPowerOfTwoH { 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. - NextVal = (N|(N-1)) + 1, - Val = NextPowerOfTwo::Val + Val = NextPowerOfTwo<(N|(N-1)) + 1>::Val }; }; @@ -206,7 +226,31 @@ class SmallPtrSet : public SmallPtrSetImpl { 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); + } + + /// 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); } + + /// erase - If the set contains the specified pointer, remove it and return + /// true, otherwise return false. + bool erase(PtrType Ptr) { return erase_imp(Ptr); } + + /// count - Return true if the specified pointer is in the set. + bool count(PtrType Ptr) const { return count_imp(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 { @@ -215,6 +259,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; + } + }; }