Title: [262803] trunk/Source/WebCore
- Revision
- 262803
- Author
- [email protected]
- Date
- 2020-06-09 12:39:46 -0700 (Tue, 09 Jun 2020)
Log Message
ComplexTextController: Use std::sort to calculate m_runIndices
https://bugs.webkit.org/show_bug.cgi?id=212944
Reviewed by Myles C. Maxfield.
ComplexTextController was using O(n²) sort to lazily calculate
m_runIndices. And, exact matching stringBegin and stringEnd can
cause infinite loop (Bug 212670 and Bug 108877).
Use std::sort instead.
* platform/graphics/ComplexTextController.cpp:
(WebCore::ComplexTextController::finishConstruction):
(WebCore::ComplexTextController::indexOfCurrentRun):
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (262802 => 262803)
--- trunk/Source/WebCore/ChangeLog 2020-06-09 19:08:20 UTC (rev 262802)
+++ trunk/Source/WebCore/ChangeLog 2020-06-09 19:39:46 UTC (rev 262803)
@@ -1,3 +1,20 @@
+2020-06-09 Fujii Hironori <[email protected]>
+
+ ComplexTextController: Use std::sort to calculate m_runIndices
+ https://bugs.webkit.org/show_bug.cgi?id=212944
+
+ Reviewed by Myles C. Maxfield.
+
+ ComplexTextController was using O(n²) sort to lazily calculate
+ m_runIndices. And, exact matching stringBegin and stringEnd can
+ cause infinite loop (Bug 212670 and Bug 108877).
+
+ Use std::sort instead.
+
+ * platform/graphics/ComplexTextController.cpp:
+ (WebCore::ComplexTextController::finishConstruction):
+ (WebCore::ComplexTextController::indexOfCurrentRun):
+
2020-06-09 Youenn Fablet <[email protected]>
BaseAudioSharedUnit should unmute its clients in case of suspension even if not having any audio unit
Modified: trunk/Source/WebCore/platform/graphics/ComplexTextController.cpp (262802 => 262803)
--- trunk/Source/WebCore/platform/graphics/ComplexTextController.cpp 2020-06-09 19:08:20 UTC (rev 262802)
+++ trunk/Source/WebCore/platform/graphics/ComplexTextController.cpp 2020-06-09 19:39:46 UTC (rev 262803)
@@ -150,11 +150,18 @@
adjustGlyphsAndAdvances();
if (!m_isLTROnly) {
- m_runIndices.reserveInitialCapacity(m_complexTextRuns.size());
+ unsigned length = m_complexTextRuns.size();
+ m_runIndices.reserveInitialCapacity(length);
+ for (unsigned i = 0; i < length; ++i)
+ m_runIndices.uncheckedAppend(length - i - 1);
+ std::sort(m_runIndices.data(), m_runIndices.data() + length,
+ [this](auto a, auto b) {
+ return stringBegin(*m_complexTextRuns[a]) < stringBegin(*m_complexTextRuns[b]);
+ });
- m_glyphCountFromStartToIndex.reserveInitialCapacity(m_complexTextRuns.size());
+ m_glyphCountFromStartToIndex.reserveInitialCapacity(length);
unsigned glyphCountSoFar = 0;
- for (unsigned i = 0; i < m_complexTextRuns.size(); ++i) {
+ for (unsigned i = 0; i < length; ++i) {
m_glyphCountFromStartToIndex.uncheckedAppend(glyphCountSoFar);
glyphCountSoFar += m_complexTextRuns[i]->glyphCount();
}
@@ -509,30 +516,6 @@
return m_currentRun;
}
- if (m_runIndices.isEmpty()) {
- unsigned firstRun = 0;
- unsigned firstRunOffset = stringBegin(*m_complexTextRuns[0]);
- for (unsigned i = 1; i < runCount; ++i) {
- unsigned offset = stringBegin(*m_complexTextRuns[i]);
- if (offset < firstRunOffset) {
- firstRun = i;
- firstRunOffset = offset;
- }
- }
- m_runIndices.uncheckedAppend(firstRun);
- }
-
- while (m_runIndices.size() <= m_currentRun) {
- unsigned offset = stringEnd(*m_complexTextRuns[m_runIndices.last()]);
-
- for (unsigned i = 0; i < runCount; ++i) {
- if (offset == stringBegin(*m_complexTextRuns[i])) {
- m_runIndices.uncheckedAppend(i);
- break;
- }
- }
- }
-
unsigned currentRunIndex = m_runIndices[m_currentRun];
leftmostGlyph = m_glyphCountFromStartToIndex[currentRunIndex];
return currentRunIndex;
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
