qmap.h

奇趣公司比较新的qt/emd版本

/****************************************************************************
**
** Copyright (C) 1992-2007 Trolltech ASA. All rights reserved.
**
** This file is part of the QtCore module of the Qt Toolkit.
**
** This file may be used under the terms of the GNU General Public
** License version 2.0 as published by the Free Software Foundation
** and appearing in the file LICENSE.GPL included in the packaging of
** this file.  Please review the following information to ensure GNU
** General Public Licensing requirements will be met:
** http://trolltech.com/products/qt/licenses/licensing/opensource/
**
** If you are unsure which license is appropriate for your use, please
** review the following information:
** http://trolltech.com/products/qt/licenses/licensing/licensingoverview
** or contact the sales department at [e-mail].
**
** In addition, as a special exception, Trolltech gives you certain
** additional rights. These rights are described in the Trolltech GPL
** Exception version 1.0, which can be found at
** http://www.trolltech.com/products/qt/gplexception/ and in the file
** GPL_EXCEPTION.txt in this package.
**
** In addition, as a special exception, Trolltech, as the sole copyright
** holder for Qt Designer, grants users of the Qt/Eclipse Integration
** plug-in the right for the Qt/Eclipse Integration to link to
** functionality provided by Qt Designer and its related libraries.
**
** Trolltech reserves all rights not expressly granted herein.
**
** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE
** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
**
****************************************************************************/

#ifndef QMAP_H
#define QMAP_H

#include <QtCore/qatomic.h>
#include <QtCore/qiterator.h>
#include <QtCore/qlist.h>

#ifndef QT_NO_STL
#include <map>
#endif

#include <new>
#undef QT_MAP_DEBUG

QT_BEGIN_HEADER

QT_MODULE(Core)

struct Q_CORE_EXPORT QMapData
{
    struct Node {
        Node *backward;
        Node *forward[1];
    };
    enum { LastLevel = 11, Sparseness = 3 };

    QMapData *backward;
    QMapData *forward[QMapData::LastLevel + 1];
    QBasicAtomic ref;
    int topLevel;
    int size;
    uint randomBits;
    uint insertInOrder : 1;
    uint sharable : 1;

    static QMapData *createData();
    void continueFreeData(int offset);
    Node *node_create(Node *update[], int offset);
    void node_delete(Node *update[], int offset, Node *node);
#ifdef QT_QMAP_DEBUG
    uint adjust_ptr(Node *node);
    void dump();
#endif

    static QMapData shared_null;
};


/*
    QMap uses qMapLessThanKey() to compare keys. The default
    implementation uses operator<(). For pointer types,
    qMapLessThanKey() casts the pointers to integers before it
    compares them, because operator<() is undefined on pointers
    that come from different memory blocks. (In practice, this
    is only a problem when running a program such as
    BoundsChecker.)
*/

template <class Key> inline bool qMapLessThanKey(const Key &key1, const Key &key2)
{
    return key1 < key2;
}

#ifndef QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION
template <class Ptr> inline bool qMapLessThanKey(Ptr *key1, Ptr *key2)
{
    Q_ASSERT(sizeof(ulong) == sizeof(Ptr *));
    return reinterpret_cast<ulong>(key1) < reinterpret_cast<ulong>(key2);
}

template <class Ptr> inline bool qMapLessThanKey(const Ptr *key1, const Ptr *key2)
{
    Q_ASSERT(sizeof(ulong) == sizeof(const Ptr *));
    return reinterpret_cast<ulong>(key1) < reinterpret_cast<ulong>(key2);
}
#endif // QT_NO_PARTIAL_TEMPLATE_SPECIALIZATION

template <class Key, class T>
class QMap
{
    struct Node {
        Key key;
        T value;
        QMapData::Node *backward;
        QMapData::Node *forward[1];
    };
    union {
        QMapData *d;
        QMapData::Node *e;
    };

    struct PayloadNode
    {
        Key key;
        T value;
        QMapData::Node *backward;
    };

    static inline int payload() { return sizeof(PayloadNode) - sizeof(QMapData::Node *); }
    static inline Node *concrete(QMapData::Node *node) {
        return reinterpret_cast<Node *>(reinterpret_cast<char *>(node) - payload());
    }

public:
    inline QMap() : d(&QMapData::shared_null) { d->ref.ref(); }
    inline QMap(const QMap<Key, T> &other) : d(other.d)
    { d->ref.ref(); if (!d->sharable) detach(); }
    inline ~QMap() { if (!d) return; if (!d->ref.deref()) freeData(d); }

    QMap<Key, T> &operator=(const QMap<Key, T> &other);
#ifndef QT_NO_STL
    explicit QMap(const typename std::map<Key, T> &other);
    std::map<Key, T> toStdMap() const;
#endif

    bool operator==(const QMap<Key, T> &other) const;
    inline bool operator!=(const QMap<Key, T> &other) const { return !(*this == other); }

    inline int size() const { return d->size; }

    inline bool isEmpty() const { return d->size == 0; }

    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; }
    inline void setInsertInOrder(bool ordered) { d->insertInOrder = ordered; }

    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
    {
        QMapData::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 QMapData::Node *() const { return i; }
        inline iterator() : i(0) { }
        inline iterator(QMapData::Node *node) : i(node) { }

        inline const Key &key() const { return concrete(i)->key; }
        inline T &value() const { return concrete(i)->value; }
#ifdef QT3_SUPPORT
        inline QT3_SUPPORT T &data() const { return concrete(i)->value; }
#endif
        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 = i->forward[0];
            return *this;
        }
        inline iterator operator++(int) {
            iterator r = *this;
            i = i->forward[0];
            return r;
        }
        inline iterator &operator--() {
            i = i->backward;
            return *this;
        }
        inline iterator operator--(int) {
            iterator r = *this;
            i = i->backward;
            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 == reinterpret_cast<const iterator &>(o).i; }
        inline bool operator!=(const const_iterator &o) const
            { return i != reinterpret_cast<const iterator &>(o).i; }

    private:
        // ### Qt 5: remove
        inline operator bool() const { return false; }
    };
    friend class iterator;

    class const_iterator
    {
        QMapData::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 QMapData::Node *() const { return i; }
        inline const_iterator() : i(0) { }
        inline const_iterator(QMapData::Node *node) : i(node) { }
#ifdef QT_STRICT_ITERATORS
        explicit inline const_iterator(const iterator &o)
#else
        inline const_iterator(const iterator &o)
#endif
        { i = reinterpret_cast<const const_iterator &>(o).i; }

        inline const Key &key() const { return concrete(i)->key; }
        inline const T &value() const { return concrete(i)->value; }
#ifdef QT3_SUPPORT
        inline QT3_SUPPORT const T &data() const { return concrete(i)->value; }
#endif
        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 = i->forward[0];
            return *this;
        }
        inline const_iterator operator++(int) {
            const_iterator r = *this;
            i = i->forward[0];
            return r;
        }
        inline const_iterator &operator--() {
            i = i->backward;
            return *this;
        }
        inline const_iterator operator--(int) {
            const_iterator r = *this;
            i = i->backward;
            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) { return operator==(const_iterator(o)); }
        inline bool operator!=(const iterator &o) { 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(e->forward[0]); }
    inline const_iterator begin() const { return const_iterator(e->forward[0]); }
    inline const_iterator constBegin() const { return const_iterator(e->forward[0]); }
    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);
#ifdef QT3_SUPPORT
    inline QT3_SUPPORT iterator remove(iterator it) { return erase(it); }
    inline QT3_SUPPORT void erase(const Key &key) { remove(key); }
#endif