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