Review Hashtable extract node API

[Jonathan Wakely]

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.


-------------- next part --------------
A non-text attachment was scrubbed...
Name: patch.txt
Type: text/x-patch
Size: 4003 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20190605/91269439/attachment.bin>