diff options
Diffstat (limited to 'utils/HashTable.cc')
| -rw-r--r-- | utils/HashTable.cc | 291 |
1 files changed, 141 insertions, 150 deletions
diff --git a/utils/HashTable.cc b/utils/HashTable.cc index 002efdd..59ac76d 100644 --- a/utils/HashTable.cc +++ b/utils/HashTable.cc @@ -22,15 +22,15 @@ #include <stdio.h> #endif -/*?class CcuHashTable -The class \typ{CcuHashTable} implements association tables based on a hashing algorithm. +/*?class IvlHashTable +The class \typ{IvlHashTable} implements association tables based on a hashing algorithm. Hash tables are useful to store information that needs to be retrieved quickly, and which bears no efficient ordering. For instance, this is the case for strings: in a compiler, one may wish to maintain a hash table with identifiers as hash keys and symbol table entries as information. -A hash table is made of a set of hash entries (of class \typ{CcuHashCell}), +A hash table is made of a set of hash entries (of class \typ{IvlHashCell}), which can be modified during the life of the table. An entry has two main fields: a hash key, and a user defined information attached to that key. We will not give details about the structure of @@ -40,13 +40,13 @@ here as a reminder. The current implementation uses lists to store the synonyms so that entries can be deleted efficiently. -The class \typ{CcuHashTable} makes no assumption about the type of the keys, which it handles as +The class \typ{IvlHashTable} makes no assumption about the type of the keys, which it handles as \typ{const void *}. The user can define several functions used when managing a hash table: the hash function, which is determinant for the performances of the hash table, and the functions to copy, compare, and destroy keys. Basic functions are provided by default. -The following definitions are used by member functions of the class \typ{CcuHashTable}, +The following definitions are used by member functions of the class \typ{IvlHashTable}, and by them only: \index{HASH_F}\index{HCP_F}\index{HCMP_F}\index{HENUM_F}\index{HDEL_F} \begin{ccode} @@ -59,35 +59,33 @@ and by them only: ?*/ - - -CcuAllocator* CcuHashCell::HashCellMem = 0; +IvlAllocator* IvlHashCell::HashCellMem = 0; /*?hidden?*/ void -CcuHashCell :: ClassInit () +IvlHashCell :: ClassInit () { if (!HashCellMem) - HashCellMem = new CcuAllocator (sizeof (CcuHashCell)); + HashCellMem = new IvlAllocator (sizeof (IvlHashCell)); } /*?nodoc?*/ void* -CcuHashCell :: operator new (size_t) +IvlHashCell :: operator new (size_t) { return HashCellMem->Alloc (); } /*?nodoc?*/ void -CcuHashCell :: operator delete (void* that) +IvlHashCell :: operator delete (void* that) { HashCellMem->Free (that); } #if 0 unsigned int -CcuHashTable :: HashPtr (const void* p, int max) +IvlHashTable :: HashPtr (const void* p, int max) { /* stolen from Tcl */ /* this would be easier if max was a power of 2 */ @@ -96,13 +94,13 @@ CcuHashTable :: HashPtr (const void* p, int max) #endif /*? -Constructor for \typ{CcuHashTable}s. Build a hash table based on an array of +Constructor for \typ{IvlHashTable}s. Build a hash table based on an array of size \var{size}. You can optionally provide your own functions for copying, destroying and comparing keys, and the hashing function. If no hashing function is provided, the identity function is used. ?*/ -CcuHashTable :: CcuHashTable (unsigned int size, HASH_F hash_fun, HCP_F cp_fun, HDEL_F del_fun, HCMP_F cmp_fun) +IvlHashTable :: IvlHashTable (unsigned int size, HASH_F hash_fun, HCP_F cp_fun, HDEL_F del_fun, HCMP_F cmp_fun) : Size (size), Hash (hash_fun), Copy (cp_fun), @@ -111,12 +109,12 @@ CcuHashTable :: CcuHashTable (unsigned int size, HASH_F hash_fun, HCP_F cp_fun, { if (Size <= 0) Size = 1; - Table = new CcuHashCell* [Size]; - memset (Table, 0, Size*sizeof (CcuHashCell*)); + Table = new IvlHashCell* [Size]; + memset (Table, 0, Size*sizeof (IvlHashCell*)); /* I know that HashCells can only be created from HashTables */ - if (!CcuHashCell::HashCellMem) - CcuHashCell::ClassInit (); + if (!IvlHashCell::HashCellMem) + IvlHashCell::ClassInit (); } /*? @@ -124,21 +122,21 @@ Copy constructor for hash tables. The table and the cells are copied. The keys a copied only if \var{ht} had a copy function. The new hash table will contain the same informations as \var{ht}, but the synonyms will not necessarily be in the same order. ?*/ -CcuHashTable :: CcuHashTable (const CcuHashTable& ht) +IvlHashTable :: IvlHashTable (const IvlHashTable& ht) : Size (ht.Size), Hash (ht.Hash), Copy (ht.Copy), Delete (ht.Delete), Compare (ht.Compare) { - Table = new CcuHashCell* [Size]; - register CcuHashCell** p = Table; - register CcuHashCell** q = ht.Table; + Table = new IvlHashCell* [Size]; + register IvlHashCell** p = Table; + register IvlHashCell** q = ht.Table; while (p < Table + Size) { *p = 0; - register CcuHashCell* r = *q; + register IvlHashCell* r = *q; while (r) { - (*p) = new CcuHashCell (Copy ? (*Copy) (r->GetKey ()) : r->GetKey (), *p); + (*p) = new IvlHashCell (Copy ? (*Copy) (r->GetKey ()) : r->GetKey (), *p); (*p)->SetInfo (r->Info); r = r->Next; } @@ -150,7 +148,7 @@ CcuHashTable :: CcuHashTable (const CcuHashTable& ht) /*? Destructor for hash tables. All keys are destroyed if a destruction function was provided. ?*/ -CcuHashTable :: ~CcuHashTable () +IvlHashTable :: ~IvlHashTable () { Clear (); @@ -161,23 +159,22 @@ CcuHashTable :: ~CcuHashTable () #endif } - /*? Remove all data from the hash table. All keys are destroyed if a destruction function was provided. ?*/ void -CcuHashTable :: Clear () +IvlHashTable :: Clear () { /* destroy keys */ if (Delete) { - CcuHashCellIter hi (*this); + IvlHashCellIter hi (*this); while (++hi) (*Delete) ((*hi)->Key); } /* destroy cells */ int s = Size; - CcuHashCell** entry = Table; + IvlHashCell** entry = Table; /* for each slot of the array ... */ for ( ; s--; ++entry ) { @@ -185,8 +182,8 @@ CcuHashTable :: Clear () continue; /* ... destroy all cells linked from that slot ...*/ - for (CcuHashCell* h = *entry; h;) { - CcuHashCell* del = h; + for (IvlHashCell* h = *entry; h;) { + IvlHashCell* del = h; h = h->Next; delete del; } @@ -196,10 +193,9 @@ CcuHashTable :: Clear () } } - /*?hidden?*/ -CcuHashCell** -CcuHashTable :: HashKey (const void* key) const +IvlHashCell** +IvlHashTable :: HashKey (const void* key) const { register unsigned int h = (unsigned int) key; @@ -213,10 +209,10 @@ CcuHashTable :: HashKey (const void* key) const } /*?hidden?*/ -CcuHashCell* -CcuHashTable :: FindCell (CcuHashCell** entry, const void* key) const +IvlHashCell* +IvlHashTable :: FindCell (IvlHashCell** entry, const void* key) const { - CcuHashCell* h; + IvlHashCell* h; for (h = *entry; h; h = h -> Next) if (Compare ? (*Compare) (key, h->Key) : (key == h->Key)) break; @@ -225,41 +221,40 @@ CcuHashTable :: FindCell (CcuHashCell** entry, const void* key) const /*?hidden?*/ -CcuHashCell* -CcuHashTable :: AddCell (CcuHashCell** entry, const void* key) const +IvlHashCell* +IvlHashTable :: AddCell (IvlHashCell** entry, const void* key) const { if (Copy) key = (* Copy) (key); - CcuHashCell* h = new CcuHashCell (key, *entry); + IvlHashCell* h = new IvlHashCell (key, *entry); *entry = h; return h; } -/*?class CcuHashCell -\typ{CcuHashCell}s hold the entries of an hash table. -A \typ{CcuHashCell} contains a key and a user defined information. +/*?class IvlHashCell +\typ{IvlHashCell}s hold the entries of an hash table. +A \typ{IvlHashCell} contains a key and a user defined information. ?*/ - #ifdef DOC /*?hidden?*/ -CcuHashCellOf :: CcuHashCell (const void*, CcuHashCell*) +IvlHashCellOf :: IvlHashCell (const void*, IvlHashCell*) { } /*?nextdoc?*/ const void* -CcuHashCell :: GetKey () const +IvlHashCell :: GetKey () const { } /*? -Retrieve the key, or the information from a \typ{CcuHashCell}. +Retrieve the key, or the information from a \typ{IvlHashCell}. ?*/ -CcuHashItem* -CcuHashCell :: GetInfo () const +IvlHashItem* +IvlHashCell :: GetInfo () const { } @@ -267,7 +262,7 @@ CcuHashCell :: GetInfo () const Set the cell information to \var{p}. ?*/ void -CcuHashCell :: SetInfo (CcuHashItem* p) +IvlHashCell :: SetInfo (IvlHashItem* p) { } @@ -281,12 +276,12 @@ function returns the address of the hash entry corresponding to the key. \fun{Add} uses the hash function of the table. If the key is new and a copy function was provided, the key is copied. ?*/ -CcuHashCell* -CcuHashTable :: Add (const void* key, int* found) +IvlHashCell* +IvlHashTable :: Add (const void* key, int* found) { /* est-il dans la table ? */ - CcuHashCell** entry = HashKey (key); - CcuHashCell* h = FindCell (entry, key); + IvlHashCell** entry = HashKey (key); + IvlHashCell* h = FindCell (entry, key); if (found) *found = (h != 0); @@ -302,19 +297,19 @@ Retrieve the key \var{key} from the table. If it exists, return the address of its hash entry, thus allowing to get its associated info. If the key does not exist in the table, return 0. ?*/ -CcuHashCell* -CcuHashTable :: Get (const void* key) +IvlHashCell* +IvlHashTable :: Get (const void* key) { - CcuHashCell **entry = HashKey (key); + IvlHashCell **entry = HashKey (key); return FindCell (entry, key); } #if 0 -CcuHashItem*& -CcuHashTable :: operator [] (const void* key) +IvlHashItem*& +IvlHashTable :: operator [] (const void* key) { - CcuHashCell **entry = HashKey (key); - CcuHashCell *h = FindCell (entry, key); + IvlHashCell **entry = HashKey (key); + IvlHashCell *h = FindCell (entry, key); if (!h) h = AddCell (entry, key); @@ -328,25 +323,24 @@ reference can be used for reading as for writing. If the key was not present in the table, a new entry is created when writing, and a default (invalid) entry is returned when reading. ?*/ -CcuHashCellRef -CcuHashTable :: operator [] (const void* key) const +IvlHashCellRef +IvlHashTable :: operator [] (const void* key) const { - return CcuHashCellRef (*this, key); + return IvlHashCellRef (*this, key); } #endif - /*? Remove the key \var{key} from the table. If it exists, return its associated data. If the key does not exist, return 0. \var{found} may be used to test whether the key was found. ?*/ -CcuHashItem* -CcuHashTable :: Remove (const void* key, int* found) +IvlHashItem* +IvlHashTable :: Remove (const void* key, int* found) { - CcuHashCell **entry; - register CcuHashCell *h, *hp = 0; - CcuHashItem* info = 0; + IvlHashCell **entry; + register IvlHashCell *h, *hp = 0; + IvlHashItem* info = 0; entry = HashKey (key); @@ -372,32 +366,31 @@ CcuHashTable :: Remove (const void* key, int* found) return info; } - /*? Change the size of the table, which is re-hashed. ?*/ void -CcuHashTable :: Resize (int size) +IvlHashTable :: Resize (int size) { int s = Size; if (size <= 0) size = 1; Size = size; - CcuHashCell** entry = Table; - CcuHashCell** old_table = Table; - Table = new CcuHashCell* [size]; - memset (Table, 0, size*sizeof (CcuHashCell*)); + IvlHashCell** entry = Table; + IvlHashCell** old_table = Table; + Table = new IvlHashCell* [size]; + memset (Table, 0, size*sizeof (IvlHashCell*)); /* rehash */ for (; s--; ++entry) { /* scan the list */ - register CcuHashCell *cur, *next; + register IvlHashCell *cur, *next; for (cur = *entry; cur; cur = next) { next = cur->Next; - register CcuHashCell** slot = HashKey (cur->Key); + register IvlHashCell** slot = HashKey (cur->Key); /* prepend the cell to the corresponding list */ cur->Next = *slot; @@ -411,14 +404,13 @@ CcuHashTable :: Resize (int size) #endif } - #ifdef TUNE /*?nextdoc?*/ void -CcuHashTable :: HashStats () +IvlHashTable :: HashStats () { - CcuHashCell * h; - CcuHashCell **entry; + IvlHashCell * h; + IvlHashCell **entry; int s, coll = 0, empty = 0; for (s = Size, entry = Table; s--; entry++) { @@ -442,15 +434,15 @@ Print some statistics about this hash table on file descriptor \var{fd} (default is stderr). ?*/ void -CcuHashTable :: CollStats () +IvlHashTable :: CollStats () { - CcuHashCell * h; - CcuHashCell **entry; + IvlHashCell * h; + IvlHashCell **entry; int s, lcoll, coll = 0, empty = 0; int min = 999999, max = 0, moy = 0, moy2 = 0; float fmoy, fvar; - for (s = Size, entry = (CcuHashCell**) Table; s--; entry++) { + for (s = Size, entry = (IvlHashCell**) Table; s--; entry++) { lcoll = 0; if (h = *entry) { while (h = h->Next) { @@ -477,11 +469,11 @@ CcuHashTable :: CollStats () #endif /* TUNE */ -CcuHashItem* -CcuHashCellRef :: operator = (CcuHashItem* info) +IvlHashItem* +IvlHashCellRef :: operator = (IvlHashItem* info) { - CcuHashCell **entry = Table.HashKey (Key); - CcuHashCell *h = Table.FindCell (entry, Key); + IvlHashCell **entry = Table.HashKey (Key); + IvlHashCell *h = Table.FindCell (entry, Key); if (!h) h = Table.AddCell (entry, Key); @@ -491,24 +483,23 @@ CcuHashCellRef :: operator = (CcuHashItem* info) return info; } -CcuHashCellRef :: operator CcuHashItem* () +IvlHashCellRef :: operator IvlHashItem* () { - CcuHashCell **entry = Table.HashKey (Key); - CcuHashCell *h = Table.FindCell (entry, Key); + IvlHashCell **entry = Table.HashKey (Key); + IvlHashCell *h = Table.FindCell (entry, Key); return h ? h->GetInfo () : 0; } - -/*?class CcuDictionnary +/*?class IvlDictionnary For the common case when character strings are used as keys, -the class \typ{CcuDictionnary} was derived from the class \typ{CcuHashTable}. +the class \typ{IvlDictionnary} was derived from the class \typ{IvlHashTable}. It is the class that should be used for dictionaries, symbol tables,~\ldots\, For this special kind of hash tables, keys are compared as strings, and are copied with the function \fun{NewString} (see page~\pageref{newstring}). If users do not provide a hash function, a default one is used. -All the functions of class \typ{CcuHashTable} are available in class \typ{CcuDictionnary}. -\typ{CcuHashCellIter}s and \typ{CcuHashIter}s can be used on \typ{CcuDictionnary}s as well. +All the functions of class \typ{IvlHashTable} are available in class \typ{IvlDictionnary}. +\typ{IvlHashCellIter}s and \typ{IvlHashIter}s can be used on \typ{IvlDictionnary}s as well. ?*/ /*? @@ -516,7 +507,7 @@ This function computes an integer key from a string. It is used by dictionaries a hashing function, and is provided to users for a possible reuse. ?*/ unsigned int -CcuDictionnary :: HashString (const void* key, int) +IvlDictionnary :: HashString (const void* key, int) { register int h = 0; register const char* p = (const char*) key; @@ -531,7 +522,7 @@ CcuDictionnary :: HashString (const void* key, int) /*?hidden?*/ int -CcuDictionnary :: CompareString (const void* a, const void* b) +IvlDictionnary :: CompareString (const void* a, const void* b) { register const char *p, *q; /* on fait le strcmp a la main : ca va + vite */ @@ -543,36 +534,36 @@ CcuDictionnary :: CompareString (const void* a, const void* b) /*?hidden?*/ void* -CcuDictionnary :: CopyString (const void* k) +IvlDictionnary :: CopyString (const void* k) { return NewString ((const char*) k); } /*?hidden?*/ void -CcuDictionnary :: DeleteString (const void* k) +IvlDictionnary :: DeleteString (const void* k) { FreeString ((char*) k); } /*? -Constructor for \typ{CcuDictionnary}s. Initialize a \typ{CcuDictionnary} with an array of size \var{size}, +Constructor for \typ{IvlDictionnary}s. Initialize a \typ{IvlDictionnary} with an array of size \var{size}, and \var{hash\_fun} as the hash function. If \var{hash\_fun} is not provided, the default function is used. ?*/ -CcuDictionnary :: CcuDictionnary (int size, HASH_F f) -: CcuHashTable (size, (f ? f : HashString), (HCP_F) (CopyString), (HDEL_F) (DeleteString), (HCMP_F) (CompareString)) +IvlDictionnary :: IvlDictionnary (int size, HASH_F f) +: IvlHashTable (size, (f ? f : HashString), (HCP_F) (CopyString), (HDEL_F) (DeleteString), (HCMP_F) (CompareString)) { } /*?nodoc?*/ -CcuDictionnary :: ~CcuDictionnary () +IvlDictionnary :: ~IvlDictionnary () { } /*?nodoc?*/ void -CcuDictionnary :: KeyCopy (int flag) +IvlDictionnary :: KeyCopy (int flag) { if (flag) { Copy = (HCP_F) (&CopyString); @@ -583,25 +574,25 @@ CcuDictionnary :: KeyCopy (int flag) } } -/*?class CcuHashCellIter -The class \typ{CcuHashCellIter} makes it possible to iterate through the entries of an hash table. +/*?class IvlHashCellIter +The class \typ{IvlHashCellIter} makes it possible to iterate through the entries of an hash table. The order of iteration is not specified. These iterators yield pointers to cells, so that keys -and entries are both accessible. To see only the entries, refer to the class \typ{CcuHashIter}. +and entries are both accessible. To see only the entries, refer to the class \typ{IvlHashIter}. ?*/ #ifdef DOC /*? -Constructor for \typ{CcuHashCellIter}s. Initialize an iterator on the hash table \var{t}. +Constructor for \typ{IvlHashCellIter}s. Initialize an iterator on the hash table \var{t}. ?*/ -CcuHashCellIter :: CcuHashCellIter (const CcuHashTable& t) +IvlHashCellIter :: IvlHashCellIter (const IvlHashTable& t) { } /*? Get the current cell pointed by an iterator. ?*/ -CcuHashCell* -CcuHashCellIter :: operator * () const +IvlHashCell* +IvlHashCellIter :: operator * () const { } #endif @@ -610,10 +601,10 @@ CcuHashCellIter :: operator * () const Take one step of iteration. This operator returns a pointer on the next hash entry of the table it is iterating on. When it is finished, it returns 0. ?*/ -CcuHashCellIter& -CcuHashCellIter :: operator ++ () +IvlHashCellIter& +IvlHashCellIter :: operator ++ () { - register CcuHashCell* h = 0; + register IvlHashCell* h = 0; register int size = TheTable.GetSize (); @@ -629,10 +620,10 @@ CcuHashCellIter :: operator ++ () /*? Post-increment equivalent of the previous operator. ?*/ -CcuHashCellIter -CcuHashCellIter :: operator ++ (int) +IvlHashCellIter +IvlHashCellIter :: operator ++ (int) { - CcuHashCellIter result = *this; + IvlHashCellIter result = *this; ++(*this); return result; } @@ -643,11 +634,11 @@ Get the status of an iterator. The status may be one of \var{Normal, StartOfTabl \var{EndOfTable} ?*/ #ifndef CPLUS_BUG13 -CcuHashCellIter::hashiter_status -CcuHashCellIter :: GetStatus () const +IvlHashCellIter::hashiter_status +IvlHashCellIter :: GetStatus () const #else hashiter_status -CcuHashCellIter :: GetStatus () const +IvlHashCellIter :: GetStatus () const #endif { if (CurCell) @@ -661,93 +652,93 @@ CcuHashCellIter :: GetStatus () const /*? Check whether the status of an iterator is \var{Normal}. ?*/ -CcuHashCellIter :: operator int () const +IvlHashCellIter :: operator int () const { } -/*?class CcuHashIter -\typ{CcuHashIter}s are iterators that yield entries and not cells. They only differ -from \typ{CcuHashCellIter}s by their operator \fun{*}. +/*?class IvlHashIter +\typ{IvlHashIter}s are iterators that yield entries and not cells. They only differ +from \typ{IvlHashCellIter}s by their operator \fun{*}. ?*/ /*? Get the current entry pointed by an iterator. ?*/ -CcuHashItem* -CcuHashIter :: operator * () const +IvlHashItem* +IvlHashIter :: operator * () const { } -/*?class CcuHashTableOf -The generic classes \typ{CcuHashTableOf, CcuHashCellOf, CcuHashCellIterOf} -and \typ{CcuHashIterOf} are derived classes of \typ{CcuHashTable, CcuHashCell, CcuHashCellIter} -and \typ{CcuHashIter} that provide hash tables whose entries are +/*?class IvlHashTableOf +The generic classes \typ{IvlHashTableOf, IvlHashCellOf, IvlHashCellIterOf} +and \typ{IvlHashIterOf} are derived classes of \typ{IvlHashTable, IvlHashCell, IvlHashCellIter} +and \typ{IvlHashIter} that provide hash tables whose entries are pointers to class objects. When parameterized by the class \typ{ITEM}, the following functions are redefined: ?*/ /*?nextdoc?*/ -CcuHashCellOf<ITEM>* -CcuHashTableOf :: Add (const void* key, int* found) +IvlHashCellOf<ITEM>* +IvlHashTableOf :: Add (const void* key, int* found) { } /*?nextdoc?*/ -CcuHashCellOf<ITEM>* -CcuHashTableOf :: Get (const void* key) +IvlHashCellOf<ITEM>* +IvlHashTableOf :: Get (const void* key) { } /*?nextdoc?*/ ITEM* -CcuHashTableOf :: Remove (const void* key, int* found) +IvlHashTableOf :: Remove (const void* key, int* found) { } /*? -These functions are equivalent to their homonyms in the class \typ{CcuHashTable}, +These functions are equivalent to their homonyms in the class \typ{IvlHashTable}, except that they are customized in order to manipulate pointers to \typ{ITEM} instead of \typ{void*}. ?*/ -CcuHashCellRefOf<ITEM> -CcuHashTableOf :: operator [] (const void* key) const +IvlHashCellRefOf<ITEM> +IvlHashTableOf :: operator [] (const void* key) const { } /*?nextdoc?*/ void -CcuHashCellOf :: SetInfo (ITEM* p) +IvlHashCellOf :: SetInfo (ITEM* p) { } /*? -These functions are equivalent to their homonyms in the class \typ{CcuHashCell}, +These functions are equivalent to their homonyms in the class \typ{IvlHashCell}, except that they are customized in order to manipulate pointers to \typ{ITEM} instead of \typ{void*}. ?*/ ITEM* -CcuHashCellOf :: GetInfo () const +IvlHashCellOf :: GetInfo () const { } /*?nextdoc?*/ -CcuHashIterOf :: CcuHashIterOf (const CcuHashTableOf<ITEM>& t) +IvlHashIterOf :: IvlHashIterOf (const IvlHashTableOf<ITEM>& t) { } /*?nextdoc?*/ -CcuHashIterOf<ITEM>& -CcuHashIterOf :: operator ++ () +IvlHashIterOf<ITEM>& +IvlHashIterOf :: operator ++ () { } /*? -These functions are equivalent to their homonyms in the class \typ{CcuHashIter}, +These functions are equivalent to their homonyms in the class \typ{IvlHashIter}, except that they are customized in order to manipulate pointers to \typ{ITEM} instead of \typ{void*}. ?*/ ITEM* -CcuHashIterOf :: operator * () const +IvlHashIterOf :: operator * () const { } |