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 <bits/c++config.h>
  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
 121   // Dummy generic implementation (for sizeof(size_t) != 4, 8).
 122   template<size_t>
 123     struct _Fnv_hash_base
 124     {
 125       template<typename _Tp>
 126         static size_t
 127         hash(const _Tp* __ptr, size_t __clength, size_t __hash = 0)
 128         {
 129           const char* __cptr = reinterpret_cast<const char*>(__ptr);
 130           for (; __clength; --__clength)
 131             __hash = (__hash * 131) + *__cptr++;
 132           return __hash;
 133         }
 134     };
 135
 136   template<>
 137     struct _Fnv_hash_base<4>
 138     {
 139       template<typename _Tp>
 140         static size_t
 141         hash(const _Tp* __ptr, size_t __clength,
 142              size_t __hash = static_cast<size_t>(2166136261UL))
 143         {
 144           const char* __cptr = reinterpret_cast<const char*>(__ptr);
 145           for (; __clength; --__clength)
 146             {
 147               __hash ^= static_cast<size_t>(*__cptr++);
 148               __hash *= static_cast<size_t>(16777619UL);
 149             }
 150           return __hash;
 151         }
 152     };
 153
 154   template<>
 155     struct _Fnv_hash_base<8>
 156     {
 157       template<typename _Tp>
 158         static size_t
 159         hash(const _Tp* __ptr, size_t __clength,
 160              size_t __hash = static_cast<size_t>(14695981039346656037ULL))
 161         {
 162           const char* __cptr = reinterpret_cast<const char*>(__ptr);
 163           for (; __clength; --__clength)
 164             {
 165               __hash ^= static_cast<size_t>(*__cptr++);
 166               __hash *= static_cast<size_t>(1099511628211ULL);
 167             }
 168           return __hash;
 169         }
 170     };
 171
 172     struct _Fnv_hash
 173     : public _Fnv_hash_base<sizeof(size_t)>
 174     {
 175       using _Fnv_hash_base<sizeof(size_t)>::hash;
 176
 177       template<typename _Tp>
 178         static size_t
 179         hash(const _Tp& __val)
 180         { return hash(&__val, sizeof(__val)); }
 181
 182       template<typename _Tp>
 183         static size_t
 184         __hash_combine(const _Tp& __val, size_t __hash)
 185         { return hash(&__val, sizeof(__val), __hash); }
 186     };
 187
 188   /// Specialization for float.
 189   template<>
 190     inline size_t
 191     hash<float>::operator()(float __val) const
 192     {
 193       // 0 and -0 both hash to zero.
 194       return __val != 0.0f ? std::_Fnv_hash::hash(__val) : 0;
 195     }
 196
 197   /// Specialization for double.
 198   template<>
 199     inline size_t
 200     hash<double>::operator()(double __val) const
 201     {
 202       // 0 and -0 both hash to zero.
 203       return __val != 0.0 ? std::_Fnv_hash::hash(__val) : 0;
 204     }
 205
 206   /// Specialization for long double.
 207   template<>
 208     _GLIBCXX_PURE size_t
 209     hash<long double>::operator()(long double __val) const;
 210
 211   // @} group hashes
 212 }
 213
 214 #endif // _FUNCTIONAL_HASH_H