| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright (C) 2006, 2007, 2008, 2012, 2013 Apple Inc. All rights reserved | 2 * Copyright (C) 2006, 2007, 2008, 2012, 2013 Apple Inc. All rights reserved |
| 3 * Copyright (C) Research In Motion Limited 2009. All rights reserved. | 3 * Copyright (C) Research In Motion Limited 2009. All rights reserved. |
| 4 * | 4 * |
| 5 * This library is free software; you can redistribute it and/or | 5 * This library is free software; you can redistribute it and/or |
| 6 * modify it under the terms of the GNU Library General Public | 6 * modify it under the terms of the GNU Library General Public |
| 7 * License as published by the Free Software Foundation; either | 7 * License as published by the Free Software Foundation; either |
| 8 * version 2 of the License, or (at your option) any later version. | 8 * version 2 of the License, or (at your option) any later version. |
| 9 * | 9 * |
| 10 * This library is distributed in the hope that it will be useful, | 10 * This library is distributed in the hope that it will be useful, |
| 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of | 11 * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | 12 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| 13 * Library General Public License for more details. | 13 * Library General Public License for more details. |
| 14 * | 14 * |
| 15 * You should have received a copy of the GNU Library General Public License | 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 | 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, | 17 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, |
| 18 * Boston, MA 02110-1301, USA. | 18 * Boston, MA 02110-1301, USA. |
| 19 * | 19 * |
| 20 */ | 20 */ |
| 21 | 21 |
| 22 #ifndef StringHash_h | 22 #ifndef StringHash_h |
| 23 #define StringHash_h | 23 #define StringHash_h |
| 24 | 24 |
| 25 #include "wtf/text/AtomicString.h" | |
| 26 #include "wtf/HashTraits.h" | 25 #include "wtf/HashTraits.h" |
| 27 #include "wtf/StringHasher.h" | 26 #include "wtf/StringHasher.h" |
| 27 #include "wtf/text/AtomicString.h" |
| 28 | 28 |
| 29 namespace WTF { | 29 namespace WTF { |
| 30 | 30 |
| 31 inline bool HashTraits<String>::isEmptyValue(const String& value) | 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 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 unsigned hash(StringImpl* key) { return key->hash(); } |
| 47 static inline bool equal(const StringImpl* a, const StringImpl* b) |
| 32 { | 48 { |
| 33 return value.isNull(); | 49 return equalNonNull(a, b); |
| 34 } | 50 } |
| 35 | 51 |
| 36 // The hash() functions on StringHash and CaseFoldingHash do not support | 52 static unsigned hash(const RefPtr<StringImpl>& key) { return key->hash(); } |
| 37 // null strings. get(), contains(), and add() on HashMap<String,..., StringH
ash> | 53 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b) |
| 38 // cause a null-pointer dereference when passed null strings. | 54 { |
| 55 return equal(a.get(), b.get()); |
| 56 } |
| 39 | 57 |
| 40 // FIXME: We should really figure out a way to put the computeHash function
that's | 58 static unsigned hash(const String& key) { return key.impl()->hash(); } |
| 41 // currently a member function of StringImpl into this file so we can be a l
ittle | 59 static bool equal(const String& a, const String& b) |
| 42 // closer to having all the nearly-identical hash functions in one place. | 60 { |
| 61 return equal(a.impl(), b.impl()); |
| 62 } |
| 43 | 63 |
| 44 struct StringHash { | 64 static const bool safeToCompareToEmptyOrDeleted = false; |
| 45 static unsigned hash(StringImpl* key) { return key->hash(); } | 65 }; |
| 46 static inline bool equal(const StringImpl* a, const StringImpl* b) | |
| 47 { | |
| 48 return equalNonNull(a, b); | |
| 49 } | |
| 50 | 66 |
| 51 static unsigned hash(const RefPtr<StringImpl>& key) { return key->hash()
; } | 67 class CaseFoldingHash { |
| 52 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>&
b) | 68 public: |
| 53 { | 69 static unsigned hash(const UChar* data, unsigned length) |
| 54 return equal(a.get(), b.get()); | 70 { |
| 55 } | 71 return StringHasher::computeHashAndMaskTop8Bits<UChar, foldCase<UChar>>(
data, length); |
| 72 } |
| 56 | 73 |
| 57 static unsigned hash(const String& key) { return key.impl()->hash(); } | 74 static unsigned hash(StringImpl* str) |
| 58 static bool equal(const String& a, const String& b) | 75 { |
| 59 { | 76 if (str->is8Bit()) |
| 60 return equal(a.impl(), b.impl()); | 77 return hash(str->characters8(), str->length()); |
| 61 } | 78 return hash(str->characters16(), str->length()); |
| 79 } |
| 62 | 80 |
| 63 static const bool safeToCompareToEmptyOrDeleted = false; | 81 static unsigned hash(const LChar* data, unsigned length) |
| 64 }; | 82 { |
| 83 return StringHasher::computeHashAndMaskTop8Bits<LChar, foldCase<LChar>>(
data, length); |
| 84 } |
| 65 | 85 |
| 66 class CaseFoldingHash { | 86 static inline unsigned hash(const char* data, unsigned length) |
| 67 public: | 87 { |
| 68 static unsigned hash(const UChar* data, unsigned length) | 88 return CaseFoldingHash::hash(reinterpret_cast<const LChar*>(data), lengt
h); |
| 69 { | 89 } |
| 70 return StringHasher::computeHashAndMaskTop8Bits<UChar, foldCase<UCha
r>>(data, length); | |
| 71 } | |
| 72 | 90 |
| 73 static unsigned hash(StringImpl* str) | 91 static inline bool equal(const StringImpl* a, const StringImpl* b) |
| 74 { | 92 { |
| 75 if (str->is8Bit()) | 93 return equalIgnoringCaseNonNull(a, b); |
| 76 return hash(str->characters8(), str->length()); | 94 } |
| 77 return hash(str->characters16(), str->length()); | |
| 78 } | |
| 79 | 95 |
| 80 static unsigned hash(const LChar* data, unsigned length) | 96 static unsigned hash(const RefPtr<StringImpl>& key) |
| 81 { | 97 { |
| 82 return StringHasher::computeHashAndMaskTop8Bits<LChar, foldCase<LCha
r>>(data, length); | 98 return hash(key.get()); |
| 83 } | 99 } |
| 84 | 100 |
| 85 static inline unsigned hash(const char* data, unsigned length) | 101 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b) |
| 86 { | 102 { |
| 87 return CaseFoldingHash::hash(reinterpret_cast<const LChar*>(data), l
ength); | 103 return equal(a.get(), b.get()); |
| 88 } | 104 } |
| 89 | 105 |
| 90 static inline bool equal(const StringImpl* a, const StringImpl* b) | 106 static unsigned hash(const String& key) |
| 91 { | 107 { |
| 92 return equalIgnoringCaseNonNull(a, b); | 108 return hash(key.impl()); |
| 93 } | 109 } |
| 110 static unsigned hash(const AtomicString& key) |
| 111 { |
| 112 return hash(key.impl()); |
| 113 } |
| 114 static bool equal(const String& a, const String& b) |
| 115 { |
| 116 return equal(a.impl(), b.impl()); |
| 117 } |
| 118 static bool equal(const AtomicString& a, const AtomicString& b) |
| 119 { |
| 120 return (a == b) || equal(a.impl(), b.impl()); |
| 121 } |
| 94 | 122 |
| 95 static unsigned hash(const RefPtr<StringImpl>& key) | 123 static const bool safeToCompareToEmptyOrDeleted = false; |
| 96 { | |
| 97 return hash(key.get()); | |
| 98 } | |
| 99 | 124 |
| 100 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>&
b) | 125 private: |
| 101 { | 126 // Private so no one uses this in the belief that it will return the |
| 102 return equal(a.get(), b.get()); | 127 // correctly-folded code point in all cases (see comment below). |
| 103 } | 128 template<typename T> static inline UChar foldCase(T ch) |
| 129 { |
| 130 if (IsSameType<T, LChar>::value) |
| 131 return StringImpl::latin1CaseFoldTable[ch]; |
| 132 // It's possible for WTF::Unicode::foldCase() to return a 32-bit value |
| 133 // that's not representable as a UChar. However, since this is rare and |
| 134 // deterministic, and the result of this is merely used for hashing, go |
| 135 // ahead and clamp the value. |
| 136 return static_cast<UChar>(WTF::Unicode::foldCase(ch)); |
| 137 } |
| 138 }; |
| 104 | 139 |
| 105 static unsigned hash(const String& key) | 140 // This hash can be used in cases where the key is a hash of a string, but we |
| 106 { | 141 // don't want to store the string. It's not really specific to string hashing, |
| 107 return hash(key.impl()); | 142 // but all our current uses of it are for strings. |
| 108 } | 143 struct AlreadyHashed : IntHash<unsigned> { |
| 109 static unsigned hash(const AtomicString& key) | 144 static unsigned hash(unsigned key) { return key; } |
| 110 { | |
| 111 return hash(key.impl()); | |
| 112 } | |
| 113 static bool equal(const String& a, const String& b) | |
| 114 { | |
| 115 return equal(a.impl(), b.impl()); | |
| 116 } | |
| 117 static bool equal(const AtomicString& a, const AtomicString& b) | |
| 118 { | |
| 119 return (a == b) || equal(a.impl(), b.impl()); | |
| 120 } | |
| 121 | 145 |
| 122 static const bool safeToCompareToEmptyOrDeleted = false; | 146 // To use a hash value as a key for a hash table, we need to eliminate the |
| 123 | 147 // "deleted" value, which is negative one. That could be done by changing |
| 124 private: | 148 // the string hash function to never generate negative one, but this works |
| 125 // Private so no one uses this in the belief that it will return the | 149 // and is still relatively efficient. |
| 126 // correctly-folded code point in all cases (see comment below). | 150 static unsigned avoidDeletedValue(unsigned hash) |
| 127 template<typename T> static inline UChar foldCase(T ch) | 151 { |
| 128 { | 152 ASSERT(hash); |
| 129 if (IsSameType<T, LChar>::value) | 153 unsigned newHash = hash | (!(hash + 1) << 31); |
| 130 return StringImpl::latin1CaseFoldTable[ch]; | 154 ASSERT(newHash); |
| 131 // It's possible for WTF::Unicode::foldCase() to return a 32-bit | 155 ASSERT(newHash != 0xFFFFFFFF); |
| 132 // value that's not representable as a UChar. However, since this | 156 return newHash; |
| 133 // is rare and deterministic, and the result of this is merely used | 157 } |
| 134 // for hashing, go ahead and clamp the value. | 158 }; |
| 135 return static_cast<UChar>(WTF::Unicode::foldCase(ch)); | |
| 136 } | |
| 137 }; | |
| 138 | |
| 139 // This hash can be used in cases where the key is a hash of a string, but w
e don't | |
| 140 // want to store the string. It's not really specific to string hashing, but
all our | |
| 141 // current uses of it are for strings. | |
| 142 struct AlreadyHashed : IntHash<unsigned> { | |
| 143 static unsigned hash(unsigned key) { return key; } | |
| 144 | |
| 145 // To use a hash value as a key for a hash table, we need to eliminate t
he | |
| 146 // "deleted" value, which is negative one. That could be done by changin
g | |
| 147 // the string hash function to never generate negative one, but this wor
ks | |
| 148 // and is still relatively efficient. | |
| 149 static unsigned avoidDeletedValue(unsigned hash) | |
| 150 { | |
| 151 ASSERT(hash); | |
| 152 unsigned newHash = hash | (!(hash + 1) << 31); | |
| 153 ASSERT(newHash); | |
| 154 ASSERT(newHash != 0xFFFFFFFF); | |
| 155 return newHash; | |
| 156 } | |
| 157 }; | |
| 158 | 159 |
| 159 } | 160 } |
| 160 | 161 |
| 161 using WTF::AlreadyHashed; | 162 using WTF::AlreadyHashed; |
| 162 using WTF::CaseFoldingHash; | 163 using WTF::CaseFoldingHash; |
| 163 using WTF::StringHash; | 164 using WTF::StringHash; |
| 164 | 165 |
| 165 #endif | 166 #endif |
| OLD | NEW |