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