MADNESS  0.10.1
worldhash.h
Go to the documentation of this file.
1 /*
2  This file is part of MADNESS.
3 
4  Copyright (C) 2007,2010 Oak Ridge National Laboratory
5 
6  This program is free software; you can redistribute it and/or modify
7  it under the terms of the GNU General Public License as published by
8  the Free Software Foundation; either version 2 of the License, or
9  (at your option) any later version.
10 
11  This program is distributed in the hope that it will be useful,
12  but WITHOUT ANY WARRANTY; without even the implied warranty of
13  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14  GNU General Public 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, write to the Free Software
18  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
19 
20  For more information please contact:
21 
22  Robert J. Harrison
23  Oak Ridge National Laboratory
24  One Bethel Valley Road
25  P.O. Box 2008, MS-6367
26 
27  email: harrisonrj@ornl.gov
28  tel: 865-241-3937
29  fax: 865-572-0680
30 */
31 
32 #ifndef MADNESS_WORLD_WORLDHASH_H__INCLUDED
33 #define MADNESS_WORLD_WORLDHASH_H__INCLUDED
34 
35 /*!
36  \file worldhash.h
37  \brief Defines hash functions for use in distributed containers
38  \addtogroup hashing
39  @{
40 
41 MADNESS uses hashing functions are modeled after Boost.Functional/Hash. It has
42 many similar function calls including hash_value, hash_combine, and hash_range.
43 In addition, it is also compatible with C++ TR1 hashing functors. The
44 \c madness::Hash functor interface is identical to both boost::hash and
45 \c std::hash , and any one of these may be used. By default, MADNESS hashing
46 functions can hash all fundamental types including integral types, floating
47 point types, pointer types, std::string, std::wstring, and std::array. Presently
48 \c hashT is typedef to \c std::size_t .
49 
50 Since having a good hash is important, we are using Bob Jenkin's "lookup v3"
51 hash from http://www.burtleburtle.net/bob/c/lookup3.c. The preferred interface
52 for these function is with the \c madness::Hash<T> functor, but you can also use
53 hash_value or the "lookup v3" interface directly.
54 
55 \b Note: Bob Jenkin's "lookup v3" hash returns a uint32_t hash value, which is
56 cast to std::size_t. This is done for compatibility with std::hash.
57 
58 \b WARNING: While both std::hash and madness::Hash have the same interface, they
59 will not generate the same hash values from the same key value.
60 
61 MADNESS hashing consists of one functor and three functions
62  \li \c madness::Hash is the hash functor and the primary interface for hashing
63  \li \c hash_value() is for hashing a single value and is the function used by the Hash functor
64  \li \c hash_range() is for hashing a group of values. You can use this function to hash
65  an iterator range, a C-style array, or a pointer.
66  \li \c hash_combine() hashs a given value and combines it with a seed. This is
67  useful for combining multiple elements into a single hash value.
68 
69 There are several options for creating and using hash functions for your custom
70 types. The easiest method is to define a \c hash_value function for your key
71 type in the same namespace. This function will automatically be used by MADNESS
72 hashing containers. The hashing function should have the following form.
73 \code
74 namespace MyNamespace {
75 
76  class Key {
77  // ...
78  };
79 
80  madness::hashT hash_value(const Key& t) {
81  // ...
82  }
83 
84 } // namespace MyNamespace
85 \endcode
86 If your object is in the \c madness namespace, you may also use the intrusive
87 method and define a hash member function for your key.
88 \code
89 namespace madness {
90  class Key {
91  public:
92 
93  // ...
94 
95  madness::hashT hash() const {
96  // ...
97  }
98  };
99 }
100 \endcode
101 You can create a specialization of madness::Hash for your type directly.
102 \code
103 class Key {
104  // ...
105 };
106 
107 namespace madness {
108 
109  template <>
110  struct Hash<Key> {
111  hashT operator()(const Key& a) const {
112  // ...
113  }
114  };
115 
116 } // namespace madness
117 \endcode
118 If you use any of the above methods, MADNESS hash_combine and hash_range functions
119 will be able to hash your custom types.
120 
121 In addition to these methods, you can use std::hash, boost::hash, or create your
122 own custom hashing functor that has the same form as madness::hash. However, if
123 you want to use a hashing functor other than madness::Hash, you will need to
124 provide the appropriate template parameter to the hashing container.
125 
126 */
127 
128 #include <madness/madness_config.h>
129 #include <stdint.h>
130 #include <cstddef>
131 #include <iterator>
132 #include <type_traits>
133 
134 // Bob Jenkin's "lookup v3" hash from http://www.burtleburtle.net/bob/c/lookup3.c.
135 extern "C" {
136  uint32_t hashword(const uint32_t *k, size_t length, uint32_t initval);
137  uint32_t hashlittle(const void *key, size_t length, uint32_t initval);
138 }
139 
140 namespace madness {
141 
142  // Hash, hash_value, hash_combine, and hash_range a la Boost.
143 
144  /// The hash value type
145  typedef std::size_t hashT;
146 
147  /// Hash a single fundamental object
148 
149  /// \tparam T The fundamental type
150  /// \param t The object to hash
151  /// \return The hashed value
152  /// \note Use heavily optimized hashword when sizeof(T) is multiple
153  /// of sizeof(uint32_t) and presumably correctly aligned.
154  template <class T>
155  inline typename std::enable_if<std::is_fundamental<T>::value &&
156  ((sizeof(T)%sizeof(uint32_t)) == 0),
157  hashT>::type
158  hash_value(const T t) {
159  hashT result = 0ul;
160  result = hashword(reinterpret_cast<const uint32_t*>(&t),
161  std::integral_constant<std::size_t,sizeof(T)/sizeof(uint32_t)>::value, 0u);
162  return result;
163  }
164 
165  /// Hash a single fundamental object
166 
167  /// \tparam T The fundamental type
168  /// \param t The object to hash
169  /// \return The hashed value
170  template <class T>
171  inline typename std::enable_if<std::is_fundamental<T>::value &&
172  ((sizeof(T)%sizeof(uint32_t)) != 0),
173  hashT>::type
174  hash_value(const T t) {
175  hashT result = 0ul;
176  result = hashlittle(reinterpret_cast<const void*>(&t), sizeof(T), 0u);
177  return result;
178  }
179 
180  /// Hash a pointer address
181 
182  /// \tparam T The pointer type
183  /// \param t The pointer to be hashed
184  /// \return The hashed value
185  template <typename T>
186  inline hashT hash_value(const T* t) {
187  const unsigned long n = reinterpret_cast<unsigned long>(t);
188  return hash_value(n);
189  }
190 
191  /// Hash a class object
192 
193  /// \tparam T The class type
194  /// \param t The object to hash
195  /// \return \c t.hash()
196  template <typename T, typename = std::enable_if_t<std::is_same_v<decltype(std::declval<const T&>().hash()),hashT>>>
197  inline auto
198  hash_value(const T& t) {
199  return t.hash();
200  }
201 
202  /// Hash a std::basic_string
203 
204  /// \tparam T The character type
205  /// \param t The string to hash
206  /// \return The hashed value of the string
207  template <typename T>
208  inline hashT hash_value(const std::basic_string<T>& t);
209 
210  /// Hash a std::pair
211 
212  /// \param t a pair to hash
213  /// \return The hashed value of \p t
214  template <typename T, typename R>
215  inline hashT hash_value(const std::pair<T,R>& t);
216 
217  /// Hash functor
218 
219  /// This hash functor calls hash_value for the given type, \c T . The
220  /// namespace for hash_value function is not specified so you are free to
221  /// implement your own version for your data type as follows:
222  /// \code
223  /// namespace MyNamespace {
224  /// class MyClass;
225  /// madness::hashT hash_value(const MyClass& t) {
226  /// // ...
227  /// }
228  /// } // namespace MyNamespace
229  /// \endcode
230  /// or you can specialize this functor directly.
231  /// \tparam T The object type to hash
232  template <typename T>
233  struct Hash {
234 
235  /// Hashing function wrapper
236 
237  /// \param t The object to be hashed
238  /// \return The hashed value
239  hashT operator()(const T& t) const {
240  return hash_value(t);
241  }
242  }; // struct Hash
243 
244  namespace detail {
245  /// Internal use only
246  // We don't hash anything here. It is just used for combining a hashed
247  // value with a seed.
248  inline void combine_hash(hashT& seed, hashT hash) {
249  seed ^= hash + 0x9e3779b9 + (seed<<6) + (seed>>2);
250  }
251  }
252 
253  /// Combine hash values
254 
255  /// This function uses the standard hash function.
256  /// \tparam T The type to hash
257  /// \param[in,out] seed The initial hash seed value
258  /// \param[in] v The value to be hashed
259  template <class T>
260  inline void hash_combine(hashT& seed, const T& v) {
261  Hash<T> hasher;
262  detail::combine_hash(seed, hasher(v));
263  }
264 
265  template <typename T, typename R>
266  inline hashT hash_value(const std::pair<T,R>& t) {
267  hashT result = hash_value(t.first);
268  hash_combine(result, hash_value(t.second));
269  return result;
270  }
271 
272 
273 
274 
275  /// \tparam It the iterator type
276  /// \param[in,out] seed The initial hash seed value
277  /// \param[in] first The first element of the iterator range to be hashed
278  /// \param[in] last The end of the iterator range to be hashed
279  template <class It>
280  inline void hash_range(hashT& seed, It first, It last) {
282  for(; first != last; ++first)
283  detail::combine_hash(seed, hasher(*first));
284  }
285 
286  /// Combine the hash values of an iterator range
287 
288  /// \tparam It the iterator type
289  /// \param[in] first The first element of the iterator range to be hashed
290  /// \param[in] last The end of the iterator range to be hashed
291  /// \return The hashed iterator range
292  template <class It>
293  inline hashT hash_range(It first, It last) {
294  hashT seed = 0;
295  hash_range(seed, first, last);
296 
297  return seed;
298  }
299 
300  /// Combine the hash values of a C-style array
301 
302  /// \tparam T The type to be hashed
303  /// \tparam n The size of the C-style array
304  /// \param[in] t The array to be hashed
305  /// \return The hashed array value
306  template <class T, std::size_t n>
307  inline hashT hash_range(const T(&t)[n]) {
308  return hash_range(t, n);
309  }
310 
311  /// Combine the hash values of a C-style array
312 
313  /// \tparam T The type to be hashed
314  /// \tparam n The size of the C-style array
315  /// \param[in,out] seed The initial hash seed value
316  /// \param[in] t The array to be hashed
317  /// \note This function uses std::hash
318  template <class T, std::size_t n>
319  inline void hash_range(hashT& seed, const T(&t)[n]) {
320  hash_range(seed, t, n);
321  }
322 
323  /// Combine the hash values of a pointer range
324 
325  /// \tparam T The type to be hashed
326  /// \param[in,out] seed The initial hash seed value
327  /// \param[in] t A pointer to the beginning of the range to be hashed
328  /// \param[in] n The number of elements to hashed
329  /// \note May use heavily optimized hashword when n * sizeof(T) is multiple
330  /// of sizeof(uint32_t) and presumably correctly aligned.
331  template <class T>
332  inline typename std::enable_if<std::is_fundamental<T>::value >::type
333  hash_range(hashT& seed, const T* t, std::size_t n) {
334  const std::size_t bytes = n * sizeof(T);
335  if((bytes % sizeof(uint32_t)) == 0)
336  seed = hashword(reinterpret_cast<const uint32_t *>(t), bytes/sizeof(uint32_t), seed);
337  else
338  seed = hashlittle(static_cast<const void *>(t), bytes, seed);
339  }
340 
341  /// Combine the hash values of a pointer range
342 
343  /// \tparam T The type to be hashed
344  /// \param[in,out] seed The initial hash seed value
345  /// \param[in] t A pointer to the beginning of the range to be hashed
346  /// \param[in] n The number of elements to hashed
347  template <class T>
348  inline typename std::enable_if<!std::is_fundamental<T>::value >::type
349  hash_range(hashT& seed, const T* t, std::size_t n) {
350  hash_range(seed, t, t + n);
351  }
352 
353  /// Combine the hash values of a pointer range
354 
355  /// \tparam T The type to be hashed
356  /// \param t A pointer to the beginning of the range to be hashed
357  /// \param n The number of elements to hashed
358  /// \return The hashed pointer range value
359  template <class T>
360  inline hashT hash_range(const T* t, std::size_t n) {
361  hashT seed = 0ul;
362  hash_range(seed, t, n);
363  return seed;
364  }
365 
366  template <typename T>
367  inline hashT hash_value(const std::basic_string<T>& t) {
368  return hash_range(t.c_str(), t.size());
369  }
370 
371 
372 } // namespace madness
373 
374 ///@}
375 
376 #endif // MADNESS_WORLD_WORLDHASH_H__INCLUDED
auto T(World &world, response_space &f) -> response_space
Definition: global_functions.cc:34
uint32_t hashword(const uint32_t *k, size_t length, uint32_t initval)
Definition: lookup3.c:177
uint32_t hashlittle(const void *key, size_t length, uint32_t initval)
Definition: lookup3.c:240
static const double v
Definition: hatom_sf_dirac.cc:20
static const double length
Definition: hedft.cc:48
Macros and tools pertaining to the configuration of MADNESS.
void combine_hash(hashT &seed, hashT hash)
Internal use only.
Definition: worldhash.h:248
File holds all helper structures necessary for the CC_Operator and CC2 class.
Definition: DFParameters.h:10
void hash_range(hashT &seed, It first, It last)
Definition: worldhash.h:280
void hash_combine(hashT &seed, const T &v)
Combine hash values.
Definition: worldhash.h:260
std::size_t hashT
The hash value type.
Definition: worldhash.h:145
std::string type(const PairType &n)
Definition: PNOParameters.h:18
madness::hashT hash_value(const std::array< T, N > &a)
Hash std::array with madness hash.
Definition: array_addons.h:78
static const long k
Definition: rk.cc:44
Hash functor.
Definition: worldhash.h:233
hashT operator()(const T &t) const
Hashing function wrapper.
Definition: worldhash.h:239
double u(const double x, const double expnt)
Definition: testperiodic.cc:56