projects / wxWidgets.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
added wxArray::SetCount()
[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 license
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(T, name) \
57 /* ctor */ \
58 name::name() \
59 { \
60 m_nSize = \
61 m_nCount = 0; \
62 m_pItems = (T *)NULL; \
63 } \
64 \
65 /* copy ctor */ \
66 name::name(const name& src) \
67 { \
68 m_nSize = /* not src.m_nSize to save memory */ \
69 m_nCount = src.m_nCount; \
70 \
71 if ( m_nSize != 0 ) { \
72 m_pItems = new T[m_nSize]; \
73 /* only copy if allocation succeeded */ \
74 if ( m_pItems ) { \
75 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \
76 } \
77 else { \
78 m_nSize = 0; \
79 } \
80 } \
81 else \
82 m_pItems = (T *) NULL; \
83 } \
84 \
85 /* assignment operator */ \
86 name& name::operator=(const name& src) \
87 { \
88 wxDELETEA(m_pItems); \
89 \
90 m_nSize = /* not src.m_nSize to save memory */ \
91 m_nCount = src.m_nCount; \
92 \
93 if ( m_nSize != 0 ){ \
94 m_pItems = new T[m_nSize]; \
95 /* only copy if allocation succeeded */ \
96 if ( m_pItems ) { \
97 memcpy(m_pItems, src.m_pItems, m_nCount*sizeof(T)); \
98 } \
99 else { \
100 m_nSize = 0; \
101 } \
102 } \
103 else \
104 m_pItems = (T *) NULL; \
105 \
106 return *this; \
107 } \
108 \
109 /* allocate new buffer of the given size and move our data to it */ \
110 bool name::Realloc(size_t nSize) \
111 { \
112 T *pNew = new T[nSize]; \
113 /* only grow if allocation succeeded */ \
114 if ( !pNew ) \
115 return false; \
116 \
117 m_nSize = nSize; \
118 /* copy data to new location */ \
119 memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \
120 delete [] m_pItems; \
121 m_pItems = pNew; \
122 \
123 return true; \
124 } \
125 \
126 /* grow the array */ \
127 void name::Grow(size_t nIncrement) \
128 { \
129 /* only do it if no more place */ \
130 if( (m_nCount == m_nSize) || ((m_nSize - m_nCount) < nIncrement) ) { \
131 if( m_nSize == 0 ) { \
132 /* was empty, determine initial size */ \
133 size_t size = WX_ARRAY_DEFAULT_INITIAL_SIZE; \
134 if (size < nIncrement) size = nIncrement; \
135 /* allocate some memory */ \
136 m_pItems = new T[size]; \
137 /* only grow if allocation succeeded */ \
138 if ( m_pItems ) { \
139 m_nSize = size; \
140 } \
141 } \
142 else \
143 { \
144 /* add at least 50% but not too much */ \
145 size_t ndefIncrement = m_nSize < WX_ARRAY_DEFAULT_INITIAL_SIZE \
146 ? WX_ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1; \
147 if ( ndefIncrement > ARRAY_MAXSIZE_INCREMENT ) \
148 ndefIncrement = ARRAY_MAXSIZE_INCREMENT; \
149 if ( nIncrement < ndefIncrement ) \
150 nIncrement = ndefIncrement; \
151 Realloc(m_nSize + nIncrement); \
152 } \
153 } \
154 } \
155 \
156 /* make sure that the array has at least count elements */ \
157 void name::SetCount(size_t count, T defval) \
158 { \
159 if ( m_nSize < count ) \
160 { \
161 /* need to realloc memory: don't overallocate it here as if */ \
162 /* SetCount() is called, it probably means that the caller */ \
163 /* knows in advance how many elements there will be in the */ \
164 /* array and so it won't be necessary to realloc it later */ \
165 if ( !Realloc(count) ) \
166 { \
167 /* out of memory -- what can we do? */ \
168 return; \
169 } \
170 } \
171 \
172 /* add new elements if we extend the array */ \
173 while ( m_nCount < count ) \
174 { \
175 m_pItems[m_nCount++] = defval; \
176 } \
177 } \
178 \
179 /* dtor */ \
180 name::~name() \
181 { \
182 wxDELETEA(m_pItems); \
183 } \
184 \
185 /* clears the list */ \
186 void name::Clear() \
187 { \
188 m_nSize = \
189 m_nCount = 0; \
190 \
191 wxDELETEA(m_pItems); \
192 } \
193 \
194 /* pre-allocates memory (frees the previous data!) */ \
195 void name::Alloc(size_t nSize) \
196 { \
197 /* only if old buffer was not big enough */ \
198 if ( nSize > m_nSize ) { \
199 wxDELETEA(m_pItems); \
200 m_nSize = 0; \
201 m_pItems = new T[nSize]; \
202 /* only alloc if allocation succeeded */ \
203 if ( m_pItems ) { \
204 m_nSize = nSize; \
205 } \
206 } \
207 \
208 m_nCount = 0; \
209 } \
210 \
211 /* minimizes the memory usage by freeing unused memory */ \
212 void name::Shrink() \
213 { \
214 /* only do it if we have some memory to free */ \
215 if( m_nCount < m_nSize ) { \
216 /* allocates exactly as much memory as we need */ \
217 T *pNew = new T[m_nCount]; \
218 /* only shrink if allocation succeeded */ \
219 if ( pNew ) { \
220 /* copy data to new location */ \
221 memcpy(pNew, m_pItems, m_nCount*sizeof(T)); \
222 delete [] m_pItems; \
223 m_pItems = pNew; \
224 } \
225 } \
226 } \
227 \
228 /* searches the array for an item (forward or backwards) */ \
229 int name::Index(T lItem, bool bFromEnd) const \
230 { \
231 if ( bFromEnd ) { \
232 if ( m_nCount > 0 ) { \
233 size_t n = m_nCount; \
234 do { \
235 if ( m_pItems[--n] == lItem ) \
236 return n; \
237 } \
238 while ( n != 0 ); \
239 } \
240 } \
241 else { \
242 for( size_t n = 0; n < m_nCount; n++ ) { \
243 if( m_pItems[n] == lItem ) \
244 return n; \
245 } \
246 } \
247 \
248 return wxNOT_FOUND; \
249 } \
250 \
251 /* search for a place to insert item into sorted array (binary search) */ \
252 size_t name::IndexForInsert(T lItem, CMPFUNC fnCompare) const \
253 { \
254 size_t i, \
255 lo = 0, \
256 hi = m_nCount; \
257 int res; \
258 \
259 while ( lo < hi ) { \
260 i = (lo + hi)/2; \
261 \
262 res = (*fnCompare)((const void *)(long)lItem, \
263 (const void *)(long)(m_pItems[i])); \
264 if ( res < 0 ) \
265 hi = i; \
266 else if ( res > 0 ) \
267 lo = i + 1; \
268 else { \
269 lo = i; \
270 break; \
271 } \
272 } \
273 \
274 return lo; \
275 } \
276 \
277 /* search for an item in a sorted array (binary search) */ \
278 int name::Index(T lItem, CMPFUNC fnCompare) const \
279 { \
280 size_t n = IndexForInsert(lItem, fnCompare); \
281 \
282 return n < m_nCount && m_pItems[n] == lItem ? (int)n : wxNOT_FOUND; \
283 } \
284 \
285 /* add item at the end */ \
286 void name::Add(T lItem, size_t nInsert) \
287 { \
288 if (nInsert == 0) \
289 return; \
290 Grow(nInsert); \
291 for (size_t i = 0; i < nInsert; i++) \
292 m_pItems[m_nCount++] = lItem; \
293 } \
294 \
295 /* add item assuming the array is sorted with fnCompare function */ \
296 void name::Add(T lItem, CMPFUNC fnCompare) \
297 { \
298 Insert(lItem, IndexForInsert(lItem, fnCompare)); \
299 } \
300 \
301 /* add item at the given position */ \
302 void name::Insert(T lItem, size_t nIndex, size_t nInsert) \
303 { \
304 wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArray::Insert") ); \
305 wxCHECK_RET( m_nCount <= m_nCount + nInsert, \
306 wxT("array size overflow in wxArray::Insert") ); \
307 \
308 if (nInsert == 0) \
309 return; \
310 Grow(nInsert); \
311 \
312 memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex], \
313 (m_nCount - nIndex)*sizeof(T)); \
314 for (size_t i = 0; i < nInsert; i++) \
315 m_pItems[nIndex + i] = lItem; \
316 m_nCount += nInsert; \
317 } \
318 \
319 /* removes item from array (by index) */ \
320 void name::RemoveAt(size_t nIndex, size_t nRemove) \
321 { \
322 wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArray::RemoveAt") ); \
323 wxCHECK_RET( nIndex + nRemove <= m_nCount, \
324 wxT("removing too many elements in wxArray::RemoveAt") ); \
325 \
326 memmove(&m_pItems[nIndex], &m_pItems[nIndex + nRemove], \
327 (m_nCount - nIndex - nRemove)*sizeof(T)); \
328 m_nCount -= nRemove; \
329 } \
330 \
331 /* removes item from array (by value) */ \
332 void name::Remove(T lItem) \
333 { \
334 int iIndex = Index(lItem); \
335 \
336 wxCHECK_RET( iIndex != wxNOT_FOUND, \
337 wxT("removing inexistent item in wxArray::Remove") ); \
338 \
339 RemoveAt((size_t)iIndex); \
340 } \
341 \
342 /* sort array elements using passed comparaison function */ \
343 void name::Sort(CMPFUNC fCmp) \
344 { \
345 qsort(m_pItems, m_nCount, sizeof(T), fCmp); \
346 }
347
348 _WX_DEFINE_BASEARRAY(const void *, wxBaseArrayPtrVoid)
349 _WX_DEFINE_BASEARRAY(short, wxBaseArrayShort)
350 _WX_DEFINE_BASEARRAY(int, wxBaseArrayInt)
351 _WX_DEFINE_BASEARRAY(long, wxBaseArrayLong)
352 //_WX_DEFINE_BASEARRAY(double, wxBaseArrayDouble)
353
wxWidgets (Impactor)