1.1 --- a/PrivateHash.c	Thu Feb 09 15:51:22 2012 +0100
     1.2 +++ b/PrivateHash.c	Sat Feb 11 17:55:51 2012 -0800
     1.3 @@ -1,249 +1,242 @@
     1.4 -/*
     1.5 - *  Copyright 2009 OpenSourceStewardshipFoundation.org
     1.6 - *  Licensed under GNU General Public License version 2
     1.7 - *
     1.8 - *
     1.9 - * Author: seanhalle@yahoo.com
    1.10 - */
    1.11 -
    1.12 -
    1.13 -#include <stdio.h>
    1.14 -#include <string.h>
    1.15 -#include <errno.h>
    1.16 -#include <stdlib.h>
    1.17 -
    1.18 -#include "PrivateHash.h"
    1.19 -#include "../vmalloc.h"
    1.20 -
    1.21 -
    1.22 - HashTable *
    1.23 -makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn )
    1.24 - { HashTable * retTable;
    1.25 -   retTable = VMS__malloc( sizeof( HashTable ) );
    1.26 -
    1.27 -   retTable->freeEntryContentFn = freeFn;
    1.28 -   
    1.29 -   retTable->entries    = VMS__malloc( numHashSlots * sizeof(HashEntry *) );
    1.30 -   retTable->numEntries = 0;
    1.31 -   retTable->tableSz    = numHashSlots;
    1.32 -
    1.33 -   nullOutTablesArray( retTable );
    1.34 -
    1.35 -   return retTable;
    1.36 - }
    1.37 -
    1.38 - void
    1.39 -doubleTableSize( HashTable *table )
    1.40 - { int i, oldTableSz, newTableSz;
    1.41 -   HashEntry *entry, *nextEntry, **oldEntries, **newEntries;
    1.42 -
    1.43 -   oldTableSz = table->tableSz;
    1.44 -   oldEntries = table->entries;
    1.45 -
    1.46 -   newTableSz = 2 * oldTableSz + 1;
    1.47 -   newEntries = VMS__malloc( newTableSz * sizeof(HashEntry *) );
    1.48 -
    1.49 -   table->tableSz    = newTableSz;
    1.50 -   table->entries    = newEntries;
    1.51 -   table->numEntries = 0; //about to add them all back!
    1.52 -
    1.53 -      // move all the entries from old to new
    1.54 -   for( i=0; i < oldTableSz; i++ )
    1.55 -    { if( oldEntries[i] != NULL )
    1.56 -       { entry = oldEntries[i];
    1.57 -         while( entry != NULL )
    1.58 -          { nextEntry = entry->next;
    1.59 -            entry->next = NULL;
    1.60 -            putEntryIntoTable( entry, table ); //does not allocate anything
    1.61 -            entry = nextEntry;
    1.62 -          }
    1.63 -       }
    1.64 -    }
    1.65 - }
    1.66 -
    1.67 -void
    1.68 -nullOutTablesArray( HashTable *table )
    1.69 - { int i, tableSz;
    1.70 -   tableSz = table->tableSz;
    1.71 -   HashEntry ** entries = table->entries;
    1.72 -   for( i = 0; i < tableSz; i++ )
    1.73 -      entries[ i ] = NULL;
    1.74 - }
    1.75 -
    1.76 -unsigned int
    1.77 -hashThisKey( char* s, int hashSz )
    1.78 - { unsigned int h = 0;
    1.79 -   unsigned int i;
    1.80 -   hashkey_t* key = (hashkey_t*)s;
    1.81 -
    1.82 -   for(i=0 ; i<sizeof(hashkey_t); i++ )
    1.83 -      h = key->hashable[i] + h*31;
    1.84 -   return h % hashSz;
    1.85 - }
    1.86 -
    1.87 -/*Need this to be separated out, for use in both getParam and putParam
    1.88 - */
    1.89 -HashEntry *
    1.90 -getEntryFromTable( char *key, HashTable * table )
    1.91 - {  unsigned int
    1.92 -   hashIndex = hashThisKey( key, table->tableSz );
    1.93 -    HashEntry*
    1.94 -   hashEntry = table->entries[ hashIndex ];
    1.95 -   for( ; hashEntry != NULL; hashEntry = hashEntry->next )
    1.96 -    {
    1.97 -       if( memcmp( hashEntry->key, key, sizeof(hashkey_t) ) == 0 )
    1.98 -           return hashEntry;
    1.99 -    }
   1.100 -   return NULL;
   1.101 - }
   1.102 -
   1.103 -void *
   1.104 -getValueFromTable( char *key, HashTable * table )
   1.105 - { HashEntry *entry;
   1.106 -   entry = getEntryFromTable( key, table );
   1.107 -   if( entry == NULL ) return NULL;
   1.108 -
   1.109 -   return entry->content;
   1.110 - }
   1.111 -
   1.112 -
   1.113 -/*If key already has a value, clobber the old one and replace it
   1.114 - */
   1.115 - int
   1.116 -addValueIntoTable( char* key, void *content, HashTable *table )
   1.117 - { unsigned int hashIdx;
   1.118 -   HashEntry* hashEntry;
   1.119 -
   1.120 -   hashEntry = getEntryFromTable( key, table );
   1.121 -   if( hashEntry == NULL )
   1.122 -    { hashIdx = hashThisKey( key, table->tableSz );
   1.123 -      hashEntry = (HashEntry*) VMS__malloc( sizeof( HashEntry ) );
   1.124 -            if( hashEntry == NULL )  return 0;
   1.125 -      hashEntry->key = VMS__malloc( sizeof(hashkey_t) );
   1.126 -            if( hashEntry->key == NULL ) return 0;
   1.127 -      memcpy( hashEntry->key, key, sizeof(hashkey_t) );
   1.128 -      hashEntry->next = (table->entries)[hashIdx];
   1.129 -      (table->entries)[hashIdx] = hashEntry;
   1.130 -      table->numEntries += 1;
   1.131 -      if( table->tableSz < table->numEntries ) doubleTableSize( table );
   1.132 -    }
   1.133 -   else
   1.134 -    { (*(table->freeEntryContentFn))( hashEntry->content );
   1.135 -    }
   1.136 -   hashEntry->content = content;
   1.137 -   return 1;
   1.138 - }
   1.139 -
   1.140 - int
   1.141 -putEntryIntoTable( HashEntry *entry, HashTable *table )
   1.142 - { unsigned int hashIdx;
   1.143 -   HashEntry* testEntry;
   1.144 -
   1.145 -   testEntry = getEntryFromTable( entry->key, table );
   1.146 -   if( testEntry == NULL )
   1.147 -    { hashIdx = hashThisKey( entry->key, table->tableSz );
   1.148 -      entry->next = (table->entries)[hashIdx];
   1.149 -      (table->entries)[hashIdx] = entry;
   1.150 -      table->numEntries += 1;
   1.151 -      if( table->tableSz < table->numEntries ) doubleTableSize( table );
   1.152 -    }
   1.153 -   else
   1.154 -    { (*(table->freeEntryContentFn))( testEntry->content );
   1.155 -         //being lazy -- will create bug in code that relies on having ptr to
   1.156 -         // elem given to insert into table!
   1.157 -      testEntry->content = entry->content;
   1.158 -      entry->content = NULL;
   1.159 -      freeHashEntryButNotContent( entry );
   1.160 -    }
   1.161 -   return 1;
   1.162 - }
   1.163 -
   1.164 -/*Better version
   1.165 - */
   1.166 - void
   1.167 -untested_putEntryIntoTable( HashEntry *entry, HashTable * table )
   1.168 - { HashEntry *testEntry, *prevEntry = NULL;
   1.169 -    unsigned int
   1.170 -   hashIndex = hashThisKey( entry->key, table->tableSz );
   1.171 -   
   1.172 -   testEntry = table->entries[ hashIndex ];
   1.173 -   for( ; testEntry != NULL; testEntry = testEntry->next )
   1.174 -    { if( memcmp( testEntry->key, entry->key, sizeof(hashkey_t)) == 0 )
   1.175 -       { if( prevEntry == NULL )
   1.176 -          { table->entries[hashIndex] = entry;
   1.177 -            entry->next = testEntry->next;
   1.178 -          }
   1.179 -         else
   1.180 -          { prevEntry->next = entry;
   1.181 -            entry->next = testEntry->next;
   1.182 -          }
   1.183 -         freeHashEntryUsing( testEntry, table ); //frees content too!
   1.184 -         return;
   1.185 -       }
   1.186 -    }
   1.187 -      //wasn't found, so insert
   1.188 -   entry->next = table->entries[hashIndex];
   1.189 -   table->entries[hashIndex] = entry;
   1.190 - }
   1.191 -
   1.192 -
   1.193 -
   1.194 - bool8
   1.195 -deleteEntryFromTable( char *key, HashTable *table )
   1.196 - { HashEntry  *hashEntry;
   1.197 -   HashEntry **addrOfHashEntryPtr;
   1.198 -   unsigned int hashIndex;
   1.199 -
   1.200 -   hashIndex = hashThisKey( key, table->tableSz );
   1.201 -   addrOfHashEntryPtr = &( table->entries[ hashIndex ] );
   1.202 -   hashEntry = *addrOfHashEntryPtr;
   1.203 -   while( hashEntry != NULL )
   1.204 -    { if( memcmp( hashEntry->key, key, sizeof(hashkey_t) ) == 0 )
   1.205 -       {
   1.206 -         *addrOfHashEntryPtr = hashEntry->next;
   1.207 -         //TODO: Free the contents of entry?
   1.208 -         freeHashEntryButNotContent( hashEntry );
   1.209 -         table->numEntries -= 1;
   1.210 -         return TRUE;
   1.211 -       }
   1.212 -      addrOfHashEntryPtr = &( hashEntry->next );
   1.213 -      hashEntry = *addrOfHashEntryPtr;
   1.214 -    }
   1.215 -   return FALSE;
   1.216 - }
   1.217 - 
   1.218 -void
   1.219 -freeHashTable( HashTable *table )
   1.220 - { int i;
   1.221 -   HashEntry *hashEntry, *temp, **entries;
   1.222 -
   1.223 -   entries = table->entries;
   1.224 -   for( i=0; i < table->tableSz; i++ )
   1.225 -    { if( entries[i] != NULL )
   1.226 -       { hashEntry = entries[i];
   1.227 -         while( hashEntry != NULL )
   1.228 -          {
   1.229 -            temp = hashEntry->next;
   1.230 -            freeHashEntryUsing( hashEntry, table );
   1.231 -            hashEntry = temp;
   1.232 -          }
   1.233 -       }
   1.234 -    }
   1.235 - }
   1.236 -
   1.237 -void
   1.238 -freeHashEntryUsing( HashEntry *entry, HashTable *table )
   1.239 - {
   1.240 -   if( entry->content != NULL )
   1.241 -      (*(table->freeEntryContentFn))( entry->content );
   1.242 -   VMS__free( entry->key ); //was VMS__malloc'd above, so free it
   1.243 -   VMS__free( entry );
   1.244 - }
   1.245 -
   1.246 -void
   1.247 -freeHashEntryButNotContent( HashEntry *entry )
   1.248 - {
   1.249 -   VMS__free( entry->key ); //was VMS__malloc'd above, so free it
   1.250 -   VMS__free( entry );
   1.251 - }
   1.252 -
   1.253 +/*
   1.254 + *  Copyright 2009 OpenSourceStewardshipFoundation.org
   1.255 + *  Licensed under GNU General Public License version 2
   1.256 + *
   1.257 + *
   1.258 + * Author: seanhalle@yahoo.com
   1.259 + */
   1.260 +
   1.261 +#include "PrivateHash.h"
   1.262 +
   1.263 +
   1.264 + HashTable *
   1.265 +makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn )
   1.266 + { HashTable * retTable;
   1.267 +   retTable = VMS__malloc( sizeof( HashTable ) );
   1.268 +
   1.269 +   retTable->freeEntryContentFn = freeFn;
   1.270 +   
   1.271 +   retTable->entries    = VMS__malloc( numHashSlots * sizeof(HashEntry *) );
   1.272 +   retTable->numEntries = 0;
   1.273 +   retTable->tableSz    = numHashSlots;
   1.274 +
   1.275 +   nullOutTablesArray( retTable );
   1.276 +
   1.277 +   return retTable;
   1.278 + }
   1.279 +
   1.280 + void
   1.281 +doubleTableSize( HashTable *table )
   1.282 + { int i, oldTableSz, newTableSz;
   1.283 +   HashEntry *entry, *nextEntry, **oldEntries, **newEntries;
   1.284 +
   1.285 +   oldTableSz = table->tableSz;
   1.286 +   oldEntries = table->entries;
   1.287 +
   1.288 +   newTableSz = 2 * oldTableSz + 1;
   1.289 +   newEntries = VMS__malloc( newTableSz * sizeof(HashEntry *) );
   1.290 +
   1.291 +   table->tableSz    = newTableSz;
   1.292 +   table->entries    = newEntries;
   1.293 +   table->numEntries = 0; //about to add them all back!
   1.294 +
   1.295 +      // move all the entries from old to new
   1.296 +   for( i=0; i < oldTableSz; i++ )
   1.297 +    { if( oldEntries[i] != NULL )
   1.298 +       { entry = oldEntries[i];
   1.299 +         while( entry != NULL )
   1.300 +          { nextEntry = entry->next;
   1.301 +            entry->next = NULL;
   1.302 +            putEntryIntoTable( entry, table ); //does not allocate anything
   1.303 +            entry = nextEntry;
   1.304 +          }
   1.305 +       }
   1.306 +    }
   1.307 + }
   1.308 +
   1.309 +void
   1.310 +nullOutTablesArray( HashTable *table )
   1.311 + { int i, tableSz;
   1.312 +   tableSz = table->tableSz;
   1.313 +   HashEntry ** entries = table->entries;
   1.314 +   for( i = 0; i < tableSz; i++ )
   1.315 +      entries[ i ] = NULL;
   1.316 + }
   1.317 +
   1.318 +unsigned int
   1.319 +hashThisKey( char* s, int hashSz )
   1.320 + { unsigned int h = 0;
   1.321 +   unsigned int i;
   1.322 +   hashkey_t* key = (hashkey_t*)s;
   1.323 +
   1.324 +   for(i=0 ; i<sizeof(hashkey_t); i++ )
   1.325 +      h = key->hashable[i] + h*31;
   1.326 +   return h % hashSz;
   1.327 + }
   1.328 +
   1.329 +/*Need this to be separated out, for use in both getParam and putParam
   1.330 + */
   1.331 +HashEntry *
   1.332 +getEntryFromTable( char *key, HashTable * table )
   1.333 + {  unsigned int
   1.334 +   hashIndex = hashThisKey( key, table->tableSz );
   1.335 +    HashEntry*
   1.336 +   hashEntry = table->entries[ hashIndex ];
   1.337 +   for( ; hashEntry != NULL; hashEntry = hashEntry->next )
   1.338 +    {
   1.339 +       if( memcmp( hashEntry->key, key, sizeof(hashkey_t) ) == 0 )
   1.340 +           return hashEntry;
   1.341 +    }
   1.342 +   return NULL;
   1.343 + }
   1.344 +
   1.345 +void *
   1.346 +getValueFromTable( char *key, HashTable * table )
   1.347 + { HashEntry *entry;
   1.348 +   entry = getEntryFromTable( key, table );
   1.349 +   if( entry == NULL ) return NULL;
   1.350 +
   1.351 +   return entry->content;
   1.352 + }
   1.353 +
   1.354 +
   1.355 +/*If key already has a value, clobber the old one and replace it
   1.356 + */
   1.357 + int
   1.358 +addValueIntoTable( char* key, void *content, HashTable *table )
   1.359 + { unsigned int hashIdx;
   1.360 +   HashEntry* hashEntry;
   1.361 +
   1.362 +   hashEntry = getEntryFromTable( key, table );
   1.363 +   if( hashEntry == NULL )
   1.364 +    { hashIdx = hashThisKey( key, table->tableSz );
   1.365 +      hashEntry = (HashEntry*) VMS__malloc( sizeof( HashEntry ) );
   1.366 +            if( hashEntry == NULL )  return 0;
   1.367 +      hashEntry->key = VMS__malloc( sizeof(hashkey_t) );
   1.368 +            if( hashEntry->key == NULL ) return 0;
   1.369 +      memcpy( hashEntry->key, key, sizeof(hashkey_t) );
   1.370 +      hashEntry->next = (table->entries)[hashIdx];
   1.371 +      (table->entries)[hashIdx] = hashEntry;
   1.372 +      table->numEntries += 1;
   1.373 +      if( table->tableSz < table->numEntries ) doubleTableSize( table );
   1.374 +    }
   1.375 +   else
   1.376 +    { (*(table->freeEntryContentFn))( hashEntry->content );
   1.377 +    }
   1.378 +   hashEntry->content = content;
   1.379 +   return 1;
   1.380 + }
   1.381 +
   1.382 + int
   1.383 +putEntryIntoTable( HashEntry *entry, HashTable *table )
   1.384 + { unsigned int hashIdx;
   1.385 +   HashEntry* testEntry;
   1.386 +
   1.387 +   testEntry = getEntryFromTable( entry->key, table );
   1.388 +   if( testEntry == NULL )
   1.389 +    { hashIdx = hashThisKey( entry->key, table->tableSz );
   1.390 +      entry->next = (table->entries)[hashIdx];
   1.391 +      (table->entries)[hashIdx] = entry;
   1.392 +      table->numEntries += 1;
   1.393 +      if( table->tableSz < table->numEntries ) doubleTableSize( table );
   1.394 +    }
   1.395 +   else
   1.396 +    { (*(table->freeEntryContentFn))( testEntry->content );
   1.397 +         //being lazy -- will create bug in code that relies on having ptr to
   1.398 +         // elem given to insert into table!
   1.399 +      testEntry->content = entry->content;
   1.400 +      entry->content = NULL;
   1.401 +      freeHashEntryButNotContent( entry );
   1.402 +    }
   1.403 +   return 1;
   1.404 + }
   1.405 +
   1.406 +/*Better version
   1.407 + */
   1.408 + void
   1.409 +untested_putEntryIntoTable( HashEntry *entry, HashTable * table )
   1.410 + { HashEntry *testEntry, *prevEntry = NULL;
   1.411 +    unsigned int
   1.412 +   hashIndex = hashThisKey( entry->key, table->tableSz );
   1.413 +   
   1.414 +   testEntry = table->entries[ hashIndex ];
   1.415 +   for( ; testEntry != NULL; testEntry = testEntry->next )
   1.416 +    { if( memcmp( testEntry->key, entry->key, sizeof(hashkey_t)) == 0 )
   1.417 +       { if( prevEntry == NULL )
   1.418 +          { table->entries[hashIndex] = entry;
   1.419 +            entry->next = testEntry->next;
   1.420 +          }
   1.421 +         else
   1.422 +          { prevEntry->next = entry;
   1.423 +            entry->next = testEntry->next;
   1.424 +          }
   1.425 +         freeHashEntryUsing( testEntry, table ); //frees content too!
   1.426 +         return;
   1.427 +       }
   1.428 +    }
   1.429 +      //wasn't found, so insert
   1.430 +   entry->next = table->entries[hashIndex];
   1.431 +   table->entries[hashIndex] = entry;
   1.432 + }
   1.433 +
   1.434 +
   1.435 +
   1.436 + bool8
   1.437 +deleteEntryFromTable( char *key, HashTable *table )
   1.438 + { HashEntry  *hashEntry;
   1.439 +   HashEntry **addrOfHashEntryPtr;
   1.440 +   unsigned int hashIndex;
   1.441 +
   1.442 +   hashIndex = hashThisKey( key, table->tableSz );
   1.443 +   addrOfHashEntryPtr = &( table->entries[ hashIndex ] );
   1.444 +   hashEntry = *addrOfHashEntryPtr;
   1.445 +   while( hashEntry != NULL )
   1.446 +    { if( memcmp( hashEntry->key, key, sizeof(hashkey_t) ) == 0 )
   1.447 +       {
   1.448 +         *addrOfHashEntryPtr = hashEntry->next;
   1.449 +         //TODO: Free the contents of entry?
   1.450 +         freeHashEntryButNotContent( hashEntry );
   1.451 +         table->numEntries -= 1;
   1.452 +         return TRUE;
   1.453 +       }
   1.454 +      addrOfHashEntryPtr = &( hashEntry->next );
   1.455 +      hashEntry = *addrOfHashEntryPtr;
   1.456 +    }
   1.457 +   return FALSE;
   1.458 + }
   1.459 + 
   1.460 +void
   1.461 +freeHashTable( HashTable *table )
   1.462 + { int i;
   1.463 +   HashEntry *hashEntry, *temp, **entries;
   1.464 +
   1.465 +   entries = table->entries;
   1.466 +   for( i=0; i < table->tableSz; i++ )
   1.467 +    { if( entries[i] != NULL )
   1.468 +       { hashEntry = entries[i];
   1.469 +         while( hashEntry != NULL )
   1.470 +          {
   1.471 +            temp = hashEntry->next;
   1.472 +            freeHashEntryUsing( hashEntry, table );
   1.473 +            hashEntry = temp;
   1.474 +          }
   1.475 +       }
   1.476 +    }
   1.477 + }
   1.478 +
   1.479 +void
   1.480 +freeHashEntryUsing( HashEntry *entry, HashTable *table )
   1.481 + {
   1.482 +   if( entry->content != NULL )
   1.483 +      (*(table->freeEntryContentFn))( entry->content );
   1.484 +   VMS__free( entry->key ); //was VMS__malloc'd above, so free it
   1.485 +   VMS__free( entry );
   1.486 + }
   1.487 +
   1.488 +void
   1.489 +freeHashEntryButNotContent( HashEntry *entry )
   1.490 + {
   1.491 +   VMS__free( entry->key ); //was VMS__malloc'd above, so free it
   1.492 +   VMS__free( entry );
   1.493 + }
   1.494 +