Tulip  4.0.0
Better Visualization Through Research
 All Classes Files Functions Variables Enumerations Enumerator Properties Groups Pages
tuliphash.h
1 /*
2  *
3  * This file is part of Tulip (www.tulip-software.org)
4  *
5  * Authors: David Auber and the Tulip development Team
6  * from LaBRI, University of Bordeaux 1 and Inria Bordeaux - Sud Ouest
7  *
8  * Tulip is free software; you can redistribute it and/or modify
9  * it under the terms of the GNU Lesser General Public License
10  * as published by the Free Software Foundation, either version 3
11  * of the License, or (at your option) any later version.
12  *
13  * Tulip is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
16  * See the GNU General Public License for more details.
17  *
18  */
19 ///@cond DOXYGEN_HIDDEN
20 
21 #ifndef TLP_HASH_H
22 #define TLP_HASH_H
23 
24 /**
25  * @brief This file defines what class is used to provide a hashmap.
26  * The TLP_HASH_MAP macro defines which implementation is used for hash maps.
27  * The TLP_HASH_SET macro defines which implementation is used for hash sets.
28  *
29  * TLP_BEGIN_HASH_NAMESPACE is defined to open the namespace in which the hash classes are defined, to define new hashes (e.g. for Edge).
30  * TLP_END_HASH_NAMESPACE is definde to close the namespace (only used when using std::tr1)
31  */
32 
33 //VS2010 and later can use C++0x's unordered_map; vs2008 uses boost's tr1 implementation
34 #if(defined _MSC_VER && _MSC_VER > 1500)
35 # include <unordered_map>
36 # include <unordered_set>
37 # define TLP_HASH_MAP std::unordered_map
38 # define TLP_HASH_SET std::unordered_set
39 # define TLP_BEGIN_HASH_NAMESPACE namespace std
40 # define TLP_END_HASH_NAMESPACE
41 //clang, and GCC versions prior to the 4.x series do not have tr1; using ext
42 #elif (! defined _MSC_VER && (__GNUC__ < 4 || __GNUC_MINOR__ < 1))
43 # include <tulip/tulipconf.h>
44 # if (__GNUC__ < 3)
45 # include <hash_map>
46 # include <hash_set>
47 # else
48 # include <ext/hash_map>
49 # include <ext/hash_set>
50 # endif
51 # define TLP_HASH_MAP stdext::hash_map
52 # define TLP_HASH_SET stdext::hash_set
53 # define TLP_BEGIN_HASH_NAMESPACE namespace stdext
54 # define TLP_END_HASH_NAMESPACE
55 
56 # include <string>
57 
58 namespace stdext {
59 template<> struct hash<const std::string> {
60  size_t operator()(const std::string &s) const {
61  return hash<const char *>()(s.c_str());
62  }
63 };
64 template<> struct hash<std::string> {
65  size_t operator()(const std::string &s) const {
66  return hash<const char *>()(s.c_str());
67  }
68 };
69 template<>
70 struct hash<double> {
71  size_t operator()(const double s) const {
72  return (size_t) s;
73  }
74 };
75 template<>
76 struct hash<float> {
77  size_t operator()(const float s) const {
78  return hash<unsigned int>()(*((unsigned int *) &s));
79  }
80 };
81 }
82 //MSVC < 2010 use tr1 from boost, and GCC 4.X provides tr1 too.
83 #else
84 # include <tr1/unordered_map>
85 # include <tr1/unordered_set>
86 # define TLP_HASH_MAP std::tr1::unordered_map
87 # define TLP_HASH_SET std::tr1::unordered_set
88 # define TLP_BEGIN_HASH_NAMESPACE namespace std { namespace tr1
89 # define TLP_END_HASH_NAMESPACE }
90 #endif
91 
92 // The hash_combine function from the boost library
93 // Call it repeatedly to incrementally create a hash value from several variables.
94 
95 // Explanation of the formula from StackOverflow (http://stackoverflow.com/questions/4948780/magic-numbers-in-boosthash-combine) :
96 // The magic number 0x9e3779b9 = 2^32 / ((1 + sqrt(5)) / 2) is the reciprocal of the golden ratio.
97 // It is supposed to be 32 random bits, where each is equally likely to be 0 or 1, and with no simple correlation between the bits.
98 // So including this number "randomly" changes each bit of the seed; as you say, this means that consecutive values will be far apart.
99 // Including the shifted versions of the old seed makes sure that, even if hash_value() has a fairly small range of values,
100 // differences will soon be spread across all the bits.
101 TLP_BEGIN_HASH_NAMESPACE {
102  template <class T>
103  inline void hash_combine(std::size_t & seed, const T & v) {
104  hash<T> hasher;
105  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
106  }
107 } TLP_END_HASH_NAMESPACE
108 
109 #endif
110 ///@endcond