PolyBoRi
generic_hash.h
Go to the documentation of this file.
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