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,..., 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 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<UChar> >(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<LChar> >(data, length); 88 } 89 90 static inline unsigned hash(const char* data, unsigned length) 91 { 92 return CaseFoldingHash::hash(reinterpret_cast<const LChar*>(data), length); 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 we 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 the 137 // "deleted" value, which is negative one. That could be done by changing 138 // the string hash function to never generate negative one, but this works 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 157
