Subversion Repositories Kolibri OS

/*

 * Copyright (c) 1997-1998

 * 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.

 */

/* NOTE: This is an internal header file, included by other STL headers.

 *   You should not attempt to use it directly.

 */

// rope<_CharT,_Alloc> is a sequence of _CharT.

// Ropes appear to be mutable, but update operations

// really copy enough of the data structure to leave the original

// valid.  Thus ropes can be logically copied by just copying

// a pointer value.

#ifndef __SGI_STL_INTERNAL_ROPE_H

# define __SGI_STL_INTERNAL_ROPE_H

# ifdef __GC

#   define __GC_CONST const

# else

#   include 

#   define __GC_CONST   // constant except for deallocation

# endif

# ifdef __STL_SGI_THREADS

#    include 

# endif

namespace std

{

// 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 convereted 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 output_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;

            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;

            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;

                size_t __j = 0;

                for (; __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 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>();

}

//

// 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 occurence 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.

//

// 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.

#define __STATIC_IF_SGI_ALLOC  /* not static */

// Base class for ordinary allocators.

template 

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 _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 

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) {}

};

template

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)

        : _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 __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

};

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 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)

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

          _M_data(__d)

        {

        __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

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)

      : _Rope_RopeRep<_CharT,_Alloc>(_S_concat,

                                     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() {

        _M_free_c_string();

        _M_left->_M_unref_nonnil();

        _M_right->_M_unref_nonnil();

    }

# endif

};

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, allocator_type __a)

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

      , _M_fn(__f)

#       ifndef __GC

      , _M_delete_when_done(__d)

#       endif

    {

        __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.

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 _S_function:

            case _S_substringfn:

              {

                char_producer<_CharT>* __fn =

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

                __stl_assert(__start_pos + __req_len <= _M_size);

                __stl_assert(_M_start + _M_size <= _M_base->_M_size);

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

              }

              break;

            case _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:

              __stl_assert(false);

        }

    }

    typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type

        allocator_type;

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

                          size_t __l, allocator_type __a)

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

        char_producer<_CharT>(),

        _M_base(__b),

        _M_start(__s)

    {

        __stl_assert(__l > 0);

        __stl_assert(__s + __l <= __b->_M_size);

#       ifndef __GC

            _M_base->_M_ref_nonnil();

#       endif

        _M_tag = _S_substringfn;

    }

    virtual ~_Rope_RopeSubstring()

      {

#       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); }

#   ifdef __STL_USE_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_valid(false), _M_root(__r) {}

    _Rope_char_ref_proxy(const _Rope_char_ref_proxy& __x)

      : _M_pos(__x._M_pos), _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) {

        __stl_assert(0 == __x);

    }

    _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 random_access_iterator<_CharT, ptrdiff_t> {

    friend class rope<_CharT,_Alloc>;

  public:

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

    typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;

        // Borland doesnt 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) {

        if (0 != __x._M_buf_ptr) {

            *this = __x;

        } else {

            _M_current_pos = __x._M_current_pos;

            _M_root = __x._M_root;

            _M_buf_ptr = 0;

        }

    }

};

template class _Rope_iterator;

template

class _Rope_const_iterator : public _Rope_iterator_base<_CharT,_Alloc> {

    friend class rope<_CharT,_Alloc>;

  protected:

      typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep;

      // The one from the base class may not be directly visible.

    _Rope_const_iterator(const _RopeRep* __root, size_t __pos):

                   _Rope_iterator_base<_CharT,_Alloc>(

                     const_cast<_RopeRep*>(__root), __pos)

                   // Only nonconst iterators modify root ref count

    {}

  public:

    typedef _CharT reference;   // Really a value.  Returning a reference

                                // Would be a mess, since it would have

                                // to be included in refcount.

    typedef const _CharT* pointer;

  public:

    _Rope_const_iterator() {};

    _Rope_const_iterator(const _Rope_const_iterator& __x) :

                                _Rope_iterator_base<_CharT,_Alloc>(__x) { }

    _Rope_const_iterator(const _Rope_iterator<_CharT,_Alloc>& __x);

    _Rope_const_iterator(const rope<_CharT,_Alloc>& __r, size_t __pos) :

        _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos) {}

    _Rope_const_iterator& operator= (const _Rope_const_iterator& __x) {

        if (0 != __x._M_buf_ptr) {

            *(static_cast<_Rope_iterator_base<_CharT,_Alloc>*>(this)) = __x;

        } else {

            _M_current_pos = __x._M_current_pos;

            _M_root = __x._M_root;

            _M_buf_ptr = 0;

        }

        return(*this);

    }

    reference operator*() {

        if (0 == _M_buf_ptr) _S_setcache(*this);

        return *_M_buf_ptr;

    }

    _Rope_const_iterator& operator++() {

        __GC_CONST _CharT* __next;

        if (0 != _M_buf_ptr && (__next = _M_buf_ptr + 1) < _M_buf_end) {

            _M_buf_ptr = __next;

            ++_M_current_pos;

        } else {

            _M_incr(1);

        }

        return *this;

    }

    _Rope_const_iterator& operator+=(ptrdiff_t __n) {

        if (__n >= 0) {

            _M_incr(__n);

        } else {

            _M_decr(-__n);

        }

        return *this;

    }

    _Rope_const_iterator& operator--() {

        _M_decr(1);

        return *this;

    }

    _Rope_const_iterator& operator-=(ptrdiff_t __n) {

        if (__n >= 0) {

            _M_decr(__n);

        } else {

            _M_incr(-__n);

        }

        return *this;

    }

    _Rope_const_iterator operator++(int) {

        size_t __old_pos = _M_current_pos;

        _M_incr(1);

        return _Rope_const_iterator<_CharT,_Alloc>(_M_root, __old_pos);

        // This makes a subsequent dereference expensive.

        // Perhaps we should instead copy the iterator

        // if it has a valid cache?

    }

    _Rope_const_iterator operator--(int) {

        size_t __old_pos = _M_current_pos;

        _M_decr(1);

        return _Rope_const_iterator<_CharT,_Alloc>(_M_root, __old_pos);

    }

    template

    friend _Rope_const_iterator<_CharT2,_Alloc2> operator-

        (const _Rope_const_iterator<_CharT2,_Alloc2>& __x,

         ptrdiff_t __n);

    template

    friend _Rope_const_iterator<_CharT2,_Alloc2> operator+

        (const _Rope_const_iterator<_CharT2,_Alloc2>& __x,

         ptrdiff_t __n);

    template

    friend _Rope_const_iterator<_CharT2,_Alloc2> operator+

        (ptrdiff_t __n,

         const _Rope_const_iterator<_CharT2,_Alloc2>& __x);

    reference operator[](size_t __n) {

        return rope<_CharT,_Alloc>::_S_fetch(_M_root, _M_current_pos + __n);

    }

    template

    friend bool operator==

        (const _Rope_const_iterator<_CharT2,_Alloc2>& __x,

         const _Rope_const_iterator<_CharT2,_Alloc2>& __y);

    template

    friend bool operator<

        (const _Rope_const_iterator<_CharT2,_Alloc2>& __x,

         const _Rope_const_iterator<_CharT2,_Alloc2>& __y);

    template

    friend ptrdiff_t operator-

        (const _Rope_const_iterator<_CharT2,_Alloc2>& __x,

         const _Rope_const_iterator<_CharT2,_Alloc2>& __y);

};

template

class _Rope_iterator : public _Rope_iterator_base<_CharT,_Alloc> {

    friend class rope<_CharT,_Alloc>;

  protected:

    rope<_CharT,_Alloc>* _M_root_rope;

        // root is treated as a cached version of this,

        // and is used to detect changes to the underlying

        // rope.

        // Root is included in the reference count.

        // This is necessary so that we can detect changes reliably.

        // Unfortunately, it requires careful bookkeeping for the

        // nonGC case.

    _Rope_iterator(rope<_CharT,_Alloc>* __r, size_t __pos)

      : _Rope_iterator_base<_CharT,_Alloc>(__r->_M_tree_ptr, __pos),

        _M_root_rope(__r)

       { _RopeRep::_S_ref(_M_root); if (!(__r -> empty()))_S_setcache(*this); }

    void _M_check();

  public:

    typedef _Rope_char_ref_proxy<_CharT,_Alloc>  reference;

    typedef _Rope_char_ref_proxy<_CharT,_Alloc>* pointer;

  public:

    rope<_CharT,_Alloc>& container() { return *_M_root_rope; }

    _Rope_iterator() {

        _M_root = 0;  // Needed for reference counting.

    };

    _Rope_iterator(const _Rope_iterator& __x) :

        _Rope_iterator_base<_CharT,_Alloc>(__x) {

        _M_root_rope = __x._M_root_rope;

        _RopeRep::_S_ref(_M_root);

    }

    _Rope_iterator(rope<_CharT,_Alloc>& __r, size_t __pos);

    ~_Rope_iterator() {

        _RopeRep::_S_unref(_M_root);

    }

    _Rope_iterator& operator= (const _Rope_iterator& __x) {

        _RopeRep* __old = _M_root;

        _RopeRep::_S_ref(__x._M_root);

        if (0 != __x._M_buf_ptr) {

            _M_root_rope = __x._M_root_rope;

            *(static_cast<_Rope_iterator_base<_CharT,_Alloc>*>(this)) = __x;

        } else {

            _M_current_pos = __x._M_current_pos;

            _M_root = __x._M_root;

            _M_root_rope = __x._M_root_rope;

            _M_buf_ptr = 0;

        }

        _RopeRep::_S_unref(__old);

        return(*this);

    }

    reference operator*() {

        _M_check();

        if (0 == _M_buf_ptr) {

            return _Rope_char_ref_proxy<_CharT,_Alloc>(

               _M_root_rope, _M_current_pos);

        } else {

            return _Rope_char_ref_proxy<_CharT,_Alloc>(

               _M_root_rope, _M_current_pos, *_M_buf_ptr);

        }

    }

    _Rope_iterator& operator++() {

        _M_incr(1);

        return *this;

    }

    _Rope_iterator& operator+=(ptrdiff_t __n) {

        if (__n >= 0) {

            _M_incr(__n);

        } else {

            _M_decr(-__n);

        }

        return *this;

    }

    _Rope_iterator& operator--() {

        _M_decr(1);

        return *this;

    }

    _Rope_iterator& operator-=(ptrdiff_t __n) {

        if (__n >= 0) {

            _M_decr(__n);

        } else {

            _M_incr(-__n);

        }

        return *this;

    }

    _Rope_iterator operator++(int) {

        size_t __old_pos = _M_current_pos;

        _M_incr(1);

        return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);

    }

    _Rope_iterator operator--(int) {

        size_t __old_pos = _M_current_pos;

        _M_decr(1);

        return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);

    }

    reference operator[](ptrdiff_t __n) {

        return _Rope_char_ref_proxy<_CharT,_Alloc>(

          _M_root_rope, _M_current_pos + __n);

    }

    template

    friend bool operator==

        (const _Rope_iterator<_CharT2,_Alloc2>& __x,

         const _Rope_iterator<_CharT2,_Alloc2>& __y);

    template

    friend bool operator<

        (const _Rope_iterator<_CharT2,_Alloc2>& __x,

         const _Rope_iterator<_CharT2,_Alloc2>& __y);

    template

    friend ptrdiff_t operator-

        (const _Rope_iterator<_CharT2,_Alloc2>& __x,

         const _Rope_iterator<_CharT2,_Alloc2>& __y);

    template

    friend _Rope_iterator<_CharT2,_Alloc2> operator-

        (const _Rope_iterator<_CharT2,_Alloc2>& __x,

         ptrdiff_t __n);

    template

    friend _Rope_iterator<_CharT2,_Alloc2> operator+

        (const _Rope_iterator<_CharT2,_Alloc2>& __x,