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