summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/corelib/text/qstringlist.cpp10
-rw-r--r--src/corelib/tools/qduplicatetracker_p.h94
-rw-r--r--src/corelib/tools/tools.pri1
-rw-r--r--src/platformsupport/fontdatabases/fontconfig/qfontconfigdatabase.cpp9
-rw-r--r--src/widgets/itemviews/qtreewidget.cpp7
-rw-r--r--src/xml/dom/qdom.cpp8
-rw-r--r--tests/benchmarks/corelib/text/qstringlist/main.cpp39
-rw-r--r--tests/benchmarks/corelib/text/qstringlist/qstringlist.pro1
8 files changed, 153 insertions, 16 deletions
diff --git a/src/corelib/text/qstringlist.cpp b/src/corelib/text/qstringlist.cpp
index 4bbe424ed2..4b9dcee169 100644
--- a/src/corelib/text/qstringlist.cpp
+++ b/src/corelib/text/qstringlist.cpp
@@ -43,9 +43,9 @@
#if QT_CONFIG(regularexpression)
# include <qregularexpression.h>
#endif
+#include <private/qduplicatetracker_p.h>
#include <algorithm>
-
QT_BEGIN_NAMESPACE
/*! \typedef QStringListIterator
@@ -885,15 +885,13 @@ int QtPrivate::QStringList_removeDuplicates(QStringList *that)
{
int n = that->size();
int j = 0;
- QSet<QString> seen;
+
+ QDuplicateTracker<QString> seen;
seen.reserve(n);
- int setSize = 0;
for (int i = 0; i < n; ++i) {
const QString &s = that->at(i);
- seen.insert(s);
- if (setSize == seen.size()) // unchanged size => was already seen
+ if (seen.hasSeen(s))
continue;
- ++setSize;
if (j != i)
that->swapItemsAt(i, j);
++j;
diff --git a/src/corelib/tools/qduplicatetracker_p.h b/src/corelib/tools/qduplicatetracker_p.h
new file mode 100644
index 0000000000..99068c01a3
--- /dev/null
+++ b/src/corelib/tools/qduplicatetracker_p.h
@@ -0,0 +1,94 @@
+/****************************************************************************
+**
+** Copyright (C) 2020 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Marc Mutz <marc.mutz@kdab.com>
+** Contact: http://www.qt.io/licensing/
+**
+** This file is part of the QtCore module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** Commercial License Usage
+** Licensees holding valid commercial Qt licenses may use this file in
+** accordance with the commercial license agreement provided with the
+** Software or, alternatively, in accordance with the terms contained in
+** a written agreement between you and The Qt Company. For licensing terms
+** and conditions see https://www.qt.io/terms-conditions. For further
+** information use the contact form at https://www.qt.io/contact-us.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 3 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL3 included in the
+** packaging of this file. Please review the following information to
+** ensure the GNU Lesser General Public License version 3 requirements
+** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
+**
+** GNU General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU
+** General Public License version 2.0 or (at your option) the GNU General
+** Public license version 3 or any later version approved by the KDE Free
+** Qt Foundation. The licenses are as published by the Free Software
+** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
+** included in the packaging of this file. Please review the following
+** information to ensure the GNU General Public License requirements will
+** be met: https://www.gnu.org/licenses/gpl-2.0.html and
+** https://www.gnu.org/licenses/gpl-3.0.html.
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+#ifndef QDUPLICATETRACKER_P_H
+#define QDUPLICATETRACKER_P_H
+
+//
+// W A R N I N G
+// -------------
+//
+// This file is not part of the Qt API. It exists purely as an
+// implementation detail. This header file may change from version to
+// version without notice, or even be removed.
+//
+// We mean it.
+//
+
+#include <qglobal.h>
+
+#if QT_HAS_INCLUDE(<memory_resource>) && __cplusplus > 201402L
+# include <unordered_set>
+# include <memory_resource>
+#else
+# include <qset.h>
+#endif
+
+QT_BEGIN_NAMESPACE
+
+template <typename T, size_t Prealloc = 32>
+class QDuplicateTracker {
+#ifdef __cpp_lib_memory_resource
+ char buffer[Prealloc * sizeof(T)];
+ std::pmr::monotonic_buffer_resource res{buffer, sizeof buffer};
+ std::pmr::unordered_set<T> set{&res};
+#else
+ QSet<T> set;
+ int setSize = 0;
+#endif
+ Q_DISABLE_COPY_MOVE(QDuplicateTracker);
+public:
+ QDuplicateTracker() = default;
+ void reserve(int n) { set.reserve(n); }
+ Q_REQUIRED_RESULT bool hasSeen(const T &s)
+ {
+ bool inserted;
+#ifdef __cpp_lib_memory_resource
+ inserted = set.insert(s).second;
+#else
+ set.insert(s);
+ const int n = set.size();
+ inserted = qExchange(setSize, n) != n;
+#endif
+ return !inserted;
+ }
+};
+
+QT_END_NAMESPACE
+
+#endif /* QDUPLICATETRACKER_P_H */
diff --git a/src/corelib/tools/tools.pri b/src/corelib/tools/tools.pri
index 40c84157cd..e078ab4409 100644
--- a/src/corelib/tools/tools.pri
+++ b/src/corelib/tools/tools.pri
@@ -12,6 +12,7 @@ HEADERS += \
tools/qcontainerfwd.h \
tools/qcontainertools_impl.h \
tools/qcryptographichash.h \
+ tools/qduplicatetracker_p.h \
tools/qfreelist_p.h \
tools/qhash.h \
tools/qhashfunctions.h \
diff --git a/src/platformsupport/fontdatabases/fontconfig/qfontconfigdatabase.cpp b/src/platformsupport/fontdatabases/fontconfig/qfontconfigdatabase.cpp
index 7af5490963..af49ad6407 100644
--- a/src/platformsupport/fontdatabases/fontconfig/qfontconfigdatabase.cpp
+++ b/src/platformsupport/fontdatabases/fontconfig/qfontconfigdatabase.cpp
@@ -56,6 +56,8 @@
#include <QtGui/qguiapplication.h>
+#include <QtCore/private/qduplicatetracker_p.h>
+
#include <fontconfig/fontconfig.h>
#if FC_VERSION >= 20402
#include <fontconfig/fcfreetype.h>
@@ -778,9 +780,9 @@ QStringList QFontconfigDatabase::fallbacksForFamily(const QString &family, QFont
FcPatternDestroy(pattern);
if (fontSet) {
- QSet<QString> duplicates;
+ QDuplicateTracker<QString> duplicates;
duplicates.reserve(fontSet->nfont + 1);
- duplicates.insert(family.toCaseFolded());
+ (void)duplicates.hasSeen(family.toCaseFolded());
for (int i = 0; i < fontSet->nfont; i++) {
FcChar8 *value = nullptr;
if (FcPatternGetString(fontSet->fonts[i], FC_FAMILY, 0, &value) != FcResultMatch)
@@ -788,9 +790,8 @@ QStringList QFontconfigDatabase::fallbacksForFamily(const QString &family, QFont
// capitalize(value);
const QString familyName = QString::fromUtf8((const char *)value);
const QString familyNameCF = familyName.toCaseFolded();
- if (!duplicates.contains(familyNameCF)) {
+ if (!duplicates.hasSeen(familyNameCF)) {
fallbackFamilies << familyName;
- duplicates.insert(familyNameCF);
}
}
FcFontSetDestroy(fontSet);
diff --git a/src/widgets/itemviews/qtreewidget.cpp b/src/widgets/itemviews/qtreewidget.cpp
index ddb31523fd..0d4c391e1c 100644
--- a/src/widgets/itemviews/qtreewidget.cpp
+++ b/src/widgets/itemviews/qtreewidget.cpp
@@ -48,6 +48,8 @@
#include <private/qwidgetitemdata_p.h>
#include <private/qtreewidgetitemiterator_p.h>
+#include <QtCore/private/qduplicatetracker_p.h>
+
#include <algorithm>
QT_BEGIN_NAMESPACE
@@ -3175,13 +3177,12 @@ QList<QTreeWidgetItem*> QTreeWidget::selectedItems() const
const QModelIndexList indexes = selectionModel()->selectedIndexes();
QList<QTreeWidgetItem*> items;
items.reserve(indexes.count());
- QSet<QTreeWidgetItem *> seen;
+ QDuplicateTracker<QTreeWidgetItem *> seen;
seen.reserve(indexes.count());
for (const auto &index : indexes) {
QTreeWidgetItem *item = d->item(index);
- if (item->isHidden() || seen.contains(item))
+ if (item->isHidden() || seen.hasSeen(item))
continue;
- seen.insert(item);
items.append(item);
}
return items;
diff --git a/src/xml/dom/qdom.cpp b/src/xml/dom/qdom.cpp
index bbc877eead..26c1a2122b 100644
--- a/src/xml/dom/qdom.cpp
+++ b/src/xml/dom/qdom.cpp
@@ -60,6 +60,9 @@
#include <qshareddata.h>
#include <qdebug.h>
#include <qxmlstream.h>
+#include <private/qduplicatetracker_p.h>
+
+
#include <stdio.h>
QT_BEGIN_NAMESPACE
@@ -4081,10 +4084,10 @@ void QDomElementPrivate::save(QTextStream& s, int depth, int indent) const
}
s << '<' << qName << nsDecl;
- QSet<QString> outputtedPrefixes;
/* Write out attributes. */
if (!m_attr->map.isEmpty()) {
+ QDuplicateTracker<QString> outputtedPrefixes;
QHash<QString, QDomNodePrivate *>::const_iterator it = m_attr->map.constBegin();
for (; it != m_attr->map.constEnd(); ++it) {
s << ' ';
@@ -4105,9 +4108,8 @@ void QDomElementPrivate::save(QTextStream& s, int depth, int indent) const
* arrive in those situations. */
if((!it.value()->ownerNode ||
it.value()->ownerNode->prefix != it.value()->prefix) &&
- !outputtedPrefixes.contains(it.value()->prefix)) {
+ !outputtedPrefixes.hasSeen(it.value()->prefix)) {
s << " xmlns:" << it.value()->prefix << "=\"" << encodeText(it.value()->namespaceURI, s, true, true) << '\"';
- outputtedPrefixes.insert(it.value()->prefix);
}
}
}
diff --git a/tests/benchmarks/corelib/text/qstringlist/main.cpp b/tests/benchmarks/corelib/text/qstringlist/main.cpp
index ae355a8b89..9f184d0cf5 100644
--- a/tests/benchmarks/corelib/text/qstringlist/main.cpp
+++ b/tests/benchmarks/corelib/text/qstringlist/main.cpp
@@ -41,6 +41,9 @@ private slots:
void join() const;
void join_data() const;
+ void removeDuplicates() const;
+ void removeDuplicates_data() const;
+
void split_qlist_qbytearray() const;
void split_qlist_qbytearray_data() const { return split_data(); }
@@ -116,6 +119,42 @@ void tst_QStringList::join_data() const
<< QString();
}
+void tst_QStringList::removeDuplicates() const
+{
+ QFETCH(const QStringList, input);
+
+ QBENCHMARK {
+ auto copy = input;
+ copy.removeDuplicates();
+ }
+}
+
+void tst_QStringList::removeDuplicates_data() const
+{
+ QTest::addColumn<QStringList>("input");
+
+ const QStringList s = {"one", "two", "three"};
+
+ QTest::addRow("empty") << QStringList();
+ QTest::addRow("short-dup-0.00") << s;
+ QTest::addRow("short-dup-0.50") << (s + s);
+ QTest::addRow("short-dup-0.66") << (s + s + s);
+ QTest::addRow("short-dup-0.75") << (s + s + s + s);
+
+ const QStringList l = []() {
+ QStringList result;
+ const int n = 1000;
+ result.reserve(n);
+ for (int i = 0; i < n; ++i)
+ result.push_back(QString::number(i));
+ return result;
+ }();
+ QTest::addRow("long-dup-0.00") << l;
+ QTest::addRow("long-dup-0.50") << (l + l);
+ QTest::addRow("long-dup-0.66") << (l + l + l);
+ QTest::addRow("long-dup-0.75") << (l + l + l + l);
+}
+
void tst_QStringList::split_data() const
{
QTest::addColumn<QString>("input");
diff --git a/tests/benchmarks/corelib/text/qstringlist/qstringlist.pro b/tests/benchmarks/corelib/text/qstringlist/qstringlist.pro
index 5803e7da0e..2e7ae058f7 100644
--- a/tests/benchmarks/corelib/text/qstringlist/qstringlist.pro
+++ b/tests/benchmarks/corelib/text/qstringlist/qstringlist.pro
@@ -1,5 +1,6 @@
TARGET = tst_bench_qstringlist
CONFIG -= debug
CONFIG += release
+CONFIG += benchmark
QT = core testlib
SOURCES += main.cpp
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-19 21:15:42 +0000