]>
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 PE |
66 | template <typename _Tp, typename _Alloc> |
67 | deque<_Tp,_Alloc>& | |
68 | deque<_Tp,_Alloc>:: | |
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> |
ed6814f7 | 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> |
ed6814f7 | 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> |
ed6814f7 | 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; | |
149 | std::_Destroy(this->_M_impl._M_start, __new_start); | |
0d8c9baf PC |
150 | _M_destroy_nodes(this->_M_impl._M_start._M_node, |
151 | __new_start._M_node); | |
03f9ea44 | 152 | this->_M_impl._M_start = __new_start; |
f6592a9e PC |
153 | } |
154 | else | |
155 | { | |
03f9ea44 DM |
156 | std::copy(__last, this->_M_impl._M_finish, __first); |
157 | iterator __new_finish = this->_M_impl._M_finish - __n; | |
158 | std::_Destroy(__new_finish, this->_M_impl._M_finish); | |
f6592a9e | 159 | _M_destroy_nodes(__new_finish._M_node + 1, |
03f9ea44 DM |
160 | this->_M_impl._M_finish._M_node + 1); |
161 | this->_M_impl._M_finish = __new_finish; | |
f6592a9e | 162 | } |
03f9ea44 | 163 | return this->_M_impl._M_start + __elems_before; |
f6592a9e | 164 | } |
83144cfc | 165 | } |
ed6814f7 BI |
166 | |
167 | template <typename _Tp, typename _Alloc> | |
83144cfc | 168 | void |
43da93a7 | 169 | deque<_Tp, _Alloc>:: |
3971a4d2 | 170 | clear() |
83144cfc | 171 | { |
03f9ea44 DM |
172 | for (_Map_pointer __node = this->_M_impl._M_start._M_node + 1; |
173 | __node < this->_M_impl._M_finish._M_node; | |
3971a4d2 | 174 | ++__node) |
f6592a9e PC |
175 | { |
176 | std::_Destroy(*__node, *__node + _S_buffer_size()); | |
177 | _M_deallocate_node(*__node); | |
178 | } | |
ed6814f7 | 179 | |
03f9ea44 | 180 | if (this->_M_impl._M_start._M_node != this->_M_impl._M_finish._M_node) |
f6592a9e | 181 | { |
0d8c9baf PC |
182 | std::_Destroy(this->_M_impl._M_start._M_cur, |
183 | this->_M_impl._M_start._M_last); | |
184 | std::_Destroy(this->_M_impl._M_finish._M_first, | |
185 | this->_M_impl._M_finish._M_cur); | |
03f9ea44 | 186 | _M_deallocate_node(this->_M_impl._M_finish._M_first); |
f6592a9e | 187 | } |
3971a4d2 | 188 | else |
0d8c9baf PC |
189 | std::_Destroy(this->_M_impl._M_start._M_cur, |
190 | this->_M_impl._M_finish._M_cur); | |
ed6814f7 | 191 | |
03f9ea44 | 192 | this->_M_impl._M_finish = this->_M_impl._M_start; |
3971a4d2 | 193 | } |
ed6814f7 | 194 | |
3971a4d2 | 195 | template <typename _Tp, class _Alloc> |
08addde6 | 196 | template <typename _InputIterator> |
3971a4d2 | 197 | void |
43da93a7 | 198 | deque<_Tp, _Alloc> |
f6592a9e PC |
199 | ::_M_assign_aux(_InputIterator __first, _InputIterator __last, |
200 | input_iterator_tag) | |
83144cfc | 201 | { |
3971a4d2 | 202 | iterator __cur = begin(); |
43da93a7 | 203 | for (; __first != __last && __cur != end(); ++__cur, ++__first) |
3971a4d2 PE |
204 | *__cur = *__first; |
205 | if (__first == __last) | |
206 | erase(__cur, end()); | |
207 | else | |
208 | insert(end(), __first, __last); | |
83144cfc | 209 | } |
ed6814f7 | 210 | |
3971a4d2 | 211 | template <typename _Tp, typename _Alloc> |
83144cfc | 212 | void |
43da93a7 | 213 | deque<_Tp, _Alloc>:: |
3971a4d2 | 214 | _M_fill_insert(iterator __pos, size_type __n, const value_type& __x) |
83144cfc | 215 | { |
03f9ea44 | 216 | if (__pos._M_cur == this->_M_impl._M_start._M_cur) |
f6592a9e PC |
217 | { |
218 | iterator __new_start = _M_reserve_elements_at_front(__n); | |
219 | try | |
220 | { | |
03f9ea44 DM |
221 | std::uninitialized_fill(__new_start, this->_M_impl._M_start, __x); |
222 | this->_M_impl._M_start = __new_start; | |
f6592a9e PC |
223 | } |
224 | catch(...) | |
225 | { | |
0d8c9baf PC |
226 | _M_destroy_nodes(__new_start._M_node, |
227 | this->_M_impl._M_start._M_node); | |
f6592a9e PC |
228 | __throw_exception_again; |
229 | } | |
230 | } | |
03f9ea44 | 231 | else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) |
f6592a9e PC |
232 | { |
233 | iterator __new_finish = _M_reserve_elements_at_back(__n); | |
234 | try | |
235 | { | |
0d8c9baf PC |
236 | std::uninitialized_fill(this->_M_impl._M_finish, |
237 | __new_finish, __x); | |
03f9ea44 | 238 | this->_M_impl._M_finish = __new_finish; |
f6592a9e PC |
239 | } |
240 | catch(...) | |
241 | { | |
03f9ea44 | 242 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
ed6814f7 | 243 | __new_finish._M_node + 1); |
f6592a9e PC |
244 | __throw_exception_again; |
245 | } | |
246 | } | |
ed6814f7 | 247 | else |
3971a4d2 | 248 | _M_insert_aux(__pos, __n, __x); |
83144cfc | 249 | } |
ed6814f7 | 250 | |
3971a4d2 PE |
251 | template <typename _Tp, typename _Alloc> |
252 | void | |
43da93a7 | 253 | deque<_Tp, _Alloc>:: |
3971a4d2 | 254 | _M_fill_initialize(const value_type& __value) |
83144cfc | 255 | { |
3971a4d2 PE |
256 | _Map_pointer __cur; |
257 | try | |
258 | { | |
03f9ea44 DM |
259 | for (__cur = this->_M_impl._M_start._M_node; |
260 | __cur < this->_M_impl._M_finish._M_node; | |
8fbc5ae7 | 261 | ++__cur) |
5b5bf717 | 262 | std::uninitialized_fill(*__cur, *__cur + _S_buffer_size(), __value); |
03f9ea44 DM |
263 | std::uninitialized_fill(this->_M_impl._M_finish._M_first, |
264 | this->_M_impl._M_finish._M_cur, | |
5b5bf717 | 265 | __value); |
3971a4d2 PE |
266 | } |
267 | catch(...) | |
268 | { | |
03f9ea44 | 269 | std::_Destroy(this->_M_impl._M_start, iterator(*__cur, __cur)); |
3971a4d2 PE |
270 | __throw_exception_again; |
271 | } | |
83144cfc | 272 | } |
ed6814f7 | 273 | |
3971a4d2 PE |
274 | template <typename _Tp, typename _Alloc> |
275 | template <typename _InputIterator> | |
276 | void | |
43da93a7 | 277 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
278 | _M_range_initialize(_InputIterator __first, _InputIterator __last, |
279 | input_iterator_tag) | |
280 | { | |
f2ffecb1 | 281 | this->_M_initialize_map(0); |
3971a4d2 PE |
282 | try |
283 | { | |
43da93a7 | 284 | for (; __first != __last; ++__first) |
3971a4d2 PE |
285 | push_back(*__first); |
286 | } | |
287 | catch(...) | |
288 | { | |
289 | clear(); | |
290 | __throw_exception_again; | |
291 | } | |
292 | } | |
ed6814f7 | 293 | |
3971a4d2 PE |
294 | template <typename _Tp, typename _Alloc> |
295 | template <typename _ForwardIterator> | |
296 | void | |
43da93a7 | 297 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
298 | _M_range_initialize(_ForwardIterator __first, _ForwardIterator __last, |
299 | forward_iterator_tag) | |
300 | { | |
f6592a9e | 301 | const size_type __n = std::distance(__first, __last); |
f2ffecb1 | 302 | this->_M_initialize_map(__n); |
ed6814f7 | 303 | |
3971a4d2 PE |
304 | _Map_pointer __cur_node; |
305 | try | |
306 | { | |
03f9ea44 DM |
307 | for (__cur_node = this->_M_impl._M_start._M_node; |
308 | __cur_node < this->_M_impl._M_finish._M_node; | |
3971a4d2 PE |
309 | ++__cur_node) |
310 | { | |
311 | _ForwardIterator __mid = __first; | |
5b5bf717 PC |
312 | std::advance(__mid, _S_buffer_size()); |
313 | std::uninitialized_copy(__first, __mid, *__cur_node); | |
3971a4d2 PE |
314 | __first = __mid; |
315 | } | |
0d8c9baf PC |
316 | std::uninitialized_copy(__first, __last, |
317 | this->_M_impl._M_finish._M_first); | |
3971a4d2 PE |
318 | } |
319 | catch(...) | |
320 | { | |
0d8c9baf PC |
321 | std::_Destroy(this->_M_impl._M_start, |
322 | iterator(*__cur_node, __cur_node)); | |
3971a4d2 PE |
323 | __throw_exception_again; |
324 | } | |
325 | } | |
ed6814f7 | 326 | |
03f9ea44 | 327 | // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_last - 1. |
3971a4d2 PE |
328 | template <typename _Tp, typename _Alloc> |
329 | void | |
43da93a7 | 330 | deque<_Tp, _Alloc>:: |
3971a4d2 | 331 | _M_push_back_aux(const value_type& __t) |
83144cfc | 332 | { |
3971a4d2 PE |
333 | value_type __t_copy = __t; |
334 | _M_reserve_map_at_back(); | |
03f9ea44 | 335 | *(this->_M_impl._M_finish._M_node + 1) = this->_M_allocate_node(); |
3971a4d2 PE |
336 | try |
337 | { | |
03f9ea44 | 338 | std::_Construct(this->_M_impl._M_finish._M_cur, __t_copy); |
0d8c9baf PC |
339 | this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node |
340 | + 1); | |
03f9ea44 | 341 | this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_first; |
3971a4d2 PE |
342 | } |
343 | catch(...) | |
344 | { | |
03f9ea44 | 345 | _M_deallocate_node(*(this->_M_impl._M_finish._M_node + 1)); |
3971a4d2 PE |
346 | __throw_exception_again; |
347 | } | |
83144cfc | 348 | } |
ed6814f7 | 349 | |
03f9ea44 | 350 | // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_first. |
3971a4d2 PE |
351 | template <typename _Tp, typename _Alloc> |
352 | void | |
43da93a7 | 353 | deque<_Tp, _Alloc>:: |
3971a4d2 | 354 | _M_push_front_aux(const value_type& __t) |
83144cfc | 355 | { |
3971a4d2 PE |
356 | value_type __t_copy = __t; |
357 | _M_reserve_map_at_front(); | |
03f9ea44 | 358 | *(this->_M_impl._M_start._M_node - 1) = this->_M_allocate_node(); |
83144cfc PE |
359 | try |
360 | { | |
0d8c9baf PC |
361 | this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node |
362 | - 1); | |
03f9ea44 DM |
363 | this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_last - 1; |
364 | std::_Construct(this->_M_impl._M_start._M_cur, __t_copy); | |
83144cfc PE |
365 | } |
366 | catch(...) | |
3971a4d2 | 367 | { |
03f9ea44 DM |
368 | ++this->_M_impl._M_start; |
369 | _M_deallocate_node(*(this->_M_impl._M_start._M_node - 1)); | |
83144cfc PE |
370 | __throw_exception_again; |
371 | } | |
ed6814f7 BI |
372 | } |
373 | ||
03f9ea44 | 374 | // Called only if _M_impl._M_finish._M_cur == _M_impl._M_finish._M_first. |
3971a4d2 | 375 | template <typename _Tp, typename _Alloc> |
43da93a7 | 376 | void deque<_Tp, _Alloc>:: |
3971a4d2 PE |
377 | _M_pop_back_aux() |
378 | { | |
03f9ea44 DM |
379 | _M_deallocate_node(this->_M_impl._M_finish._M_first); |
380 | this->_M_impl._M_finish._M_set_node(this->_M_impl._M_finish._M_node - 1); | |
381 | this->_M_impl._M_finish._M_cur = this->_M_impl._M_finish._M_last - 1; | |
382 | std::_Destroy(this->_M_impl._M_finish._M_cur); | |
83144cfc | 383 | } |
ed6814f7 | 384 | |
0d8c9baf PC |
385 | // Called only if _M_impl._M_start._M_cur == _M_impl._M_start._M_last - 1. |
386 | // Note that if the deque has at least one element (a precondition for this | |
387 | // member function), and if | |
388 | // _M_impl._M_start._M_cur == _M_impl._M_start._M_last, | |
389 | // then the deque must have at least two nodes. | |
3971a4d2 | 390 | template <typename _Tp, typename _Alloc> |
43da93a7 | 391 | void deque<_Tp, _Alloc>:: |
3971a4d2 PE |
392 | _M_pop_front_aux() |
393 | { | |
03f9ea44 DM |
394 | std::_Destroy(this->_M_impl._M_start._M_cur); |
395 | _M_deallocate_node(this->_M_impl._M_start._M_first); | |
396 | this->_M_impl._M_start._M_set_node(this->_M_impl._M_start._M_node + 1); | |
397 | this->_M_impl._M_start._M_cur = this->_M_impl._M_start._M_first; | |
ed6814f7 BI |
398 | } |
399 | ||
3971a4d2 PE |
400 | template <typename _Tp, typename _Alloc> |
401 | template <typename _InputIterator> | |
402 | void | |
43da93a7 | 403 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
404 | _M_range_insert_aux(iterator __pos, |
405 | _InputIterator __first, _InputIterator __last, | |
406 | input_iterator_tag) | |
f6592a9e | 407 | { std::copy(__first, __last, std::inserter(*this, __pos)); } |
ed6814f7 | 408 | |
3971a4d2 PE |
409 | template <typename _Tp, typename _Alloc> |
410 | template <typename _ForwardIterator> | |
411 | void | |
43da93a7 | 412 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
413 | _M_range_insert_aux(iterator __pos, |
414 | _ForwardIterator __first, _ForwardIterator __last, | |
415 | forward_iterator_tag) | |
416 | { | |
43da93a7 | 417 | const size_type __n = std::distance(__first, __last); |
03f9ea44 | 418 | if (__pos._M_cur == this->_M_impl._M_start._M_cur) |
f6592a9e PC |
419 | { |
420 | iterator __new_start = _M_reserve_elements_at_front(__n); | |
421 | try | |
422 | { | |
423 | std::uninitialized_copy(__first, __last, __new_start); | |
03f9ea44 | 424 | this->_M_impl._M_start = __new_start; |
f6592a9e PC |
425 | } |
426 | catch(...) | |
427 | { | |
0d8c9baf PC |
428 | _M_destroy_nodes(__new_start._M_node, |
429 | this->_M_impl._M_start._M_node); | |
f6592a9e PC |
430 | __throw_exception_again; |
431 | } | |
432 | } | |
03f9ea44 | 433 | else if (__pos._M_cur == this->_M_impl._M_finish._M_cur) |
f6592a9e PC |
434 | { |
435 | iterator __new_finish = _M_reserve_elements_at_back(__n); | |
436 | try | |
437 | { | |
0d8c9baf PC |
438 | std::uninitialized_copy(__first, __last, |
439 | this->_M_impl._M_finish); | |
03f9ea44 | 440 | this->_M_impl._M_finish = __new_finish; |
f6592a9e PC |
441 | } |
442 | catch(...) | |
443 | { | |
03f9ea44 | 444 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
f6592a9e PC |
445 | __new_finish._M_node + 1); |
446 | __throw_exception_again; | |
447 | } | |
448 | } | |
3971a4d2 PE |
449 | else |
450 | _M_insert_aux(__pos, __first, __last, __n); | |
451 | } | |
ed6814f7 | 452 | |
3971a4d2 PE |
453 | template <typename _Tp, typename _Alloc> |
454 | typename deque<_Tp, _Alloc>::iterator | |
43da93a7 | 455 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
456 | _M_insert_aux(iterator __pos, const value_type& __x) |
457 | { | |
03f9ea44 | 458 | difference_type __index = __pos - this->_M_impl._M_start; |
3971a4d2 PE |
459 | value_type __x_copy = __x; // XXX copy |
460 | if (static_cast<size_type>(__index) < size() / 2) | |
f6592a9e PC |
461 | { |
462 | push_front(front()); | |
03f9ea44 | 463 | iterator __front1 = this->_M_impl._M_start; |
f6592a9e PC |
464 | ++__front1; |
465 | iterator __front2 = __front1; | |
466 | ++__front2; | |
03f9ea44 | 467 | __pos = this->_M_impl._M_start + __index; |
f6592a9e PC |
468 | iterator __pos1 = __pos; |
469 | ++__pos1; | |
470 | std::copy(__front2, __pos1, __front1); | |
471 | } | |
3971a4d2 | 472 | else |
f6592a9e PC |
473 | { |
474 | push_back(back()); | |
03f9ea44 | 475 | iterator __back1 = this->_M_impl._M_finish; |
f6592a9e PC |
476 | --__back1; |
477 | iterator __back2 = __back1; | |
478 | --__back2; | |
03f9ea44 | 479 | __pos = this->_M_impl._M_start + __index; |
f6592a9e PC |
480 | std::copy_backward(__pos, __back2, __back1); |
481 | } | |
3971a4d2 PE |
482 | *__pos = __x_copy; |
483 | return __pos; | |
484 | } | |
ed6814f7 | 485 | |
3971a4d2 | 486 | template <typename _Tp, typename _Alloc> |
83144cfc | 487 | void |
43da93a7 | 488 | deque<_Tp, _Alloc>:: |
3971a4d2 | 489 | _M_insert_aux(iterator __pos, size_type __n, const value_type& __x) |
83144cfc | 490 | { |
03f9ea44 | 491 | const difference_type __elems_before = __pos - this->_M_impl._M_start; |
43da93a7 | 492 | const size_type __length = this->size(); |
3971a4d2 PE |
493 | value_type __x_copy = __x; |
494 | if (__elems_before < difference_type(__length / 2)) | |
f6592a9e PC |
495 | { |
496 | iterator __new_start = _M_reserve_elements_at_front(__n); | |
03f9ea44 DM |
497 | iterator __old_start = this->_M_impl._M_start; |
498 | __pos = this->_M_impl._M_start + __elems_before; | |
f6592a9e PC |
499 | try |
500 | { | |
501 | if (__elems_before >= difference_type(__n)) | |
502 | { | |
0d8c9baf PC |
503 | iterator __start_n = (this->_M_impl._M_start |
504 | + difference_type(__n)); | |
03f9ea44 | 505 | std::uninitialized_copy(this->_M_impl._M_start, __start_n, |
f6592a9e | 506 | __new_start); |
03f9ea44 | 507 | this->_M_impl._M_start = __new_start; |
f6592a9e PC |
508 | std::copy(__start_n, __pos, __old_start); |
509 | fill(__pos - difference_type(__n), __pos, __x_copy); | |
510 | } | |
511 | else | |
512 | { | |
0d8c9baf PC |
513 | std::__uninitialized_copy_fill(this->_M_impl._M_start, |
514 | __pos, __new_start, | |
515 | this->_M_impl._M_start, | |
516 | __x_copy); | |
03f9ea44 | 517 | this->_M_impl._M_start = __new_start; |
f6592a9e PC |
518 | std::fill(__old_start, __pos, __x_copy); |
519 | } | |
520 | } | |
521 | catch(...) | |
ed6814f7 | 522 | { |
0d8c9baf PC |
523 | _M_destroy_nodes(__new_start._M_node, |
524 | this->_M_impl._M_start._M_node); | |
f6592a9e PC |
525 | __throw_exception_again; |
526 | } | |
527 | } | |
83144cfc | 528 | else |
f6592a9e PC |
529 | { |
530 | iterator __new_finish = _M_reserve_elements_at_back(__n); | |
03f9ea44 | 531 | iterator __old_finish = this->_M_impl._M_finish; |
ed6814f7 | 532 | const difference_type __elems_after = |
f6592a9e | 533 | difference_type(__length) - __elems_before; |
03f9ea44 | 534 | __pos = this->_M_impl._M_finish - __elems_after; |
f6592a9e PC |
535 | try |
536 | { | |
537 | if (__elems_after > difference_type(__n)) | |
538 | { | |
0d8c9baf PC |
539 | iterator __finish_n = (this->_M_impl._M_finish |
540 | - difference_type(__n)); | |
03f9ea44 DM |
541 | std::uninitialized_copy(__finish_n, this->_M_impl._M_finish, |
542 | this->_M_impl._M_finish); | |
543 | this->_M_impl._M_finish = __new_finish; | |
f6592a9e PC |
544 | std::copy_backward(__pos, __finish_n, __old_finish); |
545 | std::fill(__pos, __pos + difference_type(__n), __x_copy); | |
546 | } | |
547 | else | |
548 | { | |
03f9ea44 | 549 | std::__uninitialized_fill_copy(this->_M_impl._M_finish, |
f6592a9e PC |
550 | __pos + difference_type(__n), |
551 | __x_copy, __pos, | |
03f9ea44 DM |
552 | this->_M_impl._M_finish); |
553 | this->_M_impl._M_finish = __new_finish; | |
f6592a9e PC |
554 | std::fill(__pos, __old_finish, __x_copy); |
555 | } | |
556 | } | |
557 | catch(...) | |
ed6814f7 | 558 | { |
03f9ea44 | 559 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
f6592a9e PC |
560 | __new_finish._M_node + 1); |
561 | __throw_exception_again; | |
562 | } | |
563 | } | |
83144cfc | 564 | } |
ed6814f7 | 565 | |
3971a4d2 PE |
566 | template <typename _Tp, typename _Alloc> |
567 | template <typename _ForwardIterator> | |
568 | void | |
43da93a7 | 569 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
570 | _M_insert_aux(iterator __pos, |
571 | _ForwardIterator __first, _ForwardIterator __last, | |
572 | size_type __n) | |
83144cfc | 573 | { |
03f9ea44 | 574 | const difference_type __elemsbefore = __pos - this->_M_impl._M_start; |
43da93a7 | 575 | const size_type __length = size(); |
3971a4d2 | 576 | if (static_cast<size_type>(__elemsbefore) < __length / 2) |
f6592a9e PC |
577 | { |
578 | iterator __new_start = _M_reserve_elements_at_front(__n); | |
03f9ea44 DM |
579 | iterator __old_start = this->_M_impl._M_start; |
580 | __pos = this->_M_impl._M_start + __elemsbefore; | |
f6592a9e PC |
581 | try |
582 | { | |
583 | if (__elemsbefore >= difference_type(__n)) | |
584 | { | |
0d8c9baf PC |
585 | iterator __start_n = (this->_M_impl._M_start |
586 | + difference_type(__n)); | |
03f9ea44 | 587 | std::uninitialized_copy(this->_M_impl._M_start, __start_n, |
f6592a9e | 588 | __new_start); |
03f9ea44 | 589 | this->_M_impl._M_start = __new_start; |
f6592a9e PC |
590 | std::copy(__start_n, __pos, __old_start); |
591 | std::copy(__first, __last, __pos - difference_type(__n)); | |
592 | } | |
593 | else | |
594 | { | |
595 | _ForwardIterator __mid = __first; | |
596 | std::advance(__mid, difference_type(__n) - __elemsbefore); | |
0d8c9baf PC |
597 | std::__uninitialized_copy_copy(this->_M_impl._M_start, |
598 | __pos, __first, __mid, | |
599 | __new_start); | |
03f9ea44 | 600 | this->_M_impl._M_start = __new_start; |
f6592a9e PC |
601 | std::copy(__mid, __last, __old_start); |
602 | } | |
603 | } | |
604 | catch(...) | |
605 | { | |
0d8c9baf PC |
606 | _M_destroy_nodes(__new_start._M_node, |
607 | this->_M_impl._M_start._M_node); | |
f6592a9e PC |
608 | __throw_exception_again; |
609 | } | |
610 | } | |
3971a4d2 PE |
611 | else |
612 | { | |
613 | iterator __new_finish = _M_reserve_elements_at_back(__n); | |
03f9ea44 | 614 | iterator __old_finish = this->_M_impl._M_finish; |
ed6814f7 | 615 | const difference_type __elemsafter = |
3971a4d2 | 616 | difference_type(__length) - __elemsbefore; |
03f9ea44 | 617 | __pos = this->_M_impl._M_finish - __elemsafter; |
3971a4d2 PE |
618 | try |
619 | { | |
620 | if (__elemsafter > difference_type(__n)) | |
f6592a9e | 621 | { |
0d8c9baf PC |
622 | iterator __finish_n = (this->_M_impl._M_finish |
623 | - difference_type(__n)); | |
f6592a9e | 624 | std::uninitialized_copy(__finish_n, |
03f9ea44 DM |
625 | this->_M_impl._M_finish, |
626 | this->_M_impl._M_finish); | |
627 | this->_M_impl._M_finish = __new_finish; | |
f6592a9e PC |
628 | std::copy_backward(__pos, __finish_n, __old_finish); |
629 | std::copy(__first, __last, __pos); | |
630 | } | |
3971a4d2 | 631 | else |
f6592a9e PC |
632 | { |
633 | _ForwardIterator __mid = __first; | |
634 | std::advance(__mid, __elemsafter); | |
635 | std::__uninitialized_copy_copy(__mid, __last, __pos, | |
03f9ea44 DM |
636 | this->_M_impl._M_finish, |
637 | this->_M_impl._M_finish); | |
638 | this->_M_impl._M_finish = __new_finish; | |
f6592a9e PC |
639 | std::copy(__first, __mid, __pos); |
640 | } | |
3971a4d2 PE |
641 | } |
642 | catch(...) | |
643 | { | |
03f9ea44 | 644 | _M_destroy_nodes(this->_M_impl._M_finish._M_node + 1, |
8fbc5ae7 | 645 | __new_finish._M_node + 1); |
3971a4d2 PE |
646 | __throw_exception_again; |
647 | } | |
648 | } | |
83144cfc | 649 | } |
ed6814f7 | 650 | |
3971a4d2 PE |
651 | template <typename _Tp, typename _Alloc> |
652 | void | |
43da93a7 | 653 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
654 | _M_new_elements_at_front(size_type __new_elems) |
655 | { | |
43da93a7 | 656 | const size_type __new_nodes |
f6592a9e | 657 | = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); |
3971a4d2 PE |
658 | _M_reserve_map_at_front(__new_nodes); |
659 | size_type __i; | |
660 | try | |
661 | { | |
662 | for (__i = 1; __i <= __new_nodes; ++__i) | |
03f9ea44 | 663 | *(this->_M_impl._M_start._M_node - __i) = this->_M_allocate_node(); |
3971a4d2 PE |
664 | } |
665 | catch(...) | |
666 | { | |
667 | for (size_type __j = 1; __j < __i; ++__j) | |
03f9ea44 | 668 | _M_deallocate_node(*(this->_M_impl._M_start._M_node - __j)); |
3971a4d2 PE |
669 | __throw_exception_again; |
670 | } | |
671 | } | |
ed6814f7 | 672 | |
3971a4d2 PE |
673 | template <typename _Tp, typename _Alloc> |
674 | void | |
43da93a7 | 675 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
676 | _M_new_elements_at_back(size_type __new_elems) |
677 | { | |
43da93a7 PC |
678 | const size_type __new_nodes |
679 | = (__new_elems + _S_buffer_size() - 1) / _S_buffer_size(); | |
3971a4d2 PE |
680 | _M_reserve_map_at_back(__new_nodes); |
681 | size_type __i; | |
682 | try | |
683 | { | |
684 | for (__i = 1; __i <= __new_nodes; ++__i) | |
03f9ea44 | 685 | *(this->_M_impl._M_finish._M_node + __i) = this->_M_allocate_node(); |
3971a4d2 PE |
686 | } |
687 | catch(...) | |
688 | { | |
689 | for (size_type __j = 1; __j < __i; ++__j) | |
03f9ea44 | 690 | _M_deallocate_node(*(this->_M_impl._M_finish._M_node + __j)); |
3971a4d2 PE |
691 | __throw_exception_again; |
692 | } | |
693 | } | |
ed6814f7 | 694 | |
3971a4d2 PE |
695 | template <typename _Tp, typename _Alloc> |
696 | void | |
43da93a7 | 697 | deque<_Tp, _Alloc>:: |
3971a4d2 PE |
698 | _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front) |
699 | { | |
43da93a7 | 700 | const size_type __old_num_nodes |
03f9ea44 | 701 | = this->_M_impl._M_finish._M_node - this->_M_impl._M_start._M_node + 1; |
43da93a7 | 702 | const size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; |
ed6814f7 | 703 | |
3971a4d2 | 704 | _Map_pointer __new_nstart; |
03f9ea44 | 705 | if (this->_M_impl._M_map_size > 2 * __new_num_nodes) |
f6592a9e | 706 | { |
03f9ea44 | 707 | __new_nstart = this->_M_impl._M_map + (this->_M_impl._M_map_size |
ed6814f7 | 708 | - __new_num_nodes) / 2 |
f6592a9e | 709 | + (__add_at_front ? __nodes_to_add : 0); |
03f9ea44 DM |
710 | if (__new_nstart < this->_M_impl._M_start._M_node) |
711 | std::copy(this->_M_impl._M_start._M_node, | |
712 | this->_M_impl._M_finish._M_node + 1, | |
5b5bf717 | 713 | __new_nstart); |
f6592a9e | 714 | else |
03f9ea44 DM |
715 | std::copy_backward(this->_M_impl._M_start._M_node, |
716 | this->_M_impl._M_finish._M_node + 1, | |
f6592a9e PC |
717 | __new_nstart + __old_num_nodes); |
718 | } | |
3971a4d2 | 719 | else |
f6592a9e | 720 | { |
03f9ea44 DM |
721 | size_type __new_map_size = this->_M_impl._M_map_size |
722 | + std::max(this->_M_impl._M_map_size, | |
f6592a9e | 723 | __nodes_to_add) + 2; |
ed6814f7 | 724 | |
f6592a9e PC |
725 | _Map_pointer __new_map = this->_M_allocate_map(__new_map_size); |
726 | __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 | |
727 | + (__add_at_front ? __nodes_to_add : 0); | |
03f9ea44 DM |
728 | std::copy(this->_M_impl._M_start._M_node, |
729 | this->_M_impl._M_finish._M_node + 1, | |
f6592a9e | 730 | __new_nstart); |
03f9ea44 | 731 | _M_deallocate_map(this->_M_impl._M_map, this->_M_impl._M_map_size); |
ed6814f7 | 732 | |
03f9ea44 DM |
733 | this->_M_impl._M_map = __new_map; |
734 | this->_M_impl._M_map_size = __new_map_size; | |
f6592a9e | 735 | } |
ed6814f7 | 736 | |
03f9ea44 DM |
737 | this->_M_impl._M_start._M_set_node(__new_nstart); |
738 | this->_M_impl._M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); | |
83144cfc | 739 | } |
390e4c0d | 740 | } // namespace std |
f6592a9e | 741 | |
3d7c150e | 742 | #endif |