1 // SGI's rope class implementation -*- C++ -*-
3 // Copyright (C) 2001-2017 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 // <http://www.gnu.org/licenses/>.
27 * Silicon Graphics Computer Systems, Inc.
29 * Permission to use, copy, modify, distribute and sell this software
30 * and its documentation for any purpose is hereby granted without fee,
31 * provided that the above copyright notice appear in all copies and
32 * that both that copyright notice and this permission notice appear
33 * in supporting documentation. Silicon Graphics makes no
34 * representations about the suitability of this software for any
35 * purpose. It is provided "as is" without express or implied warranty.
39 * This is an internal header file, included by other library headers.
40 * Do not attempt to use it directly. @headername{ext/rope}
45 #include <bits/functexcept.h>
47 #include <ext/algorithm> // For copy_n and lexicographical_compare_3way
48 #include <ext/memory> // For uninitialized_copy_n
49 #include <ext/numeric> // For power
51 namespace __gnu_cxx
_GLIBCXX_VISIBILITY(default)
53 _GLIBCXX_BEGIN_NAMESPACE_VERSION
57 using std::basic_ostream
;
58 using std::__throw_length_error
;
60 using std::__uninitialized_fill_n_a
;
62 // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
63 // if necessary. Assumes _M_path_end[leaf_index] and leaf_pos are correct.
64 // Results in a valid buf_ptr if the iterator can be legitimately
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
;
109 // Set path and buffer inside a rope iterator. We assume that
110 // pos and root are already set.
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; /* index into path */
119 size_t __curr_start_pos
= 0;
120 size_t __pos
= __x
._M_current_pos
;
121 unsigned char __dirns
= 0; // Bit vector marking right turns in the path
123 if (__pos
>= __x
._M_root
->_M_size
)
128 __curr_rope
= __x
._M_root
;
129 if (0 != __curr_rope
->_M_c_string
)
131 /* Treat the root as a leaf. */
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
;
172 // Copy last section of path into _M_path_end.
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
;
186 // Specialized version of the above. Assumes that
187 // the path cache is valid for the previous position.
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
)
202 /* More stuff in this leaf, we just didn't cache it. */
206 // node_start_pos is starting position of last_node.
207 while (--__current_index
>= 0)
209 if (!(__dirns
& 1) /* Path turned left */)
211 __current_node
= __x
._M_path_end
[__current_index
];
212 __c
= (_Rope_RopeConcatenation
<_CharT
, _Alloc
>*)__current_node
;
213 // Otherwise we were in the right child. Thus we should pop
214 // the concatenation node.
215 __node_start_pos
-= __c
->_M_left
->_M_size
;
218 if (__current_index
< 0)
220 // We underflowed the cache. Punt.
224 __current_node
= __x
._M_path_end
[__current_index
];
225 __c
= (_Rope_RopeConcatenation
<_CharT
, _Alloc
>*)__current_node
;
226 // current_node is a concatenation node. We are positioned on the first
227 // character in its right child.
228 // node_start_pos is starting position of 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
;
247 // node_start_pos is unchanged.
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
)
299 // _Rope was modified. Get things fixed up.
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))
357 _Destroy(__s
, __s
+ __n
, __a
);
359 // This has to be a static member, so this gets a bit messy
361 _Rope_RopeLeaf
<_CharT
, _Alloc
>::_S_rounded_up_size(__n
));
364 // There are several reasons for not doing this with virtual destructors
365 // and a class specific delete operator:
366 // - A class specific delete operator can't easily get access to
367 // allocator instances if we need them.
368 // - Any virtual function would need a 4 or byte vtable pointer;
369 // this only requires a one byte tag per object.
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
)
423 // Concatenate a C string onto a leaf rope by copying the rope data.
424 // Used for short ropes.
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
));
435 uninitialized_copy_n(__r
->_M_data
, __old_len
, __new_data
);
436 uninitialized_copy_n(__iter
, __len
, __new_data
+ __old_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
;
453 // As above, but it's OK to clobber original if refcount is 1
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
)
465 // The space has been partially initialized for the standard
466 // character types. But that doesn't matter for those types.
467 uninitialized_copy_n(__iter
, __len
, __r
->_M_data
+ __old_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
);
487 // Assumes left and right are not 0.
488 // Does not increment (nor decrement on exception) child reference counts.
489 // Result has ref count 1.
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
;
516 // In case of exception, we need to deallocate
517 // otherwise dangling result node. But caller
518 // still owns its children. Thus unref is
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; // One more than before
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; // One more than before.
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
)
727 __base
->_M_ref_nonnil();
735 __adj_endp1
= __endp1
;
737 switch(__base
->_M_tag
)
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; // Not eos terminated.
777 // We should sometimes create substring node instead.
778 __result
= __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__l
->_M_data
+ __start
,
785 case __detail::_S_substringfn
:
786 // Avoid introducing multiple layers of substring nodes.
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());
802 } // *** else fall through: ***
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());
832 // Create substring node.
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
)
854 uninitialized_copy_n(__leaf
, __n
, _M_buf_ptr
);
860 template<class _CharT
>
861 class _Rope_find_char_char_consumer
862 : public _Rope_char_consumer
<_CharT
>
867 size_t _M_count
; // Number of nonmatching characters
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
>
891 // Here _CharT is both the stream and rope character type.
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() { }
902 // Caller is presumed to own the ostream
903 bool operator() (const _CharT
* __leaf
, size_t __n
);
904 // Returns true to continue traversal.
907 template<class _CharT
, class _Traits
>
909 _Rope_insert_char_consumer
<_CharT
, _Traits
>::
910 operator()(const _CharT
* __leaf
, size_t __n
)
913 // We assume that formatting is set up correctly for each element.
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();
1013 bool __left
= bool(__o
.flags() & std::ios::left
);
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
:
1095 // We don't yet do anything with substring nodes.
1096 // This needs to be fixed before ropefiles will work well.
1098 _RopeFunction
* __f
= (_RopeFunction
*)__r
;
1099 (*(__f
->_M_fn
))(0, __f
->_M_size
, __buffer
);
1100 return __buffer
+ __f
->_M_size
;
1107 // This needs work for _CharT != char
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 /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21,
1187 /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377,
1188 /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181,
1189 /* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368,
1190 /* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811,
1191 /* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309,
1192 /* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352,
1193 /* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155,
1194 /* 39 */165580141, /* 40 */267914296, /* 41 */433494437,
1195 /* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903,
1196 /* 45 */2971215073u };
1197 // These are Fibonacci numbers < 2**32.
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;
1208 // The concatenation of forest in descending order is equal to __r.
1209 // __forest[__i]._M_size >= _S_min_len[__i]
1210 // __forest[__i]._M_depth = __i
1211 // References from forest are included in refcount.
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
; // included in refcount
1269 _RopeRep
* __too_tiny
= 0; // included in refcount
1270 int __i
; // forest[0..__i-1] is empty
1271 size_t __s
= __r
->_M_size
;
1273 for (__i
= 0; __s
>= _S_min_len
[__i
+1]/* not this bucket */; ++__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
);
1292 // Too_tiny dead, and no longer included in refcount.
1293 // Insertee is live and included.
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
;
1310 // refcount is OK since __insertee is now dead.
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
);
1363 // Return a uniquely referenced character slot for the given
1364 // position, or 0 if that's not possible.
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
:
1418 // The following could be implemented trivially using
1419 // lexicographical_compare_3way.
1420 // We do a little more work to avoid dealing with rope iterators for
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
;
1442 return lexicographical_compare_3way(__l
->_M_data
,
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
);
1451 return lexicographical_compare_3way(__l
->_M_data
, __l
->_M_data
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
;
1463 return lexicographical_compare_3way(__lstart
, __lend
,
1464 __r
->_M_data
, __r
->_M_data
1469 const_iterator
__rstart(__right
, 0);
1470 const_iterator
__rend(__right
, __right_len
);
1471 return lexicographical_compare_3way(__lstart
, __lend
,
1477 // Assignment to reference proxies.
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
;
1485 // First check for the case in which everything is uniquely
1486 // referenced. In that case we can do this destructively.
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
>
1521 _Rope_char_ref_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); // Possibly redundant,
1613 // but probably fast.
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());
1653 // Algorithm specializations. More should be added.
1655 template<class _Rope_iterator
> // was templated on CharT and Alloc
1656 void // VC++ workaround
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__)
1679 // Appears to confuse g++
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
); }
1688 // Probably not useful for several reasons:
1689 // - for SGIs 7.1 compiler and probably some others,
1690 // this forces lots of rope<wchar_t, ...> instantiations, creating a
1691 // code bloat and compile time problem. (Fixed in 7.2.)
1692 // - wchar_t is 4 bytes wide on most UNIX platforms, making it
1693 // unattractive for unicode strings. Unsigned short may be a better
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