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