X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/5fd588d2298a44428ac66bef1e4d9fc73e18d4fd..77c8efc8c37da6d6a5e2e8022d21d1cd7d76371d:/include/wx/vector.h diff --git a/include/wx/vector.h b/include/wx/vector.h index fa01349ca5..d558e774e6 100644 --- a/include/wx/vector.h +++ b/include/wx/vector.h @@ -2,10 +2,11 @@ // Name: wx/vector.h // Purpose: STL vector clone // Author: Lindsay Mathieson -// Modified by: +// Modified by: Vaclav Slavik - make it a template // Created: 30.07.2001 -// Copyright: (c) 2001 Lindsay Mathieson -// Licence: wxWindows license +// Copyright: (c) 2001 Lindsay Mathieson , +// 2007 Vaclav Slavik +// Licence: wxWindows licence /////////////////////////////////////////////////////////////////////////////// #ifndef _WX_VECTOR_H_ @@ -13,101 +14,261 @@ #include "wx/defs.h" -class WXDLLEXPORT wxVectorBase +#if wxUSE_STD_CONTAINERS + +#include +#include + +#define wxVector std::vector +template +inline void wxVectorSort(wxVector& v) +{ + std::sort(v.begin(), v.end()); +} + +#else // !wxUSE_STD_CONTAINERS + +#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. + // + // Note that bcc needs the extra parentheses for non-type template + // arguments to compile this expression. + 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; - size_type m_allocsize; - size_type m_size, - m_capacity; - void **m_objects; - -protected: - bool Alloc(size_type sz) - { - // work in multiples of m_allocsize; - sz = (sz / m_allocsize + 1) * m_allocsize; - if (sz <= m_capacity) - return true; - - // try to realloc - void *mem = realloc(m_objects, sizeof(void *) * sz); - if (! mem) - return false; // failed - // success - m_objects = (void **) mem; - m_capacity = sz; - return true; + 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) + { m_ptr -= n; return *this; } + reverse_iterator operator-(difference_type n) const + { return reverse_iterator(m_ptr + n); } + reverse_iterator& operator-=(difference_type n) + { 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; }; - // untyped destructor of elements - must be overriden - virtual void Free(void *) = 0; - // untyped copy constructor of elements - must be overriden - virtual void *Copy(const void *) const = 0; + wxVector() : m_size(0), m_capacity(0), m_values(NULL) {} - const void *GetItem(size_type idx) const + wxVector(size_type p_size) + : m_size(0), m_capacity(0), m_values(NULL) { - wxASSERT(idx >= 0 && idx < m_size); - return m_objects[idx]; - }; + reserve(p_size); + for ( size_t n = 0; n < p_size; n++ ) + push_back(value_type()); + } - void Append(void *obj) + wxVector(size_type p_size, const value_type& v) + : m_size(0), m_capacity(0), m_values(NULL) { - wxASSERT(m_size < m_capacity); - m_objects[m_size] = obj; - m_size++; - }; + reserve(p_size); + for ( size_t n = 0; n < p_size; n++ ) + push_back(v); + } - void RemoveAt(size_type idx) + wxVector(const wxVector& c) : m_size(0), m_capacity(0), m_values(NULL) { - wxASSERT(idx >= 0 && idx < m_size); - Free(m_objects[idx]); - if (idx < m_size - 1) - memcpy( - m_objects + idx, - m_objects + idx + 1, - ( m_size - idx - 1 ) * sizeof(void*) ); - m_size--; - }; + Copy(c); + } - bool copy(const wxVectorBase& vb) + ~wxVector() { clear(); - if (! Alloc(vb.size())) - return false; - - for (size_type i = 0; i < vb.size(); i++) - { - void *o = vb.Copy(vb.GetItem(i)); - if (! o) - return false; - Append(o); - }; + } - return true; - }; + void assign(size_type p_size, const value_type& v) + { + clear(); + reserve(p_size); + for ( size_t n = 0; n < p_size; n++ ) + push_back(v); + } -public: - wxVectorBase() : m_allocsize(16), m_size(0), m_capacity(0), m_objects(0) {} - virtual ~wxVectorBase() {} // calm down GCC + void swap(wxVector& v) + { + wxSwap(m_size, v.m_size); + wxSwap(m_capacity, v.m_capacity); + wxSwap(m_values, v.m_values); + } void clear() { - for (size_type i = 0; i < size(); i++) - Free(m_objects[i]); - free(m_objects); - m_objects = 0; - m_size = m_capacity = 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; + } + + void resize(size_type n) + { + if ( n < m_size ) + Shrink(n); + else if ( n > m_size ) + Extend(n, value_type()); + } + + void resize(size_type n, const value_type& v) + { + if ( n < m_size ) + Shrink(n); + else if ( n > m_size ) + Extend(n, v); + } size_type size() const { @@ -117,99 +278,227 @@ public: size_type capacity() const { return m_capacity; - }; + } bool empty() const { return size() == 0; - }; + } - wxVectorBase& operator = (const wxVectorBase& vb) + wxVector& operator=(const wxVector& vb) { - bool rc = copy(vb); - wxASSERT(rc); + if (this != &vb) + { + clear(); + Copy(vb); + } return *this; } + + void push_back(const value_type& v) + { + 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() + { + erase(end() - 1); + } + + const value_type& at(size_type idx) const + { + wxASSERT(idx < m_size); + return m_values[idx]; + } + + value_type& at(size_type idx) + { + wxASSERT(idx < m_size); + return m_values[idx]; + } + + const value_type& operator[](size_type idx) const { return at(idx); } + value_type& operator[](size_type idx) { return at(idx); } + const value_type& front() const { return at(0); } + value_type& front() { return at(0); } + const value_type& back() const { return at(size() - 1); } + value_type& back() { return at(size() - 1); } + + 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(); } + + 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()) + { + // 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); + + // the place where the new element is going to be inserted + value_type * const place = m_values + idx; + + // 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; + } + + iterator erase(iterator it) + { + return erase(it, it + 1); + } + + iterator erase(iterator first, iterator last) + { + if ( first == last ) + return first; + wxASSERT( first < end() && last <= end() ); + + const size_type idx = first - begin(); + const size_type count = last - first; + const size_type after = end() - last; + + // erase elements by calling their destructors: + for ( iterator i = first; i < last; ++i ) + i->~T(); + + // 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() + idx; + } + +#if WXWIN_COMPATIBILITY_2_8 + wxDEPRECATED( size_type erase(size_type n) ); +#endif // WXWIN_COMPATIBILITY_2_8 + +private: + // VC6 can't compile static const int members + enum { ALLOC_INITIAL_SIZE = 16 }; + enum { ALLOC_MAX_SIZE = 4096 }; + + void Copy(const wxVector& vb) + { + reserve(vb.size()); + + for ( const_iterator i = vb.begin(); i != vb.end(); ++i ) + push_back(*i); + } + +private: + void Shrink(size_type n) + { + for ( size_type i = n; i < m_size; i++ ) + m_values[i].~T(); + m_size = n; + } + + void Extend(size_type n, const value_type& v) + { + reserve(n); + for ( size_type i = m_size; i < n; i++ ) + push_back(v); + } + + size_type m_size, + m_capacity; + 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 + + + +namespace wxPrivate +{ + +// This is a helper for the wxVectorSort function, and should not be used +// directly in user's code. +template +struct wxVectorComparator +{ + static int + Compare(const void* pitem1, const void* pitem2, const void* ) + { + const T& item1 = *reinterpret_cast(pitem1); + const T& item2 = *reinterpret_cast(pitem2); + + if (item1 < item2) + return -1; + else if (item2 < item1) + return 1; + else + return 0; + } }; -#define WX_DECLARE_VECTORBASE(obj, cls)\ -private:\ - virtual void Free(void *o)\ - {\ - delete (obj *) o;\ - };\ - virtual void *Copy(const void *o) const\ - {\ - return new obj(*(obj *) o);\ - };\ -public:\ - cls() {}\ - cls(const cls& c)\ - {\ - bool rc = copy(c);\ - wxASSERT(rc);\ - }\ - ~cls()\ - {\ - clear();\ - } - -#define _WX_DECLARE_VECTOR(obj, cls, exp)\ -class exp cls : public wxVectorBase\ -{\ - WX_DECLARE_VECTORBASE(obj, cls);\ -public:\ - void push_back(const obj& o)\ - {\ - bool rc = Alloc(size() + 1);\ - wxASSERT(rc);\ - Append(new obj(o));\ - };\ - void pop_back()\ - {\ - RemoveAt(size() - 1);\ - };\ - const obj& at(size_type idx) const\ - {\ - return *(obj *) GetItem(idx);\ - };\ - obj& at(size_type idx)\ - {\ - return *(obj *) GetItem(idx);\ - };\ - const obj& operator[](size_type idx) const\ - {\ - return at(idx);\ - };\ - obj& operator[](size_type idx)\ - {\ - return at(idx);\ - };\ - const obj& front() const\ - {\ - return at(0);\ - };\ - obj& front()\ - {\ - return at(0);\ - };\ - const obj& back() const\ - {\ - return at(size() - 1);\ - };\ - obj& back()\ - {\ - return at(size() - 1);\ - };\ - size_type erase(size_type idx)\ - {\ - RemoveAt(idx);\ - return idx;\ - };\ +} // namespace wxPrivate + + + +template +void wxVectorSort(wxVector& v) +{ + wxQsort(v.begin(), v.size(), sizeof(T), + wxPrivate::wxVectorComparator::Compare, NULL); } -#define WX_DECLARE_VECTOR(obj, cls) \ - _WX_DECLARE_VECTOR(obj, cls, WXDLLEXPORT) -#endif // _WX_VECTOR_H_ +#endif // wxUSE_STD_CONTAINERS/!wxUSE_STD_CONTAINERS + +#if WXWIN_COMPATIBILITY_2_8 + #define WX_DECLARE_VECTORBASE(obj, cls) typedef wxVector cls + #define _WX_DECLARE_VECTOR(obj, cls, exp) WX_DECLARE_VECTORBASE(obj, cls) + #define WX_DECLARE_VECTOR(obj, cls) WX_DECLARE_VECTORBASE(obj, cls) +#endif // WXWIN_COMPATIBILITY_2_8 + +#endif // _WX_VECTOR_H_