]> 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
avoid undefined behavior from token paste resulting in more than one token
[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 // 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
35
36 // ============================================================================
37 // constants
38 // ============================================================================
39
40 // size increment = max(50% of current size, ARRAY_MAXSIZE_INCREMENT)
41 #define ARRAY_MAXSIZE_INCREMENT 4096
42
43 // ============================================================================
44 // implementation
45 // ============================================================================
46
47 // ----------------------------------------------------------------------------
48 // wxBaseArray - dynamic array of 'T's
49 // ----------------------------------------------------------------------------
50
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 \
54 { \
55 if ( bFromEnd ) { \
56 if ( size() > 0 ) { \
57 size_t n = size(); \
58 do { \
59 if ( (*this)[--n] == lItem ) \
60 return n; \
61 } \
62 while ( n != 0 ); \
63 } \
64 } \
65 else { \
66 for( size_t n = 0; n < size(); n++ ) { \
67 if( (*this)[n] == lItem ) \
68 return n; \
69 } \
70 } \
71 \
72 return wxNOT_FOUND; \
73 } \
74 \
75 /* add item assuming the array is sorted with fnCompare function */ \
76 size_t name::Add(T lItem, CMPFUNC fnCompare) \
77 { \
78 size_t idx = IndexForInsert(lItem, fnCompare); \
79 Insert(lItem, idx); \
80 return idx; \
81 }
82
83 #if wxUSE_STL
84
85 #define _WX_DEFINE_BASEARRAY_NOCOMMON(T, name) \
86 size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \
87 { \
88 Predicate p((SCMPFUNC)fnCompare); \
89 const_iterator it = std::lower_bound(begin(), end(), lItem, p); \
90 return it - begin(); \
91 } \
92 \
93 int name::Index(T lItem, CMPFUNC fnCompare) const \
94 { \
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; \
99 } \
100 \
101 void name::Shrink() \
102 { \
103 name tmp(*this); \
104 swap(tmp); \
105 }
106
107 #else // if !wxUSE_STL
108
109 #define _WX_DEFINE_BASEARRAY_NOCOMMON(T, name) \
110 /* ctor */ \
111 name::name() \
112 { \
113 m_nSize = \
114 m_nCount = 0; \
115 m_pItems = (T *)NULL; \
116 } \
117 \
118 /* copy ctor */ \
119 name::name(const name& src) \
120 { \
121 m_nSize = /* not src.m_nSize to save memory */ \
122 m_nCount = src.m_nCount; \
123 \
124 if ( m_nSize != 0 ) { \
125 m_pItems = new T[m_nSize]; \
126 /* only copy if allocation succeeded */ \
127 if ( m_pItems ) { \
128 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \
129 } \
130 else { \
131 m_nSize = 0; \
132 } \
133 } \
134 else \
135 m_pItems = (T *) NULL; \
136 } \
137 \
138 /* assignment operator */ \
139 name& name::operator=(const name& src) \
140 { \
141 wxDELETEA(m_pItems); \
142 \
143 m_nSize = /* not src.m_nSize to save memory */ \
144 m_nCount = src.m_nCount; \
145 \
146 if ( m_nSize != 0 ){ \
147 m_pItems = new T[m_nSize]; \
148 /* only copy if allocation succeeded */ \
149 if ( m_pItems ) { \
150 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \
151 } \
152 else { \
153 m_nSize = 0; \
154 } \
155 } \
156 else \
157 m_pItems = (T *) NULL; \
158 \
159 return *this; \
160 } \
161 \
162 /* allocate new buffer of the given size and move our data to it */ \
163 bool name::Realloc(size_t nSize) \
164 { \
165 T *pNew = new T[nSize]; \
166 /* only grow if allocation succeeded */ \
167 if ( !pNew ) \
168 return false; \
169 \
170 m_nSize = nSize; \
171 /* copy data to new location */ \
172 memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \
173 delete [] m_pItems; \
174 m_pItems = pNew; \
175 \
176 return true; \
177 } \
178 \
179 /* grow the array */ \
180 void name::Grow(size_t nIncrement) \
181 { \
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 */ \
191 if ( m_pItems ) { \
192 m_nSize = size; \
193 } \
194 } \
195 else \
196 { \
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); \
205 } \
206 } \
207 } \
208 \
209 /* make sure that the array has at least count elements */ \
210 void name::SetCount(size_t count, T defval) \
211 { \
212 if ( m_nSize < count ) \
213 { \
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) ) \
219 { \
220 /* out of memory -- what can we do? */ \
221 return; \
222 } \
223 } \
224 \
225 /* add new elements if we extend the array */ \
226 while ( m_nCount < count ) \
227 { \
228 m_pItems[m_nCount++] = defval; \
229 } \
230 } \
231 \
232 /* dtor */ \
233 name::~name() \
234 { \
235 wxDELETEA(m_pItems); \
236 } \
237 \
238 /* clears the list */ \
239 void name::Clear() \
240 { \
241 m_nSize = \
242 m_nCount = 0; \
243 \
244 wxDELETEA(m_pItems); \
245 } \
246 \
247 /* minimizes the memory usage by freeing unused memory */ \
248 void name::Shrink() \
249 { \
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 */ \
255 if ( pNew ) { \
256 /* copy data to new location */ \
257 memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \
258 delete [] m_pItems; \
259 m_pItems = pNew; \
260 \
261 /* update the size of the new block */ \
262 m_nSize = m_nCount; \
263 } \
264 /* else: don't do anything, better keep old memory block! */ \
265 } \
266 } \
267 \
268 /* add item at the end */ \
269 void name::Add(T lItem, size_t nInsert) \
270 { \
271 if (nInsert == 0) \
272 return; \
273 Grow(nInsert); \
274 for (size_t i = 0; i < nInsert; i++) \
275 m_pItems[m_nCount++] = lItem; \
276 } \
277 \
278 /* add item at the given position */ \
279 void name::Insert(T lItem, size_t nIndex, size_t nInsert) \
280 { \
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") ); \
284 \
285 if (nInsert == 0) \
286 return; \
287 Grow(nInsert); \
288 \
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; \
294 } \
295 \
296 /* search for a place to insert item into sorted array (binary search) */ \
297 size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \
298 { \
299 size_t i, \
300 lo = 0, \
301 hi = m_nCount; \
302 int res; \
303 \
304 while ( lo < hi ) { \
305 i = (lo + hi)/2; \
306 \
307 res = (*fnCompare)((const void *)(wxUIntPtr)lItem, \
308 (const void *)(wxUIntPtr)(m_pItems[i])); \
309 if ( res < 0 ) \
310 hi = i; \
311 else if ( res > 0 ) \
312 lo = i + 1; \
313 else { \
314 lo = i; \
315 break; \
316 } \
317 } \
318 \
319 return lo; \
320 } \
321 \
322 /* search for an item in a sorted array (binary search) */ \
323 int name::Index(T lItem, CMPFUNC fnCompare) const \
324 { \
325 size_t n = IndexForInsert(lItem, fnCompare); \
326 \
327 return (n >= m_nCount || \
328 (*fnCompare)((const void *)(wxUIntPtr)lItem, \
329 ((const void *)(wxUIntPtr)m_pItems[n]))) \
330 ? wxNOT_FOUND \
331 : (int)n; \
332 } \
333 \
334 /* removes item from array (by index) */ \
335 void name::RemoveAt(size_t nIndex, size_t nRemove) \
336 { \
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") ); \
340 \
341 memmove(&m_pItems[nIndex], &m_pItems[nIndex + nRemove], \
342 (m_nCount - nIndex - nRemove)*sizeof(T)); \
343 m_nCount -= nRemove; \
344 } \
345 \
346 /* removes item from array (by value) */ \
347 void name::Remove(T lItem) \
348 { \
349 int iIndex = Index(lItem); \
350 \
351 wxCHECK_RET( iIndex != wxNOT_FOUND, \
352 wxT("removing inexistent item in wxArray::Remove") ); \
353 \
354 RemoveAt((size_t)iIndex); \
355 } \
356 \
357 /* sort array elements using passed comparaison function */ \
358 void name::Sort(CMPFUNC fCmp) \
359 { \
360 qsort(m_pItems, m_nCount, sizeof(T), fCmp); \
361 } \
362 \
363 void name::assign(const_iterator first, const_iterator last) \
364 { \
365 clear(); \
366 reserve(last - first); \
367 for(; first != last; ++first) \
368 push_back(*first); \
369 } \
370 \
371 void name::assign(size_type n, const_reference v) \
372 { \
373 clear(); \
374 reserve(n); \
375 for( size_type i = 0; i < n; ++i ) \
376 push_back(v); \
377 } \
378 \
379 void name::insert(iterator it, const_iterator first, const_iterator last) \
380 { \
381 size_t nInsert = last - first, nIndex = it - begin(); \
382 if (nInsert == 0) \
383 return; \
384 Grow(nInsert); \
385 \
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) \
389 *it = *first; \
390 m_nCount += nInsert; \
391 }
392
393 #endif
394
395 #define _WX_DEFINE_BASEARRAY(T, name) \
396 _WX_DEFINE_BASEARRAY_COMMON(T, name) \
397 _WX_DEFINE_BASEARRAY_NOCOMMON(T, name)
398
399 #ifdef __INTELC__
400 #pragma warning(push)
401 #pragma warning(disable: 1684)
402 #pragma warning(disable: 1572)
403 #endif
404
405 _WX_DEFINE_BASEARRAY(const void *, wxBaseArrayPtrVoid)
406 _WX_DEFINE_BASEARRAY(char, wxBaseArrayChar)
407 _WX_DEFINE_BASEARRAY(short, wxBaseArrayShort)
408 _WX_DEFINE_BASEARRAY(int, wxBaseArrayInt)
409 _WX_DEFINE_BASEARRAY(long, wxBaseArrayLong)
410 _WX_DEFINE_BASEARRAY(size_t, wxBaseArraySizeT)
411 _WX_DEFINE_BASEARRAY(double, wxBaseArrayDouble)
412
413 #ifdef __INTELC__
414 #pragma warning(pop)
415 #endif
416
417 #if wxUSE_STL
418 #include "wx/arrstr.h"
419
420 #include "wx/beforestd.h"
421 #include <functional>
422 #include "wx/afterstd.h"
423
424 _WX_DEFINE_BASEARRAY(wxString, wxBaseArrayStringBase)
425
426 // some compilers (Sun CC being the only known example) distinguish between
427 // extern "C" functions and the functions with C++ linkage and ptr_fun and
428 // wxStringCompareLess can't take wxStrcmp/wxStricmp directly as arguments in
429 // this case, we need the wrappers below to make this work
430 struct wxStringCmp
431 {
432 typedef wxString first_argument_type;
433 typedef wxString second_argument_type;
434 typedef int result_type;
435
436 int operator()(const wxString& s1, const wxString& s2) const
437 {
438 return s1.compare(s2);
439 }
440 };
441
442 struct wxStringCmpNoCase
443 {
444 typedef wxString first_argument_type;
445 typedef wxString second_argument_type;
446 typedef int result_type;
447
448 int operator()(const wxString& s1, const wxString& s2) const
449 {
450 return s1.CmpNoCase(s2);
451 }
452 };
453
454 int wxArrayString::Index(const wxString& str, bool bCase, bool WXUNUSED(bFromEnd)) const
455 {
456 wxArrayString::const_iterator it;
457
458 if (bCase)
459 {
460 it = std::find_if(begin(), end(),
461 std::not1(
462 std::bind2nd(
463 wxStringCmp(), str)));
464 }
465 else // !bCase
466 {
467 it = std::find_if(begin(), end(),
468 std::not1(
469 std::bind2nd(
470 wxStringCmpNoCase(), str)));
471 }
472
473 return it == end() ? wxNOT_FOUND : it - begin();
474 }
475
476 template<class F>
477 class wxStringCompareLess
478 {
479 public:
480 wxStringCompareLess(F f) : m_f(f) { }
481 bool operator()(const wxString& s1, const wxString& s2)
482 { return m_f(s1, s2) < 0; }
483 private:
484 F m_f;
485 };
486
487 template<class F>
488 wxStringCompareLess<F> wxStringCompare(F f)
489 {
490 return wxStringCompareLess<F>(f);
491 }
492
493 void wxArrayString::Sort(CompareFunction function)
494 {
495 std::sort(begin(), end(), wxStringCompare(function));
496 }
497
498 void wxArrayString::Sort(bool reverseOrder)
499 {
500 if (reverseOrder)
501 {
502 std::sort(begin(), end(), std::greater<wxString>());
503 }
504 else
505 {
506 std::sort(begin(), end());
507 }
508 }
509
510 int wxSortedArrayString::Index(const wxString& str, bool bCase, bool WXUNUSED(bFromEnd)) const
511 {
512 wxSortedArrayString::const_iterator it;
513
514 if (bCase)
515 it = std::lower_bound(begin(), end(), str,
516 wxStringCompare(wxStringCmp()));
517 else
518 it = std::lower_bound(begin(), end(), str,
519 wxStringCompare(wxStringCmpNoCase()));
520
521 if (it == end())
522 return wxNOT_FOUND;
523
524 if (bCase)
525 {
526 if (str.Cmp(*it) != 0)
527 return wxNOT_FOUND;
528 }
529 else
530 {
531 if (str.CmpNoCase(*it) != 0)
532 return wxNOT_FOUND;
533 }
534
535 return it - begin();
536 }
537
538 #endif // wxUSE_STL
wxWidgets (Impactor)