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
   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, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  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 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
 429       if (this == &_S_empty_rep())
 430         return;
 431 #endif
 432       const size_type __size = sizeof(_Rep_base) +
 433                                (this->_M_capacity + 1) * sizeof(_CharT);
 434       _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size);
 435     }
 436
 437   template<typename _CharT, typename _Traits, typename _Alloc>
 438     void
 439     basic_string<_CharT, _Traits, _Alloc>::
 440     _M_leak_hard()
 441     {
 442 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING
 443       if (_M_rep() == &_S_empty_rep())
 444         return;
 445 #endif
 446       if (_M_rep()->_M_is_shared())
 447         _M_mutate(0, 0, 0);
 448       _M_rep()->_M_set_leaked();
 449     }
 450
 451   template<typename _CharT, typename _Traits, typename _Alloc>
 452     void
 453     basic_string<_CharT, _Traits, _Alloc>::
 454     _M_mutate(size_type __pos, size_type __len1, size_type __len2)
 455     {
 456       const size_type __old_size = this->size();
 457       const size_type __new_size = __old_size + __len2 - __len1;
 458       const size_type __how_much = __old_size - __pos - __len1;
 459
 460       if (__new_size > this->capacity() || _M_rep()->_M_is_shared())
 461         {
 462           // Must reallocate.
 463           const allocator_type __a = get_allocator();
 464           _Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a);
 465
 466           if (__pos)
 467             _M_copy(__r->_M_refdata(), _M_data(), __pos);
 468           if (__how_much)
 469             _M_copy(__r->_M_refdata() + __pos + __len2,
 470                     _M_data() + __pos + __len1, __how_much);
 471
 472           _M_rep()->_M_dispose(__a);
 473           _M_data(__r->_M_refdata());
 474         }
 475       else if (__how_much && __len1 != __len2)
 476         {
 477           // Work in-place.
 478           _M_move(_M_data() + __pos + __len2,
 479                   _M_data() + __pos + __len1, __how_much);
 480         }
 481       _M_rep()->_M_set_length_and_sharable(__new_size);
 482     }
 483
 484   template<typename _CharT, typename _Traits, typename _Alloc>
 485     void
 486     basic_string<_CharT, _Traits, _Alloc>::
 487     reserve(size_type __res)
 488     {
 489       if (__res != this->capacity() || _M_rep()->_M_is_shared())
 490         {
 491           // Make sure we don't shrink below the current size
 492           if (__res < this->size())
 493             __res = this->size();
 494           const allocator_type __a = get_allocator();
 495           _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size());
 496           _M_rep()->_M_dispose(__a);
 497           _M_data(__tmp);
 498         }
 499     }
 500
 501   template<typename _CharT, typename _Traits, typename _Alloc>
 502     void
 503     basic_string<_CharT, _Traits, _Alloc>::
 504     swap(basic_string& __s)
 505     {
 506       if (_M_rep()->_M_is_leaked())
 507         _M_rep()->_M_set_sharable();
 508       if (__s._M_rep()->_M_is_leaked())
 509         __s._M_rep()->_M_set_sharable();
 510       if (this->get_allocator() == __s.get_allocator())
 511         {
 512           _CharT* __tmp = _M_data();
 513           _M_data(__s._M_data());
 514           __s._M_data(__tmp);
 515         }
 516       // The code below can usually be optimized away.
 517       else
 518         {
 519           const basic_string __tmp1(_M_ibegin(), _M_iend(),
 520                                     __s.get_allocator());
 521           const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(),
 522                                     this->get_allocator());
 523           *this = __tmp2;
 524           __s = __tmp1;
 525         }
 526     }
 527
 528   template<typename _CharT, typename _Traits, typename _Alloc>
 529     typename basic_string<_CharT, _Traits, _Alloc>::_Rep*
 530     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 531     _S_create(size_type __capacity, size_type __old_capacity,
 532               const _Alloc& __alloc)
 533     {
 534       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 535       // 83.  String::npos vs. string::max_size()
 536       if (__capacity > _S_max_size)
 537         __throw_length_error(__N("basic_string::_S_create"));
 538
 539       // The standard places no restriction on allocating more memory
 540       // than is strictly needed within this layer at the moment or as
 541       // requested by an explicit application call to reserve().
 542
 543       // Many malloc implementations perform quite poorly when an
 544       // application attempts to allocate memory in a stepwise fashion
 545       // growing each allocation size by only 1 char.  Additionally,
 546       // it makes little sense to allocate less linear memory than the
 547       // natural blocking size of the malloc implementation.
 548       // Unfortunately, we would need a somewhat low-level calculation
 549       // with tuned parameters to get this perfect for any particular
 550       // malloc implementation.  Fortunately, generalizations about
 551       // common features seen among implementations seems to suffice.
 552
 553       // __pagesize need not match the actual VM page size for good
 554       // results in practice, thus we pick a common value on the low
 555       // side.  __malloc_header_size is an estimate of the amount of
 556       // overhead per memory allocation (in practice seen N * sizeof
 557       // (void*) where N is 0, 2 or 4).  According to folklore,
 558       // picking this value on the high side is better than
 559       // low-balling it (especially when this algorithm is used with
 560       // malloc implementations that allocate memory blocks rounded up
 561       // to a size which is a power of 2).
 562       const size_type __pagesize = 4096;
 563       const size_type __malloc_header_size = 4 * sizeof(void*);
 564
 565       // The below implements an exponential growth policy, necessary to
 566       // meet amortized linear time requirements of the library: see
 567       // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
 568       // It's active for allocations requiring an amount of memory above
 569       // system pagesize. This is consistent with the requirements of the
 570       // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html
 571       if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
 572         __capacity = 2 * __old_capacity;
 573
 574       // NB: Need an array of char_type[__capacity], plus a terminating
 575       // null char_type() element, plus enough for the _Rep data structure.
 576       // Whew. Seemingly so needy, yet so elemental.
 577       size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
 578
 579       const size_type __adj_size = __size + __malloc_header_size;
 580       if (__adj_size > __pagesize)
 581         {
 582           const size_type __extra = __pagesize - __adj_size % __pagesize;
 583           __capacity += __extra / sizeof(_CharT);
 584           // Never allocate a string bigger than _S_max_size.
 585           if (__capacity > _S_max_size)
 586             __capacity = _S_max_size;
 587           __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep);
 588         }
 589
 590       // NB: Might throw, but no worries about a leak, mate: _Rep()
 591       // does not throw.
 592       void* __place = _Raw_bytes_alloc(__alloc).allocate(__size);
 593       _Rep *__p = new (__place) _Rep;
 594       __p->_M_capacity = __capacity;
 595       return __p;
 596     }
 597
 598   template<typename _CharT, typename _Traits, typename _Alloc>
 599     _CharT*
 600     basic_string<_CharT, _Traits, _Alloc>::_Rep::
 601     _M_clone(const _Alloc& __alloc, size_type __res)
 602     {
 603       // Requested capacity of the clone.
 604       const size_type __requested_cap = this->_M_length + __res;
 605       _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity,
 606                                   __alloc);
 607       if (this->_M_length)
 608         _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length);
 609
 610       __r->_M_set_length_and_sharable(this->_M_length);
 611       return __r->_M_refdata();
 612     }
 613
 614   template<typename _CharT, typename _Traits, typename _Alloc>
 615     void
 616     basic_string<_CharT, _Traits, _Alloc>::
 617     resize(size_type __n, _CharT __c)
 618     {
 619       const size_type __size = this->size();
 620       _M_check_length(__size, __n, "basic_string::resize");
 621       if (__size < __n)
 622         this->append(__n - __size, __c);
 623       else if (__n < __size)
 624         this->erase(__n);
 625       // else nothing (in particular, avoid calling _M_mutate() unnecessarily.)
 626     }
 627
 628   template<typename _CharT, typename _Traits, typename _Alloc>
 629     template<typename _InputIterator>
 630       basic_string<_CharT, _Traits, _Alloc>&
 631       basic_string<_CharT, _Traits, _Alloc>::
 632       _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1,
 633                           _InputIterator __k2, __false_type)
 634       {
 635         const basic_string __s(__k1, __k2);
 636         const size_type __n1 = __i2 - __i1;
 637         _M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch");
 638         return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(),
 639                                __s.size());
 640       }
 641
 642   template<typename _CharT, typename _Traits, typename _Alloc>
 643     basic_string<_CharT, _Traits, _Alloc>&
 644     basic_string<_CharT, _Traits, _Alloc>::
 645     _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2,
 646                    _CharT __c)
 647     {
 648       _M_check_length(__n1, __n2, "basic_string::_M_replace_aux");
 649       _M_mutate(__pos1, __n1, __n2);
 650       if (__n2)
 651         _M_assign(_M_data() + __pos1, __n2, __c);
 652       return *this;
 653     }
 654
 655   template<typename _CharT, typename _Traits, typename _Alloc>
 656     basic_string<_CharT, _Traits, _Alloc>&
 657     basic_string<_CharT, _Traits, _Alloc>::
 658     _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s,
 659                     size_type __n2)
 660     {
 661       _M_mutate(__pos1, __n1, __n2);
 662       if (__n2)
 663         _M_copy(_M_data() + __pos1, __s, __n2);
 664       return *this;
 665     }
 666
 667   template<typename _CharT, typename _Traits, typename _Alloc>
 668     basic_string<_CharT, _Traits, _Alloc>
 669     operator+(const _CharT* __lhs,
 670               const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 671     {
 672       __glibcxx_requires_string(__lhs);
 673       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 674       typedef typename __string_type::size_type   __size_type;
 675       const __size_type __len = _Traits::length(__lhs);
 676       __string_type __str;
 677       __str.reserve(__len + __rhs.size());
 678       __str.append(__lhs, __len);
 679       __str.append(__rhs);
 680       return __str;
 681     }
 682
 683   template<typename _CharT, typename _Traits, typename _Alloc>
 684     basic_string<_CharT, _Traits, _Alloc>
 685     operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs)
 686     {
 687       typedef basic_string<_CharT, _Traits, _Alloc> __string_type;
 688       typedef typename __string_type::size_type   __size_type;
 689       __string_type __str;
 690       const __size_type __len = __rhs.size();
 691       __str.reserve(__len + 1);
 692       __str.append(__size_type(1), __lhs);
 693       __str.append(__rhs);
 694       return __str;
 695     }
 696
 697   template<typename _CharT, typename _Traits, typename _Alloc>
 698     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 699     basic_string<_CharT, _Traits, _Alloc>::
 700     copy(_CharT* __s, size_type __n, size_type __pos) const
 701     {
 702       _M_check(__pos, "basic_string::copy");
 703       __n = _M_limit(__pos, __n);
 704       __glibcxx_requires_string_len(__s, __n);
 705       if (__n)
 706         _M_copy(__s, _M_data() + __pos, __n);
 707       // 21.3.5.7 par 3: do not append null.  (good.)
 708       return __n;
 709     }
 710
 711   template<typename _CharT, typename _Traits, typename _Alloc>
 712     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 713     basic_string<_CharT, _Traits, _Alloc>::
 714     find(const _CharT* __s, size_type __pos, size_type __n) const
 715     {
 716       __glibcxx_requires_string_len(__s, __n);
 717       size_type __ret = npos;
 718       const size_type __size = this->size();
 719       if (__pos + __n <= __size)
 720         {
 721           const _CharT* __data = _M_data();
 722           const _CharT* __p = std::search(__data + __pos, __data + __size,
 723                                           __s, __s + __n, traits_type::eq);
 724           if (__p != __data + __size || __n == 0)
 725             __ret = __p - __data;
 726         }
 727       return __ret;
 728     }
 729
 730   template<typename _CharT, typename _Traits, typename _Alloc>
 731     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 732     basic_string<_CharT, _Traits, _Alloc>::
 733     find(_CharT __c, size_type __pos) const
 734     {
 735       size_type __ret = npos;
 736       const size_type __size = this->size();
 737       if (__pos < __size)
 738         {
 739           const _CharT* __data = _M_data();
 740           const size_type __n = __size - __pos;
 741           const _CharT* __p = traits_type::find(__data + __pos, __n, __c);
 742           if (__p)
 743             __ret = __p - __data;
 744         }
 745       return __ret;
 746     }
 747
 748   template<typename _CharT, typename _Traits, typename _Alloc>
 749     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 750     basic_string<_CharT, _Traits, _Alloc>::
 751     rfind(const _CharT* __s, size_type __pos, size_type __n) const
 752     {
 753       __glibcxx_requires_string_len(__s, __n);
 754       const size_type __size = this->size();
 755       if (__n <= __size)
 756         {
 757           __pos = std::min(size_type(__size - __n), __pos);
 758           const _CharT* __data = _M_data();
 759           do
 760             {
 761               if (traits_type::compare(__data + __pos, __s, __n) == 0)
 762                 return __pos;
 763             }
 764           while (__pos-- > 0);
 765         }
 766       return npos;
 767     }
 768
 769   template<typename _CharT, typename _Traits, typename _Alloc>
 770     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 771     basic_string<_CharT, _Traits, _Alloc>::
 772     rfind(_CharT __c, size_type __pos) const
 773     {
 774       size_type __size = this->size();
 775       if (__size)
 776         {
 777           if (--__size > __pos)
 778             __size = __pos;
 779           for (++__size; __size-- > 0; )
 780             if (traits_type::eq(_M_data()[__size], __c))
 781               return __size;
 782         }
 783       return npos;
 784     }
 785
 786   template<typename _CharT, typename _Traits, typename _Alloc>
 787     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 788     basic_string<_CharT, _Traits, _Alloc>::
 789     find_first_of(const _CharT* __s, size_type __pos, size_type __n) const
 790     {
 791       __glibcxx_requires_string_len(__s, __n);
 792       for (; __n && __pos < this->size(); ++__pos)
 793         {
 794           const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]);
 795           if (__p)
 796             return __pos;
 797         }
 798       return npos;
 799     }
 800
 801   template<typename _CharT, typename _Traits, typename _Alloc>
 802     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 803     basic_string<_CharT, _Traits, _Alloc>::
 804     find_last_of(const _CharT* __s, size_type __pos, size_type __n) const
 805     {
 806       __glibcxx_requires_string_len(__s, __n);
 807       size_type __size = this->size();
 808       if (__size && __n)
 809         {
 810           if (--__size > __pos)
 811             __size = __pos;
 812           do
 813             {
 814               if (traits_type::find(__s, __n, _M_data()[__size]))
 815                 return __size;
 816             }
 817           while (__size-- != 0);
 818         }
 819       return npos;
 820     }
 821
 822   template<typename _CharT, typename _Traits, typename _Alloc>
 823     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 824     basic_string<_CharT, _Traits, _Alloc>::
 825     find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const
 826     {
 827       __glibcxx_requires_string_len(__s, __n);
 828       for (; __pos < this->size(); ++__pos)
 829         if (!traits_type::find(__s, __n, _M_data()[__pos]))
 830           return __pos;
 831       return npos;
 832     }
 833
 834   template<typename _CharT, typename _Traits, typename _Alloc>
 835     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 836     basic_string<_CharT, _Traits, _Alloc>::
 837     find_first_not_of(_CharT __c, size_type __pos) const
 838     {
 839       for (; __pos < this->size(); ++__pos)
 840         if (!traits_type::eq(_M_data()[__pos], __c))
 841           return __pos;
 842       return npos;
 843     }
 844
 845   template<typename _CharT, typename _Traits, typename _Alloc>
 846     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 847     basic_string<_CharT, _Traits, _Alloc>::
 848     find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const
 849     {
 850       __glibcxx_requires_string_len(__s, __n);
 851       size_type __size = this->size();
 852       if (__size)
 853         {
 854           if (--__size > __pos)
 855             __size = __pos;
 856           do
 857             {
 858               if (!traits_type::find(__s, __n, _M_data()[__size]))
 859                 return __size;
 860             }
 861           while (__size--);
 862         }
 863       return npos;
 864     }
 865
 866   template<typename _CharT, typename _Traits, typename _Alloc>
 867     typename basic_string<_CharT, _Traits, _Alloc>::size_type
 868     basic_string<_CharT, _Traits, _Alloc>::
 869     find_last_not_of(_CharT __c, size_type __pos) const
 870     {
 871       size_type __size = this->size();
 872       if (__size)
 873         {
 874           if (--__size > __pos)
 875             __size = __pos;
 876           do
 877             {
 878               if (!traits_type::eq(_M_data()[__size], __c))
 879                 return __size;
 880             }
 881           while (__size--);
 882         }
 883       return npos;
 884     }
 885
 886   template<typename _CharT, typename _Traits, typename _Alloc>
 887     int
 888     basic_string<_CharT, _Traits, _Alloc>::
 889     compare(size_type __pos, size_type __n, const basic_string& __str) const
 890     {
 891       _M_check(__pos, "basic_string::compare");
 892       __n = _M_limit(__pos, __n);
 893       const size_type __osize = __str.size();
 894       const size_type __len = std::min(__n, __osize);
 895       int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len);
 896       if (!__r)
 897         __r = __n - __osize;
 898       return __r;
 899     }
 900
 901   template<typename _CharT, typename _Traits, typename _Alloc>
 902     int
 903     basic_string<_CharT, _Traits, _Alloc>::
 904     compare(size_type __pos1, size_type __n1, const basic_string& __str,
 905             size_type __pos2, size_type __n2) const
 906     {
 907       _M_check(__pos1, "basic_string::compare");
 908       __str._M_check(__pos2, "basic_string::compare");
 909       __n1 = _M_limit(__pos1, __n1);
 910       __n2 = __str._M_limit(__pos2, __n2);
 911       const size_type __len = std::min(__n1, __n2);
 912       int __r = traits_type::compare(_M_data() + __pos1,
 913                                      __str.data() + __pos2, __len);
 914       if (!__r)
 915         __r = __n1 - __n2;
 916       return __r;
 917     }
 918
 919   template<typename _CharT, typename _Traits, typename _Alloc>
 920     int
 921     basic_string<_CharT, _Traits, _Alloc>::
 922     compare(const _CharT* __s) const
 923     {
 924       __glibcxx_requires_string(__s);
 925       const size_type __size = this->size();
 926       const size_type __osize = traits_type::length(__s);
 927       const size_type __len = std::min(__size, __osize);
 928       int __r = traits_type::compare(_M_data(), __s, __len);
 929       if (!__r)
 930         __r = __size - __osize;
 931       return __r;
 932     }
 933
 934   template<typename _CharT, typename _Traits, typename _Alloc>
 935     int
 936     basic_string <_CharT, _Traits, _Alloc>::
 937     compare(size_type __pos, size_type __n1, const _CharT* __s) const
 938     {
 939       __glibcxx_requires_string(__s);
 940       _M_check(__pos, "basic_string::compare");
 941       __n1 = _M_limit(__pos, __n1);
 942       const size_type __osize = traits_type::length(__s);
 943       const size_type __len = std::min(__n1, __osize);
 944       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
 945       if (!__r)
 946         __r = __n1 - __osize;
 947       return __r;
 948     }
 949
 950   template<typename _CharT, typename _Traits, typename _Alloc>
 951     int
 952     basic_string <_CharT, _Traits, _Alloc>::
 953     compare(size_type __pos, size_type __n1, const _CharT* __s,
 954             size_type __n2) const
 955     {
 956       __glibcxx_requires_string_len(__s, __n2);
 957       _M_check(__pos, "basic_string::compare");
 958       __n1 = _M_limit(__pos, __n1);
 959       const size_type __len = std::min(__n1, __n2);
 960       int __r = traits_type::compare(_M_data() + __pos, __s, __len);
 961       if (!__r)
 962         __r = __n1 - __n2;
 963       return __r;
 964     }
 965
 966   // Inhibit implicit instantiations for required instantiations,
 967   // which are defined via explicit instantiations elsewhere.
 968   // NB: This syntax is a GNU extension.
 969 #if _GLIBCXX_EXTERN_TEMPLATE
 970   extern template class basic_string<char>;
 971   extern template
 972     basic_istream<char>&
 973     operator>>(basic_istream<char>&, string&);
 974   extern template
 975     basic_ostream<char>&
 976     operator<<(basic_ostream<char>&, const string&);
 977   extern template
 978     basic_istream<char>&
 979     getline(basic_istream<char>&, string&, char);
 980   extern template
 981     basic_istream<char>&
 982     getline(basic_istream<char>&, string&);
 983
 984 #ifdef _GLIBCXX_USE_WCHAR_T
 985   extern template class basic_string<wchar_t>;
 986   extern template
 987     basic_istream<wchar_t>&
 988     operator>>(basic_istream<wchar_t>&, wstring&);
 989   extern template
 990     basic_ostream<wchar_t>&
 991     operator<<(basic_ostream<wchar_t>&, const wstring&);
 992   extern template
 993     basic_istream<wchar_t>&
 994     getline(basic_istream<wchar_t>&, wstring&, wchar_t);
 995   extern template
 996     basic_istream<wchar_t>&
 997     getline(basic_istream<wchar_t>&, wstring&);
 998 #endif
 999 #endif
1000 } // namespace std
1001
1002 #endif