1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Copyright (C) 2015 Klarälvdalens Datakonsult AB, a KDAB Group company, info@kdab.com, author Marc Mutz <marc.mutz@kdab.com>
5** Contact: https://www.qt.io/licensing/
6**
7** This file is part of the QtCore module of the Qt Toolkit.
8**
9** $QT_BEGIN_LICENSE:LGPL$
10** Commercial License Usage
11** Licensees holding valid commercial Qt licenses may use this file in
12** accordance with the commercial license agreement provided with the
13** Software or, alternatively, in accordance with the terms contained in
14** a written agreement between you and The Qt Company. For licensing terms
15** and conditions see https://www.qt.io/terms-conditions. For further
16** information use the contact form at https://www.qt.io/contact-us.
17**
18** GNU Lesser General Public License Usage
19** Alternatively, this file may be used under the terms of the GNU Lesser
20** General Public License version 3 as published by the Free Software
21** Foundation and appearing in the file LICENSE.LGPL3 included in the
22** packaging of this file. Please review the following information to
23** ensure the GNU Lesser General Public License version 3 requirements
24** will be met: https://www.gnu.org/licenses/lgpl-3.0.html.
25**
26** GNU General Public License Usage
27** Alternatively, this file may be used under the terms of the GNU
28** General Public License version 2.0 or (at your option) the GNU General
29** Public license version 3 or any later version approved by the KDE Free
30** Qt Foundation. The licenses are as published by the Free Software
31** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3
32** included in the packaging of this file. Please review the following
33** information to ensure the GNU General Public License requirements will
34** be met: https://www.gnu.org/licenses/gpl-2.0.html and
35** https://www.gnu.org/licenses/gpl-3.0.html.
36**
37** $QT_END_LICENSE$
38**
39****************************************************************************/
40
41#ifndef QHASH_H
42#define QHASH_H
43
44#include <QtCore/qchar.h>
45#include <QtCore/qiterator.h>
46#include <QtCore/qlist.h>
47#include <QtCore/qrefcount.h>
48#include <QtCore/qhashfunctions.h>
49#include <QtCore/qcontainertools_impl.h>
50
51#include <algorithm>
52#include <initializer_list>
53
54#if defined(Q_CC_MSVC)
55#pragma warning( push )
56#pragma warning( disable : 4311 ) // disable pointer truncation warning
57#pragma warning( disable : 4127 ) // conditional expression is constant
58#endif
59
60QT_BEGIN_NAMESPACE
61
62struct Q_CORE_EXPORT QHashData
63{
64 struct Node {
65 Node *next;
66 uint h;
67 };
68
69 Node *fakeNext;
70 Node **buckets;
71 QtPrivate::RefCount ref;
72 int size;
73 int nodeSize;
74 short userNumBits;
75 short numBits;
76 int numBuckets;
77 uint seed;
78 uint sharable : 1;
79 uint strictAlignment : 1;
80 uint reserved : 30;
81
82 void *allocateNode(int nodeAlign);
83 void freeNode(void *node);
84 QHashData *detach_helper(void (*node_duplicate)(Node *, void *), void (*node_delete)(Node *),
85 int nodeSize, int nodeAlign);
86 bool willGrow();
87 void hasShrunk();
88 void rehash(int hint);
89 void free_helper(void (*node_delete)(Node *));
90 Node *firstNode();
91#ifdef QT_QHASH_DEBUG
92 void dump();
93 void checkSanity();
94#endif
95 static Node *nextNode(Node *node);
96 static Node *previousNode(Node *node);
97
98 static const QHashData shared_null;
99};
100
101inline bool QHashData::willGrow()
102{
103 if (size >= numBuckets) {
104 rehash(numBits + 1);
105 return true;
106 } else {
107 return false;
108 }
109}
110
111inline void QHashData::hasShrunk()
112{
113 if (size <= (numBuckets >> 3) && numBits > userNumBits) {
114 QT_TRY {
115 rehash(qMax(int(numBits) - 2, int(userNumBits)));
116 } QT_CATCH(const std::bad_alloc &) {
117 // ignore bad allocs - shrinking shouldn't throw. rehash is exception safe.
118 }
119 }
120}
121
122inline QHashData::Node *QHashData::firstNode()
123{
124 Node *e = reinterpret_cast<Node *>(this);
125 Node **bucket = buckets;
126 int n = numBuckets;
127 while (n--) {
128 if (*bucket != e)
129 return *bucket;
130 ++bucket;
131 }
132 return e;
133}
134
135struct QHashDummyValue
136{
137};
138
139constexpr bool operator==(const QHashDummyValue &, const QHashDummyValue &) noexcept
140{
141 return true;
142}
143
144Q_DECLARE_TYPEINFO(QHashDummyValue, Q_MOVABLE_TYPE | Q_DUMMY_TYPE);
145
146template <class Key, class T>
147struct QHashNode
148{
149 QHashNode *next;
150 const uint h;
151 const Key key;
152 T value;
153
154 inline QHashNode(const Key &key0, const T &value0, uint hash, QHashNode *n)
155 : next(n), h(hash), key(key0), value(value0) {}
156 inline bool same_key(uint h0, const Key &key0) const { return h0 == h && key0 == key; }
157
158private:
159 Q_DISABLE_COPY(QHashNode)
160};
161
162// Specialize for QHashDummyValue in order to save some memory
163template <class Key>
164struct QHashNode<Key, QHashDummyValue>
165{
166 union {
167 QHashNode *next;
168 QHashDummyValue value;
169 };
170 const uint h;
171 const Key key;
172
173 inline QHashNode(const Key &key0, const QHashDummyValue &, uint hash, QHashNode *n)
174 : next(n), h(hash), key(key0) {}
175 inline bool same_key(uint h0, const Key &key0) const { return h0 == h && key0 == key; }
176
177private:
178 Q_DISABLE_COPY(QHashNode)
179};
180
181
182#if 0
183// ###
184// The introduction of the QHash random seed breaks this optimization, as it
185// relies on qHash(int i) = i. If the hash value is salted, then the hash
186// table becomes corrupted.
187//
188// A bit more research about whether it makes sense or not to salt integer
189// keys (and in general keys whose hash value is easy to invert)
190// is needed, or about how keep this optimization and the seed (f.i. by
191// specializing QHash for integer values, and re-apply the seed during lookup).
192//
193// Be aware that such changes can easily be binary incompatible, and therefore
194// cannot be made during the Qt 5 lifetime.
195#define Q_HASH_DECLARE_INT_NODES(key_type) \
196 template <class T> \
197 struct QHashDummyNode<key_type, T> { \
198 QHashDummyNode *next; \
199 union { uint h; key_type key; }; \
200\
201 inline QHashDummyNode(key_type /* key0 */) {} \
202 }; \
203\
204 template <class T> \
205 struct QHashNode<key_type, T> { \
206 QHashNode *next; \
207 union { uint h; key_type key; }; \
208 T value; \
209\
210 inline QHashNode(key_type /* key0 */) {} \
211 inline QHashNode(key_type /* key0 */, const T &value0) : value(value0) {} \
212 inline bool same_key(uint h0, key_type) const { return h0 == h; } \
213 }
214
215#if defined(Q_BYTE_ORDER) && Q_BYTE_ORDER == Q_LITTLE_ENDIAN
216Q_HASH_DECLARE_INT_NODES(short);
217Q_HASH_DECLARE_INT_NODES(ushort);
218#endif
219Q_HASH_DECLARE_INT_NODES(int);
220Q_HASH_DECLARE_INT_NODES(uint);
221#undef Q_HASH_DECLARE_INT_NODES
222#endif // #if 0
223
224template <class Key, class T>
225class QHash
226{
227 typedef QHashNode<Key, T> Node;
228
229 union {
230 QHashData *d;
231 QHashNode<Key, T> *e;
232 };
233
234 static inline Node *concrete(QHashData::Node *node) {
235 return reinterpret_cast<Node *>(node);
236 }
237
238 static inline int alignOfNode() { return qMax<int>(sizeof(void*), Q_ALIGNOF(Node)); }
239
240public:
241 inline QHash() noexcept : d(const_cast<QHashData *>(&QHashData::shared_null)) { }
242 inline QHash(std::initializer_list<std::pair<Key,T> > list)
243 : d(const_cast<QHashData *>(&QHashData::shared_null))
244 {
245 reserve(int(list.size()));
246 for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
247 insert(it->first, it->second);
248 }
249 QHash(const QHash &other) : d(other.d) { d->ref.ref(); if (!d->sharable) detach(); }
250 ~QHash() { if (!d->ref.deref()) freeData(d); }
251
252 QHash &operator=(const QHash &other);
253 QHash(QHash &&other) noexcept : d(other.d) { other.d = const_cast<QHashData *>(&QHashData::shared_null); }
254 QHash &operator=(QHash &&other) noexcept
255 { QHash moved(std::move(other)); swap(moved); return *this; }
256#ifdef Q_QDOC
257 template <typename InputIterator>
258 QHash(InputIterator f, InputIterator l);
259#else
260 template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasKeyAndValue<InputIterator> = true>
261 QHash(InputIterator f, InputIterator l)
262 : QHash()
263 {
264 QtPrivate::reserveIfForwardIterator(this, f, l);
265 for (; f != l; ++f)
266 insert(f.key(), f.value());
267 }
268
269 template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true>
270 QHash(InputIterator f, InputIterator l)
271 : QHash()
272 {
273 QtPrivate::reserveIfForwardIterator(this, f, l);
274 for (; f != l; ++f)
275 insert(f->first, f->second);
276 }
277#endif
278 void swap(QHash &other) noexcept { qSwap(d, other.d); }
279
280 bool operator==(const QHash &other) const;
281 bool operator!=(const QHash &other) const { return !(*this == other); }
282
283 inline int size() const { return d->size; }
284
285 inline bool isEmpty() const { return d->size == 0; }
286
287 inline int capacity() const { return d->numBuckets; }
288 void reserve(int size);
289 inline void squeeze() { reserve(1); }
290
291 inline void detach() { if (d->ref.isShared()) detach_helper(); }
292 inline bool isDetached() const { return !d->ref.isShared(); }
293#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
294 inline void setSharable(bool sharable) { if (!sharable) detach(); if (d != &QHashData::shared_null) d->sharable = sharable; }
295#endif
296 bool isSharedWith(const QHash &other) const { return d == other.d; }
297
298 void clear();
299
300 int remove(const Key &key);
301 T take(const Key &key);
302
303 bool contains(const Key &key) const;
304 const Key key(const T &value) const;
305 const Key key(const T &value, const Key &defaultKey) const;
306 const T value(const Key &key) const;
307 const T value(const Key &key, const T &defaultValue) const;
308 T &operator[](const Key &key);
309 const T operator[](const Key &key) const;
310
311 QList<Key> keys() const;
312 QList<Key> keys(const T &value) const;
313 QList<T> values() const;
314#if QT_DEPRECATED_SINCE(5, 15)
315 QT_DEPRECATED_VERSION_X_5_15("Use QMultiHash for hashes storing multiple values with the same key.") QList<Key> uniqueKeys() const;
316 QT_DEPRECATED_VERSION_X_5_15("Use QMultiHash for hashes storing multiple values with the same key.") QList<T> values(const Key &key) const;
317#endif
318 int count(const Key &key) const;
319
320 class const_iterator;
321
322 class iterator
323 {
324 friend class const_iterator;
325 friend class QHash<Key, T>;
326 friend class QSet<Key>;
327 QHashData::Node *i;
328
329 public:
330#if QT_DEPRECATED_WARNINGS_SINCE < QT_VERSION_CHECK(5, 15, 0)
331 typedef std::bidirectional_iterator_tag iterator_category;
332#else
333 typedef std::forward_iterator_tag iterator_category;
334#endif
335 typedef qptrdiff difference_type;
336 typedef T value_type;
337 typedef T *pointer;
338 typedef T &reference;
339
340 inline iterator() : i(nullptr) { }
341 explicit inline iterator(void *node) : i(reinterpret_cast<QHashData::Node *>(node)) { }
342
343 inline const Key &key() const { return concrete(i)->key; }
344 inline T &value() const { return concrete(i)->value; }
345 inline T &operator*() const { return concrete(i)->value; }
346 inline T *operator->() const { return &concrete(i)->value; }
347 inline bool operator==(const iterator &o) const { return i == o.i; }
348 inline bool operator!=(const iterator &o) const { return i != o.i; }
349
350 inline iterator &operator++() {
351 i = QHashData::nextNode(i);
352 return *this;
353 }
354 inline iterator operator++(int) {
355 iterator r = *this;
356 i = QHashData::nextNode(i);
357 return r;
358 }
359#if QT_DEPRECATED_SINCE(5, 15)
360 inline QT_DEPRECATED_VERSION_5_15 iterator &operator--()
361 {
362 i = QHashData::previousNode(i);
363 return *this;
364 }
365 inline QT_DEPRECATED_VERSION_5_15 iterator operator--(int)
366 {
367 iterator r = *this;
368 i = QHashData::previousNode(i);
369 return r;
370 }
371 inline QT_DEPRECATED_VERSION_5_15 iterator operator+(int j) const
372 { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
373 inline QT_DEPRECATED_VERSION_5_15 iterator operator-(int j) const { return operator+(-j); }
374 inline QT_DEPRECATED_VERSION_5_15 iterator &operator+=(int j) { return *this = *this + j; }
375 inline QT_DEPRECATED_VERSION_5_15 iterator &operator-=(int j) { return *this = *this - j; }
376 friend inline QT_DEPRECATED_VERSION_5_15 iterator operator+(int j, iterator k) { return k + j; }
377#endif
378
379#ifndef QT_STRICT_ITERATORS
380 public:
381 inline bool operator==(const const_iterator &o) const
382 { return i == o.i; }
383 inline bool operator!=(const const_iterator &o) const
384 { return i != o.i; }
385#endif
386 };
387 friend class iterator;
388
389 class const_iterator
390 {
391 friend class iterator;
392 friend class QHash<Key, T>;
393 friend class QMultiHash<Key, T>;
394 friend class QSet<Key>;
395 QHashData::Node *i;
396
397 public:
398#if QT_DEPRECATED_WARNINGS_SINCE < QT_VERSION_CHECK(5, 15, 0)
399 typedef std::bidirectional_iterator_tag iterator_category;
400#else
401 typedef std::forward_iterator_tag iterator_category;
402#endif
403 typedef qptrdiff difference_type;
404 typedef T value_type;
405 typedef const T *pointer;
406 typedef const T &reference;
407
408 Q_DECL_CONSTEXPR inline const_iterator() : i(nullptr) { }
409 explicit inline const_iterator(void *node)
410 : i(reinterpret_cast<QHashData::Node *>(node)) { }
411#ifdef QT_STRICT_ITERATORS
412 explicit inline const_iterator(const iterator &o)
413#else
414 inline const_iterator(const iterator &o)
415#endif
416 { i = o.i; }
417
418 inline const Key &key() const { return concrete(i)->key; }
419 inline const T &value() const { return concrete(i)->value; }
420 inline const T &operator*() const { return concrete(i)->value; }
421 inline const T *operator->() const { return &concrete(i)->value; }
422 Q_DECL_CONSTEXPR inline bool operator==(const const_iterator &o) const { return i == o.i; }
423 Q_DECL_CONSTEXPR inline bool operator!=(const const_iterator &o) const { return i != o.i; }
424
425 inline const_iterator &operator++() {
426 i = QHashData::nextNode(i);
427 return *this;
428 }
429 inline const_iterator operator++(int) {
430 const_iterator r = *this;
431 i = QHashData::nextNode(i);
432 return r;
433 }
434#if QT_DEPRECATED_SINCE(5, 15)
435 inline QT_DEPRECATED_VERSION_5_15 const_iterator &operator--()
436 {
437 i = QHashData::previousNode(i);
438 return *this;
439 }
440 inline QT_DEPRECATED_VERSION_5_15 const_iterator operator--(int)
441 {
442 const_iterator r = *this;
443 i = QHashData::previousNode(i);
444 return r;
445 }
446 inline QT_DEPRECATED_VERSION_5_15 const_iterator operator+(int j) const
447 { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
448 inline QT_DEPRECATED_VERSION_5_15 const_iterator operator-(int j) const { return operator+(-j); }
449 inline QT_DEPRECATED_VERSION_5_15 const_iterator &operator+=(int j) { return *this = *this + j; }
450 inline QT_DEPRECATED_VERSION_5_15 const_iterator &operator-=(int j) { return *this = *this - j; }
451 friend inline QT_DEPRECATED_VERSION_5_15 const_iterator operator+(int j, const_iterator k)
452 {
453 return k + j;
454 }
455#endif
456
457 // ### Qt 5: not sure this is necessary anymore
458#ifdef QT_STRICT_ITERATORS
459 private:
460 inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); }
461 inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); }
462#endif
463 };
464 friend class const_iterator;
465
466 class key_iterator
467 {
468 const_iterator i;
469
470 public:
471 typedef typename const_iterator::iterator_category iterator_category;
472 typedef typename const_iterator::difference_type difference_type;
473 typedef Key value_type;
474 typedef const Key *pointer;
475 typedef const Key &reference;
476
477 key_iterator() = default;
478 explicit key_iterator(const_iterator o) : i(o) { }
479
480 const Key &operator*() const { return i.key(); }
481 const Key *operator->() const { return &i.key(); }
482 bool operator==(key_iterator o) const { return i == o.i; }
483 bool operator!=(key_iterator o) const { return i != o.i; }
484
485 inline key_iterator &operator++() { ++i; return *this; }
486 inline key_iterator operator++(int) { return key_iterator(i++);}
487#if QT_DEPRECATED_SINCE(5, 15)
488 inline QT_DEPRECATED_VERSION_5_15 key_iterator &operator--()
489 {
490 --i;
491 return *this;
492 }
493 inline QT_DEPRECATED_VERSION_5_15 key_iterator operator--(int) { return key_iterator(i--); }
494#endif
495 const_iterator base() const { return i; }
496 };
497
498 typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator;
499 typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
500
501 // STL style
502 inline iterator begin() { detach(); return iterator(d->firstNode()); }
503 inline const_iterator begin() const { return const_iterator(d->firstNode()); }
504 inline const_iterator cbegin() const { return const_iterator(d->firstNode()); }
505 inline const_iterator constBegin() const { return const_iterator(d->firstNode()); }
506 inline iterator end() { detach(); return iterator(e); }
507 inline const_iterator end() const { return const_iterator(e); }
508 inline const_iterator cend() const { return const_iterator(e); }
509 inline const_iterator constEnd() const { return const_iterator(e); }
510 inline key_iterator keyBegin() const { return key_iterator(begin()); }
511 inline key_iterator keyEnd() const { return key_iterator(end()); }
512 inline key_value_iterator keyValueBegin() { return key_value_iterator(begin()); }
513 inline key_value_iterator keyValueEnd() { return key_value_iterator(end()); }
514 inline const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); }
515 inline const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); }
516 inline const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); }
517 inline const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); }
518
519 QPair<iterator, iterator> equal_range(const Key &key);
520 QPair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept;
521 iterator erase(iterator it) { return erase(const_iterator(it.i)); }
522 iterator erase(const_iterator it);
523
524 // more Qt
525 typedef iterator Iterator;
526 typedef const_iterator ConstIterator;
527 inline int count() const { return d->size; }
528 iterator find(const Key &key);
529 const_iterator find(const Key &key) const;
530 const_iterator constFind(const Key &key) const;
531 iterator insert(const Key &key, const T &value);
532 void insert(const QHash &hash);
533#if QT_DEPRECATED_SINCE(5, 15)
534 QT_DEPRECATED_VERSION_X_5_15("Use QMultiHash for hashes storing multiple values with the same key.") iterator insertMulti(const Key &key, const T &value);
535 QT_DEPRECATED_VERSION_X_5_15("Use QMultiHash for hashes storing multiple values with the same key.") QHash &unite(const QHash &other);
536#endif
537
538 // STL compatibility
539 typedef T mapped_type;
540 typedef Key key_type;
541 typedef qptrdiff difference_type;
542 typedef int size_type;
543
544 inline bool empty() const { return isEmpty(); }
545
546#ifdef QT_QHASH_DEBUG
547 inline void dump() const { d->dump(); }
548 inline void checkSanity() const { d->checkSanity(); }
549#endif
550
551private:
552 void detach_helper();
553 void freeData(QHashData *d);
554 Node **findNode(const Key &key, uint *hp = nullptr) const;
555 Node **findNode(const Key &key, uint h) const;
556 Node *createNode(uint h, const Key &key, const T &value, Node **nextNode);
557 void deleteNode(Node *node);
558 static void deleteNode2(QHashData::Node *node);
559
560 static void duplicateNode(QHashData::Node *originalNode, void *newNode);
561
562 bool isValidIterator(const iterator &it) const noexcept
563 { return isValidNode(it.i); }
564 bool isValidIterator(const const_iterator &it) const noexcept
565 { return isValidNode(it.i); }
566 bool isValidNode(QHashData::Node *node) const noexcept
567 {
568#if defined(QT_DEBUG) && !defined(Q_HASH_NO_ITERATOR_DEBUG)
569 while (node->next)
570 node = node->next;
571 return (static_cast<void *>(node) == d);
572#else
573 Q_UNUSED(node);
574 return true;
575#endif
576 }
577 friend class QSet<Key>;
578 friend class QMultiHash<Key, T>;
579};
580
581
582template <class Key, class T>
583Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(Node *node)
584{
585 deleteNode2(reinterpret_cast<QHashData::Node*>(node));
586 d->freeNode(node);
587}
588
589template <class Key, class T>
590Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode2(QHashData::Node *node)
591{
592#ifdef Q_CC_BOR
593 concrete(node)->~QHashNode<Key, T>();
594#else
595 concrete(node)->~Node();
596#endif
597}
598
599template <class Key, class T>
600Q_INLINE_TEMPLATE void QHash<Key, T>::duplicateNode(QHashData::Node *node, void *newNode)
601{
602 Node *concreteNode = concrete(node);
603 new (newNode) Node(concreteNode->key, concreteNode->value, concreteNode->h, nullptr);
604}
605
606template <class Key, class T>
607Q_INLINE_TEMPLATE typename QHash<Key, T>::Node *
608QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anextNode)
609{
610 Node *node = new (d->allocateNode(alignOfNode())) Node(akey, avalue, ah, *anextNode);
611 *anextNode = node;
612 ++d->size;
613 return node;
614}
615
616template <class Key, class T>
617Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x)
618{
619 x->free_helper(deleteNode2);
620}
621
622template <class Key, class T>
623Q_INLINE_TEMPLATE void QHash<Key, T>::clear()
624{
625 *this = QHash();
626}
627
628template <class Key, class T>
629Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::detach_helper()
630{
631 QHashData *x = d->detach_helper(duplicateNode, deleteNode2, sizeof(Node), alignOfNode());
632 if (!d->ref.deref())
633 freeData(d);
634 d = x;
635}
636
637template <class Key, class T>
638Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::operator=(const QHash &other)
639{
640 if (d != other.d) {
641 QHashData *o = other.d;
642 o->ref.ref();
643 if (!d->ref.deref())
644 freeData(d);
645 d = o;
646 if (!d->sharable)
647 detach_helper();
648 }
649 return *this;
650}
651
652template <class Key, class T>
653Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey) const
654{
655 Node *node;
656 if (d->size == 0 || (node = *findNode(akey)) == e) {
657 return T();
658 } else {
659 return node->value;
660 }
661}
662
663template <class Key, class T>
664Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey, const T &adefaultValue) const
665{
666 Node *node;
667 if (d->size == 0 || (node = *findNode(akey)) == e) {
668 return adefaultValue;
669 } else {
670 return node->value;
671 }
672}
673
674template <class Key, class T>
675Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys() const
676{
677 QList<Key> res;
678 res.reserve(size());
679 const_iterator i = begin();
680 while (i != end()) {
681 res.append(i.key());
682 ++i;
683 }
684 return res;
685}
686
687template <class Key, class T>
688Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys(const T &avalue) const
689{
690 QList<Key> res;
691 const_iterator i = begin();
692 while (i != end()) {
693 if (i.value() == avalue)
694 res.append(i.key());
695 ++i;
696 }
697 return res;
698}
699
700template <class Key, class T>
701Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue) const
702{
703 return key(avalue, Key());
704}
705
706template <class Key, class T>
707Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue, const Key &defaultValue) const
708{
709 const_iterator i = begin();
710 while (i != end()) {
711 if (i.value() == avalue)
712 return i.key();
713 ++i;
714 }
715
716 return defaultValue;
717}
718
719template <class Key, class T>
720Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values() const
721{
722 QList<T> res;
723 res.reserve(size());
724 const_iterator i = begin();
725 while (i != end()) {
726 res.append(i.value());
727 ++i;
728 }
729 return res;
730}
731
732template <class Key, class T>
733Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::count(const Key &akey) const
734{
735 int cnt = 0;
736 Node *node = *findNode(akey);
737 if (node != e) {
738 do {
739 ++cnt;
740 } while ((node = node->next) != e && node->key == akey);
741 }
742 return cnt;
743}
744
745template <class Key, class T>
746Q_INLINE_TEMPLATE const T QHash<Key, T>::operator[](const Key &akey) const
747{
748 return value(akey);
749}
750
751template <class Key, class T>
752Q_INLINE_TEMPLATE T &QHash<Key, T>::operator[](const Key &akey)
753{
754 detach();
755
756 uint h;
757 Node **node = findNode(akey, &h);
758 if (*node == e) {
759 if (d->willGrow())
760 node = findNode(akey, h);
761 return createNode(h, akey, T(), node)->value;
762 }
763 return (*node)->value;
764}
765
766template <class Key, class T>
767Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &akey,
768 const T &avalue)
769{
770 detach();
771
772 uint h;
773 Node **node = findNode(akey, &h);
774 if (*node == e) {
775 if (d->willGrow())
776 node = findNode(akey, h);
777 return iterator(createNode(h, akey, avalue, node));
778 }
779
780 if (!std::is_same<T, QHashDummyValue>::value)
781 (*node)->value = avalue;
782 return iterator(*node);
783}
784
785template <class Key, class T>
786Q_INLINE_TEMPLATE void QHash<Key, T>::insert(const QHash &hash)
787{
788 if (d == hash.d)
789 return;
790
791 detach();
792
793 QHashData::Node *i = hash.d->firstNode();
794 QHashData::Node *end = reinterpret_cast<QHashData::Node *>(hash.e);
795 while (i != end) {
796 Node *n = concrete(i);
797 Node **node = findNode(n->key, n->h);
798 if (*node == e) {
799 if (d->willGrow())
800 node = findNode(n->key, n->h);
801 createNode(n->h, n->key, n->value, node);
802 } else {
803 if (!std::is_same<T, QHashDummyValue>::value)
804 (*node)->value = n->value;
805 }
806 i = QHashData::nextNode(i);
807 }
808}
809
810template <class Key, class T>
811Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::remove(const Key &akey)
812{
813 if (isEmpty()) // prevents detaching shared null
814 return 0;
815 detach();
816
817 int oldSize = d->size;
818 Node **node = findNode(akey);
819 if (*node != e) {
820 bool deleteNext = true;
821 do {
822 Node *next = (*node)->next;
823 deleteNext = (next != e && next->key == (*node)->key);
824 deleteNode(*node);
825 *node = next;
826 --d->size;
827 } while (deleteNext);
828 d->hasShrunk();
829 }
830 return oldSize - d->size;
831}
832
833template <class Key, class T>
834Q_OUTOFLINE_TEMPLATE T QHash<Key, T>::take(const Key &akey)
835{
836 if (isEmpty()) // prevents detaching shared null
837 return T();
838 detach();
839
840 Node **node = findNode(akey);
841 if (*node != e) {
842 T t = std::move((*node)->value);
843 Node *next = (*node)->next;
844 deleteNode(*node);
845 *node = next;
846 --d->size;
847 d->hasShrunk();
848 return t;
849 }
850 return T();
851}
852
853template <class Key, class T>
854Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::erase(const_iterator it)
855{
856 Q_ASSERT_X(isValidIterator(it), "QHash::erase", "The specified iterator argument 'it' is invalid");
857
858 if (it == const_iterator(e))
859 return iterator(it.i);
860
861 if (d->ref.isShared()) {
862 // save 'it' across the detach:
863 int bucketNum = (it.i->h % d->numBuckets);
864 const_iterator bucketIterator(*(d->buckets + bucketNum));
865 int stepsFromBucketStartToIte = 0;
866 while (bucketIterator != it) {
867 ++stepsFromBucketStartToIte;
868 ++bucketIterator;
869 }
870 detach();
871 it = const_iterator(*(d->buckets + bucketNum));
872 while (stepsFromBucketStartToIte > 0) {
873 --stepsFromBucketStartToIte;
874 ++it;
875 }
876 }
877
878 iterator ret(it.i);
879 ++ret;
880
881 Node *node = concrete(it.i);
882 Node **node_ptr = reinterpret_cast<Node **>(&d->buckets[node->h % d->numBuckets]);
883 while (*node_ptr != node)
884 node_ptr = &(*node_ptr)->next;
885 *node_ptr = node->next;
886 deleteNode(node);
887 --d->size;
888 return ret;
889}
890
891template <class Key, class T>
892Q_INLINE_TEMPLATE void QHash<Key, T>::reserve(int asize)
893{
894 detach();
895 d->rehash(-qMax(asize, 1));
896}
897
898template <class Key, class T>
899Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &akey) const
900{
901 return const_iterator(*findNode(akey));
902}
903
904template <class Key, class T>
905Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &akey) const
906{
907 return const_iterator(*findNode(akey));
908}
909
910template <class Key, class T>
911Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::find(const Key &akey)
912{
913 detach();
914 return iterator(*findNode(akey));
915}
916
917template <class Key, class T>
918Q_INLINE_TEMPLATE bool QHash<Key, T>::contains(const Key &akey) const
919{
920 return *findNode(akey) != e;
921}
922
923template <class Key, class T>
924Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey, uint h) const
925{
926 Node **node;
927
928 if (d->numBuckets) {
929 node = reinterpret_cast<Node **>(&d->buckets[h % d->numBuckets]);
930 Q_ASSERT(*node == e || (*node)->next);
931 while (*node != e && !(*node)->same_key(h, akey))
932 node = &(*node)->next;
933 } else {
934 node = const_cast<Node **>(reinterpret_cast<const Node * const *>(&e));
935 }
936 return node;
937}
938
939template <class Key, class T>
940Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey,
941 uint *ahp) const
942{
943 uint h = 0;
944
945 if (d->numBuckets || ahp) {
946 h = qHash(akey, d->seed);
947 if (ahp)
948 *ahp = h;
949 }
950 return findNode(akey, h);
951}
952
953template <class Key, class T>
954Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash &other) const
955{
956 if (d == other.d)
957 return true;
958 if (size() != other.size())
959 return false;
960
961 const_iterator it = begin();
962
963 while (it != end()) {
964 // Build two equal ranges for i.key(); one for *this and one for other.
965 // For *this we can avoid a lookup via equal_range, as we know the beginning of the range.
966 auto thisEqualRangeStart = it;
967 const Key &thisEqualRangeKey = it.key();
968 size_type n = 0;
969 do {
970 ++it;
971 ++n;
972 } while (it != end() && it.key() == thisEqualRangeKey);
973
974 const auto otherEqualRange = other.equal_range(thisEqualRangeKey);
975
976 if (n != std::distance(otherEqualRange.first, otherEqualRange.second))
977 return false;
978
979 // Keys in the ranges are equal by construction; this checks only the values.
980 if (!qt_is_permutation(thisEqualRangeStart, it, otherEqualRange.first, otherEqualRange.second))
981 return false;
982 }
983
984 return true;
985}
986
987template <class Key, class T>
988QPair<typename QHash<Key, T>::iterator, typename QHash<Key, T>::iterator> QHash<Key, T>::equal_range(const Key &akey)
989{
990 detach();
991 auto pair = qAsConst(*this).equal_range(akey);
992 return qMakePair(iterator(pair.first.i), iterator(pair.second.i));
993}
994
995template <class Key, class T>
996QPair<typename QHash<Key, T>::const_iterator, typename QHash<Key, T>::const_iterator> QHash<Key, T>::equal_range(const Key &akey) const noexcept
997{
998 Node *node = *findNode(akey);
999 const_iterator firstIt = const_iterator(node);
1000
1001 if (node != e) {
1002 // equal keys must hash to the same value and so they all
1003 // end up in the same bucket. So we can use node->next,
1004 // which only works within a bucket, instead of (out-of-line)
1005 // QHashData::nextNode()
1006 while (node->next != e && node->next->key == akey)
1007 node = node->next;
1008
1009 // 'node' may be the last node in the bucket. To produce the end iterator, we'd
1010 // need to enter the next bucket in this case, so we need to use
1011 // QHashData::nextNode() here, which, unlike node->next above, can move between
1012 // buckets.
1013 node = concrete(QHashData::nextNode(reinterpret_cast<QHashData::Node *>(node)));
1014 }
1015
1016 return qMakePair(firstIt, const_iterator(node));
1017}
1018
1019template <class Key, class T>
1020class QMultiHash : public QHash<Key, T>
1021{
1022public:
1023 QMultiHash() noexcept {}
1024 inline QMultiHash(std::initializer_list<std::pair<Key,T> > list)
1025 {
1026 this->reserve(int(list.size()));
1027 for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
1028 insert(it->first, it->second);
1029 }
1030#ifdef Q_QDOC
1031 template <typename InputIterator>
1032 QMultiHash(InputIterator f, InputIterator l);
1033#else
1034 template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasKeyAndValue<InputIterator> = true>
1035 QMultiHash(InputIterator f, InputIterator l)
1036 {
1037 QtPrivate::reserveIfForwardIterator(this, f, l);
1038 for (; f != l; ++f)
1039 insert(f.key(), f.value());
1040 }
1041
1042 template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true>
1043 QMultiHash(InputIterator f, InputIterator l)
1044 {
1045 QtPrivate::reserveIfForwardIterator(this, f, l);
1046 for (; f != l; ++f)
1047 insert(f->first, f->second);
1048 }
1049#endif
1050 // compiler-generated copy/move ctors/assignment operators are fine!
1051 // compiler-generated destructor is fine!
1052
1053 QMultiHash(const QHash<Key, T> &other) : QHash<Key, T>(other) {}
1054 QMultiHash(QHash<Key, T> &&other) noexcept : QHash<Key, T>(std::move(other)) {}
1055 void swap(QMultiHash &other) noexcept { QHash<Key, T>::swap(other); } // prevent QMultiHash<->QHash swaps
1056
1057 inline typename QHash<Key, T>::iterator replace(const Key &key, const T &value)
1058 { return QHash<Key, T>::insert(key, value); }
1059
1060 typename QHash<Key, T>::iterator insert(const Key &key, const T &value);
1061
1062 inline QMultiHash &unite(const QMultiHash &other);
1063
1064 inline QMultiHash &operator+=(const QMultiHash &other)
1065 { return unite(other); }
1066 inline QMultiHash operator+(const QMultiHash &other) const
1067 { QMultiHash result = *this; result += other; return result; }
1068
1069 using QHash<Key, T>::contains;
1070 using QHash<Key, T>::remove;
1071 using QHash<Key, T>::count;
1072 using QHash<Key, T>::find;
1073 using QHash<Key, T>::constFind;
1074 using QHash<Key, T>::values;
1075 using QHash<Key, T>::findNode;
1076 using QHash<Key, T>::createNode;
1077 using QHash<Key, T>::concrete;
1078 using QHash<Key, T>::detach;
1079
1080 using typename QHash<Key, T>::Node;
1081 using typename QHash<Key, T>::iterator;
1082 using typename QHash<Key, T>::const_iterator;
1083
1084 bool contains(const Key &key, const T &value) const;
1085
1086 int remove(const Key &key, const T &value);
1087
1088 int count(const Key &key, const T &value) const;
1089
1090 QList<Key> uniqueKeys() const;
1091
1092 QList<T> values(const Key &akey) const;
1093
1094 typename QHash<Key, T>::iterator find(const Key &key, const T &value) {
1095 typename QHash<Key, T>::iterator i(find(key));
1096 typename QHash<Key, T>::iterator end(this->end());
1097 while (i != end && i.key() == key) {
1098 if (i.value() == value)
1099 return i;
1100 ++i;
1101 }
1102 return end;
1103 }
1104 typename QHash<Key, T>::const_iterator find(const Key &key, const T &value) const {
1105 typename QHash<Key, T>::const_iterator i(constFind(key));
1106 typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
1107 while (i != end && i.key() == key) {
1108 if (i.value() == value)
1109 return i;
1110 ++i;
1111 }
1112 return end;
1113 }
1114 typename QHash<Key, T>::const_iterator constFind(const Key &key, const T &value) const
1115 { return find(key, value); }
1116private:
1117 T &operator[](const Key &key);
1118 const T operator[](const Key &key) const;
1119};
1120
1121template <class Key, class T>
1122Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QMultiHash<Key, T>::insert(const Key &akey, const T &avalue)
1123{
1124 detach();
1125 this->d->willGrow();
1126
1127 uint h;
1128 Node **nextNode = findNode(akey, &h);
1129 return iterator(createNode(h, akey, avalue, nextNode));
1130}
1131
1132template <class Key, class T>
1133Q_INLINE_TEMPLATE QMultiHash<Key, T> &QMultiHash<Key, T>::unite(const QMultiHash &other)
1134{
1135 if (this->d == &QHashData::shared_null) {
1136 *this = other;
1137 } else {
1138#if QT_DEPRECATED_SINCE(5, 15)
1139 QMultiHash copy(other);
1140 const_iterator it = copy.constEnd();
1141 while (it != copy.constBegin()) {
1142 it.i = QHashData::previousNode(it.i);
1143 insert(it.key(), it.value());
1144 }
1145#else
1146 const QMultiHash copy(other);
1147 const_iterator it = copy.cbegin();
1148 const const_iterator end = copy.cend();
1149 while (it != end) {
1150 const auto rangeStart = it++;
1151 while (it != end && rangeStart.key() == it.key())
1152 ++it;
1153 const qint64 last = std::distance(rangeStart, it) - 1;
1154 for (qint64 i = last; i >= 0; --i) {
1155 auto next = std::next(rangeStart, i);
1156 insert(next.key(), next.value());
1157 }
1158 }
1159#endif
1160 }
1161 return *this;
1162}
1163
1164
1165template <class Key, class T>
1166Q_INLINE_TEMPLATE bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const
1167{
1168 return constFind(key, value) != QHash<Key, T>::constEnd();
1169}
1170
1171template <class Key, class T>
1172Q_INLINE_TEMPLATE int QMultiHash<Key, T>::remove(const Key &key, const T &value)
1173{
1174 int n = 0;
1175 typename QHash<Key, T>::iterator i(find(key));
1176 typename QHash<Key, T>::iterator end(QHash<Key, T>::end());
1177 while (i != end && i.key() == key) {
1178 if (i.value() == value) {
1179 i = this->erase(i);
1180 ++n;
1181 } else {
1182 ++i;
1183 }
1184 }
1185 return n;
1186}
1187
1188template <class Key, class T>
1189Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value) const
1190{
1191 int n = 0;
1192 typename QHash<Key, T>::const_iterator i(constFind(key));
1193 typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
1194 while (i != end && i.key() == key) {
1195 if (i.value() == value)
1196 ++n;
1197 ++i;
1198 }
1199 return n;
1200}
1201
1202template <class Key, class T>
1203Q_OUTOFLINE_TEMPLATE QList<Key> QMultiHash<Key, T>::uniqueKeys() const
1204{
1205 QList<Key> res;
1206 res.reserve(QHash<Key, T>::size()); // May be too much, but assume short lifetime
1207 typename QHash<Key, T>::const_iterator i = QHash<Key, T>::begin();
1208 if (i != QHash<Key, T>::end()) {
1209 for (;;) {
1210 const Key &aKey = i.key();
1211 res.append(aKey);
1212 do {
1213 if (++i == QHash<Key, T>::end())
1214 goto break_out_of_outer_loop;
1215 } while (aKey == i.key());
1216 }
1217 }
1218break_out_of_outer_loop:
1219 return res;
1220}
1221
1222#if QT_DEPRECATED_SINCE(5, 15)
1223
1224template <class Key, class T>
1225Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &key, const T &value) {
1226 return static_cast<QMultiHash<Key, T> *>(this)->insert(key, value);
1227}
1228
1229template <class Key, class T>
1230Q_OUTOFLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash &other) {
1231 return static_cast<QMultiHash<Key, T> *>(this)->unite(other);
1232}
1233
1234template <class Key, class T>
1235Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const
1236{
1237 return static_cast<const QMultiHash<Key, T> *>(this)->values(akey);
1238}
1239
1240template <class Key, class T>
1241Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const
1242{
1243 return static_cast<const QMultiHash<Key, T> *>(this)->uniqueKeys();
1244}
1245#endif
1246
1247template <class Key, class T>
1248Q_OUTOFLINE_TEMPLATE QList<T> QMultiHash<Key, T>::values(const Key &akey) const
1249{
1250 QList<T> res;
1251 Node *node = *findNode(akey);
1252 if (node != this->e) {
1253 do {
1254 res.append(node->value);
1255 } while ((node = node->next) != this->e && node->key == akey);
1256 }
1257 return res;
1258}
1259
1260#if !defined(QT_NO_JAVA_STYLE_ITERATORS)
1261template <class Key, class T>
1262class QHashIterator
1263{
1264 typedef typename QHash<Key, T>::const_iterator const_iterator;
1265 typedef const_iterator Item;
1266 QHash<Key, T> c;
1267 const_iterator i, n;
1268 inline bool item_exists() const { return n != c.constEnd(); }
1269
1270public:
1271 inline QHashIterator(const QHash<Key, T> &container)
1272 : c(container), i(c.constBegin()), n(c.constEnd())
1273 {
1274 }
1275 inline QHashIterator &operator=(const QHash<Key, T> &container)
1276 {
1277 c = container;
1278 i = c.constBegin();
1279 n = c.constEnd();
1280 return *this;
1281 }
1282 inline void toFront()
1283 {
1284 i = c.constBegin();
1285 n = c.constEnd();
1286 }
1287 inline void toBack()
1288 {
1289 i = c.constEnd();
1290 n = c.constEnd();
1291 }
1292 inline bool hasNext() const { return i != c.constEnd(); }
1293 inline Item next()
1294 {
1295 n = i++;
1296 return n;
1297 }
1298 inline Item peekNext() const { return i; }
1299 inline const T &value() const
1300 {
1301 Q_ASSERT(item_exists());
1302 return *n;
1303 }
1304 inline const Key &key() const
1305 {
1306 Q_ASSERT(item_exists());
1307 return n.key();
1308 }
1309 inline bool findNext(const T &t)
1310 {
1311 while ((n = i) != c.constEnd())
1312 if (*i++ == t)
1313 return true;
1314 return false;
1315 }
1316#if QT_DEPRECATED_SINCE(5, 15)
1317 inline QT_DEPRECATED_VERSION_5_15 bool hasPrevious() const { return i != c.constBegin(); }
1318 inline QT_DEPRECATED_VERSION_5_15 Item previous()
1319 {
1320 n = --i;
1321 return n;
1322 }
1323 inline QT_DEPRECATED_VERSION_5_15 Item peekPrevious() const
1324 {
1325 const_iterator p = i;
1326 return --p;
1327 }
1328 inline bool QT_DEPRECATED_VERSION_5_15 findPrevious(const T &t)
1329 {
1330 while (i != c.constBegin())
1331 if (*(n = --i) == t)
1332 return true;
1333 n = c.constEnd();
1334 return false;
1335 }
1336#endif
1337};
1338
1339template<class Key, class T>
1340class QMutableHashIterator
1341{
1342 typedef typename QHash<Key, T>::iterator iterator;
1343 typedef typename QHash<Key, T>::const_iterator const_iterator;
1344 typedef iterator Item;
1345 QHash<Key, T> *c;
1346 iterator i, n;
1347 inline bool item_exists() const { return const_iterator(n) != c->constEnd(); }
1348
1349public:
1350 inline QMutableHashIterator(QHash<Key, T> &container) : c(&container)
1351 {
1352 i = c->begin();
1353 n = c->end();
1354 }
1355 inline QMutableHashIterator &operator=(QHash<Key, T> &container)
1356 {
1357 c = &container;
1358 i = c->begin();
1359 n = c->end();
1360 return *this;
1361 }
1362 inline void toFront()
1363 {
1364 i = c->begin();
1365 n = c->end();
1366 }
1367 inline void toBack()
1368 {
1369 i = c->end();
1370 n = c->end();
1371 }
1372 inline bool hasNext() const { return const_iterator(i) != c->constEnd(); }
1373 inline Item next()
1374 {
1375 n = i++;
1376 return n;
1377 }
1378 inline Item peekNext() const { return i; }
1379 inline void remove()
1380 {
1381 if (const_iterator(n) != c->constEnd()) {
1382 i = c->erase(n);
1383 n = c->end();
1384 }
1385 }
1386 inline void setValue(const T &t)
1387 {
1388 if (const_iterator(n) != c->constEnd())
1389 *n = t;
1390 }
1391 inline T &value()
1392 {
1393 Q_ASSERT(item_exists());
1394 return *n;
1395 }
1396 inline const T &value() const
1397 {
1398 Q_ASSERT(item_exists());
1399 return *n;
1400 }
1401 inline const Key &key() const
1402 {
1403 Q_ASSERT(item_exists());
1404 return n.key();
1405 }
1406 inline bool findNext(const T &t)
1407 {
1408 while (const_iterator(n = i) != c->constEnd())
1409 if (*i++ == t)
1410 return true;
1411 return false;
1412 }
1413#if QT_DEPRECATED_SINCE(5, 15)
1414 inline QT_DEPRECATED_VERSION_5_15 bool hasPrevious() const { return const_iterator(i) != c->constBegin(); }
1415 inline QT_DEPRECATED_VERSION_5_15 Item previous()
1416 {
1417 n = --i;
1418 return n;
1419 }
1420 inline QT_DEPRECATED_VERSION_5_15 Item peekPrevious() const
1421 {
1422 iterator p = i;
1423 return --p;
1424 }
1425 inline QT_DEPRECATED_VERSION_5_15 bool findPrevious(const T &t)
1426 {
1427 while (const_iterator(i) != c->constBegin())
1428 if (*(n = --i) == t)
1429 return true;
1430 n = c->end();
1431 return false;
1432 }
1433#endif
1434};
1435#endif // !QT_NO_JAVA_STYLE_ITERATORS
1436
1437template <class Key, class T>
1438uint qHash(const QHash<Key, T> &key, uint seed = 0)
1439 noexcept(noexcept(qHash(std::declval<Key&>())) && noexcept(qHash(std::declval<T&>())))
1440{
1441 QtPrivate::QHashCombineCommutative hash;
1442 for (auto it = key.begin(), end = key.end(); it != end; ++it) {
1443 const Key &k = it.key();
1444 const T &v = it.value();
1445 seed = hash(seed, std::pair<const Key&, const T&>(k, v));
1446 }
1447 return seed;
1448}
1449
1450template <class Key, class T>
1451inline uint qHash(const QMultiHash<Key, T> &key, uint seed = 0)
1452 noexcept(noexcept(qHash(std::declval<Key&>())) && noexcept(qHash(std::declval<T&>())))
1453{
1454 const QHash<Key, T> &key2 = key;
1455 return qHash(key2, seed);
1456}
1457
1458QT_END_NAMESPACE
1459
1460#if defined(Q_CC_MSVC)
1461#pragma warning( pop )
1462#endif
1463
1464#endif // QHASH_H
1465