]>
Commit | Line | Data |
---|---|---|
83144cfc PE |
1 | // Deque implementation (out of line) -*- C++ -*- |
2 | ||
f6592a9e | 3 | // Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc. |
83144cfc PE |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free | |
6 | // software; you can redistribute it and/or modify it under the | |
7 | // terms of the GNU General Public License as published by the | |
8 | // Free Software Foundation; either version 2, or (at your option) | |
9 | // any later version. | |
10 | ||
11 | // This library is distributed in the hope that it will be useful, | |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | // GNU General Public License for more details. | |
15 | ||
16 | // You should have received a copy of the GNU General Public License along | |
17 | // with this library; see the file COPYING. If not, write to the Free | |
18 | // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, | |
19 | // USA. | |
20 | ||
21 | // As a special exception, you may use this file as part of a free software | |
22 | // library without restriction. Specifically, if other files instantiate | |
23 | // templates or use macros or inline functions from this file, or you compile | |
24 | // this file and link it with other files to produce an executable, this | |
25 | // file does not by itself cause the resulting executable to be covered by | |
26 | // the GNU General Public License. This exception does not however | |
27 | // invalidate any other reasons why the executable file might be covered by | |
28 | // the GNU General Public License. | |
29 | ||
30 | /* | |
31 | * | |
32 | * Copyright (c) 1994 | |
33 | * Hewlett-Packard Company | |
34 | * | |
35 | * Permission to use, copy, modify, distribute and sell this software | |
36 | * and its documentation for any purpose is hereby granted without fee, | |
37 | * provided that the above copyright notice appear in all copies and | |
38 | * that both that copyright notice and this permission notice appear | |
39 | * in supporting documentation. Hewlett-Packard Company makes no | |
40 | * representations about the suitability of this software for any | |
41 | * purpose. It is provided "as is" without express or implied warranty. | |
42 | * | |
43 | * | |
44 | * Copyright (c) 1997 | |
45 | * Silicon Graphics Computer Systems, Inc. | |
46 | * | |
47 | * Permission to use, copy, modify, distribute and sell this software | |
48 | * and its documentation for any purpose is hereby granted without fee, | |
49 | * provided that the above copyright notice appear in all copies and | |
50 | * that both that copyright notice and this permission notice appear | |
51 | * in supporting documentation. Silicon Graphics makes no | |
52 | * representations about the suitability of this software for any | |
53 | * purpose. It is provided "as is" without express or implied warranty. | |
54 | */ | |
55 | ||
56 | /** @file deque.tcc | |
57 | * This is an internal header file, included by other library headers. | |
58 | * You should not attempt to use it directly. | |
59 | */ | |
60 | ||
3d7c150e BK |
61 | #ifndef _DEQUE_TCC |
62 | #define _DEQUE_TCC 1 | |
83144cfc | 63 | |
390e4c0d | 64 | namespace _GLIBCXX_STD |
ed6814f7 | 65 | { |
3971a4d2 | 66 | template <typename _Tp, typename _Alloc> |
23d4fa49 PC |
67 | deque<_Tp, _Alloc>& |
68 | deque<_Tp, _Alloc>:: | |
3971a4d2 | 69 | operator=(const deque& __x) |
83144cfc | 70 | { |
3971a4d2 PE |
71 | const size_type __len = size(); |
72 | if (&__x != this) | |
f6592a9e PC |
73 | { |
74 | if (__len >= __x.size()) | |
03f9ea44 DM |
75 | erase(std::copy(__x.begin(), __x.end(), this->_M_impl._M_start), |
76 | this->_M_impl._M_finish); | |
f6592a9e PC |
77 | else |
78 | { | |
79 | const_iterator __mid = __x.begin() + difference_type(__len); | |
03f9ea44 DM |
80 | std::copy(__x.begin(), __mid, this->_M_impl._M_start); |
81 | insert(this->_M_impl._M_finish, __mid, __x.end()); | |
f6592a9e PC |
82 | } |
83 | } | |
3971a4d2 | 84 | return *this; |
ed6814f7 BI |
85 | } |
86 | ||
3971a4d2 | 87 | template <typename _Tp, typename _Alloc> |
23d4fa49 | 88 | typename deque<_Tp, _Alloc>::iterator |
43da93a7 | 89 | deque<_Tp, _Alloc>:: |
3971a4d2 | 90 | insert(iterator position, const value_type& __x) |
83144cfc | 91 | { |
03f9ea44 | 92 | if (position._M_cur == this->_M_impl._M_start._M_cur) |
f6592a9e PC |
93 | { |
94 | push_front(__x); | |
03f9ea44 | 95 | return this->_M_impl._M_start; |
f6592a9e | 96 | } |
03f9ea44 | 97 | else if (position._M_cur == this->_M_impl._M_finish._M_cur) |
f6592a9e PC |
98 | { |
99 | push_back(__x); | |
03f9ea44 | 100 | iterator __tmp = this->_M_impl._M_finish; |
f6592a9e PC |
101 | --__tmp; |
102 | return __tmp; | |
103 | } | |
83144cfc | 104 | else |
3971a4d2 | 105 | return _M_insert_aux(position, __x); |
83144cfc | 106 | } |
ed6814f7 | 107 | |
3971a4d2 | 108 | template <typename _Tp, typename _Alloc> |
23d4fa49 | 109 | typename deque<_Tp, _Alloc>::iterator |
43da93a7 | 110 | deque<_Tp, _Alloc>:: |
3971a4d2 | 111 | erase(iterator __position) |
83144cfc | 112 | { |
3971a4d2 PE |
113 | iterator __next = __position; |
114 | ++__next; | |
43da93a7 | 115 | const size_type __index = __position - this->_M_impl._M_start; |
3971a4d2 | 116 | if (__index < (size() >> 1)) |
f6592a9e | 117 | { |
03f9ea44 | 118 | std::copy_backward(this->_M_impl._M_start, __position, __next); |
f6592a9e PC |
119 | pop_front(); |
120 | } | |
3971a4d2 | 121 | else |
f6592a9e | 122 | { |
03f9ea44 | 123 | std::copy(__next, this->_M_impl._M_finish, __position); |
f6592a9e PC |
124 | pop_back(); |
125 | } | |
03f9ea44 | 126 | return this->_M_impl._M_start + __index; |
3971a4d2 | 127 | } |
ed6814f7 | 128 | |
3971a4d2 | 129 | template <typename _Tp, typename _Alloc> |
23d4fa49 | 130 | typename deque<_Tp, _Alloc>::iterator |
43da93a7 | 131 | deque<_Tp, _Alloc>:: |
3971a4d2 | 132 | erase(iterator __first, iterator __last) |
83144cfc | 133 | { |
0d8c9baf PC |
134 | if (__first == this->_M_impl._M_start |
135 | && __last == this->_M_impl._M_finish) | |
f6592a9e PC |
136 | { |
137 | clear(); | |
03f9ea44 | 138 | return this->_M_impl._M_finish; |
f6592a9e | 139 | } |
3971a4d2 | 140 | else |
f6592a9e PC |
141 | { |
142 | const difference_type __n = __last - __first; | |
0d8c9baf PC |
143 | const difference_type __elems_before = (__first |
144 | - this->_M_impl._M_start); | |
f6592a9e PC |
145 | if (static_cast<size_type>(__elems_before) < (size() - __n) / 2) |
146 | { | |
03f9ea44 DM |
147 | std::copy_backward(this->_M_impl._M_start, __first, __last); |
148 | iterator __new_start = this->_M_impl._M_start + __n; | |
1985f1cd MA |
149 | std::_Destroy(this->_M_impl._M_start, __new_start, |
150 | this->get_allocator()); | |
0d8c9baf PC |
151 | _M_destroy_nodes(this->_M_impl._M_start._M_node, |
152 | __new_start._M_node); | |
03f9ea44 | 153 | this->_M_impl._M_start = __new_start; |
f6592a9e PC |
154 | } |
155 | else | |
156 | { | |
03f9ea44 DM |
157 | std::copy(__last, this->_M_impl._M_finish, __first); |
158 | iterator __new_finish = this->_M_impl._M_finish - __n; | |
1985f1cd MA |
159 | std::_Destroy(__new_finish, this->_M_impl._M_finish, |
160 | this->get_allocator()); | |
f6592a9e | 161 | _M_destroy_nodes(__new_finish._M_node + 1, |
03f9ea44 DM |
162 | this->_M_impl._M_finish._M_node + 1); |
163 | this->_M_impl._M_finish = __new_finish; | |
f6592a9e | 164 | } |
03f9ea44 | 165 | return this->_M_impl._M_start + __elems_before; |
f6592a9e | 166 | } |
83144cfc | 167 | } |
ed6814f7 BI |
168 | |
169 | template <typename _Tp, typename _Alloc> | |
83144cfc | 170 | void |
43da93a7 | 171 | deque<_Tp, _Alloc>:: |
3971a4d2 | 172 | clear() |
83144cfc | 173 | { |
03f9ea44 DM |
174 | for (_Map_pointer __node = this->_M_impl._M_start._M_node + 1; |
175 | __node < this->_M_impl._M_finish._M_node; | |
3971a4d2 | 176 | ++__node) |
f6592a9e | 177 | { |
1985f1cd MA |
178 | std::_Destroy(*__node, *__node + _S_buffer_size(), |
179 | this->get_allocator()); | |
f6592a9e PC |
180 | _M_deallocate_node(*__node); |
181 | } | |
ed6814f7 | 182 | |
03f9ea44 | 183 | if (this->_M_impl._M_start._M_node != this->_M_impl._M_finish._M_node) |
f6592a9e | 184 | { |
0d8c9baf | 185 | std::_Destroy(this->_M_impl._M_start._M_cur, |
1985f1cd MA |
186 | this->_M_impl._M_start._M_last, |
187 | this->get_allocator()); | |
0d8c9baf | 188 | std::_Destroy(this->_M_impl._M_finish._M_first, |
1985f1cd MA |
189 | this->_M_impl._M_finish._M_cur, |
190 | this->get_allocator()); | |
03f9ea44 | 191 | _M_deallocate_node(this->_M_impl._M_finish._M_first); |
f6592a9e | 192 | } |
3971a4d2 | 193 | else |
0d8c9baf | 194 | std::_Destroy(this->_M_impl._M_start._M_cur, |
1985f1cd MA |
195 | this->_M_impl._M_finish._M_cur, |
196 | this->get_allocator()); | |
ed6814f7 | 197 | |
03f9ea44 | 198 | this->_M_impl._M_finish = this->_M_impl._M_start; |
3971a4d2 | 199 | } |
ed6814f7 | 200 | |
3971a4d2 | 201 | template <typename _Tp, class _Alloc> |
08addde6 | 202 | template <typename _InputIterator> |
3971a4d2 | 203 | void |
43da93a7 | 204 | deque<_Tp, _Alloc> |
f6592a9e PC |
205 | ::_M_assign_aux(_InputIterator __first, _InputIterator __last, |
206 | input_iterator_tag) | |
83144cfc | 207 | { |
3971a4d2 | 208 | iterator __cur = begin(); |
43da93a7 | 209 | for (; __first != __last && __cur != end(); ++__cur, ++__first) |
3971a4d2 PE |
210 | *__cur = *__first; |
211 | if (__first == __last) | |
212 | erase(__cur, end()); | |
213 | else | |
214 | insert(end(), __first, __last); | |
83144cfc | 215 | } |
ed6814f7 | 216 | |
3971a4d2 | 217 | template <typename _Tp, typename _Alloc> |
83144cfc | 218 | void |
43da93a7 | 219 | deque<_Tp, _Alloc>:: |
3971a4d2 | 220 | _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) |
83144cfc | 221 | { |
03f9ea44 | 222 | if (__pos._M_cur == this->_M_impl._M_start._M_cur) |
f6592a9e PC |
223 | { |
224 | iterator __new_start = _M_reserve_elements_at_front(__n); | |
225 | try | |
226 | { | |
1985f1cd MA |
227 | std::__uninitialized_fill_a(__new_start, this->_M_impl._M_start, |
228 | __x, | |
229 | this->get_allocator()); | |
03f9ea44 | 230 | this->_M_impl._M_start = __new_start; |
f6592a9e PC |
231 | } |
232 | catch(...) | |
233 | { | |
0d8c9baf PC |
234 | _M_destroy_nodes(__new_start._M_node, |
235 | this->_M_impl._M_start._M_node); | |
f6592a9e PC |
236 | __throw_exception_again; |
237 | } | |
238 | } | |
03f9ea44 | 239 | else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) |
f6592a9e PC |
240 | { |
241 | iterator __new_finish = _M_reserve_elements_at_back(__n); | |
242 | try | |
243 | { | |
1985f1cd MA |
244 | std::__uninitialized_fill_a(this->_M_impl._M_finish, |
245 | __new_finish, __x, | |
246 | this->get_allocator()); | |
03f9ea44 | 247 | this->_M_impl._M_finish = __new_finish; |
f6592a9e PC |
248 | } |
249 | catch(...) | |
250 | { | |
03f9ea44 | 251 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
ed6814f7 | 252 | __new_finish._M_node + 1); |
f6592a9e PC |
253 | __throw_exception_again; |
254 | } | |
255 | } | |
ed6814f7 | 256 | else |
3971a4d2 | 257 | _M_insert_aux(__pos, __n, __x); |
83144cfc | 258 | } |
ed6814f7 | 259 | |
3971a4d2 PE |
260 | template <typename _Tp, typename _Alloc> |
261 | void | |
43da93a7 | 262 | deque<_Tp, _Alloc>:: |
3971a4d2 | 263 | _M_fill_initialize(const value_type& __value) |
83144cfc | 264 | { |
3971a4d2 PE |
265 | _Map_pointer __cur; |
266 | try | |
267 | { | |
03f9ea44 DM |
268 | for (__cur = this->_M_impl._M_start._M_node; |
269 | __cur < this->_M_impl._M_finish._M_node; | |
8fbc5ae7 | 270 | ++__cur) |
1985f1cd MA |
271 | std::__uninitialized_fill_a(*__cur, *__cur + _S_buffer_size(), __value, |
272 | this->get_allocator()); | |
273 | std::__uninitialized_fill_a(this->_M_impl._M_finish._M_first, | |
274 | this->_M_impl._M_finish._M_cur, | |
275 | __value, | |
276 | this->get_allocator()); | |
3971a4d2 PE |
277 | } |
278 | catch(...) | |
279 | { | |
1985f1cd MA |
280 | std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur), |
281 | this->get_allocator()); | |
3971a4d2 PE |
282 | __throw_exception_again; |
283 | } | |
83144cfc | 284 | } |
ed6814f7 | 285 | |
3971a4d2 PE |
286 | template <typename _Tp, typename _Alloc> |
287 | template <typename _InputIterator> | |
288 | void | |
43da93a7 | 289 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
290 | _M_range_initialize(_InputIterator __first, _InputIterator __last, |
291 | input_iterator_tag) | |
292 | { | |
f2ffecb1 | 293 | this->_M_initialize_map(0); |
3971a4d2 PE |
294 | try |
295 | { | |
43da93a7 | 296 | for (; __first != __last; ++__first) |
3971a4d2 PE |
297 | push_back(*__first); |
298 | } | |
299 | catch(...) | |
300 | { | |
301 | clear(); | |
302 | __throw_exception_again; | |
303 | } | |
304 | } | |
ed6814f7 | 305 | |
3971a4d2 PE |
306 | template <typename _Tp, typename _Alloc> |
307 | template <typename _ForwardIterator> | |
308 | void | |
43da93a7 | 309 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
310 | _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, |
311 | forward_iterator_tag) | |
312 | { | |
f6592a9e | 313 | const size_type __n = std::distance(__first, __last); |
f2ffecb1 | 314 | this->_M_initialize_map(__n); |
ed6814f7 | 315 | |
3971a4d2 PE |
316 | _Map_pointer __cur_node; |
317 | try | |
318 | { | |
03f9ea44 DM |
319 | for (__cur_node = this->_M_impl._M_start._M_node; |
320 | __cur_node < this->_M_impl._M_finish._M_node; | |
3971a4d2 PE |
321 | ++__cur_node) |
322 | { | |
323 | _ForwardIterator __mid = __first; | |
5b5bf717 | 324 | std::advance(__mid, _S_buffer_size()); |
1985f1cd MA |
325 | std::__uninitialized_copy_a(__first, __mid, *__cur_node, |
326 | this->get_allocator()); | |
3971a4d2 PE |
327 | __first = __mid; |
328 | } | |
1985f1cd MA |
329 | std::__uninitialized_copy_a(__first, __last, |
330 | this->_M_impl._M_finish._M_first, | |
331 | this->get_allocator()); | |
3971a4d2 PE |
332 | } |
333 | catch(...) | |
334 | { | |
0d8c9baf | 335 | std::_Destroy(this->_M_impl._M_start, |
1985f1cd MA |
336 | iterator(*__cur_node, __cur_node), |
337 | this->get_allocator()); | |
3971a4d2 PE |
338 | __throw_exception_again; |
339 | } | |
340 | } | |
ed6814f7 | 341 | |
03f9ea44 | 342 | // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. |
3971a4d2 PE |
343 | template <typename _Tp, typename _Alloc> |
344 | void | |
43da93a7 | 345 | deque<_Tp, _Alloc>:: |
3971a4d2 | 346 | _M_push_back_aux(const value_type& __t) |
83144cfc | 347 | { |
3971a4d2 PE |
348 | value_type __t_copy = __t; |
349 | _M_reserve_map_at_back(); | |
03f9ea44 | 350 | *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); |
3971a4d2 PE |
351 | try |
352 | { | |
1985f1cd | 353 | this->_M_impl.construct(this->_M_impl._M_finish._M_cur, __t_copy); |
0d8c9baf PC |
354 | this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node |
355 | + 1); | |
03f9ea44 | 356 | this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; |
3971a4d2 PE |
357 | } |
358 | catch(...) | |
359 | { | |
03f9ea44 | 360 | _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); |
3971a4d2 PE |
361 | __throw_exception_again; |
362 | } | |
83144cfc | 363 | } |
ed6814f7 | 364 | |
03f9ea44 | 365 | // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. |
3971a4d2 PE |
366 | template <typename _Tp, typename _Alloc> |
367 | void | |
43da93a7 | 368 | deque<_Tp, _Alloc>:: |
3971a4d2 | 369 | _M_push_front_aux(const value_type& __t) |
83144cfc | 370 | { |
3971a4d2 PE |
371 | value_type __t_copy = __t; |
372 | _M_reserve_map_at_front(); | |
03f9ea44 | 373 | *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); |
83144cfc PE |
374 | try |
375 | { | |
0d8c9baf PC |
376 | this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node |
377 | - 1); | |
03f9ea44 | 378 | this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; |
1985f1cd | 379 | this->_M_impl.construct(this->_M_impl._M_start._M_cur, __t_copy); |
83144cfc PE |
380 | } |
381 | catch(...) | |
3971a4d2 | 382 | { |
03f9ea44 DM |
383 | ++this->_M_impl._M_start; |
384 | _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); | |
83144cfc PE |
385 | __throw_exception_again; |
386 | } | |
ed6814f7 BI |
387 | } |
388 | ||
03f9ea44 | 389 | // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. |
3971a4d2 | 390 | template <typename _Tp, typename _Alloc> |
43da93a7 | 391 | void deque<_Tp, _Alloc>:: |
3971a4d2 PE |
392 | _M_pop_back_aux() |
393 | { | |
03f9ea44 DM |
394 | _M_deallocate_node(this->_M_impl._M_finish._M_first); |
395 | this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); | |
396 | this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; | |
1985f1cd | 397 | this->_M_impl.destroy(this->_M_impl._M_finish._M_cur); |
83144cfc | 398 | } |
ed6814f7 | 399 | |
0d8c9baf PC |
400 | // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. |
401 | // Note that if the deque has at least one element (a precondition for this | |
402 | // member function), and if | |
403 | // _M_impl._M_start._M_cur == _M_impl._M_start._M_last, | |
404 | // then the deque must have at least two nodes. | |
3971a4d2 | 405 | template <typename _Tp, typename _Alloc> |
43da93a7 | 406 | void deque<_Tp, _Alloc>:: |
3971a4d2 PE |
407 | _M_pop_front_aux() |
408 | { | |
1985f1cd | 409 | this->_M_impl.destroy(this->_M_impl._M_start._M_cur); |
03f9ea44 DM |
410 | _M_deallocate_node(this->_M_impl._M_start._M_first); |
411 | this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); | |
412 | this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; | |
ed6814f7 BI |
413 | } |
414 | ||
3971a4d2 PE |
415 | template <typename _Tp, typename _Alloc> |
416 | template <typename _InputIterator> | |
417 | void | |
43da93a7 | 418 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
419 | _M_range_insert_aux(iterator __pos, |
420 | _InputIterator __first, _InputIterator __last, | |
421 | input_iterator_tag) | |
f6592a9e | 422 | { std::copy(__first, __last, std::inserter(*this, __pos)); } |
ed6814f7 | 423 | |
3971a4d2 PE |
424 | template <typename _Tp, typename _Alloc> |
425 | template <typename _ForwardIterator> | |
426 | void | |
43da93a7 | 427 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
428 | _M_range_insert_aux(iterator __pos, |
429 | _ForwardIterator __first, _ForwardIterator __last, | |
430 | forward_iterator_tag) | |
431 | { | |
43da93a7 | 432 | const size_type __n = std::distance(__first, __last); |
03f9ea44 | 433 | if (__pos._M_cur == this->_M_impl._M_start._M_cur) |
f6592a9e PC |
434 | { |
435 | iterator __new_start = _M_reserve_elements_at_front(__n); | |
436 | try | |
437 | { | |
1985f1cd MA |
438 | std::__uninitialized_copy_a(__first, __last, __new_start, |
439 | this->get_allocator()); | |
03f9ea44 | 440 | this->_M_impl._M_start = __new_start; |
f6592a9e PC |
441 | } |
442 | catch(...) | |
443 | { | |
0d8c9baf PC |
444 | _M_destroy_nodes(__new_start._M_node, |
445 | this->_M_impl._M_start._M_node); | |
f6592a9e PC |
446 | __throw_exception_again; |
447 | } | |
448 | } | |
03f9ea44 | 449 | else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) |
f6592a9e PC |
450 | { |
451 | iterator __new_finish = _M_reserve_elements_at_back(__n); | |
452 | try | |
453 | { | |
1985f1cd MA |
454 | std::__uninitialized_copy_a(__first, __last, |
455 | this->_M_impl._M_finish, | |
456 | this->get_allocator()); | |
03f9ea44 | 457 | this->_M_impl._M_finish = __new_finish; |
f6592a9e PC |
458 | } |
459 | catch(...) | |
460 | { | |
03f9ea44 | 461 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
f6592a9e PC |
462 | __new_finish._M_node + 1); |
463 | __throw_exception_again; | |
464 | } | |
465 | } | |
3971a4d2 PE |
466 | else |
467 | _M_insert_aux(__pos, __first, __last, __n); | |
468 | } | |
ed6814f7 | 469 | |
3971a4d2 PE |
470 | template <typename _Tp, typename _Alloc> |
471 | typename deque<_Tp, _Alloc>::iterator | |
43da93a7 | 472 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
473 | _M_insert_aux(iterator __pos, const value_type& __x) |
474 | { | |
03f9ea44 | 475 | difference_type __index = __pos - this->_M_impl._M_start; |
3971a4d2 PE |
476 | value_type __x_copy = __x; // XXX copy |
477 | if (static_cast<size_type>(__index) < size() / 2) | |
f6592a9e PC |
478 | { |
479 | push_front(front()); | |
03f9ea44 | 480 | iterator __front1 = this->_M_impl._M_start; |
f6592a9e PC |
481 | ++__front1; |
482 | iterator __front2 = __front1; | |
483 | ++__front2; | |
03f9ea44 | 484 | __pos = this->_M_impl._M_start + __index; |
f6592a9e PC |
485 | iterator __pos1 = __pos; |
486 | ++__pos1; | |
487 | std::copy(__front2, __pos1, __front1); | |
488 | } | |
3971a4d2 | 489 | else |
f6592a9e PC |
490 | { |
491 | push_back(back()); | |
03f9ea44 | 492 | iterator __back1 = this->_M_impl._M_finish; |
f6592a9e PC |
493 | --__back1; |
494 | iterator __back2 = __back1; | |
495 | --__back2; | |
03f9ea44 | 496 | __pos = this->_M_impl._M_start + __index; |
f6592a9e PC |
497 | std::copy_backward(__pos, __back2, __back1); |
498 | } | |
3971a4d2 PE |
499 | *__pos = __x_copy; |
500 | return __pos; | |
501 | } | |
ed6814f7 | 502 | |
3971a4d2 | 503 | template <typename _Tp, typename _Alloc> |
83144cfc | 504 | void |
43da93a7 | 505 | deque<_Tp, _Alloc>:: |
3971a4d2 | 506 | _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) |
83144cfc | 507 | { |
03f9ea44 | 508 | const difference_type __elems_before = __pos - this->_M_impl._M_start; |
43da93a7 | 509 | const size_type __length = this->size(); |
3971a4d2 PE |
510 | value_type __x_copy = __x; |
511 | if (__elems_before < difference_type(__length / 2)) | |
f6592a9e PC |
512 | { |
513 | iterator __new_start = _M_reserve_elements_at_front(__n); | |
03f9ea44 DM |
514 | iterator __old_start = this->_M_impl._M_start; |
515 | __pos = this->_M_impl._M_start + __elems_before; | |
f6592a9e PC |
516 | try |
517 | { | |
518 | if (__elems_before >= difference_type(__n)) | |
519 | { | |
0d8c9baf PC |
520 | iterator __start_n = (this->_M_impl._M_start |
521 | + difference_type(__n)); | |
1985f1cd MA |
522 | std::__uninitialized_copy_a(this->_M_impl._M_start, __start_n, |
523 | __new_start, | |
524 | this->get_allocator()); | |
03f9ea44 | 525 | this->_M_impl._M_start = __new_start; |
f6592a9e PC |
526 | std::copy(__start_n, __pos, __old_start); |
527 | fill(__pos - difference_type(__n), __pos, __x_copy); | |
528 | } | |
529 | else | |
530 | { | |
0d8c9baf PC |
531 | std::__uninitialized_copy_fill(this->_M_impl._M_start, |
532 | __pos, __new_start, | |
533 | this->_M_impl._M_start, | |
1985f1cd MA |
534 | __x_copy, |
535 | this->get_allocator()); | |
03f9ea44 | 536 | this->_M_impl._M_start = __new_start; |
f6592a9e PC |
537 | std::fill(__old_start, __pos, __x_copy); |
538 | } | |
539 | } | |
540 | catch(...) | |
ed6814f7 | 541 | { |
0d8c9baf PC |
542 | _M_destroy_nodes(__new_start._M_node, |
543 | this->_M_impl._M_start._M_node); | |
f6592a9e PC |
544 | __throw_exception_again; |
545 | } | |
546 | } | |
83144cfc | 547 | else |
f6592a9e PC |
548 | { |
549 | iterator __new_finish = _M_reserve_elements_at_back(__n); | |
03f9ea44 | 550 | iterator __old_finish = this->_M_impl._M_finish; |
ed6814f7 | 551 | const difference_type __elems_after = |
f6592a9e | 552 | difference_type(__length) - __elems_before; |
03f9ea44 | 553 | __pos = this->_M_impl._M_finish - __elems_after; |
f6592a9e PC |
554 | try |
555 | { | |
556 | if (__elems_after > difference_type(__n)) | |
557 | { | |
0d8c9baf PC |
558 | iterator __finish_n = (this->_M_impl._M_finish |
559 | - difference_type(__n)); | |
1985f1cd MA |
560 | std::__uninitialized_copy_a(__finish_n, this->_M_impl._M_finish, |
561 | this->_M_impl._M_finish, | |
562 | this->get_allocator()); | |
03f9ea44 | 563 | this->_M_impl._M_finish = __new_finish; |
f6592a9e PC |
564 | std::copy_backward(__pos, __finish_n, __old_finish); |
565 | std::fill(__pos, __pos + difference_type(__n), __x_copy); | |
566 | } | |
567 | else | |
568 | { | |
03f9ea44 | 569 | std::__uninitialized_fill_copy(this->_M_impl._M_finish, |
f6592a9e PC |
570 | __pos + difference_type(__n), |
571 | __x_copy, __pos, | |
1985f1cd MA |
572 | this->_M_impl._M_finish, |
573 | this->get_allocator()); | |
03f9ea44 | 574 | this->_M_impl._M_finish = __new_finish; |
f6592a9e PC |
575 | std::fill(__pos, __old_finish, __x_copy); |
576 | } | |
577 | } | |
578 | catch(...) | |
ed6814f7 | 579 | { |
03f9ea44 | 580 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
f6592a9e PC |
581 | __new_finish._M_node + 1); |
582 | __throw_exception_again; | |
583 | } | |
584 | } | |
83144cfc | 585 | } |
ed6814f7 | 586 | |
3971a4d2 PE |
587 | template <typename _Tp, typename _Alloc> |
588 | template <typename _ForwardIterator> | |
589 | void | |
43da93a7 | 590 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
591 | _M_insert_aux(iterator __pos, |
592 | _ForwardIterator __first, _ForwardIterator __last, | |
593 | size_type __n) | |
83144cfc | 594 | { |
03f9ea44 | 595 | const difference_type __elemsbefore = __pos - this->_M_impl._M_start; |
43da93a7 | 596 | const size_type __length = size(); |
3971a4d2 | 597 | if (static_cast<size_type>(__elemsbefore) < __length / 2) |
f6592a9e PC |
598 | { |
599 | iterator __new_start = _M_reserve_elements_at_front(__n); | |
03f9ea44 DM |
600 | iterator __old_start = this->_M_impl._M_start; |
601 | __pos = this->_M_impl._M_start + __elemsbefore; | |
f6592a9e PC |
602 | try |
603 | { | |
604 | if (__elemsbefore >= difference_type(__n)) | |
605 | { | |
0d8c9baf PC |
606 | iterator __start_n = (this->_M_impl._M_start |
607 | + difference_type(__n)); | |
1985f1cd MA |
608 | std::__uninitialized_copy_a(this->_M_impl._M_start, __start_n, |
609 | __new_start, | |
610 | this->get_allocator()); | |
03f9ea44 | 611 | this->_M_impl._M_start = __new_start; |
f6592a9e PC |
612 | std::copy(__start_n, __pos, __old_start); |
613 | std::copy(__first, __last, __pos - difference_type(__n)); | |
614 | } | |
615 | else | |
616 | { | |
617 | _ForwardIterator __mid = __first; | |
618 | std::advance(__mid, difference_type(__n) - __elemsbefore); | |
0d8c9baf PC |
619 | std::__uninitialized_copy_copy(this->_M_impl._M_start, |
620 | __pos, __first, __mid, | |
1985f1cd MA |
621 | __new_start, |
622 | this->get_allocator()); | |
03f9ea44 | 623 | this->_M_impl._M_start = __new_start; |
f6592a9e PC |
624 | std::copy(__mid, __last, __old_start); |
625 | } | |
626 | } | |
627 | catch(...) | |
628 | { | |
0d8c9baf PC |
629 | _M_destroy_nodes(__new_start._M_node, |
630 | this->_M_impl._M_start._M_node); | |
f6592a9e PC |
631 | __throw_exception_again; |
632 | } | |
633 | } | |
3971a4d2 PE |
634 | else |
635 | { | |
636 | iterator __new_finish = _M_reserve_elements_at_back(__n); | |
03f9ea44 | 637 | iterator __old_finish = this->_M_impl._M_finish; |
ed6814f7 | 638 | const difference_type __elemsafter = |
3971a4d2 | 639 | difference_type(__length) - __elemsbefore; |
03f9ea44 | 640 | __pos = this->_M_impl._M_finish - __elemsafter; |
3971a4d2 PE |
641 | try |
642 | { | |
643 | if (__elemsafter > difference_type(__n)) | |
f6592a9e | 644 | { |
0d8c9baf PC |
645 | iterator __finish_n = (this->_M_impl._M_finish |
646 | - difference_type(__n)); | |
1985f1cd MA |
647 | std::__uninitialized_copy_a(__finish_n, |
648 | this->_M_impl._M_finish, | |
649 | this->_M_impl._M_finish, | |
650 | this->get_allocator()); | |
03f9ea44 | 651 | this->_M_impl._M_finish = __new_finish; |
f6592a9e PC |
652 | std::copy_backward(__pos, __finish_n, __old_finish); |
653 | std::copy(__first, __last, __pos); | |
654 | } | |
3971a4d2 | 655 | else |
f6592a9e PC |
656 | { |
657 | _ForwardIterator __mid = __first; | |
658 | std::advance(__mid, __elemsafter); | |
659 | std::__uninitialized_copy_copy(__mid, __last, __pos, | |
03f9ea44 | 660 | this->_M_impl._M_finish, |
1985f1cd MA |
661 | this->_M_impl._M_finish, |
662 | this->get_allocator()); | |
03f9ea44 | 663 | this->_M_impl._M_finish = __new_finish; |
f6592a9e PC |
664 | std::copy(__first, __mid, __pos); |
665 | } | |
3971a4d2 PE |
666 | } |
667 | catch(...) | |
668 | { | |
03f9ea44 | 669 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
8fbc5ae7 | 670 | __new_finish._M_node + 1); |
3971a4d2 PE |
671 | __throw_exception_again; |
672 | } | |
673 | } | |
83144cfc | 674 | } |
ed6814f7 | 675 | |
3971a4d2 PE |
676 | template <typename _Tp, typename _Alloc> |
677 | void | |
43da93a7 | 678 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
679 | _M_new_elements_at_front(size_type __new_elems) |
680 | { | |
43da93a7 | 681 | const size_type __new_nodes |
f6592a9e | 682 | = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); |
3971a4d2 PE |
683 | _M_reserve_map_at_front(__new_nodes); |
684 | size_type __i; | |
685 | try | |
686 | { | |
687 | for (__i = 1; __i <= __new_nodes; ++__i) | |
03f9ea44 | 688 | *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); |
3971a4d2 PE |
689 | } |
690 | catch(...) | |
691 | { | |
692 | for (size_type __j = 1; __j < __i; ++__j) | |
03f9ea44 | 693 | _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); |
3971a4d2 PE |
694 | __throw_exception_again; |
695 | } | |
696 | } | |
ed6814f7 | 697 | |
3971a4d2 PE |
698 | template <typename _Tp, typename _Alloc> |
699 | void | |
43da93a7 | 700 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
701 | _M_new_elements_at_back(size_type __new_elems) |
702 | { | |
43da93a7 PC |
703 | const size_type __new_nodes |
704 | = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); | |
3971a4d2 PE |
705 | _M_reserve_map_at_back(__new_nodes); |
706 | size_type __i; | |
707 | try | |
708 | { | |
709 | for (__i = 1; __i <= __new_nodes; ++__i) | |
03f9ea44 | 710 | *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); |
3971a4d2 PE |
711 | } |
712 | catch(...) | |
713 | { | |
714 | for (size_type __j = 1; __j < __i; ++__j) | |
03f9ea44 | 715 | _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); |
3971a4d2 PE |
716 | __throw_exception_again; |
717 | } | |
718 | } | |
ed6814f7 | 719 | |
3971a4d2 PE |
720 | template <typename _Tp, typename _Alloc> |
721 | void | |
43da93a7 | 722 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
723 | _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) |
724 | { | |
43da93a7 | 725 | const size_type __old_num_nodes |
03f9ea44 | 726 | = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; |
43da93a7 | 727 | const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; |
ed6814f7 | 728 | |
3971a4d2 | 729 | _Map_pointer __new_nstart; |
03f9ea44 | 730 | if (this->_M_impl._M_map_size > 2 * __new_num_nodes) |
f6592a9e | 731 | { |
03f9ea44 | 732 | __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size |
ed6814f7 | 733 | - __new_num_nodes) / 2 |
f6592a9e | 734 | + (__add_at_front ? __nodes_to_add : 0); |
03f9ea44 DM |
735 | if (__new_nstart < this->_M_impl._M_start._M_node) |
736 | std::copy(this->_M_impl._M_start._M_node, | |
737 | this->_M_impl._M_finish._M_node + 1, | |
5b5bf717 | 738 | __new_nstart); |
f6592a9e | 739 | else |
03f9ea44 DM |
740 | std::copy_backward(this->_M_impl._M_start._M_node, |
741 | this->_M_impl._M_finish._M_node + 1, | |
f6592a9e PC |
742 | __new_nstart + __old_num_nodes); |
743 | } | |
3971a4d2 | 744 | else |
f6592a9e | 745 | { |
03f9ea44 DM |
746 | size_type __new_map_size = this->_M_impl._M_map_size |
747 | + std::max(this->_M_impl._M_map_size, | |
f6592a9e | 748 | __nodes_to_add) + 2; |
ed6814f7 | 749 | |
f6592a9e PC |
750 | _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); |
751 | __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 | |
752 | + (__add_at_front ? __nodes_to_add : 0); | |
03f9ea44 DM |
753 | std::copy(this->_M_impl._M_start._M_node, |
754 | this->_M_impl._M_finish._M_node + 1, | |
f6592a9e | 755 | __new_nstart); |
03f9ea44 | 756 | _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); |
ed6814f7 | 757 | |
03f9ea44 DM |
758 | this->_M_impl._M_map = __new_map; |
759 | this->_M_impl._M_map_size = __new_map_size; | |
f6592a9e | 760 | } |
ed6814f7 | 761 | |
03f9ea44 DM |
762 | this->_M_impl._M_start._M_set_node(__new_nstart); |
763 | this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); | |
83144cfc | 764 | } |
390e4c0d | 765 | } // namespace std |
f6592a9e | 766 | |
3d7c150e | 767 | #endif |