Tulip  5.0.0
Large graphs analysis and drawing
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
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 // to search for _LIBCPP_VERSION
25 #include <ciso646>
26 
27 /**
28  * @brief This file defines what class is used to provide a hashmap.
29  * The TLP_HASH_MAP macro defines which implementation is used for hash maps.
30  * The TLP_HASH_SET macro defines which implementation is used for hash sets.
31  *
32  * 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).
33  * TLP_END_HASH_NAMESPACE is definde to close the namespace (only used when using std::tr1)
34  * TLP_HASH_NAMESPACE allows to use a specific hasher class when declaring a hash set or a hash map.
35  */
36 
37 //VS2010 and later can use C++0x's unordered_map; vs2008 uses boost's tr1 implementation
38 #if defined(_MSC_VER) && (_MSC_VER > 1500)
39 # define TLP_USE_UNORDERED_MAP
40 #elif defined(__GXX_EXPERIMENTAL_CXX0X__) || __cplusplus >= 201103L || defined(_LIBCPP_VERSION)
41 # define TLP_USE_UNORDERED_MAP
42 #endif
43 
44 #ifdef TLP_USE_UNORDERED_MAP
45 # include <unordered_map>
46 # include <unordered_set>
47 # define TLP_HASH_MAP std::unordered_map
48 # define TLP_HASH_SET std::unordered_set
49 # define TLP_HASH_NAMESPACE std
50 # define TLP_BEGIN_HASH_NAMESPACE namespace std
51 # define TLP_END_HASH_NAMESPACE
52 //clang, and GCC versions prior to the 4.x series do not have tr1; using ext
53 #elif (! defined _MSC_VER && (__GNUC__ < 4 || __GNUC_MINOR__ < 1))
54 # include <tulip/tulipconf.h>
55 # if (__GNUC__ < 3)
56 # include <hash_map>
57 # include <hash_set>
58 # else
59 # include <ext/hash_map>
60 # include <ext/hash_set>
61 # endif
62 # define TLP_HASH_MAP stdext::hash_map
63 # define TLP_HASH_SET stdext::hash_set
64 # define TLP_HASH_NAMESPACE stdext
65 # define TLP_BEGIN_HASH_NAMESPACE namespace stdext
66 # define TLP_END_HASH_NAMESPACE
67 
68 # include <string>
69 
70 namespace stdext {
71 template<> struct hash<const std::string> {
72  size_t operator()(const std::string &s) const {
73  return hash<const char *>()(s.c_str());
74  }
75 };
76 template<> struct hash<std::string> {
77  size_t operator()(const std::string &s) const {
78  return hash<const char *>()(s.c_str());
79  }
80 };
81 template<>
82 struct hash<double> {
83  size_t operator()(const double s) const {
84  return (size_t) s;
85  }
86 };
87 template<>
88 struct hash<float> {
89  size_t operator()(const float s) const {
90  return hash<unsigned int>()(*((unsigned int *) &s));
91  }
92 };
93 }
94 //MSVC < 2010 use tr1 from boost, and GCC 4.X provides tr1 too.
95 #else
96 # include <tr1/unordered_map>
97 # include <tr1/unordered_set>
98 # define TLP_HASH_MAP std::tr1::unordered_map
99 # define TLP_HASH_SET std::tr1::unordered_set
100 # define TLP_HASH_NAMESPACE std::tr1
101 # define TLP_BEGIN_HASH_NAMESPACE namespace std { namespace tr1
102 # define TLP_END_HASH_NAMESPACE }
103 #endif
104 
105 // The hash_combine function from the boost library
106 // Call it repeatedly to incrementally create a hash value from several variables.
107 
108 // Explanation of the formula from StackOverflow (http://stackoverflow.com/questions/4948780/magic-numbers-in-boosthash-combine) :
109 // The magic number 0x9e3779b9 = 2^32 / ((1 + sqrt(5)) / 2) is the reciprocal of the golden ratio.
110 // 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.
111 // So including this number "randomly" changes each bit of the seed; as you say, this means that consecutive values will be far apart.
112 // Including the shifted versions of the old seed makes sure that, even if hash_value() has a fairly small range of values,
113 // differences will soon be spread across all the bits.
114 TLP_BEGIN_HASH_NAMESPACE {
115  template <class T>
116  inline void hash_combine(std::size_t & seed, const T & v) {
117  hash<T> hasher;
118  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
119  }
120 } TLP_END_HASH_NAMESPACE
121 
122 #endif
123 ///@endcond