1 // SGI's rope class implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010
4 // Free Software Foundation, Inc.
6 // This file is part of the GNU ISO C++ Library. This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 // GNU General Public License for more details.
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
24 // <http://www.gnu.org/licenses/>.
28 * Silicon Graphics Computer Systems, Inc.
30 * Permission to use, copy, modify, distribute and sell this software
31 * and its documentation for any purpose is hereby granted without fee,
32 * provided that the above copyright notice appear in all copies and
33 * that both that copyright notice and this permission notice appear
34 * in supporting documentation. Silicon Graphics makes no
35 * representations about the suitability of this software for any
36 * purpose. It is provided "as is" without express or implied warranty.
40 * This is an internal header file, included by other library headers.
41 * Do not attempt to use it directly. @headername{ext/rope}
46 #include <bits/functexcept.h>
48 #include <ext/algorithm> // For copy_n and lexicographical_compare_3way
49 #include <ext/memory> // For uninitialized_copy_n
50 #include <ext/numeric> // For power
52 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx
)
56 using std::basic_ostream
;
57 using std::__throw_length_error
;
59 using std::uninitialized_fill_n
;
61 // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
62 // if necessary. Assumes _M_path_end[leaf_index] and leaf_pos are correct.
63 // Results in a valid buf_ptr if the iterator can be legitimately
65 template <class _CharT
, class _Alloc
>
67 _Rope_iterator_base
<_CharT
, _Alloc
>::
68 _S_setbuf(_Rope_iterator_base
<_CharT
, _Alloc
>& __x
)
70 const _RopeRep
* __leaf
= __x
._M_path_end
[__x
._M_leaf_index
];
71 size_t __leaf_pos
= __x
._M_leaf_pos
;
72 size_t __pos
= __x
._M_current_pos
;
74 switch(__leaf
->_M_tag
)
76 case __detail::_S_leaf
:
77 __x
._M_buf_start
= ((_Rope_RopeLeaf
<_CharT
, _Alloc
>*)__leaf
)->_M_data
;
78 __x
._M_buf_ptr
= __x
._M_buf_start
+ (__pos
- __leaf_pos
);
79 __x
._M_buf_end
= __x
._M_buf_start
+ __leaf
->_M_size
;
81 case __detail::_S_function
:
82 case __detail::_S_substringfn
:
84 size_t __len
= _S_iterator_buf_len
;
85 size_t __buf_start_pos
= __leaf_pos
;
86 size_t __leaf_end
= __leaf_pos
+ __leaf
->_M_size
;
87 char_producer
<_CharT
>* __fn
= ((_Rope_RopeFunction
<_CharT
,
88 _Alloc
>*)__leaf
)->_M_fn
;
89 if (__buf_start_pos
+ __len
<= __pos
)
91 __buf_start_pos
= __pos
- __len
/ 4;
92 if (__buf_start_pos
+ __len
> __leaf_end
)
93 __buf_start_pos
= __leaf_end
- __len
;
95 if (__buf_start_pos
+ __len
> __leaf_end
)
96 __len
= __leaf_end
- __buf_start_pos
;
97 (*__fn
)(__buf_start_pos
- __leaf_pos
, __len
, __x
._M_tmp_buf
);
98 __x
._M_buf_ptr
= __x
._M_tmp_buf
+ (__pos
- __buf_start_pos
);
99 __x
._M_buf_start
= __x
._M_tmp_buf
;
100 __x
._M_buf_end
= __x
._M_tmp_buf
+ __len
;
108 // Set path and buffer inside a rope iterator. We assume that
109 // pos and root are already set.
110 template <class _CharT
, class _Alloc
>
112 _Rope_iterator_base
<_CharT
, _Alloc
>::
113 _S_setcache(_Rope_iterator_base
<_CharT
, _Alloc
>& __x
)
115 const _RopeRep
* __path
[int(__detail::_S_max_rope_depth
) + 1];
116 const _RopeRep
* __curr_rope
;
117 int __curr_depth
= -1; /* index into path */
118 size_t __curr_start_pos
= 0;
119 size_t __pos
= __x
._M_current_pos
;
120 unsigned char __dirns
= 0; // Bit vector marking right turns in the path
122 if (__pos
>= __x
._M_root
->_M_size
)
127 __curr_rope
= __x
._M_root
;
128 if (0 != __curr_rope
->_M_c_string
)
130 /* Treat the root as a leaf. */
131 __x
._M_buf_start
= __curr_rope
->_M_c_string
;
132 __x
._M_buf_end
= __curr_rope
->_M_c_string
+ __curr_rope
->_M_size
;
133 __x
._M_buf_ptr
= __curr_rope
->_M_c_string
+ __pos
;
134 __x
._M_path_end
[0] = __curr_rope
;
135 __x
._M_leaf_index
= 0;
142 __path
[__curr_depth
] = __curr_rope
;
143 switch(__curr_rope
->_M_tag
)
145 case __detail::_S_leaf
:
146 case __detail::_S_function
:
147 case __detail::_S_substringfn
:
148 __x
._M_leaf_pos
= __curr_start_pos
;
150 case __detail::_S_concat
:
152 _Rope_RopeConcatenation
<_CharT
, _Alloc
>* __c
=
153 (_Rope_RopeConcatenation
<_CharT
, _Alloc
>*)__curr_rope
;
154 _RopeRep
* __left
= __c
->_M_left
;
155 size_t __left_len
= __left
->_M_size
;
158 if (__pos
>= __curr_start_pos
+ __left_len
)
161 __curr_rope
= __c
->_M_right
;
162 __curr_start_pos
+= __left_len
;
165 __curr_rope
= __left
;
171 // Copy last section of path into _M_path_end.
174 int __j
= __curr_depth
+ 1 - int(_S_path_cache_len
);
176 if (__j
< 0) __j
= 0;
177 while (__j
<= __curr_depth
)
178 __x
._M_path_end
[++__i
] = __path
[__j
++];
179 __x
._M_leaf_index
= __i
;
181 __x
._M_path_directions
= __dirns
;
185 // Specialized version of the above. Assumes that
186 // the path cache is valid for the previous position.
187 template <class _CharT
, class _Alloc
>
189 _Rope_iterator_base
<_CharT
, _Alloc
>::
190 _S_setcache_for_incr(_Rope_iterator_base
<_CharT
, _Alloc
>& __x
)
192 int __current_index
= __x
._M_leaf_index
;
193 const _RopeRep
* __current_node
= __x
._M_path_end
[__current_index
];
194 size_t __len
= __current_node
->_M_size
;
195 size_t __node_start_pos
= __x
._M_leaf_pos
;
196 unsigned char __dirns
= __x
._M_path_directions
;
197 _Rope_RopeConcatenation
<_CharT
, _Alloc
>* __c
;
199 if (__x
._M_current_pos
- __node_start_pos
< __len
)
201 /* More stuff in this leaf, we just didn't cache it. */
205 // node_start_pos is starting position of last_node.
206 while (--__current_index
>= 0)
208 if (!(__dirns
& 1) /* Path turned left */)
210 __current_node
= __x
._M_path_end
[__current_index
];
211 __c
= (_Rope_RopeConcatenation
<_CharT
, _Alloc
>*)__current_node
;
212 // Otherwise we were in the right child. Thus we should pop
213 // the concatenation node.
214 __node_start_pos
-= __c
->_M_left
->_M_size
;
217 if (__current_index
< 0)
219 // We underflowed the cache. Punt.
223 __current_node
= __x
._M_path_end
[__current_index
];
224 __c
= (_Rope_RopeConcatenation
<_CharT
, _Alloc
>*)__current_node
;
225 // current_node is a concatenation node. We are positioned on the first
226 // character in its right child.
227 // node_start_pos is starting position of current_node.
228 __node_start_pos
+= __c
->_M_left
->_M_size
;
229 __current_node
= __c
->_M_right
;
230 __x
._M_path_end
[++__current_index
] = __current_node
;
232 while (__detail::_S_concat
== __current_node
->_M_tag
)
235 if (int(_S_path_cache_len
) == __current_index
)
238 for (__i
= 0; __i
< int(_S_path_cache_len
) - 1; __i
++)
239 __x
._M_path_end
[__i
] = __x
._M_path_end
[__i
+1];
243 ((_Rope_RopeConcatenation
<_CharT
, _Alloc
>*)__current_node
)->_M_left
;
244 __x
._M_path_end
[__current_index
] = __current_node
;
246 // node_start_pos is unchanged.
248 __x
._M_leaf_index
= __current_index
;
249 __x
._M_leaf_pos
= __node_start_pos
;
250 __x
._M_path_directions
= __dirns
;
254 template <class _CharT
, class _Alloc
>
256 _Rope_iterator_base
<_CharT
, _Alloc
>::
259 _M_current_pos
+= __n
;
262 size_t __chars_left
= _M_buf_end
- _M_buf_ptr
;
263 if (__chars_left
> __n
)
265 else if (__chars_left
== __n
)
268 _S_setcache_for_incr(*this);
275 template <class _CharT
, class _Alloc
>
277 _Rope_iterator_base
<_CharT
, _Alloc
>::
282 size_t __chars_left
= _M_buf_ptr
- _M_buf_start
;
283 if (__chars_left
>= __n
)
288 _M_current_pos
-= __n
;
291 template <class _CharT
, class _Alloc
>
293 _Rope_iterator
<_CharT
, _Alloc
>::
296 if (_M_root_rope
->_M_tree_ptr
!= this->_M_root
)
298 // _Rope was modified. Get things fixed up.
299 _RopeRep::_S_unref(this->_M_root
);
300 this->_M_root
= _M_root_rope
->_M_tree_ptr
;
301 _RopeRep::_S_ref(this->_M_root
);
302 this->_M_buf_ptr
= 0;
306 template <class _CharT
, class _Alloc
>
308 _Rope_const_iterator
<_CharT
, _Alloc
>::
309 _Rope_const_iterator(const _Rope_iterator
<_CharT
, _Alloc
>& __x
)
310 : _Rope_iterator_base
<_CharT
, _Alloc
>(__x
)
313 template <class _CharT
, class _Alloc
>
315 _Rope_iterator
<_CharT
, _Alloc
>::
316 _Rope_iterator(rope
<_CharT
, _Alloc
>& __r
, size_t __pos
)
317 : _Rope_iterator_base
<_CharT
,_Alloc
>(__r
._M_tree_ptr
, __pos
),
319 { _RopeRep::_S_ref(this->_M_root
); }
321 template <class _CharT
, class _Alloc
>
323 rope
<_CharT
, _Alloc
>::
324 _S_char_ptr_len(const _CharT
* __s
)
326 const _CharT
* __p
= __s
;
328 while (!_S_is0(*__p
))
336 template <class _CharT
, class _Alloc
>
338 _Rope_RopeRep
<_CharT
, _Alloc
>::
341 _CharT
* __cstr
= _M_c_string
;
344 size_t __size
= this->_M_size
+ 1;
345 _Destroy(__cstr
, __cstr
+ __size
, _M_get_allocator());
346 this->_Data_deallocate(__cstr
, __size
);
350 template <class _CharT
, class _Alloc
>
352 _Rope_RopeRep
<_CharT
, _Alloc
>::
353 _S_free_string(_CharT
* __s
, size_t __n
, allocator_type
& __a
)
355 if (!_S_is_basic_char_type((_CharT
*)0))
356 _Destroy(__s
, __s
+ __n
, __a
);
358 // This has to be a static member, so this gets a bit messy
360 _Rope_RopeLeaf
<_CharT
, _Alloc
>::_S_rounded_up_size(__n
));
363 // There are several reasons for not doing this with virtual destructors
364 // and a class specific delete operator:
365 // - A class specific delete operator can't easily get access to
366 // allocator instances if we need them.
367 // - Any virtual function would need a 4 or byte vtable pointer;
368 // this only requires a one byte tag per object.
369 template <class _CharT
, class _Alloc
>
371 _Rope_RopeRep
<_CharT
, _Alloc
>::
376 case __detail::_S_leaf
:
378 _Rope_RopeLeaf
<_CharT
, _Alloc
>* __l
379 = (_Rope_RopeLeaf
<_CharT
, _Alloc
>*)this;
380 __l
->_Rope_RopeLeaf
<_CharT
, _Alloc
>::~_Rope_RopeLeaf();
381 _L_deallocate(__l
, 1);
384 case __detail::_S_concat
:
386 _Rope_RopeConcatenation
<_CharT
,_Alloc
>* __c
387 = (_Rope_RopeConcatenation
<_CharT
, _Alloc
>*)this;
388 __c
->_Rope_RopeConcatenation
<_CharT
, _Alloc
>::
389 ~_Rope_RopeConcatenation();
390 _C_deallocate(__c
, 1);
393 case __detail::_S_function
:
395 _Rope_RopeFunction
<_CharT
, _Alloc
>* __f
396 = (_Rope_RopeFunction
<_CharT
, _Alloc
>*)this;
397 __f
->_Rope_RopeFunction
<_CharT
, _Alloc
>::~_Rope_RopeFunction();
398 _F_deallocate(__f
, 1);
401 case __detail::_S_substringfn
:
403 _Rope_RopeSubstring
<_CharT
, _Alloc
>* __ss
=
404 (_Rope_RopeSubstring
<_CharT
, _Alloc
>*)this;
405 __ss
->_Rope_RopeSubstring
<_CharT
, _Alloc
>::
406 ~_Rope_RopeSubstring();
407 _S_deallocate(__ss
, 1);
414 template <class _CharT
, class _Alloc
>
416 _Rope_RopeRep
<_CharT
, _Alloc
>::
417 _S_free_string(const _CharT
*, size_t, allocator_type
)
422 // Concatenate a C string onto a leaf rope by copying the rope data.
423 // Used for short ropes.
424 template <class _CharT
, class _Alloc
>
425 typename rope
<_CharT
, _Alloc
>::_RopeLeaf
*
426 rope
<_CharT
, _Alloc
>::
427 _S_leaf_concat_char_iter(_RopeLeaf
* __r
, const _CharT
* __iter
, size_t __len
)
429 size_t __old_len
= __r
->_M_size
;
430 _CharT
* __new_data
= (_CharT
*)
431 _Data_allocate(_S_rounded_up_size(__old_len
+ __len
));
434 uninitialized_copy_n(__r
->_M_data
, __old_len
, __new_data
);
435 uninitialized_copy_n(__iter
, __len
, __new_data
+ __old_len
);
436 _S_cond_store_eos(__new_data
[__old_len
+ __len
]);
439 __result
= _S_new_RopeLeaf(__new_data
, __old_len
+ __len
,
440 __r
->_M_get_allocator());
444 _RopeRep::__STL_FREE_STRING(__new_data
, __old_len
+ __len
,
445 __r
->_M_get_allocator());
446 __throw_exception_again
;
452 // As above, but it's OK to clobber original if refcount is 1
453 template <class _CharT
, class _Alloc
>
454 typename rope
<_CharT
,_Alloc
>::_RopeLeaf
*
455 rope
<_CharT
, _Alloc
>::
456 _S_destr_leaf_concat_char_iter(_RopeLeaf
* __r
, const _CharT
* __iter
,
459 if (__r
->_M_ref_count
> 1)
460 return _S_leaf_concat_char_iter(__r
, __iter
, __len
);
461 size_t __old_len
= __r
->_M_size
;
462 if (_S_allocated_capacity(__old_len
) >= __old_len
+ __len
)
464 // The space has been partially initialized for the standard
465 // character types. But that doesn't matter for those types.
466 uninitialized_copy_n(__iter
, __len
, __r
->_M_data
+ __old_len
);
467 if (_S_is_basic_char_type((_CharT
*)0))
468 _S_cond_store_eos(__r
->_M_data
[__old_len
+ __len
]);
469 else if (__r
->_M_c_string
!= __r
->_M_data
&& 0 != __r
->_M_c_string
)
471 __r
->_M_free_c_string();
472 __r
->_M_c_string
= 0;
474 __r
->_M_size
= __old_len
+ __len
;
475 __r
->_M_ref_count
= 2;
480 _RopeLeaf
* __result
= _S_leaf_concat_char_iter(__r
, __iter
, __len
);
486 // Assumes left and right are not 0.
487 // Does not increment (nor decrement on exception) child reference counts.
488 // Result has ref count 1.
489 template <class _CharT
, class _Alloc
>
490 typename rope
<_CharT
, _Alloc
>::_RopeRep
*
491 rope
<_CharT
, _Alloc
>::
492 _S_tree_concat(_RopeRep
* __left
, _RopeRep
* __right
)
494 _RopeConcatenation
* __result
= _S_new_RopeConcatenation(__left
, __right
,
497 size_t __depth
= __result
->_M_depth
;
500 && (__result
->_M_size
< 1000
501 || __depth
> size_t(__detail::_S_max_rope_depth
)))
503 _RopeRep
* __balanced
;
507 __balanced
= _S_balance(__result
);
508 __result
->_M_unref_nonnil();
512 _C_deallocate(__result
,1);
513 __throw_exception_again
;
515 // In case of exception, we need to deallocate
516 // otherwise dangling result node. But caller
517 // still owns its children. Thus unref is
525 template <class _CharT
, class _Alloc
>
526 typename rope
<_CharT
, _Alloc
>::_RopeRep
*
527 rope
<_CharT
, _Alloc
>::
528 _S_concat_char_iter(_RopeRep
* __r
, const _CharT
*__s
, 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
, size_t __slen
)
591 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __slen
,
592 __r
->_M_get_allocator());
593 size_t __count
= __r
->_M_ref_count
;
594 size_t __orig_size
= __r
->_M_size
;
596 return _S_concat_char_iter(__r
, __s
, __slen
);
599 __r
->_M_ref_count
= 2; // One more than before
602 if (__orig_size
+ __slen
<= size_t(_S_copy_max
)
603 && __detail::_S_leaf
== __r
->_M_tag
)
605 __result
= _S_destr_leaf_concat_char_iter((_RopeLeaf
*)__r
, __s
,
609 if (__detail::_S_concat
== __r
->_M_tag
)
611 _RopeLeaf
* __right
= (_RopeLeaf
*)(((_RopeConcatenation
*)
613 if (__detail::_S_leaf
== __right
->_M_tag
614 && __right
->_M_size
+ __slen
<= size_t(_S_copy_max
))
616 _RopeRep
* __new_right
=
617 _S_destr_leaf_concat_char_iter(__right
, __s
, __slen
);
618 if (__right
== __new_right
)
619 __new_right
->_M_ref_count
= 1;
621 __right
->_M_unref_nonnil();
622 __r
->_M_ref_count
= 2; // One more than before.
623 ((_RopeConcatenation
*)__r
)->_M_right
= __new_right
;
624 __r
->_M_size
= __orig_size
+ __slen
;
625 if (0 != __r
->_M_c_string
)
627 __r
->_M_free_c_string();
628 __r
->_M_c_string
= 0;
634 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __slen
, __r
->_M_get_allocator());
635 __r
->_M_ref_nonnil();
637 { __result
= _S_tree_concat(__r
, __right
); }
642 __throw_exception_again
;
648 template <class _CharT
, class _Alloc
>
649 typename rope
<_CharT
, _Alloc
>::_RopeRep
*
650 rope
<_CharT
, _Alloc
>::
651 _S_concat(_RopeRep
* __left
, _RopeRep
* __right
)
660 __left
->_M_ref_nonnil();
663 if (__detail::_S_leaf
== __right
->_M_tag
)
665 if (__detail::_S_leaf
== __left
->_M_tag
)
667 if (__right
->_M_size
+ __left
->_M_size
<= size_t(_S_copy_max
))
668 return _S_leaf_concat_char_iter((_RopeLeaf
*)__left
,
669 ((_RopeLeaf
*)__right
)->_M_data
,
672 else if (__detail::_S_concat
== __left
->_M_tag
673 && __detail::_S_leaf
== ((_RopeConcatenation
*)
674 __left
)->_M_right
->_M_tag
)
676 _RopeLeaf
* __leftright
=
677 (_RopeLeaf
*)(((_RopeConcatenation
*)__left
)->_M_right
);
678 if (__leftright
->_M_size
679 + __right
->_M_size
<= size_t(_S_copy_max
))
681 _RopeRep
* __leftleft
= ((_RopeConcatenation
*)__left
)->_M_left
;
682 _RopeRep
* __rest
= _S_leaf_concat_char_iter(__leftright
,
687 __leftleft
->_M_ref_nonnil();
689 { return(_S_tree_concat(__leftleft
, __rest
)); }
692 _S_unref(__leftleft
);
694 __throw_exception_again
;
699 __left
->_M_ref_nonnil();
700 __right
->_M_ref_nonnil();
702 { return(_S_tree_concat(__left
, __right
)); }
707 __throw_exception_again
;
711 template <class _CharT
, class _Alloc
>
712 typename rope
<_CharT
, _Alloc
>::_RopeRep
*
713 rope
<_CharT
, _Alloc
>::
714 _S_substring(_RopeRep
* __base
, size_t __start
, size_t __endp1
)
718 size_t __len
= __base
->_M_size
;
720 const size_t __lazy_threshold
= 128;
722 if (__endp1
>= __len
)
726 __base
->_M_ref_nonnil();
734 __adj_endp1
= __endp1
;
736 switch(__base
->_M_tag
)
738 case __detail::_S_concat
:
740 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__base
;
741 _RopeRep
* __left
= __c
->_M_left
;
742 _RopeRep
* __right
= __c
->_M_right
;
743 size_t __left_len
= __left
->_M_size
;
746 if (__adj_endp1
<= __left_len
)
747 return _S_substring(__left
, __start
, __endp1
);
748 else if (__start
>= __left_len
)
749 return _S_substring(__right
, __start
- __left_len
,
750 __adj_endp1
- __left_len
);
751 _Self_destruct_ptr
__left_result(_S_substring(__left
,
754 _Self_destruct_ptr
__right_result(_S_substring(__right
, 0,
757 __result
= _S_concat(__left_result
, __right_result
);
760 case __detail::_S_leaf
:
762 _RopeLeaf
* __l
= (_RopeLeaf
*)__base
;
765 if (__start
>= __adj_endp1
)
767 __result_len
= __adj_endp1
- __start
;
768 if (__result_len
> __lazy_threshold
)
771 const _CharT
* __section
= __l
->_M_data
+ __start
;
772 __result
= _S_new_RopeLeaf(__section
, __result_len
,
773 __base
->_M_get_allocator());
774 __result
->_M_c_string
= 0; // Not eos terminated.
776 // We should sometimes create substring node instead.
777 __result
= __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__l
->_M_data
+ __start
,
784 case __detail::_S_substringfn
:
785 // Avoid introducing multiple layers of substring nodes.
787 _RopeSubstring
* __old
= (_RopeSubstring
*)__base
;
789 if (__start
>= __adj_endp1
)
791 __result_len
= __adj_endp1
- __start
;
792 if (__result_len
> __lazy_threshold
)
794 _RopeSubstring
* __result
=
795 _S_new_RopeSubstring(__old
->_M_base
,
796 __start
+ __old
->_M_start
,
797 __adj_endp1
- __start
,
798 __base
->_M_get_allocator());
801 } // *** else fall through: ***
803 case __detail::_S_function
:
805 _RopeFunction
* __f
= (_RopeFunction
*)__base
;
808 if (__start
>= __adj_endp1
)
810 __result_len
= __adj_endp1
- __start
;
812 if (__result_len
> __lazy_threshold
)
814 __section
= (_CharT
*)
815 _Data_allocate(_S_rounded_up_size(__result_len
));
817 { (*(__f
->_M_fn
))(__start
, __result_len
, __section
); }
820 _RopeRep::__STL_FREE_STRING(__section
, __result_len
,
821 __base
->_M_get_allocator());
822 __throw_exception_again
;
824 _S_cond_store_eos(__section
[__result_len
]);
825 return _S_new_RopeLeaf(__section
, __result_len
,
826 __base
->_M_get_allocator());
831 // Create substring node.
832 return _S_new_RopeSubstring(__base
, __start
, __adj_endp1
- __start
,
833 __base
->_M_get_allocator());
837 template<class _CharT
>
838 class _Rope_flatten_char_consumer
839 : public _Rope_char_consumer
<_CharT
>
845 _Rope_flatten_char_consumer(_CharT
* __buffer
)
846 { _M_buf_ptr
= __buffer
; };
848 ~_Rope_flatten_char_consumer() {}
851 operator()(const _CharT
* __leaf
, size_t __n
)
853 uninitialized_copy_n(__leaf
, __n
, _M_buf_ptr
);
859 template<class _CharT
>
860 class _Rope_find_char_char_consumer
861 : public _Rope_char_consumer
<_CharT
>
866 size_t _M_count
; // Number of nonmatching characters
868 _Rope_find_char_char_consumer(_CharT __p
)
869 : _M_pattern(__p
), _M_count(0) {}
871 ~_Rope_find_char_char_consumer() {}
874 operator()(const _CharT
* __leaf
, size_t __n
)
877 for (__i
= 0; __i
< __n
; __i
++)
879 if (__leaf
[__i
] == _M_pattern
)
885 _M_count
+= __n
; return true;
889 template<class _CharT
, class _Traits
>
890 // Here _CharT is both the stream and rope character type.
891 class _Rope_insert_char_consumer
892 : public _Rope_char_consumer
<_CharT
>
895 typedef basic_ostream
<_CharT
,_Traits
> _Insert_ostream
;
896 _Insert_ostream
& _M_o
;
898 _Rope_insert_char_consumer(_Insert_ostream
& __writer
)
900 ~_Rope_insert_char_consumer() { };
901 // Caller is presumed to own the ostream
902 bool operator() (const _CharT
* __leaf
, size_t __n
);
903 // Returns true to continue traversal.
906 template<class _CharT
, class _Traits
>
908 _Rope_insert_char_consumer
<_CharT
, _Traits
>::
909 operator()(const _CharT
* __leaf
, size_t __n
)
912 // We assume that formatting is set up correctly for each element.
913 for (__i
= 0; __i
< __n
; __i
++)
914 _M_o
.put(__leaf
[__i
]);
918 template <class _CharT
, class _Alloc
>
920 rope
<_CharT
, _Alloc
>::
921 _S_apply_to_pieces(_Rope_char_consumer
<_CharT
>& __c
,
922 const _RopeRep
* __r
, size_t __begin
, 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
>
983 _Rope_fill(basic_ostream
<_CharT
, _Traits
>& __o
, size_t __n
)
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
>
1007 basic_ostream
<_CharT
, _Traits
>&
1008 operator<<(basic_ostream
<_CharT
, _Traits
>& __o
,
1009 const rope
<_CharT
, _Alloc
>& __r
)
1011 size_t __w
= __o
.width();
1012 bool __left
= bool(__o
.flags() & std::ios::left
);
1014 size_t __rope_len
= __r
.size();
1015 _Rope_insert_char_consumer
<_CharT
, _Traits
> __c(__o
);
1016 bool __is_simple
= _Rope_is_simple((_CharT
*)0);
1018 if (__rope_len
< __w
)
1019 __pad_len
= __w
- __rope_len
;
1024 __o
.width(__w
/ __rope_len
);
1027 if (__is_simple
&& !__left
&& __pad_len
> 0)
1028 _Rope_fill(__o
, __pad_len
);
1029 __r
.apply_to_pieces(0, __r
.size(), __c
);
1030 if (__is_simple
&& __left
&& __pad_len
> 0)
1031 _Rope_fill(__o
, __pad_len
);
1039 __throw_exception_again
;
1044 template <class _CharT
, class _Alloc
>
1046 rope
<_CharT
, _Alloc
>::
1047 _S_flatten(_RopeRep
* __r
, size_t __start
, size_t __len
,
1050 _Rope_flatten_char_consumer
<_CharT
> __c(__buffer
);
1051 _S_apply_to_pieces(__c
, __r
, __start
, __start
+ __len
);
1052 return(__buffer
+ __len
);
1055 template <class _CharT
, class _Alloc
>
1057 rope
<_CharT
, _Alloc
>::
1058 find(_CharT __pattern
, size_t __start
) const
1060 _Rope_find_char_char_consumer
<_CharT
> __c(__pattern
);
1061 _S_apply_to_pieces(__c
, this->_M_tree_ptr
, __start
, size());
1062 size_type __result_pos
= __start
+ __c
._M_count
;
1063 #ifndef __STL_OLD_ROPE_SEMANTICS
1064 if (__result_pos
== size())
1065 __result_pos
= npos
;
1067 return __result_pos
;
1070 template <class _CharT
, class _Alloc
>
1072 rope
<_CharT
, _Alloc
>::
1073 _S_flatten(_RopeRep
* __r
, _CharT
* __buffer
)
1079 case __detail::_S_concat
:
1081 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1082 _RopeRep
* __left
= __c
->_M_left
;
1083 _RopeRep
* __right
= __c
->_M_right
;
1084 _CharT
* __rest
= _S_flatten(__left
, __buffer
);
1085 return _S_flatten(__right
, __rest
);
1087 case __detail::_S_leaf
:
1089 _RopeLeaf
* __l
= (_RopeLeaf
*)__r
;
1090 return copy_n(__l
->_M_data
, __l
->_M_size
, __buffer
).second
;
1092 case __detail::_S_function
:
1093 case __detail::_S_substringfn
:
1094 // We don't yet do anything with substring nodes.
1095 // This needs to be fixed before ropefiles will work well.
1097 _RopeFunction
* __f
= (_RopeFunction
*)__r
;
1098 (*(__f
->_M_fn
))(0, __f
->_M_size
, __buffer
);
1099 return __buffer
+ __f
->_M_size
;
1106 // This needs work for _CharT != char
1107 template <class _CharT
, class _Alloc
>
1109 rope
<_CharT
, _Alloc
>::
1110 _S_dump(_RopeRep
* __r
, int __indent
)
1112 for (int __i
= 0; __i
< __indent
; __i
++)
1119 if (_S_concat
== __r
->_M_tag
)
1121 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1122 _RopeRep
* __left
= __c
->_M_left
;
1123 _RopeRep
* __right
= __c
->_M_right
;
1126 printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
1127 __r
, __r
->_M_depth
, __r
->_M_size
,
1128 __r
->_M_is_balanced
? "" : "not");
1130 printf("Concatenation %p (rc = %ld, depth = %d, "
1131 "len = %ld, %s balanced)\n",
1132 __r
, __r
->_M_ref_count
, __r
->_M_depth
, __r
->_M_size
,
1133 __r
->_M_is_balanced
? "" : "not");
1135 _S_dump(__left
, __indent
+ 2);
1136 _S_dump(__right
, __indent
+ 2);
1143 switch (__r
->_M_tag
)
1145 case __detail::_S_leaf
:
1148 case __detail::_S_function
:
1149 __kind
= "Function";
1151 case __detail::_S_substringfn
:
1152 __kind
= "Function representing substring";
1155 __kind
= "(corrupted kind field!)";
1158 printf("%s %p (depth = %d, len = %ld) ",
1159 __kind
, __r
, __r
->_M_depth
, __r
->_M_size
);
1161 printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
1162 __kind
, __r
, __r
->_M_ref_count
, __r
->_M_depth
, __r
->_M_size
);
1164 if (_S_is_one_byte_char_type((_CharT
*)0))
1166 const int __max_len
= 40;
1167 _Self_destruct_ptr
__prefix(_S_substring(__r
, 0, __max_len
));
1168 _CharT __buffer
[__max_len
+ 1];
1169 bool __too_big
= __r
->_M_size
> __prefix
->_M_size
;
1171 _S_flatten(__prefix
, __buffer
);
1172 __buffer
[__prefix
->_M_size
] = _S_eos((_CharT
*)0);
1173 printf("%s%s\n", (char*)__buffer
,
1174 __too_big
? "...\n" : "\n");
1181 template <class _CharT
, class _Alloc
>
1183 rope
<_CharT
, _Alloc
>::
1184 _S_min_len
[int(__detail::_S_max_rope_depth
) + 1] = {
1185 /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21,
1186 /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377,
1187 /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181,
1188 /* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368,
1189 /* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811,
1190 /* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309,
1191 /* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352,
1192 /* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155,
1193 /* 39 */165580141, /* 40 */267914296, /* 41 */433494437,
1194 /* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903,
1195 /* 45 */2971215073u };
1196 // These are Fibonacci numbers < 2**32.
1198 template <class _CharT
, class _Alloc
>
1199 typename rope
<_CharT
, _Alloc
>::_RopeRep
*
1200 rope
<_CharT
, _Alloc
>::
1201 _S_balance(_RopeRep
* __r
)
1203 _RopeRep
* __forest
[int(__detail::_S_max_rope_depth
) + 1];
1204 _RopeRep
* __result
= 0;
1207 // The concatenation of forest in descending order is equal to __r.
1208 // __forest[__i]._M_size >= _S_min_len[__i]
1209 // __forest[__i]._M_depth = __i
1210 // References from forest are included in refcount.
1212 for (__i
= 0; __i
<= int(__detail::_S_max_rope_depth
); ++__i
)
1216 _S_add_to_forest(__r
, __forest
);
1217 for (__i
= 0; __i
<= int(__detail::_S_max_rope_depth
); ++__i
)
1218 if (0 != __forest
[__i
])
1221 _Self_destruct_ptr
__old(__result
);
1223 __result
= _S_concat(__forest
[__i
], __result
);
1224 __forest
[__i
]->_M_unref_nonnil();
1225 #if !defined(__GC) && defined(__EXCEPTIONS)
1232 for(__i
= 0; __i
<= int(__detail::_S_max_rope_depth
); __i
++)
1233 _S_unref(__forest
[__i
]);
1234 __throw_exception_again
;
1237 if (__result
->_M_depth
> int(__detail::_S_max_rope_depth
))
1238 __throw_length_error(__N("rope::_S_balance"));
1242 template <class _CharT
, class _Alloc
>
1244 rope
<_CharT
, _Alloc
>::
1245 _S_add_to_forest(_RopeRep
* __r
, _RopeRep
** __forest
)
1247 if (__r
->_M_is_balanced
)
1249 _S_add_leaf_to_forest(__r
, __forest
);
1254 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1256 _S_add_to_forest(__c
->_M_left
, __forest
);
1257 _S_add_to_forest(__c
->_M_right
, __forest
);
1262 template <class _CharT
, class _Alloc
>
1264 rope
<_CharT
, _Alloc
>::
1265 _S_add_leaf_to_forest(_RopeRep
* __r
, _RopeRep
** __forest
)
1267 _RopeRep
* __insertee
; // included in refcount
1268 _RopeRep
* __too_tiny
= 0; // included in refcount
1269 int __i
; // forest[0..__i-1] is empty
1270 size_t __s
= __r
->_M_size
;
1272 for (__i
= 0; __s
>= _S_min_len
[__i
+1]/* not this bucket */; ++__i
)
1274 if (0 != __forest
[__i
])
1277 _Self_destruct_ptr
__old(__too_tiny
);
1279 __too_tiny
= _S_concat_and_set_balanced(__forest
[__i
],
1281 __forest
[__i
]->_M_unref_nonnil();
1287 _Self_destruct_ptr
__old(__too_tiny
);
1289 __insertee
= _S_concat_and_set_balanced(__too_tiny
, __r
);
1291 // Too_tiny dead, and no longer included in refcount.
1292 // Insertee is live and included.
1295 if (0 != __forest
[__i
])
1298 _Self_destruct_ptr
__old(__insertee
);
1300 __insertee
= _S_concat_and_set_balanced(__forest
[__i
],
1302 __forest
[__i
]->_M_unref_nonnil();
1305 if (__i
== int(__detail::_S_max_rope_depth
)
1306 || __insertee
->_M_size
< _S_min_len
[__i
+1])
1308 __forest
[__i
] = __insertee
;
1309 // refcount is OK since __insertee is now dead.
1315 template <class _CharT
, class _Alloc
>
1317 rope
<_CharT
, _Alloc
>::
1318 _S_fetch(_RopeRep
* __r
, size_type __i
)
1320 __GC_CONST _CharT
* __cstr
= __r
->_M_c_string
;
1328 case __detail::_S_concat
:
1330 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1331 _RopeRep
* __left
= __c
->_M_left
;
1332 size_t __left_len
= __left
->_M_size
;
1334 if (__i
>= __left_len
)
1337 __r
= __c
->_M_right
;
1343 case __detail::_S_leaf
:
1345 _RopeLeaf
* __l
= (_RopeLeaf
*)__r
;
1346 return __l
->_M_data
[__i
];
1348 case __detail::_S_function
:
1349 case __detail::_S_substringfn
:
1351 _RopeFunction
* __f
= (_RopeFunction
*)__r
;
1354 (*(__f
->_M_fn
))(__i
, 1, &__result
);
1362 // Return a uniquely referenced character slot for the given
1363 // position, or 0 if that's not possible.
1364 template <class _CharT
, class _Alloc
>
1366 rope
<_CharT
, _Alloc
>::
1367 _S_fetch_ptr(_RopeRep
* __r
, size_type __i
)
1369 _RopeRep
* __clrstack
[__detail::_S_max_rope_depth
];
1374 if (__r
->_M_ref_count
> 1)
1378 case __detail::_S_concat
:
1380 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1381 _RopeRep
* __left
= __c
->_M_left
;
1382 size_t __left_len
= __left
->_M_size
;
1384 if (__c
->_M_c_string
!= 0)
1385 __clrstack
[__csptr
++] = __c
;
1386 if (__i
>= __left_len
)
1389 __r
= __c
->_M_right
;
1395 case __detail::_S_leaf
:
1397 _RopeLeaf
* __l
= (_RopeLeaf
*)__r
;
1398 if (__l
->_M_c_string
!= __l
->_M_data
&& __l
->_M_c_string
!= 0)
1399 __clrstack
[__csptr
++] = __l
;
1403 _RopeRep
* __d
= __clrstack
[__csptr
];
1404 __d
->_M_free_c_string();
1405 __d
->_M_c_string
= 0;
1407 return __l
->_M_data
+ __i
;
1409 case __detail::_S_function
:
1410 case __detail::_S_substringfn
:
1417 // The following could be implemented trivially using
1418 // lexicographical_compare_3way.
1419 // We do a little more work to avoid dealing with rope iterators for
1421 template <class _CharT
, class _Alloc
>
1423 rope
<_CharT
, _Alloc
>::
1424 _S_compare (const _RopeRep
* __left
, const _RopeRep
* __right
)
1433 __left_len
= __left
->_M_size
;
1434 __right_len
= __right
->_M_size
;
1435 if (__detail::_S_leaf
== __left
->_M_tag
)
1437 _RopeLeaf
* __l
= (_RopeLeaf
*) __left
;
1438 if (__detail::_S_leaf
== __right
->_M_tag
)
1440 _RopeLeaf
* __r
= (_RopeLeaf
*) __right
;
1441 return lexicographical_compare_3way(__l
->_M_data
,
1442 __l
->_M_data
+ __left_len
,
1443 __r
->_M_data
, __r
->_M_data
1448 const_iterator
__rstart(__right
, 0);
1449 const_iterator
__rend(__right
, __right_len
);
1450 return lexicographical_compare_3way(__l
->_M_data
, __l
->_M_data
1457 const_iterator
__lstart(__left
, 0);
1458 const_iterator
__lend(__left
, __left_len
);
1459 if (__detail::_S_leaf
== __right
->_M_tag
)
1461 _RopeLeaf
* __r
= (_RopeLeaf
*) __right
;
1462 return lexicographical_compare_3way(__lstart
, __lend
,
1463 __r
->_M_data
, __r
->_M_data
1468 const_iterator
__rstart(__right
, 0);
1469 const_iterator
__rend(__right
, __right_len
);
1470 return lexicographical_compare_3way(__lstart
, __lend
,
1476 // Assignment to reference proxies.
1477 template <class _CharT
, class _Alloc
>
1478 _Rope_char_ref_proxy
<_CharT
, _Alloc
>&
1479 _Rope_char_ref_proxy
<_CharT
, _Alloc
>::
1480 operator=(_CharT __c
)
1482 _RopeRep
* __old
= _M_root
->_M_tree_ptr
;
1484 // First check for the case in which everything is uniquely
1485 // referenced. In that case we can do this destructively.
1486 _CharT
* __ptr
= _My_rope::_S_fetch_ptr(__old
, _M_pos
);
1493 _Self_destruct_ptr
__left(_My_rope::_S_substring(__old
, 0, _M_pos
));
1494 _Self_destruct_ptr
__right(_My_rope::_S_substring(__old
, _M_pos
+ 1,
1496 _Self_destruct_ptr
__result_left(_My_rope::
1497 _S_destr_concat_char_iter(__left
,
1500 _RopeRep
* __result
= _My_rope::_S_concat(__result_left
, __right
);
1502 _RopeRep::_S_unref(__old
);
1504 _M_root
->_M_tree_ptr
= __result
;
1508 template <class _CharT
, class _Alloc
>
1509 inline _Rope_char_ref_proxy
<_CharT
, _Alloc
>::
1510 operator _CharT() const
1512 if (_M_current_valid
)
1515 return _My_rope::_S_fetch(_M_root
->_M_tree_ptr
, _M_pos
);
1518 template <class _CharT
, class _Alloc
>
1519 _Rope_char_ptr_proxy
<_CharT
, _Alloc
>
1520 _Rope_char_ref_proxy
<_CharT
, _Alloc
>::
1522 { return _Rope_char_ptr_proxy
<_CharT
, _Alloc
>(*this); }
1524 template <class _CharT
, class _Alloc
>
1525 rope
<_CharT
, _Alloc
>::
1526 rope(size_t __n
, _CharT __c
, const allocator_type
& __a
)
1529 rope
<_CharT
,_Alloc
> __result
;
1530 const size_t __exponentiate_threshold
= 32;
1533 _CharT
* __rest_buffer
;
1534 _RopeRep
* __remainder
;
1535 rope
<_CharT
, _Alloc
> __remainder_rope
;
1540 __exponent
= __n
/ __exponentiate_threshold
;
1541 __rest
= __n
% __exponentiate_threshold
;
1546 __rest_buffer
= this->_Data_allocate(_S_rounded_up_size(__rest
));
1547 __uninitialized_fill_n_a(__rest_buffer
, __rest
, __c
,
1548 _M_get_allocator());
1549 _S_cond_store_eos(__rest_buffer
[__rest
]);
1551 { __remainder
= _S_new_RopeLeaf(__rest_buffer
, __rest
,
1552 _M_get_allocator()); }
1555 _RopeRep::__STL_FREE_STRING(__rest_buffer
, __rest
,
1556 _M_get_allocator());
1557 __throw_exception_again
;
1560 __remainder_rope
._M_tree_ptr
= __remainder
;
1561 if (__exponent
!= 0)
1563 _CharT
* __base_buffer
=
1564 this->_Data_allocate(_S_rounded_up_size(__exponentiate_threshold
));
1565 _RopeLeaf
* __base_leaf
;
1567 __uninitialized_fill_n_a(__base_buffer
, __exponentiate_threshold
, __c
,
1568 _M_get_allocator());
1569 _S_cond_store_eos(__base_buffer
[__exponentiate_threshold
]);
1572 __base_leaf
= _S_new_RopeLeaf(__base_buffer
,
1573 __exponentiate_threshold
,
1574 _M_get_allocator());
1578 _RopeRep::__STL_FREE_STRING(__base_buffer
,
1579 __exponentiate_threshold
,
1580 _M_get_allocator());
1581 __throw_exception_again
;
1583 __base_rope
._M_tree_ptr
= __base_leaf
;
1584 if (1 == __exponent
)
1585 __result
= __base_rope
;
1587 __result
= power(__base_rope
, __exponent
,
1588 _Rope_Concat_fn
<_CharT
, _Alloc
>());
1590 if (0 != __remainder
)
1591 __result
+= __remainder_rope
;
1594 __result
= __remainder_rope
;
1596 this->_M_tree_ptr
= __result
._M_tree_ptr
;
1597 this->_M_tree_ptr
->_M_ref_nonnil();
1600 template<class _CharT
, class _Alloc
>
1602 rope
<_CharT
, _Alloc
>::_S_empty_c_str
[1];
1604 template<class _CharT
, class _Alloc
>
1606 rope
<_CharT
, _Alloc
>::
1609 if (0 == this->_M_tree_ptr
)
1611 _S_empty_c_str
[0] = _S_eos((_CharT
*)0); // Possibly redundant,
1612 // but probably fast.
1613 return _S_empty_c_str
;
1615 __gthread_mutex_lock (&this->_M_tree_ptr
->_M_c_string_lock
);
1616 __GC_CONST _CharT
* __result
= this->_M_tree_ptr
->_M_c_string
;
1619 size_t __s
= size();
1620 __result
= this->_Data_allocate(__s
+ 1);
1621 _S_flatten(this->_M_tree_ptr
, __result
);
1622 __result
[__s
] = _S_eos((_CharT
*)0);
1623 this->_M_tree_ptr
->_M_c_string
= __result
;
1625 __gthread_mutex_unlock (&this->_M_tree_ptr
->_M_c_string_lock
);
1629 template<class _CharT
, class _Alloc
>
1630 const _CharT
* rope
<_CharT
, _Alloc
>::
1631 replace_with_c_str()
1633 if (0 == this->_M_tree_ptr
)
1635 _S_empty_c_str
[0] = _S_eos((_CharT
*)0);
1636 return _S_empty_c_str
;
1638 __GC_CONST _CharT
* __old_c_string
= this->_M_tree_ptr
->_M_c_string
;
1639 if (__detail::_S_leaf
== this->_M_tree_ptr
->_M_tag
1640 && 0 != __old_c_string
)
1641 return(__old_c_string
);
1642 size_t __s
= size();
1643 _CharT
* __result
= this->_Data_allocate(_S_rounded_up_size(__s
));
1644 _S_flatten(this->_M_tree_ptr
, __result
);
1645 __result
[__s
] = _S_eos((_CharT
*)0);
1646 this->_M_tree_ptr
->_M_unref_nonnil();
1647 this->_M_tree_ptr
= _S_new_RopeLeaf(__result
, __s
,
1648 this->_M_get_allocator());
1652 // Algorithm specializations. More should be added.
1654 template<class _Rope_iterator
> // was templated on CharT and Alloc
1655 void // VC++ workaround
1656 _Rope_rotate(_Rope_iterator __first
,
1657 _Rope_iterator __middle
,
1658 _Rope_iterator __last
)
1660 typedef typename
_Rope_iterator::value_type _CharT
;
1661 typedef typename
_Rope_iterator::_allocator_type _Alloc
;
1663 rope
<_CharT
, _Alloc
>& __r(__first
.container());
1664 rope
<_CharT
, _Alloc
> __prefix
= __r
.substr(0, __first
.index());
1665 rope
<_CharT
, _Alloc
> __suffix
=
1666 __r
.substr(__last
.index(), __r
.size() - __last
.index());
1667 rope
<_CharT
, _Alloc
> __part1
=
1668 __r
.substr(__middle
.index(), __last
.index() - __middle
.index());
1669 rope
<_CharT
, _Alloc
> __part2
=
1670 __r
.substr(__first
.index(), __middle
.index() - __first
.index());
1677 #if !defined(__GNUC__)
1678 // Appears to confuse g++
1680 rotate(_Rope_iterator
<char, __STL_DEFAULT_ALLOCATOR(char)> __first
,
1681 _Rope_iterator
<char, __STL_DEFAULT_ALLOCATOR(char)> __middle
,
1682 _Rope_iterator
<char, __STL_DEFAULT_ALLOCATOR(char)> __last
)
1683 { _Rope_rotate(__first
, __middle
, __last
); }
1687 // Probably not useful for several reasons:
1688 // - for SGIs 7.1 compiler and probably some others,
1689 // this forces lots of rope<wchar_t, ...> instantiations, creating a
1690 // code bloat and compile time problem. (Fixed in 7.2.)
1691 // - wchar_t is 4 bytes wide on most UNIX platforms, making it
1692 // unattractive for unicode strings. Unsigned short may be a better
1695 rotate(_Rope_iterator
<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __first
,
1696 _Rope_iterator
<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __middle
,
1697 _Rope_iterator
<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __last
)
1698 { _Rope_rotate(__first
, __middle
, __last
); }
1701 _GLIBCXX_END_NAMESPACE