diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -499,6 +499,7 @@ __memory/temp_value.h __memory/temporary_buffer.h __memory/uninitialized_algorithms.h + __memory/uninitialized_buffer.h __memory/unique_ptr.h __memory/uses_allocator.h __memory/uses_allocator_construction.h diff --git a/libcxx/include/__algorithm/inplace_merge.h b/libcxx/include/__algorithm/inplace_merge.h --- a/libcxx/include/__algorithm/inplace_merge.h +++ b/libcxx/include/__algorithm/inplace_merge.h @@ -24,7 +24,7 @@ #include <__iterator/iterator_traits.h> #include <__iterator/reverse_iterator.h> #include <__memory/destruct_n.h> -#include <__memory/temporary_buffer.h> +#include <__memory/uninitialized_buffer.h> #include <__memory/unique_ptr.h> #include <__utility/pair.h> #include @@ -225,13 +225,16 @@ difference_type __len1 = _IterOps<_AlgPolicy>::distance(__first, __middle); difference_type __len2 = _IterOps<_AlgPolicy>::distance(__middle, __last); difference_type __buf_size = _VSTD::min(__len1, __len2); -// TODO: Remove the use of std::get_temporary_buffer -_LIBCPP_SUPPRESS_DEPRECATED_PUSH - pair __buf = _VSTD::get_temporary_buffer(__buf_size); -_LIBCPP_SUPPRESS_DEPRECATED_POP - unique_ptr __h(__buf.first); + auto __buf = std::__make_uninitialized_buffer(nothrow, __buf_size); return std::__inplace_merge<_AlgPolicy>( - std::move(__first), std::move(__middle), std::move(__last), __comp, __len1, __len2, __buf.first, __buf.second); + std::move(__first), + std::move(__middle), + std::move(__last), + __comp, + __len1, + __len2, + __buf.get(), + __buf ? __buf_size : 0); } template diff --git a/libcxx/include/__algorithm/stable_partition.h b/libcxx/include/__algorithm/stable_partition.h --- a/libcxx/include/__algorithm/stable_partition.h +++ b/libcxx/include/__algorithm/stable_partition.h @@ -16,7 +16,7 @@ #include <__iterator/distance.h> #include <__iterator/iterator_traits.h> #include <__memory/destruct_n.h> -#include <__memory/temporary_buffer.h> +#include <__memory/uninitialized_buffer.h> #include <__memory/unique_ptr.h> #include <__utility/move.h> #include <__utility/pair.h> @@ -29,7 +29,7 @@ _LIBCPP_BEGIN_NAMESPACE_STD template -_LIBCPP_HIDE_FROM_ABI _ForwardIterator +_LIBCPP_HIDDEN _ForwardIterator __stable_partition_impl(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, _Distance __len, _Pair __p, forward_iterator_tag __fit) { @@ -122,7 +122,10 @@ __stable_partition_impl(_ForwardIterator __first, _ForwardIterator __last, _Predicate __pred, forward_iterator_tag) { - const unsigned __alloc_limit = 3; // might want to make this a function of trivial assignment + using difference_type = typename iterator_traits<_ForwardIterator>::difference_type; + using value_type = typename iterator_traits<_ForwardIterator>::value_type; + + const difference_type __alloc_limit = 3; // might want to make this a function of trivial assignment // Either prove all true and return __first or point to first false while (true) { @@ -134,21 +137,19 @@ } // We now have a reduced range [__first, __last) // *__first is known to be false - typedef typename iterator_traits<_ForwardIterator>::difference_type difference_type; - typedef typename iterator_traits<_ForwardIterator>::value_type value_type; difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last); - pair __p(0, 0); - unique_ptr __h; + + __uninitialized_buffer_t __buf; if (__len >= __alloc_limit) - { -// TODO: Remove the use of std::get_temporary_buffer -_LIBCPP_SUPPRESS_DEPRECATED_PUSH - __p = _VSTD::get_temporary_buffer(__len); -_LIBCPP_SUPPRESS_DEPRECATED_POP - __h.reset(__p.first); - } + __buf = std::__make_uninitialized_buffer(nothrow, __len); + return std::__stable_partition_impl<_AlgPolicy, _Predicate&>( - std::move(__first), std::move(__last), __pred, __len, __p, forward_iterator_tag()); + std::move(__first), + std::move(__last), + __pred, + __len, + std::make_pair(__buf.get(), __buf ? __len : 0), + forward_iterator_tag()); } template @@ -291,18 +292,17 @@ // *__last is known to be true // __len >= 2 difference_type __len = _IterOps<_AlgPolicy>::distance(__first, __last) + 1; - pair __p(0, 0); - unique_ptr __h; + __uninitialized_buffer_t __buf; if (__len >= __alloc_limit) - { -// TODO: Remove the use of std::get_temporary_buffer -_LIBCPP_SUPPRESS_DEPRECATED_PUSH - __p = _VSTD::get_temporary_buffer(__len); -_LIBCPP_SUPPRESS_DEPRECATED_POP - __h.reset(__p.first); - } + __buf = std::__make_uninitialized_buffer(nothrow, __len); + return std::__stable_partition_impl<_AlgPolicy, _Predicate&>( - std::move(__first), std::move(__last), __pred, __len, __p, bidirectional_iterator_tag()); + std::move(__first), + std::move(__last), + __pred, + __len, + std::make_pair(__buf.get(), __buf ? __len : 0), + bidirectional_iterator_tag()); } template diff --git a/libcxx/include/__algorithm/stable_sort.h b/libcxx/include/__algorithm/stable_sort.h --- a/libcxx/include/__algorithm/stable_sort.h +++ b/libcxx/include/__algorithm/stable_sort.h @@ -18,7 +18,7 @@ #include <__debug_utils/strict_weak_ordering_check.h> #include <__iterator/iterator_traits.h> #include <__memory/destruct_n.h> -#include <__memory/temporary_buffer.h> +#include <__memory/uninitialized_buffer.h> #include <__memory/unique_ptr.h> #include <__type_traits/is_trivially_copy_assignable.h> #include <__utility/move.h> @@ -249,17 +249,12 @@ using difference_type = typename iterator_traits<_RandomAccessIterator>::difference_type; difference_type __len = __last - __first; - pair __buf(0, 0); - unique_ptr __h; - if (__len > static_cast(__stable_sort_switch::value)) { -// TODO: Remove the use of std::get_temporary_buffer -_LIBCPP_SUPPRESS_DEPRECATED_PUSH - __buf = std::get_temporary_buffer(__len); -_LIBCPP_SUPPRESS_DEPRECATED_POP - __h.reset(__buf.first); - } + __uninitialized_buffer_t __buf; + if (__len > static_cast(__stable_sort_switch::value)) + __buf = std::__make_uninitialized_buffer(nothrow, __len); - std::__stable_sort<_AlgPolicy, __comp_ref_type<_Compare> >(__first, __last, __comp, __len, __buf.first, __buf.second); + std::__stable_sort<_AlgPolicy, __comp_ref_type<_Compare> >( + __first, __last, __comp, __len, __buf.get(), __buf ? __len : 0); std::__check_strict_weak_ordering_sorted(__first, __last, __comp); } diff --git a/libcxx/include/__memory/construct_at.h b/libcxx/include/__memory/construct_at.h --- a/libcxx/include/__memory/construct_at.h +++ b/libcxx/include/__memory/construct_at.h @@ -93,6 +93,16 @@ return __last; } +template +_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 +_ForwardIterator __destroy_n(_ForwardIterator __first, _Size __n) { + while (__n > 0) { + std::__destroy_at(std::addressof(*__first)); + ++__first; + --__n; + } + return __first; +} #if _LIBCPP_STD_VER >= 17 template , int> = 0> @@ -118,9 +128,7 @@ template _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 _ForwardIterator destroy_n(_ForwardIterator __first, _Size __n) { - for (; __n > 0; (void)++__first, --__n) - std::__destroy_at(std::addressof(*__first)); - return __first; + return std::__destroy_n(__first, __n); } #endif // _LIBCPP_STD_VER >= 17 diff --git a/libcxx/include/__memory/temporary_buffer.h b/libcxx/include/__memory/temporary_buffer.h --- a/libcxx/include/__memory/temporary_buffer.h +++ b/libcxx/include/__memory/temporary_buffer.h @@ -74,14 +74,6 @@ _VSTD::__libcpp_deallocate_unsized((void*)__p, _LIBCPP_ALIGNOF(_Tp)); } -struct __return_temporary_buffer -{ -_LIBCPP_SUPPRESS_DEPRECATED_PUSH - template - _LIBCPP_INLINE_VISIBILITY void operator()(_Tp* __p) const {_VSTD::return_temporary_buffer(__p);} -_LIBCPP_SUPPRESS_DEPRECATED_POP -}; - _LIBCPP_END_NAMESPACE_STD #endif // _LIBCPP___MEMORY_TEMPORARY_BUFFER_H diff --git a/libcxx/include/__memory/uninitialized_buffer.h b/libcxx/include/__memory/uninitialized_buffer.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__memory/uninitialized_buffer.h @@ -0,0 +1,81 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___MEMORY_UNINITIALIZED_BUFFER_H +#define _LIBCPP___MEMORY_UNINITIALIZED_BUFFER_H + +#include <__config> +#include <__memory/construct_at.h> +#include <__memory/unique_ptr.h> +#include <__type_traits/is_array.h> +#include <__type_traits/is_default_constructible.h> +#include <__type_traits/remove_extent.h> +#include <__utility/move.h> +#include +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +// __make_uninitialized_buffer is a utility function to allocate some memory for scratch storage. The __destructor is +// called before deleting the memory, making it possible to destroy any leftover elements. The __destructor is called +// with the pointer to the first element and the total number of elements. + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +class __uninitialized_buffer_deleter { + size_t __count_; + _Destructor __destructor_; + +public: + template ::value, _Dummy> = 0> + __uninitialized_buffer_deleter() : __count_(0) {} + + __uninitialized_buffer_deleter(size_t __count, _Destructor __destructor) + : __count_(__count), __destructor_(std::move(__destructor)) {} + + template + _LIBCPP_HIDE_FROM_ABI void operator()(_Tp* __ptr) { + __destructor_(__ptr, __count_); +#ifdef _LIBCPP_HAS_NO_ALIGNED_ALLOCATION + ::operator delete(__ptr); +#else + ::operator delete(__ptr, __count_ * sizeof(_Tp), align_val_t(_LIBCPP_ALIGNOF(_Tp))); +#endif + } +}; + +struct __noop { + template + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 void operator()(_Args&&...) const {} +}; + +template +using __uninitialized_buffer_t = unique_ptr<_Array, __uninitialized_buffer_deleter<_Destructor> >; + +template +_LIBCPP_HIDE_FROM_ABI __uninitialized_buffer_t<_Array, _Destructor> +__make_uninitialized_buffer(nothrow_t, size_t __count, _Destructor __destructor = __noop()) { + static_assert(is_array<_Array>::value, ""); + using _Tp = __remove_extent_t<_Array>; + +#ifdef _LIBCPP_HAS_NO_ALIGNED_ALLOCATION + _Tp* __ptr = static_cast<_Tp*>(::operator new(sizeof(_Tp) * __count, nothrow)); +#else + _Tp* __ptr = static_cast<_Tp*>(::operator new(sizeof(_Tp) * __count, align_val_t(_LIBCPP_ALIGNOF(_Tp)), nothrow)); +#endif + + using _Deleter = __uninitialized_buffer_deleter<_Destructor>; + return unique_ptr<_Array, _Deleter>(__ptr, _Deleter(__count, std::move(__destructor))); +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___MEMORY_UNINITIALIZED_BUFFER_H diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -1210,6 +1210,7 @@ module temp_value { private header "__memory/temp_value.h" } module temporary_buffer { private header "__memory/temporary_buffer.h" } module uninitialized_algorithms { private header "__memory/uninitialized_algorithms.h" } + module uninitialized_buffer { private header "__memory/uninitialized_buffer.h" } module unique_ptr { private header "__memory/unique_ptr.h" } module uses_allocator { private header "__memory/uses_allocator.h" } module uses_allocator_construction { private header "__memory/uses_allocator_construction.h" } diff --git a/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/stable_partition.pass.cpp b/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/stable_partition.pass.cpp --- a/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/stable_partition.pass.cpp +++ b/libcxx/test/std/algorithms/alg.modifying.operations/alg.partitions/stable_partition.pass.cpp @@ -17,9 +17,11 @@ #include #include #include +#include -#include "test_macros.h" +#include "count_new.h" #include "test_iterators.h" +#include "test_macros.h" struct is_odd { @@ -36,7 +38,7 @@ void test() { - { // check mixed + { // check mixed typedef std::pair P; P array[] = { @@ -64,8 +66,8 @@ assert(array[7] == P(2, 2)); assert(array[8] == P(4, 1)); assert(array[9] == P(4, 2)); - } - { + } + { typedef std::pair P; P array[] = { @@ -104,8 +106,8 @@ r = std::stable_partition(Iter(array+4), Iter(array+5), odd_first()); assert(base(r) == array+4); assert(array[4] == P(0, 1)); - } - { // check all false + } + { // check all false typedef std::pair P; P array[] = { @@ -133,8 +135,8 @@ assert(array[7] == P(6, 2)); assert(array[8] == P(8, 1)); assert(array[9] == P(8, 2)); - } - { // check all true + } + { // check all true typedef std::pair P; P array[] = { @@ -162,8 +164,8 @@ assert(array[7] == P(7, 2)); assert(array[8] == P(9, 1)); assert(array[9] == P(9, 2)); - } - { // check all false but first true + } + { // check all false but first true typedef std::pair P; P array[] = { @@ -191,8 +193,8 @@ assert(array[7] == P(6, 2)); assert(array[8] == P(8, 1)); assert(array[9] == P(8, 2)); - } - { // check all false but last true + } + { // check all false but last true typedef std::pair P; P array[] = { @@ -220,8 +222,8 @@ assert(array[7] == P(6, 1)); assert(array[8] == P(6, 2)); assert(array[9] == P(8, 1)); - } - { // check all true but first false + } + { // check all true but first false typedef std::pair P; P array[] = { @@ -249,8 +251,8 @@ assert(array[7] == P(9, 1)); assert(array[8] == P(9, 2)); assert(array[9] == P(0, 1)); - } - { // check all true but last false + } + { // check all true but last false typedef std::pair P; P array[] = { @@ -278,7 +280,24 @@ assert(array[7] == P(7, 2)); assert(array[8] == P(9, 1)); assert(array[9] == P(0, 2)); - } + } +#if TEST_STD_VER >= 11 && !defined(TEST_HAS_NO_EXCEPTIONS) + { // check that the algorithm still works when no memory is available + std::vector vec(150, 3); + vec[5] = 6; + getGlobalMemCounter()->throw_after = 0; + std::stable_partition(vec.begin(), vec.end(), [](int i) { return i < 5; }); + assert(std::is_partitioned(vec.begin(), vec.end(), [](int i) { return i < 5; })); + vec[5] = 6; + getGlobalMemCounter()->throw_after = 0; + std::stable_partition( + forward_iterator(vec.data()), forward_iterator(vec.data() + vec.size()), [](int i) { + return i < 5; + }); + assert(std::is_partitioned(vec.begin(), vec.end(), [](int i) { return i < 5; })); + getGlobalMemCounter()->throw_after = 9999; + } +#endif // TEST_STD_VER >= 11 } #if TEST_STD_VER >= 11 diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp --- a/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.merge/inplace_merge.pass.cpp @@ -15,11 +15,13 @@ // inplace_merge(Iter first, Iter middle, Iter last); #include -#include #include +#include +#include -#include "test_macros.h" +#include "count_new.h" #include "test_iterators.h" +#include "test_macros.h" #if TEST_STD_VER >= 11 struct S { @@ -103,10 +105,15 @@ test >(); test(); -#if TEST_STD_VER >= 11 +#if TEST_STD_VER >= 11 && !defined(TEST_HAS_NO_EXCEPTIONS) test >(); test >(); test(); + + std::vector vec(150, 3); + getGlobalMemCounter()->throw_after = 0; + std::inplace_merge(vec.begin(), vec.begin() + 100, vec.end()); + assert(std::all_of(vec.begin(), vec.end(), [](int i) { return i == 3; })); #endif // TEST_STD_VER >= 11 return 0; diff --git a/libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/stable_sort.pass.cpp b/libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/stable_sort.pass.cpp --- a/libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/stable_sort.pass.cpp +++ b/libcxx/test/std/algorithms/alg.sorting/alg.sort/stable.sort/stable_sort.pass.cpp @@ -15,10 +15,11 @@ // stable_sort(Iter first, Iter last); #include +#include #include #include -#include +#include "count_new.h" #include "test_macros.h" std::mt19937 randomness; @@ -155,5 +156,13 @@ test_larger_sorts(1000); test_larger_sorts(1009); +#if !defined(TEST_HAS_NO_EXCEPTIONS) + { // check that the algorithm works without memory + std::vector vec(150, 3); + getGlobalMemCounter()->throw_after = 0; + std::stable_sort(vec.begin(), vec.end()); + } +#endif + return 0; } diff --git a/libcxx/test/support/count_new.h b/libcxx/test/support/count_new.h --- a/libcxx/test/support/count_new.h +++ b/libcxx/test/support/count_new.h @@ -9,9 +9,10 @@ #ifndef COUNT_NEW_H #define COUNT_NEW_H -# include -# include -# include +#include +#include +#include +#include #include #include "test_macros.h" @@ -78,7 +79,6 @@ void newCalled(std::size_t s) { assert(disable_allocations == false); - assert(s); if (throw_after == 0) { throw_after = never_throw_value; detail::throw_bad_alloc_helper(); @@ -112,7 +112,6 @@ void newArrayCalled(std::size_t s) { assert(disable_allocations == false); - assert(s); if (throw_after == 0) { throw_after = never_throw_value; detail::throw_bad_alloc_helper(); @@ -410,11 +409,11 @@ void* operator new(std::size_t s, std::align_val_t av) TEST_THROW_SPEC(std::bad_alloc) { const std::size_t a = static_cast(av); getGlobalMemCounter()->alignedNewCalled(s, a); - void *ret; + void *ret = nullptr; #ifdef USE_ALIGNED_ALLOC ret = _aligned_malloc(s, a); #else - posix_memalign(&ret, a, s); + posix_memalign(&ret, std::max(a, sizeof(void*)), s); #endif if (ret == nullptr) detail::throw_bad_alloc_helper();