Line data    Source code

       1             : // functional_hash.h header -*- C++ -*-
       2             : 
       3             : // Copyright (C) 2007-2019 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          22 :       operator()(_Tp __val) const noexcept
      92             :       {
      93             :        using __type = typename underlying_type<_Tp>::type;
      94          22 :        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             :       operator()(_Tp* __p) const noexcept
     110             :       { 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          22 :   _Cxx_hashtable_define_trivial_hash(unsigned char)
     134             : 
     135             :   /// Explicit specialization for wchar_t.
     136             :   _Cxx_hashtable_define_trivial_hash(wchar_t)
     137             : 
     138             : #ifdef _GLIBCXX_USE_CHAR8_T
     139             :   /// Explicit specialization for char8_t.
     140             :   _Cxx_hashtable_define_trivial_hash(char8_t)
     141             : #endif
     142             : 
     143             :   /// Explicit specialization for char16_t.
     144             :   _Cxx_hashtable_define_trivial_hash(char16_t)
     145             : 
     146             :   /// Explicit specialization for char32_t.
     147             :   _Cxx_hashtable_define_trivial_hash(char32_t)
     148             : 
     149             :   /// Explicit specialization for short.
     150             :   _Cxx_hashtable_define_trivial_hash(short)
     151             : 
     152             :   /// Explicit specialization for int.
     153             :   _Cxx_hashtable_define_trivial_hash(int)
     154             : 
     155             :   /// Explicit specialization for long.
     156             :   _Cxx_hashtable_define_trivial_hash(long)
     157             : 
     158             :   /// Explicit specialization for long long.
     159             :   _Cxx_hashtable_define_trivial_hash(long long)
     160             : 
     161             :   /// Explicit specialization for unsigned short.
     162             :   _Cxx_hashtable_define_trivial_hash(unsigned short)
     163             : 
     164             :   /// Explicit specialization for unsigned int.
     165             :   _Cxx_hashtable_define_trivial_hash(unsigned int)
     166             : 
     167             :   /// Explicit specialization for unsigned long.
     168             :   _Cxx_hashtable_define_trivial_hash(unsigned long)
     169             : 
     170             :   /// Explicit specialization for unsigned long long.
     171             :   _Cxx_hashtable_define_trivial_hash(unsigned long long)
     172             : 
     173             : #ifdef __GLIBCXX_TYPE_INT_N_0
     174             :   _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_0)
     175             :   _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_0 unsigned)
     176             : #endif
     177             : #ifdef __GLIBCXX_TYPE_INT_N_1
     178             :   _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_1)
     179             :   _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_1 unsigned)
     180             : #endif
     181             : #ifdef __GLIBCXX_TYPE_INT_N_2
     182             :   _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_2)
     183             :   _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_2 unsigned)
     184             : #endif
     185             : #ifdef __GLIBCXX_TYPE_INT_N_3
     186             :   _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_3)
     187             :   _Cxx_hashtable_define_trivial_hash(__GLIBCXX_TYPE_INT_N_3 unsigned)
     188             : #endif
     189             : 
     190             : #undef _Cxx_hashtable_define_trivial_hash
     191             : 
     192             :   struct _Hash_impl
     193             :   {
     194             :     static size_t
     195             :     hash(const void* __ptr, size_t __clength,
     196             :          size_t __seed = static_cast<size_t>(0xc70f6907UL))
     197             :     { return _Hash_bytes(__ptr, __clength, __seed); }
     198             : 
     199             :     template<typename _Tp>
     200             :       static size_t
     201             :       hash(const _Tp& __val)
     202             :       { return hash(&__val, sizeof(__val)); }
     203             : 
     204             :     template<typename _Tp>
     205             :       static size_t
     206             :       __hash_combine(const _Tp& __val, size_t __hash)
     207             :       { return hash(&__val, sizeof(__val), __hash); }
     208             :   };
     209             : 
     210             :   // A hash function similar to FNV-1a (see PR59406 for how it differs).
     211             :   struct _Fnv_hash_impl
     212             :   {
     213             :     static size_t
     214             :     hash(const void* __ptr, size_t __clength,
     215             :          size_t __seed = static_cast<size_t>(2166136261UL))
     216             :     { return _Fnv_hash_bytes(__ptr, __clength, __seed); }
     217             : 
     218             :     template<typename _Tp>
     219             :       static size_t
     220             :       hash(const _Tp& __val)
     221             :       { return hash(&__val, sizeof(__val)); }
     222             : 
     223             :     template<typename _Tp>
     224             :       static size_t
     225             :       __hash_combine(const _Tp& __val, size_t __hash)
     226             :       { return hash(&__val, sizeof(__val), __hash); }
     227             :   };
     228             : 
     229             :   /// Specialization for float.
     230             :   template<>
     231             :     struct hash<float> : public __hash_base<size_t, float>
     232             :     {
     233             :       size_t
     234             :       operator()(float __val) const noexcept
     235             :       {
     236             :         // 0 and -0 both hash to zero.
     237             :         return __val != 0.0f ? std::_Hash_impl::hash(__val) : 0;
     238             :       }
     239             :     };
     240             : 
     241             :   /// Specialization for double.
     242             :   template<>
     243             :     struct hash<double> : public __hash_base<size_t, double>
     244             :     {
     245             :       size_t
     246             :       operator()(double __val) const noexcept
     247             :       {
     248             :         // 0 and -0 both hash to zero.
     249             :         return __val != 0.0 ? std::_Hash_impl::hash(__val) : 0;
     250             :       }
     251             :     };
     252             : 
     253             :   /// Specialization for long double.
     254             :   template<>
     255             :     struct hash<long double>
     256             :     : public __hash_base<size_t, long double>
     257             :     {
     258             :       _GLIBCXX_PURE size_t
     259             :       operator()(long double __val) const noexcept;
     260             :     };
     261             : 
     262             : #if __cplusplus >= 201703L
     263             :   template<>
     264             :     struct hash<nullptr_t> : public __hash_base<size_t, nullptr_t>
     265             :     {
     266             :       size_t
     267             :       operator()(nullptr_t) const noexcept
     268             :       { return 0; }
     269             :     };
     270             : #endif
     271             : 
     272             :   /// @} group hashes
     273             : 
     274             :   // Hint about performance of hash functor. If not fast the hash-based
     275             :   // containers will cache the hash code.
     276             :   // Default behavior is to consider that hashers are fast unless specified
     277             :   // otherwise.
     278             :   template<typename _Hash>
     279             :     struct __is_fast_hash : public std::true_type
     280             :     { };
     281             : 
     282             :   template<>
     283             :     struct __is_fast_hash<hash<long double>> : public std::false_type
     284             :     { };
     285             : 
     286             : _GLIBCXX_END_NAMESPACE_VERSION
     287             : } // namespace
     288             : 
     289             : #endif // _FUNCTIONAL_HASH_H