1 // SGI's rope class implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004 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
;
63 using std::uninitialized_fill_n
;
65 // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
66 // if necessary. Assumes _M_path_end[leaf_index] and leaf_pos are correct.
67 // Results in a valid buf_ptr if the iterator can be legitimately
69 template <class _CharT
, class _Alloc
>
71 _Rope_iterator_base
<_CharT
, _Alloc
>::
72 _S_setbuf(_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
)
80 case _Rope_constants::_S_leaf
:
81 __x
._M_buf_start
= ((_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 _Rope_constants::_S_function
:
86 case _Rope_constants::_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
= ((_Rope_RopeFunction
<_CharT
,
92 _Alloc
>*)__leaf
)->_M_fn
;
93 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
;
99 if (__buf_start_pos
+ __len
> __leaf_end
)
100 __len
= __leaf_end
- __buf_start_pos
;
101 (*__fn
)(__buf_start_pos
- __leaf_pos
, __len
, __x
._M_tmp_buf
);
102 __x
._M_buf_ptr
= __x
._M_tmp_buf
+ (__pos
- __buf_start_pos
);
103 __x
._M_buf_start
= __x
._M_tmp_buf
;
104 __x
._M_buf_end
= __x
._M_tmp_buf
+ __len
;
112 // Set path and buffer inside a rope iterator. We assume that
113 // pos and root are already set.
114 template <class _CharT
, class _Alloc
>
116 _Rope_iterator_base
<_CharT
, _Alloc
>::
117 _S_setcache(_Rope_iterator_base
<_CharT
, _Alloc
>& __x
)
119 const _RopeRep
* __path
[_Rope_constants::_S_max_rope_depth
+ 1];
120 const _RopeRep
* __curr_rope
;
121 int __curr_depth
= -1; /* index into path */
122 size_t __curr_start_pos
= 0;
123 size_t __pos
= __x
._M_current_pos
;
124 unsigned char __dirns
= 0; // Bit vector marking right turns in the path
126 if (__pos
>= __x
._M_root
->_M_size
)
131 __curr_rope
= __x
._M_root
;
132 if (0 != __curr_rope
->_M_c_string
)
134 /* Treat the root as a leaf. */
135 __x
._M_buf_start
= __curr_rope
->_M_c_string
;
136 __x
._M_buf_end
= __curr_rope
->_M_c_string
+ __curr_rope
->_M_size
;
137 __x
._M_buf_ptr
= __curr_rope
->_M_c_string
+ __pos
;
138 __x
._M_path_end
[0] = __curr_rope
;
139 __x
._M_leaf_index
= 0;
146 __path
[__curr_depth
] = __curr_rope
;
147 switch(__curr_rope
->_M_tag
)
149 case _Rope_constants::_S_leaf
:
150 case _Rope_constants::_S_function
:
151 case _Rope_constants::_S_substringfn
:
152 __x
._M_leaf_pos
= __curr_start_pos
;
154 case _Rope_constants::_S_concat
:
156 _Rope_RopeConcatenation
<_CharT
, _Alloc
>* __c
=
157 (_Rope_RopeConcatenation
<_CharT
, _Alloc
>*)__curr_rope
;
158 _RopeRep
* __left
= __c
->_M_left
;
159 size_t __left_len
= __left
->_M_size
;
162 if (__pos
>= __curr_start_pos
+ __left_len
)
165 __curr_rope
= __c
->_M_right
;
166 __curr_start_pos
+= __left_len
;
169 __curr_rope
= __left
;
175 // Copy last section of path into _M_path_end.
178 int __j
= __curr_depth
+ 1 - _S_path_cache_len
;
180 if (__j
< 0) __j
= 0;
181 while (__j
<= __curr_depth
)
182 __x
._M_path_end
[++__i
] = __path
[__j
++];
183 __x
._M_leaf_index
= __i
;
185 __x
._M_path_directions
= __dirns
;
189 // Specialized version of the above. Assumes that
190 // the path cache is valid for the previous position.
191 template <class _CharT
, class _Alloc
>
193 _Rope_iterator_base
<_CharT
, _Alloc
>::
194 _S_setcache_for_incr(_Rope_iterator_base
<_CharT
, _Alloc
>& __x
)
196 int __current_index
= __x
._M_leaf_index
;
197 const _RopeRep
* __current_node
= __x
._M_path_end
[__current_index
];
198 size_t __len
= __current_node
->_M_size
;
199 size_t __node_start_pos
= __x
._M_leaf_pos
;
200 unsigned char __dirns
= __x
._M_path_directions
;
201 _Rope_RopeConcatenation
<_CharT
, _Alloc
>* __c
;
203 if (__x
._M_current_pos
- __node_start_pos
< __len
)
205 /* More stuff in this leaf, we just didn't cache it. */
209 // node_start_pos is starting position of last_node.
210 while (--__current_index
>= 0)
212 if (!(__dirns
& 1) /* Path turned left */)
214 __current_node
= __x
._M_path_end
[__current_index
];
215 __c
= (_Rope_RopeConcatenation
<_CharT
, _Alloc
>*)__current_node
;
216 // Otherwise we were in the right child. Thus we should pop
217 // the concatenation node.
218 __node_start_pos
-= __c
->_M_left
->_M_size
;
221 if (__current_index
< 0)
223 // We underflowed the cache. Punt.
227 __current_node
= __x
._M_path_end
[__current_index
];
228 __c
= (_Rope_RopeConcatenation
<_CharT
, _Alloc
>*)__current_node
;
229 // current_node is a concatenation node. We are positioned on the first
230 // character in its right child.
231 // node_start_pos is starting position of current_node.
232 __node_start_pos
+= __c
->_M_left
->_M_size
;
233 __current_node
= __c
->_M_right
;
234 __x
._M_path_end
[++__current_index
] = __current_node
;
236 while (_Rope_constants::_S_concat
== __current_node
->_M_tag
)
239 if (_S_path_cache_len
== __current_index
)
242 for (__i
= 0; __i
< _S_path_cache_len
-1; __i
++)
243 __x
._M_path_end
[__i
] = __x
._M_path_end
[__i
+1];
247 ((_Rope_RopeConcatenation
<_CharT
, _Alloc
>*)__current_node
)->_M_left
;
248 __x
._M_path_end
[__current_index
] = __current_node
;
250 // node_start_pos is unchanged.
252 __x
._M_leaf_index
= __current_index
;
253 __x
._M_leaf_pos
= __node_start_pos
;
254 __x
._M_path_directions
= __dirns
;
258 template <class _CharT
, class _Alloc
>
260 _Rope_iterator_base
<_CharT
, _Alloc
>::
263 _M_current_pos
+= __n
;
266 size_t __chars_left
= _M_buf_end
- _M_buf_ptr
;
267 if (__chars_left
> __n
)
269 else if (__chars_left
== __n
)
272 _S_setcache_for_incr(*this);
279 template <class _CharT
, class _Alloc
>
281 _Rope_iterator_base
<_CharT
, _Alloc
>::
286 size_t __chars_left
= _M_buf_ptr
- _M_buf_start
;
287 if (__chars_left
>= __n
)
292 _M_current_pos
-= __n
;
295 template <class _CharT
, class _Alloc
>
297 _Rope_iterator
<_CharT
, _Alloc
>::
300 if (_M_root_rope
->_M_tree_ptr
!= this->_M_root
)
302 // _Rope was modified. Get things fixed up.
303 _RopeRep::_S_unref(this->_M_root
);
304 this->_M_root
= _M_root_rope
->_M_tree_ptr
;
305 _RopeRep::_S_ref(this->_M_root
);
306 this->_M_buf_ptr
= 0;
310 template <class _CharT
, class _Alloc
>
312 _Rope_const_iterator
<_CharT
, _Alloc
>::
313 _Rope_const_iterator(const _Rope_iterator
<_CharT
, _Alloc
>& __x
)
314 : _Rope_iterator_base
<_CharT
, _Alloc
>(__x
)
317 template <class _CharT
, class _Alloc
>
319 _Rope_iterator
<_CharT
, _Alloc
>::
320 _Rope_iterator(rope
<_CharT
, _Alloc
>& __r
, size_t __pos
)
321 : _Rope_iterator_base
<_CharT
,_Alloc
>(__r
._M_tree_ptr
, __pos
),
323 { _RopeRep::_S_ref(this->_M_root
); }
325 template <class _CharT
, class _Alloc
>
327 rope
<_CharT
, _Alloc
>::
328 _S_char_ptr_len(const _CharT
* __s
)
330 const _CharT
* __p
= __s
;
332 while (!_S_is0(*__p
))
340 template <class _CharT
, class _Alloc
>
342 _Rope_RopeRep
<_CharT
, _Alloc
>::
345 _CharT
* __cstr
= _M_c_string
;
348 size_t __size
= this->_M_size
+ 1;
349 _Destroy(__cstr
, __cstr
+ __size
, get_allocator());
350 this->_Data_deallocate(__cstr
, __size
);
354 template <class _CharT
, class _Alloc
>
356 _Rope_RopeRep
<_CharT
, _Alloc
>::
357 _S_free_string(_CharT
* __s
, size_t __n
, allocator_type __a
)
359 if (!_S_is_basic_char_type((_CharT
*)0))
360 _Destroy(__s
, __s
+ __n
, __a
);
362 // This has to be a static member, so this gets a bit messy
364 _Rope_RopeLeaf
<_CharT
, _Alloc
>::_S_rounded_up_size(__n
));
367 // There are several reasons for not doing this with virtual destructors
368 // and a class specific delete operator:
369 // - A class specific delete operator can't easily get access to
370 // allocator instances if we need them.
371 // - Any virtual function would need a 4 or byte vtable pointer;
372 // this only requires a one byte tag per object.
373 template <class _CharT
, class _Alloc
>
375 _Rope_RopeRep
<_CharT
, _Alloc
>::
380 case _Rope_constants::_S_leaf
:
382 _Rope_RopeLeaf
<_CharT
, _Alloc
>* __l
383 = (_Rope_RopeLeaf
<_CharT
, _Alloc
>*)this;
384 __l
->_Rope_RopeLeaf
<_CharT
, _Alloc
>::~_Rope_RopeLeaf();
385 _L_deallocate(__l
, 1);
388 case _Rope_constants::_S_concat
:
390 _Rope_RopeConcatenation
<_CharT
,_Alloc
>* __c
391 = (_Rope_RopeConcatenation
<_CharT
, _Alloc
>*)this;
392 __c
->_Rope_RopeConcatenation
<_CharT
, _Alloc
>::
393 ~_Rope_RopeConcatenation();
394 _C_deallocate(__c
, 1);
397 case _Rope_constants::_S_function
:
399 _Rope_RopeFunction
<_CharT
, _Alloc
>* __f
400 = (_Rope_RopeFunction
<_CharT
, _Alloc
>*)this;
401 __f
->_Rope_RopeFunction
<_CharT
, _Alloc
>::~_Rope_RopeFunction();
402 _F_deallocate(__f
, 1);
405 case _Rope_constants::_S_substringfn
:
407 _Rope_RopeSubstring
<_CharT
, _Alloc
>* __ss
=
408 (_Rope_RopeSubstring
<_CharT
, _Alloc
>*)this;
409 __ss
->_Rope_RopeSubstring
<_CharT
, _Alloc
>::
410 ~_Rope_RopeSubstring();
411 _S_deallocate(__ss
, 1);
418 template <class _CharT
, class _Alloc
>
420 _Rope_RopeRep
<_CharT
, _Alloc
>::
421 _S_free_string(const _CharT
*, size_t, allocator_type
)
426 // Concatenate a C string onto a leaf rope by copying the rope data.
427 // Used for short ropes.
428 template <class _CharT
, class _Alloc
>
429 typename rope
<_CharT
, _Alloc
>::_RopeLeaf
*
430 rope
<_CharT
, _Alloc
>::
431 _S_leaf_concat_char_iter(_RopeLeaf
* __r
, const _CharT
* __iter
, size_t __len
)
433 size_t __old_len
= __r
->_M_size
;
434 _CharT
* __new_data
= (_CharT
*)
435 _Data_allocate(_S_rounded_up_size(__old_len
+ __len
));
438 uninitialized_copy_n(__r
->_M_data
, __old_len
, __new_data
);
439 uninitialized_copy_n(__iter
, __len
, __new_data
+ __old_len
);
440 _S_cond_store_eos(__new_data
[__old_len
+ __len
]);
443 __result
= _S_new_RopeLeaf(__new_data
, __old_len
+ __len
,
444 __r
->get_allocator());
448 _RopeRep::__STL_FREE_STRING(__new_data
, __old_len
+ __len
,
449 __r
->get_allocator());
450 __throw_exception_again
;
456 // As above, but it's OK to clobber original if refcount is 1
457 template <class _CharT
, class _Alloc
>
458 typename rope
<_CharT
,_Alloc
>::_RopeLeaf
*
459 rope
<_CharT
, _Alloc
>::
460 _S_destr_leaf_concat_char_iter(_RopeLeaf
* __r
, const _CharT
* __iter
,
463 if (__r
->_M_ref_count
> 1)
464 return _S_leaf_concat_char_iter(__r
, __iter
, __len
);
465 size_t __old_len
= __r
->_M_size
;
466 if (_S_allocated_capacity(__old_len
) >= __old_len
+ __len
)
468 // The space has been partially initialized for the standard
469 // character types. But that doesn't matter for those types.
470 uninitialized_copy_n(__iter
, __len
, __r
->_M_data
+ __old_len
);
471 if (_S_is_basic_char_type((_CharT
*)0))
472 _S_cond_store_eos(__r
->_M_data
[__old_len
+ __len
]);
473 else if (__r
->_M_c_string
!= __r
->_M_data
&& 0 != __r
->_M_c_string
)
475 __r
->_M_free_c_string();
476 __r
->_M_c_string
= 0;
478 __r
->_M_size
= __old_len
+ __len
;
479 __r
->_M_ref_count
= 2;
484 _RopeLeaf
* __result
= _S_leaf_concat_char_iter(__r
, __iter
, __len
);
490 // Assumes left and right are not 0.
491 // Does not increment (nor decrement on exception) child reference counts.
492 // Result has ref count 1.
493 template <class _CharT
, class _Alloc
>
494 typename rope
<_CharT
, _Alloc
>::_RopeRep
*
495 rope
<_CharT
, _Alloc
>::
496 _S_tree_concat(_RopeRep
* __left
, _RopeRep
* __right
)
498 _RopeConcatenation
* __result
= _S_new_RopeConcatenation(__left
, __right
,
501 size_t __depth
= __result
->_M_depth
;
503 if (__depth
> 20 && (__result
->_M_size
< 1000
504 || __depth
> _Rope_constants::_S_max_rope_depth
))
506 _RopeRep
* __balanced
;
510 __balanced
= _S_balance(__result
);
511 __result
->_M_unref_nonnil();
515 _C_deallocate(__result
,1);
516 __throw_exception_again
;
518 // In case of exception, we need to deallocate
519 // otherwise dangling result node. But caller
520 // still owns its children. Thus unref is
528 template <class _CharT
, class _Alloc
>
529 typename rope
<_CharT
, _Alloc
>::_RopeRep
*
530 rope
<_CharT
, _Alloc
>::
531 _S_concat_char_iter(_RopeRep
* __r
, const _CharT
*__s
, size_t __slen
)
540 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __slen
,
541 __r
->get_allocator());
542 if (_Rope_constants::_S_leaf
== __r
->_M_tag
543 && __r
->_M_size
+ __slen
<= _S_copy_max
)
545 __result
= _S_leaf_concat_char_iter((_RopeLeaf
*)__r
, __s
, __slen
);
548 if (_Rope_constants::_S_concat
== __r
->_M_tag
549 && _Rope_constants::_S_leaf
== ((_RopeConcatenation
*)
550 __r
)->_M_right
->_M_tag
)
553 (_RopeLeaf
* )(((_RopeConcatenation
* )__r
)->_M_right
);
554 if (__right
->_M_size
+ __slen
<= _S_copy_max
)
556 _RopeRep
* __left
= ((_RopeConcatenation
*)__r
)->_M_left
;
558 _S_leaf_concat_char_iter((_RopeLeaf
*)__right
, __s
, __slen
);
559 __left
->_M_ref_nonnil();
561 { __result
= _S_tree_concat(__left
, __nright
); }
566 __throw_exception_again
;
572 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __slen
, __r
->get_allocator());
575 __r
->_M_ref_nonnil();
576 __result
= _S_tree_concat(__r
, __nright
);
582 __throw_exception_again
;
588 template <class _CharT
, class _Alloc
>
589 typename rope
<_CharT
,_Alloc
>::_RopeRep
*
590 rope
<_CharT
,_Alloc
>::
591 _S_destr_concat_char_iter(_RopeRep
* __r
, const _CharT
* __s
, size_t __slen
)
595 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __slen
,
596 __r
->get_allocator());
597 size_t __count
= __r
->_M_ref_count
;
598 size_t __orig_size
= __r
->_M_size
;
600 return _S_concat_char_iter(__r
, __s
, __slen
);
603 __r
->_M_ref_count
= 2; // One more than before
606 if (__orig_size
+ __slen
<= _S_copy_max
607 && _Rope_constants::_S_leaf
== __r
->_M_tag
)
609 __result
= _S_destr_leaf_concat_char_iter((_RopeLeaf
*)__r
, __s
,
613 if (_Rope_constants::_S_concat
== __r
->_M_tag
)
615 _RopeLeaf
* __right
= (_RopeLeaf
*)(((_RopeConcatenation
*)
617 if (_Rope_constants::_S_leaf
== __right
->_M_tag
618 && __right
->_M_size
+ __slen
<= _S_copy_max
)
620 _RopeRep
* __new_right
=
621 _S_destr_leaf_concat_char_iter(__right
, __s
, __slen
);
622 if (__right
== __new_right
)
623 __new_right
->_M_ref_count
= 1;
625 __right
->_M_unref_nonnil();
626 __r
->_M_ref_count
= 2; // One more than before.
627 ((_RopeConcatenation
*)__r
)->_M_right
= __new_right
;
628 __r
->_M_size
= __orig_size
+ __slen
;
629 if (0 != __r
->_M_c_string
)
631 __r
->_M_free_c_string();
632 __r
->_M_c_string
= 0;
638 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __slen
, __r
->get_allocator());
639 __r
->_M_ref_nonnil();
641 { __result
= _S_tree_concat(__r
, __right
); }
646 __throw_exception_again
;
652 template <class _CharT
, class _Alloc
>
653 typename rope
<_CharT
, _Alloc
>::_RopeRep
*
654 rope
<_CharT
, _Alloc
>::
655 _S_concat(_RopeRep
* __left
, _RopeRep
* __right
)
664 __left
->_M_ref_nonnil();
667 if (_Rope_constants::_S_leaf
== __right
->_M_tag
)
669 if (_Rope_constants::_S_leaf
== __left
->_M_tag
)
671 if (__right
->_M_size
+ __left
->_M_size
<= _S_copy_max
)
672 return _S_leaf_concat_char_iter((_RopeLeaf
*)__left
,
673 ((_RopeLeaf
*)__right
)->_M_data
,
676 else if (_Rope_constants::_S_concat
== __left
->_M_tag
677 && _Rope_constants::_S_leaf
== ((_RopeConcatenation
*)
678 __left
)->_M_right
->_M_tag
)
680 _RopeLeaf
* __leftright
=
681 (_RopeLeaf
*)(((_RopeConcatenation
*)__left
)->_M_right
);
682 if (__leftright
->_M_size
+ __right
->_M_size
<= _S_copy_max
)
684 _RopeRep
* __leftleft
= ((_RopeConcatenation
*)__left
)->_M_left
;
685 _RopeRep
* __rest
= _S_leaf_concat_char_iter(__leftright
,
690 __leftleft
->_M_ref_nonnil();
692 { return(_S_tree_concat(__leftleft
, __rest
)); }
695 _S_unref(__leftleft
);
697 __throw_exception_again
;
702 __left
->_M_ref_nonnil();
703 __right
->_M_ref_nonnil();
705 { return(_S_tree_concat(__left
, __right
)); }
710 __throw_exception_again
;
714 template <class _CharT
, class _Alloc
>
715 typename rope
<_CharT
, _Alloc
>::_RopeRep
*
716 rope
<_CharT
, _Alloc
>::
717 _S_substring(_RopeRep
* __base
, size_t __start
, size_t __endp1
)
721 size_t __len
= __base
->_M_size
;
723 const size_t __lazy_threshold
= 128;
725 if (__endp1
>= __len
)
729 __base
->_M_ref_nonnil();
737 __adj_endp1
= __endp1
;
739 switch(__base
->_M_tag
)
741 case _Rope_constants::_S_concat
:
743 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__base
;
744 _RopeRep
* __left
= __c
->_M_left
;
745 _RopeRep
* __right
= __c
->_M_right
;
746 size_t __left_len
= __left
->_M_size
;
749 if (__adj_endp1
<= __left_len
)
750 return _S_substring(__left
, __start
, __endp1
);
751 else if (__start
>= __left_len
)
752 return _S_substring(__right
, __start
- __left_len
,
753 __adj_endp1
- __left_len
);
754 _Self_destruct_ptr
__left_result(_S_substring(__left
,
757 _Self_destruct_ptr
__right_result(_S_substring(__right
, 0,
760 __result
= _S_concat(__left_result
, __right_result
);
763 case _Rope_constants::_S_leaf
:
765 _RopeLeaf
* __l
= (_RopeLeaf
*)__base
;
768 if (__start
>= __adj_endp1
)
770 __result_len
= __adj_endp1
- __start
;
771 if (__result_len
> __lazy_threshold
)
774 const _CharT
* __section
= __l
->_M_data
+ __start
;
775 __result
= _S_new_RopeLeaf(__section
, __result_len
,
776 __base
->get_allocator());
777 __result
->_M_c_string
= 0; // Not eos terminated.
779 // We should sometimes create substring node instead.
780 __result
= __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__l
->_M_data
+ __start
,
787 case _Rope_constants::_S_substringfn
:
788 // Avoid introducing multiple layers of substring nodes.
790 _RopeSubstring
* __old
= (_RopeSubstring
*)__base
;
792 if (__start
>= __adj_endp1
)
794 __result_len
= __adj_endp1
- __start
;
795 if (__result_len
> __lazy_threshold
)
797 _RopeSubstring
* __result
=
798 _S_new_RopeSubstring(__old
->_M_base
,
799 __start
+ __old
->_M_start
,
800 __adj_endp1
- __start
,
801 __base
->get_allocator());
804 } // *** else fall through: ***
806 case _Rope_constants::_S_function
:
808 _RopeFunction
* __f
= (_RopeFunction
*)__base
;
811 if (__start
>= __adj_endp1
)
813 __result_len
= __adj_endp1
- __start
;
815 if (__result_len
> __lazy_threshold
)
817 __section
= (_CharT
*)
818 _Data_allocate(_S_rounded_up_size(__result_len
));
820 { (*(__f
->_M_fn
))(__start
, __result_len
, __section
); }
823 _RopeRep::__STL_FREE_STRING(__section
, __result_len
,
824 __base
->get_allocator());
825 __throw_exception_again
;
827 _S_cond_store_eos(__section
[__result_len
]);
828 return _S_new_RopeLeaf(__section
, __result_len
,
829 __base
->get_allocator());
834 // Create substring node.
835 return _S_new_RopeSubstring(__base
, __start
, __adj_endp1
- __start
,
836 __base
->get_allocator());
840 template<class _CharT
>
841 class _Rope_flatten_char_consumer
842 : public _Rope_char_consumer
<_CharT
>
848 _Rope_flatten_char_consumer(_CharT
* __buffer
)
849 { _M_buf_ptr
= __buffer
; };
851 ~_Rope_flatten_char_consumer() {}
854 operator()(const _CharT
* __leaf
, size_t __n
)
856 uninitialized_copy_n(__leaf
, __n
, _M_buf_ptr
);
862 template<class _CharT
>
863 class _Rope_find_char_char_consumer
864 : public _Rope_char_consumer
<_CharT
>
869 size_t _M_count
; // Number of nonmatching characters
871 _Rope_find_char_char_consumer(_CharT __p
)
872 : _M_pattern(__p
), _M_count(0) {}
874 ~_Rope_find_char_char_consumer() {}
877 operator()(const _CharT
* __leaf
, size_t __n
)
880 for (__i
= 0; __i
< __n
; __i
++)
882 if (__leaf
[__i
] == _M_pattern
)
888 _M_count
+= __n
; return true;
892 template<class _CharT
, class _Traits
>
893 // Here _CharT is both the stream and rope character type.
894 class _Rope_insert_char_consumer
895 : public _Rope_char_consumer
<_CharT
>
898 typedef basic_ostream
<_CharT
,_Traits
> _Insert_ostream
;
899 _Insert_ostream
& _M_o
;
901 _Rope_insert_char_consumer(_Insert_ostream
& __writer
)
903 ~_Rope_insert_char_consumer() { };
904 // Caller is presumed to own the ostream
905 bool operator() (const _CharT
* __leaf
, size_t __n
);
906 // Returns true to continue traversal.
909 template<class _CharT
, class _Traits
>
911 _Rope_insert_char_consumer
<_CharT
, _Traits
>::
912 operator()(const _CharT
* __leaf
, size_t __n
)
915 // We assume that formatting is set up correctly for each element.
916 for (__i
= 0; __i
< __n
; __i
++)
917 _M_o
.put(__leaf
[__i
]);
921 template <class _CharT
, class _Alloc
>
923 rope
<_CharT
, _Alloc
>::
924 _S_apply_to_pieces(_Rope_char_consumer
<_CharT
>& __c
,
925 const _RopeRep
* __r
, size_t __begin
, size_t __end
)
931 case _Rope_constants::_S_concat
:
933 _RopeConcatenation
* __conc
= (_RopeConcatenation
*)__r
;
934 _RopeRep
* __left
= __conc
->_M_left
;
935 size_t __left_len
= __left
->_M_size
;
936 if (__begin
< __left_len
)
938 size_t __left_end
= std::min(__left_len
, __end
);
939 if (!_S_apply_to_pieces(__c
, __left
, __begin
, __left_end
))
942 if (__end
> __left_len
)
944 _RopeRep
* __right
= __conc
->_M_right
;
945 size_t __right_start
= std::max(__left_len
, __begin
);
946 if (!_S_apply_to_pieces(__c
, __right
,
947 __right_start
- __left_len
,
953 case _Rope_constants::_S_leaf
:
955 _RopeLeaf
* __l
= (_RopeLeaf
*)__r
;
956 return __c(__l
->_M_data
+ __begin
, __end
- __begin
);
958 case _Rope_constants::_S_function
:
959 case _Rope_constants::_S_substringfn
:
961 _RopeFunction
* __f
= (_RopeFunction
*)__r
;
962 size_t __len
= __end
- __begin
;
965 (_CharT
*)_Alloc().allocate(__len
* sizeof(_CharT
));
968 (*(__f
->_M_fn
))(__begin
, __len
, __buffer
);
969 __result
= __c(__buffer
, __len
);
970 _Alloc().deallocate(__buffer
, __len
* sizeof(_CharT
));
974 _Alloc().deallocate(__buffer
, __len
* sizeof(_CharT
));
975 __throw_exception_again
;
984 template<class _CharT
, class _Traits
>
986 _Rope_fill(basic_ostream
<_CharT
, _Traits
>& __o
, size_t __n
)
988 char __f
= __o
.fill();
991 for (__i
= 0; __i
< __n
; __i
++)
996 template <class _CharT
>
998 _Rope_is_simple(_CharT
*)
1002 _Rope_is_simple(char*)
1006 _Rope_is_simple(wchar_t*)
1009 template<class _CharT
, class _Traits
, class _Alloc
>
1010 basic_ostream
<_CharT
, _Traits
>&
1011 operator<<(basic_ostream
<_CharT
, _Traits
>& __o
,
1012 const rope
<_CharT
, _Alloc
>& __r
)
1014 size_t __w
= __o
.width();
1015 bool __left
= bool(__o
.flags() & std::ios::left
);
1017 size_t __rope_len
= __r
.size();
1018 _Rope_insert_char_consumer
<_CharT
, _Traits
> __c(__o
);
1019 bool __is_simple
= _Rope_is_simple((_CharT
*)0);
1021 if (__rope_len
< __w
)
1022 __pad_len
= __w
- __rope_len
;
1027 __o
.width(__w
/ __rope_len
);
1030 if (__is_simple
&& !__left
&& __pad_len
> 0)
1031 _Rope_fill(__o
, __pad_len
);
1032 __r
.apply_to_pieces(0, __r
.size(), __c
);
1033 if (__is_simple
&& __left
&& __pad_len
> 0)
1034 _Rope_fill(__o
, __pad_len
);
1042 __throw_exception_again
;
1047 template <class _CharT
, class _Alloc
>
1049 rope
<_CharT
, _Alloc
>::
1050 _S_flatten(_RopeRep
* __r
, size_t __start
, size_t __len
,
1053 _Rope_flatten_char_consumer
<_CharT
> __c(__buffer
);
1054 _S_apply_to_pieces(__c
, __r
, __start
, __start
+ __len
);
1055 return(__buffer
+ __len
);
1058 template <class _CharT
, class _Alloc
>
1060 rope
<_CharT
, _Alloc
>::
1061 find(_CharT __pattern
, size_t __start
) const
1063 _Rope_find_char_char_consumer
<_CharT
> __c(__pattern
);
1064 _S_apply_to_pieces(__c
, this->_M_tree_ptr
, __start
, size());
1065 size_type __result_pos
= __start
+ __c
._M_count
;
1066 #ifndef __STL_OLD_ROPE_SEMANTICS
1067 if (__result_pos
== size())
1068 __result_pos
= npos
;
1070 return __result_pos
;
1073 template <class _CharT
, class _Alloc
>
1075 rope
<_CharT
, _Alloc
>::
1076 _S_flatten(_RopeRep
* __r
, _CharT
* __buffer
)
1082 case _Rope_constants::_S_concat
:
1084 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1085 _RopeRep
* __left
= __c
->_M_left
;
1086 _RopeRep
* __right
= __c
->_M_right
;
1087 _CharT
* __rest
= _S_flatten(__left
, __buffer
);
1088 return _S_flatten(__right
, __rest
);
1090 case _Rope_constants::_S_leaf
:
1092 _RopeLeaf
* __l
= (_RopeLeaf
*)__r
;
1093 return copy_n(__l
->_M_data
, __l
->_M_size
, __buffer
).second
;
1095 case _Rope_constants::_S_function
:
1096 case _Rope_constants::_S_substringfn
:
1097 // We don't yet do anything with substring nodes.
1098 // This needs to be fixed before ropefiles will work well.
1100 _RopeFunction
* __f
= (_RopeFunction
*)__r
;
1101 (*(__f
->_M_fn
))(0, __f
->_M_size
, __buffer
);
1102 return __buffer
+ __f
->_M_size
;
1109 // This needs work for _CharT != char
1110 template <class _CharT
, class _Alloc
>
1112 rope
<_CharT
, _Alloc
>::
1113 _S_dump(_RopeRep
* __r
, int __indent
)
1115 for (int __i
= 0; __i
< __indent
; __i
++)
1122 if (_Rope_constants::_S_concat
== __r
->_M_tag
)
1124 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1125 _RopeRep
* __left
= __c
->_M_left
;
1126 _RopeRep
* __right
= __c
->_M_right
;
1129 printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
1130 __r
, __r
->_M_depth
, __r
->_M_size
,
1131 __r
->_M_is_balanced
? "" : "not");
1133 printf("Concatenation %p (rc = %ld, depth = %d, "
1134 "len = %ld, %s balanced)\n",
1135 __r
, __r
->_M_ref_count
, __r
->_M_depth
, __r
->_M_size
,
1136 __r
->_M_is_balanced
? "" : "not");
1138 _S_dump(__left
, __indent
+ 2);
1139 _S_dump(__right
, __indent
+ 2);
1146 switch (__r
->_M_tag
)
1148 case _Rope_constants::_S_leaf
:
1151 case _Rope_constants::_S_function
:
1152 __kind
= "Function";
1154 case _Rope_constants::_S_substringfn
:
1155 __kind
= "Function representing substring";
1158 __kind
= "(corrupted kind field!)";
1161 printf("%s %p (depth = %d, len = %ld) ",
1162 __kind
, __r
, __r
->_M_depth
, __r
->_M_size
);
1164 printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
1165 __kind
, __r
, __r
->_M_ref_count
, __r
->_M_depth
, __r
->_M_size
);
1167 if (_S_is_one_byte_char_type((_CharT
*)0))
1169 const int __max_len
= 40;
1170 _Self_destruct_ptr
__prefix(_S_substring(__r
, 0, __max_len
));
1171 _CharT __buffer
[__max_len
+ 1];
1172 bool __too_big
= __r
->_M_size
> __prefix
->_M_size
;
1174 _S_flatten(__prefix
, __buffer
);
1175 __buffer
[__prefix
->_M_size
] = _S_eos((_CharT
*)0);
1176 printf("%s%s\n", (char*)__buffer
,
1177 __too_big
? "...\n" : "\n");
1184 template <class _CharT
, class _Alloc
>
1186 rope
<_CharT
, _Alloc
>::
1187 _S_min_len
[_Rope_constants::_S_max_rope_depth
+ 1] = {
1188 /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21,
1189 /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377,
1190 /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181,
1191 /* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368,
1192 /* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811,
1193 /* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309,
1194 /* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352,
1195 /* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155,
1196 /* 39 */165580141, /* 40 */267914296, /* 41 */433494437,
1197 /* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903,
1198 /* 45 */2971215073u };
1199 // These are Fibonacci numbers < 2**32.
1201 template <class _CharT
, class _Alloc
>
1202 typename rope
<_CharT
, _Alloc
>::_RopeRep
*
1203 rope
<_CharT
, _Alloc
>::
1204 _S_balance(_RopeRep
* __r
)
1206 _RopeRep
* __forest
[_Rope_constants::_S_max_rope_depth
+ 1];
1207 _RopeRep
* __result
= 0;
1210 // The concatenation of forest in descending order is equal to __r.
1211 // __forest[__i]._M_size >= _S_min_len[__i]
1212 // __forest[__i]._M_depth = __i
1213 // References from forest are included in refcount.
1215 for (__i
= 0; __i
<= _Rope_constants::_S_max_rope_depth
; ++__i
)
1219 _S_add_to_forest(__r
, __forest
);
1220 for (__i
= 0; __i
<= _Rope_constants::_S_max_rope_depth
; ++__i
)
1221 if (0 != __forest
[__i
])
1224 _Self_destruct_ptr
__old(__result
);
1226 __result
= _S_concat(__forest
[__i
], __result
);
1227 __forest
[__i
]->_M_unref_nonnil();
1228 #if !defined(__GC) && defined(__EXCEPTIONS)
1235 for(__i
= 0; __i
<= _Rope_constants::_S_max_rope_depth
; __i
++)
1236 _S_unref(__forest
[__i
]);
1237 __throw_exception_again
;
1240 if (__result
->_M_depth
> _Rope_constants::_S_max_rope_depth
)
1241 __throw_length_error(__N("rope::_S_balance"));
1245 template <class _CharT
, class _Alloc
>
1247 rope
<_CharT
, _Alloc
>::
1248 _S_add_to_forest(_RopeRep
* __r
, _RopeRep
** __forest
)
1250 if (__r
->_M_is_balanced
)
1252 _S_add_leaf_to_forest(__r
, __forest
);
1257 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1259 _S_add_to_forest(__c
->_M_left
, __forest
);
1260 _S_add_to_forest(__c
->_M_right
, __forest
);
1265 template <class _CharT
, class _Alloc
>
1267 rope
<_CharT
, _Alloc
>::
1268 _S_add_leaf_to_forest(_RopeRep
* __r
, _RopeRep
** __forest
)
1270 _RopeRep
* __insertee
; // included in refcount
1271 _RopeRep
* __too_tiny
= 0; // included in refcount
1272 int __i
; // forest[0..__i-1] is empty
1273 size_t __s
= __r
->_M_size
;
1275 for (__i
= 0; __s
>= _S_min_len
[__i
+1]/* not this bucket */; ++__i
)
1277 if (0 != __forest
[__i
])
1280 _Self_destruct_ptr
__old(__too_tiny
);
1282 __too_tiny
= _S_concat_and_set_balanced(__forest
[__i
],
1284 __forest
[__i
]->_M_unref_nonnil();
1290 _Self_destruct_ptr
__old(__too_tiny
);
1292 __insertee
= _S_concat_and_set_balanced(__too_tiny
, __r
);
1294 // Too_tiny dead, and no longer included in refcount.
1295 // Insertee is live and included.
1298 if (0 != __forest
[__i
])
1301 _Self_destruct_ptr
__old(__insertee
);
1303 __insertee
= _S_concat_and_set_balanced(__forest
[__i
],
1305 __forest
[__i
]->_M_unref_nonnil();
1308 if (__i
== _Rope_constants::_S_max_rope_depth
1309 || __insertee
->_M_size
< _S_min_len
[__i
+1])
1311 __forest
[__i
] = __insertee
;
1312 // refcount is OK since __insertee is now dead.
1318 template <class _CharT
, class _Alloc
>
1320 rope
<_CharT
, _Alloc
>::
1321 _S_fetch(_RopeRep
* __r
, size_type __i
)
1323 __GC_CONST _CharT
* __cstr
= __r
->_M_c_string
;
1331 case _Rope_constants::_S_concat
:
1333 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1334 _RopeRep
* __left
= __c
->_M_left
;
1335 size_t __left_len
= __left
->_M_size
;
1337 if (__i
>= __left_len
)
1340 __r
= __c
->_M_right
;
1346 case _Rope_constants::_S_leaf
:
1348 _RopeLeaf
* __l
= (_RopeLeaf
*)__r
;
1349 return __l
->_M_data
[__i
];
1351 case _Rope_constants::_S_function
:
1352 case _Rope_constants::_S_substringfn
:
1354 _RopeFunction
* __f
= (_RopeFunction
*)__r
;
1357 (*(__f
->_M_fn
))(__i
, 1, &__result
);
1365 // Return a uniquely referenced character slot for the given
1366 // position, or 0 if that's not possible.
1367 template <class _CharT
, class _Alloc
>
1369 rope
<_CharT
, _Alloc
>::
1370 _S_fetch_ptr(_RopeRep
* __r
, size_type __i
)
1372 _RopeRep
* __clrstack
[_Rope_constants::_S_max_rope_depth
];
1377 if (__r
->_M_ref_count
> 1)
1381 case _Rope_constants::_S_concat
:
1383 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1384 _RopeRep
* __left
= __c
->_M_left
;
1385 size_t __left_len
= __left
->_M_size
;
1387 if (__c
->_M_c_string
!= 0)
1388 __clrstack
[__csptr
++] = __c
;
1389 if (__i
>= __left_len
)
1392 __r
= __c
->_M_right
;
1398 case _Rope_constants::_S_leaf
:
1400 _RopeLeaf
* __l
= (_RopeLeaf
*)__r
;
1401 if (__l
->_M_c_string
!= __l
->_M_data
&& __l
->_M_c_string
!= 0)
1402 __clrstack
[__csptr
++] = __l
;
1406 _RopeRep
* __d
= __clrstack
[__csptr
];
1407 __d
->_M_free_c_string();
1408 __d
->_M_c_string
= 0;
1410 return __l
->_M_data
+ __i
;
1412 case _Rope_constants::_S_function
:
1413 case _Rope_constants::_S_substringfn
:
1420 // The following could be implemented trivially using
1421 // lexicographical_compare_3way.
1422 // We do a little more work to avoid dealing with rope iterators for
1424 template <class _CharT
, class _Alloc
>
1426 rope
<_CharT
, _Alloc
>::
1427 _S_compare (const _RopeRep
* __left
, const _RopeRep
* __right
)
1436 __left_len
= __left
->_M_size
;
1437 __right_len
= __right
->_M_size
;
1438 if (_Rope_constants::_S_leaf
== __left
->_M_tag
)
1440 _RopeLeaf
* __l
= (_RopeLeaf
*) __left
;
1441 if (_Rope_constants::_S_leaf
== __right
->_M_tag
)
1443 _RopeLeaf
* __r
= (_RopeLeaf
*) __right
;
1444 return lexicographical_compare_3way(__l
->_M_data
,
1445 __l
->_M_data
+ __left_len
,
1446 __r
->_M_data
, __r
->_M_data
1451 const_iterator
__rstart(__right
, 0);
1452 const_iterator
__rend(__right
, __right_len
);
1453 return lexicographical_compare_3way(__l
->_M_data
, __l
->_M_data
1460 const_iterator
__lstart(__left
, 0);
1461 const_iterator
__lend(__left
, __left_len
);
1462 if (_Rope_constants::_S_leaf
== __right
->_M_tag
)
1464 _RopeLeaf
* __r
= (_RopeLeaf
*) __right
;
1465 return lexicographical_compare_3way(__lstart
, __lend
,
1466 __r
->_M_data
, __r
->_M_data
1471 const_iterator
__rstart(__right
, 0);
1472 const_iterator
__rend(__right
, __right_len
);
1473 return lexicographical_compare_3way(__lstart
, __lend
,
1479 // Assignment to reference proxies.
1480 template <class _CharT
, class _Alloc
>
1481 _Rope_char_ref_proxy
<_CharT
, _Alloc
>&
1482 _Rope_char_ref_proxy
<_CharT
, _Alloc
>::
1483 operator=(_CharT __c
)
1485 _RopeRep
* __old
= _M_root
->_M_tree_ptr
;
1487 // First check for the case in which everything is uniquely
1488 // referenced. In that case we can do this destructively.
1489 _CharT
* __ptr
= _My_rope::_S_fetch_ptr(__old
, _M_pos
);
1496 _Self_destruct_ptr
__left(_My_rope::_S_substring(__old
, 0, _M_pos
));
1497 _Self_destruct_ptr
__right(_My_rope::_S_substring(__old
, _M_pos
+ 1,
1499 _Self_destruct_ptr
__result_left(_My_rope::
1500 _S_destr_concat_char_iter(__left
,
1503 _RopeRep
* __result
= _My_rope::_S_concat(__result_left
, __right
);
1505 _RopeRep::_S_unref(__old
);
1507 _M_root
->_M_tree_ptr
= __result
;
1511 template <class _CharT
, class _Alloc
>
1512 inline _Rope_char_ref_proxy
<_CharT
, _Alloc
>::
1513 operator _CharT() const
1515 if (_M_current_valid
)
1518 return _My_rope::_S_fetch(_M_root
->_M_tree_ptr
, _M_pos
);
1521 template <class _CharT
, class _Alloc
>
1522 _Rope_char_ptr_proxy
<_CharT
, _Alloc
>
1523 _Rope_char_ref_proxy
<_CharT
, _Alloc
>::
1525 { return _Rope_char_ptr_proxy
<_CharT
, _Alloc
>(*this); }
1527 template <class _CharT
, class _Alloc
>
1528 rope
<_CharT
, _Alloc
>::
1529 rope(size_t __n
, _CharT __c
, const allocator_type
& __a
)
1532 rope
<_CharT
,_Alloc
> __result
;
1533 const size_t __exponentiate_threshold
= 32;
1536 _CharT
* __rest_buffer
;
1537 _RopeRep
* __remainder
;
1538 rope
<_CharT
, _Alloc
> __remainder_rope
;
1543 __exponent
= __n
/ __exponentiate_threshold
;
1544 __rest
= __n
% __exponentiate_threshold
;
1549 __rest_buffer
= this->_Data_allocate(_S_rounded_up_size(__rest
));
1550 __uninitialized_fill_n_a(__rest_buffer
, __rest
, __c
,
1552 _S_cond_store_eos(__rest_buffer
[__rest
]);
1554 { __remainder
= _S_new_RopeLeaf(__rest_buffer
, __rest
, __a
); }
1557 _RopeRep::__STL_FREE_STRING(__rest_buffer
, __rest
, __a
);
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
,
1570 _S_cond_store_eos(__base_buffer
[__exponentiate_threshold
]);
1573 __base_leaf
= _S_new_RopeLeaf(__base_buffer
,
1574 __exponentiate_threshold
, __a
);
1578 _RopeRep::__STL_FREE_STRING(__base_buffer
,
1579 __exponentiate_threshold
, __a
);
1580 __throw_exception_again
;
1582 __base_rope
._M_tree_ptr
= __base_leaf
;
1583 if (1 == __exponent
)
1584 __result
= __base_rope
;
1586 __result
= power(__base_rope
, __exponent
,
1587 _Rope_Concat_fn
<_CharT
, _Alloc
>());
1589 if (0 != __remainder
)
1590 __result
+= __remainder_rope
;
1593 __result
= __remainder_rope
;
1595 this->_M_tree_ptr
= __result
._M_tree_ptr
;
1596 this->_M_tree_ptr
->_M_ref_nonnil();
1599 template<class _CharT
, class _Alloc
>
1601 rope
<_CharT
, _Alloc
>::_S_empty_c_str
[1];
1603 template<class _CharT
, class _Alloc
>
1605 rope
<_CharT
, _Alloc
>::
1608 if (0 == this->_M_tree_ptr
)
1610 _S_empty_c_str
[0] = _S_eos((_CharT
*)0); // Possibly redundant,
1611 // but probably fast.
1612 return _S_empty_c_str
;
1614 __gthread_mutex_lock (&this->_M_tree_ptr
->_M_c_string_lock
);
1615 __GC_CONST _CharT
* __result
= this->_M_tree_ptr
->_M_c_string
;
1618 size_t __s
= size();
1619 __result
= this->_Data_allocate(__s
+ 1);
1620 _S_flatten(this->_M_tree_ptr
, __result
);
1621 __result
[__s
] = _S_eos((_CharT
*)0);
1622 this->_M_tree_ptr
->_M_c_string
= __result
;
1624 __gthread_mutex_unlock (&this->_M_tree_ptr
->_M_c_string_lock
);
1628 template<class _CharT
, class _Alloc
>
1629 const _CharT
* rope
<_CharT
, _Alloc
>::
1630 replace_with_c_str()
1632 if (0 == this->_M_tree_ptr
)
1634 _S_empty_c_str
[0] = _S_eos((_CharT
*)0);
1635 return _S_empty_c_str
;
1637 __GC_CONST _CharT
* __old_c_string
= this->_M_tree_ptr
->_M_c_string
;
1638 if (_Rope_constants::_S_leaf
== this->_M_tree_ptr
->_M_tag
1639 && 0 != __old_c_string
)
1640 return(__old_c_string
);
1641 size_t __s
= size();
1642 _CharT
* __result
= this->_Data_allocate(_S_rounded_up_size(__s
));
1643 _S_flatten(this->_M_tree_ptr
, __result
);
1644 __result
[__s
] = _S_eos((_CharT
*)0);
1645 this->_M_tree_ptr
->_M_unref_nonnil();
1646 this->_M_tree_ptr
= _S_new_RopeLeaf(__result
, __s
,
1647 this->get_allocator());
1651 // Algorithm specializations. More should be added.
1653 template<class _Rope_iterator
> // was templated on CharT and Alloc
1654 void // VC++ workaround
1655 _Rope_rotate(_Rope_iterator __first
,
1656 _Rope_iterator __middle
,
1657 _Rope_iterator __last
)
1659 typedef typename
_Rope_iterator::value_type _CharT
;
1660 typedef typename
_Rope_iterator::_allocator_type _Alloc
;
1662 rope
<_CharT
, _Alloc
>& __r(__first
.container());
1663 rope
<_CharT
, _Alloc
> __prefix
= __r
.substr(0, __first
.index());
1664 rope
<_CharT
, _Alloc
> __suffix
=
1665 __r
.substr(__last
.index(), __r
.size() - __last
.index());
1666 rope
<_CharT
, _Alloc
> __part1
=
1667 __r
.substr(__middle
.index(), __last
.index() - __middle
.index());
1668 rope
<_CharT
, _Alloc
> __part2
=
1669 __r
.substr(__first
.index(), __middle
.index() - __first
.index());
1676 #if !defined(__GNUC__)
1677 // Appears to confuse g++
1679 rotate(_Rope_iterator
<char, __STL_DEFAULT_ALLOCATOR(char)> __first
,
1680 _Rope_iterator
<char, __STL_DEFAULT_ALLOCATOR(char)> __middle
,
1681 _Rope_iterator
<char, __STL_DEFAULT_ALLOCATOR(char)> __last
)
1682 { _Rope_rotate(__first
, __middle
, __last
); }
1686 // Probably not useful for several reasons:
1687 // - for SGIs 7.1 compiler and probably some others,
1688 // this forces lots of rope<wchar_t, ...> instantiations, creating a
1689 // code bloat and compile time problem. (Fixed in 7.2.)
1690 // - wchar_t is 4 bytes wide on most UNIX platforms, making it
1691 // unattractive for unicode strings. Unsigned short may be a better
1694 rotate(_Rope_iterator
<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __first
,
1695 _Rope_iterator
<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __middle
,
1696 _Rope_iterator
<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __last
)
1697 { _Rope_rotate(__first
, __middle
, __last
); }
1700 } // namespace __gnu_cxx