changeset 0:ee3ad252427e

Initial add
author Me
date Sat, 22 May 2010 19:49:28 -0700
parents
children 5900d90f5d71
files PrivateHash.c PrivateHash.h
diffstat 2 files changed, 284 insertions(+), 0 deletions(-) [+]
line diff
     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/PrivateHash.c	Sat May 22 19:49:28 2010 -0700
     1.3 @@ -0,0 +1,224 @@
     1.4 +/*
     1.5 + *  Copyright 2009 OpenSourceCodeStewardshipFoundation.org
     1.6 + *  Licensed under GNU General Public License version 2
     1.7 + *
     1.8 + * NOTE: this version of SRSW correct as of April 25, 2010
     1.9 + *
    1.10 + * Author: seanhalle@yahoo.com
    1.11 + */
    1.12 +
    1.13 +
    1.14 +#include <stdio.h>
    1.15 +#include <string.h>
    1.16 +#include <errno.h>
    1.17 +#include <stdlib.h>
    1.18 +
    1.19 +#include "PrivateHash.h"
    1.20 +
    1.21 +
    1.22 + HashTable *
    1.23 +makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn )
    1.24 + { HashTable * retTable;
    1.25 +   retTable = malloc( sizeof( HashTable ) );
    1.26 +
    1.27 +   retTable->freeEntryContentFn = freeFn;
    1.28 +   
    1.29 +   retTable->entries = malloc( numHashSlots * sizeof(HashEntry *) );
    1.30 +   retTable->tableSz = numHashSlots;
    1.31 +
    1.32 +   nullOutTablesArray( retTable );
    1.33 +
    1.34 +   return retTable;
    1.35 + }
    1.36 +
    1.37 + void
    1.38 +doubleTableSize( HashTable *table )
    1.39 + { int i, oldTableSz, newTableSz;
    1.40 +   HashEntry *entry, **oldEntries, **newEntries;
    1.41 +
    1.42 +   oldTableSz = table->tableSz;
    1.43 +   oldEntries = table->entries;
    1.44 +
    1.45 +   newTableSz = 2 * oldTableSz + 1;
    1.46 +   newEntries = malloc( newTableSz * sizeof(HashEntry *) );
    1.47 +
    1.48 +   table->tableSz    = newTableSz;
    1.49 +   table->entries    = newEntries;
    1.50 +   table->numEntries = 0; //about to add them all back!
    1.51 +
    1.52 +      // move all the entries from old to new
    1.53 +   for( i=0; i < oldTableSz; i++ )
    1.54 +    { if( oldEntries[i] != NULL )
    1.55 +       { entry = oldEntries[i];
    1.56 +         while( entry != NULL )
    1.57 +          {
    1.58 +            addEntryToTable( entry, table ); //does not allocate anything
    1.59 +            entry = entry->next;
    1.60 +          }
    1.61 +       }
    1.62 +    }
    1.63 + }
    1.64 +
    1.65 + void
    1.66 +nullOutTablesArray( HashTable *table )
    1.67 + { int i, tableSz;
    1.68 +   tableSz = table->tableSz;
    1.69 +   HashEntry ** entries = table->entries;
    1.70 +   for( i = 0; i < tableSz; i++ )
    1.71 +      entries[ i ] = NULL;
    1.72 + }
    1.73 +
    1.74 + unsigned int
    1.75 +hashThisKey( char *s, int hashSz )
    1.76 + { unsigned int h = 0;
    1.77 +
    1.78 +   for( ; *s != 0; s++ )
    1.79 +      h = *s + h*31;
    1.80 +   return h % hashSz;
    1.81 + }
    1.82 +
    1.83 +/*Need this to be separated out, for use in both getParam and putParam
    1.84 + */
    1.85 + HashEntry *
    1.86 +getEntryFromTable( char *key, HashTable * table )
    1.87 + {  unsigned int
    1.88 +   hashIndex = hashKey( key, table->tableSz );
    1.89 +    HashEntry*
    1.90 +   hashEntry = table->entries[ hashIndex ];
    1.91 +   for( ; hashEntry != NULL; hashEntry = hashEntry->next )
    1.92 +    { if( strcmp( hashEntry->key, key ) == 0 )  return hashEntry;
    1.93 +    }
    1.94 +   return NULL;
    1.95 + }
    1.96 +
    1.97 + void *
    1.98 +getValueFromTable( char *key, HashTable * table )
    1.99 + { HashEntry *entry;
   1.100 +   entry = lookupKeyInHash( key, table );
   1.101 +   if( entry == NULL ) return NULL;
   1.102 +
   1.103 +   return entry->content;
   1.104 + }
   1.105 +
   1.106 + int
   1.107 +addToTable( char* key, void *content, HashTable *table )
   1.108 + { unsigned int hashIdx;
   1.109 +   HashEntry* hashEntry;
   1.110 +
   1.111 +   hashEntry = getEntryFromTable( key, table );
   1.112 +   if( hashEntry == NULL )
   1.113 +    { hashIdx = hashThisKey( key, table->tableSz );
   1.114 +      hashEntry = (HashEntry*) malloc( sizeof( HashEntry ) );
   1.115 +            if( hashEntry == NULL )  return 0;
   1.116 +      hashEntry->key = strdup_m( key ); //TODO: figure out soln for incr Sz
   1.117 +            if( hashEntry->key == NULL ) return 0;
   1.118 +      hashEntry->next = (table->entries)[hashIdx];
   1.119 +      (table->entries)[hashIdx] = hashEntry;
   1.120 +      table->numEntries += 1;
   1.121 +      if( table->tableSz < table->numEntries ) doubleTableSize( table );
   1.122 +    }
   1.123 +   else
   1.124 +    { (*(table->freeEntryContentFn))( hashEntry->content );
   1.125 +    }
   1.126 +   hashEntry->content = content;
   1.127 +   return 1;
   1.128 + }
   1.129 +
   1.130 + int
   1.131 +addEntryToTable( HashEntry *entry, HashTable *table )
   1.132 + { unsigned int hashIdx;
   1.133 +   HashEntry* testEntry;
   1.134 +
   1.135 +   testEntry = getEntryFromTable( entry->key, table );
   1.136 +   if( testEntry == NULL )
   1.137 +    { hashIdx = hashThisKey( entry->key, table->tableSz );
   1.138 +      entry->next = (table->entries)[hashIdx];
   1.139 +      (table->entries)[hashIdx] = entry;
   1.140 +      table->numEntries += 1;
   1.141 +      if( table->tableSz < table->numEntries ) doubleTableSize( table );
   1.142 +    }
   1.143 +   else
   1.144 +    { (*(table->freeEntryContentFn))( testEntry->content );
   1.145 +      testEntry->content = entry->content;
   1.146 +      entry->content = NULL;
   1.147 +      freeHashEntryUsing( entry, table );
   1.148 +    }
   1.149 +   return 1;
   1.150 + }
   1.151 +
   1.152 + bool8
   1.153 +deleteEntryFromTable( char *key, HashTable *table )
   1.154 + {
   1.155 +   table->numEntries -= 1;
   1.156 +
   1.157 + }
   1.158 +
   1.159 +
   1.160 + char*
   1.161 +strdup_m( char *o )
   1.162 + { int len = strlen(o)+1;
   1.163 +   char *ns = (char*) malloc( len * sizeof(char) );
   1.164 +   strcpy( ns, o );
   1.165 +   return ns;
   1.166 + }
   1.167 +
   1.168 +/* debugging function displays the hashtable in (key.value) pairs
   1.169 +*/
   1.170 +/*void hashTableToString( HashTable * table )
   1.171 + { int i;
   1.172 +   HashEntry *t;
   1.173 +   for( i = 0; i < table->tableSz; i++ )
   1.174 +    { t = entries[i];
   1.175 +      if( t == NULL )
   1.176 +         strcat_m( retStr, &"()" );
   1.177 +      else
   1.178 +       { strcat_m( retStr, &"(" );
   1.179 +         for( ; t != NULL; t = t->next )
   1.180 +          { strcat_m( retStr, &" " );
   1.181 +            strcat_m( retStr, t->key );
   1.182 +            strcat_m( retStr, &"." );
   1.183 +            strcat_m( retStr, paramToString( t->param ) );
   1.184 +            strcat_m( retStr, &" " );
   1.185 +          }
   1.186 +         strcat_m( retStr, &")" );
   1.187 +       }
   1.188 +    }
   1.189 + }
   1.190 +*/
   1.191 +
   1.192 +/*
   1.193 + void
   1.194 +setFnToFreeEntryContent( HashTable *table, FreeEntryContentFnPtr fnPtr )
   1.195 + {
   1.196 +   table->freeEntryContentFn = fnPtr;
   1.197 + }
   1.198 +*/
   1.199 +
   1.200 + void
   1.201 +freeHashTable( HashTable *table )
   1.202 + { int i;
   1.203 +   HashEntry *hashEntry, *temp, **entries;
   1.204 +
   1.205 +   entries = table->entries;
   1.206 +   for( i=0; i < table->tableSz; i++ )
   1.207 +    { if( entries[i] != NULL )
   1.208 +       { hashEntry = entries[i];
   1.209 +         while( hashEntry != NULL )
   1.210 +          {
   1.211 +            temp = hashEntry->next;
   1.212 +            freeHashEntryUsing( hashEntry, table );
   1.213 +            hashEntry = temp;
   1.214 +          }
   1.215 +       }
   1.216 +    }
   1.217 + }
   1.218 +
   1.219 + void
   1.220 +freeHashEntryUsing( HashEntry *entry, HashTable *table )
   1.221 + {
   1.222 +   if( entry->content != NULL )
   1.223 +      (*(table->freeEntryContentFn))( entry->content );
   1.224 +   free( entry->key ); //was malloc'd above, so free it
   1.225 +   free( entry );
   1.226 + }
   1.227 +
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/PrivateHash.h	Sat May 22 19:49:28 2010 -0700
     2.3 @@ -0,0 +1,60 @@
     2.4 +/*
     2.5 + *  Copyright 2009 OpenSourceStewardshipFoundation.org
     2.6 + *  Licensed under GNU General Public License version 2
     2.7 + *
     2.8 + * Author: seanhalle@yahoo.com
     2.9 + */
    2.10 +
    2.11 +#ifndef _PRIVATE_HASH_H
    2.12 +#define	_PRIVATE_HASH_H
    2.13 +
    2.14 +
    2.15 +#define TRUE     1
    2.16 +#define FALSE    0
    2.17 +
    2.18 +
    2.19 +#define HASHSIZE 101
    2.20 +
    2.21 +typedef struct _HashEntry HashEntry;
    2.22 +
    2.23 +struct _HashEntry
    2.24 + {
    2.25 +   char       *key;
    2.26 +   void       *content;
    2.27 +   HashEntry  *next;
    2.28 + };
    2.29 +
    2.30 +typedef void (*FreeEntryContentFnPtr)    ( void * );
    2.31 +
    2.32 +typedef struct
    2.33 + { int tableSz;
    2.34 +   int numEntries;
    2.35 +   HashEntry* *entries;
    2.36 +   FreeEntryContentFnPtr freeEntryContentFn;
    2.37 + }
    2.38 +HashTable;
    2.39 +
    2.40 +//===========================================================================
    2.41 +//   Internal functions
    2.42 +void         freeHashEntryUsing( HashEntry *entry, HashTable *table );
    2.43 +char*        strdup_m(char *o);
    2.44 +unsigned int hashThisKey( char *s, int hashSz );
    2.45 +void         nullOutTablesArray( HashTable *table );
    2.46 +void        *getEntryFromTable( char *key, HashTable *table );
    2.47 +void         doubleTableSize( HashTable *table );
    2.48 +void         addEntryToTable( HashEntry *entry, HashTable *table );
    2.49 +
    2.50 +//===========================================================================
    2.51 +//   Public functions
    2.52 +HashTable   *makeHashTable( int numHashSlots, FreeEntryContentFnPtr freeFn );
    2.53 +
    2.54 +void        *getValueFromTable( char *key, HashTable *table );
    2.55 +bool8        deleteEntryFromTable( char *key, HashTable *table );
    2.56 +bool8        deleteEntrysValueInTable( char *key, HashTable *table );
    2.57 +
    2.58 +int          addToTable( char* key, void *content, HashTable *table );
    2.59 +void         freeTable( HashTable *table );
    2.60 +//char        *paramBagToString( ParamBag * bag )
    2.61 +
    2.62 +#endif	/* _PRIVATE_HASH_H */
    2.63 +