source: trunk/src/corelib/tools/qmap.h@ 175

Last change on this file since 175 was 2, checked in by Dmitry A. Kuminov, 16 years ago

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