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