Line data Source code
1 : // Vector implementation (out of line) -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2019 Free Software Foundation, Inc.
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 3, 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 : // Under Section 7 of GPL version 3, you are granted additional
17 : // permissions described in the GCC Runtime Library Exception, version
18 : // 3.1, as published by the Free Software Foundation.
19 :
20 : // You should have received a copy of the GNU General Public License and
21 : // a copy of the GCC Runtime Library Exception along with this program;
22 : // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23 : // <http://www.gnu.org/licenses/>.
24 :
25 : /*
26 : *
27 : * Copyright (c) 1994
28 : * Hewlett-Packard Company
29 : *
30 : * Permission to use, copy, modify, distribute and sell this software
31 : * and its documentation for any purpose is hereby granted without fee,
32 : * provided that the above copyright notice appear in all copies and
33 : * that both that copyright notice and this permission notice appear
34 : * in supporting documentation. Hewlett-Packard Company makes no
35 : * representations about the suitability of this software for any
36 : * purpose. It is provided "as is" without express or implied warranty.
37 : *
38 : *
39 : * Copyright (c) 1996
40 : * Silicon Graphics Computer Systems, Inc.
41 : *
42 : * Permission to use, copy, modify, distribute and sell this software
43 : * and its documentation for any purpose is hereby granted without fee,
44 : * provided that the above copyright notice appear in all copies and
45 : * that both that copyright notice and this permission notice appear
46 : * in supporting documentation. Silicon Graphics makes no
47 : * representations about the suitability of this software for any
48 : * purpose. It is provided "as is" without express or implied warranty.
49 : */
50 :
51 : /** @file bits/vector.tcc
52 : * This is an internal header file, included by other library headers.
53 : * Do not attempt to use it directly. @headername{vector}
54 : */
55 :
56 : #ifndef _VECTOR_TCC
57 : #define _VECTOR_TCC 1
58 :
59 : namespace std _GLIBCXX_VISIBILITY(default)
60 : {
61 : _GLIBCXX_BEGIN_NAMESPACE_VERSION
62 : _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
63 :
64 : template<typename _Tp, typename _Alloc>
65 : void
66 51327506 : vector<_Tp, _Alloc>::
67 : reserve(size_type __n)
68 : {
69 51327506 : if (__n > this->max_size())
70 0 : __throw_length_error(__N("vector::reserve"));
71 51327506 : if (this->capacity() < __n)
72 : {
73 49399012 : const size_type __old_size = size();
74 : pointer __tmp;
75 : #if __cplusplus >= 201103L
76 : if _GLIBCXX17_CONSTEXPR (_S_use_relocate())
77 : {
78 49398300 : __tmp = this->_M_allocate(__n);
79 49398300 : _S_relocate(this->_M_impl._M_start, this->_M_impl._M_finish,
80 49398300 : __tmp, _M_get_Tp_allocator());
81 : }
82 : else
83 : #endif
84 : {
85 712 : __tmp = _M_allocate_and_copy(__n,
86 : _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start),
87 : _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish));
88 712 : std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
89 712 : _M_get_Tp_allocator());
90 : }
91 : _GLIBCXX_ASAN_ANNOTATE_REINIT;
92 98797924 : _M_deallocate(this->_M_impl._M_start,
93 49399012 : this->_M_impl._M_end_of_storage
94 49399012 : - this->_M_impl._M_start);
95 49399012 : this->_M_impl._M_start = __tmp;
96 49399012 : this->_M_impl._M_finish = __tmp + __old_size;
97 49399012 : this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
98 : }
99 51327506 : }
100 :
101 : #if __cplusplus >= 201103L
102 : template<typename _Tp, typename _Alloc>
103 : template<typename... _Args>
104 : #if __cplusplus > 201402L
105 : typename vector<_Tp, _Alloc>::reference
106 : #else
107 : void
108 : #endif
109 3092236200 : vector<_Tp, _Alloc>::
110 : emplace_back(_Args&&... __args)
111 : {
112 3092236200 : if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
113 : {
114 : _GLIBCXX_ASAN_ANNOTATE_GROW(1);
115 2782094383 : _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
116 : std::forward<_Args>(__args)...);
117 2782094383 : ++this->_M_impl._M_finish;
118 : _GLIBCXX_ASAN_ANNOTATE_GREW(1);
119 : }
120 : else
121 310150975 : _M_realloc_insert(end(), std::forward<_Args>(__args)...);
122 : #if __cplusplus > 201402L
123 : return back();
124 : #endif
125 3092236200 : }
126 : #endif
127 :
128 : template<typename _Tp, typename _Alloc>
129 : typename vector<_Tp, _Alloc>::iterator
130 31352 : vector<_Tp, _Alloc>::
131 : #if __cplusplus >= 201103L
132 : insert(const_iterator __position, const value_type& __x)
133 : #else
134 : insert(iterator __position, const value_type& __x)
135 : #endif
136 : {
137 31352 : const size_type __n = __position - begin();
138 31352 : if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
139 2600 : if (__position == end())
140 : {
141 : _GLIBCXX_ASAN_ANNOTATE_GROW(1);
142 2591 : _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
143 : __x);
144 2591 : ++this->_M_impl._M_finish;
145 : _GLIBCXX_ASAN_ANNOTATE_GREW(1);
146 : }
147 : else
148 : {
149 : #if __cplusplus >= 201103L
150 9 : const auto __pos = begin() + (__position - cbegin());
151 : // __x could be an existing element of this vector, so make a
152 : // copy of it before _M_insert_aux moves elements around.
153 9 : _Temporary_value __x_copy(this, __x);
154 9 : _M_insert_aux(__pos, std::move(__x_copy._M_val()));
155 : #else
156 : _M_insert_aux(__position, __x);
157 : #endif
158 : }
159 : else
160 : #if __cplusplus >= 201103L
161 28752 : _M_realloc_insert(begin() + (__position - cbegin()), __x);
162 : #else
163 : _M_realloc_insert(__position, __x);
164 : #endif
165 :
166 31352 : return iterator(this->_M_impl._M_start + __n);
167 : }
168 :
169 : template<typename _Tp, typename _Alloc>
170 : typename vector<_Tp, _Alloc>::iterator
171 5070 : vector<_Tp, _Alloc>::
172 : _M_erase(iterator __position)
173 : {
174 5070 : if (__position + 1 != end())
175 3811 : _GLIBCXX_MOVE3(__position + 1, end(), __position);
176 5070 : --this->_M_impl._M_finish;
177 5070 : _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
178 : _GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
179 5070 : return __position;
180 : }
181 :
182 : template<typename _Tp, typename _Alloc>
183 : typename vector<_Tp, _Alloc>::iterator
184 3529079 : vector<_Tp, _Alloc>::
185 : _M_erase(iterator __first, iterator __last)
186 : {
187 3529079 : if (__first != __last)
188 : {
189 13735 : if (__last != end())
190 1998 : _GLIBCXX_MOVE3(__last, end(), __first);
191 13735 : _M_erase_at_end(__first.base() + (end() - __last));
192 : }
193 3529079 : return __first;
194 : }
195 :
196 : template<typename _Tp, typename _Alloc>
197 : vector<_Tp, _Alloc>&
198 46886508 : vector<_Tp, _Alloc>::
199 : operator=(const vector<_Tp, _Alloc>& __x)
200 : {
201 46886508 : if (&__x != this)
202 : {
203 : _GLIBCXX_ASAN_ANNOTATE_REINIT;
204 : #if __cplusplus >= 201103L
205 : if (_Alloc_traits::_S_propagate_on_copy_assign())
206 : {
207 : if (!_Alloc_traits::_S_always_equal()
208 : && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
209 : {
210 : // replacement allocator cannot free existing storage
211 : this->clear();
212 : _M_deallocate(this->_M_impl._M_start,
213 : this->_M_impl._M_end_of_storage
214 : - this->_M_impl._M_start);
215 : this->_M_impl._M_start = nullptr;
216 : this->_M_impl._M_finish = nullptr;
217 : this->_M_impl._M_end_of_storage = nullptr;
218 : }
219 : std::__alloc_on_copy(_M_get_Tp_allocator(),
220 : __x._M_get_Tp_allocator());
221 : }
222 : #endif
223 46886508 : const size_type __xlen = __x.size();
224 46886508 : if (__xlen > capacity())
225 : {
226 1894434 : pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
227 : __x.end());
228 1894434 : std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
229 1894434 : _M_get_Tp_allocator());
230 3788868 : _M_deallocate(this->_M_impl._M_start,
231 1894434 : this->_M_impl._M_end_of_storage
232 1894434 : - this->_M_impl._M_start);
233 1894434 : this->_M_impl._M_start = __tmp;
234 1894434 : this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
235 : }
236 44992070 : else if (size() >= __xlen)
237 : {
238 45037797 : std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
239 44992905 : end(), _M_get_Tp_allocator());
240 : }
241 : else
242 : {
243 19 : std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
244 : this->_M_impl._M_start);
245 46883970 : std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
246 8 : __x._M_impl._M_finish,
247 : this->_M_impl._M_finish,
248 44 : _M_get_Tp_allocator());
249 : }
250 46886508 : this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
251 : }
252 46886508 : return *this;
253 : }
254 :
255 : template<typename _Tp, typename _Alloc>
256 : void
257 0 : vector<_Tp, _Alloc>::
258 : _M_fill_assign(size_t __n, const value_type& __val)
259 : {
260 0 : if (__n > capacity())
261 : {
262 0 : vector __tmp(__n, __val, _M_get_Tp_allocator());
263 0 : __tmp._M_impl._M_swap_data(this->_M_impl);
264 : }
265 0 : else if (__n > size())
266 : {
267 0 : std::fill(begin(), end(), __val);
268 0 : const size_type __add = __n - size();
269 : _GLIBCXX_ASAN_ANNOTATE_GROW(__add);
270 0 : this->_M_impl._M_finish =
271 0 : std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
272 0 : __add, __val, _M_get_Tp_allocator());
273 : _GLIBCXX_ASAN_ANNOTATE_GREW(__add);
274 : }
275 : else
276 0 : _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
277 0 : }
278 :
279 : template<typename _Tp, typename _Alloc>
280 : template<typename _InputIterator>
281 : void
282 : vector<_Tp, _Alloc>::
283 : _M_assign_aux(_InputIterator __first, _InputIterator __last,
284 : std::input_iterator_tag)
285 : {
286 : pointer __cur(this->_M_impl._M_start);
287 : for (; __first != __last && __cur != this->_M_impl._M_finish;
288 : ++__cur, (void)++__first)
289 : *__cur = *__first;
290 : if (__first == __last)
291 : _M_erase_at_end(__cur);
292 : else
293 : _M_range_insert(end(), __first, __last,
294 : std::__iterator_category(__first));
295 : }
296 :
297 : template<typename _Tp, typename _Alloc>
298 : template<typename _ForwardIterator>
299 : void
300 712 : vector<_Tp, _Alloc>::
301 : _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
302 : std::forward_iterator_tag)
303 : {
304 712 : const size_type __len = std::distance(__first, __last);
305 :
306 712 : if (__len > capacity())
307 : {
308 712 : _S_check_init_len(__len, _M_get_Tp_allocator());
309 712 : pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
310 712 : std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
311 712 : _M_get_Tp_allocator());
312 : _GLIBCXX_ASAN_ANNOTATE_REINIT;
313 1424 : _M_deallocate(this->_M_impl._M_start,
314 712 : this->_M_impl._M_end_of_storage
315 712 : - this->_M_impl._M_start);
316 712 : this->_M_impl._M_start = __tmp;
317 712 : this->_M_impl._M_finish = this->_M_impl._M_start + __len;
318 712 : this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
319 : }
320 0 : else if (size() >= __len)
321 0 : _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
322 : else
323 : {
324 0 : _ForwardIterator __mid = __first;
325 0 : std::advance(__mid, size());
326 0 : std::copy(__first, __mid, this->_M_impl._M_start);
327 0 : const size_type __attribute__((__unused__)) __n = __len - size();
328 : _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
329 0 : this->_M_impl._M_finish =
330 0 : std::__uninitialized_copy_a(__mid, __last,
331 : this->_M_impl._M_finish,
332 0 : _M_get_Tp_allocator());
333 : _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
334 : }
335 712 : }
336 :
337 : #if __cplusplus >= 201103L
338 : template<typename _Tp, typename _Alloc>
339 : auto
340 1283552 : vector<_Tp, _Alloc>::
341 : _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator
342 : {
343 1283552 : const auto __n = __position - cbegin();
344 1283552 : if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
345 1241480 : if (__position == cend())
346 : {
347 : _GLIBCXX_ASAN_ANNOTATE_GROW(1);
348 1240144 : _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
349 1240140 : std::move(__v));
350 1240140 : ++this->_M_impl._M_finish;
351 : _GLIBCXX_ASAN_ANNOTATE_GREW(1);
352 : }
353 : else
354 1336 : _M_insert_aux(begin() + __n, std::move(__v));
355 : else
356 42076 : _M_realloc_insert(begin() + __n, std::move(__v));
357 :
358 1283552 : return iterator(this->_M_impl._M_start + __n);
359 : }
360 :
361 : template<typename _Tp, typename _Alloc>
362 : template<typename... _Args>
363 : auto
364 : vector<_Tp, _Alloc>::
365 : _M_emplace_aux(const_iterator __position, _Args&&... __args)
366 : -> iterator
367 : {
368 : const auto __n = __position - cbegin();
369 : if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
370 : if (__position == cend())
371 : {
372 : _GLIBCXX_ASAN_ANNOTATE_GROW(1);
373 : _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
374 : std::forward<_Args>(__args)...);
375 : ++this->_M_impl._M_finish;
376 : _GLIBCXX_ASAN_ANNOTATE_GREW(1);
377 : }
378 : else
379 : {
380 : // We need to construct a temporary because something in __args...
381 : // could alias one of the elements of the container and so we
382 : // need to use it before _M_insert_aux moves elements around.
383 : _Temporary_value __tmp(this, std::forward<_Args>(__args)...);
384 : _M_insert_aux(begin() + __n, std::move(__tmp._M_val()));
385 : }
386 : else
387 : _M_realloc_insert(begin() + __n, std::forward<_Args>(__args)...);
388 :
389 : return iterator(this->_M_impl._M_start + __n);
390 : }
391 :
392 : template<typename _Tp, typename _Alloc>
393 : template<typename _Arg>
394 : void
395 1345 : vector<_Tp, _Alloc>::
396 : _M_insert_aux(iterator __position, _Arg&& __arg)
397 : #else
398 : template<typename _Tp, typename _Alloc>
399 : void
400 : vector<_Tp, _Alloc>::
401 : _M_insert_aux(iterator __position, const _Tp& __x)
402 : #endif
403 : {
404 : _GLIBCXX_ASAN_ANNOTATE_GROW(1);
405 1345 : _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
406 1345 : _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
407 1345 : ++this->_M_impl._M_finish;
408 : _GLIBCXX_ASAN_ANNOTATE_GREW(1);
409 : #if __cplusplus < 201103L
410 : _Tp __x_copy = __x;
411 : #endif
412 1583 : _GLIBCXX_MOVE_BACKWARD3(__position.base(),
413 : this->_M_impl._M_finish - 2,
414 : this->_M_impl._M_finish - 1);
415 : #if __cplusplus < 201103L
416 : *__position = __x_copy;
417 : #else
418 1345 : *__position = std::forward<_Arg>(__arg);
419 : #endif
420 1345 : }
421 :
422 : #if __cplusplus >= 201103L
423 : template<typename _Tp, typename _Alloc>
424 : template<typename... _Args>
425 : void
426 456074113 : vector<_Tp, _Alloc>::
427 : _M_realloc_insert(iterator __position, _Args&&... __args)
428 : #else
429 : template<typename _Tp, typename _Alloc>
430 : void
431 : vector<_Tp, _Alloc>::
432 : _M_realloc_insert(iterator __position, const _Tp& __x)
433 : #endif
434 : {
435 456074113 : const size_type __len =
436 : _M_check_len(size_type(1), "vector::_M_realloc_insert");
437 456074113 : pointer __old_start = this->_M_impl._M_start;
438 456074113 : pointer __old_finish = this->_M_impl._M_finish;
439 456074113 : const size_type __elems_before = __position - begin();
440 456074113 : pointer __new_start(this->_M_allocate(__len));
441 456074113 : pointer __new_finish(__new_start);
442 : __try
443 : {
444 : // The order of the three operations is dictated by the C++11
445 : // case, where the moves could alter a new element belonging
446 : // to the existing vector. This is an issue only for callers
447 : // taking the element by lvalue ref (see last bullet of C++11
448 : // [res.on.arguments]).
449 736932216 : _Alloc_traits::construct(this->_M_impl,
450 456046886 : __new_start + __elems_before,
451 : #if __cplusplus >= 201103L
452 : std::forward<_Args>(__args)...);
453 : #else
454 : __x);
455 : #endif
456 456275127 : __new_finish = pointer();
457 :
458 : #if __cplusplus >= 201103L
459 : if _GLIBCXX17_CONSTEXPR (_S_use_relocate())
460 : {
461 455605141 : __new_finish = _S_relocate(__old_start, __position.base(),
462 455605141 : __new_start, _M_get_Tp_allocator());
463 :
464 455404127 : ++__new_finish;
465 :
466 455404127 : __new_finish = _S_relocate(__position.base(), __old_finish,
467 455404127 : __new_finish, _M_get_Tp_allocator());
468 : }
469 : else
470 : #endif
471 : {
472 : __new_finish
473 : = std::__uninitialized_move_if_noexcept_a
474 669986 : (__old_start, __position.base(),
475 669986 : __new_start, _M_get_Tp_allocator());
476 :
477 669986 : ++__new_finish;
478 :
479 : __new_finish
480 : = std::__uninitialized_move_if_noexcept_a
481 669986 : (__position.base(), __old_finish,
482 669986 : __new_finish, _M_get_Tp_allocator());
483 : }
484 : }
485 0 : __catch(...)
486 : {
487 0 : if (!__new_finish)
488 0 : _Alloc_traits::destroy(this->_M_impl,
489 : __new_start + __elems_before);
490 : else
491 0 : std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
492 0 : _M_deallocate(__new_start, __len);
493 0 : __throw_exception_again;
494 : }
495 : #if __cplusplus >= 201103L
496 : if _GLIBCXX17_CONSTEXPR (!_S_use_relocate())
497 : #endif
498 719746 : std::_Destroy(__old_start, __old_finish, _M_get_Tp_allocator());
499 : _GLIBCXX_ASAN_ANNOTATE_REINIT;
500 912150192 : _M_deallocate(__old_start,
501 456074113 : this->_M_impl._M_end_of_storage - __old_start);
502 456074113 : this->_M_impl._M_start = __new_start;
503 456074113 : this->_M_impl._M_finish = __new_finish;
504 456074113 : this->_M_impl._M_end_of_storage = __new_start + __len;
505 456074113 : }
506 :
507 : template<typename _Tp, typename _Alloc>
508 : void
509 0 : vector<_Tp, _Alloc>::
510 : _M_fill_insert(iterator __position, size_type __n, const value_type& __x)
511 : {
512 0 : if (__n != 0)
513 : {
514 0 : if (size_type(this->_M_impl._M_end_of_storage
515 0 : - this->_M_impl._M_finish) >= __n)
516 : {
517 : #if __cplusplus < 201103L
518 : value_type __x_copy = __x;
519 : #else
520 0 : _Temporary_value __tmp(this, __x);
521 0 : value_type& __x_copy = __tmp._M_val();
522 : #endif
523 0 : const size_type __elems_after = end() - __position;
524 0 : pointer __old_finish(this->_M_impl._M_finish);
525 0 : if (__elems_after > __n)
526 : {
527 : _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
528 0 : std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
529 : this->_M_impl._M_finish,
530 : this->_M_impl._M_finish,
531 0 : _M_get_Tp_allocator());
532 0 : this->_M_impl._M_finish += __n;
533 : _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
534 0 : _GLIBCXX_MOVE_BACKWARD3(__position.base(),
535 : __old_finish - __n, __old_finish);
536 0 : std::fill(__position.base(), __position.base() + __n,
537 : __x_copy);
538 : }
539 : else
540 : {
541 : _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
542 0 : this->_M_impl._M_finish =
543 0 : std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
544 : __n - __elems_after,
545 : __x_copy,
546 0 : _M_get_Tp_allocator());
547 : _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
548 0 : std::__uninitialized_move_a(__position.base(), __old_finish,
549 : this->_M_impl._M_finish,
550 0 : _M_get_Tp_allocator());
551 0 : this->_M_impl._M_finish += __elems_after;
552 : _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
553 0 : std::fill(__position.base(), __old_finish, __x_copy);
554 : }
555 : }
556 : else
557 : {
558 0 : const size_type __len =
559 : _M_check_len(__n, "vector::_M_fill_insert");
560 0 : const size_type __elems_before = __position - begin();
561 0 : pointer __new_start(this->_M_allocate(__len));
562 0 : pointer __new_finish(__new_start);
563 : __try
564 : {
565 : // See _M_realloc_insert above.
566 0 : std::__uninitialized_fill_n_a(__new_start + __elems_before,
567 : __n, __x,
568 0 : _M_get_Tp_allocator());
569 0 : __new_finish = pointer();
570 :
571 : __new_finish
572 : = std::__uninitialized_move_if_noexcept_a
573 0 : (this->_M_impl._M_start, __position.base(),
574 0 : __new_start, _M_get_Tp_allocator());
575 :
576 0 : __new_finish += __n;
577 :
578 : __new_finish
579 : = std::__uninitialized_move_if_noexcept_a
580 0 : (__position.base(), this->_M_impl._M_finish,
581 0 : __new_finish, _M_get_Tp_allocator());
582 : }
583 0 : __catch(...)
584 : {
585 0 : if (!__new_finish)
586 0 : std::_Destroy(__new_start + __elems_before,
587 0 : __new_start + __elems_before + __n,
588 0 : _M_get_Tp_allocator());
589 : else
590 0 : std::_Destroy(__new_start, __new_finish,
591 0 : _M_get_Tp_allocator());
592 0 : _M_deallocate(__new_start, __len);
593 0 : __throw_exception_again;
594 : }
595 0 : std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
596 0 : _M_get_Tp_allocator());
597 : _GLIBCXX_ASAN_ANNOTATE_REINIT;
598 0 : _M_deallocate(this->_M_impl._M_start,
599 0 : this->_M_impl._M_end_of_storage
600 0 : - this->_M_impl._M_start);
601 0 : this->_M_impl._M_start = __new_start;
602 0 : this->_M_impl._M_finish = __new_finish;
603 0 : this->_M_impl._M_end_of_storage = __new_start + __len;
604 : }
605 : }
606 0 : }
607 :
608 : #if __cplusplus >= 201103L
609 : template<typename _Tp, typename _Alloc>
610 : void
611 955 : vector<_Tp, _Alloc>::
612 : _M_default_append(size_type __n)
613 : {
614 955 : if (__n != 0)
615 : {
616 955 : const size_type __size = size();
617 955 : size_type __navail = size_type(this->_M_impl._M_end_of_storage
618 955 : - this->_M_impl._M_finish);
619 :
620 955 : if (__size > max_size() || __navail > max_size() - __size)
621 0 : __builtin_unreachable();
622 :
623 955 : if (__navail >= __n)
624 : {
625 : _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
626 0 : this->_M_impl._M_finish =
627 0 : std::__uninitialized_default_n_a(this->_M_impl._M_finish,
628 0 : __n, _M_get_Tp_allocator());
629 : _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
630 : }
631 : else
632 : {
633 955 : const size_type __len =
634 : _M_check_len(__n, "vector::_M_default_append");
635 955 : pointer __new_start(this->_M_allocate(__len));
636 : if _GLIBCXX17_CONSTEXPR (_S_use_relocate())
637 : {
638 : __try
639 : {
640 955 : std::__uninitialized_default_n_a(__new_start + __size,
641 955 : __n, _M_get_Tp_allocator());
642 : }
643 : __catch(...)
644 : {
645 : _M_deallocate(__new_start, __len);
646 : __throw_exception_again;
647 : }
648 955 : _S_relocate(this->_M_impl._M_start, this->_M_impl._M_finish,
649 955 : __new_start, _M_get_Tp_allocator());
650 : }
651 : else
652 : {
653 0 : pointer __destroy_from = pointer();
654 : __try
655 : {
656 0 : std::__uninitialized_default_n_a(__new_start + __size,
657 0 : __n, _M_get_Tp_allocator());
658 0 : __destroy_from = __new_start + __size;
659 0 : std::__uninitialized_move_if_noexcept_a(
660 : this->_M_impl._M_start, this->_M_impl._M_finish,
661 0 : __new_start, _M_get_Tp_allocator());
662 : }
663 0 : __catch(...)
664 : {
665 0 : if (__destroy_from)
666 0 : std::_Destroy(__destroy_from, __destroy_from + __n,
667 0 : _M_get_Tp_allocator());
668 0 : _M_deallocate(__new_start, __len);
669 0 : __throw_exception_again;
670 : }
671 0 : std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
672 0 : _M_get_Tp_allocator());
673 : }
674 : _GLIBCXX_ASAN_ANNOTATE_REINIT;
675 1910 : _M_deallocate(this->_M_impl._M_start,
676 955 : this->_M_impl._M_end_of_storage
677 955 : - this->_M_impl._M_start);
678 955 : this->_M_impl._M_start = __new_start;
679 955 : this->_M_impl._M_finish = __new_start + __size + __n;
680 955 : this->_M_impl._M_end_of_storage = __new_start + __len;
681 : }
682 : }
683 955 : }
684 :
685 : template<typename _Tp, typename _Alloc>
686 : bool
687 0 : vector<_Tp, _Alloc>::
688 : _M_shrink_to_fit()
689 : {
690 0 : if (capacity() == size())
691 : return false;
692 : _GLIBCXX_ASAN_ANNOTATE_REINIT;
693 0 : return std::__shrink_to_fit_aux<vector>::_S_do_it(*this);
694 : }
695 : #endif
696 :
697 : template<typename _Tp, typename _Alloc>
698 : template<typename _InputIterator>
699 : void
700 : vector<_Tp, _Alloc>::
701 : _M_range_insert(iterator __pos, _InputIterator __first,
702 : _InputIterator __last, std::input_iterator_tag)
703 : {
704 : if (__pos == end())
705 : {
706 : for (; __first != __last; ++__first)
707 : insert(end(), *__first);
708 : }
709 : else if (__first != __last)
710 : {
711 : vector __tmp(__first, __last, _M_get_Tp_allocator());
712 : insert(__pos,
713 : _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.begin()),
714 : _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.end()));
715 : }
716 : }
717 :
718 : template<typename _Tp, typename _Alloc>
719 : template<typename _ForwardIterator>
720 : void
721 61568395 : vector<_Tp, _Alloc>::
722 : _M_range_insert(iterator __position, _ForwardIterator __first,
723 : _ForwardIterator __last, std::forward_iterator_tag)
724 : {
725 61568395 : if (__first != __last)
726 : {
727 59580991 : const size_type __n = std::distance(__first, __last);
728 59580991 : if (size_type(this->_M_impl._M_end_of_storage
729 59580991 : - this->_M_impl._M_finish) >= __n)
730 : {
731 386405 : const size_type __elems_after = end() - __position;
732 386405 : pointer __old_finish(this->_M_impl._M_finish);
733 386405 : if (__elems_after > __n)
734 : {
735 : _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
736 0 : std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
737 : this->_M_impl._M_finish,
738 : this->_M_impl._M_finish,
739 0 : _M_get_Tp_allocator());
740 0 : this->_M_impl._M_finish += __n;
741 : _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
742 0 : _GLIBCXX_MOVE_BACKWARD3(__position.base(),
743 : __old_finish - __n, __old_finish);
744 355187 : std::copy(__first, __last, __position);
745 : }
746 : else
747 : {
748 386405 : _ForwardIterator __mid = __first;
749 386405 : std::advance(__mid, __elems_after);
750 : _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
751 386405 : std::__uninitialized_copy_a(__mid, __last,
752 : this->_M_impl._M_finish,
753 386405 : _M_get_Tp_allocator());
754 386405 : this->_M_impl._M_finish += __n - __elems_after;
755 : _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
756 386405 : std::__uninitialized_move_a(__position.base(),
757 : __old_finish,
758 : this->_M_impl._M_finish,
759 386405 : _M_get_Tp_allocator());
760 386405 : this->_M_impl._M_finish += __elems_after;
761 : _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
762 739905 : std::copy(__first, __mid, __position);
763 : }
764 : }
765 : else
766 : {
767 59194586 : const size_type __len =
768 : _M_check_len(__n, "vector::_M_range_insert");
769 59194586 : pointer __new_start(this->_M_allocate(__len));
770 59194586 : pointer __new_finish(__new_start);
771 : __try
772 : {
773 : __new_finish
774 : = std::__uninitialized_move_if_noexcept_a
775 59194586 : (this->_M_impl._M_start, __position.base(),
776 59194586 : __new_start, _M_get_Tp_allocator());
777 : __new_finish
778 59194586 : = std::__uninitialized_copy_a(__first, __last,
779 : __new_finish,
780 59197522 : _M_get_Tp_allocator());
781 : __new_finish
782 : = std::__uninitialized_move_if_noexcept_a
783 118385261 : (__position.base(), this->_M_impl._M_finish,
784 59194586 : __new_finish, _M_get_Tp_allocator());
785 : }
786 0 : __catch(...)
787 : {
788 0 : std::_Destroy(__new_start, __new_finish,
789 0 : _M_get_Tp_allocator());
790 0 : _M_deallocate(__new_start, __len);
791 0 : __throw_exception_again;
792 : }
793 59194586 : std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
794 59194586 : _M_get_Tp_allocator());
795 : _GLIBCXX_ASAN_ANNOTATE_REINIT;
796 118388772 : _M_deallocate(this->_M_impl._M_start,
797 59194586 : this->_M_impl._M_end_of_storage
798 59194586 : - this->_M_impl._M_start);
799 59194586 : this->_M_impl._M_start = __new_start;
800 59194586 : this->_M_impl._M_finish = __new_finish;
801 59194586 : this->_M_impl._M_end_of_storage = __new_start + __len;
802 : }
803 : }
804 61568395 : }
805 :
806 :
807 : // vector<bool>
808 : template<typename _Alloc>
809 : void
810 : vector<bool, _Alloc>::
811 : _M_reallocate(size_type __n)
812 : {
813 : _Bit_pointer __q = this->_M_allocate(__n);
814 : iterator __start(std::__addressof(*__q), 0);
815 : iterator __finish(_M_copy_aligned(begin(), end(), __start));
816 : this->_M_deallocate();
817 : this->_M_impl._M_start = __start;
818 : this->_M_impl._M_finish = __finish;
819 : this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
820 : }
821 :
822 : template<typename _Alloc>
823 : void
824 0 : vector<bool, _Alloc>::
825 : _M_fill_insert(iterator __position, size_type __n, bool __x)
826 : {
827 0 : if (__n == 0)
828 : return;
829 0 : if (capacity() - size() >= __n)
830 : {
831 0 : std::copy_backward(__position, end(),
832 : this->_M_impl._M_finish + difference_type(__n));
833 0 : std::fill(__position, __position + difference_type(__n), __x);
834 0 : this->_M_impl._M_finish += difference_type(__n);
835 : }
836 : else
837 : {
838 0 : const size_type __len =
839 : _M_check_len(__n, "vector<bool>::_M_fill_insert");
840 0 : _Bit_pointer __q = this->_M_allocate(__len);
841 0 : iterator __start(std::__addressof(*__q), 0);
842 0 : iterator __i = _M_copy_aligned(begin(), __position, __start);
843 0 : std::fill(__i, __i + difference_type(__n), __x);
844 0 : iterator __finish = std::copy(__position, end(),
845 : __i + difference_type(__n));
846 0 : this->_M_deallocate();
847 0 : this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
848 0 : this->_M_impl._M_start = __start;
849 0 : this->_M_impl._M_finish = __finish;
850 : }
851 : }
852 :
853 : template<typename _Alloc>
854 : template<typename _ForwardIterator>
855 : void
856 : vector<bool, _Alloc>::
857 : _M_insert_range(iterator __position, _ForwardIterator __first,
858 : _ForwardIterator __last, std::forward_iterator_tag)
859 : {
860 : if (__first != __last)
861 : {
862 : size_type __n = std::distance(__first, __last);
863 : if (capacity() - size() >= __n)
864 : {
865 : std::copy_backward(__position, end(),
866 : this->_M_impl._M_finish
867 : + difference_type(__n));
868 : std::copy(__first, __last, __position);
869 : this->_M_impl._M_finish += difference_type(__n);
870 : }
871 : else
872 : {
873 : const size_type __len =
874 : _M_check_len(__n, "vector<bool>::_M_insert_range");
875 : _Bit_pointer __q = this->_M_allocate(__len);
876 : iterator __start(std::__addressof(*__q), 0);
877 : iterator __i = _M_copy_aligned(begin(), __position, __start);
878 : __i = std::copy(__first, __last, __i);
879 : iterator __finish = std::copy(__position, end(), __i);
880 : this->_M_deallocate();
881 : this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
882 : this->_M_impl._M_start = __start;
883 : this->_M_impl._M_finish = __finish;
884 : }
885 : }
886 : }
887 :
888 : template<typename _Alloc>
889 : void
890 1852850 : vector<bool, _Alloc>::
891 : _M_insert_aux(iterator __position, bool __x)
892 : {
893 1852850 : if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
894 : {
895 0 : std::copy_backward(__position, this->_M_impl._M_finish,
896 : this->_M_impl._M_finish + 1);
897 0 : *__position = __x;
898 0 : ++this->_M_impl._M_finish;
899 : }
900 : else
901 : {
902 1852850 : const size_type __len =
903 : _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
904 1852850 : _Bit_pointer __q = this->_M_allocate(__len);
905 1852850 : iterator __start(std::__addressof(*__q), 0);
906 1852850 : iterator __i = _M_copy_aligned(begin(), __position, __start);
907 3705700 : *__i++ = __x;
908 1852850 : iterator __finish = std::copy(__position, end(), __i);
909 1852850 : this->_M_deallocate();
910 1852850 : this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
911 1852850 : this->_M_impl._M_start = __start;
912 1852850 : this->_M_impl._M_finish = __finish;
913 : }
914 1852850 : }
915 :
916 : template<typename _Alloc>
917 : typename vector<bool, _Alloc>::iterator
918 : vector<bool, _Alloc>::
919 : _M_erase(iterator __position)
920 : {
921 : if (__position + 1 != end())
922 : std::copy(__position + 1, end(), __position);
923 : --this->_M_impl._M_finish;
924 : return __position;
925 : }
926 :
927 : template<typename _Alloc>
928 : typename vector<bool, _Alloc>::iterator
929 : vector<bool, _Alloc>::
930 : _M_erase(iterator __first, iterator __last)
931 : {
932 : if (__first != __last)
933 : _M_erase_at_end(std::copy(__last, end(), __first));
934 : return __first;
935 : }
936 :
937 : #if __cplusplus >= 201103L
938 : template<typename _Alloc>
939 : bool
940 : vector<bool, _Alloc>::
941 : _M_shrink_to_fit()
942 : {
943 : if (capacity() - size() < int(_S_word_bit))
944 : return false;
945 : __try
946 : {
947 : _M_reallocate(size());
948 : return true;
949 : }
950 : __catch(...)
951 : { return false; }
952 : }
953 : #endif
954 :
955 : _GLIBCXX_END_NAMESPACE_CONTAINER
956 : _GLIBCXX_END_NAMESPACE_VERSION
957 : } // namespace std
958 :
959 : #if __cplusplus >= 201103L
960 :
961 : namespace std _GLIBCXX_VISIBILITY(default)
962 : {
963 : _GLIBCXX_BEGIN_NAMESPACE_VERSION
964 :
965 : template<typename _Alloc>
966 : size_t
967 : hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>::
968 : operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept
969 : {
970 : size_t __hash = 0;
971 : using _GLIBCXX_STD_C::_S_word_bit;
972 : using _GLIBCXX_STD_C::_Bit_type;
973 :
974 : const size_t __words = __b.size() / _S_word_bit;
975 : if (__words)
976 : {
977 : const size_t __clength = __words * sizeof(_Bit_type);
978 : __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength);
979 : }
980 :
981 : const size_t __extrabits = __b.size() % _S_word_bit;
982 : if (__extrabits)
983 : {
984 : _Bit_type __hiword = *__b._M_impl._M_finish._M_p;
985 : __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits);
986 :
987 : const size_t __clength
988 : = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__;
989 : if (__words)
990 : __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash);
991 : else
992 : __hash = std::_Hash_impl::hash(&__hiword, __clength);
993 : }
994 :
995 : return __hash;
996 : }
997 :
998 : _GLIBCXX_END_NAMESPACE_VERSION
999 : } // namespace std
1000 :
1001 : #endif // C++11
1002 :
1003 : #undef _GLIBCXX_ASAN_ANNOTATE_REINIT
1004 : #undef _GLIBCXX_ASAN_ANNOTATE_GROW
1005 : #undef _GLIBCXX_ASAN_ANNOTATE_GREW
1006 : #undef _GLIBCXX_ASAN_ANNOTATE_SHRINK
1007 :
1008 : #endif /* _VECTOR_TCC */
|
