OLD | NEW |
| (Empty) |
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 StringHash_h | |
23 #define StringHash_h | |
24 | |
25 #include <wtf/text/AtomicString.h> | |
26 #include <wtf/HashTraits.h> | |
27 #include <wtf/StringHasher.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 CaseFoldingHash do not support | |
37 // null strings. get(), contains(), and add() on HashMap<String,..., StringH
ash> | |
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 l
ittle | |
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 equalNonNull(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 | |
57 static unsigned hash(const String& key) { return key.impl()->hash(); } | |
58 static bool equal(const String& a, const String& b) | |
59 { | |
60 return equal(a.impl(), b.impl()); | |
61 } | |
62 | |
63 static const bool safeToCompareToEmptyOrDeleted = false; | |
64 }; | |
65 | |
66 class CaseFoldingHash { | |
67 public: | |
68 template<typename T> static inline UChar foldCase(T ch) | |
69 { | |
70 return WTF::Unicode::foldCase(ch); | |
71 } | |
72 | |
73 static unsigned hash(const UChar* data, unsigned length) | |
74 { | |
75 return StringHasher::computeHashAndMaskTop8Bits<UChar, foldCase<UCha
r> >(data, length); | |
76 } | |
77 | |
78 static unsigned hash(StringImpl* str) | |
79 { | |
80 if (str->is8Bit()) | |
81 return hash(str->characters8(), str->length()); | |
82 return hash(str->characters16(), str->length()); | |
83 } | |
84 | |
85 static unsigned hash(const LChar* data, unsigned length) | |
86 { | |
87 return StringHasher::computeHashAndMaskTop8Bits<LChar, foldCase<LCha
r> >(data, length); | |
88 } | |
89 | |
90 static inline unsigned hash(const char* data, unsigned length) | |
91 { | |
92 return CaseFoldingHash::hash(reinterpret_cast<const LChar*>(data), l
ength); | |
93 } | |
94 | |
95 static inline bool equal(const StringImpl* a, const StringImpl* b) | |
96 { | |
97 return equalIgnoringCaseNonNull(a, b); | |
98 } | |
99 | |
100 static unsigned hash(const RefPtr<StringImpl>& key) | |
101 { | |
102 return hash(key.get()); | |
103 } | |
104 | |
105 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>&
b) | |
106 { | |
107 return equal(a.get(), b.get()); | |
108 } | |
109 | |
110 static unsigned hash(const String& key) | |
111 { | |
112 return hash(key.impl()); | |
113 } | |
114 static unsigned hash(const AtomicString& key) | |
115 { | |
116 return hash(key.impl()); | |
117 } | |
118 static bool equal(const String& a, const String& b) | |
119 { | |
120 return equal(a.impl(), b.impl()); | |
121 } | |
122 static bool equal(const AtomicString& a, const AtomicString& b) | |
123 { | |
124 return (a == b) || equal(a.impl(), b.impl()); | |
125 } | |
126 | |
127 static const bool safeToCompareToEmptyOrDeleted = false; | |
128 }; | |
129 | |
130 // This hash can be used in cases where the key is a hash of a string, but w
e don't | |
131 // want to store the string. It's not really specific to string hashing, but
all our | |
132 // current uses of it are for strings. | |
133 struct AlreadyHashed : IntHash<unsigned> { | |
134 static unsigned hash(unsigned key) { return key; } | |
135 | |
136 // To use a hash value as a key for a hash table, we need to eliminate t
he | |
137 // "deleted" value, which is negative one. That could be done by changin
g | |
138 // the string hash function to never generate negative one, but this wor
ks | |
139 // and is still relatively efficient. | |
140 static unsigned avoidDeletedValue(unsigned hash) | |
141 { | |
142 ASSERT(hash); | |
143 unsigned newHash = hash | (!(hash + 1) << 31); | |
144 ASSERT(newHash); | |
145 ASSERT(newHash != 0xFFFFFFFF); | |
146 return newHash; | |
147 } | |
148 }; | |
149 | |
150 } | |
151 | |
152 using WTF::AlreadyHashed; | |
153 using WTF::CaseFoldingHash; | |
154 using WTF::StringHash; | |
155 | |
156 #endif | |
OLD | NEW |