Logo Search packages:      
Sourcecode: blender version File versions

STR_HashedString.h

/**
 * $Id: STR_HashedString.h,v 1.4 2002/12/26 18:25:17 mein Exp $
 * ***** BEGIN GPL/BL DUAL LICENSE BLOCK *****
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * as published by the Free Software Foundation; either version 2
 * of the License, or (at your option) any later version. The Blender
 * Foundation also sells licenses for use in proprietary software under
 * the Blender License.  See http://www.blender.org/BL/ for information
 * about this.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software Foundation,
 * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
 *
 * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
 * All rights reserved.
 *
 * The Original Code is: all of this file.
 *
 * Contributor(s): none yet.
 *
 * ***** END GPL/BL DUAL LICENSE BLOCK *****
 */

/**

 * $Id: STR_HashedString.h,v 1.4 2002/12/26 18:25:17 mein Exp $
 * Copyright (C) 2001 NaN Technologies B.V.
 * This file was formerly known as: GEN_StdString.cpp.
 * @date    November, 14, 2001
 */

#ifndef __STR_HASHSTRING
#define __STR_HASHSTRING

#include "STR_String.h"


// Hash Mix utility function, by Bob Jenkins - Mix 3 32-bit values reversibly
//
// - If gHashMix() is run forward or backward, at least 32 bits in a,b,c have at
//   least 1/4 probability of changing.
//
// - If gHashMix() is run forward, every bit of c will change between 1/3 and
//   2/3 of the time.
//
static inline void STR_gHashMix(dword& a, dword& b, dword& c)
{
      a -= b; a -= c; a ^= (c>>13);
      b -= c; b -= a; b ^= (a<<8);
      c -= a; c -= b; c ^= (b>>13);
      a -= b; a -= c; a ^= (c>>12);
      b -= c; b -= a; b ^= (a<<16);
      c -= a; c -= b; c ^= (b>>5);
      a -= b; a -= c; a ^= (c>>3);
      b -= c; b -= a; b ^= (a<<10);
      c -= a; c -= b; c ^= (b>>15);
}

//
// Fast Hashable<int32> functionality
// http://www.concentric.net/~Ttwang/tech/inthash.htm
//
static inline dword                 STR_gHash(dword inDWord)
{
      dword key = inDWord;
      key += ~(key << 16);
      key ^=  (key >>  5);
      key +=  (key <<  3);
      key ^=  (key >> 13);
      key += ~(key <<  9);
      key ^=  (key >> 17);
      return key;
}

enum { GOLDEN_RATIO = 0x9e3779b9 }; // arbitrary value to initialize hash funtion, well not so arbitrary
                                                      // as this value is taken from the pigs library (Orange Games/Lost Boys)



static dword STR_gHash(const void* in, int len, dword init_val)
{
      unsigned int  length = len;
      dword a = (dword)GOLDEN_RATIO;
      dword b = (dword)GOLDEN_RATIO;
      dword c = init_val;                                                                                         // the previous hash value
      byte  *p_in = (byte *)in;

      // Do the largest part of the key
      while (length >= 12)
      {
            a += (p_in[0] + ((dword)p_in[1]<<8) + ((dword)p_in[2] <<16) + ((dword)p_in[3] <<24));
            b += (p_in[4] + ((dword)p_in[5]<<8) + ((dword)p_in[6] <<16) + ((dword)p_in[7] <<24));
            c += (p_in[8] + ((dword)p_in[9]<<8) + ((dword)p_in[10]<<16) + ((dword)p_in[11]<<24));
            STR_gHashMix(a, b, c);
            p_in += 12; length -= 12;
      }

      // Handle the last 11 bytes
      c += len;
      switch(length) {
      case 11: c+=((dword)p_in[10]<<24);
      case 10: c+=((dword)p_in[9]<<16);
      case 9 : c+=((dword)p_in[8]<<8);                                                                // the first byte of c is reserved for the length
      case 8 : b+=((dword)p_in[7]<<24);
      case 7 : b+=((dword)p_in[6]<<16);
      case 6 : b+=((dword)p_in[5]<<8);
      case 5 : b+=p_in[4];
      case 4 : a+=((dword)p_in[3]<<24);
      case 3 : a+=((dword)p_in[2]<<16);
      case 2 : a+=((dword)p_in[1]<<8);
      case 1 : a+=p_in[0];
      }
      STR_gHashMix(a, b, c);

      return c;
}




class STR_HashedString : public STR_String
{
public:
      STR_HashedString()      : STR_String(),m_Hashed(false) {}
      STR_HashedString(const char* str)   : STR_String(str),m_Hashed(false) {}
      STR_HashedString(const STR_String& str) : STR_String(str),m_Hashed(false) {}

      inline dword hash(dword init=0) const
      { 
            if (!m_Hashed) 
            {
                  const char* str = *this;
                  int length = this->Length();
                  m_CachedHash = STR_gHash(str,length,init);
                  m_Hashed=true;
            } 
            return m_CachedHash;
      }

private:
      mutable bool m_Hashed;
      mutable dword m_CachedHash;
};

#endif //__STR_HASHSTRING


Generated by  Doxygen 1.6.0   Back to index