[boost] Re: [review] hash functions

From: Alberto Barbati (abarbati_at_[hidden])
Date: 2005-03-11 15:01:55

Hi,

I have a doubt about the proposed implementation of hash_value() for 
pointers, which is:

     template <class T> inline std::size_t hash_value(T* v)
     {
         return static_cast<std::size_t>(v - (T*)0);
     }

this code calls for undefined behaviour according to §5.7/6, each time v 
is a non-null pointer.

IMHO, the only reasonable way to map generic pointer values to integer 
values is through reinterpret_cast<>. The mapping would be 
implementation-defined, but it would be no worse than the intent of the 
proposed implementation (if it worked).

To be picky, in order to accomodate with implementations that may have 
sizeof(size_t) < sizeof(T*), we should use two casts:

     template <class T> inline std::size_t hash_value(T* v)
     {
         return static_cast<std::size_t>(
            reinterpret_cast<boost::uintmax_t>(v));
     }

(the right thing would be to use a C9X-ish uintptr_t type, but 
boost/cstdint.hpp does not provide such a type).

However, as the double cast may result in suboptimal code if size_t is 
large enough, a boost::enable_if trick might be used to provide an 
optimized version with just a single use of reinterpret_cast. The result 
would be something similar to:

#include <boost/utility.hpp>
#include <boost/cstdint.hpp>

namespace detail
{
   template <class T>
   struct fits_in_size_t
   {
     static const bool value = sizeof(T) <= sizeof(size_t);
   };
}

template <class T>
inline typename boost::enable_if<
   detail::fits_in_size_t<T*>, std::size_t>::type
hash_value(T* v)
{
   return reinterpret_cast<std::size_t>(v);
}

template <class T>
inline typename boost::disable_if<
   detail::fits_in_size_t<T*>, std::size_t>::type
hash_value(T* v)
{
   return static_cast<std::size_t>(
     reinterpret_cast<boost::uintmax_t>(v));
}

Unfortunately, there's one more thing... even if p == q, 
reinterpret_cast<uintmax_t>(p) is not guaranteed to be equal to 
reinterpret_cast<uintmax_t>(q) on implementations that have multiple 
internal representations for the same address. I don't think much can be 
done (in a portable way) for such platforms.

HTH,

Alberto