From 3093cef829d26137a14303c36d592ed817da1028 Mon Sep 17 00:00:00 2001 From: Vadim Zeitlin Date: Fri, 18 Sep 1998 21:35:44 +0000 Subject: [PATCH] wxBaseArray::Shrink() added git-svn-id: https://svn.wxwidgets.org/svn/wx/wxWidgets/trunk@754 c3d73ce0-8a6f-49c7-b76d-6d57e0e08775 --- include/wx/dynarray.h | 44 +++++++------- src/common/dynarray.cpp | 125 ++++++++++++++++++++++------------------ 2 files changed, 93 insertions(+), 76 deletions(-) diff --git a/include/wx/dynarray.h b/include/wx/dynarray.h index 022701069e..7174148866 100644 --- a/include/wx/dynarray.h +++ b/include/wx/dynarray.h @@ -86,20 +86,22 @@ public: /** @name memory management */ //@{ /// empties the list, but doesn't release memory - void Empty() { m_uiCount = 0; } + void Empty() { m_nCount = 0; } /// empties the list and releases memory void Clear(); /// preallocates memory for given number of items void Alloc(size_t uiSize); + /// minimizes the memory used by the array (frees unused memory) + void Shrink(); //@} /** @name simple accessors */ //@{ /// number of elements in the array - size_t Count() const { return m_uiCount; } - size_t GetCount() const { return m_uiCount; } + size_t Count() const { return m_nCount; } + size_t GetCount() const { return m_nCount; } /// is it empty? - bool IsEmpty() const { return m_uiCount == 0; } + bool IsEmpty() const { return m_nCount == 0; } //@} protected: @@ -111,7 +113,7 @@ protected: //@{ /// get item at position uiIndex (range checking is done in debug version) long& Item(size_t uiIndex) const - { wxASSERT( uiIndex < m_uiCount ); return m_pItems[uiIndex]; } + { wxASSERT( uiIndex < m_nCount ); return m_pItems[uiIndex]; } /// same as Item() long& operator[](size_t uiIndex) const { return Item(uiIndex); } //@} @@ -145,8 +147,8 @@ protected: private: void Grow(); // makes array bigger if needed - size_t m_uiSize, // current size of the array - m_uiCount; // current number of elements + size_t m_nSize, // current size of the array + m_nCount; // current number of elements long *m_pItems; // pointer to data }; @@ -173,9 +175,9 @@ public: \ { ((wxBaseArray *)this)->operator=((const wxBaseArray&)src); \ return *this; } \ \ - T& operator[](size_t uiIndex) const \ + T& operator[](size_t uiIndex) const \ { return (T&)(wxBaseArray::Item(uiIndex)); } \ - T& Item(size_t uiIndex) const \ + T& Item(size_t uiIndex) const \ { return (T&)(wxBaseArray::Item(uiIndex)); } \ T& Last() const \ { return (T&)(wxBaseArray::Item(Count() - 1)); } \ @@ -185,10 +187,10 @@ public: \ \ void Add(T Item) \ { wxBaseArray::Add((long)Item); } \ - void Insert(T Item, size_t uiIndex) \ + void Insert(T Item, size_t uiIndex) \ { wxBaseArray::Insert((long)Item, uiIndex) ; } \ \ - void Remove(size_t uiIndex) { wxBaseArray::Remove(uiIndex); } \ + void Remove(size_t uiIndex) { wxBaseArray::Remove(uiIndex); } \ void Remove(T Item) \ { int iIndex = Index(Item); \ wxCHECK2_MSG( iIndex != NOT_FOUND, return, \ @@ -228,9 +230,9 @@ public: \ m_fnCompare = src.m_fnCompare; \ return *this; } \ \ - T& operator[](size_t uiIndex) const \ + T& operator[](size_t uiIndex) const \ { return (T&)(wxBaseArray::Item(uiIndex)); } \ - T& Item(size_t uiIndex) const \ + T& Item(size_t uiIndex) const \ { return (T&)(wxBaseArray::Item(uiIndex)); } \ T& Last() const \ { return (T&)(wxBaseArray::Item(Count() - 1)); } \ @@ -241,12 +243,12 @@ public: \ void Add(T Item) \ { wxBaseArray::Add((long)Item, (CMPFUNC)m_fnCompare); } \ \ - void Remove(size_t uiIndex) { wxBaseArray::Remove(uiIndex); } \ + void Remove(size_t uiIndex) { wxBaseArray::Remove(uiIndex); } \ void Remove(T Item) \ { int iIndex = Index(Item); \ wxCHECK2_MSG( iIndex != NOT_FOUND, return, \ "removing inexisting element in wxArray::Remove" ); \ - wxBaseArray::Remove((size_t)iIndex); } \ + wxBaseArray::Remove((size_t)iIndex); } \ \ private: \ SCMPFUNC##T m_fnCompare; \ @@ -266,9 +268,9 @@ public: \ \ ~name(); \ \ - T& operator[](size_t uiIndex) const \ + T& operator[](size_t uiIndex) const \ { return *(T*)wxBaseArray::Item(uiIndex); } \ - T& Item(size_t uiIndex) const \ + T& Item(size_t uiIndex) const \ { return *(T*)wxBaseArray::Item(uiIndex); } \ T& Last() const \ { return *(T*)(wxBaseArray::Item(Count() - 1)); } \ @@ -279,16 +281,16 @@ public: \ void Add(const T* pItem) \ { wxBaseArray::Add((long)pItem); } \ \ - void Insert(const T& Item, size_t uiIndex); \ - void Insert(const T* pItem, size_t uiIndex) \ + void Insert(const T& Item, size_t uiIndex); \ + void Insert(const T* pItem, size_t uiIndex) \ { wxBaseArray::Insert((long)pItem, uiIndex); } \ \ void Empty(); \ \ - T* Detach(size_t uiIndex) \ + T* Detach(size_t uiIndex) \ { T* p = (T*)wxBaseArray::Item(uiIndex); \ wxBaseArray::Remove(uiIndex); return p; } \ - void Remove(size_t uiIndex); \ + void Remove(size_t uiIndex); \ \ void Sort(CMPFUNC##T fCmp) { wxBaseArray::Sort((CMPFUNC)fCmp); } \ \ diff --git a/src/common/dynarray.cpp b/src/common/dynarray.cpp index 305a1f07d4..4d13c80f0b 100644 --- a/src/common/dynarray.cpp +++ b/src/common/dynarray.cpp @@ -51,20 +51,20 @@ // ctor wxBaseArray::wxBaseArray() { - m_uiSize = - m_uiCount = 0; + 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 = (long *) NULL; @@ -82,12 +82,12 @@ wxBaseArray& wxBaseArray::operator=(const wxBaseArray& src) } #endif - 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 = (long *) NULL; @@ -99,24 +99,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; } @@ -132,44 +132,59 @@ 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 ); + wxASSERT( nSize > 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; } } @@ -181,7 +196,7 @@ int wxBaseArray::Index(long lItem, CMPFUNC fnCompare) const { size_t i, lo = 0, - hi = m_uiCount; + hi = m_nCount; int res; while ( lo < hi ) { @@ -202,7 +217,7 @@ int wxBaseArray::Index(long lItem, CMPFUNC fnCompare) const 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 @@ -210,7 +225,7 @@ void wxBaseArray::Add(long lItem, CMPFUNC fnCompare) { size_t i, lo = 0, - hi = m_uiCount; + hi = m_nCount; int res; while ( lo < hi ) { @@ -233,26 +248,26 @@ void wxBaseArray::Add(long lItem, CMPFUNC 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, "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::Remove(size_t nIndex) { - wxCHECK_RET( uiIndex <= m_uiCount, _("bad index in wxArray::Remove") ); + wxCHECK_RET( nIndex <= m_nCount, "bad index in wxArray::Remove" ); - 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) @@ -261,7 +276,7 @@ void wxBaseArray::Remove(long lItem) int iIndex = Index(lItem); wxCHECK_RET( iIndex != NOT_FOUND, - _("removing inexistent item in wxArray::Remove") ); + "removing inexistent item in wxArray::Remove" ); Remove((size_t)iIndex); } @@ -269,5 +284,5 @@ void wxBaseArray::Remove(long lItem) // 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); } -- 2.45.2