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