summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorLars Knoll <lars.knoll@qt.io>2020-02-07 12:29:59 +0100
committerLars Knoll <lars.knoll@qt.io>2020-04-09 20:03:32 +0200
commit0375757bfb3852ace3bf3237a7de0ed2dbb371d8 (patch)
treeda0241b0cb4870b42a72cd572e7b6845a4d8700e
parentc6cdf38e752c22babdbe645366bdfb7ce51d01ff (diff)
Implement emplace() for QHash and QMultiHash
At the same time use the opportunity to refactor the insertion code inside the implementation of QHash to avoid copy and move constructors as much as possible and always construct nodes in place. Change-Id: I951b4cf2c77a17f7db825c6a776aae38c2662d23 Reviewed-by: MÃ¥rten Nordheim <marten.nordheim@qt.io>
-rw-r--r--src/corelib/tools/qcache.h18
-rw-r--r--src/corelib/tools/qhash.cpp47
-rw-r--r--src/corelib/tools/qhash.h238
-rw-r--r--tests/auto/corelib/tools/qhash/tst_qhash.cpp85
4 files changed, 262 insertions, 126 deletions
diff --git a/src/corelib/tools/qcache.h b/src/corelib/tools/qcache.h
index f043ea9cff..3582a44e32 100644
--- a/src/corelib/tools/qcache.h
+++ b/src/corelib/tools/qcache.h
@@ -99,9 +99,13 @@ class QCache
value(std::move(t))
{
}
- static Node create(Key &&k, Value &&t) noexcept(std::is_nothrow_move_assignable_v<Key> && std::is_nothrow_move_assignable_v<T>)
+ static void createInPlace(Node *n, const Key &k, T *o, int cost)
{
- return Node(std::move(k), std::move(t));
+ new (n) Node{ Key(k), Value(o, cost) };
+ }
+ void emplace(T *o, int cost)
+ {
+ value = Value(o, cost);
}
static Node create(const Key &k, Value &&t) noexcept(std::is_nothrow_move_assignable_v<Key> && std::is_nothrow_move_assignable_v<T>)
{
@@ -230,9 +234,15 @@ public:
return false;
}
trim(mx - cost);
- auto it = d.insert(Node::create(Key(key), Value(object, cost)));
+ auto result = d.findOrInsert(key);
+ Node *n = result.it.node();
+ if (result.initialized) {
+ cost -= n->value.cost;
+ result.it.node()->emplace(object, cost);
+ } else {
+ Node::createInPlace(n, key, object, cost);
+ }
total += cost;
- Node *n = it.node();
n->prev = &chain;
n->next = chain.next;
chain.next->prev = n;
diff --git a/src/corelib/tools/qhash.cpp b/src/corelib/tools/qhash.cpp
index ab699a7f94..4b3996d432 100644
--- a/src/corelib/tools/qhash.cpp
+++ b/src/corelib/tools/qhash.cpp
@@ -1422,6 +1422,18 @@ size_t qHash(long double key, size_t seed) noexcept
is replaced with \a value.
*/
+/*!
+ \fn template <typename T> template <typename ...Args> QHash<Key, T>::iterator QHash<Key, T>::emplace(const Key &key, Args&&... args)
+ \fn template <typename T> template <typename ...Args> QHash<Key, T>::iterator QHash<Key, T>::emplace(Key &&key, Args&&... args)
+
+ Inserts a new element into the container. This new element
+ is constructed in-place using \a args as the arguments for its
+ construction.
+
+ Returns an iterator pointing to the new element.
+*/
+
+
/*! \fn template <class Key, class T> void QHash<Key, T>::insert(const QHash &other)
\since 5.15
@@ -2099,6 +2111,41 @@ size_t qHash(long double key, size_t seed) noexcept
\sa replace()
*/
+/*!
+ \fn template <typename T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplace(const Key &key, Args&&... args)
+ \fn template <typename T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplace(Key &&key, Args&&... args)
+
+ Inserts a new element into the container. This new element
+ is constructed in-place using \a args as the arguments for its
+ construction.
+
+ If there is already an item with the same key in the hash, this
+ function will simply create a new one. (This behavior is
+ different from replace(), which overwrites the value of an
+ existing item.)
+
+ Returns an iterator pointing to the new element.
+
+ \sa insert
+*/
+
+/*!
+ \fn template <typename T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplaceReplace(const Key &key, Args&&... args)
+ \fn template <typename T> template <typename ...Args> QMultiHash<Key, T>::iterator QMultiHash<Key, T>::emplaceReplace(Key &&key, Args&&... args)
+
+ Inserts a new element into the container. This new element
+ is constructed in-place using \a args as the arguments for its
+ construction.
+
+ If there is already an item with the same key in the hash, that item's
+ value is replaced with a value constructed from \a args.
+
+ Returns an iterator pointing to the new element.
+
+ \sa replace, emplace
+*/
+
+
/*! \fn template <class Key, class T> QMultiHash &QMultiHash<Key, T>::unite(const QMultiHash &other)
\since 5.13
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index 1d3f84d0ec..6b0b6525ac 100644
--- a/src/corelib/tools/qhash.h
+++ b/src/corelib/tools/qhash.h
@@ -87,21 +87,16 @@ struct Node
Key key;
T value;
- static Node create(Key &&k, T &&t) noexcept(std::is_nothrow_move_assignable_v<Key> && std::is_nothrow_move_assignable_v<T>)
+ template<typename ...Args>
+ static void createInPlace(Node *n, Key &&k, Args &&... args)
+ { new (n) Node{ std::move(k), T(std::forward<Args>(args)...) }; }
+ template<typename ...Args>
+ static void createInPlace(Node *n, const Key &k, Args &&... args)
+ { new (n) Node{ Key(k), T(std::forward<Args>(args)...) }; }
+ template<typename ...Args>
+ void emplaceValue(Args &&... args)
{
- return Node{ std::move(k), std::move(t) };
- }
- static Node create(const Key &k, const T &t) noexcept(std::is_nothrow_copy_constructible_v<Key> && std::is_nothrow_copy_constructible_v<T>)
- {
- return Node{ k, t };
- }
- void replace(const T &t) noexcept(std::is_nothrow_assignable_v<T>)
- {
- value = t;
- }
- void replace(T &&t) noexcept(std::is_nothrow_move_assignable_v<T>)
- {
- value = std::move(t);
+ value = T(std::forward<Args>(args)...);
}
T &&takeValue() noexcept(std::is_nothrow_move_assignable_v<T>)
{
@@ -116,18 +111,14 @@ struct Node<Key, QHashDummyValue> {
using ValueType = QHashDummyValue;
Key key;
- static Node create(Key &&k, ValueType &&)
- {
- return Node{ std::move(k) };
- }
- static Node create(const Key &k, const ValueType &)
- {
- return Node{ k };
- }
- void replace(const ValueType &)
- {
- }
- void replace(ValueType &&)
+ template<typename ...Args>
+ static void createInPlace(Node *n, Key &&k, Args &&...)
+ { new (n) Node{ std::move(k) }; }
+ template<typename ...Args>
+ static void createInPlace(Node *n, const Key &k, Args &&...)
+ { new (n) Node{ k }; }
+ template<typename ...Args>
+ void emplaceValue(Args &&...)
{
}
ValueType takeValue() { return QHashDummyValue(); }
@@ -176,16 +167,12 @@ struct MultiNode
Key key;
Chain *value;
- static MultiNode create(Key &&k, T &&t)
- {
- Chain *c = new Chain{ std::move(t), nullptr };
- return MultiNode(std::move(k), c);
- }
- static MultiNode create(const Key &k, const T &t)
- {
- Chain *c = new Chain{ t, nullptr };
- return MultiNode(k, c);
- }
+ template<typename ...Args>
+ static void createInPlace(MultiNode *n, Key &&k, Args &&... args)
+ { new (n) MultiNode(std::move(k), new Chain{ T(std::forward<Args>(args)...), nullptr }); }
+ template<typename ...Args>
+ static void createInPlace(MultiNode *n, const Key &k, Args &&... args)
+ { new (n) MultiNode(k, new Chain{ T(std::forward<Args>(args)...), nullptr }); }
MultiNode(const Key &k, Chain *c)
: key(k),
@@ -226,20 +213,18 @@ struct MultiNode
n->value = nullptr;
return size;
}
- void replace(const T &t) noexcept(std::is_nothrow_assignable_v<T, T>)
- {
- value->value = t;
- }
- void replace(T &&t) noexcept(std::is_nothrow_move_assignable_v<T>)
+ template<typename ...Args>
+ void insertMulti(Args &&... args)
{
- value->value = std::move(t);
- }
- void insertMulti(const T &t)
- {
- Chain *e = new Chain{ t, nullptr };
+ Chain *e = new Chain{ T(std::forward<Args>(args)...), nullptr };
e->next = value;
value = e;
}
+ template<typename ...Args>
+ void emplaceValue(Args &&... args)
+ {
+ value->value = T(std::forward<Args>(args)...);
+ }
// compiler generated move operators are fine
};
@@ -305,7 +290,7 @@ struct Span {
entries = nullptr;
}
}
- void insert(size_t i, Node &&n)
+ Node *insert(size_t i)
{
Q_ASSERT(i <= NEntries);
Q_ASSERT(offsets[i] == UnusedEntry);
@@ -315,7 +300,7 @@ struct Span {
Q_ASSERT(entry < allocated);
nextFree = entries[entry].nextFree();
offsets[i] = entry;
- new (&entries[entry].node()) Node(std::move(n));
+ return &entries[entry].node();
}
void erase(size_t bucket) noexcept(std::is_nothrow_destructible<Node>::value)
{
@@ -471,7 +456,8 @@ struct Data
iterator it{ this, s*Span::NEntries + index };
Q_ASSERT(it.isUnused());
- spans[it.span()].insert(it.index(), std::move(Node(n)));
+ Node *newNode = spans[it.span()].insert(it.index());
+ new (newNode) Node(n);
}
}
}
@@ -491,7 +477,8 @@ struct Data
const Node &n = span.at(index);
iterator it = find(n.key);
Q_ASSERT(it.isUnused());
- spans[it.span()].insert(it.index(), std::move(Node(n)));
+ Node *newNode = spans[it.span()].insert(it.index());
+ new (newNode) Node(n);
}
}
}
@@ -563,7 +550,8 @@ struct Data
Node &n = span.at(index);
iterator it = find(n.key);
Q_ASSERT(it.isUnused());
- spans[it.span()].insert(it.index(), std::move(n));
+ Node *newNode = spans[it.span()].insert(it.index());
+ new (newNode) Node(std::move(n));
}
span.freeData();
}
@@ -622,62 +610,24 @@ struct Data
return it.node();
}
- Node *findAndInsertNode(const Key &key) noexcept
- {
- if (shouldGrow())
- rehash(size + 1);
- iterator it = find(key);
- if (it.isUnused()) {
- spans[it.span()].insert(it.index(), Node::create(key, T()));
- ++size;
- }
- return it.node();
- }
-
-
- iterator insert(Node &&n)
- {
- if (shouldGrow())
- rehash(size + 1);
- iterator it = find(n.key);
- if (it.isUnused()) {
- spans[it.span()].insert(it.index(), std::move(n));
- ++size;
- } else {
- it.node()->replace(std::move(n.takeValue()));
- }
- return it;
- }
-
- iterator insert(const Key &key, const T &value)
- {
- if (shouldGrow())
- rehash(size + 1);
- auto it = find(key);
- if (it.isUnused()) {
- spans[it.span()].insert(it.index(), Node::create(key, value));
- ++size;
- } else {
- it.node()->replace(value);
- }
- return it;
- }
+ struct InsertionResult {
+ iterator it;
+ bool initialized;
+ };
- iterator insertMulti(const Key &key, const T &value)
+ InsertionResult findOrInsert(const Key &key) noexcept
{
if (shouldGrow())
rehash(size + 1);
- auto it = find(key);
+ iterator it = find(key);
if (it.isUnused()) {
- spans[it.span()].insert(it.index(), std::move(Node::create(key, value)));
+ spans[it.span()].insert(it.index());
++size;
- } else {
- it.node()->insertMulti(value);
+ return { it, false };
}
- return it;
+ return { it, true };
}
-
iterator erase(iterator it) noexcept(std::is_nothrow_destructible<Node>::value)
{
size_t bucket = it.bucket;
@@ -963,9 +913,11 @@ public:
T &operator[](const Key &key)
{
detach();
- Node *n = d->findAndInsertNode(key);
- Q_ASSERT(n);
- return n->value;
+ auto result = d->findOrInsert(key);
+ Q_ASSERT(!result.it.atEnd());
+ if (!result.initialized)
+ Node::createInPlace(result.it.node(), key, T());
+ return result.it.node()->value;
}
const T operator[](const Key &key) const noexcept
@@ -1179,11 +1131,9 @@ public:
}
iterator insert(const Key &key, const T &value)
{
- detach();
-
- auto i = d->insert(Node::create(key, value));
- return iterator(i);
+ return emplace(key, value);
}
+
void insert(const QHash &hash)
{
if (d == hash.d || !hash.d)
@@ -1196,7 +1146,26 @@ public:
detach();
for (auto it = hash.begin(); it != hash.end(); ++it)
- insert(it.key(), it.value());
+ emplace(it.key(), it.value());
+ }
+
+ template <typename ...Args>
+ iterator emplace(const Key &key, Args &&... args)
+ {
+ return emplace(Key(key), std::forward<Args>(args)...);
+ }
+
+ template <typename ...Args>
+ iterator emplace(Key &&key, Args &&... args)
+ {
+ detach();
+
+ auto result = d->findOrInsert(key);
+ if (!result.initialized)
+ Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...);
+ else
+ result.it.node()->emplaceValue(std::forward<Args>(args)...);
+ return iterator(result.it);
}
float load_factor() const noexcept { return d ? d->loadFactor() : 0; }
@@ -1427,9 +1396,11 @@ public:
T &operator[](const Key &key)
{
detach();
- Node *n = d->findAndInsertNode(key);
- Q_ASSERT(n);
- return n->value->value;
+ auto result = d->findOrInsert(key);
+ Q_ASSERT(!result.it.atEnd());
+ if (!result.initialized)
+ Node::createInPlace(result.it.node(), key, T());
+ return result.it.node()->value->value;
}
const T operator[](const Key &key) const noexcept
@@ -1711,12 +1682,30 @@ public:
}
iterator insert(const Key &key, const T &value)
{
+ return emplace(key, value);
+ }
+
+ template <typename ...Args>
+ iterator emplace(const Key &key, Args &&... args)
+ {
+ return emplace(Key(key), std::forward<Args>(args)...);
+ }
+
+ template <typename ...Args>
+ iterator emplace(Key &&key, Args &&... args)
+ {
detach();
- auto it = d->insertMulti(key, value);
+
+ auto result = d->findOrInsert(key);
+ if (!result.initialized)
+ Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...);
+ else
+ result.it.node()->insertMulti(std::forward<Args>(args)...);
++m_size;
- return iterator(it);
+ return iterator(result.it);
}
+
float load_factor() const noexcept { return d ? d->loadFactor() : 0; }
static float max_load_factor() noexcept { return 0.5; }
size_t bucket_count() const noexcept { return d ? d->numBuckets : 0; }
@@ -1724,13 +1713,30 @@ public:
inline bool empty() const noexcept { return isEmpty(); }
- inline typename QMultiHash<Key, T>::iterator replace(const Key &key, const T &value)
+ inline iterator replace(const Key &key, const T &value)
+ {
+ return emplaceReplace(key, value);
+ }
+
+ template <typename ...Args>
+ iterator emplaceReplace(const Key &key, Args &&... args)
+ {
+ return emplaceReplace(Key(key), std::forward<Args>(args)...);
+ }
+
+ template <typename ...Args>
+ iterator emplaceReplace(Key &&key, Args &&... args)
{
detach();
- qsizetype s = d->size;
- auto it = d->insert(key, value);
- m_size += d->size - s;
- return iterator(it);
+
+ auto result = d->findOrInsert(key);
+ if (!result.initialized) {
+ ++m_size;
+ Node::createInPlace(result.it.node(), std::move(key), std::forward<Args>(args)...);
+ } else {
+ result.it.node()->emplaceValue(std::forward<Args>(args)...);
+ }
+ return iterator(result.it);
}
inline QMultiHash &operator+=(const QMultiHash &other)
diff --git a/tests/auto/corelib/tools/qhash/tst_qhash.cpp b/tests/auto/corelib/tools/qhash/tst_qhash.cpp
index da1cb15cd8..c3e5d8d083 100644
--- a/tests/auto/corelib/tools/qhash/tst_qhash.cpp
+++ b/tests/auto/corelib/tools/qhash/tst_qhash.cpp
@@ -70,6 +70,8 @@ private slots:
void equal_range();
void insert_hash();
+ void emplace();
+
void badHashFunction();
};
@@ -96,26 +98,53 @@ int Foo::count = 0;
class MyClass
{
public:
- MyClass() { ++count;
+ MyClass()
+ {
+ ++count;
+ }
+ MyClass( const QString& c)
+ {
+ count++;
+ str = c;
}
- MyClass( const QString& c) {
- count++; str = c;
+ MyClass(const QString &a, const QString &b)
+ {
+ count++;
+ str = a + b;
}
~MyClass() {
count--;
}
MyClass( const MyClass& c ) {
- count++; str = c.str;
+ count++;
+ ++copies;
+ str = c.str;
}
MyClass &operator =(const MyClass &o) {
- str = o.str; return *this;
+ str = o.str;
+ ++copies;
+ return *this;
+ }
+ MyClass(MyClass &&c) {
+ count++;
+ ++moves;
+ str = c.str;
+ }
+ MyClass &operator =(MyClass &&o) {
+ str = o.str;
+ ++moves;
+ return *this;
}
QString str;
static int count;
+ static int copies;
+ static int moves;
};
-int MyClass::count = 0;
+int MyClass::count = 0;
+int MyClass::copies = 0;
+int MyClass::moves = 0;
typedef QHash<QString, MyClass> MyMap;
@@ -1650,6 +1679,50 @@ void tst_QHash::insert_hash()
}
}
+void tst_QHash::emplace()
+{
+ {
+ QHash<QString, MyClass> hash;
+ MyClass::copies = 0;
+ MyClass::moves = 0;
+
+ hash.emplace(QString("a"), QString("a"));
+ QCOMPARE(hash["a"].str, "a");
+ QCOMPARE(MyClass::copies, 0);
+ QCOMPARE(MyClass::moves, 0);
+ hash.emplace(QString("ab"), QString("ab"));
+ QCOMPARE(hash["ab"].str, "ab");
+ QCOMPARE(MyClass::copies, 0);
+ QCOMPARE(MyClass::moves, 0);
+ hash.emplace(QString("ab"), QString("abc"));
+ QCOMPARE(hash["ab"].str, "abc");
+ QCOMPARE(MyClass::copies, 0);
+ QCOMPARE(MyClass::moves, 1);
+ }
+ {
+ QMultiHash<QString, MyClass> hash;
+ MyClass::copies = 0;
+ MyClass::moves = 0;
+
+ hash.emplace(QString("a"), QString("a"));
+ QCOMPARE(hash["a"].str, "a");
+ QCOMPARE(MyClass::copies, 0);
+ QCOMPARE(MyClass::moves, 0);
+ hash.emplace(QString("ab"), QString("ab"));
+ QCOMPARE(hash["ab"].str, "ab");
+ QCOMPARE(MyClass::copies, 0);
+ QCOMPARE(MyClass::moves, 0);
+ hash.emplace(QString("ab"), QString("abc"));
+ QCOMPARE(hash["ab"].str, "abc");
+ QCOMPARE(MyClass::copies, 0);
+ QCOMPARE(MyClass::moves, 0);
+ hash.emplaceReplace(QString("ab"), QString("abcd"));
+ QCOMPARE(hash["ab"].str, "abcd");
+ QCOMPARE(MyClass::copies, 0);
+ QCOMPARE(MyClass::moves, 1);
+ }
+}
+
struct BadKey {
int k;
BadKey(int i) : k(i) {}