_rope.h

来自「stl的源码」· C头文件 代码 · 共 1,929 行 · 第 1/5 页

/*
 *
 * Copyright (c) 1996,1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * Copyright (c) 1997
 * Moscow Center for SPARC Technology
 *
 * Copyright (c) 1999
 * Boris Fomitchev
 *
 * This material is provided "as is", with absolutely no warranty expressed
 * or implied. Any use is at your own risk.
 *
 * Permission to use or copy this software for any purpose is hereby granted
 * without fee, provided the above notices are retained on all copies.
 * Permission to modify the code and to distribute modified code is granted,
 * provided the above notices are retained, and a notice that the code was
 * modified is included with the above copyright notice.
 *
 */

/* 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 _STLP_INTERNAL_ROPE_H
#define _STLP_INTERNAL_ROPE_H

#ifndef _STLP_INTERNAL_ALGOBASE_H
#  include <stl/_algobase.h>
#endif

#if !defined (_STLP_USE_NO_IOSTREAMS) && !defined (_STLP_INTERNAL_IOSFWD)
#  include <stl/_iosfwd.h>
#endif

#ifndef _STLP_INTERNAL_ALLOC_H
#  include <stl/_alloc.h>
#endif

#ifndef _STLP_INTERNAL_ITERATOR_H
#  include <stl/_iterator.h>
#endif

#ifndef _STLP_INTERNAL_ALGO_H
#  include <stl/_algo.h>
#endif

#ifndef _STLP_INTERNAL_FUNCTION_BASE_H
#  include <stl/_function_base.h>
#endif

#ifndef _STLP_INTERNAL_NUMERIC_H
#  include <stl/_numeric.h>
#endif

#ifndef _STLP_INTERNAL_HASH_FUN_H
#  include <stl/_hash_fun.h>
#endif

#ifndef _STLP_CHAR_TRAITS_H
#  include <stl/char_traits.h>
#endif

#ifndef _STLP_INTERNAL_THREADS_H
#  include <stl/_threads.h>
#endif

#ifdef _STLP_SGI_THREADS
#  include <mutex.h>
#endif

#ifndef _STLP_DONT_SUPPORT_REBIND_MEMBER_TEMPLATE
#  define _STLP_CREATE_ALLOCATOR(__atype,__a, _Tp) (_Alloc_traits<_Tp,__atype>::create_allocator(__a))
#else
#  define _STLP_CREATE_ALLOCATOR(__atype,__a, _Tp) __stl_alloc_create(__a,(_Tp*)0)
#endif

_STLP_BEGIN_NAMESPACE

// 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, _STLP_DFL_TMPL_PARAM(_Alloc, allocator<_CharT>) > class rope;
template<class _CharT, class _Alloc> struct _Rope_RopeConcatenation;
template<class _CharT, class _Alloc> struct _Rope_RopeRep;
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;

_STLP_MOVE_TO_PRIV_NAMESPACE

template <class _CharT>
struct _BasicCharType { typedef __false_type _Ret; };

_STLP_TEMPLATE_NULL
struct _BasicCharType<char> { typedef __true_type _Ret; };

#ifdef _STLP_HAS_WCHAR_T
_STLP_TEMPLATE_NULL
struct _BasicCharType<wchar_t> { typedef __true_type _Ret; };
#endif

// Some helpers, so we can use the power algorithm 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>(); }

_STLP_MOVE_TO_STD_NAMESPACE

// Store an eos
template <class _CharT>
inline void _S_construct_null_aux(_CharT *__p, const __true_type&)
{ *__p = 0; }

template <class _CharT>
inline void _S_construct_null_aux(_CharT *__p, const __false_type&)
{ _STLP_STD::_Construct(__p); }

template <class _CharT>
inline void _S_construct_null(_CharT *__p) {
  typedef typename _IsIntegral<_CharT>::_Ret _Char_Is_Integral;
  _S_construct_null_aux(__p, _Char_Is_Integral());
}

// 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 _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
# if !(defined (_STLP_NON_TYPE_TMPL_PARAM_BUG) || \
       defined ( _STLP_NO_DEFAULT_NON_TYPE_PARAM ))
         , size_t _Buf_sz = 100
#   if defined(__sgi) && !defined(__GNUC__)
#   define __TYPEDEF_WORKAROUND
         ,class _V = typename _Sequence::value_type
#   endif /* __sgi */
# endif /* _STLP_NON_TYPE_TMPL_PARAM_BUG */
         >
// The 3rd parameter works around a common compiler bug.
class sequence_buffer : public iterator <output_iterator_tag, void, void, void, void> {
public:
# ifndef __TYPEDEF_WORKAROUND
  typedef typename _Sequence::value_type value_type;
  typedef sequence_buffer<_Sequence
# if !(defined (_STLP_NON_TYPE_TMPL_PARAM_BUG) || \
       defined ( _STLP_NO_DEFAULT_NON_TYPE_PARAM ))
  , _Buf_sz
  > _Self;
# else /* _STLP_NON_TYPE_TMPL_PARAM_BUG */
  > _Self;
  enum { _Buf_sz = 100};
# endif /* _STLP_NON_TYPE_TMPL_PARAM_BUG */
  // # endif
# else /* __TYPEDEF_WORKAROUND */
  typedef _V value_type;
  typedef sequence_buffer<_Sequence, _Buf_sz, _V> _Self;
# endif /* __TYPEDEF_WORKAROUND */
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 _Self& __x) {
    _M_prefix = __x._M_prefix;
    _M_buf_count = __x._M_buf_count;
    _STLP_STD::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
  }
  sequence_buffer(_Self& __x) {
    __x.flush();
    _M_prefix = __x._M_prefix;
    _M_buf_count = 0;
  }
  sequence_buffer(_Sequence& __s) : _M_prefix(&__s), _M_buf_count(0) {}
  _Self& operator= (_Self& __x) {
    __x.flush();
    _M_prefix = __x._M_prefix;
    _M_buf_count = 0;
    return *this;
  }
  _Self& operator= (const _Self& __x) {
    _M_prefix = __x._M_prefix;
    _M_buf_count = __x._M_buf_count;
    _STLP_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(const 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);
    }
  }
  _Self& write(const value_type *__s, size_t __len) {
    append(__s, __len);
    return *this;
  }
  _Self& put(value_type __x) {
    push_back(__x);
    return *this;
  }
  _Self& operator=(const value_type& __rhs) {
    push_back(__rhs);
    return *this;
  }
  _Self& operator*() { return *this; }
  _Self& operator++() { return *this; }
  _Self& operator++(int) { return *this; }
};

// The following should be treated as private, at least for now.
template<class _CharT>
class _Rope_char_consumer {
#if !defined (_STLP_MEMBER_TEMPLATES)
public:
  //Without member templates we have to use run-time parameterization.
  // The symmetry with char_producer is accidental and temporary.
  virtual ~_Rope_char_consumer() {}
  virtual bool operator()(const _CharT* __buffer, size_t __len) = 0;
#endif
};

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

template<class _CharT, class _Alloc>
struct _Rope_RopeRep
  : public _Refcount_Base
{
  typedef _Rope_RopeRep<_CharT, _Alloc> _Self;
public:
  //
  // GAB: 11/09/05
  //
  // "__ROPE_DEPTH_SIZE" is set to one more then the "__ROPE_MAX_DEPTH".
  // This was originally just an addition of "__ROPE_MAX_DEPTH + 1"
  // but this addition causes the sunpro compiler to complain about
  // multiple declarations during the initialization of "_S_min_len".
  // Changed to be a fixed value and the sunpro compiler appears to
  // be happy???
  //
#  define __ROPE_MAX_DEPTH  45
#  define __ROPE_DEPTH_SIZE 46 // __ROPE_MAX_DEPTH + 1
  enum { _S_max_rope_depth = __ROPE_MAX_DEPTH };
  enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function};
  // 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 };

  _Tag _M_tag:8;
  bool _M_is_balanced:8;

  _STLP_FORCE_ALLOCATORS(_CharT, _Alloc)
  typedef _Alloc allocator_type;

  allocator_type get_allocator() const { return allocator_type(_M_size);  }

  unsigned char _M_depth;
  _CharT* _STLP_VOLATILE _M_c_string;
  _STLP_PRIV _STLP_alloc_proxy<size_t, _CharT, allocator_type> _M_size;

#ifdef _STLP_NO_ARROW_OPERATOR
  _Rope_RopeRep() : _Refcount_Base(1), _M_size(allocator_type(), 0) {
#  if defined (_STLP_CHECK_RUNTIME_COMPATIBILITY)
    _STLP_CHECK_RUNTIME_COMPATIBILITY();
#  endif
  }
#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.       */
  _Rope_RopeRep(_Tag __t, unsigned char __d, bool __b, size_t _p_size,
                allocator_type __a) :
    _Refcount_Base(1),
    _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0), _M_size(__a, _p_size) {
#if defined (_STLP_CHECK_RUNTIME_COMPATIBILITY)
    _STLP_CHECK_RUNTIME_COMPATIBILITY();
#endif
    }