1/*
2 * Copyright (C) 2006-2017 Apple Inc. All rights reserved
3 * Copyright (C) Research In Motion Limited 2009. All rights reserved.
4 *
5 * This library is free software; you can redistribute it and/or
6 * modify it under the terms of the GNU Library General Public
7 * License as published by the Free Software Foundation; either
8 * version 2 of the License, or (at your option) any later version.
9 *
10 * This library is distributed in the hope that it will be useful,
11 * but WITHOUT ANY WARRANTY; without even the implied warranty of
12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 * Library General Public License for more details.
14 *
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
17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 * Boston, MA 02110-1301, USA.
19 *
20 */
21
22#pragma once
23
24#include <wtf/HashTraits.h>
25#include <wtf/text/AtomicString.h>
26#include <wtf/text/StringHasher.h>
27
28namespace WTF {
29
30 inline bool HashTraits<String>::isEmptyValue(const String& value)
31 {
32 return value.isNull();
33 }
34
35 inline void HashTraits<String>::customDeleteBucket(String& value)
36 {
37 // See unique_ptr's customDeleteBucket() for an explanation.
38 ASSERT(!isDeletedValue(value));
39 String valueToBeDestroyed = WTFMove(value);
40 constructDeletedValue(value);
41 }
42
43 // The hash() functions on StringHash and ASCIICaseInsensitiveHash do not support
44 // null strings. get(), contains(), and add() on HashMap<String,..., StringHash>
45 // cause a null-pointer dereference when passed null strings.
46
47 // FIXME: We should really figure out a way to put the computeHash function that's
48 // currently a member function of StringImpl into this file so we can be a little
49 // closer to having all the nearly-identical hash functions in one place.
50
51 struct StringHash {
52 static unsigned hash(StringImpl* key) { return key->hash(); }
53 static inline bool equal(const StringImpl* a, const StringImpl* b)
54 {
55 return WTF::equal(*a, *b);
56 }
57
58 static unsigned hash(const RefPtr<StringImpl>& key) { return key->hash(); }
59 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b)
60 {
61 return equal(a.get(), b.get());
62 }
63 static bool equal(const RefPtr<StringImpl>& a, const StringImpl* b)
64 {
65 return equal(a.get(), b);
66 }
67 static bool equal(const StringImpl* a, const RefPtr<StringImpl>& b)
68 {
69 return equal(a, b.get());
70 }
71
72 static unsigned hash(const String& key) { return key.impl()->hash(); }
73 static bool equal(const String& a, const String& b)
74 {
75 return equal(a.impl(), b.impl());
76 }
77
78 static const bool safeToCompareToEmptyOrDeleted = false;
79 };
80
81 struct ASCIICaseInsensitiveHash {
82 template<typename T>
83 struct FoldCase {
84 static inline UChar convert(T character)
85 {
86 return toASCIILower(character);
87 }
88 };
89
90 static unsigned hash(const UChar* data, unsigned length)
91 {
92 return StringHasher::computeHashAndMaskTop8Bits<UChar, FoldCase<UChar>>(data, length);
93 }
94
95 static unsigned hash(StringImpl& string)
96 {
97 if (string.is8Bit())
98 return hash(string.characters8(), string.length());
99 return hash(string.characters16(), string.length());
100 }
101 static unsigned hash(StringImpl* string)
102 {
103 ASSERT(string);
104 return hash(*string);
105 }
106
107 static unsigned hash(const LChar* data, unsigned length)
108 {
109 return StringHasher::computeHashAndMaskTop8Bits<LChar, FoldCase<LChar>>(data, length);
110 }
111
112 static inline unsigned hash(const char* data, unsigned length)
113 {
114 return hash(reinterpret_cast<const LChar*>(data), length);
115 }
116
117 static inline bool equal(const StringImpl& a, const StringImpl& b)
118 {
119 return equalIgnoringASCIICase(a, b);
120 }
121 static inline bool equal(const StringImpl* a, const StringImpl* b)
122 {
123 ASSERT(a);
124 ASSERT(b);
125 return equal(*a, *b);
126 }
127
128 static unsigned hash(const RefPtr<StringImpl>& key)
129 {
130 return hash(key.get());
131 }
132
133 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b)
134 {
135 return equal(a.get(), b.get());
136 }
137
138 static unsigned hash(const String& key)
139 {
140 return hash(key.impl());
141 }
142 static unsigned hash(const AtomicString& key)
143 {
144 return hash(key.impl());
145 }
146 static bool equal(const String& a, const String& b)
147 {
148 return equal(a.impl(), b.impl());
149 }
150 static bool equal(const AtomicString& a, const AtomicString& b)
151 {
152 // FIXME: Is the "a == b" here a helpful optimization?
153 // It makes all cases where the strings are not identical slightly slower.
154 return a == b || equal(a.impl(), b.impl());
155 }
156
157 static const bool safeToCompareToEmptyOrDeleted = false;
158 };
159
160 // This hash can be used in cases where the key is a hash of a string, but we don't
161 // want to store the string. It's not really specific to string hashing, but all our
162 // current uses of it are for strings.
163 struct AlreadyHashed : IntHash<unsigned> {
164 static unsigned hash(unsigned key) { return key; }
165
166 // To use a hash value as a key for a hash table, we need to eliminate the
167 // "deleted" value, which is negative one. That could be done by changing
168 // the string hash function to never generate negative one, but this works
169 // and is still relatively efficient.
170 static unsigned avoidDeletedValue(unsigned hash)
171 {
172 ASSERT(hash);
173 unsigned newHash = hash | (!(hash + 1) << 31);
174 ASSERT(newHash);
175 ASSERT(newHash != 0xFFFFFFFF);
176 return newHash;
177 }
178 };
179
180 // FIXME: Find a way to incorporate this functionality into ASCIICaseInsensitiveHash and allow
181 // a HashMap whose keys are type String to perform operations when given a key of type StringView.
182 struct ASCIICaseInsensitiveStringViewHashTranslator {
183 static unsigned hash(StringView key)
184 {
185 if (key.is8Bit())
186 return ASCIICaseInsensitiveHash::hash(key.characters8(), key.length());
187 return ASCIICaseInsensitiveHash::hash(key.characters16(), key.length());
188 }
189
190 static bool equal(const String& a, StringView b)
191 {
192 return equalIgnoringASCIICaseCommon(a, b);
193 }
194 };
195
196}
197
198using WTF::ASCIICaseInsensitiveHash;
199using WTF::ASCIICaseInsensitiveStringViewHashTranslator;
200using WTF::AlreadyHashed;
201using WTF::StringHash;
202