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