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

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