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