cds/opt/hash.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_OPT_HASH_H
   4 #define __CDS_OPT_HASH_H
   5
   6 #include <cds/opt/options.h>
   7 #include <cds/details/hash_functor_selector.h>
   8 #include <cds/details/std/tuple.h>
   9
  10 namespace cds { namespace opt {
  11
  12     /// [type-option] Option setter for a hash function
  13     /**
  14         This option setter specifies hash functor used in unordered containers.
  15
  16         The default value  of template argument \p Functor is \p cds::opt::v::hash
  17         that is synonym for <tt>std::hash</tt> implementation of standard library.
  18         If standard C++ library of the compiler you use does not provide TR1 implementation
  19         the \p cds library automatically selects <tt>boost::hash</tt>.
  20     */
  21     template <typename Functor>
  22     struct hash {
  23         //@cond
  24         template <typename Base> struct pack: public Base
  25         {
  26             typedef Functor hash;
  27         };
  28         //@endcond
  29     };
  30
  31     namespace v {
  32         //@cond
  33         using cds::details::hash;
  34
  35         /// Metafunction selecting default hash implementation
  36         /**
  37             The metafunction selects appropriate hash functor implementation.
  38             If \p Hash is not equal to opt::none, then result of metafunction is \p Hash.
  39             Otherwise, the result is <tt> std::hash<Q> </tt> or <tt> boost::hash<Q> </tt>
  40             depending of compiler you use.
  41
  42             Note that default hash function like <tt> std::hash<Q> </tt> or <tt> boost::hash<Q> </tt>
  43             is generally not suitable for complex type \p Q and its derivatives.
  44             You should manually provide particular hash functor for such types.
  45         */
  46         template <typename Hash>
  47         struct hash_selector
  48         {
  49             typedef Hash    type    ;   ///< resulting implementation of hash functor
  50         };
  51
  52         template <>
  53         struct hash_selector<opt::none>
  54         {
  55             struct type {
  56                 template <typename Q>
  57                 size_t operator()( Q const& key ) const
  58                 {
  59                     return hash<Q>()( key );
  60                 }
  61             };
  62         };
  63         //@endcond
  64     }   // namespace v
  65
  66 #ifdef CDS_CXX11_VARIADIC_TEMPLATE_SUPPORT
  67     //@cond
  68     namespace details {
  69         template <class> struct hash_list;
  70         template <typename... Functors>
  71         struct hash_list< std::tuple<Functors...> >
  72         {
  73             static size_t const size = sizeof...(Functors);
  74             typedef size_t values[size];
  75             typedef std::tuple<Functors...> hash_tuple_type;
  76
  77             hash_tuple_type hash_tuple;
  78
  79             hash_list()
  80             {}
  81
  82             hash_list( hash_tuple_type const& t)
  83                 : hash_tuple( t )
  84             {}
  85 #       ifdef CDS_MOVE_SEMANTICS_SUPPORT
  86             hash_list( hash_tuple_type&& t)
  87                 : hash_tuple( std::forward<hash_tuple_type>(t) )
  88             {}
  89 #       endif
  90
  91             template <size_t I, typename T>
  92             typename std::enable_if< (I == sizeof...(Functors)) >::type apply( size_t * dest, T const& v ) const
  93             {}
  94
  95             template <size_t I, typename T>
  96             typename std::enable_if< (I < sizeof...(Functors)) >::type apply( size_t * dest, T const& v ) const
  97             {
  98                 dest[I] = std::get<I>( hash_tuple )( v );
  99                 apply<I+1>( dest, v );
 100             }
 101
 102             template <typename T>
 103             void operator()( size_t * dest, T const& v ) const
 104             {
 105                 apply<0>( dest, v );
 106             }
 107         };
 108     } // namespace details
 109     //@endcond
 110
 111     //@cond
 112     // At least, two functors must be provided. Single functor is not supported
 113 //#if CDS_COMPILER != CDS_COMPILER_INTEL
 114     // Intel C++ compiler does not support
 115     template <typename Functor> struct hash< std::tuple<Functor> >;
 116 //#endif
 117     //@endcond
 118
 119     /// Multi-functor hash option setter - specialization for std::tuple
 120     template <typename... Functors>
 121     struct hash< std::tuple<Functors...> >
 122     {
 123 //#   if CDS_COMPILER == CDS_COMPILER_INTEL
 124         //static_assert( sizeof...(Functors) > 1, "At least, two functors must be provided. Single functor is not supported" );
 125 //#   endif
 126         //@cond
 127         template <typename Base> struct pack: public Base
 128         {
 129             typedef details::hash_list< std::tuple<Functors...> >  hash;
 130         };
 131         //@endcond
 132     };
 133
 134 #else   // no variadic template support
 135     namespace details {
 136         template <typename T> struct hash_list;
 137         template <typename F1, typename F2>
 138         struct hash_list< std::tuple<F1, F2> >
 139         {
 140             static size_t const size = 2;
 141             typedef size_t values[size];
 142             typedef std::tuple<F1, F2>  hash_tuple_type;
 143
 144             hash_tuple_type hash_tuple;
 145
 146             hash_list()
 147             {}
 148             hash_list( hash_tuple_type const& t)
 149                 : hash_tuple( t )
 150             {}
 151 #       ifdef CDS_MOVE_SEMANTICS_SUPPORT
 152             hash_list( hash_tuple_type&& t)
 153                 : hash_tuple( t )
 154             {}
 155 #       endif
 156
 157             template <typename T>
 158             void operator()( size_t * dest, T const& v ) const
 159             {
 160                 dest[0] = std::get<0>( hash_tuple )( v );
 161                 dest[1] = std::get<1>( hash_tuple )( v );
 162             }
 163         };
 164
 165         template <typename F1, typename F2, typename F3>
 166         struct hash_list< std::tuple<F1, F2, F3> >
 167         {
 168             static size_t const size = 3;
 169             typedef size_t values[size];
 170             typedef std::tuple<F1, F2, F3> hash_tuple_type;
 171
 172             hash_tuple_type hash_tuple;
 173
 174             hash_list()
 175             {}
 176             hash_list( hash_tuple_type const& t)
 177                 : hash_tuple( t )
 178             {}
 179 #       ifdef CDS_MOVE_SEMANTICS_SUPPORT
 180             hash_list( hash_tuple_type&& t)
 181                 : hash_tuple( t )
 182             {}
 183 #       endif
 184
 185             template <typename T>
 186             void operator()( size_t * dest, T const& v ) const
 187             {
 188                 dest[0] = std::get<0>( hash_tuple )( v );
 189                 dest[1] = std::get<1>( hash_tuple )( v );
 190                 dest[2] = std::get<2>( hash_tuple )( v );
 191             }
 192         };
 193
 194         template <typename F1, typename F2, typename F3, typename F4>
 195         struct hash_list< std::tuple<F1, F2, F3, F4> >
 196         {
 197             static size_t const size = 4;
 198             typedef size_t values[size];
 199             typedef std::tuple<F1, F2, F3, F4> hash_tuple_type;
 200
 201             hash_tuple_type hash_tuple;
 202
 203             hash_list()
 204             {}
 205             hash_list( hash_tuple_type const& t)
 206                 : hash_tuple( t )
 207             {}
 208 #       ifdef CDS_MOVE_SEMANTICS_SUPPORT
 209             hash_list( hash_tuple_type&& t)
 210                 : hash_tuple( t )
 211             {}
 212 #       endif
 213
 214             template <typename T>
 215             void operator()( size_t * dest, T const& v ) const
 216             {
 217                 dest[0] = std::get<0>( hash_tuple )( v );
 218                 dest[1] = std::get<1>( hash_tuple )( v );
 219                 dest[2] = std::get<2>( hash_tuple )( v );
 220                 dest[3] = std::get<3>( hash_tuple )( v );
 221             }
 222         };
 223
 224         template <typename F1, typename F2, typename F3, typename F4, typename F5>
 225         struct hash_list< std::tuple<F1, F2, F3, F4, F5> >
 226         {
 227             static size_t const size = 5;
 228             typedef size_t values[size];
 229             typedef std::tuple<F1, F2, F3, F4, F5> hash_tuple_type;
 230
 231             hash_tuple_type hash_tuple;
 232
 233             hash_list()
 234             {}
 235             hash_list( hash_tuple_type const& t)
 236                 : hash_tuple( t )
 237             {}
 238 #       ifdef CDS_MOVE_SEMANTICS_SUPPORT
 239             hash_list( hash_tuple_type&& t)
 240                 : hash_tuple( t )
 241             {}
 242 #       endif
 243
 244             template <typename T>
 245             void operator()( size_t * dest, T const& v ) const
 246             {
 247                 dest[0] = std::get<0>( hash_tuple )( v );
 248                 dest[1] = std::get<1>( hash_tuple )( v );
 249                 dest[2] = std::get<2>( hash_tuple )( v );
 250                 dest[3] = std::get<3>( hash_tuple )( v );
 251                 dest[4] = std::get<4>( hash_tuple )( v );
 252             }
 253         };
 254
 255         template <typename F1, typename F2, typename F3, typename F4, typename F5, typename F6>
 256         struct hash_list< std::tuple<F1, F2, F3, F4, F5, F6> >
 257         {
 258             static size_t const size = 6;
 259             typedef size_t values[size];
 260             typedef std::tuple<F1, F2, F3, F4, F5, F6> hash_tuple_type;
 261
 262             hash_tuple_type hash_tuple;
 263
 264             hash_list()
 265             {}
 266             hash_list( hash_tuple_type const& t)
 267                 : hash_tuple( t )
 268             {}
 269 #       ifdef CDS_MOVE_SEMANTICS_SUPPORT
 270             hash_list( hash_tuple_type&& t)
 271                 : hash_tuple( t )
 272             {}
 273 #       endif
 274
 275             template <typename T>
 276             void operator()( size_t * dest, T const& v ) const
 277             {
 278                 dest[0] = std::get<0>( hash_tuple )( v );
 279                 dest[1] = std::get<1>( hash_tuple )( v );
 280                 dest[2] = std::get<2>( hash_tuple )( v );
 281                 dest[3] = std::get<3>( hash_tuple )( v );
 282                 dest[4] = std::get<4>( hash_tuple )( v );
 283                 dest[5] = std::get<5>( hash_tuple )( v );
 284             }
 285         };
 286
 287         template <typename F1, typename F2, typename F3, typename F4, typename F5, typename F6, typename F7>
 288         struct hash_list< std::tuple<F1, F2, F3, F4, F5, F6, F7> >
 289         {
 290             static size_t const size = 7;
 291             typedef size_t values[size];
 292             typedef std::tuple<F1, F2, F3, F4, F5, F6, F7> hash_tuple_type;
 293
 294             hash_tuple_type hash_tuple;
 295
 296             hash_list()
 297             {}
 298             hash_list( hash_tuple_type const& t)
 299                 : hash_tuple( t )
 300             {}
 301 #       ifdef CDS_MOVE_SEMANTICS_SUPPORT
 302             hash_list( hash_tuple_type&& t)
 303                 : hash_tuple( t )
 304             {}
 305 #       endif
 306
 307             template <typename T>
 308             void operator()( size_t * dest, T const& v ) const
 309             {
 310                 dest[0] = std::get<0>( hash_tuple )( v );
 311                 dest[1] = std::get<1>( hash_tuple )( v );
 312                 dest[2] = std::get<2>( hash_tuple )( v );
 313                 dest[3] = std::get<3>( hash_tuple )( v );
 314                 dest[4] = std::get<4>( hash_tuple )( v );
 315                 dest[5] = std::get<5>( hash_tuple )( v );
 316                 dest[6] = std::get<6>( hash_tuple )( v );
 317             }
 318         };
 319
 320         template <typename F1, typename F2, typename F3, typename F4, typename F5, typename F6, typename F7, typename F8>
 321         struct hash_list< std::tuple<F1, F2, F3, F4, F5, F6, F7, F8> >
 322         {
 323             static size_t const size = 8;
 324             typedef size_t values[size];
 325             typedef std::tuple<F1, F2, F3, F4, F5, F6, F7, F8> hash_tuple_type;
 326
 327             hash_tuple_type hash_tuple;
 328
 329             hash_list()
 330             {}
 331             hash_list( hash_tuple_type const& t)
 332                 : hash_tuple( t )
 333             {}
 334 #       ifdef CDS_MOVE_SEMANTICS_SUPPORT
 335             hash_list( hash_tuple_type&& t)
 336                 : hash_tuple( t )
 337             {}
 338 #       endif
 339
 340             template <typename T>
 341             void operator()( size_t * dest, T const& v ) const
 342             {
 343                 dest[0] = std::get<0>( hash_tuple )( v );
 344                 dest[1] = std::get<1>( hash_tuple )( v );
 345                 dest[2] = std::get<2>( hash_tuple )( v );
 346                 dest[3] = std::get<3>( hash_tuple )( v );
 347                 dest[4] = std::get<4>( hash_tuple )( v );
 348                 dest[5] = std::get<5>( hash_tuple )( v );
 349                 dest[6] = std::get<6>( hash_tuple )( v );
 350                 dest[7] = std::get<7>( hash_tuple )( v );
 351             }
 352         };
 353
 354 #if !((CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL) && _MSC_VER == 1700)
 355         // MSVC 11: max count of argument is 8
 356
 357         template <typename F1, typename F2, typename F3, typename F4, typename F5, typename F6, typename F7, typename F8, typename F9>
 358         struct hash_list< std::tuple<F1, F2, F3, F4, F5, F6, F7, F8, F9> >
 359         {
 360             static size_t const size = 9;
 361             typedef size_t values[size];
 362             typedef std::tuple<F1, F2, F3, F4, F5, F6, F7, F8, F9> hash_tuple_type;
 363
 364             hash_tuple_type hash_tuple;
 365
 366             hash_list()
 367             {}
 368             hash_list( hash_tuple_type const& t)
 369                 : hash_tuple( t )
 370             {}
 371 #       ifdef CDS_MOVE_SEMANTICS_SUPPORT
 372             hash_list( hash_tuple_type&& t)
 373                 : hash_tuple( t )
 374             {}
 375 #       endif
 376
 377             template <typename T>
 378             void operator()( size_t * dest, T const& v ) const
 379             {
 380                 dest[0] = std::get<0>( hash_tuple )( v );
 381                 dest[1] = std::get<1>( hash_tuple )( v );
 382                 dest[2] = std::get<2>( hash_tuple )( v );
 383                 dest[3] = std::get<3>( hash_tuple )( v );
 384                 dest[4] = std::get<4>( hash_tuple )( v );
 385                 dest[5] = std::get<5>( hash_tuple )( v );
 386                 dest[6] = std::get<6>( hash_tuple )( v );
 387                 dest[7] = std::get<7>( hash_tuple )( v );
 388                 dest[8] = std::get<8>( hash_tuple )( v );
 389             }
 390         };
 391
 392         template <typename F1, typename F2, typename F3, typename F4, typename F5, typename F6, typename F7, typename F8, typename F9,
 393                   typename F10>
 394         struct hash_list< std::tuple<F1, F2, F3, F4, F5, F6, F7, F8, F9, F10> >
 395         {
 396             static size_t const size = 10;
 397             typedef size_t values[size];
 398             typedef std::tuple<F1, F2, F3, F4, F5, F6, F7, F8, F9, F10> hash_tuple_type;
 399
 400             hash_tuple_type hash_tuple;
 401
 402             hash_list()
 403             {}
 404             hash_list( hash_tuple_type const& t)
 405                 : hash_tuple( t )
 406             {}
 407 #       ifdef CDS_MOVE_SEMANTICS_SUPPORT
 408             hash_list( hash_tuple_type&& t)
 409                 : hash_tuple( t )
 410             {}
 411 #       endif
 412
 413             template <typename T>
 414             void operator()( size_t * dest, T const& v ) const
 415             {
 416                 dest[0] = std::get<0>( hash_tuple )( v );
 417                 dest[1] = std::get<1>( hash_tuple )( v );
 418                 dest[2] = std::get<2>( hash_tuple )( v );
 419                 dest[3] = std::get<3>( hash_tuple )( v );
 420                 dest[4] = std::get<4>( hash_tuple )( v );
 421                 dest[5] = std::get<5>( hash_tuple )( v );
 422                 dest[6] = std::get<6>( hash_tuple )( v );
 423                 dest[7] = std::get<7>( hash_tuple )( v );
 424                 dest[8] = std::get<8>( hash_tuple )( v );
 425                 dest[9] = std::get<9>( hash_tuple )( v );
 426             }
 427         };
 428 #endif
 429     } // namespace details
 430
 431     template< typename F1, typename F2 >
 432     struct hash< std::tuple< F1, F2 > >
 433     {
 434         //@cond
 435         template <typename Base> struct pack: public Base
 436         {
 437             typedef details::hash_list< std::tuple<F1, F2> >  hash;
 438         };
 439         //@endcond
 440     };
 441     template< typename F1, typename F2, typename F3 >
 442     struct hash< std::tuple< F1, F2, F3 > >
 443     {
 444         //@cond
 445         template <typename Base> struct pack: public Base
 446         {
 447             typedef details::hash_list< std::tuple<F1, F2, F3> >  hash;
 448         };
 449         //@endcond
 450     };
 451     template< typename F1, typename F2, typename F3, typename F4 >
 452     struct hash< std::tuple< F1, F2, F3, F4 > >
 453     {
 454         //@cond
 455         template <typename Base> struct pack: public Base
 456         {
 457             typedef details::hash_list< std::tuple<F1, F2, F3, F4> >  hash;
 458         };
 459         //@endcond
 460     };
 461     template< typename F1, typename F2, typename F3, typename F4, typename F5 >
 462     struct hash< std::tuple< F1, F2, F3, F4, F5 > >
 463     {
 464         //@cond
 465         template <typename Base> struct pack: public Base
 466         {
 467             typedef details::hash_list< std::tuple<F1, F2, F3, F4, F5> >  hash;
 468         };
 469         //@endcond
 470     };
 471     template< typename F1, typename F2, typename F3, typename F4, typename F5, typename F6 >
 472     struct hash< std::tuple< F1, F2, F3, F4, F5, F6 > >
 473     {
 474         //@cond
 475         template <typename Base> struct pack: public Base
 476         {
 477             typedef details::hash_list< std::tuple<F1, F2, F3, F4, F5, F6> >  hash;
 478         };
 479         //@endcond
 480     };
 481     template< typename F1, typename F2, typename F3, typename F4, typename F5, typename F6, typename F7 >
 482     struct hash< std::tuple< F1, F2, F3, F4, F5, F6, F7 > >
 483     {
 484         //@cond
 485         template <typename Base> struct pack: public Base
 486         {
 487             typedef details::hash_list< std::tuple<F1, F2, F3, F4, F5, F6, F7> >  hash;
 488         };
 489         //@endcond
 490     };
 491     template< typename F1, typename F2, typename F3, typename F4, typename F5, typename F6, typename F7, typename F8 >
 492     struct hash< std::tuple< F1, F2, F3, F4, F5, F6, F7, F8 > >
 493     {
 494         //@cond
 495         template <typename Base> struct pack: public Base
 496         {
 497             typedef details::hash_list< std::tuple<F1, F2, F3, F4, F5, F6, F7, F8> >  hash;
 498         };
 499         //@endcond
 500     };
 501
 502 #if !((CDS_COMPILER == CDS_COMPILER_MSVC || CDS_COMPILER == CDS_COMPILER_INTEL) && _MSC_VER == 1700)
 503     // MSVC 11: max count of argument is 8
 504
 505     template< typename F1, typename F2, typename F3, typename F4, typename F5, typename F6, typename F7, typename F8, typename F9 >
 506     struct hash< std::tuple< F1, F2, F3, F4, F5, F6, F7, F8, F9 > >
 507     {
 508         //@cond
 509         template <typename Base> struct pack: public Base
 510         {
 511             typedef details::hash_list< std::tuple<F1, F2, F3, F4, F5, F6, F7, F8, F9> >  hash;
 512         };
 513         //@endcond
 514     };
 515     template< typename F1, typename F2, typename F3, typename F4, typename F5, typename F6, typename F7, typename F8, typename F9,
 516               typename F10 >
 517     struct hash< std::tuple< F1, F2, F3, F4, F5, F6, F7, F8, F9, F10 > >
 518     {
 519         //@cond
 520         template <typename Base> struct pack: public Base
 521         {
 522             typedef details::hash_list< std::tuple<F1, F2, F3, F4, F5, F6, F7, F8, F9, F10> >  hash;
 523         };
 524         //@endcond
 525     };
 526 #endif  // !MSVC11
 527 #endif  // #ifdef CDS_CXX11_VARIADIC_TEMPLATE_SUPPORT
 528
 529     //@cond
 530     namespace details {
 531
 532         template <class HashList, typename WrappedType, typename Wrapper>
 533         struct hash_list_wrapper {
 534             typedef HashList                            hash_list;
 535             typedef WrappedType                         wrapped_type;
 536             typedef Wrapper                             wrapper_type;
 537
 538             typedef typename hash_list::hash_tuple_type hash_tuple_type;
 539             static size_t const size = hash_list::size;
 540
 541             hash_list   m_wrappedList;
 542
 543             hash_list_wrapper()
 544             {}
 545             hash_list_wrapper( hash_tuple_type const& t)
 546                 : m_wrappedList( t )
 547             {}
 548 #       ifdef CDS_MOVE_SEMANTICS_SUPPORT
 549             hash_list_wrapper( hash_tuple_type&& t)
 550                 : m_wrappedList( std::forward<hash_tuple_type>(t) )
 551             {}
 552 #       endif
 553
 554             void operator()( size_t * dest, wrapped_type const& what ) const
 555             {
 556                 m_wrappedList( dest, wrapper_type()( what ));
 557             }
 558
 559             template <typename Q>
 560             void operator()( size_t * dest, Q const& what) const
 561             {
 562                 m_wrappedList( dest, what );
 563             }
 564         };
 565
 566     } // namespace details
 567     //@endcond
 568
 569 }} // namespace cds::opt
 570
 571 #endif // #ifndef __CDS_OPT_HASH_H