hash policy patch

[François Dumont]

On 07/28/2011 10:49 PM, Paolo Carlini wrote:
> Hi,
>
>>     I forget to talk about this modification. Yes with this refactoring the float value is casted to size_t before the call to lower_bound. There is no modification here because when the float value is casted to size_t we lose only the decimal part but not the integer part. As the research is done on integer values only the integer part of __min_bkts is important. Even if __min_bkts is greater than size_t max value then the cast will always give this size_t mas value and the call to lower_bound will always give the larger prime number from the list of prime numbers.
>>
>>     This is in fact even a good side effect of this patch, lower_bound will only be instantiated once with the size_t value.
> Ok, thanks for the analysis. Then let's commit these bits for now.
>
> Paolo
Hi

     After some additional time spent on hashtable I prefer to do this 
new proposal. It fixes
- Yet some issues with hash policy that was still able to give a bucket 
count for which load_factor == max_load_factor, Standard says 
load_factor < max_load_factor. Note that in fact the refactoring to 
generalize use of _M_next_bkt had indeed a side effect which is that 
when looking for instance for 11.5 lower_bound was returning 13 but now 
that it is casted to integer it will return 11. Not only that reason now 
_M_next_bkt takes an optional __strict bool parameter signaling if the 
returned value shall be not only not shorter but even larger.
- In hashtable implementation I removed usages of std::max that was 
potentially leaving the hashtable in an inconsistent state with a hash 
policy next resize value not matching the current bucket count. It was 
not really a bug because the next resize value was updated on the next 
insertion but at the cost of a useless floating point operation.
- I deal with allocation failure directly in _M_rehash method to avoid 
introducing new try/catch blocks. I also reset hash policy next resize 
value when the container is emptied on a hash functor exception.
- In __rehash_policy I only commit the new hash policy instance if the 
rehash operation succeeded. The associated test change_load_factor.cc 
requires exception support, is there already a way to detect it or I 
need to add a new dg-require-exceptions dejaGnu macro ?

On a design point of view, with the new interactions introduced between 
hash policy and hashtable, I wonder if accepting the hash policy as a 
template parameter is still necessary. We could perhaps simplify the 
_Hashtable template type unless you prefer to find a new cleaner hash 
policy contract.

2011-08-03  François Dumont <francois.cppdevs@free.fr>

         * include/bits/hashtable_policy.h (_Prime_rehash_policy): Reuse
         _M_next_bkt as much as possible. Fix corner case leading to load
         factor equals max load factor.
         * include/bits/hashtable.h: Fix management of hash policy next 
resize
         value so that it stays in sync with bucket count.
         * testsuite/23_containers/unordered_set/cons/range_cons.cc: New.
         * testsuite/23_containers/unordered_set/hash_policy/
         change_load_factor.cc, rehash.cc: New.

François
-------------- next part --------------
A non-text attachment was scrubbed...
Name: hashtable.patch
Type: text/x-patch
Size: 14265 bytes
Desc: not available
URL: <http://gcc.gnu.org/pipermail/libstdc++/attachments/20110802/9c93c491/attachment.bin>