# HG changeset patch
# User Sean Halle <seanhalle@yahoo.com>
# Date 1339030858 25200
# Node ID ac99f4a8ce223c4fefb6b68e8c7e0951fc9174ac
# Parent  f5972b1ddb2949cca17df4d75cbe3d358ddcd82a
First working version

diff -r f5972b1ddb29 -r ac99f4a8ce22 PrivateHash.c
--- a/PrivateHash.c	Tue Mar 13 18:31:05 2012 -0700
+++ b/PrivateHash.c	Wed Jun 06 18:00:58 2012 -0700
@@ -9,7 +9,7 @@
 #include "PrivateHash.h"
 
 
- HashTable *
+HashTable *
 makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn )
  { HashTable * retTable;
    retTable = VMS_int__malloc( sizeof( HashTable ) );
@@ -25,7 +25,23 @@
    return retTable;
  }
 
- void
+HashTable *
+makeHashTable_WL( int numHashSlots, FreeEntryContentFnPtr freeFn )
+ { HashTable * retTable;
+   retTable = VMS_WL__malloc( sizeof( HashTable ) );
+
+   retTable->freeEntryContentFn = freeFn;
+   
+   retTable->entries    = VMS_int__malloc( numHashSlots * sizeof(HashEntry *) );
+   retTable->numEntries = 0;
+   retTable->tableSz    = numHashSlots;
+
+   nullOutTablesArray( retTable );
+
+   return retTable;
+ }
+
+void
 doubleTableSize( HashTable *table )
  { int i, oldTableSz, newTableSz;
    HashEntry *entry, *nextEntry, **oldEntries, **newEntries;
@@ -33,7 +49,7 @@
    oldTableSz = table->tableSz;
    oldEntries = table->entries;
 
-   newTableSz = 2 * oldTableSz + 1;
+   newTableSz = 2 * oldTableSz;
    newEntries = VMS_int__malloc( newTableSz * sizeof(HashEntry *) );
 
    table->tableSz    = newTableSz;
@@ -45,7 +61,7 @@
     { if( oldEntries[i] != NULL )
        { entry = oldEntries[i];
          while( entry != NULL )
-          { nextEntry = entry->next;
+          { nextEntry = entry->next;  //save for later
             entry->next = NULL;
             putEntryIntoTable( entry, table ); //does not allocate anything
             entry = nextEntry;
@@ -74,17 +90,36 @@
    return h % hashSz;
  }
 
+/*Copies the string that is the key*/
+inline HashEntry *
+makeHashEntry( char * key )
+ { HashEntry *hashEntry;
+ 
+   int32 len = strlen(key);
+ 
+   hashEntry = (HashEntry*) VMS_int__malloc( sizeof( HashEntry ) );
+         if( hashEntry == NULL )  return NULL;
+   
+   hashEntry->key = VMS_int__malloc( len + 1 );
+         if( hashEntry->key == NULL ) return NULL;
+   memcpy( hashEntry->key, key, len + 1 );
+   hashEntry->next = NULL;
+   
+   return hashEntry;
+ }
+
+
 /*Need this to be separated out, for use in both getParam and putParam
  */
 HashEntry *
 getEntryFromTable( char *key, HashTable * table )
- {  unsigned int
+ {  uint32
    hashIndex = hashThisKey( key, table->tableSz );
     HashEntry*
    hashEntry = table->entries[ hashIndex ];
    for( ; hashEntry != NULL; hashEntry = hashEntry->next )
     {
-       if( memcmp( hashEntry->key, key, sizeof(hashkey_t) ) == 0 )
+       if( strcmp( hashEntry->key, key ) == 0 )
            return hashEntry;
     }
    return NULL;
@@ -99,7 +134,6 @@
    return entry->content;
  }
 
-
 /*If key already has a value, clobber the old one and replace it
  */
  int
@@ -110,11 +144,7 @@
    hashEntry = getEntryFromTable( key, table );
    if( hashEntry == NULL )
     { hashIdx = hashThisKey( key, table->tableSz );
-      hashEntry = (HashEntry*) VMS_int__malloc( sizeof( HashEntry ) );
-            if( hashEntry == NULL )  return 0;
-      hashEntry->key = VMS_int__malloc( sizeof(hashkey_t) );
-            if( hashEntry->key == NULL ) return 0;
-      memcpy( hashEntry->key, key, sizeof(hashkey_t) );
+      hashEntry = makeHashEntry( key );
       hashEntry->next = (table->entries)[hashIdx];
       (table->entries)[hashIdx] = hashEntry;
       table->numEntries += 1;
@@ -127,6 +157,7 @@
    return 1;
  }
 
+
  int
 putEntryIntoTable( HashEntry *entry, HashTable *table )
  { unsigned int hashIdx;
@@ -142,8 +173,8 @@
     }
    else
     { (*(table->freeEntryContentFn))( testEntry->content );
-         //being lazy -- will create bug in code that relies on having ptr to
-         // elem given to insert into table!
+         //being lazy -- will create bug in code that relies on having ptr
+         // to elem given to insert into table!
       testEntry->content = entry->content;
       entry->content = NULL;
       freeHashEntryButNotContent( entry );
@@ -161,7 +192,7 @@
    
    testEntry = table->entries[ hashIndex ];
    for( ; testEntry != NULL; testEntry = testEntry->next )
-    { if( memcmp( testEntry->key, entry->key, sizeof(hashkey_t)) == 0 )
+    { if( strcmp( testEntry->key, entry->key ) == 0 )
        { if( prevEntry == NULL )
           { table->entries[hashIndex] = entry;
             entry->next = testEntry->next;
@@ -180,27 +211,26 @@
  }
 
 
-
- bool8
+bool8
 deleteEntryFromTable( char *key, HashTable *table )
  { HashEntry  *hashEntry;
-   HashEntry **addrOfHashEntryPtr;
+   HashEntry **addrOfPrevPtr;
    unsigned int hashIndex;
 
    hashIndex = hashThisKey( key, table->tableSz );
-   addrOfHashEntryPtr = &( table->entries[ hashIndex ] );
-   hashEntry = *addrOfHashEntryPtr;
+   addrOfPrevPtr = &( table->entries[ hashIndex ] );//for removing node
+   hashEntry = *addrOfPrevPtr; //already did work, might as well use it
    while( hashEntry != NULL )
-    { if( memcmp( hashEntry->key, key, sizeof(hashkey_t) ) == 0 )
+    { if( strcmp( hashEntry->key, key ) == 0 )
        {
-         *addrOfHashEntryPtr = hashEntry->next;
+         *addrOfPrevPtr = hashEntry->next;  //remove node from list
          //TODO: Free the contents of entry?
          freeHashEntryButNotContent( hashEntry );
          table->numEntries -= 1;
          return TRUE;
        }
-      addrOfHashEntryPtr = &( hashEntry->next );
-      hashEntry = *addrOfHashEntryPtr;
+      addrOfPrevPtr = &( hashEntry->next );
+      hashEntry = *addrOfPrevPtr;
     }
    return FALSE;
  }
@@ -234,9 +264,247 @@
  }
 
 void
+freeHashEntryUsing_WL( HashEntry *entry, HashTable *table )
+ {
+   if( entry->content != NULL )
+      (*(table->freeEntryContentFn))( entry->content );
+   VMS_WL__free( entry->key ); //was VMS_int__malloc'd above, so free it
+   VMS_WL__free( entry );
+ }
+ 
+void
+freeHashTable_WL( HashTable *table )
+ { int i;
+   HashEntry *hashEntry, *temp, **entries;
+
+   entries = table->entries;
+   for( i=0; i < table->tableSz; i++ )
+    { if( entries[i] != NULL )
+       { hashEntry = entries[i];
+         while( hashEntry != NULL )
+          {
+            temp = hashEntry->next;
+            freeHashEntryUsing_WL( hashEntry, table );
+            hashEntry = temp;
+          }
+       }
+    }
+ }
+
+
+void
 freeHashEntryButNotContent( HashEntry *entry )
  {
    VMS_int__free( entry->key ); //was VMS_int__malloc'd above, so free it
    VMS_int__free( entry );
  }
 
+void
+freeHashEntryButNotContent_WL( HashEntry *entry )
+ {
+   VMS_WL__free( entry->key ); //was VMS_int__malloc'd above, so free it
+   VMS_WL__free( entry );
+ }
+
+
+
+
+//======================= 32 bit integer key version ======================
+
+/*key is array of uint32, with first entry being the num ints in key.
+ * that means size of key is content of first entry times 4, plus the
+ * size of first entry itself, which is another 4*/
+#define sizeOfKey(key) key[0]*4 + 4
+
+
+HashTable *
+makeHashTable32( int powerOf2OfSz, FreeEntryContentFnPtr freeFn )
+ { HashTable * retTable;
+   int32 numHashSlots;
+   
+   retTable = VMS_int__malloc( sizeof( HashTable ) );
+
+   numHashSlots = 1 << powerOf2OfSz;
+   retTable->hashMask   = 0xffffffff >> 32 - powerOf2OfSz;   
+   retTable->prevHash   = (int32)rand();
+   
+   retTable->freeEntryContentFn = freeFn;
+   
+   retTable->entries = VMS_int__malloc( numHashSlots * sizeof(HashEntry *));
+   retTable->numEntries = 0;
+   retTable->tableSz    = numHashSlots;
+
+   nullOutTablesArray( retTable );
+
+   return retTable;
+ }
+
+HashTable *
+makeDefaultSizeHashTable32( FreeEntryContentFnPtr freeFn )
+ {
+   return makeHashTable32( DEFAULT_POWER_OF_2_TABLE_SIZE, freeFn );
+ }
+
+HashEntry *
+makeHashEntry32( uint32 * key )
+ { HashEntry *hashEntry;
+ 
+   hashEntry = (HashEntry*) VMS_int__malloc( sizeof( HashEntry ) );
+         if( hashEntry == NULL )  return NULL;
+   hashEntry->key = VMS_int__malloc( sizeOfKey(key) );
+         if( hashEntry->key == NULL ) return NULL;
+   memcpy( hashEntry->key, key, sizeOfKey(key) );
+   hashEntry->next = NULL;
+   
+   return hashEntry;
+ }
+
+
+
+int32
+putEntryIntoTable32( HashEntry *entry, HashTable *table )
+ { unsigned int hashIdx;
+   HashEntry* testEntry;
+
+   testEntry = getEntryFromTable32( (uint32 *)entry->key, table );
+   if( testEntry == NULL ) //no entry w/key, so add passed-in as list-head
+    { hashIdx = hashThisKey32( entry->key, table->tableSz );
+      entry->next = (table->entries)[hashIdx];
+      (table->entries)[hashIdx] = entry;
+      table->numEntries += 1;
+         //keep num entries less than half the num indexes in table
+      if( table->numEntries > (table->tableSz >>1) ) doubleTableSize(table);
+    }
+   else //entry w/key already exists, so free content, then replace then
+        // free the passed-in entry, leaving the entry already in table
+    { (*(table->freeEntryContentFn))( testEntry->content );
+         //being lazy -- will create bug in code that relies on having ptr
+         // to elem given to insert into table!
+      testEntry->content = entry->content;
+      entry->content = NULL;
+      freeHashEntryButNotContent( entry );
+    }
+   return 1;
+ }
+
+
+void
+doubleTableSize32( HashTable *table )
+ { int i, oldTableSz, newTableSz;
+   HashEntry *entry, *nextEntry, **oldEntries, **newEntries;
+
+   oldTableSz = table->tableSz;
+   oldEntries = table->entries;
+
+   newTableSz = 2 * oldTableSz;
+   newEntries = VMS_int__malloc( newTableSz * sizeof(HashEntry *) );
+
+   table->tableSz    = newTableSz;
+   table->entries    = newEntries;
+   table->numEntries = 0; //about to add them all back!
+
+      // move all the entries from old to new
+   for( i=0; i < oldTableSz; i++ )
+    { if( oldEntries[i] != NULL )
+       { entry = oldEntries[i];
+         while( entry != NULL )
+          { nextEntry = entry->next;  //save for later
+            entry->next = NULL;       //null before, so can chain in new
+            putEntryIntoTable32( entry, table ); //doesn't allocate anything
+            entry = nextEntry;
+          }
+       }
+    }
+ }
+
+/*The key is a self-sized array of 32 bit unsigned ints, with the first
+ * entry being the number of ints in the key, which makes up the rest of
+ * the array.*/
+int32
+hashThisKey32( uint32 *key, HashTable *hashTable )
+ { int32 hashOfKey;
+ 
+      //the hash function takes addr of start of key array, plus num int32s,
+   hashOfKey = jenkHash32( &key[1], *key );
+   hashTable->prevHash = hashOfKey;
+   
+   /*The hash is a full 32 bits, but only want hashes that fall within
+    * the size of the table.  So, mask off the higher bits. */
+   return ( hashTable->hashMask & hashOfKey ); //reduce to size of table
+ }
+
+
+/*The first entry of key says the size of the key, while key itself is the
+ * rest of the integers in the array
+ */
+HashEntry *
+getEntryFromTable32( uint32 *key, HashTable * table )
+ {  unsigned int
+   hashIndex = hashThisKey32( key, table );
+    HashEntry*
+   hashEntry = table->entries[ hashIndex ];
+   for( ; hashEntry != NULL; hashEntry = hashEntry->next )
+    {
+       if( memcmp( hashEntry->key, key, sizeOfKey(key) ) == 0 )
+           return hashEntry;
+    }
+   return NULL;
+ }
+
+void *
+getValueFromTable32( uint32 *key, HashTable * table )
+ { HashEntry *entry;
+   entry = getEntryFromTable32( key, table );
+   if( entry == NULL ) return NULL;
+
+   return entry->content;
+ }
+
+/*Returns NULL if failed to insert, else returns ptr to hash entry */
+HashEntry *
+addValueIntoTable32( uint32* key, void *content, HashTable *table )
+ { unsigned int hashIdx;
+   HashEntry* hashEntry;
+
+   hashEntry = getEntryFromTable32( key, table );
+   if( hashEntry == NULL )
+    { hashIdx   = hashThisKey32( key, table );
+      hashEntry = makeHashEntry32( key );
+      hashEntry->next = (table->entries)[hashIdx];
+      (table->entries)[hashIdx] = hashEntry;
+      table->numEntries += 1;
+         //Check if need to make bigger -- keep half-full (hence ">> 1")
+      if( table->numEntries > table->tableSz >>1 ) doubleTableSize( table );
+    }
+   else
+    { (*(table->freeEntryContentFn))( hashEntry->content );
+    }
+   hashEntry->content = content;
+   return hashEntry;
+ }
+
+
+bool32
+deleteEntryFromTable32( uint32 *key, HashTable *table )
+ { HashEntry   *hashEntry;
+   HashEntry  **addrOfPrevPtr;
+   unsigned int hashIndex;
+
+   hashIndex = hashThisKey32( key, table );
+   hashEntry = table->entries[ hashIndex ];
+      //go down the chained list, checking all with this hash value
+   addrOfPrevPtr = &( table->entries[hashIndex] ); //for removing a node
+   hashEntry = *addrOfPrevPtr;  //did ptr chasing, might as well use it
+   while( hashEntry != NULL )
+    { if( memcmp( hashEntry->key, key, sizeOfKey(key) ) == 0 )
+       { *addrOfPrevPtr = hashEntry->next; //remove node from list
+         freeHashEntryButNotContent( hashEntry );
+         table->numEntries -= 1;
+         return TRUE;
+       }
+      addrOfPrevPtr = &(hashEntry->next); //chg content of *this* to remove
+      hashEntry     = *addrOfPrevPtr;     //cheaper than hashEntry->next
+    }
+   return FALSE;
+ }
+
diff -r f5972b1ddb29 -r ac99f4a8ce22 PrivateHash.h
--- a/PrivateHash.h	Tue Mar 13 18:31:05 2012 -0700
+++ b/PrivateHash.h	Wed Jun 06 18:00:58 2012 -0700
@@ -16,9 +16,15 @@
 #include "VMS_impl/VMS_primitive_data_types.h"
 #include "VMS_impl/Services_Offered_by_VMS/Memory_Handling/vmalloc.h"
 
+//=====================  defines  =====================
 #define TRUE     1
 #define FALSE    0
 
+#define DEFAULT_HASH_TABLE_SIZE 1 << 10
+#define DEFAULT_POWER_OF_2_TABLE_SIZE 10
+
+
+//=====================  structs  =====================
 union hashkey_t{
     char hashable[8];
     int  parts[2];
@@ -26,8 +32,6 @@
 
 typedef union hashkey_t hashkey_t;
 
-#define DEFAULT_HASHSIZE 1 << 10
-
 typedef struct _HashEntry HashEntry;
 
 struct _HashEntry
@@ -40,9 +44,11 @@
 typedef void (*FreeEntryContentFnPtr)    ( void * );
 
 typedef struct
- { int tableSz;
-   int numEntries;
+ { int         tableSz;
+   int         numEntries;
    HashEntry* *entries;
+   int32       hashMask;
+   int32       prevHash;
    FreeEntryContentFnPtr freeEntryContentFn;
  }
 HashTable;
@@ -64,6 +70,17 @@
 void         freeHashTable( HashTable *table );
 //char        *paramBagToString( ParamBag * bag )
 
+//================= Same Fns, but for 32b array key hash fn ================
+HashTable *makeHashTable32(int32 powerOf2OfSz, FreeEntryContentFnPtr freeFn);
+HashTable *makeDefaultSizeHashTable32( FreeEntryContentFnPtr freeFn );
+
+int        putEntryIntoTable32( HashEntry *entry, HashTable *table);
+HashEntry *addValueIntoTable32( uint32 key[], void *value, HashTable *table);
+HashEntry *getEntryFromTable32( uint32 key[], HashTable *table );
+void      *getValueFromTable32( uint32 key[], HashTable *table );
+
+bool32     deleteEntryFromTable32( uint32 key[], HashTable *table );
+
 //===========================================================================
 //   Internal functions
 void         freeHashEntryUsing( HashEntry *entry, HashTable *table );
@@ -72,5 +89,9 @@
 void         doubleTableSize( HashTable *table );
 void         freeHashEntryButNotContent( HashEntry *entry );
 
+uint32 
+jenkHash32( const uint32  *key,     /* array of uint32 values */
+                   int32   length);  /* num uint32 in the key */
+        
 #endif	/* _PRIVATE_HASH_H */