diff options
Diffstat (limited to 'src/corelib/tools/qhash.h')
-rw-r--r-- | src/corelib/tools/qhash.h | 96 |
1 files changed, 72 insertions, 24 deletions
diff --git a/src/corelib/tools/qhash.h b/src/corelib/tools/qhash.h index a18dd74706..5e3016d313 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 } @@ -807,30 +821,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 +947,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: |