source: webkit/trunk/JavaScriptCore/wtf/StringHashFunctions.h@ 65104

Last change on this file since 65104 was 53456, checked in by [email protected], 15 years ago

Revert r53454, since it causes much sadness in this world.

Patch by Gavin Barraclough <​[email protected]> on 2010-01-18
Reviewed by NOBODY (build fix).

  • runtime/UString.cpp:

(JSC::UString::spliceSubstringsWithSeparators):
(JSC::UString::replaceRange):

  • runtime/UStringImpl.cpp:

(JSC::UStringImpl::baseSharedBuffer):
(JSC::UStringImpl::sharedBuffer):
(JSC::UStringImpl::~UStringImpl):

  • runtime/UStringImpl.h:

(JSC::UntypedPtrAndBitfield::UntypedPtrAndBitfield):
(JSC::UntypedPtrAndBitfield::asPtr):
(JSC::UntypedPtrAndBitfield::operator&=):
(JSC::UntypedPtrAndBitfield::operator|=):
(JSC::UntypedPtrAndBitfield::operator&):
(JSC::UStringImpl::create):
(JSC::UStringImpl::cost):
(JSC::UStringImpl::isIdentifier):
(JSC::UStringImpl::setIsIdentifier):
(JSC::UStringImpl::ref):
(JSC::UStringImpl::deref):
(JSC::UStringImpl::checkConsistency):
(JSC::UStringImpl::UStringImpl):
(JSC::UStringImpl::bufferOwnerString):
(JSC::UStringImpl::bufferOwnership):
(JSC::UStringImpl::isStatic):

  • wtf/StringHashFunctions.h:

(WTF::stringHash):
File size: 4.3 KB
Line 
1/*
2 * Copyright (C) 2005, 2006, 2008, 2010 Apple Inc. All rights reserved.
3 *
4 * This library is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Library General Public
6 * License as published by the Free Software Foundation; either
7 * version 2 of the License, or (at your option) any later version.
8 *
9 * This library is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
12 * Library General Public License for more details.
13 *
14 * You should have received a copy of the GNU Library General Public License
15 * along with this library; see the file COPYING.LIB. If not, write to
16 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17 * Boston, MA 02110-1301, USA.
18 *
19 */
20#ifndef WTF_StringHashFunctions_h
21#define WTF_StringHashFunctions_h
22
23#include <wtf/unicode/Unicode.h>
24
25namespace WTF {
26
27// Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
28static const unsigned stringHashingStartValue = 0x9e3779b9U;
29
30// stringHash methods based on Paul Hsieh's SuperFastHash.
31// http://www.azillionmonkeys.com/qed/hash.html
32// char* data is interpreted as latin-encoded (zero extended to 16 bits).
33
34inline unsigned stringHash(const UChar* data, unsigned length)
35{
36 unsigned hash = WTF::stringHashingStartValue;
37 unsigned rem = length & 1;
38 length >>= 1;
39
40 // Main loop
41 for (; length > 0; length--) {
42 hash += data[0];
43 unsigned tmp = (data[1] << 11) ^ hash;
44 hash = (hash << 16) ^ tmp;
45 data += 2;
46 hash += hash >> 11;
47 }
48
49 // Handle end case
50 if (rem) {
51 hash += data[0];
52 hash ^= hash << 11;
53 hash += hash >> 17;
54 }
55
56 // Force "avalanching" of final 127 bits
57 hash ^= hash << 3;
58 hash += hash >> 5;
59 hash ^= hash << 2;
60 hash += hash >> 15;
61 hash ^= hash << 10;
62
63 hash &= 0x7fffffff;
64
65 // this avoids ever returning a hash code of 0, since that is used to
66 // signal "hash not computed yet", using a value that is likely to be
67 // effectively the same as 0 when the low bits are masked
68 if (hash == 0)
69 hash = 0x40000000;
70
71 return hash;
72}
73
74inline unsigned stringHash(const char* data, unsigned length)
75{
76 unsigned hash = WTF::stringHashingStartValue;
77 unsigned rem = length & 1;
78 length >>= 1;
79
80 // Main loop
81 for (; length > 0; length--) {
82 hash += static_cast<unsigned char>(data[0]);
83 unsigned tmp = (static_cast<unsigned char>(data[1]) << 11) ^ hash;
84 hash = (hash << 16) ^ tmp;
85 data += 2;
86 hash += hash >> 11;
87 }
88
89 // Handle end case
90 if (rem) {
91 hash += static_cast<unsigned char>(data[0]);
92 hash ^= hash << 11;
93 hash += hash >> 17;
94 }
95
96 // Force "avalanching" of final 127 bits
97 hash ^= hash << 3;
98 hash += hash >> 5;
99 hash ^= hash << 2;
100 hash += hash >> 15;
101 hash ^= hash << 10;
102
103 hash &= 0x7fffffff;
104
105 // this avoids ever returning a hash code of 0, since that is used to
106 // signal "hash not computed yet", using a value that is likely to be
107 // effectively the same as 0 when the low bits are masked
108 if (hash == 0)
109 hash = 0x40000000;
110
111 return hash;
112}
113
114inline unsigned stringHash(const char* data)
115{
116 unsigned hash = WTF::stringHashingStartValue;
117
118 // Main loop
119 for (;;) {
120 unsigned char b0 = data[0];
121 if (!b0)
122 break;
123 unsigned char b1 = data[1];
124 if (!b1) {
125 hash += b0;
126 hash ^= hash << 11;
127 hash += hash >> 17;
128 break;
129 }
130 hash += b0;
131 unsigned tmp = (b1 << 11) ^ hash;
132 hash = (hash << 16) ^ tmp;
133 data += 2;
134 hash += hash >> 11;
135 }
136
137 // Force "avalanching" of final 127 bits.
138 hash ^= hash << 3;
139 hash += hash >> 5;
140 hash ^= hash << 2;
141 hash += hash >> 15;
142 hash ^= hash << 10;
143
144 hash &= 0x7fffffff;
145
146 // This avoids ever returning a hash code of 0, since that is used to
147 // signal "hash not computed yet", using a value that is likely to be
148 // effectively the same as 0 when the low bits are masked.
149 if (hash == 0)
150 hash = 0x40000000;
151
152 return hash;
153}
154
155} // namespace WTF
156
157#endif // WTF_StringHashFunctions_h
Note: See TracBrowser for help on using the repository browser.