On 05/06/19 17:43 +0100, Jonathan Wakely wrote:
On 05/06/19 17:22 +0100, Jonathan Wakely wrote:
On 04/06/19 19:19 +0200, François Dumont wrote:
@@ -669,18 +670,19 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__node_base*
_M_get_previous_node(size_type __bkt, __node_base* __n);
- // Insert node with hash code __code, in bucket bkt if no rehash (assumes
- // no element with its key already present). Take ownership of the node,
- // deallocate it on exception.
+ // Insert node with key __k and hash code __code, in bucket __bkt if no
+ // rehash (assumes no element with its key already present).
+ template<typename _NodeAccessor>
iterator
- _M_insert_unique_node(size_type __bkt, __hash_code __code,
- __node_type* __n, size_type __n_elt = 1);
+ _M_insert_unique_node(const key_type& __k, size_type __bkt,
+ __hash_code __code, const _NodeAccessor&,
+ size_type __n_elt = 1);
- // Insert node with hash code __code. Take ownership of the node,
- // deallocate it on exception.
+ // Insert node with hash code __code.
+ template<typename _NodeAccessor>
iterator
- _M_insert_multi_node(__node_type* __hint,
- __hash_code __code, __node_type* __n);
+ _M_insert_multi_node(__node_type* __hint, __hash_code __code,
+ const _NodeAccessor& __node_accessor);
It looks like most times you call these functions you pass an
identical lambda expression, but each of those lambda expressions will
create a unique type. That means you create different instantiations
of the function templates even though they do exactly the same thing.
That's just generating multiple copies of identical code. Passing in a
function object to provide the node pointer doesn't really seem
necessary anyway, so if it results in larger executables it's really
not desirable.
Also I didn't really like the name NodeAccessor. It's not an accessor,
because it performs ownership transfer. Invoking __node_accessor()
returns a __node_type* by releasing it from the previous owner (by
setting the owner's pointer member to null).
Passing a const reference to something called NodeAccessor does not
make it clear that it performs a mutating operation like that! If the
_M_insert_unique_node and _M_insert_multi_node functions did the
__node_accessor() call *before* rehashing, and rehashing threw an
exception, then they would leak. So it's important that the
__node_acessor() call happens at the right time, and so it's important
to name it well.
In my suggested patch the naming isn't misleading, because we just
pass a raw __node_type* and have a new comment saying:
// Takes ownership of __n if insertion succeeds, throws otherwise.
The function doesn't have a callable with non-local effects that
modifies an object outside the function. Because the caller sets the
previous owner's pointer to null there's no danger of it happening at
the wrong time; it can only happen after the function has returned and
ownership transfer has completed.
As a further evolution that simplifies some uses of _Scoped_node we
could give it a constructor that allocates a node and constructs an
element, as in the attached patch.
commit cba81aa3c4b41bef140de30e9651c5134ee2f5ef
Author: Jonathan Wakely <jwak...@redhat.com>
Date: Wed Jun 5 20:12:01 2019 +0100
with _Scoped_node constructor that creates the node
diff --git a/libstdc++-v3/include/bits/hashtable.h b/libstdc++-v3/include/bits/hashtable.h
index 87a15c8d037..ab579a7059e 100644
--- a/libstdc++-v3/include/bits/hashtable.h
+++ b/libstdc++-v3/include/bits/hashtable.h
@@ -259,9 +259,18 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
// Simple RAII type for managing a node containing an element
struct _Scoped_node
{
- _Scoped_node(__hashtable_alloc* __h, __node_type* __n)
+ // Take ownership of a node with a constructed element.
+ _Scoped_node(__node_type* __n, __hashtable_alloc* __h)
: _M_h(__h), _M_node(__n) { }
+ // Allocate a node and construct an element within it.
+ template<typename... _Args>
+ _Scoped_node(__hashtable_alloc* __h, _Args&&... __args)
+ : _M_h(__h),
+ _M_node(__h->_M_allocate_node(std::forward<_Args>(__args)...))
+ { }
+
+ // Destroy element and deallocate node.
~_Scoped_node() { if (_M_node) _M_h->_M_deallocate_node(_M_node); };
_Scoped_node(const _Scoped_node&) = delete;
@@ -1653,9 +1662,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
-> pair<iterator, bool>
{
// First build the node to get access to the hash code
- _Scoped_node __node {
- this, this->_M_allocate_node(std::forward<_Args>(__args)...)
- };
+ _Scoped_node __node { this, std::forward<_Args>(__args)... };
const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
__hash_code __code = this->_M_hash_code(__k);
size_type __bkt = _M_bucket_index(__k, __code);
@@ -1681,9 +1688,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
-> iterator
{
// First build the node to get its hash code.
- _Scoped_node __node {
- this, this->_M_allocate_node(std::forward<_Args>(__args)...)
- };
+ _Scoped_node __node { this, std::forward<_Args>(__args)... };
const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
__hash_code __code = this->_M_hash_code(__k);
@@ -1797,7 +1802,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
if (__node_type* __node = _M_find_node(__bkt, __k, __code))
return { iterator(__node), false };
- _Scoped_node __node{ this, __node_gen(std::forward<_Arg>(__v)) };
+ _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
auto __pos
= _M_insert_unique_node(__k, __bkt, __code, __node._M_node, __n_elt);
__node._M_node = nullptr;
@@ -1822,7 +1827,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
__hash_code __code = this->_M_hash_code(this->_M_extract()(__v));
// Second allocate new node so that we don't rehash if it throws.
- _Scoped_node __node{ this, __node_gen(std::forward<_Arg>(__v)) };
+ _Scoped_node __node{ __node_gen(std::forward<_Arg>(__v)), this };
const key_type& __k = this->_M_extract()(__node._M_node->_M_v());
auto __pos
= _M_insert_multi_node(__hint._M_cur, __k, __code, __node._M_node);
diff --git a/libstdc++-v3/include/bits/hashtable_policy.h b/libstdc++-v3/include/bits/hashtable_policy.h
index 7cc3f5c6d03..f5809c7443a 100644
--- a/libstdc++-v3/include/bits/hashtable_policy.h
+++ b/libstdc++-v3/include/bits/hashtable_policy.h
@@ -711,9 +711,9 @@ namespace __detail
typename __hashtable::_Scoped_node __node {
__h,
- __h->_M_allocate_node(std::piecewise_construct,
- std::tuple<const key_type&>(__k),
- std::tuple<>())
+ std::piecewise_construct,
+ std::tuple<const key_type&>(__k),
+ std::tuple<>()
};
auto __pos
= __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node);
@@ -738,9 +738,9 @@ namespace __detail
typename __hashtable::_Scoped_node __node {
__h,
- __h->_M_allocate_node(std::piecewise_construct,
- std::forward_as_tuple(std::move(__k)),
- std::tuple<>())
+ std::piecewise_construct,
+ std::forward_as_tuple(std::move(__k)),
+ std::tuple<>()
};
auto __pos
= __h->_M_insert_unique_node(__k, __bkt, __code, __node._M_node);
