From a9e4bf7eef4b4e3a2c765cd0a6df48ed61d49111 Mon Sep 17 00:00:00 2001 From: Edward Welbourne Date: Mon, 12 Oct 2020 13:12:48 +0200 Subject: Implement binary search in QLocale's likely sub-tag lookup MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Follow through on a comment from 2012: sort the likely subtag array (in the CLDR update script) and use bsearch to find entries in it. This simplifies QLocaleXmlReader.likelyMap() slightly, moving the detection of last entry to LocaleDataWriter.likelySubtags(), but requires collecting all likely sub-tag mapping pairs (rather than just passing them through from read to write via generators) in order to sort them. Change-Id: Ieb6875ccde1ddbd475ae68c0766a666ec32b7005 Reviewed-by: Mårten Nordheim --- src/corelib/text/qlocale.cpp | 42 ++++++++++++++++++++++++++++++++---------- 1 file changed, 32 insertions(+), 10 deletions(-) (limited to 'src/corelib/text/qlocale.cpp') diff --git a/src/corelib/text/qlocale.cpp b/src/corelib/text/qlocale.cpp index 89928a5e87..ebdd4d1b15 100644 --- a/src/corelib/text/qlocale.cpp +++ b/src/corelib/text/qlocale.cpp @@ -201,19 +201,41 @@ QLatin1String QLocalePrivate::countryToCode(QLocale::Country country) return QLatin1String(reinterpret_cast(c), c[2] == 0 ? 2 : 3); } +static int cmpLikelySubtag(const void *lhs, const void *rhs) +{ + // Must match the comparison LocaleDataWriter.likelySubtags() uses when + // sorting, see qtbase/util/locale_database.qlocalexml2cpp.py + const auto compare = [](int lhs, int rhs) { + // 0 sorts after all other values; lhs and rhs are passed ushort values. + const int huge = 0x10000; + return (lhs ? lhs : huge) - (rhs ? rhs : huge); + }; + const auto &left = *reinterpret_cast(lhs); + const auto &right = *reinterpret_cast(rhs); + if (int cmp = compare(left.language_id, right.language_id)) + return cmp; + if (int cmp = compare(left.country_id, right.country_id)) + return cmp; + return compare(left.script_id, right.script_id); +} + // http://www.unicode.org/reports/tr35/#Likely_Subtags static bool addLikelySubtags(QLocaleId &localeId) { - // ### optimize with bsearch - const QLocaleId *p = likely_subtags; - const QLocaleId *const e = p + std::size(likely_subtags); - for ( ; p < e; p += 2) { - if (localeId == p[0]) { - localeId = p[1]; - return true; - } - } - return false; + // Array is overtly of QLocaleId but to be interpreted as of pairs, mapping + // each even entry to the following odd entry. So search only the even + // entries for a match and return the matching odd entry, if found. + static_assert(std::size(likely_subtags) % 2 == 0); + const auto *p = reinterpret_cast( + bsearch(&localeId, + likely_subtags, std::size(likely_subtags) / 2, 2 * sizeof(QLocaleId), + cmpLikelySubtag)); + if (!p) + return false; + Q_ASSERT(p >= likely_subtags && p < likely_subtags + std::size(likely_subtags)); + Q_ASSERT((p - likely_subtags) % 2 == 0); + localeId = p[1]; + return true; } QLocaleId QLocaleId::withLikelySubtagsAdded() const -- cgit v1.2.3