X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/2d615fe9336b30558216af831eb52b598af336c9..c39058f631b3a53682f00807a60bfff6c5aa2b7c:/include/wx/vector.h diff --git a/include/wx/vector.h b/include/wx/vector.h index 1132087a5e..e2faf83569 100644 --- a/include/wx/vector.h +++ b/include/wx/vector.h @@ -22,20 +22,154 @@ #else // !wxUSE_STL #include "wx/utils.h" +#include "wx/scopeguard.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 size_t difference_type; typedef T value_type; + typedef value_type* pointer; typedef value_type* iterator; typedef const value_type* const_iterator; typedef value_type& reference; + class reverse_iterator + { + public: + reverse_iterator() : m_ptr(NULL) { } + wxEXPLICIT reverse_iterator(iterator it) : m_ptr(it) { } + reverse_iterator(const reverse_iterator& it) : m_ptr(it.m_ptr) { } + + reference operator*() const { return *m_ptr; } + pointer operator->() const { return m_ptr; } + + iterator base() const { return m_ptr; } + + reverse_iterator& operator++() + { --m_ptr; return *this; } + reverse_iterator operator++(int) + { reverse_iterator tmp = *this; --m_ptr; return tmp; } + reverse_iterator& operator--() + { ++m_ptr; return *this; } + reverse_iterator operator--(int) + { reverse_iterator tmp = *this; ++m_ptr; return tmp; } + + reverse_iterator operator+(difference_type n) const + { return reverse_iterator(m_ptr - n); } + reverse_iterator& operator+=(difference_type n) + { return m_ptr -= n; return *this; } + reverse_iterator operator-(difference_type n) const + { return reverse_iterator(m_ptr + n); } + reverse_iterator& operator-=(difference_type n) + { return m_ptr += n; return *this; } + + reference operator[](difference_type n) const + { return *(*this + n); } + + bool operator ==(const reverse_iterator& it) const + { return m_ptr == it.m_ptr; } + bool operator !=(const reverse_iterator& it) const + { return m_ptr != it.m_ptr; } + + private: + value_type *m_ptr; + }; + wxVector() : m_size(0), m_capacity(0), m_values(NULL) {} - wxVector(const wxVector& c) + wxVector(const wxVector& c) : m_size(0), m_capacity(0), m_values(NULL) { Copy(c); } @@ -47,9 +181,16 @@ public: void clear() { - delete[] m_values; + // 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; + m_size = + m_capacity = 0; } void reserve(size_type n) @@ -59,22 +200,16 @@ public: // increase the size twice, unless we're already too big or unless // more is requested - const size_type increment = (m_size > 0) - ? wxMin(m_size, ALLOC_MAX_SIZE) - : ALLOC_INITIAL_SIZE; + // + // 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; - value_type *mem = new value_type[n]; - - if ( m_values ) - { - for ( size_type i = 0; i < m_size; ++i ) - mem[i] = m_values[i]; - delete[] m_values; - } - - m_values = mem; + m_values = Ops::Realloc(m_values, n * sizeof(value_type), m_size); m_capacity = n; } @@ -95,6 +230,7 @@ public: wxVector& operator=(const wxVector& vb) { + clear(); Copy(vb); return *this; } @@ -102,7 +238,17 @@ public: void push_back(const value_type& v) { reserve(size() + 1); - m_values[m_size++] = v; + + // 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() @@ -134,18 +280,40 @@ public: const_iterator end() const { return m_values + size(); } iterator end() { return m_values + size(); } + reverse_iterator rbegin() { return reverse_iterator(end() - 1); } + reverse_iterator rend() { return reverse_iterator(begin() - 1); } + iterator insert(iterator it, const value_type& v = value_type()) { - size_t idx = it - begin(); + // 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 values out of - // the way: - for ( size_t n = m_size; n != idx; --n ) - m_values[n] = m_values[n-1]; + // the place where the new element is going to be inserted + value_type * const place = m_values + idx; - m_values[idx] = v; + // unless we're inserting at the end, move following elements out of + // the way: + if ( after > 0 ) + Ops::MemmoveForward(place + 1, place, after); + + // if the ctor called below throws an exception, we need to move all + // the elements back to their original positions in m_values + wxScopeGuard moveBack = wxMakeGuard( + Ops::MemmoveBackward, place, place + 1, after); + if ( !after ) + moveBack.Dismiss(); + + // use placement new to initialize new object in preallocated place in + // m_values and store 'v' in it: + new(place) value_type(v); + + // now that we did successfully add the new element, increment the size + // and disable moving the items back + moveBack.Dismiss(); m_size++; return begin() + idx; @@ -162,20 +330,23 @@ public: return first; wxASSERT( first < end() && last <= end() ); - size_type index = first - begin(); - size_type count = last - first; + const size_type idx = first - begin(); + const size_type count = last - first; + const size_type after = end() - last; - // move the remaining values over to the freed space: - for ( iterator i = last; i < end(); ++i ) - *(i - count) = *i; + // erase elements by calling their destructors: + for ( iterator i = first; i < last; ++i ) + i->~T(); - // erase items behind the new end of m_values: - for ( iterator i = end() - count; i < end(); ++i ) - *i = value_type(); + // 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); + } m_size -= count; - return begin() + index; + return begin() + idx; } #if WXWIN_COMPATIBILITY_2_8 @@ -183,12 +354,12 @@ public: #endif // WXWIN_COMPATIBILITY_2_8 private: - static const size_type ALLOC_INITIAL_SIZE = 16; - static const size_type ALLOC_MAX_SIZE = 4096; + // VC6 can't compile static const int members + enum { ALLOC_INITIAL_SIZE = 16 }; + enum { ALLOC_MAX_SIZE = 4096 }; void Copy(const wxVector& vb) { - clear(); reserve(vb.size()); for ( const_iterator i = vb.begin(); i != vb.end(); ++i ) @@ -203,7 +374,7 @@ private: #if WXWIN_COMPATIBILITY_2_8 template -typename wxVector::size_type wxVector::erase(size_type n) +inline typename wxVector::size_type wxVector::erase(size_type n) { erase(begin() + n); return n;