hashtable local iterator

[François Dumont]

Hi

     Since modification of hashtable implementation I was quite unhappy 
of the impact on local_iterator and especially on the end(size_type bkt) 
method that required to loop through all bucket nodes to access the 
past-the-end one. This is why I would like to propose, if it is still 
time, this new local iterator implementation that allow to implement 
begin(size_t)/end(size_t) in constant time. Note that:
- this new iterator type needs a pointer to its parent container to work 
which is quite unusual on normal iterators.
- I had to make an overload of _M_bucket_index public to use it in local 
iterator implem', do you prefer to introduce a friend declaration ?

     Thanks to this new implementation I have been able to enhance 
unordered container profile mode because it now relies on local 
iterator. This way we can use most of the time the cached hash code 
while with the current implementation the hash code must be recomputed 
for each element in the container.

Tested under x86_64 linux.

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

         * include/bits/hashtable_policy.h (_Local_iterator_base,
         _Locale_iterator, _Locale_const_iterator): New, implementation 
of...
         * include/bits/hashtable.h (_Hashtable<>::local_iterator,
         _Hashtable<>::const_local_iterator): ...those. 
(_M_bucket_index): New
         overloads using current bucket count, use through out the 
_Hastable<>
         implementation.
         * 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.

If it is ok to commit I will only be able to do so on thursday.

François
-------------- next part --------------
A non-text attachment was scrubbed...
Name: hashtable_local_iterator.patch
Type: text/x-patch
Size: 25629 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20111213/1b792126/attachment.bin>