X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/f1322419da01a8ba68c720fef65357433a330cf8..878711c01c1b9ad5b97d35f379a048b8ce1bfb49:/src/common/dynarray.cpp diff --git a/src/common/dynarray.cpp b/src/common/dynarray.cpp index 07ddf168df..012c6077a3 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 /////////////////////////////////////////////////////////////////////////////// // ============================================================================ @@ -33,6 +33,11 @@ #define max(a, b) (((a) > (b)) ? (a) : (b)) #endif +// we cast the value to long from which we cast it to void * in IndexForInsert: +// this can't work if the pointers are not big enough +wxCOMPILE_TIME_ASSERT( sizeof(long) <= sizeof(void *), + wxArraySizeOfPtrLessSizeOfLong ); // < 32 symbols + // ============================================================================ // constants // ============================================================================ @@ -101,39 +106,76 @@ 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() \ +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 \ { \ - /* add 50% but not too much */ \ - size_t nIncrement = m_nSize < WX_ARRAY_DEFAULT_INITIAL_SIZE \ - ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1; \ - if ( nIncrement > ARRAY_MAXSIZE_INCREMENT ) \ - nIncrement = ARRAY_MAXSIZE_INCREMENT; \ - 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; \ - } \ + /* add at least 50% but not too much */ \ + size_t ndefIncrement = m_nSize < WX_ARRAY_DEFAULT_INITIAL_SIZE \ + ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1; \ + if ( ndefIncrement > ARRAY_MAXSIZE_INCREMENT ) \ + ndefIncrement = ARRAY_MAXSIZE_INCREMENT; \ + if ( nIncrement < ndefIncrement ) \ + nIncrement = ndefIncrement; \ + 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() \ { \ @@ -179,7 +221,11 @@ 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! */ \ } \ } \ \ @@ -217,7 +263,8 @@ size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \ while ( lo < hi ) { \ i = (lo + hi)/2; \ \ - res = (*fnCompare)((const void *)lItem, (const void *)(m_pItems[i])); \ + res = (*fnCompare)((const void *)(long)lItem, \ + (const void *)(long)(m_pItems[i])); \ if ( res < 0 ) \ hi = i; \ else if ( res > 0 ) \ @@ -236,14 +283,20 @@ 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; \ + return n < m_nCount && \ + (*fnCompare)((const void *)(long)lItem, \ + ((const void *)(long)m_pItems[n])) ? (int)n \ + : wxNOT_FOUND; \ } \ \ /* add item at the end */ \ -void name::Add(T lItem) \ +void name::Add(T lItem, size_t nInsert) \ { \ - Grow(); \ - m_pItems[m_nCount++] = lItem; \ + if (nInsert == 0) \ + return; \ + 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 */ \ @@ -253,26 +306,33 @@ void name::Add(T lItem, CMPFUNC fnCompare) \ } \ \ /* add item at the given position */ \ -void name::Insert(T lItem, size_t nIndex) \ +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(); \ + if (nInsert == 0) \ + return; \ + Grow(nInsert); \ \ - memmove(&m_pItems[nIndex + 1], &m_pItems[nIndex], \ + memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \ (m_nCount - nIndex)*sizeof(T)); \ - m_pItems[nIndex] = lItem; \ - m_nCount++; \ + for (size_t i = 0; i < nInsert; i++) \ + m_pItems[nIndex + i] = lItem; \ + m_nCount += nInsert; \ } \ \ /* removes item from array (by index) */ \ -void name::RemoveAt(size_t nIndex) \ +void name::RemoveAt(size_t nIndex, size_t nRemove) \ { \ - wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::RemoveAt") ); \ + wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArray::RemoveAt") ); \ + wxCHECK_RET( nIndex + nRemove <= m_nCount, \ + wxT("removing too many elements in wxArray::RemoveAt") ); \ \ - memmove(&m_pItems[nIndex], &m_pItems[nIndex + 1], \ - (m_nCount - nIndex - 1)*sizeof(T)); \ - m_nCount--; \ + memmove(&m_pItems[nIndex], &m_pItems[nIndex + nRemove], \ + (m_nCount - nIndex - nRemove)*sizeof(T)); \ + m_nCount -= nRemove; \ } \ \ /* removes item from array (by value) */ \