1.1 --- a/PrivateHash.c	Tue Mar 13 18:31:05 2012 -0700
     1.2 +++ b/PrivateHash.c	Wed Jun 06 18:00:58 2012 -0700
     1.3 @@ -9,7 +9,7 @@
     1.4  #include "PrivateHash.h"
     1.5  
     1.6  
     1.7 - HashTable *
     1.8 +HashTable *
     1.9  makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn )
    1.10   { HashTable * retTable;
    1.11     retTable = VMS_int__malloc( sizeof( HashTable ) );
    1.12 @@ -25,7 +25,23 @@
    1.13     return retTable;
    1.14   }
    1.15  
    1.16 - void
    1.17 +HashTable *
    1.18 +makeHashTable_WL( int numHashSlots, FreeEntryContentFnPtr freeFn )
    1.19 + { HashTable * retTable;
    1.20 +   retTable = VMS_WL__malloc( sizeof( HashTable ) );
    1.21 +
    1.22 +   retTable->freeEntryContentFn = freeFn;
    1.23 +   
    1.24 +   retTable->entries    = VMS_int__malloc( numHashSlots * sizeof(HashEntry *) );
    1.25 +   retTable->numEntries = 0;
    1.26 +   retTable->tableSz    = numHashSlots;
    1.27 +
    1.28 +   nullOutTablesArray( retTable );
    1.29 +
    1.30 +   return retTable;
    1.31 + }
    1.32 +
    1.33 +void
    1.34  doubleTableSize( HashTable *table )
    1.35   { int i, oldTableSz, newTableSz;
    1.36     HashEntry *entry, *nextEntry, **oldEntries, **newEntries;
    1.37 @@ -33,7 +49,7 @@
    1.38     oldTableSz = table->tableSz;
    1.39     oldEntries = table->entries;
    1.40  
    1.41 -   newTableSz = 2 * oldTableSz + 1;
    1.42 +   newTableSz = 2 * oldTableSz;
    1.43     newEntries = VMS_int__malloc( newTableSz * sizeof(HashEntry *) );
    1.44  
    1.45     table->tableSz    = newTableSz;
    1.46 @@ -45,7 +61,7 @@
    1.47      { if( oldEntries[i] != NULL )
    1.48         { entry = oldEntries[i];
    1.49           while( entry != NULL )
    1.50 -          { nextEntry = entry->next;
    1.51 +          { nextEntry = entry->next;  //save for later
    1.52              entry->next = NULL;
    1.53              putEntryIntoTable( entry, table ); //does not allocate anything
    1.54              entry = nextEntry;
    1.55 @@ -74,17 +90,36 @@
    1.56     return h % hashSz;
    1.57   }
    1.58  
    1.59 +/*Copies the string that is the key*/
    1.60 +inline HashEntry *
    1.61 +makeHashEntry( char * key )
    1.62 + { HashEntry *hashEntry;
    1.63 + 
    1.64 +   int32 len = strlen(key);
    1.65 + 
    1.66 +   hashEntry = (HashEntry*) VMS_int__malloc( sizeof( HashEntry ) );
    1.67 +         if( hashEntry == NULL )  return NULL;
    1.68 +   
    1.69 +   hashEntry->key = VMS_int__malloc( len + 1 );
    1.70 +         if( hashEntry->key == NULL ) return NULL;
    1.71 +   memcpy( hashEntry->key, key, len + 1 );
    1.72 +   hashEntry->next = NULL;
    1.73 +   
    1.74 +   return hashEntry;
    1.75 + }
    1.76 +
    1.77 +
    1.78  /*Need this to be separated out, for use in both getParam and putParam
    1.79   */
    1.80  HashEntry *
    1.81  getEntryFromTable( char *key, HashTable * table )
    1.82 - {  unsigned int
    1.83 + {  uint32
    1.84     hashIndex = hashThisKey( key, table->tableSz );
    1.85      HashEntry*
    1.86     hashEntry = table->entries[ hashIndex ];
    1.87     for( ; hashEntry != NULL; hashEntry = hashEntry->next )
    1.88      {
    1.89 -       if( memcmp( hashEntry->key, key, sizeof(hashkey_t) ) == 0 )
    1.90 +       if( strcmp( hashEntry->key, key ) == 0 )
    1.91             return hashEntry;
    1.92      }
    1.93     return NULL;
    1.94 @@ -99,7 +134,6 @@
    1.95     return entry->content;
    1.96   }
    1.97  
    1.98 -
    1.99  /*If key already has a value, clobber the old one and replace it
   1.100   */
   1.101   int
   1.102 @@ -110,11 +144,7 @@
   1.103     hashEntry = getEntryFromTable( key, table );
   1.104     if( hashEntry == NULL )
   1.105      { hashIdx = hashThisKey( key, table->tableSz );
   1.106 -      hashEntry = (HashEntry*) VMS_int__malloc( sizeof( HashEntry ) );
   1.107 -            if( hashEntry == NULL )  return 0;
   1.108 -      hashEntry->key = VMS_int__malloc( sizeof(hashkey_t) );
   1.109 -            if( hashEntry->key == NULL ) return 0;
   1.110 -      memcpy( hashEntry->key, key, sizeof(hashkey_t) );
   1.111 +      hashEntry = makeHashEntry( key );
   1.112        hashEntry->next = (table->entries)[hashIdx];
   1.113        (table->entries)[hashIdx] = hashEntry;
   1.114        table->numEntries += 1;
   1.115 @@ -127,6 +157,7 @@
   1.116     return 1;
   1.117   }
   1.118  
   1.119 +
   1.120   int
   1.121  putEntryIntoTable( HashEntry *entry, HashTable *table )
   1.122   { unsigned int hashIdx;
   1.123 @@ -142,8 +173,8 @@
   1.124      }
   1.125     else
   1.126      { (*(table->freeEntryContentFn))( testEntry->content );
   1.127 -         //being lazy -- will create bug in code that relies on having ptr to
   1.128 -         // elem given to insert into table!
   1.129 +         //being lazy -- will create bug in code that relies on having ptr
   1.130 +         // to elem given to insert into table!
   1.131        testEntry->content = entry->content;
   1.132        entry->content = NULL;
   1.133        freeHashEntryButNotContent( entry );
   1.134 @@ -161,7 +192,7 @@
   1.135     
   1.136     testEntry = table->entries[ hashIndex ];
   1.137     for( ; testEntry != NULL; testEntry = testEntry->next )
   1.138 -    { if( memcmp( testEntry->key, entry->key, sizeof(hashkey_t)) == 0 )
   1.139 +    { if( strcmp( testEntry->key, entry->key ) == 0 )
   1.140         { if( prevEntry == NULL )
   1.141            { table->entries[hashIndex] = entry;
   1.142              entry->next = testEntry->next;
   1.143 @@ -180,27 +211,26 @@
   1.144   }
   1.145  
   1.146  
   1.147 -
   1.148 - bool8
   1.149 +bool8
   1.150  deleteEntryFromTable( char *key, HashTable *table )
   1.151   { HashEntry  *hashEntry;
   1.152 -   HashEntry **addrOfHashEntryPtr;
   1.153 +   HashEntry **addrOfPrevPtr;
   1.154     unsigned int hashIndex;
   1.155  
   1.156     hashIndex = hashThisKey( key, table->tableSz );
   1.157 -   addrOfHashEntryPtr = &( table->entries[ hashIndex ] );
   1.158 -   hashEntry = *addrOfHashEntryPtr;
   1.159 +   addrOfPrevPtr = &( table->entries[ hashIndex ] );//for removing node
   1.160 +   hashEntry = *addrOfPrevPtr; //already did work, might as well use it
   1.161     while( hashEntry != NULL )
   1.162 -    { if( memcmp( hashEntry->key, key, sizeof(hashkey_t) ) == 0 )
   1.163 +    { if( strcmp( hashEntry->key, key ) == 0 )
   1.164         {
   1.165 -         *addrOfHashEntryPtr = hashEntry->next;
   1.166 +         *addrOfPrevPtr = hashEntry->next;  //remove node from list
   1.167           //TODO: Free the contents of entry?
   1.168           freeHashEntryButNotContent( hashEntry );
   1.169           table->numEntries -= 1;
   1.170           return TRUE;
   1.171         }
   1.172 -      addrOfHashEntryPtr = &( hashEntry->next );
   1.173 -      hashEntry = *addrOfHashEntryPtr;
   1.174 +      addrOfPrevPtr = &( hashEntry->next );
   1.175 +      hashEntry = *addrOfPrevPtr;
   1.176      }
   1.177     return FALSE;
   1.178   }
   1.179 @@ -234,9 +264,247 @@
   1.180   }
   1.181  
   1.182  void
   1.183 +freeHashEntryUsing_WL( HashEntry *entry, HashTable *table )
   1.184 + {
   1.185 +   if( entry->content != NULL )
   1.186 +      (*(table->freeEntryContentFn))( entry->content );
   1.187 +   VMS_WL__free( entry->key ); //was VMS_int__malloc'd above, so free it
   1.188 +   VMS_WL__free( entry );
   1.189 + }
   1.190 + 
   1.191 +void
   1.192 +freeHashTable_WL( HashTable *table )
   1.193 + { int i;
   1.194 +   HashEntry *hashEntry, *temp, **entries;
   1.195 +
   1.196 +   entries = table->entries;
   1.197 +   for( i=0; i < table->tableSz; i++ )
   1.198 +    { if( entries[i] != NULL )
   1.199 +       { hashEntry = entries[i];
   1.200 +         while( hashEntry != NULL )
   1.201 +          {
   1.202 +            temp = hashEntry->next;
   1.203 +            freeHashEntryUsing_WL( hashEntry, table );
   1.204 +            hashEntry = temp;
   1.205 +          }
   1.206 +       }
   1.207 +    }
   1.208 + }
   1.209 +
   1.210 +
   1.211 +void
   1.212  freeHashEntryButNotContent( HashEntry *entry )
   1.213   {
   1.214     VMS_int__free( entry->key ); //was VMS_int__malloc'd above, so free it
   1.215     VMS_int__free( entry );
   1.216   }
   1.217  
   1.218 +void
   1.219 +freeHashEntryButNotContent_WL( HashEntry *entry )
   1.220 + {
   1.221 +   VMS_WL__free( entry->key ); //was VMS_int__malloc'd above, so free it
   1.222 +   VMS_WL__free( entry );
   1.223 + }
   1.224 +
   1.225 +
   1.226 +
   1.227 +
   1.228 +//======================= 32 bit integer key version ======================
   1.229 +
   1.230 +/*key is array of uint32, with first entry being the num ints in key.
   1.231 + * that means size of key is content of first entry times 4, plus the
   1.232 + * size of first entry itself, which is another 4*/
   1.233 +#define sizeOfKey(key) key[0]*4 + 4
   1.234 +
   1.235 +
   1.236 +HashTable *
   1.237 +makeHashTable32( int powerOf2OfSz, FreeEntryContentFnPtr freeFn )
   1.238 + { HashTable * retTable;
   1.239 +   int32 numHashSlots;
   1.240 +   
   1.241 +   retTable = VMS_int__malloc( sizeof( HashTable ) );
   1.242 +
   1.243 +   numHashSlots = 1 << powerOf2OfSz;
   1.244 +   retTable->hashMask   = 0xffffffff >> 32 - powerOf2OfSz;   
   1.245 +   retTable->prevHash   = (int32)rand();
   1.246 +   
   1.247 +   retTable->freeEntryContentFn = freeFn;
   1.248 +   
   1.249 +   retTable->entries = VMS_int__malloc( numHashSlots * sizeof(HashEntry *));
   1.250 +   retTable->numEntries = 0;
   1.251 +   retTable->tableSz    = numHashSlots;
   1.252 +
   1.253 +   nullOutTablesArray( retTable );
   1.254 +
   1.255 +   return retTable;
   1.256 + }
   1.257 +
   1.258 +HashTable *
   1.259 +makeDefaultSizeHashTable32( FreeEntryContentFnPtr freeFn )
   1.260 + {
   1.261 +   return makeHashTable32( DEFAULT_POWER_OF_2_TABLE_SIZE, freeFn );
   1.262 + }
   1.263 +
   1.264 +HashEntry *
   1.265 +makeHashEntry32( uint32 * key )
   1.266 + { HashEntry *hashEntry;
   1.267 + 
   1.268 +   hashEntry = (HashEntry*) VMS_int__malloc( sizeof( HashEntry ) );
   1.269 +         if( hashEntry == NULL )  return NULL;
   1.270 +   hashEntry->key = VMS_int__malloc( sizeOfKey(key) );
   1.271 +         if( hashEntry->key == NULL ) return NULL;
   1.272 +   memcpy( hashEntry->key, key, sizeOfKey(key) );
   1.273 +   hashEntry->next = NULL;
   1.274 +   
   1.275 +   return hashEntry;
   1.276 + }
   1.277 +
   1.278 +
   1.279 +
   1.280 +int32
   1.281 +putEntryIntoTable32( HashEntry *entry, HashTable *table )
   1.282 + { unsigned int hashIdx;
   1.283 +   HashEntry* testEntry;
   1.284 +
   1.285 +   testEntry = getEntryFromTable32( (uint32 *)entry->key, table );
   1.286 +   if( testEntry == NULL ) //no entry w/key, so add passed-in as list-head
   1.287 +    { hashIdx = hashThisKey32( entry->key, table->tableSz );
   1.288 +      entry->next = (table->entries)[hashIdx];
   1.289 +      (table->entries)[hashIdx] = entry;
   1.290 +      table->numEntries += 1;
   1.291 +         //keep num entries less than half the num indexes in table
   1.292 +      if( table->numEntries > (table->tableSz >>1) ) doubleTableSize(table);
   1.293 +    }
   1.294 +   else //entry w/key already exists, so free content, then replace then
   1.295 +        // free the passed-in entry, leaving the entry already in table
   1.296 +    { (*(table->freeEntryContentFn))( testEntry->content );
   1.297 +         //being lazy -- will create bug in code that relies on having ptr
   1.298 +         // to elem given to insert into table!
   1.299 +      testEntry->content = entry->content;
   1.300 +      entry->content = NULL;
   1.301 +      freeHashEntryButNotContent( entry );
   1.302 +    }
   1.303 +   return 1;
   1.304 + }
   1.305 +
   1.306 +
   1.307 +void
   1.308 +doubleTableSize32( HashTable *table )
   1.309 + { int i, oldTableSz, newTableSz;
   1.310 +   HashEntry *entry, *nextEntry, **oldEntries, **newEntries;
   1.311 +
   1.312 +   oldTableSz = table->tableSz;
   1.313 +   oldEntries = table->entries;
   1.314 +
   1.315 +   newTableSz = 2 * oldTableSz;
   1.316 +   newEntries = VMS_int__malloc( newTableSz * sizeof(HashEntry *) );
   1.317 +
   1.318 +   table->tableSz    = newTableSz;
   1.319 +   table->entries    = newEntries;
   1.320 +   table->numEntries = 0; //about to add them all back!
   1.321 +
   1.322 +      // move all the entries from old to new
   1.323 +   for( i=0; i < oldTableSz; i++ )
   1.324 +    { if( oldEntries[i] != NULL )
   1.325 +       { entry = oldEntries[i];
   1.326 +         while( entry != NULL )
   1.327 +          { nextEntry = entry->next;  //save for later
   1.328 +            entry->next = NULL;       //null before, so can chain in new
   1.329 +            putEntryIntoTable32( entry, table ); //doesn't allocate anything
   1.330 +            entry = nextEntry;
   1.331 +          }
   1.332 +       }
   1.333 +    }
   1.334 + }
   1.335 +
   1.336 +/*The key is a self-sized array of 32 bit unsigned ints, with the first
   1.337 + * entry being the number of ints in the key, which makes up the rest of
   1.338 + * the array.*/
   1.339 +int32
   1.340 +hashThisKey32( uint32 *key, HashTable *hashTable )
   1.341 + { int32 hashOfKey;
   1.342 + 
   1.343 +      //the hash function takes addr of start of key array, plus num int32s,
   1.344 +   hashOfKey = jenkHash32( &key[1], *key );
   1.345 +   hashTable->prevHash = hashOfKey;
   1.346 +   
   1.347 +   /*The hash is a full 32 bits, but only want hashes that fall within
   1.348 +    * the size of the table.  So, mask off the higher bits. */
   1.349 +   return ( hashTable->hashMask & hashOfKey ); //reduce to size of table
   1.350 + }
   1.351 +
   1.352 +
   1.353 +/*The first entry of key says the size of the key, while key itself is the
   1.354 + * rest of the integers in the array
   1.355 + */
   1.356 +HashEntry *
   1.357 +getEntryFromTable32( uint32 *key, HashTable * table )
   1.358 + {  unsigned int
   1.359 +   hashIndex = hashThisKey32( key, table );
   1.360 +    HashEntry*
   1.361 +   hashEntry = table->entries[ hashIndex ];
   1.362 +   for( ; hashEntry != NULL; hashEntry = hashEntry->next )
   1.363 +    {
   1.364 +       if( memcmp( hashEntry->key, key, sizeOfKey(key) ) == 0 )
   1.365 +           return hashEntry;
   1.366 +    }
   1.367 +   return NULL;
   1.368 + }
   1.369 +
   1.370 +void *
   1.371 +getValueFromTable32( uint32 *key, HashTable * table )
   1.372 + { HashEntry *entry;
   1.373 +   entry = getEntryFromTable32( key, table );
   1.374 +   if( entry == NULL ) return NULL;
   1.375 +
   1.376 +   return entry->content;
   1.377 + }
   1.378 +
   1.379 +/*Returns NULL if failed to insert, else returns ptr to hash entry */
   1.380 +HashEntry *
   1.381 +addValueIntoTable32( uint32* key, void *content, HashTable *table )
   1.382 + { unsigned int hashIdx;
   1.383 +   HashEntry* hashEntry;
   1.384 +
   1.385 +   hashEntry = getEntryFromTable32( key, table );
   1.386 +   if( hashEntry == NULL )
   1.387 +    { hashIdx   = hashThisKey32( key, table );
   1.388 +      hashEntry = makeHashEntry32( key );
   1.389 +      hashEntry->next = (table->entries)[hashIdx];
   1.390 +      (table->entries)[hashIdx] = hashEntry;
   1.391 +      table->numEntries += 1;
   1.392 +         //Check if need to make bigger -- keep half-full (hence ">> 1")
   1.393 +      if( table->numEntries > table->tableSz >>1 ) doubleTableSize( table );
   1.394 +    }
   1.395 +   else
   1.396 +    { (*(table->freeEntryContentFn))( hashEntry->content );
   1.397 +    }
   1.398 +   hashEntry->content = content;
   1.399 +   return hashEntry;
   1.400 + }
   1.401 +
   1.402 +
   1.403 +bool32
   1.404 +deleteEntryFromTable32( uint32 *key, HashTable *table )
   1.405 + { HashEntry   *hashEntry;
   1.406 +   HashEntry  **addrOfPrevPtr;
   1.407 +   unsigned int hashIndex;
   1.408 +
   1.409 +   hashIndex = hashThisKey32( key, table );
   1.410 +   hashEntry = table->entries[ hashIndex ];
   1.411 +      //go down the chained list, checking all with this hash value
   1.412 +   addrOfPrevPtr = &( table->entries[hashIndex] ); //for removing a node
   1.413 +   hashEntry = *addrOfPrevPtr;  //did ptr chasing, might as well use it
   1.414 +   while( hashEntry != NULL )
   1.415 +    { if( memcmp( hashEntry->key, key, sizeOfKey(key) ) == 0 )
   1.416 +       { *addrOfPrevPtr = hashEntry->next; //remove node from list
   1.417 +         freeHashEntryButNotContent( hashEntry );
   1.418 +         table->numEntries -= 1;
   1.419 +         return TRUE;
   1.420 +       }
   1.421 +      addrOfPrevPtr = &(hashEntry->next); //chg content of *this* to remove
   1.422 +      hashEntry     = *addrOfPrevPtr;     //cheaper than hashEntry->next
   1.423 +    }
   1.424 +   return FALSE;
   1.425 + }
   1.426 +

     2.1 --- a/PrivateHash.h	Tue Mar 13 18:31:05 2012 -0700
     2.2 +++ b/PrivateHash.h	Wed Jun 06 18:00:58 2012 -0700
     2.3 @@ -16,9 +16,15 @@
     2.4  #include "VMS_impl/VMS_primitive_data_types.h"
     2.5  #include "VMS_impl/Services_Offered_by_VMS/Memory_Handling/vmalloc.h"
     2.6  
     2.7 +//=====================  defines  =====================
     2.8  #define TRUE     1
     2.9  #define FALSE    0
    2.10  
    2.11 +#define DEFAULT_HASH_TABLE_SIZE 1 << 10
    2.12 +#define DEFAULT_POWER_OF_2_TABLE_SIZE 10
    2.13 +
    2.14 +
    2.15 +//=====================  structs  =====================
    2.16  union hashkey_t{
    2.17      char hashable[8];
    2.18      int  parts[2];
    2.19 @@ -26,8 +32,6 @@
    2.20  
    2.21  typedef union hashkey_t hashkey_t;
    2.22  
    2.23 -#define DEFAULT_HASHSIZE 1 << 10
    2.24 -
    2.25  typedef struct _HashEntry HashEntry;
    2.26  
    2.27  struct _HashEntry
    2.28 @@ -40,9 +44,11 @@
    2.29  typedef void (*FreeEntryContentFnPtr)    ( void * );
    2.30  
    2.31  typedef struct
    2.32 - { int tableSz;
    2.33 -   int numEntries;
    2.34 + { int         tableSz;
    2.35 +   int         numEntries;
    2.36     HashEntry* *entries;
    2.37 +   int32       hashMask;
    2.38 +   int32       prevHash;
    2.39     FreeEntryContentFnPtr freeEntryContentFn;
    2.40   }
    2.41  HashTable;
    2.42 @@ -64,6 +70,17 @@
    2.43  void         freeHashTable( HashTable *table );
    2.44  //char        *paramBagToString( ParamBag * bag )
    2.45  
    2.46 +//================= Same Fns, but for 32b array key hash fn ================
    2.47 +HashTable *makeHashTable32(int32 powerOf2OfSz, FreeEntryContentFnPtr freeFn);
    2.48 +HashTable *makeDefaultSizeHashTable32( FreeEntryContentFnPtr freeFn );
    2.49 +
    2.50 +int        putEntryIntoTable32( HashEntry *entry, HashTable *table);
    2.51 +HashEntry *addValueIntoTable32( uint32 key[], void *value, HashTable *table);
    2.52 +HashEntry *getEntryFromTable32( uint32 key[], HashTable *table );
    2.53 +void      *getValueFromTable32( uint32 key[], HashTable *table );
    2.54 +
    2.55 +bool32     deleteEntryFromTable32( uint32 key[], HashTable *table );
    2.56 +
    2.57  //===========================================================================
    2.58  //   Internal functions
    2.59  void         freeHashEntryUsing( HashEntry *entry, HashTable *table );
    2.60 @@ -72,5 +89,9 @@
    2.61  void         doubleTableSize( HashTable *table );
    2.62  void         freeHashEntryButNotContent( HashEntry *entry );
    2.63  
    2.64 +uint32 
    2.65 +jenkHash32( const uint32  *key,     /* array of uint32 values */
    2.66 +                   int32   length);  /* num uint32 in the key */
    2.67 +        
    2.68  #endif	/* _PRIVATE_HASH_H */
    2.69