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