1.1 --- a/epoc32/include/stdapis/stlport/stl/_rope.c Tue Mar 16 16:12:26 2010 +0000
1.2 +++ /dev/null Thu Jan 01 00:00:00 1970 +0000
1.3 @@ -1,1545 +0,0 @@
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: