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

   1 // functional_hash.h header -*- C++ -*-
   2
   3 // Copyright (C) 2007, 2008, 2009, 2010 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 3, 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 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 /** @file bits/functional_hash.h
  26  *  This is an internal header file, included by other library headers.
  27  *  You should not attempt to use it directly.
  28  */
  29
  30 #ifndef _FUNCTIONAL_HASH_H
  31 #define _FUNCTIONAL_HASH_H 1
  32
  33 #pragma GCC system_header
  34
  35 #include <cstddef>
  36 #include <bits/stl_function.h>
  37
  38 namespace std
  39 {
  40   /** @defgroup hashes Hashes
  41    *  @ingroup functors
  42    *
  43    *   Hashing functors taking a variable type and returning a @c std::size_t.
  44    *
  45    *  @{
  46    */
  47
  48   /// Primary class template hash.
  49   template<typename _Tp>
  50     struct hash : public std::unary_function<_Tp, size_t>
  51     {
  52       size_t
  53       operator()(_Tp __val) const;
  54     };
  55
  56   /// Partial specializations for pointer types.
  57   template<typename _Tp>
  58     struct hash<_Tp*> : public std::unary_function<_Tp*, size_t>
  59     {
  60       size_t
  61       operator()(_Tp* __p) const
  62       { return reinterpret_cast<size_t>(__p); }
  63     };
  64
  65   // Explicit specializations for integer types.
  66 #define _Cxx_hashtable_define_trivial_hash(_Tp)         \
  67   template<>                                            \
  68     inline size_t                                       \
  69     hash<_Tp>::operator()(_Tp __val) const              \
  70     { return static_cast<size_t>(__val); }
  71
  72   /// Explicit specialization for bool.
  73   _Cxx_hashtable_define_trivial_hash(bool);
  74
  75   /// Explicit specialization for char.
  76   _Cxx_hashtable_define_trivial_hash(char);
  77
  78   /// Explicit specialization for signed char.
  79   _Cxx_hashtable_define_trivial_hash(signed char);
  80
  81   /// Explicit specialization for unsigned char.
  82   _Cxx_hashtable_define_trivial_hash(unsigned char);
  83
  84   /// Explicit specialization for wchar_t.
  85   _Cxx_hashtable_define_trivial_hash(wchar_t);
  86
  87   /// Explicit specialization for char16_t.
  88   _Cxx_hashtable_define_trivial_hash(char16_t);
  89
  90   /// Explicit specialization for char32_t.
  91   _Cxx_hashtable_define_trivial_hash(char32_t);
  92
  93   /// Explicit specialization for short.
  94   _Cxx_hashtable_define_trivial_hash(short);
  95
  96   /// Explicit specialization for int.
  97   _Cxx_hashtable_define_trivial_hash(int);
  98
  99   /// Explicit specialization for long.
 100   _Cxx_hashtable_define_trivial_hash(long);
 101
 102   /// Explicit specialization for long long.
 103   _Cxx_hashtable_define_trivial_hash(long long);
 104
 105   /// Explicit specialization for unsigned short.
 106   _Cxx_hashtable_define_trivial_hash(unsigned short);
 107
 108   /// Explicit specialization for unsigned int.
 109   _Cxx_hashtable_define_trivial_hash(unsigned int);
 110
 111   /// Explicit specialization for unsigned long.
 112   _Cxx_hashtable_define_trivial_hash(unsigned long);
 113
 114   /// Explicit specialization for unsigned long long.
 115   _Cxx_hashtable_define_trivial_hash(unsigned long long);
 116
 117 #undef _Cxx_hashtable_define_trivial_hash
 118
 119   // Fowler / Noll / Vo (FNV) Hash (type FNV-1a)
 120   // (Used by the next specializations of std::hash.)
 121
 122   template<size_t = sizeof(size_t)>
 123     struct _Fnv_hash;
 124
 125   // Dummy generic implementation (for sizeof(size_t) != 4, 8).
 126   template<size_t>
 127     struct _Fnv_hash
 128     {
 129       static size_t
 130       hash(const char* __first, size_t __length)
 131       {
 132         size_t __result = 0;
 133         for (; __length > 0; --__length)
 134           __result = (__result * 131) + *__first++;
 135         return __result;
 136       }
 137     };
 138
 139   template<>
 140     struct _Fnv_hash<4>
 141     {
 142       static size_t
 143       hash(const char* __first, size_t __length)
 144       {
 145         size_t __result = static_cast<size_t>(2166136261UL);
 146         for (; __length > 0; --__length)
 147           {
 148             __result ^= static_cast<size_t>(*__first++);
 149             __result *= static_cast<size_t>(16777619UL);
 150           }
 151         return __result;
 152       }
 153     };
 154
 155   template<>
 156     struct _Fnv_hash<8>
 157     {
 158       static size_t
 159       hash(const char* __first, size_t __length)
 160       {
 161         size_t __result =
 162           static_cast<size_t>(14695981039346656037ULL);
 163         for (; __length > 0; --__length)
 164           {
 165             __result ^= static_cast<size_t>(*__first++);
 166             __result *= static_cast<size_t>(1099511628211ULL);
 167           }
 168         return __result;
 169       }
 170     };
 171
 172   /// Specialization for float.
 173   template<>
 174     inline size_t
 175     hash<float>::operator()(float __val) const
 176     {
 177       size_t __result = 0;
 178
 179       // 0 and -0 both hash to zero.
 180       if (__val != 0.0f)
 181         __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__val),
 182                                      sizeof(__val));
 183       return __result;
 184     }
 185
 186   /// Specialization for double.
 187   template<>
 188     inline size_t
 189     hash<double>::operator()(double __val) const
 190     {
 191       size_t __result = 0;
 192
 193       // 0 and -0 both hash to zero.
 194       if (__val != 0.0)
 195         __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__val),
 196                                      sizeof(__val));
 197       return __result;
 198     }
 199
 200   /// Specialization for long double.
 201   template<>
 202     size_t
 203     hash<long double>::operator()(long double __val) const;
 204
 205   // @} group hashes
 206 }
 207
 208 #endif // _FUNCTIONAL_HASH_H