contrib/gcc-4.1/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 // 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 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       return __p;
 592     }
 593
 594   template<typename _CharT, typename _Traits, typename _Alloc>
 595     _CharT*
 596     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 597     _M_clone(const _Alloc& __alloc, size_type __res)
 598     {
 599       // Requested capacity of the clone.
 600       const size_type __requested_cap = this->_M_length + __res;
 601       _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity,
 602                                   __alloc);
 603       if (this->_M_length)
 604         _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length);
 605
 606       __r->_M_set_length_and_sharable(this->_M_length);
 607       return __r->_M_refdata();
 608     }
 609
 610   template<typename _CharT, typename _Traits, typename _Alloc>
 611     void
 612     basic_string<_CharT, _Traits, _Alloc>::
 613     resize(size_type __n, _CharT __c)
 614     {
 615       const size_type __size = this->size();
 616       _M_check_length(__size, __n, "basic_string::resize");
 617       if (__size < __n)
 618         this->append(__n - __size, __c);
 619       else if (__n < __size)
 620         this->erase(__n);
 621       // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
 622     }
 623
 624   template<typename _CharT, typename _Traits, typename _Alloc>
 625     template<typename _InputIterator>
 626       basic_string<_CharT, _Traits, _Alloc>&
 627       basic_string<_CharT, _Traits, _Alloc>::
 628       _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
 629                           _InputIterator __k2, __false_type)
 630       {
 631         const basic_string __s(__k1, __k2);
 632         const size_type __n1 = __i2 - __i1;
 633         _M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch");
 634         return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(),
 635                                __s.size());
 636       }
 637
 638   template<typename _CharT, typename _Traits, typename _Alloc>
 639     basic_string<_CharT, _Traits, _Alloc>&
 640     basic_string<_CharT, _Traits, _Alloc>::
 641     _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
 642                    _CharT __c)
 643     {
 644       _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
 645       _M_mutate(__pos1, __n1, __n2);
 646       if (__n2)
 647         _M_assign(_M_data() + __pos1, __n2, __c);
 648       return *this;
 649     }
 650
 651   template<typename _CharT, typename _Traits, typename _Alloc>
 652     basic_string<_CharT, _Traits, _Alloc>&
 653     basic_string<_CharT, _Traits, _Alloc>::
 654     _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
 655                     size_type __n2)
 656     {
 657       _M_mutate(__pos1, __n1, __n2);
 658       if (__n2)
 659         _M_copy(_M_data() + __pos1, __s, __n2);
 660       return *this;
 661     }
 662
 663   template<typename _CharT, typename _Traits, typename _Alloc>
 664     basic_string<_CharT, _Traits, _Alloc>
 665     operator+(const _CharT* __lhs,
 666               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 667     {
 668       __glibcxx_requires_string(__lhs);
 669       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 670       typedef typename __string_type::size_type   __size_type;
 671       const __size_type __len = _Traits::length(__lhs);
 672       __string_type __str;
 673       __str.reserve(__len + __rhs.size());
 674       __str.append(__lhs, __len);
 675       __str.append(__rhs);
 676       return __str;
 677     }
 678
 679   template<typename _CharT, typename _Traits, typename _Alloc>
 680     basic_string<_CharT, _Traits, _Alloc>
 681     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 682     {
 683       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 684       typedef typename __string_type::size_type   __size_type;
 685       __string_type __str;
 686       const __size_type __len = __rhs.size();
 687       __str.reserve(__len + 1);
 688       __str.append(__size_type(1), __lhs);
 689       __str.append(__rhs);
 690       return __str;
 691     }
 692
 693   template<typename _CharT, typename _Traits, typename _Alloc>
 694     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 695     basic_string<_CharT, _Traits, _Alloc>::
 696     copy(_CharT* __s, size_type __n, size_type __pos) const
 697     {
 698       _M_check(__pos, "basic_string::copy");
 699       __n = _M_limit(__pos, __n);
 700       __glibcxx_requires_string_len(__s, __n);
 701       if (__n)
 702         _M_copy(__s, _M_data() + __pos, __n);
 703       // 21.3.5.7 par 3: do not append null.  (good.)
 704       return __n;
 705     }
 706
 707   template<typename _CharT, typename _Traits, typename _Alloc>
 708     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 709     basic_string<_CharT, _Traits, _Alloc>::
 710     find(const _CharT* __s, size_type __pos, size_type __n) const
 711     {
 712       __glibcxx_requires_string_len(__s, __n);
 713       size_type __ret = npos;
 714       const size_type __size = this->size();
 715       if (__pos + __n <= __size)
 716         {
 717           const _CharT* __data = _M_data();
 718           const _CharT* __p = std::search(__data + __pos, __data + __size,
 719                                           __s, __s + __n, traits_type::eq);
 720           if (__p != __data + __size || __n == 0)
 721             __ret = __p - __data;
 722         }
 723       return __ret;
 724     }
 725
 726   template<typename _CharT, typename _Traits, typename _Alloc>
 727     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 728     basic_string<_CharT, _Traits, _Alloc>::
 729     find(_CharT __c, size_type __pos) const
 730     {
 731       size_type __ret = npos;
 732       const size_type __size = this->size();
 733       if (__pos < __size)
 734         {
 735           const _CharT* __data = _M_data();
 736           const size_type __n = __size - __pos;
 737           const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
 738           if (__p)
 739             __ret = __p - __data;
 740         }
 741       return __ret;
 742     }
 743
 744   template<typename _CharT, typename _Traits, typename _Alloc>
 745     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 746     basic_string<_CharT, _Traits, _Alloc>::
 747     rfind(const _CharT* __s, size_type __pos, size_type __n) const
 748     {
 749       __glibcxx_requires_string_len(__s, __n);
 750       const size_type __size = this->size();
 751       if (__n <= __size)
 752         {
 753           __pos = std::min(size_type(__size - __n), __pos);
 754           const _CharT* __data = _M_data();
 755           do
 756             {
 757               if (traits_type::compare(__data + __pos, __s, __n) == 0)
 758                 return __pos;
 759             }
 760           while (__pos-- > 0);
 761         }
 762       return npos;
 763     }
 764
 765   template<typename _CharT, typename _Traits, typename _Alloc>
 766     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 767     basic_string<_CharT, _Traits, _Alloc>::
 768     rfind(_CharT __c, size_type __pos) const
 769     {
 770       size_type __size = this->size();
 771       if (__size)
 772         {
 773           if (--__size > __pos)
 774             __size = __pos;
 775           for (++__size; __size-- > 0; )
 776             if (traits_type::eq(_M_data()[__size], __c))
 777               return __size;
 778         }
 779       return npos;
 780     }
 781
 782   template<typename _CharT, typename _Traits, typename _Alloc>
 783     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 784     basic_string<_CharT, _Traits, _Alloc>::
 785     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
 786     {
 787       __glibcxx_requires_string_len(__s, __n);
 788       for (; __n && __pos < this->size(); ++__pos)
 789         {
 790           const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
 791           if (__p)
 792             return __pos;
 793         }
 794       return npos;
 795     }
 796
 797   template<typename _CharT, typename _Traits, typename _Alloc>
 798     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 799     basic_string<_CharT, _Traits, _Alloc>::
 800     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
 801     {
 802       __glibcxx_requires_string_len(__s, __n);
 803       size_type __size = this->size();
 804       if (__size && __n)
 805         {
 806           if (--__size > __pos)
 807             __size = __pos;
 808           do
 809             {
 810               if (traits_type::find(__s, __n, _M_data()[__size]))
 811                 return __size;
 812             }
 813           while (__size-- != 0);
 814         }
 815       return npos;
 816     }
 817
 818   template<typename _CharT, typename _Traits, typename _Alloc>
 819     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 820     basic_string<_CharT, _Traits, _Alloc>::
 821     find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
 822     {
 823       __glibcxx_requires_string_len(__s, __n);
 824       for (; __pos < this->size(); ++__pos)
 825         if (!traits_type::find(__s, __n, _M_data()[__pos]))
 826           return __pos;
 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(_CharT __c, size_type __pos) const
 834     {
 835       for (; __pos < this->size(); ++__pos)
 836         if (!traits_type::eq(_M_data()[__pos], __c))
 837           return __pos;
 838       return npos;
 839     }
 840
 841   template<typename _CharT, typename _Traits, typename _Alloc>
 842     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 843     basic_string<_CharT, _Traits, _Alloc>::
 844     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
 845     {
 846       __glibcxx_requires_string_len(__s, __n);
 847       size_type __size = this->size();
 848       if (__size)
 849         {
 850           if (--__size > __pos)
 851             __size = __pos;
 852           do
 853             {
 854               if (!traits_type::find(__s, __n, _M_data()[__size]))
 855                 return __size;
 856             }
 857           while (__size--);
 858         }
 859       return npos;
 860     }
 861
 862   template<typename _CharT, typename _Traits, typename _Alloc>
 863     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 864     basic_string<_CharT, _Traits, _Alloc>::
 865     find_last_not_of(_CharT __c, size_type __pos) const
 866     {
 867       size_type __size = this->size();
 868       if (__size)
 869         {
 870           if (--__size > __pos)
 871             __size = __pos;
 872           do
 873             {
 874               if (!traits_type::eq(_M_data()[__size], __c))
 875                 return __size;
 876             }
 877           while (__size--);
 878         }
 879       return npos;
 880     }
 881
 882   template<typename _CharT, typename _Traits, typename _Alloc>
 883     int
 884     basic_string<_CharT, _Traits, _Alloc>::
 885     compare(size_type __pos, size_type __n, const basic_string& __str) const
 886     {
 887       _M_check(__pos, "basic_string::compare");
 888       __n = _M_limit(__pos, __n);
 889       const size_type __osize = __str.size();
 890       const size_type __len = std::min(__n, __osize);
 891       int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
 892       if (!__r)
 893         __r = __n - __osize;
 894       return __r;
 895     }
 896
 897   template<typename _CharT, typename _Traits, typename _Alloc>
 898     int
 899     basic_string<_CharT, _Traits, _Alloc>::
 900     compare(size_type __pos1, size_type __n1, const basic_string& __str,
 901             size_type __pos2, size_type __n2) const
 902     {
 903       _M_check(__pos1, "basic_string::compare");
 904       __str._M_check(__pos2, "basic_string::compare");
 905       __n1 = _M_limit(__pos1, __n1);
 906       __n2 = __str._M_limit(__pos2, __n2);
 907       const size_type __len = std::min(__n1, __n2);
 908       int __r = traits_type::compare(_M_data() + __pos1,
 909                                      __str.data() + __pos2, __len);
 910       if (!__r)
 911         __r = __n1 - __n2;
 912       return __r;
 913     }
 914
 915   template<typename _CharT, typename _Traits, typename _Alloc>
 916     int
 917     basic_string<_CharT, _Traits, _Alloc>::
 918     compare(const _CharT* __s) const
 919     {
 920       __glibcxx_requires_string(__s);
 921       const size_type __size = this->size();
 922       const size_type __osize = traits_type::length(__s);
 923       const size_type __len = std::min(__size, __osize);
 924       int __r = traits_type::compare(_M_data(), __s, __len);
 925       if (!__r)
 926         __r = __size - __osize;
 927       return __r;
 928     }
 929
 930   template<typename _CharT, typename _Traits, typename _Alloc>
 931     int
 932     basic_string <_CharT, _Traits, _Alloc>::
 933     compare(size_type __pos, size_type __n1, const _CharT* __s) const
 934     {
 935       __glibcxx_requires_string(__s);
 936       _M_check(__pos, "basic_string::compare");
 937       __n1 = _M_limit(__pos, __n1);
 938       const size_type __osize = traits_type::length(__s);
 939       const size_type __len = std::min(__n1, __osize);
 940       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
 941       if (!__r)
 942         __r = __n1 - __osize;
 943       return __r;
 944     }
 945
 946   template<typename _CharT, typename _Traits, typename _Alloc>
 947     int
 948     basic_string <_CharT, _Traits, _Alloc>::
 949     compare(size_type __pos, size_type __n1, const _CharT* __s,
 950             size_type __n2) const
 951     {
 952       __glibcxx_requires_string_len(__s, __n2);
 953       _M_check(__pos, "basic_string::compare");
 954       __n1 = _M_limit(__pos, __n1);
 955       const size_type __len = std::min(__n1, __n2);
 956       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
 957       if (!__r)
 958         __r = __n1 - __n2;
 959       return __r;
 960     }
 961
 962   // Inhibit implicit instantiations for required instantiations,
 963   // which are defined via explicit instantiations elsewhere.
 964   // NB: This syntax is a GNU extension.
 965 #if _GLIBCXX_EXTERN_TEMPLATE
 966   extern template class basic_string<char>;
 967   extern template
 968     basic_istream<char>&
 969     operator>>(basic_istream<char>&, string&);
 970   extern template
 971     basic_ostream<char>&
 972     operator<<(basic_ostream<char>&, const string&);
 973   extern template
 974     basic_istream<char>&
 975     getline(basic_istream<char>&, string&, char);
 976   extern template
 977     basic_istream<char>&
 978     getline(basic_istream<char>&, string&);
 979
 980 #ifdef _GLIBCXX_USE_WCHAR_T
 981   extern template class basic_string<wchar_t>;
 982   extern template
 983     basic_istream<wchar_t>&
 984     operator>>(basic_istream<wchar_t>&, wstring&);
 985   extern template
 986     basic_ostream<wchar_t>&
 987     operator<<(basic_ostream<wchar_t>&, const wstring&);
 988   extern template
 989     basic_istream<wchar_t>&
 990     getline(basic_istream<wchar_t>&, wstring&, wchar_t);
 991   extern template
 992     basic_istream<wchar_t>&
 993     getline(basic_istream<wchar_t>&, wstring&);
 994 #endif
 995 #endif
 996 } // namespace std
 997
 998 #endif