Looking into reason why we still do throw_bad_alloc in clang binary I noticed
that quite few calls come from deque::_M_reallocate_map. This patch adds
unreachable to limit the size of realloc_map. _M_reallocate_map is called only
if new size is smaller then max_size. map is an array holding pointers to
entries of fixed size.
Since rellocation is done by doubling the map size, I think the maximal size of
map allocated is max_size / deque_buf_size rounded up times two. This should
be also safe for overflows since we have extra bit.
map size is always at least 8. Theoretically this computation may be wrong for
very large T, but in that case callers should never reallocate.
On the testcase I get:
jh@shroud:~> ~/trunk-install-new4/bin/g++ -O2 dq.C -c ; size -A dq.o | grep text
.text 284 0
.text._ZNSt5dequeIiSaIiEE17_M_reallocate_mapEmb 485 0
.text.unlikely 10 0
jh@shroud:~> ~/trunk-install-new5/bin/g++ -O2 dq.C -c ; size -A dq.o | grep text
.text 284 0
.text._ZNSt5dequeIiSaIiEE17_M_reallocate_mapEmb 465 0
.text.unlikely 10 0
so this saves about 20 bytes of rellocate_map, which I think is worthwhile.
Curiously enough gcc14 does:
jh@shroud:~> g++ -O2 dq.C -c ; size -A dq.o | grep text
.text 604 0
.text.unlikely 10 0
which is 145 bytes smaller. Obvoius difference is that _M_reallocate_map gets inlined.
Compiling gcc14 preprocessed file with trunk gives:
jh@shroud:~> g++ -O2 dq.C -S ; size -A dq.o | grep text
.text 762 0
.text.unlikely 10 0
So inlining is due to changes at libstdc++ side, but code size growth is due to
something else.
For clang this reduced number of thris_bad_new_array_length from 121 to 61.
libstdc++-v3/ChangeLog:
* include/bits/deque.tcc (std::deque::_M_reallocate_map): Add
__builtin_unreachable check to declare that maps are not very large.
* include/bits/stl_deque.h (std::deque::size): Add __builtin_unreachable
to check for maximal size of map.
gcc/testsuite/ChangeLog:
* g++.dg/tree-ssa/deque-1.C: New test.
* g++.dg/tree-ssa/deque-2.C: New test.
As an extension, this adds conditional noexcept to std::begin, std::end,
and std::ssize.
libstdc++-v3/ChangeLog:
* include/bits/range_access.h (begin, end, ssize): Add
conditional noexcept.
* testsuite/18_support/initializer_list/range_access.cc: Check
results and noexcept-specifier for std::begin and std::end.
* testsuite/24_iterators/headers/iterator/range_access_c++11.cc:
Check for conditional noexcept on std::begin and std::end.
* testsuite/24_iterators/headers/iterator/range_access_c++14.cc:
Likewise.
* testsuite/24_iterators/headers/iterator/range_access_c++17.cc:
Likewise.
* testsuite/24_iterators/range_access/range_access.cc: Check
conditional noexcept is correct.
* testsuite/24_iterators/range_access/range_access_cpp17.cc:
Check std::size, std::empty and std::data.
* testsuite/24_iterators/range_access/range_access_cpp20.cc:
Check conditional noexcept on std::ssize.
Use Markdown backticks to format comments, instead of Doxygen @c and @a
commands.
libstdc++-v3/ChangeLog:
* include/bits/forward_list.h: Use Markdown in Doxygen comments.
François noticed that the "wrong" type is used in the return type for a
std::set member function template.
The iterator for our std::set is the same type as const_iterator,
so this doesn't actually matter. But it's clearer if the return type
matches the type used in the function body.
libstdc++-v3/ChangeLog:
* include/bits/stl_set.h (set::find): Use const_iterator in
return type, not iterator.
The __is_key_type specialization that matches a pair<key_type, T>
argument is intended for std::unordered_map, not for
std::unordered_set<std::pair<K,T>>.
This uses a pair<const Args&...> as the template argument for
__is_key_type, so that it won't match a set's key_type.
libstdc++-v3/ChangeLog:
PR libstdc++/117686
* include/bits/hashtable.h (_Hashtable::_M_emplace_uniq):
Adjust usage of __is_key_type to avoid false positive.
* testsuite/23_containers/unordered_set/insert/117686.cc:
New test.
François pointed out that static_cast<__node_ptr>(&_M_before_begin) is
invalid, because _M_before_begin is only a node-base not a node.
Refactor the new merge overloads to only cast when we know we have a
valid node.
He also pointed out some optimizations to allow reusing hash codes that
might be cached in the node. The _M_src_hash_code function already has
the right logic to decide when a cached hash code can be reused by a
different _Hashtable object.
libstdc++-v3/ChangeLog:
* include/bits/hashtable.h (_Hashtable::_M_src_hash_code):
Improve comments.
(_Hashtable::_M_merge_unique(_Hashtable&)): Use pointer_traits
to get before-begin pointer. Only use static_cast on valid
nodes, not the before-begin pointer. Reuse a hash code cached in
the node when possible.
(_Hashtable::_M_merge_multi(_Hashtable&)): Likewise.
Reviewed-by: François Dumont <fdumont@gcc.gnu.org>
This patch introduces an installed source form of module std and std.compat.
To help a build system find them, we install a libstdc++.modules.json file
alongside libstdc++.so, which tells the build system where the files are and
any special flags it should use when compiling them (none, in this case).
The format is from a proposal in SG15. The build system can find this file
with 'gcc -print-file-name=libstdc++.modules.json'.
It seems preferable to use a relative path from this file to the sources so
that moving the installation doesn't break the reference, but I didn't see
any obvious way to compute that without relying on coreutils, perl, or
python, so I wrote a POSIX shell script for it. The .. canonicalization
bits aren't necessary since I discovered $(abspath), but I guess I might as
well leave them in.
Currently this installs the sources under $(gxx_include_dir)/bits/,
i.e. /usr/include/c++/15/bits. So with my -fsearch-include-path change,
std.cc can be compiled with g++ -fsearch-include-path bits/std.cc. Note
that if someone actually tries to #include <bits/std.cc> it will fail with
"error: module control-line cannot be in included file".
Any ideas about a more user-friendly way to express "compile module std" are
welcome.
The sources currently have the extension .cc, like other source files.
std.cc started with m.cencora's implementation in PR114600. I've made some
adjustments, but more is probably desirable, e.g. of the <algorithm>
handling of namespace ranges, and to remove exports of templates that are
only specialized in a particular header. I've filled in a bunch of missing
exports, and added some FIXMEs where I noticed bits that are not implemented
yet.
Since bits/stdc++.h also intends to include the whole standard library, I
include it rather than duplicate it. But stdc++.h comments out <execution>,
due to TBB issues; I include it separately and suppress TBB usage, so module
std won't currently provide parallel execution.
It seemed most convenient for the two files to be monolithic so we don't
need to worry about include paths. So the C library names that module
std.compat exports in both namespace std and :: are a block of code that is
appended to both files, adjusted based on whether the macro STD_COMPAT is
defined before the block.
In this implementation std.compat imports std; it would also be valid for it
to duplicate everything in std. I see the libc++ std.compat also imports
std.
As discussed in the PR, module std is supported in C++20 mode even though it
was added in C++23.
Changes to test module std will follow in a separate patch. In my testing
I've noticed a few compiler bugs that break various testcases, so I don't
expect to enable module std testing by default at first.
PR libstdc++/106852
libstdc++-v3/ChangeLog:
* include/bits/version.def: Add __cpp_lib_modules.
* include/bits/version.h: Regenerate.
* src/c++23/Makefile.am: Add modules std and std.compat.
* src/c++23/Makefile.in: Regenerate.
* src/c++23/std-clib.cc.in: New file.
* src/c++23/std.cc.in: New file.
* src/c++23/std.compat.cc.in: New file.
* src/c++23/libstdc++.modules.json.in: New file.
contrib/ChangeLog:
* relpath.sh: New file.
This patch makes it clear that vector sizes and capacities are not
negative. With recent change to ipa-fnsummary this should not affect
inlining and improves codegen of some vector manipulation functions.
I tested clang build. Looking for throw_bad calls there are only 3
called considerably often (bad_allloc, bad_array_new_length and
function_callv).
The patch seems to reduce bad_alloc and bad_array_new_length calls
considerably:
bad_alloc 380->147
bad_array_new_length 832->128
libstdc++-v3/ChangeLog:
PR tree-optimization/109442
* include/bits/stl_vector.h: (vector::size(),
vector::capacity()): Add __builtin_unreachable call to announce
that size and capacity are non-negative.
gcc/testsuite/ChangeLog:
PR tree-optimization/109442
* g++.dg/tree-ssa/pr109442.C: New test.
We already implement short-circuiting for random access iterators, but
we also need to do so for ranges::equal and ranges::is_permutation when
given sized ranges that are not random access ranges (e.g. std::list).
libstdc++-v3/ChangeLog:
* include/bits/ranges_algo.h (__is_permutation_fn::operator()):
Short-circuit for sized ranges with different sizes, as per LWG
3560.
* include/bits/ranges_algobase.h (__equal_fn::operator()):
Likewise.
* include/bits/stl_algo.h (__is_permutation): Use if-constexpr
for random access iterator branches.
* include/bits/stl_algobase.h (__equal4): Likewise.
* testsuite/25_algorithms/equal/lwg3560.cc: New test.
* testsuite/25_algorithms/is_permutation/lwg3560.cc: New test.
Reviewed-by: Patrick Palka <ppalka@redhat.com>
This LWG issue corrects the definition of these alias templates to make
them suitable for alias CTAD.
libstdc++-v3/ChangeLog:
* include/std/ranges (keys_view): Adjust as per LWG 3563.
(values_view): Likewise.
* testsuite/std/ranges/adaptors/elements.cc (test08): New test.
Reviewed-by: Jonathan Wakely <jwakely@redhat.com>
Apprived at October 2021 plenary.
libstdc++-v3/ChangeLog:
* include/bits/ranges_util.h (subrange::begin): Fix constraint,
as per LWG 3589.
* testsuite/std/ranges/subrange/lwg3589.cc: New test.
The _GLIBCXX_NODISCARD macro only expands to [[__nodiscard__]] for C++17
and later, but all supported compilers will allow us to use that for
C++11 and C++14 too. Enable it for those older standards, to give
improved diagnostics for users of those older standards.
libstdc++-v3/ChangeLog:
* include/bits/c++config (_GLIBCXX_NODISCARD): Expand for C++11
and C++14.
* testsuite/22_locale/locale/cons/12438.cc: Adjust dg-warning to
expect nodiscard warnings for C++11 and C++14 as well.
* testsuite/22_locale/locale/operations/2.cc: Likewise.
* testsuite/25_algorithms/equal/debug/1_neg.cc: Likewise.
* testsuite/25_algorithms/equal/debug/2_neg.cc: Likewise.
* testsuite/25_algorithms/equal/debug/3_neg.cc: Likewise.
* testsuite/25_algorithms/find_first_of/concept_check_1.cc:
Likewise.
* testsuite/25_algorithms/is_permutation/2.cc: Likewise.
* testsuite/25_algorithms/lexicographical_compare/71545.cc:
Likewise.
* testsuite/25_algorithms/lower_bound/33613.cc: Likewise.
* testsuite/25_algorithms/lower_bound/debug/irreflexive.cc:
Likewise.
* testsuite/25_algorithms/lower_bound/debug/partitioned_neg.cc:
Likewise.
* testsuite/25_algorithms/lower_bound/debug/partitioned_pred_neg.cc: Likewise.
* testsuite/25_algorithms/minmax/3.cc: Likewise.
* testsuite/25_algorithms/search/78346.cc: Likewise.
* testsuite/25_algorithms/search_n/58358.cc: Likewise.
* testsuite/25_algorithms/unique/1.cc: Likewise.
* testsuite/25_algorithms/unique/11480.cc: Likewise.
* testsuite/25_algorithms/upper_bound/33613.cc: Likewise.
* testsuite/25_algorithms/upper_bound/debug/partitioned_neg.cc:
Likewise.
* testsuite/25_algorithms/upper_bound/debug/partitioned_pred_neg.cc: Likewise.
* testsuite/27_io/ios_base/types/fmtflags/bitmask_operators.cc:
Likewise.
* testsuite/27_io/ios_base/types/iostate/bitmask_operators.cc:
Likewise.
* testsuite/27_io/ios_base/types/openmode/bitmask_operators.cc:
Likewise.
* testsuite/ext/concept_checks.cc: Likewise.
* testsuite/ext/is_heap/47709.cc: Likewise.
* testsuite/ext/is_sorted/cxx0x.cc: Likewise.
r13-3036 moved #include <coroutine> into the new freestanding section, but
also moved it from a C++20 section to a C++23 section. This patch moves it
back.
Incidentally, I'm curious why a few headers were removed from the hosted
section (including <coroutine>), but most were left in place, so we have
redundant includes of most hosted headers.
libstdc++-v3/ChangeLog:
* include/precompiled/stdc++.h: <coroutine> is C++20.
This constraint was added by the One Ranges proposal (P0896R4) and
then fixed by LWG 3293, but it was missing from libstdc++.
libstdc++-v3/ChangeLog:
* include/bits/stl_iterator.h (operator+): Add constraint to
move_iterator operator.
* testsuite/24_iterators/move_iterator/rel_ops_c++20.cc:
This is a very minor throughput optimization, to avoid instantiating
std::enable_if and std::is_convertible when concepts are available.
libstdc++-v3/ChangeLog:
* include/bits/stl_iterator.h (__normal_iterator): Replace
enable_if constraint with requires-clause.
Remove __cplusplus > 201703L checks that are redundant when used
alongside __glibcxx_concepts checks, because <version> already
guarantees that __glibcxx_concepts is only defined for C++20 and later.
Prefer to check __glibcxx_ranges for features such as move_sentinel that
were added by the One Ranges proposal (P0896R4), or for features which
depend on other components introduced by that proposal.
But prefer to check __glibcxx_concepts for constraints that only depend
on requires-clauses and concepts defined in <concepts>, even if those
constraints were added by the Ranges proposal (e.g. the constraints on
non-member operators for move_iterator).
Prefer #ifdef to #if when just testing for the presence of __glibcxx_foo
macros with caring about their value.
Also add/tweak some Doxygen comments.
libstdc++-v3/ChangeLog:
* include/bits/stl_iterator.h: Make use of feature test macros
more consistent. Improve doxygen comments.
It looks like I only read half the resolution of LWG 3480 and decided we
already supported it. As well as making the non-member overloads of end
take their parameters by value, we need some specializations of the
enable_borrowed_range and enable_view variable templates.
libstdc++-v3/ChangeLog:
PR libstdc++/117560
* include/bits/fs_dir.h (enable_borrowed_range, enable_view):
Define specializations for directory iterators, as per LWG 3480.
* testsuite/27_io/filesystem/iterators/lwg3480.cc: New test.
This attempts to simplify and clean up our std::hash code. The primary
benefit is improved diagnostics for users when they do something wrong
involving std::hash or unordered containers. An additional benefit is
that for the unstable ABI (--enable-symvers=gnu-versioned-namespace) we
can reduce the memory footprint of several std::hash specializations.
In the current design, __hash_enum is a base class of the std::hash
primary template, but the partial specialization of __hash_enum for
non-enum types is disabled. This means that if a user forgets to
specialize std::hash for their class type (or forgets to use a custom
hash function for unordered containers) they get error messages about
std::__hash_enum not being constructible. This is confusing when there
is no enum type involved: why should users care about __hash_enum not
being constructible if they're not trying to hash enums?
This change makes the std::hash primary template only derive from
__hash_enum when the template argument type is an enum. Otherwise, it
derives directly from a new class template, __hash_not_enabled. This new
class template defines the deleted members that cause a given std::hash
specialization to be a disabled specialization (as per P0513R0). Now
when users try to use a disabled specialization, they get more
descriptive errors that mention __hash_not_enabled instead of
__hash_enum.
Additionally, adjust __hash_base to remove the deprecated result_type
and argument_type typedefs for C++20 and later.
In the current code we use a __poison_hash base class in the std::hash
specializations for std::unique_ptr, std::optional, and std::variant.
The primary template of __poison_hash has deleted special members, which
is used to conditionally disable the derived std::hash specialization.
This can also result in confusing diagnostics, because seeing "poison"
in an enabled specialization is misleading. Only some uses of
__poison_hash actually "poison" anything, i.e. cause a specialization to
be disabled. In other cases it's just an empty base class that does
nothing.
This change removes __poison_hash and changes the std::hash
specializations that were using it to conditionally derive from
__hash_not_enabled instead. When the std::hash specialization is
enabled, there is no more __poison_hash base class. However, to preserve
the ABI properties of those std::hash specializations, we need to
replace __poison_hash with some other empty base class. This is needed
because in the current code std::hash<std::variant<int, const int>> has
two __poison_hash<int> base classes, which must have unique addresses,
so sizeof(std::hash<std::variant<int, const int>>) == 2. To preserve
this unfortunate property, a new __hash_empty_base class is used as a
base class to re-introduce du0plicate base classes that increase the
class size. For the unstable ABI we don't use __hash_empty_base so the
std::hash<std::variant<T...>> specializations are always size 1, and
the class hierarchy is much simpler so will compile faster.
Additionally, remove the result_type and argument_type typedefs from all
disabled specializations of std::hash for std::unique_ptr,
std::optional, and std::variant. Those typedefs are useless for disabled
specializations, and although the standard doesn't say they must *not*
be present for disabled specializations, it certainly only requires them
for enabled specializations. Finally, for C++20 the typedefs are also
removed from enabled specializations of std::hash for std::unique_ptr,
std::optional, and std::variant.
libstdc++-v3/ChangeLog:
* doc/xml/manual/evolution.xml: Document removal of nested types
from std::hash specializations.
* doc/html/manual/api.html: Regenerate.
* include/bits/functional_hash.h (__hash_base): Remove
deprecated nested types for C++20.
(__hash_empty_base): Define new class template.
(__is_hash_enabled_for): Define new variable template.
(__poison_hash): Remove.
(__hash_not_enabled): Define new class template.
(__hash_enum): Remove partial specialization for non-enums.
(hash): Derive from __hash_not_enabled for non-enums, instead of
__hash_enum.
* include/bits/unique_ptr.h (__uniq_ptr_hash): Derive from
__hash_base. Conditionally derive from __hash_empty_base.
(__uniq_ptr_hash<>): Remove disabled specialization.
(hash): Do not derive from __hash_base unconditionally.
Conditionally derive from either __uniq_ptr_hash or
__hash_not_enabled.
* include/std/optional (__optional_hash_call_base): Remove.
(__optional_hash): Define new class template.
(hash): Derive from either
(hash): Conditionally derive from either __optional_hash or
__hash_not_enabled. Remove nested typedefs.
* include/std/variant (_Base_dedup): Replace __poison_hash with
__hash_empty_base.
(__variant_hash_call_base_impl): Remove.
(__variant_hash): Define new class template.
(hash): Conditionally derive from either __variant_hash or
__hash_not_enabled. Remove nested typedefs.
* testsuite/20_util/optional/hash.cc: Check whether nested types
are present.
* testsuite/20_util/variant/hash.cc: Likewise.
* testsuite/20_util/optional/hash_abi.cc: New test.
* testsuite/20_util/unique_ptr/hash/abi.cc: New test.
* testsuite/20_util/unique_ptr/hash/types.cc: New test.
* testsuite/20_util/variant/hash_abi.cc: New test.
We have two overloads of _M_find_before_node but they have quite
different performance characteristics, which isn't necessarily obvious.
The original version, _M_find_before_node(bucket, key, hash_code), looks
only in the specified bucket, doing a linear search within that bucket
for an element that compares equal to the key. This is the typical fast
lookup for hash containers, assuming the load factor is low so that each
bucket isn't too large.
The newer _M_find_before_node(key) was added in r12-6272-ge3ef832a9e8d6a
and could be naively assumed to calculate the hash code and bucket for
key and then call the efficient _M_find_before_node(bkt, key, code)
function. But in fact it does a linear search of the entire container.
This is potentially very slow and should only be used for a suitably
small container, as determined by the __small_size_threshold() function.
We don't even have a comment pointing out this O(N) performance of the
newer overload.
Additionally, the newer overload is only ever used in exactly one place,
which would suggest it could just be removed. However there are several
places that do the linear search of the whole container with an explicit
loop each time.
This adds a new member function, _M_locate, and uses it to replace most
uses of _M_find_node and the loops doing linear searches. This new
member function does both forms of lookup, the linear search for small
sizes and the _M_find_node(bkt, key, code) lookup within a single
bucket. The new function returns a __location_type which is a struct
that contains a pointer to the first node matching the key (if such a
node is present), or the hash code and bucket index for the key. The
hash code and bucket index allow the caller to know where a new node
with that key should be inserted, for the cases where the lookup didn't
find a matching node.
The result struct actually contains a pointer to the node *before* the
one that was located, as that is needed for it to be useful in erase and
extract members. There is a member function that returns the found node,
i.e. _M_before->_M_nxt downcast to __node_ptr, which should be used in
most cases.
This new function greatly simplifies the functions that currently have
to do two kinds of lookup and explicitly check the current size against
the small size threshold.
Additionally, now that try_emplace is defined directly in _Hashtable
(not in _Insert_base) we can use _M_locate in there too, to speed up
some try_emplace calls. Previously it did not do the small-size linear
search.
It would be possible to add a function to get a __location_type from an
iterator, and then rewrite some functions like _M_erase and
_M_extract_node to take a __location_type parameter. While that might be
conceptually nice, it wouldn't really make the code any simpler or more
readable than it is now. That isn't done in this change.
libstdc++-v3/ChangeLog:
* include/bits/hashtable.h (__location_type): New struct.
(_M_locate): New member function.
(_M_find_before_node(const key_type&)): Remove.
(_M_find_node): Move variable initialization into condition.
(_M_find_node_tr): Likewise.
(operator=(initializer_list<T>), try_emplace, _M_reinsert_node)
(_M_merge_unique, find, erase(const key_type&)): Use _M_locate
for lookup.
I realised that _M_merge_unique and _M_merge_multi call extract(iter)
which then has to call _M_get_previous_node to iterate through the
bucket to find the node before the one iter points to. Since the merge
function is already iterating over the entire container, we had the
previous node a moment ago. Walking the whole bucket to find it again is
wasteful. We could just rewrite the loop in terms of node pointers
instead of iterators, and then call _M_extract_node directly. However,
this is only possible when the source container is the same type as the
destination, because otherwise we can't access the source's private
members (_M_before_begin, _M_begin, _M_extract_node etc.)
Add overloads of _M_merge_unique and _M_merge_multi that work with
source containers of the same type, to enable this optimization.
For both overloads of _M_merge_unique we can also remove the conditional
modifications to __n_elt and just consistently decrement it for every
element processed. Use a multiplier of one or zero that dictates whether
__n_elt is passed to _M_insert_unique_node or not. We can also remove
the repeated calls to size() and just keep track of the size in a local
variable.
Although _M_merge_unique and _M_merge_multi should be safe for
"self-merge", i.e. when doing c.merge(c), it's wasteful to search/insert
every element when we don't need to do anything. Add 'this == &source'
checks to the overloads taking an lvalue of the container's own type.
Because those checks aren't needed for the rvalue overloads, change
those to call the underlying _M_merge_xxx function directly instead of
going through the lvalue overload that checks the address.
I've also added more extensive tests for better coverage of the new
overloads added in this commit.
libstdc++-v3/ChangeLog:
* include/bits/hashtable.h (_M_merge_unique): Add overload for
merging from same type.
(_M_merge_unique<Compatible>): Simplify size tracking. Add
comment.
(_M_merge_multi): Add overload for merging from same type.
(_M_merge_multi<Compatible>): Add comment.
* include/bits/unordered_map.h (unordered_map::merge): Check for
self-merge in the lvalue overload. Call _M_merge_unique directly
for the rvalue overload.
(unordered_multimap::merge): Likewise.
* include/bits/unordered_set.h (unordered_set::merge): Likewise.
(unordered_multiset::merge): Likewise.
* testsuite/23_containers/unordered_map/modifiers/merge.cc:
Add more tests.
* testsuite/23_containers/unordered_multimap/modifiers/merge.cc:
Likewise.
* testsuite/23_containers/unordered_multiset/modifiers/merge.cc:
Likewise.
* testsuite/23_containers/unordered_set/modifiers/merge.cc:
Likewise.
This removes the overloaded _S_equals and _S_node_equals functions,
replacing them with 'if constexpr' in the handful of places they're
used.
libstdc++-v3/ChangeLog:
* include/bits/hashtable_policy.h (_Hashtable_base::_S_equals):
Remove.
(_Hashtable_base::_S_node_equals): Remove.
(_Hashtable_base::_M_key_equals_tr): Fix inaccurate
static_assert string.
(_Hashtable_base::_M_equals, _Hashtable_base::_M_equals_tr): Use
'if constexpr' instead of _S_equals.
(_Hashtable_base::_M_node_equals): Use 'if constexpr' instead of
_S_node_equals.
There's no reason to have a separate base class defining the insert
member functions now. They can all be moved into the _Hashtable class,
which simplifies them slightly.
libstdc++-v3/ChangeLog:
* include/bits/hashtable.h (_Hashtable): Remove inheritance from
__detail::_Insert and move its members into _Hashtable.
* include/bits/hashtable_policy.h (__detail::_Insert): Remove.
Reviewed-by: François Dumont <fdumont@gcc.gnu.org>
Use scoped guard types to clean up if an exception is thrown. This
allows some try-catch blocks to be removed.
libstdc++-v3/ChangeLog:
* include/bits/hashtable.h (operator=(const _Hashtable&)): Use
RAII instead of try-catch.
(_M_assign(_Ht&&, _NodeGenerator&)): Likewise.
Reviewed-by: François Dumont <fdumont@gcc.gnu.org>
We can just use a cast to the appropriate type instead of calling a
function to do it. This gives the compiler less work to compile and
optimize, and at -O0 avoids a function call per element.
libstdc++-v3/ChangeLog:
* include/bits/hashtable.h (_Hashtable::__fwd_value_for):
Remove.
(_Hashtable::_M_assign): Use static_cast instead of
__fwd_value_for.
Reviewed-by: François Dumont <fdumont@gcc.gnu.org>
This adds a convenient _M_assign overload for the common case where the
node generator is the _AllocNode type. Only two places need to call
_M_assign with a _ReuseOrAllocNode node generator, so all the other
calls to _M_assign can use the new overload instead of manually
constructing a node generator.
The _AllocNode::operator(Args&&...) function doesn't need to be a
variadic template. It is only ever called with a single argument of type
const value_type& or value_type&&, so could be simplified. That isn't
done in this commit.
libstdc++-v3/ChangeLog:
* include/bits/hashtable.h (_Hashtable): Remove typedefs for
node generators.
(_Hashtable::_M_assign(_Ht&&)): Add new overload.
(_Hashtable::operator=(initializer_list<value_type>)): Add local
typedef for node generator.
(_Hashtable::_M_assign_elements): Likewise.
(_Hashtable::operator=(const _Hashtable&)): Use new _M_assign
overload.
(_Hashtable(const _Hashtable&)): Likewise.
(_Hashtable(const _Hashtable&, const allocator_type&)):
Likewise.
(_Hashtable(_Hashtable&&, __node_alloc_type&&, false_type)):
Likewise.
* include/bits/hashtable_policy.h (_Insert): Remove typedef for
node generator.
Reviewed-by: François Dumont <fdumont@gcc.gnu.org>
This reworks the internal member functions for erasure from
unordered containers, similarly to the earlier commit doing it for
insertion.
Instead of multiple overloads of _M_erase which are selected via tag
dispatching, the erase(const key_type&) member can use 'if constexpr' to
choose an appropriate implementation (returning after erasing a single
element for unique keys, or continuing to erase all equivalent elements
for non-unique keys).
libstdc++-v3/ChangeLog:
* include/bits/hashtable.h (_Hashtable::_M_erase): Remove
overloads for erasing by key, moving logic to ...
(_Hashtable::erase): ... here.
Reviewed-by: François Dumont <fdumont@gcc.gnu.org>
This completely reworks the internal member functions for insertion into
unordered containers. Currently we use a mixture of tag dispatching (for
unique vs non-unique keys) and template specialization (for maps vs
sets) to correctly implement insert and emplace members.
This removes a lot of complexity and indirection by using 'if constexpr'
to select the appropriate member function to call.
Previously there were four overloads of _M_emplace, for unique keys and
non-unique keys, and for hinted insertion and non-hinted. However two of
those were redundant, because we always ignore the hint for unique keys
and always use a hint for non-unique keys. Those four overloads have
been replaced by two new non-overloaded function templates:
_M_emplace_uniq and _M_emplace_multi. The former is for unique keys and
doesn't take a hint, and the latter is for non-unique keys and takes a
hint.
In the body of _M_emplace_uniq there are special cases to handle
emplacing values from which a key_type can be extracted directly. This
means we don't need to allocate a node and construct a value_type that
might be discarded if an equivalent key is already present. The special
case applies when emplacing the key_type into std::unordered_set, or
when emplacing std::pair<cv key_type, X> into std::unordered_map, or
when emplacing two values into std::unordered_map where the first has
type cv key_type. For the std::unordered_set case, obviously if we're
inserting something that's already the key_type, we can look it up
directly. For the std::unordered_map cases, we know that the inserted
std::pair<const key_type, mapped_type> would have its first element
initialized from first member of a std::pair value, or from the first of
two values, so if that is a key_type, we can look that up directly.
All the _M_insert overloads used a node generator parameter, but apart
from the one case where _M_insert_range was called from
_Hashtable::operator=(initializer_list<value_type>), that parameter was
always the _AllocNode type, never the _ReuseOrAllocNode type. Because
operator=(initializer_list<value_type>) was rewritten in an earlier
commit, all calls to _M_insert now use _AllocNode, so there's no reason
to pass the generator as a template parameter when inserting.
The multiple overloads of _Hashtable::_M_insert can all be removed now,
because the _Insert_base::insert members now call either _M_emplace_uniq
or _M_emplace_multi directly, only passing a hint to the latter. Which
one to call is decided using 'if constexpr (__unique_keys::value)' so
there is no unnecessary code instantiation, and overload resolution is
much simpler.
The partial specializations of the _Insert class template can be
entirely removed, moving the minor differences in 'insert' member
functions into the common _Insert_base base class. The different
behaviour for maps and sets can be implemented using enable_if
constraints and 'if constexpr'. With the _Insert class template no
longer needed, the _Insert_base class template can be renamed to
_Insert. This is a minor simplification for the complex inheritance
hierarchy used by _Hashtable, removing one base class. It also means
one less class template instantiation, and no need to match the right
partial specialization of _Insert. The _Insert base class could be
removed entirely by moving all its 'insert' members into _Hashtable,
because without any variation in specializations of _Insert there is no
reason to use a base class to define those members. That is left for a
later commit.
Consistently using _M_emplace_uniq or _M_emplace_multi for insertion
means we no longer attempt to avoid constructing a value_type object to
find its key, removing the PR libstdc++/96088 optimizations. This fixes
the bugs caused by those optimizations, such as PR libstdc++/115285, but
causes regressions in the expected number of allocations and temporary
objects constructed for the PR 96088 tests. It should be noted that the
"regressions" in the 96088 tests put us exactly level with the number of
allocations done by libc++ for those same tests.
To mitigate this to some extent, _M_emplace_uniq detects when the
emplace arguments already contain a key_type (either as the sole
argument, for unordered_set, or as the first part of a pair of
arguments, for unordered_map). In that specific case we don't need to
allocate a node and construct a value type to check for an existing
element with equivalent key.
The remaining regressions in the number of allocations and temporaries
should be addressed separately, with more conservative optimizations
specific to std::string. That is not part of this commit.
libstdc++-v3/ChangeLog:
PR libstdc++/115285
* include/bits/hashtable.h (_Hashtable::_M_emplace): Replace
with _M_emplace_uniq and _M_emplace_multi.
(_Hashtable::_S_forward_key, _Hashtable::_M_insert_unique)
(_Hashtable::_M_insert_unique_aux, _Hashtable::_M_insert):
Remove.
* include/bits/hashtable_policy.h (_ConvertToValueType):
Remove.
(_Insert_base::_M_insert_range): Remove overload for unique keys
and rename overload for non-unique keys to ...
(_Insert_base::_M_insert_range_multi): ... this.
(_Insert_base::insert): Call _M_emplace_uniq or _M_emplace_multi
instead of _M_insert. Add insert overloads from _Insert.
(_Insert_base): Rename to _Insert.
(_Insert): Remove
* testsuite/23_containers/unordered_map/96088.cc: Adjust
expected number of allocations.
* testsuite/23_containers/unordered_set/96088.cc: Likewise.
Currently the _ReuseOrAllocNode::operator(Args&&...) function always
destroys the value stored in recycled nodes and constructs a new value.
The _ReuseOrAllocNode type is only ever used for implementing
assignment, either from another unordered container of the same type, or
from std::initializer_list<value_type>. Consequently, the parameter pack
Args only ever consists of a single parameter or type const value_type&
or value_type. We can replace the variadic parameter pack with a single
forwarding reference parameter, and when the value_type is assignable
from that type we can use assignment instead of destroying the existing
value and then constructing a new one.
Using assignment is typically only possible for sets, because for maps
the value_type is std::pair<const key_type, mapped_type> and in most
cases std::is_assignable_v<const key_type&, const key_type&> is false.
libstdc++-v3/ChangeLog:
* include/bits/hashtable_policy.h (_ReuseOrAllocNode::operator()):
Replace parameter pack with a single parameter. Assign to
existing value when possible.
* testsuite/23_containers/unordered_multiset/allocator/move_assign.cc:
Adjust expected count of operations.
* testsuite/23_containers/unordered_set/allocator/move_assign.cc:
Likewise.
Reviewed-by: François Dumont <fdumont@gcc.gnu.org>
This replaces a call to _M_insert_range with open coding the loop. This
will allow removing the node generator parameter from _M_insert_range in
a later commit.
libstdc++-v3/ChangeLog:
* include/bits/hashtable.h (operator=(initializer_list)):
Refactor to not use _M_insert_range.
Reviewed-by: François Dumont <fdumont@gcc.gnu.org>
The std::logic_error exceptions thrown from misuses of
std::wbuffer_convert and std::wstring_convert should use names qualified
with "std::".
libstdc++-v3/ChangeLog:
* include/bits/locale_conv.h (wstring_convert, wbuffer_convert):
Adjust strings passed to exception constructors.
The intended behaviour for std::text_encoding::aliases_view's iterator
is that it incrementing or decrementing too far sets it to a
value-initialized state, or fails an assertion when those are enabled.
There were typos that used == instead of = which meant that instead of
becoming singular or aborting, an out-of-range increment just did
nothing. This meant erroneous operations were well-defined and didn't
produce any undefined behaviour, but were not diagnosed with assertions
enabled, as had been intended.
This change fixes the bugs and adds more tests to verify the intended
behaviour.
libstdc++-v3/ChangeLog:
PR libstdc++/117520
* include/std/text_encoding (aliases_view:_Iterator::operator+=):
Fix typos that caused == to be used instead of =.
(aliases_view::_Iterator): Fix friend declaration.
* testsuite/std/text_encoding/members.cc: Adjust expected
behaviour of invalid subscript. Add tests for other erroneous
operations on iterators.
libstdc++-v3/ChangeLog:
* include/bits/hashtable.h (_Hashtable): Add 'inline' to some
one-line constructors.
Reviewed-by: François Dumont <fdumont@gcc.gnu.org>
This is not a reserved name in C++11 and C++14, so must not be defined.
Also use the appropriate feature test macros for the try_emplace members
of the Debug Mode maps.
libstdc++-v3/ChangeLog:
* include/bits/hashtable_policy.h (_Insert_base::try_emplace):
Do not define for C++11 and C++14.
* include/debug/map.h (try_emplace): Use feature test macro.
* include/debug/unordered_map (try_emplace): Likewise.
* testsuite/17_intro/names.cc: Define try_emplace before C++17.
This uses 'if constexpr' instead of tag dispatching, removing the need
for a second call using that tag, and simplifying the overload set that
needs to be resolved for calls to __distance_fw.
libstdc++-v3/ChangeLog:
* include/bits/hashtable_policy.h (__distance_fw): Replace tag
dispatching with 'if constexpr'.
Clarify the effects if rehashing is needed. Document the __n_elt
parameter.
libstdc++-v3/ChangeLog:
* include/bits/hashtable.h (_M_insert_unique_node): Improve
comment.
The conversions to key_type and value_type that are performed when
inserting into _Hashtable need to be fixed to do any required
conversions explicitly. The current code assumes that conversions from
the parameter to the key_type or value_type can be done implicitly,
which isn't necessarily true.
Remove the _S_forward_key function which doesn't handle all cases and
either forward the parameter if it already has type cv key_type, or
explicitly construct a temporary of type key_type.
Similarly, the _ConvertToValueType specialization for maps doesn't
handle all cases either, for std::pair arguments only some value
categories are handled. Remove _ConvertToValueType and for the _M_insert
function for unique keys, either forward the argument unchanged or
explicitly construct a temporary of type value_type.
For the _M_insert overload for non-unique keys we don't need any
conversion at all, we can just forward the argument directly to where we
construct a node.
libstdc++-v3/ChangeLog:
PR libstdc++/115285
* include/bits/hashtable.h (_Hashtable::_S_forward_key): Remove.
(_Hashtable::_M_insert_unique_aux): Replace _S_forward_key with
a static_cast to a type defined using conditional_t.
(_Hashtable::_M_insert): Replace _ConvertToValueType with a
static_cast to a type defined using conditional_t.
* include/bits/hashtable_policy.h (_ConvertToValueType): Remove.
* testsuite/23_containers/unordered_map/insert/115285.cc: New test.
* testsuite/23_containers/unordered_set/insert/115285.cc: New test.
* testsuite/23_containers/unordered_set/96088.cc: Adjust
expected number of allocations.
std::is_permutation is only used in <bits/hashtable.h> not in
<bits/hashtable_policy.h>, so move the comment referring to it.
libstdc++-v3/ChangeLog:
* include/bits/hashtable.h: Add is_permutation to comment.
* include/bits/hashtable_policy.h: Remove it from comment.
These headers make no sense for C++ programs, because they either define
different content to the corresponding <xxx.h> C header, or define
nothing at all in namespace std. They were all deprecated in C++17, so
add deprecation warnings to them, which can be disabled with
-Wno-deprecated. For C++20 and later these headers are no longer in the
standard at all, so compiling with _GLIBCXX_USE_DEPRECATED defined to 0
will give an error when they are included.
Because #warning is non-standard before C++23 we need to use pragmas to
ignore -Wc++23-extensions for the -Wsystem-headers -pedantic case.
One g++ test needs adjustment because it includes <ciso646>, but that
can be made conditional on the __cplusplus value without any reduction
in test coverage.
For the library tests, consolidate the std_c++0x_neg.cc XFAIL tests into
the macros.cc test, using dg-error with a { target c++98_only }
selector. This avoids having two separate test files, one for C++98 and
one for everything later. Also add tests for the <xxx.h> headers to
ensure that they behave as expected and don't give deprecated warnings.
libstdc++-v3/ChangeLog:
* doc/xml/manual/evolution.xml: Document deprecations.
* doc/html/*: Regenerate.
* include/c_compatibility/complex.h (_GLIBCXX_COMPLEX_H): Move
include guard to start of file. Include <complex> directly
instead of <ccomplex>.
* include/c_compatibility/tgmath.h: Include <cmath> and
<complex> directly, instead of <ctgmath>.
* include/c_global/ccomplex: Add deprecated #warning for C++17
and #error for C++20 if _GLIBCXX_USE_DEPRECATED == 0.
* include/c_global/ciso646: Likewise.
* include/c_global/cstdalign: Likewise.
* include/c_global/cstdbool: Likewise.
* include/c_global/ctgmath: Likewise.
* include/c_std/ciso646: Likewise.
* include/precompiled/stdc++.h: Do not include ccomplex,
ciso646, cstdalign, cstdbool, or ctgmath in C++17 and later.
* testsuite/18_support/headers/cstdalign/macros.cc: Check for
warnings and errors for unsupported dialects.
* testsuite/18_support/headers/cstdbool/macros.cc: Likewise.
* testsuite/26_numerics/headers/ctgmath/complex.cc: Likewise.
* testsuite/27_io/objects/char/1.cc: Do not include <ciso646>.
* testsuite/27_io/objects/wchar_t/1.cc: Likewise.
* testsuite/18_support/headers/cstdbool/std_c++0x_neg.cc: Removed.
* testsuite/18_support/headers/cstdalign/std_c++0x_neg.cc: Removed.
* testsuite/26_numerics/headers/ccomplex/std_c++0x_neg.cc: Removed.
* testsuite/26_numerics/headers/ctgmath/std_c++0x_neg.cc: Removed.
* testsuite/18_support/headers/ciso646/macros.cc: New test.
* testsuite/18_support/headers/ciso646/macros.h.cc: New test.
* testsuite/18_support/headers/cstdbool/macros.h.cc: New test.
* testsuite/26_numerics/headers/ccomplex/complex.cc: New test.
* testsuite/26_numerics/headers/ccomplex/complex.h.cc: New test.
* testsuite/26_numerics/headers/ctgmath/complex.h.cc: New test.
gcc/testsuite/ChangeLog:
* g++.old-deja/g++.other/headers1.C: Do not include ciso646 for
C++17 and later.
libstdc++-v3/ChangeLog:
* include/c_compatibility/complex.h (_GLIBCXX_COMPLEX_H): Move
include guard to start of the header.
* include/c_global/ctgmath (_GLIBCXX_CTGMATH): Likewise.
Currently dereferencing an empty shared_ptr prints a complicated
internal type in the assertion message:
include/bits/shared_ptr_base.h:1377: std::__shared_ptr_access<_Tp, _Lp, <anonymous>, <anonymous> >::element_type& std::__shared_ptr_access<_Tp, _Lp, <anonymous>, <anonymous> >::operator*() const [with _Tp = std::filesystem::__cxx11::recursive_directory_iterator::_Dir_stack; __gnu_cxx::_Lock_policy _Lp = __gnu_cxx::_S_atomic; bool <anonymous> = false; bool <anonymous> = false; element_type = std::filesystem::__cxx11::recursive_directory_iterator::_Dir_stack]: Assertion '_M_get() != nullptr' failed.
Users don't care about any of the _Lp and <anonymous> template
parameters, so this is unnecessarily verbose.
We can simplify it to something that only mentions "shared_ptr_deref"
and the element type:
include/bits/shared_ptr_base.h:1371: _Tp* std::__shared_ptr_deref(_Tp*) [with _Tp = filesystem::__cxx11::recursive_directory_iterator::_Dir_stack]: Assertion '__p != nullptr' failed.
libstdc++-v3/ChangeLog:
* include/bits/shared_ptr_base.h (__shared_ptr_deref): New
function template.
(__shared_ptr_access, __shared_ptr_access<>): Use it.
These overloads incorrectly cast the result of the float __builtin_*
to _Float or __gnu_cxx::__bfloat16_t. For std::ilogb that changes
behavior for the INT_MAX return because that isn't representable in
either of the floating point formats, for the others it is I think
just a very inefficient hop from int/long/long long to std::{,b}float16_t
and back. I mean for the round/rint cases, either the argument is small
and then the return value should be representable in the floating point
format too, or it is too large that the argument is already integral
and then it should just return the argument with the round trips.
Too large value is unspecified unlike ilogb.
2024-11-02 Jakub Jelinek <jakub@redhat.com>
PR libstdc++/117406
* include/c_global/cmath (std::ilogb(_Float16), std::llrint(_Float16),
std::llround(_Float16), std::lrint(_Float16), std::lround(_Float16)):
Don't cast __builtin_* return to _Float16.
(std::ilogb(__gnu_cxx::__bfloat16_t),
std::llrint(__gnu_cxx::__bfloat16_t),
std::llround(__gnu_cxx::__bfloat16_t),
std::lrint(__gnu_cxx::__bfloat16_t),
std::lround(__gnu_cxx::__bfloat16_t)): Don't cast __builtin_* return to
__gnu_cxx::__bfloat16_t.
* testsuite/26_numerics/headers/cmath/117406.cc: New test.
Replace some `__cplusplus > 201402L` preprocessor checks with more
expressive checks for the appropriate feature test macros.
libstdc++-v3/ChangeLog:
* include/bits/unordered_map.h: Check __glibcxx_node_extract and
__glibcxx_unordered_map_try_emplace instead of __cplusplus.
* include/bits/unordered_set.h: Check __glibcxx_node_extract
instead of __cplusplus.
