stl_rope.h

ISO_C++：C++_STL开发文档

/*
 * 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 <stl_threads.h>
#   define __GC_CONST   // constant except for deallocation
# endif
# ifdef __STL_SGI_THREADS
#    include <mutex.h>
# endif

__STL_BEGIN_NAMESPACE

#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma set woff 1174
#endif

// 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 <class _CharT>
inline _CharT _S_eos(_CharT*) { return _CharT(); }

// Test for basic character types.
// For basic character types leaves having a trailing eos.
template <class _CharT>
inline bool _S_is_basic_char_type(_CharT*) { return false; }
template <class _CharT>
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 <class _CharT>
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 _CharT>
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<sequence::value_type>
// 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<sequence::value_type> and a
// little like containers.

template<class _Sequence, size_t _Buf_sz = 100
#   if defined(__sgi) && !defined(__GNUC__)
#        define __TYPEDEF_WORKAROUND
         ,class _V = typename _Sequence::value_type
#   endif
        >
// The 3rd parameter works around a common compiler bug.
class sequence_buffer : public output_iterator {
    public:
#       ifndef __TYPEDEF_WORKAROUND
            typedef typename _Sequence::value_type value_type;
#       else
            typedef _V value_type;
#       endif
    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 _CharT>
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 _CharT, class _Alloc=__STL_DEFAULT_ALLOCATOR(_CharT)> class rope;
template<class _CharT, class _Alloc> struct _Rope_RopeConcatenation;
template<class _CharT, class _Alloc> struct _Rope_RopeLeaf;
template<class _CharT, class _Alloc> struct _Rope_RopeFunction;
template<class _CharT, class _Alloc> struct _Rope_RopeSubstring;
template<class _CharT, class _Alloc> class _Rope_iterator;
template<class _CharT, class _Alloc> class _Rope_const_iterator;
template<class _CharT, class _Alloc> class _Rope_char_ref_proxy;
template<class _CharT, class _Alloc> class _Rope_char_ptr_proxy;

template<class _CharT, class _Alloc>
bool operator== (const _Rope_char_ptr_proxy<_CharT,_Alloc>& __x,
                 const _Rope_char_ptr_proxy<_CharT,_Alloc>& __y);

template<class _CharT, class _Alloc>
_Rope_const_iterator<_CharT,_Alloc> operator-
        (const _Rope_const_iterator<_CharT,_Alloc>& __x,
         ptrdiff_t __n);

template<class _CharT, class _Alloc>
_Rope_const_iterator<_CharT,_Alloc> operator+
        (const _Rope_const_iterator<_CharT,_Alloc>& __x,
         ptrdiff_t __n);

template<class _CharT, class _Alloc>
_Rope_const_iterator<_CharT,_Alloc> operator+
        (ptrdiff_t __n,
         const _Rope_const_iterator<_CharT,_Alloc>& __x);

template<class _CharT, class _Alloc>
bool operator== 
        (const _Rope_const_iterator<_CharT,_Alloc>& __x,
         const _Rope_const_iterator<_CharT,_Alloc>& __y);

template<class _CharT, class _Alloc>
bool operator< 
        (const _Rope_const_iterator<_CharT,_Alloc>& __x,
         const _Rope_const_iterator<_CharT,_Alloc>& __y);

template<class _CharT, class _Alloc>
ptrdiff_t operator- 
        (const _Rope_const_iterator<_CharT,_Alloc>& __x,
         const _Rope_const_iterator<_CharT,_Alloc>& __y);

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

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

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

template<class _CharT, class _Alloc>
bool operator== 
        (const _Rope_iterator<_CharT,_Alloc>& __x,
         const _Rope_iterator<_CharT,_Alloc>& __y);

template<class _CharT, class _Alloc>
bool operator< 
        (const _Rope_iterator<_CharT,_Alloc>& __x,
         const _Rope_iterator<_CharT,_Alloc>& __y);

template<class _CharT, class _Alloc>
ptrdiff_t operator- 
        (const _Rope_iterator<_CharT,_Alloc>& __x,
         const _Rope_iterator<_CharT,_Alloc>& __y);

template<class _CharT, class _Alloc>
rope<_CharT,_Alloc> operator+ (const rope<_CharT,_Alloc>& __left,
                               const rope<_CharT,_Alloc>& __right);
        
template<class _CharT, class _Alloc>
rope<_CharT,_Alloc> operator+ (const rope<_CharT,_Alloc>& __left,
                               const _CharT* __right);
        
template<class _CharT, class _Alloc>
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<class _CharT, class _Alloc>
struct _Rope_Concat_fn
       : public binary_function<rope<_CharT,_Alloc>, rope<_CharT,_Alloc>,
                                     rope<_CharT,_Alloc> > {
        rope<_CharT,_Alloc> operator() (const rope<_CharT,_Alloc>& __x,
                                const rope<_CharT,_Alloc>& __y) {
                    return __x + __y;
        }
};

template <class _CharT, class _Alloc>
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.