1169691Skan// TR1 functional -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2007 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the 7169691Skan// terms of the GNU General Public License as published by the 8169691Skan// Free Software Foundation; either version 2, or (at your option) 9169691Skan// any later version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, 12169691Skan// but WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14169691Skan// GNU General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License along 17169691Skan// with this library; see the file COPYING. If not, write to the Free 18169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19169691Skan// USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free software 22169691Skan// library without restriction. Specifically, if other files instantiate 23169691Skan// templates or use macros or inline functions from this file, or you compile 24169691Skan// this file and link it with other files to produce an executable, this 25169691Skan// file does not by itself cause the resulting executable to be covered by 26169691Skan// the GNU General Public License. This exception does not however 27169691Skan// invalidate any other reasons why the executable file might be covered by 28169691Skan// the GNU General Public License. 29169691Skan 30169691Skan/** @file tr1/functional_hash.h 31169691Skan * This is an internal header file, included by other library headers. 32169691Skan * You should not attempt to use it directly. 33169691Skan */ 34169691Skan 35169691Skan#ifndef _TR1_FUNCTIONAL_HASH_H 36169691Skan#define _TR1_FUNCTIONAL_HASH_H 1 37169691Skan 38169691Skan#include <string> 39169691Skan#include <cmath> // for std::frexp 40169691Skan 41169691Skannamespace std 42169691Skan{ 43169691Skan_GLIBCXX_BEGIN_NAMESPACE(tr1) 44169691Skan 45169691Skan // Definition of default hash function std::tr1::hash<>. The types for 46169691Skan // which std::tr1::hash<T> is defined is in clause 6.3.3. of the PDTR. 47169691Skan template<typename T> 48169691Skan struct hash; 49169691Skan 50169691Skan#define _TR1_hashtable_define_trivial_hash(_Tp) \ 51169691Skan template<> \ 52169691Skan struct hash<_Tp> \ 53169691Skan : public std::unary_function<_Tp, std::size_t> \ 54169691Skan { \ 55169691Skan std::size_t \ 56169691Skan operator()(_Tp __val) const \ 57169691Skan { return static_cast<std::size_t>(__val); } \ 58169691Skan } 59169691Skan 60169691Skan _TR1_hashtable_define_trivial_hash(bool); 61169691Skan _TR1_hashtable_define_trivial_hash(char); 62169691Skan _TR1_hashtable_define_trivial_hash(signed char); 63169691Skan _TR1_hashtable_define_trivial_hash(unsigned char); 64169691Skan _TR1_hashtable_define_trivial_hash(wchar_t); 65169691Skan _TR1_hashtable_define_trivial_hash(short); 66169691Skan _TR1_hashtable_define_trivial_hash(int); 67169691Skan _TR1_hashtable_define_trivial_hash(long); 68169691Skan _TR1_hashtable_define_trivial_hash(long long); 69169691Skan _TR1_hashtable_define_trivial_hash(unsigned short); 70169691Skan _TR1_hashtable_define_trivial_hash(unsigned int); 71169691Skan _TR1_hashtable_define_trivial_hash(unsigned long); 72169691Skan _TR1_hashtable_define_trivial_hash(unsigned long long); 73169691Skan 74169691Skan#undef _TR1_hashtable_define_trivial_hash 75169691Skan 76169691Skan template<typename _Tp> 77169691Skan struct hash<_Tp*> 78169691Skan : public std::unary_function<_Tp*, std::size_t> 79169691Skan { 80169691Skan std::size_t 81169691Skan operator()(_Tp* __p) const 82169691Skan { return reinterpret_cast<std::size_t>(__p); } 83169691Skan }; 84169691Skan 85169691Skan // Fowler / Noll / Vo (FNV) Hash (type FNV-1a) 86169691Skan // (used by the next specializations of std::tr1::hash<>) 87169691Skan 88169691Skan // Dummy generic implementation (for sizeof(size_t) != 4, 8). 89169691Skan template<std::size_t = sizeof(std::size_t)> 90169691Skan struct _Fnv_hash 91169691Skan { 92169691Skan static std::size_t 93169691Skan hash(const char* __first, std::size_t __length) 94169691Skan { 95169691Skan std::size_t __result = 0; 96169691Skan for (; __length > 0; --__length) 97169691Skan __result = (__result * 131) + *__first++; 98169691Skan return __result; 99169691Skan } 100169691Skan }; 101169691Skan 102169691Skan template<> 103169691Skan struct _Fnv_hash<4> 104169691Skan { 105169691Skan static std::size_t 106169691Skan hash(const char* __first, std::size_t __length) 107169691Skan { 108169691Skan std::size_t __result = static_cast<std::size_t>(2166136261UL); 109169691Skan for (; __length > 0; --__length) 110169691Skan { 111169691Skan __result ^= static_cast<std::size_t>(*__first++); 112169691Skan __result *= static_cast<std::size_t>(16777619UL); 113169691Skan } 114169691Skan return __result; 115169691Skan } 116169691Skan }; 117169691Skan 118169691Skan template<> 119169691Skan struct _Fnv_hash<8> 120169691Skan { 121169691Skan static std::size_t 122169691Skan hash(const char* __first, std::size_t __length) 123169691Skan { 124169691Skan std::size_t __result = 125169691Skan static_cast<std::size_t>(14695981039346656037ULL); 126169691Skan for (; __length > 0; --__length) 127169691Skan { 128169691Skan __result ^= static_cast<std::size_t>(*__first++); 129169691Skan __result *= static_cast<std::size_t>(1099511628211ULL); 130169691Skan } 131169691Skan return __result; 132169691Skan } 133169691Skan }; 134169691Skan 135169691Skan // XXX String and floating point hashes probably shouldn't be inline 136169691Skan // member functions, since are nontrivial. Once we have the framework 137169691Skan // for TR1 .cc files, these should go in one. 138169691Skan template<> 139169691Skan struct hash<std::string> 140169691Skan : public std::unary_function<std::string, std::size_t> 141169691Skan { 142169691Skan std::size_t 143169691Skan operator()(const std::string& __s) const 144169691Skan { return _Fnv_hash<>::hash(__s.data(), __s.length()); } 145169691Skan }; 146169691Skan 147169691Skan#ifdef _GLIBCXX_USE_WCHAR_T 148169691Skan template<> 149169691Skan struct hash<std::wstring> 150169691Skan : public std::unary_function<std::wstring, std::size_t> 151169691Skan { 152169691Skan std::size_t 153169691Skan operator()(const std::wstring& __s) const 154169691Skan { 155169691Skan return _Fnv_hash<>::hash(reinterpret_cast<const char*>(__s.data()), 156169691Skan __s.length() * sizeof(wchar_t)); 157169691Skan } 158169691Skan }; 159169691Skan#endif 160169691Skan 161169691Skan template<> 162169691Skan struct hash<float> 163169691Skan : public std::unary_function<float, std::size_t> 164169691Skan { 165169691Skan std::size_t 166169691Skan operator()(float __fval) const 167169691Skan { 168169691Skan std::size_t __result = 0; 169169691Skan 170169691Skan // 0 and -0 both hash to zero. 171169691Skan if (__fval != 0.0f) 172169691Skan __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__fval), 173169691Skan sizeof(__fval)); 174169691Skan return __result; 175169691Skan } 176169691Skan }; 177169691Skan 178169691Skan template<> 179169691Skan struct hash<double> 180169691Skan : public std::unary_function<double, std::size_t> 181169691Skan { 182169691Skan std::size_t 183169691Skan operator()(double __dval) const 184169691Skan { 185169691Skan std::size_t __result = 0; 186169691Skan 187169691Skan // 0 and -0 both hash to zero. 188169691Skan if (__dval != 0.0) 189169691Skan __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__dval), 190169691Skan sizeof(__dval)); 191169691Skan return __result; 192169691Skan } 193169691Skan }; 194169691Skan 195169691Skan // For long double, careful with random padding bits (e.g., on x86, 196169691Skan // 10 bytes -> 12 bytes) and resort to frexp. 197169691Skan template<> 198169691Skan struct hash<long double> 199169691Skan : public std::unary_function<long double, std::size_t> 200169691Skan { 201169691Skan std::size_t 202169691Skan operator()(long double __ldval) const 203169691Skan { 204169691Skan std::size_t __result = 0; 205169691Skan 206169691Skan int __exponent; 207169691Skan __ldval = std::frexp(__ldval, &__exponent); 208169691Skan __ldval = __ldval < 0.0l ? -(__ldval + 0.5l) : __ldval; 209169691Skan 210169691Skan const long double __mult = 211169691Skan std::numeric_limits<std::size_t>::max() + 1.0l; 212169691Skan __ldval *= __mult; 213169691Skan 214169691Skan // Try to use all the bits of the mantissa (really necessary only 215169691Skan // on 32-bit targets, at least for 80-bit floating point formats). 216169691Skan const std::size_t __hibits = (std::size_t)__ldval; 217169691Skan __ldval = (__ldval - (long double)__hibits) * __mult; 218169691Skan 219169691Skan const std::size_t __coeff = 220169691Skan (std::numeric_limits<std::size_t>::max() 221169691Skan / std::numeric_limits<long double>::max_exponent); 222169691Skan 223169691Skan __result = __hibits + (std::size_t)__ldval + __coeff * __exponent; 224169691Skan 225169691Skan return __result; 226169691Skan } 227169691Skan }; 228169691Skan 229169691Skan_GLIBCXX_END_NAMESPACE 230169691Skan} 231169691Skan 232169691Skan#endif 233