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