path: root/utils/HashTable.cc

/*
 *	CENA C++ Utilities
 *
 *	by Stephane Chatty
 *
 *	Copyright 1991-1996
 *	Laboratoire de Recherche en Informatique (LRI)
 *	Centre d'Etudes de la Navigation Aerienne (CENA)
 *
 *	plain and generic hash tables and dictionnaries
 *	(Original C version by Michel Beaudouin-Lafon)
 *
 *	$Id$
 *	$CurLog$
 */

#include <string.h>
#include "String.h"
#include "HashTable.h"
#include "Allocator.h"
#ifdef TUNE
#include <stdio.h>
#endif

/*?class IvlHashTable
The class \typ{IvlHashTable} implements association tables based on a hashing algorithm.
Hash tables are useful to store information that needs to be retrieved
quickly, and which bears no efficient ordering. For instance, this is the
case for strings:
in a compiler, one may wish to maintain a hash table with identifiers
as hash keys and symbol table entries as information.

A hash table is made of a set of hash entries (of class \typ{IvlHashCell}),
which can be modified during
the life of the table. An entry has two main fields: a hash key, and a user defined
information attached to that key. We will not give details about the structure of
a hash table, as they can be found in any book about algorithms. Figure~\ref{FIGURES/hash} is only
here as a reminder.
\fig{FIGURES/hash}{Internals of a hash table}
The current implementation uses lists to store the synonyms so that entries can
be deleted efficiently.

The class \typ{IvlHashTable} makes no assumption about the type of the keys, which it handles as 
\typ{const void *}.

The user can define several functions used when managing a hash table: the hash function, which 
is determinant for the performances of the hash table, and the functions to copy, compare, and
destroy keys. Basic functions are provided by default.
The following definitions are used by member functions of the class \typ{IvlHashTable},
and by them only:
\index{HASH_F}\index{HCP_F}\index{HCMP_F}\index{HENUM_F}\index{HDEL_F}
\begin{ccode}
        typedef unsigned int     (*HASH_F) (HashItem*, int);
        typedef pointer (*HCP_F) (HashItem*);
        typedef int     (*HCMP_F) (HashItem*, HashItem*);
        typedef int     (*HENUM_F) (HashCell*, HashItem*);
        typedef void    (*HDEL_F) (HashCell*);
\end{ccode}

?*/

IvlAllocator* IvlHashCell::HashCellMem = 0;

/*?hidden?*/ 
void
IvlHashCell :: ClassInit ()
{
	if (!HashCellMem)
		HashCellMem = new IvlAllocator (sizeof (IvlHashCell));
} 

/*?nodoc?*/
void*
IvlHashCell :: operator new (size_t)
{
	return HashCellMem->Alloc ();
}

/*?nodoc?*/
void
IvlHashCell :: operator delete (void* that)
{
	HashCellMem->Free (that);
}

#if 0
unsigned int
IvlHashTable :: HashPtr (const void* p, int max)
{
	/* stolen from Tcl */
	/* this would be easier if max was a power of 2 */
	return ((long)(p) * 1103515245) >> (30 - ffs (max));
}
#endif

/*?
Constructor for \typ{IvlHashTable}s. Build a hash table based on an array of
size \var{size}.
You can optionally provide your own functions for copying, destroying
and comparing keys, and the hashing function. If no hashing function is
provided, the identity function is used.
?*/
IvlHashTable :: IvlHashTable (unsigned int size, HASH_F hash_fun, HCP_F cp_fun, HDEL_F del_fun, HCMP_F cmp_fun)
: Size (size),
  Hash (hash_fun),
  Copy (cp_fun),
  Delete (del_fun),
  Compare (cmp_fun)
{
	if (Size <= 0)
		Size = 1;
	Table = new IvlHashCell* [Size];
	memset (Table, 0, Size*sizeof (IvlHashCell*));

	/* I know that HashCells can only be created from HashTables */
	if (!IvlHashCell::HashCellMem)
		IvlHashCell::ClassInit ();
}

/*?
Copy constructor for hash tables. The table and the cells are copied. The keys are
copied only if \var{ht} had a copy function. The new hash table will contain the
same informations as \var{ht}, but the synonyms will not necessarily be in the same order.
?*/
IvlHashTable :: IvlHashTable (const IvlHashTable& ht)
: Size (ht.Size),
  Hash (ht.Hash),
  Copy (ht.Copy),
  Delete (ht.Delete),
  Compare (ht.Compare)
{
	Table = new IvlHashCell* [Size];
	register IvlHashCell** p = Table;
	register IvlHashCell** q = ht.Table;
	while (p < Table + Size) {
		*p = 0;
		register IvlHashCell* r = *q;
		while (r) {
			(*p) = new IvlHashCell (Copy ? (*Copy) (r->GetKey ()) : r->GetKey (), *p);
			(*p)->SetInfo (r->Info);
			r = r->Next;
		}
		++p;
		++q;
	}
}

/*?
Destructor for hash tables. All keys are destroyed if a destruction function was provided.
?*/
IvlHashTable :: ~IvlHashTable ()
{
	Clear ();

#ifdef CPLUS_BUG4
	delete [Size] Table;
#else
	delete [] Table;
#endif
}

/*?
Remove all data from the hash table.  All keys are destroyed if a destruction function was provided.
?*/
void
IvlHashTable :: Clear ()
{
	/* destroy keys */
	if (Delete) {
		IvlHashCellIter hi (*this);
		while (++hi)
			(*Delete) ((*hi)->Key);
	}

	/* destroy cells */
	int s = Size;
	IvlHashCell** entry = Table;

	/* for each slot of the array ... */	
	for ( ; s--; ++entry ) {
		if (! *entry)
			continue;
		
		/* ... destroy all cells linked from that slot ...*/
		for (IvlHashCell* h = *entry; h;) {
			IvlHashCell* del = h;
			h = h->Next;
			delete del;
		}

		/* ... and clear it */
		*entry = 0;
	}
}

/*?hidden?*/
IvlHashCell** 
IvlHashTable :: HashKey (const void* key) const
{
	register unsigned int h = (unsigned int) key;

	if (Hash)
		h = (*Hash) (key, Size);
 
	if (h >= Size)
		h %= Size;

	return (Table + h);
}

/*?hidden?*/
IvlHashCell*
IvlHashTable :: FindCell (IvlHashCell** entry, const void* key) const
{
	IvlHashCell* h;
	for (h = *entry; h; h = h -> Next)
		if (Compare ? (*Compare) (key, h->Key) : (key == h->Key))
			break;
	return h;
}

	
/*?hidden?*/
IvlHashCell*
IvlHashTable :: AddCell (IvlHashCell** entry, const void* key) const
{
	if (Copy)
		key = (* Copy) (key);
	
	IvlHashCell* h = new IvlHashCell (key, *entry);
	*entry = h;
	return h;
}

/*?class IvlHashCell
\typ{IvlHashCell}s hold the entries of an hash table.
A \typ{IvlHashCell} contains a key and a user defined information.
?*/

#ifdef DOC

/*?hidden?*/
IvlHashCellOf :: IvlHashCell (const void*, IvlHashCell*)
{
}

/*?nextdoc?*/
const void*
IvlHashCell :: GetKey () const
{
}

/*?
Retrieve the key, or the information from a \typ{IvlHashCell}.
?*/
IvlHashItem*
IvlHashCell :: GetInfo () const
{
}

/*?
Set the cell information to \var{p}.
?*/
void
IvlHashCell :: SetInfo (IvlHashItem* p)
{
}

#endif

/*?
Add the key \var{key} into the table. If 
\var{found} is not 0, it is a return parameter which contains true if the
key was already in the table, or false if it was new. In both cases, the 
function returns the address of the hash entry corresponding to the key.
\fun{Add} uses the hash function of the table.
If the key is new and a copy function was provided, the key is copied.
?*/
IvlHashCell*
IvlHashTable :: Add (const void* key, int* found)
{
	/* est-il dans la table ? */
	IvlHashCell** entry = HashKey (key);
	IvlHashCell* h = FindCell (entry, key);
	
	if (found)
		*found = (h != 0);

	if (h)
		return h;
	
	return AddCell (entry, key);
}

/*?
Retrieve the key \var{key} from the table. If it exists, return
the address of its hash entry, thus allowing to get its associated info. If the key
does not exist in the table, return 0.
?*/
IvlHashCell*
IvlHashTable :: Get (const void* key)
{
	IvlHashCell **entry = HashKey (key);
	return FindCell (entry, key);
}

#if 0
IvlHashItem*&
IvlHashTable :: operator [] (const void* key)
{
	IvlHashCell **entry = HashKey (key);
	IvlHashCell *h = FindCell (entry, key);
	
	if (!h)
		h = AddCell (entry, key);

	return h->Info;
}
#else
/*?
Get a reference to the data stored in the table for the key \var{key}. That
reference can be used for reading as for writing. If the key was not present
in the table, a new entry is created when writing, and a default (invalid) entry
is returned when reading.
?*/
IvlHashCellRef
IvlHashTable :: operator [] (const void* key) const
{
	return IvlHashCellRef (*this, key);
}
#endif

/*?
Remove the key \var{key} from the table. If it exists, return its
associated data. If the key does not exist, return 0. \var{found} may
be used to test whether the key was found.
?*/
IvlHashItem*
IvlHashTable :: Remove (const void* key, int* found)
{
	IvlHashCell **entry;
	register IvlHashCell *h, *hp = 0;
	IvlHashItem* info = 0;
	
	entry = HashKey (key);
	
	for (h = *entry; h; h = h->Next) {
		if (Compare ? (*Compare) (key, h->Key) : (key == h->Key)) {
			/* remove it from the list */
			if (hp)
				hp->Next = h->Next;
			else
				*entry = h->Next;
			
			/* free it, sparing its info */
			if (Delete)
				(*Delete) (h->Key);
			info = h->Info;
			delete h;
			break;
		}
		hp = h;
	}
	if (found)
		*found = (h != 0);
	return info;
}

/*?
Change the size of the table, which is re-hashed.
?*/
void
IvlHashTable :: Resize (int size)
{
	int s = Size;
	if (size <= 0)
		size = 1;
	Size = size;

	IvlHashCell** entry = Table;
	IvlHashCell** old_table = Table;
	Table = new IvlHashCell* [size];
	memset (Table, 0, size*sizeof (IvlHashCell*));

	/* rehash */
	for (; s--; ++entry) {
		
		/* scan the list */
		register IvlHashCell *cur, *next;
		for (cur = *entry; cur; cur = next) {
			next = cur->Next;

			register IvlHashCell** slot = HashKey (cur->Key);

			/* prepend the cell to the corresponding list */
			cur->Next = *slot;
			*slot = cur;
		}
	}
#ifdef CPLUS_BUG4
	delete [Size] old_table;
#else
	delete [] old_table;
#endif
}

#ifdef TUNE
/*?nextdoc?*/
void
IvlHashTable :: HashStats ()
{
	IvlHashCell * h;
	IvlHashCell **entry;
	int s, coll = 0, empty = 0;

	for (s = Size, entry = Table; s--; entry++) {
		if (h = *entry) {
			fprintf (stderr, "%s(%d)", h->Key, h->Info);
			while (h = h->Next) {
				fprintf (stderr, "\t%s(%d)", h->Key, h->Info);
				coll++;
			}
			fprintf (stderr, "\n");
		} else	{
			fprintf (stderr, "<EMPTY>\n");
			empty++;
		}
	}
	fprintf (stderr, "size: %d; %d empty; %d collisions\n", Size, empty, coll);
}

/*?
Print some statistics about this hash table on file descriptor \var{fd}
(default is stderr).
?*/
void
IvlHashTable :: CollStats ()
{
	IvlHashCell * h;
	IvlHashCell **entry;
	int s, lcoll, coll = 0, empty = 0;
	int min = 999999, max = 0, moy = 0, moy2 = 0;
	float fmoy, fvar;
	
	for (s = Size, entry = (IvlHashCell**) Table; s--; entry++) {
		lcoll = 0;
		if (h = *entry) {
			while (h = h->Next) {
				coll++, lcoll++;
			}
/*			sprintf (msg, "%d colls\n", lcoll);
			write (fd, msg, strlen (msg));
*/			moy += lcoll;
			moy2 += lcoll * lcoll;
			if (lcoll < min)
				min = lcoll;
			if (lcoll > max)
				max = lcoll;
		} else	{
/*			write (fd, "<EMPTY>\n", 8);
*/			empty++;
		}
	}
	fmoy = ((float) moy) / ((float) Size);
	fvar = fmoy * fmoy - (((float) moy2) / ((float) Size));
	fprintf (stderr, "size : %d; %d empty; %d collisions\n", Size, empty, coll);
	fprintf (stderr, "min : %d; max %d; moy %f; variance %f\n----\n\n", min, max, fmoy, fvar);
}

#endif	/* TUNE */

IvlHashItem*
IvlHashCellRef :: operator = (IvlHashItem* info)
{
	IvlHashCell **entry = Table.HashKey (Key);
	IvlHashCell *h = Table.FindCell (entry, Key);
	
	if (!h)
		h = Table.AddCell (entry, Key);

	h->SetInfo (info);

	return info;
}

IvlHashCellRef :: operator IvlHashItem* ()
{
	IvlHashCell **entry = Table.HashKey (Key);
	IvlHashCell *h = Table.FindCell (entry, Key);
	return h ? h->GetInfo () : 0;
}

/*?class IvlDictionnary
For the common case when character strings are used as keys, 
the class \typ{IvlDictionnary} was derived from the class \typ{IvlHashTable}. 
It is the class that should be used for dictionaries, symbol tables,~\ldots\,
For this special kind of hash tables, keys are compared as strings, and are copied with the 
function \fun{NewString} (see page~\pageref{newstring}). If users do not provide a hash function,
a default one is used.

All the functions of class \typ{IvlHashTable} are available in class \typ{IvlDictionnary}.
\typ{IvlHashCellIter}s and \typ{IvlHashIter}s can be used on \typ{IvlDictionnary}s as well.
?*/

/*?
This function computes an integer key from a string. It is used by dictionaries as
a hashing function, and is provided to users for a possible reuse.
?*/
unsigned int
IvlDictionnary :: HashString (const void* key, int)
{
	register int h = 0;
	register const char* p = (const char*) key;
	while (*p)
#if 0
		h ^= *p++;
#else
		h += (h << 3) + *p++;	/* this hash function was stolen from Tcl */
#endif
	return h;
}

/*?hidden?*/
int
IvlDictionnary :: CompareString (const void* a, const void* b)
{
	register const char *p, *q;
	/* on fait le strcmp a la main : ca va + vite */
	for (p = (const char *) a, q = (const char *) b; *p == *q++; p++)
		if (*p == '\0')
			return 1;
	return 0;
}

/*?hidden?*/
void*
IvlDictionnary :: CopyString (const void* k)
{
	return NewString ((const char*) k);
}

/*?hidden?*/
void
IvlDictionnary :: DeleteString (const void* k)
{
	FreeString ((char*) k);
}

/*?
Constructor for \typ{IvlDictionnary}s. Initialize a \typ{IvlDictionnary} with an array of size \var{size},
and \var{hash\_fun} as the hash function. If \var{hash\_fun} is not provided, the default 
function is used.
?*/
IvlDictionnary :: IvlDictionnary (int size, HASH_F f)
: IvlHashTable (size, (f ? f : HashString), (HCP_F) (CopyString), (HDEL_F) (DeleteString), (HCMP_F) (CompareString))
{
}

/*?nodoc?*/
IvlDictionnary :: ~IvlDictionnary ()
{
}

/*?nodoc?*/
void
IvlDictionnary :: KeyCopy (int flag)
{
	if (flag) {
		Copy = (HCP_F) (&CopyString);
		Delete = (HDEL_F) &DeleteString;
	} else {
		Copy = 0;
		Delete = 0;
	}
}

/*?class IvlHashCellIter
The class \typ{IvlHashCellIter} makes it possible to iterate through the entries of an hash table.
The order of iteration is not specified. These iterators yield pointers to cells, so that keys
and entries are both accessible. To see only the entries, refer to the class \typ{IvlHashIter}.
?*/

#ifdef DOC
/*?
Constructor for \typ{IvlHashCellIter}s. Initialize an iterator on the hash table \var{t}.
?*/
IvlHashCellIter :: IvlHashCellIter (const IvlHashTable& t)
{
}

/*?
Get the current cell  pointed by an iterator.
?*/
IvlHashCell*
IvlHashCellIter :: operator * () const
{
}
#endif

/*?
Take one step of iteration. This operator returns a pointer on the next 
hash entry of the table it is iterating on. When it is finished, it returns 0.
?*/
IvlHashCellIter&
IvlHashCellIter :: operator ++ ()
{
	register IvlHashCell* h = 0;
	register int size = TheTable.GetSize ();
	
	
	if (!CurCell || !(h = CurCell->Next))
		while ((++CurIndex < size) && !(h = (TheTable.Table [CurIndex])))
			;

	CurCell = h;
	return *this;
}

#ifndef CPLUS_BUG16
/*?
Post-increment equivalent of the previous operator.
?*/
IvlHashCellIter
IvlHashCellIter :: operator ++ (int)
{
	IvlHashCellIter result = *this;
	++(*this);
	return result;
}
#endif

/*?
Get the status of an iterator. The status may be one of \var{Normal, StartOfTable}, or
\var{EndOfTable}
?*/
#ifndef CPLUS_BUG13
IvlHashCellIter::hashiter_status
IvlHashCellIter :: GetStatus () const
#else
hashiter_status
IvlHashCellIter :: GetStatus () const
#endif
{
	if (CurCell)
		return Normal;
	if (CurIndex < 0)
		return StartOfTable;
	return EndOfTable;
}

#ifdef DOC
/*?
Check whether the status of an iterator is \var{Normal}.
?*/
IvlHashCellIter :: operator int () const
{
}

/*?class IvlHashIter
\typ{IvlHashIter}s are iterators that yield entries and not cells. They only differ
from \typ{IvlHashCellIter}s by their operator \fun{*}.
?*/

/*?
Get the current entry  pointed by an iterator.
?*/
IvlHashItem*
IvlHashIter :: operator * () const
{
}

/*?class IvlHashTableOf
The generic classes \typ{IvlHashTableOf, IvlHashCellOf, IvlHashCellIterOf}
and \typ{IvlHashIterOf} are derived classes of \typ{IvlHashTable, IvlHashCell, IvlHashCellIter}
and \typ{IvlHashIter} that provide hash tables whose entries are
pointers to class objects.
When parameterized by the class \typ{ITEM}, the following functions are redefined:
?*/

/*?nextdoc?*/
IvlHashCellOf<ITEM>*
IvlHashTableOf :: Add (const void* key, int* found)
{
}

/*?nextdoc?*/
IvlHashCellOf<ITEM>*
IvlHashTableOf :: Get (const void* key)
{
}

/*?nextdoc?*/
ITEM*
IvlHashTableOf :: Remove (const void* key, int* found)
{
}

/*?
These functions are equivalent to their homonyms in the class \typ{IvlHashTable},
except that they are customized in order to manipulate pointers to \typ{ITEM}
instead of \typ{void*}.
?*/
IvlHashCellRefOf<ITEM>
IvlHashTableOf :: operator [] (const void* key) const
{
}

/*?nextdoc?*/
void
IvlHashCellOf :: SetInfo (ITEM* p)
{
}

/*?
These functions are equivalent to their homonyms in the class \typ{IvlHashCell},
except that they are customized in order to manipulate pointers to \typ{ITEM}
instead of \typ{void*}.
?*/
ITEM*
IvlHashCellOf :: GetInfo () const
{
}

/*?nextdoc?*/
IvlHashIterOf :: IvlHashIterOf (const IvlHashTableOf<ITEM>& t)
{
}

/*?nextdoc?*/
IvlHashIterOf<ITEM>&
IvlHashIterOf :: operator ++ ()
{
}

/*?
These functions are equivalent to their homonyms in the class \typ{IvlHashIter},
except that they are customized in order to manipulate pointers to \typ{ITEM}
instead of \typ{void*}.
?*/
ITEM*
IvlHashIterOf :: operator * () const
{
}

#endif