From c13011829fd39661cc9e983256766c6edb88dead Mon Sep 17 00:00:00 2001 From: Olivier Goffart Date: Thu, 19 Jul 2012 14:42:37 +0200 Subject: Speed up QTextEngine::setBoundary Before, setBoundary was O(N), now it is O(log N) assuming the boundaries are added in order. (splitItem might still be linear because of the call to QVector::insert) This speeds up a lot QTextEngine::addRequiredBoundaries when there is a lot of addFormats. (For example if there is a very long line with syntax highlighting) Task-number: QTBUG-8389 Change-Id: I10c9fca72343f46db24b1d4f519f7747188d4009 Reviewed-by: Lars Knoll --- src/gui/text/qtextengine.cpp | 20 ++++++++++++++------ 1 file changed, 14 insertions(+), 6 deletions(-) diff --git a/src/gui/text/qtextengine.cpp b/src/gui/text/qtextengine.cpp index a9c57dfa05..6abdbdaa2a 100644 --- a/src/gui/text/qtextengine.cpp +++ b/src/gui/text/qtextengine.cpp @@ -2535,20 +2535,28 @@ QString QTextEngine::elidedText(Qt::TextElideMode mode, const QFixed &width, int return layoutData->string.mid(from, to - from); } +namespace { +struct QScriptItemComparator { + bool operator()(const QScriptItem &a, const QScriptItem &b) { return a.position < b.position; } + bool operator()(int p, const QScriptItem &b) { return p < b.position; } + //bool operator()(const QScriptItem &a, int p) { return a.position < p; } +}; +} + void QTextEngine::setBoundary(int strPos) const { if (strPos <= 0 || strPos >= layoutData->string.length()) return; - int itemToSplit = 0; - while (itemToSplit < layoutData->items.size() && layoutData->items.at(itemToSplit).position <= strPos) - itemToSplit++; - itemToSplit--; - if (layoutData->items.at(itemToSplit).position == strPos) { + const QScriptItem* it = qUpperBound(layoutData->items.constBegin(), layoutData->items.constEnd(), + strPos, QScriptItemComparator()); + Q_ASSERT(it > layoutData->items.constBegin()); + --it; + if (it->position == strPos) { // already a split at the requested position return; } - splitItem(itemToSplit, strPos - layoutData->items.at(itemToSplit).position); + splitItem(it - layoutData->items.constBegin(), strPos - it->position); } void QTextEngine::splitItem(int item, int pos) const -- cgit v1.2.3