diff -r 000000000000 -r 1918ee327afb src/corelib/tools/qhash.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/src/corelib/tools/qhash.h	Mon Jan 11 14:00:40 2010 +0000
@@ -0,0 +1,1029 @@
+/****************************************************************************
+**
+** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies).
+** All rights reserved.
+** Contact: Nokia Corporation (qt-info@nokia.com)
+**
+** This file is part of the QtCore module of the Qt Toolkit.
+**
+** $QT_BEGIN_LICENSE:LGPL$
+** No Commercial Usage
+** This file contains pre-release code and may not be distributed.
+** You may use this file in accordance with the terms and conditions
+** contained in the Technology Preview License Agreement accompanying
+** this package.
+**
+** GNU Lesser General Public License Usage
+** Alternatively, this file may be used under the terms of the GNU Lesser
+** General Public License version 2.1 as published by the Free Software
+** Foundation and appearing in the file LICENSE.LGPL included in the
+** packaging of this file.  Please review the following information to
+** ensure the GNU Lesser General Public License version 2.1 requirements
+** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html.
+**
+** In addition, as a special exception, Nokia gives you certain additional
+** rights.  These rights are described in the Nokia Qt LGPL Exception
+** version 1.1, included in the file LGPL_EXCEPTION.txt in this package.
+**
+** If you have questions regarding the use of this file, please contact
+** Nokia at qt-info@nokia.com.
+**
+**
+**
+**
+**
+**
+**
+**
+** $QT_END_LICENSE$
+**
+****************************************************************************/
+
+#ifndef QHASH_H
+#define QHASH_H
+
+#include <QtCore/qatomic.h>
+#include <QtCore/qchar.h>
+#include <QtCore/qiterator.h>
+#include <QtCore/qlist.h>
+#include <QtCore/qpair.h>
+
+QT_BEGIN_HEADER
+
+QT_BEGIN_NAMESPACE
+
+QT_MODULE(Core)
+
+class QBitArray;
+class QByteArray;
+class QString;
+class QStringRef;
+
+inline uint qHash(char key) { return uint(key); }
+inline uint qHash(uchar key) { return uint(key); }
+inline uint qHash(signed char key) { return uint(key); }
+inline uint qHash(ushort key) { return uint(key); }
+inline uint qHash(short key) { return uint(key); }
+inline uint qHash(uint key) { return key; }
+inline uint qHash(int key) { return uint(key); }
+inline uint qHash(ulong key)
+{
+    if (sizeof(ulong) > sizeof(uint)) {
+        return uint((key >> (8 * sizeof(uint) - 1)) ^ key);
+    } else {
+        return uint(key);
+    }
+}
+inline uint qHash(long key) { return qHash(ulong(key)); }
+inline uint qHash(quint64 key)
+{
+    if (sizeof(quint64) > sizeof(uint)) {
+        return uint((key >> (8 * sizeof(uint) - 1)) ^ key);
+    } else {
+        return uint(key);
+    }
+}
+inline uint qHash(qint64 key) { return qHash(quint64(key)); }
+inline uint qHash(QChar key) { return qHash(key.unicode()); }
+Q_CORE_EXPORT uint qHash(const QByteArray &key);
+Q_CORE_EXPORT uint qHash(const QString &key);
+Q_CORE_EXPORT uint qHash(const QStringRef &key);
+Q_CORE_EXPORT uint qHash(const QBitArray &key);
+
+#if defined(Q_CC_MSVC)
+#pragma warning( push )
+#pragma warning( disable : 4311 ) // disable pointer truncation warning
+#endif
+template <class T> inline uint qHash(const T *key)
+{
+    return qHash(reinterpret_cast<quintptr>(key));
+}
+#if defined(Q_CC_MSVC)
+#pragma warning( pop )
+#endif
+
+template <typename T1, typename T2> inline uint qHash(const QPair<T1, T2> &key)
+{
+    uint h1 = qHash(key.first);
+    uint h2 = qHash(key.second);
+    return ((h1 << 16) | (h1 >> 16)) ^ h2;
+}
+
+struct Q_CORE_EXPORT QHashData
+{
+    struct Node {
+        Node *next;
+        uint h;
+    };
+
+    Node *fakeNext;
+    Node **buckets;
+    QBasicAtomicInt ref;
+    int size;
+    int nodeSize;
+    short userNumBits;
+    short numBits;
+    int numBuckets;
+    uint sharable : 1;
+
+    void *allocateNode();
+    void freeNode(void *node);
+    QHashData *detach_helper(void (*node_duplicate)(Node *, void *), int nodeSize); // ### Qt5 remove me
+    QHashData *detach_helper(void (*node_duplicate)(Node *, void *), void (*node_delete)(Node *),
+            int nodeSize);
+    void mightGrow();
+    bool willGrow();
+    void hasShrunk();
+    void rehash(int hint);
+    void free_helper(void (*node_delete)(Node *));
+    void destroyAndFree(); // ### Qt5 remove me
+    Node *firstNode();
+#ifdef QT_QHASH_DEBUG
+    void dump();
+    void checkSanity();
+#endif
+    static Node *nextNode(Node *node);
+    static Node *previousNode(Node *node);
+
+    static QHashData shared_null;
+};
+
+inline void QHashData::mightGrow() // ### Qt 5: eliminate
+{
+    if (size >= numBuckets)
+        rehash(numBits + 1);
+}
+
+inline bool QHashData::willGrow()
+{
+    if (size >= numBuckets) {
+        rehash(numBits + 1);
+        return true;
+    } else {
+        return false;
+    }
+}
+
+inline void QHashData::hasShrunk()
+{
+    if (size <= (numBuckets >> 3) && numBits > userNumBits) {
+        QT_TRY {
+            rehash(qMax(int(numBits) - 2, int(userNumBits)));
+        } QT_CATCH(const std::bad_alloc &) {
+            // ignore bad allocs - shrinking shouldn't throw. rehash is exception safe.
+        }
+    }
+}
+
+inline QHashData::Node *QHashData::firstNode()
+{
+    Node *e = reinterpret_cast<Node *>(this);
+    Node **bucket = buckets;
+    int n = numBuckets;
+    while (n--) {
+        if (*bucket != e)
+            return *bucket;
+        ++bucket;
+    }
+    return e;
+}
+
+struct QHashDummyValue
+{
+};
+
+inline bool operator==(const QHashDummyValue & /* v1 */, const QHashDummyValue & /* v2 */)
+{
+    return true;
+}
+
+Q_DECLARE_TYPEINFO(QHashDummyValue, Q_MOVABLE_TYPE | Q_DUMMY_TYPE);
+
+template <class Key, class T>
+struct QHashDummyNode
+{
+    QHashDummyNode *next;
+    uint h;
+    Key key;
+
+    inline QHashDummyNode(const Key &key0) : key(key0) {}
+};
+
+template <class Key, class T>
+struct QHashNode
+{
+    QHashNode *next;
+    uint h;
+    Key key;
+    T value;
+
+    inline QHashNode(const Key &key0) : key(key0) {} // ### remove in 5.0
+    inline QHashNode(const Key &key0, const T &value0) : key(key0), value(value0) {}
+    inline bool same_key(uint h0, const Key &key0) { return h0 == h && key0 == key; }
+};
+
+#ifndef QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
+#define Q_HASH_DECLARE_INT_NODES(key_type) \
+    template <class T> \
+    struct QHashDummyNode<key_type, T> { \
+        QHashDummyNode *next; \
+        union { uint h; key_type key; }; \
+\
+        inline QHashDummyNode(key_type /* key0 */) {} \
+    }; \
+\
+    template <class T> \
+    struct QHashNode<key_type, T> { \
+        QHashNode *next; \
+        union { uint h; key_type key; }; \
+        T value; \
+\
+        inline QHashNode(key_type /* key0 */) {} \
+        inline QHashNode(key_type /* key0 */, const T &value0) : value(value0) {} \
+        inline bool same_key(uint h0, key_type) { return h0 == h; } \
+    }
+
+#if defined(Q_BYTE_ORDER) && Q_BYTE_ORDER == Q_LITTLE_ENDIAN
+Q_HASH_DECLARE_INT_NODES(short);
+Q_HASH_DECLARE_INT_NODES(ushort);
+#endif
+Q_HASH_DECLARE_INT_NODES(int);
+Q_HASH_DECLARE_INT_NODES(uint);
+#undef Q_HASH_DECLARE_INT_NODES
+#endif // QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
+
+template <class Key, class T>
+class QHash
+{
+    typedef QHashDummyNode<Key, T> DummyNode;
+    typedef QHashNode<Key, T> Node;
+
+    union {
+        QHashData *d;
+        QHashNode<Key, T> *e;
+    };
+
+    static inline Node *concrete(QHashData::Node *node) {
+        return reinterpret_cast<Node *>(node);
+    }
+
+public:
+    inline QHash() : d(&QHashData::shared_null) { d->ref.ref(); }
+    inline QHash(const QHash<Key, T> &other) : d(other.d) { d->ref.ref(); if (!d->sharable) detach(); }
+    inline ~QHash() { if (!d->ref.deref()) freeData(d); }
+
+    QHash<Key, T> &operator=(const QHash<Key, T> &other);
+
+    bool operator==(const QHash<Key, T> &other) const;
+    inline bool operator!=(const QHash<Key, T> &other) const { return !(*this == other); }
+
+    inline int size() const { return d->size; }
+
+    inline bool isEmpty() const { return d->size == 0; }
+
+    inline int capacity() const { return d->numBuckets; }
+    void reserve(int size);
+    inline void squeeze() { reserve(1); }
+
+    inline void detach() { if (d->ref != 1) detach_helper(); }
+    inline bool isDetached() const { return d->ref == 1; }
+    inline void setSharable(bool sharable) { if (!sharable) detach(); d->sharable = sharable; }
+
+    void clear();
+
+    int remove(const Key &key);
+    T take(const Key &key);
+
+    bool contains(const Key &key) const;
+    const Key key(const T &value) const;
+    const Key key(const T &value, const Key &defaultKey) const;
+    const T value(const Key &key) const;
+    const T value(const Key &key, const T &defaultValue) const;
+    T &operator[](const Key &key);
+    const T operator[](const Key &key) const;
+
+    QList<Key> uniqueKeys() const;
+    QList<Key> keys() const;
+    QList<Key> keys(const T &value) const;
+    QList<T> values() const;
+    QList<T> values(const Key &key) const;
+    int count(const Key &key) const;
+
+    class const_iterator;
+
+    class iterator
+    {
+        friend class const_iterator;
+        QHashData::Node *i;
+
+    public:
+        typedef std::bidirectional_iterator_tag iterator_category;
+        typedef ptrdiff_t difference_type;
+        typedef T value_type;
+        typedef T *pointer;
+        typedef T &reference;
+
+        // ### Qt 5: get rid of 'operator Node *'
+        inline operator Node *() const { return concrete(i); }
+        inline iterator() : i(0) { }
+        explicit inline iterator(void *node) : i(reinterpret_cast<QHashData::Node *>(node)) { }
+
+        inline const Key &key() const { return concrete(i)->key; }
+        inline T &value() const { return concrete(i)->value; }
+        inline T &operator*() const { return concrete(i)->value; }
+        inline T *operator->() const { return &concrete(i)->value; }
+        inline bool operator==(const iterator &o) const { return i == o.i; }
+        inline bool operator!=(const iterator &o) const { return i != o.i; }
+
+        inline iterator &operator++() {
+            i = QHashData::nextNode(i);
+            return *this;
+        }
+        inline iterator operator++(int) {
+            iterator r = *this;
+            i = QHashData::nextNode(i);
+            return r;
+        }
+        inline iterator &operator--() {
+            i = QHashData::previousNode(i);
+            return *this;
+        }
+        inline iterator operator--(int) {
+            iterator r = *this;
+            i = QHashData::previousNode(i);
+            return r;
+        }
+        inline iterator operator+(int j) const
+        { iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
+        inline iterator operator-(int j) const { return operator+(-j); }
+        inline iterator &operator+=(int j) { return *this = *this + j; }
+        inline iterator &operator-=(int j) { return *this = *this - j; }
+
+        // ### Qt 5: not sure this is necessary anymore
+#ifdef QT_STRICT_ITERATORS
+    private:
+#else
+    public:
+#endif
+        inline bool operator==(const const_iterator &o) const
+            { return i == o.i; }
+        inline bool operator!=(const const_iterator &o) const
+            { return i != o.i; }
+
+    private:
+        // ### Qt 5: remove
+        inline operator bool() const { return false; }
+    };
+    friend class iterator;
+
+    class const_iterator
+    {
+        friend class iterator;
+        QHashData::Node *i;
+
+    public:
+        typedef std::bidirectional_iterator_tag iterator_category;
+        typedef ptrdiff_t difference_type;
+        typedef T value_type;
+        typedef const T *pointer;
+        typedef const T &reference;
+
+        // ### Qt 5: get rid of 'operator Node *'
+        inline operator Node *() const { return concrete(i); }
+        inline const_iterator() : i(0) { }
+        explicit inline const_iterator(void *node)
+            : i(reinterpret_cast<QHashData::Node *>(node)) { }
+#ifdef QT_STRICT_ITERATORS
+        explicit inline const_iterator(const iterator &o)
+#else
+        inline const_iterator(const iterator &o)
+#endif
+        { i = o.i; }
+
+        inline const Key &key() const { return concrete(i)->key; }
+        inline const T &value() const { return concrete(i)->value; }
+        inline const T &operator*() const { return concrete(i)->value; }
+        inline const T *operator->() const { return &concrete(i)->value; }
+        inline bool operator==(const const_iterator &o) const { return i == o.i; }
+        inline bool operator!=(const const_iterator &o) const { return i != o.i; }
+
+        inline const_iterator &operator++() {
+            i = QHashData::nextNode(i);
+            return *this;
+        }
+        inline const_iterator operator++(int) {
+            const_iterator r = *this;
+            i = QHashData::nextNode(i);
+            return r;
+        }
+        inline const_iterator &operator--() {
+            i = QHashData::previousNode(i);
+            return *this;
+        }
+        inline const_iterator operator--(int) {
+            const_iterator r = *this;
+            i = QHashData::previousNode(i);
+            return r;
+        }
+        inline const_iterator operator+(int j) const
+        { const_iterator r = *this; if (j > 0) while (j--) ++r; else while (j++) --r; return r; }
+        inline const_iterator operator-(int j) const { return operator+(-j); }
+        inline const_iterator &operator+=(int j) { return *this = *this + j; }
+        inline const_iterator &operator-=(int j) { return *this = *this - j; }
+
+        // ### Qt 5: not sure this is necessary anymore
+#ifdef QT_STRICT_ITERATORS
+    private:
+        inline bool operator==(const iterator &o) const { return operator==(const_iterator(o)); }
+        inline bool operator!=(const iterator &o) const { return operator!=(const_iterator(o)); }
+#endif
+
+    private:
+        // ### Qt 5: remove
+        inline operator bool() const { return false; }
+    };
+    friend class const_iterator;
+
+    // STL style
+    inline iterator begin() { detach(); return iterator(d->firstNode()); }
+    inline const_iterator begin() const { return const_iterator(d->firstNode()); }
+    inline const_iterator constBegin() const { return const_iterator(d->firstNode()); }
+    inline iterator end() { detach(); return iterator(e); }
+    inline const_iterator end() const { return const_iterator(e); }
+    inline const_iterator constEnd() const { return const_iterator(e); }
+    iterator erase(iterator it);
+
+    // more Qt
+    typedef iterator Iterator;
+    typedef const_iterator ConstIterator;
+    inline int count() const { return d->size; }
+    iterator find(const Key &key);
+    const_iterator find(const Key &key) const;
+    const_iterator constFind(const Key &key) const;
+    iterator insert(const Key &key, const T &value);
+    iterator insertMulti(const Key &key, const T &value);
+    QHash<Key, T> &unite(const QHash<Key, T> &other);
+
+    // STL compatibility
+    typedef T mapped_type;
+    typedef Key key_type;
+    typedef ptrdiff_t difference_type;
+    typedef int size_type;
+
+    inline bool empty() const { return isEmpty(); }
+
+#ifdef QT_QHASH_DEBUG
+    inline void dump() const { d->dump(); }
+    inline void checkSanity() const { d->checkSanity(); }
+#endif
+
+private:
+    void detach_helper();
+    void freeData(QHashData *d);
+    Node **findNode(const Key &key, uint *hp = 0) const;
+    Node *createNode(uint h, const Key &key, const T &value, Node **nextNode);
+    void deleteNode(Node *node);
+    static void deleteNode(QHashData::Node *node);
+
+    static void duplicateNode(QHashData::Node *originalNode, void *newNode);
+};
+
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(Node *node)
+{
+    deleteNode(reinterpret_cast<QHashData::Node*>(node));
+}
+
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE void QHash<Key, T>::deleteNode(QHashData::Node *node)
+{
+#ifdef Q_CC_BOR
+    concrete(node)->~QHashNode<Key, T>();
+#elif defined(QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION)
+    concrete(node)->~QHashNode();
+#else
+    concrete(node)->~Node();
+#endif
+    qFree(node);
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE void QHash<Key, T>::duplicateNode(QHashData::Node *node, void *newNode)
+{
+    Node *concreteNode = concrete(node);
+    if (QTypeInfo<T>::isDummy) {
+        (void) new (newNode) DummyNode(concreteNode->key);
+    } else {
+        (void) new (newNode) Node(concreteNode->key, concreteNode->value);
+    }
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE typename QHash<Key, T>::Node *
+QHash<Key, T>::createNode(uint ah, const Key &akey, const T &avalue, Node **anextNode)
+{
+    Node *node;
+
+    if (QTypeInfo<T>::isDummy) {
+        node = reinterpret_cast<Node *>(new (d->allocateNode()) DummyNode(akey));
+    } else {
+        node = new (d->allocateNode()) Node(akey, avalue);
+    }
+
+    node->h = ah;
+    node->next = *anextNode;
+    *anextNode = node;
+    ++d->size;
+    return node;
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::unite(const QHash<Key, T> &other)
+{
+    QHash<Key, T> copy(other);
+    const_iterator it = copy.constEnd();
+    while (it != copy.constBegin()) {
+        --it;
+        insertMulti(it.key(), it.value());
+    }
+    return *this;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::freeData(QHashData *x)
+{
+    x->free_helper(deleteNode);
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE void QHash<Key, T>::clear()
+{
+    *this = QHash<Key,T>();
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE void QHash<Key, T>::detach_helper()
+{
+    QHashData *x = d->detach_helper(duplicateNode, deleteNode,
+        QTypeInfo<T>::isDummy ? sizeof(DummyNode) : sizeof(Node));
+    if (!d->ref.deref())
+        freeData(d);
+    d = x;
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE QHash<Key, T> &QHash<Key, T>::operator=(const QHash<Key, T> &other)
+{
+    if (d != other.d) {
+        other.d->ref.ref();
+        if (!d->ref.deref())
+            freeData(d);
+        d = other.d;
+        if (!d->sharable)
+            detach_helper();
+    }
+    return *this;
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey) const
+{
+    Node *node;
+    if (d->size == 0 || (node = *findNode(akey)) == e) {
+        return T();
+    } else {
+        return node->value;
+    }
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE const T QHash<Key, T>::value(const Key &akey, const T &adefaultValue) const
+{
+    Node *node;
+    if (d->size == 0 || (node = *findNode(akey)) == e) {
+        return adefaultValue;
+    } else {
+        return node->value;
+    }
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::uniqueKeys() const
+{
+    QList<Key> res;
+    const_iterator i = begin();
+    if (i != end()) {
+        for (;;) {
+            const Key &aKey = i.key();
+            res.append(aKey);
+            do {
+                if (++i == end())
+                    goto break_out_of_outer_loop;
+            } while (aKey == i.key());
+        }
+    }
+break_out_of_outer_loop:
+    return res;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys() const
+{
+    QList<Key> res;
+    const_iterator i = begin();
+    while (i != end()) {
+        res.append(i.key());
+        ++i;
+    }
+    return res;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE QList<Key> QHash<Key, T>::keys(const T &avalue) const
+{
+    QList<Key> res;
+    const_iterator i = begin();
+    while (i != end()) {
+        if (i.value() == avalue)
+            res.append(i.key());
+        ++i;
+    }
+    return res;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue) const
+{
+    return key(avalue, Key());
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE const Key QHash<Key, T>::key(const T &avalue, const Key &defaultValue) const
+{
+    const_iterator i = begin();
+    while (i != end()) {
+        if (i.value() == avalue)
+            return i.key();
+        ++i;
+    }
+
+    return defaultValue;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values() const
+{
+    QList<T> res;
+    const_iterator i = begin();
+    while (i != end()) {
+        res.append(i.value());
+        ++i;
+    }
+    return res;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE QList<T> QHash<Key, T>::values(const Key &akey) const
+{
+    QList<T> res;
+    Node *node = *findNode(akey);
+    if (node != e) {
+        do {
+            res.append(node->value);
+        } while ((node = node->next) != e && node->key == akey);
+    }
+    return res;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::count(const Key &akey) const
+{
+    int cnt = 0;
+    Node *node = *findNode(akey);
+    if (node != e) {
+        do {
+            ++cnt;
+        } while ((node = node->next) != e && node->key == akey);
+    }
+    return cnt;
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE const T QHash<Key, T>::operator[](const Key &akey) const
+{
+    return value(akey);
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE T &QHash<Key, T>::operator[](const Key &akey)
+{
+    detach();
+
+    uint h;
+    Node **node = findNode(akey, &h);
+    if (*node == e) {
+        if (d->willGrow())
+            node = findNode(akey, &h);
+        return createNode(h, akey, T(), node)->value;
+    }
+    return (*node)->value;
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insert(const Key &akey,
+                                                                         const T &avalue)
+{
+    detach();
+
+    uint h;
+    Node **node = findNode(akey, &h);
+    if (*node == e) {
+        if (d->willGrow())
+            node = findNode(akey, &h);
+        return iterator(createNode(h, akey, avalue, node));
+    }
+
+    if (!QTypeInfo<T>::isDummy)
+        (*node)->value = avalue;
+    return iterator(*node);
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::insertMulti(const Key &akey,
+                                                                              const T &avalue)
+{
+    detach();
+    d->willGrow();
+
+    uint h;
+    Node **nextNode = findNode(akey, &h);
+    return iterator(createNode(h, akey, avalue, nextNode));
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE int QHash<Key, T>::remove(const Key &akey)
+{
+    if (isEmpty()) // prevents detaching shared null
+        return 0;
+    detach();
+
+    int oldSize = d->size;
+    Node **node = findNode(akey);
+    if (*node != e) {
+        bool deleteNext = true;
+        do {
+            Node *next = (*node)->next;
+            deleteNext = (next != e && next->key == (*node)->key);
+            deleteNode(*node);
+            *node = next;
+            --d->size;
+        } while (deleteNext);
+        d->hasShrunk();
+    }
+    return oldSize - d->size;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE T QHash<Key, T>::take(const Key &akey)
+{
+    if (isEmpty()) // prevents detaching shared null
+        return T();
+    detach();
+
+    Node **node = findNode(akey);
+    if (*node != e) {
+        T t = (*node)->value;
+        Node *next = (*node)->next;
+        deleteNode(*node);
+        *node = next;
+        --d->size;
+        d->hasShrunk();
+        return t;
+    }
+    return T();
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::erase(iterator it)
+{
+    if (it == iterator(e))
+        return it;
+
+    iterator ret = it;
+    ++ret;
+
+    Node *node = it;
+    Node **node_ptr = reinterpret_cast<Node **>(&d->buckets[node->h % d->numBuckets]);
+    while (*node_ptr != node)
+        node_ptr = &(*node_ptr)->next;
+    *node_ptr = node->next;
+    deleteNode(node);
+    --d->size;
+    return ret;
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE void QHash<Key, T>::reserve(int asize)
+{
+    detach();
+    d->rehash(-qMax(asize, 1));
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::find(const Key &akey) const
+{
+    return const_iterator(*findNode(akey));
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE typename QHash<Key, T>::const_iterator QHash<Key, T>::constFind(const Key &akey) const
+{
+    return const_iterator(*findNode(akey));
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE typename QHash<Key, T>::iterator QHash<Key, T>::find(const Key &akey)
+{
+    detach();
+    return iterator(*findNode(akey));
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE bool QHash<Key, T>::contains(const Key &akey) const
+{
+    return *findNode(akey) != e;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE typename QHash<Key, T>::Node **QHash<Key, T>::findNode(const Key &akey,
+                                                                            uint *ahp) const
+{
+    Node **node;
+    uint h = qHash(akey);
+
+    if (d->numBuckets) {
+        node = reinterpret_cast<Node **>(&d->buckets[h % d->numBuckets]);
+        Q_ASSERT(*node == e || (*node)->next);
+        while (*node != e && !(*node)->same_key(h, akey))
+            node = &(*node)->next;
+    } else {
+        node = const_cast<Node **>(reinterpret_cast<const Node * const *>(&e));
+    }
+    if (ahp)
+        *ahp = h;
+    return node;
+}
+
+template <class Key, class T>
+Q_OUTOFLINE_TEMPLATE bool QHash<Key, T>::operator==(const QHash<Key, T> &other) const
+{
+    if (size() != other.size())
+        return false;
+    if (d == other.d)
+        return true;
+
+    const_iterator it = begin();
+
+    while (it != end()) {
+        const Key &akey = it.key();
+
+        const_iterator it2 = other.find(akey);
+        do {
+            if (it2 == other.end() || !(it2.key() == akey))
+                return false;
+            if (!QTypeInfo<T>::isDummy && !(it.value() == it2.value()))
+                return false;
+            ++it;
+            ++it2;
+        } while (it != end() && it.key() == akey);
+    }
+    return true;
+}
+
+template <class Key, class T>
+class QMultiHash : public QHash<Key, T>
+{
+public:
+    QMultiHash() {}
+    QMultiHash(const QHash<Key, T> &other) : QHash<Key, T>(other) {}
+
+    inline typename QHash<Key, T>::iterator replace(const Key &key, const T &value)
+    { return QHash<Key, T>::insert(key, value); }
+
+    inline typename QHash<Key, T>::iterator insert(const Key &key, const T &value)
+    { return QHash<Key, T>::insertMulti(key, value); }
+
+    inline QMultiHash &operator+=(const QMultiHash &other)
+    { unite(other); return *this; }
+    inline QMultiHash operator+(const QMultiHash &other) const
+    { QMultiHash result = *this; result += other; return result; }
+
+#if !defined(Q_NO_USING_KEYWORD) && !defined(Q_CC_RVCT)
+    // RVCT compiler doesn't handle using-keyword right when used functions are overloaded in child class
+    using QHash<Key, T>::contains;
+    using QHash<Key, T>::remove;
+    using QHash<Key, T>::count;
+    using QHash<Key, T>::find;
+    using QHash<Key, T>::constFind;
+#else
+    inline bool contains(const Key &key) const
+    { return QHash<Key, T>::contains(key); }
+    inline int remove(const Key &key)
+    { return QHash<Key, T>::remove(key); }
+    inline int count(const Key &key) const
+    { return QHash<Key, T>::count(key); }
+    inline int count() const
+    { return QHash<Key, T>::count(); }
+    inline typename QHash<Key, T>::iterator find(const Key &key)
+    { return QHash<Key, T>::find(key); }
+    inline typename QHash<Key, T>::const_iterator find(const Key &key) const
+    { return QHash<Key, T>::find(key); }
+    inline typename QHash<Key, T>::const_iterator constFind(const Key &key) const
+    { return QHash<Key, T>::constFind(key); }
+#endif
+
+    bool contains(const Key &key, const T &value) const;
+
+    int remove(const Key &key, const T &value);
+
+    int count(const Key &key, const T &value) const;
+
+    typename QHash<Key, T>::iterator find(const Key &key, const T &value) {
+        typename QHash<Key, T>::iterator i(find(key));
+        typename QHash<Key, T>::iterator end(this->end());
+        while (i != end && i.key() == key) {
+            if (i.value() == value)
+                return i;
+            ++i;
+        }
+        return end;
+    }
+    typename QHash<Key, T>::const_iterator find(const Key &key, const T &value) const {
+        typename QHash<Key, T>::const_iterator i(constFind(key));
+        typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
+        while (i != end && i.key() == key) {
+            if (i.value() == value)
+                return i;
+            ++i;
+        }
+        return end;
+    }
+    typename QHash<Key, T>::const_iterator constFind(const Key &key, const T &value) const
+        { return find(key, value); }
+private:
+    T &operator[](const Key &key);
+    const T operator[](const Key &key) const;
+};
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE bool QMultiHash<Key, T>::contains(const Key &key, const T &value) const
+{
+    return constFind(key, value) != QHash<Key, T>::constEnd();
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE int QMultiHash<Key, T>::remove(const Key &key, const T &value)
+{
+    int n = 0;
+    typename QHash<Key, T>::iterator i(find(key));
+    typename QHash<Key, T>::iterator end(QHash<Key, T>::end());
+    while (i != end && i.key() == key) {
+        if (i.value() == value) {
+#if defined(Q_CC_RVCT)
+            // RVCT has problems with scoping, apparently.
+            i = QHash<Key, T>::erase(i);
+#else
+            i = erase(i);
+#endif
+            ++n;
+        } else {
+            ++i;
+        }
+    }
+    return n;
+}
+
+template <class Key, class T>
+Q_INLINE_TEMPLATE int QMultiHash<Key, T>::count(const Key &key, const T &value) const
+{
+    int n = 0;
+    typename QHash<Key, T>::const_iterator i(constFind(key));
+    typename QHash<Key, T>::const_iterator end(QHash<Key, T>::constEnd());
+    while (i != end && i.key() == key) {
+        if (i.value() == value)
+            ++n;
+        ++i;
+    }
+    return n;
+}
+
+Q_DECLARE_ASSOCIATIVE_ITERATOR(Hash)
+Q_DECLARE_MUTABLE_ASSOCIATIVE_ITERATOR(Hash)
+
+QT_END_NAMESPACE
+
+QT_END_HEADER
+
+#endif // QHASH_H