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