functional_hash.h

Go to the documentation of this file.
00001 // functional_hash.h header -*- C++ -*-
00002 
00003 // Copyright (C) 2007, 2008, 2009, 2010 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the
00007 // terms of the GNU General Public License as published by the
00008 // Free Software Foundation; either version 3, or (at your option)
00009 // any later version.
00010 
00011 // This library is distributed in the hope that it will be useful,
00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00014 // GNU General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 /** @file bits/functional_hash.h
00026  *  This is an internal header file, included by other library headers.
00027  *  You should not attempt to use it directly.
00028  */
00029 
00030 #ifndef _FUNCTIONAL_HASH_H
00031 #define _FUNCTIONAL_HASH_H 1
00032 
00033 #pragma GCC system_header
00034 
00035 #include <cstddef>
00036 #include <bits/stl_function.h>
00037 
00038 namespace std
00039 {
00040   /** @defgroup hashes Hashes
00041    *  @ingroup functors
00042    *
00043    *   Hashing functors taking a variable type and returning a @c std::size_t.
00044    *
00045    *  @{
00046    */
00047 
00048   /// Primary class template hash.
00049   template<typename _Tp>
00050     struct hash : public std::unary_function<_Tp, size_t>
00051     {
00052       size_t
00053       operator()(_Tp __val) const;
00054     };
00055 
00056   /// Partial specializations for pointer types.
00057   template<typename _Tp>
00058     struct hash<_Tp*> : public std::unary_function<_Tp*, size_t>
00059     {
00060       size_t
00061       operator()(_Tp* __p) const
00062       { return reinterpret_cast<size_t>(__p); }
00063     };
00064 
00065   // Explicit specializations for integer types.
00066 #define _Cxx_hashtable_define_trivial_hash(_Tp)     \
00067   template<>                        \
00068     inline size_t                   \
00069     hash<_Tp>::operator()(_Tp __val) const      \
00070     { return static_cast<size_t>(__val); }
00071 
00072   /// Explicit specialization for bool.
00073   _Cxx_hashtable_define_trivial_hash(bool);
00074 
00075   /// Explicit specialization for char.
00076   _Cxx_hashtable_define_trivial_hash(char);
00077 
00078   /// Explicit specialization for signed char.
00079   _Cxx_hashtable_define_trivial_hash(signed char);
00080 
00081   /// Explicit specialization for unsigned char.
00082   _Cxx_hashtable_define_trivial_hash(unsigned char);
00083 
00084   /// Explicit specialization for wchar_t.
00085   _Cxx_hashtable_define_trivial_hash(wchar_t);
00086 
00087   /// Explicit specialization for char16_t.
00088   _Cxx_hashtable_define_trivial_hash(char16_t);
00089 
00090   /// Explicit specialization for char32_t.
00091   _Cxx_hashtable_define_trivial_hash(char32_t);
00092 
00093   /// Explicit specialization for short.
00094   _Cxx_hashtable_define_trivial_hash(short);
00095 
00096   /// Explicit specialization for int.
00097   _Cxx_hashtable_define_trivial_hash(int);
00098 
00099   /// Explicit specialization for long.
00100   _Cxx_hashtable_define_trivial_hash(long);
00101 
00102   /// Explicit specialization for long long.
00103   _Cxx_hashtable_define_trivial_hash(long long);
00104 
00105   /// Explicit specialization for unsigned short.
00106   _Cxx_hashtable_define_trivial_hash(unsigned short);
00107 
00108   /// Explicit specialization for unsigned int.
00109   _Cxx_hashtable_define_trivial_hash(unsigned int);
00110 
00111   /// Explicit specialization for unsigned long.
00112   _Cxx_hashtable_define_trivial_hash(unsigned long);
00113 
00114   /// Explicit specialization for unsigned long long.
00115   _Cxx_hashtable_define_trivial_hash(unsigned long long);
00116 
00117 #undef _Cxx_hashtable_define_trivial_hash
00118 
00119   // Fowler / Noll / Vo (FNV) Hash (type FNV-1a)
00120 
00121   // Dummy generic implementation (for sizeof(size_t) != 4, 8).
00122   template<size_t>
00123     struct _Fnv_hash_base
00124     {
00125       template<typename _Tp>
00126         static size_t
00127         hash(const _Tp* __ptr, size_t __clength, size_t __hash = 0)
00128         {
00129       const char* __cptr = reinterpret_cast<const char*>(__ptr);
00130       for (; __clength; --__clength)
00131         __hash = (__hash * 131) + *__cptr++;
00132       return __hash;
00133     }
00134     };
00135 
00136   template<>
00137     struct _Fnv_hash_base<4>
00138     {
00139       template<typename _Tp>
00140         static size_t
00141         hash(const _Tp* __ptr, size_t __clength,
00142          size_t __hash = static_cast<size_t>(2166136261UL))
00143         {
00144       const char* __cptr = reinterpret_cast<const char*>(__ptr);
00145       for (; __clength; --__clength)
00146         {
00147           __hash ^= static_cast<size_t>(*__cptr++);
00148           __hash *= static_cast<size_t>(16777619UL);
00149         }
00150       return __hash;
00151     }
00152     };
00153   
00154   template<>
00155     struct _Fnv_hash_base<8>
00156     {
00157       template<typename _Tp>
00158         static size_t
00159         hash(const _Tp* __ptr, size_t __clength,
00160          size_t __hash = static_cast<size_t>(14695981039346656037ULL))
00161         {
00162       const char* __cptr = reinterpret_cast<const char*>(__ptr);
00163       for (; __clength; --__clength)
00164         {
00165           __hash ^= static_cast<size_t>(*__cptr++);
00166           __hash *= static_cast<size_t>(1099511628211ULL);
00167         }
00168       return __hash;
00169     }
00170     };
00171 
00172     struct _Fnv_hash
00173     : public _Fnv_hash_base<sizeof(size_t)>
00174     {
00175       using _Fnv_hash_base<sizeof(size_t)>::hash;
00176 
00177       template<typename _Tp>
00178         static size_t
00179         hash(const _Tp& __val)
00180         { return hash(&__val, sizeof(__val)); }
00181 
00182       template<typename _Tp>
00183         static size_t
00184         __hash_combine(const _Tp& __val, size_t __hash)
00185         { return hash(&__val, sizeof(__val), __hash); }
00186     };
00187 
00188   /// Specialization for float.
00189   template<>
00190     inline size_t
00191     hash<float>::operator()(float __val) const
00192     {
00193       // 0 and -0 both hash to zero.
00194       return __val != 0.0f ? std::_Fnv_hash::hash(__val) : 0;
00195     }
00196 
00197   /// Specialization for double.
00198   template<>
00199     inline size_t
00200     hash<double>::operator()(double __val) const
00201     {
00202       // 0 and -0 both hash to zero.
00203       return __val != 0.0 ? std::_Fnv_hash::hash(__val) : 0;
00204     }
00205 
00206   /// Specialization for long double.
00207   template<>
00208     _GLIBCXX_PURE size_t
00209     hash<long double>::operator()(long double __val) const;
00210 
00211   // @} group hashes
00212 }
00213 
00214 #endif // _FUNCTIONAL_HASH_H