summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-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) {}
generated by cgit v1.2.3 (git 2.25.1) at 2024-05-11 10:17:56 +0000