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
55QT_BEGIN_HEADER
56
57QT_BEGIN_NAMESPACE
58
59QT_MODULE(Core)
60
61struct Q_CORE_EXPORT QMapData
62{
63 struct Node {
64 Node *backward;
65 Node *forward[1];
66 };
67 enum { LastLevel = 11, Sparseness = 3 };
68
69 QMapData *backward;
70 QMapData *forward[QMapData::LastLevel + 1];
71 QBasicAtomicInt ref;
72 int topLevel;
73 int size;
74 uint randomBits;
75 uint insertInOrder : 1;
76 uint sharable : 1;
77 uint strictAlignment : 1;
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
105template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2)
106{
107 return key1 < key2;
108}
109
110template <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
116template <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
122template <class Key, class T>
123struct QMapNode {
124 Key key;
125 T value;
126
127private:
128 // never access these members through this structure.
129 // see below
130 QMapData::Node *backward;
131 QMapData::Node *forward[1];
132};
133
134template <class Key, class T>
135struct QMapPayloadNode
136{
137 Key key;
138 T value;
139
140private:
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 ----->|
155 QMapData::Node *backward;
156};
157
158template <class Key, class T>
159class QMap
160{
161 typedef QMapNode<Key, T> Node;
162 typedef QMapPayloadNode<Key, T> PayloadNode;
163
164 union {
165 QMapData *d;
166 QMapData::Node *e;
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
181public:
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;
236 QMapData::Node *i;
237
238 public:
239 typedef std::bidirectional_iterator_tag iterator_category;
240 typedef qptrdiff difference_type;
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
301 class const_iterator
302 {
303 friend class iterator;
304 QMapData::Node *i;
305
306 public:
307 typedef std::bidirectional_iterator_tag iterator_category;
308 typedef qptrdiff difference_type;
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
334 inline const_iterator &operator++() {
335 i = i->forward[0];
336 return *this;
337 }
338 inline const_iterator operator++(int) {
339 const_iterator r = *this;
340 i = i->forward[0];
341 return r;
342 }
343 inline const_iterator &operator--() {
344 i = i->backward;
345 return *this;
346 }
347 inline const_iterator operator--(int) {
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;
411 typedef qptrdiff difference_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
419private:
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
428template <class Key, class T>
429Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)
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
443template <class Key, class T>
444Q_INLINE_TEMPLATE void QMap<Key, T>::clear()
445{
446 *this = QMap<Key, T>();
447}
448
449template <class Key, class T>
450Q_INLINE_TEMPLATE typename QMapData::Node *
451QMap<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
480template <class Key, class T>
481Q_INLINE_TEMPLATE QMapData::Node *QMap<Key, T>::findNode(const Key &akey) const
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
498template <class Key, class T>
499Q_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
509template <class Key, class T>
510Q_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
520template <class Key, class T>
521Q_INLINE_TEMPLATE const T QMap<Key, T>::operator[](const Key &akey) const
522{
523 return value(akey);
524}
525
526template <class Key, class T>
527Q_INLINE_TEMPLATE T &QMap<Key, T>::operator[](const Key &akey)
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
538template <class Key, class T>
539Q_INLINE_TEMPLATE int QMap<Key, T>::count(const Key &akey) const
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
552template <class Key, class T>
553Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const
554{
555 return findNode(akey) != e;
556}
557
558template <class Key, class T>
559Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey,
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
575template <class Key, class T>
576Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey,
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
594template <class Key, class T>
595Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &akey,
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
605template <class Key, class T>
606Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const
607{
608 return const_iterator(findNode(akey));
609}
610
611template <class Key, class T>
612Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const
613{
614 return const_iterator(findNode(akey));
615}
616
617template <class Key, class T>
618Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::find(const Key &akey)
619{
620 detach();
621 return iterator(findNode(akey));
622}
623
624template <class Key, class T>
625Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other)
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
641template <class Key, class T>
642Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::freeData(QMapData *x)
643{
644 if (QTypeInfo<Key>::isComplex || QTypeInfo<T>::isComplex) {
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
661template <class Key, class T>
662Q_OUTOFLINE_TEMPLATE int QMap<Key, T>::remove(const Key &akey)
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
691template <class Key, class T>
692Q_OUTOFLINE_TEMPLATE T QMap<Key, T>::take(const Key &akey)
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
716template <class Key, class T>
717Q_OUTOFLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::erase(iterator it)
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
751template <class Key, class T>
752Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper()
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
778template <class Key, class T>
779Q_OUTOFLINE_TEMPLATE QMapData::Node *QMap<Key, T>::mutableFindNode(QMapData::Node *aupdate[],
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
797template <class Key, class T>
798Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::uniqueKeys() const
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 }
813break_out_of_outer_loop:
814 return res;
815}
816
817template <class Key, class T>
818Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys() const
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
830template <class Key, class T>
831Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys(const T &avalue) const
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
843template <class Key, class T>
844Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue) const
845{
846 return key(avalue, Key());
847}
848
849template <class Key, class T>
850Q_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
862template <class Key, class T>
863Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values() const
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
875template <class Key, class T>
876Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values(const Key &akey) const
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
889template <class Key, class T>
890Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
891QMap<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
898template <class Key, class T>
899Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &akey)
900{
901 detach();
902 return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->lowerBound(akey));
903}
904
905template <class Key, class T>
906Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
907QMap<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
917template <class Key, class T>
918Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &akey)
919{
920 detach();
921 return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->upperBound(akey));
922}
923
924template <class Key, class T>
925Q_OUTOFLINE_TEMPLATE bool QMap<Key, T>::operator==(const QMap<Key, T> &other) const
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
945template <class Key, class T>
946Q_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
958template <class Key, class T>
959Q_OUTOFLINE_TEMPLATE std::map<Key, T> QMap<Key, T>::toStdMap() const
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
972template <class Key, class T>
973class QMultiMap : public QMap<Key, T>
974{
975public:
976 QMultiMap() {}
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
992 using QMap<Key, T>::contains;
993 using QMap<Key, T>::remove;
994 using QMap<Key, T>::count;
995 using QMap<Key, T>::find;
996 using QMap<Key, T>::constFind;
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));
1032 typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
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); }
1042private:
1043 T &operator[](const Key &key);
1044 const T operator[](const Key &key) const;
1045};
1046
1047template <class Key, class T>
1048Q_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
1053template <class Key, class T>
1054Q_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));
1058 typename QMap<Key, T>::iterator end(QMap<Key, T>::end());
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
1070template <class Key, class T>
1071Q_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));
1075 typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
1076 while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1077 if (i.value() == value)
1078 ++n;
1079 ++i;
1080 }
1081 return n;
1082}
1083
1084Q_DECLARE_ASSOCIATIVE_ITERATOR(Map)
1085Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map)
1086
1087QT_END_NAMESPACE
1088
1089QT_END_HEADER
1090
1091#endif // QMAP_H
1092