1 ///////////////////////////////////////////////////////////////////////////////
2 // Name: src/common/dynarray.cpp
3 // Purpose: implementation of wxBaseArray class
4 // Author: Vadim Zeitlin
8 // Copyright: (c) 1998 Vadim Zeitlin <zeitlin@dptmaths.ens-cachan.fr>
9 // Licence: wxWindows licence
10 ///////////////////////////////////////////////////////////////////////////////
12 // ============================================================================
14 // ============================================================================
16 // For compilers that support precompilation, includes "wx.h".
17 #include "wx/wxprec.h"
24 #include "wx/dynarray.h"
29 #include <string.h> // for memmove
31 // we cast the value to long from which we cast it to void * in IndexForInsert:
32 // this can't work if the pointers are not big enough
33 wxCOMPILE_TIME_ASSERT( sizeof(wxUIntPtr
) <= sizeof(void *),
34 wxArraySizeOfPtrLessSizeOfLong
); // < 32 symbols
36 // ============================================================================
38 // ============================================================================
40 // size increment = max(50% of current size, ARRAY_MAXSIZE_INCREMENT)
41 #define ARRAY_MAXSIZE_INCREMENT 4096
43 // ============================================================================
45 // ============================================================================
47 // ----------------------------------------------------------------------------
48 // wxBaseArray - dynamic array of 'T's
49 // ----------------------------------------------------------------------------
51 #define _WX_DEFINE_BASEARRAY_COMMON(T, name) \
52 /* searches the array for an item (forward or backwards) */ \
53 int name::Index(T lItem, bool bFromEnd) const \
59 if ( (*this)[--n] == lItem ) \
66 for( size_t n = 0; n < size(); n++ ) { \
67 if( (*this)[n] == lItem ) \
75 /* add item assuming the array is sorted with fnCompare function */ \
76 size_t name::Add(T lItem, CMPFUNC fnCompare) \
78 size_t idx = IndexForInsert(lItem, fnCompare); \
85 #define _WX_DEFINE_BASEARRAY_NOCOMMON(T, name) \
86 size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \
88 Predicate p((SCMPFUNC)fnCompare); \
89 const_iterator it = std::lower_bound(begin(), end(), lItem, p); \
90 return it - begin(); \
93 int name::Index(T lItem, CMPFUNC fnCompare) const \
95 Predicate p((SCMPFUNC)fnCompare); \
96 const_iterator it = std::lower_bound(begin(), end(), lItem, p); \
97 return (it != end() && !p(lItem, *it)) ? \
98 (int)(it - begin()) : wxNOT_FOUND; \
101 void name::Shrink() \
107 #else // if !wxUSE_STL
109 #define _WX_DEFINE_BASEARRAY_NOCOMMON(T, name) \
115 m_pItems = (T *)NULL; \
119 name::name(const name& src) \
121 m_nSize = /* not src.m_nSize to save memory */ \
122 m_nCount = src.m_nCount; \
124 if ( m_nSize != 0 ) { \
125 m_pItems = new T[m_nSize]; \
126 /* only copy if allocation succeeded */ \
128 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \
135 m_pItems = (T *) NULL; \
138 /* assignment operator */ \
139 name& name::operator=(const name& src) \
141 wxDELETEA(m_pItems); \
143 m_nSize = /* not src.m_nSize to save memory */ \
144 m_nCount = src.m_nCount; \
146 if ( m_nSize != 0 ){ \
147 m_pItems = new T[m_nSize]; \
148 /* only copy if allocation succeeded */ \
150 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \
157 m_pItems = (T *) NULL; \
162 /* allocate new buffer of the given size and move our data to it */ \
163 bool name::Realloc(size_t nSize) \
165 T *pNew = new T[nSize]; \
166 /* only grow if allocation succeeded */ \
171 /* copy data to new location */ \
172 memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \
173 delete [] m_pItems; \
179 /* grow the array */ \
180 void name::Grow(size_t nIncrement) \
182 /* only do it if no more place */ \
183 if( (m_nCount == m_nSize) || ((m_nSize - m_nCount) < nIncrement) ) { \
184 if( m_nSize == 0 ) { \
185 /* was empty, determine initial size */ \
186 size_t size = WX_ARRAY_DEFAULT_INITIAL_SIZE; \
187 if (size < nIncrement) size = nIncrement; \
188 /* allocate some memory */ \
189 m_pItems = new T[size]; \
190 /* only grow if allocation succeeded */ \
197 /* add at least 50% but not too much */ \
198 size_t ndefIncrement = m_nSize < WX_ARRAY_DEFAULT_INITIAL_SIZE \
199 ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1; \
200 if ( ndefIncrement > ARRAY_MAXSIZE_INCREMENT ) \
201 ndefIncrement = ARRAY_MAXSIZE_INCREMENT; \
202 if ( nIncrement < ndefIncrement ) \
203 nIncrement = ndefIncrement; \
204 Realloc(m_nSize + nIncrement); \
209 /* make sure that the array has at least count elements */ \
210 void name::SetCount(size_t count, T defval) \
212 if ( m_nSize < count ) \
214 /* need to realloc memory: don't overallocate it here as if */ \
215 /* SetCount() is called, it probably means that the caller */ \
216 /* knows in advance how many elements there will be in the */ \
217 /* array and so it won't be necessary to realloc it later */ \
218 if ( !Realloc(count) ) \
220 /* out of memory -- what can we do? */ \
225 /* add new elements if we extend the array */ \
226 while ( m_nCount < count ) \
228 m_pItems[m_nCount++] = defval; \
235 wxDELETEA(m_pItems); \
238 /* clears the list */ \
244 wxDELETEA(m_pItems); \
247 /* minimizes the memory usage by freeing unused memory */ \
248 void name::Shrink() \
250 /* only do it if we have some memory to free */ \
251 if( m_nCount < m_nSize ) { \
252 /* allocates exactly as much memory as we need */ \
253 T *pNew = new T[m_nCount]; \
254 /* only shrink if allocation succeeded */ \
256 /* copy data to new location */ \
257 memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \
258 delete [] m_pItems; \
261 /* update the size of the new block */ \
262 m_nSize = m_nCount; \
264 /* else: don't do anything, better keep old memory block! */ \
268 /* add item at the end */ \
269 void name::Add(T lItem, size_t nInsert) \
274 for (size_t i = 0; i < nInsert; i++) \
275 m_pItems[m_nCount++] = lItem; \
278 /* add item at the given position */ \
279 void name::Insert(T lItem, size_t nIndex, size_t nInsert) \
281 wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") ); \
282 wxCHECK_RET( m_nCount <= m_nCount + nInsert, \
283 wxT("array size overflow in wxArray::Insert") ); \
289 memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \
290 (m_nCount - nIndex)*sizeof(T)); \
291 for (size_t i = 0; i < nInsert; i++) \
292 m_pItems[nIndex + i] = lItem; \
293 m_nCount += nInsert; \
296 /* search for a place to insert item into sorted array (binary search) */ \
297 size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \
304 while ( lo < hi ) { \
307 res = (*fnCompare)((const void *)(wxUIntPtr)lItem, \
308 (const void *)(wxUIntPtr)(m_pItems[i])); \
311 else if ( res > 0 ) \
322 /* search for an item in a sorted array (binary search) */ \
323 int name::Index(T lItem, CMPFUNC fnCompare) const \
325 size_t n = IndexForInsert(lItem, fnCompare); \
327 return (n >= m_nCount || \
328 (*fnCompare)((const void *)(wxUIntPtr)lItem, \
329 ((const void *)(wxUIntPtr)m_pItems[n]))) \
334 /* removes item from array (by index) */ \
335 void name::RemoveAt(size_t nIndex, size_t nRemove) \
337 wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArray::RemoveAt") ); \
338 wxCHECK_RET( nIndex + nRemove <= m_nCount, \
339 wxT("removing too many elements in wxArray::RemoveAt") ); \
341 memmove(&m_pItems[nIndex], &m_pItems[nIndex + nRemove], \
342 (m_nCount - nIndex - nRemove)*sizeof(T)); \
343 m_nCount -= nRemove; \
346 /* removes item from array (by value) */ \
347 void name::Remove(T lItem) \
349 int iIndex = Index(lItem); \
351 wxCHECK_RET( iIndex != wxNOT_FOUND, \
352 wxT("removing inexistent item in wxArray::Remove") ); \
354 RemoveAt((size_t)iIndex); \
357 /* sort array elements using passed comparaison function */ \
358 void name::Sort(CMPFUNC fCmp) \
360 qsort(m_pItems, m_nCount, sizeof(T), fCmp); \
363 void name::assign(const_iterator first, const_iterator last) \
366 reserve(last - first); \
367 for(; first != last; ++first) \
371 void name::assign(size_type n, const_reference v) \
375 for( size_type i = 0; i < n; ++i ) \
379 void name::insert(iterator it, const_iterator first, const_iterator last) \
381 size_t nInsert = last - first, nIndex = it - begin(); \
386 memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \
387 (m_nCount - nIndex)*sizeof(T)); \
388 for (size_t i = 0; i < nInsert; ++i, ++it, ++first) \
390 m_nCount += nInsert; \
395 #define _WX_DEFINE_BASEARRAY(T, name) \
396 _WX_DEFINE_BASEARRAY_COMMON(T, name) \
397 _WX_DEFINE_BASEARRAY_NOCOMMON(T, name)
400 #pragma warning(push)
401 #pragma warning(disable: 1684)
402 #pragma warning(disable: 1572)
405 _WX_DEFINE_BASEARRAY(const void *, wxBaseArrayPtrVoid
)
406 _WX_DEFINE_BASEARRAY(short, wxBaseArrayShort
)
407 _WX_DEFINE_BASEARRAY(int, wxBaseArrayInt
)
408 _WX_DEFINE_BASEARRAY(long, wxBaseArrayLong
)
409 _WX_DEFINE_BASEARRAY(size_t, wxBaseArraySizeT
)
410 _WX_DEFINE_BASEARRAY(double, wxBaseArrayDouble
)
417 #include "wx/arrstr.h"
419 #include "wx/beforestd.h"
420 #include <functional>
421 #include "wx/afterstd.h"
423 _WX_DEFINE_BASEARRAY(wxString
, wxBaseArrayStringBase
)
425 // some compilers (Sun CC being the only known example) distinguish between
426 // extern "C" functions and the functions with C++ linkage and ptr_fun and
427 // wxStringCompareLess can't take wxStrcmp/wxStricmp directly as arguments in
428 // this case, we need the wrappers below to make this work
429 inline int wxStrcmpCppWrapper(const wxChar
*p
, const wxChar
*q
)
431 return wxStrcmp(p
, q
);
434 inline int wxStricmpCppWrapper(const wxChar
*p
, const wxChar
*q
)
436 return wxStricmp(p
, q
);
439 int wxArrayString::Index(const wxChar
* sz
, bool bCase
, bool WXUNUSED(bFromEnd
)) const
441 wxArrayString::const_iterator it
;
445 it
= std::find_if(begin(), end(),
448 std::ptr_fun(wxStrcmpCppWrapper
), sz
)));
452 it
= std::find_if(begin(), end(),
455 std::ptr_fun(wxStricmpCppWrapper
), sz
)));
458 return it
== end() ? wxNOT_FOUND
: it
- begin();
462 class wxStringCompareLess
465 wxStringCompareLess(F f
) : m_f(f
) { }
466 bool operator()(const wxChar
* s1
, const wxChar
* s2
)
467 { return m_f(s1
, s2
) < 0; }
468 bool operator()(const wxString
& s1
, const wxString
& s2
)
469 { return m_f(s1
, s2
) < 0; }
475 wxStringCompareLess
<F
> wxStringCompare(F f
)
477 return wxStringCompareLess
<F
>(f
);
480 void wxArrayString::Sort(CompareFunction function
)
482 std::sort(begin(), end(), wxStringCompare(function
));
485 void wxArrayString::Sort(bool reverseOrder
)
489 std::sort(begin(), end(), std::greater
<wxString
>());
493 std::sort(begin(), end());
497 int wxSortedArrayString::Index(const wxChar
* sz
, bool bCase
, bool WXUNUSED(bFromEnd
)) const
499 wxSortedArrayString::const_iterator it
;
503 it
= std::lower_bound(begin(), end(), s
,
504 wxStringCompare(wxStrcmpCppWrapper
));
506 it
= std::lower_bound(begin(), end(), s
,
507 wxStringCompare(wxStricmpCppWrapper
));
514 if (wxStrcmp(it
->c_str(), sz
) != 0)
519 if (wxStricmp(it
->c_str(), sz
) != 0)