ReactOS 0.4.15-dev-7788-g1ad9096
_rope.c
Go to the documentation of this file.
1/*
2 * Copyright (c) 1996,1997
3 * Silicon Graphics Computer Systems, Inc.
4 *
5 * Copyright (c) 1999
6 * Boris Fomitchev
7 *
8 * This material is provided "as is", with absolutely no warranty expressed
9 * or implied. Any use is at your own risk.
10 *
11 * Permission to use or copy this software for any purpose is hereby granted
12 * without fee, provided the above notices are retained on all copies.
13 * Permission to modify the code and to distribute modified code is granted,
14 * provided the above notices are retained, and a notice that the code was
15 * modified is included with the above copyright notice.
16 *
17 */
18
19/* NOTE: This is an internal header file, included by other STL headers.
20 * You should not attempt to use it directly.
21 */
22
23// Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
24// if necessary. Assumes path_end[leaf_index] and leaf_pos are correct.
25// Results in a valid buf_ptr if the iterator can be legitimately
26// dereferenced.
27#ifndef _STLP_ROPEIMPL_H
28#define _STLP_ROPEIMPL_H
29
30#ifndef _STLP_INTERNAL_ROPE_H
31# include <stl/_rope.h>
32#endif
33
34#ifndef _STLP_INTERNAL_CSTDIO
35# include <stl/_cstdio.h>
36#endif
37
38#if !defined (_STLP_USE_NO_IOSTREAMS)
39# ifndef _STLP_INTERNAL_OSTREAM_H
40# include <stl/_ostream.h>
41# endif
42
43# ifndef _STLP_INTERNAL_ISTREAM
44# include <stl/_istream.h>
45# endif
46#endif
47
48#include <stl/_range_errors.h>
49
51
52#if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
53# define __allocator__ _Alloc
54#else
55# define __allocator__ allocator_type
56#endif
57
58template<class _CharT, class _Alloc>
60 : _Rope_iterator_base<_CharT,_Alloc>(__r->_M_tree_ptr._M_data, __pos),
61 _M_root_rope(__r) { _RopeRep::_S_ref(this->_M_root); }
62
63template<class _CharT, class _Alloc>
65 _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr._M_data, __pos),
66 _M_root_rope(&__r) {
67#if !defined (__DMC__)
68 _RopeRep::_S_ref(this->_M_root); if (!(__r.empty()))_S_setcache(*this);
69#else
71 _RopeRep::_S_ref(this->_M_root); if (!(__r.empty()))_S_setcache(*__x);
72#endif
73}
74
75template<class _CharT, class _Alloc>
77 _CharT* __cstr = _M_c_string;
78 if (0 != __cstr) {
79 size_t _p_size = _M_size._M_data + 1;
80 _STLP_STD::_Destroy_Range(__cstr, __cstr + _p_size);
81 _M_size.deallocate(__cstr, _p_size);
82 }
83}
84
85// Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
86// if necessary. Assumes _M_path_end[leaf_index] and leaf_pos are correct.
87// Results in a valid buf_ptr if the iterator can be legitimately
88// dereferenced.
89template <class _CharT, class _Alloc>
92 const _RopeRep* __leaf = __x._M_path_end._M_data[__x._M_leaf_index];
93 size_t __leaf_pos = __x._M_leaf_pos;
94 size_t __pos = __x._M_current_pos;
95
96 switch(__leaf->_M_tag) {
97 case _RopeRep::_S_leaf:
98 typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf;
99 __x._M_buf_start = __STATIC_CAST(const _RopeLeaf*, __leaf)->_M_data;
100 __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos);
101 __x._M_buf_end = __x._M_buf_start + __leaf->_M_size._M_data;
102 break;
103 case _RopeRep::_S_function:
104 case _RopeRep::_S_substringfn:
105 {
106 size_t __len = _S_iterator_buf_len;
107 size_t __buf_start_pos = __leaf_pos;
108 size_t __leaf_end = __leaf_pos + __leaf->_M_size._M_data;
109 typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction;
110 char_producer<_CharT>* __fn = __STATIC_CAST(const _RopeFunction*, __leaf)->_M_fn;
111
112 if (__buf_start_pos + __len <= __pos) {
113 __buf_start_pos = __pos - __len/4;
114 if (__buf_start_pos + __len > __leaf_end) {
115 __buf_start_pos = __leaf_end - __len;
116 }
117 }
118 if (__buf_start_pos + __len > __leaf_end) {
119 __len = __leaf_end - __buf_start_pos;
120 }
121 (*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf._M_data);
122 __x._M_buf_ptr = __x._M_tmp_buf._M_data + (__pos - __buf_start_pos);
123 __x._M_buf_start = __x._M_tmp_buf._M_data;
124 __x._M_buf_end = __x._M_tmp_buf._M_data + __len;
125 }
126 break;
127 default:
128 _STLP_ASSERT(0)
129 ;
130 }
131}
132
133// Set path and buffer inside a rope iterator. We assume that
134// pos and root are already set.
135template <class _CharT, class _Alloc>
138 const _RopeRep* __path[_RopeRep::_S_max_rope_depth+1];
139 const _RopeRep* __curr_rope;
140 int __curr_depth = -1; /* index into path */
141 size_t __curr_start_pos = 0;
142 size_t __pos = __x._M_current_pos;
143 unsigned char __dirns = 0; // Bit vector marking right turns in the path
144
145 _STLP_ASSERT(__pos <= __x._M_root->_M_size._M_data)
146 if (__pos >= __x._M_root->_M_size._M_data) {
147 __x._M_buf_ptr = 0;
148 return;
149 }
150 __curr_rope = __x._M_root;
151 if (0 != __curr_rope->_M_c_string) {
152 /* Treat the root as a leaf. */
153 __x._M_buf_start = __curr_rope->_M_c_string;
154 __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size._M_data;
155 __x._M_buf_ptr = __curr_rope->_M_c_string + __pos;
156 __x._M_path_end._M_data[0] = __curr_rope;
157 __x._M_leaf_index = 0;
158 __x._M_leaf_pos = 0;
159 return;
160 }
161 for(;;) {
162 ++__curr_depth;
163 _STLP_ASSERT(__curr_depth <= _RopeRep::_S_max_rope_depth)
164 __path[__curr_depth] = __curr_rope;
165 switch(__curr_rope->_M_tag) {
166 case _RopeRep::_S_leaf:
167 case _RopeRep::_S_function:
168 case _RopeRep::_S_substringfn:
169 __x._M_leaf_pos = __curr_start_pos;
170 goto done;
171 case _RopeRep::_S_concat:
172 {
173 const _RopeConcat* __c = __STATIC_CAST(const _RopeConcat*, __curr_rope);
174 _RopeRep* __left = __c->_M_left;
175 size_t __left_len = __left->_M_size._M_data;
176
177 __dirns <<= 1;
178 if (__pos >= __curr_start_pos + __left_len) {
179 __dirns |= 1;
180 __curr_rope = __c->_M_right;
181 __curr_start_pos += __left_len;
182 } else {
183 __curr_rope = __left;
184 }
185 }
186 break;
187 }
188 }
189done:
190 // Copy last section of path into _M_path_end.
191 {
192 int __i = -1;
193 int __j = __curr_depth + 1 - _S_path_cache_len;
194
195 if (__j < 0) __j = 0;
196 while (__j <= __curr_depth) {
197 __x._M_path_end._M_data[++__i] = __path[__j++];
198 }
199 __x._M_leaf_index = __i;
200 }
201 __x._M_path_directions = __dirns;
202 _S_setbuf(__x);
203}
204
205// Specialized version of the above. Assumes that
206// the path cache is valid for the previous position.
207template <class _CharT, class _Alloc>
210 int __current_index = __x._M_leaf_index;
211 const _RopeRep* __current_node = __x._M_path_end._M_data[__current_index];
212 size_t __len = __current_node->_M_size._M_data;
213 size_t __node_start_pos = __x._M_leaf_pos;
214 unsigned char __dirns = __x._M_path_directions;
215 const _RopeConcat* __c;
216
218 if (__x._M_current_pos - __node_start_pos < __len) {
219 /* More stuff in this leaf, we just didn't cache it. */
220 _S_setbuf(__x);
221 return;
222 }
223 _STLP_ASSERT(__node_start_pos + __len == __x._M_current_pos)
224 // node_start_pos is starting position of last_node.
225 while (--__current_index >= 0) {
226 if (!(__dirns & 1) /* Path turned left */)
227 break;
228 __current_node = __x._M_path_end._M_data[__current_index];
229 __c = __STATIC_CAST(const _RopeConcat*, __current_node);
230 // Otherwise we were in the right child. Thus we should pop
231 // the concatenation node.
232 __node_start_pos -= __c->_M_left->_M_size._M_data;
233 __dirns >>= 1;
234 }
235 if (__current_index < 0) {
236 // We underflowed the cache. Punt.
237 _S_setcache(__x);
238 return;
239 }
240 __current_node = __x._M_path_end._M_data[__current_index];
241 __c = __STATIC_CAST(const _RopeConcat*, __current_node);
242 // current_node is a concatenation node. We are positioned on the first
243 // character in its right child.
244 // node_start_pos is starting position of current_node.
245 __node_start_pos += __c->_M_left->_M_size._M_data;
246 __current_node = __c->_M_right;
247 __x._M_path_end._M_data[++__current_index] = __current_node;
248 __dirns |= 1;
249 while (_RopeRep::_S_concat == __current_node->_M_tag) {
250 ++__current_index;
251 if (_S_path_cache_len == __current_index) {
252 int __i;
253 for (__i = 0; __i < _S_path_cache_len-1; ++__i) {
254 __x._M_path_end._M_data[__i] = __x._M_path_end._M_data[__i+1];
255 }
256 --__current_index;
257 }
258 __current_node = __STATIC_CAST(const _RopeConcat*, __current_node)->_M_left;
259 __x._M_path_end._M_data[__current_index] = __current_node;
260 __dirns <<= 1;
261 // node_start_pos is unchanged.
262 }
263 __x._M_leaf_index = __current_index;
264 __x._M_leaf_pos = __node_start_pos;
265 __x._M_path_directions = __dirns;
266 _S_setbuf(__x);
267}
268
269template <class _CharT, class _Alloc>
271 _M_current_pos += __n;
272 if (0 != _M_buf_ptr) {
273 size_t __chars_left = _M_buf_end - _M_buf_ptr;
274 if (__chars_left > __n) {
275 _M_buf_ptr += __n;
276 } else if (__chars_left == __n) {
277 _M_buf_ptr += __n;
278 _S_setcache_for_incr(*this);
279 } else {
280 _M_buf_ptr = 0;
281 }
282 }
283}
284
285template <class _CharT, class _Alloc>
287 if (0 != _M_buf_ptr) {
288 size_t __chars_left = _M_buf_ptr - _M_buf_start;
289 if (__chars_left >= __n) {
290 _M_buf_ptr -= __n;
291 } else {
292 _M_buf_ptr = 0;
293 }
294 }
295 _M_current_pos -= __n;
296}
297
298template <class _CharT, class _Alloc>
300 if (_M_root_rope->_M_tree_ptr._M_data != this->_M_root) {
301 // _Rope was modified. Get things fixed up.
302 _RopeRep::_S_unref(this->_M_root);
303 this->_M_root = _M_root_rope->_M_tree_ptr._M_data;
304 _RopeRep::_S_ref(this->_M_root);
305 this->_M_buf_ptr = 0;
306 }
307}
308
309// There are several reasons for not doing this with virtual destructors
310// and a class specific delete operator:
311// - A class specific delete operator can't easily get access to
312// allocator instances if we need them.
313// - Any virtual function would need a 4 or byte vtable pointer;
314// this only requires a one byte tag per object.
315template <class _CharT, class _Alloc>
317 switch (_M_tag) {
318 case _S_leaf:
319 {
320 typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf;
321 _RopeLeaf* __l = __STATIC_CAST(_RopeLeaf*, this);
322 _STLP_STD::_Destroy(__l); // ->_Rope_RopeLeaf<_CharT,_Alloc>::~_Rope_RopeLeaf();
324 _RopeLeaf).deallocate(__l, 1);
325 break;
326 }
327 case _S_concat:
328 {
329 typedef _Rope_RopeConcatenation<_CharT, _Alloc> _RopeConcatenation;
330 _RopeConcatenation* __c = __STATIC_CAST(_RopeConcatenation*, this);
331 _STLP_STD::_Destroy(__c);
333 _RopeConcatenation).deallocate(__c, 1);
334 break;
335 }
336 case _S_function:
337 {
338 typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction;
339 _RopeFunction* __f = __STATIC_CAST(_RopeFunction*, this);
340 _STLP_STD::_Destroy(__f);
342 _RopeFunction).deallocate(__f, 1);
343 break;
344 }
345 case _S_substringfn:
346 {
347 typedef _Rope_RopeSubstring<_CharT, _Alloc> _RopeSubstring;
348 _RopeSubstring* __rss = __STATIC_CAST(_RopeSubstring*, this);
349 _STLP_STD::_Destroy(__rss);
351 _RopeSubstring).deallocate(__rss, 1);
352 break;
353 }
354 }
355}
356
357# if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
358# define __RopeLeaf__ _Rope_RopeLeaf<_CharT,_Alloc>
359# define __RopeRep__ _Rope_RopeRep<_CharT,_Alloc>
360# define _RopeLeaf _Rope_RopeLeaf<_CharT,_Alloc>
361# define _RopeRep _Rope_RopeRep<_CharT,_Alloc>
362# define size_type size_t
363# else
364# define __RopeLeaf__ _STLP_TYPENAME_ON_RETURN_TYPE rope<_CharT,_Alloc>::_RopeLeaf
365# define __RopeRep__ _STLP_TYPENAME_ON_RETURN_TYPE rope<_CharT,_Alloc>::_RopeRep
366# endif
367
368template <class _CharT, class _Alloc>
371}
372
373// Concatenate a C string onto a leaf rope by copying the rope data.
374// Used for short ropes.
375template <class _CharT, class _Alloc>
378 _RopeLeaf* __r, const _CharT* __iter, size_t __len) {
379 size_t __old_len = __r->_M_size._M_data;
380 _CharT* __new_data = __r->_M_size.allocate(_S_rounded_up_size(__old_len + __len));
381 _RopeLeaf* __result;
382
383 _STLP_PRIV __ucopy_n(__r->_M_data, __old_len, __new_data);
384 _STLP_PRIV __ucopy_n(__iter, __len, __new_data + __old_len);
385 _S_construct_null(__new_data + __old_len + __len);
386 _STLP_TRY {
387 __result = _S_new_RopeLeaf(__new_data, __old_len + __len, __r->get_allocator());
388 }
389 _STLP_UNWIND(_RopeRep::_S_free_string(__new_data, __old_len + __len,
390 __r->get_allocator()))
391 return __result;
392}
393
394template <class _CharT, class _Alloc>
396 size_t __size, const __true_type& /*basic char type*/) {
397 _S_construct_null(__r->_M_data + __size);
398 _STLP_ASSERT(__r->_M_c_string == __r->_M_data)
399}
400
401template <class _CharT, class _Alloc>
403 size_t, const __false_type& /*basic char type*/) {
404 if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string) {
405 __r->_M_free_c_string();
406 __r->_M_c_string = 0;
407 }
408}
409
410// As above, but it's OK to clobber original if refcount is 1
411template <class _CharT, class _Alloc>
413rope<_CharT,_Alloc>::_S_destr_leaf_concat_char_iter (_RopeLeaf* __r, const _CharT* __iter, size_t __len) {
414 //_STLP_ASSERT(__r->_M_ref_count >= 1)
415 if ( /* __r->_M_ref_count > 1 */ __r->_M_incr() > 2 ) { // - ptr
416 __r->_M_decr(); // - ptr
417 return _S_leaf_concat_char_iter(__r, __iter, __len);
418 }
419 __r->_M_decr(); // - ptr, __r->_M_ref_count == 1 or 0
420 size_t __old_len = __r->_M_size._M_data;
421 if (_S_rounded_up_size(__old_len) == _S_rounded_up_size(__old_len + __len)) {
422 // The space has been partially initialized for the standard
423 // character types. But that doesn't matter for those types.
424 _STLP_PRIV __ucopy_n(__iter, __len, __r->_M_data + __old_len);
425 _Terminate_RopeLeaf(__r, __old_len + __len, _IsBasicCharType());
426 __r->_M_size._M_data = __old_len + __len;
427 // _STLP_ASSERT(__r->_M_ref_count == 1)
428 // __r->_M_ref_count = 2;
429 __r->_M_incr(); // i.e. __r->_M_ref_count = 2
430 return __r;
431 } else {
432 _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len);
433 //_STLP_ASSERT(__result->_M_ref_count == 1)
434 return __result;
435 }
436}
437
438// Assumes left and right are not 0.
439// Does not increment (nor decrement on exception) child reference counts.
440// Result has ref count 1.
441template <class _CharT, class _Alloc>
444 _RopeConcatenation* __result =
445 _S_new_RopeConcatenation(__left, __right, __left->get_allocator());
446 size_t __depth = __result->_M_depth;
447
448 _STLP_ASSERT(__left->get_allocator() == __right->get_allocator())
449 if (__depth > 20 && (__result->_M_size._M_data < 1000 ||
450 __depth > _RopeRep::_S_max_rope_depth)) {
451 _RopeRep* __balanced;
452
453 _STLP_TRY {
454 __balanced = _S_balance(__result);
455 // _STLP_ASSERT(__result == __balanced ||
456 // 1 == __result->_M_ref_count &&
457 // 1 == __balanced->_M_ref_count)
458 __result->_M_unref_nonnil();
459 }
461 _RopeConcatenation).deallocate(__result,1)))
462 // In case of exception, we need to deallocate
463 // otherwise dangling result node. But caller
464 // still owns its children. Thus unref is
465 // inappropriate.
466 return __balanced;
467 } else {
468 return __result;
469 }
470}
471
472template <class _CharT, class _Alloc>
475 const _CharT*__s, size_t __slen) {
476 _RopeRep* __result;
477 if (0 == __slen) {
478 _S_ref(__r);
479 return __r;
480 }
481 if (0 == __r)
482 return _S_RopeLeaf_from_unowned_char_ptr(__s, __slen, __r->get_allocator());
483 if (_RopeRep::_S_leaf == __r->_M_tag &&
484 __r->_M_size._M_data + __slen <= _S_copy_max) {
485 __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
486 // _STLP_ASSERT(1 == __result->_M_ref_count)
487 return __result;
488 }
489 if (_RopeRep::_S_concat == __r->_M_tag &&
490 _RopeRep::_S_leaf == ((_RopeConcatenation*)__r)->_M_right->_M_tag) {
491 _RopeLeaf* __right = (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right);
492 if (__right->_M_size._M_data + __slen <= _S_copy_max) {
493 _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left;
494 _RopeRep* __nright = _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen);
495 __left->_M_ref_nonnil();
496 _STLP_TRY {
497 __result = _S_tree_concat(__left, __nright);
498 }
499 _STLP_UNWIND(_S_unref(__left); _S_unref(__nright))
500 // _STLP_ASSERT(1 == __result->_M_ref_count)
501 return __result;
502 }
503 }
504 _RopeRep* __nright =
505 _S_RopeLeaf_from_unowned_char_ptr(__s, __slen, __r->get_allocator());
506 _STLP_TRY {
507 __r->_M_ref_nonnil();
508 __result = _S_tree_concat(__r, __nright);
509 }
510 _STLP_UNWIND(_S_unref(__r); _S_unref(__nright))
511 // _STLP_ASSERT(1 == __result->_M_ref_count)
512 return __result;
513}
514
515template <class _CharT, class _Alloc>
518 _RopeRep* __r, const _CharT* __s, size_t __slen) {
519 _RopeRep* __result;
520 if (0 == __r)
521 return _S_RopeLeaf_from_unowned_char_ptr(__s, __slen,
522 __r->get_allocator());
523 // size_t __count = __r->_M_ref_count;
524 size_t __orig_size = __r->_M_size._M_data;
525 // _STLP_ASSERT(__count >= 1)
526 if ( /* __count > 1 */ __r->_M_incr() > 2 ) {
527 __r->_M_decr();
528 return _S_concat_char_iter(__r, __s, __slen);
529 }
530 if (0 == __slen) {
531 return __r;
532 }
533 __r->_M_decr();
534 if (__orig_size + __slen <= _S_copy_max && _RopeRep::_S_leaf == __r->_M_tag) {
535 return _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
536 }
537 if (_RopeRep::_S_concat == __r->_M_tag) {
539 if (_RopeRep::_S_leaf == __right->_M_tag &&
540 __right->_M_size._M_data + __slen <= _S_copy_max) {
541 _RopeRep* __new_right = _S_destr_leaf_concat_char_iter(__right, __s, __slen);
542 if (__right == __new_right) {
543 // _STLP_ASSERT(__new_right->_M_ref_count == 2)
544 // __new_right->_M_ref_count = 1;
545 __new_right->_M_decr();
546 } else {
547 // _STLP_ASSERT(__new_right->_M_ref_count >= 1)
548 __right->_M_unref_nonnil();
549 }
550 // _STLP_ASSERT(__r->_M_ref_count == 1)
551 // __r->_M_ref_count = 2; // One more than before.
552 __r->_M_incr();
553 __STATIC_CAST(_RopeConcatenation*, __r)->_M_right = __new_right;
554 // E.Musser : moved below
555 // __r->_M_size._M_data = __orig_size + __slen;
556 if (0 != __r->_M_c_string) {
557 __r->_M_free_c_string();
558 __r->_M_c_string = 0;
559 }
560 __r->_M_size._M_data = __orig_size + __slen;
561 return __r;
562 }
563 }
564 _RopeRep* __right =
565 _S_RopeLeaf_from_unowned_char_ptr(__s, __slen, __r->get_allocator());
566 __r->_M_ref_nonnil();
567 _STLP_TRY {
568 __result = _S_tree_concat(__r, __right);
569 }
570 _STLP_UNWIND(_S_unref(__r); _S_unref(__right))
571 // _STLP_ASSERT(1 == __result->_M_ref_count)
572 return __result;
573}
574
575template <class _CharT, class _Alloc>
578 if (0 == __left) {
579 _S_ref(__right);
580 return __right;
581 }
582 if (0 == __right) {
583 __left->_M_ref_nonnil();
584 return __left;
585 }
586 if (_RopeRep::_S_leaf == __right->_M_tag) {
587 if (_RopeRep::_S_leaf == __left->_M_tag) {
588 if (__right->_M_size._M_data + __left->_M_size._M_data <= _S_copy_max) {
589 return _S_leaf_concat_char_iter(__STATIC_CAST(_RopeLeaf*, __left),
590 __STATIC_CAST(_RopeLeaf*, __right)->_M_data,
591 __right->_M_size._M_data);
592 }
593 } else if (_RopeRep::_S_concat == __left->_M_tag &&
594 _RopeRep::_S_leaf == __STATIC_CAST(_RopeConcatenation*, __left)->_M_right->_M_tag) {
595 _RopeLeaf* __leftright =
597 if (__leftright->_M_size._M_data + __right->_M_size._M_data <= _S_copy_max) {
598 _RopeRep* __leftleft = __STATIC_CAST(_RopeConcatenation*, __left)->_M_left;
599 _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright,
600 __STATIC_CAST(_RopeLeaf*, __right)->_M_data,
601 __right->_M_size._M_data);
602 __leftleft->_M_ref_nonnil();
603 _STLP_TRY {
604 return _S_tree_concat(__leftleft, __rest);
605 }
606 _STLP_UNWIND(_S_unref(__leftleft); _S_unref(__rest))
607 }
608 }
609 }
610 __left->_M_ref_nonnil();
611 __right->_M_ref_nonnil();
612 _STLP_TRY {
613 return _S_tree_concat(__left, __right);
614 }
615 _STLP_UNWIND(_S_unref(__left); _S_unref(__right))
617}
618
619template <class _CharT, class _Alloc>
622 size_t __start, size_t __endp1) {
623 if (0 == __base) return 0;
624 size_t __len = __base->_M_size._M_data;
625 size_t __adj_endp1;
626 const size_t __lazy_threshold = 128;
627
628 if (__endp1 >= __len) {
629 if (0 == __start) {
630 __base->_M_ref_nonnil();
631 return __base;
632 } else {
633 __adj_endp1 = __len;
634 }
635 } else {
636 __adj_endp1 = __endp1;
637 }
638 switch(__base->_M_tag) {
639 case _RopeRep::_S_concat:
640 {
642 _RopeRep* __left = __c->_M_left;
643 _RopeRep* __right = __c->_M_right;
644 size_t __left_len = __left->_M_size._M_data;
645 _RopeRep* __result;
646
647 if (__adj_endp1 <= __left_len) {
648 return _S_substring(__left, __start, __endp1);
649 } else if (__start >= __left_len) {
650 return _S_substring(__right, __start - __left_len,
651 __adj_endp1 - __left_len);
652 }
653 _Self_destruct_ptr __left_result(_S_substring(__left, __start, __left_len));
654 _Self_destruct_ptr __right_result(_S_substring(__right, 0, __endp1 - __left_len));
655 _STLP_MPWFIX_TRY //*TY 06/01/2000 - mpw forgets to call dtor on __left_result and __right_result without this try block
656 __result = _S_concat_rep(__left_result, __right_result);
657 // _STLP_ASSERT(1 == __result->_M_ref_count)
658 return __result;
659 _STLP_MPWFIX_CATCH //*TY 06/01/2000 -
660 }
661 case _RopeRep::_S_leaf:
662 {
663 _RopeLeaf* __l = __STATIC_CAST(_RopeLeaf*, __base);
664 _RopeLeaf* __result;
665 size_t __result_len;
666 if (__start >= __adj_endp1) return 0;
667 __result_len = __adj_endp1 - __start;
668 if (__result_len > __lazy_threshold) goto lazy;
669 const _CharT* __section = __l->_M_data + __start;
670 // We should sometimes create substring node instead.
671 __result = _S_RopeLeaf_from_unowned_char_ptr(__section, __result_len,
672 __base->get_allocator());
673 return __result;
674 }
675 case _RopeRep::_S_substringfn:
676 // Avoid introducing multiple layers of substring nodes.
677 {
679 size_t __result_len;
680 if (__start >= __adj_endp1) return 0;
681 __result_len = __adj_endp1 - __start;
682 if (__result_len > __lazy_threshold) {
683 _RopeSubstring* __result = _S_new_RopeSubstring(__old->_M_base,
684 __start + __old->_M_start,
685 __adj_endp1 - __start,
686 __base->get_allocator());
687 return __result;
688 } // *** else fall through: ***
689 }
690 case _RopeRep::_S_function:
691 {
693 if (__start >= __adj_endp1) return 0;
694 size_t __result_len = __adj_endp1 - __start;
695
696 if (__result_len > __lazy_threshold) goto lazy;
697 _CharT* __section = __base->_M_size.allocate(_S_rounded_up_size(__result_len));
698 _STLP_TRY {
699 (*(__f->_M_fn))(__start, __result_len, __section);
700 }
701 _STLP_UNWIND(_RopeRep::_S_free_string(__section,
702 __result_len, __base->get_allocator()))
703 _S_construct_null(__section + __result_len);
704 return _S_new_RopeLeaf(__section, __result_len,
705 __base->get_allocator());
706 }
707 }
708 /*NOTREACHED*/
709 _STLP_ASSERT(false)
710 lazy:
711 {
712 // Create substring node.
713 return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start,
714 __base->get_allocator());
715 }
716}
717
718template<class _CharT>
720private:
721 _CharT* _M_buf_ptr;
722public:
723 _Rope_flatten_char_consumer(_CharT* __buffer) {
724 _M_buf_ptr = __buffer;
725 }
727 bool operator() (const _CharT* __leaf, size_t __n) {
729 _M_buf_ptr += __n;
730 return true;
731 }
732};
733
734template<class _CharT>
736private:
738public:
739 size_t _M_count; // Number of nonmatching characters
741 : _M_pattern(__p), _M_count(0) {}
743 bool operator() (const _CharT* __leaf, size_t __n) {
744 size_t __i;
745 for (__i = 0; __i < __n; ++__i) {
746 if (__leaf[__i] == _M_pattern) {
747 _M_count += __i; return false;
748 }
749 }
750 _M_count += __n; return true;
751 }
752};
753
754#if !defined (_STLP_USE_NO_IOSTREAMS)
755template<class _CharT, class _Traits>
756// Here _CharT is both the stream and rope character type.
758private:
762
763 //explicitely defined as private to avoid warnings:
765public:
767 : _M_o(__writer) {}
769 // Caller is presumed to own the ostream
770 bool operator() (const _CharT* __leaf, size_t __n);
771 // Returns true to continue traversal.
772};
773
774template<class _CharT, class _Traits>
776 (const _CharT* __leaf, size_t __n) {
777 size_t __i;
778 // We assume that formatting is set up correctly for each element.
779 for (__i = 0; __i < __n; ++__i) _M_o.put(__leaf[__i]);
780 return true;
781}
782#endif /* !_STLP_USE_NO_IOSTREAMS */
783
784template <class _CharT, class _Alloc, class _CharConsumer>
785bool _S_apply_to_pieces(_CharConsumer& __c,
787 size_t __begin, size_t __end) {
788 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
789 typedef _Rope_RopeConcatenation<_CharT,_Alloc> _RopeConcatenation;
790 typedef _Rope_RopeLeaf<_CharT,_Alloc> _RopeLeaf;
791 typedef _Rope_RopeFunction<_CharT,_Alloc> _RopeFunction;
792
793 if (0 == __r) return true;
794 switch(__r->_M_tag) {
795 case _RopeRep::_S_concat:
796 {
797 _RopeConcatenation* __conc = __STATIC_CAST(_RopeConcatenation*, __r);
798 _RopeRep* __left = __conc->_M_left;
799 size_t __left_len = __left->_M_size._M_data;
800 if (__begin < __left_len) {
801 size_t __left_end = (min) (__left_len, __end);
802 if (!_S_apply_to_pieces(__c, __left, __begin, __left_end))
803 return false;
804 }
805 if (__end > __left_len) {
806 _RopeRep* __right = __conc->_M_right;
807 size_t __right_start = (max)(__left_len, __begin);
808 if (!_S_apply_to_pieces(__c, __right,
809 __right_start - __left_len,
810 __end - __left_len)) {
811 return false;
812 }
813 }
814 }
815 return true;
816 case _RopeRep::_S_leaf:
817 {
818 _RopeLeaf* __l = __STATIC_CAST(_RopeLeaf*, __r);
819 return __c(__l->_M_data + __begin, __end - __begin);
820 }
821 case _RopeRep::_S_function:
822 case _RopeRep::_S_substringfn:
823 {
824 _RopeFunction* __f = __STATIC_CAST(_RopeFunction*, __r);
825 size_t __len = __end - __begin;
826 bool __result;
827 _CharT* __buffer = __r->get_allocator().allocate(__len);
828 _STLP_TRY {
829 (*(__f->_M_fn))(__begin, __len, __buffer);
830 __result = __c(__buffer, __len);
831 __r->get_allocator().deallocate(__buffer, __len);
832 }
833 _STLP_UNWIND((__r->get_allocator().deallocate(__buffer, __len)))
834 return __result;
835 }
836 default:
837 _STLP_ASSERT(false)
838 /*NOTREACHED*/
839 return false;
840 }
841}
842
843#if !defined (_STLP_USE_NO_IOSTREAMS)
844template<class _CharT, class _Traits>
846 char __f = __o.fill();
847 for (streamsize __i = 0; __i < __n; ++__i) __o.put(__f);
848}
849
850template<class _CharT, class _Traits, class _Alloc>
852 const rope<_CharT, _Alloc>& __r, const __true_type& /*_IsBasicCharType*/) {
853 streamsize __w = __o.width();
854 const bool __left = (__o.flags() & ios::left) != 0;
855 size_t __rope_len = __r.size();
857
858 const bool __need_pad = (((sizeof(streamsize) > sizeof(size_t)) && (__STATIC_CAST(streamsize, __rope_len) < __w)) ||
859 ((sizeof(streamsize) <= sizeof(size_t)) && (__rope_len < __STATIC_CAST(size_t, __w))));
860 streamsize __pad_len = __need_pad ? __w - __rope_len : 0;
861
862 if (!__left && __pad_len > 0) {
863 _Rope_fill(__o, __pad_len);
864 }
865 __r.apply_to_pieces(0, __rope_len, __c);
866 if (__left && __pad_len > 0) {
867 _Rope_fill(__o, __pad_len);
868 }
869 return __o;
870}
871
872template<class _CharT, class _Traits, class _Alloc>
874 const rope<_CharT, _Alloc>& __r, const __false_type& /*_IsBasicCharType*/) {
875 streamsize __w = __o.width();
876 size_t __rope_len = __r.size();
878
879 __o.width(__w /__rope_len);
880 _STLP_TRY {
881 __r.apply_to_pieces(0, __rope_len, __c);
882 __o.width(__w);
883 }
884 _STLP_UNWIND(__o.width(__w))
885 return __o;
886}
887
888template<class _CharT, class _Traits, class _Alloc>
890 const rope<_CharT, _Alloc>& __r) {
891 typedef typename _IsIntegral<_CharT>::_Ret _Char_Is_Integral;
892 return _S_io_get(__o, __r, _Char_Is_Integral());
893}
894#endif /* NO_IOSTREAMS */
895
896template <class _CharT, class _Alloc>
898 size_t __start, size_t __len,
899 _CharT* __buffer) {
901 _S_apply_to_pieces(__c, __r, __start, __start + __len);
902 return(__buffer + __len);
903}
904
905template <class _CharT, class _Alloc>
906size_t rope<_CharT,_Alloc>::find(_CharT __pattern, size_t __start) const {
908 _S_apply_to_pieces(__c, _M_tree_ptr._M_data, __start, size());
909 size_type __result_pos = __start + __c._M_count;
910#ifndef _STLP_OLD_ROPE_SEMANTICS
911 if (__result_pos == size()) __result_pos = npos;
912#endif
913 return __result_pos;
914}
915
916template <class _CharT, class _Alloc>
917_CharT*
919 if (0 == __r) return __buffer;
920 switch(__r->_M_tag) {
921 case _RopeRep::_S_concat:
922 {
924 _RopeRep* __left = __c->_M_left;
925 _RopeRep* __right = __c->_M_right;
926 _CharT* __rest = _S_flatten(__left, __buffer);
927 return _S_flatten(__right, __rest);
928 }
929 case _RopeRep::_S_leaf:
930 {
931 _RopeLeaf* __l = __STATIC_CAST(_RopeLeaf*, __r);
932 return _STLP_PRIV __ucopy_n(__l->_M_data, __l->_M_size._M_data, __buffer).second;
933 }
934 case _RopeRep::_S_function:
935 case _RopeRep::_S_substringfn:
936 // We dont yet do anything with substring nodes.
937 // This needs to be fixed before ropefiles will work well.
938 {
940 (*(__f->_M_fn))(0, __f->_M_size._M_data, __buffer);
941 return __buffer + __f->_M_size._M_data;
942 }
943 default:
944 _STLP_ASSERT(false)
945 /*NOTREACHED*/
946 return 0;
947 }
948}
949
950#ifdef _STLP_DEBUG
951// This needs work for _CharT != char
952template <class _CharT, class _Alloc>
953void rope<_CharT,_Alloc>::_S_dump(_RopeRep* __r, int __indent) {
954 for (int __i = 0; __i < __indent; ++__i) putchar(' ');
955 if (0 == __r) {
956 printf("NULL\n"); return;
957 }
958 if (_RopeRep::_S_concat == __r->_M_tag) {
959 _RopeConcatenation* __c = __STATIC_CAST(_RopeConcatenation*, __r);
960 _RopeRep* __left = __c->_M_left;
961 _RopeRep* __right = __c->_M_right;
962 printf("Concatenation %p (rc = %ld, depth = %d, len = %ld, %s balanced)\n",
963 __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size._M_data,
964 __r->_M_is_balanced? "" : "not");
965 _S_dump(__left, __indent + 2);
966 _S_dump(__right, __indent + 2);
967 return;
968 }
969 else {
970 const char* __kind;
971
972 switch (__r->_M_tag) {
973 case _RopeRep::_S_leaf:
974 __kind = "Leaf";
975 break;
976 case _RopeRep::_S_function:
977 __kind = "Function";
978 break;
979 case _RopeRep::_S_substringfn:
980 __kind = "Function representing substring";
981 break;
982 default:
983 __kind = "(corrupted kind field!)";
984 }
985 printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
986 __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size._M_data);
987 if (sizeof(_CharT) == 1) {
988 const int __max_len = 40;
989 _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len));
990 _CharT __buffer[__max_len + 1];
991 bool __too_big = __r->_M_size._M_data > __prefix->_M_size._M_data;
992
993 _S_flatten(__prefix, __buffer);
994 __buffer[__prefix->_M_size._M_data] = _STLP_DEFAULT_CONSTRUCTED(_CharT);
995 printf("%s%s\n", (char*)__buffer, __too_big? "...\n" : "\n");
996 } else {
997 printf("\n");
998 }
999 }
1000}
1001#endif /* _STLP_DEBUG */
1002
1003# define __ROPE_TABLE_BODY = { \
1004/* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21, \
1005/* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377, \
1006/* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181, \
1007/* 18 */6765ul, /* 19 */10946ul, /* 20 */17711ul, /* 21 */28657ul, /* 22 */46368ul, \
1008/* 23 */75025ul, /* 24 */121393ul, /* 25 */196418ul, /* 26 */317811ul, \
1009/* 27 */514229ul, /* 28 */832040ul, /* 29 */1346269ul, /* 30 */2178309ul, \
1010/* 31 */3524578ul, /* 32 */5702887ul, /* 33 */9227465ul, /* 34 */14930352ul, \
1011/* 35 */24157817ul, /* 36 */39088169ul, /* 37 */63245986ul, /* 38 */102334155ul, \
1012/* 39 */165580141ul, /* 40 */267914296ul, /* 41 */433494437ul, \
1013/* 42 */701408733ul, /* 43 */1134903170ul, /* 44 */1836311903ul, \
1014/* 45 */2971215073ul }
1015
1016template <class _CharT, class _Alloc>
1017const unsigned long
1019# undef __ROPE_DEPTH_SIZE
1020# undef __ROPE_MAX_DEPTH
1021# undef __ROPE_TABLE_BODY
1022
1023// These are Fibonacci numbers < 2**32.
1024
1025template <class _CharT, class _Alloc>
1027 _RopeRep* __forest[_RopeRep::_S_max_rope_depth + 1] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1028 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1029 0,0,0,0,0,0};
1030 _RopeRep* __result = 0;
1031 int __i;
1032 // Invariant:
1033 // The concatenation of forest in descending order is equal to __r.
1034 // __forest[__i]._M_size._M_data >= _S_min_len[__i]
1035 // __forest[__i]._M_depth = __i
1036 // References from forest are included in refcount.
1037
1038 _STLP_TRY {
1039 _S_add_to_forest(__r, __forest);
1040 for (__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i)
1041 if (0 != __forest[__i]) {
1042 _Self_destruct_ptr __old(__result);
1043 __result = _S_concat_rep(__forest[__i], __result);
1044 __forest[__i]->_M_unref_nonnil();
1045# ifdef _STLP_USE_EXCEPTIONS
1046 __forest[__i] = 0;
1047# endif
1048 }
1049 }
1050 _STLP_UNWIND(for(__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i)
1051 _S_unref(__forest[__i]))
1052 if (__result->_M_depth > _RopeRep::_S_max_rope_depth) {
1053 __stl_throw_range_error("rope too long");
1054 }
1055 return(__result);
1056}
1057
1058
1059template <class _CharT, class _Alloc>
1060void
1062{
1063 if (__r -> _M_is_balanced) {
1064 _S_add_leaf_to_forest(__r, __forest);
1065 return;
1066 }
1067 _STLP_ASSERT(__r->_M_tag == _RopeRep::_S_concat)
1068 {
1070
1071 _S_add_to_forest(__c->_M_left, __forest);
1072 _S_add_to_forest(__c->_M_right, __forest);
1073 }
1074}
1075
1076
1077template <class _CharT, class _Alloc>
1078void
1080{
1081 _RopeRep* __insertee; // included in refcount
1082 _RopeRep* __too_tiny = 0; // included in refcount
1083 int __i; // forest[0..__i-1] is empty
1084 size_t __s = __r->_M_size._M_data;
1085
1086 for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i) {
1087 if (0 != __forest[__i]) {
1088 _Self_destruct_ptr __old(__too_tiny);
1089 __too_tiny = _S_concat_and_set_balanced(__forest[__i], __too_tiny);
1090 __forest[__i]->_M_unref_nonnil();
1091 __forest[__i] = 0;
1092 }
1093 }
1094 {
1095 _Self_destruct_ptr __old(__too_tiny);
1096 __insertee = _S_concat_and_set_balanced(__too_tiny, __r);
1097 }
1098 // Too_tiny dead, and no longer included in refcount.
1099 // Insertee is live and included.
1100 _STLP_ASSERT(_S_is_almost_balanced(__insertee))
1101 _STLP_ASSERT(__insertee->_M_depth <= __r->_M_depth + 1)
1102 for (;; ++__i) {
1103 if (0 != __forest[__i]) {
1104 _Self_destruct_ptr __old(__insertee);
1105 __insertee = _S_concat_and_set_balanced(__forest[__i], __insertee);
1106 __forest[__i]->_M_unref_nonnil();
1107 __forest[__i] = 0;
1108 _STLP_ASSERT(_S_is_almost_balanced(__insertee))
1109 }
1110 _STLP_ASSERT(_S_min_len[__i] <= __insertee->_M_size._M_data)
1111 _STLP_ASSERT(__forest[__i] == 0)
1112 if (__i == _RopeRep::_S_max_rope_depth ||
1113 __insertee->_M_size._M_data < _S_min_len[__i+1]) {
1114 __forest[__i] = __insertee;
1115 // refcount is OK since __insertee is now dead.
1116 return;
1117 }
1118 }
1119}
1120
1121template <class _CharT, class _Alloc>
1122_CharT
1124{
1125 _CharT* __cstr = __r->_M_c_string;
1126
1127 _STLP_ASSERT(__i < __r->_M_size._M_data)
1128 if (0 != __cstr) return __cstr[__i];
1129 for(;;) {
1130 switch(__r->_M_tag) {
1131 case _RopeRep::_S_concat:
1132 {
1134 _RopeRep* __left = __c->_M_left;
1135 size_t __left_len = __left->_M_size._M_data;
1136
1137 if (__i >= __left_len) {
1138 __i -= __left_len;
1139 __r = __c->_M_right;
1140 } else {
1141 __r = __left;
1142 }
1143 }
1144 break;
1145 case _RopeRep::_S_leaf:
1146 {
1147 _RopeLeaf* __l = (_RopeLeaf*)__r;
1148 return __l->_M_data[__i];
1149 }
1150 case _RopeRep::_S_function:
1151 case _RopeRep::_S_substringfn:
1152 {
1153 _RopeFunction* __f = (_RopeFunction*)__r;
1154 _CharT __result;
1155
1156 (*(__f->_M_fn))(__i, 1, &__result);
1157 return __result;
1158 }
1159 }
1160 }
1161#if defined(_STLP_NEED_UNREACHABLE_RETURN)
1162 return 0;
1163#endif
1164}
1165
1166// Return a uniquely referenced character slot for the given
1167// position, or 0 if that's not possible.
1168template <class _CharT, class _Alloc>
1169_CharT*
1171{
1172 _RopeRep* __clrstack[_RopeRep::_S_max_rope_depth];
1173 size_t __csptr = 0;
1174
1175 for(;;) {
1176 // if (__r->_M_ref_count > 1) return 0;
1177 if ( __r->_M_incr() > 2 ) {
1178 __r->_M_decr();
1179 return 0;
1180 }
1181 switch(__r->_M_tag) {
1182 case _RopeRep::_S_concat:
1183 {
1185 _RopeRep* __left = __c->_M_left;
1186 size_t __left_len = __left->_M_size._M_data;
1187
1188 if (__c->_M_c_string != 0) __clrstack[__csptr++] = __c;
1189 if (__i >= __left_len) {
1190 __i -= __left_len;
1191 __r = __c->_M_right;
1192 } else {
1193 __r = __left;
1194 }
1195 }
1196 break;
1197 case _RopeRep::_S_leaf:
1198 {
1199 _RopeLeaf* __l = (_RopeLeaf*)__r;
1200 if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0)
1201 __clrstack[__csptr++] = __l;
1202 while (__csptr > 0) {
1203 -- __csptr;
1204 _RopeRep* __d = __clrstack[__csptr];
1205 __d->_M_free_c_string();
1206 __d->_M_c_string = 0;
1207 }
1208 return __l->_M_data + __i;
1209 }
1210 case _RopeRep::_S_function:
1211 case _RopeRep::_S_substringfn:
1212 return 0;
1213 }
1214 }
1215#if defined(_STLP_NEED_UNREACHABLE_RETURN)
1216 return 0;
1217#endif
1218
1219}
1220
1221// The following could be implemented trivially using
1222// lexicographical_compare_3way.
1223// We do a little more work to avoid dealing with rope iterators for
1224// flat strings.
1225template <class _CharT, class _Alloc>
1226int
1228 const _RopeRep* __right) {
1229 size_t __left_len;
1230 size_t __right_len;
1231
1232 if (0 == __right) return 0 != __left;
1233 if (0 == __left) return -1;
1234 __left_len = __left->_M_size._M_data;
1235 __right_len = __right->_M_size._M_data;
1236 if (_RopeRep::_S_leaf == __left->_M_tag) {
1237 const _RopeLeaf* __l = __STATIC_CAST(const _RopeLeaf*, __left);
1238 if (_RopeRep::_S_leaf == __right->_M_tag) {
1239 const _RopeLeaf* __r = __STATIC_CAST(const _RopeLeaf*, __right);
1240 return _STLP_PRIV __lexicographical_compare_3way(__l->_M_data, __l->_M_data + __left_len,
1241 __r->_M_data, __r->_M_data + __right_len);
1242 }
1243 else {
1244 const_iterator __rstart(__right, 0);
1245 const_iterator __rend(__right, __right_len);
1246 return _STLP_PRIV __lexicographical_compare_3way(__l->_M_data, __l->_M_data + __left_len,
1247 __rstart, __rend);
1248 }
1249 }
1250 else {
1251 const_iterator __lstart(__left, 0);
1252 const_iterator __lend(__left, __left_len);
1253 if (_RopeRep::_S_leaf == __right->_M_tag) {
1254 const _RopeLeaf* __r = __STATIC_CAST(const _RopeLeaf*, __right);
1255 return _STLP_PRIV __lexicographical_compare_3way(__lstart, __lend,
1256 __r->_M_data, __r->_M_data + __right_len);
1257 }
1258 else {
1259 const_iterator __rstart(__right, 0);
1260 const_iterator __rend(__right, __right_len);
1261 return _STLP_PRIV __lexicographical_compare_3way(__lstart, __lend, __rstart, __rend);
1262 }
1263 }
1264}
1265
1266// Assignment to reference proxies.
1267template <class _CharT, class _Alloc>
1270 _RopeRep* __old = _M_root->_M_tree_ptr._M_data;
1271 // First check for the case in which everything is uniquely
1272 // referenced. In that case we can do this destructively.
1273 _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos);
1274 if (0 != __ptr) {
1275 *__ptr = __c;
1276 return *this;
1277 }
1278 _Self_destruct_ptr __left(
1279 _My_rope::_S_substring(__old, 0, _M_pos));
1280 _Self_destruct_ptr __right(
1281 _My_rope::_S_substring(__old, _M_pos+1, __old->_M_size._M_data));
1282 _Self_destruct_ptr __result_left(
1283 _My_rope::_S_destr_concat_char_iter(__left, &__c, 1));
1284
1285 // _STLP_ASSERT(__left == __result_left || 1 == __result_left->_M_ref_count)
1286 _RopeRep* __result =
1287 _My_rope::_S_concat_rep(__result_left, __right);
1288 // _STLP_ASSERT(1 <= __result->_M_ref_count)
1289 _RopeRep::_S_unref(__old);
1290 _M_root->_M_tree_ptr._M_data = __result;
1291 return *this;
1292}
1293
1294template <class _CharT, class _Alloc>
1298}
1299
1300template<class _CharT, class _Alloc>
1301_CharT rope<_CharT,_Alloc>::_S_empty_c_str[1] = { _CharT() };
1302// # endif
1303
1304#if !defined (_STLP_STATIC_CONST_INIT_BUG) && !defined (_STLP_NO_STATIC_CONST_DEFINITION)
1305template <class _CharT, class _Alloc>
1306const size_t rope<_CharT, _Alloc>::npos;
1307#endif
1308
1309template<class _CharT, class _Alloc>
1310const _CharT* rope<_CharT,_Alloc>::c_str() const {
1311 if (0 == _M_tree_ptr._M_data) {
1312 // Possibly redundant, but probably fast.
1313 _S_empty_c_str[0] = _STLP_DEFAULT_CONSTRUCTED(_CharT);
1314 return _S_empty_c_str;
1315 }
1316 _CharT* __old_c_string = _M_tree_ptr._M_data->_M_c_string;
1317 if (0 != __old_c_string) return __old_c_string;
1318 size_t __s = size();
1319 _CharT* __result = _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_tree_ptr, _CharT).allocate(__s + 1);
1320 _S_flatten(_M_tree_ptr._M_data, __result);
1321 _S_construct_null(__result + __s);
1322 __old_c_string = __STATIC_CAST(_CharT*, _Atomic_swap_ptr(__REINTERPRET_CAST(void* _STLP_VOLATILE*, &(_M_tree_ptr._M_data->_M_c_string)),
1323 __result));
1324 if (0 != __old_c_string) {
1325 // It must have been added in the interim. Hence it had to have been
1326 // separately allocated. Deallocate the old copy, since we just
1327 // replaced it.
1328 _STLP_STD::_Destroy_Range(__old_c_string, __old_c_string + __s + 1);
1329 _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_tree_ptr, _CharT).deallocate(__old_c_string, __s + 1);
1330 }
1331 return __result;
1332}
1333
1334template<class _CharT, class _Alloc>
1336 if (0 == _M_tree_ptr._M_data) {
1337 _S_empty_c_str[0] = _STLP_DEFAULT_CONSTRUCTED(_CharT);
1338 return _S_empty_c_str;
1339 }
1340 _CharT* __old_c_string = _M_tree_ptr._M_data->_M_c_string;
1341 if (_RopeRep::_S_leaf == _M_tree_ptr._M_data->_M_tag && 0 != __old_c_string) {
1342 return __old_c_string;
1343 }
1344 size_t __s = size();
1345 _CharT* __result = _M_tree_ptr.allocate(_S_rounded_up_size(__s));
1346 _S_flatten(_M_tree_ptr._M_data, __result);
1347 _S_construct_null(__result + __s);
1348 _M_tree_ptr._M_data->_M_unref_nonnil();
1349 _M_tree_ptr._M_data = _S_new_RopeLeaf(__result, __s, _M_tree_ptr);
1350 return __result;
1351}
1352
1353// Algorithm specializations. More should be added.
1354
1355#if (!defined (_STLP_MSVC) || (_STLP_MSVC >= 1310)) && !defined (__DMC__)
1356// I couldn't get this to work with VC++
1357template<class _CharT,class _Alloc>
1361 _STLP_ASSERT(__first.container() == __middle.container() &&
1362 __middle.container() == __last.container())
1363 rope<_CharT,_Alloc>& __r(__first.container());
1364 rope<_CharT,_Alloc> __prefix = __r.substr(0, __first.index());
1365 rope<_CharT,_Alloc> __suffix =
1366 __r.substr(__last.index(), __r.size() - __last.index());
1367 rope<_CharT,_Alloc> __part1 =
1368 __r.substr(__middle.index(), __last.index() - __middle.index());
1369 rope<_CharT,_Alloc> __part2 =
1370 __r.substr(__first.index(), __middle.index() - __first.index());
1371 __r = __prefix;
1372 __r += __part1;
1373 __r += __part2;
1374 __r += __suffix;
1375}
1376
1377
1378# if 0
1379// Probably not useful for several reasons:
1380// - for SGIs 7.1 compiler and probably some others,
1381// this forces lots of rope<wchar_t, ...> instantiations, creating a
1382// code bloat and compile time problem. (Fixed in 7.2.)
1383// - wchar_t is 4 bytes wide on most UNIX platforms, making it unattractive
1384// for unicode strings. Unsigned short may be a better character
1385// type.
1386inline void rotate(
1387 _Rope_iterator<wchar_t, allocator<char> > __first,
1388 _Rope_iterator<wchar_t, allocator<char> > __middle,
1390 _Rope_rotate(__first, __middle, __last);
1391}
1392# endif
1393#endif /* _STLP_MSVC */
1394
1395# undef __RopeLeaf__
1396# undef __RopeRep__
1397# undef __RopeLeaf
1398# undef __RopeRep
1399# undef size_type
1400
1402
1403# endif /* ROPEIMPL_H */
1404
1405// Local Variables:
1406// mode:C++
1407// End:
_STLP_MOVE_TO_STD_NAMESPACE void rotate(_ForwardIter __first, _ForwardIter __middle, _ForwardIter __last)
Definition: _algo.c:519
_STLP_INLINE_LOOP _InputIter __last
Definition: _algo.h:68
return __n
Definition: _algo.h:75
_STLP_MOVE_TO_PRIV_NAMESPACE int __lexicographical_compare_3way(_InputIter1 __first1, _InputIter1 __last1, _InputIter2 __first2, _InputIter2 __last2)
Definition: _algobase.c:78
#define _STLP_MPWFIX_CATCH
Definition: _apple.h:111
#define _STLP_MPWFIX_TRY
Definition: _apple.h:110
#define _Alloc
Definition: _bvector.h:330
#define _STLP_DEFAULT_CONSTRUCTED(_TTp)
Definition: _construct.h:265
#define _STLP_ASSERT(expr)
Definition: _debug.h:165
#define _STLP_PRIV
Definition: _dm.h:70
_STLP_THROW_FUNCT_SPEC _STLP_CALL __stl_throw_out_of_range(const char *__msg)
Definition: _range_errors.c:69
_STLP_THROW_FUNCT_SPEC _STLP_CALL __stl_throw_range_error(const char *__msg)
Definition: _range_errors.c:66
#define __RopeLeaf__
Definition: _rope.c:364
#define __RopeRep__
Definition: _rope.c:365
bool _S_apply_to_pieces(_CharConsumer &__c, _Rope_RopeRep< _CharT, _Alloc > *__r, size_t __begin, size_t __end)
Definition: _rope.c:785
void _Terminate_RopeLeaf(_Rope_RopeLeaf< _CharT, _Alloc > *__r, size_t __size, const __true_type &)
Definition: _rope.c:395
basic_ostream< _CharT, _Traits > & _S_io_get(basic_ostream< _CharT, _Traits > &__o, const rope< _CharT, _Alloc > &__r, const __true_type &)
Definition: _rope.c:851
#define __ROPE_TABLE_BODY
Definition: _rope.c:1003
basic_ostream< _CharT, _Traits > & operator<<(basic_ostream< _CharT, _Traits > &__o, const rope< _CharT, _Alloc > &__r)
Definition: _rope.c:889
void _Rope_fill(basic_ostream< _CharT, _Traits > &__o, streamsize __n)
Definition: _rope.c:845
void _Rope_rotate(_Rope_iterator< _CharT, _Alloc > __first, _Rope_iterator< _CharT, _Alloc > __middle, _Rope_iterator< _CharT, _Alloc > __last)
Definition: _rope.c:1358
void _S_construct_null(_CharT *__p)
Definition: _rope.h:148
#define _STLP_CREATE_ALLOCATOR(__atype, __a, _Tp)
Definition: _rope.h:81
#define __ROPE_DEPTH_SIZE
Definition: _rope.h:343
static const size_t npos
Definition: _string_npos.h:26
void *_STLP_CALL _Atomic_swap_ptr(void *_STLP_VOLATILE *__p, void *__q)
Definition: _threads.h:628
_STLP_MOVE_TO_PRIV_NAMESPACE _STLP_INLINE_LOOP pair< _InputIter, _ForwardIter > __ucopy_n(_InputIter __first, _Size __count, _ForwardIter __result, const input_iterator_tag &)
ptrdiff_t streamsize
Definition: char_traits.h:81
__stl_atomic_t _M_incr()
Definition: _threads.h:479
__stl_atomic_t _M_decr()
Definition: _threads.h:480
_Self & operator=(_CharT __c)
Definition: _rope.c:1269
_Rope_char_ptr_proxy< _CharT, _Alloc > operator&() const
Definition: _rope.c:1296
_Rope_find_char_char_consumer(_CharT __p)
Definition: _rope.c:740
bool operator()(const _CharT *__leaf, size_t __n)
Definition: _rope.c:743
_Rope_flatten_char_consumer(_CharT *__buffer)
Definition: _rope.c:723
bool operator()(const _CharT *__leaf, size_t __n)
Definition: _rope.c:727
_Insert_ostream & _M_o
Definition: _rope.c:761
basic_ostream< _CharT, _Traits > _Insert_ostream
Definition: _rope.c:759
bool operator()(const _CharT *__leaf, size_t __n)
Definition: _rope.c:776
_Rope_insert_char_consumer(_Insert_ostream &__writer)
Definition: _rope.c:766
_Self & operator=(_Self const &)
_Rope_insert_char_consumer< _CharT, _Traits > _Self
Definition: _rope.c:760
size_t _M_leaf_pos
Definition: _rope.h:768
_CharT * _M_buf_end
Definition: _rope.h:774
void _M_incr(size_t __n)
Definition: _rope.c:270
void _M_decr(size_t __n)
Definition: _rope.c:286
size_t _M_current_pos
Definition: _rope.h:764
static void _S_setcache(_Rope_iterator_base< _CharT, _Alloc > &__x)
Definition: _rope.c:136
static void _S_setbuf(_Rope_iterator_base< _CharT, _Alloc > &__x)
Definition: _rope.c:90
_CharT * _M_buf_start
Definition: _rope.h:770
unsigned char _M_path_directions
Definition: _rope.h:795
struct _Rope_iterator_base::@1842 _M_path_end
size_t index() const
Definition: _rope.h:823
_RopeRep * _M_root
Definition: _rope.h:766
static void _S_setcache_for_incr(_Rope_iterator_base< _CharT, _Alloc > &__x)
Definition: _rope.c:208
struct _Rope_iterator_base::@1843 _M_tmp_buf
_CharT * _M_buf_ptr
Definition: _rope.h:772
_Rope_iterator()
Definition: _rope.h:995
rope< _CharT, _Alloc > & container()
Definition: _rope.h:994
void _M_check()
Definition: _rope.c:299
_Value _M_data
Definition: _alloc.h:478
_Tp * allocate(size_type __n, size_type &__allocated_n)
Definition: _alloc.h:525
char_type fill() const
Definition: _ios.h:81
_Self & put(char_type __c)
Definition: _ostream.c:408
fmtflags flags() const
Definition: _ios_base.h:107
streamsize width() const
Definition: _ios_base.h:134
Definition: _rope.h:1087
void apply_to_pieces(size_t __begin, size_t __end, _CharConsumer &__c) const
Definition: _rope.h:1184
static _RopeLeaf * _S_destr_leaf_concat_char_iter(_RopeLeaf *__r, const _CharT *__iter, size_t __slen)
Definition: _rope.c:413
void _STLP_FUNCTION_THROWS _M_throw_out_of_range() const
Definition: _rope.c:369
size_type find(const _Self &__s, size_type __pos=0) const
Definition: _rope.h:1968
static _RopeRep * _S_substring(_RopeRep *__base, size_t __start, size_t __endp1)
Definition: _rope.c:621
static int _S_compare(const _RopeRep *__x, const _RopeRep *__y)
Definition: _rope.c:1227
const _CharT * c_str() const
Definition: _rope.c:1310
static _CharT * _S_fetch_ptr(_RopeRep *__r, size_type __pos)
Definition: _rope.c:1170
bool empty() const
Definition: _rope.h:1354
static _RopeRep * _S_tree_concat(_RopeRep *__left, _RopeRep *__right)
Definition: _rope.c:443
_Self substr(size_t __start, size_t __len=1) const
Definition: _rope.h:1941
static _RopeRep * _S_concat_rep(_RopeRep *__left, _RopeRep *__right)
Definition: _rope.c:577
static _CharT _S_fetch(_RopeRep *__r, size_type __pos)
Definition: _rope.c:1123
const _CharT * replace_with_c_str()
Definition: _rope.c:1335
static _RopeRep * _S_destr_concat_char_iter(_RopeRep *__r, const _CharT *__iter, size_t __slen)
Definition: _rope.c:517
static _RopeRep * _S_concat_char_iter(_RopeRep *__r, const _CharT *__iter, size_t __slen)
Definition: _rope.c:474
static _RopeRep * _S_balance(_RopeRep *__r)
Definition: _rope.c:1026
static _CharT * _S_flatten(_RopeRep *__r, _CharT *__buffer)
Definition: _rope.c:918
_Alloc allocator_type
Definition: _rope.h:1124
static void _S_add_leaf_to_forest(_RopeRep *__r, _RopeRep **__forest)
Definition: _rope.c:1079
_RopeRep::_IsBasicCharType _IsBasicCharType
Definition: _rope.h:1120
size_t size_type
Definition: _rope.h:1092
size_type size() const
Definition: _rope.h:1623
static _RopeLeaf * _S_leaf_concat_char_iter(_RopeLeaf *__r, const _CharT *__iter, size_t __slen)
Definition: _rope.c:377
static void _S_add_to_forest(_RopeRep *__r, _RopeRep **__forest)
Definition: _rope.c:1061
int putchar(int c)
Definition: crtsupp.c:12
#define _STLP_UNWIND(action)
Definition: features.h:824
#define _STLP_RET_AFTER_THROW(data)
Definition: features.h:829
#define __REINTERPRET_CAST(__x, __y)
Definition: features.h:586
#define _STLP_VOLATILE
Definition: features.h:277
#define __STATIC_CAST(__x, __y)
Definition: features.h:585
#define _STLP_TRY
Definition: features.h:817
#define _STLP_BEGIN_NAMESPACE
Definition: features.h:501
#define _STLP_END_NAMESPACE
Definition: features.h:503
#define printf
Definition: freeldr.h:93
GLsizeiptr size
Definition: glext.h:5919
#define min(a, b)
Definition: monoChain.cc:55
#define __c
Definition: schilyio.h:209
char_producer< _CharT > * _M_fn
Definition: _rope.h:525
_CharT * _M_data
Definition: _rope.h:453
_CharT *_STLP_VOLATILE _M_c_string
Definition: _rope.h:361
_Tag _M_tag
Definition: _rope.h:352
static void _S_ref(_Self *__t)
Definition: _rope.h:442
allocator_type get_allocator() const
Definition: _rope.h:358
_Alloc allocator_type
Definition: _rope.h:356
unsigned char _M_depth
Definition: _rope.h:360
void _M_free_c_string()
Definition: _rope.c:76
_STLP_PRIV _STLP_alloc_proxy< size_t, _CharT, allocator_type > _M_size
Definition: _rope.h:362
void _M_ref_nonnil()
Definition: _rope.h:434
void _M_unref_nonnil()
Definition: _rope.h:431
void _M_free_tree()
Definition: _rope.c:316
size_t _M_start
Definition: _rope.h:569
_RopeRep * _M_base
Definition: _rope.h:568
#define max(a, b)
Definition: svc.c:63