cds/opt/hash.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_OPT_HASH_H
  32 #define CDSLIB_OPT_HASH_H
  33
  34 #include <tuple>
  35 #include <functional>
  36 #include <cds/opt/options.h>
  37
  38 namespace cds { namespace opt {
  39
  40     /// [type-option] Option setter for a hash function
  41     /**
  42         This option setter specifies hash functor used in unordered containers.
  43
  44         The default value  of template argument \p Functor is \p cds::opt::v::hash
  45         that is synonym for <tt>std::hash</tt> implementation of standard library.
  46     */
  47     template <typename Functor>
  48     struct hash {
  49         //@cond
  50         template <typename Base> struct pack: public Base
  51         {
  52             typedef Functor hash;
  53         };
  54         //@endcond
  55     };
  56
  57     namespace v {
  58         //@cond
  59         using std::hash;
  60
  61         /// Metafunction selecting default hash implementation
  62         /**
  63             The metafunction selects appropriate hash functor implementation.
  64             If \p Hash is not equal to opt::none, then result of metafunction is \p Hash.
  65             Otherwise, the result is <tt> std::hash<Q> </tt>.
  66
  67             Note that default hash function like <tt> std::hash<Q> </tt>
  68             is generally not suitable for complex type \p Q and its derivatives.
  69             You should manually provide particular hash functor for such types.
  70         */
  71         template <typename Hash>
  72         struct hash_selector
  73         {
  74             typedef Hash    type;   ///< resulting implementation of hash functor
  75         };
  76
  77         template <>
  78         struct hash_selector<opt::none>
  79         {
  80             struct type {
  81                 template <typename Q>
  82                 size_t operator()( Q const& key ) const
  83                 {
  84                     return std::hash<Q>()( key );
  85                 }
  86             };
  87         };
  88         //@endcond
  89     }   // namespace v
  90
  91     //@cond
  92     namespace details {
  93         template <class> struct hash_list;
  94         template <typename... Functors>
  95         struct hash_list< std::tuple<Functors...> >
  96         {
  97             static size_t const size = sizeof...(Functors);
  98             typedef size_t values[size];
  99             typedef std::tuple<Functors...> hash_tuple_type;
 100
 101             hash_tuple_type hash_tuple;
 102
 103             hash_list()
 104             {}
 105
 106             hash_list( hash_tuple_type const& t)
 107                 : hash_tuple( t )
 108             {}
 109             hash_list( hash_tuple_type&& t)
 110                 : hash_tuple( std::forward<hash_tuple_type>(t))
 111             {}
 112
 113             template <size_t I, typename T>
 114             typename std::enable_if< (I == sizeof...(Functors)) >::type apply( size_t * /*dest*/, T const& /*v*/ ) const
 115             {}
 116
 117             template <size_t I, typename T>
 118             typename std::enable_if< (I < sizeof...(Functors)) >::type apply( size_t * dest, T const& v ) const
 119             {
 120                 dest[I] = std::get<I>( hash_tuple )( v );
 121                 apply<I+1>( dest, v );
 122             }
 123
 124             template <typename T>
 125             void operator()( size_t * dest, T const& v ) const
 126             {
 127                 apply<0>( dest, v );
 128             }
 129         };
 130     } // namespace details
 131     //@endcond
 132
 133     /// Declare tuple for hash functors \p Functors
 134     template <typename... Functors>
 135     using hash_tuple = details::hash_list< std::tuple< Functors... >>;
 136
 137     //@cond
 138     // At least, two functors must be provided. Single functor is not supported
 139     template <typename Functor> struct hash< std::tuple<Functor> >;
 140     //@endcond
 141
 142     /// Multi-functor hash option setter - specialization for \p std::tuple
 143     template <typename... Functors>
 144     struct hash< std::tuple<Functors...> >
 145     {
 146         //@cond
 147         template <typename Base> struct pack: public Base
 148         {
 149             typedef details::hash_list< std::tuple<Functors...> >  hash;
 150         };
 151         //@endcond
 152     };
 153
 154
 155     //@cond
 156     namespace details {
 157
 158         template <class HashList, typename WrappedType, typename Wrapper>
 159         struct hash_list_wrapper {
 160             typedef HashList                            hash_list;
 161             typedef WrappedType                         wrapped_type;
 162             typedef Wrapper                             wrapper_type;
 163
 164             typedef typename hash_list::hash_tuple_type hash_tuple_type;
 165             static size_t const size = hash_list::size;
 166
 167             hash_list   m_wrappedList;
 168
 169             hash_list_wrapper()
 170             {}
 171             hash_list_wrapper( hash_tuple_type const& t)
 172                 : m_wrappedList( t )
 173             {}
 174             hash_list_wrapper( hash_tuple_type&& t)
 175                 : m_wrappedList( std::forward<hash_tuple_type>(t))
 176             {}
 177
 178             void operator()( size_t * dest, wrapped_type const& what ) const
 179             {
 180                 m_wrappedList( dest, wrapper_type()( what ));
 181             }
 182
 183             template <typename Q>
 184             void operator()( size_t * dest, Q const& what) const
 185             {
 186                 m_wrappedList( dest, what );
 187             }
 188         };
 189
 190     } // namespace details
 191     //@endcond
 192
 193 }} // namespace cds::opt
 194
 195 #endif // #ifndef CDSLIB_OPT_HASH_H