/*
 *	CENA C++ Utilities
 *
 *	by Stephane Chatty
 *
 *	Copyright 1990, 1991, 1992
 *	Laboratoire de Recherche en Informatique (LRI)
 *	Centre d'Etudes de la Navigation Aerienne (CENA)
 *
 *	tables for managing an ID scheme, originally by Michel Beaudouin-Lafon
 *
 *	$Id$
 *	$CurLog$
 */

#include "IdTable.h"
#include <memory.h>

/*?class CcuIdTable
The class \typ{CcuIdTable} stores object pointers in a table, and assigns them a unique identifier.
Objects can be added, removed and retrieved in constant time (roughly, an index and a test).
This makes this class very useful for distributed applications that usually need
to communicate object identifiers instead of object pointers. In such applications,
mapping the identifier to an object must be a very fast operation.

The following paragraphs details the implementation of the ident table.

An identifier (id for short) is a 32 bits number made of an index in a table
in the lower 16 bits, and a check number in the higher 16 bits.
An entry of the table contains a check number, a 16 bits type (for use by the application),
and the object pointer.
Each entry in the table corresponds to a unique id made of the check of this
entry and its index.

Free entries in the table are linked in a free list by using the type field.
They also have a nil object pointer.
Each time an entry is reused, its check number is incremented.
Thus, the id corresponding to this entry differs from the previous id.

To retrieve an object from its id, we need only index in the table (by masking the check
part of the id), and check the check number of the id against the check number
in the table. If they are different, the id is no more in the table.

With 16 bits indexes, we can have at most \begin{math}2^{16}\end{math} entries
in the table. This is the maximum number of objects at any one time.
With 16 bits check we can generate \begin{math}2^{32}\end{math} different ids.
The check number wraps around so as to reuse (very) old identifiers.
This happens when a given entry has been used \begin{math}2^{16}\end{math} times.

The table automatically grows when it is full, until its maximum size.
Note that growing the table only involves linking the new free entries.
This is far less expensive than rehashing a hash table for instance.
?*/

/*?
Build an ident table with \var{nb} entries.
The table grows automatically (by a factor of 2) until 32768 entries (the maximum).
?*/
CcuIdTable :: CcuIdTable (int nb)
{
	if (nb > TID_MAX)
		nb = TID_MAX;
	entries = new CcuIdCell [nb];
	memset (entries, 0, nb * sizeof (CcuIdCell));
	last = entries + nb;
	
	// link free entries with the 'typ' field
	int i = 0;
	for (CcuIdCell* p = entries; p < last; p++)
		p->typ = ++i;

	(--p)->typ = 0;	// end of free list
	free = 0;
	last_free = --i;
	num_free = nb;
}

/*?hidden?*/
bool
CcuIdTable :: Grow (int newNb)
{
	int nb =  last - entries;
	if (nb >= TID_MAX)
		return FALSE;
	
	if (newNb >= TID_MAX)
		newNb = TID_MAX;
	
	CcuIdCell* newTbl = new CcuIdCell [newNb];
	int size = nb * sizeof (CcuIdCell);
	memcpy (newTbl, entries, size);
	memset (newTbl + nb, 0, newNb * sizeof (CcuIdCell) - size);
#ifdef CPLUS_BUG4
	delete [nb] entries;
#else
	delete [] entries;
#endif
	entries = newTbl;
	last = newTbl + newNb;
	
	// link free entries with the 'typ' field
	int i = nb;
	for (CcuIdCell* p = entries + nb; p < last; p++)
		p->typ = ++i;
	// prepend to current free list (to use them first)
	(--p)->typ = free;
	free = nb;
	last_free = --i;
	num_free += newNb - nb;
	
	return TRUE;
}

/*?
Store an object in the table and return its unique identifier.
If the table is full, return 0 (0 cannot be a valid identifier).
\var{typ} is an optional value that it stored in the table with the object.
It can be used to store the type of the object.
\var{obj} cannot be 0.
?*/
lword
CcuIdTable :: Store (const void* obj, sword typ)
{
	if (num_free == 0)
		if (! Grow ((last - entries) * 2))
			return 0;
	// get entry out of free list
	register CcuIdCell* p = entries + free;
	free = p->typ;
	--num_free;
	
	p->chk++;
	p->obj = obj;
	p->typ = typ;
	
	return (p->chk << TID_SHIFT) | (p - entries);
}

/*?
Remove object with identifier \var{id} from table.
Return FALSE if it was not found.
?*/
bool
CcuIdTable :: Remove (lword id)
{
	register	sword		i = sword (id & TID_MASK);
	register	CcuIdCell*	p = entries + i;
	
	if (p->chk != id >> TID_SHIFT)
		return FALSE;
	
	// link at end of free list (this avoids reusing the same ids too often)
	p->obj = 0;	// mark free
	if (num_free)
		entries [last_free].typ = i;	
	else
		free = i;
	last_free = i;
	num_free++;
	
	return TRUE;
}

/*?
Retrieve object with identifier \var{id} from table.
Return the object pointer, or 0 if it was not found.
if \var{typ} is not 0, it is filled with the type of the object.
?*/
const void*
CcuIdTable :: Get (lword id, sword* typ)
{
	register	CcuIdCell*	p;
	
	p = entries + (id & TID_MASK);
	if (p->chk != id >> TID_SHIFT)
		return 0;
	if (typ)
		*typ = p->typ;
	return p->obj;
}

/*?
Change the object pointer and the type of the entry associated to \var{id}.
The validity of the identifier is {\em not} checked.
The table is grown if the identifier falls out if it.
This makes it possible to store entries in the table with identifiers allocated
elsewhere, for instance to maintain a local copy of a remote table.
?*/
void
CcuIdTable :: Change (lword id, const void* obj, sword typ)
{
	register	CcuIdCell*	p;
	
	p = entries + (id & TID_MASK);
	int ip = p - entries;
	
	if (p >= last) {
		int size = last - entries;
		while (size <= ip)
			size *= 2;
		if (! Grow (size))
			return;
		p = entries + ip;
	}
	
	if (! p->obj) {
		// it's in the free list
		if (ip == free) {
			// if we maintain two tables in sync, this will always be the case
			free = p->typ;
		} else {
			int i = free;
			int j;
			while ((j = entries [i].typ) != ip)
				i = j;
			entries [i].typ = p->typ;
			if (ip == last_free)
				last_free = i;
		}
		num_free--;
	}
	p->chk = sword (id >> TID_SHIFT);
	p->typ = typ;
	p->obj = obj;
}

/*?class CcuIdIter
The class \typ{CcuIdIter} is an iterator over \typ{CcuIdTable}.
?*/

/*?hidden?*/
void
CcuIdIter :: Step ()
{
	if (! cur)
		return;
	
	// if table changed, reassign current
	if (entries != idt->entries) {
		cur = idt->entries + (cur - entries);
		entries = idt->entries;
	}
	
	// find valid entry
	while (cur < idt->last) {
		if (cur->obj)
			return;
		cur++;
	}
	cur = 0;
}

#ifdef DOC
// fake entries for documentation

/*?
Build an iterator over the table \var{t}.
?*/
CcuIdIter :: CcuIdIter (CcuIdTable& t)
{
}

/*?
This operator is similar to \fun{Current} below, except that it
advances the iterator to the next valid entry if the current entry has ben removed.
The iterator can be on an invalid entry if the current entry is removed from
the iterator itself.
?*/
const void*
CcuIdIter :: operator () ()
{
}

/*?
Advance the iterator to the next entry and return its associated data.
Return NIL if the whole table has been enumerated.
Note that this cannot be distinguished from an NIL data associated to
the current entry.
?*/
const void*
CcuIdIter :: operator ++ ()
{
}

/*?nextdoc?*/
const void*
CcuIdIter :: Current ()
{
}

/*?nextdoc?*/
sword
CcuIdIter :: CurType ()
{
}

/*?
Return the information of the current entry:
its associated data, its type, and its ident.
If the iterator is finished, these functions return 0.
\fun{CurId} is the only function for which 0 cannot be returned
for a valid entry. So this is the most secure way to identify that the whole
table has been ennumerated.
?*/
lword
CcuIdIter :: CurId ()
{
}

/*?
Reset the iterator to enumerate the whole table again.
?*/
void
CcuIdIter :: Reset ()
{
}

#endif /* DOC */