| /* |
| * 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 <wtf/unicode/Unicode.h> |
| |
| 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<unsigned char>(data[0]); |
| unsigned tmp = (static_cast<unsigned char>(data[1]) << 11) ^ hash; |
| hash = (hash << 16) ^ tmp; |
| data += 2; |
| hash += hash >> 11; |
| } |
| |
| // Handle end case |
| if (rem) { |
| hash += static_cast<unsigned char>(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 |