PR 71181 Avoid rehash after reserve

François Dumont
Sun May 22 15:16:00 GMT 2016


     To fix 71181 problem I propose to change how we deal with reserve 
called with pivot values that is to say prime numbers. Now _M_next_bkt 
always return a value higher than the input value. This way when 
reverse(97) is called we end up with 199 buckets and so enough space to 
store 97 values without rehashing.

     I have integrated in this patch several other enhancements on the 
same subject. Improvement of _M_next_resize management when reaching 
highest bucket number. Remove sentinel value in __prime_list, just need 
to limit range when calling lower_bound.

     PR libstdc++/71181
     * include/tr1/hashtable_policy.h (_S_n_primes): Minus 1 to avoid check
     on lower_bound call.
     * src/c++11/ (_Prime_rehash_policy::_M_next_bkt):
     Always return a value greater than input value. Set _M_next_resize to
     value when reaching highest prime number.
     * src/shared/ (__prime_list): Remove sentinel value.
     * testsuite/23_containers/unordered_set/hash_policy/ New.
     * testsuite/23_containers/unordered_set/max_load_factor/

Tested under Linux x86_64, ok to commit ?


-------------- next part --------------
A non-text attachment was scrubbed...
Name: 71181.patch
Type: text/x-patch
Size: 6810 bytes
Desc: not available
URL: <>

More information about the Libstdc++ mailing list