qgdict.cpp

Trolltech公司发布的图形界面操作系统。可在qt-embedded-2.3.10平台上编译为嵌入式图形界面操作系统。

		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, QPtrCollection::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, QPtrCollection::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, QPtrCollection::Item d )
{
    if ( numItems == 0 )			// nothing in dictionary
	return 0;
    QPtrBucket *n;
    QPtrBucket *prev = 0;
    int index = (int)((ulong)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;
}


/*!
  Removes the item with the specified \a key.  If \a item is not 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, QPtrCollection::Item item )
{
    QStringBucket *n = unlink_string( key, item );
    if ( n ) {
	deleteItem( n->getData() );
	delete n;
	return TRUE;
    } else {
	return FALSE;
    }
}

bool QGDict::remove_ascii( const char *key, QPtrCollection::Item item )
{
    QAsciiBucket *n = unlink_ascii( key, item );
    if ( n ) {
	if ( copyk )
	    delete [] (char *)n->getKey();
	deleteItem( n->getData() );
	delete n;
    }
    return n != 0;
}

bool QGDict::remove_int( long key, QPtrCollection::Item item )
{
    QIntBucket *n = unlink_int( key, item );
    if ( n ) {
	deleteItem( n->getData() );
	delete n;
    }
    return n != 0;
}

bool QGDict::remove_ptr( void *key, QPtrCollection::Item item )
{
    QPtrBucket *n = unlink_ptr( key, item );
    if ( n ) {
	deleteItem( n->getData() );
	delete n;
    }
    return n != 0;
}

QPtrCollection::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;
}

QPtrCollection::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;
}

QPtrCollection::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;
}

QPtrCollection::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;
}

/*!
  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();
	}
    }
}

/*!
  Outputs debug statistics.
*/
void QGDict::statistics() const
{
#if defined(QT_DEBUG)
    QString line;
    line.fill( '-', 60 );
    double real, ideal;
    qDebug( line.ascii() );
    qDebug( "DICTIONARY STATISTICS:" );
    if ( count() == 0 ) {
	qDebug( "Empty!" );
	qDebug( 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( 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( line.ascii() );
#endif // QT_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(Q_CC_DEC) && defined(__alpha) && (__DECCXX_VER-0 >= 50190001)
#pragma message disable narrowptr
#endif

/*!
  Reads a dictionary from the stream \a 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 *)k, d, op_insert );
		}
		break;
	}
    }
    return s;
}

/*!
  Writes the dictionary to the stream \a 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
  \reentrant
  \ingroup collection
  \brief The QGDictIterator class is an internal class for implementing QDictIterator and QIntDictIterator.

  \internal

  QGDictIterator is a strictly internal class that does the heavy work for
  QDictIterator and QIntDictIterator.
*/

/*!
  Constructs an iterator that operates on the dictionary \a 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
	Q_CHECK_PTR( dict->iterators );
    }
    dict->iterators->append( this );		// attach iterator to dict
}

/*!
  Constructs a copy of the iterator \a 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
}

/*!
  Assigns a copy of the iterator \a 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;
}

/*!
  Destroys the iterator.
*/

QGDictIterator::~QGDictIterator()
{
    if ( dict )					// detach iterator from dict
	dict->iterators->removeRef( this );
}


/*!
  Sets the iterator to point to the first item in the dictionary.
*/

QPtrCollection::Item QGDictIterator::toFirst()
{
    if ( !dict ) {
#if defined(QT_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();
}


/*!
  Moves to the next item (postfix).
*/

QPtrCollection::Item QGDictIterator::operator()()
{
    if ( !dict ) {
#if defined(QT_CHECK_NULL)
	qWarning( "QGDictIterator::operator(): Dictionary has been deleted" );
#endif
	return 0;
    }
    if ( !curNode )
	return 0;
    QPtrCollection::Item d = curNode->getData();
    this->operator++();
    return d;
}

/*!
  Moves to the next item (prefix).
*/

QPtrCollection::Item QGDictIterator::operator++()
{
    if ( !dict ) {
#if defined(QT_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();
}

/*!
  Moves \a jumps positions forward.
*/

QPtrCollection::Item QGDictIterator::operator+=( uint jumps )
{
    while ( curNode && jumps-- )
	operator++();
    return curNode ? curNode->getData() : 0;
}