From 2451f7f434fe53586ac3cd3e5859f061aeaf56b6 Mon Sep 17 00:00:00 2001 From: chatty Date: Wed, 22 Dec 1993 12:25:29 +0000 Subject: Changed algorithm of CcuDictionnary::HashString Simplified HashStats and CollStats Added CcuHashTable::HashWord for future use. changed arg of operator new replaced TRUE/FALSE by true/false --- utils/HashTable.cc | 78 ++++++++++++++++++++++++++++++------------------------ 1 file changed, 44 insertions(+), 34 deletions(-) diff --git a/utils/HashTable.cc b/utils/HashTable.cc index 98de9ce..4712f0f 100644 --- a/utils/HashTable.cc +++ b/utils/HashTable.cc @@ -18,6 +18,9 @@ #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. @@ -47,7 +50,7 @@ The following definitions are used by member functions of the class \typ{CcuHash and by them only: \index{HASH_F}\index{HCP_F}\index{HCMP_F}\index{HENUM_F}\index{HDEL_F} \begin{ccode} - typedef int (*HASH_F) (HashItem*, int); + typedef unsigned int (*HASH_F) (HashItem*, int); typedef pointer (*HCP_F) (HashItem*); typedef int (*HCMP_F) (HashItem*, HashItem*); typedef int (*HENUM_F) (HashCell*, HashItem*); @@ -70,7 +73,7 @@ CcuHashCell :: ClassInit () /*?nodoc?*/ void* -CcuHashCell :: operator new (unsigned int) +CcuHashCell :: operator new (unsigned long) { return HashCellMem->Alloc (); } @@ -82,7 +85,15 @@ 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 @@ -194,7 +205,7 @@ CcuHashTable :: HashKey (const void* key) const if (Hash) h = (*Hash) (key, Size); - + if (h >= Size) h %= Size; @@ -264,8 +275,8 @@ CcuHashCell :: SetInfo (CcuHashItem* p) /*? 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 +\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. @@ -404,30 +415,26 @@ CcuHashTable :: Resize (int size) #ifdef TUNE /*?nextdoc?*/ void -CcuHashTable :: HashStats (int fd) +CcuHashTable :: HashStats () { CcuHashCell * h; CcuHashCell **entry; - char msg[80]; int s, coll = 0, empty = 0; for (s = Size, entry = Table; s--; entry++) { if (h = *entry) { - sprintf (msg, "%s(%d)", h->Key, h->Info); - write (fd, msg, strlen (msg)); + fprintf (stderr, "%s(%d)", h->Key, h->Info); while (h = h->Next) { - sprintf (msg, "\t%s(%d)", h->Key, h->Info); - write (fd, msg, strlen (msg)); + fprintf (stderr, "\t%s(%d)", h->Key, h->Info); coll++; } - write (fd, "\n", 1); + fprintf (stderr, "\n"); } else { - write (fd, "\n", 8); + fprintf (stderr, "\n"); empty++; } } - sprintf (msg, "size : %d; %d empty; %d collisions\n", Size, empty, coll); - write (fd, msg, strlen (msg)); + fprintf (stderr, "size: %d; %d empty; %d collisions\n", Size, empty, coll); } /*? @@ -435,16 +442,15 @@ Print some statistics about this hash table on file descriptor \var{fd} (default is stderr). ?*/ void -CcuHashTable :: CollStats (int fd) +CcuHashTable :: CollStats () { CcuHashCell * h; CcuHashCell **entry; - char msg[80]; int s, lcoll, coll = 0, empty = 0; int min = 999999, max = 0, moy = 0, moy2 = 0; float fmoy, fvar; - for (s = Size, entry = (CcuHashCell**) Data; s--; entry++) { + for (s = Size, entry = (CcuHashCell**) Table; s--; entry++) { lcoll = 0; if (h = *entry) { while (h = h->Next) { @@ -465,10 +471,8 @@ CcuHashTable :: CollStats (int fd) } fmoy = ((float) moy) / ((float) Size); fvar = fmoy * fmoy - (((float) moy2) / ((float) Size)); - sprintf (msg, "size : %d; %d empty; %d collisions\n", Size, empty, coll); - write (fd, msg, strlen (msg)); - sprintf (msg, "min : %d; max %d; moy %f; variance %f\n----\n\n", min, max, fmoy, fvar); - write (fd, msg, strlen (msg)); + 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 */ @@ -507,21 +511,27 @@ All the functions of class \typ{CcuHashTable} are available in class \typ{CcuDic \typ{CcuHashCellIter}s and \typ{CcuHashIter}s can be used on \typ{CcuDictionnary}s as well. ?*/ - -/*?hidden?*/ -int -CcuDictionnary :: HashKey (const void* key, int) +/*? +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; + 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 :: CompareKey (const void* a, const void* b) +CcuDictionnary :: CompareString (const void* a, const void* b) { register const char *p, *q; /* on fait le strcmp a la main : ca va + vite */ @@ -533,14 +543,14 @@ CcuDictionnary :: CompareKey (const void* a, const void* b) /*?hidden?*/ void* -CcuDictionnary :: CopyKey (const void* k) +CcuDictionnary :: CopyString (const void* k) { return NewString ((const char*) k); } /*?hidden?*/ void -CcuDictionnary :: DeleteKey (void* k) +CcuDictionnary :: DeleteString (void* k) { FreeString ((char*) k); } @@ -551,7 +561,7 @@ and \var{hash\_fun} as the hash function. If \var{hash\_fun} is not provided, th function is used. ?*/ CcuDictionnary :: CcuDictionnary (int size, HASH_F f) -: CcuHashTable (size, (f ? f : HashKey), (HCP_F) (CopyKey), (HDEL_F) (DeleteKey), (HCMP_F) (CompareKey)) +: CcuHashTable (size, (f ? f : HashString), (HCP_F) (CopyString), (HDEL_F) (DeleteString), (HCMP_F) (CompareString)) { } @@ -565,8 +575,8 @@ void CcuDictionnary :: KeyCopy (int flag) { if (flag) { - Copy = (HCP_F) (&CopyKey); - Delete = (HDEL_F) &DeleteKey; + Copy = (HCP_F) (&CopyString); + Delete = (HDEL_F) &DeleteString; } else { Copy = 0; Delete = 0; -- cgit v1.1