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