src/third_party/WebKit/Source/platform/fonts/WidthCache.h

   1 /*
   2  * Copyright (C) 2012 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #ifndef WidthCache_h
  27 #define WidthCache_h
  28
  29 #include "platform/text/TextRun.h"
  30 #include "wtf/Forward.h"
  31 #include "wtf/HashFunctions.h"
  32 #include "wtf/HashSet.h"
  33 #include "wtf/HashTableDeletedValueType.h"
  34 #include "wtf/StringHasher.h"
  35
  36 namespace WebCore {
  37
  38 struct GlyphOverflow;
  39
  40 class WidthCache {
  41 private:
  42     // Used to optimize small strings as hash table keys. Avoids malloc'ing an out-of-line StringImpl.
  43     class SmallStringKey {
  44     public:
  45         static unsigned capacity() { return s_capacity; }
  46
  47         SmallStringKey()
  48             : m_length(s_emptyValueLength)
  49         {
  50         }
  51
  52         SmallStringKey(WTF::HashTableDeletedValueType)
  53             : m_length(s_deletedValueLength)
  54         {
  55         }
  56
  57         template<typename CharacterType> SmallStringKey(CharacterType* characters, unsigned short length)
  58             : m_length(length)
  59         {
  60             ASSERT(length <= s_capacity);
  61
  62             StringHasher hasher;
  63
  64             bool remainder = length & 1;
  65             length >>= 1;
  66
  67             unsigned i = 0;
  68             while (length--) {
  69                 m_characters[i] = characters[i];
  70                 m_characters[i + 1] = characters[i + 1];
  71                 hasher.addCharactersAssumingAligned(characters[i], characters[i + 1]);
  72                 i += 2;
  73             }
  74
  75             if (remainder) {
  76                 m_characters[i] = characters[i];
  77                 hasher.addCharacter(characters[i]);
  78             }
  79
  80             m_hash = hasher.hash();
  81         }
  82
  83         const UChar* characters() const { return m_characters; }
  84         unsigned short length() const { return m_length; }
  85         unsigned hash() const { return m_hash; }
  86
  87         bool isHashTableDeletedValue() const { return m_length == s_deletedValueLength; }
  88         bool isHashTableEmptyValue() const { return m_length == s_emptyValueLength; }
  89
  90     private:
  91         static const unsigned s_capacity = 15;
  92         static const unsigned s_emptyValueLength = s_capacity + 1;
  93         static const unsigned s_deletedValueLength = s_capacity + 2;
  94
  95         unsigned m_hash;
  96         unsigned short m_length;
  97         UChar m_characters[s_capacity];
  98     };
  99
 100     struct SmallStringKeyHash {
 101         static unsigned hash(const SmallStringKey& key) { return key.hash(); }
 102         static bool equal(const SmallStringKey& a, const SmallStringKey& b) { return a == b; }
 103         static const bool safeToCompareToEmptyOrDeleted = true; // Empty and deleted values have lengths that are not equal to any valid length.
 104     };
 105
 106     struct SmallStringKeyHashTraits : WTF::SimpleClassHashTraits<SmallStringKey> {
 107         static const bool hasIsEmptyValueFunction = true;
 108         static bool isEmptyValue(const SmallStringKey& key) { return key.isHashTableEmptyValue(); }
 109         static const bool needsDestruction = false;
 110         static const unsigned minimumTableSize = 16;
 111     };
 112
 113     friend bool operator==(const SmallStringKey&, const SmallStringKey&);
 114
 115 public:
 116     WidthCache()
 117         : m_interval(s_maxInterval)
 118         , m_countdown(m_interval)
 119     {
 120     }
 121
 122     float* add(const TextRun& run, float entry, bool hasKerningOrLigatures, bool hasWordSpacingOrLetterSpacing, GlyphOverflow* glyphOverflow)
 123     {
 124         // The width cache is not really profitable unless we're doing expensive glyph transformations.
 125         if (!hasKerningOrLigatures)
 126             return 0;
 127         // Word spacing and letter spacing can change the width of a word.
 128         if (hasWordSpacingOrLetterSpacing)
 129             return 0;
 130         // Since this is just a width cache, we don't have enough information to satisfy glyph queries.
 131         if (glyphOverflow)
 132             return 0;
 133         // If we allow tabs and a tab occurs inside a word, the width of the word varies based on its position on the line.
 134         if (run.allowTabs())
 135             return 0;
 136         if (static_cast<unsigned>(run.length()) > SmallStringKey::capacity())
 137             return 0;
 138
 139         if (m_countdown > 0) {
 140             --m_countdown;
 141             return 0;
 142         }
 143
 144         return addSlowCase(run, entry);
 145     }
 146
 147     void clear()
 148     {
 149         m_singleCharMap.clear();
 150         m_map.clear();
 151     }
 152
 153 private:
 154     float* addSlowCase(const TextRun& run, float entry)
 155     {
 156         int length = run.length();
 157         bool isNewEntry;
 158         float *value;
 159         if (length == 1) {
 160             SingleCharMap::AddResult addResult = m_singleCharMap.add(run[0], entry);
 161             isNewEntry = addResult.isNewEntry;
 162             value = &addResult.iterator->value;
 163         } else {
 164             SmallStringKey smallStringKey;
 165             if (run.is8Bit())
 166                 smallStringKey = SmallStringKey(run.characters8(), length);
 167             else
 168                 smallStringKey = SmallStringKey(run.characters16(), length);
 169
 170             Map::AddResult addResult = m_map.add(smallStringKey, entry);
 171             isNewEntry = addResult.isNewEntry;
 172             value = &addResult.iterator->value;
 173         }
 174
 175         // Cache hit: ramp up by sampling the next few words.
 176         if (!isNewEntry) {
 177             m_interval = s_minInterval;
 178             return value;
 179         }
 180
 181         // Cache miss: ramp down by increasing our sampling interval.
 182         if (m_interval < s_maxInterval)
 183             ++m_interval;
 184         m_countdown = m_interval;
 185
 186         if ((m_singleCharMap.size() + m_map.size()) < s_maxSize)
 187             return value;
 188
 189         // No need to be fancy: we're just trying to avoid pathological growth.
 190         m_singleCharMap.clear();
 191         m_map.clear();
 192         return 0;
 193     }
 194
 195     typedef HashMap<SmallStringKey, float, SmallStringKeyHash, SmallStringKeyHashTraits> Map;
 196     typedef HashMap<uint32_t, float, DefaultHash<uint32_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint32_t> > SingleCharMap;
 197     static const int s_minInterval = -3; // A cache hit pays for about 3 cache misses.
 198     static const int s_maxInterval = 20; // Sampling at this interval has almost no overhead.
 199     static const unsigned s_maxSize = 500000; // Just enough to guard against pathological growth.
 200
 201     int m_interval;
 202     int m_countdown;
 203     SingleCharMap m_singleCharMap;
 204     Map m_map;
 205 };
 206
 207 inline bool operator==(const WidthCache::SmallStringKey& a, const WidthCache::SmallStringKey& b)
 208 {
 209     if (a.length() != b.length())
 210         return false;
 211     return WTF::equal(a.characters(), b.characters(), a.length());
 212 }
 213
 214 } // namespace WebCore
 215
 216 #endif // WidthCache_h