OLD | NEW |
1 /* | 1 // Copyright 2017 The Chromium Authors. All rights reserved. |
2 * Copyright (C) 2006, 2007, 2008, 2012, 2013 Apple Inc. All rights reserved | 2 // Use of this source code is governed by a BSD-style license that can be |
3 * Copyright (C) Research In Motion Limited 2009. All rights reserved. | 3 // found in the LICENSE file. |
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 | 4 |
22 #ifndef StringHash_h | 5 #include "platform/wtf/text/StringHash.h" |
23 #define StringHash_h | |
24 | 6 |
25 #include "wtf/Allocator.h" | 7 // The contents of this header was moved to platform/wtf as part of |
26 #include "wtf/HashTraits.h" | 8 // WTF migration project. See the following post for details: |
27 #include "wtf/StringHasher.h" | 9 // https://groups.google.com/a/chromium.org/d/msg/blink-dev/tLdAZCTlcAA/bYXVT8gY
CAAJ |
28 #include "wtf/text/AtomicString.h" | |
29 | |
30 namespace WTF { | |
31 | |
32 inline bool HashTraits<String>::isEmptyValue(const String& value) { | |
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_ONLY(StringHash); | |
47 static unsigned hash(StringImpl* key) { return key->hash(); } | |
48 static inline bool equal(const StringImpl* a, const StringImpl* b) { | |
49 return equalNonNull(a, b); | |
50 } | |
51 | |
52 static unsigned hash(const RefPtr<StringImpl>& key) { return key->hash(); } | |
53 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b) { | |
54 return equal(a.get(), b.get()); | |
55 } | |
56 | |
57 static unsigned hash(const String& key) { return key.impl()->hash(); } | |
58 static bool equal(const String& a, const String& b) { | |
59 return equal(a.impl(), b.impl()); | |
60 } | |
61 | |
62 static const bool safeToCompareToEmptyOrDeleted = false; | |
63 }; | |
64 | |
65 class CaseFoldingHash { | |
66 STATIC_ONLY(CaseFoldingHash); | |
67 | |
68 public: | |
69 static unsigned hash(const UChar* data, unsigned length) { | |
70 return StringHasher::computeHashAndMaskTop8Bits<UChar, foldCase<UChar>>( | |
71 data, length); | |
72 } | |
73 | |
74 static unsigned hash(StringImpl* str) { | |
75 if (str->is8Bit()) | |
76 return hash(str->characters8(), str->length()); | |
77 return hash(str->characters16(), str->length()); | |
78 } | |
79 | |
80 static unsigned hash(const LChar* data, unsigned length) { | |
81 return StringHasher::computeHashAndMaskTop8Bits<LChar, foldCase<LChar>>( | |
82 data, length); | |
83 } | |
84 | |
85 static inline unsigned hash(const char* data, unsigned length) { | |
86 return CaseFoldingHash::hash(reinterpret_cast<const LChar*>(data), length); | |
87 } | |
88 | |
89 static inline unsigned hash(const char* data) { | |
90 return CaseFoldingHash::hash(reinterpret_cast<const LChar*>(data), | |
91 strlen(data)); | |
92 } | |
93 | |
94 static inline bool equal(const StringImpl* a, const StringImpl* b) { | |
95 DCHECK(a); | |
96 DCHECK(b); | |
97 // Save one branch inside each StringView by derefing the StringImpl, | |
98 // and another branch inside the compare function by skipping the null | |
99 // checks. | |
100 return equalIgnoringCaseAndNullity(*a, *b); | |
101 } | |
102 | |
103 static unsigned hash(const RefPtr<StringImpl>& key) { | |
104 return hash(key.get()); | |
105 } | |
106 | |
107 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b) { | |
108 return equal(a.get(), b.get()); | |
109 } | |
110 | |
111 static unsigned hash(const String& key) { return hash(key.impl()); } | |
112 static unsigned hash(const AtomicString& key) { return hash(key.impl()); } | |
113 static bool equal(const String& a, const String& b) { | |
114 return equal(a.impl(), b.impl()); | |
115 } | |
116 static bool equal(const AtomicString& a, const AtomicString& b) { | |
117 return (a == b) || equal(a.impl(), b.impl()); | |
118 } | |
119 | |
120 static const bool safeToCompareToEmptyOrDeleted = false; | |
121 | |
122 private: | |
123 // Private so no one uses this in the belief that it will return the | |
124 // correctly-folded code point in all cases (see comment below). | |
125 template <typename T> | |
126 static inline UChar foldCase(T ch) { | |
127 if (std::is_same<T, LChar>::value) | |
128 return StringImpl::latin1CaseFoldTable[ch]; | |
129 // It's possible for WTF::Unicode::foldCase() to return a 32-bit value | |
130 // that's not representable as a UChar. However, since this is rare and | |
131 // deterministic, and the result of this is merely used for hashing, go | |
132 // ahead and clamp the value. | |
133 return static_cast<UChar>(WTF::Unicode::foldCase(ch)); | |
134 } | |
135 }; | |
136 | |
137 // This hash can be used in cases where the key is a hash of a string, but we | |
138 // don't want to store the string. It's not really specific to string hashing, | |
139 // but all our current uses of it are for strings. | |
140 struct AlreadyHashed : IntHash<unsigned> { | |
141 STATIC_ONLY(AlreadyHashed); | |
142 static unsigned hash(unsigned key) { return key; } | |
143 | |
144 // To use a hash value as a key for a hash table, we need to eliminate the | |
145 // "deleted" value, which is negative one. That could be done by changing | |
146 // the string hash function to never generate negative one, but this works | |
147 // and is still relatively efficient. | |
148 static unsigned avoidDeletedValue(unsigned hash) { | |
149 DCHECK(hash); | |
150 unsigned newHash = hash | (!(hash + 1) << 31); | |
151 DCHECK(newHash); | |
152 DCHECK_NE(newHash, 0xFFFFFFFF); | |
153 return newHash; | |
154 } | |
155 }; | |
156 | |
157 } // namespace WTF | |
158 | |
159 using WTF::AlreadyHashed; | |
160 using WTF::CaseFoldingHash; | |
161 using WTF::StringHash; | |
162 | |
163 #endif | |
OLD | NEW |