OLD | NEW |
| (Empty) |
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/graphics/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 o
ut-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* character
s, 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_deletedValue
Length; } | |
88 bool isHashTableEmptyValue() const { return m_length == s_emptyValueLeng
th; } | |
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) { re
turn a == b; } | |
103 static const bool safeToCompareToEmptyOrDeleted = true; // Empty and del
eted 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.isHashT
ableEmptyValue(); } | |
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 wor
d 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], ent
ry); | |
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, SmallStringKeyHas
hTraits> Map; | |
196 typedef HashMap<uint32_t, float, DefaultHash<uint32_t>::Hash, WTF::UnsignedW
ithZeroKeyHashTraits<uint32_t> > SingleCharMap; | |
197 static const int s_minInterval = -3; // A cache hit pays for about 3 cache m
isses. | |
198 static const int s_maxInterval = 20; // Sampling at this interval has almost
no overhead. | |
199 static const int s_maxSize = 500000; // Just enough to guard against patholo
gical 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::Sm
allStringKey& 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 | |
OLD | NEW |