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