rope

linux下编程用 编译软件

      {
        this->_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(this->_M_root);
      }

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

      ~_Rope_iterator()
      { _RopeRep::_S_unref(this->_M_root); }

      _Rope_iterator&
      operator=(const _Rope_iterator& __x)
      {
        _RopeRep* __old = this->_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
	  {
	    this->_M_current_pos = __x._M_current_pos;
            this->_M_root = __x._M_root;
            _M_root_rope = __x._M_root_rope;
            this->_M_buf_ptr = 0;
	  }
        _RopeRep::_S_unref(__old);
        return(*this);
      }

      reference
      operator*()
      {
        _M_check();
        if (0 == this->_M_buf_ptr)
	  return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
						      this->_M_current_pos);
	else
	  return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
						      this->_M_current_pos,
						      *this->_M_buf_ptr);
      }

      _Rope_iterator&
      operator++()
      {
        this->_M_incr(1);
        return *this;
      }

      _Rope_iterator&
      operator+=(ptrdiff_t __n)
      {
        if (__n >= 0)
	  this->_M_incr(__n);
	else
	  this->_M_decr(-__n);
	return *this;
      }

      _Rope_iterator&
      operator--()
      {
        this->_M_decr(1);
        return *this;
      }

      _Rope_iterator&
      operator-=(ptrdiff_t __n)
      {
        if (__n >= 0)
	  this->_M_decr(__n);
	else
	  this->_M_incr(-__n);
	return *this;
      }

      _Rope_iterator
      operator++(int)
      {
        size_t __old_pos = this->_M_current_pos;
        this->_M_incr(1);
        return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
      }

      _Rope_iterator
      operator--(int)
      {
        size_t __old_pos = this->_M_current_pos;
        this->_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,
						    this->_M_current_pos
						    + __n); }

      template<class _CharT2, class _Alloc2>
        friend bool
        operator==(const _Rope_iterator<_CharT2, _Alloc2>& __x,
		   const _Rope_iterator<_CharT2, _Alloc2>& __y);

      template<class _CharT2, class _Alloc2>
        friend bool
        operator<(const _Rope_iterator<_CharT2, _Alloc2>& __x,
		  const _Rope_iterator<_CharT2, _Alloc2>& __y);

      template<class _CharT2, class _Alloc2>
        friend ptrdiff_t
        operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x,
		  const _Rope_iterator<_CharT2, _Alloc2>& __y);

      template<class _CharT2, class _Alloc2>
        friend _Rope_iterator<_CharT2, _Alloc2>
        operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);

      template<class _CharT2, class _Alloc2>
        friend _Rope_iterator<_CharT2, _Alloc2>
        operator+(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);

      template<class _CharT2, class _Alloc2>
        friend _Rope_iterator<_CharT2, _Alloc2>
        operator+(ptrdiff_t __n, const _Rope_iterator<_CharT2, _Alloc2>& __x);
    };


  template <class _CharT, class _Alloc>
    struct _Rope_base
    : public _Alloc
    {
      typedef _Alloc allocator_type;

      allocator_type
      get_allocator() const
      { return *static_cast<const _Alloc*>(this); }

      typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
      // The one in _Base may not be visible due to template rules.

      _Rope_base(_RopeRep* __t, const allocator_type&)
      : _M_tree_ptr(__t) {}

      _Rope_base(const allocator_type&) {}

      // The only data member of a rope:
      _RopeRep *_M_tree_ptr;

#define __ROPE_DEFINE_ALLOC(_Tp, __name) \
        typedef typename \
          _Alloc::template rebind<_Tp>::other __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

	protected:
      _Rope_base&
      operator=(const _Rope_base&);
      
      _Rope_base(const _Rope_base&);
    };

  /**
   *  This is an SGI extension.
   *  @ingroup SGIextensions
   *  @doctodo
   */
  template <class _CharT, class _Alloc>
    class rope : public _Rope_base<_CharT, _Alloc>
    {
    public:
      typedef _CharT value_type;
      typedef ptrdiff_t difference_type;
      typedef size_t size_type;
      typedef _CharT const_reference;
      typedef const _CharT* const_pointer;
      typedef _Rope_iterator<_CharT, _Alloc> iterator;
      typedef _Rope_const_iterator<_CharT, _Alloc> const_iterator;
      typedef _Rope_char_ref_proxy<_CharT, _Alloc> reference;
      typedef _Rope_char_ptr_proxy<_CharT, _Alloc> pointer;

      friend class _Rope_iterator<_CharT, _Alloc>;
      friend class _Rope_const_iterator<_CharT, _Alloc>;
      friend struct _Rope_RopeRep<_CharT, _Alloc>;
      friend class _Rope_iterator_base<_CharT, _Alloc>;
      friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;
      friend class _Rope_char_ref_proxy<_CharT, _Alloc>;
      friend struct _Rope_RopeSubstring<_CharT, _Alloc>;

    protected:
      typedef _Rope_base<_CharT, _Alloc> _Base;
      typedef typename _Base::allocator_type allocator_type;
      using _Base::_M_tree_ptr;
      using _Base::get_allocator;
      typedef __GC_CONST _CharT* _Cstrptr;
      
      static _CharT _S_empty_c_str[1];
      
      static bool
      _S_is0(_CharT __c)
      { return __c == _S_eos((_CharT*)0); }
      
      enum { _S_copy_max = 23 };
                // For strings shorter than _S_copy_max, we copy to
                // concatenate.

      typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
      typedef _Rope_RopeConcatenation<_CharT, _Alloc> _RopeConcatenation;
      typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf;
      typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction;
      typedef _Rope_RopeSubstring<_CharT, _Alloc> _RopeSubstring;

      // Retrieve a character at the indicated position.
      static _CharT _S_fetch(_RopeRep* __r, size_type __pos);

#ifndef __GC
      // Obtain a pointer to the character at the indicated position.
      // The pointer can be used to change the character.
      // If such a pointer cannot be produced, as is frequently the
      // case, 0 is returned instead.
      // (Returns nonzero only if all nodes in the path have a refcount
      // of 1.)
      static _CharT* _S_fetch_ptr(_RopeRep* __r, size_type __pos);
#endif

      static bool
      _S_apply_to_pieces(// should be template parameter
			 _Rope_char_consumer<_CharT>& __c,
			 const _RopeRep* __r,
			 size_t __begin, size_t __end);
                         // begin and end are assumed to be in range.

#ifndef __GC
      static void
      _S_unref(_RopeRep* __t)
      { _RopeRep::_S_unref(__t); }

      static void
      _S_ref(_RopeRep* __t)
      { _RopeRep::_S_ref(__t); }

#else /* __GC */
      static void _S_unref(_RopeRep*) {}
      static void _S_ref(_RopeRep*) {}
#endif

#ifdef __GC
      typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
#else
      typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
#endif

      // _Result is counted in refcount.
      static _RopeRep* _S_substring(_RopeRep* __base,
                                    size_t __start, size_t __endp1);

      static _RopeRep* _S_concat_char_iter(_RopeRep* __r,
					   const _CharT* __iter, size_t __slen);
      // Concatenate rope and char ptr, copying __s.
      // Should really take an arbitrary iterator.
      // Result is counted in refcount.
      static _RopeRep* _S_destr_concat_char_iter(_RopeRep* __r,
						 const _CharT* __iter,
						 size_t __slen)
	// As above, but one reference to __r is about to be
	// destroyed.  Thus the pieces may be recycled if all
	// relevant reference counts are 1.
#ifdef __GC
	// We can't really do anything since refcounts are unavailable.
      { return _S_concat_char_iter(__r, __iter, __slen); }
#else
      ;
#endif

      static _RopeRep* _S_concat(_RopeRep* __left, _RopeRep* __right);
      // General concatenation on _RopeRep.  _Result
      // has refcount of 1.  Adjusts argument refcounts.

   public:
      void
      apply_to_pieces(size_t __begin, size_t __end,
		      _Rope_char_consumer<_CharT>& __c) const
      { _S_apply_to_pieces(__c, this->_M_tree_ptr, __begin, __end); }

   protected:

      static size_t
      _S_rounded_up_size(size_t __n)
      { return _RopeLeaf::_S_rounded_up_size(__n); }

      static size_t
      _S_allocated_capacity(size_t __n)
      {
	if (_S_is_basic_char_type((_CharT*)0))
	  return _S_rounded_up_size(__n) - 1;
	else
	  return _S_rounded_up_size(__n);
	
      }

      // Allocate and construct a RopeLeaf using the supplied allocator
      // Takes ownership of s instead of copying.
      static _RopeLeaf*
      _S_new_RopeLeaf(__GC_CONST _CharT *__s,
		      size_t __size, allocator_type __a)
      {
	_RopeLeaf* __space = typename _Base::_LAlloc(__a).allocate(1);
	return new(__space) _RopeLeaf(__s, __size, __a);
      }

      static _RopeConcatenation*
      _S_new_RopeConcatenation(_RopeRep* __left, _RopeRep* __right,
			       allocator_type __a)
      {
	_RopeConcatenation* __space = typename _Base::_CAlloc(__a).allocate(1);
	return new(__space) _RopeConcatenation(__left, __right, __a);
      }

      static _RopeFunction*
      _S_new_RopeFunction(char_producer<_CharT>* __f,
			  size_t __size, bool __d, allocator_type __a)
      {
	_RopeFunction* __space = typename _Base::_FAlloc(__a).allocate(1);
	return new(__space) _RopeFunction(__f, __size, __d, __a);
      }

      static _RopeSubstring*
      _S_new_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s,
			   size_t __l, allocator_type __a)
      {
	_RopeSubstring* __space = typename _Base::_SAlloc(__a).allocate(1);
	return new(__space) _RopeSubstring(__b, __s, __l, __a);
      }
      
      static _RopeLeaf*
      _S_RopeLeaf_from_unowned_char_ptr(const _CharT *__s,
					size_t __size, allocator_type __a)
#define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) \
                _S_RopeLeaf_from_unowned_char_ptr(__s, __size, __a)
      {
	if (0 == __size)
	  return 0;
	_CharT* __buf = __a.allocate(_S_rounded_up_size(__size));
	
	__uninitialized_copy_n_a(__s, __size, __buf, __a);
	_S_cond_store_eos(__buf[__size]);
	try
	  { return _S_new_RopeLeaf(__buf, __size, __a); }
	catch(...)
	  {
	    _RopeRep::__STL_FREE_STRING(__buf, __size, __a);
	    __throw_exception_again;
	  }
      }

      // Concatenation of nonempty strings.
      // Always builds a concatenation node.
      // Rebalances if the result is too deep.
      // Result has refcount 1.
      // Does not increment left and right ref counts even though
      // they are referenced.
      static _RopeRep*
      _S_tree_concat(_RopeRep* __left, _RopeRep* __right);

      // Concatenation helper functions
      static _RopeLeaf*
      _S_leaf_concat_char_iter(_RopeLeaf* __r,
			       const _CharT* __iter, size_t __slen);
      // Concatenate by copying leaf.
      // should take an arbitrary iterator
      // result has refcount 1.
#ifndef __GC
      static _RopeLeaf*
      _S_destr_leaf_concat_char_iter(_RopeLeaf* __r,
				     const _CharT* __iter, size_t __slen);
      // A version that potentially clobbers __r if __r->_M_ref_count == 1.
#endif

    private:
      
      static size_t _S_char_ptr_len(const _CharT* __s);
      // slightly generalized strlen

      rope(_RopeRep* __t, const allocator_type& __a = allocator_type())
      : _Base(__t, __a) { }


      // Copy __r to the _CharT buffer.
      // Returns __buffer + __r->_M_size.
      // Assumes that buffer is uninitialized.
      static _CharT* _S_flatten(_RopeRep* __r, _CharT* __buffer);

      // Again, with explicit starting position and length.
      // Assumes that buffer is uninitialized.
      static _CharT* _S_flatten(_RopeRep* __r,
				size_t __start, size_t __len,
				_CharT* __buffer);

      static const unsigned long
      _S_min_len[_Rope_constants::_S_max_rope_depth + 1];
      
      static bool
      _S_is_balanced(_RopeRep* __r)
      { return (__r->_M_size >= _S_min_len[__r->_M_depth]); }

      static bool
      _S_is_almost_balanced(_RopeRep* __r)
      { return (__r->_M_depth == 0
		|| __r->_M_size >= _S_min_len[__r->_M_depth - 1]); }

      static bool
      _S_is_roughly_balanced(_RopeRep* __r)
      { return (__r->_M_depth <= 1
		|| __r->_M_size >= _S_min_len[__r->_M_depth - 2]); }

      // Assumes the result is not empty.
      static _RopeRep*