1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/stlportv5/stl/_rope.c Wed Mar 31 12:27:01 2010 +0100
1.3 @@ -0,0 +1,1545 @@
1.4 +/*
1.5 + * © Portions copyright (c) 2006-2007 Nokia Corporation. All rights reserved.
1.6 + * Copyright (c) 1996,1997
1.7 + * Silicon Graphics Computer Systems, Inc.
1.8 + *
1.9 + * Copyright (c) 1999
1.10 + * Boris Fomitchev
1.11 + *
1.12 + * This material is provided "as is", with absolutely no warranty expressed
1.13 + * or implied. Any use is at your own risk.
1.14 + *
1.15 + * Permission to use or copy this software for any purpose is hereby granted
1.16 + * without fee, provided the above notices are retained on all copies.
1.17 + * Permission to modify the code and to distribute modified code is granted,
1.18 + * provided the above notices are retained, and a notice that the code was
1.19 + * modified is included with the above copyright notice.
1.20 + *
1.21 + */
1.22 +
1.23 +/* NOTE: This is an internal header file, included by other STL headers.
1.24 + * You should not attempt to use it directly.
1.25 + */
1.26 +
1.27 +// Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
1.28 +// if necessary. Assumes path_end[leaf_index] and leaf_pos are correct.
1.29 +// Results in a valid buf_ptr if the iterator can be legitimately
1.30 +// dereferenced.
1.31 +# ifndef _STLP_ROPEIMPL_H
1.32 +# define _STLP_ROPEIMPL_H
1.33 +
1.34 +#ifndef _STLP_INTERNAL_ROPE_H
1.35 +# include <stl/_rope.h>
1.36 +#endif
1.37 +
1.38 +# ifndef _STLP_CSTDIO
1.39 +# include <cstdio>
1.40 +# endif
1.41 +
1.42 +#ifndef _STLP_IOSTREAM
1.43 +# include <iostream>
1.44 +#endif
1.45 +
1.46 +# include <stl/_range_errors.h>
1.47 +
1.48 +_STLP_BEGIN_NAMESPACE
1.49 +
1.50 +# if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
1.51 +# define __allocator__ _Alloc
1.52 +# else
1.53 +# define __allocator__ allocator_type
1.54 +# endif
1.55 +
1.56 +template<class _CharT, class _Alloc>
1.57 +_Rope_iterator<_CharT, _Alloc>::_Rope_iterator(rope<_CharT,_Alloc>* __r, size_t __pos)
1.58 + : _Rope_iterator_base<_CharT,_Alloc>(__r->_M_tree_ptr._M_data, __pos),
1.59 + _M_root_rope(__r) { _RopeRep::_S_ref(this->_M_root); }
1.60 +
1.61 +template<class _CharT, class _Alloc>
1.62 +_Rope_iterator<_CharT, _Alloc>::_Rope_iterator(rope<_CharT,_Alloc>& __r, size_t __pos):
1.63 + _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr._M_data, __pos),
1.64 + _M_root_rope(&__r) {
1.65 + _RopeRep::_S_ref(this->_M_root); if (!(__r.empty()))_S_setcache(*this);
1.66 +}
1.67 +
1.68 +template<class _CharT, class _Alloc>
1.69 +void
1.70 +_Rope_RopeRep<_CharT, _Alloc>::_M_free_c_string()
1.71 +{
1.72 + _CharT* __cstr = _M_c_string;
1.73 + if (0 != __cstr) {
1.74 + size_t _p_size = _M_size._M_data + 1;
1.75 + _STLP_STD::_Destroy(__cstr, __cstr + _p_size);
1.76 + _M_size.deallocate(__cstr, _p_size);
1.77 + }
1.78 +}
1.79 +
1.80 +
1.81 +// Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
1.82 +// if necessary. Assumes _M_path_end[leaf_index] and leaf_pos are correct.
1.83 +// Results in a valid buf_ptr if the iterator can be legitimately
1.84 +// dereferenced.
1.85 +template <class _CharT, class _Alloc>
1.86 +void _Rope_iterator_base<_CharT,_Alloc>::_S_setbuf(
1.87 + _Rope_iterator_base<_CharT,_Alloc>& __x)
1.88 +{
1.89 + const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index];
1.90 + size_t __leaf_pos = __x._M_leaf_pos;
1.91 + size_t __pos = __x._M_current_pos;
1.92 +
1.93 + switch(__leaf->_M_tag) {
1.94 + case _RopeRep::_S_leaf:
1.95 + __x._M_buf_start =
1.96 + ((_Rope_RopeLeaf<_CharT,_Alloc>*)__leaf)->_M_data;
1.97 + __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos);
1.98 + __x._M_buf_end = __x._M_buf_start + __leaf->_M_size._M_data;
1.99 + break;
1.100 + case _RopeRep::_S_function:
1.101 + case _RopeRep::_S_substringfn:
1.102 + {
1.103 + size_t __len = _S_iterator_buf_len;
1.104 + size_t __buf_start_pos = __leaf_pos;
1.105 + size_t __leaf_end = __leaf_pos + __leaf->_M_size._M_data;
1.106 + char_producer<_CharT>* __fn =
1.107 + ((_Rope_RopeFunction<_CharT,_Alloc>*)__leaf)->_M_fn;
1.108 +
1.109 + if (__buf_start_pos + __len <= __pos) {
1.110 + __buf_start_pos = __pos - __len/4;
1.111 + if (__buf_start_pos + __len > __leaf_end) {
1.112 + __buf_start_pos = __leaf_end - __len;
1.113 + }
1.114 + }
1.115 + if (__buf_start_pos + __len > __leaf_end) {
1.116 + __len = __leaf_end - __buf_start_pos;
1.117 + }
1.118 + (*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf);
1.119 + __x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos);
1.120 + __x._M_buf_start = __x._M_tmp_buf;
1.121 + __x._M_buf_end = __x._M_tmp_buf + __len;
1.122 + }
1.123 + break;
1.124 + default:
1.125 + _STLP_ASSERT(0)
1.126 + ;
1.127 + }
1.128 +}
1.129 +
1.130 +// Set path and buffer inside a rope iterator. We assume that
1.131 +// pos and root are already set.
1.132 +template <class _CharT, class _Alloc>
1.133 +void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache
1.134 +(_Rope_iterator_base<_CharT,_Alloc>& __x)
1.135 +{
1.136 + const _RopeRep* __path[_RopeRep::_S_max_rope_depth+1];
1.137 + const _RopeRep* __curr_rope;
1.138 + int __curr_depth = -1; /* index into path */
1.139 + size_t __curr_start_pos = 0;
1.140 + size_t __pos = __x._M_current_pos;
1.141 + unsigned char __dirns = 0; // Bit vector marking right turns in the path
1.142 +
1.143 + _STLP_ASSERT(__pos <= __x._M_root->_M_size._M_data)
1.144 + if (__pos >= __x._M_root->_M_size._M_data) {
1.145 + __x._M_buf_ptr = 0;
1.146 + return;
1.147 + }
1.148 + __curr_rope = __x._M_root;
1.149 + if (0 != __curr_rope->_M_c_string) {
1.150 + /* Treat the root as a leaf. */
1.151 + __x._M_buf_start = __curr_rope->_M_c_string;
1.152 + __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size._M_data;
1.153 + __x._M_buf_ptr = __curr_rope->_M_c_string + __pos;
1.154 + __x._M_path_end[0] = __curr_rope;
1.155 + __x._M_leaf_index = 0;
1.156 + __x._M_leaf_pos = 0;
1.157 + return;
1.158 + }
1.159 + for(;;) {
1.160 + ++__curr_depth;
1.161 + _STLP_ASSERT(__curr_depth <= _RopeRep::_S_max_rope_depth)
1.162 + __path[__curr_depth] = __curr_rope;
1.163 + switch(__curr_rope->_M_tag) {
1.164 + case _RopeRep::_S_leaf:
1.165 + case _RopeRep::_S_function:
1.166 + case _RopeRep::_S_substringfn:
1.167 + __x._M_leaf_pos = __curr_start_pos;
1.168 + goto done;
1.169 + case _RopeRep::_S_concat:
1.170 + {
1.171 + _Rope_RopeConcatenation<_CharT,_Alloc>* __c =
1.172 + (_Rope_RopeConcatenation<_CharT,_Alloc>*)__curr_rope;
1.173 + _RopeRep* __left = __c->_M_left;
1.174 + size_t __left_len = __left->_M_size._M_data;
1.175 +
1.176 + __dirns <<= 1;
1.177 + if (__pos >= __curr_start_pos + __left_len) {
1.178 + __dirns |= 1;
1.179 + __curr_rope = __c->_M_right;
1.180 + __curr_start_pos += __left_len;
1.181 + } else {
1.182 + __curr_rope = __left;
1.183 + }
1.184 + }
1.185 + break;
1.186 + }
1.187 + }
1.188 + done:
1.189 + // Copy last section of path into _M_path_end.
1.190 + {
1.191 + int __i = -1;
1.192 + int __j = __curr_depth + 1 - _S_path_cache_len;
1.193 +
1.194 + if (__j < 0) __j = 0;
1.195 + while (__j <= __curr_depth) {
1.196 + __x._M_path_end[++__i] = __path[__j++];
1.197 + }
1.198 + __x._M_leaf_index = __i;
1.199 + }
1.200 + __x._M_path_directions = __dirns;
1.201 + _S_setbuf(__x);
1.202 +}
1.203 +
1.204 +// Specialized version of the above. Assumes that
1.205 +// the path cache is valid for the previous position.
1.206 +template <class _CharT, class _Alloc>
1.207 +void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache_for_incr
1.208 +(_Rope_iterator_base<_CharT,_Alloc>& __x)
1.209 +{
1.210 + int __current_index = __x._M_leaf_index;
1.211 + const _RopeRep* __current_node = __x._M_path_end[__current_index];
1.212 + size_t __len = __current_node->_M_size._M_data;
1.213 + size_t __node_start_pos = __x._M_leaf_pos;
1.214 + unsigned char __dirns = __x._M_path_directions;
1.215 + _Rope_RopeConcatenation<_CharT,_Alloc>* __c;
1.216 +
1.217 + _STLP_ASSERT(__x._M_current_pos <= __x._M_root->_M_size._M_data)
1.218 + if (__x._M_current_pos - __node_start_pos < __len) {
1.219 + /* More stuff in this leaf, we just didn't cache it. */
1.220 + _S_setbuf(__x);
1.221 + return;
1.222 + }
1.223 + _STLP_ASSERT(__node_start_pos + __len == __x._M_current_pos)
1.224 + // node_start_pos is starting position of last_node.
1.225 + while (--__current_index >= 0) {
1.226 + if (!(__dirns & 1) /* Path turned left */)
1.227 + break;
1.228 + __current_node = __x._M_path_end[__current_index];
1.229 + __c = (_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node;
1.230 + // Otherwise we were in the right child. Thus we should pop
1.231 + // the concatenation node.
1.232 + __node_start_pos -= __c->_M_left->_M_size._M_data;
1.233 + __dirns >>= 1;
1.234 + }
1.235 + if (__current_index < 0) {
1.236 + // We underflowed the cache. Punt.
1.237 + _S_setcache(__x);
1.238 + return;
1.239 + }
1.240 + __current_node = __x._M_path_end[__current_index];
1.241 + __c = (_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node;
1.242 + // current_node is a concatenation node. We are positioned on the first
1.243 + // character in its right child.
1.244 + // node_start_pos is starting position of current_node.
1.245 + __node_start_pos += __c->_M_left->_M_size._M_data;
1.246 + __current_node = __c->_M_right;
1.247 + __x._M_path_end[++__current_index] = __current_node;
1.248 + __dirns |= 1;
1.249 + while (_RopeRep::_S_concat == __current_node->_M_tag) {
1.250 + ++__current_index;
1.251 + if (_S_path_cache_len == __current_index) {
1.252 + int __i;
1.253 + for (__i = 0; __i < _S_path_cache_len-1; __i++) {
1.254 + __x._M_path_end[__i] = __x._M_path_end[__i+1];
1.255 + }
1.256 + --__current_index;
1.257 + }
1.258 + __current_node =
1.259 + ((_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node)->_M_left;
1.260 + __x._M_path_end[__current_index] = __current_node;
1.261 + __dirns <<= 1;
1.262 + // node_start_pos is unchanged.
1.263 + }
1.264 + __x._M_leaf_index = __current_index;
1.265 + __x._M_leaf_pos = __node_start_pos;
1.266 + __x._M_path_directions = __dirns;
1.267 + _S_setbuf(__x);
1.268 +}
1.269 +
1.270 +template <class _CharT, class _Alloc>
1.271 +void _Rope_iterator_base<_CharT,_Alloc>::_M_incr(size_t __n) {
1.272 + _M_current_pos += __n;
1.273 + if (0 != _M_buf_ptr) {
1.274 + size_t __chars_left = _M_buf_end - _M_buf_ptr;
1.275 + if (__chars_left > __n) {
1.276 + _M_buf_ptr += __n;
1.277 + } else if (__chars_left == __n) {
1.278 + _M_buf_ptr += __n;
1.279 + _S_setcache_for_incr(*this);
1.280 + } else {
1.281 + _M_buf_ptr = 0;
1.282 + }
1.283 + }
1.284 +}
1.285 +
1.286 +template <class _CharT, class _Alloc>
1.287 +void _Rope_iterator_base<_CharT,_Alloc>::_M_decr(size_t __n) {
1.288 + if (0 != _M_buf_ptr) {
1.289 + size_t __chars_left = _M_buf_ptr - _M_buf_start;
1.290 + if (__chars_left >= __n) {
1.291 + _M_buf_ptr -= __n;
1.292 + } else {
1.293 + _M_buf_ptr = 0;
1.294 + }
1.295 + }
1.296 + _M_current_pos -= __n;
1.297 +}
1.298 +
1.299 +template <class _CharT, class _Alloc>
1.300 +void _Rope_iterator<_CharT,_Alloc>::_M_check() {
1.301 + if (_M_root_rope->_M_tree_ptr._M_data != this->_M_root) {
1.302 + // _Rope was modified. Get things fixed up.
1.303 + _RopeRep::_S_unref(this->_M_root);
1.304 + this->_M_root = _M_root_rope->_M_tree_ptr._M_data;
1.305 + _RopeRep::_S_ref(this->_M_root);
1.306 + this->_M_buf_ptr = 0;
1.307 + }
1.308 +}
1.309 +
1.310 +# ifndef _GC
1.311 +// There are several reasons for not doing this with virtual destructors
1.312 +// and a class specific delete operator:
1.313 +// - A class specific delete operator can't easily get access to
1.314 +// allocator instances if we need them.
1.315 +// - Any virtual function would need a 4 or byte vtable pointer;
1.316 +// this only requires a one byte tag per object.
1.317 +template <class _CharT, class _Alloc>
1.318 +void _Rope_RopeRep<_CharT,_Alloc>::_M_free_tree()
1.319 +{
1.320 + switch(_M_tag) {
1.321 + case _S_leaf:
1.322 + {
1.323 + typedef _Rope_RopeLeaf<_CharT,_Alloc> _Rope_RopeLeaf_T;
1.324 + _Rope_RopeLeaf_T* __l = (_Rope_RopeLeaf_T*)this;
1.325 + _STLP_STD::_Destroy(__l); // ->_Rope_RopeLeaf<_CharT,_Alloc>::~_Rope_RopeLeaf();
1.326 + _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_size, _Rope_RopeLeaf_T).deallocate(__l, 1);
1.327 + break;
1.328 + }
1.329 + case _S_concat:
1.330 + {
1.331 + typedef _Rope_RopeConcatenation<_CharT,_Alloc> _Rope_RopeConcatenation_T;
1.332 + _Rope_RopeConcatenation_T* __c = (_Rope_RopeConcatenation_T*)this;
1.333 + _STLP_STD::_Destroy(__c);
1.334 + _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_size,
1.335 + _Rope_RopeConcatenation_T).deallocate(__c, 1);
1.336 + break;
1.337 + }
1.338 + case _S_function:
1.339 + {
1.340 + typedef _Rope_RopeFunction<_CharT,_Alloc> _Rope_RopeFunctionT;
1.341 + _Rope_RopeFunctionT* __f = (_Rope_RopeFunctionT*)this;
1.342 + _STLP_STD::_Destroy(__f);
1.343 + _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_size,
1.344 + _Rope_RopeFunctionT).deallocate(__f, 1);
1.345 + break;
1.346 + }
1.347 + case _S_substringfn:
1.348 + {
1.349 + typedef _Rope_RopeSubstring<_CharT,_Alloc> _Rope_RopeSubstring_T;
1.350 + _Rope_RopeSubstring_T* __ss = (_Rope_RopeSubstring_T*)this;
1.351 + _STLP_STD::_Destroy(__ss);
1.352 + _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_size,
1.353 + _Rope_RopeSubstring_T).deallocate(__ss, 1);
1.354 + break;
1.355 + }
1.356 + }
1.357 +}
1.358 +#endif
1.359 +
1.360 +# if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
1.361 +# define __RopeLeaf__ _Rope_RopeLeaf<_CharT,_Alloc>
1.362 +# define __RopeRep__ _Rope_RopeRep<_CharT,_Alloc>
1.363 +# define _RopeLeaf _Rope_RopeLeaf<_CharT,_Alloc>
1.364 +# define _RopeRep _Rope_RopeRep<_CharT,_Alloc>
1.365 +# define size_type size_t
1.366 +# else
1.367 +# define __RopeLeaf__ _STLP_TYPENAME_ON_RETURN_TYPE rope<_CharT,_Alloc>::_RopeLeaf
1.368 +# define __RopeRep__ _STLP_TYPENAME_ON_RETURN_TYPE rope<_CharT,_Alloc>::_RopeRep
1.369 +# endif
1.370 +
1.371 +// Concatenate a C string onto a leaf rope by copying the rope data.
1.372 +// Used for short ropes.
1.373 +template <class _CharT, class _Alloc>
1.374 +__RopeLeaf__*
1.375 +rope<_CharT,_Alloc>::_S_leaf_concat_char_iter
1.376 + (_RopeLeaf* __r, const _CharT* __iter, size_t __len)
1.377 +{
1.378 + size_t __old_len = __r->_M_size._M_data;
1.379 + _CharT* __new_data = __r->_M_size.allocate(_S_rounded_up_size(__old_len + __len));
1.380 + _RopeLeaf* __result;
1.381 +
1.382 + uninitialized_copy_n(__r->_M_data, __old_len, __new_data);
1.383 + uninitialized_copy_n(__iter, __len, __new_data + __old_len);
1.384 + _S_cond_store_eos(__new_data[__old_len + __len]);
1.385 + _STLP_TRY {
1.386 + __result = _S_new_RopeLeaf(__new_data, __old_len + __len,
1.387 + __r->get_allocator());
1.388 + }
1.389 + _STLP_UNWIND(_RopeRep::_S_free_string(__new_data, __old_len + __len,
1.390 + __r->get_allocator()));
1.391 + return __result;
1.392 +}
1.393 +
1.394 +#ifndef __GC
1.395 +// As above, but it's OK to clobber original if refcount is 1
1.396 +template <class _CharT, class _Alloc>
1.397 +__RopeLeaf__*
1.398 +rope<_CharT,_Alloc>::_S_destr_leaf_concat_char_iter
1.399 + (_RopeLeaf* __r, const _CharT* __iter, size_t __len)
1.400 +{
1.401 + _STLP_ASSERT(__r->_M_ref_count >= 1)
1.402 + if (__r->_M_ref_count > 1)
1.403 + return _S_leaf_concat_char_iter(__r, __iter, __len);
1.404 + size_t __old_len = __r->_M_size._M_data;
1.405 + if (_S_allocated_capacity(__old_len) >= __old_len + __len) {
1.406 + // The space has been partially initialized for the standard
1.407 + // character types. But that doesn't matter for those types.
1.408 + uninitialized_copy_n(__iter, __len, __r->_M_data + __old_len);
1.409 + if (_S_is_basic_char_type((_CharT*)0)) {
1.410 + _S_cond_store_eos(__r->_M_data[__old_len + __len]);
1.411 + _STLP_ASSERT(__r->_M_c_string == __r->_M_data)
1.412 + } else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string) {
1.413 + __r->_M_free_c_string();
1.414 + __r->_M_c_string = 0;
1.415 + }
1.416 + __r->_M_size._M_data = __old_len + __len;
1.417 + _STLP_ASSERT(__r->_M_ref_count == 1)
1.418 + __r->_M_ref_count = 2;
1.419 + return __r;
1.420 + } else {
1.421 + _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len);
1.422 + _STLP_ASSERT(__result->_M_ref_count == 1)
1.423 + return __result;
1.424 + }
1.425 +}
1.426 +#endif
1.427 +
1.428 +// Assumes left and right are not 0.
1.429 +// Does not increment (nor decrement on exception) child reference counts.
1.430 +// Result has ref count 1.
1.431 +template <class _CharT, class _Alloc>
1.432 +__RopeRep__*
1.433 +rope<_CharT,_Alloc>::_S_tree_concat (_RopeRep* __left, _RopeRep* __right)
1.434 +{
1.435 + _RopeConcatenation* __result =
1.436 + _S_new_RopeConcatenation(__left, __right, __left->get_allocator());
1.437 + size_t __depth = __result->_M_depth;
1.438 +
1.439 + _STLP_ASSERT(__left->get_allocator() == __right->get_allocator())
1.440 + if (__depth > 20 && (__result->_M_size._M_data < 1000 ||
1.441 + __depth > _RopeRep::_S_max_rope_depth)) {
1.442 + _RopeRep* __balanced;
1.443 +
1.444 + _STLP_TRY {
1.445 + __balanced = _S_balance(__result);
1.446 +# ifndef __GC
1.447 + if (__result != __balanced) {
1.448 + _STLP_ASSERT(1 == __result->_M_ref_count
1.449 + && 1 == __balanced->_M_ref_count)
1.450 + }
1.451 +# endif
1.452 + __result->_M_unref_nonnil();
1.453 + }
1.454 + _STLP_UNWIND((_STLP_CREATE_ALLOCATOR(allocator_type,(allocator_type&)__left->_M_size,
1.455 + _RopeConcatenation).deallocate(__result,1)));
1.456 + // In case of exception, we need to deallocate
1.457 + // otherwise dangling result node. But caller
1.458 + // still owns its children. Thus unref is
1.459 + // inappropriate.
1.460 + return __balanced;
1.461 + } else {
1.462 + return __result;
1.463 + }
1.464 +}
1.465 +
1.466 +template <class _CharT, class _Alloc>
1.467 +__RopeRep__*
1.468 +rope<_CharT,_Alloc>::_S_concat_char_iter
1.469 + (_RopeRep* __r, const _CharT*__s, size_t __slen)
1.470 +{
1.471 + _RopeRep* __result;
1.472 + if (0 == __slen) {
1.473 + _S_ref(__r);
1.474 + return __r;
1.475 + }
1.476 + if (0 == __r)
1.477 + return _STLP_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
1.478 + /* __r->get_allocator()*/ allocator_type() );
1.479 + if (_RopeRep::_S_leaf == __r->_M_tag &&
1.480 + __r->_M_size._M_data + __slen <= _S_copy_max) {
1.481 + __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
1.482 +# ifndef __GC
1.483 + _STLP_ASSERT(1 == __result->_M_ref_count)
1.484 +# endif
1.485 + return __result;
1.486 + }
1.487 + if (_RopeRep::_S_concat == __r->_M_tag
1.488 + && _RopeRep::_S_leaf == ((_RopeConcatenation*)__r)->_M_right->_M_tag) {
1.489 + _RopeLeaf* __right =
1.490 + (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right);
1.491 + if (__right->_M_size._M_data + __slen <= _S_copy_max) {
1.492 + _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left;
1.493 + _RopeRep* __nright =
1.494 + _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen);
1.495 + __left->_M_ref_nonnil();
1.496 + _STLP_TRY {
1.497 + __result = _S_tree_concat(__left, __nright);
1.498 + }
1.499 + _STLP_UNWIND(_S_unref(__left); _S_unref(__nright));
1.500 +# ifndef __GC
1.501 + _STLP_ASSERT(1 == __result->_M_ref_count)
1.502 +# endif
1.503 + return __result;
1.504 + }
1.505 + }
1.506 + _RopeRep* __nright =
1.507 + _STLP_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator());
1.508 + _STLP_TRY {
1.509 + __r->_M_ref_nonnil();
1.510 + __result = _S_tree_concat(__r, __nright);
1.511 + }
1.512 + _STLP_UNWIND(_S_unref(__r); _S_unref(__nright));
1.513 +# ifndef __GC
1.514 + _STLP_ASSERT(1 == __result->_M_ref_count)
1.515 +# endif
1.516 + return __result;
1.517 +}
1.518 +
1.519 +#ifndef __GC
1.520 +template <class _CharT, class _Alloc>
1.521 +__RopeRep__*
1.522 +rope<_CharT,_Alloc>::_S_destr_concat_char_iter(
1.523 + _RopeRep* __r, const _CharT* __s, size_t __slen)
1.524 +{
1.525 + _RopeRep* __result;
1.526 + if (0 == __r)
1.527 + return _STLP_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
1.528 + /* __r-> */allocator_type());
1.529 + size_t __count = __r->_M_ref_count;
1.530 + size_t __orig_size = __r->_M_size._M_data;
1.531 + _STLP_ASSERT(__count >= 1)
1.532 + if (__count > 1) return _S_concat_char_iter(__r, __s, __slen);
1.533 + if (0 == __slen) {
1.534 + __r->_M_ref_count = 2; // One more than before
1.535 + return __r;
1.536 + }
1.537 + if (__orig_size + __slen <= _S_copy_max &&
1.538 + _RopeRep::_S_leaf == __r->_M_tag) {
1.539 + __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
1.540 + return __result;
1.541 + }
1.542 + if (_RopeRep::_S_concat == __r->_M_tag) {
1.543 + _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*)__r)->_M_right);
1.544 + if (_RopeRep::_S_leaf == __right->_M_tag
1.545 + && __right->_M_size._M_data + __slen <= _S_copy_max) {
1.546 + _RopeRep* __new_right =
1.547 + _S_destr_leaf_concat_char_iter(__right, __s, __slen);
1.548 + if (__right == __new_right) {
1.549 + _STLP_ASSERT(__new_right->_M_ref_count == 2)
1.550 + __new_right->_M_ref_count = 1;
1.551 + } else {
1.552 + _STLP_ASSERT(__new_right->_M_ref_count >= 1)
1.553 + __right->_M_unref_nonnil();
1.554 + }
1.555 + _STLP_ASSERT(__r->_M_ref_count == 1)
1.556 + __r->_M_ref_count = 2; // One more than before.
1.557 + ((_RopeConcatenation*)__r)->_M_right = __new_right;
1.558 + // E.Musser : moved below
1.559 + // __r->_M_size._M_data = __orig_size + __slen;
1.560 + if (0 != __r->_M_c_string) {
1.561 + __r->_M_free_c_string();
1.562 + __r->_M_c_string = 0;
1.563 + }
1.564 + __r->_M_size._M_data = __orig_size + __slen;
1.565 + return __r;
1.566 + }
1.567 + }
1.568 + _RopeRep* __right =
1.569 + _STLP_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator());
1.570 + __r->_M_ref_nonnil();
1.571 + _STLP_TRY {
1.572 + __result = _S_tree_concat(__r, __right);
1.573 + }
1.574 + _STLP_UNWIND(_S_unref(__r); _S_unref(__right))
1.575 + _STLP_ASSERT(1 == __result->_M_ref_count)
1.576 + return __result;
1.577 +}
1.578 +#endif /* !__GC */
1.579 +
1.580 +template <class _CharT, class _Alloc>
1.581 +__RopeRep__*
1.582 +rope<_CharT,_Alloc>::_S_concat_rep(_RopeRep* __left, _RopeRep* __right)
1.583 +{
1.584 + if (0 == __left) {
1.585 + _S_ref(__right);
1.586 + return __right;
1.587 + }
1.588 + if (0 == __right) {
1.589 + __left->_M_ref_nonnil();
1.590 + return __left;
1.591 + }
1.592 + if (_RopeRep::_S_leaf == __right->_M_tag) {
1.593 + if (_RopeRep::_S_leaf == __left->_M_tag) {
1.594 + if (__right->_M_size._M_data + __left->_M_size._M_data <= _S_copy_max) {
1.595 + return _S_leaf_concat_char_iter((_RopeLeaf*)__left,
1.596 + ((_RopeLeaf*)__right)->_M_data,
1.597 + __right->_M_size._M_data);
1.598 + }
1.599 + } else if (_RopeRep::_S_concat == __left->_M_tag
1.600 + && _RopeRep::_S_leaf ==
1.601 + ((_RopeConcatenation*)__left)->_M_right->_M_tag) {
1.602 + _RopeLeaf* __leftright =
1.603 + (_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right);
1.604 + if (__leftright->_M_size._M_data + __right->_M_size._M_data <= _S_copy_max) {
1.605 + _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left;
1.606 + _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright,
1.607 + ((_RopeLeaf*)__right)->_M_data,
1.608 + __right->_M_size._M_data);
1.609 + __leftleft->_M_ref_nonnil();
1.610 + _STLP_TRY {
1.611 + return(_S_tree_concat(__leftleft, __rest));
1.612 + }
1.613 + _STLP_UNWIND(_S_unref(__leftleft); _S_unref(__rest))
1.614 + }
1.615 + }
1.616 + }
1.617 + __left->_M_ref_nonnil();
1.618 + __right->_M_ref_nonnil();
1.619 + _STLP_TRY {
1.620 + return(_S_tree_concat(__left, __right));
1.621 + }
1.622 + _STLP_UNWIND(_S_unref(__left); _S_unref(__right));
1.623 +#ifdef _STLP_THROW_RETURN_BUG
1.624 + return 0;
1.625 +#endif
1.626 +}
1.627 +
1.628 +template <class _CharT, class _Alloc>
1.629 +__RopeRep__*
1.630 +rope<_CharT,_Alloc>::_S_substring(_RopeRep* __base,
1.631 + size_t __start, size_t __endp1)
1.632 +{
1.633 + if (0 == __base) return 0;
1.634 + size_t __len = __base->_M_size._M_data;
1.635 + size_t __adj_endp1;
1.636 + const size_t __lazy_threshold = 128;
1.637 +
1.638 + if (__endp1 >= __len) {
1.639 + if (0 == __start) {
1.640 + __base->_M_ref_nonnil();
1.641 + return __base;
1.642 + } else {
1.643 + __adj_endp1 = __len;
1.644 + }
1.645 + } else {
1.646 + __adj_endp1 = __endp1;
1.647 + }
1.648 + switch(__base->_M_tag) {
1.649 + case _RopeRep::_S_concat:
1.650 + {
1.651 + _RopeConcatenation* __c = (_RopeConcatenation*)__base;
1.652 + _RopeRep* __left = __c->_M_left;
1.653 + _RopeRep* __right = __c->_M_right;
1.654 + size_t __left_len = __left->_M_size._M_data;
1.655 + _RopeRep* __result;
1.656 +
1.657 + if (__adj_endp1 <= __left_len) {
1.658 + return _S_substring(__left, __start, __endp1);
1.659 + } else if (__start >= __left_len) {
1.660 + return _S_substring(__right, __start - __left_len,
1.661 + __adj_endp1 - __left_len);
1.662 + }
1.663 + _Self_destruct_ptr __left_result(
1.664 + _S_substring(__left, __start, __left_len));
1.665 + _Self_destruct_ptr __right_result(
1.666 + _S_substring(__right, 0, __endp1 - __left_len));
1.667 + _STLP_MPWFIX_TRY //*TY 06/01/2000 - mpw forgets to call dtor on __left_result and __right_result without this try block
1.668 + __result = _S_concat_rep(__left_result, __right_result);
1.669 +# ifndef __GC
1.670 + _STLP_ASSERT(1 == __result->_M_ref_count)
1.671 +# endif
1.672 + return __result;
1.673 + _STLP_MPWFIX_CATCH //*TY 06/01/2000 -
1.674 + }
1.675 + case _RopeRep::_S_leaf:
1.676 + {
1.677 + _RopeLeaf* __l = (_RopeLeaf*)__base;
1.678 + _RopeLeaf* __result;
1.679 + size_t __result_len;
1.680 + if (__start >= __adj_endp1) return 0;
1.681 + __result_len = __adj_endp1 - __start;
1.682 + if (__result_len > __lazy_threshold) goto lazy;
1.683 +# ifdef __GC
1.684 + const _CharT* __section = __l->_M_data + __start;
1.685 + __result = _S_new_RopeLeaf(__section, __result_len,
1.686 + __base->get_allocator());
1.687 + __result->_M_c_string = 0; // Not eos terminated.
1.688 +# else
1.689 + // We should sometimes create substring node instead.
1.690 + __result = _STLP_ROPE_FROM_UNOWNED_CHAR_PTR(
1.691 + __l->_M_data + __start, __result_len,
1.692 + __base->get_allocator());
1.693 +# endif
1.694 + return __result;
1.695 + }
1.696 + case _RopeRep::_S_substringfn:
1.697 + // Avoid introducing multiple layers of substring nodes.
1.698 + {
1.699 + _RopeSubstring* __old = (_RopeSubstring*)__base;
1.700 + size_t __result_len;
1.701 + if (__start >= __adj_endp1) return 0;
1.702 + __result_len = __adj_endp1 - __start;
1.703 + if (__result_len > __lazy_threshold) {
1.704 + _RopeSubstring* __result =
1.705 + _S_new_RopeSubstring(__old->_M_base,
1.706 + __start + __old->_M_start,
1.707 + __adj_endp1 - __start,
1.708 + __base->get_allocator());
1.709 + return __result;
1.710 +
1.711 + } // *** else fall through: ***
1.712 + }
1.713 + case _RopeRep::_S_function:
1.714 + {
1.715 + _RopeFunction* __f = (_RopeFunction*)__base;
1.716 + if (__start >= __adj_endp1) return 0;
1.717 + size_t __result_len = __adj_endp1 - __start;
1.718 +
1.719 + if (__result_len > __lazy_threshold) goto lazy;
1.720 + _CharT* __section = __base->_M_size.allocate(_S_rounded_up_size(__result_len));
1.721 + _STLP_TRY {
1.722 + (*(__f->_M_fn))(__start, __result_len, __section);
1.723 + }
1.724 + _STLP_UNWIND(_RopeRep::_S_free_string(
1.725 + __section, __result_len, __base->get_allocator()));
1.726 + _S_cond_store_eos(__section[__result_len]);
1.727 + return _S_new_RopeLeaf(__section, __result_len,
1.728 + __base->get_allocator());
1.729 + }
1.730 + }
1.731 + /*NOTREACHED*/
1.732 + _STLP_ASSERT(false)
1.733 + lazy:
1.734 + {
1.735 + // Create substring node.
1.736 + return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start,
1.737 + __base->get_allocator());
1.738 + }
1.739 +}
1.740 +
1.741 +template<class _CharT>
1.742 +class _Rope_flatten_char_consumer : public _Rope_char_consumer<_CharT> {
1.743 + private:
1.744 + _CharT* _M_buf_ptr;
1.745 + public:
1.746 + // _CharT* _M_buffer; // XXX not used
1.747 +
1.748 + _Rope_flatten_char_consumer(_CharT* __buffer) {
1.749 + _M_buf_ptr = __buffer;
1.750 + };
1.751 + ~_Rope_flatten_char_consumer() {}
1.752 + bool operator() (const _CharT* __leaf, size_t __n) {
1.753 + uninitialized_copy_n(__leaf, __n, _M_buf_ptr);
1.754 + _M_buf_ptr += __n;
1.755 + return true;
1.756 + }
1.757 +};
1.758 +
1.759 +template<class _CharT>
1.760 +class _Rope_find_char_char_consumer : public _Rope_char_consumer<_CharT> {
1.761 + private:
1.762 + _CharT _M_pattern;
1.763 + public:
1.764 + size_t _M_count; // Number of nonmatching characters
1.765 + _Rope_find_char_char_consumer(_CharT __p)
1.766 + : _M_pattern(__p), _M_count(0) {}
1.767 + ~_Rope_find_char_char_consumer() {}
1.768 + bool operator() (const _CharT* __leaf, size_t __n) {
1.769 + size_t __i;
1.770 + for (__i = 0; __i < __n; __i++) {
1.771 + if (__leaf[__i] == _M_pattern) {
1.772 + _M_count += __i; return false;
1.773 + }
1.774 + }
1.775 + _M_count += __n; return true;
1.776 + }
1.777 +};
1.778 +
1.779 +#if !defined (_STLP_USE_NO_IOSTREAMS)
1.780 +#if defined (_STLP_USE_NEW_IOSTREAMS)
1.781 + template<class _CharT, class _Traits>
1.782 + // Here _CharT is both the stream and rope character type.
1.783 +#else
1.784 + template<class _CharT>
1.785 + // Here _CharT is the rope character type. Unlike in the
1.786 + // above case, we somewhat handle the case in which it doesn't
1.787 + // match the stream character type, i.e. char.
1.788 +#endif
1.789 +class _Rope_insert_char_consumer : public _Rope_char_consumer<_CharT> {
1.790 + private:
1.791 +# if defined (_STLP_USE_NEW_IOSTREAMS)
1.792 + typedef basic_ostream<_CharT,_Traits> _Insert_ostream;
1.793 +# else
1.794 + typedef ostream _Insert_ostream;
1.795 +# endif
1.796 + _Insert_ostream& _M_o;
1.797 + public:
1.798 + // _CharT* buffer; // XXX not used
1.799 + _Rope_insert_char_consumer(_Insert_ostream& __writer)
1.800 + : _M_o(__writer) {};
1.801 +#if defined(__MRC__)||(defined(__SC__) && !defined(__DMC__)) //*TY 05/23/2000 - added support for mpw compiler's trigger function approach to generate vtable
1.802 + ~_Rope_insert_char_consumer(); //*TY 05/23/2000 -
1.803 +#else //*TY 05/23/2000 -
1.804 + ~_Rope_insert_char_consumer() {}
1.805 +#endif //*TY 05/23/2000 -
1.806 + // Caller is presumed to own the ostream
1.807 + bool operator() (const _CharT* __leaf, size_t __n);
1.808 + // Returns true to continue traversal.
1.809 +};
1.810 +
1.811 +# if defined ( _STLP_USE_NEW_IOSTREAMS )
1.812 +# if defined(__MRC__)||(defined(__SC__) && !defined(__DMC__)) //*TY 05/23/2000 - added support for mpw compiler's trigger function approach to generate vtable
1.813 + template<class _CharT, class _Traits>
1.814 + _Rope_insert_char_consumer<_CharT, _Traits>:: ~_Rope_insert_char_consumer() {}
1.815 +# endif //*TY 05/23/2000 -
1.816 +
1.817 + template<class _CharT, class _Traits>
1.818 + bool _Rope_insert_char_consumer<_CharT, _Traits>::operator()
1.819 + (const _CharT* __leaf, size_t __n)
1.820 +{
1.821 + size_t __i;
1.822 + // We assume that formatting is set up correctly for each element.
1.823 + for (__i = 0; __i < __n; __i++) _M_o.put(__leaf[__i]);
1.824 + return true;
1.825 +}
1.826 +# else
1.827 +# if defined(__MRC__)||(defined(__SC__) && !defined(__DMC__)) //*TY 05/23/2000 - added support for mpw compiler's trigger function approach to generate vtable
1.828 + template<class _CharT>
1.829 + _Rope_insert_char_consumer<_CharT>:: ~_Rope_insert_char_consumer() {}
1.830 +# endif //*TY 05/23/2000 -
1.831 +
1.832 + template<class _CharT>
1.833 + bool _Rope_insert_char_consumer<_CharT>::operator()
1.834 + (const _CharT* __leaf, size_t __n)
1.835 + {
1.836 + size_t __i;
1.837 + // We assume that formatting is set up correctly for each element.
1.838 + for (__i = 0; __i < __n; __i++) _M_o << __leaf[__i];
1.839 + return true;
1.840 + }
1.841 +
1.842 +# if !defined (_STLP_NO_METHOD_SPECIALIZATION)
1.843 +_STLP_TEMPLATE_NULL
1.844 +inline bool
1.845 +_Rope_insert_char_consumer<char>::operator()
1.846 + (const char* __leaf, size_t __n)
1.847 +{
1.848 + size_t __i;
1.849 + for (__i = 0; __i < __n; __i++) _M_o.put(__leaf[__i]);
1.850 + return true;
1.851 +}
1.852 +
1.853 +#endif /* _STLP_METHOD_SPECIALIZATION */
1.854 +#endif /* _STLP_USE_NEW_IOSTREAM */
1.855 +#endif /* if !defined (_STLP_USE_NO_IOSTREAMS) */
1.856 +
1.857 +template <class _CharT, class _Alloc>
1.858 +bool rope<_CharT, _Alloc>::_S_apply_to_pieces(
1.859 + _Rope_char_consumer<_CharT>& __c,
1.860 + const _RopeRep* __r,
1.861 + size_t __begin, size_t __end)
1.862 +{
1.863 + if (0 == __r) return true;
1.864 + switch(__r->_M_tag) {
1.865 + case _RopeRep::_S_concat:
1.866 + {
1.867 + _RopeConcatenation* __conc = (_RopeConcatenation*)__r;
1.868 + _RopeRep* __left = __conc->_M_left;
1.869 + size_t __left_len = __left->_M_size._M_data;
1.870 + if (__begin < __left_len) {
1.871 + size_t __left_end = (min) (__left_len, __end);
1.872 + if (!_S_apply_to_pieces(__c, __left, __begin, __left_end))
1.873 + return false;
1.874 + }
1.875 + if (__end > __left_len) {
1.876 + _RopeRep* __right = __conc->_M_right;
1.877 + size_t __right_start = (max)(__left_len, __begin);
1.878 + if (!_S_apply_to_pieces(__c, __right,
1.879 + __right_start - __left_len,
1.880 + __end - __left_len)) {
1.881 + return false;
1.882 + }
1.883 + }
1.884 + }
1.885 + return true;
1.886 + case _RopeRep::_S_leaf:
1.887 + {
1.888 + _RopeLeaf* __l = (_RopeLeaf*)__r;
1.889 + return __c.operator()(__l->_M_data + __begin, __end - __begin);
1.890 + }
1.891 + case _RopeRep::_S_function:
1.892 + case _RopeRep::_S_substringfn:
1.893 + {
1.894 + _RopeFunction* __f = (_RopeFunction*)__r;
1.895 + size_t __len = __end - __begin;
1.896 +#ifdef __SYMBIAN32__
1.897 + bool __result = false;
1.898 +#else
1.899 + bool __result;
1.900 +#endif
1.901 + _CharT* __buffer =
1.902 + (_CharT*)__sgi_alloc::allocate(__len * sizeof(_CharT));
1.903 + _STLP_TRY {
1.904 + (*(__f->_M_fn))(__begin, __len, __buffer);
1.905 + __result = __c.operator()(__buffer, __len);
1.906 + __sgi_alloc::deallocate(__buffer, __len * sizeof(_CharT));
1.907 + }
1.908 + _STLP_UNWIND((__sgi_alloc::deallocate(__buffer,
1.909 + __len * sizeof(_CharT))))
1.910 + return __result;
1.911 + }
1.912 + default:
1.913 + _STLP_ASSERT(false)
1.914 + /*NOTREACHED*/
1.915 + return false;
1.916 + }
1.917 +}
1.918 +
1.919 +template <class _CharT> inline bool _Rope_is_simple(_CharT*) { return false; }
1.920 +inline bool _Rope_is_simple(char*) { return true; }
1.921 +# ifdef _STLP_HAS_WCHAR_T
1.922 +inline bool _Rope_is_simple(wchar_t*) { return true; }
1.923 +# endif
1.924 +
1.925 +#if !defined (_STLP_USE_NO_IOSTREAMS)
1.926 +#if defined (_STLP_USE_NEW_IOSTREAMS)
1.927 + template<class _CharT, class _Traits>
1.928 + inline void _Rope_fill(basic_ostream<_CharT, _Traits>& __o, size_t __n)
1.929 +#else
1.930 +inline void _Rope_fill(ostream& __o, size_t __n)
1.931 +#endif
1.932 +{
1.933 + char __f = __o.fill();
1.934 + size_t __i;
1.935 +
1.936 + for (__i = 0; __i < __n; __i++) __o.put(__f);
1.937 +}
1.938 +
1.939 +#if defined (_STLP_USE_NEW_IOSTREAMS)
1.940 + template<class _CharT, class _Traits, class _Alloc>
1.941 + basic_ostream<_CharT, _Traits>& operator<<
1.942 + (basic_ostream<_CharT, _Traits>& __o,
1.943 + const rope<_CharT, _Alloc>& __r)
1.944 +# else
1.945 +template<class _CharT, class _Alloc>
1.946 +ostream& operator<< (ostream& __o, const rope<_CharT, _Alloc>& __r)
1.947 +#endif
1.948 +{
1.949 + size_t __w = __o.width();
1.950 + bool __left = bool(__o.flags() & ios::left);
1.951 + size_t __pad_len;
1.952 + size_t __rope_len = __r.size();
1.953 +# if defined (_STLP_USE_NEW_IOSTREAMS)
1.954 + _Rope_insert_char_consumer<_CharT, _Traits> __c(__o);
1.955 +# else
1.956 + _Rope_insert_char_consumer<_CharT> __c(__o);
1.957 +# endif
1.958 + bool __is_simple = _Rope_is_simple((_CharT*)0);
1.959 +
1.960 + if (__rope_len < __w) {
1.961 + __pad_len = __w - __rope_len;
1.962 + } else {
1.963 + __pad_len = 0;
1.964 + }
1.965 + if (!__is_simple) __o.width(__w/__rope_len);
1.966 + _STLP_TRY {
1.967 + if (__is_simple && !__left && __pad_len > 0) {
1.968 + _Rope_fill(__o, __pad_len);
1.969 + }
1.970 + __r.apply_to_pieces(0, __r.size(), __c);
1.971 + if (__is_simple && __left && __pad_len > 0) {
1.972 + _Rope_fill(__o, __pad_len);
1.973 + }
1.974 + if (!__is_simple)
1.975 + __o.width(__w);
1.976 + }
1.977 + _STLP_UNWIND(if (!__is_simple) __o.width(__w))
1.978 + return __o;
1.979 +}
1.980 +
1.981 +#endif /* NO_IOSTREAMS */
1.982 +
1.983 +template <class _CharT, class _Alloc>
1.984 +_CharT*
1.985 +rope<_CharT,_Alloc>::_S_flatten(_RopeRep* __r,
1.986 + size_t __start, size_t __len,
1.987 + _CharT* __buffer)
1.988 +{
1.989 + _Rope_flatten_char_consumer<_CharT> __c(__buffer);
1.990 + _S_apply_to_pieces(__c, __r, __start, __start + __len);
1.991 + return(__buffer + __len);
1.992 +}
1.993 +
1.994 +template <class _CharT, class _Alloc>
1.995 +size_t
1.996 +rope<_CharT,_Alloc>::find(_CharT __pattern, size_t __start) const
1.997 +{
1.998 + _Rope_find_char_char_consumer<_CharT> __c(__pattern);
1.999 + _S_apply_to_pieces(__c, _M_tree_ptr._M_data, __start, size());
1.1000 + size_type __result_pos = __start + __c._M_count;
1.1001 +# ifndef _STLP_OLD_ROPE_SEMANTICS
1.1002 + if (__result_pos == size()) __result_pos = npos;
1.1003 +# endif
1.1004 + return __result_pos;
1.1005 +}
1.1006 +
1.1007 +template <class _CharT, class _Alloc>
1.1008 +_CharT*
1.1009 +rope<_CharT,_Alloc>::_S_flatten(_Rope_RopeRep<_CharT, _Alloc>* __r, _CharT* __buffer)
1.1010 +{
1.1011 + if (0 == __r) return __buffer;
1.1012 + switch(__r->_M_tag) {
1.1013 + case _RopeRep::_S_concat:
1.1014 + {
1.1015 + _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1.1016 + _RopeRep* __left = __c->_M_left;
1.1017 + _RopeRep* __right = __c->_M_right;
1.1018 + _CharT* __rest = _S_flatten(__left, __buffer);
1.1019 + return _S_flatten(__right, __rest);
1.1020 + }
1.1021 + case _RopeRep::_S_leaf:
1.1022 + {
1.1023 + _RopeLeaf* __l = (_RopeLeaf*)__r;
1.1024 + return copy_n(__l->_M_data, __l->_M_size._M_data, __buffer).second;
1.1025 + }
1.1026 + case _RopeRep::_S_function:
1.1027 + case _RopeRep::_S_substringfn:
1.1028 + // We dont yet do anything with substring nodes.
1.1029 + // This needs to be fixed before ropefiles will work well.
1.1030 + {
1.1031 + _RopeFunction* __f = (_RopeFunction*)__r;
1.1032 + (*(__f->_M_fn))(0, __f->_M_size._M_data, __buffer);
1.1033 + return __buffer + __f->_M_size._M_data;
1.1034 + }
1.1035 + default:
1.1036 + _STLP_ASSERT(false)
1.1037 + /*NOTREACHED*/
1.1038 + return 0;
1.1039 + }
1.1040 +}
1.1041 +
1.1042 +
1.1043 +// This needs work for _CharT != char
1.1044 +template <class _CharT, class _Alloc>
1.1045 +void
1.1046 +rope<_CharT,_Alloc>::_S_dump(_RopeRep* __r, int __indent)
1.1047 +{
1.1048 + for (int __i = 0; __i < __indent; __i++) putchar(' ');
1.1049 + if (0 == __r) {
1.1050 + printf("NULL\n"); return;
1.1051 + }
1.1052 + if (_RopeRep::_S_concat == __r->_M_tag) {
1.1053 + _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1.1054 + _RopeRep* __left = __c->_M_left;
1.1055 + _RopeRep* __right = __c->_M_right;
1.1056 +
1.1057 +# ifdef __GC
1.1058 + printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
1.1059 + __r, __r->_M_depth, __r->_M_size._M_data, __r->_M_is_balanced? "" : "not");
1.1060 +# else
1.1061 + printf("Concatenation %p (rc = %ld, depth = %d, "
1.1062 + "len = %ld, %s balanced)\n",
1.1063 + __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size._M_data,
1.1064 + __r->_M_is_balanced? "" : "not");
1.1065 +# endif
1.1066 + _S_dump(__left, __indent + 2);
1.1067 + _S_dump(__right, __indent + 2);
1.1068 + return;
1.1069 + } else {
1.1070 + const char* __kind;
1.1071 +
1.1072 + switch (__r->_M_tag) {
1.1073 + case _RopeRep::_S_leaf:
1.1074 + __kind = "Leaf";
1.1075 + break;
1.1076 + case _RopeRep::_S_function:
1.1077 + __kind = "Function";
1.1078 + break;
1.1079 + case _RopeRep::_S_substringfn:
1.1080 + __kind = "Function representing substring";
1.1081 + break;
1.1082 + default:
1.1083 + __kind = "(corrupted kind field!)";
1.1084 + }
1.1085 +# ifdef __GC
1.1086 + printf("%s %p (depth = %d, len = %ld) ",
1.1087 + __kind, __r, __r->_M_depth, __r->_M_size._M_data);
1.1088 +# else
1.1089 + printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
1.1090 + __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size._M_data);
1.1091 +# endif
1.1092 + if (_S_is_one_byte_char_type((_CharT*)0)) {
1.1093 + const int __max_len = 40;
1.1094 + _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len));
1.1095 + _CharT __buffer[__max_len + 1];
1.1096 + bool __too_big = __r->_M_size._M_data > __prefix->_M_size._M_data;
1.1097 +
1.1098 + _S_flatten(__prefix, __buffer);
1.1099 + __buffer[__prefix->_M_size._M_data] = _S_eos((_CharT*)0);
1.1100 + printf("%s%s\n",
1.1101 + (char*)__buffer, __too_big? "...\n" : "\n");
1.1102 + } else {
1.1103 + printf("\n");
1.1104 + }
1.1105 + }
1.1106 +}
1.1107 +
1.1108 +# define __ROPE_TABLE_BODY = { \
1.1109 +/* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21, \
1.1110 +/* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377, \
1.1111 +/* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181, \
1.1112 +/* 18 */6765ul, /* 19 */10946ul, /* 20 */17711ul, /* 21 */28657ul, /* 22 */46368ul, \
1.1113 +/* 23 */75025ul, /* 24 */121393ul, /* 25 */196418ul, /* 26 */317811ul, \
1.1114 +/* 27 */514229ul, /* 28 */832040ul, /* 29 */1346269ul, /* 30 */2178309ul, \
1.1115 +/* 31 */3524578ul, /* 32 */5702887ul, /* 33 */9227465ul, /* 34 */14930352ul, \
1.1116 +/* 35 */24157817ul, /* 36 */39088169ul, /* 37 */63245986ul, /* 38 */102334155ul, \
1.1117 +/* 39 */165580141ul, /* 40 */267914296ul, /* 41 */433494437ul, \
1.1118 +/* 42 */701408733ul, /* 43 */1134903170ul, /* 44 */1836311903ul, \
1.1119 +/* 45 */2971215073ul }
1.1120 +
1.1121 +# if ( _STLP_STATIC_TEMPLATE_DATA > 0 )
1.1122 +template <class _CharT, class _Alloc>
1.1123 +const unsigned long
1.1124 +rope<_CharT,_Alloc>::_S_min_len[__ROPE_DEPTH_SIZE] __ROPE_TABLE_BODY ;
1.1125 +# else
1.1126 +__DECLARE_INSTANCE(const unsigned long,
1.1127 + crope::_S_min_len[__ROPE_DEPTH_SIZE],
1.1128 + __ROPE_TABLE_BODY);
1.1129 +# ifndef _STLP_NO_WCHAR_T
1.1130 +__DECLARE_INSTANCE(const unsigned long,
1.1131 + wrope::_S_min_len[__ROPE_DEPTH_SIZE],
1.1132 + __ROPE_TABLE_BODY);
1.1133 +# endif
1.1134 +# endif
1.1135 +# undef __ROPE_DEPTH_SIZE
1.1136 +# undef __ROPE_MAX_DEPTH
1.1137 +# undef __ROPE_TABLE_BODY
1.1138 +
1.1139 +// These are Fibonacci numbers < 2**32.
1.1140 +
1.1141 +template <class _CharT, class _Alloc>
1.1142 +__RopeRep__*
1.1143 +rope<_CharT,_Alloc>::_S_balance(_RopeRep* __r)
1.1144 +{
1.1145 + _RopeRep* __forest[_RopeRep::_S_max_rope_depth + 1];
1.1146 + _RopeRep* __result = 0;
1.1147 + int __i;
1.1148 + // Invariant:
1.1149 + // The concatenation of forest in descending order is equal to __r.
1.1150 + // __forest[__i]._M_size._M_data >= _S_min_len[__i]
1.1151 + // __forest[__i]._M_depth = __i
1.1152 + // References from forest are included in refcount.
1.1153 +
1.1154 + for (__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i)
1.1155 + __forest[__i] = 0;
1.1156 + _STLP_TRY {
1.1157 + _S_add_to_forest(__r, __forest);
1.1158 + for (__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i)
1.1159 + if (0 != __forest[__i]) {
1.1160 +# ifndef __GC
1.1161 + _Self_destruct_ptr __old(__result);
1.1162 +# endif
1.1163 + __result = _S_concat_rep(__forest[__i], __result);
1.1164 + __forest[__i]->_M_unref_nonnil();
1.1165 +# if !defined(__GC) && defined(_STLP_USE_EXCEPTIONS)
1.1166 + __forest[__i] = 0;
1.1167 +# endif
1.1168 + }
1.1169 + }
1.1170 + _STLP_UNWIND(for(__i = 0; __i <= _RopeRep::_S_max_rope_depth; __i++)
1.1171 + _S_unref(__forest[__i]))
1.1172 + if (__result->_M_depth > _RopeRep::_S_max_rope_depth) {
1.1173 + __stl_throw_range_error("rope too long");
1.1174 + }
1.1175 + return(__result);
1.1176 +}
1.1177 +
1.1178 +
1.1179 +template <class _CharT, class _Alloc>
1.1180 +void
1.1181 +rope<_CharT,_Alloc>::_S_add_to_forest(_RopeRep* __r, _RopeRep** __forest)
1.1182 +{
1.1183 + if (__r -> _M_is_balanced) {
1.1184 + _S_add_leaf_to_forest(__r, __forest);
1.1185 + return;
1.1186 + }
1.1187 + _STLP_ASSERT(__r->_M_tag == _RopeRep::_S_concat)
1.1188 + {
1.1189 + _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1.1190 +
1.1191 + _S_add_to_forest(__c->_M_left, __forest);
1.1192 + _S_add_to_forest(__c->_M_right, __forest);
1.1193 + }
1.1194 +}
1.1195 +
1.1196 +
1.1197 +template <class _CharT, class _Alloc>
1.1198 +void
1.1199 +rope<_CharT,_Alloc>::_S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest)
1.1200 +{
1.1201 + _RopeRep* __insertee; // included in refcount
1.1202 + _RopeRep* __too_tiny = 0; // included in refcount
1.1203 + int __i; // forest[0..__i-1] is empty
1.1204 + size_t __s = __r->_M_size._M_data;
1.1205 +
1.1206 + for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i) {
1.1207 + if (0 != __forest[__i]) {
1.1208 +# ifndef __GC
1.1209 + _Self_destruct_ptr __old(__too_tiny);
1.1210 +# endif
1.1211 + __too_tiny = _S_concat_and_set_balanced(__forest[__i], __too_tiny);
1.1212 + __forest[__i]->_M_unref_nonnil();
1.1213 + __forest[__i] = 0;
1.1214 + }
1.1215 + }
1.1216 + {
1.1217 +# ifndef __GC
1.1218 + _Self_destruct_ptr __old(__too_tiny);
1.1219 +# endif
1.1220 + __insertee = _S_concat_and_set_balanced(__too_tiny, __r);
1.1221 + }
1.1222 + // Too_tiny dead, and no longer included in refcount.
1.1223 + // Insertee is live and included.
1.1224 + _STLP_ASSERT(_S_is_almost_balanced(__insertee))
1.1225 + _STLP_ASSERT(__insertee->_M_depth <= __r->_M_depth + 1)
1.1226 + for (;; ++__i) {
1.1227 + if (0 != __forest[__i]) {
1.1228 +# ifndef __GC
1.1229 + _Self_destruct_ptr __old(__insertee);
1.1230 +# endif
1.1231 + __insertee = _S_concat_and_set_balanced(__forest[__i], __insertee);
1.1232 + __forest[__i]->_M_unref_nonnil();
1.1233 + __forest[__i] = 0;
1.1234 + _STLP_ASSERT(_S_is_almost_balanced(__insertee))
1.1235 + }
1.1236 + _STLP_ASSERT(_S_min_len[__i] <= __insertee->_M_size._M_data)
1.1237 + _STLP_ASSERT(__forest[__i] == 0)
1.1238 + if (__i == _RopeRep::_S_max_rope_depth ||
1.1239 + __insertee->_M_size._M_data < _S_min_len[__i+1]) {
1.1240 + __forest[__i] = __insertee;
1.1241 + // refcount is OK since __insertee is now dead.
1.1242 + return;
1.1243 + }
1.1244 + }
1.1245 +}
1.1246 +
1.1247 +template <class _CharT, class _Alloc>
1.1248 +_CharT
1.1249 +rope<_CharT,_Alloc>::_S_fetch(_RopeRep* __r, size_type __i)
1.1250 +{
1.1251 + __GC_CONST _CharT* __cstr = __r->_M_c_string;
1.1252 +
1.1253 + _STLP_ASSERT(__i < __r->_M_size._M_data)
1.1254 + if (0 != __cstr) return __cstr[__i];
1.1255 + for(;;) {
1.1256 + switch(__r->_M_tag) {
1.1257 + case _RopeRep::_S_concat:
1.1258 + {
1.1259 + _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1.1260 + _RopeRep* __left = __c->_M_left;
1.1261 + size_t __left_len = __left->_M_size._M_data;
1.1262 +
1.1263 + if (__i >= __left_len) {
1.1264 + __i -= __left_len;
1.1265 + __r = __c->_M_right;
1.1266 + } else {
1.1267 + __r = __left;
1.1268 + }
1.1269 + }
1.1270 + break;
1.1271 + case _RopeRep::_S_leaf:
1.1272 + {
1.1273 + _RopeLeaf* __l = (_RopeLeaf*)__r;
1.1274 + return __l->_M_data[__i];
1.1275 + }
1.1276 + case _RopeRep::_S_function:
1.1277 + case _RopeRep::_S_substringfn:
1.1278 + {
1.1279 + _RopeFunction* __f = (_RopeFunction*)__r;
1.1280 + _CharT __result;
1.1281 +
1.1282 + (*(__f->_M_fn))(__i, 1, &__result);
1.1283 + return __result;
1.1284 + }
1.1285 + }
1.1286 + }
1.1287 +#if defined(_STLP_NEED_UNREACHABLE_RETURN)
1.1288 + return 0;
1.1289 +#endif
1.1290 +}
1.1291 +
1.1292 +# ifndef __GC
1.1293 +// Return a uniquely referenced character slot for the given
1.1294 +// position, or 0 if that's not possible.
1.1295 +template <class _CharT, class _Alloc>
1.1296 +_CharT*
1.1297 +rope<_CharT,_Alloc>::_S_fetch_ptr(_RopeRep* __r, size_type __i)
1.1298 +{
1.1299 + _RopeRep* __clrstack[_RopeRep::_S_max_rope_depth];
1.1300 + size_t __csptr = 0;
1.1301 +
1.1302 + for(;;) {
1.1303 + if (__r->_M_ref_count > 1) return 0;
1.1304 + switch(__r->_M_tag) {
1.1305 + case _RopeRep::_S_concat:
1.1306 + {
1.1307 + _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1.1308 + _RopeRep* __left = __c->_M_left;
1.1309 + size_t __left_len = __left->_M_size._M_data;
1.1310 +
1.1311 + if (__c->_M_c_string != 0) __clrstack[__csptr++] = __c;
1.1312 + if (__i >= __left_len) {
1.1313 + __i -= __left_len;
1.1314 + __r = __c->_M_right;
1.1315 + } else {
1.1316 + __r = __left;
1.1317 + }
1.1318 + }
1.1319 + break;
1.1320 + case _RopeRep::_S_leaf:
1.1321 + {
1.1322 + _RopeLeaf* __l = (_RopeLeaf*)__r;
1.1323 + if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0)
1.1324 + __clrstack[__csptr++] = __l;
1.1325 + while (__csptr > 0) {
1.1326 + -- __csptr;
1.1327 + _RopeRep* __d = __clrstack[__csptr];
1.1328 + __d->_M_free_c_string();
1.1329 + __d->_M_c_string = 0;
1.1330 + }
1.1331 + return __l->_M_data + __i;
1.1332 + }
1.1333 + case _RopeRep::_S_function:
1.1334 + case _RopeRep::_S_substringfn:
1.1335 + return 0;
1.1336 + }
1.1337 + }
1.1338 +#if defined(_STLP_NEED_UNREACHABLE_RETURN)
1.1339 + return 0;
1.1340 +#endif
1.1341 +
1.1342 +}
1.1343 +# endif /* __GC */
1.1344 +
1.1345 +// The following could be implemented trivially using
1.1346 +// lexicographical_compare_3way.
1.1347 +// We do a little more work to avoid dealing with rope iterators for
1.1348 +// flat strings.
1.1349 +template <class _CharT, class _Alloc>
1.1350 +int
1.1351 +rope<_CharT,_Alloc>::_S_compare (const _RopeRep* __left,
1.1352 + const _RopeRep* __right)
1.1353 +{
1.1354 + size_t __left_len;
1.1355 + size_t __right_len;
1.1356 +
1.1357 + if (0 == __right) return 0 != __left;
1.1358 + if (0 == __left) return -1;
1.1359 + __left_len = __left->_M_size._M_data;
1.1360 + __right_len = __right->_M_size._M_data;
1.1361 + if (_RopeRep::_S_leaf == __left->_M_tag) {
1.1362 + _RopeLeaf* __l = (_RopeLeaf*) __left;
1.1363 + if (_RopeRep::_S_leaf == __right->_M_tag) {
1.1364 + _RopeLeaf* __r = (_RopeLeaf*) __right;
1.1365 + return lexicographical_compare_3way(
1.1366 + __l->_M_data, __l->_M_data + __left_len,
1.1367 + __r->_M_data, __r->_M_data + __right_len);
1.1368 + } else {
1.1369 + const_iterator __rstart(__right, 0);
1.1370 + const_iterator __rend(__right, __right_len);
1.1371 + return lexicographical_compare_3way(
1.1372 + __l->_M_data, __l->_M_data + __left_len,
1.1373 + __rstart, __rend);
1.1374 + }
1.1375 + } else {
1.1376 + const_iterator __lstart(__left, 0);
1.1377 + const_iterator __lend(__left, __left_len);
1.1378 + if (_RopeRep::_S_leaf == __right->_M_tag) {
1.1379 + _RopeLeaf* __r = (_RopeLeaf*) __right;
1.1380 + return lexicographical_compare_3way(
1.1381 + __lstart, __lend,
1.1382 + __r->_M_data, __r->_M_data + __right_len);
1.1383 + } else {
1.1384 + const_iterator __rstart(__right, 0);
1.1385 + const_iterator __rend(__right, __right_len);
1.1386 + return lexicographical_compare_3way(
1.1387 + __lstart, __lend,
1.1388 + __rstart, __rend);
1.1389 + }
1.1390 + }
1.1391 +}
1.1392 +
1.1393 +// Assignment to reference proxies.
1.1394 +template <class _CharT, class _Alloc>
1.1395 +_Rope_char_ref_proxy<_CharT, _Alloc>&
1.1396 +_Rope_char_ref_proxy<_CharT, _Alloc>::operator= (_CharT __c) {
1.1397 + _RopeRep* __old = _M_root->_M_tree_ptr._M_data;
1.1398 +# ifndef __GC
1.1399 + // First check for the case in which everything is uniquely
1.1400 + // referenced. In that case we can do this destructively.
1.1401 + _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos);
1.1402 + if (0 != __ptr) {
1.1403 + *__ptr = __c;
1.1404 + return *this;
1.1405 + }
1.1406 +# endif
1.1407 + _Self_destruct_ptr __left(
1.1408 + _My_rope::_S_substring(__old, 0, _M_pos));
1.1409 + _Self_destruct_ptr __right(
1.1410 + _My_rope::_S_substring(__old, _M_pos+1, __old->_M_size._M_data));
1.1411 + _Self_destruct_ptr __result_left(
1.1412 + _My_rope::_S_destr_concat_char_iter(__left, &__c, 1));
1.1413 +
1.1414 +# ifndef __GC
1.1415 + _STLP_ASSERT(__left == __result_left || 1 == __result_left->_M_ref_count)
1.1416 +# endif
1.1417 + _RopeRep* __result =
1.1418 + _My_rope::_S_concat_rep(__result_left, __right);
1.1419 +# ifndef __GC
1.1420 + _STLP_ASSERT(1 <= __result->_M_ref_count)
1.1421 + _RopeRep::_S_unref(__old);
1.1422 +# endif
1.1423 + _M_root->_M_tree_ptr._M_data = __result;
1.1424 + return *this;
1.1425 +}
1.1426 +
1.1427 +template <class _CharT, class _Alloc>
1.1428 +_Rope_char_ptr_proxy<_CharT, _Alloc>
1.1429 +_Rope_char_ref_proxy<_CharT, _Alloc>::operator& () const {
1.1430 + return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this);
1.1431 +}
1.1432 +
1.1433 +# if ( _STLP_STATIC_TEMPLATE_DATA > 0 )
1.1434 +template<class _CharT, class _Alloc>
1.1435 +_CharT rope<_CharT,_Alloc>::_S_empty_c_str[1] = { _CharT() };
1.1436 +# else
1.1437 +__DECLARE_INSTANCE(char, crope::_S_empty_c_str[1], ={0});
1.1438 +# ifdef _STLP_HAS_WCHAR_T
1.1439 +__DECLARE_INSTANCE(wchar_t, wrope::_S_empty_c_str[1], ={0});
1.1440 +# endif /* _STLP_HAS_WCHAR_T */
1.1441 +# endif /* _STLP_STATIC_TEMPLATE_DATA */
1.1442 +// # endif
1.1443 +
1.1444 +template<class _CharT, class _Alloc>
1.1445 +const _CharT* rope<_CharT,_Alloc>::c_str() const {
1.1446 + if (0 == _M_tree_ptr._M_data) {
1.1447 + _S_empty_c_str[0] = _S_eos((_CharT*)0); // Possibly redundant,
1.1448 + // but probably fast.
1.1449 + return _S_empty_c_str;
1.1450 + }
1.1451 + __GC_CONST _CharT* __old_c_string = _M_tree_ptr._M_data->_M_c_string;
1.1452 + if (0 != __old_c_string) return(__old_c_string);
1.1453 + size_t __s = size();
1.1454 + _CharT* __result = _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_tree_ptr, _CharT).allocate(__s + 1);
1.1455 + _S_flatten(_M_tree_ptr._M_data, __result);
1.1456 + __result[__s] = _S_eos((_CharT*)0);
1.1457 +# ifdef __GC
1.1458 + _M_tree_ptr._M_data->_M_c_string = __result;
1.1459 +# else
1.1460 + if ((__old_c_string = (__GC_CONST _CharT*)
1.1461 + _Atomic_swap((__stl_atomic_t *)(&(_M_tree_ptr._M_data->_M_c_string)),
1.1462 + (__stl_atomic_t)__result)) != 0) {
1.1463 + // It must have been added in the interim. Hence it had to have been
1.1464 + // separately allocated. Deallocate the old copy, since we just
1.1465 + // replaced it.
1.1466 + _STLP_STD::_Destroy(__old_c_string, __old_c_string + __s + 1);
1.1467 + _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_tree_ptr, _CharT).deallocate(__old_c_string, __s + 1);
1.1468 + }
1.1469 +# endif
1.1470 + return(__result);
1.1471 +}
1.1472 +
1.1473 +template<class _CharT, class _Alloc>
1.1474 +const _CharT* rope<_CharT,_Alloc>::replace_with_c_str() {
1.1475 + if (0 == _M_tree_ptr._M_data) {
1.1476 + _S_empty_c_str[0] = _S_eos((_CharT*)0);
1.1477 + return _S_empty_c_str;
1.1478 + }
1.1479 + __GC_CONST _CharT* __old_c_string = _M_tree_ptr._M_data->_M_c_string;
1.1480 + if (_RopeRep::_S_leaf == _M_tree_ptr._M_data->_M_tag && 0 != __old_c_string) {
1.1481 + return(__old_c_string);
1.1482 + }
1.1483 + size_t __s = size();
1.1484 + _CharT* __result = _M_tree_ptr.allocate(_S_rounded_up_size(__s));
1.1485 + _S_flatten(_M_tree_ptr._M_data, __result);
1.1486 + __result[__s] = _S_eos((_CharT*)0);
1.1487 + _M_tree_ptr._M_data->_M_unref_nonnil();
1.1488 + _M_tree_ptr._M_data = _S_new_RopeLeaf(__result, __s, get_allocator());
1.1489 + return(__result);
1.1490 +}
1.1491 +
1.1492 +// Algorithm specializations. More should be added.
1.1493 +
1.1494 +#ifndef _STLP_MSVC
1.1495 +// I couldn't get this to work with VC++
1.1496 +template<class _CharT,class _Alloc>
1.1497 +void
1.1498 +_Rope_rotate(_Rope_iterator<_CharT,_Alloc> __first,
1.1499 + _Rope_iterator<_CharT,_Alloc> __middle,
1.1500 + _Rope_iterator<_CharT,_Alloc> __last)
1.1501 +{
1.1502 + _STLP_ASSERT(__first.container() == __middle.container()
1.1503 + && __middle.container() == __last.container())
1.1504 + rope<_CharT,_Alloc>& __r(__first.container());
1.1505 + rope<_CharT,_Alloc> __prefix = __r.substr(0, __first.index());
1.1506 + rope<_CharT,_Alloc> __suffix =
1.1507 + __r.substr(__last.index(), __r.size() - __last.index());
1.1508 + rope<_CharT,_Alloc> __part1 =
1.1509 + __r.substr(__middle.index(), __last.index() - __middle.index());
1.1510 + rope<_CharT,_Alloc> __part2 =
1.1511 + __r.substr(__first.index(), __middle.index() - __first.index());
1.1512 + __r = __prefix;
1.1513 + __r += __part1;
1.1514 + __r += __part2;
1.1515 + __r += __suffix;
1.1516 +}
1.1517 +
1.1518 +
1.1519 +# if 0
1.1520 +// Probably not useful for several reasons:
1.1521 +// - for SGIs 7.1 compiler and probably some others,
1.1522 +// this forces lots of rope<wchar_t, ...> instantiations, creating a
1.1523 +// code bloat and compile time problem. (Fixed in 7.2.)
1.1524 +// - wchar_t is 4 bytes wide on most UNIX platforms, making it unattractive
1.1525 +// for unicode strings. Unsigned short may be a better character
1.1526 +// type.
1.1527 +inline void rotate(
1.1528 + _Rope_iterator<wchar_t,_STLP_DEFAULT_ALLOCATOR(char) > __first,
1.1529 + _Rope_iterator<wchar_t,_STLP_DEFAULT_ALLOCATOR(char) > __middle,
1.1530 + _Rope_iterator<wchar_t,_STLP_DEFAULT_ALLOCATOR(char) > __last) {
1.1531 + _Rope_rotate(__first, __middle, __last);
1.1532 +}
1.1533 +# endif
1.1534 +#endif /* _STLP_MSVC */
1.1535 +
1.1536 +# undef __RopeLeaf__
1.1537 +# undef __RopeRep__
1.1538 +# undef __RopeLeaf
1.1539 +# undef __RopeRep
1.1540 +# undef size_type
1.1541 +
1.1542 +_STLP_END_NAMESPACE
1.1543 +
1.1544 +# endif /* ROPEIMPL_H */
1.1545 +
1.1546 +// Local Variables:
1.1547 +// mode:C++
1.1548 +// End: