CnC
cnc_tag_hash_compare.h
00001 /* *******************************************************************************
00002  *  Copyright (c) 2007-2014, Intel Corporation
00003  *
00004  *  Redistribution and use in source and binary forms, with or without
00005  *  modification, are permitted provided that the following conditions are met:
00006  *
00007  *  * Redistributions of source code must retain the above copyright notice,
00008  *    this list of conditions and the following disclaimer.
00009  *  * Redistributions in binary form must reproduce the above copyright
00010  *    notice, this list of conditions and the following disclaimer in the
00011  *    documentation and/or other materials provided with the distribution.
00012  *  * Neither the name of Intel Corporation nor the names of its contributors
00013  *    may be used to endorse or promote products derived from this software
00014  *    without specific prior written permission.
00015  *
00016  *  THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
00017  *  AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00018  *  IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
00019  *  DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
00020  *  FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00021  *  DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
00022  *  SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
00023  *  CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
00024  *  OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
00025  *  OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
00026  ********************************************************************************/
00027 
00028 /*
00029   hashing and comparing tags and items.
00030 */
00031 
00032 #ifndef _TAG_HASH_COMPARE_HH_ALREADY_INCLUDED
00033 #define _TAG_HASH_COMPARE_HH_ALREADY_INCLUDED
00034 
00035 #include <string>
00036 #include <vector>
00037 #include <cnc/internal/cnc_stddef.h>
00038 #include <cstring>
00039 #include <cnc/internal/tbbcompat.h>
00040 #include <tbb/concurrent_hash_map.h>
00041 
00042 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00043 
00044 /// \brief Provides hash operators for hashing
00045 /// 
00046 /// Specializations for custom data types must implement
00047 /// hash and equal to work with preserving tag-collections (CnC::preserve_tuner)
00048 /// and/or (default) CnC::item_collection using hashmaps.
00049 ///
00050 /// Standard data types are supported out-of-the-box as
00051 /// well as std::vector and std:pair thereof, char*, std::string
00052 /// and pointers (which you better avoid if ever possible, because it
00053 /// pointers as tags are not portable, e.g. to distributed memory).
00054 /// \return a unique integer for the given tag
00055 template< typename T >
00056 struct cnc_hash : public tbb::tbb_hash< T >
00057 { 
00058 };
00059 
00060 /// \brief Provides equality operators for hashing
00061 /// 
00062 /// Specializations for custom data types must implement
00063 /// hash and equal to work with preserving tag-collections (CnC::preserve_tuner)
00064 /// and/or (default) CnC::item_collection using hashmaps.
00065 ///
00066 /// Standard data types are supported out-of-the-box as
00067 /// well as std::vector and std:pair thereof, char*, std::string
00068 /// and pointers (which you better avoid if ever possible, because it
00069 /// pointers as tags are not portable, e.g. to distributed memory).
00070 /// \return true if a equals b, false otherwise
00071 template< typename T >
00072 struct cnc_equal : public std::equal_to< T >
00073 {
00074 };
00075 
00076 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00077 
00078 // \brief hash for pointer types, but you better avoid tags being pointers
00079 template< class T >
00080 struct cnc_hash< T* >
00081 {
00082     size_t operator()( const T * x ) const
00083     { 
00084         return reinterpret_cast< size_t >( x ) * 2654435761;
00085     }
00086 };
00087 
00088 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00089 
00090 // \brief hash for const char *
00091 template<>
00092 struct cnc_hash< char * >
00093 {
00094     size_t operator()( const char * x ) const
00095     {
00096         // suggested by Paul Larson of Microsoft Research
00097         size_t _n = 0;
00098         while ( *x ) {
00099             _n = _n * 101  +  *x;
00100             ++x;
00101         }
00102         return _n;
00103     }
00104 };
00105 
00106 // \brief equality for const char *
00107 template<>
00108 struct cnc_equal< char * >
00109 {
00110     bool operator()( const char * x, const char * y ) const
00111     {
00112         return ( strcmp( x, y ) == 0 );
00113     }
00114 };
00115 
00116 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00117 
00118 /// \brief hash for std::string
00119 template<>
00120 struct cnc_hash< std::string >
00121 {
00122     size_t operator()( const std::string & x ) const
00123     {
00124         // suggested by Paul Larson of Microsoft Research
00125         size_t _n = 0;
00126         for( std::string::const_iterator i = x.begin(); i != x.end(); ++ i ) {
00127             _n = _n * 101  +  *i;
00128         }
00129         return _n;
00130     }
00131 };
00132 
00133 /// \brief equality for std::string
00134 template<>
00135 struct cnc_equal< std::string >
00136 {
00137     bool operator()( const std::string & a, const std::string & b ) const
00138     {
00139         return ( a.compare( b ) == 0 );
00140     }
00141 };
00142 
00143 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00144 
00145 // \brief hash/equality for std::vector
00146 template< class T, class Allocator >
00147 struct cnc_hash< std::vector< T, Allocator > >
00148 {
00149 public:
00150     size_t operator()( const std::vector< T, Allocator > & x ) const
00151     {
00152         size_t _n = x.size();
00153         CNC_ASSERT( _n > 0 );
00154         cnc_hash< T > _hasher;
00155         switch( _n ) {
00156             case 0 : return 0;
00157             case 1 : return _hasher.operator()( x[0] );
00158             case 2 : return ( _hasher.operator()( x[0] )
00159                               + ( _hasher.operator()( x[1] ) << 10 ) );;
00160             case 3 : return ( _hasher.operator()( x[0] )
00161                                + ( _hasher.operator()( x[1] ) << 9 )
00162                                + ( _hasher.operator()( x[2] ) << 18 ) );
00163             case 4 : return ( _hasher.operator()( x[0] )
00164                                + ( _hasher.operator()( x[3] ) << 8 )
00165                                + ( _hasher.operator()( x[1] ) << 16 )
00166                                + ( _hasher.operator()( x[2] ) << 24 ) );
00167             default : {
00168                 size_t _n = 0;
00169                 for( typename std::vector< T, Allocator >::const_iterator i = x.begin(); i != x.end(); ++ i ) {
00170                     _n = _n * 3  + _hasher.operator()( *i );
00171                 }
00172                 return _n;
00173             }
00174         }
00175     }
00176 };
00177 
00178 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00179 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
00180 
00181 
00182 /// \brief Provides hash and equality operators for hashing as used by item_collections
00183 ///
00184 /// It is recommended to specilialize cnc_hash and/or cnc_equal rather than cnc_tag_hash_compare
00185 template< class T >
00186 struct cnc_tag_hash_compare : public cnc_hash< T >, public cnc_equal< T >
00187 {
00188     /// \return a unique integer for the given tag
00189     size_t hash( const T & x ) const
00190     { 
00191         return cnc_hash< T >::operator()( x );
00192     }
00193     /// \return true if a equals b, false otherwise
00194     bool equal( const T & x, const T & y ) const
00195     {
00196         return cnc_equal< T >::operator()( x, y );
00197     }
00198 };
00199 
00200 #endif // _TAG_HASH_COMPARE_HH_ALREADY_INCLUDED