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: dynarray.cpp 43030 2006-11-04 12:51:01Z VZ $ 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 33wxCOMPILE_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) */ \ 53int 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 */ \ 76size_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) \ 86size_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 \ 93int 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 \ 101void 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 */ \ 111name::name() \ 112{ \ 113 m_nSize = \ 114 m_nCount = 0; \ 115 m_pItems = (T *)NULL; \ 116} \ 117 \ 118/* copy ctor */ \ 119name::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 */ \ 139name& 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 */ \ 163bool 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 */ \ 180void 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 */ \ 210void 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 */ \ 233name::~name() \ 234{ \ 235 wxDELETEA(m_pItems); \ 236} \ 237 \ 238/* clears the list */ \ 239void 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 */ \ 248void 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 */ \ 269void 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 */ \ 279void 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) */ \ 297size_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) */ \ 323int 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) */ \ 335void 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) */ \ 347void 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 */ \ 358void name::Sort(CMPFUNC fCmp) \ 359{ \ 360 qsort(m_pItems, m_nCount, sizeof(T), fCmp); \ 361} \ 362 \ 363void 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 \ 371void 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 \ 379void 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 430inline int wxStrcmpCppWrapper(const wxChar *p, const wxChar *q) 431{ 432 return wxStrcmp(p, q); 433} 434 435inline int wxStricmpCppWrapper(const wxChar *p, const wxChar *q) 436{ 437 return wxStricmp(p, q); 438} 439 440int 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 462template<class F> 463class wxStringCompareLess 464{ 465public: 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; } 471private: 472 F m_f; 473}; 474 475template<class F> 476wxStringCompareLess<F> wxStringCompare(F f) 477{ 478 return wxStringCompareLess<F>(f); 479} 480 481void wxArrayString::Sort(CompareFunction function) 482{ 483 std::sort(begin(), end(), wxStringCompare(function)); 484} 485 486void 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 498int 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 528