_deque.c 32 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823
  1. /*
  2. *
  3. *
  4. * Copyright (c) 1994
  5. * Hewlett-Packard Company
  6. *
  7. * Copyright (c) 1996,1997
  8. * Silicon Graphics Computer Systems, Inc.
  9. *
  10. * Copyright (c) 1997
  11. * Moscow Center for SPARC Technology
  12. *
  13. * Copyright (c) 1999
  14. * Boris Fomitchev
  15. *
  16. * This material is provided "as is", with absolutely no warranty expressed
  17. * or implied. Any use is at your own risk.
  18. *
  19. * Permission to use or copy this software for any purpose is hereby granted
  20. * without fee, provided the above notices are retained on all copies.
  21. * Permission to modify the code and to distribute modified code is granted,
  22. * provided the above notices are retained, and a notice that the code was
  23. * modified is included with the above copyright notice.
  24. *
  25. */
  26. #ifndef _STLP_DEQUE_C
  27. #define _STLP_DEQUE_C
  28. #ifndef _STLP_INTERNAL_DEQUE_H
  29. # include <stl/_deque.h>
  30. #endif
  31. _STLP_BEGIN_NAMESPACE
  32. _STLP_MOVE_TO_PRIV_NAMESPACE
  33. // Non-inline member functions from _Deque_base.
  34. template <class _Tp, class _Alloc >
  35. _Deque_base<_Tp,_Alloc >::~_Deque_base() {
  36. if (_M_map._M_data) {
  37. _M_destroy_nodes(_M_start._M_node, this->_M_finish._M_node + 1);
  38. _M_map.deallocate(_M_map._M_data, _M_map_size._M_data);
  39. }
  40. }
  41. template <class _Tp, class _Alloc >
  42. void _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements) {
  43. size_t __num_nodes = __num_elements / this->buffer_size() + 1 ;
  44. _M_map_size._M_data = (max)((size_t) _S_initial_map_size, __num_nodes + 2);
  45. _M_map._M_data = _M_map.allocate(_M_map_size._M_data);
  46. _Tp** __nstart = _M_map._M_data + (_M_map_size._M_data - __num_nodes) / 2;
  47. _Tp** __nfinish = __nstart + __num_nodes;
  48. _STLP_TRY {
  49. _M_create_nodes(__nstart, __nfinish);
  50. }
  51. _STLP_UNWIND((_M_map.deallocate(_M_map._M_data, _M_map_size._M_data),
  52. _M_map._M_data = 0, _M_map_size._M_data = 0))
  53. _M_start._M_set_node(__nstart);
  54. this->_M_finish._M_set_node(__nfinish - 1);
  55. _M_start._M_cur = _M_start._M_first;
  56. this->_M_finish._M_cur = this->_M_finish._M_first + __num_elements % this->buffer_size();
  57. }
  58. template <class _Tp, class _Alloc >
  59. void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart,
  60. _Tp** __nfinish) {
  61. _Tp** __cur = __nstart;
  62. _STLP_TRY {
  63. for (; __cur < __nfinish; ++__cur)
  64. *__cur = _M_map_size.allocate(this->buffer_size());
  65. }
  66. _STLP_UNWIND(_M_destroy_nodes(__nstart, __cur))
  67. }
  68. template <class _Tp, class _Alloc >
  69. void _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart,
  70. _Tp** __nfinish) {
  71. for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
  72. _M_map_size.deallocate(*__n, this->buffer_size());
  73. }
  74. #if defined (_STLP_USE_PTR_SPECIALIZATIONS)
  75. # define deque _STLP_PTR_IMPL_NAME(deque)
  76. #elif defined (_STLP_DEBUG)
  77. # define deque _STLP_NON_DBG_NAME(deque)
  78. #else
  79. _STLP_MOVE_TO_STD_NAMESPACE
  80. #endif
  81. #if defined (_STLP_NESTED_TYPE_PARAM_BUG)
  82. // qualified references
  83. # define __iterator__ _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >
  84. # define const_iterator _Deque_iterator<_Tp, _Const_traits<_Tp> >
  85. # define iterator __iterator__
  86. # define size_type size_t
  87. # define value_type _Tp
  88. #else
  89. # define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE deque<_Tp, _Alloc>::iterator
  90. #endif
  91. template <class _Tp, class _Alloc >
  92. deque<_Tp, _Alloc >&
  93. deque<_Tp, _Alloc >::operator= (const deque<_Tp, _Alloc >& __x) {
  94. const size_type __len = size();
  95. if (&__x != this) {
  96. if (__len >= __x.size())
  97. erase(_STLP_STD::copy(__x.begin(), __x.end(), this->_M_start), this->_M_finish);
  98. else {
  99. const_iterator __mid = __x.begin() + difference_type(__len);
  100. _STLP_STD::copy(__x.begin(), __mid, this->_M_start);
  101. insert(this->_M_finish, __mid, __x.end());
  102. }
  103. }
  104. return *this;
  105. }
  106. template <class _Tp, class _Alloc >
  107. void deque<_Tp, _Alloc >::_M_fill_insert(iterator __pos,
  108. size_type __n, const value_type& __x) {
  109. #if !defined (_STLP_NO_MOVE_SEMANTIC)
  110. typedef typename __move_traits<_Tp>::implemented _Movable;
  111. #endif
  112. if (__pos._M_cur == this->_M_start._M_cur) {
  113. iterator __new_start = _M_reserve_elements_at_front(__n);
  114. _STLP_TRY {
  115. uninitialized_fill(__new_start, this->_M_start, __x);
  116. }
  117. _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
  118. this->_M_start = __new_start;
  119. }
  120. else if (__pos._M_cur == this->_M_finish._M_cur) {
  121. iterator __new_finish = _M_reserve_elements_at_back(__n);
  122. _STLP_TRY {
  123. uninitialized_fill(this->_M_finish, __new_finish, __x);
  124. }
  125. _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node+1, __new_finish._M_node+1))
  126. this->_M_finish = __new_finish;
  127. }
  128. else
  129. _M_fill_insert_aux(__pos, __n, __x, _Movable());
  130. }
  131. #if !defined (_STLP_MEMBER_TEMPLATES)
  132. template <class _Tp, class _Alloc >
  133. void deque<_Tp, _Alloc>::insert(iterator __pos,
  134. const value_type* __first, const value_type* __last) {
  135. #if !defined (_STLP_NO_MOVE_SEMANTIC)
  136. typedef typename __move_traits<_Tp>::implemented _Movable;
  137. #endif
  138. size_type __n = __last - __first;
  139. if (__pos._M_cur == this->_M_start._M_cur) {
  140. iterator __new_start = _M_reserve_elements_at_front(__n);
  141. _STLP_TRY {
  142. _STLP_PRIV __ucopy(__first, __last, __new_start);
  143. }
  144. _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
  145. this->_M_start = __new_start;
  146. }
  147. else if (__pos._M_cur == this->_M_finish._M_cur) {
  148. iterator __new_finish = _M_reserve_elements_at_back(__n);
  149. _STLP_TRY {
  150. _STLP_PRIV __ucopy(__first, __last, this->_M_finish);
  151. }
  152. _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1,
  153. __new_finish._M_node + 1))
  154. this->_M_finish = __new_finish;
  155. }
  156. else
  157. _M_insert_range_aux(__pos, __first, __last, __n, _Movable());
  158. }
  159. template <class _Tp, class _Alloc >
  160. void deque<_Tp,_Alloc>::insert(iterator __pos,
  161. const_iterator __first, const_iterator __last) {
  162. #if !defined (_STLP_NO_MOVE_SEMANTIC)
  163. typedef typename __move_traits<_Tp>::implemented _Movable;
  164. #endif
  165. size_type __n = __last - __first;
  166. if (__pos._M_cur == this->_M_start._M_cur) {
  167. iterator __new_start = _M_reserve_elements_at_front(__n);
  168. _STLP_TRY {
  169. _STLP_PRIV __ucopy(__first, __last, __new_start);
  170. }
  171. _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
  172. this->_M_start = __new_start;
  173. }
  174. else if (__pos._M_cur == this->_M_finish._M_cur) {
  175. iterator __new_finish = _M_reserve_elements_at_back(__n);
  176. _STLP_TRY {
  177. _STLP_PRIV __ucopy(__first, __last, this->_M_finish);
  178. }
  179. _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1,
  180. __new_finish._M_node + 1))
  181. this->_M_finish = __new_finish;
  182. }
  183. else
  184. _M_insert_range_aux(__pos, __first, __last, __n, _Movable());
  185. }
  186. #endif /* _STLP_MEMBER_TEMPLATES */
  187. template <class _Tp, class _Alloc >
  188. __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __pos,
  189. const __true_type& /*_Movable*/) {
  190. difference_type __index = __pos - this->_M_start;
  191. if (size_type(__index) < this->size() >> 1) {
  192. //We move the start of the deque one position to the right
  193. //starting from the rightmost element to move.
  194. iterator __src = __pos, __dst = __pos;
  195. _STLP_STD::_Destroy(&(*__dst));
  196. if (__src != this->_M_start) {
  197. for (--__src; __dst != this->_M_start; --__src, --__dst) {
  198. _STLP_STD::_Move_Construct(&(*__dst), *__src);
  199. _STLP_STD::_Destroy_Moved(&(*__src));
  200. }
  201. }
  202. _M_pop_front_aux();
  203. }
  204. else {
  205. iterator __src = __pos, __dst = __pos;
  206. _STLP_STD::_Destroy(&(*__dst));
  207. for (++__src; __src != this->_M_finish; ++__src, ++__dst) {
  208. _STLP_STD::_Move_Construct(&(*__dst), *__src);
  209. _STLP_STD::_Destroy_Moved(&(*__src));
  210. }
  211. //Duplication of the pop_back code without the destroy which has already been done:
  212. if (this->_M_finish._M_cur != this->_M_finish._M_first) {
  213. --this->_M_finish._M_cur;
  214. }
  215. else {
  216. _M_pop_back_aux();
  217. }
  218. }
  219. return this->_M_start + __index;
  220. }
  221. template <class _Tp, class _Alloc >
  222. __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __pos,
  223. const __false_type& /*_Movable*/) {
  224. iterator __next = __pos;
  225. ++__next;
  226. difference_type __index = __pos - this->_M_start;
  227. if (size_type(__index) < this->size() >> 1) {
  228. copy_backward(this->_M_start, __pos, __next);
  229. pop_front();
  230. }
  231. else {
  232. _STLP_STD::copy(__next, this->_M_finish, __pos);
  233. pop_back();
  234. }
  235. return this->_M_start + __index;
  236. }
  237. template <class _Tp, class _Alloc >
  238. __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __first, iterator __last,
  239. const __true_type& /*_Movable*/) {
  240. difference_type __n = __last - __first;
  241. difference_type __elems_before = __first - this->_M_start;
  242. if (__elems_before <= difference_type(this->size() - __n) / 2) {
  243. iterator __src = __first, __dst = __last;
  244. if (__src != this->_M_start) {
  245. for (--__src, --__dst; (__src >= this->_M_start) && (__dst >= __first); --__src, --__dst) {
  246. _STLP_STD::_Destroy(&(*__dst));
  247. _STLP_STD::_Move_Construct(&(*__dst), *__src);
  248. }
  249. if (__dst >= __first) {
  250. //There are more elements to erase than elements to move
  251. _STLP_STD::_Destroy_Range(__first, ++__dst);
  252. _STLP_STD::_Destroy_Moved_Range(this->_M_start, __first);
  253. }
  254. else {
  255. //There are more elements to move than elements to erase
  256. for (; __src >= this->_M_start; --__src, --__dst) {
  257. _STLP_STD::_Destroy_Moved(&(*__dst));
  258. _STLP_STD::_Move_Construct(&(*__dst), *__src);
  259. }
  260. _STLP_STD::_Destroy_Moved_Range(this->_M_start, ++__dst);
  261. }
  262. }
  263. else {
  264. _STLP_STD::_Destroy_Range(this->_M_start, __last);
  265. }
  266. iterator __new_start = this->_M_start + __n;
  267. this->_M_destroy_nodes(this->_M_start._M_node, __new_start._M_node);
  268. this->_M_start = __new_start;
  269. }
  270. else {
  271. if (__last != this->_M_finish) {
  272. iterator __src = __last, __dst = __first;
  273. for (; (__src != this->_M_finish) && (__dst != __last); ++__src, ++__dst) {
  274. _STLP_STD::_Destroy(&(*__dst));
  275. _STLP_STD::_Move_Construct(&(*__dst), *__src);
  276. }
  277. if (__dst != __last) {
  278. //There are more elements to erase than elements to move
  279. _STLP_STD::_Destroy_Range(__dst, __last);
  280. _STLP_STD::_Destroy_Moved_Range(__last, this->_M_finish);
  281. }
  282. else {
  283. //There are more elements to move than elements to erase
  284. for (; __src != this->_M_finish; ++__src, ++__dst) {
  285. _STLP_STD::_Destroy_Moved(&(*__dst));
  286. _STLP_STD::_Move_Construct(&(*__dst), *__src);
  287. }
  288. _STLP_STD::_Destroy_Moved_Range(__dst, this->_M_finish);
  289. }
  290. }
  291. else {
  292. _STLP_STD::_Destroy_Range(__first, this->_M_finish);
  293. }
  294. iterator __new_finish = this->_M_finish - __n;
  295. this->_M_destroy_nodes(__new_finish._M_node + 1, this->_M_finish._M_node + 1);
  296. this->_M_finish = __new_finish;
  297. }
  298. return this->_M_start + __elems_before;
  299. }
  300. template <class _Tp, class _Alloc >
  301. __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __first, iterator __last,
  302. const __false_type& /*_Movable*/) {
  303. difference_type __n = __last - __first;
  304. difference_type __elems_before = __first - this->_M_start;
  305. if (__elems_before <= difference_type(this->size() - __n) / 2) {
  306. copy_backward(this->_M_start, __first, __last);
  307. iterator __new_start = this->_M_start + __n;
  308. _STLP_STD::_Destroy_Range(this->_M_start, __new_start);
  309. this->_M_destroy_nodes(this->_M_start._M_node, __new_start._M_node);
  310. this->_M_start = __new_start;
  311. }
  312. else {
  313. _STLP_STD::copy(__last, this->_M_finish, __first);
  314. iterator __new_finish = this->_M_finish - __n;
  315. _STLP_STD::_Destroy_Range(__new_finish, this->_M_finish);
  316. this->_M_destroy_nodes(__new_finish._M_node + 1, this->_M_finish._M_node + 1);
  317. this->_M_finish = __new_finish;
  318. }
  319. return this->_M_start + __elems_before;
  320. }
  321. template <class _Tp, class _Alloc >
  322. void deque<_Tp,_Alloc>::clear() {
  323. for (_Map_pointer __node = this->_M_start._M_node + 1;
  324. __node < this->_M_finish._M_node;
  325. ++__node) {
  326. _STLP_STD::_Destroy_Range(*__node, *__node + this->buffer_size());
  327. this->_M_map_size.deallocate(*__node, this->buffer_size());
  328. }
  329. if (this->_M_start._M_node != this->_M_finish._M_node) {
  330. _STLP_STD::_Destroy_Range(this->_M_start._M_cur, this->_M_start._M_last);
  331. _STLP_STD::_Destroy_Range(this->_M_finish._M_first, this->_M_finish._M_cur);
  332. this->_M_map_size.deallocate(this->_M_finish._M_first, this->buffer_size());
  333. }
  334. else
  335. _STLP_STD::_Destroy_Range(this->_M_start._M_cur, this->_M_finish._M_cur);
  336. this->_M_finish = this->_M_start;
  337. }
  338. // Precondition: this->_M_start and this->_M_finish have already been initialized,
  339. // but none of the deque's elements have yet been constructed.
  340. template <class _Tp, class _Alloc >
  341. void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __val,
  342. const __false_type& /*_TrivialInit*/) {
  343. _Map_pointer __cur = this->_M_start._M_node;
  344. _STLP_TRY {
  345. for (; __cur < this->_M_finish._M_node; ++__cur)
  346. uninitialized_fill(*__cur, *__cur + this->buffer_size(), __val);
  347. uninitialized_fill(this->_M_finish._M_first, this->_M_finish._M_cur, __val);
  348. }
  349. _STLP_UNWIND(_STLP_STD::_Destroy_Range(this->_M_start, iterator(*__cur, __cur)))
  350. }
  351. // Called only if this->_M_finish._M_cur == this->_M_finish._M_last - 1.
  352. template <class _Tp, class _Alloc >
  353. void deque<_Tp,_Alloc>::_M_push_back_aux_v(const value_type& __t) {
  354. _M_reserve_map_at_back();
  355. *(this->_M_finish._M_node + 1) = this->_M_map_size.allocate(this->buffer_size());
  356. _STLP_TRY {
  357. _Copy_Construct(this->_M_finish._M_cur, __t);
  358. this->_M_finish._M_set_node(this->_M_finish._M_node + 1);
  359. this->_M_finish._M_cur = this->_M_finish._M_first;
  360. }
  361. _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1),
  362. this->buffer_size()))
  363. }
  364. #if defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS)
  365. // Called only if this->_M_finish._M_cur == this->_M_finish._M_last - 1.
  366. template <class _Tp, class _Alloc >
  367. void deque<_Tp,_Alloc>::_M_push_back_aux() {
  368. _M_reserve_map_at_back();
  369. *(this->_M_finish._M_node + 1) = this->_M_map_size.allocate(this->buffer_size());
  370. _STLP_TRY {
  371. _STLP_STD::_Construct(this->_M_finish._M_cur);
  372. this->_M_finish._M_set_node(this->_M_finish._M_node + 1);
  373. this->_M_finish._M_cur = this->_M_finish._M_first;
  374. }
  375. _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1),
  376. this->buffer_size()))
  377. }
  378. #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
  379. // Called only if this->_M_start._M_cur == this->_M_start._M_first.
  380. template <class _Tp, class _Alloc >
  381. void deque<_Tp,_Alloc>::_M_push_front_aux_v(const value_type& __t) {
  382. _M_reserve_map_at_front();
  383. *(this->_M_start._M_node - 1) = this->_M_map_size.allocate(this->buffer_size());
  384. _STLP_TRY {
  385. this->_M_start._M_set_node(this->_M_start._M_node - 1);
  386. this->_M_start._M_cur = this->_M_start._M_last - 1;
  387. _Copy_Construct(this->_M_start._M_cur, __t);
  388. }
  389. _STLP_UNWIND((++this->_M_start,
  390. this->_M_map_size.deallocate(*(this->_M_start._M_node - 1), this->buffer_size())))
  391. }
  392. #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
  393. // Called only if this->_M_start._M_cur == this->_M_start._M_first.
  394. template <class _Tp, class _Alloc >
  395. void deque<_Tp,_Alloc>::_M_push_front_aux() {
  396. _M_reserve_map_at_front();
  397. *(this->_M_start._M_node - 1) = this->_M_map_size.allocate(this->buffer_size());
  398. _STLP_TRY {
  399. this->_M_start._M_set_node(this->_M_start._M_node - 1);
  400. this->_M_start._M_cur = this->_M_start._M_last - 1;
  401. _STLP_STD::_Construct(this->_M_start._M_cur);
  402. }
  403. _STLP_UNWIND((++this->_M_start, this->_M_map_size.deallocate(*(this->_M_start._M_node - 1),
  404. this->buffer_size())))
  405. }
  406. #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
  407. // Called only if this->_M_finish._M_cur == this->_M_finish._M_first.
  408. template <class _Tp, class _Alloc >
  409. void deque<_Tp,_Alloc>::_M_pop_back_aux() {
  410. this->_M_map_size.deallocate(this->_M_finish._M_first, this->buffer_size());
  411. this->_M_finish._M_set_node(this->_M_finish._M_node - 1);
  412. this->_M_finish._M_cur = this->_M_finish._M_last - 1;
  413. }
  414. // Note that if the deque has at least one element (a precondition for this member
  415. // function), and if this->_M_start._M_cur == this->_M_start._M_last, then the deque
  416. // must have at least two nodes.
  417. template <class _Tp, class _Alloc >
  418. void deque<_Tp,_Alloc>::_M_pop_front_aux() {
  419. if (this->_M_start._M_cur != this->_M_start._M_last - 1)
  420. ++this->_M_start._M_cur;
  421. else {
  422. this->_M_map_size.deallocate(this->_M_start._M_first, this->buffer_size());
  423. this->_M_start._M_set_node(this->_M_start._M_node + 1);
  424. this->_M_start._M_cur = this->_M_start._M_first;
  425. }
  426. }
  427. template <class _Tp, class _Alloc >
  428. __iterator__ deque<_Tp,_Alloc>::_M_fill_insert_aux(iterator __pos, size_type __n,
  429. const value_type& __x,
  430. const __true_type& /*_Movable*/) {
  431. const difference_type __elems_before = __pos - this->_M_start;
  432. size_type __length = this->size();
  433. value_type __x_copy = __x;
  434. if (__elems_before <= difference_type(__length / 2)) {
  435. iterator __new_start = _M_reserve_elements_at_front(__n);
  436. __pos = this->_M_start + __elems_before;
  437. _STLP_TRY {
  438. iterator __dst = __new_start;
  439. iterator __src = this->_M_start;
  440. for (; __src != __pos; ++__dst, ++__src) {
  441. _STLP_STD::_Move_Construct(&(*__dst), *__src);
  442. _STLP_STD::_Destroy_Moved(&(*__src));
  443. }
  444. this->_M_start = __new_start;
  445. uninitialized_fill(__dst, __src, __x_copy);
  446. __pos = __dst;
  447. }
  448. _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
  449. }
  450. else {
  451. iterator __new_finish = _M_reserve_elements_at_back(__n);
  452. const difference_type __elems_after = difference_type(__length) - __elems_before;
  453. __pos = this->_M_finish - __elems_after;
  454. _STLP_TRY {
  455. iterator __dst = __new_finish;
  456. iterator __src = this->_M_finish;
  457. for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
  458. _STLP_STD::_Move_Construct(&(*__dst), *__src);
  459. _STLP_STD::_Destroy_Moved(&(*__src));
  460. }
  461. this->_M_finish = __new_finish;
  462. uninitialized_fill(__pos, __pos + __n, __x_copy);
  463. }
  464. _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
  465. }
  466. return __pos;
  467. }
  468. template <class _Tp, class _Alloc >
  469. __iterator__ deque<_Tp,_Alloc>::_M_fill_insert_aux(iterator __pos, size_type __n,
  470. const value_type& __x,
  471. const __false_type& /*_Movable*/) {
  472. const difference_type __elems_before = __pos - this->_M_start;
  473. size_type __length = this->size();
  474. value_type __x_copy = __x;
  475. if (__elems_before <= difference_type(__length / 2)) {
  476. iterator __new_start = _M_reserve_elements_at_front(__n);
  477. iterator __old_start = this->_M_start;
  478. __pos = this->_M_start + __elems_before;
  479. _STLP_TRY {
  480. if (__elems_before >= difference_type(__n)) {
  481. iterator __start_n = this->_M_start + difference_type(__n);
  482. _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start);
  483. this->_M_start = __new_start;
  484. _STLP_STD::copy(__start_n, __pos, __old_start);
  485. _STLP_STD::fill(__pos - difference_type(__n), __pos, __x_copy);
  486. __pos -= difference_type(__n);
  487. }
  488. else {
  489. _STLP_PRIV __uninitialized_copy_fill(this->_M_start, __pos, __new_start,
  490. this->_M_start, __x_copy);
  491. this->_M_start = __new_start;
  492. fill(__old_start, __pos, __x_copy);
  493. }
  494. }
  495. _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
  496. }
  497. else {
  498. iterator __new_finish = _M_reserve_elements_at_back(__n);
  499. iterator __old_finish = this->_M_finish;
  500. const difference_type __elems_after =
  501. difference_type(__length) - __elems_before;
  502. __pos = this->_M_finish - __elems_after;
  503. _STLP_TRY {
  504. if (__elems_after > difference_type(__n)) {
  505. iterator __finish_n = this->_M_finish - difference_type(__n);
  506. _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish);
  507. this->_M_finish = __new_finish;
  508. copy_backward(__pos, __finish_n, __old_finish);
  509. fill(__pos, __pos + difference_type(__n), __x_copy);
  510. }
  511. else {
  512. _STLP_PRIV __uninitialized_fill_copy(this->_M_finish, __pos + difference_type(__n),
  513. __x_copy, __pos, this->_M_finish);
  514. this->_M_finish = __new_finish;
  515. fill(__pos, __old_finish, __x_copy);
  516. }
  517. }
  518. _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
  519. }
  520. return __pos;
  521. }
  522. #if !defined (_STLP_MEMBER_TEMPLATES)
  523. template <class _Tp, class _Alloc >
  524. void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
  525. const value_type* __first, const value_type* __last,
  526. size_type __n, const __true_type& /*_Movable*/) {
  527. const difference_type __elems_before = __pos - this->_M_start;
  528. size_type __length = size();
  529. if (__elems_before <= difference_type(__length / 2)) {
  530. iterator __new_start = _M_reserve_elements_at_front(__n);
  531. __pos = this->_M_start + __elems_before;
  532. _STLP_TRY {
  533. iterator __dst = __new_start;
  534. iterator __src = this->_M_start;
  535. for (; __src != __pos; ++__dst, ++__src) {
  536. _STLP_STD::_Move_Construct(&(*__dst), *__src);
  537. _STLP_STD::_Destroy_Moved(&(*__src));
  538. }
  539. this->_M_start = __new_start;
  540. _STLP_PRIV __ucopy(__first, __last, __dst);
  541. }
  542. _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
  543. }
  544. else {
  545. iterator __new_finish = _M_reserve_elements_at_back(__n);
  546. const difference_type __elems_after = difference_type(__length) - __elems_before;
  547. __pos = this->_M_finish - __elems_after;
  548. _STLP_TRY {
  549. iterator __dst = __new_finish;
  550. iterator __src = this->_M_finish;
  551. for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
  552. _STLP_STD::_Move_Construct(&(*__dst), *__src);
  553. _STLP_STD::_Destroy_Moved(&(*__src));
  554. }
  555. this->_M_finish = __new_finish;
  556. _STLP_PRIV __ucopy(__first, __last, __pos);
  557. }
  558. _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
  559. }
  560. }
  561. template <class _Tp, class _Alloc >
  562. void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
  563. const value_type* __first, const value_type* __last,
  564. size_type __n, const __false_type& /*_Movable*/) {
  565. const difference_type __elems_before = __pos - this->_M_start;
  566. size_type __length = size();
  567. if (__elems_before <= difference_type(__length / 2)) {
  568. iterator __new_start = _M_reserve_elements_at_front(__n);
  569. iterator __old_start = this->_M_start;
  570. __pos = this->_M_start + __elems_before;
  571. _STLP_TRY {
  572. if (__elems_before >= difference_type(__n)) {
  573. iterator __start_n = this->_M_start + difference_type(__n);
  574. _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start);
  575. this->_M_start = __new_start;
  576. _STLP_STD::copy(__start_n, __pos, __old_start);
  577. _STLP_STD::copy(__first, __last, __pos - difference_type(__n));
  578. }
  579. else {
  580. const value_type* __mid = __first + (difference_type(__n) - __elems_before);
  581. _STLP_PRIV __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start);
  582. this->_M_start = __new_start;
  583. _STLP_STD::copy(__mid, __last, __old_start);
  584. }
  585. }
  586. _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
  587. }
  588. else {
  589. iterator __new_finish = _M_reserve_elements_at_back(__n);
  590. iterator __old_finish = this->_M_finish;
  591. const difference_type __elems_after =
  592. difference_type(__length) - __elems_before;
  593. __pos = this->_M_finish - __elems_after;
  594. _STLP_TRY {
  595. if (__elems_after > difference_type(__n)) {
  596. iterator __finish_n = this->_M_finish - difference_type(__n);
  597. _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish);
  598. this->_M_finish = __new_finish;
  599. _STLP_STD::copy_backward(__pos, __finish_n, __old_finish);
  600. _STLP_STD::copy(__first, __last, __pos);
  601. }
  602. else {
  603. const value_type* __mid = __first + __elems_after;
  604. _STLP_PRIV __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish);
  605. this->_M_finish = __new_finish;
  606. _STLP_STD::copy(__first, __mid, __pos);
  607. }
  608. }
  609. _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
  610. }
  611. }
  612. template <class _Tp, class _Alloc >
  613. void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
  614. const_iterator __first, const_iterator __last,
  615. size_type __n, const __true_type& /*_Movable*/) {
  616. const difference_type __elems_before = __pos - this->_M_start;
  617. size_type __length = size();
  618. if (__elems_before <= difference_type(__length / 2)) {
  619. iterator __new_start = _M_reserve_elements_at_front(__n);
  620. __pos = this->_M_start + __elems_before;
  621. _STLP_TRY {
  622. iterator __dst = __new_start;
  623. iterator __src = this->_M_start;
  624. for (; __src != __pos; ++__dst, ++__src) {
  625. _STLP_STD::_Move_Construct(&(*__dst), *__src);
  626. _STLP_STD::_Destroy_Moved(&(*__src));
  627. }
  628. this->_M_start = __new_start;
  629. _STLP_PRIV __ucopy(__first, __last, __dst);
  630. }
  631. _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
  632. }
  633. else {
  634. iterator __new_finish = _M_reserve_elements_at_back(__n);
  635. const difference_type __elems_after = difference_type(__length) - __elems_before;
  636. __pos = this->_M_finish - __elems_after;
  637. _STLP_TRY {
  638. iterator __dst = __new_finish;
  639. iterator __src = this->_M_finish;
  640. for (--__src, --__dst; __src >= __pos; --__src, --__dst) {
  641. _STLP_STD::_Move_Construct(&(*__dst), *__src);
  642. _STLP_STD::_Destroy_Moved(&(*__src));
  643. }
  644. this->_M_finish = __new_finish;
  645. _STLP_PRIV __ucopy(__first, __last, __pos);
  646. }
  647. _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
  648. }
  649. }
  650. template <class _Tp, class _Alloc >
  651. void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos,
  652. const_iterator __first, const_iterator __last,
  653. size_type __n, const __false_type& /*_Movable*/) {
  654. const difference_type __elems_before = __pos - this->_M_start;
  655. size_type __length = size();
  656. if (__elems_before < difference_type(__length / 2)) {
  657. iterator __new_start = _M_reserve_elements_at_front(__n);
  658. iterator __old_start = this->_M_start;
  659. __pos = this->_M_start + __elems_before;
  660. _STLP_TRY {
  661. if (__elems_before >= difference_type(__n)) {
  662. iterator __start_n = this->_M_start + __n;
  663. _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start);
  664. this->_M_start = __new_start;
  665. _STLP_STD::copy(__start_n, __pos, __old_start);
  666. _STLP_STD::copy(__first, __last, __pos - difference_type(__n));
  667. }
  668. else {
  669. const_iterator __mid = __first + (__n - __elems_before);
  670. _STLP_PRIV __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start);
  671. this->_M_start = __new_start;
  672. _STLP_STD::copy(__mid, __last, __old_start);
  673. }
  674. }
  675. _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
  676. }
  677. else {
  678. iterator __new_finish = _M_reserve_elements_at_back(__n);
  679. iterator __old_finish = this->_M_finish;
  680. const difference_type __elems_after = __length - __elems_before;
  681. __pos = this->_M_finish - __elems_after;
  682. _STLP_TRY {
  683. if (__elems_after > difference_type(__n)) {
  684. iterator __finish_n = this->_M_finish - difference_type(__n);
  685. _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish);
  686. this->_M_finish = __new_finish;
  687. _STLP_STD::copy_backward(__pos, __finish_n, __old_finish);
  688. _STLP_STD::copy(__first, __last, __pos);
  689. }
  690. else {
  691. const_iterator __mid = __first + __elems_after;
  692. _STLP_PRIV __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish);
  693. this->_M_finish = __new_finish;
  694. _STLP_STD::copy(__first, __mid, __pos);
  695. }
  696. }
  697. _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1))
  698. }
  699. }
  700. #endif /* _STLP_MEMBER_TEMPLATES */
  701. template <class _Tp, class _Alloc >
  702. void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems) {
  703. size_type __new_nodes
  704. = (__new_elems + this->buffer_size() - 1) / this->buffer_size();
  705. _M_reserve_map_at_front(__new_nodes);
  706. size_type __i = 1;
  707. _STLP_TRY {
  708. for (; __i <= __new_nodes; ++__i)
  709. *(this->_M_start._M_node - __i) = this->_M_map_size.allocate(this->buffer_size());
  710. }
  711. _STLP_UNWIND(for (size_type __j = 1; __j < __i; ++__j)
  712. this->_M_map_size.deallocate(*(this->_M_start._M_node - __j), this->buffer_size()))
  713. }
  714. template <class _Tp, class _Alloc >
  715. void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems) {
  716. size_type __new_nodes
  717. = (__new_elems + this->buffer_size() - 1) / this->buffer_size();
  718. _M_reserve_map_at_back(__new_nodes);
  719. size_type __i = 1;
  720. _STLP_TRY {
  721. for (; __i <= __new_nodes; ++__i)
  722. *(this->_M_finish._M_node + __i) = this->_M_map_size.allocate(this->buffer_size());
  723. }
  724. _STLP_UNWIND(for (size_type __j = 1; __j < __i; ++__j)
  725. this->_M_map_size.deallocate(*(this->_M_finish._M_node + __j), this->buffer_size()))
  726. }
  727. template <class _Tp, class _Alloc >
  728. void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add,
  729. bool __add_at_front) {
  730. size_type __old_num_nodes = this->_M_finish._M_node - this->_M_start._M_node + 1;
  731. size_type __new_num_nodes = __old_num_nodes + __nodes_to_add;
  732. _Map_pointer __new_nstart;
  733. if (this->_M_map_size._M_data > 2 * __new_num_nodes) {
  734. __new_nstart = this->_M_map._M_data + (this->_M_map_size._M_data - __new_num_nodes) / 2
  735. + (__add_at_front ? __nodes_to_add : 0);
  736. if (__new_nstart < this->_M_start._M_node)
  737. _STLP_STD::copy(this->_M_start._M_node, this->_M_finish._M_node + 1, __new_nstart);
  738. else
  739. _STLP_STD::copy_backward(this->_M_start._M_node, this->_M_finish._M_node + 1,
  740. __new_nstart + __old_num_nodes);
  741. }
  742. else {
  743. size_type __new_map_size =
  744. this->_M_map_size._M_data + (max)((size_t)this->_M_map_size._M_data, __nodes_to_add) + 2;
  745. _Map_pointer __new_map = this->_M_map.allocate(__new_map_size);
  746. __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2
  747. + (__add_at_front ? __nodes_to_add : 0);
  748. _STLP_STD::copy(this->_M_start._M_node, this->_M_finish._M_node + 1, __new_nstart);
  749. this->_M_map.deallocate(this->_M_map._M_data, this->_M_map_size._M_data);
  750. this->_M_map._M_data = __new_map;
  751. this->_M_map_size._M_data = __new_map_size;
  752. }
  753. this->_M_start._M_set_node(__new_nstart);
  754. this->_M_finish._M_set_node(__new_nstart + __old_num_nodes - 1);
  755. }
  756. #if defined (deque)
  757. # undef deque
  758. _STLP_MOVE_TO_STD_NAMESPACE
  759. #endif
  760. _STLP_END_NAMESPACE
  761. #undef __iterator__
  762. #undef iterator
  763. #undef const_iterator
  764. #undef size_type
  765. #undef value_type
  766. #endif /* _STLP_DEQUE_C */
  767. // Local Variables:
  768. // mode:C++
  769. // End: