PolyBoRi
generic_hash.h
Go to the documentation of this file.
1 // -*- c++ -*-
2 //*****************************************************************************
51 //*****************************************************************************
52 
53 #ifndef generic_hash_h_
54 #define generic_hash_h_
55 
61 
62 
64 public:
65  struct simple_tag {};
66  struct js_tag {};
67  struct pjw_tag {};
68  struct elf_tag {};
69  struct bkdr_tag {};
70  struct sdbm_tag {};
71  struct djb_tag {};
72  struct dek_tag {};
73  typedef dek_tag knuth_tag;
74 
76 };
77 
78 template <class Iterator, class HashType, class UnaryOp>
79 HashType
80 generic_hash_function(Iterator start, Iterator finish, HashType sum,
81  generic_hash_tags::simple_tag, UnaryOp op) {
82 
83  HashType vars = 0;
84  sum = 0;
85 
86  while (start != finish){
87  vars++;
88  sum += ((op(*start))+1) * ((op(*start))+1);
89  ++start;
90  }
91  return sum * vars;
92 }
93 
94 
95 template <class Iterator, class HashType, class UnaryOp>
96 HashType
97 generic_hash_function(Iterator start, Iterator finish, HashType hash,
98  generic_hash_tags::js_tag, UnaryOp op) {
99 
100  hash = 1315423911;
101 
102  while (start != finish) {
103  hash ^= ((hash << 5) + op(*start) + (hash >> 2));
104  ++start;
105  }
106 
107  return hash;
108 }
109 
110 template <class Iterator, class HashType, class UnaryOp>
111 HashType
112 generic_hash_function(Iterator start, Iterator finish, HashType hash,
113  generic_hash_tags::pjw_tag, UnaryOp op) {
114 
115  const HashType nBits = (HashType)(sizeof(HashType) * 8);
116  const HashType nTimes3Div4 = (HashType)((nBits * 3) / 4);
117  const HashType nDiv8 = (HashType)(nBits / 8);
118  const HashType BitMaskHigh = (HashType)(0xFFFFFFFF) << (nBits - nDiv8);
119 
120  hash = 0;
121  HashType test = 0;
122 
123  while (start != finish) {
124  hash = (hash << nDiv8) + op(*start);
125 
126  if((test = hash & BitMaskHigh) != 0) {
127  hash = (( hash ^ (test >> nTimes3Div4)) & (~BitMaskHigh));
128  }
129  ++start;
130  }
131 
132  return hash;
133 }
134 
135 
136 template <class Iterator, class HashType, class UnaryOp>
137 HashType
138 generic_hash_function(Iterator start, Iterator finish, HashType hash,
139  generic_hash_tags::elf_tag, UnaryOp op) {
140 
141  hash = 0;
142  HashType tmp = 0;
143 
144  while (start != finish) {
145  hash = (hash << 4) + op(*start);
146  if((tmp = hash & 0xF0000000L) != 0) {
147  hash ^= (tmp >> 24);
148  hash &= ~tmp;
149  }
150  ++start;
151  }
152  return hash;
153 }
154 
155 template <class Iterator, class HashType, class UnaryOp>
156 HashType
157 generic_hash_function(Iterator start, Iterator finish, HashType hash,
158  generic_hash_tags::bkdr_tag, UnaryOp op) {
159 
160  HashType magic_number = 131;
161  hash = 0;
162 
163  while (start != finish) {
164  hash = (hash * magic_number) + op(*start);
165  ++start;
166  }
167 
168  return hash;
169 }
170 template <class Iterator, class HashType, class UnaryOp>
171 HashType
172 generic_hash_function(Iterator start, Iterator finish, HashType hash,
173  generic_hash_tags::sdbm_tag, UnaryOp op) {
174 
175  hash = 0;
176 
177  while (start != finish) {
178  hash = op(*start) + (hash << 6) + (hash << 16) - hash;
179  ++start;
180  }
181 
182  return hash;
183 }
184 
185 template <class Iterator, class HashType, class UnaryOp>
186 HashType
187 generic_hash_function(Iterator start, Iterator finish, HashType hash,
188  generic_hash_tags::djb_tag, UnaryOp op) {
189 
190  hash = 5381;
191 
192  while (start != finish) {
193  hash = ((hash << 5) + hash) + op(*start);
194  ++start;
195  }
196 
197  return hash;
198 }
199 
200 template <class Iterator, class HashType, class UnaryOp>
201 HashType
202 generic_hash_function(Iterator start, Iterator finish, HashType hash,
203  generic_hash_tags::dek_tag, UnaryOp op) {
204 
205 
206  hash = static_cast<HashType>(std::distance(start, finish));
207 
208  while (start != finish) {
209  hash = ((hash << 5) ^ (hash >> 27)) ^ op(*start);
210  ++start;
211  }
212 
213  return hash;
214 }
215 
216 
218 public:
219  template <class ValueType>
220  ValueType& operator()(ValueType& val) const { return val; }
221 
222  template <class ValueType>
223  const ValueType& operator()(const ValueType& val) const { return val; }
224 };
225 
227 public:
228 
229  template <class ValueType>
230  ValueType operator()(ValueType val) const { return ++val; }
231 };
232 
233 template <class Iterator, class HashType, class HashTag>
234 HashType
235 generic_hash_function(Iterator start, Iterator finish, HashType init,
236  HashTag tag) {
237 
238  return generic_hash_function(start, finish, init, tag, simple_identity());
239 }
240 
241 
242 template <class Iterator, class HashType,
243  class AlgTag, HashType BitMask = 0x7FFFFFFF>
245  public generic_hash_tags {
246 
247 public:
248  typedef Iterator iterator_type;
249  typedef HashType hash_type;
250  typedef AlgTag alg_tag;
251  enum { mask = BitMask };
252 
254  hash_type hash = 0;
255  hash = generic_hash_function(start, finish, hash, alg_tag(),
256  simple_increment() );
257  return (--hash & mask);
258  }
259 };
260 
261 template <class VectorType, class HashType,
262  class AlgTag, HashType BitMask = 0x7FFFFFFF>
264  public generic_hash_tags {
265 public:
266  typedef VectorType vector_type;
267  typedef typename vector_type::const_iterator const_iterator;
268  typedef HashType hash_type;
269  typedef AlgTag alg_tag;
270  enum { mask = BitMask };
271 
272  hash_type operator()(const vector_type& vec) const {
273  return hash_op(vec.begin(), vec.end());
274  }
275 protected:
277 };
278 
279 #endif