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> uniqueKeys() const;
312 QList<Key> keys() const;
313 QList<Key> keys(const T &value) const;
314 QList<T> values() const;
315 QList<T> values(const Key &key) const;
316 int count(const Key &key) const;
317
318 class const_iterator;
319
320 class iterator
321 {
322 friend class const_iterator;
323 friend class QHash<Key, T>;
324 friend class QSet<Key>;
325 QHashData::Node *i;
326
327 public:
328 typedef std::bidirectional_iterator_tag iterator_category;
329 typedef qptrdiff difference_type;
330 typedef T value_type;
331 typedef T *pointer;
332 typedef T &reference;
333
334 inline iterator() : i(nullptr) { }
335 explicit inline iterator(void *node) : i(reinterpret_cast<QHashData::Node *>(node)) { }
336
337 inline const Key &key() const { return concrete(i)->key; }
338 inline T &value() const { return concrete(i)->value; }
339 inline T &operator*() const { return concrete(i)->value; }
340 inline T *operator->() const { return &concrete(i)->value; }
341 inline bool operator==(const iterator &o) const { return i == o.i; }
342 inline bool operator!=(const iterator &o) const { return i != o.i; }
343
344 inline iterator &operator++() {
345 i = QHashData::nextNode(i);
346 return *this;
347 }
348 inline iterator operator++(int) {
349 iterator r = *this;
350 i = QHashData::nextNode(i);
351 return r;
352 }
353 inline iterator &operator--() {
354 i = QHashData::previousNode(i);
355 return *this;
356 }
357 inline iterator operator--(int) {
358 iterator r = *this;
359 i = QHashData::previousNode(i);
360 return r;
361 }
362 inline iterator operator+(int j) const
363 { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
364 inline iterator operator-(int j) const { return operator+(-j); }
365 inline iterator &operator+=(int j) { return *this = *this + j; }
366 inline iterator &operator-=(int j) { return *this = *this - j; }
367 friend inline iterator operator+(int j, iterator k) { return k + j; }
368
369#ifndef QT_STRICT_ITERATORS
370 public:
371 inline bool operator==(const const_iterator &o) const
372 { return i == o.i; }
373 inline bool operator!=(const const_iterator &o) const
374 { return i != o.i; }
375#endif
376 };
377 friend class iterator;
378
379 class const_iterator
380 {
381 friend class iterator;
382 friend class QHash<Key, T>;
383 friend class QSet<Key>;
384 QHashData::Node *i;
385
386 public:
387 typedef std::bidirectional_iterator_tag iterator_category;
388 typedef qptrdiff difference_type;
389 typedef T value_type;
390 typedef const T *pointer;
391 typedef const T &reference;
392
393 Q_DECL_CONSTEXPR inline const_iterator() : i(nullptr) { }
394 explicit inline const_iterator(void *node)
395 : i(reinterpret_cast<QHashData::Node *>(node)) { }
396#ifdef QT_STRICT_ITERATORS
397 explicit inline const_iterator(const iterator &o)
398#else
399 inline const_iterator(const iterator &o)
400#endif
401 { i = o.i; }
402
403 inline const Key &key() const { return concrete(i)->key; }
404 inline const T &value() const { return concrete(i)->value; }
405 inline const T &operator*() const { return concrete(i)->value; }
406 inline const T *operator->() const { return &concrete(i)->value; }
407 Q_DECL_CONSTEXPR inline bool operator==(const const_iterator &o) const { return i == o.i; }
408 Q_DECL_CONSTEXPR inline bool operator!=(const const_iterator &o) const { return i != o.i; }
409
410 inline const_iterator &operator++() {
411 i = QHashData::nextNode(i);
412 return *this;
413 }
414 inline const_iterator operator++(int) {
415 const_iterator r = *this;
416 i = QHashData::nextNode(i);
417 return r;
418 }
419 inline const_iterator &operator--() {
420 i = QHashData::previousNode(i);
421 return *this;
422 }
423 inline const_iterator operator--(int) {
424 const_iterator r = *this;
425 i = QHashData::previousNode(i);
426 return r;
427 }
428 inline const_iterator operator+(int j) const
429 { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
430 inline const_iterator operator-(int j) const { return operator+(-j); }
431 inline const_iterator &operator+=(int j) { return *this = *this + j; }
432 inline const_iterator &operator-=(int j) { return *this = *this - j; }
433 friend inline const_iterator operator+(int j, const_iterator k) { return k + j; }
434
435 // ### Qt 5: not sure this is necessary anymore
436#ifdef QT_STRICT_ITERATORS
437 private:
438 inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); }
439 inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); }
440#endif
441 };
442 friend class const_iterator;
443
444 class key_iterator
445 {
446 const_iterator i;
447
448 public:
449 typedef typename const_iterator::iterator_category iterator_category;
450 typedef typename const_iterator::difference_type difference_type;
451 typedef Key value_type;
452 typedef const Key *pointer;
453 typedef const Key &reference;
454
455 key_iterator() = default;
456 explicit key_iterator(const_iterator o) : i(o) { }
457
458 const Key &operator*() const { return i.key(); }
459 const Key *operator->() const { return &i.key(); }
460 bool operator==(key_iterator o) const { return i == o.i; }
461 bool operator!=(key_iterator o) const { return i != o.i; }
462
463 inline key_iterator &operator++() { ++i; return *this; }
464 inline key_iterator operator++(int) { return key_iterator(i++);}
465 inline key_iterator &operator--() { --i; return *this; }
466 inline key_iterator operator--(int) { return key_iterator(i--); }
467 const_iterator base() const { return i; }
468 };
469
470 typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator;
471 typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
472
473 // STL style
474 inline iterator begin() { detach(); return iterator(d->firstNode()); }
475 inline const_iterator begin() const { return const_iterator(d->firstNode()); }
476 inline const_iterator cbegin() const { return const_iterator(d->firstNode()); }
477 inline const_iterator constBegin() const { return const_iterator(d->firstNode()); }
478 inline iterator end() { detach(); return iterator(e); }
479 inline const_iterator end() const { return const_iterator(e); }
480 inline const_iterator cend() const { return const_iterator(e); }
481 inline const_iterator constEnd() const { return const_iterator(e); }
482 inline key_iterator keyBegin() const { return key_iterator(begin()); }
483 inline key_iterator keyEnd() const { return key_iterator(end()); }
484 inline key_value_iterator keyValueBegin() { return key_value_iterator(begin()); }
485 inline key_value_iterator keyValueEnd() { return key_value_iterator(end()); }
486 inline const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); }
487 inline const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); }
488 inline const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); }
489 inline const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); }
490
491 QPair<iterator, iterator> equal_range(const Key &key);
492 QPair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept;
493 iterator erase(iterator it) { return erase(const_iterator(it.i)); }
494 iterator erase(const_iterator it);
495
496 // more Qt
497 typedef iterator Iterator;
498 typedef const_iterator ConstIterator;
499 inline int count() const { return d->size; }
500 iterator find(const Key &key);
501 const_iterator find(const Key &key) const;
502 const_iterator constFind(const Key &key) const;
503 iterator insert(const Key &key, const T &value);
504 iterator insertMulti(const Key &key, const T &value);
505 QHash &unite(const QHash &other);
506
507 // STL compatibility
508 typedef T mapped_type;
509 typedef Key key_type;
510 typedef qptrdiff difference_type;
511 typedef int size_type;
512
513 inline bool empty() const { return isEmpty(); }
514
515#ifdef QT_QHASH_DEBUG
516 inline void dump() const { d->dump(); }
517 inline void checkSanity() const { d->checkSanity(); }
518#endif
519
520private:
521 void detach_helper();
522 void freeData(QHashData *d);
523 Node **findNode(const Key &key, uint *hp = nullptr) const;
524 Node **findNode(const Key &key, uint h) const;
525 Node *createNode(uint h, const Key &key, const T &value, Node **nextNode);
526 void deleteNode(Node *node);
527 static void deleteNode2(QHashData::Node *node);
528
529 static void duplicateNode(QHashData::Node *originalNode, void *newNode);
530
531 bool isValidIterator(const iterator &it) const noexcept
532 { return isValidNode(it.i); }
533 bool isValidIterator(const const_iterator &it) const noexcept
534 { return isValidNode(it.i); }
535 bool isValidNode(QHashData::Node *node) const noexcept
536 {
537#if defined(QT_DEBUG) && !defined(Q_HASH_NO_ITERATOR_DEBUG)
538 while (node->next)
539 node = node->next;
540 return (static_cast<void *>(node) == d);
541#else
542 Q_UNUSED(node);
543 return true;
544#endif
545 }
546 friend class QSet<Key>;
547};
548
549
550template <class Key, class T>
551Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(Node *node)
552{
553 deleteNode2(reinterpret_cast<QHashData::Node*>(node));
554 d->freeNode(node);
555}
556
557template <class Key, class T>
558Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode2(QHashData::Node *node)
559{
560#ifdef Q_CC_BOR
561 concrete(node)->~QHashNode<Key, T>();
562#else
563 concrete(node)->~Node();
564#endif
565}
566
567template <class Key, class T>
568Q_INLINE_TEMPLATE void QHash<Key, T>::duplicateNode(QHashData::Node *node, void *newNode)
569{
570 Node *concreteNode = concrete(node);
571 new (newNode) Node(concreteNode->key, concreteNode->value, concreteNode->h, nullptr);
572}
573
574template <class Key, class T>
575Q_INLINE_TEMPLATE typename QHash<Key, T>::Node *
576QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anextNode)
577{
578 Node *node = new (d->allocateNode(alignOfNode())) Node(akey, avalue, ah, *anextNode);
579 *anextNode = node;
580 ++d->size;
581 return node;
582}
583
584template <class Key, class T>
585Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash &other)
586{
587 if (d == &QHashData::shared_null) {
588 *this = other;
589 } else {
590 QHash copy(other);
591 const_iterator it = copy.constEnd();
592 while (it != copy.constBegin()) {
593 --it;
594 insertMulti(it.key(), it.value());
595 }
596 }
597 return *this;
598}
599
600template <class Key, class T>
601Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x)
602{
603 x->free_helper(deleteNode2);
604}
605
606template <class Key, class T>
607Q_INLINE_TEMPLATE void QHash<Key, T>::clear()
608{
609 *this = QHash();
610}
611
612template <class Key, class T>
613Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::detach_helper()
614{
615 QHashData *x = d->detach_helper(duplicateNode, deleteNode2, sizeof(Node), alignOfNode());
616 if (!d->ref.deref())
617 freeData(d);
618 d = x;
619}
620
621template <class Key, class T>
622Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::operator=(const QHash &other)
623{
624 if (d != other.d) {
625 QHashData *o = other.d;
626 o->ref.ref();
627 if (!d->ref.deref())
628 freeData(d);
629 d = o;
630 if (!d->sharable)
631 detach_helper();
632 }
633 return *this;
634}
635
636template <class Key, class T>
637Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey) const
638{
639 Node *node;
640 if (d->size == 0 || (node = *findNode(akey)) == e) {
641 return T();
642 } else {
643 return node->value;
644 }
645}
646
647template <class Key, class T>
648Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey, const T &adefaultValue) const
649{
650 Node *node;
651 if (d->size == 0 || (node = *findNode(akey)) == e) {
652 return adefaultValue;
653 } else {
654 return node->value;
655 }
656}
657
658template <class Key, class T>
659Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const
660{
661 QList<Key> res;
662 res.reserve(size()); // May be too much, but assume short lifetime
663 const_iterator i = begin();
664 if (i != end()) {
665 for (;;) {
666 const Key &aKey = i.key();
667 res.append(aKey);
668 do {
669 if (++i == end())
670 goto break_out_of_outer_loop;
671 } while (aKey == i.key());
672 }
673 }
674break_out_of_outer_loop:
675 return res;
676}
677
678template <class Key, class T>
679Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys() const
680{
681 QList<Key> res;
682 res.reserve(size());
683 const_iterator i = begin();
684 while (i != end()) {
685 res.append(i.key());
686 ++i;
687 }
688 return res;
689}
690
691template <class Key, class T>
692Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys(const T &avalue) const
693{
694 QList<Key> res;
695 const_iterator i = begin();
696 while (i != end()) {
697 if (i.value() == avalue)
698 res.append(i.key());
699 ++i;
700 }
701 return res;
702}
703
704template <class Key, class T>
705Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue) const
706{
707 return key(avalue, Key());
708}
709
710template <class Key, class T>
711Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue, const Key &defaultValue) const
712{
713 const_iterator i = begin();
714 while (i != end()) {
715 if (i.value() == avalue)
716 return i.key();
717 ++i;
718 }
719
720 return defaultValue;
721}
722
723template <class Key, class T>
724Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values() const
725{
726 QList<T> res;
727 res.reserve(size());
728 const_iterator i = begin();
729 while (i != end()) {
730 res.append(i.value());
731 ++i;
732 }
733 return res;
734}
735
736template <class Key, class T>
737Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const
738{
739 QList<T> res;
740 Node *node = *findNode(akey);
741 if (node != e) {
742 do {
743 res.append(node->value);
744 } while ((node = node->next) != e && node->key == akey);
745 }
746 return res;
747}
748
749template <class Key, class T>
750Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::count(const Key &akey) const
751{
752 int cnt = 0;
753 Node *node = *findNode(akey);
754 if (node != e) {
755 do {
756 ++cnt;
757 } while ((node = node->next) != e && node->key == akey);
758 }
759 return cnt;
760}
761
762template <class Key, class T>
763Q_INLINE_TEMPLATE const T QHash<Key, T>::operator[](const Key &akey) const
764{
765 return value(akey);
766}
767
768template <class Key, class T>
769Q_INLINE_TEMPLATE T &QHash<Key, T>::operator[](const Key &akey)
770{
771 detach();
772
773 uint h;
774 Node **node = findNode(akey, &h);
775 if (*node == e) {
776 if (d->willGrow())
777 node = findNode(akey, h);
778 return createNode(h, akey, T(), node)->value;
779 }
780 return (*node)->value;
781}
782
783template <class Key, class T>
784Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &akey,
785 const T &avalue)
786{
787 detach();
788
789 uint h;
790 Node **node = findNode(akey, &h);
791 if (*node == e) {
792 if (d->willGrow())
793 node = findNode(akey, h);
794 return iterator(createNode(h, akey, avalue, node));
795 }
796
797 if (!std::is_same<T, QHashDummyValue>::value)
798 (*node)->value = avalue;
799 return iterator(*node);
800}
801
802template <class Key, class T>
803Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &akey,
804 const T &avalue)
805{
806 detach();
807 d->willGrow();
808
809 uint h;
810 Node **nextNode = findNode(akey, &h);
811 return iterator(createNode(h, akey, avalue, nextNode));
812}
813
814template <class Key, class T>
815Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::remove(const Key &akey)
816{
817 if (isEmpty()) // prevents detaching shared null
818 return 0;
819 detach();
820
821 int oldSize = d->size;
822 Node **node = findNode(akey);
823 if (*node != e) {
824 bool deleteNext = true;
825 do {
826 Node *next = (*node)->next;
827 deleteNext = (next != e && next->key == (*node)->key);
828 deleteNode(*node);
829 *node = next;
830 --d->size;
831 } while (deleteNext);
832 d->hasShrunk();
833 }
834 return oldSize - d->size;
835}
836
837template <class Key, class T>
838Q_OUTOFLINE_TEMPLATE T QHash<Key, T>::take(const Key &akey)
839{
840 if (isEmpty()) // prevents detaching shared null
841 return T();
842 detach();
843
844 Node **node = findNode(akey);
845 if (*node != e) {
846 T t = std::move((*node)->value);
847 Node *next = (*node)->next;
848 deleteNode(*node);
849 *node = next;
850 --d->size;
851 d->hasShrunk();
852 return t;
853 }
854 return T();
855}
856
857template <class Key, class T>
858Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::erase(const_iterator it)
859{
860 Q_ASSERT_X(isValidIterator(it), "QHash::erase", "The specified iterator argument 'it' is invalid");
861
862 if (it == const_iterator(e))
863 return iterator(it.i);
864
865 if (d->ref.isShared()) {
866 // save 'it' across the detach:
867 int bucketNum = (it.i->h % d->numBuckets);
868 const_iterator bucketIterator(*(d->buckets + bucketNum));
869 int stepsFromBucketStartToIte = 0;
870 while (bucketIterator != it) {
871 ++stepsFromBucketStartToIte;
872 ++bucketIterator;
873 }
874 detach();
875 it = const_iterator(*(d->buckets + bucketNum));
876 while (stepsFromBucketStartToIte > 0) {
877 --stepsFromBucketStartToIte;
878 ++it;
879 }
880 }
881
882 iterator ret(it.i);
883 ++ret;
884
885 Node *node = concrete(it.i);
886 Node **node_ptr = reinterpret_cast<Node **>(&d->buckets[node->h % d->numBuckets]);
887 while (*node_ptr != node)
888 node_ptr = &(*node_ptr)->next;
889 *node_ptr = node->next;
890 deleteNode(node);
891 --d->size;
892 return ret;
893}
894
895template <class Key, class T>
896Q_INLINE_TEMPLATE void QHash<Key, T>::reserve(int asize)
897{
898 detach();
899 d->rehash(-qMax(asize, 1));
900}
901
902template <class Key, class T>
903Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &akey) const
904{
905 return const_iterator(*findNode(akey));
906}
907
908template <class Key, class T>
909Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &akey) const
910{
911 return const_iterator(*findNode(akey));
912}
913
914template <class Key, class T>
915Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::find(const Key &akey)
916{
917 detach();
918 return iterator(*findNode(akey));
919}
920
921template <class Key, class T>
922Q_INLINE_TEMPLATE bool QHash<Key, T>::contains(const Key &akey) const
923{
924 return *findNode(akey) != e;
925}
926
927template <class Key, class T>
928Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey, uint h) const
929{
930 Node **node;
931
932 if (d->numBuckets) {
933 node = reinterpret_cast<Node **>(&d->buckets[h % d->numBuckets]);
934 Q_ASSERT(*node == e || (*node)->next);
935 while (*node != e && !(*node)->same_key(h, akey))
936 node = &(*node)->next;
937 } else {
938 node = const_cast<Node **>(reinterpret_cast<const Node * const *>(&e));
939 }
940 return node;
941}
942
943template <class Key, class T>
944Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey,
945 uint *ahp) const
946{
947 uint h = 0;
948
949 if (d->numBuckets || ahp) {
950 h = qHash(akey, d->seed);
951 if (ahp)
952 *ahp = h;
953 }
954 return findNode(akey, h);
955}
956
957template <class Key, class T>
958Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash &other) const
959{
960 if (d == other.d)
961 return true;
962 if (size() != other.size())
963 return false;
964
965 const_iterator it = begin();
966
967 while (it != end()) {
968 // Build two equal ranges for i.key(); one for *this and one for other.
969 // For *this we can avoid a lookup via equal_range, as we know the beginning of the range.
970 auto thisEqualRangeStart = it;
971 const Key &thisEqualRangeKey = it.key();
972 size_type n = 0;
973 do {
974 ++it;
975 ++n;
976 } while (it != end() && it.key() == thisEqualRangeKey);
977
978 const auto otherEqualRange = other.equal_range(thisEqualRangeKey);
979
980 if (n != std::distance(otherEqualRange.first, otherEqualRange.second))
981 return false;
982
983 // Keys in the ranges are equal by construction; this checks only the values.
984 if (!qt_is_permutation(thisEqualRangeStart, it, otherEqualRange.first, otherEqualRange.second))
985 return false;
986 }
987
988 return true;
989}
990
991template <class Key, class T>
992QPair<typename QHash<Key, T>::iterator, typename QHash<Key, T>::iterator> QHash<Key, T>::equal_range(const Key &akey)
993{
994 detach();
995 auto pair = qAsConst(*this).equal_range(akey);
996 return qMakePair(iterator(pair.first.i), iterator(pair.second.i));
997}
998
999template <class Key, class T>
1000QPair<typename QHash<Key, T>::const_iterator, typename QHash<Key, T>::const_iterator> QHash<Key, T>::equal_range(const Key &akey) const noexcept
1001{
1002 Node *node = *findNode(akey);
1003 const_iterator firstIt = const_iterator(node);
1004
1005 if (node != e) {
1006 // equal keys must hash to the same value and so they all
1007 // end up in the same bucket. So we can use node->next,
1008 // which only works within a bucket, instead of (out-of-line)
1009 // QHashData::nextNode()
1010 while (node->next != e && node->next->key == akey)
1011 node = node->next;
1012
1013 // 'node' may be the last node in the bucket. To produce the end iterator, we'd
1014 // need to enter the next bucket in this case, so we need to use
1015 // QHashData::nextNode() here, which, unlike node->next above, can move between
1016 // buckets.
1017 node = concrete(QHashData::nextNode(reinterpret_cast<QHashData::Node *>(node)));
1018 }
1019
1020 return qMakePair(firstIt, const_iterator(node));
1021}
1022
1023template <class Key, class T>
1024class QMultiHash : public QHash<Key, T>
1025{
1026public:
1027 QMultiHash() noexcept {}
1028 inline QMultiHash(std::initializer_list<std::pair<Key,T> > list)
1029 {
1030 this->reserve(int(list.size()));
1031 for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
1032 insert(it->first, it->second);
1033 }
1034#ifdef Q_QDOC
1035 template <typename InputIterator>
1036 QMultiHash(InputIterator f, InputIterator l);
1037#else
1038 template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasKeyAndValue<InputIterator> = true>
1039 QMultiHash(InputIterator f, InputIterator l)
1040 {
1041 QtPrivate::reserveIfForwardIterator(this, f, l);
1042 for (; f != l; ++f)
1043 insert(f.key(), f.value());
1044 }
1045
1046 template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true>
1047 QMultiHash(InputIterator f, InputIterator l)
1048 {
1049 QtPrivate::reserveIfForwardIterator(this, f, l);
1050 for (; f != l; ++f)
1051 insert(f->first, f->second);
1052 }
1053#endif
1054 // compiler-generated copy/move ctors/assignment operators are fine!
1055 // compiler-generated destructor is fine!
1056
1057 QMultiHash(const QHash<Key, T> &other) : QHash<Key, T>(other) {}
1058 QMultiHash(QHash<Key, T> &&other) noexcept : QHash<Key, T>(std::move(other)) {}
1059 void swap(QMultiHash &other) noexcept { QHash<Key, T>::swap(other); } // prevent QMultiHash<->QHash swaps
1060
1061 inline typename QHash<Key, T>::iterator replace(const Key &key, const T &value)
1062 { return QHash<Key, T>::insert(key, value); }
1063
1064 inline typename QHash<Key, T>::iterator insert(const Key &key, const T &value)
1065 { return QHash<Key, T>::insertMulti(key, value); }
1066
1067 inline QMultiHash &operator+=(const QMultiHash &other)
1068 { this->unite(other); return *this; }
1069 inline QMultiHash operator+(const QMultiHash &other) const
1070 { QMultiHash result = *this; result += other; return result; }
1071
1072 using QHash<Key, T>::contains;
1073 using QHash<Key, T>::remove;
1074 using QHash<Key, T>::count;
1075 using QHash<Key, T>::find;
1076 using QHash<Key, T>::constFind;
1077
1078 bool contains(const Key &key, const T &value) const;
1079
1080 int remove(const Key &key, const T &value);
1081
1082 int count(const Key &key, const T &value) const;
1083
1084 typename QHash<Key, T>::iterator find(const Key &key, const T &value) {
1085 typename QHash<Key, T>::iterator i(find(key));
1086 typename QHash<Key, T>::iterator end(this->end());
1087 while (i != end && i.key() == key) {
1088 if (i.value() == value)
1089 return i;
1090 ++i;
1091 }
1092 return end;
1093 }
1094 typename QHash<Key, T>::const_iterator find(const Key &key, const T &value) const {
1095 typename QHash<Key, T>::const_iterator i(constFind(key));
1096 typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
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 constFind(const Key &key, const T &value) const
1105 { return find(key, value); }
1106private:
1107 T &operator[](const Key &key);
1108 const T operator[](const Key &key) const;
1109};
1110
1111template <class Key, class T>
1112Q_INLINE_TEMPLATE bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const
1113{
1114 return constFind(key, value) != QHash<Key, T>::constEnd();
1115}
1116
1117template <class Key, class T>
1118Q_INLINE_TEMPLATE int QMultiHash<Key, T>::remove(const Key &key, const T &value)
1119{
1120 int n = 0;
1121 typename QHash<Key, T>::iterator i(find(key));
1122 typename QHash<Key, T>::iterator end(QHash<Key, T>::end());
1123 while (i != end && i.key() == key) {
1124 if (i.value() == value) {
1125 i = this->erase(i);
1126 ++n;
1127 } else {
1128 ++i;
1129 }
1130 }
1131 return n;
1132}
1133
1134template <class Key, class T>
1135Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value) const
1136{
1137 int n = 0;
1138 typename QHash<Key, T>::const_iterator i(constFind(key));
1139 typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
1140 while (i != end && i.key() == key) {
1141 if (i.value() == value)
1142 ++n;
1143 ++i;
1144 }
1145 return n;
1146}
1147
1148Q_DECLARE_ASSOCIATIVE_ITERATOR(Hash)
1149Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Hash)
1150
1151template <class Key, class T>
1152uint qHash(const QHash<Key, T> &key, uint seed = 0)
1153 noexcept(noexcept(qHash(std::declval<Key&>())) && noexcept(qHash(std::declval<T&>())))
1154{
1155 QtPrivate::QHashCombineCommutative hash;
1156 for (auto it = key.begin(), end = key.end(); it != end; ++it) {
1157 const Key &k = it.key();
1158 const T &v = it.value();
1159 seed = hash(seed, std::pair<const Key&, const T&>(k, v));
1160 }
1161 return seed;
1162}
1163
1164template <class Key, class T>
1165inline uint qHash(const QMultiHash<Key, T> &key, uint seed = 0)
1166 noexcept(noexcept(qHash(std::declval<Key&>())) && noexcept(qHash(std::declval<T&>())))
1167{
1168 const QHash<Key, T> &key2 = key;
1169 return qHash(key2, seed);
1170}
1171
1172QT_END_NAMESPACE
1173
1174#if defined(Q_CC_MSVC)
1175#pragma warning( pop )
1176#endif
1177
1178#endif // QHASH_H
1179