diff --git a/libcxx/include/vector b/libcxx/include/vector --- a/libcxx/include/vector +++ b/libcxx/include/vector @@ -490,6 +490,10 @@ typedef _VSTD::reverse_iterator reverse_iterator; typedef _VSTD::reverse_iterator const_reverse_iterator; + typedef typename _VSTD::conditional< + _VSTD::is_same >::value, allocator_type, + allocator_type&>::type __allocator_ref; + static_assert((is_same::value), "Allocator::value_type must be same type as value_type"); @@ -663,6 +667,7 @@ bool empty() const _NOEXCEPT {return this->__begin_ == this->__end_;} size_type max_size() const _NOEXCEPT; + static size_type __max_size(__allocator_ref __a) _NOEXCEPT; void reserve(size_type __n); void shrink_to_fit() _NOEXCEPT; @@ -804,6 +809,8 @@ void __vallocate(size_type __n); void __vdeallocate() _NOEXCEPT; _LIBCPP_INLINE_VISIBILITY size_type __recommend(size_type __new_size) const; + static _LIBCPP_INLINE_VISIBILITY size_type + __recommend(__allocator_ref __a, size_type __old_cap, size_type __new_size); void __construct_at_end(size_type __n); _LIBCPP_INLINE_VISIBILITY void __construct_at_end(size_type __n, const_reference __x); @@ -820,6 +827,29 @@ iterator __make_iter(pointer __p) _NOEXCEPT; _LIBCPP_INLINE_VISIBILITY const_iterator __make_iter(const_pointer __p) const _NOEXCEPT; + inline void __apply_buffer(_VSTD::pair __r, + ptrdiff_t __byte_size) _NOEXCEPT { + __invalidate_all_iterators(); + this->__begin_ = __r.first; + this->__end_cap() = __r.second; + + // What we would like to express: + // __builtin_assume((__byte_size % sizeof(value_type)) == 0); + // this->__end_ = __r.first + __byte_size / sizeof(value_type); + // What works: + this->__end_ = + pointer_traits::pointer_to(*reinterpret_cast( + reinterpret_cast(_VSTD::__to_address(__r.first)) + + __byte_size)); + } + + // Swaps out the existing __begin, __end, __end_cap values into the provided + // circular buffer. Returns the swapped out {__begin __end_cap} values + // swapped from the circular buffer. + static _VSTD::pair __swap_out_circular_buffer( + __split_buffer& __v, pointer __begin, + pointer __end, pointer __end_cap); + void __swap_out_circular_buffer(__split_buffer& __v); pointer __swap_out_circular_buffer(__split_buffer& __v, pointer __p); void __move_range(pointer __from_s, pointer __from_e, pointer __to); @@ -836,18 +866,28 @@ __annotate_shrink(__old_size); } + // Returns the size of this instance in bytes. This is used for internally + // optimizing setting the `__end` pointer relative from the `__begin` + // pointer, without needing sizeof(T) mul/div translations. + inline ptrdiff_t __byte_size() const _NOEXCEPT { + return sizeof(value_type) * (this->__end_ - this->__begin_); + } + #ifndef _LIBCPP_CXX03_LANG template - _LIBCPP_INLINE_VISIBILITY - inline void __push_back_slow_path(_Up&& __x); + static _LIBCPP_INLINE_VISIBILITY inline _VSTD::pair + __push_back_slow_path(__allocator_ref __a, pointer __begin, pointer __end, + _Up&& __x); template - _LIBCPP_INLINE_VISIBILITY - inline void __emplace_back_slow_path(_Args&&... __args); + static _LIBCPP_INLINE_VISIBILITY inline _VSTD::pair + __emplace_back_slow_path(__allocator_ref __a, pointer __begin, + pointer __end, _Args&&... __args); #else template - _LIBCPP_INLINE_VISIBILITY - inline void __push_back_slow_path(_Up& __x); + static _LIBCPP_INLINE_VISIBILITY inline _VSTD::pair + __push_back_slow_path(__allocator_ref __a, pointer __begin, pointer __end, + _Up& __x); #endif // The following functions are no-ops outside of AddressSanitizer mode. @@ -855,19 +895,27 @@ // may not meet the AddressSanitizer alignment constraints. // See the documentation for __sanitizer_annotate_contiguous_container for more details. #ifndef _LIBCPP_HAS_NO_ASAN - void __annotate_contiguous_container(const void *__beg, const void *__end, - const void *__old_mid, - const void *__new_mid) const - { - + static void __annotate_contiguous_container(const void* __beg, + const void* __end, + const void* __old_mid, + const void* __new_mid) { if (__beg && is_same::value) __sanitizer_annotate_contiguous_container(__beg, __end, __old_mid, __new_mid); } #else _LIBCPP_INLINE_VISIBILITY - void __annotate_contiguous_container(const void*, const void*, const void*, - const void*) const _NOEXCEPT {} + static void __annotate_contiguous_container(const void*, const void*, + const void*, + const void*) _NOEXCEPT {} #endif + _LIBCPP_INLINE_VISIBILITY + static void __annotate(const_pointer __beg, const_pointer __end, + const_pointer __old_mid, const_pointer __new_mid) _NOEXCEPT { + __annotate_contiguous_container( + _VSTD::__to_address(__beg), _VSTD::__to_address(__end), + _VSTD::__to_address(__old_mid), _VSTD::__to_address(__new_mid)); + } + _LIBCPP_INLINE_VISIBILITY void __annotate_new(size_type __current_size) const _NOEXCEPT { __annotate_contiguous_container(data(), data() + capacity(), @@ -945,6 +993,23 @@ -> vector::value_type, _Alloc>; #endif +template +_VSTD::pair::pointer, + typename vector<_Tp, _Allocator>::pointer> +vector<_Tp, _Allocator>::__swap_out_circular_buffer( + __split_buffer& __v, pointer __begin, + pointer __end, pointer __end_cap) { + __alloc_traits::__construct_backward_with_exception_guarantees( + __v.__alloc(), __begin, __end, __v.__begin_); + __annotate(__begin, __end_cap, __end, __end_cap); + __annotate(__v.__begin_, __v.__end_cap(), __v.__end_cap(), __v.__end_); + _VSTD::pair __r(__v.__begin_, __v.__end_cap()); + __v.__first_ = __v.__begin_ = __begin; + __v.__end_ = __end; + __v.__end_cap() = __end_cap; + return __r; +} + template void vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer& __v) @@ -1018,6 +1083,24 @@ numeric_limits::max()); } +template +typename vector<_Tp, _Allocator>::size_type vector<_Tp, _Allocator>::__max_size( + __allocator_ref __a) _NOEXCEPT { + return _VSTD::min(__alloc_traits::max_size(__a), + numeric_limits::max()); +} + +// Precondition: __new_size > old_cap +template +inline _LIBCPP_INLINE_VISIBILITY typename vector<_Tp, _Allocator>::size_type +vector<_Tp, _Allocator>::__recommend(__allocator_ref __a, size_type __old_cap, + size_type __new_size) { + const size_type __ms = __max_size(__a); + if (__new_size > __ms) _VSTD::__throw_length_error("vector"); + if (__old_cap >= __ms / 2) return __ms; + return _VSTD::max(2 * __old_cap, __new_size); +} + // Precondition: __new_size > capacity() template inline _LIBCPP_INLINE_VISIBILITY @@ -1616,19 +1699,26 @@ template template -void +_VSTD::pair::pointer, + typename vector<_Tp, _Allocator>::pointer> #ifndef _LIBCPP_CXX03_LANG -vector<_Tp, _Allocator>::__push_back_slow_path(_Up&& __x) +vector<_Tp, _Allocator>::__push_back_slow_path(__allocator_ref __a, + pointer __begin, pointer __end, + _Up&& __x) #else -vector<_Tp, _Allocator>::__push_back_slow_path(_Up& __x) +vector<_Tp, _Allocator>::__push_back_slow_path(__allocator_ref __a, + pointer __begin, pointer __end, + _Up& __x) #endif { - allocator_type& __a = this->__alloc(); - __split_buffer __v(__recommend(size() + 1), size(), __a); - // __v.push_back(_VSTD::forward<_Up>(__x)); - __alloc_traits::construct(__a, _VSTD::__to_address(__v.__end_), _VSTD::forward<_Up>(__x)); - __v.__end_++; - __swap_out_circular_buffer(__v); + const size_type __size = __end - __begin; + const size_type __n = __recommend(__a, __size, __size + 1); + __split_buffer __v(__n, __size, __a); + // __v.push_back(_VSTD::forward<_Up>(__x)); + __alloc_traits::construct(__a, _VSTD::__to_address(__v.__end_), + _VSTD::forward<_Up>(__x)); + __v.__end_++; + return __swap_out_circular_buffer(__v, __begin, __end, __end); } template @@ -1636,40 +1726,46 @@ void vector<_Tp, _Allocator>::push_back(const_reference __x) { - if (this->__end_ != this->__end_cap()) - { - __construct_one_at_end(__x); - } - else - __push_back_slow_path(__x); + if (this->__end_ != this->__end_cap()) { + __construct_one_at_end(__x); + } else { + const ptrdiff_t __next_byte_size = this->__byte_size() + sizeof(value_type); + __apply_buffer(__push_back_slow_path(this->__alloc(), this->__begin_, + this->__end_, __x), + __next_byte_size); + } } #ifndef _LIBCPP_CXX03_LANG template -inline _LIBCPP_INLINE_VISIBILITY -void -vector<_Tp, _Allocator>::push_back(value_type&& __x) -{ - if (this->__end_ < this->__end_cap()) - { - __construct_one_at_end(_VSTD::move(__x)); - } - else - __push_back_slow_path(_VSTD::move(__x)); +inline _LIBCPP_INLINE_VISIBILITY void vector<_Tp, _Allocator>::push_back( + value_type&& __x) { + if (this->__end_ != this->__end_cap()) { + __construct_one_at_end(_VSTD::move(__x)); + } else { + const ptrdiff_t __next_byte_size = this->__byte_size() + sizeof(value_type); + __apply_buffer(__push_back_slow_path(this->__alloc(), this->__begin_, + this->__end_, _VSTD::move(__x)), + __next_byte_size); + } } template template -void -vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args) -{ - allocator_type& __a = this->__alloc(); - __split_buffer __v(__recommend(size() + 1), size(), __a); -// __v.emplace_back(_VSTD::forward<_Args>(__args)...); - __alloc_traits::construct(__a, _VSTD::__to_address(__v.__end_), _VSTD::forward<_Args>(__args)...); - __v.__end_++; - __swap_out_circular_buffer(__v); +_VSTD::pair::pointer, + typename vector<_Tp, _Allocator>::pointer> +vector<_Tp, _Allocator>::__emplace_back_slow_path(__allocator_ref __a, + pointer __begin, + pointer __end, + _Args&&... __args) { + const size_type __size = __end - __begin; + const size_type __n = __recommend(__a, __size, __size + 1); + __split_buffer __v(__n, __size, __a); + __alloc_traits::construct(__a, _VSTD::__to_address(__v.__end_), + _VSTD::forward<_Args>(__args)...); + __v.__end_++; + return __swap_out_circular_buffer(__v, __begin, __end, __end); } template @@ -1682,14 +1778,17 @@ #endif vector<_Tp, _Allocator>::emplace_back(_Args&&... __args) { - if (this->__end_ < this->__end_cap()) - { - __construct_one_at_end(_VSTD::forward<_Args>(__args)...); - } - else - __emplace_back_slow_path(_VSTD::forward<_Args>(__args)...); + if (this->__end_ != this->__end_cap()) { + __construct_one_at_end(_VSTD::forward<_Args>(__args)...); + } else { + const ptrdiff_t __next_byte_size = this->__byte_size() + sizeof(value_type); + __apply_buffer( + __emplace_back_slow_path(this->__alloc(), this->__begin_, this->__end_, + _VSTD::forward<_Args>(__args)...), + __next_byte_size); + } #if _LIBCPP_STD_VER > 14 - return this->back(); + return this->back(); #endif }