X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/acf88ae62167d8d4b832b867ba24341ef8467ab9..b0cb01589f81b1794e07b82ff3d23f9757fb33d2:/src/common/dynarray.cpp diff --git a/src/common/dynarray.cpp b/src/common/dynarray.cpp index 25a7b4a31d..39db10d384 100644 --- a/src/common/dynarray.cpp +++ b/src/common/dynarray.cpp @@ -6,7 +6,7 @@ // Created: 12.09.97 // RCS-ID: $Id$ // Copyright: (c) 1998 Vadim Zeitlin -// Licence: wxWindows license +// Licence: wxWindows licence /////////////////////////////////////////////////////////////////////////////// // ============================================================================ @@ -53,7 +53,64 @@ wxCOMPILE_TIME_ASSERT( sizeof(long) <= sizeof(void *), // wxBaseArray - dynamic array of 'T's // ---------------------------------------------------------------------------- -#define _WX_DEFINE_BASEARRAY(T, name) \ +#define _WX_DEFINE_BASEARRAY_COMMON(T, name) \ +/* searches the array for an item (forward or backwards) */ \ +int name::Index(T lItem, bool bFromEnd) const \ +{ \ + if ( bFromEnd ) { \ + if ( size() > 0 ) { \ + size_t n = size(); \ + do { \ + if ( (*this)[--n] == lItem ) \ + return n; \ + } \ + while ( n != 0 ); \ + } \ + } \ + else { \ + for( size_t n = 0; n < size(); n++ ) { \ + if( (*this)[n] == lItem ) \ + return n; \ + } \ + } \ + \ + return wxNOT_FOUND; \ +} \ + \ +/* add item assuming the array is sorted with fnCompare function */ \ +void name::Add(T lItem, CMPFUNC fnCompare) \ +{ \ + Insert(lItem, IndexForInsert(lItem, fnCompare)); \ +} \ + \ + +#if wxUSE_STL + +#define _WX_DEFINE_BASEARRAY_NOCOMMON(T, name) \ +size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \ +{ \ + Predicate p(fnCompare); \ + const_iterator it = std::lower_bound(begin(), end(), lItem, p); \ + return it - begin(); \ +} \ + \ +int name::Index(T lItem, CMPFUNC fnCompare) const \ +{ \ + size_t n = IndexForInsert(lItem, fnCompare); \ + \ + return (n >= size() || \ + (*fnCompare)(&lItem, &(*this)[n])) ? wxNOT_FOUND : (int)n; \ +} \ + \ +void name::Shrink() \ +{ \ + name tmp(*this); \ + swap(tmp); \ +} + +#else // if !wxUSE_STL + +#define _WX_DEFINE_BASEARRAY_NOCOMMON(T, name) \ /* ctor */ \ name::name() \ { \ @@ -106,17 +163,37 @@ name& name::operator=(const name& src) \ return *this; \ } \ \ +/* allocate new buffer of the given size and move our data to it */ \ +bool name::Realloc(size_t nSize) \ +{ \ + T *pNew = new T[nSize]; \ + /* only grow if allocation succeeded */ \ + if ( !pNew ) \ + return false; \ + \ + m_nSize = nSize; \ + /* copy data to new location */ \ + memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \ + delete [] m_pItems; \ + m_pItems = pNew; \ + \ + return true; \ +} \ + \ /* grow the array */ \ void name::Grow(size_t nIncrement) \ { \ /* only do it if no more place */ \ - if( m_nCount == m_nSize ) { \ + if( (m_nCount == m_nSize) || ((m_nSize - m_nCount) < nIncrement) ) { \ if( m_nSize == 0 ) { \ - /* was empty, alloc some memory */ \ - m_pItems = new T[WX_ARRAY_DEFAULT_INITIAL_SIZE]; \ + /* was empty, determine initial size */ \ + size_t size = WX_ARRAY_DEFAULT_INITIAL_SIZE; \ + if (size < nIncrement) size = nIncrement; \ + /* allocate some memory */ \ + m_pItems = new T[size]; \ /* only grow if allocation succeeded */ \ if ( m_pItems ) { \ - m_nSize = WX_ARRAY_DEFAULT_INITIAL_SIZE; \ + m_nSize = size; \ } \ } \ else \ @@ -128,19 +205,34 @@ void name::Grow(size_t nIncrement) \ ndefIncrement = ARRAY_MAXSIZE_INCREMENT; \ if ( nIncrement < ndefIncrement ) \ nIncrement = ndefIncrement; \ - T *pNew = new T[m_nSize + nIncrement]; \ - /* only grow if allocation succeeded */ \ - if ( pNew ) { \ - m_nSize += nIncrement; \ - /* copy data to new location */ \ - memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \ - delete [] m_pItems; \ - m_pItems = pNew; \ - } \ + Realloc(m_nSize + nIncrement); \ } \ } \ } \ \ +/* make sure that the array has at least count elements */ \ +void name::SetCount(size_t count, T defval) \ +{ \ + if ( m_nSize < count ) \ + { \ + /* need to realloc memory: don't overallocate it here as if */ \ + /* SetCount() is called, it probably means that the caller */ \ + /* knows in advance how many elements there will be in the */ \ + /* array and so it won't be necessary to realloc it later */ \ + if ( !Realloc(count) ) \ + { \ + /* out of memory -- what can we do? */ \ + return; \ + } \ + } \ + \ + /* add new elements if we extend the array */ \ + while ( m_nCount < count ) \ + { \ + m_pItems[m_nCount++] = defval; \ + } \ +} \ + \ /* dtor */ \ name::~name() \ { \ @@ -186,31 +278,40 @@ void name::Shrink() \ memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \ delete [] m_pItems; \ m_pItems = pNew; \ + \ + /* update the size of the new block */ \ + m_nSize = m_nCount; \ } \ + /* else: don't do anything, better keep old memory block! */ \ } \ } \ \ -/* searches the array for an item (forward or backwards) */ \ -int name::Index(T lItem, bool bFromEnd) const \ +/* add item at the end */ \ +void name::Add(T lItem, size_t nInsert) \ { \ - if ( bFromEnd ) { \ - if ( m_nCount > 0 ) { \ - size_t n = m_nCount; \ - do { \ - if ( m_pItems[--n] == lItem ) \ - return n; \ - } \ - while ( n != 0 ); \ - } \ - } \ - else { \ - for( size_t n = 0; n < m_nCount; n++ ) { \ - if( m_pItems[n] == lItem ) \ - return n; \ - } \ - } \ + if (nInsert == 0) \ + return; \ + Grow(nInsert); \ + for (size_t i = 0; i < nInsert; i++) \ + m_pItems[m_nCount++] = lItem; \ +} \ \ - return wxNOT_FOUND; \ +/* add item at the given position */ \ +void name::Insert(T lItem, size_t nIndex, size_t nInsert) \ +{ \ + wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") ); \ + wxCHECK_RET( m_nCount <= m_nCount + nInsert, \ + wxT("array size overflow in wxArray::Insert") ); \ + \ + if (nInsert == 0) \ + return; \ + Grow(nInsert); \ + \ + memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \ + (m_nCount - nIndex)*sizeof(T)); \ + for (size_t i = 0; i < nInsert; i++) \ + m_pItems[nIndex + i] = lItem; \ + m_nCount += nInsert; \ } \ \ /* search for a place to insert item into sorted array (binary search) */ \ @@ -244,37 +345,10 @@ int name::Index(T lItem, CMPFUNC fnCompare) const \ { \ size_t n = IndexForInsert(lItem, fnCompare); \ \ - return n < m_nCount && m_pItems[n] == lItem ? (int)n : wxNOT_FOUND; \ -} \ - \ -/* add item at the end */ \ -void name::Add(T lItem, size_t nInsert) \ -{ \ - Grow(nInsert); \ - for (size_t i = 0; i < nInsert; i++) \ - m_pItems[m_nCount++] = lItem; \ -} \ - \ -/* add item assuming the array is sorted with fnCompare function */ \ -void name::Add(T lItem, CMPFUNC fnCompare) \ -{ \ - Insert(lItem, IndexForInsert(lItem, fnCompare)); \ -} \ - \ -/* add item at the given position */ \ -void name::Insert(T lItem, size_t nIndex, size_t nInsert) \ -{ \ - wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") ); \ - wxCHECK_RET( m_nCount <= m_nCount + nInsert, \ - wxT("array size overflow in wxArray::Insert") ); \ - \ - Grow(nInsert); \ - \ - memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \ - (m_nCount - nIndex)*sizeof(T)); \ - for (size_t i = 0; i < nInsert; i++) \ - m_pItems[nIndex + i] = lItem; \ - m_nCount += nInsert; \ + return (n >= m_nCount || \ + (*fnCompare)((const void *)(long)lItem, \ + ((const void *)(long)m_pItems[n]))) ? wxNOT_FOUND \ + : (int)n; \ } \ \ /* removes item from array (by index) */ \ @@ -304,11 +378,53 @@ void name::Remove(T lItem) \ void name::Sort(CMPFUNC fCmp) \ { \ qsort(m_pItems, m_nCount, sizeof(T), fCmp); \ +} \ + \ +void name::assign(const_iterator first, const_iterator last) \ +{ \ + clear(); \ + reserve(last - first); \ + for(; first != last; ++first) \ + push_back(*first); \ +} \ + \ +void name::assign(size_type n, const_reference v) \ +{ \ + clear(); \ + reserve(n); \ + for( size_type i = 0; i < n; ++i ) \ + push_back(v); \ +} \ + \ +void name::insert(iterator it, const_iterator first, const_iterator last) \ +{ \ + size_t nInsert = last - first, nIndex = it - begin(); \ + if (nInsert == 0) \ + return; \ + Grow(nInsert); \ + \ + memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \ + (m_nCount - nIndex)*sizeof(T)); \ + for (size_t i = 0; i < nInsert; ++i, ++it, ++first) \ + *it = *first; \ + m_nCount += nInsert; \ } +#endif + +#define _WX_DEFINE_BASEARRAY(T, name) \ + _WX_DEFINE_BASEARRAY_COMMON(T, name) \ + _WX_DEFINE_BASEARRAY_NOCOMMON(T, name) + _WX_DEFINE_BASEARRAY(const void *, wxBaseArrayPtrVoid) _WX_DEFINE_BASEARRAY(short, wxBaseArrayShort) _WX_DEFINE_BASEARRAY(int, wxBaseArrayInt) _WX_DEFINE_BASEARRAY(long, wxBaseArrayLong) -//_WX_DEFINE_BASEARRAY(double, wxBaseArrayDouble) +_WX_DEFINE_BASEARRAY(double, wxBaseArrayDouble) + +#if wxUSE_STL +#include "wx/arrstr.h" +_WX_DEFINE_BASEARRAY(wxString, wxBaseArrayStringBase) + +#endif