X-Git-Url: https://git.saurik.com/wxWidgets.git/blobdiff_plain/c86f1403c3737c07d58676a203f4707942684a01..6443de026310552cacd68a6d0318e73d14929680:/src/common/dynarray.cpp diff --git a/src/common/dynarray.cpp b/src/common/dynarray.cpp index eb2b4e6be9..2d8e162378 100644 --- a/src/common/dynarray.cpp +++ b/src/common/dynarray.cpp @@ -17,14 +17,14 @@ #pragma implementation "dynarray.h" #endif -#include +#include "wx/wxprec.h" #ifdef __BORLANDC__ #pragma hdrstop #endif #include "wx/dynarray.h" -#include +#include "wx/intl.h" #include #include // for memmove @@ -51,23 +51,23 @@ // ctor wxBaseArray::wxBaseArray() { - m_uiSize = - m_uiCount = 0; - m_pItems = NULL; + m_nSize = + m_nCount = 0; + m_pItems = (long *) NULL; } // copy ctor wxBaseArray::wxBaseArray(const wxBaseArray& src) { - m_uiSize = // not src.m_uiSize to save memory - m_uiCount = src.m_uiCount; + m_nSize = // not src.m_nSize to save memory + m_nCount = src.m_nCount; - if ( m_uiSize != 0 ) { - m_pItems = new long[m_uiSize]; - memcpy(m_pItems, src.m_pItems, m_uiCount*sizeof(long)); + if ( m_nSize != 0 ) { + m_pItems = new long[m_nSize]; + memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(long)); } else - m_pItems = NULL; + m_pItems = (long *) NULL; } // assignment operator @@ -75,15 +75,15 @@ wxBaseArray& wxBaseArray::operator=(const wxBaseArray& src) { wxDELETEA(m_pItems); - m_uiSize = // not src.m_uiSize to save memory - m_uiCount = src.m_uiCount; + m_nSize = // not src.m_nSize to save memory + m_nCount = src.m_nCount; - if ( m_uiSize != 0 ) { - m_pItems = new long[m_uiSize]; - memcpy(m_pItems, src.m_pItems, m_uiCount*sizeof(long)); + if ( m_nSize != 0 ) { + m_pItems = new long[m_nSize]; + memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(long)); } else - m_pItems = NULL; + m_pItems = (long *) NULL; return *this; } @@ -92,24 +92,24 @@ wxBaseArray& wxBaseArray::operator=(const wxBaseArray& src) void wxBaseArray::Grow() { // only do it if no more place - if( m_uiCount == m_uiSize ) { - if( m_uiSize == 0 ) { + if( m_nCount == m_nSize ) { + if( m_nSize == 0 ) { // was empty, alloc some memory - m_uiSize = WX_ARRAY_DEFAULT_INITIAL_SIZE; - m_pItems = new long[m_uiSize]; + m_nSize = WX_ARRAY_DEFAULT_INITIAL_SIZE; + m_pItems = new long[m_nSize]; } else { // add 50% but not too much - size_t uiIncrement = m_uiSize < WX_ARRAY_DEFAULT_INITIAL_SIZE - ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_uiSize >> 1; - if ( uiIncrement > ARRAY_MAXSIZE_INCREMENT ) - uiIncrement = ARRAY_MAXSIZE_INCREMENT; - m_uiSize += uiIncrement; - long *pNew = new long[m_uiSize]; + 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; + m_nSize += nIncrement; + long *pNew = new long[m_nSize]; // copy data to new location - memcpy(pNew, m_pItems, m_uiCount*sizeof(long)); + memcpy(pNew, m_pItems, m_nCount*sizeof(long)); delete [] m_pItems; m_pItems = pNew; } @@ -125,56 +125,69 @@ wxBaseArray::~wxBaseArray() // clears the list void wxBaseArray::Clear() { - m_uiSize = - m_uiCount = 0; + m_nSize = + m_nCount = 0; wxDELETEA(m_pItems); } // pre-allocates memory (frees the previous data!) -void wxBaseArray::Alloc(size_t uiSize) +void wxBaseArray::Alloc(size_t nSize) { - wxASSERT( uiSize > 0 ); - // only if old buffer was not big enough - if ( uiSize > m_uiSize ) { + if ( nSize > m_nSize ) { wxDELETEA(m_pItems); - m_pItems = new long[uiSize]; - m_uiSize = uiSize; + m_pItems = new long[nSize]; + m_nSize = nSize; } - m_uiCount = 0; + m_nCount = 0; +} + +// minimizes the memory usage by freeing unused memory +void wxBaseArray::Shrink() +{ + // only do it if we have some memory to free + if( m_nCount < m_nSize ) { + // allocates exactly as much memory as we need + long *pNew = new long[m_nCount]; + + // copy data to new location + memcpy(pNew, m_pItems, m_nCount*sizeof(long)); + delete [] m_pItems; + m_pItems = pNew; + } } // searches the array for an item (forward or backwards) int wxBaseArray::Index(long lItem, bool bFromEnd) const { if ( bFromEnd ) { - if ( m_uiCount > 0 ) { - size_t ui = m_uiCount; + if ( m_nCount > 0 ) { + size_t n = m_nCount; do { - if ( m_pItems[--ui] == lItem ) - return ui; + if ( m_pItems[--n] == lItem ) + return n; } - while ( ui != 0 ); + while ( n != 0 ); } } else { - for( size_t ui = 0; ui < m_uiCount; ui++ ) { - if( m_pItems[ui] == lItem ) - return ui; + for( size_t n = 0; n < m_nCount; n++ ) { + if( m_pItems[n] == lItem ) + return n; } } - return NOT_FOUND; + return wxNOT_FOUND; } -// search for an item in a sorted array (binary search) -int wxBaseArray::Index(long lItem, CMPFUNC fnCompare) const +// search for a place to insert an item into a sorted array (binary search) +size_t wxBaseArray::IndexForInsert(long lItem, CMPFUNC fnCompare) const { size_t i, lo = 0, - hi = m_uiCount; + hi = m_nCount; int res; while ( lo < hi ) { @@ -185,67 +198,57 @@ int wxBaseArray::Index(long lItem, CMPFUNC fnCompare) const hi = i; else if ( res > 0 ) lo = i + 1; - else - return i; + else { + lo = i; + break; + } } - return NOT_FOUND; + return lo; } + +// search for an item in a sorted array (binary search) +int wxBaseArray::Index(long 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 wxBaseArray::Add(long lItem) { Grow(); - m_pItems[m_uiCount++] = lItem; + m_pItems[m_nCount++] = lItem; } // add item assuming the array is sorted with fnCompare function void wxBaseArray::Add(long lItem, CMPFUNC fnCompare) { - size_t i, - lo = 0, - hi = m_uiCount; - 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 = hi = i; - break; - } - } - - wxASSERT( lo == hi ); // I hope I got binary search right :-) - - Insert(lItem, lo); + Insert(lItem, IndexForInsert(lItem, fnCompare)); } // add item at the given position -void wxBaseArray::Insert(long lItem, size_t uiIndex) +void wxBaseArray::Insert(long lItem, size_t nIndex) { - wxCHECK_RET( uiIndex <= m_uiCount, _("bad index in wxArray::Insert") ); + wxCHECK_RET( nIndex <= m_nCount, wxT("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++; + memmove(&m_pItems[nIndex + 1], &m_pItems[nIndex], + (m_nCount - nIndex)*sizeof(long)); + m_pItems[nIndex] = lItem; + m_nCount++; } // removes item from array (by index) -void wxBaseArray::Remove(size_t uiIndex) +void wxBaseArray::RemoveAt(size_t nIndex) { - wxCHECK_RET( uiIndex <= m_uiCount, _("bad index in wxArray::Remove") ); + wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::RemoveAt") ); - memmove(&m_pItems[uiIndex], &m_pItems[uiIndex + 1], - (m_uiCount - uiIndex - 1)*sizeof(long)); - m_uiCount--; + memmove(&m_pItems[nIndex], &m_pItems[nIndex + 1], + (m_nCount - nIndex - 1)*sizeof(long)); + m_nCount--; } // removes item from array (by value) @@ -253,14 +256,14 @@ void wxBaseArray::Remove(long lItem) { int iIndex = Index(lItem); - wxCHECK_RET( iIndex != NOT_FOUND, - _("removing inexistent item in wxArray::Remove") ); + wxCHECK_RET( iIndex != wxNOT_FOUND, + wxT("removing inexistent item in wxArray::Remove") ); - Remove((size_t)iIndex); + RemoveAt((size_t)iIndex); } // sort array elements using passed comparaison function void wxBaseArray::Sort(CMPFUNC fCmp) { - qsort(m_pItems, m_uiCount, sizeof(long), fCmp); + qsort(m_pItems, m_nCount, sizeof(long), fCmp); }