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 bool wxString::IsAscii() const
1017 {
1018   const wxChar *s = (const wxChar*) *this;
1019   while(*s){
1020     if(!isascii(*s)) return(FALSE);
1021     s++;
1022   }
1023   return(TRUE);
1024 }
1025
1026 bool wxString::IsWord() const
1027 {
1028   const wxChar *s = (const wxChar*) *this;
1029   while(*s){
1030     if(!wxIsalpha(*s)) return(FALSE);
1031     s++;
1032   }
1033   return(TRUE);
1034 }
1035
1036 bool wxString::IsNumber() const
1037 {
1038   const wxChar *s = (const wxChar*) *this;
1039   if (wxStrlen(s))
1040      if ((s[0] == '-') || (s[0] == '+')) s++;
1041   while(*s){
1042     if(!wxIsdigit(*s)) return(FALSE);
1043     s++;
1044   }
1045   return(TRUE);
1046 }
1047
1048 wxString wxString::Strip(stripType w) const
1049 {
1050     wxString s = *this;
1051     if ( w & leading ) s.Trim(FALSE);
1052     if ( w & trailing ) s.Trim(TRUE);
1053     return s;
1054 }
1055
1056 // ---------------------------------------------------------------------------
1057 // case conversion
1058 // ---------------------------------------------------------------------------
1059
1060 wxString& wxString::MakeUpper()
1061 {
1062   if ( !CopyBeforeWrite() ) {
1063     wxFAIL_MSG( _T("out of memory in wxString::MakeUpper") );
1064     return *this;
1065   }
1066
1067   for ( wxChar *p = m_pchData; *p; p++ )
1068     *p = (wxChar)wxToupper(*p);
1069
1070   return *this;
1071 }
1072
1073 wxString& wxString::MakeLower()
1074 {
1075   if ( !CopyBeforeWrite() ) {
1076     wxFAIL_MSG( _T("out of memory in wxString::MakeLower") );
1077     return *this;
1078   }
1079
1080   for ( wxChar *p = m_pchData; *p; p++ )
1081     *p = (wxChar)wxTolower(*p);
1082
1083   return *this;
1084 }
1085
1086 // ---------------------------------------------------------------------------
1087 // trimming and padding
1088 // ---------------------------------------------------------------------------
1089
1090 // some compilers (VC++ 6.0 not to name them) return TRUE for a call to
1091 // isspace('ê') in the C locale which seems to be broken to me, but we have to
1092 // live with this by checking that the character is a 7 bit one - even if this
1093 // may fail to detect some spaces (I don't know if Unicode doesn't have
1094 // space-like symbols somewhere except in the first 128 chars), it is arguably
1095 // still better than trimming away accented letters
1096 inline int wxSafeIsspace(wxChar ch) { return (ch < 127) && wxIsspace(ch); }
1097
1098 // trims spaces (in the sense of isspace) from left or right side
1099 wxString& wxString::Trim(bool bFromRight)
1100 {
1101   // first check if we're going to modify the string at all
1102   if ( !IsEmpty() &&
1103        (
1104         (bFromRight && wxSafeIsspace(GetChar(Len() - 1))) ||
1105         (!bFromRight && wxSafeIsspace(GetChar(0u)))
1106        )
1107      )
1108   {
1109     // ok, there is at least one space to trim
1110     if ( !CopyBeforeWrite() ) {
1111       wxFAIL_MSG( _T("out of memory in wxString::Trim") );
1112       return *this;
1113     }
1114
1115     if ( bFromRight )
1116     {
1117       // find last non-space character
1118       wxChar *psz = m_pchData + GetStringData()->nDataLength - 1;
1119       while ( wxSafeIsspace(*psz) && (psz >= m_pchData) )
1120         psz--;
1121
1122       // truncate at trailing space start
1123       *++psz = wxT('\0');
1124       GetStringData()->nDataLength = psz - m_pchData;
1125     }
1126     else
1127     {
1128       // find first non-space character
1129       const wxChar *psz = m_pchData;
1130       while ( wxSafeIsspace(*psz) )
1131         psz++;
1132
1133       // fix up data and length
1134       int nDataLength = GetStringData()->nDataLength - (psz - (const wxChar*) m_pchData);
1135       memmove(m_pchData, psz, (nDataLength + 1)*sizeof(wxChar));
1136       GetStringData()->nDataLength = nDataLength;
1137     }
1138   }
1139
1140   return *this;
1141 }
1142
1143 // adds nCount characters chPad to the string from either side
1144 wxString& wxString::Pad(size_t nCount, wxChar chPad, bool bFromRight)
1145 {
1146   wxString s(chPad, nCount);
1147
1148   if ( bFromRight )
1149     *this += s;
1150   else
1151   {
1152     s += *this;
1153     *this = s;
1154   }
1155
1156   return *this;
1157 }
1158
1159 // truncate the string
1160 wxString& wxString::Truncate(size_t uiLen)
1161 {
1162   if ( uiLen < Len() ) {
1163     if ( !CopyBeforeWrite() ) {
1164       wxFAIL_MSG( _T("out of memory in wxString::Truncate") );
1165       return *this;
1166     }
1167
1168     *(m_pchData + uiLen) = wxT('\0');
1169     GetStringData()->nDataLength = uiLen;
1170   }
1171   //else: nothing to do, string is already short enough
1172
1173   return *this;
1174 }
1175
1176 // ---------------------------------------------------------------------------
1177 // finding (return wxNOT_FOUND if not found and index otherwise)
1178 // ---------------------------------------------------------------------------
1179
1180 // find a character
1181 int wxString::Find(wxChar ch, bool bFromEnd) const
1182 {
1183   const wxChar *psz = bFromEnd ? wxStrrchr(m_pchData, ch) : wxStrchr(m_pchData, ch);
1184
1185   return (psz == NULL) ? wxNOT_FOUND : psz - (const wxChar*) m_pchData;
1186 }
1187
1188 // find a sub-string (like strstr)
1189 int wxString::Find(const wxChar *pszSub) const
1190 {
1191   const wxChar *psz = wxStrstr(m_pchData, pszSub);
1192
1193   return (psz == NULL) ? wxNOT_FOUND : psz - (const wxChar*) m_pchData;
1194 }
1195
1196 // ----------------------------------------------------------------------------
1197 // conversion to numbers
1198 // ----------------------------------------------------------------------------
1199
1200 bool wxString::ToLong(long *val, int base) const
1201 {
1202     wxCHECK_MSG( val, FALSE, _T("NULL pointer in wxString::ToLong") );
1203     wxASSERT_MSG( !base || (base > 1 && base <= 36), _T("invalid base") );
1204
1205     const wxChar *start = c_str();
1206     wxChar *end;
1207     *val = wxStrtol(start, &end, base);
1208
1209     // return TRUE only if scan was stopped by the terminating NUL and if the
1210     // string was not empty to start with
1211     return !*end && (end != start);
1212 }
1213
1214 bool wxString::ToULong(unsigned long *val, int base) const
1215 {
1216     wxCHECK_MSG( val, FALSE, _T("NULL pointer in wxString::ToULong") );
1217     wxASSERT_MSG( !base || (base > 1 && base <= 36), _T("invalid base") );
1218
1219     const wxChar *start = c_str();
1220     wxChar *end;
1221     *val = wxStrtoul(start, &end, base);
1222
1223     // return TRUE only if scan was stopped by the terminating NUL and if the
1224     // string was not empty to start with
1225     return !*end && (end != start);
1226 }
1227
1228 bool wxString::ToDouble(double *val) const
1229 {
1230     wxCHECK_MSG( val, FALSE, _T("NULL pointer in wxString::ToDouble") );
1231
1232     const wxChar *start = c_str();
1233     wxChar *end;
1234     *val = wxStrtod(start, &end);
1235
1236     // return TRUE only if scan was stopped by the terminating NUL and if the
1237     // string was not empty to start with
1238     return !*end && (end != start);
1239 }
1240
1241 // ---------------------------------------------------------------------------
1242 // formatted output
1243 // ---------------------------------------------------------------------------
1244
1245 /* static */
1246 wxString wxString::Format(const wxChar *pszFormat, ...)
1247 {
1248     va_list argptr;
1249     va_start(argptr, pszFormat);
1250
1251     wxString s;
1252     s.PrintfV(pszFormat, argptr);
1253
1254     va_end(argptr);
1255
1256     return s;
1257 }
1258
1259 /* static */
1260 wxString wxString::FormatV(const wxChar *pszFormat, va_list argptr)
1261 {
1262     wxString s;
1263     s.PrintfV(pszFormat, argptr);
1264     return s;
1265 }
1266
1267 int wxString::Printf(const wxChar *pszFormat, ...)
1268 {
1269   va_list argptr;
1270   va_start(argptr, pszFormat);
1271
1272   int iLen = PrintfV(pszFormat, argptr);
1273
1274   va_end(argptr);
1275
1276   return iLen;
1277 }
1278
1279 int wxString::PrintfV(const wxChar* pszFormat, va_list argptr)
1280 {
1281     int size = 1024;
1282     for ( ;; )
1283     {
1284         wxChar *buf = GetWriteBuf(size + 1);
1285         if ( !buf )
1286         {
1287             // out of memory
1288             return -1;
1289         }
1290
1291         int len = wxVsnprintf(buf, size, pszFormat, argptr);
1292
1293         // some implementations of vsnprintf() don't NUL terminate the string
1294         // if there is not enough space for it so always do it manually
1295         buf[size] = _T('\0');
1296
1297         UngetWriteBuf();
1298
1299         if ( len >= 0 )
1300         {
1301             // ok, there was enough space
1302             break;
1303         }
1304
1305         // still not enough, double it again
1306         size *= 2;
1307     }
1308
1309     // we could have overshot
1310     Shrink();
1311
1312     return Len();
1313 }
1314
1315 // ----------------------------------------------------------------------------
1316 // misc other operations
1317 // ----------------------------------------------------------------------------
1318
1319 // returns TRUE if the string matches the pattern which may contain '*' and
1320 // '?' metacharacters (as usual, '?' matches any character and '*' any number
1321 // of them)
1322 bool wxString::Matches(const wxChar *pszMask) const
1323 {
1324     // I disable this code as it doesn't seem to be faster (in fact, it seems
1325     // to be much slower) than the old, hand-written code below and using it
1326     // here requires always linking with libregex even if the user code doesn't
1327     // use it
1328 #if 0 // wxUSE_REGEX
1329     // first translate the shell-like mask into a regex
1330     wxString pattern;
1331     pattern.reserve(wxStrlen(pszMask));
1332
1333     pattern += _T('^');
1334     while ( *pszMask )
1335     {
1336         switch ( *pszMask )
1337         {
1338             case _T('?'):
1339                 pattern += _T('.');
1340                 break;
1341
1342             case _T('*'):
1343                 pattern += _T(".*");
1344                 break;
1345
1346             case _T('^'):
1347             case _T('.'):
1348             case _T('$'):
1349             case _T('('):
1350             case _T(')'):
1351             case _T('|'):
1352             case _T('+'):
1353             case _T('\\'):
1354                 // these characters are special in a RE, quote them
1355                 // (however note that we don't quote '[' and ']' to allow
1356                 // using them for Unix shell like matching)
1357                 pattern += _T('\\');
1358                 // fall through
1359
1360             default:
1361                 pattern += *pszMask;
1362         }
1363
1364         pszMask++;
1365     }
1366     pattern += _T('$');
1367
1368     // and now use it
1369     return wxRegEx(pattern, wxRE_NOSUB | wxRE_EXTENDED).Matches(c_str());
1370 #else // !wxUSE_REGEX
1371   // TODO: this is, of course, awfully inefficient...
1372
1373   // the char currently being checked
1374   const wxChar *pszTxt = c_str();
1375
1376   // the last location where '*' matched
1377   const wxChar *pszLastStarInText = NULL;
1378   const wxChar *pszLastStarInMask = NULL;
1379
1380 match:
1381   for ( ; *pszMask != wxT('\0'); pszMask++, pszTxt++ ) {
1382     switch ( *pszMask ) {
1383       case wxT('?'):
1384         if ( *pszTxt == wxT('\0') )
1385           return FALSE;
1386
1387         // pszTxt and pszMask will be incremented in the loop statement
1388
1389         break;
1390
1391       case wxT('*'):
1392         {
1393           // remember where we started to be able to backtrack later
1394           pszLastStarInText = pszTxt;
1395           pszLastStarInMask = pszMask;
1396
1397           // ignore special chars immediately following this one
1398           // (should this be an error?)
1399           while ( *pszMask == wxT('*') || *pszMask == wxT('?') )
1400             pszMask++;
1401
1402           // if there is nothing more, match
1403           if ( *pszMask == wxT('\0') )
1404             return TRUE;
1405
1406           // are there any other metacharacters in the mask?
1407           size_t uiLenMask;
1408           const wxChar *pEndMask = wxStrpbrk(pszMask, wxT("*?"));
1409
1410           if ( pEndMask != NULL ) {
1411             // we have to match the string between two metachars
1412             uiLenMask = pEndMask - pszMask;
1413           }
1414           else {
1415             // we have to match the remainder of the string
1416             uiLenMask = wxStrlen(pszMask);
1417           }
1418
1419           wxString strToMatch(pszMask, uiLenMask);
1420           const wxChar* pMatch = wxStrstr(pszTxt, strToMatch);
1421           if ( pMatch == NULL )
1422             return FALSE;
1423
1424           // -1 to compensate "++" in the loop
1425           pszTxt = pMatch + uiLenMask - 1;
1426           pszMask += uiLenMask - 1;
1427         }
1428         break;
1429
1430       default:
1431         if ( *pszMask != *pszTxt )
1432           return FALSE;
1433         break;
1434     }
1435   }
1436
1437   // match only if nothing left
1438   if ( *pszTxt == wxT('\0') )
1439     return TRUE;
1440
1441   // if we failed to match, backtrack if we can
1442   if ( pszLastStarInText ) {
1443     pszTxt = pszLastStarInText + 1;
1444     pszMask = pszLastStarInMask;
1445
1446     pszLastStarInText = NULL;
1447
1448     // don't bother resetting pszLastStarInMask, it's unnecessary
1449
1450     goto match;
1451   }
1452
1453   return FALSE;
1454 #endif // wxUSE_REGEX/!wxUSE_REGEX
1455 }
1456
1457 // Count the number of chars
1458 int wxString::Freq(wxChar ch) const
1459 {
1460     int count = 0;
1461     int len = Len();
1462     for (int i = 0; i < len; i++)
1463     {
1464         if (GetChar(i) == ch)
1465             count ++;
1466     }
1467     return count;
1468 }
1469
1470 // convert to upper case, return the copy of the string
1471 wxString wxString::Upper() const
1472 { wxString s(*this); return s.MakeUpper(); }
1473
1474 // convert to lower case, return the copy of the string
1475 wxString wxString::Lower() const { wxString s(*this); return s.MakeLower(); }
1476
1477 int wxString::sprintf(const wxChar *pszFormat, ...)
1478   {
1479     va_list argptr;
1480     va_start(argptr, pszFormat);
1481     int iLen = PrintfV(pszFormat, argptr);
1482     va_end(argptr);
1483     return iLen;
1484   }
1485
1486 // ---------------------------------------------------------------------------
1487 // standard C++ library string functions
1488 // ---------------------------------------------------------------------------
1489
1490 #ifdef  wxSTD_STRING_COMPATIBILITY
1491
1492 void wxString::resize(size_t nSize, wxChar ch)
1493 {
1494     size_t len = length();
1495
1496     if ( nSize < len )
1497     {
1498         Truncate(nSize);
1499     }
1500     else if ( nSize > len )
1501     {
1502         *this += wxString(ch, nSize - len);
1503     }
1504     //else: we have exactly the specified length, nothing to do
1505 }
1506
1507 void wxString::swap(wxString& str)
1508 {
1509     // this is slightly less efficient than fiddling with m_pchData directly,
1510     // but it is still quite efficient as we don't copy the string here because
1511     // ref count always stays positive
1512     wxString tmp = str;
1513     str = *this;
1514     *this = tmp;
1515 }
1516
1517 wxString& wxString::insert(size_t nPos, const wxString& str)
1518 {
1519   wxASSERT( str.GetStringData()->IsValid() );
1520   wxASSERT( nPos <= Len() );
1521
1522   if ( !str.IsEmpty() ) {
1523     wxString strTmp;
1524     wxChar *pc = strTmp.GetWriteBuf(Len() + str.Len());
1525     wxStrncpy(pc, c_str(), nPos);
1526     wxStrcpy(pc + nPos, str);
1527     wxStrcpy(pc + nPos + str.Len(), c_str() + nPos);
1528     strTmp.UngetWriteBuf();
1529     *this = strTmp;
1530   }
1531
1532   return *this;
1533 }
1534
1535 size_t wxString::find(const wxString& str, size_t nStart) const
1536 {
1537   wxASSERT( str.GetStringData()->IsValid() );
1538   wxASSERT( nStart <= Len() );
1539
1540   const wxChar *p = wxStrstr(c_str() + nStart, str);
1541
1542   return p == NULL ? npos : p - c_str();
1543 }
1544
1545 // VC++ 1.5 can't cope with the default argument in the header.
1546 #if !defined(__VISUALC__) || defined(__WIN32__)
1547 size_t wxString::find(const wxChar* sz, size_t nStart, size_t n) const
1548 {
1549   return find(wxString(sz, n), nStart);
1550 }
1551 #endif // VC++ 1.5
1552
1553 // Gives a duplicate symbol (presumably a case-insensitivity problem)
1554 #if !defined(__BORLANDC__)
1555 size_t wxString::find(wxChar ch, size_t nStart) const
1556 {
1557   wxASSERT( nStart <= Len() );
1558
1559   const wxChar *p = wxStrchr(c_str() + nStart, ch);
1560
1561   return p == NULL ? npos : p - c_str();
1562 }
1563 #endif
1564
1565 size_t wxString::rfind(const wxString& str, size_t nStart) const
1566 {
1567   wxASSERT( str.GetStringData()->IsValid() );
1568   wxASSERT( nStart == npos || nStart <= Len() );
1569
1570   // TODO could be made much quicker than that
1571   const wxChar *p = c_str() + (nStart == npos ? Len() : nStart);
1572   while ( p >= c_str() + str.Len() ) {
1573     if ( wxStrncmp(p - str.Len(), str, str.Len()) == 0 )
1574       return p - str.Len() - c_str();
1575     p--;
1576   }
1577
1578   return npos;
1579 }
1580
1581 // VC++ 1.5 can't cope with the default argument in the header.
1582 #if !defined(__VISUALC__) || defined(__WIN32__)
1583 size_t wxString::rfind(const wxChar* sz, size_t nStart, size_t n) const
1584 {
1585     return rfind(wxString(sz, n == npos ? wxSTRING_MAXLEN : n), nStart);
1586 }
1587
1588 size_t wxString::rfind(wxChar ch, size_t nStart) const
1589 {
1590     if ( nStart == npos )
1591     {
1592         nStart = Len();
1593     }
1594     else
1595     {
1596         wxASSERT( nStart <= Len() );
1597     }
1598
1599     const wxChar *p = wxStrrchr(c_str(), ch);
1600
1601     if ( p == NULL )
1602         return npos;
1603
1604     size_t result = p - c_str();
1605     return ( result > nStart ) ? npos : result;
1606 }
1607 #endif // VC++ 1.5
1608
1609 size_t wxString::find_first_of(const wxChar* sz, size_t nStart) const
1610 {
1611     const wxChar *start = c_str() + nStart;
1612     const wxChar *firstOf = wxStrpbrk(start, sz);
1613     if ( firstOf )
1614         return firstOf - c_str();
1615     else
1616         return npos;
1617 }
1618
1619 size_t wxString::find_last_of(const wxChar* sz, size_t nStart) const
1620 {
1621     if ( nStart == npos )
1622     {
1623         nStart = Len();
1624     }
1625     else
1626     {
1627         wxASSERT( nStart <= Len() );
1628     }
1629
1630     for ( const wxChar *p = c_str() + length() - 1; p >= c_str(); p-- )
1631     {
1632         if ( wxStrchr(sz, *p) )
1633             return p - c_str();
1634     }
1635
1636     return npos;
1637 }
1638
1639 size_t wxString::find_first_not_of(const wxChar* sz, size_t nStart) const
1640 {
1641     if ( nStart == npos )
1642     {
1643         nStart = Len();
1644     }
1645     else
1646     {
1647         wxASSERT( nStart <= Len() );
1648     }
1649
1650     size_t nAccept = wxStrspn(c_str() + nStart, sz);
1651     if ( nAccept >= length() - nStart )
1652         return npos;
1653     else
1654         return nAccept;
1655 }
1656
1657 size_t wxString::find_first_not_of(wxChar ch, size_t nStart) const
1658 {
1659     wxASSERT( nStart <= Len() );
1660
1661     for ( const wxChar *p = c_str() + nStart; *p; p++ )
1662     {
1663         if ( *p != ch )
1664             return p - c_str();
1665     }
1666
1667     return npos;
1668 }
1669
1670 size_t wxString::find_last_not_of(const wxChar* sz, size_t nStart) const
1671 {
1672     if ( nStart == npos )
1673     {
1674         nStart = Len();
1675     }
1676     else
1677     {
1678         wxASSERT( nStart <= Len() );
1679     }
1680
1681     for ( const wxChar *p = c_str() + nStart - 1; p >= c_str(); p-- )
1682     {
1683         if ( !wxStrchr(sz, *p) )
1684             return p - c_str();
1685     }
1686
1687     return npos;
1688 }
1689
1690 size_t wxString::find_last_not_of(wxChar ch, size_t nStart) const
1691 {
1692     if ( nStart == npos )
1693     {
1694         nStart = Len();
1695     }
1696     else
1697     {
1698         wxASSERT( nStart <= Len() );
1699     }
1700
1701     for ( const wxChar *p = c_str() + nStart - 1; p >= c_str(); p-- )
1702     {
1703         if ( *p != ch )
1704             return p - c_str();
1705     }
1706
1707     return npos;
1708 }
1709
1710 wxString& wxString::erase(size_t nStart, size_t nLen)
1711 {
1712   wxString strTmp(c_str(), nStart);
1713   if ( nLen != npos ) {
1714     wxASSERT( nStart + nLen <= Len() );
1715
1716     strTmp.append(c_str() + nStart + nLen);
1717   }
1718
1719   *this = strTmp;
1720   return *this;
1721 }
1722
1723 wxString& wxString::replace(size_t nStart, size_t nLen, const wxChar *sz)
1724 {
1725   wxASSERT_MSG( nStart + nLen <= Len(),
1726                 _T("index out of bounds in wxString::replace") );
1727
1728   wxString strTmp;
1729   strTmp.Alloc(Len());      // micro optimisation to avoid multiple mem allocs
1730
1731   if ( nStart != 0 )
1732     strTmp.append(c_str(), nStart);
1733   strTmp << sz << c_str() + nStart + nLen;
1734
1735   *this = strTmp;
1736   return *this;
1737 }
1738
1739 wxString& wxString::replace(size_t nStart, size_t nLen, size_t nCount, wxChar ch)
1740 {
1741   return replace(nStart, nLen, wxString(ch, nCount));
1742 }
1743
1744 wxString& wxString::replace(size_t nStart, size_t nLen,
1745                             const wxString& str, size_t nStart2, size_t nLen2)
1746 {
1747   return replace(nStart, nLen, str.substr(nStart2, nLen2));
1748 }
1749
1750 wxString& wxString::replace(size_t nStart, size_t nLen,
1751                         const wxChar* sz, size_t nCount)
1752 {
1753   return replace(nStart, nLen, wxString(sz, nCount));
1754 }
1755
1756 #endif  //std::string compatibility
1757
1758 // ============================================================================
1759 // ArrayString
1760 // ============================================================================
1761
1762 #include "wx/arrstr.h"
1763
1764 #if !wxUSE_STL
1765
1766 // size increment = min(50% of current size, ARRAY_MAXSIZE_INCREMENT)
1767 #define   ARRAY_MAXSIZE_INCREMENT       4096
1768
1769 #ifndef   ARRAY_DEFAULT_INITIAL_SIZE    // also defined in dynarray.h
1770 #define   ARRAY_DEFAULT_INITIAL_SIZE    (16)
1771 #endif
1772
1773 #define   STRING(p)   ((wxString *)(&(p)))
1774
1775 // ctor
1776 void wxArrayString::Init(bool autoSort)
1777 {
1778   m_nSize  =
1779   m_nCount = 0;
1780   m_pItems = (wxChar **) NULL;
1781   m_autoSort = autoSort;
1782 }
1783
1784 // copy ctor
1785 wxArrayString::wxArrayString(const wxArrayString& src)
1786 {
1787   Init(src.m_autoSort);
1788
1789   *this = src;
1790 }
1791
1792 // assignment operator
1793 wxArrayString& wxArrayString::operator=(const wxArrayString& src)
1794 {
1795   if ( m_nSize > 0 )
1796     Clear();
1797
1798   Copy(src);
1799
1800   m_autoSort = src.m_autoSort;
1801
1802   return *this;
1803 }
1804
1805 void wxArrayString::Copy(const wxArrayString& src)
1806 {
1807   if ( src.m_nCount > ARRAY_DEFAULT_INITIAL_SIZE )
1808     Alloc(src.m_nCount);
1809
1810   for ( size_t n = 0; n < src.m_nCount; n++ )
1811     Add(src[n]);
1812 }
1813
1814 // grow the array
1815 void wxArrayString::Grow(size_t nIncrement)
1816 {
1817   // only do it if no more place
1818   if ( (m_nSize - m_nCount) < nIncrement ) {
1819     // if ARRAY_DEFAULT_INITIAL_SIZE were set to 0, the initially empty would
1820     // be never resized!
1821     #if ARRAY_DEFAULT_INITIAL_SIZE == 0
1822       #error "ARRAY_DEFAULT_INITIAL_SIZE must be > 0!"
1823     #endif
1824
1825     if ( m_nSize == 0 ) {
1826       // was empty, alloc some memory
1827       m_nSize = ARRAY_DEFAULT_INITIAL_SIZE;
1828       if (m_nSize < nIncrement)
1829           m_nSize = nIncrement;
1830       m_pItems = new wxChar *[m_nSize];
1831     }
1832     else {
1833       // otherwise when it's called for the first time, nIncrement would be 0
1834       // and the array would never be expanded
1835       // add 50% but not too much
1836       size_t ndefIncrement = m_nSize < ARRAY_DEFAULT_INITIAL_SIZE
1837                           ? ARRAY_DEFAULT_INITIAL_SIZE : m_nSize >> 1;
1838       if ( ndefIncrement > ARRAY_MAXSIZE_INCREMENT )
1839         ndefIncrement = ARRAY_MAXSIZE_INCREMENT;
1840       if ( nIncrement < ndefIncrement )
1841         nIncrement = ndefIncrement;
1842       m_nSize += nIncrement;
1843       wxChar **pNew = new wxChar *[m_nSize];
1844
1845       // copy data to new location
1846       memcpy(pNew, m_pItems, m_nCount*sizeof(wxChar *));
1847
1848       // delete old memory (but do not release the strings!)
1849       wxDELETEA(m_pItems);
1850
1851       m_pItems = pNew;
1852     }
1853   }
1854 }
1855
1856 void wxArrayString::Free()
1857 {
1858   for ( size_t n = 0; n < m_nCount; n++ ) {
1859     STRING(m_pItems[n])->GetStringData()->Unlock();
1860   }
1861 }
1862
1863 // deletes all the strings from the list
1864 void wxArrayString::Empty()
1865 {
1866   Free();
1867
1868   m_nCount = 0;
1869 }
1870
1871 // as Empty, but also frees memory
1872 void wxArrayString::Clear()
1873 {
1874   Free();
1875
1876   m_nSize  =
1877   m_nCount = 0;
1878
1879   wxDELETEA(m_pItems);
1880 }
1881
1882 // dtor
1883 wxArrayString::~wxArrayString()
1884 {
1885   Free();
1886
1887   wxDELETEA(m_pItems);
1888 }
1889
1890 // pre-allocates memory (frees the previous data!)
1891 void wxArrayString::Alloc(size_t nSize)
1892 {
1893   // only if old buffer was not big enough
1894   if ( nSize > m_nSize ) {
1895     Free();
1896     wxDELETEA(m_pItems);
1897     m_pItems = new wxChar *[nSize];
1898     m_nSize  = nSize;
1899   }
1900
1901   m_nCount = 0;
1902 }
1903
1904 // minimizes the memory usage by freeing unused memory
1905 void wxArrayString::Shrink()
1906 {
1907   // only do it if we have some memory to free
1908   if( m_nCount < m_nSize ) {
1909     // allocates exactly as much memory as we need
1910     wxChar **pNew = new wxChar *[m_nCount];
1911
1912     // copy data to new location
1913     memcpy(pNew, m_pItems, m_nCount*sizeof(wxChar *));
1914     delete [] m_pItems;
1915     m_pItems = pNew;
1916   }
1917 }
1918
1919 #if WXWIN_COMPATIBILITY_2_4
1920
1921 // return a wxString[] as required for some control ctors.
1922 wxString* wxArrayString::GetStringArray() const
1923 {
1924     wxString *array = 0;
1925
1926     if( m_nCount > 0 )
1927     {
1928         array = new wxString[m_nCount];
1929         for( size_t i = 0; i < m_nCount; i++ )
1930             array[i] = m_pItems[i];
1931     }
1932
1933     return array;
1934 }
1935
1936 #endif // WXWIN_COMPATIBILITY_2_4
1937
1938 // searches the array for an item (forward or backwards)
1939 int wxArrayString::Index(const wxChar *sz, bool bCase, bool bFromEnd) const
1940 {
1941   if ( m_autoSort ) {
1942     // use binary search in the sorted array
1943     wxASSERT_MSG( bCase && !bFromEnd,
1944                   wxT("search parameters ignored for auto sorted array") );
1945
1946     size_t i,
1947            lo = 0,
1948            hi = m_nCount;
1949     int res;
1950     while ( lo < hi ) {
1951       i = (lo + hi)/2;
1952
1953       res = wxStrcmp(sz, m_pItems[i]);
1954       if ( res < 0 )
1955         hi = i;
1956       else if ( res > 0 )
1957         lo = i + 1;
1958       else
1959         return i;
1960     }
1961
1962     return wxNOT_FOUND;
1963   }
1964   else {
1965     // use linear search in unsorted array
1966     if ( bFromEnd ) {
1967       if ( m_nCount > 0 ) {
1968         size_t ui = m_nCount;
1969         do {
1970           if ( STRING(m_pItems[--ui])->IsSameAs(sz, bCase) )
1971             return ui;
1972         }
1973         while ( ui != 0 );
1974       }
1975     }
1976     else {
1977       for( size_t ui = 0; ui < m_nCount; ui++ ) {
1978         if( STRING(m_pItems[ui])->IsSameAs(sz, bCase) )
1979           return ui;
1980       }
1981     }
1982   }
1983
1984   return wxNOT_FOUND;
1985 }
1986
1987 // add item at the end
1988 size_t wxArrayString::Add(const wxString& str, size_t nInsert)
1989 {
1990   if ( m_autoSort ) {
1991     // insert the string at the correct position to keep the array sorted
1992     size_t i,
1993            lo = 0,
1994            hi = m_nCount;
1995     int res;
1996     while ( lo < hi ) {
1997       i = (lo + hi)/2;
1998
1999       res = wxStrcmp(str, m_pItems[i]);
2000       if ( res < 0 )
2001         hi = i;
2002       else if ( res > 0 )
2003         lo = i + 1;
2004       else {
2005         lo = hi = i;
2006         break;
2007       }
2008     }
2009
2010     wxASSERT_MSG( lo == hi, wxT("binary search broken") );
2011
2012     Insert(str, lo, nInsert);
2013
2014     return (size_t)lo;
2015   }
2016   else {
2017     wxASSERT( str.GetStringData()->IsValid() );
2018
2019     Grow(nInsert);
2020
2021     for (size_t i = 0; i < nInsert; i++)
2022     {
2023         // the string data must not be deleted!
2024         str.GetStringData()->Lock();
2025
2026         // just append
2027         m_pItems[m_nCount + i] = (wxChar *)str.c_str(); // const_cast
2028     }
2029     size_t ret = m_nCount;
2030     m_nCount += nInsert;
2031     return ret;
2032   }
2033 }
2034
2035 // add item at the given position
2036 void wxArrayString::Insert(const wxString& str, size_t nIndex, size_t nInsert)
2037 {
2038   wxASSERT( str.GetStringData()->IsValid() );
2039
2040   wxCHECK_RET( nIndex <= m_nCount, wxT("bad index in wxArrayString::Insert") );
2041   wxCHECK_RET( m_nCount <= m_nCount + nInsert,
2042                wxT("array size overflow in wxArrayString::Insert") );
2043
2044   Grow(nInsert);
2045
2046   memmove(&m_pItems[nIndex + nInsert], &m_pItems[nIndex],
2047           (m_nCount - nIndex)*sizeof(wxChar *));
2048
2049   for (size_t i = 0; i < nInsert; i++)
2050   {
2051       str.GetStringData()->Lock();
2052       m_pItems[nIndex + i] = (wxChar *)str.c_str();
2053   }
2054   m_nCount += nInsert;
2055 }
2056
2057 // expand the array
2058 void wxArrayString::SetCount(size_t count)
2059 {
2060     Alloc(count);
2061
2062     wxString s;
2063     while ( m_nCount < count )
2064         m_pItems[m_nCount++] = (wxChar *)s.c_str();
2065 }
2066
2067 // removes item from array (by index)
2068 void wxArrayString::RemoveAt(size_t nIndex, size_t nRemove)
2069 {
2070   wxCHECK_RET( nIndex < m_nCount, wxT("bad index in wxArrayString::Remove") );
2071   wxCHECK_RET( nIndex + nRemove <= m_nCount,
2072                wxT("removing too many elements in wxArrayString::Remove") );
2073
2074   // release our lock
2075   for (size_t i = 0; i < nRemove; i++)
2076       Item(nIndex + i).GetStringData()->Unlock();
2077
2078   memmove(&m_pItems[nIndex], &m_pItems[nIndex + nRemove],
2079           (m_nCount - nIndex - nRemove)*sizeof(wxChar *));
2080   m_nCount -= nRemove;
2081 }
2082
2083 // removes item from array (by value)
2084 void wxArrayString::Remove(const wxChar *sz)
2085 {
2086   int iIndex = Index(sz);
2087
2088   wxCHECK_RET( iIndex != wxNOT_FOUND,
2089                wxT("removing inexistent element in wxArrayString::Remove") );
2090
2091   RemoveAt(iIndex);
2092 }
2093
2094 // ----------------------------------------------------------------------------
2095 // sorting
2096 // ----------------------------------------------------------------------------
2097
2098 // we can only sort one array at a time with the quick-sort based
2099 // implementation
2100 #if wxUSE_THREADS
2101   // need a critical section to protect access to gs_compareFunction and
2102   // gs_sortAscending variables
2103   static wxCriticalSection *gs_critsectStringSort = NULL;
2104
2105   // call this before the value of the global sort vars is changed/after
2106   // you're finished with them
2107   #define START_SORT()     wxASSERT( !gs_critsectStringSort );                \
2108                            gs_critsectStringSort = new wxCriticalSection;     \
2109                            gs_critsectStringSort->Enter()
2110   #define END_SORT()       gs_critsectStringSort->Leave();                    \
2111                            delete gs_critsectStringSort;                      \
2112                            gs_critsectStringSort = NULL
2113 #else // !threads
2114   #define START_SORT()
2115   #define END_SORT()
2116 #endif // wxUSE_THREADS
2117
2118 // function to use for string comparaison
2119 static wxArrayString::CompareFunction gs_compareFunction = NULL;
2120
2121 // if we don't use the compare function, this flag tells us if we sort the
2122 // array in ascending or descending order
2123 static bool gs_sortAscending = TRUE;
2124
2125 // function which is called by quick sort
2126 extern "C" int wxC_CALLING_CONV     // LINKAGEMODE
2127 wxStringCompareFunction(const void *first, const void *second)
2128 {
2129   wxString *strFirst = (wxString *)first;
2130   wxString *strSecond = (wxString *)second;
2131
2132   if ( gs_compareFunction ) {
2133     return gs_compareFunction(*strFirst, *strSecond);
2134   }
2135   else {
2136     // maybe we should use wxStrcoll
2137     int result = wxStrcmp(strFirst->c_str(), strSecond->c_str());
2138
2139     return gs_sortAscending ? result : -result;
2140   }
2141 }
2142
2143 // sort array elements using passed comparaison function
2144 void wxArrayString::Sort(CompareFunction compareFunction)
2145 {
2146   START_SORT();
2147
2148   wxASSERT( !gs_compareFunction );  // must have been reset to NULL
2149   gs_compareFunction = compareFunction;
2150
2151   DoSort();
2152
2153   // reset it to NULL so that Sort(bool) will work the next time
2154   gs_compareFunction = NULL;
2155
2156   END_SORT();
2157 }
2158
2159 typedef  int (wxC_CALLING_CONV * wxStringCompareFn)(const void *first, const void *second);
2160
2161 void wxArrayString::Sort(CompareFunction2 compareFunction)
2162 {
2163   qsort(m_pItems, m_nCount, sizeof(wxChar *), (wxStringCompareFn)compareFunction);
2164 }
2165
2166 void wxArrayString::Sort(bool reverseOrder)
2167 {
2168   Sort(reverseOrder ? wxStringSortDescending : wxStringSortAscending);
2169 }
2170
2171 void wxArrayString::DoSort()
2172 {
2173   wxCHECK_RET( !m_autoSort, wxT("can't use this method with sorted arrays") );
2174
2175   // just sort the pointers using qsort() - of course it only works because
2176   // wxString() *is* a pointer to its data
2177   qsort(m_pItems, m_nCount, sizeof(wxChar *), wxStringCompareFunction);
2178 }
2179
2180 bool wxArrayString::operator==(const wxArrayString& a) const
2181 {
2182     if ( m_nCount != a.m_nCount )
2183         return FALSE;
2184
2185     for ( size_t n = 0; n < m_nCount; n++ )
2186     {
2187         if ( Item(n) != a[n] )
2188             return FALSE;
2189     }
2190
2191     return TRUE;
2192 }
2193
2194 #endif // !wxUSE_STL
2195
2196 int wxStringSortAscending(wxString* s1, wxString* s2)
2197 {
2198     return wxStrcmp(s1->c_str(), s2->c_str());
2199 }
2200
2201 int wxStringSortDescending(wxString* s1, wxString* s2)
2202 {
2203     return -wxStrcmp(s1->c_str(), s2->c_str());
2204 }