libstdc++ PR 57272 Fancy pointer support in Hashtable

[François Dumont]

I think I completed this evolution.

I eventually used ref to node pointer as much as possible and even use 
move semantic on it.

My prerequisite for this to work is that nullptr can be assign on the 
fancy pointer and that a fancy pointer to __node_type is assignable 
implicitely to a fancy pointer to __node_base.

     * include/bits/hashtable_policy.h (_Hashtable_base): Add _Alloc
     template parameter.
         (_ReuseOrAllocNode<>::__node_type): Remove.
         (_ReuseOrAllocNode<>::__node_pointer): New.
         (_ReuseOrAllocNode(__node_pointer, __hashtable_alloc&)): Adapt 
to use
         latter.
         (_ReuseOrAllocNode<>::operator()(_Arg&&)): Return latter.
         (_AllocNode<>::__node_type): Remove.
         (_AllocNode<>::__node_pointer): New.
         (_AllocNode<>::operator()<>(_Arg&&)): Return latter.
         (_Hash_node_base<>): Add _NodePtr template parameter.
         (_Hash_node_value_base<>): Likewise.
         (_Hash_node<>): Add _Ptr template parameter.
         (_Hash_node<>::_M_next()): Remove.
         (_Node_iterator_base<>): Use _NodePtr template parameter.
         (operator==(const _Node_iterator_base&, const 
_Node_iterator_base&)):
         Make inline friend.
         (operator!=(const _Node_iterator_base&, const 
_Node_iterator_base&)):
         Likewise.
         (_Node_iterator<>): Use _NodePtr template parameter.
         (_Node_const_iterator<>): Use _NodePtr template parameter.
         (_Map_base<>::__node_type): Remove.
         (_Map_base<>::__node_pointer): New.
         (_Hash_code_base<>): Add _Alloc template parameter.
         (_Hash_code_base<>::__pointer): New.
         (_Hash_code_base<>::__node_pointer): New.
         (_Hash_code_base<>::__node_ptr_arg_t): New.
         (_Local_iterator_base<>): Add _Alloc template parameter. 
Inherit from
         _Node_iterator_base<>.
         (_Local_iterator_base<>::__base_node_iter): New.
         (_Local_iterator_base<>::_M_cur): Remove.
         (_Local_iterator_base<>::_M_incr()): Adapt.
         (_Local_iterator_base<>::_M_curr()): Remove.
     (operator==(const _Local_iterator_base<>&,
     const _Local_iterator_base<>&)): Remove.
         (operator!=(const _Local_iterator_base<>&,
         const _Local_iterator_base<>&)): Remove.
         (_Local_iterator<>): Add _Alloc and _NodePtr template parameters.
         (_Local_const_iterator<>): Likewise.
         (_Hashtable_base<>): Add _Alloc template parameter.
         (_Hashtable_alloc<>::__node_pointer): New.
         (_Hashtable_alloc<>::__bucket_pointer): New.
         (_Hashtable_alloc<>::_M_allocate_node): Adapt.
         (_Hashtable_alloc<>::_M_deallocate_node): Adapt.
         (_Hashtable_alloc<>::_M_deallocate_node_ptr): Adapt.
         (_Hashtable_alloc<>::_M_deallocate_nodes): Adapt.
         (_Hashtable_alloc<>::_M_allocate_buckets): Adapt.
         (_Hashtable_alloc<>::_M_deallocate_buckets): Adapt.
         * include/bits/hashtable.h (_Hashtable<>): Adapt.
     (_Hashtable<>::_M_begin()): Remove.
         * include/debug/unordered_map: Adapt.
         * include/debug/unordered_set: Adapt.
         * testsuite/23_containers/unordered_map/allocator/ext_ptr.cc: New.
         * 
testsuite/23_containers/unordered_multimap/allocator/ext_ptr.cc: New.
         * 
testsuite/23_containers/unordered_multiset/allocator/ext_ptr.cc: New.
         * testsuite/23_containers/unordered_set/allocator/ext_ptr.cc

Tested under Linux x86_64.

Ok to commit ?

François

On 19/04/20 7:31 pm, François Dumont wrote:
> Here is my work in progress to use allocator pointer type. This type 
> is used both as the node pointer and as the buckets pointer.
>
> Rather than adapting _Local_iterator_base like _Node_iterator_base I 
> prefer to just make it inherits from _Node_iterator_base. It 
> simplifies its implementation and avoids to provided dedicated 
> comparison operators.
>
> Now I wonder if I need to consider Phil Bouchard comment regarding how 
> node pointers are being passed, either by value or reference. I 
> already chose to pass them as rvalue references in some occasions and 
> even lvalue reference like in _M_bucket_index method. Do you think I 
> need to continue this way ? Maybe I should use some conditional type, 
> if raw pointer we pass by value and otherwise we pass by ref ?
>
> François
>

-------------- next part --------------
A non-text attachment was scrubbed...
Name: hashtable_ext_ptr.patch
Type: text/x-patch
Size: 94662 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20200515/9a6d2c50/attachment-0001.bin>