Index: /trunk/psLib/src/sysUtils/Makefile
===================================================================
--- /trunk/psLib/src/sysUtils/Makefile	(revision 493)
+++ /trunk/psLib/src/sysUtils/Makefile	(revision 494)
@@ -3,6 +3,6 @@
 ##  Makefile:   sysUtils
 ##
-##  $Revision: 1.4 $  $Name: not supported by cvs2svn $
-##  $Date: 2004-04-20 23:51:06 $
+##  $Revision: 1.5 $  $Name: not supported by cvs2svn $
+##  $Date: 2004-04-21 19:02:28 $
 ##
 ##  Copyright 2004 Maui High Performance Computing Center, University of Hawaii
@@ -35,4 +35,5 @@
            psTrace.o     \
            psLogMsg.o     \
+           psHash.o     \
            psAbort.o     \
            psString.o
Index: /trunk/psLib/src/sysUtils/psHash.c
===================================================================
--- /trunk/psLib/src/sysUtils/psHash.c	(revision 494)
+++ /trunk/psLib/src/sysUtils/psHash.c	(revision 494)
@@ -0,0 +1,235 @@
+/******************************************************************************
+    An interface to hash tables for Pan-STARRS
+ 
+    Collisions are handled by simple linked lists
+ *****************************************************************************/
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+//#include "psLib.h"
+#include "psHash.h"
+#include "psMemory.h"
+#include "psString.h"
+#include "psTrace.h"
+
+// A bucket that holds an item of data
+typedef struct HashBucket
+{
+    char *key;    // key for this item of data
+    void *data;    // the data itself
+    struct HashBucket *next;  // list of other possible keys
+}
+HashBucket;
+
+// An entire hash table
+struct HashTable
+{
+    int nbucket;   // number of buckets
+    HashBucket **buckets;  // the buckets themselves
+};
+
+/******************************************************************************
+    Con/Destruct buckets
+ *****************************************************************************/
+static HashBucket *hashBucketAlloc(const char *key,
+                                   void *data,
+                                   HashBucket *next)
+{
+    HashBucket *bucket = psAlloc(sizeof(HashBucket));
+
+    bucket->key = psStringCopy(key);
+    bucket->data = psMemIncrRefCounter(data);
+    bucket->next = next;
+
+    return bucket;
+}
+
+/******************************************************************************
+ 
+ *****************************************************************************/
+static void hashBucketFree(
+    HashBucket *bucket,   // bucket to free
+    void (*itemFree)(void *item)) // how to free hashed data;
+// or NULL
+{
+    if (bucket == NULL)
+    {
+        return;
+    }
+
+    psFree(bucket->key);
+    psMemDecrRefCounter(bucket->data);
+
+    if (itemFree != NULL)
+    {
+        itemFree(bucket->data);
+    }
+
+    psFree(bucket);
+}
+
+/******************************************************************************
+    Con/Destruct psHash tables
+ *****************************************************************************/
+psHash *psHashAlloc(int nbucket) // initial number of buckets
+{
+    psHash *table = psAlloc(sizeof(psHash));
+    table->buckets = psAlloc(nbucket*sizeof(HashBucket *));
+    table->nbucket = nbucket;
+
+    psTrace("utils.hash", 1, "Creating %d-element hash table\n", nbucket);
+
+    for (int i = 0; i < nbucket; i++)
+    {
+        table->buckets[i] = NULL;
+    }
+
+    return table;
+}
+
+/******************************************************************************
+ 
+ *****************************************************************************/
+void psHashFree(psHash *table,  // hash table to be freed
+                void (*itemFree)(void *item)) // how to free hashed data; or NULL
+{
+    if (table == NULL)
+    {
+        return;
+    }
+    /*
+     * Release data interned on the list, and delete the buckets
+     */
+    for (int i = 0; i < table->nbucket; i++)
+    {
+        if (table->buckets[i] != NULL) {
+            HashBucket *ptr = table->buckets[i];
+            while (ptr != NULL) {
+                HashBucket *tmp = ptr->next;
+                hashBucketFree(ptr, itemFree);
+                ptr = tmp;
+            }
+        }
+    }
+
+    psFree(table->buckets);
+    psFree(table);
+}
+
+/******************************************************************************
+    Here's the routine to do the work of insertion/retrieval/removal
+ 
+    We need itemFree if the key is already in use and we're inserting
+ 
+    N.b. this is NOT a good hash function! See Knuth for some better ones
+ *****************************************************************************/
+static void *doHashWork(
+    psHash *table,   // table to insert in
+    const char *key,   // key to use
+    void *data,    // data to insert,
+    // or (if NULL) retrieve/remove
+    int remove
+        ,    // remove the item from the list?
+        void (*itemFree)(void *item)) // how to free hashed data
+    // or NULL
+{
+    long int hash = 1;
+
+    for (int i = 0, len = strlen(key); i < len; i++) {
+        hash = (hash << 1) ^ key[i];
+    }
+
+    hash &= (table->nbucket - 1);
+
+    HashBucket *ptr = table->buckets[hash];
+    /*
+     * We've found the correct hash bucket, now we need to know what to do
+     */
+    if (data == NULL) {   // retrieve/remove
+        if (remove
+           ) {
+            HashBucket *optr = ptr;
+            while (ptr != NULL) {
+                if (strcmp(key, ptr->key) == 0) { // found it!
+                    void *data = ptr->data;
+                    optr->next = ptr->next;
+
+                    if (ptr == table->buckets[hash]) {
+                        table->buckets[hash] = ptr->next;
+                    }
+
+                    psFree(ptr->key);
+                    psFree(ptr);
+
+                    return psMemDecrRefCounter(data); // return data
+                }
+
+                optr = ptr;
+                ptr = ptr->next;
+            }
+        }
+        else {
+            while (ptr != NULL) {
+                if (strcmp(key, ptr->key) == 0) { // found it!
+                    return ptr->data;
+                }
+
+                ptr = ptr->next;
+            }
+        }
+
+        return NULL;   // not in hash
+    } else {    // insert
+        while (ptr != NULL) {
+            if (strcmp(key, ptr->key) == 0) { // found it!
+                if (itemFree == NULL) {
+                    return NULL; // can't insert
+                }
+
+                psTrace("utils.hash.insert", 3, "Replacing data for %s\n",
+                        key);
+
+                itemFree(psMemDecrRefCounter(ptr->data));
+                ptr->data = psMemIncrRefCounter(data);
+
+                return data;
+            }
+        }
+        /*
+         * Not found, so insert at the front of the list
+         */
+        table->buckets[hash] = hashBucketAlloc(key, data, table->buckets[hash]);
+
+        return data;
+    }
+}
+
+/******************************************************************************
+    Insert a value into a hash table
+ *****************************************************************************/
+void *psHashInsert(psHash *table, // table to insert in
+                   const char *key, // key to use
+                   void *data,  // data to insert
+                   void (*itemFree)(void *item)) // how to free hashed data;
+// or NULL
+{
+    return doHashWork(table, key, data, 0, itemFree);
+}
+
+/******************************************************************************
+    Lookup a value in a hash table
+ *****************************************************************************/
+void *psHashLookup(psHash *table, // table to lookup key in
+                   const char *key) // key to lookup
+{
+    return doHashWork(table, key, NULL, 0, NULL);
+}
+
+/******************************************************************************
+    Remove and return a value from a hash table
+ *****************************************************************************/
+void *psHashRemove(psHash *table, // table to lookup key in
+                   const char *key) // key to lookup
+{
+    return doHashWork(table, key, NULL, 1, NULL);
+}
Index: /trunk/psLib/src/sysUtils/psHash.h
===================================================================
--- /trunk/psLib/src/sysUtils/psHash.h	(revision 494)
+++ /trunk/psLib/src/sysUtils/psHash.h	(revision 494)
@@ -0,0 +1,44 @@
+#if !defined(PS_HASH_H)
+#define PS_HASH_H
+
+/** \file psHash.h
+ *  \brief Hash Table manipulation
+ *  \ingroup DataGroup
+ */
+
+/** DO WE NEED TO DEFINE HashTable? */
+typedef struct HashTable psHash; ///< Opaque type for a hash table
+
+/** Functions **************************************************************/
+/** \addtogroup DataGroup General Data Container Utilities
+ *  \{
+ */
+
+/// Allocate hash buckets in table.
+psHash *psHashAlloc(int nbucket);
+
+/// Free hash buckets from table.
+void psHashFree(psHash *table,  ///< hash table to be freed
+                void (*itemFree)(void *item) ///< how to free hashed data; or NULL
+               );
+
+/// Insert entry into table.
+void *psHashInsert(psHash *table, ///< table to insert in
+                   const char *key, ///< key to use
+                   void *data,  ///< data to insert
+                   void (*itemFree)(void *item) ///< how to free hashed data; or NULL
+                  );
+
+/// Lookup key in table.
+void *psHashLookup(psHash *table, ///< table to lookup key in
+                   const char *key ///< key to lookup
+                  );
+
+/// Remove key from table.
+void *psHashRemove(psHash *table, ///< table to lookup key in
+                   const char *key ///< key to lookup
+                  );
+
+/* \} */ // End of DataGroup Functions
+
+#endif