Re: [PATCH] Implement C++17 node extraction and insertion (P0083R5)

2016-10-10 Thread Jonathan Wakely 

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 from a map. 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 forgot to mention another thing worth calling out.

I spoke to Richi and Michael Matz at the Cauldron and they assured me
that the middle end won't do any optimizations that would cause the
"magic happens here" part to do the wrong thing. Specifically, the
node handle for maps does this to get a non-const pointer to the
key_type in the pair:

 auto& __key = const_cast<_Key&>(__ptr->_M_valptr()->first);
 _M_pkey = _S_pointer_to(__key);
 _M_pmapped = _S_pointer_to(__ptr->_M_valptr()->second);

Where _S_pointer_to() is:

 template
   using __pointer = __ptr_rebind;

 template
   __pointer<_Tp>
   _S_pointer_to(_Tp& __obj)
   { return pointer_traits<__pointer<_Tp>>::pointer_to(__obj); }

The potentially worrying part of this is the const_cast, but as we
know that the pair is inside a non-const node allocated on the heap,
it will never be in read-only memory or actually non-modifiable. Once
we have std::launder we could consider using that, i.e.

 _M_pkey = _S_pointer_to(std::launder(__key));

Re: [PATCH] Implement C++17 node extraction and insertion (P0083R5)

2016-09-26 Thread Jonathan Wakely 

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.


This adds some assertions to check for the mistake of trying to
extract the end iterator.

Tested powerpc64le-linux, comitted to trunk.


commit 1073944c341d022d501c07b7881e7c6ead0b1fca
Author: Jonathan Wakely 
Date:   Mon Sep 26 10:35:52 2016 +0100

Add assertions to extract(const_iterator) functions

	* include/bits/stl_map.h (map::extract(const_iterator)): Assert that
	iterator is not past-the-end.
	* include/bits/stl_multimap.h (multimap::extract(const_iterator)):
	Likewise.
	* include/bits/stl_multiset.h (multiset::extract(const_iterator)):
	Likewise.
	* include/bits/stl_set.h (set::extract(const_iterator)): Likewise.
	* include/bits/unordered_map.h (unordered_map::extract(const_iterator))
	(unordered_multimap::extract(const_iterator)): Likewise.
	* include/bits/unordered_set.h (unordered_set::extract(const_iterator))
	(unordered_multiset::extract(const_iterator)): Likewise.

diff --git a/libstdc++-v3/include/bits/stl_map.h b/libstdc++-v3/include/bits/stl_map.h
index f9482e2..9a0454a 100644
--- a/libstdc++-v3/include/bits/stl_map.h
+++ b/libstdc++-v3/include/bits/stl_map.h
@@ -605,7 +605,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   /// Extract a node.
   node_type
   extract(const_iterator __pos)
-  { return _M_t.extract(__pos); }
+  {
+	__glibcxx_assert(__pos != end());
+	return _M_t.extract(__pos);
+  }
 
   /// Extract a node.
   node_type
diff --git a/libstdc++-v3/include/bits/stl_multimap.h b/libstdc++-v3/include/bits/stl_multimap.h
index 2b56824..c794b9b 100644
--- a/libstdc++-v3/include/bits/stl_multimap.h
+++ b/libstdc++-v3/include/bits/stl_multimap.h
@@ -606,7 +606,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   /// Extract a node.
   node_type
   extract(const_iterator __pos)
-  { return _M_t.extract(__pos); }
+  {
+	__glibcxx_assert(__pos != end());
+	return _M_t.extract(__pos);
+  }
 
   /// Extract a node.
   node_type
diff --git a/libstdc++-v3/include/bits/stl_multiset.h b/libstdc++-v3/include/bits/stl_multiset.h
index d7312df..d3219eb 100644
--- a/libstdc++-v3/include/bits/stl_multiset.h
+++ b/libstdc++-v3/include/bits/stl_multiset.h
@@ -549,7 +549,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   /// Extract a node.
   node_type
   extract(const_iterator __pos)
-  { return _M_t.extract(__pos); }
+  {
+	__glibcxx_assert(__pos != end());
+	return _M_t.extract(__pos);
+  }
 
   /// Extract a node.
   node_type
diff --git a/libstdc++-v3/include/bits/stl_set.h b/libstdc++-v3/include/bits/stl_set.h
index fd96dd4..140db39 100644
--- a/libstdc++-v3/include/bits/stl_set.h
+++ b/libstdc++-v3/include/bits/stl_set.h
@@ -565,7 +565,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   /// Extract a node.
   node_type
   extract(const_iterator __pos)
-  { return _M_t.extract(__pos); }
+  {
+	__glibcxx_assert(__pos != end());
+	return _M_t.extract(__pos);
+  }
 
   /// Extract a node.
   node_type
diff --git a/libstdc++-v3/include/bits/unordered_map.h b/libstdc++-v3/include/bits/unordered_map.h
index ab8a762..6776090 100644
--- a/libstdc++-v3/include/bits/unordered_map.h
+++ b/libstdc++-v3/include/bits/unordered_map.h
@@ -421,7 +421,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   /// Extract a node.
   node_type
   extract(const_iterator __pos)
-  { return _M_h.extract(__pos); }
+  {
+	__glibcxx_assert(__pos != end());
+	return _M_h.extract(__pos);
+  }
 
   /// Extract a node.
   node_type
@@ -1534,7 +1537,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   /// Extract a node.
   node_type
   extract(const_iterator __pos)
-  { return _M_h.extract(__pos); }
+  {
+	__glibcxx_assert(__pos != end());
+	return _M_h.extract(__pos);
+  }
 
   /// Extract a node.
   node_type
diff --git a/libstdc++-v3/include/bits/unordered_set.h b/libstdc++-v3/include/bits/unordered_set.h
index e5bb2be..9905257 100644
--- a/libstdc++-v3/include/bits/unordered_set.h
+++ b/libstdc++-v3/include/bits/unordered_set.h
@@ -482,7 +482,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   /// Extract a node.
   node_type
   extract(const_iterator __pos)
-  { return _M_h.extract(__pos); }
+  {
+	__glibcxx_assert(__pos != end());
+	return _M_h.extract(__pos);
+  }
 
   /// Extract a node.
   node_type
@@ -1190,7 +1193,10 @@ _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
   /// Extract a node.
   node_type
   extract(const_iterator __pos)
-  { return _M_h.extract(__pos); }
+  {
+	__glibcxx_assert(__pos != end());
+	return _M_h.extract(__pos);
+  }
 
   /// Extract a node.
   node_type

Re: [PATCH] Implement C++17 node extraction and insertion (P0083R5)

2016-09-21 Thread Jonathan Wakely 

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 from a map. 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/ma