spot  2.12
hash.hh
1 // -*- coding: utf-8 -*-
2 // Copyright (C) by the Spot authors, see the AUTHORS file for details.
3 //
4 // This file is part of Spot, a model checking library.
5 //
6 // Spot is free software; you can redistribute it and/or modify it
7 // under the terms of the GNU General Public License as published by
8 // the Free Software Foundation; either version 3 of the License, or
9 // (at your option) any later version.
10 //
11 // Spot is distributed in the hope that it will be useful, but WITHOUT
12 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
13 // or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public
14 // License for more details.
15 //
16 // You should have received a copy of the GNU General Public License
17 // along with this program. If not, see <http://www.gnu.org/licenses/>.
18 
19 #pragma once
20 
21 #include <climits>
22 #include <string>
23 #include <functional>
24 #include <spot/misc/hashfunc.hh>
25 
26 #include <unordered_map>
27 #include <unordered_set>
28 
29 namespace spot
30 {
31 
34  template <class T>
35  struct ptr_hash
36  {
37  // A default constructor is needed if the ptr_hash object is
38  // stored in a const member. This occur with the clang version
39  // installed by OS X 10.9.
40  ptr_hash() noexcept
41  {
42  }
43 
44  size_t operator()(const T* p) const noexcept
45  {
46  return knuth32_hash(reinterpret_cast<size_t>(p));
47  }
48  };
49 
52  typedef std::hash<std::string> string_hash;
53 
56  template<typename T>
58  {
59  // A default constructor is needed if the identity_hash object is
60  // stored in a const member.
62  {
63  }
64 
65  size_t operator()(const T& s) const noexcept
66  {
67  return s;
68  }
69  };
70 
71 
72  struct pair_hash
73  {
74  template<typename T, typename U>
75  std::size_t operator()(const std::pair<T, U> &p) const noexcept
76  {
77 
78  if constexpr (std::is_integral<T>::value
79  && sizeof(T) <= sizeof(std::size_t)/2
80  && std::is_integral<U>::value
81  && sizeof(U) <= sizeof(std::size_t)/2)
82  {
83  constexpr unsigned shift = (sizeof(std::size_t)/2)*CHAR_BIT;
84  std::size_t h = p.first;
85  h <<= shift;
86  h += p.second;
87  return h;
88  }
89  else
90  {
91  std::hash<T> th;
92  std::hash<U> uh;
93 
94  return wang32_hash(static_cast<size_t>(th(p.first)) ^
95  static_cast<size_t>(uh(p.second)));
96  }
97  }
98  };
99 
100  // From primes.utm.edu shuffled. This primes are used when we simulate
101  // transition shuffling using "primitive root modulo n" technique.
102  static const unsigned primes[144] =
103  {
104  295075531, 334214857, 314607103, 314607191, 334214891, 334214779,
105  295075421, 472882073, 256203329, 275604599, 314606953, 256203397,
106  275604547, 256203631, 275604617, 472882141, 472882297, 472882219,
107  256203229, 256203469, 275604643, 472882169, 275604803, 472882283,
108  295075463, 334214593, 295075213, 256203373, 314607019, 314607193,
109  295075399, 256203523, 314607001, 295075289, 256203293, 256203641,
110  256203307, 314607047, 295075373, 314607053, 314606977, 334214681,
111  275604691, 275604577, 472882447, 314607031, 275605019, 472882477,
112  472882499, 314607173, 295075241, 295075471, 295075367, 256203559,
113  314607233, 275604881, 334214941, 472882103, 275604821, 472882511,
114  295075357, 472882517, 314607023, 256203317, 295075337, 275605007,
115  472882391, 256203223, 334214723, 295075381, 295075423, 275604733,
116  314607113, 256203257, 472882453, 256203359, 295075283, 314607043,
117  256203403, 472882259, 314606891, 472882253, 314606917, 256203349,
118  256203457, 295075457, 472882171, 314607229, 295075513, 472882429,
119  334214953, 275604841, 295075309, 472882099, 334214467, 334214939,
120  275604869, 314607077, 314607089, 275604947, 275605027, 295075379,
121  334214861, 314606909, 334214911, 314607199, 275604983, 314606969,
122  256203221, 334214899, 256203611, 256203679, 472882337, 275604767,
123  472882199, 295075523, 472882049, 275604817, 334214561, 334214581,
124  334214663, 295075489, 295075163, 334214869, 334214521, 295075499,
125  275604913, 334214753, 334214687, 256203491, 295075153, 334214893,
126  472882411, 472882117, 275604793, 334214833, 334214591, 314607091,
127  256203419, 275604727, 256203659, 275604961, 334214557, 275604677
128  };
129 }
size_t wang32_hash(size_t key)
Thomas Wang's 32 bit hash function.
Definition: hashfunc.hh:37
std::hash< std::string > string_hash
A hash function for strings.
Definition: hash.hh:52
size_t knuth32_hash(size_t key)
Knuth's Multiplicative hash function.
Definition: hashfunc.hh:56
@ U
until
Definition: automata.hh:26
A hash function that returns identity.
Definition: hash.hh:58
Definition: hash.hh:73
A hash function for pointers.
Definition: hash.hh:36

Please direct any question, comment, or bug report to the Spot mailing list at spot@lrde.epita.fr.
Generated on Fri Feb 27 2015 10:00:07 for spot by doxygen 1.9.1