hashtable local iterator

[François Dumont]

Hi

     Here is a new proposition to fix the unordered containers 
local_iterator Standard non-conforming regression.

     I finally introduce no modification in hashtable data model, a 
bucket is still a simple node pointer. I simply embed the necessary 
functors in local_iterator instances. However I had to put some 
constraints on functor types used to instantiate _Hashtable. If hash 
code are cached only the type used to map hash codes to bucket indexes 
needs to be empty, otherwise the extract key, h1, h2 and hash functors 
must all be empty. The consequence is that cache hash code flag default 
value in unordered_XXX types now depends on hash functor emptiness, if 
hash functor is not an empty type hash code will be put in cache so that 
local iterators are not invalidated when hashtable instances are swapped.

     I have however a remark regarding this patch. For the moment, on my 
64bits platform, sizeof(local_iterator) is 32 while it should normally 
be 24 for the 2 size_t and the node pointer. I thought about using 
inheritance in _Hash_code_base type in replacement of _M_extract, _M_h1, 
_M_h2, _M_hash fields to benefit from EBO, would it be ok ? This way I 
could replace the static assertion:

       static_assert(__or_<integral_constant<bool, __cache_hash_code>,
                           __and_<is_empty<_H1>, is_empty<_H2>,
                         is_empty<_Hash>, is_empty<_ExtractKey>>>::value,
             "Cache the hash code or make _ExtractKey, _H1 and _Hash 
functors"
             " empty");

with the more accurate:

       static_assert(__or_<integral_constant<bool, __cache_hash_code>,
                                       is_empty<_HCBase>>::value,
             "Cache the hash code or make _ExtractKey, _H1 and _Hash 
functors"
             " empty");

because H1, H2 and Hash are never used all together.

I already noticed that I couldn't inherit from both _Hash and _Equal 
because those 2 types might be identical resulting in an ambiguity. But 
between _ExtractKey, _H1, _H2 and _Hash there is no chance of ambiguity.

2011-12-19  François Dumont <fdumont@gcc.gnu.org>

         * include/bits/hashtable_policy.h (_Equal_helper<>) New.
         (_Hash_code_base): Move _Equal functor management... 
(_Hashtable_base)
         ...here, new, use _Equal_helper. (_Local_iterator_base<>,
         _Locale_iterator<>, _Locale_const_iterator<>): New, use 
_Hash_code_base,
         implementation of...
         * include/bits/hashtable.h (_Hashtable<>::local_iterator,
         _Hashtable<>::const_local_iterator): ...those. Add static 
assertions
         checking that some functors are empty depending on whether hash 
code
         is cache or not. (_Hashtable<>::_M_bucket_index): New overloads 
using
         current bucket count, use through out the _Hastable<> 
implementation.
         * include/bits/unordered_set.h (__unordered_set<>,
         __unordered_multiset<>): Cache hash code if hash functor is not 
empty.
         * include/bits/unordere_map.H (__unordered_map<>,
         __unordered_multimap<>): Likewise.
         * include/debug/unordered_map
         (unordered_map<>::_S_to_local, unordered_multimap<>::_S_to_local):
         Adapt to match new local iterator implementation.
         * include/debug/unordered_set (unordered_set<>::_S_to_local,
         unordered_multiset<>::_S_to_local): Likewise.
         * include/profile/unordered_map 
(unordered_map<>::_M_profile_destruct,
         unordered_multimap<>::_M_profile_destruct): Enhance thanks to 
usage of
         local iterators.
         * include/profile/unordered_set 
(unordered_set<>::_M_profile_destruct,
         unordered_multiset<>::_M_profile_destruct): Likewise.

François

-------------- next part --------------
A non-text attachment was scrubbed...
Name: hashtable_local_iterator.patch
Type: text/x-patch
Size: 42898 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20111219/0ca1bd6b/attachment.bin>