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