Me@14: /*
seanhalle@31:  *  Copyright 2009 OpenSourceResearchInstitute.org
Me@14:  *  Licensed under GNU General Public License version 2
Me@14:  *
Me@14:  *
Me@14:  * Author: seanhalle@yahoo.com
Me@14:  */
Me@14: 
Me@14: #include "PrivateHash.h"
Me@14: 
Me@14: 
seanhalle@23: HashTable *
Me@14: makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn )
Me@14:  { HashTable * retTable;
seanhalle@29:    retTable = PR_int__malloc( sizeof( HashTable ) );
Me@14: 
Me@14:    retTable->freeEntryContentFn = freeFn;
Me@14:    
seanhalle@29:    retTable->entries    = PR_int__malloc( numHashSlots * sizeof(HashEntry *) );
Me@14:    retTable->numEntries = 0;
Me@14:    retTable->tableSz    = numHashSlots;
Me@14: 
Me@14:    nullOutTablesArray( retTable );
Me@14: 
Me@14:    return retTable;
Me@14:  }
Me@14: 
seanhalle@23: HashTable *
seanhalle@23: makeHashTable_WL( int numHashSlots, FreeEntryContentFnPtr freeFn )
seanhalle@23:  { HashTable * retTable;
seanhalle@29:    retTable = PR_WL__malloc( sizeof( HashTable ) );
seanhalle@23: 
seanhalle@23:    retTable->freeEntryContentFn = freeFn;
seanhalle@23:    
seanhalle@29:    retTable->entries    = PR_int__malloc( numHashSlots * sizeof(HashEntry *) );
seanhalle@23:    retTable->numEntries = 0;
seanhalle@23:    retTable->tableSz    = numHashSlots;
seanhalle@23: 
seanhalle@23:    nullOutTablesArray( retTable );
seanhalle@23: 
seanhalle@23:    return retTable;
seanhalle@23:  }
seanhalle@23: 
seanhalle@23: void
Me@14: doubleTableSize( HashTable *table )
Me@14:  { int i, oldTableSz, newTableSz;
Me@14:    HashEntry *entry, *nextEntry, **oldEntries, **newEntries;
Me@14: 
Me@14:    oldTableSz = table->tableSz;
Me@14:    oldEntries = table->entries;
Me@14: 
seanhalle@23:    newTableSz = 2 * oldTableSz;
seanhalle@29:    newEntries = PR_int__malloc( newTableSz * sizeof(HashEntry *) );
Me@14: 
Me@14:    table->tableSz    = newTableSz;
Me@14:    table->entries    = newEntries;
Me@14:    table->numEntries = 0; //about to add them all back!
Me@14: 
Me@14:       // move all the entries from old to new
Me@14:    for( i=0; i < oldTableSz; i++ )
Me@14:     { if( oldEntries[i] != NULL )
Me@14:        { entry = oldEntries[i];
Me@14:          while( entry != NULL )
seanhalle@23:           { nextEntry = entry->next;  //save for later
Me@14:             entry->next = NULL;
Me@14:             putEntryIntoTable( entry, table ); //does not allocate anything
Me@14:             entry = nextEntry;
Me@14:           }
Me@14:        }
Me@14:     }
Me@14:  }
Me@14: 
Me@14: void
Me@14: nullOutTablesArray( HashTable *table )
Me@14:  { int i, tableSz;
Me@14:    tableSz = table->tableSz;
Me@14:    HashEntry ** entries = table->entries;
Me@14:    for( i = 0; i < tableSz; i++ )
Me@14:       entries[ i ] = NULL;
Me@14:  }
Me@14: 
Me@14: unsigned int
Me@14: hashThisKey( char* s, int hashSz )
Me@14:  { unsigned int h = 0;
Me@14:    unsigned int i;
Me@14:    hashkey_t* key = (hashkey_t*)s;
Me@14: 
Me@14:    for(i=0 ; i<sizeof(hashkey_t); i++ )
Me@14:       h = key->hashable[i] + h*31;
Me@14:    return h % hashSz;
Me@14:  }
Me@14: 
seanhalle@23: /*Copies the string that is the key*/
seanhalle@23: inline HashEntry *
seanhalle@23: makeHashEntry( char * key )
seanhalle@23:  { HashEntry *hashEntry;
seanhalle@23:  
seanhalle@23:    int32 len = strlen(key);
seanhalle@23:  
seanhalle@29:    hashEntry = (HashEntry*) PR_int__malloc( sizeof( HashEntry ) );
seanhalle@23:          if( hashEntry == NULL )  return NULL;
seanhalle@23:    
seanhalle@29:    hashEntry->key = PR_int__malloc( len + 1 );
seanhalle@23:          if( hashEntry->key == NULL ) return NULL;
seanhalle@23:    memcpy( hashEntry->key, key, len + 1 );
seanhalle@23:    hashEntry->next = NULL;
seanhalle@23:    
seanhalle@23:    return hashEntry;
seanhalle@23:  }
seanhalle@23: 
seanhalle@23: 
Me@14: /*Need this to be separated out, for use in both getParam and putParam
Me@14:  */
Me@14: HashEntry *
Me@14: getEntryFromTable( char *key, HashTable * table )
seanhalle@23:  {  uint32
Me@14:    hashIndex = hashThisKey( key, table->tableSz );
Me@14:     HashEntry*
Me@14:    hashEntry = table->entries[ hashIndex ];
Me@14:    for( ; hashEntry != NULL; hashEntry = hashEntry->next )
Me@14:     {
seanhalle@23:        if( strcmp( hashEntry->key, key ) == 0 )
Me@14:            return hashEntry;
Me@14:     }
Me@14:    return NULL;
Me@14:  }
Me@14: 
Me@14: void *
Me@14: getValueFromTable( char *key, HashTable * table )
Me@14:  { HashEntry *entry;
Me@14:    entry = getEntryFromTable( key, table );
Me@14:    if( entry == NULL ) return NULL;
Me@14: 
Me@14:    return entry->content;
Me@14:  }
Me@14: 
Me@14: /*If key already has a value, clobber the old one and replace it
Me@14:  */
Me@14:  int
Me@14: addValueIntoTable( char* key, void *content, HashTable *table )
Me@14:  { unsigned int hashIdx;
Me@14:    HashEntry* hashEntry;
Me@14: 
Me@14:    hashEntry = getEntryFromTable( key, table );
Me@14:    if( hashEntry == NULL )
Me@14:     { hashIdx = hashThisKey( key, table->tableSz );
seanhalle@23:       hashEntry = makeHashEntry( key );
Me@14:       hashEntry->next = (table->entries)[hashIdx];
Me@14:       (table->entries)[hashIdx] = hashEntry;
Me@14:       table->numEntries += 1;
Me@14:       if( table->tableSz < table->numEntries ) doubleTableSize( table );
Me@14:     }
Me@14:    else
Me@14:     { (*(table->freeEntryContentFn))( hashEntry->content );
Me@14:     }
Me@14:    hashEntry->content = content;
Me@14:    return 1;
Me@14:  }
Me@14: 
seanhalle@23: 
Me@14:  int
Me@14: putEntryIntoTable( HashEntry *entry, HashTable *table )
Me@14:  { unsigned int hashIdx;
Me@14:    HashEntry* testEntry;
Me@14: 
Me@14:    testEntry = getEntryFromTable( entry->key, table );
Me@14:    if( testEntry == NULL )
Me@14:     { hashIdx = hashThisKey( entry->key, table->tableSz );
Me@14:       entry->next = (table->entries)[hashIdx];
Me@14:       (table->entries)[hashIdx] = entry;
Me@14:       table->numEntries += 1;
Me@14:       if( table->tableSz < table->numEntries ) doubleTableSize( table );
Me@14:     }
Me@14:    else
Me@14:     { (*(table->freeEntryContentFn))( testEntry->content );
seanhalle@23:          //being lazy -- will create bug in code that relies on having ptr
seanhalle@23:          // to elem given to insert into table!
Me@14:       testEntry->content = entry->content;
Me@14:       entry->content = NULL;
Me@14:       freeHashEntryButNotContent( entry );
Me@14:     }
Me@14:    return 1;
Me@14:  }
Me@14: 
Me@14: /*Better version
Me@14:  */
Me@14:  void
Me@14: untested_putEntryIntoTable( HashEntry *entry, HashTable * table )
Me@14:  { HashEntry *testEntry, *prevEntry = NULL;
Me@14:     unsigned int
Me@14:    hashIndex = hashThisKey( entry->key, table->tableSz );
Me@14:    
Me@14:    testEntry = table->entries[ hashIndex ];
Me@14:    for( ; testEntry != NULL; testEntry = testEntry->next )
seanhalle@23:     { if( strcmp( testEntry->key, entry->key ) == 0 )
Me@14:        { if( prevEntry == NULL )
Me@14:           { table->entries[hashIndex] = entry;
Me@14:             entry->next = testEntry->next;
Me@14:           }
Me@14:          else
Me@14:           { prevEntry->next = entry;
Me@14:             entry->next = testEntry->next;
Me@14:           }
Me@14:          freeHashEntryUsing( testEntry, table ); //frees content too!
Me@14:          return;
Me@14:        }
Me@14:     }
Me@14:       //wasn't found, so insert
Me@14:    entry->next = table->entries[hashIndex];
Me@14:    table->entries[hashIndex] = entry;
Me@14:  }
Me@14: 
Me@14: 
seanhalle@23: bool8
Me@14: deleteEntryFromTable( char *key, HashTable *table )
Me@14:  { HashEntry  *hashEntry;
seanhalle@23:    HashEntry **addrOfPrevPtr;
Me@14:    unsigned int hashIndex;
Me@14: 
Me@14:    hashIndex = hashThisKey( key, table->tableSz );
seanhalle@23:    addrOfPrevPtr = &( table->entries[ hashIndex ] );//for removing node
seanhalle@23:    hashEntry = *addrOfPrevPtr; //already did work, might as well use it
Me@14:    while( hashEntry != NULL )
seanhalle@23:     { if( strcmp( hashEntry->key, key ) == 0 )
Me@14:        {
seanhalle@23:          *addrOfPrevPtr = hashEntry->next;  //remove node from list
Me@14:          //TODO: Free the contents of entry?
Me@14:          freeHashEntryButNotContent( hashEntry );
Me@14:          table->numEntries -= 1;
Me@14:          return TRUE;
Me@14:        }
seanhalle@23:       addrOfPrevPtr = &( hashEntry->next );
seanhalle@23:       hashEntry = *addrOfPrevPtr;
Me@14:     }
Me@14:    return FALSE;
Me@14:  }
Me@14:  
seanhalle@31: /*Frees hash table struct, all entry strucs, and even the contents of each
seanhalle@31:  * entry.
seanhalle@31:  */
Me@14: void
Me@14: freeHashTable( HashTable *table )
Me@14:  { int i;
Me@14:    HashEntry *hashEntry, *temp, **entries;
Me@14: 
Me@14:    entries = table->entries;
Me@14:    for( i=0; i < table->tableSz; i++ )
Me@14:     { if( entries[i] != NULL )
Me@14:        { hashEntry = entries[i];
Me@14:          while( hashEntry != NULL )
Me@14:           {
Me@14:             temp = hashEntry->next;
Me@14:             freeHashEntryUsing( hashEntry, table );
Me@14:             hashEntry = temp;
Me@14:           }
Me@14:        }
Me@14:     }
Me@14:  }
Me@14: 
Me@14: void
Me@14: freeHashEntryUsing( HashEntry *entry, HashTable *table )
Me@14:  {
Me@14:    if( entry->content != NULL )
Me@14:       (*(table->freeEntryContentFn))( entry->content );
seanhalle@29:    PR_int__free( entry->key ); //was PR_int__malloc'd above, so free it
seanhalle@29:    PR_int__free( entry );
Me@14:  }
Me@14: 
Me@14: void
seanhalle@23: freeHashEntryUsing_WL( HashEntry *entry, HashTable *table )
seanhalle@23:  {
seanhalle@23:    if( entry->content != NULL )
seanhalle@23:       (*(table->freeEntryContentFn))( entry->content );
seanhalle@29:    PR_WL__free( entry->key ); //was PR_int__malloc'd above, so free it
seanhalle@29:    PR_WL__free( entry );
seanhalle@23:  }
seanhalle@23:  
seanhalle@23: void
seanhalle@23: freeHashTable_WL( HashTable *table )
seanhalle@23:  { int i;
seanhalle@23:    HashEntry *hashEntry, *temp, **entries;
seanhalle@23: 
seanhalle@23:    entries = table->entries;
seanhalle@23:    for( i=0; i < table->tableSz; i++ )
seanhalle@23:     { if( entries[i] != NULL )
seanhalle@23:        { hashEntry = entries[i];
seanhalle@23:          while( hashEntry != NULL )
seanhalle@23:           {
seanhalle@23:             temp = hashEntry->next;
seanhalle@23:             freeHashEntryUsing_WL( hashEntry, table );
seanhalle@23:             hashEntry = temp;
seanhalle@23:           }
seanhalle@23:        }
seanhalle@23:     }
seanhalle@23:  }
seanhalle@23: 
seanhalle@23: 
seanhalle@23: void
Me@14: freeHashEntryButNotContent( HashEntry *entry )
Me@14:  {
seanhalle@29:    PR_int__free( entry->key ); //was PR_int__malloc'd above, so free it
seanhalle@29:    PR_int__free( entry );
Me@14:  }
Me@14: 
seanhalle@23: void
seanhalle@23: freeHashEntryButNotContent_WL( HashEntry *entry )
seanhalle@23:  {
seanhalle@29:    PR_WL__free( entry->key ); //was PR_int__malloc'd above, so free it
seanhalle@29:    PR_WL__free( entry );
seanhalle@23:  }
seanhalle@23: 
seanhalle@23: 
seanhalle@23: 
seanhalle@23: 
seanhalle@23: //======================= 32 bit integer key version ======================
seanhalle@23: 
seanhalle@23: /*key is array of uint32, with first entry being the num ints in key.
seanhalle@23:  * that means size of key is content of first entry times 4, plus the
seanhalle@23:  * size of first entry itself, which is another 4*/
seanhalle@23: #define sizeOfKey(key) key[0]*4 + 4
seanhalle@23: 
seanhalle@23: 
seanhalle@23: HashTable *
seanhalle@23: makeHashTable32( int powerOf2OfSz, FreeEntryContentFnPtr freeFn )
seanhalle@23:  { HashTable * retTable;
seanhalle@23:    int32 numHashSlots;
seanhalle@23:    
seanhalle@29:    retTable = PR_int__malloc( sizeof( HashTable ) );
seanhalle@23: 
seanhalle@23:    numHashSlots = 1 << powerOf2OfSz;
seanhalle@23:    retTable->hashMask   = 0xffffffff >> 32 - powerOf2OfSz;   
seanhalle@23:    retTable->prevHash   = (int32)rand();
seanhalle@23:    
seanhalle@23:    retTable->freeEntryContentFn = freeFn;
seanhalle@23:    
seanhalle@29:    retTable->entries = PR_int__malloc( numHashSlots * sizeof(HashEntry *));
seanhalle@23:    retTable->numEntries = 0;
seanhalle@23:    retTable->tableSz    = numHashSlots;
seanhalle@23: 
seanhalle@23:    nullOutTablesArray( retTable );
seanhalle@23: 
seanhalle@23:    return retTable;
seanhalle@23:  }
seanhalle@23: 
seanhalle@23: HashTable *
seanhalle@23: makeDefaultSizeHashTable32( FreeEntryContentFnPtr freeFn )
seanhalle@23:  {
seanhalle@23:    return makeHashTable32( DEFAULT_POWER_OF_2_TABLE_SIZE, freeFn );
seanhalle@23:  }
seanhalle@23: 
seanhalle@23: HashEntry *
seanhalle@23: makeHashEntry32( uint32 * key )
seanhalle@23:  { HashEntry *hashEntry;
seanhalle@23:  
seanhalle@29:    hashEntry = (HashEntry*) PR_int__malloc( sizeof( HashEntry ) );
seanhalle@23:          if( hashEntry == NULL )  return NULL;
seanhalle@29:    hashEntry->key = PR_int__malloc( sizeOfKey(key) );
seanhalle@23:          if( hashEntry->key == NULL ) return NULL;
seanhalle@23:    memcpy( hashEntry->key, key, sizeOfKey(key) );
seanhalle@23:    hashEntry->next = NULL;
seanhalle@23:    
seanhalle@23:    return hashEntry;
seanhalle@23:  }
seanhalle@23: 
seanhalle@23: 
seanhalle@23: 
seanhalle@23: int32
seanhalle@23: putEntryIntoTable32( HashEntry *entry, HashTable *table )
seanhalle@23:  { unsigned int hashIdx;
seanhalle@23:    HashEntry* testEntry;
seanhalle@23: 
seanhalle@23:    testEntry = getEntryFromTable32( (uint32 *)entry->key, table );
seanhalle@23:    if( testEntry == NULL ) //no entry w/key, so add passed-in as list-head
seanhalle@23:     { hashIdx = hashThisKey32( entry->key, table->tableSz );
seanhalle@23:       entry->next = (table->entries)[hashIdx];
seanhalle@23:       (table->entries)[hashIdx] = entry;
seanhalle@23:       table->numEntries += 1;
seanhalle@23:          //keep num entries less than half the num indexes in table
seanhalle@23:       if( table->numEntries > (table->tableSz >>1) ) doubleTableSize(table);
seanhalle@23:     }
seanhalle@23:    else //entry w/key already exists, so free content, then replace then
seanhalle@23:         // free the passed-in entry, leaving the entry already in table
seanhalle@23:     { (*(table->freeEntryContentFn))( testEntry->content );
seanhalle@23:          //being lazy -- will create bug in code that relies on having ptr
seanhalle@23:          // to elem given to insert into table!
seanhalle@23:       testEntry->content = entry->content;
seanhalle@23:       entry->content = NULL;
seanhalle@23:       freeHashEntryButNotContent( entry );
seanhalle@23:     }
seanhalle@23:    return 1;
seanhalle@23:  }
seanhalle@23: 
seanhalle@23: 
seanhalle@23: void
seanhalle@23: doubleTableSize32( HashTable *table )
seanhalle@23:  { int i, oldTableSz, newTableSz;
seanhalle@23:    HashEntry *entry, *nextEntry, **oldEntries, **newEntries;
seanhalle@23: 
seanhalle@23:    oldTableSz = table->tableSz;
seanhalle@23:    oldEntries = table->entries;
seanhalle@23: 
seanhalle@23:    newTableSz = 2 * oldTableSz;
seanhalle@29:    newEntries = PR_int__malloc( newTableSz * sizeof(HashEntry *) );
seanhalle@23: 
seanhalle@23:    table->tableSz    = newTableSz;
seanhalle@23:    table->entries    = newEntries;
seanhalle@23:    table->numEntries = 0; //about to add them all back!
seanhalle@23: 
seanhalle@23:       // move all the entries from old to new
seanhalle@23:    for( i=0; i < oldTableSz; i++ )
seanhalle@23:     { if( oldEntries[i] != NULL )
seanhalle@23:        { entry = oldEntries[i];
seanhalle@23:          while( entry != NULL )
seanhalle@23:           { nextEntry = entry->next;  //save for later
seanhalle@23:             entry->next = NULL;       //null before, so can chain in new
seanhalle@23:             putEntryIntoTable32( entry, table ); //doesn't allocate anything
seanhalle@23:             entry = nextEntry;
seanhalle@23:           }
seanhalle@23:        }
seanhalle@23:     }
seanhalle@23:  }
seanhalle@23: 
seanhalle@23: /*The key is a self-sized array of 32 bit unsigned ints, with the first
seanhalle@23:  * entry being the number of ints in the key, which makes up the rest of
seanhalle@23:  * the array.*/
seanhalle@23: int32
seanhalle@23: hashThisKey32( uint32 *key, HashTable *hashTable )
seanhalle@23:  { int32 hashOfKey;
seanhalle@23:  
seanhalle@23:       //the hash function takes addr of start of key array, plus num int32s,
seanhalle@23:    hashOfKey = jenkHash32( &key[1], *key );
seanhalle@23:    hashTable->prevHash = hashOfKey;
seanhalle@23:    
seanhalle@23:    /*The hash is a full 32 bits, but only want hashes that fall within
seanhalle@23:     * the size of the table.  So, mask off the higher bits. */
seanhalle@23:    return ( hashTable->hashMask & hashOfKey ); //reduce to size of table
seanhalle@23:  }
seanhalle@23: 
seanhalle@23: 
seanhalle@23: /*The first entry of key says the size of the key, while key itself is the
seanhalle@23:  * rest of the integers in the array
seanhalle@23:  */
seanhalle@23: HashEntry *
seanhalle@23: getEntryFromTable32( uint32 *key, HashTable * table )
seanhalle@23:  {  unsigned int
seanhalle@23:    hashIndex = hashThisKey32( key, table );
seanhalle@23:     HashEntry*
seanhalle@23:    hashEntry = table->entries[ hashIndex ];
seanhalle@23:    for( ; hashEntry != NULL; hashEntry = hashEntry->next )
seanhalle@23:     {
seanhalle@23:        if( memcmp( hashEntry->key, key, sizeOfKey(key) ) == 0 )
seanhalle@23:            return hashEntry;
seanhalle@23:     }
seanhalle@23:    return NULL;
seanhalle@23:  }
seanhalle@23: 
seanhalle@23: void *
seanhalle@23: getValueFromTable32( uint32 *key, HashTable * table )
seanhalle@23:  { HashEntry *entry;
seanhalle@23:    entry = getEntryFromTable32( key, table );
seanhalle@23:    if( entry == NULL ) return NULL;
seanhalle@23: 
seanhalle@23:    return entry->content;
seanhalle@23:  }
seanhalle@23: 
seanhalle@24: /*Returns NULL if failed to insert, else returns ptr to hash entry
seanhalle@24:  * NOTE: does a copy of the key, so key can be alloc'd on stack */
seanhalle@23: HashEntry *
seanhalle@23: addValueIntoTable32( uint32* key, void *content, HashTable *table )
seanhalle@23:  { unsigned int hashIdx;
seanhalle@23:    HashEntry* hashEntry;
seanhalle@23: 
seanhalle@23:    hashEntry = getEntryFromTable32( key, table );
seanhalle@23:    if( hashEntry == NULL )
seanhalle@23:     { hashIdx   = hashThisKey32( key, table );
seanhalle@23:       hashEntry = makeHashEntry32( key );
seanhalle@23:       hashEntry->next = (table->entries)[hashIdx];
seanhalle@23:       (table->entries)[hashIdx] = hashEntry;
seanhalle@23:       table->numEntries += 1;
seanhalle@23:          //Check if need to make bigger -- keep half-full (hence ">> 1")
seanhalle@23:       if( table->numEntries > table->tableSz >>1 ) doubleTableSize( table );
seanhalle@23:     }
seanhalle@23:    else
seanhalle@23:     { (*(table->freeEntryContentFn))( hashEntry->content );
seanhalle@23:     }
seanhalle@23:    hashEntry->content = content;
seanhalle@23:    return hashEntry;
seanhalle@23:  }
seanhalle@23: 
seanhalle@23: 
seanhalle@23: bool32
seanhalle@23: deleteEntryFromTable32( uint32 *key, HashTable *table )
seanhalle@23:  { HashEntry   *hashEntry;
seanhalle@23:    HashEntry  **addrOfPrevPtr;
seanhalle@23:    unsigned int hashIndex;
seanhalle@23: 
seanhalle@23:    hashIndex = hashThisKey32( key, table );
seanhalle@23:    hashEntry = table->entries[ hashIndex ];
seanhalle@23:       //go down the chained list, checking all with this hash value
seanhalle@23:    addrOfPrevPtr = &( table->entries[hashIndex] ); //for removing a node
seanhalle@23:    hashEntry = *addrOfPrevPtr;  //did ptr chasing, might as well use it
seanhalle@23:    while( hashEntry != NULL )
seanhalle@23:     { if( memcmp( hashEntry->key, key, sizeOfKey(key) ) == 0 )
seanhalle@23:        { *addrOfPrevPtr = hashEntry->next; //remove node from list
seanhalle@23:          freeHashEntryButNotContent( hashEntry );
seanhalle@23:          table->numEntries -= 1;
seanhalle@23:          return TRUE;
seanhalle@23:        }
seanhalle@23:       addrOfPrevPtr = &(hashEntry->next); //chg content of *this* to remove
seanhalle@23:       hashEntry     = *addrOfPrevPtr;     //cheaper than hashEntry->next
seanhalle@23:     }
seanhalle@23:    return FALSE;
seanhalle@23:  }
seanhalle@23: