2 * Copyright (c) 1996,1997
3 * Silicon Graphics Computer Systems, Inc.
8 * This material is provided "as is", with absolutely no warranty expressed
9 * or implied. Any use is at your own risk.
11 * Permission to use or copy this software for any purpose is hereby granted
12 * without fee, provided the above notices are retained on all copies.
13 * Permission to modify the code and to distribute modified code is granted,
14 * provided the above notices are retained, and a notice that the code was
15 * modified is included with the above copyright notice.
19 /* NOTE: This is an internal header file, included by other STL headers.
20 * You should not attempt to use it directly.
23 // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
24 // if necessary. Assumes path_end[leaf_index] and leaf_pos are correct.
25 // Results in a valid buf_ptr if the iterator can be legitimately
27 #ifndef _STLP_ROPEIMPL_H
28 #define _STLP_ROPEIMPL_H
30 #ifndef _STLP_INTERNAL_ROPE_H
31 # include <stl/_rope.h>
34 #ifndef _STLP_INTERNAL_CSTDIO
35 # include <stl/_cstdio.h>
38 #if !defined (_STLP_USE_NO_IOSTREAMS)
39 # ifndef _STLP_INTERNAL_OSTREAM_H
40 # include <stl/_ostream.h>
43 # ifndef _STLP_INTERNAL_ISTREAM
44 # include <stl/_istream.h>
48 #include <stl/_range_errors.h>
52 #if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
53 # define __allocator__ _Alloc
55 # define __allocator__ allocator_type
58 template<class _CharT
, class _Alloc
>
59 _Rope_iterator
<_CharT
, _Alloc
>::_Rope_iterator(rope
<_CharT
,_Alloc
>* __r
, size_t __pos
)
60 : _Rope_iterator_base
<_CharT
,_Alloc
>(__r
->_M_tree_ptr
._M_data
, __pos
),
61 _M_root_rope(__r
) { _RopeRep::_S_ref(this->_M_root
); }
63 template<class _CharT
, class _Alloc
>
64 _Rope_iterator
<_CharT
, _Alloc
>::_Rope_iterator(rope
<_CharT
,_Alloc
>& __r
, size_t __pos
):
65 _Rope_iterator_base
<_CharT
,_Alloc
>(__r
._M_tree_ptr
._M_data
, __pos
),
67 #if !defined (__DMC__)
68 _RopeRep::_S_ref(this->_M_root
); if (!(__r
.empty()))_S_setcache(*this);
70 _Rope_iterator_base
<_CharT
, _Alloc
>* __x
= this;
71 _RopeRep::_S_ref(this->_M_root
); if (!(__r
.empty()))_S_setcache(*__x
);
75 template<class _CharT
, class _Alloc
>
76 void _Rope_RopeRep
<_CharT
, _Alloc
>::_M_free_c_string() {
77 _CharT
* __cstr
= _M_c_string
;
79 size_t _p_size
= _M_size
._M_data
+ 1;
80 _STLP_STD::_Destroy_Range(__cstr
, __cstr
+ _p_size
);
81 _M_size
.deallocate(__cstr
, _p_size
);
85 // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
86 // if necessary. Assumes _M_path_end[leaf_index] and leaf_pos are correct.
87 // Results in a valid buf_ptr if the iterator can be legitimately
89 template <class _CharT
, class _Alloc
>
90 void _Rope_iterator_base
<_CharT
,_Alloc
>::_S_setbuf(
91 _Rope_iterator_base
<_CharT
,_Alloc
>& __x
) {
92 const _RopeRep
* __leaf
= __x
._M_path_end
._M_data
[__x
._M_leaf_index
];
93 size_t __leaf_pos
= __x
._M_leaf_pos
;
94 size_t __pos
= __x
._M_current_pos
;
96 switch(__leaf
->_M_tag
) {
97 case _RopeRep::_S_leaf
:
98 typedef _Rope_RopeLeaf
<_CharT
, _Alloc
> _RopeLeaf
;
99 __x
._M_buf_start
= __STATIC_CAST(const _RopeLeaf
*, __leaf
)->_M_data
;
100 __x
._M_buf_ptr
= __x
._M_buf_start
+ (__pos
- __leaf_pos
);
101 __x
._M_buf_end
= __x
._M_buf_start
+ __leaf
->_M_size
._M_data
;
103 case _RopeRep::_S_function
:
104 case _RopeRep::_S_substringfn
:
106 size_t __len
= _S_iterator_buf_len
;
107 size_t __buf_start_pos
= __leaf_pos
;
108 size_t __leaf_end
= __leaf_pos
+ __leaf
->_M_size
._M_data
;
109 typedef _Rope_RopeFunction
<_CharT
, _Alloc
> _RopeFunction
;
110 char_producer
<_CharT
>* __fn
= __STATIC_CAST(const _RopeFunction
*, __leaf
)->_M_fn
;
112 if (__buf_start_pos
+ __len
<= __pos
) {
113 __buf_start_pos
= __pos
- __len
/4;
114 if (__buf_start_pos
+ __len
> __leaf_end
) {
115 __buf_start_pos
= __leaf_end
- __len
;
118 if (__buf_start_pos
+ __len
> __leaf_end
) {
119 __len
= __leaf_end
- __buf_start_pos
;
121 (*__fn
)(__buf_start_pos
- __leaf_pos
, __len
, __x
._M_tmp_buf
._M_data
);
122 __x
._M_buf_ptr
= __x
._M_tmp_buf
._M_data
+ (__pos
- __buf_start_pos
);
123 __x
._M_buf_start
= __x
._M_tmp_buf
._M_data
;
124 __x
._M_buf_end
= __x
._M_tmp_buf
._M_data
+ __len
;
133 // Set path and buffer inside a rope iterator. We assume that
134 // pos and root are already set.
135 template <class _CharT
, class _Alloc
>
136 void _Rope_iterator_base
<_CharT
,_Alloc
>::_S_setcache(
137 _Rope_iterator_base
<_CharT
,_Alloc
>& __x
) {
138 const _RopeRep
* __path
[_RopeRep::_S_max_rope_depth
+1];
139 const _RopeRep
* __curr_rope
;
140 int __curr_depth
= -1; /* index into path */
141 size_t __curr_start_pos
= 0;
142 size_t __pos
= __x
._M_current_pos
;
143 unsigned char __dirns
= 0; // Bit vector marking right turns in the path
145 _STLP_ASSERT(__pos
<= __x
._M_root
->_M_size
._M_data
)
146 if (__pos
>= __x
._M_root
->_M_size
._M_data
) {
150 __curr_rope
= __x
._M_root
;
151 if (0 != __curr_rope
->_M_c_string
) {
152 /* Treat the root as a leaf. */
153 __x
._M_buf_start
= __curr_rope
->_M_c_string
;
154 __x
._M_buf_end
= __curr_rope
->_M_c_string
+ __curr_rope
->_M_size
._M_data
;
155 __x
._M_buf_ptr
= __curr_rope
->_M_c_string
+ __pos
;
156 __x
._M_path_end
._M_data
[0] = __curr_rope
;
157 __x
._M_leaf_index
= 0;
163 _STLP_ASSERT(__curr_depth
<= _RopeRep::_S_max_rope_depth
)
164 __path
[__curr_depth
] = __curr_rope
;
165 switch(__curr_rope
->_M_tag
) {
166 case _RopeRep::_S_leaf
:
167 case _RopeRep::_S_function
:
168 case _RopeRep::_S_substringfn
:
169 __x
._M_leaf_pos
= __curr_start_pos
;
171 case _RopeRep::_S_concat
:
173 const _RopeConcat
* __c
= __STATIC_CAST(const _RopeConcat
*, __curr_rope
);
174 _RopeRep
* __left
= __c
->_M_left
;
175 size_t __left_len
= __left
->_M_size
._M_data
;
178 if (__pos
>= __curr_start_pos
+ __left_len
) {
180 __curr_rope
= __c
->_M_right
;
181 __curr_start_pos
+= __left_len
;
183 __curr_rope
= __left
;
190 // Copy last section of path into _M_path_end.
193 int __j
= __curr_depth
+ 1 - _S_path_cache_len
;
195 if (__j
< 0) __j
= 0;
196 while (__j
<= __curr_depth
) {
197 __x
._M_path_end
._M_data
[++__i
] = __path
[__j
++];
199 __x
._M_leaf_index
= __i
;
201 __x
._M_path_directions
= __dirns
;
205 // Specialized version of the above. Assumes that
206 // the path cache is valid for the previous position.
207 template <class _CharT
, class _Alloc
>
208 void _Rope_iterator_base
<_CharT
,_Alloc
>::_S_setcache_for_incr(
209 _Rope_iterator_base
<_CharT
,_Alloc
>& __x
) {
210 int __current_index
= __x
._M_leaf_index
;
211 const _RopeRep
* __current_node
= __x
._M_path_end
._M_data
[__current_index
];
212 size_t __len
= __current_node
->_M_size
._M_data
;
213 size_t __node_start_pos
= __x
._M_leaf_pos
;
214 unsigned char __dirns
= __x
._M_path_directions
;
215 const _RopeConcat
* __c
;
217 _STLP_ASSERT(__x
._M_current_pos
<= __x
._M_root
->_M_size
._M_data
)
218 if (__x
._M_current_pos
- __node_start_pos
< __len
) {
219 /* More stuff in this leaf, we just didn't cache it. */
223 _STLP_ASSERT(__node_start_pos
+ __len
== __x
._M_current_pos
)
224 // node_start_pos is starting position of last_node.
225 while (--__current_index
>= 0) {
226 if (!(__dirns
& 1) /* Path turned left */)
228 __current_node
= __x
._M_path_end
._M_data
[__current_index
];
229 __c
= __STATIC_CAST(const _RopeConcat
*, __current_node
);
230 // Otherwise we were in the right child. Thus we should pop
231 // the concatenation node.
232 __node_start_pos
-= __c
->_M_left
->_M_size
._M_data
;
235 if (__current_index
< 0) {
236 // We underflowed the cache. Punt.
240 __current_node
= __x
._M_path_end
._M_data
[__current_index
];
241 __c
= __STATIC_CAST(const _RopeConcat
*, __current_node
);
242 // current_node is a concatenation node. We are positioned on the first
243 // character in its right child.
244 // node_start_pos is starting position of current_node.
245 __node_start_pos
+= __c
->_M_left
->_M_size
._M_data
;
246 __current_node
= __c
->_M_right
;
247 __x
._M_path_end
._M_data
[++__current_index
] = __current_node
;
249 while (_RopeRep::_S_concat
== __current_node
->_M_tag
) {
251 if (_S_path_cache_len
== __current_index
) {
253 for (__i
= 0; __i
< _S_path_cache_len
-1; ++__i
) {
254 __x
._M_path_end
._M_data
[__i
] = __x
._M_path_end
._M_data
[__i
+1];
258 __current_node
= __STATIC_CAST(const _RopeConcat
*, __current_node
)->_M_left
;
259 __x
._M_path_end
._M_data
[__current_index
] = __current_node
;
261 // node_start_pos is unchanged.
263 __x
._M_leaf_index
= __current_index
;
264 __x
._M_leaf_pos
= __node_start_pos
;
265 __x
._M_path_directions
= __dirns
;
269 template <class _CharT
, class _Alloc
>
270 void _Rope_iterator_base
<_CharT
,_Alloc
>::_M_incr(size_t __n
) {
271 _M_current_pos
+= __n
;
272 if (0 != _M_buf_ptr
) {
273 size_t __chars_left
= _M_buf_end
- _M_buf_ptr
;
274 if (__chars_left
> __n
) {
276 } else if (__chars_left
== __n
) {
278 _S_setcache_for_incr(*this);
285 template <class _CharT
, class _Alloc
>
286 void _Rope_iterator_base
<_CharT
,_Alloc
>::_M_decr(size_t __n
) {
287 if (0 != _M_buf_ptr
) {
288 size_t __chars_left
= _M_buf_ptr
- _M_buf_start
;
289 if (__chars_left
>= __n
) {
295 _M_current_pos
-= __n
;
298 template <class _CharT
, class _Alloc
>
299 void _Rope_iterator
<_CharT
,_Alloc
>::_M_check() {
300 if (_M_root_rope
->_M_tree_ptr
._M_data
!= this->_M_root
) {
301 // _Rope was modified. Get things fixed up.
302 _RopeRep::_S_unref(this->_M_root
);
303 this->_M_root
= _M_root_rope
->_M_tree_ptr
._M_data
;
304 _RopeRep::_S_ref(this->_M_root
);
305 this->_M_buf_ptr
= 0;
309 // There are several reasons for not doing this with virtual destructors
310 // and a class specific delete operator:
311 // - A class specific delete operator can't easily get access to
312 // allocator instances if we need them.
313 // - Any virtual function would need a 4 or byte vtable pointer;
314 // this only requires a one byte tag per object.
315 template <class _CharT
, class _Alloc
>
316 void _Rope_RopeRep
<_CharT
,_Alloc
>::_M_free_tree() {
320 typedef _Rope_RopeLeaf
<_CharT
, _Alloc
> _RopeLeaf
;
321 _RopeLeaf
* __l
= __STATIC_CAST(_RopeLeaf
*, this);
322 _STLP_STD::_Destroy(__l
); // ->_Rope_RopeLeaf<_CharT,_Alloc>::~_Rope_RopeLeaf();
323 _STLP_CREATE_ALLOCATOR(allocator_type
,(const allocator_type
&)_M_size
,
324 _RopeLeaf
).deallocate(__l
, 1);
329 typedef _Rope_RopeConcatenation
<_CharT
, _Alloc
> _RopeConcatenation
;
330 _RopeConcatenation
* __c
= __STATIC_CAST(_RopeConcatenation
*, this);
331 _STLP_STD::_Destroy(__c
);
332 _STLP_CREATE_ALLOCATOR(allocator_type
,(const allocator_type
&)_M_size
,
333 _RopeConcatenation
).deallocate(__c
, 1);
338 typedef _Rope_RopeFunction
<_CharT
, _Alloc
> _RopeFunction
;
339 _RopeFunction
* __f
= __STATIC_CAST(_RopeFunction
*, this);
340 _STLP_STD::_Destroy(__f
);
341 _STLP_CREATE_ALLOCATOR(allocator_type
, (const allocator_type
&)_M_size
,
342 _RopeFunction
).deallocate(__f
, 1);
347 typedef _Rope_RopeSubstring
<_CharT
, _Alloc
> _RopeSubstring
;
348 _RopeSubstring
* __rss
= __STATIC_CAST(_RopeSubstring
*, this);
349 _STLP_STD::_Destroy(__rss
);
350 _STLP_CREATE_ALLOCATOR(allocator_type
, (const allocator_type
&)_M_size
,
351 _RopeSubstring
).deallocate(__rss
, 1);
357 # if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
358 # define __RopeLeaf__ _Rope_RopeLeaf<_CharT,_Alloc>
359 # define __RopeRep__ _Rope_RopeRep<_CharT,_Alloc>
360 # define _RopeLeaf _Rope_RopeLeaf<_CharT,_Alloc>
361 # define _RopeRep _Rope_RopeRep<_CharT,_Alloc>
362 # define size_type size_t
364 # define __RopeLeaf__ _STLP_TYPENAME_ON_RETURN_TYPE rope<_CharT,_Alloc>::_RopeLeaf
365 # define __RopeRep__ _STLP_TYPENAME_ON_RETURN_TYPE rope<_CharT,_Alloc>::_RopeRep
368 template <class _CharT
, class _Alloc
>
369 void rope
<_CharT
, _Alloc
>::_M_throw_out_of_range() const {
370 __stl_throw_out_of_range("rope");
373 // Concatenate a C string onto a leaf rope by copying the rope data.
374 // Used for short ropes.
375 template <class _CharT
, class _Alloc
>
377 rope
<_CharT
,_Alloc
>::_S_leaf_concat_char_iter (
378 _RopeLeaf
* __r
, const _CharT
* __iter
, size_t __len
) {
379 size_t __old_len
= __r
->_M_size
._M_data
;
380 _CharT
* __new_data
= __r
->_M_size
.allocate(_S_rounded_up_size(__old_len
+ __len
));
383 _STLP_PRIV
__ucopy_n(__r
->_M_data
, __old_len
, __new_data
);
384 _STLP_PRIV
__ucopy_n(__iter
, __len
, __new_data
+ __old_len
);
385 _S_construct_null(__new_data
+ __old_len
+ __len
);
387 __result
= _S_new_RopeLeaf(__new_data
, __old_len
+ __len
, __r
->get_allocator());
389 _STLP_UNWIND(_RopeRep::_S_free_string(__new_data
, __old_len
+ __len
,
390 __r
->get_allocator()))
394 template <class _CharT
, class _Alloc
>
395 void _Terminate_RopeLeaf(_Rope_RopeLeaf
<_CharT
,_Alloc
> *__r
,
396 size_t __size
, const __true_type
& /*basic char type*/) {
397 _S_construct_null(__r
->_M_data
+ __size
);
398 _STLP_ASSERT(__r
->_M_c_string
== __r
->_M_data
)
401 template <class _CharT
, class _Alloc
>
402 void _Terminate_RopeLeaf(_Rope_RopeLeaf
<_CharT
,_Alloc
> *__r
,
403 size_t, const __false_type
& /*basic char type*/) {
404 if (__r
->_M_c_string
!= __r
->_M_data
&& 0 != __r
->_M_c_string
) {
405 __r
->_M_free_c_string();
406 __r
->_M_c_string
= 0;
410 // As above, but it's OK to clobber original if refcount is 1
411 template <class _CharT
, class _Alloc
>
413 rope
<_CharT
,_Alloc
>::_S_destr_leaf_concat_char_iter (_RopeLeaf
* __r
, const _CharT
* __iter
, size_t __len
) {
414 //_STLP_ASSERT(__r->_M_ref_count >= 1)
415 if ( /* __r->_M_ref_count > 1 */ __r
->_M_incr() > 2 ) { // - ptr
416 __r
->_M_decr(); // - ptr
417 return _S_leaf_concat_char_iter(__r
, __iter
, __len
);
419 __r
->_M_decr(); // - ptr, __r->_M_ref_count == 1 or 0
420 size_t __old_len
= __r
->_M_size
._M_data
;
421 if (_S_rounded_up_size(__old_len
) == _S_rounded_up_size(__old_len
+ __len
)) {
422 // The space has been partially initialized for the standard
423 // character types. But that doesn't matter for those types.
424 _STLP_PRIV
__ucopy_n(__iter
, __len
, __r
->_M_data
+ __old_len
);
425 _Terminate_RopeLeaf(__r
, __old_len
+ __len
, _IsBasicCharType());
426 __r
->_M_size
._M_data
= __old_len
+ __len
;
427 // _STLP_ASSERT(__r->_M_ref_count == 1)
428 // __r->_M_ref_count = 2;
429 __r
->_M_incr(); // i.e. __r->_M_ref_count = 2
432 _RopeLeaf
* __result
= _S_leaf_concat_char_iter(__r
, __iter
, __len
);
433 //_STLP_ASSERT(__result->_M_ref_count == 1)
438 // Assumes left and right are not 0.
439 // Does not increment (nor decrement on exception) child reference counts.
440 // Result has ref count 1.
441 template <class _CharT
, class _Alloc
>
443 rope
<_CharT
,_Alloc
>::_S_tree_concat (_RopeRep
* __left
, _RopeRep
* __right
) {
444 _RopeConcatenation
* __result
=
445 _S_new_RopeConcatenation(__left
, __right
, __left
->get_allocator());
446 size_t __depth
= __result
->_M_depth
;
448 _STLP_ASSERT(__left
->get_allocator() == __right
->get_allocator())
449 if (__depth
> 20 && (__result
->_M_size
._M_data
< 1000 ||
450 __depth
> _RopeRep::_S_max_rope_depth
)) {
451 _RopeRep
* __balanced
;
454 __balanced
= _S_balance(__result
);
455 // _STLP_ASSERT(__result == __balanced ||
456 // 1 == __result->_M_ref_count &&
457 // 1 == __balanced->_M_ref_count)
458 __result
->_M_unref_nonnil();
460 _STLP_UNWIND((_STLP_CREATE_ALLOCATOR(allocator_type
,(allocator_type
&)__left
->_M_size
,
461 _RopeConcatenation
).deallocate(__result
,1)))
462 // In case of exception, we need to deallocate
463 // otherwise dangling result node. But caller
464 // still owns its children. Thus unref is
472 template <class _CharT
, class _Alloc
>
474 rope
<_CharT
,_Alloc
>::_S_concat_char_iter (_RopeRep
* __r
,
475 const _CharT
*__s
, size_t __slen
) {
482 return _S_RopeLeaf_from_unowned_char_ptr(__s
, __slen
, __r
->get_allocator());
483 if (_RopeRep::_S_leaf
== __r
->_M_tag
&&
484 __r
->_M_size
._M_data
+ __slen
<= _S_copy_max
) {
485 __result
= _S_leaf_concat_char_iter((_RopeLeaf
*)__r
, __s
, __slen
);
486 // _STLP_ASSERT(1 == __result->_M_ref_count)
489 if (_RopeRep::_S_concat
== __r
->_M_tag
&&
490 _RopeRep::_S_leaf
== ((_RopeConcatenation
*)__r
)->_M_right
->_M_tag
) {
491 _RopeLeaf
* __right
= (_RopeLeaf
* )(((_RopeConcatenation
* )__r
)->_M_right
);
492 if (__right
->_M_size
._M_data
+ __slen
<= _S_copy_max
) {
493 _RopeRep
* __left
= ((_RopeConcatenation
*)__r
)->_M_left
;
494 _RopeRep
* __nright
= _S_leaf_concat_char_iter((_RopeLeaf
*)__right
, __s
, __slen
);
495 __left
->_M_ref_nonnil();
497 __result
= _S_tree_concat(__left
, __nright
);
499 _STLP_UNWIND(_S_unref(__left
); _S_unref(__nright
))
500 // _STLP_ASSERT(1 == __result->_M_ref_count)
505 _S_RopeLeaf_from_unowned_char_ptr(__s
, __slen
, __r
->get_allocator());
507 __r
->_M_ref_nonnil();
508 __result
= _S_tree_concat(__r
, __nright
);
510 _STLP_UNWIND(_S_unref(__r
); _S_unref(__nright
))
511 // _STLP_ASSERT(1 == __result->_M_ref_count)
515 template <class _CharT
, class _Alloc
>
517 rope
<_CharT
,_Alloc
>::_S_destr_concat_char_iter(
518 _RopeRep
* __r
, const _CharT
* __s
, size_t __slen
) {
521 return _S_RopeLeaf_from_unowned_char_ptr(__s
, __slen
,
522 __r
->get_allocator());
523 // size_t __count = __r->_M_ref_count;
524 size_t __orig_size
= __r
->_M_size
._M_data
;
525 // _STLP_ASSERT(__count >= 1)
526 if ( /* __count > 1 */ __r
->_M_incr() > 2 ) {
528 return _S_concat_char_iter(__r
, __s
, __slen
);
534 if (__orig_size
+ __slen
<= _S_copy_max
&& _RopeRep::_S_leaf
== __r
->_M_tag
) {
535 return _S_destr_leaf_concat_char_iter((_RopeLeaf
*)__r
, __s
, __slen
);
537 if (_RopeRep::_S_concat
== __r
->_M_tag
) {
538 _RopeLeaf
* __right
= __STATIC_CAST(_RopeLeaf
*, __STATIC_CAST(_RopeConcatenation
*, __r
)->_M_right
);
539 if (_RopeRep::_S_leaf
== __right
->_M_tag
&&
540 __right
->_M_size
._M_data
+ __slen
<= _S_copy_max
) {
541 _RopeRep
* __new_right
= _S_destr_leaf_concat_char_iter(__right
, __s
, __slen
);
542 if (__right
== __new_right
) {
543 // _STLP_ASSERT(__new_right->_M_ref_count == 2)
544 // __new_right->_M_ref_count = 1;
545 __new_right
->_M_decr();
547 // _STLP_ASSERT(__new_right->_M_ref_count >= 1)
548 __right
->_M_unref_nonnil();
550 // _STLP_ASSERT(__r->_M_ref_count == 1)
551 // __r->_M_ref_count = 2; // One more than before.
553 __STATIC_CAST(_RopeConcatenation
*, __r
)->_M_right
= __new_right
;
554 // E.Musser : moved below
555 // __r->_M_size._M_data = __orig_size + __slen;
556 if (0 != __r
->_M_c_string
) {
557 __r
->_M_free_c_string();
558 __r
->_M_c_string
= 0;
560 __r
->_M_size
._M_data
= __orig_size
+ __slen
;
565 _S_RopeLeaf_from_unowned_char_ptr(__s
, __slen
, __r
->get_allocator());
566 __r
->_M_ref_nonnil();
568 __result
= _S_tree_concat(__r
, __right
);
570 _STLP_UNWIND(_S_unref(__r
); _S_unref(__right
))
571 // _STLP_ASSERT(1 == __result->_M_ref_count)
575 template <class _CharT
, class _Alloc
>
577 rope
<_CharT
,_Alloc
>::_S_concat_rep(_RopeRep
* __left
, _RopeRep
* __right
) {
583 __left
->_M_ref_nonnil();
586 if (_RopeRep::_S_leaf
== __right
->_M_tag
) {
587 if (_RopeRep::_S_leaf
== __left
->_M_tag
) {
588 if (__right
->_M_size
._M_data
+ __left
->_M_size
._M_data
<= _S_copy_max
) {
589 return _S_leaf_concat_char_iter(__STATIC_CAST(_RopeLeaf
*, __left
),
590 __STATIC_CAST(_RopeLeaf
*, __right
)->_M_data
,
591 __right
->_M_size
._M_data
);
593 } else if (_RopeRep::_S_concat
== __left
->_M_tag
&&
594 _RopeRep::_S_leaf
== __STATIC_CAST(_RopeConcatenation
*, __left
)->_M_right
->_M_tag
) {
595 _RopeLeaf
* __leftright
=
596 __STATIC_CAST(_RopeLeaf
*, __STATIC_CAST(_RopeConcatenation
*, __left
)->_M_right
);
597 if (__leftright
->_M_size
._M_data
+ __right
->_M_size
._M_data
<= _S_copy_max
) {
598 _RopeRep
* __leftleft
= __STATIC_CAST(_RopeConcatenation
*, __left
)->_M_left
;
599 _RopeRep
* __rest
= _S_leaf_concat_char_iter(__leftright
,
600 __STATIC_CAST(_RopeLeaf
*, __right
)->_M_data
,
601 __right
->_M_size
._M_data
);
602 __leftleft
->_M_ref_nonnil();
604 return _S_tree_concat(__leftleft
, __rest
);
606 _STLP_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 _STLP_UNWIND(_S_unref(__left
); _S_unref(__right
))
616 _STLP_RET_AFTER_THROW(0)
619 template <class _CharT
, class _Alloc
>
621 rope
<_CharT
,_Alloc
>::_S_substring(_RopeRep
* __base
,
622 size_t __start
, size_t __endp1
) {
623 if (0 == __base
) return 0;
624 size_t __len
= __base
->_M_size
._M_data
;
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
= __STATIC_CAST(_RopeConcatenation
*, __base
);
642 _RopeRep
* __left
= __c
->_M_left
;
643 _RopeRep
* __right
= __c
->_M_right
;
644 size_t __left_len
= __left
->_M_size
._M_data
;
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(_S_substring(__left
, __start
, __left_len
));
654 _Self_destruct_ptr
__right_result(_S_substring(__right
, 0, __endp1
- __left_len
));
655 _STLP_MPWFIX_TRY
//*TY 06/01/2000 - mpw forgets to call dtor on __left_result and __right_result without this try block
656 __result
= _S_concat_rep(__left_result
, __right_result
);
657 // _STLP_ASSERT(1 == __result->_M_ref_count)
659 _STLP_MPWFIX_CATCH
//*TY 06/01/2000 -
661 case _RopeRep::_S_leaf
:
663 _RopeLeaf
* __l
= __STATIC_CAST(_RopeLeaf
*, __base
);
666 if (__start
>= __adj_endp1
) return 0;
667 __result_len
= __adj_endp1
- __start
;
668 if (__result_len
> __lazy_threshold
) goto lazy
;
669 const _CharT
* __section
= __l
->_M_data
+ __start
;
670 // We should sometimes create substring node instead.
671 __result
= _S_RopeLeaf_from_unowned_char_ptr(__section
, __result_len
,
672 __base
->get_allocator());
675 case _RopeRep::_S_substringfn
:
676 // Avoid introducing multiple layers of substring nodes.
678 _RopeSubstring
* __old
= __STATIC_CAST(_RopeSubstring
*, __base
);
680 if (__start
>= __adj_endp1
) return 0;
681 __result_len
= __adj_endp1
- __start
;
682 if (__result_len
> __lazy_threshold
) {
683 _RopeSubstring
* __result
= _S_new_RopeSubstring(__old
->_M_base
,
684 __start
+ __old
->_M_start
,
685 __adj_endp1
- __start
,
686 __base
->get_allocator());
688 } // *** else fall through: ***
690 case _RopeRep::_S_function
:
692 _RopeFunction
* __f
= __STATIC_CAST(_RopeFunction
*, __base
);
693 if (__start
>= __adj_endp1
) return 0;
694 size_t __result_len
= __adj_endp1
- __start
;
696 if (__result_len
> __lazy_threshold
) goto lazy
;
697 _CharT
* __section
= __base
->_M_size
.allocate(_S_rounded_up_size(__result_len
));
699 (*(__f
->_M_fn
))(__start
, __result_len
, __section
);
701 _STLP_UNWIND(_RopeRep::_S_free_string(__section
,
702 __result_len
, __base
->get_allocator()))
703 _S_construct_null(__section
+ __result_len
);
704 return _S_new_RopeLeaf(__section
, __result_len
,
705 __base
->get_allocator());
712 // Create substring node.
713 return _S_new_RopeSubstring(__base
, __start
, __adj_endp1
- __start
,
714 __base
->get_allocator());
718 template<class _CharT
>
719 class _Rope_flatten_char_consumer
: public _Rope_char_consumer
<_CharT
> {
723 _Rope_flatten_char_consumer(_CharT
* __buffer
) {
724 _M_buf_ptr
= __buffer
;
726 ~_Rope_flatten_char_consumer() {}
727 bool operator() (const _CharT
* __leaf
, size_t __n
) {
728 _STLP_PRIV
__ucopy_n(__leaf
, __n
, _M_buf_ptr
);
734 template<class _CharT
>
735 class _Rope_find_char_char_consumer
: public _Rope_char_consumer
<_CharT
> {
739 size_t _M_count
; // Number of nonmatching characters
740 _Rope_find_char_char_consumer(_CharT __p
)
741 : _M_pattern(__p
), _M_count(0) {}
742 ~_Rope_find_char_char_consumer() {}
743 bool operator() (const _CharT
* __leaf
, size_t __n
) {
745 for (__i
= 0; __i
< __n
; ++__i
) {
746 if (__leaf
[__i
] == _M_pattern
) {
747 _M_count
+= __i
; return false;
750 _M_count
+= __n
; return true;
754 #if !defined (_STLP_USE_NO_IOSTREAMS)
755 template<class _CharT
, class _Traits
>
756 // Here _CharT is both the stream and rope character type.
757 class _Rope_insert_char_consumer
: public _Rope_char_consumer
<_CharT
> {
759 typedef basic_ostream
<_CharT
,_Traits
> _Insert_ostream
;
760 typedef _Rope_insert_char_consumer
<_CharT
,_Traits
> _Self
;
761 _Insert_ostream
& _M_o
;
763 //explicitely defined as private to avoid warnings:
764 _Self
& operator = (_Self
const&);
766 _Rope_insert_char_consumer(_Insert_ostream
& __writer
)
768 ~_Rope_insert_char_consumer() {}
769 // Caller is presumed to own the ostream
770 bool operator() (const _CharT
* __leaf
, size_t __n
);
771 // Returns true to continue traversal.
774 template<class _CharT
, class _Traits
>
775 bool _Rope_insert_char_consumer
<_CharT
, _Traits
>::operator()
776 (const _CharT
* __leaf
, size_t __n
) {
778 // We assume that formatting is set up correctly for each element.
779 for (__i
= 0; __i
< __n
; ++__i
) _M_o
.put(__leaf
[__i
]);
782 #endif /* !_STLP_USE_NO_IOSTREAMS */
784 template <class _CharT
, class _Alloc
, class _CharConsumer
>
785 bool _S_apply_to_pieces(_CharConsumer
& __c
,
786 _Rope_RopeRep
<_CharT
, _Alloc
> * __r
,
787 size_t __begin
, size_t __end
) {
788 typedef _Rope_RopeRep
<_CharT
, _Alloc
> _RopeRep
;
789 typedef _Rope_RopeConcatenation
<_CharT
,_Alloc
> _RopeConcatenation
;
790 typedef _Rope_RopeLeaf
<_CharT
,_Alloc
> _RopeLeaf
;
791 typedef _Rope_RopeFunction
<_CharT
,_Alloc
> _RopeFunction
;
793 if (0 == __r
) return true;
794 switch(__r
->_M_tag
) {
795 case _RopeRep::_S_concat
:
797 _RopeConcatenation
* __conc
= __STATIC_CAST(_RopeConcatenation
*, __r
);
798 _RopeRep
* __left
= __conc
->_M_left
;
799 size_t __left_len
= __left
->_M_size
._M_data
;
800 if (__begin
< __left_len
) {
801 size_t __left_end
= (min
) (__left_len
, __end
);
802 if (!_S_apply_to_pieces(__c
, __left
, __begin
, __left_end
))
805 if (__end
> __left_len
) {
806 _RopeRep
* __right
= __conc
->_M_right
;
807 size_t __right_start
= (max
)(__left_len
, __begin
);
808 if (!_S_apply_to_pieces(__c
, __right
,
809 __right_start
- __left_len
,
810 __end
- __left_len
)) {
816 case _RopeRep::_S_leaf
:
818 _RopeLeaf
* __l
= __STATIC_CAST(_RopeLeaf
*, __r
);
819 return __c(__l
->_M_data
+ __begin
, __end
- __begin
);
821 case _RopeRep::_S_function
:
822 case _RopeRep::_S_substringfn
:
824 _RopeFunction
* __f
= __STATIC_CAST(_RopeFunction
*, __r
);
825 size_t __len
= __end
- __begin
;
827 _CharT
* __buffer
= __r
->get_allocator().allocate(__len
);
829 (*(__f
->_M_fn
))(__begin
, __len
, __buffer
);
830 __result
= __c(__buffer
, __len
);
831 __r
->get_allocator().deallocate(__buffer
, __len
);
833 _STLP_UNWIND((__r
->get_allocator().deallocate(__buffer
, __len
)))
843 #if !defined (_STLP_USE_NO_IOSTREAMS)
844 template<class _CharT
, class _Traits
>
845 inline void _Rope_fill(basic_ostream
<_CharT
, _Traits
>& __o
, streamsize __n
) {
846 char __f
= __o
.fill();
847 for (streamsize __i
= 0; __i
< __n
; ++__i
) __o
.put(__f
);
850 template<class _CharT
, class _Traits
, class _Alloc
>
851 basic_ostream
<_CharT
, _Traits
>& _S_io_get(basic_ostream
<_CharT
, _Traits
>& __o
,
852 const rope
<_CharT
, _Alloc
>& __r
, const __true_type
& /*_IsBasicCharType*/) {
853 streamsize __w
= __o
.width();
854 const bool __left
= (__o
.flags() & ios::left
) != 0;
855 size_t __rope_len
= __r
.size();
856 _Rope_insert_char_consumer
<_CharT
, _Traits
> __c(__o
);
858 const bool __need_pad
= (((sizeof(streamsize
) > sizeof(size_t)) && (__STATIC_CAST(streamsize
, __rope_len
) < __w
)) ||
859 ((sizeof(streamsize
) <= sizeof(size_t)) && (__rope_len
< __STATIC_CAST(size_t, __w
))));
860 streamsize __pad_len
= __need_pad
? __w
- __rope_len
: 0;
862 if (!__left
&& __pad_len
> 0) {
863 _Rope_fill(__o
, __pad_len
);
865 __r
.apply_to_pieces(0, __rope_len
, __c
);
866 if (__left
&& __pad_len
> 0) {
867 _Rope_fill(__o
, __pad_len
);
872 template<class _CharT
, class _Traits
, class _Alloc
>
873 basic_ostream
<_CharT
, _Traits
>& _S_io_get(basic_ostream
<_CharT
, _Traits
>& __o
,
874 const rope
<_CharT
, _Alloc
>& __r
, const __false_type
& /*_IsBasicCharType*/) {
875 streamsize __w
= __o
.width();
876 size_t __rope_len
= __r
.size();
877 _Rope_insert_char_consumer
<_CharT
, _Traits
> __c(__o
);
879 __o
.width(__w
/__rope_len
);
881 __r
.apply_to_pieces(0, __rope_len
, __c
);
884 _STLP_UNWIND(__o
.width(__w
))
888 template<class _CharT
, class _Traits
, class _Alloc
>
889 basic_ostream
<_CharT
, _Traits
>& operator<<(basic_ostream
<_CharT
, _Traits
>& __o
,
890 const rope
<_CharT
, _Alloc
>& __r
) {
891 typedef typename _IsIntegral
<_CharT
>::_Ret _Char_Is_Integral
;
892 return _S_io_get(__o
, __r
, _Char_Is_Integral());
894 #endif /* NO_IOSTREAMS */
896 template <class _CharT
, class _Alloc
>
897 _CharT
* rope
<_CharT
,_Alloc
>::_S_flatten(_RopeRep
* __r
,
898 size_t __start
, size_t __len
,
900 _Rope_flatten_char_consumer
<_CharT
> __c(__buffer
);
901 _S_apply_to_pieces(__c
, __r
, __start
, __start
+ __len
);
902 return(__buffer
+ __len
);
905 template <class _CharT
, class _Alloc
>
906 size_t rope
<_CharT
,_Alloc
>::find(_CharT __pattern
, size_t __start
) const {
907 _Rope_find_char_char_consumer
<_CharT
> __c(__pattern
);
908 _S_apply_to_pieces(__c
, _M_tree_ptr
._M_data
, __start
, size());
909 size_type __result_pos
= __start
+ __c
._M_count
;
910 #ifndef _STLP_OLD_ROPE_SEMANTICS
911 if (__result_pos
== size()) __result_pos
= npos
;
916 template <class _CharT
, class _Alloc
>
918 rope
<_CharT
,_Alloc
>::_S_flatten(_Rope_RopeRep
<_CharT
, _Alloc
>* __r
, _CharT
* __buffer
) {
919 if (0 == __r
) return __buffer
;
920 switch(__r
->_M_tag
) {
921 case _RopeRep::_S_concat
:
923 _RopeConcatenation
* __c
= __STATIC_CAST(_RopeConcatenation
*, __r
);
924 _RopeRep
* __left
= __c
->_M_left
;
925 _RopeRep
* __right
= __c
->_M_right
;
926 _CharT
* __rest
= _S_flatten(__left
, __buffer
);
927 return _S_flatten(__right
, __rest
);
929 case _RopeRep::_S_leaf
:
931 _RopeLeaf
* __l
= __STATIC_CAST(_RopeLeaf
*, __r
);
932 return _STLP_PRIV
__ucopy_n(__l
->_M_data
, __l
->_M_size
._M_data
, __buffer
).second
;
934 case _RopeRep::_S_function
:
935 case _RopeRep::_S_substringfn
:
936 // We dont yet do anything with substring nodes.
937 // This needs to be fixed before ropefiles will work well.
939 _RopeFunction
* __f
= __STATIC_CAST(_RopeFunction
*, __r
);
940 (*(__f
->_M_fn
))(0, __f
->_M_size
._M_data
, __buffer
);
941 return __buffer
+ __f
->_M_size
._M_data
;
951 // This needs work for _CharT != char
952 template <class _CharT
, class _Alloc
>
953 void rope
<_CharT
,_Alloc
>::_S_dump(_RopeRep
* __r
, int __indent
) {
954 for (int __i
= 0; __i
< __indent
; ++__i
) putchar(' ');
956 printf("NULL\n"); return;
958 if (_RopeRep::_S_concat
== __r
->_M_tag
) {
959 _RopeConcatenation
* __c
= __STATIC_CAST(_RopeConcatenation
*, __r
);
960 _RopeRep
* __left
= __c
->_M_left
;
961 _RopeRep
* __right
= __c
->_M_right
;
962 printf("Concatenation %p (rc = %ld, depth = %d, len = %ld, %s balanced)\n",
963 __r
, __r
->_M_ref_count
, __r
->_M_depth
, __r
->_M_size
._M_data
,
964 __r
->_M_is_balanced
? "" : "not");
965 _S_dump(__left
, __indent
+ 2);
966 _S_dump(__right
, __indent
+ 2);
972 switch (__r
->_M_tag
) {
973 case _RopeRep::_S_leaf
:
976 case _RopeRep::_S_function
:
979 case _RopeRep::_S_substringfn
:
980 __kind
= "Function representing substring";
983 __kind
= "(corrupted kind field!)";
985 printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
986 __kind
, __r
, __r
->_M_ref_count
, __r
->_M_depth
, __r
->_M_size
._M_data
);
987 if (sizeof(_CharT
) == 1) {
988 const int __max_len
= 40;
989 _Self_destruct_ptr
__prefix(_S_substring(__r
, 0, __max_len
));
990 _CharT __buffer
[__max_len
+ 1];
991 bool __too_big
= __r
->_M_size
._M_data
> __prefix
->_M_size
._M_data
;
993 _S_flatten(__prefix
, __buffer
);
994 __buffer
[__prefix
->_M_size
._M_data
] = _STLP_DEFAULT_CONSTRUCTED(_CharT
);
995 printf("%s%s\n", (char*)__buffer
, __too_big
? "...\n" : "\n");
1001 #endif /* _STLP_DEBUG */
1003 # define __ROPE_TABLE_BODY = { \
1004 /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21, \
1005 /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377, \
1006 /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181, \
1007 /* 18 */6765ul, /* 19 */10946ul, /* 20 */17711ul, /* 21 */28657ul, /* 22 */46368ul, \
1008 /* 23 */75025ul, /* 24 */121393ul, /* 25 */196418ul, /* 26 */317811ul, \
1009 /* 27 */514229ul, /* 28 */832040ul, /* 29 */1346269ul, /* 30 */2178309ul, \
1010 /* 31 */3524578ul, /* 32 */5702887ul, /* 33 */9227465ul, /* 34 */14930352ul, \
1011 /* 35 */24157817ul, /* 36 */39088169ul, /* 37 */63245986ul, /* 38 */102334155ul, \
1012 /* 39 */165580141ul, /* 40 */267914296ul, /* 41 */433494437ul, \
1013 /* 42 */701408733ul, /* 43 */1134903170ul, /* 44 */1836311903ul, \
1014 /* 45 */2971215073ul }
1016 template <class _CharT
, class _Alloc
>
1018 rope
<_CharT
,_Alloc
>::_S_min_len
[__ROPE_DEPTH_SIZE
] __ROPE_TABLE_BODY
;
1019 # undef __ROPE_DEPTH_SIZE
1020 # undef __ROPE_MAX_DEPTH
1021 # undef __ROPE_TABLE_BODY
1023 // These are Fibonacci numbers < 2**32.
1025 template <class _CharT
, class _Alloc
>
1026 __RopeRep__
* rope
<_CharT
,_Alloc
>::_S_balance(_RopeRep
* __r
) {
1027 _RopeRep
* __forest
[_RopeRep::_S_max_rope_depth
+ 1] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1028 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1030 _RopeRep
* __result
= 0;
1033 // The concatenation of forest in descending order is equal to __r.
1034 // __forest[__i]._M_size._M_data >= _S_min_len[__i]
1035 // __forest[__i]._M_depth = __i
1036 // References from forest are included in refcount.
1039 _S_add_to_forest(__r
, __forest
);
1040 for (__i
= 0; __i
<= _RopeRep::_S_max_rope_depth
; ++__i
)
1041 if (0 != __forest
[__i
]) {
1042 _Self_destruct_ptr
__old(__result
);
1043 __result
= _S_concat_rep(__forest
[__i
], __result
);
1044 __forest
[__i
]->_M_unref_nonnil();
1045 # ifdef _STLP_USE_EXCEPTIONS
1050 _STLP_UNWIND(for(__i
= 0; __i
<= _RopeRep::_S_max_rope_depth
; ++__i
)
1051 _S_unref(__forest
[__i
]))
1052 if (__result
->_M_depth
> _RopeRep::_S_max_rope_depth
) {
1053 __stl_throw_range_error("rope too long");
1059 template <class _CharT
, class _Alloc
>
1061 rope
<_CharT
,_Alloc
>::_S_add_to_forest(_RopeRep
* __r
, _RopeRep
** __forest
)
1063 if (__r
-> _M_is_balanced
) {
1064 _S_add_leaf_to_forest(__r
, __forest
);
1067 _STLP_ASSERT(__r
->_M_tag
== _RopeRep::_S_concat
)
1069 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1071 _S_add_to_forest(__c
->_M_left
, __forest
);
1072 _S_add_to_forest(__c
->_M_right
, __forest
);
1077 template <class _CharT
, class _Alloc
>
1079 rope
<_CharT
,_Alloc
>::_S_add_leaf_to_forest(_RopeRep
* __r
, _RopeRep
** __forest
)
1081 _RopeRep
* __insertee
; // included in refcount
1082 _RopeRep
* __too_tiny
= 0; // included in refcount
1083 int __i
; // forest[0..__i-1] is empty
1084 size_t __s
= __r
->_M_size
._M_data
;
1086 for (__i
= 0; __s
>= _S_min_len
[__i
+1]/* not this bucket */; ++__i
) {
1087 if (0 != __forest
[__i
]) {
1088 _Self_destruct_ptr
__old(__too_tiny
);
1089 __too_tiny
= _S_concat_and_set_balanced(__forest
[__i
], __too_tiny
);
1090 __forest
[__i
]->_M_unref_nonnil();
1095 _Self_destruct_ptr
__old(__too_tiny
);
1096 __insertee
= _S_concat_and_set_balanced(__too_tiny
, __r
);
1098 // Too_tiny dead, and no longer included in refcount.
1099 // Insertee is live and included.
1100 _STLP_ASSERT(_S_is_almost_balanced(__insertee
))
1101 _STLP_ASSERT(__insertee
->_M_depth
<= __r
->_M_depth
+ 1)
1103 if (0 != __forest
[__i
]) {
1104 _Self_destruct_ptr
__old(__insertee
);
1105 __insertee
= _S_concat_and_set_balanced(__forest
[__i
], __insertee
);
1106 __forest
[__i
]->_M_unref_nonnil();
1108 _STLP_ASSERT(_S_is_almost_balanced(__insertee
))
1110 _STLP_ASSERT(_S_min_len
[__i
] <= __insertee
->_M_size
._M_data
)
1111 _STLP_ASSERT(__forest
[__i
] == 0)
1112 if (__i
== _RopeRep::_S_max_rope_depth
||
1113 __insertee
->_M_size
._M_data
< _S_min_len
[__i
+1]) {
1114 __forest
[__i
] = __insertee
;
1115 // refcount is OK since __insertee is now dead.
1121 template <class _CharT
, class _Alloc
>
1123 rope
<_CharT
,_Alloc
>::_S_fetch(_RopeRep
* __r
, size_type __i
)
1125 _CharT
* __cstr
= __r
->_M_c_string
;
1127 _STLP_ASSERT(__i
< __r
->_M_size
._M_data
)
1128 if (0 != __cstr
) return __cstr
[__i
];
1130 switch(__r
->_M_tag
) {
1131 case _RopeRep::_S_concat
:
1133 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1134 _RopeRep
* __left
= __c
->_M_left
;
1135 size_t __left_len
= __left
->_M_size
._M_data
;
1137 if (__i
>= __left_len
) {
1139 __r
= __c
->_M_right
;
1145 case _RopeRep::_S_leaf
:
1147 _RopeLeaf
* __l
= (_RopeLeaf
*)__r
;
1148 return __l
->_M_data
[__i
];
1150 case _RopeRep::_S_function
:
1151 case _RopeRep::_S_substringfn
:
1153 _RopeFunction
* __f
= (_RopeFunction
*)__r
;
1156 (*(__f
->_M_fn
))(__i
, 1, &__result
);
1161 #if defined(_STLP_NEED_UNREACHABLE_RETURN)
1166 // Return a uniquely referenced character slot for the given
1167 // position, or 0 if that's not possible.
1168 template <class _CharT
, class _Alloc
>
1170 rope
<_CharT
,_Alloc
>::_S_fetch_ptr(_RopeRep
* __r
, size_type __i
)
1172 _RopeRep
* __clrstack
[_RopeRep::_S_max_rope_depth
];
1176 // if (__r->_M_ref_count > 1) return 0;
1177 if ( __r
->_M_incr() > 2 ) {
1181 switch(__r
->_M_tag
) {
1182 case _RopeRep::_S_concat
:
1184 _RopeConcatenation
* __c
= (_RopeConcatenation
*)__r
;
1185 _RopeRep
* __left
= __c
->_M_left
;
1186 size_t __left_len
= __left
->_M_size
._M_data
;
1188 if (__c
->_M_c_string
!= 0) __clrstack
[__csptr
++] = __c
;
1189 if (__i
>= __left_len
) {
1191 __r
= __c
->_M_right
;
1197 case _RopeRep::_S_leaf
:
1199 _RopeLeaf
* __l
= (_RopeLeaf
*)__r
;
1200 if (__l
->_M_c_string
!= __l
->_M_data
&& __l
->_M_c_string
!= 0)
1201 __clrstack
[__csptr
++] = __l
;
1202 while (__csptr
> 0) {
1204 _RopeRep
* __d
= __clrstack
[__csptr
];
1205 __d
->_M_free_c_string();
1206 __d
->_M_c_string
= 0;
1208 return __l
->_M_data
+ __i
;
1210 case _RopeRep::_S_function
:
1211 case _RopeRep::_S_substringfn
:
1215 #if defined(_STLP_NEED_UNREACHABLE_RETURN)
1221 // The following could be implemented trivially using
1222 // lexicographical_compare_3way.
1223 // We do a little more work to avoid dealing with rope iterators for
1225 template <class _CharT
, class _Alloc
>
1227 rope
<_CharT
,_Alloc
>::_S_compare (const _RopeRep
* __left
,
1228 const _RopeRep
* __right
) {
1232 if (0 == __right
) return 0 != __left
;
1233 if (0 == __left
) return -1;
1234 __left_len
= __left
->_M_size
._M_data
;
1235 __right_len
= __right
->_M_size
._M_data
;
1236 if (_RopeRep::_S_leaf
== __left
->_M_tag
) {
1237 const _RopeLeaf
* __l
= __STATIC_CAST(const _RopeLeaf
*, __left
);
1238 if (_RopeRep::_S_leaf
== __right
->_M_tag
) {
1239 const _RopeLeaf
* __r
= __STATIC_CAST(const _RopeLeaf
*, __right
);
1240 return _STLP_PRIV
__lexicographical_compare_3way(__l
->_M_data
, __l
->_M_data
+ __left_len
,
1241 __r
->_M_data
, __r
->_M_data
+ __right_len
);
1244 const_iterator
__rstart(__right
, 0);
1245 const_iterator
__rend(__right
, __right_len
);
1246 return _STLP_PRIV
__lexicographical_compare_3way(__l
->_M_data
, __l
->_M_data
+ __left_len
,
1251 const_iterator
__lstart(__left
, 0);
1252 const_iterator
__lend(__left
, __left_len
);
1253 if (_RopeRep::_S_leaf
== __right
->_M_tag
) {
1254 const _RopeLeaf
* __r
= __STATIC_CAST(const _RopeLeaf
*, __right
);
1255 return _STLP_PRIV
__lexicographical_compare_3way(__lstart
, __lend
,
1256 __r
->_M_data
, __r
->_M_data
+ __right_len
);
1259 const_iterator
__rstart(__right
, 0);
1260 const_iterator
__rend(__right
, __right_len
);
1261 return _STLP_PRIV
__lexicographical_compare_3way(__lstart
, __lend
, __rstart
, __rend
);
1266 // Assignment to reference proxies.
1267 template <class _CharT
, class _Alloc
>
1268 _Rope_char_ref_proxy
<_CharT
, _Alloc
>&
1269 _Rope_char_ref_proxy
<_CharT
, _Alloc
>::operator= (_CharT __c
) {
1270 _RopeRep
* __old
= _M_root
->_M_tree_ptr
._M_data
;
1271 // First check for the case in which everything is uniquely
1272 // referenced. In that case we can do this destructively.
1273 _CharT
* __ptr
= _My_rope::_S_fetch_ptr(__old
, _M_pos
);
1278 _Self_destruct_ptr
__left(
1279 _My_rope::_S_substring(__old
, 0, _M_pos
));
1280 _Self_destruct_ptr
__right(
1281 _My_rope::_S_substring(__old
, _M_pos
+1, __old
->_M_size
._M_data
));
1282 _Self_destruct_ptr
__result_left(
1283 _My_rope::_S_destr_concat_char_iter(__left
, &__c
, 1));
1285 // _STLP_ASSERT(__left == __result_left || 1 == __result_left->_M_ref_count)
1286 _RopeRep
* __result
=
1287 _My_rope::_S_concat_rep(__result_left
, __right
);
1288 // _STLP_ASSERT(1 <= __result->_M_ref_count)
1289 _RopeRep::_S_unref(__old
);
1290 _M_root
->_M_tree_ptr
._M_data
= __result
;
1294 template <class _CharT
, class _Alloc
>
1295 _Rope_char_ptr_proxy
<_CharT
, _Alloc
>
1296 _Rope_char_ref_proxy
<_CharT
, _Alloc
>::operator& () const {
1297 return _Rope_char_ptr_proxy
<_CharT
, _Alloc
>(*this);
1300 template<class _CharT
, class _Alloc
>
1301 _CharT rope
<_CharT
,_Alloc
>::_S_empty_c_str
[1] = { _CharT() };
1304 #if !defined (_STLP_STATIC_CONST_INIT_BUG) && !defined (_STLP_NO_STATIC_CONST_DEFINITION)
1305 template <class _CharT
, class _Alloc
>
1306 const size_t rope
<_CharT
, _Alloc
>::npos
;
1309 template<class _CharT
, class _Alloc
>
1310 const _CharT
* rope
<_CharT
,_Alloc
>::c_str() const {
1311 if (0 == _M_tree_ptr
._M_data
) {
1312 // Possibly redundant, but probably fast.
1313 _S_empty_c_str
[0] = _STLP_DEFAULT_CONSTRUCTED(_CharT
);
1314 return _S_empty_c_str
;
1316 _CharT
* __old_c_string
= _M_tree_ptr
._M_data
->_M_c_string
;
1317 if (0 != __old_c_string
) return __old_c_string
;
1318 size_t __s
= size();
1319 _CharT
* __result
= _STLP_CREATE_ALLOCATOR(allocator_type
,(const allocator_type
&)_M_tree_ptr
, _CharT
).allocate(__s
+ 1);
1320 _S_flatten(_M_tree_ptr
._M_data
, __result
);
1321 _S_construct_null(__result
+ __s
);
1322 __old_c_string
= __STATIC_CAST(_CharT
*, _Atomic_swap_ptr(__REINTERPRET_CAST(void* _STLP_VOLATILE
*, &(_M_tree_ptr
._M_data
->_M_c_string
)),
1324 if (0 != __old_c_string
) {
1325 // It must have been added in the interim. Hence it had to have been
1326 // separately allocated. Deallocate the old copy, since we just
1328 _STLP_STD::_Destroy_Range(__old_c_string
, __old_c_string
+ __s
+ 1);
1329 _STLP_CREATE_ALLOCATOR(allocator_type
,(const allocator_type
&)_M_tree_ptr
, _CharT
).deallocate(__old_c_string
, __s
+ 1);
1334 template<class _CharT
, class _Alloc
>
1335 const _CharT
* rope
<_CharT
,_Alloc
>::replace_with_c_str() {
1336 if (0 == _M_tree_ptr
._M_data
) {
1337 _S_empty_c_str
[0] = _STLP_DEFAULT_CONSTRUCTED(_CharT
);
1338 return _S_empty_c_str
;
1340 _CharT
* __old_c_string
= _M_tree_ptr
._M_data
->_M_c_string
;
1341 if (_RopeRep::_S_leaf
== _M_tree_ptr
._M_data
->_M_tag
&& 0 != __old_c_string
) {
1342 return __old_c_string
;
1344 size_t __s
= size();
1345 _CharT
* __result
= _M_tree_ptr
.allocate(_S_rounded_up_size(__s
));
1346 _S_flatten(_M_tree_ptr
._M_data
, __result
);
1347 _S_construct_null(__result
+ __s
);
1348 _M_tree_ptr
._M_data
->_M_unref_nonnil();
1349 _M_tree_ptr
._M_data
= _S_new_RopeLeaf(__result
, __s
, _M_tree_ptr
);
1353 // Algorithm specializations. More should be added.
1355 #if (!defined (_STLP_MSVC) || (_STLP_MSVC >= 1310)) && !defined (__DMC__)
1356 // I couldn't get this to work with VC++
1357 template<class _CharT
,class _Alloc
>
1358 void _Rope_rotate(_Rope_iterator
<_CharT
,_Alloc
> __first
,
1359 _Rope_iterator
<_CharT
,_Alloc
> __middle
,
1360 _Rope_iterator
<_CharT
,_Alloc
> __last
) {
1361 _STLP_ASSERT(__first
.container() == __middle
.container() &&
1362 __middle
.container() == __last
.container())
1363 rope
<_CharT
,_Alloc
>& __r(__first
.container());
1364 rope
<_CharT
,_Alloc
> __prefix
= __r
.substr(0, __first
.index());
1365 rope
<_CharT
,_Alloc
> __suffix
=
1366 __r
.substr(__last
.index(), __r
.size() - __last
.index());
1367 rope
<_CharT
,_Alloc
> __part1
=
1368 __r
.substr(__middle
.index(), __last
.index() - __middle
.index());
1369 rope
<_CharT
,_Alloc
> __part2
=
1370 __r
.substr(__first
.index(), __middle
.index() - __first
.index());
1379 // Probably not useful for several reasons:
1380 // - for SGIs 7.1 compiler and probably some others,
1381 // this forces lots of rope<wchar_t, ...> instantiations, creating a
1382 // code bloat and compile time problem. (Fixed in 7.2.)
1383 // - wchar_t is 4 bytes wide on most UNIX platforms, making it unattractive
1384 // for unicode strings. Unsigned short may be a better character
1387 _Rope_iterator
<wchar_t, allocator
<char> > __first
,
1388 _Rope_iterator
<wchar_t, allocator
<char> > __middle
,
1389 _Rope_iterator
<wchar_t, allocator
<char> > __last
) {
1390 _Rope_rotate(__first
, __middle
, __last
);
1393 #endif /* _STLP_MSVC */
1395 # undef __RopeLeaf__
1403 # endif /* ROPEIMPL_H */