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>

3 files changed, 183 insertions, 120 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)