libdc-dev 0.3.24~svn3121-2 / usr / include / dclib-0.3 / dclib / core / cstringlist.h

/***************************************************************************
                           cstringlist.h  -  description
                             -------------------
    begin                : Sat Jun 1 2002
    copyright            : (C) 2002-2003 by Mathias Küster
    email                : mathen@users.berlios.de
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/

#ifndef CSTRINGLIST_H
#define CSTRINGLIST_H

/**
  *@author Mathias Küster
  *
  * Turned into a template class by Edward Sheldrake,
  * which makes the downloadmanager code a hell of a lot clearer.
  *
  * However this class and CList should still be removed entirely and replaced
  * with more appropriate STL classes (map, set, unordered_map).
  *
  * CStringList is a mapping class, not a list of strings. It is implemented
  * by containing lists per first key character. To handle more characters
  * of the key, the maxdepth parameter can be used, then it will contain
  * as many levels of CStringLists as necessary, each level handling
  * one character.
  *
  * CStringList's performance varies depending on how well
  * the items distribute, there is no real hash function to make
  * sure the items distribute evenly.
  *
  * The remove without deleting the item function never used to work
  * for CStringLists created with maxdepth > 0, the item was always
  * deleted. dclib does not require this to work, even if it was fixed.
  */

#include <dclib/dcos.h>
#include <dclib/core/cstring.h>
#include <dclib/core/clist.h>

template<class type> class CStringListObject {
public:
	/** */
	CStringListObject() {
		m_pObject = 0;
	};
	/** */
	~CStringListObject() {};

	/** */
	CString m_s;
	/** */
	type * m_pObject;
};

template<class type> class CStringList {
public: 
	/** */
	CStringList( int maxdepth = 0, int depth = 0 );
	/** */
	~CStringList();

	/** */
	int Add( const CString & s, type * object = 0 );
	/** */
	int Get( const CString & s, type ** object );
	/** */
	int Del( const CString & s, bool bdelobj = true );
	/** */
	int Remove( const CString & s ) { return Del(s,false); };
	/** */
	void Clear();
	/** */
	long Count() const;
	/** */
	int Next( type ** object );
	/** */
	int Next( CString & s, type ** object );
private:
	/** */
	int m_nDepth;
	/** */
	int m_nMaxDepth;
	/** */
	long m_nSize;
	/** */
	long m_nCachePos;
	/** */
	CStringListObject<type> * m_nCacheObj;
	/** */
	CStringList<type> ** m_pStringList;
	/** */
	CList<CStringListObject<type> > ** m_pList;
};

/** */
template<class type> inline long CStringList<type>::Count() const
{ return m_nSize; }

#define HASH_TABLE_SIZE 0x100

#include <stdio.h>
#include <string.h>

template<class type> CStringList<type>::CStringList( int maxdepth, int depth )
{
	m_nDepth    = depth;
	m_nMaxDepth = maxdepth;
	m_nSize     = 0;
	m_nCachePos = 0;
	m_nCacheObj = 0;

	m_pList       = 0;
	m_pStringList = 0;

	if ( m_nDepth == m_nMaxDepth )
	{
		m_pList = new CList<CStringListObject<type> >*[HASH_TABLE_SIZE];
		memset(m_pList, 0, HASH_TABLE_SIZE*sizeof(CList<CStringListObject<type> >*));
	}
	else
	{
		m_pStringList = new CStringList<type>*[HASH_TABLE_SIZE];
		memset(m_pStringList, 0, HASH_TABLE_SIZE*sizeof(CStringList<type>*));
	}
}

template<class type> CStringList<type>::~CStringList()
{
	Clear();

	if ( m_nDepth == m_nMaxDepth )
		delete [] m_pList;
	else
		delete [] m_pStringList;
}

/** */
template<class type> int CStringList<type>::Add( const CString & s, type * object )
{
	int i = s.GetHash(m_nDepth);

	if ( m_nDepth == m_nMaxDepth )
	{
		CStringListObject<type> * o = new CStringListObject<type>();

		o->m_s = s;
		o->m_pObject = object;

		if ( m_pList[i] == 0 )
			m_pList[i] = new CList<CStringListObject<type> >();

		m_pList[i]->Add(o);
	}
	else
	{
		if ( m_pStringList[i] == 0 )
			m_pStringList[i] = new CStringList<type>(m_nMaxDepth,m_nDepth+1);
		m_pStringList[i]->Add(s,object);
	}

	m_nSize++;

	m_nCachePos = 0;
	m_nCacheObj = 0;

	return 0;
}

/** */
template<class type> int CStringList<type>::Del( const CString & s, bool bdelobj )
{
	CStringListObject<type> * o = 0;
	int i = s.GetHash(m_nDepth);

	if ( m_nDepth == m_nMaxDepth )
	{
		if ( m_pList[i] == 0 )
			return -1;

		while( (o=m_pList[i]->Next(o)) != 0 )
		{
			if ( s == o->m_s )
				break;
		}

		if (!o)
			return -1;

		m_pList[i]->Remove(o);

		if ( bdelobj )
			delete o->m_pObject;

		delete o;

		if (m_pList[i]->Count() == 0 )
		{
			delete m_pList[i];
			m_pList[i]=0;
		}
	}
	else
	{
		if ( m_pStringList[i] == 0 )
			return -1;
		m_pStringList[i]->Del(s,bdelobj);
	}

	m_nSize--;

	m_nCachePos = 0;
	m_nCacheObj = 0;

	return 0;
}

/** */
template<class type> int CStringList<type>::Get( const CString & s, type ** object )
{
	CStringListObject<type> * o = 0;
	int i = s.GetHash(m_nDepth);

	if ( m_nDepth == m_nMaxDepth )
	{
		if ( !m_pList[i] )
			return -1;

		while( (o=m_pList[i]->Next(o)) != 0 )
		{
			if ( s == o->m_s )
				break;
		}

		if (!o)
			return -1;

		*object = o->m_pObject;
	}
	else
	{
		if ( !m_pStringList[i] )
			return -1;

		return m_pStringList[i]->Get(s,object);
	}

	return 0;
}

/** */
template<class type> void CStringList<type>::Clear()
{
	CStringListObject<type> * o = 0;
	int i;

	for(i=0;i<HASH_TABLE_SIZE;i++)
	{
		if ( m_nDepth == m_nMaxDepth )
		{
			if(m_pList[i])
			{
				while( (o=m_pList[i]->Next(0)) != 0 )
				{

					delete o->m_pObject;
					o->m_pObject = 0;

					m_pList[i]->Del(o);
				}

				delete m_pList[i];
			}
			m_pList[i]=0;
		}
		else
		{
			if(m_pStringList[i])
				delete m_pStringList[i];
			m_pStringList[i]=0;
		}
	}

	m_nSize     = 0;
	m_nCachePos = 0;
	m_nCacheObj = 0;
}

/** */
template<class type> int CStringList<type>::Next( type ** object )
{
	CString s;

	return Next(s,object);
}

/** */
template<class type> int CStringList<type>::Next( CString & s, type ** object )
{
	int i;
	long l;
	CStringListObject<type> * obj=0;

	if ( *object == 0 )
	{
		m_nCachePos = 0;
		m_nCacheObj = 0;
	}

	for(i=0,l=0;(i<HASH_TABLE_SIZE)&&(m_nSize>0);i++)
	{
		if ( m_nDepth == m_nMaxDepth )
		{
			if(!m_pList[i])
				continue;

			// fix cache after del
			if ( (*object != 0) && (m_nCacheObj == 0) )
			{
				obj = 0;
				while ( (obj=m_pList[i]->Next(obj)) != 0 )
				{
					m_nCachePos++;
					if ( obj->m_pObject == *object )
					{
						m_nCacheObj = obj;
						break;
					}
				}
				obj = 0;
			}
			else if ( (l<=m_nCachePos) && ((l+m_pList[i]->Count())>m_nCachePos) )
			{
				if(l==m_nCachePos)
					m_nCacheObj=0;
				obj = m_pList[i]->Next(m_nCacheObj);
				if ( obj )
					s = obj->m_s;
				else
					printf("WARNING: CStringList::Next nullpointer !\n");
				m_nCachePos++;
				m_nCacheObj = obj;
				break;
			}

			l+=m_pList[i]->Count();
		}
		else
		{
			if(!m_pStringList[i])
				continue;

			if ( (l<=m_nCachePos) && ((l+m_pStringList[i]->Count())>m_nCachePos) )
			{
				if(l==m_nCachePos)
					*object=0;
				m_nCachePos++;
				return m_pStringList[i]->Next(object);
			}

			l+=m_pStringList[i]->Count();
		}
	}
	
	if ( obj )
		*object = obj->m_pObject;
	else
		*object = 0;

	return (obj!=0);
}

#endif