summaryrefslogtreecommitdiff
path: root/utils/IdTable.cc
diff options
context:
space:
mode:
Diffstat (limited to 'utils/IdTable.cc')
-rw-r--r--utils/IdTable.cc88
1 files changed, 43 insertions, 45 deletions
diff --git a/utils/IdTable.cc b/utils/IdTable.cc
index 193973c..5bc461f 100644
--- a/utils/IdTable.cc
+++ b/utils/IdTable.cc
@@ -16,8 +16,8 @@
#include "IdTable.h"
#include <memory.h>
-/*?class CcuIdTable
-A \typ{CcuIdTable} stores pointers in a table, and assigns them a unique identifier.
+/*?class IvlIdTable
+A \typ{IvlIdTable} 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,
@@ -59,15 +59,14 @@ This is far less expensive than rehashing a hash table for instance.
#define TID_SHIFT 16
#define TID_MASK 0xffff
-
-struct CcuIdCell {
+struct IvlIdCell {
sword Check; // the check number
- CcuIdType Type; // for the appli, for free list when not allocated
- CcuIdItem* Info;
+ IvlIdType Type; // for the appli, for free list when not allocated
+ IvlIdItem* Info;
-inline CcuID ComputeId (const CcuIdTable* t)
+inline IvlID ComputeId (const IvlIdTable* t)
{
- return (CcuID) ((Check << TID_SHIFT) | (this - t->Entries));
+ return (IvlID) ((Check << TID_SHIFT) | (this - t->Entries));
}
};
@@ -75,7 +74,7 @@ inline CcuID ComputeId (const CcuIdTable* t)
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)
+IvlIdTable :: IvlIdTable (int sz)
{
if (sz > TID_MAX)
sz = TID_MAX;
@@ -83,13 +82,13 @@ CcuIdTable :: CcuIdTable (int sz)
sz = 0;
int nb = 2 << sz;
- Entries = new CcuIdCell [nb];
- memset (Entries, 0, nb * sizeof (CcuIdCell));
+ Entries = new IvlIdCell [nb];
+ memset (Entries, 0, nb * sizeof (IvlIdCell));
LastCell = Entries + nb;
// link free entries with the 'Type' field
int i = 0;
- CcuIdCell* p;
+ IvlIdCell* p;
for (p = Entries; p < LastCell; p++)
p->Type = ++i;
@@ -101,7 +100,7 @@ CcuIdTable :: CcuIdTable (int sz)
/*?hidden?*/
bool
-CcuIdTable :: Grow (int newNb)
+IvlIdTable :: Grow (int newNb)
{
int nb = LastCell - Entries;
if (nb >= TID_MAX)
@@ -110,10 +109,10 @@ CcuIdTable :: Grow (int newNb)
if (newNb >= TID_MAX)
newNb = TID_MAX;
- CcuIdCell* newTbl = new CcuIdCell [newNb];
- int size = nb * sizeof (CcuIdCell);
+ IvlIdCell* newTbl = new IvlIdCell [newNb];
+ int size = nb * sizeof (IvlIdCell);
memcpy (newTbl, Entries, size);
- memset (newTbl + nb, 0, newNb * sizeof (CcuIdCell) - size);
+ memset (newTbl + nb, 0, newNb * sizeof (IvlIdCell) - size);
#ifdef CPLUS_BUG4
delete [nb] Entries;
#else
@@ -124,7 +123,7 @@ CcuIdTable :: Grow (int newNb)
// link free entries with the 'Type' field
int i = nb;
- CcuIdCell* p;
+ IvlIdCell* p;
for (p = Entries + nb; p < LastCell; p++)
p->Type = ++i;
// prepend to current free list (to use them first)
@@ -143,14 +142,14 @@ 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.
?*/
-CcuID
-CcuIdTable :: Store (CcuIdItem* obj, CcuIdType typ)
+IvlID
+IvlIdTable :: Store (IvlIdItem* obj, IvlIdType typ)
{
if (NumFree == 0)
if (! Grow ((LastCell - Entries) * 2))
return 0;
// get entry out of free list
- register CcuIdCell* p = Entries + FirstFree;
+ register IvlIdCell* p = Entries + FirstFree;
FirstFree = p->Type;
--NumFree;
@@ -165,15 +164,15 @@ CcuIdTable :: Store (CcuIdItem* obj, CcuIdType typ)
Remove object with identifier \var{id} from table.
Return false if it was not found.
?*/
-CcuIdItem*
-CcuIdTable :: Remove (CcuID id, bool* found, CcuIdType* type)
+IvlIdItem*
+IvlIdTable :: Remove (IvlID id, bool* found, IvlIdType* type)
{
- register CcuIdIndex i = CcuIdIndex (id & TID_MASK);
- register CcuIdCell* p = Entries + i;
+ register IvlIdIndex i = IvlIdIndex (id & TID_MASK);
+ register IvlIdCell* p = Entries + i;
- CcuIdType ret_type;
+ IvlIdType ret_type;
bool ret_found;
- CcuIdItem* ret_value;
+ IvlIdItem* ret_value;
if (p->Check != id >> TID_SHIFT) {
ret_type = 0;
@@ -187,7 +186,7 @@ CcuIdTable :: Remove (CcuID id, bool* found, CcuIdType* type)
p->Info = 0; // mark as free
p->Check = 0; // mark as free
if (NumFree > 0)
- Entries [LastFree].Type = (CcuIdType) i;
+ Entries [LastFree].Type = (IvlIdType) i;
else
FirstFree = i;
LastFree = i;
@@ -205,10 +204,10 @@ 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)
+IvlIdItem*
+IvlIdTable :: Get (IvlID id, IvlIdType* typ)
{
- register CcuIdCell* p;
+ register IvlIdCell* p;
p = Entries + (id & TID_MASK);
if (p->Check != id >> TID_SHIFT)
@@ -226,9 +225,9 @@ 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)
+IvlIdTable :: Change (IvlID id, IvlIdItem* obj, IvlIdType typ)
{
- register CcuIdCell* p;
+ register IvlIdCell* p;
p = Entries + (id & TID_MASK);
int ip = p - Entries;
@@ -263,15 +262,15 @@ CcuIdTable :: Change (CcuID id, CcuIdItem* obj, CcuIdType typ)
p->Info = obj;
}
-/*?class CcuIdIter
-The class \typ{CcuIdIter} is an iterator over \typ{CcuIdTable}.
+/*?class IvlIdIter
+The class \typ{IvlIdIter} is an iterator over \typ{IvlIdTable}.
?*/
#ifdef DOC
/*?
Build an iterator over the table \var{t}.
?*/
-CcuIdIter :: CcuIdIter (CcuIdTable& t)
+IvlIdIter :: IvlIdIter (IvlIdTable& t)
{
}
@@ -279,17 +278,16 @@ CcuIdIter :: CcuIdIter (CcuIdTable& t)
Reset the iterator to enumerate the whole table again.
?*/
void
-CcuIdIter :: Reset ()
+IvlIdIter :: Reset ()
{
}
#endif /* DOC */
-
/*?
Advance the iterator to the next entry.
?*/
-CcuIdIter&
-CcuIdIter :: operator ++ ()
+IvlIdIter&
+IvlIdIter :: operator ++ ()
{
if (! CurCell)
return *this;
@@ -313,15 +311,15 @@ CcuIdIter :: operator ++ ()
}
/*?nextdoc?*/
-CcuIdItem*
-CcuIdIter :: Current () const
+IvlIdItem*
+IvlIdIter :: Current () const
{
return (CurCell && StatusFlag == Normal) ? CurCell->Info : 0;
}
/*?nextdoc?*/
-CcuIdType
-CcuIdIter :: CurType () const
+IvlIdType
+IvlIdIter :: CurType () const
{
return (CurCell && StatusFlag == Normal) ? CurCell->Type : 0;
}
@@ -331,8 +329,8 @@ 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
+IvlID
+IvlIdIter :: CurId () const
{
return (CurCell && StatusFlag == Normal) ? CurCell->ComputeId (TheTable) : 0;
}
generated by cgit v1.1 at 2024-06-29 09:52:24 +0000