CnC
cnc_tag_hash_compare.h
1 /* *******************************************************************************
2  * Copyright (c) 2007-2014, Intel Corporation
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions are met:
6  *
7  * * Redistributions of source code must retain the above copyright notice,
8  * this list of conditions and the following disclaimer.
9  * * Redistributions in binary form must reproduce the above copyright
10  * notice, this list of conditions and the following disclaimer in the
11  * documentation and/or other materials provided with the distribution.
12  * * Neither the name of Intel Corporation nor the names of its contributors
13  * may be used to endorse or promote products derived from this software
14  * without specific prior written permission.
15  *
16  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19  * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
20  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
21  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
22  * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
23  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
24  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
25  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26  ********************************************************************************/
27 
28 /*
29  hashing and comparing tags and items.
30 */
31 
32 #ifndef _TAG_HASH_COMPARE_HH_ALREADY_INCLUDED
33 #define _TAG_HASH_COMPARE_HH_ALREADY_INCLUDED
34 
35 #include <string>
36 #include <vector>
37 #include <cnc/internal/cnc_stddef.h>
38 #include <cstring>
39 #include <cnc/internal/tbbcompat.h>
40 #include <tbb/concurrent_hash_map.h>
41 
42 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
43 
44 /// \brief Provides hash operators for hashing
45 ///
46 /// Specializations for custom data types must implement
47 /// hash and equal to work with preserving tag-collections (CnC::preserve_tuner)
48 /// and/or (default) CnC::item_collection using hashmaps.
49 ///
50 /// Standard data types are supported out-of-the-box as
51 /// well as std::vector and std:pair thereof, char*, std::string
52 /// and pointers (which you better avoid if ever possible, because it
53 /// pointers as tags are not portable, e.g. to distributed memory).
54 /// \return a unique integer for the given tag
55 template< typename T >
56 struct cnc_hash : public tbb::tbb_hash< T >
57 {
58 };
59 
60 /// \brief Provides equality operators for hashing
61 ///
62 /// Specializations for custom data types must implement
63 /// hash and equal to work with preserving tag-collections (CnC::preserve_tuner)
64 /// and/or (default) CnC::item_collection using hashmaps.
65 ///
66 /// Standard data types are supported out-of-the-box as
67 /// well as std::vector and std:pair thereof, char*, std::string
68 /// and pointers (which you better avoid if ever possible, because it
69 /// pointers as tags are not portable, e.g. to distributed memory).
70 /// \return true if a equals b, false otherwise
71 template< typename T >
72 struct cnc_equal : public std::equal_to< T >
73 {
74 };
75 
76 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
77 
78 // \brief hash for pointer types, but you better avoid tags being pointers
79 template< class T >
80 struct cnc_hash< T* >
81 {
82  size_t operator()( const T * x ) const
83  {
84  return reinterpret_cast< size_t >( x ) * 2654435761;
85  }
86 };
87 
88 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
89 
90 // \brief hash for const char *
91 template<>
92 struct cnc_hash< char * >
93 {
94  size_t operator()( const char * x ) const
95  {
96  // suggested by Paul Larson of Microsoft Research
97  size_t _n = 0;
98  while ( *x ) {
99  _n = _n * 101 + *x;
100  ++x;
101  }
102  return _n;
103  }
104 };
105 
106 // \brief equality for const char *
107 template<>
108 struct cnc_equal< char * >
109 {
110  bool operator()( const char * x, const char * y ) const
111  {
112  return ( strcmp( x, y ) == 0 );
113  }
114 };
115 
116 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
117 
118 /// \brief hash for std::string
119 template<>
120 struct cnc_hash< std::string >
121 {
122  size_t operator()( const std::string & x ) const
123  {
124  // suggested by Paul Larson of Microsoft Research
125  size_t _n = 0;
126  for( std::string::const_iterator i = x.begin(); i != x.end(); ++ i ) {
127  _n = _n * 101 + *i;
128  }
129  return _n;
130  }
131 };
132 
133 /// \brief equality for std::string
134 template<>
135 struct cnc_equal< std::string >
136 {
137  bool operator()( const std::string & a, const std::string & b ) const
138  {
139  return ( a.compare( b ) == 0 );
140  }
141 };
142 
143 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
144 
145 // \brief hash/equality for std::vector
146 template< class T, class Allocator >
147 struct cnc_hash< std::vector< T, Allocator > >
148 {
149 public:
150  size_t operator()( const std::vector< T, Allocator > & x ) const
151  {
152  size_t _n = x.size();
153  CNC_ASSERT( _n > 0 );
154  cnc_hash< T > _hasher;
155  switch( _n ) {
156  case 0 : return 0;
157  case 1 : return _hasher.operator()( x[0] );
158  case 2 : return ( _hasher.operator()( x[0] )
159  + ( _hasher.operator()( x[1] ) << 10 ) );;
160  case 3 : return ( _hasher.operator()( x[0] )
161  + ( _hasher.operator()( x[1] ) << 9 )
162  + ( _hasher.operator()( x[2] ) << 18 ) );
163  case 4 : return ( _hasher.operator()( x[0] )
164  + ( _hasher.operator()( x[3] ) << 8 )
165  + ( _hasher.operator()( x[1] ) << 16 )
166  + ( _hasher.operator()( x[2] ) << 24 ) );
167  default : {
168  size_t _n = 0;
169  for( typename std::vector< T, Allocator >::const_iterator i = x.begin(); i != x.end(); ++ i ) {
170  _n = _n * 3 + _hasher.operator()( *i );
171  }
172  return _n;
173  }
174  }
175  }
176 };
177 
178 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
179 // %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
180 
181 
182 /// \brief Provides hash and equality operators for hashing as used by item_collections
183 ///
184 /// It is recommended to specilialize cnc_hash and/or cnc_equal rather than cnc_tag_hash_compare
185 template< class T >
186 struct cnc_tag_hash_compare : public cnc_hash< T >, public cnc_equal< T >
187 {
188  /// \return a unique integer for the given tag
189  size_t hash( const T & x ) const
190  {
191  return cnc_hash< T >::operator()( x );
192  }
193  /// \return true if a equals b, false otherwise
194  bool equal( const T & x, const T & y ) const
195  {
196  return cnc_equal< T >::operator()( x, y );
197  }
198 };
199 
200 #endif // _TAG_HASH_COMPARE_HH_ALREADY_INCLUDED
bool equal(const T &x, const T &y) const
Provides hash operators for hashing.
Provides hash and equality operators for hashing as used by item_collections.
Provides equality operators for hashing.
size_t hash(const T &x) const