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