From da034a9a68ce75b7b7b48758f43f1cb69699549a Mon Sep 17 00:00:00 2001 From: Milian Wolff Date: Mon, 3 Sep 2012 17:45:43 +0200 Subject: Optimize QTextEngine::findItem by using a binary search. This is basically a backport from Qt5: - revert the revert: 22995948cd3f46780be5d8016708aeef0cd7b066 - backport from qtbase: 487583459ea7958f24cd579888a662bcce26caf3 this fixes the off-by-one error in the binary search Task-number: QTBUG-17209 Task-number: QTBUG-231 Change-Id: I7f62fb33cf919ecd7fb2246ae01bb23559e11bf4 Reviewed-by: Jiang Jiang --- src/gui/text/qtextengine.cpp | 17 ++++++++++++----- 1 file changed, 12 insertions(+), 5 deletions(-) diff --git a/src/gui/text/qtextengine.cpp b/src/gui/text/qtextengine.cpp index 3af0355..bb453d5 100644 --- a/src/gui/text/qtextengine.cpp +++ b/src/gui/text/qtextengine.cpp @@ -1656,12 +1656,19 @@ int QTextEngine::findItem(int strPos) const { itemize(); - int item; - for (item = layoutData->items.size()-1; item > 0; --item) { - if (layoutData->items[item].position <= strPos) - break; + int left = 1; + int right = layoutData->items.size()-1; + while (left <= right) { + int middle = ((right-left)/2)+left; + if (strPos > layoutData->items[middle].position) + left = middle+1; + else if (strPos < layoutData->items[middle].position) + right = middle-1; + else { + return middle; + } } - return item; + return right; } QFixed QTextEngine::width(int from, int len) const -- cgit v0.12