spot  2.12
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 
24 namespace 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.1