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 "TextRun.h"
30#include <wtf/Forward.h>
31#include <wtf/HashFunctions.h>
32#include <wtf/HashSet.h>
33#include <wtf/Hasher.h>
34#include <wtf/MemoryPressureHandler.h>
35
36namespace WebCore {
37
38struct GlyphOverflow;
39
40class WidthCache {
41private:
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 int minimumTableSize = 16;
110 };
111
112 friend bool operator==(const SmallStringKey&, const SmallStringKey&);
113
114public:
115 WidthCache()
116 : m_interval(s_maxInterval)
117 , m_countdown(m_interval)
118 {
119 }
120
121 float* add(StringView text, float entry)
122 {
123 if (MemoryPressureHandler::singleton().isUnderMemoryPressure())
124 return nullptr;
125
126 if (text.length() > SmallStringKey::capacity())
127 return nullptr;
128
129 if (m_countdown > 0) {
130 --m_countdown;
131 return nullptr;
132 }
133 return addSlowCase(text, entry);
134 }
135
136 float* add(const TextRun& run, float entry, bool hasKerningOrLigatures, bool hasWordSpacingOrLetterSpacing, GlyphOverflow* glyphOverflow)
137 {
138 if (MemoryPressureHandler::singleton().isUnderMemoryPressure())
139 return nullptr;
140 // The width cache is not really profitable unless we're doing expensive glyph transformations.
141 if (!hasKerningOrLigatures)
142 return nullptr;
143 // Word spacing and letter spacing can change the width of a word.
144 if (hasWordSpacingOrLetterSpacing)
145 return nullptr;
146 // Since this is just a width cache, we don't have enough information to satisfy glyph queries.
147 if (glyphOverflow)
148 return nullptr;
149 // If we allow tabs and a tab occurs inside a word, the width of the word varies based on its position on the line.
150 if (run.allowTabs())
151 return nullptr;
152 if (run.length() > SmallStringKey::capacity())
153 return nullptr;
154
155 if (m_countdown > 0) {
156 --m_countdown;
157 return nullptr;
158 }
159
160 return addSlowCase(run.text(), entry);
161 }
162
163 void clear()
164 {
165 m_singleCharMap.clear();
166 m_map.clear();
167 }
168
169private:
170
171 float* addSlowCase(StringView text, float entry)
172 {
173 int length = text.length();
174 bool isNewEntry;
175 float* value;
176 if (length == 1) {
177 SingleCharMap::AddResult addResult = m_singleCharMap.fastAdd(text[0], entry);
178 isNewEntry = addResult.isNewEntry;
179 value = &addResult.iterator->value;
180 } else {
181 SmallStringKey smallStringKey;
182 if (text.is8Bit())
183 smallStringKey = SmallStringKey(text.characters8(), length);
184 else
185 smallStringKey = SmallStringKey(text.characters16(), length);
186
187 Map::AddResult addResult = m_map.fastAdd(smallStringKey, entry);
188 isNewEntry = addResult.isNewEntry;
189 value = &addResult.iterator->value;
190 }
191
192 // Cache hit: ramp up by sampling the next few words.
193 if (!isNewEntry) {
194 m_interval = s_minInterval;
195 return value;
196 }
197
198 // Cache miss: ramp down by increasing our sampling interval.
199 if (m_interval < s_maxInterval)
200 ++m_interval;
201 m_countdown = m_interval;
202
203 if ((m_singleCharMap.size() + m_map.size()) < s_maxSize)
204 return value;
205
206 // No need to be fancy: we're just trying to avoid pathological growth.
207 m_singleCharMap.clear();
208 m_map.clear();
209 return nullptr;
210 }
211
212 typedef HashMap<SmallStringKey, float, SmallStringKeyHash, SmallStringKeyHashTraits> Map;
213 typedef HashMap<uint32_t, float, DefaultHash<uint32_t>::Hash, WTF::UnsignedWithZeroKeyHashTraits<uint32_t>> SingleCharMap;
214 static const int s_minInterval = -3; // A cache hit pays for about 3 cache misses.
215 static const int s_maxInterval = 20; // Sampling at this interval has almost no overhead.
216 static const int s_maxSize = 500000; // Just enough to guard against pathological growth.
217
218 int m_interval;
219 int m_countdown;
220 SingleCharMap m_singleCharMap;
221 Map m_map;
222};
223
224inline bool operator==(const WidthCache::SmallStringKey& a, const WidthCache::SmallStringKey& b)
225{
226 if (a.length() != b.length())
227 return false;
228 return WTF::equal(a.characters(), b.characters(), a.length());
229}
230
231} // namespace WebCore
232
233#endif // WidthCache_h
234