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