libstdc++-v3/include/tr1/functional_hash.h

   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
  41 namespace 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