15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 2926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) * Copyright (C) 2006, 2007, 2008, 2012, 2013 Apple Inc. All rights reserved 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Copyright (C) Research In Motion Limited 2009. All rights reserved. 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * This library is free software; you can redistribute it and/or 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modify it under the terms of the GNU Library General Public 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * License as published by the Free Software Foundation; either 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * version 2 of the License, or (at your option) any later version. 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * This library is distributed in the hope that it will be useful, 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * but WITHOUT ANY WARRANTY; without even the implied warranty of 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Library General Public License for more details. 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * You should have received a copy of the GNU Library General Public License 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * along with this library; see the file COPYING.LIB. If not, write to 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Boston, MA 02110-1301, USA. 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#ifndef StringHash_h 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#define StringHash_h 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 25591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/text/AtomicString.h" 26591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/HashTraits.h" 27591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/StringHasher.h" 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace WTF { 305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) inline bool HashTraits<String>::isEmptyValue(const String& value) 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return value.isNull(); 345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // The hash() functions on StringHash and CaseFoldingHash do not support 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // null strings. get(), contains(), and add() on HashMap<String,..., StringHash> 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // cause a null-pointer dereference when passed null strings. 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // FIXME: We should really figure out a way to put the computeHash function that's 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // currently a member function of StringImpl into this file so we can be a little 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // closer to having all the nearly-identical hash functions in one place. 435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct StringHash { 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static unsigned hash(StringImpl* key) { return key->hash(); } 46926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) static inline bool equal(const StringImpl* a, const StringImpl* b) 475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 48926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return equalNonNull(a, b); 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static unsigned hash(const RefPtr<StringImpl>& key) { return key->hash(); } 525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b) 535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return equal(a.get(), b.get()); 555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 575c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static unsigned hash(const String& key) { return key.impl()->hash(); } 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool equal(const String& a, const String& b) 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return equal(a.impl(), b.impl()); 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 625c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 635c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool safeToCompareToEmptyOrDeleted = false; 645c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 655c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 665c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) class CaseFoldingHash { 675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) public: 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) template<typename T> static inline UChar foldCase(T ch) 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return WTF::Unicode::foldCase(ch); 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 725c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static unsigned hash(const UChar* data, unsigned length) 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 755c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return StringHasher::computeHashAndMaskTop8Bits<UChar, foldCase<UChar> >(data, length); 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 785c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static unsigned hash(StringImpl* str) 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) if (str->is8Bit()) 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return hash(str->characters8(), str->length()); 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return hash(str->characters16(), str->length()); 835c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static unsigned hash(const LChar* data, unsigned length) 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 875c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return StringHasher::computeHashAndMaskTop8Bits<LChar, foldCase<LChar> >(data, length); 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 895c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static inline unsigned hash(const char* data, unsigned length) 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return CaseFoldingHash::hash(reinterpret_cast<const LChar*>(data), length); 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 9402772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch 95926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) static inline bool equal(const StringImpl* a, const StringImpl* b) 965c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 97926b001d589ce2f10facb93dd4b87578ea35a855Torne (Richard Coles) return equalIgnoringCaseNonNull(a, b); 985c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 10002772c6a72f1ee0b226341a4f4439970c29fc861Ben Murdoch static unsigned hash(const RefPtr<StringImpl>& key) 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return hash(key.get()); 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1055c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b) 1065c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1075c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return equal(a.get(), b.get()); 1085c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1095c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static unsigned hash(const String& key) 1115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return hash(key.impl()); 1135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static unsigned hash(const AtomicString& key) 1155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return hash(key.impl()); 1175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool equal(const String& a, const String& b) 1195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return equal(a.impl(), b.impl()); 1215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static bool equal(const AtomicString& a, const AtomicString& b) 1235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return (a == b) || equal(a.impl(), b.impl()); 1255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1275c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static const bool safeToCompareToEmptyOrDeleted = false; 1285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 1295c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1305c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // This hash can be used in cases where the key is a hash of a string, but we don't 1315c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // want to store the string. It's not really specific to string hashing, but all our 1325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // current uses of it are for strings. 1335c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) struct AlreadyHashed : IntHash<unsigned> { 1345c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static unsigned hash(unsigned key) { return key; } 1355c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // To use a hash value as a key for a hash table, we need to eliminate the 1375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // "deleted" value, which is negative one. That could be done by changing 1385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // the string hash function to never generate negative one, but this works 1395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) // and is still relatively efficient. 1405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) static unsigned avoidDeletedValue(unsigned hash) 1415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 1425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(hash); 1435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) unsigned newHash = hash | (!(hash + 1) << 31); 1445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(newHash); 1455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) ASSERT(newHash != 0xFFFFFFFF); 1465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) return newHash; 1475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) }; 1495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1515c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1525c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)using WTF::AlreadyHashed; 1535c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)using WTF::CaseFoldingHash; 1545c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)using WTF::StringHash; 1555c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 1565c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#endif 157