📄 qgdict.cpp
字号:
/****************************************************************************** $Id: qt/src/tools/qgdict.cpp 2.2.3 edited 2000-08-25 $**** Implementation of QGDict and QGDictIterator classes**** Created : 920529**** Copyright (C) 1992-2000 Trolltech AS. All rights reserved.**** This file is part of the tools module of the Qt GUI Toolkit.**** This file may be distributed under the terms of the Q Public License** as defined by Trolltech AS of Norway and appearing in the file** LICENSE.QPL included in the packaging of this file.**** This file may be distributed and/or modified under the terms of the** GNU General Public License version 2 as published by the Free Software** Foundation and appearing in the file LICENSE.GPL included in the** packaging of this file.**** Licensees holding valid Qt Enterprise Edition or Qt Professional Edition** licenses may use this file in accordance with the Qt Commercial License** Agreement provided with the Software.**** This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE** WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.**** See http://www.trolltech.com/pricing.html or email sales@trolltech.com for** information about Qt Commercial License Agreements.** See http://www.trolltech.com/qpl/ for QPL licensing information.** See http://www.trolltech.com/gpl/ for GPL licensing information.**** Contact info@trolltech.com if any conditions of this licensing are** not clear to you.************************************************************************/#include "qgdict.h"#include "qlist.h"#include "qstring.h"#include "qdatastream.h"#include <ctype.h>// NOT REVISED/*! \class QGDict qgdict.h \brief The QGDict class is an internal class for implementing QDict template classes. QGDict is a strictly internal class that acts as a base class for the \link collection.html collection classes\endlink QDict and QIntDict. QGDict has some virtual functions that can be reimplemented to customize the subclasses. <ul> <li> read() reads a collection/dictionary item from a QDataStream. <li> write() writes a collection/dictionary item to a QDataStream. </ul> 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 QGDItList : public QList<QGDictIterator>{public: QGDItList() : QList<QGDictIterator>() {} QGDItList( const QGDItList &list ) : QList<QGDictIterator>(list) {} ~QGDItList() { clear(); } QGDItList &operator=(const QGDItList &list) { return (QGDItList&)QList<QGDictIterator>::operator=(list); }};/***************************************************************************** Default implementation of special and virtual functions *****************************************************************************//*! \internal Returns the hash key for \e key, when key is a string.*/int QGDict::hashKeyString( const QString &key ){#if defined(CHECK_NULL) if ( key.isNull() ) qWarning( "QGDict::hashStringKey: 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;}/*! \internal Returns the hash key for \a key, which is a C string.*/int QGDict::hashKeyAscii( const char *key ){#if defined(CHECK_NULL) if ( key == 0 ) qWarning( "QGDict::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(*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/*! Reads a collection/dictionary item from the stream \e s and returns a reference to the stream. The default implementation sets \e item to 0. \sa write()*/QDataStream& QGDict::read( QDataStream &s, QCollection::Item &item ){ item = 0; return s;}/*! Writes a collection/dictionary item to the stream \e s and returns a reference to the stream. \sa read()*/QDataStream& QGDict::write( QDataStream &s, QCollection::Item ) const{ return s;}#endif //QT_NO_DATASTREAM/***************************************************************************** QGDict member functions *****************************************************************************//*! \internal Constructs a dictionary.*/QGDict::QGDict( uint len, KeyType kt, bool caseSensitive, bool copyKeys ){ init( len, kt, caseSensitive, copyKeys );}void QGDict::init( uint len, KeyType kt, bool caseSensitive, bool copyKeys ){ vec = new QBaseBucket *[vlen = len]; // allocate hash table CHECK_PTR( vec ); memset( (char*)vec, 0, vlen*sizeof(QBaseBucket*) ); 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; }}/*! \internal Constructs a copy of \e dict.*/QGDict::QGDict( const QGDict & dict ) : QCollection( dict ){ init( dict.vlen, (KeyType)dict.keytype, dict.cases, dict.copyk ); QGDictIterator 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; }}/*! \internal Removes all items from the dictionary and destroys it.*/QGDict::~QGDict(){ clear(); // delete everything delete [] vec; if ( !iterators ) // no iterators for this dict return; QGDictIterator *i = iterators->first(); while ( i ) { // notify all iterators that i->dict = 0; // this dict is deleted i = iterators->next(); } delete iterators;}/*! \internal Assigns \e dict to this dictionary.*/QGDict &QGDict::operator=( const QGDict &dict ){ clear(); QGDictIterator 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 QCollection::Item QGDictIterator::get() const \internal*//*! \fn QString QGDictIterator::getKeyString() const \internal*//*! \fn const char * QGDictIterator::getKeyAscii() const \internal*//*! \fn void * QGDictIterator::getKeyPtr() const \internal*//*! \fn long QGDictIterator::getKeyInt() const \internal*//*! \fn uint QGDict::count() const \internal Returns the number of items in the dictionary.*//*! \fn uint QGDict::size() const \internal Returns the size of the hash array.*//*! \internal The do-it-all function; op is one of op_find, op_insert, op_replace*/QCollection::Item QGDict::look_string( const QString &key, QCollection::Item d, int op ){ QStringBucket *n; int index = hashKeyString(key) % vlen; if ( op == op_find ) { // find if ( cases ) { for ( n=(QStringBucket*)vec[index]; n; n=(QStringBucket*)n->getNext() ) { if ( key == n->getKey() ) return n->getData(); // item found } } else { QString k = key.lower(); for ( n=(QStringBucket*)vec[index]; n; n=(QStringBucket*)n->getNext() ) { if ( k == n->getKey().lower() ) return n->getData(); // item found } } 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 QStringBucket(key,newItem(d),vec[index]); CHECK_PTR( n );#if defined(CHECK_NULL) if ( n->getData() == 0 ) qWarning( "QDict: Cannot insert null item" );#endif vec[index] = n; numItems++; return n->getData();}/*! \internal */QCollection::Item QGDict::look_ascii( const char *key, QCollection::Item d, int op ){ QAsciiBucket *n; int index = hashKeyAscii(key) % vlen; if ( op == op_find ) { // find if ( cases ) { for ( n=(QAsciiBucket*)vec[index]; n; n=(QAsciiBucket*)n->getNext() ) { if ( qstrcmp(n->getKey(),key) == 0 ) return n->getData(); // item found } } else { for ( n=(QAsciiBucket*)vec[index]; n; n=(QAsciiBucket*)n->getNext() ) { if ( qstricmp(n->getKey(),key) == 0 ) return n->getData(); // item found } } return 0; // not found } if ( op == op_replace ) { // replace if ( vec[index] != 0 ) // maybe something there remove_ascii( key ); } // op_insert or op_replace n = new QAsciiBucket(copyk ? qstrdup(key) : key,newItem(d),vec[index]); CHECK_PTR( n );#if defined(CHECK_NULL) if ( n->getData() == 0 ) qWarning( "QAsciiDict: Cannot insert null item" );#endif vec[index] = n; numItems++; return n->getData();}/*! \internal */QCollection::Item QGDict::look_int( long key, QCollection::Item d, int op ){ QIntBucket *n; int index = (int)((ulong)key % vlen); // simple hash if ( op == op_find ) { // find for ( n=(QIntBucket*)vec[index]; n; n=(QIntBucket*)n->getNext() ) { if ( n->getKey() == key ) return n->getData(); // item found } return 0; // not found } if ( op == op_replace ) { // replace if ( vec[index] != 0 ) // maybe something there remove_int( key ); } // op_insert or op_replace n = new QIntBucket(key,newItem(d),vec[index]); CHECK_PTR( n );#if defined(CHECK_NULL) if ( n->getData() == 0 ) qWarning( "QIntDict: Cannot insert null item" );#endif vec[index] = n; numItems++; return n->getData();}/*! \internal */QCollection::Item QGDict::look_ptr( void *key, QCollection::Item d, int op ){ QPtrBucket *n; int index = (int)((ulong)key % vlen); // simple hash if ( op == op_find ) { // find for ( n=(QPtrBucket*)vec[index]; n; n=(QPtrBucket*)n->getNext() ) { if ( n->getKey() == key ) return n->getData(); // item found } return 0; // not found } if ( op == op_replace ) { // replace if ( vec[index] != 0 ) // maybe something there remove_ptr( key ); } // op_insert or op_replace n = new QPtrBucket(key,newItem(d),vec[index]); CHECK_PTR( n );#if defined(CHECK_NULL) if ( n->getData() == 0 ) qWarning( "QPtrDict: Cannot insert null item" );#endif vec[index] = n; numItems++; return n->getData();}/*! \internal Changes the size of the hashtable. The contents of the dictionary are preserved, but all iterators on the dictionary become invalid.*/void QGDict::resize( uint newsize ){ // Save old information QBaseBucket **old_vec = vec; uint old_vlen = vlen; bool old_copyk = copyk; vec = new QBaseBucket *[vlen = newsize]; CHECK_PTR( vec ); memset( (char*)vec, 0, vlen*sizeof(QBaseBucket*) ); numItems = 0; copyk = FALSE; // Reinsert every item from vec, deleting vec as we go for ( uint index = 0; index < old_vlen; index++ ) { switch ( keytype ) { case StringKey: { QStringBucket *n=(QStringBucket *)old_vec[index]; while ( n ) { look_string( n->getKey(), n->getData(), op_insert ); QStringBucket *t=(QStringBucket *)n->getNext(); delete n; n = t; } } break; case AsciiKey: { QAsciiBucket *n=(QAsciiBucket *)old_vec[index]; while ( n ) { look_ascii( n->getKey(), n->getData(), op_insert ); QAsciiBucket *t=(QAsciiBucket *)n->getNext(); delete n; n = t; } } break; case IntKey: { QIntBucket *n=(QIntBucket *)old_vec[index]; while ( n ) { look_int( n->getKey(), n->getData(), op_insert ); QIntBucket *t=(QIntBucket *)n->getNext(); delete n; n = t; } } break; case PtrKey: { QPtrBucket *n=(QPtrBucket *)old_vec[index]; while ( n ) { look_ptr( n->getKey(), n->getData(), op_insert ); QPtrBucket *t=(QPtrBucket *)n->getNext(); delete n; n = t; } } break; } } delete [] old_vec; // Restore state copyk = old_copyk; // Invalidate all iterators, since order is lost if ( iterators && iterators->count() ) { QGDictIterator *i = iterators->first(); while ( i ) { i->toFirst(); i = iterators->next(); } }}/*! \internal Unlinks the bucket with the specified key (and specified data pointer, if it is set).*/void QGDict::unlink_common( int index, QBaseBucket *node, QBaseBucket *prev ){ if ( iterators && iterators->count() ) { // update iterators QGDictIterator *i = iterators->first(); while ( i ) { // invalidate all iterators if ( i->curNode == node ) // referring to pending node i->operator++(); i = iterators->next(); } } if ( prev ) // unlink node prev->setNext( node->getNext() ); else vec[index] = node->getNext(); numItems--;}QStringBucket *QGDict::unlink_string( const QString &key, QCollection::Item d ){ if ( numItems == 0 ) // nothing in dictionary return 0; QStringBucket *n; QStringBucket *prev = 0; int index = hashKeyString(key) % vlen; if ( cases ) { for ( n=(QStringBucket*)vec[index]; n; n=(QStringBucket*)n->getNext() ) { bool found = (key == n->getKey());
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -