Line data    Source code

       1             : // functional_hash.h header -*- C++ -*-
       2             : 
       3             : // Copyright (C) 2007-2018 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             :  *  Do not attempt to use it directly. @headername{functional}
      28             :  */
      29             : 
      30             : #ifndef _FUNCTIONAL_HASH_H
      31             : #define _FUNCTIONAL_HASH_H 1
      32             : 
      33             : #pragma GCC system_header
      34             : 
      35             : #include <bits/hash_bytes.h>
      36             : 
      37             : namespace std _GLIBCXX_VISIBILITY(default)
      38             : {
      39             : _GLIBCXX_BEGIN_NAMESPACE_VERSION
      40             : 
      41             :   /** @defgroup hashes Hashes
      42             :    *  @ingroup functors
      43             :    *
      44             :    *   Hashing functors taking a variable type and returning a @c std::size_t.
      45             :    *
      46             :    *  @{
      47             :    */
      48             : 
      49             :   template<typename _Result, typename _Arg>
      50             :     struct __hash_base
      51             :     {
      52             :       typedef _Result     result_type _GLIBCXX17_DEPRECATED;
      53             :       typedef _Arg      argument_type _GLIBCXX17_DEPRECATED;
      54             :     };
      55             : 
      56             :   /// Primary class template hash.
      57             :   template<typename _Tp>
      58             :     struct hash;
      59             : 
      60             :   template<typename _Tp, typename = void>
      61             :     struct __poison_hash
      62             :     {
      63             :       static constexpr bool __enable_hash_call = false;
      64             :     private:
      65             :       // Private rather than deleted to be non-trivially-copyable.
      66             :       __poison_hash(__poison_hash&&);
      67             :       ~__poison_hash();
      68             :     };
      69             : 
      70             :   template<typename _Tp>
      71             :     struct __poison_hash<_Tp, __void_t<decltype(hash<_Tp>()(declval<_Tp>()))>>
      72             :     {
      73             :       static constexpr bool __enable_hash_call = true;
      74             :     };
      75             : 
      76             :   // Helper struct for SFINAE-poisoning non-enum types.
      77             :   template<typename _Tp, bool = is_enum<_Tp>::value>
      78             :     struct __hash_enum
      79             :     {
      80             :     private:
      81             :       // Private rather than deleted to be non-trivially-copyable.
      82             :       __hash_enum(__hash_enum&&);
      83             :       ~__hash_enum();
      84             :     };
      85             : 
      86             :   // Helper struct for hash with enum types.
      87             :   template<typename _Tp>
      88             :     struct __hash_enum<_Tp, true> : public __hash_base<size_t, _Tp>
      89             :     {
      90             :       size_t
      91             :       operator()(_Tp __val) const noexcept
      92             :       {
      93             :        using __type = typename underlying_type<_Tp>::type;
      94             :        return hash<__type>{}(static_cast<__type>(__val));
      95             :       }
      96             :     };
      97             : 
      98             :   /// Primary class template hash, usable for enum types only.
      99             :   // Use with non-enum types still SFINAES.
     100             :   template<typename _Tp>
     101             :     struct hash : __hash_enum<_Tp>
     102             :     { };
     103             : 
     104             :   /// Partial specializations for pointer types.
     105             :   template<typename _Tp>
     106             :     struct hash<_Tp*> : public __hash_base<size_t, _Tp*>
     107             :     {
     108             :       size_t
     109       30723 :       operator()(_Tp* __p) const noexcept
     110       30723 :       { return reinterpret_cast<size_t>(__p); }
     111             :     };
     112             : 
     113             :   // Explicit specializations for integer types.
     114             : #define _Cxx_hashtable_define_trivial_hash(_Tp)         \
     115             :   template<>                                              \
     116             :     struct hash<_Tp> : public __hash_base<size_t, _Tp>  \
     117             :     {                                                   \
     118             :       size_t                                            \
     119             :       operator()(_Tp __val) const noexcept              \
     120             :       { return static_cast<size_t>(__val); }            \
     121             :     };
     122             : 
     123             :   /// Explicit specialization for bool.
     124             :   _Cxx_hashtable_define_trivial_hash(bool)
     125             : 
     126             :   /// Explicit specialization for char.
     127             :   _Cxx_hashtable_define_trivial_hash(char)
     128             : 
     129             :   /// Explicit specialization for signed char.
     130             :   _Cxx_hashtable_define_trivial_hash(signed char)
     131             : 
     132             :   /// Explicit specialization for unsigned char.
     133             :   _Cxx_hashtable_define_trivial_hash(unsigned char)
     134             : 
     135             :   /// Explicit specialization for wchar_t.
     136             :   _Cxx_hashtable_define_trivial_hash(wchar_t)
     137             : 
     138             :   /// Explicit specialization for char16_t.
     139             :   _Cxx_hashtable_define_trivial_hash(char16_t)
     140             : 
     141             :   /// Explicit specialization for char32_t.
     142             :   _Cxx_hashtable_define_trivial_hash(char32_t)
     143             : 
     144             :   /// Explicit specialization for short.
     145             :   _Cxx_hashtable_define_trivial_hash(short)
     146             : 
     147             :   /// Explicit specialization for int.
     148             :   _Cxx_hashtable_define_trivial_hash(int)
     149             : 
     150             :   /// Explicit specialization for long.
     151        2515 :   _Cxx_hashtable_define_trivial_hash(long)
     152             : 
     153             :   /// Explicit specialization for long long.
     154             :   _Cxx_hashtable_define_trivial_hash(long long)
     155             : 
     156             :   /// Explicit specialization for unsigned short.
     157             :   _Cxx_hashtable_define_trivial_hash(unsigned short)
     158             : 
     159             :   /// Explicit specialization for unsigned int.
     160             :   _Cxx_hashtable_define_trivial_hash(unsigned int)
     161             : 
     162             :   /// Explicit specialization for unsigned long.
     163             :   _Cxx_hashtable_define_trivial_hash(unsigned long)
     164             : 
     165             :   /// Explicit specialization for unsigned long long.
     166             :   _Cxx_hashtable_define_trivial_hash(unsigned long long)
     167             : 
     168             : #ifdef __GLIBCXX_TYPE_INT_N_0
     169             :   _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_0)
     170             :   _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_0 unsigned)
     171             : #endif
     172             : #ifdef __GLIBCXX_TYPE_INT_N_1
     173             :   _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_1)
     174             :   _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_1 unsigned)
     175             : #endif
     176             : #ifdef __GLIBCXX_TYPE_INT_N_2
     177             :   _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_2)
     178             :   _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_2 unsigned)
     179             : #endif
     180             : #ifdef __GLIBCXX_TYPE_INT_N_3
     181             :   _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_3)
     182             :   _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_3 unsigned)
     183             : #endif
     184             : 
     185             : #undef _Cxx_hashtable_define_trivial_hash
     186             : 
     187             :   struct _Hash_impl
     188             :   {
     189             :     static size_t
     190        1558 :     hash(const void* __ptr, size_t __clength,
     191             :          size_t __seed = static_cast<size_t>(0xc70f6907UL))
     192        1558 :     { return _Hash_bytes(__ptr, __clength, __seed); }
     193             : 
     194             :     template<typename _Tp>
     195             :       static size_t
     196             :       hash(const _Tp& __val)
     197             :       { return hash(&__val, sizeof(__val)); }
     198             : 
     199             :     template<typename _Tp>
     200             :       static size_t
     201             :       __hash_combine(const _Tp& __val, size_t __hash)
     202             :       { return hash(&__val, sizeof(__val), __hash); }
     203             :   };
     204             : 
     205             :   // A hash function similar to FNV-1a (see PR59406 for how it differs).
     206             :   struct _Fnv_hash_impl
     207             :   {
     208             :     static size_t
     209             :     hash(const void* __ptr, size_t __clength,
     210             :          size_t __seed = static_cast<size_t>(2166136261UL))
     211             :     { return _Fnv_hash_bytes(__ptr, __clength, __seed); }
     212             : 
     213             :     template<typename _Tp>
     214             :       static size_t
     215             :       hash(const _Tp& __val)
     216             :       { return hash(&__val, sizeof(__val)); }
     217             : 
     218             :     template<typename _Tp>
     219             :       static size_t
     220             :       __hash_combine(const _Tp& __val, size_t __hash)
     221             :       { return hash(&__val, sizeof(__val), __hash); }
     222             :   };
     223             : 
     224             :   /// Specialization for float.
     225             :   template<>
     226             :     struct hash<float> : public __hash_base<size_t, float>
     227             :     {
     228             :       size_t
     229             :       operator()(float __val) const noexcept
     230             :       {
     231             :         // 0 and -0 both hash to zero.
     232             :         return __val != 0.0f ? std::_Hash_impl::hash(__val) : 0;
     233             :       }
     234             :     };
     235             : 
     236             :   /// Specialization for double.
     237             :   template<>
     238             :     struct hash<double> : public __hash_base<size_t, double>
     239             :     {
     240             :       size_t
     241             :       operator()(double __val) const noexcept
     242             :       {
     243             :         // 0 and -0 both hash to zero.
     244             :         return __val != 0.0 ? std::_Hash_impl::hash(__val) : 0;
     245             :       }
     246             :     };
     247             : 
     248             :   /// Specialization for long double.
     249             :   template<>
     250             :     struct hash<long double>
     251             :     : public __hash_base<size_t, long double>
     252             :     {
     253             :       _GLIBCXX_PURE size_t
     254             :       operator()(long double __val) const noexcept;
     255             :     };
     256             : 
     257             :   // @} group hashes
     258             : 
     259             :   // Hint about performance of hash functor. If not fast the hash-based
     260             :   // containers will cache the hash code.
     261             :   // Default behavior is to consider that hashers are fast unless specified
     262             :   // otherwise.
     263             :   template<typename _Hash>
     264             :     struct __is_fast_hash : public std::true_type
     265             :     { };
     266             : 
     267             :   template<>
     268             :     struct __is_fast_hash<hash<long double>> : public std::false_type
     269             :     { };
     270             : 
     271             : _GLIBCXX_END_NAMESPACE_VERSION
     272             : } // namespace
     273             : 
     274             : #endif // _FUNCTIONAL_HASH_H