VMS/C_Libraries/Hash_impl: PrivateHash.c comparison

comparison PrivateHash.c @ 23:ac99f4a8ce22

First working version

author	Sean Halle <seanhalle@yahoo.com>
date	Wed, 06 Jun 2012 18:00:58 -0700
parents	4b5abed39ab9
children	b032601956bb

comparison

equal deleted inserted replaced

-:8a0db7afdd70
+:c1e688d57e4d
 */
 #include "PrivateHash.h"
 HashTable *
 makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn )
 { HashTable * retTable;
 retTable = VMS_int__malloc( sizeof( HashTable ) );
 retTable->freeEntryContentFn = freeFn;
 nullOutTablesArray( retTable );
 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;
 oldTableSz = table->tableSz;
 oldEntries = table->entries;
-newTableSz = 2 * oldTableSz + 1;
+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;
+{ nextEntry = entry->next;  //save for later
 entry->next = NULL;
 putEntryIntoTable( entry, table ); //does not allocate anything
 entry = nextEntry;
 }
 }
 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 )
-{  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;
 }
 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 )
 HashEntry* hashEntry;
 hashEntry = getEntryFromTable( key, table );
 if( hashEntry == NULL )
 { hashIdx = hashThisKey( key, table->tableSz );
-hashEntry = (HashEntry*) VMS_int__malloc( sizeof( HashEntry ) );
+hashEntry = makeHashEntry( key );
-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->next = (table->entries)[hashIdx];
 (table->entries)[hashIdx] = hashEntry;
 table->numEntries += 1;
 if( table->tableSz < table->numEntries ) doubleTableSize( table );
 }
 { (*(table->freeEntryContentFn))( hashEntry->content );
 }
 hashEntry->content = content;
 return 1;
 }
 int
 putEntryIntoTable( HashEntry *entry, HashTable *table )
 { unsigned int hashIdx;
 HashEntry* testEntry;
 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
+//being lazy -- will create bug in code that relies on having ptr
-// elem given to insert into table!
+// to elem given to insert into table!
 testEntry->content = entry->content;
 entry->content = NULL;
 freeHashEntryButNotContent( entry );
 }
 return 1;
 unsigned int
 hashIndex = hashThisKey( entry->key, table->tableSz );
 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;
 }
 else
 entry->next = table->entries[hashIndex];
 table->entries[hashIndex] = entry;
 }
+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 ] );
+addrOfPrevPtr = &( table->entries[ hashIndex ] );//for removing node
-hashEntry = *addrOfHashEntryPtr;
+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 );
+addrOfPrevPtr = &( hashEntry->next );
-hashEntry = *addrOfHashEntryPtr;
+hashEntry = *addrOfPrevPtr;
 }
 return FALSE;
 }
 void
 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 */
+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;
+}

Mercurial > cgi-bin > hgwebdir.cgi > VMS > C_Libraries > Hash_impl

comparison PrivateHash.c @ 23:ac99f4a8ce22