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