1251881Speter// TR1 functional -*- C++ -*- 2251881Speter 3251881Speter// Copyright (C) 2007 Free Software Foundation, Inc. 4251881Speter// 5251881Speter// This file is part of the GNU ISO C++ Library. This library is free 6251881Speter// software; you can redistribute it and/or modify it under the 7251881Speter// terms of the GNU General Public License as published by the 8251881Speter// Free Software Foundation; either version 2, or (at your option) 9251881Speter// any later version. 10251881Speter 11251881Speter// This library is distributed in the hope that it will be useful, 12251881Speter// but WITHOUT ANY WARRANTY; without even the implied warranty of 13251881Speter// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14251881Speter// GNU General Public License for more details. 15251881Speter 16251881Speter// You should have received a copy of the GNU General Public License along 17251881Speter// with this library; see the file COPYING. If not, write to the Free 18251881Speter// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19251881Speter// USA. 20251881Speter 21251881Speter// As a special exception, you may use this file as part of a free software 22251881Speter// library without restriction. Specifically, if other files instantiate 23251881Speter// templates or use macros or inline functions from this file, or you compile 24251881Speter// this file and link it with other files to produce an executable, this 25251881Speter// file does not by itself cause the resulting executable to be covered by 26251881Speter// the GNU General Public License. This exception does not however 27251881Speter// invalidate any other reasons why the executable file might be covered by 28251881Speter// the GNU General Public License. 29251881Speter 30251881Speter/** @file tr1/functional_hash.h 31251881Speter * This is an internal header file, included by other library headers. 32251881Speter * You should not attempt to use it directly. 33251881Speter */ 34251881Speter 35251881Speter#ifndef _TR1_FUNCTIONAL_HASH_H 36251881Speter#define _TR1_FUNCTIONAL_HASH_H 1 37251881Speter 38251881Speter#include <string> 39251881Speter#include <cmath> // for std::frexp 40251881Speter 41251881Speternamespace std 42251881Speter{ 43251881Speter_GLIBCXX_BEGIN_NAMESPACE(tr1) 44251881Speter 45251881Speter // Definition of default hash function std::tr1::hash<>. The types for 46251881Speter // which std::tr1::hash<T> is defined is in clause 6.3.3. of the PDTR. 47251881Speter template<typename T> 48251881Speter struct hash; 49251881Speter 50251881Speter#define _TR1_hashtable_define_trivial_hash(_Tp) \ 51251881Speter template<> \ 52251881Speter struct hash<_Tp> \ 53251881Speter : public std::unary_function<_Tp, std::size_t> \ 54251881Speter { \ 55251881Speter std::size_t \ 56251881Speter operator()(_Tp __val) const \ 57251881Speter { return static_cast<std::size_t>(__val); } \ 58251881Speter } 59251881Speter 60251881Speter _TR1_hashtable_define_trivial_hash(bool); 61251881Speter _TR1_hashtable_define_trivial_hash(char); 62251881Speter _TR1_hashtable_define_trivial_hash(signed char); 63251881Speter _TR1_hashtable_define_trivial_hash(unsigned char); 64251881Speter _TR1_hashtable_define_trivial_hash(wchar_t); 65251881Speter _TR1_hashtable_define_trivial_hash(short); 66251881Speter _TR1_hashtable_define_trivial_hash(int); 67251881Speter _TR1_hashtable_define_trivial_hash(long); 68251881Speter _TR1_hashtable_define_trivial_hash(long long); 69251881Speter _TR1_hashtable_define_trivial_hash(unsigned short); 70251881Speter _TR1_hashtable_define_trivial_hash(unsigned int); 71251881Speter _TR1_hashtable_define_trivial_hash(unsigned long); 72251881Speter _TR1_hashtable_define_trivial_hash(unsigned long long); 73251881Speter 74251881Speter#undef _TR1_hashtable_define_trivial_hash 75251881Speter 76251881Speter template<typename _Tp> 77251881Speter struct hash<_Tp*> 78251881Speter : public std::unary_function<_Tp*, std::size_t> 79251881Speter { 80251881Speter std::size_t 81251881Speter operator()(_Tp* __p) const 82251881Speter { return reinterpret_cast<std::size_t>(__p); } 83251881Speter }; 84251881Speter 85251881Speter // Fowler / Noll / Vo (FNV) Hash (type FNV-1a) 86251881Speter // (used by the next specializations of std::tr1::hash<>) 87251881Speter 88251881Speter // Dummy generic implementation (for sizeof(size_t) != 4, 8). 89251881Speter template<std::size_t = sizeof(std::size_t)> 90251881Speter struct _Fnv_hash 91251881Speter { 92251881Speter static std::size_t 93251881Speter hash(const char* __first, std::size_t __length) 94251881Speter { 95251881Speter std::size_t __result = 0; 96251881Speter for (; __length > 0; --__length) 97251881Speter __result = (__result * 131) + *__first++; 98251881Speter return __result; 99251881Speter } 100251881Speter }; 101251881Speter 102251881Speter template<> 103251881Speter struct _Fnv_hash<4> 104251881Speter { 105251881Speter static std::size_t 106251881Speter hash(const char* __first, std::size_t __length) 107251881Speter { 108251881Speter std::size_t __result = static_cast<std::size_t>(2166136261UL); 109251881Speter for (; __length > 0; --__length) 110251881Speter { 111251881Speter __result ^= static_cast<std::size_t>(*__first++); 112251881Speter __result *= static_cast<std::size_t>(16777619UL); 113251881Speter } 114251881Speter return __result; 115251881Speter } 116251881Speter }; 117251881Speter 118251881Speter template<> 119251881Speter struct _Fnv_hash<8> 120251881Speter { 121251881Speter static std::size_t 122251881Speter hash(const char* __first, std::size_t __length) 123251881Speter { 124251881Speter std::size_t __result = 125251881Speter static_cast<std::size_t>(14695981039346656037ULL); 126251881Speter for (; __length > 0; --__length) 127251881Speter { 128251881Speter __result ^= static_cast<std::size_t>(*__first++); 129251881Speter __result *= static_cast<std::size_t>(1099511628211ULL); 130251881Speter } 131251881Speter return __result; 132251881Speter } 133251881Speter }; 134251881Speter 135251881Speter // XXX String and floating point hashes probably shouldn't be inline 136251881Speter // member functions, since are nontrivial. Once we have the framework 137251881Speter // for TR1 .cc files, these should go in one. 138251881Speter template<> 139251881Speter struct hash<std::string> 140251881Speter : public std::unary_function<std::string, std::size_t> 141251881Speter { 142251881Speter std::size_t 143251881Speter operator()(const std::string& __s) const 144251881Speter { return _Fnv_hash<>::hash(__s.data(), __s.length()); } 145251881Speter }; 146251881Speter 147251881Speter#ifdef _GLIBCXX_USE_WCHAR_T 148251881Speter template<> 149251881Speter struct hash<std::wstring> 150251881Speter : public std::unary_function<std::wstring, std::size_t> 151251881Speter { 152251881Speter std::size_t 153251881Speter operator()(const std::wstring& __s) const 154251881Speter { 155251881Speter return _Fnv_hash<>::hash(reinterpret_cast<const char*>(__s.data()), 156251881Speter __s.length() * sizeof(wchar_t)); 157251881Speter } 158251881Speter }; 159251881Speter#endif 160251881Speter 161251881Speter template<> 162251881Speter struct hash<float> 163251881Speter : public std::unary_function<float, std::size_t> 164251881Speter { 165251881Speter std::size_t 166251881Speter operator()(float __fval) const 167251881Speter { 168251881Speter std::size_t __result = 0; 169251881Speter 170251881Speter // 0 and -0 both hash to zero. 171251881Speter if (__fval != 0.0f) 172251881Speter __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__fval), 173251881Speter sizeof(__fval)); 174251881Speter return __result; 175251881Speter } 176251881Speter }; 177251881Speter 178251881Speter template<> 179251881Speter struct hash<double> 180251881Speter : public std::unary_function<double, std::size_t> 181251881Speter { 182251881Speter std::size_t 183251881Speter operator()(double __dval) const 184251881Speter { 185251881Speter std::size_t __result = 0; 186251881Speter 187251881Speter // 0 and -0 both hash to zero. 188251881Speter if (__dval != 0.0) 189251881Speter __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__dval), 190251881Speter sizeof(__dval)); 191251881Speter return __result; 192251881Speter } 193251881Speter }; 194251881Speter 195251881Speter // For long double, careful with random padding bits (e.g., on x86, 196251881Speter // 10 bytes -> 12 bytes) and resort to frexp. 197251881Speter template<> 198251881Speter struct hash<long double> 199251881Speter : public std::unary_function<long double, std::size_t> 200251881Speter { 201251881Speter std::size_t 202251881Speter operator()(long double __ldval) const 203251881Speter { 204251881Speter std::size_t __result = 0; 205251881Speter 206251881Speter int __exponent; 207251881Speter __ldval = std::frexp(__ldval, &__exponent); 208251881Speter __ldval = __ldval < 0.0l ? -(__ldval + 0.5l) : __ldval; 209251881Speter 210251881Speter const long double __mult = 211251881Speter std::numeric_limits<std::size_t>::max() + 1.0l; 212251881Speter __ldval *= __mult; 213251881Speter 214251881Speter // Try to use all the bits of the mantissa (really necessary only 215251881Speter // on 32-bit targets, at least for 80-bit floating point formats). 216251881Speter const std::size_t __hibits = (std::size_t)__ldval; 217251881Speter __ldval = (__ldval - (long double)__hibits) * __mult; 218251881Speter 219251881Speter const std::size_t __coeff = 220251881Speter (std::numeric_limits<std::size_t>::max() 221251881Speter / std::numeric_limits<long double>::max_exponent); 222251881Speter 223251881Speter __result = __hibits + (std::size_t)__ldval + __coeff * __exponent; 224251881Speter 225251881Speter return __result; 226251881Speter } 227251881Speter }; 228251881Speter 229251881Speter_GLIBCXX_END_NAMESPACE 230251881Speter} 231251881Speter 232251881Speter#endif 233251881Speter