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