diff options
Diffstat (limited to 'intern/string/STR_HashedString.h')
-rw-r--r-- | intern/string/STR_HashedString.h | 150 |
1 files changed, 0 insertions, 150 deletions
diff --git a/intern/string/STR_HashedString.h b/intern/string/STR_HashedString.h deleted file mode 100644 index 4fffa51a37d..00000000000 --- a/intern/string/STR_HashedString.h +++ /dev/null @@ -1,150 +0,0 @@ -/* - * 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. - * - * 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. - * - * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV. - * All rights reserved. - */ - -/** \file string/STR_HashedString.h - * \ingroup string - * - * Copyright (C) 2001 NaN Technologies B.V. - * This file was formerly known as: GEN_StdString.cpp. - * \date November, 14, 2001 - */ - -#ifndef __STR_HASHEDSTRING_H__ -#define __STR_HASHEDSTRING_H__ - -#include "STR_String.h" - -/* copied from 'BLI_compiler_attrs.h' */ -/* Use to suppress '-Wimplicit-fallthrough' (in place of 'break'). */ -#if defined(__GNUC__) && (__GNUC__ >= 7) /* gcc7.0+ only */ -#define ATTR_FALLTHROUGH __attribute__((fallthrough)) -#else -#define ATTR_FALLTHROUGH ((void)0) -#endif - - -// 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); ATTR_FALLTHROUGH; - case 10: c += ((dword)p_in[9] << 16); ATTR_FALLTHROUGH; - case 9: c += ((dword)p_in[8] << 8); ATTR_FALLTHROUGH; /* the first byte of c is reserved for the length */ - case 8: b += ((dword)p_in[7] << 24); ATTR_FALLTHROUGH; - case 7: b += ((dword)p_in[6] << 16); ATTR_FALLTHROUGH; - case 6: b += ((dword)p_in[5] << 8); ATTR_FALLTHROUGH; - case 5: b += p_in[4]; ATTR_FALLTHROUGH; - case 4: a += ((dword)p_in[3] << 24); ATTR_FALLTHROUGH; - case 3: a += ((dword)p_in[2] << 16); ATTR_FALLTHROUGH; - case 2: a += ((dword)p_in[1] << 8); ATTR_FALLTHROUGH; - 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_HASHEDSTRING_H__ - |