The C and C++ Include Header Files

/usr/include/c++/11/ext/rc_string_base.h


$ cat -n /usr/include/c++/11/ext/rc_string_base.h

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