/****************************************************************************

**

** 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;