]>
Commit | Line | Data |
---|---|---|
83144cfc PE |
1 | // Vector implementation (out of line) -*- C++ -*- |
2 | ||
a945c346 | 3 | // Copyright (C) 2001-2024 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 | |
748086b7 | 8 | // Free Software Foundation; either version 3, or (at your option) |
83144cfc PE |
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 | ||
748086b7 JJ |
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. | |
83144cfc | 19 | |
748086b7 JJ |
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/>. | |
83144cfc PE |
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 | ||
f910786b | 51 | /** @file bits/vector.tcc |
83144cfc | 52 | * This is an internal header file, included by other library headers. |
f910786b | 53 | * Do not attempt to use it directly. @headername{vector} |
83144cfc PE |
54 | */ |
55 | ||
3d7c150e BK |
56 | #ifndef _VECTOR_TCC |
57 | #define _VECTOR_TCC 1 | |
83144cfc | 58 | |
12ffa228 BK |
59 | namespace std _GLIBCXX_VISIBILITY(default) |
60 | { | |
4a15d842 | 61 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
12ffa228 | 62 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |
3cbc7af0 | 63 | |
af5fb6ab | 64 | template<typename _Tp, typename _Alloc> |
1ae8edf5 | 65 | _GLIBCXX20_CONSTEXPR |
3971a4d2 | 66 | void |
874e7baa | 67 | vector<_Tp, _Alloc>:: |
3971a4d2 | 68 | reserve(size_type __n) |
83144cfc | 69 | { |
48d1c3c5 | 70 | if (__n > this->max_size()) |
ba9119ec | 71 | __throw_length_error(__N("vector::reserve")); |
48d1c3c5 BK |
72 | if (this->capacity() < __n) |
73 | { | |
74 | const size_type __old_size = size(); | |
0f317ef7 MG |
75 | pointer __tmp; |
76 | #if __cplusplus >= 201103L | |
27812872 | 77 | if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) |
0f317ef7 MG |
78 | { |
79 | __tmp = this->_M_allocate(__n); | |
258bd1d6 JW |
80 | _S_relocate(this->_M_impl._M_start, this->_M_impl._M_finish, |
81 | __tmp, _M_get_Tp_allocator()); | |
0f317ef7 MG |
82 | } |
83 | else | |
84 | #endif | |
85 | { | |
86 | __tmp = _M_allocate_and_copy(__n, | |
87 | _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start), | |
88 | _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish)); | |
89 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, | |
90 | _M_get_Tp_allocator()); | |
91 | } | |
8c7331c5 | 92 | _GLIBCXX_ASAN_ANNOTATE_REINIT; |
03f9ea44 | 93 | _M_deallocate(this->_M_impl._M_start, |
874e7baa PC |
94 | this->_M_impl._M_end_of_storage |
95 | - this->_M_impl._M_start); | |
03f9ea44 DM |
96 | this->_M_impl._M_start = __tmp; |
97 | this->_M_impl._M_finish = __tmp + __old_size; | |
98 | this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n; | |
48d1c3c5 | 99 | } |
3971a4d2 | 100 | } |
ed6814f7 | 101 | |
734f5023 | 102 | #if __cplusplus >= 201103L |
4dc3e453 PC |
103 | template<typename _Tp, typename _Alloc> |
104 | template<typename... _Args> | |
594ef205 | 105 | #if __cplusplus > 201402L |
1ae8edf5 | 106 | _GLIBCXX20_CONSTEXPR |
594ef205 JW |
107 | typename vector<_Tp, _Alloc>::reference |
108 | #else | |
4dc3e453 | 109 | void |
594ef205 | 110 | #endif |
4dc3e453 PC |
111 | vector<_Tp, _Alloc>:: |
112 | emplace_back(_Args&&... __args) | |
113 | { | |
114 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) | |
115 | { | |
8c7331c5 | 116 | _GLIBCXX_ASAN_ANNOTATE_GROW(1); |
bd8485dc JW |
117 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, |
118 | std::forward<_Args>(__args)...); | |
4dc3e453 | 119 | ++this->_M_impl._M_finish; |
8c7331c5 | 120 | _GLIBCXX_ASAN_ANNOTATE_GREW(1); |
4dc3e453 PC |
121 | } |
122 | else | |
1d82fc2e | 123 | _M_realloc_append(std::forward<_Args>(__args)...); |
594ef205 JW |
124 | #if __cplusplus > 201402L |
125 | return back(); | |
126 | #endif | |
4dc3e453 PC |
127 | } |
128 | #endif | |
129 | ||
af5fb6ab | 130 | template<typename _Tp, typename _Alloc> |
1ae8edf5 | 131 | _GLIBCXX20_CONSTEXPR |
874e7baa PC |
132 | typename vector<_Tp, _Alloc>::iterator |
133 | vector<_Tp, _Alloc>:: | |
7b61c5a9 PC |
134 | #if __cplusplus >= 201103L |
135 | insert(const_iterator __position, const value_type& __x) | |
136 | #else | |
3971a4d2 | 137 | insert(iterator __position, const value_type& __x) |
7b61c5a9 | 138 | #endif |
3971a4d2 | 139 | { |
43da93a7 | 140 | const size_type __n = __position - begin(); |
76225d2c | 141 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) |
4ba94abf JW |
142 | { |
143 | __glibcxx_assert(__position != const_iterator()); | |
144 | if (!(__position != const_iterator())) | |
145 | __builtin_unreachable(); // PR 106434 | |
146 | ||
147 | if (__position == end()) | |
148 | { | |
149 | _GLIBCXX_ASAN_ANNOTATE_GROW(1); | |
150 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, | |
151 | __x); | |
152 | ++this->_M_impl._M_finish; | |
153 | _GLIBCXX_ASAN_ANNOTATE_GREW(1); | |
154 | } | |
155 | else | |
156 | { | |
734f5023 | 157 | #if __cplusplus >= 201103L |
4ba94abf JW |
158 | const auto __pos = begin() + (__position - cbegin()); |
159 | // __x could be an existing element of this vector, so make a | |
160 | // copy of it before _M_insert_aux moves elements around. | |
161 | _Temporary_value __x_copy(this, __x); | |
162 | _M_insert_aux(__pos, std::move(__x_copy._M_val())); | |
bbf264c9 | 163 | #else |
4ba94abf | 164 | _M_insert_aux(__position, __x); |
812e8c79 | 165 | #endif |
4ba94abf JW |
166 | } |
167 | } | |
76225d2c FD |
168 | else |
169 | #if __cplusplus >= 201103L | |
170 | _M_realloc_insert(begin() + (__position - cbegin()), __x); | |
171 | #else | |
172 | _M_realloc_insert(__position, __x); | |
173 | #endif | |
174 | ||
bc9053ab | 175 | return iterator(this->_M_impl._M_start + __n); |
83144cfc | 176 | } |
ed6814f7 | 177 | |
af5fb6ab | 178 | template<typename _Tp, typename _Alloc> |
1ae8edf5 | 179 | _GLIBCXX20_CONSTEXPR |
874e7baa PC |
180 | typename vector<_Tp, _Alloc>::iterator |
181 | vector<_Tp, _Alloc>:: | |
94938aec | 182 | _M_erase(iterator __position) |
83144cfc | 183 | { |
3971a4d2 | 184 | if (__position + 1 != end()) |
245a5fe5 | 185 | _GLIBCXX_MOVE3(__position + 1, end(), __position); |
03f9ea44 | 186 | --this->_M_impl._M_finish; |
bd8485dc | 187 | _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish); |
8c7331c5 | 188 | _GLIBCXX_ASAN_ANNOTATE_SHRINK(1); |
3971a4d2 | 189 | return __position; |
83144cfc | 190 | } |
ed6814f7 | 191 | |
af5fb6ab | 192 | template<typename _Tp, typename _Alloc> |
1ae8edf5 | 193 | _GLIBCXX20_CONSTEXPR |
874e7baa PC |
194 | typename vector<_Tp, _Alloc>::iterator |
195 | vector<_Tp, _Alloc>:: | |
94938aec | 196 | _M_erase(iterator __first, iterator __last) |
83144cfc | 197 | { |
a7cee01d PC |
198 | if (__first != __last) |
199 | { | |
200 | if (__last != end()) | |
201 | _GLIBCXX_MOVE3(__last, end(), __first); | |
202 | _M_erase_at_end(__first.base() + (end() - __last)); | |
203 | } | |
3971a4d2 | 204 | return __first; |
83144cfc | 205 | } |
ed6814f7 | 206 | |
af5fb6ab | 207 | template<typename _Tp, typename _Alloc> |
1ae8edf5 | 208 | _GLIBCXX20_CONSTEXPR |
874e7baa PC |
209 | vector<_Tp, _Alloc>& |
210 | vector<_Tp, _Alloc>:: | |
211 | operator=(const vector<_Tp, _Alloc>& __x) | |
83144cfc | 212 | { |
47915ef8 | 213 | if (std::__addressof(__x) != this) |
874e7baa | 214 | { |
8c7331c5 | 215 | _GLIBCXX_ASAN_ANNOTATE_REINIT; |
734f5023 | 216 | #if __cplusplus >= 201103L |
bd8485dc JW |
217 | if (_Alloc_traits::_S_propagate_on_copy_assign()) |
218 | { | |
219 | if (!_Alloc_traits::_S_always_equal() | |
220 | && _M_get_Tp_allocator() != __x._M_get_Tp_allocator()) | |
221 | { | |
222 | // replacement allocator cannot free existing storage | |
223 | this->clear(); | |
224 | _M_deallocate(this->_M_impl._M_start, | |
225 | this->_M_impl._M_end_of_storage | |
226 | - this->_M_impl._M_start); | |
68d047cb FD |
227 | this->_M_impl._M_start = nullptr; |
228 | this->_M_impl._M_finish = nullptr; | |
229 | this->_M_impl._M_end_of_storage = nullptr; | |
bd8485dc JW |
230 | } |
231 | std::__alloc_on_copy(_M_get_Tp_allocator(), | |
232 | __x._M_get_Tp_allocator()); | |
233 | } | |
234 | #endif | |
874e7baa PC |
235 | const size_type __xlen = __x.size(); |
236 | if (__xlen > capacity()) | |
237 | { | |
238 | pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), | |
239 | __x.end()); | |
1985f1cd | 240 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
4fd20a8f | 241 | _M_get_Tp_allocator()); |
874e7baa PC |
242 | _M_deallocate(this->_M_impl._M_start, |
243 | this->_M_impl._M_end_of_storage | |
244 | - this->_M_impl._M_start); | |
245 | this->_M_impl._M_start = __tmp; | |
246 | this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen; | |
247 | } | |
248 | else if (size() >= __xlen) | |
249 | { | |
bc9053ab PC |
250 | std::_Destroy(std::copy(__x.begin(), __x.end(), begin()), |
251 | end(), _M_get_Tp_allocator()); | |
874e7baa PC |
252 | } |
253 | else | |
254 | { | |
bc9053ab | 255 | std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(), |
874e7baa | 256 | this->_M_impl._M_start); |
bc9053ab PC |
257 | std::__uninitialized_copy_a(__x._M_impl._M_start + size(), |
258 | __x._M_impl._M_finish, | |
259 | this->_M_impl._M_finish, | |
4fd20a8f | 260 | _M_get_Tp_allocator()); |
874e7baa PC |
261 | } |
262 | this->_M_impl._M_finish = this->_M_impl._M_start + __xlen; | |
263 | } | |
3971a4d2 | 264 | return *this; |
83144cfc | 265 | } |
ed6814f7 | 266 | |
af5fb6ab | 267 | template<typename _Tp, typename _Alloc> |
1ae8edf5 | 268 | _GLIBCXX20_CONSTEXPR |
3971a4d2 | 269 | void |
874e7baa | 270 | vector<_Tp, _Alloc>:: |
3971a4d2 | 271 | _M_fill_assign(size_t __n, const value_type& __val) |
83144cfc | 272 | { |
b7b255e7 | 273 | const size_type __sz = size(); |
3971a4d2 | 274 | if (__n > capacity()) |
874e7baa | 275 | { |
b7b255e7 JW |
276 | if (__n <= __sz) |
277 | __builtin_unreachable(); | |
4fd20a8f | 278 | vector __tmp(__n, __val, _M_get_Tp_allocator()); |
c5b26147 | 279 | __tmp._M_impl._M_swap_data(this->_M_impl); |
874e7baa | 280 | } |
b7b255e7 | 281 | else if (__n > __sz) |
874e7baa PC |
282 | { |
283 | std::fill(begin(), end(), __val); | |
b7b255e7 | 284 | const size_type __add = __n - __sz; |
8c7331c5 | 285 | _GLIBCXX_ASAN_ANNOTATE_GROW(__add); |
e51cf2f5 JW |
286 | this->_M_impl._M_finish = |
287 | std::__uninitialized_fill_n_a(this->_M_impl._M_finish, | |
8c7331c5 JW |
288 | __add, __val, _M_get_Tp_allocator()); |
289 | _GLIBCXX_ASAN_ANNOTATE_GREW(__add); | |
874e7baa | 290 | } |
3971a4d2 | 291 | else |
bc9053ab | 292 | _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val)); |
83144cfc | 293 | } |
ed6814f7 | 294 | |
874e7baa PC |
295 | template<typename _Tp, typename _Alloc> |
296 | template<typename _InputIterator> | |
1ae8edf5 | 297 | _GLIBCXX20_CONSTEXPR |
874e7baa PC |
298 | void |
299 | vector<_Tp, _Alloc>:: | |
300 | _M_assign_aux(_InputIterator __first, _InputIterator __last, | |
6323b34e | 301 | std::input_iterator_tag) |
3971a4d2 | 302 | { |
bc9053ab PC |
303 | pointer __cur(this->_M_impl._M_start); |
304 | for (; __first != __last && __cur != this->_M_impl._M_finish; | |
27db01d8 | 305 | ++__cur, (void)++__first) |
874e7baa PC |
306 | *__cur = *__first; |
307 | if (__first == __last) | |
bc9053ab | 308 | _M_erase_at_end(__cur); |
874e7baa | 309 | else |
d7e16fc5 FD |
310 | _M_range_insert(end(), __first, __last, |
311 | std::__iterator_category(__first)); | |
3971a4d2 | 312 | } |
874e7baa PC |
313 | |
314 | template<typename _Tp, typename _Alloc> | |
315 | template<typename _ForwardIterator> | |
1ae8edf5 | 316 | _GLIBCXX20_CONSTEXPR |
874e7baa | 317 | void |
43da93a7 | 318 | vector<_Tp, _Alloc>:: |
874e7baa | 319 | _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last, |
6323b34e | 320 | std::forward_iterator_tag) |
3971a4d2 | 321 | { |
b7b255e7 | 322 | const size_type __sz = size(); |
43da93a7 | 323 | const size_type __len = std::distance(__first, __last); |
874e7baa PC |
324 | |
325 | if (__len > capacity()) | |
326 | { | |
b7b255e7 JW |
327 | if (__len <= __sz) |
328 | __builtin_unreachable(); | |
329 | ||
af55b3af | 330 | _S_check_init_len(__len, _M_get_Tp_allocator()); |
874e7baa | 331 | pointer __tmp(_M_allocate_and_copy(__len, __first, __last)); |
1985f1cd | 332 | std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish, |
4fd20a8f | 333 | _M_get_Tp_allocator()); |
0f317ef7 | 334 | _GLIBCXX_ASAN_ANNOTATE_REINIT; |
874e7baa PC |
335 | _M_deallocate(this->_M_impl._M_start, |
336 | this->_M_impl._M_end_of_storage | |
337 | - this->_M_impl._M_start); | |
338 | this->_M_impl._M_start = __tmp; | |
339 | this->_M_impl._M_finish = this->_M_impl._M_start + __len; | |
340 | this->_M_impl._M_end_of_storage = this->_M_impl._M_finish; | |
341 | } | |
b7b255e7 | 342 | else if (__sz >= __len) |
bc9053ab | 343 | _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start)); |
874e7baa PC |
344 | else |
345 | { | |
346 | _ForwardIterator __mid = __first; | |
b7b255e7 | 347 | std::advance(__mid, __sz); |
874e7baa | 348 | std::copy(__first, __mid, this->_M_impl._M_start); |
b7b255e7 | 349 | const size_type __attribute__((__unused__)) __n = __len - __sz; |
8c7331c5 | 350 | _GLIBCXX_ASAN_ANNOTATE_GROW(__n); |
1985f1cd MA |
351 | this->_M_impl._M_finish = |
352 | std::__uninitialized_copy_a(__mid, __last, | |
353 | this->_M_impl._M_finish, | |
4fd20a8f | 354 | _M_get_Tp_allocator()); |
8c7331c5 | 355 | _GLIBCXX_ASAN_ANNOTATE_GREW(__n); |
874e7baa | 356 | } |
3971a4d2 | 357 | } |
ed6814f7 | 358 | |
734f5023 | 359 | #if __cplusplus >= 201103L |
9958c7eb | 360 | template<typename _Tp, typename _Alloc> |
1ae8edf5 | 361 | _GLIBCXX20_CONSTEXPR |
9958c7eb JW |
362 | auto |
363 | vector<_Tp, _Alloc>:: | |
364 | _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator | |
365 | { | |
366 | const auto __n = __position - cbegin(); | |
76225d2c FD |
367 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) |
368 | if (__position == cend()) | |
369 | { | |
8c7331c5 | 370 | _GLIBCXX_ASAN_ANNOTATE_GROW(1); |
76225d2c FD |
371 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, |
372 | std::move(__v)); | |
373 | ++this->_M_impl._M_finish; | |
8c7331c5 | 374 | _GLIBCXX_ASAN_ANNOTATE_GREW(1); |
76225d2c FD |
375 | } |
376 | else | |
377 | _M_insert_aux(begin() + __n, std::move(__v)); | |
9958c7eb | 378 | else |
76225d2c FD |
379 | _M_realloc_insert(begin() + __n, std::move(__v)); |
380 | ||
9958c7eb JW |
381 | return iterator(this->_M_impl._M_start + __n); |
382 | } | |
383 | ||
6eef7402 CJ |
384 | template<typename _Tp, typename _Alloc> |
385 | template<typename... _Args> | |
1ae8edf5 | 386 | _GLIBCXX20_CONSTEXPR |
9958c7eb | 387 | auto |
6eef7402 | 388 | vector<_Tp, _Alloc>:: |
9958c7eb JW |
389 | _M_emplace_aux(const_iterator __position, _Args&&... __args) |
390 | -> iterator | |
6eef7402 | 391 | { |
9958c7eb | 392 | const auto __n = __position - cbegin(); |
76225d2c FD |
393 | if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage) |
394 | if (__position == cend()) | |
395 | { | |
8c7331c5 | 396 | _GLIBCXX_ASAN_ANNOTATE_GROW(1); |
76225d2c FD |
397 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, |
398 | std::forward<_Args>(__args)...); | |
399 | ++this->_M_impl._M_finish; | |
8c7331c5 | 400 | _GLIBCXX_ASAN_ANNOTATE_GREW(1); |
76225d2c FD |
401 | } |
402 | else | |
403 | { | |
404 | // We need to construct a temporary because something in __args... | |
405 | // could alias one of the elements of the container and so we | |
406 | // need to use it before _M_insert_aux moves elements around. | |
407 | _Temporary_value __tmp(this, std::forward<_Args>(__args)...); | |
408 | _M_insert_aux(begin() + __n, std::move(__tmp._M_val())); | |
409 | } | |
9958c7eb | 410 | else |
76225d2c FD |
411 | _M_realloc_insert(begin() + __n, std::forward<_Args>(__args)...); |
412 | ||
6eef7402 CJ |
413 | return iterator(this->_M_impl._M_start + __n); |
414 | } | |
415 | ||
416 | template<typename _Tp, typename _Alloc> | |
9958c7eb | 417 | template<typename _Arg> |
1ae8edf5 | 418 | _GLIBCXX20_CONSTEXPR |
6eef7402 CJ |
419 | void |
420 | vector<_Tp, _Alloc>:: | |
9958c7eb | 421 | _M_insert_aux(iterator __position, _Arg&& __arg) |
6eef7402 | 422 | #else |
af5fb6ab | 423 | template<typename _Tp, typename _Alloc> |
3971a4d2 | 424 | void |
43da93a7 | 425 | vector<_Tp, _Alloc>:: |
3971a4d2 | 426 | _M_insert_aux(iterator __position, const _Tp& __x) |
6eef7402 | 427 | #endif |
812e8c79 | 428 | { |
8c7331c5 | 429 | _GLIBCXX_ASAN_ANNOTATE_GROW(1); |
76225d2c | 430 | _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish, |
8c7331c5 | 431 | _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1))); |
76225d2c | 432 | ++this->_M_impl._M_finish; |
8c7331c5 | 433 | _GLIBCXX_ASAN_ANNOTATE_GREW(1); |
734f5023 | 434 | #if __cplusplus < 201103L |
76225d2c | 435 | _Tp __x_copy = __x; |
6eef7402 | 436 | #endif |
76225d2c FD |
437 | _GLIBCXX_MOVE_BACKWARD3(__position.base(), |
438 | this->_M_impl._M_finish - 2, | |
439 | this->_M_impl._M_finish - 1); | |
734f5023 | 440 | #if __cplusplus < 201103L |
76225d2c | 441 | *__position = __x_copy; |
812e8c79 | 442 | #else |
76225d2c | 443 | *__position = std::forward<_Arg>(__arg); |
812e8c79 | 444 | #endif |
83144cfc | 445 | } |
64ebadac | 446 | |
734f5023 | 447 | #if __cplusplus >= 201103L |
cc2ba8e3 PC |
448 | template<typename _Tp, typename _Alloc> |
449 | template<typename... _Args> | |
1ae8edf5 | 450 | _GLIBCXX20_CONSTEXPR |
cc2ba8e3 PC |
451 | void |
452 | vector<_Tp, _Alloc>:: | |
76225d2c FD |
453 | _M_realloc_insert(iterator __position, _Args&&... __args) |
454 | #else | |
455 | template<typename _Tp, typename _Alloc> | |
456 | void | |
457 | vector<_Tp, _Alloc>:: | |
458 | _M_realloc_insert(iterator __position, const _Tp& __x) | |
459 | #endif | |
460 | { | |
dd2eb972 | 461 | const size_type __len = _M_check_len(1u, "vector::_M_realloc_insert"); |
1d82fc2e JH |
462 | if (__len <= 0) |
463 | __builtin_unreachable (); | |
c261ba2c MG |
464 | pointer __old_start = this->_M_impl._M_start; |
465 | pointer __old_finish = this->_M_impl._M_finish; | |
76225d2c FD |
466 | const size_type __elems_before = __position - begin(); |
467 | pointer __new_start(this->_M_allocate(__len)); | |
468 | pointer __new_finish(__new_start); | |
dd2eb972 | 469 | |
dd2eb972 | 470 | { |
d22eaeca | 471 | _Guard_alloc __guard(__new_start, __len, *this); |
419c423d VP |
472 | |
473 | // The order of the three operations is dictated by the C++11 | |
474 | // case, where the moves could alter a new element belonging | |
475 | // to the existing vector. This is an issue only for callers | |
476 | // taking the element by lvalue ref (see last bullet of C++11 | |
477 | // [res.on.arguments]). | |
dd2eb972 | 478 | |
419c423d | 479 | // If this throws, the existing elements are unchanged. |
76225d2c | 480 | #if __cplusplus >= 201103L |
419c423d VP |
481 | _Alloc_traits::construct(this->_M_impl, |
482 | std::__to_address(__new_start + __elems_before), | |
483 | std::forward<_Args>(__args)...); | |
76225d2c | 484 | #else |
419c423d VP |
485 | _Alloc_traits::construct(this->_M_impl, |
486 | __new_start + __elems_before, | |
487 | __x); | |
76225d2c | 488 | #endif |
cc2ba8e3 | 489 | |
0f317ef7 | 490 | #if __cplusplus >= 201103L |
419c423d VP |
491 | if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) |
492 | { | |
493 | // Relocation cannot throw. | |
494 | __new_finish = _S_relocate(__old_start, __position.base(), | |
495 | __new_start, _M_get_Tp_allocator()); | |
496 | ++__new_finish; | |
497 | __new_finish = _S_relocate(__position.base(), __old_finish, | |
498 | __new_finish, _M_get_Tp_allocator()); | |
499 | } | |
500 | else | |
dd2eb972 | 501 | #endif |
dd2eb972 | 502 | { |
419c423d VP |
503 | // RAII type to destroy initialized elements. |
504 | struct _Guard_elts | |
505 | { | |
506 | pointer _M_first, _M_last; // Elements to destroy | |
507 | _Tp_alloc_type& _M_alloc; | |
0f317ef7 | 508 | |
419c423d VP |
509 | _GLIBCXX20_CONSTEXPR |
510 | _Guard_elts(pointer __elt, _Tp_alloc_type& __a) | |
511 | : _M_first(__elt), _M_last(__elt + 1), _M_alloc(__a) | |
512 | { } | |
0f317ef7 | 513 | |
419c423d VP |
514 | _GLIBCXX20_CONSTEXPR |
515 | ~_Guard_elts() | |
516 | { std::_Destroy(_M_first, _M_last, _M_alloc); } | |
cc2ba8e3 | 517 | |
419c423d VP |
518 | private: |
519 | _Guard_elts(const _Guard_elts&); | |
520 | }; | |
76225d2c | 521 | |
419c423d VP |
522 | // Guard the new element so it will be destroyed if anything throws. |
523 | _Guard_elts __guard_elts(__new_start + __elems_before, _M_impl); | |
dd2eb972 | 524 | |
419c423d VP |
525 | __new_finish = std::__uninitialized_move_if_noexcept_a( |
526 | __old_start, __position.base(), | |
527 | __new_start, _M_get_Tp_allocator()); | |
dd2eb972 | 528 | |
419c423d VP |
529 | ++__new_finish; |
530 | // Guard everything before the new element too. | |
531 | __guard_elts._M_first = __new_start; | |
dd2eb972 | 532 | |
419c423d VP |
533 | __new_finish = std::__uninitialized_move_if_noexcept_a( |
534 | __position.base(), __old_finish, | |
535 | __new_finish, _M_get_Tp_allocator()); | |
dd2eb972 | 536 | |
419c423d VP |
537 | // New storage has been fully initialized, destroy the old elements. |
538 | __guard_elts._M_first = __old_start; | |
539 | __guard_elts._M_last = __old_finish; | |
540 | } | |
541 | __guard._M_storage = __old_start; | |
542 | __guard._M_len = this->_M_impl._M_end_of_storage - __old_start; | |
543 | } | |
544 | // deallocate should be called before assignments to _M_impl, | |
545 | // to avoid call-clobbering | |
dd2eb972 | 546 | |
76225d2c FD |
547 | this->_M_impl._M_start = __new_start; |
548 | this->_M_impl._M_finish = __new_finish; | |
549 | this->_M_impl._M_end_of_storage = __new_start + __len; | |
550 | } | |
cc2ba8e3 | 551 | |
1d82fc2e JH |
552 | #if __cplusplus >= 201103L |
553 | template<typename _Tp, typename _Alloc> | |
554 | template<typename... _Args> | |
555 | _GLIBCXX20_CONSTEXPR | |
556 | void | |
557 | vector<_Tp, _Alloc>:: | |
558 | _M_realloc_append(_Args&&... __args) | |
559 | #else | |
560 | template<typename _Tp, typename _Alloc> | |
561 | void | |
562 | vector<_Tp, _Alloc>:: | |
563 | _M_realloc_append(const _Tp& __x) | |
564 | #endif | |
565 | { | |
566 | const size_type __len = _M_check_len(1u, "vector::_M_realloc_append"); | |
567 | if (__len <= 0) | |
568 | __builtin_unreachable (); | |
569 | pointer __old_start = this->_M_impl._M_start; | |
570 | pointer __old_finish = this->_M_impl._M_finish; | |
571 | const size_type __elems = end() - begin(); | |
572 | pointer __new_start(this->_M_allocate(__len)); | |
573 | pointer __new_finish(__new_start); | |
574 | ||
1d82fc2e | 575 | { |
d22eaeca | 576 | _Guard_alloc __guard(__new_start, __len, *this); |
1d82fc2e JH |
577 | |
578 | // The order of the three operations is dictated by the C++11 | |
579 | // case, where the moves could alter a new element belonging | |
580 | // to the existing vector. This is an issue only for callers | |
581 | // taking the element by lvalue ref (see last bullet of C++11 | |
582 | // [res.on.arguments]). | |
583 | ||
584 | // If this throws, the existing elements are unchanged. | |
585 | #if __cplusplus >= 201103L | |
586 | _Alloc_traits::construct(this->_M_impl, | |
587 | std::__to_address(__new_start + __elems), | |
588 | std::forward<_Args>(__args)...); | |
589 | #else | |
590 | _Alloc_traits::construct(this->_M_impl, | |
591 | __new_start + __elems, | |
592 | __x); | |
593 | #endif | |
594 | ||
595 | #if __cplusplus >= 201103L | |
596 | if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) | |
597 | { | |
598 | // Relocation cannot throw. | |
599 | __new_finish = _S_relocate(__old_start, __old_finish, | |
600 | __new_start, _M_get_Tp_allocator()); | |
601 | ++__new_finish; | |
602 | } | |
603 | else | |
604 | #endif | |
605 | { | |
606 | // RAII type to destroy initialized elements. | |
607 | struct _Guard_elts | |
608 | { | |
609 | pointer _M_first, _M_last; // Elements to destroy | |
610 | _Tp_alloc_type& _M_alloc; | |
611 | ||
612 | _GLIBCXX20_CONSTEXPR | |
613 | _Guard_elts(pointer __elt, _Tp_alloc_type& __a) | |
614 | : _M_first(__elt), _M_last(__elt + 1), _M_alloc(__a) | |
615 | { } | |
616 | ||
617 | _GLIBCXX20_CONSTEXPR | |
618 | ~_Guard_elts() | |
619 | { std::_Destroy(_M_first, _M_last, _M_alloc); } | |
620 | ||
621 | private: | |
622 | _Guard_elts(const _Guard_elts&); | |
623 | }; | |
624 | ||
625 | // Guard the new element so it will be destroyed if anything throws. | |
626 | _Guard_elts __guard_elts(__new_start + __elems, _M_impl); | |
627 | ||
628 | __new_finish = std::__uninitialized_move_if_noexcept_a( | |
629 | __old_start, __old_finish, | |
630 | __new_start, _M_get_Tp_allocator()); | |
631 | ||
632 | ++__new_finish; | |
633 | ||
634 | // New storage has been fully initialized, destroy the old elements. | |
635 | __guard_elts._M_first = __old_start; | |
636 | __guard_elts._M_last = __old_finish; | |
637 | } | |
638 | __guard._M_storage = __old_start; | |
639 | __guard._M_len = this->_M_impl._M_end_of_storage - __old_start; | |
640 | } | |
641 | // deallocate should be called before assignments to _M_impl, | |
642 | // to avoid call-clobbering | |
643 | ||
644 | this->_M_impl._M_start = __new_start; | |
645 | this->_M_impl._M_finish = __new_finish; | |
646 | this->_M_impl._M_end_of_storage = __new_start + __len; | |
647 | } | |
648 | ||
af5fb6ab | 649 | template<typename _Tp, typename _Alloc> |
1ae8edf5 | 650 | _GLIBCXX20_CONSTEXPR |
3971a4d2 | 651 | void |
43da93a7 | 652 | vector<_Tp, _Alloc>:: |
3971a4d2 PE |
653 | _M_fill_insert(iterator __position, size_type __n, const value_type& __x) |
654 | { | |
655 | if (__n != 0) | |
874e7baa PC |
656 | { |
657 | if (size_type(this->_M_impl._M_end_of_storage | |
658 | - this->_M_impl._M_finish) >= __n) | |
659 | { | |
9958c7eb | 660 | #if __cplusplus < 201103L |
874e7baa | 661 | value_type __x_copy = __x; |
9958c7eb JW |
662 | #else |
663 | _Temporary_value __tmp(this, __x); | |
664 | value_type& __x_copy = __tmp._M_val(); | |
665 | #endif | |
874e7baa | 666 | const size_type __elems_after = end() - __position; |
bc9053ab | 667 | pointer __old_finish(this->_M_impl._M_finish); |
874e7baa PC |
668 | if (__elems_after > __n) |
669 | { | |
8c7331c5 | 670 | _GLIBCXX_ASAN_ANNOTATE_GROW(__n); |
cca06f0d JW |
671 | std::__uninitialized_move_a(__old_finish - __n, |
672 | __old_finish, | |
673 | __old_finish, | |
4fd20a8f | 674 | _M_get_Tp_allocator()); |
874e7baa | 675 | this->_M_impl._M_finish += __n; |
8c7331c5 | 676 | _GLIBCXX_ASAN_ANNOTATE_GREW(__n); |
6eef7402 CJ |
677 | _GLIBCXX_MOVE_BACKWARD3(__position.base(), |
678 | __old_finish - __n, __old_finish); | |
bc9053ab PC |
679 | std::fill(__position.base(), __position.base() + __n, |
680 | __x_copy); | |
874e7baa PC |
681 | } |
682 | else | |
683 | { | |
8c7331c5 | 684 | _GLIBCXX_ASAN_ANNOTATE_GROW(__n); |
e51cf2f5 | 685 | this->_M_impl._M_finish = |
cca06f0d | 686 | std::__uninitialized_fill_n_a(__old_finish, |
e51cf2f5 JW |
687 | __n - __elems_after, |
688 | __x_copy, | |
689 | _M_get_Tp_allocator()); | |
8c7331c5 | 690 | _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after); |
6eef7402 | 691 | std::__uninitialized_move_a(__position.base(), __old_finish, |
1985f1cd | 692 | this->_M_impl._M_finish, |
4fd20a8f | 693 | _M_get_Tp_allocator()); |
874e7baa | 694 | this->_M_impl._M_finish += __elems_after; |
8c7331c5 | 695 | _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after); |
bc9053ab | 696 | std::fill(__position.base(), __old_finish, __x_copy); |
874e7baa PC |
697 | } |
698 | } | |
699 | else | |
700 | { | |
cca06f0d JW |
701 | // Make local copies of these members because the compiler thinks |
702 | // the allocator can alter them if 'this' is globally reachable. | |
703 | pointer __old_start = this->_M_impl._M_start; | |
704 | pointer __old_finish = this->_M_impl._M_finish; | |
705 | const pointer __pos = __position.base(); | |
706 | ||
be1088fa ML |
707 | const size_type __len = |
708 | _M_check_len(__n, "vector::_M_fill_insert"); | |
cca06f0d | 709 | const size_type __elems_before = __pos - __old_start; |
bc9053ab PC |
710 | pointer __new_start(this->_M_allocate(__len)); |
711 | pointer __new_finish(__new_start); | |
bc2631e0 | 712 | __try |
874e7baa | 713 | { |
76225d2c | 714 | // See _M_realloc_insert above. |
d2219f89 PC |
715 | std::__uninitialized_fill_n_a(__new_start + __elems_before, |
716 | __n, __x, | |
717 | _M_get_Tp_allocator()); | |
5b99e0a0 | 718 | __new_finish = pointer(); |
d2219f89 | 719 | |
74a2a1b4 PC |
720 | __new_finish |
721 | = std::__uninitialized_move_if_noexcept_a | |
cca06f0d | 722 | (__old_start, __pos, __new_start, _M_get_Tp_allocator()); |
74a2a1b4 | 723 | |
368b7a30 | 724 | __new_finish += __n; |
d2219f89 | 725 | |
74a2a1b4 PC |
726 | __new_finish |
727 | = std::__uninitialized_move_if_noexcept_a | |
cca06f0d | 728 | (__pos, __old_finish, __new_finish, _M_get_Tp_allocator()); |
874e7baa | 729 | } |
bc2631e0 | 730 | __catch(...) |
874e7baa | 731 | { |
d2219f89 PC |
732 | if (!__new_finish) |
733 | std::_Destroy(__new_start + __elems_before, | |
734 | __new_start + __elems_before + __n, | |
735 | _M_get_Tp_allocator()); | |
736 | else | |
737 | std::_Destroy(__new_start, __new_finish, | |
738 | _M_get_Tp_allocator()); | |
bc9053ab | 739 | _M_deallocate(__new_start, __len); |
874e7baa PC |
740 | __throw_exception_again; |
741 | } | |
cca06f0d | 742 | std::_Destroy(__old_start, __old_finish, _M_get_Tp_allocator()); |
0f317ef7 | 743 | _GLIBCXX_ASAN_ANNOTATE_REINIT; |
cca06f0d JW |
744 | _M_deallocate(__old_start, |
745 | this->_M_impl._M_end_of_storage - __old_start); | |
bc9053ab PC |
746 | this->_M_impl._M_start = __new_start; |
747 | this->_M_impl._M_finish = __new_finish; | |
748 | this->_M_impl._M_end_of_storage = __new_start + __len; | |
874e7baa PC |
749 | } |
750 | } | |
3971a4d2 | 751 | } |
ed6814f7 | 752 | |
734f5023 | 753 | #if __cplusplus >= 201103L |
dc2cf706 | 754 | template<typename _Tp, typename _Alloc> |
1ae8edf5 | 755 | _GLIBCXX20_CONSTEXPR |
dc2cf706 PC |
756 | void |
757 | vector<_Tp, _Alloc>:: | |
758 | _M_default_append(size_type __n) | |
759 | { | |
760 | if (__n != 0) | |
761 | { | |
4c1d999a | 762 | const size_type __size = size(); |
d4356822 MS |
763 | size_type __navail = size_type(this->_M_impl._M_end_of_storage |
764 | - this->_M_impl._M_finish); | |
765 | ||
766 | if (__size > max_size() || __navail > max_size() - __size) | |
767 | __builtin_unreachable(); | |
768 | ||
769 | if (__navail >= __n) | |
dc2cf706 | 770 | { |
8c7331c5 | 771 | _GLIBCXX_ASAN_ANNOTATE_GROW(__n); |
e51cf2f5 JW |
772 | this->_M_impl._M_finish = |
773 | std::__uninitialized_default_n_a(this->_M_impl._M_finish, | |
774 | __n, _M_get_Tp_allocator()); | |
8c7331c5 | 775 | _GLIBCXX_ASAN_ANNOTATE_GREW(__n); |
dc2cf706 PC |
776 | } |
777 | else | |
778 | { | |
cca06f0d JW |
779 | // Make local copies of these members because the compiler thinks |
780 | // the allocator can alter them if 'this' is globally reachable. | |
781 | pointer __old_start = this->_M_impl._M_start; | |
782 | pointer __old_finish = this->_M_impl._M_finish; | |
783 | ||
dc2cf706 PC |
784 | const size_type __len = |
785 | _M_check_len(__n, "vector::_M_default_append"); | |
dc2cf706 | 786 | pointer __new_start(this->_M_allocate(__len)); |
4870a18a | 787 | |
419c423d | 788 | { |
d22eaeca | 789 | _Guard_alloc __guard(__new_start, __len, *this); |
4870a18a | 790 | |
419c423d VP |
791 | std::__uninitialized_default_n_a(__new_start + __size, __n, |
792 | _M_get_Tp_allocator()); | |
793 | ||
794 | if _GLIBCXX17_CONSTEXPR (_S_use_relocate()) | |
4870a18a | 795 | { |
419c423d VP |
796 | _S_relocate(__old_start, __old_finish, |
797 | __new_start, _M_get_Tp_allocator()); | |
798 | } | |
799 | else | |
800 | { | |
801 | // RAII type to destroy initialized elements. | |
802 | struct _Guard_elts | |
803 | { | |
804 | pointer _M_first, _M_last; // Elements to destroy | |
805 | _Tp_alloc_type& _M_alloc; | |
806 | ||
807 | _GLIBCXX20_CONSTEXPR | |
808 | _Guard_elts(pointer __first, size_type __n, | |
809 | _Tp_alloc_type& __a) | |
810 | : _M_first(__first), _M_last(__first + __n), _M_alloc(__a) | |
811 | { } | |
812 | ||
813 | _GLIBCXX20_CONSTEXPR | |
814 | ~_Guard_elts() | |
815 | { std::_Destroy(_M_first, _M_last, _M_alloc); } | |
816 | ||
817 | private: | |
818 | _Guard_elts(const _Guard_elts&); | |
819 | }; | |
820 | _Guard_elts __guard_elts(__new_start + __size, __n, _M_impl); | |
821 | ||
822 | std::__uninitialized_move_if_noexcept_a( | |
823 | __old_start, __old_finish, __new_start, | |
824 | _M_get_Tp_allocator()); | |
825 | ||
826 | __guard_elts._M_first = __old_start; | |
827 | __guard_elts._M_last = __old_finish; | |
828 | } | |
829 | _GLIBCXX_ASAN_ANNOTATE_REINIT; | |
830 | __guard._M_storage = __old_start; | |
831 | __guard._M_len = this->_M_impl._M_end_of_storage - __old_start; | |
832 | } | |
833 | // deallocate should be called before assignments to _M_impl, | |
834 | // to avoid call-clobbering | |
4870a18a | 835 | |
dc2cf706 | 836 | this->_M_impl._M_start = __new_start; |
4c1d999a | 837 | this->_M_impl._M_finish = __new_start + __size + __n; |
dc2cf706 PC |
838 | this->_M_impl._M_end_of_storage = __new_start + __len; |
839 | } | |
840 | } | |
841 | } | |
8a752dfe FD |
842 | |
843 | template<typename _Tp, typename _Alloc> | |
1ae8edf5 | 844 | _GLIBCXX20_CONSTEXPR |
8a752dfe FD |
845 | bool |
846 | vector<_Tp, _Alloc>:: | |
847 | _M_shrink_to_fit() | |
848 | { | |
849 | if (capacity() == size()) | |
850 | return false; | |
8c7331c5 | 851 | _GLIBCXX_ASAN_ANNOTATE_REINIT; |
8a752dfe FD |
852 | return std::__shrink_to_fit_aux<vector>::_S_do_it(*this); |
853 | } | |
dc2cf706 PC |
854 | #endif |
855 | ||
232c4925 PC |
856 | template<typename _Tp, typename _Alloc> |
857 | template<typename _InputIterator> | |
1ae8edf5 | 858 | _GLIBCXX20_CONSTEXPR |
232c4925 PC |
859 | void |
860 | vector<_Tp, _Alloc>:: | |
861 | _M_range_insert(iterator __pos, _InputIterator __first, | |
862 | _InputIterator __last, std::input_iterator_tag) | |
863 | { | |
304a15ec | 864 | if (__pos == end()) |
232c4925 | 865 | { |
304a15ec JW |
866 | for (; __first != __last; ++__first) |
867 | insert(end(), *__first); | |
868 | } | |
869 | else if (__first != __last) | |
870 | { | |
871 | vector __tmp(__first, __last, _M_get_Tp_allocator()); | |
872 | insert(__pos, | |
873 | _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.begin()), | |
874 | _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.end())); | |
232c4925 PC |
875 | } |
876 | } | |
ed6814f7 | 877 | |
874e7baa PC |
878 | template<typename _Tp, typename _Alloc> |
879 | template<typename _ForwardIterator> | |
1ae8edf5 | 880 | _GLIBCXX20_CONSTEXPR |
874e7baa | 881 | void |
43da93a7 | 882 | vector<_Tp, _Alloc>:: |
996e5395 | 883 | _M_range_insert(iterator __position, _ForwardIterator __first, |
6323b34e | 884 | _ForwardIterator __last, std::forward_iterator_tag) |
3971a4d2 | 885 | { |
874e7baa PC |
886 | if (__first != __last) |
887 | { | |
43da93a7 | 888 | const size_type __n = std::distance(__first, __last); |
874e7baa PC |
889 | if (size_type(this->_M_impl._M_end_of_storage |
890 | - this->_M_impl._M_finish) >= __n) | |
891 | { | |
892 | const size_type __elems_after = end() - __position; | |
bc9053ab | 893 | pointer __old_finish(this->_M_impl._M_finish); |
874e7baa PC |
894 | if (__elems_after > __n) |
895 | { | |
8c7331c5 | 896 | _GLIBCXX_ASAN_ANNOTATE_GROW(__n); |
6eef7402 | 897 | std::__uninitialized_move_a(this->_M_impl._M_finish - __n, |
1985f1cd MA |
898 | this->_M_impl._M_finish, |
899 | this->_M_impl._M_finish, | |
4fd20a8f | 900 | _M_get_Tp_allocator()); |
874e7baa | 901 | this->_M_impl._M_finish += __n; |
8c7331c5 | 902 | _GLIBCXX_ASAN_ANNOTATE_GREW(__n); |
6eef7402 CJ |
903 | _GLIBCXX_MOVE_BACKWARD3(__position.base(), |
904 | __old_finish - __n, __old_finish); | |
874e7baa PC |
905 | std::copy(__first, __last, __position); |
906 | } | |
907 | else | |
908 | { | |
909 | _ForwardIterator __mid = __first; | |
910 | std::advance(__mid, __elems_after); | |
8c7331c5 | 911 | _GLIBCXX_ASAN_ANNOTATE_GROW(__n); |
1985f1cd MA |
912 | std::__uninitialized_copy_a(__mid, __last, |
913 | this->_M_impl._M_finish, | |
4fd20a8f | 914 | _M_get_Tp_allocator()); |
874e7baa | 915 | this->_M_impl._M_finish += __n - __elems_after; |
8c7331c5 | 916 | _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after); |
6eef7402 | 917 | std::__uninitialized_move_a(__position.base(), |
bc9053ab | 918 | __old_finish, |
1985f1cd | 919 | this->_M_impl._M_finish, |
4fd20a8f | 920 | _M_get_Tp_allocator()); |
874e7baa | 921 | this->_M_impl._M_finish += __elems_after; |
8c7331c5 | 922 | _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after); |
874e7baa PC |
923 | std::copy(__first, __mid, __position); |
924 | } | |
925 | } | |
926 | else | |
927 | { | |
cca06f0d JW |
928 | // Make local copies of these members because the compiler |
929 | // thinks the allocator can alter them if 'this' is globally | |
930 | // reachable. | |
931 | pointer __old_start = this->_M_impl._M_start; | |
932 | pointer __old_finish = this->_M_impl._M_finish; | |
933 | ||
be1088fa ML |
934 | const size_type __len = |
935 | _M_check_len(__n, "vector::_M_range_insert"); | |
0426be45 FD |
936 | #if __cplusplus < 201103LL |
937 | if (__len < (__n + (__old_start - __old_finish))) | |
938 | __builtin_unreachable(); | |
939 | #endif | |
940 | ||
bc9053ab PC |
941 | pointer __new_start(this->_M_allocate(__len)); |
942 | pointer __new_finish(__new_start); | |
bc2631e0 | 943 | __try |
874e7baa | 944 | { |
74a2a1b4 PC |
945 | __new_finish |
946 | = std::__uninitialized_move_if_noexcept_a | |
cca06f0d | 947 | (__old_start, __position.base(), |
74a2a1b4 PC |
948 | __new_start, _M_get_Tp_allocator()); |
949 | __new_finish | |
950 | = std::__uninitialized_copy_a(__first, __last, | |
951 | __new_finish, | |
952 | _M_get_Tp_allocator()); | |
953 | __new_finish | |
954 | = std::__uninitialized_move_if_noexcept_a | |
cca06f0d | 955 | (__position.base(), __old_finish, |
74a2a1b4 | 956 | __new_finish, _M_get_Tp_allocator()); |
874e7baa | 957 | } |
bc2631e0 | 958 | __catch(...) |
874e7baa | 959 | { |
bc9053ab | 960 | std::_Destroy(__new_start, __new_finish, |
4fd20a8f | 961 | _M_get_Tp_allocator()); |
bc9053ab | 962 | _M_deallocate(__new_start, __len); |
874e7baa PC |
963 | __throw_exception_again; |
964 | } | |
cca06f0d | 965 | std::_Destroy(__old_start, __old_finish, |
4fd20a8f | 966 | _M_get_Tp_allocator()); |
0f317ef7 | 967 | _GLIBCXX_ASAN_ANNOTATE_REINIT; |
cca06f0d JW |
968 | _M_deallocate(__old_start, |
969 | this->_M_impl._M_end_of_storage - __old_start); | |
bc9053ab PC |
970 | this->_M_impl._M_start = __new_start; |
971 | this->_M_impl._M_finish = __new_finish; | |
972 | this->_M_impl._M_end_of_storage = __new_start + __len; | |
874e7baa PC |
973 | } |
974 | } | |
83144cfc | 975 | } |
3cbc7af0 | 976 | |
232c4925 PC |
977 | |
978 | // vector<bool> | |
c62df8fd | 979 | template<typename _Alloc> |
1ae8edf5 | 980 | _GLIBCXX20_CONSTEXPR |
c62df8fd PC |
981 | void |
982 | vector<bool, _Alloc>:: | |
8a752dfe | 983 | _M_reallocate(size_type __n) |
c62df8fd | 984 | { |
ccd615e3 JW |
985 | _Bit_pointer __q = this->_M_allocate(__n); |
986 | iterator __start(std::__addressof(*__q), 0); | |
32917686 | 987 | iterator __finish(_M_copy_aligned(begin(), end(), __start)); |
8a752dfe | 988 | this->_M_deallocate(); |
ccd615e3 | 989 | this->_M_impl._M_start = __start; |
32917686 | 990 | this->_M_impl._M_finish = __finish; |
8a752dfe | 991 | this->_M_impl._M_end_of_storage = __q + _S_nword(__n); |
c62df8fd PC |
992 | } |
993 | ||
232c4925 | 994 | template<typename _Alloc> |
1ae8edf5 | 995 | _GLIBCXX20_CONSTEXPR |
232c4925 PC |
996 | void |
997 | vector<bool, _Alloc>:: | |
998 | _M_fill_insert(iterator __position, size_type __n, bool __x) | |
999 | { | |
1000 | if (__n == 0) | |
1001 | return; | |
1002 | if (capacity() - size() >= __n) | |
1003 | { | |
1004 | std::copy_backward(__position, end(), | |
1005 | this->_M_impl._M_finish + difference_type(__n)); | |
1006 | std::fill(__position, __position + difference_type(__n), __x); | |
1007 | this->_M_impl._M_finish += difference_type(__n); | |
1008 | } | |
1009 | else | |
1010 | { | |
be1088fa ML |
1011 | const size_type __len = |
1012 | _M_check_len(__n, "vector<bool>::_M_fill_insert"); | |
ccd615e3 JW |
1013 | _Bit_pointer __q = this->_M_allocate(__len); |
1014 | iterator __start(std::__addressof(*__q), 0); | |
1015 | iterator __i = _M_copy_aligned(begin(), __position, __start); | |
232c4925 | 1016 | std::fill(__i, __i + difference_type(__n), __x); |
32917686 JW |
1017 | iterator __finish = std::copy(__position, end(), |
1018 | __i + difference_type(__n)); | |
232c4925 | 1019 | this->_M_deallocate(); |
8a752dfe | 1020 | this->_M_impl._M_end_of_storage = __q + _S_nword(__len); |
ccd615e3 | 1021 | this->_M_impl._M_start = __start; |
32917686 | 1022 | this->_M_impl._M_finish = __finish; |
232c4925 PC |
1023 | } |
1024 | } | |
1025 | ||
1026 | template<typename _Alloc> | |
1027 | template<typename _ForwardIterator> | |
1ae8edf5 | 1028 | _GLIBCXX20_CONSTEXPR |
232c4925 PC |
1029 | void |
1030 | vector<bool, _Alloc>:: | |
1031 | _M_insert_range(iterator __position, _ForwardIterator __first, | |
1032 | _ForwardIterator __last, std::forward_iterator_tag) | |
1033 | { | |
1034 | if (__first != __last) | |
1035 | { | |
1036 | size_type __n = std::distance(__first, __last); | |
1037 | if (capacity() - size() >= __n) | |
1038 | { | |
1039 | std::copy_backward(__position, end(), | |
1040 | this->_M_impl._M_finish | |
1041 | + difference_type(__n)); | |
1042 | std::copy(__first, __last, __position); | |
1043 | this->_M_impl._M_finish += difference_type(__n); | |
1044 | } | |
1045 | else | |
1046 | { | |
be1088fa ML |
1047 | const size_type __len = |
1048 | _M_check_len(__n, "vector<bool>::_M_insert_range"); | |
7931a1de | 1049 | const iterator __begin = begin(), __end = end(); |
ccd615e3 JW |
1050 | _Bit_pointer __q = this->_M_allocate(__len); |
1051 | iterator __start(std::__addressof(*__q), 0); | |
7931a1de | 1052 | iterator __i = _M_copy_aligned(__begin, __position, __start); |
232c4925 | 1053 | __i = std::copy(__first, __last, __i); |
7931a1de | 1054 | iterator __finish = std::copy(__position, __end, __i); |
232c4925 | 1055 | this->_M_deallocate(); |
8a752dfe | 1056 | this->_M_impl._M_end_of_storage = __q + _S_nword(__len); |
ccd615e3 | 1057 | this->_M_impl._M_start = __start; |
32917686 | 1058 | this->_M_impl._M_finish = __finish; |
232c4925 PC |
1059 | } |
1060 | } | |
1061 | } | |
1062 | ||
1063 | template<typename _Alloc> | |
1ae8edf5 | 1064 | _GLIBCXX20_CONSTEXPR |
232c4925 PC |
1065 | void |
1066 | vector<bool, _Alloc>:: | |
1067 | _M_insert_aux(iterator __position, bool __x) | |
1068 | { | |
ccd615e3 | 1069 | if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr()) |
232c4925 PC |
1070 | { |
1071 | std::copy_backward(__position, this->_M_impl._M_finish, | |
1072 | this->_M_impl._M_finish + 1); | |
1073 | *__position = __x; | |
1074 | ++this->_M_impl._M_finish; | |
1075 | } | |
1076 | else | |
1077 | { | |
be1088fa ML |
1078 | const size_type __len = |
1079 | _M_check_len(size_type(1), "vector<bool>::_M_insert_aux"); | |
ccd615e3 JW |
1080 | _Bit_pointer __q = this->_M_allocate(__len); |
1081 | iterator __start(std::__addressof(*__q), 0); | |
1082 | iterator __i = _M_copy_aligned(begin(), __position, __start); | |
232c4925 | 1083 | *__i++ = __x; |
32917686 | 1084 | iterator __finish = std::copy(__position, end(), __i); |
232c4925 | 1085 | this->_M_deallocate(); |
8a752dfe | 1086 | this->_M_impl._M_end_of_storage = __q + _S_nword(__len); |
ccd615e3 | 1087 | this->_M_impl._M_start = __start; |
32917686 | 1088 | this->_M_impl._M_finish = __finish; |
232c4925 PC |
1089 | } |
1090 | } | |
1091 | ||
94938aec | 1092 | template<typename _Alloc> |
1ae8edf5 | 1093 | _GLIBCXX20_CONSTEXPR |
94938aec PC |
1094 | typename vector<bool, _Alloc>::iterator |
1095 | vector<bool, _Alloc>:: | |
1096 | _M_erase(iterator __position) | |
1097 | { | |
1098 | if (__position + 1 != end()) | |
1099 | std::copy(__position + 1, end(), __position); | |
1100 | --this->_M_impl._M_finish; | |
1101 | return __position; | |
1102 | } | |
1103 | ||
1104 | template<typename _Alloc> | |
1ae8edf5 | 1105 | _GLIBCXX20_CONSTEXPR |
94938aec PC |
1106 | typename vector<bool, _Alloc>::iterator |
1107 | vector<bool, _Alloc>:: | |
1108 | _M_erase(iterator __first, iterator __last) | |
1109 | { | |
1110 | if (__first != __last) | |
1111 | _M_erase_at_end(std::copy(__last, end(), __first)); | |
1112 | return __first; | |
1113 | } | |
1114 | ||
734f5023 | 1115 | #if __cplusplus >= 201103L |
8a752dfe | 1116 | template<typename _Alloc> |
1ae8edf5 | 1117 | _GLIBCXX20_CONSTEXPR |
8a752dfe FD |
1118 | bool |
1119 | vector<bool, _Alloc>:: | |
1120 | _M_shrink_to_fit() | |
1121 | { | |
1122 | if (capacity() - size() < int(_S_word_bit)) | |
1123 | return false; | |
1124 | __try | |
1125 | { | |
681707ec JW |
1126 | if (size_type __n = size()) |
1127 | _M_reallocate(__n); | |
1128 | else | |
1129 | { | |
1130 | this->_M_deallocate(); | |
1131 | this->_M_impl._M_reset(); | |
1132 | } | |
8a752dfe FD |
1133 | return true; |
1134 | } | |
1135 | __catch(...) | |
1136 | { return false; } | |
1137 | } | |
1138 | #endif | |
1139 | ||
12ffa228 | 1140 | _GLIBCXX_END_NAMESPACE_CONTAINER |
4a15d842 | 1141 | _GLIBCXX_END_NAMESPACE_VERSION |
12ffa228 | 1142 | } // namespace std |
83144cfc | 1143 | |
734f5023 | 1144 | #if __cplusplus >= 201103L |
f54e96d9 | 1145 | |
12ffa228 BK |
1146 | namespace std _GLIBCXX_VISIBILITY(default) |
1147 | { | |
1148 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
f54e96d9 PC |
1149 | |
1150 | template<typename _Alloc> | |
1151 | size_t | |
12ffa228 | 1152 | hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>:: |
72f1c34b | 1153 | operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept |
f54e96d9 PC |
1154 | { |
1155 | size_t __hash = 0; | |
f54e96d9 PC |
1156 | const size_t __words = __b.size() / _S_word_bit; |
1157 | if (__words) | |
1158 | { | |
055f6a47 | 1159 | const size_t __clength = __words * sizeof(_Bit_type); |
e7f72940 | 1160 | __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength); |
f54e96d9 PC |
1161 | } |
1162 | ||
1163 | const size_t __extrabits = __b.size() % _S_word_bit; | |
1164 | if (__extrabits) | |
1165 | { | |
1166 | _Bit_type __hiword = *__b._M_impl._M_finish._M_p; | |
1167 | __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits); | |
1168 | ||
055f6a47 | 1169 | const size_t __clength |
f54e96d9 PC |
1170 | = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__; |
1171 | if (__words) | |
e7f72940 | 1172 | __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash); |
f54e96d9 | 1173 | else |
e7f72940 | 1174 | __hash = std::_Hash_impl::hash(&__hiword, __clength); |
f54e96d9 PC |
1175 | } |
1176 | ||
1177 | return __hash; | |
1178 | } | |
1179 | ||
12ffa228 BK |
1180 | _GLIBCXX_END_NAMESPACE_VERSION |
1181 | } // namespace std | |
f54e96d9 | 1182 | |
734f5023 | 1183 | #endif // C++11 |
f54e96d9 | 1184 | |
8c7331c5 JW |
1185 | #undef _GLIBCXX_ASAN_ANNOTATE_REINIT |
1186 | #undef _GLIBCXX_ASAN_ANNOTATE_GROW | |
1187 | #undef _GLIBCXX_ASAN_ANNOTATE_GREW | |
1188 | #undef _GLIBCXX_ASAN_ANNOTATE_SHRINK | |
1189 | ||
3d7c150e | 1190 | #endif /* _VECTOR_TCC */ |