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_check(__pos),
 210                                __str._M_fold(__pos, __n), _Alloc()), _Alloc())
 211     { }
 212
 213   template<typename _CharT, typename _Traits, typename _Alloc>
 214     basic_string<_CharT, _Traits, _Alloc>::
 215     basic_string(const basic_string& __str, size_type __pos,
 216                  size_type __n, const _Alloc& __a)
 217     : _M_dataplus(_S_construct(__str._M_check(__pos),
 218                                __str._M_fold(__pos, __n), __a), __a)
 219     { }
 220
 221   // TBD: DPG annotate
 222   template<typename _CharT, typename _Traits, typename _Alloc>
 223     basic_string<_CharT, _Traits, _Alloc>::
 224     basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
 225     : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
 226     { }
 227
 228   // TBD: DPG annotate
 229   template<typename _CharT, typename _Traits, typename _Alloc>
 230     basic_string<_CharT, _Traits, _Alloc>::
 231     basic_string(const _CharT* __s, const _Alloc& __a)
 232     : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) :
 233                                __s + npos, __a), __a)
 234     { }
 235
 236   template<typename _CharT, typename _Traits, typename _Alloc>
 237     basic_string<_CharT, _Traits, _Alloc>::
 238     basic_string(size_type __n, _CharT __c, const _Alloc& __a)
 239     : _M_dataplus(_S_construct(__n, __c, __a), __a)
 240     { }
 241
 242   // TBD: DPG annotate
 243   template<typename _CharT, typename _Traits, typename _Alloc>
 244     template<typename _InputIterator>
 245     basic_string<_CharT, _Traits, _Alloc>::
 246     basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a)
 247     : _M_dataplus(_S_construct(__beg, __end, __a), __a)
 248     { }
 249
 250   template<typename _CharT, typename _Traits, typename _Alloc>
 251     basic_string<_CharT, _Traits, _Alloc>&
 252     basic_string<_CharT, _Traits, _Alloc>::
 253     assign(const basic_string& __str)
 254     {
 255       if (_M_rep() != __str._M_rep())
 256         {
 257           // XXX MT
 258           allocator_type __a = this->get_allocator();
 259           _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
 260           _M_rep()->_M_dispose(__a);
 261           _M_data(__tmp);
 262         }
 263       return *this;
 264     }
 265
 266    template<typename _CharT, typename _Traits, typename _Alloc>
 267      basic_string<_CharT, _Traits, _Alloc>&
 268      basic_string<_CharT, _Traits, _Alloc>::
 269      assign(const basic_string& __str, size_type __pos, size_type __n)
 270      {
 271        const size_type __strsize = __str.size();
 272        if (__pos > __strsize)
 273          __throw_out_of_range("basic_string::assign");
 274        const bool __testn = __n < __strsize - __pos;
 275        const size_type __newsize = __testn ? __n : __strsize - __pos;
 276        return this->assign(__str._M_data() + __pos, __newsize);
 277      }
 278
 279    template<typename _CharT, typename _Traits, typename _Alloc>
 280      basic_string<_CharT, _Traits, _Alloc>&
 281      basic_string<_CharT, _Traits, _Alloc>::
 282      assign(const _CharT* __s, size_type __n)
 283      {
 284        __glibcxx_requires_string_len(__s, __n);
 285        if (__n > this->max_size())
 286          __throw_length_error("basic_string::assign");
 287        if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
 288            || less<const _CharT*>()(_M_data() + this->size(), __s))
 289          return _M_replace_safe(_M_ibegin(), _M_iend(), __s, __s + __n);
 290        else
 291          {
 292            // Work in-place
 293            const size_type __pos = __s - _M_data();
 294            if (__pos >= __n)
 295              traits_type::copy(_M_data(), __s, __n);
 296            else if (__pos)
 297              traits_type::move(_M_data(), __s, __n);
 298            _M_rep()->_M_length = __n;
 299            _M_data()[__n] = _Rep::_S_terminal;  // grr.
 300            return *this;
 301          }
 302      }
 303
 304    template<typename _CharT, typename _Traits, typename _Alloc>
 305      basic_string<_CharT, _Traits, _Alloc>&
 306      basic_string<_CharT, _Traits, _Alloc>::
 307      insert(size_type __pos1, const basic_string& __str,
 308             size_type __pos2, size_type __n)
 309      {
 310        const size_type __strsize = __str.size();
 311        if (__pos2 > __strsize)
 312          __throw_out_of_range("basic_string::insert");
 313        const bool __testn = __n < __strsize - __pos2;
 314        const size_type __newsize = __testn ? __n : __strsize - __pos2;
 315        return this->insert(__pos1, __str._M_data() + __pos2, __newsize);
 316      }
 317
 318    template<typename _CharT, typename _Traits, typename _Alloc>
 319      basic_string<_CharT, _Traits, _Alloc>&
 320      basic_string<_CharT, _Traits, _Alloc>::
 321      insert(size_type __pos, const _CharT* __s, size_type __n)
 322      {
 323        __glibcxx_requires_string_len(__s, __n);
 324        const size_type __size = this->size();
 325        if (__pos > __size)
 326          __throw_out_of_range("basic_string::insert");
 327        if (__size > this->max_size() - __n)
 328          __throw_length_error("basic_string::insert");
 329        if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
 330            || less<const _CharT*>()(_M_data() + __size, __s))
 331          return _M_replace_safe(_M_ibegin() + __pos, _M_ibegin() + __pos,
 332                                 __s, __s + __n);
 333        else
 334          {
 335            // Work in-place. If _M_mutate reallocates the string, __s
 336            // does not point anymore to valid data, therefore we save its
 337            // offset, then we restore it.
 338            const size_type __off = __s - _M_data();
 339            _M_mutate(__pos, 0, __n);
 340            __s = _M_data() + __off;
 341            _CharT* __p = _M_data() + __pos;
 342            if (__s  + __n <= __p)
 343              traits_type::copy(__p, __s, __n);
 344            else if (__s >= __p)
 345              traits_type::copy(__p, __s + __n, __n);
 346            else
 347              {
 348                traits_type::copy(__p, __s, __p - __s);
 349                traits_type::copy(__p + (__p-__s), __p + __n, __n - (__p-__s));
 350              }
 351            return *this;
 352          }
 353      }
 354
 355    template<typename _CharT, typename _Traits, typename _Alloc>
 356      basic_string<_CharT, _Traits, _Alloc>&
 357      basic_string<_CharT, _Traits, _Alloc>::
 358      replace(size_type __pos, size_type __n1, const _CharT* __s,
 359              size_type __n2)
 360      {
 361        __glibcxx_requires_string_len(__s, __n2);
 362        const size_type __size = this->size();
 363        if (__pos > __size)
 364          __throw_out_of_range("basic_string::replace");
 365        const bool __testn1 = __n1 < __size - __pos;
 366        const size_type __foldn1 = __testn1 ? __n1 : __size - __pos;
 367        if (__size - __foldn1 > this->max_size() - __n2)
 368          __throw_length_error("basic_string::replace");
 369        if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data())
 370            || less<const _CharT*>()(_M_data() + __size, __s))
 371          return _M_replace_safe(_M_ibegin() + __pos,
 372                                 _M_ibegin() + __pos + __foldn1, __s, __s + __n2);
 373        // Todo: optimized in-place replace.
 374        else
 375          return _M_replace(_M_ibegin() + __pos, _M_ibegin() + __pos + __foldn1,
 376                            __s, __s + __n2);
 377      }
 378
 379   template<typename _CharT, typename _Traits, typename _Alloc>
 380     void
 381     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 382     _M_destroy(const _Alloc& __a) throw ()
 383     {
 384       if (this == &_S_empty_rep())
 385         return;
 386       const size_type __size = sizeof(_Rep_base) +
 387                                (this->_M_capacity + 1) * sizeof(_CharT);
 388       _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
 389     }
 390
 391   template<typename _CharT, typename _Traits, typename _Alloc>
 392     void
 393     basic_string<_CharT, _Traits, _Alloc>::_M_leak_hard()
 394     {
 395       if (_M_rep() == &_S_empty_rep())
 396         return;
 397       if (_M_rep()->_M_is_shared())
 398         _M_mutate(0, 0, 0);
 399       _M_rep()->_M_set_leaked();
 400     }
 401
 402   // _M_mutate and, below, _M_clone, include, in the same form, an exponential
 403   // growth policy, necessary to meet amortized linear time requirements of
 404   // the library: see http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
 405   // The policy is active for allocations requiring an amount of memory above
 406   // system pagesize. This is consistent with the requirements of the standard:
 407   // see, f.i., http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
 408   template<typename _CharT, typename _Traits, typename _Alloc>
 409     void
 410     basic_string<_CharT, _Traits, _Alloc>::
 411     _M_mutate(size_type __pos, size_type __len1, size_type __len2)
 412     {
 413       const size_type __old_size = this->size();
 414       const size_type __new_size = __old_size + __len2 - __len1;
 415       const _CharT*        __src = _M_data()  + __pos + __len1;
 416       const size_type __how_much = __old_size - __pos - __len1;
 417
 418       if (_M_rep() == &_S_empty_rep()
 419           || _M_rep()->_M_is_shared() || __new_size > capacity())
 420         {
 421           // Must reallocate.
 422           allocator_type __a = get_allocator();
 423           // See below (_S_create) for the meaning and value of these
 424           // constants.
 425           const size_type __pagesize = 4096;
 426           const size_type __malloc_header_size = 4 * sizeof (void*);
 427           // The biggest string which fits in a memory page
 428           const size_type __page_capacity = (__pagesize - __malloc_header_size
 429                                              - sizeof(_Rep) - sizeof(_CharT))
 430                                              / sizeof(_CharT);
 431           _Rep* __r;
 432           if (__new_size > capacity() && __new_size > __page_capacity)
 433             // Growing exponentially.
 434             __r = _Rep::_S_create(__new_size > 2*capacity() ?
 435                                   __new_size : 2*capacity(), __a);
 436           else
 437             __r = _Rep::_S_create(__new_size, __a);
 438
 439           if (__pos)
 440             traits_type::copy(__r->_M_refdata(), _M_data(), __pos);
 441           if (__how_much)
 442             traits_type::copy(__r->_M_refdata() + __pos + __len2,
 443                               __src, __how_much);
 444
 445           _M_rep()->_M_dispose(__a);
 446           _M_data(__r->_M_refdata());
 447         }
 448       else if (__how_much && __len1 != __len2)
 449         {
 450           // Work in-place
 451           traits_type::move(_M_data() + __pos + __len2, __src, __how_much);
 452         }
 453       _M_rep()->_M_set_sharable();
 454       _M_rep()->_M_length = __new_size;
 455       _M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4)
 456       // You cannot leave those LWG people alone for a second.
 457     }
 458
 459   template<typename _CharT, typename _Traits, typename _Alloc>
 460     void
 461     basic_string<_CharT, _Traits, _Alloc>::reserve(size_type __res)
 462     {
 463       if (__res != this->capacity() || _M_rep()->_M_is_shared())
 464         {
 465           if (__res > this->max_size())
 466             __throw_length_error("basic_string::reserve");
 467           // Make sure we don't shrink below the current size
 468           if (__res < this->size())
 469             __res = this->size();
 470           allocator_type __a = get_allocator();
 471           _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
 472           _M_rep()->_M_dispose(__a);
 473           _M_data(__tmp);
 474         }
 475     }
 476
 477   template<typename _CharT, typename _Traits, typename _Alloc>
 478     void basic_string<_CharT, _Traits, _Alloc>::swap(basic_string& __s)
 479     {
 480       if (_M_rep()->_M_is_leaked())
 481         _M_rep()->_M_set_sharable();
 482       if (__s._M_rep()->_M_is_leaked())
 483         __s._M_rep()->_M_set_sharable();
 484       if (this->get_allocator() == __s.get_allocator())
 485         {
 486           _CharT* __tmp = _M_data();
 487           _M_data(__s._M_data());
 488           __s._M_data(__tmp);
 489         }
 490       // The code below can usually be optimized away.
 491       else
 492         {
 493           basic_string __tmp1(_M_ibegin(), _M_iend(), __s.get_allocator());
 494           basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
 495                               this->get_allocator());
 496           *this = __tmp2;
 497           __s = __tmp1;
 498         }
 499     }
 500
 501   template<typename _CharT, typename _Traits, typename _Alloc>
 502     typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
 503     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 504     _S_create(size_t __capacity, const _Alloc& __alloc)
 505     {
 506       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 507       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 508       // 83.  String::npos vs. string::max_size()
 509       if (__capacity > _S_max_size)
 510         __throw_length_error("basic_string::_S_create");
 511
 512       // NB: Need an array of char_type[__capacity], plus a
 513       // terminating null char_type() element, plus enough for the
 514       // _Rep data structure. Whew. Seemingly so needy, yet so elemental.
 515       size_t __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep_base);
 516
 517       // The standard places no restriction on allocating more memory
 518       // than is strictly needed within this layer at the moment or as
 519       // requested by an explicit application call to reserve().  Many
 520       // malloc implementations perform quite poorly when an
 521       // application attempts to allocate memory in a stepwise fashion
 522       // growing each allocation size by only 1 char.  Additionally,
 523       // it makes little sense to allocate less linear memory than the
 524       // natural blocking size of the malloc implementation.
 525       // Unfortunately, we would need a somewhat low-level calculation
 526       // with tuned parameters to get this perfect for any particular
 527       // malloc implementation.  Fortunately, generalizations about
 528       // common features seen among implementations seems to suffice.
 529
 530       // __pagesize need not match the actual VM page size for good
 531       // results in practice, thus we pick a common value on the low
 532       // side.  __malloc_header_size is an estimate of the amount of
 533       // overhead per memory allocation (in practice seen N * sizeof
 534       // (void*) where N is 0, 2 or 4).  According to folklore,
 535       // picking this value on the high side is better than
 536       // low-balling it (especially when this algorithm is used with
 537       // malloc implementations that allocate memory blocks rounded up
 538       // to a size which is a power of 2).
 539       const size_t __pagesize = 4096; // must be 2^i * __subpagesize
 540       const size_t __subpagesize = 128; // should be >> __malloc_header_size
 541       const size_t __malloc_header_size = 4 * sizeof (void*);
 542       if ((__size + __malloc_header_size) > __pagesize)
 543         {
 544           const size_t __extra =
 545             (__pagesize - ((__size + __malloc_header_size) % __pagesize))
 546             % __pagesize;
 547           __capacity += __extra / sizeof(_CharT);
 548           __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep_base);
 549         }
 550       else if (__size > __subpagesize)
 551         {
 552           const size_t __extra =
 553             (__subpagesize - ((__size + __malloc_header_size) % __subpagesize))
 554             % __subpagesize;
 555           __capacity += __extra / sizeof(_CharT);
 556           __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep_base);
 557         }
 558
 559       // NB: Might throw, but no worries about a leak, mate: _Rep()
 560       // does not throw.
 561       void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
 562       _Rep *__p = new (__place) _Rep;
 563       __p->_M_capacity = __capacity;
 564       __p->_M_set_sharable();  // One reference.
 565       __p->_M_length = 0;
 566       return __p;
 567     }
 568
 569   template<typename _CharT, typename _Traits, typename _Alloc>
 570     _CharT*
 571     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 572     _M_clone(const _Alloc& __alloc, size_type __res)
 573     {
 574       // Requested capacity of the clone.
 575       const size_type __requested_cap = this->_M_length + __res;
 576       // See above (_S_create) for the meaning and value of these constants.
 577       const size_type __pagesize = 4096;
 578       const size_type __malloc_header_size = 4 * sizeof (void*);
 579       // The biggest string which fits in a memory page.
 580       const size_type __page_capacity =
 581         (__pagesize - __malloc_header_size - sizeof(_Rep_base) - sizeof(_CharT))
 582         / sizeof(_CharT);
 583       _Rep* __r;
 584       if (__requested_cap > this->_M_capacity
 585           && __requested_cap > __page_capacity)
 586         // Growing exponentially.
 587         __r = _Rep::_S_create(__requested_cap > 2*this->_M_capacity ?
 588                               __requested_cap : 2*this->_M_capacity, __alloc);
 589       else
 590         __r = _Rep::_S_create(__requested_cap, __alloc);
 591
 592       if (this->_M_length)
 593         traits_type::copy(__r->_M_refdata(), _M_refdata(),
 594                           this->_M_length);
 595
 596       __r->_M_length = this->_M_length;
 597       __r->_M_refdata()[this->_M_length] = _Rep::_S_terminal;
 598       return __r->_M_refdata();
 599     }
 600
 601   template<typename _CharT, typename _Traits, typename _Alloc>
 602     void
 603     basic_string<_CharT, _Traits, _Alloc>::resize(size_type __n, _CharT __c)
 604     {
 605       if (__n > max_size())
 606         __throw_length_error("basic_string::resize");
 607       const size_type __size = this->size();
 608       if (__size < __n)
 609         this->append(__n - __size, __c);
 610       else if (__n < __size)
 611         this->erase(__n);
 612       // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
 613     }
 614
 615   template<typename _CharT, typename _Traits, typename _Alloc>
 616     basic_string<_CharT, _Traits, _Alloc>&
 617     basic_string<_CharT, _Traits, _Alloc>::
 618     _M_replace_aux(iterator __i1, iterator __i2, size_type __n2, _CharT __c)
 619     {
 620       const size_type __n1 = __i2 - __i1;
 621       const size_type __off1 = __i1 - _M_ibegin();
 622       if (max_size() - (this->size() - __n1) <= __n2)
 623         __throw_length_error("basic_string::_M_replace_aux");
 624       _M_mutate(__off1, __n1, __n2);
 625       // Invalidated __i1, __i2
 626       if (__n2)
 627         traits_type::assign(_M_data() + __off1, __n2, __c);
 628       return *this;
 629     }
 630
 631   // This is the general replace helper. It buffers internally and then calls
 632   // _M_replace_safe.
 633   template<typename _CharT, typename _Traits, typename _Alloc>
 634     template<typename _InputIterator>
 635       basic_string<_CharT, _Traits, _Alloc>&
 636       basic_string<_CharT, _Traits, _Alloc>::
 637       _M_replace(iterator __i1, iterator __i2, _InputIterator __k1,
 638                  _InputIterator __k2)
 639       {
 640         // Save concerned source string data in a temporary.
 641         const basic_string __s(__k1, __k2);
 642         return _M_replace_safe(__i1, __i2, __s._M_ibegin(), __s._M_iend());
 643       }
 644
 645   // This is a special replace helper, which does not buffer internally
 646   // and can be used in "safe" situations involving forward iterators,
 647   // i.e., when source and destination ranges are known to not overlap.
 648   template<typename _CharT, typename _Traits, typename _Alloc>
 649     template<typename _ForwardIterator>
 650       basic_string<_CharT, _Traits, _Alloc>&
 651       basic_string<_CharT, _Traits, _Alloc>::
 652       _M_replace_safe(iterator __i1, iterator __i2, _ForwardIterator __k1,
 653                       _ForwardIterator __k2)
 654       {
 655         const size_type __dnew = static_cast<size_type>(std::distance(__k1, __k2));
 656         const size_type __dold = __i2 - __i1;
 657         const size_type __dmax = this->max_size();
 658
 659         if (__dmax <= __dnew)
 660           __throw_length_error("basic_string::_M_replace_safe");
 661         const size_type __off = __i1 - _M_ibegin();
 662         _M_mutate(__off, __dold, __dnew);
 663
 664         // Invalidated __i1, __i2
 665         if (__dnew)
 666           _S_copy_chars(_M_data() + __off, __k1, __k2);
 667
 668         return *this;
 669       }
 670
 671   template<typename _CharT, typename _Traits, typename _Alloc>
 672     basic_string<_CharT, _Traits, _Alloc>&
 673     basic_string<_CharT, _Traits, _Alloc>::
 674     replace(size_type __pos1, size_type __n1, const basic_string& __str,
 675             size_type __pos2, size_type __n2)
 676     {
 677       const size_type __strsize = __str.size();
 678       if (__pos2 > __strsize)
 679         __throw_out_of_range("basic_string::replace");
 680       const bool __testn2 = __n2 < __strsize - __pos2;
 681       const size_type __foldn2 = __testn2 ? __n2 : __strsize - __pos2;
 682       return this->replace(__pos1, __n1,
 683                            __str._M_data() + __pos2, __foldn2);
 684     }
 685
 686   template<typename _CharT, typename _Traits, typename _Alloc>
 687     basic_string<_CharT, _Traits, _Alloc>&
 688     basic_string<_CharT, _Traits, _Alloc>::
 689     append(const basic_string& __str)
 690     {
 691       // Iff appending itself, string needs to pre-reserve the
 692       // correct size so that _M_mutate does not clobber the
 693       // iterators formed here.
 694       const size_type __size = __str.size();
 695       const size_type __len = __size + this->size();
 696       if (__len > this->capacity())
 697         this->reserve(__len);
 698       return _M_replace_safe(_M_iend(), _M_iend(), __str._M_ibegin(),
 699                              __str._M_iend());
 700     }
 701
 702   template<typename _CharT, typename _Traits, typename _Alloc>
 703     basic_string<_CharT, _Traits, _Alloc>&
 704     basic_string<_CharT, _Traits, _Alloc>::
 705     append(const basic_string& __str, size_type __pos, size_type __n)
 706     {
 707       // Iff appending itself, string needs to pre-reserve the
 708       // correct size so that _M_mutate does not clobber the
 709       // iterators formed here.
 710       const size_type __len = std::min(size_type(__str.size() - __pos),
 711                                        __n) + this->size();
 712       if (__len > this->capacity())
 713         this->reserve(__len);
 714       return _M_replace_safe(_M_iend(), _M_iend(), __str._M_check(__pos),
 715                              __str._M_fold(__pos, __n));
 716     }
 717
 718   template<typename _CharT, typename _Traits, typename _Alloc>
 719     basic_string<_CharT, _Traits, _Alloc>&
 720     basic_string<_CharT, _Traits, _Alloc>::
 721     append(const _CharT* __s, size_type __n)
 722     {
 723       __glibcxx_requires_string_len(__s, __n);
 724       const size_type __len = __n + this->size();
 725       if (__len > this->capacity())
 726         this->reserve(__len);
 727       return _M_replace_safe(_M_iend(), _M_iend(), __s, __s + __n);
 728     }
 729
 730   template<typename _CharT, typename _Traits, typename _Alloc>
 731     basic_string<_CharT, _Traits, _Alloc>
 732     operator+(const _CharT* __lhs,
 733               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 734     {
 735       __glibcxx_requires_string(__lhs);
 736       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 737       typedef typename __string_type::size_type   __size_type;
 738       const __size_type __len = _Traits::length(__lhs);
 739       __string_type __str;
 740       __str.reserve(__len + __rhs.size());
 741       __str.append(__lhs, __lhs + __len);
 742       __str.append(__rhs);
 743       return __str;
 744     }
 745
 746   template<typename _CharT, typename _Traits, typename _Alloc>
 747     basic_string<_CharT, _Traits, _Alloc>
 748     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 749     {
 750       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 751       typedef typename __string_type::size_type   __size_type;
 752       __string_type __str;
 753       const __size_type __len = __rhs.size();
 754       __str.reserve(__len + 1);
 755       __str.append(__size_type(1), __lhs);
 756       __str.append(__rhs);
 757       return __str;
 758     }
 759
 760   template<typename _CharT, typename _Traits, typename _Alloc>
 761     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 762     basic_string<_CharT, _Traits, _Alloc>::
 763     copy(_CharT* __s, size_type __n, size_type __pos) const
 764     {
 765       if (__pos > this->size())
 766         __throw_out_of_range("basic_string::copy");
 767
 768       if (__n > this->size() - __pos)
 769         __n = this->size() - __pos;
 770
 771       __glibcxx_requires_string_len(__s, __n);
 772
 773       traits_type::copy(__s, _M_data() + __pos, __n);
 774       // 21.3.5.7 par 3: do not append null.  (good.)
 775       return __n;
 776     }
 777
 778   template<typename _CharT, typename _Traits, typename _Alloc>
 779     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 780     basic_string<_CharT, _Traits, _Alloc>::
 781     find(const _CharT* __s, size_type __pos, size_type __n) const
 782     {
 783       __glibcxx_requires_string_len(__s, __n);
 784
 785       const size_type __size = this->size();
 786       size_t __xpos = __pos;
 787       const _CharT* __data = _M_data();
 788       for (; __xpos + __n <= __size; ++__xpos)
 789         if (traits_type::compare(__data + __xpos, __s, __n) == 0)
 790           return __xpos;
 791       return npos;
 792     }
 793
 794   template<typename _CharT, typename _Traits, typename _Alloc>
 795     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 796     basic_string<_CharT, _Traits, _Alloc>::
 797     find(_CharT __c, size_type __pos) const
 798     {
 799       const size_type __size = this->size();
 800       size_type __ret = npos;
 801       if (__pos < __size)
 802         {
 803           const _CharT* __data = _M_data();
 804           const size_type __n = __size - __pos;
 805           const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
 806           if (__p)
 807             __ret = __p - __data;
 808         }
 809       return __ret;
 810     }
 811
 812
 813   template<typename _CharT, typename _Traits, typename _Alloc>
 814     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 815     basic_string<_CharT, _Traits, _Alloc>::
 816     rfind(const _CharT* __s, size_type __pos, size_type __n) const
 817     {
 818       __glibcxx_requires_string_len(__s, __n);
 819
 820       const size_type __size = this->size();
 821       if (__n <= __size)
 822         {
 823           __pos = std::min(size_type(__size - __n), __pos);
 824           const _CharT* __data = _M_data();
 825           do
 826             {
 827               if (traits_type::compare(__data + __pos, __s, __n) == 0)
 828                 return __pos;
 829             }
 830           while (__pos-- > 0);
 831         }
 832       return npos;
 833     }
 834
 835   template<typename _CharT, typename _Traits, typename _Alloc>
 836     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 837     basic_string<_CharT, _Traits, _Alloc>::
 838     rfind(_CharT __c, size_type __pos) const
 839     {
 840       const size_type __size = this->size();
 841       if (__size)
 842         {
 843           size_t __xpos = __size - 1;
 844           if (__xpos > __pos)
 845             __xpos = __pos;
 846
 847           for (++__xpos; __xpos-- > 0; )
 848             if (traits_type::eq(_M_data()[__xpos], __c))
 849               return __xpos;
 850         }
 851       return npos;
 852     }
 853
 854   template<typename _CharT, typename _Traits, typename _Alloc>
 855     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 856     basic_string<_CharT, _Traits, _Alloc>::
 857     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
 858     {
 859       __glibcxx_requires_string_len(__s, __n);
 860
 861       for (; __n && __pos < this->size(); ++__pos)
 862         {
 863           const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
 864           if (__p)
 865             return __pos;
 866         }
 867       return npos;
 868     }
 869
 870   template<typename _CharT, typename _Traits, typename _Alloc>
 871     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 872     basic_string<_CharT, _Traits, _Alloc>::
 873     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
 874     {
 875       __glibcxx_requires_string_len(__s, __n);
 876
 877       size_type __size = this->size();
 878       if (__size && __n)
 879         {
 880           if (--__size > __pos)
 881             __size = __pos;
 882           do
 883             {
 884               if (traits_type::find(__s, __n, _M_data()[__size]))
 885                 return __size;
 886             }
 887           while (__size-- != 0);
 888         }
 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_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
 896     {
 897       __glibcxx_requires_string_len(__s, __n);
 898
 899       size_t __xpos = __pos;
 900       for (; __xpos < this->size(); ++__xpos)
 901         if (!traits_type::find(__s, __n, _M_data()[__xpos]))
 902           return __xpos;
 903       return npos;
 904     }
 905
 906   template<typename _CharT, typename _Traits, typename _Alloc>
 907     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 908     basic_string<_CharT, _Traits, _Alloc>::
 909     find_first_not_of(_CharT __c, size_type __pos) const
 910     {
 911       size_t __xpos = __pos;
 912       for (; __xpos < this->size(); ++__xpos)
 913         if (!traits_type::eq(_M_data()[__xpos], __c))
 914           return __xpos;
 915       return npos;
 916     }
 917
 918   template<typename _CharT, typename _Traits, typename _Alloc>
 919     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 920     basic_string<_CharT, _Traits, _Alloc>::
 921     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
 922     {
 923       __glibcxx_requires_string_len(__s, __n);
 924
 925       size_type __size = this->size();
 926       if (__size)
 927         {
 928           if (--__size > __pos)
 929             __size = __pos;
 930           do
 931             {
 932               if (!traits_type::find(__s, __n, _M_data()[__size]))
 933                 return __size;
 934             }
 935           while (__size--);
 936         }
 937       return npos;
 938     }
 939
 940   template<typename _CharT, typename _Traits, typename _Alloc>
 941     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 942     basic_string<_CharT, _Traits, _Alloc>::
 943     find_last_not_of(_CharT __c, size_type __pos) const
 944     {
 945       size_type __size = this->size();
 946       if (__size)
 947         {
 948           if (--__size > __pos)
 949             __size = __pos;
 950           do
 951             {
 952               if (!traits_type::eq(_M_data()[__size], __c))
 953                 return __size;
 954             }
 955           while (__size--);
 956         }
 957       return npos;
 958     }
 959
 960   template<typename _CharT, typename _Traits, typename _Alloc>
 961     int
 962     basic_string<_CharT, _Traits, _Alloc>::
 963     compare(size_type __pos, size_type __n, const basic_string& __str) const
 964     {
 965       const size_type __size = this->size();
 966       const size_type __osize = __str.size();
 967       if (__pos > __size)
 968         __throw_out_of_range("basic_string::compare");
 969
 970       const size_type __rsize= std::min(size_type(__size - __pos), __n);
 971       const size_type __len = std::min(__rsize, __osize);
 972       int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
 973       if (!__r)
 974         __r = __rsize - __osize;
 975       return __r;
 976     }
 977
 978   template<typename _CharT, typename _Traits, typename _Alloc>
 979     int
 980     basic_string<_CharT, _Traits, _Alloc>::
 981     compare(size_type __pos1, size_type __n1, const basic_string& __str,
 982             size_type __pos2, size_type __n2) const
 983     {
 984       const size_type __size = this->size();
 985       const size_type __osize = __str.size();
 986       if (__pos1 > __size || __pos2 > __osize)
 987         __throw_out_of_range("basic_string::compare");
 988
 989       const size_type __rsize = std::min(size_type(__size - __pos1), __n1);
 990       const size_type __rosize = std::min(size_type(__osize - __pos2), __n2);
 991       const size_type __len = std::min(__rsize, __rosize);
 992       int __r = traits_type::compare(_M_data() + __pos1,
 993                                      __str.data() + __pos2, __len);
 994       if (!__r)
 995         __r = __rsize - __rosize;
 996       return __r;
 997     }
 998
 999
1000   template<typename _CharT, typename _Traits, typename _Alloc>
1001     int
1002     basic_string<_CharT, _Traits, _Alloc>::
1003     compare(const _CharT* __s) const
1004     {
1005       __glibcxx_requires_string(__s);
1006
1007       const size_type __size = this->size();
1008       const size_type __osize = traits_type::length(__s);
1009       const size_type __len = std::min(__size, __osize);
1010       int __r = traits_type::compare(_M_data(), __s, __len);
1011       if (!__r)
1012         __r = __size - __osize;
1013       return __r;
1014     }
1015
1016
1017   template<typename _CharT, typename _Traits, typename _Alloc>
1018     int
1019     basic_string <_CharT, _Traits, _Alloc>::
1020     compare(size_type __pos, size_type __n1, const _CharT* __s) const
1021     {
1022       __glibcxx_requires_string(__s);
1023
1024       const size_type __size = this->size();
1025       if (__pos > __size)
1026         __throw_out_of_range("basic_string::compare");
1027
1028       const size_type __osize = traits_type::length(__s);
1029       const size_type __rsize = std::min(size_type(__size - __pos), __n1);
1030       const size_type __len = std::min(__rsize, __osize);
1031       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
1032       if (!__r)
1033         __r = __rsize - __osize;
1034       return __r;
1035     }
1036
1037   template<typename _CharT, typename _Traits, typename _Alloc>
1038     int
1039     basic_string <_CharT, _Traits, _Alloc>::
1040     compare(size_type __pos, size_type __n1, const _CharT* __s,
1041             size_type __n2) const
1042     {
1043       __glibcxx_requires_string_len(__s, __n2);
1044
1045       const size_type __size = this->size();
1046       if (__pos > __size)
1047         __throw_out_of_range("basic_string::compare");
1048
1049       const size_type __rsize = std::min(size_type(__size - __pos), __n1);
1050       const size_type __len = std::min(__rsize, __n2);
1051       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
1052       if (!__r)
1053         __r = __rsize - __n2;
1054       return __r;
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 _GLIBCXX_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 _GLIBCXX_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