Qt 4.8
qmap.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 QMAP_H
43 #define QMAP_H
44 
45 #include <QtCore/qatomic.h>
46 #include <QtCore/qiterator.h>
47 #include <QtCore/qlist.h>
48 
49 #ifndef QT_NO_STL
50 #include <map>
51 #endif
52 
53 #include <new>
54 
56 
58 
59 QT_MODULE(Core)
60 
62 {
63  struct Node {
65  Node *forward[1];
66  };
67  enum { LastLevel = 11, Sparseness = 3 };
68 
69  QMapData *backward;
70  QMapData *forward[QMapData::LastLevel + 1];
72  int topLevel;
73  int size;
78  uint reserved : 29;
79 
80  static QMapData *createData(); // ### Qt5 remove me
81  static QMapData *createData(int alignment);
82  void continueFreeData(int offset);
83  Node *node_create(Node *update[], int offset); // ### Qt5 remove me
84  Node *node_create(Node *update[], int offset, int alignment);
85  void node_delete(Node *update[], int offset, Node *node);
86 #ifdef QT_QMAP_DEBUG
87  uint adjust_ptr(Node *node);
88  void dump();
89 #endif
90 
91  static QMapData shared_null;
92 };
93 
94 
95 /*
96  QMap uses qMapLessThanKey() to compare keys. The default
97  implementation uses operator<(). For pointer types,
98  qMapLessThanKey() casts the pointers to integers before it
99  compares them, because operator<() is undefined on pointers
100  that come from different memory blocks. (In practice, this
101  is only a problem when running a program such as
102  BoundsChecker.)
103 */
104 
105 template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2)
106 {
107  return key1 < key2;
108 }
109 
110 template <class Ptr> inline bool qMapLessThanKey(Ptr *key1, Ptr *key2)
111 {
112  Q_ASSERT(sizeof(quintptr) == sizeof(Ptr *));
113  return quintptr(key1) < quintptr(key2);
114 }
115 
116 template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)
117 {
118  Q_ASSERT(sizeof(quintptr) == sizeof(const Ptr *));
119  return quintptr(key1) < quintptr(key2);
120 }
121 
122 template <class Key, class T>
123 struct QMapNode {
125  T value;
126 
127 private:
128  // never access these members through this structure.
129  // see below
131  QMapData::Node *forward[1];
132 };
133 
134 template <class Key, class T>
136 {
138  T value;
139 
140 private:
141  // QMap::e is a pointer to QMapData::Node, which matches the member
142  // below. However, the memory allocation node in QMapData::node_create
143  // allocates sizeof(QMapPayloNode) and incorrectly calculates the offset
144  // of 'backward' below. If the alignment of QMapPayloadNode is larger
145  // than the alignment of a pointer, the 'backward' member is aligned to
146  // the end of this structure, not to 'value' above, and will occupy the
147  // tail-padding area.
148  //
149  // e.g., on a 32-bit archictecture with Key = int and
150  // sizeof(T) = alignof(T) = 8
151  // 0 4 8 12 16 20 24 byte
152  // | key | PAD | value |backward| PAD | correct layout
153  // | key | PAD | value | |backward| how it's actually used
154  // |<----- value of QMap::payload() = 20 ----->|
156 };
157 
158 template <class Key, class T>
159 class QMap
160 {
163 
164  union {
167  };
168 
169  static inline int payload() { return sizeof(PayloadNode) - sizeof(QMapData::Node *); }
170  static inline int alignment() {
171 #ifdef Q_ALIGNOF
172  return int(qMax(sizeof(void*), Q_ALIGNOF(Node)));
173 #else
174  return 0;
175 #endif
176  }
177  static inline Node *concrete(QMapData::Node *node) {
178  return reinterpret_cast<Node *>(reinterpret_cast<char *>(node) - payload());
179  }
180 
181 public:
182  inline QMap() : d(&QMapData::shared_null) { d->ref.ref(); }
183  inline QMap(const QMap<Key, T> &other) : d(other.d)
184  { d->ref.ref(); if (!d->sharable) detach(); }
185  inline ~QMap() { if (!d) return; if (!d->ref.deref()) freeData(d); }
186 
187  QMap<Key, T> &operator=(const QMap<Key, T> &other);
188 #ifdef Q_COMPILER_RVALUE_REFS
189  inline QMap<Key, T> &operator=(QMap<Key, T> &&other)
190  { qSwap(d, other.d); return *this; }
191 #endif
192  inline void swap(QMap<Key, T> &other) { qSwap(d, other.d); }
193 #ifndef QT_NO_STL
194  explicit QMap(const typename std::map<Key, T> &other);
195  std::map<Key, T> toStdMap() const;
196 #endif
197 
198  bool operator==(const QMap<Key, T> &other) const;
199  inline bool operator!=(const QMap<Key, T> &other) const { return !(*this == other); }
200 
201  inline int size() const { return d->size; }
202 
203  inline bool isEmpty() const { return d->size == 0; }
204 
205  inline void detach() { if (d->ref != 1) detach_helper(); }
206  inline bool isDetached() const { return d->ref == 1; }
207  inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
208  inline bool isSharedWith(const QMap<Key, T> &other) const { return d == other.d; }
209  inline void setInsertInOrder(bool ordered) { d->insertInOrder = ordered; }
210 
211  void clear();
212 
213  int remove(const Key &key);
214  T take(const Key &key);
215 
216  bool contains(const Key &key) const;
217  const Key key(const T &value) const;
218  const Key key(const T &value, const Key &defaultKey) const;
219  const T value(const Key &key) const;
220  const T value(const Key &key, const T &defaultValue) const;
221  T &operator[](const Key &key);
222  const T operator[](const Key &key) const;
223 
224  QList<Key> uniqueKeys() const;
225  QList<Key> keys() const;
226  QList<Key> keys(const T &value) const;
227  QList<T> values() const;
228  QList<T> values(const Key &key) const;
229  int count(const Key &key) const;
230 
231  class const_iterator;
232 
233  class iterator
234  {
235  friend class const_iterator;
237 
238  public:
239  typedef std::bidirectional_iterator_tag iterator_category;
241  typedef T value_type;
242  typedef T *pointer;
243  typedef T &reference;
244 
245  // ### Qt 5: get rid of 'operator Node *'
246  inline operator QMapData::Node *() const { return i; }
247  inline iterator() : i(0) { }
248  inline iterator(QMapData::Node *node) : i(node) { }
249 
250  inline const Key &key() const { return concrete(i)->key; }
251  inline T &value() const { return concrete(i)->value; }
252 #ifdef QT3_SUPPORT
253  inline QT3_SUPPORT T &data() const { return concrete(i)->value; }
254 #endif
255  inline T &operator*() const { return concrete(i)->value; }
256  inline T *operator->() const { return &concrete(i)->value; }
257  inline bool operator==(const iterator &o) const { return i == o.i; }
258  inline bool operator!=(const iterator &o) const { return i != o.i; }
259 
260  inline iterator &operator++() {
261  i = i->forward[0];
262  return *this;
263  }
264  inline iterator operator++(int) {
265  iterator r = *this;
266  i = i->forward[0];
267  return r;
268  }
269  inline iterator &operator--() {
270  i = i->backward;
271  return *this;
272  }
273  inline iterator operator--(int) {
274  iterator r = *this;
275  i = i->backward;
276  return r;
277  }
278  inline iterator operator+(int j) const
279  { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
280  inline iterator operator-(int j) const { return operator+(-j); }
281  inline iterator &operator+=(int j) { return *this = *this + j; }
282  inline iterator &operator-=(int j) { return *this = *this - j; }
283 
284  // ### Qt 5: not sure this is necessary anymore
285 #ifdef QT_STRICT_ITERATORS
286  private:
287 #else
288  public:
289 #endif
290  inline bool operator==(const const_iterator &o) const
291  { return i == o.i; }
292  inline bool operator!=(const const_iterator &o) const
293  { return i != o.i; }
294 
295  private:
296  // ### Qt 5: remove
297  inline operator bool() const { return false; }
298  };
299  friend class iterator;
300 
302  {
303  friend class iterator;
305 
306  public:
307  typedef std::bidirectional_iterator_tag iterator_category;
309  typedef T value_type;
310  typedef const T *pointer;
311  typedef const T &reference;
312 
313  // ### Qt 5: get rid of 'operator Node *'
314  inline operator QMapData::Node *() const { return i; }
315  inline const_iterator() : i(0) { }
316  inline const_iterator(QMapData::Node *node) : i(node) { }
317 #ifdef QT_STRICT_ITERATORS
318  explicit inline const_iterator(const iterator &o)
319 #else
320  inline const_iterator(const iterator &o)
321 #endif
322  { i = o.i; }
323 
324  inline const Key &key() const { return concrete(i)->key; }
325  inline const T &value() const { return concrete(i)->value; }
326 #ifdef QT3_SUPPORT
327  inline QT3_SUPPORT const T &data() const { return concrete(i)->value; }
328 #endif
329  inline const T &operator*() const { return concrete(i)->value; }
330  inline const T *operator->() const { return &concrete(i)->value; }
331  inline bool operator==(const const_iterator &o) const { return i == o.i; }
332  inline bool operator!=(const const_iterator &o) const { return i != o.i; }
333 
335  i = i->forward[0];
336  return *this;
337  }
339  const_iterator r = *this;
340  i = i->forward[0];
341  return r;
342  }
344  i = i->backward;
345  return *this;
346  }
348  const_iterator r = *this;
349  i = i->backward;
350  return r;
351  }
352  inline const_iterator operator+(int j) const
353  { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
354  inline const_iterator operator-(int j) const { return operator+(-j); }
355  inline const_iterator &operator+=(int j) { return *this = *this + j; }
356  inline const_iterator &operator-=(int j) { return *this = *this - j; }
357 
358  // ### Qt 5: not sure this is necessary anymore
359 #ifdef QT_STRICT_ITERATORS
360  private:
361  inline bool operator==(const iterator &o) { return operator==(const_iterator(o)); }
362  inline bool operator!=(const iterator &o) { return operator!=(const_iterator(o)); }
363 #endif
364 
365  private:
366  // ### Qt 5: remove
367  inline operator bool() const { return false; }
368  };
369  friend class const_iterator;
370 
371  // STL style
372  inline iterator begin() { detach(); return iterator(e->forward[0]); }
373  inline const_iterator begin() const { return const_iterator(e->forward[0]); }
374  inline const_iterator constBegin() const { return const_iterator(e->forward[0]); }
375  inline iterator end() {
376  detach();
377  return iterator(e);
378  }
379  inline const_iterator end() const { return const_iterator(e); }
380  inline const_iterator constEnd() const { return const_iterator(e); }
381  iterator erase(iterator it);
382 #ifdef QT3_SUPPORT
383  inline QT3_SUPPORT iterator remove(iterator it) { return erase(it); }
384  inline QT3_SUPPORT void erase(const Key &aKey) { remove(aKey); }
385 #endif
386 
387  // more Qt
388  typedef iterator Iterator;
389  typedef const_iterator ConstIterator;
390  inline int count() const { return d->size; }
391  iterator find(const Key &key);
392  const_iterator find(const Key &key) const;
393  const_iterator constFind(const Key &key) const;
394  iterator lowerBound(const Key &key);
395  const_iterator lowerBound(const Key &key) const;
396  iterator upperBound(const Key &key);
397  const_iterator upperBound(const Key &key) const;
398  iterator insert(const Key &key, const T &value);
399 #ifdef QT3_SUPPORT
400  QT3_SUPPORT iterator insert(const Key &key, const T &value, bool overwrite);
401 #endif
402  iterator insertMulti(const Key &key, const T &value);
403 #ifdef QT3_SUPPORT
404  inline QT3_SUPPORT iterator replace(const Key &aKey, const T &aValue) { return insert(aKey, aValue); }
405 #endif
406  QMap<Key, T> &unite(const QMap<Key, T> &other);
407 
408  // STL compatibility
409  typedef Key key_type;
410  typedef T mapped_type;
412  typedef int size_type;
413  inline bool empty() const { return isEmpty(); }
414 
415 #ifdef QT_QMAP_DEBUG
416  inline void dump() const { d->dump(); }
417 #endif
418 
419 private:
420  void detach_helper();
421  void freeData(QMapData *d);
422  QMapData::Node *findNode(const Key &key) const;
423  QMapData::Node *mutableFindNode(QMapData::Node *update[], const Key &key) const;
424  QMapData::Node *node_create(QMapData *d, QMapData::Node *update[], const Key &key,
425  const T &value);
426 };
427 
428 template <class Key, class T>
430 {
431  if (d != other.d) {
432  QMapData* o = other.d;
433  o->ref.ref();
434  if (!d->ref.deref())
435  freeData(d);
436  d = o;
437  if (!d->sharable)
438  detach_helper();
439  }
440  return *this;
441 }
442 
443 template <class Key, class T>
445 {
446  *this = QMap<Key, T>();
447 }
448 
449 template <class Key, class T>
451 QMap<Key, T>::node_create(QMapData *adt, QMapData::Node *aupdate[], const Key &akey, const T &avalue)
452 {
453  QMapData::Node *abstractNode = adt->node_create(aupdate, payload(), alignment());
454  QT_TRY {
455  Node *concreteNode = concrete(abstractNode);
456  new (&concreteNode->key) Key(akey);
457  QT_TRY {
458  new (&concreteNode->value) T(avalue);
459  } QT_CATCH(...) {
460  concreteNode->key.~Key();
461  QT_RETHROW;
462  }
463  } QT_CATCH(...) {
464  adt->node_delete(aupdate, payload(), abstractNode);
465  QT_RETHROW;
466  }
467 
468  // clean up the update array for further insertions
469  /*
470  for (int i = 0; i <= d->topLevel; ++i) {
471  if ( aupdate[i]==reinterpret_cast<QMapData::Node *>(adt) || aupdate[i]->forward[i] != abstractNode)
472  break;
473  aupdate[i] = abstractNode;
474  }
475 */
476 
477  return abstractNode;
478 }
479 
480 template <class Key, class T>
482 {
483  QMapData::Node *cur = e;
484  QMapData::Node *next = e;
485 
486  for (int i = d->topLevel; i >= 0; i--) {
487  while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
488  cur = next;
489  }
490 
491  if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
492  return next;
493  } else {
494  return e;
495  }
496 }
497 
498 template <class Key, class T>
499 Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey) const
500 {
501  QMapData::Node *node;
502  if (d->size == 0 || (node = findNode(akey)) == e) {
503  return T();
504  } else {
505  return concrete(node)->value;
506  }
507 }
508 
509 template <class Key, class T>
510 Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey, const T &adefaultValue) const
511 {
512  QMapData::Node *node;
513  if (d->size == 0 || (node = findNode(akey)) == e) {
514  return adefaultValue;
515  } else {
516  return concrete(node)->value;
517  }
518 }
519 
520 template <class Key, class T>
522 {
523  return value(akey);
524 }
525 
526 template <class Key, class T>
528 {
529  detach();
530 
531  QMapData::Node *update[QMapData::LastLevel + 1];
532  QMapData::Node *node = mutableFindNode(update, akey);
533  if (node == e)
534  node = node_create(d, update, akey, T());
535  return concrete(node)->value;
536 }
537 
538 template <class Key, class T>
540 {
541  int cnt = 0;
542  QMapData::Node *node = findNode(akey);
543  if (node != e) {
544  do {
545  ++cnt;
546  node = node->forward[0];
547  } while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));
548  }
549  return cnt;
550 }
551 
552 template <class Key, class T>
554 {
555  return findNode(akey) != e;
556 }
557 
558 template <class Key, class T>
560  const T &avalue)
561 {
562  detach();
563 
564  QMapData::Node *update[QMapData::LastLevel + 1];
565  QMapData::Node *node = mutableFindNode(update, akey);
566  if (node == e) {
567  node = node_create(d, update, akey, avalue);
568  } else {
569  concrete(node)->value = avalue;
570  }
571  return iterator(node);
572 }
573 
574 #ifdef QT3_SUPPORT
575 template <class Key, class T>
577  const T &avalue,
578  bool aoverwrite)
579 {
580  detach();
581 
582  QMapData::Node *update[QMapData::LastLevel + 1];
583  QMapData::Node *node = mutableFindNode(update, akey);
584  if (node == e) {
585  node = node_create(d, update, akey, avalue);
586  } else {
587  if (aoverwrite)
588  concrete(node)->value = avalue;
589  }
590  return iterator(node);
591 }
592 #endif
593 
594 template <class Key, class T>
596  const T &avalue)
597 {
598  detach();
599 
600  QMapData::Node *update[QMapData::LastLevel + 1];
601  mutableFindNode(update, akey);
602  return iterator(node_create(d, update, akey, avalue));
603 }
604 
605 template <class Key, class T>
607 {
608  return const_iterator(findNode(akey));
609 }
610 
611 template <class Key, class T>
613 {
614  return const_iterator(findNode(akey));
615 }
616 
617 template <class Key, class T>
619 {
620  detach();
621  return iterator(findNode(akey));
622 }
623 
624 template <class Key, class T>
626 {
627  QMap<Key, T> copy(other);
628  const_iterator it = copy.constEnd();
629  const const_iterator b = copy.constBegin();
630  while (it != b) {
631  --it;
632  insertMulti(it.key(), it.value());
633  }
634  return *this;
635 }
636 
637 #if defined(_MSC_VER)
638 #pragma warning(push)
639 #pragma warning(disable:4189)
640 #endif
641 template <class Key, class T>
643 {
645  QMapData *cur = x;
646  QMapData *next = cur->forward[0];
647  while (next != x) {
648  cur = next;
649  next = cur->forward[0];
650  Node *concreteNode = concrete(reinterpret_cast<QMapData::Node *>(cur));
651  concreteNode->key.~Key();
652  concreteNode->value.~T();
653  }
654  }
655  x->continueFreeData(payload());
656 }
657 #if defined(_MSC_VER)
658 #pragma warning(pop)
659 #endif
660 
661 template <class Key, class T>
663 {
664  detach();
665 
666  QMapData::Node *update[QMapData::LastLevel + 1];
667  QMapData::Node *cur = e;
668  QMapData::Node *next = e;
669  int oldSize = d->size;
670 
671  for (int i = d->topLevel; i >= 0; i--) {
672  while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
673  cur = next;
674  update[i] = cur;
675  }
676 
677  if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
678  bool deleteNext = true;
679  do {
680  cur = next;
681  next = cur->forward[0];
682  deleteNext = (next != e && !qMapLessThanKey<Key>(concrete(cur)->key, concrete(next)->key));
683  concrete(cur)->key.~Key();
684  concrete(cur)->value.~T();
685  d->node_delete(update, payload(), cur);
686  } while (deleteNext);
687  }
688  return oldSize - d->size;
689 }
690 
691 template <class Key, class T>
693 {
694  detach();
695 
696  QMapData::Node *update[QMapData::LastLevel + 1];
697  QMapData::Node *cur = e;
698  QMapData::Node *next = e;
699 
700  for (int i = d->topLevel; i >= 0; i--) {
701  while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
702  cur = next;
703  update[i] = cur;
704  }
705 
706  if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
707  T t = concrete(next)->value;
708  concrete(next)->key.~Key();
709  concrete(next)->value.~T();
710  d->node_delete(update, payload(), next);
711  return t;
712  }
713  return T();
714 }
715 
716 template <class Key, class T>
718 {
719  QMapData::Node *update[QMapData::LastLevel + 1];
720  QMapData::Node *cur = e;
721  QMapData::Node *next = e;
722 
723  if (it == iterator(e))
724  return it;
725 
726  for (int i = d->topLevel; i >= 0; i--) {
727  while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, it.key()))
728  cur = next;
729  update[i] = cur;
730  }
731 
732  while (next != e) {
733  cur = next;
734  next = cur->forward[0];
735  if (cur == it) {
736  concrete(cur)->key.~Key();
737  concrete(cur)->value.~T();
738  d->node_delete(update, payload(), cur);
739  return iterator(next);
740  }
741 
742  for (int i = 0; i <= d->topLevel; ++i) {
743  if (update[i]->forward[i] != cur)
744  break;
745  update[i] = cur;
746  }
747  }
748  return end();
749 }
750 
751 template <class Key, class T>
753 {
754  union { QMapData *d; QMapData::Node *e; } x;
755  x.d = QMapData::createData(alignment());
756  if (d->size) {
757  x.d->insertInOrder = true;
758  QMapData::Node *update[QMapData::LastLevel + 1];
759  QMapData::Node *cur = e->forward[0];
760  update[0] = x.e;
761  while (cur != e) {
762  QT_TRY {
763  Node *concreteNode = concrete(cur);
764  node_create(x.d, update, concreteNode->key, concreteNode->value);
765  } QT_CATCH(...) {
766  freeData(x.d);
767  QT_RETHROW;
768  }
769  cur = cur->forward[0];
770  }
771  x.d->insertInOrder = false;
772  }
773  if (!d->ref.deref())
774  freeData(d);
775  d = x.d;
776 }
777 
778 template <class Key, class T>
780  const Key &akey) const
781 {
782  QMapData::Node *cur = e;
783  QMapData::Node *next = e;
784 
785  for (int i = d->topLevel; i >= 0; i--) {
786  while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
787  cur = next;
788  aupdate[i] = cur;
789  }
790  if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
791  return next;
792  } else {
793  return e;
794  }
795 }
796 
797 template <class Key, class T>
799 {
800  QList<Key> res;
801  res.reserve(size()); // May be too much, but assume short lifetime
802  const_iterator i = begin();
803  if (i != end()) {
804  for (;;) {
805  const Key &aKey = i.key();
806  res.append(aKey);
807  do {
808  if (++i == end())
809  goto break_out_of_outer_loop;
810  } while (!(aKey < i.key())); // loop while (key == i.key())
811  }
812  }
813 break_out_of_outer_loop:
814  return res;
815 }
816 
817 template <class Key, class T>
819 {
820  QList<Key> res;
821  res.reserve(size());
822  const_iterator i = begin();
823  while (i != end()) {
824  res.append(i.key());
825  ++i;
826  }
827  return res;
828 }
829 
830 template <class Key, class T>
832 {
833  QList<Key> res;
834  const_iterator i = begin();
835  while (i != end()) {
836  if (i.value() == avalue)
837  res.append(i.key());
838  ++i;
839  }
840  return res;
841 }
842 
843 template <class Key, class T>
844 Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue) const
845 {
846  return key(avalue, Key());
847 }
848 
849 template <class Key, class T>
850 Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue, const Key &defaultKey) const
851 {
852  const_iterator i = begin();
853  while (i != end()) {
854  if (i.value() == avalue)
855  return i.key();
856  ++i;
857  }
858 
859  return defaultKey;
860 }
861 
862 template <class Key, class T>
864 {
865  QList<T> res;
866  res.reserve(size());
867  const_iterator i = begin();
868  while (i != end()) {
869  res.append(i.value());
870  ++i;
871  }
872  return res;
873 }
874 
875 template <class Key, class T>
877 {
878  QList<T> res;
879  QMapData::Node *node = findNode(akey);
880  if (node != e) {
881  do {
882  res.append(concrete(node)->value);
883  node = node->forward[0];
884  } while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));
885  }
886  return res;
887 }
888 
889 template <class Key, class T>
891 QMap<Key, T>::lowerBound(const Key &akey) const
892 {
893  QMapData::Node *update[QMapData::LastLevel + 1];
894  mutableFindNode(update, akey);
895  return const_iterator(update[0]->forward[0]);
896 }
897 
898 template <class Key, class T>
900 {
901  detach();
902  return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->lowerBound(akey));
903 }
904 
905 template <class Key, class T>
907 QMap<Key, T>::upperBound(const Key &akey) const
908 {
909  QMapData::Node *update[QMapData::LastLevel + 1];
910  mutableFindNode(update, akey);
911  QMapData::Node *node = update[0]->forward[0];
912  while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key))
913  node = node->forward[0];
914  return const_iterator(node);
915 }
916 
917 template <class Key, class T>
919 {
920  detach();
921  return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->upperBound(akey));
922 }
923 
924 template <class Key, class T>
926 {
927  if (size() != other.size())
928  return false;
929  if (d == other.d)
930  return true;
931 
932  const_iterator it1 = begin();
933  const_iterator it2 = other.begin();
934 
935  while (it1 != end()) {
936  if (!(it1.value() == it2.value()) || qMapLessThanKey(it1.key(), it2.key()) || qMapLessThanKey(it2.key(), it1.key()))
937  return false;
938  ++it2;
939  ++it1;
940  }
941  return true;
942 }
943 
944 #ifndef QT_NO_STL
945 template <class Key, class T>
946 Q_OUTOFLINE_TEMPLATE QMap<Key, T>::QMap(const std::map<Key, T> &other)
947 {
948  d = QMapData::createData(alignment());
949  d->insertInOrder = true;
950  typename std::map<Key,T>::const_iterator it = other.end();
951  while (it != other.begin()) {
952  --it;
953  insert((*it).first, (*it).second);
954  }
955  d->insertInOrder = false;
956 }
957 
958 template <class Key, class T>
960 {
961  std::map<Key, T> map;
962  const_iterator it = end();
963  while (it != begin()) {
964  --it;
965  map.insert(std::pair<Key, T>(it.key(), it.value()));
966  }
967  return map;
968 }
969 
970 #endif // QT_NO_STL
971 
972 template <class Key, class T>
973 class QMultiMap : public QMap<Key, T>
974 {
975 public:
977  QMultiMap(const QMap<Key, T> &other) : QMap<Key, T>(other) {}
978  inline void swap(QMultiMap<Key, T> &other) { QMap<Key, T>::swap(other); }
979 
980  inline typename QMap<Key, T>::iterator replace(const Key &key, const T &value)
981  { return QMap<Key, T>::insert(key, value); }
982  inline typename QMap<Key, T>::iterator insert(const Key &key, const T &value)
983  { return QMap<Key, T>::insertMulti(key, value); }
984 
985  inline QMultiMap &operator+=(const QMultiMap &other)
986  { this->unite(other); return *this; }
987  inline QMultiMap operator+(const QMultiMap &other) const
988  { QMultiMap result = *this; result += other; return result; }
989 
990 #if !defined(Q_NO_USING_KEYWORD) && !defined(Q_CC_RVCT)
991  // RVCT compiler doesn't handle using-keyword right when used functions are overloaded in child class
993  using QMap<Key, T>::remove;
994  using QMap<Key, T>::count;
995  using QMap<Key, T>::find;
997 #else
998  inline bool contains(const Key &key) const
999  { return QMap<Key, T>::contains(key); }
1000  inline int remove(const Key &key)
1001  { return QMap<Key, T>::remove(key); }
1002  inline int count(const Key &key) const
1003  { return QMap<Key, T>::count(key); }
1004  inline int count() const
1005  { return QMap<Key, T>::count(); }
1006  inline typename QMap<Key, T>::iterator find(const Key &key)
1007  { return QMap<Key, T>::find(key); }
1008  inline typename QMap<Key, T>::const_iterator find(const Key &key) const
1009  { return QMap<Key, T>::find(key); }
1010  inline typename QMap<Key, T>::const_iterator constFind(const Key &key) const
1011  { return QMap<Key, T>::constFind(key); }
1012 #endif
1013 
1014  bool contains(const Key &key, const T &value) const;
1015 
1016  int remove(const Key &key, const T &value);
1017 
1018  int count(const Key &key, const T &value) const;
1019 
1020  typename QMap<Key, T>::iterator find(const Key &key, const T &value) {
1021  typename QMap<Key, T>::iterator i(find(key));
1022  typename QMap<Key, T>::iterator end(this->end());
1023  while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1024  if (i.value() == value)
1025  return i;
1026  ++i;
1027  }
1028  return end;
1029  }
1030  typename QMap<Key, T>::const_iterator find(const Key &key, const T &value) const {
1031  typename QMap<Key, T>::const_iterator i(constFind(key));
1033  while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1034  if (i.value() == value)
1035  return i;
1036  ++i;
1037  }
1038  return end;
1039  }
1040  typename QMap<Key, T>::const_iterator constFind(const Key &key, const T &value) const
1041  { return find(key, value); }
1042 private:
1043  T &operator[](const Key &key);
1044  const T operator[](const Key &key) const;
1045 };
1046 
1047 template <class Key, class T>
1048 Q_INLINE_TEMPLATE bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const
1049 {
1050  return constFind(key, value) != QMap<Key, T>::constEnd();
1051 }
1052 
1053 template <class Key, class T>
1054 Q_INLINE_TEMPLATE int QMultiMap<Key, T>::remove(const Key &key, const T &value)
1055 {
1056  int n = 0;
1057  typename QMap<Key, T>::iterator i(find(key));
1059  while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1060  if (i.value() == value) {
1061  i = this->erase(i);
1062  ++n;
1063  } else {
1064  ++i;
1065  }
1066  }
1067  return n;
1068 }
1069 
1070 template <class Key, class T>
1071 Q_INLINE_TEMPLATE int QMultiMap<Key, T>::count(const Key &key, const T &value) const
1072 {
1073  int n = 0;
1074  typename QMap<Key, T>::const_iterator i(constFind(key));
1076  while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1077  if (i.value() == value)
1078  ++n;
1079  ++i;
1080  }
1081  return n;
1082 }
1083 
1086 
1088 
1090 
1091 #endif // QMAP_H
QMapNode< Key, T > Node
Definition: qmap.h:161
The QMultiMap class is a convenience QMap subclass that provides multi-valued maps.
Definition: qcontainerfwd.h:59
Key key_type
Typedef for Key.
Definition: qmap.h:409
void node_delete(Node *update[], int offset, Node *node)
Definition: qmap.cpp:157
const Key & key() const
Returns the current item&#39;s key as a const reference.
Definition: qmap.h:250
QMapData::Node * i
Definition: qmap.h:304
void setInsertInOrder(bool ordered)
Definition: qmap.h:209
qptrdiff difference_type
Typedef for ptrdiff_t.
Definition: qmap.h:411
Key key
Definition: qmap.h:124
QIntegerForSizeof< void * >::Unsigned quintptr
Definition: qglobal.h:986
#define QT_END_NAMESPACE
This macro expands to.
Definition: qglobal.h:90
const Key key(const T &value) const
Returns the first key with value value.
Definition: qmap.h:844
#define QT_MODULE(x)
Definition: qglobal.h:2783
QMultiMap(const QMap< Key, T > &other)
Constructs a copy of other (which can be a QMap or a QMultiMap).
Definition: qmap.h:977
#define QT_BEGIN_HEADER
Definition: qglobal.h:136
bool empty() const
This function is provided for STL compatibility.
Definition: qmap.h:413
#define it(className, varName)
std::bidirectional_iterator_tag iterator_category
A synonym for {std::bidirectional_iterator_tag} indicating this iterator is a bidirectional iterator...
Definition: qmap.h:307
QList< Key > uniqueKeys() const
Returns a list containing all the keys in the map in ascending order.
Definition: qmap.h:798
bool isDetached() const
Returns true if the map&#39;s internal data isn&#39;t shared with any other map object; otherwise returns fal...
Definition: qmap.h:206
QMap< Key, T >::iterator insert(const Key &key, const T &value)
Inserts a new item with the key key and a value of value.
Definition: qmap.h:982
QMultiMap & operator+=(const QMultiMap &other)
Inserts all the items in the other map into this map and returns a reference to this map...
Definition: qmap.h:985
iterator operator-(int j) const
Returns an iterator to the item at j positions backward from this iterator.
Definition: qmap.h:280
QList< T > values() const
Returns a list containing all the values in the map, in ascending order of their keys.
Definition: qmap.h:863
const_iterator & operator-=(int j)
Makes the iterator go back by j items.
Definition: qmap.h:356
const T * operator->() const
Returns a pointer to the current item&#39;s value.
Definition: qmap.h:330
bool operator!=(const iterator &o) const
Returns true if other points to a different item than this iterator; otherwise returns false...
Definition: qmap.h:258
T & reference
Definition: qmap.h:243
QMapPayloadNode< Key, T > PayloadNode
Definition: qmap.h:162
QMap< Key, T > & operator=(const QMap< Key, T > &other)
Assigns other to this map and returns a reference to this map.
Definition: qmap.h:429
const_iterator(const iterator &o)
Constructs a copy of other.
Definition: qmap.h:320
const_iterator begin() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: qmap.h:373
static void clear(QVariant::Private *d)
Definition: qvariant.cpp:197
const_iterator & operator+=(int j)
Advances the iterator by j items.
Definition: qmap.h:355
int remove(const Key &key, const T &value)
Removes all the items that have the key key and the value value from the map.
Definition: qmap.h:1054
int size() const
Returns the number of (key, value) pairs in the map.
Definition: qmap.h:201
Node * node_create(Node *update[], int offset)
Definition: qmap.cpp:98
QMapData::Node * mutableFindNode(QMapData::Node *update[], const Key &key) const
Definition: qmap.h:779
T & operator[](const Key &key)
Returns the value associated with the key key as a modifiable reference.
Definition: qmap.h:527
QMultiMap()
Constructs an empty map.
Definition: qmap.h:976
T mapped_type
Typedef for T.
Definition: qmap.h:410
const_iterator operator+(int j) const
Returns an iterator to the item at j positions forward from this iterator.
Definition: qmap.h:352
const_iterator(QMapData::Node *node)
Definition: qmap.h:316
QMapData::Node * node_create(QMapData *d, QMapData::Node *update[], const Key &key, const T &value)
Definition: qmap.h:451
const Key & key() const
Returns the current item&#39;s key.
Definition: qmap.h:324
void continueFreeData(int offset)
Definition: qmap.cpp:82
iterator find(const Key &key)
Returns an iterator pointing to the item with key key in the map.
Definition: qmap.h:618
int size
Definition: qmap.h:73
bool operator!=(QBool b1, bool b2)
Definition: qglobal.h:2026
const_iterator & operator--()
The prefix – operator (–i) makes the preceding item current and returns an iterator pointing to the...
Definition: qmap.h:343
const_iterator operator++(int)
The postfix ++ operator (i++) advances the iterator to the next item in the map and returns an iterat...
Definition: qmap.h:338
void setSharable(bool sharable)
Definition: qmap.h:207
QMapData::Node * e
Definition: qmap.h:166
static int alignment()
Definition: qmap.h:170
uint randomBits
Definition: qmap.h:74
#define Q_ASSERT(cond)
Definition: qglobal.h:1823
iterator operator++(int)
The postfix ++ operator (i++) advances the iterator to the next item in the map and returns an iterat...
Definition: qmap.h:264
const T & reference
Definition: qmap.h:311
QStringList keys
T & operator*() const
Returns a modifiable reference to the current item&#39;s value.
Definition: qmap.h:255
QMap< Key, T >::const_iterator constFind(const Key &key, const T &value) const
Returns an iterator pointing to the item with key key and the value value in the map.
Definition: qmap.h:1040
Q_DECL_CONSTEXPR const T & qMax(const T &a, const T &b)
Definition: qglobal.h:1217
QBasicAtomicInt ref
Definition: qmap.h:71
int size_type
Typedef for int.
Definition: qmap.h:412
static QTextFrameData * createData(QTextFrame *f)
#define Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(C)
Definition: qiterator.h:183
QMap< Key, T > & unite(const QMap< Key, T > &other)
Inserts all the items in the other map into this map.
Definition: qmap.h:625
int topLevel
Definition: qmap.h:72
bool operator!=(const const_iterator &o) const
Definition: qmap.h:292
void freeData(QMapData *d)
Definition: qmap.h:642
T & value() const
Returns a modifiable reference to the current item&#39;s value.
Definition: qmap.h:251
QMapData * d
Definition: qmap.h:165
iterator insertMulti(const Key &key, const T &value)
Inserts a new item with the key key and a value of value.
Definition: qmap.h:595
#define QT_RETHROW
Definition: qglobal.h:1539
const_iterator operator-(int j) const
Returns an iterator to the item at j positions backward from this iterator.
Definition: qmap.h:354
void append(const T &t)
Inserts value at the end of the list.
Definition: qlist.h:507
static QMapData * createData()
Definition: qmap.cpp:59
QMultiMap operator+(const QMultiMap &other) const
Returns a map that contains all the items in this map in addition to all the items in other...
Definition: qmap.h:987
QFuture< void > map(Sequence &sequence, MapFunction function)
QMapData::Node * backward
Definition: qmap.h:155
#define QT_BEGIN_NAMESPACE
This macro expands to.
Definition: qglobal.h:89
QMapData::Node * i
Definition: qmap.h:236
uint strictAlignment
Definition: qmap.h:77
uint sharable
Definition: qmap.h:76
static bool isEmpty(const char *str)
const_iterator ConstIterator
Qt-style synonym for QMap::const_iterator.
Definition: qmap.h:389
QMap< Key, T >::iterator find(const Key &key, const T &value)
Returns an iterator pointing to the item with key key and value value in the map. ...
Definition: qmap.h:1020
QIntegerForSizeof< void * >::Signed qptrdiff
Definition: qglobal.h:987
bool operator==(const const_iterator &o) const
Returns true if other points to the same item as this iterator; otherwise returns false...
Definition: qmap.h:331
T * pointer
Definition: qmap.h:242
const T value(const Key &key) const
Returns the value associated with the key key.
Definition: qmap.h:499
int count() const
Same as size().
Definition: qmap.h:390
iterator Iterator
Qt-style synonym for QMap::iterator.
Definition: qmap.h:388
iterator & operator--()
The prefix – operator (–i) makes the preceding item current and returns an iterator pointing to the...
Definition: qmap.h:269
T value_type
Definition: qmap.h:241
#define Q_INLINE_TEMPLATE
Definition: qglobal.h:1713
static const char * data(const QByteArray &arr)
QMapData * forward[QMapData::LastLevel+1]
Definition: qmap.h:70
unsigned int uint
Definition: qglobal.h:996
QMap()
Constructs an empty map.
Definition: qmap.h:182
uint insertInOrder
Definition: qmap.h:75
QList< Key > keys() const
Returns a list containing all the keys in the map in ascending order.
Definition: qmap.h:818
QMap< Key, T >::iterator replace(const Key &key, const T &value)
Inserts a new item with the key key and a value of value.
Definition: qmap.h:980
void detach()
Detaches this map from any other maps with which it may share data.
Definition: qmap.h:205
quint16 values[128]
T * operator->() const
Returns a pointer to the current item&#39;s value.
Definition: qmap.h:256
const_iterator constBegin() const
Returns a const STL-style iterator pointing to the first item in the map.
Definition: qmap.h:374
#define QT_CATCH(A)
Definition: qglobal.h:1537
iterator & operator++()
The prefix ++ operator (++i) advances the iterator to the next item in the map and returns an iterato...
Definition: qmap.h:260
std::map< Key, T > toStdMap() const
Returns an STL map equivalent to this QMap.
Definition: qmap.h:959
qptrdiff difference_type
Definition: qmap.h:240
bool operator!=(const QMap< Key, T > &other) const
Returns true if other is not equal to this map; otherwise returns false.
Definition: qmap.h:199
iterator & operator+=(int j)
Advances the iterator by j items.
Definition: qmap.h:281
void qSwap(T &value1, T &value2)
Definition: qglobal.h:2181
iterator begin()
Returns an STL-style iterator pointing to the first item in the map.
Definition: qmap.h:372
bool operator==(const const_iterator &o) const
Definition: qmap.h:290
#define Q_DECLARE_ASSOCIATIVE_ITERATOR(C)
Definition: qiterator.h:151
void swap(QMap< Key, T > &other)
Swaps map other with this map.
Definition: qmap.h:192
bool qMapLessThanKey(const Key &key1, const Key &key2)
Definition: qmap.h:105
int remove(const Key &key)
Removes all the items that have the key key from the map.
Definition: qmap.h:662
Node * forward[1]
Definition: qmap.h:65
bool contains(const Key &key, const T &value) const
Returns true if the map contains an item with key key and value value; otherwise returns false...
Definition: qmap.h:1048
The QMap::const_iterator class provides an STL-style const iterator for QMap and QMultiMap.
Definition: qmap.h:301
const_iterator constEnd() const
Returns a const STL-style iterator pointing to the imaginary item after the last item in the map...
Definition: qmap.h:380
const_iterator end() const
This is an overloaded member function, provided for convenience. It differs from the above function o...
Definition: qmap.h:379
#define Q_CORE_EXPORT
Definition: qglobal.h:1449
The QMap::iterator class provides an STL-style non-const iterator for QMap and QMultiMap.
Definition: qmap.h:233
QMapData::Node * backward
Definition: qmap.h:130
~QMap()
Destroys the map.
Definition: qmap.h:185
iterator end()
Returns an STL-style iterator pointing to the imaginary item after the last item in the map...
Definition: qmap.h:375
bool operator==(const iterator &o) const
Returns true if other points to the same item as this iterator; otherwise returns false...
Definition: qmap.h:257
iterator insert(const Key &key, const T &value)
Inserts a new item with the key key and a value of value.
Definition: qmap.h:559
iterator(QMapData::Node *node)
Definition: qmap.h:248
bool operator==(const QMap< Key, T > &other) const
Returns true if other is equal to this map; otherwise returns false.
Definition: qmap.h:925
Definition: qmap.h:61
int key
static int payload()
Definition: qmap.h:169
const T & operator*() const
Returns the current item&#39;s value.
Definition: qmap.h:329
iterator & operator-=(int j)
Makes the iterator go back by j items.
Definition: qmap.h:282
bool isEmpty() const
Returns true if the map contains no items; otherwise returns false.
Definition: qmap.h:203
const_iterator & operator++()
The prefix ++ operator (++i) advances the iterator to the next item in the map and returns an iterato...
Definition: qmap.h:334
Node & operator=(const Node &)
const_iterator()
Constructs an uninitialized iterator.
Definition: qmap.h:315
const_iterator operator--(int)
The postfix – operator (i–) makes the preceding item current and returns an iterator pointing to th...
Definition: qmap.h:347
const T & value() const
Returns the current item&#39;s value.
Definition: qmap.h:325
bool contains(const Key &key) const
Returns true if the map contains an item with key key; otherwise returns false.
Definition: qmap.h:553
QMap(const QMap< Key, T > &other)
Constructs a copy of other.
Definition: qmap.h:183
static QString dump(const QByteArray &)
const_iterator constFind(const Key &key) const
Returns an const iterator pointing to the item with key key in the map.
Definition: qmap.h:612
QMapData * backward
Definition: qmap.h:69
iterator()
Constructs an uninitialized iterator.
Definition: qmap.h:247
bool isSharedWith(const QMap< Key, T > &other) const
Definition: qmap.h:208
iterator erase(iterator it)
Removes the (key, value) pair pointed to by the iterator pos from the map, and returns an iterator to...
Definition: qmap.h:717
iterator upperBound(const Key &key)
Returns an iterator pointing to the item that immediately follows the last item with key key in the m...
Definition: qmap.h:918
Node * backward
Definition: qmap.h:64
T take(const Key &key)
Removes the item with the key key from the map and returns the value associated with it...
Definition: qmap.h:692
static Node * concrete(QMapData::Node *node)
Definition: qmap.h:177
iterator operator--(int)
The postfix – operator (i–) makes the preceding item current and returns an iterator pointing to th...
Definition: qmap.h:273
iterator lowerBound(const Key &key)
Returns an iterator pointing to the first item with key key in the map.
Definition: qmap.h:899
void detach_helper()
Definition: qmap.h:752
void swap(QMultiMap< Key, T > &other)
Swaps map other with this map.
Definition: qmap.h:978
static const KeyPair *const end
#define Q_OUTOFLINE_TEMPLATE
Definition: qglobal.h:1710
bool operator!=(const const_iterator &o) const
Returns true if other points to a different item than this iterator; otherwise returns false...
Definition: qmap.h:332
#define QT_END_HEADER
Definition: qglobal.h:137
bool operator==(QBool b1, bool b2)
Definition: qglobal.h:2023
uint reserved
Definition: qmap.h:78
#define QT_TRY
Definition: qglobal.h:1536
std::bidirectional_iterator_tag iterator_category
A synonym for {std::bidirectional_iterator_tag} indicating this iterator is a bidirectional iterator...
Definition: qmap.h:239
QMap< Key, T >::const_iterator find(const Key &key, const T &value) const
Returns a const iterator pointing to the item with the given key and value in the map...
Definition: qmap.h:1030
void clear()
Removes all items from the map.
Definition: qmap.h:444
iterator operator+(int j) const
Returns an iterator to the item at j positions forward from this iterator.
Definition: qmap.h:278
The QMap class is a template class that provides a skip-list-based dictionary.
Definition: qdatastream.h:67
void reserve(int size)
Reserve space for alloc elements.
Definition: qlist.h:496
qptrdiff difference_type
Definition: qmap.h:308
QMapData::Node * findNode(const Key &key) const
Definition: qmap.h:481
const T * pointer
Definition: qmap.h:310
The QList class is a template class that provides lists.
Definition: qdatastream.h:62
Definition: qmap.h:123
T value
Definition: qmap.h:125
static QMapData shared_null
Definition: qmap.h:91
timeval operator+(const timeval &t1, const timeval &t2)
Definition: qcore_unix_p.h:126