// Vector implementation (out of line) -*- C++ -*-
-// Copyright (C) 2001, 2002 Free Software Foundation, Inc.
+// Copyright (C) 2001-2020 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library. This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
-// Free Software Foundation; either version 2, or (at your option)
+// Free Software Foundation; either version 3, or (at your option)
// any later version.
// This library is distributed in the hope that it will be useful,
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
-// You should have received a copy of the GNU General Public License along
-// with this library; see the file COPYING. If not, write to the Free
-// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
-// USA.
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
-// As a special exception, you may use this file as part of a free software
-// library without restriction. Specifically, if other files instantiate
-// templates or use macros or inline functions from this file, or you compile
-// this file and link it with other files to produce an executable, this
-// file does not by itself cause the resulting executable to be covered by
-// the GNU General Public License. This exception does not however
-// invalidate any other reasons why the executable file might be covered by
-// the GNU General Public License.
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+// <http://www.gnu.org/licenses/>.
/*
*
* purpose. It is provided "as is" without express or implied warranty.
*/
-/** @file vector.tcc
+/** @file bits/vector.tcc
* This is an internal header file, included by other library headers.
- * You should not attempt to use it directly.
+ * Do not attempt to use it directly. @headername{vector}
*/
-#ifndef __GLIBCPP_INTERNAL_VECTOR_TCC
-#define __GLIBCPP_INTERNAL_VECTOR_TCC
+#ifndef _VECTOR_TCC
+#define _VECTOR_TCC 1
-namespace std
+namespace std _GLIBCXX_VISIBILITY(default)
{
- template <typename _Tp, typename _Alloc>
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+_GLIBCXX_BEGIN_NAMESPACE_CONTAINER
+
+ template<typename _Tp, typename _Alloc>
void
- vector<_Tp,_Alloc>::
+ vector<_Tp, _Alloc>::
reserve(size_type __n)
{
- if (capacity() < __n)
+ if (__n > this->max_size())
+ __throw_length_error(__N("vector::reserve"));
+ if (this->capacity() < __n)
+ {
+ const size_type __old_size = size();
+ pointer __tmp;
+#if __cplusplus >= 201103L
+ if _GLIBCXX17_CONSTEXPR (_S_use_relocate())
+ {
+ __tmp = this->_M_allocate(__n);
+ _S_relocate(this->_M_impl._M_start, this->_M_impl._M_finish,
+ __tmp, _M_get_Tp_allocator());
+ }
+ else
+#endif
+ {
+ __tmp = _M_allocate_and_copy(__n,
+ _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_start),
+ _GLIBCXX_MAKE_MOVE_IF_NOEXCEPT_ITERATOR(this->_M_impl._M_finish));
+ std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+ _M_get_Tp_allocator());
+ }
+ _GLIBCXX_ASAN_ANNOTATE_REINIT;
+ _M_deallocate(this->_M_impl._M_start,
+ this->_M_impl._M_end_of_storage
+ - this->_M_impl._M_start);
+ this->_M_impl._M_start = __tmp;
+ this->_M_impl._M_finish = __tmp + __old_size;
+ this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __n;
+ }
+ }
+
+#if __cplusplus >= 201103L
+ template<typename _Tp, typename _Alloc>
+ template<typename... _Args>
+#if __cplusplus > 201402L
+ typename vector<_Tp, _Alloc>::reference
+#else
+ void
+#endif
+ vector<_Tp, _Alloc>::
+ emplace_back(_Args&&... __args)
{
- const size_type __old_size = size();
- pointer __tmp = _M_allocate_and_copy(__n, _M_start, _M_finish);
- _Destroy(_M_start, _M_finish);
- _M_deallocate(_M_start, _M_end_of_storage - _M_start);
- _M_start = __tmp;
- _M_finish = __tmp + __old_size;
- _M_end_of_storage = _M_start + __n;
+ if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+ {
+ _GLIBCXX_ASAN_ANNOTATE_GROW(1);
+ _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+ std::forward<_Args>(__args)...);
+ ++this->_M_impl._M_finish;
+ _GLIBCXX_ASAN_ANNOTATE_GREW(1);
+ }
+ else
+ _M_realloc_insert(end(), std::forward<_Args>(__args)...);
+#if __cplusplus > 201402L
+ return back();
+#endif
}
- }
-
- template <typename _Tp, typename _Alloc>
- typename vector<_Tp,_Alloc>::iterator
- vector<_Tp,_Alloc>::
+#endif
+
+ template<typename _Tp, typename _Alloc>
+ typename vector<_Tp, _Alloc>::iterator
+ vector<_Tp, _Alloc>::
+#if __cplusplus >= 201103L
+ insert(const_iterator __position, const value_type& __x)
+#else
insert(iterator __position, const value_type& __x)
+#endif
{
- size_type __n = __position - begin();
- if (_M_finish != _M_end_of_storage && __position == end())
- {
- _Construct(_M_finish, __x);
- ++_M_finish;
- }
+ const size_type __n = __position - begin();
+ if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+ if (__position == end())
+ {
+ _GLIBCXX_ASAN_ANNOTATE_GROW(1);
+ _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+ __x);
+ ++this->_M_impl._M_finish;
+ _GLIBCXX_ASAN_ANNOTATE_GREW(1);
+ }
+ else
+ {
+#if __cplusplus >= 201103L
+ const auto __pos = begin() + (__position - cbegin());
+ // __x could be an existing element of this vector, so make a
+ // copy of it before _M_insert_aux moves elements around.
+ _Temporary_value __x_copy(this, __x);
+ _M_insert_aux(__pos, std::move(__x_copy._M_val()));
+#else
+ _M_insert_aux(__position, __x);
+#endif
+ }
else
- _M_insert_aux(__position, __x);
- return begin() + __n;
+#if __cplusplus >= 201103L
+ _M_realloc_insert(begin() + (__position - cbegin()), __x);
+#else
+ _M_realloc_insert(__position, __x);
+#endif
+
+ return iterator(this->_M_impl._M_start + __n);
}
-
- template <typename _Tp, typename _Alloc>
- typename vector<_Tp,_Alloc>::iterator
- vector<_Tp,_Alloc>::
- erase(iterator __position)
+
+ template<typename _Tp, typename _Alloc>
+ typename vector<_Tp, _Alloc>::iterator
+ vector<_Tp, _Alloc>::
+ _M_erase(iterator __position)
{
if (__position + 1 != end())
- copy(__position + 1, end(), __position);
- --_M_finish;
- _Destroy(_M_finish);
+ _GLIBCXX_MOVE3(__position + 1, end(), __position);
+ --this->_M_impl._M_finish;
+ _Alloc_traits::destroy(this->_M_impl, this->_M_impl._M_finish);
+ _GLIBCXX_ASAN_ANNOTATE_SHRINK(1);
return __position;
}
-
- template <typename _Tp, typename _Alloc>
- typename vector<_Tp,_Alloc>::iterator
- vector<_Tp,_Alloc>::
- erase(iterator __first, iterator __last)
+
+ template<typename _Tp, typename _Alloc>
+ typename vector<_Tp, _Alloc>::iterator
+ vector<_Tp, _Alloc>::
+ _M_erase(iterator __first, iterator __last)
{
- iterator __i(copy(__last, end(), __first));
- _Destroy(__i, end());
- _M_finish = _M_finish - (__last - __first);
+ if (__first != __last)
+ {
+ if (__last != end())
+ _GLIBCXX_MOVE3(__last, end(), __first);
+ _M_erase_at_end(__first.base() + (end() - __last));
+ }
return __first;
}
-
- template <typename _Tp, typename _Alloc>
- vector<_Tp,_Alloc>&
- vector<_Tp,_Alloc>::
- operator=(const vector<_Tp,_Alloc>& __x)
+
+ template<typename _Tp, typename _Alloc>
+ vector<_Tp, _Alloc>&
+ vector<_Tp, _Alloc>::
+ operator=(const vector<_Tp, _Alloc>& __x)
{
if (&__x != this)
- {
- const size_type __xlen = __x.size();
- if (__xlen > capacity())
- {
- pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(), __x.end());
- _Destroy(_M_start, _M_finish);
- _M_deallocate(_M_start, _M_end_of_storage - _M_start);
- _M_start = __tmp;
- _M_end_of_storage = _M_start + __xlen;
- }
- else if (size() >= __xlen)
- {
- iterator __i(copy(__x.begin(), __x.end(), begin()));
- _Destroy(__i, end());
- }
- else
- {
- copy(__x.begin(), __x.begin() + size(), _M_start);
- uninitialized_copy(__x.begin() + size(), __x.end(), _M_finish);
- }
- _M_finish = _M_start + __xlen;
- }
+ {
+ _GLIBCXX_ASAN_ANNOTATE_REINIT;
+#if __cplusplus >= 201103L
+ if (_Alloc_traits::_S_propagate_on_copy_assign())
+ {
+ if (!_Alloc_traits::_S_always_equal()
+ && _M_get_Tp_allocator() != __x._M_get_Tp_allocator())
+ {
+ // replacement allocator cannot free existing storage
+ this->clear();
+ _M_deallocate(this->_M_impl._M_start,
+ this->_M_impl._M_end_of_storage
+ - this->_M_impl._M_start);
+ this->_M_impl._M_start = nullptr;
+ this->_M_impl._M_finish = nullptr;
+ this->_M_impl._M_end_of_storage = nullptr;
+ }
+ std::__alloc_on_copy(_M_get_Tp_allocator(),
+ __x._M_get_Tp_allocator());
+ }
+#endif
+ const size_type __xlen = __x.size();
+ if (__xlen > capacity())
+ {
+ pointer __tmp = _M_allocate_and_copy(__xlen, __x.begin(),
+ __x.end());
+ std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+ _M_get_Tp_allocator());
+ _M_deallocate(this->_M_impl._M_start,
+ this->_M_impl._M_end_of_storage
+ - this->_M_impl._M_start);
+ this->_M_impl._M_start = __tmp;
+ this->_M_impl._M_end_of_storage = this->_M_impl._M_start + __xlen;
+ }
+ else if (size() >= __xlen)
+ {
+ std::_Destroy(std::copy(__x.begin(), __x.end(), begin()),
+ end(), _M_get_Tp_allocator());
+ }
+ else
+ {
+ std::copy(__x._M_impl._M_start, __x._M_impl._M_start + size(),
+ this->_M_impl._M_start);
+ std::__uninitialized_copy_a(__x._M_impl._M_start + size(),
+ __x._M_impl._M_finish,
+ this->_M_impl._M_finish,
+ _M_get_Tp_allocator());
+ }
+ this->_M_impl._M_finish = this->_M_impl._M_start + __xlen;
+ }
return *this;
}
-
- template <typename _Tp, typename _Alloc>
+
+ template<typename _Tp, typename _Alloc>
void
- vector<_Tp,_Alloc>::
+ vector<_Tp, _Alloc>::
_M_fill_assign(size_t __n, const value_type& __val)
{
if (__n > capacity())
- {
- vector __tmp(__n, __val, get_allocator());
- __tmp.swap(*this);
- }
+ {
+ vector __tmp(__n, __val, _M_get_Tp_allocator());
+ __tmp._M_impl._M_swap_data(this->_M_impl);
+ }
else if (__n > size())
- {
- fill(begin(), end(), __val);
- _M_finish = uninitialized_fill_n(_M_finish, __n - size(), __val);
- }
- else
- erase(fill_n(begin(), __n, __val), end());
- }
-
- template <typename _Tp, typename _Alloc> template <typename _InputIter>
- void
- vector<_Tp,_Alloc>::
- _M_assign_aux(_InputIter __first, _InputIter __last, input_iterator_tag)
- {
- iterator __cur(begin());
- for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
- *__cur = *__first;
- if (__first == __last)
- erase(__cur, end());
+ {
+ std::fill(begin(), end(), __val);
+ const size_type __add = __n - size();
+ _GLIBCXX_ASAN_ANNOTATE_GROW(__add);
+ this->_M_impl._M_finish =
+ std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
+ __add, __val, _M_get_Tp_allocator());
+ _GLIBCXX_ASAN_ANNOTATE_GREW(__add);
+ }
else
- insert(end(), __first, __last);
+ _M_erase_at_end(std::fill_n(this->_M_impl._M_start, __n, __val));
}
-
- template <typename _Tp, typename _Alloc> template <typename _ForwardIter>
- void
- vector<_Tp,_Alloc>::
- _M_assign_aux(_ForwardIter __first, _ForwardIter __last,
- forward_iterator_tag)
- {
- size_type __len = distance(__first, __last);
-
- if (__len > capacity())
+
+ template<typename _Tp, typename _Alloc>
+ template<typename _InputIterator>
+ void
+ vector<_Tp, _Alloc>::
+ _M_assign_aux(_InputIterator __first, _InputIterator __last,
+ std::input_iterator_tag)
{
- pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
- _Destroy(_M_start, _M_finish);
- _M_deallocate(_M_start, _M_end_of_storage - _M_start);
- _M_start = __tmp;
- _M_end_of_storage = _M_finish = _M_start + __len;
+ pointer __cur(this->_M_impl._M_start);
+ for (; __first != __last && __cur != this->_M_impl._M_finish;
+ ++__cur, (void)++__first)
+ *__cur = *__first;
+ if (__first == __last)
+ _M_erase_at_end(__cur);
+ else
+ _M_range_insert(end(), __first, __last,
+ std::__iterator_category(__first));
}
- else if (size() >= __len)
+
+ template<typename _Tp, typename _Alloc>
+ template<typename _ForwardIterator>
+ void
+ vector<_Tp, _Alloc>::
+ _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
+ std::forward_iterator_tag)
{
- iterator __new_finish(copy(__first, __last, _M_start));
- _Destroy(__new_finish, end());
- _M_finish = __new_finish.base();
+ const size_type __len = std::distance(__first, __last);
+
+ if (__len > capacity())
+ {
+ _S_check_init_len(__len, _M_get_Tp_allocator());
+ pointer __tmp(_M_allocate_and_copy(__len, __first, __last));
+ std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+ _M_get_Tp_allocator());
+ _GLIBCXX_ASAN_ANNOTATE_REINIT;
+ _M_deallocate(this->_M_impl._M_start,
+ this->_M_impl._M_end_of_storage
+ - this->_M_impl._M_start);
+ this->_M_impl._M_start = __tmp;
+ this->_M_impl._M_finish = this->_M_impl._M_start + __len;
+ this->_M_impl._M_end_of_storage = this->_M_impl._M_finish;
+ }
+ else if (size() >= __len)
+ _M_erase_at_end(std::copy(__first, __last, this->_M_impl._M_start));
+ else
+ {
+ _ForwardIterator __mid = __first;
+ std::advance(__mid, size());
+ std::copy(__first, __mid, this->_M_impl._M_start);
+ const size_type __attribute__((__unused__)) __n = __len - size();
+ _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
+ this->_M_impl._M_finish =
+ std::__uninitialized_copy_a(__mid, __last,
+ this->_M_impl._M_finish,
+ _M_get_Tp_allocator());
+ _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
+ }
}
+
+#if __cplusplus >= 201103L
+ template<typename _Tp, typename _Alloc>
+ auto
+ vector<_Tp, _Alloc>::
+ _M_insert_rval(const_iterator __position, value_type&& __v) -> iterator
+ {
+ const auto __n = __position - cbegin();
+ if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+ if (__position == cend())
+ {
+ _GLIBCXX_ASAN_ANNOTATE_GROW(1);
+ _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+ std::move(__v));
+ ++this->_M_impl._M_finish;
+ _GLIBCXX_ASAN_ANNOTATE_GREW(1);
+ }
+ else
+ _M_insert_aux(begin() + __n, std::move(__v));
else
+ _M_realloc_insert(begin() + __n, std::move(__v));
+
+ return iterator(this->_M_impl._M_start + __n);
+ }
+
+ template<typename _Tp, typename _Alloc>
+ template<typename... _Args>
+ auto
+ vector<_Tp, _Alloc>::
+ _M_emplace_aux(const_iterator __position, _Args&&... __args)
+ -> iterator
{
- _ForwardIter __mid = __first;
- advance(__mid, size());
- copy(__first, __mid, _M_start);
- _M_finish = uninitialized_copy(__mid, __last, _M_finish);
+ const auto __n = __position - cbegin();
+ if (this->_M_impl._M_finish != this->_M_impl._M_end_of_storage)
+ if (__position == cend())
+ {
+ _GLIBCXX_ASAN_ANNOTATE_GROW(1);
+ _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+ std::forward<_Args>(__args)...);
+ ++this->_M_impl._M_finish;
+ _GLIBCXX_ASAN_ANNOTATE_GREW(1);
+ }
+ else
+ {
+ // We need to construct a temporary because something in __args...
+ // could alias one of the elements of the container and so we
+ // need to use it before _M_insert_aux moves elements around.
+ _Temporary_value __tmp(this, std::forward<_Args>(__args)...);
+ _M_insert_aux(begin() + __n, std::move(__tmp._M_val()));
+ }
+ else
+ _M_realloc_insert(begin() + __n, std::forward<_Args>(__args)...);
+
+ return iterator(this->_M_impl._M_start + __n);
}
- }
-
- template <typename _Tp, typename _Alloc>
+
+ template<typename _Tp, typename _Alloc>
+ template<typename _Arg>
+ void
+ vector<_Tp, _Alloc>::
+ _M_insert_aux(iterator __position, _Arg&& __arg)
+#else
+ template<typename _Tp, typename _Alloc>
void
- vector<_Tp,_Alloc>::
+ vector<_Tp, _Alloc>::
_M_insert_aux(iterator __position, const _Tp& __x)
+#endif
{
- if (_M_finish != _M_end_of_storage)
- {
- _Construct(_M_finish, *(_M_finish - 1));
- ++_M_finish;
- _Tp __x_copy = __x;
- copy_backward(__position, iterator(_M_finish-2), iterator(_M_finish-1));
- *__position = __x_copy;
- }
- else
- {
- const size_type __old_size = size();
- const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
- iterator __new_start(_M_allocate(__len));
- iterator __new_finish(__new_start);
- try
- {
- __new_finish = uninitialized_copy(iterator(_M_start), __position,
- __new_start);
- _Construct(__new_finish.base(), __x);
- ++__new_finish;
- __new_finish = uninitialized_copy(__position, iterator(_M_finish),
- __new_finish);
- }
- catch(...)
- {
- _Destroy(__new_start,__new_finish);
- _M_deallocate(__new_start.base(),__len);
- __throw_exception_again;
- }
- _Destroy(begin(), end());
- _M_deallocate(_M_start, _M_end_of_storage - _M_start);
- _M_start = __new_start.base();
- _M_finish = __new_finish.base();
- _M_end_of_storage = __new_start.base() + __len;
- }
+ _GLIBCXX_ASAN_ANNOTATE_GROW(1);
+ _Alloc_traits::construct(this->_M_impl, this->_M_impl._M_finish,
+ _GLIBCXX_MOVE(*(this->_M_impl._M_finish - 1)));
+ ++this->_M_impl._M_finish;
+ _GLIBCXX_ASAN_ANNOTATE_GREW(1);
+#if __cplusplus < 201103L
+ _Tp __x_copy = __x;
+#endif
+ _GLIBCXX_MOVE_BACKWARD3(__position.base(),
+ this->_M_impl._M_finish - 2,
+ this->_M_impl._M_finish - 1);
+#if __cplusplus < 201103L
+ *__position = __x_copy;
+#else
+ *__position = std::forward<_Arg>(__arg);
+#endif
}
-
- #ifdef _GLIBCPP_DEPRECATED
- template <typename _Tp, typename _Alloc>
+
+#if __cplusplus >= 201103L
+ template<typename _Tp, typename _Alloc>
+ template<typename... _Args>
+ void
+ vector<_Tp, _Alloc>::
+ _M_realloc_insert(iterator __position, _Args&&... __args)
+#else
+ template<typename _Tp, typename _Alloc>
void
- vector<_Tp,_Alloc>::
- _M_insert_aux(iterator __position)
+ vector<_Tp, _Alloc>::
+ _M_realloc_insert(iterator __position, const _Tp& __x)
+#endif
{
- if (_M_finish != _M_end_of_storage)
- {
- _Construct(_M_finish, *(_M_finish - 1));
- ++_M_finish;
- copy_backward(__position, iterator(_M_finish - 2),
- iterator(_M_finish - 1));
- *__position = value_type();
- }
- else
- {
- const size_type __old_size = size();
- const size_type __len = __old_size != 0 ? 2 * __old_size : 1;
- pointer __new_start = _M_allocate(__len);
- pointer __new_finish = __new_start;
- try
- {
- __new_finish = uninitialized_copy(iterator(_M_start), __position,
- __new_start);
- _Construct(__new_finish);
- ++__new_finish;
- __new_finish = uninitialized_copy(__position, iterator(_M_finish),
- __new_finish);
- }
- catch(...)
- {
- _Destroy(__new_start,__new_finish);
- _M_deallocate(__new_start,__len);
- __throw_exception_again;
- }
- _Destroy(begin(), end());
- _M_deallocate(_M_start, _M_end_of_storage - _M_start);
- _M_start = __new_start;
- _M_finish = __new_finish;
- _M_end_of_storage = __new_start + __len;
- }
+ const size_type __len =
+ _M_check_len(size_type(1), "vector::_M_realloc_insert");
+ pointer __old_start = this->_M_impl._M_start;
+ pointer __old_finish = this->_M_impl._M_finish;
+ const size_type __elems_before = __position - begin();
+ pointer __new_start(this->_M_allocate(__len));
+ pointer __new_finish(__new_start);
+ __try
+ {
+ // The order of the three operations is dictated by the C++11
+ // case, where the moves could alter a new element belonging
+ // to the existing vector. This is an issue only for callers
+ // taking the element by lvalue ref (see last bullet of C++11
+ // [res.on.arguments]).
+ _Alloc_traits::construct(this->_M_impl,
+ __new_start + __elems_before,
+#if __cplusplus >= 201103L
+ std::forward<_Args>(__args)...);
+#else
+ __x);
+#endif
+ __new_finish = pointer();
+
+#if __cplusplus >= 201103L
+ if _GLIBCXX17_CONSTEXPR (_S_use_relocate())
+ {
+ __new_finish = _S_relocate(__old_start, __position.base(),
+ __new_start, _M_get_Tp_allocator());
+
+ ++__new_finish;
+
+ __new_finish = _S_relocate(__position.base(), __old_finish,
+ __new_finish, _M_get_Tp_allocator());
+ }
+ else
+#endif
+ {
+ __new_finish
+ = std::__uninitialized_move_if_noexcept_a
+ (__old_start, __position.base(),
+ __new_start, _M_get_Tp_allocator());
+
+ ++__new_finish;
+
+ __new_finish
+ = std::__uninitialized_move_if_noexcept_a
+ (__position.base(), __old_finish,
+ __new_finish, _M_get_Tp_allocator());
+ }
+ }
+ __catch(...)
+ {
+ if (!__new_finish)
+ _Alloc_traits::destroy(this->_M_impl,
+ __new_start + __elems_before);
+ else
+ std::_Destroy(__new_start, __new_finish, _M_get_Tp_allocator());
+ _M_deallocate(__new_start, __len);
+ __throw_exception_again;
+ }
+#if __cplusplus >= 201103L
+ if _GLIBCXX17_CONSTEXPR (!_S_use_relocate())
+#endif
+ std::_Destroy(__old_start, __old_finish, _M_get_Tp_allocator());
+ _GLIBCXX_ASAN_ANNOTATE_REINIT;
+ _M_deallocate(__old_start,
+ this->_M_impl._M_end_of_storage - __old_start);
+ this->_M_impl._M_start = __new_start;
+ this->_M_impl._M_finish = __new_finish;
+ this->_M_impl._M_end_of_storage = __new_start + __len;
}
- #endif
-
- template <typename _Tp, typename _Alloc>
+
+ template<typename _Tp, typename _Alloc>
void
- vector<_Tp,_Alloc>::
+ vector<_Tp, _Alloc>::
_M_fill_insert(iterator __position, size_type __n, const value_type& __x)
{
if (__n != 0)
- {
- if (size_type(_M_end_of_storage - _M_finish) >= __n) {
- value_type __x_copy = __x;
- const size_type __elems_after = end() - __position;
- iterator __old_finish(_M_finish);
- if (__elems_after > __n)
- {
- uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
- _M_finish += __n;
- copy_backward(__position, __old_finish - __n, __old_finish);
- fill(__position, __position + __n, __x_copy);
- }
- else
- {
- uninitialized_fill_n(_M_finish, __n - __elems_after, __x_copy);
- _M_finish += __n - __elems_after;
- uninitialized_copy(__position, __old_finish, _M_finish);
- _M_finish += __elems_after;
- fill(__position, __old_finish, __x_copy);
- }
- }
- else
- {
- const size_type __old_size = size();
- const size_type __len = __old_size + max(__old_size, __n);
- iterator __new_start(_M_allocate(__len));
- iterator __new_finish(__new_start);
- try
- {
- __new_finish = uninitialized_copy(begin(), __position,
- __new_start);
- __new_finish = uninitialized_fill_n(__new_finish, __n, __x);
- __new_finish
- = uninitialized_copy(__position, end(), __new_finish);
- }
- catch(...)
- {
- _Destroy(__new_start,__new_finish);
- _M_deallocate(__new_start.base(),__len);
- __throw_exception_again;
- }
- _Destroy(_M_start, _M_finish);
- _M_deallocate(_M_start, _M_end_of_storage - _M_start);
- _M_start = __new_start.base();
- _M_finish = __new_finish.base();
- _M_end_of_storage = __new_start.base() + __len;
- }
- }
+ {
+ if (size_type(this->_M_impl._M_end_of_storage
+ - this->_M_impl._M_finish) >= __n)
+ {
+#if __cplusplus < 201103L
+ value_type __x_copy = __x;
+#else
+ _Temporary_value __tmp(this, __x);
+ value_type& __x_copy = __tmp._M_val();
+#endif
+ const size_type __elems_after = end() - __position;
+ pointer __old_finish(this->_M_impl._M_finish);
+ if (__elems_after > __n)
+ {
+ _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
+ std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
+ this->_M_impl._M_finish,
+ this->_M_impl._M_finish,
+ _M_get_Tp_allocator());
+ this->_M_impl._M_finish += __n;
+ _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
+ _GLIBCXX_MOVE_BACKWARD3(__position.base(),
+ __old_finish - __n, __old_finish);
+ std::fill(__position.base(), __position.base() + __n,
+ __x_copy);
+ }
+ else
+ {
+ _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
+ this->_M_impl._M_finish =
+ std::__uninitialized_fill_n_a(this->_M_impl._M_finish,
+ __n - __elems_after,
+ __x_copy,
+ _M_get_Tp_allocator());
+ _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
+ std::__uninitialized_move_a(__position.base(), __old_finish,
+ this->_M_impl._M_finish,
+ _M_get_Tp_allocator());
+ this->_M_impl._M_finish += __elems_after;
+ _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
+ std::fill(__position.base(), __old_finish, __x_copy);
+ }
+ }
+ else
+ {
+ const size_type __len =
+ _M_check_len(__n, "vector::_M_fill_insert");
+ const size_type __elems_before = __position - begin();
+ pointer __new_start(this->_M_allocate(__len));
+ pointer __new_finish(__new_start);
+ __try
+ {
+ // See _M_realloc_insert above.
+ std::__uninitialized_fill_n_a(__new_start + __elems_before,
+ __n, __x,
+ _M_get_Tp_allocator());
+ __new_finish = pointer();
+
+ __new_finish
+ = std::__uninitialized_move_if_noexcept_a
+ (this->_M_impl._M_start, __position.base(),
+ __new_start, _M_get_Tp_allocator());
+
+ __new_finish += __n;
+
+ __new_finish
+ = std::__uninitialized_move_if_noexcept_a
+ (__position.base(), this->_M_impl._M_finish,
+ __new_finish, _M_get_Tp_allocator());
+ }
+ __catch(...)
+ {
+ if (!__new_finish)
+ std::_Destroy(__new_start + __elems_before,
+ __new_start + __elems_before + __n,
+ _M_get_Tp_allocator());
+ else
+ std::_Destroy(__new_start, __new_finish,
+ _M_get_Tp_allocator());
+ _M_deallocate(__new_start, __len);
+ __throw_exception_again;
+ }
+ std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+ _M_get_Tp_allocator());
+ _GLIBCXX_ASAN_ANNOTATE_REINIT;
+ _M_deallocate(this->_M_impl._M_start,
+ this->_M_impl._M_end_of_storage
+ - this->_M_impl._M_start);
+ this->_M_impl._M_start = __new_start;
+ this->_M_impl._M_finish = __new_finish;
+ this->_M_impl._M_end_of_storage = __new_start + __len;
+ }
+ }
}
-
- template <typename _Tp, typename _Alloc> template <typename _InputIterator>
+
+#if __cplusplus >= 201103L
+ template<typename _Tp, typename _Alloc>
void
- vector<_Tp,_Alloc>::
- _M_range_insert(iterator __pos,
- _InputIterator __first, _InputIterator __last,
- input_iterator_tag)
+ vector<_Tp, _Alloc>::
+ _M_default_append(size_type __n)
+ {
+ if (__n != 0)
+ {
+ const size_type __size = size();
+ size_type __navail = size_type(this->_M_impl._M_end_of_storage
+ - this->_M_impl._M_finish);
+
+ if (__size > max_size() || __navail > max_size() - __size)
+ __builtin_unreachable();
+
+ if (__navail >= __n)
+ {
+ _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
+ this->_M_impl._M_finish =
+ std::__uninitialized_default_n_a(this->_M_impl._M_finish,
+ __n, _M_get_Tp_allocator());
+ _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
+ }
+ else
+ {
+ const size_type __len =
+ _M_check_len(__n, "vector::_M_default_append");
+ pointer __new_start(this->_M_allocate(__len));
+ if _GLIBCXX17_CONSTEXPR (_S_use_relocate())
+ {
+ __try
+ {
+ std::__uninitialized_default_n_a(__new_start + __size,
+ __n, _M_get_Tp_allocator());
+ }
+ __catch(...)
+ {
+ _M_deallocate(__new_start, __len);
+ __throw_exception_again;
+ }
+ _S_relocate(this->_M_impl._M_start, this->_M_impl._M_finish,
+ __new_start, _M_get_Tp_allocator());
+ }
+ else
+ {
+ pointer __destroy_from = pointer();
+ __try
+ {
+ std::__uninitialized_default_n_a(__new_start + __size,
+ __n, _M_get_Tp_allocator());
+ __destroy_from = __new_start + __size;
+ std::__uninitialized_move_if_noexcept_a(
+ this->_M_impl._M_start, this->_M_impl._M_finish,
+ __new_start, _M_get_Tp_allocator());
+ }
+ __catch(...)
+ {
+ if (__destroy_from)
+ std::_Destroy(__destroy_from, __destroy_from + __n,
+ _M_get_Tp_allocator());
+ _M_deallocate(__new_start, __len);
+ __throw_exception_again;
+ }
+ std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+ _M_get_Tp_allocator());
+ }
+ _GLIBCXX_ASAN_ANNOTATE_REINIT;
+ _M_deallocate(this->_M_impl._M_start,
+ this->_M_impl._M_end_of_storage
+ - this->_M_impl._M_start);
+ this->_M_impl._M_start = __new_start;
+ this->_M_impl._M_finish = __new_start + __size + __n;
+ this->_M_impl._M_end_of_storage = __new_start + __len;
+ }
+ }
+ }
+
+ template<typename _Tp, typename _Alloc>
+ bool
+ vector<_Tp, _Alloc>::
+ _M_shrink_to_fit()
{
- for ( ; __first != __last; ++__first)
+ if (capacity() == size())
+ return false;
+ _GLIBCXX_ASAN_ANNOTATE_REINIT;
+ return std::__shrink_to_fit_aux<vector>::_S_do_it(*this);
+ }
+#endif
+
+ template<typename _Tp, typename _Alloc>
+ template<typename _InputIterator>
+ void
+ vector<_Tp, _Alloc>::
+ _M_range_insert(iterator __pos, _InputIterator __first,
+ _InputIterator __last, std::input_iterator_tag)
+ {
+ if (__pos == end())
+ {
+ for (; __first != __last; ++__first)
+ insert(end(), *__first);
+ }
+ else if (__first != __last)
+ {
+ vector __tmp(__first, __last, _M_get_Tp_allocator());
+ insert(__pos,
+ _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.begin()),
+ _GLIBCXX_MAKE_MOVE_ITERATOR(__tmp.end()));
+ }
+ }
+
+ template<typename _Tp, typename _Alloc>
+ template<typename _ForwardIterator>
+ void
+ vector<_Tp, _Alloc>::
+ _M_range_insert(iterator __position, _ForwardIterator __first,
+ _ForwardIterator __last, std::forward_iterator_tag)
{
- __pos = insert(__pos, *__first);
- ++__pos;
+ if (__first != __last)
+ {
+ const size_type __n = std::distance(__first, __last);
+ if (size_type(this->_M_impl._M_end_of_storage
+ - this->_M_impl._M_finish) >= __n)
+ {
+ const size_type __elems_after = end() - __position;
+ pointer __old_finish(this->_M_impl._M_finish);
+ if (__elems_after > __n)
+ {
+ _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
+ std::__uninitialized_move_a(this->_M_impl._M_finish - __n,
+ this->_M_impl._M_finish,
+ this->_M_impl._M_finish,
+ _M_get_Tp_allocator());
+ this->_M_impl._M_finish += __n;
+ _GLIBCXX_ASAN_ANNOTATE_GREW(__n);
+ _GLIBCXX_MOVE_BACKWARD3(__position.base(),
+ __old_finish - __n, __old_finish);
+ std::copy(__first, __last, __position);
+ }
+ else
+ {
+ _ForwardIterator __mid = __first;
+ std::advance(__mid, __elems_after);
+ _GLIBCXX_ASAN_ANNOTATE_GROW(__n);
+ std::__uninitialized_copy_a(__mid, __last,
+ this->_M_impl._M_finish,
+ _M_get_Tp_allocator());
+ this->_M_impl._M_finish += __n - __elems_after;
+ _GLIBCXX_ASAN_ANNOTATE_GREW(__n - __elems_after);
+ std::__uninitialized_move_a(__position.base(),
+ __old_finish,
+ this->_M_impl._M_finish,
+ _M_get_Tp_allocator());
+ this->_M_impl._M_finish += __elems_after;
+ _GLIBCXX_ASAN_ANNOTATE_GREW(__elems_after);
+ std::copy(__first, __mid, __position);
+ }
+ }
+ else
+ {
+ const size_type __len =
+ _M_check_len(__n, "vector::_M_range_insert");
+ pointer __new_start(this->_M_allocate(__len));
+ pointer __new_finish(__new_start);
+ __try
+ {
+ __new_finish
+ = std::__uninitialized_move_if_noexcept_a
+ (this->_M_impl._M_start, __position.base(),
+ __new_start, _M_get_Tp_allocator());
+ __new_finish
+ = std::__uninitialized_copy_a(__first, __last,
+ __new_finish,
+ _M_get_Tp_allocator());
+ __new_finish
+ = std::__uninitialized_move_if_noexcept_a
+ (__position.base(), this->_M_impl._M_finish,
+ __new_finish, _M_get_Tp_allocator());
+ }
+ __catch(...)
+ {
+ std::_Destroy(__new_start, __new_finish,
+ _M_get_Tp_allocator());
+ _M_deallocate(__new_start, __len);
+ __throw_exception_again;
+ }
+ std::_Destroy(this->_M_impl._M_start, this->_M_impl._M_finish,
+ _M_get_Tp_allocator());
+ _GLIBCXX_ASAN_ANNOTATE_REINIT;
+ _M_deallocate(this->_M_impl._M_start,
+ this->_M_impl._M_end_of_storage
+ - this->_M_impl._M_start);
+ this->_M_impl._M_start = __new_start;
+ this->_M_impl._M_finish = __new_finish;
+ this->_M_impl._M_end_of_storage = __new_start + __len;
+ }
+ }
}
+
+
+ // vector<bool>
+ template<typename _Alloc>
+ void
+ vector<bool, _Alloc>::
+ _M_reallocate(size_type __n)
+ {
+ _Bit_pointer __q = this->_M_allocate(__n);
+ iterator __start(std::__addressof(*__q), 0);
+ iterator __finish(_M_copy_aligned(begin(), end(), __start));
+ this->_M_deallocate();
+ this->_M_impl._M_start = __start;
+ this->_M_impl._M_finish = __finish;
+ this->_M_impl._M_end_of_storage = __q + _S_nword(__n);
}
-
- template <typename _Tp, typename _Alloc> template <typename _ForwardIterator>
+
+ template<typename _Alloc>
void
- vector<_Tp,_Alloc>::
- _M_range_insert(iterator __position,
- _ForwardIterator __first, _ForwardIterator __last,
- forward_iterator_tag)
+ vector<bool, _Alloc>::
+ _M_fill_insert(iterator __position, size_type __n, bool __x)
{
- if (__first != __last)
+ if (__n == 0)
+ return;
+ if (capacity() - size() >= __n)
+ {
+ std::copy_backward(__position, end(),
+ this->_M_impl._M_finish + difference_type(__n));
+ std::fill(__position, __position + difference_type(__n), __x);
+ this->_M_impl._M_finish += difference_type(__n);
+ }
+ else
+ {
+ const size_type __len =
+ _M_check_len(__n, "vector<bool>::_M_fill_insert");
+ _Bit_pointer __q = this->_M_allocate(__len);
+ iterator __start(std::__addressof(*__q), 0);
+ iterator __i = _M_copy_aligned(begin(), __position, __start);
+ std::fill(__i, __i + difference_type(__n), __x);
+ iterator __finish = std::copy(__position, end(),
+ __i + difference_type(__n));
+ this->_M_deallocate();
+ this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
+ this->_M_impl._M_start = __start;
+ this->_M_impl._M_finish = __finish;
+ }
+ }
+
+ template<typename _Alloc>
+ template<typename _ForwardIterator>
+ void
+ vector<bool, _Alloc>::
+ _M_insert_range(iterator __position, _ForwardIterator __first,
+ _ForwardIterator __last, std::forward_iterator_tag)
{
- size_type __n = distance(__first, __last);
- if (size_type(_M_end_of_storage - _M_finish) >= __n)
- {
- const size_type __elems_after = end() - __position;
- iterator __old_finish(_M_finish);
- if (__elems_after > __n)
- {
- uninitialized_copy(_M_finish - __n, _M_finish, _M_finish);
- _M_finish += __n;
- copy_backward(__position, __old_finish - __n, __old_finish);
- copy(__first, __last, __position);
- }
- else
- {
- _ForwardIterator __mid = __first;
- advance(__mid, __elems_after);
- uninitialized_copy(__mid, __last, _M_finish);
- _M_finish += __n - __elems_after;
- uninitialized_copy(__position, __old_finish, _M_finish);
- _M_finish += __elems_after;
- copy(__first, __mid, __position);
- }
- }
- else
- {
- const size_type __old_size = size();
- const size_type __len = __old_size + max(__old_size, __n);
- iterator __new_start(_M_allocate(__len));
- iterator __new_finish(__new_start);
- try
- {
- __new_finish = uninitialized_copy(iterator(_M_start),
- __position, __new_start);
- __new_finish = uninitialized_copy(__first, __last, __new_finish);
- __new_finish = uninitialized_copy(__position, iterator(_M_finish),
- __new_finish);
- }
- catch(...)
- {
- _Destroy(__new_start,__new_finish);
- _M_deallocate(__new_start.base(), __len);
- __throw_exception_again;
- }
- _Destroy(_M_start, _M_finish);
- _M_deallocate(_M_start, _M_end_of_storage - _M_start);
- _M_start = __new_start.base();
- _M_finish = __new_finish.base();
- _M_end_of_storage = __new_start.base() + __len;
- }
+ if (__first != __last)
+ {
+ size_type __n = std::distance(__first, __last);
+ if (capacity() - size() >= __n)
+ {
+ std::copy_backward(__position, end(),
+ this->_M_impl._M_finish
+ + difference_type(__n));
+ std::copy(__first, __last, __position);
+ this->_M_impl._M_finish += difference_type(__n);
+ }
+ else
+ {
+ const size_type __len =
+ _M_check_len(__n, "vector<bool>::_M_insert_range");
+ _Bit_pointer __q = this->_M_allocate(__len);
+ iterator __start(std::__addressof(*__q), 0);
+ iterator __i = _M_copy_aligned(begin(), __position, __start);
+ __i = std::copy(__first, __last, __i);
+ iterator __finish = std::copy(__position, end(), __i);
+ this->_M_deallocate();
+ this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
+ this->_M_impl._M_start = __start;
+ this->_M_impl._M_finish = __finish;
+ }
+ }
}
+
+ template<typename _Alloc>
+ void
+ vector<bool, _Alloc>::
+ _M_insert_aux(iterator __position, bool __x)
+ {
+ if (this->_M_impl._M_finish._M_p != this->_M_impl._M_end_addr())
+ {
+ std::copy_backward(__position, this->_M_impl._M_finish,
+ this->_M_impl._M_finish + 1);
+ *__position = __x;
+ ++this->_M_impl._M_finish;
+ }
+ else
+ {
+ const size_type __len =
+ _M_check_len(size_type(1), "vector<bool>::_M_insert_aux");
+ _Bit_pointer __q = this->_M_allocate(__len);
+ iterator __start(std::__addressof(*__q), 0);
+ iterator __i = _M_copy_aligned(begin(), __position, __start);
+ *__i++ = __x;
+ iterator __finish = std::copy(__position, end(), __i);
+ this->_M_deallocate();
+ this->_M_impl._M_end_of_storage = __q + _S_nword(__len);
+ this->_M_impl._M_start = __start;
+ this->_M_impl._M_finish = __finish;
+ }
}
+
+ template<typename _Alloc>
+ typename vector<bool, _Alloc>::iterator
+ vector<bool, _Alloc>::
+ _M_erase(iterator __position)
+ {
+ if (__position + 1 != end())
+ std::copy(__position + 1, end(), __position);
+ --this->_M_impl._M_finish;
+ return __position;
+ }
+
+ template<typename _Alloc>
+ typename vector<bool, _Alloc>::iterator
+ vector<bool, _Alloc>::
+ _M_erase(iterator __first, iterator __last)
+ {
+ if (__first != __last)
+ _M_erase_at_end(std::copy(__last, end(), __first));
+ return __first;
+ }
+
+#if __cplusplus >= 201103L
+ template<typename _Alloc>
+ bool
+ vector<bool, _Alloc>::
+ _M_shrink_to_fit()
+ {
+ if (capacity() - size() < int(_S_word_bit))
+ return false;
+ __try
+ {
+ _M_reallocate(size());
+ return true;
+ }
+ __catch(...)
+ { return false; }
+ }
+#endif
+
+_GLIBCXX_END_NAMESPACE_CONTAINER
+_GLIBCXX_END_NAMESPACE_VERSION
} // namespace std
-#endif /* __GLIBCPP_INTERNAL_VECTOR_TCC */
+#if __cplusplus >= 201103L
+
+namespace std _GLIBCXX_VISIBILITY(default)
+{
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+
+ template<typename _Alloc>
+ size_t
+ hash<_GLIBCXX_STD_C::vector<bool, _Alloc>>::
+ operator()(const _GLIBCXX_STD_C::vector<bool, _Alloc>& __b) const noexcept
+ {
+ size_t __hash = 0;
+ using _GLIBCXX_STD_C::_S_word_bit;
+ using _GLIBCXX_STD_C::_Bit_type;
+
+ const size_t __words = __b.size() / _S_word_bit;
+ if (__words)
+ {
+ const size_t __clength = __words * sizeof(_Bit_type);
+ __hash = std::_Hash_impl::hash(__b._M_impl._M_start._M_p, __clength);
+ }
+
+ const size_t __extrabits = __b.size() % _S_word_bit;
+ if (__extrabits)
+ {
+ _Bit_type __hiword = *__b._M_impl._M_finish._M_p;
+ __hiword &= ~((~static_cast<_Bit_type>(0)) << __extrabits);
+
+ const size_t __clength
+ = (__extrabits + __CHAR_BIT__ - 1) / __CHAR_BIT__;
+ if (__words)
+ __hash = std::_Hash_impl::hash(&__hiword, __clength, __hash);
+ else
+ __hash = std::_Hash_impl::hash(&__hiword, __clength);
+ }
+
+ return __hash;
+ }
+
+_GLIBCXX_END_NAMESPACE_VERSION
+} // namespace std
+
+#endif // C++11
+
+#undef _GLIBCXX_ASAN_ANNOTATE_REINIT
+#undef _GLIBCXX_ASAN_ANNOTATE_GROW
+#undef _GLIBCXX_ASAN_ANNOTATE_GREW
+#undef _GLIBCXX_ASAN_ANNOTATE_SHRINK
+
+#endif /* _VECTOR_TCC */
projects / thirdparty / gcc.git / blobdiff