Qt 4.8
qhash.h
Go to the documentation of this file.
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 
52 
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); }
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)); }
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()); }
89 Q_CORE_EXPORT uint qHash(const QString &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 
113 {
114  struct Node {
117  };
118 
122  int size;
123  int nodeSize;
124  short userNumBits;
125  short numBits;
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 
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 
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 
195 {
196 };
197 
198 inline bool operator==(const QHashDummyValue & /* v1 */, const QHashDummyValue & /* v2 */)
199 {
200  return true;
201 }
202 
204 
205 template <class Key, class T>
207 {
211 
212  inline QHashDummyNode(const Key &key0) : key(key0) {}
213 };
214 
215 template <class Key, class T>
216 struct QHashNode
217 {
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
252 #endif
255 #undef Q_HASH_DECLARE_INT_NODES
256 
257 template <class Key, class T>
258 class QHash
259 {
262 
263  union {
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;
334 
335  public:
336  typedef std::bidirectional_iterator_tag iterator_category;
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--() {
365  return *this;
366  }
367  inline iterator operator--(int) {
368  iterator r = *this;
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 
396  {
397  friend class iterator;
399 
400  public:
401  typedef std::bidirectional_iterator_tag iterator_category;
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 
427  i = QHashData::nextNode(i);
428  return *this;
429  }
431  const_iterator r = *this;
432  i = QHashData::nextNode(i);
433  return r;
434  }
437  return *this;
438  }
440  const_iterator r = *this;
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;
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>
510 {
511  deleteNode2(reinterpret_cast<QHashData::Node*>(node));
512  d->freeNode(node);
513 }
514 
515 template <class Key, class T>
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>
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>
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>
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>
569 {
570  x->free_helper(deleteNode2);
571 }
572 
573 template <class Key, class T>
575 {
576  *this = QHash<Key,T>();
577 }
578 
579 template <class Key, class T>
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>
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>
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>
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>
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>
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>
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>
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>
733 {
734  return value(akey);
735 }
736 
737 template <class Key, class T>
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>
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 
767  (*node)->value = avalue;
768  return iterator(*node);
769 }
770 
771 template <class Key, class T>
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>
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>
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>
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>
847 {
848  detach();
849  d->rehash(-qMax(asize, 1));
850 }
851 
852 template <class Key, class T>
854 {
855  return const_iterator(*findNode(akey));
856 }
857 
858 template <class Key, class T>
860 {
861  return const_iterator(*findNode(akey));
862 }
863 
864 template <class Key, class T>
866 {
867  detach();
868  return iterator(*findNode(akey));
869 }
870 
871 template <class Key, class T>
873 {
874  return *findNode(akey) != e;
875 }
876 
877 template <class Key, class T>
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>
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:
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
945  using QHash<Key, T>::remove;
946  using QHash<Key, T>::count;
947  using QHash<Key, T>::find;
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));
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));
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));
1028  while (i != end && i.key() == key) {
1029  if (i.value() == value)
1030  ++n;
1031  ++i;
1032  }
1033  return n;
1034 }
1035 
1038 
1040 
1042 
1043 #endif // QHASH_H
The QMultiHash class is a convenience QHash subclass that provides multi-valued hashes.
Definition: qcontainerfwd.h:58
iterator operator-(int j) const
Returns an iterator to the item at j positions backward from this iterator.
Definition: qhash.h:374
double d
Definition: qnumeric_p.h:62
iterator & operator-=(int j)
Makes the iterator go back by j items.
Definition: qhash.h:376
iterator & operator++()
The prefix ++ operator (++i) advances the iterator to the next item in the hash and returns an iterat...
Definition: qhash.h:354
void setSharable(bool sharable)
Definition: qhash.h:305
The QHash::const_iterator class provides an STL-style const iterator for QHash and QMultiHash...
Definition: qhash.h:395
QBasicAtomicInt ref
Definition: qhash.h:121
QHashDummyNode * next
Definition: qhash.h:208
const_iterator begin() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: qhash.h:465
bool isDetached() const
Returns true if the hash&#39;s internal data isn&#39;t shared with any other hash object; otherwise returns f...
Definition: qhash.h:304
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
bool operator!=(const iterator &o) const
Returns true if other points to a different item than this iterator; otherwise returns false...
Definition: qhash.h:352
static int alignOfNode()
Definition: qhash.h:276
#define QT_MODULE(x)
Definition: qglobal.h:2783
void clear()
Removes all items from the hash.
Definition: qhash.h:574
QHash< Key, T >::const_iterator constFind(const Key &key, const T &value) const
Returns an iterator pointing to the item with the key and the value in the hash.
Definition: qhash.h:992
int remove(const Key &key)
Removes all the items that have the key from the hash.
Definition: qhash.h:784
int size_type
Typedef for int.
Definition: qhash.h:487
ushort unicode() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: qchar.h:251
#define QT_BEGIN_HEADER
Definition: qglobal.h:136
#define it(className, varName)
iterator & operator--()
The prefix – operator (–i) makes the preceding item current and returns an iterator pointing to the...
Definition: qhash.h:363
static Node * previousNode(Node *node)
Definition: qhash.cpp:308
void swap(QMultiHash< Key, T > &other)
Swaps hash other with this hash.
Definition: qhash.h:929
The QByteArray class provides an array of bytes.
Definition: qbytearray.h:135
T & reference
Definition: qhash.h:340
bool operator==(const const_iterator &o) const
Returns true if other points to the same item as this iterator; otherwise returns false...
Definition: qhash.h:423
Node * firstNode()
Definition: qhash.h:181
const_iterator ConstIterator
Qt-style synonym for QHash::const_iterator.
Definition: qhash.h:474
T1 first
Definition: qpair.h:65
int size
Definition: qhash.h:122
T2 second
Definition: qpair.h:66
QHashData::Node * i
Definition: qhash.h:398
static void clear(QVariant::Private *d)
Definition: qvariant.cpp:197
bool operator==(const QHashDummyValue &, const QHashDummyValue &)
Definition: qhash.h:198
short numBits
Definition: qhash.h:125
T mapped_type
Typedef for T.
Definition: qhash.h:484
void squeeze()
Reduces the size of the QHash&#39;s internal hash table to save memory.
Definition: qhash.h:301
void detach_helper()
Definition: qhash.h:580
QHashData * d
Definition: qhash.h:264
static Node * nextNode(Node *node)
Definition: qhash.cpp:285
bool operator!=(QBool b1, bool b2)
Definition: qglobal.h:2026
T & value() const
Returns a modifiable reference to the current item&#39;s value.
Definition: qhash.h:348
The QString class provides a Unicode character string.
Definition: qstring.h:83
void swap(QHash< Key, T > &other)
Swaps hash other with this hash.
Definition: qhash.h:290
int numBuckets
Definition: qhash.h:126
T take(const Key &key)
Removes the item with the key from the hash and returns the value associated with it...
Definition: qhash.h:807
The QHash class is a template class that provides a hash-table-based dictionary.
Definition: qdatastream.h:66
QHash< Key, T > & operator=(const QHash< Key, T > &other)
Assigns other to this hash and returns a reference to this hash.
Definition: qhash.h:591
const_iterator operator+(int j) const
Returns an iterator to the item at j positions forward from this iterator.
Definition: qhash.h:444
#define Q_ASSERT(cond)
Definition: qglobal.h:1823
iterator & operator+=(int j)
Advances the iterator by j items.
Definition: qhash.h:375
~QHash()
Destroys the hash.
Definition: qhash.h:283
bool contains(const Key &key) const
Returns true if the hash contains an item with the key; otherwise returns false.
Definition: qhash.h:872
iterator()
Constructs an uninitialized iterator.
Definition: qhash.h:344
std::bidirectional_iterator_tag iterator_category
Definition: qhash.h:401
QHash< Key, T >::iterator find(const Key &key, const T &value)
Returns an iterator pointing to the item with the key and value.
Definition: qhash.h:972
The QChar class provides a 16-bit Unicode character.
Definition: qchar.h:72
Node * next
Definition: qhash.h:115
bool same_key(uint h0, const Key &key0)
Definition: qhash.h:225
QHashNode(const Key &key0, const T &value0)
Definition: qhash.h:224
QStringList keys
const T value(const Key &key) const
Returns the value associated with the key.
Definition: qhash.h:606
Q_DECL_CONSTEXPR const T & qMax(const T &a, const T &b)
Definition: qglobal.h:1217
QHashDummyNode(const Key &key0)
Definition: qhash.h:212
Key key_type
Typedef for Key.
Definition: qhash.h:485
void reserve(int size)
Ensures that the QHash&#39;s internal hash table consists of at least size buckets.
Definition: qhash.h:846
#define Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(C)
Definition: qiterator.h:183
Node ** buckets
Definition: qhash.h:120
iterator insert(const Key &key, const T &value)
Inserts a new item with the key and a value of value.
Definition: qhash.h:753
Node ** findNode(const Key &key, uint *hp=0) const
Definition: qhash.h:878
bool operator!=(const QHash< Key, T > &other) const
Returns true if other is not equal to this hash; otherwise returns false.
Definition: qhash.h:293
const_iterator & operator-=(int j)
Makes the iterator go back by j items.
Definition: qhash.h:448
Key key
Definition: qhash.h:220
const Key & key() const
Returns the current item&#39;s key.
Definition: qhash.h:419
const_iterator & operator+=(int j)
Advances the iterator by j items.
Definition: qhash.h:447
uint h
Definition: qhash.h:219
unsigned char uchar
Definition: qglobal.h:994
void append(const T &t)
Inserts value at the end of the list.
Definition: qlist.h:507
QHashData::Node * i
Definition: qhash.h:333
Q_DECLARE_TYPEINFO(QHashDummyValue, Q_MOVABLE_TYPE|Q_DUMMY_TYPE)
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
qptrdiff difference_type
Typedef for ptrdiff_t.
Definition: qhash.h:486
QHash< Key, T >::const_iterator find(const Key &key, const T &value) const
Definition: qhash.h:982
static bool isEmpty(const char *str)
unsigned __int64 quint64
Definition: qglobal.h:943
QIntegerForSizeof< void * >::Signed qptrdiff
Definition: qglobal.h:987
bool contains(const Key &key, const T &value) const
Returns true if the hash contains an item with the key and value; otherwise returns false...
Definition: qhash.h:1000
short userNumBits
Definition: qhash.h:124
QMultiHash(const QHash< Key, T > &other)
Constructs a copy of other (which can be a QHash or a QMultiHash).
Definition: qhash.h:928
const_iterator()
Constructs an uninitialized iterator.
Definition: qhash.h:409
const T * pointer
Definition: qhash.h:404
bool isEmpty() const
Returns true if the hash contains no items; otherwise returns false.
Definition: qhash.h:297
const T & value() const
Returns the current item&#39;s value.
Definition: qhash.h:420
#define Q_INLINE_TEMPLATE
Definition: qglobal.h:1713
const T & operator*() const
Returns the current item&#39;s value.
Definition: qhash.h:421
unsigned int uint
Definition: qglobal.h:996
const_iterator constFind(const Key &key) const
Returns an iterator pointing to the item with the key in the hash.
Definition: qhash.h:859
const_iterator end() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: qhash.h:468
QMultiHash operator+(const QMultiHash &other) const
Returns a hash that contains all the items in this hash in addition to all the items in other...
Definition: qhash.h:939
bool operator==(const QHash< Key, T > &other) const
Returns true if other is equal to this hash; otherwise returns false.
Definition: qhash.h:898
const_iterator operator++(int)
The postfix ++ operator (i++) advances the iterator to the next item in the hash and returns an itera...
Definition: qhash.h:430
#define Q_HASH_DECLARE_INT_NODES(key_type)
Definition: qhash.h:229
void free_helper(void(*node_delete)(Node *))
Definition: qhash.cpp:264
__int64 qint64
Definition: qglobal.h:942
const Key & key() const
Returns the current item&#39;s key as a const reference.
Definition: qhash.h:347
unsigned long ulong
Definition: qglobal.h:997
const_iterator & operator++()
The prefix ++ operator (++i) advances the iterator to the next item in the hash and returns an iterat...
Definition: qhash.h:426
quint16 values[128]
static QHashData shared_null
Definition: qhash.h:151
uint qHash(char key)
Definition: qhash.h:62
#define QT_CATCH(A)
Definition: qglobal.h:1537
bool operator==(const const_iterator &o) const
Definition: qhash.h:384
const_iterator(const iterator &o)
Constructs a copy of other.
Definition: qhash.h:415
The QStringRef class provides a thin wrapper around QString substrings.
Definition: qstring.h:1099
void qSwap(T &value1, T &value2)
Definition: qglobal.h:2181
QHash(const QHash< Key, T > &other)
Constructs a copy of other.
Definition: qhash.h:282
QMultiHash & operator+=(const QMultiHash &other)
Inserts all the items in the other hash into this hash and returns a reference to this hash...
Definition: qhash.h:937
The QBitArray class provides an array of bits.
Definition: qbitarray.h:54
#define Q_DECLARE_ASSOCIATIVE_ITERATOR(C)
Definition: qiterator.h:151
const_iterator(void *node)
Definition: qhash.h:410
QHash< Key, T >::iterator insert(const Key &key, const T &value)
Inserts a new item with the key and a value of value.
Definition: qhash.h:934
const_iterator constBegin() const
Returns a const STL-style iterator pointing to the first item in the hash.
Definition: qhash.h:466
const_iterator constEnd() const
Returns a const STL-style iterator pointing to the imaginary item after the last item in the hash...
Definition: qhash.h:469
uint qHash(const QUrl &url)
Definition: qurl.h:285
uint reserved
Definition: qhash.h:129
QHashNode * next
Definition: qhash.h:218
int remove(const Key &key, const T &value)
Removes all the items that have the key and the value value from the hash.
Definition: qhash.h:1006
int size() const
Returns the number of items in the hash.
Definition: qhash.h:295
const T * operator->() const
Returns a pointer to the current item&#39;s value.
Definition: qhash.h:422
#define Q_CORE_EXPORT
Definition: qglobal.h:1449
iterator end()
Returns an STL-style iterator pointing to the imaginary item after the last item in the hash...
Definition: qhash.h:467
static Node * concrete(QHashData::Node *node)
Definition: qhash.h:268
Node * createNode(uint h, const Key &key, const T &value, Node **nextNode)
Definition: qhash.h:538
bool operator!=(const const_iterator &o) const
Definition: qhash.h:386
unsigned short ushort
Definition: qglobal.h:995
uint sharable
Definition: qhash.h:127
std::bidirectional_iterator_tag iterator_category
Definition: qhash.h:336
void detach()
Detaches this hash from any other hashes with which it may share data.
Definition: qhash.h:303
const Key key(const T &value) const
Returns the first key mapped to value.
Definition: qhash.h:674
QHashNode< Key, T > * e
Definition: qhash.h:265
QList< T > values() const
Returns a list containing all the values in the hash, in an arbitrary order.
Definition: qhash.h:693
iterator operator++(int)
The postfix ++ operator (i++) advances the iterator to the next item in the hash and returns an itera...
Definition: qhash.h:358
int key
Node * fakeNext
Definition: qhash.h:119
bool operator==(const iterator &o) const
Returns true if other points to the same item as this iterator; otherwise returns false...
Definition: qhash.h:351
The QHash::iterator class provides an STL-style non-const iterator for QHash and QMultiHash.
Definition: qhash.h:330
QHash< Key, T >::iterator replace(const Key &key, const T &value)
Inserts a new item with the key and a value of value.
Definition: qhash.h:931
bool empty() const
This function is provided for STL compatibility.
Definition: qhash.h:489
const T & reference
Definition: qhash.h:405
bool willGrow()
Definition: qhash.h:160
bool operator!=(const const_iterator &o) const
Returns true if other points to a different item than this iterator; otherwise returns false...
Definition: qhash.h:424
QHashDummyNode< Key, T > DummyNode
Definition: qhash.h:260
QList< Key > uniqueKeys() const
Returns a list containing all the keys in the map.
Definition: qhash.h:628
iterator begin()
Returns an STL-style iterator pointing to the first item in the hash.
Definition: qhash.h:464
static void deleteNode2(QHashData::Node *node)
Definition: qhash.h:516
static QString dump(const QByteArray &)
void deleteNode(Node *node)
Definition: qhash.h:509
const_iterator & operator--()
The prefix – operator (–i) makes the preceding item current and returns an iterator pointing to the...
Definition: qhash.h:435
static int alignOfDummyNode()
Definition: qhash.h:277
bool isSharedWith(const QHash< Key, T > &other) const
Definition: qhash.h:306
QMultiHash()
Constructs an empty hash.
Definition: qhash.h:927
int capacity() const
Returns the number of buckets in the QHash&#39;s internal hash table.
Definition: qhash.h:299
QHashNode(const Key &key0)
Definition: qhash.h:223
T * operator->() const
Returns a pointer to the current item&#39;s value.
Definition: qhash.h:350
iterator find(const Key &key)
Returns an iterator pointing to the item with the key in the hash.
Definition: qhash.h:865
void mightGrow()
Definition: qhash.h:154
iterator insertMulti(const Key &key, const T &value)
Inserts a new item with the key and a value of value.
Definition: qhash.h:772
T & operator*() const
Returns a modifiable reference to the current item&#39;s value.
Definition: qhash.h:349
T value
Definition: qhash.h:221
uint strictAlignment
Definition: qhash.h:128
static void duplicateNode(QHashData::Node *originalNode, void *newNode)
Definition: qhash.h:526
static const KeyPair *const end
#define Q_OUTOFLINE_TEMPLATE
Definition: qglobal.h:1710
iterator(void *node)
Definition: qhash.h:345
int count() const
Same as size().
Definition: qhash.h:475
#define QT_END_HEADER
Definition: qglobal.h:137
const_iterator operator--(int)
The postfix – operator (i–) makes the preceding item current and returns an iterator pointing to th...
Definition: qhash.h:439
T & operator[](const Key &key)
Returns the value associated with the key as a modifiable reference.
Definition: qhash.h:738
#define QT_TRY
Definition: qglobal.h:1536
QList< Key > keys() const
Returns a list containing all the keys in the hash, in an arbitrary order.
Definition: qhash.h:648
const_iterator operator-(int j) const
Returns an iterator to the item at j positions backward from this iterator.
Definition: qhash.h:446
iterator erase(iterator it)
Removes the (key, value) pair associated with the iterator pos from the hash, and returns an iterator...
Definition: qhash.h:827
int nodeSize
Definition: qhash.h:123
iterator Iterator
Qt-style synonym for QHash::iterator.
Definition: qhash.h:473
QHash< Key, T > & unite(const QHash< Key, T > &other)
Inserts all the items in the other hash into this hash.
Definition: qhash.h:556
void reserve(int size)
Reserve space for alloc elements.
Definition: qlist.h:496
QHash()
Constructs an empty hash.
Definition: qhash.h:281
The QList class is a template class that provides lists.
Definition: qdatastream.h:62
void hasShrunk()
Definition: qhash.h:170
QHashNode< Key, T > Node
Definition: qhash.h:261
qptrdiff difference_type
Definition: qhash.h:337
iterator operator--(int)
The postfix – operator (i–) makes the preceding item current and returns an iterator pointing to th...
Definition: qhash.h:367
void freeData(QHashData *d)
Definition: qhash.h:568
timeval operator+(const timeval &t1, const timeval &t2)
Definition: qcore_unix_p.h:126
iterator operator+(int j) const
Returns an iterator to the item at j positions forward from this iterator.
Definition: qhash.h:372
qptrdiff difference_type
Definition: qhash.h:402