CnC
|
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