qmap.cpp

奇趣公司比较新的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.
**
****************************************************************************/

#include "qmap.h"

#include <stdlib.h>

QMapData QMapData::shared_null = {
    &shared_null,
    { &shared_null, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, Q_ATOMIC_INIT(1), 0, 0, 0, false, true
};

QMapData *QMapData::createData()
{
    QMapData *d = new QMapData;
    Node *e = reinterpret_cast<Node *>(d);
    e->backward = e;
    e->forward[0] = e;
    d->ref.init(1);
    d->topLevel = 0;
    d->size = 0;
    d->randomBits = 0;
    d->insertInOrder = false;
    d->sharable = true;
    return d;
}

void QMapData::continueFreeData(int offset)
{
    Node *e = reinterpret_cast<Node *>(this);
    Node *cur = e->forward[0];
    Node *prev;
    while (cur != e) {
        prev = cur;
        cur = cur->forward[0];
        ::free(reinterpret_cast<char *>(prev) - offset);
    }
    delete this;
}

QMapData::Node *QMapData::node_create(Node *update[], int offset)
{
    int level = 0;
    uint mask = (1 << Sparseness) - 1;

    while ((randomBits & mask) == mask && level < LastLevel) {
        ++level;
        mask <<= Sparseness;
    }

    ++randomBits;
    if (level == 3 && !insertInOrder)
        randomBits = ::qrand();

    if (level > topLevel) {
        Node *e = reinterpret_cast<Node *>(this);
        level = ++topLevel;
        e->forward[level] = e;
        update[level] = e;
    }

    void *concreteNode = ::malloc(offset + sizeof(Node) + level * sizeof(Node *));
    Node *abstractNode = reinterpret_cast<Node *>(reinterpret_cast<char *>(concreteNode) + offset);

    abstractNode->backward = update[0];
    update[0]->forward[0]->backward = abstractNode;

    for (int i = level; i >= 0; i--) {
        abstractNode->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = abstractNode;
        update[i] = abstractNode;
    }
    ++size;
    return abstractNode;
}

void QMapData::node_delete(Node *update[], int offset, Node *node)
{
    node->forward[0]->backward = node->backward;

    for (int i = 0; i <= topLevel; ++i) {
        if (update[i]->forward[i] != node)
            break;
        update[i]->forward[i] = node->forward[i];
    }
    --size;
    ::free(reinterpret_cast<char *>(node) - offset);
}

#ifdef QT_QMAP_DEBUG
#include <qstring.h>
#include <qvector.h>

uint QMapData::adjust_ptr(Node *node)
{
    if (node == reinterpret_cast<Node *>(this)) {
       return (uint)0xDEADBEEF;
    } else {
        return (uint)node;
    }
}

void QMapData::dump()
{
    qDebug("Map data (ref = %d, size = %d, randomBits = %#.8x)", ref.atomic, size, randomBits);

    QString preOutput;
    QVector<QString> output(topLevel + 1);
    Node *e = reinterpret_cast<Node *>(this);

    QString str;
    str.sprintf("    %.8x", adjust_ptr(reinterpret_cast<Node *>(this)));
    preOutput += str;

    Node *update[LastLevel + 1];
    for (int i = 0; i <= topLevel; ++i) {
        str.sprintf("%d: [%.8x] -", i, adjust_ptr(forward[i]));
        output[i] += str;
        update[i] = forward[i];
    }

    Node *node = forward[0];
    while (node != e) {
        int level = 0;
        while (level < topLevel && update[level + 1] == node)
            ++level;

        str.sprintf("       %.8x", adjust_ptr(node));
        preOutput += str;

        for (int i = 0; i <= level; ++i) {
            str.sprintf("-> [%.8x] -", adjust_ptr(node->forward[i]));
            output[i] += str;
            update[i] = node->forward[i];
        }
        for (int j = level + 1; j <= topLevel; ++j)
            output[j] += "---------------";
        node = node->forward[0];
    }

    qDebug(preOutput.ascii());
    for (int i = 0; i <= topLevel; ++i)
        qDebug(output[i].ascii());
}
#endif

/*!
    \class QMap
    \brief The QMap class is a template class that provides a skip-list-based dictionary.

    \ingroup tools
    \ingroup shared
    \mainclass
    \reentrant

    QMap\<Key, T\> is one of Qt's generic \l{container classes}. It
    stores (key, value) pairs and provides fast lookup of the
    value associated with a key.

    QMap and QHash provide very similar functionality. The
    differences are:

    \list
    \i QHash provides faster lookups than QMap. (See \l{Algorithmic
       Complexity} for details.)
    \i When iterating over a QHash, the items are arbitrarily ordered.
       With QMap, the items are always sorted by key.
    \i The key type of a QHash must provide operator==() and a global
       qHash(Key) function. The key type of a QMap must provide
       operator<() specifying a total order.
    \endlist

    Here's an example QMap with QString keys and \c int values:
    \code
        QMap<QString, int> map;
    \endcode

    To insert a (key, value) pair into the map, you can use operator[]():

    \code
        map["one"] = 1;
        map["three"] = 3;
        map["seven"] = 7;
    \endcode

    This inserts the following three (key, value) pairs into the
    QMap: ("one", 1), ("three", 3), and ("seven", 7). Another way to
    insert items into the map is to use insert():

    \code
        map.insert("twelve", 12);
    \endcode

    To look up a value, use operator[]() or value():

    \code
        int num1 = map["thirteen"];
        int num2 = map.value("thirteen");
    \endcode

    If there is no item with the specified key in the map, these
    functions return a \l{default-constructed value}.

    If you want to check whether the map contains a certain key, use
    contains():

    \code
        int timeout = 30;
        if (map.contains("TIMEOUT"))
            timeout = map.value("TIMEOUT");
    \endcode

    There is also a value() overload that uses its second argument as
    a default value if there is no item with the specified key:

    \code
        int timeout = map.value("TIMEOUT", 30);
    \endcode

    In general, we recommend that you use contains() and value()
    rather than operator[]() for looking up a key in a map. The
    reason is that operator[]() silently inserts an item into the
    map if no item exists with the same key (unless the map is
    const). For example, the following code snippet will create 1000
    items in memory:

    \code
        // WRONG
        QMap<int, QWidget *> map;
        ...
        for (int i = 0; i < 1000; ++i) {
            if (map[i] == okButton)
                cout << "Found button at index " << i << endl;
        }
    \endcode

    To avoid this problem, replace \c map[i] with \c map.value(i)
    in the code above.

    If you want to navigate through all the (key, value) pairs stored
    in a QMap, you can use an iterator. QMap provides both
    \l{Java-style iterators} (QMapIterator and QMutableMapIterator)
    and \l{STL-style iterators} (QMap::const_iterator and
    QMap::iterator). Here's how to iterate over a QMap<QString, int>
    using a Java-style iterator:

    \code
        QMapIterator<QString, int> i(map);
        while (i.hasNext()) {
            i.next();
            cout << i.key() << ": " << i.value() << endl;
        }
    \endcode

    Here's the same code, but using an STL-style iterator this time:

    \code
        QMap<QString, int>::const_iterator i = map.constBegin();
        while (i != map.constEnd()) {
            cout << i.key() << ": " << i.value() << endl;
            ++i;
        }
    \endcode

    The items are traversed in ascending key order.

    Normally, a QMap allows only one value per key. If you call
    insert() with a key that already exists in the QMap, the
    previous value will be erased. For example:

    \code
        map.insert("plenty", 100);
        map.insert("plenty", 2000);
        // map.value("plenty") == 2000
    \endcode

    However, you can store multiple values per key by using
    insertMulti() instead of insert() (or using the convenience
    subclass QMultiMap). If you want to retrieve all the values for a
    single key, you can use values(const Key &key), which returns a
    QList<T>:

    \code
        QList<int> values = map.values("plenty");
        for (int i = 0; i < values.size(); ++i)
            cout << values.at(i) << endl;
    \endcode

    The items that share the same key are available from most
    recently to least recently inserted. Another approach is to call
    find() to get the STL-style iterator for the first item with a
    key and iterate from there:

    \code
        QMap<QString, int>::iterator i = map.find("plenty");
        while (i != map.end() && i.key() == "plenty") {
            cout << i.value() << endl;
            ++i;
        }
    \endcode

    If you only need to extract the values from a map (not the keys),
    you can also use \l{foreach}:

    \code
        QMap<QString, int> map;
        ...
        foreach (int value, map)
            cout << value << endl;
    \endcode

    Items can be removed from the map in several ways. One way is to
    call remove(); this will remove any item with the given key.
    Another way is to use QMutableMapIterator::remove(). In addition,
    you can clear the entire map using clear().

    QMap's key and value data types must be \l{assignable data
    types}. This covers most data types you are likely to encounter,
    but the compiler won't let you, for example, store a QWidget as a
    value; instead, store a QWidget *. In addition, QMap's key type
    must provide operator<(). QMap uses it to keep its items sorted,
    and assumes that two keys \c x and \c y are equal if neither \c{x
    < y} nor \c{y < x} is true.

    Example:
    \code
        #ifndef EMPLOYEE_H
        #define EMPLOYEE_H

        class Employee
        {
        public:
            Employee() {}
            Employee(const QString &name, const QDate &dateOfBirth);
            ...

        private:
            QString myName;
            QDate myDateOfBirth;
        };

        inline bool operator<(const Employee &e1, const Employee &e2)
        {
            if (e1.name() != e2.name())
                return e1.name() < e2.name();
            return e1.dateOfBirth() < e2.dateOfBirth();
        }

        #endif // EMPLOYEE_H
    \endcode

    In the example, we start by comparing the employees' names. If
    they're equal, we compare their dates of birth to break the tie.

    \sa QMapIterator, QMutableMapIterator, QHash, QSet
*/

/*! \fn QMap::QMap()

    Constructs an empty map.

    \sa clear()
*/

/*! \fn QMap::QMap(const QMap<Key, T> &other)

    Constructs a copy of \a other.

    This operation occurs in \l{constant time}, because QMap is
    \l{implicitly shared}. This makes returning a QMap from a
    function very fast. If a shared instance is modified, it will be
    copied (copy-on-write), and this takes \l{linear time}.

    \sa operator=()
*/

/*! \fn QMap::QMap(const std::map<Key, T> & other)

    Constructs a copy of \a other.

    This function is only available if Qt is configured with STL
    compatibility enabled.

    \sa toStdMap()
*/

/*! \fn std::map<Key, T> QMap::toStdMap() const

    Returns an STL map equivalent to this QMap.

    This function is only available if Qt is configured with STL
    compatibility enabled.
*/

/*! \fn QMap::~QMap()

    Destroys the map. References to the values in the map, and all
    iterators over this map, become invalid.
*/

/*! \fn QMap<Key, T> &QMap::operator=(const QMap<Key, T> &other)

    Assigns \a other to this map and returns a reference to this map.
*/

/*! \fn bool QMap::operator==(const QMap<Key, T> &other) const

    Returns true if \a other is equal to this map; otherwise returns
    false.