← Back to branch summary

~ubuntu-branches/ubuntu/wily/qtbase-opensource-src/wily

« back to all changes in this revision

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

  • Committer: Package Import Robot
  • Author(s): Timo Jyrinki
  • Date: 2013-02-05 12:46:17 UTC
  • Revision ID: package-import@ubuntu.com-20130205124617-c8jouts182j002fx
Tags: upstream-5.0.1+dfsg
Import upstream version 5.0.1+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/corelib/tools/qhash.h
 
1
/****************************************************************************
 
2
**
 
3
** Copyright (C) 2012 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 QHASH_H
 
43
#define QHASH_H
 
44
 
 
45
#include <QtCore/qchar.h>
 
46
#include <QtCore/qiterator.h>
 
47
#include <QtCore/qlist.h>
 
48
#include <QtCore/qpair.h>
 
49
#include <QtCore/qrefcount.h>
 
50
 
 
51
QT_BEGIN_HEADER
 
52
 
 
53
QT_BEGIN_NAMESPACE
 
54
 
 
55
class QBitArray;
 
56
class QByteArray;
 
57
class QString;
 
58
class QStringRef;
 
59
class QLatin1String;
 
60
 
 
61
inline uint qHash(char key, uint seed = 0) Q_DECL_NOTHROW { return uint(key) ^ seed; }
 
62
inline uint qHash(uchar key, uint seed = 0) Q_DECL_NOTHROW { return uint(key) ^ seed; }
 
63
inline uint qHash(signed char key, uint seed = 0) Q_DECL_NOTHROW { return uint(key) ^ seed; }
 
64
inline uint qHash(ushort key, uint seed = 0) Q_DECL_NOTHROW { return uint(key) ^ seed; }
 
65
inline uint qHash(short key, uint seed = 0) Q_DECL_NOTHROW { return uint(key) ^ seed; }
 
66
inline uint qHash(uint key, uint seed = 0) Q_DECL_NOTHROW { return key ^ seed; }
 
67
inline uint qHash(int key, uint seed = 0) Q_DECL_NOTHROW { return uint(key) ^ seed; }
 
68
inline uint qHash(ulong key, uint seed = 0) Q_DECL_NOTHROW
 
69
{
 
70
    if (sizeof(ulong) > sizeof(uint)) {
 
71
        return uint(((key >> (8 * sizeof(uint) - 1)) ^ key) & (~0U)) ^ seed;
 
72
    } else {
 
73
        return uint(key & (~0U)) ^ seed;
 
74
    }
 
75
}
 
76
inline uint qHash(long key, uint seed = 0) Q_DECL_NOTHROW { return qHash(ulong(key), seed); }
 
77
inline uint qHash(quint64 key, uint seed = 0) Q_DECL_NOTHROW
 
78
{
 
79
    if (sizeof(quint64) > sizeof(uint)) {
 
80
        return uint(((key >> (8 * sizeof(uint) - 1)) ^ key) & (~0U)) ^ seed;
 
81
    } else {
 
82
        return uint(key & (~0U)) ^ seed;
 
83
    }
 
84
}
 
85
inline uint qHash(qint64 key, uint seed = 0) Q_DECL_NOTHROW { return qHash(quint64(key), seed); }
 
86
inline uint qHash(QChar key, uint seed = 0) Q_DECL_NOTHROW { return qHash(key.unicode(), seed); }
 
87
Q_CORE_EXPORT uint qHash(const QByteArray &key, uint seed = 0) Q_DECL_NOTHROW;
 
88
Q_CORE_EXPORT uint qHash(const QString &key, uint seed = 0) Q_DECL_NOTHROW;
 
89
Q_CORE_EXPORT uint qHash(const QStringRef &key, uint seed = 0) Q_DECL_NOTHROW;
 
90
Q_CORE_EXPORT uint qHash(const QBitArray &key, uint seed = 0) Q_DECL_NOTHROW;
 
91
Q_CORE_EXPORT uint qHash(QLatin1String key, uint seed = 0) Q_DECL_NOTHROW;
 
92
Q_CORE_EXPORT uint qt_hash(const QString &key) Q_DECL_NOTHROW;
 
93
 
 
94
#if defined(Q_CC_MSVC)
 
95
#pragma warning( push )
 
96
#pragma warning( disable : 4311 ) // disable pointer truncation warning
 
97
#endif
 
98
template <class T> inline uint qHash(const T *key, uint seed = 0) Q_DECL_NOTHROW
 
99
{
 
100
    return qHash(reinterpret_cast<quintptr>(key), seed);
 
101
}
 
102
#if defined(Q_CC_MSVC)
 
103
#pragma warning( pop )
 
104
#endif
 
105
 
 
106
template<typename T> inline uint qHash(const T &t, uint seed)
 
107
    Q_DECL_NOEXCEPT_EXPR(noexcept(qHash(t)))
 
108
{ return (qHash(t) ^ seed); }
 
109
 
 
110
template <typename T1, typename T2> inline uint qHash(const QPair<T1, T2> &key, uint seed = 0)
 
111
    Q_DECL_NOEXCEPT_EXPR(noexcept(qHash(key.first, seed)) && noexcept(qHash(key.second, seed)))
 
112
{
 
113
    uint h1 = qHash(key.first, seed);
 
114
    uint h2 = qHash(key.second, seed);
 
115
    return ((h1 << 16) | (h1 >> 16)) ^ h2 ^ seed;
 
116
}
 
117
 
 
118
struct Q_CORE_EXPORT QHashData
 
119
{
 
120
    struct Node {
 
121
        Node *next;
 
122
        uint h;
 
123
    };
 
124
 
 
125
    Node *fakeNext;
 
126
    Node **buckets;
 
127
    QtPrivate::RefCount ref;
 
128
    int size;
 
129
    int nodeSize;
 
130
    short userNumBits;
 
131
    short numBits;
 
132
    int numBuckets;
 
133
    uint seed;
 
134
    uint sharable : 1;
 
135
    uint strictAlignment : 1;
 
136
    uint reserved : 30;
 
137
 
 
138
    void *allocateNode(int nodeAlign);
 
139
    void freeNode(void *node);
 
140
    QHashData *detach_helper(void (*node_duplicate)(Node *, void *), void (*node_delete)(Node *),
 
141
                             int nodeSize, int nodeAlign);
 
142
    bool willGrow();
 
143
    void hasShrunk();
 
144
    void rehash(int hint);
 
145
    void free_helper(void (*node_delete)(Node *));
 
146
    Node *firstNode();
 
147
#ifdef QT_QHASH_DEBUG
 
148
    void dump();
 
149
    void checkSanity();
 
150
#endif
 
151
    static Node *nextNode(Node *node);
 
152
    static Node *previousNode(Node *node);
 
153
 
 
154
    static const QHashData shared_null;
 
155
};
 
156
 
 
157
inline bool QHashData::willGrow()
 
158
{
 
159
    if (size >= numBuckets) {
 
160
        rehash(numBits + 1);
 
161
        return true;
 
162
    } else {
 
163
        return false;
 
164
    }
 
165
}
 
166
 
 
167
inline void QHashData::hasShrunk()
 
168
{
 
169
    if (size <= (numBuckets >> 3) && numBits > userNumBits) {
 
170
        QT_TRY {
 
171
            rehash(qMax(int(numBits) - 2, int(userNumBits)));
 
172
        } QT_CATCH(const std::bad_alloc &) {
 
173
            // ignore bad allocs - shrinking shouldn't throw. rehash is exception safe.
 
174
        }
 
175
    }
 
176
}
 
177
 
 
178
inline QHashData::Node *QHashData::firstNode()
 
179
{
 
180
    Node *e = reinterpret_cast<Node *>(this);
 
181
    Node **bucket = buckets;
 
182
    int n = numBuckets;
 
183
    while (n--) {
 
184
        if (*bucket != e)
 
185
            return *bucket;
 
186
        ++bucket;
 
187
    }
 
188
    return e;
 
189
}
 
190
 
 
191
struct QHashDummyValue
 
192
{
 
193
};
 
194
 
 
195
inline bool operator==(const QHashDummyValue & /* v1 */, const QHashDummyValue & /* v2 */)
 
196
{
 
197
    return true;
 
198
}
 
199
 
 
200
Q_DECLARE_TYPEINFO(QHashDummyValue, Q_MOVABLE_TYPE | Q_DUMMY_TYPE);
 
201
 
 
202
template <class Key, class T>
 
203
struct QHashNode
 
204
{
 
205
    QHashNode *next;
 
206
    const uint h;
 
207
    const Key key;
 
208
    T value;
 
209
 
 
210
    inline QHashNode(const Key &key0, const T &value0, uint hash, QHashNode *n)
 
211
        : next(n), h(hash), key(key0), value(value0) {}
 
212
    inline bool same_key(uint h0, const Key &key0) const { return h0 == h && key0 == key; }
 
213
};
 
214
 
 
215
template <class Key, class T>
 
216
struct QHashDummyNode
 
217
{
 
218
    QHashNode<Key, T> *next;
 
219
    const uint h;
 
220
    const Key key;
 
221
 
 
222
    inline QHashDummyNode(const Key &key0, uint hash, QHashNode<Key, T> *n) : next(n), h(hash), key(key0) {}
 
223
};
 
224
 
 
225
 
 
226
#if 0
 
227
// ###
 
228
// The introduction of the QHash random seed breaks this optimization, as it
 
229
// relies on qHash(int i) = i. If the hash value is salted, then the hash
 
230
// table becomes corrupted.
 
231
//
 
232
// A bit more research about whether it makes sense or not to salt integer
 
233
// keys (and in general keys whose hash value is easy to invert)
 
234
// is needed, or about how keep this optimization and the seed (f.i. by
 
235
// specializing QHash for integer values, and re-apply the seed during lookup).
 
236
//
 
237
// Be aware that such changes can easily be binary incompatible, and therefore
 
238
// cannot be made during the Qt 5 lifetime.
 
239
#define Q_HASH_DECLARE_INT_NODES(key_type) \
 
240
    template <class T> \
 
241
    struct QHashDummyNode<key_type, T> { \
 
242
        QHashDummyNode *next; \
 
243
        union { uint h; key_type key; }; \
 
244
\
 
245
        inline QHashDummyNode(key_type /* key0 */) {} \
 
246
    }; \
 
247
\
 
248
    template <class T> \
 
249
    struct QHashNode<key_type, T> { \
 
250
        QHashNode *next; \
 
251
        union { uint h; key_type key; }; \
 
252
        T value; \
 
253
\
 
254
        inline QHashNode(key_type /* key0 */) {} \
 
255
        inline QHashNode(key_type /* key0 */, const T &value0) : value(value0) {} \
 
256
        inline bool same_key(uint h0, key_type) const { return h0 == h; } \
 
257
    }
 
258
 
 
259
#if defined(Q_BYTE_ORDER) && Q_BYTE_ORDER == Q_LITTLE_ENDIAN
 
260
Q_HASH_DECLARE_INT_NODES(short);
 
261
Q_HASH_DECLARE_INT_NODES(ushort);
 
262
#endif
 
263
Q_HASH_DECLARE_INT_NODES(int);
 
264
Q_HASH_DECLARE_INT_NODES(uint);
 
265
#undef Q_HASH_DECLARE_INT_NODES
 
266
#endif // #if 0
 
267
 
 
268
template <class Key, class T>
 
269
class QHash
 
270
{
 
271
    typedef QHashDummyNode<Key, T> DummyNode;
 
272
    typedef QHashNode<Key, T> Node;
 
273
 
 
274
    union {
 
275
        QHashData *d;
 
276
        QHashNode<Key, T> *e;
 
277
    };
 
278
 
 
279
    static inline Node *concrete(QHashData::Node *node) {
 
280
        return reinterpret_cast<Node *>(node);
 
281
    }
 
282
 
 
283
    static inline int alignOfNode() { return qMax<int>(sizeof(void*), Q_ALIGNOF(Node)); }
 
284
    static inline int alignOfDummyNode() { return qMax<int>(sizeof(void*), Q_ALIGNOF(DummyNode)); }
 
285
 
 
286
public:
 
287
    inline QHash() : d(const_cast<QHashData *>(&QHashData::shared_null)) { }
 
288
    inline QHash(const QHash<Key, T> &other) : d(other.d) { d->ref.ref(); if (!d->sharable) detach(); }
 
289
    inline ~QHash() { if (!d->ref.deref()) freeData(d); }
 
290
 
 
291
    QHash<Key, T> &operator=(const QHash<Key, T> &other);
 
292
#ifdef Q_COMPILER_RVALUE_REFS
 
293
    inline QHash(QHash<Key, T> &&other) : d(other.d) { other.d = const_cast<QHashData *>(&QHashData::shared_null); }
 
294
    inline QHash<Key, T> &operator=(QHash<Key, T> &&other)
 
295
    { qSwap(d, other.d); return *this; }
 
296
#endif
 
297
    inline void swap(QHash<Key, T> &other) { qSwap(d, other.d); }
 
298
 
 
299
    bool operator==(const QHash<Key, T> &other) const;
 
300
    inline bool operator!=(const QHash<Key, T> &other) const { return !(*this == other); }
 
301
 
 
302
    inline int size() const { return d->size; }
 
303
 
 
304
    inline bool isEmpty() const { return d->size == 0; }
 
305
 
 
306
    inline int capacity() const { return d->numBuckets; }
 
307
    void reserve(int size);
 
308
    inline void squeeze() { reserve(1); }
 
309
 
 
310
    inline void detach() { if (d->ref.isShared()) detach_helper(); }
 
311
    inline bool isDetached() const { return !d->ref.isShared(); }
 
312
    inline void setSharable(bool sharable) { if (!sharable) detach(); if (d != &QHashData::shared_null) d->sharable = sharable; }
 
313
    inline bool isSharedWith(const QHash<Key, T> &other) const { return d == other.d; }
 
314
 
 
315
    void clear();
 
316
 
 
317
    int remove(const Key &key);
 
318
    T take(const Key &key);
 
319
 
 
320
    bool contains(const Key &key) const;
 
321
    const Key key(const T &value) const;
 
322
    const Key key(const T &value, const Key &defaultKey) const;
 
323
    const T value(const Key &key) const;
 
324
    const T value(const Key &key, const T &defaultValue) const;
 
325
    T &operator[](const Key &key);
 
326
    const T operator[](const Key &key) const;
 
327
 
 
328
    QList<Key> uniqueKeys() const;
 
329
    QList<Key> keys() const;
 
330
    QList<Key> keys(const T &value) const;
 
331
    QList<T> values() const;
 
332
    QList<T> values(const Key &key) const;
 
333
    int count(const Key &key) const;
 
334
 
 
335
    class const_iterator;
 
336
 
 
337
    class iterator
 
338
    {
 
339
        friend class const_iterator;
 
340
        friend class QHash<Key, T>;
 
341
        QHashData::Node *i;
 
342
 
 
343
    public:
 
344
        typedef std::bidirectional_iterator_tag iterator_category;
 
345
        typedef qptrdiff difference_type;
 
346
        typedef T value_type;
 
347
        typedef T *pointer;
 
348
        typedef T &reference;
 
349
 
 
350
        inline iterator() : i(0) { }
 
351
        explicit inline iterator(void *node) : i(reinterpret_cast<QHashData::Node *>(node)) { }
 
352
 
 
353
        inline const Key &key() const { return concrete(i)->key; }
 
354
        inline T &value() const { return concrete(i)->value; }
 
355
        inline T &operator*() const { return concrete(i)->value; }
 
356
        inline T *operator->() const { return &concrete(i)->value; }
 
357
        inline bool operator==(const iterator &o) const { return i == o.i; }
 
358
        inline bool operator!=(const iterator &o) const { return i != o.i; }
 
359
 
 
360
        inline iterator &operator++() {
 
361
            i = QHashData::nextNode(i);
 
362
            return *this;
 
363
        }
 
364
        inline iterator operator++(int) {
 
365
            iterator r = *this;
 
366
            i = QHashData::nextNode(i);
 
367
            return r;
 
368
        }
 
369
        inline iterator &operator--() {
 
370
            i = QHashData::previousNode(i);
 
371
            return *this;
 
372
        }
 
373
        inline iterator operator--(int) {
 
374
            iterator r = *this;
 
375
            i = QHashData::previousNode(i);
 
376
            return r;
 
377
        }
 
378
        inline iterator operator+(int j) const
 
379
        { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
 
380
        inline iterator operator-(int j) const { return operator+(-j); }
 
381
        inline iterator &operator+=(int j) { return *this = *this + j; }
 
382
        inline iterator &operator-=(int j) { return *this = *this - j; }
 
383
 
 
384
#ifndef QT_STRICT_ITERATORS
 
385
    public:
 
386
        inline bool operator==(const const_iterator &o) const
 
387
            { return i == o.i; }
 
388
        inline bool operator!=(const const_iterator &o) const
 
389
            { return i != o.i; }
 
390
#endif
 
391
    };
 
392
    friend class iterator;
 
393
 
 
394
    class const_iterator
 
395
    {
 
396
        friend class iterator;
 
397
        QHashData::Node *i;
 
398
 
 
399
    public:
 
400
        typedef std::bidirectional_iterator_tag iterator_category;
 
401
        typedef qptrdiff difference_type;
 
402
        typedef T value_type;
 
403
        typedef const T *pointer;
 
404
        typedef const T &reference;
 
405
 
 
406
        inline const_iterator() : i(0) { }
 
407
        explicit inline const_iterator(void *node)
 
408
            : i(reinterpret_cast<QHashData::Node *>(node)) { }
 
409
#ifdef QT_STRICT_ITERATORS
 
410
        explicit inline const_iterator(const iterator &o)
 
411
#else
 
412
        inline const_iterator(const iterator &o)
 
413
#endif
 
414
        { i = o.i; }
 
415
 
 
416
        inline const Key &key() const { return concrete(i)->key; }
 
417
        inline const T &value() const { return concrete(i)->value; }
 
418
        inline const T &operator*() const { return concrete(i)->value; }
 
419
        inline const T *operator->() const { return &concrete(i)->value; }
 
420
        inline bool operator==(const const_iterator &o) const { return i == o.i; }
 
421
        inline bool operator!=(const const_iterator &o) const { return i != o.i; }
 
422
 
 
423
        inline const_iterator &operator++() {
 
424
            i = QHashData::nextNode(i);
 
425
            return *this;
 
426
        }
 
427
        inline const_iterator operator++(int) {
 
428
            const_iterator r = *this;
 
429
            i = QHashData::nextNode(i);
 
430
            return r;
 
431
        }
 
432
        inline const_iterator &operator--() {
 
433
            i = QHashData::previousNode(i);
 
434
            return *this;
 
435
        }
 
436
        inline const_iterator operator--(int) {
 
437
            const_iterator r = *this;
 
438
            i = QHashData::previousNode(i);
 
439
            return r;
 
440
        }
 
441
        inline const_iterator operator+(int j) const
 
442
        { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
 
443
        inline const_iterator operator-(int j) const { return operator+(-j); }
 
444
        inline const_iterator &operator+=(int j) { return *this = *this + j; }
 
445
        inline const_iterator &operator-=(int j) { return *this = *this - j; }
 
446
 
 
447
        // ### Qt 5: not sure this is necessary anymore
 
448
#ifdef QT_STRICT_ITERATORS
 
449
    private:
 
450
        inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); }
 
451
        inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); }
 
452
#endif
 
453
    };
 
454
    friend class const_iterator;
 
455
 
 
456
    // STL style
 
457
    inline iterator begin() { detach(); return iterator(d->firstNode()); }
 
458
    inline const_iterator begin() const { return const_iterator(d->firstNode()); }
 
459
    inline const_iterator cbegin() const { return const_iterator(d->firstNode()); }
 
460
    inline const_iterator constBegin() const { return const_iterator(d->firstNode()); }
 
461
    inline iterator end() { detach(); return iterator(e); }
 
462
    inline const_iterator end() const { return const_iterator(e); }
 
463
    inline const_iterator cend() const { return const_iterator(e); }
 
464
    inline const_iterator constEnd() const { return const_iterator(e); }
 
465
    iterator erase(iterator it);
 
466
 
 
467
    // more Qt
 
468
    typedef iterator Iterator;
 
469
    typedef const_iterator ConstIterator;
 
470
    inline int count() const { return d->size; }
 
471
    iterator find(const Key &key);
 
472
    const_iterator find(const Key &key) const;
 
473
    const_iterator constFind(const Key &key) const;
 
474
    iterator insert(const Key &key, const T &value);
 
475
    iterator insertMulti(const Key &key, const T &value);
 
476
    QHash<Key, T> &unite(const QHash<Key, T> &other);
 
477
 
 
478
    // STL compatibility
 
479
    typedef T mapped_type;
 
480
    typedef Key key_type;
 
481
    typedef qptrdiff difference_type;
 
482
    typedef int size_type;
 
483
 
 
484
    inline bool empty() const { return isEmpty(); }
 
485
 
 
486
#ifdef QT_QHASH_DEBUG
 
487
    inline void dump() const { d->dump(); }
 
488
    inline void checkSanity() const { d->checkSanity(); }
 
489
#endif
 
490
 
 
491
private:
 
492
    void detach_helper();
 
493
    void freeData(QHashData *d);
 
494
    Node **findNode(const Key &key, uint *hp = 0) const;
 
495
    Node *createNode(uint h, const Key &key, const T &value, Node **nextNode);
 
496
    void deleteNode(Node *node);
 
497
    static void deleteNode2(QHashData::Node *node);
 
498
 
 
499
    static void duplicateNode(QHashData::Node *originalNode, void *newNode);
 
500
};
 
501
 
 
502
 
 
503
template <class Key, class T>
 
504
Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(Node *node)
 
505
{
 
506
    deleteNode2(reinterpret_cast<QHashData::Node*>(node));
 
507
    d->freeNode(node);
 
508
}
 
509
 
 
510
template <class Key, class T>
 
511
Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode2(QHashData::Node *node)
 
512
{
 
513
#ifdef Q_CC_BOR
 
514
    concrete(node)->~QHashNode<Key, T>();
 
515
#else
 
516
    concrete(node)->~Node();
 
517
#endif
 
518
}
 
519
 
 
520
template <class Key, class T>
 
521
Q_INLINE_TEMPLATE void QHash<Key, T>::duplicateNode(QHashData::Node *node, void *newNode)
 
522
{
 
523
    Node *concreteNode = concrete(node);
 
524
    if (QTypeInfo<T>::isDummy) {
 
525
        (void) new (newNode) DummyNode(concreteNode->key, concreteNode->h, 0);
 
526
    } else {
 
527
        (void) new (newNode) Node(concreteNode->key, concreteNode->value, concreteNode->h, 0);
 
528
    }
 
529
}
 
530
 
 
531
template <class Key, class T>
 
532
Q_INLINE_TEMPLATE typename QHash<Key, T>::Node *
 
533
QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anextNode)
 
534
{
 
535
    Node *node;
 
536
 
 
537
    if (QTypeInfo<T>::isDummy) {
 
538
        node = reinterpret_cast<Node *>(new (d->allocateNode(alignOfDummyNode())) DummyNode(akey, ah, *anextNode));
 
539
    } else {
 
540
        node = new (d->allocateNode(alignOfNode())) Node(akey, avalue, ah, *anextNode);
 
541
    }
 
542
 
 
543
    *anextNode = node;
 
544
    ++d->size;
 
545
    return node;
 
546
}
 
547
 
 
548
template <class Key, class T>
 
549
Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash<Key, T> &other)
 
550
{
 
551
    QHash<Key, T> copy(other);
 
552
    const_iterator it = copy.constEnd();
 
553
    while (it != copy.constBegin()) {
 
554
        --it;
 
555
        insertMulti(it.key(), it.value());
 
556
    }
 
557
    return *this;
 
558
}
 
559
 
 
560
template <class Key, class T>
 
561
Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x)
 
562
{
 
563
    x->free_helper(deleteNode2);
 
564
}
 
565
 
 
566
template <class Key, class T>
 
567
Q_INLINE_TEMPLATE void QHash<Key, T>::clear()
 
568
{
 
569
    *this = QHash<Key,T>();
 
570
}
 
571
 
 
572
template <class Key, class T>
 
573
Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::detach_helper()
 
574
{
 
575
    QHashData *x = d->detach_helper(duplicateNode, deleteNode2,
 
576
        QTypeInfo<T>::isDummy ? sizeof(DummyNode) : sizeof(Node),
 
577
        QTypeInfo<T>::isDummy ? alignOfDummyNode() : alignOfNode());
 
578
    if (!d->ref.deref())
 
579
        freeData(d);
 
580
    d = x;
 
581
}
 
582
 
 
583
template <class Key, class T>
 
584
Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::operator=(const QHash<Key, T> &other)
 
585
{
 
586
    if (d != other.d) {
 
587
        QHashData *o = other.d;
 
588
        o->ref.ref();
 
589
        if (!d->ref.deref())
 
590
            freeData(d);
 
591
        d = o;
 
592
        if (!d->sharable)
 
593
            detach_helper();
 
594
    }
 
595
    return *this;
 
596
}
 
597
 
 
598
template <class Key, class T>
 
599
Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey) const
 
600
{
 
601
    Node *node;
 
602
    if (d->size == 0 || (node = *findNode(akey)) == e) {
 
603
        return T();
 
604
    } else {
 
605
        return node->value;
 
606
    }
 
607
}
 
608
 
 
609
template <class Key, class T>
 
610
Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey, const T &adefaultValue) const
 
611
{
 
612
    Node *node;
 
613
    if (d->size == 0 || (node = *findNode(akey)) == e) {
 
614
        return adefaultValue;
 
615
    } else {
 
616
        return node->value;
 
617
    }
 
618
}
 
619
 
 
620
template <class Key, class T>
 
621
Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const
 
622
{
 
623
    QList<Key> res;
 
624
    res.reserve(size()); // May be too much, but assume short lifetime
 
625
    const_iterator i = begin();
 
626
    if (i != end()) {
 
627
        for (;;) {
 
628
            const Key &aKey = i.key();
 
629
            res.append(aKey);
 
630
            do {
 
631
                if (++i == end())
 
632
                    goto break_out_of_outer_loop;
 
633
            } while (aKey == i.key());
 
634
        }
 
635
    }
 
636
break_out_of_outer_loop:
 
637
    return res;
 
638
}
 
639
 
 
640
template <class Key, class T>
 
641
Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys() const
 
642
{
 
643
    QList<Key> res;
 
644
    res.reserve(size());
 
645
    const_iterator i = begin();
 
646
    while (i != end()) {
 
647
        res.append(i.key());
 
648
        ++i;
 
649
    }
 
650
    return res;
 
651
}
 
652
 
 
653
template <class Key, class T>
 
654
Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys(const T &avalue) const
 
655
{
 
656
    QList<Key> res;
 
657
    const_iterator i = begin();
 
658
    while (i != end()) {
 
659
        if (i.value() == avalue)
 
660
            res.append(i.key());
 
661
        ++i;
 
662
    }
 
663
    return res;
 
664
}
 
665
 
 
666
template <class Key, class T>
 
667
Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue) const
 
668
{
 
669
    return key(avalue, Key());
 
670
}
 
671
 
 
672
template <class Key, class T>
 
673
Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue, const Key &defaultValue) const
 
674
{
 
675
    const_iterator i = begin();
 
676
    while (i != end()) {
 
677
        if (i.value() == avalue)
 
678
            return i.key();
 
679
        ++i;
 
680
    }
 
681
 
 
682
    return defaultValue;
 
683
}
 
684
 
 
685
template <class Key, class T>
 
686
Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values() const
 
687
{
 
688
    QList<T> res;
 
689
    res.reserve(size());
 
690
    const_iterator i = begin();
 
691
    while (i != end()) {
 
692
        res.append(i.value());
 
693
        ++i;
 
694
    }
 
695
    return res;
 
696
}
 
697
 
 
698
template <class Key, class T>
 
699
Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const
 
700
{
 
701
    QList<T> res;
 
702
    Node *node = *findNode(akey);
 
703
    if (node != e) {
 
704
        do {
 
705
            res.append(node->value);
 
706
        } while ((node = node->next) != e && node->key == akey);
 
707
    }
 
708
    return res;
 
709
}
 
710
 
 
711
template <class Key, class T>
 
712
Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::count(const Key &akey) const
 
713
{
 
714
    int cnt = 0;
 
715
    Node *node = *findNode(akey);
 
716
    if (node != e) {
 
717
        do {
 
718
            ++cnt;
 
719
        } while ((node = node->next) != e && node->key == akey);
 
720
    }
 
721
    return cnt;
 
722
}
 
723
 
 
724
template <class Key, class T>
 
725
Q_INLINE_TEMPLATE const T QHash<Key, T>::operator[](const Key &akey) const
 
726
{
 
727
    return value(akey);
 
728
}
 
729
 
 
730
template <class Key, class T>
 
731
Q_INLINE_TEMPLATE T &QHash<Key, T>::operator[](const Key &akey)
 
732
{
 
733
    detach();
 
734
 
 
735
    uint h;
 
736
    Node **node = findNode(akey, &h);
 
737
    if (*node == e) {
 
738
        if (d->willGrow())
 
739
            node = findNode(akey, &h);
 
740
        return createNode(h, akey, T(), node)->value;
 
741
    }
 
742
    return (*node)->value;
 
743
}
 
744
 
 
745
template <class Key, class T>
 
746
Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &akey,
 
747
                                                                         const T &avalue)
 
748
{
 
749
    detach();
 
750
 
 
751
    uint h;
 
752
    Node **node = findNode(akey, &h);
 
753
    if (*node == e) {
 
754
        if (d->willGrow())
 
755
            node = findNode(akey, &h);
 
756
        return iterator(createNode(h, akey, avalue, node));
 
757
    }
 
758
 
 
759
    if (!QTypeInfo<T>::isDummy)
 
760
        (*node)->value = avalue;
 
761
    return iterator(*node);
 
762
}
 
763
 
 
764
template <class Key, class T>
 
765
Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &akey,
 
766
                                                                              const T &avalue)
 
767
{
 
768
    detach();
 
769
    d->willGrow();
 
770
 
 
771
    uint h;
 
772
    Node **nextNode = findNode(akey, &h);
 
773
    return iterator(createNode(h, akey, avalue, nextNode));
 
774
}
 
775
 
 
776
template <class Key, class T>
 
777
Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::remove(const Key &akey)
 
778
{
 
779
    if (isEmpty()) // prevents detaching shared null
 
780
        return 0;
 
781
    detach();
 
782
 
 
783
    int oldSize = d->size;
 
784
    Node **node = findNode(akey);
 
785
    if (*node != e) {
 
786
        bool deleteNext = true;
 
787
        do {
 
788
            Node *next = (*node)->next;
 
789
            deleteNext = (next != e && next->key == (*node)->key);
 
790
            deleteNode(*node);
 
791
            *node = next;
 
792
            --d->size;
 
793
        } while (deleteNext);
 
794
        d->hasShrunk();
 
795
    }
 
796
    return oldSize - d->size;
 
797
}
 
798
 
 
799
template <class Key, class T>
 
800
Q_OUTOFLINE_TEMPLATE T QHash<Key, T>::take(const Key &akey)
 
801
{
 
802
    if (isEmpty()) // prevents detaching shared null
 
803
        return T();
 
804
    detach();
 
805
 
 
806
    Node **node = findNode(akey);
 
807
    if (*node != e) {
 
808
        T t = (*node)->value;
 
809
        Node *next = (*node)->next;
 
810
        deleteNode(*node);
 
811
        *node = next;
 
812
        --d->size;
 
813
        d->hasShrunk();
 
814
        return t;
 
815
    }
 
816
    return T();
 
817
}
 
818
 
 
819
template <class Key, class T>
 
820
Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::erase(iterator it)
 
821
{
 
822
    if (it == iterator(e))
 
823
        return it;
 
824
 
 
825
    iterator ret = it;
 
826
    ++ret;
 
827
 
 
828
    Node *node = concrete(it.i);
 
829
    Node **node_ptr = reinterpret_cast<Node **>(&d->buckets[node->h % d->numBuckets]);
 
830
    while (*node_ptr != node)
 
831
        node_ptr = &(*node_ptr)->next;
 
832
    *node_ptr = node->next;
 
833
    deleteNode(node);
 
834
    --d->size;
 
835
    return ret;
 
836
}
 
837
 
 
838
template <class Key, class T>
 
839
Q_INLINE_TEMPLATE void QHash<Key, T>::reserve(int asize)
 
840
{
 
841
    detach();
 
842
    d->rehash(-qMax(asize, 1));
 
843
}
 
844
 
 
845
template <class Key, class T>
 
846
Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &akey) const
 
847
{
 
848
    return const_iterator(*findNode(akey));
 
849
}
 
850
 
 
851
template <class Key, class T>
 
852
Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &akey) const
 
853
{
 
854
    return const_iterator(*findNode(akey));
 
855
}
 
856
 
 
857
template <class Key, class T>
 
858
Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::find(const Key &akey)
 
859
{
 
860
    detach();
 
861
    return iterator(*findNode(akey));
 
862
}
 
863
 
 
864
template <class Key, class T>
 
865
Q_INLINE_TEMPLATE bool QHash<Key, T>::contains(const Key &akey) const
 
866
{
 
867
    return *findNode(akey) != e;
 
868
}
 
869
 
 
870
template <class Key, class T>
 
871
Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey,
 
872
                                                                            uint *ahp) const
 
873
{
 
874
    Node **node;
 
875
    uint h = 0;
 
876
 
 
877
    if (d->numBuckets || ahp) {
 
878
        h = qHash(akey, d->seed);
 
879
        if (ahp)
 
880
            *ahp = h;
 
881
    }
 
882
    if (d->numBuckets) {
 
883
        node = reinterpret_cast<Node **>(&d->buckets[h % d->numBuckets]);
 
884
        Q_ASSERT(*node == e || (*node)->next);
 
885
        while (*node != e && !(*node)->same_key(h, akey))
 
886
            node = &(*node)->next;
 
887
    } else {
 
888
        node = const_cast<Node **>(reinterpret_cast<const Node * const *>(&e));
 
889
    }
 
890
    return node;
 
891
}
 
892
 
 
893
template <class Key, class T>
 
894
Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash<Key, T> &other) const
 
895
{
 
896
    if (size() != other.size())
 
897
        return false;
 
898
    if (d == other.d)
 
899
        return true;
 
900
 
 
901
    const_iterator it = begin();
 
902
 
 
903
    while (it != end()) {
 
904
        const Key &akey = it.key();
 
905
 
 
906
        const_iterator it2 = other.find(akey);
 
907
        do {
 
908
            if (it2 == other.end() || !(it2.key() == akey))
 
909
                return false;
 
910
            if (!QTypeInfo<T>::isDummy && !(it.value() == it2.value()))
 
911
                return false;
 
912
            ++it;
 
913
            ++it2;
 
914
        } while (it != end() && it.key() == akey);
 
915
    }
 
916
    return true;
 
917
}
 
918
 
 
919
template <class Key, class T>
 
920
class QMultiHash : public QHash<Key, T>
 
921
{
 
922
public:
 
923
    QMultiHash() {}
 
924
    QMultiHash(const QHash<Key, T> &other) : QHash<Key, T>(other) {}
 
925
    inline void swap(QMultiHash<Key, T> &other) { QHash<Key, T>::swap(other); } // prevent QMultiHash<->QHash swaps
 
926
 
 
927
    inline typename QHash<Key, T>::iterator replace(const Key &key, const T &value)
 
928
    { return QHash<Key, T>::insert(key, value); }
 
929
 
 
930
    inline typename QHash<Key, T>::iterator insert(const Key &key, const T &value)
 
931
    { return QHash<Key, T>::insertMulti(key, value); }
 
932
 
 
933
    inline QMultiHash &operator+=(const QMultiHash &other)
 
934
    { this->unite(other); return *this; }
 
935
    inline QMultiHash operator+(const QMultiHash &other) const
 
936
    { QMultiHash result = *this; result += other; return result; }
 
937
 
 
938
#if !defined(Q_NO_USING_KEYWORD) && !defined(Q_CC_RVCT)
 
939
    // RVCT compiler doesn't handle using-keyword right when used functions are overloaded in child class
 
940
    using QHash<Key, T>::contains;
 
941
    using QHash<Key, T>::remove;
 
942
    using QHash<Key, T>::count;
 
943
    using QHash<Key, T>::find;
 
944
    using QHash<Key, T>::constFind;
 
945
#else
 
946
    inline bool contains(const Key &key) const
 
947
    { return QHash<Key, T>::contains(key); }
 
948
    inline int remove(const Key &key)
 
949
    { return QHash<Key, T>::remove(key); }
 
950
    inline int count(const Key &key) const
 
951
    { return QHash<Key, T>::count(key); }
 
952
    inline int count() const
 
953
    { return QHash<Key, T>::count(); }
 
954
    inline typename QHash<Key, T>::iterator find(const Key &key)
 
955
    { return QHash<Key, T>::find(key); }
 
956
    inline typename QHash<Key, T>::const_iterator find(const Key &key) const
 
957
    { return QHash<Key, T>::find(key); }
 
958
    inline typename QHash<Key, T>::const_iterator constFind(const Key &key) const
 
959
    { return QHash<Key, T>::constFind(key); }
 
960
#endif
 
961
 
 
962
    bool contains(const Key &key, const T &value) const;
 
963
 
 
964
    int remove(const Key &key, const T &value);
 
965
 
 
966
    int count(const Key &key, const T &value) const;
 
967
 
 
968
    typename QHash<Key, T>::iterator find(const Key &key, const T &value) {
 
969
        typename QHash<Key, T>::iterator i(find(key));
 
970
        typename QHash<Key, T>::iterator end(this->end());
 
971
        while (i != end && i.key() == key) {
 
972
            if (i.value() == value)
 
973
                return i;
 
974
            ++i;
 
975
        }
 
976
        return end;
 
977
    }
 
978
    typename QHash<Key, T>::const_iterator find(const Key &key, const T &value) const {
 
979
        typename QHash<Key, T>::const_iterator i(constFind(key));
 
980
        typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
 
981
        while (i != end && i.key() == key) {
 
982
            if (i.value() == value)
 
983
                return i;
 
984
            ++i;
 
985
        }
 
986
        return end;
 
987
    }
 
988
    typename QHash<Key, T>::const_iterator constFind(const Key &key, const T &value) const
 
989
        { return find(key, value); }
 
990
private:
 
991
    T &operator[](const Key &key);
 
992
    const T operator[](const Key &key) const;
 
993
};
 
994
 
 
995
template <class Key, class T>
 
996
Q_INLINE_TEMPLATE bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const
 
997
{
 
998
    return constFind(key, value) != QHash<Key, T>::constEnd();
 
999
}
 
1000
 
 
1001
template <class Key, class T>
 
1002
Q_INLINE_TEMPLATE int QMultiHash<Key, T>::remove(const Key &key, const T &value)
 
1003
{
 
1004
    int n = 0;
 
1005
    typename QHash<Key, T>::iterator i(find(key));
 
1006
    typename QHash<Key, T>::iterator end(QHash<Key, T>::end());
 
1007
    while (i != end && i.key() == key) {
 
1008
        if (i.value() == value) {
 
1009
            i = this->erase(i);
 
1010
            ++n;
 
1011
        } else {
 
1012
            ++i;
 
1013
        }
 
1014
    }
 
1015
    return n;
 
1016
}
 
1017
 
 
1018
template <class Key, class T>
 
1019
Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value) const
 
1020
{
 
1021
    int n = 0;
 
1022
    typename QHash<Key, T>::const_iterator i(constFind(key));
 
1023
    typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
 
1024
    while (i != end && i.key() == key) {
 
1025
        if (i.value() == value)
 
1026
            ++n;
 
1027
        ++i;
 
1028
    }
 
1029
    return n;
 
1030
}
 
1031
 
 
1032
Q_DECLARE_ASSOCIATIVE_ITERATOR(Hash)
 
1033
Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Hash)
 
1034
 
 
1035
QT_END_NAMESPACE
 
1036
 
 
1037
QT_END_HEADER
 
1038
 
 
1039
#endif // QHASH_H