[PATCH] Hashtable refactoring and simplification

[François Dumont]

I'd like to integrate some of the refactoring I had to do as part of my 
work on support of custom pointers in unordered containers.

Those are of course the abi compatible changes.

Thanks to the changes on _Hash_node type definition I was able to get 
rid of _Hash_code_base partial specialization. I also removed the 
smaller _Hashtable_base::_Equal_hash_code helper type. For this one I 
wonder if you prefer to keep it in place of the new 
_S_equals/_S_node_equals overloads ?

I also review where typedef are done. Mostly those done in 
_Hashtable_base have been moved in _Insert_base because it is the type 
making use of it and moreover _Insert_base knowns about the allocator 
whereas _Hashtable_base don't. It is mandatory to know the allocator to 
support its custom pointers.

Patch generated with -b option cause there is an indentation issue in 
_Hashtable_base definition.

     libstdc++: Refactor _Hashtable to prepare for custom pointers

     Limit usage of node pointers in _Hashtable implementation details 
so that when
     we move to allocator custom pointer type we do not need to add an 
_Alloc
     template parameter everywhere which would impact abi.

     This is done by reviewing node type definition. It is now based on 
new basic
     types which are not pointer dependant. The _Hashtable helper
     types are now using those new node base types and do not receive 
node pointers.

     libstdc++-v3/ChangeLog

             * include/bits/hashtable_policy.h
             (_Hash_node_value_base<>): Remove _Hash_node_base inheritance.
             (_Hash_node_code_cache<bool _Cache_hash_code>): New.
             (_Hash_node_value<typename _Value, bool _Cache_hash_code>): 
New.
             (_Hash_node<>): Inherits _Hash_node_base<> and 
_Hash_node_value<>.
             (_Map_base<>::__node_type): Remove.
             (_Map_base<>::iterator): Remove.
             (_Insert_base<>::__hash_cached): New.
             (_Insert_base<>::__constant_iterators): New.
             (_Insert_base<>::__hashtable_alloc): New.
             (_Insert_base<>::__node_type): Remove.
             (_Insert_base<>::__node_ptr): New.
             (_Hash_code_base<>): Remove specializations.
             (_Hash_code_base<>::__node_type): Remove.
             (_Hash_code_base<>::_M_bucket_index(const __node_type*, 
size_t)):
             Replace by...
             (_Hash_code_base<>::_M_bucket_index(const 
_Hash_node_value<>&, size_t)):
             ...this.
             (_Hash_code_base<>::_M_store_code(__node_type*, __hash_code)):
             Replace by...
(_Hash_code_base<>::_M_store_code(_Hash_node_code_cache<>&, __hash_code)):
             ...this.
             (_Hash_code_base<>::_M_copy_code(__node_type*, const 
__node_type*)):
             Replace by...
(_Hash_code_base<>::_M_copy_code(_Hash_node_code_cache<>&,
             const _Hash_node_code_base<>&)): ...this.
             (_Hashtable_base<>::__constant_iterators): Remove.
             (_Hashtable_base<>::__unique_keys): Remove.
             (_Hashtable_base<>::__node_type): Remove.
             (_Hashtable_base<>::iterator): Remove.
             (_Hashtable_base<>::const_iterator): Remove.
             (_Hashtable_base<>::local_iterator): Remove.
             (_Hashtable_base<>::const_local_iterator): Remove.
             (_Hashtable_base<>::__ireturn_type): Remove.
(_Hashtable_base<>::_Equal_hash_code<>::_S_equals): Replace by...
             (_Hashtable_base<>::_S_equals(__hash_code, const 
_Hash_node_code_hash<>&)):
             ...this.
(_Hashtable_base<>::_Equal_hash_code<>::_S_node_equals): Replace by...
             (_Hashtable_base<>::_S_node_equals(__hash_code,
             const _Hash_node_code_hash<>&)): ...this.
             (_Hashtable_base<>::_Equal_hash_code<>): Remove.
             (_Hashtable_base<>::_M_equals): Adapt.
             (_Hashtable_baxe<>::_M_node_equals): Adapt.
             (_Equality<>::_M_equal): Adapt.
             (_Hashtable_alloc<>::__node_ptr): New.
             (_Hashtable_alloc<>::__bucket_type): Rename into...
             (_Hashtable_alloc<>::__node_base_ptr): ...this.
             (_Hashtable_alloc<>::__bucket_alloc_type): Rename into...
             (_Hashtable_alloc<>::__buckets_alloc_type): ...this.
             (_Hashtable_alloc<>::__bucket_alloc_traits): Rename into...
             (_Hashtable_alloc<>::__buckets_alloc_traits): ...this.
             (_Hashtable_alloc<>::__buckets_ptr): 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.

All unordered containers tests run successfully on Linux x86_64.

Ok to commit once all tests run ?

François

-------------- next part --------------
A non-text attachment was scrubbed...
Name: hashtable.patch
Type: text/x-patch
Size: 54076 bytes
Desc: not available
URL: <https://gcc.gnu.org/pipermail/libstdc++/attachments/20201015/15ef8dd1/attachment-0001.bin>