intrusive/detail/hash_combine.hpp

0001 // Copyright 2005-2014 Daniel James.
0002 // Distributed under the Boost Software License, Version 1.0. (See accompanying
0003 // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0004 //
0005 //  Based on Peter Dimov's proposal
0006 //  http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2005/n1756.pdf
0007 //  issue 6.18.
0008 //
0009 //  This also contains public domain code from MurmurHash. From the
0010 //  MurmurHash header:
0011 //
0012 // MurmurHash3 was written by Austin Appleby, and is placed in the public
0013 // domain. The author hereby disclaims copyright to this source code.
0014 //
0015 // Copyright 2021 Ion Gaztanaga
0016 // Refactored the original boost/container_hash/hash.hpp to avoid
0017 // any heavy std header dependencies to just combine two hash
0018 // values represented in a std::size_t type.
0019
0020 #ifndef BOOST_INTRUSIVE_DETAIL_HASH_COMBINE_HPP
0021 #define BOOST_INTRUSIVE_DETAIL_HASH_COMBINE_HPP
0022
0023 #ifndef BOOST_CONFIG_HPP
0024 #  include <boost/config.hpp>
0025 #endif
0026
0027 #if defined(BOOST_HAS_PRAGMA_ONCE)
0028 #  pragma once
0029 #endif
0030
0031 #include <boost/cstdint.hpp>
0032
0033 #if defined(_MSC_VER)
0034 #  include <stdlib.h>
0035 #  define BOOST_INTRUSIVE_HASH_ROTL32(x, r) _rotl(x,r)
0036 #else
0037 #  define BOOST_INTRUSIVE_HASH_ROTL32(x, r) (x << r) | (x >> (32 - r))
0038 #endif
0039
0040 namespace boost {
0041 namespace intrusive {
0042 namespace detail {
0043
0044 template <typename SizeT>
0045 inline void hash_combine_size_t(SizeT& seed, SizeT value)
0046 {
0047    seed ^= value + 0x9e3779b9 + (seed<<6) + (seed>>2);
0048 }
0049
0050 inline void hash_combine_size_t(boost::uint32_t& h1, boost::uint32_t k1)
0051 {
0052    const uint32_t c1 = 0xcc9e2d51;
0053    const uint32_t c2 = 0x1b873593;
0054
0055    k1 *= c1;
0056    k1 = BOOST_INTRUSIVE_HASH_ROTL32(k1,15);
0057    k1 *= c2;
0058
0059    h1 ^= k1;
0060    h1 = BOOST_INTRUSIVE_HASH_ROTL32(h1,13);
0061    h1 = h1*5+0xe6546b64;
0062 }
0063
0064
0065    // Don't define 64-bit hash combine on platforms without 64 bit integers,
0066    // and also not for 32-bit gcc as it warns about the 64-bit constant.
0067    #if !defined(BOOST_NO_INT64_T) && \
0068        !(defined(__GNUC__) && ULONG_MAX == 0xffffffff)
0069    inline void hash_combine_size_t(boost::uint64_t& h, boost::uint64_t k)
0070    {
0071       const boost::uint64_t m = UINT64_C(0xc6a4a7935bd1e995);
0072       const int r = 47;
0073
0074       k *= m;
0075       k ^= k >> r;
0076       k *= m;
0077
0078       h ^= k;
0079       h *= m;
0080
0081       // Completely arbitrary number, to prevent 0's
0082       // from hashing to 0.
0083       h += 0xe6546b64;
0084    }
0085
0086    #endif // BOOST_NO_INT64_T
0087
0088 }  //namespace detail {
0089 }  //namespace intrusive {
0090 }  //namespace boost {
0091
0092 #endif   //BOOST_INTRUSIVE_DETAIL_HASH_COMBINE_HPP