# functional_hash.h

Go to the documentation of this file.

    00001 // TR1 functional -*- C++ -*-
    00002
    00003 // Copyright (C) 2007 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 2, 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 // You should have received a copy of the GNU General Public License along
    00017 // with this library; see the file COPYING.  If not, write to the Free
    00018 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
    00019 // USA.
    00020
    00021 // As a special exception, you may use this file as part of a free software
    00022 // library without restriction.  Specifically, if other files instantiate
    00023 // templates or use macros or inline functions from this file, or you compile
    00024 // this file and link it with other files to produce an executable, this
    00025 // file does not by itself cause the resulting executable to be covered by
    00026 // the GNU General Public License.  This exception does not however
    00027 // invalidate any other reasons why the executable file might be covered by
    00028 // the GNU General Public License.
    00029
    00030 /** @file tr1/functional_hash.h
    00031  *  This is an internal header file, included by other library headers.
    00032  *  You should not attempt to use it directly.
    00033  */
    00034
    00035 #ifndef _TR1_FUNCTIONAL_HASH_H
    00036 #define _TR1_FUNCTIONAL_HASH_H 1
    00037
    00038 #include <string>
    00039 #include <cmath>  // for std::frexp
    00040
    00041 namespace std
    00042 {
    00043 _GLIBCXX_BEGIN_NAMESPACE(tr1)
    00044
    00045   // Definition of default hash function std::tr1::hash<>.  The types for
    00046   // which std::tr1::hash<T> is defined is in clause 6.3.3. of the PDTR.
    00047   template<typename T>
    00048     struct hash;
    00049
    00050 #define _TR1_hashtable_define_trivial_hash(_Tp)         \
    00051   template<>                                            \
    00052     struct hash<_Tp>                                    \
    00053     : public std::unary_function<_Tp, std::size_t>      \
    00054     {                                                   \
    00055       std::size_t                                       \
    00056       operator()(_Tp __val) const                       \
    00057       { return static_cast<std::size_t>(__val); }       \
    00058     }
    00059
    00060   _TR1_hashtable_define_trivial_hash(bool);
    00061   _TR1_hashtable_define_trivial_hash(char);
    00062   _TR1_hashtable_define_trivial_hash(signed char);
    00063   _TR1_hashtable_define_trivial_hash(unsigned char);
    00064   _TR1_hashtable_define_trivial_hash(wchar_t);
    00065   _TR1_hashtable_define_trivial_hash(short);
    00066   _TR1_hashtable_define_trivial_hash(int);
    00067   _TR1_hashtable_define_trivial_hash(long);
    00068   _TR1_hashtable_define_trivial_hash(long long);
    00069   _TR1_hashtable_define_trivial_hash(unsigned short);
    00070   _TR1_hashtable_define_trivial_hash(unsigned int);
    00071   _TR1_hashtable_define_trivial_hash(unsigned long);
    00072   _TR1_hashtable_define_trivial_hash(unsigned long long);
    00073
    00074 #undef _TR1_hashtable_define_trivial_hash
    00075
    00076   template<typename _Tp>
    00077     struct hash<_Tp*>
    00078     : public std::unary_function<_Tp*, std::size_t>
    00079     {
    00080       std::size_t
    00081       operator()(_Tp* __p) const
    00082       { return reinterpret_cast<std::size_t>(__p); }
    00083     };
    00084
    00085   // Fowler / Noll / Vo (FNV) Hash (type FNV-1a)
    00086   // (used by the next specializations of std::tr1::hash<>)
    00087
    00088   // Dummy generic implementation (for sizeof(size_t) != 4, 8).
    00089   template<std::size_t = sizeof(std::size_t)>
    00090     struct _Fnv_hash
    00091     {
    00092       static std::size_t
    00093       hash(const char* __first, std::size_t __length)
    00094       {
    00095     std::size_t __result = 0;
    00096     for (; __length > 0; --__length)
    00097       __result = (__result * 131) + *__first++;
    00098     return __result;
    00099       }
    00100     };
    00101
    00102   template<>
    00103     struct _Fnv_hash<4>
    00104     {
    00105       static std::size_t
    00106       hash(const char* __first, std::size_t __length)
    00107       {
    00108     std::size_t __result = static_cast<std::size_t>(2166136261UL);
    00109     for (; __length > 0; --__length)
    00110       {
    00111         __result ^= static_cast<std::size_t>(*__first++);
    00112         __result *= static_cast<std::size_t>(16777619UL);
    00113       }
    00114     return __result;
    00115       }
    00116     };
    00117
    00118   template<>
    00119     struct _Fnv_hash<8>
    00120     {
    00121       static std::size_t
    00122       hash(const char* __first, std::size_t __length)
    00123       {
    00124     std::size_t __result =
    00125       static_cast<std::size_t>(14695981039346656037ULL);
    00126     for (; __length > 0; --__length)
    00127       {
    00128         __result ^= static_cast<std::size_t>(*__first++);
    00129         __result *= static_cast<std::size_t>(1099511628211ULL);
    00130       }
    00131     return __result;
    00132       }
    00133     };
    00134
    00135   // XXX String and floating point hashes probably shouldn't be inline
    00136   // member functions, since are nontrivial.  Once we have the framework
    00137   // for TR1 .cc files, these should go in one.
    00138   template<>
    00139     struct hash<std::string>
    00140     : public std::unary_function<std::string, std::size_t>
    00141     {
    00142       std::size_t
    00143       operator()(const std::string& __s) const
    00144       { return _Fnv_hash<>::hash(__s.data(), __s.length()); }
    00145     };
    00146
    00147 #ifdef _GLIBCXX_USE_WCHAR_T
    00148   template<>
    00149     struct hash<std::wstring>
    00150     : public std::unary_function<std::wstring, std::size_t>
    00151     {
    00152       std::size_t
    00153       operator()(const std::wstring& __s) const
    00154       {
    00155     return _Fnv_hash<>::hash(reinterpret_cast<const char*>(__s.data()),
    00156                  __s.length() * sizeof(wchar_t));
    00157       }
    00158     };
    00159 #endif
    00160
    00161   template<>
    00162     struct hash<float>
    00163     : public std::unary_function<float, std::size_t>
    00164     {
    00165       std::size_t
    00166       operator()(float __fval) const
    00167       {
    00168     std::size_t __result = 0;
    00169
    00170     // 0 and -0 both hash to zero.
    00171     if (__fval != 0.0f)
    00172       __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__fval),
    00173                        sizeof(__fval));
    00174     return __result;
    00175       }
    00176     };
    00177
    00178   template<>
    00179     struct hash<double>
    00180     : public std::unary_function<double, std::size_t>
    00181     {
    00182       std::size_t
    00183       operator()(double __dval) const
    00184       {
    00185     std::size_t __result = 0;
    00186
    00187     // 0 and -0 both hash to zero.
    00188     if (__dval != 0.0)
    00189       __result = _Fnv_hash<>::hash(reinterpret_cast<const char*>(&__dval),
    00190                        sizeof(__dval));
    00191     return __result;
    00192       }
    00193     };
    00194
    00195   // For long double, careful with random padding bits (e.g., on x86,
    00196   // 10 bytes -> 12 bytes) and resort to frexp.
    00197   template<>
    00198     struct hash<long double>
    00199     : public std::unary_function<long double, std::size_t>
    00200     {
    00201       std::size_t
    00202       operator()(long double __ldval) const
    00203       {
    00204     std::size_t __result = 0;
    00205
    00206     int __exponent;
    00207     __ldval = std::frexp(__ldval, &__exponent);
    00208     __ldval = __ldval < 0.0l ? -(__ldval + 0.5l) : __ldval;
    00209
    00210     const long double __mult =
    00211       std::numeric_limits<std::size_t>::max() + 1.0l;
    00212     __ldval *= __mult;
    00213
    00214     // Try to use all the bits of the mantissa (really necessary only
    00215     // on 32-bit targets, at least for 80-bit floating point formats).
    00216     const std::size_t __hibits = (std::size_t)__ldval;
    00217     __ldval = (__ldval - (long double)__hibits) * __mult;
    00218
    00219     const std::size_t __coeff =
    00220       (std::numeric_limits<std::size_t>::max()
    00221        / std::numeric_limits<long double>::max_exponent);
    00222
    00223     __result = __hibits + (std::size_t)__ldval + __coeff * __exponent;
    00224
    00225     return __result;
    00226       }
    00227     };
    00228
    00229 _GLIBCXX_END_NAMESPACE
    00230 }
    00231
    00232 #endif