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/geometry/IntRectExtent.h" 30#include "platform/text/TextRun.h" 31#include "wtf/Forward.h" 32#include "wtf/HashFunctions.h" 33#include "wtf/HashSet.h" 34#include "wtf/HashTableDeletedValueType.h" 35#include "wtf/StringHasher.h" 36 37namespace blink { 38 39struct WidthCacheEntry { 40 WidthCacheEntry() 41 { 42 width = std::numeric_limits<float>::quiet_NaN(); 43 } 44 bool isValid() const { return !std::isnan(width); } 45 float width; 46 IntRectExtent glyphBounds; 47}; 48 49class WidthCache { 50private: 51 // Used to optimize small strings as hash table keys. Avoids malloc'ing an out-of-line StringImpl. 52 class SmallStringKey { 53 public: 54 static unsigned capacity() { return s_capacity; } 55 56 SmallStringKey() 57 : m_length(s_emptyValueLength) 58 { 59 } 60 61 SmallStringKey(WTF::HashTableDeletedValueType) 62 : m_length(s_deletedValueLength) 63 { 64 } 65 66 template<typename CharacterType> SmallStringKey(CharacterType* characters, unsigned short length) 67 : m_length(length) 68 { 69 ASSERT(length <= s_capacity); 70 71 StringHasher hasher; 72 73 bool remainder = length & 1; 74 length >>= 1; 75 76 unsigned i = 0; 77 while (length--) { 78 m_characters[i] = characters[i]; 79 m_characters[i + 1] = characters[i + 1]; 80 hasher.addCharactersAssumingAligned(characters[i], characters[i + 1]); 81 i += 2; 82 } 83 84 if (remainder) { 85 m_characters[i] = characters[i]; 86 hasher.addCharacter(characters[i]); 87 } 88 89 m_hash = hasher.hash(); 90 } 91 92 const UChar* characters() const { return m_characters; } 93 unsigned short length() const { return m_length; } 94 unsigned hash() const { return m_hash; } 95 96 bool isHashTableDeletedValue() const { return m_length == s_deletedValueLength; } 97 bool isHashTableEmptyValue() const { return m_length == s_emptyValueLength; } 98 99 private: 100 static const unsigned s_capacity = 15; 101 static const unsigned s_emptyValueLength = s_capacity + 1; 102 static const unsigned s_deletedValueLength = s_capacity + 2; 103 104 unsigned m_hash; 105 unsigned short m_length; 106 UChar m_characters[s_capacity]; 107 }; 108 109 struct SmallStringKeyHash { 110 static unsigned hash(const SmallStringKey& key) { return key.hash(); } 111 static bool equal(const SmallStringKey& a, const SmallStringKey& b) { return a == b; } 112 static const bool safeToCompareToEmptyOrDeleted = true; // Empty and deleted values have lengths that are not equal to any valid length. 113 }; 114 115 struct SmallStringKeyHashTraits : WTF::SimpleClassHashTraits<SmallStringKey> { 116 static const bool hasIsEmptyValueFunction = true; 117 static bool isEmptyValue(const SmallStringKey& key) { return key.isHashTableEmptyValue(); } 118 static const bool needsDestruction = false; 119 static const unsigned minimumTableSize = 16; 120 }; 121 122 friend bool operator==(const SmallStringKey&, const SmallStringKey&); 123 124public: 125 WidthCache() 126 : m_interval(s_maxInterval) 127 , m_countdown(m_interval) 128 { 129 } 130 131 WidthCacheEntry* add(const TextRun& run, WidthCacheEntry entry) 132 { 133 if (static_cast<unsigned>(run.length()) > SmallStringKey::capacity()) 134 return 0; 135 136 if (m_countdown > 0) { 137 --m_countdown; 138 return 0; 139 } 140 141 return addSlowCase(run, entry); 142 } 143 144 void clear() 145 { 146 m_singleCharMap.clear(); 147 m_map.clear(); 148 } 149 150private: 151 WidthCacheEntry* addSlowCase(const TextRun& run, WidthCacheEntry entry) 152 { 153 int length = run.length(); 154 bool isNewEntry; 155 WidthCacheEntry *value; 156 if (length == 1) { 157 SingleCharMap::AddResult addResult = m_singleCharMap.add(run[0], entry); 158 isNewEntry = addResult.isNewEntry; 159 value = &addResult.storedValue->value; 160 } else { 161 SmallStringKey smallStringKey; 162 if (run.is8Bit()) 163 smallStringKey = SmallStringKey(run.characters8(), length); 164 else 165 smallStringKey = SmallStringKey(run.characters16(), length); 166 167 Map::AddResult addResult = m_map.add(smallStringKey, entry); 168 isNewEntry = addResult.isNewEntry; 169 value = &addResult.storedValue->value; 170 } 171 172 // Cache hit: ramp up by sampling the next few words. 173 if (!isNewEntry) { 174 m_interval = s_minInterval; 175 return value; 176 } 177 178 // Cache miss: ramp down by increasing our sampling interval. 179 if (m_interval < s_maxInterval) 180 ++m_interval; 181 m_countdown = m_interval; 182 183 if ((m_singleCharMap.size() + m_map.size()) < s_maxSize) 184 return value; 185 186 // No need to be fancy: we're just trying to avoid pathological growth. 187 m_singleCharMap.clear(); 188 m_map.clear(); 189 return 0; 190 } 191 192 typedef HashMap<SmallStringKey, WidthCacheEntry, SmallStringKeyHash, SmallStringKeyHashTraits> Map; 193 typedef HashMap<uint32_t, WidthCacheEntry, DefaultHash<uint32_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint32_t> > SingleCharMap; 194 static const int s_minInterval = -3; // A cache hit pays for about 3 cache misses. 195 static const int s_maxInterval = 20; // Sampling at this interval has almost no overhead. 196 static const unsigned s_maxSize = 500000; // Just enough to guard against pathological growth. 197 198 int m_interval; 199 int m_countdown; 200 SingleCharMap m_singleCharMap; 201 Map m_map; 202}; 203 204inline bool operator==(const WidthCache::SmallStringKey& a, const WidthCache::SmallStringKey& b) 205{ 206 if (a.length() != b.length()) 207 return false; 208 return WTF::equal(a.characters(), b.characters(), a.length()); 209} 210 211} // namespace blink 212 213#endif // WidthCache_h 214