Line data Source code
1 : /****************************************************************************
2 : **
3 : ** Copyright (C) 2013 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/qiterator.h>
46 : #include <QtCore/qlist.h>
47 : #include <QtCore/qrefcount.h>
48 : #include <QtCore/qpair.h>
49 :
50 : #ifdef Q_MAP_DEBUG
51 : #include <QtCore/qdebug.h>
52 : #endif
53 :
54 : #include <map>
55 : #include <new>
56 :
57 : #ifdef Q_COMPILER_INITIALIZER_LISTS
58 : #include <initializer_list>
59 : #endif
60 :
61 : QT_BEGIN_NAMESPACE
62 :
63 : /*
64 : QMap uses qMapLessThanKey() to compare keys. The default
65 : implementation uses operator<(). For pointer types,
66 : qMapLessThanKey() casts the pointers to integers before it
67 : compares them, because operator<() is undefined on pointers
68 : that come from different memory blocks. (In practice, this
69 : is only a problem when running a program such as
70 : BoundsChecker.)
71 : */
72 :
73 176 : template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2)
74 : {
75 176 : return key1 < key2;
76 : }
77 :
78 : template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)
79 : {
80 : Q_STATIC_ASSERT(sizeof(quintptr) == sizeof(const Ptr *));
81 : return quintptr(key1) < quintptr(key2);
82 : }
83 :
84 : struct QMapDataBase;
85 : template <class Key, class T> struct QMapData;
86 :
87 : struct Q_CORE_EXPORT QMapNodeBase
88 : {
89 : quintptr p;
90 : QMapNodeBase *left;
91 : QMapNodeBase *right;
92 :
93 : enum Color { Red = 0, Black = 1 };
94 : enum { Mask = 3 }; // reserve the second bit as well
95 :
96 : const QMapNodeBase *nextNode() const;
97 : QMapNodeBase *nextNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->nextNode()); }
98 : const QMapNodeBase *previousNode() const;
99 : QMapNodeBase *previousNode() { return const_cast<QMapNodeBase *>(const_cast<const QMapNodeBase *>(this)->previousNode()); }
100 :
101 0 : Color color() const { return Color(p & 1); }
102 0 : void setColor(Color c) { if (c == Black) p |= Black; else p &= ~Black; }
103 : QMapNodeBase *parent() const { return reinterpret_cast<QMapNodeBase *>(p & ~Mask); }
104 0 : void setParent(QMapNodeBase *pp) { p = (p & Mask) | quintptr(pp); }
105 : };
106 :
107 : template <class Key, class T>
108 : struct QMapNode : public QMapNodeBase
109 : {
110 : Key key;
111 : T value;
112 :
113 69 : inline QMapNode *leftNode() const { return static_cast<QMapNode *>(left); }
114 65 : inline QMapNode *rightNode() const { return static_cast<QMapNode *>(right); }
115 :
116 11 : inline const QMapNode *nextNode() const { return static_cast<const QMapNode *>(QMapNodeBase::nextNode()); }
117 : inline const QMapNode *previousNode() const { return static_cast<const QMapNode *>(QMapNodeBase::previousNode()); }
118 : inline QMapNode *nextNode() { return static_cast<QMapNode *>(QMapNodeBase::nextNode()); }
119 : inline QMapNode *previousNode() { return static_cast<QMapNode *>(QMapNodeBase::previousNode()); }
120 :
121 : QMapNode<Key, T> *copy(QMapData<Key, T> *d) const;
122 :
123 : void destroySubTree();
124 :
125 : QMapNode<Key, T> *lowerBound(const Key &key);
126 : QMapNode<Key, T> *upperBound(const Key &key);
127 :
128 : private:
129 : QMapNode() Q_DECL_EQ_DELETE;
130 : Q_DISABLE_COPY(QMapNode)
131 : };
132 :
133 : template <class Key, class T>
134 54 : inline QMapNode<Key, T> *QMapNode<Key, T>::lowerBound(const Key &akey)
135 : {
136 54 : QMapNode<Key, T> *n = this;
137 54 : QMapNode<Key, T> *lastNode = 0;
138 196 : while (n) {
139 88 : if (!qMapLessThanKey(n->key, akey)) {
140 60 : lastNode = n;
141 60 : n = n->leftNode();
142 : } else {
143 28 : n = n->rightNode();
144 : }
145 : }
146 54 : return lastNode;
147 : }
148 :
149 : template <class Key, class T>
150 : inline QMapNode<Key, T> *QMapNode<Key, T>::upperBound(const Key &akey)
151 : {
152 : QMapNode<Key, T> *n = this;
153 : QMapNode<Key, T> *lastNode = 0;
154 : while (n) {
155 : if (qMapLessThanKey(akey, n->key)) {
156 : lastNode = n;
157 : n = n->leftNode();
158 : } else {
159 : n = n->rightNode();
160 : }
161 : }
162 : return lastNode;
163 : }
164 :
165 :
166 :
167 : struct Q_CORE_EXPORT QMapDataBase
168 : {
169 : QtPrivate::RefCount ref;
170 : int size;
171 : QMapNodeBase header;
172 : QMapNodeBase *mostLeftNode;
173 :
174 : void rotateLeft(QMapNodeBase *x);
175 : void rotateRight(QMapNodeBase *x);
176 : void rebalance(QMapNodeBase *x);
177 : void freeNodeAndRebalance(QMapNodeBase *z);
178 : void recalcMostLeftNode();
179 :
180 : QMapNodeBase *createNode(int size, int alignment, QMapNodeBase *parent, bool left);
181 : void freeTree(QMapNodeBase *root, int alignment);
182 :
183 : static const QMapDataBase shared_null;
184 :
185 : static QMapDataBase *createData();
186 : static void freeData(QMapDataBase *d);
187 : };
188 :
189 : template <class Key, class T>
190 : struct QMapData : public QMapDataBase
191 : {
192 : typedef QMapNode<Key, T> Node;
193 :
194 140 : Node *root() const { return static_cast<Node *>(header.left); }
195 :
196 : const Node *end() const { return static_cast<const Node *>(&header); }
197 59 : Node *end() { return static_cast<Node *>(&header); }
198 : const Node *begin() const { if (root()) return static_cast<const Node*>(mostLeftNode); return end(); }
199 1 : Node *begin() { if (root()) return static_cast<Node*>(mostLeftNode); return end(); }
200 :
201 : void deleteNode(Node *z);
202 : Node *findNode(const Key &akey) const;
203 : void nodeRange(const Key &akey, Node **firstNode, Node **lastNode);
204 :
205 47 : Node *createNode(const Key &k, const T &v, Node *parent = 0, bool left = false)
206 : {
207 : Node *n = static_cast<Node *>(QMapDataBase::createNode(sizeof(Node), Q_ALIGNOF(Node),
208 47 : parent, left));
209 : QT_TRY {
210 47 : new (&n->key) Key(k);
211 : QT_TRY {
212 47 : new (&n->value) T(v);
213 0 : } QT_CATCH(...) {
214 : n->key.~Key();
215 0 : QT_RETHROW;
216 : }
217 0 : } QT_CATCH(...) {
218 0 : QMapDataBase::freeNodeAndRebalance(n);
219 0 : QT_RETHROW;
220 : }
221 47 : return n;
222 : }
223 :
224 7 : static QMapData *create() {
225 7 : return static_cast<QMapData *>(createData());
226 : }
227 :
228 7 : void destroy() {
229 7 : if (root()) {
230 1 : root()->destroySubTree();
231 1 : freeTree(header.left, Q_ALIGNOF(Node));
232 : }
233 7 : freeData(this);
234 7 : }
235 : };
236 :
237 : template <class Key, class T>
238 0 : QMapNode<Key, T> *QMapNode<Key, T>::copy(QMapData<Key, T> *d) const
239 : {
240 0 : QMapNode<Key, T> *n = d->createNode(key, value);
241 0 : n->setColor(color());
242 0 : if (left) {
243 0 : n->left = leftNode()->copy(d);
244 0 : n->left->setParent(n);
245 : } else {
246 0 : n->left = 0;
247 : }
248 0 : if (right) {
249 0 : n->right = rightNode()->copy(d);
250 0 : n->right->setParent(n);
251 : } else {
252 0 : n->right = 0;
253 : }
254 0 : return n;
255 : }
256 :
257 : #if defined(Q_CC_MSVC)
258 : #pragma warning( push )
259 : #pragma warning( disable : 4127 ) // conditional expression is constant
260 : #endif
261 :
262 : template <class Key, class T>
263 11 : void QMapNode<Key, T>::destroySubTree()
264 : {
265 : if (QTypeInfo<Key>::isComplex)
266 : key.~Key();
267 : if (QTypeInfo<T>::isComplex)
268 11 : value.~T();
269 : if (QTypeInfo<Key>::isComplex || QTypeInfo<T>::isComplex) {
270 11 : if (left)
271 5 : leftNode()->destroySubTree();
272 11 : if (right)
273 5 : rightNode()->destroySubTree();
274 : }
275 11 : }
276 :
277 : #if defined(Q_CC_MSVC)
278 : #pragma warning( pop )
279 : #endif
280 :
281 : template <class Key, class T>
282 36 : void QMapData<Key, T>::deleteNode(QMapNode<Key, T> *z)
283 : {
284 : if (QTypeInfo<Key>::isComplex)
285 : z->key.~Key();
286 : if (QTypeInfo<T>::isComplex)
287 : z->value.~T();
288 36 : freeNodeAndRebalance(z);
289 36 : }
290 :
291 : template <class Key, class T>
292 84 : QMapNode<Key, T> *QMapData<Key, T>::findNode(const Key &akey) const
293 : {
294 84 : if (Node *r = root()) {
295 54 : Node *lb = r->lowerBound(akey);
296 54 : if (lb && !qMapLessThanKey(akey, lb->key))
297 48 : return lb;
298 : }
299 36 : return 0;
300 : }
301 :
302 :
303 : template <class Key, class T>
304 : void QMapData<Key, T>::nodeRange(const Key &akey, QMapNode<Key, T> **firstNode, QMapNode<Key, T> **lastNode)
305 : {
306 : Node *n = root();
307 : Node *l = end();
308 : while (n) {
309 : if (qMapLessThanKey(akey, n->key)) {
310 : l = n;
311 : n = n->leftNode();
312 : } else if (qMapLessThanKey(n->key, akey)) {
313 : n = n->rightNode();
314 : } else {
315 : *firstNode = n->leftNode() ? n->leftNode()->lowerBound(akey) : 0;
316 : if (!*firstNode)
317 : *firstNode = n;
318 : *lastNode = n->rightNode() ? n->rightNode()->upperBound(akey) : 0;
319 : if (!*lastNode)
320 : *lastNode = l;
321 : return;
322 : }
323 : }
324 : *firstNode = *lastNode = l;
325 : }
326 :
327 :
328 : template <class Key, class T>
329 : class QMap
330 : {
331 : typedef QMapNode<Key, T> Node;
332 :
333 : QMapData<Key, T> *d;
334 :
335 : public:
336 6 : inline QMap() : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null))) { }
337 : #ifdef Q_COMPILER_INITIALIZER_LISTS
338 1 : inline QMap(std::initializer_list<std::pair<Key,T> > list)
339 1 : : d(static_cast<QMapData<Key, T> *>(const_cast<QMapDataBase *>(&QMapDataBase::shared_null)))
340 : {
341 12 : for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
342 11 : insert(it->first, it->second);
343 1 : }
344 : #endif
345 : QMap(const QMap<Key, T> &other);
346 :
347 7 : inline ~QMap() { if (!d->ref.deref()) d->destroy(); }
348 :
349 : QMap<Key, T> &operator=(const QMap<Key, T> &other);
350 : #ifdef Q_COMPILER_RVALUE_REFS
351 : inline QMap(QMap<Key, T> &&other)
352 : : d(other.d)
353 : {
354 : other.d = static_cast<QMapData<Key, T> *>(
355 : const_cast<QMapDataBase *>(&QMapDataBase::shared_null));
356 : }
357 :
358 : inline QMap<Key, T> &operator=(QMap<Key, T> &&other)
359 : { qSwap(d, other.d); return *this; }
360 : #endif
361 : inline void swap(QMap<Key, T> &other) { qSwap(d, other.d); }
362 : explicit QMap(const typename std::map<Key, T> &other);
363 : std::map<Key, T> toStdMap() const;
364 :
365 : bool operator==(const QMap<Key, T> &other) const;
366 : inline bool operator!=(const QMap<Key, T> &other) const { return !(*this == other); }
367 :
368 1 : inline int size() const { return d->size; }
369 :
370 : inline bool isEmpty() const { return d->size == 0; }
371 :
372 83 : inline void detach() { if (d->ref.isShared()) detach_helper(); }
373 : inline bool isDetached() const { return !d->ref.isShared(); }
374 : #if QT_SUPPORTS(UNSHARABLE_CONTAINERS)
375 : inline void setSharable(bool sharable)
376 : {
377 : if (sharable == d->ref.isSharable())
378 : return;
379 : if (!sharable)
380 : detach();
381 : // Don't call on shared_null
382 : d->ref.setSharable(sharable);
383 : }
384 : #endif
385 : inline bool isSharedWith(const QMap<Key, T> &other) const { return d == other.d; }
386 :
387 : void clear();
388 :
389 : int remove(const Key &key);
390 : T take(const Key &key);
391 :
392 : bool contains(const Key &key) const;
393 : const Key key(const T &value, const Key &defaultKey = Key()) const;
394 : const T value(const Key &key, const T &defaultValue = T()) const;
395 : T &operator[](const Key &key);
396 : const T operator[](const Key &key) const;
397 :
398 : QList<Key> uniqueKeys() const;
399 : QList<Key> keys() const;
400 : QList<Key> keys(const T &value) const;
401 : QList<T> values() const;
402 : QList<T> values(const Key &key) const;
403 : int count(const Key &key) const;
404 :
405 : inline const Key &firstKey() const { Q_ASSERT(!isEmpty()); return constBegin().key(); }
406 : inline const Key &lastKey() const { Q_ASSERT(!isEmpty()); return (constEnd() - 1).key(); }
407 :
408 : inline T &first() { Q_ASSERT(!isEmpty()); return *begin(); }
409 : inline const T &first() const { Q_ASSERT(!isEmpty()); return *constBegin(); }
410 : inline T &last() { Q_ASSERT(!isEmpty()); return *(end() - 1); }
411 : inline const T &last() const { Q_ASSERT(!isEmpty()); return *(constEnd() - 1); }
412 :
413 : class const_iterator;
414 :
415 : class iterator
416 : {
417 : friend class const_iterator;
418 : Node *i;
419 :
420 : public:
421 : typedef std::bidirectional_iterator_tag iterator_category;
422 : typedef qptrdiff difference_type;
423 : typedef T value_type;
424 : typedef T *pointer;
425 : typedef T &reference;
426 :
427 : inline iterator() : i(0) { }
428 47 : inline iterator(Node *node) : i(node) { }
429 :
430 : inline const Key &key() const { return i->key; }
431 : inline T &value() const { return i->value; }
432 : inline T &operator*() const { return i->value; }
433 : inline T *operator->() const { return &i->value; }
434 : inline bool operator==(const iterator &o) const { return i == o.i; }
435 : inline bool operator!=(const iterator &o) const { return i != o.i; }
436 :
437 : inline iterator &operator++() {
438 : i = i->nextNode();
439 : return *this;
440 : }
441 : inline iterator operator++(int) {
442 : iterator r = *this;
443 : i = i->nextNode();
444 : return r;
445 : }
446 : inline iterator &operator--() {
447 : i = i->previousNode();
448 : return *this;
449 : }
450 : inline iterator operator--(int) {
451 : iterator r = *this;
452 : i = i->previousNode();
453 : return r;
454 : }
455 : inline iterator operator+(int j) const
456 : { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
457 : inline iterator operator-(int j) const { return operator+(-j); }
458 : inline iterator &operator+=(int j) { return *this = *this + j; }
459 : inline iterator &operator-=(int j) { return *this = *this - j; }
460 :
461 : #ifndef QT_STRICT_ITERATORS
462 : public:
463 : inline bool operator==(const const_iterator &o) const
464 : { return i == o.i; }
465 : inline bool operator!=(const const_iterator &o) const
466 : { return i != o.i; }
467 : #endif
468 : friend class QMap<Key, T>;
469 : };
470 : friend class iterator;
471 :
472 : class const_iterator
473 : {
474 : friend class iterator;
475 : const Node *i;
476 :
477 : public:
478 : typedef std::bidirectional_iterator_tag iterator_category;
479 : typedef qptrdiff difference_type;
480 : typedef T value_type;
481 : typedef const T *pointer;
482 : typedef const T &reference;
483 :
484 : inline const_iterator() : i(0) { }
485 13 : inline const_iterator(const Node *node) : i(node) { }
486 : #ifdef QT_STRICT_ITERATORS
487 : explicit inline const_iterator(const iterator &o)
488 : #else
489 : inline const_iterator(const iterator &o)
490 : #endif
491 : { i = o.i; }
492 :
493 11 : inline const Key &key() const { return i->key; }
494 : inline const T &value() const { return i->value; }
495 : inline const T &operator*() const { return i->value; }
496 : inline const T *operator->() const { return &i->value; }
497 : inline bool operator==(const const_iterator &o) const { return i == o.i; }
498 12 : inline bool operator!=(const const_iterator &o) const { return i != o.i; }
499 :
500 11 : inline const_iterator &operator++() {
501 11 : i = i->nextNode();
502 11 : return *this;
503 : }
504 : inline const_iterator operator++(int) {
505 : const_iterator r = *this;
506 : i = i->nextNode();
507 : return r;
508 : }
509 : inline const_iterator &operator--() {
510 : i = i->previousNode();
511 : return *this;
512 : }
513 : inline const_iterator operator--(int) {
514 : const_iterator r = *this;
515 : i = i->previousNode();
516 : return r;
517 : }
518 : inline const_iterator operator+(int j) const
519 : { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
520 : inline const_iterator operator-(int j) const { return operator+(-j); }
521 : inline const_iterator &operator+=(int j) { return *this = *this + j; }
522 : inline const_iterator &operator-=(int j) { return *this = *this - j; }
523 :
524 : #ifdef QT_STRICT_ITERATORS
525 : private:
526 : inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); }
527 : inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); }
528 : #endif
529 : friend class QMap<Key, T>;
530 : };
531 : friend class const_iterator;
532 :
533 : // STL style
534 : inline iterator begin() { detach(); return iterator(d->begin()); }
535 1 : inline const_iterator begin() const { return const_iterator(d->begin()); }
536 : inline const_iterator constBegin() const { return const_iterator(d->begin()); }
537 : inline const_iterator cbegin() const { return const_iterator(d->begin()); }
538 : inline iterator end() { detach(); return iterator(d->end()); }
539 12 : inline const_iterator end() const { return const_iterator(d->end()); }
540 : inline const_iterator constEnd() const { return const_iterator(d->end()); }
541 : inline const_iterator cend() const { return const_iterator(d->end()); }
542 : iterator erase(iterator it);
543 :
544 : // more Qt
545 : typedef iterator Iterator;
546 : typedef const_iterator ConstIterator;
547 : inline int count() const { return d->size; }
548 : iterator find(const Key &key);
549 : const_iterator find(const Key &key) const;
550 : const_iterator constFind(const Key &key) const;
551 : iterator lowerBound(const Key &key);
552 : const_iterator lowerBound(const Key &key) const;
553 : iterator upperBound(const Key &key);
554 : const_iterator upperBound(const Key &key) const;
555 : iterator insert(const Key &key, const T &value);
556 : iterator insert(const_iterator pos, const Key &key, const T &value);
557 : iterator insertMulti(const Key &key, const T &value);
558 : iterator insertMulti(const_iterator pos, const Key &akey, const T &avalue);
559 : QMap<Key, T> &unite(const QMap<Key, T> &other);
560 :
561 : // STL compatibility
562 : typedef Key key_type;
563 : typedef T mapped_type;
564 : typedef qptrdiff difference_type;
565 : typedef int size_type;
566 : inline bool empty() const { return isEmpty(); }
567 : QPair<iterator, iterator> equal_range(const Key &akey);
568 :
569 : #ifdef Q_MAP_DEBUG
570 : void dump() const;
571 : #endif
572 :
573 : private:
574 : void detach_helper();
575 : bool isValidIterator(const const_iterator &ci) const
576 : {
577 : #if defined(QT_DEBUG) && !defined(Q_MAP_NO_ITERATOR_DEBUG)
578 : const QMapNodeBase *n = ci.i;
579 : while (n->parent())
580 : n = n->parent();
581 : return n->left == d->root();
582 : #else
583 : Q_UNUSED(ci);
584 : return true;
585 : #endif
586 : }
587 : };
588 :
589 : template <class Key, class T>
590 : inline QMap<Key, T>::QMap(const QMap<Key, T> &other)
591 : {
592 : if (other.d->ref.ref()) {
593 : d = other.d;
594 : } else {
595 : d = QMapData<Key, T>::create();
596 : if (other.d->header.left) {
597 : d->header.left = static_cast<Node *>(other.d->header.left)->copy(d);
598 : d->header.left->setParent(&d->header);
599 : d->recalcMostLeftNode();
600 : }
601 : }
602 : }
603 :
604 : template <class Key, class T>
605 : Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)
606 : {
607 : if (d != other.d) {
608 : QMap<Key, T> tmp(other);
609 : tmp.swap(*this);
610 : }
611 : return *this;
612 : }
613 :
614 : template <class Key, class T>
615 : Q_INLINE_TEMPLATE void QMap<Key, T>::clear()
616 : {
617 : *this = QMap<Key, T>();
618 : }
619 :
620 :
621 : template <class Key, class T>
622 12 : Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey, const T &adefaultValue) const
623 : {
624 12 : Node *n = d->findNode(akey);
625 12 : return n ? n->value : adefaultValue;
626 : }
627 :
628 : template <class Key, class T>
629 : Q_INLINE_TEMPLATE const T QMap<Key, T>::operator[](const Key &akey) const
630 : {
631 : return value(akey);
632 : }
633 :
634 : template <class Key, class T>
635 : Q_INLINE_TEMPLATE T &QMap<Key, T>::operator[](const Key &akey)
636 : {
637 : detach();
638 : Node *n = d->findNode(akey);
639 : if (!n)
640 : return *insert(akey, T());
641 : return n->value;
642 : }
643 :
644 : template <class Key, class T>
645 : Q_INLINE_TEMPLATE int QMap<Key, T>::count(const Key &akey) const
646 : {
647 : Node *firstNode;
648 : Node *lastNode;
649 : d->nodeRange(akey, &firstNode, &lastNode);
650 :
651 : const_iterator ci_first(firstNode);
652 : const const_iterator ci_last(lastNode);
653 : int cnt = 0;
654 : while (ci_first != ci_last) {
655 : ++cnt;
656 : ++ci_first;
657 : }
658 : return cnt;
659 : }
660 :
661 : template <class Key, class T>
662 : Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const
663 : {
664 : return d->findNode(akey) != 0;
665 : }
666 :
667 : template <class Key, class T>
668 47 : Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey, const T &avalue)
669 : {
670 47 : detach();
671 47 : Node *n = d->root();
672 47 : Node *y = d->end();
673 47 : Node *lastNode = 0;
674 47 : bool left = true;
675 130 : while (n) {
676 36 : y = n;
677 36 : if (!qMapLessThanKey(n->key, akey)) {
678 4 : lastNode = n;
679 4 : left = true;
680 4 : n = n->leftNode();
681 : } else {
682 32 : left = false;
683 32 : n = n->rightNode();
684 : }
685 : }
686 47 : if (lastNode && !qMapLessThanKey(akey, lastNode->key)) {
687 0 : lastNode->value = avalue;
688 0 : return iterator(lastNode);
689 : }
690 47 : Node *z = d->createNode(akey, avalue, y, left);
691 47 : return iterator(z);
692 : }
693 :
694 : template <class Key, class T>
695 : typename QMap<Key, T>::iterator QMap<Key, T>::insert(const_iterator pos, const Key &akey, const T &avalue)
696 : {
697 : if (d->ref.isShared())
698 : return this->insert(akey, avalue);
699 :
700 : Q_ASSERT_X(isValidIterator(pos), "QMap::insert", "The specified const_iterator argument 'it' is invalid");
701 :
702 : if (pos == constEnd()) {
703 : // Hint is that the Node is larger than (or equal to) the largest value.
704 : Node *n = static_cast<Node *>(pos.i->left);
705 : if (n) {
706 : while (n->right)
707 : n = static_cast<Node *>(n->right);
708 :
709 : if (!qMapLessThanKey(n->key, akey))
710 : return this->insert(akey, avalue); // ignore hint
711 : // This can be optimized by checking equal too.
712 : // we can overwrite if previous node key is strictly smaller
713 : // (or there is no previous node)
714 :
715 : Node *z = d->createNode(akey, avalue, n, false); // insert right most
716 : return iterator(z);
717 : }
718 : return this->insert(akey, avalue);
719 : } else {
720 : // Hint indicates that the node should be less (or equal to) the hint given
721 : // but larger than the previous value.
722 : Node *next = const_cast<Node*>(pos.i);
723 : if (qMapLessThanKey(next->key, akey))
724 : return this->insert(akey, avalue); // ignore hint
725 :
726 : if (pos == constBegin()) {
727 : // There is no previous value
728 : // Maybe overwrite left most value
729 : if (!qMapLessThanKey(akey, next->key)) {
730 : next->value = avalue; // overwrite current iterator
731 : return iterator(next);
732 : }
733 : // insert left most.
734 : Node *z = d->createNode(akey, avalue, begin().i, true);
735 : return iterator(z);
736 : } else {
737 : Node *prev = const_cast<Node*>(pos.i->previousNode());
738 : if (!qMapLessThanKey(prev->key, akey)) {
739 : return this->insert(akey, avalue); // ignore hint
740 : }
741 : // Hint is ok
742 : if (!qMapLessThanKey(akey, next->key)) {
743 : next->value = avalue; // overwrite current iterator
744 : return iterator(next);
745 : }
746 :
747 : // we need to insert (not overwrite)
748 : if (prev->right == 0) {
749 : Node *z = d->createNode(akey, avalue, prev, false);
750 : return iterator(z);
751 : }
752 : if (next->left == 0) {
753 : Node *z = d->createNode(akey, avalue, next, true);
754 : return iterator(z);
755 : }
756 : Q_ASSERT(false); // We should have prev->right == 0 or next->left == 0.
757 : return this->insert(akey, avalue);
758 : }
759 : }
760 : }
761 :
762 : template <class Key, class T>
763 : Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &akey,
764 : const T &avalue)
765 : {
766 : detach();
767 : Node* y = d->end();
768 : Node* x = static_cast<Node *>(d->root());
769 : bool left = true;
770 : while (x != 0) {
771 : left = !qMapLessThanKey(x->key, akey);
772 : y = x;
773 : x = left ? x->leftNode() : x->rightNode();
774 : }
775 : Node *z = d->createNode(akey, avalue, y, left);
776 : return iterator(z);
777 : }
778 :
779 : template <class Key, class T>
780 : typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const_iterator pos, const Key &akey, const T &avalue)
781 : {
782 : if (d->ref.isShared())
783 : return this->insertMulti(akey, avalue);
784 :
785 : Q_ASSERT_X(isValidIterator(pos), "QMap::insertMulti", "The specified const_iterator argument 'pos' is invalid");
786 :
787 : if (pos == constEnd()) {
788 : // Hint is that the Node is larger than (or equal to) the largest value.
789 : Node *n = static_cast<Node *>(pos.i->left);
790 : if (n) {
791 : while (n->right)
792 : n = static_cast<Node *>(n->right);
793 :
794 : if (!qMapLessThanKey(n->key, akey))
795 : return this->insertMulti(akey, avalue); // ignore hint
796 : Node *z = d->createNode(akey, avalue, n, false); // insert right most
797 : return iterator(z);
798 : }
799 : return this->insertMulti(akey, avalue);
800 : } else {
801 : // Hint indicates that the node should be less (or equal to) the hint given
802 : // but larger than the previous value.
803 : Node *next = const_cast<Node*>(pos.i);
804 : if (qMapLessThanKey(next->key, akey))
805 : return this->insertMulti(akey, avalue); // ignore hint
806 :
807 : if (pos == constBegin()) {
808 : // There is no previous value (insert left most)
809 : Node *z = d->createNode(akey, avalue, begin().i, true);
810 : return iterator(z);
811 : } else {
812 : Node *prev = const_cast<Node*>(pos.i->previousNode());
813 : if (!qMapLessThanKey(prev->key, akey))
814 : return this->insertMulti(akey, avalue); // ignore hint
815 :
816 : // Hint is ok - do insert
817 : if (prev->right == 0) {
818 : Node *z = d->createNode(akey, avalue, prev, false);
819 : return iterator(z);
820 : }
821 : if (next->left == 0) {
822 : Node *z = d->createNode(akey, avalue, next, true);
823 : return iterator(z);
824 : }
825 : Q_ASSERT(false); // We should have prev->right == 0 or next->left == 0.
826 : return this->insertMulti(akey, avalue);
827 : }
828 : }
829 : }
830 :
831 :
832 : template <class Key, class T>
833 : Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::constFind(const Key &akey) const
834 : {
835 : Node *n = d->findNode(akey);
836 : return const_iterator(n ? n : d->end());
837 : }
838 :
839 : template <class Key, class T>
840 : Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const
841 : {
842 : return constFind(akey);
843 : }
844 :
845 : template <class Key, class T>
846 : Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::find(const Key &akey)
847 : {
848 : detach();
849 : Node *n = d->findNode(akey);
850 : return iterator(n ? n : d->end());
851 : }
852 :
853 : template <class Key, class T>
854 : Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other)
855 : {
856 : QMap<Key, T> copy(other);
857 : const_iterator it = copy.constEnd();
858 : const const_iterator b = copy.constBegin();
859 : while (it != b) {
860 : --it;
861 : insertMulti(it.key(), it.value());
862 : }
863 : return *this;
864 : }
865 :
866 : template <class Key, class T>
867 : QPair<typename QMap<Key, T>::iterator, typename QMap<Key, T>::iterator> QMap<Key, T>::equal_range(const Key &akey)
868 : {
869 : detach();
870 : Node *firstNode, *lastNode;
871 : d->nodeRange(akey, &firstNode, &lastNode);
872 : return QPair<iterator, iterator>(iterator(firstNode), iterator(lastNode));
873 : }
874 :
875 : #ifdef Q_MAP_DEBUG
876 : template <class Key, class T>
877 : void QMap<Key, T>::dump() const
878 : {
879 : const_iterator it = begin();
880 : qDebug() << "map dump:";
881 : while (it != end()) {
882 : const QMapNodeBase *n = it.i;
883 : int depth = 0;
884 : while (n && n != d->root()) {
885 : ++depth;
886 : n = n->parent();
887 : }
888 : QByteArray space(4*depth, ' ');
889 : qDebug() << space << (it.i->color() == Node::Red ? "Red " : "Black") << it.i << it.i->left << it.i->right
890 : << it.key() << it.value();
891 : ++it;
892 : }
893 : qDebug() << "---------";
894 : }
895 : #endif
896 :
897 : template <class Key, class T>
898 36 : Q_OUTOFLINE_TEMPLATE int QMap<Key, T>::remove(const Key &akey)
899 : {
900 36 : detach();
901 36 : int n = 0;
902 72 : while (Node *node = d->findNode(akey)) {
903 36 : d->deleteNode(node);
904 36 : ++n;
905 : }
906 36 : return n;
907 : }
908 :
909 : template <class Key, class T>
910 : Q_OUTOFLINE_TEMPLATE T QMap<Key, T>::take(const Key &akey)
911 : {
912 : detach();
913 :
914 : Node *node = d->findNode(akey);
915 : if (node) {
916 : T t = node->value;
917 : d->deleteNode(node);
918 : return t;
919 : }
920 : return T();
921 : }
922 :
923 : template <class Key, class T>
924 : Q_OUTOFLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::erase(iterator it)
925 : {
926 : if (it == iterator(d->end()))
927 : return it;
928 :
929 : Q_ASSERT_X(isValidIterator(const_iterator(it)), "QMap::erase", "The specified iterator argument 'it' is invalid");
930 :
931 : if (d->ref.isShared()) {
932 : const_iterator oldBegin = constBegin();
933 : const_iterator old = const_iterator(it);
934 : int backStepsWithSameKey = 0;
935 :
936 : while (old != oldBegin) {
937 : --old;
938 : if (qMapLessThanKey(old.key(), it.key()))
939 : break;
940 : ++backStepsWithSameKey;
941 : }
942 :
943 : it = find(old.key()); // ensures detach
944 : Q_ASSERT_X(it != iterator(d->end()), "QMap::erase", "Unable to locate same key in erase after detach.");
945 :
946 : while (backStepsWithSameKey > 0) {
947 : ++it;
948 : --backStepsWithSameKey;
949 : }
950 : }
951 :
952 : Node *n = it.i;
953 : ++it;
954 : d->deleteNode(n);
955 : return it;
956 : }
957 :
958 : template <class Key, class T>
959 7 : Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper()
960 : {
961 7 : QMapData<Key, T> *x = QMapData<Key, T>::create();
962 7 : if (d->header.left) {
963 0 : x->header.left = static_cast<Node *>(d->header.left)->copy(x);
964 0 : x->header.left->setParent(&x->header);
965 : }
966 7 : if (!d->ref.deref())
967 0 : d->destroy();
968 7 : d = x;
969 7 : d->recalcMostLeftNode();
970 7 : }
971 :
972 : template <class Key, class T>
973 : Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::uniqueKeys() const
974 : {
975 : QList<Key> res;
976 : res.reserve(size()); // May be too much, but assume short lifetime
977 : const_iterator i = begin();
978 : if (i != end()) {
979 : for (;;) {
980 : const Key &aKey = i.key();
981 : res.append(aKey);
982 : do {
983 : if (++i == end())
984 : goto break_out_of_outer_loop;
985 : } while (!qMapLessThanKey(aKey, i.key())); // loop while (key == i.key())
986 : }
987 : }
988 : break_out_of_outer_loop:
989 : return res;
990 : }
991 :
992 : template <class Key, class T>
993 1 : Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys() const
994 : {
995 1 : QList<Key> res;
996 1 : res.reserve(size());
997 1 : const_iterator i = begin();
998 13 : while (i != end()) {
999 11 : res.append(i.key());
1000 11 : ++i;
1001 : }
1002 1 : return res;
1003 : }
1004 :
1005 : template <class Key, class T>
1006 : Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys(const T &avalue) const
1007 : {
1008 : QList<Key> res;
1009 : const_iterator i = begin();
1010 : while (i != end()) {
1011 : if (i.value() == avalue)
1012 : res.append(i.key());
1013 : ++i;
1014 : }
1015 : return res;
1016 : }
1017 :
1018 : template <class Key, class T>
1019 : Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue, const Key &defaultKey) const
1020 : {
1021 : const_iterator i = begin();
1022 : while (i != end()) {
1023 : if (i.value() == avalue)
1024 : return i.key();
1025 : ++i;
1026 : }
1027 :
1028 : return defaultKey;
1029 : }
1030 :
1031 : template <class Key, class T>
1032 : Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values() const
1033 : {
1034 : QList<T> res;
1035 : res.reserve(size());
1036 : const_iterator i = begin();
1037 : while (i != end()) {
1038 : res.append(i.value());
1039 : ++i;
1040 : }
1041 : return res;
1042 : }
1043 :
1044 : template <class Key, class T>
1045 : Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values(const Key &akey) const
1046 : {
1047 : QList<T> res;
1048 : Node *n = d->findNode(akey);
1049 : if (n) {
1050 : const_iterator it(n);
1051 : do {
1052 : res.append(*it);
1053 : ++it;
1054 : } while (it != constEnd() && !qMapLessThanKey<Key>(akey, it.key()));
1055 : }
1056 : return res;
1057 : }
1058 :
1059 : template <class Key, class T>
1060 : Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::lowerBound(const Key &akey) const
1061 : {
1062 : Node *lb = d->root() ? d->root()->lowerBound(akey) : 0;
1063 : if (!lb)
1064 : lb = d->end();
1065 : return const_iterator(lb);
1066 : }
1067 :
1068 : template <class Key, class T>
1069 : Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &akey)
1070 : {
1071 : detach();
1072 : Node *lb = d->root() ? d->root()->lowerBound(akey) : 0;
1073 : if (!lb)
1074 : lb = d->end();
1075 : return iterator(lb);
1076 : }
1077 :
1078 : template <class Key, class T>
1079 : Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
1080 : QMap<Key, T>::upperBound(const Key &akey) const
1081 : {
1082 : Node *ub = d->root() ? d->root()->upperBound(akey) : 0;
1083 : if (!ub)
1084 : ub = d->end();
1085 : return const_iterator(ub);
1086 : }
1087 :
1088 : template <class Key, class T>
1089 : Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &akey)
1090 : {
1091 : detach();
1092 : Node *ub = d->root() ? d->root()->upperBound(akey) : 0;
1093 : if (!ub)
1094 : ub = d->end();
1095 : return iterator(ub);
1096 : }
1097 :
1098 : template <class Key, class T>
1099 : Q_OUTOFLINE_TEMPLATE bool QMap<Key, T>::operator==(const QMap<Key, T> &other) const
1100 : {
1101 : if (size() != other.size())
1102 : return false;
1103 : if (d == other.d)
1104 : return true;
1105 :
1106 : const_iterator it1 = begin();
1107 : const_iterator it2 = other.begin();
1108 :
1109 : while (it1 != end()) {
1110 : if (!(it1.value() == it2.value()) || qMapLessThanKey(it1.key(), it2.key()) || qMapLessThanKey(it2.key(), it1.key()))
1111 : return false;
1112 : ++it2;
1113 : ++it1;
1114 : }
1115 : return true;
1116 : }
1117 :
1118 : template <class Key, class T>
1119 : Q_OUTOFLINE_TEMPLATE QMap<Key, T>::QMap(const std::map<Key, T> &other)
1120 : {
1121 : d = QMapData<Key, T>::create();
1122 : typename std::map<Key,T>::const_iterator it = other.end();
1123 : while (it != other.begin()) {
1124 : --it;
1125 : d->createNode((*it).first, (*it).second, d->begin(), true); // insert on most left node.
1126 : }
1127 : }
1128 :
1129 : template <class Key, class T>
1130 : Q_OUTOFLINE_TEMPLATE std::map<Key, T> QMap<Key, T>::toStdMap() const
1131 : {
1132 : std::map<Key, T> map;
1133 : const_iterator it = end();
1134 : while (it != begin()) {
1135 : --it;
1136 : map.insert(map.begin(), std::pair<Key, T>(it.key(), it.value()));
1137 : }
1138 : return map;
1139 : }
1140 :
1141 : template <class Key, class T>
1142 : class QMultiMap : public QMap<Key, T>
1143 : {
1144 : public:
1145 : QMultiMap() {}
1146 : #ifdef Q_COMPILER_INITIALIZER_LISTS
1147 : inline QMultiMap(std::initializer_list<std::pair<Key,T> > list)
1148 : {
1149 : for (typename std::initializer_list<std::pair<Key,T> >::const_iterator it = list.begin(); it != list.end(); ++it)
1150 : insert(it->first, it->second);
1151 : }
1152 : #endif
1153 : QMultiMap(const QMap<Key, T> &other) : QMap<Key, T>(other) {}
1154 : inline void swap(QMultiMap<Key, T> &other) { QMap<Key, T>::swap(other); }
1155 :
1156 : inline typename QMap<Key, T>::iterator replace(const Key &key, const T &value)
1157 : { return QMap<Key, T>::insert(key, value); }
1158 : inline typename QMap<Key, T>::iterator insert(const Key &key, const T &value)
1159 : { return QMap<Key, T>::insertMulti(key, value); }
1160 : inline typename QMap<Key, T>::iterator insert(typename QMap<Key, T>::const_iterator pos, const Key &key, const T &value)
1161 : { return QMap<Key, T>::insertMulti(pos, key, value); }
1162 :
1163 : inline QMultiMap &operator+=(const QMultiMap &other)
1164 : { this->unite(other); return *this; }
1165 : inline QMultiMap operator+(const QMultiMap &other) const
1166 : { QMultiMap result = *this; result += other; return result; }
1167 :
1168 : #if !defined(Q_NO_USING_KEYWORD) && !defined(Q_CC_RVCT)
1169 : // RVCT compiler doesn't handle using-keyword right when used functions are overloaded in child class
1170 : using QMap<Key, T>::contains;
1171 : using QMap<Key, T>::remove;
1172 : using QMap<Key, T>::count;
1173 : using QMap<Key, T>::find;
1174 : using QMap<Key, T>::constFind;
1175 : #else
1176 : inline bool contains(const Key &key) const
1177 : { return QMap<Key, T>::contains(key); }
1178 : inline int remove(const Key &key)
1179 : { return QMap<Key, T>::remove(key); }
1180 : inline int count(const Key &key) const
1181 : { return QMap<Key, T>::count(key); }
1182 : inline int count() const
1183 : { return QMap<Key, T>::count(); }
1184 : inline typename QMap<Key, T>::iterator find(const Key &key)
1185 : { return QMap<Key, T>::find(key); }
1186 : inline typename QMap<Key, T>::const_iterator find(const Key &key) const
1187 : { return QMap<Key, T>::find(key); }
1188 : inline typename QMap<Key, T>::const_iterator constFind(const Key &key) const
1189 : { return QMap<Key, T>::constFind(key); }
1190 : #endif
1191 :
1192 : bool contains(const Key &key, const T &value) const;
1193 :
1194 : int remove(const Key &key, const T &value);
1195 :
1196 : int count(const Key &key, const T &value) const;
1197 :
1198 : typename QMap<Key, T>::iterator find(const Key &key, const T &value) {
1199 : typename QMap<Key, T>::iterator i(find(key));
1200 : typename QMap<Key, T>::iterator end(this->end());
1201 : while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1202 : if (i.value() == value)
1203 : return i;
1204 : ++i;
1205 : }
1206 : return end;
1207 : }
1208 : typename QMap<Key, T>::const_iterator find(const Key &key, const T &value) const {
1209 : typename QMap<Key, T>::const_iterator i(constFind(key));
1210 : typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
1211 : while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1212 : if (i.value() == value)
1213 : return i;
1214 : ++i;
1215 : }
1216 : return end;
1217 : }
1218 : typename QMap<Key, T>::const_iterator constFind(const Key &key, const T &value) const
1219 : { return find(key, value); }
1220 : private:
1221 : T &operator[](const Key &key);
1222 : const T operator[](const Key &key) const;
1223 : };
1224 :
1225 : template <class Key, class T>
1226 : Q_INLINE_TEMPLATE bool QMultiMap<Key, T>::contains(const Key &key, const T &value) const
1227 : {
1228 : return constFind(key, value) != QMap<Key, T>::constEnd();
1229 : }
1230 :
1231 : template <class Key, class T>
1232 : Q_INLINE_TEMPLATE int QMultiMap<Key, T>::remove(const Key &key, const T &value)
1233 : {
1234 : int n = 0;
1235 : typename QMap<Key, T>::iterator i(find(key));
1236 : typename QMap<Key, T>::iterator end(QMap<Key, T>::end());
1237 : while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1238 : if (i.value() == value) {
1239 : i = this->erase(i);
1240 : ++n;
1241 : } else {
1242 : ++i;
1243 : }
1244 : }
1245 : return n;
1246 : }
1247 :
1248 : template <class Key, class T>
1249 : Q_INLINE_TEMPLATE int QMultiMap<Key, T>::count(const Key &key, const T &value) const
1250 : {
1251 : int n = 0;
1252 : typename QMap<Key, T>::const_iterator i(constFind(key));
1253 : typename QMap<Key, T>::const_iterator end(QMap<Key, T>::constEnd());
1254 : while (i != end && !qMapLessThanKey<Key>(key, i.key())) {
1255 : if (i.value() == value)
1256 : ++n;
1257 : ++i;
1258 : }
1259 : return n;
1260 : }
1261 :
1262 : Q_DECLARE_ASSOCIATIVE_ITERATOR(Map)
1263 : Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map)
1264 :
1265 : QT_END_NAMESPACE
1266 :
1267 : #endif // QMAP_H
|
