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

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.4