src/common/string.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 // Name:        string.cpp
   3 // Purpose:     wxString class
   4 // Author:      Vadim Zeitlin
   5 // Modified by:
   6 // Created:     29/01/98
   7 // RCS-ID:      $Id$
   8 // Copyright:   (c) 1998 Vadim Zeitlin <zeitlin@dptmaths.ens-cachan.fr>
   9 // Licence:     wxWindows license
  10 /////////////////////////////////////////////////////////////////////////////
  11
  12 #ifdef __GNUG__
  13   #pragma implementation "string.h"
  14 #endif
  15
  16 /*
  17  * About ref counting:
  18  *  1) all empty strings use g_strEmpty, nRefs = -1 (set in Init())
  19  *  2) AllocBuffer() sets nRefs to 1, Lock() increments it by one
  20  *  3) Unlock() decrements nRefs and frees memory if it goes to 0
  21  */
  22
  23 // ===========================================================================
  24 // headers, declarations, constants
  25 // ===========================================================================
  26
  27 // For compilers that support precompilation, includes "wx.h".
  28 #include "wx/wxprec.h"
  29
  30 #ifdef __BORLANDC__
  31   #pragma hdrstop
  32 #endif
  33
  34 #ifndef WX_PRECOMP
  35   #include "wx/defs.h"
  36   #include "wx/string.h"
  37   #include "wx/intl.h"
  38   #include "wx/thread.h"
  39 #endif
  40
  41 #include <ctype.h>
  42 #include <string.h>
  43 #include <stdlib.h>
  44
  45 #ifdef __SALFORDC__
  46   #include <clib.h>
  47 #endif
  48
  49 #if wxUSE_UNICODE
  50     #undef wxUSE_EXPERIMENTAL_PRINTF
  51     #ifndef wvsnprintf
  52         #define wxUSE_EXPERIMENTAL_PRINTF 1
  53     #endif
  54 #endif
  55
  56 // allocating extra space for each string consumes more memory but speeds up
  57 // the concatenation operations (nLen is the current string's length)
  58 // NB: EXTRA_ALLOC must be >= 0!
  59 #define EXTRA_ALLOC       (19 - nLen % 16)
  60
  61 // ---------------------------------------------------------------------------
  62 // static class variables definition
  63 // ---------------------------------------------------------------------------
  64
  65 #if defined(__VISAGECPP__) && __IBMCPP__ >= 400
  66 // must define this static for VA or else you get multiply defined symbols
  67 // everywhere
  68 const unsigned int wxSTRING_MAXLEN = UINT_MAX - 100;
  69 #endif // Visual Age
  70
  71 #ifdef  wxSTD_STRING_COMPATIBILITY
  72   const size_t wxString::npos = wxSTRING_MAXLEN;
  73 #endif // wxSTD_STRING_COMPATIBILITY
  74
  75 // ----------------------------------------------------------------------------
  76 // static data
  77 // ----------------------------------------------------------------------------
  78
  79 // for an empty string, GetStringData() will return this address: this
  80 // structure has the same layout as wxStringData and it's data() method will
  81 // return the empty string (dummy pointer)
  82 static const struct
  83 {
  84   wxStringData data;
  85   wxChar dummy;
  86 } g_strEmpty = { {-1, 0, 0}, wxT('\0') };
  87
  88 // empty C style string: points to 'string data' byte of g_strEmpty
  89 extern const wxChar WXDLLEXPORT *wxEmptyString = &g_strEmpty.dummy;
  90
  91 // ----------------------------------------------------------------------------
  92 // conditional compilation
  93 // ----------------------------------------------------------------------------
  94
  95 #if !defined(__WXSW__) && wxUSE_UNICODE
  96   #ifdef wxUSE_EXPERIMENTAL_PRINTF
  97     #undef wxUSE_EXPERIMENTAL_PRINTF
  98   #endif
  99   #define wxUSE_EXPERIMENTAL_PRINTF 1
 100 #endif
 101
 102 // we want to find out if the current platform supports vsnprintf()-like
 103 // function: for Unix this is done with configure, for Windows we test the
 104 // compiler explicitly.
 105 //
 106 // FIXME currently, this is only for ANSI (!Unicode) strings, so we call this
 107 //       function wxVsnprintfA (A for ANSI), should also find one for Unicode
 108 //       strings in Unicode build
 109 #ifdef __WXMSW__
 110     #if defined(__VISUALC__) || (defined(__MINGW32__) && wxUSE_NORLANDER_HEADERS)
 111         #define wxVsnprintfA     _vsnprintf
 112     #endif
 113 #elif defined(__WXMAC__)
 114     #define wxVsnprintfA       vsnprintf
 115 #else   // !Windows
 116     #ifdef HAVE_VSNPRINTF
 117         #define wxVsnprintfA       vsnprintf
 118     #endif
 119 #endif  // Windows/!Windows
 120
 121 #ifndef wxVsnprintfA
 122     // in this case we'll use vsprintf() (which is ANSI and thus should be
 123     // always available), but it's unsafe because it doesn't check for buffer
 124     // size - so give a warning
 125     #define wxVsnprintfA(buf, len, format, arg) vsprintf(buf, format, arg)
 126
 127     #if defined(__VISUALC__)
 128         #pragma message("Using sprintf() because no snprintf()-like function defined")
 129     #elif defined(__GNUG__)
 130         #warning "Using sprintf() because no snprintf()-like function defined"
 131     #endif //compiler
 132 #endif // no vsnprintf
 133
 134 #if defined(_AIX)
 135   // AIX has vsnprintf, but there's no prototype in the system headers.
 136   extern "C" int vsnprintf(char* str, size_t n, const char* format, va_list ap);
 137 #endif
 138
 139 // ----------------------------------------------------------------------------
 140 // global functions
 141 // ----------------------------------------------------------------------------
 142
 143 #if defined(wxSTD_STRING_COMPATIBILITY) && wxUSE_STD_IOSTREAM
 144
 145 // MS Visual C++ version 5.0 provides the new STL headers as well as the old
 146 // iostream ones.
 147 //
 148 // ATTN: you can _not_ use both of these in the same program!
 149
 150 wxSTD istream& operator>>(wxSTD istream& is, wxString& WXUNUSED(str))
 151 {
 152 #if 0
 153   int w = is.width(0);
 154   if ( is.ipfx(0) ) {
 155     streambuf *sb = is.rdbuf();
 156     str.erase();
 157     while ( true ) {
 158       int ch = sb->sbumpc ();
 159       if ( ch == EOF ) {
 160         is.setstate(ios::eofbit);
 161         break;
 162       }
 163       else if ( isspace(ch) ) {
 164         sb->sungetc();
 165         break;
 166       }
 167
 168       str += ch;
 169       if ( --w == 1 )
 170         break;
 171     }
 172   }
 173
 174   is.isfx();
 175   if ( str.length() == 0 )
 176     is.setstate(ios::failbit);
 177 #endif
 178   return is;
 179 }
 180
 181 wxSTD ostream& operator<<(wxSTD ostream& os, const wxString& str)
 182 {
 183   os << str.c_str();
 184   return os;
 185 }
 186
 187 #endif  //std::string compatibility
 188
 189 #ifndef wxVsnprintf
 190 int WXDLLEXPORT wxVsnprintf(wxChar *buf, size_t len,
 191                             const wxChar *format, va_list argptr)
 192 {
 193 #if wxUSE_UNICODE
 194     wxString s;
 195     int iLen = s.PrintfV(format, argptr);
 196     if ( iLen != -1 )
 197     {
 198         wxStrncpy(buf, s.c_str(), len);
 199         buf[len-1] = wxT('\0');
 200     }
 201
 202     return iLen;
 203 #else // ANSI
 204     // vsnprintf() will not terminate the string with '\0' if there is not
 205     // enough place, but we want the string to always be NUL terminated
 206     int rc = wxVsnprintfA(buf, len - 1, format, argptr);
 207     if ( rc == -1 )
 208     {
 209         buf[len] = 0;
 210     }
 211
 212     return rc;
 213 #endif // Unicode/ANSI
 214 }
 215 #else
 216 // GNU libc 2.2 only has for wxVsnprintf for Unicode called vswprintf
 217 // so we imitate wxVsprintf using it.
 218 int WXDLLEXPORT wxVsprintf(wxChar *buf,
 219                            const wxChar *format,
 220                            va_list argptr)
 221 {
 222     return vswprintf( buf, 10000, format, argptr );
 223 }
 224 #endif
 225
 226 #ifndef wxSnprintf
 227 int WXDLLEXPORT wxSnprintf(wxChar *buf, size_t len,
 228                            const wxChar *format, ...)
 229 {
 230     va_list argptr;
 231     va_start(argptr, format);
 232
 233     int iLen = wxVsnprintf(buf, len, format, argptr);
 234
 235     va_end(argptr);
 236
 237     return iLen;
 238 }
 239 #else
 240 // GNU libc 2.2 only has for wxSnprintf for Unicode called swprintf
 241 // so we imitate wxSprintf using it.
 242 int WXDLLEXPORT wxSprintf(wxChar *buf,
 243                           const wxChar *format,
 244                           ...) ATTRIBUTE_PRINTF_2
 245 {
 246     va_list argptr;
 247     va_start(argptr, format);
 248
 249     int iLen = swprintf(buf, 10000, format, argptr);
 250
 251     va_end(argptr);
 252
 253     return iLen;
 254 }
 255 #endif
 256
 257 // ----------------------------------------------------------------------------
 258 // private classes
 259 // ----------------------------------------------------------------------------
 260
 261 // this small class is used to gather statistics for performance tuning
 262 //#define WXSTRING_STATISTICS
 263 #ifdef  WXSTRING_STATISTICS
 264   class Averager
 265   {
 266   public:
 267     Averager(const char *sz) { m_sz = sz; m_nTotal = m_nCount = 0; }
 268    ~Averager()
 269    { printf("wxString: average %s = %f\n", m_sz, ((float)m_nTotal)/m_nCount); }
 270
 271     void Add(size_t n) { m_nTotal += n; m_nCount++; }
 272
 273   private:
 274     size_t m_nCount, m_nTotal;
 275     const char *m_sz;
 276   } g_averageLength("allocation size"),
 277     g_averageSummandLength("summand length"),
 278     g_averageConcatHit("hit probability in concat"),
 279     g_averageInitialLength("initial string length");
 280
 281   #define STATISTICS_ADD(av, val) g_average##av.Add(val)
 282 #else
 283   #define STATISTICS_ADD(av, val)
 284 #endif // WXSTRING_STATISTICS
 285
 286 // ===========================================================================
 287 // wxString class core
 288 // ===========================================================================
 289
 290 // ---------------------------------------------------------------------------
 291 // construction
 292 // ---------------------------------------------------------------------------
 293
 294 // constructs string of <nLength> copies of character <ch>
 295 wxString::wxString(wxChar ch, size_t nLength)
 296 {
 297   Init();
 298
 299   if ( nLength > 0 ) {
 300     if ( !AllocBuffer(nLength) ) {
 301       wxFAIL_MSG( _T("out of memory in wxString::wxString") );
 302       return;
 303     }
 304
 305 #if wxUSE_UNICODE
 306     // memset only works on char
 307     for (size_t n=0; n<nLength; n++) m_pchData[n] = ch;
 308 #else
 309     memset(m_pchData, ch, nLength);
 310 #endif
 311   }
 312 }
 313
 314 // takes nLength elements of psz starting at nPos
 315 void wxString::InitWith(const wxChar *psz, size_t nPos, size_t nLength)
 316 {
 317   Init();
 318
 319   // if the length is not given, assume the string to be NUL terminated
 320   if ( nLength == wxSTRING_MAXLEN ) {
 321     wxASSERT_MSG( nPos <= wxStrlen(psz), _T("index out of bounds") );
 322
 323     nLength = wxStrlen(psz + nPos);
 324   }
 325
 326   STATISTICS_ADD(InitialLength, nLength);
 327
 328   if ( nLength > 0 ) {
 329     // trailing '\0' is written in AllocBuffer()
 330     if ( !AllocBuffer(nLength) ) {
 331       wxFAIL_MSG( _T("out of memory in wxString::InitWith") );
 332       return;
 333     }
 334     memcpy(m_pchData, psz + nPos, nLength*sizeof(wxChar));
 335   }
 336 }
 337
 338 #ifdef  wxSTD_STRING_COMPATIBILITY
 339
 340 // poor man's iterators are "void *" pointers
 341 wxString::wxString(const void *pStart, const void *pEnd)
 342 {
 343   InitWith((const wxChar *)pStart, 0,
 344            (const wxChar *)pEnd - (const wxChar *)pStart);
 345 }
 346
 347 #endif  //std::string compatibility
 348
 349 #if wxUSE_UNICODE
 350
 351 // from multibyte string
 352 wxString::wxString(const char *psz, wxMBConv& conv, size_t nLength)
 353 {
 354   // first get necessary size
 355   size_t nLen = psz ? conv.MB2WC((wchar_t *) NULL, psz, 0) : 0;
 356
 357   // nLength is number of *Unicode* characters here!
 358   if ((nLen != (size_t)-1) && (nLen > nLength))
 359     nLen = nLength;
 360
 361   // empty?
 362   if ( (nLen != 0) && (nLen != (size_t)-1) ) {
 363     if ( !AllocBuffer(nLen) ) {
 364       wxFAIL_MSG( _T("out of memory in wxString::wxString") );
 365       return;
 366     }
 367     conv.MB2WC(m_pchData, psz, nLen);
 368   }
 369   else {
 370     Init();
 371   }
 372 }
 373
 374 #else // ANSI
 375
 376 #if wxUSE_WCHAR_T
 377 // from wide string
 378 wxString::wxString(const wchar_t *pwz, wxMBConv& conv, size_t nLength)
 379 {
 380   // first get necessary size
 381   size_t nLen = 0;
 382   if (pwz)
 383   {
 384     if (nLength == wxSTRING_MAXLEN)
 385       nLen = conv.WC2MB((char *) NULL, pwz, 0);
 386     else
 387       nLen = nLength;
 388   }
 389
 390   // empty?
 391   if ( (nLen != 0) && (nLen != (size_t)-1) ) {
 392     if ( !AllocBuffer(nLen) ) {
 393       wxFAIL_MSG( _T("out of memory in wxString::wxString") );
 394       return;
 395     }
 396     conv.WC2MB(m_pchData, pwz, nLen);
 397   }
 398   else {
 399     Init();
 400   }
 401 }
 402 #endif // wxUSE_WCHAR_T
 403
 404 #endif // Unicode/ANSI
 405
 406 // ---------------------------------------------------------------------------
 407 // memory allocation
 408 // ---------------------------------------------------------------------------
 409
 410 // allocates memory needed to store a C string of length nLen
 411 bool wxString::AllocBuffer(size_t nLen)
 412 {
 413   // allocating 0 sized buffer doesn't make sense, all empty strings should
 414   // reuse g_strEmpty
 415   wxASSERT( nLen >  0 );
 416
 417   // make sure that we don't overflow
 418   wxASSERT( nLen < (INT_MAX / sizeof(wxChar)) -
 419                    (sizeof(wxStringData) + EXTRA_ALLOC + 1) );
 420
 421   STATISTICS_ADD(Length, nLen);
 422
 423   // allocate memory:
 424   // 1) one extra character for '\0' termination
 425   // 2) sizeof(wxStringData) for housekeeping info
 426   wxStringData* pData = (wxStringData*)
 427     malloc(sizeof(wxStringData) + (nLen + EXTRA_ALLOC + 1)*sizeof(wxChar));
 428
 429   if ( pData == NULL ) {
 430     // allocation failures are handled by the caller
 431     return FALSE;
 432   }
 433
 434   pData->nRefs        = 1;
 435   pData->nDataLength  = nLen;
 436   pData->nAllocLength = nLen + EXTRA_ALLOC;
 437   m_pchData           = pData->data();  // data starts after wxStringData
 438   m_pchData[nLen]     = wxT('\0');
 439   return TRUE;
 440 }
 441
 442 // must be called before changing this string
 443 bool wxString::CopyBeforeWrite()
 444 {
 445   wxStringData* pData = GetStringData();
 446
 447   if ( pData->IsShared() ) {
 448     pData->Unlock();                // memory not freed because shared
 449     size_t nLen = pData->nDataLength;
 450     if ( !AllocBuffer(nLen) ) {
 451       // allocation failures are handled by the caller
 452       return FALSE;
 453     }
 454     memcpy(m_pchData, pData->data(), nLen*sizeof(wxChar));
 455   }
 456
 457   wxASSERT( !GetStringData()->IsShared() );  // we must be the only owner
 458
 459   return TRUE;
 460 }
 461
 462 // must be called before replacing contents of this string
 463 bool wxString::AllocBeforeWrite(size_t nLen)
 464 {
 465   wxASSERT( nLen != 0 );  // doesn't make any sense
 466
 467   // must not share string and must have enough space
 468   wxStringData* pData = GetStringData();
 469   if ( pData->IsShared() || pData->IsEmpty() ) {
 470     // can't work with old buffer, get new one
 471     pData->Unlock();
 472     if ( !AllocBuffer(nLen) ) {
 473       // allocation failures are handled by the caller
 474       return FALSE;
 475     }
 476   }
 477   else {
 478     if ( nLen > pData->nAllocLength ) {
 479       // realloc the buffer instead of calling malloc() again, this is more
 480       // efficient
 481       STATISTICS_ADD(Length, nLen);
 482
 483       nLen += EXTRA_ALLOC;
 484
 485       pData = (wxStringData*)
 486           realloc(pData, sizeof(wxStringData) + (nLen + 1)*sizeof(wxChar));
 487
 488       if ( pData == NULL ) {
 489         // allocation failures are handled by the caller
 490         // keep previous data since reallocation failed
 491         return FALSE;
 492       }
 493
 494       pData->nAllocLength = nLen;
 495       m_pchData = pData->data();
 496     }
 497
 498     // now we have enough space, just update the string length
 499     pData->nDataLength = nLen;
 500   }
 501
 502   wxASSERT( !GetStringData()->IsShared() );  // we must be the only owner
 503
 504   return TRUE;
 505 }
 506
 507 // allocate enough memory for nLen characters
 508 bool wxString::Alloc(size_t nLen)
 509 {
 510   wxStringData *pData = GetStringData();
 511   if ( pData->nAllocLength <= nLen ) {
 512     if ( pData->IsEmpty() ) {
 513       nLen += EXTRA_ALLOC;
 514
 515       wxStringData* pData = (wxStringData*)
 516           malloc(sizeof(wxStringData) + (nLen + 1)*sizeof(wxChar));
 517
 518       if ( pData == NULL ) {
 519         // allocation failure handled by caller
 520         return FALSE;
 521       }
 522
 523       pData->nRefs = 1;
 524       pData->nDataLength = 0;
 525       pData->nAllocLength = nLen;
 526       m_pchData = pData->data();  // data starts after wxStringData
 527       m_pchData[0u] = wxT('\0');
 528     }
 529     else if ( pData->IsShared() ) {
 530       pData->Unlock();                // memory not freed because shared
 531       size_t nOldLen = pData->nDataLength;
 532       if ( !AllocBuffer(nLen) ) {
 533         // allocation failure handled by caller
 534         return FALSE;
 535       }
 536       memcpy(m_pchData, pData->data(), nOldLen*sizeof(wxChar));
 537     }
 538     else {
 539       nLen += EXTRA_ALLOC;
 540
 541       pData = (wxStringData *)
 542         realloc(pData, sizeof(wxStringData) + (nLen + 1)*sizeof(wxChar));
 543
 544       if ( pData == NULL ) {
 545         // allocation failure handled by caller
 546         // keep previous data since reallocation failed
 547         return FALSE;
 548       }
 549
 550       // it's not important if the pointer changed or not (the check for this
 551       // is not faster than assigning to m_pchData in all cases)
 552       pData->nAllocLength = nLen;
 553       m_pchData = pData->data();
 554     }
 555   }
 556   //else: we've already got enough
 557   return TRUE;
 558 }
 559
 560 // shrink to minimal size (releasing extra memory)
 561 bool wxString::Shrink()
 562 {
 563   wxStringData *pData = GetStringData();
 564
 565   size_t nLen = pData->nDataLength;
 566   void *p = realloc(pData, sizeof(wxStringData) + (nLen + 1)*sizeof(wxChar));
 567
 568   if ( p == NULL) {
 569       wxFAIL_MSG( _T("out of memory reallocating wxString data") );
 570       // keep previous data since reallocation failed
 571       return FALSE;
 572   }
 573
 574   if ( p != pData )
 575   {
 576       // contrary to what one might believe, some realloc() implementation do
 577       // move the memory block even when its size is reduced
 578       pData = (wxStringData *)p;
 579
 580       m_pchData = pData->data();
 581   }
 582
 583   pData->nAllocLength = nLen;
 584
 585   return TRUE;
 586 }
 587
 588 // get the pointer to writable buffer of (at least) nLen bytes
 589 wxChar *wxString::GetWriteBuf(size_t nLen)
 590 {
 591   if ( !AllocBeforeWrite(nLen) ) {
 592     // allocation failure handled by caller
 593     return NULL;
 594   }
 595
 596   wxASSERT( GetStringData()->nRefs == 1 );
 597   GetStringData()->Validate(FALSE);
 598
 599   return m_pchData;
 600 }
 601
 602 // put string back in a reasonable state after GetWriteBuf
 603 void wxString::UngetWriteBuf()
 604 {
 605   GetStringData()->nDataLength = wxStrlen(m_pchData);
 606   GetStringData()->Validate(TRUE);
 607 }
 608
 609 void wxString::UngetWriteBuf(size_t nLen)
 610 {
 611   GetStringData()->nDataLength = nLen;
 612   GetStringData()->Validate(TRUE);
 613 }
 614
 615 // ---------------------------------------------------------------------------
 616 // data access
 617 // ---------------------------------------------------------------------------
 618
 619 // all functions are inline in string.h
 620
 621 // ---------------------------------------------------------------------------
 622 // assignment operators
 623 // ---------------------------------------------------------------------------
 624
 625 // helper function: does real copy
 626 bool wxString::AssignCopy(size_t nSrcLen, const wxChar *pszSrcData)
 627 {
 628   if ( nSrcLen == 0 ) {
 629     Reinit();
 630   }
 631   else {
 632     if ( !AllocBeforeWrite(nSrcLen) ) {
 633       // allocation failure handled by caller
 634       return FALSE;
 635     }
 636     memcpy(m_pchData, pszSrcData, nSrcLen*sizeof(wxChar));
 637     GetStringData()->nDataLength = nSrcLen;
 638     m_pchData[nSrcLen] = wxT('\0');
 639   }
 640   return TRUE;
 641 }
 642
 643 // assigns one string to another
 644 wxString& wxString::operator=(const wxString& stringSrc)
 645 {
 646   wxASSERT( stringSrc.GetStringData()->IsValid() );
 647
 648   // don't copy string over itself
 649   if ( m_pchData != stringSrc.m_pchData ) {
 650     if ( stringSrc.GetStringData()->IsEmpty() ) {
 651       Reinit();
 652     }
 653     else {
 654       // adjust references
 655       GetStringData()->Unlock();
 656       m_pchData = stringSrc.m_pchData;
 657       GetStringData()->Lock();
 658     }
 659   }
 660
 661   return *this;
 662 }
 663
 664 // assigns a single character
 665 wxString& wxString::operator=(wxChar ch)
 666 {
 667   if ( !AssignCopy(1, &ch) ) {
 668     wxFAIL_MSG( _T("out of memory in wxString::operator=(wxChar)") );
 669   }
 670   return *this;
 671 }
 672
 673
 674 // assigns C string
 675 wxString& wxString::operator=(const wxChar *psz)
 676 {
 677   if ( !AssignCopy(wxStrlen(psz), psz) ) {
 678     wxFAIL_MSG( _T("out of memory in wxString::operator=(const wxChar *)") );
 679   }
 680   return *this;
 681 }
 682
 683 #if !wxUSE_UNICODE
 684
 685 // same as 'signed char' variant
 686 wxString& wxString::operator=(const unsigned char* psz)
 687 {
 688   *this = (const char *)psz;
 689   return *this;
 690 }
 691
 692 #if wxUSE_WCHAR_T
 693 wxString& wxString::operator=(const wchar_t *pwz)
 694 {
 695   wxString str(pwz);
 696   *this = str;
 697   return *this;
 698 }
 699 #endif
 700
 701 #endif
 702
 703 // ---------------------------------------------------------------------------
 704 // string concatenation
 705 // ---------------------------------------------------------------------------
 706
 707 // add something to this string
 708 bool wxString::ConcatSelf(int nSrcLen, const wxChar *pszSrcData)
 709 {
 710   STATISTICS_ADD(SummandLength, nSrcLen);
 711
 712   // concatenating an empty string is a NOP
 713   if ( nSrcLen > 0 ) {
 714     wxStringData *pData = GetStringData();
 715     size_t nLen = pData->nDataLength;
 716     size_t nNewLen = nLen + nSrcLen;
 717
 718     // alloc new buffer if current is too small
 719     if ( pData->IsShared() ) {
 720       STATISTICS_ADD(ConcatHit, 0);
 721
 722       // we have to allocate another buffer
 723       wxStringData* pOldData = GetStringData();
 724       if ( !AllocBuffer(nNewLen) ) {
 725           // allocation failure handled by caller
 726           return FALSE;
 727       }
 728       memcpy(m_pchData, pOldData->data(), nLen*sizeof(wxChar));
 729       pOldData->Unlock();
 730     }
 731     else if ( nNewLen > pData->nAllocLength ) {
 732       STATISTICS_ADD(ConcatHit, 0);
 733
 734       // we have to grow the buffer
 735       if ( !Alloc(nNewLen) ) {
 736           // allocation failure handled by caller
 737           return FALSE;
 738       }
 739     }
 740     else {
 741       STATISTICS_ADD(ConcatHit, 1);
 742
 743       // the buffer is already big enough
 744     }
 745
 746     // should be enough space
 747     wxASSERT( nNewLen <= GetStringData()->nAllocLength );
 748
 749     // fast concatenation - all is done in our buffer
 750     memcpy(m_pchData + nLen, pszSrcData, nSrcLen*sizeof(wxChar));
 751
 752     m_pchData[nNewLen] = wxT('\0');          // put terminating '\0'
 753     GetStringData()->nDataLength = nNewLen; // and fix the length
 754   }
 755   //else: the string to append was empty
 756   return TRUE;
 757 }
 758
 759 /*
 760  * concatenation functions come in 5 flavours:
 761  *  string + string
 762  *  char   + string      and      string + char
 763  *  C str  + string      and      string + C str
 764  */
 765
 766 wxString operator+(const wxString& str1, const wxString& str2)
 767 {
 768   wxASSERT( str1.GetStringData()->IsValid() );
 769   wxASSERT( str2.GetStringData()->IsValid() );
 770
 771   wxString s = str1;
 772   s += str2;
 773
 774   return s;
 775 }
 776
 777 wxString operator+(const wxString& str, wxChar ch)
 778 {
 779   wxASSERT( str.GetStringData()->IsValid() );
 780
 781   wxString s = str;
 782   s += ch;
 783
 784   return s;
 785 }
 786
 787 wxString operator+(wxChar ch, const wxString& str)
 788 {
 789   wxASSERT( str.GetStringData()->IsValid() );
 790
 791   wxString s = ch;
 792   s += str;
 793
 794   return s;
 795 }
 796
 797 wxString operator+(const wxString& str, const wxChar *psz)
 798 {
 799   wxASSERT( str.GetStringData()->IsValid() );
 800
 801   wxString s;
 802   if ( !s.Alloc(wxStrlen(psz) + str.Len()) ) {
 803     wxFAIL_MSG( _T("out of memory in wxString::operator+") );
 804   }
 805   s = str;
 806   s += psz;
 807
 808   return s;
 809 }
 810
 811 wxString operator+(const wxChar *psz, const wxString& str)
 812 {
 813   wxASSERT( str.GetStringData()->IsValid() );
 814
 815   wxString s;
 816   if ( !s.Alloc(wxStrlen(psz) + str.Len()) ) {
 817     wxFAIL_MSG( _T("out of memory in wxString::operator+") );
 818   }
 819   s = psz;
 820   s += str;
 821
 822   return s;
 823 }
 824
 825 // ===========================================================================
 826 // other common string functions
 827 // ===========================================================================
 828
 829 #if wxUSE_UNICODE
 830 wxString wxString::FromAscii( char *ascii )
 831 {
 832     if (!ascii)
 833        return wxEmptyString;
 834
 835     size_t len = strlen( ascii );
 836     wxString res;
 837     res.AllocBuffer( len );
 838     wchar_t *dest = (wchar_t*)(const wchar_t*) res.c_str();
 839
 840     for (size_t i = 0; i < len+1; i++)
 841        dest[i] = (wchar_t) ascii[i];
 842
 843     return res;
 844 }
 845
 846 const wxCharBuffer wxString::ToAscii() const
 847 {
 848     if (IsNull())
 849        return wxCharBuffer( (const char*)NULL );
 850
 851     size_t len = Len();
 852     wxCharBuffer buffer( len ); // allocates len+1
 853
 854     char *dest = (char*)(const char*) buffer;
 855
 856     for (size_t i = 0; i < len+1; i++)
 857     {
 858         if (m_pchData[i] > 127)
 859             dest[i] = '_';
 860         else
 861             dest[i] = (char) m_pchData[i];
 862     }
 863
 864     return buffer;
 865 }
 866 #endif
 867
 868 // ---------------------------------------------------------------------------
 869 // simple sub-string extraction
 870 // ---------------------------------------------------------------------------
 871
 872 // helper function: clone the data attached to this string
 873 bool wxString::AllocCopy(wxString& dest, int nCopyLen, int nCopyIndex) const
 874 {
 875   if ( nCopyLen == 0 ) {
 876     dest.Init();
 877   }
 878   else {
 879     if ( !dest.AllocBuffer(nCopyLen) ) {
 880       // allocation failure handled by caller
 881       return FALSE;
 882     }
 883     memcpy(dest.m_pchData, m_pchData + nCopyIndex, nCopyLen*sizeof(wxChar));
 884   }
 885   return TRUE;
 886 }
 887
 888 // extract string of length nCount starting at nFirst
 889 wxString wxString::Mid(size_t nFirst, size_t nCount) const
 890 {
 891   wxStringData *pData = GetStringData();
 892   size_t nLen = pData->nDataLength;
 893
 894   // default value of nCount is wxSTRING_MAXLEN and means "till the end"
 895   if ( nCount == wxSTRING_MAXLEN )
 896   {
 897     nCount = nLen - nFirst;
 898   }
 899
 900   // out-of-bounds requests return sensible things
 901   if ( nFirst + nCount > nLen )
 902   {
 903     nCount = nLen - nFirst;
 904   }
 905
 906   if ( nFirst > nLen )
 907   {
 908     // AllocCopy() will return empty string
 909     nCount = 0;
 910   }
 911
 912   wxString dest;
 913   if ( !AllocCopy(dest, nCount, nFirst) ) {
 914       wxFAIL_MSG( _T("out of memory in wxString::Mid") );
 915   }
 916
 917   return dest;
 918 }
 919
 920 // check that the tring starts with prefix and return the rest of the string
 921 // in the provided pointer if it is not NULL, otherwise return FALSE
 922 bool wxString::StartsWith(const wxChar *prefix, wxString *rest) const
 923 {
 924     wxASSERT_MSG( prefix, _T("invalid parameter in wxString::StartsWith") );
 925
 926     // first check if the beginning of the string matches the prefix: note
 927     // that we don't have to check that we don't run out of this string as
 928     // when we reach the terminating NUL, either prefix string ends too (and
 929     // then it's ok) or we break out of the loop because there is no match
 930     const wxChar *p = c_str();
 931     while ( *prefix )
 932     {
 933         if ( *prefix++ != *p++ )
 934         {
 935             // no match
 936             return FALSE;
 937         }
 938     }
 939
 940     if ( rest )
 941     {
 942         // put the rest of the string into provided pointer
 943         *rest = p;
 944     }
 945
 946     return TRUE;
 947 }
 948
 949 // extract nCount last (rightmost) characters
 950 wxString wxString::Right(size_t nCount) const
 951 {
 952   if ( nCount > (size_t)GetStringData()->nDataLength )
 953     nCount = GetStringData()->nDataLength;
 954
 955   wxString dest;
 956   if ( !AllocCopy(dest, nCount, GetStringData()->nDataLength - nCount) ) {
 957     wxFAIL_MSG( _T("out of memory in wxString::Right") );
 958   }
 959   return dest;
 960 }
 961
 962 // get all characters after the last occurence of ch
 963 // (returns the whole string if ch not found)
 964 wxString wxString::AfterLast(wxChar ch) const
 965 {
 966   wxString str;
 967   int iPos = Find(ch, TRUE);
 968   if ( iPos == wxNOT_FOUND )
 969     str = *this;
 970   else
 971     str = c_str() + iPos + 1;
 972
 973   return str;
 974 }
 975
 976 // extract nCount first (leftmost) characters
 977 wxString wxString::Left(size_t nCount) const
 978 {
 979   if ( nCount > (size_t)GetStringData()->nDataLength )
 980     nCount = GetStringData()->nDataLength;
 981
 982   wxString dest;
 983   if ( !AllocCopy(dest, nCount, 0) ) {
 984     wxFAIL_MSG( _T("out of memory in wxString::Left") );
 985   }
 986   return dest;
 987 }
 988
 989 // get all characters before the first occurence of ch
 990 // (returns the whole string if ch not found)
 991 wxString wxString::BeforeFirst(wxChar ch) const
 992 {
 993   wxString str;
 994   for ( const wxChar *pc = m_pchData; *pc != wxT('\0') && *pc != ch; pc++ )
 995     str += *pc;
 996
 997   return str;
 998 }
 999
1000 /// get all characters before the last occurence of ch
1001 /// (returns empty string if ch not found)
1002 wxString wxString::BeforeLast(wxChar ch) const
1003 {
1004   wxString str;
1005   int iPos = Find(ch, TRUE);
1006   if ( iPos != wxNOT_FOUND && iPos != 0 )
1007     str = wxString(c_str(), iPos);
1008
1009   return str;
1010 }
1011
1012 /// get all characters after the first occurence of ch
1013 /// (returns empty string if ch not found)
1014 wxString wxString::AfterFirst(wxChar ch) const
1015 {
1016   wxString str;
1017   int iPos = Find(ch);
1018   if ( iPos != wxNOT_FOUND )
1019     str = c_str() + iPos + 1;
1020
1021   return str;
1022 }
1023
1024 // replace first (or all) occurences of some substring with another one
1025 size_t wxString::Replace(const wxChar *szOld, const wxChar *szNew, bool bReplaceAll)
1026 {
1027   size_t uiCount = 0;   // count of replacements made
1028
1029   size_t uiOldLen = wxStrlen(szOld);
1030
1031   wxString strTemp;
1032   const wxChar *pCurrent = m_pchData;
1033   const wxChar *pSubstr;
1034   while ( *pCurrent != wxT('\0') ) {
1035     pSubstr = wxStrstr(pCurrent, szOld);
1036     if ( pSubstr == NULL ) {
1037       // strTemp is unused if no replacements were made, so avoid the copy
1038       if ( uiCount == 0 )
1039         return 0;
1040
1041       strTemp += pCurrent;    // copy the rest
1042       break;                  // exit the loop
1043     }
1044     else {
1045       // take chars before match
1046       if ( !strTemp.ConcatSelf(pSubstr - pCurrent, pCurrent) ) {
1047         wxFAIL_MSG( _T("out of memory in wxString::Replace") );
1048         return 0;
1049       }
1050       strTemp += szNew;
1051       pCurrent = pSubstr + uiOldLen;  // restart after match
1052
1053       uiCount++;
1054
1055       // stop now?
1056       if ( !bReplaceAll ) {
1057         strTemp += pCurrent;    // copy the rest
1058         break;                  // exit the loop
1059       }
1060     }
1061   }
1062
1063   // only done if there were replacements, otherwise would have returned above
1064   *this = strTemp;
1065
1066   return uiCount;
1067 }
1068
1069 bool wxString::IsAscii() const
1070 {
1071   const wxChar *s = (const wxChar*) *this;
1072   while(*s){
1073     if(!isascii(*s)) return(FALSE);
1074     s++;
1075   }
1076   return(TRUE);
1077 }
1078
1079 bool wxString::IsWord() const
1080 {
1081   const wxChar *s = (const wxChar*) *this;
1082   while(*s){
1083     if(!wxIsalpha(*s)) return(FALSE);
1084     s++;
1085   }
1086   return(TRUE);
1087 }
1088
1089 bool wxString::IsNumber() const
1090 {
1091   const wxChar *s = (const wxChar*) *this;
1092   if (wxStrlen(s))
1093      if ((s[0] == '-') || (s[0] == '+')) s++;
1094   while(*s){
1095     if(!wxIsdigit(*s)) return(FALSE);
1096     s++;
1097   }
1098   return(TRUE);
1099 }
1100
1101 wxString wxString::Strip(stripType w) const
1102 {
1103     wxString s = *this;
1104     if ( w & leading ) s.Trim(FALSE);
1105     if ( w & trailing ) s.Trim(TRUE);
1106     return s;
1107 }
1108
1109 // ---------------------------------------------------------------------------
1110 // case conversion
1111 // ---------------------------------------------------------------------------
1112
1113 wxString& wxString::MakeUpper()
1114 {
1115   if ( !CopyBeforeWrite() ) {
1116     wxFAIL_MSG( _T("out of memory in wxString::MakeUpper") );
1117     return *this;
1118   }
1119
1120   for ( wxChar *p = m_pchData; *p; p++ )
1121     *p = (wxChar)wxToupper(*p);
1122
1123   return *this;
1124 }
1125
1126 wxString& wxString::MakeLower()
1127 {
1128   if ( !CopyBeforeWrite() ) {
1129     wxFAIL_MSG( _T("out of memory in wxString::MakeLower") );
1130     return *this;
1131   }
1132
1133   for ( wxChar *p = m_pchData; *p; p++ )
1134     *p = (wxChar)wxTolower(*p);
1135
1136   return *this;
1137 }
1138
1139 // ---------------------------------------------------------------------------
1140 // trimming and padding
1141 // ---------------------------------------------------------------------------
1142
1143 // some compilers (VC++ 6.0 not to name them) return TRUE for a call to
1144 // isspace('ê') in the C locale which seems to be broken to me, but we have to
1145 // live with this by checking that the character is a 7 bit one - even if this
1146 // may fail to detect some spaces (I don't know if Unicode doesn't have
1147 // space-like symbols somewhere except in the first 128 chars), it is arguably
1148 // still better than trimming away accented letters
1149 inline int wxSafeIsspace(wxChar ch) { return (ch < 127) && wxIsspace(ch); }
1150
1151 // trims spaces (in the sense of isspace) from left or right side
1152 wxString& wxString::Trim(bool bFromRight)
1153 {
1154   // first check if we're going to modify the string at all
1155   if ( !IsEmpty() &&
1156        (
1157         (bFromRight && wxSafeIsspace(GetChar(Len() - 1))) ||
1158         (!bFromRight && wxSafeIsspace(GetChar(0u)))
1159        )
1160      )
1161   {
1162     // ok, there is at least one space to trim
1163     if ( !CopyBeforeWrite() ) {
1164       wxFAIL_MSG( _T("out of memory in wxString::Trim") );
1165       return *this;
1166     }
1167
1168     if ( bFromRight )
1169     {
1170       // find last non-space character
1171       wxChar *psz = m_pchData + GetStringData()->nDataLength - 1;
1172       while ( wxSafeIsspace(*psz) && (psz >= m_pchData) )
1173         psz--;
1174
1175       // truncate at trailing space start
1176       *++psz = wxT('\0');
1177       GetStringData()->nDataLength = psz - m_pchData;
1178     }
1179     else
1180     {
1181       // find first non-space character
1182       const wxChar *psz = m_pchData;
1183       while ( wxSafeIsspace(*psz) )
1184         psz++;
1185
1186       // fix up data and length
1187       int nDataLength = GetStringData()->nDataLength - (psz - (const wxChar*) m_pchData);
1188       memmove(m_pchData, psz, (nDataLength + 1)*sizeof(wxChar));
1189       GetStringData()->nDataLength = nDataLength;
1190     }
1191   }
1192
1193   return *this;
1194 }
1195
1196 // adds nCount characters chPad to the string from either side
1197 wxString& wxString::Pad(size_t nCount, wxChar chPad, bool bFromRight)
1198 {
1199   wxString s(chPad, nCount);
1200
1201   if ( bFromRight )
1202     *this += s;
1203   else
1204   {
1205     s += *this;
1206     *this = s;
1207   }
1208
1209   return *this;
1210 }
1211
1212 // truncate the string
1213 wxString& wxString::Truncate(size_t uiLen)
1214 {
1215   if ( uiLen < Len() ) {
1216     if ( !CopyBeforeWrite() ) {
1217       wxFAIL_MSG( _T("out of memory in wxString::Truncate") );
1218       return *this;
1219     }
1220
1221     *(m_pchData + uiLen) = wxT('\0');
1222     GetStringData()->nDataLength = uiLen;
1223   }
1224   //else: nothing to do, string is already short enough
1225
1226   return *this;
1227 }
1228
1229 // ---------------------------------------------------------------------------
1230 // finding (return wxNOT_FOUND if not found and index otherwise)
1231 // ---------------------------------------------------------------------------
1232
1233 // find a character
1234 int wxString::Find(wxChar ch, bool bFromEnd) const
1235 {
1236   const wxChar *psz = bFromEnd ? wxStrrchr(m_pchData, ch) : wxStrchr(m_pchData, ch);
1237
1238   return (psz == NULL) ? wxNOT_FOUND : psz - (const wxChar*) m_pchData;
1239 }
1240
1241 // find a sub-string (like strstr)
1242 int wxString::Find(const wxChar *pszSub) const
1243 {
1244   const wxChar *psz = wxStrstr(m_pchData, pszSub);
1245
1246   return (psz == NULL) ? wxNOT_FOUND : psz - (const wxChar*) m_pchData;
1247 }
1248
1249 // ----------------------------------------------------------------------------
1250 // conversion to numbers
1251 // ----------------------------------------------------------------------------
1252
1253 bool wxString::ToLong(long *val, int base) const
1254 {
1255     wxCHECK_MSG( val, FALSE, _T("NULL pointer in wxString::ToLong") );
1256     wxASSERT_MSG( !base || (base > 1 && base <= 36), _T("invalid base") );
1257
1258     const wxChar *start = c_str();
1259     wxChar *end;
1260     *val = wxStrtol(start, &end, base);
1261
1262     // return TRUE only if scan was stopped by the terminating NUL and if the
1263     // string was not empty to start with
1264     return !*end && (end != start);
1265 }
1266
1267 bool wxString::ToULong(unsigned long *val, int base) const
1268 {
1269     wxCHECK_MSG( val, FALSE, _T("NULL pointer in wxString::ToULong") );
1270     wxASSERT_MSG( !base || (base > 1 && base <= 36), _T("invalid base") );
1271
1272     const wxChar *start = c_str();
1273     wxChar *end;
1274     *val = wxStrtoul(start, &end, base);
1275
1276     // return TRUE only if scan was stopped by the terminating NUL and if the
1277     // string was not empty to start with
1278     return !*end && (end != start);
1279 }
1280
1281 bool wxString::ToDouble(double *val) const
1282 {
1283     wxCHECK_MSG( val, FALSE, _T("NULL pointer in wxString::ToDouble") );
1284
1285     const wxChar *start = c_str();
1286     wxChar *end;
1287     *val = wxStrtod(start, &end);
1288
1289     // return TRUE only if scan was stopped by the terminating NUL and if the
1290     // string was not empty to start with
1291     return !*end && (end != start);
1292 }
1293
1294 // ---------------------------------------------------------------------------
1295 // formatted output
1296 // ---------------------------------------------------------------------------
1297
1298 /* static */
1299 wxString wxString::Format(const wxChar *pszFormat, ...)
1300 {
1301     va_list argptr;
1302     va_start(argptr, pszFormat);
1303
1304     wxString s;
1305     s.PrintfV(pszFormat, argptr);
1306
1307     va_end(argptr);
1308
1309     return s;
1310 }
1311
1312 /* static */
1313 wxString wxString::FormatV(const wxChar *pszFormat, va_list argptr)
1314 {
1315     wxString s;
1316     s.PrintfV(pszFormat, argptr);
1317     return s;
1318 }
1319
1320 int wxString::Printf(const wxChar *pszFormat, ...)
1321 {
1322   va_list argptr;
1323   va_start(argptr, pszFormat);
1324
1325   int iLen = PrintfV(pszFormat, argptr);
1326
1327   va_end(argptr);
1328
1329   return iLen;
1330 }
1331
1332 int wxString::PrintfV(const wxChar* pszFormat, va_list argptr)
1333 {
1334 #if wxUSE_EXPERIMENTAL_PRINTF
1335   // the new implementation
1336
1337   // buffer to avoid dynamic memory allocation each time for small strings
1338   char szScratch[1024];
1339
1340   Reinit();
1341   for (size_t n = 0; pszFormat[n]; n++)
1342     if (pszFormat[n] == wxT('%')) {
1343       static char s_szFlags[256] = "%";
1344       size_t flagofs = 1;
1345       bool adj_left = FALSE, in_prec = FALSE,
1346            prec_dot = FALSE, done = FALSE;
1347       int ilen = 0;
1348       size_t min_width = 0, max_width = wxSTRING_MAXLEN;
1349       do {
1350 #define CHECK_PREC if (in_prec && !prec_dot) { s_szFlags[flagofs++] = '.'; prec_dot = TRUE; }
1351         switch (pszFormat[++n]) {
1352         case wxT('\0'):
1353           done = TRUE;
1354           break;
1355         case wxT('%'):
1356           *this += wxT('%');
1357           done = TRUE;
1358           break;
1359         case wxT('#'):
1360         case wxT('0'):
1361         case wxT(' '):
1362         case wxT('+'):
1363         case wxT('\''):
1364           CHECK_PREC
1365           s_szFlags[flagofs++] = pszFormat[n];
1366           break;
1367         case wxT('-'):
1368           CHECK_PREC
1369           adj_left = TRUE;
1370           s_szFlags[flagofs++] = pszFormat[n];
1371           break;
1372         case wxT('.'):
1373           CHECK_PREC
1374           in_prec = TRUE;
1375           prec_dot = FALSE;
1376           max_width = 0;
1377           // dot will be auto-added to s_szFlags if non-negative number follows
1378           break;
1379         case wxT('h'):
1380           ilen = -1;
1381           CHECK_PREC
1382           s_szFlags[flagofs++] = pszFormat[n];
1383           break;
1384         case wxT('l'):
1385           ilen = 1;
1386           CHECK_PREC
1387           s_szFlags[flagofs++] = pszFormat[n];
1388           break;
1389         case wxT('q'):
1390         case wxT('L'):
1391           ilen = 2;
1392           CHECK_PREC
1393           s_szFlags[flagofs++] = pszFormat[n];
1394           break;
1395         case wxT('Z'):
1396           ilen = 3;
1397           CHECK_PREC
1398           s_szFlags[flagofs++] = pszFormat[n];
1399           break;
1400         case wxT('*'):
1401           {
1402             int len = va_arg(argptr, int);
1403             if (in_prec) {
1404               if (len<0) break;
1405               CHECK_PREC
1406               max_width = len;
1407             } else {
1408               if (len<0) {
1409                 adj_left = !adj_left;
1410                 s_szFlags[flagofs++] = '-';
1411                 len = -len;
1412               }
1413               min_width = len;
1414             }
1415             flagofs += ::sprintf(s_szFlags+flagofs,"%d",len);
1416           }
1417           break;
1418         case wxT('1'): case wxT('2'): case wxT('3'):
1419         case wxT('4'): case wxT('5'): case wxT('6'):
1420         case wxT('7'): case wxT('8'): case wxT('9'):
1421           {
1422             int len = 0;
1423             CHECK_PREC
1424             while ((pszFormat[n]>=wxT('0')) && (pszFormat[n]<=wxT('9'))) {
1425               s_szFlags[flagofs++] = pszFormat[n];
1426               len = len*10 + (pszFormat[n] - wxT('0'));
1427               n++;
1428             }
1429             if (in_prec) max_width = len;
1430             else min_width = len;
1431             n--; // the main loop pre-increments n again
1432           }
1433           break;
1434         case wxT('d'):
1435         case wxT('i'):
1436         case wxT('o'):
1437         case wxT('u'):
1438         case wxT('x'):
1439         case wxT('X'):
1440           CHECK_PREC
1441           s_szFlags[flagofs++] = pszFormat[n];
1442           s_szFlags[flagofs] = '\0';
1443           if (ilen == 0 ) {
1444             int val = va_arg(argptr, int);
1445             ::sprintf(szScratch, s_szFlags, val);
1446           }
1447           else if (ilen == -1) {
1448             short int val = va_arg(argptr, short int);
1449             ::sprintf(szScratch, s_szFlags, val);
1450           }
1451           else if (ilen == 1) {
1452             long int val = va_arg(argptr, long int);
1453             ::sprintf(szScratch, s_szFlags, val);
1454           }
1455           else if (ilen == 2) {
1456 #if SIZEOF_LONG_LONG
1457             long long int val = va_arg(argptr, long long int);
1458             ::sprintf(szScratch, s_szFlags, val);
1459 #else
1460             long int val = va_arg(argptr, long int);
1461             ::sprintf(szScratch, s_szFlags, val);
1462 #endif
1463           }
1464           else if (ilen == 3) {
1465             size_t val = va_arg(argptr, size_t);
1466             ::sprintf(szScratch, s_szFlags, val);
1467           }
1468           *this += wxString(szScratch);
1469           done = TRUE;
1470           break;
1471         case wxT('e'):
1472         case wxT('E'):
1473         case wxT('f'):
1474         case wxT('g'):
1475         case wxT('G'):
1476           CHECK_PREC
1477           s_szFlags[flagofs++] = pszFormat[n];
1478           s_szFlags[flagofs] = '\0';
1479           if (ilen == 2) {
1480             long double val = va_arg(argptr, long double);
1481             ::sprintf(szScratch, s_szFlags, val);
1482           } else {
1483             double val = va_arg(argptr, double);
1484             ::sprintf(szScratch, s_szFlags, val);
1485           }
1486           *this += wxString(szScratch);
1487           done = TRUE;
1488           break;
1489         case wxT('p'):
1490           {
1491             void *val = va_arg(argptr, void *);
1492             CHECK_PREC
1493             s_szFlags[flagofs++] = pszFormat[n];
1494             s_szFlags[flagofs] = '\0';
1495             ::sprintf(szScratch, s_szFlags, val);
1496             *this += wxString(szScratch);
1497             done = TRUE;
1498           }
1499           break;
1500         case wxT('c'):
1501           {
1502             wxChar val = va_arg(argptr, int);
1503             // we don't need to honor padding here, do we?
1504             *this += val;
1505             done = TRUE;
1506           }
1507           break;
1508         case wxT('s'):
1509           if (ilen == -1) {
1510             // wx extension: we'll let %hs mean non-Unicode strings
1511             char *val = va_arg(argptr, char *);
1512 #if wxUSE_UNICODE
1513             // ASCII->Unicode constructor handles max_width right
1514             wxString s(val, wxConvLibc, max_width);
1515 #else
1516             size_t len = wxSTRING_MAXLEN;
1517             if (val) {
1518               for (len = 0; val[len] && (len<max_width); len++);
1519             } else val = wxT("(null)");
1520             wxString s(val, len);
1521 #endif
1522             if (s.Len() < min_width)
1523               s.Pad(min_width - s.Len(), wxT(' '), adj_left);
1524             *this += s;
1525           } else {
1526             wxChar *val = va_arg(argptr, wxChar *);
1527             size_t len = wxSTRING_MAXLEN;
1528             if (val) {
1529               for (len = 0; val[len] && (len<max_width); len++);
1530             } else val = wxT("(null)");
1531             wxString s(val, len);
1532             if (s.Len() < min_width)
1533               s.Pad(min_width - s.Len(), wxT(' '), adj_left);
1534             *this += s;
1535           }
1536           done = TRUE;
1537           break;
1538         case wxT('n'):
1539           if (ilen == 0) {
1540             int *val = va_arg(argptr, int *);
1541             *val = Len();
1542           }
1543           else if (ilen == -1) {
1544             short int *val = va_arg(argptr, short int *);
1545             *val = Len();
1546           }
1547           else if (ilen >= 1) {
1548             long int *val = va_arg(argptr, long int *);
1549             *val = Len();
1550           }
1551           done = TRUE;
1552           break;
1553         default:
1554           if (wxIsalpha(pszFormat[n]))
1555             // probably some flag not taken care of here yet
1556             s_szFlags[flagofs++] = pszFormat[n];
1557           else {
1558             // bad format
1559             *this += wxT('%'); // just to pass the glibc tst-printf.c
1560             n--;
1561             done = TRUE;
1562           }
1563           break;
1564         }
1565 #undef CHECK_PREC
1566       } while (!done);
1567     } else *this += pszFormat[n];
1568
1569 #else
1570   // buffer to avoid dynamic memory allocation each time for small strings
1571   char szScratch[1024];
1572
1573   // NB: wxVsnprintf() may return either less than the buffer size or -1 if
1574   //     there is not enough place depending on implementation
1575   int iLen = wxVsnprintfA(szScratch, WXSIZEOF(szScratch), (char *)pszFormat, argptr);
1576   if ( iLen != -1 ) {
1577     // the whole string is in szScratch
1578     *this = szScratch;
1579   }
1580   else {
1581       bool outOfMemory = FALSE;
1582       int size = 2*WXSIZEOF(szScratch);
1583       while ( !outOfMemory ) {
1584           char *buf = GetWriteBuf(size);
1585           if ( buf )
1586             iLen = wxVsnprintfA(buf, size, pszFormat, argptr);
1587           else
1588             outOfMemory = TRUE;
1589
1590           UngetWriteBuf();
1591
1592           if ( iLen != -1 ) {
1593               // ok, there was enough space
1594               break;
1595           }
1596
1597           // still not enough, double it again
1598           size *= 2;
1599       }
1600
1601       if ( outOfMemory ) {
1602           // out of memory
1603           return -1;
1604       }
1605   }
1606 #endif // wxUSE_EXPERIMENTAL_PRINTF/!wxUSE_EXPERIMENTAL_PRINTF
1607
1608   return Len();
1609 }
1610
1611 // ----------------------------------------------------------------------------
1612 // misc other operations
1613 // ----------------------------------------------------------------------------
1614
1615 // returns TRUE if the string matches the pattern which may contain '*' and
1616 // '?' metacharacters (as usual, '?' matches any character and '*' any number
1617 // of them)
1618 bool wxString::Matches(const wxChar *pszMask) const
1619 {
1620     // I disable this code as it doesn't seem to be faster (in fact, it seems
1621     // to be much slower) than the old, hand-written code below and using it
1622     // here requires always linking with libregex even if the user code doesn't
1623     // use it
1624 #if 0 // wxUSE_REGEX
1625     // first translate the shell-like mask into a regex
1626     wxString pattern;
1627     pattern.reserve(wxStrlen(pszMask));
1628
1629     pattern += _T('^');
1630     while ( *pszMask )
1631     {
1632         switch ( *pszMask )
1633         {
1634             case _T('?'):
1635                 pattern += _T('.');
1636                 break;
1637
1638             case _T('*'):
1639                 pattern += _T(".*");
1640                 break;
1641
1642             case _T('^'):
1643             case _T('.'):
1644             case _T('$'):
1645             case _T('('):
1646             case _T(')'):
1647             case _T('|'):
1648             case _T('+'):
1649             case _T('\\'):
1650                 // these characters are special in a RE, quote them
1651                 // (however note that we don't quote '[' and ']' to allow
1652                 // using them for Unix shell like matching)
1653                 pattern += _T('\\');
1654                 // fall through
1655
1656             default:
1657                 pattern += *pszMask;
1658         }
1659
1660         pszMask++;
1661     }
1662     pattern += _T('$');
1663
1664     // and now use it
1665     return wxRegEx(pattern, wxRE_NOSUB | wxRE_EXTENDED).Matches(c_str());
1666 #else // !wxUSE_REGEX
1667   // TODO: this is, of course, awfully inefficient...
1668
1669   // the char currently being checked
1670   const wxChar *pszTxt = c_str();
1671
1672   // the last location where '*' matched
1673   const wxChar *pszLastStarInText = NULL;
1674   const wxChar *pszLastStarInMask = NULL;
1675
1676 match:
1677   for ( ; *pszMask != wxT('\0'); pszMask++, pszTxt++ ) {
1678     switch ( *pszMask ) {
1679       case wxT('?'):
1680         if ( *pszTxt == wxT('\0') )
1681           return FALSE;
1682
1683         // pszTxt and pszMask will be incremented in the loop statement
1684
1685         break;
1686
1687       case wxT('*'):
1688         {
1689           // remember where we started to be able to backtrack later
1690           pszLastStarInText = pszTxt;
1691           pszLastStarInMask = pszMask;
1692
1693           // ignore special chars immediately following this one
1694           // (should this be an error?)
1695           while ( *pszMask == wxT('*') || *pszMask == wxT('?') )
1696             pszMask++;
1697
1698           // if there is nothing more, match
1699           if ( *pszMask == wxT('\0') )
1700             return TRUE;
1701
1702           // are there any other metacharacters in the mask?
1703           size_t uiLenMask;
1704           const wxChar *pEndMask = wxStrpbrk(pszMask, wxT("*?"));
1705
1706           if ( pEndMask != NULL ) {
1707             // we have to match the string between two metachars
1708             uiLenMask = pEndMask - pszMask;
1709           }
1710           else {
1711             // we have to match the remainder of the string
1712             uiLenMask = wxStrlen(pszMask);
1713           }
1714
1715           wxString strToMatch(pszMask, uiLenMask);
1716           const wxChar* pMatch = wxStrstr(pszTxt, strToMatch);
1717           if ( pMatch == NULL )
1718             return FALSE;
1719
1720           // -1 to compensate "++" in the loop
1721           pszTxt = pMatch + uiLenMask - 1;
1722           pszMask += uiLenMask - 1;
1723         }
1724         break;
1725
1726       default:
1727         if ( *pszMask != *pszTxt )
1728           return FALSE;
1729         break;
1730     }
1731   }
1732
1733   // match only if nothing left
1734   if ( *pszTxt == wxT('\0') )
1735     return TRUE;
1736
1737   // if we failed to match, backtrack if we can
1738   if ( pszLastStarInText ) {
1739     pszTxt = pszLastStarInText + 1;
1740     pszMask = pszLastStarInMask;
1741
1742     pszLastStarInText = NULL;
1743
1744     // don't bother resetting pszLastStarInMask, it's unnecessary
1745
1746     goto match;
1747   }
1748
1749   return FALSE;
1750 #endif // wxUSE_REGEX/!wxUSE_REGEX
1751 }
1752
1753 // Count the number of chars
1754 int wxString::Freq(wxChar ch) const
1755 {
1756     int count = 0;
1757     int len = Len();
1758     for (int i = 0; i < len; i++)
1759     {
1760         if (GetChar(i) == ch)
1761             count ++;
1762     }
1763     return count;
1764 }
1765
1766 // convert to upper case, return the copy of the string
1767 wxString wxString::Upper() const
1768 { wxString s(*this); return s.MakeUpper(); }
1769
1770 // convert to lower case, return the copy of the string
1771 wxString wxString::Lower() const { wxString s(*this); return s.MakeLower(); }
1772
1773 int wxString::sprintf(const wxChar *pszFormat, ...)
1774   {
1775     va_list argptr;
1776     va_start(argptr, pszFormat);
1777     int iLen = PrintfV(pszFormat, argptr);
1778     va_end(argptr);
1779     return iLen;
1780   }
1781
1782 // ---------------------------------------------------------------------------
1783 // standard C++ library string functions
1784 // ---------------------------------------------------------------------------
1785
1786 #ifdef  wxSTD_STRING_COMPATIBILITY
1787
1788 void wxString::resize(size_t nSize, wxChar ch)
1789 {
1790     size_t len = length();
1791
1792     if ( nSize < len )
1793     {
1794         Truncate(nSize);
1795     }
1796     else if ( nSize > len )
1797     {
1798         *this += wxString(ch, nSize - len);
1799     }
1800     //else: we have exactly the specified length, nothing to do
1801 }
1802
1803 void wxString::swap(wxString& str)
1804 {
1805     // this is slightly less efficient than fiddling with m_pchData directly,
1806     // but it is still quite efficient as we don't copy the string here because
1807     // ref count always stays positive
1808     wxString tmp = str;
1809     str = *this;
1810     *this = tmp;
1811 }
1812
1813 wxString& wxString::insert(size_t nPos, const wxString& str)
1814 {
1815   wxASSERT( str.GetStringData()->IsValid() );
1816   wxASSERT( nPos <= Len() );
1817
1818   if ( !str.IsEmpty() ) {
1819     wxString strTmp;
1820     wxChar *pc = strTmp.GetWriteBuf(Len() + str.Len());
1821     wxStrncpy(pc, c_str(), nPos);
1822     wxStrcpy(pc + nPos, str);
1823     wxStrcpy(pc + nPos + str.Len(), c_str() + nPos);
1824     strTmp.UngetWriteBuf();
1825     *this = strTmp;
1826   }
1827
1828   return *this;
1829 }
1830
1831 size_t wxString::find(const wxString& str, size_t nStart) const
1832 {
1833   wxASSERT( str.GetStringData()->IsValid() );
1834   wxASSERT( nStart <= Len() );
1835
1836   const wxChar *p = wxStrstr(c_str() + nStart, str);
1837
1838   return p == NULL ? npos : p - c_str();
1839 }
1840
1841 // VC++ 1.5 can't cope with the default argument in the header.
1842 #if !defined(__VISUALC__) || defined(__WIN32__)
1843 size_t wxString::find(const wxChar* sz, size_t nStart, size_t n) const
1844 {
1845   return find(wxString(sz, n), nStart);
1846 }
1847 #endif // VC++ 1.5
1848
1849 // Gives a duplicate symbol (presumably a case-insensitivity problem)
1850 #if !defined(__BORLANDC__)
1851 size_t wxString::find(wxChar ch, size_t nStart) const
1852 {
1853   wxASSERT( nStart <= Len() );
1854
1855   const wxChar *p = wxStrchr(c_str() + nStart, ch);
1856
1857   return p == NULL ? npos : p - c_str();
1858 }
1859 #endif
1860
1861 size_t wxString::rfind(const wxString& str, size_t nStart) const
1862 {
1863   wxASSERT( str.GetStringData()->IsValid() );
1864   wxASSERT( nStart == npos || nStart <= Len() );
1865
1866   // TODO could be made much quicker than that
1867   const wxChar *p = c_str() + (nStart == npos ? Len() : nStart);
1868   while ( p >= c_str() + str.Len() ) {
1869     if ( wxStrncmp(p - str.Len(), str, str.Len()) == 0 )
1870       return p - str.Len() - c_str();
1871     p--;
1872   }
1873
1874   return npos;
1875 }
1876
1877 // VC++ 1.5 can't cope with the default argument in the header.
1878 #if !defined(__VISUALC__) || defined(__WIN32__)
1879 size_t wxString::rfind(const wxChar* sz, size_t nStart, size_t n) const
1880 {
1881     return rfind(wxString(sz, n == npos ? wxSTRING_MAXLEN : n), nStart);
1882 }
1883
1884 size_t wxString::rfind(wxChar ch, size_t nStart) const
1885 {
1886     if ( nStart == npos )
1887     {
1888         nStart = Len();
1889     }
1890     else
1891     {
1892         wxASSERT( nStart <= Len() );
1893     }
1894
1895     const wxChar *p = wxStrrchr(c_str(), ch);
1896
1897     if ( p == NULL )
1898         return npos;
1899
1900     size_t result = p - c_str();
1901     return ( result > nStart ) ? npos : result;
1902 }
1903 #endif // VC++ 1.5
1904
1905 size_t wxString::find_first_of(const wxChar* sz, size_t nStart) const
1906 {
1907     const wxChar *start = c_str() + nStart;
1908     const wxChar *firstOf = wxStrpbrk(start, sz);
1909     if ( firstOf )
1910         return firstOf - c_str();
1911     else
1912         return npos;
1913 }
1914
1915 size_t wxString::find_last_of(const wxChar* sz, size_t nStart) const
1916 {
1917     if ( nStart == npos )
1918     {
1919         nStart = Len();
1920     }
1921     else
1922     {
1923         wxASSERT( nStart <= Len() );
1924     }
1925
1926     for ( const wxChar *p = c_str() + length() - 1; p >= c_str(); p-- )
1927     {
1928         if ( wxStrchr(sz, *p) )
1929             return p - c_str();
1930     }
1931
1932     return npos;
1933 }
1934
1935 size_t wxString::find_first_not_of(const wxChar* sz, size_t nStart) const
1936 {
1937     if ( nStart == npos )
1938     {
1939         nStart = Len();
1940     }
1941     else
1942     {
1943         wxASSERT( nStart <= Len() );
1944     }
1945
1946     size_t nAccept = wxStrspn(c_str() + nStart, sz);
1947     if ( nAccept >= length() - nStart )
1948         return npos;
1949     else
1950         return nAccept;
1951 }
1952
1953 size_t wxString::find_first_not_of(wxChar ch, size_t nStart) const
1954 {
1955     wxASSERT( nStart <= Len() );
1956
1957     for ( const wxChar *p = c_str() + nStart; *p; p++ )
1958     {
1959         if ( *p != ch )
1960             return p - c_str();
1961     }
1962
1963     return npos;
1964 }
1965
1966 size_t wxString::find_last_not_of(const wxChar* sz, size_t nStart) const
1967 {
1968     if ( nStart == npos )
1969     {
1970         nStart = Len();
1971     }
1972     else
1973     {
1974         wxASSERT( nStart <= Len() );
1975     }
1976
1977     for ( const wxChar *p = c_str() + nStart - 1; p >= c_str(); p-- )
1978     {
1979         if ( !wxStrchr(sz, *p) )
1980             return p - c_str();
1981     }
1982
1983     return npos;
1984 }
1985
1986 size_t wxString::find_last_not_of(wxChar ch, size_t nStart) const
1987 {
1988     if ( nStart == npos )
1989     {
1990         nStart = Len();
1991     }
1992     else
1993     {
1994         wxASSERT( nStart <= Len() );
1995     }
1996
1997     for ( const wxChar *p = c_str() + nStart - 1; p >= c_str(); p-- )
1998     {
1999         if ( *p != ch )
2000             return p - c_str();
2001     }
2002
2003     return npos;
2004 }
2005
2006 wxString& wxString::erase(size_t nStart, size_t nLen)
2007 {
2008   wxString strTmp(c_str(), nStart);
2009   if ( nLen != npos ) {
2010     wxASSERT( nStart + nLen <= Len() );
2011
2012     strTmp.append(c_str() + nStart + nLen);
2013   }
2014
2015   *this = strTmp;
2016   return *this;
2017 }
2018
2019 wxString& wxString::replace(size_t nStart, size_t nLen, const wxChar *sz)
2020 {
2021   wxASSERT_MSG( nStart + nLen <= Len(),
2022                 _T("index out of bounds in wxString::replace") );
2023
2024   wxString strTmp;
2025   strTmp.Alloc(Len());      // micro optimisation to avoid multiple mem allocs
2026
2027   if ( nStart != 0 )
2028     strTmp.append(c_str(), nStart);
2029   strTmp << sz << c_str() + nStart + nLen;
2030
2031   *this = strTmp;
2032   return *this;
2033 }
2034
2035 wxString& wxString::replace(size_t nStart, size_t nLen, size_t nCount, wxChar ch)
2036 {
2037   return replace(nStart, nLen, wxString(ch, nCount));
2038 }
2039
2040 wxString& wxString::replace(size_t nStart, size_t nLen,
2041                             const wxString& str, size_t nStart2, size_t nLen2)
2042 {
2043   return replace(nStart, nLen, str.substr(nStart2, nLen2));
2044 }
2045
2046 wxString& wxString::replace(size_t nStart, size_t nLen,
2047                         const wxChar* sz, size_t nCount)
2048 {
2049   return replace(nStart, nLen, wxString(sz, nCount));
2050 }
2051
2052 #endif  //std::string compatibility
2053
2054 // ============================================================================
2055 // ArrayString
2056 // ============================================================================
2057
2058 // size increment = min(50% of current size, ARRAY_MAXSIZE_INCREMENT)
2059 #define   ARRAY_MAXSIZE_INCREMENT       4096
2060
2061 #ifndef   ARRAY_DEFAULT_INITIAL_SIZE    // also defined in dynarray.h
2062 #define   ARRAY_DEFAULT_INITIAL_SIZE    (16)
2063 #endif
2064
2065 #define   STRING(p)   ((wxString *)(&(p)))
2066
2067 // ctor
2068 void wxArrayString::Init(bool autoSort)
2069 {
2070   m_nSize  =
2071   m_nCount = 0;
2072   m_pItems = (wxChar **) NULL;
2073   m_autoSort = autoSort;
2074 }
2075
2076 // copy ctor
2077 wxArrayString::wxArrayString(const wxArrayString& src)
2078 {
2079   Init(src.m_autoSort);
2080
2081   *this = src;
2082 }
2083
2084 // assignment operator
2085 wxArrayString& wxArrayString::operator=(const wxArrayString& src)
2086 {
2087   if ( m_nSize > 0 )
2088     Clear();
2089
2090   Copy(src);
2091
2092   m_autoSort = src.m_autoSort;
2093
2094   return *this;
2095 }
2096
2097 void wxArrayString::Copy(const wxArrayString& src)
2098 {
2099   if ( src.m_nCount > ARRAY_DEFAULT_INITIAL_SIZE )
2100     Alloc(src.m_nCount);
2101
2102   for ( size_t n = 0; n < src.m_nCount; n++ )
2103     Add(src[n]);
2104 }
2105
2106 // grow the array
2107 void wxArrayString::Grow(size_t nIncrement)
2108 {
2109   // only do it if no more place
2110   if ( m_nCount == m_nSize ) {
2111     // if ARRAY_DEFAULT_INITIAL_SIZE were set to 0, the initially empty would
2112     // be never resized!
2113     #if ARRAY_DEFAULT_INITIAL_SIZE == 0
2114       #error "ARRAY_DEFAULT_INITIAL_SIZE must be > 0!"
2115     #endif
2116
2117     if ( m_nSize == 0 ) {
2118       // was empty, alloc some memory
2119       m_nSize = ARRAY_DEFAULT_INITIAL_SIZE;
2120       m_pItems = new wxChar *[m_nSize];
2121     }
2122     else {
2123       // otherwise when it's called for the first time, nIncrement would be 0
2124       // and the array would never be expanded
2125       // add 50% but not too much
2126       size_t ndefIncrement = m_nSize < ARRAY_DEFAULT_INITIAL_SIZE
2127                           ? ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1;
2128       if ( ndefIncrement > ARRAY_MAXSIZE_INCREMENT )
2129         ndefIncrement = ARRAY_MAXSIZE_INCREMENT;
2130       if ( nIncrement < ndefIncrement )
2131         nIncrement = ndefIncrement;
2132       m_nSize += nIncrement;
2133       wxChar **pNew = new wxChar *[m_nSize];
2134
2135       // copy data to new location
2136       memcpy(pNew, m_pItems, m_nCount*sizeof(wxChar *));
2137
2138       // delete old memory (but do not release the strings!)
2139       wxDELETEA(m_pItems);
2140
2141       m_pItems = pNew;
2142     }
2143   }
2144 }
2145
2146 void wxArrayString::Free()
2147 {
2148   for ( size_t n = 0; n < m_nCount; n++ ) {
2149     STRING(m_pItems[n])->GetStringData()->Unlock();
2150   }
2151 }
2152
2153 // deletes all the strings from the list
2154 void wxArrayString::Empty()
2155 {
2156   Free();
2157
2158   m_nCount = 0;
2159 }
2160
2161 // as Empty, but also frees memory
2162 void wxArrayString::Clear()
2163 {
2164   Free();
2165
2166   m_nSize  =
2167   m_nCount = 0;
2168
2169   wxDELETEA(m_pItems);
2170 }
2171
2172 // dtor
2173 wxArrayString::~wxArrayString()
2174 {
2175   Free();
2176
2177   wxDELETEA(m_pItems);
2178 }
2179
2180 // pre-allocates memory (frees the previous data!)
2181 void wxArrayString::Alloc(size_t nSize)
2182 {
2183   // only if old buffer was not big enough
2184   if ( nSize > m_nSize ) {
2185     Free();
2186     wxDELETEA(m_pItems);
2187     m_pItems = new wxChar *[nSize];
2188     m_nSize  = nSize;
2189   }
2190
2191   m_nCount = 0;
2192 }
2193
2194 // minimizes the memory usage by freeing unused memory
2195 void wxArrayString::Shrink()
2196 {
2197   // only do it if we have some memory to free
2198   if( m_nCount < m_nSize ) {
2199     // allocates exactly as much memory as we need
2200     wxChar **pNew = new wxChar *[m_nCount];
2201
2202     // copy data to new location
2203     memcpy(pNew, m_pItems, m_nCount*sizeof(wxChar *));
2204     delete [] m_pItems;
2205     m_pItems = pNew;
2206   }
2207 }
2208
2209 // return a wxString[] as required for some control ctors.
2210 wxString* wxArrayString::GetStringArray() const
2211 {
2212     wxString *array = 0;
2213
2214     if( m_nCount > 0 )
2215     {
2216         array = new wxString[m_nCount];
2217         for( size_t i = 0; i < m_nCount; i++ )
2218             array[i] = m_pItems[i];
2219     }
2220
2221     return array;
2222 }
2223
2224 // searches the array for an item (forward or backwards)
2225 int wxArrayString::Index(const wxChar *sz, bool bCase, bool bFromEnd) const
2226 {
2227   if ( m_autoSort ) {
2228     // use binary search in the sorted array
2229     wxASSERT_MSG( bCase && !bFromEnd,
2230                   wxT("search parameters ignored for auto sorted array") );
2231
2232     size_t i,
2233            lo = 0,
2234            hi = m_nCount;
2235     int res;
2236     while ( lo < hi ) {
2237       i = (lo + hi)/2;
2238
2239       res = wxStrcmp(sz, m_pItems[i]);
2240       if ( res < 0 )
2241         hi = i;
2242       else if ( res > 0 )
2243         lo = i + 1;
2244       else
2245         return i;
2246     }
2247
2248     return wxNOT_FOUND;
2249   }
2250   else {
2251     // use linear search in unsorted array
2252     if ( bFromEnd ) {
2253       if ( m_nCount > 0 ) {
2254         size_t ui = m_nCount;
2255         do {
2256           if ( STRING(m_pItems[--ui])->IsSameAs(sz, bCase) )
2257             return ui;
2258         }
2259         while ( ui != 0 );
2260       }
2261     }
2262     else {
2263       for( size_t ui = 0; ui < m_nCount; ui++ ) {
2264         if( STRING(m_pItems[ui])->IsSameAs(sz, bCase) )
2265           return ui;
2266       }
2267     }
2268   }
2269
2270   return wxNOT_FOUND;
2271 }
2272
2273 // add item at the end
2274 size_t wxArrayString::Add(const wxString& str, size_t nInsert)
2275 {
2276   if ( m_autoSort ) {
2277     // insert the string at the correct position to keep the array sorted
2278     size_t i,
2279            lo = 0,
2280            hi = m_nCount;
2281     int res;
2282     while ( lo < hi ) {
2283       i = (lo + hi)/2;
2284
2285       res = wxStrcmp(str, m_pItems[i]);
2286       if ( res < 0 )
2287         hi = i;
2288       else if ( res > 0 )
2289         lo = i + 1;
2290       else {
2291         lo = hi = i;
2292         break;
2293       }
2294     }
2295
2296     wxASSERT_MSG( lo == hi, wxT("binary search broken") );
2297
2298     Insert(str, lo, nInsert);
2299
2300     return (size_t)lo;
2301   }
2302   else {
2303     wxASSERT( str.GetStringData()->IsValid() );
2304
2305     Grow(nInsert);
2306
2307     for (size_t i = 0; i < nInsert; i++)
2308     {
2309         // the string data must not be deleted!
2310         str.GetStringData()->Lock();
2311
2312         // just append
2313         m_pItems[m_nCount + i] = (wxChar *)str.c_str(); // const_cast
2314     }
2315     size_t ret = m_nCount;
2316     m_nCount += nInsert;
2317     return ret;
2318   }
2319 }
2320
2321 // add item at the given position
2322 void wxArrayString::Insert(const wxString& str, size_t nIndex, size_t nInsert)
2323 {
2324   wxASSERT( str.GetStringData()->IsValid() );
2325
2326   wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArrayString::Insert") );
2327   wxCHECK_RET( m_nCount <= m_nCount + nInsert,
2328                wxT("array size overflow in wxArrayString::Insert") );
2329
2330   Grow(nInsert);
2331
2332   memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex],
2333           (m_nCount - nIndex)*sizeof(wxChar *));
2334
2335   for (size_t i = 0; i < nInsert; i++)
2336   {
2337       str.GetStringData()->Lock();
2338       m_pItems[nIndex + i] = (wxChar *)str.c_str();
2339   }
2340   m_nCount += nInsert;
2341 }
2342
2343 // expand the array
2344 void wxArrayString::SetCount(size_t count)
2345 {
2346     Alloc(count);
2347
2348     wxString s;
2349     while ( m_nCount < count )
2350         m_pItems[m_nCount++] = (wxChar *)s.c_str();
2351 }
2352
2353 // removes item from array (by index)
2354 void wxArrayString::Remove(size_t nIndex, size_t nRemove)
2355 {
2356   wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArrayString::Remove") );
2357   wxCHECK_RET( nIndex + nRemove <= m_nCount,
2358                wxT("removing too many elements in wxArrayString::Remove") );
2359
2360   // release our lock
2361   for (size_t i = 0; i < nRemove; i++)
2362       Item(nIndex + i).GetStringData()->Unlock();
2363
2364   memmove(&m_pItems[nIndex], &m_pItems[nIndex + nRemove],
2365           (m_nCount - nIndex - nRemove)*sizeof(wxChar *));
2366   m_nCount -= nRemove;
2367 }
2368
2369 // removes item from array (by value)
2370 void wxArrayString::Remove(const wxChar *sz)
2371 {
2372   int iIndex = Index(sz);
2373
2374   wxCHECK_RET( iIndex != wxNOT_FOUND,
2375                wxT("removing inexistent element in wxArrayString::Remove") );
2376
2377   Remove(iIndex);
2378 }
2379
2380 // ----------------------------------------------------------------------------
2381 // sorting
2382 // ----------------------------------------------------------------------------
2383
2384 // we can only sort one array at a time with the quick-sort based
2385 // implementation
2386 #if wxUSE_THREADS
2387   // need a critical section to protect access to gs_compareFunction and
2388   // gs_sortAscending variables
2389   static wxCriticalSection *gs_critsectStringSort = NULL;
2390
2391   // call this before the value of the global sort vars is changed/after
2392   // you're finished with them
2393   #define START_SORT()     wxASSERT( !gs_critsectStringSort );                \
2394                            gs_critsectStringSort = new wxCriticalSection;     \
2395                            gs_critsectStringSort->Enter()
2396   #define END_SORT()       gs_critsectStringSort->Leave();                    \
2397                            delete gs_critsectStringSort;                      \
2398                            gs_critsectStringSort = NULL
2399 #else // !threads
2400   #define START_SORT()
2401   #define END_SORT()
2402 #endif // wxUSE_THREADS
2403
2404 // function to use for string comparaison
2405 static wxArrayString::CompareFunction gs_compareFunction = NULL;
2406
2407 // if we don't use the compare function, this flag tells us if we sort the
2408 // array in ascending or descending order
2409 static bool gs_sortAscending = TRUE;
2410
2411 // function which is called by quick sort
2412 extern "C" int LINKAGEMODE
2413 wxStringCompareFunction(const void *first, const void *second)
2414 {
2415   wxString *strFirst = (wxString *)first;
2416   wxString *strSecond = (wxString *)second;
2417
2418   if ( gs_compareFunction ) {
2419     return gs_compareFunction(*strFirst, *strSecond);
2420   }
2421   else {
2422     // maybe we should use wxStrcoll
2423     int result = wxStrcmp(strFirst->c_str(), strSecond->c_str());
2424
2425     return gs_sortAscending ? result : -result;
2426   }
2427 }
2428
2429 // sort array elements using passed comparaison function
2430 void wxArrayString::Sort(CompareFunction compareFunction)
2431 {
2432   START_SORT();
2433
2434   wxASSERT( !gs_compareFunction );  // must have been reset to NULL
2435   gs_compareFunction = compareFunction;
2436
2437   DoSort();
2438
2439   // reset it to NULL so that Sort(bool) will work the next time
2440   gs_compareFunction = NULL;
2441
2442   END_SORT();
2443 }
2444
2445 void wxArrayString::Sort(bool reverseOrder)
2446 {
2447   START_SORT();
2448
2449   wxASSERT( !gs_compareFunction );  // must have been reset to NULL
2450   gs_sortAscending = !reverseOrder;
2451
2452   DoSort();
2453
2454   END_SORT();
2455 }
2456
2457 void wxArrayString::DoSort()
2458 {
2459   wxCHECK_RET( !m_autoSort, wxT("can't use this method with sorted arrays") );
2460
2461   // just sort the pointers using qsort() - of course it only works because
2462   // wxString() *is* a pointer to its data
2463   qsort(m_pItems, m_nCount, sizeof(wxChar *), wxStringCompareFunction);
2464 }
2465
2466 bool wxArrayString::operator==(const wxArrayString& a) const
2467 {
2468     if ( m_nCount != a.m_nCount )
2469         return FALSE;
2470
2471     for ( size_t n = 0; n < m_nCount; n++ )
2472     {
2473         if ( Item(n) != a[n] )
2474             return FALSE;
2475     }
2476
2477     return TRUE;
2478 }
2479