diff options
Diffstat (limited to 'cutl/details/boost/functional/hash/detail')
5 files changed, 555 insertions, 0 deletions
diff --git a/cutl/details/boost/functional/hash/detail/float_functions.hpp b/cutl/details/boost/functional/hash/detail/float_functions.hpp new file mode 100644 index 0000000..0686928 --- /dev/null +++ b/cutl/details/boost/functional/hash/detail/float_functions.hpp @@ -0,0 +1,246 @@ + +// Copyright 2005-2009 Daniel James. +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) + +#if !defined(BOOST_FUNCTIONAL_HASH_DETAIL_FLOAT_FUNCTIONS_HPP) +#define BOOST_FUNCTIONAL_HASH_DETAIL_FLOAT_FUNCTIONS_HPP + +#include <cutl/details/boost/config.hpp> +#include <cutl/details/boost/config/no_tr1/cmath.hpp> + +#if defined(_MSC_VER) && (_MSC_VER >= 1020) +# pragma once +#endif + +// The C++ standard requires that the C float functions are overloarded +// for float, double and long double in the std namespace, but some of the older +// library implementations don't support this. On some that don't, the C99 +// float functions (frexpf, frexpl, etc.) are available. +// +// The following tries to automatically detect which are available. + +namespace cutl_details_boost { + namespace hash_detail { + + // Returned by dummy versions of the float functions. + + struct not_found { + // Implicitly convertible to float and long double in order to avoid + // a compile error when the dummy float functions are used. + + inline operator float() const { return 0; } + inline operator long double() const { return 0; } + }; + + // A type for detecting the return type of functions. + + template <typename T> struct is; + template <> struct is<float> { char x[10]; }; + template <> struct is<double> { char x[20]; }; + template <> struct is<long double> { char x[30]; }; + template <> struct is<cutl_details_boost::hash_detail::not_found> { char x[40]; }; + + // Used to convert the return type of a function to a type for sizeof. + + template <typename T> is<T> float_type(T); + + // call_ldexp + // + // This will get specialized for float and long double + + template <typename Float> struct call_ldexp + { + typedef double float_type; + + inline double operator()(double a, int b) const + { + using namespace std; + return ldexp(a, b); + } + }; + + // call_frexp + // + // This will get specialized for float and long double + + template <typename Float> struct call_frexp + { + typedef double float_type; + + inline double operator()(double a, int* b) const + { + using namespace std; + return frexp(a, b); + } + }; + } +} + +// A namespace for dummy functions to detect when the actual function we want +// isn't available. ldexpl, ldexpf etc. might be added tby the macros below. +// +// AFAICT these have to be outside of the boost namespace, as if they're in +// the boost namespace they'll always be preferable to any other function +// (since the arguments are built in types, ADL can't be used). + +namespace cutl_details_boost_hash_detect_float_functions { + template <class Float> cutl_details_boost::hash_detail::not_found ldexp(Float, int); + template <class Float> cutl_details_boost::hash_detail::not_found frexp(Float, int*); +} + +// Macros for generating specializations of call_ldexp and call_frexp. +// +// check_cpp and check_c99 check if the C++ or C99 functions are available. +// +// Then the call_* functions select an appropriate implementation. +// +// I used c99_func in a few places just to get a unique name. +// +// Important: when using 'using namespace' at namespace level, include as +// little as possible in that namespace, as Visual C++ has an odd bug which +// can cause the namespace to be imported at the global level. This seems to +// happen mainly when there's a template in the same namesapce. + +#define BOOST_HASH_CALL_FLOAT_FUNC(cpp_func, c99_func, type1, type2) \ +namespace cutl_details_boost_hash_detect_float_functions { \ + template <class Float> \ + cutl_details_boost::hash_detail::not_found c99_func(Float, type2); \ +} \ + \ +namespace cutl_details_boost { \ + namespace hash_detail { \ + namespace c99_func##_detect { \ + using namespace std; \ + using namespace cutl_details_boost_hash_detect_float_functions; \ + \ + struct check { \ + static type1 x; \ + static type2 y; \ + BOOST_STATIC_CONSTANT(bool, cpp = \ + sizeof(float_type(cpp_func(x,y))) \ + == sizeof(is<type1>)); \ + BOOST_STATIC_CONSTANT(bool, c99 = \ + sizeof(float_type(c99_func(x,y))) \ + == sizeof(is<type1>)); \ + }; \ + } \ + \ + template <bool x> \ + struct call_c99_##c99_func : \ + cutl_details_boost::hash_detail::call_##cpp_func<double> {}; \ + \ + template <> \ + struct call_c99_##c99_func<true> { \ + typedef type1 float_type; \ + \ + template <typename T> \ + inline type1 operator()(type1 a, T b) const \ + { \ + using namespace std; \ + return c99_func(a, b); \ + } \ + }; \ + \ + template <bool x> \ + struct call_cpp_##c99_func : \ + call_c99_##c99_func< \ + ::cutl_details_boost::hash_detail::c99_func##_detect::check::c99 \ + > {}; \ + \ + template <> \ + struct call_cpp_##c99_func<true> { \ + typedef type1 float_type; \ + \ + template <typename T> \ + inline type1 operator()(type1 a, T b) const \ + { \ + using namespace std; \ + return cpp_func(a, b); \ + } \ + }; \ + \ + template <> \ + struct call_##cpp_func<type1> : \ + call_cpp_##c99_func< \ + ::cutl_details_boost::hash_detail::c99_func##_detect::check::cpp \ + > {}; \ + } \ +} + +#define BOOST_HASH_CALL_FLOAT_MACRO(cpp_func, c99_func, type1, type2) \ +namespace cutl_details_boost { \ + namespace hash_detail { \ + \ + template <> \ + struct call_##cpp_func<type1> { \ + typedef type1 float_type; \ + inline type1 operator()(type1 x, type2 y) const { \ + return c99_func(x, y); \ + } \ + }; \ + } \ +} + +#if defined(ldexpf) +BOOST_HASH_CALL_FLOAT_MACRO(ldexp, ldexpf, float, int) +#else +BOOST_HASH_CALL_FLOAT_FUNC(ldexp, ldexpf, float, int) +#endif + +#if defined(ldexpl) +BOOST_HASH_CALL_FLOAT_MACRO(ldexp, ldexpl, long double, int) +#else +BOOST_HASH_CALL_FLOAT_FUNC(ldexp, ldexpl, long double, int) +#endif + +#if defined(frexpf) +BOOST_HASH_CALL_FLOAT_MACRO(frexp, frexpf, float, int*) +#else +BOOST_HASH_CALL_FLOAT_FUNC(frexp, frexpf, float, int*) +#endif + +#if defined(frexpl) +BOOST_HASH_CALL_FLOAT_MACRO(frexp, frexpl, long double, int*) +#else +BOOST_HASH_CALL_FLOAT_FUNC(frexp, frexpl, long double, int*) +#endif + +#undef BOOST_HASH_CALL_FLOAT_MACRO +#undef BOOST_HASH_CALL_FLOAT_FUNC + + +namespace cutl_details_boost +{ + namespace hash_detail + { + template <typename Float1, typename Float2> + struct select_hash_type_impl { + typedef double type; + }; + + template <> + struct select_hash_type_impl<float, float> { + typedef float type; + }; + + template <> + struct select_hash_type_impl<long double, long double> { + typedef long double type; + }; + + + // select_hash_type + // + // If there is support for a particular floating point type, use that + // otherwise use double (there's always support for double). + + template <typename Float> + struct select_hash_type : select_hash_type_impl< + BOOST_DEDUCED_TYPENAME call_ldexp<Float>::float_type, + BOOST_DEDUCED_TYPENAME call_frexp<Float>::float_type + > {}; + } +} + +#endif diff --git a/cutl/details/boost/functional/hash/detail/hash_float.hpp b/cutl/details/boost/functional/hash/detail/hash_float.hpp new file mode 100644 index 0000000..dafec9a --- /dev/null +++ b/cutl/details/boost/functional/hash/detail/hash_float.hpp @@ -0,0 +1,101 @@ + +// Copyright 2005-2009 Daniel James. +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) + +#if !defined(BOOST_FUNCTIONAL_HASH_DETAIL_HASH_FLOAT_HEADER) +#define BOOST_FUNCTIONAL_HASH_DETAIL_HASH_FLOAT_HEADER + +#if defined(_MSC_VER) && (_MSC_VER >= 1020) +# pragma once +#endif + +#include <cutl/details/boost/config.hpp> +#include <cutl/details/boost/functional/hash/detail/float_functions.hpp> +#include <cutl/details/boost/functional/hash/detail/limits.hpp> +#include <cutl/details/boost/integer/static_log2.hpp> +#include <cutl/details/boost/cstdint.hpp> +#include <cutl/details/boost/assert.hpp> + +// Include hash implementation for the current platform. + +// Cygwn +#if defined(__CYGWIN__) +# if defined(__i386__) || defined(_M_IX86) +# include <cutl/details/boost/functional/hash/detail/hash_float_x86.hpp> +# else +# include <cutl/details/boost/functional/hash/detail/hash_float_generic.hpp> +# endif +#else +# include <cutl/details/boost/functional/hash/detail/hash_float_generic.hpp> +#endif + +// Can we use fpclassify? + +// STLport +#if defined(__SGI_STL_PORT) || defined(_STLPORT_VERSION) +#define BOOST_HASH_USE_FPCLASSIFY 0 + +// GNU libstdc++ 3 +#elif defined(__GLIBCPP__) || defined(__GLIBCXX__) +# if (defined(__USE_ISOC99) || defined(_GLIBCXX_USE_C99_MATH)) && \ + !(defined(macintosh) || defined(__APPLE__) || defined(__APPLE_CC__)) +# define BOOST_HASH_USE_FPCLASSIFY 1 +# else +# define BOOST_HASH_USE_FPCLASSIFY 0 +# endif + +// Everything else +#else +# define BOOST_HASH_USE_FPCLASSIFY 0 +#endif + +#if BOOST_HASH_USE_FPCLASSIFY + +#include <cutl/details/boost/config/no_tr1/cmath.hpp> + +namespace cutl_details_boost +{ + namespace hash_detail + { + template <class T> + inline std::size_t float_hash_value(T v) + { + using namespace std; + switch (fpclassify(v)) { + case FP_ZERO: + return 0; + case FP_INFINITE: + return (std::size_t)(v > 0 ? -1 : -2); + case FP_NAN: + return (std::size_t)(-3); + case FP_NORMAL: + case FP_SUBNORMAL: + return float_hash_impl(v); + default: + BOOST_ASSERT(0); + return 0; + } + } + } +} + +#else // !BOOST_HASH_USE_FPCLASSIFY + +namespace cutl_details_boost +{ + namespace hash_detail + { + template <class T> + inline std::size_t float_hash_value(T v) + { + return v == 0 ? 0 : float_hash_impl(v); + } + } +} + +#endif // BOOST_HASH_USE_FPCLASSIFY + +#undef BOOST_HASH_USE_FPCLASSIFY + +#endif diff --git a/cutl/details/boost/functional/hash/detail/hash_float_generic.hpp b/cutl/details/boost/functional/hash/detail/hash_float_generic.hpp new file mode 100644 index 0000000..295b620 --- /dev/null +++ b/cutl/details/boost/functional/hash/detail/hash_float_generic.hpp @@ -0,0 +1,91 @@ + +// Copyright 2005-2009 Daniel James. +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) + +// A general purpose hash function for non-zero floating point values. + +#if !defined(BOOST_FUNCTIONAL_HASH_DETAIL_HASH_FLOAT_GENERIC_HEADER) +#define BOOST_FUNCTIONAL_HASH_DETAIL_HASH_FLOAT_GENERIC_HEADER + +#include <cutl/details/boost/functional/hash/detail/float_functions.hpp> +#include <cutl/details/boost/integer/static_log2.hpp> +#include <cutl/details/boost/functional/hash/detail/limits.hpp> + +#if defined(_MSC_VER) && (_MSC_VER >= 1020) +# pragma once +#endif + +#if defined(BOOST_MSVC) +#pragma warning(push) +#if BOOST_MSVC >= 1400 +#pragma warning(disable:6294) // Ill-defined for-loop: initial condition does + // not satisfy test. Loop body not executed +#endif +#endif + +namespace cutl_details_boost +{ + namespace hash_detail + { + inline void hash_float_combine(std::size_t& seed, std::size_t value) + { + seed ^= value + (seed<<6) + (seed>>2); + } + + template <class T> + inline std::size_t float_hash_impl2(T v) + { + cutl_details_boost::hash_detail::call_frexp<T> frexp; + cutl_details_boost::hash_detail::call_ldexp<T> ldexp; + + int exp = 0; + + v = frexp(v, &exp); + + // A postive value is easier to hash, so combine the + // sign with the exponent and use the absolute value. + if(v < 0) { + v = -v; + exp += limits<T>::max_exponent - + limits<T>::min_exponent; + } + + v = ldexp(v, limits<std::size_t>::digits); + std::size_t seed = static_cast<std::size_t>(v); + v -= static_cast<T>(seed); + + // ceiling(digits(T) * log2(radix(T))/ digits(size_t)) - 1; + std::size_t const length + = (limits<T>::digits * + cutl_details_boost::static_log2<limits<T>::radix>::value + + limits<std::size_t>::digits - 1) + / limits<std::size_t>::digits; + + for(std::size_t i = 0; i != length; ++i) + { + v = ldexp(v, limits<std::size_t>::digits); + std::size_t part = static_cast<std::size_t>(v); + v -= static_cast<T>(part); + hash_float_combine(seed, part); + } + + hash_float_combine(seed, exp); + + return seed; + } + + template <class T> + inline std::size_t float_hash_impl(T v) + { + typedef BOOST_DEDUCED_TYPENAME select_hash_type<T>::type type; + return float_hash_impl2(static_cast<type>(v)); + } + } +} + +#if defined(BOOST_MSVC) +#pragma warning(pop) +#endif + +#endif diff --git a/cutl/details/boost/functional/hash/detail/hash_float_x86.hpp b/cutl/details/boost/functional/hash/detail/hash_float_x86.hpp new file mode 100644 index 0000000..6a70556 --- /dev/null +++ b/cutl/details/boost/functional/hash/detail/hash_float_x86.hpp @@ -0,0 +1,56 @@ + +// Copyright 2005-2009 Daniel James. +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) + +// A non-portable hash function form non-zero floats on x86. +// +// Even if you're on an x86 platform, this might not work if their floating +// point isn't set up as this expects. So this should only be used if it's +// absolutely certain that it will work. + +#if !defined(BOOST_FUNCTIONAL_HASH_DETAIL_HASH_FLOAT_X86_HEADER) +#define BOOST_FUNCTIONAL_HASH_DETAIL_HASH_FLOAT_X86_HEADER + +#include <cutl/details/boost/cstdint.hpp> + +#if defined(_MSC_VER) && (_MSC_VER >= 1020) +# pragma once +#endif + +namespace cutl_details_boost +{ + namespace hash_detail + { + inline void hash_float_combine(std::size_t& seed, std::size_t value) + { + seed ^= value + (seed<<6) + (seed>>2); + } + + inline std::size_t float_hash_impl(float v) + { + cutl_details_boost::uint32_t* ptr = (cutl_details_boost::uint32_t*)&v; + std::size_t seed = *ptr; + return seed; + } + + inline std::size_t float_hash_impl(double v) + { + cutl_details_boost::uint32_t* ptr = (cutl_details_boost::uint32_t*)&v; + std::size_t seed = *ptr++; + hash_float_combine(seed, *ptr); + return seed; + } + + inline std::size_t float_hash_impl(long double v) + { + cutl_details_boost::uint32_t* ptr = (cutl_details_boost::uint32_t*)&v; + std::size_t seed = *ptr++; + hash_float_combine(seed, *ptr++); + hash_float_combine(seed, *(cutl_details_boost::uint16_t*)ptr); + return seed; + } + } +} + +#endif diff --git a/cutl/details/boost/functional/hash/detail/limits.hpp b/cutl/details/boost/functional/hash/detail/limits.hpp new file mode 100644 index 0000000..de9abbe --- /dev/null +++ b/cutl/details/boost/functional/hash/detail/limits.hpp @@ -0,0 +1,61 @@ + +// Copyright 2005-2009 Daniel James. +// Distributed under the Boost Software License, Version 1.0. (See accompanying +// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) +// +// On some platforms std::limits gives incorrect values for long double. +// This tries to work around them. + +#if !defined(BOOST_FUNCTIONAL_HASH_DETAIL_LIMITS_HEADER) +#define BOOST_FUNCTIONAL_HASH_DETAIL_LIMITS_HEADER + +#if defined(_MSC_VER) && (_MSC_VER >= 1020) +# pragma once +#endif + +#include <cutl/details/boost/limits.hpp> + +// On OpenBSD, numeric_limits is not reliable for long doubles, but +// the macros defined in <float.h> are and support long double when STLport +// doesn't. + +#if defined(__OpenBSD__) || defined(_STLP_NO_LONG_DOUBLE) +#include <float.h> +#endif + +namespace cutl_details_boost +{ + namespace hash_detail + { + template <class T> + struct limits : std::numeric_limits<T> {}; + +#if defined(__OpenBSD__) || defined(_STLP_NO_LONG_DOUBLE) + template <> + struct limits<long double> + : std::numeric_limits<long double> + { + static long double epsilon() { + return LDBL_EPSILON; + } + + static long double (max)() { + return LDBL_MAX; + } + + static long double (min)() { + return LDBL_MIN; + } + + BOOST_STATIC_CONSTANT(int, digits = LDBL_MANT_DIG); + BOOST_STATIC_CONSTANT(int, max_exponent = LDBL_MAX_EXP); + BOOST_STATIC_CONSTANT(int, min_exponent = LDBL_MIN_EXP); +#if defined(_STLP_NO_LONG_DOUBLE) + BOOST_STATIC_CONSTANT(int, radix = FLT_RADIX); +#endif + }; +#endif // __OpenBSD__ + } +} + +#endif |