third_party/WebKit/Source/wtf/text/StringHash.h

   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         static unsigned hash(const UChar* data, unsigned length)
  69         {
  70             return StringHasher::computeHashAndMaskTop8Bits<UChar, foldCase<UChar>>(data, length);
  71         }
  72
  73         static unsigned hash(StringImpl* str)
  74         {
  75             if (str->is8Bit())
  76                 return hash(str->characters8(), str->length());
  77             return hash(str->characters16(), str->length());
  78         }
  79
  80         static unsigned hash(const LChar* data, unsigned length)
  81         {
  82             return StringHasher::computeHashAndMaskTop8Bits<LChar, foldCase<LChar>>(data, length);
  83         }
  84
  85         static inline unsigned hash(const char* data, unsigned length)
  86         {
  87             return CaseFoldingHash::hash(reinterpret_cast<const LChar*>(data), length);
  88         }
  89
  90         static inline bool equal(const StringImpl* a, const StringImpl* b)
  91         {
  92             return equalIgnoringCaseNonNull(a, b);
  93         }
  94
  95         static unsigned hash(const RefPtr<StringImpl>& key)
  96         {
  97             return hash(key.get());
  98         }
  99
 100         static bool equal(const RefPtr<StringImpl>& a, const RefPtr<StringImpl>& b)
 101         {
 102             return equal(a.get(), b.get());
 103         }
 104
 105         static unsigned hash(const String& key)
 106         {
 107             return hash(key.impl());
 108         }
 109         static unsigned hash(const AtomicString& 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
 122         static const bool safeToCompareToEmptyOrDeleted = false;
 123
 124     private:
 125         // Private so no one uses this in the belief that it will return the
 126         // correctly-folded code point in all cases (see comment below).
 127         template<typename T> static inline UChar foldCase(T ch)
 128         {
 129             if (IsSameType<T, LChar>::value)
 130                 return StringImpl::latin1CaseFoldTable[ch];
 131             // It's possible for WTF::Unicode::foldCase() to return a 32-bit
 132             // value that's not representable as a UChar.  However, since this
 133             // is rare and deterministic, and the result of this is merely used
 134             // for hashing, go ahead and clamp the value.
 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 we 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 the
 146         // "deleted" value, which is negative one. That could be done by changing
 147         // the string hash function to never generate negative one, but this works
 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 }
 160
 161 using WTF::AlreadyHashed;
 162 using WTF::CaseFoldingHash;
 163 using WTF::StringHash;
 164
 165 #endif