Line data    Source code

       1             : // Author(s): Jan Friso Groote
       2             : // Copyright: see the accompanying file COPYING or copy at
       3             : // https://github.com/mCRL2org/mCRL2/blob/master/COPYING
       4             : //
       5             : // Distributed under the Boost Software License, Version 1.0.
       6             : // (See accompanying file LICENSE_1_0.txt or copy at
       7             : // http://www.boost.org/LICENSE_1_0.txt)
       8             : //
       9             : 
      10             : /** \file
      11             :  *
      12             :  * \brief This file contains a specialisation for hashes on pairs.
      13             :  *        This is not a part of the standard, although it ought to be part.
      14             :  *        Once it has become a part of the standard, this can be removed.
      15             :  * \author Jan Friso Groote
      16             :  */
      17             : 
      18             : #ifndef MCRL2_UTILITIES_HASH_UTILITY_H
      19             : #define MCRL2_UTILITIES_HASH_UTILITY_H
      20             : 
      21             : #include <cstddef>
      22             : #include <vector>
      23             : #include <map>
      24             : 
      25             : namespace mcrl2
      26             : {
      27             : namespace utilities
      28             : {
      29             : namespace detail
      30             : {
      31             : 
      32    19771745 : inline std::size_t hash_combine(const std::size_t h1, const std::size_t h2)
      33             : {
      34             :   // This hash function is inpired by boost.
      35    19771745 :   return h1 ^  (h2 + 0x9e3779b9 + (h1<<6) + (h1>>2));
      36             : }
      37             : 
      38             : /// \brief Auxiliary function to combine seed with a hash number.
      39   363968005 : inline std::size_t hash_combine_cheap(const std::size_t seed, const std::size_t hash_number)
      40             : {
      41             :   // Addition works better than xor, because xor maps equal inputs to 0 which
      42             :   // can lead to many collisions. However, with addition we also want to prevent
      43             :   // symmetry, i.e a + b equals b + a, so a relative cheap solution is to multiply
      44             :   // one side by a number. For this purpose we chose hnr + floor(2.5 * seed);
      45   363968005 :   return hash_number + (seed << 1) + (seed >> 1);
      46             : }
      47             : 
      48             : } //end namespace detail
      49             : } //end namespace utilities
      50             : } //end namespace mcrl2
      51             : 
      52             : namespace std
      53             : {
      54             : 
      55             : template <class X>
      56             : struct hash< std::vector < X > >
      57             : {
      58        3533 :   std::size_t operator()(const std::vector < X >& v) const
      59             :   {
      60             :     hash<X> hasher;
      61             :     // This follows boost.
      62        3533 :     std::size_t hash=0;
      63        8188 :     for(const X& x: v)
      64             :     {
      65        4655 :       hash = mcrl2::utilities::detail::hash_combine(hash,hasher(x)); 
      66             :     }
      67        3533 :     return hash;
      68             :   }
      69             : };
      70             : 
      71             : template <class X, class Y>
      72             : struct hash< std::map < X, Y > >
      73             : {
      74             :   std::size_t operator()(const std::map < X, Y >& v) const
      75             :   {
      76             :     hash<X> hasher1;
      77             :     hash<Y> hasher2;
      78             :     // This follows boost.
      79             :     std::size_t hash=0;
      80             :     for(const std::pair< X, Y>& p: v)
      81             :     {
      82             :       hash = mcrl2::utilities::detail::hash_combine(hash,
      83             :                    mcrl2::utilities::detail::hash_combine(hasher1(p.first),
      84             :                                                           hasher2(p.second)));
      85             :     }
      86             :     return hash;
      87             :   }
      88             : };
      89             : 
      90             : template <class X, class Y>
      91             : struct hash< std::pair < X, Y > >
      92             : {
      93    19763890 :   std::size_t operator()(const std::pair < X, Y >& p) const
      94             :   {
      95             :     hash<X> hasher1;
      96             :     hash<Y> hasher2;
      97             :     
      98    19763890 :     return mcrl2::utilities::detail::hash_combine(hasher1(p.first),hasher2(p.second));
      99             :   }
     100             : };
     101             : 
     102             : } // namespace std
     103             : 
     104             : 
     105             : #endif // MCRL2_UTILITIES_HASH_UTILITY_H
     106             : 
     107             :