libstdc++ PR 57272 Fancy pointer support in Hashtable
François Dumont
frs.dumont@gmail.com
Mon Sep 28 20:37:35 GMT 2020
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
>>
>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: hashtable_ext_ptr.patch
Type: text/x-patch
Size: 88755 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20200928/02c5a997/attachment-0001.bin>
More information about the Libstdc++
mailing list