Line data    Source code

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