This mail got rejected from gcc-patches as spam. The attachment can be
found at https://gcc.gnu.org/ml/libstdc++/2016-09/msg00115.html
On 21/09/16 14:48 +0100, Jonathan Wakely wrote:
This implements container node extraction/insertion, and merging. The
patch includes Debug Mode support and pretty printers for the node
handles.
Most of the changes are fairly straightforward, with two things worth
pointing out.
There's a FIXME in bits/hashtable.h due to an exception-safety issue.
If the hash function or equality predicate throws then the node is
destroyed and deallocated. It would be better to leave it unchanged in
the node_handle argument.
I didn't want to make all map and multimap specializations friends of
each other (and similarly for all sets and multisets, and again for
the unordered ones). That would make it too easy to accidentally
access the internals of a map<T,U> from a map<V,W>. So I defined the
_Rb_tree_merge_helper and _Hash_merge_helper class templates to
mediate access, so that any access to a "foreign" container type must
be done through that type, and only certain internals can be obtained.
I'll probably commit this tomorrow.
* 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.
