From 81a45e1f13fdf56129aed952a6e3479e16c14a2c Mon Sep 17 00:00:00 2001 From: Marc Mutz Date: Sat, 26 Jul 2014 01:43:18 +0200 Subject: QTimeZone: don't use QSet, use sorted QList QSet, as a node-based container, requires one memory allocation per element inserted. QList, as a contiguous-memory container (at least in the case of a QByteArray payload), requires one memory allocation per container. The higher lookup speed might still speak for using QSet, but there are only two uses of the sets: 1. Checking for existence (or lack thereof) of timezone names. For this, first generating a container full of data just to check for existence of one item of data is extremely wasteful. The QTZPrivate API should be extended to allow said lookup to be performed on the native data store instead. That leaves 2. Returning a sorted(!) list(!) from the public QTimeZone API. There is no reason why, during the construction of those sorted lists, the data should be held in a set. Instead, the well-known technique of first cramming everything into a result container, which is subsequently sorted and has its duplicates removed, can be used here. Saves more than 8K of text size on AMD64 stripped release builds. Change-Id: I71c2298e94e02d55b0c9fb6f7ebeaed79a1fe2db Reviewed-by: Thiago Macieira --- src/corelib/tools/qtimezone.cpp | 42 +++++++++-------- src/corelib/tools/qtimezoneprivate.cpp | 74 +++++++++++++++++------------- src/corelib/tools/qtimezoneprivate_icu.cpp | 37 ++++++++------- src/corelib/tools/qtimezoneprivate_mac.mm | 13 ++++-- src/corelib/tools/qtimezoneprivate_p.h | 26 +++++------ src/corelib/tools/qtimezoneprivate_tz.cpp | 16 ++++--- src/corelib/tools/qtimezoneprivate_win.cpp | 12 +++-- 7 files changed, 125 insertions(+), 95 deletions(-) diff --git a/src/corelib/tools/qtimezone.cpp b/src/corelib/tools/qtimezone.cpp index b6160a3fd8..c2ee99a2d8 100644 --- a/src/corelib/tools/qtimezone.cpp +++ b/src/corelib/tools/qtimezone.cpp @@ -378,12 +378,10 @@ QTimeZone::QTimeZone(int offsetSeconds) QTimeZone::QTimeZone(const QByteArray &ianaId, int offsetSeconds, const QString &name, const QString &abbreviation, QLocale::Country country, const QString &comment) + : d() { - // ianaId must be a valid ID and must not clash with the standard system names - if (QTimeZonePrivate::isValidId(ianaId) && !availableTimeZoneIds().contains(ianaId)) + if (!isTimeZoneIdAvailable(ianaId)) d = new QUtcTimeZonePrivate(ianaId, offsetSeconds, name, abbreviation, country, comment); - else - d = 0; } /*! @@ -821,7 +819,20 @@ bool QTimeZone::isTimeZoneIdAvailable(const QByteArray &ianaId) { // isValidId is not strictly required, but faster to weed out invalid // IDs as availableTimeZoneIds() may be slow - return (QTimeZonePrivate::isValidId(ianaId) && (availableTimeZoneIds().contains(ianaId))); + if (!QTimeZonePrivate::isValidId(ianaId)) + return false; + const QList tzIds = availableTimeZoneIds(); + return std::binary_search(tzIds.begin(), tzIds.end(), ianaId); +} + +static QList set_union(const QList &l1, const QList &l2) +{ + QList result; + result.reserve(l1.size() + l2.size()); + std::set_union(l1.begin(), l1.end(), + l2.begin(), l2.end(), + std::back_inserter(result)); + return result; } /*! @@ -832,11 +843,8 @@ bool QTimeZone::isTimeZoneIdAvailable(const QByteArray &ianaId) QList QTimeZone::availableTimeZoneIds() { - QSet set = QUtcTimeZonePrivate().availableTimeZoneIds() - + global_tz->backend->availableTimeZoneIds(); - QList list = set.toList(); - std::sort(list.begin(), list.end()); - return list; + return set_union(QUtcTimeZonePrivate().availableTimeZoneIds(), + global_tz->backend->availableTimeZoneIds()); } /*! @@ -852,11 +860,8 @@ QList QTimeZone::availableTimeZoneIds() QList QTimeZone::availableTimeZoneIds(QLocale::Country country) { - QSet set = QUtcTimeZonePrivate().availableTimeZoneIds(country) - + global_tz->backend->availableTimeZoneIds(country); - QList list = set.toList(); - std::sort(list.begin(), list.end()); - return list; + return set_union(QUtcTimeZonePrivate().availableTimeZoneIds(country), + global_tz->backend->availableTimeZoneIds(country)); } /*! @@ -868,11 +873,8 @@ QList QTimeZone::availableTimeZoneIds(QLocale::Country country) QList QTimeZone::availableTimeZoneIds(int offsetSeconds) { - QSet set = QUtcTimeZonePrivate().availableTimeZoneIds(offsetSeconds) - + global_tz->backend->availableTimeZoneIds(offsetSeconds); - QList list = set.toList(); - std::sort(list.begin(), list.end()); - return list; + return set_union(QUtcTimeZonePrivate().availableTimeZoneIds(offsetSeconds), + global_tz->backend->availableTimeZoneIds(offsetSeconds)); } /*! diff --git a/src/corelib/tools/qtimezoneprivate.cpp b/src/corelib/tools/qtimezoneprivate.cpp index 337f0e6bfb..164db5ed0c 100644 --- a/src/corelib/tools/qtimezoneprivate.cpp +++ b/src/corelib/tools/qtimezoneprivate.cpp @@ -39,6 +39,8 @@ #include #include +#include + QT_BEGIN_NAMESPACE enum { @@ -341,36 +343,38 @@ QByteArray QTimeZonePrivate::systemTimeZoneId() const return QByteArray(); } -QSet QTimeZonePrivate::availableTimeZoneIds() const +QList QTimeZonePrivate::availableTimeZoneIds() const { - return QSet(); + return QList(); } -QSet QTimeZonePrivate::availableTimeZoneIds(QLocale::Country country) const +QList QTimeZonePrivate::availableTimeZoneIds(QLocale::Country country) const { // Default fall-back mode, use the zoneTable to find Region of know Zones - QSet regionSet; + QList regions; // First get all Zones in the Zones table belonging to the Region for (int i = 0; i < zoneDataTableSize; ++i) { if (zoneData(i)->country == country) - regionSet += ianaId(zoneData(i)).split(' ').toSet(); + regions += ianaId(zoneData(i)).split(' '); } - // Then select just those that are available - QSet set; - foreach (const QByteArray &ianaId, availableTimeZoneIds()) { - if (regionSet.contains(ianaId)) - set << ianaId; - } + std::sort(regions.begin(), regions.end()); + regions.erase(std::unique(regions.begin(), regions.end()), regions.end()); - return set; + // Then select just those that are available + const QList all = availableTimeZoneIds(); + QList result; + result.reserve(qMin(all.size(), regions.size())); + std::set_intersection(all.begin(), all.end(), regions.cbegin(), regions.cend(), + std::back_inserter(result)); + return result; } -QSet QTimeZonePrivate::availableTimeZoneIds(int offsetFromUtc) const +QList QTimeZonePrivate::availableTimeZoneIds(int offsetFromUtc) const { // Default fall-back mode, use the zoneTable to find Offset of know Zones - QSet offsetSet; + QList offsets; // First get all Zones in the table using the Offset for (int i = 0; i < windowsDataTableSize; ++i) { const QWindowsData *winData = windowsData(i); @@ -378,19 +382,21 @@ QSet QTimeZonePrivate::availableTimeZoneIds(int offsetFromUtc) const for (int j = 0; j < zoneDataTableSize; ++j) { const QZoneData *data = zoneData(j); if (data->windowsIdKey == winData->windowsIdKey) - offsetSet += ianaId(data).split(' ').toSet(); + offsets += ianaId(data).split(' '); } } } - // Then select just those that are available - QSet set; - foreach (const QByteArray &ianaId, availableTimeZoneIds()) { - if (offsetSet.contains(ianaId)) - set << ianaId; - } + std::sort(offsets.begin(), offsets.end()); + offsets.erase(std::unique(offsets.begin(), offsets.end()), offsets.end()); - return set; + // Then select just those that are available + const QList all = availableTimeZoneIds(); + QList result; + result.reserve(qMin(all.size(), offsets.size())); + std::set_intersection(all.begin(), all.end(), offsets.cbegin(), offsets.cend(), + std::back_inserter(result)); + return result; } #ifndef QT_NO_DATASTREAM @@ -682,31 +688,35 @@ QByteArray QUtcTimeZonePrivate::systemTimeZoneId() const return utcQByteArray(); } -QSet QUtcTimeZonePrivate::availableTimeZoneIds() const +QList QUtcTimeZonePrivate::availableTimeZoneIds() const { - QSet set; + QList result; for (int i = 0; i < utcDataTableSize; ++i) - set << utcId(utcData(i)); - return set; + result << utcId(utcData(i)); + std::sort(result.begin(), result.end()); // ### or already sorted?? + // ### assuming no duplicates + return result; } -QSet QUtcTimeZonePrivate::availableTimeZoneIds(QLocale::Country country) const +QList QUtcTimeZonePrivate::availableTimeZoneIds(QLocale::Country country) const { // If AnyCountry then is request for all non-region offset codes if (country == QLocale::AnyCountry) return availableTimeZoneIds(); - return QSet(); + return QList(); } -QSet QUtcTimeZonePrivate::availableTimeZoneIds(qint32 offsetSeconds) const +QList QUtcTimeZonePrivate::availableTimeZoneIds(qint32 offsetSeconds) const { - QSet set; + QList result; for (int i = 0; i < utcDataTableSize; ++i) { const QUtcData *data = utcData(i); if (data->offsetFromUtc == offsetSeconds) - set << utcId(data); + result << utcId(data); } - return set; + std::sort(result.begin(), result.end()); // ### or already sorted?? + // ### assuming no duplicates + return result; } #ifndef QT_NO_DATASTREAM diff --git a/src/corelib/tools/qtimezoneprivate_icu.cpp b/src/corelib/tools/qtimezoneprivate_icu.cpp index 3ab42661c0..dd57464a72 100644 --- a/src/corelib/tools/qtimezoneprivate_icu.cpp +++ b/src/corelib/tools/qtimezoneprivate_icu.cpp @@ -37,6 +37,9 @@ #include #include +#include + +#include QT_BEGIN_NAMESPACE @@ -234,19 +237,21 @@ static QTimeZonePrivate::Data ucalTimeZoneTransition(UCalendar *m_ucal, #endif // U_ICU_VERSION_SHORT // Convert a uenum to a QList -static QSet uenumToIdSet(UEnumeration *uenum) +static QList uenumToIdList(UEnumeration *uenum) { - QSet set; + QList list; int32_t size = 0; UErrorCode status = U_ZERO_ERROR; // TODO Perhaps use uenum_unext instead? QByteArray result = uenum_next(uenum, &size, &status); while (U_SUCCESS(status) && !result.isEmpty()) { - set << result; + list << result; status = U_ZERO_ERROR; result = uenum_next(uenum, &size, &status); } - return set; + std::sort(list.begin(), list.end()); + list.erase(std::unique(list.begin(), list.end()), list.end()); + return list; } // Qt wrapper around ucal_getDSTSavings() @@ -453,41 +458,41 @@ QByteArray QIcuTimeZonePrivate::systemTimeZoneId() const return ucalDefaultTimeZoneId(); } -QSet QIcuTimeZonePrivate::availableTimeZoneIds() const +QList QIcuTimeZonePrivate::availableTimeZoneIds() const { UErrorCode status = U_ZERO_ERROR; UEnumeration *uenum = ucal_openTimeZones(&status); - QSet set; + QList result; if (U_SUCCESS(status)) - set = uenumToIdSet(uenum); + result = uenumToIdList(uenum); uenum_close(uenum); - return set; + return result; } -QSet QIcuTimeZonePrivate::availableTimeZoneIds(QLocale::Country country) const +QList QIcuTimeZonePrivate::availableTimeZoneIds(QLocale::Country country) const { QByteArray regionCode = QLocalePrivate::countryToCode(country).toUtf8(); UErrorCode status = U_ZERO_ERROR; UEnumeration *uenum = ucal_openCountryTimeZones(regionCode, &status); - QSet set; + QList result; if (U_SUCCESS(status)) - set = uenumToIdSet(uenum); + result = uenumToIdList(uenum); uenum_close(uenum); - return set; + return result; } -QSet QIcuTimeZonePrivate::availableTimeZoneIds(int offsetFromUtc) const +QList QIcuTimeZonePrivate::availableTimeZoneIds(int offsetFromUtc) const { // TODO Available directly in C++ api but not C api, from 4.8 onwards new filter method works #if U_ICU_VERSION_MAJOR_NUM >= 49 || (U_ICU_VERSION_MAJOR_NUM == 4 && U_ICU_VERSION_MINOR_NUM == 8) UErrorCode status = U_ZERO_ERROR; UEnumeration *uenum = ucal_openTimeZoneIDEnumeration(UCAL_ZONE_TYPE_ANY, 0, &offsetFromUtc, &status); - QSet set; + QList result; if (U_SUCCESS(status)) - set = uenumToIdSet(uenum); + result = uenumToIdList(uenum); uenum_close(uenum); - return set; + return result; #else return QTimeZonePrivate::availableTimeZoneIds(offsetFromUtc); #endif diff --git a/src/corelib/tools/qtimezoneprivate_mac.mm b/src/corelib/tools/qtimezoneprivate_mac.mm index b0c3c9e64f..f316fe0a6d 100644 --- a/src/corelib/tools/qtimezoneprivate_mac.mm +++ b/src/corelib/tools/qtimezoneprivate_mac.mm @@ -41,6 +41,8 @@ #include +#include + QT_BEGIN_NAMESPACE /* @@ -247,18 +249,21 @@ QByteArray QMacTimeZonePrivate::systemTimeZoneId() const return QCFString::toQString([[NSTimeZone systemTimeZone] name]).toUtf8(); } -QSet QMacTimeZonePrivate::availableTimeZoneIds() const +QList QMacTimeZonePrivate::availableTimeZoneIds() const { NSEnumerator *enumerator = [[NSTimeZone knownTimeZoneNames] objectEnumerator]; QByteArray tzid = QCFString::toQString([enumerator nextObject]).toUtf8(); - QSet set; + QList list; while (!tzid.isEmpty()) { - set << tzid; + list << tzid; tzid = QCFString::toQString([enumerator nextObject]).toUtf8(); } - return set; + std::sort(list.begin(), list.end()); + list.erase(std::unique(list.begin(), list.end()), list.end()); + + return list; } QT_END_NAMESPACE diff --git a/src/corelib/tools/qtimezoneprivate_p.h b/src/corelib/tools/qtimezoneprivate_p.h index 609ed50c56..64827950e2 100644 --- a/src/corelib/tools/qtimezoneprivate_p.h +++ b/src/corelib/tools/qtimezoneprivate_p.h @@ -126,9 +126,9 @@ public: virtual QByteArray systemTimeZoneId() const; - virtual QSet availableTimeZoneIds() const; - virtual QSet availableTimeZoneIds(QLocale::Country country) const; - virtual QSet availableTimeZoneIds(int utcOffset) const; + virtual QList availableTimeZoneIds() const; + virtual QList availableTimeZoneIds(QLocale::Country country) const; + virtual QList availableTimeZoneIds(int utcOffset) const; virtual void serialize(QDataStream &ds) const; @@ -199,9 +199,9 @@ public: QByteArray systemTimeZoneId() const Q_DECL_OVERRIDE; - QSet availableTimeZoneIds() const Q_DECL_OVERRIDE; - QSet availableTimeZoneIds(QLocale::Country country) const Q_DECL_OVERRIDE; - QSet availableTimeZoneIds(int utcOffset) const Q_DECL_OVERRIDE; + QList availableTimeZoneIds() const Q_DECL_OVERRIDE; + QList availableTimeZoneIds(QLocale::Country country) const Q_DECL_OVERRIDE; + QList availableTimeZoneIds(int utcOffset) const Q_DECL_OVERRIDE; void serialize(QDataStream &ds) const Q_DECL_OVERRIDE; @@ -250,9 +250,9 @@ public: QByteArray systemTimeZoneId() const Q_DECL_OVERRIDE; - QSet availableTimeZoneIds() const Q_DECL_OVERRIDE; - QSet availableTimeZoneIds(QLocale::Country country) const Q_DECL_OVERRIDE; - QSet availableTimeZoneIds(int offsetFromUtc) const Q_DECL_OVERRIDE; + QList availableTimeZoneIds() const Q_DECL_OVERRIDE; + QList availableTimeZoneIds(QLocale::Country country) const Q_DECL_OVERRIDE; + QList availableTimeZoneIds(int offsetFromUtc) const Q_DECL_OVERRIDE; private: void init(const QByteArray &ianaId); @@ -318,8 +318,8 @@ public: QByteArray systemTimeZoneId() const Q_DECL_OVERRIDE; - QSet availableTimeZoneIds() const Q_DECL_OVERRIDE; - QSet availableTimeZoneIds(QLocale::Country country) const Q_DECL_OVERRIDE; + QList availableTimeZoneIds() const Q_DECL_OVERRIDE; + QList availableTimeZoneIds(QLocale::Country country) const Q_DECL_OVERRIDE; private: void init(const QByteArray &ianaId); @@ -369,7 +369,7 @@ public: QByteArray systemTimeZoneId() const Q_DECL_OVERRIDE; - QSet availableTimeZoneIds() const Q_DECL_OVERRIDE; + QList availableTimeZoneIds() const Q_DECL_OVERRIDE; private: void init(const QByteArray &zoneId); @@ -420,7 +420,7 @@ public: QByteArray systemTimeZoneId() const Q_DECL_OVERRIDE; - QSet availableTimeZoneIds() const Q_DECL_OVERRIDE; + QList availableTimeZoneIds() const Q_DECL_OVERRIDE; private: void init(const QByteArray &ianaId); diff --git a/src/corelib/tools/qtimezoneprivate_tz.cpp b/src/corelib/tools/qtimezoneprivate_tz.cpp index 0d8ae3b47f..29f0e17012 100644 --- a/src/corelib/tools/qtimezoneprivate_tz.cpp +++ b/src/corelib/tools/qtimezoneprivate_tz.cpp @@ -41,6 +41,7 @@ #include +#include QT_BEGIN_NAMESPACE @@ -956,20 +957,23 @@ QByteArray QTzTimeZonePrivate::systemTimeZoneId() const return ianaId; } -QSet QTzTimeZonePrivate::availableTimeZoneIds() const +QList QTzTimeZonePrivate::availableTimeZoneIds() const { - return tzZones->keys().toSet(); + QList result = tzZones->keys(); + std::sort(result.begin(), result.end()); + return result; } -QSet QTzTimeZonePrivate::availableTimeZoneIds(QLocale::Country country) const +QList QTzTimeZonePrivate::availableTimeZoneIds(QLocale::Country country) const { // TODO AnyCountry - QSet set; + QList result; foreach (const QByteArray &key, tzZones->keys()) { if (tzZones->value(key).country == country) - set << key; + result << key; } - return set; + std::sort(result.begin(), result.end()); + return result; } QT_END_NAMESPACE diff --git a/src/corelib/tools/qtimezoneprivate_win.cpp b/src/corelib/tools/qtimezoneprivate_win.cpp index 2d0caf07a8..a9bb3aa3b5 100644 --- a/src/corelib/tools/qtimezoneprivate_win.cpp +++ b/src/corelib/tools/qtimezoneprivate_win.cpp @@ -38,6 +38,8 @@ #include "qdebug.h" +#include + QT_BEGIN_NAMESPACE /* @@ -632,14 +634,16 @@ QByteArray QWinTimeZonePrivate::systemTimeZoneId() const return ianaId; } -QSet QWinTimeZonePrivate::availableTimeZoneIds() const +QList QWinTimeZonePrivate::availableTimeZoneIds() const { - QSet set; + QList result; foreach (const QByteArray &winId, availableWindowsIds()) { foreach (const QByteArray &ianaId, windowsIdToIanaIds(winId)) - set << ianaId; + result << ianaId; } - return set; + std::sort(result.begin(), result.end()); + result.erase(std::unique(result.begin(), result.end()), result.end()); + return result; } QWinTimeZonePrivate::QWinTransitionRule QWinTimeZonePrivate::ruleForYear(int year) const -- cgit v1.2.3