libstdc++-v3/include/bits/basic_string.tcc

   1 // Components for manipulating sequences of characters -*- C++ -*-
   2
   3 // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004
   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 _BASIC_STRING_TCC
  42 #define _BASIC_STRING_TCC 1
  43
  44 #pragma GCC system_header
  45
  46 namespace std
  47 {
  48   template<typename _Type>
  49     inline bool
  50     __is_null_pointer(_Type* __ptr)
  51     { return __ptr == 0; }
  52
  53   template<typename _Type>
  54     inline bool
  55     __is_null_pointer(_Type)
  56     { return false; }
  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>::
  61     _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4;
  62
  63   template<typename _CharT, typename _Traits, typename _Alloc>
  64     const _CharT
  65     basic_string<_CharT, _Traits, _Alloc>::
  66     _Rep::_S_terminal = _CharT();
  67
  68   template<typename _CharT, typename _Traits, typename _Alloc>
  69     const typename basic_string<_CharT, _Traits, _Alloc>::size_type
  70     basic_string<_CharT, _Traits, _Alloc>::npos;
  71
  72   // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string)
  73   // at static init time (before static ctors are run).
  74   template<typename _CharT, typename _Traits, typename _Alloc>
  75     typename basic_string<_CharT, _Traits, _Alloc>::size_type
  76     basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_empty_rep_storage[
  77     (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) /
  78       sizeof(size_type)];
  79
  80   // NB: This is the special case for Input Iterators, used in
  81   // istreambuf_iterators, etc.
  82   // Input Iterators have a cost structure very different from
  83   // pointers, calling for a different coding style.
  84   template<typename _CharT, typename _Traits, typename _Alloc>
  85     template<typename _InIterator>
  86       _CharT*
  87       basic_string<_CharT, _Traits, _Alloc>::
  88       _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
  89                    input_iterator_tag)
  90       {
  91         if (__beg == __end && __a == _Alloc())
  92           return _S_empty_rep()._M_refdata();
  93         // Avoid reallocation for common case.
  94         _CharT __buf[100];
  95         size_type __i = 0;
  96         while (__beg != __end && __i < sizeof(__buf) / sizeof(_CharT))
  97           {
  98             __buf[__i++] = *__beg;
  99             ++__beg;
 100           }
 101         _Rep* __r = _Rep::_S_create(__i, __a);
 102         traits_type::copy(__r->_M_refdata(), __buf, __i);
 103         __r->_M_length = __i;
 104         try
 105           {
 106             // NB: this loop looks precisely this way because
 107             // it avoids comparing __beg != __end any more
 108             // than strictly necessary; != might be expensive!
 109             for (;;)
 110               {
 111                 _CharT* __p = __r->_M_refdata() + __r->_M_length;
 112                 _CharT* __last = __r->_M_refdata() + __r->_M_capacity;
 113                 for (;;)
 114                   {
 115                     if (__beg == __end)
 116                       {
 117                         __r->_M_length = __p - __r->_M_refdata();
 118                         *__p = _Rep::_S_terminal;       // grrr.
 119                         return __r->_M_refdata();
 120                       }
 121                     if (__p == __last)
 122                       break;
 123                     *__p++ = *__beg;
 124                     ++__beg;
 125                   }
 126                 // Allocate more space.
 127                 const size_type __len = __p - __r->_M_refdata();
 128                 _Rep* __another = _Rep::_S_create(__len + 1, __a);
 129                 traits_type::copy(__another->_M_refdata(),
 130                                   __r->_M_refdata(), __len);
 131                 __r->_M_destroy(__a);
 132                 __r = __another;
 133                 __r->_M_length = __len;
 134               }
 135           }
 136         catch(...)
 137           {
 138             __r->_M_destroy(__a);
 139             __throw_exception_again;
 140           }
 141         return 0;
 142       }
 143
 144   template<typename _CharT, typename _Traits, typename _Alloc>
 145     template <class _InIterator>
 146       _CharT*
 147       basic_string<_CharT, _Traits, _Alloc>::
 148       _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
 149                    forward_iterator_tag)
 150       {
 151         if (__beg == __end && __a == _Alloc())
 152           return _S_empty_rep()._M_refdata();
 153
 154         // NB: Not required, but considered best practice.
 155         if (__builtin_expect(__is_null_pointer(__beg), 0))
 156           __throw_logic_error("basic_string::_S_construct NULL not valid");
 157
 158         const size_type __dnew = static_cast<size_type>(std::distance(__beg, __end));
 159
 160         // Check for out_of_range and length_error exceptions.
 161         _Rep* __r = _Rep::_S_create(__dnew, __a);
 162         try
 163           { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
 164         catch(...)
 165           {
 166             __r->_M_destroy(__a);
 167             __throw_exception_again;
 168           }
 169         __r->_M_length = __dnew;
 170
 171         __r->_M_refdata()[__dnew] = _Rep::_S_terminal;  // grrr.
 172         return __r->_M_refdata();
 173       }
 174
 175   template<typename _CharT, typename _Traits, typename _Alloc>
 176     _CharT*
 177     basic_string<_CharT, _Traits, _Alloc>::
 178     _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
 179     {
 180       if (__n == 0 && __a == _Alloc())
 181         return _S_empty_rep()._M_refdata();
 182
 183       // Check for out_of_range and length_error exceptions.
 184       _Rep* __r = _Rep::_S_create(__n, __a);
 185       if (__n)
 186         traits_type::assign(__r->_M_refdata(), __n, __c);
 187
 188       __r->_M_length = __n;
 189       __r->_M_refdata()[__n] = _Rep::_S_terminal;  // grrr
 190       return __r->_M_refdata();
 191     }
 192
 193   template<typename _CharT, typename _Traits, typename _Alloc>
 194     basic_string<_CharT, _Traits, _Alloc>::
 195     basic_string(const basic_string& __str)
 196     : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(), __str.get_allocator()),
 197                  __str.get_allocator())
 198     { }
 199
 200   template<typename _CharT, typename _Traits, typename _Alloc>
 201     basic_string<_CharT, _Traits, _Alloc>::
 202     basic_string(const _Alloc& __a)
 203     : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a)
 204     { }
 205
 206   template<typename _CharT, typename _Traits, typename _Alloc>
 207     basic_string<_CharT, _Traits, _Alloc>::
 208     basic_string(const basic_string& __str, size_type __pos, size_type __n)
 209     : _M_dataplus(_S_construct(__str._M_ibegin()
 210                                + __str._M_check(__pos, "basic_string::basic_string"),
 211                                __str._M_ibegin() + __pos + __str._M_limit(__pos, __n),
 212                                _Alloc()), _Alloc())
 213     { }
 214
 215   template<typename _CharT, typename _Traits, typename _Alloc>
 216     basic_string<_CharT, _Traits, _Alloc>::
 217     basic_string(const basic_string& __str, size_type __pos,
 218                  size_type __n, const _Alloc& __a)
 219     : _M_dataplus(_S_construct(__str._M_ibegin()
 220                                + __str._M_check(__pos, "basic_string::basic_string"),
 221                                __str._M_ibegin() + __pos + __str._M_limit(__pos, __n),
 222                                __a), __a)
 223     { }
 224
 225   // TBD: DPG annotate
 226   template<typename _CharT, typename _Traits, typename _Alloc>
 227     basic_string<_CharT, _Traits, _Alloc>::
 228     basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
 229     : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
 230     { }
 231
 232   // TBD: DPG annotate
 233   template<typename _CharT, typename _Traits, typename _Alloc>
 234     basic_string<_CharT, _Traits, _Alloc>::
 235     basic_string(const _CharT* __s, const _Alloc& __a)
 236     : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) :
 237                                __s + npos, __a), __a)
 238     { }
 239
 240   template<typename _CharT, typename _Traits, typename _Alloc>
 241     basic_string<_CharT, _Traits, _Alloc>::
 242     basic_string(size_type __n, _CharT __c, const _Alloc& __a)
 243     : _M_dataplus(_S_construct(__n, __c, __a), __a)
 244     { }
 245
 246   // TBD: DPG annotate
 247   template<typename _CharT, typename _Traits, typename _Alloc>
 248     template<typename _InputIterator>
 249     basic_string<_CharT, _Traits, _Alloc>::
 250     basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a)
 251     : _M_dataplus(_S_construct(__beg, __end, __a), __a)
 252     { }
 253
 254   template<typename _CharT, typename _Traits, typename _Alloc>
 255     basic_string<_CharT, _Traits, _Alloc>&
 256     basic_string<_CharT, _Traits, _Alloc>::
 257     assign(const basic_string& __str)
 258     {
 259       if (_M_rep() != __str._M_rep())
 260         {
 261           // XXX MT
 262           allocator_type __a = this->get_allocator();
 263           _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
 264           _M_rep()->_M_dispose(__a);
 265           _M_data(__tmp);
 266         }
 267       return *this;
 268     }
 269
 270    template<typename _CharT, typename _Traits, typename _Alloc>
 271      basic_string<_CharT, _Traits, _Alloc>&
 272      basic_string<_CharT, _Traits, _Alloc>::
 273      assign(const basic_string& __str, size_type __pos, size_type __n)
 274      {
 275        return this->assign(__str._M_data()
 276                            + __str._M_check(__pos, "basic_string::assign"),
 277                            __str._M_limit(__pos, __n));
 278      }
 279
 280    template<typename _CharT, typename _Traits, typename _Alloc>
 281      basic_string<_CharT, _Traits, _Alloc>&
 282      basic_string<_CharT, _Traits, _Alloc>::
 283      assign(const _CharT* __s, size_type __n)
 284      {
 285        __glibcxx_requires_string_len(__s, __n);
 286        if (__n > this->max_size())
 287          __throw_length_error("basic_string::assign");
 288        if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
 289            || less<const _CharT*>()(_M_data() + this->size(), __s))
 290          return _M_replace_safe(size_type(0), this->size(), __s, __n);
 291        else
 292          {
 293            // Work in-place
 294            const size_type __pos = __s - _M_data();
 295            if (__pos >= __n)
 296              traits_type::copy(_M_data(), __s, __n);
 297            else if (__pos)
 298              traits_type::move(_M_data(), __s, __n);
 299            _M_rep()->_M_length = __n;
 300            _M_data()[__n] = _Rep::_S_terminal;  // grr.
 301            return *this;
 302          }
 303      }
 304
 305    template<typename _CharT, typename _Traits, typename _Alloc>
 306      basic_string<_CharT, _Traits, _Alloc>&
 307      basic_string<_CharT, _Traits, _Alloc>::
 308      insert(size_type __pos1, const basic_string& __str,
 309             size_type __pos2, size_type __n)
 310      {
 311        return this->insert(__pos1, __str._M_data()
 312                            + __str._M_check(__pos2, "basic_string::insert"),
 313                            __str._M_limit(__pos2, __n));
 314      }
 315
 316    template<typename _CharT, typename _Traits, typename _Alloc>
 317      basic_string<_CharT, _Traits, _Alloc>&
 318      basic_string<_CharT, _Traits, _Alloc>::
 319      insert(size_type __pos, const _CharT* __s, size_type __n)
 320      {
 321        __glibcxx_requires_string_len(__s, __n);
 322        __pos = _M_check(__pos, "basic_string::insert");
 323        if (this->max_size() - this->size() < __n)
 324          __throw_length_error("basic_string::insert");
 325        if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
 326            || less<const _CharT*>()(_M_data() + this->size(), __s))
 327          return _M_replace_safe(__pos, size_type(0), __s, __n);
 328        else
 329          {
 330            // Work in-place. If _M_mutate reallocates the string, __s
 331            // does not point anymore to valid data, therefore we save its
 332            // offset, then we restore it.
 333            const size_type __off = __s - _M_data();
 334            _M_mutate(__pos, 0, __n);
 335            __s = _M_data() + __off;
 336            _CharT* __p = _M_data() + __pos;
 337            if (__s  + __n <= __p)
 338              traits_type::copy(__p, __s, __n);
 339            else if (__s >= __p)
 340              traits_type::copy(__p, __s + __n, __n);
 341            else
 342              {
 343                traits_type::copy(__p, __s, __p - __s);
 344                traits_type::copy(__p + (__p-__s), __p + __n, __n - (__p-__s));
 345              }
 346            return *this;
 347          }
 348      }
 349
 350    template<typename _CharT, typename _Traits, typename _Alloc>
 351      basic_string<_CharT, _Traits, _Alloc>&
 352      basic_string<_CharT, _Traits, _Alloc>::
 353      replace(size_type __pos, size_type __n1, const _CharT* __s,
 354              size_type __n2)
 355      {
 356        __glibcxx_requires_string_len(__s, __n2);
 357        __pos = _M_check(__pos, "basic_string::replace");
 358        __n1 = _M_limit(__pos, __n1);
 359        if (this->max_size() - (this->size() - __n1) < __n2)
 360          __throw_length_error("basic_string::replace");
 361        if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
 362            || less<const _CharT*>()(_M_data() + this->size(), __s))
 363          return _M_replace_safe(__pos, __n1, __s, __n2);
 364        else
 365          {
 366            // Todo: optimized in-place replace.
 367            const basic_string __tmp(__s, __n2);
 368            return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2);
 369          }
 370      }
 371
 372   template<typename _CharT, typename _Traits, typename _Alloc>
 373     void
 374     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 375     _M_destroy(const _Alloc& __a) throw ()
 376     {
 377       if (this == &_S_empty_rep())
 378         return;
 379       const size_type __size = sizeof(_Rep_base) +
 380                                (this->_M_capacity + 1) * sizeof(_CharT);
 381       _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
 382     }
 383
 384   template<typename _CharT, typename _Traits, typename _Alloc>
 385     void
 386     basic_string<_CharT, _Traits, _Alloc>::_M_leak_hard()
 387     {
 388       if (_M_rep() == &_S_empty_rep())
 389         return;
 390       if (_M_rep()->_M_is_shared())
 391         _M_mutate(0, 0, 0);
 392       _M_rep()->_M_set_leaked();
 393     }
 394
 395   // _M_mutate and, below, _M_clone, include, in the same form, an exponential
 396   // growth policy, necessary to meet amortized linear time requirements of
 397   // the library: see http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
 398   // The policy is active for allocations requiring an amount of memory above
 399   // system pagesize. This is consistent with the requirements of the standard:
 400   // see, f.i., http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
 401   template<typename _CharT, typename _Traits, typename _Alloc>
 402     void
 403     basic_string<_CharT, _Traits, _Alloc>::
 404     _M_mutate(size_type __pos, size_type __len1, size_type __len2)
 405     {
 406       const size_type __old_size = this->size();
 407       const size_type __new_size = __old_size + __len2 - __len1;
 408       const _CharT*        __src = _M_data()  + __pos + __len1;
 409       const size_type __how_much = __old_size - __pos - __len1;
 410
 411       if (_M_rep() == &_S_empty_rep()
 412           || _M_rep()->_M_is_shared() || __new_size > capacity())
 413         {
 414           // Must reallocate.
 415           allocator_type __a = get_allocator();
 416           // See below (_S_create) for the meaning and value of these
 417           // constants.
 418           const size_type __pagesize = 4096;
 419           const size_type __malloc_header_size = 4 * sizeof (void*);
 420           // The biggest string which fits in a memory page
 421           const size_type __page_capacity = (__pagesize - __malloc_header_size
 422                                              - sizeof(_Rep) - sizeof(_CharT))
 423                                              / sizeof(_CharT);
 424           _Rep* __r;
 425           if (__new_size > capacity() && __new_size > __page_capacity)
 426             // Growing exponentially.
 427             __r = _Rep::_S_create(__new_size > 2*capacity() ?
 428                                   __new_size : 2*capacity(), __a);
 429           else
 430             __r = _Rep::_S_create(__new_size, __a);
 431
 432           if (__pos)
 433             traits_type::copy(__r->_M_refdata(), _M_data(), __pos);
 434           if (__how_much)
 435             traits_type::copy(__r->_M_refdata() + __pos + __len2,
 436                               __src, __how_much);
 437
 438           _M_rep()->_M_dispose(__a);
 439           _M_data(__r->_M_refdata());
 440         }
 441       else if (__how_much && __len1 != __len2)
 442         {
 443           // Work in-place
 444           traits_type::move(_M_data() + __pos + __len2, __src, __how_much);
 445         }
 446       _M_rep()->_M_set_sharable();
 447       _M_rep()->_M_length = __new_size;
 448       _M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4)
 449       // You cannot leave those LWG people alone for a second.
 450     }
 451
 452   template<typename _CharT, typename _Traits, typename _Alloc>
 453     void
 454     basic_string<_CharT, _Traits, _Alloc>::reserve(size_type __res)
 455     {
 456       if (__res != this->capacity() || _M_rep()->_M_is_shared())
 457         {
 458           if (__res > this->max_size())
 459             __throw_length_error("basic_string::reserve");
 460           // Make sure we don't shrink below the current size
 461           if (__res < this->size())
 462             __res = this->size();
 463           allocator_type __a = get_allocator();
 464           _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
 465           _M_rep()->_M_dispose(__a);
 466           _M_data(__tmp);
 467         }
 468     }
 469
 470   template<typename _CharT, typename _Traits, typename _Alloc>
 471     void basic_string<_CharT, _Traits, _Alloc>::swap(basic_string& __s)
 472     {
 473       if (_M_rep()->_M_is_leaked())
 474         _M_rep()->_M_set_sharable();
 475       if (__s._M_rep()->_M_is_leaked())
 476         __s._M_rep()->_M_set_sharable();
 477       if (this->get_allocator() == __s.get_allocator())
 478         {
 479           _CharT* __tmp = _M_data();
 480           _M_data(__s._M_data());
 481           __s._M_data(__tmp);
 482         }
 483       // The code below can usually be optimized away.
 484       else
 485         {
 486           basic_string __tmp1(_M_ibegin(), _M_iend(), __s.get_allocator());
 487           basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
 488                               this->get_allocator());
 489           *this = __tmp2;
 490           __s = __tmp1;
 491         }
 492     }
 493
 494   template<typename _CharT, typename _Traits, typename _Alloc>
 495     typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
 496     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 497     _S_create(size_t __capacity, const _Alloc& __alloc)
 498     {
 499       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 500       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 501       // 83.  String::npos vs. string::max_size()
 502       if (__capacity > _S_max_size)
 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_base);
 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           const 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_base);
 542         }
 543       else if (__size > __subpagesize)
 544         {
 545           const 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_base);
 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 = this->_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_base) - sizeof(_CharT))
 575         / sizeof(_CharT);
 576       _Rep* __r;
 577       if (__requested_cap > this->_M_capacity
 578           && __requested_cap > __page_capacity)
 579         // Growing exponentially.
 580         __r = _Rep::_S_create(__requested_cap > 2*this->_M_capacity ?
 581                               __requested_cap : 2*this->_M_capacity, __alloc);
 582       else
 583         __r = _Rep::_S_create(__requested_cap, __alloc);
 584
 585       if (this->_M_length)
 586         traits_type::copy(__r->_M_refdata(), _M_refdata(),
 587                           this->_M_length);
 588
 589       __r->_M_length = this->_M_length;
 590       __r->_M_refdata()[this->_M_length] = _Rep::_S_terminal;
 591       return __r->_M_refdata();
 592     }
 593
 594   template<typename _CharT, typename _Traits, typename _Alloc>
 595     void
 596     basic_string<_CharT, _Traits, _Alloc>::resize(size_type __n, _CharT __c)
 597     {
 598       if (__n > max_size())
 599         __throw_length_error("basic_string::resize");
 600       const size_type __size = this->size();
 601       if (__size < __n)
 602         this->append(__n - __size, __c);
 603       else if (__n < __size)
 604         this->erase(__n);
 605       // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
 606     }
 607
 608   template<typename _CharT, typename _Traits, typename _Alloc>
 609     basic_string<_CharT, _Traits, _Alloc>&
 610     basic_string<_CharT, _Traits, _Alloc>::
 611     _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
 612                    _CharT __c)
 613     {
 614       if (this->max_size() - (this->size() - __n1) < __n2)
 615         __throw_length_error("basic_string::_M_replace_aux");
 616       _M_mutate(__pos1, __n1, __n2);
 617       if (__n2)
 618         traits_type::assign(_M_data() + __pos1, __n2, __c);
 619       return *this;
 620     }
 621
 622   // This is the general replace helper. It buffers internally and then calls
 623   // _M_replace_safe.
 624   template<typename _CharT, typename _Traits, typename _Alloc>
 625     template<typename _InputIterator>
 626       basic_string<_CharT, _Traits, _Alloc>&
 627       basic_string<_CharT, _Traits, _Alloc>::
 628       _M_replace(iterator __i1, iterator __i2, _InputIterator __k1,
 629                  _InputIterator __k2)
 630       {
 631         const basic_string __s(__k1, __k2);
 632         const size_type __n1 = __i2 - __i1;
 633         if (this->max_size() - (this->size() - __n1) < __s.size())
 634           __throw_length_error("basic_string::_M_replace");
 635         return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(),
 636                                __s.size());
 637       }
 638
 639   // This helper doesn't buffer internally and can be used in "safe" situations,
 640   // i.e., when source and destination ranges are known to not overlap.
 641   template<typename _CharT, typename _Traits, typename _Alloc>
 642     basic_string<_CharT, _Traits, _Alloc>&
 643     basic_string<_CharT, _Traits, _Alloc>::
 644     _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
 645                     size_type __n2)
 646     {
 647       _M_mutate(__pos1, __n1, __n2);
 648       if (__n2)
 649         traits_type::copy(_M_data() + __pos1, __s, __n2);
 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       return this->replace(__pos1, __n1, __str._M_data()
 660                            + __str._M_check(__pos2, "basic_string::replace"),
 661                            __str._M_limit(__pos2, __n2));
 662     }
 663
 664   template<typename _CharT, typename _Traits, typename _Alloc>
 665     basic_string<_CharT, _Traits, _Alloc>&
 666     basic_string<_CharT, _Traits, _Alloc>::
 667     append(const basic_string& __str)
 668     {
 669       // Iff appending itself, string needs to pre-reserve the
 670       // correct size so that _M_mutate does not clobber the
 671       // pointer __str._M_data() formed here.
 672       const size_type __size = __str.size();
 673       const size_type __len = __size + this->size();
 674       if (__len > this->capacity())
 675         this->reserve(__len);
 676       return _M_replace_safe(this->size(), size_type(0), __str._M_data(),
 677                              __str.size());
 678     }
 679
 680   template<typename _CharT, typename _Traits, typename _Alloc>
 681     basic_string<_CharT, _Traits, _Alloc>&
 682     basic_string<_CharT, _Traits, _Alloc>::
 683     append(const basic_string& __str, size_type __pos, size_type __n)
 684     {
 685       // Iff appending itself, string needs to pre-reserve the
 686       // correct size so that _M_mutate does not clobber the
 687       // pointer __str._M_data() formed here.
 688       __pos = __str._M_check(__pos, "basic_string::append");
 689       __n = __str._M_limit(__pos, __n);
 690       const size_type __len = __n + this->size();
 691       if (__len > this->capacity())
 692         this->reserve(__len);
 693       return _M_replace_safe(this->size(), size_type(0), __str._M_data()
 694                              + __pos, __n);
 695     }
 696
 697   template<typename _CharT, typename _Traits, typename _Alloc>
 698     basic_string<_CharT, _Traits, _Alloc>&
 699     basic_string<_CharT, _Traits, _Alloc>::
 700     append(const _CharT* __s, size_type __n)
 701     {
 702       __glibcxx_requires_string_len(__s, __n);
 703       const size_type __len = __n + this->size();
 704       if (__len > this->capacity())
 705         this->reserve(__len);
 706       return _M_replace_safe(this->size(), size_type(0), __s, __n);
 707     }
 708
 709   template<typename _CharT, typename _Traits, typename _Alloc>
 710     basic_string<_CharT, _Traits, _Alloc>
 711     operator+(const _CharT* __lhs,
 712               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 713     {
 714       __glibcxx_requires_string(__lhs);
 715       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 716       typedef typename __string_type::size_type   __size_type;
 717       const __size_type __len = _Traits::length(__lhs);
 718       __string_type __str;
 719       __str.reserve(__len + __rhs.size());
 720       __str.append(__lhs, __lhs + __len);
 721       __str.append(__rhs);
 722       return __str;
 723     }
 724
 725   template<typename _CharT, typename _Traits, typename _Alloc>
 726     basic_string<_CharT, _Traits, _Alloc>
 727     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 728     {
 729       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 730       typedef typename __string_type::size_type   __size_type;
 731       __string_type __str;
 732       const __size_type __len = __rhs.size();
 733       __str.reserve(__len + 1);
 734       __str.append(__size_type(1), __lhs);
 735       __str.append(__rhs);
 736       return __str;
 737     }
 738
 739   template<typename _CharT, typename _Traits, typename _Alloc>
 740     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 741     basic_string<_CharT, _Traits, _Alloc>::
 742     copy(_CharT* __s, size_type __n, size_type __pos) const
 743     {
 744       __pos = _M_check(__pos, "basic_string::copy");
 745       __n = _M_limit(__pos, __n);
 746       __glibcxx_requires_string_len(__s, __n);
 747       if (__n)
 748         traits_type::copy(__s, _M_data() + __pos, __n);
 749       // 21.3.5.7 par 3: do not append null.  (good.)
 750       return __n;
 751     }
 752
 753   template<typename _CharT, typename _Traits, typename _Alloc>
 754     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 755     basic_string<_CharT, _Traits, _Alloc>::
 756     find(const _CharT* __s, size_type __pos, size_type __n) const
 757     {
 758       __glibcxx_requires_string_len(__s, __n);
 759
 760       const size_type __size = this->size();
 761       size_t __xpos = __pos;
 762       const _CharT* __data = _M_data();
 763       for (; __xpos + __n <= __size; ++__xpos)
 764         if (traits_type::compare(__data + __xpos, __s, __n) == 0)
 765           return __xpos;
 766       return npos;
 767     }
 768
 769   template<typename _CharT, typename _Traits, typename _Alloc>
 770     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 771     basic_string<_CharT, _Traits, _Alloc>::
 772     find(_CharT __c, size_type __pos) const
 773     {
 774       const size_type __size = this->size();
 775       size_type __ret = npos;
 776       if (__pos < __size)
 777         {
 778           const _CharT* __data = _M_data();
 779           const size_type __n = __size - __pos;
 780           const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
 781           if (__p)
 782             __ret = __p - __data;
 783         }
 784       return __ret;
 785     }
 786
 787   template<typename _CharT, typename _Traits, typename _Alloc>
 788     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 789     basic_string<_CharT, _Traits, _Alloc>::
 790     rfind(const _CharT* __s, size_type __pos, size_type __n) const
 791     {
 792       __glibcxx_requires_string_len(__s, __n);
 793
 794       const size_type __size = this->size();
 795       if (__n <= __size)
 796         {
 797           __pos = std::min(size_type(__size - __n), __pos);
 798           const _CharT* __data = _M_data();
 799           do
 800             {
 801               if (traits_type::compare(__data + __pos, __s, __n) == 0)
 802                 return __pos;
 803             }
 804           while (__pos-- > 0);
 805         }
 806       return npos;
 807     }
 808
 809   template<typename _CharT, typename _Traits, typename _Alloc>
 810     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 811     basic_string<_CharT, _Traits, _Alloc>::
 812     rfind(_CharT __c, size_type __pos) const
 813     {
 814       const size_type __size = this->size();
 815       if (__size)
 816         {
 817           size_t __xpos = __size - 1;
 818           if (__xpos > __pos)
 819             __xpos = __pos;
 820
 821           for (++__xpos; __xpos-- > 0; )
 822             if (traits_type::eq(_M_data()[__xpos], __c))
 823               return __xpos;
 824         }
 825       return npos;
 826     }
 827
 828   template<typename _CharT, typename _Traits, typename _Alloc>
 829     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 830     basic_string<_CharT, _Traits, _Alloc>::
 831     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
 832     {
 833       __glibcxx_requires_string_len(__s, __n);
 834
 835       for (; __n && __pos < this->size(); ++__pos)
 836         {
 837           const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
 838           if (__p)
 839             return __pos;
 840         }
 841       return npos;
 842     }
 843
 844   template<typename _CharT, typename _Traits, typename _Alloc>
 845     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 846     basic_string<_CharT, _Traits, _Alloc>::
 847     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
 848     {
 849       __glibcxx_requires_string_len(__s, __n);
 850
 851       size_type __size = this->size();
 852       if (__size && __n)
 853         {
 854           if (--__size > __pos)
 855             __size = __pos;
 856           do
 857             {
 858               if (traits_type::find(__s, __n, _M_data()[__size]))
 859                 return __size;
 860             }
 861           while (__size-- != 0);
 862         }
 863       return npos;
 864     }
 865
 866   template<typename _CharT, typename _Traits, typename _Alloc>
 867     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 868     basic_string<_CharT, _Traits, _Alloc>::
 869     find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
 870     {
 871       __glibcxx_requires_string_len(__s, __n);
 872
 873       size_t __xpos = __pos;
 874       for (; __xpos < this->size(); ++__xpos)
 875         if (!traits_type::find(__s, __n, _M_data()[__xpos]))
 876           return __xpos;
 877       return npos;
 878     }
 879
 880   template<typename _CharT, typename _Traits, typename _Alloc>
 881     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 882     basic_string<_CharT, _Traits, _Alloc>::
 883     find_first_not_of(_CharT __c, size_type __pos) const
 884     {
 885       size_t __xpos = __pos;
 886       for (; __xpos < this->size(); ++__xpos)
 887         if (!traits_type::eq(_M_data()[__xpos], __c))
 888           return __xpos;
 889       return npos;
 890     }
 891
 892   template<typename _CharT, typename _Traits, typename _Alloc>
 893     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 894     basic_string<_CharT, _Traits, _Alloc>::
 895     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
 896     {
 897       __glibcxx_requires_string_len(__s, __n);
 898
 899       size_type __size = this->size();
 900       if (__size)
 901         {
 902           if (--__size > __pos)
 903             __size = __pos;
 904           do
 905             {
 906               if (!traits_type::find(__s, __n, _M_data()[__size]))
 907                 return __size;
 908             }
 909           while (__size--);
 910         }
 911       return npos;
 912     }
 913
 914   template<typename _CharT, typename _Traits, typename _Alloc>
 915     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 916     basic_string<_CharT, _Traits, _Alloc>::
 917     find_last_not_of(_CharT __c, size_type __pos) const
 918     {
 919       size_type __size = this->size();
 920       if (__size)
 921         {
 922           if (--__size > __pos)
 923             __size = __pos;
 924           do
 925             {
 926               if (!traits_type::eq(_M_data()[__size], __c))
 927                 return __size;
 928             }
 929           while (__size--);
 930         }
 931       return npos;
 932     }
 933
 934   template<typename _CharT, typename _Traits, typename _Alloc>
 935     int
 936     basic_string<_CharT, _Traits, _Alloc>::
 937     compare(size_type __pos, size_type __n, const basic_string& __str) const
 938     {
 939       __pos = _M_check(__pos, "basic_string::compare");
 940       __n = _M_limit(__pos, __n);
 941       const size_type __osize = __str.size();
 942       const size_type __len = std::min(__n, __osize);
 943       int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
 944       if (!__r)
 945         __r = __n - __osize;
 946       return __r;
 947     }
 948
 949   template<typename _CharT, typename _Traits, typename _Alloc>
 950     int
 951     basic_string<_CharT, _Traits, _Alloc>::
 952     compare(size_type __pos1, size_type __n1, const basic_string& __str,
 953             size_type __pos2, size_type __n2) const
 954     {
 955       __pos1 = _M_check(__pos1, "basic_string::compare");
 956       __pos2 = __str._M_check(__pos2, "basic_string::compare");
 957       __n1 = _M_limit(__pos1, __n1);
 958       __n2 = __str._M_limit(__pos2, __n2);
 959       const size_type __len = std::min(__n1, __n2);
 960       int __r = traits_type::compare(_M_data() + __pos1,
 961                                      __str.data() + __pos2, __len);
 962       if (!__r)
 963         __r = __n1 - __n2;
 964       return __r;
 965     }
 966
 967   template<typename _CharT, typename _Traits, typename _Alloc>
 968     int
 969     basic_string<_CharT, _Traits, _Alloc>::
 970     compare(const _CharT* __s) const
 971     {
 972       __glibcxx_requires_string(__s);
 973       const size_type __size = this->size();
 974       const size_type __osize = traits_type::length(__s);
 975       const size_type __len = std::min(__size, __osize);
 976       int __r = traits_type::compare(_M_data(), __s, __len);
 977       if (!__r)
 978         __r = __size - __osize;
 979       return __r;
 980     }
 981
 982   template<typename _CharT, typename _Traits, typename _Alloc>
 983     int
 984     basic_string <_CharT, _Traits, _Alloc>::
 985     compare(size_type __pos, size_type __n1, const _CharT* __s) const
 986     {
 987       __glibcxx_requires_string(__s);
 988       __pos = _M_check(__pos, "basic_string::compare");
 989       __n1 = _M_limit(__pos, __n1);
 990       const size_type __osize = traits_type::length(__s);
 991       const size_type __len = std::min(__n1, __osize);
 992       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
 993       if (!__r)
 994         __r = __n1 - __osize;
 995       return __r;
 996     }
 997
 998   template<typename _CharT, typename _Traits, typename _Alloc>
 999     int
1000     basic_string <_CharT, _Traits, _Alloc>::
1001     compare(size_type __pos, size_type __n1, const _CharT* __s,
1002             size_type __n2) const
1003     {
1004       __glibcxx_requires_string_len(__s, __n2);
1005       __pos = _M_check(__pos, "basic_string::compare");
1006       __n1 = _M_limit(__pos, __n1);
1007       const size_type __len = std::min(__n1, __n2);
1008       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
1009       if (!__r)
1010         __r = __n1 - __n2;
1011       return __r;
1012     }
1013
1014   // Inhibit implicit instantiations for required instantiations,
1015   // which are defined via explicit instantiations elsewhere.
1016   // NB: This syntax is a GNU extension.
1017 #if _GLIBCXX_EXTERN_TEMPLATE
1018   extern template class basic_string<char>;
1019   extern template
1020     basic_istream<char>&
1021     operator>>(basic_istream<char>&, string&);
1022   extern template
1023     basic_ostream<char>&
1024     operator<<(basic_ostream<char>&, const string&);
1025   extern template
1026     basic_istream<char>&
1027     getline(basic_istream<char>&, string&, char);
1028   extern template
1029     basic_istream<char>&
1030     getline(basic_istream<char>&, string&);
1031
1032 #ifdef _GLIBCXX_USE_WCHAR_T
1033   extern template class basic_string<wchar_t>;
1034   extern template
1035     basic_istream<wchar_t>&
1036     operator>>(basic_istream<wchar_t>&, wstring&);
1037   extern template
1038     basic_ostream<wchar_t>&
1039     operator<<(basic_ostream<wchar_t>&, const wstring&);
1040   extern template
1041     basic_istream<wchar_t>&
1042     getline(basic_istream<wchar_t>&, wstring&, wchar_t);
1043   extern template
1044     basic_istream<wchar_t>&
1045     getline(basic_istream<wchar_t>&, wstring&);
1046 #endif
1047 #endif
1048 } // namespace std
1049
1050 #endif