libstdc++-v3/include/ext/rc_string_base.h

   1 // Reference-counted versatile string base -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /** @file ext/rc_string_base.h
  31  *  This file is a GNU extension to the Standard C++ Library.
  32  *  This is an internal header file, included by other library headers.
  33  *  You should not attempt to use it directly.
  34  */
  35
  36 #ifndef _RC_STRING_BASE_H
  37 #define _RC_STRING_BASE_H 1
  38
  39 #include <ext/atomicity.h>
  40 #include <bits/stl_iterator_base_funcs.h>
  41
  42 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
  43
  44   /**
  45    *  @if maint
  46    *  Documentation?  What's that?
  47    *  Nathan Myers <ncm@cantrip.org>.
  48    *
  49    *  A string looks like this:
  50    *
  51    *  @code
  52    *                                        [_Rep]
  53    *                                        _M_length
  54    *   [__rc_string_base<char_type>]        _M_capacity
  55    *   _M_dataplus                          _M_refcount
  56    *   _M_p ---------------->               unnamed array of char_type
  57    *  @endcode
  58    *
  59    *  Where the _M_p points to the first character in the string, and
  60    *  you cast it to a pointer-to-_Rep and subtract 1 to get a
  61    *  pointer to the header.
  62    *
  63    *  This approach has the enormous advantage that a string object
  64    *  requires only one allocation.  All the ugliness is confined
  65    *  within a single pair of inline functions, which each compile to
  66    *  a single "add" instruction: _Rep::_M_refdata(), and
  67    *  __rc_string_base::_M_rep(); and the allocation function which gets a
  68    *  block of raw bytes and with room enough and constructs a _Rep
  69    *  object at the front.
  70    *
  71    *  The reason you want _M_data pointing to the character array and
  72    *  not the _Rep is so that the debugger can see the string
  73    *  contents. (Probably we should add a non-inline member to get
  74    *  the _Rep for the debugger to use, so users can check the actual
  75    *  string length.)
  76    *
  77    *  Note that the _Rep object is a POD so that you can have a
  78    *  static "empty string" _Rep object already "constructed" before
  79    *  static constructors have run.  The reference-count encoding is
  80    *  chosen so that a 0 indicates one reference, so you never try to
  81    *  destroy the empty-string _Rep object.
  82    *
  83    *  All but the last paragraph is considered pretty conventional
  84    *  for a C++ string implementation.
  85    *  @endif
  86   */
  87  template<typename _CharT, typename _Traits, typename _Alloc>
  88     class __rc_string_base
  89     : protected __vstring_utility<_CharT, _Traits, _Alloc>
  90     {
  91     public:
  92       typedef _Traits                                       traits_type;
  93       typedef typename _Traits::char_type                   value_type;
  94       typedef _Alloc                                        allocator_type;
  95
  96       typedef __vstring_utility<_CharT, _Traits, _Alloc>    _Util_Base;
  97       typedef typename _Util_Base::_CharT_alloc_type        _CharT_alloc_type;
  98       typedef typename _CharT_alloc_type::size_type         size_type;
  99
 100     private:
 101       // _Rep: string representation
 102       //   Invariants:
 103       //   1. String really contains _M_length + 1 characters: due to 21.3.4
 104       //      must be kept null-terminated.
 105       //   2. _M_capacity >= _M_length
 106       //      Allocated memory is always (_M_capacity + 1) * sizeof(_CharT).
 107       //   3. _M_refcount has three states:
 108       //      -1: leaked, one reference, no ref-copies allowed, non-const.
 109       //       0: one reference, non-const.
 110       //     n>0: n + 1 references, operations require a lock, const.
 111       //   4. All fields == 0 is an empty string, given the extra storage
 112       //      beyond-the-end for a null terminator; thus, the shared
 113       //      empty string representation needs no constructor.
 114       struct _Rep
 115       {
 116         union
 117         {
 118           struct
 119           {
 120             size_type       _M_length;
 121             size_type       _M_capacity;
 122             _Atomic_word    _M_refcount;
 123           }                 _M_info;
 124
 125           // Only for alignment purposes.
 126           _CharT            _M_align;
 127         };
 128
 129         typedef typename _Alloc::template rebind<_Rep>::other _Rep_alloc_type;
 130
 131         _CharT*
 132         _M_refdata() throw()
 133         { return reinterpret_cast<_CharT*>(this + 1); }
 134
 135         _CharT*
 136         _M_refcopy() throw()
 137         {
 138           __atomic_add_dispatch(&_M_info._M_refcount, 1);
 139           return _M_refdata();
 140         }  // XXX MT
 141
 142         void
 143         _M_set_length(size_type __n)
 144         {
 145           _M_info._M_refcount = 0;  // One reference.
 146           _M_info._M_length = __n;
 147           // grrr. (per 21.3.4)
 148           // You cannot leave those LWG people alone for a second.
 149           traits_type::assign(_M_refdata()[__n], _CharT());
 150         }
 151
 152         // Create & Destroy
 153         static _Rep*
 154         _S_create(size_type, size_type, const _Alloc&);
 155
 156         void
 157         _M_destroy(const _Alloc&) throw();
 158
 159         _CharT*
 160         _M_clone(const _Alloc&, size_type __res = 0);
 161       };
 162
 163       struct _Rep_empty
 164       : public _Rep
 165       {
 166         _CharT              _M_terminal;
 167       };
 168
 169       static _Rep_empty     _S_empty_rep;
 170
 171       // The maximum number of individual char_type elements of an
 172       // individual string is determined by _S_max_size. This is the
 173       // value that will be returned by max_size().  (Whereas npos
 174       // is the maximum number of bytes the allocator can allocate.)
 175       // If one was to divvy up the theoretical largest size string,
 176       // with a terminating character and m _CharT elements, it'd
 177       // look like this:
 178       // npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)
 179       //        + sizeof(_Rep) - 1
 180       // (NB: last two terms for rounding reasons, see _M_create below)
 181       // Solving for m:
 182       // m = ((npos - 2 * sizeof(_Rep) + 1) / sizeof(_CharT)) - 1
 183       // In addition, this implementation halfs this amount.
 184       enum { _S_max_size = (((static_cast<size_type>(-1) - 2 * sizeof(_Rep)
 185                               + 1) / sizeof(_CharT)) - 1) / 2 };
 186
 187       // Data Member (private):
 188       mutable typename _Util_Base::template _Alloc_hider<_Alloc>  _M_dataplus;
 189
 190       void
 191       _M_data(_CharT* __p)
 192       { _M_dataplus._M_p = __p; }
 193
 194       _Rep*
 195       _M_rep() const
 196       { return &((reinterpret_cast<_Rep*>(_M_data()))[-1]); }
 197
 198       _CharT*
 199       _M_grab(const _Alloc& __alloc) const
 200       {
 201         return (!_M_is_leaked() && _M_get_allocator() == __alloc)
 202                 ? _M_rep()->_M_refcopy() : _M_rep()->_M_clone(__alloc);
 203       }
 204
 205       void
 206       _M_dispose()
 207       {
 208         if (__exchange_and_add_dispatch(&_M_rep()->_M_info._M_refcount,
 209                                         -1) <= 0)
 210           _M_rep()->_M_destroy(_M_get_allocator());
 211       }  // XXX MT
 212
 213       bool
 214       _M_is_leaked() const
 215       { return _M_rep()->_M_info._M_refcount < 0; }
 216
 217       void
 218       _M_set_sharable()
 219       { _M_rep()->_M_info._M_refcount = 0; }
 220
 221       void
 222       _M_leak_hard();
 223
 224       // _S_construct_aux is used to implement the 21.3.1 para 15 which
 225       // requires special behaviour if _InIterator is an integral type
 226       template<typename _InIterator>
 227         static _CharT*
 228         _S_construct_aux(_InIterator __beg, _InIterator __end,
 229                          const _Alloc& __a, std::__false_type)
 230         {
 231           typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
 232           return _S_construct(__beg, __end, __a, _Tag());
 233         }
 234
 235       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 236       // 438. Ambiguity in the "do the right thing" clause
 237       template<typename _Integer>
 238         static _CharT*
 239         _S_construct_aux(_Integer __beg, _Integer __end,
 240                          const _Alloc& __a, std::__true_type)
 241         { return _S_construct(static_cast<size_type>(__beg), __end, __a); }
 242
 243       template<typename _InIterator>
 244         static _CharT*
 245         _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a)
 246         {
 247           typedef typename std::__is_integer<_InIterator>::__type _Integral;
 248           return _S_construct_aux(__beg, __end, __a, _Integral());
 249         }
 250
 251       // For Input Iterators, used in istreambuf_iterators, etc.
 252       template<typename _InIterator>
 253         static _CharT*
 254          _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
 255                       std::input_iterator_tag);
 256
 257       // For forward_iterators up to random_access_iterators, used for
 258       // string::iterator, _CharT*, etc.
 259       template<typename _FwdIterator>
 260         static _CharT*
 261         _S_construct(_FwdIterator __beg, _FwdIterator __end, const _Alloc& __a,
 262                      std::forward_iterator_tag);
 263
 264       static _CharT*
 265       _S_construct(size_type __req, _CharT __c, const _Alloc& __a);
 266
 267     public:
 268       size_type
 269       _M_max_size() const
 270       { return size_type(_S_max_size); }
 271
 272       _CharT*
 273       _M_data() const
 274       { return _M_dataplus._M_p; }
 275
 276       size_type
 277       _M_length() const
 278       { return _M_rep()->_M_info._M_length; }
 279
 280       size_type
 281       _M_capacity() const
 282       { return _M_rep()->_M_info._M_capacity; }
 283
 284       bool
 285       _M_is_shared() const
 286       { return _M_rep()->_M_info._M_refcount > 0; }
 287
 288       void
 289       _M_set_leaked()
 290       { _M_rep()->_M_info._M_refcount = -1; }
 291
 292       void
 293       _M_leak()    // for use in begin() & non-const op[]
 294       {
 295         if (!_M_is_leaked())
 296           _M_leak_hard();
 297       }
 298
 299       void
 300       _M_set_length(size_type __n)
 301       { _M_rep()->_M_set_length(__n); }
 302
 303       __rc_string_base()
 304       : _M_dataplus(_S_empty_rep._M_refcopy()) { }
 305
 306       __rc_string_base(const _Alloc& __a);
 307
 308       __rc_string_base(const __rc_string_base& __rcs);
 309
 310 #ifdef __GXX_EXPERIMENTAL_CXX0X__
 311       __rc_string_base(__rc_string_base&& __rcs)
 312       : _M_dataplus(__rcs._M_get_allocator(), __rcs._M_data())
 313       { __rcs._M_data(_S_empty_rep._M_refcopy()); }
 314 #endif
 315
 316       __rc_string_base(size_type __n, _CharT __c, const _Alloc& __a);
 317
 318       template<typename _InputIterator>
 319         __rc_string_base(_InputIterator __beg, _InputIterator __end,
 320                          const _Alloc& __a);
 321
 322       ~__rc_string_base()
 323       { _M_dispose(); }
 324
 325       allocator_type&
 326       _M_get_allocator()
 327       { return _M_dataplus; }
 328
 329       const allocator_type&
 330       _M_get_allocator() const
 331       { return _M_dataplus; }
 332
 333       void
 334       _M_swap(__rc_string_base& __rcs);
 335
 336       void
 337       _M_assign(const __rc_string_base& __rcs);
 338
 339       void
 340       _M_reserve(size_type __res);
 341
 342       void
 343       _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
 344                 size_type __len2);
 345
 346       void
 347       _M_erase(size_type __pos, size_type __n);
 348
 349       void
 350       _M_clear()
 351       { _M_erase(size_type(0), _M_length()); }
 352
 353       bool
 354       _M_compare(const __rc_string_base&) const
 355       { return false; }
 356     };
 357
 358   template<typename _CharT, typename _Traits, typename _Alloc>
 359     typename __rc_string_base<_CharT, _Traits, _Alloc>::_Rep_empty
 360     __rc_string_base<_CharT, _Traits, _Alloc>::_S_empty_rep;
 361
 362   template<typename _CharT, typename _Traits, typename _Alloc>
 363     typename __rc_string_base<_CharT, _Traits, _Alloc>::_Rep*
 364     __rc_string_base<_CharT, _Traits, _Alloc>::_Rep::
 365     _S_create(size_type __capacity, size_type __old_capacity,
 366               const _Alloc& __alloc)
 367     {
 368       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 369       // 83.  String::npos vs. string::max_size()
 370       if (__capacity > size_type(_S_max_size))
 371         std::__throw_length_error(__N("__rc_string_base::_Rep::_S_create"));
 372
 373       // The standard places no restriction on allocating more memory
 374       // than is strictly needed within this layer at the moment or as
 375       // requested by an explicit application call to reserve().
 376
 377       // Many malloc implementations perform quite poorly when an
 378       // application attempts to allocate memory in a stepwise fashion
 379       // growing each allocation size by only 1 char.  Additionally,
 380       // it makes little sense to allocate less linear memory than the
 381       // natural blocking size of the malloc implementation.
 382       // Unfortunately, we would need a somewhat low-level calculation
 383       // with tuned parameters to get this perfect for any particular
 384       // malloc implementation.  Fortunately, generalizations about
 385       // common features seen among implementations seems to suffice.
 386
 387       // __pagesize need not match the actual VM page size for good
 388       // results in practice, thus we pick a common value on the low
 389       // side.  __malloc_header_size is an estimate of the amount of
 390       // overhead per memory allocation (in practice seen N * sizeof
 391       // (void*) where N is 0, 2 or 4).  According to folklore,
 392       // picking this value on the high side is better than
 393       // low-balling it (especially when this algorithm is used with
 394       // malloc implementations that allocate memory blocks rounded up
 395       // to a size which is a power of 2).
 396       const size_type __pagesize = 4096;
 397       const size_type __malloc_header_size = 4 * sizeof(void*);
 398
 399       // The below implements an exponential growth policy, necessary to
 400       // meet amortized linear time requirements of the library: see
 401       // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
 402       if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
 403         {
 404           __capacity = 2 * __old_capacity;
 405           // Never allocate a string bigger than _S_max_size.
 406           if (__capacity > size_type(_S_max_size))
 407             __capacity = size_type(_S_max_size);
 408         }
 409
 410       // NB: Need an array of char_type[__capacity], plus a terminating
 411       // null char_type() element, plus enough for the _Rep data structure,
 412       // plus sizeof(_Rep) - 1 to upper round to a size multiple of
 413       // sizeof(_Rep).
 414       // Whew. Seemingly so needy, yet so elemental.
 415       size_type __size = ((__capacity + 1) * sizeof(_CharT)
 416                           + 2 * sizeof(_Rep) - 1);
 417
 418       const size_type __adj_size = __size + __malloc_header_size;
 419       if (__adj_size > __pagesize && __capacity > __old_capacity)
 420         {
 421           const size_type __extra = __pagesize - __adj_size % __pagesize;
 422           __capacity += __extra / sizeof(_CharT);
 423           if (__capacity > size_type(_S_max_size))
 424             __capacity = size_type(_S_max_size);
 425           __size = (__capacity + 1) * sizeof(_CharT) + 2 * sizeof(_Rep) - 1;
 426         }
 427
 428       // NB: Might throw, but no worries about a leak, mate: _Rep()
 429       // does not throw.
 430       _Rep* __place = _Rep_alloc_type(__alloc).allocate(__size / sizeof(_Rep));
 431       _Rep* __p = new (__place) _Rep;
 432       __p->_M_info._M_capacity = __capacity;
 433       return __p;
 434     }
 435
 436   template<typename _CharT, typename _Traits, typename _Alloc>
 437     void
 438     __rc_string_base<_CharT, _Traits, _Alloc>::_Rep::
 439     _M_destroy(const _Alloc& __a) throw ()
 440     {
 441       const size_type __size = ((_M_info._M_capacity + 1) * sizeof(_CharT)
 442                                 + 2 * sizeof(_Rep) - 1);
 443       _Rep_alloc_type(__a).deallocate(this, __size / sizeof(_Rep));
 444     }
 445
 446   template<typename _CharT, typename _Traits, typename _Alloc>
 447     _CharT*
 448     __rc_string_base<_CharT, _Traits, _Alloc>::_Rep::
 449     _M_clone(const _Alloc& __alloc, size_type __res)
 450     {
 451       // Requested capacity of the clone.
 452       const size_type __requested_cap = _M_info._M_length + __res;
 453       _Rep* __r = _Rep::_S_create(__requested_cap, _M_info._M_capacity,
 454                                   __alloc);
 455
 456       if (_M_info._M_length)
 457         _S_copy(__r->_M_refdata(), _M_refdata(), _M_info._M_length);
 458
 459       __r->_M_set_length(_M_info._M_length);
 460       return __r->_M_refdata();
 461     }
 462
 463   template<typename _CharT, typename _Traits, typename _Alloc>
 464     __rc_string_base<_CharT, _Traits, _Alloc>::
 465     __rc_string_base(const _Alloc& __a)
 466     : _M_dataplus(__a, _S_construct(size_type(), _CharT(), __a)) { }
 467
 468   template<typename _CharT, typename _Traits, typename _Alloc>
 469     __rc_string_base<_CharT, _Traits, _Alloc>::
 470     __rc_string_base(const __rc_string_base& __rcs)
 471     : _M_dataplus(__rcs._M_get_allocator(),
 472                   __rcs._M_grab(__rcs._M_get_allocator())) { }
 473
 474   template<typename _CharT, typename _Traits, typename _Alloc>
 475     __rc_string_base<_CharT, _Traits, _Alloc>::
 476     __rc_string_base(size_type __n, _CharT __c, const _Alloc& __a)
 477     : _M_dataplus(__a, _S_construct(__n, __c, __a)) { }
 478
 479   template<typename _CharT, typename _Traits, typename _Alloc>
 480     template<typename _InputIterator>
 481     __rc_string_base<_CharT, _Traits, _Alloc>::
 482     __rc_string_base(_InputIterator __beg, _InputIterator __end,
 483                      const _Alloc& __a)
 484     : _M_dataplus(__a, _S_construct(__beg, __end, __a)) { }
 485
 486   template<typename _CharT, typename _Traits, typename _Alloc>
 487     void
 488     __rc_string_base<_CharT, _Traits, _Alloc>::
 489     _M_leak_hard()
 490     {
 491       if (_M_is_shared())
 492         _M_erase(0, 0);
 493       _M_set_leaked();
 494     }
 495
 496   // NB: This is the special case for Input Iterators, used in
 497   // istreambuf_iterators, etc.
 498   // Input Iterators have a cost structure very different from
 499   // pointers, calling for a different coding style.
 500   template<typename _CharT, typename _Traits, typename _Alloc>
 501     template<typename _InIterator>
 502       _CharT*
 503       __rc_string_base<_CharT, _Traits, _Alloc>::
 504       _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
 505                    std::input_iterator_tag)
 506       {
 507         if (__beg == __end && __a == _Alloc())
 508           return _S_empty_rep._M_refcopy();
 509
 510         // Avoid reallocation for common case.
 511         _CharT __buf[128];
 512         size_type __len = 0;
 513         while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT))
 514           {
 515             __buf[__len++] = *__beg;
 516             ++__beg;
 517           }
 518         _Rep* __r = _Rep::_S_create(__len, size_type(0), __a);
 519         _S_copy(__r->_M_refdata(), __buf, __len);
 520         try
 521           {
 522             while (__beg != __end)
 523               {
 524                 if (__len == __r->_M_info._M_capacity)
 525                   {
 526                     // Allocate more space.
 527                     _Rep* __another = _Rep::_S_create(__len + 1, __len, __a);
 528                     _S_copy(__another->_M_refdata(), __r->_M_refdata(), __len);
 529                     __r->_M_destroy(__a);
 530                     __r = __another;
 531                   }
 532                 __r->_M_refdata()[__len++] = *__beg;
 533                 ++__beg;
 534               }
 535           }
 536         catch(...)
 537           {
 538             __r->_M_destroy(__a);
 539             __throw_exception_again;
 540           }
 541         __r->_M_set_length(__len);
 542         return __r->_M_refdata();
 543       }
 544
 545   template<typename _CharT, typename _Traits, typename _Alloc>
 546     template<typename _InIterator>
 547       _CharT*
 548       __rc_string_base<_CharT, _Traits, _Alloc>::
 549       _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
 550                    std::forward_iterator_tag)
 551       {
 552         if (__beg == __end && __a == _Alloc())
 553           return _S_empty_rep._M_refcopy();
 554
 555         // NB: Not required, but considered best practice.
 556         if (__builtin_expect(__is_null_pointer(__beg) && __beg != __end, 0))
 557           std::__throw_logic_error(__N("__rc_string_base::"
 558                                        "_S_construct NULL not valid"));
 559
 560         const size_type __dnew = static_cast<size_type>(std::distance(__beg,
 561                                                                       __end));
 562         // Check for out_of_range and length_error exceptions.
 563         _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a);
 564         try
 565           { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
 566         catch(...)
 567           {
 568             __r->_M_destroy(__a);
 569             __throw_exception_again;
 570           }
 571         __r->_M_set_length(__dnew);
 572         return __r->_M_refdata();
 573       }
 574
 575   template<typename _CharT, typename _Traits, typename _Alloc>
 576     _CharT*
 577     __rc_string_base<_CharT, _Traits, _Alloc>::
 578     _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
 579     {
 580       if (__n == 0 && __a == _Alloc())
 581         return _S_empty_rep._M_refcopy();
 582
 583       // Check for out_of_range and length_error exceptions.
 584       _Rep* __r = _Rep::_S_create(__n, size_type(0), __a);
 585       if (__n)
 586         _S_assign(__r->_M_refdata(), __n, __c);
 587
 588       __r->_M_set_length(__n);
 589       return __r->_M_refdata();
 590     }
 591
 592   template<typename _CharT, typename _Traits, typename _Alloc>
 593     void
 594     __rc_string_base<_CharT, _Traits, _Alloc>::
 595     _M_swap(__rc_string_base& __rcs)
 596     {
 597       if (_M_is_leaked())
 598         _M_set_sharable();
 599       if (__rcs._M_is_leaked())
 600         __rcs._M_set_sharable();
 601
 602       _CharT* __tmp = _M_data();
 603       _M_data(__rcs._M_data());
 604       __rcs._M_data(__tmp);
 605
 606       // _GLIBCXX_RESOLVE_LIB_DEFECTS
 607       // 431. Swapping containers with unequal allocators.
 608       std::__alloc_swap<allocator_type>::_S_do_it(_M_get_allocator(),
 609                                                   __rcs._M_get_allocator());
 610     }
 611
 612   template<typename _CharT, typename _Traits, typename _Alloc>
 613     void
 614     __rc_string_base<_CharT, _Traits, _Alloc>::
 615     _M_assign(const __rc_string_base& __rcs)
 616     {
 617       if (_M_rep() != __rcs._M_rep())
 618         {
 619           _CharT* __tmp = __rcs._M_grab(_M_get_allocator());
 620           _M_dispose();
 621           _M_data(__tmp);
 622         }
 623     }
 624
 625   template<typename _CharT, typename _Traits, typename _Alloc>
 626     void
 627     __rc_string_base<_CharT, _Traits, _Alloc>::
 628     _M_reserve(size_type __res)
 629     {
 630       // Make sure we don't shrink below the current size.
 631       if (__res < _M_length())
 632         __res = _M_length();
 633
 634       if (__res != _M_capacity() || _M_is_shared())
 635         {
 636           _CharT* __tmp = _M_rep()->_M_clone(_M_get_allocator(),
 637                                              __res - _M_length());
 638           _M_dispose();
 639           _M_data(__tmp);
 640         }
 641     }
 642
 643   template<typename _CharT, typename _Traits, typename _Alloc>
 644     void
 645     __rc_string_base<_CharT, _Traits, _Alloc>::
 646     _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
 647               size_type __len2)
 648     {
 649       const size_type __how_much = _M_length() - __pos - __len1;
 650
 651       _Rep* __r = _Rep::_S_create(_M_length() + __len2 - __len1,
 652                                   _M_capacity(), _M_get_allocator());
 653
 654       if (__pos)
 655         _S_copy(__r->_M_refdata(), _M_data(), __pos);
 656       if (__s && __len2)
 657         _S_copy(__r->_M_refdata() + __pos, __s, __len2);
 658       if (__how_much)
 659         _S_copy(__r->_M_refdata() + __pos + __len2,
 660                 _M_data() + __pos + __len1, __how_much);
 661
 662       _M_dispose();
 663       _M_data(__r->_M_refdata());
 664     }
 665
 666   template<typename _CharT, typename _Traits, typename _Alloc>
 667     void
 668     __rc_string_base<_CharT, _Traits, _Alloc>::
 669     _M_erase(size_type __pos, size_type __n)
 670     {
 671       const size_type __new_size = _M_length() - __n;
 672       const size_type __how_much = _M_length() - __pos - __n;
 673
 674       if (_M_is_shared())
 675         {
 676           // Must reallocate.
 677           _Rep* __r = _Rep::_S_create(__new_size, _M_capacity(),
 678                                       _M_get_allocator());
 679
 680           if (__pos)
 681             _S_copy(__r->_M_refdata(), _M_data(), __pos);
 682           if (__how_much)
 683             _S_copy(__r->_M_refdata() + __pos,
 684                     _M_data() + __pos + __n, __how_much);
 685
 686           _M_dispose();
 687           _M_data(__r->_M_refdata());
 688         }
 689       else if (__how_much && __n)
 690         {
 691           // Work in-place.
 692           _S_move(_M_data() + __pos,
 693                   _M_data() + __pos + __n, __how_much);
 694         }
 695
 696       _M_rep()->_M_set_length(__new_size);
 697     }
 698
 699   template<>
 700     inline bool
 701     __rc_string_base<char, std::char_traits<char>,
 702                      std::allocator<char> >::
 703     _M_compare(const __rc_string_base& __rcs) const
 704     {
 705       if (_M_rep() == __rcs._M_rep())
 706         return true;
 707       return false;
 708     }
 709
 710 #ifdef _GLIBCXX_USE_WCHAR_T
 711   template<>
 712     inline bool
 713     __rc_string_base<wchar_t, std::char_traits<wchar_t>,
 714                      std::allocator<wchar_t> >::
 715     _M_compare(const __rc_string_base& __rcs) const
 716     {
 717       if (_M_rep() == __rcs._M_rep())
 718         return true;
 719       return false;
 720     }
 721 #endif
 722
 723 _GLIBCXX_END_NAMESPACE
 724
 725 #endif /* _RC_STRING_BASE_H */