libstdc++
rc_string_base.h
Go to the documentation of this file.
00001 // Reference-counted versatile string base -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the
00008 // terms of the GNU General Public License as published by the
00009 // Free Software Foundation; either version 3, or (at your option)
00010 // any later version.
00011 
00012 // This library is distributed in the hope that it will be useful,
00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015 // GNU General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 /** @file ext/rc_string_base.h
00027  *  This is an internal header file, included by other library headers.
00028  *  Do not attempt to use it directly. @headername{ext/vstring.h}
00029  */
00030 
00031 #ifndef _RC_STRING_BASE_H
00032 #define _RC_STRING_BASE_H 1
00033 
00034 #include <ext/atomicity.h>
00035 #include <bits/stl_iterator_base_funcs.h>
00036 
00037 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00038 {
00039 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00040 
00041   /**
00042    *  Documentation?  What's that?
00043    *  Nathan Myers <ncm@cantrip.org>.
00044    *
00045    *  A string looks like this:
00046    *
00047    *  @code
00048    *                                        [_Rep]
00049    *                                        _M_length
00050    *   [__rc_string_base<char_type>]        _M_capacity
00051    *   _M_dataplus                          _M_refcount
00052    *   _M_p ---------------->               unnamed array of char_type
00053    *  @endcode
00054    *
00055    *  Where the _M_p points to the first character in the string, and
00056    *  you cast it to a pointer-to-_Rep and subtract 1 to get a
00057    *  pointer to the header.
00058    *
00059    *  This approach has the enormous advantage that a string object
00060    *  requires only one allocation.  All the ugliness is confined
00061    *  within a single pair of inline functions, which each compile to
00062    *  a single @a add instruction: _Rep::_M_refdata(), and
00063    *  __rc_string_base::_M_rep(); and the allocation function which gets a
00064    *  block of raw bytes and with room enough and constructs a _Rep
00065    *  object at the front.
00066    *
00067    *  The reason you want _M_data pointing to the character array and
00068    *  not the _Rep is so that the debugger can see the string
00069    *  contents. (Probably we should add a non-inline member to get
00070    *  the _Rep for the debugger to use, so users can check the actual
00071    *  string length.)
00072    *
00073    *  Note that the _Rep object is a POD so that you can have a
00074    *  static <em>empty string</em> _Rep object already @a constructed before
00075    *  static constructors have run.  The reference-count encoding is
00076    *  chosen so that a 0 indicates one reference, so you never try to
00077    *  destroy the empty-string _Rep object.
00078    *
00079    *  All but the last paragraph is considered pretty conventional
00080    *  for a C++ string implementation.
00081   */
00082  template<typename _CharT, typename _Traits, typename _Alloc>
00083     class __rc_string_base
00084     : protected __vstring_utility<_CharT, _Traits, _Alloc>
00085     {
00086     public:
00087       typedef _Traits                       traits_type;
00088       typedef typename _Traits::char_type           value_type;
00089       typedef _Alloc                        allocator_type;
00090 
00091       typedef __vstring_utility<_CharT, _Traits, _Alloc>    _Util_Base;
00092       typedef typename _Util_Base::_CharT_alloc_type        _CharT_alloc_type;
00093       typedef typename _CharT_alloc_type::size_type     size_type;
00094 
00095     private:
00096       // _Rep: string representation
00097       //   Invariants:
00098       //   1. String really contains _M_length + 1 characters: due to 21.3.4
00099       //      must be kept null-terminated.
00100       //   2. _M_capacity >= _M_length
00101       //      Allocated memory is always (_M_capacity + 1) * sizeof(_CharT).
00102       //   3. _M_refcount has three states:
00103       //      -1: leaked, one reference, no ref-copies allowed, non-const.
00104       //       0: one reference, non-const.
00105       //     n>0: n + 1 references, operations require a lock, const.
00106       //   4. All fields == 0 is an empty string, given the extra storage
00107       //      beyond-the-end for a null terminator; thus, the shared
00108       //      empty string representation needs no constructor.
00109       struct _Rep
00110       {
00111     union
00112     {
00113       struct
00114       {
00115         size_type       _M_length;
00116         size_type       _M_capacity;
00117         _Atomic_word    _M_refcount;
00118       }                 _M_info;
00119 
00120       // Only for alignment purposes.
00121       _CharT            _M_align;
00122     };
00123 
00124     typedef typename _Alloc::template rebind<_Rep>::other _Rep_alloc_type;
00125 
00126     _CharT*
00127     _M_refdata() throw()
00128     { return reinterpret_cast<_CharT*>(this + 1); }
00129 
00130     _CharT*
00131     _M_refcopy() throw()
00132     {
00133       __atomic_add_dispatch(&_M_info._M_refcount, 1);
00134       return _M_refdata();
00135     }  // XXX MT
00136 
00137     void
00138     _M_set_length(size_type __n)
00139     {
00140       _M_info._M_refcount = 0;  // One reference.
00141       _M_info._M_length = __n;
00142       // grrr. (per 21.3.4)
00143       // You cannot leave those LWG people alone for a second.
00144       traits_type::assign(_M_refdata()[__n], _CharT());
00145     }
00146 
00147     // Create & Destroy
00148     static _Rep*
00149     _S_create(size_type, size_type, const _Alloc&);
00150 
00151     void
00152     _M_destroy(const _Alloc&) throw();
00153 
00154     _CharT*
00155     _M_clone(const _Alloc&, size_type __res = 0);
00156       };
00157 
00158       struct _Rep_empty
00159       : public _Rep
00160       {
00161     _CharT              _M_terminal;
00162       };
00163 
00164       static _Rep_empty     _S_empty_rep;
00165 
00166       // The maximum number of individual char_type elements of an
00167       // individual string is determined by _S_max_size. This is the
00168       // value that will be returned by max_size().  (Whereas npos
00169       // is the maximum number of bytes the allocator can allocate.)
00170       // If one was to divvy up the theoretical largest size string,
00171       // with a terminating character and m _CharT elements, it'd
00172       // look like this:
00173       // npos = sizeof(_Rep) + (m * sizeof(_CharT)) + sizeof(_CharT)
00174       //        + sizeof(_Rep) - 1
00175       // (NB: last two terms for rounding reasons, see _M_create below)
00176       // Solving for m:
00177       // m = ((npos - 2 * sizeof(_Rep) + 1) / sizeof(_CharT)) - 1
00178       // In addition, this implementation halves this amount.
00179       enum { _S_max_size = (((static_cast<size_type>(-1) - 2 * sizeof(_Rep)
00180                   + 1) / sizeof(_CharT)) - 1) / 2 };
00181 
00182       // Data Member (private):
00183       mutable typename _Util_Base::template _Alloc_hider<_Alloc>  _M_dataplus;
00184 
00185       void
00186       _M_data(_CharT* __p)
00187       { _M_dataplus._M_p = __p; }
00188 
00189       _Rep*
00190       _M_rep() const
00191       { return &((reinterpret_cast<_Rep*>(_M_data()))[-1]); }
00192 
00193       _CharT*
00194       _M_grab(const _Alloc& __alloc) const
00195       {
00196     return (!_M_is_leaked() && _M_get_allocator() == __alloc)
00197         ? _M_rep()->_M_refcopy() : _M_rep()->_M_clone(__alloc);
00198       }
00199 
00200       void
00201       _M_dispose()
00202       {
00203     // Be race-detector-friendly.  For more info see bits/c++config.
00204     _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&_M_rep()->_M_info.
00205                         _M_refcount);
00206     if (__exchange_and_add_dispatch(&_M_rep()->_M_info._M_refcount,
00207                     -1) <= 0)
00208       {
00209         _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&_M_rep()->_M_info.
00210                            _M_refcount);
00211         _M_rep()->_M_destroy(_M_get_allocator());
00212       }
00213       }  // XXX MT
00214 
00215       bool
00216       _M_is_leaked() const
00217       { return _M_rep()->_M_info._M_refcount < 0; }
00218 
00219       void
00220       _M_set_sharable()
00221       { _M_rep()->_M_info._M_refcount = 0; }
00222 
00223       void
00224       _M_leak_hard();
00225 
00226       // _S_construct_aux is used to implement the 21.3.1 para 15 which
00227       // requires special behaviour if _InIterator is an integral type
00228       template<typename _InIterator>
00229     static _CharT*
00230     _S_construct_aux(_InIterator __beg, _InIterator __end,
00231              const _Alloc& __a, std::__false_type)
00232     {
00233       typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
00234       return _S_construct(__beg, __end, __a, _Tag());
00235     }
00236 
00237       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00238       // 438. Ambiguity in the "do the right thing" clause
00239       template<typename _Integer>
00240     static _CharT*
00241     _S_construct_aux(_Integer __beg, _Integer __end,
00242              const _Alloc& __a, std::__true_type)
00243     { return _S_construct_aux_2(static_cast<size_type>(__beg),
00244                     __end, __a); }
00245 
00246       static _CharT*
00247       _S_construct_aux_2(size_type __req, _CharT __c, const _Alloc& __a)
00248       { return _S_construct(__req, __c, __a); }
00249 
00250       template<typename _InIterator>
00251     static _CharT*
00252     _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a)
00253     {
00254       typedef typename std::__is_integer<_InIterator>::__type _Integral;
00255       return _S_construct_aux(__beg, __end, __a, _Integral());
00256     }
00257 
00258       // For Input Iterators, used in istreambuf_iterators, etc.
00259       template<typename _InIterator>
00260     static _CharT*
00261      _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
00262               std::input_iterator_tag);
00263 
00264       // For forward_iterators up to random_access_iterators, used for
00265       // string::iterator, _CharT*, etc.
00266       template<typename _FwdIterator>
00267     static _CharT*
00268     _S_construct(_FwdIterator __beg, _FwdIterator __end, const _Alloc& __a,
00269              std::forward_iterator_tag);
00270 
00271       static _CharT*
00272       _S_construct(size_type __req, _CharT __c, const _Alloc& __a);
00273 
00274     public:
00275       size_type
00276       _M_max_size() const
00277       { return size_type(_S_max_size); }
00278 
00279       _CharT*
00280       _M_data() const
00281       { return _M_dataplus._M_p; }
00282 
00283       size_type
00284       _M_length() const
00285       { return _M_rep()->_M_info._M_length; }
00286 
00287       size_type
00288       _M_capacity() const
00289       { return _M_rep()->_M_info._M_capacity; }
00290 
00291       bool
00292       _M_is_shared() const
00293       { return _M_rep()->_M_info._M_refcount > 0; }
00294 
00295       void
00296       _M_set_leaked()
00297       { _M_rep()->_M_info._M_refcount = -1; }
00298 
00299       void
00300       _M_leak()    // for use in begin() & non-const op[]
00301       {
00302     if (!_M_is_leaked())
00303       _M_leak_hard();
00304       }
00305 
00306       void
00307       _M_set_length(size_type __n)
00308       { _M_rep()->_M_set_length(__n); }
00309 
00310       __rc_string_base()
00311       : _M_dataplus(_S_empty_rep._M_refcopy()) { }
00312 
00313       __rc_string_base(const _Alloc& __a);
00314 
00315       __rc_string_base(const __rc_string_base& __rcs);
00316 
00317 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00318       __rc_string_base(__rc_string_base&& __rcs)
00319       : _M_dataplus(__rcs._M_dataplus)
00320       { __rcs._M_data(_S_empty_rep._M_refcopy()); }
00321 #endif
00322 
00323       __rc_string_base(size_type __n, _CharT __c, const _Alloc& __a);
00324 
00325       template<typename _InputIterator>
00326     __rc_string_base(_InputIterator __beg, _InputIterator __end,
00327              const _Alloc& __a);
00328 
00329       ~__rc_string_base()
00330       { _M_dispose(); }
00331 
00332       allocator_type&
00333       _M_get_allocator()
00334       { return _M_dataplus; }
00335 
00336       const allocator_type&
00337       _M_get_allocator() const
00338       { return _M_dataplus; }
00339 
00340       void
00341       _M_swap(__rc_string_base& __rcs);
00342 
00343       void
00344       _M_assign(const __rc_string_base& __rcs);
00345 
00346       void
00347       _M_reserve(size_type __res);
00348 
00349       void
00350       _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
00351         size_type __len2);
00352 
00353       void
00354       _M_erase(size_type __pos, size_type __n);
00355 
00356       void
00357       _M_clear()
00358       { _M_erase(size_type(0), _M_length()); }
00359 
00360       bool
00361       _M_compare(const __rc_string_base&) const
00362       { return false; }
00363     };
00364 
00365   template<typename _CharT, typename _Traits, typename _Alloc>
00366     typename __rc_string_base<_CharT, _Traits, _Alloc>::_Rep_empty
00367     __rc_string_base<_CharT, _Traits, _Alloc>::_S_empty_rep;
00368 
00369   template<typename _CharT, typename _Traits, typename _Alloc>
00370     typename __rc_string_base<_CharT, _Traits, _Alloc>::_Rep*
00371     __rc_string_base<_CharT, _Traits, _Alloc>::_Rep::
00372     _S_create(size_type __capacity, size_type __old_capacity,
00373           const _Alloc& __alloc)
00374     {
00375       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00376       // 83.  String::npos vs. string::max_size()
00377       if (__capacity > size_type(_S_max_size))
00378     std::__throw_length_error(__N("__rc_string_base::_Rep::_S_create"));
00379 
00380       // The standard places no restriction on allocating more memory
00381       // than is strictly needed within this layer at the moment or as
00382       // requested by an explicit application call to reserve().
00383 
00384       // Many malloc implementations perform quite poorly when an
00385       // application attempts to allocate memory in a stepwise fashion
00386       // growing each allocation size by only 1 char.  Additionally,
00387       // it makes little sense to allocate less linear memory than the
00388       // natural blocking size of the malloc implementation.
00389       // Unfortunately, we would need a somewhat low-level calculation
00390       // with tuned parameters to get this perfect for any particular
00391       // malloc implementation.  Fortunately, generalizations about
00392       // common features seen among implementations seems to suffice.
00393 
00394       // __pagesize need not match the actual VM page size for good
00395       // results in practice, thus we pick a common value on the low
00396       // side.  __malloc_header_size is an estimate of the amount of
00397       // overhead per memory allocation (in practice seen N * sizeof
00398       // (void*) where N is 0, 2 or 4).  According to folklore,
00399       // picking this value on the high side is better than
00400       // low-balling it (especially when this algorithm is used with
00401       // malloc implementations that allocate memory blocks rounded up
00402       // to a size which is a power of 2).
00403       const size_type __pagesize = 4096;
00404       const size_type __malloc_header_size = 4 * sizeof(void*);
00405 
00406       // The below implements an exponential growth policy, necessary to
00407       // meet amortized linear time requirements of the library: see
00408       // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html.
00409       if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
00410     {
00411       __capacity = 2 * __old_capacity;
00412       // Never allocate a string bigger than _S_max_size.
00413       if (__capacity > size_type(_S_max_size))
00414         __capacity = size_type(_S_max_size);
00415     }
00416 
00417       // NB: Need an array of char_type[__capacity], plus a terminating
00418       // null char_type() element, plus enough for the _Rep data structure,
00419       // plus sizeof(_Rep) - 1 to upper round to a size multiple of
00420       // sizeof(_Rep).
00421       // Whew. Seemingly so needy, yet so elemental.
00422       size_type __size = ((__capacity + 1) * sizeof(_CharT)
00423               + 2 * sizeof(_Rep) - 1);
00424 
00425       const size_type __adj_size = __size + __malloc_header_size;
00426       if (__adj_size > __pagesize && __capacity > __old_capacity)
00427     {
00428       const size_type __extra = __pagesize - __adj_size % __pagesize;
00429       __capacity += __extra / sizeof(_CharT);
00430       if (__capacity > size_type(_S_max_size))
00431         __capacity = size_type(_S_max_size);
00432       __size = (__capacity + 1) * sizeof(_CharT) + 2 * sizeof(_Rep) - 1;
00433     }
00434 
00435       // NB: Might throw, but no worries about a leak, mate: _Rep()
00436       // does not throw.
00437       _Rep* __place = _Rep_alloc_type(__alloc).allocate(__size / sizeof(_Rep));
00438       _Rep* __p = new (__place) _Rep;
00439       __p->_M_info._M_capacity = __capacity;
00440       return __p;
00441     }
00442 
00443   template<typename _CharT, typename _Traits, typename _Alloc>
00444     void
00445     __rc_string_base<_CharT, _Traits, _Alloc>::_Rep::
00446     _M_destroy(const _Alloc& __a) throw ()
00447     {
00448       const size_type __size = ((_M_info._M_capacity + 1) * sizeof(_CharT)
00449                 + 2 * sizeof(_Rep) - 1);
00450       _Rep_alloc_type(__a).deallocate(this, __size / sizeof(_Rep));
00451     }
00452 
00453   template<typename _CharT, typename _Traits, typename _Alloc>
00454     _CharT*
00455     __rc_string_base<_CharT, _Traits, _Alloc>::_Rep::
00456     _M_clone(const _Alloc& __alloc, size_type __res)
00457     {
00458       // Requested capacity of the clone.
00459       const size_type __requested_cap = _M_info._M_length + __res;
00460       _Rep* __r = _Rep::_S_create(__requested_cap, _M_info._M_capacity,
00461                   __alloc);
00462 
00463       if (_M_info._M_length)
00464     _S_copy(__r->_M_refdata(), _M_refdata(), _M_info._M_length);
00465 
00466       __r->_M_set_length(_M_info._M_length);
00467       return __r->_M_refdata();
00468     }
00469 
00470   template<typename _CharT, typename _Traits, typename _Alloc>
00471     __rc_string_base<_CharT, _Traits, _Alloc>::
00472     __rc_string_base(const _Alloc& __a)
00473     : _M_dataplus(__a, _S_construct(size_type(), _CharT(), __a)) { }
00474 
00475   template<typename _CharT, typename _Traits, typename _Alloc>
00476     __rc_string_base<_CharT, _Traits, _Alloc>::
00477     __rc_string_base(const __rc_string_base& __rcs)
00478     : _M_dataplus(__rcs._M_get_allocator(),
00479           __rcs._M_grab(__rcs._M_get_allocator())) { }
00480 
00481   template<typename _CharT, typename _Traits, typename _Alloc>
00482     __rc_string_base<_CharT, _Traits, _Alloc>::
00483     __rc_string_base(size_type __n, _CharT __c, const _Alloc& __a)
00484     : _M_dataplus(__a, _S_construct(__n, __c, __a)) { }
00485 
00486   template<typename _CharT, typename _Traits, typename _Alloc>
00487     template<typename _InputIterator>
00488     __rc_string_base<_CharT, _Traits, _Alloc>::
00489     __rc_string_base(_InputIterator __beg, _InputIterator __end,
00490              const _Alloc& __a)
00491     : _M_dataplus(__a, _S_construct(__beg, __end, __a)) { }
00492 
00493   template<typename _CharT, typename _Traits, typename _Alloc>
00494     void
00495     __rc_string_base<_CharT, _Traits, _Alloc>::
00496     _M_leak_hard()
00497     {
00498       if (_M_is_shared())
00499     _M_erase(0, 0);
00500       _M_set_leaked();
00501     }
00502 
00503   // NB: This is the special case for Input Iterators, used in
00504   // istreambuf_iterators, etc.
00505   // Input Iterators have a cost structure very different from
00506   // pointers, calling for a different coding style.
00507   template<typename _CharT, typename _Traits, typename _Alloc>
00508     template<typename _InIterator>
00509       _CharT*
00510       __rc_string_base<_CharT, _Traits, _Alloc>::
00511       _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
00512            std::input_iterator_tag)
00513       {
00514     if (__beg == __end && __a == _Alloc())
00515       return _S_empty_rep._M_refcopy();
00516 
00517     // Avoid reallocation for common case.
00518     _CharT __buf[128];
00519     size_type __len = 0;
00520     while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT))
00521       {
00522         __buf[__len++] = *__beg;
00523         ++__beg;
00524       }
00525     _Rep* __r = _Rep::_S_create(__len, size_type(0), __a);
00526     _S_copy(__r->_M_refdata(), __buf, __len);
00527     __try
00528       {
00529         while (__beg != __end)
00530           {
00531         if (__len == __r->_M_info._M_capacity)
00532           {
00533             // Allocate more space.
00534             _Rep* __another = _Rep::_S_create(__len + 1, __len, __a);
00535             _S_copy(__another->_M_refdata(), __r->_M_refdata(), __len);
00536             __r->_M_destroy(__a);
00537             __r = __another;
00538           }
00539         __r->_M_refdata()[__len++] = *__beg;
00540         ++__beg;
00541           }
00542       }
00543     __catch(...)
00544       {
00545         __r->_M_destroy(__a);
00546         __throw_exception_again;
00547       }
00548     __r->_M_set_length(__len);
00549     return __r->_M_refdata();
00550       }
00551 
00552   template<typename _CharT, typename _Traits, typename _Alloc>
00553     template<typename _InIterator>
00554       _CharT*
00555       __rc_string_base<_CharT, _Traits, _Alloc>::
00556       _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
00557            std::forward_iterator_tag)
00558       {
00559     if (__beg == __end && __a == _Alloc())
00560       return _S_empty_rep._M_refcopy();
00561 
00562     // NB: Not required, but considered best practice.
00563     if (__is_null_pointer(__beg) && __beg != __end)
00564       std::__throw_logic_error(__N("__rc_string_base::"
00565                        "_S_construct null not valid"));
00566 
00567     const size_type __dnew = static_cast<size_type>(std::distance(__beg,
00568                                       __end));
00569     // Check for out_of_range and length_error exceptions.
00570     _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a);
00571     __try
00572       { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
00573     __catch(...)
00574       {
00575         __r->_M_destroy(__a);
00576         __throw_exception_again;
00577       }
00578     __r->_M_set_length(__dnew);
00579     return __r->_M_refdata();
00580       }
00581 
00582   template<typename _CharT, typename _Traits, typename _Alloc>
00583     _CharT*
00584     __rc_string_base<_CharT, _Traits, _Alloc>::
00585     _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
00586     {
00587       if (__n == 0 && __a == _Alloc())
00588     return _S_empty_rep._M_refcopy();
00589 
00590       // Check for out_of_range and length_error exceptions.
00591       _Rep* __r = _Rep::_S_create(__n, size_type(0), __a);
00592       if (__n)
00593     _S_assign(__r->_M_refdata(), __n, __c);
00594 
00595       __r->_M_set_length(__n);
00596       return __r->_M_refdata();
00597     }
00598 
00599   template<typename _CharT, typename _Traits, typename _Alloc>
00600     void
00601     __rc_string_base<_CharT, _Traits, _Alloc>::
00602     _M_swap(__rc_string_base& __rcs)
00603     {
00604       if (_M_is_leaked())
00605     _M_set_sharable();
00606       if (__rcs._M_is_leaked())
00607     __rcs._M_set_sharable();
00608 
00609       _CharT* __tmp = _M_data();
00610       _M_data(__rcs._M_data());
00611       __rcs._M_data(__tmp);
00612 
00613       // _GLIBCXX_RESOLVE_LIB_DEFECTS
00614       // 431. Swapping containers with unequal allocators.
00615       std::__alloc_swap<allocator_type>::_S_do_it(_M_get_allocator(),
00616                           __rcs._M_get_allocator());
00617     }
00618 
00619   template<typename _CharT, typename _Traits, typename _Alloc>
00620     void
00621     __rc_string_base<_CharT, _Traits, _Alloc>::
00622     _M_assign(const __rc_string_base& __rcs)
00623     {
00624       if (_M_rep() != __rcs._M_rep())
00625     {
00626       _CharT* __tmp = __rcs._M_grab(_M_get_allocator());
00627       _M_dispose();
00628       _M_data(__tmp);
00629     }
00630     }
00631 
00632   template<typename _CharT, typename _Traits, typename _Alloc>
00633     void
00634     __rc_string_base<_CharT, _Traits, _Alloc>::
00635     _M_reserve(size_type __res)
00636     {
00637       // Make sure we don't shrink below the current size.
00638       if (__res < _M_length())
00639     __res = _M_length();
00640 
00641       if (__res != _M_capacity() || _M_is_shared())
00642     {
00643       _CharT* __tmp = _M_rep()->_M_clone(_M_get_allocator(),
00644                          __res - _M_length());
00645       _M_dispose();
00646       _M_data(__tmp);
00647     }
00648     }
00649 
00650   template<typename _CharT, typename _Traits, typename _Alloc>
00651     void
00652     __rc_string_base<_CharT, _Traits, _Alloc>::
00653     _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
00654           size_type __len2)
00655     {
00656       const size_type __how_much = _M_length() - __pos - __len1;
00657 
00658       _Rep* __r = _Rep::_S_create(_M_length() + __len2 - __len1,
00659                   _M_capacity(), _M_get_allocator());
00660 
00661       if (__pos)
00662     _S_copy(__r->_M_refdata(), _M_data(), __pos);
00663       if (__s && __len2)
00664     _S_copy(__r->_M_refdata() + __pos, __s, __len2);
00665       if (__how_much)
00666     _S_copy(__r->_M_refdata() + __pos + __len2,
00667         _M_data() + __pos + __len1, __how_much);
00668 
00669       _M_dispose();
00670       _M_data(__r->_M_refdata());
00671     }
00672 
00673   template<typename _CharT, typename _Traits, typename _Alloc>
00674     void
00675     __rc_string_base<_CharT, _Traits, _Alloc>::
00676     _M_erase(size_type __pos, size_type __n)
00677     {
00678       const size_type __new_size = _M_length() - __n;
00679       const size_type __how_much = _M_length() - __pos - __n;
00680 
00681       if (_M_is_shared())
00682     {
00683       // Must reallocate.
00684       _Rep* __r = _Rep::_S_create(__new_size, _M_capacity(),
00685                       _M_get_allocator());
00686 
00687       if (__pos)
00688         _S_copy(__r->_M_refdata(), _M_data(), __pos);
00689       if (__how_much)
00690         _S_copy(__r->_M_refdata() + __pos,
00691             _M_data() + __pos + __n, __how_much);
00692 
00693       _M_dispose();
00694       _M_data(__r->_M_refdata());
00695     }
00696       else if (__how_much && __n)
00697     {
00698       // Work in-place.
00699       _S_move(_M_data() + __pos,
00700           _M_data() + __pos + __n, __how_much);
00701     }
00702 
00703       _M_rep()->_M_set_length(__new_size);
00704     }
00705 
00706   template<>
00707     inline bool
00708     __rc_string_base<char, std::char_traits<char>,
00709              std::allocator<char> >::
00710     _M_compare(const __rc_string_base& __rcs) const
00711     {
00712       if (_M_rep() == __rcs._M_rep())
00713     return true;
00714       return false;
00715     }
00716 
00717 #ifdef _GLIBCXX_USE_WCHAR_T
00718   template<>
00719     inline bool
00720     __rc_string_base<wchar_t, std::char_traits<wchar_t>,
00721              std::allocator<wchar_t> >::
00722     _M_compare(const __rc_string_base& __rcs) const
00723     {
00724       if (_M_rep() == __rcs._M_rep())
00725     return true;
00726       return false;
00727     }
00728 #endif
00729 
00730 _GLIBCXX_END_NAMESPACE_VERSION
00731 } // namespace
00732 
00733 #endif /* _RC_STRING_BASE_H */