diff options
Diffstat (limited to 'utils/IdTable.cc')
| -rw-r--r-- | utils/IdTable.cc | 319 |
1 files changed, 319 insertions, 0 deletions
diff --git a/utils/IdTable.cc b/utils/IdTable.cc new file mode 100644 index 0000000..bd18e0a --- /dev/null +++ b/utils/IdTable.cc @@ -0,0 +1,319 @@ +/* + * 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 */ + |