Me@15: /*
Me@15:  *  Copyright 2009 OpenSourceStewardshipFoundation.org
Me@15:  *  Licensed under GNU General Public License version 2
Me@15:  *
Me@15:  *
Me@15:  * Author: seanhalle@yahoo.com
Me@15:  */
Me@15: 
Me@15: #include "PrivateHash.h"
Me@15: 
Me@15: 
Me@15:  HashTable *
Me@15: makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn )
Me@15:  { HashTable * retTable;
Me@15:    retTable = malloc( sizeof( HashTable ) );
Me@15: 
Me@15:    retTable->freeEntryContentFn = freeFn;
Me@15:    
Me@15:    retTable->entries    = malloc( numHashSlots * sizeof(HashEntry *) );
Me@15:    retTable->numEntries = 0;
Me@15:    retTable->tableSz    = numHashSlots;
Me@15: 
Me@15:    nullOutTablesArray( retTable );
Me@15: 
Me@15:    return retTable;
Me@15:  }
Me@15: 
Me@15:  void
Me@15: doubleTableSize( HashTable *table )
Me@15:  { int i, oldTableSz, newTableSz;
Me@15:    HashEntry *entry, *nextEntry, **oldEntries, **newEntries;
Me@15: 
Me@15:    oldTableSz = table->tableSz;
Me@15:    oldEntries = table->entries;
Me@15: 
Me@15:    newTableSz = 2 * oldTableSz + 1;
Me@15:    newEntries = malloc( newTableSz * sizeof(HashEntry *) );
Me@15: 
Me@15:    table->tableSz    = newTableSz;
Me@15:    table->entries    = newEntries;
Me@15:    table->numEntries = 0; //about to add them all back!
Me@15: 
Me@15:       // move all the entries from old to new
Me@15:    for( i=0; i < oldTableSz; i++ )
Me@15:     { if( oldEntries[i] != NULL )
Me@15:        { entry = oldEntries[i];
Me@15:          while( entry != NULL )
Me@15:           { nextEntry = entry->next;
Me@15:             entry->next = NULL;
Me@15:             putEntryIntoTable( entry, table ); //does not allocate anything
Me@15:             entry = nextEntry;
Me@15:           }
Me@15:        }
Me@15:     }
Me@15:  }
Me@15: 
Me@15: void
Me@15: nullOutTablesArray( HashTable *table )
Me@15:  { int i, tableSz;
Me@15:    tableSz = table->tableSz;
Me@15:    HashEntry ** entries = table->entries;
Me@15:    for( i = 0; i < tableSz; i++ )
Me@15:       entries[ i ] = NULL;
Me@15:  }
Me@15: 
Me@15: unsigned int
Me@15: hashThisKey( char* s, int hashSz )
Me@15:  { unsigned int h = 0;
Me@15:    unsigned int i;
Me@15:    hashkey_t* key = (hashkey_t*)s;
Me@15: 
Me@15:    for(i=0 ; i<sizeof(hashkey_t); i++ )
Me@15:       h = key->hashable[i] + h*31;
Me@15:    return h % hashSz;
Me@15:  }
Me@15: 
Me@15: /*Need this to be separated out, for use in both getParam and putParam
Me@15:  */
Me@15: HashEntry *
Me@15: getEntryFromTable( char *key, HashTable * table )
Me@15:  {  unsigned int
Me@15:    hashIndex = hashThisKey( key, table->tableSz );
Me@15:     HashEntry*
Me@15:    hashEntry = table->entries[ hashIndex ];
Me@15:    for( ; hashEntry != NULL; hashEntry = hashEntry->next )
Me@15:     {
Me@15:        if( memcmp( hashEntry->key, key, sizeof(hashkey_t) ) == 0 )
Me@15:            return hashEntry;
Me@15:     }
Me@15:    return NULL;
Me@15:  }
Me@15: 
Me@15: void *
Me@15: getValueFromTable( char *key, HashTable * table )
Me@15:  { HashEntry *entry;
Me@15:    entry = getEntryFromTable( key, table );
Me@15:    if( entry == NULL ) return NULL;
Me@15: 
Me@15:    return entry->content;
Me@15:  }
Me@15: 
Me@15: 
Me@15: /*If key already has a value, clobber the old one and replace it
Me@15:  */
Me@15:  int
Me@15: addValueIntoTable( char* key, void *content, HashTable *table )
Me@15:  { unsigned int hashIdx;
Me@15:    HashEntry* hashEntry;
Me@15: 
Me@15:    hashEntry = getEntryFromTable( key, table );
Me@15:    if( hashEntry == NULL )
Me@15:     { hashIdx = hashThisKey( key, table->tableSz );
Me@15:       hashEntry = (HashEntry*) malloc( sizeof( HashEntry ) );
Me@15:             if( hashEntry == NULL )  return 0;
Me@15:       hashEntry->key = malloc( sizeof(hashkey_t) );
Me@15:             if( hashEntry->key == NULL ) return 0;
Me@15:       memcpy( hashEntry->key, key, sizeof(hashkey_t) );
Me@15:       hashEntry->next = (table->entries)[hashIdx];
Me@15:       (table->entries)[hashIdx] = hashEntry;
Me@15:       table->numEntries += 1;
Me@15:       if( table->tableSz < table->numEntries ) doubleTableSize( table );
Me@15:     }
Me@15:    else
Me@15:     { (*(table->freeEntryContentFn))( hashEntry->content );
Me@15:     }
Me@15:    hashEntry->content = content;
Me@15:    return 1;
Me@15:  }
Me@15: 
Me@15:  int
Me@15: putEntryIntoTable( HashEntry *entry, HashTable *table )
Me@15:  { unsigned int hashIdx;
Me@15:    HashEntry* testEntry;
Me@15: 
Me@15:    testEntry = getEntryFromTable( entry->key, table );
Me@15:    if( testEntry == NULL )
Me@15:     { hashIdx = hashThisKey( entry->key, table->tableSz );
Me@15:       entry->next = (table->entries)[hashIdx];
Me@15:       (table->entries)[hashIdx] = entry;
Me@15:       table->numEntries += 1;
Me@15:       if( table->tableSz < table->numEntries ) doubleTableSize( table );
Me@15:     }
Me@15:    else
Me@15:     { (*(table->freeEntryContentFn))( testEntry->content );
Me@15:          //being lazy -- will create bug in code that relies on having ptr to
Me@15:          // elem given to insert into table!
Me@15:       testEntry->content = entry->content;
Me@15:       entry->content = NULL;
Me@15:       freeHashEntryButNotContent( entry );
Me@15:     }
Me@15:    return 1;
Me@15:  }
Me@15: 
Me@15: /*Better version
Me@15:  */
Me@15:  void
Me@15: untested_putEntryIntoTable( HashEntry *entry, HashTable * table )
Me@15:  { HashEntry *testEntry, *prevEntry = NULL;
Me@15:     unsigned int
Me@15:    hashIndex = hashThisKey( entry->key, table->tableSz );
Me@15:    
Me@15:    testEntry = table->entries[ hashIndex ];
Me@15:    for( ; testEntry != NULL; testEntry = testEntry->next )
Me@15:     { if( memcmp( testEntry->key, entry->key, sizeof(hashkey_t)) == 0 )
Me@15:        { if( prevEntry == NULL )
Me@15:           { table->entries[hashIndex] = entry;
Me@15:             entry->next = testEntry->next;
Me@15:           }
Me@15:          else
Me@15:           { prevEntry->next = entry;
Me@15:             entry->next = testEntry->next;
Me@15:           }
Me@15:          freeHashEntryUsing( testEntry, table ); //frees content too!
Me@15:          return;
Me@15:        }
Me@15:     }
Me@15:       //wasn't found, so insert
Me@15:    entry->next = table->entries[hashIndex];
Me@15:    table->entries[hashIndex] = entry;
Me@15:  }
Me@15: 
Me@15: 
Me@15: 
Me@15:  bool8
Me@15: deleteEntryFromTable( char *key, HashTable *table )
Me@15:  { HashEntry  *hashEntry;
Me@15:    HashEntry **addrOfHashEntryPtr;
Me@15:    unsigned int hashIndex;
Me@15: 
Me@15:    hashIndex = hashThisKey( key, table->tableSz );
Me@15:    addrOfHashEntryPtr = &( table->entries[ hashIndex ] );
Me@15:    hashEntry = *addrOfHashEntryPtr;
Me@15:    while( hashEntry != NULL )
Me@15:     { if( memcmp( hashEntry->key, key, sizeof(hashkey_t) ) == 0 )
Me@15:        {
Me@15:          *addrOfHashEntryPtr = hashEntry->next;
Me@15:          //TODO: Free the contents of entry?
Me@15:          freeHashEntryButNotContent( hashEntry );
Me@15:          table->numEntries -= 1;
Me@15:          return TRUE;
Me@15:        }
Me@15:       addrOfHashEntryPtr = &( hashEntry->next );
Me@15:       hashEntry = *addrOfHashEntryPtr;
Me@15:     }
Me@15:    return FALSE;
Me@15:  }
Me@15:  
Me@15: void
Me@15: freeHashTable( HashTable *table )
Me@15:  { int i;
Me@15:    HashEntry *hashEntry, *temp, **entries;
Me@15: 
Me@15:    entries = table->entries;
Me@15:    for( i=0; i < table->tableSz; i++ )
Me@15:     { if( entries[i] != NULL )
Me@15:        { hashEntry = entries[i];
Me@15:          while( hashEntry != NULL )
Me@15:           {
Me@15:             temp = hashEntry->next;
Me@15:             freeHashEntryUsing( hashEntry, table );
Me@15:             hashEntry = temp;
Me@15:           }
Me@15:        }
Me@15:     }
Me@15:  }
Me@15: 
Me@15: void
Me@15: freeHashEntryUsing( HashEntry *entry, HashTable *table )
Me@15:  {
Me@15:    if( entry->content != NULL )
Me@15:       (*(table->freeEntryContentFn))( entry->content );
Me@15:    free( entry->key ); //was malloc'd above, so free it
Me@15:    free( entry );
Me@15:  }
Me@15: 
Me@15: void
Me@15: freeHashEntryButNotContent( HashEntry *entry )
Me@15:  {
Me@15:    free( entry->key ); //was malloc'd above, so free it
Me@15:    free( entry );
Me@15:  }
Me@15: