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