Index: llvm/trunk/include/llvm/ADT/SmallPtrSet.h =================================================================== --- llvm/trunk/include/llvm/ADT/SmallPtrSet.h +++ llvm/trunk/include/llvm/ADT/SmallPtrSet.h @@ -59,8 +59,11 @@ /// CurArraySize - The allocated size of CurArray, always a power of two. unsigned CurArraySize; - // If small, this is # elts allocated consecutively - unsigned NumElements; + /// Number of elements in CurArray that contain a value or are a tombstone. + /// If small, all these elements are at the beginning of CurArray and the rest + /// is uninitialized. + unsigned NumNonEmpty; + /// Number of tombstones in CurArray. unsigned NumTombstones; // Helpers to copy and move construct a SmallPtrSet. @@ -68,11 +71,11 @@ const SmallPtrSetImplBase &that); SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize, SmallPtrSetImplBase &&that); - explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize) : - SmallArray(SmallStorage), CurArray(SmallStorage), CurArraySize(SmallSize) { + explicit SmallPtrSetImplBase(const void **SmallStorage, unsigned SmallSize) + : SmallArray(SmallStorage), CurArray(SmallStorage), + CurArraySize(SmallSize), NumNonEmpty(0), NumTombstones(0) { assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 && "Initial size must be a power of two!"); - clear(); } ~SmallPtrSetImplBase() { if (!isSmall()) @@ -82,17 +85,19 @@ public: typedef unsigned size_type; bool LLVM_ATTRIBUTE_UNUSED_RESULT empty() const { return size() == 0; } - size_type size() const { return NumElements; } + size_type size() const { return NumNonEmpty - NumTombstones; } 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(); + if (!isSmall()) { + if (size() * 4 < CurArraySize && CurArraySize > 32) + return shrink_and_clear(); + // Fill the array with empty markers. + memset(CurArray, -1, CurArraySize * sizeof(void *)); + } - // Fill the array with empty markers. - memset(CurArray, -1, CurArraySize*sizeof(void*)); - NumElements = 0; + NumNonEmpty = 0; NumTombstones = 0; } @@ -104,21 +109,37 @@ return reinterpret_cast(-1); } + const void **EndPointer() const { + return isSmall() ? CurArray + NumNonEmpty : CurArray + CurArraySize; + } + /// 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. std::pair insert_imp(const void *Ptr) { if (isSmall()) { // Check to see if it is already in the set. - for (const void **APtr = SmallArray, **E = SmallArray+NumElements; - APtr != E; ++APtr) - if (*APtr == Ptr) + const void **LastTombstone = nullptr; + for (const void **APtr = SmallArray, **E = SmallArray + NumNonEmpty; + APtr != E; ++APtr) { + const void *Value = *APtr; + if (Value == Ptr) return std::make_pair(APtr, false); + if (Value == getTombstoneMarker()) + LastTombstone = APtr; + } + + // Did we find any tombstone marker? + if (LastTombstone != nullptr) { + *LastTombstone = Ptr; + --NumTombstones; + return std::make_pair(LastTombstone, true); + } // Nope, there isn't. If we stay small, just 'pushback' now. - if (NumElements < CurArraySize) { - SmallArray[NumElements++] = Ptr; - return std::make_pair(SmallArray + (NumElements - 1), true); + if (NumNonEmpty < CurArraySize) { + SmallArray[NumNonEmpty++] = Ptr; + return std::make_pair(SmallArray + (NumNonEmpty - 1), true); } // Otherwise, hit the big set case, which will call grow. } @@ -135,7 +156,7 @@ if (isSmall()) { // Linear search for the item. for (const void *const *APtr = SmallArray, - *const *E = SmallArray+NumElements; APtr != E; ++APtr) + *const *E = SmallArray + NumNonEmpty; APtr != E; ++APtr) if (*APtr == Ptr) return true; return false; @@ -295,7 +316,7 @@ /// the element equal to Ptr. std::pair insert(PtrType Ptr) { auto p = insert_imp(PtrTraits::getAsVoidPointer(Ptr)); - return std::make_pair(iterator(p.first, CurArray + CurArraySize), p.second); + return std::make_pair(iterator(p.first, EndPointer()), p.second); } /// erase - If the set contains the specified pointer, remove it and return @@ -316,10 +337,11 @@ } inline iterator begin() const { - return iterator(CurArray, CurArray+CurArraySize); + return iterator(CurArray, EndPointer()); } inline iterator end() const { - return iterator(CurArray+CurArraySize, CurArray+CurArraySize); + const void *const *End = EndPointer(); + return iterator(End, End); } }; Index: llvm/trunk/lib/Support/SmallPtrSet.cpp =================================================================== --- llvm/trunk/lib/Support/SmallPtrSet.cpp +++ llvm/trunk/lib/Support/SmallPtrSet.cpp @@ -25,8 +25,9 @@ free(CurArray); // Reduce the number of buckets. - CurArraySize = NumElements > 16 ? 1 << (Log2_32_Ceil(NumElements) + 1) : 32; - NumElements = NumTombstones = 0; + unsigned Size = size(); + CurArraySize = Size > 16 ? 1 << (Log2_32_Ceil(Size) + 1) : 32; + NumNonEmpty = NumTombstones = 0; // Install the new array. Clear all the buckets to empty. CurArray = (const void**)malloc(sizeof(void*) * CurArraySize); @@ -36,11 +37,10 @@ std::pair SmallPtrSetImplBase::insert_imp_big(const void *Ptr) { - if (LLVM_UNLIKELY(NumElements * 4 >= CurArraySize * 3)) { + if (LLVM_UNLIKELY(size() * 4 >= CurArraySize * 3)) { // If more than 3/4 of the array is full, grow. - Grow(CurArraySize < 64 ? 128 : CurArraySize*2); - } else if (LLVM_UNLIKELY(CurArraySize - (NumElements + NumTombstones) < - CurArraySize / 8)) { + Grow(CurArraySize < 64 ? 128 : CurArraySize * 2); + } else if (LLVM_UNLIKELY(CurArraySize - NumNonEmpty < CurArraySize / 8)) { // If fewer of 1/8 of the array is empty (meaning that many are filled with // tombstones), rehash. Grow(CurArraySize); @@ -54,21 +54,21 @@ // Otherwise, insert it! if (*Bucket == getTombstoneMarker()) --NumTombstones; + else + ++NumNonEmpty; // Track density. *Bucket = Ptr; - ++NumElements; // Track density. return std::make_pair(Bucket, true); } bool SmallPtrSetImplBase::erase_imp(const void * Ptr) { if (isSmall()) { // Check to see if it is in the set. - for (const void **APtr = SmallArray, **E = SmallArray+NumElements; - APtr != E; ++APtr) + for (const void **APtr = CurArray, **E = CurArray + NumNonEmpty; APtr != E; + ++APtr) if (*APtr == Ptr) { // If it is in the set, replace this element. - *APtr = E[-1]; - E[-1] = getEmptyMarker(); - --NumElements; + *APtr = getTombstoneMarker(); + ++NumTombstones; return true; } @@ -81,7 +81,6 @@ // Set this as a tombstone. *Bucket = getTombstoneMarker(); - --NumElements; ++NumTombstones; return true; } @@ -116,10 +115,8 @@ /// Grow - Allocate a larger backing store for the buckets and move it over. /// void SmallPtrSetImplBase::Grow(unsigned NewSize) { - // Allocate at twice as many buckets, but at least 128. - unsigned OldSize = CurArraySize; - const void **OldBuckets = CurArray; + const void **OldEnd = EndPointer(); bool WasSmall = isSmall(); // Install the new array. Clear all the buckets to empty. @@ -128,27 +125,18 @@ CurArraySize = NewSize; memset(CurArray, -1, NewSize*sizeof(void*)); - // Copy over all the elements. - if (WasSmall) { - // Small sets store their elements in order. - for (const void **BucketPtr = OldBuckets, **E = OldBuckets+NumElements; - BucketPtr != E; ++BucketPtr) { - const void *Elt = *BucketPtr; + // Copy over all valid entries. + for (const void **BucketPtr = OldBuckets; BucketPtr != OldEnd; ++BucketPtr) { + // Copy over the element if it is valid. + const void *Elt = *BucketPtr; + if (Elt != getTombstoneMarker() && Elt != getEmptyMarker()) *const_cast(FindBucketFor(Elt)) = const_cast(Elt); - } - } else { - // Copy over all valid entries. - for (const void **BucketPtr = OldBuckets, **E = OldBuckets+OldSize; - BucketPtr != E; ++BucketPtr) { - // Copy over the element if it is valid. - const void *Elt = *BucketPtr; - if (Elt != getTombstoneMarker() && Elt != getEmptyMarker()) - *const_cast(FindBucketFor(Elt)) = const_cast(Elt); - } + } + if (!WasSmall) free(OldBuckets); - NumTombstones = 0; - } + NumNonEmpty -= NumTombstones; + NumTombstones = 0; } SmallPtrSetImplBase::SmallPtrSetImplBase(const void **SmallStorage, @@ -209,9 +197,9 @@ CurArraySize = RHS.CurArraySize; // Copy over the contents from the other set - memcpy(CurArray, RHS.CurArray, sizeof(void*)*CurArraySize); + std::copy(RHS.CurArray, RHS.EndPointer(), CurArray); - NumElements = RHS.NumElements; + NumNonEmpty = RHS.NumNonEmpty; NumTombstones = RHS.NumTombstones; } @@ -229,7 +217,7 @@ if (RHS.isSmall()) { // Copy a small RHS rather than moving. CurArray = SmallArray; - memcpy(CurArray, RHS.CurArray, sizeof(void*)*RHS.CurArraySize); + std::copy(RHS.CurArray, RHS.CurArray + RHS.NumNonEmpty, CurArray); } else { CurArray = RHS.CurArray; RHS.CurArray = RHS.SmallArray; @@ -237,13 +225,13 @@ // Copy the rest of the trivial members. CurArraySize = RHS.CurArraySize; - NumElements = RHS.NumElements; + NumNonEmpty = RHS.NumNonEmpty; NumTombstones = RHS.NumTombstones; // Make the RHS small and empty. RHS.CurArraySize = SmallSize; assert(RHS.CurArray == RHS.SmallArray); - RHS.NumElements = 0; + RHS.NumNonEmpty = 0; RHS.NumTombstones = 0; } @@ -254,7 +242,7 @@ if (!this->isSmall() && !RHS.isSmall()) { std::swap(this->CurArray, RHS.CurArray); std::swap(this->CurArraySize, RHS.CurArraySize); - std::swap(this->NumElements, RHS.NumElements); + std::swap(this->NumNonEmpty, RHS.NumNonEmpty); std::swap(this->NumTombstones, RHS.NumTombstones); return; } @@ -264,35 +252,44 @@ // If only RHS is small, copy the small elements into LHS and move the pointer // from LHS to RHS. if (!this->isSmall() && RHS.isSmall()) { - std::copy(RHS.SmallArray, RHS.SmallArray+RHS.CurArraySize, - this->SmallArray); - std::swap(this->NumElements, RHS.NumElements); - std::swap(this->CurArraySize, RHS.CurArraySize); + assert(RHS.CurArray == RHS.SmallArray); + std::copy(RHS.CurArray, RHS.CurArray + RHS.NumNonEmpty, this->SmallArray); + std::swap(RHS.CurArraySize, this->CurArraySize); + std::swap(this->NumNonEmpty, RHS.NumNonEmpty); + std::swap(this->NumTombstones, RHS.NumTombstones); RHS.CurArray = this->CurArray; - RHS.NumTombstones = this->NumTombstones; this->CurArray = this->SmallArray; - this->NumTombstones = 0; return; } // If only LHS is small, copy the small elements into RHS and move the pointer // from RHS to LHS. if (this->isSmall() && !RHS.isSmall()) { - std::copy(this->SmallArray, this->SmallArray+this->CurArraySize, + assert(this->CurArray == this->SmallArray); + std::copy(this->CurArray, this->CurArray + this->NumNonEmpty, RHS.SmallArray); - std::swap(RHS.NumElements, this->NumElements); std::swap(RHS.CurArraySize, this->CurArraySize); + std::swap(RHS.NumNonEmpty, this->NumNonEmpty); + std::swap(RHS.NumTombstones, this->NumTombstones); this->CurArray = RHS.CurArray; - this->NumTombstones = RHS.NumTombstones; RHS.CurArray = RHS.SmallArray; - RHS.NumTombstones = 0; return; } // Both a small, just swap the small elements. assert(this->isSmall() && RHS.isSmall()); - assert(this->CurArraySize == RHS.CurArraySize); - std::swap_ranges(this->SmallArray, this->SmallArray+this->CurArraySize, + unsigned MinNonEmpty = std::min(this->NumNonEmpty, RHS.NumNonEmpty); + std::swap_ranges(this->SmallArray, this->SmallArray + MinNonEmpty, RHS.SmallArray); - std::swap(this->NumElements, RHS.NumElements); + if (this->NumNonEmpty > MinNonEmpty) { + std::copy(this->SmallArray + MinNonEmpty, + this->SmallArray + this->NumNonEmpty, + RHS.SmallArray + MinNonEmpty); + } else { + std::copy(RHS.SmallArray + MinNonEmpty, RHS.SmallArray + RHS.NumNonEmpty, + this->SmallArray + MinNonEmpty); + } + assert(this->CurArraySize == RHS.CurArraySize); + std::swap(this->NumNonEmpty, RHS.NumNonEmpty); + std::swap(this->NumTombstones, RHS.NumTombstones); }