From 0375757bfb3852ace3bf3237a7de0ed2dbb371d8 Mon Sep 17 00:00:00 2001 From: Lars Knoll Date: Fri, 7 Feb 2020 12:29:59 +0100 Subject: Implement emplace() for QHash and QMultiHash MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit 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 --- src/corelib/tools/qcache.h | 18 +- src/corelib/tools/qhash.cpp | 47 ++++++ src/corelib/tools/qhash.h | 238 ++++++++++++++------------- tests/auto/corelib/tools/qhash/tst_qhash.cpp | 85 +++++++++- 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 && std::is_nothrow_move_assignable_v) + 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 && std::is_nothrow_move_assignable_v) { @@ -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 template QHash::iterator QHash::emplace(const Key &key, Args&&... args) + \fn template template QHash::iterator QHash::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 void QHash::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 template QMultiHash::iterator QMultiHash::emplace(const Key &key, Args&&... args) + \fn template template QMultiHash::iterator QMultiHash::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 template QMultiHash::iterator QMultiHash::emplaceReplace(const Key &key, Args&&... args) + \fn template template QMultiHash::iterator QMultiHash::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 QMultiHash &QMultiHash::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 && std::is_nothrow_move_assignable_v) + template + static void createInPlace(Node *n, Key &&k, Args &&... args) + { new (n) Node{ std::move(k), T(std::forward(args)...) }; } + template + static void createInPlace(Node *n, const Key &k, Args &&... args) + { new (n) Node{ Key(k), T(std::forward(args)...) }; } + template + 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 && std::is_nothrow_copy_constructible_v) - { - return Node{ k, t }; - } - void replace(const T &t) noexcept(std::is_nothrow_assignable_v) - { - value = t; - } - void replace(T &&t) noexcept(std::is_nothrow_move_assignable_v) - { - value = std::move(t); + value = T(std::forward(args)...); } T &&takeValue() noexcept(std::is_nothrow_move_assignable_v) { @@ -116,18 +111,14 @@ struct Node { 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 + static void createInPlace(Node *n, Key &&k, Args &&...) + { new (n) Node{ std::move(k) }; } + template + static void createInPlace(Node *n, const Key &k, Args &&...) + { new (n) Node{ k }; } + template + 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 + static void createInPlace(MultiNode *n, Key &&k, Args &&... args) + { new (n) MultiNode(std::move(k), new Chain{ T(std::forward(args)...), nullptr }); } + template + static void createInPlace(MultiNode *n, const Key &k, Args &&... args) + { new (n) MultiNode(k, new Chain{ T(std::forward(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) - { - value->value = t; - } - void replace(T &&t) noexcept(std::is_nothrow_move_assignable_v) + template + 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)...), nullptr }; e->next = value; value = e; } + template + void emplaceValue(Args &&... args) + { + value->value = T(std::forward(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::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::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 + iterator emplace(const Key &key, Args &&... args) + { + return emplace(Key(key), std::forward(args)...); + } + + template + 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)...); + else + result.it.node()->emplaceValue(std::forward(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 @@ -1710,13 +1681,31 @@ public: return const_iterator(it); } iterator insert(const Key &key, const T &value) + { + return emplace(key, value); + } + + template + iterator emplace(const Key &key, Args &&... args) + { + return emplace(Key(key), std::forward(args)...); + } + + template + 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)...); + else + result.it.node()->insertMulti(std::forward(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::iterator replace(const Key &key, const T &value) + inline iterator replace(const Key &key, const T &value) + { + return emplaceReplace(key, value); + } + + template + iterator emplaceReplace(const Key &key, Args &&... args) + { + return emplaceReplace(Key(key), std::forward(args)...); + } + + template + 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)...); + } else { + result.it.node()->emplaceValue(std::forward(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 MyMap; @@ -1650,6 +1679,50 @@ void tst_QHash::insert_hash() } } +void tst_QHash::emplace() +{ + { + QHash 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 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) {} -- cgit v1.2.3