From 617330909f0c26a3f2ab8601a029b9bdca48aa61 Mon Sep 17 00:00:00 2001 From: Jean-Luc Duprat Date: Fri, 29 Mar 2013 05:45:22 +0000 Subject: Fix allocations of SmallVector and SmallPtrSet so they are more prone to being power-of-two sized. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@178332 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Support/SmallPtrSet.cpp | 24 ++++++++---------------- 1 file changed, 8 insertions(+), 16 deletions(-) (limited to 'lib/Support/SmallPtrSet.cpp') diff --git a/lib/Support/SmallPtrSet.cpp b/lib/Support/SmallPtrSet.cpp index 3b53e9ff49..f0fed7792c 100644 --- a/lib/Support/SmallPtrSet.cpp +++ b/lib/Support/SmallPtrSet.cpp @@ -29,13 +29,9 @@ void SmallPtrSetImpl::shrink_and_clear() { NumElements = NumTombstones = 0; // Install the new array. Clear all the buckets to empty. - CurArray = (const void**)malloc(sizeof(void*) * (CurArraySize+1)); + CurArray = (const void**)malloc(sizeof(void*) * CurArraySize); 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_imp(const void * Ptr) { @@ -139,15 +135,11 @@ void SmallPtrSetImpl::Grow(unsigned NewSize) { bool WasSmall = isSmall(); // Install the new array. Clear all the buckets to empty. - CurArray = (const void**)malloc(sizeof(void*) * (NewSize+1)); + CurArray = (const void**)malloc(sizeof(void*) * NewSize); assert(CurArray && "Failed to allocate memory?"); CurArraySize = NewSize; memset(CurArray, -1, NewSize*sizeof(void*)); - // The end pointer, always valid, is set to a valid element to help the - // iterator. - CurArray[NewSize] = 0; - // Copy over all the elements. if (WasSmall) { // Small sets store their elements in order. @@ -180,7 +172,7 @@ SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage, CurArray = SmallArray; // Otherwise, allocate new heap space (unless we were the same size) } else { - CurArray = (const void**)malloc(sizeof(void*) * (that.CurArraySize+1)); + CurArray = (const void**)malloc(sizeof(void*) * that.CurArraySize); assert(CurArray && "Failed to allocate memory?"); } @@ -188,7 +180,7 @@ SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage, CurArraySize = that.CurArraySize; // Copy over the contents from the other set - memcpy(CurArray, that.CurArray, sizeof(void*)*(CurArraySize+1)); + memcpy(CurArray, that.CurArray, sizeof(void*)*CurArraySize); NumElements = that.NumElements; NumTombstones = that.NumTombstones; @@ -200,7 +192,7 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { if (isSmall() && RHS.isSmall()) assert(CurArraySize == RHS.CurArraySize && "Cannot assign sets with different small sizes"); - + // If we're becoming small, prepare to insert into our stack space if (RHS.isSmall()) { if (!isSmall()) @@ -209,9 +201,9 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { // Otherwise, allocate new heap space (unless we were the same size) } else if (CurArraySize != RHS.CurArraySize) { if (isSmall()) - CurArray = (const void**)malloc(sizeof(void*) * (RHS.CurArraySize+1)); + CurArray = (const void**)malloc(sizeof(void*) * RHS.CurArraySize); else - CurArray = (const void**)realloc(CurArray, sizeof(void*)*(RHS.CurArraySize+1)); + CurArray = (const void**)realloc(CurArray, sizeof(void*)*RHS.CurArraySize); assert(CurArray && "Failed to allocate memory?"); } @@ -219,7 +211,7 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { CurArraySize = RHS.CurArraySize; // Copy over the contents from the other set - memcpy(CurArray, RHS.CurArray, sizeof(void*)*(CurArraySize+1)); + memcpy(CurArray, RHS.CurArray, sizeof(void*)*CurArraySize); NumElements = RHS.NumElements; NumTombstones = RHS.NumTombstones; -- cgit v1.2.3-70-g09d2 From ef484a376cce3729b45ad86eab5724aa83a61823 Mon Sep 17 00:00:00 2001 From: Rafael Espindola Date: Fri, 29 Mar 2013 07:11:21 +0000 Subject: Revert "Fix allocations of SmallVector and SmallPtrSet so they are more prone to" This reverts commit 617330909f0c26a3f2ab8601a029b9bdca48aa61. It broke the bots: /home/clangbuild2/clang-ppc64-2/llvm.src/unittests/ADT/SmallVectorTest.cpp:150: PushPopTest /home/clangbuild2/clang-ppc64-2/llvm.src/unittests/ADT/SmallVectorTest.cpp:118: Failure Value of: v[i].getValue() Actual: 0 Expected: value Which is: 2 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@178334 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/SmallPtrSet.h | 31 +++++++++++----------- include/llvm/ADT/SmallVector.h | 4 +-- lib/Support/SmallPtrSet.cpp | 24 +++++++++++------ unittests/ADT/SmallPtrSetTest.cpp | 55 --------------------------------------- 4 files changed, 33 insertions(+), 81 deletions(-) (limited to 'lib/Support/SmallPtrSet.cpp') diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index 15ec619a36..3bb883088c 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -54,6 +54,8 @@ protected: /// 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 consecutively @@ -66,6 +68,9 @@ protected: SmallArray(SmallStorage), CurArray(SmallStorage), CurArraySize(SmallSize) { assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 && "Initial size must be a power of two!"); + // The end pointer, always valid, is set to a valid element to help the + // iterator. + CurArray[SmallSize] = 0; clear(); } ~SmallPtrSetImpl(); @@ -142,11 +147,9 @@ protected: class SmallPtrSetIteratorImpl { protected: const void *const *Bucket; - const void *const *End; public: - explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E) - : Bucket(BP), End(E) { - AdvanceIfNotValid(); + explicit SmallPtrSetIteratorImpl(const void *const *BP) : Bucket(BP) { + AdvanceIfNotValid(); } bool operator==(const SmallPtrSetIteratorImpl &RHS) const { @@ -161,10 +164,8 @@ protected: /// that is. This is guaranteed to stop because the end() bucket is marked /// valid. void AdvanceIfNotValid() { - assert(Bucket <= End); - while (Bucket != End && - (*Bucket == SmallPtrSetImpl::getEmptyMarker() || - *Bucket == SmallPtrSetImpl::getTombstoneMarker())) + while (*Bucket == SmallPtrSetImpl::getEmptyMarker() || + *Bucket == SmallPtrSetImpl::getTombstoneMarker()) ++Bucket; } }; @@ -181,13 +182,12 @@ public: typedef std::ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; - explicit SmallPtrSetIterator(const void *const *BP, const void *const *E) - : SmallPtrSetIteratorImpl(BP, E) {} + explicit SmallPtrSetIterator(const void *const *BP) + : SmallPtrSetIteratorImpl(BP) {} // Most methods provided by baseclass. const PtrTy operator*() const { - assert(Bucket < End); return PtrTraits::getFromVoidPointer(const_cast(*Bucket)); } @@ -236,8 +236,9 @@ template class SmallPtrSet : public SmallPtrSetImpl { // 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'. - const void *SmallStorage[SmallSizePowTwo]; + /// 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(SmallStorage, SmallSizePowTwo) {} @@ -274,10 +275,10 @@ public: typedef SmallPtrSetIterator iterator; typedef SmallPtrSetIterator const_iterator; inline iterator begin() const { - return iterator(CurArray, CurArray+CurArraySize); + return iterator(CurArray); } inline iterator end() const { - return iterator(CurArray+CurArraySize, CurArray+CurArraySize); + return iterator(CurArray+CurArraySize); } // Allow assignment from any smallptrset with the same element type even if it diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h index 6ea8de511d..9167f87218 100644 --- a/include/llvm/ADT/SmallVector.h +++ b/include/llvm/ADT/SmallVector.h @@ -16,7 +16,6 @@ #include "llvm/Support/AlignOf.h" #include "llvm/Support/Compiler.h" -#include "llvm/Support/MathExtras.h" #include "llvm/Support/type_traits.h" #include #include @@ -268,8 +267,7 @@ template void SmallVectorTemplateBase::grow(size_t MinSize) { size_t CurCapacity = this->capacity(); size_t CurSize = this->size(); - // Always grow, even from zero. - size_t NewCapacity = NextPowerOf2(2*CurCapacity+(CurCapacity==0)); + size_t NewCapacity = 2*CurCapacity + 1; // Always grow, even from zero. if (NewCapacity < MinSize) NewCapacity = MinSize; T *NewElts = static_cast(malloc(NewCapacity*sizeof(T))); diff --git a/lib/Support/SmallPtrSet.cpp b/lib/Support/SmallPtrSet.cpp index f0fed7792c..3b53e9ff49 100644 --- a/lib/Support/SmallPtrSet.cpp +++ b/lib/Support/SmallPtrSet.cpp @@ -29,9 +29,13 @@ void SmallPtrSetImpl::shrink_and_clear() { NumElements = NumTombstones = 0; // Install the new array. Clear all the buckets to empty. - CurArray = (const void**)malloc(sizeof(void*) * CurArraySize); + 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_imp(const void * Ptr) { @@ -135,11 +139,15 @@ void SmallPtrSetImpl::Grow(unsigned NewSize) { bool WasSmall = isSmall(); // Install the new array. Clear all the buckets to empty. - CurArray = (const void**)malloc(sizeof(void*) * NewSize); + CurArray = (const void**)malloc(sizeof(void*) * (NewSize+1)); assert(CurArray && "Failed to allocate memory?"); CurArraySize = NewSize; memset(CurArray, -1, NewSize*sizeof(void*)); + // The end pointer, always valid, is set to a valid element to help the + // iterator. + CurArray[NewSize] = 0; + // Copy over all the elements. if (WasSmall) { // Small sets store their elements in order. @@ -172,7 +180,7 @@ SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage, CurArray = SmallArray; // Otherwise, allocate new heap space (unless we were the same size) } else { - CurArray = (const void**)malloc(sizeof(void*) * that.CurArraySize); + CurArray = (const void**)malloc(sizeof(void*) * (that.CurArraySize+1)); assert(CurArray && "Failed to allocate memory?"); } @@ -180,7 +188,7 @@ SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage, CurArraySize = that.CurArraySize; // Copy over the contents from the other set - memcpy(CurArray, that.CurArray, sizeof(void*)*CurArraySize); + memcpy(CurArray, that.CurArray, sizeof(void*)*(CurArraySize+1)); NumElements = that.NumElements; NumTombstones = that.NumTombstones; @@ -192,7 +200,7 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { if (isSmall() && RHS.isSmall()) assert(CurArraySize == RHS.CurArraySize && "Cannot assign sets with different small sizes"); - + // If we're becoming small, prepare to insert into our stack space if (RHS.isSmall()) { if (!isSmall()) @@ -201,9 +209,9 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { // Otherwise, allocate new heap space (unless we were the same size) } else if (CurArraySize != RHS.CurArraySize) { if (isSmall()) - CurArray = (const void**)malloc(sizeof(void*) * RHS.CurArraySize); + CurArray = (const void**)malloc(sizeof(void*) * (RHS.CurArraySize+1)); else - CurArray = (const void**)realloc(CurArray, sizeof(void*)*RHS.CurArraySize); + CurArray = (const void**)realloc(CurArray, sizeof(void*)*(RHS.CurArraySize+1)); assert(CurArray && "Failed to allocate memory?"); } @@ -211,7 +219,7 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { CurArraySize = RHS.CurArraySize; // Copy over the contents from the other set - memcpy(CurArray, RHS.CurArray, sizeof(void*)*CurArraySize); + memcpy(CurArray, RHS.CurArray, sizeof(void*)*(CurArraySize+1)); NumElements = RHS.NumElements; NumTombstones = RHS.NumTombstones; diff --git a/unittests/ADT/SmallPtrSetTest.cpp b/unittests/ADT/SmallPtrSetTest.cpp index f85d7c941e..9114875e00 100644 --- a/unittests/ADT/SmallPtrSetTest.cpp +++ b/unittests/ADT/SmallPtrSetTest.cpp @@ -17,61 +17,6 @@ using namespace llvm; // SmallPtrSet swapping test. -TEST(SmallPtrSetTest, GrowthTest) { - int i; - int buf[8]; - for(i=0; i<8; ++i) buf[i]=0; - - - SmallPtrSet s; - typedef SmallPtrSet::iterator iter; - - s.insert(&buf[0]); - s.insert(&buf[1]); - s.insert(&buf[2]); - s.insert(&buf[3]); - EXPECT_EQ(4U, s.size()); - - i = 0; - for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) - (**I)++; - EXPECT_EQ(4, i); - for(i=0; i<8; ++i) - EXPECT_EQ(i<4?1:0,buf[i]); - - s.insert(&buf[4]); - s.insert(&buf[5]); - s.insert(&buf[6]); - s.insert(&buf[7]); - - i = 0; - for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) - (**I)++; - EXPECT_EQ(8, i); - s.erase(&buf[4]); - s.erase(&buf[5]); - s.erase(&buf[6]); - s.erase(&buf[7]); - EXPECT_EQ(4U, s.size()); - - i = 0; - for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) - (**I)++; - EXPECT_EQ(4, i); - for(i=0; i<8; ++i) - EXPECT_EQ(i<4?3:1,buf[i]); - - s.clear(); - for(i=0; i<8; ++i) buf[i]=0; - for(i=0; i<128; ++i) s.insert(&buf[i%8]); // test repeated entires - EXPECT_EQ(8U, s.size()); - for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) - (**I)++; - for(i=0; i<8; ++i) - EXPECT_EQ(1,buf[i]); -} - - TEST(SmallPtrSetTest, SwapTest) { int buf[10]; -- cgit v1.2.3-70-g09d2 From e1e9366281a98cd06b61d5d7e136ce2b1a433ba6 Mon Sep 17 00:00:00 2001 From: Jean-Luc Duprat Date: Fri, 29 Mar 2013 22:07:12 +0000 Subject: SmallVector and SmallPtrSet allocations now power-of-two aligned. This time tested on both OSX and Linux. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@178377 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/SmallPtrSet.h | 31 +++++++++++----------- include/llvm/ADT/SmallVector.h | 4 ++- lib/Support/SmallPtrSet.cpp | 24 ++++++----------- unittests/ADT/SmallPtrSetTest.cpp | 55 +++++++++++++++++++++++++++++++++++++++ 4 files changed, 81 insertions(+), 33 deletions(-) (limited to 'lib/Support/SmallPtrSet.cpp') diff --git a/include/llvm/ADT/SmallPtrSet.h b/include/llvm/ADT/SmallPtrSet.h index 3bb883088c..8c7304197f 100644 --- a/include/llvm/ADT/SmallPtrSet.h +++ b/include/llvm/ADT/SmallPtrSet.h @@ -54,8 +54,6 @@ protected: /// 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 consecutively @@ -68,9 +66,6 @@ protected: SmallArray(SmallStorage), CurArray(SmallStorage), CurArraySize(SmallSize) { assert(SmallSize && (SmallSize & (SmallSize-1)) == 0 && "Initial size must be a power of two!"); - // The end pointer, always valid, is set to a valid element to help the - // iterator. - CurArray[SmallSize] = 0; clear(); } ~SmallPtrSetImpl(); @@ -147,9 +142,11 @@ protected: class SmallPtrSetIteratorImpl { protected: const void *const *Bucket; + const void *const *End; public: - explicit SmallPtrSetIteratorImpl(const void *const *BP) : Bucket(BP) { - AdvanceIfNotValid(); + explicit SmallPtrSetIteratorImpl(const void *const *BP, const void*const *E) + : Bucket(BP), End(E) { + AdvanceIfNotValid(); } bool operator==(const SmallPtrSetIteratorImpl &RHS) const { @@ -164,8 +161,10 @@ protected: /// that is. This is guaranteed to stop because the end() bucket is marked /// valid. void AdvanceIfNotValid() { - while (*Bucket == SmallPtrSetImpl::getEmptyMarker() || - *Bucket == SmallPtrSetImpl::getTombstoneMarker()) + assert(Bucket <= End); + while (Bucket != End && + (*Bucket == SmallPtrSetImpl::getEmptyMarker() || + *Bucket == SmallPtrSetImpl::getTombstoneMarker())) ++Bucket; } }; @@ -182,12 +181,13 @@ public: typedef std::ptrdiff_t difference_type; typedef std::forward_iterator_tag iterator_category; - explicit SmallPtrSetIterator(const void *const *BP) - : SmallPtrSetIteratorImpl(BP) {} + explicit SmallPtrSetIterator(const void *const *BP, const void *const *E) + : SmallPtrSetIteratorImpl(BP, E) {} // Most methods provided by baseclass. const PtrTy operator*() const { + assert(Bucket < End); return PtrTraits::getFromVoidPointer(const_cast(*Bucket)); } @@ -236,9 +236,8 @@ template class SmallPtrSet : public SmallPtrSetImpl { // 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]; + /// SmallStorage - Fixed size storage used in 'small mode'. + const void *SmallStorage[SmallSizePowTwo]; typedef PointerLikeTypeTraits PtrTraits; public: SmallPtrSet() : SmallPtrSetImpl(SmallStorage, SmallSizePowTwo) {} @@ -275,10 +274,10 @@ public: typedef SmallPtrSetIterator iterator; typedef SmallPtrSetIterator const_iterator; inline iterator begin() const { - return iterator(CurArray); + return iterator(CurArray, CurArray+CurArraySize); } inline iterator end() const { - return iterator(CurArray+CurArraySize); + return iterator(CurArray+CurArraySize, CurArray+CurArraySize); } // Allow assignment from any smallptrset with the same element type even if it diff --git a/include/llvm/ADT/SmallVector.h b/include/llvm/ADT/SmallVector.h index 9167f87218..7ba0a714bf 100644 --- a/include/llvm/ADT/SmallVector.h +++ b/include/llvm/ADT/SmallVector.h @@ -16,6 +16,7 @@ #include "llvm/Support/AlignOf.h" #include "llvm/Support/Compiler.h" +#include "llvm/Support/MathExtras.h" #include "llvm/Support/type_traits.h" #include #include @@ -267,7 +268,8 @@ template void SmallVectorTemplateBase::grow(size_t MinSize) { size_t CurCapacity = this->capacity(); size_t CurSize = this->size(); - size_t NewCapacity = 2*CurCapacity + 1; // Always grow, even from zero. + // Always grow, even from zero. + size_t NewCapacity = size_t(NextPowerOf2(CurCapacity+2)); if (NewCapacity < MinSize) NewCapacity = MinSize; T *NewElts = static_cast(malloc(NewCapacity*sizeof(T))); diff --git a/lib/Support/SmallPtrSet.cpp b/lib/Support/SmallPtrSet.cpp index 3b53e9ff49..f0fed7792c 100644 --- a/lib/Support/SmallPtrSet.cpp +++ b/lib/Support/SmallPtrSet.cpp @@ -29,13 +29,9 @@ void SmallPtrSetImpl::shrink_and_clear() { NumElements = NumTombstones = 0; // Install the new array. Clear all the buckets to empty. - CurArray = (const void**)malloc(sizeof(void*) * (CurArraySize+1)); + CurArray = (const void**)malloc(sizeof(void*) * CurArraySize); 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_imp(const void * Ptr) { @@ -139,15 +135,11 @@ void SmallPtrSetImpl::Grow(unsigned NewSize) { bool WasSmall = isSmall(); // Install the new array. Clear all the buckets to empty. - CurArray = (const void**)malloc(sizeof(void*) * (NewSize+1)); + CurArray = (const void**)malloc(sizeof(void*) * NewSize); assert(CurArray && "Failed to allocate memory?"); CurArraySize = NewSize; memset(CurArray, -1, NewSize*sizeof(void*)); - // The end pointer, always valid, is set to a valid element to help the - // iterator. - CurArray[NewSize] = 0; - // Copy over all the elements. if (WasSmall) { // Small sets store their elements in order. @@ -180,7 +172,7 @@ SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage, CurArray = SmallArray; // Otherwise, allocate new heap space (unless we were the same size) } else { - CurArray = (const void**)malloc(sizeof(void*) * (that.CurArraySize+1)); + CurArray = (const void**)malloc(sizeof(void*) * that.CurArraySize); assert(CurArray && "Failed to allocate memory?"); } @@ -188,7 +180,7 @@ SmallPtrSetImpl::SmallPtrSetImpl(const void **SmallStorage, CurArraySize = that.CurArraySize; // Copy over the contents from the other set - memcpy(CurArray, that.CurArray, sizeof(void*)*(CurArraySize+1)); + memcpy(CurArray, that.CurArray, sizeof(void*)*CurArraySize); NumElements = that.NumElements; NumTombstones = that.NumTombstones; @@ -200,7 +192,7 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { if (isSmall() && RHS.isSmall()) assert(CurArraySize == RHS.CurArraySize && "Cannot assign sets with different small sizes"); - + // If we're becoming small, prepare to insert into our stack space if (RHS.isSmall()) { if (!isSmall()) @@ -209,9 +201,9 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { // Otherwise, allocate new heap space (unless we were the same size) } else if (CurArraySize != RHS.CurArraySize) { if (isSmall()) - CurArray = (const void**)malloc(sizeof(void*) * (RHS.CurArraySize+1)); + CurArray = (const void**)malloc(sizeof(void*) * RHS.CurArraySize); else - CurArray = (const void**)realloc(CurArray, sizeof(void*)*(RHS.CurArraySize+1)); + CurArray = (const void**)realloc(CurArray, sizeof(void*)*RHS.CurArraySize); assert(CurArray && "Failed to allocate memory?"); } @@ -219,7 +211,7 @@ void SmallPtrSetImpl::CopyFrom(const SmallPtrSetImpl &RHS) { CurArraySize = RHS.CurArraySize; // Copy over the contents from the other set - memcpy(CurArray, RHS.CurArray, sizeof(void*)*(CurArraySize+1)); + memcpy(CurArray, RHS.CurArray, sizeof(void*)*CurArraySize); NumElements = RHS.NumElements; NumTombstones = RHS.NumTombstones; diff --git a/unittests/ADT/SmallPtrSetTest.cpp b/unittests/ADT/SmallPtrSetTest.cpp index 9114875e00..f85d7c941e 100644 --- a/unittests/ADT/SmallPtrSetTest.cpp +++ b/unittests/ADT/SmallPtrSetTest.cpp @@ -17,6 +17,61 @@ using namespace llvm; // SmallPtrSet swapping test. +TEST(SmallPtrSetTest, GrowthTest) { + int i; + int buf[8]; + for(i=0; i<8; ++i) buf[i]=0; + + + SmallPtrSet s; + typedef SmallPtrSet::iterator iter; + + s.insert(&buf[0]); + s.insert(&buf[1]); + s.insert(&buf[2]); + s.insert(&buf[3]); + EXPECT_EQ(4U, s.size()); + + i = 0; + for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) + (**I)++; + EXPECT_EQ(4, i); + for(i=0; i<8; ++i) + EXPECT_EQ(i<4?1:0,buf[i]); + + s.insert(&buf[4]); + s.insert(&buf[5]); + s.insert(&buf[6]); + s.insert(&buf[7]); + + i = 0; + for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) + (**I)++; + EXPECT_EQ(8, i); + s.erase(&buf[4]); + s.erase(&buf[5]); + s.erase(&buf[6]); + s.erase(&buf[7]); + EXPECT_EQ(4U, s.size()); + + i = 0; + for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) + (**I)++; + EXPECT_EQ(4, i); + for(i=0; i<8; ++i) + EXPECT_EQ(i<4?3:1,buf[i]); + + s.clear(); + for(i=0; i<8; ++i) buf[i]=0; + for(i=0; i<128; ++i) s.insert(&buf[i%8]); // test repeated entires + EXPECT_EQ(8U, s.size()); + for(iter I=s.begin(), E=s.end(); I!=E; ++I, ++i) + (**I)++; + for(i=0; i<8; ++i) + EXPECT_EQ(1,buf[i]); +} + + TEST(SmallPtrSetTest, SwapTest) { int buf[10]; -- cgit v1.2.3-70-g09d2