Review Hashtable extract node API

[Jonathan Wakely]

On 05/06/19 20:18 +0100, Jonathan Wakely wrote:
>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.

Of course all this code is completely wrong, because it uses raw
pointers not the allocator's pointer type. But that's a much bigger
problem that needs to be solved separately.