// named functions in rope that simply invoke the _RopeRep versions.//// A macro to introduce various allocation and deallocation functions// These need to be defined differently depending on whether or not// we are using standard conforming allocators, and whether the allocator// instances have real state.  Thus this macro is invoked repeatedly// with different definitions of __ROPE_DEFINE_ALLOC.// __ROPE_DEFINE_ALLOC(type,name) defines //   type * name_allocate(size_t) and//   void name_deallocate(tipe *, size_t)// Both functions may or may not be static.#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.//  The _Rope_rep_base class encapsulates//  the differences between SGI-style allocators and standard-conforming//  allocators.#ifdef __STL_USE_STD_ALLOCATORS#define __STATIC_IF_SGI_ALLOC  /* not static */// Base class for ordinary allocators.template <class _CharT, class _Allocator, bool _IsStatic>class _Rope_rep_alloc_base {public:  typedef typename _Alloc_traits<_CharT,_Allocator>::allocator_type          allocator_type;  allocator_type get_allocator() const { return _M_data_allocator; }  _Rope_rep_alloc_base(size_t __size, const allocator_type& __a)        : _M_size(__size), _M_data_allocator(__a) {}  size_t _M_size;       // This is here only to avoid wasting space                // for an otherwise empty base class.  protected:    allocator_type _M_data_allocator;# define __ROPE_DEFINE_ALLOC(_Tp, __name) \        typedef typename \          _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \        /*static*/ _Tp * __name##_allocate(size_t __n) \          { return __name##Allocator(_M_data_allocator).allocate(__n); } \        void __name##_deallocate(_Tp* __p, size_t __n) \          { __name##Allocator(_M_data_allocator).deallocate(__p, __n); }  __ROPE_DEFINE_ALLOCS(_Allocator);# undef __ROPE_DEFINE_ALLOC};// Specialization for allocators that have the property that we don't//  actually have to store an allocator object.  template <class _CharT, class _Allocator>class _Rope_rep_alloc_base<_CharT,_Allocator,true> {public:  typedef typename _Alloc_traits<_CharT,_Allocator>::allocator_type          allocator_type;  allocator_type get_allocator() const { return allocator_type(); }  _Rope_rep_alloc_base(size_t __size, const allocator_type&)                : _M_size(__size) {}  size_t _M_size;  protected:# define __ROPE_DEFINE_ALLOC(_Tp, __name) \        typedef typename \          _Alloc_traits<_Tp,_Allocator>::_Alloc_type __name##Alloc; \        typedef typename \          _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \        static _Tp* __name##_allocate(size_t __n) \                { return __name##Alloc::allocate(__n); } \        void __name##_deallocate(_Tp *__p, size_t __n) \                { __name##Alloc::deallocate(__p, __n); }  __ROPE_DEFINE_ALLOCS(_Allocator);# undef __ROPE_DEFINE_ALLOC};template <class _CharT, class _Alloc>struct _Rope_rep_base  : public _Rope_rep_alloc_base<_CharT,_Alloc,                                _Alloc_traits<_CharT,_Alloc>::_S_instanceless>{  typedef _Rope_rep_alloc_base<_CharT,_Alloc,                               _Alloc_traits<_CharT,_Alloc>::_S_instanceless>          _Base;  typedef typename _Base::allocator_type allocator_type;  _Rope_rep_base(size_t __size, const allocator_type& __a)    : _Base(__size, __a) {}};    #else /* !__STL_USE_STD_ALLOCATORS */#define __STATIC_IF_SGI_ALLOC statictemplate <class _CharT, class _Alloc> class _Rope_rep_base {public:  typedef _Alloc allocator_type;  static allocator_type get_allocator() { return allocator_type(); }  _Rope_rep_base(size_t __size, const allocator_type&) : _M_size(__size) {}  size_t _M_size;protected:# define __ROPE_DEFINE_ALLOC(_Tp, __name) \        typedef simple_alloc<_Tp, _Alloc> __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};#endif /* __STL_USE_STD_ALLOCATORS */template<class _CharT, class _Alloc>struct _Rope_RopeRep : public _Rope_rep_base<_CharT,_Alloc># ifndef __GC    , _Refcount_Base# endif{    public:    enum { _S_max_rope_depth = 45 };    enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function};    _Tag _M_tag:8;    bool _M_is_balanced:8;    unsigned char _M_depth;    __GC_CONST _CharT* _M_c_string;                        /* 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;    _Rope_RopeRep(_Tag __t, int __d, bool __b, size_t __size,                  allocator_type __a)        : _M_tag(__t), _M_depth(__d), _M_is_balanced(__b), _M_c_string(0),          _Rope_rep_base<_CharT,_Alloc>(__size, __a)#         ifndef __GC	  , _Refcount_Base(1)#	  endif    { }#   ifdef __GC        void _M_incr () {}#   endif#   ifdef __STL_USE_STD_ALLOCATORS        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);#   else        static void _S_free_string(__GC_CONST _CharT*, size_t __len);#       define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l);#   endif                        // 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};template<class _CharT, class _Alloc>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 accomodate 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 + _S_alloc_granularity-1)                        &~ (_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, allocator_type __a)        : _M_data(__d)        , _Rope_RopeRep<_CharT,_Alloc>(_S_leaf, 0, true, __size, __a)        {        __stl_assert(__size > 0);        if (_S_is_basic_char_type((_CharT *)0)) {            // already eos terminated.            _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() {        if (_M_data != _M_c_string) {            _M_free_c_string();        }        __STL_FREE_STRING(_M_data, _M_size, get_allocator());    }# endif};template<class _CharT, class _Alloc>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,                             allocator_type __a)      : _M_left(__l), _M_right(__r)      , _Rope_RopeRep<_CharT,_Alloc>(          _S_concat, max(__l->_M_depth, __r->_M_depth) + 1, false,          __l->_M_size + __r->_M_size, __a)      {}# ifndef __GC    ~_Rope_RopeConcatenation() {        _M_free_c_string();        _M_left->_M_unref_nonnil();        _M_right->_M_unref_nonnil();    }# endif};template<class _CharT, class _Alloc>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, allocator_type __a)      : _M_fn(__f)#       ifndef __GC      , _M_delete_when_done(__d)#       endif      , _Rope_RopeRep<_CharT,_Alloc>(_S_function, 0, true, __size, __a) {        __stl_assert(__size > 0);#       ifdef __GC            if (__d) {                GC_REGISTER_FINALIZER(                  this, _Rope_RopeFunction::_S_fn_finalization_proc, 0, 0, 0);            }#       endif    }# ifndef __GC    ~_Rope_RopeFunction() {          _M_free_c_string();          if (_M_delete_when_done) {              delete _M_fn;          }    }# endif};// 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.