spot  2.9.8.dev
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<const char*>(p)
52  - static_cast<const char*>(nullptr));
53  }
54  };
55 
58  typedef std::hash<std::string> string_hash;
59 
62  template<typename T>
63  struct identity_hash:
64  public std::unary_function<const T&, size_t>
65  {
66  // A default constructor is needed if the identity_hash object is
67  // stored in a const member.
69  {
70  }
71 
72  size_t operator()(const T& s) const noexcept
73  {
74  return s;
75  }
76  };
77 
78 
79  struct pair_hash
80  {
81  template<typename T, typename U>
82  std::size_t operator()(const std::pair<T, U> &p) const noexcept
83  {
84 
85  if constexpr (std::is_integral<T>::value
86  && sizeof(T) <= sizeof(std::size_t)/2
87  && std::is_integral<U>::value
88  && sizeof(U) <= sizeof(std::size_t)/2)
89  {
90  constexpr unsigned shift = (sizeof(std::size_t)/2)*CHAR_BIT;
91  std::size_t h = p.first;
92  h <<= shift;
93  h += p.second;
94  return h;
95  }
96  else
97  {
98  std::hash<T> th;
99  std::hash<U> uh;
100 
101  return wang32_hash(static_cast<size_t>(th(p.first)) ^
102  static_cast<size_t>(uh(p.second)));
103  }
104  }
105  };
106 
107  // From primes.utm.edu shuffled. This primes are used when we simulate
108  // transition shuffling using "primitive root modulo n" technique.
109  static const unsigned primes[144] =
110  {
111  295075531, 334214857, 314607103, 314607191, 334214891, 334214779,
112  295075421, 472882073, 256203329, 275604599, 314606953, 256203397,
113  275604547, 256203631, 275604617, 472882141, 472882297, 472882219,
114  256203229, 256203469, 275604643, 472882169, 275604803, 472882283,
115  295075463, 334214593, 295075213, 256203373, 314607019, 314607193,
116  295075399, 256203523, 314607001, 295075289, 256203293, 256203641,
117  256203307, 314607047, 295075373, 314607053, 314606977, 334214681,
118  275604691, 275604577, 472882447, 314607031, 275605019, 472882477,
119  472882499, 314607173, 295075241, 295075471, 295075367, 256203559,
120  314607233, 275604881, 334214941, 472882103, 275604821, 472882511,
121  295075357, 472882517, 314607023, 256203317, 295075337, 275605007,
122  472882391, 256203223, 334214723, 295075381, 295075423, 275604733,
123  314607113, 256203257, 472882453, 256203359, 295075283, 314607043,
124  256203403, 472882259, 314606891, 472882253, 314606917, 256203349,
125  256203457, 295075457, 472882171, 314607229, 295075513, 472882429,
126  334214953, 275604841, 295075309, 472882099, 334214467, 334214939,
127  275604869, 314607077, 314607089, 275604947, 275605027, 295075379,
128  334214861, 314606909, 334214911, 314607199, 275604983, 314606969,
129  256203221, 334214899, 256203611, 256203679, 472882337, 275604767,
130  472882199, 295075523, 472882049, 275604817, 334214561, 334214581,
131  334214663, 295075489, 295075163, 334214869, 334214521, 295075499,
132  275604913, 334214753, 334214687, 256203491, 295075153, 334214893,
133  472882411, 472882117, 275604793, 334214833, 334214591, 314607091,
134  256203419, 275604727, 256203659, 275604961, 334214557, 275604677
135  };
136 }
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:58
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:65
Definition: hash.hh:80
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