1 /*
2 * Copyright (C) 2006, 2007, 2008, 2012, 2013 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 THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TEXT_STRING_HASH_H_
23 #define THIRD_PARTY_BLINK_RENDERER_PLATFORM_WTF_TEXT_STRING_HASH_H_
24
25 #include "third_party/blink/renderer/platform/wtf/allocator/allocator.h"
26 #include "third_party/blink/renderer/platform/wtf/hash_traits.h"
27 #include "third_party/blink/renderer/platform/wtf/text/atomic_string.h"
28 #include "third_party/blink/renderer/platform/wtf/text/string_hasher.h"
29
30 namespace WTF {
31
IsEmptyValue(const String & value)32 inline bool HashTraits<String>::IsEmptyValue(const String& value) {
33 return value.IsNull();
34 }
35
IsDeletedValue(const String & value)36 inline bool HashTraits<String>::IsDeletedValue(const String& value) {
37 return HashTraits<scoped_refptr<StringImpl>>::IsDeletedValue(value.impl_);
38 }
39
ConstructDeletedValue(String & slot,bool zero_value)40 inline void HashTraits<String>::ConstructDeletedValue(String& slot,
41 bool zero_value) {
42 HashTraits<scoped_refptr<StringImpl>>::ConstructDeletedValue(slot.impl_,
43 zero_value);
44 }
45
46 // The hash() functions on StringHash and CaseFoldingHash do not support null
47 // strings. get(), contains(), and add() on HashMap<String,..., StringHash>
48 // cause a null-pointer dereference when passed null strings.
49
50 // FIXME: We should really figure out a way to put the computeHash function
51 // that's currently a member function of StringImpl into this file so we can be
52 // a little closer to having all the nearly-identical hash functions in one
53 // place.
54
55 struct StringHash {
56 STATIC_ONLY(StringHash);
GetHashStringHash57 static unsigned GetHash(StringImpl* key) { return key->GetHash(); }
EqualStringHash58 static inline bool Equal(const StringImpl* a, const StringImpl* b) {
59 return EqualNonNull(a, b);
60 }
61
GetHashStringHash62 static unsigned GetHash(const scoped_refptr<StringImpl>& key) {
63 return key->GetHash();
64 }
EqualStringHash65 static bool Equal(const scoped_refptr<StringImpl>& a,
66 const scoped_refptr<StringImpl>& b) {
67 return Equal(a.get(), b.get());
68 }
69
GetHashStringHash70 static unsigned GetHash(const String& key) { return key.Impl()->GetHash(); }
EqualStringHash71 static bool Equal(const String& a, const String& b) {
72 return Equal(a.Impl(), b.Impl());
73 }
74
75 static const bool safe_to_compare_to_empty_or_deleted = false;
76 };
77
78 class CaseFoldingHash {
79 STATIC_ONLY(CaseFoldingHash);
80
81 public:
GetHash(const UChar * data,unsigned length)82 static unsigned GetHash(const UChar* data, unsigned length) {
83 return StringHasher::ComputeHashAndMaskTop8Bits<UChar, FoldCase<UChar>>(
84 data, length);
85 }
86
GetHash(StringImpl * str)87 static unsigned GetHash(StringImpl* str) {
88 if (str->Is8Bit())
89 return GetHash(str->Characters8(), str->length());
90 return GetHash(str->Characters16(), str->length());
91 }
92
GetHash(const LChar * data,unsigned length)93 static unsigned GetHash(const LChar* data, unsigned length) {
94 return StringHasher::ComputeHashAndMaskTop8Bits<LChar, FoldCase<LChar>>(
95 data, length);
96 }
97
GetHash(const char * data,unsigned length)98 static inline unsigned GetHash(const char* data, unsigned length) {
99 return CaseFoldingHash::GetHash(reinterpret_cast<const LChar*>(data),
100 length);
101 }
102
Equal(const StringImpl * a,const StringImpl * b)103 static inline bool Equal(const StringImpl* a, const StringImpl* b) {
104 DCHECK(a);
105 DCHECK(b);
106 // Save one branch inside each StringView by derefing the StringImpl,
107 // and another branch inside the compare function by skipping the null
108 // checks.
109 return DeprecatedEqualIgnoringCaseAndNullity(*a, *b);
110 }
111
GetHash(const scoped_refptr<StringImpl> & key)112 static unsigned GetHash(const scoped_refptr<StringImpl>& key) {
113 return GetHash(key.get());
114 }
115
Equal(const scoped_refptr<StringImpl> & a,const scoped_refptr<StringImpl> & b)116 static bool Equal(const scoped_refptr<StringImpl>& a,
117 const scoped_refptr<StringImpl>& b) {
118 return Equal(a.get(), b.get());
119 }
120
GetHash(const String & key)121 static unsigned GetHash(const String& key) { return GetHash(key.Impl()); }
GetHash(const AtomicString & key)122 static unsigned GetHash(const AtomicString& key) {
123 return GetHash(key.Impl());
124 }
Equal(const String & a,const String & b)125 static bool Equal(const String& a, const String& b) {
126 return Equal(a.Impl(), b.Impl());
127 }
Equal(const AtomicString & a,const AtomicString & b)128 static bool Equal(const AtomicString& a, const AtomicString& b) {
129 return (a == b) || Equal(a.Impl(), b.Impl());
130 }
131
132 static const bool safe_to_compare_to_empty_or_deleted = false;
133
134 private:
135 // Private so no one uses this in the belief that it will return the
136 // correctly-folded code point in all cases (see comment below).
137 template <typename T>
FoldCase(T ch)138 static inline UChar FoldCase(T ch) {
139 if (std::is_same<T, LChar>::value)
140 return StringImpl::kLatin1CaseFoldTable[ch];
141 // It's possible for WTF::unicode::foldCase() to return a 32-bit value
142 // that's not representable as a UChar. However, since this is rare and
143 // deterministic, and the result of this is merely used for hashing, go
144 // ahead and clamp the value.
145 return static_cast<UChar>(WTF::unicode::FoldCase(ch));
146 }
147 };
148
149 // This hash can be used in cases where the key is a hash of a string, but we
150 // don't want to store the string. It's not really specific to string hashing,
151 // but all our current uses of it are for strings.
152 struct AlreadyHashed : IntHash<unsigned> {
153 STATIC_ONLY(AlreadyHashed);
GetHashAlreadyHashed154 static unsigned GetHash(unsigned key) { return key; }
155
156 // To use a hash value as a key for a hash table, we need to eliminate the
157 // "deleted" value, which is negative one. That could be done by changing
158 // the string hash function to never generate negative one, but this works
159 // and is still relatively efficient.
AvoidDeletedValueAlreadyHashed160 static unsigned AvoidDeletedValue(unsigned hash) {
161 DCHECK(hash);
162 unsigned new_hash = hash | (!(hash + 1) << 31);
163 DCHECK(new_hash);
164 DCHECK_NE(new_hash, 0xFFFFFFFF);
165 return new_hash;
166 }
167 };
168
169 } // namespace WTF
170
171 using WTF::AlreadyHashed;
172 using WTF::CaseFoldingHash;
173 using WTF::StringHash;
174
175 #endif
176