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 | |
60 | QT_BEGIN_NAMESPACE |
61 | |
62 | struct 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 | |
101 | inline bool QHashData::willGrow() |
102 | { |
103 | if (size >= numBuckets) { |
104 | rehash(hint: numBits + 1); |
105 | return true; |
106 | } else { |
107 | return false; |
108 | } |
109 | } |
110 | |
111 | inline void QHashData::hasShrunk() |
112 | { |
113 | if (size <= (numBuckets >> 3) && numBits > userNumBits) { |
114 | QT_TRY { |
115 | rehash(hint: qMax(a: int(numBits) - 2, b: 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 | |
122 | inline 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 | |
135 | struct QHashDummyValue |
136 | { |
137 | }; |
138 | |
139 | constexpr bool operator==(const QHashDummyValue &, const QHashDummyValue &) noexcept |
140 | { |
141 | return true; |
142 | } |
143 | |
144 | Q_DECLARE_TYPEINFO(QHashDummyValue, Q_MOVABLE_TYPE | Q_DUMMY_TYPE); |
145 | |
146 | template <class Key, class T> |
147 | struct 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 | |
158 | private: |
159 | Q_DISABLE_COPY(QHashNode) |
160 | }; |
161 | |
162 | // Specialize for QHashDummyValue in order to save some memory |
163 | template <class Key> |
164 | struct 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 | |
177 | private: |
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 |
216 | Q_HASH_DECLARE_INT_NODES(short); |
217 | Q_HASH_DECLARE_INT_NODES(ushort); |
218 | #endif |
219 | Q_HASH_DECLARE_INT_NODES(int); |
220 | Q_HASH_DECLARE_INT_NODES(uint); |
221 | #undef Q_HASH_DECLARE_INT_NODES |
222 | #endif // #if 0 |
223 | |
224 | template <class Key, class T> |
225 | class 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>(a: sizeof(void*), Q_ALIGNOF(Node)); } |
239 | |
240 | public: |
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(size: 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: 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(other&: 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(size: 1); } |
290 | |
291 | inline void detach() { if (d->ref.isShared()) detach_helper(); } |
292 | inline bool isDetached() const { return !d->ref.isShared(); } |
293 | #if !defined(QT_NO_UNSHARABLE_CONTAINERS) |
294 | inline void setSharable(bool sharable) { if (!sharable) detach(); if (d != &QHashData::shared_null) d->sharable = sharable; } |
295 | #endif |
296 | bool isSharedWith(const QHash &other) const { return d == other.d; } |
297 | |
298 | void clear(); |
299 | |
300 | int remove(const Key &key); |
301 | T take(const Key &key); |
302 | |
303 | bool contains(const Key &key) const; |
304 | const Key key(const T &value) const; |
305 | const Key key(const T &value, const Key &defaultKey) const; |
306 | const T value(const Key &key) const; |
307 | const T value(const Key &key, const T &defaultValue) const; |
308 | T &operator[](const Key &key); |
309 | const T operator[](const Key &key) const; |
310 | |
311 | QList<Key> keys() const; |
312 | QList<Key> keys(const T &value) const; |
313 | QList<T> values() const; |
314 | #if QT_DEPRECATED_SINCE(5, 15) |
315 | QT_DEPRECATED_VERSION_X_5_15("Use QMultiHash for hashes storing multiple values with the same key." ) QList<Key> uniqueKeys() const; |
316 | QT_DEPRECATED_VERSION_X_5_15("Use QMultiHash for hashes storing multiple values with the same key." ) QList<T> values(const Key &key) const; |
317 | #endif |
318 | int count(const Key &key) const; |
319 | |
320 | class const_iterator; |
321 | |
322 | class iterator |
323 | { |
324 | friend class const_iterator; |
325 | friend class QHash<Key, T>; |
326 | friend class QSet<Key>; |
327 | QHashData::Node *i; |
328 | |
329 | public: |
330 | #if QT_DEPRECATED_WARNINGS_SINCE < QT_VERSION_CHECK(5, 15, 0) |
331 | typedef std::bidirectional_iterator_tag iterator_category; |
332 | #else |
333 | typedef std::forward_iterator_tag iterator_category; |
334 | #endif |
335 | typedef qptrdiff difference_type; |
336 | typedef T value_type; |
337 | typedef T *pointer; |
338 | typedef T &reference; |
339 | |
340 | inline iterator() : i(nullptr) { } |
341 | explicit inline iterator(void *node) : i(reinterpret_cast<QHashData::Node *>(node)) { } |
342 | |
343 | inline const Key &key() const { return concrete(node: i)->key; } |
344 | inline T &value() const { return concrete(node: i)->value; } |
345 | inline T &operator*() const { return concrete(node: i)->value; } |
346 | inline T *operator->() const { return &concrete(node: i)->value; } |
347 | inline bool operator==(const iterator &o) const { return i == o.i; } |
348 | inline bool operator!=(const iterator &o) const { return i != o.i; } |
349 | |
350 | inline iterator &operator++() { |
351 | i = QHashData::nextNode(node: i); |
352 | return *this; |
353 | } |
354 | inline iterator operator++(int) { |
355 | iterator r = *this; |
356 | i = QHashData::nextNode(node: i); |
357 | return r; |
358 | } |
359 | #if QT_DEPRECATED_SINCE(5, 15) |
360 | inline QT_DEPRECATED_VERSION_5_15 iterator &operator--() |
361 | { |
362 | i = QHashData::previousNode(node: i); |
363 | return *this; |
364 | } |
365 | inline QT_DEPRECATED_VERSION_5_15 iterator operator--(int) |
366 | { |
367 | iterator r = *this; |
368 | i = QHashData::previousNode(node: i); |
369 | return r; |
370 | } |
371 | inline QT_DEPRECATED_VERSION_5_15 iterator operator+(int j) const |
372 | { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; } |
373 | inline QT_DEPRECATED_VERSION_5_15 iterator operator-(int j) const { return operator+(j: -j); } |
374 | inline QT_DEPRECATED_VERSION_5_15 iterator &operator+=(int j) { return *this = *this + j; } |
375 | inline QT_DEPRECATED_VERSION_5_15 iterator &operator-=(int j) { return *this = *this - j; } |
376 | friend inline QT_DEPRECATED_VERSION_5_15 iterator operator+(int j, iterator k) { return k + j; } |
377 | #endif |
378 | |
379 | #ifndef QT_STRICT_ITERATORS |
380 | public: |
381 | inline bool operator==(const const_iterator &o) const |
382 | { return i == o.i; } |
383 | inline bool operator!=(const const_iterator &o) const |
384 | { return i != o.i; } |
385 | #endif |
386 | }; |
387 | friend class iterator; |
388 | |
389 | class const_iterator |
390 | { |
391 | friend class iterator; |
392 | friend class QHash<Key, T>; |
393 | friend class QMultiHash<Key, T>; |
394 | friend class QSet<Key>; |
395 | QHashData::Node *i; |
396 | |
397 | public: |
398 | #if QT_DEPRECATED_WARNINGS_SINCE < QT_VERSION_CHECK(5, 15, 0) |
399 | typedef std::bidirectional_iterator_tag iterator_category; |
400 | #else |
401 | typedef std::forward_iterator_tag iterator_category; |
402 | #endif |
403 | typedef qptrdiff difference_type; |
404 | typedef T value_type; |
405 | typedef const T *pointer; |
406 | typedef const T &reference; |
407 | |
408 | Q_DECL_CONSTEXPR inline const_iterator() : i(nullptr) { } |
409 | explicit inline const_iterator(void *node) |
410 | : i(reinterpret_cast<QHashData::Node *>(node)) { } |
411 | #ifdef QT_STRICT_ITERATORS |
412 | explicit inline const_iterator(const iterator &o) |
413 | #else |
414 | inline const_iterator(const iterator &o) |
415 | #endif |
416 | { i = o.i; } |
417 | |
418 | inline const Key &key() const { return concrete(node: i)->key; } |
419 | inline const T &value() const { return concrete(node: i)->value; } |
420 | inline const T &operator*() const { return concrete(node: i)->value; } |
421 | inline const T *operator->() const { return &concrete(node: i)->value; } |
422 | Q_DECL_CONSTEXPR inline bool operator==(const const_iterator &o) const { return i == o.i; } |
423 | Q_DECL_CONSTEXPR inline bool operator!=(const const_iterator &o) const { return i != o.i; } |
424 | |
425 | inline const_iterator &operator++() { |
426 | i = QHashData::nextNode(node: i); |
427 | return *this; |
428 | } |
429 | inline const_iterator operator++(int) { |
430 | const_iterator r = *this; |
431 | i = QHashData::nextNode(node: i); |
432 | return r; |
433 | } |
434 | #if QT_DEPRECATED_SINCE(5, 15) |
435 | inline QT_DEPRECATED_VERSION_5_15 const_iterator &operator--() |
436 | { |
437 | i = QHashData::previousNode(node: i); |
438 | return *this; |
439 | } |
440 | inline QT_DEPRECATED_VERSION_5_15 const_iterator operator--(int) |
441 | { |
442 | const_iterator r = *this; |
443 | i = QHashData::previousNode(node: i); |
444 | return r; |
445 | } |
446 | inline QT_DEPRECATED_VERSION_5_15 const_iterator operator+(int j) const |
447 | { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; } |
448 | inline QT_DEPRECATED_VERSION_5_15 const_iterator operator-(int j) const { return operator+(j: -j); } |
449 | inline QT_DEPRECATED_VERSION_5_15 const_iterator &operator+=(int j) { return *this = *this + j; } |
450 | inline QT_DEPRECATED_VERSION_5_15 const_iterator &operator-=(int j) { return *this = *this - j; } |
451 | friend inline QT_DEPRECATED_VERSION_5_15 const_iterator operator+(int j, const_iterator k) |
452 | { |
453 | return k + j; |
454 | } |
455 | #endif |
456 | |
457 | // ### Qt 5: not sure this is necessary anymore |
458 | #ifdef QT_STRICT_ITERATORS |
459 | private: |
460 | inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); } |
461 | inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); } |
462 | #endif |
463 | }; |
464 | friend class const_iterator; |
465 | |
466 | class key_iterator |
467 | { |
468 | const_iterator i; |
469 | |
470 | public: |
471 | typedef typename const_iterator::iterator_category iterator_category; |
472 | typedef typename const_iterator::difference_type difference_type; |
473 | typedef Key value_type; |
474 | typedef const Key *pointer; |
475 | typedef const Key &reference; |
476 | |
477 | key_iterator() = default; |
478 | explicit key_iterator(const_iterator o) : i(o) { } |
479 | |
480 | const Key &operator*() const { return i.key(); } |
481 | const Key *operator->() const { return &i.key(); } |
482 | bool operator==(key_iterator o) const { return i == o.i; } |
483 | bool operator!=(key_iterator o) const { return i != o.i; } |
484 | |
485 | inline key_iterator &operator++() { ++i; return *this; } |
486 | inline key_iterator operator++(int) { return key_iterator(i++);} |
487 | #if QT_DEPRECATED_SINCE(5, 15) |
488 | inline QT_DEPRECATED_VERSION_5_15 key_iterator &operator--() |
489 | { |
490 | --i; |
491 | return *this; |
492 | } |
493 | inline QT_DEPRECATED_VERSION_5_15 key_iterator operator--(int) { return key_iterator(i--); } |
494 | #endif |
495 | const_iterator base() const { return i; } |
496 | }; |
497 | |
498 | typedef QKeyValueIterator<const Key&, const T&, const_iterator> const_key_value_iterator; |
499 | typedef QKeyValueIterator<const Key&, T&, iterator> key_value_iterator; |
500 | |
501 | // STL style |
502 | inline iterator begin() { detach(); return iterator(d->firstNode()); } |
503 | inline const_iterator begin() const { return const_iterator(d->firstNode()); } |
504 | inline const_iterator cbegin() const { return const_iterator(d->firstNode()); } |
505 | inline const_iterator constBegin() const { return const_iterator(d->firstNode()); } |
506 | inline iterator end() { detach(); return iterator(e); } |
507 | inline const_iterator end() const { return const_iterator(e); } |
508 | inline const_iterator cend() const { return const_iterator(e); } |
509 | inline const_iterator constEnd() const { return const_iterator(e); } |
510 | inline key_iterator keyBegin() const { return key_iterator(begin()); } |
511 | inline key_iterator keyEnd() const { return key_iterator(end()); } |
512 | inline key_value_iterator keyValueBegin() { return key_value_iterator(begin()); } |
513 | inline key_value_iterator keyValueEnd() { return key_value_iterator(end()); } |
514 | inline const_key_value_iterator keyValueBegin() const { return const_key_value_iterator(begin()); } |
515 | inline const_key_value_iterator constKeyValueBegin() const { return const_key_value_iterator(begin()); } |
516 | inline const_key_value_iterator keyValueEnd() const { return const_key_value_iterator(end()); } |
517 | inline const_key_value_iterator constKeyValueEnd() const { return const_key_value_iterator(end()); } |
518 | |
519 | QPair<iterator, iterator> equal_range(const Key &key); |
520 | QPair<const_iterator, const_iterator> equal_range(const Key &key) const noexcept; |
521 | iterator erase(iterator it) { return erase(const_iterator(it.i)); } |
522 | iterator erase(const_iterator it); |
523 | |
524 | // more Qt |
525 | typedef iterator Iterator; |
526 | typedef const_iterator ConstIterator; |
527 | inline int count() const { return d->size; } |
528 | iterator find(const Key &key); |
529 | const_iterator find(const Key &key) const; |
530 | const_iterator constFind(const Key &key) const; |
531 | iterator insert(const Key &key, const T &value); |
532 | void insert(const QHash &hash); |
533 | #if QT_DEPRECATED_SINCE(5, 15) |
534 | QT_DEPRECATED_VERSION_X_5_15("Use QMultiHash for hashes storing multiple values with the same key." ) iterator insertMulti(const Key &key, const T &value); |
535 | QT_DEPRECATED_VERSION_X_5_15("Use QMultiHash for hashes storing multiple values with the same key." ) QHash &unite(const QHash &other); |
536 | #endif |
537 | |
538 | // STL compatibility |
539 | typedef T mapped_type; |
540 | typedef Key key_type; |
541 | typedef qptrdiff difference_type; |
542 | typedef int size_type; |
543 | |
544 | inline bool empty() const { return isEmpty(); } |
545 | |
546 | #ifdef QT_QHASH_DEBUG |
547 | inline void dump() const { d->dump(); } |
548 | inline void checkSanity() const { d->checkSanity(); } |
549 | #endif |
550 | |
551 | private: |
552 | void detach_helper(); |
553 | void freeData(QHashData *d); |
554 | Node **findNode(const Key &key, uint *hp = nullptr) const; |
555 | Node **findNode(const Key &key, uint h) const; |
556 | Node *createNode(uint h, const Key &key, const T &value, Node **nextNode); |
557 | void deleteNode(Node *node); |
558 | static void deleteNode2(QHashData::Node *node); |
559 | |
560 | static void duplicateNode(QHashData::Node *originalNode, void *newNode); |
561 | |
562 | bool isValidIterator(const iterator &it) const noexcept |
563 | { return isValidNode(node: it.i); } |
564 | bool isValidIterator(const const_iterator &it) const noexcept |
565 | { return isValidNode(node: it.i); } |
566 | bool isValidNode(QHashData::Node *node) const noexcept |
567 | { |
568 | #if defined(QT_DEBUG) && !defined(Q_HASH_NO_ITERATOR_DEBUG) |
569 | while (node->next) |
570 | node = node->next; |
571 | return (static_cast<void *>(node) == d); |
572 | #else |
573 | Q_UNUSED(node); |
574 | return true; |
575 | #endif |
576 | } |
577 | friend class QSet<Key>; |
578 | friend class QMultiHash<Key, T>; |
579 | }; |
580 | |
581 | |
582 | template <class Key, class T> |
583 | Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(Node *node) |
584 | { |
585 | deleteNode2(node: reinterpret_cast<QHashData::Node*>(node)); |
586 | d->freeNode(node); |
587 | } |
588 | |
589 | template <class Key, class T> |
590 | Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode2(QHashData::Node *node) |
591 | { |
592 | #ifdef Q_CC_BOR |
593 | concrete(node)->~QHashNode<Key, T>(); |
594 | #else |
595 | concrete(node)->~Node(); |
596 | #endif |
597 | } |
598 | |
599 | template <class Key, class T> |
600 | Q_INLINE_TEMPLATE void QHash<Key, T>::duplicateNode(QHashData::Node *node, void *newNode) |
601 | { |
602 | Node *concreteNode = concrete(node); |
603 | new (newNode) Node(concreteNode->key, concreteNode->value, concreteNode->h, nullptr); |
604 | } |
605 | |
606 | template <class Key, class T> |
607 | Q_INLINE_TEMPLATE typename QHash<Key, T>::Node * |
608 | QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anextNode) |
609 | { |
610 | Node *node = new (d->allocateNode(nodeAlign: alignOfNode())) Node(akey, avalue, ah, *anextNode); |
611 | *anextNode = node; |
612 | ++d->size; |
613 | return node; |
614 | } |
615 | |
616 | template <class Key, class T> |
617 | Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x) |
618 | { |
619 | x->free_helper(node_delete: deleteNode2); |
620 | } |
621 | |
622 | template <class Key, class T> |
623 | Q_INLINE_TEMPLATE void QHash<Key, T>::clear() |
624 | { |
625 | *this = QHash(); |
626 | } |
627 | |
628 | template <class Key, class T> |
629 | Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::detach_helper() |
630 | { |
631 | QHashData *x = d->detach_helper(node_duplicate: duplicateNode, node_delete: deleteNode2, nodeSize: sizeof(Node), nodeAlign: alignOfNode()); |
632 | if (!d->ref.deref()) |
633 | freeData(x: d); |
634 | d = x; |
635 | } |
636 | |
637 | template <class Key, class T> |
638 | Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::operator=(const QHash &other) |
639 | { |
640 | if (d != other.d) { |
641 | QHashData *o = other.d; |
642 | o->ref.ref(); |
643 | if (!d->ref.deref()) |
644 | freeData(x: d); |
645 | d = o; |
646 | if (!d->sharable) |
647 | detach_helper(); |
648 | } |
649 | return *this; |
650 | } |
651 | |
652 | template <class Key, class T> |
653 | Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey) const |
654 | { |
655 | Node *node; |
656 | if (d->size == 0 || (node = *findNode(akey)) == e) { |
657 | return T(); |
658 | } else { |
659 | return node->value; |
660 | } |
661 | } |
662 | |
663 | template <class Key, class T> |
664 | Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey, const T &adefaultValue) const |
665 | { |
666 | Node *node; |
667 | if (d->size == 0 || (node = *findNode(akey)) == e) { |
668 | return adefaultValue; |
669 | } else { |
670 | return node->value; |
671 | } |
672 | } |
673 | |
674 | template <class Key, class T> |
675 | Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys() const |
676 | { |
677 | QList<Key> res; |
678 | res.reserve(size()); |
679 | const_iterator i = begin(); |
680 | while (i != end()) { |
681 | res.append(i.key()); |
682 | ++i; |
683 | } |
684 | return res; |
685 | } |
686 | |
687 | template <class Key, class T> |
688 | Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys(const T &avalue) const |
689 | { |
690 | QList<Key> res; |
691 | const_iterator i = begin(); |
692 | while (i != end()) { |
693 | if (i.value() == avalue) |
694 | res.append(i.key()); |
695 | ++i; |
696 | } |
697 | return res; |
698 | } |
699 | |
700 | template <class Key, class T> |
701 | Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue) const |
702 | { |
703 | return key(avalue, Key()); |
704 | } |
705 | |
706 | template <class Key, class T> |
707 | Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue, const Key &defaultValue) const |
708 | { |
709 | const_iterator i = begin(); |
710 | while (i != end()) { |
711 | if (i.value() == avalue) |
712 | return i.key(); |
713 | ++i; |
714 | } |
715 | |
716 | return defaultValue; |
717 | } |
718 | |
719 | template <class Key, class T> |
720 | Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values() const |
721 | { |
722 | QList<T> res; |
723 | res.reserve(size()); |
724 | const_iterator i = begin(); |
725 | while (i != end()) { |
726 | res.append(i.value()); |
727 | ++i; |
728 | } |
729 | return res; |
730 | } |
731 | |
732 | template <class Key, class T> |
733 | Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::count(const Key &akey) const |
734 | { |
735 | int cnt = 0; |
736 | Node *node = *findNode(akey); |
737 | if (node != e) { |
738 | do { |
739 | ++cnt; |
740 | } while ((node = node->next) != e && node->key == akey); |
741 | } |
742 | return cnt; |
743 | } |
744 | |
745 | template <class Key, class T> |
746 | Q_INLINE_TEMPLATE const T QHash<Key, T>::operator[](const Key &akey) const |
747 | { |
748 | return value(akey); |
749 | } |
750 | |
751 | template <class Key, class T> |
752 | Q_INLINE_TEMPLATE T &QHash<Key, T>::operator[](const Key &akey) |
753 | { |
754 | detach(); |
755 | |
756 | uint h; |
757 | Node **node = findNode(akey, &h); |
758 | if (*node == e) { |
759 | if (d->willGrow()) |
760 | node = findNode(akey, h); |
761 | return createNode(ah: h, akey, avalue: T(), anextNode: node)->value; |
762 | } |
763 | return (*node)->value; |
764 | } |
765 | |
766 | template <class Key, class T> |
767 | Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &akey, |
768 | const T &avalue) |
769 | { |
770 | detach(); |
771 | |
772 | uint h; |
773 | Node **node = findNode(akey, &h); |
774 | if (*node == e) { |
775 | if (d->willGrow()) |
776 | node = findNode(akey, h); |
777 | return iterator(createNode(ah: h, akey, avalue, anextNode: node)); |
778 | } |
779 | |
780 | if (!std::is_same<T, QHashDummyValue>::value) |
781 | (*node)->value = avalue; |
782 | return iterator(*node); |
783 | } |
784 | |
785 | template <class Key, class T> |
786 | Q_INLINE_TEMPLATE void QHash<Key, T>::insert(const QHash &hash) |
787 | { |
788 | if (d == hash.d) |
789 | return; |
790 | |
791 | detach(); |
792 | |
793 | QHashData::Node *i = hash.d->firstNode(); |
794 | QHashData::Node *end = reinterpret_cast<QHashData::Node *>(hash.e); |
795 | while (i != end) { |
796 | Node *n = concrete(node: i); |
797 | Node **node = findNode(n->key, n->h); |
798 | if (*node == e) { |
799 | if (d->willGrow()) |
800 | node = findNode(n->key, n->h); |
801 | createNode(ah: n->h, akey: n->key, avalue: n->value, anextNode: node); |
802 | } else { |
803 | if (!std::is_same<T, QHashDummyValue>::value) |
804 | (*node)->value = n->value; |
805 | } |
806 | i = QHashData::nextNode(node: i); |
807 | } |
808 | } |
809 | |
810 | template <class Key, class T> |
811 | Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::remove(const Key &akey) |
812 | { |
813 | if (isEmpty()) // prevents detaching shared null |
814 | return 0; |
815 | detach(); |
816 | |
817 | int oldSize = d->size; |
818 | Node **node = findNode(akey); |
819 | if (*node != e) { |
820 | bool deleteNext = true; |
821 | do { |
822 | Node *next = (*node)->next; |
823 | deleteNext = (next != e && next->key == (*node)->key); |
824 | deleteNode(node: *node); |
825 | *node = next; |
826 | --d->size; |
827 | } while (deleteNext); |
828 | d->hasShrunk(); |
829 | } |
830 | return oldSize - d->size; |
831 | } |
832 | |
833 | template <class Key, class T> |
834 | Q_OUTOFLINE_TEMPLATE T QHash<Key, T>::take(const Key &akey) |
835 | { |
836 | if (isEmpty()) // prevents detaching shared null |
837 | return T(); |
838 | detach(); |
839 | |
840 | Node **node = findNode(akey); |
841 | if (*node != e) { |
842 | T t = std::move((*node)->value); |
843 | Node *next = (*node)->next; |
844 | deleteNode(node: *node); |
845 | *node = next; |
846 | --d->size; |
847 | d->hasShrunk(); |
848 | return t; |
849 | } |
850 | return T(); |
851 | } |
852 | |
853 | template <class Key, class T> |
854 | Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::erase(const_iterator it) |
855 | { |
856 | Q_ASSERT_X(isValidIterator(it), "QHash::erase" , "The specified iterator argument 'it' is invalid" ); |
857 | |
858 | if (it == const_iterator(e)) |
859 | return iterator(it.i); |
860 | |
861 | if (d->ref.isShared()) { |
862 | // save 'it' across the detach: |
863 | int bucketNum = (it.i->h % d->numBuckets); |
864 | const_iterator bucketIterator(*(d->buckets + bucketNum)); |
865 | int stepsFromBucketStartToIte = 0; |
866 | while (bucketIterator != it) { |
867 | ++stepsFromBucketStartToIte; |
868 | ++bucketIterator; |
869 | } |
870 | detach(); |
871 | it = const_iterator(*(d->buckets + bucketNum)); |
872 | while (stepsFromBucketStartToIte > 0) { |
873 | --stepsFromBucketStartToIte; |
874 | ++it; |
875 | } |
876 | } |
877 | |
878 | iterator ret(it.i); |
879 | ++ret; |
880 | |
881 | Node *node = concrete(node: it.i); |
882 | Node **node_ptr = reinterpret_cast<Node **>(&d->buckets[node->h % d->numBuckets]); |
883 | while (*node_ptr != node) |
884 | node_ptr = &(*node_ptr)->next; |
885 | *node_ptr = node->next; |
886 | deleteNode(node); |
887 | --d->size; |
888 | return ret; |
889 | } |
890 | |
891 | template <class Key, class T> |
892 | Q_INLINE_TEMPLATE void QHash<Key, T>::reserve(int asize) |
893 | { |
894 | detach(); |
895 | d->rehash(hint: -qMax(a: asize, b: 1)); |
896 | } |
897 | |
898 | template <class Key, class T> |
899 | Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &akey) const |
900 | { |
901 | return const_iterator(*findNode(akey)); |
902 | } |
903 | |
904 | template <class Key, class T> |
905 | Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &akey) const |
906 | { |
907 | return const_iterator(*findNode(akey)); |
908 | } |
909 | |
910 | template <class Key, class T> |
911 | Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::find(const Key &akey) |
912 | { |
913 | detach(); |
914 | return iterator(*findNode(akey)); |
915 | } |
916 | |
917 | template <class Key, class T> |
918 | Q_INLINE_TEMPLATE bool QHash<Key, T>::contains(const Key &akey) const |
919 | { |
920 | return *findNode(akey) != e; |
921 | } |
922 | |
923 | template <class Key, class T> |
924 | Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey, uint h) const |
925 | { |
926 | Node **node; |
927 | |
928 | if (d->numBuckets) { |
929 | node = reinterpret_cast<Node **>(&d->buckets[h % d->numBuckets]); |
930 | Q_ASSERT(*node == e || (*node)->next); |
931 | while (*node != e && !(*node)->same_key(h, akey)) |
932 | node = &(*node)->next; |
933 | } else { |
934 | node = const_cast<Node **>(reinterpret_cast<const Node * const *>(&e)); |
935 | } |
936 | return node; |
937 | } |
938 | |
939 | template <class Key, class T> |
940 | Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey, |
941 | uint *ahp) const |
942 | { |
943 | uint h = 0; |
944 | |
945 | if (d->numBuckets || ahp) { |
946 | h = qHash(akey, d->seed); |
947 | if (ahp) |
948 | *ahp = h; |
949 | } |
950 | return findNode(akey, h); |
951 | } |
952 | |
953 | template <class Key, class T> |
954 | Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash &other) const |
955 | { |
956 | if (d == other.d) |
957 | return true; |
958 | if (size() != other.size()) |
959 | return false; |
960 | |
961 | const_iterator it = begin(); |
962 | |
963 | while (it != end()) { |
964 | // Build two equal ranges for i.key(); one for *this and one for other. |
965 | // For *this we can avoid a lookup via equal_range, as we know the beginning of the range. |
966 | auto thisEqualRangeStart = it; |
967 | const Key &thisEqualRangeKey = it.key(); |
968 | size_type n = 0; |
969 | do { |
970 | ++it; |
971 | ++n; |
972 | } while (it != end() && it.key() == thisEqualRangeKey); |
973 | |
974 | const auto otherEqualRange = other.equal_range(thisEqualRangeKey); |
975 | |
976 | if (n != std::distance(otherEqualRange.first, otherEqualRange.second)) |
977 | return false; |
978 | |
979 | // Keys in the ranges are equal by construction; this checks only the values. |
980 | if (!qt_is_permutation(thisEqualRangeStart, it, otherEqualRange.first, otherEqualRange.second)) |
981 | return false; |
982 | } |
983 | |
984 | return true; |
985 | } |
986 | |
987 | template <class Key, class T> |
988 | QPair<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 | |
995 | template <class Key, class T> |
996 | QPair<typename QHash<Key, T>::const_iterator, typename QHash<Key, T>::const_iterator> QHash<Key, T>::equal_range(const Key &akey) const noexcept |
997 | { |
998 | Node *node = *findNode(akey); |
999 | const_iterator firstIt = const_iterator(node); |
1000 | |
1001 | if (node != e) { |
1002 | // equal keys must hash to the same value and so they all |
1003 | // end up in the same bucket. So we can use node->next, |
1004 | // which only works within a bucket, instead of (out-of-line) |
1005 | // QHashData::nextNode() |
1006 | while (node->next != e && node->next->key == akey) |
1007 | node = node->next; |
1008 | |
1009 | // 'node' may be the last node in the bucket. To produce the end iterator, we'd |
1010 | // need to enter the next bucket in this case, so we need to use |
1011 | // QHashData::nextNode() here, which, unlike node->next above, can move between |
1012 | // buckets. |
1013 | node = concrete(node: QHashData::nextNode(node: reinterpret_cast<QHashData::Node *>(node))); |
1014 | } |
1015 | |
1016 | return qMakePair(firstIt, const_iterator(node)); |
1017 | } |
1018 | |
1019 | template <class Key, class T> |
1020 | class QMultiHash : public QHash<Key, T> |
1021 | { |
1022 | public: |
1023 | QMultiHash() noexcept {} |
1024 | inline QMultiHash(std::initializer_list<std::pair<Key,T> > list) |
1025 | { |
1026 | this->reserve(int(list.size())); |
1027 | for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it) |
1028 | insert(key: it->first, value: it->second); |
1029 | } |
1030 | #ifdef Q_QDOC |
1031 | template <typename InputIterator> |
1032 | QMultiHash(InputIterator f, InputIterator l); |
1033 | #else |
1034 | template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasKeyAndValue<InputIterator> = true> |
1035 | QMultiHash(InputIterator f, InputIterator l) |
1036 | { |
1037 | QtPrivate::reserveIfForwardIterator(this, f, l); |
1038 | for (; f != l; ++f) |
1039 | insert(key: f.key(), value: f.value()); |
1040 | } |
1041 | |
1042 | template <typename InputIterator, QtPrivate::IfAssociativeIteratorHasFirstAndSecond<InputIterator> = true> |
1043 | QMultiHash(InputIterator f, InputIterator l) |
1044 | { |
1045 | QtPrivate::reserveIfForwardIterator(this, f, l); |
1046 | for (; f != l; ++f) |
1047 | insert(key: f->first, value: f->second); |
1048 | } |
1049 | #endif |
1050 | // compiler-generated copy/move ctors/assignment operators are fine! |
1051 | // compiler-generated destructor is fine! |
1052 | |
1053 | QMultiHash(const QHash<Key, T> &other) : QHash<Key, T>(other) {} |
1054 | QMultiHash(QHash<Key, T> &&other) noexcept : QHash<Key, T>(std::move(other)) {} |
1055 | void swap(QMultiHash &other) noexcept { QHash<Key, T>::swap(other); } // prevent QMultiHash<->QHash swaps |
1056 | |
1057 | inline typename QHash<Key, T>::iterator replace(const Key &key, const T &value) |
1058 | { return QHash<Key, T>::insert(key, value); } |
1059 | |
1060 | typename QHash<Key, T>::iterator insert(const Key &key, const T &value); |
1061 | |
1062 | inline QMultiHash &unite(const QMultiHash &other); |
1063 | |
1064 | inline QMultiHash &operator+=(const QMultiHash &other) |
1065 | { return unite(other); } |
1066 | inline QMultiHash operator+(const QMultiHash &other) const |
1067 | { QMultiHash result = *this; result += other; return result; } |
1068 | |
1069 | using QHash<Key, T>::contains; |
1070 | using QHash<Key, T>::remove; |
1071 | using QHash<Key, T>::count; |
1072 | using QHash<Key, T>::find; |
1073 | using QHash<Key, T>::constFind; |
1074 | using QHash<Key, T>::values; |
1075 | using QHash<Key, T>::findNode; |
1076 | using QHash<Key, T>::createNode; |
1077 | using QHash<Key, T>::concrete; |
1078 | using QHash<Key, T>::detach; |
1079 | |
1080 | using typename QHash<Key, T>::Node; |
1081 | using typename QHash<Key, T>::iterator; |
1082 | using typename QHash<Key, T>::const_iterator; |
1083 | |
1084 | bool contains(const Key &key, const T &value) const; |
1085 | |
1086 | int remove(const Key &key, const T &value); |
1087 | |
1088 | int count(const Key &key, const T &value) const; |
1089 | |
1090 | QList<Key> uniqueKeys() const; |
1091 | |
1092 | QList<T> values(const Key &akey) const; |
1093 | |
1094 | typename QHash<Key, T>::iterator find(const Key &key, const T &value) { |
1095 | typename QHash<Key, T>::iterator i(find(key)); |
1096 | typename QHash<Key, T>::iterator end(this->end()); |
1097 | while (i != end && i.key() == key) { |
1098 | if (i.value() == value) |
1099 | return i; |
1100 | ++i; |
1101 | } |
1102 | return end; |
1103 | } |
1104 | typename QHash<Key, T>::const_iterator find(const Key &key, const T &value) const { |
1105 | typename QHash<Key, T>::const_iterator i(constFind(key)); |
1106 | typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd()); |
1107 | while (i != end && i.key() == key) { |
1108 | if (i.value() == value) |
1109 | return i; |
1110 | ++i; |
1111 | } |
1112 | return end; |
1113 | } |
1114 | typename QHash<Key, T>::const_iterator constFind(const Key &key, const T &value) const |
1115 | { return find(key, value); } |
1116 | private: |
1117 | T &operator[](const Key &key); |
1118 | const T operator[](const Key &key) const; |
1119 | }; |
1120 | |
1121 | template <class Key, class T> |
1122 | Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QMultiHash<Key, T>::insert(const Key &akey, const T &avalue) |
1123 | { |
1124 | detach(); |
1125 | this->d->willGrow(); |
1126 | |
1127 | uint h; |
1128 | Node **nextNode = findNode(akey, &h); |
1129 | return iterator(createNode(h, akey, avalue, nextNode)); |
1130 | } |
1131 | |
1132 | template <class Key, class T> |
1133 | Q_INLINE_TEMPLATE QMultiHash<Key, T> &QMultiHash<Key, T>::unite(const QMultiHash &other) |
1134 | { |
1135 | if (this->d == &QHashData::shared_null) { |
1136 | *this = other; |
1137 | } else { |
1138 | #if QT_DEPRECATED_SINCE(5, 15) |
1139 | QMultiHash copy(other); |
1140 | const_iterator it = copy.constEnd(); |
1141 | while (it != copy.constBegin()) { |
1142 | it.i = QHashData::previousNode(node: it.i); |
1143 | insert(akey: it.key(), avalue: it.value()); |
1144 | } |
1145 | #else |
1146 | const QMultiHash copy(other); |
1147 | const_iterator it = copy.cbegin(); |
1148 | const const_iterator end = copy.cend(); |
1149 | while (it != end) { |
1150 | const auto rangeStart = it++; |
1151 | while (it != end && rangeStart.key() == it.key()) |
1152 | ++it; |
1153 | const qint64 last = std::distance(rangeStart, it) - 1; |
1154 | for (qint64 i = last; i >= 0; --i) { |
1155 | auto next = std::next(rangeStart, i); |
1156 | insert(next.key(), next.value()); |
1157 | } |
1158 | } |
1159 | #endif |
1160 | } |
1161 | return *this; |
1162 | } |
1163 | |
1164 | |
1165 | template <class Key, class T> |
1166 | Q_INLINE_TEMPLATE bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const |
1167 | { |
1168 | return constFind(key, value) != QHash<Key, T>::constEnd(); |
1169 | } |
1170 | |
1171 | template <class Key, class T> |
1172 | Q_INLINE_TEMPLATE int QMultiHash<Key, T>::remove(const Key &key, const T &value) |
1173 | { |
1174 | int n = 0; |
1175 | typename QHash<Key, T>::iterator i(find(key)); |
1176 | typename QHash<Key, T>::iterator end(QHash<Key, T>::end()); |
1177 | while (i != end && i.key() == key) { |
1178 | if (i.value() == value) { |
1179 | i = this->erase(i); |
1180 | ++n; |
1181 | } else { |
1182 | ++i; |
1183 | } |
1184 | } |
1185 | return n; |
1186 | } |
1187 | |
1188 | template <class Key, class T> |
1189 | Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value) const |
1190 | { |
1191 | int n = 0; |
1192 | typename QHash<Key, T>::const_iterator i(constFind(key)); |
1193 | typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd()); |
1194 | while (i != end && i.key() == key) { |
1195 | if (i.value() == value) |
1196 | ++n; |
1197 | ++i; |
1198 | } |
1199 | return n; |
1200 | } |
1201 | |
1202 | template <class Key, class T> |
1203 | Q_OUTOFLINE_TEMPLATE QList<Key> QMultiHash<Key, T>::uniqueKeys() const |
1204 | { |
1205 | QList<Key> res; |
1206 | res.reserve(QHash<Key, T>::size()); // May be too much, but assume short lifetime |
1207 | typename QHash<Key, T>::const_iterator i = QHash<Key, T>::begin(); |
1208 | if (i != QHash<Key, T>::end()) { |
1209 | for (;;) { |
1210 | const Key &aKey = i.key(); |
1211 | res.append(aKey); |
1212 | do { |
1213 | if (++i == QHash<Key, T>::end()) |
1214 | goto break_out_of_outer_loop; |
1215 | } while (aKey == i.key()); |
1216 | } |
1217 | } |
1218 | break_out_of_outer_loop: |
1219 | return res; |
1220 | } |
1221 | |
1222 | #if QT_DEPRECATED_SINCE(5, 15) |
1223 | |
1224 | template <class Key, class T> |
1225 | Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &key, const T &value) { |
1226 | return static_cast<QMultiHash<Key, T> *>(this)->insert(key, value); |
1227 | } |
1228 | |
1229 | template <class Key, class T> |
1230 | Q_OUTOFLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash &other) { |
1231 | return static_cast<QMultiHash<Key, T> *>(this)->unite(other); |
1232 | } |
1233 | |
1234 | template <class Key, class T> |
1235 | Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const |
1236 | { |
1237 | return static_cast<const QMultiHash<Key, T> *>(this)->values(akey); |
1238 | } |
1239 | |
1240 | template <class Key, class T> |
1241 | Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const |
1242 | { |
1243 | return static_cast<const QMultiHash<Key, T> *>(this)->uniqueKeys(); |
1244 | } |
1245 | #endif |
1246 | |
1247 | template <class Key, class T> |
1248 | Q_OUTOFLINE_TEMPLATE QList<T> QMultiHash<Key, T>::values(const Key &akey) const |
1249 | { |
1250 | QList<T> res; |
1251 | Node *node = *findNode(akey); |
1252 | if (node != this->e) { |
1253 | do { |
1254 | res.append(node->value); |
1255 | } while ((node = node->next) != this->e && node->key == akey); |
1256 | } |
1257 | return res; |
1258 | } |
1259 | |
1260 | #if !defined(QT_NO_JAVA_STYLE_ITERATORS) |
1261 | template <class Key, class T> |
1262 | class QHashIterator |
1263 | { |
1264 | typedef typename QHash<Key, T>::const_iterator const_iterator; |
1265 | typedef const_iterator Item; |
1266 | QHash<Key, T> c; |
1267 | const_iterator i, n; |
1268 | inline bool item_exists() const { return n != c.constEnd(); } |
1269 | |
1270 | public: |
1271 | inline QHashIterator(const QHash<Key, T> &container) |
1272 | : c(container), i(c.constBegin()), n(c.constEnd()) |
1273 | { |
1274 | } |
1275 | inline QHashIterator &operator=(const QHash<Key, T> &container) |
1276 | { |
1277 | c = container; |
1278 | i = c.constBegin(); |
1279 | n = c.constEnd(); |
1280 | return *this; |
1281 | } |
1282 | inline void toFront() |
1283 | { |
1284 | i = c.constBegin(); |
1285 | n = c.constEnd(); |
1286 | } |
1287 | inline void toBack() |
1288 | { |
1289 | i = c.constEnd(); |
1290 | n = c.constEnd(); |
1291 | } |
1292 | inline bool hasNext() const { return i != c.constEnd(); } |
1293 | inline Item next() |
1294 | { |
1295 | n = i++; |
1296 | return n; |
1297 | } |
1298 | inline Item peekNext() const { return i; } |
1299 | inline const T &value() const |
1300 | { |
1301 | Q_ASSERT(item_exists()); |
1302 | return *n; |
1303 | } |
1304 | inline const Key &key() const |
1305 | { |
1306 | Q_ASSERT(item_exists()); |
1307 | return n.key(); |
1308 | } |
1309 | inline bool findNext(const T &t) |
1310 | { |
1311 | while ((n = i) != c.constEnd()) |
1312 | if (*i++ == t) |
1313 | return true; |
1314 | return false; |
1315 | } |
1316 | #if QT_DEPRECATED_SINCE(5, 15) |
1317 | inline QT_DEPRECATED_VERSION_5_15 bool hasPrevious() const { return i != c.constBegin(); } |
1318 | inline QT_DEPRECATED_VERSION_5_15 Item previous() |
1319 | { |
1320 | n = --i; |
1321 | return n; |
1322 | } |
1323 | inline QT_DEPRECATED_VERSION_5_15 Item peekPrevious() const |
1324 | { |
1325 | const_iterator p = i; |
1326 | return --p; |
1327 | } |
1328 | inline bool QT_DEPRECATED_VERSION_5_15 findPrevious(const T &t) |
1329 | { |
1330 | while (i != c.constBegin()) |
1331 | if (*(n = --i) == t) |
1332 | return true; |
1333 | n = c.constEnd(); |
1334 | return false; |
1335 | } |
1336 | #endif |
1337 | }; |
1338 | |
1339 | template<class Key, class T> |
1340 | class QMutableHashIterator |
1341 | { |
1342 | typedef typename QHash<Key, T>::iterator iterator; |
1343 | typedef typename QHash<Key, T>::const_iterator const_iterator; |
1344 | typedef iterator Item; |
1345 | QHash<Key, T> *c; |
1346 | iterator i, n; |
1347 | inline bool item_exists() const { return const_iterator(n) != c->constEnd(); } |
1348 | |
1349 | public: |
1350 | inline QMutableHashIterator(QHash<Key, T> &container) : c(&container) |
1351 | { |
1352 | i = c->begin(); |
1353 | n = c->end(); |
1354 | } |
1355 | inline QMutableHashIterator &operator=(QHash<Key, T> &container) |
1356 | { |
1357 | c = &container; |
1358 | i = c->begin(); |
1359 | n = c->end(); |
1360 | return *this; |
1361 | } |
1362 | inline void toFront() |
1363 | { |
1364 | i = c->begin(); |
1365 | n = c->end(); |
1366 | } |
1367 | inline void toBack() |
1368 | { |
1369 | i = c->end(); |
1370 | n = c->end(); |
1371 | } |
1372 | inline bool hasNext() const { return const_iterator(i) != c->constEnd(); } |
1373 | inline Item next() |
1374 | { |
1375 | n = i++; |
1376 | return n; |
1377 | } |
1378 | inline Item peekNext() const { return i; } |
1379 | inline void remove() |
1380 | { |
1381 | if (const_iterator(n) != c->constEnd()) { |
1382 | i = c->erase(n); |
1383 | n = c->end(); |
1384 | } |
1385 | } |
1386 | inline void setValue(const T &t) |
1387 | { |
1388 | if (const_iterator(n) != c->constEnd()) |
1389 | *n = t; |
1390 | } |
1391 | inline T &value() |
1392 | { |
1393 | Q_ASSERT(item_exists()); |
1394 | return *n; |
1395 | } |
1396 | inline const T &value() const |
1397 | { |
1398 | Q_ASSERT(item_exists()); |
1399 | return *n; |
1400 | } |
1401 | inline const Key &key() const |
1402 | { |
1403 | Q_ASSERT(item_exists()); |
1404 | return n.key(); |
1405 | } |
1406 | inline bool findNext(const T &t) |
1407 | { |
1408 | while (const_iterator(n = i) != c->constEnd()) |
1409 | if (*i++ == t) |
1410 | return true; |
1411 | return false; |
1412 | } |
1413 | #if QT_DEPRECATED_SINCE(5, 15) |
1414 | inline QT_DEPRECATED_VERSION_5_15 bool hasPrevious() const { return const_iterator(i) != c->constBegin(); } |
1415 | inline QT_DEPRECATED_VERSION_5_15 Item previous() |
1416 | { |
1417 | n = --i; |
1418 | return n; |
1419 | } |
1420 | inline QT_DEPRECATED_VERSION_5_15 Item peekPrevious() const |
1421 | { |
1422 | iterator p = i; |
1423 | return --p; |
1424 | } |
1425 | inline QT_DEPRECATED_VERSION_5_15 bool findPrevious(const T &t) |
1426 | { |
1427 | while (const_iterator(i) != c->constBegin()) |
1428 | if (*(n = --i) == t) |
1429 | return true; |
1430 | n = c->end(); |
1431 | return false; |
1432 | } |
1433 | #endif |
1434 | }; |
1435 | #endif // !QT_NO_JAVA_STYLE_ITERATORS |
1436 | |
1437 | template <class Key, class T> |
1438 | uint qHash(const QHash<Key, T> &key, uint seed = 0) |
1439 | noexcept(noexcept(qHash(std::declval<Key&>())) && noexcept(qHash(std::declval<T&>()))) |
1440 | { |
1441 | QtPrivate::QHashCombineCommutative hash; |
1442 | for (auto it = key.begin(), end = key.end(); it != end; ++it) { |
1443 | const Key &k = it.key(); |
1444 | const T &v = it.value(); |
1445 | seed = hash(seed, std::pair<const Key&, const T&>(k, v)); |
1446 | } |
1447 | return seed; |
1448 | } |
1449 | |
1450 | template <class Key, class T> |
1451 | inline uint qHash(const QMultiHash<Key, T> &key, uint seed = 0) |
1452 | noexcept(noexcept(qHash(std::declval<Key&>())) && noexcept(qHash(std::declval<T&>()))) |
1453 | { |
1454 | const QHash<Key, T> &key2 = key; |
1455 | return qHash(key2, seed); |
1456 | } |
1457 | |
1458 | QT_END_NAMESPACE |
1459 | |
1460 | #if defined(Q_CC_MSVC) |
1461 | #pragma warning( pop ) |
1462 | #endif |
1463 | |
1464 | #endif // QHASH_H |
1465 | |