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