aboutsummaryrefslogtreecommitdiff
path: root/libstdc++-v3/include/bits/hashtable.h
AgeCommit message (Collapse)AuthorFilesLines
2021-10-21libstdc++: Suppress Doxygen docs for more implementation detailsJonathan Wakely1-0/+2
libstdc++-v3/ChangeLog: * include/bits/alloc_traits.h: Suppress doxygen documentation. * include/bits/allocated_ptr.h: Likewise. * include/bits/enable_special_members.h: Likewise. * include/bits/hashtable.h: Likewise. * include/bits/hashtable_policy.h: Likewise. * include/bits/uses_allocator.h: Likewise. * include/bits/node_handle.h: Document node handles and suppress documentation for protected members. * include/std/any: Suppress documentation for implementation details.
2021-10-09libstdc++: Avoid instantiation of _Hash_node before it's neededJonathan Wakely1-8/+9
This is a step towards restoring support for incomplete types in unordered containers (PR 53339). We do not need to instantiate the node type to get its value_type member, because we know that the value type is the first template parameter. We can deduce that template argument using a custom trait and a partial specialization for _Hash_node. If we wanted to support custom hash node types we could still use typename _Tp::value_type in the primary template of that trait, but that seems unnecessary. The other change needed is to defer a static assert at class scope, so that it is done when the types are complete. We must have a complete type in the destructor, so we can do it there instead. libstdc++-v3/ChangeLog: * include/bits/hashtable.h: Move static assertion to destructor. * include/bits/hashtable_policy.h: Deduce value type from node type without instantiating it.
2021-10-01libstdc++: Add std::__conditional_t alias templateJonathan Wakely1-7/+7
This change is inspired by the suggestion in http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1715r0.html The new std::__conditional_t alias template is functionally equivalent to std::conditional_t but should be more efficient to compile, due to only ever instantiating two specializations (std::__conditional<true> and std::__conditional<false>) rather than a new specialization for every use of std::conditional. The new alias template is also available in C++11, unlike the C++14 std::conditional_t alias. Signed-off-by: Jonathan Wakely <jwakely@redhat.com> libstdc++-v3/ChangeLog: * include/std/type_traits (__conditional): New class template for internal uses of std::conditional. (__conditional_t): New alias template to replace conditional_t. (__and_, __or_, __result_of_memfun, __result_of_memobj): Use __conditional_t instead of conditional::type. * include/bits/atomic_base.h (__atomic_impl::_Diff): Likewise. * include/bits/hashtable.h (_Hashtable): Likewise. * include/bits/hashtable_policy.h (_Node_iterator, _Insert_base) (_Local_iterator): Likewise. Replace typedefs with using-declarations. * include/bits/move.h (move_if_noexcept): Use __conditional_t. * include/bits/parse_numbers.h (_Select_int_base): Likewise. * include/bits/ptr_traits.h (__make_not_void): Likewise. * include/bits/ranges_algobase.h (__copy_or_move_backward) (__copy_or_move): Likewise. * include/bits/ranges_base.h (borrowed_iterator_t): Likewise. * include/bits/ranges_util.h (borrowed_subrange_t): Likewise. * include/bits/regex_compiler.h (_BracketMatcher): Use __conditional_t. Replace typedefs with using-declarations. * include/bits/shared_ptr_base.h (__shared_count): Use __conditional_t. * include/bits/stl_algobase.h (__copy_move, __copy_move_backward): Likewise. * include/bits/stl_iterator.h (__detail::__clamp_iter_cat) (reverse_iterator::iterator_concept) (__make_move_if_noexcept_iterator) (iterator_traits<common_iterator<_It, _Sent>>) (iterator_traits<counted_iterator<_It>>): Likewise. * include/bits/stl_pair.h (_PCC, pair::operator=): Likewise. * include/bits/stl_tree.h (_Rb_tree::insert_return_type) (_Rb_tree::_M_clone_node): Likewise. * include/bits/unique_ptr.h (unique_ptr(unique_ptr<U,E>&&)): Likewise. * include/bits/uses_allocator.h (__uses_alloc): Likewise. (__is_uses_allocator_predicate): Likewise. * include/debug/functions.h (__foreign_iterator_aux2): Likewise. * include/experimental/any (any::_Manager, __any_caster): Likewise. * include/experimental/executor (async_completion): Likewise. * include/experimental/functional (__boyer_moore_base_t): Likewise. * include/std/any (any::_Manager): Likewise. * include/std/functional (__boyer_moore_base_t): Likewise. * include/std/ranges (borrowed_iterator_t) (borrowed_subrange_t, __detail::__maybe_present_t) (__detail::__maybe_const_t, split_view): Likewise. * include/std/tuple (__empty_not_final, tuple::operator=): Likewise. * include/std/variant (__detail::__variant::__get_t): Likewise.
2021-07-22libstdc++: Fix non-default constructors for hash containers [PR101583]Jonathan Wakely1-5/+12
When I added the new mixin to _Hashtable, I forgot to explicitly construct it in each non-default constructor. That means you can't use any constructors unless all three of the hash function, equality function, and allocator are all default constructible. libstdc++-v3/ChangeLog: PR libstdc++/101583 * include/bits/hashtable.h (_Hashtable): Replace mixin with _Enable_default_ctor. Construct it explicitly in all non-forwarding, non-defaulted constructors. * testsuite/23_containers/unordered_map/cons/default.cc: Check non-default constructors can be used. * testsuite/23_containers/unordered_set/cons/default.cc: Likewise.
2021-07-20libstdc++: fix is_default_constructible for hash containers [PR 100863]Jonathan Wakely1-1/+14
The recent change to _Hashtable_ebo_helper for this PR broke the is_default_constructible trait for a hash container with a non-default constructible allocator. That happens because the constructor needs to be user-provided in order to initialize the member, and so is not defined as deleted when the type is not default constructible. By making _Hashtable derive from _Enable_special_members we can ensure that the default constructor for the std::unordered_xxx containers is deleted when it would be ill-formed. This makes the trait give the correct answer. Signed-off-by: Jonathan Wakely <jwakely@redhat.com> libstdc++-v3/ChangeLog: PR libstdc++/100863 * include/bits/hashtable.h (_Hashtable): Conditionally delete default constructor by deriving from _Enable_special_members. * testsuite/23_containers/unordered_map/cons/default.cc: New test. * testsuite/23_containers/unordered_set/cons/default.cc: New test.
2021-06-04libstdc++: Add feature test macro for heterogeneous lookup in unordered ↵Jonathan Wakely1-2/+4
containers Also update the C++20 status docs. Signed-off-by: Jonathan Wakely <jwakely@redhat.com> libstdc++-v3/ChangeLog: * doc/xml/manual/status_cxx2020.xml: * doc/html/*: Regenerate. * include/bits/hashtable.h (__cpp_lib_generic_unordered_lookup): Define. * include/std/version (__cpp_lib_generic_unordered_lookup): Define. * testsuite/23_containers/unordered_map/operations/1.cc: Check feature test macro. * testsuite/23_containers/unordered_set/operations/1.cc: Likewise.
2021-05-24libstdc++: Limit allocation on iterator insertion in Hashtable [PR 96088]François Dumont1-13/+46
When inserting into unordered_multiset or unordered_multimap first instantiate the node to store and compute the hash code from it to avoid a potential intermediate key_type instantiation. When inserting into unordered_set or unordered_map check if invoking the hash functor with container key_type is noexcept and invoking the same hash functor with key part of the iterator value_type can throw. In this case create a temporary key_type instance at Hashtable level and use it to compute the hash code. This temporary instance is moved to the final storage location if needed. libstdc++-v3/ChangeLog: PR libstdc++/96088 * include/bits/hashtable_policy.h (_Select2nd): New. (_NodeBuilder<>): New. (_ReuseOrAllocNode<>::operator()): Use variadic template args. (_AllocNode<>::operator()): Likewise. * include/bits/hashtable.h (_Hashtable<>::__node_builder_t): New. (_Hashtable<>::_M_insert_unique<>(_Kt&&, _Arg&&, const _NodeGenerator&)): New. (_Hashtable<>::_S_forward_key): New. (_Hashtable<>::_M_insert): Use latter. (_Hashtable<>::_M_insert(const_iterator, _Arg&&, const _NodeGenerator&, false_type)): Instantiate node first, compute hash code second. * testsuite/23_containers/unordered_map/96088.cc: New test. * testsuite/23_containers/unordered_multimap/96088.cc: New test. * testsuite/23_containers/unordered_multiset/96088.cc: New test. * testsuite/23_containers/unordered_set/96088.cc: New test. * testsuite/util/replacement_memory_operators.h (counter::_M_increment): New. (counter::_M_decrement): New. (counter::reset()): New.
2021-04-09libstdc++: Fix invalid constexpr function in C++11 mode [PR 99985]Jonathan Wakely1-2/+8
I keep forgetting that a constexpr function in C++11 has to be a single return statement. libstdc++-v3/ChangeLog: PR libstdc++/99985 * include/bits/hashtable.h (_Hashtable::_S_nothrow_move()): Fix to be a valid constexpr function in C++11. * testsuite/23_containers/unordered_set/cons/99985.cc: New test.
2021-04-08libstdc++: Simplify noexcept-specifiers for move constructorsJonathan Wakely1-12/+14
This puts the logic for the noexcept-specifier in one place, and then reuses it elsewhere. This means checking whether the move constructor can throw doesn't need to do overload resolution and then check whether some other constructor can throw, we just get the answer directly. libstdc++-v3/ChangeLog: * include/bits/hashtable.h (_Hashtable::_S_nothrow_move()): New function to determine noexcept-specifier for move constructors. (_Hashtable): Use _S_nothrow_move() on move constructors. * testsuite/23_containers/unordered_map/cons/noexcept_move_construct.cc: Correct static assertion message. * testsuite/23_containers/unordered_multimap/cons/noexcept_move_construct.cc: Likewise. * testsuite/23_containers/unordered_multiset/cons/noexcept_move_construct.cc: Likewise. * testsuite/23_containers/unordered_set/cons/noexcept_move_construct.cc: Likewise.
2021-02-09libstdc++: Add unordered containers heterogeneous lookupFrançois Dumont1-0/+201
Add unordered containers heterogeneous lookup member functions find, count, contains and equal_range in C++20. Those members are considered for overload resolution only if hash and equal functors used to instantiate the container have a nested is_transparent type. libstdc++-v3/ChangeLog: * include/bits/stl_tree.h (__has_is_transparent, __has_is_transparent_t): Move... * include/bits/stl_function.h: ...here. * include/bits/hashtable_policy.h (_Hash_code_base<>::_M_hash_code_tr): New.. (_Hashtable_base<>::_M_equals_tr): New. * include/bits/hashtable.h (_Hashtable<>::_M_find_tr, _Hashtable<>::_M_count_tr, _Hashtable<>::_M_equal_range_tr): New member function templates to perform heterogeneous lookup. (_Hashtable<>::_M_find_before_node_tr): New. (_Hashtable<>::_M_find_node_tr): New. * include/bits/unordered_map.h (unordered_map::find<>, unordered_map::count<>, unordered_map::contains<>, unordered_map::equal_range<>): New member function templates to perform heterogeneous lookup. (unordered_multimap::find<>, unordered_multimap::count<>, unordered_multimap::contains<>, unordered_multimap::equal_range<>): Likewise. * include/bits/unordered_set.h (unordered_set::find<>, unordered_set::count<>, unordered_set::contains<>, unordered_set::equal_range<>): Likewise. (unordered_multiset::find<>, unordered_multiset::count<>, unordered_multiset::contains<>, unordered_multiset::equal_range<>): Likewise. * include/debug/unordered_map (unordered_map::find<>, unordered_map::equal_range<>): Likewise. (unordered_multimap::find<>, unordered_multimap::equal_range<>): Likewise. * include/debug/unordered_set (unordered_set::find<>, unordered_set::equal_range<>): Likewise. (unordered_multiset::find<>, unordered_multiset::equal_range<>): Likewise. * testsuite/23_containers/unordered_map/operations/1.cc: New test. * testsuite/23_containers/unordered_multimap/operations/1.cc: New test. * testsuite/23_containers/unordered_multiset/operations/1.cc: New test. * testsuite/23_containers/unordered_set/operations/1.cc: New test.
2021-01-04Update copyright years.Jakub Jelinek1-1/+1
2020-10-20libstdc++: Refactor _Hashtable to prepare for custom pointersFrançois Dumont1-117/+134
Limit usage of node pointers in _Hashtable implementation details so that when we move to allocator custom pointer type we do not need to add an _Alloc template parameter everywhere which would impact abi. This is done by reviewing node type definition. It is now based on new basic types which are not pointer dependant. The _Hashtable helper types are now using those new node base types and do not receive node pointers. libstdc++-v3/ChangeLog * include/bits/hashtable_policy.h (_Hash_node_value_base<>): Remove _Hash_node_base inheritance. (_Hash_node_code_cache<bool _Cache_hash_code>): New. (_Hash_node_value<typename _Value, bool _Cache_hash_code>): New. (_Hash_node<>): Inherits _Hash_node_base<> and _Hash_node_value<>. (_Map_base<>::__node_type): Remove. (_Map_base<>::iterator): Remove. (_Insert_base<>::__hash_cached): New. (_Insert_base<>::__constant_iterators): New. (_Insert_base<>::__hashtable_alloc): New. (_Insert_base<>::__node_type): Remove. (_Insert_base<>::__node_ptr): New. (_Hash_code_base<>): Remove specializations. (_Hash_code_base<>::__node_type): Remove. (_Hash_code_base<>::_M_bucket_index(const __node_type*, size_t)): Replace by... (_Hash_code_base<>::_M_bucket_index(const _Hash_node_value<>&, size_t)): ...this. (_Hash_code_base<>::_M_store_code(__node_type*, __hash_code)): Replace by... (_Hash_code_base<>::_M_store_code(_Hash_node_code_cache<>&, __hash_code)): ...this. (_Hash_code_base<>::_M_copy_code(__node_type*, const __node_type*)): Replace by... (_Hash_code_base<>::_M_copy_code(_Hash_node_code_cache<>&, const _Hash_node_code_base<>&)): ...this. (_Hashtable_base<>::__constant_iterators): Remove. (_Hashtable_base<>::__unique_keys): Remove. (_Hashtable_base<>::__node_type): Remove. (_Hashtable_base<>::iterator): Remove. (_Hashtable_base<>::const_iterator): Remove. (_Hashtable_base<>::local_iterator): Remove. (_Hashtable_base<>::const_local_iterator): Remove. (_Hashtable_base<>::__ireturn_type): Remove. (_Hashtable_base<>::_Equal_hash_code<>::_S_equals): Replace by... (_Hashtable_base<>::_S_equals(__hash_code, const _Hash_node_code_hash<>&)): ...this. (_Hashtable_base<>::_Equal_hash_code<>::_S_node_equals): Replace by... (_Hashtable_base<>::_S_node_equals(__hash_code, const _Hash_node_code_hash<>&)): ...this. (_Hashtable_base<>::_Equal_hash_code<>): Remove. (_Hashtable_base<>::_M_equals): Adapt. (_Hashtable_baxe<>::_M_node_equals): Adapt. (_Equality<>::_M_equal): Adapt. (_Hashtable_alloc<>::__node_ptr): New. (_Hashtable_alloc<>::__bucket_type): Rename into... (_Hashtable_alloc<>::__node_base_ptr): ...this. (_Hashtable_alloc<>::__bucket_alloc_type): Rename into... (_Hashtable_alloc<>::__buckets_alloc_type): ...this. (_Hashtable_alloc<>::__bucket_alloc_traits): Rename into... (_Hashtable_alloc<>::__buckets_alloc_traits): ...this. (_Hashtable_alloc<>::__buckets_ptr): New. (_Hashtable_alloc<>::_M_allocate_node): Adapt. (_Hashtable_alloc<>::_M_deallocate_node): Adapt. (_Hashtable_alloc<>::_M_deallocate_node_ptr): Adapt. (_Hashtable_alloc<>::_M_deallocate_nodes): Adapt. (_Hashtable_alloc<>::_M_allocate_buckets): Adapt. (_Hashtable_alloc<>::_M_deallocate_buckets): Adapt. * include/bits/hashtable.h (_Hashtable<>): Adapt.
2020-08-26libstdc++: Rename _Hashtable _H1, _H2 and _Hash template parametersFrançois Dumont1-362/+330
Limit our _Hashtable implementation to ranged hash. _H1 is now rename to _Hash matching the _Hash functor used for unordered containers. _H2 is now renamed to _RangeHash. Former _Hash simply becomes _Unused. Remove _ExtractKey storage. libstdc++-v3/ChangeLog: * include/bits/hashtable_policy.h (_Hashtable<>): Rename _H1 into _Hash _H2 into _RangeHash and _Hash into _Unused. (_Hastable_base<>): Likewise. (_Map_base<>): Likewise. (_Insert_base<>): Likewise. (_Insert<>): Likewise. (_Rehash_base<>): Likewise. (_Local_iterator_base<>): Likewise. (_Hash_code_base<>): Likewise. (_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, false>): Remove. (_Hash_code_base<_Key, _Value, _ExtractKey, _H1, _H2, _Hash, true>): Remove. (_Hash_code_base<_Key, _Value, _ExtractKey, _Hash, _RangeHas, _Unused, bool>): Remove _Hashtable_ebo_helper<2, _RangeHash> base type.. (_Hash_code_base<>::_M_bucket_index(const _Key&, __hash_code, size_t)): Replace by... (_Hash_code_base<>::_M_bucket_index(__hash_code, size_t)): ...this. (_Local_iterator<>): Remove _H1 and _H2 template parameters. (_Local_const_iterator<>): Likewise. (_Equality<>): Likewise. (_Map_base<>::operator[](const key_type&): Adapt. (_Map_base<>::operator[](key_type&&): Adapt. (_Identity::operator()): Add noexcept. (_Select1st::operator()): Likewise. (_Hash_code_base<>): Remove _Hashtable_ebo_helper<0, _ExtractKey> base type. (_Hash_code_base::_M_extract): Remove. * include/bits/hashtable.h (_Hashtable<>): Remove _H1 and _H2 template parameters. Remove _ExtractKey from constructors. (_Hashtable<>::_M_insert_unique_node(const key_type&, size_t, __hash_code, __node_type*, size_t)): Replace by... (_Hashtable<>::_M_insert_unique_node(size_t, __hash_code, __node_type*, size_t)): ...this. (_Hashtable<>::_M_insert_muti_node(__node_type*, const key_type&, __hash_code, __node_type*)): Replace by... (_Hashtable<>::_M_insert_multi_node(__node_type*, __hash_code, __node_type*)): ...this. (_Hashtable<>::__key_extract): Remove. * include/bits/node_handle.h: Adapt.
2020-08-12libstdc++: Make self-move well-defined for containers [PR 85828]Jonathan Wakely1-0/+3
The C++ LWG recently confirmed that self-move assignment should not have undefined behaviour for standard containers (see the proposed resolution of LWG 2839). The result should be a valid but unspecified value, just like other times when a container is moved from. Our std::list, std::__cxx11::basic_string and unordered containers all have bugs which result in undefined behaviour. For std::list the problem is that we clear the previous contents using _M_clear() instead of clear(). This means the _M_next, _M_prev and _M_size members are not zeroed, and so after we "update" them (with their existing values), we are left with dangling pointers and a non-zero size, but no elements. For the unordered containers the problem is similar. _Hashtable first deallocates the existing contents, then takes ownership of the pointers from the RHS object (which has just had its contents deallocated so the pointers are dangling). For std::basic_string it's a little more subtle. When the string is local (i.e. fits in the SSO buffer) we use char_traits::copy to copy the contents from this->data() to __rhs.data(). When &__rhs == this that copy violates the precondition that the ranges don't overlap. We only need to check for self-move for this case where it's local, because the only other case that can be true for self-move is that it's non-local but the allocators compare equal. In that case the data pointer is neither deallocated nor leaked, so the result is well-defined. This patch also makes a small optimization for std::deque move assignment, to use the efficient move when is_always_equal is false, but the allocators compare equal at runtime. Finally, we need to remove all the Debug Mode checks which abort the program when a self-move is detected, because it's not undefined to do that. Before PR 85828 can be closed we should also look into fixing std::shuffle so it doesn't do any redundant self-swaps. libstdc++-v3/ChangeLog: PR libstdc++/85828 * include/bits/basic_string.h (operator=(basic_string&&)): Check for self-move before copying with char_traits::copy. * include/bits/hashtable.h (operator=(_Hashtable&&)): Check for self-move. * include/bits/stl_deque.h (_M_move_assign1(deque&&, false_type)): Check for equal allocators. * include/bits/stl_list.h (_M_move_assign(list&&, true_type)): Call clear() instead of _M_clear(). * include/debug/formatter.h (__msg_self_move_assign): Change comment. * include/debug/macros.h (__glibcxx_check_self_move_assign): (_GLIBCXX_DEBUG_VERIFY): Remove. * include/debug/safe_container.h (operator=(_Safe_container&&)): Remove assertion check for safe move and make it well-defined. * include/debug/safe_iterator.h (operator=(_Safe_iterator&&)): Remove assertion check for self-move. * include/debug/safe_local_iterator.h (operator=(_Safe_local_iterator&&)): Likewise. * testsuite/21_strings/basic_string/cons/char/self_move.cc: New test. * testsuite/23_containers/deque/cons/self_move.cc: New test. * testsuite/23_containers/forward_list/cons/self_move.cc: New test. * testsuite/23_containers/list/cons/self_move.cc: New test. * testsuite/23_containers/set/cons/self_move.cc: New test. * testsuite/23_containers/unordered_set/cons/self_move.cc: New test. * testsuite/23_containers/vector/cons/self_move.cc: New test.
2020-07-29libstdc++: Fix unordered containers move constructors noexcept qualificationFrançois Dumont1-7/+33
_Hashtable move constructor is wrongly qualified as noexcept(true) regardless of _Equal and _H1 copy constructor qualifications. _Hashtable allocator-aware move constructor is missing its noexcept qualification like the depending unordered containers ones. libstdc++-v3/ChangeLog: * include/bits/hashtable.h (_Hashtable(_Hashtable&& __ht, __node_alloc_type&& __a, true_type)): Add noexcept qualification. (_Hashtable(_Hashtable&&)): Fix noexcept qualification. (_Hashtable(_Hashtable&&, const allocator_type&)): Add noexcept qualification. * include/bits/unordered_map.h (unordered_map(unordered_map&&, const allocator_type&)): Add noexcept qualification. (unordered_multimap(unordered_multimap&&, const allocator_type&)): Likewise. * include/bits/unordered_set.h (unordered_set(unordered_set&&, const allocator_type&)): Likewise. (unordered_multiset(unordered_multiset&&, const allocator_type&)): Likewise. * include/debug/unordered_map (unordered_map(unordered_map&&, const allocator_type&)): Likewise. (unordered_multimap(unordered_multimap&&, const allocator_type&)): Likewise. * include/debug/unordered_set (unordered_set(unordered_set&&, const allocator_type&)): Likewise. (unordered_multiset(unordered_multiset&&, const allocator_type&)): Likewise. * testsuite/23_containers/unordered_map/allocator/default_init.cc: New test. * testsuite/23_containers/unordered_map/cons/noexcept_default_construct.cc: New test. * testsuite/23_containers/unordered_map/cons/noexcept_move_construct.cc: New test. * testsuite/23_containers/unordered_map/modifiers/move_assign.cc: New test. * testsuite/23_containers/unordered_multimap/cons/noexcept_default_construct.cc: New test. * testsuite/23_containers/unordered_multimap/cons/noexcept_move_construct.cc: New test. * testsuite/23_containers/unordered_multiset/cons/noexcept_default_construct.cc: New test. * testsuite/23_containers/unordered_multiset/cons/noexcept_move_construct.cc: New test. * testsuite/23_containers/unordered_set/allocator/default_init.cc: New test. * testsuite/23_containers/unordered_set/cons/noexcept_default_construct.cc: New test. * testsuite/23_containers/unordered_set/cons/noexcept_move_construct.cc: New test.
2020-07-28libstdc++: Do not over-size hashtable buckets on range insertionFrançois Dumont1-22/+68
We used to consider range size on insertion but on unique keys container not all range values might be inserted resulting in over-sizing. In this case we just consider user reservation and if none then the container will adapt to actually inserted elements. libstdc++-v3/ChangeLog: * include/bits/hashtable.h (_Hashtable<>(_InputIterator, _InputIterator, size_t, const _H1&, const _H2&, const _Hash&, const _Equal&, const _ExtractKey&, const allocator_type&, true_type)): New. (_Hashtable<>(_InputIterator, _InputIterator, size_t, const _H1&, const _H2&, const _Hash&, const _Equal&, const _ExtractKey&, const allocator_type&, false_type)): New. (_Hashtable<>(_InputIterator, _InputIterator, size_t, const _H1&, const _H2&, const _Hash&, const _Equal&, const _ExtractKey&, const allocator_type&)): Delegate to latters. (operator=(initializer_list<value_type>)): Rehash if too small. (_M_insert(_Arg&&, const _NodeGenerator&, true_type)): Remove size_t len parameter. * include/bits/hashtable_policy.h (_Insert_base<>::_M_insert_range): Do not try to get input range distance. * testsuite/23_containers/unordered_set/cons/bucket_hint.cc: New test. * testsuite/23_containers/unordered_set/modifiers/insert.cc: New test.
2020-07-27libstdc++: Review _Hashtable count, equal_range _M_erase(false_type,) codeFrançois Dumont1-82/+81
Simplify operator[] implementation using find method. Review several _Hashtable method implementations to limit the computation of bucket index. Introduce _M_update_bbegin to simplify code. libstdc++-v3/ChangeLog: * include/bits/hashtable_policy.h (_Map_base<>::at): Use _Hashtable<>::find. (_Hashtable_base<>::_Equal_hash_code<>::_S_node_equals):New. (_Hashtable_base<>::_M_node_equals): New, use latter. (_Equality<_Key, _Value, _Alloc, _ExtractKey, _Equal, _H1, _H2, _Hash, _RehashPolicy, false>::_M_equal): Adapt to use latter. * include/bits/hashtable.h (_Hashtable<>::_M_update_bbegin): New. (_Hashtable<>::_M_assign): Use latter. (_Hashtable<>::_M_move_assign): Likewise. (_Hashtable<>(_Hashtable<>&&)): Likewise. (_Hashtable<>(_Hashtable<>&&, const allocator_type&)): Likewise. (_Hashtable<>::swap): Likewise. (_Hashtable<>::find): Build iterator directly from _M_find_node result. (_Hashtable<>::count): Use _Hashtable<>::find. (_Hashtable<>::equal_range): Likewise. (_Hashtable<>::_M_erase(false_type, const key_type&)): Use _M_node_equals.
2020-02-12libstdc++: Add missing std:: qualification of a forward callFrançois Dumont1-1/+1
* include/bits/hashtable.h (_Hashtable<>(_Hashtable&&, std::allocator_type&)): Add missing std namespace qualification to forward call.
2020-01-16libstdc++: Improve unordered containers == operator (PR 91263)François Dumont1-0/+7
Avoid comparing elements with operator== multiple times by replacing uses of find and equal_range with equivalent inlined code that uses operator== instead of the container's equality comparison predicate. This is valid because the standard requires that operator== is a refinement of the equality predicate. Also replace the _S_is_permutation function with std::is_permutation, which wasn't yet implemented when this code was first written. PR libstdc++/91263 * include/bits/hashtable.h (_Hashtable<>): Make _Equality<> friend. * include/bits/hashtable_policy.h: Include <bits/stl_algo.h>. (_Equality_base): Remove. (_Equality<>::_M_equal): Review implementation. Use std::is_permutation. * testsuite/23_containers/unordered_multiset/operators/1.cc (Hash, Equal, test02, test03): New. * testsuite/23_containers/unordered_set/operators/1.cc (Hash, Equal, test02, test03): New.
2020-01-09PR libstdc++/92124 fix incorrect unordered container move assignmentFrançois Dumont1-36/+37
* include/bits/hashtable.h (_Hashtable<>::__alloc_node_gen_t): New template alias. (_Hashtable<>::__fwd_value_for): New. (_Hashtable<>::_M_assign_elements<>): Remove _NodeGenerator template parameter. (_Hashtable<>::_M_assign<>): Add _Ht template parameter. (_Hashtable<>::operator=(const _Hashtable<>&)): Adapt. (_Hashtable<>::_M_move_assign): Adapt. Replace std::move_if_noexcept with std::move. (_Hashtable<>::_Hashtable(const _Hashtable&)): Adapt. (_Hashtable<>::_Hashtable(const _Hashtable&, const allocator_type&)): Adapt. (_Hashtable<>::_Hashtable(_Hashtable&&, const allocator_type&)): Adapt. * testsuite/23_containers/unordered_set/92124.cc: New. From-SVN: r280028
2020-01-01Update copyright years.Jakub Jelinek1-1/+1
From-SVN: r279813
2019-06-17Simplify node ownership in _Hashtable membersFrançois Dumont1-145/+138
Introduce an RAII type to manage nodes in unordered containers while they are being inserted. If the caller always owns a node until it is inserted, then the insertion functions don't need to deallocate on failure. This allows a FIXME in the node re-insertion API to be removed. Also change extract(const key_type&) to not call extract(const_iterator) anymore. This avoids looping through the bucket nodes again to find the node before the one being extracted. 2019-06-17 François Dumont <fdumont@gcc.gnu.org> Jonathan Wakely <jwakely@redhat.com> * include/bits/hashtable.h (struct _Hashtable::_Scoped_node): New type. (_Hashtable::_M_insert_unique_node): Add key_type parameter. Don't deallocate node if insertion fails. (_Hashtable::_M_insert_multi_node): Likewise. (_Hashtable::_M_reinsert_node): Pass additional key argument. (_Hashtable::_M_reinsert_node_multi): Likewise. Remove FIXME. (_Hashtable::_M_extract_node(size_t, __node_base*)): New function. (_Hashtable::extract(const_iterator)): Use _M_extract_node. (_Hashtable::extract(const _Key&)): Likewise. (_Hashtable::_M_merge_unique): Pass additional key argument. (_Hashtable::_M_emplace<Args>(true_type, Args&&...)): Likewise. Use _Scoped_node. (_Hashtable::_M_insert): Likewise. * include/bits/hashtable_policy.h (_Map_base::operator[]): Likewise. (_Hashtable_alloc): Add comments to functions with misleading names. Co-Authored-By: Jonathan Wakely <jwakely@redhat.com> From-SVN: r272381
2019-06-03Rename variables and cleanup comments.François Dumont1-108/+112
2019-06-03 François Dumont <fdumont@gcc.gnu.org> Rename variables and cleanup comments. * include/bits/hashtable_policy.h * include/bits/hashtable.h From-SVN: r271876
2019-06-03Enforce allocator::value_type consistency for containers in C++2aJonathan Wakely1-1/+1
In previous standards it is undefined for a container and its allocator to have a different value_type. Libstdc++ has traditionally allowed it as an extension, automatically rebinding the allocator to the container's value_type. Since GCC 8.1 that extension has been disabled for C++11 and later when __STRICT_ANSI__ is defined (i.e. for -std=c++11, -std=c++14, -std=c++17 and -std=c++2a). Since the acceptance of P1463R1 into the C++2a draft an incorrect allocator::value_type now requires a diagnostic. This patch implements that by enabling the static_assert for -std=gnu++2a as well. * doc/xml/manual/status_cxx2020.xml: Document P1463R1 status. * include/bits/forward_list.h [__cplusplus > 201703]: Enable allocator::value_type assertion for C++2a. * include/bits/hashtable.h: Likewise. * include/bits/stl_deque.h: Likewise. * include/bits/stl_list.h: Likewise. * include/bits/stl_map.h: Likewise. * include/bits/stl_multimap.h: Likewise. * include/bits/stl_multiset.h: Likewise. * include/bits/stl_set.h: Likewise. * include/bits/stl_vector.h: Likewise. * testsuite/23_containers/deque/48101-3_neg.cc: New test. * testsuite/23_containers/forward_list/48101-3_neg.cc: New test. * testsuite/23_containers/list/48101-3_neg.cc: New test. * testsuite/23_containers/map/48101-3_neg.cc: New test. * testsuite/23_containers/multimap/48101-3_neg.cc: New test. * testsuite/23_containers/multiset/48101-3_neg.cc: New test. * testsuite/23_containers/set/48101-3_neg.cc: New test. * testsuite/23_containers/unordered_map/48101-3_neg.cc: New test. * testsuite/23_containers/unordered_multimap/48101-3_neg.cc: New test. * testsuite/23_containers/unordered_multiset/48101-3_neg.cc: New test. * testsuite/23_containers/unordered_set/48101-3_neg.cc: New test. * testsuite/23_containers/vector/48101-3_neg.cc: New test. From-SVN: r271866
2019-05-17PR libstdc++/85965 move is_invocable assertions againJonathan Wakely1-6/+0
This is another attempt to reduce how often the assertions are evaluated, so that code which doesn't try to use the function objects doesn't need them to be invocable. For _Rb_tree we access the _M_key_compare object directly, so can't put the assertions in an accessor function for it. However, every invocation of _M_key_compare is accompanied by a use of _S_key, so the assertions can be put in there. For _Hashtable there are member functions that are consistently used to obtain a hash code or test for equality, so the assertions can go in those members. PR libstdc++/85965 * include/bits/hashtable.h (_Hashtable::~_Hashtable()): Remove static assertions from the destructor. * include/bits/hashtable_policy.h (_Hash_code_base::_M_hash_code): Move static_assert for hash function to here. (_Hash_table_base::_M_equals): Move static_assert for equality predicate to here. * include/bits/stl_tree.h (_Rb_tree::_S_value(_Const_Link_type)): Remove. (_Rb_tree::_S_key(_Const_Link_type)): Move assertions here. Access the value directly instead of calling _S_value. (_Rb_tree::_S_value(_Const_Base_ptr)): Remove. (_Rb_tree::_S_key(_Const_Base_ptr)): Do downcast and forward to _S_key(_Const_Link_type). * testsuite/23_containers/set/85965.cc: Check construction, destruction, assignment and size() do not trigger the assertions. * testsuite/23_containers/unordered_set/85965.cc: Likewise. * testsuite/23_containers/map/48101_neg.cc: Call find and adjust expected errors. * testsuite/23_containers/multimap/48101_neg.cc: Likewise. * testsuite/23_containers/multiset/48101_neg.cc: Likewise. * testsuite/23_containers/set/48101_neg.cc: Likewise. * testsuite/23_containers/unordered_map/48101_neg.cc: Likewise. * testsuite/23_containers/unordered_multimap/48101_neg.cc: Likewise. * testsuite/23_containers/unordered_multiset/48101_neg.cc: Likewise. * testsuite/23_containers/unordered_set/48101_neg.cc: Likewise. From-SVN: r271323
2019-05-04hashtable.h (_Hashtable<>::rehash): Review comment.François Dumont1-1/+2
2019-05-04 François Dumont <fdumont@gcc.gnu.org> * include/bits/hashtable.h (_Hashtable<>::rehash): Review comment. * include/bits/hashtable_policy.h (_Prime_rehash_policy::_M_bkt_for_elements): Use __builtin_ceill. (_Power2_rehash_policy::_M_bkt_for_elements): Likewise. (_Power2_rehash_policy::_M_next_bkt): Enforce returning a result not smaller than input value rather than always greater. Preserve _M_next_resize if called with 0 input. Use __builtin_floorl. (_Power2_rehash_policy::_M_need_rehash): Rehash only if number of elements + number of insertions is greater than _M_next_resize. Start with 11 buckets if not told otherwise. Use __builtin_floorl. (_Rehash_base<>::reserve): Use rehash policy _M_bkt_for_elements. * src/c++11/hashtable_c++0x.cc (_Prime_rehash_policy::_M_next_bkt): Preserve _M_next_resize if called with 0 input. Use __builtin_floorl. (_Prime_rehash_policy::_M_need_rehash): Start with 11 buckets if not told otherwise. Use __builtin_floorl. * testsuite/23_containers/unordered_set/hash_policy/71181.cc: Adapt test to also validate _Power2_rehash_policy. * testsuite/23_containers/unordered_set/hash_policy/power2_rehash.cc: Adapt. From-SVN: r270868
2019-03-26PR libstdc++/85965 delay static assertions until types are completeJonathan Wakely1-5/+6
The static assertions added for PR libstdc++/48101 were at class scope and so were evaluated too eagerly, when it might not be possible to determine whether the function objects are invocable with the key types. The problematic cases are where the key type is not known to be convertible to the argument type(s) of the function object until later, after a type has been completed. Specifically, if the key type is a pointer to a derived class and the function object's argument type is a pointer to a base class, then the derived-to-base conversion is only valid once the derived type is complete. By moving the static assertions to the destructor they will only be evaluated when the destructor is instantiated, at which point whether the key type can be passed to the function object should be knowable. The ideal place to do the checks would be only when the function objects are actually invoked, but that would mean adding the checks in numerous places, so the destructor is used instead. The tests need to be adjusted because the "required from here" line is now the location of the destructor, not the point of instantiation in the test file. For the map and multimap tests which check two specializations, the dg-error matching the assertion text matches both cases. Also check the diagnostic output for the template arguments, to ensure both specializations trigger the assertion. PR libstdc++/85965 * include/bits/hashtable.h (_Hashtable): Move static assertions to destructor so they are not evaluated until the _Key type is complete. * include/bits/stl_tree.h (_Rb_tree): Likewise. * testsuite/23_containers/set/85965.cc: New test. * testsuite/23_containers/unordered_set/85965.cc: New test. * testsuite/23_containers/map/48101_neg.cc: Replace "here" errors with regexp matching the corresponding _Rb_tree specialization. * testsuite/23_containers/multimap/48101_neg.cc: Likewise. * testsuite/23_containers/multiset/48101_neg.cc: Remove "here" error. * testsuite/23_containers/set/48101_neg.cc: Likewise. * testsuite/23_containers/unordered_map/48101_neg.cc: Likewise. * testsuite/23_containers/unordered_multimap/48101_neg.cc: Likewise. * testsuite/23_containers/unordered_multiset/48101_neg.cc: Likewise. * testsuite/23_containers/unordered_set/48101_neg.cc: Likewise. From-SVN: r269949
2019-02-26PR libstdc++/89477 constrain deduction guides for maps and setsJonathan Wakely1-0/+7
The Compare, Hash, and Pred template parameters should be constrained in the C++17 deduction guides for associative and unordered containers. The deduction guides for stack, queue and priority_queue are already constrained, but this patch makes them use the _RequireNotAllocator helper instead of reproducing the logic each time. PR libstdc++/89477 * include/bits/alloc_traits.h (_RequireNotAllocator): New helper for container deduction guides. * include/bits/hashtable.h (_RequireNotAllocatorOrIntegral): Likewise. * include/bits/stl_map.h (map): Use _RequireNotAllocator to constrain parameters in deduction guides. * include/bits/stl_multimap.h (multimap): Likewise. * include/bits/stl_multiset.h (multiset): Likewise. * include/bits/stl_queue.h (queue, priority_queue): Likewise. * include/bits/stl_set.h (set): Likewise. * include/bits/stl_stack.h (stack): Likewise. * include/bits/unordered_map.h (unordered_map, unordered_multimap): use _RequireNotAllocator and _RequireNotAllocatorOrIntegral to constrain parameters in deduction guides. * include/bits/unordered_set.h (unordered_set, unordered_multiset): Likewise. * testsuite/23_containers/map/cons/deduction.cc: Test additional deduction cases. * testsuite/23_containers/multiset/cons/deduction.cc: Likewise. * testsuite/23_containers/set/cons/deduction.cc: Likewise. * testsuite/23_containers/unordered_map/cons/deduction.cc: Likewise. * testsuite/23_containers/unordered_multimap/cons/deduction.cc: Likewise. * testsuite/23_containers/unordered_multiset/cons/deduction.cc: Likewise. * testsuite/23_containers/unordered_set/cons/deduction.cc: Likewise. From-SVN: r269234
2019-01-21Fix after P0600.Ulrich Drepper1-1/+1
gcc/testsuite/ChangeLog 2019-02-20 Ulrich Drepper <drepper@redhat.com> Fix after P0600. * g++.dg/init/new39.C: Don't just ignore result of new. libstdc++/ChangeLog 2019-02-20 Ulrich Drepper <drepper@redhat.com> Implement C++20 P0600r1. * include/backward/hash_map: Add nodiscard attribute to empty. * include/backward/hash_set: Likewise. * backward/hashtable.h: Likewise. * include/bits/basic_string.h: Likewise. * include/bits/forward_list.h: Likewise. * include/bits/hashtable.h: Likewise. * include/bits/regex.h: Likewise. * include/bits/stl_deque.h: Likewise. * include/bits/stl_list.h: Likewise. * include/bits/stl_map.h: Likewise. * include/bits/stl_multimap.h: Likewise. * include/bits/stl_multiset.h: Likewise. * include/bits/stl_queue.h: Likewise. * include/bits/stl_set.h: Likewise. * include/bits/stl_stack.h: Likewise. * include/bits/stl_tree.h: Likewise. * include/bits/stl_vector.h: Likewise. * include/bits/unordered_map.h: Likewise. * include/bits/unordered_set.h: Likewise. * include/debug/array: Likewise. * include/experimental/any: Likewise. * include/experimental/bits/fs_path.h: Likewise. * include/experimental/internet: Likewise. * include/experimental/string_view: Likewise. * include/ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp: Likewise. * include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp: Likewise. * include/ext/pb_ds/detail/binary_heap_/info_fn_imps.hpp: Likewise. * include/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp: Likewise. * include/ext/pb_ds/detail/cc_hash_table_map_/info_fn_imps.hpp: Likewise. * include/ext/pb_ds/detail/cc_hash_table_map_/size_fn_imps.hpp: Likewise. * include/ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp: Likewise. * include/ext/pb_ds/detail/gp_hash_table_map_/info_fn_imps.hpp: Likewise. * include/ext/pb_ds/detail/left_child_next_sibling_heap_/info_fn_imps.hpp: Likewise. * include/ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp: Likewise. * include/ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp: Likewise. * include/ext/pb_ds/detail/list_update_map_/lu_map_.hpp: Likewise. * include/ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp: Likewise. * include/ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hp: Likewise. * include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp: Likewise. * include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp: Likewise. * include/ext/pb_ds/detail/rc_binomial_heap_/rc.hpp: Likewise. * include/ext/pb_ds/detail/tree_trace_base.hpp: Likewise. * include/ext/pb_ds/trie_policy.hpp: Likewise. * include/ext/rope: Likewise. * include/ext/slist: Likewise. * include/ext/vstring.h: Likewise. * include/profile/array: Likewise. * include/std/array: Likewise. * include/tr1/array: Likewise. * include/tr1/hashtable.h: Likewise. * include/tr1/regex: Likewise. * include/tr2/dynamic_bitset: Likewise. * include/bits/alloc_traits.h: Add nodiscard attribute to allocate. * include/experimental/memory_resource: Likewise. * include/ext/alloc_traits.h: Likewise. * include/ext/array_allocator.h: Likewise. * include/ext/bitmap_allocator.h: Likewise. * include/ext/debug_allocator.h: Likewise. * include/ext/extptr_allocator.h: Likewise. * include/ext/mt_allocator.h: Likewise. * include/ext/new_allocator.h: Likewise. * include/ext/pool_allocator.h: Likewise. * include/ext/throw_allocator.h: Likewise. * include/std/scoped_allocator: Likewise. * libsupc++/eh_alloc.cc: Likewise. * include/std/future: Add nodiscard attribute to async. * libsupc++/new: Add nodiscard attribute to new. From-SVN: r268111
2019-01-01Update copyright years.Jakub Jelinek1-1/+1
From-SVN: r267494
2018-11-27re PR libstdc++/88199 (memory leak on unordered container move assignment)François Dumont1-78/+64
2018-11-27 François Dumont <fdumont@gcc.gnu.org> PR libstdc++/88199 * include/bits/hashtable.h (_Hashtable<>::_M_assign_elements): New. (_Hashtable<>::operator=(const _Hashtable&)): Use latter. (_Hashtable<>::_M_move_assign(_Hashtable&&, false_type)): Likewise. * testsuite/23_containers/unordered_set/allocator/move_assign.cc (test03): New. From-SVN: r266528
2018-01-09re PR libstdc++/83709 (Inserting duplicates into an unordered associative ↵François Dumont1-12/+18
containers causes the container to invalidate iterators) 2018-01-09 François Dumont <fdumont@gcc.gnu.org> PR libstdc++/83709 * include/bits/hashtable_policy.h (__distance_fwd(_Iterator, _Iterator, input_iterator_tag)): Return 1 if __first != __last. (_Insert_base::_M_insert_range(_Ite, _Ite, _NodeGetter, true_type)): New. (_Insert_base::_M_insert_range(_Ite, _Ite, _NodeGetter, false_type)): Add false_type parameter. (_Insert_base::insert): Adapt. * include/bits/hashtable.h (_Hashtable::operator=(initializzr_list<>)): Adapt. (_Hashtable::_M_insert(_Arg&&, const _NodeGen&, true_type, size_t)): Add __n_elt parameter, defaulted to 1. (_Hashtable::_M_insert_unique_node): Likewise. Use it to call rehash policy _M_need_rehash. (_Hashtable::_M_merge_unique): Pass target number of elements to add to produce only 1 rehash if necessary. * testsuite/23_containers/unordered_map/insert/83709.cc: New. * testsuite/23_containers/unordered_set/insert/83709.cc: New. From-SVN: r256396
2018-01-03Update copyright years.Jakub Jelinek1-1/+1
From-SVN: r256169
2017-11-21PR libstdc++/48101 improve errors for invalid container specializationsJonathan Wakely1-1/+13
PR libstdc++/48101 * include/bits/allocator.h (allocator<const _Tp>) (allocator<volatile _Tp>, allocator<const volatile _Tp>): Add partial specializations. * include/bits/forward_list.h (forward_list): Add static assertions. * include/bits/hashtable.h (__cache_default): Use __is_nothrow_invocable instead of __is_noexcept_hash. (_Hashtable): Add static assertions. * include/bits/hashtable_policy.h (__is_noexcept_hash): Remove. * include/bits/stl_deque.h (deque): Add static assertions. * include/bits/stl_function.h (_Identity<const _Tp>): Add partial specialization. * include/bits/stl_list.h (list): Add static assertions. * include/bits/stl_map.h (map): Likewise. * include/bits/stl_multimap.h (multimap): Likewise. * include/bits/stl_multiset.h (multiset): Likewise. * include/bits/stl_set.h (set): Likewise. * include/bits/stl_tree.h (_Rb_tree): Likewise. * include/bits/stl_vector.h (vector): Likewise. * include/bits/unordered_map.h (unordered_map, unordered_multimap): Use typename instead of class in template-parameter-list and remove spaces. * include/bits/unordered_set.h (unordered_set, unordered_multiset): Likewise. * testsuite/23_containers/deque/48101-2_neg.cc: New test. * testsuite/23_containers/deque/48101_neg.cc: New test. * testsuite/23_containers/forward_list/48101-2_neg.cc: New test. * testsuite/23_containers/forward_list/48101_neg.cc: New test. * testsuite/23_containers/list/48101-2_neg.cc: New test. * testsuite/23_containers/list/48101_neg.cc: New test. * testsuite/23_containers/map/48101-2_neg.cc: New test. * testsuite/23_containers/map/48101_neg.cc: New test. * testsuite/23_containers/map/operations/31440.cc: Fix comparison object to have const-qualified call operator. * testsuite/23_containers/multimap/48101-2_neg.cc: New test. * testsuite/23_containers/multimap/48101_neg.cc: New test. * testsuite/23_containers/multiset/48101-2_neg.cc: New test. * testsuite/23_containers/multiset/48101_neg.cc: New test. * testsuite/23_containers/set/48101-2_neg.cc: New test. * testsuite/23_containers/set/48101_neg.cc: New test. * testsuite/23_containers/unordered_map/48101-2_neg.cc: New test. * testsuite/23_containers/unordered_map/48101_neg.cc: New test. * testsuite/23_containers/unordered_multimap/48101-2_neg.cc: New test. * testsuite/23_containers/unordered_multimap/48101_neg.cc: New test. * testsuite/23_containers/unordered_multiset/48101-2_neg.cc: New test. * testsuite/23_containers/unordered_multiset/48101_neg.cc: New test. * testsuite/23_containers/unordered_set/48101-2_neg.cc: New test. * testsuite/23_containers/unordered_set/48101_neg.cc: New test. * testsuite/23_containers/unordered_set/instantiation_neg.cc: Adjust dg-error line number. * testsuite/23_containers/vector/48101-2_neg.cc: New test. * testsuite/23_containers/vector/48101_neg.cc: New test. From-SVN: r255035
2017-08-18PR libstdc++/81891 fix double-free in hashtable constructorJonathan Wakely1-11/+2
PR libstdc++/81891 * include/bits/hashtable.h (_Hashtable(_InputIterator, _InputIterator, size_type, const _H1&, const _H2&, const _Hash&, const _Equal&, const _ExtractKey&, const allocator_type&)): Let destructor do clean up if an exception is thrown. * testsuite/23_containers/unordered_map/cons/81891.cc: New. From-SVN: r251185
2017-01-01Update copyright years.Jakub Jelinek1-1/+1
From-SVN: r243994
2016-09-22Implement C++17 node extraction and insertion (P0083R5)Jonathan Wakely1-0/+141
* doc/xml/manual/status_cxx2017.xml: Document status. * doc/html/*: Regenerate. * include/Makefile.am: Add bits/node_handle.h and reorder. * include/Makefile.in: Regenerate. * include/bits/hashtable.h (_Hashtable::node_type) (_Hashtable::insert_return_type, _Hashtable::_M_reinsert_node) (_Hashtable::_M_reinsert_node_multi, _Hashtable::extract) (_Hashtable::_M_merge_unique, _Hashtable::_M_merge_multi): Define. (_Hash_merge_helper): Define primary template. * include/bits/node_handle.h: New header. * include/bits/stl_map.h (map): Declare _Rb_tree_merge_helper as friend. (map::node_type, map::insert_return_type, map::extract, map::merge) (map::insert(node_type&&), map::insert(const_iterator, node_type&&)): Define new members. (_Rb_tree_merge_helper): Specialize for map. * include/bits/stl_multimap.h (multimap): Declare _Rb_tree_merge_helper as friend. (multimap::node_type, multimap::extract, multimap::merge) (multimap::insert(node_type&&)) (multimap::insert(const_iterator, node_type&&)): Define. (_Rb_tree_merge_helper): Specialize for multimap. * include/bits/stl_multiset.h (multiset): Declare _Rb_tree_merge_helper as friend. (multiset::node_type, multiset::extract, multiset::merge) (multiset::insert(node_type&&)) (multiset::insert(const_iterator, node_type&&)): Define. * include/bits/stl_set.h (set): Declare _Rb_tree_merge_helper as friend. (set::node_type, set::insert_return_type, set::extract, set::merge) (set::insert(node_type&&), set::insert(const_iterator, node_type&&)): Define. (_Rb_tree_merge_helper): Specialize for set. * include/bits/stl_tree.h (_Rb_tree): Declare _Rb_tree<> as friend. (_Rb_tree::node_type, _Rb_tree::insert_return_type) (_Rb_tree::_M_reinsert_node_unique, _Rb_tree::_M_reinsert_node_equal) (_Rb_tree::_M_reinsert_node_hint_unique) (_Rb_tree::_M_reinsert_node_hint_equal, _Rb_tree::extract) (_Rb_tree::_M_merge_unique, _Rb_tree::_M_merge_equal): Define. (_Rb_tree_merge_helper): Specialize for multiset. * include/bits/unordered_map.h (unordered_map): Declare unordered_map<> and unordered_multimap<> as friends. (unordered_map::node_type, unordered_map::insert_return_type) (unordered_map::extract, unordered_map::merge) (unordered_map::insert(node_type&&)) (unordered_map::insert(const_iterator, node_type&&)) (unordered_multimap): Declare _Hash_merge_helper as friend. (unordered_multimap::node_type, unordered_multimap::extract) (unordered_multimap::merge, unordered_multimap::insert(node_type&&)) (unordered_multimap::insert(const_iterator, node_type&&)): Define. (_Hash_merge_helper): Specialize for unordered maps and multimaps. * include/bits/unordered_set.h (unordered_set, unordered_multiset): Declare _Hash_merge_helper as friend. (unordered_set::node_type, unordered_set::insert_return_type) (unordered_set::extract, unordered_set::merge) (unordered_set::insert(node_type&&)) (unordered_set::insert(const_iterator, node_type&&)): Define. (unordered_multiset::node_type, unordered_multiset::extract) (unordered_multiset::merge, unordered_multiset::insert(node_type&&)) (unordered_multiset::insert(const_iterator, node_type&&)): Define. (_Hash_merge_helper): Specialize for unordered sets and multisets. * include/debug/map.h (map): Add using declarations or forwarding functions for new members. * include/debug/map.h (multimap): Likewise. * include/debug/map.h (multiset): Likewise. * include/debug/map.h (set): Likewise. * include/debug/unordered_map (unordered_map, unordered_multimap): Likewise. * include/debug/unordered_set( unordered_set, unordered_multiset): Likewise. * python/libstdcxx/v6/printers.py (get_value_from_aligned_membuf): New helper function. (get_value_from_list_node, get_value_from_Rb_tree_node): Use helper. (StdNodeHandlePrinter): Define printer for node handles. (build_libstdcxx_dictionary): Register StdNodeHandlePrinter. * testsuite/23_containers/map/modifiers/extract.cc: New. * testsuite/23_containers/map/modifiers/merge.cc: New. * testsuite/23_containers/multimap/modifiers/extract.cc: New. * testsuite/23_containers/multimap/modifiers/merge.cc: New. * testsuite/23_containers/multiset/modifiers/extract.cc: New. * testsuite/23_containers/multiset/modifiers/merge.cc: New. * testsuite/23_containers/set/modifiers/extract.cc: New. * testsuite/23_containers/set/modifiers/merge.cc: New. * testsuite/23_containers/unordered_map/modifiers/extract.cc: New. * testsuite/23_containers/unordered_map/modifiers/merge.cc: New. * testsuite/23_containers/unordered_multimap/modifiers/extract.cc: New. * testsuite/23_containers/unordered_multimap/modifiers/merge.cc: New. * testsuite/23_containers/unordered_multiset/modifiers/extract.cc: New. * testsuite/23_containers/unordered_multiset/modifiers/merge.cc: New. * testsuite/23_containers/unordered_set/modifiers/extract.cc: New. * testsuite/23_containers/unordered_set/modifiers/merge.cc: New. * testsuite/23_containers/unordered_set/instantiation_neg.cc: Adjust dg-error lineno. * testsuite/libstdc++-prettyprinters/cxx17.cc: Test node handles. From-SVN: r240363
2016-06-27re PR libstdc++/71640 (include/c++/7.0.0/bits/hashtable.h:293:7: error: too ↵François Dumont1-1/+1
many template parameters in template redeclaration) 2016-06-27 François Dumont <fdumont@gcc.gnu.org> PR libstdc++/71640 * include/bits/hashtable.h: Remove _Unique_keya parameter in _Insert friend declaration. From-SVN: r237803
2016-06-16Provide swappable traits (p0185r1)Daniel Kruegler1-4/+4
2016-06-16 Daniel Kruegler <daniel.kruegler@gmail.com> Provide swappable traits (p0185r1) * include/std/type_traits (is_swappable, is_nothrow_swappable, is_swappable_with, is_nothrow_swappable_with, is_swappable_v, is_nothrow_swappable_v, is_swappable_with_v, is_nothrow_swappable_with_v): New. * include/bits/stl_pair.h: Use it as per p0185r1. * include/bits/stl_queue.h: Likewise. * include/bits/stl_stack.h: Likewise. * include/bits/unique_ptr.h: Likewise. * include/std/tuple: Likewise. * include/std/array: Likewise. Fix zero-size member swap. * include/bits/hashtable.h: Use __and_. * testsuite/20_util/is_nothrow_swappable/requirements/ explicit_instantiation.cc: Change test options to std=gnu++17. * testsuite/20_util/is_nothrow_swappable/requirements/typedefs.cc: Likewise. * testsuite/20_util/is_nothrow_swappable/value.cc: Likewise. * testsuite/20_util/is_swappable/requirements/ explicit_instantiation.cc: Likewise. * testsuite/20_util/is_swappable/requirements/typedefs.cc: Likewise. * testsuite/20_util/is_swappable/value.cc: Likewise. * testsuite/20_util/is_nothrow_swappable/requirements/ explicit_instantiation_ext.cc: New. * testsuite/20_util/is_nothrow_swappable/requirements/typedefs_ext.cc: New. * testsuite/20_util/is_nothrow_swappable/value.h: New. * testsuite/20_util/is_nothrow_swappable/value_ext.cc: New. * testsuite/20_util/is_nothrow_swappable_with/requirements/ explicit_instantiation.cc: New. * testsuite/20_util/is_nothrow_swappable_with/requirements/typedefs.cc: New. * testsuite/20_util/is_nothrow_swappable_with/value.cc: New. * testsuite/20_util/is_swappable/requirements/ explicit_instantiation_ext.cc: New. * testsuite/20_util/is_swappable/requirements/typedefs_ext.cc: New. * testsuite/20_util/is_swappable/value.h: New. * testsuite/20_util/is_swappable/value_ext.cc: New. * testsuite/20_util/is_swappable_with/requirements/ explicit_instantiation.cc: New. * testsuite/20_util/is_swappable_with/requirements/typedefs.cc: New. * testsuite/20_util/is_swappable_with/value.cc: New. * testsuite/23_containers/array/tuple_interface/get_neg.cc: Adjust dg-error line numbers. * testsuite/23_containers/array/tuple_interface/tuple_element_neg.cc: Likewise. From-SVN: r237531
2016-04-14Revert empty class parameter passing ABI changes.Jason Merrill1-22/+20
From-SVN: r234977
2016-04-13Adjust for new empty class parameter passing ABI.Jonathan Wakely1-20/+22
* include/bits/c++config (_GLIBCXX_BEGIN_NAMESPACE_EMPTY_TYPES, _GLIBCXX_END_NAMESPACE_EMPTY_TYPES, _GLIBCXX_ABI_TAG_EMPTY): Define. * include/bits/hashtable.h (_Hashtable::_M_emplace): Change signatures of functions taking empty structs by value. Add a template parameter to overloads without hints. Rename overloads with hints to _M_emplace_hint. (_Hashtable::_M_erase(true_type, const_iterator), _Hashtable::_M_erase(false_type, const_iterator)): Change signatures by reordering parameters. * include/bits/hashtable_policy.h (_Insert::insert): Adjust to call _M_emplace_hint instead of _M_emplace. * include/bits/shared_ptr.h (shared_ptr(_Tp1*, _Deleter, _Alloc), shared_ptr(nullptr_t, _Deleter, _Alloc)): Use _GLIBCXX_ABI_TAG_EMPTY. * include/bits/shared_ptr_base.h (_Sp_counted_deleter, __shared_count, __shared_ptr): Likewise. * include/bits/stl_algo.h (replace_if): Likewise. * include/bits/stl_pair.h (piecewise_construct_t, piecewise_construct): Use _GLIBCXX_BEGIN_NAMESPACE_EMPTY_TYPES. * include/bits/uses_allocator.h (allocator_arg_t, allocator_arg, __uses_alloc0): Likewise. * include/ext/pb_ds/assoc_container.hpp (basic_hash_table): Likewise. * testsuite/20_util/scoped_allocator/69293_neg.cc: Adjust dg-error. * testsuite/20_util/shared_ptr/cons/43820_neg.cc: Likewise. * testsuite/20_util/shared_ptr/cons/void_neg.cc: Likewise. * testsuite/20_util/uses_allocator/69293_neg.cc: Likewise. * testsuite/20_util/uses_allocator/cons_neg.cc: Likewise. * testsuite/ext/profile/mutex_extensions_neg.cc: Likewise. From-SVN: r234964
2016-01-04Update copyright years.Jakub Jelinek1-1/+1
From-SVN: r232055
2015-07-13c++config (_GLIBCXX_NOEXCEPT_IF): Define.Jonathan Wakely1-4/+2
* include/bits/c++config (_GLIBCXX_NOEXCEPT_IF): Define. * include/bits/forward_list.h (forward_list::swap): Make noexcept unconditional. * include/bits/hashtable.h (_Hashtable::swap): Do not use _S_nothrow_swap(). * include/bits/stl_bvector.h (vector<bool>::swap): Make noexcept unconditional. * include/bits/stl_deque.h (deque::swap): Likewise. (swap(deque&, deque&)): Use _GLIBCXX_NOEXCEPT_IF. * include/bits/stl_list.h (list::swap): Make noexcept unconditional. (swap(list&, list&)): Use _GLIBCXX_NOEXCEPT_IF. * include/bits/stl_map.h (map::swap, swap(map&, map&)): Use _GLIBCXX_NOEXCEPT_IF, do not depend on _S_nothrow_swap. * include/bits/stl_multimap.h (multimap::swap, swap(multimap&, multimap&)): Likewise. * include/bits/stl_multiset.h (multiset::swap, swap(multiset&, multiset&)): Likewise. * include/bits/stl_set.h (set::swap, swap(set&, set&)): Likewise. * include/bits/stl_tree.h (_Rb_tree::swap, swap(_Rb_tree&, _Rb_tree&)): Likewise. * include/bits/stl_vector.h (vector::swap): Make noexcept unconditional. (swap(vector&, vector&)): Use _GLIBCXX_NOEXCEPT_IF. * include/debug/deque (deque::swap, swap): Likewise. * include/debug/forward_list (swap): Add noexcept. * include/debug/list (list::swap, swap): Use _GLIBCXX_NOEXCEPT_IF. * include/debug/map.h (map::swap, swap): Likewise. * include/debug/multimap.h (multimap::swap, swap): Likewise. * include/debug/multiset.h (multiset::Swap, swap): Likewise. * include/debug/set.h (set::swap, swap): Likewise. * include/debug/unordered_map (unordered_map::swap, unordered_multimap::swap, swap): Likewise. * include/debug/unordered_set (unordered_set::swap, unordered_multiset::swap, swap): Likewise. * include/debug/vector (vector::swap, swap): Likewise. * include/ext/alloc_traits.h (__alloc_traits::_S_nothrow_swap()): Remove. * include/profile/deque (deque::swap, swap): Use _GLIBCXX_NOEXCEPT_IF. * include/profile/forward_list (swap): Add noexcept. * include/profile/list (list::swap, swap) : Use _GLIBCXX_NOEXCEPT_IF. * include/profile/map.h (map::swap, swap): Likewise. * include/profile/multimap.h (multimap::swap, swap): Likewise. * include/profile/multiset.h (multiset::swap, swap): Likewise. * include/profile/set.h (set::swap, swap): Likewise. * include/profile/unordered_map (swap): Likewise. * include/profile/unordered_set (swap): Likewise. * include/profile/vector (vector::swap, swap): Likewise. Remove overloads for swapping rvalues. * testsuite/23_containers/deque/allocator/noexcept.cc: Update tests for noexcept on swap. * testsuite/23_containers/forward_list/allocator/noexcept.cc: Likewise. * testsuite/23_containers/list/allocator/noexcept.cc: Likewise. * testsuite/23_containers/map/allocator/noexcept.cc: Likewise. * testsuite/23_containers/multimap/allocator/noexcept.cc: Likewise. * testsuite/23_containers/multiset/allocator/noexcept.cc: Likewise. * testsuite/23_containers/set/allocator/noexcept.cc: Likewise. * testsuite/23_containers/unordered_map/allocator/noexcept.cc: Likewise. * testsuite/23_containers/unordered_multimap/allocator/noexcept.cc: Likewise. * testsuite/23_containers/unordered_multiset/allocator/noexcept.cc: Likewise. * testsuite/23_containers/unordered_set/allocator/noexcept.cc: Likewise. * testsuite/23_containers/vector/allocator/noexcept.cc: Likewise. * testsuite/23_containers/vector/bool/allocator/noexcept.cc: Likewise. * testsuite/ext/profile/mutex_extensions_neg.cc: Adjust dg-error line number. From-SVN: r225744
2015-07-05hashtable.h (_Hashtable<>::__rehash_policy): Do not rehash container.François Dumont1-17/+2
2015-07-05 François Dumont <fdumont@gcc.gnu.org> * include/bits/hashtable.h (_Hashtable<>::__rehash_policy): Do not rehash container. * testsuite/23_containers/unordered_set/max_load_factor/robustness.cc: Adapt. From-SVN: r225436
2015-07-01alloc_traits.h (__alloctr_rebind): Remove.Jonathan Wakely1-5/+4
* include/bits/alloc_traits.h (__alloctr_rebind): Remove. (__allocator_traits_base): New base class. (__alloc_rebind): Reimplement in terms of detection idiom. (allocator_traits): Derive from __allocator_traits_base. Reimplement nested types in terms of detection idiom. Simplify SFINAE constraints on overloaded static member functions. * include/bits/hashtable.h (_Hashtable): Use __alloc_rebind instead of __alloctr_rebind. * testsuite/20_util/scoped_allocator/propagation.cc: Define rebind. * testsuite/23_containers/unordered_set/instantiation_neg.cc: Adjust dg-error line number. From-SVN: r225244
2015-06-26Implement N4258 (Cleaning-up noexcept in the Library rev 3)Jonathan Wakely1-7/+12
* doc/xml/manual/intro.xml: Document LWG 2108 status. * include/bits/alloc_traits.h (allocator_traits::is_always_equal): Define. * include/bits/allocator.h (allocator::is_always_equal): Likewise. * include/bits/forward_list.h (forward_list::operator=(forward_list&&)): Use __bool_constant. (forward_list::swap(forward_list&)): Add noexcept. * include/bits/hashtable.h (_Hashtable::operator=(_Hashtable&&)): Likewise. (_Hashtable::swap(_Hashtable&)): Likewise. * include/bits/stl_deque.h (_Deque_base::_Deque_base(_Deque_base&&)): Use _Alloc_traits::is_always_equal. (deque::operator=(deque&&)): Likewise. (deque::_M_move_assign1(deque&&, false_type)): Add comment and use __bool_constant. (swap(deque&, deque&)): Add noexcept. * include/bits/stl_list.h (list::operator=(list&&)): Use __bool_constant. (swap(list&, list&)): Add noexcept. * include/bits/stl_map.h (map::swap(map&)): Include _Compare in noexcept. (swap(map&, map&)): Add noexcept. * include/bits/stl_multimap.h (multimap::swap(multimap&)): Include _Compare in noexcept. (swap(multimap&, multimap&)): Add noexcept. * include/bits/stl_multiset.h (multiset::swap(multiset&)): Include _Compare in noexcept. (swap(multiset&, multiset&)): Add noexcept. * include/bits/stl_set.h (set::swap(set&)): Include _Compare in noexcept. (swap(set&, set&)): Add noexcept. * include/bits/stl_tree.h (_Rb_tree::operator=(_Rb_tree&&)): Include _Compare in noexcept. (_Rb_tree::_Rb_tree(_Rb_tree&&, _Node_alloc_type&&)): Use is_always_equal. * include/bits/stl_vector.h (vector::operator=(vector&&)): Use __bool_constant. (swap(vector&, vector&)): Add noexcept. * include/bits/unordered_map.h (swap(unordered_map&, unordered_map&), swap(unordered_multimap& unordered_multimap&)): Add noexcept. * include/bits/unordered_set.h (swap(unordered_set&, unordered_set&), swap(unordered_multiset& unordered_multiset&)): Add noexcept. * include/ext/alloc_traits.h (__allocator_always_compares_equal): Remove. (__alloc_traits::_S_always_equal()): Use is_always_equal instead of __allocator_always_compares_equal. * include/ext/array_allocator.h (array_allocator::is_always_equal): Define. * include/std/scoped_allocator (__any_of, __propagate_on_copy, __propagate_on_move, __propagate_on_swap): Remove. (scoped_allocator_adaptor::propagate_on_container_copy_assignment, scoped_allocator_adaptor::propagate_on_container_move_assignment, scoped_allocator_adaptor::propagate_on_container_swap): Define with __and_ instead of __any_of. (scoped_allocator_adaptor::is_always_equal): Define. * testsuite/20_util/allocator_traits/members/is_always_equal.cc: New. * testsuite/20_util/scoped_allocator/propagation.cc: Make traits derive from true_type or false_type. * testsuite/23_containers/deque/allocator/move_assign-2.cc: Add is_always_equal member and remove the trait specialization. * testsuite/23_containers/vector/52591.cc: Likewise. * testsuite/23_containers/deque/requirements/dr438/assign_neg.cc: Adjust dg-error line number. * testsuite/23_containers/deque/requirements/dr438/ constructor_1_neg.cc: Likewise. * testsuite/23_containers/deque/requirements/dr438/ constructor_2_neg.cc: Likewise. * testsuite/23_containers/deque/requirements/dr438/insert_neg.cc: Likewise. * testsuite/23_containers/list/requirements/dr438/assign_neg.cc: Likewise. * testsuite/23_containers/list/requirements/dr438/constructor_1_neg.cc: Likewise. * testsuite/23_containers/list/requirements/dr438/insert_neg.cc: Likewise. * testsuite/23_containers/vector/requirements/dr438/assign_neg.cc: Likewise. * testsuite/23_containers/vector/requirements/dr438/ constructor_1_neg.cc: Likewise. * testsuite/23_containers/vector/requirements/dr438/ constructor_2_neg.cc: Likewise. * testsuite/23_containers/vector/requirements/dr438/insert_neg.cc: Likewise. From-SVN: r225081
2015-01-05Update copyright years.Jakub Jelinek1-1/+1
From-SVN: r219188
2014-12-03hashtable.h: Fix whitespace and simplify function definitions with trailing ↵Jonathan Wakely1-158/+126
return types. * include/bits/hashtable.h: Fix whitespace and simplify function definitions with trailing return types. From-SVN: r218309
2014-10-05re PR libstdc++/63456 (unordered_map incorrectly frees _M_single_bucket. ↵François Dumont1-1/+1
Patch Included) 2014-10-05 François Dumont <fdumont@gcc.gnu.org> PR libstdc++/63456 * include/bits/hashtable.h (_M_uses_single_bucket(__bucket_type*)): Test the parameter. * testsuite/23_containers/unordered_set/63456.cc: New. From-SVN: r215905
2014-09-06hashtable_policy.h (_Prime_rehash_policy): Constructor noexcept qualified.François Dumont1-27/+32
2014-09-06 François Dumont <fdumont@gcc.gnu.org> * include/bits/hashtable_policy.h (_Prime_rehash_policy): Constructor noexcept qualified. (_Hash_code_base<>): All specialization default constructible if possible. (_Hashtable_base<>): Likewise. * include/bits/hashtable.h (_Hashtable<>()): Implementation defaulted. * include/bits/unordered_map.h (unordered_map<>::unordered_map()): New, implementation defaulted. (unordered_multimap<>::unordered_multimap()): Likewise. * include/bits/unordered_set.h (unordered_set<>::unordered_set()): Likewise. (unordered_multiset<>::unordered_multiset()): Likewise. * include/debug/unordered_map: Likewise. * include/debug/unordered_set: Likewise. * testsuite/23_containers/unordered_map/allocator/noexcept.cc (test04()): New. * testsuite/23_containers/unordered_multimap/allocator/noexcept.cc (test04()): New. * testsuite/23_containers/unordered_set/allocator/noexcept.cc (test04()): New. * testsuite/23_containers/unordered_multiset/allocator/noexcept.cc (test04()): New. From-SVN: r214986
generated by cgit v1.1 at 2025-07-15 01:06:13 +0000