Following recent changes on _Hashtable I rebase the patch and completely 
review it.

I managed to integrate the allocator custom pointer type without 
touching to _Hashtable base types like _Hash_code_base or 
_Hashtable_base. However I cannot see how to use the custom pointer type 
without impacting the node types like _Hash_node_base which now takes a 
template parameter, the custom pointer type.

On an abi point of view node types are different however the data 
structure is the same. The only difference is that the _Hash_node_base 
_M_nxt is now a _Hash_node<> custom pointer rather than a simple 
_Hash_node_base*.

Even if this patch can't go in because of the abi breaking change I am 
going to adapt some of the code simplifications for master. Especially 
the _Hash_code_base and _Local_iterator_base simplifications.

Let me know if you can think of a way to integrate the custom pointer 
without impacting abi. Unless impacting node types and associated 
iterator types is fine even if I already noticed that pretty printer 
tests are broken with those changes.

François


On 15/05/20 11:12 pm, François Dumont wrote:
> 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
>>
>