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