spot 2.12.2
hashfunc.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 <cstddef>
22#include <type_traits>
23
24namespace spot
25{
28
31
36 inline size_t
37 wang32_hash(size_t key)
38 {
39 // We assume that size_t has at least 32bits.
40 key += ~(key << 15);
41 key ^= (key >> 10);
42 key += (key << 3);
43 key ^= (key >> 6);
44 key += ~(key << 11);
45 key ^= (key >> 16);
46 return key;
47 }
48
55 inline size_t
56 knuth32_hash(size_t key)
57 {
58 // 2654435761 is the golden ratio of 2^32. The right shift of 3
59 // bits assumes that all objects are aligned on a 8 byte boundary.
60 return (key >> 3) * 2654435761U;
61 }
62
63
65 template<class T, class Enable = void>
66 struct fnv
67 {};
68
70 template<class T>
71 struct fnv<T, typename std::enable_if<sizeof(T) == 4>::type>
72 {
73 static_assert(std::is_integral<T>::value && std::is_unsigned<T>::value,
74 "Fowler-Noll-Vo hash requires an unsigned integral type");
75 static constexpr T init = 2166136261UL;
76 static constexpr T prime = 16777619UL;
77 };
78
80 template<class T>
81 struct fnv<T, typename std::enable_if<sizeof(T) == 8>::type>
82 {
83 static_assert(std::is_integral<T>::value && std::is_unsigned<T>::value,
84 "Fowler-Noll-Vo hash requires an unsigned integral type");
85 static constexpr T init = 14695981039346656037ULL;
86 static constexpr T prime = 1099511628211ULL;
87 };
88
93 template<class It>
94 size_t
95 fnv_hash(It begin, It end)
96 {
97 size_t res = fnv<size_t>::init;
98 for (; begin != end; ++begin)
99 {
100 res ^= *begin;
101 res *= fnv<size_t>::prime;
102 }
103 return res;
104 }
105
107}
size_t fnv_hash(It begin, It end)
Fowler-Noll-Vo hash function.
Definition: hashfunc.hh:95
size_t wang32_hash(size_t key)
Thomas Wang's 32 bit hash function.
Definition: hashfunc.hh:37
size_t knuth32_hash(size_t key)
Knuth's Multiplicative hash function.
Definition: hashfunc.hh:56
Definition: automata.hh:26
Struct for Fowler-Noll-Vo parameters.
Definition: hashfunc.hh:67

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