/****************************************************************************
**
**
** 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 "qinternallist.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 QInternalList<QGDictIterator>
{
public:
QGDItList() : QInternalList<QGDictIterator>() {}
QGDItList( const QGDItList &list ) : QInternalList<QGDictIterator>(list) {}
~QGDItList() { clear(); }
QGDItList &operator=(const QGDItList &list)
{ return (QGDItList&)QInternalList<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;
int len = key.length();
const QChar *p = key.unicode();
if ( cases ) { // case sensitive
for ( i=0; i<len; i++ ) {
h = (h<<4) + p[i].cell();
if ( (g = h & 0xf0000000) )
h ^= g >> 24;
h &= ~g;
}
} else { // case insensitive
for ( i=0; i<len; 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" );
return 0;
}
#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;
}
#if 0
int QGDict::hashKeyAscii( const char *key )
{
#if defined(CHECK_NULL)
if ( key == 0 )
{
qWarning( "QGDict::hashAsciiKey: Invalid null key" );
return 0;
}
#endif
unsigned int hash = 5381;
int c;
// use djb2 by Dan Bernstein
if (cases)
{
while ((c=*key++)) hash = ((hash<<5)+hash)+c;
}
else
{
while ((c=*key++)) hash = ((hash<<5)+hash)+tolower(c);
}
int index = hash;
return index<0 ? -index : index;
}
#endif
#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)((uintptr_t)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());
if ( found && d )
found = (n->getData() == d);
if ( found ) {
unlink_common(index,n,prev);
return n;
}
prev = n;
}
} else {
QString k = key.lower();
for ( n=(QStringBucket*)vec[index]; n;
n=(QStringBucket*)n->getNext() ) {
bool found = (k == n->getKey().lower());
if ( found && d )
found = (n->getData() == d);
if ( found ) {
unlink_common(index,n,prev);
return n;
}
prev = n;
}
}
return 0;
}
QAsciiBucket *QGDict::unlink_ascii( const char *key, QCollection::Item d )
{
if ( numItems == 0 ) // nothing in dictionary
return 0;
QAsciiBucket *n;
QAsciiBucket *prev = 0;
int index = hashKeyAscii(key) % vlen;
for ( n=(QAsciiBucket *)vec[index]; n; n=(QAsciiBucket *)n->getNext() ) {
bool found = (cases ? qstrcmp(n->getKey(),key)
: qstricmp(n->getKey(),key)) == 0;
if ( found && d )
found = (n->getData() == d);
if ( found ) {
unlink_common(index,n,prev);
return n;
}
prev = n;
}
return 0;
}
QIntBucket *QGDict::unlink_int( long key, QCollection::Item d )
{
if ( numItems == 0 ) // nothing in dictionary
return 0;
QIntBucket *n;
QIntBucket *prev = 0;
int index = (int)((ulong)key % vlen);
for ( n=(QIntBucket *)vec[index]; n; n=(QIntBucket *)n->getNext() ) {
bool found = (n->getKey() == key);
if ( found && d )
found = (n->getData() == d);
if ( found ) {
unlink_common(index,n,prev);
return n;
}
prev = n;
}
return 0;
}
QPtrBucket *QGDict::unlink_ptr( void *key, QCollection::Item d )
{
if ( numItems == 0 ) // nothing in dictionary
return 0;
QPtrBucket *n;
QPtrBucket *prev = 0;
int index = (int)((uintptr_t)key % vlen);
for ( n=(QPtrBucket *)vec[index]; n; n=(QPtrBucket *)n->getNext() ) {
bool found = (n->getKey() == key);
if ( found && d )
found = (n->getData() == d);
if ( found ) {
unlink_common(index,n,prev);
return n;
}
prev = n;
}
return 0;
}
/*!
\internal
Removes the item with the specified key. If item is non-null,
the remove will match the \a item as well (used to remove an
item when several items have the same key).
*/
bool QGDict::remove_string( const QString &key, QCollection::Item item )
{
QStringBucket *n = unlink_string( key, item );
if ( n ) {
deleteItem( n->getData() );
delete n;
return TRUE;
} else {
return FALSE;
}
}
/*! \internal */
bool QGDict::remove_ascii( const char *key, QCollection::Item item )
{
QAsciiBucket *n = unlink_ascii( key, item );
if ( n ) {
if ( copyk )
delete [] (char *)n->getKey();
deleteItem( n->getData() );
delete n;
}
return n != 0;
}
/*! \internal */
bool QGDict::remove_int( long key, QCollection::Item item )
{
QIntBucket *n = unlink_int( key, item );
if ( n ) {
deleteItem( n->getData() );
delete n;
}
return n != 0;
}
/*! \internal */
bool QGDict::remove_ptr( void *key, QCollection::Item item )
{
QPtrBucket *n = unlink_ptr( key, item );
if ( n ) {
deleteItem( n->getData() );
delete n;
}
return n != 0;
}
/*! \internal */
QCollection::Item QGDict::take_string( const QString &key )
{
QStringBucket *n = unlink_string( key );
Item d;
if ( n ) {
d = n->getData();
delete n;
} else {
d = 0;
}
return d;
}
/*! \internal */
QCollection::Item QGDict::take_ascii( const char *key )
{
QAsciiBucket *n = unlink_ascii( key );
Item d;
if ( n ) {
if ( copyk )
delete [] (char *)n->getKey();
d = n->getData();
delete n;
} else {
d = 0;
}
return d;
}
/*! \internal */
QCollection::Item QGDict::take_int( long key )
{
QIntBucket *n = unlink_int( key );
Item d;
if ( n ) {
d = n->getData();
delete n;
} else {
d = 0;
}
return d;
}
/*! \internal */
QCollection::Item QGDict::take_ptr( void *key )
{
QPtrBucket *n = unlink_ptr( key );
Item d;
if ( n ) {
d = n->getData();
delete n;
} else {
d = 0;
}
return d;
}
/*!
\internal
Removes all items from the dictionary.
*/
void QGDict::clear()
{
if ( !numItems )
return;
numItems = 0; // disable remove() function
for ( uint j=0; j<vlen; j++ ) { // destroy hash table
if ( vec[j] ) {
switch ( keytype ) {
case StringKey:
{
QStringBucket *n=(QStringBucket *)vec[j];
while ( n ) {
QStringBucket *next = (QStringBucket*)n->getNext();
deleteItem( n->getData() );
delete n;
n = next;
}
}
break;
case AsciiKey:
{
QAsciiBucket *n=(QAsciiBucket *)vec[j];
while ( n ) {
QAsciiBucket *next = (QAsciiBucket*)n->getNext();
if ( copyk )
delete [] (char *)n->getKey();
deleteItem( n->getData() );
delete n;
n = next;
}
}
break;
case IntKey:
{
QIntBucket *n=(QIntBucket *)vec[j];
while ( n ) {
QIntBucket *next = (QIntBucket*)n->getNext();
deleteItem( n->getData() );
delete n;
n = next;
}
}
break;
case PtrKey:
{
QPtrBucket *n=(QPtrBucket *)vec[j];
while ( n ) {
QPtrBucket *next = (QPtrBucket*)n->getNext();
deleteItem( n->getData() );
delete n;
n = next;
}
}
break;
}
vec[j] = 0; // detach list of buckets
}
}
if ( iterators && iterators->count() ) { // invalidate all iterators
QGDictIterator *i = iterators->first();
while ( i ) {
i->curNode = 0;
i = iterators->next();
}
}
}
/*!
\internal
Outputs debug statistics.
*/
void QGDict::statistics() const
{
#if defined(DEBUG)
QString line;
line.fill( '-', 60 );
double real, ideal;
qDebug( "%s",line.ascii() );
qDebug( "DICTIONARY STATISTICS:" );
if ( count() == 0 ) {
qDebug( "Empty!" );
qDebug( "%s", line.ascii() );
return;
}
real = 0.0;
ideal = (float)count()/(2.0*size())*(count()+2.0*size()-1);
uint i = 0;
while ( i<size() ) {
QBaseBucket *n = vec[i];
int b = 0;
while ( n ) { // count number of buckets
b++;
n = n->getNext();
}
real = real + (double)b * ((double)b+1.0)/2.0;
char buf[80], *pbuf;
if ( b > 78 )
b = 78;
pbuf = buf;
while ( b-- )
*pbuf++ = '*';
*pbuf = '\0';
qDebug( "%s", buf );
i++;
}
qDebug( "Array size = %d", size() );
qDebug( "# items = %d", count() );
qDebug( "Real dist = %g", real );
qDebug( "Rand dist = %g", ideal );
qDebug( "Real/Rand = %g", real/ideal );
qDebug( "%s",line.ascii() );
#endif // DEBUG
}
/*****************************************************************************
QGDict stream functions
*****************************************************************************/
#ifndef QT_NO_DATASTREAM
QDataStream &operator>>( QDataStream &s, QGDict &dict )
{
return dict.read( s );
}
QDataStream &operator<<( QDataStream &s, const QGDict &dict )
{
return dict.write( s );
}
#if defined(_CC_DEC_) && defined(__alpha) && (__DECCXX_VER >= 50190001)
#pragma message disable narrowptr
#endif
/*!
\internal
Reads a dictionary from the stream \e s.
*/
QDataStream &QGDict::read( QDataStream &s )
{
uint num;
s >> num; // read number of items
clear(); // clear dict
while ( num-- ) { // read all items
Item d;
switch ( keytype ) {
case StringKey:
{
QString k;
s >> k;
read( s, d );
look_string( k, d, op_insert );
}
break;
case AsciiKey:
{
char *k;
s >> k;
read( s, d );
look_ascii( k, d, op_insert );
if ( copyk )
delete [] k;
}
break;
case IntKey:
{
Q_UINT32 k;
s >> k;
read( s, d );
look_int( k, d, op_insert );
}
break;
case PtrKey:
{
Q_UINT32 k;
s >> k;
read( s, d );
// ### cannot insert 0 - this renders the thing
// useless since all pointers are written as 0,
// but hey, serializing pointers? can it be done
// at all, ever?
if ( k )
look_ptr( (void *)(uintptr_t)k, d, op_insert );
}
break;
}
}
return s;
}
/*!
\internal
Writes the dictionary to the stream \e s.
*/
QDataStream& QGDict::write( QDataStream &s ) const
{
s << count(); // write number of items
uint i = 0;
while ( i<size() ) {
QBaseBucket *n = vec[i];
while ( n ) { // write all buckets
switch ( keytype ) {
case StringKey:
s << ((QStringBucket*)n)->getKey();
break;
case AsciiKey:
s << ((QAsciiBucket*)n)->getKey();
break;
case IntKey:
s << (Q_UINT32)((QIntBucket*)n)->getKey();
break;
case PtrKey:
s << (Q_UINT32)0; // ### cannot serialize a pointer
break;
}
write( s, n->getData() ); // write data
n = n->getNext();
}
i++;
}
return s;
}
#endif //QT_NO_DATASTREAM
/*****************************************************************************
QGDictIterator member functions
*****************************************************************************/
/*!
\class QGDictIterator qgdict.h
\brief An internal class for implementing QDictIterator and QIntDictIterator.
QGDictIterator is a strictly internal class that does the heavy work for
QDictIterator and QIntDictIterator.
*/
/*!
\internal
Constructs an iterator that operates on the dictionary \e d.
*/
QGDictIterator::QGDictIterator( const QGDict &d )
{
dict = (QGDict *)&d; // get reference to dict
toFirst(); // set to first noe
if ( !dict->iterators ) {
dict->iterators = new QGDItList; // create iterator list
CHECK_PTR( dict->iterators );
}
dict->iterators->append( this ); // attach iterator to dict
}
/*!
\internal
Constructs a copy of the iterator \e it.
*/
QGDictIterator::QGDictIterator( const QGDictIterator &it )
{
dict = it.dict;
curNode = it.curNode;
curIndex = it.curIndex;
if ( dict )
dict->iterators->append( this ); // attach iterator to dict
}
/*!
\internal
Assigns a copy of the iterator \e it and returns a reference to this
iterator.
*/
QGDictIterator &QGDictIterator::operator=( const QGDictIterator &it )
{
if ( dict ) // detach from old dict
dict->iterators->removeRef( this );
dict = it.dict;
curNode = it.curNode;
curIndex = it.curIndex;
if ( dict )
dict->iterators->append( this ); // attach to new list
return *this;
}
/*!
\internal
Destroys the iterator.
*/
QGDictIterator::~QGDictIterator()
{
if ( dict ) // detach iterator from dict
dict->iterators->removeRef( this );
}
/*!
\internal
Sets the iterator to point to the first item in the dictionary.
*/
QCollection::Item QGDictIterator::toFirst()
{
if ( !dict ) {
#if defined(CHECK_NULL)
qWarning( "QGDictIterator::toFirst: Dictionary has been deleted" );
#endif
return 0;
}
if ( dict->count() == 0 ) { // empty dictionary
curNode = 0;
return 0;
}
register uint i = 0;
register QBaseBucket **v = dict->vec;
while ( !(*v++) )
i++;
curNode = dict->vec[i];
curIndex = i;
return curNode->getData();
}
/*!
\internal
Moves to the next item (postfix).
*/
QCollection::Item QGDictIterator::operator()()
{
if ( !dict ) {
#if defined(CHECK_NULL)
qWarning( "QGDictIterator::operator(): Dictionary has been deleted" );
#endif
return 0;
}
if ( !curNode )
return 0;
QCollection::Item d = curNode->getData();
this->operator++();
return d;
}
/*!
\internal
Moves to the next item (prefix).
*/
QCollection::Item QGDictIterator::operator++()
{
if ( !dict ) {
#if defined(CHECK_NULL)
qWarning( "QGDictIterator::operator++: Dictionary has been deleted" );
#endif
return 0;
}
if ( !curNode )
return 0;
curNode = curNode->getNext();
if ( !curNode ) { // no next bucket
register uint i = curIndex + 1; // look from next vec element
register QBaseBucket **v = &dict->vec[i];
while ( i < dict->size() && !(*v++) )
i++;
if ( i == dict->size() ) { // nothing found
curNode = 0;
return 0;
}
curNode = dict->vec[i];
curIndex = i;
}
return curNode->getData();
}
/*!
\internal
Moves \e jumps positions forward.
*/
QCollection::Item QGDictIterator::operator+=( uint jumps )
{
while ( curNode && jumps-- )
operator++();
return curNode ? curNode->getData() : 0;
}