52 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
56 using std::basic_ostream;
57 using std::__throw_length_error;
65 template <class _CharT, class _Alloc>
67 _Rope_iterator_base<_CharT, _Alloc>::
68 _S_setbuf(_Rope_iterator_base<_CharT, _Alloc>& __x)
70 const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index];
71 size_t __leaf_pos = __x._M_leaf_pos;
72 size_t __pos = __x._M_current_pos;
74 switch(__leaf->_M_tag)
76 case __detail::_S_leaf:
77 __x._M_buf_start = ((_Rope_RopeLeaf<_CharT, _Alloc>*)__leaf)->_M_data;
78 __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos);
79 __x._M_buf_end = __x._M_buf_start + __leaf->_M_size;
81 case __detail::_S_function:
82 case __detail::_S_substringfn:
84 size_t __len = _S_iterator_buf_len;
85 size_t __buf_start_pos = __leaf_pos;
86 size_t __leaf_end = __leaf_pos + __leaf->_M_size;
87 char_producer<_CharT>* __fn = ((_Rope_RopeFunction<_CharT,
88 _Alloc>*)__leaf)->_M_fn;
89 if (__buf_start_pos + __len <= __pos)
91 __buf_start_pos = __pos - __len / 4;
92 if (__buf_start_pos + __len > __leaf_end)
93 __buf_start_pos = __leaf_end - __len;
95 if (__buf_start_pos + __len > __leaf_end)
96 __len = __leaf_end - __buf_start_pos;
97 (*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf);
98 __x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos);
99 __x._M_buf_start = __x._M_tmp_buf;
100 __x._M_buf_end = __x._M_tmp_buf + __len;
110 template <
class _CharT,
class _Alloc>
112 _Rope_iterator_base<_CharT, _Alloc>::
113 _S_setcache(_Rope_iterator_base<_CharT, _Alloc>& __x)
115 const _RopeRep* __path[int(__detail::_S_max_rope_depth) + 1];
116 const _RopeRep* __curr_rope;
117 int __curr_depth = -1;
118 size_t __curr_start_pos = 0;
119 size_t __pos = __x._M_current_pos;
120 unsigned char __dirns = 0;
122 if (__pos >= __x._M_root->_M_size)
127 __curr_rope = __x._M_root;
128 if (0 != __curr_rope->_M_c_string)
131 __x._M_buf_start = __curr_rope->_M_c_string;
132 __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size;
133 __x._M_buf_ptr = __curr_rope->_M_c_string + __pos;
134 __x._M_path_end[0] = __curr_rope;
135 __x._M_leaf_index = 0;
142 __path[__curr_depth] = __curr_rope;
143 switch(__curr_rope->_M_tag)
145 case __detail::_S_leaf:
146 case __detail::_S_function:
147 case __detail::_S_substringfn:
148 __x._M_leaf_pos = __curr_start_pos;
150 case __detail::_S_concat:
152 _Rope_RopeConcatenation<_CharT, _Alloc>* __c =
153 (_Rope_RopeConcatenation<_CharT, _Alloc>*)__curr_rope;
154 _RopeRep* __left = __c->_M_left;
155 size_t __left_len = __left->_M_size;
158 if (__pos >= __curr_start_pos + __left_len)
161 __curr_rope = __c->_M_right;
162 __curr_start_pos += __left_len;
165 __curr_rope = __left;
174 int __j = __curr_depth + 1 - int(_S_path_cache_len);
176 if (__j < 0) __j = 0;
177 while (__j <= __curr_depth)
178 __x._M_path_end[++__i] = __path[__j++];
179 __x._M_leaf_index = __i;
181 __x._M_path_directions = __dirns;
187 template <
class _CharT,
class _Alloc>
189 _Rope_iterator_base<_CharT, _Alloc>::
190 _S_setcache_for_incr(_Rope_iterator_base<_CharT, _Alloc>& __x)
192 int __current_index = __x._M_leaf_index;
193 const _RopeRep* __current_node = __x._M_path_end[__current_index];
194 size_t __len = __current_node->_M_size;
195 size_t __node_start_pos = __x._M_leaf_pos;
196 unsigned char __dirns = __x._M_path_directions;
197 _Rope_RopeConcatenation<_CharT, _Alloc>* __c;
199 if (__x._M_current_pos - __node_start_pos < __len)
206 while (--__current_index >= 0)
210 __current_node = __x._M_path_end[__current_index];
211 __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node;
214 __node_start_pos -= __c->_M_left->_M_size;
217 if (__current_index < 0)
223 __current_node = __x._M_path_end[__current_index];
224 __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node;
228 __node_start_pos += __c->_M_left->_M_size;
229 __current_node = __c->_M_right;
230 __x._M_path_end[++__current_index] = __current_node;
232 while (__detail::_S_concat == __current_node->_M_tag)
235 if (
int(_S_path_cache_len) == __current_index)
238 for (__i = 0; __i < int(_S_path_cache_len) - 1; __i++)
239 __x._M_path_end[__i] = __x._M_path_end[__i+1];
243 ((_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node)->_M_left;
244 __x._M_path_end[__current_index] = __current_node;
248 __x._M_leaf_index = __current_index;
249 __x._M_leaf_pos = __node_start_pos;
250 __x._M_path_directions = __dirns;
254 template <
class _CharT,
class _Alloc>
256 _Rope_iterator_base<_CharT, _Alloc>::
259 _M_current_pos += __n;
262 size_t __chars_left = _M_buf_end - _M_buf_ptr;
263 if (__chars_left > __n)
265 else if (__chars_left == __n)
268 _S_setcache_for_incr(*
this);
275 template <
class _CharT,
class _Alloc>
277 _Rope_iterator_base<_CharT, _Alloc>::
282 size_t __chars_left = _M_buf_ptr - _M_buf_start;
283 if (__chars_left >= __n)
288 _M_current_pos -= __n;
291 template <
class _CharT,
class _Alloc>
293 _Rope_iterator<_CharT, _Alloc>::
296 if (_M_root_rope->_M_tree_ptr != this->_M_root)
299 _RopeRep::_S_unref(this->_M_root);
300 this->_M_root = _M_root_rope->_M_tree_ptr;
301 _RopeRep::_S_ref(this->_M_root);
302 this->_M_buf_ptr = 0;
306 template <
class _CharT,
class _Alloc>
308 _Rope_const_iterator<_CharT, _Alloc>::
309 _Rope_const_iterator(
const _Rope_iterator<_CharT, _Alloc>& __x)
310 : _Rope_iterator_base<_CharT, _Alloc>(__x)
313 template <
class _CharT,
class _Alloc>
315 _Rope_iterator<_CharT, _Alloc>::
316 _Rope_iterator(rope<_CharT, _Alloc>& __r,
size_t __pos)
317 : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos),
319 { _RopeRep::_S_ref(this->_M_root); }
321 template <
class _CharT,
class _Alloc>
323 rope<_CharT, _Alloc>::
324 _S_char_ptr_len(
const _CharT* __s)
326 const _CharT* __p = __s;
328 while (!_S_is0(*__p))
336 template <
class _CharT,
class _Alloc>
338 _Rope_RopeRep<_CharT, _Alloc>::
341 _CharT* __cstr = _M_c_string;
344 size_t __size = this->_M_size + 1;
345 _Destroy(__cstr, __cstr + __size, _M_get_allocator());
346 this->_Data_deallocate(__cstr, __size);
350 template <
class _CharT,
class _Alloc>
352 _Rope_RopeRep<_CharT, _Alloc>::
353 _S_free_string(_CharT* __s,
size_t __n, allocator_type& __a)
355 if (!_S_is_basic_char_type((_CharT*)0))
360 _Rope_RopeLeaf<_CharT, _Alloc>::_S_rounded_up_size(__n));
369 template <
class _CharT,
class _Alloc>
371 _Rope_RopeRep<_CharT, _Alloc>::
376 case __detail::_S_leaf:
378 _Rope_RopeLeaf<_CharT, _Alloc>* __l
379 = (_Rope_RopeLeaf<_CharT, _Alloc>*)
this;
380 __l->_Rope_RopeLeaf<_CharT, _Alloc>::~_Rope_RopeLeaf();
381 _L_deallocate(__l, 1);
384 case __detail::_S_concat:
386 _Rope_RopeConcatenation<_CharT,_Alloc>* __c
387 = (_Rope_RopeConcatenation<_CharT, _Alloc>*)
this;
388 __c->_Rope_RopeConcatenation<_CharT, _Alloc>::
~_Rope_RopeConcatenation();
389 _C_deallocate(__c, 1);
392 case __detail::_S_function:
394 _Rope_RopeFunction<_CharT, _Alloc>* __f
395 = (_Rope_RopeFunction<_CharT, _Alloc>*)
this;
396 __f->_Rope_RopeFunction<_CharT, _Alloc>::~_Rope_RopeFunction();
397 _F_deallocate(__f, 1);
400 case __detail::_S_substringfn:
402 _Rope_RopeSubstring<_CharT, _Alloc>* __ss =
403 (_Rope_RopeSubstring<_CharT, _Alloc>*)
this;
404 __ss->_Rope_RopeSubstring<_CharT, _Alloc>::
~_Rope_RopeSubstring();
405 _S_deallocate(__ss, 1);
412 template <
class _CharT,
class _Alloc>
414 _Rope_RopeRep<_CharT, _Alloc>::
415 _S_free_string(
const _CharT*,
size_t, allocator_type)
422 template <
class _CharT,
class _Alloc>
423 typename rope<_CharT, _Alloc>::_RopeLeaf*
424 rope<_CharT, _Alloc>::
425 _S_leaf_concat_char_iter(_RopeLeaf* __r,
const _CharT* __iter,
size_t __len)
427 size_t __old_len = __r->_M_size;
428 _CharT* __new_data = (_CharT*)
429 _Data_allocate(_S_rounded_up_size(__old_len + __len));
434 _S_cond_store_eos(__new_data[__old_len + __len]);
437 __result = _S_new_RopeLeaf(__new_data, __old_len + __len,
438 __r->_M_get_allocator());
442 _RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len,
443 __r->_M_get_allocator());
444 __throw_exception_again;
451 template <
class _CharT,
class _Alloc>
452 typename rope<_CharT,_Alloc>::_RopeLeaf*
453 rope<_CharT, _Alloc>::
454 _S_destr_leaf_concat_char_iter(_RopeLeaf* __r,
const _CharT* __iter,
457 if (__r->_M_ref_count > 1)
458 return _S_leaf_concat_char_iter(__r, __iter, __len);
459 size_t __old_len = __r->_M_size;
460 if (_S_allocated_capacity(__old_len) >= __old_len + __len)
465 if (_S_is_basic_char_type((_CharT*)0))
466 _S_cond_store_eos(__r->_M_data[__old_len + __len]);
467 else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string)
469 __r->_M_free_c_string();
470 __r->_M_c_string = 0;
472 __r->_M_size = __old_len + __len;
473 __r->_M_ref_count = 2;
478 _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len);
487 template <
class _CharT,
class _Alloc>
488 typename rope<_CharT, _Alloc>::_RopeRep*
489 rope<_CharT, _Alloc>::
490 _S_tree_concat(_RopeRep* __left, _RopeRep* __right)
492 _RopeConcatenation* __result = _S_new_RopeConcatenation(__left, __right,
495 size_t __depth = __result->_M_depth;
498 && (__result->_M_size < 1000
499 || __depth >
size_t(__detail::_S_max_rope_depth)))
501 _RopeRep* __balanced;
505 __balanced = _S_balance(__result);
506 __result->_M_unref_nonnil();
510 _C_deallocate(__result,1);
511 __throw_exception_again;
523 template <
class _CharT,
class _Alloc>
524 typename rope<_CharT, _Alloc>::_RopeRep*
525 rope<_CharT, _Alloc>::
526 _S_concat_char_iter(_RopeRep* __r,
const _CharT*__s,
size_t __slen)
535 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
536 __r->_M_get_allocator());
537 if (__r->_M_tag == __detail::_S_leaf
538 && __r->_M_size + __slen <=
size_t(_S_copy_max))
540 __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
543 if (__detail::_S_concat == __r->_M_tag
544 && __detail::_S_leaf == ((_RopeConcatenation*) __r)->_M_right->_M_tag)
547 (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right);
548 if (__right->_M_size + __slen <=
size_t(_S_copy_max))
550 _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left;
552 _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen);
553 __left->_M_ref_nonnil();
555 { __result = _S_tree_concat(__left, __nright); }
560 __throw_exception_again;
566 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->_M_get_allocator());
569 __r->_M_ref_nonnil();
570 __result = _S_tree_concat(__r, __nright);
576 __throw_exception_again;
582 template <
class _CharT,
class _Alloc>
583 typename rope<_CharT,_Alloc>::_RopeRep*
584 rope<_CharT,_Alloc>::
585 _S_destr_concat_char_iter(_RopeRep* __r,
const _CharT* __s,
size_t __slen)
589 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
590 __r->_M_get_allocator());
591 size_t __count = __r->_M_ref_count;
592 size_t __orig_size = __r->_M_size;
594 return _S_concat_char_iter(__r, __s, __slen);
597 __r->_M_ref_count = 2;
600 if (__orig_size + __slen <=
size_t(_S_copy_max)
601 && __detail::_S_leaf == __r->_M_tag)
603 __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s,
607 if (__detail::_S_concat == __r->_M_tag)
609 _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*)
611 if (__detail::_S_leaf == __right->_M_tag
612 && __right->_M_size + __slen <=
size_t(_S_copy_max))
614 _RopeRep* __new_right =
615 _S_destr_leaf_concat_char_iter(__right, __s, __slen);
616 if (__right == __new_right)
617 __new_right->_M_ref_count = 1;
619 __right->_M_unref_nonnil();
620 __r->_M_ref_count = 2;
621 ((_RopeConcatenation*)__r)->_M_right = __new_right;
622 __r->_M_size = __orig_size + __slen;
623 if (0 != __r->_M_c_string)
625 __r->_M_free_c_string();
626 __r->_M_c_string = 0;
632 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->_M_get_allocator());
633 __r->_M_ref_nonnil();
635 { __result = _S_tree_concat(__r, __right); }
640 __throw_exception_again;
646 template <
class _CharT,
class _Alloc>
647 typename rope<_CharT, _Alloc>::_RopeRep*
648 rope<_CharT, _Alloc>::
649 _S_concat(_RopeRep* __left, _RopeRep* __right)
658 __left->_M_ref_nonnil();
661 if (__detail::_S_leaf == __right->_M_tag)
663 if (__detail::_S_leaf == __left->_M_tag)
665 if (__right->_M_size + __left->_M_size <=
size_t(_S_copy_max))
666 return _S_leaf_concat_char_iter((_RopeLeaf*)__left,
667 ((_RopeLeaf*)__right)->_M_data,
670 else if (__detail::_S_concat == __left->_M_tag
671 && __detail::_S_leaf == ((_RopeConcatenation*)
672 __left)->_M_right->_M_tag)
674 _RopeLeaf* __leftright =
675 (_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right);
676 if (__leftright->_M_size
677 + __right->_M_size <=
size_t(_S_copy_max))
679 _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left;
680 _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright,
685 __leftleft->_M_ref_nonnil();
687 {
return(_S_tree_concat(__leftleft, __rest)); }
690 _S_unref(__leftleft);
692 __throw_exception_again;
697 __left->_M_ref_nonnil();
698 __right->_M_ref_nonnil();
700 {
return(_S_tree_concat(__left, __right)); }
705 __throw_exception_again;
709 template <
class _CharT,
class _Alloc>
710 typename rope<_CharT, _Alloc>::_RopeRep*
711 rope<_CharT, _Alloc>::
712 _S_substring(_RopeRep* __base,
size_t __start,
size_t __endp1)
716 size_t __len = __base->_M_size;
718 const size_t __lazy_threshold = 128;
720 if (__endp1 >= __len)
724 __base->_M_ref_nonnil();
732 __adj_endp1 = __endp1;
734 switch(__base->_M_tag)
736 case __detail::_S_concat:
738 _RopeConcatenation* __c = (_RopeConcatenation*)__base;
739 _RopeRep* __left = __c->_M_left;
740 _RopeRep* __right = __c->_M_right;
741 size_t __left_len = __left->_M_size;
744 if (__adj_endp1 <= __left_len)
745 return _S_substring(__left, __start, __endp1);
746 else if (__start >= __left_len)
747 return _S_substring(__right, __start - __left_len,
748 __adj_endp1 - __left_len);
749 _Self_destruct_ptr __left_result(_S_substring(__left,
752 _Self_destruct_ptr __right_result(_S_substring(__right, 0,
755 __result = _S_concat(__left_result, __right_result);
758 case __detail::_S_leaf:
760 _RopeLeaf* __l = (_RopeLeaf*)__base;
763 if (__start >= __adj_endp1)
765 __result_len = __adj_endp1 - __start;
766 if (__result_len > __lazy_threshold)
769 const _CharT* __section = __l->_M_data + __start;
770 __result = _S_new_RopeLeaf(__section, __result_len,
771 __base->_M_get_allocator());
772 __result->_M_c_string = 0;
775 __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__l->_M_data + __start,
782 case __detail::_S_substringfn:
785 _RopeSubstring* __old = (_RopeSubstring*)__base;
787 if (__start >= __adj_endp1)
789 __result_len = __adj_endp1 - __start;
790 if (__result_len > __lazy_threshold)
792 _RopeSubstring* __result =
793 _S_new_RopeSubstring(__old->_M_base,
794 __start + __old->_M_start,
795 __adj_endp1 - __start,
796 __base->_M_get_allocator());
801 case __detail::_S_function:
803 _RopeFunction* __f = (_RopeFunction*)__base;
806 if (__start >= __adj_endp1)
808 __result_len = __adj_endp1 - __start;
810 if (__result_len > __lazy_threshold)
812 __section = (_CharT*)
813 _Data_allocate(_S_rounded_up_size(__result_len));
815 { (*(__f->_M_fn))(__start, __result_len, __section); }
818 _RopeRep::__STL_FREE_STRING(__section, __result_len,
819 __base->_M_get_allocator());
820 __throw_exception_again;
822 _S_cond_store_eos(__section[__result_len]);
823 return _S_new_RopeLeaf(__section, __result_len,
824 __base->_M_get_allocator());
830 return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start,
831 __base->_M_get_allocator());
835 template<
class _CharT>
836 class _Rope_flatten_char_consumer
837 :
public _Rope_char_consumer<_CharT>
843 _Rope_flatten_char_consumer(_CharT* __buffer)
844 { _M_buf_ptr = __buffer; };
846 ~_Rope_flatten_char_consumer() {}
849 operator()(
const _CharT* __leaf,
size_t __n)
857 template<
class _CharT>
858 class _Rope_find_char_char_consumer
859 :
public _Rope_char_consumer<_CharT>
866 _Rope_find_char_char_consumer(_CharT __p)
867 : _M_pattern(__p), _M_count(0) {}
869 ~_Rope_find_char_char_consumer() {}
872 operator()(
const _CharT* __leaf,
size_t __n)
875 for (__i = 0; __i < __n; __i++)
877 if (__leaf[__i] == _M_pattern)
883 _M_count += __n;
return true;
887 template<
class _CharT,
class _Traits>
889 class _Rope_insert_char_consumer
890 :
public _Rope_char_consumer<_CharT>
893 typedef basic_ostream<_CharT,_Traits> _Insert_ostream;
894 _Insert_ostream& _M_o;
896 _Rope_insert_char_consumer(_Insert_ostream& __writer)
898 ~_Rope_insert_char_consumer() { };
900 bool operator() (
const _CharT* __leaf,
size_t __n);
904 template<
class _CharT,
class _Traits>
906 _Rope_insert_char_consumer<_CharT, _Traits>::
907 operator()(
const _CharT* __leaf,
size_t __n)
911 for (__i = 0; __i < __n; __i++)
912 _M_o.put(__leaf[__i]);
916 template <
class _CharT,
class _Alloc>
918 rope<_CharT, _Alloc>::
919 _S_apply_to_pieces(_Rope_char_consumer<_CharT>& __c,
920 const _RopeRep* __r,
size_t __begin,
size_t __end)
926 case __detail::_S_concat:
928 _RopeConcatenation* __conc = (_RopeConcatenation*)__r;
929 _RopeRep* __left = __conc->_M_left;
930 size_t __left_len = __left->_M_size;
931 if (__begin < __left_len)
933 size_t __left_end =
std::min(__left_len, __end);
934 if (!_S_apply_to_pieces(__c, __left, __begin, __left_end))
937 if (__end > __left_len)
939 _RopeRep* __right = __conc->_M_right;
940 size_t __right_start =
std::max(__left_len, __begin);
941 if (!_S_apply_to_pieces(__c, __right,
942 __right_start - __left_len,
948 case __detail::_S_leaf:
950 _RopeLeaf* __l = (_RopeLeaf*)__r;
951 return __c(__l->_M_data + __begin, __end - __begin);
953 case __detail::_S_function:
954 case __detail::_S_substringfn:
956 _RopeFunction* __f = (_RopeFunction*)__r;
957 size_t __len = __end - __begin;
960 (_CharT*)_Alloc().allocate(__len *
sizeof(_CharT));
963 (*(__f->_M_fn))(__begin, __len, __buffer);
964 __result = __c(__buffer, __len);
965 _Alloc().deallocate(__buffer, __len *
sizeof(_CharT));
969 _Alloc().deallocate(__buffer, __len *
sizeof(_CharT));
970 __throw_exception_again;
979 template<
class _CharT,
class _Traits>
981 _Rope_fill(basic_ostream<_CharT, _Traits>& __o,
size_t __n)
983 char __f = __o.fill();
986 for (__i = 0; __i < __n; __i++)
991 template <
class _CharT>
993 _Rope_is_simple(_CharT*)
997 _Rope_is_simple(
char*)
1001 _Rope_is_simple(
wchar_t*)
1004 template<
class _CharT,
class _Traits,
class _Alloc>
1005 basic_ostream<_CharT, _Traits>&
1006 operator<<(basic_ostream<_CharT, _Traits>& __o,
1007 const rope<_CharT, _Alloc>& __r)
1009 size_t __w = __o.width();
1012 size_t __rope_len = __r.size();
1013 _Rope_insert_char_consumer<_CharT, _Traits> __c(__o);
1014 bool __is_simple = _Rope_is_simple((_CharT*)0);
1016 if (__rope_len < __w)
1017 __pad_len = __w - __rope_len;
1022 __o.width(__w / __rope_len);
1025 if (__is_simple && !__left && __pad_len > 0)
1026 _Rope_fill(__o, __pad_len);
1027 __r.apply_to_pieces(0, __r.size(), __c);
1028 if (__is_simple && __left && __pad_len > 0)
1029 _Rope_fill(__o, __pad_len);
1037 __throw_exception_again;
1042 template <
class _CharT,
class _Alloc>
1044 rope<_CharT, _Alloc>::
1045 _S_flatten(_RopeRep* __r,
size_t __start,
size_t __len,
1048 _Rope_flatten_char_consumer<_CharT> __c(__buffer);
1049 _S_apply_to_pieces(__c, __r, __start, __start + __len);
1050 return(__buffer + __len);
1053 template <
class _CharT,
class _Alloc>
1055 rope<_CharT, _Alloc>::
1056 find(_CharT __pattern,
size_t __start)
const
1058 _Rope_find_char_char_consumer<_CharT> __c(__pattern);
1059 _S_apply_to_pieces(__c, this->_M_tree_ptr, __start, size());
1060 size_type __result_pos = __start + __c._M_count;
1061 #ifndef __STL_OLD_ROPE_SEMANTICS
1062 if (__result_pos == size())
1063 __result_pos = npos;
1065 return __result_pos;
1068 template <
class _CharT,
class _Alloc>
1070 rope<_CharT, _Alloc>::
1071 _S_flatten(_RopeRep* __r, _CharT* __buffer)
1077 case __detail::_S_concat:
1079 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1080 _RopeRep* __left = __c->_M_left;
1081 _RopeRep* __right = __c->_M_right;
1082 _CharT* __rest = _S_flatten(__left, __buffer);
1083 return _S_flatten(__right, __rest);
1085 case __detail::_S_leaf:
1087 _RopeLeaf* __l = (_RopeLeaf*)__r;
1088 return copy_n(__l->_M_data, __l->_M_size, __buffer).second;
1090 case __detail::_S_function:
1091 case __detail::_S_substringfn:
1095 _RopeFunction* __f = (_RopeFunction*)__r;
1096 (*(__f->_M_fn))(0, __f->_M_size, __buffer);
1097 return __buffer + __f->_M_size;
1105 template <
class _CharT,
class _Alloc>
1107 rope<_CharT, _Alloc>::
1108 _S_dump(_RopeRep* __r,
int __indent)
1110 for (
int __i = 0; __i < __indent; __i++)
1117 if (_S_concat == __r->_M_tag)
1119 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1120 _RopeRep* __left = __c->_M_left;
1121 _RopeRep* __right = __c->_M_right;
1124 printf(
"Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
1125 __r, __r->_M_depth, __r->_M_size,
1126 __r->_M_is_balanced?
"" :
"not");
1128 printf(
"Concatenation %p (rc = %ld, depth = %d, "
1129 "len = %ld, %s balanced)\n",
1130 __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size,
1131 __r->_M_is_balanced?
"" :
"not");
1133 _S_dump(__left, __indent + 2);
1134 _S_dump(__right, __indent + 2);
1141 switch (__r->_M_tag)
1143 case __detail::_S_leaf:
1146 case __detail::_S_function:
1147 __kind =
"Function";
1149 case __detail::_S_substringfn:
1150 __kind =
"Function representing substring";
1153 __kind =
"(corrupted kind field!)";
1156 printf(
"%s %p (depth = %d, len = %ld) ",
1157 __kind, __r, __r->_M_depth, __r->_M_size);
1159 printf(
"%s %p (rc = %ld, depth = %d, len = %ld) ",
1160 __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size);
1162 if (_S_is_one_byte_char_type((_CharT*)0))
1164 const int __max_len = 40;
1165 _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len));
1166 _CharT __buffer[__max_len + 1];
1167 bool __too_big = __r->_M_size > __prefix->_M_size;
1169 _S_flatten(__prefix, __buffer);
1170 __buffer[__prefix->_M_size] = _S_eos((_CharT*)0);
1171 printf(
"%s%s\n", (
char*)__buffer,
1172 __too_big?
"...\n" :
"\n");
1179 template <
class _CharT,
class _Alloc>
1181 rope<_CharT, _Alloc>::
1182 _S_min_len[int(__detail::_S_max_rope_depth) + 1] = {
1183 1, 2, 3, 5, 8, 13, 21,
1184 34, 55, 89, 144, 233, 377,
1185 610, 987, 1597, 2584, 4181,
1186 6765, 10946, 17711, 28657, 46368,
1187 75025, 121393, 196418, 317811,
1188 514229, 832040, 1346269, 2178309,
1189 3524578, 5702887, 9227465, 14930352,
1190 24157817, 39088169, 63245986, 102334155,
1191 165580141, 267914296, 433494437,
1192 701408733, 1134903170, 1836311903,
1196 template <
class _CharT,
class _Alloc>
1197 typename rope<_CharT, _Alloc>::_RopeRep*
1198 rope<_CharT, _Alloc>::
1199 _S_balance(_RopeRep* __r)
1201 _RopeRep* __forest[int(__detail::_S_max_rope_depth) + 1];
1202 _RopeRep* __result = 0;
1210 for (__i = 0; __i <= int(__detail::_S_max_rope_depth); ++__i)
1214 _S_add_to_forest(__r, __forest);
1215 for (__i = 0; __i <= int(__detail::_S_max_rope_depth); ++__i)
1216 if (0 != __forest[__i])
1219 _Self_destruct_ptr __old(__result);
1221 __result = _S_concat(__forest[__i], __result);
1222 __forest[__i]->_M_unref_nonnil();
1223 #if !defined(__GC) && defined(__EXCEPTIONS)
1230 for(__i = 0; __i <= int(__detail::_S_max_rope_depth); __i++)
1231 _S_unref(__forest[__i]);
1232 __throw_exception_again;
1235 if (__result->_M_depth >
int(__detail::_S_max_rope_depth))
1236 __throw_length_error(__N(
"rope::_S_balance"));
1240 template <
class _CharT,
class _Alloc>
1242 rope<_CharT, _Alloc>::
1243 _S_add_to_forest(_RopeRep* __r, _RopeRep** __forest)
1245 if (__r->_M_is_balanced)
1247 _S_add_leaf_to_forest(__r, __forest);
1252 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1254 _S_add_to_forest(__c->_M_left, __forest);
1255 _S_add_to_forest(__c->_M_right, __forest);
1260 template <
class _CharT,
class _Alloc>
1262 rope<_CharT, _Alloc>::
1263 _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest)
1265 _RopeRep* __insertee;
1266 _RopeRep* __too_tiny = 0;
1268 size_t __s = __r->_M_size;
1270 for (__i = 0; __s >= _S_min_len[__i+1]; ++__i)
1272 if (0 != __forest[__i])
1275 _Self_destruct_ptr __old(__too_tiny);
1277 __too_tiny = _S_concat_and_set_balanced(__forest[__i],
1279 __forest[__i]->_M_unref_nonnil();
1285 _Self_destruct_ptr __old(__too_tiny);
1287 __insertee = _S_concat_and_set_balanced(__too_tiny, __r);
1293 if (0 != __forest[__i])
1296 _Self_destruct_ptr __old(__insertee);
1298 __insertee = _S_concat_and_set_balanced(__forest[__i],
1300 __forest[__i]->_M_unref_nonnil();
1303 if (__i ==
int(__detail::_S_max_rope_depth)
1304 || __insertee->_M_size < _S_min_len[__i+1])
1306 __forest[__i] = __insertee;
1313 template <
class _CharT,
class _Alloc>
1315 rope<_CharT, _Alloc>::
1316 _S_fetch(_RopeRep* __r, size_type __i)
1318 __GC_CONST _CharT* __cstr = __r->_M_c_string;
1326 case __detail::_S_concat:
1328 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1329 _RopeRep* __left = __c->_M_left;
1330 size_t __left_len = __left->_M_size;
1332 if (__i >= __left_len)
1335 __r = __c->_M_right;
1341 case __detail::_S_leaf:
1343 _RopeLeaf* __l = (_RopeLeaf*)__r;
1344 return __l->_M_data[__i];
1346 case __detail::_S_function:
1347 case __detail::_S_substringfn:
1349 _RopeFunction* __f = (_RopeFunction*)__r;
1352 (*(__f->_M_fn))(__i, 1, &__result);
1362 template <
class _CharT,
class _Alloc>
1364 rope<_CharT, _Alloc>::
1365 _S_fetch_ptr(_RopeRep* __r, size_type __i)
1367 _RopeRep* __clrstack[__detail::_S_max_rope_depth];
1372 if (__r->_M_ref_count > 1)
1376 case __detail::_S_concat:
1378 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1379 _RopeRep* __left = __c->_M_left;
1380 size_t __left_len = __left->_M_size;
1382 if (__c->_M_c_string != 0)
1383 __clrstack[__csptr++] = __c;
1384 if (__i >= __left_len)
1387 __r = __c->_M_right;
1393 case __detail::_S_leaf:
1395 _RopeLeaf* __l = (_RopeLeaf*)__r;
1396 if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0)
1397 __clrstack[__csptr++] = __l;
1401 _RopeRep* __d = __clrstack[__csptr];
1402 __d->_M_free_c_string();
1403 __d->_M_c_string = 0;
1405 return __l->_M_data + __i;
1407 case __detail::_S_function:
1408 case __detail::_S_substringfn:
1419 template <
class _CharT,
class _Alloc>
1421 rope<_CharT, _Alloc>::
1422 _S_compare (
const _RopeRep* __left,
const _RopeRep* __right)
1431 __left_len = __left->_M_size;
1432 __right_len = __right->_M_size;
1433 if (__detail::_S_leaf == __left->_M_tag)
1435 _RopeLeaf* __l = (_RopeLeaf*) __left;
1436 if (__detail::_S_leaf == __right->_M_tag)
1438 _RopeLeaf* __r = (_RopeLeaf*) __right;
1440 __l->_M_data + __left_len,
1441 __r->_M_data, __r->_M_data
1446 const_iterator __rstart(__right, 0);
1447 const_iterator __rend(__right, __right_len);
1455 const_iterator __lstart(__left, 0);
1456 const_iterator __lend(__left, __left_len);
1457 if (__detail::_S_leaf == __right->_M_tag)
1459 _RopeLeaf* __r = (_RopeLeaf*) __right;
1461 __r->_M_data, __r->_M_data
1466 const_iterator __rstart(__right, 0);
1467 const_iterator __rend(__right, __right_len);
1475 template <
class _CharT,
class _Alloc>
1476 _Rope_char_ref_proxy<_CharT, _Alloc>&
1477 _Rope_char_ref_proxy<_CharT, _Alloc>::
1478 operator=(_CharT __c)
1480 _RopeRep* __old = _M_root->_M_tree_ptr;
1484 _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos);
1491 _Self_destruct_ptr __left(_My_rope::_S_substring(__old, 0, _M_pos));
1492 _Self_destruct_ptr __right(_My_rope::_S_substring(__old, _M_pos + 1,
1494 _Self_destruct_ptr __result_left(_My_rope::
1495 _S_destr_concat_char_iter(__left,
1498 _RopeRep* __result = _My_rope::_S_concat(__result_left, __right);
1500 _RopeRep::_S_unref(__old);
1502 _M_root->_M_tree_ptr = __result;
1506 template <
class _CharT,
class _Alloc>
1507 inline _Rope_char_ref_proxy<_CharT, _Alloc>::
1508 operator _CharT()
const
1510 if (_M_current_valid)
1513 return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos);
1516 template <
class _CharT,
class _Alloc>
1517 _Rope_char_ptr_proxy<_CharT, _Alloc>
1520 {
return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this); }
1522 template <
class _CharT,
class _Alloc>
1523 rope<_CharT, _Alloc>::
1524 rope(
size_t __n, _CharT __c,
const allocator_type& __a)
1527 rope<_CharT,_Alloc> __result;
1528 const size_t __exponentiate_threshold = 32;
1531 _CharT* __rest_buffer;
1532 _RopeRep* __remainder;
1533 rope<_CharT, _Alloc> __remainder_rope;
1538 __exponent = __n / __exponentiate_threshold;
1539 __rest = __n % __exponentiate_threshold;
1544 __rest_buffer = this->_Data_allocate(_S_rounded_up_size(__rest));
1545 __uninitialized_fill_n_a(__rest_buffer, __rest, __c,
1546 _M_get_allocator());
1547 _S_cond_store_eos(__rest_buffer[__rest]);
1549 { __remainder = _S_new_RopeLeaf(__rest_buffer, __rest,
1550 _M_get_allocator()); }
1553 _RopeRep::__STL_FREE_STRING(__rest_buffer, __rest,
1554 _M_get_allocator());
1555 __throw_exception_again;
1558 __remainder_rope._M_tree_ptr = __remainder;
1559 if (__exponent != 0)
1561 _CharT* __base_buffer =
1562 this->_Data_allocate(_S_rounded_up_size(__exponentiate_threshold));
1563 _RopeLeaf* __base_leaf;
1565 __uninitialized_fill_n_a(__base_buffer, __exponentiate_threshold, __c,
1566 _M_get_allocator());
1567 _S_cond_store_eos(__base_buffer[__exponentiate_threshold]);
1570 __base_leaf = _S_new_RopeLeaf(__base_buffer,
1571 __exponentiate_threshold,
1572 _M_get_allocator());
1576 _RopeRep::__STL_FREE_STRING(__base_buffer,
1577 __exponentiate_threshold,
1578 _M_get_allocator());
1579 __throw_exception_again;
1581 __base_rope._M_tree_ptr = __base_leaf;
1582 if (1 == __exponent)
1583 __result = __base_rope;
1585 __result =
power(__base_rope, __exponent,
1586 _Rope_Concat_fn<_CharT, _Alloc>());
1588 if (0 != __remainder)
1589 __result += __remainder_rope;
1592 __result = __remainder_rope;
1594 this->_M_tree_ptr = __result._M_tree_ptr;
1595 this->_M_tree_ptr->_M_ref_nonnil();
1598 template<
class _CharT,
class _Alloc>
1600 rope<_CharT, _Alloc>::_S_empty_c_str[1];
1602 template<
class _CharT,
class _Alloc>
1604 rope<_CharT, _Alloc>::
1607 if (0 == this->_M_tree_ptr)
1609 _S_empty_c_str[0] = _S_eos((_CharT*)0);
1611 return _S_empty_c_str;
1613 __gthread_mutex_lock (&this->_M_tree_ptr->_M_c_string_lock);
1614 __GC_CONST _CharT* __result = this->_M_tree_ptr->_M_c_string;
1617 size_t __s = size();
1618 __result = this->_Data_allocate(__s + 1);
1619 _S_flatten(this->_M_tree_ptr, __result);
1620 __result[__s] = _S_eos((_CharT*)0);
1621 this->_M_tree_ptr->_M_c_string = __result;
1623 __gthread_mutex_unlock (&this->_M_tree_ptr->_M_c_string_lock);
1627 template<
class _CharT,
class _Alloc>
1628 const _CharT* rope<_CharT, _Alloc>::
1629 replace_with_c_str()
1631 if (0 == this->_M_tree_ptr)
1633 _S_empty_c_str[0] = _S_eos((_CharT*)0);
1634 return _S_empty_c_str;
1636 __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string;
1637 if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag
1638 && 0 != __old_c_string)
1639 return(__old_c_string);
1640 size_t __s = size();
1641 _CharT* __result = this->_Data_allocate(_S_rounded_up_size(__s));
1642 _S_flatten(this->_M_tree_ptr, __result);
1643 __result[__s] = _S_eos((_CharT*)0);
1644 this->_M_tree_ptr->_M_unref_nonnil();
1645 this->_M_tree_ptr = _S_new_RopeLeaf(__result, __s,
1646 this->_M_get_allocator());
1652 template<
class _Rope_iterator>
1654 _Rope_rotate(_Rope_iterator __first,
1655 _Rope_iterator __middle,
1656 _Rope_iterator __last)
1658 typedef typename _Rope_iterator::value_type _CharT;
1659 typedef typename _Rope_iterator::_allocator_type _Alloc;
1661 rope<_CharT, _Alloc>& __r(__first.container());
1662 rope<_CharT, _Alloc> __prefix = __r.substr(0, __first.index());
1663 rope<_CharT, _Alloc> __suffix =
1664 __r.substr(__last.index(), __r.size() - __last.index());
1665 rope<_CharT, _Alloc> __part1 =
1666 __r.substr(__middle.index(), __last.index() - __middle.index());
1667 rope<_CharT, _Alloc> __part2 =
1668 __r.substr(__first.index(), __middle.index() - __first.index());
1675 #if !defined(__GNUC__)
1678 rotate(_Rope_iterator<
char, __STL_DEFAULT_ALLOCATOR(
char)> __first,
1679 _Rope_iterator<
char, __STL_DEFAULT_ALLOCATOR(
char)> __middle,
1680 _Rope_iterator<
char, __STL_DEFAULT_ALLOCATOR(
char)> __last)
1681 { _Rope_rotate(__first, __middle, __last); }
1693 rotate(_Rope_iterator<
wchar_t, __STL_DEFAULT_ALLOCATOR(
char)> __first,
1694 _Rope_iterator<
wchar_t, __STL_DEFAULT_ALLOCATOR(
char)> __middle,
1695 _Rope_iterator<
wchar_t, __STL_DEFAULT_ALLOCATOR(
char)> __last)
1696 { _Rope_rotate(__first, __middle, __last); }
1699 _GLIBCXX_END_NAMESPACE
1700
static const fmtflags left
Adds fill characters on the right (final positions) of certain generated output. (I.e., the thing you print is flush left.)
pair< _InputIter, _ForwardIter > uninitialized_copy_n(_InputIter __first, _Size __count, _ForwardIter __result)
Copies the range [first,last) into result.
const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
int lexicographical_compare_3way(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
memcmp on steroids.
void _Destroy(_Tp *__pointer)
bitset< _Nb > operator&(const bitset< _Nb > &__x, const bitset< _Nb > &__y)
Global bitwise operations on bitsets.
const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
void uninitialized_fill_n(_ForwardIterator __first, _Size __n, const _Tp &__x)
Copies the value x into the range [first,first+n).
pair< _InputIterator, _OutputIterator > copy_n(_InputIterator __first, _Size __count, _OutputIterator __result)
Copies the range [first,first+count) into [result,result+count).
_Tp power(_Tp __x, _Integer __n, _MonoidOperation __monoid_op)