Review Hashtable extract node API

[Jonathan Wakely]

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.