X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/1311c7a9bbaefda6b68eee5c32c3309f163a8861..9f4de6b2cf06f53a98b28f53640f3b9ec8cf4182:/src/common/dynarray.cpp diff --git a/src/common/dynarray.cpp b/src/common/dynarray.cpp index ee700fbb0c..07ddf168df 100644 --- a/src/common/dynarray.cpp +++ b/src/common/dynarray.cpp @@ -2,7 +2,7 @@ // Name: dynarray.cpp // Purpose: implementation of wxBaseArray class // Author: Vadim Zeitlin -// Modified by: +// Modified by: // Created: 12.09.97 // RCS-ID: $Id$ // Copyright: (c) 1998 Vadim Zeitlin @@ -17,15 +17,17 @@ #pragma implementation "dynarray.h" #endif -#include +#include "wx/wxprec.h" #ifdef __BORLANDC__ #pragma hdrstop #endif #include "wx/dynarray.h" +#include "wx/intl.h" #include +#include // for memmove #ifndef max #define max(a, b) (((a) > (b)) ? (a) : (b)) @@ -43,175 +45,256 @@ // ============================================================================ // ---------------------------------------------------------------------------- -// wxBaseArray - dynamice array of 'long's +// wxBaseArray - dynamic array of 'T's // ---------------------------------------------------------------------------- -// ctor -wxBaseArray::wxBaseArray() -{ - m_uiSize = - m_uiCount = 0; - m_pItems = NULL; +#define _WX_DEFINE_BASEARRAY(T, name) \ +/* ctor */ \ +name::name() \ +{ \ + m_nSize = \ + m_nCount = 0; \ + m_pItems = (T *)NULL; \ +} \ + \ +/* copy ctor */ \ +name::name(const name& src) \ +{ \ + m_nSize = /* not src.m_nSize to save memory */ \ + m_nCount = src.m_nCount; \ + \ + if ( m_nSize != 0 ) { \ + m_pItems = new T[m_nSize]; \ + /* only copy if allocation succeeded */ \ + if ( m_pItems ) { \ + memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \ + } \ + else { \ + m_nSize = 0; \ + } \ + } \ + else \ + m_pItems = (T *) NULL; \ +} \ + \ +/* assignment operator */ \ +name& name::operator=(const name& src) \ +{ \ + wxDELETEA(m_pItems); \ + \ + m_nSize = /* not src.m_nSize to save memory */ \ + m_nCount = src.m_nCount; \ + \ + if ( m_nSize != 0 ){ \ + m_pItems = new T[m_nSize]; \ + /* only copy if allocation succeeded */ \ + if ( m_pItems ) { \ + memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \ + } \ + else { \ + m_nSize = 0; \ + } \ + } \ + else \ + m_pItems = (T *) NULL; \ + \ + return *this; \ +} \ + \ +/* grow the array */ \ +void name::Grow() \ +{ \ + /* only do it if no more place */ \ + if( m_nCount == m_nSize ) { \ + if( m_nSize == 0 ) { \ + /* was empty, alloc some memory */ \ + m_pItems = new T[WX_ARRAY_DEFAULT_INITIAL_SIZE]; \ + /* only grow if allocation succeeded */ \ + if ( m_pItems ) { \ + m_nSize = WX_ARRAY_DEFAULT_INITIAL_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; \ + } \ + } \ + } \ +} \ + \ +/* dtor */ \ +name::~name() \ +{ \ + wxDELETEA(m_pItems); \ +} \ + \ +/* clears the list */ \ +void name::Clear() \ +{ \ + m_nSize = \ + m_nCount = 0; \ + \ + wxDELETEA(m_pItems); \ +} \ + \ +/* pre-allocates memory (frees the previous data!) */ \ +void name::Alloc(size_t nSize) \ +{ \ + /* only if old buffer was not big enough */ \ + if ( nSize > m_nSize ) { \ + wxDELETEA(m_pItems); \ + m_nSize = 0; \ + m_pItems = new T[nSize]; \ + /* only alloc if allocation succeeded */ \ + if ( m_pItems ) { \ + m_nSize = nSize; \ + } \ + } \ + \ + m_nCount = 0; \ +} \ + \ +/* minimizes the memory usage by freeing unused memory */ \ +void name::Shrink() \ +{ \ + /* only do it if we have some memory to free */ \ + if( m_nCount < m_nSize ) { \ + /* allocates exactly as much memory as we need */ \ + T *pNew = new T[m_nCount]; \ + /* only shrink if allocation succeeded */ \ + if ( pNew ) { \ + /* copy data to new location */ \ + memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \ + delete [] m_pItems; \ + m_pItems = pNew; \ + } \ + } \ +} \ + \ +/* searches the array for an item (forward or backwards) */ \ +int name::Index(T lItem, bool bFromEnd) const \ +{ \ + 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; \ + } \ + } \ + \ + return wxNOT_FOUND; \ +} \ + \ +/* search for a place to insert item into sorted array (binary search) */ \ +size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \ +{ \ + size_t i, \ + lo = 0, \ + hi = m_nCount; \ + int res; \ + \ + while ( lo < hi ) { \ + i = (lo + hi)/2; \ + \ + res = (*fnCompare)((const void *)lItem, (const void *)(m_pItems[i])); \ + if ( res < 0 ) \ + hi = i; \ + else if ( res > 0 ) \ + lo = i + 1; \ + else { \ + lo = i; \ + break; \ + } \ + } \ + \ + return lo; \ +} \ + \ +/* search for an item in a sorted array (binary search) */ \ +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) \ +{ \ + Grow(); \ + 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) \ +{ \ + wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") ); \ + \ + Grow(); \ + \ + memmove(&m_pItems[nIndex + 1], &m_pItems[nIndex], \ + (m_nCount - nIndex)*sizeof(T)); \ + m_pItems[nIndex] = lItem; \ + m_nCount++; \ +} \ + \ +/* removes item from array (by index) */ \ +void name::RemoveAt(size_t nIndex) \ +{ \ + wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::RemoveAt") ); \ + \ + memmove(&m_pItems[nIndex], &m_pItems[nIndex + 1], \ + (m_nCount - nIndex - 1)*sizeof(T)); \ + m_nCount--; \ +} \ + \ +/* removes item from array (by value) */ \ +void name::Remove(T lItem) \ +{ \ + int iIndex = Index(lItem); \ + \ + wxCHECK_RET( iIndex != wxNOT_FOUND, \ + wxT("removing inexistent item in wxArray::Remove") ); \ + \ + RemoveAt((size_t)iIndex); \ +} \ + \ +/* sort array elements using passed comparaison function */ \ +void name::Sort(CMPFUNC fCmp) \ +{ \ + qsort(m_pItems, m_nCount, sizeof(T), fCmp); \ } -// copy ctor -wxBaseArray::wxBaseArray(const wxBaseArray& src) -{ - m_uiSize = src.m_uiSize; - m_uiCount = src.m_uiCount; +_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) - if ( m_uiSize != 0 ) - m_pItems = new long[m_uiSize]; - else - m_pItems = NULL; - - if ( m_uiCount != 0 ) - memcpy(m_pItems, src.m_pItems, m_uiCount*sizeof(long)); -} - -// copy operator -wxBaseArray& wxBaseArray::operator=(const wxBaseArray& src) -{ - DELETEA(m_pItems); - - m_uiSize = src.m_uiSize; - m_uiCount = src.m_uiCount; - - if ( m_uiSize != 0 ) - m_pItems = new long[m_uiSize]; - else - m_pItems = NULL; - - if ( m_uiCount != 0 ) - memcpy(m_pItems, src.m_pItems, m_uiCount*sizeof(long)); - - return *this; -} - -// grow the array -void wxBaseArray::Grow() -{ - // only do it if no more place - if( m_uiCount == m_uiSize ) { - if( m_uiSize == 0 ) { - // was empty, alloc some memory - m_uiSize = WX_ARRAY_DEFAULT_INITIAL_SIZE; - m_pItems = new long[m_uiSize]; - } - else - { - // add 50% but not too much - uint uiIncrement = m_uiSize >> 1; - if ( uiIncrement > ARRAY_MAXSIZE_INCREMENT ) - uiIncrement = ARRAY_MAXSIZE_INCREMENT; - m_uiSize += uiIncrement; - long *pNew = new long[m_uiSize]; - - // copy data to new location - memcpy(pNew, m_pItems, m_uiCount*sizeof(long)); - delete [] m_pItems; - m_pItems = pNew; - } - } -} - -// dtor -wxBaseArray::~wxBaseArray() -{ - DELETEA(m_pItems); -} - -// clears the list -void wxBaseArray::Clear() -{ - m_uiSize = - m_uiCount = 0; - - DELETEA(m_pItems); - m_pItems = NULL; -} - -// pre-allocates memory (frees the previous data!) -void wxBaseArray::Alloc(uint uiSize) -{ - wxASSERT( uiSize > 0 ); - - // only if old buffer was not big enough - if ( uiSize > m_uiSize ) { - DELETEA(m_pItems); - m_pItems = new long[uiSize]; - m_uiSize = uiSize; - } - - m_uiCount = 0; -} - -// searches the array for an item (forward or backwards) -int wxBaseArray::Index(long lItem, bool bFromEnd) const -{ - if ( bFromEnd ) { - if ( m_uiCount > 0 ) { - uint ui = m_uiCount; - do { - if ( m_pItems[--ui] == lItem ) - return ui; - } - while ( ui != 0 ); - } - } - else { - for( uint ui = 0; ui < m_uiCount; ui++ ) { - if( m_pItems[ui] == lItem ) - return ui; - } - } - - return NOT_FOUND; -} - -// add item at the end -void wxBaseArray::Add(long lItem) -{ - Grow(); - m_pItems[m_uiCount++] = lItem; -} - -// add item at the given position -void wxBaseArray::Insert(long lItem, uint uiIndex) -{ - wxCHECK_RET( uiIndex <= m_uiCount, "bad index in wxArray::Insert" ); - - Grow(); - - memmove(&m_pItems[uiIndex + 1], &m_pItems[uiIndex], - (m_uiCount - uiIndex)*sizeof(long)); - m_pItems[uiIndex] = lItem; - m_uiCount++; -} - -// removes item from array (by index) -void wxBaseArray::Remove(uint uiIndex) -{ - wxCHECK_RET( uiIndex <= m_uiCount, "bad index in wxArray::Remove" ); - - memmove(&m_pItems[uiIndex], &m_pItems[uiIndex + 1], - (m_uiCount - uiIndex - 1)*sizeof(long)); - m_uiCount--; -} - -// removes item from array (by value) -void wxBaseArray::Remove(long lItem) -{ - int iIndex = Index(lItem); - - wxCHECK_RET( iIndex != NOT_FOUND, - "removing inexistent item in wxArray::Remove" ); - - Remove((uint)iIndex); -} - -// sort array elements using passed comparaison function -void wxBaseArray::Sort(CMPFUNC fCmp) -{ - qsort(m_pItems, m_uiCount, sizeof(long), fCmp); -}