![]() |
Tulip
4.6.0
Better Visualization Through Research
|
00001 /* 00002 * 00003 * This file is part of Tulip (www.tulip-software.org) 00004 * 00005 * Authors: David Auber and the Tulip development Team 00006 * from LaBRI, University of Bordeaux 00007 * 00008 * Tulip is free software; you can redistribute it and/or modify 00009 * it under the terms of the GNU Lesser General Public License 00010 * as published by the Free Software Foundation, either version 3 00011 * of the License, or (at your option) any later version. 00012 * 00013 * Tulip is distributed in the hope that it will be useful, 00014 * but WITHOUT ANY WARRANTY; without even the implied warranty of 00015 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. 00016 * See the GNU General Public License for more details. 00017 * 00018 */ 00019 ///@cond DOXYGEN_HIDDEN 00020 00021 #ifndef TLP_HASH_H 00022 #define TLP_HASH_H 00023 00024 // to search for _LIBCPP_VERSION 00025 #include <ciso646> 00026 00027 /** 00028 * @brief This file defines what class is used to provide a hashmap. 00029 * The TLP_HASH_MAP macro defines which implementation is used for hash maps. 00030 * The TLP_HASH_SET macro defines which implementation is used for hash sets. 00031 * 00032 * 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). 00033 * TLP_END_HASH_NAMESPACE is definde to close the namespace (only used when using std::tr1) 00034 * TLP_HASH_NAMESPACE allows to use a specific hasher class when declaring a hash set or a hash map. 00035 */ 00036 00037 //VS2010 and later can use C++0x's unordered_map; vs2008 uses boost's tr1 implementation 00038 #if defined(_MSC_VER) && (_MSC_VER > 1500) 00039 # define TLP_USE_UNORDERED_MAP 00040 #elif defined(__GXX_EXPERIMENTAL_CXX0X__) || __cplusplus >= 201103L || defined(_LIBCPP_VERSION) 00041 # define TLP_USE_UNORDERED_MAP 00042 #endif 00043 00044 #ifdef TLP_USE_UNORDERED_MAP 00045 # include <unordered_map> 00046 # include <unordered_set> 00047 # define TLP_HASH_MAP std::unordered_map 00048 # define TLP_HASH_SET std::unordered_set 00049 # define TLP_HASH_NAMESPACE std 00050 # define TLP_BEGIN_HASH_NAMESPACE namespace std 00051 # define TLP_END_HASH_NAMESPACE 00052 //clang, and GCC versions prior to the 4.x series do not have tr1; using ext 00053 #elif (! defined _MSC_VER && (__GNUC__ < 4 || __GNUC_MINOR__ < 1)) 00054 # include <tulip/tulipconf.h> 00055 # if (__GNUC__ < 3) 00056 # include <hash_map> 00057 # include <hash_set> 00058 # else 00059 # include <ext/hash_map> 00060 # include <ext/hash_set> 00061 # endif 00062 # define TLP_HASH_MAP stdext::hash_map 00063 # define TLP_HASH_SET stdext::hash_set 00064 # define TLP_HASH_NAMESPACE stdext 00065 # define TLP_BEGIN_HASH_NAMESPACE namespace stdext 00066 # define TLP_END_HASH_NAMESPACE 00067 00068 # include <string> 00069 00070 namespace stdext { 00071 template<> struct hash<const std::string> { 00072 size_t operator()(const std::string &s) const { 00073 return hash<const char *>()(s.c_str()); 00074 } 00075 }; 00076 template<> struct hash<std::string> { 00077 size_t operator()(const std::string &s) const { 00078 return hash<const char *>()(s.c_str()); 00079 } 00080 }; 00081 template<> 00082 struct hash<double> { 00083 size_t operator()(const double s) const { 00084 return (size_t) s; 00085 } 00086 }; 00087 template<> 00088 struct hash<float> { 00089 size_t operator()(const float s) const { 00090 return hash<unsigned int>()(*((unsigned int *) &s)); 00091 } 00092 }; 00093 } 00094 //MSVC < 2010 use tr1 from boost, and GCC 4.X provides tr1 too. 00095 #else 00096 # include <tr1/unordered_map> 00097 # include <tr1/unordered_set> 00098 # define TLP_HASH_MAP std::tr1::unordered_map 00099 # define TLP_HASH_SET std::tr1::unordered_set 00100 # define TLP_HASH_NAMESPACE std::tr1 00101 # define TLP_BEGIN_HASH_NAMESPACE namespace std { namespace tr1 00102 # define TLP_END_HASH_NAMESPACE } 00103 #endif 00104 00105 // The hash_combine function from the boost library 00106 // Call it repeatedly to incrementally create a hash value from several variables. 00107 00108 // Explanation of the formula from StackOverflow (http://stackoverflow.com/questions/4948780/magic-numbers-in-boosthash-combine) : 00109 // The magic number 0x9e3779b9 = 2^32 / ((1 + sqrt(5)) / 2) is the reciprocal of the golden ratio. 00110 // 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. 00111 // So including this number "randomly" changes each bit of the seed; as you say, this means that consecutive values will be far apart. 00112 // Including the shifted versions of the old seed makes sure that, even if hash_value() has a fairly small range of values, 00113 // differences will soon be spread across all the bits. 00114 TLP_BEGIN_HASH_NAMESPACE { 00115 template <class T> 00116 inline void hash_combine(std::size_t & seed, const T & v) { 00117 hash<T> hasher; 00118 seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2); 00119 } 00120 } TLP_END_HASH_NAMESPACE 00121 00122 #endif 00123 ///@endcond