include/c++/stl/stl/_rope.c

   1 /*
   2  * Copyright (c) 1996,1997
   3  * Silicon Graphics Computer Systems, Inc.
   4  *
   5  * Copyright (c) 1999
   6  * Boris Fomitchev
   7  *
   8  * This material is provided "as is", with absolutely no warranty expressed
   9  * or implied. Any use is at your own risk.
  10  *
  11  * Permission to use or copy this software for any purpose is hereby granted
  12  * without fee, provided the above notices are retained on all copies.
  13  * Permission to modify the code and to distribute modified code is granted,
  14  * provided the above notices are retained, and a notice that the code was
  15  * modified is included with the above copyright notice.
  16  *
  17  */
  18
  19 /* NOTE: This is an internal header file, included by other STL headers.
  20  *   You should not attempt to use it directly.
  21  */
  22
  23 // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
  24 // if necessary.  Assumes path_end[leaf_index] and leaf_pos are correct.
  25 // Results in a valid buf_ptr if the iterator can be legitimately
  26 // dereferenced.
  27 #ifndef _STLP_ROPEIMPL_H
  28 #define _STLP_ROPEIMPL_H
  29
  30 #ifndef _STLP_INTERNAL_ROPE_H
  31 #  include <stl/_rope.h>
  32 #endif
  33
  34 #ifndef _STLP_INTERNAL_CSTDIO
  35 #  include <stl/_cstdio.h>
  36 #endif
  37
  38 #if !defined (_STLP_USE_NO_IOSTREAMS)
  39 #  ifndef _STLP_IOSTREAM
  40 #    include <iostream>
  41 #  endif
  42 #endif
  43
  44 #include <stl/_range_errors.h>
  45
  46 _STLP_BEGIN_NAMESPACE
  47
  48 # if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
  49 # define __allocator__ _Alloc
  50 # else
  51 # define __allocator__ allocator_type
  52 # endif
  53
  54 template<class _CharT, class _Alloc>
  55 _Rope_iterator<_CharT, _Alloc>::_Rope_iterator(rope<_CharT,_Alloc>* __r, size_t __pos)
  56   : _Rope_iterator_base<_CharT,_Alloc>(__r->_M_tree_ptr._M_data, __pos),
  57   _M_root_rope(__r) { _RopeRep::_S_ref(this->_M_root); }
  58
  59 template<class _CharT, class _Alloc>
  60 _Rope_iterator<_CharT, _Alloc>::_Rope_iterator(rope<_CharT,_Alloc>& __r, size_t __pos):
  61   _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr._M_data, __pos),
  62   _M_root_rope(&__r) {
  63 #if !defined (__DMC__)
  64   _RopeRep::_S_ref(this->_M_root); if (!(__r.empty()))_S_setcache(*this);
  65 #else
  66   _Rope_iterator_base<_CharT, _Alloc>* __x = this;
  67   _RopeRep::_S_ref(this->_M_root); if (!(__r.empty()))_S_setcache(*__x);
  68 #endif
  69 }
  70
  71 template<class _CharT, class _Alloc>
  72 void _Rope_RopeRep<_CharT, _Alloc>::_M_free_c_string() {
  73   _CharT* __cstr = _M_c_string;
  74   if (0 != __cstr) {
  75     size_t _p_size = _M_size._M_data + 1;
  76     _STLP_STD::_Destroy_Range(__cstr, __cstr + _p_size);
  77     _M_size.deallocate(__cstr, _p_size);
  78   }
  79 }
  80
  81 // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
  82 // if necessary.  Assumes _M_path_end[leaf_index] and leaf_pos are correct.
  83 // Results in a valid buf_ptr if the iterator can be legitimately
  84 // dereferenced.
  85 template <class _CharT, class _Alloc>
  86 void _Rope_iterator_base<_CharT,_Alloc>::_S_setbuf(
  87   _Rope_iterator_base<_CharT,_Alloc>& __x) {
  88   const _RopeRep* __leaf = __x._M_path_end._M_data[__x._M_leaf_index];
  89   size_t __leaf_pos = __x._M_leaf_pos;
  90   size_t __pos = __x._M_current_pos;
  91
  92   switch(__leaf->_M_tag) {
  93   case _RopeRep::_S_leaf:
  94     typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf;
  95     __x._M_buf_start = __STATIC_CAST(const _RopeLeaf*, __leaf)->_M_data;
  96     __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos);
  97     __x._M_buf_end = __x._M_buf_start + __leaf->_M_size._M_data;
  98     break;
  99   case _RopeRep::_S_function:
 100   case _RopeRep::_S_substringfn:
 101     {
 102       size_t __len = _S_iterator_buf_len;
 103       size_t __buf_start_pos = __leaf_pos;
 104       size_t __leaf_end = __leaf_pos + __leaf->_M_size._M_data;
 105       typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction;
 106       char_producer<_CharT>* __fn = __STATIC_CAST(const _RopeFunction*, __leaf)->_M_fn;
 107
 108       if (__buf_start_pos + __len <= __pos) {
 109         __buf_start_pos = __pos - __len/4;
 110         if (__buf_start_pos + __len > __leaf_end) {
 111           __buf_start_pos = __leaf_end - __len;
 112         }
 113       }
 114       if (__buf_start_pos + __len > __leaf_end) {
 115         __len = __leaf_end - __buf_start_pos;
 116       }
 117       (*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf._M_data);
 118       __x._M_buf_ptr = __x._M_tmp_buf._M_data + (__pos - __buf_start_pos);
 119       __x._M_buf_start = __x._M_tmp_buf._M_data;
 120       __x._M_buf_end = __x._M_tmp_buf._M_data + __len;
 121     }
 122     break;
 123   default:
 124       _STLP_ASSERT(0)
 125       ;
 126   }
 127 }
 128
 129 // Set path and buffer inside a rope iterator.  We assume that
 130 // pos and root are already set.
 131 template <class _CharT, class _Alloc>
 132 void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache(
 133   _Rope_iterator_base<_CharT,_Alloc>& __x) {
 134   const _RopeRep* __path[_RopeRep::_S_max_rope_depth+1];
 135   const _RopeRep* __curr_rope;
 136   int __curr_depth = -1;  /* index into path    */
 137   size_t __curr_start_pos = 0;
 138   size_t __pos = __x._M_current_pos;
 139   unsigned char __dirns = 0; // Bit vector marking right turns in the path
 140
 141   _STLP_ASSERT(__pos <= __x._M_root->_M_size._M_data)
 142   if (__pos >= __x._M_root->_M_size._M_data) {
 143     __x._M_buf_ptr = 0;
 144     return;
 145   }
 146   __curr_rope = __x._M_root;
 147   if (0 != __curr_rope->_M_c_string) {
 148     /* Treat the root as a leaf. */
 149     __x._M_buf_start = __curr_rope->_M_c_string;
 150     __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size._M_data;
 151     __x._M_buf_ptr = __curr_rope->_M_c_string + __pos;
 152     __x._M_path_end._M_data[0] = __curr_rope;
 153     __x._M_leaf_index = 0;
 154     __x._M_leaf_pos = 0;
 155     return;
 156   }
 157   for(;;) {
 158     ++__curr_depth;
 159     _STLP_ASSERT(__curr_depth <= _RopeRep::_S_max_rope_depth)
 160     __path[__curr_depth] = __curr_rope;
 161     switch(__curr_rope->_M_tag) {
 162     case _RopeRep::_S_leaf:
 163     case _RopeRep::_S_function:
 164     case _RopeRep::_S_substringfn:
 165       __x._M_leaf_pos = __curr_start_pos;
 166       goto done;
 167     case _RopeRep::_S_concat:
 168       {
 169         const _RopeConcat* __c = __STATIC_CAST(const _RopeConcat*, __curr_rope);
 170         _RopeRep* __left = __c->_M_left;
 171         size_t __left_len = __left->_M_size._M_data;
 172
 173         __dirns <<= 1;
 174         if (__pos >= __curr_start_pos + __left_len) {
 175           __dirns |= 1;
 176           __curr_rope = __c->_M_right;
 177           __curr_start_pos += __left_len;
 178         } else {
 179           __curr_rope = __left;
 180         }
 181       }
 182       break;
 183     }
 184   }
 185 done:
 186     // Copy last section of path into _M_path_end.
 187   {
 188     int __i = -1;
 189     int __j = __curr_depth + 1 - _S_path_cache_len;
 190
 191     if (__j < 0) __j = 0;
 192     while (__j <= __curr_depth) {
 193       __x._M_path_end._M_data[++__i] = __path[__j++];
 194     }
 195     __x._M_leaf_index = __i;
 196   }
 197   __x._M_path_directions = __dirns;
 198   _S_setbuf(__x);
 199 }
 200
 201 // Specialized version of the above.  Assumes that
 202 // the path cache is valid for the previous position.
 203 template <class _CharT, class _Alloc>
 204 void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache_for_incr(
 205 _Rope_iterator_base<_CharT,_Alloc>& __x) {
 206   int __current_index = __x._M_leaf_index;
 207   const _RopeRep* __current_node = __x._M_path_end._M_data[__current_index];
 208   size_t __len = __current_node->_M_size._M_data;
 209   size_t __node_start_pos = __x._M_leaf_pos;
 210   unsigned char __dirns = __x._M_path_directions;
 211   const _RopeConcat* __c;
 212
 213   _STLP_ASSERT(__x._M_current_pos <= __x._M_root->_M_size._M_data)
 214   if (__x._M_current_pos - __node_start_pos < __len) {
 215     /* More stuff in this leaf, we just didn't cache it. */
 216     _S_setbuf(__x);
 217     return;
 218   }
 219   _STLP_ASSERT(__node_start_pos + __len == __x._M_current_pos)
 220     //  node_start_pos is starting position of last_node.
 221   while (--__current_index >= 0) {
 222     if (!(__dirns & 1) /* Path turned left */)
 223       break;
 224     __current_node = __x._M_path_end._M_data[__current_index];
 225     __c = __STATIC_CAST(const _RopeConcat*, __current_node);
 226     // Otherwise we were in the right child.  Thus we should pop
 227     // the concatenation node.
 228     __node_start_pos -= __c->_M_left->_M_size._M_data;
 229     __dirns >>= 1;
 230   }
 231   if (__current_index < 0) {
 232     // We underflowed the cache. Punt.
 233     _S_setcache(__x);
 234     return;
 235   }
 236   __current_node = __x._M_path_end._M_data[__current_index];
 237   __c = __STATIC_CAST(const _RopeConcat*, __current_node);
 238   // current_node is a concatenation node.  We are positioned on the first
 239   // character in its right child.
 240   // node_start_pos is starting position of current_node.
 241   __node_start_pos += __c->_M_left->_M_size._M_data;
 242   __current_node = __c->_M_right;
 243   __x._M_path_end._M_data[++__current_index] = __current_node;
 244   __dirns |= 1;
 245   while (_RopeRep::_S_concat == __current_node->_M_tag) {
 246     ++__current_index;
 247     if (_S_path_cache_len == __current_index) {
 248       int __i;
 249       for (__i = 0; __i < _S_path_cache_len-1; ++__i) {
 250         __x._M_path_end._M_data[__i] = __x._M_path_end._M_data[__i+1];
 251       }
 252       --__current_index;
 253     }
 254     __current_node = __STATIC_CAST(const _RopeConcat*, __current_node)->_M_left;
 255     __x._M_path_end._M_data[__current_index] = __current_node;
 256     __dirns <<= 1;
 257     // node_start_pos is unchanged.
 258   }
 259   __x._M_leaf_index = __current_index;
 260   __x._M_leaf_pos = __node_start_pos;
 261   __x._M_path_directions = __dirns;
 262   _S_setbuf(__x);
 263 }
 264
 265 template <class _CharT, class _Alloc>
 266 void _Rope_iterator_base<_CharT,_Alloc>::_M_incr(size_t __n) {
 267   _M_current_pos += __n;
 268   if (0 != _M_buf_ptr) {
 269     size_t __chars_left = _M_buf_end - _M_buf_ptr;
 270     if (__chars_left > __n) {
 271       _M_buf_ptr += __n;
 272     } else if (__chars_left == __n) {
 273       _M_buf_ptr += __n;
 274       _S_setcache_for_incr(*this);
 275     } else {
 276       _M_buf_ptr = 0;
 277     }
 278   }
 279 }
 280
 281 template <class _CharT, class _Alloc>
 282 void _Rope_iterator_base<_CharT,_Alloc>::_M_decr(size_t __n) {
 283   if (0 != _M_buf_ptr) {
 284     size_t __chars_left = _M_buf_ptr - _M_buf_start;
 285     if (__chars_left >= __n) {
 286       _M_buf_ptr -= __n;
 287     } else {
 288       _M_buf_ptr = 0;
 289     }
 290   }
 291   _M_current_pos -= __n;
 292 }
 293
 294 template <class _CharT, class _Alloc>
 295 void _Rope_iterator<_CharT,_Alloc>::_M_check() {
 296   if (_M_root_rope->_M_tree_ptr._M_data != this->_M_root) {
 297     // _Rope was modified.  Get things fixed up.
 298     _RopeRep::_S_unref(this->_M_root);
 299     this->_M_root = _M_root_rope->_M_tree_ptr._M_data;
 300     _RopeRep::_S_ref(this->_M_root);
 301     this->_M_buf_ptr = 0;
 302   }
 303 }
 304
 305 //  There are several reasons for not doing this with virtual destructors
 306 //  and a class specific delete operator:
 307 //  - A class specific delete operator can't easily get access to
 308 //    allocator instances if we need them.
 309 //  - Any virtual function would need a 4 or byte vtable pointer;
 310 //    this only requires a one byte tag per object.
 311 template <class _CharT, class _Alloc>
 312 void _Rope_RopeRep<_CharT,_Alloc>::_M_free_tree() {
 313   switch (_M_tag) {
 314   case _S_leaf:
 315     {
 316       typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf;
 317       _RopeLeaf* __l = __STATIC_CAST(_RopeLeaf*, this);
 318       _STLP_STD::_Destroy(__l); // ->_Rope_RopeLeaf<_CharT,_Alloc>::~_Rope_RopeLeaf();
 319       _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_size,
 320                              _RopeLeaf).deallocate(__l, 1);
 321       break;
 322     }
 323   case _S_concat:
 324     {
 325       typedef _Rope_RopeConcatenation<_CharT, _Alloc> _RopeConcatenation;
 326       _RopeConcatenation* __c  = __STATIC_CAST(_RopeConcatenation*, this);
 327       _STLP_STD::_Destroy(__c);
 328       _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_size,
 329                              _RopeConcatenation).deallocate(__c, 1);
 330       break;
 331     }
 332   case _S_function:
 333     {
 334       typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction;
 335       _RopeFunction* __f = __STATIC_CAST(_RopeFunction*, this);
 336       _STLP_STD::_Destroy(__f);
 337       _STLP_CREATE_ALLOCATOR(allocator_type, (const allocator_type&)_M_size,
 338                              _RopeFunction).deallocate(__f, 1);
 339       break;
 340     }
 341   case _S_substringfn:
 342     {
 343       typedef _Rope_RopeSubstring<_CharT, _Alloc> _RopeSubstring;
 344       _RopeSubstring* __rss = __STATIC_CAST(_RopeSubstring*, this);
 345       _STLP_STD::_Destroy(__rss);
 346       _STLP_CREATE_ALLOCATOR(allocator_type, (const allocator_type&)_M_size,
 347                              _RopeSubstring).deallocate(__rss, 1);
 348       break;
 349     }
 350   }
 351 }
 352
 353 # if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
 354 #   define __RopeLeaf__ _Rope_RopeLeaf<_CharT,_Alloc>
 355 #   define __RopeRep__ _Rope_RopeRep<_CharT,_Alloc>
 356 #   define _RopeLeaf _Rope_RopeLeaf<_CharT,_Alloc>
 357 #   define _RopeRep _Rope_RopeRep<_CharT,_Alloc>
 358 #   define size_type size_t
 359 # else
 360 #   define __RopeLeaf__ _STLP_TYPENAME_ON_RETURN_TYPE rope<_CharT,_Alloc>::_RopeLeaf
 361 #   define __RopeRep__ _STLP_TYPENAME_ON_RETURN_TYPE rope<_CharT,_Alloc>::_RopeRep
 362 # endif
 363
 364 template <class _CharT, class _Alloc>
 365 void rope<_CharT, _Alloc>::_M_throw_out_of_range() const {
 366   __stl_throw_out_of_range("rope");
 367 }
 368
 369 // Concatenate a C string onto a leaf rope by copying the rope data.
 370 // Used for short ropes.
 371 template <class _CharT, class _Alloc>
 372 __RopeLeaf__*
 373 rope<_CharT,_Alloc>::_S_leaf_concat_char_iter (
 374   _RopeLeaf* __r, const _CharT* __iter, size_t __len) {
 375   size_t __old_len = __r->_M_size._M_data;
 376   _CharT* __new_data = __r->_M_size.allocate(_S_rounded_up_size(__old_len + __len));
 377   _RopeLeaf* __result;
 378
 379   _STLP_PRIV __ucopy_n(__r->_M_data, __old_len, __new_data);
 380   _STLP_PRIV __ucopy_n(__iter, __len, __new_data + __old_len);
 381   _S_construct_null(__new_data + __old_len + __len);
 382   _STLP_TRY {
 383     __result = _S_new_RopeLeaf(__new_data, __old_len + __len, __r->get_allocator());
 384   }
 385   _STLP_UNWIND(_RopeRep::_S_free_string(__new_data, __old_len + __len,
 386                                         __r->get_allocator()))
 387   return __result;
 388 }
 389
 390 template <class _CharT, class _Alloc>
 391 void _Terminate_RopeLeaf(_Rope_RopeLeaf<_CharT,_Alloc> *__r,
 392                          size_t __size, const __true_type& /*basic char type*/) {
 393   _S_construct_null(__r->_M_data + __size);
 394   _STLP_ASSERT(__r->_M_c_string == __r->_M_data)
 395 }
 396
 397 template <class _CharT, class _Alloc>
 398 void _Terminate_RopeLeaf(_Rope_RopeLeaf<_CharT,_Alloc> *__r,
 399                          size_t, const __false_type& /*basic char type*/) {
 400   if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string) {
 401     __r->_M_free_c_string();
 402     __r->_M_c_string = 0;
 403   }
 404 }
 405
 406 // As above, but it's OK to clobber original if refcount is 1
 407 template <class _CharT, class _Alloc>
 408 __RopeLeaf__*
 409 rope<_CharT,_Alloc>::_S_destr_leaf_concat_char_iter (_RopeLeaf* __r, const _CharT* __iter, size_t __len) {
 410   //_STLP_ASSERT(__r->_M_ref_count >= 1)
 411   if ( /* __r->_M_ref_count > 1 */  __r->_M_incr() > 2 ) { // - ptr
 412     __r->_M_decr(); // - ptr
 413     return _S_leaf_concat_char_iter(__r, __iter, __len);
 414   }
 415   __r->_M_decr(); // - ptr, __r->_M_ref_count == 1 or 0
 416   size_t __old_len = __r->_M_size._M_data;
 417   if (_S_rounded_up_size(__old_len) == _S_rounded_up_size(__old_len + __len)) {
 418     // The space has been partially initialized for the standard
 419     // character types.  But that doesn't matter for those types.
 420     _STLP_PRIV __ucopy_n(__iter, __len, __r->_M_data + __old_len);
 421     _Terminate_RopeLeaf(__r, __old_len + __len, _IsBasicCharType());
 422     __r->_M_size._M_data = __old_len + __len;
 423     // _STLP_ASSERT(__r->_M_ref_count == 1)
 424     // __r->_M_ref_count = 2;
 425     __r->_M_incr(); // i.e.  __r->_M_ref_count = 2
 426     return __r;
 427   } else {
 428     _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len);
 429     //_STLP_ASSERT(__result->_M_ref_count == 1)
 430     return __result;
 431   }
 432 }
 433
 434 // Assumes left and right are not 0.
 435 // Does not increment (nor decrement on exception) child reference counts.
 436 // Result has ref count 1.
 437 template <class _CharT, class _Alloc>
 438 __RopeRep__*
 439 rope<_CharT,_Alloc>::_S_tree_concat (_RopeRep* __left, _RopeRep* __right) {
 440   _RopeConcatenation* __result =
 441     _S_new_RopeConcatenation(__left, __right, __left->get_allocator());
 442   size_t __depth = __result->_M_depth;
 443
 444   _STLP_ASSERT(__left->get_allocator() == __right->get_allocator())
 445   if (__depth > 20 && (__result->_M_size._M_data < 1000 ||
 446       __depth > _RopeRep::_S_max_rope_depth)) {
 447     _RopeRep* __balanced;
 448
 449     _STLP_TRY {
 450       __balanced = _S_balance(__result);
 451      // _STLP_ASSERT(__result == __balanced ||
 452      //              1 == __result->_M_ref_count &&
 453      //              1 == __balanced->_M_ref_count)
 454       __result->_M_unref_nonnil();
 455     }
 456     _STLP_UNWIND((_STLP_CREATE_ALLOCATOR(allocator_type,(allocator_type&)__left->_M_size,
 457                                          _RopeConcatenation).deallocate(__result,1)))
 458     // In case of exception, we need to deallocate
 459     // otherwise dangling result node.  But caller
 460     // still owns its children.  Thus unref is
 461     // inappropriate.
 462     return __balanced;
 463   } else {
 464     return __result;
 465   }
 466 }
 467
 468 template <class _CharT, class _Alloc>
 469 __RopeRep__*
 470 rope<_CharT,_Alloc>::_S_concat_char_iter (_RopeRep* __r,
 471                                           const _CharT*__s, size_t __slen) {
 472   _RopeRep* __result;
 473   if (0 == __slen) {
 474     _S_ref(__r);
 475     return __r;
 476   }
 477   if (0 == __r)
 478     return _S_RopeLeaf_from_unowned_char_ptr(__s, __slen, __r->get_allocator());
 479   if (_RopeRep::_S_leaf == __r->_M_tag &&
 480       __r->_M_size._M_data + __slen <= _S_copy_max) {
 481     __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
 482     // _STLP_ASSERT(1 == __result->_M_ref_count)
 483     return __result;
 484   }
 485   if (_RopeRep::_S_concat == __r->_M_tag &&
 486       _RopeRep::_S_leaf == ((_RopeConcatenation*)__r)->_M_right->_M_tag) {
 487     _RopeLeaf* __right = (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right);
 488     if (__right->_M_size._M_data + __slen <= _S_copy_max) {
 489       _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left;
 490       _RopeRep* __nright = _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen);
 491       __left->_M_ref_nonnil();
 492       _STLP_TRY {
 493         __result = _S_tree_concat(__left, __nright);
 494       }
 495       _STLP_UNWIND(_S_unref(__left); _S_unref(__nright))
 496       // _STLP_ASSERT(1 == __result->_M_ref_count)
 497       return __result;
 498     }
 499   }
 500   _RopeRep* __nright =
 501     _S_RopeLeaf_from_unowned_char_ptr(__s, __slen, __r->get_allocator());
 502   _STLP_TRY {
 503     __r->_M_ref_nonnil();
 504     __result = _S_tree_concat(__r, __nright);
 505   }
 506   _STLP_UNWIND(_S_unref(__r); _S_unref(__nright))
 507   // _STLP_ASSERT(1 == __result->_M_ref_count)
 508   return __result;
 509 }
 510
 511 template <class _CharT, class _Alloc>
 512 __RopeRep__*
 513 rope<_CharT,_Alloc>::_S_destr_concat_char_iter(
 514   _RopeRep* __r, const _CharT* __s, size_t __slen) {
 515   _RopeRep* __result;
 516   if (0 == __r)
 517     return _S_RopeLeaf_from_unowned_char_ptr(__s, __slen,
 518                                              __r->get_allocator());
 519   // size_t __count = __r->_M_ref_count;
 520   size_t __orig_size = __r->_M_size._M_data;
 521   // _STLP_ASSERT(__count >= 1)
 522   if ( /* __count > 1 */ __r->_M_incr() > 2 ) {
 523     __r->_M_decr();
 524     return _S_concat_char_iter(__r, __s, __slen);
 525   }
 526   if (0 == __slen) {
 527     return __r;
 528   }
 529   __r->_M_decr();
 530   if (__orig_size + __slen <= _S_copy_max && _RopeRep::_S_leaf == __r->_M_tag) {
 531     return _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
 532   }
 533   if (_RopeRep::_S_concat == __r->_M_tag) {
 534     _RopeLeaf* __right = __STATIC_CAST(_RopeLeaf*, __STATIC_CAST(_RopeConcatenation*, __r)->_M_right);
 535     if (_RopeRep::_S_leaf == __right->_M_tag &&
 536         __right->_M_size._M_data + __slen <= _S_copy_max) {
 537       _RopeRep* __new_right = _S_destr_leaf_concat_char_iter(__right, __s, __slen);
 538       if (__right == __new_right) {
 539         // _STLP_ASSERT(__new_right->_M_ref_count == 2)
 540         // __new_right->_M_ref_count = 1;
 541         __new_right->_M_decr();
 542       } else {
 543         // _STLP_ASSERT(__new_right->_M_ref_count >= 1)
 544         __right->_M_unref_nonnil();
 545       }
 546       // _STLP_ASSERT(__r->_M_ref_count == 1)
 547       // __r->_M_ref_count = 2;    // One more than before.
 548       __r->_M_incr();
 549       __STATIC_CAST(_RopeConcatenation*, __r)->_M_right = __new_right;
 550       // E.Musser : moved below
 551       //    __r->_M_size._M_data = __orig_size + __slen;
 552       if (0 != __r->_M_c_string) {
 553         __r->_M_free_c_string();
 554         __r->_M_c_string = 0;
 555       }
 556       __r->_M_size._M_data = __orig_size + __slen;
 557       return __r;
 558     }
 559   }
 560   _RopeRep* __right =
 561     _S_RopeLeaf_from_unowned_char_ptr(__s, __slen, __r->get_allocator());
 562   __r->_M_ref_nonnil();
 563   _STLP_TRY {
 564     __result = _S_tree_concat(__r, __right);
 565   }
 566   _STLP_UNWIND(_S_unref(__r); _S_unref(__right))
 567     // _STLP_ASSERT(1 == __result->_M_ref_count)
 568   return __result;
 569 }
 570
 571 template <class _CharT, class _Alloc>
 572 __RopeRep__*
 573 rope<_CharT,_Alloc>::_S_concat_rep(_RopeRep* __left, _RopeRep* __right) {
 574   if (0 == __left) {
 575     _S_ref(__right);
 576     return __right;
 577   }
 578   if (0 == __right) {
 579     __left->_M_ref_nonnil();
 580     return __left;
 581   }
 582   if (_RopeRep::_S_leaf == __right->_M_tag) {
 583     if (_RopeRep::_S_leaf == __left->_M_tag) {
 584       if (__right->_M_size._M_data + __left->_M_size._M_data <= _S_copy_max) {
 585         return _S_leaf_concat_char_iter(__STATIC_CAST(_RopeLeaf*, __left),
 586                                         __STATIC_CAST(_RopeLeaf*, __right)->_M_data,
 587                                         __right->_M_size._M_data);
 588       }
 589     } else if (_RopeRep::_S_concat == __left->_M_tag &&
 590                _RopeRep::_S_leaf == __STATIC_CAST(_RopeConcatenation*, __left)->_M_right->_M_tag) {
 591       _RopeLeaf* __leftright =
 592         __STATIC_CAST(_RopeLeaf*, __STATIC_CAST(_RopeConcatenation*, __left)->_M_right);
 593       if (__leftright->_M_size._M_data + __right->_M_size._M_data <= _S_copy_max) {
 594         _RopeRep* __leftleft = __STATIC_CAST(_RopeConcatenation*, __left)->_M_left;
 595         _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright,
 596                                                     __STATIC_CAST(_RopeLeaf*, __right)->_M_data,
 597                                                     __right->_M_size._M_data);
 598         __leftleft->_M_ref_nonnil();
 599         _STLP_TRY {
 600           return _S_tree_concat(__leftleft, __rest);
 601         }
 602         _STLP_UNWIND(_S_unref(__leftleft); _S_unref(__rest))
 603       }
 604     }
 605   }
 606   __left->_M_ref_nonnil();
 607   __right->_M_ref_nonnil();
 608   _STLP_TRY {
 609     return _S_tree_concat(__left, __right);
 610   }
 611   _STLP_UNWIND(_S_unref(__left); _S_unref(__right))
 612   _STLP_RET_AFTER_THROW(0)
 613 }
 614
 615 template <class _CharT, class _Alloc>
 616 __RopeRep__*
 617 rope<_CharT,_Alloc>::_S_substring(_RopeRep* __base,
 618                                   size_t __start, size_t __endp1) {
 619   if (0 == __base) return 0;
 620   size_t __len = __base->_M_size._M_data;
 621   size_t __adj_endp1;
 622   const size_t __lazy_threshold = 128;
 623
 624   if (__endp1 >= __len) {
 625     if (0 == __start) {
 626       __base->_M_ref_nonnil();
 627       return __base;
 628     } else {
 629       __adj_endp1 = __len;
 630     }
 631   } else {
 632     __adj_endp1 = __endp1;
 633   }
 634   switch(__base->_M_tag) {
 635   case _RopeRep::_S_concat:
 636   {
 637     _RopeConcatenation* __c = __STATIC_CAST(_RopeConcatenation*, __base);
 638     _RopeRep* __left = __c->_M_left;
 639     _RopeRep* __right = __c->_M_right;
 640     size_t __left_len = __left->_M_size._M_data;
 641     _RopeRep* __result;
 642
 643     if (__adj_endp1 <= __left_len) {
 644       return _S_substring(__left, __start, __endp1);
 645     } else if (__start >= __left_len) {
 646       return _S_substring(__right, __start - __left_len,
 647                           __adj_endp1 - __left_len);
 648     }
 649     _Self_destruct_ptr __left_result(_S_substring(__left, __start, __left_len));
 650     _Self_destruct_ptr __right_result(_S_substring(__right, 0, __endp1 - __left_len));
 651     _STLP_MPWFIX_TRY    //*TY 06/01/2000 - mpw forgets to call dtor on __left_result and __right_result without this try block
 652     __result = _S_concat_rep(__left_result, __right_result);
 653     // _STLP_ASSERT(1 == __result->_M_ref_count)
 654     return __result;
 655     _STLP_MPWFIX_CATCH    //*TY 06/01/2000 -
 656   }
 657   case _RopeRep::_S_leaf:
 658   {
 659     _RopeLeaf* __l = __STATIC_CAST(_RopeLeaf*, __base);
 660     _RopeLeaf* __result;
 661     size_t __result_len;
 662     if (__start >= __adj_endp1) return 0;
 663     __result_len = __adj_endp1 - __start;
 664     if (__result_len > __lazy_threshold) goto lazy;
 665     const _CharT* __section = __l->_M_data + __start;
 666     // We should sometimes create substring node instead.
 667     __result = _S_RopeLeaf_from_unowned_char_ptr(__section, __result_len,
 668                                                  __base->get_allocator());
 669     return __result;
 670   }
 671   case _RopeRep::_S_substringfn:
 672   // Avoid introducing multiple layers of substring nodes.
 673   {
 674     _RopeSubstring* __old = __STATIC_CAST(_RopeSubstring*, __base);
 675     size_t __result_len;
 676     if (__start >= __adj_endp1) return 0;
 677     __result_len = __adj_endp1 - __start;
 678     if (__result_len > __lazy_threshold) {
 679       _RopeSubstring* __result = _S_new_RopeSubstring(__old->_M_base,
 680                                                       __start + __old->_M_start,
 681                                                       __adj_endp1 - __start,
 682                                                       __base->get_allocator());
 683       return __result;
 684     } // *** else fall through: ***
 685   }
 686   case _RopeRep::_S_function:
 687   {
 688     _RopeFunction* __f = __STATIC_CAST(_RopeFunction*, __base);
 689     if (__start >= __adj_endp1) return 0;
 690     size_t __result_len = __adj_endp1 - __start;
 691
 692     if (__result_len > __lazy_threshold) goto lazy;
 693     _CharT* __section = __base->_M_size.allocate(_S_rounded_up_size(__result_len));
 694     _STLP_TRY {
 695       (*(__f->_M_fn))(__start, __result_len, __section);
 696     }
 697     _STLP_UNWIND(_RopeRep::_S_free_string(__section,
 698                                           __result_len, __base->get_allocator()))
 699     _S_construct_null(__section + __result_len);
 700     return _S_new_RopeLeaf(__section, __result_len,
 701                            __base->get_allocator());
 702   }
 703   }
 704   /*NOTREACHED*/
 705   _STLP_ASSERT(false)
 706   lazy:
 707   {
 708     // Create substring node.
 709     return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start,
 710                                 __base->get_allocator());
 711   }
 712 }
 713
 714 template<class _CharT>
 715 class _Rope_flatten_char_consumer : public _Rope_char_consumer<_CharT> {
 716 private:
 717   _CharT* _M_buf_ptr;
 718 public:
 719   _Rope_flatten_char_consumer(_CharT* __buffer) {
 720     _M_buf_ptr = __buffer;
 721   }
 722   ~_Rope_flatten_char_consumer() {}
 723   bool operator() (const _CharT* __leaf, size_t __n) {
 724     _STLP_PRIV __ucopy_n(__leaf, __n, _M_buf_ptr);
 725     _M_buf_ptr += __n;
 726     return true;
 727   }
 728 };
 729
 730 template<class _CharT>
 731 class _Rope_find_char_char_consumer : public _Rope_char_consumer<_CharT> {
 732 private:
 733   _CharT _M_pattern;
 734 public:
 735   size_t _M_count;  // Number of nonmatching characters
 736   _Rope_find_char_char_consumer(_CharT __p)
 737     : _M_pattern(__p), _M_count(0) {}
 738   ~_Rope_find_char_char_consumer() {}
 739   bool operator() (const _CharT* __leaf, size_t __n) {
 740     size_t __i;
 741     for (__i = 0; __i < __n; ++__i) {
 742       if (__leaf[__i] == _M_pattern) {
 743         _M_count += __i; return false;
 744       }
 745     }
 746     _M_count += __n; return true;
 747   }
 748 };
 749
 750 #if !defined (_STLP_USE_NO_IOSTREAMS)
 751 template<class _CharT, class _Traits>
 752 // Here _CharT is both the stream and rope character type.
 753 class _Rope_insert_char_consumer : public _Rope_char_consumer<_CharT> {
 754 private:
 755   typedef basic_ostream<_CharT,_Traits> _Insert_ostream;
 756   typedef _Rope_insert_char_consumer<_CharT,_Traits> _Self;
 757   _Insert_ostream& _M_o;
 758
 759   //explicitely defined as private to avoid warnings:
 760   _Self& operator = (_Self const&);
 761 public:
 762   _Rope_insert_char_consumer(_Insert_ostream& __writer)
 763     : _M_o(__writer) {}
 764 #  if defined(__MRC__) || (defined(__SC__) && !defined(__DMC__))  //*TY 05/23/2000 - added support for mpw compiler's trigger function approach to generate vtable
 765   ~_Rope_insert_char_consumer();    //*TY 05/23/2000 -
 766 #  else    //*TY 05/23/2000 -
 767   ~_Rope_insert_char_consumer() {}
 768 #  endif    //*TY 05/23/2000 -
 769   // Caller is presumed to own the ostream
 770   bool operator() (const _CharT* __leaf, size_t __n);
 771   // Returns true to continue traversal.
 772 };
 773
 774 #  if defined (__MRC__) || (defined (__SC__) && !defined (__DMC__))    //*TY 05/23/2000 - added support for mpw compiler's trigger function approach to generate vtable
 775 template<class _CharT, class _Traits>
 776 _Rope_insert_char_consumer<_CharT, _Traits>::  ~_Rope_insert_char_consumer() {}
 777 #  endif    //*TY 05/23/2000 -
 778
 779 template<class _CharT, class _Traits>
 780 bool _Rope_insert_char_consumer<_CharT, _Traits>::operator()
 781   (const _CharT* __leaf, size_t __n) {
 782   size_t __i;
 783   //  We assume that formatting is set up correctly for each element.
 784   for (__i = 0; __i < __n; ++__i) _M_o.put(__leaf[__i]);
 785   return true;
 786 }
 787 #endif /* !_STLP_USE_NO_IOSTREAMS */
 788
 789 template <class _CharT, class _Alloc, class _CharConsumer>
 790 bool _S_apply_to_pieces(_CharConsumer& __c,
 791                         _Rope_RopeRep<_CharT, _Alloc> * __r,
 792                         size_t __begin, size_t __end) {
 793   typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
 794   typedef _Rope_RopeConcatenation<_CharT,_Alloc> _RopeConcatenation;
 795   typedef _Rope_RopeLeaf<_CharT,_Alloc> _RopeLeaf;
 796   typedef _Rope_RopeFunction<_CharT,_Alloc> _RopeFunction;
 797
 798   if (0 == __r) return true;
 799   switch(__r->_M_tag) {
 800   case _RopeRep::_S_concat:
 801   {
 802     _RopeConcatenation* __conc = __STATIC_CAST(_RopeConcatenation*, __r);
 803     _RopeRep* __left =  __conc->_M_left;
 804     size_t __left_len = __left->_M_size._M_data;
 805     if (__begin < __left_len) {
 806       size_t __left_end = (min) (__left_len, __end);
 807       if (!_S_apply_to_pieces(__c, __left, __begin, __left_end))
 808         return false;
 809     }
 810     if (__end > __left_len) {
 811       _RopeRep* __right =  __conc->_M_right;
 812       size_t __right_start = (max)(__left_len, __begin);
 813       if (!_S_apply_to_pieces(__c, __right,
 814                               __right_start - __left_len,
 815                               __end - __left_len)) {
 816         return false;
 817       }
 818     }
 819   }
 820   return true;
 821   case _RopeRep::_S_leaf:
 822   {
 823     _RopeLeaf* __l = __STATIC_CAST(_RopeLeaf*, __r);
 824     return __c(__l->_M_data + __begin, __end - __begin);
 825   }
 826   case _RopeRep::_S_function:
 827   case _RopeRep::_S_substringfn:
 828   {
 829     _RopeFunction* __f = __STATIC_CAST(_RopeFunction*, __r);
 830     size_t __len = __end - __begin;
 831     bool __result;
 832     _CharT* __buffer = __r->get_allocator().allocate(__len);
 833     _STLP_TRY {
 834       (*(__f->_M_fn))(__begin, __len, __buffer);
 835       __result = __c(__buffer, __len);
 836       __r->get_allocator().deallocate(__buffer, __len);
 837     }
 838     _STLP_UNWIND((__r->get_allocator().deallocate(__buffer, __len)))
 839     return __result;
 840   }
 841   default:
 842     _STLP_ASSERT(false)
 843     /*NOTREACHED*/
 844     return false;
 845   }
 846 }
 847
 848 #if !defined (_STLP_USE_NO_IOSTREAMS)
 849 template<class _CharT, class _Traits>
 850 inline void _Rope_fill(basic_ostream<_CharT, _Traits>& __o, streamsize __n) {
 851   char __f = __o.fill();
 852   for (streamsize __i = 0; __i < __n; ++__i) __o.put(__f);
 853 }
 854
 855 template<class _CharT, class _Traits, class _Alloc>
 856 basic_ostream<_CharT, _Traits>& _S_io_get(basic_ostream<_CharT, _Traits>& __o,
 857                                           const rope<_CharT, _Alloc>& __r, const __true_type& /*_IsBasicCharType*/) {
 858   streamsize __w = __o.width();
 859   const bool __left = (__o.flags() & ios::left) != 0;
 860   size_t __rope_len = __r.size();
 861   _Rope_insert_char_consumer<_CharT, _Traits> __c(__o);
 862
 863   const bool __need_pad = (((sizeof(streamsize) > sizeof(size_t)) && (__STATIC_CAST(streamsize, __rope_len) < __w)) ||
 864                            ((sizeof(streamsize) <= sizeof(size_t)) && (__rope_len < __STATIC_CAST(size_t, __w))));
 865   streamsize __pad_len = __need_pad ? __w - __rope_len : 0;
 866
 867   if (!__left && __pad_len > 0) {
 868     _Rope_fill(__o, __pad_len);
 869   }
 870   __r.apply_to_pieces(0, __rope_len, __c);
 871   if (__left && __pad_len > 0) {
 872     _Rope_fill(__o, __pad_len);
 873   }
 874   return __o;
 875 }
 876
 877 template<class _CharT, class _Traits, class _Alloc>
 878 basic_ostream<_CharT, _Traits>& _S_io_get(basic_ostream<_CharT, _Traits>& __o,
 879                                          const rope<_CharT, _Alloc>& __r, const __false_type& /*_IsBasicCharType*/) {
 880   streamsize __w = __o.width();
 881   size_t __rope_len = __r.size();
 882   _Rope_insert_char_consumer<_CharT, _Traits> __c(__o);
 883
 884   __o.width(__w /__rope_len);
 885   _STLP_TRY {
 886     __r.apply_to_pieces(0, __rope_len, __c);
 887     __o.width(__w);
 888   }
 889   _STLP_UNWIND(__o.width(__w))
 890   return __o;
 891 }
 892
 893 template<class _CharT, class _Traits, class _Alloc>
 894 basic_ostream<_CharT, _Traits>& operator<<(basic_ostream<_CharT, _Traits>& __o,
 895                                            const rope<_CharT, _Alloc>& __r) {
 896   typedef typename _IsIntegral<_CharT>::_Ret _Char_Is_Integral;
 897   return _S_io_get(__o, __r, _Char_Is_Integral());
 898 }
 899 #endif /* NO_IOSTREAMS */
 900
 901 template <class _CharT, class _Alloc>
 902 _CharT* rope<_CharT,_Alloc>::_S_flatten(_RopeRep* __r,
 903                                         size_t __start, size_t __len,
 904                                         _CharT* __buffer) {
 905   _Rope_flatten_char_consumer<_CharT> __c(__buffer);
 906   _S_apply_to_pieces(__c, __r, __start, __start + __len);
 907   return(__buffer + __len);
 908 }
 909
 910 template <class _CharT, class _Alloc>
 911 size_t rope<_CharT,_Alloc>::find(_CharT __pattern, size_t __start) const {
 912   _Rope_find_char_char_consumer<_CharT> __c(__pattern);
 913   _S_apply_to_pieces(__c, _M_tree_ptr._M_data, __start, size());
 914   size_type __result_pos = __start + __c._M_count;
 915 #ifndef _STLP_OLD_ROPE_SEMANTICS
 916   if (__result_pos == size()) __result_pos = npos;
 917 #endif
 918   return __result_pos;
 919 }
 920
 921 template <class _CharT, class _Alloc>
 922 _CharT*
 923 rope<_CharT,_Alloc>::_S_flatten(_Rope_RopeRep<_CharT, _Alloc>* __r, _CharT* __buffer) {
 924   if (0 == __r) return __buffer;
 925   switch(__r->_M_tag) {
 926   case _RopeRep::_S_concat:
 927   {
 928     _RopeConcatenation* __c = __STATIC_CAST(_RopeConcatenation*, __r);
 929     _RopeRep* __left = __c->_M_left;
 930     _RopeRep* __right = __c->_M_right;
 931     _CharT* __rest = _S_flatten(__left, __buffer);
 932     return _S_flatten(__right, __rest);
 933   }
 934   case _RopeRep::_S_leaf:
 935   {
 936     _RopeLeaf* __l = __STATIC_CAST(_RopeLeaf*, __r);
 937     return _STLP_PRIV __ucopy_n(__l->_M_data, __l->_M_size._M_data, __buffer).second;
 938   }
 939   case _RopeRep::_S_function:
 940   case _RopeRep::_S_substringfn:
 941   // We dont yet do anything with substring nodes.
 942   // This needs to be fixed before ropefiles will work well.
 943   {
 944     _RopeFunction* __f = __STATIC_CAST(_RopeFunction*, __r);
 945     (*(__f->_M_fn))(0, __f->_M_size._M_data, __buffer);
 946     return __buffer + __f->_M_size._M_data;
 947   }
 948   default:
 949     _STLP_ASSERT(false)
 950     /*NOTREACHED*/
 951     return 0;
 952   }
 953 }
 954
 955 #ifdef _STLP_DEBUG
 956 // This needs work for _CharT != char
 957 template <class _CharT, class _Alloc>
 958 void rope<_CharT,_Alloc>::_S_dump(_RopeRep* __r, int __indent) {
 959   for (int __i = 0; __i < __indent; ++__i) putchar(' ');
 960   if (0 == __r) {
 961     printf("NULL\n"); return;
 962   }
 963   if (_RopeRep::_S_concat == __r->_M_tag) {
 964     _RopeConcatenation* __c = __STATIC_CAST(_RopeConcatenation*, __r);
 965     _RopeRep* __left = __c->_M_left;
 966     _RopeRep* __right = __c->_M_right;
 967     printf("Concatenation %p (rc = %ld, depth = %d, len = %ld, %s balanced)\n",
 968       __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size._M_data,
 969       __r->_M_is_balanced? "" : "not");
 970     _S_dump(__left, __indent + 2);
 971     _S_dump(__right, __indent + 2);
 972     return;
 973   }
 974   else {
 975     const char* __kind;
 976
 977     switch (__r->_M_tag) {
 978       case _RopeRep::_S_leaf:
 979         __kind = "Leaf";
 980         break;
 981       case _RopeRep::_S_function:
 982         __kind = "Function";
 983         break;
 984       case _RopeRep::_S_substringfn:
 985         __kind = "Function representing substring";
 986         break;
 987       default:
 988         __kind = "(corrupted kind field!)";
 989     }
 990     printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
 991      __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size._M_data);
 992     if (sizeof(_CharT) == 1) {
 993       const int __max_len = 40;
 994       _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len));
 995       _CharT __buffer[__max_len + 1];
 996       bool __too_big = __r->_M_size._M_data > __prefix->_M_size._M_data;
 997
 998       _S_flatten(__prefix, __buffer);
 999       __buffer[__prefix->_M_size._M_data] = _STLP_DEFAULT_CONSTRUCTED(_CharT);
1000       printf("%s%s\n", (char*)__buffer, __too_big? "...\n" : "\n");
1001     } else {
1002       printf("\n");
1003     }
1004   }
1005 }
1006 #endif /* _STLP_DEBUG */
1007
1008 # define __ROPE_TABLE_BODY  = { \
1009 /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21,         \
1010 /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377,         \
1011 /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181,             \
1012 /* 18 */6765ul, /* 19 */10946ul, /* 20 */17711ul, /* 21 */28657ul, /* 22 */46368ul,   \
1013 /* 23 */75025ul, /* 24 */121393ul, /* 25 */196418ul, /* 26 */317811ul,                \
1014 /* 27 */514229ul, /* 28 */832040ul, /* 29 */1346269ul, /* 30 */2178309ul,             \
1015 /* 31 */3524578ul, /* 32 */5702887ul, /* 33 */9227465ul, /* 34 */14930352ul,          \
1016 /* 35 */24157817ul, /* 36 */39088169ul, /* 37 */63245986ul, /* 38 */102334155ul,      \
1017 /* 39 */165580141ul, /* 40 */267914296ul, /* 41 */433494437ul,                        \
1018 /* 42 */701408733ul, /* 43 */1134903170ul, /* 44 */1836311903ul,                      \
1019 /* 45 */2971215073ul }
1020
1021 # if ( _STLP_STATIC_TEMPLATE_DATA > 0 )
1022 template <class _CharT, class _Alloc>
1023 const unsigned long
1024 rope<_CharT,_Alloc>::_S_min_len[__ROPE_DEPTH_SIZE] __ROPE_TABLE_BODY;
1025 # else
1026 __DECLARE_INSTANCE(const unsigned long,
1027                    crope::_S_min_len[__ROPE_DEPTH_SIZE],
1028                    __ROPE_TABLE_BODY);
1029 #  ifndef _STLP_NO_WCHAR_T
1030 __DECLARE_INSTANCE(const unsigned long,
1031                    wrope::_S_min_len[__ROPE_DEPTH_SIZE],
1032                    __ROPE_TABLE_BODY);
1033 #  endif
1034 # endif
1035 # undef __ROPE_DEPTH_SIZE
1036 # undef __ROPE_MAX_DEPTH
1037 # undef __ROPE_TABLE_BODY
1038
1039 // These are Fibonacci numbers < 2**32.
1040
1041 template <class _CharT, class _Alloc>
1042 __RopeRep__* rope<_CharT,_Alloc>::_S_balance(_RopeRep* __r) {
1043   _RopeRep* __forest[_RopeRep::_S_max_rope_depth + 1] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1044                                                          0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1045                                                          0,0,0,0,0,0};
1046   _RopeRep* __result = 0;
1047   int __i;
1048   // Invariant:
1049   // The concatenation of forest in descending order is equal to __r.
1050   // __forest[__i]._M_size._M_data >= _S_min_len[__i]
1051   // __forest[__i]._M_depth = __i
1052   // References from forest are included in refcount.
1053
1054   _STLP_TRY {
1055     _S_add_to_forest(__r, __forest);
1056     for (__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i)
1057       if (0 != __forest[__i]) {
1058         _Self_destruct_ptr __old(__result);
1059         __result = _S_concat_rep(__forest[__i], __result);
1060         __forest[__i]->_M_unref_nonnil();
1061 # ifdef _STLP_USE_EXCEPTIONS
1062         __forest[__i] = 0;
1063 # endif
1064       }
1065     }
1066     _STLP_UNWIND(for(__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i)
1067     _S_unref(__forest[__i]))
1068     if (__result->_M_depth > _RopeRep::_S_max_rope_depth) {
1069       __stl_throw_range_error("rope too long");
1070     }
1071     return(__result);
1072 }
1073
1074
1075 template <class _CharT, class _Alloc>
1076 void
1077 rope<_CharT,_Alloc>::_S_add_to_forest(_RopeRep* __r, _RopeRep** __forest)
1078 {
1079     if (__r -> _M_is_balanced) {
1080       _S_add_leaf_to_forest(__r, __forest);
1081       return;
1082     }
1083     _STLP_ASSERT(__r->_M_tag == _RopeRep::_S_concat)
1084     {
1085       _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1086
1087       _S_add_to_forest(__c->_M_left, __forest);
1088       _S_add_to_forest(__c->_M_right, __forest);
1089     }
1090 }
1091
1092
1093 template <class _CharT, class _Alloc>
1094 void
1095 rope<_CharT,_Alloc>::_S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest)
1096 {
1097     _RopeRep* __insertee;       // included in refcount
1098     _RopeRep* __too_tiny = 0;      // included in refcount
1099     int __i;          // forest[0..__i-1] is empty
1100     size_t __s = __r->_M_size._M_data;
1101
1102     for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i) {
1103   if (0 != __forest[__i]) {
1104         _Self_destruct_ptr __old(__too_tiny);
1105       __too_tiny = _S_concat_and_set_balanced(__forest[__i], __too_tiny);
1106       __forest[__i]->_M_unref_nonnil();
1107       __forest[__i] = 0;
1108   }
1109     }
1110     {
1111     _Self_destruct_ptr __old(__too_tiny);
1112   __insertee = _S_concat_and_set_balanced(__too_tiny, __r);
1113     }
1114     // Too_tiny dead, and no longer included in refcount.
1115     // Insertee is live and included.
1116     _STLP_ASSERT(_S_is_almost_balanced(__insertee))
1117     _STLP_ASSERT(__insertee->_M_depth <= __r->_M_depth + 1)
1118     for (;; ++__i) {
1119       if (0 != __forest[__i]) {
1120         _Self_destruct_ptr __old(__insertee);
1121       __insertee = _S_concat_and_set_balanced(__forest[__i], __insertee);
1122       __forest[__i]->_M_unref_nonnil();
1123       __forest[__i] = 0;
1124       _STLP_ASSERT(_S_is_almost_balanced(__insertee))
1125   }
1126   _STLP_ASSERT(_S_min_len[__i] <= __insertee->_M_size._M_data)
1127   _STLP_ASSERT(__forest[__i] == 0)
1128   if (__i == _RopeRep::_S_max_rope_depth ||
1129         __insertee->_M_size._M_data < _S_min_len[__i+1]) {
1130       __forest[__i] = __insertee;
1131       // refcount is OK since __insertee is now dead.
1132       return;
1133   }
1134     }
1135 }
1136
1137 template <class _CharT, class _Alloc>
1138 _CharT
1139 rope<_CharT,_Alloc>::_S_fetch(_RopeRep* __r, size_type __i)
1140 {
1141     _CharT* __cstr = __r->_M_c_string;
1142
1143     _STLP_ASSERT(__i < __r->_M_size._M_data)
1144     if (0 != __cstr) return __cstr[__i];
1145     for(;;) {
1146       switch(__r->_M_tag) {
1147   case _RopeRep::_S_concat:
1148       {
1149     _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1150     _RopeRep* __left = __c->_M_left;
1151     size_t __left_len = __left->_M_size._M_data;
1152
1153     if (__i >= __left_len) {
1154         __i -= __left_len;
1155         __r = __c->_M_right;
1156     } else {
1157         __r = __left;
1158     }
1159       }
1160       break;
1161   case _RopeRep::_S_leaf:
1162       {
1163     _RopeLeaf* __l = (_RopeLeaf*)__r;
1164     return __l->_M_data[__i];
1165       }
1166   case _RopeRep::_S_function:
1167   case _RopeRep::_S_substringfn:
1168       {
1169     _RopeFunction* __f = (_RopeFunction*)__r;
1170     _CharT __result;
1171
1172     (*(__f->_M_fn))(__i, 1, &__result);
1173     return __result;
1174       }
1175       }
1176     }
1177 #if defined(_STLP_NEED_UNREACHABLE_RETURN)
1178     return 0;
1179 #endif
1180 }
1181
1182 // Return a uniquely referenced character slot for the given
1183 // position, or 0 if that's not possible.
1184 template <class _CharT, class _Alloc>
1185 _CharT*
1186 rope<_CharT,_Alloc>::_S_fetch_ptr(_RopeRep* __r, size_type __i)
1187 {
1188     _RopeRep* __clrstack[_RopeRep::_S_max_rope_depth];
1189     size_t __csptr = 0;
1190
1191     for(;;) {
1192       // if (__r->_M_ref_count > 1) return 0;
1193       if ( __r->_M_incr() > 2 ) {
1194         __r->_M_decr();
1195         return 0;
1196       }
1197       switch(__r->_M_tag) {
1198   case _RopeRep::_S_concat:
1199       {
1200     _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1201     _RopeRep* __left = __c->_M_left;
1202     size_t __left_len = __left->_M_size._M_data;
1203
1204     if (__c->_M_c_string != 0) __clrstack[__csptr++] = __c;
1205     if (__i >= __left_len) {
1206         __i -= __left_len;
1207         __r = __c->_M_right;
1208     } else {
1209         __r = __left;
1210     }
1211       }
1212       break;
1213   case _RopeRep::_S_leaf:
1214       {
1215     _RopeLeaf* __l = (_RopeLeaf*)__r;
1216     if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0)
1217         __clrstack[__csptr++] = __l;
1218     while (__csptr > 0) {
1219         -- __csptr;
1220         _RopeRep* __d = __clrstack[__csptr];
1221         __d->_M_free_c_string();
1222         __d->_M_c_string = 0;
1223     }
1224     return __l->_M_data + __i;
1225       }
1226   case _RopeRep::_S_function:
1227   case _RopeRep::_S_substringfn:
1228       return 0;
1229       }
1230     }
1231 #if defined(_STLP_NEED_UNREACHABLE_RETURN)
1232     return 0;
1233 #endif
1234
1235 }
1236
1237 // The following could be implemented trivially using
1238 // lexicographical_compare_3way.
1239 // We do a little more work to avoid dealing with rope iterators for
1240 // flat strings.
1241 template <class _CharT, class _Alloc>
1242 int
1243 rope<_CharT,_Alloc>::_S_compare (const _RopeRep* __left,
1244                                  const _RopeRep* __right) {
1245   size_t __left_len;
1246   size_t __right_len;
1247
1248   if (0 == __right) return 0 != __left;
1249   if (0 == __left) return -1;
1250   __left_len = __left->_M_size._M_data;
1251   __right_len = __right->_M_size._M_data;
1252   if (_RopeRep::_S_leaf == __left->_M_tag) {
1253     const _RopeLeaf* __l = __STATIC_CAST(const _RopeLeaf*, __left);
1254     if (_RopeRep::_S_leaf == __right->_M_tag) {
1255       const _RopeLeaf* __r = __STATIC_CAST(const _RopeLeaf*, __right);
1256       return _STLP_PRIV __lexicographical_compare_3way(__l->_M_data, __l->_M_data + __left_len,
1257                                                        __r->_M_data, __r->_M_data + __right_len);
1258     }
1259     else {
1260       const_iterator __rstart(__right, 0);
1261       const_iterator __rend(__right, __right_len);
1262       return _STLP_PRIV __lexicographical_compare_3way(__l->_M_data, __l->_M_data + __left_len,
1263                                                        __rstart, __rend);
1264     }
1265   }
1266   else {
1267     const_iterator __lstart(__left, 0);
1268     const_iterator __lend(__left, __left_len);
1269     if (_RopeRep::_S_leaf == __right->_M_tag) {
1270       const _RopeLeaf* __r = __STATIC_CAST(const _RopeLeaf*, __right);
1271       return _STLP_PRIV __lexicographical_compare_3way(__lstart, __lend,
1272                                                        __r->_M_data, __r->_M_data + __right_len);
1273     }
1274     else {
1275       const_iterator __rstart(__right, 0);
1276       const_iterator __rend(__right, __right_len);
1277       return _STLP_PRIV __lexicographical_compare_3way(__lstart, __lend, __rstart, __rend);
1278     }
1279   }
1280 }
1281
1282 // Assignment to reference proxies.
1283 template <class _CharT, class _Alloc>
1284 _Rope_char_ref_proxy<_CharT, _Alloc>&
1285 _Rope_char_ref_proxy<_CharT, _Alloc>::operator= (_CharT __c) {
1286     _RopeRep* __old = _M_root->_M_tree_ptr._M_data;
1287   // First check for the case in which everything is uniquely
1288   // referenced.  In that case we can do this destructively.
1289   _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos);
1290   if (0 != __ptr) {
1291       *__ptr = __c;
1292       return *this;
1293   }
1294     _Self_destruct_ptr __left(
1295       _My_rope::_S_substring(__old, 0, _M_pos));
1296     _Self_destruct_ptr __right(
1297       _My_rope::_S_substring(__old, _M_pos+1, __old->_M_size._M_data));
1298     _Self_destruct_ptr __result_left(
1299       _My_rope::_S_destr_concat_char_iter(__left, &__c, 1));
1300
1301     // _STLP_ASSERT(__left == __result_left || 1 == __result_left->_M_ref_count)
1302     _RopeRep* __result =
1303       _My_rope::_S_concat_rep(__result_left, __right);
1304     // _STLP_ASSERT(1 <= __result->_M_ref_count)
1305     _RopeRep::_S_unref(__old);
1306     _M_root->_M_tree_ptr._M_data = __result;
1307     return *this;
1308 }
1309
1310 template <class _CharT, class _Alloc>
1311 _Rope_char_ptr_proxy<_CharT, _Alloc>
1312 _Rope_char_ref_proxy<_CharT, _Alloc>::operator& () const {
1313     return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this);
1314 }
1315
1316 # if ( _STLP_STATIC_TEMPLATE_DATA > 0 )
1317 template<class _CharT, class _Alloc>
1318 _CharT rope<_CharT,_Alloc>::_S_empty_c_str[1] = { _CharT() };
1319 # else
1320 __DECLARE_INSTANCE(char, crope::_S_empty_c_str[1], ={0});
1321 # ifdef _STLP_HAS_WCHAR_T
1322 __DECLARE_INSTANCE(wchar_t, wrope::_S_empty_c_str[1], ={0});
1323 # endif /* _STLP_HAS_WCHAR_T */
1324 # endif /* _STLP_STATIC_TEMPLATE_DATA */
1325 // # endif
1326
1327 #if !defined (_STLP_STATIC_CONST_INIT_BUG)
1328 #  if !defined (__GNUC__) || (__GNUC__ != 2) || (__GNUC_MINOR__ != 96)
1329 template <class _CharT, class _Alloc>
1330 const size_t rope<_CharT, _Alloc>::npos;
1331 #  endif
1332 #endif
1333
1334 template<class _CharT, class _Alloc>
1335 const _CharT* rope<_CharT,_Alloc>::c_str() const {
1336   if (0 == _M_tree_ptr._M_data) {
1337     // Possibly redundant, but probably fast.
1338     _S_empty_c_str[0] = _STLP_DEFAULT_CONSTRUCTED(_CharT);
1339     return _S_empty_c_str;
1340   }
1341   _CharT* __old_c_string = _M_tree_ptr._M_data->_M_c_string;
1342   if (0 != __old_c_string) return __old_c_string;
1343   size_t __s = size();
1344   _CharT* __result = _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_tree_ptr, _CharT).allocate(__s + 1);
1345   _S_flatten(_M_tree_ptr._M_data, __result);
1346   _S_construct_null(__result + __s);
1347   __old_c_string = __STATIC_CAST(_CharT*, _Atomic_swap_ptr(__REINTERPRET_CAST(void* _STLP_VOLATILE*, &(_M_tree_ptr._M_data->_M_c_string)),
1348                                                            __result));
1349   if (0 != __old_c_string) {
1350     // It must have been added in the interim.  Hence it had to have been
1351     // separately allocated.  Deallocate the old copy, since we just
1352     // replaced it.
1353     _STLP_STD::_Destroy_Range(__old_c_string, __old_c_string + __s + 1);
1354     _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_tree_ptr, _CharT).deallocate(__old_c_string, __s + 1);
1355   }
1356   return __result;
1357 }
1358
1359 template<class _CharT, class _Alloc>
1360 const _CharT* rope<_CharT,_Alloc>::replace_with_c_str() {
1361   if (0 == _M_tree_ptr._M_data) {
1362     _S_empty_c_str[0] = _STLP_DEFAULT_CONSTRUCTED(_CharT);
1363     return _S_empty_c_str;
1364   }
1365   _CharT* __old_c_string = _M_tree_ptr._M_data->_M_c_string;
1366   if (_RopeRep::_S_leaf == _M_tree_ptr._M_data->_M_tag && 0 != __old_c_string) {
1367     return __old_c_string;
1368   }
1369   size_t __s = size();
1370   _CharT* __result = _M_tree_ptr.allocate(_S_rounded_up_size(__s));
1371   _S_flatten(_M_tree_ptr._M_data, __result);
1372   _S_construct_null(__result + __s);
1373   _M_tree_ptr._M_data->_M_unref_nonnil();
1374   _M_tree_ptr._M_data = _S_new_RopeLeaf(__result, __s, _M_tree_ptr);
1375   return __result;
1376 }
1377
1378 // Algorithm specializations.  More should be added.
1379
1380 #if (!defined (_STLP_MSVC) || (_STLP_MSVC >= 1310)) && \
1381     (!defined (__DMC__) || defined (__PUT_STATIC_DATA_MEMBERS_HERE))
1382 // I couldn't get this to work with VC++
1383 template<class _CharT,class _Alloc>
1384 void _Rope_rotate(_Rope_iterator<_CharT,_Alloc> __first,
1385                   _Rope_iterator<_CharT,_Alloc> __middle,
1386                   _Rope_iterator<_CharT,_Alloc> __last) {
1387   _STLP_ASSERT(__first.container() == __middle.container() &&
1388                __middle.container() == __last.container())
1389   rope<_CharT,_Alloc>& __r(__first.container());
1390   rope<_CharT,_Alloc> __prefix = __r.substr(0, __first.index());
1391   rope<_CharT,_Alloc> __suffix =
1392     __r.substr(__last.index(), __r.size() - __last.index());
1393   rope<_CharT,_Alloc> __part1 =
1394     __r.substr(__middle.index(), __last.index() - __middle.index());
1395   rope<_CharT,_Alloc> __part2 =
1396     __r.substr(__first.index(), __middle.index() - __first.index());
1397   __r = __prefix;
1398   __r += __part1;
1399   __r += __part2;
1400   __r += __suffix;
1401 }
1402
1403
1404 # if 0
1405 // Probably not useful for several reasons:
1406 // - for SGIs 7.1 compiler and probably some others,
1407 //   this forces lots of rope<wchar_t, ...> instantiations, creating a
1408 //   code bloat and compile time problem.  (Fixed in 7.2.)
1409 // - wchar_t is 4 bytes wide on most UNIX platforms, making it unattractive
1410 //   for unicode strings.  Unsigned short may be a better character
1411 //   type.
1412 inline void rotate(
1413     _Rope_iterator<wchar_t,_STLP_DEFAULT_ALLOCATOR(char) > __first,
1414                 _Rope_iterator<wchar_t,_STLP_DEFAULT_ALLOCATOR(char) > __middle,
1415                 _Rope_iterator<wchar_t,_STLP_DEFAULT_ALLOCATOR(char) > __last) {
1416     _Rope_rotate(__first, __middle, __last);
1417 }
1418 # endif
1419 #endif /* _STLP_MSVC */
1420
1421 #   undef __RopeLeaf__
1422 #   undef __RopeRep__
1423 #   undef __RopeLeaf
1424 #   undef __RopeRep
1425 #   undef size_type
1426
1427 _STLP_END_NAMESPACE
1428
1429 # endif /* ROPEIMPL_H */
1430
1431 // Local Variables:
1432 // mode:C++
1433 // End: