/*
 *  Copyright 2009 OpenSourceStewardshipFoundation.org
 *  Licensed under GNU General Public License version 2
 *
 *
 * Author: seanhalle@yahoo.com
 */

#include "PrivateHash.h"


HashTable *
makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn )
 { HashTable * retTable;
   retTable = VMS_int__malloc( sizeof( HashTable ) );

   retTable->freeEntryContentFn = freeFn;
   
   retTable->entries    = VMS_int__malloc( numHashSlots * sizeof(HashEntry *) );
   retTable->numEntries = 0;
   retTable->tableSz    = numHashSlots;

   nullOutTablesArray( retTable );

   return retTable;
 }

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;

   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;
            putEntryIntoTable( entry, table ); //does not allocate anything
            entry = nextEntry;
          }
       }
    }
 }

void
nullOutTablesArray( HashTable *table )
 { int i, tableSz;
   tableSz = table->tableSz;
   HashEntry ** entries = table->entries;
   for( i = 0; i < tableSz; i++ )
      entries[ i ] = NULL;
 }

unsigned int
hashThisKey( char* s, int hashSz )
 { unsigned int h = 0;
   unsigned int i;
   hashkey_t* key = (hashkey_t*)s;

   for(i=0 ; i<sizeof(hashkey_t); i++ )
      h = key->hashable[i] + h*31;
   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 )
 {  uint32
   hashIndex = hashThisKey( key, table->tableSz );
    HashEntry*
   hashEntry = table->entries[ hashIndex ];
   for( ; hashEntry != NULL; hashEntry = hashEntry->next )
    {
       if( strcmp( hashEntry->key, key ) == 0 )
           return hashEntry;
    }
   return NULL;
 }

void *
getValueFromTable( char *key, HashTable * table )
 { HashEntry *entry;
   entry = getEntryFromTable( key, table );
   if( entry == NULL ) return NULL;

   return entry->content;
 }

/*If key already has a value, clobber the old one and replace it
 */
 int
addValueIntoTable( char* key, void *content, HashTable *table )
 { unsigned int hashIdx;
   HashEntry* hashEntry;

   hashEntry = getEntryFromTable( key, table );
   if( hashEntry == NULL )
    { hashIdx = hashThisKey( key, table->tableSz );
      hashEntry = makeHashEntry( key );
      hashEntry->next = (table->entries)[hashIdx];
      (table->entries)[hashIdx] = hashEntry;
      table->numEntries += 1;
      if( table->tableSz < table->numEntries ) doubleTableSize( table );
    }
   else
    { (*(table->freeEntryContentFn))( hashEntry->content );
    }
   hashEntry->content = content;
   return 1;
 }


 int
putEntryIntoTable( HashEntry *entry, HashTable *table )
 { unsigned int hashIdx;
   HashEntry* testEntry;

   testEntry = getEntryFromTable( entry->key, table );
   if( testEntry == NULL )
    { hashIdx = hashThisKey( entry->key, table->tableSz );
      entry->next = (table->entries)[hashIdx];
      (table->entries)[hashIdx] = entry;
      table->numEntries += 1;
      if( table->tableSz < table->numEntries ) doubleTableSize( table );
    }
   else
    { (*(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;
 }

/*Better version
 */
 void
untested_putEntryIntoTable( HashEntry *entry, HashTable * table )
 { HashEntry *testEntry, *prevEntry = NULL;
    unsigned int
   hashIndex = hashThisKey( entry->key, table->tableSz );
   
   testEntry = table->entries[ hashIndex ];
   for( ; testEntry != NULL; testEntry = testEntry->next )
    { if( strcmp( testEntry->key, entry->key ) == 0 )
       { if( prevEntry == NULL )
          { table->entries[hashIndex] = entry;
            entry->next = testEntry->next;
          }
         else
          { prevEntry->next = entry;
            entry->next = testEntry->next;
          }
         freeHashEntryUsing( testEntry, table ); //frees content too!
         return;
       }
    }
      //wasn't found, so insert
   entry->next = table->entries[hashIndex];
   table->entries[hashIndex] = entry;
 }


bool8
deleteEntryFromTable( char *key, HashTable *table )
 { HashEntry  *hashEntry;
   HashEntry **addrOfPrevPtr;
   unsigned int hashIndex;

   hashIndex = hashThisKey( key, table->tableSz );
   addrOfPrevPtr = &( table->entries[ hashIndex ] );//for removing node
   hashEntry = *addrOfPrevPtr; //already did work, might as well use it
   while( hashEntry != NULL )
    { if( strcmp( hashEntry->key, key ) == 0 )
       {
         *addrOfPrevPtr = hashEntry->next;  //remove node from list
         //TODO: Free the contents of entry?
         freeHashEntryButNotContent( hashEntry );
         table->numEntries -= 1;
         return TRUE;
       }
      addrOfPrevPtr = &( hashEntry->next );
      hashEntry = *addrOfPrevPtr;
    }
   return FALSE;
 }
 
void
freeHashTable( 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( hashEntry, table );
            hashEntry = temp;
          }
       }
    }
 }

void
freeHashEntryUsing( HashEntry *entry, HashTable *table )
 {
   if( entry->content != NULL )
      (*(table->freeEntryContentFn))( entry->content );
   VMS_int__free( entry->key ); //was VMS_int__malloc'd above, so free it
   VMS_int__free( entry );
 }

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
 * NOTE: does a copy of the key, so key can be alloc'd on stack */
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;
 }