PolyBoRi
|
00001 // -*- c++ -*- 00002 //***************************************************************************** 00051 //***************************************************************************** 00052 00053 #ifndef generic_hash_h_ 00054 #define generic_hash_h_ 00055 00061 00062 00063 class generic_hash_tags { 00064 public: 00065 struct simple_tag {}; 00066 struct js_tag {}; 00067 struct pjw_tag {}; 00068 struct elf_tag {}; 00069 struct bkdr_tag {}; 00070 struct sdbm_tag {}; 00071 struct djb_tag {}; 00072 struct dek_tag {}; 00073 typedef dek_tag knuth_tag; 00074 00075 typedef simple_tag default_tag; 00076 }; 00077 00078 template <class Iterator, class HashType, class UnaryOp> 00079 HashType 00080 generic_hash_function(Iterator start, Iterator finish, HashType sum, 00081 generic_hash_tags::simple_tag, UnaryOp op) { 00082 00083 HashType vars = 0; 00084 sum = 0; 00085 00086 while (start != finish){ 00087 vars++; 00088 sum += ((op(*start))+1) * ((op(*start))+1); 00089 ++start; 00090 } 00091 return sum * vars; 00092 } 00093 00094 00095 template <class Iterator, class HashType, class UnaryOp> 00096 HashType 00097 generic_hash_function(Iterator start, Iterator finish, HashType hash, 00098 generic_hash_tags::js_tag, UnaryOp op) { 00099 00100 hash = 1315423911; 00101 00102 while (start != finish) { 00103 hash ^= ((hash << 5) + op(*start) + (hash >> 2)); 00104 ++start; 00105 } 00106 00107 return hash; 00108 } 00109 00110 template <class Iterator, class HashType, class UnaryOp> 00111 HashType 00112 generic_hash_function(Iterator start, Iterator finish, HashType hash, 00113 generic_hash_tags::pjw_tag, UnaryOp op) { 00114 00115 const HashType nBits = (HashType)(sizeof(HashType) * 8); 00116 const HashType nTimes3Div4 = (HashType)((nBits * 3) / 4); 00117 const HashType nDiv8 = (HashType)(nBits / 8); 00118 const HashType BitMaskHigh = (HashType)(0xFFFFFFFF) << (nBits - nDiv8); 00119 00120 hash = 0; 00121 HashType test = 0; 00122 00123 while (start != finish) { 00124 hash = (hash << nDiv8) + op(*start); 00125 00126 if((test = hash & BitMaskHigh) != 0) { 00127 hash = (( hash ^ (test >> nTimes3Div4)) & (~BitMaskHigh)); 00128 } 00129 ++start; 00130 } 00131 00132 return hash; 00133 } 00134 00135 00136 template <class Iterator, class HashType, class UnaryOp> 00137 HashType 00138 generic_hash_function(Iterator start, Iterator finish, HashType hash, 00139 generic_hash_tags::elf_tag, UnaryOp op) { 00140 00141 hash = 0; 00142 HashType tmp = 0; 00143 00144 while (start != finish) { 00145 hash = (hash << 4) + op(*start); 00146 if((tmp = hash & 0xF0000000L) != 0) { 00147 hash ^= (tmp >> 24); 00148 hash &= ~tmp; 00149 } 00150 ++start; 00151 } 00152 return hash; 00153 } 00154 00155 template <class Iterator, class HashType, class UnaryOp> 00156 HashType 00157 generic_hash_function(Iterator start, Iterator finish, HashType hash, 00158 generic_hash_tags::bkdr_tag, UnaryOp op) { 00159 00160 HashType magic_number = 131; 00161 hash = 0; 00162 00163 while (start != finish) { 00164 hash = (hash * magic_number) + op(*start); 00165 ++start; 00166 } 00167 00168 return hash; 00169 } 00170 template <class Iterator, class HashType, class UnaryOp> 00171 HashType 00172 generic_hash_function(Iterator start, Iterator finish, HashType hash, 00173 generic_hash_tags::sdbm_tag, UnaryOp op) { 00174 00175 hash = 0; 00176 00177 while (start != finish) { 00178 hash = op(*start) + (hash << 6) + (hash << 16) - hash; 00179 ++start; 00180 } 00181 00182 return hash; 00183 } 00184 00185 template <class Iterator, class HashType, class UnaryOp> 00186 HashType 00187 generic_hash_function(Iterator start, Iterator finish, HashType hash, 00188 generic_hash_tags::djb_tag, UnaryOp op) { 00189 00190 hash = 5381; 00191 00192 while (start != finish) { 00193 hash = ((hash << 5) + hash) + op(*start); 00194 ++start; 00195 } 00196 00197 return hash; 00198 } 00199 00200 template <class Iterator, class HashType, class UnaryOp> 00201 HashType 00202 generic_hash_function(Iterator start, Iterator finish, HashType hash, 00203 generic_hash_tags::dek_tag, UnaryOp op) { 00204 00205 00206 hash = static_cast<HashType>(std::distance(start, finish)); 00207 00208 while (start != finish) { 00209 hash = ((hash << 5) ^ (hash >> 27)) ^ op(*start); 00210 ++start; 00211 } 00212 00213 return hash; 00214 } 00215 00216 00217 class simple_identity { 00218 public: 00219 template <class ValueType> 00220 ValueType& operator()(ValueType& val) const { return val; } 00221 00222 template <class ValueType> 00223 const ValueType& operator()(const ValueType& val) const { return val; } 00224 }; 00225 00226 class simple_increment { 00227 public: 00228 00229 template <class ValueType> 00230 ValueType operator()(ValueType val) const { return ++val; } 00231 }; 00232 00233 template <class Iterator, class HashType, class HashTag> 00234 HashType 00235 generic_hash_function(Iterator start, Iterator finish, HashType init, 00236 HashTag tag) { 00237 00238 return generic_hash_function(start, finish, init, tag, simple_identity()); 00239 } 00240 00241 00242 template <class Iterator, class HashType, 00243 class AlgTag, HashType BitMask = 0x7FFFFFFF> 00244 class generic_sequence_hash: 00245 public generic_hash_tags { 00246 00247 public: 00248 typedef Iterator iterator_type; 00249 typedef HashType hash_type; 00250 typedef AlgTag alg_tag; 00251 enum { mask = BitMask }; 00252 00253 hash_type operator()(iterator_type start, iterator_type finish) const { 00254 hash_type hash = 0; 00255 hash = generic_hash_function(start, finish, hash, alg_tag(), 00256 simple_increment() ); 00257 return (--hash & mask); 00258 } 00259 }; 00260 00261 template <class VectorType, class HashType, 00262 class AlgTag, HashType BitMask = 0x7FFFFFFF> 00263 class generic_hash: 00264 public generic_hash_tags { 00265 public: 00266 typedef VectorType vector_type; 00267 typedef typename vector_type::const_iterator const_iterator; 00268 typedef HashType hash_type; 00269 typedef AlgTag alg_tag; 00270 enum { mask = BitMask }; 00271 00272 hash_type operator()(const vector_type& vec) const { 00273 return hash_op(vec.begin(), vec.end()); 00274 } 00275 protected: 00276 generic_sequence_hash<const_iterator, hash_type, alg_tag, mask> hash_op; 00277 }; 00278 00279 #endif