00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034
00035
00036
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049 #ifndef _ROPE
00050 #define _ROPE 1
00051
00052 #include <bits/stl_algobase.h>
00053 #include <bits/stl_construct.h>
00054 #include <bits/stl_uninitialized.h>
00055 #include <bits/stl_algo.h>
00056 #include <bits/stl_function.h>
00057 #include <bits/stl_numeric.h>
00058 #include <bits/allocator.h>
00059 #include <ext/hash_fun.h>
00060
00061 # ifdef __GC
00062 # define __GC_CONST const
00063 # else
00064 # include <bits/gthr.h>
00065 # define __GC_CONST // constant except for deallocation
00066 # endif
00067
00068 #include <ext/memory>
00069
00070 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
00071
00072 namespace __detail
00073 {
00074 enum { _S_max_rope_depth = 45 };
00075 enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function};
00076 }
00077
00078 using std::size_t;
00079 using std::ptrdiff_t;
00080 using std::allocator;
00081 using std::iterator;
00082 using std::reverse_iterator;
00083 using std::_Destroy;
00084
00085
00086
00087
00088
00089
00090 template <class _CharT>
00091 inline _CharT
00092 _S_eos(_CharT*)
00093 { return _CharT(); }
00094
00095
00096
00097 template <class _CharT>
00098 inline bool
00099 _S_is_basic_char_type(_CharT*)
00100 { return false; }
00101
00102 template <class _CharT>
00103 inline bool
00104 _S_is_one_byte_char_type(_CharT*)
00105 { return false; }
00106
00107 inline bool
00108 _S_is_basic_char_type(char*)
00109 { return true; }
00110
00111 inline bool
00112 _S_is_one_byte_char_type(char*)
00113 { return true; }
00114
00115 inline bool
00116 _S_is_basic_char_type(wchar_t*)
00117 { return true; }
00118
00119
00120
00121 template <class _CharT>
00122 inline void
00123 _S_cond_store_eos(_CharT&) { }
00124
00125 inline void
00126 _S_cond_store_eos(char& __c)
00127 { __c = 0; }
00128
00129 inline void
00130 _S_cond_store_eos(wchar_t& __c)
00131 { __c = 0; }
00132
00133
00134
00135
00136
00137 template <class _CharT>
00138 class char_producer
00139 {
00140 public:
00141 virtual ~char_producer() { };
00142
00143 virtual void
00144 operator()(size_t __start_pos, size_t __len,
00145 _CharT* __buffer) = 0;
00146
00147
00148
00149
00150 };
00151
00152
00153
00154
00155
00156
00157
00158
00159
00160
00161
00162
00163
00164
00165
00166 template<class _Sequence, size_t _Buf_sz = 100>
00167 class sequence_buffer
00168 : public iterator<std::output_iterator_tag, void, void, void, void>
00169 {
00170 public:
00171 typedef typename _Sequence::value_type value_type;
00172 protected:
00173 _Sequence* _M_prefix;
00174 value_type _M_buffer[_Buf_sz];
00175 size_t _M_buf_count;
00176 public:
00177
00178 void
00179 flush()
00180 {
00181 _M_prefix->append(_M_buffer, _M_buffer + _M_buf_count);
00182 _M_buf_count = 0;
00183 }
00184
00185 ~sequence_buffer()
00186 { flush(); }
00187
00188 sequence_buffer()
00189 : _M_prefix(0), _M_buf_count(0) { }
00190
00191 sequence_buffer(const sequence_buffer& __x)
00192 {
00193 _M_prefix = __x._M_prefix;
00194 _M_buf_count = __x._M_buf_count;
00195 std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
00196 }
00197
00198 sequence_buffer(sequence_buffer& __x)
00199 {
00200 __x.flush();
00201 _M_prefix = __x._M_prefix;
00202 _M_buf_count = 0;
00203 }
00204
00205 sequence_buffer(_Sequence& __s)
00206 : _M_prefix(&__s), _M_buf_count(0) { }
00207
00208 sequence_buffer&
00209 operator=(sequence_buffer& __x)
00210 {
00211 __x.flush();
00212 _M_prefix = __x._M_prefix;
00213 _M_buf_count = 0;
00214 return *this;
00215 }
00216
00217 sequence_buffer&
00218 operator=(const sequence_buffer& __x)
00219 {
00220 _M_prefix = __x._M_prefix;
00221 _M_buf_count = __x._M_buf_count;
00222 std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
00223 return *this;
00224 }
00225
00226 void
00227 push_back(value_type __x)
00228 {
00229 if (_M_buf_count < _Buf_sz)
00230 {
00231 _M_buffer[_M_buf_count] = __x;
00232 ++_M_buf_count;
00233 }
00234 else
00235 {
00236 flush();
00237 _M_buffer[0] = __x;
00238 _M_buf_count = 1;
00239 }
00240 }
00241
00242 void
00243 append(value_type* __s, size_t __len)
00244 {
00245 if (__len + _M_buf_count <= _Buf_sz)
00246 {
00247 size_t __i = _M_buf_count;
00248 for (size_t __j = 0; __j < __len; __i++, __j++)
00249 _M_buffer[__i] = __s[__j];
00250 _M_buf_count += __len;
00251 }
00252 else if (0 == _M_buf_count)
00253 _M_prefix->append(__s, __s + __len);
00254 else
00255 {
00256 flush();
00257 append(__s, __len);
00258 }
00259 }
00260
00261 sequence_buffer&
00262 write(value_type* __s, size_t __len)
00263 {
00264 append(__s, __len);
00265 return *this;
00266 }
00267
00268 sequence_buffer&
00269 put(value_type __x)
00270 {
00271 push_back(__x);
00272 return *this;
00273 }
00274
00275 sequence_buffer&
00276 operator=(const value_type& __rhs)
00277 {
00278 push_back(__rhs);
00279 return *this;
00280 }
00281
00282 sequence_buffer&
00283 operator*()
00284 { return *this; }
00285
00286 sequence_buffer&
00287 operator++()
00288 { return *this; }
00289
00290 sequence_buffer
00291 operator++(int)
00292 { return *this; }
00293 };
00294
00295
00296 template<class _CharT>
00297 class _Rope_char_consumer
00298 {
00299 public:
00300
00301
00302
00303
00304
00305 virtual ~_Rope_char_consumer() { };
00306
00307 virtual bool
00308 operator()(const _CharT* __buffer, size_t __len) = 0;
00309 };
00310
00311
00312
00313
00314 template<class _CharT, class _Alloc = allocator<_CharT> >
00315 class rope;
00316
00317 template<class _CharT, class _Alloc>
00318 struct _Rope_RopeConcatenation;
00319
00320 template<class _CharT, class _Alloc>
00321 struct _Rope_RopeLeaf;
00322
00323 template<class _CharT, class _Alloc>
00324 struct _Rope_RopeFunction;
00325
00326 template<class _CharT, class _Alloc>
00327 struct _Rope_RopeSubstring;
00328
00329 template<class _CharT, class _Alloc>
00330 class _Rope_iterator;
00331
00332 template<class _CharT, class _Alloc>
00333 class _Rope_const_iterator;
00334
00335 template<class _CharT, class _Alloc>
00336 class _Rope_char_ref_proxy;
00337
00338 template<class _CharT, class _Alloc>
00339 class _Rope_char_ptr_proxy;
00340
00341 template<class _CharT, class _Alloc>
00342 bool
00343 operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
00344 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y);
00345
00346 template<class _CharT, class _Alloc>
00347 _Rope_const_iterator<_CharT, _Alloc>
00348 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
00349 ptrdiff_t __n);
00350
00351 template<class _CharT, class _Alloc>
00352 _Rope_const_iterator<_CharT, _Alloc>
00353 operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x,
00354 ptrdiff_t __n);
00355
00356 template<class _CharT, class _Alloc>
00357 _Rope_const_iterator<_CharT, _Alloc>
00358 operator+(ptrdiff_t __n,
00359 const _Rope_const_iterator<_CharT, _Alloc>& __x);
00360
00361 template<class _CharT, class _Alloc>
00362 bool
00363 operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x,
00364 const _Rope_const_iterator<_CharT, _Alloc>& __y);
00365
00366 template<class _CharT, class _Alloc>
00367 bool
00368 operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,
00369 const _Rope_const_iterator<_CharT, _Alloc>& __y);
00370
00371 template<class _CharT, class _Alloc>
00372 ptrdiff_t
00373 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
00374 const _Rope_const_iterator<_CharT, _Alloc>& __y);
00375
00376 template<class _CharT, class _Alloc>
00377 _Rope_iterator<_CharT, _Alloc>
00378 operator-(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);
00379
00380 template<class _CharT, class _Alloc>
00381 _Rope_iterator<_CharT, _Alloc>
00382 operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);
00383
00384 template<class _CharT, class _Alloc>
00385 _Rope_iterator<_CharT, _Alloc>
00386 operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x);
00387
00388 template<class _CharT, class _Alloc>
00389 bool
00390 operator==(const _Rope_iterator<_CharT, _Alloc>& __x,
00391 const _Rope_iterator<_CharT, _Alloc>& __y);
00392
00393 template<class _CharT, class _Alloc>
00394 bool
00395 operator<(const _Rope_iterator<_CharT, _Alloc>& __x,
00396 const _Rope_iterator<_CharT, _Alloc>& __y);
00397
00398 template<class _CharT, class _Alloc>
00399 ptrdiff_t
00400 operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
00401 const _Rope_iterator<_CharT, _Alloc>& __y);
00402
00403 template<class _CharT, class _Alloc>
00404 rope<_CharT, _Alloc>
00405 operator+(const rope<_CharT, _Alloc>& __left,
00406 const rope<_CharT, _Alloc>& __right);
00407
00408 template<class _CharT, class _Alloc>
00409 rope<_CharT, _Alloc>
00410 operator+(const rope<_CharT, _Alloc>& __left, const _CharT* __right);
00411
00412 template<class _CharT, class _Alloc>
00413 rope<_CharT, _Alloc>
00414 operator+(const rope<_CharT, _Alloc>& __left, _CharT __right);
00415
00416
00417
00418
00419
00420
00421 template<class _CharT, class _Alloc>
00422 struct _Rope_Concat_fn
00423 : public std::binary_function<rope<_CharT, _Alloc>, rope<_CharT, _Alloc>,
00424 rope<_CharT, _Alloc> >
00425 {
00426 rope<_CharT, _Alloc>
00427 operator()(const rope<_CharT, _Alloc>& __x,
00428 const rope<_CharT, _Alloc>& __y)
00429 { return __x + __y; }
00430 };
00431
00432 template <class _CharT, class _Alloc>
00433 inline rope<_CharT, _Alloc>
00434 identity_element(_Rope_Concat_fn<_CharT, _Alloc>)
00435 { return rope<_CharT, _Alloc>(); }
00436
00437
00438
00439
00440
00441 struct _Refcount_Base
00442 {
00443
00444 typedef size_t _RC_t;
00445
00446
00447 volatile _RC_t _M_ref_count;
00448
00449
00450 __gthread_mutex_t _M_ref_count_lock;
00451
00452 _Refcount_Base(_RC_t __n) : _M_ref_count(__n), _M_ref_count_lock()
00453 {
00454 #ifdef __GTHREAD_MUTEX_INIT
00455 __gthread_mutex_t __tmp = __GTHREAD_MUTEX_INIT;
00456 _M_ref_count_lock = __tmp;
00457 #elif defined(__GTHREAD_MUTEX_INIT_FUNCTION)
00458 __GTHREAD_MUTEX_INIT_FUNCTION (&_M_ref_count_lock);
00459 #else
00460 #error __GTHREAD_MUTEX_INIT or __GTHREAD_MUTEX_INIT_FUNCTION should be defined by gthr.h abstraction layer, report problem to libstdc++@gcc.gnu.org.
00461 #endif
00462 }
00463
00464 void
00465 _M_incr()
00466 {
00467 __gthread_mutex_lock(&_M_ref_count_lock);
00468 ++_M_ref_count;
00469 __gthread_mutex_unlock(&_M_ref_count_lock);
00470 }
00471
00472 _RC_t
00473 _M_decr()
00474 {
00475 __gthread_mutex_lock(&_M_ref_count_lock);
00476 volatile _RC_t __tmp = --_M_ref_count;
00477 __gthread_mutex_unlock(&_M_ref_count_lock);
00478 return __tmp;
00479 }
00480 };
00481
00482
00483
00484
00485
00486
00487
00488
00489
00490
00491
00492
00493
00494
00495
00496
00497
00498
00499
00500
00501
00502
00503
00504
00505
00506
00507 #define __ROPE_DEFINE_ALLOCS(__a) \
00508 __ROPE_DEFINE_ALLOC(_CharT,_Data) \
00509 typedef _Rope_RopeConcatenation<_CharT,__a> __C; \
00510 __ROPE_DEFINE_ALLOC(__C,_C) \
00511 typedef _Rope_RopeLeaf<_CharT,__a> __L; \
00512 __ROPE_DEFINE_ALLOC(__L,_L) \
00513 typedef _Rope_RopeFunction<_CharT,__a> __F; \
00514 __ROPE_DEFINE_ALLOC(__F,_F) \
00515 typedef _Rope_RopeSubstring<_CharT,__a> __S; \
00516 __ROPE_DEFINE_ALLOC(__S,_S)
00517
00518
00519
00520
00521
00522
00523
00524
00525 #define __STATIC_IF_SGI_ALLOC
00526
00527 template <class _CharT, class _Alloc>
00528 struct _Rope_rep_base
00529 : public _Alloc
00530 {
00531 typedef _Alloc allocator_type;
00532
00533 allocator_type
00534 get_allocator() const
00535 { return *static_cast<const _Alloc*>(this); }
00536
00537 _Rope_rep_base(size_t __size, const allocator_type&)
00538 : _M_size(__size) { }
00539
00540 size_t _M_size;
00541
00542 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
00543 typedef typename \
00544 _Alloc::template rebind<_Tp>::other __name##Alloc; \
00545 static _Tp* __name##_allocate(size_t __n) \
00546 { return __name##Alloc().allocate(__n); } \
00547 static void __name##_deallocate(_Tp *__p, size_t __n) \
00548 { __name##Alloc().deallocate(__p, __n); }
00549 __ROPE_DEFINE_ALLOCS(_Alloc)
00550 # undef __ROPE_DEFINE_ALLOC
00551 };
00552
00553 template<class _CharT, class _Alloc>
00554 struct _Rope_RopeRep
00555 : public _Rope_rep_base<_CharT, _Alloc>
00556 # ifndef __GC
00557 , _Refcount_Base
00558 # endif
00559 {
00560 public:
00561 __detail::_Tag _M_tag:8;
00562 bool _M_is_balanced:8;
00563 unsigned char _M_depth;
00564 __GC_CONST _CharT* _M_c_string;
00565 __gthread_mutex_t _M_c_string_lock;
00566
00567
00568
00569
00570
00571
00572 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
00573 allocator_type;
00574
00575 using _Rope_rep_base<_CharT, _Alloc>::get_allocator;
00576
00577 _Rope_RopeRep(__detail::_Tag __t, int __d, bool __b, size_t __size,
00578 allocator_type __a)
00579 : _Rope_rep_base<_CharT, _Alloc>(__size, __a),
00580 #ifndef __GC
00581 _Refcount_Base(1),
00582 #endif
00583 _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0)
00584 #ifdef __GTHREAD_MUTEX_INIT
00585 {
00586
00587 __gthread_mutex_t __tmp = __GTHREAD_MUTEX_INIT;
00588 _M_c_string_lock = __tmp;
00589 }
00590 #else
00591 { __GTHREAD_MUTEX_INIT_FUNCTION (&_M_c_string_lock); }
00592 #endif
00593 #ifdef __GC
00594 void
00595 _M_incr () { }
00596 #endif
00597 static void
00598 _S_free_string(__GC_CONST _CharT*, size_t __len,
00599 allocator_type __a);
00600 #define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a);
00601
00602
00603
00604
00605
00606
00607 #ifndef __GC
00608 void _M_free_c_string();
00609 void _M_free_tree();
00610
00611 void
00612 _M_unref_nonnil()
00613 {
00614 if (0 == _M_decr())
00615 _M_free_tree();
00616 }
00617
00618 void
00619 _M_ref_nonnil()
00620 { _M_incr(); }
00621
00622 static void
00623 _S_unref(_Rope_RopeRep* __t)
00624 {
00625 if (0 != __t)
00626 __t->_M_unref_nonnil();
00627 }
00628
00629 static void
00630 _S_ref(_Rope_RopeRep* __t)
00631 {
00632 if (0 != __t)
00633 __t->_M_incr();
00634 }
00635
00636 static void
00637 _S_free_if_unref(_Rope_RopeRep* __t)
00638 {
00639 if (0 != __t && 0 == __t->_M_ref_count)
00640 __t->_M_free_tree();
00641 }
00642 # else
00643 void _M_unref_nonnil() { }
00644 void _M_ref_nonnil() { }
00645 static void _S_unref(_Rope_RopeRep*) { }
00646 static void _S_ref(_Rope_RopeRep*) { }
00647 static void _S_free_if_unref(_Rope_RopeRep*) { }
00648 # endif
00649 protected:
00650 _Rope_RopeRep&
00651 operator=(const _Rope_RopeRep&);
00652
00653 _Rope_RopeRep(const _Rope_RopeRep&);
00654 };
00655
00656 template<class _CharT, class _Alloc>
00657 struct _Rope_RopeLeaf
00658 : public _Rope_RopeRep<_CharT, _Alloc>
00659 {
00660 public:
00661
00662
00663
00664
00665 enum { _S_alloc_granularity = 8 };
00666
00667 static size_t
00668 _S_rounded_up_size(size_t __n)
00669 {
00670 size_t __size_with_eos;
00671
00672 if (_S_is_basic_char_type((_CharT*)0))
00673 __size_with_eos = __n + 1;
00674 else
00675 __size_with_eos = __n;
00676 #ifdef __GC
00677 return __size_with_eos;
00678 #else
00679
00680 return ((__size_with_eos + size_t(_S_alloc_granularity) - 1)
00681 &~ (size_t(_S_alloc_granularity) - 1));
00682 #endif
00683 }
00684 __GC_CONST _CharT* _M_data;
00685
00686
00687
00688
00689 typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type
00690 allocator_type;
00691
00692 _Rope_RopeLeaf(__GC_CONST _CharT* __d, size_t __size,
00693 allocator_type __a)
00694 : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_leaf, 0, true,
00695 __size, __a), _M_data(__d)
00696 {
00697 if (_S_is_basic_char_type((_CharT *)0))
00698 {
00699
00700 this->_M_c_string = __d;
00701 }
00702 }
00703
00704
00705
00706 #ifndef __GC
00707 ~_Rope_RopeLeaf() throw()
00708 {
00709 if (_M_data != this->_M_c_string)
00710 this->_M_free_c_string();
00711
00712 __STL_FREE_STRING(_M_data, this->_M_size, this->get_allocator());
00713 }
00714 #endif
00715 protected:
00716 _Rope_RopeLeaf&
00717 operator=(const _Rope_RopeLeaf&);
00718
00719 _Rope_RopeLeaf(const _Rope_RopeLeaf&);
00720 };
00721
00722 template<class _CharT, class _Alloc>
00723 struct _Rope_RopeConcatenation
00724 : public _Rope_RopeRep<_CharT, _Alloc>
00725 {
00726 public:
00727 _Rope_RopeRep<_CharT, _Alloc>* _M_left;
00728 _Rope_RopeRep<_CharT, _Alloc>* _M_right;
00729
00730 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
00731 allocator_type;
00732
00733 _Rope_RopeConcatenation(_Rope_RopeRep<_CharT, _Alloc>* __l,
00734 _Rope_RopeRep<_CharT, _Alloc>* __r,
00735 allocator_type __a)
00736 : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_concat,
00737 std::max(__l->_M_depth,
00738 __r->_M_depth) + 1,
00739 false,
00740 __l->_M_size + __r->_M_size, __a),
00741 _M_left(__l), _M_right(__r)
00742 { }
00743 #ifndef __GC
00744 ~_Rope_RopeConcatenation() throw()
00745 {
00746 this->_M_free_c_string();
00747 _M_left->_M_unref_nonnil();
00748 _M_right->_M_unref_nonnil();
00749 }
00750 #endif
00751 protected:
00752 _Rope_RopeConcatenation&
00753 operator=(const _Rope_RopeConcatenation&);
00754
00755 _Rope_RopeConcatenation(const _Rope_RopeConcatenation&);
00756 };
00757
00758 template<class _CharT, class _Alloc>
00759 struct _Rope_RopeFunction
00760 : public _Rope_RopeRep<_CharT, _Alloc>
00761 {
00762 public:
00763 char_producer<_CharT>* _M_fn;
00764 #ifndef __GC
00765 bool _M_delete_when_done;
00766
00767
00768
00769 #else
00770
00771
00772
00773
00774
00775 static void
00776 _S_fn_finalization_proc(void * __tree, void *)
00777 { delete ((_Rope_RopeFunction *)__tree) -> _M_fn; }
00778 #endif
00779 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
00780 allocator_type;
00781
00782 _Rope_RopeFunction(char_producer<_CharT>* __f, size_t __size,
00783 bool __d, allocator_type __a)
00784 : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_function, 0, true, __size, __a)
00785 , _M_fn(__f)
00786 #ifndef __GC
00787 , _M_delete_when_done(__d)
00788 #endif
00789 {
00790 #ifdef __GC
00791 if (__d)
00792 {
00793 GC_REGISTER_FINALIZER(this, _Rope_RopeFunction::
00794 _S_fn_finalization_proc, 0, 0, 0);
00795 }
00796 #endif
00797 }
00798 #ifndef __GC
00799 ~_Rope_RopeFunction() throw()
00800 {
00801 this->_M_free_c_string();
00802 if (_M_delete_when_done)
00803 delete _M_fn;
00804 }
00805 # endif
00806 protected:
00807 _Rope_RopeFunction&
00808 operator=(const _Rope_RopeFunction&);
00809
00810 _Rope_RopeFunction(const _Rope_RopeFunction&);
00811 };
00812
00813
00814
00815
00816
00817
00818
00819 template<class _CharT, class _Alloc>
00820 struct _Rope_RopeSubstring
00821 : public _Rope_RopeFunction<_CharT, _Alloc>,
00822 public char_producer<_CharT>
00823 {
00824 public:
00825
00826 _Rope_RopeRep<_CharT,_Alloc>* _M_base;
00827 size_t _M_start;
00828
00829 virtual void
00830 operator()(size_t __start_pos, size_t __req_len,
00831 _CharT* __buffer)
00832 {
00833 switch(_M_base->_M_tag)
00834 {
00835 case __detail::_S_function:
00836 case __detail::_S_substringfn:
00837 {
00838 char_producer<_CharT>* __fn =
00839 ((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn;
00840 (*__fn)(__start_pos + _M_start, __req_len, __buffer);
00841 }
00842 break;
00843 case __detail::_S_leaf:
00844 {
00845 __GC_CONST _CharT* __s =
00846 ((_Rope_RopeLeaf<_CharT,_Alloc>*)_M_base)->_M_data;
00847 uninitialized_copy_n(__s + __start_pos + _M_start, __req_len,
00848 __buffer);
00849 }
00850 break;
00851 default:
00852 break;
00853 }
00854 }
00855
00856 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
00857 allocator_type;
00858
00859 _Rope_RopeSubstring(_Rope_RopeRep<_CharT, _Alloc>* __b, size_t __s,
00860 size_t __l, allocator_type __a)
00861 : _Rope_RopeFunction<_CharT, _Alloc>(this, __l, false, __a),
00862 char_producer<_CharT>(), _M_base(__b), _M_start(__s)
00863 {
00864 #ifndef __GC
00865 _M_base->_M_ref_nonnil();
00866 #endif
00867 this->_M_tag = __detail::_S_substringfn;
00868 }
00869 virtual ~_Rope_RopeSubstring() throw()
00870 {
00871 #ifndef __GC
00872 _M_base->_M_unref_nonnil();
00873
00874 #endif
00875 }
00876 };
00877
00878
00879
00880
00881
00882
00883
00884
00885
00886
00887 #ifndef __GC
00888 template<class _CharT, class _Alloc>
00889 struct _Rope_self_destruct_ptr
00890 {
00891 _Rope_RopeRep<_CharT, _Alloc>* _M_ptr;
00892
00893 ~_Rope_self_destruct_ptr()
00894 { _Rope_RopeRep<_CharT, _Alloc>::_S_unref(_M_ptr); }
00895 #ifdef __EXCEPTIONS
00896 _Rope_self_destruct_ptr() : _M_ptr(0) { };
00897 #else
00898 _Rope_self_destruct_ptr() { };
00899 #endif
00900 _Rope_self_destruct_ptr(_Rope_RopeRep<_CharT, _Alloc>* __p)
00901 : _M_ptr(__p) { }
00902
00903 _Rope_RopeRep<_CharT, _Alloc>&
00904 operator*()
00905 { return *_M_ptr; }
00906
00907 _Rope_RopeRep<_CharT, _Alloc>*
00908 operator->()
00909 { return _M_ptr; }
00910
00911 operator _Rope_RopeRep<_CharT, _Alloc>*()
00912 { return _M_ptr; }
00913
00914 _Rope_self_destruct_ptr&
00915 operator=(_Rope_RopeRep<_CharT, _Alloc>* __x)
00916 { _M_ptr = __x; return *this; }
00917 };
00918 #endif
00919
00920
00921
00922
00923
00924
00925 template<class _CharT, class _Alloc>
00926 class _Rope_char_ref_proxy
00927 {
00928 friend class rope<_CharT, _Alloc>;
00929 friend class _Rope_iterator<_CharT, _Alloc>;
00930 friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;
00931 #ifdef __GC
00932 typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
00933 #else
00934 typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
00935 #endif
00936 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
00937 typedef rope<_CharT, _Alloc> _My_rope;
00938 size_t _M_pos;
00939 _CharT _M_current;
00940 bool _M_current_valid;
00941 _My_rope* _M_root;
00942 public:
00943 _Rope_char_ref_proxy(_My_rope* __r, size_t __p)
00944 : _M_pos(__p), _M_current(), _M_current_valid(false), _M_root(__r) { }
00945
00946 _Rope_char_ref_proxy(const _Rope_char_ref_proxy& __x)
00947 : _M_pos(__x._M_pos), _M_current(__x._M_current),
00948 _M_current_valid(false), _M_root(__x._M_root) { }
00949
00950
00951
00952
00953
00954 _Rope_char_ref_proxy(_My_rope* __r, size_t __p, _CharT __c)
00955 : _M_pos(__p), _M_current(__c), _M_current_valid(true), _M_root(__r) { }
00956
00957 inline operator _CharT () const;
00958
00959 _Rope_char_ref_proxy&
00960 operator=(_CharT __c);
00961
00962 _Rope_char_ptr_proxy<_CharT, _Alloc> operator&() const;
00963
00964 _Rope_char_ref_proxy&
00965 operator=(const _Rope_char_ref_proxy& __c)
00966 { return operator=((_CharT)__c); }
00967 };
00968
00969 template<class _CharT, class __Alloc>
00970 inline void
00971 swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a,
00972 _Rope_char_ref_proxy <_CharT, __Alloc > __b)
00973 {
00974 _CharT __tmp = __a;
00975 __a = __b;
00976 __b = __tmp;
00977 }
00978
00979 template<class _CharT, class _Alloc>
00980 class _Rope_char_ptr_proxy
00981 {
00982
00983 friend class _Rope_char_ref_proxy<_CharT, _Alloc>;
00984 size_t _M_pos;
00985 rope<_CharT,_Alloc>* _M_root;
00986 public:
00987 _Rope_char_ptr_proxy(const _Rope_char_ref_proxy<_CharT,_Alloc>& __x)
00988 : _M_pos(__x._M_pos), _M_root(__x._M_root) { }
00989
00990 _Rope_char_ptr_proxy(const _Rope_char_ptr_proxy& __x)
00991 : _M_pos(__x._M_pos), _M_root(__x._M_root) { }
00992
00993 _Rope_char_ptr_proxy() { }
00994
00995 _Rope_char_ptr_proxy(_CharT* __x)
00996 : _M_root(0), _M_pos(0) { }
00997
00998 _Rope_char_ptr_proxy&
00999 operator=(const _Rope_char_ptr_proxy& __x)
01000 {
01001 _M_pos = __x._M_pos;
01002 _M_root = __x._M_root;
01003 return *this;
01004 }
01005
01006 template<class _CharT2, class _Alloc2>
01007 friend bool
01008 operator==(const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __x,
01009 const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __y);
01010
01011 _Rope_char_ref_proxy<_CharT, _Alloc> operator*() const
01012 { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root, _M_pos); }
01013 };
01014
01015
01016
01017
01018
01019
01020
01021
01022
01023
01024 template<class _CharT, class _Alloc>
01025 class _Rope_iterator_base
01026 : public iterator<std::random_access_iterator_tag, _CharT>
01027 {
01028 friend class rope<_CharT, _Alloc>;
01029 public:
01030 typedef _Alloc _allocator_type;
01031 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
01032
01033 protected:
01034 enum { _S_path_cache_len = 4 };
01035 enum { _S_iterator_buf_len = 15 };
01036 size_t _M_current_pos;
01037 _RopeRep* _M_root;
01038 size_t _M_leaf_pos;
01039 __GC_CONST _CharT* _M_buf_start;
01040
01041
01042 __GC_CONST _CharT* _M_buf_ptr;
01043
01044
01045 __GC_CONST _CharT* _M_buf_end;
01046
01047
01048
01049
01050
01051 const _RopeRep* _M_path_end[_S_path_cache_len];
01052 int _M_leaf_index;
01053
01054
01055 unsigned char _M_path_directions;
01056
01057
01058
01059
01060 _CharT _M_tmp_buf[_S_iterator_buf_len];
01061
01062
01063
01064
01065
01066
01067
01068 static void _S_setbuf(_Rope_iterator_base& __x);
01069
01070
01071 static void _S_setcache(_Rope_iterator_base& __x);
01072
01073
01074 static void _S_setcache_for_incr(_Rope_iterator_base& __x);
01075
01076
01077 _Rope_iterator_base() { }
01078
01079 _Rope_iterator_base(_RopeRep* __root, size_t __pos)
01080 : _M_current_pos(__pos), _M_root(__root), _M_buf_ptr(0) { }
01081
01082 void _M_incr(size_t __n);
01083 void _M_decr(size_t __n);
01084 public:
01085 size_t
01086 index() const
01087 { return _M_current_pos; }
01088
01089 _Rope_iterator_base(const _Rope_iterator_base& __x)
01090 {
01091 if (0 != __x._M_buf_ptr)
01092 *this = __x;
01093 else
01094 {
01095 _M_current_pos = __x._M_current_pos;
01096 _M_root = __x._M_root;
01097 _M_buf_ptr = 0;
01098 }
01099 }
01100 };
01101
01102 template<class _CharT, class _Alloc>
01103 class _Rope_iterator;
01104
01105 template<class _CharT, class _Alloc>
01106 class _Rope_const_iterator
01107 : public _Rope_iterator_base<_CharT, _Alloc>
01108 {
01109 friend class rope<_CharT, _Alloc>;
01110 protected:
01111 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
01112
01113 _Rope_const_iterator(const _RopeRep* __root, size_t __pos)
01114 : _Rope_iterator_base<_CharT, _Alloc>(const_cast<_RopeRep*>(__root),
01115 __pos)
01116
01117 { }
01118 public:
01119 typedef _CharT reference;
01120
01121
01122 typedef const _CharT* pointer;
01123
01124 public:
01125 _Rope_const_iterator() { };
01126
01127 _Rope_const_iterator(const _Rope_const_iterator& __x)
01128 : _Rope_iterator_base<_CharT,_Alloc>(__x) { }
01129
01130 _Rope_const_iterator(const _Rope_iterator<_CharT,_Alloc>& __x);
01131
01132 _Rope_const_iterator(const rope<_CharT, _Alloc>& __r, size_t __pos)
01133 : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos) { }
01134
01135 _Rope_const_iterator&
01136 operator=(const _Rope_const_iterator& __x)
01137 {
01138 if (0 != __x._M_buf_ptr)
01139 *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x;
01140 else
01141 {
01142 this->_M_current_pos = __x._M_current_pos;
01143 this->_M_root = __x._M_root;
01144 this->_M_buf_ptr = 0;
01145 }
01146 return(*this);
01147 }
01148
01149 reference
01150 operator*()
01151 {
01152 if (0 == this->_M_buf_ptr)
01153 _S_setcache(*this);
01154 return *this->_M_buf_ptr;
01155 }
01156
01157
01158
01159 reference
01160 operator*() const
01161 {
01162 return *const_cast<_Rope_const_iterator&>(*this);
01163 }
01164
01165 _Rope_const_iterator&
01166 operator++()
01167 {
01168 __GC_CONST _CharT* __next;
01169 if (0 != this->_M_buf_ptr
01170 && (__next = this->_M_buf_ptr + 1) < this->_M_buf_end)
01171 {
01172 this->_M_buf_ptr = __next;
01173 ++this->_M_current_pos;
01174 }
01175 else
01176 this->_M_incr(1);
01177 return *this;
01178 }
01179
01180 _Rope_const_iterator&
01181 operator+=(ptrdiff_t __n)
01182 {
01183 if (__n >= 0)
01184 this->_M_incr(__n);
01185 else
01186 this->_M_decr(-__n);
01187 return *this;
01188 }
01189
01190 _Rope_const_iterator&
01191 operator--()
01192 {
01193 this->_M_decr(1);
01194 return *this;
01195 }
01196
01197 _Rope_const_iterator&
01198 operator-=(ptrdiff_t __n)
01199 {
01200 if (__n >= 0)
01201 this->_M_decr(__n);
01202 else
01203 this->_M_incr(-__n);
01204 return *this;
01205 }
01206
01207 _Rope_const_iterator
01208 operator++(int)
01209 {
01210 size_t __old_pos = this->_M_current_pos;
01211 this->_M_incr(1);
01212 return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
01213
01214
01215
01216 }
01217
01218 _Rope_const_iterator
01219 operator--(int)
01220 {
01221 size_t __old_pos = this->_M_current_pos;
01222 this->_M_decr(1);
01223 return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
01224 }
01225
01226 template<class _CharT2, class _Alloc2>
01227 friend _Rope_const_iterator<_CharT2, _Alloc2>
01228 operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
01229 ptrdiff_t __n);
01230
01231 template<class _CharT2, class _Alloc2>
01232 friend _Rope_const_iterator<_CharT2, _Alloc2>
01233 operator+(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
01234 ptrdiff_t __n);
01235
01236 template<class _CharT2, class _Alloc2>
01237 friend _Rope_const_iterator<_CharT2, _Alloc2>
01238 operator+(ptrdiff_t __n,
01239 const _Rope_const_iterator<_CharT2, _Alloc2>& __x);
01240
01241 reference
01242 operator[](size_t __n)
01243 { return rope<_CharT, _Alloc>::_S_fetch(this->_M_root,
01244 this->_M_current_pos + __n); }
01245
01246 template<class _CharT2, class _Alloc2>
01247 friend bool
01248 operator==(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
01249 const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
01250
01251 template<class _CharT2, class _Alloc2>
01252 friend bool
01253 operator<(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
01254 const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
01255
01256 template<class _CharT2, class _Alloc2>
01257 friend ptrdiff_t
01258 operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
01259 const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
01260 };
01261
01262 template<class _CharT, class _Alloc>
01263 class _Rope_iterator
01264 : public _Rope_iterator_base<_CharT, _Alloc>
01265 {
01266 friend class rope<_CharT, _Alloc>;
01267 protected:
01268 typedef typename _Rope_iterator_base<_CharT, _Alloc>::_RopeRep _RopeRep;
01269 rope<_CharT, _Alloc>* _M_root_rope;
01270
01271
01272
01273
01274
01275
01276
01277 _Rope_iterator(rope<_CharT, _Alloc>* __r, size_t __pos)
01278 : _Rope_iterator_base<_CharT, _Alloc>(__r->_M_tree_ptr, __pos),
01279 _M_root_rope(__r)
01280 { _RopeRep::_S_ref(this->_M_root);
01281 if (!(__r -> empty()))
01282 _S_setcache(*this);
01283 }
01284
01285 void _M_check();
01286 public:
01287 typedef _Rope_char_ref_proxy<_CharT, _Alloc> reference;
01288 typedef _Rope_char_ref_proxy<_CharT, _Alloc>* pointer;
01289
01290 rope<_CharT, _Alloc>&
01291 container()
01292 { return *_M_root_rope; }
01293
01294 _Rope_iterator()
01295 {
01296 this->_M_root = 0;
01297 };
01298
01299 _Rope_iterator(const _Rope_iterator& __x)
01300 : _Rope_iterator_base<_CharT, _Alloc>(__x)
01301 {
01302 _M_root_rope = __x._M_root_rope;
01303 _RopeRep::_S_ref(this->_M_root);
01304 }
01305
01306 _Rope_iterator(rope<_CharT, _Alloc>& __r, size_t __pos);
01307
01308 ~_Rope_iterator()
01309 { _RopeRep::_S_unref(this->_M_root); }
01310
01311 _Rope_iterator&
01312 operator=(const _Rope_iterator& __x)
01313 {
01314 _RopeRep* __old = this->_M_root;
01315
01316 _RopeRep::_S_ref(__x._M_root);
01317 if (0 != __x._M_buf_ptr)
01318 {
01319 _M_root_rope = __x._M_root_rope;
01320 *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x;
01321 }
01322 else
01323 {
01324 this->_M_current_pos = __x._M_current_pos;
01325 this->_M_root = __x._M_root;
01326 _M_root_rope = __x._M_root_rope;
01327 this->_M_buf_ptr = 0;
01328 }
01329 _RopeRep::_S_unref(__old);
01330 return(*this);
01331 }
01332
01333 reference
01334 operator*()
01335 {
01336 _M_check();
01337 if (0 == this->_M_buf_ptr)
01338 return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
01339 this->_M_current_pos);
01340 else
01341 return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
01342 this->_M_current_pos,
01343 *this->_M_buf_ptr);
01344 }
01345
01346
01347 reference
01348 operator*() const
01349 {
01350 return *const_cast<_Rope_iterator&>(*this);
01351 }
01352
01353 _Rope_iterator&
01354 operator++()
01355 {
01356 this->_M_incr(1);
01357 return *this;
01358 }
01359
01360 _Rope_iterator&
01361 operator+=(ptrdiff_t __n)
01362 {
01363 if (__n >= 0)
01364 this->_M_incr(__n);
01365 else
01366 this->_M_decr(-__n);
01367 return *this;
01368 }
01369
01370 _Rope_iterator&
01371 operator--()
01372 {
01373 this->_M_decr(1);
01374 return *this;
01375 }
01376
01377 _Rope_iterator&
01378 operator-=(ptrdiff_t __n)
01379 {
01380 if (__n >= 0)
01381 this->_M_decr(__n);
01382 else
01383 this->_M_incr(-__n);
01384 return *this;
01385 }
01386
01387 _Rope_iterator
01388 operator++(int)
01389 {
01390 size_t __old_pos = this->_M_current_pos;
01391 this->_M_incr(1);
01392 return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
01393 }
01394
01395 _Rope_iterator
01396 operator--(int)
01397 {
01398 size_t __old_pos = this->_M_current_pos;
01399 this->_M_decr(1);
01400 return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
01401 }
01402
01403 reference
01404 operator[](ptrdiff_t __n)
01405 { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
01406 this->_M_current_pos
01407 + __n); }
01408
01409 template<class _CharT2, class _Alloc2>
01410 friend bool
01411 operator==(const _Rope_iterator<_CharT2, _Alloc2>& __x,
01412 const _Rope_iterator<_CharT2, _Alloc2>& __y);
01413
01414 template<class _CharT2, class _Alloc2>
01415 friend bool
01416 operator<(const _Rope_iterator<_CharT2, _Alloc2>& __x,
01417 const _Rope_iterator<_CharT2, _Alloc2>& __y);
01418
01419 template<class _CharT2, class _Alloc2>
01420 friend ptrdiff_t
01421 operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x,
01422 const _Rope_iterator<_CharT2, _Alloc2>& __y);
01423
01424 template<class _CharT2, class _Alloc2>
01425 friend _Rope_iterator<_CharT2, _Alloc2>
01426 operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);
01427
01428 template<class _CharT2, class _Alloc2>
01429 friend _Rope_iterator<_CharT2, _Alloc2>
01430 operator+(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);
01431
01432 template<class _CharT2, class _Alloc2>
01433 friend _Rope_iterator<_CharT2, _Alloc2>
01434 operator+(ptrdiff_t __n, const _Rope_iterator<_CharT2, _Alloc2>& __x);
01435 };
01436
01437
01438 template <class _CharT, class _Alloc>
01439 struct _Rope_base
01440 : public _Alloc
01441 {
01442 typedef _Alloc allocator_type;
01443
01444 allocator_type
01445 get_allocator() const
01446 { return *static_cast<const _Alloc*>(this); }
01447
01448 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
01449
01450
01451 _Rope_base(_RopeRep* __t, const allocator_type&)
01452 : _M_tree_ptr(__t) { }
01453
01454 _Rope_base(const allocator_type&) { }
01455
01456
01457 _RopeRep *_M_tree_ptr;
01458
01459 #define __ROPE_DEFINE_ALLOC(_Tp, __name) \
01460 typedef typename \
01461 _Alloc::template rebind<_Tp>::other __name##Alloc; \
01462 static _Tp* __name##_allocate(size_t __n) \
01463 { return __name##Alloc().allocate(__n); } \
01464 static void __name##_deallocate(_Tp *__p, size_t __n) \
01465 { __name##Alloc().deallocate(__p, __n); }
01466 __ROPE_DEFINE_ALLOCS(_Alloc)
01467 #undef __ROPE_DEFINE_ALLOC
01468
01469 protected:
01470 _Rope_base&
01471 operator=(const _Rope_base&);
01472
01473 _Rope_base(const _Rope_base&);
01474 };
01475
01476
01477
01478
01479
01480
01481 template <class _CharT, class _Alloc>
01482 class rope : public _Rope_base<_CharT, _Alloc>
01483 {
01484 public:
01485 typedef _CharT value_type;
01486 typedef ptrdiff_t difference_type;
01487 typedef size_t size_type;
01488 typedef _CharT const_reference;
01489 typedef const _CharT* const_pointer;
01490 typedef _Rope_iterator<_CharT, _Alloc> iterator;
01491 typedef _Rope_const_iterator<_CharT, _Alloc> const_iterator;
01492 typedef _Rope_char_ref_proxy<_CharT, _Alloc> reference;
01493 typedef _Rope_char_ptr_proxy<_CharT, _Alloc> pointer;
01494
01495 friend class _Rope_iterator<_CharT, _Alloc>;
01496 friend class _Rope_const_iterator<_CharT, _Alloc>;
01497 friend struct _Rope_RopeRep<_CharT, _Alloc>;
01498 friend class _Rope_iterator_base<_CharT, _Alloc>;
01499 friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;
01500 friend class _Rope_char_ref_proxy<_CharT, _Alloc>;
01501 friend struct _Rope_RopeSubstring<_CharT, _Alloc>;
01502
01503 protected:
01504 typedef _Rope_base<_CharT, _Alloc> _Base;
01505 typedef typename _Base::allocator_type allocator_type;
01506 using _Base::_M_tree_ptr;
01507 using _Base::get_allocator;
01508 typedef __GC_CONST _CharT* _Cstrptr;
01509
01510 static _CharT _S_empty_c_str[1];
01511
01512 static bool
01513 _S_is0(_CharT __c)
01514 { return __c == _S_eos((_CharT*)0); }
01515
01516 enum { _S_copy_max = 23 };
01517
01518
01519
01520 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
01521 typedef _Rope_RopeConcatenation<_CharT, _Alloc> _RopeConcatenation;
01522 typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf;
01523 typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction;
01524 typedef _Rope_RopeSubstring<_CharT, _Alloc> _RopeSubstring;
01525
01526
01527 static _CharT _S_fetch(_RopeRep* __r, size_type __pos);
01528
01529 #ifndef __GC
01530
01531
01532
01533
01534
01535
01536 static _CharT* _S_fetch_ptr(_RopeRep* __r, size_type __pos);
01537 #endif
01538
01539 static bool
01540 _S_apply_to_pieces(
01541 _Rope_char_consumer<_CharT>& __c,
01542 const _RopeRep* __r,
01543 size_t __begin, size_t __end);
01544
01545
01546 #ifndef __GC
01547 static void
01548 _S_unref(_RopeRep* __t)
01549 { _RopeRep::_S_unref(__t); }
01550
01551 static void
01552 _S_ref(_RopeRep* __t)
01553 { _RopeRep::_S_ref(__t); }
01554
01555 #else
01556 static void _S_unref(_RopeRep*) { }
01557 static void _S_ref(_RopeRep*) { }
01558 #endif
01559
01560 #ifdef __GC
01561 typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
01562 #else
01563 typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
01564 #endif
01565
01566
01567 static _RopeRep* _S_substring(_RopeRep* __base,
01568 size_t __start, size_t __endp1);
01569
01570 static _RopeRep* _S_concat_char_iter(_RopeRep* __r,
01571 const _CharT* __iter, size_t __slen);
01572
01573
01574
01575 static _RopeRep* _S_destr_concat_char_iter(_RopeRep* __r,
01576 const _CharT* __iter,
01577 size_t __slen)
01578
01579
01580
01581 #ifdef __GC
01582
01583 { return _S_concat_char_iter(__r, __iter, __slen); }
01584 #else
01585 ;
01586 #endif
01587
01588 static _RopeRep* _S_concat(_RopeRep* __left, _RopeRep* __right);
01589
01590
01591
01592 public:
01593 void
01594 apply_to_pieces(size_t __begin, size_t __end,
01595 _Rope_char_consumer<_CharT>& __c) const
01596 { _S_apply_to_pieces(__c, this->_M_tree_ptr, __begin, __end); }
01597
01598 protected:
01599
01600 static size_t
01601 _S_rounded_up_size(size_t __n)
01602 { return _RopeLeaf::_S_rounded_up_size(__n); }
01603
01604 static size_t
01605 _S_allocated_capacity(size_t __n)
01606 {
01607 if (_S_is_basic_char_type((_CharT*)0))
01608 return _S_rounded_up_size(__n) - 1;
01609 else
01610 return _S_rounded_up_size(__n);
01611
01612 }
01613
01614
01615
01616 static _RopeLeaf*
01617 _S_new_RopeLeaf(__GC_CONST _CharT *__s,
01618 size_t __size, allocator_type __a)
01619 {
01620 _RopeLeaf* __space = typename _Base::_LAlloc(__a).allocate(1);
01621 return new(__space) _RopeLeaf(__s, __size, __a);
01622 }
01623
01624 static _RopeConcatenation*
01625 _S_new_RopeConcatenation(_RopeRep* __left, _RopeRep* __right,
01626 allocator_type __a)
01627 {
01628 _RopeConcatenation* __space = typename _Base::_CAlloc(__a).allocate(1);
01629 return new(__space) _RopeConcatenation(__left, __right, __a);
01630 }
01631
01632 static _RopeFunction*
01633 _S_new_RopeFunction(char_producer<_CharT>* __f,
01634 size_t __size, bool __d, allocator_type __a)
01635 {
01636 _RopeFunction* __space = typename _Base::_FAlloc(__a).allocate(1);
01637 return new(__space) _RopeFunction(__f, __size, __d, __a);
01638 }
01639
01640 static _RopeSubstring*
01641 _S_new_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s,
01642 size_t __l, allocator_type __a)
01643 {
01644 _RopeSubstring* __space = typename _Base::_SAlloc(__a).allocate(1);
01645 return new(__space) _RopeSubstring(__b, __s, __l, __a);
01646 }
01647
01648 static _RopeLeaf*
01649 _S_RopeLeaf_from_unowned_char_ptr(const _CharT *__s,
01650 size_t __size, allocator_type __a)
01651 #define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) \
01652 _S_RopeLeaf_from_unowned_char_ptr(__s, __size, __a)
01653 {
01654 if (0 == __size)
01655 return 0;
01656 _CharT* __buf = __a.allocate(_S_rounded_up_size(__size));
01657
01658 __uninitialized_copy_n_a(__s, __size, __buf, __a);
01659 _S_cond_store_eos(__buf[__size]);
01660 try
01661 { return _S_new_RopeLeaf(__buf, __size, __a); }
01662 catch(...)
01663 {
01664 _RopeRep::__STL_FREE_STRING(__buf, __size, __a);
01665 __throw_exception_again;
01666 }
01667 }
01668
01669
01670
01671
01672
01673
01674
01675 static _RopeRep*
01676 _S_tree_concat(_RopeRep* __left, _RopeRep* __right);
01677
01678
01679 static _RopeLeaf*
01680 _S_leaf_concat_char_iter(_RopeLeaf* __r,
01681 const _CharT* __iter, size_t __slen);
01682
01683
01684
01685 #ifndef __GC
01686 static _RopeLeaf*
01687 _S_destr_leaf_concat_char_iter(_RopeLeaf* __r,
01688 const _CharT* __iter, size_t __slen);
01689
01690 #endif
01691
01692 private:
01693
01694 static size_t _S_char_ptr_len(const _CharT* __s);
01695
01696
01697 rope(_RopeRep* __t, const allocator_type& __a = allocator_type())
01698 : _Base(__t, __a) { }
01699
01700
01701
01702
01703
01704 static _CharT* _S_flatten(_RopeRep* __r, _CharT* __buffer);
01705
01706
01707
01708 static _CharT* _S_flatten(_RopeRep* __r,
01709 size_t __start, size_t __len,
01710 _CharT* __buffer);
01711
01712 static const unsigned long
01713 _S_min_len[__detail::_S_max_rope_depth + 1];
01714
01715 static bool
01716 _S_is_balanced(_RopeRep* __r)
01717 { return (__r->_M_size >= _S_min_len[__r->_M_depth]); }
01718
01719 static bool
01720 _S_is_almost_balanced(_RopeRep* __r)
01721 { return (__r->_M_depth == 0
01722 || __r->_M_size >= _S_min_len[__r->_M_depth - 1]); }
01723
01724 static bool
01725 _S_is_roughly_balanced(_RopeRep* __r)
01726 { return (__r->_M_depth <= 1
01727 || __r->_M_size >= _S_min_len[__r->_M_depth - 2]); }
01728
01729
01730 static _RopeRep*
01731 _S_concat_and_set_balanced(_RopeRep* __left, _RopeRep* __right)
01732 {
01733 _RopeRep* __result = _S_concat(__left, __right);
01734 if (_S_is_balanced(__result))
01735 __result->_M_is_balanced = true;
01736 return __result;
01737 }
01738
01739
01740
01741
01742
01743
01744 static _RopeRep* _S_balance(_RopeRep* __r);
01745
01746
01747
01748 static void _S_add_to_forest(_RopeRep*__r, _RopeRep** __forest);
01749
01750
01751 static void _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest);
01752
01753
01754 static void _S_dump(_RopeRep* __r, int __indent = 0);
01755
01756
01757 static int _S_compare(const _RopeRep* __x, const _RopeRep* __y);
01758
01759 public:
01760 bool
01761 empty() const
01762 { return 0 == this->_M_tree_ptr; }
01763
01764
01765
01766
01767 int
01768 compare(const rope& __y) const
01769 { return _S_compare(this->_M_tree_ptr, __y._M_tree_ptr); }
01770
01771 rope(const _CharT* __s, const allocator_type& __a = allocator_type())
01772 : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, _S_char_ptr_len(__s),
01773 __a), __a)
01774 { }
01775
01776 rope(const _CharT* __s, size_t __len,
01777 const allocator_type& __a = allocator_type())
01778 : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __len, __a), __a)
01779 { }
01780
01781
01782
01783
01784 rope(const _CharT *__s, const _CharT *__e,
01785 const allocator_type& __a = allocator_type())
01786 : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __e - __s, __a), __a)
01787 { }
01788
01789 rope(const const_iterator& __s, const const_iterator& __e,
01790 const allocator_type& __a = allocator_type())
01791 : _Base(_S_substring(__s._M_root, __s._M_current_pos,
01792 __e._M_current_pos), __a)
01793 { }
01794
01795 rope(const iterator& __s, const iterator& __e,
01796 const allocator_type& __a = allocator_type())
01797 : _Base(_S_substring(__s._M_root, __s._M_current_pos,
01798 __e._M_current_pos), __a)
01799 { }
01800
01801 rope(_CharT __c, const allocator_type& __a = allocator_type())
01802 : _Base(__a)
01803 {
01804 _CharT* __buf = this->_Data_allocate(_S_rounded_up_size(1));
01805
01806 get_allocator().construct(__buf, __c);
01807 try
01808 { this->_M_tree_ptr = _S_new_RopeLeaf(__buf, 1, __a); }
01809 catch(...)
01810 {
01811 _RopeRep::__STL_FREE_STRING(__buf, 1, __a);
01812 __throw_exception_again;
01813 }
01814 }
01815
01816 rope(size_t __n, _CharT __c,
01817 const allocator_type& __a = allocator_type());
01818
01819 rope(const allocator_type& __a = allocator_type())
01820 : _Base(0, __a) { }
01821
01822
01823 rope(char_producer<_CharT> *__fn, size_t __len, bool __delete_fn,
01824 const allocator_type& __a = allocator_type())
01825 : _Base(__a)
01826 {
01827 this->_M_tree_ptr = (0 == __len) ?
01828 0 : _S_new_RopeFunction(__fn, __len, __delete_fn, __a);
01829 }
01830
01831 rope(const rope& __x, const allocator_type& __a = allocator_type())
01832 : _Base(__x._M_tree_ptr, __a)
01833 { _S_ref(this->_M_tree_ptr); }
01834
01835 ~rope() throw()
01836 { _S_unref(this->_M_tree_ptr); }
01837
01838 rope&
01839 operator=(const rope& __x)
01840 {
01841 _RopeRep* __old = this->_M_tree_ptr;
01842 this->_M_tree_ptr = __x._M_tree_ptr;
01843 _S_ref(this->_M_tree_ptr);
01844 _S_unref(__old);
01845 return *this;
01846 }
01847
01848 void
01849 clear()
01850 {
01851 _S_unref(this->_M_tree_ptr);
01852 this->_M_tree_ptr = 0;
01853 }
01854
01855 void
01856 push_back(_CharT __x)
01857 {
01858 _RopeRep* __old = this->_M_tree_ptr;
01859 this->_M_tree_ptr
01860 = _S_destr_concat_char_iter(this->_M_tree_ptr, &__x, 1);
01861 _S_unref(__old);
01862 }
01863
01864 void
01865 pop_back()
01866 {
01867 _RopeRep* __old = this->_M_tree_ptr;
01868 this->_M_tree_ptr = _S_substring(this->_M_tree_ptr,
01869 0, this->_M_tree_ptr->_M_size - 1);
01870 _S_unref(__old);
01871 }
01872
01873 _CharT
01874 back() const
01875 { return _S_fetch(this->_M_tree_ptr, this->_M_tree_ptr->_M_size - 1); }
01876
01877 void
01878 push_front(_CharT __x)
01879 {
01880 _RopeRep* __old = this->_M_tree_ptr;
01881 _RopeRep* __left =
01882 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1, this->get_allocator());
01883 try
01884 {
01885 this->_M_tree_ptr = _S_concat(__left, this->_M_tree_ptr);
01886 _S_unref(__old);
01887 _S_unref(__left);
01888 }
01889 catch(...)
01890 {
01891 _S_unref(__left);
01892 __throw_exception_again;
01893 }
01894 }
01895
01896 void
01897 pop_front()
01898 {
01899 _RopeRep* __old = this->_M_tree_ptr;
01900 this->_M_tree_ptr
01901 = _S_substring(this->_M_tree_ptr, 1, this->_M_tree_ptr->_M_size);
01902 _S_unref(__old);
01903 }
01904
01905 _CharT
01906 front() const
01907 { return _S_fetch(this->_M_tree_ptr, 0); }
01908
01909 void
01910 balance()
01911 {
01912 _RopeRep* __old = this->_M_tree_ptr;
01913 this->_M_tree_ptr = _S_balance(this->_M_tree_ptr);
01914 _S_unref(__old);
01915 }
01916
01917 void
01918 copy(_CharT* __buffer) const
01919 {
01920 _Destroy(__buffer, __buffer + size(), get_allocator());
01921 _S_flatten(this->_M_tree_ptr, __buffer);
01922 }
01923
01924
01925
01926
01927
01928
01929 size_type
01930 copy(size_type __pos, size_type __n, _CharT* __buffer) const
01931 {
01932 size_t __size = size();
01933 size_t __len = (__pos + __n > __size? __size - __pos : __n);
01934
01935 _Destroy(__buffer, __buffer + __len, get_allocator());
01936 _S_flatten(this->_M_tree_ptr, __pos, __len, __buffer);
01937 return __len;
01938 }
01939
01940
01941
01942 void
01943 dump()
01944 { _S_dump(this->_M_tree_ptr); }
01945
01946
01947
01948 const _CharT* c_str() const;
01949
01950
01951
01952 const _CharT* replace_with_c_str();
01953
01954
01955
01956
01957 void
01958 delete_c_str ()
01959 {
01960 if (0 == this->_M_tree_ptr)
01961 return;
01962 if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag &&
01963 ((_RopeLeaf*)this->_M_tree_ptr)->_M_data ==
01964 this->_M_tree_ptr->_M_c_string)
01965 {
01966
01967 return;
01968 }
01969 #ifndef __GC
01970 this->_M_tree_ptr->_M_free_c_string();
01971 #endif
01972 this->_M_tree_ptr->_M_c_string = 0;
01973 }
01974
01975 _CharT
01976 operator[] (size_type __pos) const
01977 { return _S_fetch(this->_M_tree_ptr, __pos); }
01978
01979 _CharT
01980 at(size_type __pos) const
01981 {
01982
01983 return (*this)[__pos];
01984 }
01985
01986 const_iterator
01987 begin() const
01988 { return(const_iterator(this->_M_tree_ptr, 0)); }
01989
01990
01991 const_iterator
01992 const_begin() const
01993 { return(const_iterator(this->_M_tree_ptr, 0)); }
01994
01995 const_iterator
01996 end() const
01997 { return(const_iterator(this->_M_tree_ptr, size())); }
01998
01999 const_iterator
02000 const_end() const
02001 { return(const_iterator(this->_M_tree_ptr, size())); }
02002
02003 size_type
02004 size() const
02005 { return(0 == this->_M_tree_ptr? 0 : this->_M_tree_ptr->_M_size); }
02006
02007 size_type
02008 length() const
02009 { return size(); }
02010
02011 size_type
02012 max_size() const
02013 {
02014 return _S_min_len[int(__detail::_S_max_rope_depth) - 1] - 1;
02015
02016
02017
02018 }
02019
02020 typedef reverse_iterator<const_iterator> const_reverse_iterator;
02021
02022 const_reverse_iterator
02023 rbegin() const
02024 { return const_reverse_iterator(end()); }
02025
02026 const_reverse_iterator
02027 const_rbegin() const
02028 { return const_reverse_iterator(end()); }
02029
02030 const_reverse_iterator
02031 rend() const
02032 { return const_reverse_iterator(begin()); }
02033
02034 const_reverse_iterator
02035 const_rend() const
02036 { return const_reverse_iterator(begin()); }
02037
02038 template<class _CharT2, class _Alloc2>
02039 friend rope<_CharT2, _Alloc2>
02040 operator+(const rope<_CharT2, _Alloc2>& __left,
02041 const rope<_CharT2, _Alloc2>& __right);
02042
02043 template<class _CharT2, class _Alloc2>
02044 friend rope<_CharT2, _Alloc2>
02045 operator+(const rope<_CharT2, _Alloc2>& __left, const _CharT2* __right);
02046
02047 template<class _CharT2, class _Alloc2>
02048 friend rope<_CharT2, _Alloc2>
02049 operator+(const rope<_CharT2, _Alloc2>& __left, _CharT2 __right);
02050
02051
02052
02053
02054
02055
02056
02057 rope&
02058 append(const _CharT* __iter, size_t __n)
02059 {
02060 _RopeRep* __result =
02061 _S_destr_concat_char_iter(this->_M_tree_ptr, __iter, __n);
02062 _S_unref(this->_M_tree_ptr);
02063 this->_M_tree_ptr = __result;
02064 return *this;
02065 }
02066
02067 rope&
02068 append(const _CharT* __c_string)
02069 {
02070 size_t __len = _S_char_ptr_len(__c_string);
02071 append(__c_string, __len);
02072 return(*this);
02073 }
02074
02075 rope&
02076 append(const _CharT* __s, const _CharT* __e)
02077 {
02078 _RopeRep* __result =
02079 _S_destr_concat_char_iter(this->_M_tree_ptr, __s, __e - __s);
02080 _S_unref(this->_M_tree_ptr);
02081 this->_M_tree_ptr = __result;
02082 return *this;
02083 }
02084
02085 rope&
02086 append(const_iterator __s, const_iterator __e)
02087 {
02088 _Self_destruct_ptr __appendee(_S_substring(__s._M_root,
02089 __s._M_current_pos,
02090 __e._M_current_pos));
02091 _RopeRep* __result = _S_concat(this->_M_tree_ptr,
02092 (_RopeRep*)__appendee);
02093 _S_unref(this->_M_tree_ptr);
02094 this->_M_tree_ptr = __result;
02095 return *this;
02096 }
02097
02098 rope&
02099 append(_CharT __c)
02100 {
02101 _RopeRep* __result =
02102 _S_destr_concat_char_iter(this->_M_tree_ptr, &__c, 1);
02103 _S_unref(this->_M_tree_ptr);
02104 this->_M_tree_ptr = __result;
02105 return *this;
02106 }
02107
02108 rope&
02109 append()
02110 { return append(_CharT()); }
02111
02112 rope&
02113 append(const rope& __y)
02114 {
02115 _RopeRep* __result = _S_concat(this->_M_tree_ptr, __y._M_tree_ptr);
02116 _S_unref(this->_M_tree_ptr);
02117 this->_M_tree_ptr = __result;
02118 return *this;
02119 }
02120
02121 rope&
02122 append(size_t __n, _CharT __c)
02123 {
02124 rope<_CharT,_Alloc> __last(__n, __c);
02125 return append(__last);
02126 }
02127
02128 void
02129 swap(rope& __b)
02130 {
02131 _RopeRep* __tmp = this->_M_tree_ptr;
02132 this->_M_tree_ptr = __b._M_tree_ptr;
02133 __b._M_tree_ptr = __tmp;
02134 }
02135
02136 protected:
02137
02138 static _RopeRep*
02139 replace(_RopeRep* __old, size_t __pos1,
02140 size_t __pos2, _RopeRep* __r)
02141 {
02142 if (0 == __old)
02143 {
02144 _S_ref(__r);
02145 return __r;
02146 }
02147 _Self_destruct_ptr __left(_S_substring(__old, 0, __pos1));
02148 _Self_destruct_ptr __right(_S_substring(__old, __pos2, __old->_M_size));
02149 _RopeRep* __result;
02150
02151 if (0 == __r)
02152 __result = _S_concat(__left, __right);
02153 else
02154 {
02155 _Self_destruct_ptr __left_result(_S_concat(__left, __r));
02156 __result = _S_concat(__left_result, __right);
02157 }
02158 return __result;
02159 }
02160
02161 public:
02162 void
02163 insert(size_t __p, const rope& __r)
02164 {
02165 _RopeRep* __result =
02166 replace(this->_M_tree_ptr, __p, __p, __r._M_tree_ptr);
02167 _S_unref(this->_M_tree_ptr);
02168 this->_M_tree_ptr = __result;
02169 }
02170
02171 void
02172 insert(size_t __p, size_t __n, _CharT __c)
02173 {
02174 rope<_CharT,_Alloc> __r(__n,__c);
02175 insert(__p, __r);
02176 }
02177
02178 void
02179 insert(size_t __p, const _CharT* __i, size_t __n)
02180 {
02181 _Self_destruct_ptr __left(_S_substring(this->_M_tree_ptr, 0, __p));
02182 _Self_destruct_ptr __right(_S_substring(this->_M_tree_ptr,
02183 __p, size()));
02184 _Self_destruct_ptr __left_result(_S_concat_char_iter(__left, __i, __n));
02185
02186
02187
02188 _RopeRep* __result = _S_concat(__left_result, __right);
02189 _S_unref(this->_M_tree_ptr);
02190 this->_M_tree_ptr = __result;
02191 }
02192
02193 void
02194 insert(size_t __p, const _CharT* __c_string)
02195 { insert(__p, __c_string, _S_char_ptr_len(__c_string)); }
02196
02197 void
02198 insert(size_t __p, _CharT __c)
02199 { insert(__p, &__c, 1); }
02200
02201 void
02202 insert(size_t __p)
02203 {
02204 _CharT __c = _CharT();
02205 insert(__p, &__c, 1);
02206 }
02207
02208 void
02209 insert(size_t __p, const _CharT* __i, const _CharT* __j)
02210 {
02211 rope __r(__i, __j);
02212 insert(__p, __r);
02213 }
02214
02215 void
02216 insert(size_t __p, const const_iterator& __i,
02217 const const_iterator& __j)
02218 {
02219 rope __r(__i, __j);
02220 insert(__p, __r);
02221 }
02222
02223 void
02224 insert(size_t __p, const iterator& __i,
02225 const iterator& __j)
02226 {
02227 rope __r(__i, __j);
02228 insert(__p, __r);
02229 }
02230
02231
02232
02233 void
02234 replace(size_t __p, size_t __n, const rope& __r)
02235 {
02236 _RopeRep* __result =
02237 replace(this->_M_tree_ptr, __p, __p + __n, __r._M_tree_ptr);
02238 _S_unref(this->_M_tree_ptr);
02239 this->_M_tree_ptr = __result;
02240 }
02241
02242 void
02243 replace(size_t __p, size_t __n,
02244 const _CharT* __i, size_t __i_len)
02245 {
02246 rope __r(__i, __i_len);
02247 replace(__p, __n, __r);
02248 }
02249
02250 void
02251 replace(size_t __p, size_t __n, _CharT __c)
02252 {
02253 rope __r(__c);
02254 replace(__p, __n, __r);
02255 }
02256
02257 void
02258 replace(size_t __p, size_t __n, const _CharT* __c_string)
02259 {
02260 rope __r(__c_string);
02261 replace(__p, __n, __r);
02262 }
02263
02264 void
02265 replace(size_t __p, size_t __n,
02266 const _CharT* __i, const _CharT* __j)
02267 {
02268 rope __r(__i, __j);
02269 replace(__p, __n, __r);
02270 }
02271
02272 void
02273 replace(size_t __p, size_t __n,
02274 const const_iterator& __i, const const_iterator& __j)
02275 {
02276 rope __r(__i, __j);
02277 replace(__p, __n, __r);
02278 }
02279
02280 void
02281 replace(size_t __p, size_t __n,
02282 const iterator& __i, const iterator& __j)
02283 {
02284 rope __r(__i, __j);
02285 replace(__p, __n, __r);
02286 }
02287
02288
02289 void
02290 replace(size_t __p, _CharT __c)
02291 {
02292 iterator __i(this, __p);
02293 *__i = __c;
02294 }
02295
02296 void
02297 replace(size_t __p, const rope& __r)
02298 { replace(__p, 1, __r); }
02299
02300 void
02301 replace(size_t __p, const _CharT* __i, size_t __i_len)
02302 { replace(__p, 1, __i, __i_len); }
02303
02304 void
02305 replace(size_t __p, const _CharT* __c_string)
02306 { replace(__p, 1, __c_string); }
02307
02308 void
02309 replace(size_t __p, const _CharT* __i, const _CharT* __j)
02310 { replace(__p, 1, __i, __j); }
02311
02312 void
02313 replace(size_t __p, const const_iterator& __i,
02314 const const_iterator& __j)
02315 { replace(__p, 1, __i, __j); }
02316
02317 void
02318 replace(size_t __p, const iterator& __i,
02319 const iterator& __j)
02320 { replace(__p, 1, __i, __j); }
02321
02322
02323 void
02324 erase(size_t __p, size_t __n)
02325 {
02326 _RopeRep* __result = replace(this->_M_tree_ptr, __p,
02327 __p + __n, 0);
02328 _S_unref(this->_M_tree_ptr);
02329 this->_M_tree_ptr = __result;
02330 }
02331
02332
02333 void
02334 erase(size_t __p)
02335 { erase(__p, __p + 1); }
02336
02337
02338 iterator
02339 insert(const iterator& __p, const rope& __r)
02340 {
02341 insert(__p.index(), __r);
02342 return __p;
02343 }
02344
02345 iterator
02346 insert(const iterator& __p, size_t __n, _CharT __c)
02347 {
02348 insert(__p.index(), __n, __c);
02349 return __p;
02350 }
02351
02352 iterator insert(const iterator& __p, _CharT __c)
02353 {
02354 insert(__p.index(), __c);
02355 return __p;
02356 }
02357
02358 iterator
02359 insert(const iterator& __p )
02360 {
02361 insert(__p.index());
02362 return __p;
02363 }
02364
02365 iterator
02366 insert(const iterator& __p, const _CharT* c_string)
02367 {
02368 insert(__p.index(), c_string);
02369 return __p;
02370 }
02371
02372 iterator
02373 insert(const iterator& __p, const _CharT* __i, size_t __n)
02374 {
02375 insert(__p.index(), __i, __n);
02376 return __p;
02377 }
02378
02379 iterator
02380 insert(const iterator& __p, const _CharT* __i,
02381 const _CharT* __j)
02382 {
02383 insert(__p.index(), __i, __j);
02384 return __p;
02385 }
02386
02387 iterator
02388 insert(const iterator& __p,
02389 const const_iterator& __i, const const_iterator& __j)
02390 {
02391 insert(__p.index(), __i, __j);
02392 return __p;
02393 }
02394
02395 iterator
02396 insert(const iterator& __p,
02397 const iterator& __i, const iterator& __j)
02398 {
02399 insert(__p.index(), __i, __j);
02400 return __p;
02401 }
02402
02403
02404 void
02405 replace(const iterator& __p, const iterator& __q, const rope& __r)
02406 { replace(__p.index(), __q.index() - __p.index(), __r); }
02407
02408 void
02409 replace(const iterator& __p, const iterator& __q, _CharT __c)
02410 { replace(__p.index(), __q.index() - __p.index(), __c); }
02411
02412 void
02413 replace(const iterator& __p, const iterator& __q,
02414 const _CharT* __c_string)
02415 { replace(__p.index(), __q.index() - __p.index(), __c_string); }
02416
02417 void
02418 replace(const iterator& __p, const iterator& __q,
02419 const _CharT* __i, size_t __n)
02420 { replace(__p.index(), __q.index() - __p.index(), __i, __n); }
02421
02422 void
02423 replace(const iterator& __p, const iterator& __q,
02424 const _CharT* __i, const _CharT* __j)
02425 { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
02426
02427 void
02428 replace(const iterator& __p, const iterator& __q,
02429 const const_iterator& __i, const const_iterator& __j)
02430 { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
02431
02432 void
02433 replace(const iterator& __p, const iterator& __q,
02434 const iterator& __i, const iterator& __j)
02435 { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
02436
02437
02438 void
02439 replace(const iterator& __p, const rope& __r)
02440 { replace(__p.index(), __r); }
02441
02442 void
02443 replace(const iterator& __p, _CharT __c)
02444 { replace(__p.index(), __c); }
02445
02446 void
02447 replace(const iterator& __p, const _CharT* __c_string)
02448 { replace(__p.index(), __c_string); }
02449
02450 void
02451 replace(const iterator& __p, const _CharT* __i, size_t __n)
02452 { replace(__p.index(), __i, __n); }
02453
02454 void
02455 replace(const iterator& __p, const _CharT* __i, const _CharT* __j)
02456 { replace(__p.index(), __i, __j); }
02457
02458 void
02459 replace(const iterator& __p, const_iterator __i, const_iterator __j)
02460 { replace(__p.index(), __i, __j); }
02461
02462 void
02463 replace(const iterator& __p, iterator __i, iterator __j)
02464 { replace(__p.index(), __i, __j); }
02465
02466
02467 iterator
02468 erase(const iterator& __p, const iterator& __q)
02469 {
02470 size_t __p_index = __p.index();
02471 erase(__p_index, __q.index() - __p_index);
02472 return iterator(this, __p_index);
02473 }
02474
02475 iterator
02476 erase(const iterator& __p)
02477 {
02478 size_t __p_index = __p.index();
02479 erase(__p_index, 1);
02480 return iterator(this, __p_index);
02481 }
02482
02483 rope
02484 substr(size_t __start, size_t __len = 1) const
02485 {
02486 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
02487 __start,
02488 __start + __len));
02489 }
02490
02491 rope
02492 substr(iterator __start, iterator __end) const
02493 {
02494 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
02495 __start.index(),
02496 __end.index()));
02497 }
02498
02499 rope
02500 substr(iterator __start) const
02501 {
02502 size_t __pos = __start.index();
02503 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
02504 __pos, __pos + 1));
02505 }
02506
02507 rope
02508 substr(const_iterator __start, const_iterator __end) const
02509 {
02510
02511
02512 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
02513 __start.index(),
02514 __end.index()));
02515 }
02516
02517 rope<_CharT, _Alloc>
02518 substr(const_iterator __start)
02519 {
02520 size_t __pos = __start.index();
02521 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
02522 __pos, __pos + 1));
02523 }
02524
02525 static const size_type npos;
02526
02527 size_type find(_CharT __c, size_type __pos = 0) const;
02528
02529 size_type
02530 find(const _CharT* __s, size_type __pos = 0) const
02531 {
02532 size_type __result_pos;
02533 const_iterator __result =
02534 std::search(const_begin() + __pos, const_end(),
02535 __s, __s + _S_char_ptr_len(__s));
02536 __result_pos = __result.index();
02537 #ifndef __STL_OLD_ROPE_SEMANTICS
02538 if (__result_pos == size())
02539 __result_pos = npos;
02540 #endif
02541 return __result_pos;
02542 }
02543
02544 iterator
02545 mutable_begin()
02546 { return(iterator(this, 0)); }
02547
02548 iterator
02549 mutable_end()
02550 { return(iterator(this, size())); }
02551
02552 typedef reverse_iterator<iterator> reverse_iterator;
02553
02554 reverse_iterator
02555 mutable_rbegin()
02556 { return reverse_iterator(mutable_end()); }
02557
02558 reverse_iterator
02559 mutable_rend()
02560 { return reverse_iterator(mutable_begin()); }
02561
02562 reference
02563 mutable_reference_at(size_type __pos)
02564 { return reference(this, __pos); }
02565
02566 #ifdef __STD_STUFF
02567 reference
02568 operator[] (size_type __pos)
02569 { return _char_ref_proxy(this, __pos); }
02570
02571 reference
02572 at(size_type __pos)
02573 {
02574
02575 return (*this)[__pos];
02576 }
02577
02578 void resize(size_type __n, _CharT __c) { }
02579 void resize(size_type __n) { }
02580 void reserve(size_type __res_arg = 0) { }
02581
02582 size_type
02583 capacity() const
02584 { return max_size(); }
02585
02586
02587
02588
02589 size_type
02590 copy(_CharT* __buffer, size_type __n,
02591 size_type __pos = 0) const
02592 { return copy(__pos, __n, __buffer); }
02593
02594 iterator
02595 end()
02596 { return mutable_end(); }
02597
02598 iterator
02599 begin()
02600 { return mutable_begin(); }
02601
02602 reverse_iterator
02603 rend()
02604 { return mutable_rend(); }
02605
02606 reverse_iterator
02607 rbegin()
02608 { return mutable_rbegin(); }
02609
02610 #else
02611 const_iterator
02612 end()
02613 { return const_end(); }
02614
02615 const_iterator
02616 begin()
02617 { return const_begin(); }
02618
02619 const_reverse_iterator
02620 rend()
02621 { return const_rend(); }
02622
02623 const_reverse_iterator
02624 rbegin()
02625 { return const_rbegin(); }
02626
02627 #endif
02628 };
02629
02630 template <class _CharT, class _Alloc>
02631 const typename rope<_CharT, _Alloc>::size_type
02632 rope<_CharT, _Alloc>::npos = (size_type)(-1);
02633
02634 template <class _CharT, class _Alloc>
02635 inline bool operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02636 const _Rope_const_iterator<_CharT, _Alloc>& __y)
02637 { return (__x._M_current_pos == __y._M_current_pos
02638 && __x._M_root == __y._M_root); }
02639
02640 template <class _CharT, class _Alloc>
02641 inline bool operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02642 const _Rope_const_iterator<_CharT, _Alloc>& __y)
02643 { return (__x._M_current_pos < __y._M_current_pos); }
02644
02645 template <class _CharT, class _Alloc>
02646 inline bool operator!=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02647 const _Rope_const_iterator<_CharT, _Alloc>& __y)
02648 { return !(__x == __y); }
02649
02650 template <class _CharT, class _Alloc>
02651 inline bool operator>(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02652 const _Rope_const_iterator<_CharT, _Alloc>& __y)
02653 { return __y < __x; }
02654
02655 template <class _CharT, class _Alloc>
02656 inline bool
02657 operator<=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02658 const _Rope_const_iterator<_CharT, _Alloc>& __y)
02659 { return !(__y < __x); }
02660
02661 template <class _CharT, class _Alloc>
02662 inline bool
02663 operator>=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02664 const _Rope_const_iterator<_CharT, _Alloc>& __y)
02665 { return !(__x < __y); }
02666
02667 template <class _CharT, class _Alloc>
02668 inline ptrdiff_t
02669 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
02670 const _Rope_const_iterator<_CharT, _Alloc>& __y)
02671 { return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; }
02672
02673 template <class _CharT, class _Alloc>
02674 inline _Rope_const_iterator<_CharT, _Alloc>
02675 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
02676 { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
02677 __x._M_current_pos - __n); }
02678
02679 template <class _CharT, class _Alloc>
02680 inline _Rope_const_iterator<_CharT, _Alloc>
02681 operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
02682 { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
02683 __x._M_current_pos + __n); }
02684
02685 template <class _CharT, class _Alloc>
02686 inline _Rope_const_iterator<_CharT, _Alloc>
02687 operator+(ptrdiff_t __n, const _Rope_const_iterator<_CharT, _Alloc>& __x)
02688 { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
02689 __x._M_current_pos + __n); }
02690
02691 template <class _CharT, class _Alloc>
02692 inline bool
02693 operator==(const _Rope_iterator<_CharT, _Alloc>& __x,
02694 const _Rope_iterator<_CharT, _Alloc>& __y)
02695 {return (__x._M_current_pos == __y._M_current_pos
02696 && __x._M_root_rope == __y._M_root_rope); }
02697
02698 template <class _CharT, class _Alloc>
02699 inline bool
02700 operator<(const _Rope_iterator<_CharT, _Alloc>& __x,
02701 const _Rope_iterator<_CharT, _Alloc>& __y)
02702 { return (__x._M_current_pos < __y._M_current_pos); }
02703
02704 template <class _CharT, class _Alloc>
02705 inline bool
02706 operator!=(const _Rope_iterator<_CharT, _Alloc>& __x,
02707 const _Rope_iterator<_CharT, _Alloc>& __y)
02708 { return !(__x == __y); }
02709
02710 template <class _CharT, class _Alloc>
02711 inline bool
02712 operator>(const _Rope_iterator<_CharT, _Alloc>& __x,
02713 const _Rope_iterator<_CharT, _Alloc>& __y)
02714 { return __y < __x; }
02715
02716 template <class _CharT, class _Alloc>
02717 inline bool
02718 operator<=(const _Rope_iterator<_CharT, _Alloc>& __x,
02719 const _Rope_iterator<_CharT, _Alloc>& __y)
02720 { return !(__y < __x); }
02721
02722 template <class _CharT, class _Alloc>
02723 inline bool
02724 operator>=(const _Rope_iterator<_CharT, _Alloc>& __x,
02725 const _Rope_iterator<_CharT, _Alloc>& __y)
02726 { return !(__x < __y); }
02727
02728 template <class _CharT, class _Alloc>
02729 inline ptrdiff_t
02730 operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
02731 const _Rope_iterator<_CharT, _Alloc>& __y)
02732 { return ((ptrdiff_t)__x._M_current_pos
02733 - (ptrdiff_t)__y._M_current_pos); }
02734
02735 template <class _CharT, class _Alloc>
02736 inline _Rope_iterator<_CharT, _Alloc>
02737 operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
02738 ptrdiff_t __n)
02739 { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
02740 __x._M_current_pos - __n); }
02741
02742 template <class _CharT, class _Alloc>
02743 inline _Rope_iterator<_CharT, _Alloc>
02744 operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
02745 { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
02746 __x._M_current_pos + __n); }
02747
02748 template <class _CharT, class _Alloc>
02749 inline _Rope_iterator<_CharT, _Alloc>
02750 operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x)
02751 { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
02752 __x._M_current_pos + __n); }
02753
02754 template <class _CharT, class _Alloc>
02755 inline rope<_CharT, _Alloc>
02756 operator+(const rope<_CharT, _Alloc>& __left,
02757 const rope<_CharT, _Alloc>& __right)
02758 {
02759
02760
02761 typedef rope<_CharT, _Alloc> rope_type;
02762 return rope_type(rope_type::_S_concat(__left._M_tree_ptr,
02763 __right._M_tree_ptr));
02764 }
02765
02766 template <class _CharT, class _Alloc>
02767 inline rope<_CharT, _Alloc>&
02768 operator+=(rope<_CharT, _Alloc>& __left,
02769 const rope<_CharT, _Alloc>& __right)
02770 {
02771 __left.append(__right);
02772 return __left;
02773 }
02774
02775 template <class _CharT, class _Alloc>
02776 inline rope<_CharT, _Alloc>
02777 operator+(const rope<_CharT, _Alloc>& __left,
02778 const _CharT* __right)
02779 {
02780 typedef rope<_CharT, _Alloc> rope_type;
02781 size_t __rlen = rope_type::_S_char_ptr_len(__right);
02782 return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
02783 __right, __rlen));
02784 }
02785
02786 template <class _CharT, class _Alloc>
02787 inline rope<_CharT, _Alloc>&
02788 operator+=(rope<_CharT, _Alloc>& __left,
02789 const _CharT* __right)
02790 {
02791 __left.append(__right);
02792 return __left;
02793 }
02794
02795 template <class _CharT, class _Alloc>
02796 inline rope<_CharT, _Alloc>
02797 operator+(const rope<_CharT, _Alloc>& __left, _CharT __right)
02798 {
02799 typedef rope<_CharT, _Alloc> rope_type;
02800 return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
02801 &__right, 1));
02802 }
02803
02804 template <class _CharT, class _Alloc>
02805 inline rope<_CharT, _Alloc>&
02806 operator+=(rope<_CharT, _Alloc>& __left, _CharT __right)
02807 {
02808 __left.append(__right);
02809 return __left;
02810 }
02811
02812 template <class _CharT, class _Alloc>
02813 bool
02814 operator<(const rope<_CharT, _Alloc>& __left,
02815 const rope<_CharT, _Alloc>& __right)
02816 { return __left.compare(__right) < 0; }
02817
02818 template <class _CharT, class _Alloc>
02819 bool
02820 operator==(const rope<_CharT, _Alloc>& __left,
02821 const rope<_CharT, _Alloc>& __right)
02822 { return __left.compare(__right) == 0; }
02823
02824 template <class _CharT, class _Alloc>
02825 inline bool
02826 operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
02827 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
02828 { return (__x._M_pos == __y._M_pos && __x._M_root == __y._M_root); }
02829
02830 template <class _CharT, class _Alloc>
02831 inline bool
02832 operator!=(const rope<_CharT, _Alloc>& __x,
02833 const rope<_CharT, _Alloc>& __y)
02834 { return !(__x == __y); }
02835
02836 template <class _CharT, class _Alloc>
02837 inline bool
02838 operator>(const rope<_CharT, _Alloc>& __x,
02839 const rope<_CharT, _Alloc>& __y)
02840 { return __y < __x; }
02841
02842 template <class _CharT, class _Alloc>
02843 inline bool
02844 operator<=(const rope<_CharT, _Alloc>& __x,
02845 const rope<_CharT, _Alloc>& __y)
02846 { return !(__y < __x); }
02847
02848 template <class _CharT, class _Alloc>
02849 inline bool
02850 operator>=(const rope<_CharT, _Alloc>& __x,
02851 const rope<_CharT, _Alloc>& __y)
02852 { return !(__x < __y); }
02853
02854 template <class _CharT, class _Alloc>
02855 inline bool
02856 operator!=(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
02857 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
02858 { return !(__x == __y); }
02859
02860 template<class _CharT, class _Traits, class _Alloc>
02861 std::basic_ostream<_CharT, _Traits>&
02862 operator<<(std::basic_ostream<_CharT, _Traits>& __o,
02863 const rope<_CharT, _Alloc>& __r);
02864
02865 typedef rope<char> crope;
02866 typedef rope<wchar_t> wrope;
02867
02868 inline crope::reference
02869 __mutable_reference_at(crope& __c, size_t __i)
02870 { return __c.mutable_reference_at(__i); }
02871
02872 inline wrope::reference
02873 __mutable_reference_at(wrope& __c, size_t __i)
02874 { return __c.mutable_reference_at(__i); }
02875
02876 template <class _CharT, class _Alloc>
02877 inline void
02878 swap(rope<_CharT, _Alloc>& __x, rope<_CharT, _Alloc>& __y)
02879 { __x.swap(__y); }
02880
02881
02882 template<>
02883 struct hash<crope>
02884 {
02885 size_t
02886 operator()(const crope& __str) const
02887 {
02888 size_t __size = __str.size();
02889 if (0 == __size)
02890 return 0;
02891 return 13 * __str[0] + 5 * __str[__size - 1] + __size;
02892 }
02893 };
02894
02895
02896 template<>
02897 struct hash<wrope>
02898 {
02899 size_t
02900 operator()(const wrope& __str) const
02901 {
02902 size_t __size = __str.size();
02903 if (0 == __size)
02904 return 0;
02905 return 13 * __str[0] + 5 * __str[__size - 1] + __size;
02906 }
02907 };
02908
02909 _GLIBCXX_END_NAMESPACE
02910
02911 # include <ext/ropeimpl.h>
02912
02913 #endif