| 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, |
| (...skipping 10 matching lines...) Expand all Loading... |
| 21 | 21 |
| 22 #ifndef StringHash_h | 22 #ifndef StringHash_h |
| 23 #define StringHash_h | 23 #define StringHash_h |
| 24 | 24 |
| 25 #include "wtf/HashTraits.h" | 25 #include "wtf/HashTraits.h" |
| 26 #include "wtf/StringHasher.h" | 26 #include "wtf/StringHasher.h" |
| 27 #include "wtf/text/AtomicString.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 { | 32 return value.isNull(); |
| 33 return value.isNull(); | |
| 34 } | 33 } |
| 35 | 34 |
| 36 // The hash() functions on StringHash and CaseFoldingHash do not support null | 35 // The hash() functions on StringHash and CaseFoldingHash do not support null |
| 37 // strings. get(), contains(), and add() on HashMap<String,..., StringHash> | 36 // strings. get(), contains(), and add() on HashMap<String,..., StringHash> |
| 38 // cause a null-pointer dereference when passed null strings. | 37 // cause a null-pointer dereference when passed null strings. |
| 39 | 38 |
| 40 // FIXME: We should really figure out a way to put the computeHash function | 39 // 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 | 40 // 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 | 41 // a little closer to having all the nearly-identical hash functions in one |
| 43 // place. | 42 // place. |
| 44 | 43 |
| 45 struct StringHash { | 44 struct StringHash { |
| 46 static unsigned hash(StringImpl* key) { return key->hash(); } | 45 static unsigned hash(StringImpl* key) { return key->hash(); } |
| 47 static inline bool equal(const StringImpl* a, const StringImpl* b) | 46 static inline bool equal(const StringImpl* a, const StringImpl* b) { |
| 48 { | 47 return equalNonNull(a, b); |
| 49 return equalNonNull(a, b); | 48 } |
| 50 } | |
| 51 | 49 |
| 52 static unsigned hash(const RefPtr<StringImpl>& key) { return key->hash(); } | 50 static unsigned hash(const RefPtr<StringImpl>& key) { return key->hash(); } |
| 53 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b) | 51 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b) { |
| 54 { | 52 return equal(a.get(), b.get()); |
| 55 return equal(a.get(), b.get()); | 53 } |
| 56 } | |
| 57 | 54 |
| 58 static unsigned hash(const String& key) { return key.impl()->hash(); } | 55 static unsigned hash(const String& key) { return key.impl()->hash(); } |
| 59 static bool equal(const String& a, const String& b) | 56 static bool equal(const String& a, const String& b) { |
| 60 { | 57 return equal(a.impl(), b.impl()); |
| 61 return equal(a.impl(), b.impl()); | 58 } |
| 62 } | |
| 63 | 59 |
| 64 static const bool safeToCompareToEmptyOrDeleted = false; | 60 static const bool safeToCompareToEmptyOrDeleted = false; |
| 65 }; | 61 }; |
| 66 | 62 |
| 67 class CaseFoldingHash { | 63 class CaseFoldingHash { |
| 68 public: | 64 public: |
| 69 static unsigned hash(const UChar* data, unsigned length) | 65 static unsigned hash(const UChar* data, unsigned length) { |
| 70 { | 66 return StringHasher::computeHashAndMaskTop8Bits<UChar, foldCase<UChar>>(data
, length); |
| 71 return StringHasher::computeHashAndMaskTop8Bits<UChar, foldCase<UChar>>(
data, length); | 67 } |
| 72 } | |
| 73 | 68 |
| 74 static unsigned hash(StringImpl* str) | 69 static unsigned hash(StringImpl* str) { |
| 75 { | 70 if (str->is8Bit()) |
| 76 if (str->is8Bit()) | 71 return hash(str->characters8(), str->length()); |
| 77 return hash(str->characters8(), str->length()); | 72 return hash(str->characters16(), str->length()); |
| 78 return hash(str->characters16(), str->length()); | 73 } |
| 79 } | |
| 80 | 74 |
| 81 static unsigned hash(const LChar* data, unsigned length) | 75 static unsigned hash(const LChar* data, unsigned length) { |
| 82 { | 76 return StringHasher::computeHashAndMaskTop8Bits<LChar, foldCase<LChar>>(data
, length); |
| 83 return StringHasher::computeHashAndMaskTop8Bits<LChar, foldCase<LChar>>(
data, length); | 77 } |
| 84 } | |
| 85 | 78 |
| 86 static inline unsigned hash(const char* data, unsigned length) | 79 static inline unsigned hash(const char* data, unsigned length) { |
| 87 { | 80 return CaseFoldingHash::hash(reinterpret_cast<const LChar*>(data), length); |
| 88 return CaseFoldingHash::hash(reinterpret_cast<const LChar*>(data), lengt
h); | 81 } |
| 89 } | |
| 90 | 82 |
| 91 static inline bool equal(const StringImpl* a, const StringImpl* b) | 83 static inline bool equal(const StringImpl* a, const StringImpl* b) { |
| 92 { | 84 return equalIgnoringCaseNonNull(a, b); |
| 93 return equalIgnoringCaseNonNull(a, b); | 85 } |
| 94 } | |
| 95 | 86 |
| 96 static unsigned hash(const RefPtr<StringImpl>& key) | 87 static unsigned hash(const RefPtr<StringImpl>& key) { |
| 97 { | 88 return hash(key.get()); |
| 98 return hash(key.get()); | 89 } |
| 99 } | |
| 100 | 90 |
| 101 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b) | 91 static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b) { |
| 102 { | 92 return equal(a.get(), b.get()); |
| 103 return equal(a.get(), b.get()); | 93 } |
| 104 } | |
| 105 | 94 |
| 106 static unsigned hash(const String& key) | 95 static unsigned hash(const String& key) { |
| 107 { | 96 return hash(key.impl()); |
| 108 return hash(key.impl()); | 97 } |
| 109 } | 98 static unsigned hash(const AtomicString& key) { |
| 110 static unsigned hash(const AtomicString& key) | 99 return hash(key.impl()); |
| 111 { | 100 } |
| 112 return hash(key.impl()); | 101 static bool equal(const String& a, const String& b) { |
| 113 } | 102 return equal(a.impl(), b.impl()); |
| 114 static bool equal(const String& a, const String& b) | 103 } |
| 115 { | 104 static bool equal(const AtomicString& a, const AtomicString& b) { |
| 116 return equal(a.impl(), b.impl()); | 105 return (a == b) || equal(a.impl(), b.impl()); |
| 117 } | 106 } |
| 118 static bool equal(const AtomicString& a, const AtomicString& b) | |
| 119 { | |
| 120 return (a == b) || equal(a.impl(), b.impl()); | |
| 121 } | |
| 122 | 107 |
| 123 static const bool safeToCompareToEmptyOrDeleted = false; | 108 static const bool safeToCompareToEmptyOrDeleted = false; |
| 124 | 109 |
| 125 private: | 110 private: |
| 126 // Private so no one uses this in the belief that it will return the | 111 // Private so no one uses this in the belief that it will return the |
| 127 // correctly-folded code point in all cases (see comment below). | 112 // correctly-folded code point in all cases (see comment below). |
| 128 template<typename T> static inline UChar foldCase(T ch) | 113 template <typename T> |
| 129 { | 114 static inline UChar foldCase(T ch) { |
| 130 if (IsSameType<T, LChar>::value) | 115 if (IsSameType<T, LChar>::value) |
| 131 return StringImpl::latin1CaseFoldTable[ch]; | 116 return StringImpl::latin1CaseFoldTable[ch]; |
| 132 // It's possible for WTF::Unicode::foldCase() to return a 32-bit value | 117 // 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 | 118 // 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 | 119 // deterministic, and the result of this is merely used for hashing, go |
| 135 // ahead and clamp the value. | 120 // ahead and clamp the value. |
| 136 return static_cast<UChar>(WTF::Unicode::foldCase(ch)); | 121 return static_cast<UChar>(WTF::Unicode::foldCase(ch)); |
| 137 } | 122 } |
| 138 }; | 123 }; |
| 139 | 124 |
| 140 // This hash can be used in cases where the key is a hash of a string, but we | 125 // This hash can be used in cases where the key is a hash of a string, but we |
| 141 // don't want to store the string. It's not really specific to string hashing, | 126 // don't want to store the string. It's not really specific to string hashing, |
| 142 // but all our current uses of it are for strings. | 127 // but all our current uses of it are for strings. |
| 143 struct AlreadyHashed : IntHash<unsigned> { | 128 struct AlreadyHashed : IntHash<unsigned> { |
| 144 static unsigned hash(unsigned key) { return key; } | 129 static unsigned hash(unsigned key) { return key; } |
| 145 | 130 |
| 146 // To use a hash value as a key for a hash table, we need to eliminate the | 131 // To use a hash value as a key for a hash table, we need to eliminate the |
| 147 // "deleted" value, which is negative one. That could be done by changing | 132 // "deleted" value, which is negative one. That could be done by changing |
| 148 // the string hash function to never generate negative one, but this works | 133 // the string hash function to never generate negative one, but this works |
| 149 // and is still relatively efficient. | 134 // and is still relatively efficient. |
| 150 static unsigned avoidDeletedValue(unsigned hash) | 135 static unsigned avoidDeletedValue(unsigned hash) { |
| 151 { | 136 ASSERT(hash); |
| 152 ASSERT(hash); | 137 unsigned newHash = hash | (!(hash + 1) << 31); |
| 153 unsigned newHash = hash | (!(hash + 1) << 31); | 138 ASSERT(newHash); |
| 154 ASSERT(newHash); | 139 ASSERT(newHash != 0xFFFFFFFF); |
| 155 ASSERT(newHash != 0xFFFFFFFF); | 140 return newHash; |
| 156 return newHash; | 141 } |
| 157 } | |
| 158 }; | 142 }; |
| 159 | |
| 160 } | 143 } |
| 161 | 144 |
| 162 using WTF::AlreadyHashed; | 145 using WTF::AlreadyHashed; |
| 163 using WTF::CaseFoldingHash; | 146 using WTF::CaseFoldingHash; |
| 164 using WTF::StringHash; | 147 using WTF::StringHash; |
| 165 | 148 |
| 166 #endif | 149 #endif |
| OLD | NEW |