Source/WTF/wtf/StringHasher.h

   1 /*
   2  * Copyright (C) 2005, 2006, 2008, 2010 Apple Inc. All rights reserved.
   3  * Copyright (C) 2010 Patrick Gansterer <paroga@paroga.com>
   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 #ifndef WTF_StringHasher_h
  22 #define WTF_StringHasher_h
  23
  24 #include <wtf/unicode/Unicode.h>
  25
  26 namespace WTF {
  27
  28 // Golden ratio - arbitrary start value to avoid mapping all 0's to all 0's
  29 static const unsigned stringHashingStartValue = 0x9e3779b9U;
  30
  31 // Paul Hsieh's SuperFastHash
  32 // http://www.azillionmonkeys.com/qed/hash.html
  33 // char* data is interpreted as latin-encoded (zero extended to 16 bits).
  34
  35 // NOTE: This class must stay in sync with the create_hash_table script in
  36 // JavaScriptCore and the CodeGeneratorJS.pm script in WebCore.
  37 class StringHasher {
  38 public:
  39     static const unsigned flagCount = 8; // Save 8 bits for StringImpl to use as flags.
  40
  41     inline StringHasher()
  42         : m_hash(stringHashingStartValue)
  43         , m_hasPendingCharacter(false)
  44         , m_pendingCharacter(0)
  45     {
  46     }
  47
  48     inline void addCharacters(UChar a, UChar b)
  49     {
  50         ASSERT(!m_hasPendingCharacter);
  51         addCharactersToHash(a, b);
  52     }
  53
  54     inline void addCharacter(UChar ch)
  55     {
  56         if (m_hasPendingCharacter) {
  57             addCharactersToHash(m_pendingCharacter, ch);
  58             m_hasPendingCharacter = false;
  59             return;
  60         }
  61
  62         m_pendingCharacter = ch;
  63         m_hasPendingCharacter = true;
  64     }
  65
  66     inline unsigned hash() const
  67     {
  68         unsigned result = m_hash;
  69
  70         // Handle end case.
  71         if (m_hasPendingCharacter) {
  72             result += m_pendingCharacter;
  73             result ^= result << 11;
  74             result += result >> 17;
  75         }
  76
  77         // Force "avalanching" of final 31 bits.
  78         result ^= result << 3;
  79         result += result >> 5;
  80         result ^= result << 2;
  81         result += result >> 15;
  82         result ^= result << 10;
  83
  84         // Reserving space from the high bits for flags preserves most of the hash's
  85         // value, since hash lookup typically masks out the high bits anyway.
  86         result &= (1u << (sizeof(result) * 8 - flagCount)) - 1;
  87
  88         // This avoids ever returning a hash code of 0, since that is used to
  89         // signal "hash not computed yet". Setting the high bit maintains
  90         // reasonable fidelity to a hash code of 0 because it is likely to yield
  91         // exactly 0 when hash lookup masks out the high bits.
  92         if (!result)
  93             result = 0x80000000 >> flagCount;
  94
  95         return result;
  96     }
  97
  98     template<typename T, UChar Converter(T)> static inline unsigned computeHash(const T* data, unsigned length)
  99     {
 100         StringHasher hasher;
 101         bool rem = length & 1;
 102         length >>= 1;
 103
 104         while (length--) {
 105             hasher.addCharacters(Converter(data[0]), Converter(data[1]));
 106             data += 2;
 107         }
 108
 109         if (rem)
 110             hasher.addCharacter(Converter(*data));
 111
 112         return hasher.hash();
 113     }
 114
 115     template<typename T, UChar Converter(T)> static inline unsigned computeHash(const T* data)
 116     {
 117         StringHasher hasher;
 118
 119         while (true) {
 120             UChar b0 = Converter(*data++);
 121             if (!b0)
 122                 break;
 123             UChar b1 = Converter(*data++);
 124             if (!b1) {
 125                 hasher.addCharacter(b0);
 126                 break;
 127             }
 128
 129             hasher.addCharacters(b0, b1);
 130         }
 131
 132         return hasher.hash();
 133     }
 134
 135     template<typename T> static inline unsigned computeHash(const T* data, unsigned length)
 136     {
 137         return computeHash<T, defaultConverter>(data, length);
 138     }
 139
 140     template<typename T> static inline unsigned computeHash(const T* data)
 141     {
 142         return computeHash<T, defaultConverter>(data);
 143     }
 144
 145     template<size_t length> static inline unsigned hashMemory(const void* data)
 146     {
 147         COMPILE_ASSERT(!(length % 4), length_must_be_a_multible_of_four);
 148         return computeHash<UChar>(static_cast<const UChar*>(data), length / sizeof(UChar));
 149     }
 150
 151     static inline unsigned hashMemory(const void* data, unsigned size)
 152     {
 153         ASSERT(!(size % 2));
 154         return computeHash<UChar>(static_cast<const UChar*>(data), size / sizeof(UChar));
 155     }
 156
 157 private:
 158     static inline UChar defaultConverter(UChar ch)
 159     {
 160         return ch;
 161     }
 162
 163     static inline UChar defaultConverter(LChar ch)
 164     {
 165         return ch;
 166     }
 167
 168     inline void addCharactersToHash(UChar a, UChar b)
 169     {
 170         m_hash += a;
 171         unsigned tmp = (b << 11) ^ m_hash;
 172         m_hash = (m_hash << 16) ^ tmp;
 173         m_hash += m_hash >> 11;
 174     }
 175
 176     unsigned m_hash;
 177     bool m_hasPendingCharacter;
 178     UChar m_pendingCharacter;
 179 };
 180
 181 } // namespace WTF
 182
 183 using WTF::StringHasher;
 184
 185 #endif // WTF_StringHasher_h