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