---

KX_HashedString.h

Go to the documentation of this file.

00001 #ifndef __KX_HASHSTRING
00002 #define __KX_HASHSTRING
00003 
00004 #include "StdString.h"
00005 
00006 
00007 // Hash Mix utility function, by Bob Jenkins - Mix 3 32-bit values reversibly
00008 //
00009 // - If gHashMix() is run forward or backward, at least 32 bits in a,b,c have at
00010 //   least 1/4 probability of changing.
00011 //
00012 // - If gHashMix() is run forward, every bit of c will change between 1/3 and
00013 //   2/3 of the time.
00014 //
00015 static inline void gHashMix(dword& a, dword& b, dword& c)

00016 {
00017         a -= b; a -= c; a ^= (c>>13);
00018         b -= c; b -= a; b ^= (a<<8);
00019         c -= a; c -= b; c ^= (b>>13);
00020         a -= b; a -= c; a ^= (c>>12);
00021         b -= c; b -= a; b ^= (a<<16);
00022         c -= a; c -= b; c ^= (b>>5);
00023         a -= b; a -= c; a ^= (c>>3);
00024         b -= c; b -= a; b ^= (a<<10);
00025         c -= a; c -= b; c ^= (b>>15);
00026 }
00027 
00028 //
00029 // Fast Hashable<int32> functionality
00030 // http://www.concentric.net/~Ttwang/tech/inthash.htm
00031 //
00032 static inline dword                     gHash(dword inDWord)

00033 {
00034         dword key = inDWord;
00035         key += ~(key << 16);
00036         key ^=  (key >>  5);
00037         key +=  (key <<  3);
00038         key ^=  (key >> 13);
00039         key += ~(key <<  9);
00040         key ^=  (key >> 17);
00041         return key;
00042 }
00043 
00044 enum { GOLDEN_RATIO = 0x9e3779b9 }; // arbitrary value to initialize hash funtion, well not so arbitrary
00045                                                                         // as this value is taken from the pigs library (Orange Games/Lost Boys)
00046 
00047 
00048 
00049 static dword gHash(const void* in, int len, dword init_val)

00050 {
00051         unsigned int  length = len;
00052         dword a = (dword)GOLDEN_RATIO;
00053         dword b = (dword)GOLDEN_RATIO;
00054         dword c = init_val;                                                                                                                     // the previous hash value
00055         byte  *p_in = (byte *)in;
00056 
00057         // Do the largest part of the key
00058         while (length >= 12)
00059         {
00060                 a += (p_in[0] + ((dword)p_in[1]<<8) + ((dword)p_in[2] <<16) + ((dword)p_in[3] <<24));
00061                 b += (p_in[4] + ((dword)p_in[5]<<8) + ((dword)p_in[6] <<16) + ((dword)p_in[7] <<24));
00062                 c += (p_in[8] + ((dword)p_in[9]<<8) + ((dword)p_in[10]<<16) + ((dword)p_in[11]<<24));
00063                 gHashMix(a, b, c);
00064                 p_in += 12; length -= 12;
00065         }
00066 
00067         // Handle the last 11 bytes
00068         c += len;
00069         switch(length) {
00070         case 11: c+=((dword)p_in[10]<<24);
00071         case 10: c+=((dword)p_in[9]<<16);
00072         case 9 : c+=((dword)p_in[8]<<8);                                                                                        // the first byte of c is reserved for the length
00073         case 8 : b+=((dword)p_in[7]<<24);
00074         case 7 : b+=((dword)p_in[6]<<16);
00075         case 6 : b+=((dword)p_in[5]<<8);
00076         case 5 : b+=p_in[4];
00077         case 4 : a+=((dword)p_in[3]<<24);
00078         case 3 : a+=((dword)p_in[2]<<16);
00079         case 2 : a+=((dword)p_in[1]<<8);
00080         case 1 : a+=p_in[0];
00081         }
00082         gHashMix(a, b, c);
00083 
00084         return c;
00085 }
00086 
00087 
00088 
00089 
00090 class KX_HashedString : public CCString
00091 {
00092 public:
00093         KX_HashedString()       : m_Hashed(false),CCString() {}
00094         KX_HashedString(const char* str)        : m_Hashed(false),CCString(str) {}
00095         KX_HashedString(const CCString & str) : m_Hashed(false),CCString(str) {}
00096 
00097         inline dword hash(dword init=0) const 

00098         { 
00099                 if (!m_Hashed) 
00100                 {
00101                         const char* str = *this;
00102                         int length = this->Length();
00103                         m_CachedHash = gHash(str,length,init);
00104                         m_Hashed=true;
00105                 } 
00106                 return m_CachedHash;
00107         }
00108 
00109 private:
00110         mutable bool m_Hashed;
00111         mutable dword m_CachedHash;
00112 };
00113 
00114 #endif //__KX_HASHSTRING
00115 

---