1// TR1 functional -*- C++ -*-
2
3// Copyright (C) 2007 Free Software Foundation, Inc.
4//
5// This file is part of the GNU ISO C++ Library.  This library is free
6// software; you can redistribute it and/or modify it under the
7// terms of the GNU General Public License as published by the
8// Free Software Foundation; either version 2, or (at your option)
9// any later version.
10
11// This library is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14// GNU General Public License for more details.
15
16// You should have received a copy of the GNU General Public License along
17// with this library; see the file COPYING.  If not, write to the Free
18// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
19// USA.
20
21// As a special exception, you may use this file as part of a free software
22// library without restriction.  Specifically, if other files instantiate
23// templates or use macros or inline functions from this file, or you compile
24// this file and link it with other files to produce an executable, this
25// file does not by itself cause the resulting executable to be covered by
26// the GNU General Public License.  This exception does not however
27// invalidate any other reasons why the executable file might be covered by
28// the GNU General Public License.
29
30/** @file tr1/functional_hash.h
31 *  This is an internal header file, included by other library headers.
32 *  You should not attempt to use it directly.
33 */
34
35#ifndef _TR1_FUNCTIONAL_HASH_H
36#define _TR1_FUNCTIONAL_HASH_H 1
37
38#include <string>
39#include <cmath>  // for std::frexp
40
41namespace std
42{
43_GLIBCXX_BEGIN_NAMESPACE(tr1)
44
45  // Definition of default hash function std::tr1::hash<>.  The types for
46  // which std::tr1::hash<T> is defined is in clause 6.3.3. of the PDTR.
47  template<typename T>
48    struct hash;
49
50#define _TR1_hashtable_define_trivial_hash(_Tp)         \
51  template<>                                            \
52    struct hash<_Tp>                                    \
53    : public std::unary_function<_Tp, std::size_t>      \
54    {                                                   \
55      std::size_t                                       \
56      operator()(_Tp __val) const                       \
57      { return static_cast<std::size_t>(__val); }       \
58    }
59
60  _TR1_hashtable_define_trivial_hash(bool);
61  _TR1_hashtable_define_trivial_hash(char);
62  _TR1_hashtable_define_trivial_hash(signed char);
63  _TR1_hashtable_define_trivial_hash(unsigned char);
64  _TR1_hashtable_define_trivial_hash(wchar_t);
65  _TR1_hashtable_define_trivial_hash(short);
66  _TR1_hashtable_define_trivial_hash(int);
67  _TR1_hashtable_define_trivial_hash(long);
68  _TR1_hashtable_define_trivial_hash(long long);
69  _TR1_hashtable_define_trivial_hash(unsigned short);
70  _TR1_hashtable_define_trivial_hash(unsigned int);
71  _TR1_hashtable_define_trivial_hash(unsigned long);
72  _TR1_hashtable_define_trivial_hash(unsigned long long);
73
74#undef _TR1_hashtable_define_trivial_hash
75
76  template<typename _Tp>
77    struct hash<_Tp*>
78    : public std::unary_function<_Tp*, std::size_t>
79    {
80      std::size_t
81      operator()(_Tp* __p) const
82      { return reinterpret_cast<std::size_t>(__p); }
83    };
84
85  // Fowler / Noll / Vo (FNV) Hash (type FNV-1a)
86  // (used by the next specializations of std::tr1::hash<>)
87
88  // Dummy generic implementation (for sizeof(size_t) != 4, 8).
89  template<std::size_t = sizeof(std::size_t)>
90    struct _Fnv_hash
91    {
92      static std::size_t
93      hash(const char* __first, std::size_t __length)
94      {
95	std::size_t __result = 0;
96	for (; __length > 0; --__length)
97	  __result = (__result * 131) + *__first++;
98	return __result;
99      }
100    };
101
102  template<>
103    struct _Fnv_hash<4>
104    {
105      static std::size_t
106      hash(const char* __first, std::size_t __length)
107      {
108	std::size_t __result = static_cast<std::size_t>(2166136261UL);
109	for (; __length > 0; --__length)
110	  {
111	    __result ^= static_cast<std::size_t>(*__first++);
112	    __result *= static_cast<std::size_t>(16777619UL);
113	  }
114	return __result;
115      }
116    };
117
118  template<>
119    struct _Fnv_hash<8>
120    {
121      static std::size_t
122      hash(const char* __first, std::size_t __length)
123      {
124	std::size_t __result =
125	  static_cast<std::size_t>(14695981039346656037ULL);
126	for (; __length > 0; --__length)
127	  {
128	    __result ^= static_cast<std::size_t>(*__first++);
129	    __result *= static_cast<std::size_t>(1099511628211ULL);
130	  }
131	return __result;
132      }
133    };
134
135  // XXX String and floating point hashes probably shouldn't be inline
136  // member functions, since are nontrivial.  Once we have the framework
137  // for TR1 .cc files, these should go in one.
138  template<>
139    struct hash<std::string>
140    : public std::unary_function<std::string, std::size_t>
141    {
142      std::size_t
143      operator()(const std::string& __s) const
144      { return _Fnv_hash<>::hash(__s.data(), __s.length()); }
145    };
146
147#ifdef _GLIBCXX_USE_WCHAR_T
148  template<>
149    struct hash<std::wstring>
150    : public std::unary_function<std::wstring, std::size_t>
151    {
152      std::size_t
153      operator()(const std::wstring& __s) const
154      {
155	return _Fnv_hash<>::hash(reinterpret_cast<const char*>(__s.data()),
156				 __s.length() * sizeof(wchar_t));
157      }
158    };
159#endif
160
161  template<>
162    struct hash<float>
163    : public std::unary_function<float, std::size_t>
164    {
165      std::size_t
166      operator()(float __fval) const
167      {
168	std::size_t __result = 0;
169
170	// 0 and -0 both hash to zero.
171	if (__fval != 0.0f)
172	  __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__fval),
173				       sizeof(__fval));
174	return __result;
175      }
176    };
177
178  template<>
179    struct hash<double>
180    : public std::unary_function<double, std::size_t>
181    {
182      std::size_t
183      operator()(double __dval) const
184      {
185	std::size_t __result = 0;
186
187	// 0 and -0 both hash to zero.
188	if (__dval != 0.0)
189	  __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__dval),
190				       sizeof(__dval));
191	return __result;
192      }
193    };
194
195  // For long double, careful with random padding bits (e.g., on x86,
196  // 10 bytes -> 12 bytes) and resort to frexp.
197  template<>
198    struct hash<long double>
199    : public std::unary_function<long double, std::size_t>
200    {
201      std::size_t
202      operator()(long double __ldval) const
203      {
204	std::size_t __result = 0;
205
206	int __exponent;
207	__ldval = std::frexp(__ldval, &__exponent);
208	__ldval = __ldval < 0.0l ? -(__ldval + 0.5l) : __ldval;
209
210	const long double __mult =
211	  std::numeric_limits<std::size_t>::max() + 1.0l;
212	__ldval *= __mult;
213
214	// Try to use all the bits of the mantissa (really necessary only
215	// on 32-bit targets, at least for 80-bit floating point formats).
216	const std::size_t __hibits = (std::size_t)__ldval;
217	__ldval = (__ldval - (long double)__hibits) * __mult;
218
219	const std::size_t __coeff =
220	  (std::numeric_limits<std::size_t>::max()
221	   / std::numeric_limits<long double>::max_exponent);
222
223	__result = __hibits + (std::size_t)__ldval + __coeff * __exponent;
224
225	return __result;
226      }
227    };
228
229_GLIBCXX_END_NAMESPACE
230}
231
232#endif
233