From dec00f2017a1601ab1b770b4b01e42f18d9092fc Mon Sep 17 00:00:00 2001 From: paolo Date: Sun, 27 Jun 2004 17:51:08 +0000 Subject: [PATCH] 2004-06-27 Paolo Carlini * include/ext/rope: Trivial formatting fixes. * include/ext/ropeimpl.h: Likewise. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@83737 138bc75d-0d04-0410-961f-82ee72b054a4 --- libstdc++-v3/ChangeLog | 5 + libstdc++-v3/include/ext/rope | 4672 +++++++++++++++++++---------------- libstdc++-v3/include/ext/ropeimpl.h | 2669 ++++++++++---------- 3 files changed, 3961 insertions(+), 3385 deletions(-) diff --git a/libstdc++-v3/ChangeLog b/libstdc++-v3/ChangeLog index dc4545b..8343b5e 100644 --- a/libstdc++-v3/ChangeLog +++ b/libstdc++-v3/ChangeLog @@ -1,3 +1,8 @@ +2004-06-27 Paolo Carlini + + * include/ext/rope: Trivial formatting fixes. + * include/ext/ropeimpl.h: Likewise. + 2004-06-26 Paolo Carlini PR libstdc++/16210 diff --git a/libstdc++-v3/include/ext/rope b/libstdc++-v3/include/ext/rope index 95afd82..8cfcde9 100644 --- a/libstdc++-v3/include/ext/rope +++ b/libstdc++-v3/include/ext/rope @@ -69,280 +69,364 @@ namespace __gnu_cxx { -using std::size_t; -using std::ptrdiff_t; -using std::allocator; -using std::iterator; -using std::reverse_iterator; -using std::_Destroy; - -// 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 -inline _CharT _S_eos(_CharT*) { return _CharT(); } - -// Test for basic character types. -// For basic character types leaves having a trailing eos. -template -inline bool _S_is_basic_char_type(_CharT*) { return false; } -template -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 -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 char_producer { + using std::size_t; + using std::ptrdiff_t; + using std::allocator; + using std::iterator; + using std::reverse_iterator; + using std::_Destroy; + + // 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 + inline _CharT + _S_eos(_CharT*) + { return _CharT(); } + + // Test for basic character types. + // For basic character types leaves having a trailing eos. + template + inline bool + _S_is_basic_char_type(_CharT*) + { return false; } + + template + 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 + 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 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 -// 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 and a -// little like containers. + 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. + }; -template -class sequence_buffer : public iterator -{ + // 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 + // 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 and a + // little like containers. + + template + class sequence_buffer + : public iterator + { public: - typedef typename _Sequence::value_type value_type; + typedef typename _Sequence::value_type value_type; protected: - _Sequence* _M_prefix; - value_type _M_buffer[_Buf_sz]; - size_t _M_buf_count; + _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; - for (size_t __j = 0; __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 _Rope_char_consumer { + + 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; + for (size_t __j = 0; __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 _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 rope; -template struct _Rope_RopeConcatenation; -template struct _Rope_RopeLeaf; -template struct _Rope_RopeFunction; -template struct _Rope_RopeSubstring; -template class _Rope_iterator; -template class _Rope_const_iterator; -template class _Rope_char_ref_proxy; -template class _Rope_char_ptr_proxy; - -template -bool operator== (const _Rope_char_ptr_proxy<_CharT,_Alloc>& __x, - const _Rope_char_ptr_proxy<_CharT,_Alloc>& __y); - -template -_Rope_const_iterator<_CharT,_Alloc> operator- - (const _Rope_const_iterator<_CharT,_Alloc>& __x, - ptrdiff_t __n); - -template -_Rope_const_iterator<_CharT,_Alloc> operator+ - (const _Rope_const_iterator<_CharT,_Alloc>& __x, - ptrdiff_t __n); - -template -_Rope_const_iterator<_CharT,_Alloc> operator+ - (ptrdiff_t __n, - const _Rope_const_iterator<_CharT,_Alloc>& __x); - -template -bool operator== - (const _Rope_const_iterator<_CharT,_Alloc>& __x, - const _Rope_const_iterator<_CharT,_Alloc>& __y); - -template -bool operator< - (const _Rope_const_iterator<_CharT,_Alloc>& __x, - const _Rope_const_iterator<_CharT,_Alloc>& __y); - -template -ptrdiff_t operator- - (const _Rope_const_iterator<_CharT,_Alloc>& __x, - const _Rope_const_iterator<_CharT,_Alloc>& __y); - -template -_Rope_iterator<_CharT,_Alloc> operator- - (const _Rope_iterator<_CharT,_Alloc>& __x, - ptrdiff_t __n); - -template -_Rope_iterator<_CharT,_Alloc> operator+ - (const _Rope_iterator<_CharT,_Alloc>& __x, - ptrdiff_t __n); - -template -_Rope_iterator<_CharT,_Alloc> operator+ - (ptrdiff_t __n, - const _Rope_iterator<_CharT,_Alloc>& __x); - -template -bool operator== - (const _Rope_iterator<_CharT,_Alloc>& __x, - const _Rope_iterator<_CharT,_Alloc>& __y); - -template -bool operator< - (const _Rope_iterator<_CharT,_Alloc>& __x, - const _Rope_iterator<_CharT,_Alloc>& __y); - -template -ptrdiff_t operator- - (const _Rope_iterator<_CharT,_Alloc>& __x, - const _Rope_iterator<_CharT,_Alloc>& __y); - -template -rope<_CharT,_Alloc> operator+ (const rope<_CharT,_Alloc>& __left, - const rope<_CharT,_Alloc>& __right); - -template -rope<_CharT,_Alloc> operator+ (const rope<_CharT,_Alloc>& __left, - const _CharT* __right); - -template -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 -struct _Rope_Concat_fn - : public std::binary_function, rope<_CharT,_Alloc>, - rope<_CharT,_Alloc> > { - rope<_CharT,_Alloc> operator() (const rope<_CharT,_Alloc>& __x, - const rope<_CharT,_Alloc>& __y) { - return __x + __y; - } -}; - -template -inline -rope<_CharT,_Alloc> -identity_element(_Rope_Concat_fn<_CharT, _Alloc>) -{ - return rope<_CharT,_Alloc>(); -} + // 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 rope; + + template + struct _Rope_RopeConcatenation; + + template + struct _Rope_RopeLeaf; + + template + struct _Rope_RopeFunction; + + template + struct _Rope_RopeSubstring; + + template + class _Rope_iterator; + + template + class _Rope_const_iterator; + + template + class _Rope_char_ref_proxy; + + template + class _Rope_char_ptr_proxy; + + template + bool + operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x, + const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y); + + template + _Rope_const_iterator<_CharT, _Alloc> + operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, + ptrdiff_t __n); + + template + _Rope_const_iterator<_CharT, _Alloc> + operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x, + ptrdiff_t __n); + + template + _Rope_const_iterator<_CharT, _Alloc> + operator+(ptrdiff_t __n, + const _Rope_const_iterator<_CharT, _Alloc>& __x); + + template + bool + operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x, + const _Rope_const_iterator<_CharT, _Alloc>& __y); + + template + bool + operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x, + const _Rope_const_iterator<_CharT, _Alloc>& __y); + + template + ptrdiff_t + operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, + const _Rope_const_iterator<_CharT, _Alloc>& __y); + + template + _Rope_iterator<_CharT, _Alloc> + operator-(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n); + + template + _Rope_iterator<_CharT, _Alloc> + operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n); + + template + _Rope_iterator<_CharT, _Alloc> + operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x); + + template + bool + operator==(const _Rope_iterator<_CharT, _Alloc>& __x, + const _Rope_iterator<_CharT, _Alloc>& __y); + + template + bool + operator<(const _Rope_iterator<_CharT, _Alloc>& __x, + const _Rope_iterator<_CharT, _Alloc>& __y); + + template + ptrdiff_t + operator-(const _Rope_iterator<_CharT, _Alloc>& __x, + const _Rope_iterator<_CharT, _Alloc>& __y); + + template + rope<_CharT, _Alloc> + operator+(const rope<_CharT, _Alloc>& __left, + const rope<_CharT, _Alloc>& __right); + + template + rope<_CharT, _Alloc> + operator+(const rope<_CharT, _Alloc>& __left, const _CharT* __right); + + template + 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 + struct _Rope_Concat_fn + : public std::binary_function, rope<_CharT, _Alloc>, + rope<_CharT, _Alloc> > + { + rope<_CharT, _Alloc> + operator()(const rope<_CharT, _Alloc>& __x, + const rope<_CharT, _Alloc>& __y) + { return __x + __y; } + }; + template + inline rope<_CharT, _Alloc> + identity_element(_Rope_Concat_fn<_CharT, _Alloc>) + { return rope<_CharT, _Alloc>(); } // Class _Refcount_Base provides a type, _RC_t, a data member, // _M_ref_count, and member functions _M_incr and _M_decr, which perform @@ -352,7 +436,7 @@ identity_element(_Rope_Concat_fn<_CharT, _Alloc>) { // The type _RC_t typedef size_t _RC_t; - + // The data member _M_ref_count volatile _RC_t _M_ref_count; @@ -389,30 +473,30 @@ identity_element(_Rope_Concat_fn<_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 occurrence 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. + // + // 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 occurrence 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. #define __ROPE_DEFINE_ALLOCS(__a) \ __ROPE_DEFINE_ALLOC(_CharT,_Data) /* character data */ \ @@ -425,28 +509,29 @@ identity_element(_Rope_Concat_fn<_CharT, _Alloc>) typedef _Rope_RopeSubstring<_CharT,__a> __S; \ __ROPE_DEFINE_ALLOC(__S,_S) -// Internal rope nodes potentially store a copy of the allocator -// instance used to allocate them. This is mostly redundant. -// But the alternative would be to pass allocator instances around -// in some form to nearly all internal functions, since any pointer -// assignment may result in a zero reference count and thus require -// deallocation. + // Internal rope nodes potentially store a copy of the allocator + // instance used to allocate them. This is mostly redundant. + // But the alternative would be to pass allocator instances around + // in some form to nearly all internal functions, since any pointer + // assignment may result in a zero reference count and thus require + // deallocation. #define __STATIC_IF_SGI_ALLOC /* not static */ -template -struct _Rope_rep_base -: public _Alloc -{ - typedef _Alloc allocator_type; + template + struct _Rope_rep_base + : public _Alloc + { + typedef _Alloc allocator_type; - allocator_type - get_allocator() const { return *static_cast(this); } + allocator_type + get_allocator() const + { return *static_cast(this); } - _Rope_rep_base(size_t __size, const allocator_type&) - : _M_size(__size) {} + _Rope_rep_base(size_t __size, const allocator_type&) + : _M_size(__size) {} - size_t _M_size; + size_t _M_size; # define __ROPE_DEFINE_ALLOC(_Tp, __name) \ typedef typename \ @@ -455,615 +540,726 @@ struct _Rope_rep_base { return __name##Alloc().allocate(__n); } \ static void __name##_deallocate(_Tp *__p, size_t __n) \ { __name##Alloc().deallocate(__p, __n); } - __ROPE_DEFINE_ALLOCS(_Alloc) + __ROPE_DEFINE_ALLOCS(_Alloc) # undef __ROPE_DEFINE_ALLOC -}; + }; -namespace _Rope_constants -{ - enum { _S_max_rope_depth = 45 }; - enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function}; -} + namespace _Rope_constants + { + enum { _S_max_rope_depth = 45 }; + enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function}; + } -template -struct _Rope_RopeRep : public _Rope_rep_base<_CharT,_Alloc> + template + struct _Rope_RopeRep + : public _Rope_rep_base<_CharT, _Alloc> # ifndef __GC - , _Refcount_Base + , _Refcount_Base # endif -{ + { public: - _Rope_constants::_Tag _M_tag:8; - bool _M_is_balanced:8; - unsigned char _M_depth; - __GC_CONST _CharT* _M_c_string; - __gthread_mutex_t _M_c_string_lock; + _Rope_constants::_Tag _M_tag:8; + bool _M_is_balanced:8; + unsigned char _M_depth; + __GC_CONST _CharT* _M_c_string; + __gthread_mutex_t _M_c_string_lock; /* 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. */ - typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type - allocator_type; - using _Rope_rep_base<_CharT,_Alloc>::get_allocator; - _Rope_RopeRep(_Rope_constants::_Tag __t, int __d, bool __b, size_t __size, - allocator_type __a) - : _Rope_rep_base<_CharT,_Alloc>(__size, __a), -# ifndef __GC - _Refcount_Base(1), -# endif - _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0) + typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type + allocator_type; + + using _Rope_rep_base<_CharT, _Alloc>::get_allocator; + + _Rope_RopeRep(_Rope_constants::_Tag __t, int __d, bool __b, size_t __size, + allocator_type __a) + : _Rope_rep_base<_CharT, _Alloc>(__size, __a), +#ifndef __GC + _Refcount_Base(1), +#endif + _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0) #ifdef __GTHREAD_MUTEX_INIT { - // Do not copy a POSIX/gthr mutex once in use. However, bits are bits. - __gthread_mutex_t __tmp = __GTHREAD_MUTEX_INIT; - _M_c_string_lock = __tmp; + // Do not copy a POSIX/gthr mutex once in use. However, bits are bits. + __gthread_mutex_t __tmp = __GTHREAD_MUTEX_INIT; + _M_c_string_lock = __tmp; } #else { __GTHREAD_MUTEX_INIT_FUNCTION (&_M_c_string_lock); } #endif -# ifdef __GC - void _M_incr () {} -# endif - static void _S_free_string(__GC_CONST _CharT*, size_t __len, - allocator_type __a); -# define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a); +#ifdef __GC + void + _M_incr () {} +#endif + static void + _S_free_string(__GC_CONST _CharT*, size_t __len, + allocator_type __a); +#define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a); // Deallocate data section of a leaf. // This shouldn't be a member function. // But its hard to do anything else at the // moment, because it's templatized w.r.t. // an allocator. // Does nothing if __GC is defined. -# ifndef __GC - void _M_free_c_string(); - void _M_free_tree(); - // Deallocate t. Assumes t is not 0. - void _M_unref_nonnil() - { - if (0 == _M_decr()) _M_free_tree(); - } - void _M_ref_nonnil() - { - _M_incr(); - } - static void _S_unref(_Rope_RopeRep* __t) - { - if (0 != __t) { - __t->_M_unref_nonnil(); - } - } - static void _S_ref(_Rope_RopeRep* __t) - { - if (0 != __t) __t->_M_incr(); - } - static void _S_free_if_unref(_Rope_RopeRep* __t) - { - if (0 != __t && 0 == __t->_M_ref_count) __t->_M_free_tree(); - } +#ifndef __GC + void _M_free_c_string(); + void _M_free_tree(); + // Deallocate t. Assumes t is not 0. + void + _M_unref_nonnil() + { + if (0 == _M_decr()) + _M_free_tree(); + } + + void + _M_ref_nonnil() + { _M_incr(); } + + static void + _S_unref(_Rope_RopeRep* __t) + { + if (0 != __t) + __t->_M_unref_nonnil(); + } + + static void + _S_ref(_Rope_RopeRep* __t) + { + if (0 != __t) + __t->_M_incr(); + } + + static void + _S_free_if_unref(_Rope_RopeRep* __t) + { + if (0 != __t && 0 == __t->_M_ref_count) + __t->_M_free_tree(); + } # else /* __GC */ - void _M_unref_nonnil() {} - void _M_ref_nonnil() {} - static void _S_unref(_Rope_RopeRep*) {} - static void _S_ref(_Rope_RopeRep*) {} - static void _S_free_if_unref(_Rope_RopeRep*) {} + void _M_unref_nonnil() {} + void _M_ref_nonnil() {} + static void _S_unref(_Rope_RopeRep*) {} + static void _S_ref(_Rope_RopeRep*) {} + static void _S_free_if_unref(_Rope_RopeRep*) {} # endif protected: - _Rope_RopeRep& - operator=(const _Rope_RopeRep&); + _Rope_RopeRep& + operator=(const _Rope_RopeRep&); - _Rope_RopeRep(const _Rope_RopeRep&); -}; + _Rope_RopeRep(const _Rope_RopeRep&); + }; -template -struct _Rope_RopeLeaf : public _Rope_RopeRep<_CharT,_Alloc> { - public: - // Apparently needed by VC++ - // The data fields of leaves are allocated with some - // extra space, to accommodate future growth and for basic - // character types, to hold a trailing eos character. - enum { _S_alloc_granularity = 8 }; - static size_t _S_rounded_up_size(size_t __n) { + template + struct _Rope_RopeLeaf + : public _Rope_RopeRep<_CharT, _Alloc> + { + public: + // Apparently needed by VC++ + // The data fields of leaves are allocated with some + // extra space, to accommodate future growth and for basic + // character types, to hold a trailing eos character. + enum { _S_alloc_granularity = 8 }; + + static size_t + _S_rounded_up_size(size_t __n) + { size_t __size_with_eos; + + if (_S_is_basic_char_type((_CharT*)0)) + __size_with_eos = __n + 1; + else + __size_with_eos = __n; +#ifdef __GC + return __size_with_eos; +#else + // Allow slop for in-place expansion. + return ((__size_with_eos + _S_alloc_granularity - 1) + &~ (_S_alloc_granularity - 1)); +#endif + } + __GC_CONST _CharT* _M_data; /* Not necessarily 0 terminated. */ + /* The allocated size is */ + /* _S_rounded_up_size(size), except */ + /* in the GC case, in which it */ + /* doesn't matter. */ + typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type + allocator_type; - if (_S_is_basic_char_type((_CharT*)0)) { - __size_with_eos = __n + 1; - } else { - __size_with_eos = __n; - } -# ifdef __GC - return __size_with_eos; -# else - // Allow slop for in-place expansion. - return (__size_with_eos + _S_alloc_granularity-1) - &~ (_S_alloc_granularity-1); -# endif - } - __GC_CONST _CharT* _M_data; /* Not necessarily 0 terminated. */ - /* The allocated size is */ - /* _S_rounded_up_size(size), except */ - /* in the GC case, in which it */ - /* doesn't matter. */ - typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type - allocator_type; - _Rope_RopeLeaf(__GC_CONST _CharT* __d, size_t __size, allocator_type __a) - : _Rope_RopeRep<_CharT,_Alloc>(_Rope_constants::_S_leaf, 0, true, __size, __a), _M_data(__d) - { - if (_S_is_basic_char_type((_CharT *)0)) { + _Rope_RopeLeaf(__GC_CONST _CharT* __d, size_t __size, + allocator_type __a) + : _Rope_RopeRep<_CharT, _Alloc>(_Rope_constants::_S_leaf, 0, true, + __size, __a), _M_data(__d) + { + if (_S_is_basic_char_type((_CharT *)0)) + { // already eos terminated. this->_M_c_string = __d; - } - } - // The constructor assumes that d has been allocated with - // the proper allocator and the properly padded size. - // In contrast, the destructor deallocates the data: -# ifndef __GC - ~_Rope_RopeLeaf() throw() { - if (_M_data != this->_M_c_string) { + } + } + // The constructor assumes that d has been allocated with + // the proper allocator and the properly padded size. + // In contrast, the destructor deallocates the data: +#ifndef __GC + ~_Rope_RopeLeaf() throw() + { + if (_M_data != this->_M_c_string) this->_M_free_c_string(); - } + __STL_FREE_STRING(_M_data, this->_M_size, this->get_allocator()); - } -# endif + } +#endif protected: - _Rope_RopeLeaf& - operator=(const _Rope_RopeLeaf&); + _Rope_RopeLeaf& + operator=(const _Rope_RopeLeaf&); - _Rope_RopeLeaf(const _Rope_RopeLeaf&); -}; + _Rope_RopeLeaf(const _Rope_RopeLeaf&); + }; -template -struct _Rope_RopeConcatenation : public _Rope_RopeRep<_CharT,_Alloc> { - public: - _Rope_RopeRep<_CharT,_Alloc>* _M_left; - _Rope_RopeRep<_CharT,_Alloc>* _M_right; - typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type - allocator_type; - _Rope_RopeConcatenation(_Rope_RopeRep<_CharT,_Alloc>* __l, - _Rope_RopeRep<_CharT,_Alloc>* __r, - allocator_type __a) - - : _Rope_RopeRep<_CharT,_Alloc>(_Rope_constants::_S_concat, - std::max(__l->_M_depth, __r->_M_depth) + 1, - false, - __l->_M_size + __r->_M_size, __a), + template + struct _Rope_RopeConcatenation + : public _Rope_RopeRep<_CharT, _Alloc> + { + public: + _Rope_RopeRep<_CharT, _Alloc>* _M_left; + _Rope_RopeRep<_CharT, _Alloc>* _M_right; + + typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type + allocator_type; + + _Rope_RopeConcatenation(_Rope_RopeRep<_CharT, _Alloc>* __l, + _Rope_RopeRep<_CharT, _Alloc>* __r, + allocator_type __a) + : _Rope_RopeRep<_CharT, _Alloc>(_Rope_constants::_S_concat, + std::max(__l->_M_depth, + __r->_M_depth) + 1, + false, + __l->_M_size + __r->_M_size, __a), _M_left(__l), _M_right(__r) - {} -# ifndef __GC - ~_Rope_RopeConcatenation() throw() { - this->_M_free_c_string(); - _M_left->_M_unref_nonnil(); - _M_right->_M_unref_nonnil(); - } -# endif + { } +#ifndef __GC + ~_Rope_RopeConcatenation() throw() + { + this->_M_free_c_string(); + _M_left->_M_unref_nonnil(); + _M_right->_M_unref_nonnil(); + } +#endif protected: - _Rope_RopeConcatenation& - operator=(const _Rope_RopeConcatenation&); - - _Rope_RopeConcatenation(const _Rope_RopeConcatenation&); -}; + _Rope_RopeConcatenation& + operator=(const _Rope_RopeConcatenation&); + + _Rope_RopeConcatenation(const _Rope_RopeConcatenation&); + }; -template -struct _Rope_RopeFunction : public _Rope_RopeRep<_CharT,_Alloc> { - public: - char_producer<_CharT>* _M_fn; -# ifndef __GC + template + struct _Rope_RopeFunction + : public _Rope_RopeRep<_CharT, _Alloc> + { + public: + char_producer<_CharT>* _M_fn; +#ifndef __GC bool _M_delete_when_done; // Char_producer is owned by the // rope and should be explicitly // deleted when the rope becomes // inaccessible. -# else +#else // In the GC case, we either register the rope for // finalization, or not. Thus the field is unnecessary; // the information is stored in the collector data structures. // We do need a finalization procedure to be invoked by the // collector. - static void _S_fn_finalization_proc(void * __tree, void *) { - delete ((_Rope_RopeFunction *)__tree) -> _M_fn; - } -# endif - typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type - allocator_type; - _Rope_RopeFunction(char_producer<_CharT>* __f, size_t __size, + static void + _S_fn_finalization_proc(void * __tree, void *) + { delete ((_Rope_RopeFunction *)__tree) -> _M_fn; } +#endif + typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type + allocator_type; + + _Rope_RopeFunction(char_producer<_CharT>* __f, size_t __size, bool __d, allocator_type __a) - : _Rope_RopeRep<_CharT,_Alloc>(_Rope_constants::_S_function, - 0, true, __size, __a) - , _M_fn(__f) -# ifndef __GC - , _M_delete_when_done(__d) -# endif - { -# ifdef __GC - if (__d) { - GC_REGISTER_FINALIZER( - this, _Rope_RopeFunction::_S_fn_finalization_proc, 0, 0, 0); - } -# endif - } -# ifndef __GC - ~_Rope_RopeFunction() throw() { - this->_M_free_c_string(); - if (_M_delete_when_done) { - delete _M_fn; - } - } + : _Rope_RopeRep<_CharT, _Alloc>(_Rope_constants::_S_function, + 0, true, __size, __a) + , _M_fn(__f) +#ifndef __GC + , _M_delete_when_done(__d) +#endif + { +#ifdef __GC + if (__d) + { + GC_REGISTER_FINALIZER(this, _Rope_RopeFunction:: + _S_fn_finalization_proc, 0, 0, 0); + } +#endif + } +#ifndef __GC + ~_Rope_RopeFunction() throw() + { + this->_M_free_c_string(); + if (_M_delete_when_done) + delete _M_fn; + } # endif -protected: - _Rope_RopeFunction& - operator=(const _Rope_RopeFunction&); - - _Rope_RopeFunction(const _Rope_RopeFunction&); -}; -// Substring results are usually represented using just -// concatenation nodes. But in the case of very long flat ropes -// or ropes with a functional representation that isn't practical. -// In that case, we represent the __result as a special case of -// RopeFunction, whose char_producer points back to the rope itself. -// In all cases except repeated substring operations and -// deallocation, we treat the __result as a RopeFunction. -template -struct _Rope_RopeSubstring : public _Rope_RopeFunction<_CharT,_Alloc>, - public char_producer<_CharT> { - public: - // XXX this whole class should be rewritten. - _Rope_RopeRep<_CharT,_Alloc>* _M_base; // not 0 - size_t _M_start; - virtual void operator()(size_t __start_pos, size_t __req_len, - _CharT* __buffer) { - switch(_M_base->_M_tag) { - case _Rope_constants::_S_function: - case _Rope_constants::_S_substringfn: - { - char_producer<_CharT>* __fn = - ((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn; - (*__fn)(__start_pos + _M_start, __req_len, __buffer); - } - break; - case _Rope_constants::_S_leaf: - { - __GC_CONST _CharT* __s = - ((_Rope_RopeLeaf<_CharT,_Alloc>*)_M_base)->_M_data; - uninitialized_copy_n(__s + __start_pos + _M_start, __req_len, - __buffer); - } - break; - default: - break; - } - } - typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type + protected: + _Rope_RopeFunction& + operator=(const _Rope_RopeFunction&); + + _Rope_RopeFunction(const _Rope_RopeFunction&); + }; + // Substring results are usually represented using just + // concatenation nodes. But in the case of very long flat ropes + // or ropes with a functional representation that isn't practical. + // In that case, we represent the __result as a special case of + // RopeFunction, whose char_producer points back to the rope itself. + // In all cases except repeated substring operations and + // deallocation, we treat the __result as a RopeFunction. + template + struct _Rope_RopeSubstring + : public _Rope_RopeFunction<_CharT, _Alloc>, + public char_producer<_CharT> + { + public: + // XXX this whole class should be rewritten. + _Rope_RopeRep<_CharT,_Alloc>* _M_base; // not 0 + size_t _M_start; + + virtual void + operator()(size_t __start_pos, size_t __req_len, + _CharT* __buffer) + { + switch(_M_base->_M_tag) + { + case _Rope_constants::_S_function: + case _Rope_constants::_S_substringfn: + { + char_producer<_CharT>* __fn = + ((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn; + (*__fn)(__start_pos + _M_start, __req_len, __buffer); + } + break; + case _Rope_constants::_S_leaf: + { + __GC_CONST _CharT* __s = + ((_Rope_RopeLeaf<_CharT,_Alloc>*)_M_base)->_M_data; + uninitialized_copy_n(__s + __start_pos + _M_start, __req_len, + __buffer); + } + break; + default: + break; + } + } + + typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type allocator_type; - _Rope_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s, + + _Rope_RopeSubstring(_Rope_RopeRep<_CharT, _Alloc>* __b, size_t __s, size_t __l, allocator_type __a) - : _Rope_RopeFunction<_CharT,_Alloc>(this, __l, false, __a), - char_producer<_CharT>(), - _M_base(__b), - _M_start(__s) - { -# ifndef __GC - _M_base->_M_ref_nonnil(); -# endif + : _Rope_RopeFunction<_CharT, _Alloc>(this, __l, false, __a), + char_producer<_CharT>(), _M_base(__b), _M_start(__s) + { +#ifndef __GC + _M_base->_M_ref_nonnil(); +#endif this->_M_tag = _Rope_constants::_S_substringfn; - } + } virtual ~_Rope_RopeSubstring() throw() { -# ifndef __GC - _M_base->_M_unref_nonnil(); - // _M_free_c_string(); -- done by parent class -# endif +#ifndef __GC + _M_base->_M_unref_nonnil(); + // _M_free_c_string(); -- done by parent class +#endif } -}; - + }; -// Self-destructing pointers to Rope_rep. -// These are not conventional smart pointers. Their -// only purpose in life is to ensure that unref is called -// on the pointer either at normal exit or if an exception -// is raised. It is the caller's responsibility to -// adjust reference counts when these pointers are initialized -// or assigned to. (This convention significantly reduces -// the number of potentially expensive reference count -// updates.) + // Self-destructing pointers to Rope_rep. + // These are not conventional smart pointers. Their + // only purpose in life is to ensure that unref is called + // on the pointer either at normal exit or if an exception + // is raised. It is the caller's responsibility to + // adjust reference counts when these pointers are initialized + // or assigned to. (This convention significantly reduces + // the number of potentially expensive reference count + // updates.) #ifndef __GC template - struct _Rope_self_destruct_ptr { - _Rope_RopeRep<_CharT,_Alloc>* _M_ptr; - ~_Rope_self_destruct_ptr() - { _Rope_RopeRep<_CharT,_Alloc>::_S_unref(_M_ptr); } + struct _Rope_self_destruct_ptr + { + _Rope_RopeRep<_CharT, _Alloc>* _M_ptr; + + ~_Rope_self_destruct_ptr() + { _Rope_RopeRep<_CharT, _Alloc>::_S_unref(_M_ptr); } #ifdef __EXCEPTIONS - _Rope_self_destruct_ptr() : _M_ptr(0) {}; + _Rope_self_destruct_ptr() : _M_ptr(0) {}; #else - _Rope_self_destruct_ptr() {}; + _Rope_self_destruct_ptr() {}; #endif - _Rope_self_destruct_ptr(_Rope_RopeRep<_CharT,_Alloc>* __p) : _M_ptr(__p) {} - _Rope_RopeRep<_CharT,_Alloc>& operator*() { return *_M_ptr; } - _Rope_RopeRep<_CharT,_Alloc>* operator->() { return _M_ptr; } - operator _Rope_RopeRep<_CharT,_Alloc>*() { return _M_ptr; } - _Rope_self_destruct_ptr& operator= (_Rope_RopeRep<_CharT,_Alloc>* __x) - { _M_ptr = __x; return *this; } - }; + _Rope_self_destruct_ptr(_Rope_RopeRep<_CharT, _Alloc>* __p) + : _M_ptr(__p) {} + + _Rope_RopeRep<_CharT, _Alloc>& + operator*() + { return *_M_ptr; } + + _Rope_RopeRep<_CharT, _Alloc>* + operator->() + { return _M_ptr; } + + operator _Rope_RopeRep<_CharT, _Alloc>*() + { return _M_ptr; } + + _Rope_self_destruct_ptr& + operator=(_Rope_RopeRep<_CharT, _Alloc>* __x) + { _M_ptr = __x; return *this; } + }; #endif -// Dereferencing a nonconst iterator has to return something -// that behaves almost like a reference. It's not possible to -// return an actual reference since assignment requires extra -// work. And we would get into the same problems as with the -// CD2 version of basic_string. -template -class _Rope_char_ref_proxy { - friend class rope<_CharT,_Alloc>; - friend class _Rope_iterator<_CharT,_Alloc>; - friend class _Rope_char_ptr_proxy<_CharT,_Alloc>; -# ifdef __GC - typedef _Rope_RopeRep<_CharT,_Alloc>* _Self_destruct_ptr; -# else - typedef _Rope_self_destruct_ptr<_CharT,_Alloc> _Self_destruct_ptr; -# endif - typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep; - typedef rope<_CharT,_Alloc> _My_rope; - size_t _M_pos; - _CharT _M_current; - bool _M_current_valid; - _My_rope* _M_root; // The whole rope. - public: - _Rope_char_ref_proxy(_My_rope* __r, size_t __p) - : _M_pos(__p), _M_current(), _M_current_valid(false), _M_root(__r) {} - - _Rope_char_ref_proxy(const _Rope_char_ref_proxy& __x) - : _M_pos(__x._M_pos), _M_current(__x._M_current), _M_current_valid(false), - _M_root(__x._M_root) {} - - // Don't preserve cache if the reference can outlive the - // expression. We claim that's not possible without calling - // a copy constructor or generating reference to a proxy - // reference. We declare the latter to have undefined semantics. - _Rope_char_ref_proxy(_My_rope* __r, size_t __p, _CharT __c) + // Dereferencing a nonconst iterator has to return something + // that behaves almost like a reference. It's not possible to + // return an actual reference since assignment requires extra + // work. And we would get into the same problems as with the + // CD2 version of basic_string. + template + class _Rope_char_ref_proxy + { + friend class rope<_CharT, _Alloc>; + friend class _Rope_iterator<_CharT, _Alloc>; + friend class _Rope_char_ptr_proxy<_CharT, _Alloc>; +#ifdef __GC + typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr; +#else + typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr; +#endif + typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep; + typedef rope<_CharT, _Alloc> _My_rope; + size_t _M_pos; + _CharT _M_current; + bool _M_current_valid; + _My_rope* _M_root; // The whole rope. + public: + _Rope_char_ref_proxy(_My_rope* __r, size_t __p) + : _M_pos(__p), _M_current(), _M_current_valid(false), _M_root(__r) {} + + _Rope_char_ref_proxy(const _Rope_char_ref_proxy& __x) + : _M_pos(__x._M_pos), _M_current(__x._M_current), _M_current_valid(false), + _M_root(__x._M_root) {} + + // Don't preserve cache if the reference can outlive the + // expression. We claim that's not possible without calling + // a copy constructor or generating reference to a proxy + // reference. We declare the latter to have undefined semantics. + _Rope_char_ref_proxy(_My_rope* __r, size_t __p, _CharT __c) : _M_pos(__p), _M_current(__c), _M_current_valid(true), _M_root(__r) {} - inline operator _CharT () const; - _Rope_char_ref_proxy& operator= (_CharT __c); - _Rope_char_ptr_proxy<_CharT,_Alloc> operator& () const; - _Rope_char_ref_proxy& operator= (const _Rope_char_ref_proxy& __c) { - return operator=((_CharT)__c); + + inline operator _CharT () const; + + _Rope_char_ref_proxy& + operator=(_CharT __c); + + _Rope_char_ptr_proxy<_CharT, _Alloc> operator&() const; + + _Rope_char_ref_proxy& + operator=(const _Rope_char_ref_proxy& __c) + { return operator=((_CharT)__c); } + }; + + template + inline void + swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a, + _Rope_char_ref_proxy <_CharT, __Alloc > __b) + { + _CharT __tmp = __a; + __a = __b; + __b = __tmp; } -}; - -template -inline void swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a, - _Rope_char_ref_proxy <_CharT, __Alloc > __b) { - _CharT __tmp = __a; - __a = __b; - __b = __tmp; -} - -template -class _Rope_char_ptr_proxy { - // XXX this class should be rewritten. - friend class _Rope_char_ref_proxy<_CharT,_Alloc>; - size_t _M_pos; - rope<_CharT,_Alloc>* _M_root; // The whole rope. - public: - _Rope_char_ptr_proxy(const _Rope_char_ref_proxy<_CharT,_Alloc>& __x) + + template + class _Rope_char_ptr_proxy + { + // XXX this class should be rewritten. + friend class _Rope_char_ref_proxy<_CharT, _Alloc>; + size_t _M_pos; + rope<_CharT,_Alloc>* _M_root; // The whole rope. + public: + _Rope_char_ptr_proxy(const _Rope_char_ref_proxy<_CharT,_Alloc>& __x) : _M_pos(__x._M_pos), _M_root(__x._M_root) {} - _Rope_char_ptr_proxy(const _Rope_char_ptr_proxy& __x) + + _Rope_char_ptr_proxy(const _Rope_char_ptr_proxy& __x) : _M_pos(__x._M_pos), _M_root(__x._M_root) {} - _Rope_char_ptr_proxy() {} - _Rope_char_ptr_proxy(_CharT* __x) : _M_root(0), _M_pos(0) { - } - _Rope_char_ptr_proxy& - operator= (const _Rope_char_ptr_proxy& __x) { + + _Rope_char_ptr_proxy() {} + + _Rope_char_ptr_proxy(_CharT* __x) + : _M_root(0), _M_pos(0) { } + + _Rope_char_ptr_proxy& + operator=(const _Rope_char_ptr_proxy& __x) + { _M_pos = __x._M_pos; _M_root = __x._M_root; return *this; - } - template - friend bool operator== (const _Rope_char_ptr_proxy<_CharT2,_Alloc2>& __x, - const _Rope_char_ptr_proxy<_CharT2,_Alloc2>& __y); - _Rope_char_ref_proxy<_CharT,_Alloc> operator*() const { - return _Rope_char_ref_proxy<_CharT,_Alloc>(_M_root, _M_pos); - } -}; + } + template + friend bool + operator==(const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __x, + const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __y); -// Rope iterators: -// Unlike in the C version, we cache only part of the stack -// for rope iterators, since they must be efficiently copyable. -// When we run out of cache, we have to reconstruct the iterator -// value. -// Pointers from iterators are not included in reference counts. -// Iterators are assumed to be thread private. Ropes can -// be shared. + _Rope_char_ref_proxy<_CharT, _Alloc> operator*() const + { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root, _M_pos); } + }; -template -class _Rope_iterator_base - : public iterator -{ - friend class rope<_CharT,_Alloc>; - public: - typedef _Alloc _allocator_type; // used in _Rope_rotate, VC++ workaround - typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep; - // Borland doesn't want this to be protected. - protected: - enum { _S_path_cache_len = 4 }; // Must be <= 9. - enum { _S_iterator_buf_len = 15 }; - size_t _M_current_pos; - _RopeRep* _M_root; // The whole rope. - size_t _M_leaf_pos; // Starting position for current leaf - __GC_CONST _CharT* _M_buf_start; - // Buffer possibly - // containing current char. - __GC_CONST _CharT* _M_buf_ptr; - // Pointer to current char in buffer. - // != 0 ==> buffer valid. - __GC_CONST _CharT* _M_buf_end; - // One past __last valid char in buffer. - // What follows is the path cache. We go out of our - // way to make this compact. - // Path_end contains the bottom section of the path from - // the root to the current leaf. - const _RopeRep* _M_path_end[_S_path_cache_len]; - int _M_leaf_index; // Last valid __pos in path_end; - // _M_path_end[0] ... _M_path_end[leaf_index-1] - // point to concatenation nodes. - unsigned char _M_path_directions; + // Rope iterators: + // Unlike in the C version, we cache only part of the stack + // for rope iterators, since they must be efficiently copyable. + // When we run out of cache, we have to reconstruct the iterator + // value. + // Pointers from iterators are not included in reference counts. + // Iterators are assumed to be thread private. Ropes can + // be shared. + + template + class _Rope_iterator_base + : public iterator + { + friend class rope<_CharT, _Alloc>; + public: + typedef _Alloc _allocator_type; // used in _Rope_rotate, VC++ workaround + typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep; + // Borland doesn't want this to be protected. + protected: + enum { _S_path_cache_len = 4 }; // Must be <= 9. + enum { _S_iterator_buf_len = 15 }; + size_t _M_current_pos; + _RopeRep* _M_root; // The whole rope. + size_t _M_leaf_pos; // Starting position for current leaf + __GC_CONST _CharT* _M_buf_start; + // Buffer possibly + // containing current char. + __GC_CONST _CharT* _M_buf_ptr; + // Pointer to current char in buffer. + // != 0 ==> buffer valid. + __GC_CONST _CharT* _M_buf_end; + // One past __last valid char in buffer. + // What follows is the path cache. We go out of our + // way to make this compact. + // Path_end contains the bottom section of the path from + // the root to the current leaf. + const _RopeRep* _M_path_end[_S_path_cache_len]; + int _M_leaf_index; // Last valid __pos in path_end; + // _M_path_end[0] ... _M_path_end[leaf_index-1] + // point to concatenation nodes. + unsigned char _M_path_directions; // (path_directions >> __i) & 1 is 1 // iff we got from _M_path_end[leaf_index - __i - 1] // to _M_path_end[leaf_index - __i] by going to the // __right. Assumes path_cache_len <= 9. - _CharT _M_tmp_buf[_S_iterator_buf_len]; + _CharT _M_tmp_buf[_S_iterator_buf_len]; // Short buffer for surrounding chars. // This is useful primarily for // RopeFunctions. We put the buffer // here to avoid locking in the // multithreaded case. - // The cached path is generally assumed to be valid - // only if the buffer is valid. - static void _S_setbuf(_Rope_iterator_base& __x); + // The cached path is generally assumed to be valid + // only if the buffer is valid. + static void _S_setbuf(_Rope_iterator_base& __x); // Set buffer contents given // path cache. - static void _S_setcache(_Rope_iterator_base& __x); + static void _S_setcache(_Rope_iterator_base& __x); // Set buffer contents and // path cache. - static void _S_setcache_for_incr(_Rope_iterator_base& __x); + static void _S_setcache_for_incr(_Rope_iterator_base& __x); // As above, but assumes path // cache is valid for previous posn. - _Rope_iterator_base() {} - _Rope_iterator_base(_RopeRep* __root, size_t __pos) + _Rope_iterator_base() {} + + _Rope_iterator_base(_RopeRep* __root, size_t __pos) : _M_current_pos(__pos), _M_root(__root), _M_buf_ptr(0) {} - void _M_incr(size_t __n); - void _M_decr(size_t __n); - public: - size_t index() const { return _M_current_pos; } - _Rope_iterator_base(const _Rope_iterator_base& __x) { - if (0 != __x._M_buf_ptr) { - *this = __x; - } else { + + void _M_incr(size_t __n); + void _M_decr(size_t __n); + public: + size_t + index() const + { return _M_current_pos; } + + _Rope_iterator_base(const _Rope_iterator_base& __x) + { + if (0 != __x._M_buf_ptr) + *this = __x; + else + { _M_current_pos = __x._M_current_pos; _M_root = __x._M_root; _M_buf_ptr = 0; - } - } -}; + } + } + }; -template class _Rope_iterator; + template + class _Rope_iterator; -template -class _Rope_const_iterator : public _Rope_iterator_base<_CharT,_Alloc> { - friend class rope<_CharT,_Alloc>; - protected: - typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep; + template + class _Rope_const_iterator + : public _Rope_iterator_base<_CharT, _Alloc> + { + friend class rope<_CharT, _Alloc>; + protected: + typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep; // The one from the base class may not be directly visible. - _Rope_const_iterator(const _RopeRep* __root, size_t __pos): - _Rope_iterator_base<_CharT,_Alloc>( - const_cast<_RopeRep*>(__root), __pos) + _Rope_const_iterator(const _RopeRep* __root, size_t __pos) + : _Rope_iterator_base<_CharT, _Alloc>(const_cast<_RopeRep*>(__root), + __pos) // Only nonconst iterators modify root ref count - {} + {} public: - typedef _CharT reference; // Really a value. Returning a reference - // Would be a mess, since it would have - // to be included in refcount. - typedef const _CharT* pointer; + typedef _CharT reference; // Really a value. Returning a reference + // Would be a mess, since it would have + // to be included in refcount. + typedef const _CharT* pointer; - public: - _Rope_const_iterator() {}; - _Rope_const_iterator(const _Rope_const_iterator& __x) : - _Rope_iterator_base<_CharT,_Alloc>(__x) { } - _Rope_const_iterator(const _Rope_iterator<_CharT,_Alloc>& __x); - _Rope_const_iterator(const rope<_CharT,_Alloc>& __r, size_t __pos) : - _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos) {} - _Rope_const_iterator& operator= (const _Rope_const_iterator& __x) { - if (0 != __x._M_buf_ptr) { - *(static_cast<_Rope_iterator_base<_CharT,_Alloc>*>(this)) = __x; - } else { + public: + _Rope_const_iterator() {}; + + _Rope_const_iterator(const _Rope_const_iterator& __x) + : _Rope_iterator_base<_CharT,_Alloc>(__x) { } + + _Rope_const_iterator(const _Rope_iterator<_CharT,_Alloc>& __x); + + _Rope_const_iterator(const rope<_CharT, _Alloc>& __r, size_t __pos) + : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos) { } + + _Rope_const_iterator& + operator=(const _Rope_const_iterator& __x) + { + if (0 != __x._M_buf_ptr) + *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x; + else + { this->_M_current_pos = __x._M_current_pos; this->_M_root = __x._M_root; this->_M_buf_ptr = 0; - } + } return(*this); - } - reference operator*() { - if (0 == this->_M_buf_ptr) _S_setcache(*this); + } + + reference + operator*() + { + if (0 == this->_M_buf_ptr) + _S_setcache(*this); return *this->_M_buf_ptr; - } - _Rope_const_iterator& operator++() { + } + + _Rope_const_iterator& + operator++() + { __GC_CONST _CharT* __next; if (0 != this->_M_buf_ptr - && (__next = this->_M_buf_ptr + 1) < this->_M_buf_end) { + && (__next = this->_M_buf_ptr + 1) < this->_M_buf_end) + { this->_M_buf_ptr = __next; ++this->_M_current_pos; - } else { - this->_M_incr(1); - } - return *this; - } - _Rope_const_iterator& operator+=(ptrdiff_t __n) { - if (__n >= 0) { - this->_M_incr(__n); - } else { - this->_M_decr(-__n); - } - return *this; - } - _Rope_const_iterator& operator--() { + } + else + this->_M_incr(1); + return *this; + } + + _Rope_const_iterator& + operator+=(ptrdiff_t __n) + { + if (__n >= 0) + this->_M_incr(__n); + else + this->_M_decr(-__n); + return *this; + } + + _Rope_const_iterator& + operator--() + { this->_M_decr(1); return *this; - } - _Rope_const_iterator& operator-=(ptrdiff_t __n) { - if (__n >= 0) { - this->_M_decr(__n); - } else { - this->_M_incr(-__n); - } - return *this; - } - _Rope_const_iterator operator++(int) { + } + + _Rope_const_iterator& + operator-=(ptrdiff_t __n) + { + if (__n >= 0) + this->_M_decr(__n); + else + this->_M_incr(-__n); + return *this; + } + + _Rope_const_iterator + operator++(int) + { size_t __old_pos = this->_M_current_pos; this->_M_incr(1); return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos); // This makes a subsequent dereference expensive. // Perhaps we should instead copy the iterator // if it has a valid cache? - } - _Rope_const_iterator operator--(int) { + } + + _Rope_const_iterator + operator--(int) + { size_t __old_pos = this->_M_current_pos; this->_M_decr(1); return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos); - } - template - friend _Rope_const_iterator<_CharT2,_Alloc2> operator- - (const _Rope_const_iterator<_CharT2,_Alloc2>& __x, - ptrdiff_t __n); - template - friend _Rope_const_iterator<_CharT2,_Alloc2> operator+ - (const _Rope_const_iterator<_CharT2,_Alloc2>& __x, - ptrdiff_t __n); - template - friend _Rope_const_iterator<_CharT2,_Alloc2> operator+ - (ptrdiff_t __n, - const _Rope_const_iterator<_CharT2,_Alloc2>& __x); - reference operator[](size_t __n) { - return rope<_CharT,_Alloc>::_S_fetch(this->_M_root, - this->_M_current_pos + __n); - } + } + + template + friend _Rope_const_iterator<_CharT2, _Alloc2> + operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x, + ptrdiff_t __n); + + template + friend _Rope_const_iterator<_CharT2, _Alloc2> + operator+(const _Rope_const_iterator<_CharT2, _Alloc2>& __x, + ptrdiff_t __n); + + template + friend _Rope_const_iterator<_CharT2, _Alloc2> + operator+(ptrdiff_t __n, + const _Rope_const_iterator<_CharT2, _Alloc2>& __x); + + reference + operator[](size_t __n) + { return rope<_CharT, _Alloc>::_S_fetch(this->_M_root, + this->_M_current_pos + __n); } + + template + friend bool + operator==(const _Rope_const_iterator<_CharT2, _Alloc2>& __x, + const _Rope_const_iterator<_CharT2, _Alloc2>& __y); + + template + friend bool + operator<(const _Rope_const_iterator<_CharT2, _Alloc2>& __x, + const _Rope_const_iterator<_CharT2, _Alloc2>& __y); + + template + friend ptrdiff_t + operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x, + const _Rope_const_iterator<_CharT2, _Alloc2>& __y); + }; - template - friend bool operator== - (const _Rope_const_iterator<_CharT2,_Alloc2>& __x, - const _Rope_const_iterator<_CharT2,_Alloc2>& __y); - template - friend bool operator< - (const _Rope_const_iterator<_CharT2,_Alloc2>& __x, - const _Rope_const_iterator<_CharT2,_Alloc2>& __y); - template - friend ptrdiff_t operator- - (const _Rope_const_iterator<_CharT2,_Alloc2>& __x, - const _Rope_const_iterator<_CharT2,_Alloc2>& __y); -}; - -template -class _Rope_iterator : public _Rope_iterator_base<_CharT,_Alloc> { - friend class rope<_CharT,_Alloc>; - protected: - typedef typename _Rope_iterator_base<_CharT,_Alloc>::_RopeRep _RopeRep; - rope<_CharT,_Alloc>* _M_root_rope; + template + class _Rope_iterator + : public _Rope_iterator_base<_CharT, _Alloc> + { + friend class rope<_CharT, _Alloc>; + protected: + typedef typename _Rope_iterator_base<_CharT, _Alloc>::_RopeRep _RopeRep; + rope<_CharT, _Alloc>* _M_root_rope; // root is treated as a cached version of this, // and is used to detect changes to the underlying // rope. @@ -1071,1421 +1267,1633 @@ class _Rope_iterator : public _Rope_iterator_base<_CharT,_Alloc> { // This is necessary so that we can detect changes reliably. // Unfortunately, it requires careful bookkeeping for the // nonGC case. - _Rope_iterator(rope<_CharT,_Alloc>* __r, size_t __pos) - : _Rope_iterator_base<_CharT,_Alloc>(__r->_M_tree_ptr, __pos), + _Rope_iterator(rope<_CharT, _Alloc>* __r, size_t __pos) + : _Rope_iterator_base<_CharT, _Alloc>(__r->_M_tree_ptr, __pos), _M_root_rope(__r) { _RopeRep::_S_ref(this->_M_root); - if (!(__r -> empty()))_S_setcache(*this); } + if (!(__r -> empty())) + _S_setcache(*this); + } - void _M_check(); - public: - typedef _Rope_char_ref_proxy<_CharT,_Alloc> reference; - typedef _Rope_char_ref_proxy<_CharT,_Alloc>* pointer; + void _M_check(); + public: + typedef _Rope_char_ref_proxy<_CharT, _Alloc> reference; + typedef _Rope_char_ref_proxy<_CharT, _Alloc>* pointer; - public: - rope<_CharT,_Alloc>& container() { return *_M_root_rope; } - _Rope_iterator() { + public: + rope<_CharT, _Alloc>& + container() + { return *_M_root_rope; } + + _Rope_iterator() + { this->_M_root = 0; // Needed for reference counting. - }; - _Rope_iterator(const _Rope_iterator& __x) : - _Rope_iterator_base<_CharT,_Alloc>(__x) { + }; + + _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; + } + + _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) { + if (0 != __x._M_buf_ptr) + { _M_root_rope = __x._M_root_rope; - *(static_cast<_Rope_iterator_base<_CharT,_Alloc>*>(this)) = __x; - } else { + *(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*() { + } + + 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++() { + 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--() { + } + + _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) { + } + + _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) { + } + + _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 - friend bool operator== - (const _Rope_iterator<_CharT2,_Alloc2>& __x, - const _Rope_iterator<_CharT2,_Alloc2>& __y); - template - friend bool operator< - (const _Rope_iterator<_CharT2,_Alloc2>& __x, - const _Rope_iterator<_CharT2,_Alloc2>& __y); - template - friend ptrdiff_t operator- - (const _Rope_iterator<_CharT2,_Alloc2>& __x, - const _Rope_iterator<_CharT2,_Alloc2>& __y); - template - friend _Rope_iterator<_CharT2,_Alloc2> operator- - (const _Rope_iterator<_CharT2,_Alloc2>& __x, - ptrdiff_t __n); - template - friend _Rope_iterator<_CharT2,_Alloc2> operator+ - (const _Rope_iterator<_CharT2,_Alloc2>& __x, - ptrdiff_t __n); - template - friend _Rope_iterator<_CharT2,_Alloc2> operator+ - (ptrdiff_t __n, - const _Rope_iterator<_CharT2,_Alloc2>& __x); -}; - - -template -struct _Rope_base -: public _Alloc -{ - typedef _Alloc allocator_type; + reference + operator[](ptrdiff_t __n) + { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope, + this->_M_current_pos + + __n); } + + template + friend bool + operator==(const _Rope_iterator<_CharT2, _Alloc2>& __x, + const _Rope_iterator<_CharT2, _Alloc2>& __y); + + template + friend bool + operator<(const _Rope_iterator<_CharT2, _Alloc2>& __x, + const _Rope_iterator<_CharT2, _Alloc2>& __y); + + template + friend ptrdiff_t + operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x, + const _Rope_iterator<_CharT2, _Alloc2>& __y); + + template + friend _Rope_iterator<_CharT2, _Alloc2> + operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n); + + template + friend _Rope_iterator<_CharT2, _Alloc2> + operator+(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n); + + template + friend _Rope_iterator<_CharT2, _Alloc2> + operator+(ptrdiff_t __n, const _Rope_iterator<_CharT2, _Alloc2>& __x); + }; - allocator_type - get_allocator() const { return *static_cast(this); } - typedef _Rope_RopeRep<_CharT,_Alloc> _RopeRep; - // The one in _Base may not be visible due to template rules. + template + struct _Rope_base + : public _Alloc + { + typedef _Alloc allocator_type; - _Rope_base(_RopeRep* __t, const allocator_type&) - : _M_tree_ptr(__t) {} - _Rope_base(const allocator_type&) {} + allocator_type + get_allocator() const + { return *static_cast(this); } - // The only data member of a rope: - _RopeRep *_M_tree_ptr; + typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep; + // The one in _Base may not be visible due to template rules. -# define __ROPE_DEFINE_ALLOC(_Tp, __name) \ + _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 + __ROPE_DEFINE_ALLOCS(_Alloc) +#undef __ROPE_DEFINE_ALLOC + + protected: + _Rope_base& + operator=(const _Rope_base&); + + _Rope_base(const _Rope_base&); + }; -protected: - _Rope_base& - operator=(const _Rope_base&); + /** + * This is an SGI extension. + * @ingroup SGIextensions + * @doctodo + */ + template + 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>; - _Rope_base(const _Rope_base&); -}; + 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; -/** - * This is an SGI extension. - * @ingroup SGIextensions - * @doctodo -*/ -template -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>; + // Retrieve a character at the indicated position. + static _CharT _S_fetch(_RopeRep* __r, size_type __pos); - 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; +#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 _CharT _S_empty_c_str[1]; + 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. - 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. +#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 - 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, +#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. + 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 - 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); - } + 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) \ + 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(__s, __size, __buf); - _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* _S_concat_and_set_balanced(_RopeRep* __left, - _RopeRep* __right) - { - _RopeRep* __result = _S_concat(__left, __right); - if (_S_is_balanced(__result)) __result->_M_is_balanced = true; - return __result; - } - - // The basic rebalancing operation. Logically copies the - // rope. The result has refcount of 1. The client will - // usually decrement the reference count of __r. - // The result is within height 2 of balanced by the above - // definition. - static _RopeRep* _S_balance(_RopeRep* __r); - - // Add all unbalanced subtrees to the forest of balanceed trees. - // Used only by balance. - static void _S_add_to_forest(_RopeRep*__r, _RopeRep** __forest); - - // Add __r to forest, assuming __r is already balanced. - static void _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest); - - // Print to stdout, exposing structure - static void _S_dump(_RopeRep* __r, int __indent = 0); - - // Return -1, 0, or 1 if __x < __y, __x == __y, or __x > __y resp. - static int _S_compare(const _RopeRep* __x, const _RopeRep* __y); + { + if (0 == __size) + return 0; + _CharT* __buf = __a.allocate(_S_rounded_up_size(__size)); + + uninitialized_copy_n(__s, __size, __buf); + _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; + } + } - public: - bool empty() const { return 0 == this->_M_tree_ptr; } - - // Comparison member function. This is public only for those - // clients that need a ternary comparison. Others - // should use the comparison operators below. - int compare(const rope& __y) const { - return _S_compare(this->_M_tree_ptr, __y._M_tree_ptr); - } - - rope(const _CharT* __s, const allocator_type& __a = allocator_type()) - : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, _S_char_ptr_len(__s), - __a),__a) - { } - - rope(const _CharT* __s, size_t __len, - const allocator_type& __a = allocator_type()) - : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __len, __a), __a) - { } - - // Should perhaps be templatized with respect to the iterator type - // and use Sequence_buffer. (It should perhaps use sequence_buffer - // even now.) - rope(const _CharT *__s, const _CharT *__e, - const allocator_type& __a = allocator_type()) - : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __e - __s, __a), __a) - { } - - rope(const const_iterator& __s, const const_iterator& __e, - const allocator_type& __a = allocator_type()) - : _Base(_S_substring(__s._M_root, __s._M_current_pos, - __e._M_current_pos), __a) - { } - - rope(const iterator& __s, const iterator& __e, - const allocator_type& __a = allocator_type()) - : _Base(_S_substring(__s._M_root, __s._M_current_pos, - __e._M_current_pos), __a) - { } - - rope(_CharT __c, const allocator_type& __a = allocator_type()) - : _Base(__a) - { - _CharT* __buf = this->_Data_allocate(_S_rounded_up_size(1)); - - std::_Construct(__buf, __c); - try { - this->_M_tree_ptr = _S_new_RopeLeaf(__buf, 1, __a); - } - catch(...) - { - _RopeRep::__STL_FREE_STRING(__buf, 1, __a); - __throw_exception_again; - } - } - - rope(size_t __n, _CharT __c, - const allocator_type& __a = allocator_type()); - - rope(const allocator_type& __a = allocator_type()) - : _Base(0, __a) {} + // 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* + _S_concat_and_set_balanced(_RopeRep* __left, _RopeRep* __right) + { + _RopeRep* __result = _S_concat(__left, __right); + if (_S_is_balanced(__result)) + __result->_M_is_balanced = true; + return __result; + } + + // The basic rebalancing operation. Logically copies the + // rope. The result has refcount of 1. The client will + // usually decrement the reference count of __r. + // The result is within height 2 of balanced by the above + // definition. + static _RopeRep* _S_balance(_RopeRep* __r); + + // Add all unbalanced subtrees to the forest of balanceed trees. + // Used only by balance. + static void _S_add_to_forest(_RopeRep*__r, _RopeRep** __forest); + + // Add __r to forest, assuming __r is already balanced. + static void _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest); + + // Print to stdout, exposing structure + static void _S_dump(_RopeRep* __r, int __indent = 0); + + // Return -1, 0, or 1 if __x < __y, __x == __y, or __x > __y resp. + static int _S_compare(const _RopeRep* __x, const _RopeRep* __y); + + public: + bool + empty() const + { return 0 == this->_M_tree_ptr; } + + // Comparison member function. This is public only for those + // clients that need a ternary comparison. Others + // should use the comparison operators below. + int + compare(const rope& __y) const + { return _S_compare(this->_M_tree_ptr, __y._M_tree_ptr); } + + rope(const _CharT* __s, const allocator_type& __a = allocator_type()) + : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, _S_char_ptr_len(__s), + __a), __a) + { } + + rope(const _CharT* __s, size_t __len, + const allocator_type& __a = allocator_type()) + : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __len, __a), __a) + { } + + // Should perhaps be templatized with respect to the iterator type + // and use Sequence_buffer. (It should perhaps use sequence_buffer + // even now.) + rope(const _CharT *__s, const _CharT *__e, + const allocator_type& __a = allocator_type()) + : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __e - __s, __a), __a) + { } + + rope(const const_iterator& __s, const const_iterator& __e, + const allocator_type& __a = allocator_type()) + : _Base(_S_substring(__s._M_root, __s._M_current_pos, + __e._M_current_pos), __a) + { } + + rope(const iterator& __s, const iterator& __e, + const allocator_type& __a = allocator_type()) + : _Base(_S_substring(__s._M_root, __s._M_current_pos, + __e._M_current_pos), __a) + { } + + rope(_CharT __c, const allocator_type& __a = allocator_type()) + : _Base(__a) + { + _CharT* __buf = this->_Data_allocate(_S_rounded_up_size(1)); + + std::_Construct(__buf, __c); + try + { this->_M_tree_ptr = _S_new_RopeLeaf(__buf, 1, __a); } + catch(...) + { + _RopeRep::__STL_FREE_STRING(__buf, 1, __a); + __throw_exception_again; + } + } + + rope(size_t __n, _CharT __c, + const allocator_type& __a = allocator_type()); + + rope(const allocator_type& __a = allocator_type()) + : _Base(0, __a) {} // Construct a rope from a function that can compute its members - rope(char_producer<_CharT> *__fn, size_t __len, bool __delete_fn, - const allocator_type& __a = allocator_type()) - : _Base(__a) - { - this->_M_tree_ptr = (0 == __len) ? - 0 : _S_new_RopeFunction(__fn, __len, __delete_fn, __a); - } - - rope(const rope& __x, const allocator_type& __a = allocator_type()) - : _Base(__x._M_tree_ptr, __a) - { - _S_ref(this->_M_tree_ptr); - } + rope(char_producer<_CharT> *__fn, size_t __len, bool __delete_fn, + const allocator_type& __a = allocator_type()) + : _Base(__a) + { + this->_M_tree_ptr = (0 == __len) ? + 0 : _S_new_RopeFunction(__fn, __len, __delete_fn, __a); + } + + rope(const rope& __x, const allocator_type& __a = allocator_type()) + : _Base(__x._M_tree_ptr, __a) + { _S_ref(this->_M_tree_ptr); } ~rope() throw() - { _S_unref(this->_M_tree_ptr); } - - rope& operator=(const rope& __x) - { - _RopeRep* __old = this->_M_tree_ptr; - this->_M_tree_ptr = __x._M_tree_ptr; - _S_ref(this->_M_tree_ptr); - _S_unref(__old); - return *this; - } - - void clear() - { - _S_unref(this->_M_tree_ptr); - this->_M_tree_ptr = 0; - } - - void push_back(_CharT __x) - { - _RopeRep* __old = this->_M_tree_ptr; - this->_M_tree_ptr - = _S_destr_concat_char_iter(this->_M_tree_ptr, &__x, 1); - _S_unref(__old); - } - - void pop_back() - { - _RopeRep* __old = this->_M_tree_ptr; - this->_M_tree_ptr = - _S_substring(this->_M_tree_ptr, - 0, - this->_M_tree_ptr->_M_size - 1); - _S_unref(__old); - } - - _CharT back() const - { - return _S_fetch(this->_M_tree_ptr, this->_M_tree_ptr->_M_size - 1); - } - - void push_front(_CharT __x) - { - _RopeRep* __old = this->_M_tree_ptr; - _RopeRep* __left = - __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1, this->get_allocator()); - try { - this->_M_tree_ptr = _S_concat(__left, this->_M_tree_ptr); - _S_unref(__old); - _S_unref(__left); - } - catch(...) - { - _S_unref(__left); - __throw_exception_again; - } - } - - void pop_front() - { - _RopeRep* __old = this->_M_tree_ptr; - this->_M_tree_ptr - = _S_substring(this->_M_tree_ptr, 1, this->_M_tree_ptr->_M_size); - _S_unref(__old); - } - - _CharT front() const - { - return _S_fetch(this->_M_tree_ptr, 0); - } - - void balance() - { - _RopeRep* __old = this->_M_tree_ptr; - this->_M_tree_ptr = _S_balance(this->_M_tree_ptr); - _S_unref(__old); - } - - void copy(_CharT* __buffer) const { - _Destroy(__buffer, __buffer + size()); - _S_flatten(this->_M_tree_ptr, __buffer); - } - - // This is the copy function from the standard, but - // with the arguments reordered to make it consistent with the - // rest of the interface. - // Note that this guaranteed not to compile if the draft standard - // order is assumed. - size_type copy(size_type __pos, size_type __n, _CharT* __buffer) const - { - size_t __size = size(); - size_t __len = (__pos + __n > __size? __size - __pos : __n); - - _Destroy(__buffer, __buffer + __len); - _S_flatten(this->_M_tree_ptr, __pos, __len, __buffer); - return __len; - } - - // Print to stdout, exposing structure. May be useful for - // performance debugging. - void dump() { - _S_dump(this->_M_tree_ptr); - } - - // Convert to 0 terminated string in new allocated memory. - // Embedded 0s in the input do not terminate the copy. - const _CharT* c_str() const; - - // As above, but lso use the flattened representation as the - // the new rope representation. - const _CharT* replace_with_c_str(); - - // Reclaim memory for the c_str generated flattened string. - // Intentionally undocumented, since it's hard to say when this - // is safe for multiple threads. - void delete_c_str () { - if (0 == this->_M_tree_ptr) return; - if (_Rope_constants::_S_leaf == this->_M_tree_ptr->_M_tag && - ((_RopeLeaf*)this->_M_tree_ptr)->_M_data == - this->_M_tree_ptr->_M_c_string) { - // Representation shared - return; - } -# ifndef __GC - this->_M_tree_ptr->_M_free_c_string(); -# endif - this->_M_tree_ptr->_M_c_string = 0; - } - - _CharT operator[] (size_type __pos) const { - return _S_fetch(this->_M_tree_ptr, __pos); - } - - _CharT at(size_type __pos) const { - // if (__pos >= size()) throw out_of_range; // XXX - return (*this)[__pos]; - } - - const_iterator begin() const { - return(const_iterator(this->_M_tree_ptr, 0)); - } - - // An easy way to get a const iterator from a non-const container. - const_iterator const_begin() const { - return(const_iterator(this->_M_tree_ptr, 0)); - } - - const_iterator end() const { - return(const_iterator(this->_M_tree_ptr, size())); - } - - const_iterator const_end() const { - return(const_iterator(this->_M_tree_ptr, size())); - } - - size_type size() const { - return(0 == this->_M_tree_ptr? 0 : this->_M_tree_ptr->_M_size); - } - - size_type length() const { - return size(); - } - - size_type max_size() const { - return _S_min_len[_Rope_constants::_S_max_rope_depth - 1] - 1; - // Guarantees that the result can be sufficirntly - // balanced. Longer ropes will probably still work, - // but it's harder to make guarantees. - } - - typedef reverse_iterator const_reverse_iterator; - - const_reverse_iterator rbegin() const { - return const_reverse_iterator(end()); - } - - const_reverse_iterator const_rbegin() const { - return const_reverse_iterator(end()); - } - - const_reverse_iterator rend() const { - return const_reverse_iterator(begin()); - } - - const_reverse_iterator const_rend() const { - return const_reverse_iterator(begin()); - } - - template - friend rope<_CharT2,_Alloc2> - operator+ (const rope<_CharT2,_Alloc2>& __left, - const rope<_CharT2,_Alloc2>& __right); - - template - friend rope<_CharT2,_Alloc2> - operator+ (const rope<_CharT2,_Alloc2>& __left, - const _CharT2* __right); - - template - friend rope<_CharT2,_Alloc2> - operator+ (const rope<_CharT2,_Alloc2>& __left, _CharT2 __right); + { _S_unref(this->_M_tree_ptr); } + + rope& + operator=(const rope& __x) + { + _RopeRep* __old = this->_M_tree_ptr; + this->_M_tree_ptr = __x._M_tree_ptr; + _S_ref(this->_M_tree_ptr); + _S_unref(__old); + return *this; + } + + void + clear() + { + _S_unref(this->_M_tree_ptr); + this->_M_tree_ptr = 0; + } + + void + push_back(_CharT __x) + { + _RopeRep* __old = this->_M_tree_ptr; + this->_M_tree_ptr + = _S_destr_concat_char_iter(this->_M_tree_ptr, &__x, 1); + _S_unref(__old); + } + + void + pop_back() + { + _RopeRep* __old = this->_M_tree_ptr; + this->_M_tree_ptr = + _S_substring(this->_M_tree_ptr, + 0, this->_M_tree_ptr->_M_size - 1); + _S_unref(__old); + } + + _CharT + back() const + { return _S_fetch(this->_M_tree_ptr, this->_M_tree_ptr->_M_size - 1); } + + void + push_front(_CharT __x) + { + _RopeRep* __old = this->_M_tree_ptr; + _RopeRep* __left = + __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1, this->get_allocator()); + try + { + this->_M_tree_ptr = _S_concat(__left, this->_M_tree_ptr); + _S_unref(__old); + _S_unref(__left); + } + catch(...) + { + _S_unref(__left); + __throw_exception_again; + } + } + + void + pop_front() + { + _RopeRep* __old = this->_M_tree_ptr; + this->_M_tree_ptr + = _S_substring(this->_M_tree_ptr, 1, this->_M_tree_ptr->_M_size); + _S_unref(__old); + } + + _CharT + front() const + { return _S_fetch(this->_M_tree_ptr, 0); } + + void + balance() + { + _RopeRep* __old = this->_M_tree_ptr; + this->_M_tree_ptr = _S_balance(this->_M_tree_ptr); + _S_unref(__old); + } + + void + copy(_CharT* __buffer) const + { + _Destroy(__buffer, __buffer + size()); + _S_flatten(this->_M_tree_ptr, __buffer); + } + + // This is the copy function from the standard, but + // with the arguments reordered to make it consistent with the + // rest of the interface. + // Note that this guaranteed not to compile if the draft standard + // order is assumed. + size_type + copy(size_type __pos, size_type __n, _CharT* __buffer) const + { + size_t __size = size(); + size_t __len = (__pos + __n > __size? __size - __pos : __n); + + _Destroy(__buffer, __buffer + __len); + _S_flatten(this->_M_tree_ptr, __pos, __len, __buffer); + return __len; + } + + // Print to stdout, exposing structure. May be useful for + // performance debugging. + void + dump() + { _S_dump(this->_M_tree_ptr); } + + // Convert to 0 terminated string in new allocated memory. + // Embedded 0s in the input do not terminate the copy. + const _CharT* c_str() const; + + // As above, but lso use the flattened representation as the + // the new rope representation. + const _CharT* replace_with_c_str(); + + // Reclaim memory for the c_str generated flattened string. + // Intentionally undocumented, since it's hard to say when this + // is safe for multiple threads. + void + delete_c_str () + { + if (0 == this->_M_tree_ptr) + return; + if (_Rope_constants::_S_leaf == this->_M_tree_ptr->_M_tag && + ((_RopeLeaf*)this->_M_tree_ptr)->_M_data == + this->_M_tree_ptr->_M_c_string) + { + // Representation shared + return; + } +#ifndef __GC + this->_M_tree_ptr->_M_free_c_string(); +#endif + this->_M_tree_ptr->_M_c_string = 0; + } + + _CharT + operator[] (size_type __pos) const + { return _S_fetch(this->_M_tree_ptr, __pos); } + + _CharT + at(size_type __pos) const + { + // if (__pos >= size()) throw out_of_range; // XXX + return (*this)[__pos]; + } + + const_iterator + begin() const + { return(const_iterator(this->_M_tree_ptr, 0)); } + + // An easy way to get a const iterator from a non-const container. + const_iterator + const_begin() const + { return(const_iterator(this->_M_tree_ptr, 0)); } + + const_iterator + end() const + { return(const_iterator(this->_M_tree_ptr, size())); } + + const_iterator + const_end() const + { return(const_iterator(this->_M_tree_ptr, size())); } + + size_type + size() const + { return(0 == this->_M_tree_ptr? 0 : this->_M_tree_ptr->_M_size); } + + size_type + length() const + { return size(); } + + size_type + max_size() const + { + return _S_min_len[_Rope_constants::_S_max_rope_depth - 1] - 1; + // Guarantees that the result can be sufficirntly + // balanced. Longer ropes will probably still work, + // but it's harder to make guarantees. + } + + typedef reverse_iterator const_reverse_iterator; + + const_reverse_iterator + rbegin() const + { return const_reverse_iterator(end()); } + + const_reverse_iterator + const_rbegin() const + { return const_reverse_iterator(end()); } + + const_reverse_iterator + rend() const + { return const_reverse_iterator(begin()); } + + const_reverse_iterator + const_rend() const + { return const_reverse_iterator(begin()); } + + template + friend rope<_CharT2, _Alloc2> + operator+(const rope<_CharT2, _Alloc2>& __left, + const rope<_CharT2, _Alloc2>& __right); + + template + friend rope<_CharT2, _Alloc2> + operator+(const rope<_CharT2, _Alloc2>& __left, const _CharT2* __right); + + template + friend rope<_CharT2, _Alloc2> + operator+(const rope<_CharT2, _Alloc2>& __left, _CharT2 __right); // The symmetric cases are intentionally omitted, since they're presumed // to be less common, and we don't handle them as well. // The following should really be templatized. // The first argument should be an input iterator or // forward iterator with value_type _CharT. - rope& append(const _CharT* __iter, size_t __n) { - _RopeRep* __result = - _S_destr_concat_char_iter(this->_M_tree_ptr, __iter, __n); - _S_unref(this->_M_tree_ptr); - this->_M_tree_ptr = __result; - return *this; - } - - rope& append(const _CharT* __c_string) { - size_t __len = _S_char_ptr_len(__c_string); - append(__c_string, __len); - return(*this); - } - - rope& append(const _CharT* __s, const _CharT* __e) { - _RopeRep* __result = - _S_destr_concat_char_iter(this->_M_tree_ptr, __s, __e - __s); - _S_unref(this->_M_tree_ptr); - this->_M_tree_ptr = __result; - return *this; - } - - rope& append(const_iterator __s, const_iterator __e) { - _Self_destruct_ptr __appendee(_S_substring( - __s._M_root, __s._M_current_pos, __e._M_current_pos)); - _RopeRep* __result = - _S_concat(this->_M_tree_ptr, (_RopeRep*)__appendee); - _S_unref(this->_M_tree_ptr); - this->_M_tree_ptr = __result; - return *this; - } - - rope& append(_CharT __c) { - _RopeRep* __result = - _S_destr_concat_char_iter(this->_M_tree_ptr, &__c, 1); - _S_unref(this->_M_tree_ptr); - this->_M_tree_ptr = __result; - return *this; - } - - rope& append() { return append(_CharT()); } // XXX why? - - rope& append(const rope& __y) { - _RopeRep* __result = _S_concat(this->_M_tree_ptr, __y._M_tree_ptr); - _S_unref(this->_M_tree_ptr); - this->_M_tree_ptr = __result; - return *this; - } - - rope& append(size_t __n, _CharT __c) { - rope<_CharT,_Alloc> __last(__n, __c); - return append(__last); - } - - void swap(rope& __b) { - _RopeRep* __tmp = this->_M_tree_ptr; - this->_M_tree_ptr = __b._M_tree_ptr; - __b._M_tree_ptr = __tmp; - } + rope& + append(const _CharT* __iter, size_t __n) + { + _RopeRep* __result = + _S_destr_concat_char_iter(this->_M_tree_ptr, __iter, __n); + _S_unref(this->_M_tree_ptr); + this->_M_tree_ptr = __result; + return *this; + } + + rope& + append(const _CharT* __c_string) + { + size_t __len = _S_char_ptr_len(__c_string); + append(__c_string, __len); + return(*this); + } + + rope& + append(const _CharT* __s, const _CharT* __e) + { + _RopeRep* __result = + _S_destr_concat_char_iter(this->_M_tree_ptr, __s, __e - __s); + _S_unref(this->_M_tree_ptr); + this->_M_tree_ptr = __result; + return *this; + } + + rope& + append(const_iterator __s, const_iterator __e) + { + _Self_destruct_ptr __appendee(_S_substring(__s._M_root, + __s._M_current_pos, + __e._M_current_pos)); + _RopeRep* __result = + _S_concat(this->_M_tree_ptr, (_RopeRep*)__appendee); + _S_unref(this->_M_tree_ptr); + this->_M_tree_ptr = __result; + return *this; + } + + rope& + append(_CharT __c) + { + _RopeRep* __result = + _S_destr_concat_char_iter(this->_M_tree_ptr, &__c, 1); + _S_unref(this->_M_tree_ptr); + this->_M_tree_ptr = __result; + return *this; + } + + rope& + append() + { return append(_CharT()); } // XXX why? + + rope& + append(const rope& __y) + { + _RopeRep* __result = _S_concat(this->_M_tree_ptr, __y._M_tree_ptr); + _S_unref(this->_M_tree_ptr); + this->_M_tree_ptr = __result; + return *this; + } + rope& + append(size_t __n, _CharT __c) + { + rope<_CharT,_Alloc> __last(__n, __c); + return append(__last); + } + + void + swap(rope& __b) + { + _RopeRep* __tmp = this->_M_tree_ptr; + this->_M_tree_ptr = __b._M_tree_ptr; + __b._M_tree_ptr = __tmp; + } protected: - // Result is included in refcount. - static _RopeRep* replace(_RopeRep* __old, size_t __pos1, - size_t __pos2, _RopeRep* __r) { - if (0 == __old) { _S_ref(__r); return __r; } - _Self_destruct_ptr __left( - _S_substring(__old, 0, __pos1)); - _Self_destruct_ptr __right( - _S_substring(__old, __pos2, __old->_M_size)); - _RopeRep* __result; - - if (0 == __r) { - __result = _S_concat(__left, __right); - } else { - _Self_destruct_ptr __left_result(_S_concat(__left, __r)); - __result = _S_concat(__left_result, __right); - } - return __result; - } + // Result is included in refcount. + static _RopeRep* + replace(_RopeRep* __old, size_t __pos1, + size_t __pos2, _RopeRep* __r) + { + if (0 == __old) + { + _S_ref(__r); + return __r; + } + _Self_destruct_ptr __left(_S_substring(__old, 0, __pos1)); + _Self_destruct_ptr __right(_S_substring(__old, __pos2, __old->_M_size)); + _RopeRep* __result; + + if (0 == __r) + __result = _S_concat(__left, __right); + else + { + _Self_destruct_ptr __left_result(_S_concat(__left, __r)); + __result = _S_concat(__left_result, __right); + } + return __result; + } public: - void insert(size_t __p, const rope& __r) { - _RopeRep* __result = - replace(this->_M_tree_ptr, __p, __p, __r._M_tree_ptr); - _S_unref(this->_M_tree_ptr); - this->_M_tree_ptr = __result; - } - - void insert(size_t __p, size_t __n, _CharT __c) { - rope<_CharT,_Alloc> __r(__n,__c); - insert(__p, __r); - } - - void insert(size_t __p, const _CharT* __i, size_t __n) { - _Self_destruct_ptr __left(_S_substring(this->_M_tree_ptr, 0, __p)); - _Self_destruct_ptr __right(_S_substring(this->_M_tree_ptr, - __p, size())); - _Self_destruct_ptr __left_result( - _S_concat_char_iter(__left, __i, __n)); - // _S_ destr_concat_char_iter should be safe here. - // But as it stands it's probably not a win, since __left - // is likely to have additional references. - _RopeRep* __result = _S_concat(__left_result, __right); - _S_unref(this->_M_tree_ptr); - this->_M_tree_ptr = __result; - } - - void insert(size_t __p, const _CharT* __c_string) { - insert(__p, __c_string, _S_char_ptr_len(__c_string)); - } - - void insert(size_t __p, _CharT __c) { - insert(__p, &__c, 1); - } - - void insert(size_t __p) { - _CharT __c = _CharT(); - insert(__p, &__c, 1); - } - - void insert(size_t __p, const _CharT* __i, const _CharT* __j) { - rope __r(__i, __j); - insert(__p, __r); - } - - void insert(size_t __p, const const_iterator& __i, - const const_iterator& __j) { - rope __r(__i, __j); - insert(__p, __r); - } - - void insert(size_t __p, const iterator& __i, - const iterator& __j) { - rope __r(__i, __j); - insert(__p, __r); - } - - // (position, length) versions of replace operations: - - void replace(size_t __p, size_t __n, const rope& __r) { - _RopeRep* __result = - replace(this->_M_tree_ptr, __p, __p + __n, __r._M_tree_ptr); - _S_unref(this->_M_tree_ptr); - this->_M_tree_ptr = __result; - } - - void replace(size_t __p, size_t __n, - const _CharT* __i, size_t __i_len) { - rope __r(__i, __i_len); - replace(__p, __n, __r); - } - - void replace(size_t __p, size_t __n, _CharT __c) { - rope __r(__c); - replace(__p, __n, __r); - } - - void replace(size_t __p, size_t __n, const _CharT* __c_string) { - rope __r(__c_string); - replace(__p, __n, __r); - } - - void replace(size_t __p, size_t __n, - const _CharT* __i, const _CharT* __j) { - rope __r(__i, __j); - replace(__p, __n, __r); - } - - void replace(size_t __p, size_t __n, - const const_iterator& __i, const const_iterator& __j) { - rope __r(__i, __j); - replace(__p, __n, __r); - } - - void replace(size_t __p, size_t __n, - const iterator& __i, const iterator& __j) { - rope __r(__i, __j); - replace(__p, __n, __r); - } - - // Single character variants: - void replace(size_t __p, _CharT __c) { - iterator __i(this, __p); - *__i = __c; - } - - void replace(size_t __p, const rope& __r) { - replace(__p, 1, __r); - } - - void replace(size_t __p, const _CharT* __i, size_t __i_len) { - replace(__p, 1, __i, __i_len); - } - - void replace(size_t __p, const _CharT* __c_string) { - replace(__p, 1, __c_string); - } - - void replace(size_t __p, const _CharT* __i, const _CharT* __j) { - replace(__p, 1, __i, __j); - } - - void replace(size_t __p, const const_iterator& __i, - const const_iterator& __j) { - replace(__p, 1, __i, __j); - } - - void replace(size_t __p, const iterator& __i, - const iterator& __j) { - replace(__p, 1, __i, __j); - } - - // Erase, (position, size) variant. - void erase(size_t __p, size_t __n) { - _RopeRep* __result = replace(this->_M_tree_ptr, __p, __p + __n, 0); - _S_unref(this->_M_tree_ptr); - this->_M_tree_ptr = __result; - } - - // Erase, single character - void erase(size_t __p) { - erase(__p, __p + 1); - } - - // Insert, iterator variants. - iterator insert(const iterator& __p, const rope& __r) - { insert(__p.index(), __r); return __p; } - iterator insert(const iterator& __p, size_t __n, _CharT __c) - { insert(__p.index(), __n, __c); return __p; } - iterator insert(const iterator& __p, _CharT __c) - { insert(__p.index(), __c); return __p; } - iterator insert(const iterator& __p ) - { insert(__p.index()); return __p; } - iterator insert(const iterator& __p, const _CharT* c_string) - { insert(__p.index(), c_string); return __p; } - iterator insert(const iterator& __p, const _CharT* __i, size_t __n) - { insert(__p.index(), __i, __n); return __p; } - iterator insert(const iterator& __p, const _CharT* __i, - const _CharT* __j) - { insert(__p.index(), __i, __j); return __p; } - iterator insert(const iterator& __p, - const const_iterator& __i, const const_iterator& __j) - { insert(__p.index(), __i, __j); return __p; } - iterator insert(const iterator& __p, - const iterator& __i, const iterator& __j) - { insert(__p.index(), __i, __j); return __p; } - - // Replace, range variants. - void replace(const iterator& __p, const iterator& __q, - const rope& __r) - { replace(__p.index(), __q.index() - __p.index(), __r); } - void replace(const iterator& __p, const iterator& __q, _CharT __c) - { replace(__p.index(), __q.index() - __p.index(), __c); } - void replace(const iterator& __p, const iterator& __q, - const _CharT* __c_string) - { replace(__p.index(), __q.index() - __p.index(), __c_string); } - void replace(const iterator& __p, const iterator& __q, - const _CharT* __i, size_t __n) - { replace(__p.index(), __q.index() - __p.index(), __i, __n); } - void replace(const iterator& __p, const iterator& __q, - const _CharT* __i, const _CharT* __j) - { replace(__p.index(), __q.index() - __p.index(), __i, __j); } - void replace(const iterator& __p, const iterator& __q, - const const_iterator& __i, const const_iterator& __j) - { replace(__p.index(), __q.index() - __p.index(), __i, __j); } - void replace(const iterator& __p, const iterator& __q, - const iterator& __i, const iterator& __j) - { replace(__p.index(), __q.index() - __p.index(), __i, __j); } - - // Replace, iterator variants. - void replace(const iterator& __p, const rope& __r) - { replace(__p.index(), __r); } - void replace(const iterator& __p, _CharT __c) - { replace(__p.index(), __c); } - void replace(const iterator& __p, const _CharT* __c_string) - { replace(__p.index(), __c_string); } - void replace(const iterator& __p, const _CharT* __i, size_t __n) - { replace(__p.index(), __i, __n); } - void replace(const iterator& __p, const _CharT* __i, const _CharT* __j) - { replace(__p.index(), __i, __j); } - void replace(const iterator& __p, const_iterator __i, - const_iterator __j) - { replace(__p.index(), __i, __j); } - void replace(const iterator& __p, iterator __i, iterator __j) - { replace(__p.index(), __i, __j); } - - // Iterator and range variants of erase - iterator erase(const iterator& __p, const iterator& __q) { - size_t __p_index = __p.index(); - erase(__p_index, __q.index() - __p_index); - return iterator(this, __p_index); - } - iterator erase(const iterator& __p) { - size_t __p_index = __p.index(); - erase(__p_index, 1); - return iterator(this, __p_index); - } - - rope substr(size_t __start, size_t __len = 1) const { - return rope<_CharT,_Alloc>( - _S_substring(this->_M_tree_ptr, - __start, - __start + __len)); - } - - rope substr(iterator __start, iterator __end) const { - return rope<_CharT,_Alloc>( - _S_substring(this->_M_tree_ptr, - __start.index(), - __end.index())); - } - - rope substr(iterator __start) const { - size_t __pos = __start.index(); - return rope<_CharT,_Alloc>( - _S_substring(this->_M_tree_ptr, __pos, __pos + 1)); - } - - rope substr(const_iterator __start, const_iterator __end) const { - // This might eventually take advantage of the cache in the - // iterator. - return rope<_CharT,_Alloc>( - _S_substring(this->_M_tree_ptr, __start.index(), __end.index())); - } - - rope<_CharT,_Alloc> substr(const_iterator __start) { - size_t __pos = __start.index(); - return rope<_CharT,_Alloc>( - _S_substring(this->_M_tree_ptr, __pos, __pos + 1)); - } - - static const size_type npos; - - size_type find(_CharT __c, size_type __pos = 0) const; - size_type find(const _CharT* __s, size_type __pos = 0) const { - size_type __result_pos; - const_iterator __result = - std::search(const_begin() + __pos, const_end(), - __s, __s + _S_char_ptr_len(__s)); - __result_pos = __result.index(); -# ifndef __STL_OLD_ROPE_SEMANTICS - if (__result_pos == size()) __result_pos = npos; -# endif - return __result_pos; - } - - iterator mutable_begin() { - return(iterator(this, 0)); - } - - iterator mutable_end() { - return(iterator(this, size())); - } - - typedef reverse_iterator reverse_iterator; - - reverse_iterator mutable_rbegin() { - return reverse_iterator(mutable_end()); - } - - reverse_iterator mutable_rend() { - return reverse_iterator(mutable_begin()); - } - - reference mutable_reference_at(size_type __pos) { - return reference(this, __pos); - } - -# ifdef __STD_STUFF - reference operator[] (size_type __pos) { - return _char_ref_proxy(this, __pos); - } - - reference at(size_type __pos) { - // if (__pos >= size()) throw out_of_range; // XXX - return (*this)[__pos]; - } - - void resize(size_type __n, _CharT __c) {} - void resize(size_type __n) {} - void reserve(size_type __res_arg = 0) {} - size_type capacity() const { - return max_size(); - } - - // Stuff below this line is dangerous because it's error prone. - // I would really like to get rid of it. - // copy function with funny arg ordering. - size_type copy(_CharT* __buffer, size_type __n, - size_type __pos = 0) const { - return copy(__pos, __n, __buffer); - } - - iterator end() { return mutable_end(); } - - iterator begin() { return mutable_begin(); } - - reverse_iterator rend() { return mutable_rend(); } - - reverse_iterator rbegin() { return mutable_rbegin(); } - -# else - - const_iterator end() { return const_end(); } - - const_iterator begin() { return const_begin(); } - - const_reverse_iterator rend() { return const_rend(); } - - const_reverse_iterator rbegin() { return const_rbegin(); } - -# endif - -}; - -template -const typename rope<_CharT, _Alloc>::size_type rope<_CharT, _Alloc>::npos = - (size_type)(-1); - -template -inline bool operator== (const _Rope_const_iterator<_CharT,_Alloc>& __x, - const _Rope_const_iterator<_CharT,_Alloc>& __y) { - return (__x._M_current_pos == __y._M_current_pos && - __x._M_root == __y._M_root); -} - -template -inline bool operator< (const _Rope_const_iterator<_CharT,_Alloc>& __x, - const _Rope_const_iterator<_CharT,_Alloc>& __y) { - return (__x._M_current_pos < __y._M_current_pos); -} - -template -inline bool operator!= (const _Rope_const_iterator<_CharT,_Alloc>& __x, - const _Rope_const_iterator<_CharT,_Alloc>& __y) { - return !(__x == __y); -} - -template -inline bool operator> (const _Rope_const_iterator<_CharT,_Alloc>& __x, - const _Rope_const_iterator<_CharT,_Alloc>& __y) { - return __y < __x; -} - -template -inline bool operator<= (const _Rope_const_iterator<_CharT,_Alloc>& __x, - const _Rope_const_iterator<_CharT,_Alloc>& __y) { - return !(__y < __x); -} - -template -inline bool operator>= (const _Rope_const_iterator<_CharT,_Alloc>& __x, - const _Rope_const_iterator<_CharT,_Alloc>& __y) { - return !(__x < __y); -} - -template -inline ptrdiff_t operator-(const _Rope_const_iterator<_CharT,_Alloc>& __x, - const _Rope_const_iterator<_CharT,_Alloc>& __y) { - return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; -} - -template -inline _Rope_const_iterator<_CharT,_Alloc> -operator-(const _Rope_const_iterator<_CharT,_Alloc>& __x, ptrdiff_t __n) { - return _Rope_const_iterator<_CharT,_Alloc>( - __x._M_root, __x._M_current_pos - __n); -} - -template -inline _Rope_const_iterator<_CharT,_Alloc> -operator+(const _Rope_const_iterator<_CharT,_Alloc>& __x, ptrdiff_t __n) { - return _Rope_const_iterator<_CharT,_Alloc>( - __x._M_root, __x._M_current_pos + __n); -} - -template -inline _Rope_const_iterator<_CharT,_Alloc> -operator+(ptrdiff_t __n, const _Rope_const_iterator<_CharT,_Alloc>& __x) { - return _Rope_const_iterator<_CharT,_Alloc>( - __x._M_root, __x._M_current_pos + __n); -} - -template -inline bool operator== (const _Rope_iterator<_CharT,_Alloc>& __x, - const _Rope_iterator<_CharT,_Alloc>& __y) { - return (__x._M_current_pos == __y._M_current_pos && - __x._M_root_rope == __y._M_root_rope); -} - -template -inline bool operator< (const _Rope_iterator<_CharT,_Alloc>& __x, - const _Rope_iterator<_CharT,_Alloc>& __y) { - return (__x._M_current_pos < __y._M_current_pos); -} - -template -inline bool operator!= (const _Rope_iterator<_CharT,_Alloc>& __x, - const _Rope_iterator<_CharT,_Alloc>& __y) { - return !(__x == __y); -} - -template -inline bool operator> (const _Rope_iterator<_CharT,_Alloc>& __x, - const _Rope_iterator<_CharT,_Alloc>& __y) { - return __y < __x; -} - -template -inline bool operator<= (const _Rope_iterator<_CharT,_Alloc>& __x, - const _Rope_iterator<_CharT,_Alloc>& __y) { - return !(__y < __x); -} - -template -inline bool operator>= (const _Rope_iterator<_CharT,_Alloc>& __x, - const _Rope_iterator<_CharT,_Alloc>& __y) { - return !(__x < __y); -} - -template -inline ptrdiff_t operator-(const _Rope_iterator<_CharT,_Alloc>& __x, - const _Rope_iterator<_CharT,_Alloc>& __y) { - return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; -} - -template -inline _Rope_iterator<_CharT,_Alloc> -operator-(const _Rope_iterator<_CharT,_Alloc>& __x, - ptrdiff_t __n) { - return _Rope_iterator<_CharT,_Alloc>( - __x._M_root_rope, __x._M_current_pos - __n); -} - -template -inline _Rope_iterator<_CharT,_Alloc> -operator+(const _Rope_iterator<_CharT,_Alloc>& __x, - ptrdiff_t __n) { - return _Rope_iterator<_CharT,_Alloc>( - __x._M_root_rope, __x._M_current_pos + __n); -} - -template -inline _Rope_iterator<_CharT,_Alloc> -operator+(ptrdiff_t __n, const _Rope_iterator<_CharT,_Alloc>& __x) { - return _Rope_iterator<_CharT,_Alloc>( - __x._M_root_rope, __x._M_current_pos + __n); -} - -template -inline -rope<_CharT,_Alloc> -operator+ (const rope<_CharT,_Alloc>& __left, - const rope<_CharT,_Alloc>& __right) -{ - return rope<_CharT,_Alloc>( - rope<_CharT,_Alloc>::_S_concat(__left._M_tree_ptr, __right._M_tree_ptr)); - // Inlining this should make it possible to keep __left and - // __right in registers. -} - -template -inline -rope<_CharT,_Alloc>& -operator+= (rope<_CharT,_Alloc>& __left, - const rope<_CharT,_Alloc>& __right) -{ - __left.append(__right); - return __left; -} - -template -inline -rope<_CharT,_Alloc> -operator+ (const rope<_CharT,_Alloc>& __left, - const _CharT* __right) { - 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, __right, __rlen)); -} - -template -inline -rope<_CharT,_Alloc>& -operator+= (rope<_CharT,_Alloc>& __left, - const _CharT* __right) { - __left.append(__right); - return __left; -} - -template -inline -rope<_CharT,_Alloc> -operator+ (const rope<_CharT,_Alloc>& __left, _CharT __right) { - return rope<_CharT,_Alloc>( - rope<_CharT,_Alloc>::_S_concat_char_iter( - __left._M_tree_ptr, &__right, 1)); -} - -template -inline -rope<_CharT,_Alloc>& -operator+= (rope<_CharT,_Alloc>& __left, _CharT __right) { - __left.append(__right); - return __left; -} - -template -bool -operator< (const rope<_CharT,_Alloc>& __left, - const rope<_CharT,_Alloc>& __right) { - return __left.compare(__right) < 0; -} - -template -bool -operator== (const rope<_CharT,_Alloc>& __left, - const rope<_CharT,_Alloc>& __right) { - return __left.compare(__right) == 0; -} - -template -inline bool operator== (const _Rope_char_ptr_proxy<_CharT,_Alloc>& __x, - const _Rope_char_ptr_proxy<_CharT,_Alloc>& __y) { - return (__x._M_pos == __y._M_pos && __x._M_root == __y._M_root); -} - -template -inline bool -operator!= (const rope<_CharT,_Alloc>& __x, const rope<_CharT,_Alloc>& __y) { - return !(__x == __y); -} - -template -inline bool -operator> (const rope<_CharT,_Alloc>& __x, const rope<_CharT,_Alloc>& __y) { - return __y < __x; -} - -template -inline bool -operator<= (const rope<_CharT,_Alloc>& __x, const rope<_CharT,_Alloc>& __y) { - return !(__y < __x); -} - -template -inline bool -operator>= (const rope<_CharT,_Alloc>& __x, const rope<_CharT,_Alloc>& __y) { - return !(__x < __y); -} - -template -inline bool operator!= (const _Rope_char_ptr_proxy<_CharT,_Alloc>& __x, - const _Rope_char_ptr_proxy<_CharT,_Alloc>& __y) { - return !(__x == __y); -} - -template -std::basic_ostream<_CharT, _Traits>& operator<< - (std::basic_ostream<_CharT, _Traits>& __o, - const rope<_CharT, _Alloc>& __r); - -typedef rope crope; -typedef rope wrope; - -inline crope::reference __mutable_reference_at(crope& __c, size_t __i) -{ - return __c.mutable_reference_at(__i); -} + void + insert(size_t __p, const rope& __r) + { + _RopeRep* __result = + replace(this->_M_tree_ptr, __p, __p, __r._M_tree_ptr); + _S_unref(this->_M_tree_ptr); + this->_M_tree_ptr = __result; + } -inline wrope::reference __mutable_reference_at(wrope& __c, size_t __i) -{ - return __c.mutable_reference_at(__i); -} + void + insert(size_t __p, size_t __n, _CharT __c) + { + rope<_CharT,_Alloc> __r(__n,__c); + insert(__p, __r); + } + + void + insert(size_t __p, const _CharT* __i, size_t __n) + { + _Self_destruct_ptr __left(_S_substring(this->_M_tree_ptr, 0, __p)); + _Self_destruct_ptr __right(_S_substring(this->_M_tree_ptr, + __p, size())); + _Self_destruct_ptr __left_result(_S_concat_char_iter(__left, __i, __n)); + // _S_ destr_concat_char_iter should be safe here. + // But as it stands it's probably not a win, since __left + // is likely to have additional references. + _RopeRep* __result = _S_concat(__left_result, __right); + _S_unref(this->_M_tree_ptr); + this->_M_tree_ptr = __result; + } -template -inline void swap(rope<_CharT,_Alloc>& __x, rope<_CharT,_Alloc>& __y) { - __x.swap(__y); -} + void + insert(size_t __p, const _CharT* __c_string) + { insert(__p, __c_string, _S_char_ptr_len(__c_string)); } -// Hash functions should probably be revisited later: -template<> struct hash -{ - size_t operator()(const crope& __str) const - { - size_t __size = __str.size(); + void + insert(size_t __p, _CharT __c) + { insert(__p, &__c, 1); } - if (0 == __size) return 0; - return 13*__str[0] + 5*__str[__size - 1] + __size; - } -}; + void + insert(size_t __p) + { + _CharT __c = _CharT(); + insert(__p, &__c, 1); + } + void + insert(size_t __p, const _CharT* __i, const _CharT* __j) + { + rope __r(__i, __j); + insert(__p, __r); + } -template<> struct hash -{ - size_t operator()(const wrope& __str) const - { - size_t __size = __str.size(); + void + insert(size_t __p, const const_iterator& __i, + const const_iterator& __j) + { + rope __r(__i, __j); + insert(__p, __r); + } - if (0 == __size) return 0; - return 13*__str[0] + 5*__str[__size - 1] + __size; - } -}; + void + insert(size_t __p, const iterator& __i, + const iterator& __j) + { + rope __r(__i, __j); + insert(__p, __r); + } + + // (position, length) versions of replace operations: + + void + replace(size_t __p, size_t __n, const rope& __r) + { + _RopeRep* __result = + replace(this->_M_tree_ptr, __p, __p + __n, __r._M_tree_ptr); + _S_unref(this->_M_tree_ptr); + this->_M_tree_ptr = __result; + } + + void + replace(size_t __p, size_t __n, + const _CharT* __i, size_t __i_len) + { + rope __r(__i, __i_len); + replace(__p, __n, __r); + } + + void + replace(size_t __p, size_t __n, _CharT __c) + { + rope __r(__c); + replace(__p, __n, __r); + } + + void + replace(size_t __p, size_t __n, const _CharT* __c_string) + { + rope __r(__c_string); + replace(__p, __n, __r); + } + + void + replace(size_t __p, size_t __n, + const _CharT* __i, const _CharT* __j) + { + rope __r(__i, __j); + replace(__p, __n, __r); + } + + void + replace(size_t __p, size_t __n, + const const_iterator& __i, const const_iterator& __j) + { + rope __r(__i, __j); + replace(__p, __n, __r); + } + + void + replace(size_t __p, size_t __n, + const iterator& __i, const iterator& __j) + { + rope __r(__i, __j); + replace(__p, __n, __r); + } + + // Single character variants: + void + replace(size_t __p, _CharT __c) + { + iterator __i(this, __p); + *__i = __c; + } + + void + replace(size_t __p, const rope& __r) + { replace(__p, 1, __r); } + + void + replace(size_t __p, const _CharT* __i, size_t __i_len) + { replace(__p, 1, __i, __i_len); } + + void + replace(size_t __p, const _CharT* __c_string) + { replace(__p, 1, __c_string); } + + void + replace(size_t __p, const _CharT* __i, const _CharT* __j) + { replace(__p, 1, __i, __j); } + + void + replace(size_t __p, const const_iterator& __i, + const const_iterator& __j) + { replace(__p, 1, __i, __j); } + + void + replace(size_t __p, const iterator& __i, + const iterator& __j) + { replace(__p, 1, __i, __j); } + + // Erase, (position, size) variant. + void + erase(size_t __p, size_t __n) + { + _RopeRep* __result = replace(this->_M_tree_ptr, __p, + __p + __n, 0); + _S_unref(this->_M_tree_ptr); + this->_M_tree_ptr = __result; + } + + // Erase, single character + void + erase(size_t __p) + { erase(__p, __p + 1); } + + // Insert, iterator variants. + iterator + insert(const iterator& __p, const rope& __r) + { + insert(__p.index(), __r); + return __p; + } + + iterator + insert(const iterator& __p, size_t __n, _CharT __c) + { + insert(__p.index(), __n, __c); + return __p; + } + + iterator insert(const iterator& __p, _CharT __c) + { + insert(__p.index(), __c); + return __p; + } + + iterator + insert(const iterator& __p ) + { + insert(__p.index()); + return __p; + } + + iterator + insert(const iterator& __p, const _CharT* c_string) + { + insert(__p.index(), c_string); + return __p; + } + + iterator + insert(const iterator& __p, const _CharT* __i, size_t __n) + { + insert(__p.index(), __i, __n); + return __p; + } + + iterator + insert(const iterator& __p, const _CharT* __i, + const _CharT* __j) + { + insert(__p.index(), __i, __j); + return __p; + } + + iterator + insert(const iterator& __p, + const const_iterator& __i, const const_iterator& __j) + { + insert(__p.index(), __i, __j); + return __p; + } + + iterator + insert(const iterator& __p, + const iterator& __i, const iterator& __j) + { + insert(__p.index(), __i, __j); + return __p; + } + + // Replace, range variants. + void + replace(const iterator& __p, const iterator& __q, const rope& __r) + { replace(__p.index(), __q.index() - __p.index(), __r); } + + void + replace(const iterator& __p, const iterator& __q, _CharT __c) + { replace(__p.index(), __q.index() - __p.index(), __c); } + + void + replace(const iterator& __p, const iterator& __q, + const _CharT* __c_string) + { replace(__p.index(), __q.index() - __p.index(), __c_string); } + + void + replace(const iterator& __p, const iterator& __q, + const _CharT* __i, size_t __n) + { replace(__p.index(), __q.index() - __p.index(), __i, __n); } + + void + replace(const iterator& __p, const iterator& __q, + const _CharT* __i, const _CharT* __j) + { replace(__p.index(), __q.index() - __p.index(), __i, __j); } + + void + replace(const iterator& __p, const iterator& __q, + const const_iterator& __i, const const_iterator& __j) + { replace(__p.index(), __q.index() - __p.index(), __i, __j); } + + void + replace(const iterator& __p, const iterator& __q, + const iterator& __i, const iterator& __j) + { replace(__p.index(), __q.index() - __p.index(), __i, __j); } + + // Replace, iterator variants. + void + replace(const iterator& __p, const rope& __r) + { replace(__p.index(), __r); } + + void + replace(const iterator& __p, _CharT __c) + { replace(__p.index(), __c); } + + void + replace(const iterator& __p, const _CharT* __c_string) + { replace(__p.index(), __c_string); } + + void + replace(const iterator& __p, const _CharT* __i, size_t __n) + { replace(__p.index(), __i, __n); } + + void + replace(const iterator& __p, const _CharT* __i, const _CharT* __j) + { replace(__p.index(), __i, __j); } + + void + replace(const iterator& __p, const_iterator __i, const_iterator __j) + { replace(__p.index(), __i, __j); } + + void + replace(const iterator& __p, iterator __i, iterator __j) + { replace(__p.index(), __i, __j); } + + // Iterator and range variants of erase + iterator + erase(const iterator& __p, const iterator& __q) + { + size_t __p_index = __p.index(); + erase(__p_index, __q.index() - __p_index); + return iterator(this, __p_index); + } + + iterator + erase(const iterator& __p) + { + size_t __p_index = __p.index(); + erase(__p_index, 1); + return iterator(this, __p_index); + } + + rope + substr(size_t __start, size_t __len = 1) const + { + return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, + __start, + __start + __len)); + } + + rope + substr(iterator __start, iterator __end) const + { + return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, + __start.index(), + __end.index())); + } + + rope + substr(iterator __start) const + { + size_t __pos = __start.index(); + return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, + __pos, __pos + 1)); + } + + rope + substr(const_iterator __start, const_iterator __end) const + { + // This might eventually take advantage of the cache in the + // iterator. + return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, + __start.index(), + __end.index())); + } + + rope<_CharT, _Alloc> + substr(const_iterator __start) + { + size_t __pos = __start.index(); + return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, + __pos, __pos + 1)); + } + + static const size_type npos; + + size_type find(_CharT __c, size_type __pos = 0) const; + + size_type + find(const _CharT* __s, size_type __pos = 0) const + { + size_type __result_pos; + const_iterator __result = + std::search(const_begin() + __pos, const_end(), + __s, __s + _S_char_ptr_len(__s)); + __result_pos = __result.index(); +#ifndef __STL_OLD_ROPE_SEMANTICS + if (__result_pos == size()) + __result_pos = npos; +#endif + return __result_pos; + } + + iterator + mutable_begin() + { return(iterator(this, 0)); } + + iterator + mutable_end() + { return(iterator(this, size())); } + + typedef reverse_iterator reverse_iterator; + + reverse_iterator + mutable_rbegin() + { return reverse_iterator(mutable_end()); } + + reverse_iterator + mutable_rend() + { return reverse_iterator(mutable_begin()); } + + reference + mutable_reference_at(size_type __pos) + { return reference(this, __pos); } + +#ifdef __STD_STUFF + reference + operator[] (size_type __pos) + { return _char_ref_proxy(this, __pos); } + + reference + at(size_type __pos) + { + // if (__pos >= size()) throw out_of_range; // XXX + return (*this)[__pos]; + } + + void resize(size_type __n, _CharT __c) {} + void resize(size_type __n) {} + void reserve(size_type __res_arg = 0) {} + + size_type + capacity() const + { return max_size(); } + + // Stuff below this line is dangerous because it's error prone. + // I would really like to get rid of it. + // copy function with funny arg ordering. + size_type + copy(_CharT* __buffer, size_type __n, + size_type __pos = 0) const + { return copy(__pos, __n, __buffer); } + + iterator + end() + { return mutable_end(); } + + iterator + begin() + { return mutable_begin(); } + + reverse_iterator + rend() + { return mutable_rend(); } + + reverse_iterator + rbegin() + { return mutable_rbegin(); } + +#else + const_iterator + end() + { return const_end(); } + + const_iterator + begin() + { return const_begin(); } + + const_reverse_iterator + rend() + { return const_rend(); } + + const_reverse_iterator + rbegin() + { return const_rbegin(); } + +#endif + }; + + template + const typename rope<_CharT, _Alloc>::size_type + rope<_CharT, _Alloc>::npos = (size_type)(-1); + + template + inline bool operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x, + const _Rope_const_iterator<_CharT, _Alloc>& __y) + { return (__x._M_current_pos == __y._M_current_pos + && __x._M_root == __y._M_root); } + + template + inline bool operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x, + const _Rope_const_iterator<_CharT, _Alloc>& __y) + { return (__x._M_current_pos < __y._M_current_pos); } + + template + inline bool operator!=(const _Rope_const_iterator<_CharT, _Alloc>& __x, + const _Rope_const_iterator<_CharT, _Alloc>& __y) + { return !(__x == __y); } + + template + inline bool operator>(const _Rope_const_iterator<_CharT, _Alloc>& __x, + const _Rope_const_iterator<_CharT, _Alloc>& __y) + { return __y < __x; } + + template + inline bool + operator<=(const _Rope_const_iterator<_CharT, _Alloc>& __x, + const _Rope_const_iterator<_CharT, _Alloc>& __y) + { return !(__y < __x); } + + template + inline bool + operator>=(const _Rope_const_iterator<_CharT, _Alloc>& __x, + const _Rope_const_iterator<_CharT, _Alloc>& __y) + { return !(__x < __y); } + + template + inline ptrdiff_t + operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, + const _Rope_const_iterator<_CharT, _Alloc>& __y) + { return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; } + + template + inline _Rope_const_iterator<_CharT, _Alloc> + operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n) + { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root, + __x._M_current_pos - __n); } + + template + inline _Rope_const_iterator<_CharT, _Alloc> + operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n) + { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root, + __x._M_current_pos + __n); } + + template + inline _Rope_const_iterator<_CharT, _Alloc> + operator+(ptrdiff_t __n, const _Rope_const_iterator<_CharT, _Alloc>& __x) + { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root, + __x._M_current_pos + __n); } + + template + inline bool + operator==(const _Rope_iterator<_CharT, _Alloc>& __x, + const _Rope_iterator<_CharT, _Alloc>& __y) + {return (__x._M_current_pos == __y._M_current_pos + && __x._M_root_rope == __y._M_root_rope); } + + template + inline bool + operator<(const _Rope_iterator<_CharT, _Alloc>& __x, + const _Rope_iterator<_CharT, _Alloc>& __y) + { return (__x._M_current_pos < __y._M_current_pos); } + + template + inline bool + operator!=(const _Rope_iterator<_CharT, _Alloc>& __x, + const _Rope_iterator<_CharT, _Alloc>& __y) + { return !(__x == __y); } + + template + inline bool + operator>(const _Rope_iterator<_CharT, _Alloc>& __x, + const _Rope_iterator<_CharT, _Alloc>& __y) + { return __y < __x; } + + template + inline bool + operator<=(const _Rope_iterator<_CharT, _Alloc>& __x, + const _Rope_iterator<_CharT, _Alloc>& __y) + { return !(__y < __x); } + + template + inline bool + operator>=(const _Rope_iterator<_CharT, _Alloc>& __x, + const _Rope_iterator<_CharT, _Alloc>& __y) + { return !(__x < __y); } + + template + inline ptrdiff_t + operator-(const _Rope_iterator<_CharT, _Alloc>& __x, + const _Rope_iterator<_CharT, _Alloc>& __y) + { return ((ptrdiff_t)__x._M_current_pos + - (ptrdiff_t)__y._M_current_pos); } + + template + inline _Rope_iterator<_CharT, _Alloc> + operator-(const _Rope_iterator<_CharT, _Alloc>& __x, + ptrdiff_t __n) + { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope, + __x._M_current_pos - __n); } + + template + inline _Rope_iterator<_CharT, _Alloc> + operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n) + { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope, + __x._M_current_pos + __n); } + + template + inline _Rope_iterator<_CharT,_Alloc> + operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x) + { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope, + __x._M_current_pos + __n); } + + template + inline rope<_CharT,_Alloc> + operator+(const rope<_CharT, _Alloc>& __left, + const rope<_CharT, _Alloc>& __right) + { + return rope<_CharT, _Alloc>(rope<_CharT, _Alloc>:: + _S_concat(__left._M_tree_ptr, + __right._M_tree_ptr)); + // Inlining this should make it possible to keep __left and + // __right in registers. + } + + template + inline rope<_CharT, _Alloc>& + operator+=(rope<_CharT, _Alloc>& __left, + const rope<_CharT, _Alloc>& __right) + { + __left.append(__right); + return __left; + } + + template + inline rope<_CharT, _Alloc> + operator+(const rope<_CharT, _Alloc>& __left, + const _CharT* __right) + { + 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, + __right, __rlen)); + } + + template + inline rope<_CharT, _Alloc>& + operator+=(rope<_CharT, _Alloc>& __left, + const _CharT* __right) + { + __left.append(__right); + return __left; + } + + template + inline rope<_CharT, _Alloc> + operator+(const rope<_CharT, _Alloc>& __left, _CharT __right) + { + return rope<_CharT, _Alloc>(rope<_CharT, _Alloc>:: + _S_concat_char_iter(__left._M_tree_ptr, + &__right, 1)); + } + + template + inline rope<_CharT, _Alloc>& + operator+=(rope<_CharT, _Alloc>& __left, _CharT __right) + { + __left.append(__right); + return __left; + } + + template + bool + operator<(const rope<_CharT, _Alloc>& __left, + const rope<_CharT, _Alloc>& __right) + { return __left.compare(__right) < 0; } + + template + bool + operator==(const rope<_CharT, _Alloc>& __left, + const rope<_CharT, _Alloc>& __right) + { return __left.compare(__right) == 0; } + + template + inline bool + operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x, + const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y) + { return (__x._M_pos == __y._M_pos && __x._M_root == __y._M_root); } + + template + inline bool + operator!=(const rope<_CharT, _Alloc>& __x, + const rope<_CharT, _Alloc>& __y) + { return !(__x == __y); } + + template + inline bool + operator>(const rope<_CharT, _Alloc>& __x, + const rope<_CharT, _Alloc>& __y) + { return __y < __x; } + + template + inline bool + operator<=(const rope<_CharT, _Alloc>& __x, + const rope<_CharT, _Alloc>& __y) + { return !(__y < __x); } + + template + inline bool + operator>=(const rope<_CharT, _Alloc>& __x, + const rope<_CharT, _Alloc>& __y) + { return !(__x < __y); } + + template + inline bool + operator!=(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x, + const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y) + { return !(__x == __y); } + + template + std::basic_ostream<_CharT, _Traits>& + operator<<(std::basic_ostream<_CharT, _Traits>& __o, + const rope<_CharT, _Alloc>& __r); + + typedef rope crope; + typedef rope wrope; + + inline crope::reference + __mutable_reference_at(crope& __c, size_t __i) + { return __c.mutable_reference_at(__i); } + + inline wrope::reference + __mutable_reference_at(wrope& __c, size_t __i) + { return __c.mutable_reference_at(__i); } + + template + inline void + swap(rope<_CharT, _Alloc>& __x, rope<_CharT, _Alloc>& __y) + { __x.swap(__y); } + + // Hash functions should probably be revisited later: + template<> + struct hash + { + size_t + operator()(const crope& __str) const + { + size_t __size = __str.size(); + + if (0 == __size) + return 0; + return 13 * __str[0] + 5 * __str[__size - 1] + __size; + } + }; + + + template<> + struct hash + { + size_t + operator()(const wrope& __str) const + { + size_t __size = __str.size(); + + if (0 == __size) + return 0; + return 13 * __str[0] + 5 * __str[__size - 1] + __size; + } + }; } // namespace __gnu_cxx diff --git a/libstdc++-v3/include/ext/ropeimpl.h b/libstdc++-v3/include/ext/ropeimpl.h index 5eba107..e9f9271 100644 --- a/libstdc++-v3/include/ext/ropeimpl.h +++ b/libstdc++-v3/include/ext/ropeimpl.h @@ -62,1474 +62,1637 @@ namespace __gnu_cxx using std::_Destroy; using std::uninitialized_fill_n; -// Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf -// if necessary. Assumes _M_path_end[leaf_index] and leaf_pos are correct. -// Results in a valid buf_ptr if the iterator can be legitimately -// dereferenced. -template -void _Rope_iterator_base<_CharT,_Alloc>::_S_setbuf( - _Rope_iterator_base<_CharT,_Alloc>& __x) -{ - const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index]; - size_t __leaf_pos = __x._M_leaf_pos; - size_t __pos = __x._M_current_pos; + // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf + // if necessary. Assumes _M_path_end[leaf_index] and leaf_pos are correct. + // Results in a valid buf_ptr if the iterator can be legitimately + // dereferenced. + template + void + _Rope_iterator_base<_CharT, _Alloc>:: + _S_setbuf(_Rope_iterator_base<_CharT, _Alloc>& __x) + { + const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index]; + size_t __leaf_pos = __x._M_leaf_pos; + size_t __pos = __x._M_current_pos; - switch(__leaf->_M_tag) { + switch(__leaf->_M_tag) + { case _Rope_constants::_S_leaf: - __x._M_buf_start = - ((_Rope_RopeLeaf<_CharT,_Alloc>*)__leaf)->_M_data; - __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos); - __x._M_buf_end = __x._M_buf_start + __leaf->_M_size; - break; + __x._M_buf_start = ((_Rope_RopeLeaf<_CharT, _Alloc>*)__leaf)->_M_data; + __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos); + __x._M_buf_end = __x._M_buf_start + __leaf->_M_size; + break; case _Rope_constants::_S_function: case _Rope_constants::_S_substringfn: - { - size_t __len = _S_iterator_buf_len; - size_t __buf_start_pos = __leaf_pos; - size_t __leaf_end = __leaf_pos + __leaf->_M_size; - char_producer<_CharT>* __fn = - ((_Rope_RopeFunction<_CharT,_Alloc>*)__leaf)->_M_fn; - - if (__buf_start_pos + __len <= __pos) { - __buf_start_pos = __pos - __len/4; - if (__buf_start_pos + __len > __leaf_end) { - __buf_start_pos = __leaf_end - __len; - } - } - if (__buf_start_pos + __len > __leaf_end) { - __len = __leaf_end - __buf_start_pos; - } - (*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf); - __x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos); - __x._M_buf_start = __x._M_tmp_buf; - __x._M_buf_end = __x._M_tmp_buf + __len; - } - break; + { + size_t __len = _S_iterator_buf_len; + size_t __buf_start_pos = __leaf_pos; + size_t __leaf_end = __leaf_pos + __leaf->_M_size; + char_producer<_CharT>* __fn = ((_Rope_RopeFunction<_CharT, + _Alloc>*)__leaf)->_M_fn; + if (__buf_start_pos + __len <= __pos) + { + __buf_start_pos = __pos - __len / 4; + if (__buf_start_pos + __len > __leaf_end) + __buf_start_pos = __leaf_end - __len; + } + if (__buf_start_pos + __len > __leaf_end) + __len = __leaf_end - __buf_start_pos; + (*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf); + __x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos); + __x._M_buf_start = __x._M_tmp_buf; + __x._M_buf_end = __x._M_tmp_buf + __len; + } + break; default: break; + } } -} -// Set path and buffer inside a rope iterator. We assume that -// pos and root are already set. -template -void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache -(_Rope_iterator_base<_CharT,_Alloc>& __x) -{ - const _RopeRep* __path[_Rope_constants::_S_max_rope_depth + 1]; - const _RopeRep* __curr_rope; - int __curr_depth = -1; /* index into path */ - size_t __curr_start_pos = 0; - size_t __pos = __x._M_current_pos; - unsigned char __dirns = 0; // Bit vector marking right turns in the path - - if (__pos >= __x._M_root->_M_size) { - __x._M_buf_ptr = 0; - return; - } - __curr_rope = __x._M_root; - if (0 != __curr_rope->_M_c_string) { - /* Treat the root as a leaf. */ - __x._M_buf_start = __curr_rope->_M_c_string; - __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size; - __x._M_buf_ptr = __curr_rope->_M_c_string + __pos; - __x._M_path_end[0] = __curr_rope; - __x._M_leaf_index = 0; - __x._M_leaf_pos = 0; - return; - } - for(;;) { - ++__curr_depth; - __path[__curr_depth] = __curr_rope; - switch(__curr_rope->_M_tag) { - case _Rope_constants::_S_leaf: - case _Rope_constants::_S_function: - case _Rope_constants::_S_substringfn: - __x._M_leaf_pos = __curr_start_pos; - goto done; - case _Rope_constants::_S_concat: + // Set path and buffer inside a rope iterator. We assume that + // pos and root are already set. + template + void + _Rope_iterator_base<_CharT, _Alloc>:: + _S_setcache(_Rope_iterator_base<_CharT, _Alloc>& __x) + { + const _RopeRep* __path[_Rope_constants::_S_max_rope_depth + 1]; + const _RopeRep* __curr_rope; + int __curr_depth = -1; /* index into path */ + size_t __curr_start_pos = 0; + size_t __pos = __x._M_current_pos; + unsigned char __dirns = 0; // Bit vector marking right turns in the path + + if (__pos >= __x._M_root->_M_size) + { + __x._M_buf_ptr = 0; + return; + } + __curr_rope = __x._M_root; + if (0 != __curr_rope->_M_c_string) + { + /* Treat the root as a leaf. */ + __x._M_buf_start = __curr_rope->_M_c_string; + __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size; + __x._M_buf_ptr = __curr_rope->_M_c_string + __pos; + __x._M_path_end[0] = __curr_rope; + __x._M_leaf_index = 0; + __x._M_leaf_pos = 0; + return; + } + for(;;) + { + ++__curr_depth; + __path[__curr_depth] = __curr_rope; + switch(__curr_rope->_M_tag) { - _Rope_RopeConcatenation<_CharT,_Alloc>* __c = - (_Rope_RopeConcatenation<_CharT,_Alloc>*)__curr_rope; + case _Rope_constants::_S_leaf: + case _Rope_constants::_S_function: + case _Rope_constants::_S_substringfn: + __x._M_leaf_pos = __curr_start_pos; + goto done; + case _Rope_constants::_S_concat: + { + _Rope_RopeConcatenation<_CharT, _Alloc>* __c = + (_Rope_RopeConcatenation<_CharT, _Alloc>*)__curr_rope; _RopeRep* __left = __c->_M_left; size_t __left_len = __left->_M_size; __dirns <<= 1; - if (__pos >= __curr_start_pos + __left_len) { + if (__pos >= __curr_start_pos + __left_len) + { __dirns |= 1; __curr_rope = __c->_M_right; __curr_start_pos += __left_len; - } else { - __curr_rope = __left; - } + } + else + __curr_rope = __left; + } + break; } - break; } - } - done: - // Copy last section of path into _M_path_end. + done: + // Copy last section of path into _M_path_end. { int __i = -1; int __j = __curr_depth + 1 - _S_path_cache_len; if (__j < 0) __j = 0; - while (__j <= __curr_depth) { - __x._M_path_end[++__i] = __path[__j++]; - } + while (__j <= __curr_depth) + __x._M_path_end[++__i] = __path[__j++]; __x._M_leaf_index = __i; } __x._M_path_directions = __dirns; _S_setbuf(__x); -} - -// Specialized version of the above. Assumes that -// the path cache is valid for the previous position. -template -void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache_for_incr -(_Rope_iterator_base<_CharT,_Alloc>& __x) -{ - int __current_index = __x._M_leaf_index; - const _RopeRep* __current_node = __x._M_path_end[__current_index]; - size_t __len = __current_node->_M_size; - size_t __node_start_pos = __x._M_leaf_pos; - unsigned char __dirns = __x._M_path_directions; - _Rope_RopeConcatenation<_CharT,_Alloc>* __c; - - if (__x._M_current_pos - __node_start_pos < __len) { - /* More stuff in this leaf, we just didn't cache it. */ - _S_setbuf(__x); - return; - } - // node_start_pos is starting position of last_node. - while (--__current_index >= 0) { - if (!(__dirns & 1) /* Path turned left */) - break; - __current_node = __x._M_path_end[__current_index]; - __c = (_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node; - // Otherwise we were in the right child. Thus we should pop - // the concatenation node. - __node_start_pos -= __c->_M_left->_M_size; - __dirns >>= 1; - } - if (__current_index < 0) { - // We underflowed the cache. Punt. - _S_setcache(__x); - return; } - __current_node = __x._M_path_end[__current_index]; - __c = (_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node; - // current_node is a concatenation node. We are positioned on the first - // character in its right child. - // node_start_pos is starting position of current_node. - __node_start_pos += __c->_M_left->_M_size; - __current_node = __c->_M_right; - __x._M_path_end[++__current_index] = __current_node; - __dirns |= 1; - while (_Rope_constants::_S_concat == __current_node->_M_tag) { - ++__current_index; - if (_S_path_cache_len == __current_index) { - int __i; - for (__i = 0; __i < _S_path_cache_len-1; __i++) { + + // Specialized version of the above. Assumes that + // the path cache is valid for the previous position. + template + void + _Rope_iterator_base<_CharT, _Alloc>:: + _S_setcache_for_incr(_Rope_iterator_base<_CharT, _Alloc>& __x) + { + int __current_index = __x._M_leaf_index; + const _RopeRep* __current_node = __x._M_path_end[__current_index]; + size_t __len = __current_node->_M_size; + size_t __node_start_pos = __x._M_leaf_pos; + unsigned char __dirns = __x._M_path_directions; + _Rope_RopeConcatenation<_CharT, _Alloc>* __c; + + if (__x._M_current_pos - __node_start_pos < __len) + { + /* More stuff in this leaf, we just didn't cache it. */ + _S_setbuf(__x); + return; + } + // node_start_pos is starting position of last_node. + while (--__current_index >= 0) + { + if (!(__dirns & 1) /* Path turned left */) + break; + __current_node = __x._M_path_end[__current_index]; + __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node; + // Otherwise we were in the right child. Thus we should pop + // the concatenation node. + __node_start_pos -= __c->_M_left->_M_size; + __dirns >>= 1; + } + if (__current_index < 0) + { + // We underflowed the cache. Punt. + _S_setcache(__x); + return; + } + __current_node = __x._M_path_end[__current_index]; + __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node; + // current_node is a concatenation node. We are positioned on the first + // character in its right child. + // node_start_pos is starting position of current_node. + __node_start_pos += __c->_M_left->_M_size; + __current_node = __c->_M_right; + __x._M_path_end[++__current_index] = __current_node; + __dirns |= 1; + while (_Rope_constants::_S_concat == __current_node->_M_tag) + { + ++__current_index; + if (_S_path_cache_len == __current_index) + { + int __i; + for (__i = 0; __i < _S_path_cache_len-1; __i++) __x._M_path_end[__i] = __x._M_path_end[__i+1]; + --__current_index; } - --__current_index; + __current_node = + ((_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node)->_M_left; + __x._M_path_end[__current_index] = __current_node; + __dirns <<= 1; + // node_start_pos is unchanged. } - __current_node = - ((_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node)->_M_left; - __x._M_path_end[__current_index] = __current_node; - __dirns <<= 1; - // node_start_pos is unchanged. - } - __x._M_leaf_index = __current_index; - __x._M_leaf_pos = __node_start_pos; - __x._M_path_directions = __dirns; - _S_setbuf(__x); -} - -template -void _Rope_iterator_base<_CharT,_Alloc>::_M_incr(size_t __n) { - _M_current_pos += __n; - if (0 != _M_buf_ptr) { - size_t __chars_left = _M_buf_end - _M_buf_ptr; - if (__chars_left > __n) { - _M_buf_ptr += __n; - } else if (__chars_left == __n) { - _M_buf_ptr += __n; - _S_setcache_for_incr(*this); - } else { - _M_buf_ptr = 0; - } + __x._M_leaf_index = __current_index; + __x._M_leaf_pos = __node_start_pos; + __x._M_path_directions = __dirns; + _S_setbuf(__x); } -} - -template -void _Rope_iterator_base<_CharT,_Alloc>::_M_decr(size_t __n) { - if (0 != _M_buf_ptr) { - size_t __chars_left = _M_buf_ptr - _M_buf_start; - if (__chars_left >= __n) { - _M_buf_ptr -= __n; - } else { - _M_buf_ptr = 0; - } + + template + void + _Rope_iterator_base<_CharT, _Alloc>:: + _M_incr(size_t __n) + { + _M_current_pos += __n; + if (0 != _M_buf_ptr) + { + size_t __chars_left = _M_buf_end - _M_buf_ptr; + if (__chars_left > __n) + _M_buf_ptr += __n; + else if (__chars_left == __n) + { + _M_buf_ptr += __n; + _S_setcache_for_incr(*this); + } + else + _M_buf_ptr = 0; + } } - _M_current_pos -= __n; -} - -template -void _Rope_iterator<_CharT,_Alloc>::_M_check() { - if (_M_root_rope->_M_tree_ptr != this->_M_root) { - // _Rope was modified. Get things fixed up. - _RopeRep::_S_unref(this->_M_root); - this->_M_root = _M_root_rope->_M_tree_ptr; - _RopeRep::_S_ref(this->_M_root); - this->_M_buf_ptr = 0; + + template + void + _Rope_iterator_base<_CharT, _Alloc>:: + _M_decr(size_t __n) + { + if (0 != _M_buf_ptr) + { + size_t __chars_left = _M_buf_ptr - _M_buf_start; + if (__chars_left >= __n) + _M_buf_ptr -= __n; + else + _M_buf_ptr = 0; + } + _M_current_pos -= __n; } -} - -template -inline -_Rope_const_iterator<_CharT, _Alloc>::_Rope_const_iterator( - const _Rope_iterator<_CharT,_Alloc>& __x) -: _Rope_iterator_base<_CharT,_Alloc>(__x) -{ } - -template -inline _Rope_iterator<_CharT,_Alloc>::_Rope_iterator( - rope<_CharT,_Alloc>& __r, size_t __pos) -: _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos), - _M_root_rope(&__r) -{ - _RopeRep::_S_ref(this->_M_root); -} -template -inline size_t -rope<_CharT,_Alloc>::_S_char_ptr_len(const _CharT* __s) -{ - const _CharT* __p = __s; + template + void + _Rope_iterator<_CharT, _Alloc>:: + _M_check() + { + if (_M_root_rope->_M_tree_ptr != this->_M_root) + { + // _Rope was modified. Get things fixed up. + _RopeRep::_S_unref(this->_M_root); + this->_M_root = _M_root_rope->_M_tree_ptr; + _RopeRep::_S_ref(this->_M_root); + this->_M_buf_ptr = 0; + } + } - while (!_S_is0(*__p)) { ++__p; } - return (__p - __s); -} + template + inline + _Rope_const_iterator<_CharT, _Alloc>:: + _Rope_const_iterator(const _Rope_iterator<_CharT, _Alloc>& __x) + : _Rope_iterator_base<_CharT, _Alloc>(__x) + { } + + template + inline + _Rope_iterator<_CharT, _Alloc>:: + _Rope_iterator(rope<_CharT, _Alloc>& __r, size_t __pos) + : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos), + _M_root_rope(&__r) + { _RopeRep::_S_ref(this->_M_root); } + + template + inline size_t + rope<_CharT, _Alloc>:: + _S_char_ptr_len(const _CharT* __s) + { + const _CharT* __p = __s; + + while (!_S_is0(*__p)) + ++__p; + return (__p - __s); + } #ifndef __GC -template -inline void _Rope_RopeRep<_CharT,_Alloc>::_M_free_c_string() -{ - _CharT* __cstr = _M_c_string; - if (0 != __cstr) { - size_t __size = this->_M_size + 1; - _Destroy(__cstr, __cstr + __size); - this->_Data_deallocate(__cstr, __size); + template + inline void + _Rope_RopeRep<_CharT, _Alloc>:: + _M_free_c_string() + { + _CharT* __cstr = _M_c_string; + if (0 != __cstr) + { + size_t __size = this->_M_size + 1; + _Destroy(__cstr, __cstr + __size); + this->_Data_deallocate(__cstr, __size); + } } -} - -template - inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string(_CharT* __s, - size_t __n, - allocator_type __a) -{ - if (!_S_is_basic_char_type((_CharT*)0)) { + template + inline void + _Rope_RopeRep<_CharT, _Alloc>:: + _S_free_string(_CharT* __s, size_t __n, allocator_type __a) + { + if (!_S_is_basic_char_type((_CharT*)0)) _Destroy(__s, __s + __n); + + // This has to be a static member, so this gets a bit messy + __a.deallocate(__s, + _Rope_RopeLeaf<_CharT, _Alloc>::_S_rounded_up_size(__n)); } -// This has to be a static member, so this gets a bit messy - __a.deallocate( - __s, _Rope_RopeLeaf<_CharT,_Alloc>::_S_rounded_up_size(__n)); -} - - -// There are several reasons for not doing this with virtual destructors -// and a class specific delete operator: -// - A class specific delete operator can't easily get access to -// allocator instances if we need them. -// - Any virtual function would need a 4 or byte vtable pointer; -// this only requires a one byte tag per object. -template -void _Rope_RopeRep<_CharT,_Alloc>::_M_free_tree() -{ - switch(_M_tag) { + + // There are several reasons for not doing this with virtual destructors + // and a class specific delete operator: + // - A class specific delete operator can't easily get access to + // allocator instances if we need them. + // - Any virtual function would need a 4 or byte vtable pointer; + // this only requires a one byte tag per object. + template + void + _Rope_RopeRep<_CharT, _Alloc>:: + _M_free_tree() + { + switch(_M_tag) + { case _Rope_constants::_S_leaf: - { - _Rope_RopeLeaf<_CharT,_Alloc>* __l - = (_Rope_RopeLeaf<_CharT,_Alloc>*)this; - __l->_Rope_RopeLeaf<_CharT,_Alloc>::~_Rope_RopeLeaf(); - _L_deallocate(__l, 1); - break; - } + { + _Rope_RopeLeaf<_CharT, _Alloc>* __l + = (_Rope_RopeLeaf<_CharT, _Alloc>*)this; + __l->_Rope_RopeLeaf<_CharT, _Alloc>::~_Rope_RopeLeaf(); + _L_deallocate(__l, 1); + break; + } case _Rope_constants::_S_concat: - { - _Rope_RopeConcatenation<_CharT,_Alloc>* __c - = (_Rope_RopeConcatenation<_CharT,_Alloc>*)this; - __c->_Rope_RopeConcatenation<_CharT,_Alloc>:: - ~_Rope_RopeConcatenation(); - _C_deallocate(__c, 1); - break; - } + { + _Rope_RopeConcatenation<_CharT,_Alloc>* __c + = (_Rope_RopeConcatenation<_CharT, _Alloc>*)this; + __c->_Rope_RopeConcatenation<_CharT, _Alloc>:: + ~_Rope_RopeConcatenation(); + _C_deallocate(__c, 1); + break; + } case _Rope_constants::_S_function: - { - _Rope_RopeFunction<_CharT,_Alloc>* __f - = (_Rope_RopeFunction<_CharT,_Alloc>*)this; - __f->_Rope_RopeFunction<_CharT,_Alloc>::~_Rope_RopeFunction(); - _F_deallocate(__f, 1); - break; - } + { + _Rope_RopeFunction<_CharT, _Alloc>* __f + = (_Rope_RopeFunction<_CharT, _Alloc>*)this; + __f->_Rope_RopeFunction<_CharT, _Alloc>::~_Rope_RopeFunction(); + _F_deallocate(__f, 1); + break; + } case _Rope_constants::_S_substringfn: - { - _Rope_RopeSubstring<_CharT,_Alloc>* __ss = - (_Rope_RopeSubstring<_CharT,_Alloc>*)this; - __ss->_Rope_RopeSubstring<_CharT,_Alloc>:: - ~_Rope_RopeSubstring(); - _S_deallocate(__ss, 1); - break; - } + { + _Rope_RopeSubstring<_CharT, _Alloc>* __ss = + (_Rope_RopeSubstring<_CharT, _Alloc>*)this; + __ss->_Rope_RopeSubstring<_CharT, _Alloc>:: + ~_Rope_RopeSubstring(); + _S_deallocate(__ss, 1); + break; + } + } } -} #else -template - inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string - (const _CharT*, size_t, allocator_type) -{} + template + inline void + _Rope_RopeRep<_CharT, _Alloc>:: + _S_free_string(const _CharT*, size_t, allocator_type) + { } #endif - -// Concatenate a C string onto a leaf rope by copying the rope data. -// Used for short ropes. -template -typename rope<_CharT,_Alloc>::_RopeLeaf* -rope<_CharT,_Alloc>::_S_leaf_concat_char_iter - (_RopeLeaf* __r, const _CharT* __iter, size_t __len) -{ - size_t __old_len = __r->_M_size; - _CharT* __new_data = (_CharT*) - _Data_allocate(_S_rounded_up_size(__old_len + __len)); - _RopeLeaf* __result; - - uninitialized_copy_n(__r->_M_data, __old_len, __new_data); - uninitialized_copy_n(__iter, __len, __new_data + __old_len); - _S_cond_store_eos(__new_data[__old_len + __len]); - try { - __result = _S_new_RopeLeaf(__new_data, __old_len + __len, - __r->get_allocator()); + // Concatenate a C string onto a leaf rope by copying the rope data. + // Used for short ropes. + template + typename rope<_CharT, _Alloc>::_RopeLeaf* + rope<_CharT, _Alloc>:: + _S_leaf_concat_char_iter(_RopeLeaf* __r, const _CharT* __iter, size_t __len) + { + size_t __old_len = __r->_M_size; + _CharT* __new_data = (_CharT*) + _Data_allocate(_S_rounded_up_size(__old_len + __len)); + _RopeLeaf* __result; + + uninitialized_copy_n(__r->_M_data, __old_len, __new_data); + uninitialized_copy_n(__iter, __len, __new_data + __old_len); + _S_cond_store_eos(__new_data[__old_len + __len]); + try + { + __result = _S_new_RopeLeaf(__new_data, __old_len + __len, + __r->get_allocator()); + } + catch(...) + { + _RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len, + __r->get_allocator()); + __throw_exception_again; + } + return __result; } - catch(...) - { - _RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len, - __r->get_allocator()); - __throw_exception_again; - } - return __result; -} #ifndef __GC -// As above, but it's OK to clobber original if refcount is 1 -template -typename rope<_CharT,_Alloc>::_RopeLeaf* -rope<_CharT,_Alloc>::_S_destr_leaf_concat_char_iter - (_RopeLeaf* __r, const _CharT* __iter, size_t __len) -{ - if (__r->_M_ref_count > 1) - return _S_leaf_concat_char_iter(__r, __iter, __len); - size_t __old_len = __r->_M_size; - if (_S_allocated_capacity(__old_len) >= __old_len + __len) { - // The space has been partially initialized for the standard - // character types. But that doesn't matter for those types. - uninitialized_copy_n(__iter, __len, __r->_M_data + __old_len); - if (_S_is_basic_char_type((_CharT*)0)) { + // As above, but it's OK to clobber original if refcount is 1 + template + typename rope<_CharT,_Alloc>::_RopeLeaf* + rope<_CharT, _Alloc>:: + _S_destr_leaf_concat_char_iter(_RopeLeaf* __r, const _CharT* __iter, + size_t __len) + { + if (__r->_M_ref_count > 1) + return _S_leaf_concat_char_iter(__r, __iter, __len); + size_t __old_len = __r->_M_size; + if (_S_allocated_capacity(__old_len) >= __old_len + __len) + { + // The space has been partially initialized for the standard + // character types. But that doesn't matter for those types. + uninitialized_copy_n(__iter, __len, __r->_M_data + __old_len); + if (_S_is_basic_char_type((_CharT*)0)) _S_cond_store_eos(__r->_M_data[__old_len + __len]); - } else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string) { - __r->_M_free_c_string(); - __r->_M_c_string = 0; + else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string) + { + __r->_M_free_c_string(); + __r->_M_c_string = 0; + } + __r->_M_size = __old_len + __len; + __r->_M_ref_count = 2; + return __r; + } + else + { + _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len); + return __result; } - __r->_M_size = __old_len + __len; - __r->_M_ref_count = 2; - return __r; - } else { - _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len); - return __result; } -} #endif -// Assumes left and right are not 0. -// Does not increment (nor decrement on exception) child reference counts. -// Result has ref count 1. -template -typename rope<_CharT,_Alloc>::_RopeRep* -rope<_CharT,_Alloc>::_S_tree_concat (_RopeRep* __left, _RopeRep* __right) -{ - _RopeConcatenation* __result = _S_new_RopeConcatenation(__left, __right, - __left->get_allocator()); - size_t __depth = __result->_M_depth; - - if (__depth > 20 && (__result->_M_size < 1000 || - __depth > _Rope_constants::_S_max_rope_depth)) + // Assumes left and right are not 0. + // Does not increment (nor decrement on exception) child reference counts. + // Result has ref count 1. + template + typename rope<_CharT, _Alloc>::_RopeRep* + rope<_CharT, _Alloc>:: + _S_tree_concat(_RopeRep* __left, _RopeRep* __right) { - _RopeRep* __balanced; + _RopeConcatenation* __result = _S_new_RopeConcatenation(__left, __right, + __left-> + get_allocator()); + size_t __depth = __result->_M_depth; + + if (__depth > 20 && (__result->_M_size < 1000 + || __depth > _Rope_constants::_S_max_rope_depth)) + { + _RopeRep* __balanced; + + try + { + __balanced = _S_balance(__result); + __result->_M_unref_nonnil(); + } + catch(...) + { + _C_deallocate(__result,1); + __throw_exception_again; + } + // In case of exception, we need to deallocate + // otherwise dangling result node. But caller + // still owns its children. Thus unref is + // inappropriate. + return __balanced; + } + else + return __result; + } + template + typename rope<_CharT, _Alloc>::_RopeRep* + rope<_CharT, _Alloc>:: + _S_concat_char_iter(_RopeRep* __r, const _CharT*__s, size_t __slen) + { + _RopeRep* __result; + if (0 == __slen) + { + _S_ref(__r); + return __r; + } + if (0 == __r) + return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, + __r->get_allocator()); + if (_Rope_constants::_S_leaf == __r->_M_tag + && __r->_M_size + __slen <= _S_copy_max) + { + __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen); + return __result; + } + if (_Rope_constants::_S_concat == __r->_M_tag + && _Rope_constants::_S_leaf == ((_RopeConcatenation*) + __r)->_M_right->_M_tag) + { + _RopeLeaf* __right = + (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right); + if (__right->_M_size + __slen <= _S_copy_max) + { + _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left; + _RopeRep* __nright = + _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen); + __left->_M_ref_nonnil(); + try + { __result = _S_tree_concat(__left, __nright); } + catch(...) + { + _S_unref(__left); + _S_unref(__nright); + __throw_exception_again; + } + return __result; + } + } + _RopeRep* __nright = + __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator()); try { - __balanced = _S_balance(__result); - __result->_M_unref_nonnil(); - } + __r->_M_ref_nonnil(); + __result = _S_tree_concat(__r, __nright); + } catch(...) { - _C_deallocate(__result,1); + _S_unref(__r); + _S_unref(__nright); __throw_exception_again; } - // In case of exception, we need to deallocate - // otherwise dangling result node. But caller - // still owns its children. Thus unref is - // inappropriate. - return __balanced; - } - else - return __result; -} - -template -typename -rope<_CharT,_Alloc>::_RopeRep* rope<_CharT,_Alloc>::_S_concat_char_iter - (_RopeRep* __r, const _CharT*__s, size_t __slen) -{ - _RopeRep* __result; - if (0 == __slen) { - _S_ref(__r); - return __r; - } - if (0 == __r) - return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, - __r->get_allocator()); - if (_Rope_constants::_S_leaf == __r->_M_tag && - __r->_M_size + __slen <= _S_copy_max) { - __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen); - return __result; + return __result; } - if (_Rope_constants::_S_concat == __r->_M_tag - && _Rope_constants::_S_leaf == ((_RopeConcatenation*)__r)->_M_right->_M_tag) { - _RopeLeaf* __right = - (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right); - if (__right->_M_size + __slen <= _S_copy_max) { - _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left; - _RopeRep* __nright = - _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen); - __left->_M_ref_nonnil(); - try { - __result = _S_tree_concat(__left, __nright); - } - catch(...) + +#ifndef __GC + template + typename rope<_CharT,_Alloc>::_RopeRep* + rope<_CharT,_Alloc>:: + _S_destr_concat_char_iter(_RopeRep* __r, const _CharT* __s, size_t __slen) + { + _RopeRep* __result; + if (0 == __r) + return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, + __r->get_allocator()); + size_t __count = __r->_M_ref_count; + size_t __orig_size = __r->_M_size; + if (__count > 1) + return _S_concat_char_iter(__r, __s, __slen); + if (0 == __slen) + { + __r->_M_ref_count = 2; // One more than before + return __r; + } + if (__orig_size + __slen <= _S_copy_max + && _Rope_constants::_S_leaf == __r->_M_tag) + { + __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, + __slen); + return __result; + } + if (_Rope_constants::_S_concat == __r->_M_tag) + { + _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*) + __r)->_M_right); + if (_Rope_constants::_S_leaf == __right->_M_tag + && __right->_M_size + __slen <= _S_copy_max) { - _S_unref(__left); - _S_unref(__nright); - __throw_exception_again; + _RopeRep* __new_right = + _S_destr_leaf_concat_char_iter(__right, __s, __slen); + if (__right == __new_right) + __new_right->_M_ref_count = 1; + else + __right->_M_unref_nonnil(); + __r->_M_ref_count = 2; // One more than before. + ((_RopeConcatenation*)__r)->_M_right = __new_right; + __r->_M_size = __orig_size + __slen; + if (0 != __r->_M_c_string) + { + __r->_M_free_c_string(); + __r->_M_c_string = 0; + } + return __r; } - return __result; } - } - _RopeRep* __nright = - __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator()); - try { + _RopeRep* __right = + __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator()); __r->_M_ref_nonnil(); - __result = _S_tree_concat(__r, __nright); - } - catch(...) - { - _S_unref(__r); - _S_unref(__nright); - __throw_exception_again; - } - return __result; -} - -#ifndef __GC -template -typename rope<_CharT,_Alloc>::_RopeRep* -rope<_CharT,_Alloc>::_S_destr_concat_char_iter( - _RopeRep* __r, const _CharT* __s, size_t __slen) -{ - _RopeRep* __result; - if (0 == __r) - return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, - __r->get_allocator()); - size_t __count = __r->_M_ref_count; - size_t __orig_size = __r->_M_size; - if (__count > 1) return _S_concat_char_iter(__r, __s, __slen); - if (0 == __slen) { - __r->_M_ref_count = 2; // One more than before - return __r; - } - if (__orig_size + __slen <= _S_copy_max && - _Rope_constants::_S_leaf == __r->_M_tag) { - __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen); - return __result; - } - if (_Rope_constants::_S_concat == __r->_M_tag) { - _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*)__r)->_M_right); - if (_Rope_constants::_S_leaf == __right->_M_tag - && __right->_M_size + __slen <= _S_copy_max) { - _RopeRep* __new_right = - _S_destr_leaf_concat_char_iter(__right, __s, __slen); - if (__right == __new_right) - __new_right->_M_ref_count = 1; - else - __right->_M_unref_nonnil(); - __r->_M_ref_count = 2; // One more than before. - ((_RopeConcatenation*)__r)->_M_right = __new_right; - __r->_M_size = __orig_size + __slen; - if (0 != __r->_M_c_string) { - __r->_M_free_c_string(); - __r->_M_c_string = 0; - } - return __r; + try + { __result = _S_tree_concat(__r, __right); } + catch(...) + { + _S_unref(__r); + _S_unref(__right); + __throw_exception_again; } + return __result; } - _RopeRep* __right = - __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator()); - __r->_M_ref_nonnil(); - try { - __result = _S_tree_concat(__r, __right); - } - catch(...) - { - _S_unref(__r); - _S_unref(__right); - __throw_exception_again; - } - return __result; -} #endif /* !__GC */ - -template -typename rope<_CharT,_Alloc>::_RopeRep* -rope<_CharT,_Alloc>::_S_concat(_RopeRep* __left, _RopeRep* __right) -{ - if (0 == __left) { - _S_ref(__right); - return __right; - } - if (0 == __right) { - __left->_M_ref_nonnil(); - return __left; - } - if (_Rope_constants::_S_leaf == __right->_M_tag) { - if (_Rope_constants::_S_leaf == __left->_M_tag) { - if (__right->_M_size + __left->_M_size <= _S_copy_max) { - return _S_leaf_concat_char_iter((_RopeLeaf*)__left, - ((_RopeLeaf*)__right)->_M_data, - __right->_M_size); - } - } else if (_Rope_constants::_S_concat == __left->_M_tag - && _Rope_constants::_S_leaf == - ((_RopeConcatenation*)__left)->_M_right->_M_tag) { - _RopeLeaf* __leftright = - (_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right); - if (__leftright->_M_size + __right->_M_size <= _S_copy_max) { - _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left; - _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright, - ((_RopeLeaf*)__right)->_M_data, - __right->_M_size); - __leftleft->_M_ref_nonnil(); - try { - return(_S_tree_concat(__leftleft, __rest)); - } - catch(...) - { - _S_unref(__leftleft); - _S_unref(__rest); - __throw_exception_again; - } - } + + template + typename rope<_CharT, _Alloc>::_RopeRep* + rope<_CharT, _Alloc>:: + _S_concat(_RopeRep* __left, _RopeRep* __right) + { + if (0 == __left) + { + _S_ref(__right); + return __right; + } + if (0 == __right) + { + __left->_M_ref_nonnil(); + return __left; + } + if (_Rope_constants::_S_leaf == __right->_M_tag) + { + if (_Rope_constants::_S_leaf == __left->_M_tag) + { + if (__right->_M_size + __left->_M_size <= _S_copy_max) + return _S_leaf_concat_char_iter((_RopeLeaf*)__left, + ((_RopeLeaf*)__right)->_M_data, + __right->_M_size); + } + else if (_Rope_constants::_S_concat == __left->_M_tag + && _Rope_constants::_S_leaf == ((_RopeConcatenation*) + __left)->_M_right->_M_tag) + { + _RopeLeaf* __leftright = + (_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right); + if (__leftright->_M_size + __right->_M_size <= _S_copy_max) + { + _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left; + _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright, + ((_RopeLeaf*) + __right)-> + _M_data, + __right->_M_size); + __leftleft->_M_ref_nonnil(); + try + { return(_S_tree_concat(__leftleft, __rest)); } + catch(...) + { + _S_unref(__leftleft); + _S_unref(__rest); + __throw_exception_again; + } + } + } + } + __left->_M_ref_nonnil(); + __right->_M_ref_nonnil(); + try + { return(_S_tree_concat(__left, __right)); } + catch(...) + { + _S_unref(__left); + _S_unref(__right); + __throw_exception_again; } } - __left->_M_ref_nonnil(); - __right->_M_ref_nonnil(); - try { - return(_S_tree_concat(__left, __right)); - } - catch(...) - { - _S_unref(__left); - _S_unref(__right); - __throw_exception_again; - } -} - -template -typename rope<_CharT,_Alloc>::_RopeRep* -rope<_CharT,_Alloc>::_S_substring(_RopeRep* __base, - size_t __start, size_t __endp1) -{ - if (0 == __base) return 0; - size_t __len = __base->_M_size; - size_t __adj_endp1; - const size_t __lazy_threshold = 128; - - if (__endp1 >= __len) { - if (0 == __start) { - __base->_M_ref_nonnil(); - return __base; - } else { + + template + typename rope<_CharT, _Alloc>::_RopeRep* + rope<_CharT, _Alloc>:: + _S_substring(_RopeRep* __base, size_t __start, size_t __endp1) + { + if (0 == __base) + return 0; + size_t __len = __base->_M_size; + size_t __adj_endp1; + const size_t __lazy_threshold = 128; + + if (__endp1 >= __len) + { + if (0 == __start) + { + __base->_M_ref_nonnil(); + return __base; + } + else __adj_endp1 = __len; + } - } else { + else __adj_endp1 = __endp1; - } - switch(__base->_M_tag) { + + switch(__base->_M_tag) + { case _Rope_constants::_S_concat: { - _RopeConcatenation* __c = (_RopeConcatenation*)__base; - _RopeRep* __left = __c->_M_left; - _RopeRep* __right = __c->_M_right; - size_t __left_len = __left->_M_size; - _RopeRep* __result; - - if (__adj_endp1 <= __left_len) { - return _S_substring(__left, __start, __endp1); - } else if (__start >= __left_len) { - return _S_substring(__right, __start - __left_len, - __adj_endp1 - __left_len); - } - _Self_destruct_ptr __left_result( - _S_substring(__left, __start, __left_len)); - _Self_destruct_ptr __right_result( - _S_substring(__right, 0, __endp1 - __left_len)); - __result = _S_concat(__left_result, __right_result); - return __result; + _RopeConcatenation* __c = (_RopeConcatenation*)__base; + _RopeRep* __left = __c->_M_left; + _RopeRep* __right = __c->_M_right; + size_t __left_len = __left->_M_size; + _RopeRep* __result; + + if (__adj_endp1 <= __left_len) + return _S_substring(__left, __start, __endp1); + else if (__start >= __left_len) + return _S_substring(__right, __start - __left_len, + __adj_endp1 - __left_len); + _Self_destruct_ptr __left_result(_S_substring(__left, + __start, + __left_len)); + _Self_destruct_ptr __right_result(_S_substring(__right, 0, + __endp1 + - __left_len)); + __result = _S_concat(__left_result, __right_result); + return __result; } case _Rope_constants::_S_leaf: - { - _RopeLeaf* __l = (_RopeLeaf*)__base; - _RopeLeaf* __result; - size_t __result_len; - if (__start >= __adj_endp1) return 0; - __result_len = __adj_endp1 - __start; - if (__result_len > __lazy_threshold) goto lazy; -# ifdef __GC - const _CharT* __section = __l->_M_data + __start; - __result = _S_new_RopeLeaf(__section, __result_len, - __base->get_allocator()); - __result->_M_c_string = 0; // Not eos terminated. -# else - // We should sometimes create substring node instead. - __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR( - __l->_M_data + __start, __result_len, - __base->get_allocator()); -# endif - return __result; - } + { + _RopeLeaf* __l = (_RopeLeaf*)__base; + _RopeLeaf* __result; + size_t __result_len; + if (__start >= __adj_endp1) + return 0; + __result_len = __adj_endp1 - __start; + if (__result_len > __lazy_threshold) + goto lazy; +#ifdef __GC + const _CharT* __section = __l->_M_data + __start; + __result = _S_new_RopeLeaf(__section, __result_len, + __base->get_allocator()); + __result->_M_c_string = 0; // Not eos terminated. +#else + // We should sometimes create substring node instead. + __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__l->_M_data + __start, + __result_len, + __base-> + get_allocator()); +#endif + return __result; + } case _Rope_constants::_S_substringfn: - // Avoid introducing multiple layers of substring nodes. - { - _RopeSubstring* __old = (_RopeSubstring*)__base; - size_t __result_len; - if (__start >= __adj_endp1) return 0; - __result_len = __adj_endp1 - __start; - if (__result_len > __lazy_threshold) { - _RopeSubstring* __result = - _S_new_RopeSubstring(__old->_M_base, - __start + __old->_M_start, - __adj_endp1 - __start, - __base->get_allocator()); - return __result; - - } // *** else fall through: *** - } - case _Rope_constants::_S_function: - { - _RopeFunction* __f = (_RopeFunction*)__base; - _CharT* __section; - size_t __result_len; - if (__start >= __adj_endp1) return 0; - __result_len = __adj_endp1 - __start; - - if (__result_len > __lazy_threshold) goto lazy; - __section = (_CharT*) - _Data_allocate(_S_rounded_up_size(__result_len)); - try { - (*(__f->_M_fn))(__start, __result_len, __section); - } - catch(...) - { - _RopeRep::__STL_FREE_STRING( - __section, __result_len, __base->get_allocator()); - __throw_exception_again; - } - _S_cond_store_eos(__section[__result_len]); - return _S_new_RopeLeaf(__section, __result_len, + // Avoid introducing multiple layers of substring nodes. + { + _RopeSubstring* __old = (_RopeSubstring*)__base; + size_t __result_len; + if (__start >= __adj_endp1) + return 0; + __result_len = __adj_endp1 - __start; + if (__result_len > __lazy_threshold) + { + _RopeSubstring* __result = + _S_new_RopeSubstring(__old->_M_base, + __start + __old->_M_start, + __adj_endp1 - __start, __base->get_allocator()); - } - } - lazy: - { + return __result; + + } // *** else fall through: *** + } + case _Rope_constants::_S_function: + { + _RopeFunction* __f = (_RopeFunction*)__base; + _CharT* __section; + size_t __result_len; + if (__start >= __adj_endp1) + return 0; + __result_len = __adj_endp1 - __start; + + if (__result_len > __lazy_threshold) + goto lazy; + __section = (_CharT*) + _Data_allocate(_S_rounded_up_size(__result_len)); + try + { (*(__f->_M_fn))(__start, __result_len, __section); } + catch(...) + { + _RopeRep::__STL_FREE_STRING(__section, __result_len, + __base->get_allocator()); + __throw_exception_again; + } + _S_cond_store_eos(__section[__result_len]); + return _S_new_RopeLeaf(__section, __result_len, + __base->get_allocator()); + } + } + lazy: + { // Create substring node. return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start, - __base->get_allocator()); + __base->get_allocator()); + } } -} -template -class _Rope_flatten_char_consumer : public _Rope_char_consumer<_CharT> { + template + class _Rope_flatten_char_consumer + : public _Rope_char_consumer<_CharT> + { private: - _CharT* _M_buf_ptr; + _CharT* _M_buf_ptr; public: + + _Rope_flatten_char_consumer(_CharT* __buffer) + { _M_buf_ptr = __buffer; }; + + ~_Rope_flatten_char_consumer() {} + + bool + operator()(const _CharT* __leaf, size_t __n) + { + uninitialized_copy_n(__leaf, __n, _M_buf_ptr); + _M_buf_ptr += __n; + return true; + } + }; - _Rope_flatten_char_consumer(_CharT* __buffer) { - _M_buf_ptr = __buffer; - }; - ~_Rope_flatten_char_consumer() {} - bool operator() (const _CharT* __leaf, size_t __n) { - uninitialized_copy_n(__leaf, __n, _M_buf_ptr); - _M_buf_ptr += __n; - return true; - } -}; - -template -class _Rope_find_char_char_consumer : public _Rope_char_consumer<_CharT> { + template + class _Rope_find_char_char_consumer + : public _Rope_char_consumer<_CharT> + { private: - _CharT _M_pattern; + _CharT _M_pattern; public: - size_t _M_count; // Number of nonmatching characters - _Rope_find_char_char_consumer(_CharT __p) - : _M_pattern(__p), _M_count(0) {} - ~_Rope_find_char_char_consumer() {} - bool operator() (const _CharT* __leaf, size_t __n) { - size_t __i; - for (__i = 0; __i < __n; __i++) { - if (__leaf[__i] == _M_pattern) { - _M_count += __i; return false; - } - } - _M_count += __n; return true; - } -}; + size_t _M_count; // Number of nonmatching characters + + _Rope_find_char_char_consumer(_CharT __p) + : _M_pattern(__p), _M_count(0) {} + + ~_Rope_find_char_char_consumer() {} + + bool + operator()(const _CharT* __leaf, size_t __n) + { + size_t __i; + for (__i = 0; __i < __n; __i++) + { + if (__leaf[__i] == _M_pattern) + { + _M_count += __i; + return false; + } + } + _M_count += __n; return true; + } + }; template // Here _CharT is both the stream and rope character type. -class _Rope_insert_char_consumer : public _Rope_char_consumer<_CharT> { + class _Rope_insert_char_consumer + : public _Rope_char_consumer<_CharT> + { private: - typedef basic_ostream<_CharT,_Traits> _Insert_ostream; - _Insert_ostream& _M_o; + typedef basic_ostream<_CharT,_Traits> _Insert_ostream; + _Insert_ostream& _M_o; public: - _Rope_insert_char_consumer(_Insert_ostream& __writer) - : _M_o(__writer) {}; - ~_Rope_insert_char_consumer() { }; - // Caller is presumed to own the ostream - bool operator() (const _CharT* __leaf, size_t __n); - // Returns true to continue traversal. -}; - -template -bool _Rope_insert_char_consumer<_CharT, _Traits>::operator() - (const _CharT* __leaf, size_t __n) -{ - size_t __i; - // We assume that formatting is set up correctly for each element. - for (__i = 0; __i < __n; __i++) _M_o.put(__leaf[__i]); - return true; -} - -template -bool rope<_CharT, _Alloc>::_S_apply_to_pieces( - _Rope_char_consumer<_CharT>& __c, - const _RopeRep* __r, - size_t __begin, size_t __end) -{ - if (0 == __r) return true; - switch(__r->_M_tag) { + _Rope_insert_char_consumer(_Insert_ostream& __writer) + : _M_o(__writer) {}; + ~_Rope_insert_char_consumer() { }; + // Caller is presumed to own the ostream + bool operator() (const _CharT* __leaf, size_t __n); + // Returns true to continue traversal. + }; + + template + bool + _Rope_insert_char_consumer<_CharT, _Traits>:: + operator()(const _CharT* __leaf, size_t __n) + { + size_t __i; + // We assume that formatting is set up correctly for each element. + for (__i = 0; __i < __n; __i++) + _M_o.put(__leaf[__i]); + return true; + } + + template + bool + rope<_CharT, _Alloc>:: + _S_apply_to_pieces(_Rope_char_consumer<_CharT>& __c, + const _RopeRep* __r, size_t __begin, size_t __end) + { + if (0 == __r) + return true; + switch(__r->_M_tag) + { case _Rope_constants::_S_concat: - { - _RopeConcatenation* __conc = (_RopeConcatenation*)__r; - _RopeRep* __left = __conc->_M_left; - size_t __left_len = __left->_M_size; - if (__begin < __left_len) { - size_t __left_end = std::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 = std::max(__left_len, __begin); - if (!_S_apply_to_pieces(__c, __right, - __right_start - __left_len, - __end - __left_len)) { - return false; - } - } - } - return true; - case _Rope_constants::_S_leaf: - { - _RopeLeaf* __l = (_RopeLeaf*)__r; - return __c(__l->_M_data + __begin, __end - __begin); - } + { + _RopeConcatenation* __conc = (_RopeConcatenation*)__r; + _RopeRep* __left = __conc->_M_left; + size_t __left_len = __left->_M_size; + if (__begin < __left_len) + { + size_t __left_end = std::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 = std::max(__left_len, __begin); + if (!_S_apply_to_pieces(__c, __right, + __right_start - __left_len, + __end - __left_len)) + return false; + } + } + return true; + case _Rope_constants::_S_leaf: + { + _RopeLeaf* __l = (_RopeLeaf*)__r; + return __c(__l->_M_data + __begin, __end - __begin); + } case _Rope_constants::_S_function: case _Rope_constants::_S_substringfn: { - _RopeFunction* __f = (_RopeFunction*)__r; - size_t __len = __end - __begin; - bool __result; - _CharT* __buffer = - (_CharT*)_Alloc().allocate(__len * sizeof(_CharT)); - try { + _RopeFunction* __f = (_RopeFunction*)__r; + size_t __len = __end - __begin; + bool __result; + _CharT* __buffer = + (_CharT*)_Alloc().allocate(__len * sizeof(_CharT)); + try + { (*(__f->_M_fn))(__begin, __len, __buffer); __result = __c(__buffer, __len); _Alloc().deallocate(__buffer, __len * sizeof(_CharT)); } - catch(...) - { - _Alloc().deallocate(__buffer, __len * sizeof(_CharT)); - __throw_exception_again; - } - return __result; + catch(...) + { + _Alloc().deallocate(__buffer, __len * sizeof(_CharT)); + __throw_exception_again; + } + return __result; } default: return false; + } } -} template - inline void _Rope_fill(basic_ostream<_CharT, _Traits>& __o, size_t __n) -{ - char __f = __o.fill(); - size_t __i; + inline void + _Rope_fill(basic_ostream<_CharT, _Traits>& __o, size_t __n) + { + char __f = __o.fill(); + size_t __i; + + for (__i = 0; __i < __n; __i++) + __o.put(__f); + } - for (__i = 0; __i < __n; __i++) __o.put(__f); -} + template + inline bool + _Rope_is_simple(_CharT*) + { return false; } -template inline bool _Rope_is_simple(_CharT*) { return false; } -inline bool _Rope_is_simple(char*) { return true; } -inline bool _Rope_is_simple(wchar_t*) { return true; } + inline bool + _Rope_is_simple(char*) + { return true; } -template -basic_ostream<_CharT, _Traits>& operator<< (basic_ostream<_CharT, _Traits>& __o, - const rope<_CharT, _Alloc>& __r) -{ - size_t __w = __o.width(); - bool __left = bool(__o.flags() & std::ios::left); - size_t __pad_len; - size_t __rope_len = __r.size(); - _Rope_insert_char_consumer<_CharT, _Traits> __c(__o); - bool __is_simple = _Rope_is_simple((_CharT*)0); + inline bool + _Rope_is_simple(wchar_t*) + { return true; } - if (__rope_len < __w) { + template + basic_ostream<_CharT, _Traits>& + operator<<(basic_ostream<_CharT, _Traits>& __o, + const rope<_CharT, _Alloc>& __r) + { + size_t __w = __o.width(); + bool __left = bool(__o.flags() & std::ios::left); + size_t __pad_len; + size_t __rope_len = __r.size(); + _Rope_insert_char_consumer<_CharT, _Traits> __c(__o); + bool __is_simple = _Rope_is_simple((_CharT*)0); + + if (__rope_len < __w) __pad_len = __w - __rope_len; - } else { + else __pad_len = 0; - } - if (!__is_simple) __o.width(__w/__rope_len); - try { - if (__is_simple && !__left && __pad_len > 0) { - _Rope_fill(__o, __pad_len); - } - __r.apply_to_pieces(0, __r.size(), __c); - if (__is_simple && __left && __pad_len > 0) { - _Rope_fill(__o, __pad_len); - } + if (!__is_simple) - __o.width(__w); + __o.width(__w / __rope_len); + try + { + if (__is_simple && !__left && __pad_len > 0) + _Rope_fill(__o, __pad_len); + __r.apply_to_pieces(0, __r.size(), __c); + if (__is_simple && __left && __pad_len > 0) + _Rope_fill(__o, __pad_len); + if (!__is_simple) + __o.width(__w); + } + catch(...) + { + if (!__is_simple) + __o.width(__w); + __throw_exception_again; + } + return __o; } - catch(...) - { - if (!__is_simple) - __o.width(__w); - __throw_exception_again; - } - return __o; -} - -template -_CharT* -rope<_CharT,_Alloc>::_S_flatten(_RopeRep* __r, - size_t __start, size_t __len, - _CharT* __buffer) -{ - _Rope_flatten_char_consumer<_CharT> __c(__buffer); - _S_apply_to_pieces(__c, __r, __start, __start + __len); - return(__buffer + __len); -} - -template -size_t -rope<_CharT,_Alloc>::find(_CharT __pattern, size_t __start) const -{ - _Rope_find_char_char_consumer<_CharT> __c(__pattern); - _S_apply_to_pieces(__c, this->_M_tree_ptr, __start, size()); - size_type __result_pos = __start + __c._M_count; -# ifndef __STL_OLD_ROPE_SEMANTICS - if (__result_pos == size()) __result_pos = npos; -# endif - return __result_pos; -} - -template -_CharT* -rope<_CharT,_Alloc>::_S_flatten(_RopeRep* __r, _CharT* __buffer) -{ - if (0 == __r) return __buffer; - switch(__r->_M_tag) { + + template + _CharT* + rope<_CharT, _Alloc>:: + _S_flatten(_RopeRep* __r, size_t __start, size_t __len, + _CharT* __buffer) + { + _Rope_flatten_char_consumer<_CharT> __c(__buffer); + _S_apply_to_pieces(__c, __r, __start, __start + __len); + return(__buffer + __len); + } + + template + size_t + rope<_CharT, _Alloc>:: + find(_CharT __pattern, size_t __start) const + { + _Rope_find_char_char_consumer<_CharT> __c(__pattern); + _S_apply_to_pieces(__c, this->_M_tree_ptr, __start, size()); + size_type __result_pos = __start + __c._M_count; +#ifndef __STL_OLD_ROPE_SEMANTICS + if (__result_pos == size()) + __result_pos = npos; +#endif + return __result_pos; + } + + template + _CharT* + rope<_CharT, _Alloc>:: + _S_flatten(_RopeRep* __r, _CharT* __buffer) + { + if (0 == __r) + return __buffer; + switch(__r->_M_tag) + { case _Rope_constants::_S_concat: - { - _RopeConcatenation* __c = (_RopeConcatenation*)__r; - _RopeRep* __left = __c->_M_left; - _RopeRep* __right = __c->_M_right; - _CharT* __rest = _S_flatten(__left, __buffer); - return _S_flatten(__right, __rest); - } + { + _RopeConcatenation* __c = (_RopeConcatenation*)__r; + _RopeRep* __left = __c->_M_left; + _RopeRep* __right = __c->_M_right; + _CharT* __rest = _S_flatten(__left, __buffer); + return _S_flatten(__right, __rest); + } case _Rope_constants::_S_leaf: - { - _RopeLeaf* __l = (_RopeLeaf*)__r; - return copy_n(__l->_M_data, __l->_M_size, __buffer).second; - } + { + _RopeLeaf* __l = (_RopeLeaf*)__r; + return copy_n(__l->_M_data, __l->_M_size, __buffer).second; + } case _Rope_constants::_S_function: case _Rope_constants::_S_substringfn: - // We don't yet do anything with substring nodes. - // This needs to be fixed before ropefiles will work well. - { - _RopeFunction* __f = (_RopeFunction*)__r; - (*(__f->_M_fn))(0, __f->_M_size, __buffer); - return __buffer + __f->_M_size; - } + // We don't yet do anything with substring nodes. + // This needs to be fixed before ropefiles will work well. + { + _RopeFunction* __f = (_RopeFunction*)__r; + (*(__f->_M_fn))(0, __f->_M_size, __buffer); + return __buffer + __f->_M_size; + } default: - return 0; - } -} - - -// This needs work for _CharT != char -template -void -rope<_CharT,_Alloc>::_S_dump(_RopeRep* __r, int __indent) -{ - for (int __i = 0; __i < __indent; __i++) putchar(' '); - if (0 == __r) { - printf("NULL\n"); return; + return 0; + } } - if (_Rope_constants::_S_concat == __r->_M_tag) { - _RopeConcatenation* __c = (_RopeConcatenation*)__r; - _RopeRep* __left = __c->_M_left; - _RopeRep* __right = __c->_M_right; -# ifdef __GC + // This needs work for _CharT != char + template + void + rope<_CharT, _Alloc>:: + _S_dump(_RopeRep* __r, int __indent) + { + for (int __i = 0; __i < __indent; __i++) + putchar(' '); + if (0 == __r) + { + printf("NULL\n"); + return; + } + if (_Rope_constants::_S_concat == __r->_M_tag) + { + _RopeConcatenation* __c = (_RopeConcatenation*)__r; + _RopeRep* __left = __c->_M_left; + _RopeRep* __right = __c->_M_right; + +#ifdef __GC printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n", - __r, __r->_M_depth, __r->_M_size, __r->_M_is_balanced? "" : "not"); -# else + __r, __r->_M_depth, __r->_M_size, + __r->_M_is_balanced? "" : "not"); +#else printf("Concatenation %p (rc = %ld, depth = %d, " - "len = %ld, %s balanced)\n", + "len = %ld, %s balanced)\n", __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size, __r->_M_is_balanced? "" : "not"); -# endif - _S_dump(__left, __indent + 2); - _S_dump(__right, __indent + 2); - return; - } else { - char* __kind; - - switch (__r->_M_tag) { +#endif + _S_dump(__left, __indent + 2); + _S_dump(__right, __indent + 2); + return; + } + else + { + char* __kind; + + switch (__r->_M_tag) + { case _Rope_constants::_S_leaf: - __kind = "Leaf"; - break; + __kind = "Leaf"; + break; case _Rope_constants::_S_function: - __kind = "Function"; - break; + __kind = "Function"; + break; case _Rope_constants::_S_substringfn: - __kind = "Function representing substring"; - break; + __kind = "Function representing substring"; + break; default: - __kind = "(corrupted kind field!)"; - } -# ifdef __GC + __kind = "(corrupted kind field!)"; + } +#ifdef __GC printf("%s %p (depth = %d, len = %ld) ", __kind, __r, __r->_M_depth, __r->_M_size); -# else +#else printf("%s %p (rc = %ld, depth = %d, len = %ld) ", __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size); -# endif - if (_S_is_one_byte_char_type((_CharT*)0)) { - const int __max_len = 40; - _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len)); - _CharT __buffer[__max_len + 1]; - bool __too_big = __r->_M_size > __prefix->_M_size; - - _S_flatten(__prefix, __buffer); - __buffer[__prefix->_M_size] = _S_eos((_CharT*)0); - printf("%s%s\n", - (char*)__buffer, __too_big? "...\n" : "\n"); - } else { +#endif + if (_S_is_one_byte_char_type((_CharT*)0)) + { + const int __max_len = 40; + _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len)); + _CharT __buffer[__max_len + 1]; + bool __too_big = __r->_M_size > __prefix->_M_size; + + _S_flatten(__prefix, __buffer); + __buffer[__prefix->_M_size] = _S_eos((_CharT*)0); + printf("%s%s\n", (char*)__buffer, + __too_big? "...\n" : "\n"); + } + else printf("\n"); } } -} - -template -const unsigned long -rope<_CharT,_Alloc>::_S_min_len[_Rope_constants::_S_max_rope_depth + 1] = { -/* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21, -/* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377, -/* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181, -/* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368, -/* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811, -/* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309, -/* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352, -/* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155, -/* 39 */165580141, /* 40 */267914296, /* 41 */433494437, -/* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903, -/* 45 */2971215073u }; -// These are Fibonacci numbers < 2**32. - -template -typename rope<_CharT,_Alloc>::_RopeRep* -rope<_CharT,_Alloc>::_S_balance(_RopeRep* __r) -{ - _RopeRep* __forest[_Rope_constants::_S_max_rope_depth + 1]; - _RopeRep* __result = 0; - int __i; - // Invariant: - // The concatenation of forest in descending order is equal to __r. - // __forest[__i]._M_size >= _S_min_len[__i] - // __forest[__i]._M_depth = __i - // References from forest are included in refcount. - - for (__i = 0; __i <= _Rope_constants::_S_max_rope_depth; ++__i) - __forest[__i] = 0; - try { - _S_add_to_forest(__r, __forest); - for (__i = 0; __i <= _Rope_constants::_S_max_rope_depth; ++__i) - if (0 != __forest[__i]) { -# ifndef __GC - _Self_destruct_ptr __old(__result); -# endif - __result = _S_concat(__forest[__i], __result); - __forest[__i]->_M_unref_nonnil(); -# if !defined(__GC) && defined(__EXCEPTIONS) - __forest[__i] = 0; -# endif - } - } - catch(...) - { - for(__i = 0; __i <= _Rope_constants::_S_max_rope_depth; __i++) - _S_unref(__forest[__i]); - __throw_exception_again; - } - - if (__result->_M_depth > _Rope_constants::_S_max_rope_depth) - __throw_length_error(__N("rope::_S_balance")); - return(__result); -} - -template -void -rope<_CharT,_Alloc>::_S_add_to_forest(_RopeRep* __r, _RopeRep** __forest) -{ - if (__r->_M_is_balanced) { - _S_add_leaf_to_forest(__r, __forest); - return; + template + const unsigned long + rope<_CharT, _Alloc>:: + _S_min_len[_Rope_constants::_S_max_rope_depth + 1] = { + /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21, + /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377, + /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181, + /* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368, + /* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811, + /* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309, + /* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352, + /* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155, + /* 39 */165580141, /* 40 */267914296, /* 41 */433494437, + /* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903, + /* 45 */2971215073u }; + // These are Fibonacci numbers < 2**32. + + template + typename rope<_CharT, _Alloc>::_RopeRep* + rope<_CharT, _Alloc>:: + _S_balance(_RopeRep* __r) + { + _RopeRep* __forest[_Rope_constants::_S_max_rope_depth + 1]; + _RopeRep* __result = 0; + int __i; + // Invariant: + // The concatenation of forest in descending order is equal to __r. + // __forest[__i]._M_size >= _S_min_len[__i] + // __forest[__i]._M_depth = __i + // References from forest are included in refcount. + + for (__i = 0; __i <= _Rope_constants::_S_max_rope_depth; ++__i) + __forest[__i] = 0; + try + { + _S_add_to_forest(__r, __forest); + for (__i = 0; __i <= _Rope_constants::_S_max_rope_depth; ++__i) + if (0 != __forest[__i]) + { +#ifndef __GC + _Self_destruct_ptr __old(__result); +#endif + __result = _S_concat(__forest[__i], __result); + __forest[__i]->_M_unref_nonnil(); +#if !defined(__GC) && defined(__EXCEPTIONS) + __forest[__i] = 0; +#endif + } + } + catch(...) + { + for(__i = 0; __i <= _Rope_constants::_S_max_rope_depth; __i++) + _S_unref(__forest[__i]); + __throw_exception_again; + } + + if (__result->_M_depth > _Rope_constants::_S_max_rope_depth) + __throw_length_error(__N("rope::_S_balance")); + return(__result); } + template + void + rope<_CharT, _Alloc>:: + _S_add_to_forest(_RopeRep* __r, _RopeRep** __forest) { - _RopeConcatenation* __c = (_RopeConcatenation*)__r; + if (__r->_M_is_balanced) + { + _S_add_leaf_to_forest(__r, __forest); + return; + } + { + _RopeConcatenation* __c = (_RopeConcatenation*)__r; + _S_add_to_forest(__c->_M_left, __forest); _S_add_to_forest(__c->_M_right, __forest); + } } -} -template -void -rope<_CharT,_Alloc>::_S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest) -{ - _RopeRep* __insertee; // included in refcount - _RopeRep* __too_tiny = 0; // included in refcount - int __i; // forest[0..__i-1] is empty - size_t __s = __r->_M_size; - - for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i) { - if (0 != __forest[__i]) { -# ifndef __GC + template + void + rope<_CharT, _Alloc>:: + _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest) + { + _RopeRep* __insertee; // included in refcount + _RopeRep* __too_tiny = 0; // included in refcount + int __i; // forest[0..__i-1] is empty + size_t __s = __r->_M_size; + + for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i) + { + if (0 != __forest[__i]) + { +#ifndef __GC _Self_destruct_ptr __old(__too_tiny); -# endif - __too_tiny = _S_concat_and_set_balanced(__forest[__i], __too_tiny); - __forest[__i]->_M_unref_nonnil(); - __forest[__i] = 0; +#endif + __too_tiny = _S_concat_and_set_balanced(__forest[__i], + __too_tiny); + __forest[__i]->_M_unref_nonnil(); + __forest[__i] = 0; + } } - } - { -# ifndef __GC - _Self_destruct_ptr __old(__too_tiny); -# endif + { +#ifndef __GC + _Self_destruct_ptr __old(__too_tiny); +#endif __insertee = _S_concat_and_set_balanced(__too_tiny, __r); - } - // Too_tiny dead, and no longer included in refcount. - // Insertee is live and included. - for (;; ++__i) { - if (0 != __forest[__i]) { -# ifndef __GC + } + // Too_tiny dead, and no longer included in refcount. + // Insertee is live and included. + for (;; ++__i) + { + if (0 != __forest[__i]) + { +#ifndef __GC _Self_destruct_ptr __old(__insertee); -# endif - __insertee = _S_concat_and_set_balanced(__forest[__i], __insertee); - __forest[__i]->_M_unref_nonnil(); - __forest[__i] = 0; - } - if (__i == _Rope_constants::_S_max_rope_depth || - __insertee->_M_size < _S_min_len[__i+1]) { - __forest[__i] = __insertee; - // refcount is OK since __insertee is now dead. - return; +#endif + __insertee = _S_concat_and_set_balanced(__forest[__i], + __insertee); + __forest[__i]->_M_unref_nonnil(); + __forest[__i] = 0; + } + if (__i == _Rope_constants::_S_max_rope_depth + || __insertee->_M_size < _S_min_len[__i+1]) + { + __forest[__i] = __insertee; + // refcount is OK since __insertee is now dead. + return; + } } } -} - -template -_CharT -rope<_CharT,_Alloc>::_S_fetch(_RopeRep* __r, size_type __i) -{ - __GC_CONST _CharT* __cstr = __r->_M_c_string; - if (0 != __cstr) return __cstr[__i]; - for(;;) { - switch(__r->_M_tag) { - case _Rope_constants::_S_concat: + template + _CharT + rope<_CharT, _Alloc>:: + _S_fetch(_RopeRep* __r, size_type __i) + { + __GC_CONST _CharT* __cstr = __r->_M_c_string; + + if (0 != __cstr) + return __cstr[__i]; + for(;;) + { + switch(__r->_M_tag) { + case _Rope_constants::_S_concat: + { _RopeConcatenation* __c = (_RopeConcatenation*)__r; _RopeRep* __left = __c->_M_left; size_t __left_len = __left->_M_size; - - if (__i >= __left_len) { + + if (__i >= __left_len) + { __i -= __left_len; __r = __c->_M_right; - } else { - __r = __left; - } - } - break; - case _Rope_constants::_S_leaf: - { + } + else + __r = __left; + } + break; + case _Rope_constants::_S_leaf: + { _RopeLeaf* __l = (_RopeLeaf*)__r; return __l->_M_data[__i]; - } - case _Rope_constants::_S_function: - case _Rope_constants::_S_substringfn: - { + } + case _Rope_constants::_S_function: + case _Rope_constants::_S_substringfn: + { _RopeFunction* __f = (_RopeFunction*)__r; _CharT __result; - + (*(__f->_M_fn))(__i, 1, &__result); return __result; + } } - } + } } -} - -# ifndef __GC -// Return a uniquely referenced character slot for the given -// position, or 0 if that's not possible. -template -_CharT* -rope<_CharT,_Alloc>::_S_fetch_ptr(_RopeRep* __r, size_type __i) -{ - _RopeRep* __clrstack[_Rope_constants::_S_max_rope_depth]; - size_t __csptr = 0; - - for(;;) { - if (__r->_M_ref_count > 1) return 0; - switch(__r->_M_tag) { - case _Rope_constants::_S_concat: + +#ifndef __GC + // Return a uniquely referenced character slot for the given + // position, or 0 if that's not possible. + template + _CharT* + rope<_CharT, _Alloc>:: + _S_fetch_ptr(_RopeRep* __r, size_type __i) + { + _RopeRep* __clrstack[_Rope_constants::_S_max_rope_depth]; + size_t __csptr = 0; + + for(;;) + { + if (__r->_M_ref_count > 1) + return 0; + switch(__r->_M_tag) { + case _Rope_constants::_S_concat: + { _RopeConcatenation* __c = (_RopeConcatenation*)__r; _RopeRep* __left = __c->_M_left; size_t __left_len = __left->_M_size; - - if (__c->_M_c_string != 0) __clrstack[__csptr++] = __c; - if (__i >= __left_len) { + + if (__c->_M_c_string != 0) + __clrstack[__csptr++] = __c; + if (__i >= __left_len) + { __i -= __left_len; __r = __c->_M_right; - } else { - __r = __left; - } - } - break; - case _Rope_constants::_S_leaf: - { + } + else + __r = __left; + } + break; + case _Rope_constants::_S_leaf: + { _RopeLeaf* __l = (_RopeLeaf*)__r; if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0) - __clrstack[__csptr++] = __l; - while (__csptr > 0) { + __clrstack[__csptr++] = __l; + while (__csptr > 0) + { -- __csptr; _RopeRep* __d = __clrstack[__csptr]; __d->_M_free_c_string(); __d->_M_c_string = 0; - } + } return __l->_M_data + __i; + } + case _Rope_constants::_S_function: + case _Rope_constants::_S_substringfn: + return 0; } - case _Rope_constants::_S_function: - case _Rope_constants::_S_substringfn: - return 0; - } + } } -} -# endif /* __GC */ - -// The following could be implemented trivially using -// lexicographical_compare_3way. -// We do a little more work to avoid dealing with rope iterators for -// flat strings. -template -int -rope<_CharT,_Alloc>::_S_compare (const _RopeRep* __left, - const _RopeRep* __right) -{ - size_t __left_len; - size_t __right_len; - - if (0 == __right) return 0 != __left; - if (0 == __left) return -1; - __left_len = __left->_M_size; - __right_len = __right->_M_size; - if (_Rope_constants::_S_leaf == __left->_M_tag) { - _RopeLeaf* __l = (_RopeLeaf*) __left; - if (_RopeRep::_S_leaf == __right->_M_tag) { - _RopeLeaf* __r = (_RopeLeaf*) __right; - return lexicographical_compare_3way( - __l->_M_data, __l->_M_data + __left_len, - __r->_M_data, __r->_M_data + __right_len); - } else { - const_iterator __rstart(__right, 0); - const_iterator __rend(__right, __right_len); - return lexicographical_compare_3way( - __l->_M_data, __l->_M_data + __left_len, - __rstart, __rend); +#endif /* __GC */ + + // The following could be implemented trivially using + // lexicographical_compare_3way. + // We do a little more work to avoid dealing with rope iterators for + // flat strings. + template + int + rope<_CharT, _Alloc>:: + _S_compare (const _RopeRep* __left, const _RopeRep* __right) + { + size_t __left_len; + size_t __right_len; + + if (0 == __right) + return 0 != __left; + if (0 == __left) + return -1; + __left_len = __left->_M_size; + __right_len = __right->_M_size; + if (_Rope_constants::_S_leaf == __left->_M_tag) + { + _RopeLeaf* __l = (_RopeLeaf*) __left; + if (_RopeRep::_S_leaf == __right->_M_tag) + { + _RopeLeaf* __r = (_RopeLeaf*) __right; + return lexicographical_compare_3way(__l->_M_data, + __l->_M_data + __left_len, + __r->_M_data, __r->_M_data + + __right_len); + } + else + { + const_iterator __rstart(__right, 0); + const_iterator __rend(__right, __right_len); + return lexicographical_compare_3way(__l->_M_data, __l->_M_data + + __left_len, + __rstart, __rend); + } } - } else { - const_iterator __lstart(__left, 0); - const_iterator __lend(__left, __left_len); - if (_Rope_constants::_S_leaf == __right->_M_tag) { - _RopeLeaf* __r = (_RopeLeaf*) __right; - return lexicographical_compare_3way( - __lstart, __lend, - __r->_M_data, __r->_M_data + __right_len); - } else { - const_iterator __rstart(__right, 0); - const_iterator __rend(__right, __right_len); - return lexicographical_compare_3way( - __lstart, __lend, - __rstart, __rend); + else + { + const_iterator __lstart(__left, 0); + const_iterator __lend(__left, __left_len); + if (_Rope_constants::_S_leaf == __right->_M_tag) + { + _RopeLeaf* __r = (_RopeLeaf*) __right; + return lexicographical_compare_3way(__lstart, __lend, + __r->_M_data, __r->_M_data + + __right_len); + } + else + { + const_iterator __rstart(__right, 0); + const_iterator __rend(__right, __right_len); + return lexicographical_compare_3way(__lstart, __lend, + __rstart, __rend); + } } } -} - -// Assignment to reference proxies. -template -_Rope_char_ref_proxy<_CharT, _Alloc>& -_Rope_char_ref_proxy<_CharT, _Alloc>::operator= (_CharT __c) { - _RopeRep* __old = _M_root->_M_tree_ptr; -# ifndef __GC - // First check for the case in which everything is uniquely - // referenced. In that case we can do this destructively. - _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos); - if (0 != __ptr) { - *__ptr = __c; - return *this; + + // Assignment to reference proxies. + template + _Rope_char_ref_proxy<_CharT, _Alloc>& + _Rope_char_ref_proxy<_CharT, _Alloc>:: + operator=(_CharT __c) + { + _RopeRep* __old = _M_root->_M_tree_ptr; +#ifndef __GC + // First check for the case in which everything is uniquely + // referenced. In that case we can do this destructively. + _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos); + if (0 != __ptr) + { + *__ptr = __c; + return *this; } -# endif - _Self_destruct_ptr __left( - _My_rope::_S_substring(__old, 0, _M_pos)); - _Self_destruct_ptr __right( - _My_rope::_S_substring(__old, _M_pos+1, __old->_M_size)); - _Self_destruct_ptr __result_left( - _My_rope::_S_destr_concat_char_iter(__left, &__c, 1)); - - _RopeRep* __result = - _My_rope::_S_concat(__result_left, __right); -# ifndef __GC +#endif + _Self_destruct_ptr __left(_My_rope::_S_substring(__old, 0, _M_pos)); + _Self_destruct_ptr __right(_My_rope::_S_substring(__old, _M_pos + 1, + __old->_M_size)); + _Self_destruct_ptr __result_left(_My_rope:: + _S_destr_concat_char_iter(__left, + &__c, 1)); + + _RopeRep* __result = _My_rope::_S_concat(__result_left, __right); +#ifndef __GC _RopeRep::_S_unref(__old); -# endif - _M_root->_M_tree_ptr = __result; - return *this; -} +#endif + _M_root->_M_tree_ptr = __result; + return *this; + } -template -inline _Rope_char_ref_proxy<_CharT, _Alloc>::operator _CharT () const -{ - if (_M_current_valid) { + template + inline _Rope_char_ref_proxy<_CharT, _Alloc>:: + operator _CharT() const + { + if (_M_current_valid) return _M_current; - } else { - return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos); + else + return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos); } -} -template -_Rope_char_ptr_proxy<_CharT, _Alloc> -_Rope_char_ref_proxy<_CharT, _Alloc>::operator& () const { - return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this); -} - -template -rope<_CharT, _Alloc>::rope(size_t __n, _CharT __c, - const allocator_type& __a) -: _Base(__a) -{ - rope<_CharT,_Alloc> __result; - const size_t __exponentiate_threshold = 32; - size_t __exponent; - size_t __rest; - _CharT* __rest_buffer; - _RopeRep* __remainder; - rope<_CharT,_Alloc> __remainder_rope; - - if (0 == __n) - return; - - __exponent = __n / __exponentiate_threshold; - __rest = __n % __exponentiate_threshold; - if (0 == __rest) { + + template + _Rope_char_ptr_proxy<_CharT, _Alloc> + _Rope_char_ref_proxy<_CharT, _Alloc>:: + operator&() const + { return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this); } + + template + rope<_CharT, _Alloc>:: + rope(size_t __n, _CharT __c, const allocator_type& __a) + : _Base(__a) + { + rope<_CharT,_Alloc> __result; + const size_t __exponentiate_threshold = 32; + size_t __exponent; + size_t __rest; + _CharT* __rest_buffer; + _RopeRep* __remainder; + rope<_CharT, _Alloc> __remainder_rope; + + if (0 == __n) + return; + + __exponent = __n / __exponentiate_threshold; + __rest = __n % __exponentiate_threshold; + if (0 == __rest) __remainder = 0; - } else { - __rest_buffer = this->_Data_allocate(_S_rounded_up_size(__rest)); - uninitialized_fill_n(__rest_buffer, __rest, __c); - _S_cond_store_eos(__rest_buffer[__rest]); - try { - __remainder = _S_new_RopeLeaf(__rest_buffer, __rest, __a); - } - catch(...) - { - _RopeRep::__STL_FREE_STRING(__rest_buffer, __rest, __a); - __throw_exception_again; - } - } - __remainder_rope._M_tree_ptr = __remainder; - if (__exponent != 0) { - _CharT* __base_buffer = - this->_Data_allocate(_S_rounded_up_size(__exponentiate_threshold)); - _RopeLeaf* __base_leaf; - rope __base_rope; - uninitialized_fill_n(__base_buffer, __exponentiate_threshold, __c); - _S_cond_store_eos(__base_buffer[__exponentiate_threshold]); - try { - __base_leaf = _S_new_RopeLeaf(__base_buffer, - __exponentiate_threshold, __a); - } - catch(...) - { - _RopeRep::__STL_FREE_STRING(__base_buffer, - __exponentiate_threshold, __a); - __throw_exception_again; - } - __base_rope._M_tree_ptr = __base_leaf; - if (1 == __exponent) { - __result = __base_rope; - } else { - __result = power(__base_rope, __exponent, - _Rope_Concat_fn<_CharT,_Alloc>()); + else + { + __rest_buffer = this->_Data_allocate(_S_rounded_up_size(__rest)); + uninitialized_fill_n(__rest_buffer, __rest, __c); + _S_cond_store_eos(__rest_buffer[__rest]); + try + { __remainder = _S_new_RopeLeaf(__rest_buffer, __rest, __a); } + catch(...) + { + _RopeRep::__STL_FREE_STRING(__rest_buffer, __rest, __a); + __throw_exception_again; + } } - if (0 != __remainder) { - __result += __remainder_rope; + __remainder_rope._M_tree_ptr = __remainder; + if (__exponent != 0) + { + _CharT* __base_buffer = + this->_Data_allocate(_S_rounded_up_size(__exponentiate_threshold)); + _RopeLeaf* __base_leaf; + rope __base_rope; + uninitialized_fill_n(__base_buffer, __exponentiate_threshold, __c); + _S_cond_store_eos(__base_buffer[__exponentiate_threshold]); + try + { + __base_leaf = _S_new_RopeLeaf(__base_buffer, + __exponentiate_threshold, __a); + } + catch(...) + { + _RopeRep::__STL_FREE_STRING(__base_buffer, + __exponentiate_threshold, __a); + __throw_exception_again; + } + __base_rope._M_tree_ptr = __base_leaf; + if (1 == __exponent) + __result = __base_rope; + else + __result = power(__base_rope, __exponent, + _Rope_Concat_fn<_CharT, _Alloc>()); + + if (0 != __remainder) + __result += __remainder_rope; } - } else { + else __result = __remainder_rope; + + this->_M_tree_ptr = __result._M_tree_ptr; + this->_M_tree_ptr->_M_ref_nonnil(); } - this->_M_tree_ptr = __result._M_tree_ptr; - this->_M_tree_ptr->_M_ref_nonnil(); -} - -template - _CharT rope<_CharT,_Alloc>::_S_empty_c_str[1]; - -template -const _CharT* rope<_CharT,_Alloc>::c_str() const { - if (0 == this->_M_tree_ptr) { - _S_empty_c_str[0] = _S_eos((_CharT*)0); // Possibly redundant, - // but probably fast. - return _S_empty_c_str; - } - __gthread_mutex_lock (&this->_M_tree_ptr->_M_c_string_lock); - __GC_CONST _CharT* __result = this->_M_tree_ptr->_M_c_string; - if (0 == __result) - { - size_t __s = size(); - __result = this->_Data_allocate(__s + 1); - _S_flatten(this->_M_tree_ptr, __result); - __result[__s] = _S_eos((_CharT*)0); - this->_M_tree_ptr->_M_c_string = __result; - } - __gthread_mutex_unlock (&this->_M_tree_ptr->_M_c_string_lock); - return(__result); -} - -template -const _CharT* rope<_CharT,_Alloc>::replace_with_c_str() { - if (0 == this->_M_tree_ptr) { - _S_empty_c_str[0] = _S_eos((_CharT*)0); - return _S_empty_c_str; + + template + _CharT + rope<_CharT, _Alloc>::_S_empty_c_str[1]; + + template + const _CharT* + rope<_CharT, _Alloc>:: + c_str() const + { + if (0 == this->_M_tree_ptr) + { + _S_empty_c_str[0] = _S_eos((_CharT*)0); // Possibly redundant, + // but probably fast. + return _S_empty_c_str; + } + __gthread_mutex_lock (&this->_M_tree_ptr->_M_c_string_lock); + __GC_CONST _CharT* __result = this->_M_tree_ptr->_M_c_string; + if (0 == __result) + { + size_t __s = size(); + __result = this->_Data_allocate(__s + 1); + _S_flatten(this->_M_tree_ptr, __result); + __result[__s] = _S_eos((_CharT*)0); + this->_M_tree_ptr->_M_c_string = __result; + } + __gthread_mutex_unlock (&this->_M_tree_ptr->_M_c_string_lock); + return(__result); } - __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string; - if (_Rope_constants::_S_leaf == this->_M_tree_ptr->_M_tag - && 0 != __old_c_string) { + + template + const _CharT* rope<_CharT, _Alloc>:: + replace_with_c_str() + { + if (0 == this->_M_tree_ptr) + { + _S_empty_c_str[0] = _S_eos((_CharT*)0); + return _S_empty_c_str; + } + __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string; + if (_Rope_constants::_S_leaf == this->_M_tree_ptr->_M_tag + && 0 != __old_c_string) return(__old_c_string); + size_t __s = size(); + _CharT* __result = this->_Data_allocate(_S_rounded_up_size(__s)); + _S_flatten(this->_M_tree_ptr, __result); + __result[__s] = _S_eos((_CharT*)0); + this->_M_tree_ptr->_M_unref_nonnil(); + this->_M_tree_ptr = _S_new_RopeLeaf(__result, __s, + this->get_allocator()); + return(__result); + } + + // Algorithm specializations. More should be added. + + template // was templated on CharT and Alloc + void // VC++ workaround + _Rope_rotate(_Rope_iterator __first, + _Rope_iterator __middle, + _Rope_iterator __last) + { + typedef typename _Rope_iterator::value_type _CharT; + typedef typename _Rope_iterator::_allocator_type _Alloc; + + 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; } - size_t __s = size(); - _CharT* __result = this->_Data_allocate(_S_rounded_up_size(__s)); - _S_flatten(this->_M_tree_ptr, __result); - __result[__s] = _S_eos((_CharT*)0); - this->_M_tree_ptr->_M_unref_nonnil(); - this->_M_tree_ptr = _S_new_RopeLeaf(__result, __s, this->get_allocator()); - return(__result); -} - -// Algorithm specializations. More should be added. - -template // was templated on CharT and Alloc -void // VC++ workaround -_Rope_rotate(_Rope_iterator __first, - _Rope_iterator __middle, - _Rope_iterator __last) -{ - typedef typename _Rope_iterator::value_type _CharT; - typedef typename _Rope_iterator::_allocator_type _Alloc; - - 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; -} #if !defined(__GNUC__) -// Appears to confuse g++ -inline void rotate(_Rope_iterator __first, - _Rope_iterator __middle, - _Rope_iterator __last) { - _Rope_rotate(__first, __middle, __last); -} + // Appears to confuse g++ + inline void + rotate(_Rope_iterator __first, + _Rope_iterator __middle, + _Rope_iterator __last) + { _Rope_rotate(__first, __middle, __last); } #endif # if 0 -// Probably not useful for several reasons: -// - for SGIs 7.1 compiler and probably some others, -// this forces lots of rope instantiations, creating a -// code bloat and compile time problem. (Fixed in 7.2.) -// - wchar_t is 4 bytes wide on most UNIX platforms, making it unattractive -// for unicode strings. Unsigned short may be a better character -// type. -inline void rotate( - _Rope_iterator __first, - _Rope_iterator __middle, - _Rope_iterator __last) { - _Rope_rotate(__first, __middle, __last); -} + // Probably not useful for several reasons: + // - for SGIs 7.1 compiler and probably some others, + // this forces lots of rope instantiations, creating a + // code bloat and compile time problem. (Fixed in 7.2.) + // - wchar_t is 4 bytes wide on most UNIX platforms, making it + // unattractive for unicode strings. Unsigned short may be a better + // character type. + inline void + rotate(_Rope_iterator __first, + _Rope_iterator __middle, + _Rope_iterator __last) + { _Rope_rotate(__first, __middle, __last); } # endif } // namespace __gnu_cxx -- 2.7.4