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