X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/f631cd8e128925bbf43b57b3dec0cd5ca217bdaf..dd9f8b6bb6935360a8271dc3e8749fb026b601a8:/include/wx/vector.h diff --git a/include/wx/vector.h b/include/wx/vector.h index 422e751b84..85d9257943 100644 --- a/include/wx/vector.h +++ b/include/wx/vector.h @@ -21,20 +21,112 @@ #else // !wxUSE_STL +#include "wx/utils.h" +#include "wx/meta/movable.h" +#include "wx/meta/if.h" + +#include "wx/beforestd.h" +#include // for placement new +#include "wx/afterstd.h" + +namespace wxPrivate +{ + +// These templates encapsulate memory operations for use by wxVector; there are +// two implementations, both in generic way for any C++ types and as an +// optimized version for "movable" types that uses realloc() and memmove(). + +// version for movable types: +template +struct wxVectorMemOpsMovable +{ + static void Free(T* array) + { free(array); } + + static T* Realloc(T* old, size_t newCapacity, size_t WXUNUSED(occupiedSize)) + { return (T*)realloc(old, newCapacity * sizeof(T)); } + + static void MemmoveBackward(T* dest, T* source, size_t count) + { memmove(dest, source, count * sizeof(T)); } + + static void MemmoveForward(T* dest, T* source, size_t count) + { memmove(dest, source, count * sizeof(T)); } +}; + +// generic version for non-movable types: +template +struct wxVectorMemOpsGeneric +{ + static void Free(T* array) + { ::operator delete(array); } + + static T* Realloc(T* old, size_t newCapacity, size_t occupiedSize) + { + T *mem = (T*)::operator new(newCapacity * sizeof(T)); + for ( size_t i = 0; i < occupiedSize; i++ ) + { + new(mem + i) T(old[i]); + old[i].~T(); + } + ::operator delete(old); + return mem; + } + + static void MemmoveBackward(T* dest, T* source, size_t count) + { + wxASSERT( dest < source ); + T* destptr = dest; + T* sourceptr = source; + for ( size_t i = count; i > 0; --i, ++destptr, ++sourceptr ) + { + new(destptr) T(*sourceptr); + sourceptr->~T(); + } + } + + static void MemmoveForward(T* dest, T* source, size_t count) + { + wxASSERT( dest > source ); + T* destptr = dest + count - 1; + T* sourceptr = source + count - 1; + for ( size_t i = count; i > 0; --i, --destptr, --sourceptr ) + { + new(destptr) T(*sourceptr); + sourceptr->~T(); + } + } +}; + + +} // namespace wxPrivate + template class wxVector { +private: + // This cryptic expression means "typedef Ops to wxVectorMemOpsMovable if + // type T is movable type, otherwise to wxVectorMemOpsGeneric". + // + // Note that we use typedef instead of privately deriving from this (which + // would allowed us to omit "Ops::" prefixes below) to keep VC6 happy, + // it can't compile code that derives from wxIf<...>::value. + typedef typename wxIf< wxIsMovable::value, + wxPrivate::wxVectorMemOpsMovable, + wxPrivate::wxVectorMemOpsGeneric >::value + Ops; + public: typedef size_t size_type; typedef T value_type; typedef value_type* iterator; + typedef const value_type* const_iterator; typedef value_type& reference; - wxVector() : m_allocsize(16), m_size(0), m_capacity(0), m_objects(0) {} + wxVector() : m_size(0), m_capacity(0), m_values(NULL) {} wxVector(const wxVector& c) { - wxCHECK2(Copy(c), return); + Copy(c); } ~wxVector() @@ -44,19 +136,35 @@ public: void clear() { - for (size_type i = 0; i < size(); i++) - delete m_objects[i]; - free(m_objects); - m_objects = 0; + // call destructors of stored objects: + for ( size_type i = 0; i < m_size; i++ ) + { + m_values[i].~T(); + } + + Ops::Free(m_values); + m_values = NULL; m_size = m_capacity = 0; } void reserve(size_type n) { - if ( !Alloc(n) ) - { - wxFAIL_MSG( _T("out of memory in wxVector::reserve()") ); - } + if ( n <= m_capacity ) + return; + + // increase the size twice, unless we're already too big or unless + // more is requested + // + // NB: casts to size_type are needed to suppress mingw32 warnings about + // mixing enums and ints in the same expression + const size_type increment = m_size > 0 + ? wxMin(m_size, (size_type)ALLOC_MAX_SIZE) + : (size_type)ALLOC_INITIAL_SIZE; + if ( m_capacity + increment > n ) + n = m_capacity + increment; + + m_values = Ops::Realloc(m_values, n * sizeof(value_type), m_size); + m_capacity = n; } size_type size() const @@ -76,31 +184,41 @@ public: wxVector& operator=(const wxVector& vb) { - wxCHECK(Copy(vb), *this); + Copy(vb); return *this; } - void push_back(const value_type& o) + void push_back(const value_type& v) { - wxCHECK2(Alloc(size() + 1), return); - Append(new value_type(o)); + reserve(size() + 1); + + // use placement new to initialize new object in preallocated place in + // m_values and store 'v' in it: + void* const place = m_values + m_size; + new(place) value_type(v); + + // only increase m_size if the ctor didn't throw an exception; notice + // that if it _did_ throw, everything is OK, because we only increased + // vector's capacity so far and possibly written some data to + // uninitialized memory at the end of m_values + m_size++; } void pop_back() { - RemoveAt(size() - 1); + erase(end() - 1); } const value_type& at(size_type idx) const { wxASSERT(idx < m_size); - return *m_objects[idx]; + return m_values[idx]; } value_type& at(size_type idx) { wxASSERT(idx < m_size); - return *m_objects[idx]; + return m_values[idx]; } const value_type& operator[](size_type idx) const { return at(idx); } @@ -110,119 +228,121 @@ public: const value_type& back() const { return at(size() - 1); } value_type& back() { return at(size() - 1); } - iterator begin() { return m_objects[0]; } - iterator end() { return m_objects[size()]; } + const_iterator begin() const { return m_values; } + iterator begin() { return m_values; } + const_iterator end() const { return m_values + size(); } + iterator end() { return m_values + size(); } - iterator erase(iterator first, iterator last) + iterator insert(iterator it, const value_type& v = value_type()) { - size_type idx = first - begin(); - RemoveAt(idx, last - first); + // NB: this must be done before reserve(), because reserve() + // invalidates iterators! + const size_t idx = it - begin(); + const size_t after = end() - it; + + reserve(size() + 1); + + // unless we're inserting at the end, move following elements out of + // the way: + if ( after > 0 ) + { + Ops::MemmoveForward(m_values + idx + 1, m_values + idx, after); + } + +#if wxUSE_EXCEPTIONS + try + { +#endif + // use placement new to initialize new object in preallocated place + // in m_values and store 'v' in it: + void* const place = m_values + idx; + new(place) value_type(v); +#if wxUSE_EXCEPTIONS + } + catch ( ... ) + { + // if the ctor threw an exception, we need to move all the elements + // back to their original positions in m_values + if ( after > 0 ) + { + Ops::MemmoveBackward(m_values + idx, m_values + idx + 1, after); + } + + throw; // rethrow the exception + } +#endif // wxUSE_EXCEPTIONS + + // increment m_size only if ctor didn't throw -- if it did, we'll be + // left with m_values larger than necessary, but number of elements will + // be the same + m_size++; + return begin() + idx; } + iterator erase(iterator it) { - size_type idx = it - begin(); - RemoveAt(idx); - return begin() + idx; + return erase(it, it + 1); } - iterator insert(iterator it, const value_type& v = value_type()) + iterator erase(iterator first, iterator last) { - wxCHECK2(Alloc(size() + 1), return 0); - size_type idx = it - begin(); - InsertAt(new value_type(v), idx); - return begin() + idx; - } + if ( first == last ) + return first; + wxASSERT( first < end() && last <= end() ); -private: - bool Alloc(size_type sz) - { - // work in multiples of m_allocsize; - sz = (sz / m_allocsize + 1) * m_allocsize; - if (sz <= m_capacity) - return true; + const size_type idx = first - begin(); + const size_type count = last - first; + const size_type after = end() - last; - // try to realloc - void *mem = realloc(m_objects, sizeof(value_type*) * sz); - if (! mem) - return false; // failed - // success - m_objects = (value_type **) mem; - m_capacity = sz; - return true; - } + // erase elements by calling their destructors: + for ( iterator i = first; i < last; ++i ) + i->~T(); - void Append(value_type *obj) - { - wxASSERT(m_size < m_capacity); - m_objects[m_size] = obj; - m_size++; - } + // once that's done, move following elements over to the freed space: + if ( after > 0 ) + { + Ops::MemmoveBackward(m_values + idx, m_values + idx + count, after); + } - void InsertAt(size_type idx, value_type *obj) - { - wxASSERT(idx <= m_size); - wxASSERT(m_size < m_capacity); - if (idx < m_size) - memmove( - m_objects + idx + 1, - m_objects + idx, - ( m_size - idx ) * sizeof(value_type*) ); + m_size -= count; - m_size++; + return begin() + idx; } - void RemoveAt(size_type idx) - { - wxASSERT(idx < m_size); - delete m_objects[idx]; - if (idx < m_size - 1) - memcpy( - m_objects + idx, - m_objects + idx + 1, - ( m_size - idx - 1 ) * sizeof(value_type*) ); - m_size--; - } +#if WXWIN_COMPATIBILITY_2_8 + wxDEPRECATED( size_type erase(size_type n) ); +#endif // WXWIN_COMPATIBILITY_2_8 - void RemoveAt(size_type idx, size_type count) - { - if (count == 0) - return; - wxASSERT(idx < m_size); - size_type i; - for (i = 0; i < count; i++) - delete m_objects[idx+1]; - if (idx < m_size - count) - memcpy( - m_objects + idx, - m_objects + idx + count, - ( m_size - idx - count ) * sizeof(value_type*) ); - m_size -= count; - } - bool Copy(const wxVector& vb) +private: + // VC6 can't compile static const int members + enum { ALLOC_INITIAL_SIZE = 16 }; + enum { ALLOC_MAX_SIZE = 4096 }; + + void Copy(const wxVector& vb) { clear(); - if (! Alloc(vb.size())) - return false; - - for (size_type i = 0; i < vb.size(); i++) - { - value_type *o = new value_type(vb.at(i)); - if (! o) - return false; - Append(o); - } + reserve(vb.size()); - return true; + for ( const_iterator i = vb.begin(); i != vb.end(); ++i ) + push_back(*i); } private: - size_type m_allocsize; size_type m_size, m_capacity; - value_type **m_objects; + value_type *m_values; }; +#if WXWIN_COMPATIBILITY_2_8 +template +inline typename wxVector::size_type wxVector::erase(size_type n) +{ + erase(begin() + n); + return n; +} +#endif // WXWIN_COMPATIBILITY_2_8 + #endif // wxUSE_STL/!wxUSE_STL #if WXWIN_COMPATIBILITY_2_8