1 | /**************************************************************************** |
2 | ** |
3 | ** Copyright (C) 2014 Digia Plc and/or its subsidiary(-ies). |
4 | ** Contact: http://www.qt-project.org/legal |
5 | ** |
6 | ** This file is part of the QtCore module of the Qt Toolkit. |
7 | ** |
8 | ** $QT_BEGIN_LICENSE:LGPL$ |
9 | ** Commercial License Usage |
10 | ** Licensees holding valid commercial Qt licenses may use this file in |
11 | ** accordance with the commercial license agreement provided with the |
12 | ** Software or, alternatively, in accordance with the terms contained in |
13 | ** a written agreement between you and Digia. For licensing terms and |
14 | ** conditions see http://qt.digia.com/licensing. For further information |
15 | ** use the contact form at http://qt.digia.com/contact-us. |
16 | ** |
17 | ** GNU Lesser General Public License Usage |
18 | ** Alternatively, this file may be used under the terms of the GNU Lesser |
19 | ** General Public License version 2.1 as published by the Free Software |
20 | ** Foundation and appearing in the file LICENSE.LGPL included in the |
21 | ** packaging of this file. Please review the following information to |
22 | ** ensure the GNU Lesser General Public License version 2.1 requirements |
23 | ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. |
24 | ** |
25 | ** In addition, as a special exception, Digia gives you certain additional |
26 | ** rights. These rights are described in the Digia Qt LGPL Exception |
27 | ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. |
28 | ** |
29 | ** GNU General Public License Usage |
30 | ** Alternatively, this file may be used under the terms of the GNU |
31 | ** General Public License version 3.0 as published by the Free Software |
32 | ** Foundation and appearing in the file LICENSE.GPL included in the |
33 | ** packaging of this file. Please review the following information to |
34 | ** ensure the GNU General Public License version 3.0 requirements will be |
35 | ** met: http://www.gnu.org/copyleft/gpl.html. |
36 | ** |
37 | ** |
38 | ** $QT_END_LICENSE$ |
39 | ** |
40 | ****************************************************************************/ |
41 | |
42 | #ifndef QHASH_H |
43 | #define QHASH_H |
44 | |
45 | #include <QtCore/qatomic.h> |
46 | #include <QtCore/qchar.h> |
47 | #include <QtCore/qiterator.h> |
48 | #include <QtCore/qlist.h> |
49 | #include <QtCore/qpair.h> |
50 | |
51 | QT_BEGIN_HEADER |
52 | |
53 | QT_BEGIN_NAMESPACE |
54 | |
55 | QT_MODULE(Core) |
56 | |
57 | class QBitArray; |
58 | class QByteArray; |
59 | class QString; |
60 | class QStringRef; |
61 | |
62 | inline uint qHash(char key) { return uint(key); } |
63 | inline uint qHash(uchar key) { return uint(key); } |
64 | inline uint qHash(signed char key) { return uint(key); } |
65 | inline uint qHash(ushort key) { return uint(key); } |
66 | inline uint qHash(short key) { return uint(key); } |
67 | inline uint qHash(uint key) { return key; } |
68 | inline uint qHash(int key) { return uint(key); } |
69 | inline uint qHash(ulong key) |
70 | { |
71 | if (sizeof(ulong) > sizeof(uint)) { |
72 | return uint(((key >> (8 * sizeof(uint) - 1)) ^ key) & (~0U)); |
73 | } else { |
74 | return uint(key & (~0U)); |
75 | } |
76 | } |
77 | inline uint qHash(long key) { return qHash(ulong(key)); } |
78 | inline uint qHash(quint64 key) |
79 | { |
80 | if (sizeof(quint64) > sizeof(uint)) { |
81 | return uint(((key >> (8 * sizeof(uint) - 1)) ^ key) & (~0U)); |
82 | } else { |
83 | return uint(key & (~0U)); |
84 | } |
85 | } |
86 | inline uint qHash(qint64 key) { return qHash(quint64(key)); } |
87 | inline uint qHash(QChar key) { return qHash(key.unicode()); } |
88 | Q_CORE_EXPORT uint qHash(const QByteArray &key); |
89 | Q_CORE_EXPORT uint qHash(const QString &key); |
90 | Q_CORE_EXPORT uint qHash(const QStringRef &key); |
91 | Q_CORE_EXPORT uint qHash(const QBitArray &key); |
92 | |
93 | #if defined(Q_CC_MSVC) |
94 | #pragma warning( push ) |
95 | #pragma warning( disable : 4311 ) // disable pointer truncation warning |
96 | #endif |
97 | template <class T> inline uint qHash(const T *key) |
98 | { |
99 | return qHash(reinterpret_cast<quintptr>(key)); |
100 | } |
101 | #if defined(Q_CC_MSVC) |
102 | #pragma warning( pop ) |
103 | #endif |
104 | |
105 | template <typename T1, typename T2> inline uint qHash(const QPair<T1, T2> &key) |
106 | { |
107 | uint h1 = qHash(key.first); |
108 | uint h2 = qHash(key.second); |
109 | return ((h1 << 16) | (h1 >> 16)) ^ h2; |
110 | } |
111 | |
112 | struct Q_CORE_EXPORT QHashData |
113 | { |
114 | struct Node { |
115 | Node *next; |
116 | uint h; |
117 | }; |
118 | |
119 | Node *fakeNext; |
120 | Node **buckets; |
121 | QBasicAtomicInt ref; |
122 | int size; |
123 | int nodeSize; |
124 | short userNumBits; |
125 | short numBits; |
126 | int numBuckets; |
127 | uint sharable : 1; |
128 | uint strictAlignment : 1; |
129 | uint reserved : 30; |
130 | |
131 | void *allocateNode(); // ### Qt5 remove me |
132 | void *allocateNode(int nodeAlign); |
133 | void freeNode(void *node); |
134 | QHashData *detach_helper(void (*node_duplicate)(Node *, void *), int nodeSize); // ### Qt5 remove me |
135 | QHashData *detach_helper2(void (*node_duplicate)(Node *, void *), void (*node_delete)(Node *), |
136 | int nodeSize, int nodeAlign); |
137 | void mightGrow(); |
138 | bool willGrow(); |
139 | void hasShrunk(); |
140 | void rehash(int hint); |
141 | void free_helper(void (*node_delete)(Node *)); |
142 | void destroyAndFree(); // ### Qt5 remove me |
143 | Node *firstNode(); |
144 | #ifdef QT_QHASH_DEBUG |
145 | void dump(); |
146 | void checkSanity(); |
147 | #endif |
148 | static Node *nextNode(Node *node); |
149 | static Node *previousNode(Node *node); |
150 | |
151 | static QHashData shared_null; |
152 | }; |
153 | |
154 | inline void QHashData::mightGrow() // ### Qt 5: eliminate |
155 | { |
156 | if (size >= numBuckets) |
157 | rehash(numBits + 1); |
158 | } |
159 | |
160 | inline bool QHashData::willGrow() |
161 | { |
162 | if (size >= numBuckets) { |
163 | rehash(numBits + 1); |
164 | return true; |
165 | } else { |
166 | return false; |
167 | } |
168 | } |
169 | |
170 | inline void QHashData::hasShrunk() |
171 | { |
172 | if (size <= (numBuckets >> 3) && numBits > userNumBits) { |
173 | QT_TRY { |
174 | rehash(qMax(int(numBits) - 2, int(userNumBits))); |
175 | } QT_CATCH(const std::bad_alloc &) { |
176 | // ignore bad allocs - shrinking shouldn't throw. rehash is exception safe. |
177 | } |
178 | } |
179 | } |
180 | |
181 | inline QHashData::Node *QHashData::firstNode() |
182 | { |
183 | Node *e = reinterpret_cast<Node *>(this); |
184 | Node **bucket = buckets; |
185 | int n = numBuckets; |
186 | while (n--) { |
187 | if (*bucket != e) |
188 | return *bucket; |
189 | ++bucket; |
190 | } |
191 | return e; |
192 | } |
193 | |
194 | struct QHashDummyValue |
195 | { |
196 | }; |
197 | |
198 | inline bool operator==(const QHashDummyValue & /* v1 */, const QHashDummyValue & /* v2 */) |
199 | { |
200 | return true; |
201 | } |
202 | |
203 | Q_DECLARE_TYPEINFO(QHashDummyValue, Q_MOVABLE_TYPE | Q_DUMMY_TYPE); |
204 | |
205 | template <class Key, class T> |
206 | struct QHashDummyNode |
207 | { |
208 | QHashDummyNode *next; |
209 | uint h; |
210 | Key key; |
211 | |
212 | inline QHashDummyNode(const Key &key0) : key(key0) {} |
213 | }; |
214 | |
215 | template <class Key, class T> |
216 | struct QHashNode |
217 | { |
218 | QHashNode *next; |
219 | uint h; |
220 | Key key; |
221 | T value; |
222 | |
223 | inline QHashNode(const Key &key0) : key(key0) {} // ### remove in 5.0 |
224 | inline QHashNode(const Key &key0, const T &value0) : key(key0), value(value0) {} |
225 | inline bool same_key(uint h0, const Key &key0) { return h0 == h && key0 == key; } |
226 | }; |
227 | |
228 | |
229 | #define Q_HASH_DECLARE_INT_NODES(key_type) \ |
230 | template <class T> \ |
231 | struct QHashDummyNode<key_type, T> { \ |
232 | QHashDummyNode *next; \ |
233 | union { uint h; key_type key; }; \ |
234 | \ |
235 | inline QHashDummyNode(key_type /* key0 */) {} \ |
236 | }; \ |
237 | \ |
238 | template <class T> \ |
239 | struct QHashNode<key_type, T> { \ |
240 | QHashNode *next; \ |
241 | union { uint h; key_type key; }; \ |
242 | T value; \ |
243 | \ |
244 | inline QHashNode(key_type /* key0 */) {} \ |
245 | inline QHashNode(key_type /* key0 */, const T &value0) : value(value0) {} \ |
246 | inline bool same_key(uint h0, key_type) { return h0 == h; } \ |
247 | } |
248 | |
249 | #if defined(Q_BYTE_ORDER) && Q_BYTE_ORDER == Q_LITTLE_ENDIAN |
250 | Q_HASH_DECLARE_INT_NODES(short); |
251 | Q_HASH_DECLARE_INT_NODES(ushort); |
252 | #endif |
253 | Q_HASH_DECLARE_INT_NODES(int); |
254 | Q_HASH_DECLARE_INT_NODES(uint); |
255 | #undef Q_HASH_DECLARE_INT_NODES |
256 | |
257 | template <class Key, class T> |
258 | class QHash |
259 | { |
260 | typedef QHashDummyNode<Key, T> DummyNode; |
261 | typedef QHashNode<Key, T> Node; |
262 | |
263 | union { |
264 | QHashData *d; |
265 | QHashNode<Key, T> *e; |
266 | }; |
267 | |
268 | static inline Node *concrete(QHashData::Node *node) { |
269 | return reinterpret_cast<Node *>(node); |
270 | } |
271 | |
272 | #ifdef Q_ALIGNOF |
273 | static inline int alignOfNode() { return qMax<int>(sizeof(void*), Q_ALIGNOF(Node)); } |
274 | static inline int alignOfDummyNode() { return qMax<int>(sizeof(void*), Q_ALIGNOF(DummyNode)); } |
275 | #else |
276 | static inline int alignOfNode() { return 0; } |
277 | static inline int alignOfDummyNode() { return 0; } |
278 | #endif |
279 | |
280 | public: |
281 | inline QHash() : d(&QHashData::shared_null) { d->ref.ref(); } |
282 | inline QHash(const QHash<Key, T> &other) : d(other.d) { d->ref.ref(); if (!d->sharable) detach(); } |
283 | inline ~QHash() { if (!d->ref.deref()) freeData(d); } |
284 | |
285 | QHash<Key, T> &operator=(const QHash<Key, T> &other); |
286 | #ifdef Q_COMPILER_RVALUE_REFS |
287 | inline QHash<Key, T> &operator=(QHash<Key, T> &&other) |
288 | { qSwap(d, other.d); return *this; } |
289 | #endif |
290 | inline void swap(QHash<Key, T> &other) { qSwap(d, other.d); } |
291 | |
292 | bool operator==(const QHash<Key, T> &other) const; |
293 | inline bool operator!=(const QHash<Key, T> &other) const { return !(*this == other); } |
294 | |
295 | inline int size() const { return d->size; } |
296 | |
297 | inline bool isEmpty() const { return d->size == 0; } |
298 | |
299 | inline int capacity() const { return d->numBuckets; } |
300 | void reserve(int size); |
301 | inline void squeeze() { reserve(1); } |
302 | |
303 | inline void detach() { if (d->ref != 1) detach_helper(); } |
304 | inline bool isDetached() const { return d->ref == 1; } |
305 | inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; } |
306 | inline bool isSharedWith(const QHash<Key, T> &other) const { return d == other.d; } |
307 | |
308 | void clear(); |
309 | |
310 | int remove(const Key &key); |
311 | T take(const Key &key); |
312 | |
313 | bool contains(const Key &key) const; |
314 | const Key key(const T &value) const; |
315 | const Key key(const T &value, const Key &defaultKey) const; |
316 | const T value(const Key &key) const; |
317 | const T value(const Key &key, const T &defaultValue) const; |
318 | T &operator[](const Key &key); |
319 | const T operator[](const Key &key) const; |
320 | |
321 | QList<Key> uniqueKeys() const; |
322 | QList<Key> keys() const; |
323 | QList<Key> keys(const T &value) const; |
324 | QList<T> values() const; |
325 | QList<T> values(const Key &key) const; |
326 | int count(const Key &key) const; |
327 | |
328 | class const_iterator; |
329 | |
330 | class iterator |
331 | { |
332 | friend class const_iterator; |
333 | QHashData::Node *i; |
334 | |
335 | public: |
336 | typedef std::bidirectional_iterator_tag iterator_category; |
337 | typedef qptrdiff difference_type; |
338 | typedef T value_type; |
339 | typedef T *pointer; |
340 | typedef T &reference; |
341 | |
342 | // ### Qt 5: get rid of 'operator Node *' |
343 | inline operator Node *() const { return concrete(i); } |
344 | inline iterator() : i(0) { } |
345 | explicit inline iterator(void *node) : i(reinterpret_cast<QHashData::Node *>(node)) { } |
346 | |
347 | inline const Key &key() const { return concrete(i)->key; } |
348 | inline T &value() const { return concrete(i)->value; } |
349 | inline T &operator*() const { return concrete(i)->value; } |
350 | inline T *operator->() const { return &concrete(i)->value; } |
351 | inline bool operator==(const iterator &o) const { return i == o.i; } |
352 | inline bool operator!=(const iterator &o) const { return i != o.i; } |
353 | |
354 | inline iterator &operator++() { |
355 | i = QHashData::nextNode(i); |
356 | return *this; |
357 | } |
358 | inline iterator operator++(int) { |
359 | iterator r = *this; |
360 | i = QHashData::nextNode(i); |
361 | return r; |
362 | } |
363 | inline iterator &operator--() { |
364 | i = QHashData::previousNode(i); |
365 | return *this; |
366 | } |
367 | inline iterator operator--(int) { |
368 | iterator r = *this; |
369 | i = QHashData::previousNode(i); |
370 | return r; |
371 | } |
372 | inline iterator operator+(int j) const |
373 | { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; } |
374 | inline iterator operator-(int j) const { return operator+(-j); } |
375 | inline iterator &operator+=(int j) { return *this = *this + j; } |
376 | inline iterator &operator-=(int j) { return *this = *this - j; } |
377 | |
378 | // ### Qt 5: not sure this is necessary anymore |
379 | #ifdef QT_STRICT_ITERATORS |
380 | private: |
381 | #else |
382 | public: |
383 | #endif |
384 | inline bool operator==(const const_iterator &o) const |
385 | { return i == o.i; } |
386 | inline bool operator!=(const const_iterator &o) const |
387 | { return i != o.i; } |
388 | |
389 | private: |
390 | // ### Qt 5: remove |
391 | inline operator bool() const { return false; } |
392 | }; |
393 | friend class iterator; |
394 | |
395 | class const_iterator |
396 | { |
397 | friend class iterator; |
398 | QHashData::Node *i; |
399 | |
400 | public: |
401 | typedef std::bidirectional_iterator_tag iterator_category; |
402 | typedef qptrdiff difference_type; |
403 | typedef T value_type; |
404 | typedef const T *pointer; |
405 | typedef const T &reference; |
406 | |
407 | // ### Qt 5: get rid of 'operator Node *' |
408 | inline operator Node *() const { return concrete(i); } |
409 | inline const_iterator() : i(0) { } |
410 | explicit inline const_iterator(void *node) |
411 | : i(reinterpret_cast<QHashData::Node *>(node)) { } |
412 | #ifdef QT_STRICT_ITERATORS |
413 | explicit inline const_iterator(const iterator &o) |
414 | #else |
415 | inline const_iterator(const iterator &o) |
416 | #endif |
417 | { i = o.i; } |
418 | |
419 | inline const Key &key() const { return concrete(i)->key; } |
420 | inline const T &value() const { return concrete(i)->value; } |
421 | inline const T &operator*() const { return concrete(i)->value; } |
422 | inline const T *operator->() const { return &concrete(i)->value; } |
423 | inline bool operator==(const const_iterator &o) const { return i == o.i; } |
424 | inline bool operator!=(const const_iterator &o) const { return i != o.i; } |
425 | |
426 | inline const_iterator &operator++() { |
427 | i = QHashData::nextNode(i); |
428 | return *this; |
429 | } |
430 | inline const_iterator operator++(int) { |
431 | const_iterator r = *this; |
432 | i = QHashData::nextNode(i); |
433 | return r; |
434 | } |
435 | inline const_iterator &operator--() { |
436 | i = QHashData::previousNode(i); |
437 | return *this; |
438 | } |
439 | inline const_iterator operator--(int) { |
440 | const_iterator r = *this; |
441 | i = QHashData::previousNode(i); |
442 | return r; |
443 | } |
444 | inline const_iterator operator+(int j) const |
445 | { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; } |
446 | inline const_iterator operator-(int j) const { return operator+(-j); } |
447 | inline const_iterator &operator+=(int j) { return *this = *this + j; } |
448 | inline const_iterator &operator-=(int j) { return *this = *this - j; } |
449 | |
450 | // ### Qt 5: not sure this is necessary anymore |
451 | #ifdef QT_STRICT_ITERATORS |
452 | private: |
453 | inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); } |
454 | inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); } |
455 | #endif |
456 | |
457 | private: |
458 | // ### Qt 5: remove |
459 | inline operator bool() const { return false; } |
460 | }; |
461 | friend class const_iterator; |
462 | |
463 | // STL style |
464 | inline iterator begin() { detach(); return iterator(d->firstNode()); } |
465 | inline const_iterator begin() const { return const_iterator(d->firstNode()); } |
466 | inline const_iterator constBegin() const { return const_iterator(d->firstNode()); } |
467 | inline iterator end() { detach(); return iterator(e); } |
468 | inline const_iterator end() const { return const_iterator(e); } |
469 | inline const_iterator constEnd() const { return const_iterator(e); } |
470 | iterator erase(iterator it); |
471 | |
472 | // more Qt |
473 | typedef iterator Iterator; |
474 | typedef const_iterator ConstIterator; |
475 | inline int count() const { return d->size; } |
476 | iterator find(const Key &key); |
477 | const_iterator find(const Key &key) const; |
478 | const_iterator constFind(const Key &key) const; |
479 | iterator insert(const Key &key, const T &value); |
480 | iterator insertMulti(const Key &key, const T &value); |
481 | QHash<Key, T> &unite(const QHash<Key, T> &other); |
482 | |
483 | // STL compatibility |
484 | typedef T mapped_type; |
485 | typedef Key key_type; |
486 | typedef qptrdiff difference_type; |
487 | typedef int size_type; |
488 | |
489 | inline bool empty() const { return isEmpty(); } |
490 | |
491 | #ifdef QT_QHASH_DEBUG |
492 | inline void dump() const { d->dump(); } |
493 | inline void checkSanity() const { d->checkSanity(); } |
494 | #endif |
495 | |
496 | private: |
497 | void detach_helper(); |
498 | void freeData(QHashData *d); |
499 | Node **findNode(const Key &key, uint *hp = 0) const; |
500 | Node *createNode(uint h, const Key &key, const T &value, Node **nextNode); |
501 | void deleteNode(Node *node); |
502 | static void deleteNode2(QHashData::Node *node); |
503 | |
504 | static void duplicateNode(QHashData::Node *originalNode, void *newNode); |
505 | }; |
506 | |
507 | |
508 | template <class Key, class T> |
509 | Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(Node *node) |
510 | { |
511 | deleteNode2(reinterpret_cast<QHashData::Node*>(node)); |
512 | d->freeNode(node); |
513 | } |
514 | |
515 | template <class Key, class T> |
516 | Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode2(QHashData::Node *node) |
517 | { |
518 | #ifdef Q_CC_BOR |
519 | concrete(node)->~QHashNode<Key, T>(); |
520 | #else |
521 | concrete(node)->~Node(); |
522 | #endif |
523 | } |
524 | |
525 | template <class Key, class T> |
526 | Q_INLINE_TEMPLATE void QHash<Key, T>::duplicateNode(QHashData::Node *node, void *newNode) |
527 | { |
528 | Node *concreteNode = concrete(node); |
529 | if (QTypeInfo<T>::isDummy) { |
530 | (void) new (newNode) DummyNode(concreteNode->key); |
531 | } else { |
532 | (void) new (newNode) Node(concreteNode->key, concreteNode->value); |
533 | } |
534 | } |
535 | |
536 | template <class Key, class T> |
537 | Q_INLINE_TEMPLATE typename QHash<Key, T>::Node * |
538 | QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anextNode) |
539 | { |
540 | Node *node; |
541 | |
542 | if (QTypeInfo<T>::isDummy) { |
543 | node = reinterpret_cast<Node *>(new (d->allocateNode(alignOfDummyNode())) DummyNode(akey)); |
544 | } else { |
545 | node = new (d->allocateNode(alignOfNode())) Node(akey, avalue); |
546 | } |
547 | |
548 | node->h = ah; |
549 | node->next = *anextNode; |
550 | *anextNode = node; |
551 | ++d->size; |
552 | return node; |
553 | } |
554 | |
555 | template <class Key, class T> |
556 | Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash<Key, T> &other) |
557 | { |
558 | QHash<Key, T> copy(other); |
559 | const_iterator it = copy.constEnd(); |
560 | while (it != copy.constBegin()) { |
561 | --it; |
562 | insertMulti(it.key(), it.value()); |
563 | } |
564 | return *this; |
565 | } |
566 | |
567 | template <class Key, class T> |
568 | Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x) |
569 | { |
570 | x->free_helper(deleteNode2); |
571 | } |
572 | |
573 | template <class Key, class T> |
574 | Q_INLINE_TEMPLATE void QHash<Key, T>::clear() |
575 | { |
576 | *this = QHash<Key,T>(); |
577 | } |
578 | |
579 | template <class Key, class T> |
580 | Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::detach_helper() |
581 | { |
582 | QHashData *x = d->detach_helper2(duplicateNode, deleteNode2, |
583 | QTypeInfo<T>::isDummy ? sizeof(DummyNode) : sizeof(Node), |
584 | QTypeInfo<T>::isDummy ? alignOfDummyNode() : alignOfNode()); |
585 | if (!d->ref.deref()) |
586 | freeData(d); |
587 | d = x; |
588 | } |
589 | |
590 | template <class Key, class T> |
591 | Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::operator=(const QHash<Key, T> &other) |
592 | { |
593 | if (d != other.d) { |
594 | QHashData *o = other.d; |
595 | o->ref.ref(); |
596 | if (!d->ref.deref()) |
597 | freeData(d); |
598 | d = o; |
599 | if (!d->sharable) |
600 | detach_helper(); |
601 | } |
602 | return *this; |
603 | } |
604 | |
605 | template <class Key, class T> |
606 | Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey) const |
607 | { |
608 | Node *node; |
609 | if (d->size == 0 || (node = *findNode(akey)) == e) { |
610 | return T(); |
611 | } else { |
612 | return node->value; |
613 | } |
614 | } |
615 | |
616 | template <class Key, class T> |
617 | Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey, const T &adefaultValue) const |
618 | { |
619 | Node *node; |
620 | if (d->size == 0 || (node = *findNode(akey)) == e) { |
621 | return adefaultValue; |
622 | } else { |
623 | return node->value; |
624 | } |
625 | } |
626 | |
627 | template <class Key, class T> |
628 | Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const |
629 | { |
630 | QList<Key> res; |
631 | res.reserve(size()); // May be too much, but assume short lifetime |
632 | const_iterator i = begin(); |
633 | if (i != end()) { |
634 | for (;;) { |
635 | const Key &aKey = i.key(); |
636 | res.append(aKey); |
637 | do { |
638 | if (++i == end()) |
639 | goto break_out_of_outer_loop; |
640 | } while (aKey == i.key()); |
641 | } |
642 | } |
643 | break_out_of_outer_loop: |
644 | return res; |
645 | } |
646 | |
647 | template <class Key, class T> |
648 | Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys() const |
649 | { |
650 | QList<Key> res; |
651 | res.reserve(size()); |
652 | const_iterator i = begin(); |
653 | while (i != end()) { |
654 | res.append(i.key()); |
655 | ++i; |
656 | } |
657 | return res; |
658 | } |
659 | |
660 | template <class Key, class T> |
661 | Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys(const T &avalue) const |
662 | { |
663 | QList<Key> res; |
664 | const_iterator i = begin(); |
665 | while (i != end()) { |
666 | if (i.value() == avalue) |
667 | res.append(i.key()); |
668 | ++i; |
669 | } |
670 | return res; |
671 | } |
672 | |
673 | template <class Key, class T> |
674 | Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue) const |
675 | { |
676 | return key(avalue, Key()); |
677 | } |
678 | |
679 | template <class Key, class T> |
680 | Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue, const Key &defaultValue) const |
681 | { |
682 | const_iterator i = begin(); |
683 | while (i != end()) { |
684 | if (i.value() == avalue) |
685 | return i.key(); |
686 | ++i; |
687 | } |
688 | |
689 | return defaultValue; |
690 | } |
691 | |
692 | template <class Key, class T> |
693 | Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values() const |
694 | { |
695 | QList<T> res; |
696 | res.reserve(size()); |
697 | const_iterator i = begin(); |
698 | while (i != end()) { |
699 | res.append(i.value()); |
700 | ++i; |
701 | } |
702 | return res; |
703 | } |
704 | |
705 | template <class Key, class T> |
706 | Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const |
707 | { |
708 | QList<T> res; |
709 | Node *node = *findNode(akey); |
710 | if (node != e) { |
711 | do { |
712 | res.append(node->value); |
713 | } while ((node = node->next) != e && node->key == akey); |
714 | } |
715 | return res; |
716 | } |
717 | |
718 | template <class Key, class T> |
719 | Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::count(const Key &akey) const |
720 | { |
721 | int cnt = 0; |
722 | Node *node = *findNode(akey); |
723 | if (node != e) { |
724 | do { |
725 | ++cnt; |
726 | } while ((node = node->next) != e && node->key == akey); |
727 | } |
728 | return cnt; |
729 | } |
730 | |
731 | template <class Key, class T> |
732 | Q_INLINE_TEMPLATE const T QHash<Key, T>::operator[](const Key &akey) const |
733 | { |
734 | return value(akey); |
735 | } |
736 | |
737 | template <class Key, class T> |
738 | Q_INLINE_TEMPLATE T &QHash<Key, T>::operator[](const Key &akey) |
739 | { |
740 | detach(); |
741 | |
742 | uint h; |
743 | Node **node = findNode(akey, &h); |
744 | if (*node == e) { |
745 | if (d->willGrow()) |
746 | node = findNode(akey, &h); |
747 | return createNode(h, akey, T(), node)->value; |
748 | } |
749 | return (*node)->value; |
750 | } |
751 | |
752 | template <class Key, class T> |
753 | Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &akey, |
754 | const T &avalue) |
755 | { |
756 | detach(); |
757 | |
758 | uint h; |
759 | Node **node = findNode(akey, &h); |
760 | if (*node == e) { |
761 | if (d->willGrow()) |
762 | node = findNode(akey, &h); |
763 | return iterator(createNode(h, akey, avalue, node)); |
764 | } |
765 | |
766 | if (!QTypeInfo<T>::isDummy) |
767 | (*node)->value = avalue; |
768 | return iterator(*node); |
769 | } |
770 | |
771 | template <class Key, class T> |
772 | Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &akey, |
773 | const T &avalue) |
774 | { |
775 | detach(); |
776 | d->willGrow(); |
777 | |
778 | uint h; |
779 | Node **nextNode = findNode(akey, &h); |
780 | return iterator(createNode(h, akey, avalue, nextNode)); |
781 | } |
782 | |
783 | template <class Key, class T> |
784 | Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::remove(const Key &akey) |
785 | { |
786 | if (isEmpty()) // prevents detaching shared null |
787 | return 0; |
788 | detach(); |
789 | |
790 | int oldSize = d->size; |
791 | Node **node = findNode(akey); |
792 | if (*node != e) { |
793 | bool deleteNext = true; |
794 | do { |
795 | Node *next = (*node)->next; |
796 | deleteNext = (next != e && next->key == (*node)->key); |
797 | deleteNode(*node); |
798 | *node = next; |
799 | --d->size; |
800 | } while (deleteNext); |
801 | d->hasShrunk(); |
802 | } |
803 | return oldSize - d->size; |
804 | } |
805 | |
806 | template <class Key, class T> |
807 | Q_OUTOFLINE_TEMPLATE T QHash<Key, T>::take(const Key &akey) |
808 | { |
809 | if (isEmpty()) // prevents detaching shared null |
810 | return T(); |
811 | detach(); |
812 | |
813 | Node **node = findNode(akey); |
814 | if (*node != e) { |
815 | T t = (*node)->value; |
816 | Node *next = (*node)->next; |
817 | deleteNode(*node); |
818 | *node = next; |
819 | --d->size; |
820 | d->hasShrunk(); |
821 | return t; |
822 | } |
823 | return T(); |
824 | } |
825 | |
826 | template <class Key, class T> |
827 | Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::erase(iterator it) |
828 | { |
829 | if (it == iterator(e)) |
830 | return it; |
831 | |
832 | iterator ret = it; |
833 | ++ret; |
834 | |
835 | Node *node = it; |
836 | Node **node_ptr = reinterpret_cast<Node **>(&d->buckets[node->h % d->numBuckets]); |
837 | while (*node_ptr != node) |
838 | node_ptr = &(*node_ptr)->next; |
839 | *node_ptr = node->next; |
840 | deleteNode(node); |
841 | --d->size; |
842 | return ret; |
843 | } |
844 | |
845 | template <class Key, class T> |
846 | Q_INLINE_TEMPLATE void QHash<Key, T>::reserve(int asize) |
847 | { |
848 | detach(); |
849 | d->rehash(-qMax(asize, 1)); |
850 | } |
851 | |
852 | template <class Key, class T> |
853 | Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &akey) const |
854 | { |
855 | return const_iterator(*findNode(akey)); |
856 | } |
857 | |
858 | template <class Key, class T> |
859 | Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &akey) const |
860 | { |
861 | return const_iterator(*findNode(akey)); |
862 | } |
863 | |
864 | template <class Key, class T> |
865 | Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::find(const Key &akey) |
866 | { |
867 | detach(); |
868 | return iterator(*findNode(akey)); |
869 | } |
870 | |
871 | template <class Key, class T> |
872 | Q_INLINE_TEMPLATE bool QHash<Key, T>::contains(const Key &akey) const |
873 | { |
874 | return *findNode(akey) != e; |
875 | } |
876 | |
877 | template <class Key, class T> |
878 | Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey, |
879 | uint *ahp) const |
880 | { |
881 | Node **node; |
882 | uint h = qHash(akey); |
883 | |
884 | if (d->numBuckets) { |
885 | node = reinterpret_cast<Node **>(&d->buckets[h % d->numBuckets]); |
886 | Q_ASSERT(*node == e || (*node)->next); |
887 | while (*node != e && !(*node)->same_key(h, akey)) |
888 | node = &(*node)->next; |
889 | } else { |
890 | node = const_cast<Node **>(reinterpret_cast<const Node * const *>(&e)); |
891 | } |
892 | if (ahp) |
893 | *ahp = h; |
894 | return node; |
895 | } |
896 | |
897 | template <class Key, class T> |
898 | Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash<Key, T> &other) const |
899 | { |
900 | if (size() != other.size()) |
901 | return false; |
902 | if (d == other.d) |
903 | return true; |
904 | |
905 | const_iterator it = begin(); |
906 | |
907 | while (it != end()) { |
908 | const Key &akey = it.key(); |
909 | |
910 | const_iterator it2 = other.find(akey); |
911 | do { |
912 | if (it2 == other.end() || !(it2.key() == akey)) |
913 | return false; |
914 | if (!QTypeInfo<T>::isDummy && !(it.value() == it2.value())) |
915 | return false; |
916 | ++it; |
917 | ++it2; |
918 | } while (it != end() && it.key() == akey); |
919 | } |
920 | return true; |
921 | } |
922 | |
923 | template <class Key, class T> |
924 | class QMultiHash : public QHash<Key, T> |
925 | { |
926 | public: |
927 | QMultiHash() {} |
928 | QMultiHash(const QHash<Key, T> &other) : QHash<Key, T>(other) {} |
929 | inline void swap(QMultiHash<Key, T> &other) { QHash<Key, T>::swap(other); } // prevent QMultiHash<->QHash swaps |
930 | |
931 | inline typename QHash<Key, T>::iterator replace(const Key &key, const T &value) |
932 | { return QHash<Key, T>::insert(key, value); } |
933 | |
934 | inline typename QHash<Key, T>::iterator insert(const Key &key, const T &value) |
935 | { return QHash<Key, T>::insertMulti(key, value); } |
936 | |
937 | inline QMultiHash &operator+=(const QMultiHash &other) |
938 | { this->unite(other); return *this; } |
939 | inline QMultiHash operator+(const QMultiHash &other) const |
940 | { QMultiHash result = *this; result += other; return result; } |
941 | |
942 | #if !defined(Q_NO_USING_KEYWORD) && !defined(Q_CC_RVCT) |
943 | // RVCT compiler doesn't handle using-keyword right when used functions are overloaded in child class |
944 | using QHash<Key, T>::contains; |
945 | using QHash<Key, T>::remove; |
946 | using QHash<Key, T>::count; |
947 | using QHash<Key, T>::find; |
948 | using QHash<Key, T>::constFind; |
949 | #else |
950 | inline bool contains(const Key &key) const |
951 | { return QHash<Key, T>::contains(key); } |
952 | inline int remove(const Key &key) |
953 | { return QHash<Key, T>::remove(key); } |
954 | inline int count(const Key &key) const |
955 | { return QHash<Key, T>::count(key); } |
956 | inline int count() const |
957 | { return QHash<Key, T>::count(); } |
958 | inline typename QHash<Key, T>::iterator find(const Key &key) |
959 | { return QHash<Key, T>::find(key); } |
960 | inline typename QHash<Key, T>::const_iterator find(const Key &key) const |
961 | { return QHash<Key, T>::find(key); } |
962 | inline typename QHash<Key, T>::const_iterator constFind(const Key &key) const |
963 | { return QHash<Key, T>::constFind(key); } |
964 | #endif |
965 | |
966 | bool contains(const Key &key, const T &value) const; |
967 | |
968 | int remove(const Key &key, const T &value); |
969 | |
970 | int count(const Key &key, const T &value) const; |
971 | |
972 | typename QHash<Key, T>::iterator find(const Key &key, const T &value) { |
973 | typename QHash<Key, T>::iterator i(find(key)); |
974 | typename QHash<Key, T>::iterator end(this->end()); |
975 | while (i != end && i.key() == key) { |
976 | if (i.value() == value) |
977 | return i; |
978 | ++i; |
979 | } |
980 | return end; |
981 | } |
982 | typename QHash<Key, T>::const_iterator find(const Key &key, const T &value) const { |
983 | typename QHash<Key, T>::const_iterator i(constFind(key)); |
984 | typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd()); |
985 | while (i != end && i.key() == key) { |
986 | if (i.value() == value) |
987 | return i; |
988 | ++i; |
989 | } |
990 | return end; |
991 | } |
992 | typename QHash<Key, T>::const_iterator constFind(const Key &key, const T &value) const |
993 | { return find(key, value); } |
994 | private: |
995 | T &operator[](const Key &key); |
996 | const T operator[](const Key &key) const; |
997 | }; |
998 | |
999 | template <class Key, class T> |
1000 | Q_INLINE_TEMPLATE bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const |
1001 | { |
1002 | return constFind(key, value) != QHash<Key, T>::constEnd(); |
1003 | } |
1004 | |
1005 | template <class Key, class T> |
1006 | Q_INLINE_TEMPLATE int QMultiHash<Key, T>::remove(const Key &key, const T &value) |
1007 | { |
1008 | int n = 0; |
1009 | typename QHash<Key, T>::iterator i(find(key)); |
1010 | typename QHash<Key, T>::iterator end(QHash<Key, T>::end()); |
1011 | while (i != end && i.key() == key) { |
1012 | if (i.value() == value) { |
1013 | i = this->erase(i); |
1014 | ++n; |
1015 | } else { |
1016 | ++i; |
1017 | } |
1018 | } |
1019 | return n; |
1020 | } |
1021 | |
1022 | template <class Key, class T> |
1023 | Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value) const |
1024 | { |
1025 | int n = 0; |
1026 | typename QHash<Key, T>::const_iterator i(constFind(key)); |
1027 | typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd()); |
1028 | while (i != end && i.key() == key) { |
1029 | if (i.value() == value) |
1030 | ++n; |
1031 | ++i; |
1032 | } |
1033 | return n; |
1034 | } |
1035 | |
1036 | Q_DECLARE_ASSOCIATIVE_ITERATOR(Hash) |
1037 | Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Hash) |
1038 | |
1039 | QT_END_NAMESPACE |
1040 | |
1041 | QT_END_HEADER |
1042 | |
1043 | #endif // QHASH_H |
1044 | |