[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.21 -> 1.22 --- Log message: add a new form of insert. --- Diffs of the changes: (+48 -1) SmallVector.h | 49 - 1 files changed, 48 insertions(+), 1 deletion(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.21 llvm/include/llvm/ADT/SmallVector.h:1.22 --- llvm/include/llvm/ADT/SmallVector.h:1.21Sun Oct 29 21:39:20 2006 +++ llvm/include/llvm/ADT/SmallVector.h Sun Oct 29 23:07:51 2006 @@ -207,6 +207,54 @@ goto Retry; } + template + iterator insert(iterator I, ItTy From, ItTy To) { +if (I == End) { // Important special case for empty vector. + append(From, To); + return end()-1; +} + +unsigned NumToInsert = std::distance(From, To); +// Convert iterator to elt# to avoid invalidating iterator when we reserve() +unsigned InsertElt = I-begin(); + +// Ensure there is enough space. +reserve(size() + NumToInsert); + +// Uninvalidate the iterator. +I = begin()+InsertElt; + +// If we already have this many elements in the collection, append the +// dest elements at the end, then copy over the appropriate elements. Since +// we already reserved space, we know that this won't reallocate the vector. +if (size() >= NumToInsert) { + T *OldEnd = End; + append(End-NumToInsert, End); + + // Copy the existing elements that get replaced. + std::copy(I, OldEnd-NumToInsert, I+NumToInsert); + + std::copy(From, To, I); + return I; +} + +// Otherwise, we're inserting more elements than exist already, and we're +// not inserting at the end. + +// Copy over the elements that we're about to overwrite. +T *OldEnd = End; +End += NumToInsert; +unsigned NumOverwritten = OldEnd-I; +std::uninitialized_copy(I, OldEnd, End-NumOverwritten); + +// Replace the overwritten part. +std::copy(From, From+NumOverwritten, I); + +// Insert the non-overwritten middle part. +std::uninitialized_copy(From+NumOverwritten, To, OldEnd); +return I; + } + const SmallVectorImpl &operator=(const SmallVectorImpl &RHS); private: @@ -224,7 +272,6 @@ for (; S != E; ++S) new (S) T(Elt); } - void destroy_range(T *S, T *E) { while (S != E) { ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.22 -> 1.23 --- Log message: add missing ctor --- Diffs of the changes: (+7 -0) SmallVector.h |7 +++ 1 files changed, 7 insertions(+) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.22 llvm/include/llvm/ADT/SmallVector.h:1.23 --- llvm/include/llvm/ADT/SmallVector.h:1.22Sun Oct 29 23:07:51 2006 +++ llvm/include/llvm/ADT/SmallVector.h Wed Jan 31 14:08:34 2007 @@ -418,6 +418,13 @@ SmallVector() : SmallVectorImpl(NumTsAvailable) { } + SmallVector(unsigned Size, const T &Value) +: SmallVectorImpl(NumTsAvailable) { +this->reserve(Size); +while (Size--) + push_back(Value); + } + template SmallVector(ItTy S, ItTy E) : SmallVectorImpl(NumTsAvailable) { append(S, E); ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.23 -> 1.24 --- Log message: fix a critical bug in smallvector, where it would destroy elements that are not in its range (!). --- Diffs of the changes: (+1 -1) SmallVector.h |2 +- 1 files changed, 1 insertion(+), 1 deletion(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.23 llvm/include/llvm/ADT/SmallVector.h:1.24 --- llvm/include/llvm/ADT/SmallVector.h:1.23Wed Jan 31 14:08:34 2007 +++ llvm/include/llvm/ADT/SmallVector.h Tue Feb 13 01:25:36 2007 @@ -275,8 +275,8 @@ void destroy_range(T *S, T *E) { while (S != E) { - E->~T(); --E; + E->~T(); } } }; ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.24 -> 1.25 --- Log message: Unbreak VC++ build. --- Diffs of the changes: (+19 -0) SmallVector.h | 19 +++ 1 files changed, 19 insertions(+) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.24 llvm/include/llvm/ADT/SmallVector.h:1.25 --- llvm/include/llvm/ADT/SmallVector.h:1.24Tue Feb 13 01:25:36 2007 +++ llvm/include/llvm/ADT/SmallVector.h Sun Mar 4 18:00:41 2007 @@ -18,6 +18,25 @@ #include #include +#ifdef _MSC_VER +namespace std { + // Fix bug in VC++ implementation of std::uninitialized_copy. Define + // additional overloads so that the copy is recognized as a scalar and + // not an object copy. + template + inline _Scalar_ptr_iterator_tag _Ptr_cat(T1 **, T2 **) { + _Scalar_ptr_iterator_tag _Cat; + return _Cat; + } + + template + inline _Scalar_ptr_iterator_tag _Ptr_cat(T1* const *, T2 **) { + _Scalar_ptr_iterator_tag _Cat; + return _Cat; + } +} +#endif + namespace llvm { /// SmallVectorImpl - This class consists of common code factored out of the ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.25 -> 1.26 --- Log message: Elminate tabs and improve comments. --- Diffs of the changes: (+8 -7) SmallVector.h | 15 --- 1 files changed, 8 insertions(+), 7 deletions(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.25 llvm/include/llvm/ADT/SmallVector.h:1.26 --- llvm/include/llvm/ADT/SmallVector.h:1.25Sun Mar 4 18:00:41 2007 +++ llvm/include/llvm/ADT/SmallVector.h Sun Mar 4 18:46:22 2007 @@ -20,19 +20,20 @@ #ifdef _MSC_VER namespace std { - // Fix bug in VC++ implementation of std::uninitialized_copy. Define - // additional overloads so that the copy is recognized as a scalar and - // not an object copy. + // Work around flawed VC++ implementation of std::uninitialized_copy. Define + // additional overloads so that elements with pointer types are recognized as + // scalars and not objects, causing bizarre type conversion errors. + // FIXME: this hack may or may not be correct for Visual Studio 2005. template inline _Scalar_ptr_iterator_tag _Ptr_cat(T1 **, T2 **) { - _Scalar_ptr_iterator_tag _Cat; - return _Cat; +_Scalar_ptr_iterator_tag _Cat; +return _Cat; } template inline _Scalar_ptr_iterator_tag _Ptr_cat(T1* const *, T2 **) { - _Scalar_ptr_iterator_tag _Cat; - return _Cat; +_Scalar_ptr_iterator_tag _Cat; +return _Cat; } } #endif ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.26 -> 1.27 --- Log message: The hack won't work on VS 2005, and it might not be needed anyway. --- Diffs of the changes: (+5 -1) SmallVector.h |6 +- 1 files changed, 5 insertions(+), 1 deletion(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.26 llvm/include/llvm/ADT/SmallVector.h:1.27 --- llvm/include/llvm/ADT/SmallVector.h:1.26Sun Mar 4 18:46:22 2007 +++ llvm/include/llvm/ADT/SmallVector.h Mon Mar 5 11:22:33 2007 @@ -20,10 +20,10 @@ #ifdef _MSC_VER namespace std { +#if _MSC_VER <= 1310 // Work around flawed VC++ implementation of std::uninitialized_copy. Define // additional overloads so that elements with pointer types are recognized as // scalars and not objects, causing bizarre type conversion errors. - // FIXME: this hack may or may not be correct for Visual Studio 2005. template inline _Scalar_ptr_iterator_tag _Ptr_cat(T1 **, T2 **) { _Scalar_ptr_iterator_tag _Cat; @@ -35,6 +35,10 @@ _Scalar_ptr_iterator_tag _Cat; return _Cat; } +#else +// FIXME: It is not clear if the problem is fixed in VS 2005. What is clear +// is that the above hack won't work if it wasn't fixed. +#endif } #endif ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.27 -> 1.28 --- Log message: Fix some VC++ warnings. --- Diffs of the changes: (+4 -4) SmallVector.h |8 1 files changed, 4 insertions(+), 4 deletions(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.27 llvm/include/llvm/ADT/SmallVector.h:1.28 --- llvm/include/llvm/ADT/SmallVector.h:1.27Mon Mar 5 11:22:33 2007 +++ llvm/include/llvm/ADT/SmallVector.h Wed Apr 18 21:04:09 2007 @@ -308,8 +308,8 @@ // Define this out-of-line to dissuade the C++ compiler from inlining it. template void SmallVectorImpl::grow(unsigned MinSize) { - unsigned CurCapacity = Capacity-Begin; - unsigned CurSize = size(); + unsigned CurCapacity = unsigned(Capacity-Begin); + unsigned CurSize = unsigned(size()); unsigned NewCapacity = 2*CurCapacity; if (NewCapacity < MinSize) NewCapacity = MinSize; @@ -376,8 +376,8 @@ // If we already have sufficient space, assign the common elements, then // destroy any excess. - unsigned RHSSize = RHS.size(); - unsigned CurSize = size(); + unsigned RHSSize = unsigned(RHS.size()); + unsigned CurSize = unsigned(size()); if (CurSize >= RHSSize) { // Assign common elements. iterator NewEnd = std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin); ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h added (r1.1) --- Log message: Add a new llvm::SmallVector template, which is similar to the vector class, but contains optimizations to avoid heap allocation if the vector size is smaller than some threshold. This can significantly improve the performance of code that allocates many small vectors by eliminating tons of small malloc/free's. --- Diffs of the changes: (+196 -0) SmallVector.h | 196 ++ 1 files changed, 196 insertions(+) Index: llvm/include/llvm/ADT/SmallVector.h diff -c /dev/null llvm/include/llvm/ADT/SmallVector.h:1.1 *** /dev/null Wed Jul 26 01:22:40 2006 --- llvm/include/llvm/ADT/SmallVector.h Wed Jul 26 01:22:30 2006 *** *** 0 --- 1,196 + //===- llvm/ADT/SmallVector.h - 'Normally small' vectors *- C++ -*-===// + // + // 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 defines the SmallVector class. + // + //===--===// + + #ifndef LLVM_ADT_SMALLVECTOR_H + #define LLVM_ADT_SMALLVECTOR_H + + #include + #include + + namespace llvm { + + /// SmallVector - This is a 'vector' (really, a variable-sized array), optimized + /// for the case when the array is small. It contains some number of elements + /// in-place, which allows it to avoid heap allocation when the actual number of + /// elements is below that threshold. This allows normal "small" cases to be + /// fast without losing generality for large inputs. + /// + /// Note that this does not attempt to be exception safe. + /// + template + class SmallVector { + // Allocate raw space for N elements of type T. If T has a ctor or dtor, we + // don't want it to be automatically run, so we need to represent the space as + // something else. An array of char would work great, but might not be + // aligned sufficiently. Instead, we either use GCC extensions, or some + // number of union instances for the space, which guarantee maximal alignment. + union U { + double D; + long double LD; + long long L; + void *P; + }; + + /// InlineElts - These are the 'N' elements that are stored inline in the body + /// of the vector + U InlineElts[(sizeof(T)*N+sizeof(U)-1)/sizeof(U)]; + T *Begin, *End, *Capacity; + public: + // Default ctor - Initialize to empty. + SmallVector() : Begin((T*)InlineElts), End(Begin), Capacity(Begin+N) { + } + + SmallVector(const SmallVector &RHS) { + unsigned RHSSize = RHS.size(); + Begin = (T*)InlineElts; + + // Doesn't fit in the small case? Allocate space. + if (RHSSize > N) { + End = Capacity = Begin; + grow(RHSSize); + } + End = Begin+RHSSize; + Capacity = Begin+N; + std::uninitialized_copy(RHS.begin(), RHS.end(), Begin); + } + ~SmallVector() { + // If this wasn't grown from the inline copy, deallocate the old space. + if ((void*)Begin != (void*)InlineElts) + delete[] (char*)Begin; + } + + typedef size_t size_type; + typedef T* iterator; + typedef const T* const_iterator; + typedef T& reference; + typedef const T& const_reference; + + bool empty() const { return Begin == End; } + size_type size() const { return End-Begin; } + + iterator begin() { return Begin; } + const_iterator begin() const { return Begin; } + + iterator end() { return End; } + const_iterator end() const { return End; } + + reference operator[](unsigned idx) { + assert(idx < size() && "out of range reference!"); + return Begin[idx]; + } + const_reference operator[](unsigned idx) const { + assert(idx < size() && "out of range reference!"); + return Begin[idx]; + } + + reference back() { + assert(!empty() && "SmallVector is empty!"); + return end()[-1]; + } + const_reference back() const { + assert(!empty() && "SmallVector is empty!"); + return end()[-1]; + } + + void push_back(const_reference Elt) { + if (End < Capacity) { + Retry: + new (End) T(Elt); + ++End; + return; + } + grow(); + goto Retry; + } + + const SmallVector &operator=(const SmallVector &RHS) { + // Avoid self-assignment. + if (this == &RHS) return *this; + + // If we already have sufficient space, assign the common elements, then + // destroy any excess. + unsigned RHSSize = RHS.size(); + unsigned CurSize = size(); + if (CurSize >= RHSSize) { + // Assign common elements. + for (unsigned i = 0; i != RHSSize; ++i) + Begin[i] = RHS.Begin[i]; + + // Destroy excess elements. +
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.1 -> 1.2 --- Log message: Use std::copy instead of custom loops to take advantage of STL optimizations. Add a new append method for appending a range. --- Diffs of the changes: (+19 -5) SmallVector.h | 24 +++- 1 files changed, 19 insertions(+), 5 deletions(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.1 llvm/include/llvm/ADT/SmallVector.h:1.2 --- llvm/include/llvm/ADT/SmallVector.h:1.1 Wed Jul 26 01:22:30 2006 +++ llvm/include/llvm/ADT/SmallVector.h Wed Jul 26 22:38:08 2006 @@ -14,7 +14,9 @@ #ifndef LLVM_ADT_SMALLVECTOR_H #define LLVM_ADT_SMALLVECTOR_H +#include #include +#include #include namespace llvm { @@ -113,6 +115,20 @@ goto Retry; } + /// append - Add the specified range to the end of the SmallVector. + /// + template + void append(in_iter in_start, in_iter in_end) { +unsigned NumInputs = std::distance(in_start, in_end); +// Grow allocated space if needed. +if (End+NumInputs > Capacity) + grow(size()+NumInputs); + +// Copy the new elements over. +std::uninitialized_copy(in_start, in_end, End); +End += NumInputs; + } + const SmallVector &operator=(const SmallVector &RHS) { // Avoid self-assignment. if (this == &RHS) return *this; @@ -123,8 +139,7 @@ unsigned CurSize = size(); if (CurSize >= RHSSize) { // Assign common elements. - for (unsigned i = 0; i != RHSSize; ++i) -Begin[i] = RHS.Begin[i]; + std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin); // Destroy excess elements. for (unsigned i = RHSSize; i != CurSize; ++i) @@ -144,10 +159,9 @@ End = Begin; CurSize = 0; grow(RHSSize); -} else { +} else if (CurSize) { // Otherwise, use assignment for the already-constructed elements. - for (unsigned i = 0; i != CurSize; ++i) -Begin[i] = RHS.Begin[i]; + std::copy(RHS.Begin, RHS.Begin+CurSize, Begin); } // Copy construct the new elements in place. ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.2 -> 1.3 --- Log message: The smallvector dtor should destroy the elements. Implement pop_back. Chage some code to use 'iterator' instead of T*. This unbreaks operators=. --- Diffs of the changes: (+12 -2) SmallVector.h | 14 -- 1 files changed, 12 insertions(+), 2 deletions(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.2 llvm/include/llvm/ADT/SmallVector.h:1.3 --- llvm/include/llvm/ADT/SmallVector.h:1.2 Wed Jul 26 22:38:08 2006 +++ llvm/include/llvm/ADT/SmallVector.h Fri Jul 28 00:03:42 2006 @@ -66,6 +66,10 @@ std::uninitialized_copy(RHS.begin(), RHS.end(), Begin); } ~SmallVector() { +// Destroy the constructed elements in the vector. +for (iterator I = Begin, E = End; I != E; ++I) + I->~T(); + // If this wasn't grown from the inline copy, deallocate the old space. if ((void*)Begin != (void*)InlineElts) delete[] (char*)Begin; @@ -115,6 +119,12 @@ goto Retry; } + void pop_back() { +assert(!empty() && "SmallVector is empty!"); +--End; +End->~T(); + } + /// append - Add the specified range to the end of the SmallVector. /// template @@ -154,7 +164,7 @@ // This allows us to avoid copying them during the grow. if (Capacity-Begin < RHSSize) { // Destroy current elements. - for (T *I = Begin, E = End; I != E; ++I) + for (iterator I = Begin, E = End; I != E; ++I) I->~T(); End = Begin; CurSize = 0; @@ -192,7 +202,7 @@ std::uninitialized_copy(Begin, End, NewElts); // Destroy the original elements. -for (T *I = Begin, *E = End; I != E; ++I) +for (iterator I = Begin, E = End; I != E; ++I) I->~T(); // If this wasn't grown from the inline copy, deallocate the old space. ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.3 -> 1.4 --- Log message: This causes some random crashes. --- Diffs of the changes: (+1 -1) SmallVector.h |2 +- 1 files changed, 1 insertion(+), 1 deletion(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.3 llvm/include/llvm/ADT/SmallVector.h:1.4 --- llvm/include/llvm/ADT/SmallVector.h:1.3 Fri Jul 28 00:03:42 2006 +++ llvm/include/llvm/ADT/SmallVector.h Sat Aug 5 12:31:00 2006 @@ -211,7 +211,7 @@ Begin = NewElts; End = NewElts+CurSize; -Capacity = Begin+NewCapacity*2; +Capacity = Begin+NewCapacity; } }; ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.4 -> 1.5 --- Log message: Add a clear method to SmallVector --- Diffs of the changes: (+0 -0) 0 files changed ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.5 -> 1.6 --- Log message: Remove assertions from the SmallVector class. They slow down clients of smallvector too much in a release build. Removing them speeds up isel 4%. --- Diffs of the changes: (+0 -6) SmallVector.h |6 -- 1 files changed, 6 deletions(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.5 llvm/include/llvm/ADT/SmallVector.h:1.6 --- llvm/include/llvm/ADT/SmallVector.h:1.5 Mon Aug 7 00:45:34 2006 +++ llvm/include/llvm/ADT/SmallVector.h Mon Aug 7 18:41:59 2006 @@ -15,7 +15,6 @@ #define LLVM_ADT_SMALLVECTOR_H #include -#include #include #include @@ -91,20 +90,16 @@ const_iterator end() const { return End; } reference operator[](unsigned idx) { -assert(idx < size() && "out of range reference!"); return Begin[idx]; } const_reference operator[](unsigned idx) const { -assert(idx < size() && "out of range reference!"); return Begin[idx]; } reference back() { -assert(!empty() && "SmallVector is empty!"); return end()[-1]; } const_reference back() const { -assert(!empty() && "SmallVector is empty!"); return end()[-1]; } @@ -120,7 +115,6 @@ } void pop_back() { -assert(!empty() && "SmallVector is empty!"); --End; End->~T(); } ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.6 -> 1.7 --- Log message: Add ctor that initializes from a range. --- Diffs of the changes: (+6 -0) SmallVector.h |6 ++ 1 files changed, 6 insertions(+) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.6 llvm/include/llvm/ADT/SmallVector.h:1.7 --- llvm/include/llvm/ADT/SmallVector.h:1.6 Mon Aug 7 18:41:59 2006 +++ llvm/include/llvm/ADT/SmallVector.h Mon Aug 7 19:37:50 2006 @@ -51,6 +51,12 @@ SmallVector() : Begin((T*)InlineElts), End(Begin), Capacity(Begin+N) { } + template + SmallVector(ItTy S, ItTy E) +: Begin((T*)InlineElts), End(Begin), Capacity(Begin+N) { +append(S, E); + } + SmallVector(const SmallVector &RHS) { unsigned RHSSize = RHS.size(); Begin = (T*)InlineElts; ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.7 -> 1.8 --- Log message: add a new assign method --- Diffs of the changes: (+9 -0) SmallVector.h |9 + 1 files changed, 9 insertions(+) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.7 llvm/include/llvm/ADT/SmallVector.h:1.8 --- llvm/include/llvm/ADT/SmallVector.h:1.7 Mon Aug 7 19:37:50 2006 +++ llvm/include/llvm/ADT/SmallVector.h Mon Aug 7 20:44:16 2006 @@ -146,6 +146,15 @@ End += NumInputs; } + void assign(unsigned NumElts, const T &Elt) { +clear(); +if (NumElts > Capacity) + grow(NumElts); +End = Begin+NumElts; +for (; NumElts; --NumElts) + new (Begin+NumElts-1) T(Elt); + } + const SmallVector &operator=(const SmallVector &RHS) { // Avoid self-assignment. if (this == &RHS) return *this; ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.8 -> 1.9 --- Log message: capacity is a pointer, not a value --- Diffs of the changes: (+1 -1) SmallVector.h |2 +- 1 files changed, 1 insertion(+), 1 deletion(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.8 llvm/include/llvm/ADT/SmallVector.h:1.9 --- llvm/include/llvm/ADT/SmallVector.h:1.8 Mon Aug 7 20:44:16 2006 +++ llvm/include/llvm/ADT/SmallVector.h Mon Aug 7 20:54:17 2006 @@ -148,7 +148,7 @@ void assign(unsigned NumElts, const T &Elt) { clear(); -if (NumElts > Capacity) +if (Begin+NumElts > Capacity) grow(NumElts); End = Begin+NumElts; for (; NumElts; --NumElts) ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.9 -> 1.10 --- Log message: Split SmallVector into SmallVector and SmallVectorImpl, which allows us to eliminate code duplication due to the 'N' parameter. --- Diffs of the changes: (+45 -40) SmallVector.h | 85 ++ 1 files changed, 45 insertions(+), 40 deletions(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.9 llvm/include/llvm/ADT/SmallVector.h:1.10 --- llvm/include/llvm/ADT/SmallVector.h:1.9 Mon Aug 7 20:54:17 2006 +++ llvm/include/llvm/ADT/SmallVector.h Fri Aug 11 18:19:51 2006 @@ -20,63 +20,39 @@ namespace llvm { -/// SmallVector - This is a 'vector' (really, a variable-sized array), optimized -/// for the case when the array is small. It contains some number of elements -/// in-place, which allows it to avoid heap allocation when the actual number of -/// elements is below that threshold. This allows normal "small" cases to be -/// fast without losing generality for large inputs. -/// -/// Note that this does not attempt to be exception safe. -/// -template -class SmallVector { +/// SmallVectorImpl - This class consists of common code factored out of the +/// SmallVector class to reduce code duplication based on the SmallVector 'N' +/// template parameter. +template +class SmallVectorImpl { + T *Begin, *End, *Capacity; + // Allocate raw space for N elements of type T. If T has a ctor or dtor, we // don't want it to be automatically run, so we need to represent the space as // something else. An array of char would work great, but might not be // aligned sufficiently. Instead, we either use GCC extensions, or some // number of union instances for the space, which guarantee maximal alignment. +protected: union U { double D; long double LD; long long L; void *P; - }; - - /// InlineElts - These are the 'N' elements that are stored inline in the body - /// of the vector - U InlineElts[(sizeof(T)*N+sizeof(U)-1)/sizeof(U)]; - T *Begin, *End, *Capacity; + } FirstEl; + // Space after 'FirstEl' is clobbered, do not add any instance vars after it. public: // Default ctor - Initialize to empty. - SmallVector() : Begin((T*)InlineElts), End(Begin), Capacity(Begin+N) { - } - - template - SmallVector(ItTy S, ItTy E) -: Begin((T*)InlineElts), End(Begin), Capacity(Begin+N) { -append(S, E); + SmallVectorImpl(unsigned N) +: Begin((T*)&FirstEl), End((T*)&FirstEl), Capacity((T*)&FirstEl+N) { } - SmallVector(const SmallVector &RHS) { -unsigned RHSSize = RHS.size(); -Begin = (T*)InlineElts; - -// Doesn't fit in the small case? Allocate space. -if (RHSSize > N) { - End = Capacity = Begin; - grow(RHSSize); -} -End = Begin+RHSSize; -Capacity = Begin+N; -std::uninitialized_copy(RHS.begin(), RHS.end(), Begin); - } - ~SmallVector() { + ~SmallVectorImpl() { // Destroy the constructed elements in the vector. for (iterator I = Begin, E = End; I != E; ++I) I->~T(); // If this wasn't grown from the inline copy, deallocate the old space. -if ((void*)Begin != (void*)InlineElts) +if (!isSmall()) delete[] (char*)Begin; } @@ -155,7 +131,7 @@ new (Begin+NumElts-1) T(Elt); } - const SmallVector &operator=(const SmallVector &RHS) { + const SmallVectorImpl &operator=(const SmallVectorImpl &RHS) { // Avoid self-assignment. if (this == &RHS) return *this; @@ -201,7 +177,7 @@ /// isSmall - Return true if this is a smallvector which has not had dynamic /// memory allocated for it. bool isSmall() const { -return (void*)Begin == (void*)InlineElts; +return (void*)Begin == (void*)&FirstEl; } /// grow - double the size of the allocated memory, guaranteeing space for at @@ -231,6 +207,35 @@ } }; + +/// SmallVector - This is a 'vector' (really, a variable-sized array), optimized +/// for the case when the array is small. It contains some number of elements +/// in-place, which allows it to avoid heap allocation when the actual number of +/// elements is below that threshold. This allows normal "small" cases to be +/// fast without losing generality for large inputs. +/// +/// Note that this does not attempt to be exception safe. +/// +template +class SmallVector : public SmallVectorImpl { + /// InlineElts - These are 'N-1' elements that are stored inline in the body + /// of the vector. The extra '1' element is stored in SmallVectorImpl. + typedef typename SmallVectorImpl::U U; + U InlineElts[(sizeof(T)*N+sizeof(U)-1)/sizeof(U) - 1]; +public: + SmallVector() : SmallVectorImpl(N) { + } + + template + SmallVector(ItTy S, ItTy E) : SmallVectorImpl(N) { +append(S, E); + } + + SmallVector(const SmallVector &RHS) : SmallVectorImpl(N) { +operator=(RHS); + } +}; + } // End llvm namespace #endif
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.10 -> 1.11 --- Log message: move code out of line so that GCC doesn't inline it at -O3 --- Diffs of the changes: (+69 -62) SmallVector.h | 131 ++ 1 files changed, 69 insertions(+), 62 deletions(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.10 llvm/include/llvm/ADT/SmallVector.h:1.11 --- llvm/include/llvm/ADT/SmallVector.h:1.10Fri Aug 11 18:19:51 2006 +++ llvm/include/llvm/ADT/SmallVector.h Fri Aug 11 18:40:23 2006 @@ -131,47 +131,7 @@ new (Begin+NumElts-1) T(Elt); } - const SmallVectorImpl &operator=(const SmallVectorImpl &RHS) { -// Avoid self-assignment. -if (this == &RHS) return *this; - -// If we already have sufficient space, assign the common elements, then -// destroy any excess. -unsigned RHSSize = RHS.size(); -unsigned CurSize = size(); -if (CurSize >= RHSSize) { - // Assign common elements. - std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin); - - // Destroy excess elements. - for (unsigned i = RHSSize; i != CurSize; ++i) -Begin[i].~T(); - - // Trim. - End = Begin + RHSSize; - return *this; -} - -// If we have to grow to have enough elements, destroy the current elements. -// This allows us to avoid copying them during the grow. -if (Capacity-Begin < RHSSize) { - // Destroy current elements. - for (iterator I = Begin, E = End; I != E; ++I) -I->~T(); - End = Begin; - CurSize = 0; - grow(RHSSize); -} else if (CurSize) { - // Otherwise, use assignment for the already-constructed elements. - std::copy(RHS.Begin, RHS.Begin+CurSize, Begin); -} - -// Copy construct the new elements in place. -std::uninitialized_copy(RHS.Begin+CurSize, RHS.End, Begin+CurSize); - -// Set end. -End = Begin+RHSSize; - } + const SmallVectorImpl &operator=(const SmallVectorImpl &RHS); private: /// isSmall - Return true if this is a smallvector which has not had dynamic @@ -182,31 +142,78 @@ /// grow - double the size of the allocated memory, guaranteeing space for at /// least one more element or MinSize if specified. - void grow(unsigned MinSize = 0) { -unsigned CurCapacity = Capacity-Begin; -unsigned CurSize = size(); -unsigned NewCapacity = 2*CurCapacity; -if (NewCapacity < MinSize) - NewCapacity = MinSize; -T *NewElts = reinterpret_cast(new char[NewCapacity*sizeof(T)]); + void grow(unsigned MinSize = 0); +}; -// Copy the elements over. -std::uninitialized_copy(Begin, End, NewElts); - -// Destroy the original elements. +// Define this out-of-line to dissuade the C++ compiler from inlining it. +template +void SmallVectorImpl::grow(unsigned MinSize) { + unsigned CurCapacity = Capacity-Begin; + unsigned CurSize = size(); + unsigned NewCapacity = 2*CurCapacity; + if (NewCapacity < MinSize) +NewCapacity = MinSize; + T *NewElts = reinterpret_cast(new char[NewCapacity*sizeof(T)]); + + // Copy the elements over. + std::uninitialized_copy(Begin, End, NewElts); + + // Destroy the original elements. + for (iterator I = Begin, E = End; I != E; ++I) +I->~T(); + + // If this wasn't grown from the inline copy, deallocate the old space. + if (!isSmall()) +delete[] (char*)Begin; + + Begin = NewElts; + End = NewElts+CurSize; + Capacity = Begin+NewCapacity; +} + +template +const SmallVectorImpl & +SmallVectorImpl::operator=(const SmallVectorImpl &RHS) { + // Avoid self-assignment. + if (this == &RHS) return *this; + + // If we already have sufficient space, assign the common elements, then + // destroy any excess. + unsigned RHSSize = RHS.size(); + unsigned CurSize = size(); + if (CurSize >= RHSSize) { +// Assign common elements. +std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin); + +// Destroy excess elements. +for (unsigned i = RHSSize; i != CurSize; ++i) + Begin[i].~T(); + +// Trim. +End = Begin + RHSSize; +return *this; + } + + // If we have to grow to have enough elements, destroy the current elements. + // This allows us to avoid copying them during the grow. + if (Capacity-Begin < RHSSize) { +// Destroy current elements. for (iterator I = Begin, E = End; I != E; ++I) I->~T(); - -// If this wasn't grown from the inline copy, deallocate the old space. -if (!isSmall()) - delete[] (char*)Begin; - -Begin = NewElts; -End = NewElts+CurSize; -Capacity = Begin+NewCapacity; +End = Begin; +CurSize = 0; +grow(RHSSize); + } else if (CurSize) { +// Otherwise, use assignment for the already-constructed elements. +std::copy(RHS.Begin, RHS.Begin+CurSize, Begin); } -}; - + + // Copy construct the new elements in place. + std::uninitialized_copy(RHS.B
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.11 -> 1.12 --- Log message: avoid a warning --- Diffs of the changes: (+1 -1) SmallVector.h |2 +- 1 files changed, 1 insertion(+), 1 deletion(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.11 llvm/include/llvm/ADT/SmallVector.h:1.12 --- llvm/include/llvm/ADT/SmallVector.h:1.11Fri Aug 11 18:40:23 2006 +++ llvm/include/llvm/ADT/SmallVector.h Mon Aug 14 16:47:50 2006 @@ -196,7 +196,7 @@ // If we have to grow to have enough elements, destroy the current elements. // This allows us to avoid copying them during the grow. - if (Capacity-Begin < RHSSize) { + if (unsigned(Capacity-Begin) < RHSSize) { // Destroy current elements. for (iterator I = Begin, E = End; I != E; ++I) I->~T(); ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.12 -> 1.13 --- Log message: Bugfixes for smallvector when the element size is small and N is small. --- Diffs of the changes: (+17 -4) SmallVector.h | 21 + 1 files changed, 17 insertions(+), 4 deletions(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.12 llvm/include/llvm/ADT/SmallVector.h:1.13 --- llvm/include/llvm/ADT/SmallVector.h:1.12Mon Aug 14 16:47:50 2006 +++ llvm/include/llvm/ADT/SmallVector.h Tue Aug 15 20:23:31 2006 @@ -228,17 +228,30 @@ /// InlineElts - These are 'N-1' elements that are stored inline in the body /// of the vector. The extra '1' element is stored in SmallVectorImpl. typedef typename SmallVectorImpl::U U; - U InlineElts[(sizeof(T)*N+sizeof(U)-1)/sizeof(U) - 1]; + enum { +// MinUs - The number of U's require to cover N T's. +MinUs = (sizeof(T)*N+sizeof(U)-1)/sizeof(U), + +// NumInlineEltsElts - The number of elements actually in this array. There +// is already one in the parent class, and we have to round up to avoid +// having a zero-element array. +NumInlineEltsElts = (MinUs - 1) > 0 ? (MinUs - 1) : 1, + +// NumTsAvailable - The number of T's we actually have space for, which may +// be more than N due to rounding. +NumTsAvailable = (NumInlineEltsElts+1)*sizeof(U) / sizeof(T) + }; + U InlineElts[NumInlineEltsElts]; public: - SmallVector() : SmallVectorImpl(N) { + SmallVector() : SmallVectorImpl(NumTsAvailable) { } template - SmallVector(ItTy S, ItTy E) : SmallVectorImpl(N) { + SmallVector(ItTy S, ItTy E) : SmallVectorImpl(NumTsAvailable) { append(S, E); } - SmallVector(const SmallVector &RHS) : SmallVectorImpl(N) { + SmallVector(const SmallVector &RHS) : SmallVectorImpl(NumTsAvailable) { operator=(RHS); } }; ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.13 -> 1.14 --- Log message: silence a warning. --- Diffs of the changes: (+1 -0) SmallVector.h |1 + 1 files changed, 1 insertion(+) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.13 llvm/include/llvm/ADT/SmallVector.h:1.14 --- llvm/include/llvm/ADT/SmallVector.h:1.13Tue Aug 15 20:23:31 2006 +++ llvm/include/llvm/ADT/SmallVector.h Wed Aug 16 17:09:24 2006 @@ -213,6 +213,7 @@ // Set end. End = Begin+RHSSize; + return *this; } /// SmallVector - This is a 'vector' (really, a variable-sized array), optimized ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.14 -> 1.15 --- Log message: add a bunch more operations, including swap, insert, erase, front(), and bugfixes for operator=. --- Diffs of the changes: (+115 -13) SmallVector.h | 128 -- 1 files changed, 115 insertions(+), 13 deletions(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.14 llvm/include/llvm/ADT/SmallVector.h:1.15 --- llvm/include/llvm/ADT/SmallVector.h:1.14Wed Aug 16 17:09:24 2006 +++ llvm/include/llvm/ADT/SmallVector.h Tue Aug 22 01:27:16 2006 @@ -48,8 +48,7 @@ ~SmallVectorImpl() { // Destroy the constructed elements in the vector. -for (iterator I = Begin, E = End; I != E; ++I) - I->~T(); +destroy_range(Begin, End); // If this wasn't grown from the inline copy, deallocate the old space. if (!isSmall()) @@ -78,6 +77,13 @@ return Begin[idx]; } + reference front() { +return begin()[0]; + } + const_reference front() const { +return begin()[0]; + } + reference back() { return end()[-1]; } @@ -102,9 +108,44 @@ } void clear() { -while (End != Begin) { - End->~T(); - --End; +destroy_range(Begin, End); +End = Begin; + } + + void swap(SmallVectorImpl &RHS) { +if (this == &RHS) return; + +// We can only avoid copying elements if neither vector is small. +if (!isSmall() && !RHS.isSmall()) { + std::swap(Begin, RHS.Begin); + std::swap(End, RHS.End); + std::swap(Capacity, RHS.Capacity); + return; +} +if (Begin+RHS.size() > Capacity) + grow(RHS.size()); +if (RHS.begin()+size() > RHS.Capacity) + RHS.grow(size()); + +// Swap the shared elements. +unsigned NumShared = size(); +if (NumShared > RHS.size()) NumShared = RHS.size(); +for (unsigned i = 0; i != NumShared; ++i) + std::swap(Begin[i], RHS[i]); + +// Copy over the extra elts. +if (size() > RHS.size()) { + unsigned EltDiff = size() - RHS.size(); + std::uninitialized_copy(Begin+NumShared, End, RHS.End); + RHS.End += EltDiff; + destroy_range(Begin+NumShared, End); + End = Begin+NumShared; +} else if (RHS.size() > size()) { + unsigned EltDiff = RHS.size() - size(); + std::uninitialized_copy(RHS.Begin+NumShared, RHS.End, End); + End += EltDiff; + destroy_range(RHS.Begin+NumShared, RHS.End); + RHS.End = RHS.Begin+NumShared; } } @@ -131,6 +172,42 @@ new (Begin+NumElts-1) T(Elt); } + void erase(iterator I) { +// Shift all elts down one. +std::copy(I+1, End, I); +// Drop the last elt. +pop_back(); + } + + void erase(iterator S, iterator E) { +// Shift all elts down. +iterator I = std::copy(E, End, S); +// Drop the last elts. +destroy_range(I, End); +End = I; + } + + iterator insert(iterator I, const T &Elt) { +if (I == End) { // Important special case for empty vector. + push_back(Elt); + return end()-1; +} + +if (End < Capacity) { + Retry: + new (End) T(back()); + ++End; + // Push everything else over. + std::copy_backward(I, End-1, End); + *I = Elt; + return I; +} +unsigned EltNo = I-Begin; +grow(); +I = Begin+EltNo; +goto Retry; + } + const SmallVectorImpl &operator=(const SmallVectorImpl &RHS); private: @@ -143,6 +220,13 @@ /// grow - double the size of the allocated memory, guaranteeing space for at /// least one more element or MinSize if specified. void grow(unsigned MinSize = 0); + + void destroy_range(T *S, T *E) { +while (S != E) { + E->~T(); + --E; +} + } }; // Define this out-of-line to dissuade the C++ compiler from inlining it. @@ -159,8 +243,7 @@ std::uninitialized_copy(Begin, End, NewElts); // Destroy the original elements. - for (iterator I = Begin, E = End; I != E; ++I) -I->~T(); + destroy_range(Begin, End); // If this wasn't grown from the inline copy, deallocate the old space. if (!isSmall()) @@ -183,14 +266,13 @@ unsigned CurSize = size(); if (CurSize >= RHSSize) { // Assign common elements. -std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin); +iterator NewEnd = std::copy(RHS.Begin, RHS.Begin+RHSSize, Begin); // Destroy excess elements. -for (unsigned i = RHSSize; i != CurSize; ++i) - Begin[i].~T(); +destroy_range(NewEnd, End); // Trim. -End = Begin + RHSSize; +End = NewEnd; return *this; } @@ -198,8 +280,7 @@ // This allows us to avoid copying them during the grow. if (unsigned(Capacity-Begin) < RHSSize) { // Destroy current elements. -for (iterator I = Begin, E = End; I != E; ++I) - I->~T(); +destroy_range(Begin, End); End = Begin; CurSize = 0; grow(RHSSize); @@ -255,8 +336,29 @@ S
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.15 -> 1.16 --- Log message: add resize, move swap out of line --- Diffs of the changes: (+56 -36) SmallVector.h | 92 +++--- 1 files changed, 56 insertions(+), 36 deletions(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.15 llvm/include/llvm/ADT/SmallVector.h:1.16 --- llvm/include/llvm/ADT/SmallVector.h:1.15Tue Aug 22 01:27:16 2006 +++ llvm/include/llvm/ADT/SmallVector.h Tue Aug 22 12:28:57 2006 @@ -112,43 +112,20 @@ End = Begin; } - void swap(SmallVectorImpl &RHS) { -if (this == &RHS) return; - -// We can only avoid copying elements if neither vector is small. -if (!isSmall() && !RHS.isSmall()) { - std::swap(Begin, RHS.Begin); - std::swap(End, RHS.End); - std::swap(Capacity, RHS.Capacity); - return; -} -if (Begin+RHS.size() > Capacity) - grow(RHS.size()); -if (RHS.begin()+size() > RHS.Capacity) - RHS.grow(size()); - -// Swap the shared elements. -unsigned NumShared = size(); -if (NumShared > RHS.size()) NumShared = RHS.size(); -for (unsigned i = 0; i != NumShared; ++i) - std::swap(Begin[i], RHS[i]); - -// Copy over the extra elts. -if (size() > RHS.size()) { - unsigned EltDiff = size() - RHS.size(); - std::uninitialized_copy(Begin+NumShared, End, RHS.End); - RHS.End += EltDiff; - destroy_range(Begin+NumShared, End); - End = Begin+NumShared; -} else if (RHS.size() > size()) { - unsigned EltDiff = RHS.size() - size(); - std::uninitialized_copy(RHS.Begin+NumShared, RHS.End, End); - End += EltDiff; - destroy_range(RHS.Begin+NumShared, RHS.End); - RHS.End = RHS.Begin+NumShared; + void resize(unsigned N) { +if (N < size()) { + destroy_range(Begin+N, End); + End = Begin+N; +} else if (N > size()) { + if (Begin+N > Capacity) +grow(N); + construct_range(End, Begin+N, T()); + End = Begin+N; } } + void swap(SmallVectorImpl &RHS); + /// append - Add the specified range to the end of the SmallVector. /// template @@ -168,8 +145,7 @@ if (Begin+NumElts > Capacity) grow(NumElts); End = Begin+NumElts; -for (; NumElts; --NumElts) - new (Begin+NumElts-1) T(Elt); +construct_range(Begin, End, Elt); } void erase(iterator I) { @@ -220,6 +196,12 @@ /// grow - double the size of the allocated memory, guaranteeing space for at /// least one more element or MinSize if specified. void grow(unsigned MinSize = 0); + + void construct_range(T *S, T *E, const T &Elt) { +for (; S != E; ++S) + new (S) T(Elt); + } + void destroy_range(T *S, T *E) { while (S != E) { @@ -253,6 +235,44 @@ End = NewElts+CurSize; Capacity = Begin+NewCapacity; } + +template +void SmallVectorImpl::swap(SmallVectorImpl &RHS) { + if (this == &RHS) return; + + // We can only avoid copying elements if neither vector is small. + if (!isSmall() && !RHS.isSmall()) { +std::swap(Begin, RHS.Begin); +std::swap(End, RHS.End); +std::swap(Capacity, RHS.Capacity); +return; + } + if (Begin+RHS.size() > Capacity) +grow(RHS.size()); + if (RHS.begin()+size() > RHS.Capacity) +RHS.grow(size()); + + // Swap the shared elements. + unsigned NumShared = size(); + if (NumShared > RHS.size()) NumShared = RHS.size(); + for (unsigned i = 0; i != NumShared; ++i) +std::swap(Begin[i], RHS[i]); + + // Copy over the extra elts. + if (size() > RHS.size()) { +unsigned EltDiff = size() - RHS.size(); +std::uninitialized_copy(Begin+NumShared, End, RHS.End); +RHS.End += EltDiff; +destroy_range(Begin+NumShared, End); +End = Begin+NumShared; + } else if (RHS.size() > size()) { +unsigned EltDiff = RHS.size() - size(); +std::uninitialized_copy(RHS.Begin+NumShared, RHS.End, End); +End += EltDiff; +destroy_range(RHS.Begin+NumShared, RHS.End); +RHS.End = RHS.Begin+NumShared; + } +} template const SmallVectorImpl & ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.16 -> 1.17 --- Log message: Add 2nd form of resize --- Diffs of the changes: (+12 -0) SmallVector.h | 12 1 files changed, 12 insertions(+) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.16 llvm/include/llvm/ADT/SmallVector.h:1.17 --- llvm/include/llvm/ADT/SmallVector.h:1.16Tue Aug 22 12:28:57 2006 +++ llvm/include/llvm/ADT/SmallVector.h Mon Aug 28 16:52:08 2006 @@ -124,6 +124,18 @@ } } + void resize(unsigned N, const T &NV) { +if (N < size()) { + destroy_range(Begin+N, End); + End = Begin+N; +} else if (N > size()) { + if (Begin+N > Capacity) +grow(N); + construct_range(End, Begin+N, NV); + End = Begin+N; +} + } + void swap(SmallVectorImpl &RHS); /// append - Add the specified range to the end of the SmallVector. ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.17 -> 1.18 --- Log message: add a simple reserve method. --- Diffs of the changes: (+5 -0) SmallVector.h |5 + 1 files changed, 5 insertions(+) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.17 llvm/include/llvm/ADT/SmallVector.h:1.18 --- llvm/include/llvm/ADT/SmallVector.h:1.17Mon Aug 28 16:52:08 2006 +++ llvm/include/llvm/ADT/SmallVector.h Fri Sep 1 01:08:16 2006 @@ -136,6 +136,11 @@ } } + void reserve(unsigned N) { +if (unsigned(Capacity-Begin) < N) + grow(N); + } + void swap(SmallVectorImpl &RHS); /// append - Add the specified range to the end of the SmallVector. ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.18 -> 1.19 --- Log message: Fix PR897: http://llvm.org/PR897 --- Diffs of the changes: (+5 -0) SmallVector.h |5 + 1 files changed, 5 insertions(+) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.18 llvm/include/llvm/ADT/SmallVector.h:1.19 --- llvm/include/llvm/ADT/SmallVector.h:1.18Fri Sep 1 01:08:16 2006 +++ llvm/include/llvm/ADT/SmallVector.h Sun Oct 8 17:28:34 2006 @@ -33,12 +33,17 @@ // aligned sufficiently. Instead, we either use GCC extensions, or some // number of union instances for the space, which guarantee maximal alignment. protected: +#ifdef __GNUC__ + typedef char U; + U FirstEl __attribute__((aligned(__alignof__(double; +#else union U { double D; long double LD; long long L; void *P; } FirstEl; +#endif // Space after 'FirstEl' is clobbered, do not add any instance vars after it. public: // Default ctor - Initialize to empty. ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.19 -> 1.20 --- Log message: Fix build error in gcc 3.4 and make more this general --- Diffs of the changes: (+1 -1) SmallVector.h |2 +- 1 files changed, 1 insertion(+), 1 deletion(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.19 llvm/include/llvm/ADT/SmallVector.h:1.20 --- llvm/include/llvm/ADT/SmallVector.h:1.19Sun Oct 8 17:28:34 2006 +++ llvm/include/llvm/ADT/SmallVector.h Mon Oct 9 14:05:44 2006 @@ -35,7 +35,7 @@ protected: #ifdef __GNUC__ typedef char U; - U FirstEl __attribute__((aligned(__alignof__(double; + U FirstEl __attribute__((aligned)); #else union U { double D; ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.28 -> 1.29 --- Log message: Fix some sporadic segfaults that are triggered when SmallVector's heap storage lands near the end of the available address space. In the expression Begin+N > Capacity, the Begin+N was overflowing. Fix this by replacing it by with an expression that doesn't involve computation of an address beyond the end of allocated memory. --- Diffs of the changes: (+3 -3) SmallVector.h |6 +++--- 1 files changed, 3 insertions(+), 3 deletions(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.28 llvm/include/llvm/ADT/SmallVector.h:1.29 --- llvm/include/llvm/ADT/SmallVector.h:1.28Wed Apr 18 21:04:09 2007 +++ llvm/include/llvm/ADT/SmallVector.h Thu May 17 13:29:01 2007 @@ -147,7 +147,7 @@ destroy_range(Begin+N, End); End = Begin+N; } else if (N > size()) { - if (Begin+N > Capacity) + if (Capacity-Begin < N) grow(N); construct_range(End, Begin+N, T()); End = Begin+N; @@ -159,7 +159,7 @@ destroy_range(Begin+N, End); End = Begin+N; } else if (N > size()) { - if (Begin+N > Capacity) + if (Capacity-Begin < N) grow(N); construct_range(End, Begin+N, NV); End = Begin+N; @@ -189,7 +189,7 @@ void assign(unsigned NumElts, const T &Elt) { clear(); -if (Begin+NumElts > Capacity) +if (Capacity-Begin < NumElts) grow(NumElts); End = Begin+NumElts; construct_range(Begin, End, Elt); ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.29 -> 1.30 --- Log message: silence some "comparison between signed and unsigned integer expressions" warnings --- Diffs of the changes: (+3 -3) SmallVector.h |6 +++--- 1 files changed, 3 insertions(+), 3 deletions(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.29 llvm/include/llvm/ADT/SmallVector.h:1.30 --- llvm/include/llvm/ADT/SmallVector.h:1.29Thu May 17 13:29:01 2007 +++ llvm/include/llvm/ADT/SmallVector.h Thu May 17 15:01:40 2007 @@ -147,7 +147,7 @@ destroy_range(Begin+N, End); End = Begin+N; } else if (N > size()) { - if (Capacity-Begin < N) + if (unsigned(Capacity-Begin) < N) grow(N); construct_range(End, Begin+N, T()); End = Begin+N; @@ -159,7 +159,7 @@ destroy_range(Begin+N, End); End = Begin+N; } else if (N > size()) { - if (Capacity-Begin < N) + if (unsigned(Capacity-Begin) < N) grow(N); construct_range(End, Begin+N, NV); End = Begin+N; @@ -189,7 +189,7 @@ void assign(unsigned NumElts, const T &Elt) { clear(); -if (Capacity-Begin < NumElts) +if (unsigned(Capacity-Begin) < NumElts) grow(NumElts); End = Begin+NumElts; construct_range(Begin, End, Elt); ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
[llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Changes in directory llvm/include/llvm/ADT: SmallVector.h updated: 1.30 -> 1.31 --- Log message: Add a default parameter to a SmallVector constructor to allow it to be called with just an initial length value, just like in std::vector. --- Diffs of the changes: (+1 -1) SmallVector.h |2 +- 1 files changed, 1 insertion(+), 1 deletion(-) Index: llvm/include/llvm/ADT/SmallVector.h diff -u llvm/include/llvm/ADT/SmallVector.h:1.30 llvm/include/llvm/ADT/SmallVector.h:1.31 --- llvm/include/llvm/ADT/SmallVector.h:1.30Thu May 17 15:01:40 2007 +++ llvm/include/llvm/ADT/SmallVector.h Thu Jun 28 15:27:24 2007 @@ -442,7 +442,7 @@ SmallVector() : SmallVectorImpl(NumTsAvailable) { } - SmallVector(unsigned Size, const T &Value) + SmallVector(unsigned Size, const T &Value = T()) : SmallVectorImpl(NumTsAvailable) { this->reserve(Size); while (Size--) ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
Re: [llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
Andrew, ... On Mon, 2006-10-09 at 14:05 -0500, Andrew Lenharth wrote: > > Changes in directory llvm/include/llvm/ADT: > > SmallVector.h updated: 1.19 -> 1.20 > --- > Log message: > > Fix build error in gcc 3.4 and make more this general This compiled on my 3.4.6 compiler on Linux just fine before the patch. What was the error you were trying to fix? > > --- > Diffs of the changes: (+1 -1) > > SmallVector.h |2 +- > 1 files changed, 1 insertion(+), 1 deletion(-) > > > Index: llvm/include/llvm/ADT/SmallVector.h > diff -u llvm/include/llvm/ADT/SmallVector.h:1.19 > llvm/include/llvm/ADT/SmallVector.h:1.20 > --- llvm/include/llvm/ADT/SmallVector.h:1.19 Sun Oct 8 17:28:34 2006 > +++ llvm/include/llvm/ADT/SmallVector.h Mon Oct 9 14:05:44 2006 > @@ -35,7 +35,7 @@ > protected: > #ifdef __GNUC__ >typedef char U; > - U FirstEl __attribute__((aligned(__alignof__(double; > + U FirstEl __attribute__((aligned)); Are you sure this is right? In section 5.31 of the GCC Manual it indicates that if an alignment size is not given with the aligned attribute keyword then it defaults to: "the maximum useful alignment for the target machine you are compiling for. Whenever you leave out the alignment factor in an `aligned' attribute specification, the compiler automatically sets the alignment for the declared variable or field to the largest alignment which is ever used for any data type on the target machine you are compiling for". Is this what we want here? Reid. > #else >union U { > double D; > > > > ___ > llvm-commits mailing list > llvm-commits@cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
Re: [llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
> This compiled on my 3.4.6 compiler on Linux just fine before the patch. > What was the error you were trying to fix? "Allignment Value not constant" was the error. This was gcc 3.4.4 > Are you sure this is right? In section 5.31 of the GCC Manual it > indicates that if an alignment size is not given with the aligned > attribute keyword then it defaults to: > > "the maximum useful alignment for the target machine you are compiling > for. Whenever you leave out the alignment factor in an `aligned' > attribute specification, the compiler automatically sets the alignment > for the declared variable or field to the largest alignment which is > ever used for any data type on the target machine you are compiling > for". > > Is this what we want here? I believe so. The alignment of that field needs to be sufficient for any data type put there. The non-gcc version does that with a union. My reading of the gcc manual is that without a value, this attribute does exactly that (and since doubles are not always the most constrained types, vectors tend to be, this is more general, though I doubt altivec vectors are going to be used directly by LLVM in small vectors anytime soon). Andrew ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
Re: [llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
On Oct 9, 2006, at 12:56 PM, Andrew Lenharth wrote: >> >> Is this what we want here? > > I believe so. I agree, Andrew's patch looks great to me. -Chris ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
Re: [llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
> Add a default parameter to a SmallVector constructor to allow it to > be called with just an initial length value, just like in std::vector. Ok. Should this be marked 'explicit'? -Chris > > --- > Diffs of the changes: (+1 -1) > > SmallVector.h |2 +- > 1 files changed, 1 insertion(+), 1 deletion(-) > > > Index: llvm/include/llvm/ADT/SmallVector.h > diff -u llvm/include/llvm/ADT/SmallVector.h:1.30 llvm/include/llvm/ > ADT/SmallVector.h:1.31 > --- llvm/include/llvm/ADT/SmallVector.h:1.30 Thu May 17 15:01:40 2007 > +++ llvm/include/llvm/ADT/SmallVector.h Thu Jun 28 15:27:24 2007 > @@ -442,7 +442,7 @@ >SmallVector() : SmallVectorImpl(NumTsAvailable) { >} > > - SmallVector(unsigned Size, const T &Value) > + SmallVector(unsigned Size, const T &Value = T()) > : SmallVectorImpl(NumTsAvailable) { > this->reserve(Size); > while (Size--) > > > > ___ > llvm-commits mailing list > llvm-commits@cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits
Re: [llvm-commits] CVS: llvm/include/llvm/ADT/SmallVector.h
>> Add a default parameter to a SmallVector constructor to allow it to >> be called with just an initial length value, just like in std::vector. > > Ok. > > Should this be marked 'explicit'? Yep. Good catch. Dan -- Dan Gohman, Cray Inc. ___ llvm-commits mailing list llvm-commits@cs.uiuc.edu http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits