/*************************************************************************
 *
 *  $RCSfile: hashtab.hxx,v $
 *
 *  $Revision: 1.1.1.1 $
 *
 *  last change: $Author: hr $ $Date: 2000/09/18 16:59:01 $
 *
 *  The Contents of this file are made available subject to the terms of
 *  either of the following licenses
 *
 *         - GNU Lesser General Public License Version 2.1
 *         - Sun Industry Standards Source License Version 1.1
 *
 *  Sun Microsystems Inc., October, 2000
 *
 *  GNU Lesser General Public License Version 2.1
 *  =============================================
 *  Copyright 2000 by Sun Microsystems, Inc.
 *  901 San Antonio Road, Palo Alto, CA 94303, USA
 *
 *  This library is free software; you can redistribute it and/or
 *  modify it under the terms of the GNU Lesser General Public
 *  License version 2.1, as published by the Free Software Foundation.
 *
 *  This library is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 *  Lesser General Public License for more details.
 *
 *  You should have received a copy of the GNU Lesser General Public
 *  License along with this library; if not, write to the Free Software
 *  Foundation, Inc., 59 Temple Place, Suite 330, Boston,
 *  MA  02111-1307  USA
 *
 *
 *  Sun Industry Standards Source License Version 1.1
 *  =================================================
 *  The contents of this file are subject to the Sun Industry Standards
 *  Source License Version 1.1 (the "License"); You may not use this file
 *  except in compliance with the License. You may obtain a copy of the
 *  License at http://www.openoffice.org/license.html.
 *
 *  Software provided under this License is provided on an "AS IS" basis,
 *  WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESSED OR IMPLIED, INCLUDING,
 *  WITHOUT LIMITATION, WARRANTIES THAT THE SOFTWARE IS FREE OF DEFECTS,
 *  MERCHANTABLE, FIT FOR A PARTICULAR PURPOSE, OR NON-INFRINGING.
 *  See the License for the specific provisions governing your rights and
 *  obligations concerning the Software.
 *
 *  The Initial Developer of the Original Code is: Sun Microsystems, Inc.
 *
 *  Copyright: 2000 by Sun Microsystems, Inc.
 *
 *  All Rights Reserved.
 *
 *  Contributor(s): _______________________________________
 *
 *
 ************************************************************************/

#ifndef _SVTOOLS_HASHTAB_HXX
#define _SVTOOLS_HASHTAB_HXX
/*
	$Id: hashtab.hxx,v 1.1.1.1 2000/09/18 16:59:01 hr Exp $

	@doc HashTab

	@module hashtab.hxx | Header required by hashtab.cxx.

 */

/*
	@type HASH_NO_STRING_CLASS |
	#define HASH_NO_STRING_CLASS if you don't have an appropriate class String.

	The String class must have defined:

enum StringCompare { COMPARE_EQUAL, COMPARE_LESS, COMPARE_GREATER };

						String( const String& rStr );

	const char*			GetBuffer() const;
	or (for unicode)
	const sal_Unicode*	GetBuffer() const;

	USHORT				Len() const;
	or (for unicode)
	sal_uInt32			Len() const;

	StringCompare	CompareTo( const String& rStr ) const;

 */

//#define HASH_NO_STRING_CLASS

//#define HASH_DEBUG	// guess what? ;-)

#include <string.h>			// size_t

#ifndef HASH_NO_STRING_CLASS

#ifndef _LINK_HXX //autogen
#include <tools/link.hxx>
#endif
#endif

// @type HASHNAMEPTR | Type of symbol name pointer: <t void*>
typedef void* HASHNAMEPTR;

// @type HASHSYMPTR | Type of symbol bucket data pointer: <t void*>
typedef void* HASHSYMPTR;

// @type HASHTYPE | Type of hash value: <t size_t>
typedef size_t HASHTYPE;
// if you change this for any reason be sure it is the type that new expects!

// @type HASHSYMCOUNTTYPE | Type of element count: <t ULONG>
typedef ULONG HASHSYMCOUNTTYPE;
/* @comm
	If you have lots of symbols (a lot of lots on a DOS PC are more than
	64K ...) and are not short of memory (you know the fact: 640KB should be
	enough..) and <t unsigned long> differs from <t HASHTYPE> you'll have to
	replace the <f qsort> function in <mf HashTabBase::PrintTab> which relies
	on <t size_t>. In fact the PrintTab with sort might not work at all
	because it could run out of memory..

	You won't get away with less than 10 bytes per symbol, so the max under
	DOS without using XMS is really 64K symbols.

 */

// @const Max number of expected chain lengths: <t 128>  <nl>
// used by <mf HashTabBase::GetStats> and the <t HashStats> structure.
const size_t nHashChainMaxLen = 128;

// @struct HASHBUCKET | The HashElement header, followed by symbol bucket data
typedef struct HashElement
{
private:
	friend class HashTabBase;
#ifdef HASH_DEBUG
	friend int HashNameCmp( const void*, const void* );		// for qsort in PrintTab
#endif
	HashElement*	pNext;		// @field Pointer to next element
	HashElement**	ppPrev;		// @field Pointer to <e .pNext> of previous element
	HASHNAMEPTR		pName;		// @field Pointer to copied symbol name
	USHORT			nAccess;	// @field Counter of times accessed
} HASHBUCKET;
/* 	@comm The memory for symbol bucket data follows immediately behind this
	header. For faster allocating and less overhead it is allocated together
	with the memory of the hash bucket. All fields are private, class
	<c HashTabBase> is friend.

*/

// @struct HashStats | Structure for holding calculations from
// <mf HashTabBase::GetStats>
// @xref <t HASHTYPE> <t HASHSYMCOUNTTYPE> <t nHashChainMaxLen>
struct HashStats
{
	HASHTYPE			nLengths[nHashChainMaxLen];	// @field Chain lengths
	double				nMeanLen;		// @field Running mean of all chains
	double				nVariance;		// @field Variance of all chains
	double				nMeanLenU;		// @field Running mean of used chains
	double				nVarianceU;		// @field Variance of used chains
	HASHSYMCOUNTTYPE	nNumSyms;		// @field Elements in hash table
	HASHSYMCOUNTTYPE	nMinLen;		// @field Minimum length of chains
	HASHSYMCOUNTTYPE	nMaxLen;		// @field Maximum length of chains
	HASHTYPE			nLonger;		// @field Chains longer than <t nHashChainMaxLen>
	HASHTYPE			nSize;			// @field Hash table size
	HASHTYPE			nChainsU;		// @field Count of used chains
};

// @class Abstract hash table base class
// @xref <t HASHNAMEPTR> <t HASHSYMPTR> <t HASHBUCKET> <t HASHTYPE>
// <t HASHSYMCOUNTTYPE>
class HashTabBase
{
	// @access Public members
public:
							// @cmember Get a prime number near or below <p nVal>
	static HASHTYPE		GetNearPrime( HASHTYPE nVal );

							// @cmember Ctor
						HashTabBase( HASHTYPE nMaxSlots = 127,
							const Link& rDelLink = Link() );

							// @cmember Dtor, pure virtual
	virtual				~HashTabBase() = 0;

							// @cmember Ask if Ctor was successfull
	inline HASHTYPE		Is() const;

							// @cmember Compute Hash value for symbol name
							// <p pName>, pure virtual
	virtual	HASHTYPE	Hash( const HASHNAMEPTR pName ) const = 0;

							// @cmember Compare two symbol names, pure virtual
	virtual int			NameCmp( const HASHNAMEPTR pName1,
							const HASHNAMEPTR pName2 ) const = 0;

							// @cmember Duplicate function for symbol name,
							// pure virtual
	virtual	HASHNAMEPTR	NameDup( const HASHNAMEPTR pName ) const = 0;

							// @cmember Delete function for symbol name,
							// pure virtual
	virtual	void		NameDel( HASHNAMEPTR pName ) = 0;

							// @cmember Add a symbol to the hash table
	HASHSYMPTR			AddSym( const HASHNAMEPTR pName, size_t nDataSize,
								BOOL bUseLastFindSymHash = FALSE );

							// @cmember Add a symbol to the hash table, store
							// pointer <p pSymbol> as symbol bucket data
	HASHSYMPTR			AddPtrSym( const HASHNAMEPTR pName, void* pSymbol,
								BOOL bUseLastFindSymHash = FALSE );

							// @cmember Find a symbol, return pointer to
							// symbol bucket data
	HASHSYMPTR			FindSym( const HASHNAMEPTR pName );

							// @cmember Find a symbol, return pointer stored
							// in symbol bucket data by dereferencing the
							// HASHSYMPTR returned by <mf .FindSym>
	inline void*		FindPtrSym( const HASHNAMEPTR pName );

							// @cmember Delete a symbol and it's data
	void				DelSym( HASHSYMPTR pSymbolData );

							// @cmember Set the link to a function
							// which gets called with the symbol bucket data
							// pointer as the argument whenever a symbol
							// is to be deleted
	inline void			SetDataDelLink( const Link& rLink );

							// @cmember Retrieve the first element of
							// the hash table.
	HASHSYMPTR			First();

							// @cmember Retrieve the next element of
							// the hash table.
	HASHSYMPTR			Next();

							// @cmember Get next symbol in current chain
	HASHSYMPTR			NextInChain();

							// @cmember Extract the name field for a symbol
	const HASHNAMEPTR	GetName( const HASHSYMPTR pSymbolData ) const;

							// @cmember Get the number of times a symbol is accessed
	USHORT				GetTimesAccessed( const HASHSYMPTR pSymbolData ) const;

							// @cmember Get hash table statistics
	void				GetStats( HashStats* pStat ) const;

							// @cmember Derefers a HASHSYMPTR which points to
							// a pointer stored as symbol bucket data
	static inline void*	Derefer( HASHSYMPTR pSymbolData );

							// @cmember
							// Set <md .bToTop>. If TRUE, elements of a chain
							// will be sorted by access times in <mf .FindSym>
	inline void			SetToTop( BOOL bFlg );

							// @cmember Get the table size <md .nSize>.
	inline HASHTYPE		GetSize();

							// @cmember Get number of symbols in table
	inline HASHSYMCOUNTTYPE Count();

#ifdef HASH_DEBUG
							// @cmember Print the hash table.
							// Only defined ifdef HASH_DEBUG
	int					PrintTab( void (*Print) ( const HASHNAMEPTR pName,
									const HASHSYMPTR pSymbolData ),
									BOOL bSort = FALSE ) const;

							// @cmember Debug print table function
							// Not for StringHashTab, just for simple CharHashTab!
							// Only defined ifdef HASH_DEBUG
	void				dPrintTab();
#endif

	// @access Protected members
protected:
							// @cmember Function called by the Dtor of the
							// derived class, which virtually calls
							// <mf .NameDel> of the derived class.
	void				DtorCall();

	// @access Private members
private:
							// @cmember Linked function for symbol bucket
							// data deletion
	Link				aDataDelLink;
							// @cmember Pointer to hash table
	HASHBUCKET**		ppTable;
							// @cmember Pointer to latest accessed element
							// for use with <mf .First> and <mf .Next>
	HASHBUCKET*			pActBucket;
							// @cmember Number of elements currently in table
	HASHSYMCOUNTTYPE	nNumSyms;
							// @cmember Max number of chains in table
	HASHTYPE			nSize;
							// @cmember Last hash value calculated by
							// <mf .FindSym>
	HASHTYPE			nLastFindSymHash;
							// @cmember Position of latest accessed chain
							// for use with <mf .First> and <mf .Next>
	HASHTYPE			nActPos;
							// @cmember If <md .pActBucket> is already positioned
							// on next element after a call to <mf .DelSym>
	BOOL				bActOnNext;
							// @cmember If <mf .DtorCall> has already been called
	BOOL				bDtorCalled;
							// @cmember If <mf .DtorCall> is called by ourself
	BOOL				bOwnDtorCall;
							// @cmember If elements will be moved to top of list
	BOOL				bToTop;

							// @cmember Prevent accidental copy'ing
						HashTabBase( const HashTabBase& rTab );
							// @cmember Prevent accidental assignment
	HashTabBase&		operator=( const HashTabBase& rTab );

							// @cmember Increments bucket pointer with alignment
	inline HASHSYMPTR	IncBucketPtr( HASHBUCKET* ) const;
							// @cmember Decrements bucket data pointer with alignment
	inline HASHBUCKET*	DecBucketPtr( HASHSYMPTR ) const;

							// @cmember Set <md .pActBucket> to <p pB> and
							// <md .bActOnNext> to FALSE
	inline void			SetActBucket( HASHBUCKET* pB );

};

/*	@comm
	HASHSYMPTR <p pSymbolData> is a pointer returned by a previous
	<mf .AddSym> or <mf .FindSym> or <mf .First> or <mf .Next> call.

	@todo
	There is no copy constructor implemented, and there is no assignment
	operator implemented either, sorry, just lazy.. both are declared as
	private members to prevent accidental usage.

 */

/*	@mfunc const member function.
	Call this to be sure that the hash table has been successfully
	constructed, otherwise you would refer to NULL-pointers.
	@rdesc <t HASHTYPE> value
	@flag 0 | if there was any error
	@flag else | number of slots in the hash table, the same value as the
	parameter passed to the Ctor <mf .HashTabBase>(<p nMaxSlots>)

 */
inline HASHTYPE HashTabBase::Is() const
{
	return ppTable ? nSize : 0;
}

/*	@mfunc
	Find a symbol, return pointer stored in symbol bucket data by
	dereferencing the HASHSYMPTR returned by <mf .FindSym>

*/
inline void* HashTabBase::FindPtrSym(
		const HASHNAMEPTR pName		// @parm symbol name
	)
{
	return Derefer( FindSym( pName ) );
}

/*	@mfunc
	Set <md .aDataDelLink> to a function which gets called with a symbol
	bucket data pointer <p pPtr> as the second argument whenever a symbol is
	to be deleted.

	typedef long (*PSTUB)( void*, void* )

	A non-member function may be linked with
	SetDataDelLink( Link( 0, (PSTUB)<p pFunction> ) )

	A static member function of a class may be linked with
	SetDataDelLink( Link( <p pInstance>, <p pFunction> ) )
	for example
	SetDataDelLink( Link( (ClassName*)this, (PSTUB)&ClassName::Method ) )

	The Link is called by <mf .DelSym> and <mf .DtorCall> with
	aDataDelLink.Call( <p pPtr> ) which calls
	(<p pFunction>)( <p pInstance>, <p pPtr> )

	The static long ClassName::Method may call a non-static member function
	as ((ClassName*)pInstance)->MFunc( pPtr )

	@xref <mf StringHashTab::SetStringDataDelLink>
	<mf StringHashTab::StringDel>

 */
inline void HashTabBase::SetDataDelLink(
		const Link& rLink		// @parm Link
	)
{
	aDataDelLink = rLink;
}

// @mfunc static inline meber function. Derefers a HASHSYMPTR which points to
// a pointer stored as symbol bucket data
inline void* HashTabBase::Derefer(
		HASHSYMPTR pSymbolData		// @parm pointer to symbol bucket data
	)
{
	return (pSymbolData ? *(HASHSYMPTR*)pSymbolData : 0);
}

// @mfunc
// Set <md .bToTop>. If TRUE, elements of a chain will be sorted by access
// times in <mf .FindSym>. The default on construction is TRUE.
inline void HashTabBase::SetToTop(
		BOOL bFlg		// @parm TRUE or FALSE
	)
{
	bToTop = bFlg;
}

// @mfunc Get the table size <md .nSize>.
inline HASHTYPE HashTabBase::GetSize()
{
	return nSize;
}

// @mfunc Get number of symbols in table
inline HASHSYMCOUNTTYPE HashTabBase::Count()
{
	return nNumSyms;
}

/*	@type HASH_IMPL_DTOR( ClassName ) |
	Macro to implement a simple Dtor of a derived class <p ClassName> which
	calls <mf HashTabBase::DtorCall>. It must be defined for the derived
	class so that <mf .NameDel> gets called by HashTabBase::DtorCall

 */
#define HASH_IMPL_DTOR( ClassName ) \
ClassName::~ClassName() \
{ \
	HashTabBase::DtorCall(); \
}
// @xref <mf CharHashTab::~CharHashTab> <mf StringHashTab::~StringHashTab>

// @class Hash table class of type <t char*> name
// @base public | HashTabBase
// @xref <t HASH_IMPL_DTOR( ClassName )>
class CharHashTab : public HashTabBase
{
	// @access Public members
public:
							// @cmember Ctor
						CharHashTab( HASHTYPE nMaxSlots = 127,
							const Link& rDelLink = Link() )
							: HashTabBase( nMaxSlots, rDelLink ) {}

							// @cmember Dtor
	virtual				~CharHashTab();

							// @cmember Compute Hash value for symbol <p pName>
	virtual	HASHTYPE	Hash( const HASHNAMEPTR pName ) const;

							// @cmember Compare function for two symbol names
	virtual int			NameCmp( const HASHNAMEPTR pName1, const HASHNAMEPTR pName2 ) const;

							// @cmember Duplicate function for symbol name
	virtual	HASHNAMEPTR	NameDup( const HASHNAMEPTR pName ) const;

							// @cmember Delete function for symbol name
	virtual	void		NameDel( HASHNAMEPTR pName );
};

#ifndef HASH_NO_STRING_CLASS

// @class Hash table class of type class <c String> name
// @base public | HashTabBase
// @xref <t HASH_IMPL_DTOR( ClassName )> <t HASH_NO_STRING_CLASS>
class StringHashTab : public HashTabBase
{
	// @access Public members
public:
							// @cmember Ctor
						StringHashTab( HASHTYPE nMaxSlots = 127,
							const Link& rDelLink = Link() )
							: HashTabBase( nMaxSlots, rDelLink ) {}

							// @cmember Dtor
	virtual				~StringHashTab();

							// @cmember Compute Hash value for symbol <p pName>
	virtual	HASHTYPE	Hash( const HASHNAMEPTR pName ) const;

							// @cmember Compare function for two symbol names
	virtual int			NameCmp( const HASHNAMEPTR pName1, const HASHNAMEPTR pName2 ) const;

							// @cmember Duplicate function for symbol name
	virtual	HASHNAMEPTR	NameDup( const HASHNAMEPTR pName ) const;

							// @cmember Delete function for symbol name
	virtual	void		NameDel( HASHNAMEPTR pName );

							// @cmember
							// Set <md HashTabBase::aDataDelLink> to
							// <mf .StringDel>
	void				SetStringDataDelLink();

							// @cmember static long | StringDel |
							// ( StringHashTab*, HASHSYMPTR ) |
							// Delete String pointed to by symbol bucket data
	DECL_STATIC_LINK( StringHashTab, StringDel, HASHSYMPTR );

							// @cmember
							// Unlink any link stored in <md .aDataDelLink>
	void				ClearDataDelLink();

};

#endif	// #ifndef HASH_NO_STRING_CLASS

/*
	just for AutoDuck references

	@mdata Link	| HashTabBase | aDataDelLink |
	Linked function for symbol bucket data deletion.
	@xref <mf .SetDataDelLink> <mf StringHashTab::SetStringDataDelLink>

	@mdata HASHBUCKET** | HashTabBase | ppTable |
	A pointer to the hash table itself which is an array of <md .nSize>
	<t HASHBUCKET> pointers.

	@mdata HASHBUCKET* | HashTabBase | pActBucket |
	Pointer to the current element in the hash table.

	@mdata HASHSYMCOUNTTYPE | HashTabBase | nNumSyms |
	Number of symbols currently in the hash table.

	@mdata HASHTYPE | HashTabBase | nSize |
	Max number of chains (slots) in the hash table itself. This is NOT the
	maximum number of symbols the table can hold. The maximum number of
	symbols is only limited by heap space.

	@mdata HASHTYPE | HashTabBase | nLastFindSymHash |
	Hash value of the last <mf .FindSym> call. May be used on the next call
	to <mf .AddSym>.

	@mdata HASHTYPE | HashTabBase | nActPos |
	Hash table slot where the chain bearing the current element resides.

	@mdata BOOL | HashTabBase | bActOnNext |
	Flag if <md .pActBucket> is already positioned on the next element
	if the current element was deleted by <mf .DelSym>.

	@mdata BOOL | HashTabBase | bDtorCalled |
	If <mf .DtorCall> has already been called.

	@mdata BOOL | HashTabBase | bOwnDtorCall |
	If <mf .DtorCall> is called by ourself.

	@mdata BOOL | HashTabBase | bToTop |
	If set, elements are moving towards the top of a chain if their access
	count exceeds the access count of a previous element.

 */

#endif
