diff options
Diffstat (limited to 'libstdc++/include/tr1/functional_hash.h')
| -rw-r--r-- | libstdc++/include/tr1/functional_hash.h | 232 |
1 files changed, 232 insertions, 0 deletions
diff --git a/libstdc++/include/tr1/functional_hash.h b/libstdc++/include/tr1/functional_hash.h new file mode 100644 index 0000000..3e592b4 --- /dev/null +++ b/libstdc++/include/tr1/functional_hash.h @@ -0,0 +1,232 @@ +// TR1 functional -*- C++ -*- + +// Copyright (C) 2007 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the +// terms of the GNU General Public License as published by the +// Free Software Foundation; either version 2, or (at your option) +// any later version. + +// This library is distributed in the hope that it will be useful, +// but WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +// GNU General Public License for more details. + +// You should have received a copy of the GNU General Public License along +// with this library; see the file COPYING. If not, write to the Free +// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, +// USA. + +// As a special exception, you may use this file as part of a free software +// library without restriction. Specifically, if other files instantiate +// templates or use macros or inline functions from this file, or you compile +// this file and link it with other files to produce an executable, this +// file does not by itself cause the resulting executable to be covered by +// the GNU General Public License. This exception does not however +// invalidate any other reasons why the executable file might be covered by +// the GNU General Public License. + +/** @file tr1/functional_hash.h + * This is an internal header file, included by other library headers. + * You should not attempt to use it directly. + */ + +#ifndef _TR1_FUNCTIONAL_HASH_H +#define _TR1_FUNCTIONAL_HASH_H 1 + +#include <string> +#include <cmath> // for std::frexp + +namespace std +{ +_GLIBCXX_BEGIN_NAMESPACE(tr1) + + // Definition of default hash function std::tr1::hash<>. The types for + // which std::tr1::hash<T> is defined is in clause 6.3.3. of the PDTR. + template<typename T> + struct hash; + +#define _TR1_hashtable_define_trivial_hash(_Tp) \ + template<> \ + struct hash<_Tp> \ + : public std::unary_function<_Tp, std::size_t> \ + { \ + std::size_t \ + operator()(_Tp __val) const \ + { return static_cast<std::size_t>(__val); } \ + } + + _TR1_hashtable_define_trivial_hash(bool); + _TR1_hashtable_define_trivial_hash(char); + _TR1_hashtable_define_trivial_hash(signed char); + _TR1_hashtable_define_trivial_hash(unsigned char); + _TR1_hashtable_define_trivial_hash(wchar_t); + _TR1_hashtable_define_trivial_hash(short); + _TR1_hashtable_define_trivial_hash(int); + _TR1_hashtable_define_trivial_hash(long); + _TR1_hashtable_define_trivial_hash(long long); + _TR1_hashtable_define_trivial_hash(unsigned short); + _TR1_hashtable_define_trivial_hash(unsigned int); + _TR1_hashtable_define_trivial_hash(unsigned long); + _TR1_hashtable_define_trivial_hash(unsigned long long); + +#undef _TR1_hashtable_define_trivial_hash + + template<typename _Tp> + struct hash<_Tp*> + : public std::unary_function<_Tp*, std::size_t> + { + std::size_t + operator()(_Tp* __p) const + { return reinterpret_cast<std::size_t>(__p); } + }; + + // Fowler / Noll / Vo (FNV) Hash (type FNV-1a) + // (used by the next specializations of std::tr1::hash<>) + + // Dummy generic implementation (for sizeof(size_t) != 4, 8). + template<std::size_t = sizeof(std::size_t)> + struct _Fnv_hash + { + static std::size_t + hash(const char* __first, std::size_t __length) + { + std::size_t __result = 0; + for (; __length > 0; --__length) + __result = (__result * 131) + *__first++; + return __result; + } + }; + + template<> + struct _Fnv_hash<4> + { + static std::size_t + hash(const char* __first, std::size_t __length) + { + std::size_t __result = static_cast<std::size_t>(2166136261UL); + for (; __length > 0; --__length) + { + __result ^= static_cast<std::size_t>(*__first++); + __result *= static_cast<std::size_t>(16777619UL); + } + return __result; + } + }; + + template<> + struct _Fnv_hash<8> + { + static std::size_t + hash(const char* __first, std::size_t __length) + { + std::size_t __result = + static_cast<std::size_t>(14695981039346656037ULL); + for (; __length > 0; --__length) + { + __result ^= static_cast<std::size_t>(*__first++); + __result *= static_cast<std::size_t>(1099511628211ULL); + } + return __result; + } + }; + + // XXX String and floating point hashes probably shouldn't be inline + // member functions, since are nontrivial. Once we have the framework + // for TR1 .cc files, these should go in one. + template<> + struct hash<std::string> + : public std::unary_function<std::string, std::size_t> + { + std::size_t + operator()(const std::string& __s) const + { return _Fnv_hash<>::hash(__s.data(), __s.length()); } + }; + +#ifdef _GLIBCXX_USE_WCHAR_T + template<> + struct hash<std::wstring> + : public std::unary_function<std::wstring, std::size_t> + { + std::size_t + operator()(const std::wstring& __s) const + { + return _Fnv_hash<>::hash(reinterpret_cast<const char*>(__s.data()), + __s.length() * sizeof(wchar_t)); + } + }; +#endif + + template<> + struct hash<float> + : public std::unary_function<float, std::size_t> + { + std::size_t + operator()(float __fval) const + { + std::size_t __result = 0; + + // 0 and -0 both hash to zero. + if (__fval != 0.0f) + __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__fval), + sizeof(__fval)); + return __result; + } + }; + + template<> + struct hash<double> + : public std::unary_function<double, std::size_t> + { + std::size_t + operator()(double __dval) const + { + std::size_t __result = 0; + + // 0 and -0 both hash to zero. + if (__dval != 0.0) + __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__dval), + sizeof(__dval)); + return __result; + } + }; + + // For long double, careful with random padding bits (e.g., on x86, + // 10 bytes -> 12 bytes) and resort to frexp. + template<> + struct hash<long double> + : public std::unary_function<long double, std::size_t> + { + std::size_t + operator()(long double __ldval) const + { + std::size_t __result = 0; + + int __exponent; + __ldval = std::frexp(__ldval, &__exponent); + __ldval = __ldval < 0.0l ? -(__ldval + 0.5l) : __ldval; + + const long double __mult = + std::numeric_limits<std::size_t>::max() + 1.0l; + __ldval *= __mult; + + // Try to use all the bits of the mantissa (really necessary only + // on 32-bit targets, at least for 80-bit floating point formats). + const std::size_t __hibits = (std::size_t)__ldval; + __ldval = (__ldval - (long double)__hibits) * __mult; + + const std::size_t __coeff = + (std::numeric_limits<std::size_t>::max() + / std::numeric_limits<long double>::max_exponent); + + __result = __hibits + (std::size_t)__ldval + __coeff * __exponent; + + return __result; + } + }; + +_GLIBCXX_END_NAMESPACE +} + +#endif |
