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