Merge remote branch 'origin/4.6' into integration-master-from-4.6
[qt:kenya888s-qt-palm-pre.git] / src / corelib / tools / qmap.h
1 /****************************************************************************
2 **
3 ** Copyright (C) 2010 Nokia Corporation and/or its subsidiary(-ies).
4 ** All rights reserved.
5 ** Contact: Nokia Corporation (qt-info@nokia.com)
6 **
7 ** This file is part of the QtCore module of the Qt Toolkit.
8 **
9 ** $QT_BEGIN_LICENSE:LGPL$
10 ** No Commercial Usage
11 ** This file contains pre-release code and may not be distributed.
12 ** You may use this file in accordance with the terms and conditions
13 ** contained in the Technology Preview License Agreement accompanying
14 ** this package.
15 **
16 ** GNU Lesser General Public License Usage
17 ** Alternatively, this file may be used under the terms of the GNU Lesser
18 ** General Public License version 2.1 as published by the Free Software
19 ** Foundation and appearing in the file LICENSE.LGPL included in the
20 ** packaging of this file.  Please review the following information to
21 ** ensure the GNU Lesser General Public License version 2.1 requirements
22 ** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
23 **
24 ** In addition, as a special exception, Nokia gives you certain additional
25 ** rights.  These rights are described in the Nokia Qt LGPL Exception
26 ** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
27 **
28 ** If you have questions regarding the use of this file, please contact
29 ** Nokia at qt-info@nokia.com.
30 **
31 **
32 **
33 **
34 **
35 **
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
55 QT_BEGIN_HEADER
56
57 QT_BEGIN_NAMESPACE
58
59 QT_MODULE(Core)
60
61 struct 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
105 template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2)
106 {
107     return key1 < key2;
108 }
109
110 #ifndef QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
111 template <class Ptr> inline bool qMapLessThanKey(Ptr *key1, Ptr *key2)
112 {
113     Q_ASSERT(sizeof(quintptr) == sizeof(Ptr *));
114     return quintptr(key1) < quintptr(key2);
115 }
116
117 template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)
118 {
119     Q_ASSERT(sizeof(quintptr) == sizeof(const Ptr *));
120     return quintptr(key1) < quintptr(key2);
121 }
122 #endif // QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
123
124 template <class Key, class T>
125 struct QMapNode {
126     Key key;
127     T value;
128     QMapData::Node *backward;
129     QMapData::Node *forward[1];
130 };
131
132 template <class Key, class T>
133 struct QMapPayloadNode
134 {
135     Key key;
136     T value;
137     QMapData::Node *backward;
138 };
139
140 template <class Key, class T>
141 class QMap
142 {
143     typedef QMapNode<Key, T> Node;
144     typedef QMapPayloadNode<Key, T> PayloadNode;
145
146     union {
147         QMapData *d;
148         QMapData::Node *e;
149     };
150
151     static inline int payload() { return sizeof(PayloadNode) - sizeof(QMapData::Node *); }
152     static inline int alignment() {
153 #ifdef Q_ALIGNOF
154         return int(qMax(sizeof(void*), Q_ALIGNOF(Node)));
155 #else
156         return 0;
157 #endif
158     }
159     static inline Node *concrete(QMapData::Node *node) {
160         return reinterpret_cast<Node *>(reinterpret_cast<char *>(node) - payload());
161     }
162
163 public:
164     inline QMap() : d(&QMapData::shared_null) { d->ref.ref(); }
165     inline QMap(const QMap<Key, T> &other) : d(other.d)
166     { d->ref.ref(); if (!d->sharable) detach(); }
167     inline ~QMap() { if (!d) return; if (!d->ref.deref()) freeData(d); }
168
169     QMap<Key, T> &operator=(const QMap<Key, T> &other);
170 #ifndef QT_NO_STL
171     explicit QMap(const typename std::map<Key, T> &other);
172     std::map<Key, T> toStdMap() const;
173 #endif
174
175     bool operator==(const QMap<Key, T> &other) const;
176     inline bool operator!=(const QMap<Key, T> &other) const { return !(*this == other); }
177
178     inline int size() const { return d->size; }
179
180     inline bool isEmpty() const { return d->size == 0; }
181
182     inline void detach() { if (d->ref != 1) detach_helper(); }
183     inline bool isDetached() const { return d->ref == 1; }
184     inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
185     inline bool isSharedWith(const QMap<Key, T> &other) const { return d == other.d; }
186     inline void setInsertInOrder(bool ordered) { d->insertInOrder = ordered; }
187
188     void clear();
189
190     int remove(const Key &key);
191     T take(const Key &key);
192
193     bool contains(const Key &key) const;
194     const Key key(const T &value) const;
195     const Key key(const T &value, const Key &defaultKey) const;
196     const T value(const Key &key) const;
197     const T value(const Key &key, const T &defaultValue) const;
198     T &operator[](const Key &key);
199     const T operator[](const Key &key) const;
200
201     QList<Key> uniqueKeys() const;
202     QList<Key> keys() const;
203     QList<Key> keys(const T &value) const;
204     QList<T> values() const;
205     QList<T> values(const Key &key) const;
206     int count(const Key &key) const;
207
208     class const_iterator;
209
210     class iterator
211     {
212         friend class const_iterator;
213         QMapData::Node *i;
214
215     public:
216         typedef std::bidirectional_iterator_tag iterator_category;
217         typedef qptrdiff difference_type;
218         typedef T value_type;
219         typedef T *pointer;
220         typedef T &reference;
221
222         // ### Qt 5: get rid of 'operator Node *'
223         inline operator QMapData::Node *() const { return i; }
224         inline iterator() : i(0) { }
225         inline iterator(QMapData::Node *node) : i(node) { }
226
227         inline const Key &key() const { return concrete(i)->key; }
228         inline T &value() const { return concrete(i)->value; }
229 #ifdef QT3_SUPPORT
230         inline QT3_SUPPORT T &data() const { return concrete(i)->value; }
231 #endif
232         inline T &operator*() const { return concrete(i)->value; }
233         inline T *operator->() const { return &concrete(i)->value; }
234         inline bool operator==(const iterator &o) const { return i == o.i; }
235         inline bool operator!=(const iterator &o) const { return i != o.i; }
236
237         inline iterator &operator++() {
238             i = i->forward[0];
239             return *this;
240         }
241         inline iterator operator++(int) {
242             iterator r = *this;
243             i = i->forward[0];
244             return r;
245         }
246         inline iterator &operator--() {
247             i = i->backward;
248             return *this;
249         }
250         inline iterator operator--(int) {
251             iterator r = *this;
252             i = i->backward;
253             return r;
254         }
255         inline iterator operator+(int j) const
256         { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
257         inline iterator operator-(int j) const { return operator+(-j); }
258         inline iterator &operator+=(int j) { return *this = *this + j; }
259         inline iterator &operator-=(int j) { return *this = *this - j; }
260
261         // ### Qt 5: not sure this is necessary anymore
262 #ifdef QT_STRICT_ITERATORS
263     private:
264 #else
265     public:
266 #endif
267         inline bool operator==(const const_iterator &o) const
268             { return i == o.i; }
269         inline bool operator!=(const const_iterator &o) const
270             { return i != o.i; }
271
272     private:
273         // ### Qt 5: remove
274         inline operator bool() const { return false; }
275     };
276     friend class iterator;
277
278     class const_iterator
279     {
280         friend class iterator;
281         QMapData::Node *i;
282
283     public:
284         typedef std::bidirectional_iterator_tag iterator_category;
285         typedef qptrdiff difference_type;
286         typedef T value_type;
287         typedef const T *pointer;
288         typedef const T &reference;
289
290         // ### Qt 5: get rid of 'operator Node *'
291         inline operator QMapData::Node *() const { return i; }
292         inline const_iterator() : i(0) { }
293         inline const_iterator(QMapData::Node *node) : i(node) { }
294 #ifdef QT_STRICT_ITERATORS
295         explicit inline const_iterator(const iterator &o)
296 #else
297         inline const_iterator(const iterator &o)
298 #endif
299         { i = o.i; }
300
301         inline const Key &key() const { return concrete(i)->key; }
302         inline const T &value() const { return concrete(i)->value; }
303 #ifdef QT3_SUPPORT
304         inline QT3_SUPPORT const T &data() const { return concrete(i)->value; }
305 #endif
306         inline const T &operator*() const { return concrete(i)->value; }
307         inline const T *operator->() const { return &concrete(i)->value; }
308         inline bool operator==(const const_iterator &o) const { return i == o.i; }
309         inline bool operator!=(const const_iterator &o) const { return i != o.i; }
310
311         inline const_iterator &operator++() {
312             i = i->forward[0];
313             return *this;
314         }
315         inline const_iterator operator++(int) {
316             const_iterator r = *this;
317             i = i->forward[0];
318             return r;
319         }
320         inline const_iterator &operator--() {
321             i = i->backward;
322             return *this;
323         }
324         inline const_iterator operator--(int) {
325             const_iterator r = *this;
326             i = i->backward;
327             return r;
328         }
329         inline const_iterator operator+(int j) const
330         { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
331         inline const_iterator operator-(int j) const { return operator+(-j); }
332         inline const_iterator &operator+=(int j) { return *this = *this + j; }
333         inline const_iterator &operator-=(int j) { return *this = *this - j; }
334
335         // ### Qt 5: not sure this is necessary anymore
336 #ifdef QT_STRICT_ITERATORS
337     private:
338         inline bool operator==(const iterator &o) { return operator==(const_iterator(o)); }
339         inline bool operator!=(const iterator &o) { return operator!=(const_iterator(o)); }
340 #endif
341
342     private:
343         // ### Qt 5: remove
344         inline operator bool() const { return false; }
345     };
346     friend class const_iterator;
347
348     // STL style
349     inline iterator begin() { detach(); return iterator(e->forward[0]); }
350     inline const_iterator begin() const { return const_iterator(e->forward[0]); }
351     inline const_iterator constBegin() const { return const_iterator(e->forward[0]); }
352     inline iterator end() {
353         detach();
354         return iterator(e);
355     }
356     inline const_iterator end() const { return const_iterator(e); }
357     inline const_iterator constEnd() const { return const_iterator(e); }
358     iterator erase(iterator it);
359 #ifdef QT3_SUPPORT
360     inline QT3_SUPPORT iterator remove(iterator it) { return erase(it); }
361     inline QT3_SUPPORT void erase(const Key &aKey) { remove(aKey); }
362 #endif
363
364     // more Qt
365     typedef iterator Iterator;
366     typedef const_iterator ConstIterator;
367     inline int count() const { return d->size; }
368     iterator find(const Key &key);
369     const_iterator find(const Key &key) const;
370     const_iterator constFind(const Key &key) const;
371     iterator lowerBound(const Key &key);
372     const_iterator lowerBound(const Key &key) const;
373     iterator upperBound(const Key &key);
374     const_iterator upperBound(const Key &key) const;
375     iterator insert(const Key &key, const T &value);
376 #ifdef QT3_SUPPORT
377     QT3_SUPPORT iterator insert(const Key &key, const T &value, bool overwrite);
378 #endif
379     iterator insertMulti(const Key &key, const T &value);
380 #ifdef QT3_SUPPORT
381     inline QT3_SUPPORT iterator replace(const Key &aKey, const T &aValue) { return insert(aKey, aValue); }
382 #endif
383     QMap<Key, T> &unite(const QMap<Key, T> &other);
384
385     // STL compatibility
386     typedef Key key_type;
387     typedef T mapped_type;
388     typedef qptrdiff difference_type;
389     typedef int size_type;
390     inline bool empty() const { return isEmpty(); }
391
392 #ifdef QT_QMAP_DEBUG
393     inline void dump() const { d->dump(); }
394 #endif
395
396 private:
397     void detach_helper();
398     void freeData(QMapData *d);
399     QMapData::Node *findNode(const Key &key) const;
400     QMapData::Node *mutableFindNode(QMapData::Node *update[], const Key &key) const;
401     QMapData::Node *node_create(QMapData *d, QMapData::Node *update[], const Key &key,
402                                 const T &value);
403 };
404
405 template <class Key, class T>
406 Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)
407 {
408     if (d != other.d) {
409         other.d->ref.ref();
410         if (!d->ref.deref())
411             freeData(d);
412         d = other.d;
413         if (!d->sharable)
414             detach_helper();
415     }
416     return *this;
417 }
418
419 template <class Key, class T>
420 Q_INLINE_TEMPLATE void QMap<Key, T>::clear()
421 {
422     *this = QMap<Key, T>();
423 }
424
425 template <class Key, class T>
426 Q_INLINE_TEMPLATE typename QMapData::Node *
427 QMap<Key, T>::node_create(QMapData *adt, QMapData::Node *aupdate[], const Key &akey, const T &avalue)
428 {
429     QMapData::Node *abstractNode = adt->node_create(aupdate, payload(), alignment());
430     QT_TRY {
431         Node *concreteNode = concrete(abstractNode);
432         new (&concreteNode->key) Key(akey);
433         QT_TRY {
434             new (&concreteNode->value) T(avalue);
435         } QT_CATCH(...) {
436             concreteNode->key.~Key();
437             QT_RETHROW;
438         }
439     } QT_CATCH(...) {
440         adt->node_delete(aupdate, payload(), abstractNode);
441         QT_RETHROW;
442     }
443
444     // clean up the update array for further insertions
445     /*
446     for (int i = 0; i <= d->topLevel; ++i) {
447         if ( aupdate[i]==reinterpret_cast<QMapData::Node *>(adt) || aupdate[i]->forward[i] != abstractNode)
448             break;
449         aupdate[i] = abstractNode;
450     }
451 */
452
453     return abstractNode;
454 }
455
456 template <class Key, class T>
457 Q_INLINE_TEMPLATE QMapData::Node *QMap<Key, T>::findNode(const Key &akey) const
458 {
459     QMapData::Node *cur = e;
460     QMapData::Node *next = e;
461
462     for (int i = d->topLevel; i >= 0; i--) {
463         while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
464             cur = next;
465     }
466
467     if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
468         return next;
469     } else {
470         return e;
471     }
472 }
473
474 template <class Key, class T>
475 Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey) const
476 {
477     QMapData::Node *node;
478     if (d->size == 0 || (node = findNode(akey)) == e) {
479         return T();
480     } else {
481         return concrete(node)->value;
482     }
483 }
484
485 template <class Key, class T>
486 Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey, const T &adefaultValue) const
487 {
488     QMapData::Node *node;
489     if (d->size == 0 || (node = findNode(akey)) == e) {
490         return adefaultValue;
491     } else {
492         return concrete(node)->value;
493     }
494 }
495
496 template <class Key, class T>
497 Q_INLINE_TEMPLATE const T QMap<Key, T>::operator[](const Key &akey) const
498 {
499     return value(akey);
500 }
501
502 template <class Key, class T>
503 Q_INLINE_TEMPLATE T &QMap<Key, T>::operator[](const Key &akey)
504 {
505     detach();
506
507     QMapData::Node *update[QMapData::LastLevel + 1];
508     QMapData::Node *node = mutableFindNode(update, akey);
509     if (node == e)
510         node = node_create(d, update, akey, T());
511     return concrete(node)->value;
512 }
513
514 template <class Key, class T>
515 Q_INLINE_TEMPLATE int QMap<Key, T>::count(const Key &akey) const
516 {
517     int cnt = 0;
518     QMapData::Node *node = findNode(akey);
519     if (node != e) {
520         do {
521             ++cnt;
522             node = node->forward[0];
523         } while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));
524     }
525     return cnt;
526 }
527
528 template <class Key, class T>
529 Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const
530 {
531     return findNode(akey) != e;
532 }
533
534 template <class Key, class T>
535 Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey,
536                                                                        const T &avalue)
537 {
538     detach();
539
540     QMapData::Node *update[QMapData::LastLevel + 1];
541     QMapData::Node *node = mutableFindNode(update, akey);
542     if (node == e) {
543         node = node_create(d, update, akey, avalue);
544     } else {
545         concrete(node)->value = avalue;
546     }
547     return iterator(node);
548 }
549
550 #ifdef QT3_SUPPORT
551 template <class Key, class T>
552 Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey,
553                                                                        const T &avalue,
554                                                                        bool aoverwrite)
555 {
556     detach();
557
558     QMapData::Node *update[QMapData::LastLevel + 1];
559     QMapData::Node *node = mutableFindNode(update, akey);
560     if (node == e) {
561         node = node_create(d, update, akey, avalue);
562     } else {
563         if (aoverwrite)
564             concrete(node)->value = avalue;
565     }
566     return iterator(node);
567 }
568 #endif
569
570 template <class Key, class T>
571 Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &akey,
572                                                                             const T &avalue)
573 {
574     detach();
575
576     QMapData::Node *update[QMapData::LastLevel + 1];
577     mutableFindNode(update, akey);
578     return iterator(node_create(d, update, akey, avalue));
579 }
580
581 template <class Key, class T>
582 Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const
583 {
584     return const_iterator(findNode(akey));
585 }
586
587 template <class Key, class T>
588 Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const
589 {
590     return const_iterator(findNode(akey));
591 }
592
593 template <class Key, class T>
594 Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::find(const Key &akey)
595 {
596     detach();
597     return iterator(findNode(akey));
598 }
599
600 template <class Key, class T>
601 Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other)
602 {
603     QMap<Key, T> copy(other);
604     const_iterator it = copy.constEnd();
605     const const_iterator b = copy.constBegin();
606     while (it != b) {
607         --it;
608         insertMulti(it.key(), it.value());
609     }
610     return *this;
611 }
612
613 template <class Key, class T>
614 Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::freeData(QMapData *x)
615 {
616     if (QTypeInfo<Key>::isComplex || QTypeInfo<T>::isComplex) {
617         QMapData *cur = x;
618         QMapData *next = cur->forward[0];
619         while (next != x) {
620             cur = next;
621             next = cur->forward[0];
622 #if defined(_MSC_VER) && (_MSC_VER >= 1300)
623 #pragma warning(disable:4189)
624 #endif
625             Node *concreteNode = concrete(reinterpret_cast<QMapData::Node *>(cur));
626             concreteNode->key.~Key();
627             concreteNode->value.~T();
628 #if defined(_MSC_VER) && (_MSC_VER >= 1300)
629 #pragma warning(default:4189)
630 #endif
631         }
632     }
633     x->continueFreeData(payload());
634 }
635
636 template <class Key, class T>
637 Q_OUTOFLINE_TEMPLATE int QMap<Key, T>::remove(const Key &akey)
638 {
639     detach();
640
641     QMapData::Node *update[QMapData::LastLevel + 1];
642     QMapData::Node *cur = e;
643     QMapData::Node *next = e;
644     int oldSize = d->size;
645
646     for (int i = d->topLevel; i >= 0; i--) {
647         while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
648             cur = next;
649         update[i] = cur;
650     }
651
652     if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
653         bool deleteNext = true;
654         do {
655             cur = next;
656             next = cur->forward[0];
657             deleteNext = (next != e && !qMapLessThanKey<Key>(concrete(cur)->key, concrete(next)->key));
658             concrete(cur)->key.~Key();
659             concrete(cur)->value.~T();
660             d->node_delete(update, payload(), cur);
661         } while (deleteNext);
662     }
663     return oldSize - d->size;
664 }
665
666 template <class Key, class T>
667 Q_OUTOFLINE_TEMPLATE T QMap<Key, T>::take(const Key &akey)
668 {
669     detach();
670
671     QMapData::Node *update[QMapData::LastLevel + 1];
672     QMapData::Node *cur = e;
673     QMapData::Node *next = e;
674
675     for (int i = d->topLevel; i >= 0; i--) {
676         while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
677             cur = next;
678         update[i] = cur;
679     }
680
681     if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
682         T t = concrete(next)->value;
683         concrete(next)->key.~Key();
684         concrete(next)->value.~T();
685         d->node_delete(update, payload(), next);
686         return t;
687     }
688     return T();
689 }
690
691 template <class Key, class T>
692 Q_OUTOFLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::erase(iterator it)
693 {
694     QMapData::Node *update[QMapData::LastLevel + 1];
695     QMapData::Node *cur = e;
696     QMapData::Node *next = e;
697
698     if (it == iterator(e))
699         return it;
700
701     for (int i = d->topLevel; i >= 0; i--) {
702         while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, it.key()))
703             cur = next;
704         update[i] = cur;
705     }
706
707     while (next != e) {
708         cur = next;
709         next = cur->forward[0];
710         if (cur == it) {
711             concrete(cur)->key.~Key();
712             concrete(cur)->value.~T();
713             d->node_delete(update, payload(), cur);
714             return iterator(next);
715         }
716
717         for (int i = 0; i <= d->topLevel; ++i) {
718             if (update[i]->forward[i] != cur)
719                 break;
720             update[i] = cur;
721         }
722     }
723     return end();
724 }
725
726 template <class Key, class T>
727 Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper()
728 {
729     union { QMapData *d; QMapData::Node *e; } x;
730     x.d = QMapData::createData(alignment());
731     if (d->size) {
732         x.d->insertInOrder = true;
733         QMapData::Node *update[QMapData::LastLevel + 1];
734         QMapData::Node *cur = e->forward[0];
735         update[0] = x.e;
736         while (cur != e) {
737             QT_TRY {
738                 Node *concreteNode = concrete(cur);
739                 node_create(x.d, update, concreteNode->key, concreteNode->value);
740             } QT_CATCH(...) {
741                 freeData(x.d);
742                 QT_RETHROW;
743             }
744             cur = cur->forward[0];
745         }
746         x.d->insertInOrder = false;
747     }
748     if (!d->ref.deref())
749         freeData(d);
750     d = x.d;
751 }
752
753 template <class Key, class T>
754 Q_OUTOFLINE_TEMPLATE QMapData::Node *QMap<Key, T>::mutableFindNode(QMapData::Node *aupdate[],
755                                                                    const Key &akey) const
756 {
757     QMapData::Node *cur = e;
758     QMapData::Node *next = e;
759
760     for (int i = d->topLevel; i >= 0; i--) {
761         while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
762             cur = next;
763         aupdate[i] = cur;
764     }
765     if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
766         return next;
767     } else {
768         return e;
769     }
770 }
771
772 template <class Key, class T>
773 Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::uniqueKeys() const
774 {
775     QList<Key> res;
776     const_iterator i = begin();
777     if (i != end()) {
778         for (;;) {
779             const Key &aKey = i.key();
780             res.append(aKey);
781             do {
782                 if (++i == end())
783                     goto break_out_of_outer_loop;
784             } while (!(aKey < i.key()));   // loop while (key == i.key())
785         }
786     }
787 break_out_of_outer_loop:
788     return res;
789 }
790
791 template <class Key, class T>
792 Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys() const
793 {
794     QList<Key> res;
795     const_iterator i = begin();
796     while (i != end()) {
797         res.append(i.key());
798         ++i;
799     }
800     return res;
801 }
802
803 template <class Key, class T>
804 Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys(const T &avalue) const
805 {
806     QList<Key> res;
807     const_iterator i = begin();
808     while (i != end()) {
809         if (i.value() == avalue)
810             res.append(i.key());
811         ++i;
812     }
813     return res;
814 }
815
816 template <class Key, class T>
817 Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue) const
818 {
819     return key(avalue, Key());
820 }
821
822 template <class Key, class T>
823 Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue, const Key &defaultKey) const
824 {
825     const_iterator i = begin();
826     while (i != end()) {
827         if (i.value() == avalue)
828             return i.key();
829         ++i;
830     }
831
832     return defaultKey;
833 }
834
835 template <class Key, class T>
836 Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values() const
837 {
838     QList<T> res;
839     const_iterator i = begin();
840     while (i != end()) {
841         res.append(i.value());
842         ++i;
843     }
844     return res;
845 }
846
847 template <class Key, class T>
848 Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values(const Key &akey) const
849 {
850     QList<T> res;
851     QMapData::Node *node = findNode(akey);
852     if (node != e) {
853         do {
854             res.append(concrete(node)->value);
855             node = node->forward[0];
856         } while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));
857     }
858     return res;
859 }
860
861 template <class Key, class T>
862 Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
863 QMap<Key, T>::lowerBound(const Key &akey) const
864 {
865     QMapData::Node *update[QMapData::LastLevel + 1];
866     mutableFindNode(update, akey);
867     return const_iterator(update[0]->forward[0]);
868 }
869
870 template <class Key, class T>
871 Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &akey)
872 {
873     detach();
874     return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->lowerBound(akey));
875 }
876
877 template <class Key, class T>
878 Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
879 QMap<Key, T>::upperBound(const Key &akey) const
880 {
881     QMapData::Node *update[QMapData::LastLevel + 1];
882     mutableFindNode(update, akey);
883     QMapData::Node *node = update[0]->forward[0];
884     while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key))
885         node = node->forward[0];
886     return const_iterator(node);
887 }
888
889 template <class Key, class T>
890 Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &akey)
891 {
892     detach();
893     return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->upperBound(akey));
894 }
895
896 template <class Key, class T>
897 Q_OUTOFLINE_TEMPLATE bool QMap<Key, T>::operator==(const QMap<Key, T> &other) const
898 {
899     if (size() != other.size())
900         return false;
901     if (d == other.d)
902         return true;
903
904     const_iterator it1 = begin();
905     const_iterator it2 = other.begin();
906
907     while (it1 != end()) {
908         if (!(it1.value() == it2.value()) || qMapLessThanKey(it1.key(), it2.key()) || qMapLessThanKey(it2.key(), it1.key()))
909             return false;
910         ++it2;
911         ++it1;
912     }
913     return true;
914 }
915
916 #ifndef QT_NO_STL
917 template <class Key, class T>
918 Q_OUTOFLINE_TEMPLATE QMap<Key, T>::QMap(const std::map<Key, T> &other)
919 {
920     d = QMapData::createData(alignment());
921     d->insertInOrder = true;
922     typename std::map<Key,T>::const_iterator it = other.end();
923     while (it != other.begin()) {
924         --it;
925         insert((*it).first, (*it).second);
926     }
927     d->insertInOrder = false;
928 }
929
930 template <class Key, class T>
931 Q_OUTOFLINE_TEMPLATE std::map<Key, T> QMap<Key, T>::toStdMap() const
932 {
933     std::map<Key, T> map;
934     const_iterator it = end();
935     while (it != begin()) {
936         --it;
937         map.insert(std::pair<Key, T>(it.key(), it.value()));
938     }
939     return map;
940 }
941
942 #endif // QT_NO_STL
943
944 template <class Key, class T>
945 class QMultiMap : public QMap<Key, T>
946 {
947 public:
948     QMultiMap() {}
949     QMultiMap(const QMap<Key, T> &other) : QMap<Key, T>(other) {}
950
951     inline typename QMap<Key, T>::iterator replace(const Key &key, const T &value)
952     { return QMap<Key, T>::insert(key, value); }
953     inline typename QMap<Key, T>::iterator insert(const Key &key, const T &value)
954     { return QMap<Key, T>::insertMulti(key, value); }
955
956     inline QMultiMap &operator+=(const QMultiMap &other)
957     { unite(other); return *this; }
958     inline QMultiMap operator+(const QMultiMap &other) const
959     { QMultiMap result = *this; result += other; return result; }
960
961 #if !defined(Q_NO_USING_KEYWORD) && !defined(Q_CC_RVCT)
962     // RVCT compiler doesn't handle using-keyword right when used functions are overloaded in child class
963     using QMap<Key, T>::contains;
964     using QMap<Key, T>::remove;
965     using QMap<Key, T>::count;
966     using QMap<Key, T>::find;
967     using QMap<Key, T>::constFind;
968 #else
969     inline bool contains(const Key &key) const
970     { return QMap<Key, T>::contains(key); }
971     inline int remove(const Key &key)
972     { return QMap<Key, T>::remove(key); }
973     inline int count(const Key &key) const
974     { return QMap<Key, T>::count(key); }
975     inline int count() const
976     { return QMap<Key, T>::count(); }
977     inline typename QMap<Key, T>::iterator find(const Key &key)
978     { return QMap<Key, T>::find(key); }
979     inline typename QMap<Key, T>::const_iterator find(const Key &key) const
980     { return QMap<Key, T>::find(key); }
981     inline typename QMap<Key, T>::const_iterator constFind(const Key &key) const
982     { return QMap<Key, T>::constFind(key); }
983 #endif
984
985     bool contains(const Key &key, const T &value) const;
986
987     int remove(const Key &key, const T &value);
988
989     int count(const Key &key, const T &value) const;
990
991     typename QMap<Key, T>::iterator find(const Key &key, const T &value) {
992         typename QMap<Key, T>::iterator i(find(key));
993         typename QMap<Key, T>::iterator end(this->end());
994         while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
995             if (i.value() == value)
996                 return i;
997             ++i;
998         }
999         return end;
1000     }
1001     typename QMap<Key, T>::const_iterator find(const Key &key, const T &value) const {
1002         typename QMap<Key, T>::const_iterator i(constFind(key));
1003         typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
1004         while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1005             if (i.value() == value)
1006                 return i;
1007             ++i;
1008         }
1009         return end;
1010     }
1011     typename QMap<Key, T>::const_iterator constFind(const Key &key, const T &value) const
1012         { return find(key, value); }
1013 private:
1014     T &operator[](const Key &key);
1015     const T operator[](const Key &key) const;
1016 };
1017
1018 template <class Key, class T>
1019 Q_INLINE_TEMPLATE bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const
1020 {
1021     return constFind(key, value) != QMap<Key, T>::constEnd();
1022 }
1023
1024 template <class Key, class T>
1025 Q_INLINE_TEMPLATE int QMultiMap<Key, T>::remove(const Key &key, const T &value)
1026 {
1027     int n = 0;
1028     typename QMap<Key, T>::iterator i(find(key));
1029     typename QMap<Key, T>::iterator end(QMap<Key, T>::end());
1030     while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1031         if (i.value() == value) {
1032 #if defined(Q_CC_RVCT)
1033             // RVCT has problems with scoping, apparently.
1034             i = QMap<Key, T>::erase(i);
1035 #else
1036             i = erase(i);
1037 #endif
1038             ++n;
1039         } else {
1040             ++i;
1041         }
1042     }
1043     return n;
1044 }
1045
1046 template <class Key, class T>
1047 Q_INLINE_TEMPLATE int QMultiMap<Key, T>::count(const Key &key, const T &value) const
1048 {
1049     int n = 0;
1050     typename QMap<Key, T>::const_iterator i(constFind(key));
1051     typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
1052     while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1053         if (i.value() == value)
1054             ++n;
1055         ++i;
1056     }
1057     return n;
1058 }
1059
1060 Q_DECLARE_ASSOCIATIVE_ITERATOR(Map)
1061 Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map)
1062
1063 QT_END_NAMESPACE
1064
1065 QT_END_HEADER
1066
1067 #endif // QMAP_H