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

**

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

**

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

#include "qmap.h"

#include <stdlib.h>

#ifdef QT_QMAP_DEBUG

# include <qstring.h>

# include <qvector.h>

#endif

QT_BEGIN_NAMESPACE

QMapData QMapData::shared_null = {

    &shared_null,

    { &shared_null, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },

    Q_BASIC_ATOMIC_INITIALIZER(1), 0, 0, 0, false, true

};

QMapData *QMapData::createData()

{

    QMapData *d = new QMapData;

    Q_CHECK_PTR(d);

    Node *e = reinterpret_cast<Node *>(d);

    e->backward = e;

    e->forward[0] = e;

    d->ref = 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];

        qFree(reinterpret_cast<char *>(prev) - offset);

    }

    delete this;

}

/*!

    Creates a new node inside the data structure.

    \a update is an array with pointers to the node after which the new node

    should be inserted. Because of the strange skip list data structure there

    could be several pointers to this node on different levels.

    \a offset is an amount of bytes that needs to reserved just before the

    QMapData::Node structure.

    \internal

    \since 4.6

*/

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;

    }

    if (level > topLevel) {

        Node *e = reinterpret_cast<Node *>(this);

        level = ++topLevel;

        e->forward[level] = e;

        update[level] = e;

    }

    ++randomBits;

    if (level == 3 && !insertInOrder)

        randomBits = qrand();

    void *concreteNode = qMalloc(offset + sizeof(Node) + level * sizeof(Node *));

    Q_CHECK_PTR(concreteNode);

    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;

    qFree(reinterpret_cast<char *>(node) - offset);

}

#ifdef QT_QMAP_DEBUG

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)", int(ref), 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(reinterpret_cast<Node *>(forward[i])));

        output[i] += str;

        update[i] = reinterpret_cast<Node *>(forward[i]);

    }

    Node *node = reinterpret_cast<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] += QLatin1String("---------------");

        node = node->forward[0];

    }

    qDebug("%s", preOutput.ascii());

    for (int i = 0; i <= topLevel; ++i)

        qDebug("%s", 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

    \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:

    \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 0

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

    \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 1

    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():

    \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 2

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

    \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 3

    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():

    \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 4

    There is also a value() overload that uses its second argument as

    a default value if there is no item with the specified key:

    \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 5

    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:

    \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 6

    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:

    \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 7

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

    \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 8

    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:

    \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 9

    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>:

    \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 10

    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:

    \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 11

    If you only need to extract the values from a map (not the keys),

    you can also use \l{foreach}:

    \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 12

    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:

    \snippet doc/src/snippets/code/src_corelib_tools_qmap.cpp 13

    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.

    Two maps are considered equal if they contain the same (key,

    value) pairs.

    This function requires the value type to implement \c

    operator==().

    \sa operator!=()

*/

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

    Returns true if \a other is not equal to this map; otherwise

    returns false.

    Two maps are considered equal if they contain the same (key,

    value) pairs.

    This function requires the value type to implement \c

    operator==().

    \sa operator==()

*/

/*! \fn int QMap::size() const

    Returns the number of (key, value) pairs in the map.

    \sa isEmpty(), count()

*/

/*!

    \fn bool QMap::isEmpty() const

    Returns true if the map contains no items; otherwise returns

    false.

    \sa size()

*/

/*! \fn void QMap::detach()

    \internal

    Detaches this map from any other maps with which it may share

    data.

    \sa isDetached()

*/

/*! \fn bool QMap::isDetached() const

    \internal

    Returns true if the map's internal data isn't shared with any

    other map object; otherwise returns false.

    \sa detach()

*/

/*! \fn void QMap::setSharable(bool sharable)

    \internal

*/

/*! \fn void QMap::setInsertInOrder(bool sharable)

    \internal

*/

/*! \fn void QMap::clear()

    Removes all items from the map.

    \sa remove()

*/

/*! \fn int QMap::remove(const Key &key)

    Removes all the items that have the key \a key from the map.

    Returns the number of items removed which is usually 1 but will be

    0 if the key isn't in the map, or \> 1 if insertMulti() has been

    used with the \a key.

    \sa clear(), take(), QMultiMap::remove()

*/

/*! \fn T QMap::take(const Key &key)

    Removes the item with the key \a key from the map and returns

    the value associated with it.

    If the item does not exist in the map, the function simply

    returns a \l{default-constructed value}. If there are multiple

    items for \a key in the map, only the most recently inserted one

    is removed and returned.

    If you don't use the return value, remove() is more efficient.

    \sa remove()

*/

/*! \fn bool QMap::contains(const Key &key) const

    Returns true if the map contains an item with key \a key;

    otherwise returns false.

    \sa count(), QMultiMap::contains()

*/

/*! \fn const T QMap::value(const Key &key) const

    Returns the value associated with the key \a key.

    If the map contains no item with key \a key, the function

    returns a \l{default-constructed value}. If there are multiple

    items for \a key in the map, the value of the most recently

    inserted one is returned.

    \sa key(), values(), contains(), operator[]()

*/

/*! \fn const T QMap::value(const Key &key, const T &defaultValue) const

    \overload

    If the map contains no item with key \a key, the function returns

    \a defaultValue.

*/

/*! \fn T &QMap::operator[](const Key &key)

    Returns the value associated with the key \a key as a modifiable

    reference.

    If the map contains no item with key \a key, the function inserts

    a \l{default-constructed value} into the map with key \a key, and

    returns a reference to it. If the map contains multiple items

    with key \a key, this function returns a reference to the most

    recently inserted value.