summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorMarc Mutz <marc.mutz@kdab.com>2015-06-19 02:06:30 +0200
committerMarc Mutz <marc.mutz@kdab.com>2015-06-19 18:37:30 +0000
commit452ece9c029f9c519e9cf184918862006538b9d6 (patch)
tree63c5f4e41a4df0713123f23e5e40360145054e03
parenta6000e2b6679d91c9dab44e49b485de6816372bc (diff)
Remove quadratic behavior in QFontDatabase::writingSystems()
Looping over QList::contains() constitutes O(N²) behavior, the more so as this QList is horribly inefficient since WritingSystem is not a Q_MOVABLE_TYPE. Since the range of possible unique values in the result is severly limited (by virtue of being enumerated values), use a bitmask to remember which WritingSystems were encountered, then, after releaseing the mutex again, use that bitmask to populate the QList. Change-Id: I1d12eb487513ec17faa6f38942f8b681819dc0e8 Reviewed-by: Adam Majer <adamm@zombino.com> Reviewed-by: Konstantin Ritt <ritt.ks@gmail.com> Reviewed-by: Lars Knoll <lars.knoll@theqtcompany.com>
-rw-r--r--src/gui/text/qfontdatabase.cpp24
1 files changed, 16 insertions, 8 deletions
diff --git a/src/gui/text/qfontdatabase.cpp b/src/gui/text/qfontdatabase.cpp
index dae4d560a8..0a3ce5c5d1 100644
--- a/src/gui/text/qfontdatabase.cpp
+++ b/src/gui/text/qfontdatabase.cpp
@@ -1358,22 +1358,30 @@ QList<QFontDatabase::WritingSystem> QFontDatabase::writingSystems() const
QT_PREPEND_NAMESPACE(load)();
- QList<WritingSystem> list;
+ quint64 writingSystemsFound = 0;
+ Q_STATIC_ASSERT(WritingSystemsCount < 64);
+
for (int i = 0; i < d->count; ++i) {
QtFontFamily *family = d->families[i];
family->ensurePopulated();
if (family->count == 0)
continue;
- for (int x = Latin; x < WritingSystemsCount; ++x) {
- const WritingSystem writingSystem = WritingSystem(x);
- if (!(family->writingSystems[writingSystem] & QtFontFamily::Supported))
- continue;
- if (!list.contains(writingSystem))
- list.append(writingSystem);
+ for (uint x = Latin; x < uint(WritingSystemsCount); ++x) {
+ if (family->writingSystems[x] & QtFontFamily::Supported)
+ writingSystemsFound |= quint64(1) << x;
}
}
- std::sort(list.begin(), list.end());
+
+ // mutex protection no longer needed - just working on local data now:
+ locker.unlock();
+
+ QList<WritingSystem> list;
+ list.reserve(qPopulationCount(writingSystemsFound));
+ for (uint x = Latin ; x < uint(WritingSystemsCount); ++x) {
+ if (writingSystemsFound & (quint64(1) << x))
+ list.push_back(WritingSystem(x));
+ }
return list;
}