replaced TRUE/FALSE by true/false

1 files changed, 162 insertions, 145 deletions

diff --git a/utils/IdTable.cc b/utils/IdTable.cc
index bd18e0a..bfca17a 100644
--- a/utils/IdTable.cc
+++ b/utils/IdTable.cc
@@ -17,13 +17,13 @@
 #include <memory.h>
 
 /*?class CcuIdTable
-The class \typ{CcuIdTable} stores object pointers in a table, and assigns them a unique identifier.
+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 ident table.
+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.
@@ -32,8 +32,7 @@ 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.
+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.
 
@@ -52,63 +51,87 @@ 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 \var{nb} 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 nb)
+CcuIdTable :: CcuIdTable (int sz)
 {
-	if (nb > TID_MAX)
-		nb = TID_MAX;
-	entries = new CcuIdCell [nb];
-	memset (entries, 0, nb * sizeof (CcuIdCell));
-	last = entries + nb;
+	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 'typ' field
+	// link free entries with the 'Type' field
 	int i = 0;
-	for (CcuIdCell* p = entries; p < last; p++)
-		p->typ = ++i;
+	for (CcuIdCell* p = Entries; p < LastCell; p++)
+		p->Type = ++i;
 
-	(--p)->typ = 0;	// end of free list
-	free = 0;
-	last_free = --i;
-	num_free = nb;
+	(--p)->Type = 0;	// end of free list
+	FirstFree = 0;
+	LastFree = --i;
+	NumFree = nb;
 }
 
 /*?hidden?*/
 bool
 CcuIdTable :: Grow (int newNb)
 {
-	int nb =  last - entries;
+	int nb =  LastCell - Entries;
 	if (nb >= TID_MAX)
-		return FALSE;
+		return false;
 	
 	if (newNb >= TID_MAX)
 		newNb = TID_MAX;
 	
 	CcuIdCell* newTbl = new CcuIdCell [newNb];
 	int size = nb * sizeof (CcuIdCell);
-	memcpy (newTbl, entries, size);
+	memcpy (newTbl, Entries, size);
 	memset (newTbl + nb, 0, newNb * sizeof (CcuIdCell) - size);
 #ifdef CPLUS_BUG4
-	delete [nb] entries;
+	delete [nb] Entries;
 #else
-	delete [] entries;
+	delete [] Entries;
 #endif
-	entries = newTbl;
-	last = newTbl + newNb;
+	Entries = newTbl;
+	LastCell = newTbl + newNb;
 	
-	// link free entries with the 'typ' field
+	// link free entries with the 'Type' field
 	int i = nb;
-	for (CcuIdCell* p = entries + nb; p < last; p++)
-		p->typ = ++i;
+	for (CcuIdCell* p = Entries + nb; p < LastCell; p++)
+		p->Type = ++i;
 	// prepend to current free list (to use them first)
-	(--p)->typ = free;
-	free = nb;
-	last_free = --i;
-	num_free += newNb - nb;
+	(--p)->Type = FirstFree;
+	FirstFree = nb;
+	LastFree = --i;
+	NumFree += newNb - nb;
 	
-	return TRUE;
+	return true;
 }
 
 /*?
@@ -118,47 +141,61 @@ If the table is full, return 0 (0 cannot be a valid identifier).
 It can be used to store the type of the object.
 \var{obj} cannot be 0.
 ?*/
-lword
-CcuIdTable :: Store (const void* obj, sword typ)
+CcuID
+CcuIdTable :: Store (CcuIdItem* obj, CcuIdType typ)
 {
-	if (num_free == 0)
-		if (! Grow ((last - entries) * 2))
+	if (NumFree == 0)
+		if (! Grow ((LastCell - Entries) * 2))
 			return 0;
 	// get entry out of free list
-	register CcuIdCell* p = entries + free;
-	free = p->typ;
-	--num_free;
+	register CcuIdCell* p = Entries + FirstFree;
+	FirstFree = p->Type;
+	--NumFree;
 	
-	p->chk++;
-	p->obj = obj;
-	p->typ = typ;
+	p->Check++;
+	p->Info = obj;
+	p->Type = typ;
 	
-	return (p->chk << TID_SHIFT) | (p - entries);
+	return p->ComputeId (this);
 }
 
 /*?
 Remove object with identifier \var{id} from table.
-Return FALSE if it was not found.
+Return false if it was not found.
 ?*/
-bool
-CcuIdTable :: Remove (lword id)
+CcuIdItem*
+CcuIdTable :: Remove (CcuID id, bool* found, CcuIdType* type)
 {
-	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;
+	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;
 }
 
 /*?
@@ -166,17 +203,17 @@ 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)
+CcuIdItem*
+CcuIdTable :: Get (CcuID id, CcuIdType* typ)
 {
-	register	CcuIdCell*	p;
-	
-	p = entries + (id & TID_MASK);
-	if (p->chk != id >> TID_SHIFT)
+	register CcuIdCell* p;
+
+	p = Entries + (id & TID_MASK);
+	if (p->Check != id >> TID_SHIFT)
 		return 0;
 	if (typ)
-		*typ = p->typ;
-	return p->obj;
+		*typ = p->Type;
+	return p->Info;
 }
 
 /*?
@@ -187,72 +224,48 @@ 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)
+CcuIdTable :: Change (CcuID id, CcuIdItem* obj, CcuIdType typ)
 {
-	register	CcuIdCell*	p;
+	register CcuIdCell* p;
 	
-	p = entries + (id & TID_MASK);
-	int ip = p - entries;
+	p = Entries + (id & TID_MASK);
+	int ip = p - Entries;
 	
-	if (p >= last) {
-		int size = last - entries;
+	if (p >= LastCell) {
+		int size = LastCell - Entries;
 		while (size <= ip)
 			size *= 2;
 		if (! Grow (size))
 			return;
-		p = entries + ip;
+		p = Entries + ip;
 	}
 	
-	if (! p->obj) {
+	if (! p->Info) {
 		// it's in the free list
-		if (ip == free) {
+		if (ip == FirstFree) {
 			// if we maintain two tables in sync, this will always be the case
-			free = p->typ;
+			FirstFree = p->Type;
 		} else {
-			int i = free;
+			int i = FirstFree;
 			int j;
-			while ((j = entries [i].typ) != ip)
+			while ((j = Entries [i].Type) != ip)
 				i = j;
-			entries [i].typ = p->typ;
-			if (ip == last_free)
-				last_free = i;
+			Entries [i].Type = p->Type;
+			if (ip == LastFree)
+				LastFree = i;
 		}
-		num_free--;
+		NumFree--;
 	}
-	p->chk = sword (id >> TID_SHIFT);
-	p->typ = typ;
-	p->obj = obj;
+	p->Check = sword (id >> TID_SHIFT);
+	p->Type = typ;
+	p->Info = 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}.
 ?*/
@@ -261,59 +274,63 @@ 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.
+Reset the iterator to enumerate the whole table again.
 ?*/
-const void*
-CcuIdIter :: operator () ()
+void
+CcuIdIter :: Reset ()
 {
 }
+#endif /* DOC */
+
 
 /*?
-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.
+Advance the iterator to the next entry.
 ?*/
-const void*
+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?*/
-const void*
-CcuIdIter :: Current ()
+CcuIdItem*
+CcuIdIter :: Current () const
 {
+	return (CurCell && StatusFlag == Normal) ? CurCell->Info : 0;
 }
 
 /*?nextdoc?*/
-sword
-CcuIdIter :: CurType ()
+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.
-\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 ()
+CcuID
+CcuIdIter :: CurId () const
 {
+	return (CurCell && StatusFlag == Normal) ? CurCell->ComputeId (TheTable) : 0;
 }
-
-/*?
-Reset the iterator to enumerate the whole table again.
-?*/
-void
-CcuIdIter :: Reset ()
-{
-}
-
-#endif /* DOC */
-