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 #include <cstdio>
00049 #include <iostream>
00050 #include <bits/functexcept.h>
00051
00052 #include <ext/algorithm>
00053 #include <ext/memory>
00054 #include <ext/numeric>
00055
00056 namespace __gnu_cxx
00057 {
00058 using std::size_t;
00059 using std::printf;
00060 using std::basic_ostream;
00061 using std::__throw_length_error;
00062 using std::__alloc;
00063 using std::_Destroy;
00064 using std::uninitialized_fill_n;
00065
00066
00067
00068
00069
00070 template <class _CharT, class _Alloc>
00071 void _Rope_iterator_base<_CharT,_Alloc>::_S_setbuf(
00072 _Rope_iterator_base<_CharT,_Alloc>& __x)
00073 {
00074 const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index];
00075 size_t __leaf_pos = __x._M_leaf_pos;
00076 size_t __pos = __x._M_current_pos;
00077
00078 switch(__leaf->_M_tag) {
00079 case _RopeRep::_S_leaf:
00080 __x._M_buf_start =
00081 ((_Rope_RopeLeaf<_CharT,_Alloc>*)__leaf)->_M_data;
00082 __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos);
00083 __x._M_buf_end = __x._M_buf_start + __leaf->_M_size;
00084 break;
00085 case _RopeRep::_S_function:
00086 case _RopeRep::_S_substringfn:
00087 {
00088 size_t __len = _S_iterator_buf_len;
00089 size_t __buf_start_pos = __leaf_pos;
00090 size_t __leaf_end = __leaf_pos + __leaf->_M_size;
00091 char_producer<_CharT>* __fn =
00092 ((_Rope_RopeFunction<_CharT,_Alloc>*)__leaf)->_M_fn;
00093
00094 if (__buf_start_pos + __len <= __pos) {
00095 __buf_start_pos = __pos - __len/4;
00096 if (__buf_start_pos + __len > __leaf_end) {
00097 __buf_start_pos = __leaf_end - __len;
00098 }
00099 }
00100 if (__buf_start_pos + __len > __leaf_end) {
00101 __len = __leaf_end - __buf_start_pos;
00102 }
00103 (*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf);
00104 __x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos);
00105 __x._M_buf_start = __x._M_tmp_buf;
00106 __x._M_buf_end = __x._M_tmp_buf + __len;
00107 }
00108 break;
00109 default:
00110 break;
00111 }
00112 }
00113
00114
00115
00116 template <class _CharT, class _Alloc>
00117 void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache
00118 (_Rope_iterator_base<_CharT,_Alloc>& __x)
00119 {
00120 const _RopeRep* __path[_RopeRep::_S_max_rope_depth+1];
00121 const _RopeRep* __curr_rope;
00122 int __curr_depth = -1;
00123 size_t __curr_start_pos = 0;
00124 size_t __pos = __x._M_current_pos;
00125 unsigned char __dirns = 0;
00126
00127 if (__pos >= __x._M_root->_M_size) {
00128 __x._M_buf_ptr = 0;
00129 return;
00130 }
00131 __curr_rope = __x._M_root;
00132 if (0 != __curr_rope->_M_c_string) {
00133
00134 __x._M_buf_start = __curr_rope->_M_c_string;
00135 __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size;
00136 __x._M_buf_ptr = __curr_rope->_M_c_string + __pos;
00137 __x._M_path_end[0] = __curr_rope;
00138 __x._M_leaf_index = 0;
00139 __x._M_leaf_pos = 0;
00140 return;
00141 }
00142 for(;;) {
00143 ++__curr_depth;
00144 __path[__curr_depth] = __curr_rope;
00145 switch(__curr_rope->_M_tag) {
00146 case _RopeRep::_S_leaf:
00147 case _RopeRep::_S_function:
00148 case _RopeRep::_S_substringfn:
00149 __x._M_leaf_pos = __curr_start_pos;
00150 goto done;
00151 case _RopeRep::_S_concat:
00152 {
00153 _Rope_RopeConcatenation<_CharT,_Alloc>* __c =
00154 (_Rope_RopeConcatenation<_CharT,_Alloc>*)__curr_rope;
00155 _RopeRep* __left = __c->_M_left;
00156 size_t __left_len = __left->_M_size;
00157
00158 __dirns <<= 1;
00159 if (__pos >= __curr_start_pos + __left_len) {
00160 __dirns |= 1;
00161 __curr_rope = __c->_M_right;
00162 __curr_start_pos += __left_len;
00163 } else {
00164 __curr_rope = __left;
00165 }
00166 }
00167 break;
00168 }
00169 }
00170 done:
00171
00172 {
00173 int __i = -1;
00174 int __j = __curr_depth + 1 - _S_path_cache_len;
00175
00176 if (__j < 0) __j = 0;
00177 while (__j <= __curr_depth) {
00178 __x._M_path_end[++__i] = __path[__j++];
00179 }
00180 __x._M_leaf_index = __i;
00181 }
00182 __x._M_path_directions = __dirns;
00183 _S_setbuf(__x);
00184 }
00185
00186
00187
00188 template <class _CharT, class _Alloc>
00189 void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache_for_incr
00190 (_Rope_iterator_base<_CharT,_Alloc>& __x)
00191 {
00192 int __current_index = __x._M_leaf_index;
00193 const _RopeRep* __current_node = __x._M_path_end[__current_index];
00194 size_t __len = __current_node->_M_size;
00195 size_t __node_start_pos = __x._M_leaf_pos;
00196 unsigned char __dirns = __x._M_path_directions;
00197 _Rope_RopeConcatenation<_CharT,_Alloc>* __c;
00198
00199 if (__x._M_current_pos - __node_start_pos < __len) {
00200
00201 _S_setbuf(__x);
00202 return;
00203 }
00204
00205 while (--__current_index >= 0) {
00206 if (!(__dirns & 1) )
00207 break;
00208 __current_node = __x._M_path_end[__current_index];
00209 __c = (_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node;
00210
00211
00212 __node_start_pos -= __c->_M_left->_M_size;
00213 __dirns >>= 1;
00214 }
00215 if (__current_index < 0) {
00216
00217 _S_setcache(__x);
00218 return;
00219 }
00220 __current_node = __x._M_path_end[__current_index];
00221 __c = (_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node;
00222
00223
00224
00225 __node_start_pos += __c->_M_left->_M_size;
00226 __current_node = __c->_M_right;
00227 __x._M_path_end[++__current_index] = __current_node;
00228 __dirns |= 1;
00229 while (_RopeRep::_S_concat == __current_node->_M_tag) {
00230 ++__current_index;
00231 if (_S_path_cache_len == __current_index) {
00232 int __i;
00233 for (__i = 0; __i < _S_path_cache_len-1; __i++) {
00234 __x._M_path_end[__i] = __x._M_path_end[__i+1];
00235 }
00236 --__current_index;
00237 }
00238 __current_node =
00239 ((_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node)->_M_left;
00240 __x._M_path_end[__current_index] = __current_node;
00241 __dirns <<= 1;
00242
00243 }
00244 __x._M_leaf_index = __current_index;
00245 __x._M_leaf_pos = __node_start_pos;
00246 __x._M_path_directions = __dirns;
00247 _S_setbuf(__x);
00248 }
00249
00250 template <class _CharT, class _Alloc>
00251 void _Rope_iterator_base<_CharT,_Alloc>::_M_incr(size_t __n) {
00252 _M_current_pos += __n;
00253 if (0 != _M_buf_ptr) {
00254 size_t __chars_left = _M_buf_end - _M_buf_ptr;
00255 if (__chars_left > __n) {
00256 _M_buf_ptr += __n;
00257 } else if (__chars_left == __n) {
00258 _M_buf_ptr += __n;
00259 _S_setcache_for_incr(*this);
00260 } else {
00261 _M_buf_ptr = 0;
00262 }
00263 }
00264 }
00265
00266 template <class _CharT, class _Alloc>
00267 void _Rope_iterator_base<_CharT,_Alloc>::_M_decr(size_t __n) {
00268 if (0 != _M_buf_ptr) {
00269 size_t __chars_left = _M_buf_ptr - _M_buf_start;
00270 if (__chars_left >= __n) {
00271 _M_buf_ptr -= __n;
00272 } else {
00273 _M_buf_ptr = 0;
00274 }
00275 }
00276 _M_current_pos -= __n;
00277 }
00278
00279 template <class _CharT, class _Alloc>
00280 void _Rope_iterator<_CharT,_Alloc>::_M_check() {
00281 if (_M_root_rope->_M_tree_ptr != _M_root) {
00282
00283 _RopeRep::_S_unref(_M_root);
00284 _M_root = _M_root_rope->_M_tree_ptr;
00285 _RopeRep::_S_ref(_M_root);
00286 _M_buf_ptr = 0;
00287 }
00288 }
00289
00290 template <class _CharT, class _Alloc>
00291 inline
00292 _Rope_const_iterator<_CharT, _Alloc>::_Rope_const_iterator(
00293 const _Rope_iterator<_CharT,_Alloc>& __x)
00294 : _Rope_iterator_base<_CharT,_Alloc>(__x)
00295 { }
00296
00297 template <class _CharT, class _Alloc>
00298 inline _Rope_iterator<_CharT,_Alloc>::_Rope_iterator(
00299 rope<_CharT,_Alloc>& __r, size_t __pos)
00300 : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos),
00301 _M_root_rope(&__r)
00302 {
00303 _RopeRep::_S_ref(_M_root);
00304 }
00305
00306 template <class _CharT, class _Alloc>
00307 inline size_t
00308 rope<_CharT,_Alloc>::_S_char_ptr_len(const _CharT* __s)
00309 {
00310 const _CharT* __p = __s;
00311
00312 while (!_S_is0(*__p)) { ++__p; }
00313 return (__p - __s);
00314 }
00315
00316
00317 #ifndef __GC
00318
00319 template <class _CharT, class _Alloc>
00320 inline void _Rope_RopeRep<_CharT,_Alloc>::_M_free_c_string()
00321 {
00322 _CharT* __cstr = _M_c_string;
00323 if (0 != __cstr) {
00324 size_t __size = _M_size + 1;
00325 _Destroy(__cstr, __cstr + __size);
00326 _Data_deallocate(__cstr, __size);
00327 }
00328 }
00329
00330
00331 template <class _CharT, class _Alloc>
00332 inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string(_CharT* __s,
00333 size_t __n,
00334 allocator_type __a)
00335 {
00336 if (!_S_is_basic_char_type((_CharT*)0)) {
00337 _Destroy(__s, __s + __n);
00338 }
00339
00340 __a.deallocate(
00341 __s, _Rope_RopeLeaf<_CharT,_Alloc>::_S_rounded_up_size(__n));
00342 }
00343
00344
00345
00346
00347
00348
00349
00350
00351 template <class _CharT, class _Alloc>
00352 void _Rope_RopeRep<_CharT,_Alloc>::_M_free_tree()
00353 {
00354 switch(_M_tag) {
00355 case _S_leaf:
00356 {
00357 _Rope_RopeLeaf<_CharT,_Alloc>* __l
00358 = (_Rope_RopeLeaf<_CharT,_Alloc>*)this;
00359 __l->_Rope_RopeLeaf<_CharT,_Alloc>::~_Rope_RopeLeaf();
00360 _L_deallocate(__l, 1);
00361 break;
00362 }
00363 case _S_concat:
00364 {
00365 _Rope_RopeConcatenation<_CharT,_Alloc>* __c
00366 = (_Rope_RopeConcatenation<_CharT,_Alloc>*)this;
00367 __c->_Rope_RopeConcatenation<_CharT,_Alloc>::
~_Rope_RopeConcatenation();
00368 _C_deallocate(__c, 1);
00369 break;
00370 }
00371 case _S_function:
00372 {
00373 _Rope_RopeFunction<_CharT,_Alloc>* __f
00374 = (_Rope_RopeFunction<_CharT,_Alloc>*)this;
00375 __f->_Rope_RopeFunction<_CharT,_Alloc>::~_Rope_RopeFunction();
00376 _F_deallocate(__f, 1);
00377 break;
00378 }
00379 case _S_substringfn:
00380 {
00381 _Rope_RopeSubstring<_CharT,_Alloc>* __ss =
00382 (_Rope_RopeSubstring<_CharT,_Alloc>*)this;
00383 __ss->_Rope_RopeSubstring<_CharT,_Alloc>::
~_Rope_RopeSubstring();
00384 _S_deallocate(__ss, 1);
00385 break;
00386 }
00387 }
00388 }
00389 #else
00390
00391 template <class _CharT, class _Alloc>
00392 inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string
00393 (const _CharT*, size_t, allocator_type)
00394 {}
00395
00396 #endif
00397
00398
00399
00400
00401 template <class _CharT, class _Alloc>
00402 typename rope<_CharT,_Alloc>::_RopeLeaf*
00403 rope<_CharT,_Alloc>::_S_leaf_concat_char_iter
00404 (_RopeLeaf* __r, const _CharT* __iter, size_t __len)
00405 {
00406 size_t __old_len = __r->_M_size;
00407 _CharT* __new_data = (_CharT*)
00408 _Data_allocate(_S_rounded_up_size(__old_len + __len));
00409 _RopeLeaf* __result;
00410
00411 uninitialized_copy_n(__r->_M_data, __old_len, __new_data);
00412 uninitialized_copy_n(__iter, __len, __new_data + __old_len);
00413 _S_cond_store_eos(__new_data[__old_len + __len]);
00414 try {
00415 __result = _S_new_RopeLeaf(__new_data, __old_len + __len,
00416 __r->get_allocator());
00417 }
00418 catch(...)
00419 {
00420 _RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len,
00421 __r->get_allocator());
00422 __throw_exception_again;
00423 }
00424 return __result;
00425 }
00426
00427 #ifndef __GC
00428
00429 template <class _CharT, class _Alloc>
00430 typename rope<_CharT,_Alloc>::_RopeLeaf*
00431 rope<_CharT,_Alloc>::_S_destr_leaf_concat_char_iter
00432 (_RopeLeaf* __r, const _CharT* __iter, size_t __len)
00433 {
00434 if (__r->_M_ref_count > 1)
00435 return _S_leaf_concat_char_iter(__r, __iter, __len);
00436 size_t __old_len = __r->_M_size;
00437 if (_S_allocated_capacity(__old_len) >= __old_len + __len) {
00438
00439
00440 uninitialized_copy_n(__iter, __len, __r->_M_data + __old_len);
00441 if (_S_is_basic_char_type((_CharT*)0)) {
00442 _S_cond_store_eos(__r->_M_data[__old_len + __len]);
00443 } else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string) {
00444 __r->_M_free_c_string();
00445 __r->_M_c_string = 0;
00446 }
00447 __r->_M_size = __old_len + __len;
00448 __r->_M_ref_count = 2;
00449 return __r;
00450 } else {
00451 _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len);
00452 return __result;
00453 }
00454 }
00455 #endif
00456
00457
00458
00459
00460 template <class _CharT, class _Alloc>
00461 typename rope<_CharT,_Alloc>::_RopeRep*
00462 rope<_CharT,_Alloc>::_S_tree_concat (_RopeRep* __left, _RopeRep* __right)
00463 {
00464 _RopeConcatenation* __result = _S_new_RopeConcatenation(__left, __right,
00465 __left->get_allocator());
00466 size_t __depth = __result->_M_depth;
00467
00468 if (__depth > 20 && (__result->_M_size < 1000 ||
00469 __depth > _RopeRep::_S_max_rope_depth))
00470 {
00471 _RopeRep* __balanced;
00472
00473 try
00474 {
00475 __balanced = _S_balance(__result);
00476 __result->_M_unref_nonnil();
00477 }
00478 catch(...)
00479 {
00480 _C_deallocate(__result,1);
00481 __throw_exception_again;
00482 }
00483
00484
00485
00486
00487 return __balanced;
00488 }
00489 else
00490 return __result;
00491 }
00492
00493 template <class _CharT, class _Alloc>
00494 typename
00495 rope<_CharT,_Alloc>::_RopeRep* rope<_CharT,_Alloc>::_S_concat_char_iter
00496 (_RopeRep* __r, const _CharT*__s, size_t __slen)
00497 {
00498 _RopeRep* __result;
00499 if (0 == __slen) {
00500 _S_ref(__r);
00501 return __r;
00502 }
00503 if (0 == __r)
00504 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
00505 __r->get_allocator());
00506 if (_RopeRep::_S_leaf == __r->_M_tag &&
00507 __r->_M_size + __slen <= _S_copy_max) {
00508 __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
00509 return __result;
00510 }
00511 if (_RopeRep::_S_concat == __r->_M_tag
00512 && _RopeRep::_S_leaf == ((_RopeConcatenation*)__r)->_M_right->_M_tag) {
00513 _RopeLeaf* __right =
00514 (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right);
00515 if (__right->_M_size + __slen <= _S_copy_max) {
00516 _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left;
00517 _RopeRep* __nright =
00518 _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen);
00519 __left->_M_ref_nonnil();
00520 try {
00521 __result = _S_tree_concat(__left, __nright);
00522 }
00523 catch(...)
00524 {
00525 _S_unref(__left);
00526 _S_unref(__nright);
00527 __throw_exception_again;
00528 }
00529 return __result;
00530 }
00531 }
00532 _RopeRep* __nright =
00533 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator());
00534 try {
00535 __r->_M_ref_nonnil();
00536 __result = _S_tree_concat(__r, __nright);
00537 }
00538 catch(...)
00539 {
00540 _S_unref(__r);
00541 _S_unref(__nright);
00542 __throw_exception_again;
00543 }
00544 return __result;
00545 }
00546
00547 #ifndef __GC
00548 template <class _CharT, class _Alloc>
00549 typename rope<_CharT,_Alloc>::_RopeRep*
00550 rope<_CharT,_Alloc>::_S_destr_concat_char_iter(
00551 _RopeRep* __r, const _CharT* __s, size_t __slen)
00552 {
00553 _RopeRep* __result;
00554 if (0 == __r)
00555 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
00556 __r->get_allocator());
00557 size_t __count = __r->_M_ref_count;
00558 size_t __orig_size = __r->_M_size;
00559 if (__count > 1) return _S_concat_char_iter(__r, __s, __slen);
00560 if (0 == __slen) {
00561 __r->_M_ref_count = 2;
00562 return __r;
00563 }
00564 if (__orig_size + __slen <= _S_copy_max &&
00565 _RopeRep::_S_leaf == __r->_M_tag) {
00566 __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
00567 return __result;
00568 }
00569 if (_RopeRep::_S_concat == __r->_M_tag) {
00570 _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*)__r)->_M_right);
00571 if (_RopeRep::_S_leaf == __right->_M_tag
00572 && __right->_M_size + __slen <= _S_copy_max) {
00573 _RopeRep* __new_right =
00574 _S_destr_leaf_concat_char_iter(__right, __s, __slen);
00575 if (__right == __new_right)
00576 __new_right->_M_ref_count = 1;
00577 else
00578 __right->_M_unref_nonnil();
00579 __r->_M_ref_count = 2;
00580 ((_RopeConcatenation*)__r)->_M_right = __new_right;
00581 __r->_M_size = __orig_size + __slen;
00582 if (0 != __r->_M_c_string) {
00583 __r->_M_free_c_string();
00584 __r->_M_c_string = 0;
00585 }
00586 return __r;
00587 }
00588 }
00589 _RopeRep* __right =
00590 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator());
00591 __r->_M_ref_nonnil();
00592 try {
00593 __result = _S_tree_concat(__r, __right);
00594 }
00595 catch(...)
00596 {
00597 _S_unref(__r);
00598 _S_unref(__right);
00599 __throw_exception_again;
00600 }
00601 return __result;
00602 }
00603 #endif
00604
00605 template <class _CharT, class _Alloc>
00606 typename rope<_CharT,_Alloc>::_RopeRep*
00607 rope<_CharT,_Alloc>::_S_concat(_RopeRep* __left, _RopeRep* __right)
00608 {
00609 if (0 == __left) {
00610 _S_ref(__right);
00611 return __right;
00612 }
00613 if (0 == __right) {
00614 __left->_M_ref_nonnil();
00615 return __left;
00616 }
00617 if (_RopeRep::_S_leaf == __right->_M_tag) {
00618 if (_RopeRep::_S_leaf == __left->_M_tag) {
00619 if (__right->_M_size + __left->_M_size <= _S_copy_max) {
00620 return _S_leaf_concat_char_iter((_RopeLeaf*)__left,
00621 ((_RopeLeaf*)__right)->_M_data,
00622 __right->_M_size);
00623 }
00624 } else if (_RopeRep::_S_concat == __left->_M_tag
00625 && _RopeRep::_S_leaf ==
00626 ((_RopeConcatenation*)__left)->_M_right->_M_tag) {
00627 _RopeLeaf* __leftright =
00628 (_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right);
00629 if (__leftright->_M_size + __right->_M_size <= _S_copy_max) {
00630 _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left;
00631 _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright,
00632 ((_RopeLeaf*)__right)->_M_data,
00633 __right->_M_size);
00634 __leftleft->_M_ref_nonnil();
00635 try {
00636 return(_S_tree_concat(__leftleft, __rest));
00637 }
00638 catch(...)
00639 {
00640 _S_unref(__leftleft);
00641 _S_unref(__rest);
00642 __throw_exception_again;
00643 }
00644 }
00645 }
00646 }
00647 __left->_M_ref_nonnil();
00648 __right->_M_ref_nonnil();
00649 try {
00650 return(_S_tree_concat(__left, __right));
00651 }
00652 catch(...)
00653 {
00654 _S_unref(__left);
00655 _S_unref(__right);
00656 __throw_exception_again;
00657 }
00658 }
00659
00660 template <class _CharT, class _Alloc>
00661 typename rope<_CharT,_Alloc>::_RopeRep*
00662 rope<_CharT,_Alloc>::_S_substring(_RopeRep* __base,
00663 size_t __start, size_t __endp1)
00664 {
00665 if (0 == __base) return 0;
00666 size_t __len = __base->_M_size;
00667 size_t __adj_endp1;
00668 const size_t __lazy_threshold = 128;
00669
00670 if (__endp1 >= __len) {
00671 if (0 == __start) {
00672 __base->_M_ref_nonnil();
00673 return __base;
00674 } else {
00675 __adj_endp1 = __len;
00676 }
00677 } else {
00678 __adj_endp1 = __endp1;
00679 }
00680 switch(__base->_M_tag) {
00681 case _RopeRep::_S_concat:
00682 {
00683 _RopeConcatenation* __c = (_RopeConcatenation*)__base;
00684 _RopeRep* __left = __c->_M_left;
00685 _RopeRep* __right = __c->_M_right;
00686 size_t __left_len = __left->_M_size;
00687 _RopeRep* __result;
00688
00689 if (__adj_endp1 <= __left_len) {
00690 return _S_substring(__left, __start, __endp1);
00691 } else if (__start >= __left_len) {
00692 return _S_substring(__right, __start - __left_len,
00693 __adj_endp1 - __left_len);
00694 }
00695 _Self_destruct_ptr __left_result(
00696 _S_substring(__left, __start, __left_len));
00697 _Self_destruct_ptr __right_result(
00698 _S_substring(__right, 0, __endp1 - __left_len));
00699 __result = _S_concat(__left_result, __right_result);
00700 return __result;
00701 }
00702 case _RopeRep::_S_leaf:
00703 {
00704 _RopeLeaf* __l = (_RopeLeaf*)__base;
00705 _RopeLeaf* __result;
00706 size_t __result_len;
00707 if (__start >= __adj_endp1) return 0;
00708 __result_len = __adj_endp1 - __start;
00709 if (__result_len > __lazy_threshold) goto lazy;
00710 # ifdef __GC
00711 const _CharT* __section = __l->_M_data + __start;
00712 __result = _S_new_RopeLeaf(__section, __result_len,
00713 __base->get_allocator());
00714 __result->_M_c_string = 0;
00715 # else
00716
00717 __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(
00718 __l->_M_data + __start, __result_len,
00719 __base->get_allocator());
00720 # endif
00721 return __result;
00722 }
00723 case _RopeRep::_S_substringfn:
00724
00725 {
00726 _RopeSubstring* __old = (_RopeSubstring*)__base;
00727 size_t __result_len;
00728 if (__start >= __adj_endp1) return 0;
00729 __result_len = __adj_endp1 - __start;
00730 if (__result_len > __lazy_threshold) {
00731 _RopeSubstring* __result =
00732 _S_new_RopeSubstring(__old->_M_base,
00733 __start + __old->_M_start,
00734 __adj_endp1 - __start,
00735 __base->get_allocator());
00736 return __result;
00737
00738 }
00739 }
00740 case _RopeRep::_S_function:
00741 {
00742 _RopeFunction* __f = (_RopeFunction*)__base;
00743 _CharT* __section;
00744 size_t __result_len;
00745 if (__start >= __adj_endp1) return 0;
00746 __result_len = __adj_endp1 - __start;
00747
00748 if (__result_len > __lazy_threshold) goto lazy;
00749 __section = (_CharT*)
00750 _Data_allocate(_S_rounded_up_size(__result_len));
00751 try {
00752 (*(__f->_M_fn))(__start, __result_len, __section);
00753 }
00754 catch(...)
00755 {
00756 _RopeRep::__STL_FREE_STRING(
00757 __section, __result_len, __base->get_allocator());
00758 __throw_exception_again;
00759 }
00760 _S_cond_store_eos(__section[__result_len]);
00761 return _S_new_RopeLeaf(__section, __result_len,
00762 __base->get_allocator());
00763 }
00764 }
00765 lazy:
00766 {
00767
00768 return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start,
00769 __base->get_allocator());
00770 }
00771 }
00772
00773 template<class _CharT>
00774 class _Rope_flatten_char_consumer : public _Rope_char_consumer<_CharT> {
00775 private:
00776 _CharT* _M_buf_ptr;
00777 public:
00778
00779 _Rope_flatten_char_consumer(_CharT* __buffer) {
00780 _M_buf_ptr = __buffer;
00781 };
00782 ~_Rope_flatten_char_consumer() {}
00783 bool operator() (const _CharT* __leaf, size_t __n) {
00784 uninitialized_copy_n(__leaf, __n, _M_buf_ptr);
00785 _M_buf_ptr += __n;
00786 return true;
00787 }
00788 };
00789
00790 template<class _CharT>
00791 class _Rope_find_char_char_consumer : public _Rope_char_consumer<_CharT> {
00792 private:
00793 _CharT _M_pattern;
00794 public:
00795 size_t _M_count;
00796 _Rope_find_char_char_consumer(_CharT __p)
00797 : _M_pattern(__p), _M_count(0) {}
00798 ~_Rope_find_char_char_consumer() {}
00799 bool operator() (const _CharT* __leaf, size_t __n) {
00800 size_t __i;
00801 for (__i = 0; __i < __n; __i++) {
00802 if (__leaf[__i] == _M_pattern) {
00803 _M_count += __i; return false;
00804 }
00805 }
00806 _M_count += __n; return true;
00807 }
00808 };
00809
00810 template<class _CharT, class _Traits>
00811
00812 class _Rope_insert_char_consumer : public _Rope_char_consumer<_CharT> {
00813 private:
00814 typedef basic_ostream<_CharT,_Traits> _Insert_ostream;
00815 _Insert_ostream& _M_o;
00816 public:
00817 _Rope_insert_char_consumer(_Insert_ostream& __writer)
00818 : _M_o(__writer) {};
00819 ~_Rope_insert_char_consumer() { };
00820
00821 bool operator() (const _CharT* __leaf, size_t __n);
00822
00823 };
00824
00825 template<class _CharT, class _Traits>
00826 bool _Rope_insert_char_consumer<_CharT, _Traits>::operator()
00827 (const _CharT* __leaf, size_t __n)
00828 {
00829 size_t __i;
00830
00831 for (__i = 0; __i < __n; __i++) _M_o.put(__leaf[__i]);
00832 return true;
00833 }
00834
00835 template <class _CharT, class _Alloc>
00836 bool rope<_CharT, _Alloc>::_S_apply_to_pieces(
00837 _Rope_char_consumer<_CharT>& __c,
00838 const _RopeRep* __r,
00839 size_t __begin, size_t __end)
00840 {
00841 if (0 == __r) return true;
00842 switch(__r->_M_tag) {
00843 case _RopeRep::_S_concat:
00844 {
00845 _RopeConcatenation* __conc = (_RopeConcatenation*)__r;
00846 _RopeRep* __left = __conc->_M_left;
00847 size_t __left_len = __left->_M_size;
00848 if (__begin < __left_len) {
00849 size_t __left_end = std::min(__left_len, __end);
00850 if (!_S_apply_to_pieces(__c, __left, __begin, __left_end))
00851 return false;
00852 }
00853 if (__end > __left_len) {
00854 _RopeRep* __right = __conc->_M_right;
00855 size_t __right_start = std::max(__left_len, __begin);
00856 if (!_S_apply_to_pieces(__c, __right,
00857 __right_start - __left_len,
00858 __end - __left_len)) {
00859 return false;
00860 }
00861 }
00862 }
00863 return true;
00864 case _RopeRep::_S_leaf:
00865 {
00866 _RopeLeaf* __l = (_RopeLeaf*)__r;
00867 return __c(__l->_M_data + __begin, __end - __begin);
00868 }
00869 case _RopeRep::_S_function:
00870 case _RopeRep::_S_substringfn:
00871 {
00872 _RopeFunction* __f = (_RopeFunction*)__r;
00873 size_t __len = __end - __begin;
00874 bool __result;
00875 _CharT* __buffer =
00876 (_CharT*)__alloc::allocate(__len * sizeof(_CharT));
00877 try {
00878 (*(__f->_M_fn))(__begin, __len, __buffer);
00879 __result = __c(__buffer, __len);
00880 __alloc::deallocate(__buffer, __len * sizeof(_CharT));
00881 }
00882 catch(...)
00883 {
00884 __alloc::deallocate(__buffer, __len * sizeof(_CharT));
00885 __throw_exception_again;
00886 }
00887 return __result;
00888 }
00889 default:
00890 return false;
00891 }
00892 }
00893
00894 template<class _CharT, class _Traits>
00895 inline void _Rope_fill(basic_ostream<_CharT, _Traits>& __o, size_t __n)
00896 {
00897 char __f = __o.fill();
00898 size_t __i;
00899
00900 for (__i = 0; __i < __n; __i++) __o.put(__f);
00901 }
00902
00903
00904 template <class _CharT> inline bool _Rope_is_simple(_CharT*) { return false; }
00905 inline bool _Rope_is_simple(char*) { return true; }
00906 inline bool _Rope_is_simple(wchar_t*) { return true; }
00907
00908 template<class _CharT, class _Traits, class _Alloc>
00909 basic_ostream<_CharT, _Traits>& operator<< (basic_ostream<_CharT, _Traits>& __o,
00910 const rope<_CharT, _Alloc>& __r)
00911 {
00912 size_t __w = __o.width();
00913 bool __left = bool(__o.flags() & std::ios::left);
00914 size_t __pad_len;
00915 size_t __rope_len = __r.size();
00916 _Rope_insert_char_consumer<_CharT, _Traits> __c(__o);
00917 bool __is_simple = _Rope_is_simple((_CharT*)0);
00918
00919 if (__rope_len < __w) {
00920 __pad_len = __w - __rope_len;
00921 } else {
00922 __pad_len = 0;
00923 }
00924 if (!__is_simple) __o.width(__w/__rope_len);
00925 try {
00926 if (__is_simple && !__left && __pad_len > 0) {
00927 _Rope_fill(__o, __pad_len);
00928 }
00929 __r.apply_to_pieces(0, __r.size(), __c);
00930 if (__is_simple && __left && __pad_len > 0) {
00931 _Rope_fill(__o, __pad_len);
00932 }
00933 if (!__is_simple)
00934 __o.width(__w);
00935 }
00936 catch(...)
00937 {
00938 if (!__is_simple)
00939 __o.width(__w);
00940 __throw_exception_again;
00941 }
00942 return __o;
00943 }
00944
00945 template <class _CharT, class _Alloc>
00946 _CharT*
00947 rope<_CharT,_Alloc>::_S_flatten(_RopeRep* __r,
00948 size_t __start, size_t __len,
00949 _CharT* __buffer)
00950 {
00951 _Rope_flatten_char_consumer<_CharT> __c(__buffer);
00952 _S_apply_to_pieces(__c, __r, __start, __start + __len);
00953 return(__buffer + __len);
00954 }
00955
00956 template <class _CharT, class _Alloc>
00957 size_t
00958 rope<_CharT,_Alloc>::find(_CharT __pattern, size_t __start) const
00959 {
00960 _Rope_find_char_char_consumer<_CharT> __c(__pattern);
00961 _S_apply_to_pieces(__c, _M_tree_ptr, __start, size());
00962 size_type __result_pos = __start + __c._M_count;
00963 # ifndef __STL_OLD_ROPE_SEMANTICS
00964 if (__result_pos == size()) __result_pos = npos;
00965 # endif
00966 return __result_pos;
00967 }
00968
00969 template <class _CharT, class _Alloc>
00970 _CharT*
00971 rope<_CharT,_Alloc>::_S_flatten(_RopeRep* __r, _CharT* __buffer)
00972 {
00973 if (0 == __r) return __buffer;
00974 switch(__r->_M_tag) {
00975 case _RopeRep::_S_concat:
00976 {
00977 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
00978 _RopeRep* __left = __c->_M_left;
00979 _RopeRep* __right = __c->_M_right;
00980 _CharT* __rest = _S_flatten(__left, __buffer);
00981 return _S_flatten(__right, __rest);
00982 }
00983 case _RopeRep::_S_leaf:
00984 {
00985 _RopeLeaf* __l = (_RopeLeaf*)__r;
00986 return copy_n(__l->_M_data, __l->_M_size, __buffer).second;
00987 }
00988 case _RopeRep::_S_function:
00989 case _RopeRep::_S_substringfn:
00990
00991
00992 {
00993 _RopeFunction* __f = (_RopeFunction*)__r;
00994 (*(__f->_M_fn))(0, __f->_M_size, __buffer);
00995 return __buffer + __f->_M_size;
00996 }
00997 default:
00998 return 0;
00999 }
01000 }
01001
01002
01003
01004 template <class _CharT, class _Alloc>
01005 void
01006 rope<_CharT,_Alloc>::_S_dump(_RopeRep* __r, int __indent)
01007 {
01008 for (int __i = 0; __i < __indent; __i++) putchar(' ');
01009 if (0 == __r) {
01010 printf("NULL\n"); return;
01011 }
01012 if (_RopeRep::_S_concat == __r->_M_tag) {
01013 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
01014 _RopeRep* __left = __c->_M_left;
01015 _RopeRep* __right = __c->_M_right;
01016
01017 # ifdef __GC
01018 printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
01019 __r, __r->_M_depth, __r->_M_size, __r->_M_is_balanced? "" : "not");
01020 # else
01021 printf("Concatenation %p (rc = %ld, depth = %d, "
01022 "len = %ld, %s balanced)\n",
01023 __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size,
01024 __r->_M_is_balanced? "" : "not");
01025 # endif
01026 _S_dump(__left, __indent + 2);
01027 _S_dump(__right, __indent + 2);
01028 return;
01029 } else {
01030 char* __kind;
01031
01032 switch (__r->_M_tag) {
01033 case _RopeRep::_S_leaf:
01034 __kind = "Leaf";
01035 break;
01036 case _RopeRep::_S_function:
01037 __kind = "Function";
01038 break;
01039 case _RopeRep::_S_substringfn:
01040 __kind = "Function representing substring";
01041 break;
01042 default:
01043 __kind = "(corrupted kind field!)";
01044 }
01045 # ifdef __GC
01046 printf("%s %p (depth = %d, len = %ld) ",
01047 __kind, __r, __r->_M_depth, __r->_M_size);
01048 # else
01049 printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
01050 __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size);
01051 # endif
01052 if (_S_is_one_byte_char_type((_CharT*)0)) {
01053 const int __max_len = 40;
01054 _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len));
01055 _CharT __buffer[__max_len + 1];
01056 bool __too_big = __r->_M_size > __prefix->_M_size;
01057
01058 _S_flatten(__prefix, __buffer);
01059 __buffer[__prefix->_M_size] = _S_eos((_CharT*)0);
01060 printf("%s%s\n",
01061 (char*)__buffer, __too_big? "...\n" : "\n");
01062 } else {
01063 printf("\n");
01064 }
01065 }
01066 }
01067
01068 template <class _CharT, class _Alloc>
01069 const unsigned long
01070 rope<_CharT,_Alloc>::_S_min_len[
01071 _Rope_RopeRep<_CharT,_Alloc>::_S_max_rope_depth + 1] = {
01072 1, 2, 3, 5, 8, 13, 21,
01073 34, 55, 89, 144, 233, 377,
01074 610, 987, 1597, 2584, 4181,
01075 6765, 10946, 17711, 28657, 46368,
01076 75025, 121393, 196418, 317811,
01077 514229, 832040, 1346269, 2178309,
01078 3524578, 5702887, 9227465, 14930352,
01079 24157817, 39088169, 63245986, 102334155,
01080 165580141, 267914296, 433494437,
01081 701408733, 1134903170, 1836311903,
01082 2971215073u };
01083
01084
01085 template <class _CharT, class _Alloc>
01086 typename rope<_CharT,_Alloc>::_RopeRep*
01087 rope<_CharT,_Alloc>::_S_balance(_RopeRep* __r)
01088 {
01089 _RopeRep* __forest[_RopeRep::_S_max_rope_depth + 1];
01090 _RopeRep* __result = 0;
01091 int __i;
01092
01093
01094
01095
01096
01097
01098 for (__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i)
01099 __forest[__i] = 0;
01100 try {
01101 _S_add_to_forest(__r, __forest);
01102 for (__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i)
01103 if (0 != __forest[__i]) {
01104 # ifndef __GC
01105 _Self_destruct_ptr __old(__result);
01106 # endif
01107 __result = _S_concat(__forest[__i], __result);
01108 __forest[__i]->_M_unref_nonnil();
01109 # if !defined(__GC) && defined(__EXCEPTIONS)
01110 __forest[__i] = 0;
01111 # endif
01112 }
01113 }
01114 catch(...)
01115 {
01116 for(__i = 0; __i <= _RopeRep::_S_max_rope_depth; __i++)
01117 _S_unref(__forest[__i]);
01118 __throw_exception_again;
01119 }
01120
01121 if (__result->_M_depth > _RopeRep::_S_max_rope_depth)
01122 __throw_length_error("rope too long");
01123 return(__result);
01124 }
01125
01126
01127 template <class _CharT, class _Alloc>
01128 void
01129 rope<_CharT,_Alloc>::_S_add_to_forest(_RopeRep* __r, _RopeRep** __forest)
01130 {
01131 if (__r->_M_is_balanced) {
01132 _S_add_leaf_to_forest(__r, __forest);
01133 return;
01134 }
01135
01136 {
01137 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
01138
01139 _S_add_to_forest(__c->_M_left, __forest);
01140 _S_add_to_forest(__c->_M_right, __forest);
01141 }
01142 }
01143
01144
01145 template <class _CharT, class _Alloc>
01146 void
01147 rope<_CharT,_Alloc>::_S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest)
01148 {
01149 _RopeRep* __insertee;
01150 _RopeRep* __too_tiny = 0;
01151 int __i;
01152 size_t __s = __r->_M_size;
01153
01154 for (__i = 0; __s >= _S_min_len[__i+1]; ++__i) {
01155 if (0 != __forest[__i]) {
01156 # ifndef __GC
01157 _Self_destruct_ptr __old(__too_tiny);
01158 # endif
01159 __too_tiny = _S_concat_and_set_balanced(__forest[__i], __too_tiny);
01160 __forest[__i]->_M_unref_nonnil();
01161 __forest[__i] = 0;
01162 }
01163 }
01164 {
01165 # ifndef __GC
01166 _Self_destruct_ptr __old(__too_tiny);
01167 # endif
01168 __insertee = _S_concat_and_set_balanced(__too_tiny, __r);
01169 }
01170
01171
01172 for (;; ++__i) {
01173 if (0 != __forest[__i]) {
01174 # ifndef __GC
01175 _Self_destruct_ptr __old(__insertee);
01176 # endif
01177 __insertee = _S_concat_and_set_balanced(__forest[__i], __insertee);
01178 __forest[__i]->_M_unref_nonnil();
01179 __forest[__i] = 0;
01180 }
01181 if (__i == _RopeRep::_S_max_rope_depth ||
01182 __insertee->_M_size < _S_min_len[__i+1]) {
01183 __forest[__i] = __insertee;
01184
01185 return;
01186 }
01187 }
01188 }
01189
01190 template <class _CharT, class _Alloc>
01191 _CharT
01192 rope<_CharT,_Alloc>::_S_fetch(_RopeRep* __r, size_type __i)
01193 {
01194 __GC_CONST _CharT* __cstr = __r->_M_c_string;
01195
01196 if (0 != __cstr) return __cstr[__i];
01197 for(;;) {
01198 switch(__r->_M_tag) {
01199 case _RopeRep::_S_concat:
01200 {
01201 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
01202 _RopeRep* __left = __c->_M_left;
01203 size_t __left_len = __left->_M_size;
01204
01205 if (__i >= __left_len) {
01206 __i -= __left_len;
01207 __r = __c->_M_right;
01208 } else {
01209 __r = __left;
01210 }
01211 }
01212 break;
01213 case _RopeRep::_S_leaf:
01214 {
01215 _RopeLeaf* __l = (_RopeLeaf*)__r;
01216 return __l->_M_data[__i];
01217 }
01218 case _RopeRep::_S_function:
01219 case _RopeRep::_S_substringfn:
01220 {
01221 _RopeFunction* __f = (_RopeFunction*)__r;
01222 _CharT __result;
01223
01224 (*(__f->_M_fn))(__i, 1, &__result);
01225 return __result;
01226 }
01227 }
01228 }
01229 }
01230
01231 # ifndef __GC
01232
01233
01234 template <class _CharT, class _Alloc>
01235 _CharT*
01236 rope<_CharT,_Alloc>::_S_fetch_ptr(_RopeRep* __r, size_type __i)
01237 {
01238 _RopeRep* __clrstack[_RopeRep::_S_max_rope_depth];
01239 size_t __csptr = 0;
01240
01241 for(;;) {
01242 if (__r->_M_ref_count > 1) return 0;
01243 switch(__r->_M_tag) {
01244 case _RopeRep::_S_concat:
01245 {
01246 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
01247 _RopeRep* __left = __c->_M_left;
01248 size_t __left_len = __left->_M_size;
01249
01250 if (__c->_M_c_string != 0) __clrstack[__csptr++] = __c;
01251 if (__i >= __left_len) {
01252 __i -= __left_len;
01253 __r = __c->_M_right;
01254 } else {
01255 __r = __left;
01256 }
01257 }
01258 break;
01259 case _RopeRep::_S_leaf:
01260 {
01261 _RopeLeaf* __l = (_RopeLeaf*)__r;
01262 if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0)
01263 __clrstack[__csptr++] = __l;
01264 while (__csptr > 0) {
01265 -- __csptr;
01266 _RopeRep* __d = __clrstack[__csptr];
01267 __d->_M_free_c_string();
01268 __d->_M_c_string = 0;
01269 }
01270 return __l->_M_data + __i;
01271 }
01272 case _RopeRep::_S_function:
01273 case _RopeRep::_S_substringfn:
01274 return 0;
01275 }
01276 }
01277 }
01278 # endif
01279
01280
01281
01282
01283
01284 template <class _CharT, class _Alloc>
01285 int
01286 rope<_CharT,_Alloc>::_S_compare (const _RopeRep* __left,
01287 const _RopeRep* __right)
01288 {
01289 size_t __left_len;
01290 size_t __right_len;
01291
01292 if (0 == __right) return 0 != __left;
01293 if (0 == __left) return -1;
01294 __left_len = __left->_M_size;
01295 __right_len = __right->_M_size;
01296 if (_RopeRep::_S_leaf == __left->_M_tag) {
01297 _RopeLeaf* __l = (_RopeLeaf*) __left;
01298 if (_RopeRep::_S_leaf == __right->_M_tag) {
01299 _RopeLeaf* __r = (_RopeLeaf*) __right;
01300 return lexicographical_compare_3way(
01301 __l->_M_data, __l->_M_data + __left_len,
01302 __r->_M_data, __r->_M_data + __right_len);
01303 } else {
01304 const_iterator __rstart(__right, 0);
01305 const_iterator __rend(__right, __right_len);
01306 return lexicographical_compare_3way(
01307 __l->_M_data, __l->_M_data + __left_len,
01308 __rstart, __rend);
01309 }
01310 } else {
01311 const_iterator __lstart(__left, 0);
01312 const_iterator __lend(__left, __left_len);
01313 if (_RopeRep::_S_leaf == __right->_M_tag) {
01314 _RopeLeaf* __r = (_RopeLeaf*) __right;
01315 return lexicographical_compare_3way(
01316 __lstart, __lend,
01317 __r->_M_data, __r->_M_data + __right_len);
01318 } else {
01319 const_iterator __rstart(__right, 0);
01320 const_iterator __rend(__right, __right_len);
01321 return lexicographical_compare_3way(
01322 __lstart, __lend,
01323 __rstart, __rend);
01324 }
01325 }
01326 }
01327
01328
01329 template <class _CharT, class _Alloc>
01330 _Rope_char_ref_proxy<_CharT, _Alloc>&
01331 _Rope_char_ref_proxy<_CharT, _Alloc>::operator= (_CharT __c) {
01332 _RopeRep* __old = _M_root->_M_tree_ptr;
01333 # ifndef __GC
01334
01335
01336 _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos);
01337 if (0 != __ptr) {
01338 *__ptr = __c;
01339 return *this;
01340 }
01341 # endif
01342 _Self_destruct_ptr __left(
01343 _My_rope::_S_substring(__old, 0, _M_pos));
01344 _Self_destruct_ptr __right(
01345 _My_rope::_S_substring(__old, _M_pos+1, __old->_M_size));
01346 _Self_destruct_ptr __result_left(
01347 _My_rope::_S_destr_concat_char_iter(__left, &__c, 1));
01348
01349 _RopeRep* __result =
01350 _My_rope::_S_concat(__result_left, __right);
01351 # ifndef __GC
01352 _RopeRep::_S_unref(__old);
01353 # endif
01354 _M_root->_M_tree_ptr = __result;
01355 return *this;
01356 }
01357
01358 template <class _CharT, class _Alloc>
01359 inline _Rope_char_ref_proxy<_CharT, _Alloc>::operator _CharT () const
01360 {
01361 if (_M_current_valid) {
01362 return _M_current;
01363 } else {
01364 return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos);
01365 }
01366 }
01367 template <class _CharT, class _Alloc>
01368 _Rope_char_ptr_proxy<_CharT, _Alloc>
01369 _Rope_char_ref_proxy<_CharT, _Alloc>::operator& () const {
01370 return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this);
01371 }
01372
01373 template <class _CharT, class _Alloc>
01374 rope<_CharT, _Alloc>::rope(size_t __n, _CharT __c,
01375 const allocator_type& __a)
01376 : _Base(__a)
01377 {
01378 rope<_CharT,_Alloc> __result;
01379 const size_t __exponentiate_threshold = 32;
01380 size_t __exponent;
01381 size_t __rest;
01382 _CharT* __rest_buffer;
01383 _RopeRep* __remainder;
01384 rope<_CharT,_Alloc> __remainder_rope;
01385
01386 if (0 == __n)
01387 return;
01388
01389 __exponent = __n / __exponentiate_threshold;
01390 __rest = __n % __exponentiate_threshold;
01391 if (0 == __rest) {
01392 __remainder = 0;
01393 } else {
01394 __rest_buffer = _Data_allocate(_S_rounded_up_size(__rest));
01395 uninitialized_fill_n(__rest_buffer, __rest, __c);
01396 _S_cond_store_eos(__rest_buffer[__rest]);
01397 try {
01398 __remainder = _S_new_RopeLeaf(__rest_buffer, __rest, __a);
01399 }
01400 catch(...)
01401 {
01402 _RopeRep::__STL_FREE_STRING(__rest_buffer, __rest, __a);
01403 __throw_exception_again;
01404 }
01405 }
01406 __remainder_rope._M_tree_ptr = __remainder;
01407 if (__exponent != 0) {
01408 _CharT* __base_buffer =
01409 _Data_allocate(_S_rounded_up_size(__exponentiate_threshold));
01410 _RopeLeaf* __base_leaf;
01411 rope __base_rope;
01412 uninitialized_fill_n(__base_buffer, __exponentiate_threshold, __c);
01413 _S_cond_store_eos(__base_buffer[__exponentiate_threshold]);
01414 try {
01415 __base_leaf = _S_new_RopeLeaf(__base_buffer,
01416 __exponentiate_threshold, __a);
01417 }
01418 catch(...)
01419 {
01420 _RopeRep::__STL_FREE_STRING(__base_buffer,
01421 __exponentiate_threshold, __a);
01422 __throw_exception_again;
01423 }
01424 __base_rope._M_tree_ptr = __base_leaf;
01425 if (1 == __exponent) {
01426 __result = __base_rope;
01427 } else {
01428 __result = power(__base_rope, __exponent,
01429 _Rope_Concat_fn<_CharT,_Alloc>());
01430 }
01431 if (0 != __remainder) {
01432 __result += __remainder_rope;
01433 }
01434 } else {
01435 __result = __remainder_rope;
01436 }
01437 _M_tree_ptr = __result._M_tree_ptr;
01438 _M_tree_ptr->_M_ref_nonnil();
01439 }
01440
01441 template<class _CharT, class _Alloc>
01442 _CharT rope<_CharT,_Alloc>::_S_empty_c_str[1];
01443
01444 template<class _CharT, class _Alloc>
01445 const _CharT* rope<_CharT,_Alloc>::c_str() const {
01446 if (0 == _M_tree_ptr) {
01447 _S_empty_c_str[0] = _S_eos((_CharT*)0);
01448
01449 return _S_empty_c_str;
01450 }
01451 __GC_CONST _CharT* __old_c_string = _M_tree_ptr->_M_c_string;
01452 if (0 != __old_c_string) return(__old_c_string);
01453 size_t __s = size();
01454 _CharT* __result = _Data_allocate(__s + 1);
01455 _S_flatten(_M_tree_ptr, __result);
01456 __result[__s] = _S_eos((_CharT*)0);
01457 # ifdef __GC
01458 _M_tree_ptr->_M_c_string = __result;
01459 # else
01460 if ((__old_c_string = (__GC_CONST _CharT*)
01461 std::_Atomic_swap((unsigned long *)(&(_M_tree_ptr->_M_c_string)),
01462 (unsigned long)__result)) != 0) {
01463
01464
01465
01466 _Destroy(__old_c_string, __old_c_string + __s + 1);
01467 _Data_deallocate(__old_c_string, __s + 1);
01468 }
01469 # endif
01470 return(__result);
01471 }
01472
01473 template<class _CharT, class _Alloc>
01474 const _CharT* rope<_CharT,_Alloc>::replace_with_c_str() {
01475 if (0 == _M_tree_ptr) {
01476 _S_empty_c_str[0] = _S_eos((_CharT*)0);
01477 return _S_empty_c_str;
01478 }
01479 __GC_CONST _CharT* __old_c_string = _M_tree_ptr->_M_c_string;
01480 if (_RopeRep::_S_leaf == _M_tree_ptr->_M_tag && 0 != __old_c_string) {
01481 return(__old_c_string);
01482 }
01483 size_t __s = size();
01484 _CharT* __result = _Data_allocate(_S_rounded_up_size(__s));
01485 _S_flatten(_M_tree_ptr, __result);
01486 __result[__s] = _S_eos((_CharT*)0);
01487 _M_tree_ptr->_M_unref_nonnil();
01488 _M_tree_ptr = _S_new_RopeLeaf(__result, __s, get_allocator());
01489 return(__result);
01490 }
01491
01492
01493
01494 template<class _Rope_iterator>
01495 void
01496 _Rope_rotate(_Rope_iterator __first,
01497 _Rope_iterator __middle,
01498 _Rope_iterator __last)
01499 {
01500 typedef typename _Rope_iterator::value_type _CharT;
01501 typedef typename _Rope_iterator::_allocator_type _Alloc;
01502
01503 rope<_CharT,_Alloc>& __r(__first.container());
01504 rope<_CharT,_Alloc> __prefix = __r.substr(0, __first.index());
01505 rope<_CharT,_Alloc> __suffix =
01506 __r.substr(__last.index(), __r.size() - __last.index());
01507 rope<_CharT,_Alloc> __part1 =
01508 __r.substr(__middle.index(), __last.index() - __middle.index());
01509 rope<_CharT,_Alloc> __part2 =
01510 __r.substr(__first.index(), __middle.index() - __first.index());
01511 __r = __prefix;
01512 __r += __part1;
01513 __r += __part2;
01514 __r += __suffix;
01515 }
01516
01517 #if !defined(__GNUC__)
01518
01519 inline void rotate(_Rope_iterator<char,__STL_DEFAULT_ALLOCATOR(char)> __first,
01520 _Rope_iterator<char,__STL_DEFAULT_ALLOCATOR(char)> __middle,
01521 _Rope_iterator<char,__STL_DEFAULT_ALLOCATOR(char)> __last) {
01522 _Rope_rotate(__first, __middle, __last);
01523 }
01524 #endif
01525
01526 # if 0
01527
01528
01529
01530
01531
01532
01533
01534 inline void rotate(
01535 _Rope_iterator<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __first,
01536 _Rope_iterator<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __middle,
01537 _Rope_iterator<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __last) {
01538 _Rope_rotate(__first, __middle, __last);
01539 }
01540 # endif
01541
01542 }
01543
01544
01545
01546
01547