00001
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