← Back to branch summary

~oif-team/ubuntu/natty/qt4-x11/xi2.1

« back to all changes in this revision

Viewing changes to src/corelib/tools/qmap.h

  • Committer: Bazaar Package Importer
  • Author(s): Adam Conrad
  • Date: 2005-08-24 04:09:09 UTC
  • Revision ID: james.westby@ubuntu.com-20050824040909-xmxe9jfr4a0w5671
Tags: upstream-4.0.0
Import upstream version 4.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/corelib/tools/qmap.h
 
1
/****************************************************************************
 
2
**
 
3
** Copyright (C) 1992-2005 Trolltech AS. All rights reserved.
 
4
**
 
5
** This file is part of the core module of the Qt Toolkit.
 
6
**
 
7
** This file may be distributed under the terms of the Q Public License
 
8
** as defined by Trolltech AS of Norway and appearing in the file
 
9
** LICENSE.QPL included in the packaging of this file.
 
10
**
 
11
** This file may be distributed and/or modified under the terms of the
 
12
** GNU General Public License version 2 as published by the Free Software
 
13
** Foundation and appearing in the file LICENSE.GPL included in the
 
14
** packaging of this file.
 
15
**
 
16
** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for
 
17
**   information about Qt Commercial License Agreements.
 
18
** See http://www.trolltech.com/qpl/ for QPL licensing information.
 
19
** See http://www.trolltech.com/gpl/ for GPL licensing information.
 
20
**
 
21
** Contact info@trolltech.com if any conditions of this licensing are
 
22
** not clear to you.
 
23
**
 
24
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
 
25
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 
26
**
 
27
****************************************************************************/
 
28
 
 
29
#ifndef QMAP_H
 
30
#define QMAP_H
 
31
 
 
32
#include "QtCore/qatomic.h"
 
33
#include "QtCore/qiterator.h"
 
34
#include "QtCore/qlist.h"
 
35
 
 
36
#ifndef QT_NO_STL
 
37
#include <map>
 
38
#endif
 
39
 
 
40
#include <new>
 
41
 
 
42
struct Q_CORE_EXPORT QMapData
 
43
{
 
44
    struct Node {
 
45
        Node *backward;
 
46
        Node *forward[1];
 
47
    };
 
48
    enum { LastLevel = 11, Sparseness = 3 };
 
49
 
 
50
    Node *backward;
 
51
    Node *forward[QMapData::LastLevel + 1];
 
52
    QBasicAtomic ref;
 
53
    int topLevel;
 
54
    int size;
 
55
    uint randomBits;
 
56
    uint insertInOrder : 1;
 
57
    uint sharable : 1;
 
58
 
 
59
    static QMapData *createData();
 
60
    void continueFreeData(int offset);
 
61
    Node *node_create(Node *update[], int offset);
 
62
    void node_delete(Node *update[], int offset, Node *node);
 
63
#ifdef QT_QMAP_DEBUG
 
64
    uint adjust_ptr(Node *node);
 
65
    void dump();
 
66
#endif
 
67
 
 
68
    static QMapData shared_null;
 
69
};
 
70
 
 
71
 
 
72
/*
 
73
    QMap uses qMapLessThanKey() to compare keys. The default
 
74
    implementation uses operator<(). For pointer types,
 
75
    qMapLessThanKey() casts the pointers to integers before it
 
76
    compares them, because operator<() is undefined on pointers
 
77
    that come from different memory blocks. (In practice, this
 
78
    is only a problem when running a program such as
 
79
    BoundsChecker.)
 
80
*/
 
81
 
 
82
template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2)
 
83
{
 
84
    return key1 < key2;
 
85
}
 
86
 
 
87
#ifndef QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
 
88
template <class Ptr> inline bool qMapLessThanKey(Ptr *key1, Ptr *key2)
 
89
{
 
90
    Q_ASSERT(sizeof(ulong) == sizeof(Ptr *));
 
91
    return reinterpret_cast<ulong>(key1) < reinterpret_cast<ulong>(key2);
 
92
}
 
93
 
 
94
template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)
 
95
{
 
96
    Q_ASSERT(sizeof(ulong) == sizeof(const Ptr *));
 
97
    return reinterpret_cast<ulong>(key1) < reinterpret_cast<ulong>(key2);
 
98
}
 
99
#endif // QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
 
100
 
 
101
#if !defined(QT_NO_DATASTREAM)
 
102
class QDataStream;
 
103
template <class Key, class T> class QMap;
 
104
template <class aKey, class aT>
 
105
QDataStream &operator>>(QDataStream &in, QMap<aKey, aT> &map);
 
106
#endif
 
107
 
 
108
template <class Key, class T>
 
109
class QMap
 
110
{
 
111
    struct Node {
 
112
        Key key;
 
113
        T value;
 
114
        QMapData::Node *backward;
 
115
        QMapData::Node *forward[1];
 
116
    };
 
117
    union {
 
118
        QMapData *d;
 
119
        QMapData::Node *e;
 
120
    };
 
121
 
 
122
    struct PayloadNode
 
123
    {
 
124
        Key key;
 
125
        T value;
 
126
        QMapData::Node *backward;
 
127
    };
 
128
    enum { Payload = sizeof(PayloadNode) - sizeof(QMapData::Node *) };
 
129
 
 
130
    static inline Node *concrete(QMapData::Node *node) {
 
131
        return reinterpret_cast<Node *>(reinterpret_cast<char *>(node) - Payload);
 
132
    }
 
133
public:
 
134
    inline QMap() : d(&QMapData::shared_null) { d->ref.ref(); }
 
135
    inline QMap(const QMap<Key, T> &other) : d(other.d)
 
136
    { d->ref.ref(); if (!d->sharable) detach(); }
 
137
    inline ~QMap() { if (!d) return; if (!d->ref.deref()) freeData(d); }
 
138
 
 
139
    QMap<Key, T> &operator=(const QMap<Key, T> &other);
 
140
#ifndef QT_NO_STL
 
141
    explicit QMap(const typename std::map<Key, T> &other);
 
142
    std::map<Key, T> toStdMap() const;
 
143
#endif
 
144
 
 
145
    bool operator==(const QMap<Key, T> &other) const;
 
146
    inline bool operator!=(const QMap<Key, T> &other) const { return !(*this == other); }
 
147
 
 
148
    inline int size() const { return d->size; }
 
149
 
 
150
    inline bool isEmpty() const { return d->size == 0; }
 
151
 
 
152
    inline void detach() { if (d->ref != 1) detach_helper(); }
 
153
    inline bool isDetached() const { return d->ref == 1; }
 
154
    inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
 
155
 
 
156
    void clear();
 
157
 
 
158
    int remove(const Key &key);
 
159
    T take(const Key &key);
 
160
 
 
161
    bool contains(const Key &key) const;
 
162
    const Key key(const T &value) const;
 
163
    const T value(const Key &key) const;
 
164
    const T value(const Key &key, const T &defaultValue) const;
 
165
    T &operator[](const Key &key);
 
166
    const T operator[](const Key &key) const;
 
167
 
 
168
    QList<Key> keys() const;
 
169
    QList<Key> keys(const T &value) const;
 
170
    QList<T> values() const;
 
171
    QList<T> values(const Key &key) const;
 
172
    int count(const Key &key) const;
 
173
 
 
174
    class const_iterator;
 
175
 
 
176
    class iterator
 
177
    {
 
178
        QMapData::Node *i;
 
179
    public:
 
180
        typedef std::bidirectional_iterator_tag iterator_category;
 
181
        typedef ptrdiff_t difference_type;
 
182
        typedef T value_type;
 
183
        typedef T *pointer;
 
184
        typedef T &reference;
 
185
 
 
186
        inline operator QMapData::Node *() const { return i; }
 
187
        inline iterator() : i(0) { }
 
188
        inline iterator(QMapData::Node *node) : i(node) { }
 
189
 
 
190
        inline const Key &key() const { return concrete(i)->key; }
 
191
        inline T &value() const { return concrete(i)->value; }
 
192
#ifdef QT3_SUPPORT
 
193
        inline QT3_SUPPORT T &data() const { return concrete(i)->value; }
 
194
#endif
 
195
        inline T &operator*() const { return concrete(i)->value; }
 
196
        inline T *operator->() const { return &concrete(i)->value; }
 
197
        inline bool operator==(const iterator &o) const { return i == o.i; }
 
198
        inline bool operator!=(const iterator &o) const { return i != o.i; }
 
199
        inline bool operator==(const const_iterator &o) const
 
200
            { return i == reinterpret_cast<const iterator &>(o).i; }
 
201
        inline bool operator!=(const const_iterator &o) const
 
202
            { return i != reinterpret_cast<const iterator &>(o).i; }
 
203
 
 
204
        inline iterator &operator++() {
 
205
            i = i->forward[0];
 
206
            return *this;
 
207
        }
 
208
        inline iterator operator++(int) {
 
209
            iterator r = *this;
 
210
            i = i->forward[0];
 
211
            return r;
 
212
        }
 
213
        inline iterator &operator--() {
 
214
            i = i->backward;
 
215
            return *this;
 
216
        }
 
217
        inline iterator operator--(int) {
 
218
            iterator r = *this;
 
219
            i = i->backward;
 
220
            return r;
 
221
        }
 
222
        inline iterator operator+(int j) const
 
223
        { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
 
224
        inline iterator operator-(int j) const { return operator+(-j); }
 
225
        inline iterator &operator+=(int j) { return *this = *this + j; }
 
226
        inline iterator &operator-=(int j) { return *this = *this - j; }
 
227
    };
 
228
    friend class iterator;
 
229
 
 
230
    class const_iterator
 
231
    {
 
232
        QMapData::Node *i;
 
233
    public:
 
234
        typedef std::bidirectional_iterator_tag iterator_category;
 
235
        typedef ptrdiff_t difference_type;
 
236
        typedef T value_type;
 
237
        typedef T *pointer;
 
238
        typedef T &reference;
 
239
 
 
240
        inline operator QMapData::Node *() const { return i; }
 
241
        inline const_iterator() : i(0) { }
 
242
        inline const_iterator(QMapData::Node *node) : i(node) { }
 
243
        inline const_iterator(const iterator &o)
 
244
        { i = reinterpret_cast<const const_iterator &>(o).i; }
 
245
 
 
246
        inline const Key &key() const { return concrete(i)->key; }
 
247
        inline const T &value() const { return concrete(i)->value; }
 
248
#ifdef QT3_SUPPORT
 
249
        inline QT3_SUPPORT const T &data() const { return concrete(i)->value; }
 
250
#endif
 
251
        inline const T &operator*() const { return concrete(i)->value; }
 
252
        inline const T *operator->() const { return &concrete(i)->value; }
 
253
        inline bool operator==(const const_iterator &o) const { return i == o.i; }
 
254
        inline bool operator!=(const const_iterator &o) const { return i != o.i; }
 
255
 
 
256
        inline const_iterator &operator++() {
 
257
            i = i->forward[0];
 
258
            return *this;
 
259
        }
 
260
        inline const_iterator operator++(int) {
 
261
            const_iterator r = *this;
 
262
            i = i->forward[0];
 
263
            return r;
 
264
        }
 
265
        inline const_iterator &operator--() {
 
266
            i = i->backward;
 
267
            return *this;
 
268
        }
 
269
        inline const_iterator operator--(int) {
 
270
            iterator r = *this;
 
271
            i = i->backward;
 
272
            return r;
 
273
        }
 
274
        inline const_iterator operator+(int j) const
 
275
        { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
 
276
        inline const_iterator operator-(int j) const { return operator+(-j); }
 
277
        inline const_iterator &operator+=(int j) { return *this = *this + j; }
 
278
        inline const_iterator &operator-=(int j) { return *this = *this - j; }
 
279
    };
 
280
    friend class const_iterator;
 
281
 
 
282
    // STL style
 
283
    inline iterator begin() { detach(); return iterator(e->forward[0]); }
 
284
    inline const_iterator begin() const { return const_iterator(e->forward[0]); }
 
285
    inline const_iterator constBegin() const { return const_iterator(e->forward[0]); }
 
286
    inline iterator end() {
 
287
        detach();
 
288
        return iterator(e);
 
289
    }
 
290
    inline const_iterator end() const { return const_iterator(e); }
 
291
    inline const_iterator constEnd() const { return const_iterator(e); }
 
292
    iterator erase(iterator it);
 
293
#ifdef QT3_SUPPORT
 
294
    inline QT3_SUPPORT iterator remove(iterator it) { return erase(it); }
 
295
    inline QT3_SUPPORT void erase(const Key &key) { remove(key); }
 
296
#endif
 
297
 
 
298
    // more Qt
 
299
    typedef iterator Iterator;
 
300
    typedef const_iterator ConstIterator;
 
301
    inline int count() const { return d->size; }
 
302
    iterator find(const Key &key);
 
303
    const_iterator find(const Key &key) const;
 
304
    iterator lowerBound(const Key &key);
 
305
    const_iterator lowerBound(const Key &key) const;
 
306
    iterator upperBound(const Key &key);
 
307
    const_iterator upperBound(const Key &key) const;
 
308
    iterator insert(const Key &key, const T &value);
 
309
#ifdef QT3_SUPPORT
 
310
    QT3_SUPPORT iterator insert(const Key &key, const T &value, bool overwrite);
 
311
#endif
 
312
    iterator insertMulti(const Key &key, const T &value);
 
313
#ifdef QT3_SUPPORT
 
314
    inline QT3_SUPPORT iterator replace(const Key &key, const T &value) { return insert(key, value); }
 
315
#endif
 
316
    QMap<Key, T> &unite(const QMap<Key, T> &other);
 
317
 
 
318
    // STL compatibility
 
319
    inline bool empty() const { return isEmpty(); }
 
320
 
 
321
private:
 
322
    void detach_helper();
 
323
    void freeData(QMapData *d);
 
324
    QMapData::Node *findNode(const Key &key) const;
 
325
    QMapData::Node *mutableFindNode(QMapData::Node *update[], const Key &key) const;
 
326
    QMapData::Node *node_create(QMapData *d, QMapData::Node *update[], const Key &key,
 
327
                                const T &value);
 
328
 
 
329
#if !defined(QT_NO_DATASTREAM)
 
330
#if !defined(Q_CC_BOR)
 
331
#if defined Q_CC_MSVC && _MSC_VER < 1300
 
332
    friend QDataStream &operator>> (QDataStream &in, QMap &map);
 
333
#else
 
334
    template <class aKey, class aT>
 
335
    friend QDataStream &operator>> (QDataStream &in, QMap<aKey, aT> &map);
 
336
#endif
 
337
#endif
 
338
#endif
 
339
};
 
340
 
 
341
template <class Key, class T>
 
342
Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::operator=(const QMap<Key, T> &other)
 
343
{
 
344
    if (d != other.d) {
 
345
        QMapData *x = other.d;
 
346
        x->ref.ref();
 
347
        x = qAtomicSetPtr(&d, x);
 
348
        if (!x->ref.deref())
 
349
            freeData(x);
 
350
        if (!d->sharable)
 
351
            detach_helper();
 
352
    }
 
353
    return *this;
 
354
}
 
355
 
 
356
template <class Key, class T>
 
357
Q_INLINE_TEMPLATE void QMap<Key, T>::clear()
 
358
{
 
359
    *this = QMap<Key, T>();
 
360
}
 
361
 
 
362
template <class Key, class T>
 
363
Q_INLINE_TEMPLATE typename QMapData::Node *
 
364
QMap<Key, T>::node_create(QMapData *adt, QMapData::Node *aupdate[], const Key &akey, const T &avalue)
 
365
{
 
366
    QMapData::Node *abstractNode = adt->node_create(aupdate, Payload);
 
367
    Node *concreteNode = concrete(abstractNode);
 
368
    new (&concreteNode->key) Key(akey);
 
369
    new (&concreteNode->value) T(avalue);
 
370
    return abstractNode;
 
371
}
 
372
 
 
373
template <class Key, class T>
 
374
Q_INLINE_TEMPLATE QMapData::Node *QMap<Key, T>::findNode(const Key &akey) const
 
375
{
 
376
    QMapData::Node *cur = e;
 
377
    QMapData::Node *next = e;
 
378
 
 
379
    for (int i = d->topLevel; i >= 0; i--) {
 
380
        while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
 
381
            cur = next;
 
382
    }
 
383
 
 
384
    if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
 
385
        return next;
 
386
    } else {
 
387
        return e;
 
388
    }
 
389
}
 
390
 
 
391
template <class Key, class T>
 
392
Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey) const
 
393
{
 
394
    QMapData::Node *node = findNode(akey);
 
395
    if (node == e) {
 
396
        return T();
 
397
    } else {
 
398
        return concrete(node)->value;
 
399
    }
 
400
}
 
401
 
 
402
template <class Key, class T>
 
403
Q_INLINE_TEMPLATE const T QMap<Key, T>::value(const Key &akey, const T &adefaultValue) const
 
404
{
 
405
    QMapData::Node *node = findNode(akey);
 
406
    if (node == e) {
 
407
        return adefaultValue;
 
408
    } else {
 
409
        return concrete(node)->value;
 
410
    }
 
411
}
 
412
 
 
413
template <class Key, class T>
 
414
Q_INLINE_TEMPLATE const T QMap<Key, T>::operator[](const Key &akey) const
 
415
{
 
416
    return value(akey);
 
417
}
 
418
 
 
419
template <class Key, class T>
 
420
Q_INLINE_TEMPLATE T &QMap<Key, T>::operator[](const Key &akey)
 
421
{
 
422
    detach();
 
423
 
 
424
    QMapData::Node *update[QMapData::LastLevel + 1];
 
425
    QMapData::Node *node = mutableFindNode(update, akey);
 
426
    if (node == e)
 
427
        node = node_create(d, update, akey, T());
 
428
    return concrete(node)->value;
 
429
}
 
430
 
 
431
template <class Key, class T>
 
432
Q_INLINE_TEMPLATE int QMap<Key, T>::count(const Key &akey) const
 
433
{
 
434
    int cnt = 0;
 
435
    QMapData::Node *node = findNode(akey);
 
436
    if (node != e) {
 
437
        do {
 
438
            ++cnt;
 
439
            node = node->forward[0];
 
440
        } while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));
 
441
    }
 
442
    return cnt;
 
443
}
 
444
 
 
445
template <class Key, class T>
 
446
Q_INLINE_TEMPLATE bool QMap<Key, T>::contains(const Key &akey) const
 
447
{
 
448
    return findNode(akey) != e;
 
449
}
 
450
 
 
451
template <class Key, class T>
 
452
Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey,
 
453
                                                                       const T &avalue)
 
454
{
 
455
    detach();
 
456
 
 
457
    QMapData::Node *update[QMapData::LastLevel + 1];
 
458
    QMapData::Node *node = mutableFindNode(update, akey);
 
459
    if (node == e) {
 
460
        node = node_create(d, update, akey, avalue);
 
461
    } else {
 
462
        concrete(node)->value = avalue;
 
463
    }
 
464
    return iterator(node);
 
465
}
 
466
 
 
467
#ifdef QT3_SUPPORT
 
468
template <class Key, class T>
 
469
Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insert(const Key &akey,
 
470
                                                                       const T &avalue,
 
471
                                                                       bool aoverwrite)
 
472
{
 
473
    detach();
 
474
 
 
475
    QMapData::Node *update[QMapData::LastLevel + 1];
 
476
    QMapData::Node *node = mutableFindNode(update, akey);
 
477
    if (node == e) {
 
478
        node = node_create(d, update, akey, avalue);
 
479
    } else {
 
480
        if (aoverwrite)
 
481
            concrete(node)->value = avalue;
 
482
    }
 
483
    return iterator(node);
 
484
}
 
485
#endif
 
486
 
 
487
template <class Key, class T>
 
488
Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::insertMulti(const Key &akey,
 
489
                                                                            const T &avalue)
 
490
{
 
491
    detach();
 
492
 
 
493
    QMapData::Node *update[QMapData::LastLevel + 1];
 
494
    mutableFindNode(update, akey);
 
495
    return iterator(node_create(d, update, akey, avalue));
 
496
}
 
497
 
 
498
template <class Key, class T>
 
499
Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator QMap<Key, T>::find(const Key &akey) const
 
500
{
 
501
    return const_iterator(findNode(akey));
 
502
}
 
503
 
 
504
template <class Key, class T>
 
505
Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::find(const Key &akey)
 
506
{
 
507
    detach();
 
508
    return iterator(findNode(akey));
 
509
}
 
510
 
 
511
template <class Key, class T>
 
512
Q_INLINE_TEMPLATE QMap<Key, T> &QMap<Key, T>::unite(const QMap<Key, T> &other)
 
513
{
 
514
    QMap<Key, T> copy(other);
 
515
    const_iterator it = copy.constEnd();
 
516
    while (it != copy.constBegin()) {
 
517
        --it;
 
518
        insertMulti(it.key(), it.value());
 
519
    }
 
520
    return *this;
 
521
}
 
522
 
 
523
template <class Key, class T>
 
524
Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::freeData(QMapData *x)
 
525
{
 
526
    if (QTypeInfo<Key>::isComplex || QTypeInfo<T>::isComplex) {
 
527
        QMapData::Node *y = reinterpret_cast<QMapData::Node *>(x);
 
528
        QMapData::Node *cur = y;
 
529
        QMapData::Node *next = cur->forward[0];
 
530
        while (next != y) {
 
531
            cur = next;
 
532
            next = cur->forward[0];
 
533
            Node *concreteNode = concrete(cur);
 
534
            concreteNode->key.~Key();
 
535
            concreteNode->value.~T();
 
536
        }
 
537
    }
 
538
    x->continueFreeData(Payload);
 
539
}
 
540
 
 
541
template <class Key, class T>
 
542
Q_OUTOFLINE_TEMPLATE int QMap<Key, T>::remove(const Key &akey)
 
543
{
 
544
    detach();
 
545
 
 
546
    QMapData::Node *update[QMapData::LastLevel + 1];
 
547
    QMapData::Node *cur = e;
 
548
    QMapData::Node *next = e;
 
549
    int oldSize = d->size;
 
550
 
 
551
    for (int i = d->topLevel; i >= 0; i--) {
 
552
        while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
 
553
            cur = next;
 
554
        update[i] = cur;
 
555
    }
 
556
 
 
557
    if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
 
558
        bool deleteNext = true;
 
559
        do {
 
560
            cur = next;
 
561
            next = cur->forward[0];
 
562
            deleteNext = (next != e && !qMapLessThanKey<Key>(concrete(cur)->key, concrete(next)->key));
 
563
            concrete(cur)->key.~Key();
 
564
            concrete(cur)->value.~T();
 
565
            d->node_delete(update, Payload, cur);
 
566
        } while (deleteNext);
 
567
    }
 
568
    return oldSize - d->size;
 
569
}
 
570
 
 
571
template <class Key, class T>
 
572
Q_OUTOFLINE_TEMPLATE T QMap<Key, T>::take(const Key &akey)
 
573
{
 
574
    detach();
 
575
 
 
576
    QMapData::Node *update[QMapData::LastLevel + 1];
 
577
    QMapData::Node *cur = e;
 
578
    QMapData::Node *next = e;
 
579
 
 
580
    for (int i = d->topLevel; i >= 0; i--) {
 
581
        while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
 
582
            cur = next;
 
583
        update[i] = cur;
 
584
    }
 
585
 
 
586
    if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
 
587
        T t = concrete(next)->value;
 
588
        concrete(next)->key.~Key();
 
589
        concrete(next)->value.~T();
 
590
        d->node_delete(update, Payload, next);
 
591
        return t;
 
592
    }
 
593
    return T();
 
594
}
 
595
 
 
596
template <class Key, class T>
 
597
Q_OUTOFLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::erase(iterator it)
 
598
{
 
599
    QMapData::Node *update[QMapData::LastLevel + 1];
 
600
    QMapData::Node *cur = e;
 
601
    QMapData::Node *next = e;
 
602
 
 
603
    if (it == iterator(e))
 
604
        return it;
 
605
 
 
606
    for (int i = d->topLevel; i >= 0; i--) {
 
607
        while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, it.key()))
 
608
            cur = next;
 
609
        update[i] = cur;
 
610
    }
 
611
 
 
612
    while (next != e) {
 
613
        cur = next;
 
614
        next = cur->forward[0];
 
615
        if (cur == it) {
 
616
            concrete(cur)->key.~Key();
 
617
            concrete(cur)->value.~T();
 
618
            d->node_delete(update, Payload, cur);
 
619
            return iterator(next);
 
620
        }
 
621
 
 
622
        for (int i = 0; i <= d->topLevel; ++i) {
 
623
            if (update[i]->forward[i] != cur)
 
624
                break;
 
625
            update[i] = cur;
 
626
        }
 
627
    }
 
628
    return end();
 
629
}
 
630
 
 
631
template <class Key, class T>
 
632
Q_OUTOFLINE_TEMPLATE void QMap<Key, T>::detach_helper()
 
633
{
 
634
    union { QMapData *d; QMapData::Node *e; } x;
 
635
    x.d = QMapData::createData();
 
636
    if (d->size) {
 
637
        x.d->insertInOrder = true;
 
638
        QMapData::Node *update[QMapData::LastLevel + 1];
 
639
        QMapData::Node *cur = e->forward[0];
 
640
        update[0] = x.e;
 
641
        while (cur != e) {
 
642
            Node *concreteNode = concrete(cur);
 
643
            node_create(x.d, update, concreteNode->key, concreteNode->value);
 
644
            cur = cur->forward[0];
 
645
        }
 
646
        x.d->insertInOrder = false;
 
647
    }
 
648
    x.d = qAtomicSetPtr(&d, x.d);
 
649
    if (!x.d->ref.deref())
 
650
        freeData(x.d);
 
651
}
 
652
 
 
653
template <class Key, class T>
 
654
Q_OUTOFLINE_TEMPLATE QMapData::Node *QMap<Key, T>::mutableFindNode(QMapData::Node *aupdate[],
 
655
                                                                   const Key &akey) const
 
656
{
 
657
    QMapData::Node *cur = e;
 
658
    QMapData::Node *next = e;
 
659
 
 
660
    for (int i = d->topLevel; i >= 0; i--) {
 
661
        while ((next = cur->forward[i]) != e && qMapLessThanKey<Key>(concrete(next)->key, akey))
 
662
            cur = next;
 
663
        aupdate[i] = cur;
 
664
    }
 
665
    if (next != e && !qMapLessThanKey<Key>(akey, concrete(next)->key)) {
 
666
        return next;
 
667
    } else {
 
668
        return e;
 
669
    }
 
670
}
 
671
 
 
672
template <class Key, class T>
 
673
Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys() const
 
674
{
 
675
    QList<Key> res;
 
676
    const_iterator i = begin();
 
677
    while (i != end()) {
 
678
        res.append(i.key());
 
679
        ++i;
 
680
    }
 
681
    return res;
 
682
}
 
683
 
 
684
template <class Key, class T>
 
685
Q_OUTOFLINE_TEMPLATE QList<Key> QMap<Key, T>::keys(const T &avalue) const
 
686
{
 
687
    QList<Key> res;
 
688
    const_iterator i = begin();
 
689
    while (i != end()) {
 
690
        if (i.value() == avalue)
 
691
            res.append(i.key());
 
692
        ++i;
 
693
    }
 
694
    return res;
 
695
}
 
696
 
 
697
template <class Key, class T>
 
698
Q_OUTOFLINE_TEMPLATE const Key QMap<Key, T>::key(const T &avalue) const
 
699
{
 
700
    const_iterator i = begin();
 
701
    while (i != end()) {
 
702
        if (i.value() == avalue)
 
703
            return i.key();
 
704
        ++i;
 
705
    }
 
706
 
 
707
    return Key();
 
708
}
 
709
 
 
710
template <class Key, class T>
 
711
Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values() const
 
712
{
 
713
    QList<T> res;
 
714
    const_iterator i = begin();
 
715
    while (i != end()) {
 
716
        res.append(i.value());
 
717
        ++i;
 
718
    }
 
719
    return res;
 
720
}
 
721
 
 
722
template <class Key, class T>
 
723
Q_OUTOFLINE_TEMPLATE QList<T> QMap<Key, T>::values(const Key &akey) const
 
724
{
 
725
    QList<T> res;
 
726
    QMapData::Node *node = findNode(akey);
 
727
    if (node != e) {
 
728
        do {
 
729
            res.append(concrete(node)->value);
 
730
            node = node->forward[0];
 
731
        } while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key));
 
732
    }
 
733
    return res;
 
734
}
 
735
 
 
736
template <class Key, class T>
 
737
Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
 
738
QMap<Key, T>::lowerBound(const Key &akey) const
 
739
{
 
740
    QMapData::Node *update[QMapData::LastLevel + 1];
 
741
    mutableFindNode(update, akey);
 
742
    return const_iterator(update[0]->forward[0]);
 
743
}
 
744
 
 
745
template <class Key, class T>
 
746
Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::lowerBound(const Key &akey)
 
747
{
 
748
    detach();
 
749
    return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->lowerBound(akey));
 
750
}
 
751
 
 
752
template <class Key, class T>
 
753
Q_INLINE_TEMPLATE typename QMap<Key, T>::const_iterator
 
754
QMap<Key, T>::upperBound(const Key &akey) const
 
755
{
 
756
    QMapData::Node *update[QMapData::LastLevel + 1];
 
757
    mutableFindNode(update, akey);
 
758
    QMapData::Node *node = update[0]->forward[0];
 
759
    while (node != e && !qMapLessThanKey<Key>(akey, concrete(node)->key))
 
760
        node = node->forward[0];
 
761
    return const_iterator(node);
 
762
}
 
763
 
 
764
template <class Key, class T>
 
765
Q_INLINE_TEMPLATE typename QMap<Key, T>::iterator QMap<Key, T>::upperBound(const Key &akey)
 
766
{
 
767
    detach();
 
768
    return static_cast<QMapData::Node *>(const_cast<const QMap *>(this)->upperBound(akey));
 
769
}
 
770
 
 
771
template <class Key, class T>
 
772
Q_OUTOFLINE_TEMPLATE bool QMap<Key, T>::operator==(const QMap<Key, T> &other) const
 
773
{
 
774
    if (size() != other.size())
 
775
        return false;
 
776
    if (d == other.d)
 
777
        return true;
 
778
 
 
779
    const_iterator it1 = begin();
 
780
    const_iterator it2 = other.begin();
 
781
 
 
782
    while (it1 != end()) {
 
783
        if (!(it1.value() == it2.value()) || qMapLessThanKey(it1.key(), it2.key()) || qMapLessThanKey(it2.key(), it1.key()))
 
784
            return false;
 
785
        ++it2;
 
786
        ++it1;
 
787
    }
 
788
    return true;
 
789
}
 
790
 
 
791
#ifndef QT_NO_STL
 
792
template <class Key, class T>
 
793
Q_OUTOFLINE_TEMPLATE QMap<Key, T>::QMap(const std::map<Key, T> &other)
 
794
{
 
795
    d = QMapData::createData();
 
796
    d->insertInOrder = true;
 
797
    typename std::map<Key,T>::const_iterator it = other.end();
 
798
    while (it != other.begin()) {
 
799
        --it;
 
800
        insert((*it).first, (*it).second);
 
801
    }
 
802
    d->insertInOrder = false;
 
803
}
 
804
 
 
805
template <class Key, class T>
 
806
Q_OUTOFLINE_TEMPLATE  std::map<Key, T> QMap<Key, T>::toStdMap() const
 
807
{
 
808
    std::map<Key, T> map;
 
809
    const_iterator it = end();
 
810
    while (it != begin()) {
 
811
        --it;
 
812
        map.insert((*it).first, (*it).second);
 
813
    }
 
814
    return map;
 
815
}
 
816
 
 
817
#endif // QT_NO_STL
 
818
 
 
819
template <class Key, class T>
 
820
class QMultiMap : public QMap<Key, T>
 
821
{
 
822
public:
 
823
    QMultiMap() {}
 
824
    QMultiMap(const QMap<Key, T> &other) : QMap<Key, T>(other) {}
 
825
 
 
826
    inline typename QMap<Key, T>::iterator replace(const Key &key, const T &value);
 
827
    inline typename QMap<Key, T>::iterator insert(const Key &key, const T &value);
 
828
 
 
829
    inline QMultiMap &operator+=(const QMultiMap &other)
 
830
    { unite(other); return *this; }
 
831
    inline QMultiMap operator+(const QMultiMap &other) const
 
832
    { QMultiMap result = *this; result += other; return result; }
 
833
 
 
834
private:
 
835
    T &operator[](const Key &key);
 
836
    const T operator[](const Key &key) const;
 
837
};
 
838
 
 
839
template <class Key, class T>
 
840
Q_INLINE_TEMPLATE Q_TYPENAME QMap<Key, T>::iterator QMultiMap<Key, T>::replace(const Key &akey, const T &avalue)
 
841
{ return QMap<Key, T>::insert(akey, avalue); }
 
842
 
 
843
template <class Key, class T>
 
844
Q_INLINE_TEMPLATE Q_TYPENAME QMap<Key, T>::iterator QMultiMap<Key, T>::insert(const Key &akey, const T &avalue)
 
845
{ return QMap<Key, T>::insertMulti(akey, avalue); }
 
846
 
 
847
 
 
848
Q_DECLARE_ASSOCIATIVE_ITERATOR(Map)
 
849
Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Map)
 
850
 
 
851
#endif // QMAP_H