/home/mhx/git/github/libmoost/include/moost/algorithm/fast_hash.hpp

Go to the documentation of this file.

/* vim:set ts=3 sw=3 sts=3 et: */
#ifndef MOOST_ALGORITHM_FAST_HASH_HPP
#define MOOST_ALGORITHM_FAST_HASH_HPP

#include <functional>
#include <string>

#include <boost/type_traits/is_pod.hpp>
#include <boost/static_assert.hpp>

namespace moost { namespace algorithm {

// *** BIG IMPORTANT WARNING!!! ***
// If you plan to use fast_hash to hash a custom type, including structs you
// need to understand that they can and probably will contain padding. Since
// the compiler is not at liberty to initialise padding, if you create two
// instances of a struct and initialise each member with the same value there
// is a very good change when you hash each instance you will generate
// different digests. The only way to make this safe is to use memset to zero
// out the whole object first. Note that struct foo = {0} does NOT set all
// bytes in the objects memory to 0, it does a member by member initialisation
// and thus padding is still uninitialised.
// Also, this should NOT be used for non-POD types, since the memory layout
// of a non-POD type is compiler specific and there can be no assumptions
// made. If you need to hash a custom object you are better off making an
// array of bytes out of the various member values that should form part
// of the hash and then send that to fast_hash. For example, if we have
// a non-POD class that contains of key/value pairs and the key is made up of
// 2 integer values (a composite key) this would be one safe way to create
// a hash from the key...
//       int32_t i32s[] = {key.first, key.second};
//       size_ t h = moost::algorithm::fast_hash(i32s, sizeof(i32s));


static const size_t DEFAULT_SEED = 5381;

//#define moost_fasthash_default_seed__ 5381

inline size_t fast_hash(const void* data_in, size_t size, size_t seed = DEFAULT_SEED)
{
   const unsigned char*    data = (const unsigned char*) data_in;

// [13/6/2011 ricky] Not really sure why this is unsigned int (it's not portable)
//                   but I've added the explicit cast to shut up Windows!
#ifdef WIN32
   unsigned int h = (unsigned int) seed;
#else
   unsigned int h = seed;
#endif

   while (size > 0) {
      size--;
      h = (h << 16) + (h << 6) - h + (unsigned) data[size];
   }
   return h;
}

template <size_t TSeed = DEFAULT_SEED>
struct FastHashFunctor
{
   template <typename T>
   size_t operator()(const T& p) const
   {
#ifndef MOOST_FASTHASH_NO_ISPOD_CHECK
      BOOST_STATIC_ASSERT((boost::is_pod<T>::value));
#endif

      return fast_hash(&p, sizeof(T), TSeed);
   }

   size_t operator()( const void* key, size_t size ) const
   { return fast_hash(key, size, TSeed); }

   // overrides default seed
   size_t operator()( const void* key, size_t size, size_t seed ) const
   { return fast_hash(key, size, seed); }

   // specialization for strings
   size_t operator()( const std::string& str) const
   { return fast_hash( str.data(), str.size(), TSeed ); }

   // specialization for strings, override seed
   size_t operator()( const std::string& str, size_t seed) const
   { return fast_hash( str.data(), str.size(), seed ); }
};

//#undef moost_fasthash_default_seed__

typedef FastHashFunctor<> FastHash;


}} // end of namespaces

#endif // MOOST_ALGORITHM_FAST_HASH_HPP