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