diff options
author | Marc Mutz <marc.mutz@kdab.com> | 2015-06-19 02:06:30 +0200 |
---|---|---|
committer | Marc Mutz <marc.mutz@kdab.com> | 2015-06-19 18:37:30 +0000 |
commit | 452ece9c029f9c519e9cf184918862006538b9d6 (patch) | |
tree | 63c5f4e41a4df0713123f23e5e40360145054e03 | |
parent | a6000e2b6679d91c9dab44e49b485de6816372bc (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.cpp | 24 |
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; } |