/******************************************************************************** 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 sales@trolltech.com.**** 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;}#ifdef QT_QHASH_DEBUG#include <qstring.h>void QHashData::dump(){    qDebug("Hash data (ref = %d, size = %d, nodeSize = %d, userNumBits = %d, numBits = %d, numBuckets = %d)",            int(ref), size, nodeSize, userNumBits, numBits,            numBuckets);    qDebug("    %p (fakeNode = %p)", this, fakeNext);    for (int i = 0; i < numBuckets; ++i) {        QString line;        Node *n = buckets[i];        if (n != reinterpret_cast<Node *>(this)) {            line.sprintf("%d:", i);            while (n != reinterpret_cast<Node *>(this)) {                line += QString().sprintf(" -> [%p]", n);                if (!n) {                    line += " (CORRUPT)";                    break;                }                n = n->next;            }            qDebug(qPrintable(line));        }    }}void QHashData::checkSanity(){    if (fakeNext)        qFatal("Fake next isn't 0");    for (int i = 0; i < numBuckets; ++i) {        Node *n = buckets[i];        Node *p = n;        if (!n)            qFatal("%d: Bucket entry is 0", i);        if (n != reinterpret_cast<Node *>(this)) {            while (n != reinterpret_cast<Node *>(this)) {                if (!n->next)                    qFatal("%d: Next of %p is 0, should be %p", i, n, this);                n = n->next;            }        }    }}#endif/*!    \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. (See \l{Algorithmic       Complexity} for details.)    \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