worldhash.h

Go to the documentation of this file.

/*
  This file is part of MADNESS.

  Copyright (C) 2007,2010 Oak Ridge National Laboratory

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA

  For more information please contact:

  Robert J. Harrison
  Oak Ridge National Laboratory
  One Bethel Valley Road
  P.O. Box 2008, MS-6367

  email: harrisonrj@ornl.gov
  tel:   865-241-3937
  fax:   865-572-0680


  $Id$
*/


#ifndef MADNESS_WORLD_WORLDHASH_H__INCLUDED
#define MADNESS_WORLD_WORLDHASH_H__INCLUDED

#include <madness/madness_config.h>
#include <madness/world/typestuff.h>
#include <madness/world/enable_if.h>
#include <stdint.h>
#include <cstddef>
#include <iterator>

// Bob Jenkin's "lookup v3" hash from http://www.burtleburtle.net/bob/c/lookup3.c.
extern "C" {
    uint32_t hashword(const uint32_t *k, size_t length, uint32_t initval);
    uint32_t hashlittle(const void *key, size_t length, uint32_t initval);
}

namespace madness {

    // Hash, hash_value, hash_combine, and hash_range a la Boost.

    typedef std::size_t hashT;


    template <class T>
    inline typename enable_if_c<std::is_fundamental<T>::value &&
        ((sizeof(T)%sizeof(uint32_t)) == 0),
        hashT>::type
    hash_value(const T t) {
        hashT result = 0ul;
        result = hashword(reinterpret_cast<const uint32_t*>(&t),
            std::integral_constant<std::size_t,sizeof(T)/sizeof(uint32_t)>::value, 0u);
        return result;
    }


    template <class T>
    inline typename madness::enable_if_c<std::is_fundamental<T>::value &&
        ((sizeof(T)%sizeof(uint32_t)) != 0),
        hashT>::type
    hash_value(const T t) {
        hashT result = 0ul;
        result = hashlittle(reinterpret_cast<const void*>(&t), sizeof(T), 0u);
        return result;
    }


    template <typename T>
    inline hashT hash_value(const T* t) {
        const unsigned long n = reinterpret_cast<unsigned long>(t);
        return hash_value(n);
    }


    template <typename T>
    inline typename enable_if_c<!(std::is_fundamental<T>::value ||
        std::is_pointer<T>::value || std::is_array<T>::value), hashT>::type
    hash_value(const T& t) {
        return t.hash();
    }


    template <typename T>
    inline hashT hash_value(const std::basic_string<T>& t) {
        return hash_range(t.c_str(), t.size());
    }


    template <typename T>
    struct Hash {


        hashT operator()(const T& t) const {
            return hash_value(t);
        }
    }; // struct Hash

    namespace detail {
        // We don't hash anything here. It is just used for combining a hashed
        // value with a seed.
        inline void combine_hash(hashT& seed, hashT hash) {
            seed ^= hash + 0x9e3779b9 + (seed<<6) + (seed>>2);
        }
    }


    template <class T>
    inline void hash_combine(hashT& seed, const T& v) {
        Hash<T> hasher;
        detail::combine_hash(seed, hasher(v));
    }


    template <class It>
    inline void hash_range(hashT& seed, It first, It last) {
        Hash<typename std::iterator_traits<It>::value_type> hasher;
        for(; first != last; ++first)
            detail::combine_hash(seed, hasher(*first));
    }


    template <class It>
    inline hashT hash_range(It first, It last) {
        hashT seed = 0;
        hash_range(seed, first, last);

        return seed;
    }


    template <class T, std::size_t n>
    inline hashT hash_range(const T(&t)[n]) {
        return hash_range(t, n);
    }


    template <class T, std::size_t n>
    inline void hash_range(hashT& seed, const T(&t)[n]) {
        hash_range(seed, t, n);
    }


    template <class T>
    inline typename enable_if<std::is_fundamental<T> >::type
    hash_range(hashT& seed, const T* t, std::size_t n) {
        const std::size_t bytes = n * sizeof(T);
        if((bytes % sizeof(uint32_t)) == 0)
            seed = hashword(reinterpret_cast<const uint32_t *>(t), bytes/sizeof(uint32_t), seed);
        else
            seed = hashlittle(static_cast<const void *>(t), bytes, seed);
    }


    template <class T>
    inline typename disable_if<std::is_fundamental<T> >::type
    hash_range(hashT& seed, const T* t, std::size_t n) {
        hash_range(seed, t, t + n);
    }


    template <class T>
    inline hashT hash_range(const T* t, std::size_t n) {
        hashT seed = 0ul;
        hash_range(seed, t, n);
        return seed;
    }

} // namespace madness


#endif // MADNESS_WORLD_WORLDHASH_H__INCLUDED