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