Subversion Repositories Kolibri OS

// SGI's rope class -*- C++ -*-

// Copyright (C) 2001-2015 Free Software Foundation, Inc.

//

// This file is part of the GNU ISO C++ Library.  This library is free

// software; you can redistribute it and/or modify it under the

// terms of the GNU General Public License as published by the

// Free Software Foundation; either version 3, or (at your option)

// any later version.

// This library is distributed in the hope that it will be useful,

// but WITHOUT ANY WARRANTY; without even the implied warranty of

// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional

// permissions described in the GCC Runtime Library Exception, version

// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and

// a copy of the GCC Runtime Library Exception along with this program;

// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see

// .

/*

 * Copyright (c) 1997

 * Silicon Graphics Computer Systems, Inc.

 *

 * Permission to use, copy, modify, distribute and sell this software

 * and its documentation for any purpose is hereby granted without fee,

 * provided that the above copyright notice appear in all copies and

 * that both that copyright notice and this permission notice appear

 * in supporting documentation.  Silicon Graphics makes no

 * representations about the suitability of this software for any

 * purpose.  It is provided "as is" without express or implied warranty.

 */

/** @file ext/rope

 *  This file is a GNU extension to the Standard C++ Library (possibly

 *  containing extensions from the HP/SGI STL subset).

 */

#ifndef _ROPE

#define _ROPE 1

#pragma GCC system_header

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

#include 

# ifdef __GC

#   define __GC_CONST const

# else

#   define __GC_CONST   // constant except for deallocation

# endif

#include  // For uninitialized_copy_n

namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)

{

  namespace __detail

  {

    enum { _S_max_rope_depth = 45 };

    enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function};

  } // namespace __detail

  using std::size_t;

  using std::ptrdiff_t;

  using std::allocator;

  using std::_Destroy;

_GLIBCXX_BEGIN_NAMESPACE_VERSION

  // See libstdc++/36832.

  template

    void

    _Destroy_const(_ForwardIterator __first,

		   _ForwardIterator __last, _Allocator __alloc)

    {

      for (; __first != __last; ++__first)

	__alloc.destroy(&*__first);

    }

  template

    inline void

    _Destroy_const(_ForwardIterator __first,

		   _ForwardIterator __last, allocator<_Tp>)

    { _Destroy(__first, __last); }

  // The _S_eos function is used for those functions that

  // convert to/from C-like strings to detect the end of the string.

  // The end-of-C-string character.

  // This is what the draft standard says it should be.

  template 

    inline _CharT

    _S_eos(_CharT*)

    { return _CharT(); }

  // Test for basic character types.

  // For basic character types leaves having a trailing eos.

  template 

    inline bool

    _S_is_basic_char_type(_CharT*)

    { return false; }

  template 

    inline bool

    _S_is_one_byte_char_type(_CharT*)

    { return false; }

  inline bool

  _S_is_basic_char_type(char*)

  { return true; }

  inline bool

  _S_is_one_byte_char_type(char*)

  { return true; }

  inline bool

  _S_is_basic_char_type(wchar_t*)

  { return true; }

  // Store an eos iff _CharT is a basic character type.

  // Do not reference _S_eos if it isn't.

  template 

    inline void

    _S_cond_store_eos(_CharT&) { }

  inline void

  _S_cond_store_eos(char& __c)

  { __c = 0; }

  inline void

  _S_cond_store_eos(wchar_t& __c)

  { __c = 0; }

  // char_producers are logically functions that generate a section of

  // a string.  These can be converted to ropes.  The resulting rope

  // invokes the char_producer on demand.  This allows, for example,

  // files to be viewed as ropes without reading the entire file.

  template 

    class char_producer

    {

    public:

      virtual ~char_producer() { };

      virtual void

      operator()(size_t __start_pos, size_t __len,

		 _CharT* __buffer) = 0;

      // Buffer should really be an arbitrary output iterator.

      // That way we could flatten directly into an ostream, etc.

      // This is thoroughly impossible, since iterator types don't

      // have runtime descriptions.

    };

  // Sequence buffers:

  //

  // Sequence must provide an append operation that appends an

  // array to the sequence.  Sequence buffers are useful only if

  // appending an entire array is cheaper than appending element by element.

  // This is true for many string representations.

  // This should  perhaps inherit from ostream

  // and be implemented correspondingly, so that they can be used

  // for formatted.  For the sake of portability, we don't do this yet.

  //

  // For now, sequence buffers behave as output iterators.  But they also

  // behave a little like basic_ostringstream and a

  // little like containers.

  template

    class sequence_buffer

    : public std::iterator

    {

    public:

      typedef typename _Sequence::value_type value_type;

    protected:

      _Sequence* _M_prefix;

      value_type _M_buffer[_Buf_sz];

      size_t     _M_buf_count;

    public:

      void

      flush()

      {

	_M_prefix->append(_M_buffer, _M_buffer + _M_buf_count);

	_M_buf_count = 0;

      }

      ~sequence_buffer()

      { flush(); }

      sequence_buffer()

      : _M_prefix(0), _M_buf_count(0) { }

      sequence_buffer(const sequence_buffer& __x)

      {

	_M_prefix = __x._M_prefix;

	_M_buf_count = __x._M_buf_count;

	std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);

      }

      sequence_buffer(sequence_buffer& __x)

      {

	__x.flush();

	_M_prefix = __x._M_prefix;

	_M_buf_count = 0;

      }

      sequence_buffer(_Sequence& __s)

      : _M_prefix(&__s), _M_buf_count(0) { }

      sequence_buffer&

      operator=(sequence_buffer& __x)

      {

	__x.flush();

	_M_prefix = __x._M_prefix;

	_M_buf_count = 0;

	return *this;

      }

      sequence_buffer&

      operator=(const sequence_buffer& __x)

      {

	_M_prefix = __x._M_prefix;

	_M_buf_count = __x._M_buf_count;

	std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);

	return *this;

      }

      void

      push_back(value_type __x)

      {

	if (_M_buf_count < _Buf_sz)

	  {

	    _M_buffer[_M_buf_count] = __x;

	    ++_M_buf_count;

	  }

	else

	  {

	    flush();

	    _M_buffer[0] = __x;

	    _M_buf_count = 1;

	  }

      }

      void

      append(value_type* __s, size_t __len)

      {

	if (__len + _M_buf_count <= _Buf_sz)

	  {

	    size_t __i = _M_buf_count;

	    for (size_t __j = 0; __j < __len; __i++, __j++)

	      _M_buffer[__i] = __s[__j];

	    _M_buf_count += __len;

	  }

	else if (0 == _M_buf_count)

	  _M_prefix->append(__s, __s + __len);

	else

	  {

	    flush();

	    append(__s, __len);

	  }

      }

      sequence_buffer&

      write(value_type* __s, size_t __len)

      {

	append(__s, __len);

	return *this;

      }

      sequence_buffer&

      put(value_type __x)

      {

	push_back(__x);

	return *this;

      }

      sequence_buffer&

      operator=(const value_type& __rhs)

      {

	push_back(__rhs);

	return *this;

      }

      sequence_buffer&

      operator*()

      { return *this; }

      sequence_buffer&

      operator++()

      { return *this; }

      sequence_buffer

      operator++(int)

      { return *this; }

    };

  // The following should be treated as private, at least for now.

  template

    class _Rope_char_consumer

    {

    public:

      // If we had member templates, these should not be virtual.

      // For now we need to use run-time parametrization where

      // compile-time would do.  Hence this should all be private

      // for now.

      // The symmetry with char_producer is accidental and temporary.

      virtual ~_Rope_char_consumer() { };

      virtual bool

      operator()(const _CharT* __buffer, size_t __len) = 0;

    };

  // First a lot of forward declarations.  The standard seems to require

  // much stricter "declaration before use" than many of the implementations

  // that preceded it.

  template >

    class rope;

  template

    struct _Rope_RopeConcatenation;

  template

    struct _Rope_RopeLeaf;

  template

    struct _Rope_RopeFunction;

  template

    struct _Rope_RopeSubstring;

  template

    class _Rope_iterator;

  template

    class _Rope_const_iterator;

  template

    class _Rope_char_ref_proxy;

  template

    class _Rope_char_ptr_proxy;

  template

    bool

    operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,

	       const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y);

  template

    _Rope_const_iterator<_CharT, _Alloc>

    operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,

	      ptrdiff_t __n);

  template

    _Rope_const_iterator<_CharT, _Alloc>

    operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x,

	      ptrdiff_t __n);

  template

    _Rope_const_iterator<_CharT, _Alloc>

    operator+(ptrdiff_t __n,

	      const _Rope_const_iterator<_CharT, _Alloc>& __x);

  template

    bool

    operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x,

	       const _Rope_const_iterator<_CharT, _Alloc>& __y);

  template

    bool

    operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,

	      const _Rope_const_iterator<_CharT, _Alloc>& __y);

  template

    ptrdiff_t

    operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,

	      const _Rope_const_iterator<_CharT, _Alloc>& __y);

  template

    _Rope_iterator<_CharT, _Alloc>

    operator-(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);

  template

    _Rope_iterator<_CharT, _Alloc>

    operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);

  template

    _Rope_iterator<_CharT, _Alloc>

    operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x);

  template

    bool

    operator==(const _Rope_iterator<_CharT, _Alloc>& __x,

	       const _Rope_iterator<_CharT, _Alloc>& __y);

  template

    bool

    operator<(const _Rope_iterator<_CharT, _Alloc>& __x,

	      const _Rope_iterator<_CharT, _Alloc>& __y);

  template

    ptrdiff_t

    operator-(const _Rope_iterator<_CharT, _Alloc>& __x,

	      const _Rope_iterator<_CharT, _Alloc>& __y);

  template

    rope<_CharT, _Alloc>

    operator+(const rope<_CharT, _Alloc>& __left,

	      const rope<_CharT, _Alloc>& __right);

  template

    rope<_CharT, _Alloc>

    operator+(const rope<_CharT, _Alloc>& __left, const _CharT* __right);

  template

    rope<_CharT, _Alloc>

    operator+(const rope<_CharT, _Alloc>& __left, _CharT __right);

  // Some helpers, so we can use power on ropes.

  // See below for why this isn't local to the implementation.

  // This uses a nonstandard refcount convention.

  // The result has refcount 0.

  template

    struct _Rope_Concat_fn

    : public std::binary_function, rope<_CharT, _Alloc>,

				  rope<_CharT, _Alloc> >

    {

      rope<_CharT, _Alloc>

      operator()(const rope<_CharT, _Alloc>& __x,

		 const rope<_CharT, _Alloc>& __y)

      { return __x + __y; }

    };

  template 

    inline rope<_CharT, _Alloc>

    identity_element(_Rope_Concat_fn<_CharT, _Alloc>)

    { return rope<_CharT, _Alloc>(); }

  // Class _Refcount_Base provides a type, _RC_t, a data member,

  // _M_ref_count, and member functions _M_incr and _M_decr, which perform

  // atomic preincrement/predecrement.  The constructor initializes

  // _M_ref_count.

  struct _Refcount_Base

  {

    // The type _RC_t

    typedef size_t _RC_t;

    // The data member _M_ref_count

    volatile _RC_t _M_ref_count;

    // Constructor

#ifdef __GTHREAD_MUTEX_INIT

    __gthread_mutex_t _M_ref_count_lock = __GTHREAD_MUTEX_INIT;

#else

    __gthread_mutex_t _M_ref_count_lock;

#endif

    _Refcount_Base(_RC_t __n) : _M_ref_count(__n)

    {

#ifndef __GTHREAD_MUTEX_INIT

#ifdef __GTHREAD_MUTEX_INIT_FUNCTION

      __GTHREAD_MUTEX_INIT_FUNCTION (&_M_ref_count_lock);

#else

#error __GTHREAD_MUTEX_INIT or __GTHREAD_MUTEX_INIT_FUNCTION should be defined by gthr.h abstraction layer, report problem to libstdc++@gcc.gnu.org.

#endif

#endif

    }

#ifndef __GTHREAD_MUTEX_INIT

    ~_Refcount_Base()

    { __gthread_mutex_destroy(&_M_ref_count_lock); }

#endif

    void

    _M_incr()

    {

      __gthread_mutex_lock(&_M_ref_count_lock);

      ++_M_ref_count;

      __gthread_mutex_unlock(&_M_ref_count_lock);

    }

    _RC_t

    _M_decr()

    {

      __gthread_mutex_lock(&_M_ref_count_lock);

      volatile _RC_t __tmp = --_M_ref_count;

      __gthread_mutex_unlock(&_M_ref_count_lock);

      return __tmp;

    }

  };

  //

  // What follows should really be local to rope.  Unfortunately,

  // that doesn't work, since it makes it impossible to define generic

  // equality on rope iterators.  According to the draft standard, the

  // template parameters for such an equality operator cannot be inferred

  // from the occurrence of a member class as a parameter.

  // (SGI compilers in fact allow this, but the __result wouldn't be

  // portable.)

  // Similarly, some of the static member functions are member functions

  // only to avoid polluting the global namespace, and to circumvent

  // restrictions on type inference for template functions.

  //

  //

  // The internal data structure for representing a rope.  This is

  // private to the implementation.  A rope is really just a pointer

  // to one of these.

  //

  // A few basic functions for manipulating this data structure

  // are members of _RopeRep.  Most of the more complex algorithms

  // are implemented as rope members.

  //

  // Some of the static member functions of _RopeRep have identically

  // named functions in rope that simply invoke the _RopeRep versions.

#define __ROPE_DEFINE_ALLOCS(__a) \

        __ROPE_DEFINE_ALLOC(_CharT,_Data) /* character data */ \

        typedef _Rope_RopeConcatenation<_CharT,__a> __C; \

        __ROPE_DEFINE_ALLOC(__C,_C) \

        typedef _Rope_RopeLeaf<_CharT,__a> __L; \

        __ROPE_DEFINE_ALLOC(__L,_L) \

        typedef _Rope_RopeFunction<_CharT,__a> __F; \

        __ROPE_DEFINE_ALLOC(__F,_F) \

        typedef _Rope_RopeSubstring<_CharT,__a> __S; \

        __ROPE_DEFINE_ALLOC(__S,_S)

  //  Internal rope nodes potentially store a copy of the allocator

  //  instance used to allocate them.  This is mostly redundant.

  //  But the alternative would be to pass allocator instances around

  //  in some form to nearly all internal functions, since any pointer

  //  assignment may result in a zero reference count and thus require

  //  deallocation.

#define __STATIC_IF_SGI_ALLOC  /* not static */

  template 

    struct _Rope_rep_base

    : public _Alloc

    {

      typedef _Alloc allocator_type;

      allocator_type

      get_allocator() const

      { return *static_cast(this); }

      allocator_type&

      _M_get_allocator()

      { return *static_cast<_Alloc*>(this); }

      const allocator_type&

      _M_get_allocator() const

      { return *static_cast(this); }

      _Rope_rep_base(size_t __size, const allocator_type&)

      : _M_size(__size) { }

      size_t _M_size;

# define __ROPE_DEFINE_ALLOC(_Tp, __name) \

        typedef typename \

          _Alloc::template rebind<_Tp>::other __name##Alloc; \

        static _Tp* __name##_allocate(size_t __n) \

          { return __name##Alloc().allocate(__n); } \

        static void __name##_deallocate(_Tp *__p, size_t __n) \

          { __name##Alloc().deallocate(__p, __n); }

      __ROPE_DEFINE_ALLOCS(_Alloc)

# undef __ROPE_DEFINE_ALLOC

    };

  template

    struct _Rope_RopeRep

    : public _Rope_rep_base<_CharT, _Alloc>

# ifndef __GC

	     , _Refcount_Base

# endif

    {

    public:

      __detail::_Tag _M_tag:8;

      bool _M_is_balanced:8;

      unsigned char _M_depth;

      __GC_CONST _CharT* _M_c_string;

#ifdef __GTHREAD_MUTEX_INIT

      __gthread_mutex_t _M_c_string_lock = __GTHREAD_MUTEX_INIT;

#else

      __gthread_mutex_t _M_c_string_lock;

#endif

                        /* Flattened version of string, if needed.  */

                        /* typically 0.                             */

                        /* If it's not 0, then the memory is owned  */

                        /* by this node.                            */

                        /* In the case of a leaf, this may point to */

                        /* the same memory as the data field.       */

      typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type

        allocator_type;

      using _Rope_rep_base<_CharT, _Alloc>::get_allocator;

      using _Rope_rep_base<_CharT, _Alloc>::_M_get_allocator;

      _Rope_RopeRep(__detail::_Tag __t, int __d, bool __b, size_t __size,

		    const allocator_type& __a)

      : _Rope_rep_base<_CharT, _Alloc>(__size, __a),

#ifndef __GC

	_Refcount_Base(1),

#endif

	_M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0)

#ifdef __GTHREAD_MUTEX_INIT

      { }

#else

      { __GTHREAD_MUTEX_INIT_FUNCTION (&_M_c_string_lock); }

      ~_Rope_RopeRep()

      { __gthread_mutex_destroy (&_M_c_string_lock); }

#endif

#ifdef __GC

      void

      _M_incr () { }

#endif

      static void

      _S_free_string(__GC_CONST _CharT*, size_t __len,

		     allocator_type& __a);

#define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a);

                        // Deallocate data section of a leaf.

                        // This shouldn't be a member function.

                        // But its hard to do anything else at the

                        // moment, because it's templatized w.r.t.

                        // an allocator.

                        // Does nothing if __GC is defined.

#ifndef __GC

      void _M_free_c_string();

      void _M_free_tree();

      // Deallocate t. Assumes t is not 0.

      void

      _M_unref_nonnil()

      {

	if (0 == _M_decr())

	  _M_free_tree();

      }

      void

      _M_ref_nonnil()

      { _M_incr(); }

      static void

      _S_unref(_Rope_RopeRep* __t)

      {

	if (0 != __t)

	  __t->_M_unref_nonnil();

      }

      static void

      _S_ref(_Rope_RopeRep* __t)

      {

	if (0 != __t)

	  __t->_M_incr();

      }

      static void

      _S_free_if_unref(_Rope_RopeRep* __t)

      {

	if (0 != __t && 0 == __t->_M_ref_count)

	  __t->_M_free_tree();

      }

#   else /* __GC */

      void _M_unref_nonnil() { }

      void _M_ref_nonnil() { }

      static void _S_unref(_Rope_RopeRep*) { }

      static void _S_ref(_Rope_RopeRep*) { }

      static void _S_free_if_unref(_Rope_RopeRep*) { }

#   endif

protected:

      _Rope_RopeRep&

      operator=(const _Rope_RopeRep&);

      _Rope_RopeRep(const _Rope_RopeRep&);

    };

  template

    struct _Rope_RopeLeaf

    : public _Rope_RopeRep<_CharT, _Alloc>

    {

    public:

      // Apparently needed by VC++

      // The data fields of leaves are allocated with some

      // extra space, to accommodate future growth and for basic

      // character types, to hold a trailing eos character.

      enum { _S_alloc_granularity = 8 };

      static size_t

      _S_rounded_up_size(size_t __n)

      {

        size_t __size_with_eos;

        if (_S_is_basic_char_type((_CharT*)0))

	  __size_with_eos = __n + 1;

	else

	  __size_with_eos = __n;

#ifdef __GC

	return __size_with_eos;

#else

	// Allow slop for in-place expansion.

	return ((__size_with_eos + size_t(_S_alloc_granularity) - 1)

		&~ (size_t(_S_alloc_granularity) - 1));

#endif

      }

      __GC_CONST _CharT* _M_data; /* Not necessarily 0 terminated. */

                                  /* The allocated size is         */

                                  /* _S_rounded_up_size(size), except */

                                  /* in the GC case, in which it   */

                                  /* doesn't matter.               */

      typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type

        allocator_type;

      _Rope_RopeLeaf(__GC_CONST _CharT* __d, size_t __size,

		     const allocator_type& __a)

      : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_leaf, 0, true,

				      __size, __a), _M_data(__d)

      {

        if (_S_is_basic_char_type((_CharT *)0))

	  {

            // already eos terminated.

            this->_M_c_string = __d;

	  }

      }

      // The constructor assumes that d has been allocated with

      // the proper allocator and the properly padded size.

      // In contrast, the destructor deallocates the data:

#ifndef __GC

      ~_Rope_RopeLeaf() throw()

      {

        if (_M_data != this->_M_c_string)

	  this->_M_free_c_string();

	this->__STL_FREE_STRING(_M_data, this->_M_size, this->_M_get_allocator());

      }

#endif

protected:

      _Rope_RopeLeaf&

      operator=(const _Rope_RopeLeaf&);

      _Rope_RopeLeaf(const _Rope_RopeLeaf&);

    };

  template

    struct _Rope_RopeConcatenation

    : public _Rope_RopeRep<_CharT, _Alloc>

    {

    public:

      _Rope_RopeRep<_CharT, _Alloc>* _M_left;

      _Rope_RopeRep<_CharT, _Alloc>* _M_right;

      typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type

        allocator_type;

      _Rope_RopeConcatenation(_Rope_RopeRep<_CharT, _Alloc>* __l,

			      _Rope_RopeRep<_CharT, _Alloc>* __r,

			      const allocator_type& __a)

	: _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_concat,

				      std::max(__l->_M_depth,

					       __r->_M_depth) + 1,

				      false,

				      __l->_M_size + __r->_M_size, __a),

        _M_left(__l), _M_right(__r)

      { }

#ifndef __GC

      ~_Rope_RopeConcatenation() throw()

      {

	this->_M_free_c_string();

	_M_left->_M_unref_nonnil();

	_M_right->_M_unref_nonnil();

      }

#endif

protected:

      _Rope_RopeConcatenation&

      operator=(const _Rope_RopeConcatenation&);

      _Rope_RopeConcatenation(const _Rope_RopeConcatenation&);

    };

  template

    struct _Rope_RopeFunction

    : public _Rope_RopeRep<_CharT, _Alloc>

    {

    public:

      char_producer<_CharT>* _M_fn;

#ifndef __GC

      bool _M_delete_when_done; // Char_producer is owned by the

                                // rope and should be explicitly

                                // deleted when the rope becomes

                                // inaccessible.

#else

      // In the GC case, we either register the rope for

      // finalization, or not.  Thus the field is unnecessary;

      // the information is stored in the collector data structures.

      // We do need a finalization procedure to be invoked by the

      // collector.

      static void

      _S_fn_finalization_proc(void * __tree, void *)

      { delete ((_Rope_RopeFunction *)__tree) -> _M_fn; }

#endif

    typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type

      allocator_type;

      _Rope_RopeFunction(char_producer<_CharT>* __f, size_t __size,

                        bool __d, const allocator_type& __a)

      : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_function, 0, true, __size, __a)

	, _M_fn(__f)

#ifndef __GC

	, _M_delete_when_done(__d)

#endif

      {

#ifdef __GC

	if (__d)

	  {

	    GC_REGISTER_FINALIZER(this, _Rope_RopeFunction::

				  _S_fn_finalization_proc, 0, 0, 0);

	  }

#endif

      }

#ifndef __GC

      ~_Rope_RopeFunction() throw()

      {

	this->_M_free_c_string();

	if (_M_delete_when_done)

	  delete _M_fn;

      }

# endif

    protected:

      _Rope_RopeFunction&

      operator=(const _Rope_RopeFunction&);

      _Rope_RopeFunction(const _Rope_RopeFunction&);

    };

  // Substring results are usually represented using just

  // concatenation nodes.  But in the case of very long flat ropes

  // or ropes with a functional representation that isn't practical.

  // In that case, we represent the __result as a special case of

  // RopeFunction, whose char_producer points back to the rope itself.

  // In all cases except repeated substring operations and

  // deallocation, we treat the __result as a RopeFunction.

  template

    struct _Rope_RopeSubstring

    : public _Rope_RopeFunction<_CharT, _Alloc>,

      public char_producer<_CharT>

    {

    public:

      // XXX this whole class should be rewritten.

      _Rope_RopeRep<_CharT,_Alloc>* _M_base;      // not 0

      size_t _M_start;

      virtual void

      operator()(size_t __start_pos, size_t __req_len,

		 _CharT* __buffer)

      {

        switch(_M_base->_M_tag)

	  {

	  case __detail::_S_function:

	  case __detail::_S_substringfn:

	    {

	      char_producer<_CharT>* __fn =

		((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn;

	      (*__fn)(__start_pos + _M_start, __req_len, __buffer);

	    }

	    break;

	  case __detail::_S_leaf:

	    {

	      __GC_CONST _CharT* __s =

		((_Rope_RopeLeaf<_CharT,_Alloc>*)_M_base)->_M_data;

	      uninitialized_copy_n(__s + __start_pos + _M_start, __req_len,

				   __buffer);

	    }

	    break;

	  default:

	    break;

	  }

      }

      typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type

        allocator_type;

      _Rope_RopeSubstring(_Rope_RopeRep<_CharT, _Alloc>* __b, size_t __s,

                          size_t __l, const allocator_type& __a)

      : _Rope_RopeFunction<_CharT, _Alloc>(this, __l, false, __a),

        char_producer<_CharT>(), _M_base(__b), _M_start(__s)

      {

#ifndef __GC

	_M_base->_M_ref_nonnil();

#endif

        this->_M_tag = __detail::_S_substringfn;

      }

    virtual ~_Rope_RopeSubstring() throw()

      {

#ifndef __GC

	_M_base->_M_unref_nonnil();

	// _M_free_c_string();  -- done by parent class

#endif

      }

    };

  // Self-destructing pointers to Rope_rep.

  // These are not conventional smart pointers.  Their

  // only purpose in life is to ensure that unref is called

  // on the pointer either at normal exit or if an exception

  // is raised.  It is the caller's responsibility to

  // adjust reference counts when these pointers are initialized

  // or assigned to.  (This convention significantly reduces

  // the number of potentially expensive reference count

  // updates.)

#ifndef __GC

  template

    struct _Rope_self_destruct_ptr

    {

      _Rope_RopeRep<_CharT, _Alloc>* _M_ptr;

      ~_Rope_self_destruct_ptr()

      { _Rope_RopeRep<_CharT, _Alloc>::_S_unref(_M_ptr); }

#if __cpp_exceptions

      _Rope_self_destruct_ptr() : _M_ptr(0) { };

#else

      _Rope_self_destruct_ptr() { };

#endif

      _Rope_self_destruct_ptr(_Rope_RopeRep<_CharT, _Alloc>* __p)

      : _M_ptr(__p) { }

      _Rope_RopeRep<_CharT, _Alloc>&

      operator*()

      { return *_M_ptr; }

      _Rope_RopeRep<_CharT, _Alloc>*

      operator->()

      { return _M_ptr; }

      operator _Rope_RopeRep<_CharT, _Alloc>*()

      { return _M_ptr; }

      _Rope_self_destruct_ptr&

      operator=(_Rope_RopeRep<_CharT, _Alloc>* __x)

      { _M_ptr = __x; return *this; }

    };

#endif

  // Dereferencing a nonconst iterator has to return something

  // that behaves almost like a reference.  It's not possible to

  // return an actual reference since assignment requires extra

  // work.  And we would get into the same problems as with the

  // CD2 version of basic_string.

  template

    class _Rope_char_ref_proxy

    {

      friend class rope<_CharT, _Alloc>;

      friend class _Rope_iterator<_CharT, _Alloc>;

      friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;

#ifdef __GC

      typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;

#else

      typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;

#endif

      typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;

      typedef rope<_CharT, _Alloc> _My_rope;

      size_t _M_pos;

      _CharT _M_current;

      bool _M_current_valid;

      _My_rope* _M_root;     // The whole rope.

    public:

      _Rope_char_ref_proxy(_My_rope* __r, size_t __p)

      :  _M_pos(__p), _M_current(), _M_current_valid(false), _M_root(__r) { }

      _Rope_char_ref_proxy(const _Rope_char_ref_proxy& __x)

      : _M_pos(__x._M_pos), _M_current(__x._M_current),

	_M_current_valid(false), _M_root(__x._M_root) { }

      // Don't preserve cache if the reference can outlive the

      // expression.  We claim that's not possible without calling

      // a copy constructor or generating reference to a proxy

      // reference.  We declare the latter to have undefined semantics.

      _Rope_char_ref_proxy(_My_rope* __r, size_t __p, _CharT __c)

      : _M_pos(__p), _M_current(__c), _M_current_valid(true), _M_root(__r) { }

      inline operator _CharT () const;

      _Rope_char_ref_proxy&

      operator=(_CharT __c);

      _Rope_char_ptr_proxy<_CharT, _Alloc> operator&() const;

      _Rope_char_ref_proxy&

      operator=(const _Rope_char_ref_proxy& __c)

      { return operator=((_CharT)__c); }

    };

  template

    inline void

    swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a,

	 _Rope_char_ref_proxy <_CharT, __Alloc > __b)

    {

      _CharT __tmp = __a;

      __a = __b;

      __b = __tmp;

    }

  template

    class _Rope_char_ptr_proxy

    {

      // XXX this class should be rewritten.

      friend class _Rope_char_ref_proxy<_CharT, _Alloc>;

      size_t _M_pos;

      rope<_CharT,_Alloc>* _M_root;     // The whole rope.

    public:

      _Rope_char_ptr_proxy(const _Rope_char_ref_proxy<_CharT,_Alloc>& __x)

      : _M_pos(__x._M_pos), _M_root(__x._M_root) { }

      _Rope_char_ptr_proxy(const _Rope_char_ptr_proxy& __x)

      : _M_pos(__x._M_pos), _M_root(__x._M_root) { }

      _Rope_char_ptr_proxy() { }

      _Rope_char_ptr_proxy(_CharT* __x)

      : _M_root(0), _M_pos(0) { }

      _Rope_char_ptr_proxy&

      operator=(const _Rope_char_ptr_proxy& __x)

      {

        _M_pos = __x._M_pos;

        _M_root = __x._M_root;

        return *this;

      }

      template

        friend bool

        operator==(const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __x,

		   const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __y);

      _Rope_char_ref_proxy<_CharT, _Alloc> operator*() const

      { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root, _M_pos); }

    };

  // Rope iterators:

  // Unlike in the C version, we cache only part of the stack

  // for rope iterators, since they must be efficiently copyable.

  // When we run out of cache, we have to reconstruct the iterator

  // value.

  // Pointers from iterators are not included in reference counts.

  // Iterators are assumed to be thread private.  Ropes can

  // be shared.

  template

    class _Rope_iterator_base

    : public std::iterator

    {

      friend class rope<_CharT, _Alloc>;

    public:

      typedef _Alloc _allocator_type; // used in _Rope_rotate, VC++ workaround

      typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;

      // Borland doesn't want this to be protected.

    protected:

      enum { _S_path_cache_len = 4 }; // Must be <= 9.

      enum { _S_iterator_buf_len = 15 };

      size_t _M_current_pos;

      _RopeRep* _M_root;     // The whole rope.

      size_t _M_leaf_pos;    // Starting position for current leaf

      __GC_CONST _CharT* _M_buf_start;

                             // Buffer possibly

                             // containing current char.

      __GC_CONST _CharT* _M_buf_ptr;

                             // Pointer to current char in buffer.

                             // != 0 ==> buffer valid.

      __GC_CONST _CharT* _M_buf_end;

                             // One past __last valid char in buffer.

      // What follows is the path cache.  We go out of our

      // way to make this compact.

      // Path_end contains the bottom section of the path from

      // the root to the current leaf.

      const _RopeRep* _M_path_end[_S_path_cache_len];

      int _M_leaf_index;     // Last valid __pos in path_end;

                             // _M_path_end[0] ... _M_path_end[leaf_index-1]

                             // point to concatenation nodes.

      unsigned char _M_path_directions;

                          // (path_directions >> __i) & 1 is 1

                          // iff we got from _M_path_end[leaf_index - __i - 1]

                          // to _M_path_end[leaf_index - __i] by going to the

                          // __right. Assumes path_cache_len <= 9.

      _CharT _M_tmp_buf[_S_iterator_buf_len];

                        // Short buffer for surrounding chars.

                        // This is useful primarily for

                        // RopeFunctions.  We put the buffer

                        // here to avoid locking in the

                        // multithreaded case.

      // The cached path is generally assumed to be valid

      // only if the buffer is valid.

      static void _S_setbuf(_Rope_iterator_base& __x);

                                        // Set buffer contents given

                                        // path cache.

      static void _S_setcache(_Rope_iterator_base& __x);

                                        // Set buffer contents and

                                        // path cache.

      static void _S_setcache_for_incr(_Rope_iterator_base& __x);

                                        // As above, but assumes path

                                        // cache is valid for previous posn.

      _Rope_iterator_base() { }

      _Rope_iterator_base(_RopeRep* __root, size_t __pos)

      : _M_current_pos(__pos), _M_root(__root), _M_buf_ptr(0) { }

      void _M_incr(size_t __n);

      void _M_decr(size_t __n);

    public:

      size_t

      index() const

      { return _M_current_pos; }

      _Rope_iterator_base(const _Rope_iterator_base& __x)