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