_rope.h File Reference

#include <stl/_algobase.h>
#include <stl/_iosfwd.h>
#include <stl/_alloc.h>
#include <stl/_iterator.h>
#include <stl/_algo.h>
#include <stl/_function_base.h>
#include <stl/_numeric.h>
#include <stl/_hash_fun.h>
#include <stl/char_traits.h>
#include <stl/_threads.h>
#include <stl/_string_npos.h>
#include <stl/_rope.c>

Include dependency graph for _rope.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	_BasicCharType< _CharT >
struct	_BasicCharType< char >
struct	_Rope_Concat_fn< _CharT, _Alloc >
class	char_producer< _CharT >
class	sequence_buffer< _Sequence, _Buf_sz >
class	_Rope_char_consumer< _CharT >
struct	_Rope_RopeRep< _CharT, _Alloc >
struct	_Rope_RopeLeaf< _CharT, _Alloc >
struct	_Rope_RopeConcatenation< _CharT, _Alloc >
struct	_Rope_RopeFunction< _CharT, _Alloc >
struct	_Rope_RopeSubstring< _CharT, _Alloc >
struct	_Rope_self_destruct_ptr< _CharT, _Alloc >
class	_Rope_char_ref_proxy< _CharT, _Alloc >
class	_Rope_char_ptr_proxy< _CharT, _Alloc >
class	_Rope_iterator_base< _CharT, _Alloc >
class	_Rope_const_iterator< _CharT, _Alloc >
class	_Rope_iterator< _CharT, _Alloc >
class	rope< _CharT, _Alloc >
struct	hash< crope >

Macros
#define	_STLP_CREATE_ALLOCATOR(__atype, __a, _Tp)   (_Alloc_traits<_Tp,__atype>::create_allocator(__a))
#define	__ROPE_MAX_DEPTH   45
#define	__ROPE_DEPTH_SIZE   46
#define	_ROPE_SWAP_SPECIALIZATION(_CharT, __Alloc)
#define	__exponentiate_threshold   size_t(32)

Typedefs
typedef rope< char, allocator< char > >	crope

Functions
template<class _CharT , class _Alloc >
rope< _CharT, _Alloc >	__identity_element (_Rope_Concat_fn< _CharT, _Alloc >)
template<class _CharT >
_STLP_MOVE_TO_STD_NAMESPACE void	_S_construct_null_aux (_CharT *__p, const __true_type &)
template<class _CharT >
void	_S_construct_null_aux (_CharT *__p, const __false_type &)
template<class _CharT >
void	_S_construct_null (_CharT *__p)
template<class _CharT , class _Alloc , class _CharConsumer >
bool	_S_apply_to_pieces (_CharConsumer &__c, _Rope_RopeRep< _CharT, _Alloc > *__r, size_t __begin, size_t __end)
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_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_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_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 >
rope< _CharT, _Alloc >	operator+ (const rope< _CharT, _Alloc > &__left, const rope< _CharT, _Alloc > &__right)
template<class _CharT , class _Alloc >
rope< _CharT, _Alloc > &	operator+= (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+= (rope< _CharT, _Alloc > &__left, const _CharT *__right)
template<class _CharT , class _Alloc >
rope< _CharT, _Alloc >	operator+ (const rope< _CharT, _Alloc > &__left, _CharT __right)
template<class _CharT , class _Alloc >
rope< _CharT, _Alloc > &	operator+= (rope< _CharT, _Alloc > &__left, _CharT __right)
template<class _CharT , class _Alloc >
bool	operator< (const rope< _CharT, _Alloc > &__left, const rope< _CharT, _Alloc > &__right)
template<class _CharT , class _Alloc >
bool	operator== (const rope< _CharT, _Alloc > &__left, const rope< _CharT, _Alloc > &__right)
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 _Traits , class _Alloc >
basic_ostream< _CharT, _Traits > &	operator<< (basic_ostream< _CharT, _Traits > &__o, const rope< _CharT, _Alloc > &__r)
crope::reference	__mutable_reference_at (crope &__c, size_t __i)
void	swap (crope &__x, crope &__y)
template<class _CharT , class _Alloc >
void	_Rope_rotate (_Rope_iterator< _CharT, _Alloc > __first, _Rope_iterator< _CharT, _Alloc > __middle, _Rope_iterator< _CharT, _Alloc > __last)
void	rotate (_Rope_iterator< char, allocator< char > > __first, _Rope_iterator< char, allocator< char > > __middle, _Rope_iterator< char, allocator< char > > __last)

Macro Definition Documentation

__exponentiate_threshold

#define __exponentiate_threshold   size_t(32)

__ROPE_DEPTH_SIZE

#define __ROPE_DEPTH_SIZE   46

Definition at line 343 of file _rope.h.

__ROPE_MAX_DEPTH

#define __ROPE_MAX_DEPTH   45

Definition at line 342 of file _rope.h.

_ROPE_SWAP_SPECIALIZATION

#define _ROPE_SWAP_SPECIALIZATION	(		_CharT,
			__Alloc
	)

Value:

    inline void swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a, \
                     _Rope_char_ref_proxy <_CharT, __Alloc > __b) { \
        _CharT __tmp = __a; \
        __a = __b; \
        __b = __tmp; \
    }

Definition at line 697 of file _rope.h.

_STLP_CREATE_ALLOCATOR

#define _STLP_CREATE_ALLOCATOR	(		__atype,
			__a,
			_Tp
	)		(_Alloc_traits<_Tp,__atype>::create_allocator(__a))

Definition at line 81 of file _rope.h.

Typedef Documentation

crope

typedef rope<char, allocator<char> > crope

Definition at line 2297 of file _rope.h.

Function Documentation

__identity_element()

template<class _CharT , class _Alloc >

rope< _CharT, _Alloc > __identity_element ( _Rope_Concat_fn< _CharT, _Alloc >  )

inline

Definition at line 133 of file _rope.h.

{ return rope<_CharT,_Alloc>(); }

__mutable_reference_at()

crope::reference __mutable_reference_at ( crope &  __c, size_t  __i  )

inline

Definition at line 2302 of file _rope.h.

{ return __c.mutable_reference_at(__i); }

_Rope_rotate()

template<class _CharT , class _Alloc >

void _Rope_rotate	(	_Rope_iterator< _CharT, _Alloc >	__first,
		_Rope_iterator< _CharT, _Alloc >	__middle,
		_Rope_iterator< _CharT, _Alloc >	__last
	)

Definition at line 1358 of file _rope.c.

                                                        {
  _STLP_ASSERT(__first.container() == __middle.container() &&
               __middle.container() == __last.container())
  rope<_CharT,_Alloc>& __r(__first.container());
  rope<_CharT,_Alloc> __prefix = __r.substr(0, __first.index());
  rope<_CharT,_Alloc> __suffix =
    __r.substr(__last.index(), __r.size() - __last.index());
  rope<_CharT,_Alloc> __part1 =
    __r.substr(__middle.index(), __last.index() - __middle.index());
  rope<_CharT,_Alloc> __part2 =
    __r.substr(__first.index(), __middle.index() - __first.index());
  __r = __prefix;
  __r += __part1;
  __r += __part2;
  __r += __suffix;
}

Referenced by rotate().

_S_apply_to_pieces()

template<class _CharT , class _Alloc , class _CharConsumer >

bool _S_apply_to_pieces	(	_CharConsumer &	__c,
		_Rope_RopeRep< _CharT, _Alloc > *	__r,
		size_t	__begin,
		size_t	__end
	)

Definition at line 785 of file _rope.c.

                                                      {
  typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
  typedef _Rope_RopeConcatenation<_CharT,_Alloc> _RopeConcatenation;
  typedef _Rope_RopeLeaf<_CharT,_Alloc> _RopeLeaf;
  typedef _Rope_RopeFunction<_CharT,_Alloc> _RopeFunction;
 
  if (0 == __r) return true;
  switch(__r->_M_tag) {
  case _RopeRep::_S_concat:
  {
    _RopeConcatenation* __conc = __STATIC_CAST(_RopeConcatenation*, __r);
    _RopeRep* __left =  __conc->_M_left;
    size_t __left_len = __left->_M_size._M_data;
    if (__begin < __left_len) {
      size_t __left_end = (min) (__left_len, __end);
      if (!_S_apply_to_pieces(__c, __left, __begin, __left_end))
        return false;
    }
    if (__end > __left_len) {
      _RopeRep* __right =  __conc->_M_right;
      size_t __right_start = (max)(__left_len, __begin);
      if (!_S_apply_to_pieces(__c, __right,
                              __right_start - __left_len,
                              __end - __left_len)) {
        return false;
      }
    }
  }
  return true;
  case _RopeRep::_S_leaf:
  {
    _RopeLeaf* __l = __STATIC_CAST(_RopeLeaf*, __r);
    return __c(__l->_M_data + __begin, __end - __begin);
  }
  case _RopeRep::_S_function:
  case _RopeRep::_S_substringfn:
  {
    _RopeFunction* __f = __STATIC_CAST(_RopeFunction*, __r);
    size_t __len = __end - __begin;
    bool __result;
    _CharT* __buffer = __r->get_allocator().allocate(__len);
    _STLP_TRY {
      (*(__f->_M_fn))(__begin, __len, __buffer);
      __result = __c(__buffer, __len);
      __r->get_allocator().deallocate(__buffer, __len);
    }
    _STLP_UNWIND((__r->get_allocator().deallocate(__buffer, __len)))
    return __result;
  }
  default:
    _STLP_ASSERT(false)
    /*NOTREACHED*/
    return false;
  }
}

Referenced by _S_apply_to_pieces(), rope< _CharT, _Alloc >::_S_flatten(), rope< _CharT, _Alloc >::apply_to_pieces(), and rope< _CharT, _Alloc >::find().

_S_construct_null()

template<class _CharT >

void _S_construct_null ( _CharT *  __p )

inline

Definition at line 148 of file _rope.h.

                                           {
  typedef typename _IsIntegral<_CharT>::_Ret _Char_Is_Integral;
  _S_construct_null_aux(__p, _Char_Is_Integral());
}

Referenced by rope< _CharT, _Alloc >::_S_leaf_concat_char_iter(), rope< _CharT, _Alloc >::_S_RopeLeaf_from_unowned_char_ptr(), rope< _CharT, _Alloc >::_S_substring(), _Terminate_RopeLeaf(), rope< _CharT, _Alloc >::c_str(), rope< _CharT, _Alloc >::replace_with_c_str(), and rope< _CharT, _Alloc >::rope().

_S_construct_null_aux() [1/2]

template<class _CharT >

void _S_construct_null_aux ( _CharT *  __p, const __false_type &    )

inline

Definition at line 144 of file _rope.h.

{ _STLP_STD::_Construct(__p); }

_S_construct_null_aux() [2/2]

template<class _CharT >

_STLP_MOVE_TO_STD_NAMESPACE void _S_construct_null_aux ( _CharT *  __p, const __true_type &    )

inline

Definition at line 140 of file _rope.h.

{ *__p = 0; }

Referenced by _S_construct_null().

operator+() [1/7]

template<class _CharT , class _Alloc >

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

inline

Definition at line 2122 of file _rope.h.

{ return _Rope_const_iterator<_CharT,_Alloc>(__x._M_root, __x._M_current_pos + __n); }

operator+() [2/7]

template<class _CharT , class _Alloc >

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

inline

Definition at line 2180 of file _rope.h.

                         {
  return _Rope_iterator<_CharT,_Alloc>(__x._M_root_rope, __x._M_current_pos + __n);
}

operator+() [3/7]

template<class _CharT , class _Alloc >

rope< _CharT, _Alloc > operator+ ( const rope< _CharT, _Alloc > &  __left, _CharT  __right  )

inline

Definition at line 2226 of file _rope.h.

                                                              {
  return rope<_CharT,_Alloc>(rope<_CharT,_Alloc>::_S_concat_char_iter(__left._M_tree_ptr._M_data, &__right, 1));
}

operator+() [4/7]

template<class _CharT , class _Alloc >

rope< _CharT, _Alloc > operator+ ( const rope< _CharT, _Alloc > &  __left, const _CharT *  __right  )

inline

Definition at line 2210 of file _rope.h.

                                  {
  size_t __rlen = rope<_CharT,_Alloc>::_S_char_ptr_len(__right);
  return rope<_CharT,_Alloc>(rope<_CharT,_Alloc>::_S_concat_char_iter(__left._M_tree_ptr._M_data, __right, __rlen));
}

operator+() [5/7]

template<class _CharT , class _Alloc >

rope< _CharT, _Alloc > operator+ ( const rope< _CharT, _Alloc > &  __left, const rope< _CharT, _Alloc > &  __right  )

inline

Definition at line 2193 of file _rope.h.

                                               {
  _STLP_ASSERT(__left.get_allocator() == __right.get_allocator())
  return rope<_CharT,_Alloc>(rope<_CharT,_Alloc>::_S_concat_rep(__left._M_tree_ptr._M_data, __right._M_tree_ptr._M_data));
  // Inlining this should make it possible to keep __left and __right in registers.
}

operator+() [6/7]

template<class _CharT , class _Alloc >

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

inline

Definition at line 2127 of file _rope.h.

{ return _Rope_const_iterator<_CharT,_Alloc>(__x._M_root, __x._M_current_pos + __n); }

operator+() [7/7]

template<class _CharT , class _Alloc >

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

inline

Definition at line 2187 of file _rope.h.

                                                                   {
  return _Rope_iterator<_CharT,_Alloc>(__x._M_root_rope, __x._M_current_pos + __n);
}

operator+=() [1/3]

template<class _CharT , class _Alloc >

rope< _CharT, _Alloc > & operator+= ( rope< _CharT, _Alloc > &  __left, _CharT  __right  )

inline

Definition at line 2232 of file _rope.h.

                                                         {
  __left.append(__right);
  return __left;
}

operator+=() [2/3]

template<class _CharT , class _Alloc >

rope< _CharT, _Alloc > & operator+= ( rope< _CharT, _Alloc > &  __left, const _CharT *  __right  )

inline

Definition at line 2218 of file _rope.h.

                                   {
  __left.append(__right);
  return __left;
}

operator+=() [3/3]

template<class _CharT , class _Alloc >

rope< _CharT, _Alloc > & operator+= ( rope< _CharT, _Alloc > &  __left, const rope< _CharT, _Alloc > &  __right  )

inline

Definition at line 2202 of file _rope.h.

                                                {
  __left.append(__right);
  return __left;
}

operator-() [1/4]

template<class _CharT , class _Alloc >

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

inline

Definition at line 2109 of file _rope.h.

{ return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; }

operator-() [2/4]

template<class _CharT , class _Alloc >

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

inline

Definition at line 2116 of file _rope.h.

{ return _Rope_const_iterator<_CharT,_Alloc>(__x._M_root, __x._M_current_pos - __n); }

operator-() [3/4]

template<class _CharT , class _Alloc >

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

inline

Definition at line 2165 of file _rope.h.

{ return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; }

operator-() [4/4]

template<class _CharT , class _Alloc >

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

inline

Definition at line 2172 of file _rope.h.

                         {
  return _Rope_iterator<_CharT,_Alloc>(__x._M_root_rope, __x._M_current_pos - __n);
}

operator<() [1/3]

template<class _CharT , class _Alloc >

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

inline

Definition at line 2080 of file _rope.h.

{ return (__x._M_current_pos < __y._M_current_pos); }

operator<() [2/3]

template<class _CharT , class _Alloc >

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

inline

Definition at line 2138 of file _rope.h.

{ return (__x._M_current_pos < __y._M_current_pos); }

operator<() [3/3]

template<class _CharT , class _Alloc >

bool operator< ( const rope< _CharT, _Alloc > &  __left, const rope< _CharT, _Alloc > &  __right  )

inline

Definition at line 2238 of file _rope.h.

                                               {
  return __left.compare(__right) < 0;
}

operator<<()

template<class _CharT , class _Traits , class _Alloc >

basic_ostream< _CharT, _Traits > & operator<<	(	basic_ostream< _CharT, _Traits > &	__o,
		const rope< _CharT, _Alloc > &	__r
	)

Definition at line 873 of file _rope.c.

                                                                            {
  typedef typename _IsIntegral<_CharT>::_Ret _Char_Is_Integral;
  return _S_io_get(__o, __r, _Char_Is_Integral());
}

operator==() [1/4]

template<class _CharT , class _Alloc >

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

inline

Definition at line 2286 of file _rope.h.

                                                                        {
  return (__x._M_pos == __y._M_pos && __x._M_root == __y._M_root);
}

operator==() [2/4]

template<class _CharT , class _Alloc >

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

inline

Definition at line 2073 of file _rope.h.

                                                                        {
  return (__x._M_current_pos == __y._M_current_pos &&
          __x._M_root == __y._M_root);
}

operator==() [3/4]

template<class _CharT , class _Alloc >

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

inline

Definition at line 2131 of file _rope.h.

                                                                  {
  return (__x._M_current_pos == __y._M_current_pos &&
          __x._M_root_rope == __y._M_root_rope);
}

operator==() [4/4]

template<class _CharT , class _Alloc >

bool operator== ( const rope< _CharT, _Alloc > &  __left, const rope< _CharT, _Alloc > &  __right  )

inline

Definition at line 2246 of file _rope.h.

                                                {
  return __left.compare(__right) == 0;
}

rotate()

void rotate ( _Rope_iterator< char, allocator< char > >  __first, _Rope_iterator< char, allocator< char > >  __middle, _Rope_iterator< char, allocator< char > >  __last  )

inline

Definition at line 2355 of file _rope.h.

{ _Rope_rotate(__first, __middle, __last); }

swap()

void swap ( crope &  __x, crope &  __y  )

inline

Definition at line 2316 of file _rope.h.

{ __x.swap(__y); }