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
51QT_BEGIN_HEADER
52
53QT_BEGIN_NAMESPACE
54
55QT_MODULE(Core)
56
57class QBitArray;
58class QByteArray;
59class QString;
60class QStringRef;
61
62inline uint qHash(char key) { return uint(key); }
63inline uint qHash(uchar key) { return uint(key); }
64inline uint qHash(signed char key) { return uint(key); }
65inline uint qHash(ushort key) { return uint(key); }
66inline uint qHash(short key) { return uint(key); }
67inline uint qHash(uint key) { return key; }
68inline uint qHash(int key) { return uint(key); }
69inline 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}
77inline uint qHash(long key) { return qHash(ulong(key)); }
78inline 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}
86inline uint qHash(qint64 key) { return qHash(quint64(key)); }
87inline uint qHash(QChar key) { return qHash(key.unicode()); }
88Q_CORE_EXPORT uint qHash(const QByteArray &key);
89Q_CORE_EXPORT uint qHash(const QString &key);
90Q_CORE_EXPORT uint qHash(const QStringRef &key);
91Q_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
97template <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
105template <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
112struct 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
154inline void QHashData::mightGrow() // ### Qt 5: eliminate
155{
156 if (size >= numBuckets)
157 rehash(numBits + 1);
158}
159
160inline bool QHashData::willGrow()
161{
162 if (size >= numBuckets) {
163 rehash(numBits + 1);
164 return true;
165 } else {
166 return false;
167 }
168}
169
170inline 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
181inline 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
194struct QHashDummyValue
195{
196};
197
198inline bool operator==(const QHashDummyValue & /* v1 */, const QHashDummyValue & /* v2 */)
199{
200 return true;
201}
202
203Q_DECLARE_TYPEINFO(QHashDummyValue, Q_MOVABLE_TYPE | Q_DUMMY_TYPE);
204
205template <class Key, class T>
206struct QHashDummyNode
207{
208 QHashDummyNode *next;
209 uint h;
210 Key key;
211
212 inline QHashDummyNode(const Key &key0) : key(key0) {}
213};
214
215template <class Key, class T>
216struct 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
250Q_HASH_DECLARE_INT_NODES(short);
251Q_HASH_DECLARE_INT_NODES(ushort);
252#endif
253Q_HASH_DECLARE_INT_NODES(int);
254Q_HASH_DECLARE_INT_NODES(uint);
255#undef Q_HASH_DECLARE_INT_NODES
256
257template <class Key, class T>
258class 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
280public:
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
496private:
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
508template <class Key, class T>
509Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(Node *node)
510{
511 deleteNode2(reinterpret_cast<QHashData::Node*>(node));
512 d->freeNode(node);
513}
514
515template <class Key, class T>
516Q_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
525template <class Key, class T>
526Q_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
536template <class Key, class T>
537Q_INLINE_TEMPLATE typename QHash<Key, T>::Node *
538QHash<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
555template <class Key, class T>
556Q_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
567template <class Key, class T>
568Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x)
569{
570 x->free_helper(deleteNode2);
571}
572
573template <class Key, class T>
574Q_INLINE_TEMPLATE void QHash<Key, T>::clear()
575{
576 *this = QHash<Key,T>();
577}
578
579template <class Key, class T>
580Q_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
590template <class Key, class T>
591Q_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
605template <class Key, class T>
606Q_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
616template <class Key, class T>
617Q_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
627template <class Key, class T>
628Q_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 }
643break_out_of_outer_loop:
644 return res;
645}
646
647template <class Key, class T>
648Q_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
660template <class Key, class T>
661Q_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
673template <class Key, class T>
674Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue) const
675{
676 return key(avalue, Key());
677}
678
679template <class Key, class T>
680Q_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
692template <class Key, class T>
693Q_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
705template <class Key, class T>
706Q_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
718template <class Key, class T>
719Q_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
731template <class Key, class T>
732Q_INLINE_TEMPLATE const T QHash<Key, T>::operator[](const Key &akey) const
733{
734 return value(akey);
735}
736
737template <class Key, class T>
738Q_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
752template <class Key, class T>
753Q_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
771template <class Key, class T>
772Q_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
783template <class Key, class T>
784Q_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
806template <class Key, class T>
807Q_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
826template <class Key, class T>
827Q_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
845template <class Key, class T>
846Q_INLINE_TEMPLATE void QHash<Key, T>::reserve(int asize)
847{
848 detach();
849 d->rehash(-qMax(asize, 1));
850}
851
852template <class Key, class T>
853Q_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
858template <class Key, class T>
859Q_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
864template <class Key, class T>
865Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::find(const Key &akey)
866{
867 detach();
868 return iterator(*findNode(akey));
869}
870
871template <class Key, class T>
872Q_INLINE_TEMPLATE bool QHash<Key, T>::contains(const Key &akey) const
873{
874 return *findNode(akey) != e;
875}
876
877template <class Key, class T>
878Q_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
897template <class Key, class T>
898Q_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
923template <class Key, class T>
924class QMultiHash : public QHash<Key, T>
925{
926public:
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); }
994private:
995 T &operator[](const Key &key);
996 const T operator[](const Key &key) const;
997};
998
999template <class Key, class T>
1000Q_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
1005template <class Key, class T>
1006Q_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
1022template <class Key, class T>
1023Q_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
1036Q_DECLARE_ASSOCIATIVE_ITERATOR(Hash)
1037Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Hash)
1038
1039QT_END_NAMESPACE
1040
1041QT_END_HEADER
1042
1043#endif // QHASH_H
1044