Blender V2.61 - r43446

STR_HashedString.h

Go to the documentation of this file.
00001 /*
00002  * ***** BEGIN GPL LICENSE BLOCK *****
00003  *
00004  * This program is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU General Public License
00006  * as published by the Free Software Foundation; either version 2
00007  * of the License, or (at your option) any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  * GNU General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software Foundation,
00016  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
00017  *
00018  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
00019  * All rights reserved.
00020  *
00021  * The Original Code is: all of this file.
00022  *
00023  * Contributor(s): none yet.
00024  *
00025  * ***** END GPL LICENSE BLOCK *****
00026  */
00027 
00040 #ifndef __STR_HASHSTRING
00041 #define __STR_HASHSTRING
00042 
00043 #include "STR_String.h"
00044 
00045 
00046 // Hash Mix utility function, by Bob Jenkins - Mix 3 32-bit values reversibly
00047 //
00048 // - If gHashMix() is run forward or backward, at least 32 bits in a,b,c have at
00049 //   least 1/4 probability of changing.
00050 //
00051 // - If gHashMix() is run forward, every bit of c will change between 1/3 and
00052 //   2/3 of the time.
00053 //
00054 static inline void STR_gHashMix(dword& a, dword& b, dword& c)
00055 {
00056     a -= b; a -= c; a ^= (c>>13);
00057     b -= c; b -= a; b ^= (a<<8);
00058     c -= a; c -= b; c ^= (b>>13);
00059     a -= b; a -= c; a ^= (c>>12);
00060     b -= c; b -= a; b ^= (a<<16);
00061     c -= a; c -= b; c ^= (b>>5);
00062     a -= b; a -= c; a ^= (c>>3);
00063     b -= c; b -= a; b ^= (a<<10);
00064     c -= a; c -= b; c ^= (b>>15);
00065 }
00066 
00067 //
00068 // Fast Hashable<int32> functionality
00069 // http://www.concentric.net/~Ttwang/tech/inthash.htm
00070 //
00071 static inline dword         STR_gHash(dword inDWord)
00072 {
00073     dword key = inDWord;
00074     key += ~(key << 16);
00075     key ^=  (key >>  5);
00076     key +=  (key <<  3);
00077     key ^=  (key >> 13);
00078     key += ~(key <<  9);
00079     key ^=  (key >> 17);
00080     return key;
00081 }
00082 
00083 enum { GOLDEN_RATIO = 0x9e3779b9 }; // arbitrary value to initialize hash funtion, well not so arbitrary
00084                                     // as this value is taken from the pigs library (Orange Games/Lost Boys)
00085 
00086 
00087 
00088 static dword STR_gHash(const void* in, int len, dword init_val)
00089 {
00090     unsigned int  length = len;
00091     dword a = (dword)GOLDEN_RATIO;
00092     dword b = (dword)GOLDEN_RATIO;
00093     dword c = init_val;                                                         // the previous hash value
00094     byte  *p_in = (byte *)in;
00095 
00096     // Do the largest part of the key
00097     while (length >= 12)
00098     {
00099         a += (p_in[0] + ((dword)p_in[1]<<8) + ((dword)p_in[2] <<16) + ((dword)p_in[3] <<24));
00100         b += (p_in[4] + ((dword)p_in[5]<<8) + ((dword)p_in[6] <<16) + ((dword)p_in[7] <<24));
00101         c += (p_in[8] + ((dword)p_in[9]<<8) + ((dword)p_in[10]<<16) + ((dword)p_in[11]<<24));
00102         STR_gHashMix(a, b, c);
00103         p_in += 12; length -= 12;
00104     }
00105 
00106     // Handle the last 11 bytes
00107     c += len;
00108     switch(length) {
00109     case 11: c+=((dword)p_in[10]<<24);
00110     case 10: c+=((dword)p_in[9]<<16);
00111     case 9 : c+=((dword)p_in[8]<<8);                                            // the first byte of c is reserved for the length
00112     case 8 : b+=((dword)p_in[7]<<24);
00113     case 7 : b+=((dword)p_in[6]<<16);
00114     case 6 : b+=((dword)p_in[5]<<8);
00115     case 5 : b+=p_in[4];
00116     case 4 : a+=((dword)p_in[3]<<24);
00117     case 3 : a+=((dword)p_in[2]<<16);
00118     case 2 : a+=((dword)p_in[1]<<8);
00119     case 1 : a+=p_in[0];
00120     }
00121     STR_gHashMix(a, b, c);
00122 
00123     return c;
00124 }
00125 
00126 
00127 
00128 
00129 class STR_HashedString : public STR_String
00130 {
00131 public:
00132     STR_HashedString()  : STR_String(),m_Hashed(false) {}
00133     STR_HashedString(const char* str)   : STR_String(str),m_Hashed(false) {}
00134     STR_HashedString(const STR_String& str) : STR_String(str),m_Hashed(false) {}
00135 
00136     inline dword hash(dword init=0) const
00137     { 
00138         if (!m_Hashed) 
00139         {
00140             const char* str = *this;
00141             int length = this->Length();
00142             m_CachedHash = STR_gHash(str,length,init);
00143             m_Hashed=true;
00144         } 
00145         return m_CachedHash;
00146     }
00147 
00148 private:
00149     mutable bool m_Hashed;
00150     mutable dword m_CachedHash;
00151 };
00152 
00153 #endif //__STR_HASHSTRING
00154