q3gdict.cpp

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

/****************************************************************************
**
** Copyright (C) 1992-2007 Trolltech ASA. All rights reserved.
**
** This file is part of the Qt3Support 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 "q3gdict.h"
#include "q3ptrlist.h"
#include "qstring.h"
#include "qdatastream.h"
#include <ctype.h>

/*!
  \class Q3GDict
  \reentrant
  \brief The Q3GDict class is an internal class for implementing QDict template classes.

  \internal

  Q3GDict is a strictly internal class that acts as a base class for the
  \link collection.html collection classes\endlink QDict and QIntDict.

  Q3GDict has some virtual functions that can be reimplemented to customize
  the subclasses.
  \list
  \i read() reads a collection/dictionary item from a QDataStream.
  \i write() writes a collection/dictionary item to a QDataStream.
  \endlist
  Normally, you do not have to reimplement any of these functions.
*/

static const int op_find = 0;
static const int op_insert = 1;
static const int op_replace = 2;


class Q3GDItList : public Q3PtrList<Q3GDictIterator>
{
public:
    Q3GDItList() : Q3PtrList<Q3GDictIterator>() {}
    Q3GDItList(const Q3GDItList &list) : Q3PtrList<Q3GDictIterator>(list) {}
    ~Q3GDItList() { clear(); }
    Q3GDItList &operator=(const Q3GDItList &list)
        { return (Q3GDItList&)Q3PtrList<Q3GDictIterator>::operator=(list); }
};


/*****************************************************************************
  Default implementation of special and virtual functions
 *****************************************************************************/

/*!
  Returns the hash key for \a key, when key is a string.
*/

int Q3GDict::hashKeyString(const QString &key)
{
#if defined(QT_CHECK_NULL)
    if (key.isNull())
        qWarning("Q3GDict::hashKeyString: Invalid null key");
#endif
    int i;
    register uint h=0;
    uint g;
    const QChar *p = key.unicode();
    if (cases) {                                // case sensitive
        for (i=0; i<(int)key.length(); i++) {
            h = (h<<4) + p[i].cell();
            if ((g = h & 0xf0000000))
                h ^= g >> 24;
            h &= ~g;
        }
    } else {                                    // case insensitive
        for (i=0; i<(int)key.length(); i++) {
            h = (h<<4) + p[i].lower().cell();
            if ((g = h & 0xf0000000))
                h ^= g >> 24;
            h &= ~g;
        }
    }
    int index = h;
    if (index < 0)                              // adjust index to table size
        index = -index;
    return index;
}

/*!
  Returns the hash key for \a key, which is a C string.
*/

int Q3GDict::hashKeyAscii(const char *key)
{
#if defined(QT_CHECK_NULL)
    if (key == 0)
        qWarning("Q3GDict::hashAsciiKey: Invalid null key");
#endif
    register const char *k = key;
    register uint h=0;
    uint g;
    if (cases) {                                // case sensitive
        while (*k) {
            h = (h<<4) + *k++;
            if ((g = h & 0xf0000000))
                h ^= g >> 24;
            h &= ~g;
        }
    } else {                                    // case insensitive
        while (*k) {
            h = (h<<4) + tolower((uchar) *k);
            if ((g = h & 0xf0000000))
                h ^= g >> 24;
            h &= ~g;
            k++;
        }
    }
    int index = h;
    if (index < 0)                              // adjust index to table size
        index = -index;
    return index;
}

#ifndef QT_NO_DATASTREAM

/*!
    \overload
  Reads a collection/dictionary item from the stream \a s and returns a
  reference to the stream.

  The default implementation sets \a item to 0.

  \sa write()
*/

QDataStream& Q3GDict::read(QDataStream &s, Q3PtrCollection::Item &item)
{
    item = 0;
    return s;
}

/*!
    \overload
  Writes a collection/dictionary item to the stream \a s and returns a
  reference to the stream.

  \sa read()
*/

QDataStream& Q3GDict::write(QDataStream &s, Q3PtrCollection::Item) const
{
    return s;
}
#endif //QT_NO_DATASTREAM

/*****************************************************************************
  Q3GDict member functions
 *****************************************************************************/

/*!
  Constructs a dictionary.

  \a len is the initial size of the dictionary.
  The key type is \a kt which may be \c StringKey, \c AsciiKey,
  \c IntKey or \c PtrKey. The case-sensitivity of lookups is set with
  \a caseSensitive. Keys are copied if \a copyKeys is true.
*/

Q3GDict::Q3GDict(uint len, KeyType kt, bool caseSensitive, bool copyKeys)
{
    init(len, kt, caseSensitive, copyKeys);
}


void Q3GDict::init(uint len, KeyType kt, bool caseSensitive, bool copyKeys)
{
    vlen = len ? len : 17;
    vec = new Q3BaseBucket *[ vlen ];

    Q_CHECK_PTR(vec);
    memset((char*)vec, 0, vlen*sizeof(Q3BaseBucket*));
    numItems  = 0;
    iterators = 0;
    // The caseSensitive and copyKey options don't make sense for
    // all dict types.
    switch ((keytype = (uint)kt)) {
        case StringKey:
            cases = caseSensitive;
            copyk = false;
            break;
        case AsciiKey:
            cases = caseSensitive;
            copyk = copyKeys;
            break;
        default:
            cases = false;
            copyk = false;
            break;
    }
}


/*!
  Constructs a copy of \a dict.
*/

Q3GDict::Q3GDict(const Q3GDict & dict)
    : Q3PtrCollection(dict)
{
    init(dict.vlen, (KeyType)dict.keytype, dict.cases, dict.copyk);
    Q3GDictIterator it(dict);
    while (it.get()) {                  // copy from other dict
        switch (keytype) {
            case StringKey:
                look_string(it.getKeyString(), it.get(), op_insert);
                break;
            case AsciiKey:
                look_ascii(it.getKeyAscii(), it.get(), op_insert);
                break;
            case IntKey:
                look_int(it.getKeyInt(), it.get(), op_insert);
                break;
            case PtrKey:
                look_ptr(it.getKeyPtr(), it.get(), op_insert);
                break;
        }
        ++it;
    }
}


/*!
  Removes all items from the dictionary and destroys it.
*/

Q3GDict::~Q3GDict()
{
    clear();                                    // delete everything
    delete [] vec;
    if (!iterators)                             // no iterators for this dict
        return;
    Q3GDictIterator *i = iterators->first();
    while (i) {                         // notify all iterators that
        i->dict = 0;                            // this dict is deleted
        i = iterators->next();
    }
    delete iterators;
}


/*!
  Assigns \a dict to this dictionary.
*/

Q3GDict &Q3GDict::operator=(const Q3GDict &dict)
{
    if (&dict == this)
        return *this;
    clear();
    Q3GDictIterator it(dict);
    while (it.get()) {                  // copy from other dict
        switch (keytype) {
            case StringKey:
                look_string(it.getKeyString(), it.get(), op_insert);
                break;
            case AsciiKey:
                look_ascii(it.getKeyAscii(), it.get(), op_insert);
                break;
            case IntKey:
                look_int(it.getKeyInt(), it.get(), op_insert);
                break;
            case PtrKey:
                look_ptr(it.getKeyPtr(), it.get(), op_insert);
                break;
        }
        ++it;
    }
    return *this;
}

/*!
  \fn uint Q3GDict::count() const

  Returns the number of items in the dictionary.
*/

/*!
  \fn uint Q3GDict::size() const

  Returns the size of the hash array.
*/

/*!
  The do-it-all function; \a op is one of op_find, op_insert, op_replace.
  The key is \a key and the item is \a d.
*/

Q3PtrCollection::Item Q3GDict::look_string(const QString &key, Q3PtrCollection::Item d,
                                       int op)
{
    Q3StringBucket *n = 0;
    int index = hashKeyString(key) % vlen;
    if (op == op_find) {                        // find
        if (cases) {
            n = (Q3StringBucket*)vec[index];
            while(n != 0) {
                if (key == n->getKey())
                    return n->getData();        // item found
                n = (Q3StringBucket*)n->getNext();
            }
        } else {
            QString k = key.lower();
            n = (Q3StringBucket*)vec[index];
            while(n != 0) {
                if (k == n->getKey().lower())
                    return n->getData();        // item found
                n = (Q3StringBucket*)n->getNext();
            }
        }
        return 0;                               // not found
    }
    if (op == op_replace) {                     // replace
        if (vec[index] != 0)                    // maybe something there
            remove_string(key);
    }
    // op_insert or op_replace
    n = new Q3StringBucket(key,newItem(d),vec[index]);
    Q_CHECK_PTR(n);
#if defined(QT_CHECK_NULL)
    if (n->getData() == 0)
        qWarning("QDict: Cannot insert null item");
#endif
    vec[index] = n;
    numItems++;
    return n->getData();
}

Q3PtrCollection::Item Q3GDict::look_ascii(const char *key, Q3PtrCollection::Item d, int op)
{
    Q3AsciiBucket *n;
    int index = hashKeyAscii(key) % vlen;
    if (op == op_find) {                        // find
        if (cases) {
            for (n=(Q3AsciiBucket*)vec[index]; n;
                  n=(Q3AsciiBucket*)n->getNext()) {
                if (qstrcmp(n->getKey(),key) == 0)
                    return n->getData();        // item found
            }
        } else {
            for (n=(Q3AsciiBucket*)vec[index]; n;
                  n=(Q3AsciiBucket*)n->getNext()) {
                if (qstricmp(n->getKey(),key) == 0)
                    return n->getData();        // item found
            }