]> git.saurik.com Git - wxWidgets.git/blob - src/common/dynarray.cpp
projects / wxWidgets.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
optimize FindItem(data) performance (closes #9870)
[wxWidgets.git] / src / common / dynarray.cpp
1 ///////////////////////////////////////////////////////////////////////////////
2 // Name: src/common/dynarray.cpp
3 // Purpose: implementation of wxBaseArray class
4 // Author: Vadim Zeitlin
5 // Modified by:
6 // Created: 12.09.97
7 // RCS-ID: $Id$
8 // Copyright: (c) 1998 Vadim Zeitlin <zeitlin@dptmaths.ens-cachan.fr>
9 // Licence: wxWindows licence
10 ///////////////////////////////////////////////////////////////////////////////
11
12 // ============================================================================
13 // headers
14 // ============================================================================
15
16 // For compilers that support precompilation, includes "wx.h".
17 #include "wx/wxprec.h"
18
19 #ifdef __BORLANDC__
20 #pragma hdrstop
21 #endif
22
23 #ifndef WX_PRECOMP
24 #include "wx/dynarray.h"
25 #include "wx/intl.h"
26 #endif //WX_PRECOMP
27
28 #include <stdlib.h>
29 #include <string.h> // for memmove
30
31 #if !wxUSE_STL
32
33 // we cast the value to long from which we cast it to void * in IndexForInsert:
34 // this can't work if the pointers are not big enough
35 wxCOMPILE_TIME_ASSERT( sizeof(wxUIntPtr) <= sizeof(void *),
36 wxArraySizeOfPtrLessSizeOfLong ); // < 32 symbols
37
38 // ============================================================================
39 // constants
40 // ============================================================================
41
42 // size increment = max(50% of current size, ARRAY_MAXSIZE_INCREMENT)
43 #define ARRAY_MAXSIZE_INCREMENT 4096
44
45 // ============================================================================
46 // implementation
47 // ============================================================================
48
49 // ----------------------------------------------------------------------------
50 // wxBaseArray - dynamic array of 'T's
51 // ----------------------------------------------------------------------------
52
53 #define _WX_DEFINE_BASEARRAY(T, name) \
54 /* searches the array for an item (forward or backwards) */ \
55 int name::Index(T lItem, bool bFromEnd) const \
56 { \
57 if ( bFromEnd ) { \
58 if ( size() > 0 ) { \
59 size_t n = size(); \
60 do { \
61 if ( (*this)[--n] == lItem ) \
62 return n; \
63 } \
64 while ( n != 0 ); \
65 } \
66 } \
67 else { \
68 for( size_t n = 0; n < size(); n++ ) { \
69 if( (*this)[n] == lItem ) \
70 return n; \
71 } \
72 } \
73 \
74 return wxNOT_FOUND; \
75 } \
76 \
77 /* add item assuming the array is sorted with fnCompare function */ \
78 size_t name::Add(T lItem, CMPFUNC fnCompare) \
79 { \
80 size_t idx = IndexForInsert(lItem, fnCompare); \
81 Insert(lItem, idx); \
82 return idx; \
83 } \
84 \
85 /* ctor */ \
86 name::name() \
87 { \
88 m_nSize = \
89 m_nCount = 0; \
90 m_pItems = NULL; \
91 } \
92 \
93 /* copy ctor */ \
94 name::name(const name& src) \
95 { \
96 m_nSize = /* not src.m_nSize to save memory */ \
97 m_nCount = src.m_nCount; \
98 \
99 if ( m_nSize != 0 ) { \
100 m_pItems = new T[m_nSize]; \
101 /* only copy if allocation succeeded */ \
102 if ( m_pItems ) { \
103 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \
104 } \
105 else { \
106 m_nSize = 0; \
107 } \
108 } \
109 else \
110 m_pItems = NULL; \
111 } \
112 \
113 /* assignment operator */ \
114 name& name::operator=(const name& src) \
115 { \
116 wxDELETEA(m_pItems); \
117 \
118 m_nSize = /* not src.m_nSize to save memory */ \
119 m_nCount = src.m_nCount; \
120 \
121 if ( m_nSize != 0 ){ \
122 m_pItems = new T[m_nSize]; \
123 /* only copy if allocation succeeded */ \
124 if ( m_pItems ) { \
125 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \
126 } \
127 else { \
128 m_nSize = 0; \
129 } \
130 } \
131 else \
132 m_pItems = NULL; \
133 \
134 return *this; \
135 } \
136 \
137 /* allocate new buffer of the given size and move our data to it */ \
138 bool name::Realloc(size_t nSize) \
139 { \
140 T *pNew = new T[nSize]; \
141 /* only grow if allocation succeeded */ \
142 if ( !pNew ) \
143 return false; \
144 \
145 m_nSize = nSize; \
146 /* copy data to new location */ \
147 memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \
148 delete [] m_pItems; \
149 m_pItems = pNew; \
150 \
151 return true; \
152 } \
153 \
154 /* grow the array */ \
155 void name::Grow(size_t nIncrement) \
156 { \
157 /* only do it if no more place */ \
158 if( (m_nCount == m_nSize) || ((m_nSize - m_nCount) < nIncrement) ) { \
159 if( m_nSize == 0 ) { \
160 /* was empty, determine initial size */ \
161 size_t size = WX_ARRAY_DEFAULT_INITIAL_SIZE; \
162 if (size < nIncrement) size = nIncrement; \
163 /* allocate some memory */ \
164 m_pItems = new T[size]; \
165 /* only grow if allocation succeeded */ \
166 if ( m_pItems ) { \
167 m_nSize = size; \
168 } \
169 } \
170 else \
171 { \
172 /* add at least 50% but not too much */ \
173 size_t ndefIncrement = m_nSize < WX_ARRAY_DEFAULT_INITIAL_SIZE \
174 ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1; \
175 if ( ndefIncrement > ARRAY_MAXSIZE_INCREMENT ) \
176 ndefIncrement = ARRAY_MAXSIZE_INCREMENT; \
177 if ( nIncrement < ndefIncrement ) \
178 nIncrement = ndefIncrement; \
179 Realloc(m_nSize + nIncrement); \
180 } \
181 } \
182 } \
183 \
184 /* make sure that the array has at least count elements */ \
185 void name::SetCount(size_t count, T defval) \
186 { \
187 if ( m_nSize < count ) \
188 { \
189 /* need to realloc memory: don't overallocate it here as if */ \
190 /* SetCount() is called, it probably means that the caller */ \
191 /* knows in advance how many elements there will be in the */ \
192 /* array and so it won't be necessary to realloc it later */ \
193 if ( !Realloc(count) ) \
194 { \
195 /* out of memory -- what can we do? */ \
196 return; \
197 } \
198 } \
199 \
200 /* add new elements if we extend the array */ \
201 while ( m_nCount < count ) \
202 { \
203 m_pItems[m_nCount++] = defval; \
204 } \
205 } \
206 \
207 /* dtor */ \
208 name::~name() \
209 { \
210 wxDELETEA(m_pItems); \
211 } \
212 \
213 /* clears the list */ \
214 void name::Clear() \
215 { \
216 m_nSize = \
217 m_nCount = 0; \
218 \
219 wxDELETEA(m_pItems); \
220 } \
221 \
222 /* minimizes the memory usage by freeing unused memory */ \
223 void name::Shrink() \
224 { \
225 /* only do it if we have some memory to free */ \
226 if( m_nCount < m_nSize ) { \
227 /* allocates exactly as much memory as we need */ \
228 T *pNew = new T[m_nCount]; \
229 /* only shrink if allocation succeeded */ \
230 if ( pNew ) { \
231 /* copy data to new location */ \
232 memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \
233 delete [] m_pItems; \
234 m_pItems = pNew; \
235 \
236 /* update the size of the new block */ \
237 m_nSize = m_nCount; \
238 } \
239 /* else: don't do anything, better keep old memory block! */ \
240 } \
241 } \
242 \
243 /* add item at the end */ \
244 void name::Add(T lItem, size_t nInsert) \
245 { \
246 if (nInsert == 0) \
247 return; \
248 Grow(nInsert); \
249 for (size_t i = 0; i < nInsert; i++) \
250 m_pItems[m_nCount++] = lItem; \
251 } \
252 \
253 /* add item at the given position */ \
254 void name::Insert(T lItem, size_t nIndex, size_t nInsert) \
255 { \
256 wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") ); \
257 wxCHECK_RET( m_nCount <= m_nCount + nInsert, \
258 wxT("array size overflow in wxArray::Insert") ); \
259 \
260 if (nInsert == 0) \
261 return; \
262 Grow(nInsert); \
263 \
264 memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \
265 (m_nCount - nIndex)*sizeof(T)); \
266 for (size_t i = 0; i < nInsert; i++) \
267 m_pItems[nIndex + i] = lItem; \
268 m_nCount += nInsert; \
269 } \
270 \
271 /* search for a place to insert item into sorted array (binary search) */ \
272 size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \
273 { \
274 size_t i, \
275 lo = 0, \
276 hi = m_nCount; \
277 int res; \
278 \
279 while ( lo < hi ) { \
280 i = (lo + hi)/2; \
281 \
282 res = (*fnCompare)((const void *)(wxUIntPtr)lItem, \
283 (const void *)(wxUIntPtr)(m_pItems[i])); \
284 if ( res < 0 ) \
285 hi = i; \
286 else if ( res > 0 ) \
287 lo = i + 1; \
288 else { \
289 lo = i; \
290 break; \
291 } \
292 } \
293 \
294 return lo; \
295 } \
296 \
297 /* search for an item in a sorted array (binary search) */ \
298 int name::Index(T lItem, CMPFUNC fnCompare) const \
299 { \
300 size_t n = IndexForInsert(lItem, fnCompare); \
301 \
302 return (n >= m_nCount || \
303 (*fnCompare)((const void *)(wxUIntPtr)lItem, \
304 ((const void *)(wxUIntPtr)m_pItems[n]))) \
305 ? wxNOT_FOUND \
306 : (int)n; \
307 } \
308 \
309 /* removes item from array (by index) */ \
310 void name::RemoveAt(size_t nIndex, size_t nRemove) \
311 { \
312 wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArray::RemoveAt") ); \
313 wxCHECK_RET( nIndex + nRemove <= m_nCount, \
314 wxT("removing too many elements in wxArray::RemoveAt") ); \
315 \
316 memmove(&m_pItems[nIndex], &m_pItems[nIndex + nRemove], \
317 (m_nCount - nIndex - nRemove)*sizeof(T)); \
318 m_nCount -= nRemove; \
319 } \
320 \
321 /* removes item from array (by value) */ \
322 void name::Remove(T lItem) \
323 { \
324 int iIndex = Index(lItem); \
325 \
326 wxCHECK_RET( iIndex != wxNOT_FOUND, \
327 wxT("removing inexistent item in wxArray::Remove") ); \
328 \
329 RemoveAt((size_t)iIndex); \
330 } \
331 \
332 /* sort array elements using passed comparaison function */ \
333 void name::Sort(CMPFUNC fCmp) \
334 { \
335 qsort(m_pItems, m_nCount, sizeof(T), fCmp); \
336 } \
337 \
338 void name::assign(const_iterator first, const_iterator last) \
339 { \
340 clear(); \
341 reserve(last - first); \
342 for(; first != last; ++first) \
343 push_back(*first); \
344 } \
345 \
346 void name::assign(size_type n, const_reference v) \
347 { \
348 clear(); \
349 reserve(n); \
350 for( size_type i = 0; i < n; ++i ) \
351 push_back(v); \
352 } \
353 \
354 void name::insert(iterator it, const_iterator first, const_iterator last) \
355 { \
356 size_t nInsert = last - first, nIndex = it - begin(); \
357 if (nInsert == 0) \
358 return; \
359 Grow(nInsert); \
360 \
361 memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \
362 (m_nCount - nIndex)*sizeof(T)); \
363 for (size_t i = 0; i < nInsert; ++i, ++it, ++first) \
364 *it = *first; \
365 m_nCount += nInsert; \
366 }
367
368 #ifdef __INTELC__
369 #pragma warning(push)
370 #pragma warning(disable: 1684)
371 #pragma warning(disable: 1572)
372 #endif
373
374 _WX_DEFINE_BASEARRAY(const void *, wxBaseArrayPtrVoid)
375 _WX_DEFINE_BASEARRAY(char, wxBaseArrayChar)
376 _WX_DEFINE_BASEARRAY(short, wxBaseArrayShort)
377 _WX_DEFINE_BASEARRAY(int, wxBaseArrayInt)
378 _WX_DEFINE_BASEARRAY(long, wxBaseArrayLong)
379 _WX_DEFINE_BASEARRAY(size_t, wxBaseArraySizeT)
380 _WX_DEFINE_BASEARRAY(double, wxBaseArrayDouble)
381
382 #ifdef __INTELC__
383 #pragma warning(pop)
384 #endif
385
386 #else // wxUSE_STL
387
388 #include "wx/arrstr.h"
389
390 #include "wx/beforestd.h"
391 #include <functional>
392 #include "wx/afterstd.h"
393
394 // some compilers (Sun CC being the only known example) distinguish between
395 // extern "C" functions and the functions with C++ linkage and ptr_fun and
396 // wxStringCompareLess can't take wxStrcmp/wxStricmp directly as arguments in
397 // this case, we need the wrappers below to make this work
398 struct wxStringCmp
399 {
400 typedef wxString first_argument_type;
401 typedef wxString second_argument_type;
402 typedef int result_type;
403
404 int operator()(const wxString& s1, const wxString& s2) const
405 {
406 return s1.compare(s2);
407 }
408 };
409
410 struct wxStringCmpNoCase
411 {
412 typedef wxString first_argument_type;
413 typedef wxString second_argument_type;
414 typedef int result_type;
415
416 int operator()(const wxString& s1, const wxString& s2) const
417 {
418 return s1.CmpNoCase(s2);
419 }
420 };
421
422 int wxArrayString::Index(const wxString& str, bool bCase, bool WXUNUSED(bFromEnd)) const
423 {
424 wxArrayString::const_iterator it;
425
426 if (bCase)
427 {
428 it = std::find_if(begin(), end(),
429 std::not1(
430 std::bind2nd(
431 wxStringCmp(), str)));
432 }
433 else // !bCase
434 {
435 it = std::find_if(begin(), end(),
436 std::not1(
437 std::bind2nd(
438 wxStringCmpNoCase(), str)));
439 }
440
441 return it == end() ? wxNOT_FOUND : it - begin();
442 }
443
444 template<class F>
445 class wxStringCompareLess
446 {
447 public:
448 wxStringCompareLess(F f) : m_f(f) { }
449 bool operator()(const wxString& s1, const wxString& s2)
450 { return m_f(s1, s2) < 0; }
451 private:
452 F m_f;
453 };
454
455 template<class F>
456 wxStringCompareLess<F> wxStringCompare(F f)
457 {
458 return wxStringCompareLess<F>(f);
459 }
460
461 void wxArrayString::Sort(CompareFunction function)
462 {
463 std::sort(begin(), end(), wxStringCompare(function));
464 }
465
466 void wxArrayString::Sort(bool reverseOrder)
467 {
468 if (reverseOrder)
469 {
470 std::sort(begin(), end(), std::greater<wxString>());
471 }
472 else
473 {
474 std::sort(begin(), end());
475 }
476 }
477
478 int wxSortedArrayString::Index(const wxString& str, bool bCase, bool WXUNUSED(bFromEnd)) const
479 {
480 wxSortedArrayString::const_iterator it;
481
482 if (bCase)
483 it = std::lower_bound(begin(), end(), str,
484 wxStringCompare(wxStringCmp()));
485 else
486 it = std::lower_bound(begin(), end(), str,
487 wxStringCompare(wxStringCmpNoCase()));
488
489 if (it == end())
490 return wxNOT_FOUND;
491
492 if (bCase)
493 {
494 if (str.Cmp(*it) != 0)
495 return wxNOT_FOUND;
496 }
497 else
498 {
499 if (str.CmpNoCase(*it) != 0)
500 return wxNOT_FOUND;
501 }
502
503 return it - begin();
504 }
505
506 #endif // !wxUSE_STL/wxUSE_STL
wxWidgets (Impactor)