libstdc++
ropeimpl.h
Go to the documentation of this file.
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 
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  _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>:: ~_Rope_RopeConcatenation();
391  _C_deallocate(__c, 1);
392  break;
393  }
394  case __detail::_S_function:
395  {
396  _Rope_RopeFunction<_CharT, _Alloc>* __f
397  = (_Rope_RopeFunction<_CharT, _Alloc>*)this;
398  __f->_Rope_RopeFunction<_CharT, _Alloc>::~_Rope_RopeFunction();
399  _F_deallocate(__f, 1);
400  break;
401  }
402  case __detail::_S_substringfn:
403  {
404  _Rope_RopeSubstring<_CharT, _Alloc>* __ss =
405  (_Rope_RopeSubstring<_CharT, _Alloc>*)this;
406  __ss->_Rope_RopeSubstring<_CharT, _Alloc>:: ~_Rope_RopeSubstring();
407  _S_deallocate(__ss, 1);
408  break;
409  }
410  }
411  }
412 #else
413 
414  template <class _CharT, class _Alloc>
415  inline void
416  _Rope_RopeRep<_CharT, _Alloc>::
417  _S_free_string(const _CharT*, size_t, allocator_type)
418  { }
419 
420 #endif
421 
422  // Concatenate a C string onto a leaf rope by copying the rope data.
423  // Used for short ropes.
424  template <class _CharT, class _Alloc>
425  typename rope<_CharT, _Alloc>::_RopeLeaf*
426  rope<_CharT, _Alloc>::
427  _S_leaf_concat_char_iter(_RopeLeaf* __r, const _CharT* __iter, size_t __len)
428  {
429  size_t __old_len = __r->_M_size;
430  _CharT* __new_data = (_CharT*)
431  _Data_allocate(_S_rounded_up_size(__old_len + __len));
432  _RopeLeaf* __result;
433 
434  uninitialized_copy_n(__r->_M_data, __old_len, __new_data);
435  uninitialized_copy_n(__iter, __len, __new_data + __old_len);
436  _S_cond_store_eos(__new_data[__old_len + __len]);
437  __try
438  {
439  __result = _S_new_RopeLeaf(__new_data, __old_len + __len,
440  __r->_M_get_allocator());
441  }
442  __catch(...)
443  {
444  _RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len,
445  __r->_M_get_allocator());
446  __throw_exception_again;
447  }
448  return __result;
449  }
450 
451 #ifndef __GC
452  // As above, but it's OK to clobber original if refcount is 1
453  template <class _CharT, class _Alloc>
454  typename rope<_CharT,_Alloc>::_RopeLeaf*
455  rope<_CharT, _Alloc>::
456  _S_destr_leaf_concat_char_iter(_RopeLeaf* __r, const _CharT* __iter,
457  size_t __len)
458  {
459  if (__r->_M_ref_count > 1)
460  return _S_leaf_concat_char_iter(__r, __iter, __len);
461  size_t __old_len = __r->_M_size;
462  if (_S_allocated_capacity(__old_len) >= __old_len + __len)
463  {
464  // The space has been partially initialized for the standard
465  // character types. But that doesn't matter for those types.
466  uninitialized_copy_n(__iter, __len, __r->_M_data + __old_len);
467  if (_S_is_basic_char_type((_CharT*)0))
468  _S_cond_store_eos(__r->_M_data[__old_len + __len]);
469  else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string)
470  {
471  __r->_M_free_c_string();
472  __r->_M_c_string = 0;
473  }
474  __r->_M_size = __old_len + __len;
475  __r->_M_ref_count = 2;
476  return __r;
477  }
478  else
479  {
480  _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len);
481  return __result;
482  }
483  }
484 #endif
485 
486  // Assumes left and right are not 0.
487  // Does not increment (nor decrement on exception) child reference counts.
488  // Result has ref count 1.
489  template <class _CharT, class _Alloc>
490  typename rope<_CharT, _Alloc>::_RopeRep*
491  rope<_CharT, _Alloc>::
492  _S_tree_concat(_RopeRep* __left, _RopeRep* __right)
493  {
494  _RopeConcatenation* __result = _S_new_RopeConcatenation(__left, __right,
495  __left->
496  _M_get_allocator());
497  size_t __depth = __result->_M_depth;
498 
499  if (__depth > 20
500  && (__result->_M_size < 1000
501  || __depth > size_t(__detail::_S_max_rope_depth)))
502  {
503  _RopeRep* __balanced;
504 
505  __try
506  {
507  __balanced = _S_balance(__result);
508  __result->_M_unref_nonnil();
509  }
510  __catch(...)
511  {
512  _C_deallocate(__result,1);
513  __throw_exception_again;
514  }
515  // In case of exception, we need to deallocate
516  // otherwise dangling result node. But caller
517  // still owns its children. Thus unref is
518  // inappropriate.
519  return __balanced;
520  }
521  else
522  return __result;
523  }
524 
525  template <class _CharT, class _Alloc>
526  typename rope<_CharT, _Alloc>::_RopeRep*
527  rope<_CharT, _Alloc>::
528  _S_concat_char_iter(_RopeRep* __r, const _CharT*__s, size_t __slen)
529  {
530  _RopeRep* __result;
531  if (0 == __slen)
532  {
533  _S_ref(__r);
534  return __r;
535  }
536  if (0 == __r)
537  return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
538  __r->_M_get_allocator());
539  if (__r->_M_tag == __detail::_S_leaf
540  && __r->_M_size + __slen <= size_t(_S_copy_max))
541  {
542  __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
543  return __result;
544  }
545  if (__detail::_S_concat == __r->_M_tag
546  && __detail::_S_leaf == ((_RopeConcatenation*) __r)->_M_right->_M_tag)
547  {
548  _RopeLeaf* __right =
549  (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right);
550  if (__right->_M_size + __slen <= size_t(_S_copy_max))
551  {
552  _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left;
553  _RopeRep* __nright =
554  _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen);
555  __left->_M_ref_nonnil();
556  __try
557  { __result = _S_tree_concat(__left, __nright); }
558  __catch(...)
559  {
560  _S_unref(__left);
561  _S_unref(__nright);
562  __throw_exception_again;
563  }
564  return __result;
565  }
566  }
567  _RopeRep* __nright =
568  __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->_M_get_allocator());
569  __try
570  {
571  __r->_M_ref_nonnil();
572  __result = _S_tree_concat(__r, __nright);
573  }
574  __catch(...)
575  {
576  _S_unref(__r);
577  _S_unref(__nright);
578  __throw_exception_again;
579  }
580  return __result;
581  }
582 
583 #ifndef __GC
584  template <class _CharT, class _Alloc>
585  typename rope<_CharT,_Alloc>::_RopeRep*
586  rope<_CharT,_Alloc>::
587  _S_destr_concat_char_iter(_RopeRep* __r, const _CharT* __s, size_t __slen)
588  {
589  _RopeRep* __result;
590  if (0 == __r)
591  return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
592  __r->_M_get_allocator());
593  size_t __count = __r->_M_ref_count;
594  size_t __orig_size = __r->_M_size;
595  if (__count > 1)
596  return _S_concat_char_iter(__r, __s, __slen);
597  if (0 == __slen)
598  {
599  __r->_M_ref_count = 2; // One more than before
600  return __r;
601  }
602  if (__orig_size + __slen <= size_t(_S_copy_max)
603  && __detail::_S_leaf == __r->_M_tag)
604  {
605  __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s,
606  __slen);
607  return __result;
608  }
609  if (__detail::_S_concat == __r->_M_tag)
610  {
611  _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*)
612  __r)->_M_right);
613  if (__detail::_S_leaf == __right->_M_tag
614  && __right->_M_size + __slen <= size_t(_S_copy_max))
615  {
616  _RopeRep* __new_right =
617  _S_destr_leaf_concat_char_iter(__right, __s, __slen);
618  if (__right == __new_right)
619  __new_right->_M_ref_count = 1;
620  else
621  __right->_M_unref_nonnil();
622  __r->_M_ref_count = 2; // One more than before.
623  ((_RopeConcatenation*)__r)->_M_right = __new_right;
624  __r->_M_size = __orig_size + __slen;
625  if (0 != __r->_M_c_string)
626  {
627  __r->_M_free_c_string();
628  __r->_M_c_string = 0;
629  }
630  return __r;
631  }
632  }
633  _RopeRep* __right =
634  __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->_M_get_allocator());
635  __r->_M_ref_nonnil();
636  __try
637  { __result = _S_tree_concat(__r, __right); }
638  __catch(...)
639  {
640  _S_unref(__r);
641  _S_unref(__right);
642  __throw_exception_again;
643  }
644  return __result;
645  }
646 #endif /* !__GC */
647 
648  template <class _CharT, class _Alloc>
649  typename rope<_CharT, _Alloc>::_RopeRep*
650  rope<_CharT, _Alloc>::
651  _S_concat(_RopeRep* __left, _RopeRep* __right)
652  {
653  if (0 == __left)
654  {
655  _S_ref(__right);
656  return __right;
657  }
658  if (0 == __right)
659  {
660  __left->_M_ref_nonnil();
661  return __left;
662  }
663  if (__detail::_S_leaf == __right->_M_tag)
664  {
665  if (__detail::_S_leaf == __left->_M_tag)
666  {
667  if (__right->_M_size + __left->_M_size <= size_t(_S_copy_max))
668  return _S_leaf_concat_char_iter((_RopeLeaf*)__left,
669  ((_RopeLeaf*)__right)->_M_data,
670  __right->_M_size);
671  }
672  else if (__detail::_S_concat == __left->_M_tag
673  && __detail::_S_leaf == ((_RopeConcatenation*)
674  __left)->_M_right->_M_tag)
675  {
676  _RopeLeaf* __leftright =
677  (_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right);
678  if (__leftright->_M_size
679  + __right->_M_size <= size_t(_S_copy_max))
680  {
681  _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left;
682  _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright,
683  ((_RopeLeaf*)
684  __right)->
685  _M_data,
686  __right->_M_size);
687  __leftleft->_M_ref_nonnil();
688  __try
689  { return(_S_tree_concat(__leftleft, __rest)); }
690  __catch(...)
691  {
692  _S_unref(__leftleft);
693  _S_unref(__rest);
694  __throw_exception_again;
695  }
696  }
697  }
698  }
699  __left->_M_ref_nonnil();
700  __right->_M_ref_nonnil();
701  __try
702  { return(_S_tree_concat(__left, __right)); }
703  __catch(...)
704  {
705  _S_unref(__left);
706  _S_unref(__right);
707  __throw_exception_again;
708  }
709  }
710 
711  template <class _CharT, class _Alloc>
712  typename rope<_CharT, _Alloc>::_RopeRep*
713  rope<_CharT, _Alloc>::
714  _S_substring(_RopeRep* __base, size_t __start, size_t __endp1)
715  {
716  if (0 == __base)
717  return 0;
718  size_t __len = __base->_M_size;
719  size_t __adj_endp1;
720  const size_t __lazy_threshold = 128;
721 
722  if (__endp1 >= __len)
723  {
724  if (0 == __start)
725  {
726  __base->_M_ref_nonnil();
727  return __base;
728  }
729  else
730  __adj_endp1 = __len;
731 
732  }
733  else
734  __adj_endp1 = __endp1;
735 
736  switch(__base->_M_tag)
737  {
738  case __detail::_S_concat:
739  {
740  _RopeConcatenation* __c = (_RopeConcatenation*)__base;
741  _RopeRep* __left = __c->_M_left;
742  _RopeRep* __right = __c->_M_right;
743  size_t __left_len = __left->_M_size;
744  _RopeRep* __result;
745 
746  if (__adj_endp1 <= __left_len)
747  return _S_substring(__left, __start, __endp1);
748  else if (__start >= __left_len)
749  return _S_substring(__right, __start - __left_len,
750  __adj_endp1 - __left_len);
751  _Self_destruct_ptr __left_result(_S_substring(__left,
752  __start,
753  __left_len));
754  _Self_destruct_ptr __right_result(_S_substring(__right, 0,
755  __endp1
756  - __left_len));
757  __result = _S_concat(__left_result, __right_result);
758  return __result;
759  }
760  case __detail::_S_leaf:
761  {
762  _RopeLeaf* __l = (_RopeLeaf*)__base;
763  _RopeLeaf* __result;
764  size_t __result_len;
765  if (__start >= __adj_endp1)
766  return 0;
767  __result_len = __adj_endp1 - __start;
768  if (__result_len > __lazy_threshold)
769  goto lazy;
770 #ifdef __GC
771  const _CharT* __section = __l->_M_data + __start;
772  __result = _S_new_RopeLeaf(__section, __result_len,
773  __base->_M_get_allocator());
774  __result->_M_c_string = 0; // Not eos terminated.
775 #else
776  // We should sometimes create substring node instead.
777  __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__l->_M_data + __start,
778  __result_len,
779  __base->
780  _M_get_allocator());
781 #endif
782  return __result;
783  }
784  case __detail::_S_substringfn:
785  // Avoid introducing multiple layers of substring nodes.
786  {
787  _RopeSubstring* __old = (_RopeSubstring*)__base;
788  size_t __result_len;
789  if (__start >= __adj_endp1)
790  return 0;
791  __result_len = __adj_endp1 - __start;
792  if (__result_len > __lazy_threshold)
793  {
794  _RopeSubstring* __result =
795  _S_new_RopeSubstring(__old->_M_base,
796  __start + __old->_M_start,
797  __adj_endp1 - __start,
798  __base->_M_get_allocator());
799  return __result;
800 
801  } // *** else fall through: ***
802  }
803  case __detail::_S_function:
804  {
805  _RopeFunction* __f = (_RopeFunction*)__base;
806  _CharT* __section;
807  size_t __result_len;
808  if (__start >= __adj_endp1)
809  return 0;
810  __result_len = __adj_endp1 - __start;
811 
812  if (__result_len > __lazy_threshold)
813  goto lazy;
814  __section = (_CharT*)
815  _Data_allocate(_S_rounded_up_size(__result_len));
816  __try
817  { (*(__f->_M_fn))(__start, __result_len, __section); }
818  __catch(...)
819  {
820  _RopeRep::__STL_FREE_STRING(__section, __result_len,
821  __base->_M_get_allocator());
822  __throw_exception_again;
823  }
824  _S_cond_store_eos(__section[__result_len]);
825  return _S_new_RopeLeaf(__section, __result_len,
826  __base->_M_get_allocator());
827  }
828  }
829  lazy:
830  {
831  // Create substring node.
832  return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start,
833  __base->_M_get_allocator());
834  }
835  }
836 
837  template<class _CharT>
838  class _Rope_flatten_char_consumer
839  : public _Rope_char_consumer<_CharT>
840  {
841  private:
842  _CharT* _M_buf_ptr;
843  public:
844 
845  _Rope_flatten_char_consumer(_CharT* __buffer)
846  { _M_buf_ptr = __buffer; };
847 
848  ~_Rope_flatten_char_consumer() {}
849 
850  bool
851  operator()(const _CharT* __leaf, size_t __n)
852  {
853  uninitialized_copy_n(__leaf, __n, _M_buf_ptr);
854  _M_buf_ptr += __n;
855  return true;
856  }
857  };
858 
859  template<class _CharT>
860  class _Rope_find_char_char_consumer
861  : public _Rope_char_consumer<_CharT>
862  {
863  private:
864  _CharT _M_pattern;
865  public:
866  size_t _M_count; // Number of nonmatching characters
867 
868  _Rope_find_char_char_consumer(_CharT __p)
869  : _M_pattern(__p), _M_count(0) {}
870 
871  ~_Rope_find_char_char_consumer() {}
872 
873  bool
874  operator()(const _CharT* __leaf, size_t __n)
875  {
876  size_t __i;
877  for (__i = 0; __i < __n; __i++)
878  {
879  if (__leaf[__i] == _M_pattern)
880  {
881  _M_count += __i;
882  return false;
883  }
884  }
885  _M_count += __n; return true;
886  }
887  };
888 
889  template<class _CharT, class _Traits>
890  // Here _CharT is both the stream and rope character type.
891  class _Rope_insert_char_consumer
892  : public _Rope_char_consumer<_CharT>
893  {
894  private:
895  typedef basic_ostream<_CharT,_Traits> _Insert_ostream;
896  _Insert_ostream& _M_o;
897  public:
898  _Rope_insert_char_consumer(_Insert_ostream& __writer)
899  : _M_o(__writer) {};
900  ~_Rope_insert_char_consumer() { };
901  // Caller is presumed to own the ostream
902  bool operator() (const _CharT* __leaf, size_t __n);
903  // Returns true to continue traversal.
904  };
905 
906  template<class _CharT, class _Traits>
907  bool
908  _Rope_insert_char_consumer<_CharT, _Traits>::
909  operator()(const _CharT* __leaf, size_t __n)
910  {
911  size_t __i;
912  // We assume that formatting is set up correctly for each element.
913  for (__i = 0; __i < __n; __i++)
914  _M_o.put(__leaf[__i]);
915  return true;
916  }
917 
918  template <class _CharT, class _Alloc>
919  bool
920  rope<_CharT, _Alloc>::
921  _S_apply_to_pieces(_Rope_char_consumer<_CharT>& __c,
922  const _RopeRep* __r, size_t __begin, size_t __end)
923  {
924  if (0 == __r)
925  return true;
926  switch(__r->_M_tag)
927  {
928  case __detail::_S_concat:
929  {
930  _RopeConcatenation* __conc = (_RopeConcatenation*)__r;
931  _RopeRep* __left = __conc->_M_left;
932  size_t __left_len = __left->_M_size;
933  if (__begin < __left_len)
934  {
935  size_t __left_end = std::min(__left_len, __end);
936  if (!_S_apply_to_pieces(__c, __left, __begin, __left_end))
937  return false;
938  }
939  if (__end > __left_len)
940  {
941  _RopeRep* __right = __conc->_M_right;
942  size_t __right_start = std::max(__left_len, __begin);
943  if (!_S_apply_to_pieces(__c, __right,
944  __right_start - __left_len,
945  __end - __left_len))
946  return false;
947  }
948  }
949  return true;
950  case __detail::_S_leaf:
951  {
952  _RopeLeaf* __l = (_RopeLeaf*)__r;
953  return __c(__l->_M_data + __begin, __end - __begin);
954  }
955  case __detail::_S_function:
956  case __detail::_S_substringfn:
957  {
958  _RopeFunction* __f = (_RopeFunction*)__r;
959  size_t __len = __end - __begin;
960  bool __result;
961  _CharT* __buffer =
962  (_CharT*)_Alloc().allocate(__len * sizeof(_CharT));
963  __try
964  {
965  (*(__f->_M_fn))(__begin, __len, __buffer);
966  __result = __c(__buffer, __len);
967  _Alloc().deallocate(__buffer, __len * sizeof(_CharT));
968  }
969  __catch(...)
970  {
971  _Alloc().deallocate(__buffer, __len * sizeof(_CharT));
972  __throw_exception_again;
973  }
974  return __result;
975  }
976  default:
977  return false;
978  }
979  }
980 
981  template<class _CharT, class _Traits>
982  inline void
983  _Rope_fill(basic_ostream<_CharT, _Traits>& __o, size_t __n)
984  {
985  char __f = __o.fill();
986  size_t __i;
987 
988  for (__i = 0; __i < __n; __i++)
989  __o.put(__f);
990  }
991 
992 
993  template <class _CharT>
994  inline bool
995  _Rope_is_simple(_CharT*)
996  { return false; }
997 
998  inline bool
999  _Rope_is_simple(char*)
1000  { return true; }
1001 
1002  inline bool
1003  _Rope_is_simple(wchar_t*)
1004  { return true; }
1005 
1006  template<class _CharT, class _Traits, class _Alloc>
1007  basic_ostream<_CharT, _Traits>&
1008  operator<<(basic_ostream<_CharT, _Traits>& __o,
1009  const rope<_CharT, _Alloc>& __r)
1010  {
1011  size_t __w = __o.width();
1012  bool __left = bool(__o.flags() & std::ios::left);
1013  size_t __pad_len;
1014  size_t __rope_len = __r.size();
1015  _Rope_insert_char_consumer<_CharT, _Traits> __c(__o);
1016  bool __is_simple = _Rope_is_simple((_CharT*)0);
1017 
1018  if (__rope_len < __w)
1019  __pad_len = __w - __rope_len;
1020  else
1021  __pad_len = 0;
1022 
1023  if (!__is_simple)
1024  __o.width(__w / __rope_len);
1025  __try
1026  {
1027  if (__is_simple && !__left && __pad_len > 0)
1028  _Rope_fill(__o, __pad_len);
1029  __r.apply_to_pieces(0, __r.size(), __c);
1030  if (__is_simple && __left && __pad_len > 0)
1031  _Rope_fill(__o, __pad_len);
1032  if (!__is_simple)
1033  __o.width(__w);
1034  }
1035  __catch(...)
1036  {
1037  if (!__is_simple)
1038  __o.width(__w);
1039  __throw_exception_again;
1040  }
1041  return __o;
1042  }
1043 
1044  template <class _CharT, class _Alloc>
1045  _CharT*
1046  rope<_CharT, _Alloc>::
1047  _S_flatten(_RopeRep* __r, size_t __start, size_t __len,
1048  _CharT* __buffer)
1049  {
1050  _Rope_flatten_char_consumer<_CharT> __c(__buffer);
1051  _S_apply_to_pieces(__c, __r, __start, __start + __len);
1052  return(__buffer + __len);
1053  }
1054 
1055  template <class _CharT, class _Alloc>
1056  size_t
1057  rope<_CharT, _Alloc>::
1058  find(_CharT __pattern, size_t __start) const
1059  {
1060  _Rope_find_char_char_consumer<_CharT> __c(__pattern);
1061  _S_apply_to_pieces(__c, this->_M_tree_ptr, __start, size());
1062  size_type __result_pos = __start + __c._M_count;
1063 #ifndef __STL_OLD_ROPE_SEMANTICS
1064  if (__result_pos == size())
1065  __result_pos = npos;
1066 #endif
1067  return __result_pos;
1068  }
1069 
1070  template <class _CharT, class _Alloc>
1071  _CharT*
1072  rope<_CharT, _Alloc>::
1073  _S_flatten(_RopeRep* __r, _CharT* __buffer)
1074  {
1075  if (0 == __r)
1076  return __buffer;
1077  switch(__r->_M_tag)
1078  {
1079  case __detail::_S_concat:
1080  {
1081  _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1082  _RopeRep* __left = __c->_M_left;
1083  _RopeRep* __right = __c->_M_right;
1084  _CharT* __rest = _S_flatten(__left, __buffer);
1085  return _S_flatten(__right, __rest);
1086  }
1087  case __detail::_S_leaf:
1088  {
1089  _RopeLeaf* __l = (_RopeLeaf*)__r;
1090  return copy_n(__l->_M_data, __l->_M_size, __buffer).second;
1091  }
1092  case __detail::_S_function:
1093  case __detail::_S_substringfn:
1094  // We don't yet do anything with substring nodes.
1095  // This needs to be fixed before ropefiles will work well.
1096  {
1097  _RopeFunction* __f = (_RopeFunction*)__r;
1098  (*(__f->_M_fn))(0, __f->_M_size, __buffer);
1099  return __buffer + __f->_M_size;
1100  }
1101  default:
1102  return 0;
1103  }
1104  }
1105 
1106  // This needs work for _CharT != char
1107  template <class _CharT, class _Alloc>
1108  void
1109  rope<_CharT, _Alloc>::
1110  _S_dump(_RopeRep* __r, int __indent)
1111  {
1112  for (int __i = 0; __i < __indent; __i++)
1113  putchar(' ');
1114  if (0 == __r)
1115  {
1116  printf("NULL\n");
1117  return;
1118  }
1119  if (_S_concat == __r->_M_tag)
1120  {
1121  _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1122  _RopeRep* __left = __c->_M_left;
1123  _RopeRep* __right = __c->_M_right;
1124 
1125 #ifdef __GC
1126  printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
1127  __r, __r->_M_depth, __r->_M_size,
1128  __r->_M_is_balanced? "" : "not");
1129 #else
1130  printf("Concatenation %p (rc = %ld, depth = %d, "
1131  "len = %ld, %s balanced)\n",
1132  __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size,
1133  __r->_M_is_balanced? "" : "not");
1134 #endif
1135  _S_dump(__left, __indent + 2);
1136  _S_dump(__right, __indent + 2);
1137  return;
1138  }
1139  else
1140  {
1141  char* __kind;
1142 
1143  switch (__r->_M_tag)
1144  {
1145  case __detail::_S_leaf:
1146  __kind = "Leaf";
1147  break;
1148  case __detail::_S_function:
1149  __kind = "Function";
1150  break;
1151  case __detail::_S_substringfn:
1152  __kind = "Function representing substring";
1153  break;
1154  default:
1155  __kind = "(corrupted kind field!)";
1156  }
1157 #ifdef __GC
1158  printf("%s %p (depth = %d, len = %ld) ",
1159  __kind, __r, __r->_M_depth, __r->_M_size);
1160 #else
1161  printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
1162  __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size);
1163 #endif
1164  if (_S_is_one_byte_char_type((_CharT*)0))
1165  {
1166  const int __max_len = 40;
1167  _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len));
1168  _CharT __buffer[__max_len + 1];
1169  bool __too_big = __r->_M_size > __prefix->_M_size;
1170 
1171  _S_flatten(__prefix, __buffer);
1172  __buffer[__prefix->_M_size] = _S_eos((_CharT*)0);
1173  printf("%s%s\n", (char*)__buffer,
1174  __too_big? "...\n" : "\n");
1175  }
1176  else
1177  printf("\n");
1178  }
1179  }
1180 
1181  template <class _CharT, class _Alloc>
1182  const unsigned long
1183  rope<_CharT, _Alloc>::
1184  _S_min_len[int(__detail::_S_max_rope_depth) + 1] = {
1185  /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21,
1186  /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377,
1187  /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181,
1188  /* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368,
1189  /* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811,
1190  /* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309,
1191  /* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352,
1192  /* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155,
1193  /* 39 */165580141, /* 40 */267914296, /* 41 */433494437,
1194  /* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903,
1195  /* 45 */2971215073u };
1196  // These are Fibonacci numbers < 2**32.
1197 
1198  template <class _CharT, class _Alloc>
1199  typename rope<_CharT, _Alloc>::_RopeRep*
1200  rope<_CharT, _Alloc>::
1201  _S_balance(_RopeRep* __r)
1202  {
1203  _RopeRep* __forest[int(__detail::_S_max_rope_depth) + 1];
1204  _RopeRep* __result = 0;
1205  int __i;
1206  // Invariant:
1207  // The concatenation of forest in descending order is equal to __r.
1208  // __forest[__i]._M_size >= _S_min_len[__i]
1209  // __forest[__i]._M_depth = __i
1210  // References from forest are included in refcount.
1211 
1212  for (__i = 0; __i <= int(__detail::_S_max_rope_depth); ++__i)
1213  __forest[__i] = 0;
1214  __try
1215  {
1216  _S_add_to_forest(__r, __forest);
1217  for (__i = 0; __i <= int(__detail::_S_max_rope_depth); ++__i)
1218  if (0 != __forest[__i])
1219  {
1220 #ifndef __GC
1221  _Self_destruct_ptr __old(__result);
1222 #endif
1223  __result = _S_concat(__forest[__i], __result);
1224  __forest[__i]->_M_unref_nonnil();
1225 #if !defined(__GC) && defined(__EXCEPTIONS)
1226  __forest[__i] = 0;
1227 #endif
1228  }
1229  }
1230  __catch(...)
1231  {
1232  for(__i = 0; __i <= int(__detail::_S_max_rope_depth); __i++)
1233  _S_unref(__forest[__i]);
1234  __throw_exception_again;
1235  }
1236 
1237  if (__result->_M_depth > int(__detail::_S_max_rope_depth))
1238  __throw_length_error(__N("rope::_S_balance"));
1239  return(__result);
1240  }
1241 
1242  template <class _CharT, class _Alloc>
1243  void
1244  rope<_CharT, _Alloc>::
1245  _S_add_to_forest(_RopeRep* __r, _RopeRep** __forest)
1246  {
1247  if (__r->_M_is_balanced)
1248  {
1249  _S_add_leaf_to_forest(__r, __forest);
1250  return;
1251  }
1252 
1253  {
1254  _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1255 
1256  _S_add_to_forest(__c->_M_left, __forest);
1257  _S_add_to_forest(__c->_M_right, __forest);
1258  }
1259  }
1260 
1261 
1262  template <class _CharT, class _Alloc>
1263  void
1264  rope<_CharT, _Alloc>::
1265  _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest)
1266  {
1267  _RopeRep* __insertee; // included in refcount
1268  _RopeRep* __too_tiny = 0; // included in refcount
1269  int __i; // forest[0..__i-1] is empty
1270  size_t __s = __r->_M_size;
1271 
1272  for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i)
1273  {
1274  if (0 != __forest[__i])
1275  {
1276 #ifndef __GC
1277  _Self_destruct_ptr __old(__too_tiny);
1278 #endif
1279  __too_tiny = _S_concat_and_set_balanced(__forest[__i],
1280  __too_tiny);
1281  __forest[__i]->_M_unref_nonnil();
1282  __forest[__i] = 0;
1283  }
1284  }
1285  {
1286 #ifndef __GC
1287  _Self_destruct_ptr __old(__too_tiny);
1288 #endif
1289  __insertee = _S_concat_and_set_balanced(__too_tiny, __r);
1290  }
1291  // Too_tiny dead, and no longer included in refcount.
1292  // Insertee is live and included.
1293  for (;; ++__i)
1294  {
1295  if (0 != __forest[__i])
1296  {
1297 #ifndef __GC
1298  _Self_destruct_ptr __old(__insertee);
1299 #endif
1300  __insertee = _S_concat_and_set_balanced(__forest[__i],
1301  __insertee);
1302  __forest[__i]->_M_unref_nonnil();
1303  __forest[__i] = 0;
1304  }
1305  if (__i == int(__detail::_S_max_rope_depth)
1306  || __insertee->_M_size < _S_min_len[__i+1])
1307  {
1308  __forest[__i] = __insertee;
1309  // refcount is OK since __insertee is now dead.
1310  return;
1311  }
1312  }
1313  }
1314 
1315  template <class _CharT, class _Alloc>
1316  _CharT
1317  rope<_CharT, _Alloc>::
1318  _S_fetch(_RopeRep* __r, size_type __i)
1319  {
1320  __GC_CONST _CharT* __cstr = __r->_M_c_string;
1321 
1322  if (0 != __cstr)
1323  return __cstr[__i];
1324  for(;;)
1325  {
1326  switch(__r->_M_tag)
1327  {
1328  case __detail::_S_concat:
1329  {
1330  _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1331  _RopeRep* __left = __c->_M_left;
1332  size_t __left_len = __left->_M_size;
1333 
1334  if (__i >= __left_len)
1335  {
1336  __i -= __left_len;
1337  __r = __c->_M_right;
1338  }
1339  else
1340  __r = __left;
1341  }
1342  break;
1343  case __detail::_S_leaf:
1344  {
1345  _RopeLeaf* __l = (_RopeLeaf*)__r;
1346  return __l->_M_data[__i];
1347  }
1348  case __detail::_S_function:
1349  case __detail::_S_substringfn:
1350  {
1351  _RopeFunction* __f = (_RopeFunction*)__r;
1352  _CharT __result;
1353 
1354  (*(__f->_M_fn))(__i, 1, &__result);
1355  return __result;
1356  }
1357  }
1358  }
1359  }
1360 
1361 #ifndef __GC
1362  // Return a uniquely referenced character slot for the given
1363  // position, or 0 if that's not possible.
1364  template <class _CharT, class _Alloc>
1365  _CharT*
1366  rope<_CharT, _Alloc>::
1367  _S_fetch_ptr(_RopeRep* __r, size_type __i)
1368  {
1369  _RopeRep* __clrstack[__detail::_S_max_rope_depth];
1370  size_t __csptr = 0;
1371 
1372  for(;;)
1373  {
1374  if (__r->_M_ref_count > 1)
1375  return 0;
1376  switch(__r->_M_tag)
1377  {
1378  case __detail::_S_concat:
1379  {
1380  _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1381  _RopeRep* __left = __c->_M_left;
1382  size_t __left_len = __left->_M_size;
1383 
1384  if (__c->_M_c_string != 0)
1385  __clrstack[__csptr++] = __c;
1386  if (__i >= __left_len)
1387  {
1388  __i -= __left_len;
1389  __r = __c->_M_right;
1390  }
1391  else
1392  __r = __left;
1393  }
1394  break;
1395  case __detail::_S_leaf:
1396  {
1397  _RopeLeaf* __l = (_RopeLeaf*)__r;
1398  if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0)
1399  __clrstack[__csptr++] = __l;
1400  while (__csptr > 0)
1401  {
1402  -- __csptr;
1403  _RopeRep* __d = __clrstack[__csptr];
1404  __d->_M_free_c_string();
1405  __d->_M_c_string = 0;
1406  }
1407  return __l->_M_data + __i;
1408  }
1409  case __detail::_S_function:
1410  case __detail::_S_substringfn:
1411  return 0;
1412  }
1413  }
1414  }
1415 #endif /* __GC */
1416 
1417  // The following could be implemented trivially using
1418  // lexicographical_compare_3way.
1419  // We do a little more work to avoid dealing with rope iterators for
1420  // flat strings.
1421  template <class _CharT, class _Alloc>
1422  int
1423  rope<_CharT, _Alloc>::
1424  _S_compare (const _RopeRep* __left, const _RopeRep* __right)
1425  {
1426  size_t __left_len;
1427  size_t __right_len;
1428 
1429  if (0 == __right)
1430  return 0 != __left;
1431  if (0 == __left)
1432  return -1;
1433  __left_len = __left->_M_size;
1434  __right_len = __right->_M_size;
1435  if (__detail::_S_leaf == __left->_M_tag)
1436  {
1437  _RopeLeaf* __l = (_RopeLeaf*) __left;
1438  if (__detail::_S_leaf == __right->_M_tag)
1439  {
1440  _RopeLeaf* __r = (_RopeLeaf*) __right;
1441  return lexicographical_compare_3way(__l->_M_data,
1442  __l->_M_data + __left_len,
1443  __r->_M_data, __r->_M_data
1444  + __right_len);
1445  }
1446  else
1447  {
1448  const_iterator __rstart(__right, 0);
1449  const_iterator __rend(__right, __right_len);
1450  return lexicographical_compare_3way(__l->_M_data, __l->_M_data
1451  + __left_len,
1452  __rstart, __rend);
1453  }
1454  }
1455  else
1456  {
1457  const_iterator __lstart(__left, 0);
1458  const_iterator __lend(__left, __left_len);
1459  if (__detail::_S_leaf == __right->_M_tag)
1460  {
1461  _RopeLeaf* __r = (_RopeLeaf*) __right;
1462  return lexicographical_compare_3way(__lstart, __lend,
1463  __r->_M_data, __r->_M_data
1464  + __right_len);
1465  }
1466  else
1467  {
1468  const_iterator __rstart(__right, 0);
1469  const_iterator __rend(__right, __right_len);
1470  return lexicographical_compare_3way(__lstart, __lend,
1471  __rstart, __rend);
1472  }
1473  }
1474  }
1475 
1476  // Assignment to reference proxies.
1477  template <class _CharT, class _Alloc>
1478  _Rope_char_ref_proxy<_CharT, _Alloc>&
1479  _Rope_char_ref_proxy<_CharT, _Alloc>::
1480  operator=(_CharT __c)
1481  {
1482  _RopeRep* __old = _M_root->_M_tree_ptr;
1483 #ifndef __GC
1484  // First check for the case in which everything is uniquely
1485  // referenced. In that case we can do this destructively.
1486  _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos);
1487  if (0 != __ptr)
1488  {
1489  *__ptr = __c;
1490  return *this;
1491  }
1492 #endif
1493  _Self_destruct_ptr __left(_My_rope::_S_substring(__old, 0, _M_pos));
1494  _Self_destruct_ptr __right(_My_rope::_S_substring(__old, _M_pos + 1,
1495  __old->_M_size));
1496  _Self_destruct_ptr __result_left(_My_rope::
1497  _S_destr_concat_char_iter(__left,
1498  &__c, 1));
1499 
1500  _RopeRep* __result = _My_rope::_S_concat(__result_left, __right);
1501 #ifndef __GC
1502  _RopeRep::_S_unref(__old);
1503 #endif
1504  _M_root->_M_tree_ptr = __result;
1505  return *this;
1506  }
1507 
1508  template <class _CharT, class _Alloc>
1509  inline _Rope_char_ref_proxy<_CharT, _Alloc>::
1510  operator _CharT() const
1511  {
1512  if (_M_current_valid)
1513  return _M_current;
1514  else
1515  return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos);
1516  }
1517 
1518  template <class _CharT, class _Alloc>
1519  _Rope_char_ptr_proxy<_CharT, _Alloc>
1520  _Rope_char_ref_proxy<_CharT, _Alloc>::
1521  operator&() const
1522  { return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this); }
1523 
1524  template <class _CharT, class _Alloc>
1525  rope<_CharT, _Alloc>::
1526  rope(size_t __n, _CharT __c, const allocator_type& __a)
1527  : _Base(__a)
1528  {
1529  rope<_CharT,_Alloc> __result;
1530  const size_t __exponentiate_threshold = 32;
1531  size_t __exponent;
1532  size_t __rest;
1533  _CharT* __rest_buffer;
1534  _RopeRep* __remainder;
1535  rope<_CharT, _Alloc> __remainder_rope;
1536 
1537  if (0 == __n)
1538  return;
1539 
1540  __exponent = __n / __exponentiate_threshold;
1541  __rest = __n % __exponentiate_threshold;
1542  if (0 == __rest)
1543  __remainder = 0;
1544  else
1545  {
1546  __rest_buffer = this->_Data_allocate(_S_rounded_up_size(__rest));
1547  __uninitialized_fill_n_a(__rest_buffer, __rest, __c,
1548  _M_get_allocator());
1549  _S_cond_store_eos(__rest_buffer[__rest]);
1550  __try
1551  { __remainder = _S_new_RopeLeaf(__rest_buffer, __rest,
1552  _M_get_allocator()); }
1553  __catch(...)
1554  {
1555  _RopeRep::__STL_FREE_STRING(__rest_buffer, __rest,
1556  _M_get_allocator());
1557  __throw_exception_again;
1558  }
1559  }
1560  __remainder_rope._M_tree_ptr = __remainder;
1561  if (__exponent != 0)
1562  {
1563  _CharT* __base_buffer =
1564  this->_Data_allocate(_S_rounded_up_size(__exponentiate_threshold));
1565  _RopeLeaf* __base_leaf;
1566  rope __base_rope;
1567  __uninitialized_fill_n_a(__base_buffer, __exponentiate_threshold, __c,
1568  _M_get_allocator());
1569  _S_cond_store_eos(__base_buffer[__exponentiate_threshold]);
1570  __try
1571  {
1572  __base_leaf = _S_new_RopeLeaf(__base_buffer,
1573  __exponentiate_threshold,
1574  _M_get_allocator());
1575  }
1576  __catch(...)
1577  {
1578  _RopeRep::__STL_FREE_STRING(__base_buffer,
1579  __exponentiate_threshold,
1580  _M_get_allocator());
1581  __throw_exception_again;
1582  }
1583  __base_rope._M_tree_ptr = __base_leaf;
1584  if (1 == __exponent)
1585  __result = __base_rope;
1586  else
1587  __result = power(__base_rope, __exponent,
1588  _Rope_Concat_fn<_CharT, _Alloc>());
1589 
1590  if (0 != __remainder)
1591  __result += __remainder_rope;
1592  }
1593  else
1594  __result = __remainder_rope;
1595 
1596  this->_M_tree_ptr = __result._M_tree_ptr;
1597  this->_M_tree_ptr->_M_ref_nonnil();
1598  }
1599 
1600  template<class _CharT, class _Alloc>
1601  _CharT
1602  rope<_CharT, _Alloc>::_S_empty_c_str[1];
1603 
1604  template<class _CharT, class _Alloc>
1605  const _CharT*
1606  rope<_CharT, _Alloc>::
1607  c_str() const
1608  {
1609  if (0 == this->_M_tree_ptr)
1610  {
1611  _S_empty_c_str[0] = _S_eos((_CharT*)0); // Possibly redundant,
1612  // but probably fast.
1613  return _S_empty_c_str;
1614  }
1615  __gthread_mutex_lock (&this->_M_tree_ptr->_M_c_string_lock);
1616  __GC_CONST _CharT* __result = this->_M_tree_ptr->_M_c_string;
1617  if (0 == __result)
1618  {
1619  size_t __s = size();
1620  __result = this->_Data_allocate(__s + 1);
1621  _S_flatten(this->_M_tree_ptr, __result);
1622  __result[__s] = _S_eos((_CharT*)0);
1623  this->_M_tree_ptr->_M_c_string = __result;
1624  }
1625  __gthread_mutex_unlock (&this->_M_tree_ptr->_M_c_string_lock);
1626  return(__result);
1627  }
1628 
1629  template<class _CharT, class _Alloc>
1630  const _CharT* rope<_CharT, _Alloc>::
1631  replace_with_c_str()
1632  {
1633  if (0 == this->_M_tree_ptr)
1634  {
1635  _S_empty_c_str[0] = _S_eos((_CharT*)0);
1636  return _S_empty_c_str;
1637  }
1638  __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string;
1639  if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag
1640  && 0 != __old_c_string)
1641  return(__old_c_string);
1642  size_t __s = size();
1643  _CharT* __result = this->_Data_allocate(_S_rounded_up_size(__s));
1644  _S_flatten(this->_M_tree_ptr, __result);
1645  __result[__s] = _S_eos((_CharT*)0);
1646  this->_M_tree_ptr->_M_unref_nonnil();
1647  this->_M_tree_ptr = _S_new_RopeLeaf(__result, __s,
1648  this->_M_get_allocator());
1649  return(__result);
1650  }
1651 
1652  // Algorithm specializations. More should be added.
1653 
1654  template<class _Rope_iterator> // was templated on CharT and Alloc
1655  void // VC++ workaround
1656  _Rope_rotate(_Rope_iterator __first,
1657  _Rope_iterator __middle,
1658  _Rope_iterator __last)
1659  {
1660  typedef typename _Rope_iterator::value_type _CharT;
1661  typedef typename _Rope_iterator::_allocator_type _Alloc;
1662 
1663  rope<_CharT, _Alloc>& __r(__first.container());
1664  rope<_CharT, _Alloc> __prefix = __r.substr(0, __first.index());
1665  rope<_CharT, _Alloc> __suffix =
1666  __r.substr(__last.index(), __r.size() - __last.index());
1667  rope<_CharT, _Alloc> __part1 =
1668  __r.substr(__middle.index(), __last.index() - __middle.index());
1669  rope<_CharT, _Alloc> __part2 =
1670  __r.substr(__first.index(), __middle.index() - __first.index());
1671  __r = __prefix;
1672  __r += __part1;
1673  __r += __part2;
1674  __r += __suffix;
1675  }
1676 
1677 #if !defined(__GNUC__)
1678  // Appears to confuse g++
1679  inline void
1680  rotate(_Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __first,
1681  _Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __middle,
1682  _Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __last)
1683  { _Rope_rotate(__first, __middle, __last); }
1684 #endif
1685 
1686 # if 0
1687  // Probably not useful for several reasons:
1688  // - for SGIs 7.1 compiler and probably some others,
1689  // this forces lots of rope<wchar_t, ...> instantiations, creating a
1690  // code bloat and compile time problem. (Fixed in 7.2.)
1691  // - wchar_t is 4 bytes wide on most UNIX platforms, making it
1692  // unattractive for unicode strings. Unsigned short may be a better
1693  // character type.
1694  inline void
1695  rotate(_Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __first,
1696  _Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __middle,
1697  _Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __last)
1698  { _Rope_rotate(__first, __middle, __last); }
1699 # endif
1700 
1701 _GLIBCXX_END_NAMESPACE_VERSION
1702 } // namespace
1703