qhash.cpp

qt-x11-opensource-src-4.1.4.tar.gz源码

/****************************************************************************
**
** Copyright (C) 1992-2006 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://www.trolltech.com/products/qt/opensource.html
**
** If you are unsure which license is appropriate for your use, please
** review the following information:
** http://www.trolltech.com/products/qt/licensing.html or contact the
** sales department at [e-mail].
**
** 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 "qhash.h"

#ifdef truncate
#undef truncate
#endif

#include <qbytearray.h>
#include <qstring.h>
#include <stdlib.h>

/*
    These functions are based on Peter J. Weinberger's hash function
    (from the Dragon Book). The constant 24 in the original function
    was replaced with 23 to produce fewer collisions on input such as
    "a", "aa", "aaa", "aaaa", ...
*/

uint qHash(const QByteArray &key)
{
    const uchar *p = reinterpret_cast<const uchar *>(key.data());
    int n = key.size();
    uint h = 0;
    uint g;

    while (n--) {
        h = (h << 4) + *p++;
        if ((g = (h & 0xf0000000)) != 0)
            h ^= g >> 23;
        h &= ~g;
    }
    return h;
}

uint qHash(const QString &key)
{
    const QChar *p = key.unicode();
    int n = key.size();
    uint h = 0;
    uint g;

    while (n--) {
        h = (h << 4) + (*p++).unicode();
        if ((g = (h & 0xf0000000)) != 0)
            h ^= g >> 23;
        h &= ~g;
    }
    return h;
}

/*
    The prime_deltas array is a table of selected prime values, even
    though it doesn't look like one. The primes we are using are 1,
    2, 5, 11, 17, 37, 67, 131, 257, ..., i.e. primes in the immediate
    surrounding of a power of two.

    The primeForNumBits() function returns the prime associated to a
    power of two. For example, primeForNumBits(8) returns 257.
*/

static const uchar prime_deltas[] = {
    0,  0,  1,  3,  1,  5,  3,  3,  1,  9,  7,  5,  3,  9, 25,  3,
    1, 21,  3, 21,  7, 15,  9,  5,  3, 29, 15,  0,  0,  0,  0,  0
};

static inline int primeForNumBits(int numBits)
{
    return (1 << numBits) + prime_deltas[numBits];
}

/*
    Returns the smallest integer n such that
    primeForNumBits(n) >= hint.
*/
static int countBits(int hint)
{
    int numBits = 0;
    int bits = hint;

    while (bits > 1) {
        bits >>= 1;
        numBits++;
    }

    if (numBits >= (int)sizeof(prime_deltas)) {
        numBits = sizeof(prime_deltas) - 1;
    } else if (primeForNumBits(numBits) < hint) {
        ++numBits;
    }
    return numBits;
}

/*
    A QHash has initially around pow(2, MinNumBits) buckets. For
    example, if MinNumBits is 4, it has 17 buckets.
*/
const int MinNumBits = 4;

QHashData QHashData::shared_null = {
    0, 0, Q_ATOMIC_INIT(1), 0, 0, MinNumBits, 0, 0, true
};

void *QHashData::allocateNode()
{
    return ::malloc(nodeSize);
}

void QHashData::freeNode(void *node)
{
    ::free(node);
}

QHashData *QHashData::detach_helper(void (*node_duplicate)(Node *, void *), int nodeSize)
{
    union {
        QHashData *d;
        Node *e;
    };
    d = new QHashData;
    d->fakeNext = 0;
    d->buckets = 0;
    d->ref.init(1);
    d->size = size;
    d->nodeSize = nodeSize;
    d->userNumBits = userNumBits;
    d->numBits = numBits;
    d->numBuckets = numBuckets;
    d->sharable = true;

    if (numBuckets) {
        d->buckets = new Node *[numBuckets];
        Node *this_e = reinterpret_cast<Node *>(this);
        for (int i = 0; i < numBuckets; ++i) {
            Node **nextNode = &d->buckets[i];
            Node *oldNode = buckets[i];
            while (oldNode != this_e) {
                Node *dup = static_cast<Node *>(allocateNode());
                node_duplicate(oldNode, dup);
                dup->h = oldNode->h;
                *nextNode = dup;
                nextNode = &dup->next;
                oldNode = oldNode->next;
            }
            *nextNode = e;
        }
    }
    return d;
}

QHashData::Node *QHashData::nextNode(Node *node)
{
    union {
        Node *next;
        Node *e;
        QHashData *d;
    };
    next = node->next;
    Q_ASSERT_X(next, "QHash", "Iterating beyond end()");
    if (next->next)
        return next;

    int start = (node->h % d->numBuckets) + 1;
    Node **bucket = d->buckets + start;
    int n = d->numBuckets - start;
    while (n--) {
        if (*bucket != e)
            return *bucket;
        ++bucket;
    }
    return e;
}

QHashData::Node *QHashData::previousNode(Node *node)
{
    union {
        Node *e;
        QHashData *d;
    };

    e = node;
    while (e->next)
        e = e->next;

    int start;
    if (node == e)
        start = d->numBuckets - 1;
    else
        start = node->h % d->numBuckets;

    Node *sentinel = node;
    Node **bucket = d->buckets + start;
    while (start >= 0) {
        if (*bucket != sentinel) {
            Node *prev = *bucket;
            while (prev->next != sentinel)
                prev = prev->next;
            return prev;
        }

        sentinel = e;
        --bucket;
        --start;
    }
    Q_ASSERT_X(start >= 0, "QHash", "Iterating backward beyond begin()");
    return e;
}

/*
    If hint is negative, -hint gives the approximate number of
    buckets that should be used for the hash table. If hint is
    nonnegative, (1 << hint) gives the approximate number
    of buckets that should be used.
*/
void QHashData::rehash(int hint)
{
    if (hint < 0) {
        hint = countBits(-hint);
        if (hint < MinNumBits)
            hint = MinNumBits;
        userNumBits = hint;
        while (primeForNumBits(hint) < (size >> 1))
            ++hint;
    } else if (hint < MinNumBits) {
        hint = MinNumBits;
    }

    if (numBits != hint) {
        Node *e = reinterpret_cast<Node *>(this);
        Node **oldBuckets = buckets;
        int oldNumBuckets = numBuckets;

        numBits = hint;
        numBuckets = primeForNumBits(hint);
        buckets = new Node *[numBuckets];
        for (int i = 0; i < numBuckets; ++i)
            buckets[i] = e;

        for (int i = 0; i < oldNumBuckets; ++i) {
            Node *firstNode = oldBuckets[i];
            while (firstNode != e) {
                uint h = firstNode->h;
                Node *lastNode = firstNode;
                while (lastNode->next != e && lastNode->next->h == h)
                    lastNode = lastNode->next;

                Node *afterLastNode = lastNode->next;
                Node **beforeFirstNode = &buckets[h % numBuckets];
                while (*beforeFirstNode != e)
                    beforeFirstNode = &(*beforeFirstNode)->next;
                lastNode->next = *beforeFirstNode;
                *beforeFirstNode = firstNode;
                firstNode = afterLastNode;
            }
        }
        delete [] oldBuckets;
    }
}

void QHashData::destroyAndFree()
{
    delete [] buckets;
    delete this;
}

/*!
    \class QHash
    \brief The QHash class is a template class that provides a hash-table-based dictionary.

    \ingroup tools
    \ingroup shared
    \mainclass
    \reentrant

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

    QHash provides very similar functionality to QMap. The
    differences are:

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

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

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

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

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

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

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

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

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

    If you want to check whether the hash contains a particular key,
    use contains():

    \code
        int timeout = 30;
        if (hash.contains("TIMEOUT"))
            timeout = hash.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 = hash.value("TIMEOUT", 30);
    \endcode

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

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

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

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

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

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

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

    QHash is unordered, so an iterator's sequence cannot be assumed
    to be predictable. If ordering by key is required, use a QMap.

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

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

    However, you can store multiple values per key by using
    insertMulti() instead of insert() (or using the convenience
    subclass QMultiHash). 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 = hash.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. A more efficient approach is
    to call find() to get the iterator for the first item with a key
    and iterate from there:

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

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