51namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
53_GLIBCXX_BEGIN_NAMESPACE_VERSION
59 template <
class _CharT,
class _Alloc>
61 _Rope_iterator_base<_CharT, _Alloc>::
62 _S_setbuf(_Rope_iterator_base<_CharT, _Alloc>& __x)
65 const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index];
66 size_t __leaf_pos = __x._M_leaf_pos;
67 size_t __pos = __x._M_current_pos;
69 switch(__leaf->_M_tag)
71 case __detail::_S_leaf:
72 __x._M_buf_start = ((_Rope_RopeLeaf<_CharT, _Alloc>*)__leaf)->_M_data;
73 __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos);
74 __x._M_buf_end = __x._M_buf_start + __leaf->_M_size;
76 case __detail::_S_function:
77 case __detail::_S_substringfn:
79 size_t __len = _S_iterator_buf_len;
80 size_t __buf_start_pos = __leaf_pos;
81 size_t __leaf_end = __leaf_pos + __leaf->_M_size;
82 char_producer<_CharT>* __fn = ((_Rope_RopeFunction<_CharT,
83 _Alloc>*)__leaf)->_M_fn;
84 if (__buf_start_pos + __len <= __pos)
86 __buf_start_pos = __pos - __len / 4;
87 if (__buf_start_pos + __len > __leaf_end)
88 __buf_start_pos = __leaf_end - __len;
90 if (__buf_start_pos + __len > __leaf_end)
91 __len = __leaf_end - __buf_start_pos;
92 (*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf);
93 __x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos);
94 __x._M_buf_start = __x._M_tmp_buf;
95 __x._M_buf_end = __x._M_tmp_buf + __len;
105 template <
class _CharT,
class _Alloc>
107 _Rope_iterator_base<_CharT, _Alloc>::
108 _S_setcache(_Rope_iterator_base<_CharT, _Alloc>& __x)
111 const _RopeRep* __path[int(__detail::_S_max_rope_depth) + 1];
112 const _RopeRep* __curr_rope;
113 int __curr_depth = -1;
114 size_t __curr_start_pos = 0;
115 size_t __pos = __x._M_current_pos;
116 unsigned char __dirns = 0;
118 if (__pos >= __x._M_root->_M_size)
123 __curr_rope = __x._M_root;
124 if (0 != __curr_rope->_M_c_string)
127 __x._M_buf_start = __curr_rope->_M_c_string;
128 __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size;
129 __x._M_buf_ptr = __curr_rope->_M_c_string + __pos;
130 __x._M_path_end[0] = __curr_rope;
131 __x._M_leaf_index = 0;
138 __path[__curr_depth] = __curr_rope;
139 switch(__curr_rope->_M_tag)
141 case __detail::_S_leaf:
142 case __detail::_S_function:
143 case __detail::_S_substringfn:
144 __x._M_leaf_pos = __curr_start_pos;
146 case __detail::_S_concat:
148 _Rope_RopeConcatenation<_CharT, _Alloc>* __c =
149 (_Rope_RopeConcatenation<_CharT, _Alloc>*)__curr_rope;
150 _RopeRep* __left = __c->_M_left;
151 size_t __left_len = __left->_M_size;
154 if (__pos >= __curr_start_pos + __left_len)
157 __curr_rope = __c->_M_right;
158 __curr_start_pos += __left_len;
161 __curr_rope = __left;
170 int __j = __curr_depth + 1 - int(_S_path_cache_len);
172 if (__j < 0) __j = 0;
173 while (__j <= __curr_depth)
174 __x._M_path_end[++__i] = __path[__j++];
175 __x._M_leaf_index = __i;
177 __x._M_path_directions = __dirns;
183 template <
class _CharT,
class _Alloc>
185 _Rope_iterator_base<_CharT, _Alloc>::
186 _S_setcache_for_incr(_Rope_iterator_base<_CharT, _Alloc>& __x)
189 int __current_index = __x._M_leaf_index;
190 const _RopeRep* __current_node = __x._M_path_end[__current_index];
191 size_t __len = __current_node->_M_size;
192 size_t __node_start_pos = __x._M_leaf_pos;
193 unsigned char __dirns = __x._M_path_directions;
194 _Rope_RopeConcatenation<_CharT, _Alloc>* __c;
196 if (__x._M_current_pos - __node_start_pos < __len)
203 while (--__current_index >= 0)
207 __current_node = __x._M_path_end[__current_index];
208 __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node;
211 __node_start_pos -= __c->_M_left->_M_size;
214 if (__current_index < 0)
220 __current_node = __x._M_path_end[__current_index];
221 __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node;
225 __node_start_pos += __c->_M_left->_M_size;
226 __current_node = __c->_M_right;
227 __x._M_path_end[++__current_index] = __current_node;
229 while (__detail::_S_concat == __current_node->_M_tag)
232 if (
int(_S_path_cache_len) == __current_index)
235 for (__i = 0; __i < int(_S_path_cache_len) - 1; __i++)
236 __x._M_path_end[__i] = __x._M_path_end[__i+1];
240 ((_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node)->_M_left;
241 __x._M_path_end[__current_index] = __current_node;
245 __x._M_leaf_index = __current_index;
246 __x._M_leaf_pos = __node_start_pos;
247 __x._M_path_directions = __dirns;
251 template <
class _CharT,
class _Alloc>
253 _Rope_iterator_base<_CharT, _Alloc>::
254 _M_incr(std::size_t __n)
256 _M_current_pos += __n;
259 std::size_t __chars_left = _M_buf_end - _M_buf_ptr;
260 if (__chars_left > __n)
262 else if (__chars_left == __n)
265 _S_setcache_for_incr(*
this);
272 template <
class _CharT,
class _Alloc>
274 _Rope_iterator_base<_CharT, _Alloc>::
275 _M_decr(std::size_t __n)
279 std::size_t __chars_left = _M_buf_ptr - _M_buf_start;
280 if (__chars_left >= __n)
285 _M_current_pos -= __n;
288 template <
class _CharT,
class _Alloc>
290 _Rope_iterator<_CharT, _Alloc>::
293 if (_M_root_rope->_M_tree_ptr != this->_M_root)
296 _RopeRep::_S_unref(this->_M_root);
297 this->_M_root = _M_root_rope->_M_tree_ptr;
298 _RopeRep::_S_ref(this->_M_root);
299 this->_M_buf_ptr = 0;
303 template <
class _CharT,
class _Alloc>
305 _Rope_const_iterator<_CharT, _Alloc>::
306 _Rope_const_iterator(
const _Rope_iterator<_CharT, _Alloc>& __x)
307 : _Rope_iterator_base<_CharT, _Alloc>(__x)
310 template <
class _CharT,
class _Alloc>
312 _Rope_iterator<_CharT, _Alloc>::
313 _Rope_iterator(rope<_CharT, _Alloc>& __r, std::size_t __pos)
314 : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos),
316 { _RopeRep::_S_ref(this->_M_root); }
318 template <
class _CharT,
class _Alloc>
320 rope<_CharT, _Alloc>::
321 _S_char_ptr_len(
const _CharT* __s)
323 const _CharT* __p = __s;
325 while (!_S_is0(*__p))
333 template <
class _CharT,
class _Alloc>
335 _Rope_RopeRep<_CharT, _Alloc>::
338 _CharT* __cstr = _M_c_string;
341 std::size_t __size = this->_M_size + 1;
343 this->_Data_deallocate(__cstr, __size);
347 template <
class _CharT,
class _Alloc>
349 _Rope_RopeRep<_CharT, _Alloc>::
350 _S_free_string(_CharT* __s, std::size_t __n, allocator_type& __a)
352 if (!_S_is_basic_char_type((_CharT*)0))
357 _Rope_RopeLeaf<_CharT, _Alloc>::_S_rounded_up_size(__n));
366 template <
class _CharT,
class _Alloc>
368 _Rope_RopeRep<_CharT, _Alloc>::
373 case __detail::_S_leaf:
375 _Rope_RopeLeaf<_CharT, _Alloc>* __l
376 = (_Rope_RopeLeaf<_CharT, _Alloc>*)
this;
377 __l->_Rope_RopeLeaf<_CharT, _Alloc>::~_Rope_RopeLeaf();
378 this->_L_deallocate(__l, 1);
381 case __detail::_S_concat:
383 _Rope_RopeConcatenation<_CharT,_Alloc>* __c
384 = (_Rope_RopeConcatenation<_CharT, _Alloc>*)
this;
385 __c->_Rope_RopeConcatenation<_CharT, _Alloc>::
386 ~_Rope_RopeConcatenation();
387 this->_C_deallocate(__c, 1);
390 case __detail::_S_function:
392 _Rope_RopeFunction<_CharT, _Alloc>* __f
393 = (_Rope_RopeFunction<_CharT, _Alloc>*)
this;
394 __f->_Rope_RopeFunction<_CharT, _Alloc>::~_Rope_RopeFunction();
395 this->_F_deallocate(__f, 1);
398 case __detail::_S_substringfn:
400 _Rope_RopeSubstring<_CharT, _Alloc>* __ss =
401 (_Rope_RopeSubstring<_CharT, _Alloc>*)
this;
402 __ss->_Rope_RopeSubstring<_CharT, _Alloc>::
403 ~_Rope_RopeSubstring();
404 this->_S_deallocate(__ss, 1);
411 template <
class _CharT,
class _Alloc>
413 _Rope_RopeRep<_CharT, _Alloc>::
414 _S_free_string(
const _CharT*, std::size_t, allocator_type)
421 template <
class _CharT,
class _Alloc>
422 typename rope<_CharT, _Alloc>::_RopeLeaf*
423 rope<_CharT, _Alloc>::
424 _S_leaf_concat_char_iter(_RopeLeaf* __r,
const _CharT* __iter,
427 std::size_t __old_len = __r->_M_size;
428 _CharT* __new_data = (_CharT*)
429 rope::_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 std::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)
493 _RopeConcatenation* __result = _S_new_RopeConcatenation(__left, __right,
496 size_t __depth = __result->_M_depth;
499 && (__result->_M_size < 1000
500 || __depth >
size_t(__detail::_S_max_rope_depth)))
502 _RopeRep* __balanced;
506 __balanced = _S_balance(__result);
507 __result->_M_unref_nonnil();
511 rope::_C_deallocate(__result,1);
512 __throw_exception_again;
524 template <
class _CharT,
class _Alloc>
525 typename rope<_CharT, _Alloc>::_RopeRep*
526 rope<_CharT, _Alloc>::
527 _S_concat_char_iter(_RopeRep* __r,
const _CharT*__s, std::size_t __slen)
537 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
538 __r->_M_get_allocator());
539 if (__r->_M_tag == __detail::_S_leaf
540 && __r->_M_size + __slen <=
size_t(_S_copy_max))
542 __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
545 if (__detail::_S_concat == __r->_M_tag
546 && __detail::_S_leaf == ((_RopeConcatenation*) __r)->_M_right->_M_tag)
549 (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right);
550 if (__right->_M_size + __slen <=
size_t(_S_copy_max))
552 _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left;
554 _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen);
555 __left->_M_ref_nonnil();
557 { __result = _S_tree_concat(__left, __nright); }
562 __throw_exception_again;
568 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->_M_get_allocator());
571 __r->_M_ref_nonnil();
572 __result = _S_tree_concat(__r, __nright);
578 __throw_exception_again;
584 template <
class _CharT,
class _Alloc>
585 typename rope<_CharT,_Alloc>::_RopeRep*
586 rope<_CharT,_Alloc>::
587 _S_destr_concat_char_iter(_RopeRep* __r,
const _CharT* __s,
593 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
594 __r->_M_get_allocator());
595 size_t __count = __r->_M_ref_count;
596 size_t __orig_size = __r->_M_size;
598 return _S_concat_char_iter(__r, __s, __slen);
601 __r->_M_ref_count = 2;
604 if (__orig_size + __slen <=
size_t(_S_copy_max)
605 && __detail::_S_leaf == __r->_M_tag)
607 __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s,
611 if (__detail::_S_concat == __r->_M_tag)
613 _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*)
615 if (__detail::_S_leaf == __right->_M_tag
616 && __right->_M_size + __slen <=
size_t(_S_copy_max))
618 _RopeRep* __new_right =
619 _S_destr_leaf_concat_char_iter(__right, __s, __slen);
620 if (__right == __new_right)
621 __new_right->_M_ref_count = 1;
623 __right->_M_unref_nonnil();
624 __r->_M_ref_count = 2;
625 ((_RopeConcatenation*)__r)->_M_right = __new_right;
626 __r->_M_size = __orig_size + __slen;
627 if (0 != __r->_M_c_string)
629 __r->_M_free_c_string();
630 __r->_M_c_string = 0;
636 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->_M_get_allocator());
637 __r->_M_ref_nonnil();
639 { __result = _S_tree_concat(__r, __right); }
644 __throw_exception_again;
650 template <
class _CharT,
class _Alloc>
651 typename rope<_CharT, _Alloc>::_RopeRep*
652 rope<_CharT, _Alloc>::
653 _S_concat(_RopeRep* __left, _RopeRep* __right)
663 __left->_M_ref_nonnil();
666 if (__detail::_S_leaf == __right->_M_tag)
668 if (__detail::_S_leaf == __left->_M_tag)
670 if (__right->_M_size + __left->_M_size <=
size_t(_S_copy_max))
671 return _S_leaf_concat_char_iter((_RopeLeaf*)__left,
672 ((_RopeLeaf*)__right)->_M_data,
675 else if (__detail::_S_concat == __left->_M_tag
676 && __detail::_S_leaf == ((_RopeConcatenation*)
677 __left)->_M_right->_M_tag)
679 _RopeLeaf* __leftright =
680 (_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right);
681 if (__leftright->_M_size
682 + __right->_M_size <=
size_t(_S_copy_max))
684 _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left;
685 _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright,
690 __leftleft->_M_ref_nonnil();
692 {
return(_S_tree_concat(__leftleft, __rest)); }
695 _S_unref(__leftleft);
697 __throw_exception_again;
702 __left->_M_ref_nonnil();
703 __right->_M_ref_nonnil();
705 {
return(_S_tree_concat(__left, __right)); }
710 __throw_exception_again;
714 template <
class _CharT,
class _Alloc>
715 typename rope<_CharT, _Alloc>::_RopeRep*
716 rope<_CharT, _Alloc>::
717 _S_substring(_RopeRep*
__base, std::size_t __start, std::size_t __endp1)
722 size_t __len =
__base->_M_size;
724 const size_t __lazy_threshold = 128;
726 if (__endp1 >= __len)
738 __adj_endp1 = __endp1;
742 case __detail::_S_concat:
744 _RopeConcatenation* __c = (_RopeConcatenation*)
__base;
745 _RopeRep* __left = __c->_M_left;
746 _RopeRep* __right = __c->_M_right;
747 size_t __left_len = __left->_M_size;
750 if (__adj_endp1 <= __left_len)
751 return _S_substring(__left, __start, __endp1);
752 else if (__start >= __left_len)
753 return _S_substring(__right, __start - __left_len,
754 __adj_endp1 - __left_len);
755 _Self_destruct_ptr __left_result(_S_substring(__left,
758 _Self_destruct_ptr __right_result(_S_substring(__right, 0,
761 __result = _S_concat(__left_result, __right_result);
764 case __detail::_S_leaf:
766 _RopeLeaf* __l = (_RopeLeaf*)
__base;
769 if (__start >= __adj_endp1)
771 __result_len = __adj_endp1 - __start;
772 if (__result_len > __lazy_threshold)
775 const _CharT* __section = __l->_M_data + __start;
776 __result = _S_new_RopeLeaf(__section, __result_len,
777 __base->_M_get_allocator());
778 __result->_M_c_string = 0;
781 __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__l->_M_data + __start,
788 case __detail::_S_substringfn:
791 _RopeSubstring* __old = (_RopeSubstring*)
__base;
793 if (__start >= __adj_endp1)
795 __result_len = __adj_endp1 - __start;
796 if (__result_len > __lazy_threshold)
798 _RopeSubstring* __result =
799 _S_new_RopeSubstring(__old->_M_base,
800 __start + __old->_M_start,
801 __adj_endp1 - __start,
802 __base->_M_get_allocator());
807 case __detail::_S_function:
809 _RopeFunction* __f = (_RopeFunction*)
__base;
812 if (__start >= __adj_endp1)
814 __result_len = __adj_endp1 - __start;
816 if (__result_len > __lazy_threshold)
818 __section = (_CharT*)
819 rope::_Data_allocate(_S_rounded_up_size(__result_len));
821 { (*(__f->_M_fn))(__start, __result_len, __section); }
824 _RopeRep::__STL_FREE_STRING(__section, __result_len,
825 __base->_M_get_allocator());
826 __throw_exception_again;
828 _S_cond_store_eos(__section[__result_len]);
829 return _S_new_RopeLeaf(__section, __result_len,
830 __base->_M_get_allocator());
836 return _S_new_RopeSubstring(
__base, __start, __adj_endp1 - __start,
837 __base->_M_get_allocator());
841 template<
class _CharT>
842 class _Rope_flatten_char_consumer
843 :
public _Rope_char_consumer<_CharT>
849 _Rope_flatten_char_consumer(_CharT* __buffer)
850 { _M_buf_ptr = __buffer; }
852 ~_Rope_flatten_char_consumer() {}
855 operator()(
const _CharT* __leaf, std::size_t __n)
863 template<
class _CharT>
864 class _Rope_find_char_char_consumer
865 :
public _Rope_char_consumer<_CharT>
870 std::size_t _M_count;
872 _Rope_find_char_char_consumer(_CharT __p)
873 : _M_pattern(__p), _M_count(0) {}
875 ~_Rope_find_char_char_consumer() {}
878 operator()(
const _CharT* __leaf, std::size_t __n)
881 for (__i = 0; __i < __n; __i++)
883 if (__leaf[__i] == _M_pattern)
889 _M_count += __n;
return true;
893 template<
class _CharT,
class _Traits>
895 class _Rope_insert_char_consumer
896 :
public _Rope_char_consumer<_CharT>
900 _Insert_ostream& _M_o;
902 _Rope_insert_char_consumer(_Insert_ostream& __writer)
904 ~_Rope_insert_char_consumer() { }
906 bool operator() (
const _CharT* __leaf, std::size_t __n);
910 template<
class _CharT,
class _Traits>
912 _Rope_insert_char_consumer<_CharT, _Traits>::
913 operator()(
const _CharT* __leaf, std::size_t __n)
917 for (__i = 0; __i < __n; __i++)
918 _M_o.put(__leaf[__i]);
922 template <
class _CharT,
class _Alloc>
924 rope<_CharT, _Alloc>::
925 _S_apply_to_pieces(_Rope_char_consumer<_CharT>& __c,
const _RopeRep* __r,
926 std::size_t __begin, std::size_t __end)
933 case __detail::_S_concat:
935 _RopeConcatenation* __conc = (_RopeConcatenation*)__r;
936 _RopeRep* __left = __conc->_M_left;
937 size_t __left_len = __left->_M_size;
938 if (__begin < __left_len)
940 size_t __left_end =
std::min(__left_len, __end);
941 if (!_S_apply_to_pieces(__c, __left, __begin, __left_end))
944 if (__end > __left_len)
946 _RopeRep* __right = __conc->_M_right;
947 size_t __right_start =
std::max(__left_len, __begin);
948 if (!_S_apply_to_pieces(__c, __right,
949 __right_start - __left_len,
955 case __detail::_S_leaf:
957 _RopeLeaf* __l = (_RopeLeaf*)__r;
958 return __c(__l->_M_data + __begin, __end - __begin);
960 case __detail::_S_function:
961 case __detail::_S_substringfn:
963 _RopeFunction* __f = (_RopeFunction*)__r;
964 size_t __len = __end - __begin;
967 (_CharT*)_Alloc().allocate(__len *
sizeof(_CharT));
970 (*(__f->_M_fn))(__begin, __len, __buffer);
971 __result = __c(__buffer, __len);
972 _Alloc().deallocate(__buffer, __len *
sizeof(_CharT));
976 _Alloc().deallocate(__buffer, __len *
sizeof(_CharT));
977 __throw_exception_again;
986 template<
class _CharT,
class _Traits>
990 char __f = __o.
fill();
993 for (__i = 0; __i < __n; __i++)
998 template <
class _CharT>
1000 _Rope_is_simple(_CharT*)
1004 _Rope_is_simple(
char*)
1008 _Rope_is_simple(
wchar_t*)
1011 template<
class _CharT,
class _Traits,
class _Alloc>
1014 const rope<_CharT, _Alloc>& __r)
1017 size_t __w = __o.
width();
1020 size_t __rope_len = __r.size();
1021 _Rope_insert_char_consumer<_CharT, _Traits> __c(__o);
1022 bool __is_simple = _Rope_is_simple((_CharT*)0);
1024 if (__rope_len < __w)
1025 __pad_len = __w - __rope_len;
1030 __o.
width(__w / __rope_len);
1033 if (__is_simple && !__left && __pad_len > 0)
1034 _Rope_fill(__o, __pad_len);
1035 __r.apply_to_pieces(0, __r.size(), __c);
1036 if (__is_simple && __left && __pad_len > 0)
1037 _Rope_fill(__o, __pad_len);
1045 __throw_exception_again;
1050 template <
class _CharT,
class _Alloc>
1052 rope<_CharT, _Alloc>::
1053 _S_flatten(_RopeRep* __r, std::size_t __start, std::size_t __len,
1056 _Rope_flatten_char_consumer<_CharT> __c(__buffer);
1057 _S_apply_to_pieces(__c, __r, __start, __start + __len);
1058 return(__buffer + __len);
1061 template <
class _CharT,
class _Alloc>
1063 rope<_CharT, _Alloc>::
1064 find(_CharT __pattern, std::size_t __start)
const
1066 _Rope_find_char_char_consumer<_CharT> __c(__pattern);
1067 _S_apply_to_pieces(__c, this->_M_tree_ptr, __start, size());
1068 size_type __result_pos = __start + __c._M_count;
1069#ifndef __STL_OLD_ROPE_SEMANTICS
1070 if (__result_pos == size())
1071 __result_pos = npos;
1073 return __result_pos;
1076 template <
class _CharT,
class _Alloc>
1078 rope<_CharT, _Alloc>::
1079 _S_flatten(_RopeRep* __r, _CharT* __buffer)
1085 case __detail::_S_concat:
1087 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1088 _RopeRep* __left = __c->_M_left;
1089 _RopeRep* __right = __c->_M_right;
1090 _CharT* __rest = _S_flatten(__left, __buffer);
1091 return _S_flatten(__right, __rest);
1093 case __detail::_S_leaf:
1095 _RopeLeaf* __l = (_RopeLeaf*)__r;
1096 return copy_n(__l->_M_data, __l->_M_size, __buffer).second;
1098 case __detail::_S_function:
1099 case __detail::_S_substringfn:
1103 _RopeFunction* __f = (_RopeFunction*)__r;
1104 (*(__f->_M_fn))(0, __f->_M_size, __buffer);
1105 return __buffer + __f->_M_size;
1113 template <
class _CharT,
class _Alloc>
1115 rope<_CharT, _Alloc>::
1116 _S_dump(_RopeRep* __r,
int __indent)
1119 for (
int __i = 0; __i < __indent; __i++)
1126 if (__detail::_S_concat == __r->_M_tag)
1128 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1129 _RopeRep* __left = __c->_M_left;
1130 _RopeRep* __right = __c->_M_right;
1133 printf(
"Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
1134 __r, __r->_M_depth, __r->_M_size,
1135 __r->_M_is_balanced?
"" :
"not");
1137 printf(
"Concatenation %p (rc = %ld, depth = %d, "
1138 "len = %ld, %s balanced)\n",
1139 __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size,
1140 __r->_M_is_balanced?
"" :
"not");
1142 _S_dump(__left, __indent + 2);
1143 _S_dump(__right, __indent + 2);
1150 switch (__r->_M_tag)
1152 case __detail::_S_leaf:
1155 case __detail::_S_function:
1156 __kind =
"Function";
1158 case __detail::_S_substringfn:
1159 __kind =
"Function representing substring";
1162 __kind =
"(corrupted kind field!)";
1165 printf(
"%s %p (depth = %d, len = %ld) ",
1166 __kind, __r, __r->_M_depth, __r->_M_size);
1168 printf(
"%s %p (rc = %ld, depth = %d, len = %ld) ",
1169 __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size);
1171 if (_S_is_one_byte_char_type((_CharT*)0))
1173 const int __max_len = 40;
1174 _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len));
1175 _CharT __buffer[__max_len + 1];
1176 bool __too_big = __r->_M_size > __prefix->_M_size;
1178 _S_flatten(__prefix, __buffer);
1179 __buffer[__prefix->_M_size] = _S_eos((_CharT*)0);
1180 printf(
"%s%s\n", (
char*)__buffer,
1181 __too_big?
"...\n" :
"\n");
1188 template <
class _CharT,
class _Alloc>
1190 rope<_CharT, _Alloc>::
1191 _S_min_len[int(__detail::_S_max_rope_depth) + 1] = {
1192 1, 2, 3, 5, 8, 13, 21,
1193 34, 55, 89, 144, 233, 377,
1194 610, 987, 1597, 2584, 4181,
1195 6765, 10946, 17711, 28657, 46368,
1196 75025, 121393, 196418, 317811,
1197 514229, 832040, 1346269, 2178309,
1198 3524578, 5702887, 9227465, 14930352,
1199 24157817, 39088169, 63245986, 102334155,
1200 165580141, 267914296, 433494437,
1201 701408733, 1134903170, 1836311903,
1205 template <
class _CharT,
class _Alloc>
1206 typename rope<_CharT, _Alloc>::_RopeRep*
1207 rope<_CharT, _Alloc>::
1208 _S_balance(_RopeRep* __r)
1210 _RopeRep* __forest[int(__detail::_S_max_rope_depth) + 1];
1211 _RopeRep* __result = 0;
1219 for (__i = 0; __i <= int(__detail::_S_max_rope_depth); ++__i)
1223 _S_add_to_forest(__r, __forest);
1224 for (__i = 0; __i <= int(__detail::_S_max_rope_depth); ++__i)
1225 if (0 != __forest[__i])
1228 _Self_destruct_ptr __old(__result);
1230 __result = _S_concat(__forest[__i], __result);
1231 __forest[__i]->_M_unref_nonnil();
1232#if !defined(__GC) && __cpp_exceptions
1239 for(__i = 0; __i <= int(__detail::_S_max_rope_depth); __i++)
1240 _S_unref(__forest[__i]);
1241 __throw_exception_again;
1244 if (__result->_M_depth >
int(__detail::_S_max_rope_depth))
1245 std::__throw_length_error(__N(
"rope::_S_balance"));
1249 template <
class _CharT,
class _Alloc>
1251 rope<_CharT, _Alloc>::
1252 _S_add_to_forest(_RopeRep* __r, _RopeRep** __forest)
1254 if (__r->_M_is_balanced)
1256 _S_add_leaf_to_forest(__r, __forest);
1261 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1263 _S_add_to_forest(__c->_M_left, __forest);
1264 _S_add_to_forest(__c->_M_right, __forest);
1269 template <
class _CharT,
class _Alloc>
1271 rope<_CharT, _Alloc>::
1272 _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest)
1274 _RopeRep* __insertee;
1275 _RopeRep* __too_tiny = 0;
1277 std::size_t __s = __r->_M_size;
1279 for (__i = 0; __s >= _S_min_len[__i+1]; ++__i)
1281 if (0 != __forest[__i])
1284 _Self_destruct_ptr __old(__too_tiny);
1286 __too_tiny = _S_concat_and_set_balanced(__forest[__i],
1288 __forest[__i]->_M_unref_nonnil();
1294 _Self_destruct_ptr __old(__too_tiny);
1296 __insertee = _S_concat_and_set_balanced(__too_tiny, __r);
1302 if (0 != __forest[__i])
1305 _Self_destruct_ptr __old(__insertee);
1307 __insertee = _S_concat_and_set_balanced(__forest[__i],
1309 __forest[__i]->_M_unref_nonnil();
1312 if (__i ==
int(__detail::_S_max_rope_depth)
1313 || __insertee->_M_size < _S_min_len[__i+1])
1315 __forest[__i] = __insertee;
1322 template <
class _CharT,
class _Alloc>
1324 rope<_CharT, _Alloc>::
1325 _S_fetch(_RopeRep* __r, size_type __i)
1327 __GC_CONST _CharT* __cstr = __r->_M_c_string;
1335 case __detail::_S_concat:
1337 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1338 _RopeRep* __left = __c->_M_left;
1339 std::size_t __left_len = __left->_M_size;
1341 if (__i >= __left_len)
1344 __r = __c->_M_right;
1350 case __detail::_S_leaf:
1352 _RopeLeaf* __l = (_RopeLeaf*)__r;
1353 return __l->_M_data[__i];
1355 case __detail::_S_function:
1356 case __detail::_S_substringfn:
1358 _RopeFunction* __f = (_RopeFunction*)__r;
1361 (*(__f->_M_fn))(__i, 1, &__result);
1371 template <
class _CharT,
class _Alloc>
1373 rope<_CharT, _Alloc>::
1374 _S_fetch_ptr(_RopeRep* __r, size_type __i)
1376 _RopeRep* __clrstack[__detail::_S_max_rope_depth];
1377 std::size_t __csptr = 0;
1381 if (__r->_M_ref_count > 1)
1385 case __detail::_S_concat:
1387 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1388 _RopeRep* __left = __c->_M_left;
1389 std::size_t __left_len = __left->_M_size;
1391 if (__c->_M_c_string != 0)
1392 __clrstack[__csptr++] = __c;
1393 if (__i >= __left_len)
1396 __r = __c->_M_right;
1402 case __detail::_S_leaf:
1404 _RopeLeaf* __l = (_RopeLeaf*)__r;
1405 if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0)
1406 __clrstack[__csptr++] = __l;
1410 _RopeRep* __d = __clrstack[__csptr];
1411 __d->_M_free_c_string();
1412 __d->_M_c_string = 0;
1414 return __l->_M_data + __i;
1416 case __detail::_S_function:
1417 case __detail::_S_substringfn:
1428 template <
class _CharT,
class _Alloc>
1430 rope<_CharT, _Alloc>::
1431 _S_compare (
const _RopeRep* __left,
const _RopeRep* __right)
1433 std::size_t __left_len;
1434 std::size_t __right_len;
1440 __left_len = __left->_M_size;
1441 __right_len = __right->_M_size;
1442 if (__detail::_S_leaf == __left->_M_tag)
1444 _RopeLeaf* __l = (_RopeLeaf*) __left;
1445 if (__detail::_S_leaf == __right->_M_tag)
1447 _RopeLeaf* __r = (_RopeLeaf*) __right;
1449 __l->_M_data + __left_len,
1450 __r->_M_data, __r->_M_data
1455 const_iterator __rstart(__right, 0);
1456 const_iterator __rend(__right, __right_len);
1464 const_iterator __lstart(__left, 0);
1465 const_iterator __lend(__left, __left_len);
1466 if (__detail::_S_leaf == __right->_M_tag)
1468 _RopeLeaf* __r = (_RopeLeaf*) __right;
1470 __r->_M_data, __r->_M_data
1475 const_iterator __rstart(__right, 0);
1476 const_iterator __rend(__right, __right_len);
1484 template <
class _CharT,
class _Alloc>
1485 _Rope_char_ref_proxy<_CharT, _Alloc>&
1486 _Rope_char_ref_proxy<_CharT, _Alloc>::
1487 operator=(_CharT __c)
1489 _RopeRep* __old = _M_root->_M_tree_ptr;
1493 _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos);
1500 _Self_destruct_ptr __left(_My_rope::_S_substring(__old, 0, _M_pos));
1501 _Self_destruct_ptr __right(_My_rope::_S_substring(__old, _M_pos + 1,
1503 _Self_destruct_ptr __result_left(_My_rope::
1504 _S_destr_concat_char_iter(__left,
1507 _RopeRep* __result = _My_rope::_S_concat(__result_left, __right);
1509 _RopeRep::_S_unref(__old);
1511 _M_root->_M_tree_ptr = __result;
1515 template <
class _CharT,
class _Alloc>
1516 inline _Rope_char_ref_proxy<_CharT, _Alloc>::
1517 operator _CharT()
const
1519 if (_M_current_valid)
1522 return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos);
1525 template <
class _CharT,
class _Alloc>
1526 _Rope_char_ptr_proxy<_CharT, _Alloc>
1529 {
return _Rope_char_ptr_proxy<_CharT, _Alloc>(*
this); }
1531 template <
class _CharT,
class _Alloc>
1532 rope<_CharT, _Alloc>::
1533 rope(std::size_t __n, _CharT __c,
const allocator_type& __a)
1536 using std::__uninitialized_fill_n_a;
1538 rope<_CharT,_Alloc> __result;
1539 const std::size_t __exponentiate_threshold = 32;
1540 std::size_t __exponent;
1542 _CharT* __rest_buffer;
1543 _RopeRep* __remainder;
1544 rope<_CharT, _Alloc> __remainder_rope;
1549 __exponent = __n / __exponentiate_threshold;
1550 __rest = __n % __exponentiate_threshold;
1555 __rest_buffer = this->_Data_allocate(_S_rounded_up_size(__rest));
1556 __uninitialized_fill_n_a(__rest_buffer, __rest, __c,
1557 _M_get_allocator());
1558 _S_cond_store_eos(__rest_buffer[__rest]);
1560 { __remainder = _S_new_RopeLeaf(__rest_buffer, __rest,
1561 _M_get_allocator()); }
1564 _RopeRep::__STL_FREE_STRING(__rest_buffer, __rest,
1565 _M_get_allocator());
1566 __throw_exception_again;
1569 __remainder_rope._M_tree_ptr = __remainder;
1570 if (__exponent != 0)
1572 _CharT* __base_buffer =
1573 this->_Data_allocate(_S_rounded_up_size(__exponentiate_threshold));
1574 _RopeLeaf* __base_leaf;
1576 __uninitialized_fill_n_a(__base_buffer, __exponentiate_threshold, __c,
1577 _M_get_allocator());
1578 _S_cond_store_eos(__base_buffer[__exponentiate_threshold]);
1581 __base_leaf = _S_new_RopeLeaf(__base_buffer,
1582 __exponentiate_threshold,
1583 _M_get_allocator());
1587 _RopeRep::__STL_FREE_STRING(__base_buffer,
1588 __exponentiate_threshold,
1589 _M_get_allocator());
1590 __throw_exception_again;
1592 __base_rope._M_tree_ptr = __base_leaf;
1593 if (1 == __exponent)
1594 __result = __base_rope;
1596 __result =
power(__base_rope, __exponent,
1597 _Rope_Concat_fn<_CharT, _Alloc>());
1599 if (0 != __remainder)
1600 __result += __remainder_rope;
1603 __result = __remainder_rope;
1605 this->_M_tree_ptr = __result._M_tree_ptr;
1606 this->_M_tree_ptr->_M_ref_nonnil();
1609 template<
class _CharT,
class _Alloc>
1611 rope<_CharT, _Alloc>::_S_empty_c_str[1];
1613 template<
class _CharT,
class _Alloc>
1615 rope<_CharT, _Alloc>::
1618 if (0 == this->_M_tree_ptr)
1620 _S_empty_c_str[0] = _S_eos((_CharT*)0);
1622 return _S_empty_c_str;
1624 __gthread_mutex_lock (&this->_M_tree_ptr->_M_c_string_lock);
1625 __GC_CONST _CharT* __result = this->_M_tree_ptr->_M_c_string;
1628 std::size_t __s = size();
1629 __result = this->_Data_allocate(__s + 1);
1630 _S_flatten(this->_M_tree_ptr, __result);
1631 __result[__s] = _S_eos((_CharT*)0);
1632 this->_M_tree_ptr->_M_c_string = __result;
1634 __gthread_mutex_unlock (&this->_M_tree_ptr->_M_c_string_lock);
1638 template<
class _CharT,
class _Alloc>
1639 const _CharT* rope<_CharT, _Alloc>::
1640 replace_with_c_str()
1642 if (0 == this->_M_tree_ptr)
1644 _S_empty_c_str[0] = _S_eos((_CharT*)0);
1645 return _S_empty_c_str;
1647 __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string;
1648 if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag
1649 && 0 != __old_c_string)
1650 return(__old_c_string);
1651 std::size_t __s = size();
1652 _CharT* __result = this->_Data_allocate(_S_rounded_up_size(__s));
1653 _S_flatten(this->_M_tree_ptr, __result);
1654 __result[__s] = _S_eos((_CharT*)0);
1655 this->_M_tree_ptr->_M_unref_nonnil();
1656 this->_M_tree_ptr = _S_new_RopeLeaf(__result, __s,
1657 this->_M_get_allocator());
1663 template<
class _Rope_iterator>
1665 _Rope_rotate(_Rope_iterator __first,
1666 _Rope_iterator __middle,
1667 _Rope_iterator __last)
1669 typedef typename _Rope_iterator::value_type _CharT;
1670 typedef typename _Rope_iterator::_allocator_type _Alloc;
1672 rope<_CharT, _Alloc>& __r(__first.container());
1673 rope<_CharT, _Alloc> __prefix = __r.substr(0, __first.index());
1674 rope<_CharT, _Alloc> __suffix =
1675 __r.substr(__last.index(), __r.size() - __last.index());
1676 rope<_CharT, _Alloc> __part1 =
1677 __r.substr(__middle.index(), __last.index() - __middle.index());
1678 rope<_CharT, _Alloc> __part2 =
1679 __r.substr(__first.index(), __middle.index() - __first.index());
1686#if !defined(__GNUC__)
1689 rotate(_Rope_iterator<
char, __STL_DEFAULT_ALLOCATOR(
char)> __first,
1690 _Rope_iterator<
char, __STL_DEFAULT_ALLOCATOR(
char)> __middle,
1691 _Rope_iterator<
char, __STL_DEFAULT_ALLOCATOR(
char)> __last)
1692 { _Rope_rotate(__first, __middle, __last); }
1704 rotate(_Rope_iterator<
wchar_t, __STL_DEFAULT_ALLOCATOR(
char)> __first,
1705 _Rope_iterator<
wchar_t, __STL_DEFAULT_ALLOCATOR(
char)> __middle,
1706 _Rope_iterator<
wchar_t, __STL_DEFAULT_ALLOCATOR(
char)> __last)
1707 { _Rope_rotate(__first, __middle, __last); }
1710_GLIBCXX_END_NAMESPACE_VERSION
_Tp power(_Tp __x, _Integer __n, _MonoidOperation __monoid_op)
int lexicographical_compare_3way(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
memcmp on steroids.
_ForwardIterator uninitialized_copy_n(_InputIterator __first, _Size __n, _ForwardIterator __result)
Copies the range [first,first+n) into result.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
basic_ostream< _Ch_type, _Ch_traits > & operator<<(basic_ostream< _Ch_type, _Ch_traits > &__os, const sub_match< _Bi_iter > &__m)
Inserts a matched string into an output stream.
bitset< _Nb > operator&(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
void _Destroy(_ForwardIterator __first, _ForwardIterator __last, _Allocator &__alloc)
GNU extensions for public use.
constexpr _Iterator __base(_Iterator __it)
char_type fill() const
Retrieves the empty character.
Template class basic_ostream.
__ostream_type & put(char_type __c)
Simple insertion.
fmtflags flags() const
Access to format flags.
streamsize width() const
Flags access.
static const fmtflags left
Adds fill characters on the right (final positions) of certain generated output. (I....