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