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

1 files 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 <stdio.h>
+#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, "<EMPTY>\n", 8);
+			fprintf (stderr, "<EMPTY>\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;