/*
* Copyright (C) 2005, 2006, 2008, 2010 Apple Inc. All rights reserved.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library 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
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public License
* along with this library; see the file COPYING.LIB. If not, write to
* the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
* Boston, MA 02110-1301, USA.
*
*/
#ifndef WTF_StringHashFunctions_h
#define WTF_StringHashFunctions_h
#include
namespace WTF {
// Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
static const unsigned stringHashingStartValue = 0x9e3779b9U;
// stringHash methods based on Paul Hsieh's SuperFastHash.
// http://www.azillionmonkeys.com/qed/hash.html
// char* data is interpreted as latin-encoded (zero extended to 16 bits).
inline unsigned stringHash(const UChar* data, unsigned length)
{
unsigned hash = WTF::stringHashingStartValue;
unsigned rem = length & 1;
length >>= 1;
// Main loop
for (; length > 0; length--) {
hash += data[0];
unsigned tmp = (data[1] << 11) ^ hash;
hash = (hash << 16) ^ tmp;
data += 2;
hash += hash >> 11;
}
// Handle end case
if (rem) {
hash += data[0];
hash ^= hash << 11;
hash += hash >> 17;
}
// Force "avalanching" of final 127 bits
hash ^= hash << 3;
hash += hash >> 5;
hash ^= hash << 2;
hash += hash >> 15;
hash ^= hash << 10;
hash &= 0x7fffffff;
// this avoids ever returning a hash code of 0, since that is used to
// signal "hash not computed yet", using a value that is likely to be
// effectively the same as 0 when the low bits are masked
if (hash == 0)
hash = 0x40000000;
return hash;
}
inline unsigned stringHash(const char* data, unsigned length)
{
unsigned hash = WTF::stringHashingStartValue;
unsigned rem = length & 1;
length >>= 1;
// Main loop
for (; length > 0; length--) {
hash += static_cast(data[0]);
unsigned tmp = (static_cast(data[1]) << 11) ^ hash;
hash = (hash << 16) ^ tmp;
data += 2;
hash += hash >> 11;
}
// Handle end case
if (rem) {
hash += static_cast(data[0]);
hash ^= hash << 11;
hash += hash >> 17;
}
// Force "avalanching" of final 127 bits
hash ^= hash << 3;
hash += hash >> 5;
hash ^= hash << 2;
hash += hash >> 15;
hash ^= hash << 10;
hash &= 0x7fffffff;
// this avoids ever returning a hash code of 0, since that is used to
// signal "hash not computed yet", using a value that is likely to be
// effectively the same as 0 when the low bits are masked
if (hash == 0)
hash = 0x40000000;
return hash;
}
inline unsigned stringHash(const char* data)
{
unsigned hash = WTF::stringHashingStartValue;
// Main loop
for (;;) {
unsigned char b0 = data[0];
if (!b0)
break;
unsigned char b1 = data[1];
if (!b1) {
hash += b0;
hash ^= hash << 11;
hash += hash >> 17;
break;
}
hash += b0;
unsigned tmp = (b1 << 11) ^ hash;
hash = (hash << 16) ^ tmp;
data += 2;
hash += hash >> 11;
}
// Force "avalanching" of final 127 bits.
hash ^= hash << 3;
hash += hash >> 5;
hash ^= hash << 2;
hash += hash >> 15;
hash ^= hash << 10;
hash &= 0x7fffffff;
// This avoids ever returning a hash code of 0, since that is used to
// signal "hash not computed yet", using a value that is likely to be
// effectively the same as 0 when the low bits are masked.
if (hash == 0)
hash = 0x40000000;
return hash;
}
} // namespace WTF
#endif // WTF_StringHashFunctions_h