54 #include <bits/gthr.h>
58 # define __GC_CONST const
60 # define __GC_CONST // constant except for deallocation
65 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
69 enum { _S_max_rope_depth = 45 };
70 enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function};
79 template<
typename _ForwardIterator,
typename _Allocator>
81 _Destroy_const(_ForwardIterator __first,
82 _ForwardIterator __last, _Allocator __alloc)
84 for (; __first != __last; ++__first)
85 __alloc.destroy(&*__first);
88 template<
typename _ForwardIterator,
typename _Tp>
90 _Destroy_const(_ForwardIterator __first,
91 _ForwardIterator __last, allocator<_Tp>)
99 template <
class _CharT>
106 template <
class _CharT>
108 _S_is_basic_char_type(_CharT*)
111 template <
class _CharT>
113 _S_is_one_byte_char_type(_CharT*)
117 _S_is_basic_char_type(
char*)
121 _S_is_one_byte_char_type(
char*)
125 _S_is_basic_char_type(
wchar_t*)
130 template <
class _CharT>
132 _S_cond_store_eos(_CharT&) { }
135 _S_cond_store_eos(
char& __c)
139 _S_cond_store_eos(
wchar_t& __c)
146 template <
class _CharT>
150 virtual ~char_producer() { };
153 operator()(
size_t __start_pos,
size_t __len,
154 _CharT* __buffer) = 0;
175 template<
class _Sequence,
size_t _Buf_sz = 100>
176 class sequence_buffer
177 :
public std::iterator<std::output_iterator_tag, void, void, void, void>
180 typedef typename _Sequence::value_type
value_type;
182 _Sequence* _M_prefix;
183 value_type _M_buffer[_Buf_sz];
190 _M_prefix->append(_M_buffer, _M_buffer + _M_buf_count);
198 : _M_prefix(0), _M_buf_count(0) { }
200 sequence_buffer(
const sequence_buffer& __x)
202 _M_prefix = __x._M_prefix;
203 _M_buf_count = __x._M_buf_count;
204 std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
207 sequence_buffer(sequence_buffer& __x)
210 _M_prefix = __x._M_prefix;
214 sequence_buffer(_Sequence& __s)
215 : _M_prefix(&__s), _M_buf_count(0) { }
218 operator=(sequence_buffer& __x)
221 _M_prefix = __x._M_prefix;
227 operator=(
const sequence_buffer& __x)
229 _M_prefix = __x._M_prefix;
230 _M_buf_count = __x._M_buf_count;
231 std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
236 push_back(value_type __x)
238 if (_M_buf_count < _Buf_sz)
240 _M_buffer[_M_buf_count] = __x;
252 append(value_type* __s,
size_t __len)
254 if (__len + _M_buf_count <= _Buf_sz)
256 size_t __i = _M_buf_count;
257 for (
size_t __j = 0; __j < __len; __i++, __j++)
258 _M_buffer[__i] = __s[__j];
259 _M_buf_count += __len;
261 else if (0 == _M_buf_count)
262 _M_prefix->append(__s, __s + __len);
271 write(value_type* __s,
size_t __len)
285 operator=(
const value_type& __rhs)
305 template<
class _CharT>
306 class _Rope_char_consumer
314 virtual ~_Rope_char_consumer() { };
317 operator()(
const _CharT* __buffer,
size_t __len) = 0;
323 template<
class _CharT,
class _Alloc = allocator<_CharT> >
326 template<
class _CharT,
class _Alloc>
327 struct _Rope_RopeConcatenation;
329 template<
class _CharT,
class _Alloc>
330 struct _Rope_RopeLeaf;
332 template<
class _CharT,
class _Alloc>
333 struct _Rope_RopeFunction;
335 template<
class _CharT,
class _Alloc>
336 struct _Rope_RopeSubstring;
338 template<
class _CharT,
class _Alloc>
339 class _Rope_iterator;
341 template<
class _CharT,
class _Alloc>
342 class _Rope_const_iterator;
344 template<
class _CharT,
class _Alloc>
345 class _Rope_char_ref_proxy;
347 template<
class _CharT,
class _Alloc>
348 class _Rope_char_ptr_proxy;
350 template<
class _CharT,
class _Alloc>
352 operator==(
const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
353 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y);
355 template<
class _CharT,
class _Alloc>
356 _Rope_const_iterator<_CharT, _Alloc>
357 operator-(
const _Rope_const_iterator<_CharT, _Alloc>& __x,
360 template<
class _CharT,
class _Alloc>
361 _Rope_const_iterator<_CharT, _Alloc>
362 operator+(
const _Rope_const_iterator<_CharT, _Alloc>& __x,
365 template<
class _CharT,
class _Alloc>
366 _Rope_const_iterator<_CharT, _Alloc>
367 operator+(ptrdiff_t __n,
368 const _Rope_const_iterator<_CharT, _Alloc>& __x);
370 template<
class _CharT,
class _Alloc>
372 operator==(
const _Rope_const_iterator<_CharT, _Alloc>& __x,
373 const _Rope_const_iterator<_CharT, _Alloc>& __y);
375 template<
class _CharT,
class _Alloc>
377 operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,
378 const _Rope_const_iterator<_CharT, _Alloc>& __y);
380 template<
class _CharT,
class _Alloc>
382 operator-(
const _Rope_const_iterator<_CharT, _Alloc>& __x,
383 const _Rope_const_iterator<_CharT, _Alloc>& __y);
385 template<
class _CharT,
class _Alloc>
386 _Rope_iterator<_CharT, _Alloc>
387 operator-(
const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);
389 template<
class _CharT,
class _Alloc>
390 _Rope_iterator<_CharT, _Alloc>
391 operator+(
const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);
393 template<
class _CharT,
class _Alloc>
394 _Rope_iterator<_CharT, _Alloc>
395 operator+(ptrdiff_t __n,
const _Rope_iterator<_CharT, _Alloc>& __x);
397 template<
class _CharT,
class _Alloc>
399 operator==(
const _Rope_iterator<_CharT, _Alloc>& __x,
400 const _Rope_iterator<_CharT, _Alloc>& __y);
402 template<
class _CharT,
class _Alloc>
404 operator<(const _Rope_iterator<_CharT, _Alloc>& __x,
405 const _Rope_iterator<_CharT, _Alloc>& __y);
407 template<
class _CharT,
class _Alloc>
409 operator-(
const _Rope_iterator<_CharT, _Alloc>& __x,
410 const _Rope_iterator<_CharT, _Alloc>& __y);
412 template<
class _CharT,
class _Alloc>
414 operator+(
const rope<_CharT, _Alloc>& __left,
415 const rope<_CharT, _Alloc>& __right);
417 template<
class _CharT,
class _Alloc>
419 operator+(
const rope<_CharT, _Alloc>& __left,
const _CharT* __right);
421 template<
class _CharT,
class _Alloc>
423 operator+(
const rope<_CharT, _Alloc>& __left, _CharT __right);
430 template<
class _CharT,
class _Alloc>
431 struct _Rope_Concat_fn
433 rope<_CharT, _Alloc> >
436 operator()(
const rope<_CharT, _Alloc>& __x,
437 const rope<_CharT, _Alloc>& __y)
438 {
return __x + __y; }
441 template <
class _CharT,
class _Alloc>
442 inline rope<_CharT, _Alloc>
443 identity_element(_Rope_Concat_fn<_CharT, _Alloc>)
444 {
return rope<_CharT, _Alloc>(); }
450 struct _Refcount_Base
453 typedef size_t _RC_t;
456 volatile _RC_t _M_ref_count;
459 __gthread_mutex_t _M_ref_count_lock;
461 _Refcount_Base(_RC_t __n) : _M_ref_count(__n), _M_ref_count_lock()
463 #ifdef __GTHREAD_MUTEX_INIT
464 __gthread_mutex_t __tmp = __GTHREAD_MUTEX_INIT;
465 _M_ref_count_lock = __tmp;
466 #elif defined(__GTHREAD_MUTEX_INIT_FUNCTION)
467 __GTHREAD_MUTEX_INIT_FUNCTION (&_M_ref_count_lock);
469 #error __GTHREAD_MUTEX_INIT or __GTHREAD_MUTEX_INIT_FUNCTION should be defined by gthr.h abstraction layer, report problem to libstdc++@gcc.gnu.org.
476 __gthread_mutex_lock(&_M_ref_count_lock);
478 __gthread_mutex_unlock(&_M_ref_count_lock);
484 __gthread_mutex_lock(&_M_ref_count_lock);
485 volatile _RC_t __tmp = --_M_ref_count;
486 __gthread_mutex_unlock(&_M_ref_count_lock);
516 #define __ROPE_DEFINE_ALLOCS(__a) \
517 __ROPE_DEFINE_ALLOC(_CharT,_Data) \
518 typedef _Rope_RopeConcatenation<_CharT,__a> __C; \
519 __ROPE_DEFINE_ALLOC(__C,_C) \
520 typedef _Rope_RopeLeaf<_CharT,__a> __L; \
521 __ROPE_DEFINE_ALLOC(__L,_L) \
522 typedef _Rope_RopeFunction<_CharT,__a> __F; \
523 __ROPE_DEFINE_ALLOC(__F,_F) \
524 typedef _Rope_RopeSubstring<_CharT,__a> __S; \
525 __ROPE_DEFINE_ALLOC(__S,_S)
534 #define __STATIC_IF_SGI_ALLOC
536 template <
class _CharT,
class _Alloc>
537 struct _Rope_rep_base
540 typedef _Alloc allocator_type;
543 get_allocator()
const
544 {
return *
static_cast<const _Alloc*
>(
this); }
548 {
return *
static_cast<_Alloc*
>(
this); }
550 const allocator_type&
551 _M_get_allocator()
const
552 {
return *
static_cast<const _Alloc*
>(
this); }
554 _Rope_rep_base(
size_t __size,
const allocator_type&)
555 : _M_size(__size) { }
559 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
561 _Alloc::template rebind<_Tp>::other __name##Alloc; \
562 static _Tp* __name##_allocate(size_t __n) \
563 { return __name##Alloc().allocate(__n); } \
564 static void __name##_deallocate(_Tp *__p, size_t __n) \
565 { __name##Alloc().deallocate(__p, __n); }
566 __ROPE_DEFINE_ALLOCS(_Alloc)
567 # undef __ROPE_DEFINE_ALLOC
570 template<
class _CharT,
class _Alloc>
572 :
public _Rope_rep_base<_CharT, _Alloc>
578 __detail::_Tag _M_tag:8;
579 bool _M_is_balanced:8;
580 unsigned char _M_depth;
581 __GC_CONST _CharT* _M_c_string;
582 __gthread_mutex_t _M_c_string_lock;
589 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
592 using _Rope_rep_base<_CharT, _Alloc>::get_allocator;
593 using _Rope_rep_base<_CharT, _Alloc>::_M_get_allocator;
595 _Rope_RopeRep(__detail::_Tag __t,
int __d,
bool __b,
size_t __size,
596 const allocator_type& __a)
597 : _Rope_rep_base<_CharT, _Alloc>(__size, __a),
601 _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0)
602 #ifdef __GTHREAD_MUTEX_INIT
605 __gthread_mutex_t __tmp = __GTHREAD_MUTEX_INIT;
606 _M_c_string_lock = __tmp;
609 { __GTHREAD_MUTEX_INIT_FUNCTION (&_M_c_string_lock); }
616 _S_free_string(__GC_CONST _CharT*,
size_t __len,
617 allocator_type& __a);
618 #define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a);
626 void _M_free_c_string();
641 _S_unref(_Rope_RopeRep* __t)
644 __t->_M_unref_nonnil();
648 _S_ref(_Rope_RopeRep* __t)
655 _S_free_if_unref(_Rope_RopeRep* __t)
657 if (0 != __t && 0 == __t->_M_ref_count)
661 void _M_unref_nonnil() { }
662 void _M_ref_nonnil() { }
663 static void _S_unref(_Rope_RopeRep*) { }
664 static void _S_ref(_Rope_RopeRep*) { }
665 static void _S_free_if_unref(_Rope_RopeRep*) { }
669 operator=(
const _Rope_RopeRep&);
671 _Rope_RopeRep(
const _Rope_RopeRep&);
674 template<
class _CharT,
class _Alloc>
675 struct _Rope_RopeLeaf
676 :
public _Rope_RopeRep<_CharT, _Alloc>
683 enum { _S_alloc_granularity = 8 };
686 _S_rounded_up_size(
size_t __n)
688 size_t __size_with_eos;
690 if (_S_is_basic_char_type((_CharT*)0))
691 __size_with_eos = __n + 1;
693 __size_with_eos = __n;
695 return __size_with_eos;
698 return ((__size_with_eos +
size_t(_S_alloc_granularity) - 1)
699 &~ (
size_t(_S_alloc_granularity) - 1));
702 __GC_CONST _CharT* _M_data;
707 typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type
710 _Rope_RopeLeaf(__GC_CONST _CharT* __d,
size_t __size,
711 const allocator_type& __a)
712 : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_leaf, 0, true,
713 __size, __a), _M_data(__d)
715 if (_S_is_basic_char_type((_CharT *)0))
718 this->_M_c_string = __d;
725 ~_Rope_RopeLeaf() throw()
727 if (_M_data != this->_M_c_string)
728 this->_M_free_c_string();
730 __STL_FREE_STRING(_M_data, this->_M_size, this->_M_get_allocator());
735 operator=(
const _Rope_RopeLeaf&);
737 _Rope_RopeLeaf(
const _Rope_RopeLeaf&);
740 template<
class _CharT,
class _Alloc>
741 struct _Rope_RopeConcatenation
742 :
public _Rope_RopeRep<_CharT, _Alloc>
745 _Rope_RopeRep<_CharT, _Alloc>* _M_left;
746 _Rope_RopeRep<_CharT, _Alloc>* _M_right;
748 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
751 _Rope_RopeConcatenation(_Rope_RopeRep<_CharT, _Alloc>* __l,
752 _Rope_RopeRep<_CharT, _Alloc>* __r,
753 const allocator_type& __a)
754 : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_concat,
755 std::
max(__l->_M_depth,
758 __l->_M_size + __r->_M_size, __a),
759 _M_left(__l), _M_right(__r)
762 ~_Rope_RopeConcatenation() throw()
764 this->_M_free_c_string();
765 _M_left->_M_unref_nonnil();
766 _M_right->_M_unref_nonnil();
770 _Rope_RopeConcatenation&
771 operator=(
const _Rope_RopeConcatenation&);
773 _Rope_RopeConcatenation(
const _Rope_RopeConcatenation&);
776 template<
class _CharT,
class _Alloc>
777 struct _Rope_RopeFunction
778 :
public _Rope_RopeRep<_CharT, _Alloc>
781 char_producer<_CharT>* _M_fn;
783 bool _M_delete_when_done;
794 _S_fn_finalization_proc(
void * __tree,
void *)
795 {
delete ((_Rope_RopeFunction *)__tree) -> _M_fn; }
797 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
800 _Rope_RopeFunction(char_producer<_CharT>* __f,
size_t __size,
801 bool __d,
const allocator_type& __a)
802 : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_function, 0, true, __size, __a)
805 , _M_delete_when_done(__d)
811 GC_REGISTER_FINALIZER(
this, _Rope_RopeFunction::
812 _S_fn_finalization_proc, 0, 0, 0);
817 ~_Rope_RopeFunction() throw()
819 this->_M_free_c_string();
820 if (_M_delete_when_done)
826 operator=(
const _Rope_RopeFunction&);
828 _Rope_RopeFunction(
const _Rope_RopeFunction&);
837 template<
class _CharT,
class _Alloc>
838 struct _Rope_RopeSubstring
839 :
public _Rope_RopeFunction<_CharT, _Alloc>,
840 public char_producer<_CharT>
844 _Rope_RopeRep<_CharT,_Alloc>* _M_base;
848 operator()(
size_t __start_pos,
size_t __req_len,
851 switch(_M_base->_M_tag)
853 case __detail::_S_function:
854 case __detail::_S_substringfn:
856 char_producer<_CharT>* __fn =
857 ((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn;
858 (*__fn)(__start_pos + _M_start, __req_len, __buffer);
861 case __detail::_S_leaf:
863 __GC_CONST _CharT* __s =
864 ((_Rope_RopeLeaf<_CharT,_Alloc>*)_M_base)->_M_data;
874 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
877 _Rope_RopeSubstring(_Rope_RopeRep<_CharT, _Alloc>* __b,
size_t __s,
878 size_t __l,
const allocator_type& __a)
879 : _Rope_RopeFunction<_CharT, _Alloc>(this, __l, false, __a),
880 char_producer<_CharT>(), _M_base(__b), _M_start(__s)
883 _M_base->_M_ref_nonnil();
885 this->_M_tag = __detail::_S_substringfn;
887 virtual ~_Rope_RopeSubstring() throw()
890 _M_base->_M_unref_nonnil();
906 template<
class _CharT,
class _Alloc>
907 struct _Rope_self_destruct_ptr
909 _Rope_RopeRep<_CharT, _Alloc>* _M_ptr;
911 ~_Rope_self_destruct_ptr()
912 { _Rope_RopeRep<_CharT, _Alloc>::_S_unref(_M_ptr); }
914 _Rope_self_destruct_ptr() : _M_ptr(0) { };
916 _Rope_self_destruct_ptr() { };
918 _Rope_self_destruct_ptr(_Rope_RopeRep<_CharT, _Alloc>* __p)
921 _Rope_RopeRep<_CharT, _Alloc>&
925 _Rope_RopeRep<_CharT, _Alloc>*
929 operator _Rope_RopeRep<_CharT, _Alloc>*()
932 _Rope_self_destruct_ptr&
933 operator=(_Rope_RopeRep<_CharT, _Alloc>* __x)
934 { _M_ptr = __x;
return *
this; }
943 template<
class _CharT,
class _Alloc>
944 class _Rope_char_ref_proxy
946 friend class rope<_CharT, _Alloc>;
947 friend class _Rope_iterator<_CharT, _Alloc>;
948 friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;
950 typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
952 typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
954 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
955 typedef rope<_CharT, _Alloc> _My_rope;
958 bool _M_current_valid;
961 _Rope_char_ref_proxy(_My_rope* __r,
size_t __p)
962 : _M_pos(__p), _M_current(), _M_current_valid(false), _M_root(__r) { }
964 _Rope_char_ref_proxy(
const _Rope_char_ref_proxy& __x)
965 : _M_pos(__x._M_pos), _M_current(__x._M_current),
966 _M_current_valid(false), _M_root(__x._M_root) { }
972 _Rope_char_ref_proxy(_My_rope* __r,
size_t __p, _CharT __c)
973 : _M_pos(__p), _M_current(__c), _M_current_valid(true), _M_root(__r) { }
975 inline operator _CharT ()
const;
977 _Rope_char_ref_proxy&
978 operator=(_CharT __c);
980 _Rope_char_ptr_proxy<_CharT, _Alloc>
operator&()
const;
982 _Rope_char_ref_proxy&
983 operator=(
const _Rope_char_ref_proxy& __c)
984 {
return operator=((_CharT)__c); }
987 template<
class _CharT,
class __Alloc>
989 swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a,
990 _Rope_char_ref_proxy <_CharT, __Alloc > __b)
997 template<
class _CharT,
class _Alloc>
998 class _Rope_char_ptr_proxy
1001 friend class _Rope_char_ref_proxy<_CharT, _Alloc>;
1003 rope<_CharT,_Alloc>* _M_root;
1005 _Rope_char_ptr_proxy(
const _Rope_char_ref_proxy<_CharT,_Alloc>& __x)
1006 : _M_pos(__x._M_pos), _M_root(__x._M_root) { }
1008 _Rope_char_ptr_proxy(
const _Rope_char_ptr_proxy& __x)
1009 : _M_pos(__x._M_pos), _M_root(__x._M_root) { }
1011 _Rope_char_ptr_proxy() { }
1013 _Rope_char_ptr_proxy(_CharT* __x)
1014 : _M_root(0), _M_pos(0) { }
1016 _Rope_char_ptr_proxy&
1017 operator=(
const _Rope_char_ptr_proxy& __x)
1019 _M_pos = __x._M_pos;
1020 _M_root = __x._M_root;
1024 template<
class _CharT2,
class _Alloc2>
1026 operator==(
const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __x,
1027 const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __y);
1029 _Rope_char_ref_proxy<_CharT, _Alloc> operator*()
const
1030 {
return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root, _M_pos); }
1042 template<
class _CharT,
class _Alloc>
1043 class _Rope_iterator_base
1044 :
public std::iterator<std::random_access_iterator_tag, _CharT>
1046 friend class rope<_CharT, _Alloc>;
1048 typedef _Alloc _allocator_type;
1049 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
1052 enum { _S_path_cache_len = 4 };
1053 enum { _S_iterator_buf_len = 15 };
1054 size_t _M_current_pos;
1057 __GC_CONST _CharT* _M_buf_start;
1060 __GC_CONST _CharT* _M_buf_ptr;
1063 __GC_CONST _CharT* _M_buf_end;
1069 const _RopeRep* _M_path_end[_S_path_cache_len];
1073 unsigned char _M_path_directions;
1078 _CharT _M_tmp_buf[_S_iterator_buf_len];
1086 static void _S_setbuf(_Rope_iterator_base& __x);
1089 static void _S_setcache(_Rope_iterator_base& __x);
1092 static void _S_setcache_for_incr(_Rope_iterator_base& __x);
1095 _Rope_iterator_base() { }
1097 _Rope_iterator_base(_RopeRep* __root,
size_t __pos)
1098 : _M_current_pos(__pos), _M_root(__root), _M_buf_ptr(0) { }
1100 void _M_incr(
size_t __n);
1101 void _M_decr(
size_t __n);
1105 {
return _M_current_pos; }
1107 _Rope_iterator_base(
const _Rope_iterator_base& __x)
1109 if (0 != __x._M_buf_ptr)
1113 _M_current_pos = __x._M_current_pos;
1114 _M_root = __x._M_root;
1120 template<
class _CharT,
class _Alloc>
1121 class _Rope_iterator;
1123 template<
class _CharT,
class _Alloc>
1124 class _Rope_const_iterator
1125 :
public _Rope_iterator_base<_CharT, _Alloc>
1127 friend class rope<_CharT, _Alloc>;
1129 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
1131 _Rope_const_iterator(
const _RopeRep* __root,
size_t __pos)
1132 : _Rope_iterator_base<_CharT, _Alloc>(const_cast<_RopeRep*>(__root),
1137 typedef _CharT reference;
1140 typedef const _CharT* pointer;
1143 _Rope_const_iterator() { };
1145 _Rope_const_iterator(
const _Rope_const_iterator& __x)
1146 : _Rope_iterator_base<_CharT,_Alloc>(__x) { }
1148 _Rope_const_iterator(
const _Rope_iterator<_CharT,_Alloc>& __x);
1150 _Rope_const_iterator(
const rope<_CharT, _Alloc>& __r,
size_t __pos)
1151 : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos) { }
1153 _Rope_const_iterator&
1154 operator=(
const _Rope_const_iterator& __x)
1156 if (0 != __x._M_buf_ptr)
1157 *(
static_cast<_Rope_iterator_base<_CharT, _Alloc>*
>(
this)) = __x;
1160 this->_M_current_pos = __x._M_current_pos;
1161 this->_M_root = __x._M_root;
1162 this->_M_buf_ptr = 0;
1170 if (0 == this->_M_buf_ptr)
1172 return *this->_M_buf_ptr;
1180 return *
const_cast<_Rope_const_iterator&
>(*this);
1183 _Rope_const_iterator&
1186 __GC_CONST _CharT* __next;
1187 if (0 != this->_M_buf_ptr
1188 && (__next = this->_M_buf_ptr + 1) < this->_M_buf_end)
1190 this->_M_buf_ptr = __next;
1191 ++this->_M_current_pos;
1198 _Rope_const_iterator&
1199 operator+=(ptrdiff_t __n)
1204 this->_M_decr(-__n);
1208 _Rope_const_iterator&
1215 _Rope_const_iterator&
1216 operator-=(ptrdiff_t __n)
1221 this->_M_incr(-__n);
1225 _Rope_const_iterator
1228 size_t __old_pos = this->_M_current_pos;
1230 return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
1236 _Rope_const_iterator
1239 size_t __old_pos = this->_M_current_pos;
1241 return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
1244 template<
class _CharT2,
class _Alloc2>
1245 friend _Rope_const_iterator<_CharT2, _Alloc2>
1246 operator-(
const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1249 template<
class _CharT2,
class _Alloc2>
1250 friend _Rope_const_iterator<_CharT2, _Alloc2>
1251 operator+(
const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1254 template<
class _CharT2,
class _Alloc2>
1255 friend _Rope_const_iterator<_CharT2, _Alloc2>
1256 operator+(ptrdiff_t __n,
1257 const _Rope_const_iterator<_CharT2, _Alloc2>& __x);
1260 operator[](
size_t __n)
1261 {
return rope<_CharT, _Alloc>::_S_fetch(this->_M_root,
1262 this->_M_current_pos + __n); }
1264 template<
class _CharT2,
class _Alloc2>
1266 operator==(
const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1267 const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
1269 template<
class _CharT2,
class _Alloc2>
1271 operator<(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1272 const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
1274 template<
class _CharT2,
class _Alloc2>
1276 operator-(
const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1277 const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
1280 template<
class _CharT,
class _Alloc>
1281 class _Rope_iterator
1282 :
public _Rope_iterator_base<_CharT, _Alloc>
1284 friend class rope<_CharT, _Alloc>;
1286 typedef typename _Rope_iterator_base<_CharT, _Alloc>::_RopeRep _RopeRep;
1287 rope<_CharT, _Alloc>* _M_root_rope;
1295 _Rope_iterator(rope<_CharT, _Alloc>* __r,
size_t __pos)
1296 : _Rope_iterator_base<_CharT, _Alloc>(__r->_M_tree_ptr, __pos),
1298 { _RopeRep::_S_ref(this->_M_root);
1299 if (!(__r -> empty()))
1305 typedef _Rope_char_ref_proxy<_CharT, _Alloc> reference;
1306 typedef _Rope_char_ref_proxy<_CharT, _Alloc>* pointer;
1308 rope<_CharT, _Alloc>&
1310 {
return *_M_root_rope; }
1317 _Rope_iterator(
const _Rope_iterator& __x)
1318 : _Rope_iterator_base<_CharT, _Alloc>(__x)
1320 _M_root_rope = __x._M_root_rope;
1321 _RopeRep::_S_ref(this->_M_root);
1324 _Rope_iterator(rope<_CharT, _Alloc>& __r,
size_t __pos);
1327 { _RopeRep::_S_unref(this->_M_root); }
1330 operator=(
const _Rope_iterator& __x)
1332 _RopeRep* __old = this->_M_root;
1334 _RopeRep::_S_ref(__x._M_root);
1335 if (0 != __x._M_buf_ptr)
1337 _M_root_rope = __x._M_root_rope;
1338 *(
static_cast<_Rope_iterator_base<_CharT, _Alloc>*
>(
this)) = __x;
1342 this->_M_current_pos = __x._M_current_pos;
1343 this->_M_root = __x._M_root;
1344 _M_root_rope = __x._M_root_rope;
1345 this->_M_buf_ptr = 0;
1347 _RopeRep::_S_unref(__old);
1355 if (0 == this->_M_buf_ptr)
1356 return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
1357 this->_M_current_pos);
1359 return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
1360 this->_M_current_pos,
1368 return *
const_cast<_Rope_iterator&
>(*this);
1379 operator+=(ptrdiff_t __n)
1384 this->_M_decr(-__n);
1396 operator-=(ptrdiff_t __n)
1401 this->_M_incr(-__n);
1408 size_t __old_pos = this->_M_current_pos;
1410 return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
1416 size_t __old_pos = this->_M_current_pos;
1418 return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
1422 operator[](ptrdiff_t __n)
1423 {
return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
1424 this->_M_current_pos
1427 template<
class _CharT2,
class _Alloc2>
1429 operator==(
const _Rope_iterator<_CharT2, _Alloc2>& __x,
1430 const _Rope_iterator<_CharT2, _Alloc2>& __y);
1432 template<
class _CharT2,
class _Alloc2>
1434 operator<(const _Rope_iterator<_CharT2, _Alloc2>& __x,
1435 const _Rope_iterator<_CharT2, _Alloc2>& __y);
1437 template<
class _CharT2,
class _Alloc2>
1439 operator-(
const _Rope_iterator<_CharT2, _Alloc2>& __x,
1440 const _Rope_iterator<_CharT2, _Alloc2>& __y);
1442 template<
class _CharT2,
class _Alloc2>
1443 friend _Rope_iterator<_CharT2, _Alloc2>
1444 operator-(
const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);
1446 template<
class _CharT2,
class _Alloc2>
1447 friend _Rope_iterator<_CharT2, _Alloc2>
1448 operator+(
const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);
1450 template<
class _CharT2,
class _Alloc2>
1451 friend _Rope_iterator<_CharT2, _Alloc2>
1452 operator+(ptrdiff_t __n,
const _Rope_iterator<_CharT2, _Alloc2>& __x);
1456 template <
class _CharT,
class _Alloc>
1460 typedef _Alloc allocator_type;
1463 get_allocator()
const
1464 {
return *
static_cast<const _Alloc*
>(
this); }
1468 {
return *
static_cast<_Alloc*
>(
this); }
1470 const allocator_type&
1471 _M_get_allocator()
const
1472 {
return *
static_cast<const _Alloc*
>(
this); }
1474 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
1477 _Rope_base(_RopeRep* __t,
const allocator_type&)
1478 : _M_tree_ptr(__t) { }
1480 _Rope_base(
const allocator_type&) { }
1483 _RopeRep *_M_tree_ptr;
1485 #define __ROPE_DEFINE_ALLOC(_Tp, __name) \
1487 _Alloc::template rebind<_Tp>::other __name##Alloc; \
1488 static _Tp* __name##_allocate(size_t __n) \
1489 { return __name##Alloc().allocate(__n); } \
1490 static void __name##_deallocate(_Tp *__p, size_t __n) \
1491 { __name##Alloc().deallocate(__p, __n); }
1492 __ROPE_DEFINE_ALLOCS(_Alloc)
1493 #undef __ROPE_DEFINE_ALLOC
1497 operator=(
const _Rope_base&);
1499 _Rope_base(
const _Rope_base&);
1507 template <
class _CharT,
class _Alloc>
1508 class rope :
public _Rope_base<_CharT, _Alloc>
1511 typedef _CharT value_type;
1512 typedef ptrdiff_t difference_type;
1513 typedef size_t size_type;
1514 typedef _CharT const_reference;
1515 typedef const _CharT* const_pointer;
1516 typedef _Rope_iterator<_CharT, _Alloc> iterator;
1517 typedef _Rope_const_iterator<_CharT, _Alloc> const_iterator;
1518 typedef _Rope_char_ref_proxy<_CharT, _Alloc> reference;
1519 typedef _Rope_char_ptr_proxy<_CharT, _Alloc> pointer;
1521 friend class _Rope_iterator<_CharT, _Alloc>;
1522 friend class _Rope_const_iterator<_CharT, _Alloc>;
1523 friend struct _Rope_RopeRep<_CharT, _Alloc>;
1524 friend class _Rope_iterator_base<_CharT, _Alloc>;
1525 friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;
1526 friend class _Rope_char_ref_proxy<_CharT, _Alloc>;
1527 friend struct _Rope_RopeSubstring<_CharT, _Alloc>;
1530 typedef _Rope_base<_CharT, _Alloc> _Base;
1531 typedef typename _Base::allocator_type allocator_type;
1532 using _Base::_M_tree_ptr;
1533 using _Base::get_allocator;
1534 using _Base::_M_get_allocator;
1535 typedef __GC_CONST _CharT* _Cstrptr;
1537 static _CharT _S_empty_c_str[1];
1541 {
return __c == _S_eos((_CharT*)0); }
1543 enum { _S_copy_max = 23 };
1547 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
1548 typedef _Rope_RopeConcatenation<_CharT, _Alloc> _RopeConcatenation;
1549 typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf;
1550 typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction;
1551 typedef _Rope_RopeSubstring<_CharT, _Alloc> _RopeSubstring;
1554 static _CharT _S_fetch(_RopeRep* __r, size_type __pos);
1563 static _CharT* _S_fetch_ptr(_RopeRep* __r, size_type __pos);
1568 _Rope_char_consumer<_CharT>& __c,
1569 const _RopeRep* __r,
1570 size_t __begin,
size_t __end);
1575 _S_unref(_RopeRep* __t)
1576 { _RopeRep::_S_unref(__t); }
1579 _S_ref(_RopeRep* __t)
1580 { _RopeRep::_S_ref(__t); }
1583 static void _S_unref(_RopeRep*) { }
1584 static void _S_ref(_RopeRep*) { }
1588 typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
1590 typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
1594 static _RopeRep* _S_substring(_RopeRep* __base,
1595 size_t __start,
size_t __endp1);
1597 static _RopeRep* _S_concat_char_iter(_RopeRep* __r,
1598 const _CharT* __iter,
size_t __slen);
1602 static _RopeRep* _S_destr_concat_char_iter(_RopeRep* __r,
1603 const _CharT* __iter,
1610 {
return _S_concat_char_iter(__r, __iter, __slen); }
1615 static _RopeRep* _S_concat(_RopeRep* __left, _RopeRep* __right);
1621 apply_to_pieces(
size_t __begin,
size_t __end,
1622 _Rope_char_consumer<_CharT>& __c)
const
1623 { _S_apply_to_pieces(__c, this->_M_tree_ptr, __begin, __end); }
1628 _S_rounded_up_size(
size_t __n)
1629 {
return _RopeLeaf::_S_rounded_up_size(__n); }
1632 _S_allocated_capacity(
size_t __n)
1634 if (_S_is_basic_char_type((_CharT*)0))
1635 return _S_rounded_up_size(__n) - 1;
1637 return _S_rounded_up_size(__n);
1644 _S_new_RopeLeaf(__GC_CONST _CharT *__s,
1645 size_t __size, allocator_type& __a)
1647 _RopeLeaf* __space =
typename _Base::_LAlloc(__a).allocate(1);
1648 return new(__space) _RopeLeaf(__s, __size, __a);
1651 static _RopeConcatenation*
1652 _S_new_RopeConcatenation(_RopeRep* __left, _RopeRep* __right,
1653 allocator_type& __a)
1655 _RopeConcatenation* __space =
typename _Base::_CAlloc(__a).allocate(1);
1656 return new(__space) _RopeConcatenation(__left, __right, __a);
1659 static _RopeFunction*
1660 _S_new_RopeFunction(char_producer<_CharT>* __f,
1661 size_t __size,
bool __d, allocator_type& __a)
1663 _RopeFunction* __space =
typename _Base::_FAlloc(__a).allocate(1);
1664 return new(__space) _RopeFunction(__f, __size, __d, __a);
1667 static _RopeSubstring*
1668 _S_new_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b,
size_t __s,
1669 size_t __l, allocator_type& __a)
1671 _RopeSubstring* __space =
typename _Base::_SAlloc(__a).allocate(1);
1672 return new(__space) _RopeSubstring(__b, __s, __l, __a);
1676 _S_RopeLeaf_from_unowned_char_ptr(
const _CharT *__s,
1677 size_t __size, allocator_type& __a)
1678 #define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) \
1679 _S_RopeLeaf_from_unowned_char_ptr(__s, __size, __a)
1683 _CharT* __buf = __a.allocate(_S_rounded_up_size(__size));
1685 __uninitialized_copy_n_a(__s, __size, __buf, __a);
1686 _S_cond_store_eos(__buf[__size]);
1688 {
return _S_new_RopeLeaf(__buf, __size, __a); }
1691 _RopeRep::__STL_FREE_STRING(__buf, __size, __a);
1692 __throw_exception_again;
1703 _S_tree_concat(_RopeRep* __left, _RopeRep* __right);
1707 _S_leaf_concat_char_iter(_RopeLeaf* __r,
1708 const _CharT* __iter,
size_t __slen);
1714 _S_destr_leaf_concat_char_iter(_RopeLeaf* __r,
1715 const _CharT* __iter,
size_t __slen);
1721 static size_t _S_char_ptr_len(
const _CharT* __s);
1724 rope(_RopeRep* __t,
const allocator_type& __a = allocator_type())
1725 : _Base(__t, __a) { }
1731 static _CharT* _S_flatten(_RopeRep* __r, _CharT* __buffer);
1735 static _CharT* _S_flatten(_RopeRep* __r,
1736 size_t __start,
size_t __len,
1739 static const unsigned long
1740 _S_min_len[__detail::_S_max_rope_depth + 1];
1743 _S_is_balanced(_RopeRep* __r)
1744 {
return (__r->_M_size >= _S_min_len[__r->_M_depth]); }
1747 _S_is_almost_balanced(_RopeRep* __r)
1748 {
return (__r->_M_depth == 0
1749 || __r->_M_size >= _S_min_len[__r->_M_depth - 1]); }
1752 _S_is_roughly_balanced(_RopeRep* __r)
1753 {
return (__r->_M_depth <= 1
1754 || __r->_M_size >= _S_min_len[__r->_M_depth - 2]); }
1758 _S_concat_and_set_balanced(_RopeRep* __left, _RopeRep* __right)
1760 _RopeRep* __result = _S_concat(__left, __right);
1761 if (_S_is_balanced(__result))
1762 __result->_M_is_balanced =
true;
1771 static _RopeRep* _S_balance(_RopeRep* __r);
1775 static void _S_add_to_forest(_RopeRep*__r, _RopeRep** __forest);
1778 static void _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest);
1781 static void _S_dump(_RopeRep* __r,
int __indent = 0);
1784 static int _S_compare(
const _RopeRep* __x,
const _RopeRep* __y);
1789 {
return 0 == this->_M_tree_ptr; }
1795 compare(
const rope& __y)
const
1796 {
return _S_compare(this->_M_tree_ptr, __y._M_tree_ptr); }
1798 rope(
const _CharT* __s,
const allocator_type& __a = allocator_type())
1802 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, _S_char_ptr_len(__s),
1803 _M_get_allocator());
1806 rope(
const _CharT* __s,
size_t __len,
1807 const allocator_type& __a = allocator_type())
1811 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __len, _M_get_allocator());
1817 rope(
const _CharT* __s,
const _CharT* __e,
1818 const allocator_type& __a = allocator_type())
1822 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __e - __s, _M_get_allocator());
1825 rope(
const const_iterator& __s,
const const_iterator& __e,
1826 const allocator_type& __a = allocator_type())
1827 : _Base(_S_substring(__s._M_root, __s._M_current_pos,
1828 __e._M_current_pos), __a)
1831 rope(
const iterator& __s,
const iterator& __e,
1832 const allocator_type& __a = allocator_type())
1833 : _Base(_S_substring(__s._M_root, __s._M_current_pos,
1834 __e._M_current_pos), __a)
1837 rope(_CharT __c,
const allocator_type& __a = allocator_type())
1840 _CharT* __buf = this->_Data_allocate(_S_rounded_up_size(1));
1842 _M_get_allocator().construct(__buf, __c);
1845 this->_M_tree_ptr = _S_new_RopeLeaf(__buf, 1,
1846 _M_get_allocator());
1850 _RopeRep::__STL_FREE_STRING(__buf, 1, _M_get_allocator());
1851 __throw_exception_again;
1855 rope(
size_t __n, _CharT __c,
1856 const allocator_type& __a = allocator_type());
1858 rope(
const allocator_type& __a = allocator_type())
1862 rope(char_producer<_CharT> *__fn,
size_t __len,
bool __delete_fn,
1863 const allocator_type& __a = allocator_type())
1866 this->_M_tree_ptr = (0 == __len) ?
1867 0 : _S_new_RopeFunction(__fn, __len, __delete_fn, __a);
1870 rope(
const rope& __x,
const allocator_type& __a = allocator_type())
1871 : _Base(__x._M_tree_ptr, __a)
1872 { _S_ref(this->_M_tree_ptr); }
1875 { _S_unref(this->_M_tree_ptr); }
1878 operator=(
const rope& __x)
1880 _RopeRep* __old = this->_M_tree_ptr;
1881 this->_M_tree_ptr = __x._M_tree_ptr;
1882 _S_ref(this->_M_tree_ptr);
1890 _S_unref(this->_M_tree_ptr);
1891 this->_M_tree_ptr = 0;
1895 push_back(_CharT __x)
1897 _RopeRep* __old = this->_M_tree_ptr;
1899 = _S_destr_concat_char_iter(this->_M_tree_ptr, &__x, 1);
1906 _RopeRep* __old = this->_M_tree_ptr;
1907 this->_M_tree_ptr = _S_substring(this->_M_tree_ptr,
1908 0, this->_M_tree_ptr->_M_size - 1);
1914 {
return _S_fetch(this->_M_tree_ptr, this->_M_tree_ptr->_M_size - 1); }
1917 push_front(_CharT __x)
1919 _RopeRep* __old = this->_M_tree_ptr;
1921 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1, _M_get_allocator());
1924 this->_M_tree_ptr = _S_concat(__left, this->_M_tree_ptr);
1931 __throw_exception_again;
1938 _RopeRep* __old = this->_M_tree_ptr;
1940 = _S_substring(this->_M_tree_ptr, 1, this->_M_tree_ptr->_M_size);
1946 {
return _S_fetch(this->_M_tree_ptr, 0); }
1951 _RopeRep* __old = this->_M_tree_ptr;
1952 this->_M_tree_ptr = _S_balance(this->_M_tree_ptr);
1957 copy(_CharT* __buffer)
const
1959 _Destroy_const(__buffer, __buffer + size(), _M_get_allocator());
1960 _S_flatten(this->_M_tree_ptr, __buffer);
1969 copy(size_type __pos, size_type __n, _CharT* __buffer)
const
1971 size_t __size = size();
1972 size_t __len = (__pos + __n > __size? __size - __pos : __n);
1974 _Destroy_const(__buffer, __buffer + __len, _M_get_allocator());
1975 _S_flatten(this->_M_tree_ptr, __pos, __len, __buffer);
1983 { _S_dump(this->_M_tree_ptr); }
1987 const _CharT* c_str()
const;
1991 const _CharT* replace_with_c_str();
1999 if (0 == this->_M_tree_ptr)
2001 if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag &&
2002 ((_RopeLeaf*)this->_M_tree_ptr)->_M_data ==
2003 this->_M_tree_ptr->_M_c_string)
2009 this->_M_tree_ptr->_M_free_c_string();
2011 this->_M_tree_ptr->_M_c_string = 0;
2015 operator[] (size_type __pos)
const
2016 {
return _S_fetch(this->_M_tree_ptr, __pos); }
2019 at(size_type __pos)
const
2022 return (*
this)[__pos];
2027 {
return(const_iterator(this->_M_tree_ptr, 0)); }
2032 {
return(const_iterator(this->_M_tree_ptr, 0)); }
2036 {
return(const_iterator(this->_M_tree_ptr, size())); }
2040 {
return(const_iterator(this->_M_tree_ptr, size())); }
2044 {
return(0 == this->_M_tree_ptr? 0 : this->_M_tree_ptr->_M_size); }
2053 return _S_min_len[int(__detail::_S_max_rope_depth) - 1] - 1;
2066 const_rbegin()
const
2077 template<
class _CharT2,
class _Alloc2>
2082 template<
class _CharT2,
class _Alloc2>
2086 template<
class _CharT2,
class _Alloc2>
2097 append(
const _CharT* __iter,
size_t __n)
2099 _RopeRep* __result =
2100 _S_destr_concat_char_iter(this->_M_tree_ptr, __iter, __n);
2101 _S_unref(this->_M_tree_ptr);
2102 this->_M_tree_ptr = __result;
2107 append(
const _CharT* __c_string)
2109 size_t __len = _S_char_ptr_len(__c_string);
2110 append(__c_string, __len);
2115 append(
const _CharT* __s,
const _CharT* __e)
2117 _RopeRep* __result =
2118 _S_destr_concat_char_iter(this->_M_tree_ptr, __s, __e - __s);
2119 _S_unref(this->_M_tree_ptr);
2120 this->_M_tree_ptr = __result;
2125 append(const_iterator __s, const_iterator __e)
2127 _Self_destruct_ptr __appendee(_S_substring(__s._M_root,
2129 __e._M_current_pos));
2130 _RopeRep* __result = _S_concat(this->_M_tree_ptr,
2131 (_RopeRep*)__appendee);
2132 _S_unref(this->_M_tree_ptr);
2133 this->_M_tree_ptr = __result;
2140 _RopeRep* __result =
2141 _S_destr_concat_char_iter(this->_M_tree_ptr, &__c, 1);
2142 _S_unref(this->_M_tree_ptr);
2143 this->_M_tree_ptr = __result;
2149 {
return append(_CharT()); }
2152 append(
const rope& __y)
2154 _RopeRep* __result = _S_concat(this->_M_tree_ptr, __y._M_tree_ptr);
2155 _S_unref(this->_M_tree_ptr);
2156 this->_M_tree_ptr = __result;
2161 append(
size_t __n, _CharT __c)
2164 return append(__last);
2170 _RopeRep* __tmp = this->_M_tree_ptr;
2171 this->_M_tree_ptr = __b._M_tree_ptr;
2172 __b._M_tree_ptr = __tmp;
2178 replace(_RopeRep* __old,
size_t __pos1,
2179 size_t __pos2, _RopeRep* __r)
2186 _Self_destruct_ptr __left(_S_substring(__old, 0, __pos1));
2187 _Self_destruct_ptr __right(_S_substring(__old, __pos2, __old->_M_size));
2191 __result = _S_concat(__left, __right);
2194 _Self_destruct_ptr __left_result(_S_concat(__left, __r));
2195 __result = _S_concat(__left_result, __right);
2202 insert(
size_t __p,
const rope& __r)
2204 _RopeRep* __result =
2205 replace(this->_M_tree_ptr, __p, __p, __r._M_tree_ptr);
2206 _S_unref(this->_M_tree_ptr);
2207 this->_M_tree_ptr = __result;
2211 insert(
size_t __p,
size_t __n, _CharT __c)
2218 insert(
size_t __p,
const _CharT* __i,
size_t __n)
2220 _Self_destruct_ptr __left(_S_substring(this->_M_tree_ptr, 0, __p));
2221 _Self_destruct_ptr __right(_S_substring(this->_M_tree_ptr,
2223 _Self_destruct_ptr __left_result(_S_concat_char_iter(__left, __i, __n));
2227 _RopeRep* __result = _S_concat(__left_result, __right);
2228 _S_unref(this->_M_tree_ptr);
2229 this->_M_tree_ptr = __result;
2233 insert(
size_t __p,
const _CharT* __c_string)
2234 { insert(__p, __c_string, _S_char_ptr_len(__c_string)); }
2237 insert(
size_t __p, _CharT __c)
2238 { insert(__p, &__c, 1); }
2243 _CharT __c = _CharT();
2244 insert(__p, &__c, 1);
2248 insert(
size_t __p,
const _CharT* __i,
const _CharT* __j)
2255 insert(
size_t __p,
const const_iterator& __i,
2256 const const_iterator& __j)
2263 insert(
size_t __p,
const iterator& __i,
2264 const iterator& __j)
2273 replace(
size_t __p,
size_t __n,
const rope& __r)
2275 _RopeRep* __result =
2276 replace(this->_M_tree_ptr, __p, __p + __n, __r._M_tree_ptr);
2277 _S_unref(this->_M_tree_ptr);
2278 this->_M_tree_ptr = __result;
2282 replace(
size_t __p,
size_t __n,
2283 const _CharT* __i,
size_t __i_len)
2285 rope __r(__i, __i_len);
2286 replace(__p, __n, __r);
2290 replace(
size_t __p,
size_t __n, _CharT __c)
2293 replace(__p, __n, __r);
2297 replace(
size_t __p,
size_t __n,
const _CharT* __c_string)
2299 rope __r(__c_string);
2300 replace(__p, __n, __r);
2304 replace(
size_t __p,
size_t __n,
2305 const _CharT* __i,
const _CharT* __j)
2308 replace(__p, __n, __r);
2312 replace(
size_t __p,
size_t __n,
2313 const const_iterator& __i,
const const_iterator& __j)
2316 replace(__p, __n, __r);
2320 replace(
size_t __p,
size_t __n,
2321 const iterator& __i,
const iterator& __j)
2324 replace(__p, __n, __r);
2329 replace(
size_t __p, _CharT __c)
2331 iterator __i(
this, __p);
2336 replace(
size_t __p,
const rope& __r)
2337 { replace(__p, 1, __r); }
2340 replace(
size_t __p,
const _CharT* __i,
size_t __i_len)
2341 { replace(__p, 1, __i, __i_len); }
2344 replace(
size_t __p,
const _CharT* __c_string)
2345 { replace(__p, 1, __c_string); }
2348 replace(
size_t __p,
const _CharT* __i,
const _CharT* __j)
2349 { replace(__p, 1, __i, __j); }
2352 replace(
size_t __p,
const const_iterator& __i,
2353 const const_iterator& __j)
2354 { replace(__p, 1, __i, __j); }
2357 replace(
size_t __p,
const iterator& __i,
2358 const iterator& __j)
2359 { replace(__p, 1, __i, __j); }
2363 erase(
size_t __p,
size_t __n)
2365 _RopeRep* __result = replace(this->_M_tree_ptr, __p,
2367 _S_unref(this->_M_tree_ptr);
2368 this->_M_tree_ptr = __result;
2374 { erase(__p, __p + 1); }
2378 insert(
const iterator& __p,
const rope& __r)
2380 insert(__p.index(), __r);
2385 insert(
const iterator& __p,
size_t __n, _CharT __c)
2387 insert(__p.index(), __n, __c);
2391 iterator insert(
const iterator& __p, _CharT __c)
2393 insert(__p.index(), __c);
2398 insert(
const iterator& __p )
2400 insert(__p.index());
2405 insert(
const iterator& __p,
const _CharT* c_string)
2407 insert(__p.index(), c_string);
2412 insert(
const iterator& __p,
const _CharT* __i,
size_t __n)
2414 insert(__p.index(), __i, __n);
2419 insert(
const iterator& __p,
const _CharT* __i,
2422 insert(__p.index(), __i, __j);
2427 insert(
const iterator& __p,
2428 const const_iterator& __i,
const const_iterator& __j)
2430 insert(__p.index(), __i, __j);
2435 insert(
const iterator& __p,
2436 const iterator& __i,
const iterator& __j)
2438 insert(__p.index(), __i, __j);
2444 replace(
const iterator& __p,
const iterator& __q,
const rope& __r)
2445 { replace(__p.index(), __q.index() - __p.index(), __r); }
2448 replace(
const iterator& __p,
const iterator& __q, _CharT __c)
2449 { replace(__p.index(), __q.index() - __p.index(), __c); }
2452 replace(
const iterator& __p,
const iterator& __q,
2453 const _CharT* __c_string)
2454 { replace(__p.index(), __q.index() - __p.index(), __c_string); }
2457 replace(
const iterator& __p,
const iterator& __q,
2458 const _CharT* __i,
size_t __n)
2459 { replace(__p.index(), __q.index() - __p.index(), __i, __n); }
2462 replace(
const iterator& __p,
const iterator& __q,
2463 const _CharT* __i,
const _CharT* __j)
2464 { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
2467 replace(
const iterator& __p,
const iterator& __q,
2468 const const_iterator& __i,
const const_iterator& __j)
2469 { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
2472 replace(
const iterator& __p,
const iterator& __q,
2473 const iterator& __i,
const iterator& __j)
2474 { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
2478 replace(
const iterator& __p,
const rope& __r)
2479 { replace(__p.index(), __r); }
2482 replace(
const iterator& __p, _CharT __c)
2483 { replace(__p.index(), __c); }
2486 replace(
const iterator& __p,
const _CharT* __c_string)
2487 { replace(__p.index(), __c_string); }
2490 replace(
const iterator& __p,
const _CharT* __i,
size_t __n)
2491 { replace(__p.index(), __i, __n); }
2494 replace(
const iterator& __p,
const _CharT* __i,
const _CharT* __j)
2495 { replace(__p.index(), __i, __j); }
2498 replace(
const iterator& __p, const_iterator __i, const_iterator __j)
2499 { replace(__p.index(), __i, __j); }
2502 replace(
const iterator& __p, iterator __i, iterator __j)
2503 { replace(__p.index(), __i, __j); }
2507 erase(
const iterator& __p,
const iterator& __q)
2509 size_t __p_index = __p.index();
2510 erase(__p_index, __q.index() - __p_index);
2511 return iterator(
this, __p_index);
2515 erase(
const iterator& __p)
2517 size_t __p_index = __p.index();
2518 erase(__p_index, 1);
2519 return iterator(
this, __p_index);
2523 substr(
size_t __start,
size_t __len = 1)
const
2531 substr(iterator __start, iterator __end)
const
2539 substr(iterator __start)
const
2541 size_t __pos = __start.index();
2547 substr(const_iterator __start, const_iterator __end)
const
2557 substr(const_iterator __start)
2559 size_t __pos = __start.index();
2564 static const size_type npos;
2566 size_type find(_CharT __c, size_type __pos = 0)
const;
2569 find(
const _CharT* __s, size_type __pos = 0)
const
2571 size_type __result_pos;
2572 const_iterator __result =
2573 std::search(const_begin() + __pos, const_end(),
2574 __s, __s + _S_char_ptr_len(__s));
2575 __result_pos = __result.index();
2576 #ifndef __STL_OLD_ROPE_SEMANTICS
2577 if (__result_pos == size())
2578 __result_pos = npos;
2580 return __result_pos;
2585 {
return(iterator(
this, 0)); }
2589 {
return(iterator(
this, size())); }
2602 mutable_reference_at(size_type __pos)
2603 {
return reference(
this, __pos); }
2607 operator[] (size_type __pos)
2608 {
return _char_ref_proxy(
this, __pos); }
2614 return (*
this)[__pos];
2617 void resize(size_type __n, _CharT __c) { }
2618 void resize(size_type __n) { }
2619 void reserve(size_type __res_arg = 0) { }
2623 {
return max_size(); }
2629 copy(_CharT* __buffer, size_type __n,
2630 size_type __pos = 0)
const
2631 {
return copy(__pos, __n, __buffer); }
2635 {
return mutable_end(); }
2639 {
return mutable_begin(); }
2643 {
return mutable_rend(); }
2647 {
return mutable_rbegin(); }
2652 {
return const_end(); }
2656 {
return const_begin(); }
2660 {
return const_rend(); }
2664 {
return const_rbegin(); }
2669 template <
class _CharT,
class _Alloc>
2670 const typename rope<_CharT, _Alloc>::size_type
2673 template <
class _CharT,
class _Alloc>
2674 inline bool operator==(
const _Rope_const_iterator<_CharT, _Alloc>& __x,
2675 const _Rope_const_iterator<_CharT, _Alloc>& __y)
2676 {
return (__x._M_current_pos == __y._M_current_pos
2677 && __x._M_root == __y._M_root); }
2679 template <
class _CharT,
class _Alloc>
2680 inline bool operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2681 const _Rope_const_iterator<_CharT, _Alloc>& __y)
2682 {
return (__x._M_current_pos < __y._M_current_pos); }
2684 template <
class _CharT,
class _Alloc>
2685 inline bool operator!=(
const _Rope_const_iterator<_CharT, _Alloc>& __x,
2686 const _Rope_const_iterator<_CharT, _Alloc>& __y)
2687 {
return !(__x == __y); }
2689 template <
class _CharT,
class _Alloc>
2690 inline bool operator>(
const _Rope_const_iterator<_CharT, _Alloc>& __x,
2691 const _Rope_const_iterator<_CharT, _Alloc>& __y)
2692 {
return __y < __x; }
2694 template <
class _CharT,
class _Alloc>
2696 operator<=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2697 const _Rope_const_iterator<_CharT, _Alloc>& __y)
2698 {
return !(__y < __x); }
2700 template <
class _CharT,
class _Alloc>
2702 operator>=(
const _Rope_const_iterator<_CharT, _Alloc>& __x,
2703 const _Rope_const_iterator<_CharT, _Alloc>& __y)
2704 {
return !(__x < __y); }
2706 template <
class _CharT,
class _Alloc>
2708 operator-(
const _Rope_const_iterator<_CharT, _Alloc>& __x,
2709 const _Rope_const_iterator<_CharT, _Alloc>& __y)
2710 {
return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; }
2712 template <
class _CharT,
class _Alloc>
2713 inline _Rope_const_iterator<_CharT, _Alloc>
2714 operator-(
const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
2715 {
return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
2716 __x._M_current_pos - __n); }
2718 template <
class _CharT,
class _Alloc>
2719 inline _Rope_const_iterator<_CharT, _Alloc>
2720 operator+(
const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
2721 {
return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
2722 __x._M_current_pos + __n); }
2724 template <
class _CharT,
class _Alloc>
2725 inline _Rope_const_iterator<_CharT, _Alloc>
2726 operator+(ptrdiff_t __n,
const _Rope_const_iterator<_CharT, _Alloc>& __x)
2727 {
return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
2728 __x._M_current_pos + __n); }
2730 template <
class _CharT,
class _Alloc>
2732 operator==(
const _Rope_iterator<_CharT, _Alloc>& __x,
2733 const _Rope_iterator<_CharT, _Alloc>& __y)
2734 {
return (__x._M_current_pos == __y._M_current_pos
2735 && __x._M_root_rope == __y._M_root_rope); }
2737 template <
class _CharT,
class _Alloc>
2739 operator<(const _Rope_iterator<_CharT, _Alloc>& __x,
2740 const _Rope_iterator<_CharT, _Alloc>& __y)
2741 {
return (__x._M_current_pos < __y._M_current_pos); }
2743 template <
class _CharT,
class _Alloc>
2745 operator!=(
const _Rope_iterator<_CharT, _Alloc>& __x,
2746 const _Rope_iterator<_CharT, _Alloc>& __y)
2747 {
return !(__x == __y); }
2749 template <
class _CharT,
class _Alloc>
2751 operator>(
const _Rope_iterator<_CharT, _Alloc>& __x,
2752 const _Rope_iterator<_CharT, _Alloc>& __y)
2753 {
return __y < __x; }
2755 template <
class _CharT,
class _Alloc>
2757 operator<=(const _Rope_iterator<_CharT, _Alloc>& __x,
2758 const _Rope_iterator<_CharT, _Alloc>& __y)
2759 {
return !(__y < __x); }
2761 template <
class _CharT,
class _Alloc>
2763 operator>=(
const _Rope_iterator<_CharT, _Alloc>& __x,
2764 const _Rope_iterator<_CharT, _Alloc>& __y)
2765 {
return !(__x < __y); }
2767 template <
class _CharT,
class _Alloc>
2769 operator-(
const _Rope_iterator<_CharT, _Alloc>& __x,
2770 const _Rope_iterator<_CharT, _Alloc>& __y)
2771 {
return ((ptrdiff_t)__x._M_current_pos
2772 - (ptrdiff_t)__y._M_current_pos); }
2774 template <
class _CharT,
class _Alloc>
2775 inline _Rope_iterator<_CharT, _Alloc>
2776 operator-(
const _Rope_iterator<_CharT, _Alloc>& __x,
2778 {
return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
2779 __x._M_current_pos - __n); }
2781 template <
class _CharT,
class _Alloc>
2782 inline _Rope_iterator<_CharT, _Alloc>
2783 operator+(
const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
2784 {
return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
2785 __x._M_current_pos + __n); }
2787 template <
class _CharT,
class _Alloc>
2788 inline _Rope_iterator<_CharT, _Alloc>
2789 operator+(ptrdiff_t __n,
const _Rope_iterator<_CharT, _Alloc>& __x)
2790 {
return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
2791 __x._M_current_pos + __n); }
2793 template <
class _CharT,
class _Alloc>
2794 inline rope<_CharT, _Alloc>
2795 operator+(
const rope<_CharT, _Alloc>& __left,
2796 const rope<_CharT, _Alloc>& __right)
2800 typedef rope<_CharT, _Alloc> rope_type;
2801 return rope_type(rope_type::_S_concat(__left._M_tree_ptr,
2802 __right._M_tree_ptr));
2805 template <
class _CharT,
class _Alloc>
2806 inline rope<_CharT, _Alloc>&
2807 operator+=(rope<_CharT, _Alloc>& __left,
2808 const rope<_CharT, _Alloc>& __right)
2810 __left.append(__right);
2814 template <
class _CharT,
class _Alloc>
2815 inline rope<_CharT, _Alloc>
2816 operator+(
const rope<_CharT, _Alloc>& __left,
2817 const _CharT* __right)
2819 typedef rope<_CharT, _Alloc> rope_type;
2820 size_t __rlen = rope_type::_S_char_ptr_len(__right);
2821 return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
2825 template <
class _CharT,
class _Alloc>
2826 inline rope<_CharT, _Alloc>&
2827 operator+=(rope<_CharT, _Alloc>& __left,
2828 const _CharT* __right)
2830 __left.append(__right);
2834 template <
class _CharT,
class _Alloc>
2835 inline rope<_CharT, _Alloc>
2836 operator+(
const rope<_CharT, _Alloc>& __left, _CharT __right)
2838 typedef rope<_CharT, _Alloc> rope_type;
2839 return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
2843 template <
class _CharT,
class _Alloc>
2844 inline rope<_CharT, _Alloc>&
2845 operator+=(rope<_CharT, _Alloc>& __left, _CharT __right)
2847 __left.append(__right);
2851 template <
class _CharT,
class _Alloc>
2853 operator<(const rope<_CharT, _Alloc>& __left,
2854 const rope<_CharT, _Alloc>& __right)
2855 {
return __left.compare(__right) < 0; }
2857 template <
class _CharT,
class _Alloc>
2859 operator==(
const rope<_CharT, _Alloc>& __left,
2860 const rope<_CharT, _Alloc>& __right)
2861 {
return __left.compare(__right) == 0; }
2863 template <
class _CharT,
class _Alloc>
2865 operator==(
const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
2866 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
2867 {
return (__x._M_pos == __y._M_pos && __x._M_root == __y._M_root); }
2869 template <
class _CharT,
class _Alloc>
2871 operator!=(
const rope<_CharT, _Alloc>& __x,
2872 const rope<_CharT, _Alloc>& __y)
2873 {
return !(__x == __y); }
2875 template <
class _CharT,
class _Alloc>
2877 operator>(
const rope<_CharT, _Alloc>& __x,
2878 const rope<_CharT, _Alloc>& __y)
2879 {
return __y < __x; }
2881 template <
class _CharT,
class _Alloc>
2883 operator<=(const rope<_CharT, _Alloc>& __x,
2884 const rope<_CharT, _Alloc>& __y)
2885 {
return !(__y < __x); }
2887 template <
class _CharT,
class _Alloc>
2889 operator>=(
const rope<_CharT, _Alloc>& __x,
2890 const rope<_CharT, _Alloc>& __y)
2891 {
return !(__x < __y); }
2893 template <
class _CharT,
class _Alloc>
2895 operator!=(
const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
2896 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
2897 {
return !(__x == __y); }
2899 template<
class _CharT,
class _Traits,
class _Alloc>
2901 operator<<(std::basic_ostream<_CharT, _Traits>& __o,
2902 const rope<_CharT, _Alloc>& __r);
2904 typedef rope<char> crope;
2905 typedef rope<wchar_t> wrope;
2907 inline crope::reference
2908 __mutable_reference_at(crope& __c,
size_t __i)
2909 {
return __c.mutable_reference_at(__i); }
2911 inline wrope::reference
2912 __mutable_reference_at(wrope& __c,
size_t __i)
2913 {
return __c.mutable_reference_at(__i); }
2915 template <
class _CharT,
class _Alloc>
2917 swap(rope<_CharT, _Alloc>& __x, rope<_CharT, _Alloc>& __y)
2920 _GLIBCXX_END_NAMESPACE
2928 struct hash<__gnu_cxx::crope>
2933 size_t __size = __str.size();
2936 return 13 * __str[0] + 5 * __str[__size - 1] + __size;
2942 struct hash<__gnu_cxx::wrope>
2947 size_t __size = __str.size();
2950 return 13 * __str[0] + 5 * __str[__size - 1] + __size;