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