1/*
2 * Copyright (C) 2006-2008, 2012-2013, 2016 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#ifndef StringHash_h
23#define StringHash_h
24
25#include <wtf/text/AtomicString.h>
26#include <wtf/HashTraits.h>
27#include <wtf/Hasher.h>
28
29namespace WTF {
30
31 inline bool HashTraits<String>::isEmptyValue(const String& value)
32 {
33 return value.isNull();
34 }
35
36 inline void HashTraits<String>::customDeleteBucket(String& value)
37 {
38 // See unique_ptr's customDeleteBucket() for an explanation.
39 ASSERT(!isDeletedValue(value));
40 String valueToBeDestroyed = WTFMove(value);
41 constructDeletedValue(value);
42 }
43
44 // The hash() functions on StringHash and ASCIICaseInsensitiveHash do not support
45 // null strings. get(), contains(), and add() on HashMap<String,..., StringHash>
46 // cause a null-pointer dereference when passed null strings.
47
48 // FIXME: We should really figure out a way to put the computeHash function that's
49 // currently a member function of StringImpl into this file so we can be a little
50 // closer to having all the nearly-identical hash functions in one place.
51
52 struct StringHash {
53 static unsigned hash(StringImpl* key) { return key->hash(); }
54 static inline bool equal(const StringImpl* a, const StringImpl* b)
55 {
56 return WTF::equal(*a, *b);
57 }
58
59 static unsigned hash(const RefPtr<StringImpl>& key) { return key->hash(); }
60 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b)
61 {
62 return equal(a.get(), b.get());
63 }
64 static bool equal(const RefPtr<StringImpl>& a, const StringImpl* b)
65 {
66 return equal(a.get(), b);
67 }
68 static bool equal(const StringImpl* a, const RefPtr<StringImpl>& b)
69 {
70 return equal(a, b.get());
71 }
72
73 static unsigned hash(const String& key) { return key.impl()->hash(); }
74 static bool equal(const String& a, const String& b)
75 {
76 return equal(a.impl(), b.impl());
77 }
78
79 static const bool safeToCompareToEmptyOrDeleted = false;
80 };
81
82 class ASCIICaseInsensitiveHash {
83 public:
84 template<typename T> static inline UChar foldCase(T character)
85 {
86 return toASCIILower(character);
87 }
88
89 static unsigned hash(const UChar* data, unsigned length)
90 {
91 return StringHasher::computeHashAndMaskTop8Bits<UChar, foldCase<UChar>>(data, length);
92 }
93
94 static unsigned hash(StringImpl& string)
95 {
96 if (string.is8Bit())
97 return hash(string.characters8(), string.length());
98 return hash(string.characters16(), string.length());
99 }
100 static unsigned hash(StringImpl* string)
101 {
102 ASSERT(string);
103 return hash(*string);
104 }
105
106 static unsigned hash(const LChar* data, unsigned length)
107 {
108 return StringHasher::computeHashAndMaskTop8Bits<LChar, foldCase<LChar>>(data, length);
109 }
110
111 static inline unsigned hash(const char* data, unsigned length)
112 {
113 return hash(reinterpret_cast<const LChar*>(data), length);
114 }
115
116 static inline bool equal(const StringImpl& a, const StringImpl& b)
117 {
118 return equalIgnoringASCIICase(a, b);
119 }
120 static inline bool equal(const StringImpl* a, const StringImpl* b)
121 {
122 ASSERT(a);
123 ASSERT(b);
124 return equal(*a, *b);
125 }
126
127 static unsigned hash(const RefPtr<StringImpl>& key)
128 {
129 return hash(key.get());
130 }
131
132 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b)
133 {
134 return equal(a.get(), b.get());
135 }
136
137 static unsigned hash(const String& key)
138 {
139 return hash(key.impl());
140 }
141 static unsigned hash(const AtomicString& key)
142 {
143 return hash(key.impl());
144 }
145 static bool equal(const String& a, const String& b)
146 {
147 return equal(a.impl(), b.impl());
148 }
149 static bool equal(const AtomicString& a, const AtomicString& b)
150 {
151 // FIXME: Is the "a == b" here a helpful optimization?
152 // It makes all cases where the strings are not identical slightly slower.
153 return a == b || equal(a.impl(), b.impl());
154 }
155
156 static const bool safeToCompareToEmptyOrDeleted = false;
157 };
158
159 // This hash can be used in cases where the key is a hash of a string, but we don't
160 // want to store the string. It's not really specific to string hashing, but all our
161 // current uses of it are for strings.
162 struct AlreadyHashed : IntHash<unsigned> {
163 static unsigned hash(unsigned key) { return key; }
164
165 // To use a hash value as a key for a hash table, we need to eliminate the
166 // "deleted" value, which is negative one. That could be done by changing
167 // the string hash function to never generate negative one, but this works
168 // and is still relatively efficient.
169 static unsigned avoidDeletedValue(unsigned hash)
170 {
171 ASSERT(hash);
172 unsigned newHash = hash | (!(hash + 1) << 31);
173 ASSERT(newHash);
174 ASSERT(newHash != 0xFFFFFFFF);
175 return newHash;
176 }
177 };
178
179}
180
181using WTF::ASCIICaseInsensitiveHash;
182using WTF::AlreadyHashed;
183using WTF::StringHash;
184
185#endif
186