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