optimize QString::toLower()/toUpper() for special cases, step 1

reorganize QUnicodeTables::specialCaseMap as follows:
specialCaseMap contains sequence entries in form { length, a, b, .. }

Change-Id: Iea1f80bc2f4dc1f505428dad981cde26daaa52c7
Merge-request: 70
Reviewed-by: Oswald Buddenhagen <oswald.buddenhagen@nokia.com>
Reviewed-by: Olivier
Reviewed-by: Olivier Goffart <ogoffart@woboq.com>

2 files changed, 39 insertions, 26 deletions

diff --git a/src/corelib/tools/qstring.cpp b/src/corelib/tools/qstring.cpp
index 5bb8d5a5a1..b0c259272e 100644
--- a/src/corelib/tools/qstring.cpp
+++ b/src/corelib/tools/qstring.cpp
@@ -4920,11 +4920,12 @@ QString QString::toLower() const
                     prop = qGetProp(*p);
                 }
                 if (prop->lowerCaseSpecial) {
+                    const ushort *specialCase = specialCaseMap + prop->lowerCaseDiff;
+                    ushort length = *specialCase++;
                     int pos = pp - s.d->data();
-                    s.resize(s.d->size + SPECIAL_CASE_MAX_LEN);
+                    s.resize(s.d->size + length - 1);
                     pp = s.d->data() + pos;
-                    const ushort *specialCase = specialCaseMap + prop->lowerCaseDiff;
-                    while (*specialCase)
+                    while (length--)
                         *pp++ = *specialCase++;
                 } else {
                     *pp++ = *p + prop->lowerCaseDiff;
@@ -4936,7 +4937,6 @@ QString QString::toLower() const
             while (e != d->data() + d->size)
                 *pp++ = *e++;
 
-            s.truncate(pp - s.d->data());
             return s;
         }
         ++p;
@@ -5042,11 +5042,12 @@ QString QString::toUpper() const
                     prop = qGetProp(*p);
                 }
                 if (prop->upperCaseSpecial) {
+                    const ushort *specialCase = specialCaseMap + prop->upperCaseDiff;
+                    ushort length = *specialCase++;
                     int pos = pp - s.d->data();
-                    s.resize(s.d->size + SPECIAL_CASE_MAX_LEN);
+                    s.resize(s.d->size + length - 1);
                     pp = s.d->data() + pos;
-                    const ushort *specialCase = specialCaseMap + prop->upperCaseDiff;
-                    while (*specialCase)
+                    while (length--)
                         *pp++ = *specialCase++;
                 } else {
                     *pp++ = *p + prop->upperCaseDiff;
@@ -5058,7 +5059,6 @@ QString QString::toUpper() const
             while (e != d->data() + d->size)
                 *pp++ = *e++;
 
-            s.truncate(pp - s.d->data());
             return s;
         }
         ++p;
diff --git a/util/unicode/main.cpp b/util/unicode/main.cpp
index 8ba992f72b..40294eba4d 100644
--- a/util/unicode/main.cpp
+++ b/util/unicode/main.cpp
@@ -472,17 +472,23 @@ static int appendToSpecialCaseMap(const QList<int> &map)
             utf16map << val;
         }
     }
-    specialCaseMaxLen = qMax(specialCaseMaxLen, utf16map.size());
-    utf16map << 0;
-
-    for (int i = 0; i < specialCaseMap.size() - utf16map.size() + 1; ++i) {
-        int j;
-        for (j = 0; j < utf16map.size(); ++j) {
-            if (specialCaseMap.at(i+j) != utf16map.at(j))
-                break;
+    int length = utf16map.size();
+    utf16map.prepend(length);
+    specialCaseMaxLen = qMax(specialCaseMaxLen, length);
+
+    int i = 0;
+    while (i < specialCaseMap.size()) {
+        int n = specialCaseMap.at(i);
+        if (n == length) {
+            int j;
+            for (j = 1; j <= n; ++j) {
+                if (specialCaseMap.at(i+j) != utf16map.at(j))
+                    break;
+            }
+            if (j > n)
+                return i;
         }
-        if (j == utf16map.size())
-            return i;
+        i += n + 1;
     }
 
     int pos = specialCaseMap.size();
@@ -1528,7 +1534,8 @@ static inline void foldCase(uint ch, ushort *out)
         *(out++) = ch + p->caseFoldDiff;
     } else {
         const ushort *folded = specialCaseMap + p->caseFoldDiff;
-        while (*folded)
+        ushort length = *folded++;
+        while (length--)
             *out++ = *folded++;
     }
     *out = 0;
@@ -2243,13 +2250,19 @@ static QByteArray createPropertyInfo()
            "    return (QUnicodeTables::LineBreakClass)qGetProp(ucs4)->line_break_class;\n"
            "}\n\n";
 
-    out += "static const ushort specialCaseMap[] = {\n   ";
-    for (int i = 0; i < specialCaseMap.size(); ++i) {
-        out += QByteArray(" 0x") + QByteArray::number(specialCaseMap.at(i), 16);
-        if (i < specialCaseMap.size() - 1)
-            out += ",";
-        if (!specialCaseMap.at(i))
-            out += "\n   ";
+
+    out += "static const ushort specialCaseMap[] = {";
+    int i = 0;
+    while (i < specialCaseMap.size()) {
+        out += "\n   ";
+        int n = specialCaseMap.at(i);
+        int j;
+        for (j = 0; j <= n; ++j) {
+            out += QByteArray(" 0x") + QByteArray::number(specialCaseMap.at(i+j), 16);
+            if (i+j < specialCaseMap.size() - 1)
+                out += ",";
+        }
+        i += n + 1;
     }
     out += "\n};\n";
     out += "#define SPECIAL_CASE_MAX_LEN " + QByteArray::number(specialCaseMaxLen) + "\n\n";