source: trunk/src/corelib/tools/qhash.h@ 561

Last change on this file since 561 was 561, checked in by Dmitry A. Kuminov, 15 years ago

trunk: Merged in qt 4.6.1 sources.
File size: 30.0 KB
Line 
1/****************************************************************************
2**
3** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
4** All rights reserved.
5** Contact: Nokia Corporation ([email protected])
6**
7** This file is part of the QtCore module of the Qt Toolkit.
8**
9** $QT_BEGIN_LICENSE:LGPL$
10** Commercial Usage
11** Licensees holding valid Qt Commercial licenses may use this file in
12** accordance with the Qt Commercial License Agreement provided with the
13** Software or, alternatively, in accordance with the terms contained in
14** a written agreement between you and Nokia.
15**
16** GNU Lesser General Public License Usage
17** Alternatively, this file may be used under the terms of the GNU Lesser
18** General Public License version 2.1 as published by the Free Software
19** Foundation and appearing in the file LICENSE.LGPL included in the
20** packaging of this file. Please review the following information to
21** ensure the GNU Lesser General Public License version 2.1 requirements
22** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
23**
24** In addition, as a special exception, Nokia gives you certain additional
25** rights. These rights are described in the Nokia Qt LGPL Exception
26** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
27**
28** GNU General Public License Usage
29** Alternatively, this file may be used under the terms of the GNU
30** General Public License version 3.0 as published by the Free Software
31** Foundation and appearing in the file LICENSE.GPL included in the
32** packaging of this file. Please review the following information to
33** ensure the GNU General Public License version 3.0 requirements will be
34** met: http://www.gnu.org/copyleft/gpl.html.
35**
36** If you have questions regarding the use of this file, please contact
37** Nokia at [email protected].
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#ifndef QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
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#endif // QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
257
258template <class Key, class T>
259class QHash
260{
261 typedef QHashDummyNode<Key, T> DummyNode;
262 typedef QHashNode<Key, T> Node;
263
264 union {
265 QHashData *d;
266 QHashNode<Key, T> *e;
267 };
268
269 static inline Node *concrete(QHashData::Node *node) {
270 return reinterpret_cast<Node *>(node);
271 }
272
273#ifdef Q_ALIGNOF
274 static inline int alignOfNode() { return qMax<int>(sizeof(void*), Q_ALIGNOF(Node)); }
275 static inline int alignOfDummyNode() { return qMax<int>(sizeof(void*), Q_ALIGNOF(DummyNode)); }
276#else
277 static inline int alignOfNode() { return 0; }
278 static inline int alignOfDummyNode() { return 0; }
279#endif
280
281public:
282 inline QHash() : d(&QHashData::shared_null) { d->ref.ref(); }
283 inline QHash(const QHash<Key, T> &other) : d(other.d) { d->ref.ref(); if (!d->sharable) detach(); }
284 inline ~QHash() { if (!d->ref.deref()) freeData(d); }
285
286 QHash<Key, T> &operator=(const QHash<Key, T> &other);
287
288 bool operator==(const QHash<Key, T> &other) const;
289 inline bool operator!=(const QHash<Key, T> &other) const { return !(*this == other); }
290
291 inline int size() const { return d->size; }
292
293 inline bool isEmpty() const { return d->size == 0; }
294
295 inline int capacity() const { return d->numBuckets; }
296 void reserve(int size);
297 inline void squeeze() { reserve(1); }
298
299 inline void detach() { if (d->ref != 1) detach_helper(); }
300 inline bool isDetached() const { return d->ref == 1; }
301 inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
302
303 void clear();
304
305 int remove(const Key &key);
306 T take(const Key &key);
307
308 bool contains(const Key &key) const;
309 const Key key(const T &value) const;
310 const Key key(const T &value, const Key &defaultKey) const;
311 const T value(const Key &key) const;
312 const T value(const Key &key, const T &defaultValue) const;
313 T &operator[](const Key &key);
314 const T operator[](const Key &key) const;
315
316 QList<Key> uniqueKeys() const;
317 QList<Key> keys() const;
318 QList<Key> keys(const T &value) const;
319 QList<T> values() const;
320 QList<T> values(const Key &key) const;
321 int count(const Key &key) const;
322
323 class const_iterator;
324
325 class iterator
326 {
327 friend class const_iterator;
328 QHashData::Node *i;
329
330 public:
331 typedef std::bidirectional_iterator_tag iterator_category;
332 typedef ptrdiff_t difference_type;
333 typedef T value_type;
334 typedef T *pointer;
335 typedef T &reference;
336
337 // ### Qt 5: get rid of 'operator Node *'
338 inline operator Node *() const { return concrete(i); }
339 inline iterator() : i(0) { }
340 explicit inline iterator(void *node) : i(reinterpret_cast<QHashData::Node *>(node)) { }
341
342 inline const Key &key() const { return concrete(i)->key; }
343 inline T &value() const { return concrete(i)->value; }
344 inline T &operator*() const { return concrete(i)->value; }
345 inline T *operator->() const { return &concrete(i)->value; }
346 inline bool operator==(const iterator &o) const { return i == o.i; }
347 inline bool operator!=(const iterator &o) const { return i != o.i; }
348
349 inline iterator &operator++() {
350 i = QHashData::nextNode(i);
351 return *this;
352 }
353 inline iterator operator++(int) {
354 iterator r = *this;
355 i = QHashData::nextNode(i);
356 return r;
357 }
358 inline iterator &operator--() {
359 i = QHashData::previousNode(i);
360 return *this;
361 }
362 inline iterator operator--(int) {
363 iterator r = *this;
364 i = QHashData::previousNode(i);
365 return r;
366 }
367 inline iterator operator+(int j) const
368 { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
369 inline iterator operator-(int j) const { return operator+(-j); }
370 inline iterator &operator+=(int j) { return *this = *this + j; }
371 inline iterator &operator-=(int j) { return *this = *this - j; }
372
373 // ### Qt 5: not sure this is necessary anymore
374#ifdef QT_STRICT_ITERATORS
375 private:
376#else
377 public:
378#endif
379 inline bool operator==(const const_iterator &o) const
380 { return i == o.i; }
381 inline bool operator!=(const const_iterator &o) const
382 { return i != o.i; }
383
384 private:
385 // ### Qt 5: remove
386 inline operator bool() const { return false; }
387 };
388 friend class iterator;
389
390 class const_iterator
391 {
392 friend class iterator;
393 QHashData::Node *i;
394
395 public:
396 typedef std::bidirectional_iterator_tag iterator_category;
397 typedef ptrdiff_t difference_type;
398 typedef T value_type;
399 typedef const T *pointer;
400 typedef const T &reference;
401
402 // ### Qt 5: get rid of 'operator Node *'
403 inline operator Node *() const { return concrete(i); }
404 inline const_iterator() : i(0) { }
405 explicit inline const_iterator(void *node)
406 : i(reinterpret_cast<QHashData::Node *>(node)) { }
407#ifdef QT_STRICT_ITERATORS
408 explicit inline const_iterator(const iterator &o)
409#else
410 inline const_iterator(const iterator &o)
411#endif
412 { i = o.i; }
413
414 inline const Key &key() const { return concrete(i)->key; }
415 inline const T &value() const { return concrete(i)->value; }
416 inline const T &operator*() const { return concrete(i)->value; }
417 inline const T *operator->() const { return &concrete(i)->value; }
418 inline bool operator==(const const_iterator &o) const { return i == o.i; }
419 inline bool operator!=(const const_iterator &o) const { return i != o.i; }
420
421 inline const_iterator &operator++() {
422 i = QHashData::nextNode(i);
423 return *this;
424 }
425 inline const_iterator operator++(int) {
426 const_iterator r = *this;
427 i = QHashData::nextNode(i);
428 return r;
429 }
430 inline const_iterator &operator--() {
431 i = QHashData::previousNode(i);
432 return *this;
433 }
434 inline const_iterator operator--(int) {
435 const_iterator r = *this;
436 i = QHashData::previousNode(i);
437 return r;
438 }
439 inline const_iterator operator+(int j) const
440 { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
441 inline const_iterator operator-(int j) const { return operator+(-j); }
442 inline const_iterator &operator+=(int j) { return *this = *this + j; }
443 inline const_iterator &operator-=(int j) { return *this = *this - j; }
444
445 // ### Qt 5: not sure this is necessary anymore
446#ifdef QT_STRICT_ITERATORS
447 private:
448 inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); }
449 inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); }
450#endif
451
452 private:
453 // ### Qt 5: remove
454 inline operator bool() const { return false; }
455 };
456 friend class const_iterator;
457
458 // STL style
459 inline iterator begin() { detach(); return iterator(d->firstNode()); }
460 inline const_iterator begin() const { return const_iterator(d->firstNode()); }
461 inline const_iterator constBegin() const { return const_iterator(d->firstNode()); }
462 inline iterator end() { detach(); return iterator(e); }
463 inline const_iterator end() const { return const_iterator(e); }
464 inline const_iterator constEnd() const { return const_iterator(e); }
465 iterator erase(iterator it);
466
467 // more Qt
468 typedef iterator Iterator;
469 typedef const_iterator ConstIterator;
470 inline int count() const { return d->size; }
471 iterator find(const Key &key);
472 const_iterator find(const Key &key) const;
473 const_iterator constFind(const Key &key) const;
474 iterator insert(const Key &key, const T &value);
475 iterator insertMulti(const Key &key, const T &value);
476 QHash<Key, T> &unite(const QHash<Key, T> &other);
477
478 // STL compatibility
479 typedef T mapped_type;
480 typedef Key key_type;
481 typedef ptrdiff_t difference_type;
482 typedef int size_type;
483
484 inline bool empty() const { return isEmpty(); }
485
486#ifdef QT_QHASH_DEBUG
487 inline void dump() const { d->dump(); }
488 inline void checkSanity() const { d->checkSanity(); }
489#endif
490
491private:
492 void detach_helper();
493 void freeData(QHashData *d);
494 Node **findNode(const Key &key, uint *hp = 0) const;
495 Node *createNode(uint h, const Key &key, const T &value, Node **nextNode);
496 void deleteNode(Node *node);
497 static void deleteNode2(QHashData::Node *node);
498
499 static void duplicateNode(QHashData::Node *originalNode, void *newNode);
500};
501
502
503template <class Key, class T>
504Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(Node *node)
505{
506 deleteNode2(reinterpret_cast<QHashData::Node*>(node));
507 d->freeNode(node);
508}
509
510template <class Key, class T>
511Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode2(QHashData::Node *node)
512{
513#ifdef Q_CC_BOR
514 concrete(node)->~QHashNode<Key, T>();
515#elif defined(QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION)
516 concrete(node)->~QHashNode();
517#else
518 concrete(node)->~Node();
519#endif
520}
521
522template <class Key, class T>
523Q_INLINE_TEMPLATE void QHash<Key, T>::duplicateNode(QHashData::Node *node, void *newNode)
524{
525 Node *concreteNode = concrete(node);
526 if (QTypeInfo<T>::isDummy) {
527 (void) new (newNode) DummyNode(concreteNode->key);
528 } else {
529 (void) new (newNode) Node(concreteNode->key, concreteNode->value);
530 }
531}
532
533template <class Key, class T>
534Q_INLINE_TEMPLATE typename QHash<Key, T>::Node *
535QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anextNode)
536{
537 Node *node;
538
539 if (QTypeInfo<T>::isDummy) {
540 node = reinterpret_cast<Node *>(new (d->allocateNode(alignOfDummyNode())) DummyNode(akey));
541 } else {
542 node = new (d->allocateNode(alignOfNode())) Node(akey, avalue);
543 }
544
545 node->h = ah;
546 node->next = *anextNode;
547 *anextNode = node;
548 ++d->size;
549 return node;
550}
551
552template <class Key, class T>
553Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash<Key, T> &other)
554{
555 QHash<Key, T> copy(other);
556 const_iterator it = copy.constEnd();
557 while (it != copy.constBegin()) {
558 --it;
559 insertMulti(it.key(), it.value());
560 }
561 return *this;
562}
563
564template <class Key, class T>
565Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x)
566{
567 x->free_helper(deleteNode2);
568}
569
570template <class Key, class T>
571Q_INLINE_TEMPLATE void QHash<Key, T>::clear()
572{
573 *this = QHash<Key,T>();
574}
575
576template <class Key, class T>
577Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::detach_helper()
578{
579 QHashData *x = d->detach_helper2(duplicateNode, deleteNode2,
580 QTypeInfo<T>::isDummy ? sizeof(DummyNode) : sizeof(Node),
581 QTypeInfo<T>::isDummy ? alignOfDummyNode() : alignOfNode());
582 if (!d->ref.deref())
583 freeData(d);
584 d = x;
585}
586
587template <class Key, class T>
588Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::operator=(const QHash<Key, T> &other)
589{
590 if (d != other.d) {
591 other.d->ref.ref();
592 if (!d->ref.deref())
593 freeData(d);
594 d = other.d;
595 if (!d->sharable)
596 detach_helper();
597 }
598 return *this;
599}
600
601template <class Key, class T>
602Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey) const
603{
604 Node *node;
605 if (d->size == 0 || (node = *findNode(akey)) == e) {
606 return T();
607 } else {
608 return node->value;
609 }
610}
611
612template <class Key, class T>
613Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey, const T &adefaultValue) const
614{
615 Node *node;
616 if (d->size == 0 || (node = *findNode(akey)) == e) {
617 return adefaultValue;
618 } else {
619 return node->value;
620 }
621}
622
623template <class Key, class T>
624Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const
625{
626 QList<Key> res;
627 const_iterator i = begin();
628 if (i != end()) {
629 for (;;) {
630 const Key &aKey = i.key();
631 res.append(aKey);
632 do {
633 if (++i == end())
634 goto break_out_of_outer_loop;
635 } while (aKey == i.key());
636 }
637 }
638break_out_of_outer_loop:
639 return res;
640}
641
642template <class Key, class T>
643Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys() const
644{
645 QList<Key> res;
646 const_iterator i = begin();
647 while (i != end()) {
648 res.append(i.key());
649 ++i;
650 }
651 return res;
652}
653
654template <class Key, class T>
655Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys(const T &avalue) const
656{
657 QList<Key> res;
658 const_iterator i = begin();
659 while (i != end()) {
660 if (i.value() == avalue)
661 res.append(i.key());
662 ++i;
663 }
664 return res;
665}
666
667template <class Key, class T>
668Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue) const
669{
670 return key(avalue, Key());
671}
672
673template <class Key, class T>
674Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue, const Key &defaultValue) const
675{
676 const_iterator i = begin();
677 while (i != end()) {
678 if (i.value() == avalue)
679 return i.key();
680 ++i;
681 }
682
683 return defaultValue;
684}
685
686template <class Key, class T>
687Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values() const
688{
689 QList<T> res;
690 const_iterator i = begin();
691 while (i != end()) {
692 res.append(i.value());
693 ++i;
694 }
695 return res;
696}
697
698template <class Key, class T>
699Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const
700{
701 QList<T> res;
702 Node *node = *findNode(akey);
703 if (node != e) {