libs/container/hashfunc.h

   1 /*
   2 Copyright (C) 2001-2006, William Joseph.
   3 All Rights Reserved.
   4
   5 This file is part of GtkRadiant.
   6
   7 GtkRadiant is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2 of the License, or
  10 (at your option) any later version.
  11
  12 GtkRadiant is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GtkRadiant; if not, write to the Free Software
  19 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
  20 */
  21
  22 #if !defined(INCLUDED_CONTAINER_HASHFUNC_H)
  23 #define INCLUDED_CONTAINER_HASHFUNC_H
  24
  25 #include <cctype>
  26 #include "string/string.h"
  27 #include "container/array.h"
  28 typedef  unsigned long  int  ub4;   /* unsigned 4-byte quantities */
  29 typedef  unsigned       char ub1;
  30
  31 inline ub1 ub1_as_ub1_nocase(ub1 byte)
  32 {
  33   return std::tolower(byte);
  34 }
  35
  36 inline ub4 ub1x4_as_ub4_nocase(const ub1 bytes[4])
  37 {
  38   ub4 result;
  39   reinterpret_cast<ub1*>(&result)[0] = ub1_as_ub1_nocase(bytes[0]);
  40   reinterpret_cast<ub1*>(&result)[1] = ub1_as_ub1_nocase(bytes[1]);
  41   reinterpret_cast<ub1*>(&result)[2] = ub1_as_ub1_nocase(bytes[2]);
  42   reinterpret_cast<ub1*>(&result)[3] = ub1_as_ub1_nocase(bytes[3]);
  43   return result;
  44 }
  45
  46 class ub1_default_traits
  47 {
  48 public:
  49   static ub1 as_ub1(ub1 byte)
  50   {
  51     return byte;
  52   }
  53 };
  54
  55 class ub1_nocase_traits
  56 {
  57 public:
  58   static ub1 as_ub1(ub1 byte)
  59   {
  60     return ub1_as_ub1_nocase(byte);
  61   }
  62 };
  63
  64 class ub1x4_default_traits
  65 {
  66 public:
  67   static ub4 as_ub4(const ub1 bytes[4])
  68   {
  69     return *reinterpret_cast<const ub4*>(bytes);
  70   }
  71 };
  72
  73 class ub1x4_nocase_traits
  74 {
  75 public:
  76   static ub4 as_ub4(const ub1 bytes[4])
  77   {
  78     return ub1x4_as_ub4_nocase(bytes);
  79   }
  80 };
  81
  82 class ub4_default_traits
  83 {
  84 public:
  85   static ub4 as_ub4(ub4 i)
  86   {
  87     return i;
  88   }
  89 };
  90
  91 class ub4_nocase_traits
  92 {
  93 public:
  94   static ub4 as_ub4(ub4 i)
  95   {
  96     return ub1x4_as_ub4_nocase(reinterpret_cast<const ub1*>(&i));
  97   }
  98 };
  99
 100 // lookup2.c
 101 // By Bob Jenkins, 1996.  bob_jenkins@burtleburtle.net.  You may use this
 102 // code any way you wish, private, educational, or commercial.  It's free.
 103
 104 #define hashsize(n) ((ub4)1<<(n))
 105 #define hashmask(n) (hashsize(n)-1)
 106
 107 /*
 108 --------------------------------------------------------------------
 109 mix -- mix 3 32-bit values reversibly.
 110 For every delta with one or two bit set, and the deltas of all three
 111   high bits or all three low bits, whether the original value of a,b,c
 112   is almost all zero or is uniformly distributed,
 113 * If mix() is run forward or backward, at least 32 bits in a,b,c
 114   have at least 1/4 probability of changing.
 115 * If mix() is run forward, every bit of c will change between 1/3 and
 116   2/3 of the time.  (Well, 22/100 and 78/100 for some 2-bit deltas.)
 117 mix() was built out of 36 single-cycle latency instructions in a
 118   structure that could supported 2x parallelism, like so:
 119       a -= b;
 120       a -= c; x = (c>>13);
 121       b -= c; a ^= x;
 122       b -= a; x = (a<<8);
 123       c -= a; b ^= x;
 124       c -= b; x = (b>>13);
 125       ...
 126   Unfortunately, superscalar Pentiums and Sparcs can't take advantage
 127   of that parallelism.  They've also turned some of those single-cycle
 128   latency instructions into multi-cycle latency instructions.  Still,
 129   this is the fastest good hash I could find.  There were about 2^^68
 130   to choose from.  I only looked at a billion or so.
 131 --------------------------------------------------------------------
 132 */
 133 #define mix(a,b,c) \
 134 { \
 135   a -= b; a -= c; a ^= (c>>13); \
 136   b -= c; b -= a; b ^= (a<<8); \
 137   c -= a; c -= b; c ^= (b>>13); \
 138   a -= b; a -= c; a ^= (c>>12);  \
 139   b -= c; b -= a; b ^= (a<<16); \
 140   c -= a; c -= b; c ^= (b>>5); \
 141   a -= b; a -= c; a ^= (c>>3);  \
 142   b -= c; b -= a; b ^= (a<<10); \
 143   c -= a; c -= b; c ^= (b>>15); \
 144 }
 145
 146 /* same, but slower, works on systems that might have 8 byte ub4's */
 147 #define mix2(a,b,c) \
 148 { \
 149   a -= b; a -= c; a ^= (c>>13); \
 150   b -= c; b -= a; b ^= (a<< 8); \
 151   c -= a; c -= b; c ^= ((b&0xffffffff)>>13); \
 152   a -= b; a -= c; a ^= ((c&0xffffffff)>>12); \
 153   b -= c; b -= a; b = (b ^ (a<<16)) & 0xffffffff; \
 154   c -= a; c -= b; c = (c ^ (b>> 5)) & 0xffffffff; \
 155   a -= b; a -= c; a = (a ^ (c>> 3)) & 0xffffffff; \
 156   b -= c; b -= a; b = (b ^ (a<<10)) & 0xffffffff; \
 157   c -= a; c -= b; c = (c ^ (b>>15)) & 0xffffffff; \
 158 }
 159
 160 /*
 161 --------------------------------------------------------------------
 162 hash() -- hash a variable-length key into a 32-bit value
 163   k     : the key (the unaligned variable-length array of bytes)
 164   len   : the length of the key, counting by bytes
 165   level : can be any 4-byte value
 166 Returns a 32-bit value.  Every bit of the key affects every bit of
 167 the return value.  Every 1-bit and 2-bit delta achieves avalanche.
 168 About 36+6len instructions.
 169
 170 The best hash table sizes are powers of 2.  There is no need to do
 171 mod a prime (mod is sooo slow!).  If you need less than 32 bits,
 172 use a bitmask.  For example, if you need only 10 bits, do
 173   h = (h & hashmask(10));
 174 In which case, the hash table should have hashsize(10) elements.
 175
 176 If you are hashing n strings (ub1 **)k, do it like this:
 177   for (i=0, h=0; i<n; ++i) h = hash( k[i], len[i], h);
 178
 179 See http://burlteburtle.net/bob/hash/evahash.html
 180 Use for hash table lookup, or anything where one collision in 2^32 is
 181 acceptable.  Do NOT use for cryptographic purposes.
 182 --------------------------------------------------------------------
 183 */
 184
 185 template<typename UB1Traits, typename UB4x1Traits>
 186 inline ub4 hash(
 187 const ub1 *k,        /* the key */
 188 ub4  length,   /* the length of the key */
 189 ub4  initval,    /* the previous hash, or an arbitrary value */
 190 const UB1Traits& ub1traits,
 191 const UB4x1Traits& ub4x1traits
 192 )
 193 {
 194    register ub4 a,b,c,len;
 195
 196    /* Set up the internal state */
 197    len = length;
 198    a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
 199    c = initval;           /* the previous hash value */
 200
 201    /*---------------------------------------- handle most of the key */
 202    while (len >= 12)
 203    {
 204       a += (k[0] +((ub4)UB1Traits::as_ub1(k[1])<<8) +((ub4)UB1Traits::as_ub1(k[2])<<16) +((ub4)UB1Traits::as_ub1(k[3])<<24));
 205       b += (k[4] +((ub4)UB1Traits::as_ub1(k[5])<<8) +((ub4)UB1Traits::as_ub1(k[6])<<16) +((ub4)UB1Traits::as_ub1(k[7])<<24));
 206       c += (k[8] +((ub4)UB1Traits::as_ub1(k[9])<<8) +((ub4)UB1Traits::as_ub1(k[10])<<16)+((ub4)UB1Traits::as_ub1(k[11])<<24));
 207       mix(a,b,c);
 208       k += 12; len -= 12;
 209    }
 210
 211    /*------------------------------------- handle the last 11 bytes */
 212    c += length;
 213    switch(len)              /* all the case statements fall through */
 214    {
 215    case 11: c += ((ub4)UB1Traits::as_ub1(k[10]) << 24);
 216    case 10: c += ((ub4)UB1Traits::as_ub1(k[9]) << 16);
 217    case 9 : c += ((ub4)UB1Traits::as_ub1(k[8]) << 8);
 218       /* the first byte of c is reserved for the length */
 219    case 8 : b += ((ub4)UB1Traits::as_ub1(k[7]) << 24);
 220    case 7 : b += ((ub4)UB1Traits::as_ub1(k[6]) << 16);
 221    case 6 : b += ((ub4)UB1Traits::as_ub1(k[5]) << 8);
 222    case 5 : b += UB1Traits::as_ub1(k[4]);
 223    case 4 : a += ((ub4)UB1Traits::as_ub1(k[3]) << 24);
 224    case 3 : a += ((ub4)UB1Traits::as_ub1(k[2]) << 16);
 225    case 2 : a += ((ub4)UB1Traits::as_ub1(k[1]) << 8);
 226    case 1 : a += UB1Traits::as_ub1(k[0]);
 227      /* case 0: nothing left to add */
 228    }
 229    mix(a,b,c);
 230    /*-------------------------------------------- report the result */
 231    return c;
 232 }
 233
 234 /*
 235 --------------------------------------------------------------------
 236  This works on all machines.  hash2() is identical to hash() on
 237  little-endian machines, except that the length has to be measured
 238  in ub4s instead of bytes.  It is much faster than hash().  It
 239  requires
 240  -- that the key be an array of ub4's, and
 241  -- that all your machines have the same endianness, and
 242  -- that the length be the number of ub4's in the key
 243 --------------------------------------------------------------------
 244 */
 245 template<typename UB4Traits>
 246 inline ub4 hash2(
 247 const ub4 *k,        /* the key */
 248 ub4  length,   /* the length of the key, in ub4s */
 249 ub4  initval, /* the previous hash, or an arbitrary value */
 250 const UB4Traits& ub4traits
 251 )
 252 {
 253    register ub4 a,b,c,len;
 254
 255    /* Set up the internal state */
 256    len = length;
 257    a = b = 0x9e3779b9;  /* the golden ratio; an arbitrary value */
 258    c = initval;           /* the previous hash value */
 259
 260    /*---------------------------------------- handle most of the key */
 261    while (len >= 3)
 262    {
 263      a += UB4Traits::as_ub4(k[0]);
 264      b += UB4Traits::as_ub4(k[1]);
 265      c += UB4Traits::as_ub4(k[2]);
 266      mix(a,b,c);
 267      k += 3; len -= 3;
 268    }
 269
 270    /*-------------------------------------- handle the last 2 ub4's */
 271    c += length;
 272    switch(len)              /* all the case statements fall through */
 273    {
 274      /* c is reserved for the length */
 275    case 2 : b += UB4Traits::as_ub4(k[1]);
 276    case 1 : a += UB4Traits::as_ub4(k[0]);
 277      /* case 0: nothing left to add */
 278    }
 279    mix(a,b,c);
 280    /*-------------------------------------------- report the result */
 281    return c;
 282 }
 283
 284 typedef ub4 hash_t;
 285
 286 inline hash_t hash_ub1(const ub1* key, std::size_t len, hash_t previous = 0)
 287 {
 288   return hash(key, ub4(len), previous, ub1_default_traits(), ub1x4_default_traits());
 289 }
 290
 291 inline hash_t hash_ub1_nocase(const ub1* key, std::size_t len, hash_t previous = 0)
 292 {
 293   return hash(key, ub4(len), previous, ub1_nocase_traits(), ub1x4_nocase_traits());
 294 }
 295
 296 template<typename UB4Traits>
 297 inline hash_t hash_ub4(const ub4* key, std::size_t len, const UB4Traits& traits, hash_t previous = 0)
 298 {
 299   return hash2(key,ub4(len), previous, traits);
 300 }
 301
 302 inline ub4 hash_combine(ub4 left, ub4 right)
 303 {
 304   return hash_ub1(reinterpret_cast<const ub1*>(&left), 4, right);
 305 }
 306
 307 template<typename POD>
 308 inline hash_t pod_hash(const POD& pod)
 309 {
 310   return hash_ub1(reinterpret_cast<const ub1*>(&pod), sizeof(POD));
 311 }
 312
 313 inline hash_t string_hash(const char* string, hash_t previous = 0)
 314 {
 315   return hash_ub1(reinterpret_cast<const ub1*>(string), string_length(string), previous);
 316 }
 317
 318 inline hash_t string_hash_nocase(const char* string, hash_t previous = 0)
 319 {
 320   return hash_ub1_nocase(reinterpret_cast<const ub1*>(string), string_length(string), previous);
 321 }
 322
 323 struct HashString
 324 {
 325   typedef hash_t hash_type;
 326   hash_type operator()(const CopiedString& string) const
 327   {
 328     return string_hash(string.c_str());
 329   }
 330 };
 331
 332 struct HashStringNoCase
 333 {
 334   typedef hash_t hash_type;
 335   hash_type operator()(const CopiedString& string) const
 336   {
 337     return string_hash_nocase(string.c_str());
 338   }
 339 };
 340
 341 /// \brief Length of a string in ub4.
 342 /// "wibble" (6) gives 2,
 343 /// "and" (3) gives 1,
 344 /// "bleh" (4) gives 2
 345 inline std::size_t string_length_ub4(const char* string)
 346 {
 347   return ((string_length(string)>>2)+1)<<2;
 348 }
 349
 350 /// \brief Hashable key type that stores a string as an array of ub4 - making hashing faster.
 351 /// Also caches the 32-bit result of the hash to speed up comparison of keys.
 352 template<typename UB4Traits = ub4_default_traits>
 353 class HashKey
 354 {
 355   Array<ub4> m_key;
 356   hash_t m_hash;
 357
 358   void copy(const HashKey& other)
 359   {
 360     std::copy(other.m_key.begin(), other.m_key.end(), m_key.begin());
 361     m_hash = other.m_hash;
 362   }
 363   void copy(const char* string)
 364   {
 365     strncpy(reinterpret_cast<char*>(m_key.data()), string, m_key.size());
 366     for(Array<ub4>::iterator i = m_key.begin(); i != m_key.end(); ++i)
 367     {
 368       *i = UB4Traits::as_ub4(*i);
 369     }
 370     m_hash = hash_ub4(m_key.data(), m_key.size(), ub4_default_traits());
 371   }
 372   bool equal(const HashKey& other) const
 373   {
 374     return m_hash == other.m_hash && m_key.size() == other.m_key.size()
 375       && std::equal(m_key.begin(), m_key.end(), other.m_key.begin());
 376   }
 377
 378 public:
 379   HashKey(const HashKey& other) : m_key(other.m_key.size())
 380   {
 381     copy(other);
 382   }
 383   HashKey(const char* string) : m_key(string_length_ub4(string))
 384   {
 385     copy(string);
 386   }
 387   HashKey& operator=(const char* string)
 388   {
 389     m_key.resize(string_length_ub4(string));
 390     copy(string);
 391     return *this;
 392   }
 393   bool operator==(const HashKey& other) const
 394   {
 395     return equal(other);
 396   }
 397   bool operator!=(const HashKey& other) const
 398   {
 399     return !equal(other);
 400   }
 401   hash_t hash() const
 402   {
 403     return m_hash;
 404   }
 405 #if 0
 406   const char* c_str() const
 407   {
 408     return reinterpret_cast<const char*>(m_key.data());
 409   }
 410 #endif
 411 };
 412
 413 /// \brief Hash function to use with HashKey.
 414 struct HashKeyHasher
 415 {
 416   typedef hash_t hash_type;
 417   hash_type operator()(const HashKey<ub4_default_traits>& key) const
 418   {
 419     return key.hash();
 420   }
 421 };
 422
 423
 424
 425 #endif