_rope.c 48 KB

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