Tulip  4.6.0
Better Visualization Through Research
library/tulip-core/include/tulip/tuliphash.h
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
 All Classes Files Functions Variables Enumerations Enumerator Properties