intern/string/STR_HashedString.h

   1 /**
   2  * $Id$
   3  * ***** BEGIN GPL LICENSE BLOCK *****
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License
   7  * as published by the Free Software Foundation; either version 2
   8  * of the License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13  * GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software Foundation,
  17  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  18  *
  19  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
  20  * All rights reserved.
  21  *
  22  * The Original Code is: all of this file.
  23  *
  24  * Contributor(s): none yet.
  25  *
  26  * ***** END GPL LICENSE BLOCK *****
  27  */
  28
  29 /**
  30
  31  * $Id$
  32  * Copyright (C) 2001 NaN Technologies B.V.
  33  * This file was formerly known as: GEN_StdString.cpp.
  34  * @date        November, 14, 2001
  35  */
  36
  37 #ifndef __STR_HASHSTRING
  38 #define __STR_HASHSTRING
  39
  40 #include "STR_String.h"
  41
  42
  43 // Hash Mix utility function, by Bob Jenkins - Mix 3 32-bit values reversibly
  44 //
  45 // - If gHashMix() is run forward or backward, at least 32 bits in a,b,c have at
  46 //   least 1/4 probability of changing.
  47 //
  48 // - If gHashMix() is run forward, every bit of c will change between 1/3 and
  49 //   2/3 of the time.
  50 //
  51 static inline void STR_gHashMix(dword& a, dword& b, dword& c)
  52 {
  53         a -= b; a -= c; a ^= (c>>13);
  54         b -= c; b -= a; b ^= (a<<8);
  55         c -= a; c -= b; c ^= (b>>13);
  56         a -= b; a -= c; a ^= (c>>12);
  57         b -= c; b -= a; b ^= (a<<16);
  58         c -= a; c -= b; c ^= (b>>5);
  59         a -= b; a -= c; a ^= (c>>3);
  60         b -= c; b -= a; b ^= (a<<10);
  61         c -= a; c -= b; c ^= (b>>15);
  62 }
  63
  64 //
  65 // Fast Hashable<int32> functionality
  66 // http://www.concentric.net/~Ttwang/tech/inthash.htm
  67 //
  68 static inline dword                     STR_gHash(dword inDWord)
  69 {
  70         dword key = inDWord;
  71         key += ~(key << 16);
  72         key ^=  (key >>  5);
  73         key +=  (key <<  3);
  74         key ^=  (key >> 13);
  75         key += ~(key <<  9);
  76         key ^=  (key >> 17);
  77         return key;
  78 }
  79
  80 enum { GOLDEN_RATIO = 0x9e3779b9 }; // arbitrary value to initialize hash funtion, well not so arbitrary
  81                                                                         // as this value is taken from the pigs library (Orange Games/Lost Boys)
  82
  83
  84
  85 static dword STR_gHash(const void* in, int len, dword init_val)
  86 {
  87         unsigned int  length = len;
  88         dword a = (dword)GOLDEN_RATIO;
  89         dword b = (dword)GOLDEN_RATIO;
  90         dword c = init_val;                                                                                                                     // the previous hash value
  91         byte  *p_in = (byte *)in;
  92
  93         // Do the largest part of the key
  94         while (length >= 12)
  95         {
  96                 a += (p_in[0] + ((dword)p_in[1]<<8) + ((dword)p_in[2] <<16) + ((dword)p_in[3] <<24));
  97                 b += (p_in[4] + ((dword)p_in[5]<<8) + ((dword)p_in[6] <<16) + ((dword)p_in[7] <<24));
  98                 c += (p_in[8] + ((dword)p_in[9]<<8) + ((dword)p_in[10]<<16) + ((dword)p_in[11]<<24));
  99                 STR_gHashMix(a, b, c);
 100                 p_in += 12; length -= 12;
 101         }
 102
 103         // Handle the last 11 bytes
 104         c += len;
 105         switch(length) {
 106         case 11: c+=((dword)p_in[10]<<24);
 107         case 10: c+=((dword)p_in[9]<<16);
 108         case 9 : c+=((dword)p_in[8]<<8);                                                                                        // the first byte of c is reserved for the length
 109         case 8 : b+=((dword)p_in[7]<<24);
 110         case 7 : b+=((dword)p_in[6]<<16);
 111         case 6 : b+=((dword)p_in[5]<<8);
 112         case 5 : b+=p_in[4];
 113         case 4 : a+=((dword)p_in[3]<<24);
 114         case 3 : a+=((dword)p_in[2]<<16);
 115         case 2 : a+=((dword)p_in[1]<<8);
 116         case 1 : a+=p_in[0];
 117         }
 118         STR_gHashMix(a, b, c);
 119
 120         return c;
 121 }
 122
 123
 124
 125
 126 class STR_HashedString : public STR_String
 127 {
 128 public:
 129         STR_HashedString()      : STR_String(),m_Hashed(false) {}
 130         STR_HashedString(const char* str)       : STR_String(str),m_Hashed(false) {}
 131         STR_HashedString(const STR_String& str) : STR_String(str),m_Hashed(false) {}
 132
 133         inline dword hash(dword init=0) const
 134         {
 135                 if (!m_Hashed)
 136                 {
 137                         const char* str = *this;
 138                         int length = this->Length();
 139                         m_CachedHash = STR_gHash(str,length,init);
 140                         m_Hashed=true;
 141                 }
 142                 return m_CachedHash;
 143         }
 144
 145 private:
 146         mutable bool m_Hashed;
 147         mutable dword m_CachedHash;
 148 };
 149
 150 #endif //__STR_HASHSTRING
 151