]> 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
(blindly) fixed header case confusion (replacement for patch 763760)
[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 #ifdef __GNUG__
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(long) <= 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 void name::Add(T lItem, CMPFUNC fnCompare) \
82 { \
83 Insert(lItem, IndexForInsert(lItem, fnCompare)); \
84 } \
85 \
86
87 #if wxUSE_STL
88
89 #define _WX_DEFINE_BASEARRAY_NOCOMMON(T, name) \
90 size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \
91 { \
92 Predicate p(fnCompare); \
93 const_iterator it = std::lower_bound(begin(), end(), lItem, p); \
94 return it - begin(); \
95 } \
96 \
97 int name::Index(T lItem, CMPFUNC fnCompare) const \
98 { \
99 size_t n = IndexForInsert(lItem, fnCompare); \
100 \
101 return (n >= size() || \
102 (*fnCompare)(&lItem, &(*this)[n])) ? wxNOT_FOUND : (int)n; \
103 } \
104 \
105 void name::Shrink() \
106 { \
107 name tmp(*this); \
108 swap(tmp); \
109 }
110
111 #else // if !wxUSE_STL
112
113 #define _WX_DEFINE_BASEARRAY_NOCOMMON(T, name) \
114 /* ctor */ \
115 name::name() \
116 { \
117 m_nSize = \
118 m_nCount = 0; \
119 m_pItems = (T *)NULL; \
120 } \
121 \
122 /* copy ctor */ \
123 name::name(const name& src) \
124 { \
125 m_nSize = /* not src.m_nSize to save memory */ \
126 m_nCount = src.m_nCount; \
127 \
128 if ( m_nSize != 0 ) { \
129 m_pItems = new T[m_nSize]; \
130 /* only copy if allocation succeeded */ \
131 if ( m_pItems ) { \
132 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \
133 } \
134 else { \
135 m_nSize = 0; \
136 } \
137 } \
138 else \
139 m_pItems = (T *) NULL; \
140 } \
141 \
142 /* assignment operator */ \
143 name& name::operator=(const name& src) \
144 { \
145 wxDELETEA(m_pItems); \
146 \
147 m_nSize = /* not src.m_nSize to save memory */ \
148 m_nCount = src.m_nCount; \
149 \
150 if ( m_nSize != 0 ){ \
151 m_pItems = new T[m_nSize]; \
152 /* only copy if allocation succeeded */ \
153 if ( m_pItems ) { \
154 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \
155 } \
156 else { \
157 m_nSize = 0; \
158 } \
159 } \
160 else \
161 m_pItems = (T *) NULL; \
162 \
163 return *this; \
164 } \
165 \
166 /* allocate new buffer of the given size and move our data to it */ \
167 bool name::Realloc(size_t nSize) \
168 { \
169 T *pNew = new T[nSize]; \
170 /* only grow if allocation succeeded */ \
171 if ( !pNew ) \
172 return false; \
173 \
174 m_nSize = nSize; \
175 /* copy data to new location */ \
176 memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \
177 delete [] m_pItems; \
178 m_pItems = pNew; \
179 \
180 return true; \
181 } \
182 \
183 /* grow the array */ \
184 void name::Grow(size_t nIncrement) \
185 { \
186 /* only do it if no more place */ \
187 if( (m_nCount == m_nSize) || ((m_nSize - m_nCount) < nIncrement) ) { \
188 if( m_nSize == 0 ) { \
189 /* was empty, determine initial size */ \
190 size_t size = WX_ARRAY_DEFAULT_INITIAL_SIZE; \
191 if (size < nIncrement) size = nIncrement; \
192 /* allocate some memory */ \
193 m_pItems = new T[size]; \
194 /* only grow if allocation succeeded */ \
195 if ( m_pItems ) { \
196 m_nSize = size; \
197 } \
198 } \
199 else \
200 { \
201 /* add at least 50% but not too much */ \
202 size_t ndefIncrement = m_nSize < WX_ARRAY_DEFAULT_INITIAL_SIZE \
203 ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1; \
204 if ( ndefIncrement > ARRAY_MAXSIZE_INCREMENT ) \
205 ndefIncrement = ARRAY_MAXSIZE_INCREMENT; \
206 if ( nIncrement < ndefIncrement ) \
207 nIncrement = ndefIncrement; \
208 Realloc(m_nSize + nIncrement); \
209 } \
210 } \
211 } \
212 \
213 /* make sure that the array has at least count elements */ \
214 void name::SetCount(size_t count, T defval) \
215 { \
216 if ( m_nSize < count ) \
217 { \
218 /* need to realloc memory: don't overallocate it here as if */ \
219 /* SetCount() is called, it probably means that the caller */ \
220 /* knows in advance how many elements there will be in the */ \
221 /* array and so it won't be necessary to realloc it later */ \
222 if ( !Realloc(count) ) \
223 { \
224 /* out of memory -- what can we do? */ \
225 return; \
226 } \
227 } \
228 \
229 /* add new elements if we extend the array */ \
230 while ( m_nCount < count ) \
231 { \
232 m_pItems[m_nCount++] = defval; \
233 } \
234 } \
235 \
236 /* dtor */ \
237 name::~name() \
238 { \
239 wxDELETEA(m_pItems); \
240 } \
241 \
242 /* clears the list */ \
243 void name::Clear() \
244 { \
245 m_nSize = \
246 m_nCount = 0; \
247 \
248 wxDELETEA(m_pItems); \
249 } \
250 \
251 /* pre-allocates memory (frees the previous data!) */ \
252 void name::Alloc(size_t nSize) \
253 { \
254 /* only if old buffer was not big enough */ \
255 if ( nSize > m_nSize ) { \
256 wxDELETEA(m_pItems); \
257 m_nSize = 0; \
258 m_pItems = new T[nSize]; \
259 /* only alloc if allocation succeeded */ \
260 if ( m_pItems ) { \
261 m_nSize = nSize; \
262 } \
263 } \
264 \
265 m_nCount = 0; \
266 } \
267 \
268 /* minimizes the memory usage by freeing unused memory */ \
269 void name::Shrink() \
270 { \
271 /* only do it if we have some memory to free */ \
272 if( m_nCount < m_nSize ) { \
273 /* allocates exactly as much memory as we need */ \
274 T *pNew = new T[m_nCount]; \
275 /* only shrink if allocation succeeded */ \
276 if ( pNew ) { \
277 /* copy data to new location */ \
278 memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \
279 delete [] m_pItems; \
280 m_pItems = pNew; \
281 \
282 /* update the size of the new block */ \
283 m_nSize = m_nCount; \
284 } \
285 /* else: don't do anything, better keep old memory block! */ \
286 } \
287 } \
288 \
289 /* add item at the end */ \
290 void name::Add(T lItem, size_t nInsert) \
291 { \
292 if (nInsert == 0) \
293 return; \
294 Grow(nInsert); \
295 for (size_t i = 0; i < nInsert; i++) \
296 m_pItems[m_nCount++] = lItem; \
297 } \
298 \
299 /* add item at the given position */ \
300 void name::Insert(T lItem, size_t nIndex, size_t nInsert) \
301 { \
302 wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") ); \
303 wxCHECK_RET( m_nCount <= m_nCount + nInsert, \
304 wxT("array size overflow in wxArray::Insert") ); \
305 \
306 if (nInsert == 0) \
307 return; \
308 Grow(nInsert); \
309 \
310 memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \
311 (m_nCount - nIndex)*sizeof(T)); \
312 for (size_t i = 0; i < nInsert; i++) \
313 m_pItems[nIndex + i] = lItem; \
314 m_nCount += nInsert; \
315 } \
316 \
317 /* search for a place to insert item into sorted array (binary search) */ \
318 size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \
319 { \
320 size_t i, \
321 lo = 0, \
322 hi = m_nCount; \
323 int res; \
324 \
325 while ( lo < hi ) { \
326 i = (lo + hi)/2; \
327 \
328 res = (*fnCompare)((const void *)(long)lItem, \
329 (const void *)(long)(m_pItems[i])); \
330 if ( res < 0 ) \
331 hi = i; \
332 else if ( res > 0 ) \
333 lo = i + 1; \
334 else { \
335 lo = i; \
336 break; \
337 } \
338 } \
339 \
340 return lo; \
341 } \
342 \
343 /* search for an item in a sorted array (binary search) */ \
344 int name::Index(T lItem, CMPFUNC fnCompare) const \
345 { \
346 size_t n = IndexForInsert(lItem, fnCompare); \
347 \
348 return (n >= m_nCount || \
349 (*fnCompare)((const void *)(long)lItem, \
350 ((const void *)(long)m_pItems[n]))) ? wxNOT_FOUND \
351 : (int)n; \
352 } \
353 \
354 /* removes item from array (by index) */ \
355 void name::RemoveAt(size_t nIndex, size_t nRemove) \
356 { \
357 wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArray::RemoveAt") ); \
358 wxCHECK_RET( nIndex + nRemove <= m_nCount, \
359 wxT("removing too many elements in wxArray::RemoveAt") ); \
360 \
361 memmove(&m_pItems[nIndex], &m_pItems[nIndex + nRemove], \
362 (m_nCount - nIndex - nRemove)*sizeof(T)); \
363 m_nCount -= nRemove; \
364 } \
365 \
366 /* removes item from array (by value) */ \
367 void name::Remove(T lItem) \
368 { \
369 int iIndex = Index(lItem); \
370 \
371 wxCHECK_RET( iIndex != wxNOT_FOUND, \
372 wxT("removing inexistent item in wxArray::Remove") ); \
373 \
374 RemoveAt((size_t)iIndex); \
375 } \
376 \
377 /* sort array elements using passed comparaison function */ \
378 void name::Sort(CMPFUNC fCmp) \
379 { \
380 qsort(m_pItems, m_nCount, sizeof(T), fCmp); \
381 } \
382 \
383 void name::assign(const_iterator first, const_iterator last) \
384 { \
385 clear(); \
386 reserve(last - first); \
387 for(; first != last; ++first) \
388 push_back(*first); \
389 } \
390 \
391 void name::assign(size_type n, const_reference v) \
392 { \
393 clear(); \
394 reserve(n); \
395 for( size_type i = 0; i < n; ++i ) \
396 push_back(v); \
397 } \
398 \
399 void name::insert(iterator it, const_iterator first, const_iterator last) \
400 { \
401 size_t nInsert = last - first, nIndex = it - begin(); \
402 if (nInsert == 0) \
403 return; \
404 Grow(nInsert); \
405 \
406 memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \
407 (m_nCount - nIndex)*sizeof(T)); \
408 for (size_t i = 0; i < nInsert; ++i, ++it, ++first) \
409 *it = *first; \
410 m_nCount += nInsert; \
411 }
412
413 #endif
414
415 #define _WX_DEFINE_BASEARRAY(T, name) \
416 _WX_DEFINE_BASEARRAY_COMMON(T, name) \
417 _WX_DEFINE_BASEARRAY_NOCOMMON(T, name)
418
419 _WX_DEFINE_BASEARRAY(const void *, wxBaseArrayPtrVoid)
420 _WX_DEFINE_BASEARRAY(short, wxBaseArrayShort)
421 _WX_DEFINE_BASEARRAY(int, wxBaseArrayInt)
422 _WX_DEFINE_BASEARRAY(long, wxBaseArrayLong)
423 _WX_DEFINE_BASEARRAY(double, wxBaseArrayDouble)
424
425 #if wxUSE_STL
426 #include "wx/arrstr.h"
427
428 _WX_DEFINE_BASEARRAY(wxString, wxBaseArrayStringBase)
429
430 #endif
wxWidgets (Impactor)