1 // SGI's rope class implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003 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 2, 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 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
32 * Silicon Graphics Computer Systems, Inc.
34 * Permission to use, copy, modify, distribute and sell this software
35 * and its documentation for any purpose is hereby granted without fee,
36 * provided that the above copyright notice appear in all copies and
37 * that both that copyright notice and this permission notice appear
38 * in supporting documentation. Silicon Graphics makes no
39 * representations about the suitability of this software for any
40 * purpose. It is provided "as is" without express or implied warranty.
44 * This is an internal header file, included by other library headers.
45 * You should not attempt to use it directly.
50 #include <bits/functexcept.h>
52 #include <ext/algorithm> // For copy_n and lexicographical_compare_3way
53 #include <ext/memory> // For uninitialized_copy_n
54 #include <ext/numeric> // For power
60 using std::basic_ostream
;
61 using std::__throw_length_error
;
64 using std::uninitialized_fill_n
;
66 // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
67 // if necessary. Assumes _M_path_end[leaf_index] and leaf_pos are correct.
68 // Results in a valid buf_ptr if the iterator can be legitimately
70 template <class _CharT
, class _Alloc
>
71 void _Rope_iterator_base
<_CharT
,_Alloc
>::_S_setbuf(
72 _Rope_iterator_base
<_CharT
,_Alloc
>& __x
)
74 const _RopeRep
* __leaf
= __x
._M_path_end
[__x
._M_leaf_index
];
75 size_t __leaf_pos
= __x
._M_leaf_pos
;
76 size_t __pos
= __x
._M_current_pos
;
78 switch(__leaf
->_M_tag
) {
79 case _RopeRep::_S_leaf
:
81 ((_Rope_RopeLeaf
<_CharT
,_Alloc
>*)__leaf
)->_M_data
;
82 __x
._M_buf_ptr
= __x
._M_buf_start
+ (__pos
- __leaf_pos
);
83 __x
._M_buf_end
= __x
._M_buf_start
+ __leaf
->_M_size
;
85 case _RopeRep::_S_function
:
86 case _RopeRep::_S_substringfn
:
88 size_t __len
= _S_iterator_buf_len
;
89 size_t __buf_start_pos
= __leaf_pos
;
90 size_t __leaf_end
= __leaf_pos
+ __leaf
->_M_size
;
91 char_producer
<_CharT
>* __fn
=
92 ((_Rope_RopeFunction
<_CharT
,_Alloc
>*)__leaf
)->_M_fn
;
94 if (__buf_start_pos
+ __len
<= __pos
) {
95 __buf_start_pos
= __pos
- __len
/4;
96 if (__buf_start_pos
+ __len
> __leaf_end
) {
97 __buf_start_pos
= __leaf_end
- __len
;
100 if (__buf_start_pos
+ __len
> __leaf_end
) {
101 __len
= __leaf_end
- __buf_start_pos
;
103 (*__fn
)(__buf_start_pos
- __leaf_pos
, __len
, __x
._M_tmp_buf
);
104 __x
._M_buf_ptr
= __x
._M_tmp_buf
+ (__pos
- __buf_start_pos
);
105 __x
._M_buf_start
= __x
._M_tmp_buf
;
106 __x
._M_buf_end
= __x
._M_tmp_buf
+ __len
;
114 // Set path and buffer inside a rope iterator. We assume that
115 // pos and root are already set.
116 template <class _CharT
, class _Alloc
>
117 void _Rope_iterator_base
<_CharT
,_Alloc
>::_S_setcache
118 (_Rope_iterator_base
<_CharT
,_Alloc
>& __x
)
120 const _RopeRep
* __path
[_RopeRep::_S_max_rope_depth
+1];
121 const _RopeRep
* __curr_rope
;
122 int __curr_depth
= -1; /* index into path */
123 size_t __curr_start_pos
= 0;
124 size_t __pos
= __x
._M_current_pos
;
125 unsigned char __dirns
= 0; // Bit vector marking right turns in the path
127 if (__pos
>= __x
._M_root
->_M_size
) {
131 __curr_rope
= __x
._M_root
;
132 if (0 != __curr_rope
->_M_c_string
) {
133 /* Treat the root as a leaf. */
134 __x
._M_buf_start
= __curr_rope
->_M_c_string
;
135 __x
._M_buf_end
= __curr_rope
->_M_c_string
+ __curr_rope
->_M_size
;
136 __x
._M_buf_ptr
= __curr_rope
->_M_c_string
+ __pos
;
137 __x
._M_path_end
[0] = __curr_rope
;
138 __x
._M_leaf_index
= 0;
144 __path
[__curr_depth
] = __curr_rope
;
145 switch(__curr_rope
->_M_tag
) {
146 case _RopeRep::_S_leaf
:
147 case _RopeRep::_S_function
:
148 case _RopeRep::_S_substringfn
:
149 __x
._M_leaf_pos
= __curr_start_pos
;
151 case _RopeRep::_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
) {
161 __curr_rope
= __c
->_M_right
;
162 __curr_start_pos
+= __left_len
;
164 __curr_rope
= __left
;
171 // Copy last section of path into _M_path_end.
174 int __j
= __curr_depth
+ 1 - _S_path_cache_len
;
176 if (__j
< 0) __j
= 0;
177 while (__j
<= __curr_depth
) {
178 __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
>
189 void _Rope_iterator_base
<_CharT
,_Alloc
>::_S_setcache_for_incr
190 (_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
) {
200 /* More stuff in this leaf, we just didn't cache it. */
204 // node_start_pos is starting position of last_node.
205 while (--__current_index
>= 0) {
206 if (!(__dirns
& 1) /* Path turned left */)
208 __current_node
= __x
._M_path_end
[__current_index
];
209 __c
= (_Rope_RopeConcatenation
<_CharT
,_Alloc
>*)__current_node
;
210 // Otherwise we were in the right child. Thus we should pop
211 // the concatenation node.
212 __node_start_pos
-= __c
->_M_left
->_M_size
;
215 if (__current_index
< 0) {
216 // We underflowed the cache. Punt.
220 __current_node
= __x
._M_path_end
[__current_index
];
221 __c
= (_Rope_RopeConcatenation
<_CharT
,_Alloc
>*)__current_node
;
222 // current_node is a concatenation node. We are positioned on the first
223 // character in its right child.
224 // node_start_pos is starting position of current_node.
225 __node_start_pos
+= __c
->_M_left
->_M_size
;
226 __current_node
= __c
->_M_right
;
227 __x
._M_path_end
[++__current_index
] = __current_node
;
229 while (_RopeRep::_S_concat
== __current_node
->_M_tag
) {
231 if (_S_path_cache_len
== __current_index
) {
233 for (__i
= 0; __i
< _S_path_cache_len
-1; __i
++) {
234 __x
._M_path_end
[__i
] = __x
._M_path_end
[__i
+1];
239 ((_Rope_RopeConcatenation
<_CharT
,_Alloc
>*)__current_node
)->_M_left
;
240 __x
._M_path_end
[__current_index
] = __current_node
;
242 // node_start_pos is unchanged.
244 __x
._M_leaf_index
= __current_index
;
245 __x
._M_leaf_pos
= __node_start_pos
;
246 __x
._M_path_directions
= __dirns
;
250 template <class _CharT
, class _Alloc
>
251 void _Rope_iterator_base
<_CharT
,_Alloc
>::_M_incr(size_t __n
) {
252 _M_current_pos
+= __n
;
253 if (0 != _M_buf_ptr
) {
254 size_t __chars_left
= _M_buf_end
- _M_buf_ptr
;
255 if (__chars_left
> __n
) {
257 } else if (__chars_left
== __n
) {
259 _S_setcache_for_incr(*this);
266 template <class _CharT
, class _Alloc
>
267 void _Rope_iterator_base
<_CharT
,_Alloc
>::_M_decr(size_t __n
) {
268 if (0 != _M_buf_ptr
) {
269 size_t __chars_left
= _M_buf_ptr
- _M_buf_start
;
270 if (__chars_left
>= __n
) {
276 _M_current_pos
-= __n
;
279 template <class _CharT
, class _Alloc
>
280 void _Rope_iterator
<_CharT
,_Alloc
>::_M_check() {
281 if (_M_root_rope
->_M_tree_ptr
!= this->_M_root
) {
282 // _Rope was modified. Get things fixed up.
283 _RopeRep::_S_unref(this->_M_root
);
284 this->_M_root
= _M_root_rope
->_M_tree_ptr
;
285 _RopeRep::_S_ref(this->_M_root
);
286 this->_M_buf_ptr
= 0;
290 template <class _CharT
, class _Alloc
>
292 _Rope_const_iterator
<_CharT
, _Alloc
>::_Rope_const_iterator(
293 const _Rope_iterator
<_CharT
,_Alloc
>& __x
)
294 : _Rope_iterator_base
<_CharT
,_Alloc
>(__x
)
297 template <class _CharT
, class _Alloc
>
298 inline _Rope_iterator
<_CharT
,_Alloc
>::_Rope_iterator(
299 rope
<_CharT
,_Alloc
>& __r
, size_t __pos
)
300 : _Rope_iterator_base
<_CharT
,_Alloc
>(__r
._M_tree_ptr
, __pos
),
303 _RopeRep::_S_ref(this->_M_root
);
306 template <class _CharT
, class _Alloc
>
308 rope
<_CharT
,_Alloc
>::_S_char_ptr_len(const _CharT
* __s
)
310 const _CharT
* __p
= __s
;
312 while (!_S_is0(*__p
)) { ++__p
; }
319 template <class _CharT
, class _Alloc
>
320 inline void _Rope_RopeRep
<_CharT
,_Alloc
>::_M_free_c_string()
322 _CharT
* __cstr
= _M_c_string
;
324 size_t __size
= this->_M_size
+ 1;
325 _Destroy(__cstr
, __cstr
+ __size
);
326 _Data_deallocate(__cstr
, __size
);
331 template <class _CharT
, class _Alloc
>
332 inline void _Rope_RopeRep
<_CharT
,_Alloc
>::_S_free_string(_CharT
* __s
,
336 if (!_S_is_basic_char_type((_CharT
*)0)) {
337 _Destroy(__s
, __s
+ __n
);
339 // This has to be a static member, so this gets a bit messy
341 __s
, _Rope_RopeLeaf
<_CharT
,_Alloc
>::_S_rounded_up_size(__n
));
345 // There are several reasons for not doing this with virtual destructors
346 // and a class specific delete operator:
347 // - A class specific delete operator can't easily get access to
348 // allocator instances if we need them.
349 // - Any virtual function would need a 4 or byte vtable pointer;
350 // this only requires a one byte tag per object.
351 template <class _CharT
, class _Alloc
>
352 void _Rope_RopeRep
<_CharT
,_Alloc
>::_M_free_tree()
357 _Rope_RopeLeaf
<_CharT
,_Alloc
>* __l
358 = (_Rope_RopeLeaf
<_CharT
,_Alloc
>*)this;
359 __l
->_Rope_RopeLeaf
<_CharT
,_Alloc
>::~_Rope_RopeLeaf();
360 _L_deallocate(__l
, 1);
365 _Rope_RopeConcatenation
<_CharT
,_Alloc
>* __c
366 = (_Rope_RopeConcatenation
<_CharT
,_Alloc
>*)this;
367 __c
->_Rope_RopeConcatenation
<_CharT
,_Alloc
>::
368 ~_Rope_RopeConcatenation();
369 _C_deallocate(__c
, 1);
374 _Rope_RopeFunction
<_CharT
,_Alloc
>* __f
375 = (_Rope_RopeFunction
<_CharT
,_Alloc
>*)this;
376 __f
->_Rope_RopeFunction
<_CharT
,_Alloc
>::~_Rope_RopeFunction();
377 _F_deallocate(__f
, 1);
382 _Rope_RopeSubstring
<_CharT
,_Alloc
>* __ss
=
383 (_Rope_RopeSubstring
<_CharT
,_Alloc
>*)this;
384 __ss
->_Rope_RopeSubstring
<_CharT
,_Alloc
>::
385 ~_Rope_RopeSubstring();
386 _S_deallocate(__ss
, 1);
393 template <class _CharT
, class _Alloc
>
394 inline void _Rope_RopeRep
<_CharT
,_Alloc
>::_S_free_string
395 (const _CharT
*, size_t, allocator_type
)
401 // Concatenate a C string onto a leaf rope by copying the rope data.
402 // Used for short ropes.
403 template <class _CharT
, class _Alloc
>
404 typename rope
<_CharT
,_Alloc
>::_RopeLeaf
*
405 rope
<_CharT
,_Alloc
>::_S_leaf_concat_char_iter
406 (_RopeLeaf
* __r
, const _CharT
* __iter
, size_t __len
)
408 size_t __old_len
= __r
->_M_size
;
409 _CharT
* __new_data
= (_CharT
*)
410 _Data_allocate(_S_rounded_up_size(__old_len
+ __len
));
413 uninitialized_copy_n(__r
->_M_data
, __old_len
, __new_data
);
414 uninitialized_copy_n(__iter
, __len
, __new_data
+ __old_len
);
415 _S_cond_store_eos(__new_data
[__old_len
+ __len
]);
417 __result
= _S_new_RopeLeaf(__new_data
, __old_len
+ __len
,
418 __r
->get_allocator());
422 _RopeRep::__STL_FREE_STRING(__new_data
, __old_len
+ __len
,
423 __r
->get_allocator());
424 __throw_exception_again
;
430 // As above, but it's OK to clobber original if refcount is 1
431 template <class _CharT
, class _Alloc
>
432 typename rope
<_CharT
,_Alloc
>::_RopeLeaf
*
433 rope
<_CharT
,_Alloc
>::_S_destr_leaf_concat_char_iter
434 (_RopeLeaf
* __r
, const _CharT
* __iter
, size_t __len
)
436 if (__r
->_M_ref_count
> 1)
437 return _S_leaf_concat_char_iter(__r
, __iter
, __len
);
438 size_t __old_len
= __r
->_M_size
;
439 if (_S_allocated_capacity(__old_len
) >= __old_len
+ __len
) {
440 // The space has been partially initialized for the standard
441 // character types. But that doesn't matter for those types.
442 uninitialized_copy_n(__iter
, __len
, __r
->_M_data
+ __old_len
);
443 if (_S_is_basic_char_type((_CharT
*)0)) {
444 _S_cond_store_eos(__r
->_M_data
[__old_len
+ __len
]);
445 } else if (__r
->_M_c_string
!= __r
->_M_data
&& 0 != __r
->_M_c_string
) {
446 __r
->_M_free_c_string();
447 __r
->_M_c_string
= 0;
449 __r
->_M_size
= __old_len
+ __len
;
450 __r
->_M_ref_count
= 2;
453 _RopeLeaf
* __result
= _S_leaf_concat_char_iter(__r
, __iter
, __len
);
459 // Assumes left and right are not 0.
460 // Does not increment (nor decrement on exception) child reference counts.
461 // Result has ref count 1.
462 template <class _CharT
, class _Alloc
>
463 typename rope
<_CharT
,_Alloc
>::_RopeRep
*
464 rope
<_CharT
,_Alloc
>::_S_tree_concat (_RopeRep
* __left
, _RopeRep
* __right
)
466 _RopeConcatenation
* __result
= _S_new_RopeConcatenation(__left
, __right
,
467 __left
->get_allocator());
468 size_t __depth
= __result
->_M_depth
;
470 if (__depth
> 20 && (__result
->_M_size
< 1000 ||
471 __depth
> _RopeRep::_S_max_rope_depth
))
473 _RopeRep
* __balanced
;
477 __balanced
= _S_balance(__result
);
478 __result
->_M_unref_nonnil();
482 _C_deallocate(__result
,1);
483 __throw_exception_again
;
485 // In case of exception, we need to deallocate
486 // otherwise dangling result node. But caller
487 // still owns its children. Thus unref is
495 template <class _CharT
, class _Alloc
>
497 rope
<_CharT
,_Alloc
>::_RopeRep
* rope
<_CharT
,_Alloc
>::_S_concat_char_iter
498 (_RopeRep
* __r
, const _CharT
*__s
, size_t __slen
)
506 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __slen
,
507 __r
->get_allocator());
508 if (_RopeRep::_S_leaf
== __r
->_M_tag
&&
509 __r
->_M_size
+ __slen
<= _S_copy_max
) {
510 __result
= _S_leaf_concat_char_iter((_RopeLeaf
*)__r
, __s
, __slen
);
513 if (_RopeRep::_S_concat
== __r
->_M_tag
514 && _RopeRep::_S_leaf
== ((_RopeConcatenation
*)__r
)->_M_right
->_M_tag
) {
516 (_RopeLeaf
* )(((_RopeConcatenation
* )__r
)->_M_right
);
517 if (__right
->_M_size
+ __slen
<= _S_copy_max
) {
518 _RopeRep
* __left
= ((_RopeConcatenation
*)__r
)->_M_left
;
520 _S_leaf_concat_char_iter((_RopeLeaf
*)__right
, __s
, __slen
);
521 __left
->_M_ref_nonnil();
523 __result
= _S_tree_concat(__left
, __nright
);
529 __throw_exception_again
;
535 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __slen
, __r
->get_allocator());
537 __r
->_M_ref_nonnil();
538 __result
= _S_tree_concat(__r
, __nright
);
544 __throw_exception_again
;
550 template <class _CharT
, class _Alloc
>
551 typename rope
<_CharT
,_Alloc
>::_RopeRep
*
552 rope
<_CharT
,_Alloc
>::_S_destr_concat_char_iter(
553 _RopeRep
* __r
, const _CharT
* __s
, size_t __slen
)
557 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __slen
,
558 __r
->get_allocator());
559 size_t __count
= __r
->_M_ref_count
;
560 size_t __orig_size
= __r
->_M_size
;
561 if (__count
> 1) return _S_concat_char_iter(__r
, __s
, __slen
);
563 __r
->_M_ref_count
= 2; // One more than before
566 if (__orig_size
+ __slen
<= _S_copy_max
&&
567 _RopeRep::_S_leaf
== __r
->_M_tag
) {
568 __result
= _S_destr_leaf_concat_char_iter((_RopeLeaf
*)__r
, __s
, __slen
);
571 if (_RopeRep::_S_concat
== __r
->_M_tag
) {
572 _RopeLeaf
* __right
= (_RopeLeaf
*)(((_RopeConcatenation
*)__r
)->_M_right
);
573 if (_RopeRep::_S_leaf
== __right
->_M_tag
574 && __right
->_M_size
+ __slen
<= _S_copy_max
) {
575 _RopeRep
* __new_right
=
576 _S_destr_leaf_concat_char_iter(__right
, __s
, __slen
);
577 if (__right
== __new_right
)
578 __new_right
->_M_ref_count
= 1;
580 __right
->_M_unref_nonnil();
581 __r
->_M_ref_count
= 2; // One more than before.
582 ((_RopeConcatenation
*)__r
)->_M_right
= __new_right
;
583 __r
->_M_size
= __orig_size
+ __slen
;
584 if (0 != __r
->_M_c_string
) {
585 __r
->_M_free_c_string();
586 __r
->_M_c_string
= 0;
592 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __slen
, __r
->get_allocator());
593 __r
->_M_ref_nonnil();
595 __result
= _S_tree_concat(__r
, __right
);
601 __throw_exception_again
;
607 template <class _CharT
, class _Alloc
>
608 typename rope
<_CharT
,_Alloc
>::_RopeRep
*
609 rope
<_CharT
,_Alloc
>::_S_concat(_RopeRep
* __left
, _RopeRep
* __right
)
616 __left
->_M_ref_nonnil();
619 if (_RopeRep::_S_leaf
== __right
->_M_tag
) {
620 if (_RopeRep::_S_leaf
== __left
->_M_tag
) {
621 if (__right
->_M_size
+ __left
->_M_size
<= _S_copy_max
) {
622 return _S_leaf_concat_char_iter((_RopeLeaf
*)__left
,
623 ((_RopeLeaf
*)__right
)->_M_data
,
626 } else if (_RopeRep::_S_concat
== __left
->_M_tag
627 && _RopeRep::_S_leaf
==
628 ((_RopeConcatenation
*)__left
)->_M_right
->_M_tag
) {
629 _RopeLeaf
* __leftright
=
630 (_RopeLeaf
*)(((_RopeConcatenation
*)__left
)->_M_right
);
631 if (__leftright
->_M_size
+ __right
->_M_size
<= _S_copy_max
) {
632 _RopeRep
* __leftleft
= ((_RopeConcatenation
*)__left
)->_M_left
;
633 _RopeRep
* __rest
= _S_leaf_concat_char_iter(__leftright
,
634 ((_RopeLeaf
*)__right
)->_M_data
,
636 __leftleft
->_M_ref_nonnil();
638 return(_S_tree_concat(__leftleft
, __rest
));
642 _S_unref(__leftleft
);
644 __throw_exception_again
;
649 __left
->_M_ref_nonnil();
650 __right
->_M_ref_nonnil();
652 return(_S_tree_concat(__left
, __right
));
658 __throw_exception_again
;
662 template <class _CharT
, class _Alloc
>
663 typename rope
<_CharT
,_Alloc
>::_RopeRep
*
664 rope
<_CharT
,_Alloc
>::_S_substring(_RopeRep
* __base
,
665 size_t __start
, size_t __endp1
)
667 if (0 == __base
) return 0;
668 size_t __len
= __base
->_M_size
;
670 const size_t __lazy_threshold
= 128;
672 if (__endp1
>= __len
) {
674 __base
->_M_ref_nonnil();
680 __adj_endp1
= __endp1
;
682 switch(__base
->_M_tag
) {
683 case _RopeRep::_S_concat
:
685 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__base
;
686 _RopeRep
* __left
= __c
->_M_left
;
687 _RopeRep
* __right
= __c
->_M_right
;
688 size_t __left_len
= __left
->_M_size
;
691 if (__adj_endp1
<= __left_len
) {
692 return _S_substring(__left
, __start
, __endp1
);
693 } else if (__start
>= __left_len
) {
694 return _S_substring(__right
, __start
- __left_len
,
695 __adj_endp1
- __left_len
);
697 _Self_destruct_ptr
__left_result(
698 _S_substring(__left
, __start
, __left_len
));
699 _Self_destruct_ptr
__right_result(
700 _S_substring(__right
, 0, __endp1
- __left_len
));
701 __result
= _S_concat(__left_result
, __right_result
);
704 case _RopeRep::_S_leaf
:
706 _RopeLeaf
* __l
= (_RopeLeaf
*)__base
;
709 if (__start
>= __adj_endp1
) return 0;
710 __result_len
= __adj_endp1
- __start
;
711 if (__result_len
> __lazy_threshold
) goto lazy
;
713 const _CharT
* __section
= __l
->_M_data
+ __start
;
714 __result
= _S_new_RopeLeaf(__section
, __result_len
,
715 __base
->get_allocator());
716 __result
->_M_c_string
= 0; // Not eos terminated.
718 // We should sometimes create substring node instead.
719 __result
= __STL_ROPE_FROM_UNOWNED_CHAR_PTR(
720 __l
->_M_data
+ __start
, __result_len
,
721 __base
->get_allocator());
725 case _RopeRep::_S_substringfn
:
726 // Avoid introducing multiple layers of substring nodes.
728 _RopeSubstring
* __old
= (_RopeSubstring
*)__base
;
730 if (__start
>= __adj_endp1
) return 0;
731 __result_len
= __adj_endp1
- __start
;
732 if (__result_len
> __lazy_threshold
) {
733 _RopeSubstring
* __result
=
734 _S_new_RopeSubstring(__old
->_M_base
,
735 __start
+ __old
->_M_start
,
736 __adj_endp1
- __start
,
737 __base
->get_allocator());
740 } // *** else fall through: ***
742 case _RopeRep::_S_function
:
744 _RopeFunction
* __f
= (_RopeFunction
*)__base
;
747 if (__start
>= __adj_endp1
) return 0;
748 __result_len
= __adj_endp1
- __start
;
750 if (__result_len
> __lazy_threshold
) goto lazy
;
751 __section
= (_CharT
*)
752 _Data_allocate(_S_rounded_up_size(__result_len
));
754 (*(__f
->_M_fn
))(__start
, __result_len
, __section
);
758 _RopeRep::__STL_FREE_STRING(
759 __section
, __result_len
, __base
->get_allocator());
760 __throw_exception_again
;
762 _S_cond_store_eos(__section
[__result_len
]);
763 return _S_new_RopeLeaf(__section
, __result_len
,
764 __base
->get_allocator());
769 // Create substring node.
770 return _S_new_RopeSubstring(__base
, __start
, __adj_endp1
- __start
,
771 __base
->get_allocator());
775 template<class _CharT
>
776 class _Rope_flatten_char_consumer
: public _Rope_char_consumer
<_CharT
> {
781 _Rope_flatten_char_consumer(_CharT
* __buffer
) {
782 _M_buf_ptr
= __buffer
;
784 ~_Rope_flatten_char_consumer() {}
785 bool operator() (const _CharT
* __leaf
, size_t __n
) {
786 uninitialized_copy_n(__leaf
, __n
, _M_buf_ptr
);
792 template<class _CharT
>
793 class _Rope_find_char_char_consumer
: public _Rope_char_consumer
<_CharT
> {
797 size_t _M_count
; // Number of nonmatching characters
798 _Rope_find_char_char_consumer(_CharT __p
)
799 : _M_pattern(__p
), _M_count(0) {}
800 ~_Rope_find_char_char_consumer() {}
801 bool operator() (const _CharT
* __leaf
, size_t __n
) {
803 for (__i
= 0; __i
< __n
; __i
++) {
804 if (__leaf
[__i
] == _M_pattern
) {
805 _M_count
+= __i
; return false;
808 _M_count
+= __n
; return true;
812 template<class _CharT
, class _Traits
>
813 // Here _CharT is both the stream and rope character type.
814 class _Rope_insert_char_consumer
: public _Rope_char_consumer
<_CharT
> {
816 typedef basic_ostream
<_CharT
,_Traits
> _Insert_ostream
;
817 _Insert_ostream
& _M_o
;
819 _Rope_insert_char_consumer(_Insert_ostream
& __writer
)
821 ~_Rope_insert_char_consumer() { };
822 // Caller is presumed to own the ostream
823 bool operator() (const _CharT
* __leaf
, size_t __n
);
824 // Returns true to continue traversal.
827 template<class _CharT
, class _Traits
>
828 bool _Rope_insert_char_consumer
<_CharT
, _Traits
>::operator()
829 (const _CharT
* __leaf
, size_t __n
)
832 // We assume that formatting is set up correctly for each element.
833 for (__i
= 0; __i
< __n
; __i
++) _M_o
.put(__leaf
[__i
]);
837 template <class _CharT
, class _Alloc
>
838 bool rope
<_CharT
, _Alloc
>::_S_apply_to_pieces(
839 _Rope_char_consumer
<_CharT
>& __c
,
841 size_t __begin
, size_t __end
)
843 if (0 == __r
) return true;
844 switch(__r
->_M_tag
) {
845 case _RopeRep::_S_concat
:
847 _RopeConcatenation
* __conc
= (_RopeConcatenation
*)__r
;
848 _RopeRep
* __left
= __conc
->_M_left
;
849 size_t __left_len
= __left
->_M_size
;
850 if (__begin
< __left_len
) {
851 size_t __left_end
= std::min(__left_len
, __end
);
852 if (!_S_apply_to_pieces(__c
, __left
, __begin
, __left_end
))
855 if (__end
> __left_len
) {
856 _RopeRep
* __right
= __conc
->_M_right
;
857 size_t __right_start
= std::max(__left_len
, __begin
);
858 if (!_S_apply_to_pieces(__c
, __right
,
859 __right_start
- __left_len
,
860 __end
- __left_len
)) {
866 case _RopeRep::_S_leaf
:
868 _RopeLeaf
* __l
= (_RopeLeaf
*)__r
;
869 return __c(__l
->_M_data
+ __begin
, __end
- __begin
);
871 case _RopeRep::_S_function
:
872 case _RopeRep::_S_substringfn
:
874 _RopeFunction
* __f
= (_RopeFunction
*)__r
;
875 size_t __len
= __end
- __begin
;
878 (_CharT
*)__alloc::allocate(__len
* sizeof(_CharT
));
880 (*(__f
->_M_fn
))(__begin
, __len
, __buffer
);
881 __result
= __c(__buffer
, __len
);
882 __alloc::deallocate(__buffer
, __len
* sizeof(_CharT
));
886 __alloc::deallocate(__buffer
, __len
* sizeof(_CharT
));
887 __throw_exception_again
;
896 template<class _CharT
, class _Traits
>
897 inline void _Rope_fill(basic_ostream
<_CharT
, _Traits
>& __o
, size_t __n
)
899 char __f
= __o
.fill();
902 for (__i
= 0; __i
< __n
; __i
++) __o
.put(__f
);
906 template <class _CharT
> inline bool _Rope_is_simple(_CharT
*) { return false; }
907 inline bool _Rope_is_simple(char*) { return true; }
908 inline bool _Rope_is_simple(wchar_t*) { return true; }
910 template<class _CharT
, class _Traits
, class _Alloc
>
911 basic_ostream
<_CharT
, _Traits
>& operator<< (basic_ostream
<_CharT
, _Traits
>& __o
,
912 const rope
<_CharT
, _Alloc
>& __r
)
914 size_t __w
= __o
.width();
915 bool __left
= bool(__o
.flags() & std::ios::left
);
917 size_t __rope_len
= __r
.size();
918 _Rope_insert_char_consumer
<_CharT
, _Traits
> __c(__o
);
919 bool __is_simple
= _Rope_is_simple((_CharT
*)0);
921 if (__rope_len
< __w
) {
922 __pad_len
= __w
- __rope_len
;
926 if (!__is_simple
) __o
.width(__w
/__rope_len
);
928 if (__is_simple
&& !__left
&& __pad_len
> 0) {
929 _Rope_fill(__o
, __pad_len
);
931 __r
.apply_to_pieces(0, __r
.size(), __c
);
932 if (__is_simple
&& __left
&& __pad_len
> 0) {
933 _Rope_fill(__o
, __pad_len
);
942 __throw_exception_again
;
947 template <class _CharT
, class _Alloc
>
949 rope
<_CharT
,_Alloc
>::_S_flatten(_RopeRep
* __r
,
950 size_t __start
, size_t __len
,
953 _Rope_flatten_char_consumer
<_CharT
> __c(__buffer
);
954 _S_apply_to_pieces(__c
, __r
, __start
, __start
+ __len
);
955 return(__buffer
+ __len
);
958 template <class _CharT
, class _Alloc
>
960 rope
<_CharT
,_Alloc
>::find(_CharT __pattern
, size_t __start
) const
962 _Rope_find_char_char_consumer
<_CharT
> __c(__pattern
);
963 _S_apply_to_pieces(__c
, this->_M_tree_ptr
, __start
, size());
964 size_type __result_pos
= __start
+ __c
._M_count
;
965 # ifndef __STL_OLD_ROPE_SEMANTICS
966 if (__result_pos
== size()) __result_pos
= npos
;
971 template <class _CharT
, class _Alloc
>
973 rope
<_CharT
,_Alloc
>::_S_flatten(_RopeRep
* __r
, _CharT
* __buffer
)
975 if (0 == __r
) return __buffer
;
976 switch(__r
->_M_tag
) {
977 case _RopeRep::_S_concat
:
979 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
980 _RopeRep
* __left
= __c
->_M_left
;
981 _RopeRep
* __right
= __c
->_M_right
;
982 _CharT
* __rest
= _S_flatten(__left
, __buffer
);
983 return _S_flatten(__right
, __rest
);
985 case _RopeRep::_S_leaf
:
987 _RopeLeaf
* __l
= (_RopeLeaf
*)__r
;
988 return copy_n(__l
->_M_data
, __l
->_M_size
, __buffer
).second
;
990 case _RopeRep::_S_function
:
991 case _RopeRep::_S_substringfn
:
992 // We don't yet do anything with substring nodes.
993 // This needs to be fixed before ropefiles will work well.
995 _RopeFunction
* __f
= (_RopeFunction
*)__r
;
996 (*(__f
->_M_fn
))(0, __f
->_M_size
, __buffer
);
997 return __buffer
+ __f
->_M_size
;
1005 // This needs work for _CharT != char
1006 template <class _CharT
, class _Alloc
>
1008 rope
<_CharT
,_Alloc
>::_S_dump(_RopeRep
* __r
, int __indent
)
1010 for (int __i
= 0; __i
< __indent
; __i
++) putchar(' ');
1012 printf("NULL\n"); return;
1014 if (_RopeRep::_S_concat
== __r
->_M_tag
) {
1015 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1016 _RopeRep
* __left
= __c
->_M_left
;
1017 _RopeRep
* __right
= __c
->_M_right
;
1020 printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
1021 __r
, __r
->_M_depth
, __r
->_M_size
, __r
->_M_is_balanced
? "" : "not");
1023 printf("Concatenation %p (rc = %ld, depth = %d, "
1024 "len = %ld, %s balanced)\n",
1025 __r
, __r
->_M_ref_count
, __r
->_M_depth
, __r
->_M_size
,
1026 __r
->_M_is_balanced
? "" : "not");
1028 _S_dump(__left
, __indent
+ 2);
1029 _S_dump(__right
, __indent
+ 2);
1034 switch (__r
->_M_tag
) {
1035 case _RopeRep::_S_leaf
:
1038 case _RopeRep::_S_function
:
1039 __kind
= "Function";
1041 case _RopeRep::_S_substringfn
:
1042 __kind
= "Function representing substring";
1045 __kind
= "(corrupted kind field!)";
1048 printf("%s %p (depth = %d, len = %ld) ",
1049 __kind
, __r
, __r
->_M_depth
, __r
->_M_size
);
1051 printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
1052 __kind
, __r
, __r
->_M_ref_count
, __r
->_M_depth
, __r
->_M_size
);
1054 if (_S_is_one_byte_char_type((_CharT
*)0)) {
1055 const int __max_len
= 40;
1056 _Self_destruct_ptr
__prefix(_S_substring(__r
, 0, __max_len
));
1057 _CharT __buffer
[__max_len
+ 1];
1058 bool __too_big
= __r
->_M_size
> __prefix
->_M_size
;
1060 _S_flatten(__prefix
, __buffer
);
1061 __buffer
[__prefix
->_M_size
] = _S_eos((_CharT
*)0);
1063 (char*)__buffer
, __too_big
? "...\n" : "\n");
1070 template <class _CharT
, class _Alloc
>
1072 rope
<_CharT
,_Alloc
>::_S_min_len
[
1073 _Rope_RopeRep
<_CharT
,_Alloc
>::_S_max_rope_depth
+ 1] = {
1074 /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21,
1075 /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377,
1076 /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181,
1077 /* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368,
1078 /* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811,
1079 /* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309,
1080 /* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352,
1081 /* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155,
1082 /* 39 */165580141, /* 40 */267914296, /* 41 */433494437,
1083 /* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903,
1084 /* 45 */2971215073u };
1085 // These are Fibonacci numbers < 2**32.
1087 template <class _CharT
, class _Alloc
>
1088 typename rope
<_CharT
,_Alloc
>::_RopeRep
*
1089 rope
<_CharT
,_Alloc
>::_S_balance(_RopeRep
* __r
)
1091 _RopeRep
* __forest
[_RopeRep::_S_max_rope_depth
+ 1];
1092 _RopeRep
* __result
= 0;
1095 // The concatenation of forest in descending order is equal to __r.
1096 // __forest[__i]._M_size >= _S_min_len[__i]
1097 // __forest[__i]._M_depth = __i
1098 // References from forest are included in refcount.
1100 for (__i
= 0; __i
<= _RopeRep::_S_max_rope_depth
; ++__i
)
1103 _S_add_to_forest(__r
, __forest
);
1104 for (__i
= 0; __i
<= _RopeRep::_S_max_rope_depth
; ++__i
)
1105 if (0 != __forest
[__i
]) {
1107 _Self_destruct_ptr
__old(__result
);
1109 __result
= _S_concat(__forest
[__i
], __result
);
1110 __forest
[__i
]->_M_unref_nonnil();
1111 # if !defined(__GC) && defined(__EXCEPTIONS)
1118 for(__i
= 0; __i
<= _RopeRep::_S_max_rope_depth
; __i
++)
1119 _S_unref(__forest
[__i
]);
1120 __throw_exception_again
;
1123 if (__result
->_M_depth
> _RopeRep::_S_max_rope_depth
)
1124 __throw_length_error("rope::_S_balance");
1129 template <class _CharT
, class _Alloc
>
1131 rope
<_CharT
,_Alloc
>::_S_add_to_forest(_RopeRep
* __r
, _RopeRep
** __forest
)
1133 if (__r
->_M_is_balanced
) {
1134 _S_add_leaf_to_forest(__r
, __forest
);
1139 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1141 _S_add_to_forest(__c
->_M_left
, __forest
);
1142 _S_add_to_forest(__c
->_M_right
, __forest
);
1147 template <class _CharT
, class _Alloc
>
1149 rope
<_CharT
,_Alloc
>::_S_add_leaf_to_forest(_RopeRep
* __r
, _RopeRep
** __forest
)
1151 _RopeRep
* __insertee
; // included in refcount
1152 _RopeRep
* __too_tiny
= 0; // included in refcount
1153 int __i
; // forest[0..__i-1] is empty
1154 size_t __s
= __r
->_M_size
;
1156 for (__i
= 0; __s
>= _S_min_len
[__i
+1]/* not this bucket */; ++__i
) {
1157 if (0 != __forest
[__i
]) {
1159 _Self_destruct_ptr
__old(__too_tiny
);
1161 __too_tiny
= _S_concat_and_set_balanced(__forest
[__i
], __too_tiny
);
1162 __forest
[__i
]->_M_unref_nonnil();
1168 _Self_destruct_ptr
__old(__too_tiny
);
1170 __insertee
= _S_concat_and_set_balanced(__too_tiny
, __r
);
1172 // Too_tiny dead, and no longer included in refcount.
1173 // Insertee is live and included.
1175 if (0 != __forest
[__i
]) {
1177 _Self_destruct_ptr
__old(__insertee
);
1179 __insertee
= _S_concat_and_set_balanced(__forest
[__i
], __insertee
);
1180 __forest
[__i
]->_M_unref_nonnil();
1183 if (__i
== _RopeRep::_S_max_rope_depth
||
1184 __insertee
->_M_size
< _S_min_len
[__i
+1]) {
1185 __forest
[__i
] = __insertee
;
1186 // refcount is OK since __insertee is now dead.
1192 template <class _CharT
, class _Alloc
>
1194 rope
<_CharT
,_Alloc
>::_S_fetch(_RopeRep
* __r
, size_type __i
)
1196 __GC_CONST _CharT
* __cstr
= __r
->_M_c_string
;
1198 if (0 != __cstr
) return __cstr
[__i
];
1200 switch(__r
->_M_tag
) {
1201 case _RopeRep::_S_concat
:
1203 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1204 _RopeRep
* __left
= __c
->_M_left
;
1205 size_t __left_len
= __left
->_M_size
;
1207 if (__i
>= __left_len
) {
1209 __r
= __c
->_M_right
;
1215 case _RopeRep::_S_leaf
:
1217 _RopeLeaf
* __l
= (_RopeLeaf
*)__r
;
1218 return __l
->_M_data
[__i
];
1220 case _RopeRep::_S_function
:
1221 case _RopeRep::_S_substringfn
:
1223 _RopeFunction
* __f
= (_RopeFunction
*)__r
;
1226 (*(__f
->_M_fn
))(__i
, 1, &__result
);
1234 // Return a uniquely referenced character slot for the given
1235 // position, or 0 if that's not possible.
1236 template <class _CharT
, class _Alloc
>
1238 rope
<_CharT
,_Alloc
>::_S_fetch_ptr(_RopeRep
* __r
, size_type __i
)
1240 _RopeRep
* __clrstack
[_RopeRep::_S_max_rope_depth
];
1244 if (__r
->_M_ref_count
> 1) return 0;
1245 switch(__r
->_M_tag
) {
1246 case _RopeRep::_S_concat
:
1248 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1249 _RopeRep
* __left
= __c
->_M_left
;
1250 size_t __left_len
= __left
->_M_size
;
1252 if (__c
->_M_c_string
!= 0) __clrstack
[__csptr
++] = __c
;
1253 if (__i
>= __left_len
) {
1255 __r
= __c
->_M_right
;
1261 case _RopeRep::_S_leaf
:
1263 _RopeLeaf
* __l
= (_RopeLeaf
*)__r
;
1264 if (__l
->_M_c_string
!= __l
->_M_data
&& __l
->_M_c_string
!= 0)
1265 __clrstack
[__csptr
++] = __l
;
1266 while (__csptr
> 0) {
1268 _RopeRep
* __d
= __clrstack
[__csptr
];
1269 __d
->_M_free_c_string();
1270 __d
->_M_c_string
= 0;
1272 return __l
->_M_data
+ __i
;
1274 case _RopeRep::_S_function
:
1275 case _RopeRep::_S_substringfn
:
1282 // The following could be implemented trivially using
1283 // lexicographical_compare_3way.
1284 // We do a little more work to avoid dealing with rope iterators for
1286 template <class _CharT
, class _Alloc
>
1288 rope
<_CharT
,_Alloc
>::_S_compare (const _RopeRep
* __left
,
1289 const _RopeRep
* __right
)
1294 if (0 == __right
) return 0 != __left
;
1295 if (0 == __left
) return -1;
1296 __left_len
= __left
->_M_size
;
1297 __right_len
= __right
->_M_size
;
1298 if (_RopeRep::_S_leaf
== __left
->_M_tag
) {
1299 _RopeLeaf
* __l
= (_RopeLeaf
*) __left
;
1300 if (_RopeRep::_S_leaf
== __right
->_M_tag
) {
1301 _RopeLeaf
* __r
= (_RopeLeaf
*) __right
;
1302 return lexicographical_compare_3way(
1303 __l
->_M_data
, __l
->_M_data
+ __left_len
,
1304 __r
->_M_data
, __r
->_M_data
+ __right_len
);
1306 const_iterator
__rstart(__right
, 0);
1307 const_iterator
__rend(__right
, __right_len
);
1308 return lexicographical_compare_3way(
1309 __l
->_M_data
, __l
->_M_data
+ __left_len
,
1313 const_iterator
__lstart(__left
, 0);
1314 const_iterator
__lend(__left
, __left_len
);
1315 if (_RopeRep::_S_leaf
== __right
->_M_tag
) {
1316 _RopeLeaf
* __r
= (_RopeLeaf
*) __right
;
1317 return lexicographical_compare_3way(
1319 __r
->_M_data
, __r
->_M_data
+ __right_len
);
1321 const_iterator
__rstart(__right
, 0);
1322 const_iterator
__rend(__right
, __right_len
);
1323 return lexicographical_compare_3way(
1330 // Assignment to reference proxies.
1331 template <class _CharT
, class _Alloc
>
1332 _Rope_char_ref_proxy
<_CharT
, _Alloc
>&
1333 _Rope_char_ref_proxy
<_CharT
, _Alloc
>::operator= (_CharT __c
) {
1334 _RopeRep
* __old
= _M_root
->_M_tree_ptr
;
1336 // First check for the case in which everything is uniquely
1337 // referenced. In that case we can do this destructively.
1338 _CharT
* __ptr
= _My_rope::_S_fetch_ptr(__old
, _M_pos
);
1344 _Self_destruct_ptr
__left(
1345 _My_rope::_S_substring(__old
, 0, _M_pos
));
1346 _Self_destruct_ptr
__right(
1347 _My_rope::_S_substring(__old
, _M_pos
+1, __old
->_M_size
));
1348 _Self_destruct_ptr
__result_left(
1349 _My_rope::_S_destr_concat_char_iter(__left
, &__c
, 1));
1351 _RopeRep
* __result
=
1352 _My_rope::_S_concat(__result_left
, __right
);
1354 _RopeRep::_S_unref(__old
);
1356 _M_root
->_M_tree_ptr
= __result
;
1360 template <class _CharT
, class _Alloc
>
1361 inline _Rope_char_ref_proxy
<_CharT
, _Alloc
>::operator _CharT () const
1363 if (_M_current_valid
) {
1366 return _My_rope::_S_fetch(_M_root
->_M_tree_ptr
, _M_pos
);
1369 template <class _CharT
, class _Alloc
>
1370 _Rope_char_ptr_proxy
<_CharT
, _Alloc
>
1371 _Rope_char_ref_proxy
<_CharT
, _Alloc
>::operator& () const {
1372 return _Rope_char_ptr_proxy
<_CharT
, _Alloc
>(*this);
1375 template <class _CharT
, class _Alloc
>
1376 rope
<_CharT
, _Alloc
>::rope(size_t __n
, _CharT __c
,
1377 const allocator_type
& __a
)
1380 rope
<_CharT
,_Alloc
> __result
;
1381 const size_t __exponentiate_threshold
= 32;
1384 _CharT
* __rest_buffer
;
1385 _RopeRep
* __remainder
;
1386 rope
<_CharT
,_Alloc
> __remainder_rope
;
1391 __exponent
= __n
/ __exponentiate_threshold
;
1392 __rest
= __n
% __exponentiate_threshold
;
1396 __rest_buffer
= _Data_allocate(_S_rounded_up_size(__rest
));
1397 uninitialized_fill_n(__rest_buffer
, __rest
, __c
);
1398 _S_cond_store_eos(__rest_buffer
[__rest
]);
1400 __remainder
= _S_new_RopeLeaf(__rest_buffer
, __rest
, __a
);
1404 _RopeRep::__STL_FREE_STRING(__rest_buffer
, __rest
, __a
);
1405 __throw_exception_again
;
1408 __remainder_rope
._M_tree_ptr
= __remainder
;
1409 if (__exponent
!= 0) {
1410 _CharT
* __base_buffer
=
1411 _Data_allocate(_S_rounded_up_size(__exponentiate_threshold
));
1412 _RopeLeaf
* __base_leaf
;
1414 uninitialized_fill_n(__base_buffer
, __exponentiate_threshold
, __c
);
1415 _S_cond_store_eos(__base_buffer
[__exponentiate_threshold
]);
1417 __base_leaf
= _S_new_RopeLeaf(__base_buffer
,
1418 __exponentiate_threshold
, __a
);
1422 _RopeRep::__STL_FREE_STRING(__base_buffer
,
1423 __exponentiate_threshold
, __a
);
1424 __throw_exception_again
;
1426 __base_rope
._M_tree_ptr
= __base_leaf
;
1427 if (1 == __exponent
) {
1428 __result
= __base_rope
;
1430 __result
= power(__base_rope
, __exponent
,
1431 _Rope_Concat_fn
<_CharT
,_Alloc
>());
1433 if (0 != __remainder
) {
1434 __result
+= __remainder_rope
;
1437 __result
= __remainder_rope
;
1439 this->_M_tree_ptr
= __result
._M_tree_ptr
;
1440 this->_M_tree_ptr
->_M_ref_nonnil();
1443 template<class _CharT
, class _Alloc
>
1444 _CharT rope
<_CharT
,_Alloc
>::_S_empty_c_str
[1];
1446 template<class _CharT
, class _Alloc
>
1447 const _CharT
* rope
<_CharT
,_Alloc
>::c_str() const {
1448 if (0 == this->_M_tree_ptr
) {
1449 _S_empty_c_str
[0] = _S_eos((_CharT
*)0); // Possibly redundant,
1450 // but probably fast.
1451 return _S_empty_c_str
;
1453 __GC_CONST _CharT
* __old_c_string
= this->_M_tree_ptr
->_M_c_string
;
1454 if (0 != __old_c_string
) return(__old_c_string
);
1455 size_t __s
= size();
1456 _CharT
* __result
= _Data_allocate(__s
+ 1);
1457 _S_flatten(this->_M_tree_ptr
, __result
);
1458 __result
[__s
] = _S_eos((_CharT
*)0);
1460 _M_tree_ptr
->_M_c_string
= __result
;
1462 if ((__old_c_string
= (__GC_CONST _CharT
*)
1463 std::_Atomic_swap((unsigned long *)
1464 (&(this->_M_tree_ptr
->_M_c_string
)),
1465 (unsigned long)__result
)) != 0) {
1466 // It must have been added in the interim. Hence it had to have been
1467 // separately allocated. Deallocate the old copy, since we just
1469 _Destroy(__old_c_string
, __old_c_string
+ __s
+ 1);
1470 _Data_deallocate(__old_c_string
, __s
+ 1);
1476 template<class _CharT
, class _Alloc
>
1477 const _CharT
* rope
<_CharT
,_Alloc
>::replace_with_c_str() {
1478 if (0 == this->_M_tree_ptr
) {
1479 _S_empty_c_str
[0] = _S_eos((_CharT
*)0);
1480 return _S_empty_c_str
;
1482 __GC_CONST _CharT
* __old_c_string
= this->_M_tree_ptr
->_M_c_string
;
1483 if (_RopeRep::_S_leaf
== this->_M_tree_ptr
->_M_tag
1484 && 0 != __old_c_string
) {
1485 return(__old_c_string
);
1487 size_t __s
= size();
1488 _CharT
* __result
= _Data_allocate(_S_rounded_up_size(__s
));
1489 _S_flatten(this->_M_tree_ptr
, __result
);
1490 __result
[__s
] = _S_eos((_CharT
*)0);
1491 this->_M_tree_ptr
->_M_unref_nonnil();
1492 this->_M_tree_ptr
= _S_new_RopeLeaf(__result
, __s
, get_allocator());
1496 // Algorithm specializations. More should be added.
1498 template<class _Rope_iterator
> // was templated on CharT and Alloc
1499 void // VC++ workaround
1500 _Rope_rotate(_Rope_iterator __first
,
1501 _Rope_iterator __middle
,
1502 _Rope_iterator __last
)
1504 typedef typename
_Rope_iterator::value_type _CharT
;
1505 typedef typename
_Rope_iterator::_allocator_type _Alloc
;
1507 rope
<_CharT
,_Alloc
>& __r(__first
.container());
1508 rope
<_CharT
,_Alloc
> __prefix
= __r
.substr(0, __first
.index());
1509 rope
<_CharT
,_Alloc
> __suffix
=
1510 __r
.substr(__last
.index(), __r
.size() - __last
.index());
1511 rope
<_CharT
,_Alloc
> __part1
=
1512 __r
.substr(__middle
.index(), __last
.index() - __middle
.index());
1513 rope
<_CharT
,_Alloc
> __part2
=
1514 __r
.substr(__first
.index(), __middle
.index() - __first
.index());
1521 #if !defined(__GNUC__)
1522 // Appears to confuse g++
1523 inline void rotate(_Rope_iterator
<char,__STL_DEFAULT_ALLOCATOR(char)> __first
,
1524 _Rope_iterator
<char,__STL_DEFAULT_ALLOCATOR(char)> __middle
,
1525 _Rope_iterator
<char,__STL_DEFAULT_ALLOCATOR(char)> __last
) {
1526 _Rope_rotate(__first
, __middle
, __last
);
1531 // Probably not useful for several reasons:
1532 // - for SGIs 7.1 compiler and probably some others,
1533 // this forces lots of rope<wchar_t, ...> instantiations, creating a
1534 // code bloat and compile time problem. (Fixed in 7.2.)
1535 // - wchar_t is 4 bytes wide on most UNIX platforms, making it unattractive
1536 // for unicode strings. Unsigned short may be a better character
1539 _Rope_iterator
<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __first
,
1540 _Rope_iterator
<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __middle
,
1541 _Rope_iterator
<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __last
) {
1542 _Rope_rotate(__first
, __middle
, __last
);
1546 } // namespace __gnu_cxx