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