/* * CENA C++ Utilities * * by Stephane Chatty * * Copyright 1991, 1992 * Laboratoire de Recherche en Informatique (LRI) * Centre d'Etudes de la Navigation Aerienne (CENA) * * plain and generic hash tables and dictionnaries * (Original C version by Michel Beaudouin-Lafon) * * $Id$ * $CurLog$ */ #include #include "String.h" #include "HashTable.h" #include "Allocator.h" #ifdef TUNE #include #endif /*?class CcuHashTable The class \typ{CcuHashTable} 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}), 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 a hash table, as they can be found in any book about algorithms. Figure~\ref{FIGURES/hash} is only here as a reminder. \fig{FIGURES/hash}{Internals of a hash table} 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 \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}, and by them only: \index{HASH_F}\index{HCP_F}\index{HCMP_F}\index{HENUM_F}\index{HDEL_F} \begin{ccode} typedef unsigned int (*HASH_F) (HashItem*, int); typedef pointer (*HCP_F) (HashItem*); typedef int (*HCMP_F) (HashItem*, HashItem*); typedef int (*HENUM_F) (HashCell*, HashItem*); typedef void (*HDEL_F) (HashCell*); \end{ccode} ?*/ CcuAllocator* CcuHashCell::HashCellMem = 0; /*?hidden?*/ void CcuHashCell :: ClassInit () { if (!HashCellMem) HashCellMem = new CcuAllocator (sizeof (CcuHashCell)); } /*?nodoc?*/ void* CcuHashCell :: operator new (unsigned long) { return HashCellMem->Alloc (); } /*?nodoc?*/ void CcuHashCell :: operator delete (void* that) { HashCellMem->Free (that); } #if 0 unsigned int CcuHashTable :: HashPtr (const void* p, int max) { /* stolen from Tcl */ /* this would be easier if max was a power of 2 */ return ((long)(p) * 1103515245) >> (30 - ffs (max)); } #endif /*? Constructor for \typ{CcuHashTable}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) : Size (size), Hash (hash_fun), Copy (cp_fun), Delete (del_fun), Compare (cmp_fun) { if (Size <= 0) Size = 1; Table = new CcuHashCell* [Size]; memset (Table, 0, Size*sizeof (CcuHashCell*)); /* I know that HashCells can only be created from HashTables */ if (!CcuHashCell::HashCellMem) CcuHashCell::ClassInit (); } /*? Copy constructor for hash tables. The table and the cells are copied. The keys are 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) : 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; while (p < Table + Size) { *p = 0; register CcuHashCell* r = *q; while (r) { (*p) = new CcuHashCell (Copy ? (*Copy) (r->GetKey ()) : r->GetKey (), *p); (*p)->SetInfo (r->Info); r = r->Next; } ++p; ++q; } } /*? Destructor for hash tables. All keys are destroyed if a destruction function was provided. ?*/ CcuHashTable :: ~CcuHashTable () { Clear (); #ifdef CPLUS_BUG4 delete [Size] Table; #else delete [] Table; #endif } /*? Remove all data from the hash table. All keys are destroyed if a destruction function was provided. ?*/ void CcuHashTable :: Clear () { /* destroy keys */ if (Delete) { CcuHashCellIter hi (*this); while (++hi) (*Delete) ((*hi)->Key); } /* destroy cells */ int s = Size; CcuHashCell** entry = Table; /* for each slot of the array ... */ for ( ; s--; ++entry ) { if (! *entry) continue; /* ... destroy all cells linked from that slot ...*/ for (CcuHashCell* h = *entry; h;) { CcuHashCell* del = h; h = h->Next; delete del; } /* ... and clear it */ *entry = 0; } } /*?hidden?*/ CcuHashCell** CcuHashTable :: HashKey (const void* key) const { register unsigned int h = (unsigned int) key; if (Hash) h = (*Hash) (key, Size); if (h >= Size) h %= Size; return (Table + h); } /*?hidden?*/ CcuHashCell* CcuHashTable :: FindCell (CcuHashCell** entry, const void* key) const { CcuHashCell* h; for (h = *entry; h; h = h -> Next) if (Compare ? (*Compare) (key, h->Key) : (key == h->Key)) break; return h; } /*?hidden?*/ CcuHashCell* CcuHashTable :: AddCell (CcuHashCell** entry, const void* key) const { if (Copy) key = (* Copy) (key); CcuHashCell* h = new CcuHashCell (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. ?*/ #ifdef DOC /*?hidden?*/ CcuHashCellOf :: CcuHashCell (const void*, CcuHashCell*) { } /*?nextdoc?*/ const void* CcuHashCell :: GetKey () const { } /*? Retrieve the key, or the information from a \typ{CcuHashCell}. ?*/ CcuHashItem* CcuHashCell :: GetInfo () const { } /*? Set the cell information to \var{p}. ?*/ void CcuHashCell :: SetInfo (CcuHashItem* p) { } #endif /*? Add the key \var{key} into the table. If \var{found} is not 0, it is a return parameter which contains true if the key was already in the table, or false if it was new. In both cases, the 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) { /* est-il dans la table ? */ CcuHashCell** entry = HashKey (key); CcuHashCell* h = FindCell (entry, key); if (found) *found = (h != 0); if (h) return h; return AddCell (entry, key); } /*? 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) { CcuHashCell **entry = HashKey (key); return FindCell (entry, key); } #if 0 CcuHashItem*& CcuHashTable :: operator [] (const void* key) { CcuHashCell **entry = HashKey (key); CcuHashCell *h = FindCell (entry, key); if (!h) h = AddCell (entry, key); return h->Info; } #else /*? Get a reference to the data stored in the table for the key \var{key}. That 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 { return CcuHashCellRef (*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) { CcuHashCell **entry; register CcuHashCell *h, *hp = 0; CcuHashItem* info = 0; entry = HashKey (key); for (h = *entry; h; h = h->Next) { if (Compare ? (*Compare) (key, h->Key) : (key == h->Key)) { /* remove it from the list */ if (hp) hp->Next = h->Next; else *entry = h->Next; /* free it, sparing its info */ if (Delete) (*Delete) (h->Key); info = h->Info; delete h; break; } hp = h; } if (found) *found = (h != 0); return info; } /*? Change the size of the table, which is re-hashed. ?*/ void CcuHashTable :: 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*)); /* rehash */ for (; s--; ++entry) { /* scan the list */ register CcuHashCell *cur, *next; for (cur = *entry; cur; cur = next) { next = cur->Next; register CcuHashCell** slot = HashKey (cur->Key); /* prepend the cell to the corresponding list */ cur->Next = *slot; *slot = cur; } } #ifdef CPLUS_BUG4 delete [Size] old_table; #else delete [] old_table; #endif } #ifdef TUNE /*?nextdoc?*/ void CcuHashTable :: HashStats () { CcuHashCell * h; CcuHashCell **entry; int s, coll = 0, empty = 0; for (s = Size, entry = Table; s--; entry++) { if (h = *entry) { fprintf (stderr, "%s(%d)", h->Key, h->Info); while (h = h->Next) { fprintf (stderr, "\t%s(%d)", h->Key, h->Info); coll++; } fprintf (stderr, "\n"); } else { fprintf (stderr, "\n"); empty++; } } fprintf (stderr, "size: %d; %d empty; %d collisions\n", Size, empty, coll); } /*? Print some statistics about this hash table on file descriptor \var{fd} (default is stderr). ?*/ void CcuHashTable :: CollStats () { CcuHashCell * h; CcuHashCell **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++) { lcoll = 0; if (h = *entry) { while (h = h->Next) { coll++, lcoll++; } /* sprintf (msg, "%d colls\n", lcoll); write (fd, msg, strlen (msg)); */ moy += lcoll; moy2 += lcoll * lcoll; if (lcoll < min) min = lcoll; if (lcoll > max) max = lcoll; } else { /* write (fd, "\n", 8); */ empty++; } } fmoy = ((float) moy) / ((float) Size); fvar = fmoy * fmoy - (((float) moy2) / ((float) Size)); fprintf (stderr, "size : %d; %d empty; %d collisions\n", Size, empty, coll); fprintf (stderr, "min : %d; max %d; moy %f; variance %f\n----\n\n", min, max, fmoy, fvar); } #endif /* TUNE */ CcuHashItem* CcuHashCellRef :: operator = (CcuHashItem* info) { CcuHashCell **entry = Table.HashKey (Key); CcuHashCell *h = Table.FindCell (entry, Key); if (!h) h = Table.AddCell (entry, Key); h->SetInfo (info); return info; } CcuHashCellRef :: operator CcuHashItem* () { CcuHashCell **entry = Table.HashKey (Key); CcuHashCell *h = Table.FindCell (entry, Key); return h ? h->GetInfo () : 0; } /*?class CcuDictionnary For the common case when character strings are used as keys, the class \typ{CcuDictionnary} was derived from the class \typ{CcuHashTable}. 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. ?*/ /*? This function computes an integer key from a string. It is used by dictionaries as a hashing function, and is provided to users for a possible reuse. ?*/ unsigned int CcuDictionnary :: HashString (const void* key, int) { register int h = 0; register const char* p = (const char*) key; while (*p) #if 0 h ^= *p++; #else h += (h << 3) + *p++; /* this hash function was stolen from Tcl */ #endif return h; } /*?hidden?*/ int CcuDictionnary :: CompareString (const void* a, const void* b) { register const char *p, *q; /* on fait le strcmp a la main : ca va + vite */ for (p = (const char *) a, q = (const char *) b; *p == *q++; p++) if (*p == '\0') return 1; return 0; } /*?hidden?*/ void* CcuDictionnary :: CopyString (const void* k) { return NewString ((const char*) k); } /*?hidden?*/ void CcuDictionnary :: DeleteString (void* k) { FreeString ((char*) k); } /*? Constructor for \typ{CcuDictionnary}s. Initialize a \typ{CcuDictionnary} 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)) { } /*?nodoc?*/ CcuDictionnary :: ~CcuDictionnary () { } /*?nodoc?*/ void CcuDictionnary :: KeyCopy (int flag) { if (flag) { Copy = (HCP_F) (&CopyString); Delete = (HDEL_F) &DeleteString; } else { Copy = 0; Delete = 0; } } /*?class CcuHashCellIter The class \typ{CcuHashCellIter} 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}. ?*/ #ifdef DOC /*? Constructor for \typ{CcuHashCellIter}s. Initialize an iterator on the hash table \var{t}. ?*/ CcuHashCellIter :: CcuHashCellIter (const CcuHashTable& t) { } /*? Get the current cell pointed by an iterator. ?*/ CcuHashCell* CcuHashCellIter :: operator * () const { } #endif /*? 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 ++ () { register CcuHashCell* h = 0; register int size = TheTable.GetSize (); if (!CurCell || !(h = CurCell->Next)) while ((++CurIndex < size) && !(h = (TheTable.Table [CurIndex]))) ; CurCell = h; return *this; } #ifndef CPLUS_BUG16 /*? Post-increment equivalent of the previous operator. ?*/ CcuHashCellIter CcuHashCellIter :: operator ++ (int) { CcuHashCellIter result = *this; ++(*this); return result; } #endif /*? Get the status of an iterator. The status may be one of \var{Normal, StartOfTable}, or \var{EndOfTable} ?*/ #ifndef CPLUS_BUG13 CcuHashCellIter:: #endif hashiter_status CcuHashCellIter :: Status () const { if (CurCell) return Normal; if (CurIndex < 0) return StartOfTable; return EndOfTable; } #ifdef DOC /*? Check whether the status of an iterator is \var{Normal}. ?*/ CcuHashCellIter :: 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{*}. ?*/ /*? Get the current entry pointed by an iterator. ?*/ CcuHashItem* CcuHashIter :: 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 pointers to class objects. When parameterized by the class \typ{ITEM}, the following functions are redefined: ?*/ /*?nextdoc?*/ CcuHashCellOf* CcuHashTableOf :: Add (const void* key, int* found) { } /*?nextdoc?*/ CcuHashCellOf* CcuHashTableOf :: Get (const void* key) { } /*?nextdoc?*/ ITEM* CcuHashTableOf :: Remove (const void* key, int* found) { } /*? These functions are equivalent to their homonyms in the class \typ{CcuHashTable}, except that they are customized in order to manipulate pointers to \typ{ITEM} instead of \typ{void*}. ?*/ CcuHashCellRefOf CcuHashTableOf :: operator [] (const void* key) const { } /*?nextdoc?*/ void CcuHashCellOf :: SetInfo (ITEM* p) { } /*? These functions are equivalent to their homonyms in the class \typ{CcuHashCell}, except that they are customized in order to manipulate pointers to \typ{ITEM} instead of \typ{void*}. ?*/ ITEM* CcuHashCellOf :: GetInfo () const { } /*?nextdoc?*/ CcuHashIterOf :: CcuHashIterOf (const CcuHashTableOf& t) { } /*?nextdoc?*/ CcuHashIterOf& CcuHashIterOf :: operator ++ () { } /*? These functions are equivalent to their homonyms in the class \typ{CcuHashIter}, except that they are customized in order to manipulate pointers to \typ{ITEM} instead of \typ{void*}. ?*/ ITEM* CcuHashIterOf :: operator * () const { } #endif