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