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

   1 // Components for manipulating sequences of characters -*- C++ -*-
   2
   3 // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
   4 // 2006, 2007, 2008, 2009, 2010
   5 // Free Software Foundation, Inc.
   6 //
   7 // This file is part of the GNU ISO C++ Library.  This library is free
   8 // software; you can redistribute it and/or modify it under the
   9 // terms of the GNU General Public License as published by the
  10 // Free Software Foundation; either version 3, or (at your option)
  11 // any later version.
  12
  13 // This library is distributed in the hope that it will be useful,
  14 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 // GNU General Public License for more details.
  17
  18 // Under Section 7 of GPL version 3, you are granted additional
  19 // permissions described in the GCC Runtime Library Exception, version
  20 // 3.1, as published by the Free Software Foundation.
  21
  22 // You should have received a copy of the GNU General Public License and
  23 // a copy of the GCC Runtime Library Exception along with this program;
  24 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  25 // <http://www.gnu.org/licenses/>.
  26
  27 /** @file bits/basic_string.tcc
  28  *  This is an internal header file, included by other library headers.
  29  *  Do not attempt to use it directly. @headername{string}
  30  */
  31
  32 //
  33 // ISO C++ 14882: 21  Strings library
  34 //
  35
  36 // Written by Jason Merrill based upon the specification by Takanori Adachi
  37 // in ANSI X3J16/94-0013R2.  Rewritten by Nathan Myers to ISO-14882.
  38
  39 #ifndef _BASIC_STRING_TCC
  40 #define _BASIC_STRING_TCC 1
  41
  42 #pragma GCC system_header
  43
  44 #include <cxxabi-forced.h>
  45
  46 _GLIBCXX_BEGIN_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 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
  82         if (__beg == __end && __a == _Alloc())
  83           return _S_empty_rep()._M_refdata();
  84 #endif
  85         // Avoid reallocation for common case.
  86         _CharT __buf[128];
  87         size_type __len = 0;
  88         while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT))
  89           {
  90             __buf[__len++] = *__beg;
  91             ++__beg;
  92           }
  93         _Rep* __r = _Rep::_S_create(__len, size_type(0), __a);
  94         _M_copy(__r->_M_refdata(), __buf, __len);
  95         __try
  96           {
  97             while (__beg != __end)
  98               {
  99                 if (__len == __r->_M_capacity)
 100                   {
 101                     // Allocate more space.
 102                     _Rep* __another = _Rep::_S_create(__len + 1, __len, __a);
 103                     _M_copy(__another->_M_refdata(), __r->_M_refdata(), __len);
 104                     __r->_M_destroy(__a);
 105                     __r = __another;
 106                   }
 107                 __r->_M_refdata()[__len++] = *__beg;
 108                 ++__beg;
 109               }
 110           }
 111         __catch(...)
 112           {
 113             __r->_M_destroy(__a);
 114             __throw_exception_again;
 115           }
 116         __r->_M_set_length_and_sharable(__len);
 117         return __r->_M_refdata();
 118       }
 119
 120   template<typename _CharT, typename _Traits, typename _Alloc>
 121     template <typename _InIterator>
 122       _CharT*
 123       basic_string<_CharT, _Traits, _Alloc>::
 124       _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
 125                    forward_iterator_tag)
 126       {
 127 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
 128         if (__beg == __end && __a == _Alloc())
 129           return _S_empty_rep()._M_refdata();
 130 #endif
 131         // NB: Not required, but considered best practice.
 132         if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end)
 133           __throw_logic_error(__N("basic_string::_S_construct null not valid"));
 134
 135         const size_type __dnew = static_cast<size_type>(std::distance(__beg,
 136                                                                       __end));
 137         // Check for out_of_range and length_error exceptions.
 138         _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a);
 139         __try
 140           { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
 141         __catch(...)
 142           {
 143             __r->_M_destroy(__a);
 144             __throw_exception_again;
 145           }
 146         __r->_M_set_length_and_sharable(__dnew);
 147         return __r->_M_refdata();
 148       }
 149
 150   template<typename _CharT, typename _Traits, typename _Alloc>
 151     _CharT*
 152     basic_string<_CharT, _Traits, _Alloc>::
 153     _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
 154     {
 155 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
 156       if (__n == 0 && __a == _Alloc())
 157         return _S_empty_rep()._M_refdata();
 158 #endif
 159       // Check for out_of_range and length_error exceptions.
 160       _Rep* __r = _Rep::_S_create(__n, size_type(0), __a);
 161       if (__n)
 162         _M_assign(__r->_M_refdata(), __n, __c);
 163
 164       __r->_M_set_length_and_sharable(__n);
 165       return __r->_M_refdata();
 166     }
 167
 168   template<typename _CharT, typename _Traits, typename _Alloc>
 169     basic_string<_CharT, _Traits, _Alloc>::
 170     basic_string(const basic_string& __str)
 171     : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()),
 172                                           __str.get_allocator()),
 173                   __str.get_allocator())
 174     { }
 175
 176   template<typename _CharT, typename _Traits, typename _Alloc>
 177     basic_string<_CharT, _Traits, _Alloc>::
 178     basic_string(const _Alloc& __a)
 179     : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a)
 180     { }
 181
 182   template<typename _CharT, typename _Traits, typename _Alloc>
 183     basic_string<_CharT, _Traits, _Alloc>::
 184     basic_string(const basic_string& __str, size_type __pos, size_type __n)
 185     : _M_dataplus(_S_construct(__str._M_data()
 186                                + __str._M_check(__pos,
 187                                                 "basic_string::basic_string"),
 188                                __str._M_data() + __str._M_limit(__pos, __n)
 189                                + __pos, _Alloc()), _Alloc())
 190     { }
 191
 192   template<typename _CharT, typename _Traits, typename _Alloc>
 193     basic_string<_CharT, _Traits, _Alloc>::
 194     basic_string(const basic_string& __str, size_type __pos,
 195                  size_type __n, const _Alloc& __a)
 196     : _M_dataplus(_S_construct(__str._M_data()
 197                                + __str._M_check(__pos,
 198                                                 "basic_string::basic_string"),
 199                                __str._M_data() + __str._M_limit(__pos, __n)
 200                                + __pos, __a), __a)
 201     { }
 202
 203   // TBD: DPG annotate
 204   template<typename _CharT, typename _Traits, typename _Alloc>
 205     basic_string<_CharT, _Traits, _Alloc>::
 206     basic_string(const _CharT* __s, size_type __n, const _Alloc& __a)
 207     : _M_dataplus(_S_construct(__s, __s + __n, __a), __a)
 208     { }
 209
 210   // TBD: DPG annotate
 211   template<typename _CharT, typename _Traits, typename _Alloc>
 212     basic_string<_CharT, _Traits, _Alloc>::
 213     basic_string(const _CharT* __s, const _Alloc& __a)
 214     : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) :
 215                                __s + npos, __a), __a)
 216     { }
 217
 218   template<typename _CharT, typename _Traits, typename _Alloc>
 219     basic_string<_CharT, _Traits, _Alloc>::
 220     basic_string(size_type __n, _CharT __c, const _Alloc& __a)
 221     : _M_dataplus(_S_construct(__n, __c, __a), __a)
 222     { }
 223
 224   // TBD: DPG annotate
 225   template<typename _CharT, typename _Traits, typename _Alloc>
 226     template<typename _InputIterator>
 227     basic_string<_CharT, _Traits, _Alloc>::
 228     basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a)
 229     : _M_dataplus(_S_construct(__beg, __end, __a), __a)
 230     { }
 231
 232 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 233   template<typename _CharT, typename _Traits, typename _Alloc>
 234     basic_string<_CharT, _Traits, _Alloc>::
 235     basic_string(initializer_list<_CharT> __l, const _Alloc& __a)
 236     : _M_dataplus(_S_construct(__l.begin(), __l.end(), __a), __a)
 237     { }
 238 #endif
 239
 240   template<typename _CharT, typename _Traits, typename _Alloc>
 241     basic_string<_CharT, _Traits, _Alloc>&
 242     basic_string<_CharT, _Traits, _Alloc>::
 243     assign(const basic_string& __str)
 244     {
 245       if (_M_rep() != __str._M_rep())
 246         {
 247           // XXX MT
 248           const allocator_type __a = this->get_allocator();
 249           _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator());
 250           _M_rep()->_M_dispose(__a);
 251           _M_data(__tmp);
 252         }
 253       return *this;
 254     }
 255
 256   template<typename _CharT, typename _Traits, typename _Alloc>
 257     basic_string<_CharT, _Traits, _Alloc>&
 258     basic_string<_CharT, _Traits, _Alloc>::
 259     assign(const _CharT* __s, size_type __n)
 260     {
 261       __glibcxx_requires_string_len(__s, __n);
 262       _M_check_length(this->size(), __n, "basic_string::assign");
 263       if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
 264         return _M_replace_safe(size_type(0), this->size(), __s, __n);
 265       else
 266         {
 267           // Work in-place.
 268           const size_type __pos = __s - _M_data();
 269           if (__pos >= __n)
 270             _M_copy(_M_data(), __s, __n);
 271           else if (__pos)
 272             _M_move(_M_data(), __s, __n);
 273           _M_rep()->_M_set_length_and_sharable(__n);
 274           return *this;
 275         }
 276      }
 277
 278   template<typename _CharT, typename _Traits, typename _Alloc>
 279     basic_string<_CharT, _Traits, _Alloc>&
 280     basic_string<_CharT, _Traits, _Alloc>::
 281     append(size_type __n, _CharT __c)
 282     {
 283       if (__n)
 284         {
 285           _M_check_length(size_type(0), __n, "basic_string::append");
 286           const size_type __len = __n + this->size();
 287           if (__len > this->capacity() || _M_rep()->_M_is_shared())
 288             this->reserve(__len);
 289           _M_assign(_M_data() + this->size(), __n, __c);
 290           _M_rep()->_M_set_length_and_sharable(__len);
 291         }
 292       return *this;
 293     }
 294
 295   template<typename _CharT, typename _Traits, typename _Alloc>
 296     basic_string<_CharT, _Traits, _Alloc>&
 297     basic_string<_CharT, _Traits, _Alloc>::
 298     append(const _CharT* __s, size_type __n)
 299     {
 300       __glibcxx_requires_string_len(__s, __n);
 301       if (__n)
 302         {
 303           _M_check_length(size_type(0), __n, "basic_string::append");
 304           const size_type __len = __n + this->size();
 305           if (__len > this->capacity() || _M_rep()->_M_is_shared())
 306             {
 307               if (_M_disjunct(__s))
 308                 this->reserve(__len);
 309               else
 310                 {
 311                   const size_type __off = __s - _M_data();
 312                   this->reserve(__len);
 313                   __s = _M_data() + __off;
 314                 }
 315             }
 316           _M_copy(_M_data() + this->size(), __s, __n);
 317           _M_rep()->_M_set_length_and_sharable(__len);
 318         }
 319       return *this;
 320     }
 321
 322   template<typename _CharT, typename _Traits, typename _Alloc>
 323     basic_string<_CharT, _Traits, _Alloc>&
 324     basic_string<_CharT, _Traits, _Alloc>::
 325     append(const basic_string& __str)
 326     {
 327       const size_type __size = __str.size();
 328       if (__size)
 329         {
 330           const size_type __len = __size + this->size();
 331           if (__len > this->capacity() || _M_rep()->_M_is_shared())
 332             this->reserve(__len);
 333           _M_copy(_M_data() + this->size(), __str._M_data(), __size);
 334           _M_rep()->_M_set_length_and_sharable(__len);
 335         }
 336       return *this;
 337     }
 338
 339   template<typename _CharT, typename _Traits, typename _Alloc>
 340     basic_string<_CharT, _Traits, _Alloc>&
 341     basic_string<_CharT, _Traits, _Alloc>::
 342     append(const basic_string& __str, size_type __pos, size_type __n)
 343     {
 344       __str._M_check(__pos, "basic_string::append");
 345       __n = __str._M_limit(__pos, __n);
 346       if (__n)
 347         {
 348           const size_type __len = __n + this->size();
 349           if (__len > this->capacity() || _M_rep()->_M_is_shared())
 350             this->reserve(__len);
 351           _M_copy(_M_data() + this->size(), __str._M_data() + __pos, __n);
 352           _M_rep()->_M_set_length_and_sharable(__len);
 353         }
 354       return *this;
 355     }
 356
 357    template<typename _CharT, typename _Traits, typename _Alloc>
 358      basic_string<_CharT, _Traits, _Alloc>&
 359      basic_string<_CharT, _Traits, _Alloc>::
 360      insert(size_type __pos, const _CharT* __s, size_type __n)
 361      {
 362        __glibcxx_requires_string_len(__s, __n);
 363        _M_check(__pos, "basic_string::insert");
 364        _M_check_length(size_type(0), __n, "basic_string::insert");
 365        if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
 366          return _M_replace_safe(__pos, size_type(0), __s, __n);
 367        else
 368          {
 369            // Work in-place.
 370            const size_type __off = __s - _M_data();
 371            _M_mutate(__pos, 0, __n);
 372            __s = _M_data() + __off;
 373            _CharT* __p = _M_data() + __pos;
 374            if (__s  + __n <= __p)
 375              _M_copy(__p, __s, __n);
 376            else if (__s >= __p)
 377              _M_copy(__p, __s + __n, __n);
 378            else
 379              {
 380                const size_type __nleft = __p - __s;
 381                _M_copy(__p, __s, __nleft);
 382                _M_copy(__p + __nleft, __p + __n, __n - __nleft);
 383              }
 384            return *this;
 385          }
 386      }
 387
 388    template<typename _CharT, typename _Traits, typename _Alloc>
 389      typename basic_string<_CharT, _Traits, _Alloc>::iterator
 390      basic_string<_CharT, _Traits, _Alloc>::
 391      erase(iterator __first, iterator __last)
 392      {
 393        _GLIBCXX_DEBUG_PEDASSERT(__first >= _M_ibegin() && __first <= __last
 394                                 && __last <= _M_iend());
 395
 396        // NB: This isn't just an optimization (bail out early when
 397        // there is nothing to do, really), it's also a correctness
 398        // issue vs MT, see libstdc++/40518.
 399        const size_type __size = __last - __first;
 400        if (__size)
 401          {
 402            const size_type __pos = __first - _M_ibegin();
 403            _M_mutate(__pos, __size, size_type(0));
 404            _M_rep()->_M_set_leaked();
 405            return iterator(_M_data() + __pos);
 406          }
 407        else
 408          return __first;
 409      }
 410
 411    template<typename _CharT, typename _Traits, typename _Alloc>
 412      basic_string<_CharT, _Traits, _Alloc>&
 413      basic_string<_CharT, _Traits, _Alloc>::
 414      replace(size_type __pos, size_type __n1, const _CharT* __s,
 415              size_type __n2)
 416      {
 417        __glibcxx_requires_string_len(__s, __n2);
 418        _M_check(__pos, "basic_string::replace");
 419        __n1 = _M_limit(__pos, __n1);
 420        _M_check_length(__n1, __n2, "basic_string::replace");
 421        bool __left;
 422        if (_M_disjunct(__s) || _M_rep()->_M_is_shared())
 423          return _M_replace_safe(__pos, __n1, __s, __n2);
 424        else if ((__left = __s + __n2 <= _M_data() + __pos)
 425                 || _M_data() + __pos + __n1 <= __s)
 426          {
 427            // Work in-place: non-overlapping case.
 428            size_type __off = __s - _M_data();
 429            __left ? __off : (__off += __n2 - __n1);
 430            _M_mutate(__pos, __n1, __n2);
 431            _M_copy(_M_data() + __pos, _M_data() + __off, __n2);
 432            return *this;
 433          }
 434        else
 435          {
 436            // Todo: overlapping case.
 437            const basic_string __tmp(__s, __n2);
 438            return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2);
 439          }
 440      }
 441
 442   template<typename _CharT, typename _Traits, typename _Alloc>
 443     void
 444     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 445     _M_destroy(const _Alloc& __a) throw ()
 446     {
 447       const size_type __size = sizeof(_Rep_base) +
 448                                (this->_M_capacity + 1) * sizeof(_CharT);
 449       _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
 450     }
 451
 452   template<typename _CharT, typename _Traits, typename _Alloc>
 453     void
 454     basic_string<_CharT, _Traits, _Alloc>::
 455     _M_leak_hard()
 456     {
 457 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
 458       if (_M_rep() == &_S_empty_rep())
 459         return;
 460 #endif
 461       if (_M_rep()->_M_is_shared())
 462         _M_mutate(0, 0, 0);
 463       _M_rep()->_M_set_leaked();
 464     }
 465
 466   template<typename _CharT, typename _Traits, typename _Alloc>
 467     void
 468     basic_string<_CharT, _Traits, _Alloc>::
 469     _M_mutate(size_type __pos, size_type __len1, size_type __len2)
 470     {
 471       const size_type __old_size = this->size();
 472       const size_type __new_size = __old_size + __len2 - __len1;
 473       const size_type __how_much = __old_size - __pos - __len1;
 474
 475       if (__new_size > this->capacity() || _M_rep()->_M_is_shared())
 476         {
 477           // Must reallocate.
 478           const allocator_type __a = get_allocator();
 479           _Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a);
 480
 481           if (__pos)
 482             _M_copy(__r->_M_refdata(), _M_data(), __pos);
 483           if (__how_much)
 484             _M_copy(__r->_M_refdata() + __pos + __len2,
 485                     _M_data() + __pos + __len1, __how_much);
 486
 487           _M_rep()->_M_dispose(__a);
 488           _M_data(__r->_M_refdata());
 489         }
 490       else if (__how_much && __len1 != __len2)
 491         {
 492           // Work in-place.
 493           _M_move(_M_data() + __pos + __len2,
 494                   _M_data() + __pos + __len1, __how_much);
 495         }
 496       _M_rep()->_M_set_length_and_sharable(__new_size);
 497     }
 498
 499   template<typename _CharT, typename _Traits, typename _Alloc>
 500     void
 501     basic_string<_CharT, _Traits, _Alloc>::
 502     reserve(size_type __res)
 503     {
 504       if (__res != this->capacity() || _M_rep()->_M_is_shared())
 505         {
 506           // Make sure we don't shrink below the current size
 507           if (__res < this->size())
 508             __res = this->size();
 509           const allocator_type __a = get_allocator();
 510           _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
 511           _M_rep()->_M_dispose(__a);
 512           _M_data(__tmp);
 513         }
 514     }
 515
 516   template<typename _CharT, typename _Traits, typename _Alloc>
 517     void
 518     basic_string<_CharT, _Traits, _Alloc>::
 519     swap(basic_string& __s)
 520     {
 521       if (_M_rep()->_M_is_leaked())
 522         _M_rep()->_M_set_sharable();
 523       if (__s._M_rep()->_M_is_leaked())
 524         __s._M_rep()->_M_set_sharable();
 525       if (this->get_allocator() == __s.get_allocator())
 526         {
 527           _CharT* __tmp = _M_data();
 528           _M_data(__s._M_data());
 529           __s._M_data(__tmp);
 530         }
 531       // The code below can usually be optimized away.
 532       else
 533         {
 534           const basic_string __tmp1(_M_ibegin(), _M_iend(),
 535                                     __s.get_allocator());
 536           const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
 537                                     this->get_allocator());
 538           *this = __tmp2;
 539           __s = __tmp1;
 540         }
 541     }
 542
 543   template<typename _CharT, typename _Traits, typename _Alloc>
 544     typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
 545     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 546     _S_create(size_type __capacity, size_type __old_capacity,
 547               const _Alloc& __alloc)
 548     {
 549       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 550       // 83.  String::npos vs. string::max_size()
 551       if (__capacity > _S_max_size)
 552         __throw_length_error(__N("basic_string::_S_create"));
 553
 554       // The standard places no restriction on allocating more memory
 555       // than is strictly needed within this layer at the moment or as
 556       // requested by an explicit application call to reserve().
 557
 558       // Many malloc implementations perform quite poorly when an
 559       // application attempts to allocate memory in a stepwise fashion
 560       // growing each allocation size by only 1 char.  Additionally,
 561       // it makes little sense to allocate less linear memory than the
 562       // natural blocking size of the malloc implementation.
 563       // Unfortunately, we would need a somewhat low-level calculation
 564       // with tuned parameters to get this perfect for any particular
 565       // malloc implementation.  Fortunately, generalizations about
 566       // common features seen among implementations seems to suffice.
 567
 568       // __pagesize need not match the actual VM page size for good
 569       // results in practice, thus we pick a common value on the low
 570       // side.  __malloc_header_size is an estimate of the amount of
 571       // overhead per memory allocation (in practice seen N * sizeof
 572       // (void*) where N is 0, 2 or 4).  According to folklore,
 573       // picking this value on the high side is better than
 574       // low-balling it (especially when this algorithm is used with
 575       // malloc implementations that allocate memory blocks rounded up
 576       // to a size which is a power of 2).
 577       const size_type __pagesize = 4096;
 578       const size_type __malloc_header_size = 4 * sizeof(void*);
 579
 580       // The below implements an exponential growth policy, necessary to
 581       // meet amortized linear time requirements of the library: see
 582       // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
 583       // It's active for allocations requiring an amount of memory above
 584       // system pagesize. This is consistent with the requirements of the
 585       // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
 586       if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
 587         __capacity = 2 * __old_capacity;
 588
 589       // NB: Need an array of char_type[__capacity], plus a terminating
 590       // null char_type() element, plus enough for the _Rep data structure.
 591       // Whew. Seemingly so needy, yet so elemental.
 592       size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
 593
 594       const size_type __adj_size = __size + __malloc_header_size;
 595       if (__adj_size > __pagesize && __capacity > __old_capacity)
 596         {
 597           const size_type __extra = __pagesize - __adj_size % __pagesize;
 598           __capacity += __extra / sizeof(_CharT);
 599           // Never allocate a string bigger than _S_max_size.
 600           if (__capacity > _S_max_size)
 601             __capacity = _S_max_size;
 602           __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
 603         }
 604
 605       // NB: Might throw, but no worries about a leak, mate: _Rep()
 606       // does not throw.
 607       void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
 608       _Rep *__p = new (__place) _Rep;
 609       __p->_M_capacity = __capacity;
 610       // ABI compatibility - 3.4.x set in _S_create both
 611       // _M_refcount and _M_length.  All callers of _S_create
 612       // in basic_string.tcc then set just _M_length.
 613       // In 4.0.x and later both _M_refcount and _M_length
 614       // are initialized in the callers, unfortunately we can
 615       // have 3.4.x compiled code with _S_create callers inlined
 616       // calling 4.0.x+ _S_create.
 617       __p->_M_set_sharable();
 618       return __p;
 619     }
 620
 621   template<typename _CharT, typename _Traits, typename _Alloc>
 622     _CharT*
 623     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 624     _M_clone(const _Alloc& __alloc, size_type __res)
 625     {
 626       // Requested capacity of the clone.
 627       const size_type __requested_cap = this->_M_length + __res;
 628       _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity,
 629                                   __alloc);
 630       if (this->_M_length)
 631         _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length);
 632
 633       __r->_M_set_length_and_sharable(this->_M_length);
 634       return __r->_M_refdata();
 635     }
 636
 637   template<typename _CharT, typename _Traits, typename _Alloc>
 638     void
 639     basic_string<_CharT, _Traits, _Alloc>::
 640     resize(size_type __n, _CharT __c)
 641     {
 642       const size_type __size = this->size();
 643       _M_check_length(__size, __n, "basic_string::resize");
 644       if (__size < __n)
 645         this->append(__n - __size, __c);
 646       else if (__n < __size)
 647         this->erase(__n);
 648       // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
 649     }
 650
 651   template<typename _CharT, typename _Traits, typename _Alloc>
 652     template<typename _InputIterator>
 653       basic_string<_CharT, _Traits, _Alloc>&
 654       basic_string<_CharT, _Traits, _Alloc>::
 655       _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
 656                           _InputIterator __k2, __false_type)
 657       {
 658         const basic_string __s(__k1, __k2);
 659         const size_type __n1 = __i2 - __i1;
 660         _M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch");
 661         return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(),
 662                                __s.size());
 663       }
 664
 665   template<typename _CharT, typename _Traits, typename _Alloc>
 666     basic_string<_CharT, _Traits, _Alloc>&
 667     basic_string<_CharT, _Traits, _Alloc>::
 668     _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
 669                    _CharT __c)
 670     {
 671       _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
 672       _M_mutate(__pos1, __n1, __n2);
 673       if (__n2)
 674         _M_assign(_M_data() + __pos1, __n2, __c);
 675       return *this;
 676     }
 677
 678   template<typename _CharT, typename _Traits, typename _Alloc>
 679     basic_string<_CharT, _Traits, _Alloc>&
 680     basic_string<_CharT, _Traits, _Alloc>::
 681     _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
 682                     size_type __n2)
 683     {
 684       _M_mutate(__pos1, __n1, __n2);
 685       if (__n2)
 686         _M_copy(_M_data() + __pos1, __s, __n2);
 687       return *this;
 688     }
 689
 690   template<typename _CharT, typename _Traits, typename _Alloc>
 691     basic_string<_CharT, _Traits, _Alloc>
 692     operator+(const _CharT* __lhs,
 693               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 694     {
 695       __glibcxx_requires_string(__lhs);
 696       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 697       typedef typename __string_type::size_type   __size_type;
 698       const __size_type __len = _Traits::length(__lhs);
 699       __string_type __str;
 700       __str.reserve(__len + __rhs.size());
 701       __str.append(__lhs, __len);
 702       __str.append(__rhs);
 703       return __str;
 704     }
 705
 706   template<typename _CharT, typename _Traits, typename _Alloc>
 707     basic_string<_CharT, _Traits, _Alloc>
 708     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 709     {
 710       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 711       typedef typename __string_type::size_type   __size_type;
 712       __string_type __str;
 713       const __size_type __len = __rhs.size();
 714       __str.reserve(__len + 1);
 715       __str.append(__size_type(1), __lhs);
 716       __str.append(__rhs);
 717       return __str;
 718     }
 719
 720   template<typename _CharT, typename _Traits, typename _Alloc>
 721     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 722     basic_string<_CharT, _Traits, _Alloc>::
 723     copy(_CharT* __s, size_type __n, size_type __pos) const
 724     {
 725       _M_check(__pos, "basic_string::copy");
 726       __n = _M_limit(__pos, __n);
 727       __glibcxx_requires_string_len(__s, __n);
 728       if (__n)
 729         _M_copy(__s, _M_data() + __pos, __n);
 730       // 21.3.5.7 par 3: do not append null.  (good.)
 731       return __n;
 732     }
 733
 734   template<typename _CharT, typename _Traits, typename _Alloc>
 735     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 736     basic_string<_CharT, _Traits, _Alloc>::
 737     find(const _CharT* __s, size_type __pos, size_type __n) const
 738     {
 739       __glibcxx_requires_string_len(__s, __n);
 740       const size_type __size = this->size();
 741       const _CharT* __data = _M_data();
 742
 743       if (__n == 0)
 744         return __pos <= __size ? __pos : npos;
 745
 746       if (__n <= __size)
 747         {
 748           for (; __pos <= __size - __n; ++__pos)
 749             if (traits_type::eq(__data[__pos], __s[0])
 750                 && traits_type::compare(__data + __pos + 1,
 751                                         __s + 1, __n - 1) == 0)
 752               return __pos;
 753         }
 754       return npos;
 755     }
 756
 757   template<typename _CharT, typename _Traits, typename _Alloc>
 758     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 759     basic_string<_CharT, _Traits, _Alloc>::
 760     find(_CharT __c, size_type __pos) const
 761     {
 762       size_type __ret = npos;
 763       const size_type __size = this->size();
 764       if (__pos < __size)
 765         {
 766           const _CharT* __data = _M_data();
 767           const size_type __n = __size - __pos;
 768           const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
 769           if (__p)
 770             __ret = __p - __data;
 771         }
 772       return __ret;
 773     }
 774
 775   template<typename _CharT, typename _Traits, typename _Alloc>
 776     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 777     basic_string<_CharT, _Traits, _Alloc>::
 778     rfind(const _CharT* __s, size_type __pos, size_type __n) const
 779     {
 780       __glibcxx_requires_string_len(__s, __n);
 781       const size_type __size = this->size();
 782       if (__n <= __size)
 783         {
 784           __pos = std::min(size_type(__size - __n), __pos);
 785           const _CharT* __data = _M_data();
 786           do
 787             {
 788               if (traits_type::compare(__data + __pos, __s, __n) == 0)
 789                 return __pos;
 790             }
 791           while (__pos-- > 0);
 792         }
 793       return npos;
 794     }
 795
 796   template<typename _CharT, typename _Traits, typename _Alloc>
 797     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 798     basic_string<_CharT, _Traits, _Alloc>::
 799     rfind(_CharT __c, size_type __pos) const
 800     {
 801       size_type __size = this->size();
 802       if (__size)
 803         {
 804           if (--__size > __pos)
 805             __size = __pos;
 806           for (++__size; __size-- > 0; )
 807             if (traits_type::eq(_M_data()[__size], __c))
 808               return __size;
 809         }
 810       return npos;
 811     }
 812
 813   template<typename _CharT, typename _Traits, typename _Alloc>
 814     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 815     basic_string<_CharT, _Traits, _Alloc>::
 816     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
 817     {
 818       __glibcxx_requires_string_len(__s, __n);
 819       for (; __n && __pos < this->size(); ++__pos)
 820         {
 821           const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
 822           if (__p)
 823             return __pos;
 824         }
 825       return npos;
 826     }
 827
 828   template<typename _CharT, typename _Traits, typename _Alloc>
 829     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 830     basic_string<_CharT, _Traits, _Alloc>::
 831     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
 832     {
 833       __glibcxx_requires_string_len(__s, __n);
 834       size_type __size = this->size();
 835       if (__size && __n)
 836         {
 837           if (--__size > __pos)
 838             __size = __pos;
 839           do
 840             {
 841               if (traits_type::find(__s, __n, _M_data()[__size]))
 842                 return __size;
 843             }
 844           while (__size-- != 0);
 845         }
 846       return npos;
 847     }
 848
 849   template<typename _CharT, typename _Traits, typename _Alloc>
 850     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 851     basic_string<_CharT, _Traits, _Alloc>::
 852     find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
 853     {
 854       __glibcxx_requires_string_len(__s, __n);
 855       for (; __pos < this->size(); ++__pos)
 856         if (!traits_type::find(__s, __n, _M_data()[__pos]))
 857           return __pos;
 858       return npos;
 859     }
 860
 861   template<typename _CharT, typename _Traits, typename _Alloc>
 862     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 863     basic_string<_CharT, _Traits, _Alloc>::
 864     find_first_not_of(_CharT __c, size_type __pos) const
 865     {
 866       for (; __pos < this->size(); ++__pos)
 867         if (!traits_type::eq(_M_data()[__pos], __c))
 868           return __pos;
 869       return npos;
 870     }
 871
 872   template<typename _CharT, typename _Traits, typename _Alloc>
 873     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 874     basic_string<_CharT, _Traits, _Alloc>::
 875     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
 876     {
 877       __glibcxx_requires_string_len(__s, __n);
 878       size_type __size = this->size();
 879       if (__size)
 880         {
 881           if (--__size > __pos)
 882             __size = __pos;
 883           do
 884             {
 885               if (!traits_type::find(__s, __n, _M_data()[__size]))
 886                 return __size;
 887             }
 888           while (__size--);
 889         }
 890       return npos;
 891     }
 892
 893   template<typename _CharT, typename _Traits, typename _Alloc>
 894     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 895     basic_string<_CharT, _Traits, _Alloc>::
 896     find_last_not_of(_CharT __c, size_type __pos) const
 897     {
 898       size_type __size = this->size();
 899       if (__size)
 900         {
 901           if (--__size > __pos)
 902             __size = __pos;
 903           do
 904             {
 905               if (!traits_type::eq(_M_data()[__size], __c))
 906                 return __size;
 907             }
 908           while (__size--);
 909         }
 910       return npos;
 911     }
 912
 913   template<typename _CharT, typename _Traits, typename _Alloc>
 914     int
 915     basic_string<_CharT, _Traits, _Alloc>::
 916     compare(size_type __pos, size_type __n, const basic_string& __str) const
 917     {
 918       _M_check(__pos, "basic_string::compare");
 919       __n = _M_limit(__pos, __n);
 920       const size_type __osize = __str.size();
 921       const size_type __len = std::min(__n, __osize);
 922       int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
 923       if (!__r)
 924         __r = _S_compare(__n, __osize);
 925       return __r;
 926     }
 927
 928   template<typename _CharT, typename _Traits, typename _Alloc>
 929     int
 930     basic_string<_CharT, _Traits, _Alloc>::
 931     compare(size_type __pos1, size_type __n1, const basic_string& __str,
 932             size_type __pos2, size_type __n2) const
 933     {
 934       _M_check(__pos1, "basic_string::compare");
 935       __str._M_check(__pos2, "basic_string::compare");
 936       __n1 = _M_limit(__pos1, __n1);
 937       __n2 = __str._M_limit(__pos2, __n2);
 938       const size_type __len = std::min(__n1, __n2);
 939       int __r = traits_type::compare(_M_data() + __pos1,
 940                                      __str.data() + __pos2, __len);
 941       if (!__r)
 942         __r = _S_compare(__n1, __n2);
 943       return __r;
 944     }
 945
 946   template<typename _CharT, typename _Traits, typename _Alloc>
 947     int
 948     basic_string<_CharT, _Traits, _Alloc>::
 949     compare(const _CharT* __s) const
 950     {
 951       __glibcxx_requires_string(__s);
 952       const size_type __size = this->size();
 953       const size_type __osize = traits_type::length(__s);
 954       const size_type __len = std::min(__size, __osize);
 955       int __r = traits_type::compare(_M_data(), __s, __len);
 956       if (!__r)
 957         __r = _S_compare(__size, __osize);
 958       return __r;
 959     }
 960
 961   template<typename _CharT, typename _Traits, typename _Alloc>
 962     int
 963     basic_string <_CharT, _Traits, _Alloc>::
 964     compare(size_type __pos, size_type __n1, const _CharT* __s) const
 965     {
 966       __glibcxx_requires_string(__s);
 967       _M_check(__pos, "basic_string::compare");
 968       __n1 = _M_limit(__pos, __n1);
 969       const size_type __osize = traits_type::length(__s);
 970       const size_type __len = std::min(__n1, __osize);
 971       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
 972       if (!__r)
 973         __r = _S_compare(__n1, __osize);
 974       return __r;
 975     }
 976
 977   template<typename _CharT, typename _Traits, typename _Alloc>
 978     int
 979     basic_string <_CharT, _Traits, _Alloc>::
 980     compare(size_type __pos, size_type __n1, const _CharT* __s,
 981             size_type __n2) const
 982     {
 983       __glibcxx_requires_string_len(__s, __n2);
 984       _M_check(__pos, "basic_string::compare");
 985       __n1 = _M_limit(__pos, __n1);
 986       const size_type __len = std::min(__n1, __n2);
 987       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
 988       if (!__r)
 989         __r = _S_compare(__n1, __n2);
 990       return __r;
 991     }
 992
 993   // 21.3.7.9 basic_string::getline and operators
 994   template<typename _CharT, typename _Traits, typename _Alloc>
 995     basic_istream<_CharT, _Traits>&
 996     operator>>(basic_istream<_CharT, _Traits>& __in,
 997                basic_string<_CharT, _Traits, _Alloc>& __str)
 998     {
 999       typedef basic_istream<_CharT, _Traits>            __istream_type;
1000       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
1001       typedef typename __istream_type::ios_base         __ios_base;
1002       typedef typename __istream_type::int_type         __int_type;
1003       typedef typename __string_type::size_type         __size_type;
1004       typedef ctype<_CharT>                             __ctype_type;
1005       typedef typename __ctype_type::ctype_base         __ctype_base;
1006
1007       __size_type __extracted = 0;
1008       typename __ios_base::iostate __err = __ios_base::goodbit;
1009       typename __istream_type::sentry __cerb(__in, false);
1010       if (__cerb)
1011         {
1012           __try
1013             {
1014               // Avoid reallocation for common case.
1015               __str.erase();
1016               _CharT __buf[128];
1017               __size_type __len = 0;
1018               const streamsize __w = __in.width();
1019               const __size_type __n = __w > 0 ? static_cast<__size_type>(__w)
1020                                               : __str.max_size();
1021               const __ctype_type& __ct = use_facet<__ctype_type>(__in.getloc());
1022               const __int_type __eof = _Traits::eof();
1023               __int_type __c = __in.rdbuf()->sgetc();
1024
1025               while (__extracted < __n
1026                      && !_Traits::eq_int_type(__c, __eof)
1027                      && !__ct.is(__ctype_base::space,
1028                                  _Traits::to_char_type(__c)))
1029                 {
1030                   if (__len == sizeof(__buf) / sizeof(_CharT))
1031                     {
1032                       __str.append(__buf, sizeof(__buf) / sizeof(_CharT));
1033                       __len = 0;
1034                     }
1035                   __buf[__len++] = _Traits::to_char_type(__c);
1036                   ++__extracted;
1037                   __c = __in.rdbuf()->snextc();
1038                 }
1039               __str.append(__buf, __len);
1040
1041               if (_Traits::eq_int_type(__c, __eof))
1042                 __err |= __ios_base::eofbit;
1043               __in.width(0);
1044             }
1045           __catch(__cxxabiv1::__forced_unwind&)
1046             {
1047               __in._M_setstate(__ios_base::badbit);
1048               __throw_exception_again;
1049             }
1050           __catch(...)
1051             {
1052               // _GLIBCXX_RESOLVE_LIB_DEFECTS
1053               // 91. Description of operator>> and getline() for string<>
1054               // might cause endless loop
1055               __in._M_setstate(__ios_base::badbit);
1056             }
1057         }
1058       // 211.  operator>>(istream&, string&) doesn't set failbit
1059       if (!__extracted)
1060         __err |= __ios_base::failbit;
1061       if (__err)
1062         __in.setstate(__err);
1063       return __in;
1064     }
1065
1066   template<typename _CharT, typename _Traits, typename _Alloc>
1067     basic_istream<_CharT, _Traits>&
1068     getline(basic_istream<_CharT, _Traits>& __in,
1069             basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim)
1070     {
1071       typedef basic_istream<_CharT, _Traits>            __istream_type;
1072       typedef basic_string<_CharT, _Traits, _Alloc>     __string_type;
1073       typedef typename __istream_type::ios_base         __ios_base;
1074       typedef typename __istream_type::int_type         __int_type;
1075       typedef typename __string_type::size_type         __size_type;
1076
1077       __size_type __extracted = 0;
1078       const __size_type __n = __str.max_size();
1079       typename __ios_base::iostate __err = __ios_base::goodbit;
1080       typename __istream_type::sentry __cerb(__in, true);
1081       if (__cerb)
1082         {
1083           __try
1084             {
1085               __str.erase();
1086               const __int_type __idelim = _Traits::to_int_type(__delim);
1087               const __int_type __eof = _Traits::eof();
1088               __int_type __c = __in.rdbuf()->sgetc();
1089
1090               while (__extracted < __n
1091                      && !_Traits::eq_int_type(__c, __eof)
1092                      && !_Traits::eq_int_type(__c, __idelim))
1093                 {
1094                   __str += _Traits::to_char_type(__c);
1095                   ++__extracted;
1096                   __c = __in.rdbuf()->snextc();
1097                 }
1098
1099               if (_Traits::eq_int_type(__c, __eof))
1100                 __err |= __ios_base::eofbit;
1101               else if (_Traits::eq_int_type(__c, __idelim))
1102                 {
1103                   ++__extracted;
1104                   __in.rdbuf()->sbumpc();
1105                 }
1106               else
1107                 __err |= __ios_base::failbit;
1108             }
1109           __catch(__cxxabiv1::__forced_unwind&)
1110             {
1111               __in._M_setstate(__ios_base::badbit);
1112               __throw_exception_again;
1113             }
1114           __catch(...)
1115             {
1116               // _GLIBCXX_RESOLVE_LIB_DEFECTS
1117               // 91. Description of operator>> and getline() for string<>
1118               // might cause endless loop
1119               __in._M_setstate(__ios_base::badbit);
1120             }
1121         }
1122       if (!__extracted)
1123         __err |= __ios_base::failbit;
1124       if (__err)
1125         __in.setstate(__err);
1126       return __in;
1127     }
1128
1129   // Inhibit implicit instantiations for required instantiations,
1130   // which are defined via explicit instantiations elsewhere.
1131   // NB: This syntax is a GNU extension.
1132 #if _GLIBCXX_EXTERN_TEMPLATE > 0
1133   extern template class basic_string<char>;
1134   extern template
1135     basic_istream<char>&
1136     operator>>(basic_istream<char>&, string&);
1137   extern template
1138     basic_ostream<char>&
1139     operator<<(basic_ostream<char>&, const string&);
1140   extern template
1141     basic_istream<char>&
1142     getline(basic_istream<char>&, string&, char);
1143   extern template
1144     basic_istream<char>&
1145     getline(basic_istream<char>&, string&);
1146
1147 #ifdef _GLIBCXX_USE_WCHAR_T
1148   extern template class basic_string<wchar_t>;
1149   extern template
1150     basic_istream<wchar_t>&
1151     operator>>(basic_istream<wchar_t>&, wstring&);
1152   extern template
1153     basic_ostream<wchar_t>&
1154     operator<<(basic_ostream<wchar_t>&, const wstring&);
1155   extern template
1156     basic_istream<wchar_t>&
1157     getline(basic_istream<wchar_t>&, wstring&, wchar_t);
1158   extern template
1159     basic_istream<wchar_t>&
1160     getline(basic_istream<wchar_t>&, wstring&);
1161 #endif
1162 #endif
1163
1164 _GLIBCXX_END_NAMESPACE
1165
1166 #endif