Review Hashtable extract node API

[François Dumont]

Hi

 Â Â Â  Here is a patch to enhance the _Hashtable extract node API and fix 
a FIXME request.

 Â Â Â  The enhancement to the extract node Api is that extract(const 
key_type&) do not call extract(const_iterator) anymore. Doing so we had 
to loop again through bucket nodes to find the previous node to the one 
to extract. Even if a bucket shall not contain many nodes (in unique key 
mode) it's easy to avoid it.

 Â Â Â  To fix the FIXME I introduced a node smart pointer type managing 
the node lifetime. The node is extracted from this smart pointer only 
when there can't be any exception raised. In the context of the node 
extract api the node handle is considered as a smart pointer. So the 
node handle will remain owner of the node in case of exception when 
reinserting it, I hope it is the expected behavior.

 Â Â Â  * include/bits/hashtable_policy.h
 Â Â Â  (struct _NodeSmartPointer<_NodeAlloc>): New.
 Â Â Â  (_Map_base<>::operator[](const key_type&)): Use latter, adapt.
 Â Â Â  (_Map_base<>::operator[](key_type&&)): Likewise.
 Â Â Â  * include/bits/hashtable.h
 Â Â Â  (_Hashtable<>::__node_sp_t): New.
 Â Â Â  (_Hashtable<>::_M_insert_unique_node(size_type, __hash_code,
 Â Â Â  __node_type*, size_type)): Replace by...
(_Hashtable<>::_M_insert_unique_node<_NodeAccessor>(const key_type&,
 Â Â Â  size_type, __hash_code, const _NodeAccessor&, size_type)): ...that.
 Â Â Â  (_Hashtable<>::_M_insert_multi_node(__node_type*, __hash_code,
 Â Â Â  __node_type*)): Replace by...
(_Hashtable<>::_M_insert_multi_node<_NodeAccessor>(__node_type*,
 Â Â Â  __hash_code, const _NodeAccessor&)): ...that.
 Â Â Â  (_Hashtable<>::_M_reinsert_node): Adapt.
 Â Â Â  (_Hashtable<>::_M_reinsert_node_multi): Adapt.
 Â Â Â  (_Hashtable<>::_M_extract_node(size_t, __node_base*)): New.
 Â Â Â  (_Hashtable<>::extract(const_iterator)): Use latter.
 Â Â Â  (_Hashtable<>::extract(const _Key&)): Likewise.
 Â Â Â  (_Hashtable<>::_M_merge_unique): Adapt.
 Â Â Â  (_Hashtable<>::_M_emplace<_Args>(true_type, _Args&&...)): Adapt.
 Â Â Â  (_Hashtable<>::_M_emplace<_Args>(const_iterator, false_type,
 Â Â Â  _Args&&...)): Adapt.

Tested under Linux x86_64.

Ok to commit ?

François

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