/****************************************************************************

** 

**

** 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.

  
 read() reads a collection/dictionary item from a QDataStream.

  
 write() writes a collection/dictionary item to a QDataStream.

  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

	    h = (h<<4) + p[i].cell();

	    if ( (g = h & 0xf0000000) )

		h ^= g >> 24;

	    h &= ~g;

	}

    } else {					// case insensitive

	for ( i=0; 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

	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();