Changeset 889 for trunk/psLib/src/sysUtils/psHash.c

Timestamp:

Jun 6, 2004, 2:32:53 PM (22 years ago)

Author:

gusciora

Message:

Lots of bug fixes and such.

File:

• trunk/psLib/src/sysUtils/psHash.c (modified) (3 diffs)

trunk/psLib/src/sysUtils/psHash.c

@@ -1 @@
-/******************************************************************************
-    An interface to hash tables for Pan-STARRS
- 
-    Collisions are handled by simple linked lists
- *****************************************************************************/
+/** @file  psHash.c
+ *
+ *  @brief Contains support for basic hashing functions.
+ *
+ *  This file will hold the functions for defining a hash table with arbitrary
+ *  data types, allocating/deallocating that has table, adding and removing
+ *  data from that hash table, and listing all keys defined in the hash table.
+ *
+ *  @author Robert Lupton, Princeton University
+ *  @author George Gusciora, MHPCC
+ *   
+ *  @version $Revision: 1.6 $ $Name: not supported by cvs2svn $
+ *  @date $Date: 2004-06-07 00:32:53 $
+ *
+ *  Copyright 2004 Maui High Performance Computing Center, University of Hawaii
+ */
 #include <stdlib.h>
 #include <stdio.h>
@@ -12 +23 @@
 #include "psString.h"
 #include "psTrace.h"
+#include "psAbort.h"
 
 psDlist *psHashKeyList(psHash *table)
@@ -142 +154 @@
     // bucket.
     psHashBucket *optr = NULL;
+    char *tmpchar = NULL;
 
     // NOTE: this is NOT a good hash function!  See Knuth.
     //
-    for (int i = 0, len = strlen(key); i < len; i++) {
-        hash = (hash << 1) ^ key[i];
-    }
-    hash &= (table->nbucket - 1);
+    //    for (int i = 0, len = strlen(key); i < len; i++) {
+    //        hash = (hash << 1) ^ key[i];
+    //    }
+    //    hash &= (table->nbucket - 1);
+
+    // This hash algorithm is from Sedgewick.  NOTE: must reread to ensure that
+    // the size of the hash table is not required to be a prime number.
+    tmpchar = (char *) key;
+    for (hash = 0; *tmpchar != '\0'; tmpchar++) {
+        hash = (64 * hash + *tmpchar) % (table->nbucket);
+    }
+
+    // NOTE: This should not be necessary, but for now, I'm checking bounds
+    // anyway.
+    if ((hash < 0) ||
+            (hash >= table->nbucket)) {
+        psAbort(__func__,"Internal hash function out of range (%d)",
+                hash);
+    }
 
     ptr = table->buckets[hash];