summaryrefslogtreecommitdiffstats
path: root/src/corelib/tools/qhash.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/corelib/tools/qhash.h')
-rw-r--r--src/corelib/tools/qhash.h110
1 files changed, 81 insertions, 29 deletions
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h
index adb7782efc..7abbeabeae 100644
--- a/src/corelib/tools/qhash.h
+++ b/src/corelib/tools/qhash.h
@@ -1,32 +1,38 @@
/****************************************************************************
**
-** Copyright (C) 2015 The Qt Company Ltd.
+** Copyright (C) 2016 The Qt Company Ltd.
** Copyright (C) 2015 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Marc Mutz <marc.mutz@kdab.com>
-** Contact: http://www.qt.io/licensing/
+** Contact: https://www.qt.io/licensing/
**
** This file is part of the QtCore module of the Qt Toolkit.
**
-** $QT_BEGIN_LICENSE:LGPL21$
+** $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 http://www.qt.io/terms-conditions. For further
-** information use the contact form at http://www.qt.io/contact-us.
+** 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 2.1 or version 3 as published by the Free
-** Software Foundation and appearing in the file LICENSE.LGPLv21 and
-** LICENSE.LGPLv3 included in the packaging of this file. Please review the
-** following information to ensure the GNU Lesser General Public License
-** requirements will be met: https://www.gnu.org/licenses/lgpl.html and
-** http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+** 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.
**
-** As a special exception, The Qt Company gives you certain additional
-** rights. These rights are described in The Qt Company LGPL Exception
-** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+** 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$
**
@@ -297,6 +303,7 @@ public:
{
friend class const_iterator;
friend class QHash<Key, T>;
+ friend class QSet<Key>;
QHashData::Node *i;
public:
@@ -353,6 +360,7 @@ public:
class const_iterator
{
friend class iterator;
+ friend class QHash<Key, T>;
friend class QSet<Key>;
QHashData::Node *i;
@@ -450,7 +458,10 @@ public:
inline key_iterator keyBegin() const { return key_iterator(begin()); }
inline key_iterator keyEnd() const { return key_iterator(end()); }
- iterator erase(iterator it);
+ QPair<iterator, iterator> equal_range(const Key &key);
+ QPair<const_iterator, const_iterator> equal_range(const Key &key) const Q_DECL_NOTHROW;
+ iterator erase(iterator it) { return erase(const_iterator(it.i)); }
+ iterator erase(const_iterator it);
// more Qt
typedef iterator Iterator;
@@ -487,15 +498,18 @@ private:
static void duplicateNode(QHashData::Node *originalNode, void *newNode);
- bool isValidIterator(const iterator &it) const
+ bool isValidIterator(const iterator &it) const Q_DECL_NOTHROW
+ { return isValidNode(it.i); }
+ bool isValidIterator(const const_iterator &it) const Q_DECL_NOTHROW
+ { return isValidNode(it.i); }
+ bool isValidNode(QHashData::Node *node) const Q_DECL_NOTHROW
{
#if defined(QT_DEBUG) && !defined(Q_HASH_NO_ITERATOR_DEBUG)
- QHashData::Node *node = it.i;
while (node->next)
node = node->next;
return (static_cast<void *>(node) == d);
#else
- Q_UNUSED(it);
+ Q_UNUSED(node);
return true;
#endif
}
@@ -540,11 +554,15 @@ QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anex
template <class Key, class T>
Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash &other)
{
- QHash copy(other);
- const_iterator it = copy.constEnd();
- while (it != copy.constBegin()) {
- --it;
- insertMulti(it.key(), it.value());
+ if (d == &QHashData::shared_null) {
+ *this = other;
+ } else {
+ QHash copy(other);
+ const_iterator it = copy.constEnd();
+ while (it != copy.constBegin()) {
+ --it;
+ insertMulti(it.key(), it.value());
+ }
}
return *this;
}
@@ -807,30 +825,31 @@ Q_OUTOFLINE_TEMPLATE T QHash<Key, T>::take(const Key &akey)
}
template <class Key, class T>
-Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::erase(iterator it)
+Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::erase(const_iterator it)
{
Q_ASSERT_X(isValidIterator(it), "QHash::erase", "The specified iterator argument 'it' is invalid");
- if (it == iterator(e))
- return it;
+ if (it == const_iterator(e))
+ return iterator(it.i);
if (d->ref.isShared()) {
+ // save 'it' across the detach:
int bucketNum = (it.i->h % d->numBuckets);
- iterator bucketIterator(*(d->buckets + bucketNum));
+ const_iterator bucketIterator(*(d->buckets + bucketNum));
int stepsFromBucketStartToIte = 0;
while (bucketIterator != it) {
++stepsFromBucketStartToIte;
++bucketIterator;
}
detach();
- it = iterator(*(d->buckets + bucketNum));
+ it = const_iterator(*(d->buckets + bucketNum));
while (stepsFromBucketStartToIte > 0) {
--stepsFromBucketStartToIte;
++it;
}
}
- iterator ret = it;
+ iterator ret(it.i);
++ret;
Node *node = concrete(it.i);
@@ -932,6 +951,39 @@ Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash &other) const
}
template <class Key, class T>
+QPair<typename QHash<Key, T>::iterator, typename QHash<Key, T>::iterator> QHash<Key, T>::equal_range(const Key &akey)
+{
+ detach();
+ auto pair = qAsConst(*this).equal_range(akey);
+ return qMakePair(iterator(pair.first.i), iterator(pair.second.i));
+}
+
+template <class Key, class T>
+QPair<typename QHash<Key, T>::const_iterator, typename QHash<Key, T>::const_iterator> QHash<Key, T>::equal_range(const Key &akey) const Q_DECL_NOTHROW
+{
+ uint h;
+ Node *node = *findNode(akey, &h);
+ const_iterator firstIt = const_iterator(node);
+
+ if (node != e) {
+ // equal keys must hash to the same value and so they all
+ // end up in the same bucket. So we can use node->next,
+ // which only works within a bucket, instead of (out-of-line)
+ // QHashData::nextNode()
+ while (node->next != e && node->next->key == akey)
+ node = node->next;
+
+ // 'node' may be the last node in the bucket. To produce the end iterator, we'd
+ // need to enter the next bucket in this case, so we need to use
+ // QHashData::nextNode() here, which, unlike node->next above, can move between
+ // buckets.
+ node = concrete(QHashData::nextNode(reinterpret_cast<QHashData::Node *>(node)));
+ }
+
+ return qMakePair(firstIt, const_iterator(node));
+}
+
+template <class Key, class T>
class QMultiHash : public QHash<Key, T>
{
public:
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-19 09:21:20 +0000