3 * Silicon Graphics Computer Systems, Inc.
5 * Permission to use, copy, modify, distribute and sell this software
6 * and its documentation for any purpose is hereby granted without fee,
7 * provided that the above copyright notice appear in all copies and
8 * that both that copyright notice and this permission notice appear
9 * in supporting documentation. Silicon Graphics makes no
10 * representations about the suitability of this software for any
11 * purpose. It is provided "as is" without express or implied warranty.
14 /* NOTE: This is an internal header file, included by other STL headers.
15 * You should not attempt to use it directly.
18 #include <bits/std_cstdio.h>
19 #include <bits/std_iostream.h>
21 #ifdef __STL_USE_EXCEPTIONS
22 # include <bits/std_stdexcept.h>
28 // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
29 // if necessary. Assumes _M_path_end[leaf_index] and leaf_pos are correct.
30 // Results in a valid buf_ptr if the iterator can be legitimately
32 template <class _CharT
, class _Alloc
>
33 void _Rope_iterator_base
<_CharT
,_Alloc
>::_S_setbuf(
34 _Rope_iterator_base
<_CharT
,_Alloc
>& __x
)
36 const _RopeRep
* __leaf
= __x
._M_path_end
[__x
._M_leaf_index
];
37 size_t __leaf_pos
= __x
._M_leaf_pos
;
38 size_t __pos
= __x
._M_current_pos
;
40 switch(__leaf
->_M_tag
) {
41 case _RopeRep::_S_leaf
:
43 ((_Rope_RopeLeaf
<_CharT
,_Alloc
>*)__leaf
)->_M_data
;
44 __x
._M_buf_ptr
= __x
._M_buf_start
+ (__pos
- __leaf_pos
);
45 __x
._M_buf_end
= __x
._M_buf_start
+ __leaf
->_M_size
;
47 case _RopeRep::_S_function
:
48 case _RopeRep::_S_substringfn
:
50 size_t __len
= _S_iterator_buf_len
;
51 size_t __buf_start_pos
= __leaf_pos
;
52 size_t __leaf_end
= __leaf_pos
+ __leaf
->_M_size
;
53 char_producer
<_CharT
>* __fn
=
54 ((_Rope_RopeFunction
<_CharT
,_Alloc
>*)__leaf
)->_M_fn
;
56 if (__buf_start_pos
+ __len
<= __pos
) {
57 __buf_start_pos
= __pos
- __len
/4;
58 if (__buf_start_pos
+ __len
> __leaf_end
) {
59 __buf_start_pos
= __leaf_end
- __len
;
62 if (__buf_start_pos
+ __len
> __leaf_end
) {
63 __len
= __leaf_end
- __buf_start_pos
;
65 (*__fn
)(__buf_start_pos
- __leaf_pos
, __len
, __x
._M_tmp_buf
);
66 __x
._M_buf_ptr
= __x
._M_tmp_buf
+ (__pos
- __buf_start_pos
);
67 __x
._M_buf_start
= __x
._M_tmp_buf
;
68 __x
._M_buf_end
= __x
._M_tmp_buf
+ __len
;
76 // Set path and buffer inside a rope iterator. We assume that
77 // pos and root are already set.
78 template <class _CharT
, class _Alloc
>
79 void _Rope_iterator_base
<_CharT
,_Alloc
>::_S_setcache
80 (_Rope_iterator_base
<_CharT
,_Alloc
>& __x
)
82 const _RopeRep
* __path
[_RopeRep::_S_max_rope_depth
+1];
83 const _RopeRep
* __curr_rope
;
84 int __curr_depth
= -1; /* index into path */
85 size_t __curr_start_pos
= 0;
86 size_t __pos
= __x
._M_current_pos
;
87 unsigned char __dirns
= 0; // Bit vector marking right turns in the path
89 __stl_assert(__pos
<= __x
._M_root
->_M_size
);
90 if (__pos
>= __x
._M_root
->_M_size
) {
94 __curr_rope
= __x
._M_root
;
95 if (0 != __curr_rope
->_M_c_string
) {
96 /* Treat the root as a leaf. */
97 __x
._M_buf_start
= __curr_rope
->_M_c_string
;
98 __x
._M_buf_end
= __curr_rope
->_M_c_string
+ __curr_rope
->_M_size
;
99 __x
._M_buf_ptr
= __curr_rope
->_M_c_string
+ __pos
;
100 __x
._M_path_end
[0] = __curr_rope
;
101 __x
._M_leaf_index
= 0;
107 __stl_assert(__curr_depth
<= _RopeRep::_S_max_rope_depth
);
108 __path
[__curr_depth
] = __curr_rope
;
109 switch(__curr_rope
->_M_tag
) {
110 case _RopeRep::_S_leaf
:
111 case _RopeRep::_S_function
:
112 case _RopeRep::_S_substringfn
:
113 __x
._M_leaf_pos
= __curr_start_pos
;
115 case _RopeRep::_S_concat
:
117 _Rope_RopeConcatenation
<_CharT
,_Alloc
>* __c
=
118 (_Rope_RopeConcatenation
<_CharT
,_Alloc
>*)__curr_rope
;
119 _RopeRep
* __left
= __c
->_M_left
;
120 size_t __left_len
= __left
->_M_size
;
123 if (__pos
>= __curr_start_pos
+ __left_len
) {
125 __curr_rope
= __c
->_M_right
;
126 __curr_start_pos
+= __left_len
;
128 __curr_rope
= __left
;
135 // Copy last section of path into _M_path_end.
138 int __j
= __curr_depth
+ 1 - _S_path_cache_len
;
140 if (__j
< 0) __j
= 0;
141 while (__j
<= __curr_depth
) {
142 __x
._M_path_end
[++__i
] = __path
[__j
++];
144 __x
._M_leaf_index
= __i
;
146 __x
._M_path_directions
= __dirns
;
150 // Specialized version of the above. Assumes that
151 // the path cache is valid for the previous position.
152 template <class _CharT
, class _Alloc
>
153 void _Rope_iterator_base
<_CharT
,_Alloc
>::_S_setcache_for_incr
154 (_Rope_iterator_base
<_CharT
,_Alloc
>& __x
)
156 int __current_index
= __x
._M_leaf_index
;
157 const _RopeRep
* __current_node
= __x
._M_path_end
[__current_index
];
158 size_t __len
= __current_node
->_M_size
;
159 size_t __node_start_pos
= __x
._M_leaf_pos
;
160 unsigned char __dirns
= __x
._M_path_directions
;
161 _Rope_RopeConcatenation
<_CharT
,_Alloc
>* __c
;
163 __stl_assert(__x
._M_current_pos
<= __x
._M_root
->_M_size
);
164 if (__x
._M_current_pos
- __node_start_pos
< __len
) {
165 /* More stuff in this leaf, we just didn't cache it. */
169 __stl_assert(__node_start_pos
+ __len
== __x
._M_current_pos
);
170 // node_start_pos is starting position of last_node.
171 while (--__current_index
>= 0) {
172 if (!(__dirns
& 1) /* Path turned left */)
174 __current_node
= __x
._M_path_end
[__current_index
];
175 __c
= (_Rope_RopeConcatenation
<_CharT
,_Alloc
>*)__current_node
;
176 // Otherwise we were in the right child. Thus we should pop
177 // the concatenation node.
178 __node_start_pos
-= __c
->_M_left
->_M_size
;
181 if (__current_index
< 0) {
182 // We underflowed the cache. Punt.
186 __current_node
= __x
._M_path_end
[__current_index
];
187 __c
= (_Rope_RopeConcatenation
<_CharT
,_Alloc
>*)__current_node
;
188 // current_node is a concatenation node. We are positioned on the first
189 // character in its right child.
190 // node_start_pos is starting position of current_node.
191 __node_start_pos
+= __c
->_M_left
->_M_size
;
192 __current_node
= __c
->_M_right
;
193 __x
._M_path_end
[++__current_index
] = __current_node
;
195 while (_RopeRep::_S_concat
== __current_node
->_M_tag
) {
197 if (_S_path_cache_len
== __current_index
) {
199 for (__i
= 0; __i
< _S_path_cache_len
-1; __i
++) {
200 __x
._M_path_end
[__i
] = __x
._M_path_end
[__i
+1];
205 ((_Rope_RopeConcatenation
<_CharT
,_Alloc
>*)__current_node
)->_M_left
;
206 __x
._M_path_end
[__current_index
] = __current_node
;
208 // node_start_pos is unchanged.
210 __x
._M_leaf_index
= __current_index
;
211 __x
._M_leaf_pos
= __node_start_pos
;
212 __x
._M_path_directions
= __dirns
;
216 template <class _CharT
, class _Alloc
>
217 void _Rope_iterator_base
<_CharT
,_Alloc
>::_M_incr(size_t __n
) {
218 _M_current_pos
+= __n
;
219 if (0 != _M_buf_ptr
) {
220 size_t __chars_left
= _M_buf_end
- _M_buf_ptr
;
221 if (__chars_left
> __n
) {
223 } else if (__chars_left
== __n
) {
225 _S_setcache_for_incr(*this);
232 template <class _CharT
, class _Alloc
>
233 void _Rope_iterator_base
<_CharT
,_Alloc
>::_M_decr(size_t __n
) {
234 if (0 != _M_buf_ptr
) {
235 size_t __chars_left
= _M_buf_ptr
- _M_buf_start
;
236 if (__chars_left
>= __n
) {
242 _M_current_pos
-= __n
;
245 template <class _CharT
, class _Alloc
>
246 void _Rope_iterator
<_CharT
,_Alloc
>::_M_check() {
247 if (_M_root_rope
->_M_tree_ptr
!= _M_root
) {
248 // _Rope was modified. Get things fixed up.
249 _RopeRep::_S_unref(_M_root
);
250 _M_root
= _M_root_rope
->_M_tree_ptr
;
251 _RopeRep::_S_ref(_M_root
);
256 template <class _CharT
, class _Alloc
>
258 _Rope_const_iterator
<_CharT
, _Alloc
>::_Rope_const_iterator(
259 const _Rope_iterator
<_CharT
,_Alloc
>& __x
)
260 : _Rope_iterator_base
<_CharT
,_Alloc
>(__x
)
263 template <class _CharT
, class _Alloc
>
264 inline _Rope_iterator
<_CharT
,_Alloc
>::_Rope_iterator(
265 rope
<_CharT
,_Alloc
>& __r
, size_t __pos
)
266 : _Rope_iterator_base
<_CharT
,_Alloc
>(__r
._M_tree_ptr
, __pos
),
269 _RopeRep::_S_ref(_M_root
);
272 template <class _CharT
, class _Alloc
>
274 rope
<_CharT
,_Alloc
>::_S_char_ptr_len(const _CharT
* __s
)
276 const _CharT
* __p
= __s
;
278 while (!_S_is0(*__p
)) { ++__p
; }
285 template <class _CharT
, class _Alloc
>
286 inline void _Rope_RopeRep
<_CharT
,_Alloc
>::_M_free_c_string()
288 _CharT
* __cstr
= _M_c_string
;
290 size_t __size
= _M_size
+ 1;
291 destroy(__cstr
, __cstr
+ __size
);
292 _Data_deallocate(__cstr
, __size
);
297 template <class _CharT
, class _Alloc
>
298 inline void _Rope_RopeRep
<_CharT
,_Alloc
>::_S_free_string(_CharT
* __s
,
302 if (!_S_is_basic_char_type((_CharT
*)0)) {
303 destroy(__s
, __s
+ __n
);
305 // This has to be a static member, so this gets a bit messy
307 __s
, _Rope_RopeLeaf
<_CharT
,_Alloc
>::_S_rounded_up_size(__n
));
311 // There are several reasons for not doing this with virtual destructors
312 // and a class specific delete operator:
313 // - A class specific delete operator can't easily get access to
314 // allocator instances if we need them.
315 // - Any virtual function would need a 4 or byte vtable pointer;
316 // this only requires a one byte tag per object.
317 template <class _CharT
, class _Alloc
>
318 void _Rope_RopeRep
<_CharT
,_Alloc
>::_M_free_tree()
323 _Rope_RopeLeaf
<_CharT
,_Alloc
>* __l
324 = (_Rope_RopeLeaf
<_CharT
,_Alloc
>*)this;
325 __l
->_Rope_RopeLeaf
<_CharT
,_Alloc
>::~_Rope_RopeLeaf();
326 _L_deallocate(__l
, 1);
331 _Rope_RopeConcatenation
<_CharT
,_Alloc
>* __c
332 = (_Rope_RopeConcatenation
<_CharT
,_Alloc
>*)this;
333 __c
->_Rope_RopeConcatenation
<_CharT
,_Alloc
>::
334 ~_Rope_RopeConcatenation();
335 _C_deallocate(__c
, 1);
340 _Rope_RopeFunction
<_CharT
,_Alloc
>* __f
341 = (_Rope_RopeFunction
<_CharT
,_Alloc
>*)this;
342 __f
->_Rope_RopeFunction
<_CharT
,_Alloc
>::~_Rope_RopeFunction();
343 _F_deallocate(__f
, 1);
348 _Rope_RopeSubstring
<_CharT
,_Alloc
>* __ss
=
349 (_Rope_RopeSubstring
<_CharT
,_Alloc
>*)this;
350 __ss
->_Rope_RopeSubstring
<_CharT
,_Alloc
>::
351 ~_Rope_RopeSubstring();
352 _S_deallocate(__ss
, 1);
359 template <class _CharT
, class _Alloc
>
360 inline void _Rope_RopeRep
<_CharT
,_Alloc
>::_S_free_string
361 (const _CharT
*, size_t, allocator_type
)
367 // Concatenate a C string onto a leaf rope by copying the rope data.
368 // Used for short ropes.
369 template <class _CharT
, class _Alloc
>
370 rope
<_CharT
,_Alloc
>::_RopeLeaf
*
371 rope
<_CharT
,_Alloc
>::_S_leaf_concat_char_iter
372 (_RopeLeaf
* __r
, const _CharT
* __iter
, size_t __len
)
374 size_t __old_len
= __r
->_M_size
;
375 _CharT
* __new_data
= (_CharT
*)
376 _Data_allocate(_S_rounded_up_size(__old_len
+ __len
));
379 uninitialized_copy_n(__r
->_M_data
, __old_len
, __new_data
);
380 uninitialized_copy_n(__iter
, __len
, __new_data
+ __old_len
);
381 _S_cond_store_eos(__new_data
[__old_len
+ __len
]);
383 __result
= _S_new_RopeLeaf(__new_data
, __old_len
+ __len
,
384 __r
->get_allocator());
386 __STL_UNWIND(_RopeRep::__STL_FREE_STRING(__new_data
, __old_len
+ __len
,
387 __r
->get_allocator()));
392 // As above, but it's OK to clobber original if refcount is 1
393 template <class _CharT
, class _Alloc
>
394 rope
<_CharT
,_Alloc
>::_RopeLeaf
*
395 rope
<_CharT
,_Alloc
>::_S_destr_leaf_concat_char_iter
396 (_RopeLeaf
* __r
, const _CharT
* __iter
, size_t __len
)
398 __stl_assert(__r
->_M_ref_count
>= 1);
399 if (__r
->_M_ref_count
> 1)
400 return _S_leaf_concat_char_iter(__r
, __iter
, __len
);
401 size_t __old_len
= __r
->_M_size
;
402 if (_S_allocated_capacity(__old_len
) >= __old_len
+ __len
) {
403 // The space has been partially initialized for the standard
404 // character types. But that doesn't matter for those types.
405 uninitialized_copy_n(__iter
, __len
, __r
->_M_data
+ __old_len
);
406 if (_S_is_basic_char_type((_CharT
*)0)) {
407 _S_cond_store_eos(__r
->_M_data
[__old_len
+ __len
]);
408 __stl_assert(__r
->_M_c_string
== __r
->_M_data
);
409 } else if (__r
->_M_c_string
!= __r
->_M_data
&& 0 != __r
->_M_c_string
) {
410 __r
->_M_free_c_string();
411 __r
->_M_c_string
= 0;
413 __r
->_M_size
= __old_len
+ __len
;
414 __stl_assert(__r
->_M_ref_count
== 1);
415 __r
->_M_ref_count
= 2;
418 _RopeLeaf
* __result
= _S_leaf_concat_char_iter(__r
, __iter
, __len
);
419 __stl_assert(__result
->_M_ref_count
== 1);
425 // Assumes left and right are not 0.
426 // Does not increment (nor decrement on exception) child reference counts.
427 // Result has ref count 1.
428 template <class _CharT
, class _Alloc
>
429 rope
<_CharT
,_Alloc
>::_RopeRep
*
430 rope
<_CharT
,_Alloc
>::_S_tree_concat (_RopeRep
* __left
, _RopeRep
* __right
)
432 _RopeConcatenation
* __result
=
433 _S_new_RopeConcatenation(__left
, __right
, __left
->get_allocator());
434 size_t __depth
= __result
->_M_depth
;
436 __stl_assert(__left
->get_allocator() == __right
->get_allocator());
437 if (__depth
> 20 && (__result
->_M_size
< 1000 ||
438 __depth
> _RopeRep::_S_max_rope_depth
)) {
439 _RopeRep
* __balanced
;
442 __balanced
= _S_balance(__result
);
444 if (__result
!= __balanced
) {
445 __stl_assert(1 == __result
->_M_ref_count
446 && 1 == __balanced
->_M_ref_count
);
449 __result
->_M_unref_nonnil();
451 __STL_UNWIND((_C_deallocate(__result
,1)));
452 // In case of exception, we need to deallocate
453 // otherwise dangling result node. But caller
454 // still owns its children. Thus unref is
462 template <class _CharT
, class _Alloc
>
463 rope
<_CharT
,_Alloc
>::_RopeRep
* rope
<_CharT
,_Alloc
>::_S_concat_char_iter
464 (_RopeRep
* __r
, const _CharT
*__s
, size_t __slen
)
472 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __slen
,
473 __r
->get_allocator());
474 if (_RopeRep::_S_leaf
== __r
->_M_tag
&&
475 __r
->_M_size
+ __slen
<= _S_copy_max
) {
476 __result
= _S_leaf_concat_char_iter((_RopeLeaf
*)__r
, __s
, __slen
);
478 __stl_assert(1 == __result
->_M_ref_count
);
482 if (_RopeRep::_S_concat
== __r
->_M_tag
483 && _RopeRep::_S_leaf
== ((_RopeConcatenation
*)__r
)->_M_right
->_M_tag
) {
485 (_RopeLeaf
* )(((_RopeConcatenation
* )__r
)->_M_right
);
486 if (__right
->_M_size
+ __slen
<= _S_copy_max
) {
487 _RopeRep
* __left
= ((_RopeConcatenation
*)__r
)->_M_left
;
489 _S_leaf_concat_char_iter((_RopeLeaf
*)__right
, __s
, __slen
);
490 __left
->_M_ref_nonnil();
492 __result
= _S_tree_concat(__left
, __nright
);
494 __STL_UNWIND(_S_unref(__left
); _S_unref(__nright
));
496 __stl_assert(1 == __result
->_M_ref_count
);
502 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __slen
, __r
->get_allocator());
504 __r
->_M_ref_nonnil();
505 __result
= _S_tree_concat(__r
, __nright
);
507 __STL_UNWIND(_S_unref(__r
); _S_unref(__nright
));
509 __stl_assert(1 == __result
->_M_ref_count
);
515 template <class _CharT
, class _Alloc
>
516 rope
<_CharT
,_Alloc
>::_RopeRep
*
517 rope
<_CharT
,_Alloc
>::_S_destr_concat_char_iter(
518 _RopeRep
* __r
, const _CharT
* __s
, size_t __slen
)
522 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __slen
,
523 __r
->get_allocator());
524 size_t __count
= __r
->_M_ref_count
;
525 size_t __orig_size
= __r
->_M_size
;
526 __stl_assert(__count
>= 1);
527 if (__count
> 1) return _S_concat_char_iter(__r
, __s
, __slen
);
529 __r
->_M_ref_count
= 2; // One more than before
532 if (__orig_size
+ __slen
<= _S_copy_max
&&
533 _RopeRep::_S_leaf
== __r
->_M_tag
) {
534 __result
= _S_destr_leaf_concat_char_iter((_RopeLeaf
*)__r
, __s
, __slen
);
537 if (_RopeRep::_S_concat
== __r
->_M_tag
) {
538 _RopeLeaf
* __right
= (_RopeLeaf
*)(((_RopeConcatenation
*)__r
)->_M_right
);
539 if (_RopeRep::_S_leaf
== __right
->_M_tag
540 && __right
->_M_size
+ __slen
<= _S_copy_max
) {
541 _RopeRep
* __new_right
=
542 _S_destr_leaf_concat_char_iter(__right
, __s
, __slen
);
543 if (__right
== __new_right
) {
544 __stl_assert(__new_right
->_M_ref_count
== 2);
545 __new_right
->_M_ref_count
= 1;
547 __stl_assert(__new_right
->_M_ref_count
>= 1);
548 __right
->_M_unref_nonnil();
550 __stl_assert(__r
->_M_ref_count
== 1);
551 __r
->_M_ref_count
= 2; // One more than before.
552 ((_RopeConcatenation
*)__r
)->_M_right
= __new_right
;
553 __r
->_M_size
= __orig_size
+ __slen
;
554 if (0 != __r
->_M_c_string
) {
555 __r
->_M_free_c_string();
556 __r
->_M_c_string
= 0;
562 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __slen
, __r
->get_allocator());
563 __r
->_M_ref_nonnil();
565 __result
= _S_tree_concat(__r
, __right
);
567 __STL_UNWIND(_S_unref(__r
); _S_unref(__right
))
568 __stl_assert(1 == __result
->_M_ref_count
);
573 template <class _CharT
, class _Alloc
>
574 rope
<_CharT
,_Alloc
>::_RopeRep
*
575 rope
<_CharT
,_Alloc
>::_S_concat(_RopeRep
* __left
, _RopeRep
* __right
)
582 __left
->_M_ref_nonnil();
585 if (_RopeRep::_S_leaf
== __right
->_M_tag
) {
586 if (_RopeRep::_S_leaf
== __left
->_M_tag
) {
587 if (__right
->_M_size
+ __left
->_M_size
<= _S_copy_max
) {
588 return _S_leaf_concat_char_iter((_RopeLeaf
*)__left
,
589 ((_RopeLeaf
*)__right
)->_M_data
,
592 } else if (_RopeRep::_S_concat
== __left
->_M_tag
593 && _RopeRep::_S_leaf
==
594 ((_RopeConcatenation
*)__left
)->_M_right
->_M_tag
) {
595 _RopeLeaf
* __leftright
=
596 (_RopeLeaf
*)(((_RopeConcatenation
*)__left
)->_M_right
);
597 if (__leftright
->_M_size
+ __right
->_M_size
<= _S_copy_max
) {
598 _RopeRep
* __leftleft
= ((_RopeConcatenation
*)__left
)->_M_left
;
599 _RopeRep
* __rest
= _S_leaf_concat_char_iter(__leftright
,
600 ((_RopeLeaf
*)__right
)->_M_data
,
602 __leftleft
->_M_ref_nonnil();
604 return(_S_tree_concat(__leftleft
, __rest
));
606 __STL_UNWIND(_S_unref(__leftleft
); _S_unref(__rest
))
610 __left
->_M_ref_nonnil();
611 __right
->_M_ref_nonnil();
613 return(_S_tree_concat(__left
, __right
));
615 __STL_UNWIND(_S_unref(__left
); _S_unref(__right
));
618 template <class _CharT
, class _Alloc
>
619 rope
<_CharT
,_Alloc
>::_RopeRep
*
620 rope
<_CharT
,_Alloc
>::_S_substring(_RopeRep
* __base
,
621 size_t __start
, size_t __endp1
)
623 if (0 == __base
) return 0;
624 size_t __len
= __base
->_M_size
;
626 const size_t __lazy_threshold
= 128;
628 if (__endp1
>= __len
) {
630 __base
->_M_ref_nonnil();
636 __adj_endp1
= __endp1
;
638 switch(__base
->_M_tag
) {
639 case _RopeRep::_S_concat
:
641 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__base
;
642 _RopeRep
* __left
= __c
->_M_left
;
643 _RopeRep
* __right
= __c
->_M_right
;
644 size_t __left_len
= __left
->_M_size
;
647 if (__adj_endp1
<= __left_len
) {
648 return _S_substring(__left
, __start
, __endp1
);
649 } else if (__start
>= __left_len
) {
650 return _S_substring(__right
, __start
- __left_len
,
651 __adj_endp1
- __left_len
);
653 _Self_destruct_ptr
__left_result(
654 _S_substring(__left
, __start
, __left_len
));
655 _Self_destruct_ptr
__right_result(
656 _S_substring(__right
, 0, __endp1
- __left_len
));
657 __result
= _S_concat(__left_result
, __right_result
);
659 __stl_assert(1 == __result
->_M_ref_count
);
663 case _RopeRep::_S_leaf
:
665 _RopeLeaf
* __l
= (_RopeLeaf
*)__base
;
668 if (__start
>= __adj_endp1
) return 0;
669 __result_len
= __adj_endp1
- __start
;
670 if (__result_len
> __lazy_threshold
) goto lazy
;
672 const _CharT
* __section
= __l
->_M_data
+ __start
;
673 __result
= _S_new_RopeLeaf(__section
, __result_len
,
674 __base
->get_allocator());
675 __result
->_M_c_string
= 0; // Not eos terminated.
677 // We should sometimes create substring node instead.
678 __result
= __STL_ROPE_FROM_UNOWNED_CHAR_PTR(
679 __l
->_M_data
+ __start
, __result_len
,
680 __base
->get_allocator());
684 case _RopeRep::_S_substringfn
:
685 // Avoid introducing multiple layers of substring nodes.
687 _RopeSubstring
* __old
= (_RopeSubstring
*)__base
;
689 if (__start
>= __adj_endp1
) return 0;
690 __result_len
= __adj_endp1
- __start
;
691 if (__result_len
> __lazy_threshold
) {
692 _RopeSubstring
* __result
=
693 _S_new_RopeSubstring(__old
->_M_base
,
694 __start
+ __old
->_M_start
,
695 __adj_endp1
- __start
,
696 __base
->get_allocator());
699 } // *** else fall through: ***
701 case _RopeRep::_S_function
:
703 _RopeFunction
* __f
= (_RopeFunction
*)__base
;
706 if (__start
>= __adj_endp1
) return 0;
707 __result_len
= __adj_endp1
- __start
;
709 if (__result_len
> __lazy_threshold
) goto lazy
;
710 __section
= (_CharT
*)
711 _Data_allocate(_S_rounded_up_size(__result_len
));
713 (*(__f
->_M_fn
))(__start
, __result_len
, __section
);
715 __STL_UNWIND(_RopeRep::__STL_FREE_STRING(
716 __section
, __result_len
, __base
->get_allocator()));
717 _S_cond_store_eos(__section
[__result_len
]);
718 return _S_new_RopeLeaf(__section
, __result_len
,
719 __base
->get_allocator());
726 // Create substring node.
727 return _S_new_RopeSubstring(__base
, __start
, __adj_endp1
- __start
,
728 __base
->get_allocator());
732 template<class _CharT
>
733 class _Rope_flatten_char_consumer
: public _Rope_char_consumer
<_CharT
> {
738 _Rope_flatten_char_consumer(_CharT
* __buffer
) {
739 _M_buf_ptr
= __buffer
;
741 ~_Rope_flatten_char_consumer() {}
742 bool operator() (const _CharT
* __leaf
, size_t __n
) {
743 uninitialized_copy_n(__leaf
, __n
, _M_buf_ptr
);
749 template<class _CharT
>
750 class _Rope_find_char_char_consumer
: public _Rope_char_consumer
<_CharT
> {
754 size_t _M_count
; // Number of nonmatching characters
755 _Rope_find_char_char_consumer(_CharT __p
)
756 : _M_pattern(__p
), _M_count(0) {}
757 ~_Rope_find_char_char_consumer() {}
758 bool operator() (const _CharT
* __leaf
, size_t __n
) {
760 for (__i
= 0; __i
< __n
; __i
++) {
761 if (__leaf
[__i
] == _M_pattern
) {
762 _M_count
+= __i
; return false;
765 _M_count
+= __n
; return true;
769 template<class _CharT
, class _Traits
>
770 // Here _CharT is both the stream and rope character type.
771 class _Rope_insert_char_consumer
: public _Rope_char_consumer
<_CharT
> {
773 typedef basic_ostream
<_CharT
,_Traits
> _Insert_ostream
;
774 _Insert_ostream
& _M_o
;
776 _Rope_insert_char_consumer(_Insert_ostream
& __writer
)
778 ~_Rope_insert_char_consumer() { };
779 // Caller is presumed to own the ostream
780 bool operator() (const _CharT
* __leaf
, size_t __n
);
781 // Returns true to continue traversal.
784 template<class _CharT
, class _Traits
>
785 bool _Rope_insert_char_consumer
<_CharT
, _Traits
>::operator()
786 (const _CharT
* __leaf
, size_t __n
)
789 // We assume that formatting is set up correctly for each element.
790 for (__i
= 0; __i
< __n
; __i
++) _M_o
.put(__leaf
[__i
]);
794 template <class _CharT
, class _Alloc
>
795 bool rope
<_CharT
, _Alloc
>::_S_apply_to_pieces(
796 _Rope_char_consumer
<_CharT
>& __c
,
798 size_t __begin
, size_t __end
)
800 if (0 == __r
) return true;
801 switch(__r
->_M_tag
) {
802 case _RopeRep::_S_concat
:
804 _RopeConcatenation
* __conc
= (_RopeConcatenation
*)__r
;
805 _RopeRep
* __left
= __conc
->_M_left
;
806 size_t __left_len
= __left
->_M_size
;
807 if (__begin
< __left_len
) {
808 size_t __left_end
= min(__left_len
, __end
);
809 if (!_S_apply_to_pieces(__c
, __left
, __begin
, __left_end
))
812 if (__end
> __left_len
) {
813 _RopeRep
* __right
= __conc
->_M_right
;
814 size_t __right_start
= max(__left_len
, __begin
);
815 if (!_S_apply_to_pieces(__c
, __right
,
816 __right_start
- __left_len
,
817 __end
- __left_len
)) {
823 case _RopeRep::_S_leaf
:
825 _RopeLeaf
* __l
= (_RopeLeaf
*)__r
;
826 return __c(__l
->_M_data
+ __begin
, __end
- __begin
);
828 case _RopeRep::_S_function
:
829 case _RopeRep::_S_substringfn
:
831 _RopeFunction
* __f
= (_RopeFunction
*)__r
;
832 size_t __len
= __end
- __begin
;
835 (_CharT
*)alloc::allocate(__len
* sizeof(_CharT
));
837 (*(__f
->_M_fn
))(__begin
, __len
, __buffer
);
838 __result
= __c(__buffer
, __len
);
839 alloc::deallocate(__buffer
, __len
* sizeof(_CharT
));
841 __STL_UNWIND((alloc::deallocate(__buffer
,
842 __len
* sizeof(_CharT
))))
852 template<class _CharT
, class _Traits
>
853 inline void _Rope_fill(basic_ostream
<_CharT
, _Traits
>& __o
, size_t __n
)
855 char __f
= __o
.fill();
858 for (__i
= 0; __i
< __n
; __i
++) __o
.put(__f
);
862 template <class _CharT
> inline bool _Rope_is_simple(_CharT
*) { return false; }
863 inline bool _Rope_is_simple(char*) { return true; }
864 inline bool _Rope_is_simple(wchar_t*) { return true; }
866 template<class _CharT
, class _Traits
, class _Alloc
>
867 basic_ostream
<_CharT
, _Traits
>& operator<< (basic_ostream
<_CharT
, _Traits
>& __o
,
868 const rope
<_CharT
, _Alloc
>& __r
)
870 size_t __w
= __o
.width();
871 bool __left
= bool(__o
.flags() & ios::left
);
873 size_t __rope_len
= __r
.size();
874 _Rope_insert_char_consumer
<_CharT
, _Traits
> __c(__o
);
875 bool __is_simple
= _Rope_is_simple((_CharT
*)0);
877 if (__rope_len
< __w
) {
878 __pad_len
= __w
- __rope_len
;
882 if (!__is_simple
) __o
.width(__w
/__rope_len
);
884 if (__is_simple
&& !__left
&& __pad_len
> 0) {
885 _Rope_fill(__o
, __pad_len
);
887 __r
.apply_to_pieces(0, __r
.size(), __c
);
888 if (__is_simple
&& __left
&& __pad_len
> 0) {
889 _Rope_fill(__o
, __pad_len
);
894 __STL_UNWIND(if (!__is_simple
) __o
.width(__w
))
898 template <class _CharT
, class _Alloc
>
900 rope
<_CharT
,_Alloc
>::_S_flatten(_RopeRep
* __r
,
901 size_t __start
, size_t __len
,
904 _Rope_flatten_char_consumer
<_CharT
> __c(__buffer
);
905 _S_apply_to_pieces(__c
, __r
, __start
, __start
+ __len
);
906 return(__buffer
+ __len
);
909 template <class _CharT
, class _Alloc
>
911 rope
<_CharT
,_Alloc
>::find(_CharT __pattern
, size_t __start
) const
913 _Rope_find_char_char_consumer
<_CharT
> __c(__pattern
);
914 _S_apply_to_pieces(__c
, _M_tree_ptr
, __start
, size());
915 size_type __result_pos
= __start
+ __c
._M_count
;
916 # ifndef __STL_OLD_ROPE_SEMANTICS
917 if (__result_pos
== size()) __result_pos
= npos
;
922 template <class _CharT
, class _Alloc
>
924 rope
<_CharT
,_Alloc
>::_S_flatten(_RopeRep
* __r
, _CharT
* __buffer
)
926 if (0 == __r
) return __buffer
;
927 switch(__r
->_M_tag
) {
928 case _RopeRep::_S_concat
:
930 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
931 _RopeRep
* __left
= __c
->_M_left
;
932 _RopeRep
* __right
= __c
->_M_right
;
933 _CharT
* __rest
= _S_flatten(__left
, __buffer
);
934 return _S_flatten(__right
, __rest
);
936 case _RopeRep::_S_leaf
:
938 _RopeLeaf
* __l
= (_RopeLeaf
*)__r
;
939 return copy_n(__l
->_M_data
, __l
->_M_size
, __buffer
).second
;
941 case _RopeRep::_S_function
:
942 case _RopeRep::_S_substringfn
:
943 // We dont yet do anything with substring nodes.
944 // This needs to be fixed before ropefiles will work well.
946 _RopeFunction
* __f
= (_RopeFunction
*)__r
;
947 (*(__f
->_M_fn
))(0, __f
->_M_size
, __buffer
);
948 return __buffer
+ __f
->_M_size
;
958 // This needs work for _CharT != char
959 template <class _CharT
, class _Alloc
>
961 rope
<_CharT
,_Alloc
>::_S_dump(_RopeRep
* __r
, int __indent
)
963 for (int __i
= 0; __i
< __indent
; __i
++) putchar(' ');
965 printf("NULL\n"); return;
967 if (_RopeRep::_S_concat
== __r
->_M_tag
) {
968 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
969 _RopeRep
* __left
= __c
->_M_left
;
970 _RopeRep
* __right
= __c
->_M_right
;
973 printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
974 __r
, __r
->_M_depth
, __r
->_M_size
, __r
->_M_is_balanced
? "" : "not");
976 printf("Concatenation %p (rc = %ld, depth = %d, "
977 "len = %ld, %s balanced)\n",
978 __r
, __r
->_M_ref_count
, __r
->_M_depth
, __r
->_M_size
,
979 __r
->_M_is_balanced
? "" : "not");
981 _S_dump(__left
, __indent
+ 2);
982 _S_dump(__right
, __indent
+ 2);
987 switch (__r
->_M_tag
) {
988 case _RopeRep::_S_leaf
:
991 case _RopeRep::_S_function
:
994 case _RopeRep::_S_substringfn
:
995 __kind
= "Function representing substring";
998 __kind
= "(corrupted kind field!)";
1001 printf("%s %p (depth = %d, len = %ld) ",
1002 __kind
, __r
, __r
->_M_depth
, __r
->_M_size
);
1004 printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
1005 __kind
, __r
, __r
->_M_ref_count
, __r
->_M_depth
, __r
->_M_size
);
1007 if (_S_is_one_byte_char_type((_CharT
*)0)) {
1008 const int __max_len
= 40;
1009 _Self_destruct_ptr
__prefix(_S_substring(__r
, 0, __max_len
));
1010 _CharT __buffer
[__max_len
+ 1];
1011 bool __too_big
= __r
->_M_size
> __prefix
->_M_size
;
1013 _S_flatten(__prefix
, __buffer
);
1014 __buffer
[__prefix
->_M_size
] = _S_eos((_CharT
*)0);
1016 (char*)__buffer
, __too_big
? "...\n" : "\n");
1023 template <class _CharT
, class _Alloc
>
1025 rope
<_CharT
,_Alloc
>::_S_min_len
[
1026 _Rope_RopeRep
<_CharT
,_Alloc
>::_S_max_rope_depth
+ 1] = {
1027 /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21,
1028 /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377,
1029 /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181,
1030 /* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368,
1031 /* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811,
1032 /* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309,
1033 /* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352,
1034 /* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155,
1035 /* 39 */165580141, /* 40 */267914296, /* 41 */433494437,
1036 /* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903,
1037 /* 45 */2971215073u };
1038 // These are Fibonacci numbers < 2**32.
1040 template <class _CharT
, class _Alloc
>
1041 rope
<_CharT
,_Alloc
>::_RopeRep
*
1042 rope
<_CharT
,_Alloc
>::_S_balance(_RopeRep
* __r
)
1044 _RopeRep
* __forest
[_RopeRep::_S_max_rope_depth
+ 1];
1045 _RopeRep
* __result
= 0;
1048 // The concatenation of forest in descending order is equal to __r.
1049 // __forest[__i]._M_size >= _S_min_len[__i]
1050 // __forest[__i]._M_depth = __i
1051 // References from forest are included in refcount.
1053 for (__i
= 0; __i
<= _RopeRep::_S_max_rope_depth
; ++__i
)
1056 _S_add_to_forest(__r
, __forest
);
1057 for (__i
= 0; __i
<= _RopeRep::_S_max_rope_depth
; ++__i
)
1058 if (0 != __forest
[__i
]) {
1060 _Self_destruct_ptr
__old(__result
);
1062 __result
= _S_concat(__forest
[__i
], __result
);
1063 __forest
[__i
]->_M_unref_nonnil();
1064 # if !defined(__GC) && defined(__STL_USE_EXCEPTIONS)
1069 __STL_UNWIND(for(__i
= 0; __i
<= _RopeRep::_S_max_rope_depth
; __i
++)
1070 _S_unref(__forest
[__i
]))
1071 if (__result
->_M_depth
> _RopeRep::_S_max_rope_depth
) {
1072 # ifdef __STL_USE_EXCEPTIONS
1073 __STL_THROW(length_error("rope too long"));
1082 template <class _CharT
, class _Alloc
>
1084 rope
<_CharT
,_Alloc
>::_S_add_to_forest(_RopeRep
* __r
, _RopeRep
** __forest
)
1086 if (__r
->_M_is_balanced
) {
1087 _S_add_leaf_to_forest(__r
, __forest
);
1090 __stl_assert(__r
->_M_tag
== _RopeRep::_S_concat
);
1092 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1094 _S_add_to_forest(__c
->_M_left
, __forest
);
1095 _S_add_to_forest(__c
->_M_right
, __forest
);
1100 template <class _CharT
, class _Alloc
>
1102 rope
<_CharT
,_Alloc
>::_S_add_leaf_to_forest(_RopeRep
* __r
, _RopeRep
** __forest
)
1104 _RopeRep
* __insertee
; // included in refcount
1105 _RopeRep
* __too_tiny
= 0; // included in refcount
1106 int __i
; // forest[0..__i-1] is empty
1107 size_t __s
= __r
->_M_size
;
1109 for (__i
= 0; __s
>= _S_min_len
[__i
+1]/* not this bucket */; ++__i
) {
1110 if (0 != __forest
[__i
]) {
1112 _Self_destruct_ptr
__old(__too_tiny
);
1114 __too_tiny
= _S_concat_and_set_balanced(__forest
[__i
], __too_tiny
);
1115 __forest
[__i
]->_M_unref_nonnil();
1121 _Self_destruct_ptr
__old(__too_tiny
);
1123 __insertee
= _S_concat_and_set_balanced(__too_tiny
, __r
);
1125 // Too_tiny dead, and no longer included in refcount.
1126 // Insertee is live and included.
1127 __stl_assert(_S_is_almost_balanced(__insertee
));
1128 __stl_assert(__insertee
->_M_depth
<= __r
->_M_depth
+ 1);
1130 if (0 != __forest
[__i
]) {
1132 _Self_destruct_ptr
__old(__insertee
);
1134 __insertee
= _S_concat_and_set_balanced(__forest
[__i
], __insertee
);
1135 __forest
[__i
]->_M_unref_nonnil();
1137 __stl_assert(_S_is_almost_balanced(__insertee
));
1139 __stl_assert(_S_min_len
[__i
] <= __insertee
->_M_size
);
1140 __stl_assert(__forest
[__i
] == 0);
1141 if (__i
== _RopeRep::_S_max_rope_depth
||
1142 __insertee
->_M_size
< _S_min_len
[__i
+1]) {
1143 __forest
[__i
] = __insertee
;
1144 // refcount is OK since __insertee is now dead.
1150 template <class _CharT
, class _Alloc
>
1152 rope
<_CharT
,_Alloc
>::_S_fetch(_RopeRep
* __r
, size_type __i
)
1154 __GC_CONST _CharT
* __cstr
= __r
->_M_c_string
;
1156 __stl_assert(__i
< __r
->_M_size
);
1157 if (0 != __cstr
) return __cstr
[__i
];
1159 switch(__r
->_M_tag
) {
1160 case _RopeRep::_S_concat
:
1162 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1163 _RopeRep
* __left
= __c
->_M_left
;
1164 size_t __left_len
= __left
->_M_size
;
1166 if (__i
>= __left_len
) {
1168 __r
= __c
->_M_right
;
1174 case _RopeRep::_S_leaf
:
1176 _RopeLeaf
* __l
= (_RopeLeaf
*)__r
;
1177 return __l
->_M_data
[__i
];
1179 case _RopeRep::_S_function
:
1180 case _RopeRep::_S_substringfn
:
1182 _RopeFunction
* __f
= (_RopeFunction
*)__r
;
1185 (*(__f
->_M_fn
))(__i
, 1, &__result
);
1193 // Return a uniquely referenced character slot for the given
1194 // position, or 0 if that's not possible.
1195 template <class _CharT
, class _Alloc
>
1197 rope
<_CharT
,_Alloc
>::_S_fetch_ptr(_RopeRep
* __r
, size_type __i
)
1199 _RopeRep
* __clrstack
[_RopeRep::_S_max_rope_depth
];
1203 if (__r
->_M_ref_count
> 1) return 0;
1204 switch(__r
->_M_tag
) {
1205 case _RopeRep::_S_concat
:
1207 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1208 _RopeRep
* __left
= __c
->_M_left
;
1209 size_t __left_len
= __left
->_M_size
;
1211 if (__c
->_M_c_string
!= 0) __clrstack
[__csptr
++] = __c
;
1212 if (__i
>= __left_len
) {
1214 __r
= __c
->_M_right
;
1220 case _RopeRep::_S_leaf
:
1222 _RopeLeaf
* __l
= (_RopeLeaf
*)__r
;
1223 if (__l
->_M_c_string
!= __l
->_M_data
&& __l
->_M_c_string
!= 0)
1224 __clrstack
[__csptr
++] = __l
;
1225 while (__csptr
> 0) {
1227 _RopeRep
* __d
= __clrstack
[__csptr
];
1228 __d
->_M_free_c_string();
1229 __d
->_M_c_string
= 0;
1231 return __l
->_M_data
+ __i
;
1233 case _RopeRep::_S_function
:
1234 case _RopeRep::_S_substringfn
:
1241 // The following could be implemented trivially using
1242 // lexicographical_compare_3way.
1243 // We do a little more work to avoid dealing with rope iterators for
1245 template <class _CharT
, class _Alloc
>
1247 rope
<_CharT
,_Alloc
>::_S_compare (const _RopeRep
* __left
,
1248 const _RopeRep
* __right
)
1253 if (0 == __right
) return 0 != __left
;
1254 if (0 == __left
) return -1;
1255 __left_len
= __left
->_M_size
;
1256 __right_len
= __right
->_M_size
;
1257 if (_RopeRep::_S_leaf
== __left
->_M_tag
) {
1258 _RopeLeaf
* __l
= (_RopeLeaf
*) __left
;
1259 if (_RopeRep::_S_leaf
== __right
->_M_tag
) {
1260 _RopeLeaf
* __r
= (_RopeLeaf
*) __right
;
1261 return lexicographical_compare_3way(
1262 __l
->_M_data
, __l
->_M_data
+ __left_len
,
1263 __r
->_M_data
, __r
->_M_data
+ __right_len
);
1265 const_iterator
__rstart(__right
, 0);
1266 const_iterator
__rend(__right
, __right_len
);
1267 return lexicographical_compare_3way(
1268 __l
->_M_data
, __l
->_M_data
+ __left_len
,
1272 const_iterator
__lstart(__left
, 0);
1273 const_iterator
__lend(__left
, __left_len
);
1274 if (_RopeRep::_S_leaf
== __right
->_M_tag
) {
1275 _RopeLeaf
* __r
= (_RopeLeaf
*) __right
;
1276 return lexicographical_compare_3way(
1278 __r
->_M_data
, __r
->_M_data
+ __right_len
);
1280 const_iterator
__rstart(__right
, 0);
1281 const_iterator
__rend(__right
, __right_len
);
1282 return lexicographical_compare_3way(
1289 // Assignment to reference proxies.
1290 template <class _CharT
, class _Alloc
>
1291 _Rope_char_ref_proxy
<_CharT
, _Alloc
>&
1292 _Rope_char_ref_proxy
<_CharT
, _Alloc
>::operator= (_CharT __c
) {
1293 _RopeRep
* __old
= _M_root
->_M_tree_ptr
;
1295 // First check for the case in which everything is uniquely
1296 // referenced. In that case we can do this destructively.
1297 _CharT
* __ptr
= _My_rope::_S_fetch_ptr(__old
, _M_pos
);
1303 _Self_destruct_ptr
__left(
1304 _My_rope::_S_substring(__old
, 0, _M_pos
));
1305 _Self_destruct_ptr
__right(
1306 _My_rope::_S_substring(__old
, _M_pos
+1, __old
->_M_size
));
1307 _Self_destruct_ptr
__result_left(
1308 _My_rope::_S_destr_concat_char_iter(__left
, &__c
, 1));
1311 __stl_assert(__left
== __result_left
|| 1 == __result_left
->_M_ref_count
);
1313 _RopeRep
* __result
=
1314 _My_rope::_S_concat(__result_left
, __right
);
1316 __stl_assert(1 <= __result
->_M_ref_count
);
1317 _RopeRep::_S_unref(__old
);
1319 _M_root
->_M_tree_ptr
= __result
;
1323 template <class _CharT
, class _Alloc
>
1324 inline _Rope_char_ref_proxy
<_CharT
, _Alloc
>::operator _CharT () const
1326 if (_M_current_valid
) {
1329 return _My_rope::_S_fetch(_M_root
->_M_tree_ptr
, _M_pos
);
1332 template <class _CharT
, class _Alloc
>
1333 _Rope_char_ptr_proxy
<_CharT
, _Alloc
>
1334 _Rope_char_ref_proxy
<_CharT
, _Alloc
>::operator& () const {
1335 return _Rope_char_ptr_proxy
<_CharT
, _Alloc
>(*this);
1338 template <class _CharT
, class _Alloc
>
1339 rope
<_CharT
, _Alloc
>::rope(size_t __n
, _CharT __c
,
1340 const allocator_type
& __a
)
1343 rope
<_CharT
,_Alloc
> __result
;
1344 const size_t __exponentiate_threshold
= 32;
1347 _CharT
* __rest_buffer
;
1348 _RopeRep
* __remainder
;
1349 rope
<_CharT
,_Alloc
> __remainder_rope
;
1354 __exponent
= __n
/ __exponentiate_threshold
;
1355 __rest
= __n
% __exponentiate_threshold
;
1359 __rest_buffer
= _Data_allocate(_S_rounded_up_size(__rest
));
1360 uninitialized_fill_n(__rest_buffer
, __rest
, __c
);
1361 _S_cond_store_eos(__rest_buffer
[__rest
]);
1363 __remainder
= _S_new_RopeLeaf(__rest_buffer
, __rest
, __a
);
1365 __STL_UNWIND(_RopeRep::__STL_FREE_STRING(__rest_buffer
, __rest
, __a
))
1367 __remainder_rope
._M_tree_ptr
= __remainder
;
1368 if (__exponent
!= 0) {
1369 _CharT
* __base_buffer
=
1370 _Data_allocate(_S_rounded_up_size(__exponentiate_threshold
));
1371 _RopeLeaf
* __base_leaf
;
1373 uninitialized_fill_n(__base_buffer
, __exponentiate_threshold
, __c
);
1374 _S_cond_store_eos(__base_buffer
[__exponentiate_threshold
]);
1376 __base_leaf
= _S_new_RopeLeaf(__base_buffer
,
1377 __exponentiate_threshold
, __a
);
1379 __STL_UNWIND(_RopeRep::__STL_FREE_STRING(__base_buffer
,
1380 __exponentiate_threshold
, __a
))
1381 __base_rope
._M_tree_ptr
= __base_leaf
;
1382 if (1 == __exponent
) {
1383 __result
= __base_rope
;
1385 __stl_assert(2 == __result
._M_tree_ptr
->_M_ref_count
);
1386 // One each for base_rope and __result
1389 __result
= power(__base_rope
, __exponent
,
1390 _Rope_Concat_fn
<_CharT
,_Alloc
>());
1392 if (0 != __remainder
) {
1393 __result
+= __remainder_rope
;
1396 __result
= __remainder_rope
;
1398 _M_tree_ptr
= __result
._M_tree_ptr
;
1399 _M_tree_ptr
->_M_ref_nonnil();
1402 template<class _CharT
, class _Alloc
>
1403 _CharT rope
<_CharT
,_Alloc
>::_S_empty_c_str
[1];
1405 template<class _CharT
, class _Alloc
>
1406 const _CharT
* rope
<_CharT
,_Alloc
>::c_str() const {
1407 if (0 == _M_tree_ptr
) {
1408 _S_empty_c_str
[0] = _S_eos((_CharT
*)0); // Possibly redundant,
1409 // but probably fast.
1410 return _S_empty_c_str
;
1412 __GC_CONST _CharT
* __old_c_string
= _M_tree_ptr
->_M_c_string
;
1413 if (0 != __old_c_string
) return(__old_c_string
);
1414 size_t __s
= size();
1415 _CharT
* __result
= _Data_allocate(__s
+ 1);
1416 _S_flatten(_M_tree_ptr
, __result
);
1417 __result
[__s
] = _S_eos((_CharT
*)0);
1419 _M_tree_ptr
->_M_c_string
= __result
;
1421 if ((__old_c_string
= (__GC_CONST _CharT
*)
1422 _Atomic_swap((unsigned long *)(&(_M_tree_ptr
->_M_c_string
)),
1423 (unsigned long)__result
)) != 0) {
1424 // It must have been added in the interim. Hence it had to have been
1425 // separately allocated. Deallocate the old copy, since we just
1427 destroy(__old_c_string
, __old_c_string
+ __s
+ 1);
1428 _Data_deallocate(__old_c_string
, __s
+ 1);
1434 template<class _CharT
, class _Alloc
>
1435 const _CharT
* rope
<_CharT
,_Alloc
>::replace_with_c_str() {
1436 if (0 == _M_tree_ptr
) {
1437 _S_empty_c_str
[0] = _S_eos((_CharT
*)0);
1438 return _S_empty_c_str
;
1440 __GC_CONST _CharT
* __old_c_string
= _M_tree_ptr
->_M_c_string
;
1441 if (_RopeRep::_S_leaf
== _M_tree_ptr
->_M_tag
&& 0 != __old_c_string
) {
1442 return(__old_c_string
);
1444 size_t __s
= size();
1445 _CharT
* __result
= _Data_allocate(_S_rounded_up_size(__s
));
1446 _S_flatten(_M_tree_ptr
, __result
);
1447 __result
[__s
] = _S_eos((_CharT
*)0);
1448 _M_tree_ptr
->_M_unref_nonnil();
1449 _M_tree_ptr
= _S_new_RopeLeaf(__result
, __s
, get_allocator());
1453 // Algorithm specializations. More should be added.
1455 template<class _Rope_iterator
> // was templated on CharT and Alloc
1456 void // VC++ workaround
1457 _Rope_rotate(_Rope_iterator __first
,
1458 _Rope_iterator __middle
,
1459 _Rope_iterator __last
)
1461 typedef typename
_Rope_iterator::value_type _CharT
;
1462 typedef typename
_Rope_iterator::_allocator_type _Alloc
;
1464 __stl_assert(__first
.container() == __middle
.container()
1465 && __middle
.container() == __last
.container());
1466 rope
<_CharT
,_Alloc
>& __r(__first
.container());
1467 rope
<_CharT
,_Alloc
> __prefix
= __r
.substr(0, __first
.index());
1468 rope
<_CharT
,_Alloc
> __suffix
=
1469 __r
.substr(__last
.index(), __r
.size() - __last
.index());
1470 rope
<_CharT
,_Alloc
> __part1
=
1471 __r
.substr(__middle
.index(), __last
.index() - __middle
.index());
1472 rope
<_CharT
,_Alloc
> __part2
=
1473 __r
.substr(__first
.index(), __middle
.index() - __first
.index());
1480 #if !defined(__GNUC__)
1481 // Appears to confuse g++
1482 inline void rotate(_Rope_iterator
<char,__STL_DEFAULT_ALLOCATOR(char)> __first
,
1483 _Rope_iterator
<char,__STL_DEFAULT_ALLOCATOR(char)> __middle
,
1484 _Rope_iterator
<char,__STL_DEFAULT_ALLOCATOR(char)> __last
) {
1485 _Rope_rotate(__first
, __middle
, __last
);
1490 // Probably not useful for several reasons:
1491 // - for SGIs 7.1 compiler and probably some others,
1492 // this forces lots of rope<wchar_t, ...> instantiations, creating a
1493 // code bloat and compile time problem. (Fixed in 7.2.)
1494 // - wchar_t is 4 bytes wide on most UNIX platforms, making it unattractive
1495 // for unicode strings. Unsigned short may be a better character
1498 _Rope_iterator
<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __first
,
1499 _Rope_iterator
<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __middle
,
1500 _Rope_iterator
<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __last
) {
1501 _Rope_rotate(__first
, __middle
, __last
);