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