]>
Commit | Line | Data |
---|---|---|
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 | inline int wxStrcmpCppWrapper(const wxChar *p, const wxChar *q) | |
431 | { | |
432 | return wxStrcmp(p, q); | |
433 | } | |
434 | ||
435 | inline int wxStricmpCppWrapper(const wxChar *p, const wxChar *q) | |
436 | { | |
437 | return wxStricmp(p, q); | |
438 | } | |
439 | ||
440 | int wxArrayString::Index(const wxChar* sz, bool bCase, bool WXUNUSED(bFromEnd)) const | |
441 | { | |
442 | wxArrayString::const_iterator it; | |
443 | ||
444 | if (bCase) | |
445 | { | |
446 | it = std::find_if(begin(), end(), | |
447 | std::not1( | |
448 | std::bind2nd( | |
449 | std::ptr_fun(wxStrcmpCppWrapper), sz))); | |
450 | } | |
451 | else // !bCase | |
452 | { | |
453 | it = std::find_if(begin(), end(), | |
454 | std::not1( | |
455 | std::bind2nd( | |
456 | std::ptr_fun(wxStricmpCppWrapper), sz))); | |
457 | } | |
458 | ||
459 | return it == end() ? wxNOT_FOUND : it - begin(); | |
460 | } | |
461 | ||
462 | template<class F> | |
463 | class wxStringCompareLess | |
464 | { | |
465 | public: | |
466 | wxStringCompareLess(F f) : m_f(f) { } | |
467 | bool operator()(const wxChar* s1, const wxChar* s2) | |
468 | { return m_f(s1, s2) < 0; } | |
469 | bool operator()(const wxString& s1, const wxString& s2) | |
470 | { return m_f(s1, s2) < 0; } | |
471 | private: | |
472 | F m_f; | |
473 | }; | |
474 | ||
475 | template<class F> | |
476 | wxStringCompareLess<F> wxStringCompare(F f) | |
477 | { | |
478 | return wxStringCompareLess<F>(f); | |
479 | } | |
480 | ||
481 | void wxArrayString::Sort(CompareFunction function) | |
482 | { | |
483 | std::sort(begin(), end(), wxStringCompare(function)); | |
484 | } | |
485 | ||
486 | void wxArrayString::Sort(bool reverseOrder) | |
487 | { | |
488 | if (reverseOrder) | |
489 | { | |
490 | std::sort(begin(), end(), std::greater<wxString>()); | |
491 | } | |
492 | else | |
493 | { | |
494 | std::sort(begin(), end()); | |
495 | } | |
496 | } | |
497 | ||
498 | int wxSortedArrayString::Index(const wxChar* sz, bool bCase, bool WXUNUSED(bFromEnd)) const | |
499 | { | |
500 | wxSortedArrayString::const_iterator it; | |
501 | wxString s(sz); | |
502 | ||
503 | if (bCase) | |
504 | it = std::lower_bound(begin(), end(), s, | |
505 | wxStringCompare(wxStrcmpCppWrapper)); | |
506 | else | |
507 | it = std::lower_bound(begin(), end(), s, | |
508 | wxStringCompare(wxStricmpCppWrapper)); | |
509 | ||
510 | if (it == end()) | |
511 | return wxNOT_FOUND; | |
512 | ||
513 | if (bCase) | |
514 | { | |
515 | if (wxStrcmp(it->c_str(), sz) != 0) | |
516 | return wxNOT_FOUND; | |
517 | } | |
518 | else | |
519 | { | |
520 | if (wxStricmp(it->c_str(), sz) != 0) | |
521 | return wxNOT_FOUND; | |
522 | } | |
523 | ||
524 | return it - begin(); | |
525 | } | |
526 | ||
527 | #endif |