OLD | NEW |
---|---|
1 /* | 1 /* |
2 * Copyright (C) 2012 Apple Inc. All rights reserved. | 2 * Copyright (C) 2012 Apple Inc. All rights reserved. |
3 * Copyright (C) 2015 Google Inc. All rights reserved. | |
3 * | 4 * |
4 * Redistribution and use in source and binary forms, with or without | 5 * Redistribution and use in source and binary forms, with or without |
5 * modification, are permitted provided that the following conditions | 6 * modification, are permitted provided that the following conditions |
6 * are met: | 7 * are met: |
7 * 1. Redistributions of source code must retain the above copyright | 8 * 1. Redistributions of source code must retain the above copyright |
8 * notice, this list of conditions and the following disclaimer. | 9 * notice, this list of conditions and the following disclaimer. |
9 * 2. Redistributions in binary form must reproduce the above copyright | 10 * 2. Redistributions in binary form must reproduce the above copyright |
10 * notice, this list of conditions and the following disclaimer in the | 11 * notice, this list of conditions and the following disclaimer in the |
11 * documentation and/or other materials provided with the distribution. | 12 * documentation and/or other materials provided with the distribution. |
12 * | 13 * |
13 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY | 14 * THIS SOFTWARE IS PROVIDED BY GOOGLE INC. ``AS IS'' AND ANY |
leviw_travelin_and_unemployed
2015/06/22 18:52:08
Are we supposed to make this change?
eae
2015/06/22 19:19:53
Oops, good catch. Only for _new_ files. Thanks!
| |
14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE | 15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE |
15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR | 16 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR |
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR | 17 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR |
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, | 18 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, |
18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, | 19 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, |
19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR | 20 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR |
20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY | 21 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY |
21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 22 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 23 * (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 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
24 */ | 25 */ |
25 | 26 |
26 #ifndef WidthCache_h | 27 #ifndef ShapeCache_h |
27 #define WidthCache_h | 28 #define ShapeCache_h |
28 | 29 |
29 #include "platform/geometry/FloatRectOutsets.h" | 30 #include "platform/fonts/shaping/HarfBuzzShaper.h" |
30 #include "platform/text/TextRun.h" | 31 #include "platform/text/TextRun.h" |
31 #include "wtf/Forward.h" | 32 #include "wtf/Forward.h" |
32 #include "wtf/HashFunctions.h" | 33 #include "wtf/HashFunctions.h" |
33 #include "wtf/HashSet.h" | 34 #include "wtf/HashSet.h" |
34 #include "wtf/HashTableDeletedValueType.h" | 35 #include "wtf/HashTableDeletedValueType.h" |
35 #include "wtf/StringHasher.h" | 36 #include "wtf/StringHasher.h" |
36 | 37 |
37 namespace blink { | 38 namespace blink { |
38 | 39 |
39 struct WidthCacheEntry { | 40 class Font; |
40 WidthCacheEntry() | 41 class GlyphBuffer; |
42 class SimpleFontData; | |
43 class HarfBuzzShaper; | |
44 | |
45 struct ShapeCacheEntry { | |
46 ShapeCacheEntry() | |
41 { | 47 { |
42 width = std::numeric_limits<float>::quiet_NaN(); | 48 m_shapeResult = nullptr; |
43 } | 49 } |
44 bool isValid() const { return !std::isnan(width); } | 50 RefPtr<ShapeResult> m_shapeResult; |
45 float width; | |
46 FloatRect glyphBounds; | |
47 }; | 51 }; |
48 | 52 |
49 class WidthCache { | 53 class ShapeCache { |
50 private: | 54 private: |
51 // Used to optimize small strings as hash table keys. Avoids malloc'ing an o ut-of-line StringImpl. | 55 // Used to optimize small strings as hash table keys. Avoids malloc'ing an o ut-of-line StringImpl. |
52 class SmallStringKey { | 56 class SmallStringKey { |
53 public: | 57 public: |
54 static unsigned capacity() { return s_capacity; } | 58 static unsigned capacity() { return s_capacity; } |
55 | 59 |
56 SmallStringKey() | 60 SmallStringKey() |
57 : m_length(s_emptyValueLength) | 61 : m_length(s_emptyValueLength), m_direction(LTR) |
58 { | 62 { |
59 } | 63 } |
60 | 64 |
61 SmallStringKey(WTF::HashTableDeletedValueType) | 65 SmallStringKey(WTF::HashTableDeletedValueType) |
62 : m_length(s_deletedValueLength) | 66 : m_length(s_deletedValueLength), m_direction(LTR) |
63 { | 67 { |
64 } | 68 } |
65 | 69 |
66 template<typename CharacterType> SmallStringKey(CharacterType* character s, unsigned short length) | 70 template<typename CharacterType> SmallStringKey(CharacterType* character s, unsigned short length, TextDirection direction) |
67 : m_length(length) | 71 : m_length(length), m_direction(direction) |
68 { | 72 { |
69 ASSERT(length <= s_capacity); | 73 ASSERT(length <= s_capacity); |
70 | 74 |
71 StringHasher hasher; | 75 StringHasher hasher; |
72 | 76 |
73 bool remainder = length & 1; | 77 bool remainder = length & 1; |
74 length >>= 1; | 78 length >>= 1; |
75 | 79 |
76 unsigned i = 0; | 80 unsigned i = 0; |
77 while (length--) { | 81 while (length--) { |
78 m_characters[i] = characters[i]; | 82 m_characters[i] = characters[i]; |
79 m_characters[i + 1] = characters[i + 1]; | 83 m_characters[i + 1] = characters[i + 1]; |
80 hasher.addCharactersAssumingAligned(characters[i], characters[i + 1]); | 84 hasher.addCharactersAssumingAligned(characters[i], characters[i + 1]); |
81 i += 2; | 85 i += 2; |
82 } | 86 } |
83 | 87 |
84 if (remainder) { | 88 if (remainder) { |
85 m_characters[i] = characters[i]; | 89 m_characters[i] = characters[i]; |
86 hasher.addCharacter(characters[i]); | 90 hasher.addCharacter(characters[i]); |
87 } | 91 } |
88 | 92 |
89 m_hash = hasher.hash(); | 93 m_hash = hasher.hash(); |
90 } | 94 } |
91 | 95 |
92 const UChar* characters() const { return m_characters; } | 96 const UChar* characters() const { return m_characters; } |
93 unsigned short length() const { return m_length; } | 97 unsigned short length() const { return m_length; } |
98 TextDirection direction() const { return static_cast<TextDirection>(m_di rection); } | |
94 unsigned hash() const { return m_hash; } | 99 unsigned hash() const { return m_hash; } |
95 | 100 |
96 bool isHashTableDeletedValue() const { return m_length == s_deletedValue Length; } | 101 bool isHashTableDeletedValue() const { return m_length == s_deletedValue Length; } |
97 bool isHashTableEmptyValue() const { return m_length == s_emptyValueLeng th; } | 102 bool isHashTableEmptyValue() const { return m_length == s_emptyValueLeng th; } |
98 | 103 |
99 private: | 104 private: |
100 static const unsigned s_capacity = 15; | 105 static const unsigned s_capacity = 15; |
101 static const unsigned s_emptyValueLength = s_capacity + 1; | 106 static const unsigned s_emptyValueLength = s_capacity + 1; |
102 static const unsigned s_deletedValueLength = s_capacity + 2; | 107 static const unsigned s_deletedValueLength = s_capacity + 2; |
103 | 108 |
104 unsigned m_hash; | 109 unsigned m_hash; |
105 unsigned short m_length; | 110 unsigned m_length : 15; |
111 unsigned m_direction : 1; | |
106 UChar m_characters[s_capacity]; | 112 UChar m_characters[s_capacity]; |
107 }; | 113 }; |
108 | 114 |
109 struct SmallStringKeyHash { | 115 struct SmallStringKeyHash { |
110 static unsigned hash(const SmallStringKey& key) { return key.hash(); } | 116 static unsigned hash(const SmallStringKey& key) { return key.hash(); } |
111 static bool equal(const SmallStringKey& a, const SmallStringKey& b) { re turn a == b; } | 117 static bool equal(const SmallStringKey& a, const SmallStringKey& b) { re turn a == b; } |
112 static const bool safeToCompareToEmptyOrDeleted = true; // Empty and del eted values have lengths that are not equal to any valid length. | 118 static const bool safeToCompareToEmptyOrDeleted = true; // Empty and del eted values have lengths that are not equal to any valid length. |
113 }; | 119 }; |
114 | 120 |
115 struct SmallStringKeyHashTraits : WTF::SimpleClassHashTraits<SmallStringKey> { | 121 struct SmallStringKeyHashTraits : WTF::SimpleClassHashTraits<SmallStringKey> { |
116 static const bool hasIsEmptyValueFunction = true; | 122 static const bool hasIsEmptyValueFunction = true; |
117 static bool isEmptyValue(const SmallStringKey& key) { return key.isHashT ableEmptyValue(); } | 123 static bool isEmptyValue(const SmallStringKey& key) { return key.isHashT ableEmptyValue(); } |
118 static const unsigned minimumTableSize = 16; | 124 static const unsigned minimumTableSize = 16; |
119 }; | 125 }; |
120 | 126 |
121 friend bool operator==(const SmallStringKey&, const SmallStringKey&); | 127 friend bool operator==(const SmallStringKey&, const SmallStringKey&); |
122 | 128 |
123 public: | 129 public: |
124 WidthCache() | 130 ShapeCache() { } |
125 : m_interval(s_maxInterval) | |
126 , m_countdown(m_interval) | |
127 { | |
128 } | |
129 | 131 |
130 WidthCacheEntry* add(const TextRun& run, WidthCacheEntry entry) | 132 ShapeCacheEntry* add(const TextRun& run, ShapeCacheEntry entry) |
131 { | 133 { |
132 if (static_cast<unsigned>(run.length()) > SmallStringKey::capacity()) | 134 if (static_cast<unsigned>(run.length()) > SmallStringKey::capacity()) |
133 return 0; | 135 return 0; |
134 | 136 |
135 if (m_countdown > 0) { | |
136 --m_countdown; | |
137 return 0; | |
138 } | |
139 | |
140 return addSlowCase(run, entry); | 137 return addSlowCase(run, entry); |
141 } | 138 } |
142 | 139 |
143 void clear() | 140 void clear() |
144 { | 141 { |
145 m_singleCharMap.clear(); | 142 m_singleCharMap.clear(); |
146 m_map.clear(); | 143 m_map.clear(); |
147 } | 144 } |
148 | 145 |
149 private: | 146 private: |
150 WidthCacheEntry* addSlowCase(const TextRun& run, WidthCacheEntry entry) | 147 ShapeCacheEntry* addSlowCase(const TextRun& run, ShapeCacheEntry entry) |
151 { | 148 { |
152 int length = run.length(); | 149 int length = run.length(); |
153 bool isNewEntry; | 150 bool isNewEntry; |
154 WidthCacheEntry *value; | 151 ShapeCacheEntry *value; |
155 if (length == 1) { | 152 if (length == 1) { |
156 SingleCharMap::AddResult addResult = m_singleCharMap.add(run[0], ent ry); | 153 SingleCharMap::AddResult addResult = m_singleCharMap.add(run[0], ent ry); |
157 isNewEntry = addResult.isNewEntry; | 154 isNewEntry = addResult.isNewEntry; |
158 value = &addResult.storedValue->value; | 155 value = &addResult.storedValue->value; |
159 } else { | 156 } else { |
160 SmallStringKey smallStringKey; | 157 SmallStringKey smallStringKey; |
161 if (run.is8Bit()) | 158 if (run.is8Bit()) |
162 smallStringKey = SmallStringKey(run.characters8(), length); | 159 smallStringKey = SmallStringKey(run.characters8(), length, run.d irection()); |
163 else | 160 else |
164 smallStringKey = SmallStringKey(run.characters16(), length); | 161 smallStringKey = SmallStringKey(run.characters16(), length, run. direction()); |
165 | 162 |
166 Map::AddResult addResult = m_map.add(smallStringKey, entry); | 163 Map::AddResult addResult = m_map.add(smallStringKey, entry); |
167 isNewEntry = addResult.isNewEntry; | 164 isNewEntry = addResult.isNewEntry; |
168 value = &addResult.storedValue->value; | 165 value = &addResult.storedValue->value; |
169 } | 166 } |
170 | 167 |
171 // Cache hit: ramp up by sampling the next few words. | 168 // Cache hit: ramp up by sampling the next few words. |
172 if (!isNewEntry) { | 169 if (!isNewEntry) { |
173 m_interval = s_minInterval; | |
174 return value; | 170 return value; |
175 } | 171 } |
176 | 172 |
177 // Cache miss: ramp down by increasing our sampling interval. | 173 if ((m_singleCharMap.size() + m_map.size()) < s_maxSize) { |
leviw_travelin_and_unemployed
2015/06/22 18:52:08
Nit: unnecessary braces.
eae
2015/06/22 19:19:53
Done.
| |
178 if (m_interval < s_maxInterval) | |
179 ++m_interval; | |
180 m_countdown = m_interval; | |
181 | |
182 if ((m_singleCharMap.size() + m_map.size()) < s_maxSize) | |
183 return value; | 174 return value; |
175 } | |
184 | 176 |
185 // No need to be fancy: we're just trying to avoid pathological growth. | 177 // No need to be fancy: we're just trying to avoid pathological growth. |
186 m_singleCharMap.clear(); | 178 m_singleCharMap.clear(); |
187 m_map.clear(); | 179 m_map.clear(); |
180 | |
188 return 0; | 181 return 0; |
189 } | 182 } |
190 | 183 |
191 typedef HashMap<SmallStringKey, WidthCacheEntry, SmallStringKeyHash, SmallSt ringKeyHashTraits> Map; | 184 typedef HashMap<SmallStringKey, ShapeCacheEntry, SmallStringKeyHash, SmallSt ringKeyHashTraits> Map; |
leviw_travelin_and_unemployed
2015/06/22 18:52:08
Nit: Maybe a slightly more descriptive name?
eae
2015/06/22 19:19:53
Done.
| |
192 typedef HashMap<uint32_t, WidthCacheEntry, DefaultHash<uint32_t>::Hash, WTF: :UnsignedWithZeroKeyHashTraits<uint32_t>> SingleCharMap; | 185 typedef HashMap<uint32_t, ShapeCacheEntry, DefaultHash<uint32_t>::Hash, WTF: :UnsignedWithZeroKeyHashTraits<uint32_t>> SingleCharMap; |
193 static const int s_minInterval = -3; // A cache hit pays for about 3 cache m isses. | 186 static const unsigned s_maxSize = 10000; |
leviw_travelin_and_unemployed
2015/06/22 18:52:08
Magic #1 replaced by magic #2 :p
It'd be nice if
eae
2015/06/22 19:19:53
Done.
| |
194 static const int s_maxInterval = 20; // Sampling at this interval has almost no overhead. | |
195 static const unsigned s_maxSize = 500000; // Just enough to guard against pa thological growth. | |
196 | 187 |
197 int m_interval; | |
198 int m_countdown; | |
199 SingleCharMap m_singleCharMap; | 188 SingleCharMap m_singleCharMap; |
200 Map m_map; | 189 Map m_map; |
201 }; | 190 }; |
202 | 191 |
203 inline bool operator==(const WidthCache::SmallStringKey& a, const WidthCache::Sm allStringKey& b) | 192 inline bool operator==(const ShapeCache::SmallStringKey& a, const ShapeCache::Sm allStringKey& b) |
204 { | 193 { |
205 if (a.length() != b.length()) | 194 if (a.length() != b.length() || a.direction() != b.direction()) |
206 return false; | 195 return false; |
207 return WTF::equal(a.characters(), b.characters(), a.length()); | 196 return WTF::equal(a.characters(), b.characters(), a.length()); |
208 } | 197 } |
209 | 198 |
210 } // namespace blink | 199 } // namespace blink |
211 | 200 |
212 #endif // WidthCache_h | 201 #endif // ShapeCache_h |
OLD | NEW |