Without this patch `basic_string` cannot be properly resized to be
`max_size()` elements in size, even if an allocation is successful.
`__grow_by` allocates one less element than required, resulting in an
out-of-bounds access. At the same time, `max_size()` has an off-by-one
error, since there has to be space to store the null terminator, which
is currently ignored.
The current implementation of the `shrink_to_fit()` function of
`basic_string` swaps to the newly allocated buffer when the new buffer
has the same capacity as the existing one. While this is not incorrect,
it is truly unnecessary to swap to an equally-sized buffer. With equal
capacity, we should keep using the existing buffer and simply deallocate
the new one, avoiding the extra work of copying elements.
The desired behavior was documented in the following comment within the
function:
61ad08792a/libcxx/include/string (L3560-L3566)
However, the existing implementation did not exactly conform to this
guideline, which is a QoI matter.
This PR modifies the `shrink_to_fit()` function to ensure that the
buffer is only swapped when the new allocation is strictly smaller than
the existing one. When the capacities are equal, the new buffer will be
discarded without copying the elements. This is achieved by including
the `==` check in the above conditional logic.
The test would not check its absence and the code path intended for
pointer was never actually instantiated.
I added a few pointer types since there was no coverage.
---------
Co-authored-by: Louis Dionne <ldionne.2@gmail.com>
Completes:
- LWG3359 <chrono> leap second support should allow for negative leap
seconds
- P1361R2 Integration of chrono with text formatting
Implements parts of:
- P0355 Extending <chrono> to Calendars and Time Zones
Fixes: #100432Fixes: #100014
This refactor includes the following changes:
- Refactor similar tests using `types::for_each` to remove redundant code;
- Explicitly include the missing header `type_algorithms.h` in some test files;
- Some tests scattered in different test functions with ad-hoc names
(e.g., `test5()`, `test6()`) but belong to the same kind are now grouped
into one function (`test_struct_array()`).
As a follow-up to #121013 (which optimized `ranges::copy`) and #121026
(which optimized `ranges::copy_backward`), this PR enhances the
performance of `std::ranges::{move, move_backward}` for
`vector<bool>::iterator`, addressing a subtask outlined in issue #64038.
The optimizations bring performance improvements analogous to those
achieved for the `{copy, copy_backward}` algorithms: up to 2000x for
aligned moves and 60x for unaligned moves. Moreover, comprehensive
tests covering up to 4 storage words (256 bytes) with odd and even bit
sizes are provided, which validate the proposed optimizations in this
patch.
These member types were deprecated in C++17 by P0174R2 and removed in
C++20 by P0619R4, but the changes in `<variant>` seem missing.
Drive-by: Replace one `_NOEXCEPT` with `noexcept` as the `hash`
specialization is C++17-and-later only.
All non-existing local times in a contiguous range should map to the
same time point. This fixes a bug, were the times inside the range were
mapped to the wrong time.
Fixes: #113654
Asan reports it after #124103.
It's know case of false positive for Asan.
https://github.com/google/sanitizers/wiki/AddressSanitizerInitializationOrderFiasco#false-positives
It's can be avoided with `constexpr` constructors.
In general order global constructors in different
modules is undefined. If global constructor uses
external global, they can be not constructed yet.
However, implementation may contain workaround for
that, or the state of non-constructed global can
be still valid.
Asan will still falsely report such cases, as it
has no machinery to detect correctness of such
cases.
We need to fix/workaround the issue in libc++, as
it will affect many libc++ with Asan users.
On older MacOS versions where `std::to_chars` for floating-point types
is not available the format library can't be used. Due to some issue
with the availability macro used to disable format on MacOS the issue
triggers regardless of the type being formatted.
The print library has the same issue.
Fixes: #125353
We've been improving these the tests for vector quite a bit and we are
probably not done improving our container tests. Formatting everything
at once will make subsequent reviews easier.
Currently `std::hash<Emplaceable>::operator()` relies implicit
conversion from `int` to `size_t`, which makes MSVC compelling. This PR
switches to use `static_cast`.
In `flat.map/flat.map.access/at_transparent.pass.cpp`, there's one
value-discarding use of `at` that wasn't marked `TEST_IGNORE_NODISCARD`.
This PR adds the missing `TEST_IGNORE_NODISCARD`.
Implements parts of:
- P0355 Extending <chrono> to Calendars and Time Zones
- P1361 Integration of chrono with text formatting
- LWG3359 <chrono> leap second support should allow for negative leap
seconds
The capacity is now passed correctly and a test for this path is added.
Since we changed the implementation of `reserve(size_type)` to only ever
extend,
it doesn't make a ton of sense anymore to have `__shrink_or_extend`,
since the code
paths of `reserve` and `shrink_to_fit` are now almost completely
separate.
This patch splits up `__shrink_or_extend` so that the individual parts
are in `reserve`
and `shrink_to_fit` depending on where they are needed.
This reverts commit 59f57be94f38758616b1339b293b43af845571af.
This PR slightly simplifies the implementation of `vector<bool>::max_size`
and adds extensive tests for the `max_size()` function for both `vector<bool>`
and `vector<T>`. The main purposes of the new tests include:
- Verify correctness of `max_size()` under various `size_type` and
`difference_type` definitions: check that `max_size()` works properly
with allocators that have custom `size_type` and `difference_type`. This
is particularly useful for `vector<bool>`, as different `size_type` lead
to different `__storage_type` of different word lengths, resulting in
varying `max_size()` values for `vector<bool>`. Additionally, different
`difference_type` also sets different upper limit of `max_size()` for
both `vector<bool>` and `std::vector`. These tests were previously
missing.
- Eliminate incorrect implementations: Special tests are added to identify and
reject incorrect implementations of `vector<bool>::max_size` that unconditionally
return `std::min<size_type>(size-max, __internal_cap_to_external(allocator-max-size))`.
This can cause overflow in the `__internal_cap_to_external()` call and lead
to incorrect results. The new tests ensure that such incorrect
implementations are identified.
The __is_trivially_relocatable builtin has semantics that do not
correspond to any current or future notion of trivial relocation.
Furthermore, it currently leads to incorrect optimizations for some
types on supported compilers:
- Clang on Windows where types with non-trivial destructors get
incorrectly optimized
- AppleClang where types with non-trivial move constructors get
incorrectly optimized
Until there is an agreed upon and bugfree implementation of what it
means to be trivially relocatable, it is safer to simply use trivially
copyable instead. This doesn't leave a lot of types behind and is
definitely correct.
This PR addresses an undefined behavior that arises when using the
`std::fill` and `std::fill_n` algorithms, as well as their ranges
counterparts `ranges::fill` and `ranges::fill_n`, with `vector<bool, Alloc>`
that utilizes a custom-sized allocator with small integral types.
As a follow-up to #121013 (which focused on `std::ranges::copy`), this
PR optimizes the performance of `std::ranges::copy_backward` for
`vector<bool>::iterator`, addressing a subtask outlined in issue #64038.
The optimizations yield performance improvements of up to 2000x for
aligned copies and 60x for unaligned copies.
This changes the __output_buffer to a new structure. This improves the
performace of std::format, std::format_to, std::format_to_n, and
std::formatted_size.
While implementing this feature and its associated LWG issues it turns
out
- LWG3316 Correctly define epoch for utc_clock / utc_timepoint only
added non-normative wording to the standard.
Implements parts of:
- P0355 Extending <chrono> to Calendars and Time Zones
- P1361 Integration of chrono with text formatting
- LWG3359 <chrono> leap second support should allow for negative leap
seconds
This is a continuation of what's been started in #89178.
As a drive-by, this also changes the PSTL macro to say `EXPERIMENTAL`
instead of `INCOMPLETE`.
Changes:
- Carve out sized but input-only ranges for C++23.
- Call `std::move` for related functions when the iterator is possibly input-only.
Fixes#115727
By calling `std::move` for related functions when the iterator is
possibly input-only. Also slightly changes the conditions of branch for
contiguous iterators to avoid error.
Fixes#116502
This PR addresses an issue where the `shrink_to_fit` function in
`vector<bool>` is effectively a no-op, meaning it will never shrink the
capacity.
Fixes#122502
These functions weren't added until API 26 (Android 8.0), but libc++ is
supported for API 21 and up.
These APIs are undeclared as of r.android.com/3216959.
This adds a test for an issue reported downstream at
https://github.com/mstorsjo/llvm-mingw/issues/462; this is known to fail
on Windows right now, where the fseek/ftell calls end up truncated to 32
bits.
The test for this, unfortunately, requires temporarily creating a 4 GB
file.
As a follow-up to #113852, this PR optimizes the performance of the
`insert(const_iterator pos, InputIt first, InputIt last)` function for
`input_iterator`-pair inputs in `std::vector` for cases where
reallocation occurs during insertion. Additionally, this optimization
enhances exception safety by replacing the traditional `try-catch`
mechanism with a modern exception guard for the `insert` function.
The optimization targets cases where insertion trigger reallocation. In
scenarios without reallocation, the implementation remains unchanged.
Previous implementation
-----------------------
The previous implementation of `insert` is inefficient in reallocation
scenarios because it performs the following steps separately:
- `reserve()`: This leads to the first round of relocating old
elements to new memory;
- `rotate()`: This leads to the second round of reorganizing the
existing elements;
- Move-forward: Moves the elements after the insertion position to
their final positions.
- Insert: performs the actual insertion.
This approach results in a lot of redundant operations, requiring the
elements to undergo three rounds of relocations/reorganizations to be
placed in their final positions.
Proposed implementation
-----------------------
The proposed implementation jointly optimize the above 4 steps in the
previous implementation such that each element is placed in its final
position in just one round of relocation. Specifically, this
optimization reduces the total cost from 2 relocations + 1 std::rotate
call to just 1 relocation, without needing to call `std::rotate`,
thereby significantly improving overall performance.
This PR fixes the ambiguities in name lookup caused by non-standard
member typedefs `size_type` and `difference_type` in `std::bitset`.
Follows up #121620.
Closes#121618.
Currently, when the result type is 1-`tuple`, `tuple_cat` possibly tests
an undesired constructor of the element, due to conversion from the
reference tuple to the result type. If the element type has an
unconstrained constructor template, there can be extraneous hard error
which shouldn't happen.
This patch introduces a helper function template to select the element-wise
constructor template of `tuple`, which can avoid such error.
Fixes#41034.
Implementing `constexpr std::stable_sort`. This is part of P2562R1,
tracked via issue #105360.
Closes#119394
Co-authored-by: A. Jiang <de34@live.cn>
Co-authored-by: Louis Dionne <ldionne.2@gmail.com>
As a follow-up to #117662, this PR provides a comprehensive set of
exception tests for the following capacity-related functions in
`std::vector`. Specifically, it includes tests for the following
functions:
- `reserve(size_type)`
- `resize(size_type)` and `resize(size_type, const_reference)`
- `shrink_to_fit()`
Previously, the exception safety tests for these functions were either
missing or inadequate. We need a thorough coverage of exception tests to
validate that these operations provide strong exception guarantees under
various exceptional scenarios.
