contrib/libstdc++3/include/bits/basic_string.tcc

   1 // Components for manipulating sequences of characters -*- C++ -*-
   2
   3 // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003
   4 // Free Software Foundation, Inc.
   5 //
   6 // This file is part of the GNU ISO C++ Library.  This library is free
   7 // software; you can redistribute it and/or modify it under the
   8 // terms of the GNU General Public License as published by the
   9 // Free Software Foundation; either version 2, or (at your option)
  10 // any later version.
  11
  12 // This library is distributed in the hope that it will be useful,
  13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 // GNU General Public License for more details.
  16
  17 // You should have received a copy of the GNU General Public License along
  18 // with this library; see the file COPYING.  If not, write to the Free
  19 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  20 // USA.
  21
  22 // As a special exception, you may use this file as part of a free software
  23 // library without restriction.  Specifically, if other files instantiate
  24 // templates or use macros or inline functions from this file, or you compile
  25 // this file and link it with other files to produce an executable, this
  26 // file does not by itself cause the resulting executable to be covered by
  27 // the GNU General Public License.  This exception does not however
  28 // invalidate any other reasons why the executable file might be covered by
  29 // the GNU General Public License.
  30
  31 //
  32 // ISO C++ 14882: 21  Strings library
  33 //
  34
  35 // This file is included by <string>.  It is not meant to be included
  36 // separately.
  37
  38 // Written by Jason Merrill based upon the specification by Takanori Adachi
  39 // in ANSI X3J16/94-0013R2.  Rewritten by Nathan Myers to ISO-14882.
  40
  41 #ifndef _CPP_BITS_STRING_TCC
  42 #define _CPP_BITS_STRING_TCC 1
  43
  44 #pragma GCC system_header
  45
  46 namespace std
  47 {
  48   template<typename _CharT, typename _Traits, typename _Alloc>
  49     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
  50     basic_string<_CharT, _Traits, _Alloc>::
  51     _Rep::_S_max_size = (((npos - sizeof(_Rep))/sizeof(_CharT)) - 1) / 4;
  52
  53   template<typename _CharT, typename _Traits, typename _Alloc>
  54     const _CharT
  55     basic_string<_CharT, _Traits, _Alloc>::
  56     _Rep::_S_terminal = _CharT();
  57
  58   template<typename _CharT, typename _Traits, typename _Alloc>
  59     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
  60     basic_string<_CharT, _Traits, _Alloc>::npos;
  61
  62   // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
  63   // at static init time (before static ctors are run).
  64   template<typename _CharT, typename _Traits, typename _Alloc>
  65     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  66     basic_string<_CharT, _Traits, _Alloc>::_S_empty_rep_storage[
  67     (sizeof(_Rep) + sizeof(_CharT) + sizeof(size_type) - 1)/sizeof(size_type)];
  68
  69   // NB: This is the special case for Input Iterators, used in
  70   // istreambuf_iterators, etc.
  71   // Input Iterators have a cost structure very different from
  72   // pointers, calling for a different coding style.
  73   template<typename _CharT, typename _Traits, typename _Alloc>
  74     template<typename _InIter>
  75       _CharT*
  76       basic_string<_CharT, _Traits, _Alloc>::
  77       _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
  78                    input_iterator_tag)
  79       {
  80         if (__beg == __end && __a == _Alloc())
  81           return _S_empty_rep()._M_refcopy();
  82         // Avoid reallocation for common case.
  83         _CharT __buf[100];
  84         size_type __i = 0;
  85         while (__beg != __end && __i < sizeof(__buf) / sizeof(_CharT))
  86           {
  87             __buf[__i++] = *__beg;
  88             ++__beg;
  89           }
  90         _Rep* __r = _Rep::_S_create(__i, __a);
  91         traits_type::copy(__r->_M_refdata(), __buf, __i);
  92         __r->_M_length = __i;
  93         try
  94           {
  95             // NB: this loop looks precisely this way because
  96             // it avoids comparing __beg != __end any more
  97             // than strictly necessary; != might be expensive!
  98             for (;;)
  99               {
 100                 _CharT* __p = __r->_M_refdata() + __r->_M_length;
 101                 _CharT* __last = __r->_M_refdata() + __r->_M_capacity;
 102                 for (;;)
 103                   {
 104                     if (__beg == __end)
 105                       {
 106                         __r->_M_length = __p - __r->_M_refdata();
 107                         *__p = _Rep::_S_terminal;       // grrr.
 108                         return __r->_M_refdata();
 109                       }
 110                     if (__p == __last)
 111                       break;
 112                     *__p++ = *__beg;
 113                     ++__beg;
 114                   }
 115                 // Allocate more space.
 116                 size_type __len = __p - __r->_M_refdata();
 117                 _Rep* __another = _Rep::_S_create(__len + 1, __a);
 118                 traits_type::copy(__another->_M_refdata(),
 119                                   __r->_M_refdata(), __len);
 120                 __r->_M_destroy(__a);
 121                 __r = __another;
 122                 __r->_M_length = __len;
 123               }
 124           }
 125         catch(...)
 126           {
 127             __r->_M_destroy(__a);
 128             __throw_exception_again;
 129           }
 130         return 0;
 131       }
 132
 133   template<typename _CharT, typename _Traits, typename _Alloc>
 134     template <class _InIter>
 135       _CharT*
 136       basic_string<_CharT, _Traits, _Alloc>::
 137       _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a,
 138                    forward_iterator_tag)
 139       {
 140         if (__beg == __end && __a == _Alloc())
 141           return _S_empty_rep()._M_refcopy();
 142
 143         // NB: Not required, but considered best practice.
 144         if (__builtin_expect(__beg == _InIter(), 0))
 145           __throw_logic_error("attempt to create string with null pointer");
 146
 147         size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
 148
 149         // Check for out_of_range and length_error exceptions.
 150         _Rep* __r = _Rep::_S_create(__dnew, __a);
 151         try
 152           { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
 153         catch(...)
 154           {
 155             __r->_M_destroy(__a);
 156             __throw_exception_again;
 157           }
 158         __r->_M_length = __dnew;
 159
 160         __r->_M_refdata()[__dnew] = _Rep::_S_terminal;  // grrr.
 161         return __r->_M_refdata();
 162       }
 163
 164   template<typename _CharT, typename _Traits, typename _Alloc>
 165     _CharT*
 166     basic_string<_CharT, _Traits, _Alloc>::
 167     _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
 168     {
 169       if (__n == 0 && __a == _Alloc())
 170         return _S_empty_rep()._M_refcopy();
 171
 172       // Check for out_of_range and length_error exceptions.
 173       _Rep* __r = _Rep::_S_create(__n, __a);
 174       try
 175         {
 176           if (__n)
 177             traits_type::assign(__r->_M_refdata(), __n, __c);
 178         }
 179       catch(...)
 180         {
 181           __r->_M_destroy(__a);
 182           __throw_exception_again;
 183         }
 184       __r->_M_length = __n;
 185       __r->_M_refdata()[__n] = _Rep::_S_terminal;  // grrr
 186       return __r->_M_refdata();
 187     }
 188
 189   template<typename _CharT, typename _Traits, typename _Alloc>
 190     basic_string<_CharT, _Traits, _Alloc>::
 191     basic_string(const basic_string& __str)
 192     : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(), __str.get_allocator()),
 193                  __str.get_allocator())
 194     { }
 195
 196   template<typename _CharT, typename _Traits, typename _Alloc>
 197     basic_string<_CharT, _Traits, _Alloc>::
 198     basic_string(const _Alloc& __a)
 199     : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a)
 200     { }
 201
 202   template<typename _CharT, typename _Traits, typename _Alloc>
 203     basic_string<_CharT, _Traits, _Alloc>::
 204     basic_string(const basic_string& __str, size_type __pos, size_type __n)
 205     : _M_dataplus(_S_construct(__str._M_check(__pos),
 206                                __str._M_fold(__pos, __n), _Alloc()), _Alloc())
 207     { }
 208
 209   template<typename _CharT, typename _Traits, typename _Alloc>
 210     basic_string<_CharT, _Traits, _Alloc>::
 211     basic_string(const basic_string& __str, size_type __pos,
 212                  size_type __n, const _Alloc& __a)
 213     : _M_dataplus(_S_construct(__str._M_check(__pos),
 214                                __str._M_fold(__pos, __n), __a), __a)
 215     { }
 216
 217   template<typename _CharT, typename _Traits, typename _Alloc>
 218     basic_string<_CharT, _Traits, _Alloc>::
 219     basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
 220     : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
 221     { }
 222
 223   template<typename _CharT, typename _Traits, typename _Alloc>
 224     basic_string<_CharT, _Traits, _Alloc>::
 225     basic_string(const _CharT* __s, const _Alloc& __a)
 226     : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) :
 227                                __s + npos, __a), __a)
 228     { }
 229
 230   template<typename _CharT, typename _Traits, typename _Alloc>
 231     basic_string<_CharT, _Traits, _Alloc>::
 232     basic_string(size_type __n, _CharT __c, const _Alloc& __a)
 233     : _M_dataplus(_S_construct(__n, __c, __a), __a)
 234     { }
 235
 236   template<typename _CharT, typename _Traits, typename _Alloc>
 237     template<typename _InputIter>
 238     basic_string<_CharT, _Traits, _Alloc>::
 239     basic_string(_InputIter __beg, _InputIter __end, const _Alloc& __a)
 240     : _M_dataplus(_S_construct(__beg, __end, __a), __a)
 241     { }
 242
 243   template<typename _CharT, typename _Traits, typename _Alloc>
 244     basic_string<_CharT, _Traits, _Alloc>&
 245     basic_string<_CharT, _Traits, _Alloc>::assign(const basic_string& __str)
 246     {
 247       if (_M_rep() != __str._M_rep())
 248         {
 249           // XXX MT
 250           allocator_type __a = this->get_allocator();
 251           _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
 252           _M_rep()->_M_dispose(__a);
 253           _M_data(__tmp);
 254         }
 255       return *this;
 256     }
 257
 258    template<typename _CharT, typename _Traits, typename _Alloc>
 259      basic_string<_CharT, _Traits, _Alloc>&
 260      basic_string<_CharT, _Traits, _Alloc>::
 261      assign(const basic_string& __str, size_type __pos, size_type __n)
 262      {
 263        const size_type __strsize = __str.size();
 264        if (__pos > __strsize)
 265          __throw_out_of_range("basic_string::assign");
 266        const bool __testn = __n < __strsize - __pos;
 267        const size_type __newsize = __testn ? __n : __strsize - __pos;
 268        return this->assign(__str._M_data() + __pos, __newsize);
 269      }
 270
 271    template<typename _CharT, typename _Traits, typename _Alloc>
 272      basic_string<_CharT, _Traits, _Alloc>&
 273      basic_string<_CharT, _Traits, _Alloc>::
 274      assign(const _CharT* __s, size_type __n)
 275      {
 276        if (__n > this->max_size())
 277          __throw_length_error("basic_string::assign");
 278        if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
 279            || less<const _CharT*>()(_M_data() + this->size(), __s))
 280          return _M_replace_safe(_M_ibegin(), _M_iend(), __s, __s + __n);
 281        else
 282          {
 283            // Work in-place
 284            const size_type __pos = __s - _M_data();
 285            if (__pos >= __n)
 286              traits_type::copy(_M_data(), __s, __n);
 287            else if (__pos)
 288              traits_type::move(_M_data(), __s, __n);
 289            _M_rep()->_M_length = __n;
 290            _M_data()[__n] = _Rep::_S_terminal;  // grr.
 291            return *this;
 292          }
 293      }
 294
 295    template<typename _CharT, typename _Traits, typename _Alloc>
 296      basic_string<_CharT, _Traits, _Alloc>&
 297      basic_string<_CharT, _Traits, _Alloc>::
 298      insert(size_type __pos1, const basic_string& __str,
 299             size_type __pos2, size_type __n)
 300      {
 301        const size_type __strsize = __str.size();
 302        if (__pos2 > __strsize)
 303          __throw_out_of_range("basic_string::insert");
 304        const bool __testn = __n < __strsize - __pos2;
 305        const size_type __newsize = __testn ? __n : __strsize - __pos2;
 306        return this->insert(__pos1, __str._M_data() + __pos2, __newsize);
 307      }
 308
 309    template<typename _CharT, typename _Traits, typename _Alloc>
 310      basic_string<_CharT, _Traits, _Alloc>&
 311      basic_string<_CharT, _Traits, _Alloc>::
 312      insert(size_type __pos, const _CharT* __s, size_type __n)
 313      {
 314        const size_type __size = this->size();
 315        if (__pos > __size)
 316          __throw_out_of_range("basic_string::insert");
 317        if (__size > this->max_size() - __n)
 318          __throw_length_error("basic_string::insert");
 319        if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
 320            || less<const _CharT*>()(_M_data() + __size, __s))
 321          return _M_replace_safe(_M_ibegin() + __pos, _M_ibegin() + __pos,
 322                                 __s, __s + __n);
 323        else
 324          {
 325            // Work in-place. If _M_mutate reallocates the string, __s
 326            // does not point anymore to valid data, therefore we save its
 327            // offset, then we restore it.
 328            const size_type __off = __s - _M_data();
 329            _M_mutate(__pos, 0, __n);
 330            __s = _M_data() + __off;
 331            _CharT* __p = _M_data() + __pos;
 332            if (__s  + __n <= __p)
 333              traits_type::copy(__p, __s, __n);
 334            else if (__s >= __p)
 335              traits_type::copy(__p, __s + __n, __n);
 336            else
 337              {
 338                traits_type::copy(__p, __s, __p - __s);
 339                traits_type::copy(__p + (__p-__s), __p + __n, __n - (__p-__s));
 340              }
 341            return *this;
 342          }
 343      }
 344
 345    template<typename _CharT, typename _Traits, typename _Alloc>
 346      basic_string<_CharT, _Traits, _Alloc>&
 347      basic_string<_CharT, _Traits, _Alloc>::
 348      replace(size_type __pos, size_type __n1, const _CharT* __s,
 349              size_type __n2)
 350      {
 351        const size_type __size = this->size();
 352        if (__pos > __size)
 353          __throw_out_of_range("basic_string::replace");
 354        const bool __testn1 = __n1 < __size - __pos;
 355        const size_type __foldn1 = __testn1 ? __n1 : __size - __pos;
 356        if (__size - __foldn1 > this->max_size() - __n2)
 357          __throw_length_error("basic_string::replace");
 358        if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
 359            || less<const _CharT*>()(_M_data() + __size, __s))
 360          return _M_replace_safe(_M_ibegin() + __pos,
 361                                 _M_ibegin() + __pos + __foldn1, __s, __s + __n2);
 362        // Todo: optimized in-place replace.
 363        else
 364          return _M_replace(_M_ibegin() + __pos, _M_ibegin() + __pos + __foldn1,
 365                            __s, __s + __n2,
 366                            typename iterator_traits<const _CharT*>::iterator_category());
 367      }
 368
 369   template<typename _CharT, typename _Traits, typename _Alloc>
 370     void
 371     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 372     _M_destroy(const _Alloc& __a) throw ()
 373     {
 374       size_type __size = sizeof(_Rep) + (_M_capacity + 1) * sizeof(_CharT);
 375       _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
 376     }
 377
 378   template<typename _CharT, typename _Traits, typename _Alloc>
 379     void
 380     basic_string<_CharT, _Traits, _Alloc>::_M_leak_hard()
 381     {
 382       if (_M_rep()->_M_is_shared())
 383         _M_mutate(0, 0, 0);
 384       _M_rep()->_M_set_leaked();
 385     }
 386
 387   // _M_mutate and, below, _M_clone, include, in the same form, an exponential
 388   // growth policy, necessary to meet amortized linear time requirements of
 389   // the library: see http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
 390   // The policy is active for allocations requiring an amount of memory above
 391   // system pagesize. This is consistent with the requirements of the standard:
 392   // see, f.i., http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
 393   template<typename _CharT, typename _Traits, typename _Alloc>
 394     void
 395     basic_string<_CharT, _Traits, _Alloc>::
 396     _M_mutate(size_type __pos, size_type __len1, size_type __len2)
 397     {
 398       size_type       __old_size = this->size();
 399       const size_type __new_size = __old_size + __len2 - __len1;
 400       const _CharT*        __src = _M_data()  + __pos + __len1;
 401       const size_type __how_much = __old_size - __pos - __len1;
 402
 403       if (_M_rep()->_M_is_shared() || __new_size > capacity())
 404         {
 405           // Must reallocate.
 406           allocator_type __a = get_allocator();
 407           // See below (_S_create) for the meaning and value of these
 408           // constants.
 409           const size_type __pagesize = 4096;
 410           const size_type __malloc_header_size = 4 * sizeof (void*);
 411           // The biggest string which fits in a memory page
 412           const size_type __page_capacity = (__pagesize - __malloc_header_size
 413                                              - sizeof(_Rep) - sizeof(_CharT))
 414                                              / sizeof(_CharT);
 415           _Rep* __r;
 416           if (__new_size > capacity() && __new_size > __page_capacity)
 417             // Growing exponentially.
 418             __r = _Rep::_S_create(__new_size > 2*capacity() ?
 419                                   __new_size : 2*capacity(), __a);
 420           else
 421             __r = _Rep::_S_create(__new_size, __a);
 422           try
 423             {
 424               if (__pos)
 425                 traits_type::copy(__r->_M_refdata(), _M_data(), __pos);
 426               if (__how_much)
 427                 traits_type::copy(__r->_M_refdata() + __pos + __len2,
 428                                   __src, __how_much);
 429             }
 430           catch(...)
 431             {
 432               __r->_M_dispose(get_allocator());
 433               __throw_exception_again;
 434             }
 435           _M_rep()->_M_dispose(__a);
 436           _M_data(__r->_M_refdata());
 437       }
 438       else if (__how_much && __len1 != __len2)
 439         {
 440           // Work in-place
 441           traits_type::move(_M_data() + __pos + __len2, __src, __how_much);
 442         }
 443       _M_rep()->_M_set_sharable();
 444       _M_rep()->_M_length = __new_size;
 445       _M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4)
 446     // You cannot leave those LWG people alone for a second.
 447     }
 448
 449   template<typename _CharT, typename _Traits, typename _Alloc>
 450     void
 451     basic_string<_CharT, _Traits, _Alloc>::reserve(size_type __res)
 452     {
 453       if (__res > this->capacity() || _M_rep()->_M_is_shared())
 454         {
 455           if (__res > this->max_size())
 456             __throw_length_error("basic_string::reserve");
 457           // Make sure we don't shrink below the current size
 458           if (__res < this->size())
 459             __res = this->size();
 460           allocator_type __a = get_allocator();
 461           _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
 462           _M_rep()->_M_dispose(__a);
 463           _M_data(__tmp);
 464         }
 465     }
 466
 467   template<typename _CharT, typename _Traits, typename _Alloc>
 468     void basic_string<_CharT, _Traits, _Alloc>::swap(basic_string& __s)
 469     {
 470       if (_M_rep()->_M_is_leaked())
 471         _M_rep()->_M_set_sharable();
 472       if (__s._M_rep()->_M_is_leaked())
 473         __s._M_rep()->_M_set_sharable();
 474       if (this->get_allocator() == __s.get_allocator())
 475         {
 476           _CharT* __tmp = _M_data();
 477           _M_data(__s._M_data());
 478           __s._M_data(__tmp);
 479         }
 480       // The code below can usually be optimized away.
 481       else
 482         {
 483           basic_string __tmp1(_M_ibegin(), _M_iend(), __s.get_allocator());
 484           basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
 485                               this->get_allocator());
 486           *this = __tmp2;
 487           __s = __tmp1;
 488         }
 489     }
 490
 491   template<typename _CharT, typename _Traits, typename _Alloc>
 492     typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
 493     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 494     _S_create(size_t __capacity, const _Alloc& __alloc)
 495     {
 496       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 497 #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS
 498       // 83.  String::npos vs. string::max_size()
 499       if (__capacity > _S_max_size)
 500 #else
 501       if (__capacity == npos)
 502 #endif
 503         __throw_length_error("basic_string::_S_create");
 504
 505       // NB: Need an array of char_type[__capacity], plus a
 506       // terminating null char_type() element, plus enough for the
 507       // _Rep data structure. Whew. Seemingly so needy, yet so elemental.
 508       size_t __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
 509
 510       // The standard places no restriction on allocating more memory
 511       // than is strictly needed within this layer at the moment or as
 512       // requested by an explicit application call to reserve().  Many
 513       // malloc implementations perform quite poorly when an
 514       // application attempts to allocate memory in a stepwise fashion
 515       // growing each allocation size by only 1 char.  Additionally,
 516       // it makes little sense to allocate less linear memory than the
 517       // natural blocking size of the malloc implementation.
 518       // Unfortunately, we would need a somewhat low-level calculation
 519       // with tuned parameters to get this perfect for any particular
 520       // malloc implementation.  Fortunately, generalizations about
 521       // common features seen among implementations seems to suffice.
 522
 523       // __pagesize need not match the actual VM page size for good
 524       // results in practice, thus we pick a common value on the low
 525       // side.  __malloc_header_size is an estimate of the amount of
 526       // overhead per memory allocation (in practice seen N * sizeof
 527       // (void*) where N is 0, 2 or 4).  According to folklore,
 528       // picking this value on the high side is better than
 529       // low-balling it (especially when this algorithm is used with
 530       // malloc implementations that allocate memory blocks rounded up
 531       // to a size which is a power of 2).
 532       const size_t __pagesize = 4096; // must be 2^i * __subpagesize
 533       const size_t __subpagesize = 128; // should be >> __malloc_header_size
 534       const size_t __malloc_header_size = 4 * sizeof (void*);
 535       if ((__size + __malloc_header_size) > __pagesize)
 536         {
 537           size_t __extra =
 538             (__pagesize - ((__size + __malloc_header_size) % __pagesize))
 539             % __pagesize;
 540           __capacity += __extra / sizeof(_CharT);
 541           __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
 542         }
 543       else if (__size > __subpagesize)
 544         {
 545           size_t __extra =
 546             (__subpagesize - ((__size + __malloc_header_size) % __subpagesize))
 547             % __subpagesize;
 548           __capacity += __extra / sizeof(_CharT);
 549           __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
 550         }
 551
 552       // NB: Might throw, but no worries about a leak, mate: _Rep()
 553       // does not throw.
 554       void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
 555       _Rep *__p = new (__place) _Rep;
 556       __p->_M_capacity = __capacity;
 557       __p->_M_set_sharable();  // One reference.
 558       __p->_M_length = 0;
 559       return __p;
 560     }
 561
 562   template<typename _CharT, typename _Traits, typename _Alloc>
 563     _CharT*
 564     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 565     _M_clone(const _Alloc& __alloc, size_type __res)
 566     {
 567       // Requested capacity of the clone.
 568       const size_type __requested_cap = _M_length + __res;
 569       // See above (_S_create) for the meaning and value of these constants.
 570       const size_type __pagesize = 4096;
 571       const size_type __malloc_header_size = 4 * sizeof (void*);
 572       // The biggest string which fits in a memory page.
 573       const size_type __page_capacity =
 574         (__pagesize - __malloc_header_size - sizeof(_Rep) - sizeof(_CharT))
 575         / sizeof(_CharT);
 576       _Rep* __r;
 577       if (__requested_cap > _M_capacity && __requested_cap > __page_capacity)
 578         // Growing exponentially.
 579         __r = _Rep::_S_create(__requested_cap > 2*_M_capacity ?
 580                               __requested_cap : 2*_M_capacity, __alloc);
 581       else
 582         __r = _Rep::_S_create(__requested_cap, __alloc);
 583
 584       if (_M_length)
 585         {
 586           try
 587             { traits_type::copy(__r->_M_refdata(), _M_refdata(), _M_length); }
 588           catch(...)
 589             {
 590               __r->_M_destroy(__alloc);
 591               __throw_exception_again;
 592             }
 593         }
 594       __r->_M_length = _M_length;
 595       return __r->_M_refdata();
 596     }
 597
 598   template<typename _CharT, typename _Traits, typename _Alloc>
 599     void
 600     basic_string<_CharT, _Traits, _Alloc>::resize(size_type __n, _CharT __c)
 601     {
 602       if (__n > max_size())
 603         __throw_length_error("basic_string::resize");
 604       size_type __size = this->size();
 605       if (__size < __n)
 606         this->append(__n - __size, __c);
 607       else if (__n < __size)
 608         this->erase(__n);
 609       // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
 610     }
 611
 612   // This is the general replace helper, which currently gets instantiated both
 613   // for input iterators and reverse iterators. It buffers internally and then
 614   // calls _M_replace_safe.
 615   template<typename _CharT, typename _Traits, typename _Alloc>
 616     template<typename _InputIter>
 617       basic_string<_CharT, _Traits, _Alloc>&
 618       basic_string<_CharT, _Traits, _Alloc>::
 619       _M_replace(iterator __i1, iterator __i2, _InputIter __k1,
 620                  _InputIter __k2, input_iterator_tag)
 621       {
 622         // Save concerned source string data in a temporary.
 623         basic_string __s(__k1, __k2);
 624         return _M_replace_safe(__i1, __i2, __s._M_ibegin(), __s._M_iend());
 625       }
 626
 627   // This is a special replace helper, which does not buffer internally
 628   // and can be used in "safe" situations involving forward iterators,
 629   // i.e., when source and destination ranges are known to not overlap.
 630   template<typename _CharT, typename _Traits, typename _Alloc>
 631     template<typename _ForwardIter>
 632       basic_string<_CharT, _Traits, _Alloc>&
 633       basic_string<_CharT, _Traits, _Alloc>::
 634       _M_replace_safe(iterator __i1, iterator __i2, _ForwardIter __k1,
 635                       _ForwardIter __k2)
 636       {
 637         size_type __dnew = static_cast<size_type>(std::distance(__k1, __k2));
 638         size_type __dold = __i2 - __i1;
 639         size_type __dmax = this->max_size();
 640
 641         if (__dmax <= __dnew)
 642           __throw_length_error("basic_string::_M_replace");
 643         size_type __off = __i1 - _M_ibegin();
 644         _M_mutate(__off, __dold, __dnew);
 645
 646         // Invalidated __i1, __i2
 647         if (__dnew)
 648           _S_copy_chars(_M_data() + __off, __k1, __k2);
 649
 650         return *this;
 651       }
 652
 653   template<typename _CharT, typename _Traits, typename _Alloc>
 654     basic_string<_CharT, _Traits, _Alloc>&
 655     basic_string<_CharT, _Traits, _Alloc>::
 656     replace(size_type __pos1, size_type __n1, const basic_string& __str,
 657             size_type __pos2, size_type __n2)
 658     {
 659       const size_type __strsize = __str.size();
 660       if (__pos2 > __strsize)
 661         __throw_out_of_range("basic_string::replace");
 662       const bool __testn2 = __n2 < __strsize - __pos2;
 663       const size_type __foldn2 = __testn2 ? __n2 : __strsize - __pos2;
 664       return this->replace(__pos1, __n1,
 665                            __str._M_data() + __pos2, __foldn2);
 666     }
 667
 668   template<typename _CharT, typename _Traits, typename _Alloc>
 669     basic_string<_CharT, _Traits, _Alloc>&
 670     basic_string<_CharT, _Traits, _Alloc>::
 671     append(const basic_string& __str)
 672     {
 673       // Iff appending itself, string needs to pre-reserve the
 674       // correct size so that _M_mutate does not clobber the
 675       // iterators formed here.
 676       size_type __size = __str.size();
 677       size_type __len = __size + this->size();
 678       if (__len > this->capacity())
 679         this->reserve(__len);
 680       return _M_replace_safe(_M_iend(), _M_iend(), __str._M_ibegin(),
 681                              __str._M_iend());
 682     }
 683
 684   template<typename _CharT, typename _Traits, typename _Alloc>
 685     basic_string<_CharT, _Traits, _Alloc>&
 686     basic_string<_CharT, _Traits, _Alloc>::
 687     append(const basic_string& __str, size_type __pos, size_type __n)
 688     {
 689       // Iff appending itself, string needs to pre-reserve the
 690       // correct size so that _M_mutate does not clobber the
 691       // iterators formed here.
 692       size_type __len = std::min(size_type(__str.size() - __pos),
 693                                  __n) + this->size();
 694       if (__len > this->capacity())
 695         this->reserve(__len);
 696       return _M_replace_safe(_M_iend(), _M_iend(), __str._M_check(__pos),
 697                              __str._M_fold(__pos, __n));
 698     }
 699
 700   template<typename _CharT, typename _Traits, typename _Alloc>
 701     basic_string<_CharT, _Traits, _Alloc>&
 702     basic_string<_CharT, _Traits, _Alloc>::
 703     append(const _CharT* __s, size_type __n)
 704     {
 705       size_type __len = __n + this->size();
 706       if (__len > this->capacity())
 707         this->reserve(__len);
 708       return _M_replace_safe(_M_iend(), _M_iend(), __s, __s + __n);
 709     }
 710
 711   template<typename _CharT, typename _Traits, typename _Alloc>
 712     basic_string<_CharT, _Traits, _Alloc>&
 713     basic_string<_CharT, _Traits, _Alloc>::
 714     append(size_type __n, _CharT __c)
 715     {
 716       size_type __len = __n + this->size();
 717       if (__len > this->capacity())
 718         this->reserve(__len);
 719        return this->replace(_M_iend(), _M_iend(), __n, __c);
 720     }
 721
 722   template<typename _CharT, typename _Traits, typename _Alloc>
 723     basic_string<_CharT, _Traits, _Alloc>
 724     operator+(const _CharT* __lhs,
 725               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 726     {
 727       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 728       typedef typename __string_type::size_type   __size_type;
 729       __size_type __len = _Traits::length(__lhs);
 730       __string_type __str;
 731       __str.reserve(__len + __rhs.size());
 732       __str.append(__lhs, __lhs + __len);
 733       __str.append(__rhs);
 734       return __str;
 735     }
 736
 737   template<typename _CharT, typename _Traits, typename _Alloc>
 738     basic_string<_CharT, _Traits, _Alloc>
 739     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 740     {
 741       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 742       typedef typename __string_type::size_type   __size_type;
 743       __string_type __str;
 744       __size_type __len = __rhs.size();
 745       __str.reserve(__len + 1);
 746       __str.append(__size_type(1), __lhs);
 747       __str.append(__rhs);
 748       return __str;
 749     }
 750
 751   template<typename _CharT, typename _Traits, typename _Alloc>
 752     basic_string<_CharT, _Traits, _Alloc>&
 753     basic_string<_CharT, _Traits, _Alloc>::
 754     replace(iterator __i1, iterator __i2, size_type __n2, _CharT __c)
 755     {
 756       size_type __n1 = __i2 - __i1;
 757       size_type __off1 = __i1 - _M_ibegin();
 758       if (max_size() - (this->size() - __n1) <= __n2)
 759         __throw_length_error("basic_string::replace");
 760       _M_mutate (__off1, __n1, __n2);
 761       // Invalidated __i1, __i2
 762       if (__n2)
 763         traits_type::assign(_M_data() + __off1, __n2, __c);
 764       return *this;
 765     }
 766
 767   template<typename _CharT, typename _Traits, typename _Alloc>
 768     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 769     basic_string<_CharT, _Traits, _Alloc>::
 770     copy(_CharT* __s, size_type __n, size_type __pos) const
 771     {
 772       if (__pos > this->size())
 773         __throw_out_of_range("basic_string::copy");
 774
 775       if (__n > this->size() - __pos)
 776         __n = this->size() - __pos;
 777
 778       traits_type::copy(__s, _M_data() + __pos, __n);
 779       // 21.3.5.7 par 3: do not append null.  (good.)
 780       return __n;
 781     }
 782
 783   template<typename _CharT, typename _Traits, typename _Alloc>
 784     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 785     basic_string<_CharT, _Traits, _Alloc>::
 786     find(const _CharT* __s, size_type __pos, size_type __n) const
 787     {
 788       size_type __size = this->size();
 789       size_t __xpos = __pos;
 790       const _CharT* __data = _M_data();
 791       for (; __xpos + __n <= __size; ++__xpos)
 792         if (traits_type::compare(__data + __xpos, __s, __n) == 0)
 793           return __xpos;
 794       return npos;
 795     }
 796
 797   template<typename _CharT, typename _Traits, typename _Alloc>
 798     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 799     basic_string<_CharT, _Traits, _Alloc>::
 800     find(_CharT __c, size_type __pos) const
 801     {
 802       size_type __size = this->size();
 803       size_type __ret = npos;
 804       if (__pos < __size)
 805         {
 806           const _CharT* __data = _M_data();
 807           size_type __n = __size - __pos;
 808           const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
 809           if (__p)
 810             __ret = __p - __data;
 811         }
 812       return __ret;
 813     }
 814
 815
 816   template<typename _CharT, typename _Traits, typename _Alloc>
 817     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 818     basic_string<_CharT, _Traits, _Alloc>::
 819     rfind(const _CharT* __s, size_type __pos, size_type __n) const
 820     {
 821       size_type __size = this->size();
 822       if (__n <= __size)
 823         {
 824           __pos = std::min(size_type(__size - __n), __pos);
 825           const _CharT* __data = _M_data();
 826           do
 827             {
 828               if (traits_type::compare(__data + __pos, __s, __n) == 0)
 829                 return __pos;
 830             }
 831           while (__pos-- > 0);
 832         }
 833       return npos;
 834     }
 835
 836   template<typename _CharT, typename _Traits, typename _Alloc>
 837     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 838     basic_string<_CharT, _Traits, _Alloc>::
 839     rfind(_CharT __c, size_type __pos) const
 840     {
 841       size_type __size = this->size();
 842       if (__size)
 843         {
 844           size_t __xpos = __size - 1;
 845           if (__xpos > __pos)
 846             __xpos = __pos;
 847
 848           for (++__xpos; __xpos-- > 0; )
 849             if (traits_type::eq(_M_data()[__xpos], __c))
 850               return __xpos;
 851         }
 852       return npos;
 853     }
 854
 855   template<typename _CharT, typename _Traits, typename _Alloc>
 856     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 857     basic_string<_CharT, _Traits, _Alloc>::
 858     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
 859     {
 860       for (; __n && __pos < this->size(); ++__pos)
 861         {
 862           const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
 863           if (__p)
 864             return __pos;
 865         }
 866       return npos;
 867     }
 868
 869   template<typename _CharT, typename _Traits, typename _Alloc>
 870     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 871     basic_string<_CharT, _Traits, _Alloc>::
 872     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
 873     {
 874       size_type __size = this->size();
 875       if (__size && __n)
 876         {
 877           if (--__size > __pos)
 878             __size = __pos;
 879           do
 880             {
 881               if (traits_type::find(__s, __n, _M_data()[__size]))
 882                 return __size;
 883             }
 884           while (__size-- != 0);
 885         }
 886       return npos;
 887     }
 888
 889   template<typename _CharT, typename _Traits, typename _Alloc>
 890     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 891     basic_string<_CharT, _Traits, _Alloc>::
 892     find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
 893     {
 894       size_t __xpos = __pos;
 895       for (; __xpos < this->size(); ++__xpos)
 896         if (!traits_type::find(__s, __n, _M_data()[__xpos]))
 897           return __xpos;
 898       return npos;
 899     }
 900
 901   template<typename _CharT, typename _Traits, typename _Alloc>
 902     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 903     basic_string<_CharT, _Traits, _Alloc>::
 904     find_first_not_of(_CharT __c, size_type __pos) const
 905     {
 906       size_t __xpos = __pos;
 907       for (; __xpos < this->size(); ++__xpos)
 908         if (!traits_type::eq(_M_data()[__xpos], __c))
 909           return __xpos;
 910       return npos;
 911     }
 912
 913   template<typename _CharT, typename _Traits, typename _Alloc>
 914     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 915     basic_string<_CharT, _Traits, _Alloc>::
 916     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
 917     {
 918       size_type __size = this->size();
 919       if (__size)
 920         {
 921           if (--__size > __pos)
 922             __size = __pos;
 923           do
 924             {
 925               if (!traits_type::find(__s, __n, _M_data()[__size]))
 926                 return __size;
 927             }
 928           while (__size--);
 929         }
 930       return npos;
 931     }
 932
 933   template<typename _CharT, typename _Traits, typename _Alloc>
 934     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 935     basic_string<_CharT, _Traits, _Alloc>::
 936     find_last_not_of(_CharT __c, size_type __pos) const
 937     {
 938       size_type __size = this->size();
 939       if (__size)
 940         {
 941           if (--__size > __pos)
 942             __size = __pos;
 943           do
 944             {
 945               if (!traits_type::eq(_M_data()[__size], __c))
 946                 return __size;
 947             }
 948           while (__size--);
 949         }
 950       return npos;
 951     }
 952
 953   template<typename _CharT, typename _Traits, typename _Alloc>
 954     int
 955     basic_string<_CharT, _Traits, _Alloc>::
 956     compare(size_type __pos, size_type __n, const basic_string& __str) const
 957     {
 958       size_type __size = this->size();
 959       size_type __osize = __str.size();
 960       if (__pos > __size)
 961         __throw_out_of_range("basic_string::compare");
 962
 963       size_type __rsize= std::min(size_type(__size - __pos), __n);
 964       size_type __len = std::min(__rsize, __osize);
 965       int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
 966       if (!__r)
 967         __r = __rsize - __osize;
 968       return __r;
 969     }
 970
 971   template<typename _CharT, typename _Traits, typename _Alloc>
 972     int
 973     basic_string<_CharT, _Traits, _Alloc>::
 974     compare(size_type __pos1, size_type __n1, const basic_string& __str,
 975             size_type __pos2, size_type __n2) const
 976     {
 977       size_type __size = this->size();
 978       size_type __osize = __str.size();
 979       if (__pos1 > __size || __pos2 > __osize)
 980         __throw_out_of_range("basic_string::compare");
 981
 982       size_type __rsize = std::min(size_type(__size - __pos1), __n1);
 983       size_type __rosize = std::min(size_type(__osize - __pos2), __n2);
 984       size_type __len = std::min(__rsize, __rosize);
 985       int __r = traits_type::compare(_M_data() + __pos1,
 986                                      __str.data() + __pos2, __len);
 987       if (!__r)
 988         __r = __rsize - __rosize;
 989       return __r;
 990     }
 991
 992
 993   template<typename _CharT, typename _Traits, typename _Alloc>
 994     int
 995     basic_string<_CharT, _Traits, _Alloc>::
 996     compare(const _CharT* __s) const
 997     {
 998       size_type __size = this->size();
 999       size_type __osize = traits_type::length(__s);
1000       size_type __len = std::min(__size, __osize);
1001       int __r = traits_type::compare(_M_data(), __s, __len);
1002       if (!__r)
1003         __r = __size - __osize;
1004       return __r;
1005     }
1006
1007
1008   template<typename _CharT, typename _Traits, typename _Alloc>
1009     int
1010     basic_string <_CharT, _Traits, _Alloc>::
1011     compare(size_type __pos, size_type __n1, const _CharT* __s) const
1012     {
1013       size_type __size = this->size();
1014       if (__pos > __size)
1015         __throw_out_of_range("basic_string::compare");
1016
1017       size_type __osize = traits_type::length(__s);
1018       size_type __rsize = std::min(size_type(__size - __pos), __n1);
1019       size_type __len = std::min(__rsize, __osize);
1020       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
1021       if (!__r)
1022         __r = __rsize - __osize;
1023       return __r;
1024     }
1025
1026   template<typename _CharT, typename _Traits, typename _Alloc>
1027     int
1028     basic_string <_CharT, _Traits, _Alloc>::
1029     compare(size_type __pos, size_type __n1, const _CharT* __s,
1030             size_type __n2) const
1031     {
1032       size_type __size = this->size();
1033       if (__pos > __size)
1034         __throw_out_of_range("basic_string::compare");
1035
1036       size_type __osize = std::min(traits_type::length(__s), __n2);
1037       size_type __rsize = std::min(size_type(__size - __pos), __n1);
1038       size_type __len = std::min(__rsize, __osize);
1039       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
1040       if (!__r)
1041         __r = __rsize - __osize;
1042       return __r;
1043     }
1044
1045   template <class _CharT, class _Traits, class _Alloc>
1046     void
1047     _S_string_copy(const basic_string<_CharT, _Traits, _Alloc>& __str,
1048                    _CharT* __buf, typename _Alloc::size_type __bufsiz)
1049     {
1050       typedef typename _Alloc::size_type size_type;
1051       size_type __strsize = __str.size();
1052       size_type __bytes = std::min(__strsize, __bufsiz - 1);
1053       _Traits::copy(__buf, __str.data(), __bytes);
1054       __buf[__bytes] = _CharT();
1055     }
1056
1057   // Inhibit implicit instantiations for required instantiations,
1058   // which are defined via explicit instantiations elsewhere.
1059   // NB: This syntax is a GNU extension.
1060 #if _GLIBCPP_EXTERN_TEMPLATE
1061   extern template class basic_string<char>;
1062   extern template
1063     basic_istream<char>&
1064     operator>>(basic_istream<char>&, string&);
1065   extern template
1066     basic_ostream<char>&
1067     operator<<(basic_ostream<char>&, const string&);
1068   extern template
1069     basic_istream<char>&
1070     getline(basic_istream<char>&, string&, char);
1071   extern template
1072     basic_istream<char>&
1073     getline(basic_istream<char>&, string&);
1074
1075 #ifdef _GLIBCPP_USE_WCHAR_T
1076   extern template class basic_string<wchar_t>;
1077   extern template
1078     basic_istream<wchar_t>&
1079     operator>>(basic_istream<wchar_t>&, wstring&);
1080   extern template
1081     basic_ostream<wchar_t>&
1082     operator<<(basic_ostream<wchar_t>&, const wstring&);
1083   extern template
1084     basic_istream<wchar_t>&
1085     getline(basic_istream<wchar_t>&, wstring&, wchar_t);
1086   extern template
1087     basic_istream<wchar_t>&
1088     getline(basic_istream<wchar_t>&, wstring&);
1089 #endif
1090 #endif
1091 } // namespace std
1092
1093 #endif