X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FSupport%2FSmallPtrSet.cpp;h=ba00d903658ffe83c11fcd1970f91709126c3ecc;hb=42e4bdf2577946380ce1529d5716e48b33d4186d;hp=5c672375c6b74e37c0a2900f99d165ab5fcdc51b;hpb=1629a1fa87f8c32d6d33173d6d6e77dc4ed1ca4f;p=oota-llvm.git diff --git a/lib/Support/SmallPtrSet.cpp b/lib/Support/SmallPtrSet.cpp index 5c672375c6b..ba00d903658 100644 --- a/lib/Support/SmallPtrSet.cpp +++ b/lib/Support/SmallPtrSet.cpp @@ -14,12 +14,32 @@ #include "llvm/ADT/SmallPtrSet.h" #include "llvm/Support/MathExtras.h" +#include + using namespace llvm; -bool SmallPtrSetImpl::insert(void *Ptr) { +void SmallPtrSetImpl::shrink_and_clear() { + assert(!isSmall() && "Can't shrink a small set!"); + free(CurArray); + + // Reduce the number of buckets. + CurArraySize = NumElements > 16 ? 1 << (Log2_32_Ceil(NumElements) + 1) : 32; + NumElements = NumTombstones = 0; + + // Install the new array. Clear all the buckets to empty. + CurArray = (const void**)malloc(sizeof(void*) * (CurArraySize+1)); + assert(CurArray && "Failed to allocate memory?"); + memset(CurArray, -1, CurArraySize*sizeof(void*)); + + // The end pointer, always valid, is set to a valid element to help the + // iterator. + CurArray[CurArraySize] = 0; +} + +bool SmallPtrSetImpl::insert(const void * Ptr) { if (isSmall()) { // Check to see if it is already in the set. - for (void **APtr = SmallArray, **E = SmallArray+NumElements; + for (const void **APtr = SmallArray, **E = SmallArray+NumElements; APtr != E; ++APtr) if (*APtr == Ptr) return false; @@ -38,21 +58,21 @@ bool SmallPtrSetImpl::insert(void *Ptr) { Grow(); // Okay, we know we have space. Find a hash bucket. - void **Bucket = const_cast(FindBucketFor(Ptr)); + void **Bucket = const_cast(FindBucketFor((void*)Ptr)); if (*Bucket == Ptr) return false; // Already inserted, good. // Otherwise, insert it! if (*Bucket == getTombstoneMarker()) --NumTombstones; - *Bucket = Ptr; + *Bucket = (void*)Ptr; ++NumElements; // Track density. return true; } -bool SmallPtrSetImpl::erase(void *Ptr) { +bool SmallPtrSetImpl::erase(void * const Ptr) { if (isSmall()) { // Check to see if it is in the set. - for (void **APtr = SmallArray, **E = SmallArray+NumElements; + for (const void **APtr = SmallArray, **E = SmallArray+NumElements; APtr != E; ++APtr) if (*APtr == Ptr) { // If it is in the set, replace this element. @@ -76,12 +96,12 @@ bool SmallPtrSetImpl::erase(void *Ptr) { return true; } -void * const *SmallPtrSetImpl::FindBucketFor(void *Ptr) const { +const void * const *SmallPtrSetImpl::FindBucketFor(const void *Ptr) const { unsigned Bucket = Hash(Ptr); unsigned ArraySize = CurArraySize; unsigned ProbeAmt = 1; - void *const *Array = CurArray; - void *const *Tombstone = 0; + const void *const *Array = CurArray; + const void *const *Tombstone = 0; while (1) { // Found Ptr's bucket? if (Array[Bucket] == Ptr) @@ -110,11 +130,11 @@ void SmallPtrSetImpl::Grow() { unsigned OldSize = CurArraySize; unsigned NewSize = OldSize < 64 ? 128 : OldSize*2; - void **OldBuckets = CurArray; + const void **OldBuckets = CurArray; bool WasSmall = isSmall(); // Install the new array. Clear all the buckets to empty. - CurArray = (void**)malloc(sizeof(void*) * (NewSize+1)); + CurArray = (const void**)malloc(sizeof(void*) * (NewSize+1)); assert(CurArray && "Failed to allocate memory?"); CurArraySize = NewSize; memset(CurArray, -1, NewSize*sizeof(void*)); @@ -126,19 +146,19 @@ void SmallPtrSetImpl::Grow() { // Copy over all the elements. if (WasSmall) { // Small sets store their elements in order. - for (void **BucketPtr = OldBuckets, **E = OldBuckets+NumElements; + for (const void **BucketPtr = OldBuckets, **E = OldBuckets+NumElements; BucketPtr != E; ++BucketPtr) { - void *Elt = *BucketPtr; - *const_cast(FindBucketFor(Elt)) = Elt; + const void *Elt = *BucketPtr; + *const_cast(FindBucketFor(Elt)) = const_cast(Elt); } } else { // Copy over all valid entries. - for (void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize; + for (const void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize; BucketPtr != E; ++BucketPtr) { // Copy over the element if it is valid. - void *Elt = *BucketPtr; + const void *Elt = *BucketPtr; if (Elt != getTombstoneMarker() && Elt != getEmptyMarker()) - *const_cast(FindBucketFor(Elt)) = Elt; + *const_cast(FindBucketFor(Elt)) = const_cast(Elt); } free(OldBuckets); @@ -147,33 +167,23 @@ void SmallPtrSetImpl::Grow() { } SmallPtrSetImpl::SmallPtrSetImpl(const SmallPtrSetImpl& that) { - NumElements = that.NumElements; - NumTombstones = 0; + // If we're becoming small, prepare to insert into our stack space if (that.isSmall()) { - CurArraySize = that.CurArraySize; CurArray = &SmallArray[0]; - // Copy the entire contents of the array, including the -1's and the null - // terminator. - memcpy(CurArray, that.CurArray, sizeof(void*)*(CurArraySize+1)); + // Otherwise, allocate new heap space (unless we were the same size) } else { - CurArraySize = that.NumElements < 64 ? 128 : that.CurArraySize*2; - CurArray = (void**)malloc(sizeof(void*) * (CurArraySize+1)); + CurArray = (const void**)malloc(sizeof(void*) * (that.CurArraySize+1)); assert(CurArray && "Failed to allocate memory?"); - memset(CurArray, -1, CurArraySize*sizeof(void*)); - - // The end pointer, always valid, is set to a valid element to help the - // iterator. - CurArray[CurArraySize] = 0; - - // Copy over all valid entries. - for (void **BucketPtr = that.CurArray, **E = that.CurArray+that.CurArraySize; - BucketPtr != E; ++BucketPtr) { - // Copy over the element if it is valid. - void *Elt = *BucketPtr; - if (Elt != getTombstoneMarker() && Elt != getEmptyMarker()) - *const_cast(FindBucketFor(Elt)) = Elt; - } } + + // Copy over the new array size + CurArraySize = that.CurArraySize; + + // Copy over the contents from the other set + memcpy(CurArray, that.CurArray, sizeof(void*)*(CurArraySize+1)); + + NumElements = that.NumElements; + NumTombstones = that.NumTombstones; } /// CopyFrom - implement operator= from a smallptrset that has the same pointer @@ -182,15 +192,18 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { if (isSmall() && RHS.isSmall()) assert(CurArraySize == RHS.CurArraySize && "Cannot assign sets with different small sizes"); - NumElements = RHS.NumElements; - NumTombstones = RHS.NumTombstones; - + // If we're becoming small, prepare to insert into our stack space - if (RHS.isSmall()) + if (RHS.isSmall()) { + if (!isSmall()) + free(CurArray); CurArray = &SmallArray[0]; // Otherwise, allocate new heap space (unless we were the same size) - else if (CurArraySize != RHS.CurArraySize) { - CurArray = (void**)realloc(CurArray, sizeof(void*)*(RHS.CurArraySize+1)); + } else if (CurArraySize != RHS.CurArraySize) { + if (isSmall()) + CurArray = (const void**)malloc(sizeof(void*) * (RHS.CurArraySize+1)); + else + CurArray = (const void**)realloc(CurArray, sizeof(void*)*(RHS.CurArraySize+1)); assert(CurArray && "Failed to allocate memory?"); } @@ -199,4 +212,12 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { // Copy over the contents from the other set memcpy(CurArray, RHS.CurArray, sizeof(void*)*(CurArraySize+1)); + + NumElements = RHS.NumElements; + NumTombstones = RHS.NumTombstones; +} + +SmallPtrSetImpl::~SmallPtrSetImpl() { + if (!isSmall()) + free(CurArray); }