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