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       // 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       size_type __ret = npos;
 722       const size_type __size = this->size();
 723       if (__pos + __n <= __size)
 724         {
 725           const _CharT* __data = _M_data();
 726           const _CharT* __p = std::search(__data + __pos, __data + __size,
 727                                           __s, __s + __n, traits_type::eq);
 728           if (__p != __data + __size || __n == 0)
 729             __ret = __p - __data;
 730         }
 731       return __ret;
 732     }
 733
 734   template<typename _CharT, typename _Traits, typename _Alloc>
 735     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 736     basic_string<_CharT, _Traits, _Alloc>::
 737     find(_CharT __c, size_type __pos) const
 738     {
 739       size_type __ret = npos;
 740       const size_type __size = this->size();
 741       if (__pos < __size)
 742         {
 743           const _CharT* __data = _M_data();
 744           const size_type __n = __size - __pos;
 745           const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
 746           if (__p)
 747             __ret = __p - __data;
 748         }
 749       return __ret;
 750     }
 751
 752   template<typename _CharT, typename _Traits, typename _Alloc>
 753     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 754     basic_string<_CharT, _Traits, _Alloc>::
 755     rfind(const _CharT* __s, size_type __pos, size_type __n) const
 756     {
 757       __glibcxx_requires_string_len(__s, __n);
 758       const size_type __size = this->size();
 759       if (__n <= __size)
 760         {
 761           __pos = std::min(size_type(__size - __n), __pos);
 762           const _CharT* __data = _M_data();
 763           do
 764             {
 765               if (traits_type::compare(__data + __pos, __s, __n) == 0)
 766                 return __pos;
 767             }
 768           while (__pos-- > 0);
 769         }
 770       return npos;
 771     }
 772
 773   template<typename _CharT, typename _Traits, typename _Alloc>
 774     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 775     basic_string<_CharT, _Traits, _Alloc>::
 776     rfind(_CharT __c, size_type __pos) const
 777     {
 778       size_type __size = this->size();
 779       if (__size)
 780         {
 781           if (--__size > __pos)
 782             __size = __pos;
 783           for (++__size; __size-- > 0; )
 784             if (traits_type::eq(_M_data()[__size], __c))
 785               return __size;
 786         }
 787       return npos;
 788     }
 789
 790   template<typename _CharT, typename _Traits, typename _Alloc>
 791     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 792     basic_string<_CharT, _Traits, _Alloc>::
 793     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
 794     {
 795       __glibcxx_requires_string_len(__s, __n);
 796       for (; __n && __pos < this->size(); ++__pos)
 797         {
 798           const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
 799           if (__p)
 800             return __pos;
 801         }
 802       return npos;
 803     }
 804
 805   template<typename _CharT, typename _Traits, typename _Alloc>
 806     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 807     basic_string<_CharT, _Traits, _Alloc>::
 808     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
 809     {
 810       __glibcxx_requires_string_len(__s, __n);
 811       size_type __size = this->size();
 812       if (__size && __n)
 813         {
 814           if (--__size > __pos)
 815             __size = __pos;
 816           do
 817             {
 818               if (traits_type::find(__s, __n, _M_data()[__size]))
 819                 return __size;
 820             }
 821           while (__size-- != 0);
 822         }
 823       return npos;
 824     }
 825
 826   template<typename _CharT, typename _Traits, typename _Alloc>
 827     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 828     basic_string<_CharT, _Traits, _Alloc>::
 829     find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
 830     {
 831       __glibcxx_requires_string_len(__s, __n);
 832       for (; __pos < this->size(); ++__pos)
 833         if (!traits_type::find(__s, __n, _M_data()[__pos]))
 834           return __pos;
 835       return npos;
 836     }
 837
 838   template<typename _CharT, typename _Traits, typename _Alloc>
 839     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 840     basic_string<_CharT, _Traits, _Alloc>::
 841     find_first_not_of(_CharT __c, size_type __pos) const
 842     {
 843       for (; __pos < this->size(); ++__pos)
 844         if (!traits_type::eq(_M_data()[__pos], __c))
 845           return __pos;
 846       return npos;
 847     }
 848
 849   template<typename _CharT, typename _Traits, typename _Alloc>
 850     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 851     basic_string<_CharT, _Traits, _Alloc>::
 852     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
 853     {
 854       __glibcxx_requires_string_len(__s, __n);
 855       size_type __size = this->size();
 856       if (__size)
 857         {
 858           if (--__size > __pos)
 859             __size = __pos;
 860           do
 861             {
 862               if (!traits_type::find(__s, __n, _M_data()[__size]))
 863                 return __size;
 864             }
 865           while (__size--);
 866         }
 867       return npos;
 868     }
 869
 870   template<typename _CharT, typename _Traits, typename _Alloc>
 871     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 872     basic_string<_CharT, _Traits, _Alloc>::
 873     find_last_not_of(_CharT __c, size_type __pos) const
 874     {
 875       size_type __size = this->size();
 876       if (__size)
 877         {
 878           if (--__size > __pos)
 879             __size = __pos;
 880           do
 881             {
 882               if (!traits_type::eq(_M_data()[__size], __c))
 883                 return __size;
 884             }
 885           while (__size--);
 886         }
 887       return npos;
 888     }
 889
 890   template<typename _CharT, typename _Traits, typename _Alloc>
 891     int
 892     basic_string<_CharT, _Traits, _Alloc>::
 893     compare(size_type __pos, size_type __n, const basic_string& __str) const
 894     {
 895       _M_check(__pos, "basic_string::compare");
 896       __n = _M_limit(__pos, __n);
 897       const size_type __osize = __str.size();
 898       const size_type __len = std::min(__n, __osize);
 899       int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
 900       if (!__r)
 901         __r = __n - __osize;
 902       return __r;
 903     }
 904
 905   template<typename _CharT, typename _Traits, typename _Alloc>
 906     int
 907     basic_string<_CharT, _Traits, _Alloc>::
 908     compare(size_type __pos1, size_type __n1, const basic_string& __str,
 909             size_type __pos2, size_type __n2) const
 910     {
 911       _M_check(__pos1, "basic_string::compare");
 912       __str._M_check(__pos2, "basic_string::compare");
 913       __n1 = _M_limit(__pos1, __n1);
 914       __n2 = __str._M_limit(__pos2, __n2);
 915       const size_type __len = std::min(__n1, __n2);
 916       int __r = traits_type::compare(_M_data() + __pos1,
 917                                      __str.data() + __pos2, __len);
 918       if (!__r)
 919         __r = __n1 - __n2;
 920       return __r;
 921     }
 922
 923   template<typename _CharT, typename _Traits, typename _Alloc>
 924     int
 925     basic_string<_CharT, _Traits, _Alloc>::
 926     compare(const _CharT* __s) const
 927     {
 928       __glibcxx_requires_string(__s);
 929       const size_type __size = this->size();
 930       const size_type __osize = traits_type::length(__s);
 931       const size_type __len = std::min(__size, __osize);
 932       int __r = traits_type::compare(_M_data(), __s, __len);
 933       if (!__r)
 934         __r = __size - __osize;
 935       return __r;
 936     }
 937
 938   template<typename _CharT, typename _Traits, typename _Alloc>
 939     int
 940     basic_string <_CharT, _Traits, _Alloc>::
 941     compare(size_type __pos, size_type __n1, const _CharT* __s) const
 942     {
 943       __glibcxx_requires_string(__s);
 944       _M_check(__pos, "basic_string::compare");
 945       __n1 = _M_limit(__pos, __n1);
 946       const size_type __osize = traits_type::length(__s);
 947       const size_type __len = std::min(__n1, __osize);
 948       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
 949       if (!__r)
 950         __r = __n1 - __osize;
 951       return __r;
 952     }
 953
 954   template<typename _CharT, typename _Traits, typename _Alloc>
 955     int
 956     basic_string <_CharT, _Traits, _Alloc>::
 957     compare(size_type __pos, size_type __n1, const _CharT* __s,
 958             size_type __n2) const
 959     {
 960       __glibcxx_requires_string_len(__s, __n2);
 961       _M_check(__pos, "basic_string::compare");
 962       __n1 = _M_limit(__pos, __n1);
 963       const size_type __len = std::min(__n1, __n2);
 964       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
 965       if (!__r)
 966         __r = __n1 - __n2;
 967       return __r;
 968     }
 969
 970   // Inhibit implicit instantiations for required instantiations,
 971   // which are defined via explicit instantiations elsewhere.
 972   // NB: This syntax is a GNU extension.
 973 #if _GLIBCXX_EXTERN_TEMPLATE
 974   extern template class basic_string<char>;
 975   extern template
 976     basic_istream<char>&
 977     operator>>(basic_istream<char>&, string&);
 978   extern template
 979     basic_ostream<char>&
 980     operator<<(basic_ostream<char>&, const string&);
 981   extern template
 982     basic_istream<char>&
 983     getline(basic_istream<char>&, string&, char);
 984   extern template
 985     basic_istream<char>&
 986     getline(basic_istream<char>&, string&);
 987
 988 #ifdef _GLIBCXX_USE_WCHAR_T
 989   extern template class basic_string<wchar_t>;
 990   extern template
 991     basic_istream<wchar_t>&
 992     operator>>(basic_istream<wchar_t>&, wstring&);
 993   extern template
 994     basic_ostream<wchar_t>&
 995     operator<<(basic_ostream<wchar_t>&, const wstring&);
 996   extern template
 997     basic_istream<wchar_t>&
 998     getline(basic_istream<wchar_t>&, wstring&, wchar_t);
 999   extern template
1000     basic_istream<wchar_t>&
1001     getline(basic_istream<wchar_t>&, wstring&);
1002 #endif
1003 #endif
1004 } // namespace std
1005
1006 #endif