OLD | NEW |
1 /* | 1 /* |
2 * Copyright (C) 2006, 2007, 2008, 2012, 2013 Apple Inc. All rights reserved | 2 * Copyright (C) 2006, 2007, 2008, 2012, 2013 Apple Inc. All rights reserved |
3 * Copyright (C) Research In Motion Limited 2009. All rights reserved. | 3 * Copyright (C) Research In Motion Limited 2009. All rights reserved. |
4 * | 4 * |
5 * This library is free software; you can redistribute it and/or | 5 * This library is free software; you can redistribute it and/or |
6 * modify it under the terms of the GNU Library General Public | 6 * modify it under the terms of the GNU Library General Public |
7 * License as published by the Free Software Foundation; either | 7 * License as published by the Free Software Foundation; either |
8 * version 2 of the License, or (at your option) any later version. | 8 * version 2 of the License, or (at your option) any later version. |
9 * | 9 * |
10 * This library is distributed in the hope that it will be useful, | 10 * This library is distributed in the hope that it will be useful, |
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of | 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
13 * Library General Public License for more details. | 13 * Library General Public License for more details. |
14 * | 14 * |
15 * You should have received a copy of the GNU Library General Public License | 15 * You should have received a copy of the GNU Library General Public License |
16 * along with this library; see the file COPYING.LIB. If not, write to | 16 * along with this library; see the file COPYING.LIB. If not, write to |
17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, | 17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, |
18 * Boston, MA 02110-1301, USA. | 18 * Boston, MA 02110-1301, USA. |
19 * | 19 * |
20 */ | 20 */ |
21 | 21 |
22 #ifndef StringHash_h | 22 #ifndef StringHash_h |
23 #define StringHash_h | 23 #define StringHash_h |
24 | 24 |
25 #include "wtf/text/AtomicString.h" | |
26 #include "wtf/HashTraits.h" | 25 #include "wtf/HashTraits.h" |
27 #include "wtf/StringHasher.h" | 26 #include "wtf/StringHasher.h" |
| 27 #include "wtf/text/AtomicString.h" |
28 | 28 |
29 namespace WTF { | 29 namespace WTF { |
30 | 30 |
31 inline bool HashTraits<String>::isEmptyValue(const String& value) | 31 inline bool HashTraits<String>::isEmptyValue(const String& value) |
| 32 { |
| 33 return value.isNull(); |
| 34 } |
| 35 |
| 36 // The hash() functions on StringHash and CaseFoldingHash do not support null |
| 37 // strings. get(), contains(), and add() on HashMap<String,..., StringHash> |
| 38 // cause a null-pointer dereference when passed null strings. |
| 39 |
| 40 // FIXME: We should really figure out a way to put the computeHash function |
| 41 // that's currently a member function of StringImpl into this file so we can be |
| 42 // a little closer to having all the nearly-identical hash functions in one |
| 43 // place. |
| 44 |
| 45 struct StringHash { |
| 46 static unsigned hash(StringImpl* key) { return key->hash(); } |
| 47 static inline bool equal(const StringImpl* a, const StringImpl* b) |
32 { | 48 { |
33 return value.isNull(); | 49 return equalNonNull(a, b); |
34 } | 50 } |
35 | 51 |
36 // The hash() functions on StringHash and CaseFoldingHash do not support | 52 static unsigned hash(const RefPtr<StringImpl>& key) { return key->hash(); } |
37 // null strings. get(), contains(), and add() on HashMap<String,..., StringH
ash> | 53 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b) |
38 // cause a null-pointer dereference when passed null strings. | 54 { |
| 55 return equal(a.get(), b.get()); |
| 56 } |
39 | 57 |
40 // FIXME: We should really figure out a way to put the computeHash function
that's | 58 static unsigned hash(const String& key) { return key.impl()->hash(); } |
41 // currently a member function of StringImpl into this file so we can be a l
ittle | 59 static bool equal(const String& a, const String& b) |
42 // closer to having all the nearly-identical hash functions in one place. | 60 { |
| 61 return equal(a.impl(), b.impl()); |
| 62 } |
43 | 63 |
44 struct StringHash { | 64 static const bool safeToCompareToEmptyOrDeleted = false; |
45 static unsigned hash(StringImpl* key) { return key->hash(); } | 65 }; |
46 static inline bool equal(const StringImpl* a, const StringImpl* b) | |
47 { | |
48 return equalNonNull(a, b); | |
49 } | |
50 | 66 |
51 static unsigned hash(const RefPtr<StringImpl>& key) { return key->hash()
; } | 67 class CaseFoldingHash { |
52 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>&
b) | 68 public: |
53 { | 69 static unsigned hash(const UChar* data, unsigned length) |
54 return equal(a.get(), b.get()); | 70 { |
55 } | 71 return StringHasher::computeHashAndMaskTop8Bits<UChar, foldCase<UChar>>(
data, length); |
| 72 } |
56 | 73 |
57 static unsigned hash(const String& key) { return key.impl()->hash(); } | 74 static unsigned hash(StringImpl* str) |
58 static bool equal(const String& a, const String& b) | 75 { |
59 { | 76 if (str->is8Bit()) |
60 return equal(a.impl(), b.impl()); | 77 return hash(str->characters8(), str->length()); |
61 } | 78 return hash(str->characters16(), str->length()); |
| 79 } |
62 | 80 |
63 static const bool safeToCompareToEmptyOrDeleted = false; | 81 static unsigned hash(const LChar* data, unsigned length) |
64 }; | 82 { |
| 83 return StringHasher::computeHashAndMaskTop8Bits<LChar, foldCase<LChar>>(
data, length); |
| 84 } |
65 | 85 |
66 class CaseFoldingHash { | 86 static inline unsigned hash(const char* data, unsigned length) |
67 public: | 87 { |
68 static unsigned hash(const UChar* data, unsigned length) | 88 return CaseFoldingHash::hash(reinterpret_cast<const LChar*>(data), lengt
h); |
69 { | 89 } |
70 return StringHasher::computeHashAndMaskTop8Bits<UChar, foldCase<UCha
r>>(data, length); | |
71 } | |
72 | 90 |
73 static unsigned hash(StringImpl* str) | 91 static inline bool equal(const StringImpl* a, const StringImpl* b) |
74 { | 92 { |
75 if (str->is8Bit()) | 93 return equalIgnoringCaseNonNull(a, b); |
76 return hash(str->characters8(), str->length()); | 94 } |
77 return hash(str->characters16(), str->length()); | |
78 } | |
79 | 95 |
80 static unsigned hash(const LChar* data, unsigned length) | 96 static unsigned hash(const RefPtr<StringImpl>& key) |
81 { | 97 { |
82 return StringHasher::computeHashAndMaskTop8Bits<LChar, foldCase<LCha
r>>(data, length); | 98 return hash(key.get()); |
83 } | 99 } |
84 | 100 |
85 static inline unsigned hash(const char* data, unsigned length) | 101 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b) |
86 { | 102 { |
87 return CaseFoldingHash::hash(reinterpret_cast<const LChar*>(data), l
ength); | 103 return equal(a.get(), b.get()); |
88 } | 104 } |
89 | 105 |
90 static inline bool equal(const StringImpl* a, const StringImpl* b) | 106 static unsigned hash(const String& key) |
91 { | 107 { |
92 return equalIgnoringCaseNonNull(a, b); | 108 return hash(key.impl()); |
93 } | 109 } |
| 110 static unsigned hash(const AtomicString& key) |
| 111 { |
| 112 return hash(key.impl()); |
| 113 } |
| 114 static bool equal(const String& a, const String& b) |
| 115 { |
| 116 return equal(a.impl(), b.impl()); |
| 117 } |
| 118 static bool equal(const AtomicString& a, const AtomicString& b) |
| 119 { |
| 120 return (a == b) || equal(a.impl(), b.impl()); |
| 121 } |
94 | 122 |
95 static unsigned hash(const RefPtr<StringImpl>& key) | 123 static const bool safeToCompareToEmptyOrDeleted = false; |
96 { | |
97 return hash(key.get()); | |
98 } | |
99 | 124 |
100 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>&
b) | 125 private: |
101 { | 126 // Private so no one uses this in the belief that it will return the |
102 return equal(a.get(), b.get()); | 127 // correctly-folded code point in all cases (see comment below). |
103 } | 128 template<typename T> static inline UChar foldCase(T ch) |
| 129 { |
| 130 if (IsSameType<T, LChar>::value) |
| 131 return StringImpl::latin1CaseFoldTable[ch]; |
| 132 // It's possible for WTF::Unicode::foldCase() to return a 32-bit value |
| 133 // that's not representable as a UChar. However, since this is rare and |
| 134 // deterministic, and the result of this is merely used for hashing, go |
| 135 // ahead and clamp the value. |
| 136 return static_cast<UChar>(WTF::Unicode::foldCase(ch)); |
| 137 } |
| 138 }; |
104 | 139 |
105 static unsigned hash(const String& key) | 140 // This hash can be used in cases where the key is a hash of a string, but we |
106 { | 141 // don't want to store the string. It's not really specific to string hashing, |
107 return hash(key.impl()); | 142 // but all our current uses of it are for strings. |
108 } | 143 struct AlreadyHashed : IntHash<unsigned> { |
109 static unsigned hash(const AtomicString& key) | 144 static unsigned hash(unsigned key) { return key; } |
110 { | |
111 return hash(key.impl()); | |
112 } | |
113 static bool equal(const String& a, const String& b) | |
114 { | |
115 return equal(a.impl(), b.impl()); | |
116 } | |
117 static bool equal(const AtomicString& a, const AtomicString& b) | |
118 { | |
119 return (a == b) || equal(a.impl(), b.impl()); | |
120 } | |
121 | 145 |
122 static const bool safeToCompareToEmptyOrDeleted = false; | 146 // To use a hash value as a key for a hash table, we need to eliminate the |
123 | 147 // "deleted" value, which is negative one. That could be done by changing |
124 private: | 148 // the string hash function to never generate negative one, but this works |
125 // Private so no one uses this in the belief that it will return the | 149 // and is still relatively efficient. |
126 // correctly-folded code point in all cases (see comment below). | 150 static unsigned avoidDeletedValue(unsigned hash) |
127 template<typename T> static inline UChar foldCase(T ch) | 151 { |
128 { | 152 ASSERT(hash); |
129 if (IsSameType<T, LChar>::value) | 153 unsigned newHash = hash | (!(hash + 1) << 31); |
130 return StringImpl::latin1CaseFoldTable[ch]; | 154 ASSERT(newHash); |
131 // It's possible for WTF::Unicode::foldCase() to return a 32-bit | 155 ASSERT(newHash != 0xFFFFFFFF); |
132 // value that's not representable as a UChar. However, since this | 156 return newHash; |
133 // is rare and deterministic, and the result of this is merely used | 157 } |
134 // for hashing, go ahead and clamp the value. | 158 }; |
135 return static_cast<UChar>(WTF::Unicode::foldCase(ch)); | |
136 } | |
137 }; | |
138 | |
139 // This hash can be used in cases where the key is a hash of a string, but w
e don't | |
140 // want to store the string. It's not really specific to string hashing, but
all our | |
141 // current uses of it are for strings. | |
142 struct AlreadyHashed : IntHash<unsigned> { | |
143 static unsigned hash(unsigned key) { return key; } | |
144 | |
145 // To use a hash value as a key for a hash table, we need to eliminate t
he | |
146 // "deleted" value, which is negative one. That could be done by changin
g | |
147 // the string hash function to never generate negative one, but this wor
ks | |
148 // and is still relatively efficient. | |
149 static unsigned avoidDeletedValue(unsigned hash) | |
150 { | |
151 ASSERT(hash); | |
152 unsigned newHash = hash | (!(hash + 1) << 31); | |
153 ASSERT(newHash); | |
154 ASSERT(newHash != 0xFFFFFFFF); | |
155 return newHash; | |
156 } | |
157 }; | |
158 | 159 |
159 } | 160 } |
160 | 161 |
161 using WTF::AlreadyHashed; | 162 using WTF::AlreadyHashed; |
162 using WTF::CaseFoldingHash; | 163 using WTF::CaseFoldingHash; |
163 using WTF::StringHash; | 164 using WTF::StringHash; |
164 | 165 |
165 #endif | 166 #endif |
OLD | NEW |