The C and C++ Include Header Files

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


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

     1	// SGI's rope class implementation -*- C++ -*-
     2	
     3	// Copyright (C) 2001-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	/*
    26	 * Copyright (c) 1997
    27	 * Silicon Graphics Computer Systems, Inc.
    28	 *
    29	 * Permission to use, copy, modify, distribute and sell this software
    30	 * and its documentation for any purpose is hereby granted without fee,
    31	 * provided that the above copyright notice appear in all copies and
    32	 * that both that copyright notice and this permission notice appear
    33	 * in supporting documentation.  Silicon Graphics makes no
    34	 * representations about the suitability of this software for any
    35	 * purpose.  It is provided "as is" without express or implied warranty.
    36	 */
    37	
    38	/** @file ropeimpl.h
    39	 *  This is an internal header file, included by other library headers.
    40	 *  Do not attempt to use it directly. @headername{ext/rope}
    41	 */
    42	
    43	#include <cstdio>
    44	#include <ostream>
    45	#include <bits/functexcept.h>
    46	
    47	#include <ext/algorithm> // For copy_n and lexicographical_compare_3way
    48	#include <ext/memory> // For uninitialized_copy_n
    49	#include <ext/numeric> // For power
    50	
    51	namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
    52	{
    53	_GLIBCXX_BEGIN_NAMESPACE_VERSION
    54	
    55	  // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
    56	  // if necessary.  Assumes _M_path_end[leaf_index] and leaf_pos are correct.
    57	  // Results in a valid buf_ptr if the iterator can be legitimately
    58	  // dereferenced.
    59	  template <class _CharT, class _Alloc>
    60	    void
    61	    _Rope_iterator_base<_CharT, _Alloc>::
    62	    _S_setbuf(_Rope_iterator_base<_CharT, _Alloc>& __x)
    63	    {
    64	      using std::size_t;
    65	      const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index];
    66	      size_t __leaf_pos = __x._M_leaf_pos;
    67	      size_t __pos = __x._M_current_pos;
    68	
    69	      switch(__leaf->_M_tag)
    70		{
    71		case __detail::_S_leaf:
    72		  __x._M_buf_start = ((_Rope_RopeLeaf<_CharT, _Alloc>*)__leaf)->_M_data;
    73		  __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos);
    74		  __x._M_buf_end = __x._M_buf_start + __leaf->_M_size;
    75		  break;
    76		case __detail::_S_function:
    77		case __detail::_S_substringfn:
    78		  {
    79		    size_t __len = _S_iterator_buf_len;
    80		    size_t __buf_start_pos = __leaf_pos;
    81		    size_t __leaf_end = __leaf_pos + __leaf->_M_size;
    82		    char_producer<_CharT>* __fn = ((_Rope_RopeFunction<_CharT,
    83						    _Alloc>*)__leaf)->_M_fn;
    84		    if (__buf_start_pos + __len <= __pos)
    85		      {
    86			__buf_start_pos = __pos - __len / 4;
    87			if (__buf_start_pos + __len > __leaf_end)
    88			  __buf_start_pos = __leaf_end - __len;
    89		      }
    90		    if (__buf_start_pos + __len > __leaf_end)
    91		      __len = __leaf_end - __buf_start_pos;
    92		    (*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf);
    93		    __x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos);
    94		    __x._M_buf_start = __x._M_tmp_buf;
    95		    __x._M_buf_end = __x._M_tmp_buf + __len;
    96		  }
    97		  break;
    98		default:
    99		  break;
   100		}
   101	    }
   102	
   103	  // Set path and buffer inside a rope iterator.  We assume that
   104	  // pos and root are already set.
   105	  template <class _CharT, class _Alloc>
   106	    void
   107	    _Rope_iterator_base<_CharT, _Alloc>::
   108	    _S_setcache(_Rope_iterator_base<_CharT, _Alloc>& __x)
   109	    {
   110	      using std::size_t;
   111	      const _RopeRep* __path[int(__detail::_S_max_rope_depth) + 1];
   112	      const _RopeRep* __curr_rope;
   113	      int __curr_depth = -1;  /* index into path    */
   114	      size_t __curr_start_pos = 0;
   115	      size_t __pos = __x._M_current_pos;
   116	      unsigned char __dirns = 0; // Bit vector marking right turns in the path
   117	
   118	      if (__pos >= __x._M_root->_M_size)
   119		{
   120		  __x._M_buf_ptr = 0;
   121		  return;
   122		}
   123	      __curr_rope = __x._M_root;
   124	      if (0 != __curr_rope->_M_c_string)
   125		{
   126		  /* Treat the root as a leaf. */
   127		  __x._M_buf_start = __curr_rope->_M_c_string;
   128		  __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size;
   129		  __x._M_buf_ptr = __curr_rope->_M_c_string + __pos;
   130		  __x._M_path_end[0] = __curr_rope;
   131		  __x._M_leaf_index = 0;
   132		  __x._M_leaf_pos = 0;
   133		  return;
   134		}
   135	      for(;;)
   136		{
   137		  ++__curr_depth;
   138		  __path[__curr_depth] = __curr_rope;
   139		  switch(__curr_rope->_M_tag)
   140		    {
   141		    case __detail::_S_leaf:
   142		    case __detail::_S_function:
   143		    case __detail::_S_substringfn:
   144		      __x._M_leaf_pos = __curr_start_pos;
   145		      goto done;
   146		    case __detail::_S_concat:
   147		      {
   148			_Rope_RopeConcatenation<_CharT, _Alloc>* __c =
   149			  (_Rope_RopeConcatenation<_CharT, _Alloc>*)__curr_rope;
   150			_RopeRep* __left = __c->_M_left;
   151			size_t __left_len = __left->_M_size;
   152	
   153			__dirns <<= 1;
   154			if (__pos >= __curr_start_pos + __left_len)
   155			  {
   156			    __dirns |= 1;
   157			    __curr_rope = __c->_M_right;
   158			    __curr_start_pos += __left_len;
   159			  }
   160			else
   161			  __curr_rope = __left;
   162		      }
   163		      break;
   164		    }
   165		}
   166	    done:
   167	      // Copy last section of path into _M_path_end.
   168	      {
   169		int __i = -1;
   170		int __j = __curr_depth + 1 - int(_S_path_cache_len);
   171	
   172		if (__j < 0) __j = 0;
   173		while (__j <= __curr_depth)
   174		  __x._M_path_end[++__i] = __path[__j++];
   175		__x._M_leaf_index = __i;
   176	      }
   177	      __x._M_path_directions = __dirns;
   178	      _S_setbuf(__x);
   179	    }
   180	
   181	  // Specialized version of the above.  Assumes that
   182	  // the path cache is valid for the previous position.
   183	  template <class _CharT, class _Alloc>
   184	    void
   185	    _Rope_iterator_base<_CharT, _Alloc>::
   186	    _S_setcache_for_incr(_Rope_iterator_base<_CharT, _Alloc>& __x)
   187	    {
   188	      using std::size_t;
   189	      int __current_index = __x._M_leaf_index;
   190	      const _RopeRep* __current_node = __x._M_path_end[__current_index];
   191	      size_t __len = __current_node->_M_size;
   192	      size_t __node_start_pos = __x._M_leaf_pos;
   193	      unsigned char __dirns = __x._M_path_directions;
   194	      _Rope_RopeConcatenation<_CharT, _Alloc>* __c;
   195	
   196	      if (__x._M_current_pos - __node_start_pos < __len)
   197		{
   198		  /* More stuff in this leaf, we just didn't cache it. */
   199		  _S_setbuf(__x);
   200		  return;
   201		}
   202	      //  node_start_pos is starting position of last_node.
   203	      while (--__current_index >= 0)
   204		{
   205		  if (!(__dirns & 1) /* Path turned left */)
   206		    break;
   207		  __current_node = __x._M_path_end[__current_index];
   208		  __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node;
   209		  // Otherwise we were in the right child.  Thus we should pop
   210		  // the concatenation node.
   211		  __node_start_pos -= __c->_M_left->_M_size;
   212		  __dirns >>= 1;
   213		}
   214	      if (__current_index < 0)
   215		{
   216		  // We underflowed the cache. Punt.
   217		  _S_setcache(__x);
   218		  return;
   219		}
   220	      __current_node = __x._M_path_end[__current_index];
   221	      __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node;
   222	      // current_node is a concatenation node.  We are positioned on the first
   223	      // character in its right child.
   224	      // node_start_pos is starting position of current_node.
   225	      __node_start_pos += __c->_M_left->_M_size;
   226	      __current_node = __c->_M_right;
   227	      __x._M_path_end[++__current_index] = __current_node;
   228	      __dirns |= 1;
   229	      while (__detail::_S_concat == __current_node->_M_tag)
   230		{
   231		  ++__current_index;
   232		  if (int(_S_path_cache_len) == __current_index)
   233		    {
   234		      int __i;
   235		      for (__i = 0; __i < int(_S_path_cache_len) - 1; __i++)
   236			__x._M_path_end[__i] = __x._M_path_end[__i+1];
   237		      --__current_index;
   238		    }
   239		  __current_node =
   240		    ((_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node)->_M_left;
   241		  __x._M_path_end[__current_index] = __current_node;
   242		  __dirns <<= 1;
   243		  // node_start_pos is unchanged.
   244		}
   245	      __x._M_leaf_index = __current_index;
   246	      __x._M_leaf_pos = __node_start_pos;
   247	      __x._M_path_directions = __dirns;
   248	      _S_setbuf(__x);
   249	    }
   250	
   251	  template <class _CharT, class _Alloc>
   252	    void
   253	    _Rope_iterator_base<_CharT, _Alloc>::
   254	    _M_incr(std::size_t __n)
   255	    {
   256	      _M_current_pos += __n;
   257	      if (0 != _M_buf_ptr)
   258		{
   259		  std::size_t __chars_left = _M_buf_end - _M_buf_ptr;
   260		  if (__chars_left > __n)
   261		    _M_buf_ptr += __n;
   262		  else if (__chars_left == __n)
   263		    {
   264		      _M_buf_ptr += __n;
   265		      _S_setcache_for_incr(*this);
   266		    }
   267		  else
   268		    _M_buf_ptr = 0;
   269		}
   270	    }
   271	
   272	  template <class _CharT, class _Alloc>
   273	    void
   274	    _Rope_iterator_base<_CharT, _Alloc>::
   275	    _M_decr(std::size_t __n)
   276	    {
   277	      if (0 != _M_buf_ptr)
   278		{
   279		  std::size_t __chars_left = _M_buf_ptr - _M_buf_start;
   280		  if (__chars_left >= __n)
   281		    _M_buf_ptr -= __n;
   282		  else
   283		    _M_buf_ptr = 0;
   284		}
   285	      _M_current_pos -= __n;
   286	    }
   287	
   288	  template <class _CharT, class _Alloc>
   289	    void
   290	    _Rope_iterator<_CharT, _Alloc>::
   291	    _M_check()
   292	    {
   293	      if (_M_root_rope->_M_tree_ptr != this->_M_root)
   294		{
   295		  // _Rope was modified.  Get things fixed up.
   296		  _RopeRep::_S_unref(this->_M_root);
   297		  this->_M_root = _M_root_rope->_M_tree_ptr;
   298		  _RopeRep::_S_ref(this->_M_root);
   299		  this->_M_buf_ptr = 0;
   300		}
   301	    }
   302	
   303	  template <class _CharT, class _Alloc>
   304	    inline
   305	    _Rope_const_iterator<_CharT, _Alloc>::
   306	    _Rope_const_iterator(const _Rope_iterator<_CharT, _Alloc>& __x)
   307	    : _Rope_iterator_base<_CharT, _Alloc>(__x)
   308	    { }
   309	
   310	  template <class _CharT, class _Alloc>
   311	    inline
   312	    _Rope_iterator<_CharT, _Alloc>::
   313	    _Rope_iterator(rope<_CharT, _Alloc>& __r, std::size_t __pos)
   314	    : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos),
   315	      _M_root_rope(&__r)
   316	    { _RopeRep::_S_ref(this->_M_root); }
   317	
   318	  template <class _CharT, class _Alloc>
   319	    inline std::size_t
   320	    rope<_CharT, _Alloc>::
   321	    _S_char_ptr_len(const _CharT* __s)
   322	    {
   323	      const _CharT* __p = __s;
   324	      
   325	      while (!_S_is0(*__p))
   326		++__p;
   327	      return (__p - __s);
   328	    }
   329	
   330	
   331	#ifndef __GC
   332	
   333	  template <class _CharT, class _Alloc>
   334	    inline void
   335	    _Rope_RopeRep<_CharT, _Alloc>::
   336	    _M_free_c_string()
   337	    {
   338	      _CharT* __cstr = _M_c_string;
   339	      if (0 != __cstr)
   340		{
   341		  std::size_t __size = this->_M_size + 1;
   342		  std::_Destroy(__cstr, __cstr + __size, _M_get_allocator());
   343		  this->_Data_deallocate(__cstr, __size);
   344		}
   345	    }
   346	
   347	  template <class _CharT, class _Alloc>
   348	    inline void
   349	    _Rope_RopeRep<_CharT, _Alloc>::
   350	    _S_free_string(_CharT* __s, std::size_t __n, allocator_type& __a)
   351	    {
   352	      if (!_S_is_basic_char_type((_CharT*)0))
   353		std::_Destroy(__s, __s + __n, __a);
   354	      
   355	      //  This has to be a static member, so this gets a bit messy
   356	      __a.deallocate(__s,
   357			     _Rope_RopeLeaf<_CharT, _Alloc>::_S_rounded_up_size(__n));
   358	    }
   359	
   360	  //  There are several reasons for not doing this with virtual destructors
   361	  //  and a class specific delete operator:
   362	  //  - A class specific delete operator can't easily get access to
   363	  //    allocator instances if we need them.
   364	  //  - Any virtual function would need a 4 or byte vtable pointer;
   365	  //    this only requires a one byte tag per object.
   366	  template <class _CharT, class _Alloc>
   367	    void
   368	    _Rope_RopeRep<_CharT, _Alloc>::
   369	    _M_free_tree()
   370	    {
   371	      switch(_M_tag)
   372		{
   373		case __detail::_S_leaf:
   374		  {
   375		    _Rope_RopeLeaf<_CharT, _Alloc>* __l
   376		      = (_Rope_RopeLeaf<_CharT, _Alloc>*)this;
   377		    __l->_Rope_RopeLeaf<_CharT, _Alloc>::~_Rope_RopeLeaf();
   378		    this->_L_deallocate(__l, 1);
   379		    break;
   380		  }
   381		case __detail::_S_concat:
   382		  {
   383		    _Rope_RopeConcatenation<_CharT,_Alloc>* __c
   384		      = (_Rope_RopeConcatenation<_CharT, _Alloc>*)this;
   385		    __c->_Rope_RopeConcatenation<_CharT, _Alloc>::
   386		      ~_Rope_RopeConcatenation();
   387		    this->_C_deallocate(__c, 1);
   388		    break;
   389		  }
   390		case __detail::_S_function:
   391		  {
   392		    _Rope_RopeFunction<_CharT, _Alloc>* __f
   393		      = (_Rope_RopeFunction<_CharT, _Alloc>*)this;
   394		    __f->_Rope_RopeFunction<_CharT, _Alloc>::~_Rope_RopeFunction();
   395		    this->_F_deallocate(__f, 1);
   396		    break;
   397		  }
   398		case __detail::_S_substringfn:
   399		  {
   400		    _Rope_RopeSubstring<_CharT, _Alloc>* __ss =
   401		      (_Rope_RopeSubstring<_CharT, _Alloc>*)this;
   402		    __ss->_Rope_RopeSubstring<_CharT, _Alloc>::
   403		      ~_Rope_RopeSubstring();
   404		    this->_S_deallocate(__ss, 1);
   405		    break;
   406		  }
   407		}
   408	    }
   409	#else
   410	
   411	  template <class _CharT, class _Alloc>
   412	    inline void
   413	    _Rope_RopeRep<_CharT, _Alloc>::
   414	    _S_free_string(const _CharT*, std::size_t, allocator_type)
   415	    { }
   416	
   417	#endif
   418	
   419	  // Concatenate a C string onto a leaf rope by copying the rope data.
   420	  // Used for short ropes.
   421	  template <class _CharT, class _Alloc>
   422	    typename rope<_CharT, _Alloc>::_RopeLeaf*
   423	    rope<_CharT, _Alloc>::
   424	    _S_leaf_concat_char_iter(_RopeLeaf* __r, const _CharT* __iter,
   425				     std::size_t __len)
   426	    {
   427	      std::size_t __old_len = __r->_M_size;
   428	      _CharT* __new_data = (_CharT*)
   429		rope::_Data_allocate(_S_rounded_up_size(__old_len + __len));
   430	      _RopeLeaf* __result;
   431	
   432	      uninitialized_copy_n(__r->_M_data, __old_len, __new_data);
   433	      uninitialized_copy_n(__iter, __len, __new_data + __old_len);
   434	      _S_cond_store_eos(__new_data[__old_len + __len]);
   435	      __try
   436		{
   437		  __result = _S_new_RopeLeaf(__new_data, __old_len + __len,
   438					     __r->_M_get_allocator());
   439		}
   440	      __catch(...)
   441		{
   442		  _RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len,
   443					      __r->_M_get_allocator());
   444		  __throw_exception_again;
   445		}
   446	      return __result;
   447	    }
   448	
   449	#ifndef __GC
   450	  // As above, but it's OK to clobber original if refcount is 1
   451	  template <class _CharT, class _Alloc>
   452	    typename rope<_CharT,_Alloc>::_RopeLeaf*
   453	    rope<_CharT, _Alloc>::
   454	    _S_destr_leaf_concat_char_iter(_RopeLeaf* __r, const _CharT* __iter,
   455					   std::size_t __len)
   456	    {
   457	      if (__r->_M_ref_count > 1)
   458		return _S_leaf_concat_char_iter(__r, __iter, __len);
   459	      std::size_t __old_len = __r->_M_size;
   460	      if (_S_allocated_capacity(__old_len) >= __old_len + __len)
   461		{
   462		  // The space has been partially initialized for the standard
   463		  // character types.  But that doesn't matter for those types.
   464		  uninitialized_copy_n(__iter, __len, __r->_M_data + __old_len);
   465		  if (_S_is_basic_char_type((_CharT*)0))
   466		    _S_cond_store_eos(__r->_M_data[__old_len + __len]);
   467		  else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string)
   468		    {
   469		      __r->_M_free_c_string();
   470		      __r->_M_c_string = 0;
   471		    }
   472		  __r->_M_size = __old_len + __len;
   473		  __r->_M_ref_count = 2;
   474		  return __r;
   475		}
   476	      else
   477		{
   478		  _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len);
   479		  return __result;
   480		}
   481	    }
   482	#endif
   483	
   484	  // Assumes left and right are not 0.
   485	  // Does not increment (nor decrement on exception) child reference counts.
   486	  // Result has ref count 1.
   487	  template <class _CharT, class _Alloc>
   488	    typename rope<_CharT, _Alloc>::_RopeRep*
   489	    rope<_CharT, _Alloc>::
   490	    _S_tree_concat(_RopeRep* __left, _RopeRep* __right)
   491	    {
   492	      using std::size_t;
   493	      _RopeConcatenation* __result = _S_new_RopeConcatenation(__left, __right,
   494								      __left->
   495								      _M_get_allocator());
   496	      size_t __depth = __result->_M_depth;
   497	      
   498	      if (__depth > 20
   499		  && (__result->_M_size < 1000
   500		      || __depth > size_t(__detail::_S_max_rope_depth)))
   501		{
   502		  _RopeRep* __balanced;
   503	
   504		  __try
   505		    {
   506		      __balanced = _S_balance(__result);
   507		      __result->_M_unref_nonnil();
   508		    }
   509		  __catch(...)
   510		    {
   511		      rope::_C_deallocate(__result,1);
   512		      __throw_exception_again;
   513		    }
   514		  // In case of exception, we need to deallocate
   515		  // otherwise dangling result node.  But caller
   516		  // still owns its children.  Thus unref is
   517		  // inappropriate.
   518		  return __balanced;
   519		}
   520	      else
   521		return __result;
   522	    }
   523	
   524	  template <class _CharT, class _Alloc>
   525	    typename rope<_CharT, _Alloc>::_RopeRep*
   526	    rope<_CharT, _Alloc>::
   527	    _S_concat_char_iter(_RopeRep* __r, const _CharT*__s, std::size_t __slen,
   528				allocator_type& __a)
   529	    {
   530	      using std::size_t;
   531	      _RopeRep* __result;
   532	      if (0 == __slen)
   533		{
   534		  _S_ref(__r);
   535		  return __r;
   536		}
   537	      if (0 == __r)
   538		return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __a);
   539	      if (__r->_M_tag == __detail::_S_leaf
   540		  && __r->_M_size + __slen <= size_t(_S_copy_max))
   541		{
   542		  __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
   543		  return __result;
   544		}
   545	      if (__detail::_S_concat == __r->_M_tag
   546		  && __detail::_S_leaf == ((_RopeConcatenation*) __r)->_M_right->_M_tag)
   547		{
   548		  _RopeLeaf* __right =
   549		    (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right);
   550		  if (__right->_M_size + __slen <= size_t(_S_copy_max))
   551		    {
   552		      _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left;
   553		      _RopeRep* __nright =
   554			_S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen);
   555		      __left->_M_ref_nonnil();
   556		      __try
   557			{ __result = _S_tree_concat(__left, __nright); }
   558		      __catch(...)
   559			{
   560			  _S_unref(__left);
   561			  _S_unref(__nright);
   562			  __throw_exception_again;
   563			}
   564		      return __result;
   565		    }
   566		}
   567	      _RopeRep* __nright = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __a);
   568	      __try
   569		{
   570		  __r->_M_ref_nonnil();
   571		  __result = _S_tree_concat(__r, __nright);
   572		}
   573	      __catch(...)
   574		{
   575		  _S_unref(__r);
   576		  _S_unref(__nright);
   577		  __throw_exception_again;
   578		}
   579	      return __result;
   580	    }
   581	
   582	#ifndef __GC
   583	  template <class _CharT, class _Alloc>
   584	    typename rope<_CharT,_Alloc>::_RopeRep*
   585	    rope<_CharT,_Alloc>::
   586	    _S_destr_concat_char_iter(_RopeRep* __r, const _CharT* __s,
   587				      std::size_t __slen, allocator_type& __a)
   588	    {
   589	      using std::size_t;
   590	      _RopeRep* __result;
   591	      if (0 == __r)
   592		return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __a);
   593	      size_t __count = __r->_M_ref_count;
   594	      size_t __orig_size = __r->_M_size;
   595	      if (__count > 1)
   596		return _S_concat_char_iter(__r, __s, __slen, __a);
   597	      if (0 == __slen)
   598		{
   599		  __r->_M_ref_count = 2;      // One more than before
   600		  return __r;
   601		}
   602	      if (__orig_size + __slen <= size_t(_S_copy_max)
   603		  && __detail::_S_leaf == __r->_M_tag)
   604		{
   605		  __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, 
   606							    __slen);
   607		  return __result;
   608		}
   609	      if (__detail::_S_concat == __r->_M_tag)
   610		{
   611		  _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*)
   612						     __r)->_M_right);
   613		  if (__detail::_S_leaf == __right->_M_tag
   614		      && __right->_M_size + __slen <= size_t(_S_copy_max))
   615		    {
   616		      _RopeRep* __new_right =
   617			_S_destr_leaf_concat_char_iter(__right, __s, __slen);
   618		      if (__right == __new_right)
   619			__new_right->_M_ref_count = 1;
   620		      else
   621			__right->_M_unref_nonnil();
   622		      __r->_M_ref_count = 2;    // One more than before.
   623		      ((_RopeConcatenation*)__r)->_M_right = __new_right;
   624		      __r->_M_size = __orig_size + __slen;
   625		      if (0 != __r->_M_c_string)
   626			{
   627			  __r->_M_free_c_string();
   628			  __r->_M_c_string = 0;
   629			}
   630		      return __r;
   631		    }
   632		}
   633	      _RopeRep* __right = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __a);
   634	      __r->_M_ref_nonnil();
   635	      __try
   636		{ __result = _S_tree_concat(__r, __right); }
   637	      __catch(...)
   638		{
   639		  _S_unref(__r);
   640		  _S_unref(__right);
   641		  __throw_exception_again;
   642		}
   643	      return __result;
   644	    }
   645	#endif /* !__GC */
   646	  
   647	  template <class _CharT, class _Alloc>
   648	    typename rope<_CharT, _Alloc>::_RopeRep*
   649	    rope<_CharT, _Alloc>::
   650	    _S_concat(_RopeRep* __left, _RopeRep* __right)
   651	    {
   652	      using std::size_t;
   653	      if (0 == __left)
   654		{
   655		  _S_ref(__right);
   656		  return __right;
   657		}
   658	      if (0 == __right)
   659		{
   660		  __left->_M_ref_nonnil();
   661		  return __left;
   662		}
   663	      if (__detail::_S_leaf == __right->_M_tag)
   664		{
   665		  if (__detail::_S_leaf == __left->_M_tag)
   666		    {
   667		      if (__right->_M_size + __left->_M_size <= size_t(_S_copy_max))
   668			return _S_leaf_concat_char_iter((_RopeLeaf*)__left,
   669							((_RopeLeaf*)__right)->_M_data,
   670							__right->_M_size);
   671		    }
   672		  else if (__detail::_S_concat == __left->_M_tag
   673			   && __detail::_S_leaf == ((_RopeConcatenation*)
   674							   __left)->_M_right->_M_tag)
   675		    {
   676		      _RopeLeaf* __leftright =
   677			(_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right);
   678		      if (__leftright->_M_size
   679			  + __right->_M_size <= size_t(_S_copy_max))
   680			{
   681			  _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left;
   682			  _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright,
   683								      ((_RopeLeaf*)
   684								       __right)->
   685								      _M_data,
   686								      __right->_M_size);
   687			  __leftleft->_M_ref_nonnil();
   688			  __try
   689			    { return(_S_tree_concat(__leftleft, __rest)); }
   690			  __catch(...)
   691			    {
   692			      _S_unref(__leftleft);
   693			      _S_unref(__rest);
   694			      __throw_exception_again;
   695			    }
   696			}
   697		    }
   698		}
   699	      __left->_M_ref_nonnil();
   700	      __right->_M_ref_nonnil();
   701	      __try
   702		{ return(_S_tree_concat(__left, __right)); }
   703	      __catch(...)
   704		{
   705		  _S_unref(__left);
   706		  _S_unref(__right);
   707		  __throw_exception_again;
   708		}
   709	    }
   710	
   711	  template <class _CharT, class _Alloc>
   712	    typename rope<_CharT, _Alloc>::_RopeRep*
   713	    rope<_CharT, _Alloc>::
   714	    _S_substring(_RopeRep* __base, std::size_t __start, std::size_t __endp1)
   715	    {
   716	      using std::size_t;
   717	      if (0 == __base)
   718		return 0;
   719	      size_t __len = __base->_M_size;
   720	      size_t __adj_endp1;
   721	      const size_t __lazy_threshold = 128;
   722	      
   723	      if (__endp1 >= __len)
   724		{
   725		  if (0 == __start)
   726		    {
   727		      __base->_M_ref_nonnil();
   728		      return __base;
   729		    }
   730		  else
   731		    __adj_endp1 = __len;
   732		  
   733		}
   734	      else
   735		__adj_endp1 = __endp1;
   736	
   737	      switch(__base->_M_tag)
   738		{
   739		case __detail::_S_concat:
   740		    {
   741		      _RopeConcatenation* __c = (_RopeConcatenation*)__base;
   742		      _RopeRep* __left = __c->_M_left;
   743		      _RopeRep* __right = __c->_M_right;
   744		      size_t __left_len = __left->_M_size;
   745		      _RopeRep* __result;
   746		      
   747		      if (__adj_endp1 <= __left_len)
   748			return _S_substring(__left, __start, __endp1);
   749		      else if (__start >= __left_len)
   750			return _S_substring(__right, __start - __left_len,
   751					    __adj_endp1 - __left_len);
   752		      _Self_destruct_ptr __left_result(_S_substring(__left,
   753								    __start,
   754								    __left_len));
   755		      _Self_destruct_ptr __right_result(_S_substring(__right, 0,
   756								     __endp1 
   757								     - __left_len));
   758		      __result = _S_concat(__left_result, __right_result);
   759		      return __result;
   760		    }
   761		case __detail::_S_leaf:
   762		  {
   763		    _RopeLeaf* __l = (_RopeLeaf*)__base;
   764		    _RopeLeaf* __result;
   765		    size_t __result_len;
   766		    if (__start >= __adj_endp1)
   767		      return 0;
   768		    __result_len = __adj_endp1 - __start;
   769		    if (__result_len > __lazy_threshold)
   770		      goto lazy;
   771	#ifdef __GC
   772		    const _CharT* __section = __l->_M_data + __start;
   773		    __result = _S_new_RopeLeaf(__section, __result_len,
   774					       __base->_M_get_allocator());
   775		    __result->_M_c_string = 0;  // Not eos terminated.
   776	#else
   777		    // We should sometimes create substring node instead.
   778		    __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__l->_M_data + __start,
   779								__result_len,
   780								__base->
   781								_M_get_allocator());
   782	#endif
   783		    return __result;
   784		  }
   785		case __detail::_S_substringfn:
   786		  // Avoid introducing multiple layers of substring nodes.
   787		  {
   788		    _RopeSubstring* __old = (_RopeSubstring*)__base;
   789		    size_t __result_len;
   790		    if (__start >= __adj_endp1)
   791		      return 0;
   792		    __result_len = __adj_endp1 - __start;
   793		    if (__result_len > __lazy_threshold)
   794		      {
   795			_RopeSubstring* __result =
   796			  _S_new_RopeSubstring(__old->_M_base,
   797					       __start + __old->_M_start,
   798					       __adj_endp1 - __start,
   799					       __base->_M_get_allocator());
   800			return __result;
   801			
   802		      } // *** else fall through: ***
   803		  }
   804		case __detail::_S_function:
   805		  {
   806		    _RopeFunction* __f = (_RopeFunction*)__base;
   807		    _CharT* __section;
   808		    size_t __result_len;
   809		    if (__start >= __adj_endp1)
   810		      return 0;
   811		    __result_len = __adj_endp1 - __start;
   812		    
   813		    if (__result_len > __lazy_threshold)
   814		      goto lazy;
   815		    __section = (_CharT*)
   816		      rope::_Data_allocate(_S_rounded_up_size(__result_len));
   817		    __try
   818		      {	(*(__f->_M_fn))(__start, __result_len, __section); }
   819		    __catch(...)
   820		      {
   821			_RopeRep::__STL_FREE_STRING(__section, __result_len,
   822						    __base->_M_get_allocator());
   823			__throw_exception_again;
   824		      }
   825		    _S_cond_store_eos(__section[__result_len]);
   826		    return _S_new_RopeLeaf(__section, __result_len,
   827					   __base->_M_get_allocator());
   828		  }
   829		}
   830	    lazy:
   831	      {
   832		// Create substring node.
   833		return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start,
   834					    __base->_M_get_allocator());
   835	      }
   836	    }
   837	
   838	  template<class _CharT>
   839	    class _Rope_flatten_char_consumer
   840	    : public _Rope_char_consumer<_CharT>
   841	    {
   842	    private:
   843	      _CharT* _M_buf_ptr;
   844	    public:
   845	      
   846	      _Rope_flatten_char_consumer(_CharT* __buffer)
   847	      { _M_buf_ptr = __buffer; }
   848	
   849	      ~_Rope_flatten_char_consumer() {}
   850	      
   851	      bool
   852	      operator()(const _CharT* __leaf, std::size_t __n)
   853	      {
   854		uninitialized_copy_n(__leaf, __n, _M_buf_ptr);
   855		_M_buf_ptr += __n;
   856		return true;
   857	      }
   858	    };
   859	
   860	  template<class _CharT>
   861	    class _Rope_find_char_char_consumer
   862	    : public _Rope_char_consumer<_CharT>
   863	    {
   864	    private:
   865	      _CharT _M_pattern;
   866	    public:
   867	      std::size_t _M_count;  // Number of nonmatching characters
   868	      
   869	      _Rope_find_char_char_consumer(_CharT __p)
   870	      : _M_pattern(__p), _M_count(0) {}
   871		
   872	      ~_Rope_find_char_char_consumer() {}
   873	      
   874	      bool
   875	      operator()(const _CharT* __leaf, std::size_t __n)
   876	      {
   877		std::size_t __i;
   878		for (__i = 0; __i < __n; __i++)
   879		  {
   880		    if (__leaf[__i] == _M_pattern)
   881		      {
   882			_M_count += __i;
   883			return false;
   884		      }
   885		  }
   886		_M_count += __n; return true;
   887	      }
   888	    };
   889	
   890	  template<class _CharT, class _Traits>
   891	  // Here _CharT is both the stream and rope character type.
   892	    class _Rope_insert_char_consumer
   893	    : public _Rope_char_consumer<_CharT>
   894	    {
   895	    private:
   896	      typedef std::basic_ostream<_CharT,_Traits> _Insert_ostream;
   897	      _Insert_ostream& _M_o;
   898	    public:
   899	      _Rope_insert_char_consumer(_Insert_ostream& __writer)
   900		: _M_o(__writer) {}
   901	      ~_Rope_insert_char_consumer() { }
   902	      // Caller is presumed to own the ostream
   903	      bool operator() (const _CharT* __leaf, std::size_t __n);
   904	      // Returns true to continue traversal.
   905	    };
   906	
   907	  template<class _CharT, class _Traits>
   908	    bool
   909	    _Rope_insert_char_consumer<_CharT, _Traits>::
   910	    operator()(const _CharT* __leaf, std::size_t __n)
   911	    {
   912	      std::size_t __i;
   913	      //  We assume that formatting is set up correctly for each element.
   914	      for (__i = 0; __i < __n; __i++)
   915		_M_o.put(__leaf[__i]);
   916	      return true;
   917	    }
   918	
   919	  template <class _CharT, class _Alloc>
   920	    bool
   921	    rope<_CharT, _Alloc>::
   922	    _S_apply_to_pieces(_Rope_char_consumer<_CharT>& __c, const _RopeRep* __r,
   923			       std::size_t __begin, std::size_t __end)
   924	    {
   925	      using std::size_t;
   926	      if (0 == __r)
   927		return true;
   928	      switch(__r->_M_tag)
   929		{
   930		case __detail::_S_concat:
   931		  {
   932		    _RopeConcatenation* __conc = (_RopeConcatenation*)__r;
   933		    _RopeRep* __left =  __conc->_M_left;
   934		    size_t __left_len = __left->_M_size;
   935		    if (__begin < __left_len)
   936		      {
   937			size_t __left_end = std::min(__left_len, __end);
   938			if (!_S_apply_to_pieces(__c, __left, __begin, __left_end))
   939			  return false;
   940		      }
   941		    if (__end > __left_len)
   942		      {
   943			_RopeRep* __right =  __conc->_M_right;
   944			size_t __right_start = std::max(__left_len, __begin);
   945			if (!_S_apply_to_pieces(__c, __right,
   946						__right_start - __left_len,
   947						__end - __left_len))
   948			  return false;
   949		      }
   950		  }
   951		  return true;
   952		case __detail::_S_leaf:
   953		  {
   954		    _RopeLeaf* __l = (_RopeLeaf*)__r;
   955		    return __c(__l->_M_data + __begin, __end - __begin);
   956		  }
   957		case __detail::_S_function:
   958		case __detail::_S_substringfn:
   959		    {
   960		      _RopeFunction* __f = (_RopeFunction*)__r;
   961		      size_t __len = __end - __begin;
   962		      bool __result;
   963		      _CharT* __buffer =
   964			(_CharT*)_Alloc().allocate(__len * sizeof(_CharT));
   965		      __try
   966			{
   967			  (*(__f->_M_fn))(__begin, __len, __buffer);
   968			  __result = __c(__buffer, __len);
   969	                  _Alloc().deallocate(__buffer, __len * sizeof(_CharT));
   970	                }
   971		      __catch(...)
   972			{
   973			  _Alloc().deallocate(__buffer, __len * sizeof(_CharT));
   974			  __throw_exception_again;
   975			}
   976		      return __result;
   977		    }
   978		default:
   979		  return false;
   980		}
   981	    }
   982	
   983	  template<class _CharT, class _Traits>
   984	    inline void
   985	    _Rope_fill(std::basic_ostream<_CharT, _Traits>& __o, std::size_t __n)
   986	    {
   987	      char __f = __o.fill();
   988	      std::size_t __i;
   989	      
   990	      for (__i = 0; __i < __n; __i++)
   991		__o.put(__f);
   992	    }
   993	
   994	
   995	  template <class _CharT>
   996	    inline bool
   997	    _Rope_is_simple(_CharT*)
   998	    { return false; }
   999	
  1000	  inline bool
  1001	  _Rope_is_simple(char*)
  1002	  { return true; }
  1003	
  1004	  inline bool
  1005	  _Rope_is_simple(wchar_t*)
  1006	  { return true; }
  1007	
  1008	  template<class _CharT, class _Traits, class _Alloc>
  1009	    std::basic_ostream<_CharT, _Traits>&
  1010	    operator<<(std::basic_ostream<_CharT, _Traits>& __o,
  1011		       const rope<_CharT, _Alloc>& __r)
  1012	    {
  1013	      using std::size_t;
  1014	      size_t __w = __o.width();
  1015	      bool __left = bool(__o.flags() & std::ios::left);
  1016	      size_t __pad_len;
  1017	      size_t __rope_len = __r.size();
  1018	      _Rope_insert_char_consumer<_CharT, _Traits> __c(__o);
  1019	      bool __is_simple = _Rope_is_simple((_CharT*)0);
  1020	      
  1021	      if (__rope_len < __w)
  1022		__pad_len = __w - __rope_len;
  1023	      else
  1024		__pad_len = 0;
  1025	
  1026	      if (!__is_simple)
  1027		__o.width(__w / __rope_len);
  1028	      __try
  1029		{
  1030		  if (__is_simple && !__left && __pad_len > 0)
  1031		    _Rope_fill(__o, __pad_len);
  1032		  __r.apply_to_pieces(0, __r.size(), __c);
  1033		  if (__is_simple && __left && __pad_len > 0)
  1034		    _Rope_fill(__o, __pad_len);
  1035		  if (!__is_simple)
  1036		    __o.width(__w);
  1037		}
  1038	      __catch(...)
  1039		{
  1040		  if (!__is_simple)
  1041		    __o.width(__w);
  1042		  __throw_exception_again;
  1043		}
  1044	      return __o;
  1045	    }
  1046	
  1047	  template <class _CharT, class _Alloc>
  1048	    _CharT*
  1049	    rope<_CharT, _Alloc>::
  1050	    _S_flatten(_RopeRep* __r, std::size_t __start, std::size_t __len,
  1051		       _CharT* __buffer)
  1052	    {
  1053	      _Rope_flatten_char_consumer<_CharT> __c(__buffer);
  1054	      _S_apply_to_pieces(__c, __r, __start, __start + __len);
  1055	      return(__buffer + __len);
  1056	    }
  1057	
  1058	  template <class _CharT, class _Alloc>
  1059	    std::size_t
  1060	    rope<_CharT, _Alloc>::
  1061	    find(_CharT __pattern, std::size_t __start) const
  1062	    {
  1063	      _Rope_find_char_char_consumer<_CharT> __c(__pattern);
  1064	      _S_apply_to_pieces(__c, this->_M_tree_ptr, __start, size());
  1065	      size_type __result_pos = __start + __c._M_count;
  1066	#ifndef __STL_OLD_ROPE_SEMANTICS
  1067	      if (__result_pos == size())
  1068		__result_pos = npos;
  1069	#endif
  1070	      return __result_pos;
  1071	    }
  1072	
  1073	  template <class _CharT, class _Alloc>
  1074	    _CharT*
  1075	    rope<_CharT, _Alloc>::
  1076	    _S_flatten(_RopeRep* __r, _CharT* __buffer)
  1077	    {
  1078	      if (0 == __r)
  1079		return __buffer;
  1080	      switch(__r->_M_tag)
  1081		{
  1082		case __detail::_S_concat:
  1083		  {
  1084		    _RopeConcatenation* __c = (_RopeConcatenation*)__r;
  1085		    _RopeRep* __left = __c->_M_left;
  1086		    _RopeRep* __right = __c->_M_right;
  1087		    _CharT* __rest = _S_flatten(__left, __buffer);
  1088		    return _S_flatten(__right, __rest);
  1089		  }
  1090		case __detail::_S_leaf:
  1091		  {
  1092		    _RopeLeaf* __l = (_RopeLeaf*)__r;
  1093		    return copy_n(__l->_M_data, __l->_M_size, __buffer).second;
  1094		  }
  1095		case __detail::_S_function:
  1096		case __detail::_S_substringfn:
  1097		  // We don't yet do anything with substring nodes.
  1098		  // This needs to be fixed before ropefiles will work well.
  1099		  {
  1100		    _RopeFunction* __f = (_RopeFunction*)__r;
  1101		    (*(__f->_M_fn))(0, __f->_M_size, __buffer);
  1102		    return __buffer + __f->_M_size;
  1103		  }
  1104		default:
  1105		  return 0;
  1106		}
  1107	    }
  1108	
  1109	  // This needs work for _CharT != char
  1110	  template <class _CharT, class _Alloc>
  1111	    void
  1112	    rope<_CharT, _Alloc>::
  1113	    _S_dump(_RopeRep* __r, int __indent)
  1114	    {
  1115	      using std::printf;
  1116	      for (int __i = 0; __i < __indent; __i++)
  1117		putchar(' ');
  1118	      if (0 == __r)
  1119		{
  1120		  printf("NULL\n");
  1121		  return;
  1122		}
  1123	      if (__detail::_S_concat == __r->_M_tag)
  1124		{
  1125		  _RopeConcatenation* __c = (_RopeConcatenation*)__r;
  1126		  _RopeRep* __left = __c->_M_left;
  1127		  _RopeRep* __right = __c->_M_right;
  1128		  
  1129	#ifdef __GC
  1130		  printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
  1131			 __r, __r->_M_depth, __r->_M_size,
  1132			 __r->_M_is_balanced? "" : "not");
  1133	#else
  1134		  printf("Concatenation %p (rc = %ld, depth = %d, "
  1135			 "len = %ld, %s balanced)\n",
  1136			 __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size,
  1137			 __r->_M_is_balanced? "" : "not");
  1138	#endif
  1139		  _S_dump(__left, __indent + 2);
  1140		  _S_dump(__right, __indent + 2);
  1141		  return;
  1142		}
  1143	      else
  1144		{
  1145		  const char* __kind;
  1146		  
  1147		  switch (__r->_M_tag)
  1148		    {
  1149		    case __detail::_S_leaf:
  1150		      __kind = "Leaf";
  1151		      break;
  1152		    case __detail::_S_function:
  1153		      __kind = "Function";
  1154		      break;
  1155		    case __detail::_S_substringfn:
  1156		      __kind = "Function representing substring";
  1157		      break;
  1158		    default:
  1159		      __kind = "(corrupted kind field!)";
  1160		    }
  1161	#ifdef __GC
  1162		  printf("%s %p (depth = %d, len = %ld) ",
  1163			 __kind, __r, __r->_M_depth, __r->_M_size);
  1164	#else
  1165		  printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
  1166			 __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size);
  1167	#endif
  1168		  if (_S_is_one_byte_char_type((_CharT*)0))
  1169		    {
  1170		      const int __max_len = 40;
  1171		      _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len));
  1172		      _CharT __buffer[__max_len + 1];
  1173		      bool __too_big = __r->_M_size > __prefix->_M_size;
  1174		      
  1175		      _S_flatten(__prefix, __buffer);
  1176		      __buffer[__prefix->_M_size] = _S_eos((_CharT*)0);
  1177		      printf("%s%s\n", (char*)__buffer,
  1178			     __too_big? "...\n" : "\n");
  1179		    }
  1180		  else
  1181		    printf("\n");
  1182		}
  1183	    }
  1184	
  1185	  template <class _CharT, class _Alloc>
  1186	    const unsigned long
  1187	    rope<_CharT, _Alloc>::
  1188	    _S_min_len[int(__detail::_S_max_rope_depth) + 1] = {
  1189	      /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21,
  1190	      /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377,
  1191	      /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181,
  1192	      /* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368,
  1193	      /* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811,
  1194	      /* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309,
  1195	      /* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352,
  1196	      /* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155,
  1197	      /* 39 */165580141, /* 40 */267914296, /* 41 */433494437,
  1198	      /* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903,
  1199	      /* 45 */2971215073u };
  1200	  // These are Fibonacci numbers < 2**32.
  1201	
  1202	  template <class _CharT, class _Alloc>
  1203	    typename rope<_CharT, _Alloc>::_RopeRep*
  1204	    rope<_CharT, _Alloc>::
  1205	    _S_balance(_RopeRep* __r)
  1206	    {
  1207	      _RopeRep* __forest[int(__detail::_S_max_rope_depth) + 1];
  1208	      _RopeRep* __result = 0;
  1209	      int __i;
  1210	      // Invariant:
  1211	      // The concatenation of forest in descending order is equal to __r.
  1212	      // __forest[__i]._M_size >= _S_min_len[__i]
  1213	      // __forest[__i]._M_depth = __i
  1214	      // References from forest are included in refcount.
  1215	      
  1216	      for (__i = 0; __i <= int(__detail::_S_max_rope_depth); ++__i)
  1217		__forest[__i] = 0;
  1218	      __try
  1219		{
  1220		  _S_add_to_forest(__r, __forest);
  1221		  for (__i = 0; __i <= int(__detail::_S_max_rope_depth); ++__i)
  1222		    if (0 != __forest[__i])
  1223		      {
  1224	#ifndef __GC
  1225			_Self_destruct_ptr __old(__result);
  1226	#endif
  1227			__result = _S_concat(__forest[__i], __result);
  1228			__forest[__i]->_M_unref_nonnil();
  1229	#if !defined(__GC) && __cpp_exceptions
  1230			__forest[__i] = 0;
  1231	#endif
  1232		      }
  1233		}
  1234	      __catch(...)
  1235		{
  1236		  for(__i = 0; __i <= int(__detail::_S_max_rope_depth); __i++)
  1237		    _S_unref(__forest[__i]);
  1238		  __throw_exception_again;
  1239		}
  1240	      
  1241	      if (__result->_M_depth > int(__detail::_S_max_rope_depth))
  1242		std::__throw_length_error(__N("rope::_S_balance"));
  1243	      return(__result);
  1244	    }
  1245	
  1246	  template <class _CharT, class _Alloc>
  1247	    void
  1248	    rope<_CharT, _Alloc>::
  1249	    _S_add_to_forest(_RopeRep* __r, _RopeRep** __forest)
  1250	    {
  1251	      if (__r->_M_is_balanced)
  1252		{
  1253		  _S_add_leaf_to_forest(__r, __forest);
  1254		  return;
  1255		}
  1256	
  1257	      {
  1258		_RopeConcatenation* __c = (_RopeConcatenation*)__r;
  1259		
  1260		_S_add_to_forest(__c->_M_left, __forest);
  1261		_S_add_to_forest(__c->_M_right, __forest);
  1262	      }
  1263	    }
  1264	
  1265	
  1266	  template <class _CharT, class _Alloc>
  1267	    void
  1268	    rope<_CharT, _Alloc>::
  1269	    _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest)
  1270	    {
  1271	      _RopeRep* __insertee;		// included in refcount
  1272	      _RopeRep* __too_tiny = 0;		// included in refcount
  1273	      int __i;				// forest[0..__i-1] is empty
  1274	      std::size_t __s = __r->_M_size;
  1275	      
  1276	      for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i)
  1277		{
  1278		  if (0 != __forest[__i])
  1279		    {
  1280	#ifndef __GC
  1281		      _Self_destruct_ptr __old(__too_tiny);
  1282	#endif
  1283		      __too_tiny = _S_concat_and_set_balanced(__forest[__i],
  1284							      __too_tiny);
  1285		      __forest[__i]->_M_unref_nonnil();
  1286		      __forest[__i] = 0;
  1287		    }
  1288		}
  1289	      {
  1290	#ifndef __GC
  1291		_Self_destruct_ptr __old(__too_tiny);
  1292	#endif
  1293		__insertee = _S_concat_and_set_balanced(__too_tiny, __r);
  1294	      }
  1295	      // Too_tiny dead, and no longer included in refcount.
  1296	      // Insertee is live and included.
  1297	      for (;; ++__i)
  1298		{
  1299		  if (0 != __forest[__i])
  1300		    {
  1301	#ifndef __GC
  1302		      _Self_destruct_ptr __old(__insertee);
  1303	#endif
  1304		      __insertee = _S_concat_and_set_balanced(__forest[__i],
  1305							      __insertee);
  1306		      __forest[__i]->_M_unref_nonnil();
  1307		      __forest[__i] = 0;
  1308		    }
  1309		  if (__i == int(__detail::_S_max_rope_depth)
  1310		      || __insertee->_M_size < _S_min_len[__i+1])
  1311		    {
  1312		      __forest[__i] = __insertee;
  1313		      // refcount is OK since __insertee is now dead.
  1314		      return;
  1315		    }
  1316		}
  1317	    }
  1318	
  1319	  template <class _CharT, class _Alloc>
  1320	    _CharT
  1321	    rope<_CharT, _Alloc>::
  1322	    _S_fetch(_RopeRep* __r, size_type __i)
  1323	    {
  1324	      __GC_CONST _CharT* __cstr = __r->_M_c_string;
  1325	      
  1326	      if (0 != __cstr)
  1327		return __cstr[__i];
  1328	      for(;;)
  1329		{
  1330		  switch(__r->_M_tag)
  1331		    {
  1332		    case __detail::_S_concat:
  1333		      {
  1334			_RopeConcatenation* __c = (_RopeConcatenation*)__r;
  1335			_RopeRep* __left = __c->_M_left;
  1336			std::size_t __left_len = __left->_M_size;
  1337			
  1338			if (__i >= __left_len)
  1339			  {
  1340			    __i -= __left_len;
  1341			    __r = __c->_M_right;
  1342			  } 
  1343			else
  1344			  __r = __left;
  1345		      }
  1346		      break;
  1347		    case __detail::_S_leaf:
  1348		      {
  1349			_RopeLeaf* __l = (_RopeLeaf*)__r;
  1350			return __l->_M_data[__i];
  1351		      }
  1352		    case __detail::_S_function:
  1353		    case __detail::_S_substringfn:
  1354		      {
  1355			_RopeFunction* __f = (_RopeFunction*)__r;
  1356			_CharT __result;
  1357			
  1358			(*(__f->_M_fn))(__i, 1, &__result);
  1359			return __result;
  1360		      }
  1361		    }
  1362		}
  1363	    }
  1364	  
  1365	#ifndef __GC
  1366	  // Return a uniquely referenced character slot for the given
  1367	  // position, or 0 if that's not possible.
  1368	  template <class _CharT, class _Alloc>
  1369	    _CharT*
  1370	    rope<_CharT, _Alloc>::
  1371	    _S_fetch_ptr(_RopeRep* __r, size_type __i)
  1372	    {
  1373	      _RopeRep* __clrstack[__detail::_S_max_rope_depth];
  1374	      std::size_t __csptr = 0;
  1375	      
  1376	      for(;;)
  1377		{
  1378		  if (__r->_M_ref_count > 1)
  1379		    return 0;
  1380		  switch(__r->_M_tag)
  1381		    {
  1382		    case __detail::_S_concat:
  1383		      {
  1384			_RopeConcatenation* __c = (_RopeConcatenation*)__r;
  1385			_RopeRep* __left = __c->_M_left;
  1386			std::size_t __left_len = __left->_M_size;
  1387			
  1388			if (__c->_M_c_string != 0)
  1389			  __clrstack[__csptr++] = __c;
  1390			if (__i >= __left_len)
  1391			  {
  1392			    __i -= __left_len;
  1393			    __r = __c->_M_right;
  1394			  } 
  1395			else
  1396			  __r = __left;
  1397		      }
  1398		      break;
  1399		    case __detail::_S_leaf:
  1400		      {
  1401			_RopeLeaf* __l = (_RopeLeaf*)__r;
  1402			if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0)
  1403			  __clrstack[__csptr++] = __l;
  1404			while (__csptr > 0)
  1405			  {
  1406			    -- __csptr;
  1407			    _RopeRep* __d = __clrstack[__csptr];
  1408			    __d->_M_free_c_string();
  1409			    __d->_M_c_string = 0;
  1410			  }
  1411			return __l->_M_data + __i;
  1412		      }
  1413		    case __detail::_S_function:
  1414		    case __detail::_S_substringfn:
  1415		      return 0;
  1416		    }
  1417		}
  1418	    }
  1419	#endif /* __GC */
  1420	
  1421	  // The following could be implemented trivially using
  1422	  // lexicographical_compare_3way.
  1423	  // We do a little more work to avoid dealing with rope iterators for
  1424	  // flat strings.
  1425	  template <class _CharT, class _Alloc>
  1426	    int
  1427	    rope<_CharT, _Alloc>::
  1428	    _S_compare (const _RopeRep* __left, const _RopeRep* __right)
  1429	    {
  1430	      std::size_t __left_len;
  1431	      std::size_t __right_len;
  1432	      
  1433	      if (0 == __right)
  1434		return 0 != __left;
  1435	      if (0 == __left)
  1436		return -1;
  1437	      __left_len = __left->_M_size;
  1438	      __right_len = __right->_M_size;
  1439	      if (__detail::_S_leaf == __left->_M_tag)
  1440		{
  1441		  _RopeLeaf* __l = (_RopeLeaf*) __left;
  1442		  if (__detail::_S_leaf == __right->_M_tag)
  1443		    {
  1444		      _RopeLeaf* __r = (_RopeLeaf*) __right;
  1445		      return lexicographical_compare_3way(__l->_M_data,
  1446							  __l->_M_data + __left_len,
  1447							  __r->_M_data, __r->_M_data
  1448							  + __right_len);
  1449		    }
  1450		  else
  1451		    {
  1452		      const_iterator __rstart(__right, 0);
  1453		      const_iterator __rend(__right, __right_len);
  1454		      return lexicographical_compare_3way(__l->_M_data, __l->_M_data
  1455							  + __left_len,
  1456							  __rstart, __rend);
  1457		    }
  1458		}
  1459	      else
  1460		{
  1461		  const_iterator __lstart(__left, 0);
  1462		  const_iterator __lend(__left, __left_len);
  1463		  if (__detail::_S_leaf == __right->_M_tag)
  1464		    {
  1465		      _RopeLeaf* __r = (_RopeLeaf*) __right;
  1466		      return lexicographical_compare_3way(__lstart, __lend,
  1467							  __r->_M_data, __r->_M_data
  1468							  + __right_len);
  1469		    }
  1470		  else
  1471		    {
  1472		      const_iterator __rstart(__right, 0);
  1473		      const_iterator __rend(__right, __right_len);
  1474		      return lexicographical_compare_3way(__lstart, __lend,
  1475							  __rstart, __rend);
  1476		    }
  1477		}
  1478	    }
  1479	
  1480	  // Assignment to reference proxies.
  1481	  template <class _CharT, class _Alloc>
  1482	    _Rope_char_ref_proxy<_CharT, _Alloc>&
  1483	    _Rope_char_ref_proxy<_CharT, _Alloc>::
  1484	    operator=(_CharT __c)
  1485	    {
  1486	      _RopeRep* __old = _M_root->_M_tree_ptr;
  1487	#ifndef __GC
  1488	      // First check for the case in which everything is uniquely
  1489	      // referenced.  In that case we can do this destructively.
  1490	      _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos);
  1491	      if (0 != __ptr)
  1492		{
  1493		  *__ptr = __c;
  1494		  return *this;
  1495		}
  1496	#endif
  1497	      _Self_destruct_ptr __left(_My_rope::_S_substring(__old, 0, _M_pos));
  1498	      _Self_destruct_ptr __right(_My_rope::_S_substring(__old, _M_pos + 1,
  1499								__old->_M_size));
  1500	      typename _RopeRep::allocator_type __a = _M_root->_M_get_allocator();
  1501	      _Self_destruct_ptr __result_left(_My_rope::
  1502					       _S_destr_concat_char_iter(__left,
  1503									 &__c, 1,
  1504									 __a));
  1505	
  1506	      _RopeRep* __result = _My_rope::_S_concat(__result_left, __right);
  1507	#ifndef __GC
  1508	      _RopeRep::_S_unref(__old);
  1509	#endif
  1510	      _M_root->_M_tree_ptr = __result;
  1511	      return *this;
  1512	    }
  1513	
  1514	  template <class _CharT, class _Alloc>
  1515	    inline _Rope_char_ref_proxy<_CharT, _Alloc>::
  1516	    operator _CharT() const
  1517	    {
  1518	      if (_M_current_valid)
  1519		return _M_current;
  1520	      else
  1521		return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos);
  1522	    }
  1523	
  1524	  template <class _CharT, class _Alloc>
  1525	    _Rope_char_ptr_proxy<_CharT, _Alloc>
  1526	    _Rope_char_ref_proxy<_CharT, _Alloc>::
  1527	    operator&() const
  1528	    { return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this); }
  1529	
  1530	  template <class _CharT, class _Alloc>
  1531	    rope<_CharT, _Alloc>::
  1532	    rope(std::size_t __n, _CharT __c, const allocator_type& __a)
  1533	    : _Base(__a)
  1534	    {
  1535	      using std::__uninitialized_fill_n_a;
  1536	
  1537	      rope<_CharT,_Alloc> __result;
  1538	      const std::size_t __exponentiate_threshold = 32;
  1539	      std::size_t __exponent;
  1540	      std::size_t __rest;
  1541	      _CharT* __rest_buffer;
  1542	      _RopeRep* __remainder;
  1543	      rope<_CharT, _Alloc> __remainder_rope;
  1544	
  1545	      if (0 == __n)
  1546		return;
  1547	
  1548	      __exponent = __n / __exponentiate_threshold;
  1549	      __rest = __n % __exponentiate_threshold;
  1550	      if (0 == __rest)
  1551		__remainder = 0;
  1552	      else
  1553		{
  1554		  __rest_buffer = this->_Data_allocate(_S_rounded_up_size(__rest));
  1555		  __uninitialized_fill_n_a(__rest_buffer, __rest, __c,
  1556					   _M_get_allocator());
  1557		  _S_cond_store_eos(__rest_buffer[__rest]);
  1558		  __try
  1559		    { __remainder = _S_new_RopeLeaf(__rest_buffer, __rest,
  1560						    _M_get_allocator()); }
  1561		  __catch(...)
  1562		    {
  1563		      _RopeRep::__STL_FREE_STRING(__rest_buffer, __rest,
  1564						  _M_get_allocator());
  1565		      __throw_exception_again;
  1566		    }
  1567		}
  1568	      __remainder_rope._M_tree_ptr = __remainder;
  1569	      if (__exponent != 0)
  1570		{
  1571		  _CharT* __base_buffer =
  1572		    this->_Data_allocate(_S_rounded_up_size(__exponentiate_threshold));
  1573		  _RopeLeaf* __base_leaf;
  1574		  rope __base_rope;
  1575		  __uninitialized_fill_n_a(__base_buffer, __exponentiate_threshold, __c,
  1576					   _M_get_allocator());
  1577		  _S_cond_store_eos(__base_buffer[__exponentiate_threshold]);
  1578		  __try
  1579		    {
  1580		      __base_leaf = _S_new_RopeLeaf(__base_buffer,
  1581						    __exponentiate_threshold,
  1582						    _M_get_allocator());
  1583		    }
  1584		  __catch(...)
  1585		    {
  1586		      _RopeRep::__STL_FREE_STRING(__base_buffer,
  1587						  __exponentiate_threshold,
  1588						  _M_get_allocator());
  1589		      __throw_exception_again;
  1590		    }
  1591		  __base_rope._M_tree_ptr = __base_leaf;
  1592		  if (1 == __exponent)
  1593		    __result = __base_rope;
  1594		  else
  1595		    __result = power(__base_rope, __exponent,
  1596				     _Rope_Concat_fn<_CharT, _Alloc>());
  1597		    
  1598		  if (0 != __remainder)
  1599		    __result += __remainder_rope;
  1600		}
  1601	      else
  1602		__result = __remainder_rope;
  1603		  
  1604	      this->_M_tree_ptr = __result._M_tree_ptr;
  1605	      this->_M_tree_ptr->_M_ref_nonnil();
  1606	    }
  1607	      
  1608	  template<class _CharT, class _Alloc>
  1609	    _CharT
  1610	    rope<_CharT, _Alloc>::_S_empty_c_str[1];
  1611	      
  1612	  template<class _CharT, class _Alloc>
  1613	    const _CharT*
  1614	    rope<_CharT, _Alloc>::
  1615	    c_str() const
  1616	    {
  1617	      if (0 == this->_M_tree_ptr)
  1618		{
  1619		  _S_empty_c_str[0] = _S_eos((_CharT*)0);  // Possibly redundant,
  1620		                                           // but probably fast.
  1621		  return _S_empty_c_str;
  1622		}
  1623	      __gthread_mutex_lock (&this->_M_tree_ptr->_M_c_string_lock);
  1624	      __GC_CONST _CharT* __result = this->_M_tree_ptr->_M_c_string;
  1625	      if (0 == __result)
  1626		{
  1627		  std::size_t __s = size();
  1628		  __result = this->_Data_allocate(__s + 1);
  1629		  _S_flatten(this->_M_tree_ptr, __result);
  1630		  __result[__s] = _S_eos((_CharT*)0);
  1631		  this->_M_tree_ptr->_M_c_string = __result;
  1632		}
  1633	      __gthread_mutex_unlock (&this->_M_tree_ptr->_M_c_string_lock);
  1634	      return(__result);
  1635	    }
  1636	  
  1637	  template<class _CharT, class _Alloc>
  1638	    const _CharT* rope<_CharT, _Alloc>::
  1639	    replace_with_c_str()
  1640	    {
  1641	      if (0 == this->_M_tree_ptr)
  1642		{
  1643		  _S_empty_c_str[0] = _S_eos((_CharT*)0);
  1644		  return _S_empty_c_str;
  1645		}
  1646	      __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string;
  1647	      if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag
  1648		  && 0 != __old_c_string)
  1649		return(__old_c_string);
  1650	      std::size_t __s = size();
  1651	      _CharT* __result = this->_Data_allocate(_S_rounded_up_size(__s));
  1652	      _S_flatten(this->_M_tree_ptr, __result);
  1653	      __result[__s] = _S_eos((_CharT*)0);
  1654	      this->_M_tree_ptr->_M_unref_nonnil();
  1655	      this->_M_tree_ptr = _S_new_RopeLeaf(__result, __s,
  1656						  this->_M_get_allocator());
  1657	      return(__result);
  1658	    }
  1659	
  1660	  // Algorithm specializations.  More should be added.
  1661	  
  1662	  template<class _Rope_iterator>  // was templated on CharT and Alloc
  1663	    void		          // VC++ workaround
  1664	    _Rope_rotate(_Rope_iterator __first,
  1665			 _Rope_iterator __middle,
  1666			 _Rope_iterator __last)
  1667	    {
  1668	      typedef typename _Rope_iterator::value_type _CharT;
  1669	      typedef typename _Rope_iterator::_allocator_type _Alloc;
  1670	      
  1671	      rope<_CharT, _Alloc>& __r(__first.container());
  1672	      rope<_CharT, _Alloc> __prefix = __r.substr(0, __first.index());
  1673	      rope<_CharT, _Alloc> __suffix =
  1674		__r.substr(__last.index(), __r.size() - __last.index());
  1675	      rope<_CharT, _Alloc> __part1 =
  1676		__r.substr(__middle.index(), __last.index() - __middle.index());
  1677	      rope<_CharT, _Alloc> __part2 =
  1678		__r.substr(__first.index(), __middle.index() - __first.index());
  1679	      __r = __prefix;
  1680	      __r += __part1;
  1681	      __r += __part2;
  1682	      __r += __suffix;
  1683	    }
  1684	
  1685	#if !defined(__GNUC__)
  1686	  // Appears to confuse g++
  1687	  inline void
  1688	  rotate(_Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __first,
  1689		 _Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __middle,
  1690		 _Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __last)
  1691	  { _Rope_rotate(__first, __middle, __last); }
  1692	#endif
  1693	
  1694	# if 0
  1695	  // Probably not useful for several reasons:
  1696	  // - for SGIs 7.1 compiler and probably some others,
  1697	  //   this forces lots of rope<wchar_t, ...> instantiations, creating a
  1698	  //   code bloat and compile time problem.  (Fixed in 7.2.)
  1699	  // - wchar_t is 4 bytes wide on most UNIX platforms, making it
  1700	  //   unattractive for unicode strings.  Unsigned short may be a better
  1701	  //   character type.
  1702	  inline void
  1703	  rotate(_Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __first,
  1704		 _Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __middle,
  1705		 _Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __last)
  1706	  { _Rope_rotate(__first, __middle, __last); }
  1707	# endif
  1708	
  1709	_GLIBCXX_END_NAMESPACE_VERSION
  1710	} // namespace