path: root/utils/IdTable.cc

/*
 *	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
A \typ{CcuIdTable} stores 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 identifier 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.

Entries can be discarded, then reused.
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.
?*/

/*
 *	TID_MASK = 2^TID_SHIFT = max table size
 *	TID_MASK = TID_SHIFT bits set to 1.
 */
#define	TID_MAX	(2 << 16)
#define	TID_SHIFT	16
#define	TID_MASK	0xffff


struct CcuIdCell {
	sword	Check;	// the check number
	CcuIdType		Type;	// for the appli, for free list when not allocated
	CcuIdItem*	Info;

inline CcuID ComputeId (const CcuIdTable* t)
	{
		return (CcuID) ((Check << TID_SHIFT) | (this - t->Entries));
	}
};

/*?
Build an ident table with $2^sz$ entries.
The table grows automatically (by a factor of 2) until 32768 entries (the maximum).
?*/
CcuIdTable :: CcuIdTable (int sz)
{
	if (sz > TID_MAX)
		sz = TID_MAX;
	else if (sz < 0)
		sz = 0;
	int nb = 2 << sz;

	Entries = new CcuIdCell [nb];
	memset (Entries, 0, nb * sizeof (CcuIdCell));
	LastCell = Entries + nb;
	
	// link free entries with the 'Type' field
	int i = 0;
	for (CcuIdCell* p = Entries; p < LastCell; p++)
		p->Type = ++i;

	(--p)->Type = 0;	// end of free list
	FirstFree = 0;
	LastFree = --i;
	NumFree = nb;
}

/*?hidden?*/
bool
CcuIdTable :: Grow (int newNb)
{
	int nb =  LastCell - 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;
	LastCell = newTbl + newNb;
	
	// link free entries with the 'Type' field
	int i = nb;
	for (CcuIdCell* p = Entries + nb; p < LastCell; p++)
		p->Type = ++i;
	// prepend to current free list (to use them first)
	(--p)->Type = FirstFree;
	FirstFree = nb;
	LastFree = --i;
	NumFree += 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.
?*/
CcuID
CcuIdTable :: Store (CcuIdItem* obj, CcuIdType typ)
{
	if (NumFree == 0)
		if (! Grow ((LastCell - Entries) * 2))
			return 0;
	// get entry out of free list
	register CcuIdCell* p = Entries + FirstFree;
	FirstFree = p->Type;
	--NumFree;
	
	p->Check++;
	p->Info = obj;
	p->Type = typ;
	
	return p->ComputeId (this);
}

/*?
Remove object with identifier \var{id} from table.
Return false if it was not found.
?*/
CcuIdItem*
CcuIdTable :: Remove (CcuID id, bool* found, CcuIdType* type)
{
	register CcuIdIndex i = CcuIdIndex (id & TID_MASK);
	register CcuIdCell* p = Entries + i;

	CcuIdType ret_type;
	bool ret_found;
	CcuIdItem* ret_value;

	if (p->Check != id >> TID_SHIFT) {
		ret_type = 0;
		ret_value = 0;
		ret_found = false;
	} else {
		ret_type = p->Type;
		ret_value = p->Info;
		ret_found = true;
		/* link at end of free list (this avoids reusing the same ids too often) */
		p->Info = 0;	// mark as free
		p->Check = 0;	// mark as free
		if (NumFree > 0)
			Entries [LastFree].Type = (CcuIdType) i;
		else
			FirstFree = i;
		LastFree = i;
		NumFree++;
	}
	if (found)
		*found = ret_found;
	if (type)
		*type = ret_type;
	return ret_value;
}

/*?
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.
?*/
CcuIdItem*
CcuIdTable :: Get (CcuID id, CcuIdType* typ)
{
	register CcuIdCell* p;

	p = Entries + (id & TID_MASK);
	if (p->Check != id >> TID_SHIFT)
		return 0;
	if (typ)
		*typ = p->Type;
	return p->Info;
}

/*?
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 (CcuID id, CcuIdItem* obj, CcuIdType typ)
{
	register CcuIdCell* p;
	
	p = Entries + (id & TID_MASK);
	int ip = p - Entries;
	
	if (p >= LastCell) {
		int size = LastCell - Entries;
		while (size <= ip)
			size *= 2;
		if (! Grow (size))
			return;
		p = Entries + ip;
	}
	
	if (! p->Info) {
		// it's in the free list
		if (ip == FirstFree) {
			// if we maintain two tables in sync, this will always be the case
			FirstFree = p->Type;
		} else {
			int i = FirstFree;
			int j;
			while ((j = Entries [i].Type) != ip)
				i = j;
			Entries [i].Type = p->Type;
			if (ip == LastFree)
				LastFree = i;
		}
		NumFree--;
	}
	p->Check = sword (id >> TID_SHIFT);
	p->Type = typ;
	p->Info = obj;
}

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

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

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


/*?
Advance the iterator to the next entry.
?*/
CcuIdIter&
CcuIdIter :: operator ++ ()
{
	if (! CurCell)
		return *this;
	
	// if table changed, reassign current
	if (Entries != TheTable->Entries) {
		CurCell = TheTable->Entries + (CurCell - Entries);
		Entries = TheTable->Entries;
	}
	
	// find valid entry
	while (++CurCell < TheTable->LastCell) {
		if (CurCell->Info != 0) {
			StatusFlag = Normal;
			return *this;
		}
	}
	StatusFlag = EndOfTable;
	CurCell = 0;
	return *this;
}

/*?nextdoc?*/
CcuIdItem*
CcuIdIter :: Current () const
{
	return (CurCell && StatusFlag == Normal) ? CurCell->Info : 0;
}

/*?nextdoc?*/
CcuIdType
CcuIdIter :: CurType () const
{
	return (CurCell && StatusFlag == Normal) ? CurCell->Type : 0;
}

/*?
Return the information of the current entry:
its associated data, its type, and its ident.
If the iterator is finished, these functions return 0.
?*/
CcuID
CcuIdIter :: CurId () const
{
	return (CurCell && StatusFlag == Normal) ? CurCell->ComputeId (TheTable) : 0;
}