[Boost-commit] svn:boost r40264 - trunk/boost/functional/detail

From: daniel_james_at_[hidden]
Date: 2007-10-21 04:36:47

Author: danieljames
Date: 2007-10-21 04:36:47 EDT (Sun, 21 Oct 2007)
New Revision: 40264
URL: http://svn.boost.org/trac/boost/changeset/40264

Log:
New algorithm for hash floating point numbers.

Text files modified: 
   trunk/boost/functional/detail/hash_float.hpp |    32 ++++++++++++++++++++++++++------        
   1 files changed, 26 insertions(+), 6 deletions(-)

Modified: trunk/boost/functional/detail/hash_float.hpp
==============================================================================
--- trunk/boost/functional/detail/hash_float.hpp	(original)
+++ trunk/boost/functional/detail/hash_float.hpp	2007-10-21 04:36:47 EDT (Sun, 21 Oct 2007)
@@ -15,6 +15,7 @@
 #endif
 
 #include <boost/functional/detail/float_functions.hpp>
+#include <boost/integer/static_log2.hpp>
 #include <boost/cstdint.hpp>
 #include <boost/limits.hpp>
 #include <boost/assert.hpp>
@@ -82,23 +83,42 @@
         }
 
 #else
+
         template <class T>
         inline std::size_t float_hash_impl(T v)
         {
             int exp = 0;
+
             v = boost::hash_detail::call_frexp(v, &exp);
 
-            std::size_t seed = 0;
+            // A postive value is easier to hash, so combine the
+            // sign with the exponent.
+            if(v < 0) {
+                v = -v;
+                exp += std::numeric_limits<T>::max_exponent -
+                    std::numeric_limits<T>::min_exponent;
+            }
+
+            // The result of frexp is always between 0.5 and 1, so its
+            // top bit will always be 1. Subtract by 0.5 to remove that.
+            v -= T(0.5);
+            v = boost::hash_detail::call_ldexp(v,
+                    std::numeric_limits<std::size_t>::digits + 1);
+            std::size_t seed = static_cast<std::size_t>(v);
+            v -= seed;
 
+            // ceiling(digits(T) * log2(radix(T))/ digits(size_t)) - 1;
             std::size_t const length
-                = (std::numeric_limits<T>::digits +
-                        std::numeric_limits<int>::digits - 1)
-                / std::numeric_limits<int>::digits;
+                = (std::numeric_limits<T>::digits *
+                        boost::static_log2<std::numeric_limits<T>::radix>::value
+                        - 1)
+                / std::numeric_limits<std::size_t>::digits;
 
             for(std::size_t i = 0; i != length; ++i)
             {
-                v = boost::hash_detail::call_ldexp(v, std::numeric_limits<int>::digits);
-                int const part = static_cast<int>(v);
+                v = boost::hash_detail::call_ldexp(v,
+                        std::numeric_limits<std::size_t>::digits);
+                std::size_t part = static_cast<std::size_t>(v);
                 v -= part;
                 hash_float_combine(seed, part);
             }