51 namespace __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>::
~_Rope_RopeConcatenation();
386 this->_C_deallocate(__c, 1);
389 case __detail::_S_function:
391 _Rope_RopeFunction<_CharT, _Alloc>* __f
392 = (_Rope_RopeFunction<_CharT, _Alloc>*)
this;
393 __f->_Rope_RopeFunction<_CharT, _Alloc>::~_Rope_RopeFunction();
394 this->_F_deallocate(__f, 1);
397 case __detail::_S_substringfn:
399 _Rope_RopeSubstring<_CharT, _Alloc>* __ss =
400 (_Rope_RopeSubstring<_CharT, _Alloc>*)
this;
401 __ss->_Rope_RopeSubstring<_CharT, _Alloc>::
~_Rope_RopeSubstring();
402 this->_S_deallocate(__ss, 1);
409 template <
class _CharT,
class _Alloc>
411 _Rope_RopeRep<_CharT, _Alloc>::
412 _S_free_string(
const _CharT*, std::size_t, allocator_type)
419 template <
class _CharT,
class _Alloc>
420 typename rope<_CharT, _Alloc>::_RopeLeaf*
421 rope<_CharT, _Alloc>::
422 _S_leaf_concat_char_iter(_RopeLeaf* __r,
const _CharT* __iter,
425 std::size_t __old_len = __r->_M_size;
426 _CharT* __new_data = (_CharT*)
427 rope::_Data_allocate(_S_rounded_up_size(__old_len + __len));
432 _S_cond_store_eos(__new_data[__old_len + __len]);
435 __result = _S_new_RopeLeaf(__new_data, __old_len + __len,
436 __r->_M_get_allocator());
440 _RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len,
441 __r->_M_get_allocator());
442 __throw_exception_again;
449 template <
class _CharT,
class _Alloc>
450 typename rope<_CharT,_Alloc>::_RopeLeaf*
451 rope<_CharT, _Alloc>::
452 _S_destr_leaf_concat_char_iter(_RopeLeaf* __r,
const _CharT* __iter,
455 if (__r->_M_ref_count > 1)
456 return _S_leaf_concat_char_iter(__r, __iter, __len);
457 std::size_t __old_len = __r->_M_size;
458 if (_S_allocated_capacity(__old_len) >= __old_len + __len)
463 if (_S_is_basic_char_type((_CharT*)0))
464 _S_cond_store_eos(__r->_M_data[__old_len + __len]);
465 else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string)
467 __r->_M_free_c_string();
468 __r->_M_c_string = 0;
470 __r->_M_size = __old_len + __len;
471 __r->_M_ref_count = 2;
476 _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len);
485 template <
class _CharT,
class _Alloc>
486 typename rope<_CharT, _Alloc>::_RopeRep*
487 rope<_CharT, _Alloc>::
488 _S_tree_concat(_RopeRep* __left, _RopeRep* __right)
491 _RopeConcatenation* __result = _S_new_RopeConcatenation(__left, __right,
494 size_t __depth = __result->_M_depth;
497 && (__result->_M_size < 1000
498 || __depth >
size_t(__detail::_S_max_rope_depth)))
500 _RopeRep* __balanced;
504 __balanced = _S_balance(__result);
505 __result->_M_unref_nonnil();
509 rope::_C_deallocate(__result,1);
510 __throw_exception_again;
522 template <
class _CharT,
class _Alloc>
523 typename rope<_CharT, _Alloc>::_RopeRep*
524 rope<_CharT, _Alloc>::
525 _S_concat_char_iter(_RopeRep* __r,
const _CharT*__s, std::size_t __slen,
536 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __a);
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;
565 _RopeRep* __nright = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __a);
568 __r->_M_ref_nonnil();
569 __result = _S_tree_concat(__r, __nright);
575 __throw_exception_again;
581 template <
class _CharT,
class _Alloc>
582 typename rope<_CharT,_Alloc>::_RopeRep*
583 rope<_CharT,_Alloc>::
584 _S_destr_concat_char_iter(_RopeRep* __r,
const _CharT* __s,
585 std::size_t __slen, allocator_type& __a)
590 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __a);
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, __a);
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;
631 _RopeRep* __right = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __a);
632 __r->_M_ref_nonnil();
634 { __result = _S_tree_concat(__r, __right); }
639 __throw_exception_again;
645 template <
class _CharT,
class _Alloc>
646 typename rope<_CharT, _Alloc>::_RopeRep*
647 rope<_CharT, _Alloc>::
648 _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, std::size_t __start, std::size_t __endp1)
717 size_t __len =
__base->_M_size;
719 const size_t __lazy_threshold = 128;
721 if (__endp1 >= __len)
733 __adj_endp1 = __endp1;
737 case __detail::_S_concat:
739 _RopeConcatenation* __c = (_RopeConcatenation*)
__base;
740 _RopeRep* __left = __c->_M_left;
741 _RopeRep* __right = __c->_M_right;
742 size_t __left_len = __left->_M_size;
745 if (__adj_endp1 <= __left_len)
746 return _S_substring(__left, __start, __endp1);
747 else if (__start >= __left_len)
748 return _S_substring(__right, __start - __left_len,
749 __adj_endp1 - __left_len);
750 _Self_destruct_ptr __left_result(_S_substring(__left,
753 _Self_destruct_ptr __right_result(_S_substring(__right, 0,
756 __result = _S_concat(__left_result, __right_result);
759 case __detail::_S_leaf:
761 _RopeLeaf* __l = (_RopeLeaf*)
__base;
764 if (__start >= __adj_endp1)
766 __result_len = __adj_endp1 - __start;
767 if (__result_len > __lazy_threshold)
770 const _CharT* __section = __l->_M_data + __start;
771 __result = _S_new_RopeLeaf(__section, __result_len,
772 __base->_M_get_allocator());
773 __result->_M_c_string = 0;
776 __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__l->_M_data + __start,
783 case __detail::_S_substringfn:
786 _RopeSubstring* __old = (_RopeSubstring*)
__base;
788 if (__start >= __adj_endp1)
790 __result_len = __adj_endp1 - __start;
791 if (__result_len > __lazy_threshold)
793 _RopeSubstring* __result =
794 _S_new_RopeSubstring(__old->_M_base,
795 __start + __old->_M_start,
796 __adj_endp1 - __start,
797 __base->_M_get_allocator());
802 case __detail::_S_function:
804 _RopeFunction* __f = (_RopeFunction*)
__base;
807 if (__start >= __adj_endp1)
809 __result_len = __adj_endp1 - __start;
811 if (__result_len > __lazy_threshold)
813 __section = (_CharT*)
814 rope::_Data_allocate(_S_rounded_up_size(__result_len));
816 { (*(__f->_M_fn))(__start, __result_len, __section); }
819 _RopeRep::__STL_FREE_STRING(__section, __result_len,
820 __base->_M_get_allocator());
821 __throw_exception_again;
823 _S_cond_store_eos(__section[__result_len]);
824 return _S_new_RopeLeaf(__section, __result_len,
825 __base->_M_get_allocator());
831 return _S_new_RopeSubstring(
__base, __start, __adj_endp1 - __start,
832 __base->_M_get_allocator());
836 template<
class _CharT>
837 class _Rope_flatten_char_consumer
838 :
public _Rope_char_consumer<_CharT>
844 _Rope_flatten_char_consumer(_CharT* __buffer)
845 { _M_buf_ptr = __buffer; }
847 ~_Rope_flatten_char_consumer() {}
850 operator()(
const _CharT* __leaf, std::size_t __n)
858 template<
class _CharT>
859 class _Rope_find_char_char_consumer
860 :
public _Rope_char_consumer<_CharT>
865 std::size_t _M_count;
867 _Rope_find_char_char_consumer(_CharT __p)
868 : _M_pattern(__p), _M_count(0) {}
870 ~_Rope_find_char_char_consumer() {}
873 operator()(
const _CharT* __leaf, std::size_t __n)
876 for (__i = 0; __i < __n; __i++)
878 if (__leaf[__i] == _M_pattern)
884 _M_count += __n;
return true;
888 template<
class _CharT,
class _Traits>
890 class _Rope_insert_char_consumer
891 :
public _Rope_char_consumer<_CharT>
895 _Insert_ostream& _M_o;
897 _Rope_insert_char_consumer(_Insert_ostream& __writer)
899 ~_Rope_insert_char_consumer() { }
901 bool operator() (
const _CharT* __leaf, std::size_t __n);
905 template<
class _CharT,
class _Traits>
907 _Rope_insert_char_consumer<_CharT, _Traits>::
908 operator()(
const _CharT* __leaf, std::size_t __n)
912 for (__i = 0; __i < __n; __i++)
913 _M_o.put(__leaf[__i]);
917 template <
class _CharT,
class _Alloc>
919 rope<_CharT, _Alloc>::
920 _S_apply_to_pieces(_Rope_char_consumer<_CharT>& __c,
const _RopeRep* __r,
921 std::size_t __begin, std::size_t __end)
928 case __detail::_S_concat:
930 _RopeConcatenation* __conc = (_RopeConcatenation*)__r;
931 _RopeRep* __left = __conc->_M_left;
932 size_t __left_len = __left->_M_size;
933 if (__begin < __left_len)
935 size_t __left_end =
std::min(__left_len, __end);
936 if (!_S_apply_to_pieces(__c, __left, __begin, __left_end))
939 if (__end > __left_len)
941 _RopeRep* __right = __conc->_M_right;
942 size_t __right_start =
std::max(__left_len, __begin);
943 if (!_S_apply_to_pieces(__c, __right,
944 __right_start - __left_len,
950 case __detail::_S_leaf:
952 _RopeLeaf* __l = (_RopeLeaf*)__r;
953 return __c(__l->_M_data + __begin, __end - __begin);
955 case __detail::_S_function:
956 case __detail::_S_substringfn:
958 _RopeFunction* __f = (_RopeFunction*)__r;
959 size_t __len = __end - __begin;
962 (_CharT*)_Alloc().allocate(__len *
sizeof(_CharT));
965 (*(__f->_M_fn))(__begin, __len, __buffer);
966 __result = __c(__buffer, __len);
967 _Alloc().deallocate(__buffer, __len *
sizeof(_CharT));
971 _Alloc().deallocate(__buffer, __len *
sizeof(_CharT));
972 __throw_exception_again;
981 template<
class _CharT,
class _Traits>
985 char __f = __o.
fill();
988 for (__i = 0; __i < __n; __i++)
993 template <
class _CharT>
995 _Rope_is_simple(_CharT*)
999 _Rope_is_simple(
char*)
1003 _Rope_is_simple(
wchar_t*)
1006 template<
class _CharT,
class _Traits,
class _Alloc>
1008 operator<<(std::basic_ostream<_CharT, _Traits>& __o,
1009 const rope<_CharT, _Alloc>& __r)
1012 size_t __w = __o.
width();
1015 size_t __rope_len = __r.size();
1016 _Rope_insert_char_consumer<_CharT, _Traits> __c(__o);
1017 bool __is_simple = _Rope_is_simple((_CharT*)0);
1019 if (__rope_len < __w)
1020 __pad_len = __w - __rope_len;
1025 __o.
width(__w / __rope_len);
1028 if (__is_simple && !__left && __pad_len > 0)
1029 _Rope_fill(__o, __pad_len);
1030 __r.apply_to_pieces(0, __r.size(), __c);
1031 if (__is_simple && __left && __pad_len > 0)
1032 _Rope_fill(__o, __pad_len);
1040 __throw_exception_again;
1045 template <
class _CharT,
class _Alloc>
1047 rope<_CharT, _Alloc>::
1048 _S_flatten(_RopeRep* __r, std::size_t __start, std::size_t __len,
1051 _Rope_flatten_char_consumer<_CharT> __c(__buffer);
1052 _S_apply_to_pieces(__c, __r, __start, __start + __len);
1053 return(__buffer + __len);
1056 template <
class _CharT,
class _Alloc>
1058 rope<_CharT, _Alloc>::
1059 find(_CharT __pattern, std::size_t __start)
const 1061 _Rope_find_char_char_consumer<_CharT> __c(__pattern);
1062 _S_apply_to_pieces(__c, this->_M_tree_ptr, __start,
size());
1063 size_type __result_pos = __start + __c._M_count;
1064 #ifndef __STL_OLD_ROPE_SEMANTICS 1065 if (__result_pos ==
size())
1066 __result_pos = npos;
1068 return __result_pos;
1071 template <
class _CharT,
class _Alloc>
1073 rope<_CharT, _Alloc>::
1074 _S_flatten(_RopeRep* __r, _CharT* __buffer)
1080 case __detail::_S_concat:
1082 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1083 _RopeRep* __left = __c->_M_left;
1084 _RopeRep* __right = __c->_M_right;
1085 _CharT* __rest = _S_flatten(__left, __buffer);
1086 return _S_flatten(__right, __rest);
1088 case __detail::_S_leaf:
1090 _RopeLeaf* __l = (_RopeLeaf*)__r;
1091 return copy_n(__l->_M_data, __l->_M_size, __buffer).second;
1093 case __detail::_S_function:
1094 case __detail::_S_substringfn:
1098 _RopeFunction* __f = (_RopeFunction*)__r;
1099 (*(__f->_M_fn))(0, __f->_M_size, __buffer);
1100 return __buffer + __f->_M_size;
1108 template <
class _CharT,
class _Alloc>
1110 rope<_CharT, _Alloc>::
1111 _S_dump(_RopeRep* __r,
int __indent)
1114 for (
int __i = 0; __i < __indent; __i++)
1121 if (__detail::_S_concat == __r->_M_tag)
1123 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1124 _RopeRep* __left = __c->_M_left;
1125 _RopeRep* __right = __c->_M_right;
1128 printf(
"Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
1129 __r, __r->_M_depth, __r->_M_size,
1130 __r->_M_is_balanced?
"" :
"not");
1132 printf(
"Concatenation %p (rc = %ld, depth = %d, " 1133 "len = %ld, %s balanced)\n",
1134 __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size,
1135 __r->_M_is_balanced?
"" :
"not");
1137 _S_dump(__left, __indent + 2);
1138 _S_dump(__right, __indent + 2);
1145 switch (__r->_M_tag)
1147 case __detail::_S_leaf:
1150 case __detail::_S_function:
1151 __kind =
"Function";
1153 case __detail::_S_substringfn:
1154 __kind =
"Function representing substring";
1157 __kind =
"(corrupted kind field!)";
1160 printf(
"%s %p (depth = %d, len = %ld) ",
1161 __kind, __r, __r->_M_depth, __r->_M_size);
1163 printf(
"%s %p (rc = %ld, depth = %d, len = %ld) ",
1164 __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size);
1166 if (_S_is_one_byte_char_type((_CharT*)0))
1168 const int __max_len = 40;
1169 _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len));
1170 _CharT __buffer[__max_len + 1];
1171 bool __too_big = __r->_M_size > __prefix->_M_size;
1173 _S_flatten(__prefix, __buffer);
1174 __buffer[__prefix->_M_size] = _S_eos((_CharT*)0);
1175 printf(
"%s%s\n", (
char*)__buffer,
1176 __too_big?
"...\n" :
"\n");
1183 template <
class _CharT,
class _Alloc>
1185 rope<_CharT, _Alloc>::
1186 _S_min_len[int(__detail::_S_max_rope_depth) + 1] = {
1187 1, 2, 3, 5, 8, 13, 21,
1188 34, 55, 89, 144, 233, 377,
1189 610, 987, 1597, 2584, 4181,
1190 6765, 10946, 17711, 28657, 46368,
1191 75025, 121393, 196418, 317811,
1192 514229, 832040, 1346269, 2178309,
1193 3524578, 5702887, 9227465, 14930352,
1194 24157817, 39088169, 63245986, 102334155,
1195 165580141, 267914296, 433494437,
1196 701408733, 1134903170, 1836311903,
1200 template <
class _CharT,
class _Alloc>
1201 typename rope<_CharT, _Alloc>::_RopeRep*
1202 rope<_CharT, _Alloc>::
1203 _S_balance(_RopeRep* __r)
1205 _RopeRep* __forest[int(__detail::_S_max_rope_depth) + 1];
1206 _RopeRep* __result = 0;
1214 for (__i = 0; __i <= int(__detail::_S_max_rope_depth); ++__i)
1218 _S_add_to_forest(__r, __forest);
1219 for (__i = 0; __i <= int(__detail::_S_max_rope_depth); ++__i)
1220 if (0 != __forest[__i])
1223 _Self_destruct_ptr __old(__result);
1225 __result = _S_concat(__forest[__i], __result);
1226 __forest[__i]->_M_unref_nonnil();
1227 #if !defined(__GC) && __cpp_exceptions 1236 for(__i = 0; __i <= int(__detail::_S_max_rope_depth); __i++)
1237 _S_unref(__forest[__i]);
1238 __throw_exception_again;
1241 if (__result->_M_depth >
int(__detail::_S_max_rope_depth))
1242 std::__throw_length_error(__N(
"rope::_S_balance"));
1246 template <
class _CharT,
class _Alloc>
1248 rope<_CharT, _Alloc>::
1249 _S_add_to_forest(_RopeRep* __r, _RopeRep** __forest)
1251 if (__r->_M_is_balanced)
1253 _S_add_leaf_to_forest(__r, __forest);
1258 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1260 _S_add_to_forest(__c->_M_left, __forest);
1261 _S_add_to_forest(__c->_M_right, __forest);
1266 template <
class _CharT,
class _Alloc>
1268 rope<_CharT, _Alloc>::
1269 _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest)
1271 _RopeRep* __insertee;
1272 _RopeRep* __too_tiny = 0;
1274 std::size_t __s = __r->_M_size;
1276 for (__i = 0; __s >= _S_min_len[__i+1]; ++__i)
1278 if (0 != __forest[__i])
1281 _Self_destruct_ptr __old(__too_tiny);
1283 __too_tiny = _S_concat_and_set_balanced(__forest[__i],
1285 __forest[__i]->_M_unref_nonnil();
1291 _Self_destruct_ptr __old(__too_tiny);
1293 __insertee = _S_concat_and_set_balanced(__too_tiny, __r);
1299 if (0 != __forest[__i])
1302 _Self_destruct_ptr __old(__insertee);
1304 __insertee = _S_concat_and_set_balanced(__forest[__i],
1306 __forest[__i]->_M_unref_nonnil();
1309 if (__i ==
int(__detail::_S_max_rope_depth)
1310 || __insertee->_M_size < _S_min_len[__i+1])
1312 __forest[__i] = __insertee;
1319 template <
class _CharT,
class _Alloc>
1321 rope<_CharT, _Alloc>::
1322 _S_fetch(_RopeRep* __r, size_type __i)
1324 __GC_CONST _CharT* __cstr = __r->_M_c_string;
1332 case __detail::_S_concat:
1334 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1335 _RopeRep* __left = __c->_M_left;
1336 std::size_t __left_len = __left->_M_size;
1338 if (__i >= __left_len)
1341 __r = __c->_M_right;
1347 case __detail::_S_leaf:
1349 _RopeLeaf* __l = (_RopeLeaf*)__r;
1350 return __l->_M_data[__i];
1352 case __detail::_S_function:
1353 case __detail::_S_substringfn:
1355 _RopeFunction* __f = (_RopeFunction*)__r;
1358 (*(__f->_M_fn))(__i, 1, &__result);
1368 template <
class _CharT,
class _Alloc>
1370 rope<_CharT, _Alloc>::
1371 _S_fetch_ptr(_RopeRep* __r, size_type __i)
1373 _RopeRep* __clrstack[__detail::_S_max_rope_depth];
1374 std::size_t __csptr = 0;
1378 if (__r->_M_ref_count > 1)
1382 case __detail::_S_concat:
1384 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1385 _RopeRep* __left = __c->_M_left;
1386 std::size_t __left_len = __left->_M_size;
1388 if (__c->_M_c_string != 0)
1389 __clrstack[__csptr++] = __c;
1390 if (__i >= __left_len)
1393 __r = __c->_M_right;
1399 case __detail::_S_leaf:
1401 _RopeLeaf* __l = (_RopeLeaf*)__r;
1402 if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0)
1403 __clrstack[__csptr++] = __l;
1407 _RopeRep* __d = __clrstack[__csptr];
1408 __d->_M_free_c_string();
1409 __d->_M_c_string = 0;
1411 return __l->_M_data + __i;
1413 case __detail::_S_function:
1414 case __detail::_S_substringfn:
1425 template <
class _CharT,
class _Alloc>
1427 rope<_CharT, _Alloc>::
1428 _S_compare (
const _RopeRep* __left,
const _RopeRep* __right)
1430 std::size_t __left_len;
1431 std::size_t __right_len;
1437 __left_len = __left->_M_size;
1438 __right_len = __right->_M_size;
1439 if (__detail::_S_leaf == __left->_M_tag)
1441 _RopeLeaf* __l = (_RopeLeaf*) __left;
1442 if (__detail::_S_leaf == __right->_M_tag)
1444 _RopeLeaf* __r = (_RopeLeaf*) __right;
1446 __l->_M_data + __left_len,
1447 __r->_M_data, __r->_M_data
1452 const_iterator __rstart(__right, 0);
1453 const_iterator __rend(__right, __right_len);
1461 const_iterator __lstart(__left, 0);
1462 const_iterator __lend(__left, __left_len);
1463 if (__detail::_S_leaf == __right->_M_tag)
1465 _RopeLeaf* __r = (_RopeLeaf*) __right;
1467 __r->_M_data, __r->_M_data
1472 const_iterator __rstart(__right, 0);
1473 const_iterator __rend(__right, __right_len);
1481 template <
class _CharT,
class _Alloc>
1482 _Rope_char_ref_proxy<_CharT, _Alloc>&
1483 _Rope_char_ref_proxy<_CharT, _Alloc>::
1484 operator=(_CharT __c)
1486 _RopeRep* __old = _M_root->_M_tree_ptr;
1490 _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos);
1497 _Self_destruct_ptr __left(_My_rope::_S_substring(__old, 0, _M_pos));
1498 _Self_destruct_ptr __right(_My_rope::_S_substring(__old, _M_pos + 1,
1500 typename _RopeRep::allocator_type __a = _M_root->_M_get_allocator();
1501 _Self_destruct_ptr __result_left(_My_rope::
1502 _S_destr_concat_char_iter(__left,
1506 _RopeRep* __result = _My_rope::_S_concat(__result_left, __right);
1508 _RopeRep::_S_unref(__old);
1510 _M_root->_M_tree_ptr = __result;
1514 template <
class _CharT,
class _Alloc>
1515 inline _Rope_char_ref_proxy<_CharT, _Alloc>::
1516 operator _CharT()
const 1518 if (_M_current_valid)
1521 return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos);
1524 template <
class _CharT,
class _Alloc>
1525 _Rope_char_ptr_proxy<_CharT, _Alloc>
1528 {
return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this); }
1530 template <
class _CharT,
class _Alloc>
1531 rope<_CharT, _Alloc>::
1532 rope(std::size_t __n, _CharT __c,
const allocator_type& __a)
1535 using std::__uninitialized_fill_n_a;
1537 rope<_CharT,_Alloc> __result;
1538 const std::size_t __exponentiate_threshold = 32;
1539 std::size_t __exponent;
1541 _CharT* __rest_buffer;
1542 _RopeRep* __remainder;
1543 rope<_CharT, _Alloc> __remainder_rope;
1548 __exponent = __n / __exponentiate_threshold;
1549 __rest = __n % __exponentiate_threshold;
1554 __rest_buffer = this->_Data_allocate(_S_rounded_up_size(__rest));
1555 __uninitialized_fill_n_a(__rest_buffer, __rest, __c,
1556 _M_get_allocator());
1557 _S_cond_store_eos(__rest_buffer[__rest]);
1559 { __remainder = _S_new_RopeLeaf(__rest_buffer, __rest,
1560 _M_get_allocator()); }
1563 _RopeRep::__STL_FREE_STRING(__rest_buffer, __rest,
1564 _M_get_allocator());
1565 __throw_exception_again;
1568 __remainder_rope._M_tree_ptr = __remainder;
1569 if (__exponent != 0)
1571 _CharT* __base_buffer =
1572 this->_Data_allocate(_S_rounded_up_size(__exponentiate_threshold));
1573 _RopeLeaf* __base_leaf;
1575 __uninitialized_fill_n_a(__base_buffer, __exponentiate_threshold, __c,
1576 _M_get_allocator());
1577 _S_cond_store_eos(__base_buffer[__exponentiate_threshold]);
1580 __base_leaf = _S_new_RopeLeaf(__base_buffer,
1581 __exponentiate_threshold,
1582 _M_get_allocator());
1586 _RopeRep::__STL_FREE_STRING(__base_buffer,
1587 __exponentiate_threshold,
1588 _M_get_allocator());
1589 __throw_exception_again;
1591 __base_rope._M_tree_ptr = __base_leaf;
1592 if (1 == __exponent)
1593 __result = __base_rope;
1595 __result =
power(__base_rope, __exponent,
1596 _Rope_Concat_fn<_CharT, _Alloc>());
1598 if (0 != __remainder)
1599 __result += __remainder_rope;
1602 __result = __remainder_rope;
1604 this->_M_tree_ptr = __result._M_tree_ptr;
1605 this->_M_tree_ptr->_M_ref_nonnil();
1608 template<
class _CharT,
class _Alloc>
1610 rope<_CharT, _Alloc>::_S_empty_c_str[1];
1612 template<
class _CharT,
class _Alloc>
1614 rope<_CharT, _Alloc>::
1617 if (0 == this->_M_tree_ptr)
1619 _S_empty_c_str[0] = _S_eos((_CharT*)0);
1621 return _S_empty_c_str;
1623 __gthread_mutex_lock (&this->_M_tree_ptr->_M_c_string_lock);
1624 __GC_CONST _CharT* __result = this->_M_tree_ptr->_M_c_string;
1627 std::size_t __s =
size();
1628 __result = this->_Data_allocate(__s + 1);
1629 _S_flatten(this->_M_tree_ptr, __result);
1630 __result[__s] = _S_eos((_CharT*)0);
1631 this->_M_tree_ptr->_M_c_string = __result;
1633 __gthread_mutex_unlock (&this->_M_tree_ptr->_M_c_string_lock);
1637 template<
class _CharT,
class _Alloc>
1638 const _CharT* rope<_CharT, _Alloc>::
1639 replace_with_c_str()
1641 if (0 == this->_M_tree_ptr)
1643 _S_empty_c_str[0] = _S_eos((_CharT*)0);
1644 return _S_empty_c_str;
1646 __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string;
1647 if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag
1648 && 0 != __old_c_string)
1649 return(__old_c_string);
1650 std::size_t __s =
size();
1651 _CharT* __result = this->_Data_allocate(_S_rounded_up_size(__s));
1652 _S_flatten(this->_M_tree_ptr, __result);
1653 __result[__s] = _S_eos((_CharT*)0);
1654 this->_M_tree_ptr->_M_unref_nonnil();
1655 this->_M_tree_ptr = _S_new_RopeLeaf(__result, __s,
1656 this->_M_get_allocator());
1662 template<
class _Rope_iterator>
1664 _Rope_rotate(_Rope_iterator __first,
1665 _Rope_iterator __middle,
1666 _Rope_iterator __last)
1668 typedef typename _Rope_iterator::value_type _CharT;
1669 typedef typename _Rope_iterator::_allocator_type _Alloc;
1671 rope<_CharT, _Alloc>& __r(__first.container());
1672 rope<_CharT, _Alloc> __prefix = __r.substr(0, __first.index());
1673 rope<_CharT, _Alloc> __suffix =
1674 __r.substr(__last.index(), __r.size() - __last.index());
1675 rope<_CharT, _Alloc> __part1 =
1676 __r.substr(__middle.index(), __last.index() - __middle.index());
1677 rope<_CharT, _Alloc> __part2 =
1678 __r.substr(__first.index(), __middle.index() - __first.index());
1685 #if !defined(__GNUC__) 1688 rotate(_Rope_iterator<
char, __STL_DEFAULT_ALLOCATOR(
char)> __first,
1689 _Rope_iterator<
char, __STL_DEFAULT_ALLOCATOR(
char)> __middle,
1690 _Rope_iterator<
char, __STL_DEFAULT_ALLOCATOR(
char)> __last)
1691 { _Rope_rotate(__first, __middle, __last); }
1703 rotate(_Rope_iterator<
wchar_t, __STL_DEFAULT_ALLOCATOR(
char)> __first,
1704 _Rope_iterator<
wchar_t, __STL_DEFAULT_ALLOCATOR(
char)> __middle,
1705 _Rope_iterator<
wchar_t, __STL_DEFAULT_ALLOCATOR(
char)> __last)
1706 { _Rope_rotate(__first, __middle, __last); }
1709 _GLIBCXX_END_NAMESPACE_VERSION
1711 char_type fill() const
Retrieves the empty character.
constexpr const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
constexpr bitset< _Nb > operator &(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
constexpr _Iterator __base(_Iterator __it)
__ostream_type & put(char_type __c)
Simple insertion.
constexpr void _Destroy(_ForwardIterator __first, _ForwardIterator __last)
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
GNU extensions for public use.
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.)
int lexicographical_compare_3way(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
memcmp on steroids.
constexpr auto size(const _Container &__cont) noexcept(noexcept(__cont.size())) -> decltype(__cont.size())
Return the size of a container.
Template class basic_ostream.
streamsize width() const
Flags access.
_ForwardIterator uninitialized_copy_n(_InputIterator __first, _Size __n, _ForwardIterator __result)
Copies the range [first,first+n) into result.
_Tp power(_Tp __x, _Integer __n, _MonoidOperation __monoid_op)
fmtflags flags() const
Access to format flags.