From 360f596183969a4c690c77df08d94101428c97c0 Mon Sep 17 00:00:00 2001
From: Konstantin Ritt <ritt.ks@gmail.com>
Date: Mon, 22 Nov 2010 15:20:42 +0100
Subject: optimize ligatureHelper by using qBinaryFind instead of the for loop

Merge-request: 890
Reviewed-by: Olivier Goffart <olivier.goffart@nokia.com>
---
 src/corelib/tools/qchar.cpp | 26 +++++++++++++++++++-------
 1 file changed, 19 insertions(+), 7 deletions(-)

diff --git a/src/corelib/tools/qchar.cpp b/src/corelib/tools/qchar.cpp
index bb777cd..43b1552 100644
--- a/src/corelib/tools/qchar.cpp
+++ b/src/corelib/tools/qchar.cpp
@@ -48,11 +48,11 @@
 #  undef QT_NO_CAST_TO_ASCII
 #endif
 #include "qchar.h"
+
 #include "qdatastream.h"
 #include "qtextcodec.h"
 
 #include "qunicodetables_p.h"
-
 #include "qunicodetables.cpp"
 
 QT_BEGIN_NAMESPACE
@@ -1489,6 +1489,16 @@ static void decomposeHelper(QString *str, bool canonical, QChar::UnicodeVersion
 }
 
 
+struct UCS2Pair {
+    ushort u1;
+    ushort u2;
+};
+
+static inline bool operator<(ushort u1, const UCS2Pair &ligature)
+{ return u1 < ligature.u1; }
+static inline bool operator<(const UCS2Pair &ligature, ushort u1)
+{ return ligature.u1 < u1; }
+
 static ushort ligatureHelper(ushort u1, ushort u2)
 {
     // hangul L-V pair
@@ -1511,12 +1521,14 @@ static ushort ligatureHelper(ushort u1, ushort u2)
     if (index == 0xffff)
         return 0;
     const unsigned short *ligatures = uc_ligature_map+index;
-    ushort length = *ligatures;
-    ++ligatures;
-    // ### use bsearch
-    for (uint i = 0; i < length; ++i)
-        if (ligatures[2*i] == u1)
-            return ligatures[2*i+1];
+    ushort length = *ligatures++;
+    {
+        const UCS2Pair *data = reinterpret_cast<const UCS2Pair *>(ligatures);
+        const UCS2Pair *r = qBinaryFind(data, data + length, u1);
+        if (r != data + length)
+            return r->u2;
+    }
+
     return 0;
 }
 
-- 
cgit v0.12