51namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
53_GLIBCXX_BEGIN_NAMESPACE_VERSION
58 using std::__throw_length_error;
60 using std::__uninitialized_fill_n_a;
66 template <
class _CharT,
class _Alloc>
68 _Rope_iterator_base<_CharT, _Alloc>::
69 _S_setbuf(_Rope_iterator_base<_CharT, _Alloc>& __x)
71 const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index];
72 size_t __leaf_pos = __x._M_leaf_pos;
73 size_t __pos = __x._M_current_pos;
75 switch(__leaf->_M_tag)
77 case __detail::_S_leaf:
78 __x._M_buf_start = ((_Rope_RopeLeaf<_CharT, _Alloc>*)__leaf)->_M_data;
79 __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos);
80 __x._M_buf_end = __x._M_buf_start + __leaf->_M_size;
82 case __detail::_S_function:
83 case __detail::_S_substringfn:
85 size_t __len = _S_iterator_buf_len;
86 size_t __buf_start_pos = __leaf_pos;
87 size_t __leaf_end = __leaf_pos + __leaf->_M_size;
88 char_producer<_CharT>* __fn = ((_Rope_RopeFunction<_CharT,
89 _Alloc>*)__leaf)->_M_fn;
90 if (__buf_start_pos + __len <= __pos)
92 __buf_start_pos = __pos - __len / 4;
93 if (__buf_start_pos + __len > __leaf_end)
94 __buf_start_pos = __leaf_end - __len;
96 if (__buf_start_pos + __len > __leaf_end)
97 __len = __leaf_end - __buf_start_pos;
98 (*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf);
99 __x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos);
100 __x._M_buf_start = __x._M_tmp_buf;
101 __x._M_buf_end = __x._M_tmp_buf + __len;
111 template <
class _CharT,
class _Alloc>
113 _Rope_iterator_base<_CharT, _Alloc>::
114 _S_setcache(_Rope_iterator_base<_CharT, _Alloc>& __x)
116 const _RopeRep* __path[int(__detail::_S_max_rope_depth) + 1];
117 const _RopeRep* __curr_rope;
118 int __curr_depth = -1;
119 size_t __curr_start_pos = 0;
120 size_t __pos = __x._M_current_pos;
121 unsigned char __dirns = 0;
123 if (__pos >= __x._M_root->_M_size)
128 __curr_rope = __x._M_root;
129 if (0 != __curr_rope->_M_c_string)
132 __x._M_buf_start = __curr_rope->_M_c_string;
133 __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size;
134 __x._M_buf_ptr = __curr_rope->_M_c_string + __pos;
135 __x._M_path_end[0] = __curr_rope;
136 __x._M_leaf_index = 0;
143 __path[__curr_depth] = __curr_rope;
144 switch(__curr_rope->_M_tag)
146 case __detail::_S_leaf:
147 case __detail::_S_function:
148 case __detail::_S_substringfn:
149 __x._M_leaf_pos = __curr_start_pos;
151 case __detail::_S_concat:
153 _Rope_RopeConcatenation<_CharT, _Alloc>* __c =
154 (_Rope_RopeConcatenation<_CharT, _Alloc>*)__curr_rope;
155 _RopeRep* __left = __c->_M_left;
156 size_t __left_len = __left->_M_size;
159 if (__pos >= __curr_start_pos + __left_len)
162 __curr_rope = __c->_M_right;
163 __curr_start_pos += __left_len;
166 __curr_rope = __left;
175 int __j = __curr_depth + 1 - int(_S_path_cache_len);
177 if (__j < 0) __j = 0;
178 while (__j <= __curr_depth)
179 __x._M_path_end[++__i] = __path[__j++];
180 __x._M_leaf_index = __i;
182 __x._M_path_directions = __dirns;
188 template <
class _CharT,
class _Alloc>
190 _Rope_iterator_base<_CharT, _Alloc>::
191 _S_setcache_for_incr(_Rope_iterator_base<_CharT, _Alloc>& __x)
193 int __current_index = __x._M_leaf_index;
194 const _RopeRep* __current_node = __x._M_path_end[__current_index];
195 size_t __len = __current_node->_M_size;
196 size_t __node_start_pos = __x._M_leaf_pos;
197 unsigned char __dirns = __x._M_path_directions;
198 _Rope_RopeConcatenation<_CharT, _Alloc>* __c;
200 if (__x._M_current_pos - __node_start_pos < __len)
207 while (--__current_index >= 0)
211 __current_node = __x._M_path_end[__current_index];
212 __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node;
215 __node_start_pos -= __c->_M_left->_M_size;
218 if (__current_index < 0)
224 __current_node = __x._M_path_end[__current_index];
225 __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node;
229 __node_start_pos += __c->_M_left->_M_size;
230 __current_node = __c->_M_right;
231 __x._M_path_end[++__current_index] = __current_node;
233 while (__detail::_S_concat == __current_node->_M_tag)
236 if (
int(_S_path_cache_len) == __current_index)
239 for (__i = 0; __i < int(_S_path_cache_len) - 1; __i++)
240 __x._M_path_end[__i] = __x._M_path_end[__i+1];
244 ((_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node)->_M_left;
245 __x._M_path_end[__current_index] = __current_node;
249 __x._M_leaf_index = __current_index;
250 __x._M_leaf_pos = __node_start_pos;
251 __x._M_path_directions = __dirns;
255 template <
class _CharT,
class _Alloc>
257 _Rope_iterator_base<_CharT, _Alloc>::
260 _M_current_pos += __n;
263 size_t __chars_left = _M_buf_end - _M_buf_ptr;
264 if (__chars_left > __n)
266 else if (__chars_left == __n)
269 _S_setcache_for_incr(*
this);
276 template <
class _CharT,
class _Alloc>
278 _Rope_iterator_base<_CharT, _Alloc>::
283 size_t __chars_left = _M_buf_ptr - _M_buf_start;
284 if (__chars_left >= __n)
289 _M_current_pos -= __n;
292 template <
class _CharT,
class _Alloc>
294 _Rope_iterator<_CharT, _Alloc>::
297 if (_M_root_rope->_M_tree_ptr != this->_M_root)
300 _RopeRep::_S_unref(this->_M_root);
301 this->_M_root = _M_root_rope->_M_tree_ptr;
302 _RopeRep::_S_ref(this->_M_root);
303 this->_M_buf_ptr = 0;
307 template <
class _CharT,
class _Alloc>
309 _Rope_const_iterator<_CharT, _Alloc>::
310 _Rope_const_iterator(
const _Rope_iterator<_CharT, _Alloc>& __x)
311 : _Rope_iterator_base<_CharT, _Alloc>(__x)
314 template <
class _CharT,
class _Alloc>
316 _Rope_iterator<_CharT, _Alloc>::
317 _Rope_iterator(rope<_CharT, _Alloc>& __r,
size_t __pos)
318 : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos),
320 { _RopeRep::_S_ref(this->_M_root); }
322 template <
class _CharT,
class _Alloc>
324 rope<_CharT, _Alloc>::
325 _S_char_ptr_len(
const _CharT* __s)
327 const _CharT* __p = __s;
329 while (!_S_is0(*__p))
337 template <
class _CharT,
class _Alloc>
339 _Rope_RopeRep<_CharT, _Alloc>::
342 _CharT* __cstr = _M_c_string;
345 size_t __size = this->_M_size + 1;
346 _Destroy(__cstr, __cstr + __size, _M_get_allocator());
347 this->_Data_deallocate(__cstr, __size);
351 template <
class _CharT,
class _Alloc>
353 _Rope_RopeRep<_CharT, _Alloc>::
354 _S_free_string(_CharT* __s,
size_t __n, allocator_type& __a)
356 if (!_S_is_basic_char_type((_CharT*)0))
361 _Rope_RopeLeaf<_CharT, _Alloc>::_S_rounded_up_size(__n));
370 template <
class _CharT,
class _Alloc>
372 _Rope_RopeRep<_CharT, _Alloc>::
377 case __detail::_S_leaf:
379 _Rope_RopeLeaf<_CharT, _Alloc>* __l
380 = (_Rope_RopeLeaf<_CharT, _Alloc>*)
this;
381 __l->_Rope_RopeLeaf<_CharT, _Alloc>::~_Rope_RopeLeaf();
382 this->_L_deallocate(__l, 1);
385 case __detail::_S_concat:
387 _Rope_RopeConcatenation<_CharT,_Alloc>* __c
388 = (_Rope_RopeConcatenation<_CharT, _Alloc>*)
this;
389 __c->_Rope_RopeConcatenation<_CharT, _Alloc>::
390 ~_Rope_RopeConcatenation();
391 this->_C_deallocate(__c, 1);
394 case __detail::_S_function:
396 _Rope_RopeFunction<_CharT, _Alloc>* __f
397 = (_Rope_RopeFunction<_CharT, _Alloc>*)
this;
398 __f->_Rope_RopeFunction<_CharT, _Alloc>::~_Rope_RopeFunction();
399 this->_F_deallocate(__f, 1);
402 case __detail::_S_substringfn:
404 _Rope_RopeSubstring<_CharT, _Alloc>* __ss =
405 (_Rope_RopeSubstring<_CharT, _Alloc>*)
this;
406 __ss->_Rope_RopeSubstring<_CharT, _Alloc>::
407 ~_Rope_RopeSubstring();
408 this->_S_deallocate(__ss, 1);
415 template <
class _CharT,
class _Alloc>
417 _Rope_RopeRep<_CharT, _Alloc>::
418 _S_free_string(
const _CharT*,
size_t, allocator_type)
425 template <
class _CharT,
class _Alloc>
426 typename rope<_CharT, _Alloc>::_RopeLeaf*
427 rope<_CharT, _Alloc>::
428 _S_leaf_concat_char_iter(_RopeLeaf* __r,
const _CharT* __iter,
size_t __len)
430 size_t __old_len = __r->_M_size;
431 _CharT* __new_data = (_CharT*)
432 rope::_Data_allocate(_S_rounded_up_size(__old_len + __len));
437 _S_cond_store_eos(__new_data[__old_len + __len]);
440 __result = _S_new_RopeLeaf(__new_data, __old_len + __len,
441 __r->_M_get_allocator());
445 _RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len,
446 __r->_M_get_allocator());
447 __throw_exception_again;
454 template <
class _CharT,
class _Alloc>
455 typename rope<_CharT,_Alloc>::_RopeLeaf*
456 rope<_CharT, _Alloc>::
457 _S_destr_leaf_concat_char_iter(_RopeLeaf* __r,
const _CharT* __iter,
460 if (__r->_M_ref_count > 1)
461 return _S_leaf_concat_char_iter(__r, __iter, __len);
462 size_t __old_len = __r->_M_size;
463 if (_S_allocated_capacity(__old_len) >= __old_len + __len)
468 if (_S_is_basic_char_type((_CharT*)0))
469 _S_cond_store_eos(__r->_M_data[__old_len + __len]);
470 else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string)
472 __r->_M_free_c_string();
473 __r->_M_c_string = 0;
475 __r->_M_size = __old_len + __len;
476 __r->_M_ref_count = 2;
481 _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len);
490 template <
class _CharT,
class _Alloc>
491 typename rope<_CharT, _Alloc>::_RopeRep*
492 rope<_CharT, _Alloc>::
493 _S_tree_concat(_RopeRep* __left, _RopeRep* __right)
495 _RopeConcatenation* __result = _S_new_RopeConcatenation(__left, __right,
498 size_t __depth = __result->_M_depth;
501 && (__result->_M_size < 1000
502 || __depth >
size_t(__detail::_S_max_rope_depth)))
504 _RopeRep* __balanced;
508 __balanced = _S_balance(__result);
509 __result->_M_unref_nonnil();
513 rope::_C_deallocate(__result,1);
514 __throw_exception_again;
526 template <
class _CharT,
class _Alloc>
527 typename rope<_CharT, _Alloc>::_RopeRep*
528 rope<_CharT, _Alloc>::
529 _S_concat_char_iter(_RopeRep* __r,
const _CharT*__s,
size_t __slen)
538 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
539 __r->_M_get_allocator());
540 if (__r->_M_tag == __detail::_S_leaf
541 && __r->_M_size + __slen <=
size_t(_S_copy_max))
543 __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
546 if (__detail::_S_concat == __r->_M_tag
547 && __detail::_S_leaf == ((_RopeConcatenation*) __r)->_M_right->_M_tag)
550 (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right);
551 if (__right->_M_size + __slen <=
size_t(_S_copy_max))
553 _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left;
555 _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen);
556 __left->_M_ref_nonnil();
558 { __result = _S_tree_concat(__left, __nright); }
563 __throw_exception_again;
569 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->_M_get_allocator());
572 __r->_M_ref_nonnil();
573 __result = _S_tree_concat(__r, __nright);
579 __throw_exception_again;
585 template <
class _CharT,
class _Alloc>
586 typename rope<_CharT,_Alloc>::_RopeRep*
587 rope<_CharT,_Alloc>::
588 _S_destr_concat_char_iter(_RopeRep* __r,
const _CharT* __s,
size_t __slen)
592 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
593 __r->_M_get_allocator());
594 size_t __count = __r->_M_ref_count;
595 size_t __orig_size = __r->_M_size;
597 return _S_concat_char_iter(__r, __s, __slen);
600 __r->_M_ref_count = 2;
603 if (__orig_size + __slen <=
size_t(_S_copy_max)
604 && __detail::_S_leaf == __r->_M_tag)
606 __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s,
610 if (__detail::_S_concat == __r->_M_tag)
612 _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*)
614 if (__detail::_S_leaf == __right->_M_tag
615 && __right->_M_size + __slen <=
size_t(_S_copy_max))
617 _RopeRep* __new_right =
618 _S_destr_leaf_concat_char_iter(__right, __s, __slen);
619 if (__right == __new_right)
620 __new_right->_M_ref_count = 1;
622 __right->_M_unref_nonnil();
623 __r->_M_ref_count = 2;
624 ((_RopeConcatenation*)__r)->_M_right = __new_right;
625 __r->_M_size = __orig_size + __slen;
626 if (0 != __r->_M_c_string)
628 __r->_M_free_c_string();
629 __r->_M_c_string = 0;
635 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->_M_get_allocator());
636 __r->_M_ref_nonnil();
638 { __result = _S_tree_concat(__r, __right); }
643 __throw_exception_again;
649 template <
class _CharT,
class _Alloc>
650 typename rope<_CharT, _Alloc>::_RopeRep*
651 rope<_CharT, _Alloc>::
652 _S_concat(_RopeRep* __left, _RopeRep* __right)
661 __left->_M_ref_nonnil();
664 if (__detail::_S_leaf == __right->_M_tag)
666 if (__detail::_S_leaf == __left->_M_tag)
668 if (__right->_M_size + __left->_M_size <=
size_t(_S_copy_max))
669 return _S_leaf_concat_char_iter((_RopeLeaf*)__left,
670 ((_RopeLeaf*)__right)->_M_data,
673 else if (__detail::_S_concat == __left->_M_tag
674 && __detail::_S_leaf == ((_RopeConcatenation*)
675 __left)->_M_right->_M_tag)
677 _RopeLeaf* __leftright =
678 (_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right);
679 if (__leftright->_M_size
680 + __right->_M_size <=
size_t(_S_copy_max))
682 _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left;
683 _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright,
688 __leftleft->_M_ref_nonnil();
690 {
return(_S_tree_concat(__leftleft, __rest)); }
693 _S_unref(__leftleft);
695 __throw_exception_again;
700 __left->_M_ref_nonnil();
701 __right->_M_ref_nonnil();
703 {
return(_S_tree_concat(__left, __right)); }
708 __throw_exception_again;
712 template <
class _CharT,
class _Alloc>
713 typename rope<_CharT, _Alloc>::_RopeRep*
714 rope<_CharT, _Alloc>::
715 _S_substring(_RopeRep*
__base,
size_t __start,
size_t __endp1)
719 size_t __len =
__base->_M_size;
721 const size_t __lazy_threshold = 128;
723 if (__endp1 >= __len)
735 __adj_endp1 = __endp1;
739 case __detail::_S_concat:
741 _RopeConcatenation* __c = (_RopeConcatenation*)
__base;
742 _RopeRep* __left = __c->_M_left;
743 _RopeRep* __right = __c->_M_right;
744 size_t __left_len = __left->_M_size;
747 if (__adj_endp1 <= __left_len)
748 return _S_substring(__left, __start, __endp1);
749 else if (__start >= __left_len)
750 return _S_substring(__right, __start - __left_len,
751 __adj_endp1 - __left_len);
752 _Self_destruct_ptr __left_result(_S_substring(__left,
755 _Self_destruct_ptr __right_result(_S_substring(__right, 0,
758 __result = _S_concat(__left_result, __right_result);
761 case __detail::_S_leaf:
763 _RopeLeaf* __l = (_RopeLeaf*)
__base;
766 if (__start >= __adj_endp1)
768 __result_len = __adj_endp1 - __start;
769 if (__result_len > __lazy_threshold)
772 const _CharT* __section = __l->_M_data + __start;
773 __result = _S_new_RopeLeaf(__section, __result_len,
774 __base->_M_get_allocator());
775 __result->_M_c_string = 0;
778 __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__l->_M_data + __start,
785 case __detail::_S_substringfn:
788 _RopeSubstring* __old = (_RopeSubstring*)
__base;
790 if (__start >= __adj_endp1)
792 __result_len = __adj_endp1 - __start;
793 if (__result_len > __lazy_threshold)
795 _RopeSubstring* __result =
796 _S_new_RopeSubstring(__old->_M_base,
797 __start + __old->_M_start,
798 __adj_endp1 - __start,
799 __base->_M_get_allocator());
804 case __detail::_S_function:
806 _RopeFunction* __f = (_RopeFunction*)
__base;
809 if (__start >= __adj_endp1)
811 __result_len = __adj_endp1 - __start;
813 if (__result_len > __lazy_threshold)
815 __section = (_CharT*)
816 rope::_Data_allocate(_S_rounded_up_size(__result_len));
818 { (*(__f->_M_fn))(__start, __result_len, __section); }
821 _RopeRep::__STL_FREE_STRING(__section, __result_len,
822 __base->_M_get_allocator());
823 __throw_exception_again;
825 _S_cond_store_eos(__section[__result_len]);
826 return _S_new_RopeLeaf(__section, __result_len,
827 __base->_M_get_allocator());
833 return _S_new_RopeSubstring(
__base, __start, __adj_endp1 - __start,
834 __base->_M_get_allocator());
838 template<
class _CharT>
839 class _Rope_flatten_char_consumer
840 :
public _Rope_char_consumer<_CharT>
846 _Rope_flatten_char_consumer(_CharT* __buffer)
847 { _M_buf_ptr = __buffer; }
849 ~_Rope_flatten_char_consumer() {}
852 operator()(
const _CharT* __leaf,
size_t __n)
860 template<
class _CharT>
861 class _Rope_find_char_char_consumer
862 :
public _Rope_char_consumer<_CharT>
869 _Rope_find_char_char_consumer(_CharT __p)
870 : _M_pattern(__p), _M_count(0) {}
872 ~_Rope_find_char_char_consumer() {}
875 operator()(
const _CharT* __leaf,
size_t __n)
878 for (__i = 0; __i < __n; __i++)
880 if (__leaf[__i] == _M_pattern)
886 _M_count += __n;
return true;
890 template<
class _CharT,
class _Traits>
892 class _Rope_insert_char_consumer
893 :
public _Rope_char_consumer<_CharT>
896 typedef basic_ostream<_CharT,_Traits> _Insert_ostream;
897 _Insert_ostream& _M_o;
899 _Rope_insert_char_consumer(_Insert_ostream& __writer)
901 ~_Rope_insert_char_consumer() { }
903 bool operator() (
const _CharT* __leaf,
size_t __n);
907 template<
class _CharT,
class _Traits>
909 _Rope_insert_char_consumer<_CharT, _Traits>::
910 operator()(
const _CharT* __leaf,
size_t __n)
914 for (__i = 0; __i < __n; __i++)
915 _M_o.put(__leaf[__i]);
919 template <
class _CharT,
class _Alloc>
921 rope<_CharT, _Alloc>::
922 _S_apply_to_pieces(_Rope_char_consumer<_CharT>& __c,
923 const _RopeRep* __r,
size_t __begin,
size_t __end)
929 case __detail::_S_concat:
931 _RopeConcatenation* __conc = (_RopeConcatenation*)__r;
932 _RopeRep* __left = __conc->_M_left;
933 size_t __left_len = __left->_M_size;
934 if (__begin < __left_len)
936 size_t __left_end =
std::min(__left_len, __end);
937 if (!_S_apply_to_pieces(__c, __left, __begin, __left_end))
940 if (__end > __left_len)
942 _RopeRep* __right = __conc->_M_right;
943 size_t __right_start =
std::max(__left_len, __begin);
944 if (!_S_apply_to_pieces(__c, __right,
945 __right_start - __left_len,
951 case __detail::_S_leaf:
953 _RopeLeaf* __l = (_RopeLeaf*)__r;
954 return __c(__l->_M_data + __begin, __end - __begin);
956 case __detail::_S_function:
957 case __detail::_S_substringfn:
959 _RopeFunction* __f = (_RopeFunction*)__r;
960 size_t __len = __end - __begin;
963 (_CharT*)_Alloc().allocate(__len *
sizeof(_CharT));
966 (*(__f->_M_fn))(__begin, __len, __buffer);
967 __result = __c(__buffer, __len);
968 _Alloc().deallocate(__buffer, __len *
sizeof(_CharT));
972 _Alloc().deallocate(__buffer, __len *
sizeof(_CharT));
973 __throw_exception_again;
982 template<
class _CharT,
class _Traits>
984 _Rope_fill(basic_ostream<_CharT, _Traits>& __o,
size_t __n)
986 char __f = __o.fill();
989 for (__i = 0; __i < __n; __i++)
994 template <
class _CharT>
996 _Rope_is_simple(_CharT*)
1000 _Rope_is_simple(
char*)
1004 _Rope_is_simple(
wchar_t*)
1007 template<
class _CharT,
class _Traits,
class _Alloc>
1008 basic_ostream<_CharT, _Traits>&
1009 operator<<(basic_ostream<_CharT, _Traits>& __o,
1010 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,
size_t __start,
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,
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)
1113 for (
int __i = 0; __i < __indent; __i++)
1120 if (__detail::_S_concat == __r->_M_tag)
1122 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1123 _RopeRep* __left = __c->_M_left;
1124 _RopeRep* __right = __c->_M_right;
1127 printf(
"Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
1128 __r, __r->_M_depth, __r->_M_size,
1129 __r->_M_is_balanced?
"" :
"not");
1131 printf(
"Concatenation %p (rc = %ld, depth = %d, "
1132 "len = %ld, %s balanced)\n",
1133 __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size,
1134 __r->_M_is_balanced?
"" :
"not");
1136 _S_dump(__left, __indent + 2);
1137 _S_dump(__right, __indent + 2);
1144 switch (__r->_M_tag)
1146 case __detail::_S_leaf:
1149 case __detail::_S_function:
1150 __kind =
"Function";
1152 case __detail::_S_substringfn:
1153 __kind =
"Function representing substring";
1156 __kind =
"(corrupted kind field!)";
1159 printf(
"%s %p (depth = %d, len = %ld) ",
1160 __kind, __r, __r->_M_depth, __r->_M_size);
1162 printf(
"%s %p (rc = %ld, depth = %d, len = %ld) ",
1163 __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size);
1165 if (_S_is_one_byte_char_type((_CharT*)0))
1167 const int __max_len = 40;
1168 _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len));
1169 _CharT __buffer[__max_len + 1];
1170 bool __too_big = __r->_M_size > __prefix->_M_size;
1172 _S_flatten(__prefix, __buffer);
1173 __buffer[__prefix->_M_size] = _S_eos((_CharT*)0);
1174 printf(
"%s%s\n", (
char*)__buffer,
1175 __too_big?
"...\n" :
"\n");
1182 template <
class _CharT,
class _Alloc>
1184 rope<_CharT, _Alloc>::
1185 _S_min_len[int(__detail::_S_max_rope_depth) + 1] = {
1186 1, 2, 3, 5, 8, 13, 21,
1187 34, 55, 89, 144, 233, 377,
1188 610, 987, 1597, 2584, 4181,
1189 6765, 10946, 17711, 28657, 46368,
1190 75025, 121393, 196418, 317811,
1191 514229, 832040, 1346269, 2178309,
1192 3524578, 5702887, 9227465, 14930352,
1193 24157817, 39088169, 63245986, 102334155,
1194 165580141, 267914296, 433494437,
1195 701408733, 1134903170, 1836311903,
1199 template <
class _CharT,
class _Alloc>
1200 typename rope<_CharT, _Alloc>::_RopeRep*
1201 rope<_CharT, _Alloc>::
1202 _S_balance(_RopeRep* __r)
1204 _RopeRep* __forest[int(__detail::_S_max_rope_depth) + 1];
1205 _RopeRep* __result = 0;
1213 for (__i = 0; __i <= int(__detail::_S_max_rope_depth); ++__i)
1217 _S_add_to_forest(__r, __forest);
1218 for (__i = 0; __i <= int(__detail::_S_max_rope_depth); ++__i)
1219 if (0 != __forest[__i])
1222 _Self_destruct_ptr __old(__result);
1224 __result = _S_concat(__forest[__i], __result);
1225 __forest[__i]->_M_unref_nonnil();
1226#if !defined(__GC) && __cpp_exceptions
1233 for(__i = 0; __i <= int(__detail::_S_max_rope_depth); __i++)
1234 _S_unref(__forest[__i]);
1235 __throw_exception_again;
1238 if (__result->_M_depth >
int(__detail::_S_max_rope_depth))
1239 __throw_length_error(__N(
"rope::_S_balance"));
1243 template <
class _CharT,
class _Alloc>
1245 rope<_CharT, _Alloc>::
1246 _S_add_to_forest(_RopeRep* __r, _RopeRep** __forest)
1248 if (__r->_M_is_balanced)
1250 _S_add_leaf_to_forest(__r, __forest);
1255 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1257 _S_add_to_forest(__c->_M_left, __forest);
1258 _S_add_to_forest(__c->_M_right, __forest);
1263 template <
class _CharT,
class _Alloc>
1265 rope<_CharT, _Alloc>::
1266 _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest)
1268 _RopeRep* __insertee;
1269 _RopeRep* __too_tiny = 0;
1271 size_t __s = __r->_M_size;
1273 for (__i = 0; __s >= _S_min_len[__i+1]; ++__i)
1275 if (0 != __forest[__i])
1278 _Self_destruct_ptr __old(__too_tiny);
1280 __too_tiny = _S_concat_and_set_balanced(__forest[__i],
1282 __forest[__i]->_M_unref_nonnil();
1288 _Self_destruct_ptr __old(__too_tiny);
1290 __insertee = _S_concat_and_set_balanced(__too_tiny, __r);
1296 if (0 != __forest[__i])
1299 _Self_destruct_ptr __old(__insertee);
1301 __insertee = _S_concat_and_set_balanced(__forest[__i],
1303 __forest[__i]->_M_unref_nonnil();
1306 if (__i ==
int(__detail::_S_max_rope_depth)
1307 || __insertee->_M_size < _S_min_len[__i+1])
1309 __forest[__i] = __insertee;
1316 template <
class _CharT,
class _Alloc>
1318 rope<_CharT, _Alloc>::
1319 _S_fetch(_RopeRep* __r, size_type __i)
1321 __GC_CONST _CharT* __cstr = __r->_M_c_string;
1329 case __detail::_S_concat:
1331 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1332 _RopeRep* __left = __c->_M_left;
1333 size_t __left_len = __left->_M_size;
1335 if (__i >= __left_len)
1338 __r = __c->_M_right;
1344 case __detail::_S_leaf:
1346 _RopeLeaf* __l = (_RopeLeaf*)__r;
1347 return __l->_M_data[__i];
1349 case __detail::_S_function:
1350 case __detail::_S_substringfn:
1352 _RopeFunction* __f = (_RopeFunction*)__r;
1355 (*(__f->_M_fn))(__i, 1, &__result);
1365 template <
class _CharT,
class _Alloc>
1367 rope<_CharT, _Alloc>::
1368 _S_fetch_ptr(_RopeRep* __r, size_type __i)
1370 _RopeRep* __clrstack[__detail::_S_max_rope_depth];
1375 if (__r->_M_ref_count > 1)
1379 case __detail::_S_concat:
1381 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1382 _RopeRep* __left = __c->_M_left;
1383 size_t __left_len = __left->_M_size;
1385 if (__c->_M_c_string != 0)
1386 __clrstack[__csptr++] = __c;
1387 if (__i >= __left_len)
1390 __r = __c->_M_right;
1396 case __detail::_S_leaf:
1398 _RopeLeaf* __l = (_RopeLeaf*)__r;
1399 if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0)
1400 __clrstack[__csptr++] = __l;
1404 _RopeRep* __d = __clrstack[__csptr];
1405 __d->_M_free_c_string();
1406 __d->_M_c_string = 0;
1408 return __l->_M_data + __i;
1410 case __detail::_S_function:
1411 case __detail::_S_substringfn:
1422 template <
class _CharT,
class _Alloc>
1424 rope<_CharT, _Alloc>::
1425 _S_compare (
const _RopeRep* __left,
const _RopeRep* __right)
1434 __left_len = __left->_M_size;
1435 __right_len = __right->_M_size;
1436 if (__detail::_S_leaf == __left->_M_tag)
1438 _RopeLeaf* __l = (_RopeLeaf*) __left;
1439 if (__detail::_S_leaf == __right->_M_tag)
1441 _RopeLeaf* __r = (_RopeLeaf*) __right;
1443 __l->_M_data + __left_len,
1444 __r->_M_data, __r->_M_data
1449 const_iterator __rstart(__right, 0);
1450 const_iterator __rend(__right, __right_len);
1458 const_iterator __lstart(__left, 0);
1459 const_iterator __lend(__left, __left_len);
1460 if (__detail::_S_leaf == __right->_M_tag)
1462 _RopeLeaf* __r = (_RopeLeaf*) __right;
1464 __r->_M_data, __r->_M_data
1469 const_iterator __rstart(__right, 0);
1470 const_iterator __rend(__right, __right_len);
1478 template <
class _CharT,
class _Alloc>
1479 _Rope_char_ref_proxy<_CharT, _Alloc>&
1480 _Rope_char_ref_proxy<_CharT, _Alloc>::
1481 operator=(_CharT __c)
1483 _RopeRep* __old = _M_root->_M_tree_ptr;
1487 _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos);
1494 _Self_destruct_ptr __left(_My_rope::_S_substring(__old, 0, _M_pos));
1495 _Self_destruct_ptr __right(_My_rope::_S_substring(__old, _M_pos + 1,
1497 _Self_destruct_ptr __result_left(_My_rope::
1498 _S_destr_concat_char_iter(__left,
1501 _RopeRep* __result = _My_rope::_S_concat(__result_left, __right);
1503 _RopeRep::_S_unref(__old);
1505 _M_root->_M_tree_ptr = __result;
1509 template <
class _CharT,
class _Alloc>
1510 inline _Rope_char_ref_proxy<_CharT, _Alloc>::
1511 operator _CharT()
const
1513 if (_M_current_valid)
1516 return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos);
1519 template <
class _CharT,
class _Alloc>
1520 _Rope_char_ptr_proxy<_CharT, _Alloc>
1523 {
return _Rope_char_ptr_proxy<_CharT, _Alloc>(*
this); }
1525 template <
class _CharT,
class _Alloc>
1526 rope<_CharT, _Alloc>::
1527 rope(
size_t __n, _CharT __c,
const allocator_type& __a)
1530 rope<_CharT,_Alloc> __result;
1531 const size_t __exponentiate_threshold = 32;
1534 _CharT* __rest_buffer;
1535 _RopeRep* __remainder;
1536 rope<_CharT, _Alloc> __remainder_rope;
1541 __exponent = __n / __exponentiate_threshold;
1542 __rest = __n % __exponentiate_threshold;
1547 __rest_buffer = this->_Data_allocate(_S_rounded_up_size(__rest));
1548 __uninitialized_fill_n_a(__rest_buffer, __rest, __c,
1549 _M_get_allocator());
1550 _S_cond_store_eos(__rest_buffer[__rest]);
1552 { __remainder = _S_new_RopeLeaf(__rest_buffer, __rest,
1553 _M_get_allocator()); }
1556 _RopeRep::__STL_FREE_STRING(__rest_buffer, __rest,
1557 _M_get_allocator());
1558 __throw_exception_again;
1561 __remainder_rope._M_tree_ptr = __remainder;
1562 if (__exponent != 0)
1564 _CharT* __base_buffer =
1565 this->_Data_allocate(_S_rounded_up_size(__exponentiate_threshold));
1566 _RopeLeaf* __base_leaf;
1568 __uninitialized_fill_n_a(__base_buffer, __exponentiate_threshold, __c,
1569 _M_get_allocator());
1570 _S_cond_store_eos(__base_buffer[__exponentiate_threshold]);
1573 __base_leaf = _S_new_RopeLeaf(__base_buffer,
1574 __exponentiate_threshold,
1575 _M_get_allocator());
1579 _RopeRep::__STL_FREE_STRING(__base_buffer,
1580 __exponentiate_threshold,
1581 _M_get_allocator());
1582 __throw_exception_again;
1584 __base_rope._M_tree_ptr = __base_leaf;
1585 if (1 == __exponent)
1586 __result = __base_rope;
1588 __result =
power(__base_rope, __exponent,
1589 _Rope_Concat_fn<_CharT, _Alloc>());
1591 if (0 != __remainder)
1592 __result += __remainder_rope;
1595 __result = __remainder_rope;
1597 this->_M_tree_ptr = __result._M_tree_ptr;
1598 this->_M_tree_ptr->_M_ref_nonnil();
1601 template<
class _CharT,
class _Alloc>
1603 rope<_CharT, _Alloc>::_S_empty_c_str[1];
1605 template<
class _CharT,
class _Alloc>
1607 rope<_CharT, _Alloc>::
1610 if (0 == this->_M_tree_ptr)
1612 _S_empty_c_str[0] = _S_eos((_CharT*)0);
1614 return _S_empty_c_str;
1616 __gthread_mutex_lock (&this->_M_tree_ptr->_M_c_string_lock);
1617 __GC_CONST _CharT* __result = this->_M_tree_ptr->_M_c_string;
1620 size_t __s = size();
1621 __result = this->_Data_allocate(__s + 1);
1622 _S_flatten(this->_M_tree_ptr, __result);
1623 __result[__s] = _S_eos((_CharT*)0);
1624 this->_M_tree_ptr->_M_c_string = __result;
1626 __gthread_mutex_unlock (&this->_M_tree_ptr->_M_c_string_lock);
1630 template<
class _CharT,
class _Alloc>
1631 const _CharT* rope<_CharT, _Alloc>::
1632 replace_with_c_str()
1634 if (0 == this->_M_tree_ptr)
1636 _S_empty_c_str[0] = _S_eos((_CharT*)0);
1637 return _S_empty_c_str;
1639 __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string;
1640 if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag
1641 && 0 != __old_c_string)
1642 return(__old_c_string);
1643 size_t __s = size();
1644 _CharT* __result = this->_Data_allocate(_S_rounded_up_size(__s));
1645 _S_flatten(this->_M_tree_ptr, __result);
1646 __result[__s] = _S_eos((_CharT*)0);
1647 this->_M_tree_ptr->_M_unref_nonnil();
1648 this->_M_tree_ptr = _S_new_RopeLeaf(__result, __s,
1649 this->_M_get_allocator());
1655 template<
class _Rope_iterator>
1657 _Rope_rotate(_Rope_iterator __first,
1658 _Rope_iterator __middle,
1659 _Rope_iterator __last)
1661 typedef typename _Rope_iterator::value_type _CharT;
1662 typedef typename _Rope_iterator::_allocator_type _Alloc;
1664 rope<_CharT, _Alloc>& __r(__first.container());
1665 rope<_CharT, _Alloc> __prefix = __r.substr(0, __first.index());
1666 rope<_CharT, _Alloc> __suffix =
1667 __r.substr(__last.index(), __r.size() - __last.index());
1668 rope<_CharT, _Alloc> __part1 =
1669 __r.substr(__middle.index(), __last.index() - __middle.index());
1670 rope<_CharT, _Alloc> __part2 =
1671 __r.substr(__first.index(), __middle.index() - __first.index());
1678#if !defined(__GNUC__)
1681 rotate(_Rope_iterator<
char, __STL_DEFAULT_ALLOCATOR(
char)> __first,
1682 _Rope_iterator<
char, __STL_DEFAULT_ALLOCATOR(
char)> __middle,
1683 _Rope_iterator<
char, __STL_DEFAULT_ALLOCATOR(
char)> __last)
1684 { _Rope_rotate(__first, __middle, __last); }
1696 rotate(_Rope_iterator<
wchar_t, __STL_DEFAULT_ALLOCATOR(
char)> __first,
1697 _Rope_iterator<
wchar_t, __STL_DEFAULT_ALLOCATOR(
char)> __middle,
1698 _Rope_iterator<
wchar_t, __STL_DEFAULT_ALLOCATOR(
char)> __last)
1699 { _Rope_rotate(__first, __middle, __last); }
1702_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.
_GLIBCXX14_CONSTEXPR const _Tp & max(const _Tp &, const _Tp &)
This does what you think it does.
_GLIBCXX14_CONSTEXPR const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
_ForwardIterator uninitialized_copy_n(_InputIterator __first, _Size __n, _ForwardIterator __result)
Copies the range [first,first+n) into result.
bitset< _Nb > operator&(const bitset< _Nb > &__x, const bitset< _Nb > &__y) noexcept
Global bitwise operations on bitsets.
void _Destroy(_Tp *__pointer)
std::basic_ostream< _CharT, _Traits > & operator<<(std::basic_ostream< _CharT, _Traits > &__os, const bitset< _Nb > &__x)
Global I/O operators for bitsets.
GNU extensions for public use.
_Iterator __base(_Iterator __it)
Template class basic_ostream.
static const fmtflags left
Adds fill characters on the right (final positions) of certain generated output. (I....