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