stl_rope.h

俄罗斯高人Mamaich的Pocket gcc编译器（运行在PocketPC上）的全部源代码。

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

// Copyright (C) 2001, 2002 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 2, 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.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

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

/** @file ext/stl_rope.h
 *  This file is a GNU extension to the Standard C++ Library (possibly
 *  containing extensions from the HP/SGI STL subset).  You should only
 *  include this header if you are using GCC 3 or later.
 */

// 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 <bits/stl_threads.h>
#   define __GC_CONST   // constant except for deallocation
# endif

#include <ext/memory> // For uninitialized_copy_n

namespace __gnu_cxx
{
using std::size_t;
using std::ptrdiff_t;
using std::allocator;
using std::iterator;
using std::reverse_iterator;
using std::_Alloc_traits;
using std::_Destroy;
using std::_Refcount_Base;

// 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>
class sequence_buffer : public iterator<std::output_iterator_tag,void,void,void,void>
{
    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 _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=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 std::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,