CnC
 All Classes Namespaces Functions Variables Typedefs Enumerator Friends Groups Pages
cnc_tag_hash_compare.h
1 //********************************************************************************
2 // Copyright (c) 2007-2013 Intel Corporation. All Rights Reserved. **
3 // **
4 // The source code contained or described herein and all documents related to **
5 // the source code ("Material") are owned by Intel Corporation or its suppliers **
6 // or licensors. Title to the Material remains with Intel Corporation or its **
7 // suppliers and licensors. The Material contains trade secrets and proprietary **
8 // and confidential information of Intel or its suppliers and licensors. The **
9 // Material is protected by worldwide copyright and trade secret laws and **
10 // treaty provisions. No part of the Material may be used, copied, reproduced, **
11 // modified, published, uploaded, posted, transmitted, distributed, or **
12 // disclosed in any way without Intel's prior express written permission. **
13 // **
14 // No license under any patent, copyright, trade secret or other intellectual **
15 // property right is granted to or conferred upon you by disclosure or delivery **
16 // of the Materials, either expressly, by implication, inducement, estoppel or **
17 // otherwise. Any license under such intellectual property rights must be **
18 // express and approved by Intel in writing. **
19 //********************************************************************************
20 
21 #ifndef _TAG_HASH_COMPARE_HH_ALREADY_INCLUDED
22 #define _TAG_HASH_COMPARE_HH_ALREADY_INCLUDED
23 
24 #include <string>
25 #include <vector>
26 #include <cnc/internal/cnc_stddef.h>
27 #include <cstring>
28 #include <tbb/concurrent_hash_map.h>
29 
30 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
31 
32 /// \brief Provides hash operators for hashing
33 ///
34 /// Specializations for custom data types must implement
35 /// hash and equal to work with preserving tag-collections (CnC::preserve_tuner)
36 /// and/or (default) CnC::item_collection using hashmaps.
37 ///
38 /// Standard data types are supported out-of-the-box as
39 /// well as std::vector and std:pair thereof, char*, std::string
40 /// and pointers (which you better avoid if ever possible, because it
41 /// pointers as tags are not portable, e.g. to distributed memory).
42 /// \return a unique integer for the given tag
43 template< typename T >
44 struct cnc_hash : public tbb::tbb_hash< T >
45 {
46 };
47 
48 /// \brief Provides equality operators for hashing
49 ///
50 /// Specializations for custom data types must implement
51 /// hash and equal to work with preserving tag-collections (CnC::preserve_tuner)
52 /// and/or (default) CnC::item_collection using hashmaps.
53 ///
54 /// Standard data types are supported out-of-the-box as
55 /// well as std::vector and std:pair thereof, char*, std::string
56 /// and pointers (which you better avoid if ever possible, because it
57 /// pointers as tags are not portable, e.g. to distributed memory).
58 /// \return true if a equals b, false otherwise
59 template< typename T >
60 struct cnc_equal : public std::equal_to< T >
61 {
62 };
63 
64 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
65 
66 // \brief hash for pointer types, but you better avoid tags being pointers
67 template< class T >
68 struct cnc_hash< T* >
69 {
70  size_t operator()( const T * x ) const
71  {
72  return reinterpret_cast< size_t >( x ) * 2654435761;
73  }
74 };
75 
76 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
77 
78 // \brief hash for const char *
79 template<>
80 struct cnc_hash< char * >
81 {
82  size_t operator()( const char * x ) const
83  {
84  // suggested by Paul Larson of Microsoft Research
85  size_t _n = 0;
86  while ( *x ) {
87  _n = _n * 101 + *x;
88  ++x;
89  }
90  return _n;
91  }
92 };
93 
94 // \brief equality for const char *
95 template<>
96 struct cnc_equal< char * >
97 {
98  bool operator()( const char * x, const char * y ) const
99  {
100  return ( strcmp( x, y ) == 0 );
101  }
102 };
103 
104 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
105 
106 /// \brief hash for std::string
107 template<>
108 struct cnc_hash< std::string >
109 {
110  size_t operator()( const std::string & x ) const
111  {
112  // suggested by Paul Larson of Microsoft Research
113  size_t _n = 0;
114  for( std::string::const_iterator i = x.begin(); i != x.end(); ++ i ) {
115  _n = _n * 101 + *i;
116  }
117  return _n;
118  }
119 };
120 
121 /// \brief equality for std::string
122 template<>
123 struct cnc_equal< std::string >
124 {
125  bool operator()( const std::string & a, const std::string & b ) const
126  {
127  return ( a.compare( b ) == 0 );
128  }
129 };
130 
131 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
132 
133 // \brief hash for std::pairs
134 template< class A >
135 struct cnc_hash< std::pair< A, A > > : public cnc_hash< A >
136 {
137  size_t operator()( const std::pair< A, A > & x ) const {
138  return ( cnc_hash< A >::operator()( x.first ) + ( cnc_hash< A >::operator()( x.second ) << 10 ) );
139  }
140 };
141 
142 template< class A, class B >
143 struct cnc_hash< std::pair< A, B > > : public cnc_hash< A >, public cnc_hash< B >
144 {
145  size_t operator()( const std::pair< A, B > & x ) const {
146  return ( cnc_hash< A >::operator()( x.first ) + ( cnc_hash< B >::operator()( x.second ) << 10 ) );
147  }
148 };
149 
150 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
151 
152 // \brief hash/equality for std::vector
153 template< class T, class Allocator >
154 struct cnc_hash< std::vector< T, Allocator > >
155 {
156 public:
157  size_t operator()( const std::vector< T, Allocator > & x ) const
158  {
159  size_t _n = x.size();
160  CNC_ASSERT( _n > 0 );
161  cnc_hash< T > _hasher;
162  switch( _n ) {
163  case 0 : return 0;
164  case 1 : return _hasher.operator()( x[0] );
165  case 2 : return ( _hasher.operator()( x[0] )
166  + ( _hasher.operator()( x[1] ) << 10 ) );;
167  case 3 : return ( _hasher.operator()( x[0] )
168  + ( _hasher.operator()( x[1] ) << 9 )
169  + ( _hasher.operator()( x[2] ) << 18 ) );
170  case 4 : return ( _hasher.operator()( x[0] )
171  + ( _hasher.operator()( x[3] ) << 8 )
172  + ( _hasher.operator()( x[1] ) << 16 )
173  + ( _hasher.operator()( x[2] ) << 24 ) );
174  default : {
175  size_t _n = 0;
176  for( typename std::vector< T, Allocator >::const_iterator i = x.begin(); i != x.end(); ++ i ) {
177  _n = _n * 3 + _hasher.operator()( *i );
178  }
179  return _n;
180  }
181  }
182  }
183 };
184 
185 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
186 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
187 
188 
189 /// \brief Provides hash and equality operators for hashing as used by item_collections
190 ///
191 /// It is recommended to specilialize cnc_hash and/or cnc_equal rather than cnc_tag_hash_compare
192 template< class T >
193 struct cnc_tag_hash_compare : public cnc_hash< T >, public cnc_equal< T >
194 {
195  /// \return a unique integer for the given tag
196  size_t hash( const T & x ) const
197  {
198  return cnc_hash< T >::operator()( x );
199  }
200  /// \return true if a equals b, false otherwise
201  bool equal( const T & x, const T & y ) const
202  {
203  return cnc_equal< T >::operator()( x, y );
204  }
205 };
206 
207 #endif // _TAG_HASH_COMPARE_HH_ALREADY_INCLUDED