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

Generated on Thu Nov 1 13:11:30 2007 for libstdc++ by  doxygen 1.5.1