Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

  1. // SGI's rope class -*- C++ -*-
  2.  
  3. // Copyright (C) 2001-2015 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 ext/rope
  39.  *  This file is a GNU extension to the Standard C++ Library (possibly
  40.  *  containing extensions from the HP/SGI STL subset).
  41.  */
  42.  
  43. #ifndef _ROPE
  44. #define _ROPE 1
  45.  
  46. #pragma GCC system_header
  47.  
  48. #include <algorithm>
  49. #include <iosfwd>
  50. #include <bits/stl_construct.h>
  51. #include <bits/stl_uninitialized.h>
  52. #include <bits/stl_function.h>
  53. #include <bits/stl_numeric.h>
  54. #include <bits/allocator.h>
  55. #include <bits/gthr.h>
  56. #include <tr1/functional>
  57.  
  58. # ifdef __GC
  59. #   define __GC_CONST const
  60. # else
  61. #   define __GC_CONST   // constant except for deallocation
  62. # endif
  63.  
  64. #include <ext/memory> // For uninitialized_copy_n
  65.  
  66. namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
  67. {
  68.   namespace __detail
  69.   {
  70.     enum { _S_max_rope_depth = 45 };
  71.     enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function};
  72.   } // namespace __detail
  73.  
  74.   using std::size_t;
  75.   using std::ptrdiff_t;
  76.   using std::allocator;
  77.   using std::_Destroy;
  78.  
  79. _GLIBCXX_BEGIN_NAMESPACE_VERSION
  80.  
  81.   // See libstdc++/36832.
  82.   template<typename _ForwardIterator, typename _Allocator>
  83.     void
  84.     _Destroy_const(_ForwardIterator __first,
  85.                    _ForwardIterator __last, _Allocator __alloc)
  86.     {
  87.       for (; __first != __last; ++__first)
  88.         __alloc.destroy(&*__first);
  89.     }
  90.  
  91.   template<typename _ForwardIterator, typename _Tp>
  92.     inline void
  93.     _Destroy_const(_ForwardIterator __first,
  94.                    _ForwardIterator __last, allocator<_Tp>)
  95.     { _Destroy(__first, __last); }
  96.  
  97.   // The _S_eos function is used for those functions that
  98.   // convert to/from C-like strings to detect the end of the string.
  99.  
  100.   // The end-of-C-string character.
  101.   // This is what the draft standard says it should be.
  102.   template <class _CharT>
  103.     inline _CharT
  104.     _S_eos(_CharT*)
  105.     { return _CharT(); }
  106.  
  107.   // Test for basic character types.
  108.   // For basic character types leaves having a trailing eos.
  109.   template <class _CharT>
  110.     inline bool
  111.     _S_is_basic_char_type(_CharT*)
  112.     { return false; }
  113.  
  114.   template <class _CharT>
  115.     inline bool
  116.     _S_is_one_byte_char_type(_CharT*)
  117.     { return false; }
  118.  
  119.   inline bool
  120.   _S_is_basic_char_type(char*)
  121.   { return true; }
  122.  
  123.   inline bool
  124.   _S_is_one_byte_char_type(char*)
  125.   { return true; }
  126.  
  127.   inline bool
  128.   _S_is_basic_char_type(wchar_t*)
  129.   { return true; }
  130.  
  131.   // Store an eos iff _CharT is a basic character type.
  132.   // Do not reference _S_eos if it isn't.
  133.   template <class _CharT>
  134.     inline void
  135.     _S_cond_store_eos(_CharT&) { }
  136.  
  137.   inline void
  138.   _S_cond_store_eos(char& __c)
  139.   { __c = 0; }
  140.  
  141.   inline void
  142.   _S_cond_store_eos(wchar_t& __c)
  143.   { __c = 0; }
  144.  
  145.   // char_producers are logically functions that generate a section of
  146.   // a string.  These can be converted to ropes.  The resulting rope
  147.   // invokes the char_producer on demand.  This allows, for example,
  148.   // files to be viewed as ropes without reading the entire file.
  149.   template <class _CharT>
  150.     class char_producer
  151.     {
  152.     public:
  153.       virtual ~char_producer() { };
  154.  
  155.       virtual void
  156.       operator()(size_t __start_pos, size_t __len,
  157.                  _CharT* __buffer) = 0;
  158.       // Buffer should really be an arbitrary output iterator.
  159.       // That way we could flatten directly into an ostream, etc.
  160.       // This is thoroughly impossible, since iterator types don't
  161.       // have runtime descriptions.
  162.     };
  163.  
  164.   // Sequence buffers:
  165.   //
  166.   // Sequence must provide an append operation that appends an
  167.   // array to the sequence.  Sequence buffers are useful only if
  168.   // appending an entire array is cheaper than appending element by element.
  169.   // This is true for many string representations.
  170.   // This should  perhaps inherit from ostream<sequence::value_type>
  171.   // and be implemented correspondingly, so that they can be used
  172.   // for formatted.  For the sake of portability, we don't do this yet.
  173.   //
  174.   // For now, sequence buffers behave as output iterators.  But they also
  175.   // behave a little like basic_ostringstream<sequence::value_type> and a
  176.   // little like containers.
  177.  
  178.   template<class _Sequence, size_t _Buf_sz = 100>
  179.     class sequence_buffer
  180.     : public std::iterator<std::output_iterator_tag, void, void, void, void>
  181.     {
  182.     public:
  183.       typedef typename _Sequence::value_type value_type;
  184.     protected:
  185.       _Sequence* _M_prefix;
  186.       value_type _M_buffer[_Buf_sz];
  187.       size_t     _M_buf_count;
  188.     public:
  189.  
  190.       void
  191.       flush()
  192.       {
  193.         _M_prefix->append(_M_buffer, _M_buffer + _M_buf_count);
  194.         _M_buf_count = 0;
  195.       }
  196.      
  197.       ~sequence_buffer()
  198.       { flush(); }
  199.      
  200.       sequence_buffer()
  201.       : _M_prefix(0), _M_buf_count(0) { }
  202.  
  203.       sequence_buffer(const sequence_buffer& __x)
  204.       {
  205.         _M_prefix = __x._M_prefix;
  206.         _M_buf_count = __x._M_buf_count;
  207.         std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
  208.       }
  209.      
  210.       sequence_buffer(sequence_buffer& __x)
  211.       {
  212.         __x.flush();
  213.         _M_prefix = __x._M_prefix;
  214.         _M_buf_count = 0;
  215.       }
  216.      
  217.       sequence_buffer(_Sequence& __s)
  218.       : _M_prefix(&__s), _M_buf_count(0) { }
  219.      
  220.       sequence_buffer&
  221.       operator=(sequence_buffer& __x)
  222.       {
  223.         __x.flush();
  224.         _M_prefix = __x._M_prefix;
  225.         _M_buf_count = 0;
  226.         return *this;
  227.       }
  228.  
  229.       sequence_buffer&
  230.       operator=(const sequence_buffer& __x)
  231.       {
  232.         _M_prefix = __x._M_prefix;
  233.         _M_buf_count = __x._M_buf_count;
  234.         std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
  235.         return *this;
  236.       }
  237.      
  238.       void
  239.       push_back(value_type __x)
  240.       {
  241.         if (_M_buf_count < _Buf_sz)
  242.           {
  243.             _M_buffer[_M_buf_count] = __x;
  244.             ++_M_buf_count;
  245.           }
  246.         else
  247.           {
  248.             flush();
  249.             _M_buffer[0] = __x;
  250.             _M_buf_count = 1;
  251.           }
  252.       }
  253.      
  254.       void
  255.       append(value_type* __s, size_t __len)
  256.       {
  257.         if (__len + _M_buf_count <= _Buf_sz)
  258.           {
  259.             size_t __i = _M_buf_count;
  260.             for (size_t __j = 0; __j < __len; __i++, __j++)
  261.               _M_buffer[__i] = __s[__j];
  262.             _M_buf_count += __len;
  263.           }
  264.         else if (0 == _M_buf_count)
  265.           _M_prefix->append(__s, __s + __len);
  266.         else
  267.           {
  268.             flush();
  269.             append(__s, __len);
  270.           }
  271.       }
  272.  
  273.       sequence_buffer&
  274.       write(value_type* __s, size_t __len)
  275.       {
  276.         append(__s, __len);
  277.         return *this;
  278.       }
  279.      
  280.       sequence_buffer&
  281.       put(value_type __x)
  282.       {
  283.         push_back(__x);
  284.         return *this;
  285.       }
  286.      
  287.       sequence_buffer&
  288.       operator=(const value_type& __rhs)
  289.       {
  290.         push_back(__rhs);
  291.         return *this;
  292.       }
  293.      
  294.       sequence_buffer&
  295.       operator*()
  296.       { return *this; }
  297.      
  298.       sequence_buffer&
  299.       operator++()
  300.       { return *this; }
  301.      
  302.       sequence_buffer
  303.       operator++(int)
  304.       { return *this; }
  305.     };
  306.  
  307.   // The following should be treated as private, at least for now.
  308.   template<class _CharT>
  309.     class _Rope_char_consumer
  310.     {
  311.     public:
  312.       // If we had member templates, these should not be virtual.
  313.       // For now we need to use run-time parametrization where
  314.       // compile-time would do.  Hence this should all be private
  315.       // for now.
  316.       // The symmetry with char_producer is accidental and temporary.
  317.       virtual ~_Rope_char_consumer() { };
  318.  
  319.       virtual bool
  320.       operator()(const _CharT* __buffer, size_t __len) = 0;
  321.     };
  322.  
  323.   // First a lot of forward declarations.  The standard seems to require
  324.   // much stricter "declaration before use" than many of the implementations
  325.   // that preceded it.
  326.   template<class _CharT, class _Alloc = allocator<_CharT> >
  327.     class rope;
  328.  
  329.   template<class _CharT, class _Alloc>
  330.     struct _Rope_RopeConcatenation;
  331.  
  332.   template<class _CharT, class _Alloc>
  333.     struct _Rope_RopeLeaf;
  334.  
  335.   template<class _CharT, class _Alloc>
  336.     struct _Rope_RopeFunction;
  337.  
  338.   template<class _CharT, class _Alloc>
  339.     struct _Rope_RopeSubstring;
  340.  
  341.   template<class _CharT, class _Alloc>
  342.     class _Rope_iterator;
  343.  
  344.   template<class _CharT, class _Alloc>
  345.     class _Rope_const_iterator;
  346.  
  347.   template<class _CharT, class _Alloc>
  348.     class _Rope_char_ref_proxy;
  349.  
  350.   template<class _CharT, class _Alloc>
  351.     class _Rope_char_ptr_proxy;
  352.  
  353.   template<class _CharT, class _Alloc>
  354.     bool
  355.     operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
  356.                const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y);
  357.  
  358.   template<class _CharT, class _Alloc>
  359.     _Rope_const_iterator<_CharT, _Alloc>
  360.     operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
  361.               ptrdiff_t __n);
  362.  
  363.   template<class _CharT, class _Alloc>
  364.     _Rope_const_iterator<_CharT, _Alloc>
  365.     operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x,
  366.               ptrdiff_t __n);
  367.  
  368.   template<class _CharT, class _Alloc>
  369.     _Rope_const_iterator<_CharT, _Alloc>
  370.     operator+(ptrdiff_t __n,
  371.               const _Rope_const_iterator<_CharT, _Alloc>& __x);
  372.  
  373.   template<class _CharT, class _Alloc>
  374.     bool
  375.     operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x,
  376.                const _Rope_const_iterator<_CharT, _Alloc>& __y);
  377.  
  378.   template<class _CharT, class _Alloc>
  379.     bool
  380.     operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,
  381.               const _Rope_const_iterator<_CharT, _Alloc>& __y);
  382.  
  383.   template<class _CharT, class _Alloc>
  384.     ptrdiff_t
  385.     operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
  386.               const _Rope_const_iterator<_CharT, _Alloc>& __y);
  387.  
  388.   template<class _CharT, class _Alloc>
  389.     _Rope_iterator<_CharT, _Alloc>
  390.     operator-(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);
  391.  
  392.   template<class _CharT, class _Alloc>
  393.     _Rope_iterator<_CharT, _Alloc>
  394.     operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);
  395.  
  396.   template<class _CharT, class _Alloc>
  397.     _Rope_iterator<_CharT, _Alloc>
  398.     operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x);
  399.  
  400.   template<class _CharT, class _Alloc>
  401.     bool
  402.     operator==(const _Rope_iterator<_CharT, _Alloc>& __x,
  403.                const _Rope_iterator<_CharT, _Alloc>& __y);
  404.  
  405.   template<class _CharT, class _Alloc>
  406.     bool
  407.     operator<(const _Rope_iterator<_CharT, _Alloc>& __x,
  408.               const _Rope_iterator<_CharT, _Alloc>& __y);
  409.  
  410.   template<class _CharT, class _Alloc>
  411.     ptrdiff_t
  412.     operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
  413.               const _Rope_iterator<_CharT, _Alloc>& __y);
  414.  
  415.   template<class _CharT, class _Alloc>
  416.     rope<_CharT, _Alloc>
  417.     operator+(const rope<_CharT, _Alloc>& __left,
  418.               const rope<_CharT, _Alloc>& __right);
  419.  
  420.   template<class _CharT, class _Alloc>
  421.     rope<_CharT, _Alloc>
  422.     operator+(const rope<_CharT, _Alloc>& __left, const _CharT* __right);
  423.  
  424.   template<class _CharT, class _Alloc>
  425.     rope<_CharT, _Alloc>
  426.     operator+(const rope<_CharT, _Alloc>& __left, _CharT __right);
  427.  
  428.   // Some helpers, so we can use power on ropes.
  429.   // See below for why this isn't local to the implementation.
  430.  
  431.   // This uses a nonstandard refcount convention.
  432.   // The result has refcount 0.
  433.   template<class _CharT, class _Alloc>
  434.     struct _Rope_Concat_fn
  435.     : public std::binary_function<rope<_CharT, _Alloc>, rope<_CharT, _Alloc>,
  436.                                   rope<_CharT, _Alloc> >
  437.     {
  438.       rope<_CharT, _Alloc>
  439.       operator()(const rope<_CharT, _Alloc>& __x,
  440.                  const rope<_CharT, _Alloc>& __y)
  441.       { return __x + __y; }
  442.     };
  443.  
  444.   template <class _CharT, class _Alloc>
  445.     inline rope<_CharT, _Alloc>
  446.     identity_element(_Rope_Concat_fn<_CharT, _Alloc>)
  447.     { return rope<_CharT, _Alloc>(); }
  448.  
  449.   // Class _Refcount_Base provides a type, _RC_t, a data member,
  450.   // _M_ref_count, and member functions _M_incr and _M_decr, which perform
  451.   // atomic preincrement/predecrement.  The constructor initializes
  452.   // _M_ref_count.
  453.   struct _Refcount_Base
  454.   {
  455.     // The type _RC_t
  456.     typedef size_t _RC_t;
  457.    
  458.     // The data member _M_ref_count
  459.     volatile _RC_t _M_ref_count;
  460.  
  461.     // Constructor
  462. #ifdef __GTHREAD_MUTEX_INIT
  463.     __gthread_mutex_t _M_ref_count_lock = __GTHREAD_MUTEX_INIT;
  464. #else
  465.     __gthread_mutex_t _M_ref_count_lock;
  466. #endif
  467.  
  468.     _Refcount_Base(_RC_t __n) : _M_ref_count(__n)
  469.     {
  470. #ifndef __GTHREAD_MUTEX_INIT
  471. #ifdef __GTHREAD_MUTEX_INIT_FUNCTION
  472.       __GTHREAD_MUTEX_INIT_FUNCTION (&_M_ref_count_lock);
  473. #else
  474. #error __GTHREAD_MUTEX_INIT or __GTHREAD_MUTEX_INIT_FUNCTION should be defined by gthr.h abstraction layer, report problem to libstdc++@gcc.gnu.org.
  475. #endif
  476. #endif
  477.     }
  478.  
  479. #ifndef __GTHREAD_MUTEX_INIT
  480.     ~_Refcount_Base()
  481.     { __gthread_mutex_destroy(&_M_ref_count_lock); }
  482. #endif
  483.  
  484.     void
  485.     _M_incr()
  486.     {
  487.       __gthread_mutex_lock(&_M_ref_count_lock);
  488.       ++_M_ref_count;
  489.       __gthread_mutex_unlock(&_M_ref_count_lock);
  490.     }
  491.  
  492.     _RC_t
  493.     _M_decr()
  494.     {
  495.       __gthread_mutex_lock(&_M_ref_count_lock);
  496.       volatile _RC_t __tmp = --_M_ref_count;
  497.       __gthread_mutex_unlock(&_M_ref_count_lock);
  498.       return __tmp;
  499.     }
  500.   };
  501.  
  502.   //
  503.   // What follows should really be local to rope.  Unfortunately,
  504.   // that doesn't work, since it makes it impossible to define generic
  505.   // equality on rope iterators.  According to the draft standard, the
  506.   // template parameters for such an equality operator cannot be inferred
  507.   // from the occurrence of a member class as a parameter.
  508.   // (SGI compilers in fact allow this, but the __result wouldn't be
  509.   // portable.)
  510.   // Similarly, some of the static member functions are member functions
  511.   // only to avoid polluting the global namespace, and to circumvent
  512.   // restrictions on type inference for template functions.
  513.   //
  514.  
  515.   //
  516.   // The internal data structure for representing a rope.  This is
  517.   // private to the implementation.  A rope is really just a pointer
  518.   // to one of these.
  519.   //
  520.   // A few basic functions for manipulating this data structure
  521.   // are members of _RopeRep.  Most of the more complex algorithms
  522.   // are implemented as rope members.
  523.   //
  524.   // Some of the static member functions of _RopeRep have identically
  525.   // named functions in rope that simply invoke the _RopeRep versions.
  526.  
  527. #define __ROPE_DEFINE_ALLOCS(__a) \
  528.         __ROPE_DEFINE_ALLOC(_CharT,_Data) /* character data */ \
  529.         typedef _Rope_RopeConcatenation<_CharT,__a> __C; \
  530.         __ROPE_DEFINE_ALLOC(__C,_C) \
  531.         typedef _Rope_RopeLeaf<_CharT,__a> __L; \
  532.         __ROPE_DEFINE_ALLOC(__L,_L) \
  533.         typedef _Rope_RopeFunction<_CharT,__a> __F; \
  534.         __ROPE_DEFINE_ALLOC(__F,_F) \
  535.         typedef _Rope_RopeSubstring<_CharT,__a> __S; \
  536.         __ROPE_DEFINE_ALLOC(__S,_S)
  537.  
  538.   //  Internal rope nodes potentially store a copy of the allocator
  539.   //  instance used to allocate them.  This is mostly redundant.
  540.   //  But the alternative would be to pass allocator instances around
  541.   //  in some form to nearly all internal functions, since any pointer
  542.   //  assignment may result in a zero reference count and thus require
  543.   //  deallocation.
  544.  
  545. #define __STATIC_IF_SGI_ALLOC  /* not static */
  546.  
  547.   template <class _CharT, class _Alloc>
  548.     struct _Rope_rep_base
  549.     : public _Alloc
  550.     {
  551.       typedef _Alloc allocator_type;
  552.  
  553.       allocator_type
  554.       get_allocator() const
  555.       { return *static_cast<const _Alloc*>(this); }
  556.  
  557.       allocator_type&
  558.       _M_get_allocator()
  559.       { return *static_cast<_Alloc*>(this); }
  560.  
  561.       const allocator_type&
  562.       _M_get_allocator() const
  563.       { return *static_cast<const _Alloc*>(this); }
  564.  
  565.       _Rope_rep_base(size_t __size, const allocator_type&)
  566.       : _M_size(__size) { }
  567.  
  568.       size_t _M_size;
  569.  
  570. # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
  571.         typedef typename \
  572.           _Alloc::template rebind<_Tp>::other __name##Alloc; \
  573.         static _Tp* __name##_allocate(size_t __n) \
  574.           { return __name##Alloc().allocate(__n); } \
  575.         static void __name##_deallocate(_Tp *__p, size_t __n) \
  576.           { __name##Alloc().deallocate(__p, __n); }
  577.       __ROPE_DEFINE_ALLOCS(_Alloc)
  578. # undef __ROPE_DEFINE_ALLOC
  579.     };
  580.  
  581.   template<class _CharT, class _Alloc>
  582.     struct _Rope_RopeRep
  583.     : public _Rope_rep_base<_CharT, _Alloc>
  584. # ifndef __GC
  585.              , _Refcount_Base
  586. # endif
  587.     {
  588.     public:
  589.       __detail::_Tag _M_tag:8;
  590.       bool _M_is_balanced:8;
  591.       unsigned char _M_depth;
  592.       __GC_CONST _CharT* _M_c_string;
  593. #ifdef __GTHREAD_MUTEX_INIT
  594.       __gthread_mutex_t _M_c_string_lock = __GTHREAD_MUTEX_INIT;
  595. #else
  596.       __gthread_mutex_t _M_c_string_lock;
  597. #endif
  598.                         /* Flattened version of string, if needed.  */
  599.                         /* typically 0.                             */
  600.                         /* If it's not 0, then the memory is owned  */
  601.                         /* by this node.                            */
  602.                         /* In the case of a leaf, this may point to */
  603.                         /* the same memory as the data field.       */
  604.       typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
  605.         allocator_type;
  606.  
  607.       using _Rope_rep_base<_CharT, _Alloc>::get_allocator;
  608.       using _Rope_rep_base<_CharT, _Alloc>::_M_get_allocator;
  609.  
  610.       _Rope_RopeRep(__detail::_Tag __t, int __d, bool __b, size_t __size,
  611.                     const allocator_type& __a)
  612.       : _Rope_rep_base<_CharT, _Alloc>(__size, __a),
  613. #ifndef __GC
  614.         _Refcount_Base(1),
  615. #endif
  616.         _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0)
  617. #ifdef __GTHREAD_MUTEX_INIT
  618.       { }
  619. #else
  620.       { __GTHREAD_MUTEX_INIT_FUNCTION (&_M_c_string_lock); }
  621.       ~_Rope_RopeRep()
  622.       { __gthread_mutex_destroy (&_M_c_string_lock); }
  623. #endif
  624. #ifdef __GC
  625.       void
  626.       _M_incr () { }
  627. #endif
  628.       static void
  629.       _S_free_string(__GC_CONST _CharT*, size_t __len,
  630.                      allocator_type& __a);
  631. #define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a);
  632.                         // Deallocate data section of a leaf.
  633.                         // This shouldn't be a member function.
  634.                         // But its hard to do anything else at the
  635.                         // moment, because it's templatized w.r.t.
  636.                         // an allocator.
  637.                         // Does nothing if __GC is defined.
  638. #ifndef __GC
  639.       void _M_free_c_string();
  640.       void _M_free_tree();
  641.       // Deallocate t. Assumes t is not 0.
  642.       void
  643.       _M_unref_nonnil()
  644.       {
  645.         if (0 == _M_decr())
  646.           _M_free_tree();
  647.       }
  648.  
  649.       void
  650.       _M_ref_nonnil()
  651.       { _M_incr(); }
  652.  
  653.       static void
  654.       _S_unref(_Rope_RopeRep* __t)
  655.       {
  656.         if (0 != __t)
  657.           __t->_M_unref_nonnil();
  658.       }
  659.  
  660.       static void
  661.       _S_ref(_Rope_RopeRep* __t)
  662.       {
  663.         if (0 != __t)
  664.           __t->_M_incr();
  665.       }
  666.      
  667.       static void
  668.       _S_free_if_unref(_Rope_RopeRep* __t)
  669.       {
  670.         if (0 != __t && 0 == __t->_M_ref_count)
  671.           __t->_M_free_tree();
  672.       }
  673. #   else /* __GC */
  674.       void _M_unref_nonnil() { }
  675.       void _M_ref_nonnil() { }
  676.       static void _S_unref(_Rope_RopeRep*) { }
  677.       static void _S_ref(_Rope_RopeRep*) { }
  678.       static void _S_free_if_unref(_Rope_RopeRep*) { }
  679. #   endif
  680. protected:
  681.       _Rope_RopeRep&
  682.       operator=(const _Rope_RopeRep&);
  683.  
  684.       _Rope_RopeRep(const _Rope_RopeRep&);
  685.     };
  686.  
  687.   template<class _CharT, class _Alloc>
  688.     struct _Rope_RopeLeaf
  689.     : public _Rope_RopeRep<_CharT, _Alloc>
  690.     {
  691.     public:
  692.       // Apparently needed by VC++
  693.       // The data fields of leaves are allocated with some
  694.       // extra space, to accommodate future growth and for basic
  695.       // character types, to hold a trailing eos character.
  696.       enum { _S_alloc_granularity = 8 };
  697.      
  698.       static size_t
  699.       _S_rounded_up_size(size_t __n)
  700.       {
  701.         size_t __size_with_eos;
  702.        
  703.         if (_S_is_basic_char_type((_CharT*)0))
  704.           __size_with_eos = __n + 1;
  705.         else
  706.           __size_with_eos = __n;
  707. #ifdef __GC
  708.         return __size_with_eos;
  709. #else
  710.         // Allow slop for in-place expansion.
  711.         return ((__size_with_eos + size_t(_S_alloc_granularity) - 1)
  712.                 &~ (size_t(_S_alloc_granularity) - 1));
  713. #endif
  714.       }
  715.       __GC_CONST _CharT* _M_data; /* Not necessarily 0 terminated. */
  716.                                   /* The allocated size is         */
  717.                                   /* _S_rounded_up_size(size), except */
  718.                                   /* in the GC case, in which it   */
  719.                                   /* doesn't matter.               */
  720.       typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type
  721.         allocator_type;
  722.  
  723.       _Rope_RopeLeaf(__GC_CONST _CharT* __d, size_t __size,
  724.                      const allocator_type& __a)
  725.       : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_leaf, 0, true,
  726.                                       __size, __a), _M_data(__d)
  727.       {
  728.         if (_S_is_basic_char_type((_CharT *)0))
  729.           {
  730.             // already eos terminated.
  731.             this->_M_c_string = __d;
  732.           }
  733.       }
  734.       // The constructor assumes that d has been allocated with
  735.       // the proper allocator and the properly padded size.
  736.       // In contrast, the destructor deallocates the data:
  737. #ifndef __GC
  738.       ~_Rope_RopeLeaf() throw()
  739.       {
  740.         if (_M_data != this->_M_c_string)
  741.           this->_M_free_c_string();
  742.        
  743.         this->__STL_FREE_STRING(_M_data, this->_M_size, this->_M_get_allocator());
  744.       }
  745. #endif
  746. protected:
  747.       _Rope_RopeLeaf&
  748.       operator=(const _Rope_RopeLeaf&);
  749.  
  750.       _Rope_RopeLeaf(const _Rope_RopeLeaf&);
  751.     };
  752.  
  753.   template<class _CharT, class _Alloc>
  754.     struct _Rope_RopeConcatenation
  755.     : public _Rope_RopeRep<_CharT, _Alloc>
  756.     {
  757.     public:
  758.       _Rope_RopeRep<_CharT, _Alloc>* _M_left;
  759.       _Rope_RopeRep<_CharT, _Alloc>* _M_right;
  760.  
  761.       typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
  762.         allocator_type;
  763.  
  764.       _Rope_RopeConcatenation(_Rope_RopeRep<_CharT, _Alloc>* __l,
  765.                               _Rope_RopeRep<_CharT, _Alloc>* __r,
  766.                               const allocator_type& __a)
  767.         : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_concat,
  768.                                       std::max(__l->_M_depth,
  769.                                                __r->_M_depth) + 1,
  770.                                       false,
  771.                                       __l->_M_size + __r->_M_size, __a),
  772.         _M_left(__l), _M_right(__r)
  773.       { }
  774. #ifndef __GC
  775.       ~_Rope_RopeConcatenation() throw()
  776.       {
  777.         this->_M_free_c_string();
  778.         _M_left->_M_unref_nonnil();
  779.         _M_right->_M_unref_nonnil();
  780.       }
  781. #endif
  782. protected:
  783.       _Rope_RopeConcatenation&
  784.       operator=(const _Rope_RopeConcatenation&);
  785.      
  786.       _Rope_RopeConcatenation(const _Rope_RopeConcatenation&);
  787.     };
  788.  
  789.   template<class _CharT, class _Alloc>
  790.     struct _Rope_RopeFunction
  791.     : public _Rope_RopeRep<_CharT, _Alloc>
  792.     {
  793.     public:
  794.       char_producer<_CharT>* _M_fn;
  795. #ifndef __GC
  796.       bool _M_delete_when_done; // Char_producer is owned by the
  797.                                 // rope and should be explicitly
  798.                                 // deleted when the rope becomes
  799.                                 // inaccessible.
  800. #else
  801.       // In the GC case, we either register the rope for
  802.       // finalization, or not.  Thus the field is unnecessary;
  803.       // the information is stored in the collector data structures.
  804.       // We do need a finalization procedure to be invoked by the
  805.       // collector.
  806.       static void
  807.       _S_fn_finalization_proc(void * __tree, void *)
  808.       { delete ((_Rope_RopeFunction *)__tree) -> _M_fn; }
  809. #endif
  810.     typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
  811.       allocator_type;
  812.  
  813.       _Rope_RopeFunction(char_producer<_CharT>* __f, size_t __size,
  814.                         bool __d, const allocator_type& __a)
  815.       : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_function, 0, true, __size, __a)
  816.         , _M_fn(__f)
  817. #ifndef __GC
  818.         , _M_delete_when_done(__d)
  819. #endif
  820.       {
  821. #ifdef __GC
  822.         if (__d)
  823.           {
  824.             GC_REGISTER_FINALIZER(this, _Rope_RopeFunction::
  825.                                   _S_fn_finalization_proc, 0, 0, 0);
  826.           }
  827. #endif
  828.       }
  829. #ifndef __GC
  830.       ~_Rope_RopeFunction() throw()
  831.       {
  832.         this->_M_free_c_string();
  833.         if (_M_delete_when_done)
  834.           delete _M_fn;
  835.       }
  836. # endif
  837.     protected:
  838.       _Rope_RopeFunction&
  839.       operator=(const _Rope_RopeFunction&);
  840.  
  841.       _Rope_RopeFunction(const _Rope_RopeFunction&);
  842.     };
  843.   // Substring results are usually represented using just
  844.   // concatenation nodes.  But in the case of very long flat ropes
  845.   // or ropes with a functional representation that isn't practical.
  846.   // In that case, we represent the __result as a special case of
  847.   // RopeFunction, whose char_producer points back to the rope itself.
  848.   // In all cases except repeated substring operations and
  849.   // deallocation, we treat the __result as a RopeFunction.
  850.   template<class _CharT, class _Alloc>
  851.     struct _Rope_RopeSubstring
  852.     : public _Rope_RopeFunction<_CharT, _Alloc>,
  853.       public char_producer<_CharT>
  854.     {
  855.     public:
  856.       // XXX this whole class should be rewritten.
  857.       _Rope_RopeRep<_CharT,_Alloc>* _M_base;      // not 0
  858.       size_t _M_start;
  859.  
  860.       virtual void
  861.       operator()(size_t __start_pos, size_t __req_len,
  862.                  _CharT* __buffer)
  863.       {
  864.         switch(_M_base->_M_tag)
  865.           {
  866.           case __detail::_S_function:
  867.           case __detail::_S_substringfn:
  868.             {
  869.               char_producer<_CharT>* __fn =
  870.                 ((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn;
  871.               (*__fn)(__start_pos + _M_start, __req_len, __buffer);
  872.             }
  873.             break;
  874.           case __detail::_S_leaf:
  875.             {
  876.               __GC_CONST _CharT* __s =
  877.                 ((_Rope_RopeLeaf<_CharT,_Alloc>*)_M_base)->_M_data;
  878.               uninitialized_copy_n(__s + __start_pos + _M_start, __req_len,
  879.                                    __buffer);
  880.             }
  881.             break;
  882.           default:
  883.             break;
  884.           }
  885.       }
  886.      
  887.       typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
  888.         allocator_type;
  889.  
  890.       _Rope_RopeSubstring(_Rope_RopeRep<_CharT, _Alloc>* __b, size_t __s,
  891.                           size_t __l, const allocator_type& __a)
  892.       : _Rope_RopeFunction<_CharT, _Alloc>(this, __l, false, __a),
  893.         char_producer<_CharT>(), _M_base(__b), _M_start(__s)
  894.       {
  895. #ifndef __GC
  896.         _M_base->_M_ref_nonnil();
  897. #endif
  898.         this->_M_tag = __detail::_S_substringfn;
  899.       }
  900.     virtual ~_Rope_RopeSubstring() throw()
  901.       {
  902. #ifndef __GC
  903.         _M_base->_M_unref_nonnil();
  904.         // _M_free_c_string();  -- done by parent class
  905. #endif
  906.       }
  907.     };
  908.  
  909.   // Self-destructing pointers to Rope_rep.
  910.   // These are not conventional smart pointers.  Their
  911.   // only purpose in life is to ensure that unref is called
  912.   // on the pointer either at normal exit or if an exception
  913.   // is raised.  It is the caller's responsibility to
  914.   // adjust reference counts when these pointers are initialized
  915.   // or assigned to.  (This convention significantly reduces
  916.   // the number of potentially expensive reference count
  917.   // updates.)
  918. #ifndef __GC
  919.   template<class _CharT, class _Alloc>
  920.     struct _Rope_self_destruct_ptr
  921.     {
  922.       _Rope_RopeRep<_CharT, _Alloc>* _M_ptr;
  923.  
  924.       ~_Rope_self_destruct_ptr()
  925.       { _Rope_RopeRep<_CharT, _Alloc>::_S_unref(_M_ptr); }
  926. #if __cpp_exceptions
  927.       _Rope_self_destruct_ptr() : _M_ptr(0) { };
  928. #else
  929.       _Rope_self_destruct_ptr() { };
  930. #endif
  931.       _Rope_self_destruct_ptr(_Rope_RopeRep<_CharT, _Alloc>* __p)
  932.       : _M_ptr(__p) { }
  933.    
  934.       _Rope_RopeRep<_CharT, _Alloc>&
  935.       operator*()
  936.       { return *_M_ptr; }
  937.    
  938.       _Rope_RopeRep<_CharT, _Alloc>*
  939.       operator->()
  940.       { return _M_ptr; }
  941.    
  942.       operator _Rope_RopeRep<_CharT, _Alloc>*()
  943.       { return _M_ptr; }
  944.    
  945.       _Rope_self_destruct_ptr&
  946.       operator=(_Rope_RopeRep<_CharT, _Alloc>* __x)
  947.       { _M_ptr = __x; return *this; }
  948.     };
  949. #endif
  950.  
  951.   // Dereferencing a nonconst iterator has to return something
  952.   // that behaves almost like a reference.  It's not possible to
  953.   // return an actual reference since assignment requires extra
  954.   // work.  And we would get into the same problems as with the
  955.   // CD2 version of basic_string.
  956.   template<class _CharT, class _Alloc>
  957.     class _Rope_char_ref_proxy
  958.     {
  959.       friend class rope<_CharT, _Alloc>;
  960.       friend class _Rope_iterator<_CharT, _Alloc>;
  961.       friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;
  962. #ifdef __GC
  963.       typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
  964. #else
  965.       typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
  966. #endif
  967.       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
  968.       typedef rope<_CharT, _Alloc> _My_rope;
  969.       size_t _M_pos;
  970.       _CharT _M_current;
  971.       bool _M_current_valid;
  972.       _My_rope* _M_root;     // The whole rope.
  973.     public:
  974.       _Rope_char_ref_proxy(_My_rope* __r, size_t __p)
  975.       :  _M_pos(__p), _M_current(), _M_current_valid(false), _M_root(__r) { }
  976.  
  977.       _Rope_char_ref_proxy(const _Rope_char_ref_proxy& __x)
  978.       : _M_pos(__x._M_pos), _M_current(__x._M_current),
  979.         _M_current_valid(false), _M_root(__x._M_root) { }
  980.  
  981.       // Don't preserve cache if the reference can outlive the
  982.       // expression.  We claim that's not possible without calling
  983.       // a copy constructor or generating reference to a proxy
  984.       // reference.  We declare the latter to have undefined semantics.
  985.       _Rope_char_ref_proxy(_My_rope* __r, size_t __p, _CharT __c)
  986.       : _M_pos(__p), _M_current(__c), _M_current_valid(true), _M_root(__r) { }
  987.  
  988.       inline operator _CharT () const;
  989.  
  990.       _Rope_char_ref_proxy&
  991.       operator=(_CharT __c);
  992.    
  993.       _Rope_char_ptr_proxy<_CharT, _Alloc> operator&() const;
  994.      
  995.       _Rope_char_ref_proxy&
  996.       operator=(const _Rope_char_ref_proxy& __c)
  997.       { return operator=((_CharT)__c); }
  998.     };
  999.  
  1000.   template<class _CharT, class __Alloc>
  1001.     inline void
  1002.     swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a,
  1003.          _Rope_char_ref_proxy <_CharT, __Alloc > __b)
  1004.     {
  1005.       _CharT __tmp = __a;
  1006.       __a = __b;
  1007.       __b = __tmp;
  1008.     }
  1009.  
  1010.   template<class _CharT, class _Alloc>
  1011.     class _Rope_char_ptr_proxy
  1012.     {
  1013.       // XXX this class should be rewritten.
  1014.       friend class _Rope_char_ref_proxy<_CharT, _Alloc>;
  1015.       size_t _M_pos;
  1016.       rope<_CharT,_Alloc>* _M_root;     // The whole rope.
  1017.     public:
  1018.       _Rope_char_ptr_proxy(const _Rope_char_ref_proxy<_CharT,_Alloc>& __x)
  1019.       : _M_pos(__x._M_pos), _M_root(__x._M_root) { }
  1020.  
  1021.       _Rope_char_ptr_proxy(const _Rope_char_ptr_proxy& __x)
  1022.       : _M_pos(__x._M_pos), _M_root(__x._M_root) { }
  1023.  
  1024.       _Rope_char_ptr_proxy() { }
  1025.      
  1026.       _Rope_char_ptr_proxy(_CharT* __x)
  1027.       : _M_root(0), _M_pos(0) { }
  1028.  
  1029.       _Rope_char_ptr_proxy&
  1030.       operator=(const _Rope_char_ptr_proxy& __x)
  1031.       {
  1032.         _M_pos = __x._M_pos;
  1033.         _M_root = __x._M_root;
  1034.         return *this;
  1035.       }
  1036.  
  1037.       template<class _CharT2, class _Alloc2>
  1038.         friend bool
  1039.         operator==(const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __x,
  1040.                    const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __y);
  1041.  
  1042.       _Rope_char_ref_proxy<_CharT, _Alloc> operator*() const
  1043.       { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root, _M_pos); }
  1044.     };
  1045.  
  1046.   // Rope iterators:
  1047.   // Unlike in the C version, we cache only part of the stack
  1048.   // for rope iterators, since they must be efficiently copyable.
  1049.   // When we run out of cache, we have to reconstruct the iterator
  1050.   // value.
  1051.   // Pointers from iterators are not included in reference counts.
  1052.   // Iterators are assumed to be thread private.  Ropes can
  1053.   // be shared.
  1054.  
  1055.   template<class _CharT, class _Alloc>
  1056.     class _Rope_iterator_base
  1057.     : public std::iterator<std::random_access_iterator_tag, _CharT>
  1058.     {
  1059.       friend class rope<_CharT, _Alloc>;
  1060.     public:
  1061.       typedef _Alloc _allocator_type; // used in _Rope_rotate, VC++ workaround
  1062.       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
  1063.       // Borland doesn't want this to be protected.
  1064.     protected:
  1065.       enum { _S_path_cache_len = 4 }; // Must be <= 9.
  1066.       enum { _S_iterator_buf_len = 15 };
  1067.       size_t _M_current_pos;
  1068.       _RopeRep* _M_root;     // The whole rope.
  1069.       size_t _M_leaf_pos;    // Starting position for current leaf
  1070.       __GC_CONST _CharT* _M_buf_start;
  1071.                              // Buffer possibly
  1072.                              // containing current char.
  1073.       __GC_CONST _CharT* _M_buf_ptr;
  1074.                              // Pointer to current char in buffer.
  1075.                              // != 0 ==> buffer valid.
  1076.       __GC_CONST _CharT* _M_buf_end;
  1077.                              // One past __last valid char in buffer.
  1078.       // What follows is the path cache.  We go out of our
  1079.       // way to make this compact.
  1080.       // Path_end contains the bottom section of the path from
  1081.       // the root to the current leaf.
  1082.       const _RopeRep* _M_path_end[_S_path_cache_len];
  1083.       int _M_leaf_index;     // Last valid __pos in path_end;
  1084.                              // _M_path_end[0] ... _M_path_end[leaf_index-1]
  1085.                              // point to concatenation nodes.
  1086.       unsigned char _M_path_directions;
  1087.                           // (path_directions >> __i) & 1 is 1
  1088.                           // iff we got from _M_path_end[leaf_index - __i - 1]
  1089.                           // to _M_path_end[leaf_index - __i] by going to the
  1090.                           // __right. Assumes path_cache_len <= 9.
  1091.       _CharT _M_tmp_buf[_S_iterator_buf_len];
  1092.                         // Short buffer for surrounding chars.
  1093.                         // This is useful primarily for
  1094.                         // RopeFunctions.  We put the buffer
  1095.                         // here to avoid locking in the
  1096.                         // multithreaded case.
  1097.       // The cached path is generally assumed to be valid
  1098.       // only if the buffer is valid.
  1099.       static void _S_setbuf(_Rope_iterator_base& __x);
  1100.                                         // Set buffer contents given
  1101.                                         // path cache.
  1102.       static void _S_setcache(_Rope_iterator_base& __x);
  1103.                                         // Set buffer contents and
  1104.                                         // path cache.
  1105.       static void _S_setcache_for_incr(_Rope_iterator_base& __x);
  1106.                                         // As above, but assumes path
  1107.                                         // cache is valid for previous posn.
  1108.       _Rope_iterator_base() { }
  1109.  
  1110.       _Rope_iterator_base(_RopeRep* __root, size_t __pos)
  1111.       : _M_current_pos(__pos), _M_root(__root), _M_buf_ptr(0) { }
  1112.  
  1113.       void _M_incr(size_t __n);
  1114.       void _M_decr(size_t __n);
  1115.     public:
  1116.       size_t
  1117.       index() const
  1118.       { return _M_current_pos; }
  1119.    
  1120.       _Rope_iterator_base(const _Rope_iterator_base& __x)
  1121.       {
  1122.         if (0 != __x._M_buf_ptr)
  1123.           *this = __x;
  1124.         else
  1125.           {
  1126.             _M_current_pos = __x._M_current_pos;
  1127.             _M_root = __x._M_root;
  1128.             _M_buf_ptr = 0;
  1129.           }
  1130.       }
  1131.     };
  1132.  
  1133.   template<class _CharT, class _Alloc>
  1134.     class _Rope_iterator;
  1135.  
  1136.   template<class _CharT, class _Alloc>
  1137.     class _Rope_const_iterator
  1138.     : public _Rope_iterator_base<_CharT, _Alloc>
  1139.     {
  1140.       friend class rope<_CharT, _Alloc>;
  1141.     protected:
  1142.       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
  1143.       // The one from the base class may not be directly visible.
  1144.       _Rope_const_iterator(const _RopeRep* __root, size_t __pos)
  1145.       : _Rope_iterator_base<_CharT, _Alloc>(const_cast<_RopeRep*>(__root),
  1146.                                             __pos)
  1147.                    // Only nonconst iterators modify root ref count
  1148.       { }
  1149.   public:
  1150.       typedef _CharT reference;   // Really a value.  Returning a reference
  1151.                                   // Would be a mess, since it would have
  1152.                                   // to be included in refcount.
  1153.       typedef const _CharT* pointer;
  1154.  
  1155.     public:
  1156.       _Rope_const_iterator() { };
  1157.  
  1158.       _Rope_const_iterator(const _Rope_const_iterator& __x)
  1159.       : _Rope_iterator_base<_CharT,_Alloc>(__x) { }
  1160.  
  1161.       _Rope_const_iterator(const _Rope_iterator<_CharT,_Alloc>& __x);
  1162.    
  1163.       _Rope_const_iterator(const rope<_CharT, _Alloc>& __r, size_t __pos)
  1164.       : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos) { }
  1165.  
  1166.       _Rope_const_iterator&
  1167.       operator=(const _Rope_const_iterator& __x)
  1168.       {
  1169.         if (0 != __x._M_buf_ptr)
  1170.           *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x;
  1171.         else
  1172.           {
  1173.             this->_M_current_pos = __x._M_current_pos;
  1174.             this->_M_root = __x._M_root;
  1175.             this->_M_buf_ptr = 0;
  1176.           }
  1177.         return(*this);
  1178.       }
  1179.  
  1180.       reference
  1181.       operator*()
  1182.       {
  1183.         if (0 == this->_M_buf_ptr)
  1184.           this->_S_setcache(*this);
  1185.         return *this->_M_buf_ptr;
  1186.       }
  1187.  
  1188.       // Without this const version, Rope iterators do not meet the
  1189.       // requirements of an Input Iterator.
  1190.       reference
  1191.       operator*() const
  1192.       {
  1193.         return *const_cast<_Rope_const_iterator&>(*this);
  1194.       }
  1195.  
  1196.       _Rope_const_iterator&
  1197.       operator++()
  1198.       {
  1199.         __GC_CONST _CharT* __next;
  1200.         if (0 != this->_M_buf_ptr
  1201.             && (__next = this->_M_buf_ptr + 1) < this->_M_buf_end)
  1202.           {
  1203.             this->_M_buf_ptr = __next;
  1204.             ++this->_M_current_pos;
  1205.           }
  1206.         else
  1207.           this->_M_incr(1);
  1208.         return *this;
  1209.       }
  1210.  
  1211.       _Rope_const_iterator&
  1212.       operator+=(ptrdiff_t __n)
  1213.       {
  1214.         if (__n >= 0)
  1215.           this->_M_incr(__n);
  1216.         else
  1217.           this->_M_decr(-__n);
  1218.         return *this;
  1219.       }
  1220.  
  1221.       _Rope_const_iterator&
  1222.       operator--()
  1223.       {
  1224.         this->_M_decr(1);
  1225.         return *this;
  1226.       }
  1227.  
  1228.       _Rope_const_iterator&
  1229.       operator-=(ptrdiff_t __n)
  1230.       {
  1231.         if (__n >= 0)
  1232.           this->_M_decr(__n);
  1233.         else
  1234.           this->_M_incr(-__n);
  1235.         return *this;
  1236.       }
  1237.  
  1238.       _Rope_const_iterator
  1239.       operator++(int)
  1240.       {
  1241.         size_t __old_pos = this->_M_current_pos;
  1242.         this->_M_incr(1);
  1243.         return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
  1244.         // This makes a subsequent dereference expensive.
  1245.         // Perhaps we should instead copy the iterator
  1246.         // if it has a valid cache?
  1247.       }
  1248.  
  1249.       _Rope_const_iterator
  1250.       operator--(int)
  1251.       {
  1252.         size_t __old_pos = this->_M_current_pos;
  1253.         this->_M_decr(1);
  1254.         return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
  1255.       }
  1256.  
  1257.       template<class _CharT2, class _Alloc2>
  1258.         friend _Rope_const_iterator<_CharT2, _Alloc2>
  1259.         operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
  1260.                   ptrdiff_t __n);
  1261.  
  1262.       template<class _CharT2, class _Alloc2>
  1263.         friend _Rope_const_iterator<_CharT2, _Alloc2>
  1264.         operator+(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
  1265.                   ptrdiff_t __n);
  1266.  
  1267.       template<class _CharT2, class _Alloc2>
  1268.         friend _Rope_const_iterator<_CharT2, _Alloc2>
  1269.         operator+(ptrdiff_t __n,
  1270.                   const _Rope_const_iterator<_CharT2, _Alloc2>& __x);
  1271.  
  1272.       reference
  1273.       operator[](size_t __n)
  1274.       { return rope<_CharT, _Alloc>::_S_fetch(this->_M_root,
  1275.                                               this->_M_current_pos + __n); }
  1276.  
  1277.       template<class _CharT2, class _Alloc2>
  1278.         friend bool
  1279.         operator==(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
  1280.                    const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
  1281.  
  1282.       template<class _CharT2, class _Alloc2>
  1283.         friend bool
  1284.         operator<(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
  1285.                   const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
  1286.  
  1287.       template<class _CharT2, class _Alloc2>
  1288.         friend ptrdiff_t
  1289.         operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
  1290.                   const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
  1291.     };
  1292.  
  1293.   template<class _CharT, class _Alloc>
  1294.     class _Rope_iterator
  1295.     : public _Rope_iterator_base<_CharT, _Alloc>
  1296.     {
  1297.       friend class rope<_CharT, _Alloc>;
  1298.     protected:
  1299.       typedef typename _Rope_iterator_base<_CharT, _Alloc>::_RopeRep _RopeRep;
  1300.       rope<_CharT, _Alloc>* _M_root_rope;
  1301.  
  1302.       // root is treated as a cached version of this, and is used to
  1303.       // detect changes to the underlying rope.
  1304.  
  1305.       // Root is included in the reference count.  This is necessary
  1306.       // so that we can detect changes reliably.  Unfortunately, it
  1307.       // requires careful bookkeeping for the nonGC case.
  1308.       _Rope_iterator(rope<_CharT, _Alloc>* __r, size_t __pos)
  1309.       : _Rope_iterator_base<_CharT, _Alloc>(__r->_M_tree_ptr, __pos),
  1310.         _M_root_rope(__r)
  1311.       { _RopeRep::_S_ref(this->_M_root);
  1312.         if (!(__r -> empty()))
  1313.           this->_S_setcache(*this);
  1314.       }
  1315.  
  1316.       void _M_check();
  1317.     public:
  1318.       typedef _Rope_char_ref_proxy<_CharT, _Alloc>  reference;
  1319.       typedef _Rope_char_ref_proxy<_CharT, _Alloc>* pointer;
  1320.  
  1321.       rope<_CharT, _Alloc>&
  1322.       container()
  1323.       { return *_M_root_rope; }
  1324.  
  1325.       _Rope_iterator()
  1326.       {
  1327.         this->_M_root = 0;  // Needed for reference counting.
  1328.       };
  1329.  
  1330.       _Rope_iterator(const _Rope_iterator& __x)
  1331.       : _Rope_iterator_base<_CharT, _Alloc>(__x)
  1332.       {
  1333.         _M_root_rope = __x._M_root_rope;
  1334.         _RopeRep::_S_ref(this->_M_root);
  1335.       }
  1336.  
  1337.       _Rope_iterator(rope<_CharT, _Alloc>& __r, size_t __pos);
  1338.  
  1339.       ~_Rope_iterator()
  1340.       { _RopeRep::_S_unref(this->_M_root); }
  1341.  
  1342.       _Rope_iterator&
  1343.       operator=(const _Rope_iterator& __x)
  1344.       {
  1345.         _RopeRep* __old = this->_M_root;
  1346.        
  1347.         _RopeRep::_S_ref(__x._M_root);
  1348.         if (0 != __x._M_buf_ptr)
  1349.           {
  1350.             _M_root_rope = __x._M_root_rope;
  1351.             *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x;
  1352.           }
  1353.         else
  1354.           {
  1355.             this->_M_current_pos = __x._M_current_pos;
  1356.             this->_M_root = __x._M_root;
  1357.             _M_root_rope = __x._M_root_rope;
  1358.             this->_M_buf_ptr = 0;
  1359.           }
  1360.         _RopeRep::_S_unref(__old);
  1361.         return(*this);
  1362.       }
  1363.  
  1364.       reference
  1365.       operator*()
  1366.       {
  1367.         _M_check();
  1368.         if (0 == this->_M_buf_ptr)
  1369.           return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
  1370.                                                       this->_M_current_pos);
  1371.         else
  1372.           return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
  1373.                                                       this->_M_current_pos,
  1374.                                                       *this->_M_buf_ptr);
  1375.       }
  1376.  
  1377.       // See above comment.
  1378.       reference
  1379.       operator*() const
  1380.       {
  1381.         return *const_cast<_Rope_iterator&>(*this);
  1382.       }
  1383.  
  1384.       _Rope_iterator&
  1385.       operator++()
  1386.       {
  1387.         this->_M_incr(1);
  1388.         return *this;
  1389.       }
  1390.  
  1391.       _Rope_iterator&
  1392.       operator+=(ptrdiff_t __n)
  1393.       {
  1394.         if (__n >= 0)
  1395.           this->_M_incr(__n);
  1396.         else
  1397.           this->_M_decr(-__n);
  1398.         return *this;
  1399.       }
  1400.  
  1401.       _Rope_iterator&
  1402.       operator--()
  1403.       {
  1404.         this->_M_decr(1);
  1405.         return *this;
  1406.       }
  1407.  
  1408.       _Rope_iterator&
  1409.       operator-=(ptrdiff_t __n)
  1410.       {
  1411.         if (__n >= 0)
  1412.           this->_M_decr(__n);
  1413.         else
  1414.           this->_M_incr(-__n);
  1415.         return *this;
  1416.       }
  1417.  
  1418.       _Rope_iterator
  1419.       operator++(int)
  1420.       {
  1421.         size_t __old_pos = this->_M_current_pos;
  1422.         this->_M_incr(1);
  1423.         return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
  1424.       }
  1425.  
  1426.       _Rope_iterator
  1427.       operator--(int)
  1428.       {
  1429.         size_t __old_pos = this->_M_current_pos;
  1430.         this->_M_decr(1);
  1431.         return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
  1432.       }
  1433.  
  1434.       reference
  1435.       operator[](ptrdiff_t __n)
  1436.       { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
  1437.                                                     this->_M_current_pos
  1438.                                                     + __n); }
  1439.  
  1440.       template<class _CharT2, class _Alloc2>
  1441.         friend bool
  1442.         operator==(const _Rope_iterator<_CharT2, _Alloc2>& __x,
  1443.                    const _Rope_iterator<_CharT2, _Alloc2>& __y);
  1444.  
  1445.       template<class _CharT2, class _Alloc2>
  1446.         friend bool
  1447.         operator<(const _Rope_iterator<_CharT2, _Alloc2>& __x,
  1448.                   const _Rope_iterator<_CharT2, _Alloc2>& __y);
  1449.  
  1450.       template<class _CharT2, class _Alloc2>
  1451.         friend ptrdiff_t
  1452.         operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x,
  1453.                   const _Rope_iterator<_CharT2, _Alloc2>& __y);
  1454.  
  1455.       template<class _CharT2, class _Alloc2>
  1456.         friend _Rope_iterator<_CharT2, _Alloc2>
  1457.         operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);
  1458.  
  1459.       template<class _CharT2, class _Alloc2>
  1460.         friend _Rope_iterator<_CharT2, _Alloc2>
  1461.         operator+(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);
  1462.  
  1463.       template<class _CharT2, class _Alloc2>
  1464.         friend _Rope_iterator<_CharT2, _Alloc2>
  1465.         operator+(ptrdiff_t __n, const _Rope_iterator<_CharT2, _Alloc2>& __x);
  1466.     };
  1467.  
  1468.  
  1469.   template <class _CharT, class _Alloc>
  1470.     struct _Rope_base
  1471.     : public _Alloc
  1472.     {
  1473.       typedef _Alloc allocator_type;
  1474.  
  1475.       allocator_type
  1476.       get_allocator() const
  1477.       { return *static_cast<const _Alloc*>(this); }
  1478.  
  1479.       allocator_type&
  1480.       _M_get_allocator()
  1481.       { return *static_cast<_Alloc*>(this); }
  1482.  
  1483.       const allocator_type&
  1484.       _M_get_allocator() const
  1485.       { return *static_cast<const _Alloc*>(this); }
  1486.  
  1487.       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
  1488.       // The one in _Base may not be visible due to template rules.
  1489.  
  1490.       _Rope_base(_RopeRep* __t, const allocator_type&)
  1491.       : _M_tree_ptr(__t) { }
  1492.  
  1493.       _Rope_base(const allocator_type&) { }
  1494.  
  1495.       // The only data member of a rope:
  1496.       _RopeRep *_M_tree_ptr;
  1497.  
  1498. #define __ROPE_DEFINE_ALLOC(_Tp, __name) \
  1499.         typedef typename \
  1500.           _Alloc::template rebind<_Tp>::other __name##Alloc; \
  1501.         static _Tp* __name##_allocate(size_t __n) \
  1502.           { return __name##Alloc().allocate(__n); } \
  1503.         static void __name##_deallocate(_Tp *__p, size_t __n) \
  1504.           { __name##Alloc().deallocate(__p, __n); }
  1505.       __ROPE_DEFINE_ALLOCS(_Alloc)
  1506. #undef __ROPE_DEFINE_ALLOC
  1507.  
  1508.         protected:
  1509.       _Rope_base&
  1510.       operator=(const _Rope_base&);
  1511.      
  1512.       _Rope_base(const _Rope_base&);
  1513.     };
  1514.  
  1515.   /**
  1516.    *  This is an SGI extension.
  1517.    *  @ingroup SGIextensions
  1518.    *  @doctodo
  1519.    */
  1520.   template <class _CharT, class _Alloc>
  1521.     class rope : public _Rope_base<_CharT, _Alloc>
  1522.     {
  1523.     public:
  1524.       typedef _CharT value_type;
  1525.       typedef ptrdiff_t difference_type;
  1526.       typedef size_t size_type;
  1527.       typedef _CharT const_reference;
  1528.       typedef const _CharT* const_pointer;
  1529.       typedef _Rope_iterator<_CharT, _Alloc> iterator;
  1530.       typedef _Rope_const_iterator<_CharT, _Alloc> const_iterator;
  1531.       typedef _Rope_char_ref_proxy<_CharT, _Alloc> reference;
  1532.       typedef _Rope_char_ptr_proxy<_CharT, _Alloc> pointer;
  1533.  
  1534.       friend class _Rope_iterator<_CharT, _Alloc>;
  1535.       friend class _Rope_const_iterator<_CharT, _Alloc>;
  1536.       friend struct _Rope_RopeRep<_CharT, _Alloc>;
  1537.       friend class _Rope_iterator_base<_CharT, _Alloc>;
  1538.       friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;
  1539.       friend class _Rope_char_ref_proxy<_CharT, _Alloc>;
  1540.       friend struct _Rope_RopeSubstring<_CharT, _Alloc>;
  1541.  
  1542.     protected:
  1543.       typedef _Rope_base<_CharT, _Alloc> _Base;
  1544.       typedef typename _Base::allocator_type allocator_type;
  1545.       using _Base::_M_tree_ptr;
  1546.       using _Base::get_allocator;
  1547.       using _Base::_M_get_allocator;
  1548.       typedef __GC_CONST _CharT* _Cstrptr;
  1549.      
  1550.       static _CharT _S_empty_c_str[1];
  1551.      
  1552.       static bool
  1553.       _S_is0(_CharT __c)
  1554.       { return __c == _S_eos((_CharT*)0); }
  1555.      
  1556.       enum { _S_copy_max = 23 };
  1557.                 // For strings shorter than _S_copy_max, we copy to
  1558.                 // concatenate.
  1559.  
  1560.       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
  1561.       typedef _Rope_RopeConcatenation<_CharT, _Alloc> _RopeConcatenation;
  1562.       typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf;
  1563.       typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction;
  1564.       typedef _Rope_RopeSubstring<_CharT, _Alloc> _RopeSubstring;
  1565.  
  1566.       // Retrieve a character at the indicated position.
  1567.       static _CharT _S_fetch(_RopeRep* __r, size_type __pos);
  1568.  
  1569. #ifndef __GC
  1570.       // Obtain a pointer to the character at the indicated position.
  1571.       // The pointer can be used to change the character.
  1572.       // If such a pointer cannot be produced, as is frequently the
  1573.       // case, 0 is returned instead.
  1574.       // (Returns nonzero only if all nodes in the path have a refcount
  1575.       // of 1.)
  1576.       static _CharT* _S_fetch_ptr(_RopeRep* __r, size_type __pos);
  1577. #endif
  1578.  
  1579.       static bool
  1580.       _S_apply_to_pieces(// should be template parameter
  1581.                          _Rope_char_consumer<_CharT>& __c,
  1582.                          const _RopeRep* __r,
  1583.                          size_t __begin, size_t __end);
  1584.                          // begin and end are assumed to be in range.
  1585.  
  1586. #ifndef __GC
  1587.       static void
  1588.       _S_unref(_RopeRep* __t)
  1589.       { _RopeRep::_S_unref(__t); }
  1590.  
  1591.       static void
  1592.       _S_ref(_RopeRep* __t)
  1593.       { _RopeRep::_S_ref(__t); }
  1594.  
  1595. #else /* __GC */
  1596.       static void _S_unref(_RopeRep*) { }
  1597.       static void _S_ref(_RopeRep*) { }
  1598. #endif
  1599.  
  1600. #ifdef __GC
  1601.       typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
  1602. #else
  1603.       typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
  1604. #endif
  1605.  
  1606.       // _Result is counted in refcount.
  1607.       static _RopeRep* _S_substring(_RopeRep* __base,
  1608.                                     size_t __start, size_t __endp1);
  1609.  
  1610.       static _RopeRep* _S_concat_char_iter(_RopeRep* __r,
  1611.                                            const _CharT* __iter, size_t __slen);
  1612.       // Concatenate rope and char ptr, copying __s.
  1613.       // Should really take an arbitrary iterator.
  1614.       // Result is counted in refcount.
  1615.       static _RopeRep* _S_destr_concat_char_iter(_RopeRep* __r,
  1616.                                                  const _CharT* __iter,
  1617.                                                  size_t __slen)
  1618.         // As above, but one reference to __r is about to be
  1619.         // destroyed.  Thus the pieces may be recycled if all
  1620.         // relevant reference counts are 1.
  1621. #ifdef __GC
  1622.         // We can't really do anything since refcounts are unavailable.
  1623.       { return _S_concat_char_iter(__r, __iter, __slen); }
  1624. #else
  1625.       ;
  1626. #endif
  1627.  
  1628.       static _RopeRep* _S_concat(_RopeRep* __left, _RopeRep* __right);
  1629.       // General concatenation on _RopeRep.  _Result
  1630.       // has refcount of 1.  Adjusts argument refcounts.
  1631.  
  1632.    public:
  1633.       void
  1634.       apply_to_pieces(size_t __begin, size_t __end,
  1635.                       _Rope_char_consumer<_CharT>& __c) const
  1636.       { _S_apply_to_pieces(__c, this->_M_tree_ptr, __begin, __end); }
  1637.  
  1638.    protected:
  1639.  
  1640.       static size_t
  1641.       _S_rounded_up_size(size_t __n)
  1642.       { return _RopeLeaf::_S_rounded_up_size(__n); }
  1643.  
  1644.       static size_t
  1645.       _S_allocated_capacity(size_t __n)
  1646.       {
  1647.         if (_S_is_basic_char_type((_CharT*)0))
  1648.           return _S_rounded_up_size(__n) - 1;
  1649.         else
  1650.           return _S_rounded_up_size(__n);
  1651.        
  1652.       }
  1653.  
  1654.       // Allocate and construct a RopeLeaf using the supplied allocator
  1655.       // Takes ownership of s instead of copying.
  1656.       static _RopeLeaf*
  1657.       _S_new_RopeLeaf(__GC_CONST _CharT *__s,
  1658.                       size_t __size, allocator_type& __a)
  1659.       {
  1660.         _RopeLeaf* __space = typename _Base::_LAlloc(__a).allocate(1);
  1661.         return new(__space) _RopeLeaf(__s, __size, __a);
  1662.       }
  1663.  
  1664.       static _RopeConcatenation*
  1665.       _S_new_RopeConcatenation(_RopeRep* __left, _RopeRep* __right,
  1666.                                allocator_type& __a)
  1667.       {
  1668.         _RopeConcatenation* __space = typename _Base::_CAlloc(__a).allocate(1);
  1669.         return new(__space) _RopeConcatenation(__left, __right, __a);
  1670.       }
  1671.  
  1672.       static _RopeFunction*
  1673.       _S_new_RopeFunction(char_producer<_CharT>* __f,
  1674.                           size_t __size, bool __d, allocator_type& __a)
  1675.       {
  1676.         _RopeFunction* __space = typename _Base::_FAlloc(__a).allocate(1);
  1677.         return new(__space) _RopeFunction(__f, __size, __d, __a);
  1678.       }
  1679.  
  1680.       static _RopeSubstring*
  1681.       _S_new_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s,
  1682.                            size_t __l, allocator_type& __a)
  1683.       {
  1684.         _RopeSubstring* __space = typename _Base::_SAlloc(__a).allocate(1);
  1685.         return new(__space) _RopeSubstring(__b, __s, __l, __a);
  1686.       }
  1687.      
  1688.       static _RopeLeaf*
  1689.       _S_RopeLeaf_from_unowned_char_ptr(const _CharT *__s,
  1690.                                         size_t __size, allocator_type& __a)
  1691. #define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) \
  1692.                 _S_RopeLeaf_from_unowned_char_ptr(__s, __size, __a)
  1693.       {
  1694.         if (0 == __size)
  1695.           return 0;
  1696.         _CharT* __buf = __a.allocate(_S_rounded_up_size(__size));
  1697.        
  1698.         __uninitialized_copy_n_a(__s, __size, __buf, __a);
  1699.         _S_cond_store_eos(__buf[__size]);
  1700.         __try
  1701.           { return _S_new_RopeLeaf(__buf, __size, __a); }
  1702.         __catch(...)
  1703.           {
  1704.             _RopeRep::__STL_FREE_STRING(__buf, __size, __a);
  1705.             __throw_exception_again;
  1706.           }
  1707.       }
  1708.  
  1709.       // Concatenation of nonempty strings.
  1710.       // Always builds a concatenation node.
  1711.       // Rebalances if the result is too deep.
  1712.       // Result has refcount 1.
  1713.       // Does not increment left and right ref counts even though
  1714.       // they are referenced.
  1715.       static _RopeRep*
  1716.       _S_tree_concat(_RopeRep* __left, _RopeRep* __right);
  1717.  
  1718.       // Concatenation helper functions
  1719.       static _RopeLeaf*
  1720.       _S_leaf_concat_char_iter(_RopeLeaf* __r,
  1721.                                const _CharT* __iter, size_t __slen);
  1722.       // Concatenate by copying leaf.
  1723.       // should take an arbitrary iterator
  1724.       // result has refcount 1.
  1725. #ifndef __GC
  1726.       static _RopeLeaf*
  1727.       _S_destr_leaf_concat_char_iter(_RopeLeaf* __r,
  1728.                                      const _CharT* __iter, size_t __slen);
  1729.       // A version that potentially clobbers __r if __r->_M_ref_count == 1.
  1730. #endif
  1731.  
  1732.     private:
  1733.      
  1734.       static size_t _S_char_ptr_len(const _CharT* __s);
  1735.       // slightly generalized strlen
  1736.  
  1737.       rope(_RopeRep* __t, const allocator_type& __a = allocator_type())
  1738.       : _Base(__t, __a) { }
  1739.  
  1740.  
  1741.       // Copy __r to the _CharT buffer.
  1742.       // Returns __buffer + __r->_M_size.
  1743.       // Assumes that buffer is uninitialized.
  1744.       static _CharT* _S_flatten(_RopeRep* __r, _CharT* __buffer);
  1745.  
  1746.       // Again, with explicit starting position and length.
  1747.       // Assumes that buffer is uninitialized.
  1748.       static _CharT* _S_flatten(_RopeRep* __r,
  1749.                                 size_t __start, size_t __len,
  1750.                                 _CharT* __buffer);
  1751.  
  1752.       static const unsigned long
  1753.       _S_min_len[__detail::_S_max_rope_depth + 1];
  1754.      
  1755.       static bool
  1756.       _S_is_balanced(_RopeRep* __r)
  1757.       { return (__r->_M_size >= _S_min_len[__r->_M_depth]); }
  1758.  
  1759.       static bool
  1760.       _S_is_almost_balanced(_RopeRep* __r)
  1761.       { return (__r->_M_depth == 0
  1762.                 || __r->_M_size >= _S_min_len[__r->_M_depth - 1]); }
  1763.  
  1764.       static bool
  1765.       _S_is_roughly_balanced(_RopeRep* __r)
  1766.       { return (__r->_M_depth <= 1
  1767.                 || __r->_M_size >= _S_min_len[__r->_M_depth - 2]); }
  1768.  
  1769.       // Assumes the result is not empty.
  1770.       static _RopeRep*
  1771.       _S_concat_and_set_balanced(_RopeRep* __left, _RopeRep* __right)
  1772.       {
  1773.         _RopeRep* __result = _S_concat(__left, __right);
  1774.         if (_S_is_balanced(__result))
  1775.           __result->_M_is_balanced = true;
  1776.         return __result;
  1777.       }
  1778.  
  1779.       // The basic rebalancing operation.  Logically copies the
  1780.       // rope.  The result has refcount of 1.  The client will
  1781.       // usually decrement the reference count of __r.
  1782.       // The result is within height 2 of balanced by the above
  1783.       // definition.
  1784.       static _RopeRep* _S_balance(_RopeRep* __r);
  1785.  
  1786.       // Add all unbalanced subtrees to the forest of balanced trees.
  1787.       // Used only by balance.
  1788.       static void _S_add_to_forest(_RopeRep*__r, _RopeRep** __forest);
  1789.  
  1790.       // Add __r to forest, assuming __r is already balanced.
  1791.       static void _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest);
  1792.      
  1793.       // Print to stdout, exposing structure
  1794.       static void _S_dump(_RopeRep* __r, int __indent = 0);
  1795.      
  1796.       // Return -1, 0, or 1 if __x < __y, __x == __y, or __x > __y resp.
  1797.       static int _S_compare(const _RopeRep* __x, const _RopeRep* __y);
  1798.      
  1799.     public:
  1800.       bool
  1801.       empty() const
  1802.       { return 0 == this->_M_tree_ptr; }
  1803.      
  1804.       // Comparison member function.  This is public only for those
  1805.       // clients that need a ternary comparison.  Others
  1806.       // should use the comparison operators below.
  1807.       int
  1808.       compare(const rope& __y) const
  1809.       { return _S_compare(this->_M_tree_ptr, __y._M_tree_ptr); }
  1810.  
  1811.       rope(const _CharT* __s, const allocator_type& __a = allocator_type())
  1812.       : _Base(__a)
  1813.       {
  1814.         this->_M_tree_ptr =
  1815.           __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, _S_char_ptr_len(__s),
  1816.                                            _M_get_allocator());
  1817.       }
  1818.  
  1819.       rope(const _CharT* __s, size_t __len,
  1820.            const allocator_type& __a = allocator_type())
  1821.       : _Base(__a)
  1822.       {
  1823.         this->_M_tree_ptr =
  1824.           __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __len, _M_get_allocator());
  1825.       }
  1826.  
  1827.       // Should perhaps be templatized with respect to the iterator type
  1828.       // and use Sequence_buffer.  (It should perhaps use sequence_buffer
  1829.       // even now.)
  1830.       rope(const _CharT* __s, const _CharT* __e,
  1831.            const allocator_type& __a = allocator_type())
  1832.       : _Base(__a)
  1833.       {
  1834.         this->_M_tree_ptr =
  1835.           __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __e - __s, _M_get_allocator());
  1836.       }
  1837.  
  1838.       rope(const const_iterator& __s, const const_iterator& __e,
  1839.            const allocator_type& __a = allocator_type())
  1840.       : _Base(_S_substring(__s._M_root, __s._M_current_pos,
  1841.                            __e._M_current_pos), __a)
  1842.       { }
  1843.  
  1844.       rope(const iterator& __s, const iterator& __e,
  1845.            const allocator_type& __a = allocator_type())
  1846.       : _Base(_S_substring(__s._M_root, __s._M_current_pos,
  1847.                            __e._M_current_pos), __a)
  1848.       { }
  1849.  
  1850.       rope(_CharT __c, const allocator_type& __a = allocator_type())
  1851.       : _Base(__a)
  1852.       {
  1853.         _CharT* __buf = this->_Data_allocate(_S_rounded_up_size(1));
  1854.        
  1855.         _M_get_allocator().construct(__buf, __c);
  1856.         __try
  1857.           {
  1858.             this->_M_tree_ptr = _S_new_RopeLeaf(__buf, 1,
  1859.                                                 _M_get_allocator());
  1860.           }
  1861.         __catch(...)
  1862.           {
  1863.             _RopeRep::__STL_FREE_STRING(__buf, 1, _M_get_allocator());
  1864.             __throw_exception_again;
  1865.           }
  1866.       }
  1867.  
  1868.       rope(size_t __n, _CharT __c,
  1869.            const allocator_type& __a = allocator_type());
  1870.  
  1871.       rope(const allocator_type& __a = allocator_type())
  1872.       : _Base(0, __a) { }
  1873.  
  1874.       // Construct a rope from a function that can compute its members
  1875.       rope(char_producer<_CharT> *__fn, size_t __len, bool __delete_fn,
  1876.            const allocator_type& __a = allocator_type())
  1877.       : _Base(__a)
  1878.       {
  1879.         this->_M_tree_ptr = (0 == __len)
  1880.           ? 0
  1881.           : _S_new_RopeFunction(__fn, __len, __delete_fn, _M_get_allocator());
  1882.       }
  1883.  
  1884.       rope(const rope& __x, const allocator_type& __a = allocator_type())
  1885.       : _Base(__x._M_tree_ptr, __a)
  1886.       { _S_ref(this->_M_tree_ptr); }
  1887.  
  1888.       ~rope() throw()
  1889.       { _S_unref(this->_M_tree_ptr); }
  1890.  
  1891.       rope&
  1892.       operator=(const rope& __x)
  1893.       {
  1894.         _RopeRep* __old = this->_M_tree_ptr;
  1895.         this->_M_tree_ptr = __x._M_tree_ptr;
  1896.         _S_ref(this->_M_tree_ptr);
  1897.         _S_unref(__old);
  1898.         return *this;
  1899.       }
  1900.  
  1901.       void
  1902.       clear()
  1903.       {
  1904.         _S_unref(this->_M_tree_ptr);
  1905.         this->_M_tree_ptr = 0;
  1906.       }
  1907.      
  1908.       void
  1909.       push_back(_CharT __x)
  1910.       {
  1911.         _RopeRep* __old = this->_M_tree_ptr;
  1912.         this->_M_tree_ptr
  1913.           = _S_destr_concat_char_iter(this->_M_tree_ptr, &__x, 1);
  1914.         _S_unref(__old);
  1915.       }
  1916.  
  1917.       void
  1918.       pop_back()
  1919.       {
  1920.         _RopeRep* __old = this->_M_tree_ptr;
  1921.         this->_M_tree_ptr = _S_substring(this->_M_tree_ptr,
  1922.                                          0, this->_M_tree_ptr->_M_size - 1);
  1923.         _S_unref(__old);
  1924.       }
  1925.  
  1926.       _CharT
  1927.       back() const
  1928.       { return _S_fetch(this->_M_tree_ptr, this->_M_tree_ptr->_M_size - 1); }
  1929.  
  1930.       void
  1931.       push_front(_CharT __x)
  1932.       {
  1933.         _RopeRep* __old = this->_M_tree_ptr;
  1934.         _RopeRep* __left =
  1935.           __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1, _M_get_allocator());
  1936.         __try
  1937.           {
  1938.             this->_M_tree_ptr = _S_concat(__left, this->_M_tree_ptr);
  1939.             _S_unref(__old);
  1940.             _S_unref(__left);
  1941.           }
  1942.         __catch(...)
  1943.           {
  1944.             _S_unref(__left);
  1945.             __throw_exception_again;
  1946.           }
  1947.       }
  1948.  
  1949.       void
  1950.       pop_front()
  1951.       {
  1952.         _RopeRep* __old = this->_M_tree_ptr;
  1953.         this->_M_tree_ptr
  1954.           = _S_substring(this->_M_tree_ptr, 1, this->_M_tree_ptr->_M_size);
  1955.         _S_unref(__old);
  1956.       }
  1957.  
  1958.       _CharT
  1959.       front() const
  1960.       { return _S_fetch(this->_M_tree_ptr, 0); }
  1961.  
  1962.       void
  1963.       balance()
  1964.       {
  1965.         _RopeRep* __old = this->_M_tree_ptr;
  1966.         this->_M_tree_ptr = _S_balance(this->_M_tree_ptr);
  1967.         _S_unref(__old);
  1968.       }
  1969.  
  1970.       void
  1971.       copy(_CharT* __buffer) const
  1972.       {
  1973.         _Destroy_const(__buffer, __buffer + size(), _M_get_allocator());
  1974.         _S_flatten(this->_M_tree_ptr, __buffer);
  1975.       }
  1976.  
  1977.       // This is the copy function from the standard, but
  1978.       // with the arguments reordered to make it consistent with the
  1979.       // rest of the interface.
  1980.       // Note that this guaranteed not to compile if the draft standard
  1981.       // order is assumed.
  1982.       size_type
  1983.       copy(size_type __pos, size_type __n, _CharT* __buffer) const
  1984.       {
  1985.         size_t __size = size();
  1986.         size_t __len = (__pos + __n > __size? __size - __pos : __n);
  1987.  
  1988.         _Destroy_const(__buffer, __buffer + __len, _M_get_allocator());
  1989.         _S_flatten(this->_M_tree_ptr, __pos, __len, __buffer);
  1990.         return __len;
  1991.       }
  1992.  
  1993.       // Print to stdout, exposing structure.  May be useful for
  1994.       // performance debugging.
  1995.       void
  1996.       dump()
  1997.       { _S_dump(this->_M_tree_ptr); }
  1998.      
  1999.       // Convert to 0 terminated string in new allocated memory.
  2000.       // Embedded 0s in the input do not terminate the copy.
  2001.       const _CharT* c_str() const;
  2002.  
  2003.       // As above, but also use the flattened representation as
  2004.       // the new rope representation.
  2005.       const _CharT* replace_with_c_str();
  2006.      
  2007.       // Reclaim memory for the c_str generated flattened string.
  2008.       // Intentionally undocumented, since it's hard to say when this
  2009.       // is safe for multiple threads.
  2010.       void
  2011.       delete_c_str ()
  2012.       {
  2013.         if (0 == this->_M_tree_ptr)
  2014.           return;
  2015.         if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag &&
  2016.             ((_RopeLeaf*)this->_M_tree_ptr)->_M_data ==
  2017.             this->_M_tree_ptr->_M_c_string)
  2018.           {
  2019.             // Representation shared
  2020.             return;
  2021.           }
  2022. #ifndef __GC
  2023.         this->_M_tree_ptr->_M_free_c_string();
  2024. #endif
  2025.         this->_M_tree_ptr->_M_c_string = 0;
  2026.       }
  2027.  
  2028.       _CharT
  2029.       operator[] (size_type __pos) const
  2030.       { return _S_fetch(this->_M_tree_ptr, __pos); }
  2031.  
  2032.       _CharT
  2033.       at(size_type __pos) const
  2034.       {
  2035.         // if (__pos >= size()) throw out_of_range;  // XXX
  2036.         return (*this)[__pos];
  2037.       }
  2038.  
  2039.       const_iterator
  2040.       begin() const
  2041.       { return(const_iterator(this->_M_tree_ptr, 0)); }
  2042.  
  2043.       // An easy way to get a const iterator from a non-const container.
  2044.       const_iterator
  2045.       const_begin() const
  2046.       { return(const_iterator(this->_M_tree_ptr, 0)); }
  2047.  
  2048.       const_iterator
  2049.       end() const
  2050.       { return(const_iterator(this->_M_tree_ptr, size())); }
  2051.  
  2052.       const_iterator
  2053.       const_end() const
  2054.       { return(const_iterator(this->_M_tree_ptr, size())); }
  2055.  
  2056.       size_type
  2057.       size() const
  2058.       { return(0 == this->_M_tree_ptr? 0 : this->_M_tree_ptr->_M_size); }
  2059.      
  2060.       size_type
  2061.       length() const
  2062.       { return size(); }
  2063.  
  2064.       size_type
  2065.       max_size() const
  2066.       {
  2067.         return _S_min_len[int(__detail::_S_max_rope_depth) - 1] - 1;
  2068.         //  Guarantees that the result can be sufficiently
  2069.         //  balanced.  Longer ropes will probably still work,
  2070.         //  but it's harder to make guarantees.
  2071.       }
  2072.  
  2073.       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
  2074.  
  2075.       const_reverse_iterator
  2076.       rbegin() const
  2077.       { return const_reverse_iterator(end()); }
  2078.  
  2079.       const_reverse_iterator
  2080.       const_rbegin() const
  2081.       { return const_reverse_iterator(end()); }
  2082.  
  2083.       const_reverse_iterator
  2084.       rend() const
  2085.       { return const_reverse_iterator(begin()); }
  2086.      
  2087.       const_reverse_iterator
  2088.       const_rend() const
  2089.       { return const_reverse_iterator(begin()); }
  2090.  
  2091.       template<class _CharT2, class _Alloc2>
  2092.         friend rope<_CharT2, _Alloc2>
  2093.         operator+(const rope<_CharT2, _Alloc2>& __left,
  2094.                   const rope<_CharT2, _Alloc2>& __right);
  2095.  
  2096.       template<class _CharT2, class _Alloc2>
  2097.         friend rope<_CharT2, _Alloc2>
  2098.         operator+(const rope<_CharT2, _Alloc2>& __left, const _CharT2* __right);
  2099.  
  2100.       template<class _CharT2, class _Alloc2>
  2101.         friend rope<_CharT2, _Alloc2>
  2102.         operator+(const rope<_CharT2, _Alloc2>& __left, _CharT2 __right);
  2103.  
  2104.       // The symmetric cases are intentionally omitted, since they're
  2105.       // presumed to be less common, and we don't handle them as well.
  2106.  
  2107.       // The following should really be templatized.  The first
  2108.       // argument should be an input iterator or forward iterator with
  2109.       // value_type _CharT.
  2110.       rope&
  2111.       append(const _CharT* __iter, size_t __n)
  2112.       {
  2113.         _RopeRep* __result =
  2114.           _S_destr_concat_char_iter(this->_M_tree_ptr, __iter, __n);
  2115.         _S_unref(this->_M_tree_ptr);
  2116.         this->_M_tree_ptr = __result;
  2117.         return *this;
  2118.       }
  2119.  
  2120.       rope&
  2121.       append(const _CharT* __c_string)
  2122.       {
  2123.         size_t __len = _S_char_ptr_len(__c_string);
  2124.         append(__c_string, __len);
  2125.         return(*this);
  2126.       }
  2127.  
  2128.       rope&
  2129.       append(const _CharT* __s, const _CharT* __e)
  2130.       {
  2131.         _RopeRep* __result =
  2132.           _S_destr_concat_char_iter(this->_M_tree_ptr, __s, __e - __s);
  2133.         _S_unref(this->_M_tree_ptr);
  2134.         this->_M_tree_ptr = __result;
  2135.         return *this;
  2136.       }
  2137.  
  2138.       rope&
  2139.       append(const_iterator __s, const_iterator __e)
  2140.       {
  2141.         _Self_destruct_ptr __appendee(_S_substring(__s._M_root,
  2142.                                                    __s._M_current_pos,
  2143.                                                    __e._M_current_pos));
  2144.         _RopeRep* __result = _S_concat(this->_M_tree_ptr,
  2145.                                        (_RopeRep*)__appendee);
  2146.         _S_unref(this->_M_tree_ptr);
  2147.         this->_M_tree_ptr = __result;
  2148.         return *this;
  2149.       }
  2150.  
  2151.       rope&
  2152.       append(_CharT __c)
  2153.       {
  2154.         _RopeRep* __result =
  2155.           _S_destr_concat_char_iter(this->_M_tree_ptr, &__c, 1);
  2156.         _S_unref(this->_M_tree_ptr);
  2157.         this->_M_tree_ptr = __result;
  2158.         return *this;
  2159.       }
  2160.  
  2161.       rope&
  2162.       append()
  2163.       { return append(_CharT()); }  // XXX why?
  2164.  
  2165.       rope&
  2166.       append(const rope& __y)
  2167.       {
  2168.         _RopeRep* __result = _S_concat(this->_M_tree_ptr, __y._M_tree_ptr);
  2169.         _S_unref(this->_M_tree_ptr);
  2170.         this->_M_tree_ptr = __result;
  2171.         return *this;
  2172.       }
  2173.  
  2174.       rope&
  2175.       append(size_t __n, _CharT __c)
  2176.       {
  2177.         rope<_CharT,_Alloc> __last(__n, __c);
  2178.         return append(__last);
  2179.       }
  2180.  
  2181.       void
  2182.       swap(rope& __b)
  2183.       {
  2184.         _RopeRep* __tmp = this->_M_tree_ptr;
  2185.         this->_M_tree_ptr = __b._M_tree_ptr;
  2186.         __b._M_tree_ptr = __tmp;
  2187.       }
  2188.  
  2189.     protected:
  2190.       // Result is included in refcount.
  2191.       static _RopeRep*
  2192.       replace(_RopeRep* __old, size_t __pos1,
  2193.               size_t __pos2, _RopeRep* __r)
  2194.       {
  2195.         if (0 == __old)
  2196.           {
  2197.             _S_ref(__r);
  2198.             return __r;
  2199.           }
  2200.         _Self_destruct_ptr __left(_S_substring(__old, 0, __pos1));
  2201.         _Self_destruct_ptr __right(_S_substring(__old, __pos2, __old->_M_size));
  2202.         _RopeRep* __result;
  2203.  
  2204.         if (0 == __r)
  2205.           __result = _S_concat(__left, __right);
  2206.         else
  2207.           {
  2208.             _Self_destruct_ptr __left_result(_S_concat(__left, __r));
  2209.             __result = _S_concat(__left_result, __right);
  2210.           }
  2211.         return __result;
  2212.       }
  2213.  
  2214.     public:
  2215.       void
  2216.       insert(size_t __p, const rope& __r)
  2217.       {
  2218.         _RopeRep* __result =
  2219.           replace(this->_M_tree_ptr, __p, __p, __r._M_tree_ptr);
  2220.         _S_unref(this->_M_tree_ptr);
  2221.         this->_M_tree_ptr = __result;
  2222.       }
  2223.  
  2224.       void
  2225.       insert(size_t __p, size_t __n, _CharT __c)
  2226.       {
  2227.         rope<_CharT,_Alloc> __r(__n,__c);
  2228.         insert(__p, __r);
  2229.       }
  2230.      
  2231.       void
  2232.       insert(size_t __p, const _CharT* __i, size_t __n)
  2233.       {
  2234.         _Self_destruct_ptr __left(_S_substring(this->_M_tree_ptr, 0, __p));
  2235.         _Self_destruct_ptr __right(_S_substring(this->_M_tree_ptr,
  2236.                                                 __p, size()));
  2237.         _Self_destruct_ptr __left_result(_S_concat_char_iter(__left, __i, __n));
  2238.         // _S_ destr_concat_char_iter should be safe here.
  2239.         // But as it stands it's probably not a win, since __left
  2240.         // is likely to have additional references.
  2241.         _RopeRep* __result = _S_concat(__left_result, __right);
  2242.         _S_unref(this->_M_tree_ptr);
  2243.         this->_M_tree_ptr = __result;
  2244.       }
  2245.  
  2246.       void
  2247.       insert(size_t __p, const _CharT* __c_string)
  2248.       { insert(__p, __c_string, _S_char_ptr_len(__c_string)); }
  2249.  
  2250.       void
  2251.       insert(size_t __p, _CharT __c)
  2252.       { insert(__p, &__c, 1); }
  2253.  
  2254.       void
  2255.       insert(size_t __p)
  2256.       {
  2257.         _CharT __c = _CharT();
  2258.         insert(__p, &__c, 1);
  2259.       }
  2260.  
  2261.       void
  2262.       insert(size_t __p, const _CharT* __i, const _CharT* __j)
  2263.       {
  2264.         rope __r(__i, __j);
  2265.         insert(__p, __r);
  2266.       }
  2267.  
  2268.       void
  2269.       insert(size_t __p, const const_iterator& __i,
  2270.              const const_iterator& __j)
  2271.       {
  2272.         rope __r(__i, __j);
  2273.         insert(__p, __r);
  2274.       }
  2275.  
  2276.       void
  2277.       insert(size_t __p, const iterator& __i,
  2278.              const iterator& __j)
  2279.       {
  2280.         rope __r(__i, __j);
  2281.         insert(__p, __r);
  2282.       }
  2283.  
  2284.       // (position, length) versions of replace operations:
  2285.      
  2286.       void
  2287.       replace(size_t __p, size_t __n, const rope& __r)
  2288.       {
  2289.         _RopeRep* __result =
  2290.           replace(this->_M_tree_ptr, __p, __p + __n, __r._M_tree_ptr);
  2291.         _S_unref(this->_M_tree_ptr);
  2292.         this->_M_tree_ptr = __result;
  2293.       }
  2294.  
  2295.       void
  2296.       replace(size_t __p, size_t __n,
  2297.               const _CharT* __i, size_t __i_len)
  2298.       {
  2299.         rope __r(__i, __i_len);
  2300.         replace(__p, __n, __r);
  2301.       }
  2302.  
  2303.       void
  2304.       replace(size_t __p, size_t __n, _CharT __c)
  2305.       {
  2306.         rope __r(__c);
  2307.         replace(__p, __n, __r);
  2308.       }
  2309.  
  2310.       void
  2311.       replace(size_t __p, size_t __n, const _CharT* __c_string)
  2312.       {
  2313.         rope __r(__c_string);
  2314.         replace(__p, __n, __r);
  2315.       }
  2316.      
  2317.       void
  2318.       replace(size_t __p, size_t __n,
  2319.               const _CharT* __i, const _CharT* __j)
  2320.       {
  2321.         rope __r(__i, __j);
  2322.         replace(__p, __n, __r);
  2323.       }
  2324.      
  2325.       void
  2326.       replace(size_t __p, size_t __n,
  2327.               const const_iterator& __i, const const_iterator& __j)
  2328.       {
  2329.         rope __r(__i, __j);
  2330.         replace(__p, __n, __r);
  2331.       }
  2332.  
  2333.       void
  2334.       replace(size_t __p, size_t __n,
  2335.               const iterator& __i, const iterator& __j)
  2336.       {
  2337.         rope __r(__i, __j);
  2338.         replace(__p, __n, __r);
  2339.       }
  2340.  
  2341.       // Single character variants:
  2342.       void
  2343.       replace(size_t __p, _CharT __c)
  2344.       {
  2345.         iterator __i(this, __p);
  2346.         *__i = __c;
  2347.       }
  2348.  
  2349.       void
  2350.       replace(size_t __p, const rope& __r)
  2351.       { replace(__p, 1, __r); }
  2352.  
  2353.       void
  2354.       replace(size_t __p, const _CharT* __i, size_t __i_len)
  2355.       { replace(__p, 1, __i, __i_len); }
  2356.  
  2357.       void
  2358.       replace(size_t __p, const _CharT* __c_string)
  2359.       { replace(__p, 1, __c_string); }
  2360.  
  2361.       void
  2362.       replace(size_t __p, const _CharT* __i, const _CharT* __j)
  2363.       { replace(__p, 1, __i, __j); }
  2364.  
  2365.       void
  2366.       replace(size_t __p, const const_iterator& __i,
  2367.               const const_iterator& __j)
  2368.       { replace(__p, 1, __i, __j); }
  2369.  
  2370.       void
  2371.       replace(size_t __p, const iterator& __i,
  2372.               const iterator& __j)
  2373.       { replace(__p, 1, __i, __j); }
  2374.  
  2375.       // Erase, (position, size) variant.
  2376.       void
  2377.       erase(size_t __p, size_t __n)
  2378.       {
  2379.         _RopeRep* __result = replace(this->_M_tree_ptr, __p,
  2380.                                      __p + __n, 0);
  2381.         _S_unref(this->_M_tree_ptr);
  2382.         this->_M_tree_ptr = __result;
  2383.       }
  2384.  
  2385.       // Erase, single character
  2386.       void
  2387.       erase(size_t __p)
  2388.       { erase(__p, __p + 1); }
  2389.  
  2390.       // Insert, iterator variants.
  2391.       iterator
  2392.       insert(const iterator& __p, const rope& __r)
  2393.       {
  2394.         insert(__p.index(), __r);
  2395.         return __p;
  2396.       }
  2397.  
  2398.       iterator
  2399.       insert(const iterator& __p, size_t __n, _CharT __c)
  2400.       {
  2401.         insert(__p.index(), __n, __c);
  2402.         return __p;
  2403.       }
  2404.  
  2405.       iterator insert(const iterator& __p, _CharT __c)
  2406.       {
  2407.         insert(__p.index(), __c);
  2408.         return __p;
  2409.       }
  2410.      
  2411.       iterator
  2412.       insert(const iterator& __p )
  2413.       {
  2414.         insert(__p.index());
  2415.         return __p;
  2416.       }
  2417.      
  2418.       iterator
  2419.       insert(const iterator& __p, const _CharT* c_string)
  2420.       {
  2421.         insert(__p.index(), c_string);
  2422.         return __p;
  2423.       }
  2424.      
  2425.       iterator
  2426.       insert(const iterator& __p, const _CharT* __i, size_t __n)
  2427.       {
  2428.         insert(__p.index(), __i, __n);
  2429.         return __p;
  2430.       }
  2431.      
  2432.       iterator
  2433.       insert(const iterator& __p, const _CharT* __i,
  2434.              const _CharT* __j)
  2435.       {
  2436.         insert(__p.index(), __i, __j);
  2437.         return __p;
  2438.       }
  2439.      
  2440.       iterator
  2441.       insert(const iterator& __p,
  2442.              const const_iterator& __i, const const_iterator& __j)
  2443.       {
  2444.         insert(__p.index(), __i, __j);
  2445.         return __p;
  2446.       }
  2447.      
  2448.       iterator
  2449.       insert(const iterator& __p,
  2450.              const iterator& __i, const iterator& __j)
  2451.       {
  2452.         insert(__p.index(), __i, __j);
  2453.         return __p;
  2454.       }
  2455.  
  2456.       // Replace, range variants.
  2457.       void
  2458.       replace(const iterator& __p, const iterator& __q, const rope& __r)
  2459.       { replace(__p.index(), __q.index() - __p.index(), __r); }
  2460.  
  2461.       void
  2462.       replace(const iterator& __p, const iterator& __q, _CharT __c)
  2463.       { replace(__p.index(), __q.index() - __p.index(), __c); }
  2464.      
  2465.       void
  2466.       replace(const iterator& __p, const iterator& __q,
  2467.               const _CharT* __c_string)
  2468.       { replace(__p.index(), __q.index() - __p.index(), __c_string); }
  2469.      
  2470.       void
  2471.       replace(const iterator& __p, const iterator& __q,
  2472.               const _CharT* __i, size_t __n)
  2473.       { replace(__p.index(), __q.index() - __p.index(), __i, __n); }
  2474.      
  2475.       void
  2476.       replace(const iterator& __p, const iterator& __q,
  2477.               const _CharT* __i, const _CharT* __j)
  2478.       { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
  2479.      
  2480.       void
  2481.       replace(const iterator& __p, const iterator& __q,
  2482.               const const_iterator& __i, const const_iterator& __j)
  2483.       { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
  2484.      
  2485.       void
  2486.       replace(const iterator& __p, const iterator& __q,
  2487.               const iterator& __i, const iterator& __j)
  2488.       { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
  2489.  
  2490.       // Replace, iterator variants.
  2491.       void
  2492.       replace(const iterator& __p, const rope& __r)
  2493.       { replace(__p.index(), __r); }
  2494.      
  2495.       void
  2496.       replace(const iterator& __p, _CharT __c)
  2497.       { replace(__p.index(), __c); }
  2498.      
  2499.       void
  2500.       replace(const iterator& __p, const _CharT* __c_string)
  2501.       { replace(__p.index(), __c_string); }
  2502.      
  2503.       void
  2504.       replace(const iterator& __p, const _CharT* __i, size_t __n)
  2505.       { replace(__p.index(), __i, __n); }
  2506.      
  2507.       void
  2508.       replace(const iterator& __p, const _CharT* __i, const _CharT* __j)
  2509.       { replace(__p.index(), __i, __j); }
  2510.      
  2511.       void
  2512.       replace(const iterator& __p, const_iterator __i, const_iterator __j)
  2513.       { replace(__p.index(), __i, __j); }
  2514.      
  2515.       void
  2516.       replace(const iterator& __p, iterator __i, iterator __j)
  2517.       { replace(__p.index(), __i, __j); }
  2518.  
  2519.       // Iterator and range variants of erase
  2520.       iterator
  2521.       erase(const iterator& __p, const iterator& __q)
  2522.       {
  2523.         size_t __p_index = __p.index();
  2524.         erase(__p_index, __q.index() - __p_index);
  2525.         return iterator(this, __p_index);
  2526.       }
  2527.  
  2528.       iterator
  2529.       erase(const iterator& __p)
  2530.       {
  2531.         size_t __p_index = __p.index();
  2532.         erase(__p_index, 1);
  2533.         return iterator(this, __p_index);
  2534.       }
  2535.  
  2536.       rope
  2537.       substr(size_t __start, size_t __len = 1) const
  2538.       {
  2539.         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
  2540.                                                  __start,
  2541.                                                  __start + __len));
  2542.       }
  2543.  
  2544.       rope
  2545.       substr(iterator __start, iterator __end) const
  2546.       {
  2547.         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
  2548.                                                  __start.index(),
  2549.                                                  __end.index()));
  2550.       }
  2551.  
  2552.       rope
  2553.       substr(iterator __start) const
  2554.       {
  2555.         size_t __pos = __start.index();
  2556.         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
  2557.                                                  __pos, __pos + 1));
  2558.       }
  2559.  
  2560.       rope
  2561.       substr(const_iterator __start, const_iterator __end) const
  2562.       {
  2563.         // This might eventually take advantage of the cache in the
  2564.         // iterator.
  2565.         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
  2566.                                                  __start.index(),
  2567.                                                  __end.index()));
  2568.       }
  2569.  
  2570.       rope<_CharT, _Alloc>
  2571.       substr(const_iterator __start)
  2572.       {
  2573.         size_t __pos = __start.index();
  2574.         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
  2575.                                                  __pos, __pos + 1));
  2576.       }
  2577.  
  2578.       static const size_type npos;
  2579.  
  2580.       size_type find(_CharT __c, size_type __pos = 0) const;
  2581.  
  2582.       size_type
  2583.       find(const _CharT* __s, size_type __pos = 0) const
  2584.       {
  2585.         size_type __result_pos;
  2586.         const_iterator __result =
  2587.           std::search(const_begin() + __pos, const_end(),
  2588.                       __s, __s + _S_char_ptr_len(__s));
  2589.         __result_pos = __result.index();
  2590. #ifndef __STL_OLD_ROPE_SEMANTICS
  2591.         if (__result_pos == size())
  2592.           __result_pos = npos;
  2593. #endif
  2594.         return __result_pos;
  2595.       }
  2596.  
  2597.       iterator
  2598.       mutable_begin()
  2599.       { return(iterator(this, 0)); }
  2600.      
  2601.       iterator
  2602.       mutable_end()
  2603.       { return(iterator(this, size())); }
  2604.  
  2605.       typedef std::reverse_iterator<iterator> reverse_iterator;
  2606.      
  2607.       reverse_iterator
  2608.       mutable_rbegin()
  2609.       { return reverse_iterator(mutable_end()); }
  2610.  
  2611.       reverse_iterator
  2612.       mutable_rend()
  2613.       { return reverse_iterator(mutable_begin()); }
  2614.  
  2615.       reference
  2616.       mutable_reference_at(size_type __pos)
  2617.       { return reference(this, __pos); }
  2618.  
  2619. #ifdef __STD_STUFF
  2620.       reference
  2621.       operator[] (size_type __pos)
  2622.       { return _char_ref_proxy(this, __pos); }
  2623.  
  2624.       reference
  2625.       at(size_type __pos)
  2626.       {
  2627.         // if (__pos >= size()) throw out_of_range;  // XXX
  2628.         return (*this)[__pos];
  2629.       }
  2630.      
  2631.       void resize(size_type __n, _CharT __c) { }
  2632.       void resize(size_type __n) { }
  2633.       void reserve(size_type __res_arg = 0) { }
  2634.      
  2635.       size_type
  2636.       capacity() const
  2637.       { return max_size(); }
  2638.  
  2639.       // Stuff below this line is dangerous because it's error prone.
  2640.       // I would really like to get rid of it.
  2641.       // copy function with funny arg ordering.
  2642.       size_type
  2643.       copy(_CharT* __buffer, size_type __n,
  2644.            size_type __pos = 0) const
  2645.       { return copy(__pos, __n, __buffer); }
  2646.  
  2647.       iterator
  2648.       end()
  2649.       { return mutable_end(); }
  2650.  
  2651.       iterator
  2652.       begin()
  2653.       { return mutable_begin(); }
  2654.  
  2655.       reverse_iterator
  2656.       rend()
  2657.       { return mutable_rend(); }
  2658.      
  2659.       reverse_iterator
  2660.       rbegin()
  2661.       { return mutable_rbegin(); }
  2662.  
  2663. #else
  2664.       const_iterator
  2665.       end()
  2666.       { return const_end(); }
  2667.  
  2668.       const_iterator
  2669.       begin()
  2670.       { return const_begin(); }
  2671.  
  2672.       const_reverse_iterator
  2673.       rend()
  2674.       { return const_rend(); }
  2675.  
  2676.       const_reverse_iterator
  2677.       rbegin()
  2678.       { return const_rbegin(); }
  2679.  
  2680. #endif
  2681.     };
  2682.  
  2683.   template <class _CharT, class _Alloc>
  2684.     const typename rope<_CharT, _Alloc>::size_type
  2685.     rope<_CharT, _Alloc>::npos = (size_type)(-1);
  2686.  
  2687.   template <class _CharT, class _Alloc>
  2688.     inline bool operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x,
  2689.                            const _Rope_const_iterator<_CharT, _Alloc>& __y)
  2690.     { return (__x._M_current_pos == __y._M_current_pos
  2691.               && __x._M_root == __y._M_root); }
  2692.  
  2693.   template <class _CharT, class _Alloc>
  2694.     inline bool operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,
  2695.                           const _Rope_const_iterator<_CharT, _Alloc>& __y)
  2696.     { return (__x._M_current_pos < __y._M_current_pos); }
  2697.  
  2698.   template <class _CharT, class _Alloc>
  2699.     inline bool operator!=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
  2700.                            const _Rope_const_iterator<_CharT, _Alloc>& __y)
  2701.     { return !(__x == __y); }
  2702.  
  2703.   template <class _CharT, class _Alloc>
  2704.     inline bool operator>(const _Rope_const_iterator<_CharT, _Alloc>& __x,
  2705.                           const _Rope_const_iterator<_CharT, _Alloc>& __y)
  2706.     { return __y < __x; }
  2707.  
  2708.   template <class _CharT, class _Alloc>
  2709.     inline bool
  2710.     operator<=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
  2711.                const _Rope_const_iterator<_CharT, _Alloc>& __y)
  2712.     { return !(__y < __x); }
  2713.  
  2714.   template <class _CharT, class _Alloc>
  2715.     inline bool
  2716.     operator>=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
  2717.                const _Rope_const_iterator<_CharT, _Alloc>& __y)
  2718.     { return !(__x < __y); }
  2719.  
  2720.   template <class _CharT, class _Alloc>
  2721.     inline ptrdiff_t
  2722.     operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
  2723.               const _Rope_const_iterator<_CharT, _Alloc>& __y)
  2724.     { return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; }
  2725.  
  2726.   template <class _CharT, class _Alloc>
  2727.     inline _Rope_const_iterator<_CharT, _Alloc>
  2728.     operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
  2729.     { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
  2730.                                                   __x._M_current_pos - __n); }
  2731.  
  2732.   template <class _CharT, class _Alloc>
  2733.     inline _Rope_const_iterator<_CharT, _Alloc>
  2734.     operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
  2735.     { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
  2736.                                                   __x._M_current_pos + __n); }
  2737.  
  2738.   template <class _CharT, class _Alloc>
  2739.     inline _Rope_const_iterator<_CharT, _Alloc>
  2740.     operator+(ptrdiff_t __n, const _Rope_const_iterator<_CharT, _Alloc>& __x)
  2741.   { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
  2742.                                                 __x._M_current_pos + __n); }
  2743.  
  2744.   template <class _CharT, class _Alloc>
  2745.     inline bool
  2746.     operator==(const _Rope_iterator<_CharT, _Alloc>& __x,
  2747.                const _Rope_iterator<_CharT, _Alloc>& __y)
  2748.     {return (__x._M_current_pos == __y._M_current_pos
  2749.              && __x._M_root_rope == __y._M_root_rope); }
  2750.  
  2751.   template <class _CharT, class _Alloc>
  2752.     inline bool
  2753.     operator<(const _Rope_iterator<_CharT, _Alloc>& __x,
  2754.               const _Rope_iterator<_CharT, _Alloc>& __y)
  2755.     { return (__x._M_current_pos < __y._M_current_pos); }
  2756.  
  2757.   template <class _CharT, class _Alloc>
  2758.     inline bool
  2759.     operator!=(const _Rope_iterator<_CharT, _Alloc>& __x,
  2760.                const _Rope_iterator<_CharT, _Alloc>& __y)
  2761.     { return !(__x == __y); }
  2762.  
  2763.   template <class _CharT, class _Alloc>
  2764.     inline bool
  2765.     operator>(const _Rope_iterator<_CharT, _Alloc>& __x,
  2766.               const _Rope_iterator<_CharT, _Alloc>& __y)
  2767.     { return __y < __x; }
  2768.  
  2769.   template <class _CharT, class _Alloc>
  2770.     inline bool
  2771.     operator<=(const _Rope_iterator<_CharT, _Alloc>& __x,
  2772.                const _Rope_iterator<_CharT, _Alloc>& __y)
  2773.     { return !(__y < __x); }
  2774.  
  2775.   template <class _CharT, class _Alloc>
  2776.     inline bool
  2777.     operator>=(const _Rope_iterator<_CharT, _Alloc>& __x,
  2778.                const _Rope_iterator<_CharT, _Alloc>& __y)
  2779.     { return !(__x < __y); }
  2780.  
  2781.   template <class _CharT, class _Alloc>
  2782.     inline ptrdiff_t
  2783.     operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
  2784.               const _Rope_iterator<_CharT, _Alloc>& __y)
  2785.     { return ((ptrdiff_t)__x._M_current_pos
  2786.               - (ptrdiff_t)__y._M_current_pos); }
  2787.  
  2788.   template <class _CharT, class _Alloc>
  2789.     inline _Rope_iterator<_CharT, _Alloc>
  2790.     operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
  2791.               ptrdiff_t __n)
  2792.     { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
  2793.                                             __x._M_current_pos - __n); }
  2794.  
  2795.   template <class _CharT, class _Alloc>
  2796.     inline _Rope_iterator<_CharT, _Alloc>
  2797.     operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
  2798.     { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
  2799.                                             __x._M_current_pos + __n); }
  2800.  
  2801.   template <class _CharT, class _Alloc>
  2802.     inline _Rope_iterator<_CharT, _Alloc>
  2803.     operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x)
  2804.     { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
  2805.                                             __x._M_current_pos + __n); }
  2806.  
  2807.   template <class _CharT, class _Alloc>
  2808.     inline rope<_CharT, _Alloc>
  2809.     operator+(const rope<_CharT, _Alloc>& __left,
  2810.               const rope<_CharT, _Alloc>& __right)
  2811.     {
  2812.       // Inlining this should make it possible to keep __left and
  2813.       // __right in registers.
  2814.       typedef rope<_CharT, _Alloc> rope_type;
  2815.       return rope_type(rope_type::_S_concat(__left._M_tree_ptr,
  2816.                                             __right._M_tree_ptr));
  2817.     }
  2818.  
  2819.   template <class _CharT, class _Alloc>
  2820.     inline rope<_CharT, _Alloc>&
  2821.     operator+=(rope<_CharT, _Alloc>& __left,
  2822.                const rope<_CharT, _Alloc>& __right)
  2823.     {
  2824.       __left.append(__right);
  2825.       return __left;
  2826.     }
  2827.  
  2828.   template <class _CharT, class _Alloc>
  2829.     inline rope<_CharT, _Alloc>
  2830.     operator+(const rope<_CharT, _Alloc>& __left,
  2831.               const _CharT* __right)
  2832.     {
  2833.       typedef rope<_CharT, _Alloc> rope_type;
  2834.       size_t __rlen = rope_type::_S_char_ptr_len(__right);
  2835.       return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
  2836.                                                       __right, __rlen));
  2837.     }
  2838.  
  2839.   template <class _CharT, class _Alloc>
  2840.     inline rope<_CharT, _Alloc>&
  2841.     operator+=(rope<_CharT, _Alloc>& __left,
  2842.                const _CharT* __right)
  2843.     {
  2844.       __left.append(__right);
  2845.       return __left;
  2846.     }
  2847.  
  2848.   template <class _CharT, class _Alloc>
  2849.     inline rope<_CharT, _Alloc>
  2850.     operator+(const rope<_CharT, _Alloc>& __left, _CharT __right)
  2851.     {
  2852.       typedef rope<_CharT, _Alloc> rope_type;
  2853.       return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
  2854.                                                       &__right, 1));
  2855.     }
  2856.  
  2857.   template <class _CharT, class _Alloc>
  2858.     inline rope<_CharT, _Alloc>&
  2859.     operator+=(rope<_CharT, _Alloc>& __left, _CharT __right)
  2860.     {
  2861.       __left.append(__right);
  2862.       return __left;
  2863.     }
  2864.  
  2865.   template <class _CharT, class _Alloc>
  2866.     bool
  2867.     operator<(const rope<_CharT, _Alloc>& __left,
  2868.               const rope<_CharT, _Alloc>& __right)
  2869.     { return __left.compare(__right) < 0; }
  2870.  
  2871.   template <class _CharT, class _Alloc>
  2872.     bool
  2873.     operator==(const rope<_CharT, _Alloc>& __left,
  2874.                const rope<_CharT, _Alloc>& __right)
  2875.     { return __left.compare(__right) == 0; }
  2876.  
  2877.   template <class _CharT, class _Alloc>
  2878.     inline bool
  2879.     operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
  2880.                const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
  2881.     { return (__x._M_pos == __y._M_pos && __x._M_root == __y._M_root); }
  2882.  
  2883.   template <class _CharT, class _Alloc>
  2884.     inline bool
  2885.     operator!=(const rope<_CharT, _Alloc>& __x,
  2886.                const rope<_CharT, _Alloc>& __y)
  2887.     { return !(__x == __y); }
  2888.  
  2889.   template <class _CharT, class _Alloc>
  2890.     inline bool
  2891.     operator>(const rope<_CharT, _Alloc>& __x,
  2892.               const rope<_CharT, _Alloc>& __y)
  2893.     { return __y < __x; }
  2894.  
  2895.   template <class _CharT, class _Alloc>
  2896.     inline bool
  2897.     operator<=(const rope<_CharT, _Alloc>& __x,
  2898.                const rope<_CharT, _Alloc>& __y)
  2899.     { return !(__y < __x); }
  2900.  
  2901.   template <class _CharT, class _Alloc>
  2902.     inline bool
  2903.     operator>=(const rope<_CharT, _Alloc>& __x,
  2904.                const rope<_CharT, _Alloc>& __y)
  2905.     { return !(__x < __y); }
  2906.  
  2907.   template <class _CharT, class _Alloc>
  2908.     inline bool
  2909.     operator!=(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
  2910.                const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
  2911.     { return !(__x == __y); }
  2912.  
  2913.   template<class _CharT, class _Traits, class _Alloc>
  2914.     std::basic_ostream<_CharT, _Traits>&
  2915.     operator<<(std::basic_ostream<_CharT, _Traits>& __o,
  2916.                const rope<_CharT, _Alloc>& __r);
  2917.  
  2918.   typedef rope<char> crope;
  2919.   typedef rope<wchar_t> wrope;
  2920.  
  2921.   inline crope::reference
  2922.   __mutable_reference_at(crope& __c, size_t __i)
  2923.   { return __c.mutable_reference_at(__i); }
  2924.  
  2925.   inline wrope::reference
  2926.   __mutable_reference_at(wrope& __c, size_t __i)
  2927.   { return __c.mutable_reference_at(__i); }
  2928.  
  2929.   template <class _CharT, class _Alloc>
  2930.     inline void
  2931.     swap(rope<_CharT, _Alloc>& __x, rope<_CharT, _Alloc>& __y)
  2932.     { __x.swap(__y); }
  2933.  
  2934. _GLIBCXX_END_NAMESPACE_VERSION
  2935. } // namespace
  2936.  
  2937.  
  2938. namespace std _GLIBCXX_VISIBILITY(default)
  2939. {
  2940. namespace tr1
  2941. {
  2942. _GLIBCXX_BEGIN_NAMESPACE_VERSION
  2943.  
  2944.   template<>
  2945.     struct hash<__gnu_cxx::crope>
  2946.     {
  2947.       size_t
  2948.       operator()(const __gnu_cxx::crope& __str) const
  2949.       {
  2950.         size_t __size = __str.size();
  2951.         if (0 == __size)
  2952.           return 0;
  2953.         return 13 * __str[0] + 5 * __str[__size - 1] + __size;
  2954.       }
  2955.     };
  2956.  
  2957.  
  2958.   template<>
  2959.     struct hash<__gnu_cxx::wrope>
  2960.     {
  2961.       size_t
  2962.       operator()(const __gnu_cxx::wrope& __str) const
  2963.       {
  2964.         size_t __size = __str.size();
  2965.         if (0 == __size)
  2966.           return 0;
  2967.         return 13 * __str[0] + 5 * __str[__size - 1] + __size;
  2968.       }
  2969.     };
  2970.  
  2971. _GLIBCXX_END_NAMESPACE_VERSION
  2972. } // namespace tr1
  2973. } // namespace std
  2974.  
  2975. # include <ext/ropeimpl.h>
  2976.  
  2977. #endif
  2978.