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
50#ifdef Q_COMPILER_INITIALIZER_LISTS
51#include <initializer_list>
52#endif
53
54#include <algorithm>
55
56#if defined(Q_CC_MSVC)
57#pragma warning( push )
58#pragma warning( disable : 4311 ) // disable pointer truncation warning
59#pragma warning( disable : 4127 ) // conditional expression is constant
60#endif
61
62QT_BEGIN_NAMESPACE
63
64struct Q_CORE_EXPORT QHashData
65{
66 struct Node {
67 Node *next;
68 uint h;
69 };
70
71 Node *fakeNext;
72 Node **buckets;
73 QtPrivate::RefCount ref;
74 int size;
75 int nodeSize;
76 short userNumBits;
77 short numBits;
78 int numBuckets;
79 uint seed;
80 uint sharable : 1;
81 uint strictAlignment : 1;
82 uint reserved : 30;
83
84 void *allocateNode(int nodeAlign);
85 void freeNode(void *node);
86 QHashData *detach_helper(void (*node_duplicate)(Node *, void *), void (*node_delete)(Node *),
87 int nodeSize, int nodeAlign);
88 bool willGrow();
89 void hasShrunk();
90 void rehash(int hint);
91 void free_helper(void (*node_delete)(Node *));
92 Node *firstNode();
93#ifdef QT_QHASH_DEBUG
94 void dump();
95 void checkSanity();
96#endif
97 static Node *nextNode(Node *node);
98 static Node *previousNode(Node *node);
99
100 static const QHashData shared_null;
101};
102
103inline bool QHashData::willGrow()
104{
105 if (size >= numBuckets) {
106 rehash(numBits + 1);
107 return true;
108 } else {
109 return false;
110 }
111}
112
113inline void QHashData::hasShrunk()
114{
115 if (size <= (numBuckets >> 3) && numBits > userNumBits) {
116 QT_TRY {
117 rehash(qMax(int(numBits) - 2, int(userNumBits)));
118 } QT_CATCH(const std::bad_alloc &) {
119 // ignore bad allocs - shrinking shouldn't throw. rehash is exception safe.
120 }
121 }
122}
123
124inline QHashData::Node *QHashData::firstNode()
125{
126 Node *e = reinterpret_cast<Node *>(this);
127 Node **bucket = buckets;
128 int n = numBuckets;
129 while (n--) {
130 if (*bucket != e)
131 return *bucket;
132 ++bucket;
133 }
134 return e;
135}
136
137struct QHashDummyValue
138{
139};
140
141inline bool operator==(const QHashDummyValue & /* v1 */, const QHashDummyValue & /* v2 */)
142{
143 return true;
144}
145
146Q_DECLARE_TYPEINFO(QHashDummyValue, Q_MOVABLE_TYPE | Q_DUMMY_TYPE);
147
148template <class Key, class T>
149struct QHashNode
150{
151 QHashNode *next;
152 const uint h;
153 const Key key;
154 T value;
155
156 inline QHashNode(const Key &key0, const T &value0, uint hash, QHashNode *n)
157 : next(n), h(hash), key(key0), value(value0) {}
158 inline bool same_key(uint h0, const Key &key0) const { return h0 == h && key0 == key; }
159
160private:
161 Q_DISABLE_COPY(QHashNode)
162};
163
164// Specialize for QHashDummyValue in order to save some memory
165template <class Key>
166struct QHashNode<Key, QHashDummyValue>
167{
168 union {
169 QHashNode *next;
170 QHashDummyValue value;
171 };
172 const uint h;
173 const Key key;
174
175 inline QHashNode(const Key &key0, const QHashDummyValue &, uint hash, QHashNode *n)
176 : next(n), h(hash), key(key0) {}
177 inline bool same_key(uint h0, const Key &key0) const { return h0 == h && key0 == key; }
178
179private:
180 Q_DISABLE_COPY(QHashNode)
181};
182
183
184#if 0
185// ###
186// The introduction of the QHash random seed breaks this optimization, as it
187// relies on qHash(int i) = i. If the hash value is salted, then the hash
188// table becomes corrupted.
189//
190// A bit more research about whether it makes sense or not to salt integer
191// keys (and in general keys whose hash value is easy to invert)
192// is needed, or about how keep this optimization and the seed (f.i. by
193// specializing QHash for integer values, and re-apply the seed during lookup).
194//
195// Be aware that such changes can easily be binary incompatible, and therefore
196// cannot be made during the Qt 5 lifetime.
197#define Q_HASH_DECLARE_INT_NODES(key_type) \
198 template <class T> \
199 struct QHashDummyNode<key_type, T> { \
200 QHashDummyNode *next; \
201 union { uint h; key_type key; }; \
202\
203 inline QHashDummyNode(key_type /* key0 */) {} \
204 }; \
205\
206 template <class T> \
207 struct QHashNode<key_type, T> { \
208 QHashNode *next; \
209 union { uint h; key_type key; }; \
210 T value; \
211\
212 inline QHashNode(key_type /* key0 */) {} \
213 inline QHashNode(key_type /* key0 */, const T &value0) : value(value0) {} \
214 inline bool same_key(uint h0, key_type) const { return h0 == h; } \
215 }
216
217#if defined(Q_BYTE_ORDER) && Q_BYTE_ORDER == Q_LITTLE_ENDIAN
218Q_HASH_DECLARE_INT_NODES(short);
219Q_HASH_DECLARE_INT_NODES(ushort);
220#endif
221Q_HASH_DECLARE_INT_NODES(int);
222Q_HASH_DECLARE_INT_NODES(uint);
223#undef Q_HASH_DECLARE_INT_NODES
224#endif // #if 0
225
226template <class Key, class T>
227class QHash
228{
229 typedef QHashNode<Key, T> Node;
230
231 union {
232 QHashData *d;
233 QHashNode<Key, T> *e;
234 };
235
236 static inline Node *concrete(QHashData::Node *node) {
237 return reinterpret_cast<Node *>(node);
238 }
239
240 static inline int alignOfNode() { return qMax<int>(sizeof(void*), Q_ALIGNOF(Node)); }
241
242public:
243 inline QHash() Q_DECL_NOTHROW : d(const_cast<QHashData *>(&QHashData::shared_null)) { }
244#ifdef Q_COMPILER_INITIALIZER_LISTS
245 inline QHash(std::initializer_list<std::pair<Key,T> > list)
246 : d(const_cast<QHashData *>(&QHashData::shared_null))
247 {
248 reserve(int(list.size()));
249 for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
250 insert(it->first, it->second);
251 }
252#endif
253 QHash(const QHash &other) : d(other.d) { d->ref.ref(); if (!d->sharable) detach(); }
254 ~QHash() { if (!d->ref.deref()) freeData(d); }
255
256 QHash &operator=(const QHash &other);
257#ifdef Q_COMPILER_RVALUE_REFS
258 QHash(QHash &&other) Q_DECL_NOTHROW : d(other.d) { other.d = const_cast<QHashData *>(&QHashData::shared_null); }
259 QHash &operator=(QHash &&other) Q_DECL_NOTHROW
260 { QHash moved(std::move(other)); swap(moved); return *this; }
261#endif
262 void swap(QHash &other) Q_DECL_NOTHROW { qSwap(d, other.d); }
263
264 bool operator==(const QHash &other) const;
265 bool operator!=(const QHash &other) const { return !(*this == other); }
266
267 inline int size() const { return d->size; }
268
269 inline bool isEmpty() const { return d->size == 0; }
270
271 inline int capacity() const { return d->numBuckets; }
272 void reserve(int size);
273 inline void squeeze() { reserve(1); }
274
275 inline void detach() { if (d->ref.isShared()) detach_helper(); }
276 inline bool isDetached() const { return !d->ref.isShared(); }
277#if !defined(QT_NO_UNSHARABLE_CONTAINERS)
278 inline void setSharable(bool sharable) { if (!sharable) detach(); if (d != &QHashData::shared_null) d->sharable = sharable; }
279#endif
280 bool isSharedWith(const QHash &other) const { return d == other.d; }
281
282 void clear();
283
284 int remove(const Key &key);
285 T take(const Key &key);
286
287 bool contains(const Key &key) const;
288 const Key key(const T &value) const;
289 const Key key(const T &value, const Key &defaultKey) const;
290 const T value(const Key &key) const;
291 const T value(const Key &key, const T &defaultValue) const;
292 T &operator[](const Key &key);
293 const T operator[](const Key &key) const;
294
295 QList<Key> uniqueKeys() const;
296 QList<Key> keys() const;
297 QList<Key> keys(const T &value) const;
298 QList<T> values() const;
299 QList<T> values(const Key &key) const;
300 int count(const Key &key) const;
301
302 class const_iterator;
303
304 class iterator
305 {
306 friend class const_iterator;
307 friend class QHash<Key, T>;
308 friend class QSet<Key>;
309 QHashData::Node *i;
310
311 public:
312 typedef std::bidirectional_iterator_tag iterator_category;
313 typedef qptrdiff difference_type;
314 typedef T value_type;
315 typedef T *pointer;
316 typedef T &reference;
317
318 inline iterator() : i(nullptr) { }
319 explicit inline iterator(void *node) : i(reinterpret_cast<QHashData::Node *>(node)) { }
320
321 inline const Key &key() const { return concrete(i)->key; }
322 inline T &value() const { return concrete(i)->value; }
323 inline T &operator*() const { return concrete(i)->value; }
324 inline T *operator->() const { return &concrete(i)->value; }
325 inline bool operator==(const iterator &o) const { return i == o.i; }
326 inline bool operator!=(const iterator &o) const { return i != o.i; }
327
328 inline iterator &operator++() {
329 i = QHashData::nextNode(i);
330 return *this;
331 }
332 inline iterator operator++(int) {
333 iterator r = *this;
334 i = QHashData::nextNode(i);
335 return r;
336 }
337 inline iterator &operator--() {
338 i = QHashData::previousNode(i);
339 return *this;
340 }
341 inline iterator operator--(int) {
342 iterator r = *this;
343 i = QHashData::previousNode(i);
344 return r;
345 }
346 inline iterator operator+(int j) const
347 { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
348 inline iterator operator-(int j) const { return operator+(-j); }
349 inline iterator &operator+=(int j) { return *this = *this + j; }
350 inline iterator &operator-=(int j) { return *this = *this - j; }
351 friend inline iterator operator+(int j, iterator k) { return k + j; }
352
353#ifndef QT_STRICT_ITERATORS
354 public:
355 inline bool operator==(const const_iterator &o) const
356 { return i == o.i; }
357 inline bool operator!=(const const_iterator &o) const
358 { return i != o.i; }
359#endif
360 };
361 friend class iterator;
362
363 class const_iterator
364 {
365 friend class iterator;
366 friend class QHash<Key, T>;
367 friend class QSet<Key>;
368 QHashData::Node *i;
369
370 public:
371 typedef std::bidirectional_iterator_tag iterator_category;
372 typedef qptrdiff difference_type;
373 typedef T value_type;
374 typedef const T *pointer;
375 typedef const T &reference;
376
377 Q_DECL_CONSTEXPR inline const_iterator() : i(nullptr) { }
378 explicit inline const_iterator(void *node)
379 : i(reinterpret_cast<QHashData::Node *>(node)) { }
380#ifdef QT_STRICT_ITERATORS
381 explicit inline const_iterator(const iterator &o)
382#else
383 inline const_iterator(const iterator &o)
384#endif
385 { i = o.i; }
386
387 inline const Key &key() const { return concrete(i)->key; }
388 inline const T &value() const { return concrete(i)->value; }
389 inline const T &operator*() const { return concrete(i)->value; }
390 inline const T *operator->() const { return &concrete(i)->value; }
391 Q_DECL_CONSTEXPR inline bool operator==(const const_iterator &o) const { return i == o.i; }
392 Q_DECL_CONSTEXPR inline bool operator!=(const const_iterator &o) const { return i != o.i; }
393
394 inline const_iterator &operator++() {
395 i = QHashData::nextNode(i);
396 return *this;
397 }
398 inline const_iterator operator++(int) {
399 const_iterator r = *this;
400 i = QHashData::nextNode(i);
401 return r;
402 }
403 inline const_iterator &operator--() {
404 i = QHashData::previousNode(i);
405 return *this;
406 }
407 inline const_iterator operator--(int) {
408 const_iterator r = *this;
409 i = QHashData::previousNode(i);
410 return r;
411 }
412 inline const_iterator operator+(int j) const
413 { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
414 inline const_iterator operator-(int j) const { return operator+(-j); }
415 inline const_iterator &operator+=(int j) { return *this = *this + j; }
416 inline const_iterator &operator-=(int j) { return *this = *this - j; }
417 friend inline const_iterator operator+(int j, const_iterator k) { return k + j; }
418
419 // ### Qt 5: not sure this is necessary anymore
420#ifdef QT_STRICT_ITERATORS
421 private:
422 inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); }
423 inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); }
424#endif
425 };
426 friend class const_iterator;
427
428 class key_iterator
429 {
430 const_iterator i;
431
432 public:
433 typedef typename const_iterator::iterator_category iterator_category;
434 typedef typename const_iterator::difference_type difference_type;
435 typedef Key value_type;
436 typedef const Key *pointer;
437 typedef const Key &reference;
438
439 key_iterator() = default;
440 explicit key_iterator(const_iterator o) : i(o) { }
441
442 const Key &operator*() const { return i.key(); }
443 const Key *operator->() const { return &i.key(); }
444 bool operator==(key_iterator o) const { return i == o.i; }
445 bool operator!=(key_iterator o) const { return i != o.i; }
446
447 inline key_iterator &operator++() { ++i; return *this; }
448 inline key_iterator operator++(int) { return key_iterator(i++);}
449 inline key_iterator &operator--() { --i; return *this; }
450 inline key_iterator operator--(int) { return key_iterator(i--); }
451 const_iterator base() const { return i; }
452 };
453
454 typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator;
455 typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator;
456
457 // STL style
458 inline iterator begin() { detach(); return iterator(d->firstNode()); }
459 inline const_iterator begin() const { return const_iterator(d->firstNode()); }
460 inline const_iterator cbegin() const { return const_iterator(d->firstNode()); }
461 inline const_iterator constBegin() const { return const_iterator(d->firstNode()); }
462 inline iterator end() { detach(); return iterator(e); }
463 inline const_iterator end() const { return const_iterator(e); }
464 inline const_iterator cend() const { return const_iterator(e); }
465 inline const_iterator constEnd() const { return const_iterator(e); }
466 inline key_iterator keyBegin() const { return key_iterator(begin()); }
467 inline key_iterator keyEnd() const { return key_iterator(end()); }
468 inline key_value_iterator keyValueBegin() { return key_value_iterator(begin()); }
469 inline key_value_iterator keyValueEnd() { return key_value_iterator(end()); }
470 inline const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); }
471 inline const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); }
472 inline const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); }
473 inline const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); }
474
475 QPair<iterator, iterator> equal_range(const Key &key);
476 QPair<const_iterator, const_iterator> equal_range(const Key &key) const Q_DECL_NOTHROW;
477 iterator erase(iterator it) { return erase(const_iterator(it.i)); }
478 iterator erase(const_iterator it);
479
480 // more Qt
481 typedef iterator Iterator;
482 typedef const_iterator ConstIterator;
483 inline int count() const { return d->size; }
484 iterator find(const Key &key);
485 const_iterator find(const Key &key) const;
486 const_iterator constFind(const Key &key) const;
487 iterator insert(const Key &key, const T &value);
488 iterator insertMulti(const Key &key, const T &value);
489 QHash &unite(const QHash &other);
490
491 // STL compatibility
492 typedef T mapped_type;
493 typedef Key key_type;
494 typedef qptrdiff difference_type;
495 typedef int size_type;
496
497 inline bool empty() const { return isEmpty(); }
498
499#ifdef QT_QHASH_DEBUG
500 inline void dump() const { d->dump(); }
501 inline void checkSanity() const { d->checkSanity(); }
502#endif
503
504private:
505 void detach_helper();
506 void freeData(QHashData *d);
507 Node **findNode(const Key &key, uint *hp = nullptr) const;
508 Node **findNode(const Key &key, uint h) const;
509 Node *createNode(uint h, const Key &key, const T &value, Node **nextNode);
510 void deleteNode(Node *node);
511 static void deleteNode2(QHashData::Node *node);
512
513 static void duplicateNode(QHashData::Node *originalNode, void *newNode);
514
515 bool isValidIterator(const iterator &it) const Q_DECL_NOTHROW
516 { return isValidNode(it.i); }
517 bool isValidIterator(const const_iterator &it) const Q_DECL_NOTHROW
518 { return isValidNode(it.i); }
519 bool isValidNode(QHashData::Node *node) const Q_DECL_NOTHROW
520 {
521#if defined(QT_DEBUG) && !defined(Q_HASH_NO_ITERATOR_DEBUG)
522 while (node->next)
523 node = node->next;
524 return (static_cast<void *>(node) == d);
525#else
526 Q_UNUSED(node);
527 return true;
528#endif
529 }
530 friend class QSet<Key>;
531};
532
533
534template <class Key, class T>
535Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(Node *node)
536{
537 deleteNode2(reinterpret_cast<QHashData::Node*>(node));
538 d->freeNode(node);
539}
540
541template <class Key, class T>
542Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode2(QHashData::Node *node)
543{
544#ifdef Q_CC_BOR
545 concrete(node)->~QHashNode<Key, T>();
546#else
547 concrete(node)->~Node();
548#endif
549}
550
551template <class Key, class T>
552Q_INLINE_TEMPLATE void QHash<Key, T>::duplicateNode(QHashData::Node *node, void *newNode)
553{
554 Node *concreteNode = concrete(node);
555 new (newNode) Node(concreteNode->key, concreteNode->value, concreteNode->h, nullptr);
556}
557
558template <class Key, class T>
559Q_INLINE_TEMPLATE typename QHash<Key, T>::Node *
560QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anextNode)
561{
562 Node *node = new (d->allocateNode(alignOfNode())) Node(akey, avalue, ah, *anextNode);
563 *anextNode = node;
564 ++d->size;
565 return node;
566}
567
568template <class Key, class T>
569Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash &other)
570{
571 if (d == &QHashData::shared_null) {
572 *this = other;
573 } else {
574 QHash copy(other);
575 const_iterator it = copy.constEnd();
576 while (it != copy.constBegin()) {
577 --it;
578 insertMulti(it.key(), it.value());
579 }
580 }
581 return *this;
582}
583
584template <class Key, class T>
585Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x)
586{
587 x->free_helper(deleteNode2);
588}
589
590template <class Key, class T>
591Q_INLINE_TEMPLATE void QHash<Key, T>::clear()
592{
593 *this = QHash();
594}
595
596template <class Key, class T>
597Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::detach_helper()
598{
599 QHashData *x = d->detach_helper(duplicateNode, deleteNode2, sizeof(Node), alignOfNode());
600 if (!d->ref.deref())
601 freeData(d);
602 d = x;
603}
604
605template <class Key, class T>
606Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::operator=(const QHash &other)
607{
608 if (d != other.d) {
609 QHashData *o = other.d;
610 o->ref.ref();
611 if (!d->ref.deref())
612 freeData(d);
613 d = o;
614 if (!d->sharable)
615 detach_helper();
616 }
617 return *this;
618}
619
620template <class Key, class T>
621Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey) const
622{
623 Node *node;
624 if (d->size == 0 || (node = *findNode(akey)) == e) {
625 return T();
626 } else {
627 return node->value;
628 }
629}
630
631template <class Key, class T>
632Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey, const T &adefaultValue) const
633{
634 Node *node;
635 if (d->size == 0 || (node = *findNode(akey)) == e) {
636 return adefaultValue;
637 } else {
638 return node->value;
639 }
640}
641
642template <class Key, class T>
643Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const
644{
645 QList<Key> res;
646 res.reserve(size()); // May be too much, but assume short lifetime
647 const_iterator i = begin();
648 if (i != end()) {
649 for (;;) {
650 const Key &aKey = i.key();
651 res.append(aKey);
652 do {
653 if (++i == end())
654 goto break_out_of_outer_loop;
655 } while (aKey == i.key());
656 }
657 }
658break_out_of_outer_loop:
659 return res;
660}
661
662template <class Key, class T>
663Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys() const
664{
665 QList<Key> res;
666 res.reserve(size());
667 const_iterator i = begin();
668 while (i != end()) {
669 res.append(i.key());
670 ++i;
671 }
672 return res;
673}
674
675template <class Key, class T>
676Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys(const T &avalue) const
677{
678 QList<Key> res;
679 const_iterator i = begin();
680 while (i != end()) {
681 if (i.value() == avalue)
682 res.append(i.key());
683 ++i;
684 }
685 return res;
686}
687
688template <class Key, class T>
689Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue) const
690{
691 return key(avalue, Key());
692}
693
694template <class Key, class T>
695Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue, const Key &defaultValue) const
696{
697 const_iterator i = begin();
698 while (i != end()) {
699 if (i.value() == avalue)
700 return i.key();
701 ++i;
702 }
703
704 return defaultValue;
705}
706
707template <class Key, class T>
708Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values() const
709{
710 QList<T> res;
711 res.reserve(size());
712 const_iterator i = begin();
713 while (i != end()) {
714 res.append(i.value());
715 ++i;
716 }
717 return res;
718}
719
720template <class Key, class T>
721Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const
722{
723 QList<T> res;
724 Node *node = *findNode(akey);
725 if (node != e) {
726 do {
727 res.append(node->value);
728 } while ((node = node->next) != e && node->key == akey);
729 }
730 return res;
731}
732
733template <class Key, class T>
734Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::count(const Key &akey) const
735{
736 int cnt = 0;
737 Node *node = *findNode(akey);
738 if (node != e) {
739 do {
740 ++cnt;
741 } while ((node = node->next) != e && node->key == akey);
742 }
743 return cnt;
744}
745
746template <class Key, class T>
747Q_INLINE_TEMPLATE const T QHash<Key, T>::operator[](const Key &akey) const
748{
749 return value(akey);
750}
751
752template <class Key, class T>
753Q_INLINE_TEMPLATE T &QHash<Key, T>::operator[](const Key &akey)
754{
755 detach();
756
757 uint h;
758 Node **node = findNode(akey, &h);
759 if (*node == e) {
760 if (d->willGrow())
761 node = findNode(akey, h);
762 return createNode(h, akey, T(), node)->value;
763 }
764 return (*node)->value;
765}
766
767template <class Key, class T>
768Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &akey,
769 const T &avalue)
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 iterator(createNode(h, akey, avalue, node));
779 }
780
781 if (!std::is_same<T, QHashDummyValue>::value)
782 (*node)->value = avalue;
783 return iterator(*node);
784}
785
786template <class Key, class T>
787Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &akey,
788 const T &avalue)
789{
790 detach();
791 d->willGrow();
792
793 uint h;
794 Node **nextNode = findNode(akey, &h);
795 return iterator(createNode(h, akey, avalue, nextNode));
796}
797
798template <class Key, class T>
799Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::remove(const Key &akey)
800{
801 if (isEmpty()) // prevents detaching shared null
802 return 0;
803 detach();
804
805 int oldSize = d->size;
806 Node **node = findNode(akey);
807 if (*node != e) {
808 bool deleteNext = true;
809 do {
810 Node *next = (*node)->next;
811 deleteNext = (next != e && next->key == (*node)->key);
812 deleteNode(*node);
813 *node = next;
814 --d->size;
815 } while (deleteNext);
816 d->hasShrunk();
817 }
818 return oldSize - d->size;
819}
820
821template <class Key, class T>
822Q_OUTOFLINE_TEMPLATE T QHash<Key, T>::take(const Key &akey)
823{
824 if (isEmpty()) // prevents detaching shared null
825 return T();
826 detach();
827
828 Node **node = findNode(akey);
829 if (*node != e) {
830 T t = std::move((*node)->value);
831 Node *next = (*node)->next;
832 deleteNode(*node);
833 *node = next;
834 --d->size;
835 d->hasShrunk();
836 return t;
837 }
838 return T();
839}
840
841template <class Key, class T>
842Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::erase(const_iterator it)
843{
844 Q_ASSERT_X(isValidIterator(it), "QHash::erase", "The specified iterator argument 'it' is invalid");
845
846 if (it == const_iterator(e))
847 return iterator(it.i);
848
849 if (d->ref.isShared()) {
850 // save 'it' across the detach:
851 int bucketNum = (it.i->h % d->numBuckets);
852 const_iterator bucketIterator(*(d->buckets + bucketNum));
853 int stepsFromBucketStartToIte = 0;
854 while (bucketIterator != it) {
855 ++stepsFromBucketStartToIte;
856 ++bucketIterator;
857 }
858 detach();
859 it = const_iterator(*(d->buckets + bucketNum));
860 while (stepsFromBucketStartToIte > 0) {
861 --stepsFromBucketStartToIte;
862 ++it;
863 }
864 }
865
866 iterator ret(it.i);
867 ++ret;
868
869 Node *node = concrete(it.i);
870 Node **node_ptr = reinterpret_cast<Node **>(&d->buckets[node->h % d->numBuckets]);
871 while (*node_ptr != node)
872 node_ptr = &(*node_ptr)->next;
873 *node_ptr = node->next;
874 deleteNode(node);
875 --d->size;
876 return ret;
877}
878
879template <class Key, class T>
880Q_INLINE_TEMPLATE void QHash<Key, T>::reserve(int asize)
881{
882 detach();
883 d->rehash(-qMax(asize, 1));
884}
885
886template <class Key, class T>
887Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &akey) const
888{
889 return const_iterator(*findNode(akey));
890}
891
892template <class Key, class T>
893Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &akey) const
894{
895 return const_iterator(*findNode(akey));
896}
897
898template <class Key, class T>
899Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::find(const Key &akey)
900{
901 detach();
902 return iterator(*findNode(akey));
903}
904
905template <class Key, class T>
906Q_INLINE_TEMPLATE bool QHash<Key, T>::contains(const Key &akey) const
907{
908 return *findNode(akey) != e;
909}
910
911template <class Key, class T>
912Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey, uint h) const
913{
914 Node **node;
915
916 if (d->numBuckets) {
917 node = reinterpret_cast<Node **>(&d->buckets[h % d->numBuckets]);
918 Q_ASSERT(*node == e || (*node)->next);
919 while (*node != e && !(*node)->same_key(h, akey))
920 node = &(*node)->next;
921 } else {
922 node = const_cast<Node **>(reinterpret_cast<const Node * const *>(&e));
923 }
924 return node;
925}
926
927template <class Key, class T>
928Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey,
929 uint *ahp) const
930{
931 uint h = 0;
932
933 if (d->numBuckets || ahp) {
934 h = qHash(akey, d->seed);
935 if (ahp)
936 *ahp = h;
937 }
938 return findNode(akey, h);
939}
940
941template <class Key, class T>
942Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash &other) const
943{
944 if (size() != other.size())
945 return false;
946 if (d == other.d)
947 return true;
948
949 const_iterator it = begin();
950
951 while (it != end()) {
952 // Build two equal ranges for i.key(); one for *this and one for other.
953 // For *this we can avoid a lookup via equal_range, as we know the beginning of the range.
954 auto thisEqualRangeEnd = it;
955 while (thisEqualRangeEnd != end() && it.key() == thisEqualRangeEnd.key())
956 ++thisEqualRangeEnd;
957
958 const auto otherEqualRange = other.equal_range(it.key());
959
960 if (std::distance(it, thisEqualRangeEnd) != std::distance(otherEqualRange.first, otherEqualRange.second))
961 return false;
962
963 // Keys in the ranges are equal by construction; this checks only the values.
964 //
965 // When using the 3-arg std::is_permutation, MSVC will emit warning C4996,
966 // passing an unchecked iterator to a Standard Library algorithm. We don't
967 // want to suppress the warning, and we can't use stdext::make_checked_array_iterator
968 // because QHash::(const_)iterator does not work with size_t and thus will
969 // emit more warnings. Use the 4-arg std::is_permutation instead (which
970 // is supported since MSVC 2015).
971 //
972 // ### Qt 6: if C++14 library support is a mandated minimum, remove the ifdef for MSVC.
973 if (!std::is_permutation(it, thisEqualRangeEnd, otherEqualRange.first
974#ifdef Q_CC_MSVC
975 , otherEqualRange.second
976#endif
977 )) {
978 return false;
979 }
980
981 it = thisEqualRangeEnd;
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 Q_DECL_NOTHROW
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() Q_DECL_NOTHROW {}
1024#ifdef Q_COMPILER_INITIALIZER_LISTS
1025 inline QMultiHash(std::initializer_list<std::pair<Key,T> > list)
1026 {
1027 this->reserve(int(list.size()));
1028 for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
1029 insert(it->first, it->second);
1030 }
1031#endif
1032 // compiler-generated copy/move ctors/assignment operators are fine!
1033 // compiler-generated destructor is fine!
1034
1035 QMultiHash(const QHash<Key, T> &other) : QHash<Key, T>(other) {}
1036#ifdef Q_COMPILER_RVALUE_REFS
1037 QMultiHash(QHash<Key, T> &&other) Q_DECL_NOTHROW : QHash<Key, T>(std::move(other)) {}
1038#endif
1039 void swap(QMultiHash &other) Q_DECL_NOTHROW { QHash<Key, T>::swap(other); } // prevent QMultiHash<->QHash swaps
1040
1041 inline typename QHash<Key, T>::iterator replace(const Key &key, const T &value)
1042 { return QHash<Key, T>::insert(key, value); }
1043
1044 inline typename QHash<Key, T>::iterator insert(const Key &key, const T &value)
1045 { return QHash<Key, T>::insertMulti(key, value); }
1046
1047 inline QMultiHash &operator+=(const QMultiHash &other)
1048 { this->unite(other); return *this; }
1049 inline QMultiHash operator+(const QMultiHash &other) const
1050 { QMultiHash result = *this; result += other; return result; }
1051
1052 using QHash<Key, T>::contains;
1053 using QHash<Key, T>::remove;
1054 using QHash<Key, T>::count;
1055 using QHash<Key, T>::find;
1056 using QHash<Key, T>::constFind;
1057
1058 bool contains(const Key &key, const T &value) const;
1059
1060 int remove(const Key &key, const T &value);
1061
1062 int count(const Key &key, const T &value) const;
1063
1064 typename QHash<Key, T>::iterator find(const Key &key, const T &value) {
1065 typename QHash<Key, T>::iterator i(find(key));
1066 typename QHash<Key, T>::iterator end(this->end());
1067 while (i != end && i.key() == key) {
1068 if (i.value() == value)
1069 return i;
1070 ++i;
1071 }
1072 return end;
1073 }
1074 typename QHash<Key, T>::const_iterator find(const Key &key, const T &value) const {
1075 typename QHash<Key, T>::const_iterator i(constFind(key));
1076 typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
1077 while (i != end && i.key() == key) {
1078 if (i.value() == value)
1079 return i;
1080 ++i;
1081 }
1082 return end;
1083 }
1084 typename QHash<Key, T>::const_iterator constFind(const Key &key, const T &value) const
1085 { return find(key, value); }
1086private:
1087 T &operator[](const Key &key);
1088 const T operator[](const Key &key) const;
1089};
1090
1091template <class Key, class T>
1092Q_INLINE_TEMPLATE bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const
1093{
1094 return constFind(key, value) != QHash<Key, T>::constEnd();
1095}
1096
1097template <class Key, class T>
1098Q_INLINE_TEMPLATE int QMultiHash<Key, T>::remove(const Key &key, const T &value)
1099{
1100 int n = 0;
1101 typename QHash<Key, T>::iterator i(find(key));
1102 typename QHash<Key, T>::iterator end(QHash<Key, T>::end());
1103 while (i != end && i.key() == key) {
1104 if (i.value() == value) {
1105 i = this->erase(i);
1106 ++n;
1107 } else {
1108 ++i;
1109 }
1110 }
1111 return n;
1112}
1113
1114template <class Key, class T>
1115Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value) const
1116{
1117 int n = 0;
1118 typename QHash<Key, T>::const_iterator i(constFind(key));
1119 typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
1120 while (i != end && i.key() == key) {
1121 if (i.value() == value)
1122 ++n;
1123 ++i;
1124 }
1125 return n;
1126}
1127
1128Q_DECLARE_ASSOCIATIVE_ITERATOR(Hash)
1129Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Hash)
1130
1131template <class Key, class T>
1132uint qHash(const QHash<Key, T> &key, uint seed = 0)
1133 Q_DECL_NOEXCEPT_EXPR(noexcept(qHash(std::declval<Key&>())) && noexcept(qHash(std::declval<T&>())))
1134{
1135 QtPrivate::QHashCombineCommutative hash;
1136 for (auto it = key.begin(), end = key.end(); it != end; ++it) {
1137 const Key &k = it.key();
1138 const T &v = it.value();
1139 seed = hash(seed, std::pair<const Key&, const T&>(k, v));
1140 }
1141 return seed;
1142}
1143
1144template <class Key, class T>
1145inline uint qHash(const QMultiHash<Key, T> &key, uint seed = 0)
1146 Q_DECL_NOEXCEPT_EXPR(noexcept(qHash(std::declval<Key&>())) && noexcept(qHash(std::declval<T&>())))
1147{
1148 const QHash<Key, T> &key2 = key;
1149 return qHash(key2, seed);
1150}
1151
1152QT_END_NAMESPACE
1153
1154#if defined(Q_CC_MSVC)
1155#pragma warning( pop )
1156#endif
1157
1158#endif // QHASH_H
1159